1 //===- CFGUpdate.h - Encode a CFG Edge Update. ------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines a CFG Edge Update: Insert or Delete, and two Nodes as the
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_SUPPORT_CFGUPDATE_H
16 #define LLVM_SUPPORT_CFGUPDATE_H
18 #include "llvm/ADT/APInt.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/PointerIntPair.h"
21 #include "llvm/Support/Compiler.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/raw_ostream.h"
27 enum class UpdateKind : unsigned char { Insert, Delete };
29 template <typename NodePtr> class Update {
30 using NodeKindPair = PointerIntPair<NodePtr, 1, UpdateKind>;
32 NodeKindPair ToAndKind;
35 Update(UpdateKind Kind, NodePtr From, NodePtr To)
36 : From(From), ToAndKind(To, Kind) {}
38 UpdateKind getKind() const { return ToAndKind.getInt(); }
39 NodePtr getFrom() const { return From; }
40 NodePtr getTo() const { return ToAndKind.getPointer(); }
41 bool operator==(const Update &RHS) const {
42 return From == RHS.From && ToAndKind == RHS.ToAndKind;
45 void print(raw_ostream &OS) const {
46 OS << (getKind() == UpdateKind::Insert ? "Insert " : "Delete ");
47 getFrom()->printAsOperand(OS, false);
49 getTo()->printAsOperand(OS, false);
52 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
53 LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
57 // LegalizeUpdates function simplifies updates assuming a graph structure.
58 // This function serves double purpose:
59 // a) It removes redundant updates, which makes it easier to reverse-apply
60 // them when traversing CFG.
61 // b) It optimizes away updates that cancel each other out, as the end result
63 template <typename NodePtr>
64 void LegalizeUpdates(ArrayRef<Update<NodePtr>> AllUpdates,
65 SmallVectorImpl<Update<NodePtr>> &Result,
67 // Count the total number of inserions of each edge.
68 // Each insertion adds 1 and deletion subtracts 1. The end number should be
69 // one of {-1 (deletion), 0 (NOP), +1 (insertion)}. Otherwise, the sequence
70 // of updates contains multiple updates of the same kind and we assert for
72 SmallDenseMap<std::pair<NodePtr, NodePtr>, int, 4> Operations;
73 Operations.reserve(AllUpdates.size());
75 for (const auto &U : AllUpdates) {
76 NodePtr From = U.getFrom();
77 NodePtr To = U.getTo();
79 std::swap(From, To); // Reverse edge for postdominators.
81 Operations[{From, To}] += (U.getKind() == UpdateKind::Insert ? 1 : -1);
85 Result.reserve(Operations.size());
86 for (auto &Op : Operations) {
87 const int NumInsertions = Op.second;
88 assert(std::abs(NumInsertions) <= 1 && "Unbalanced operations!");
89 if (NumInsertions == 0)
92 NumInsertions > 0 ? UpdateKind::Insert : UpdateKind::Delete;
93 Result.push_back({UK, Op.first.first, Op.first.second});
96 // Make the order consistent by not relying on pointer values within the
97 // set. Reuse the old Operations map.
98 // In the future, we should sort by something else to minimize the amount
99 // of work needed to perform the series of updates.
100 for (size_t i = 0, e = AllUpdates.size(); i != e; ++i) {
101 const auto &U = AllUpdates[i];
103 Operations[{U.getFrom(), U.getTo()}] = int(i);
105 Operations[{U.getTo(), U.getFrom()}] = int(i);
109 [&Operations](const Update<NodePtr> &A, const Update<NodePtr> &B) {
110 return Operations[{A.getFrom(), A.getTo()}] >
111 Operations[{B.getFrom(), B.getTo()}];
115 } // end namespace cfg
116 } // end namespace llvm
118 #endif // LLVM_SUPPORT_CFGUPDATE_H