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: Update(UpdateKind Kind,NodePtr From,NodePtr To)34 Update(UpdateKind Kind, NodePtr From, NodePtr To) 35 : From(From), ToAndKind(To, Kind) {} 36 getKind()37 UpdateKind getKind() const { return ToAndKind.getInt(); } getFrom()38 NodePtr getFrom() const { return From; } getTo()39 NodePtr getTo() const { return ToAndKind.getPointer(); } 40 bool operator==(const Update &RHS) const { 41 return From == RHS.From && ToAndKind == RHS.ToAndKind; 42 } 43 print(raw_ostream & OS)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) dump()52 LLVM_DUMP_METHOD void dump() const { print(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