contrib/llvm/include/llvm/Analysis/IntervalIterator.h

   1 //===- IntervalIterator.h - Interval Iterator Declaration -------*- 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 an iterator that enumerates the intervals in a control flow
  11 // graph of some sort.  This iterator is parametric, allowing iterator over the
  12 // following types of graphs:
  13 //
  14 //  1. A Function* object, composed of BasicBlock nodes.
  15 //  2. An IntervalPartition& object, composed of Interval nodes.
  16 //
  17 // This iterator is defined to walk the control flow graph, returning intervals
  18 // in depth first order.  These intervals are completely filled in except for
  19 // the predecessor fields (the successor information is filled in however).
  20 //
  21 // By default, the intervals created by this iterator are deleted after they
  22 // are no longer any use to the iterator.  This behavior can be changed by
  23 // passing a false value into the intervals_begin() function. This causes the
  24 // IOwnMem member to be set, and the intervals to not be deleted.
  25 //
  26 // It is only safe to use this if all of the intervals are deleted by the caller
  27 // and all of the intervals are processed.  However, the user of the iterator is
  28 // not allowed to modify or delete the intervals until after the iterator has
  29 // been used completely.  The IntervalPartition class uses this functionality.
  30 //
  31 //===----------------------------------------------------------------------===//
  32
  33 #ifndef LLVM_ANALYSIS_INTERVALITERATOR_H
  34 #define LLVM_ANALYSIS_INTERVALITERATOR_H
  35
  36 #include "llvm/ADT/GraphTraits.h"
  37 #include "llvm/Analysis/Interval.h"
  38 #include "llvm/Analysis/IntervalPartition.h"
  39 #include "llvm/IR/CFG.h"
  40 #include "llvm/IR/Function.h"
  41 #include "llvm/Support/ErrorHandling.h"
  42 #include <algorithm>
  43 #include <cassert>
  44 #include <iterator>
  45 #include <set>
  46 #include <utility>
  47 #include <vector>
  48
  49 namespace llvm {
  50
  51 class BasicBlock;
  52
  53 // getNodeHeader - Given a source graph node and the source graph, return the
  54 // BasicBlock that is the header node.  This is the opposite of
  55 // getSourceGraphNode.
  56 inline BasicBlock *getNodeHeader(BasicBlock *BB) { return BB; }
  57 inline BasicBlock *getNodeHeader(Interval *I) { return I->getHeaderNode(); }
  58
  59 // getSourceGraphNode - Given a BasicBlock and the source graph, return the
  60 // source graph node that corresponds to the BasicBlock.  This is the opposite
  61 // of getNodeHeader.
  62 inline BasicBlock *getSourceGraphNode(Function *, BasicBlock *BB) {
  63   return BB;
  64 }
  65 inline Interval *getSourceGraphNode(IntervalPartition *IP, BasicBlock *BB) {
  66   return IP->getBlockInterval(BB);
  67 }
  68
  69 // addNodeToInterval - This method exists to assist the generic ProcessNode
  70 // with the task of adding a node to the new interval, depending on the
  71 // type of the source node.  In the case of a CFG source graph (BasicBlock
  72 // case), the BasicBlock itself is added to the interval.
  73 inline void addNodeToInterval(Interval *Int, BasicBlock *BB) {
  74   Int->Nodes.push_back(BB);
  75 }
  76
  77 // addNodeToInterval - This method exists to assist the generic ProcessNode
  78 // with the task of adding a node to the new interval, depending on the
  79 // type of the source node.  In the case of a CFG source graph (BasicBlock
  80 // case), the BasicBlock itself is added to the interval.  In the case of
  81 // an IntervalPartition source graph (Interval case), all of the member
  82 // BasicBlocks are added to the interval.
  83 inline void addNodeToInterval(Interval *Int, Interval *I) {
  84   // Add all of the nodes in I as new nodes in Int.
  85   Int->Nodes.insert(Int->Nodes.end(), I->Nodes.begin(), I->Nodes.end());
  86 }
  87
  88 template<class NodeTy, class OrigContainer_t, class GT = GraphTraits<NodeTy *>,
  89          class IGT = GraphTraits<Inverse<NodeTy *>>>
  90 class IntervalIterator {
  91   std::vector<std::pair<Interval *, typename Interval::succ_iterator>> IntStack;
  92   std::set<BasicBlock *> Visited;
  93   OrigContainer_t *OrigContainer;
  94   bool IOwnMem;     // If True, delete intervals when done with them
  95                     // See file header for conditions of use
  96
  97 public:
  98   using iterator_category = std::forward_iterator_tag;
  99
 100   IntervalIterator() = default; // End iterator, empty stack
 101
 102   IntervalIterator(Function *M, bool OwnMemory) : IOwnMem(OwnMemory) {
 103     OrigContainer = M;
 104     if (!ProcessInterval(&M->front())) {
 105       llvm_unreachable("ProcessInterval should never fail for first interval!");
 106     }
 107   }
 108
 109   IntervalIterator(IntervalIterator &&x)
 110       : IntStack(std::move(x.IntStack)), Visited(std::move(x.Visited)),
 111         OrigContainer(x.OrigContainer), IOwnMem(x.IOwnMem) {
 112     x.IOwnMem = false;
 113   }
 114
 115   IntervalIterator(IntervalPartition &IP, bool OwnMemory) : IOwnMem(OwnMemory) {
 116     OrigContainer = &IP;
 117     if (!ProcessInterval(IP.getRootInterval())) {
 118       llvm_unreachable("ProcessInterval should never fail for first interval!");
 119     }
 120   }
 121
 122   ~IntervalIterator() {
 123     if (IOwnMem)
 124       while (!IntStack.empty()) {
 125         delete operator*();
 126         IntStack.pop_back();
 127       }
 128   }
 129
 130   bool operator==(const IntervalIterator &x) const {
 131     return IntStack == x.IntStack;
 132   }
 133   bool operator!=(const IntervalIterator &x) const { return !(*this == x); }
 134
 135   const Interval *operator*() const { return IntStack.back().first; }
 136   Interval *operator*() { return IntStack.back().first; }
 137   const Interval *operator->() const { return operator*(); }
 138   Interval *operator->() { return operator*(); }
 139
 140   IntervalIterator &operator++() { // Preincrement
 141     assert(!IntStack.empty() && "Attempting to use interval iterator at end!");
 142     do {
 143       // All of the intervals on the stack have been visited.  Try visiting
 144       // their successors now.
 145       Interval::succ_iterator &SuccIt = IntStack.back().second,
 146                                 EndIt = succ_end(IntStack.back().first);
 147       while (SuccIt != EndIt) {                 // Loop over all interval succs
 148         bool Done = ProcessInterval(getSourceGraphNode(OrigContainer, *SuccIt));
 149         ++SuccIt;                               // Increment iterator
 150         if (Done) return *this;                 // Found a new interval! Use it!
 151       }
 152
 153       // Free interval memory... if necessary
 154       if (IOwnMem) delete IntStack.back().first;
 155
 156       // We ran out of successors for this interval... pop off the stack
 157       IntStack.pop_back();
 158     } while (!IntStack.empty());
 159
 160     return *this;
 161   }
 162
 163   IntervalIterator operator++(int) { // Postincrement
 164     IntervalIterator tmp = *this;
 165     ++*this;
 166     return tmp;
 167   }
 168
 169 private:
 170   // ProcessInterval - This method is used during the construction of the
 171   // interval graph.  It walks through the source graph, recursively creating
 172   // an interval per invocation until the entire graph is covered.  This uses
 173   // the ProcessNode method to add all of the nodes to the interval.
 174   //
 175   // This method is templated because it may operate on two different source
 176   // graphs: a basic block graph, or a preexisting interval graph.
 177   bool ProcessInterval(NodeTy *Node) {
 178     BasicBlock *Header = getNodeHeader(Node);
 179     if (!Visited.insert(Header).second)
 180       return false;
 181
 182     Interval *Int = new Interval(Header);
 183
 184     // Check all of our successors to see if they are in the interval...
 185     for (typename GT::ChildIteratorType I = GT::child_begin(Node),
 186            E = GT::child_end(Node); I != E; ++I)
 187       ProcessNode(Int, getSourceGraphNode(OrigContainer, *I));
 188
 189     IntStack.push_back(std::make_pair(Int, succ_begin(Int)));
 190     return true;
 191   }
 192
 193   // ProcessNode - This method is called by ProcessInterval to add nodes to the
 194   // interval being constructed, and it is also called recursively as it walks
 195   // the source graph.  A node is added to the current interval only if all of
 196   // its predecessors are already in the graph.  This also takes care of keeping
 197   // the successor set of an interval up to date.
 198   //
 199   // This method is templated because it may operate on two different source
 200   // graphs: a basic block graph, or a preexisting interval graph.
 201   void ProcessNode(Interval *Int, NodeTy *Node) {
 202     assert(Int && "Null interval == bad!");
 203     assert(Node && "Null Node == bad!");
 204
 205     BasicBlock *NodeHeader = getNodeHeader(Node);
 206
 207     if (Visited.count(NodeHeader)) {     // Node already been visited?
 208       if (Int->contains(NodeHeader)) {   // Already in this interval...
 209         return;
 210       } else {                           // In other interval, add as successor
 211         if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
 212           Int->Successors.push_back(NodeHeader);
 213       }
 214     } else {                             // Otherwise, not in interval yet
 215       for (typename IGT::ChildIteratorType I = IGT::child_begin(Node),
 216              E = IGT::child_end(Node); I != E; ++I) {
 217         if (!Int->contains(*I)) {        // If pred not in interval, we can't be
 218           if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
 219             Int->Successors.push_back(NodeHeader);
 220           return;                        // See you later
 221         }
 222       }
 223
 224       // If we get here, then all of the predecessors of BB are in the interval
 225       // already.  In this case, we must add BB to the interval!
 226       addNodeToInterval(Int, Node);
 227       Visited.insert(NodeHeader);     // The node has now been visited!
 228
 229       if (Int->isSuccessor(NodeHeader)) {
 230         // If we were in the successor list from before... remove from succ list
 231         Int->Successors.erase(std::remove(Int->Successors.begin(),
 232                                           Int->Successors.end(), NodeHeader),
 233                               Int->Successors.end());
 234       }
 235
 236       // Now that we have discovered that Node is in the interval, perhaps some
 237       // of its successors are as well?
 238       for (typename GT::ChildIteratorType It = GT::child_begin(Node),
 239              End = GT::child_end(Node); It != End; ++It)
 240         ProcessNode(Int, getSourceGraphNode(OrigContainer, *It));
 241     }
 242   }
 243 };
 244
 245 using function_interval_iterator = IntervalIterator<BasicBlock, Function>;
 246 using interval_part_interval_iterator =
 247     IntervalIterator<Interval, IntervalPartition>;
 248
 249 inline function_interval_iterator intervals_begin(Function *F,
 250                                                   bool DeleteInts = true) {
 251   return function_interval_iterator(F, DeleteInts);
 252 }
 253 inline function_interval_iterator intervals_end(Function *) {
 254   return function_interval_iterator();
 255 }
 256
 257 inline interval_part_interval_iterator
 258    intervals_begin(IntervalPartition &IP, bool DeleteIntervals = true) {
 259   return interval_part_interval_iterator(IP, DeleteIntervals);
 260 }
 261
 262 inline interval_part_interval_iterator intervals_end(IntervalPartition &IP) {
 263   return interval_part_interval_iterator();
 264 }
 265
 266 } // end namespace llvm
 267
 268 #endif // LLVM_ANALYSIS_INTERVALITERATOR_H