1 | //===- CFGUpdate.h - Encode a CFG Edge Update. ------------------*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This file defines a CFG Edge Update: Insert or Delete, and two Nodes as the |
10 | // Edge ends. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_SUPPORT_CFGUPDATE_H |
15 | #define LLVM_SUPPORT_CFGUPDATE_H |
16 | |
17 | #include "llvm/ADT/ArrayRef.h" |
18 | #include "llvm/ADT/DenseMap.h" |
19 | #include "llvm/ADT/PointerIntPair.h" |
20 | #include "llvm/Support/Compiler.h" |
21 | #include "llvm/Support/Debug.h" |
22 | #include "llvm/Support/raw_ostream.h" |
23 | |
24 | namespace llvm { |
25 | namespace cfg { |
26 | enum class UpdateKind : unsigned char { Insert, Delete }; |
27 | |
28 | template <typename NodePtr> class Update { |
29 | using NodeKindPair = PointerIntPair<NodePtr, 1, UpdateKind>; |
30 | NodePtr From; |
31 | NodeKindPair ToAndKind; |
32 | |
33 | public: |
34 | Update(UpdateKind Kind, NodePtr From, NodePtr To) |
35 | : From(From), ToAndKind(To, Kind) {} |
36 | |
37 | UpdateKind getKind() const { return ToAndKind.getInt(); } |
38 | NodePtr getFrom() const { return From; } |
39 | NodePtr getTo() const { return ToAndKind.getPointer(); } |
40 | bool operator==(const Update &RHS) const { |
41 | return From == RHS.From && ToAndKind == RHS.ToAndKind; |
42 | } |
43 | |
44 | void print(raw_ostream &OS) const { |
45 | OS << (getKind() == UpdateKind::Insert ? "Insert " : "Delete " ); |
46 | getFrom()->printAsOperand(OS, false); |
47 | OS << " -> " ; |
48 | getTo()->printAsOperand(OS, false); |
49 | } |
50 | |
51 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
52 | LLVM_DUMP_METHOD void dump() const { print(OS&: dbgs()); } |
53 | #endif |
54 | }; |
55 | |
56 | // LegalizeUpdates function simplifies updates assuming a graph structure. |
57 | // This function serves double purpose: |
58 | // a) It removes redundant updates, which makes it easier to reverse-apply |
59 | // them when traversing CFG. |
60 | // b) It optimizes away updates that cancel each other out, as the end result |
61 | // is the same. |
62 | template <typename NodePtr> |
63 | void LegalizeUpdates(ArrayRef<Update<NodePtr>> AllUpdates, |
64 | SmallVectorImpl<Update<NodePtr>> &Result, |
65 | bool InverseGraph, bool ReverseResultOrder = false) { |
66 | // Count the total number of inserions of each edge. |
67 | // Each insertion adds 1 and deletion subtracts 1. The end number should be |
68 | // one of {-1 (deletion), 0 (NOP), +1 (insertion)}. Otherwise, the sequence |
69 | // of updates contains multiple updates of the same kind and we assert for |
70 | // that case. |
71 | SmallDenseMap<std::pair<NodePtr, NodePtr>, int, 4> Operations; |
72 | Operations.reserve(AllUpdates.size()); |
73 | |
74 | for (const auto &U : AllUpdates) { |
75 | NodePtr From = U.getFrom(); |
76 | NodePtr To = U.getTo(); |
77 | if (InverseGraph) |
78 | std::swap(From, To); // Reverse edge for postdominators. |
79 | |
80 | Operations[{From, To}] += (U.getKind() == UpdateKind::Insert ? 1 : -1); |
81 | } |
82 | |
83 | Result.clear(); |
84 | Result.reserve(Operations.size()); |
85 | for (auto &Op : Operations) { |
86 | const int NumInsertions = Op.second; |
87 | assert(std::abs(NumInsertions) <= 1 && "Unbalanced operations!" ); |
88 | if (NumInsertions == 0) |
89 | continue; |
90 | const UpdateKind UK = |
91 | NumInsertions > 0 ? UpdateKind::Insert : UpdateKind::Delete; |
92 | Result.push_back({UK, Op.first.first, Op.first.second}); |
93 | } |
94 | |
95 | // Make the order consistent by not relying on pointer values within the |
96 | // set. Reuse the old Operations map. |
97 | // In the future, we should sort by something else to minimize the amount |
98 | // of work needed to perform the series of updates. |
99 | for (size_t i = 0, e = AllUpdates.size(); i != e; ++i) { |
100 | const auto &U = AllUpdates[i]; |
101 | if (!InverseGraph) |
102 | Operations[{U.getFrom(), U.getTo()}] = int(i); |
103 | else |
104 | Operations[{U.getTo(), U.getFrom()}] = int(i); |
105 | } |
106 | |
107 | llvm::sort(Result, [&](const Update<NodePtr> &A, const Update<NodePtr> &B) { |
108 | const auto &OpA = Operations[{A.getFrom(), A.getTo()}]; |
109 | const auto &OpB = Operations[{B.getFrom(), B.getTo()}]; |
110 | return ReverseResultOrder ? OpA < OpB : OpA > OpB; |
111 | }); |
112 | } |
113 | |
114 | } // end namespace cfg |
115 | } // end namespace llvm |
116 | |
117 | #endif // LLVM_SUPPORT_CFGUPDATE_H |
118 | |