contrib/llvm/include/llvm/IR/CFGDiff.h

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