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