LLVM  14.0.0git
IntervalPartition.cpp
Go to the documentation of this file.
1 //===- IntervalPartition.cpp - Interval Partition module code -------------===//
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 contains the definition of the IntervalPartition class, which
10 // calculates and represent the interval partition of a function.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/Analysis/Interval.h"
17 #include "llvm/InitializePasses.h"
18 #include "llvm/Pass.h"
19 #include <cassert>
20 #include <utility>
21 
22 using namespace llvm;
23 
24 char IntervalPartition::ID = 0;
25 
28 }
29 
31  "Interval Partition Construction", true, true)
32 
33 //===----------------------------------------------------------------------===//
34 // IntervalPartition Implementation
35 //===----------------------------------------------------------------------===//
36 
37 // releaseMemory - Reset state back to before function was analyzed
38 void IntervalPartition::releaseMemory() {
39  for (unsigned i = 0, e = Intervals.size(); i != e; ++i)
40  delete Intervals[i];
42  Intervals.clear();
43  RootInterval = nullptr;
44 }
45 
47  for(unsigned i = 0, e = Intervals.size(); i != e; ++i)
48  Intervals[i]->print(O);
49 }
50 
51 // addIntervalToPartition - Add an interval to the internal list of intervals,
52 // and then add mappings from all of the basic blocks in the interval to the
53 // interval itself (in the IntervalMap).
54 void IntervalPartition::addIntervalToPartition(Interval *I) {
55  Intervals.push_back(I);
56 
57  // Add mappings for all of the basic blocks in I to the IntervalPartition
58  for (Interval::node_iterator It = I->Nodes.begin(), End = I->Nodes.end();
59  It != End; ++It)
60  IntervalMap.insert(std::make_pair(*It, I));
61 }
62 
63 // updatePredecessors - Interval generation only sets the successor fields of
64 // the interval data structures. After interval generation is complete,
65 // run through all of the intervals and propagate successor info as
66 // predecessor info.
67 void IntervalPartition::updatePredecessors(Interval *Int) {
68  BasicBlock *Header = Int->getHeaderNode();
69  for (BasicBlock *Successor : Int->Successors)
70  getBlockInterval(Successor)->Predecessors.push_back(Header);
71 }
72 
73 // IntervalPartition ctor - Build the first level interval partition for the
74 // specified function...
76  // Pass false to intervals_begin because we take ownership of it's memory
78  assert(I != intervals_end(&F) && "No intervals in function!?!?!");
79 
80  addIntervalToPartition(RootInterval = *I);
81 
82  ++I; // After the first one...
83 
84  // Add the rest of the intervals to the partition.
86  addIntervalToPartition(*I);
87 
88  // Now that we know all of the successor information, propagate this to the
89  // predecessors for each block.
90  for (unsigned i = 0, e = Intervals.size(); i != e; ++i)
91  updatePredecessors(Intervals[i]);
92  return false;
93 }
94 
95 // IntervalPartition ctor - Build a reduced interval partition from an
96 // existing interval graph. This takes an additional boolean parameter to
97 // distinguish it from a copy constructor. Always pass in false for now.
99  : FunctionPass(ID) {
100  assert(IP.getRootInterval() && "Cannot operate on empty IntervalPartitions!");
101 
102  // Pass false to intervals_begin because we take ownership of it's memory
104  assert(I != intervals_end(IP) && "No intervals in interval partition!?!?!");
105 
106  addIntervalToPartition(RootInterval = *I);
107 
108  ++I; // After the first one...
109 
110  // Add the rest of the intervals to the partition.
112  addIntervalToPartition(*I);
113 
114  // Now that we know all of the successor information, propagate this to the
115  // predecessors for each block.
116  for (unsigned i = 0, e = Intervals.size(); i != e; ++i)
117  updatePredecessors(Intervals[i]);
118 }
i
i
Definition: README.txt:29
llvm::IntervalMap::clear
void clear()
clear - Remove all entries.
Definition: IntervalMap.h:1284
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::IntervalMap::insert
void insert(KeyT a, KeyT b, ValT y)
insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
Definition: IntervalMap.h:1083
llvm::Function
Definition: Function.h:61
Pass.h
llvm::IntervalPartition::runOnFunction
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: IntervalPartition.cpp:75
INITIALIZE_PASS
INITIALIZE_PASS(IntervalPartition, "intervals", "Interval Partition Construction", true, true) void IntervalPartition
Definition: IntervalPartition.cpp:30
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
IP
Definition: NVPTXLowerArgs.cpp:166
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
IntervalIterator.h
llvm::IntervalPartition::IntervalPartition
IntervalPartition()
Definition: IntervalPartition.cpp:26
llvm::initializeIntervalPartitionPass
void initializeIntervalPartitionPass(PassRegistry &)
llvm::IntervalIterator
Definition: IntervalIterator.h:89
llvm::Interval::node_iterator
std::vector< BasicBlock * >::iterator node_iterator
Definition: Interval.h:45
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:192
llvm::IntervalPartition
Definition: IntervalPartition.h:42
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
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::IntervalPartition::getBlockInterval
Interval * getBlockInterval(BasicBlock *BB)
Definition: IntervalPartition.h:77
llvm::IntervalPartition::print
void print(raw_ostream &O, const Module *=nullptr) const override
print - Print out the internal state of the pass.
Definition: IntervalPartition.cpp:46
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
IntervalPartition.h
llvm::intervals_end
function_interval_iterator intervals_end(Function *)
Definition: IntervalIterator.h:250
llvm::IntervalPartition::ID
static char ID
Definition: IntervalPartition.h:51
llvm::Successor
@ Successor
Definition: SIMachineScheduler.h:35
llvm::intervals_begin
function_interval_iterator intervals_begin(Function *F, bool DeleteInts=true)
Definition: IntervalIterator.h:246
llvm::IntervalMap
Definition: IntervalMap.h:938
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::Interval::Predecessors
std::vector< BasicBlock * > Predecessors
Predecessors - List of BasicBlocks that have this Interval's header block as one of their successors.
Definition: Interval.h:63
InitializePasses.h
Interval.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37