LLVM  14.0.0git
IntervalIterator.h
Go to the documentation of this file.
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"
38 #include "llvm/IR/CFG.h"
39 #include "llvm/IR/Function.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.
62  return BB;
63 }
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.
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.
83  // Add all of the nodes in I as new nodes in Int.
84  llvm::append_range(Int->Nodes, I->Nodes);
85 }
86 
87 template<class NodeTy, class OrigContainer_t, class GT = GraphTraits<NodeTy *>,
88  class IGT = GraphTraits<Inverse<NodeTy *>>>
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 
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 
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  llvm::erase_value(Int->Successors, NodeHeader);
231  }
232 
233  // Now that we have discovered that Node is in the interval, perhaps some
234  // of its successors are as well?
235  for (typename GT::ChildIteratorType It = GT::child_begin(Node),
236  End = GT::child_end(Node); It != End; ++It)
237  ProcessNode(Int, getSourceGraphNode(OrigContainer, *It));
238  }
239  }
240 };
241 
245 
247  bool DeleteInts = true) {
248  return function_interval_iterator(F, DeleteInts);
249 }
252 }
253 
255  intervals_begin(IntervalPartition &IP, bool DeleteIntervals = true) {
256  return interval_part_interval_iterator(IP, DeleteIntervals);
257 }
258 
261 }
262 
263 } // end namespace llvm
264 
265 #endif // LLVM_ANALYSIS_INTERVALITERATOR_H
llvm::IntervalIterator::operator*
const Interval * operator*() const
Definition: IntervalIterator.h:134
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::Function
Definition: Function.h:62
llvm::IntervalIterator::operator!=
bool operator!=(const IntervalIterator &x) const
Definition: IntervalIterator.h:132
ErrorHandling.h
llvm::IntervalIterator::operator++
IntervalIterator operator++(int)
Definition: IntervalIterator.h:162
llvm::getSourceGraphNode
BasicBlock * getSourceGraphNode(Function *, BasicBlock *BB)
Definition: IntervalIterator.h:61
llvm::addNodeToInterval
void addNodeToInterval(Interval *Int, BasicBlock *BB)
Definition: IntervalIterator.h:72
tmp
alloca< 16 x float >, align 16 %tmp2=alloca< 16 x float >, align 16 store< 16 x float > %A,< 16 x float > *%tmp %s=bitcast< 16 x float > *%tmp to i8 *%s2=bitcast< 16 x float > *%tmp2 to i8 *call void @llvm.memcpy.i64(i8 *%s, i8 *%s2, i64 64, i32 16) %R=load< 16 x float > *%tmp2 ret< 16 x float > %R } declare void @llvm.memcpy.i64(i8 *nocapture, i8 *nocapture, i64, i32) nounwind which compiles to:_foo:subl $140, %esp movaps %xmm3, 112(%esp) movaps %xmm2, 96(%esp) movaps %xmm1, 80(%esp) movaps %xmm0, 64(%esp) movl 60(%esp), %eax movl %eax, 124(%esp) movl 56(%esp), %eax movl %eax, 120(%esp) movl 52(%esp), %eax< many many more 32-bit copies > movaps(%esp), %xmm0 movaps 16(%esp), %xmm1 movaps 32(%esp), %xmm2 movaps 48(%esp), %xmm3 addl $140, %esp ret On Nehalem, it may even be cheaper to just use movups when unaligned than to fall back to lower-granularity chunks. Implement processor-specific optimizations for parity with GCC on these processors. GCC does two optimizations:1. ix86_pad_returns inserts a noop before ret instructions if immediately preceded by a conditional branch or is the target of a jump. 2. ix86_avoid_jump_misspredicts inserts noops in cases where a 16-byte block of code contains more than 3 branches. The first one is done for all AMDs, Core2, and "Generic" The second one is done for:Atom, Pentium Pro, all AMDs, Pentium 4, Nocona, Core 2, and "Generic" Testcase:int x(int a) { return(a &0xf0)> >4 tmp
Definition: README.txt:1347
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::interval_part_interval_iterator
IntervalIterator< Interval, IntervalPartition > interval_part_interval_iterator
Definition: IntervalIterator.h:244
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
GraphTraits.h
llvm::function_interval_iterator
IntervalIterator< BasicBlock, Function > function_interval_iterator
Definition: IntervalIterator.h:242
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
IP
Definition: NVPTXLowerArgs.cpp:166
llvm::erase_value
void erase_value(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:1789
llvm::IntervalIterator
Definition: IntervalIterator.h:89
CFG.h
llvm::IntervalPartition
Definition: IntervalPartition.h:42
llvm::tgtok::Int
@ Int
Definition: TGLexer.h:51
llvm::Interval
Interval Class - An Interval is a set of nodes defined such that every node in the interval has all o...
Definition: Interval.h:36
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::succ_begin
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1658
llvm::IntervalIterator::operator->
const Interval * operator->() const
Definition: IntervalIterator.h:136
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::IntervalIterator::IntervalIterator
IntervalIterator(IntervalPartition &IP, bool OwnMemory)
Definition: IntervalIterator.h:114
IntervalPartition.h
llvm::IntervalIterator::operator*
Interval * operator*()
Definition: IntervalIterator.h:135
llvm::IntervalIterator::IntervalIterator
IntervalIterator()=default
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1797
llvm::IntervalIterator::operator->
Interval * operator->()
Definition: IntervalIterator.h:137
Node
Definition: ItaniumDemangle.h:235
llvm::intervals_end
function_interval_iterator intervals_end(Function *)
Definition: IntervalIterator.h:250
llvm::IntervalIterator::operator++
IntervalIterator & operator++()
Definition: IntervalIterator.h:139
std
Definition: BitVector.h:838
llvm::IntervalIterator::operator==
bool operator==(const IntervalIterator &x) const
Definition: IntervalIterator.h:129
llvm::intervals_begin
function_interval_iterator intervals_begin(Function *F, bool DeleteInts=true)
Definition: IntervalIterator.h:246
llvm::Interval::succ_iterator
std::vector< BasicBlock * >::iterator succ_iterator
Definition: Interval.h:43
Function.h
x
TODO unsigned x
Definition: README.txt:10
llvm::getNodeHeader
BasicBlock * getNodeHeader(BasicBlock *BB)
Definition: IntervalIterator.h:55
llvm::IntervalIterator::IntervalIterator
IntervalIterator(Function *M, bool OwnMemory)
Definition: IntervalIterator.h:101
CmpMode::Int
@ Int
llvm::IntervalIterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: IntervalIterator.h:97
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::IntervalIterator::IntervalIterator
IntervalIterator(IntervalIterator &&x)
Definition: IntervalIterator.h:108
Interval
std::pair< uint64_t, uint64_t > Interval
Definition: MappedBlockStream.cpp:38
llvm::IntervalIterator::~IntervalIterator
~IntervalIterator()
Definition: IntervalIterator.h:121
Interval.h