1 //===- CFGDiff.h - Define a CFG snapshot. -----------------------*- 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 specializations of GraphTraits that allows generic 10 // algorithms to see a different snapshot of a CFG. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_SUPPORT_CFGDIFF_H 15 #define LLVM_SUPPORT_CFGDIFF_H 16 17 #include "llvm/ADT/GraphTraits.h" 18 #include "llvm/ADT/iterator.h" 19 #include "llvm/ADT/iterator_range.h" 20 #include "llvm/Support/CFGUpdate.h" 21 #include "llvm/Support/type_traits.h" 22 #include <cassert> 23 #include <cstddef> 24 #include <iterator> 25 26 // Two booleans are used to define orders in graphs: 27 // InverseGraph defines when we need to reverse the whole graph and is as such 28 // also equivalent to applying updates in reverse. 29 // InverseEdge defines whether we want to change the edges direction. E.g., for 30 // a non-inversed graph, the children are naturally the successors when 31 // InverseEdge is false and the predecessors when InverseEdge is true. 32 33 namespace llvm { 34 35 namespace detail { 36 template <typename Range> 37 auto reverse_if_helper(Range &&R, std::integral_constant<bool, false>) { 38 return std::forward<Range>(R); 39 } 40 41 template <typename Range> 42 auto reverse_if_helper(Range &&R, std::integral_constant<bool, true>) { 43 return llvm::reverse(std::forward<Range>(R)); 44 } 45 46 template <bool B, typename Range> auto reverse_if(Range &&R) { 47 return reverse_if_helper(std::forward<Range>(R), 48 std::integral_constant<bool, B>{}); 49 } 50 } // namespace detail 51 52 // GraphDiff defines a CFG snapshot: given a set of Update<NodePtr>, provides 53 // a getChildren method to get a Node's children based on the additional updates 54 // in the snapshot. The current diff treats the CFG as a graph rather than a 55 // multigraph. Added edges are pruned to be unique, and deleted edges will 56 // remove all existing edges between two blocks. 57 template <typename NodePtr, bool InverseGraph = false> class GraphDiff { 58 struct DeletesInserts { 59 SmallVector<NodePtr, 2> DI[2]; 60 }; 61 using UpdateMapType = SmallDenseMap<NodePtr, DeletesInserts>; 62 UpdateMapType Succ; 63 UpdateMapType Pred; 64 65 // By default, it is assumed that, given a CFG and a set of updates, we wish 66 // to apply these updates as given. If UpdatedAreReverseApplied is set, the 67 // updates will be applied in reverse: deleted edges are considered re-added 68 // and inserted edges are considered deleted when returning children. 69 bool UpdatedAreReverseApplied; 70 71 // Keep the list of legalized updates for a deterministic order of updates 72 // when using a GraphDiff for incremental updates in the DominatorTree. 73 // The list is kept in reverse to allow popping from end. 74 SmallVector<cfg::Update<NodePtr>, 4> LegalizedUpdates; 75 76 void printMap(raw_ostream &OS, const UpdateMapType &M) const { 77 StringRef DIText[2] = {"Delete", "Insert"}; 78 for (auto Pair : M) { 79 for (unsigned IsInsert = 0; IsInsert <= 1; ++IsInsert) { 80 OS << DIText[IsInsert] << " edges: \n"; 81 for (auto Child : Pair.second.DI[IsInsert]) { 82 OS << "("; 83 Pair.first->printAsOperand(OS, false); 84 OS << ", "; 85 Child->printAsOperand(OS, false); 86 OS << ") "; 87 } 88 } 89 } 90 OS << "\n"; 91 } 92 93 public: 94 GraphDiff() : UpdatedAreReverseApplied(false) {} 95 GraphDiff(ArrayRef<cfg::Update<NodePtr>> Updates, 96 bool ReverseApplyUpdates = false) { 97 cfg::LegalizeUpdates<NodePtr>(Updates, LegalizedUpdates, InverseGraph); 98 for (auto U : LegalizedUpdates) { 99 unsigned IsInsert = 100 (U.getKind() == cfg::UpdateKind::Insert) == !ReverseApplyUpdates; 101 Succ[U.getFrom()].DI[IsInsert].push_back(U.getTo()); 102 Pred[U.getTo()].DI[IsInsert].push_back(U.getFrom()); 103 } 104 UpdatedAreReverseApplied = ReverseApplyUpdates; 105 } 106 107 auto getLegalizedUpdates() const { 108 return make_range(LegalizedUpdates.begin(), LegalizedUpdates.end()); 109 } 110 111 unsigned getNumLegalizedUpdates() const { return LegalizedUpdates.size(); } 112 113 cfg::Update<NodePtr> popUpdateForIncrementalUpdates() { 114 assert(!LegalizedUpdates.empty() && "No updates to apply!"); 115 auto U = LegalizedUpdates.pop_back_val(); 116 unsigned IsInsert = 117 (U.getKind() == cfg::UpdateKind::Insert) == !UpdatedAreReverseApplied; 118 auto &SuccDIList = Succ[U.getFrom()]; 119 auto &SuccList = SuccDIList.DI[IsInsert]; 120 assert(SuccList.back() == U.getTo()); 121 SuccList.pop_back(); 122 if (SuccList.empty() && SuccDIList.DI[!IsInsert].empty()) 123 Succ.erase(U.getFrom()); 124 125 auto &PredDIList = Pred[U.getTo()]; 126 auto &PredList = PredDIList.DI[IsInsert]; 127 assert(PredList.back() == U.getFrom()); 128 PredList.pop_back(); 129 if (PredList.empty() && PredDIList.DI[!IsInsert].empty()) 130 Pred.erase(U.getTo()); 131 return U; 132 } 133 134 using VectRet = SmallVector<NodePtr, 8>; 135 template <bool InverseEdge> VectRet getChildren(NodePtr N) const { 136 using DirectedNodeT = 137 std::conditional_t<InverseEdge, Inverse<NodePtr>, NodePtr>; 138 auto R = children<DirectedNodeT>(N); 139 VectRet Res = VectRet(detail::reverse_if<!InverseEdge>(R)); 140 141 // Remove nullptr children for clang. 142 llvm::erase(Res, nullptr); 143 144 auto &Children = (InverseEdge != InverseGraph) ? Pred : Succ; 145 auto It = Children.find(N); 146 if (It == Children.end()) 147 return Res; 148 149 // Remove children present in the CFG but not in the snapshot. 150 for (auto *Child : It->second.DI[0]) 151 llvm::erase(Res, Child); 152 153 // Add children present in the snapshot for not in the real CFG. 154 auto &AddedChildren = It->second.DI[1]; 155 llvm::append_range(Res, AddedChildren); 156 157 return Res; 158 } 159 160 void print(raw_ostream &OS) const { 161 OS << "===== GraphDiff: CFG edge changes to create a CFG snapshot. \n" 162 "===== (Note: notion of children/inverse_children depends on " 163 "the direction of edges and the graph.)\n"; 164 OS << "Children to delete/insert:\n\t"; 165 printMap(OS, Succ); 166 OS << "Inverse_children to delete/insert:\n\t"; 167 printMap(OS, Pred); 168 OS << "\n"; 169 } 170 171 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 172 LLVM_DUMP_METHOD void dump() const { print(dbgs()); } 173 #endif 174 }; 175 } // end namespace llvm 176 177 #endif // LLVM_SUPPORT_CFGDIFF_H 178