Olivier Deprez | f4ef2d0 | 2021-04-20 13:36:24 +0200 | [diff] [blame] | 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_value(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_value(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 |