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