include/llvm/IR/CFGDiff.h

   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_IR_CFGDIFF_H
  15 #define LLVM_IR_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/IR/BasicBlock.h"
  21 #include "llvm/IR/CFG.h"
  22 #include "llvm/Support/CFGUpdate.h"
  23 #include "llvm/Support/type_traits.h"
  24 #include <cassert>
  25 #include <cstddef>
  26 #include <iterator>
  27
  28 // Two booleans are used to define orders in graphs:
  29 // InverseGraph defines when we need to reverse the whole graph and is as such
  30 // also equivalent to applying updates in reverse.
  31 // InverseEdge defines whether we want to change the edges direction. E.g., for
  32 // a non-inversed graph, the children are naturally the successors when
  33 // InverseEdge is false and the predecessors when InverseEdge is true.
  34
  35 // We define two base clases that call into GraphDiff, one for successors
  36 // (CFGSuccessors), where InverseEdge is false, and one for predecessors
  37 // (CFGPredecessors), where InverseEdge is true.
  38 // FIXME: Further refactoring may merge the two base classes into a single one
  39 // templated / parametrized on using succ_iterator/pred_iterator and false/true
  40 // for the InverseEdge.
  41
  42 // CFGViewSuccessors and CFGViewPredecessors, both can be parametrized to
  43 // consider the graph inverted or not (i.e. InverseGraph). Successors
  44 // implicitly has InverseEdge = false and Predecessors implicitly has
  45 // InverseEdge = true (see calls to GraphDiff methods in there). The GraphTraits
  46 // instantiations that follow define the value of InverseGraph.
  47
  48 // GraphTraits instantiations:
  49 // - GraphDiff<BasicBlock *> is equivalent to InverseGraph = false
  50 // - GraphDiff<Inverse<BasicBlock *>> is equivalent to InverseGraph = true
  51 // - second pair item is BasicBlock *, then InverseEdge = false (so it inherits
  52 // from CFGViewSuccessors).
  53 // - second pair item is Inverse<BasicBlock *>, then InverseEdge = true (so it
  54 // inherits from CFGViewPredecessors).
  55
  56 // The 4 GraphTraits are as follows:
  57 // 1. std::pair<const GraphDiff<BasicBlock *> *, BasicBlock *>> :
  58 //        CFGViewSuccessors<false>
  59 // Regular CFG, children means successors, InverseGraph = false,
  60 // InverseEdge = false.
  61 // 2. std::pair<const GraphDiff<Inverse<BasicBlock *>> *, BasicBlock *>> :
  62 //        CFGViewSuccessors<true>
  63 // Reverse the graph, get successors but reverse-apply updates,
  64 // InverseGraph = true, InverseEdge = false.
  65 // 3. std::pair<const GraphDiff<BasicBlock *> *, Inverse<BasicBlock *>>> :
  66 //        CFGViewPredecessors<false>
  67 // Regular CFG, reverse edges, so children mean predecessors,
  68 // InverseGraph = false, InverseEdge = true.
  69 // 4. std::pair<const GraphDiff<Inverse<BasicBlock *>> *, Inverse<BasicBlock *>>
  70 //        : CFGViewPredecessors<true>
  71 // Reverse the graph and the edges, InverseGraph = true, InverseEdge = true.
  72
  73 namespace llvm {
  74
  75 // GraphDiff defines a CFG snapshot: given a set of Update<NodePtr>, provide
  76 // utilities to skip edges marked as deleted and return a set of edges marked as
  77 // newly inserted. The current diff treats the CFG as a graph rather than a
  78 // multigraph. Added edges are pruned to be unique, and deleted edges will
  79 // remove all existing edges between two blocks.
  80 template <typename NodePtr, bool InverseGraph = false> class GraphDiff {
  81   using UpdateMapType = SmallDenseMap<NodePtr, SmallVector<NodePtr, 2>>;
  82   UpdateMapType SuccInsert;
  83   UpdateMapType SuccDelete;
  84   UpdateMapType PredInsert;
  85   UpdateMapType PredDelete;
  86   // Using a singleton empty vector for all BasicBlock requests with no
  87   // children.
  88   SmallVector<NodePtr, 1> Empty;
  89
  90   void printMap(raw_ostream &OS, const UpdateMapType &M) const {
  91     for (auto Pair : M)
  92       for (auto Child : Pair.second) {
  93         OS << "(";
  94         Pair.first->printAsOperand(OS, false);
  95         OS << ", ";
  96         Child->printAsOperand(OS, false);
  97         OS << ") ";
  98       }
  99     OS << "\n";
 100   }
 101
 102 public:
 103   GraphDiff() {}
 104   GraphDiff(ArrayRef<cfg::Update<NodePtr>> Updates) {
 105     SmallVector<cfg::Update<NodePtr>, 4> LegalizedUpdates;
 106     cfg::LegalizeUpdates<NodePtr>(Updates, LegalizedUpdates, InverseGraph);
 107     for (auto U : LegalizedUpdates) {
 108       if (U.getKind() == cfg::UpdateKind::Insert) {
 109         SuccInsert[U.getFrom()].push_back(U.getTo());
 110         PredInsert[U.getTo()].push_back(U.getFrom());
 111       } else {
 112         SuccDelete[U.getFrom()].push_back(U.getTo());
 113         PredDelete[U.getTo()].push_back(U.getFrom());
 114       }
 115     }
 116   }
 117
 118   bool ignoreChild(const NodePtr BB, NodePtr EdgeEnd, bool InverseEdge) const {
 119     auto &DeleteChildren =
 120         (InverseEdge != InverseGraph) ? PredDelete : SuccDelete;
 121     auto It = DeleteChildren.find(BB);
 122     if (It == DeleteChildren.end())
 123       return false;
 124     auto &EdgesForBB = It->second;
 125     return llvm::find(EdgesForBB, EdgeEnd) != EdgesForBB.end();
 126   }
 127
 128   iterator_range<typename SmallVectorImpl<NodePtr>::const_iterator>
 129   getAddedChildren(const NodePtr BB, bool InverseEdge) const {
 130     auto &InsertChildren =
 131         (InverseEdge != InverseGraph) ? PredInsert : SuccInsert;
 132     auto It = InsertChildren.find(BB);
 133     if (It == InsertChildren.end())
 134       return make_range(Empty.begin(), Empty.end());
 135     return make_range(It->second.begin(), It->second.end());
 136   }
 137
 138   void print(raw_ostream &OS) const {
 139     OS << "===== GraphDiff: CFG edge changes to create a CFG snapshot. \n"
 140           "===== (Note: notion of children/inverse_children depends on "
 141           "the direction of edges and the graph.)\n";
 142     OS << "Children to insert:\n\t";
 143     printMap(OS, SuccInsert);
 144     OS << "Children to delete:\n\t";
 145     printMap(OS, SuccDelete);
 146     OS << "Inverse_children to insert:\n\t";
 147     printMap(OS, PredInsert);
 148     OS << "Inverse_children to delete:\n\t";
 149     printMap(OS, PredDelete);
 150     OS << "\n";
 151   }
 152
 153 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 154   LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
 155 #endif
 156 };
 157
 158 template <bool InverseGraph = false> struct CFGViewSuccessors {
 159   using DataRef = const GraphDiff<BasicBlock *, InverseGraph> *;
 160   using NodeRef = std::pair<DataRef, BasicBlock *>;
 161
 162   using ExistingChildIterator =
 163       WrappedPairNodeDataIterator<succ_iterator, NodeRef, DataRef>;
 164   struct DeletedEdgesFilter {
 165     BasicBlock *BB;
 166     DeletedEdgesFilter(BasicBlock *BB) : BB(BB){};
 167     bool operator()(NodeRef N) const {
 168       return !N.first->ignoreChild(BB, N.second, false);
 169     }
 170   };
 171   using FilterExistingChildrenIterator =
 172       filter_iterator<ExistingChildIterator, DeletedEdgesFilter>;
 173
 174   using vec_iterator = SmallVectorImpl<BasicBlock *>::const_iterator;
 175   using AddNewChildrenIterator =
 176       WrappedPairNodeDataIterator<vec_iterator, NodeRef, DataRef>;
 177   using ChildIteratorType =
 178       concat_iterator<NodeRef, FilterExistingChildrenIterator,
 179                       AddNewChildrenIterator>;
 180
 181   static ChildIteratorType child_begin(NodeRef N) {
 182     auto InsertVec = N.first->getAddedChildren(N.second, false);
 183     // filter iterator init:
 184     auto firstit = make_filter_range(
 185         make_range<ExistingChildIterator>({succ_begin(N.second), N.first},
 186                                           {succ_end(N.second), N.first}),
 187         DeletedEdgesFilter(N.second));
 188     // new inserts iterator init:
 189     auto secondit = make_range<AddNewChildrenIterator>(
 190         {InsertVec.begin(), N.first}, {InsertVec.end(), N.first});
 191
 192     return concat_iterator<NodeRef, FilterExistingChildrenIterator,
 193                            AddNewChildrenIterator>(firstit, secondit);
 194   }
 195
 196   static ChildIteratorType child_end(NodeRef N) {
 197     auto InsertVec = N.first->getAddedChildren(N.second, false);
 198     // filter iterator init:
 199     auto firstit = make_filter_range(
 200         make_range<ExistingChildIterator>({succ_end(N.second), N.first},
 201                                           {succ_end(N.second), N.first}),
 202         DeletedEdgesFilter(N.second));
 203     // new inserts iterator init:
 204     auto secondit = make_range<AddNewChildrenIterator>(
 205         {InsertVec.end(), N.first}, {InsertVec.end(), N.first});
 206
 207     return concat_iterator<NodeRef, FilterExistingChildrenIterator,
 208                            AddNewChildrenIterator>(firstit, secondit);
 209   }
 210 };
 211
 212 template <bool InverseGraph = false> struct CFGViewPredecessors {
 213   using DataRef = const GraphDiff<BasicBlock *, InverseGraph> *;
 214   using NodeRef = std::pair<DataRef, BasicBlock *>;
 215
 216   using ExistingChildIterator =
 217       WrappedPairNodeDataIterator<pred_iterator, NodeRef, DataRef>;
 218   struct DeletedEdgesFilter {
 219     BasicBlock *BB;
 220     DeletedEdgesFilter(BasicBlock *BB) : BB(BB){};
 221     bool operator()(NodeRef N) const {
 222       return !N.first->ignoreChild(BB, N.second, true);
 223     }
 224   };
 225   using FilterExistingChildrenIterator =
 226       filter_iterator<ExistingChildIterator, DeletedEdgesFilter>;
 227
 228   using vec_iterator = SmallVectorImpl<BasicBlock *>::const_iterator;
 229   using AddNewChildrenIterator =
 230       WrappedPairNodeDataIterator<vec_iterator, NodeRef, DataRef>;
 231   using ChildIteratorType =
 232       concat_iterator<NodeRef, FilterExistingChildrenIterator,
 233                       AddNewChildrenIterator>;
 234
 235   static ChildIteratorType child_begin(NodeRef N) {
 236     auto InsertVec = N.first->getAddedChildren(N.second, true);
 237     // filter iterator init:
 238     auto firstit = make_filter_range(
 239         make_range<ExistingChildIterator>({pred_begin(N.second), N.first},
 240                                           {pred_end(N.second), N.first}),
 241         DeletedEdgesFilter(N.second));
 242     // new inserts iterator init:
 243     auto secondit = make_range<AddNewChildrenIterator>(
 244         {InsertVec.begin(), N.first}, {InsertVec.end(), N.first});
 245
 246     return concat_iterator<NodeRef, FilterExistingChildrenIterator,
 247                            AddNewChildrenIterator>(firstit, secondit);
 248   }
 249
 250   static ChildIteratorType child_end(NodeRef N) {
 251     auto InsertVec = N.first->getAddedChildren(N.second, true);
 252     // filter iterator init:
 253     auto firstit = make_filter_range(
 254         make_range<ExistingChildIterator>({pred_end(N.second), N.first},
 255                                           {pred_end(N.second), N.first}),
 256         DeletedEdgesFilter(N.second));
 257     // new inserts iterator init:
 258     auto secondit = make_range<AddNewChildrenIterator>(
 259         {InsertVec.end(), N.first}, {InsertVec.end(), N.first});
 260
 261     return concat_iterator<NodeRef, FilterExistingChildrenIterator,
 262                            AddNewChildrenIterator>(firstit, secondit);
 263   }
 264 };
 265
 266 template <>
 267 struct GraphTraits<
 268     std::pair<const GraphDiff<BasicBlock *, false> *, BasicBlock *>>
 269     : CFGViewSuccessors<false> {};
 270 template <>
 271 struct GraphTraits<
 272     std::pair<const GraphDiff<BasicBlock *, true> *, BasicBlock *>>
 273     : CFGViewSuccessors<true> {};
 274 template <>
 275 struct GraphTraits<
 276     std::pair<const GraphDiff<BasicBlock *, false> *, Inverse<BasicBlock *>>>
 277     : CFGViewPredecessors<false> {};
 278 template <>
 279 struct GraphTraits<
 280     std::pair<const GraphDiff<BasicBlock *, true> *, Inverse<BasicBlock *>>>
 281     : CFGViewPredecessors<true> {};
 282 } // end namespace llvm
 283
 284 #endif // LLVM_IR_CFGDIFF_H