LLVM  15.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 <algorithm>
40 #include <cassert>
41 #include <iterator>
42 #include <set>
43 #include <utility>
44 #include <vector>
45 
46 namespace llvm {
47 
48 class BasicBlock;
49 class Function;
50 
51 // getNodeHeader - Given a source graph node and the source graph, return the
52 // BasicBlock that is the header node. This is the opposite of
53 // getSourceGraphNode.
54 inline BasicBlock *getNodeHeader(BasicBlock *BB) { return BB; }
55 inline BasicBlock *getNodeHeader(Interval *I) { return I->getHeaderNode(); }
56 
57 // getSourceGraphNode - Given a BasicBlock and the source graph, return the
58 // source graph node that corresponds to the BasicBlock. This is the opposite
59 // of getNodeHeader.
61  return BB;
62 }
64  return IP->getBlockInterval(BB);
65 }
66 
67 // addNodeToInterval - This method exists to assist the generic ProcessNode
68 // with the task of adding a node to the new interval, depending on the
69 // type of the source node. In the case of a CFG source graph (BasicBlock
70 // case), the BasicBlock itself is added to the interval.
72  Int->Nodes.push_back(BB);
73 }
74 
75 // addNodeToInterval - This method exists to assist the generic ProcessNode
76 // with the task of adding a node to the new interval, depending on the
77 // type of the source node. In the case of a CFG source graph (BasicBlock
78 // case), the BasicBlock itself is added to the interval. In the case of
79 // an IntervalPartition source graph (Interval case), all of the member
80 // BasicBlocks are added to the interval.
82  // Add all of the nodes in I as new nodes in Int.
83  llvm::append_range(Int->Nodes, I->Nodes);
84 }
85 
86 template<class NodeTy, class OrigContainer_t, class GT = GraphTraits<NodeTy *>,
87  class IGT = GraphTraits<Inverse<NodeTy *>>>
89  std::vector<std::pair<Interval *, typename Interval::succ_iterator>> IntStack;
90  std::set<BasicBlock *> Visited;
91  OrigContainer_t *OrigContainer;
92  bool IOwnMem; // If True, delete intervals when done with them
93  // See file header for conditions of use
94 
95 public:
96  using iterator_category = std::forward_iterator_tag;
97 
98  IntervalIterator() = default; // End iterator, empty stack
99 
100  IntervalIterator(Function *M, bool OwnMemory) : IOwnMem(OwnMemory) {
101  OrigContainer = M;
102  if (!ProcessInterval(&M->front())) {
103  llvm_unreachable("ProcessInterval should never fail for first interval!");
104  }
105  }
106 
108  : IntStack(std::move(x.IntStack)), Visited(std::move(x.Visited)),
109  OrigContainer(x.OrigContainer), IOwnMem(x.IOwnMem) {
110  x.IOwnMem = false;
111  }
112 
113  IntervalIterator(IntervalPartition &IP, bool OwnMemory) : IOwnMem(OwnMemory) {
114  OrigContainer = &IP;
115  if (!ProcessInterval(IP.getRootInterval())) {
116  llvm_unreachable("ProcessInterval should never fail for first interval!");
117  }
118  }
119 
121  if (IOwnMem)
122  while (!IntStack.empty()) {
123  delete operator*();
124  IntStack.pop_back();
125  }
126  }
127 
128  bool operator==(const IntervalIterator &x) const {
129  return IntStack == x.IntStack;
130  }
131  bool operator!=(const IntervalIterator &x) const { return !(*this == x); }
132 
133  const Interval *operator*() const { return IntStack.back().first; }
134  Interval *operator*() { return IntStack.back().first; }
135  const Interval *operator->() const { return operator*(); }
136  Interval *operator->() { return operator*(); }
137 
138  IntervalIterator &operator++() { // Preincrement
139  assert(!IntStack.empty() && "Attempting to use interval iterator at end!");
140  do {
141  // All of the intervals on the stack have been visited. Try visiting
142  // their successors now.
143  Interval::succ_iterator &SuccIt = IntStack.back().second,
144  EndIt = succ_end(IntStack.back().first);
145  while (SuccIt != EndIt) { // Loop over all interval succs
146  bool Done = ProcessInterval(getSourceGraphNode(OrigContainer, *SuccIt));
147  ++SuccIt; // Increment iterator
148  if (Done) return *this; // Found a new interval! Use it!
149  }
150 
151  // Free interval memory... if necessary
152  if (IOwnMem) delete IntStack.back().first;
153 
154  // We ran out of successors for this interval... pop off the stack
155  IntStack.pop_back();
156  } while (!IntStack.empty());
157 
158  return *this;
159  }
160 
161  IntervalIterator operator++(int) { // Postincrement
162  IntervalIterator tmp = *this;
163  ++*this;
164  return tmp;
165  }
166 
167 private:
168  // ProcessInterval - This method is used during the construction of the
169  // interval graph. It walks through the source graph, recursively creating
170  // an interval per invocation until the entire graph is covered. This uses
171  // the ProcessNode method to add all of the nodes to the interval.
172  //
173  // This method is templated because it may operate on two different source
174  // graphs: a basic block graph, or a preexisting interval graph.
175  bool ProcessInterval(NodeTy *Node) {
176  BasicBlock *Header = getNodeHeader(Node);
177  if (!Visited.insert(Header).second)
178  return false;
179 
180  Interval *Int = new Interval(Header);
181 
182  // Check all of our successors to see if they are in the interval...
183  for (typename GT::ChildIteratorType I = GT::child_begin(Node),
184  E = GT::child_end(Node); I != E; ++I)
185  ProcessNode(Int, getSourceGraphNode(OrigContainer, *I));
186 
187  IntStack.push_back(std::make_pair(Int, succ_begin(Int)));
188  return true;
189  }
190 
191  // ProcessNode - This method is called by ProcessInterval to add nodes to the
192  // interval being constructed, and it is also called recursively as it walks
193  // the source graph. A node is added to the current interval only if all of
194  // its predecessors are already in the graph. This also takes care of keeping
195  // the successor set of an interval up to date.
196  //
197  // This method is templated because it may operate on two different source
198  // graphs: a basic block graph, or a preexisting interval graph.
199  void ProcessNode(Interval *Int, NodeTy *Node) {
200  assert(Int && "Null interval == bad!");
201  assert(Node && "Null Node == bad!");
202 
203  BasicBlock *NodeHeader = getNodeHeader(Node);
204 
205  if (Visited.count(NodeHeader)) { // Node already been visited?
206  if (Int->contains(NodeHeader)) { // Already in this interval...
207  return;
208  } else { // In other interval, add as successor
209  if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
210  Int->Successors.push_back(NodeHeader);
211  }
212  } else { // Otherwise, not in interval yet
213  for (typename IGT::ChildIteratorType I = IGT::child_begin(Node),
214  E = IGT::child_end(Node); I != E; ++I) {
215  if (!Int->contains(*I)) { // If pred not in interval, we can't be
216  if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
217  Int->Successors.push_back(NodeHeader);
218  return; // See you later
219  }
220  }
221 
222  // If we get here, then all of the predecessors of BB are in the interval
223  // already. In this case, we must add BB to the interval!
224  addNodeToInterval(Int, Node);
225  Visited.insert(NodeHeader); // The node has now been visited!
226 
227  if (Int->isSuccessor(NodeHeader)) {
228  // If we were in the successor list from before... remove from succ list
229  llvm::erase_value(Int->Successors, NodeHeader);
230  }
231 
232  // Now that we have discovered that Node is in the interval, perhaps some
233  // of its successors are as well?
234  for (typename GT::ChildIteratorType It = GT::child_begin(Node),
235  End = GT::child_end(Node); It != End; ++It)
236  ProcessNode(Int, getSourceGraphNode(OrigContainer, *It));
237  }
238  }
239 };
240 
244 
246  bool DeleteInts = true) {
247  return function_interval_iterator(F, DeleteInts);
248 }
251 }
252 
254  intervals_begin(IntervalPartition &IP, bool DeleteIntervals = true) {
255  return interval_part_interval_iterator(IP, DeleteIntervals);
256 }
257 
260 }
261 
262 } // end namespace llvm
263 
264 #endif // LLVM_ANALYSIS_INTERVALITERATOR_H
llvm::IntervalIterator::operator*
const Interval * operator*() const
Definition: IntervalIterator.h:133
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:60
llvm::IntervalIterator::operator!=
bool operator!=(const IntervalIterator &x) const
Definition: IntervalIterator.h:131
llvm::IntervalIterator::operator++
IntervalIterator operator++(int)
Definition: IntervalIterator.h:161
llvm::getSourceGraphNode
BasicBlock * getSourceGraphNode(Function *, BasicBlock *BB)
Definition: IntervalIterator.h:60
llvm::addNodeToInterval
void addNodeToInterval(Interval *Int, BasicBlock *BB)
Definition: IntervalIterator.h:71
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:55
llvm::interval_part_interval_iterator
IntervalIterator< Interval, IntervalPartition > interval_part_interval_iterator
Definition: IntervalIterator.h:243
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
GraphTraits.h
llvm::function_interval_iterator
IntervalIterator< BasicBlock, Function > function_interval_iterator
Definition: IntervalIterator.h:241
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
IP
Definition: NVPTXLowerArgs.cpp:167
llvm::erase_value
void erase_value(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:1815
llvm::IntervalIterator
Definition: IntervalIterator.h:88
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:58
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:1675
llvm::IntervalIterator::operator->
const Interval * operator->() const
Definition: IntervalIterator.h:135
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::IntervalIterator::IntervalIterator
IntervalIterator(IntervalPartition &IP, bool OwnMemory)
Definition: IntervalIterator.h:113
IntervalPartition.h
llvm::IntervalIterator::operator*
Interval * operator*()
Definition: IntervalIterator.h:134
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:143
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1823
llvm::IntervalIterator::operator->
Interval * operator->()
Definition: IntervalIterator.h:136
Node
Definition: ItaniumDemangle.h:155
llvm::intervals_end
function_interval_iterator intervals_end(Function *)
Definition: IntervalIterator.h:249
llvm::IntervalIterator::operator++
IntervalIterator & operator++()
Definition: IntervalIterator.h:138
std
Definition: BitVector.h:851
llvm::IntervalIterator::operator==
bool operator==(const IntervalIterator &x) const
Definition: IntervalIterator.h:128
llvm::intervals_begin
function_interval_iterator intervals_begin(Function *F, bool DeleteInts=true)
Definition: IntervalIterator.h:245
llvm::Interval::succ_iterator
std::vector< BasicBlock * >::iterator succ_iterator
Definition: Interval.h:43
x
TODO unsigned x
Definition: README.txt:10
llvm::getNodeHeader
BasicBlock * getNodeHeader(BasicBlock *BB)
Definition: IntervalIterator.h:54
llvm::IntervalIterator::IntervalIterator
IntervalIterator(Function *M, bool OwnMemory)
Definition: IntervalIterator.h:100
CmpMode::Int
@ Int
llvm::IntervalIterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: IntervalIterator.h:96
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:107
Interval
std::pair< uint64_t, uint64_t > Interval
Definition: MappedBlockStream.cpp:37
llvm::IntervalIterator::~IntervalIterator
~IntervalIterator()
Definition: IntervalIterator.h:120
Interval.h
llvm::codeview::PublicSymFlags::Function
@ Function