LLVM 17.0.0git
IntervalPartition.h
Go to the documentation of this file.
1//===- IntervalPartition.h - Interval partition Calculation -----*- 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 contains the declaration of the IntervalPartition class, which
10// calculates and represents the interval partition of a function, or a
11// preexisting interval partition.
12//
13// In this way, the interval partition may be used to reduce a flow graph down
14// to its degenerate single node interval partition (unless it is irreducible).
15//
16// TODO: The IntervalPartition class should take a bool parameter that tells
17// whether it should add the "tails" of an interval to an interval itself or if
18// they should be represented as distinct intervals.
19//
20//===----------------------------------------------------------------------===//
21
22#ifndef LLVM_ANALYSIS_INTERVALPARTITION_H
23#define LLVM_ANALYSIS_INTERVALPARTITION_H
24
25#include "llvm/Pass.h"
26#include <map>
27#include <vector>
28
29namespace llvm {
30
31class BasicBlock;
32class Interval;
33
34//===----------------------------------------------------------------------===//
35//
36// IntervalPartition - This class builds and holds an "interval partition" for
37// a function. This partition divides the control flow graph into a set of
38// maximal intervals, as defined with the properties above. Intuitively, an
39// interval is a (possibly nonexistent) loop with a "tail" of non-looping
40// nodes following it.
41//
43 using IntervalMapTy = std::map<BasicBlock *, Interval *>;
44 IntervalMapTy IntervalMap;
45
46 using IntervalListTy = std::vector<Interval *>;
47 Interval *RootInterval = nullptr;
48 std::vector<Interval *> Intervals;
49
50public:
51 static char ID; // Pass identification, replacement for typeid
52
54
55 // run - Calculate the interval partition for this function
56 bool runOnFunction(Function &F) override;
57
58 // IntervalPartition ctor - Build a reduced interval partition from an
59 // existing interval graph. This takes an additional boolean parameter to
60 // distinguish it from a copy constructor. Always pass in false for now.
62
63 // print - Show contents in human readable format...
64 void print(raw_ostream &O, const Module* = nullptr) const override;
65
66 // getRootInterval() - Return the root interval that contains the starting
67 // block of the function.
68 inline Interval *getRootInterval() { return RootInterval; }
69
70 // isDegeneratePartition() - Returns true if the interval partition contains
71 // a single interval, and thus cannot be simplified anymore.
72 bool isDegeneratePartition() { return Intervals.size() == 1; }
73
74 // TODO: isIrreducible - look for triangle graph.
75
76 // getBlockInterval - Return the interval that a basic block exists in.
78 IntervalMapTy::iterator I = IntervalMap.find(BB);
79 return I != IntervalMap.end() ? I->second : nullptr;
80 }
81
82 // getAnalysisUsage - Implement the Pass API
83 void getAnalysisUsage(AnalysisUsage &AU) const override {
84 AU.setPreservesAll();
85 }
86
87 // Interface to Intervals vector...
88 const std::vector<Interval*> &getIntervals() const { return Intervals; }
89
90 // releaseMemory - Reset state back to before function was analyzed
91 void releaseMemory() override;
92
93private:
94 // addIntervalToPartition - Add an interval to the internal list of intervals,
95 // and then add mappings from all of the basic blocks in the interval to the
96 // interval itself (in the IntervalMap).
97 void addIntervalToPartition(Interval *I);
98
99 // updatePredecessors - Interval generation only sets the successor fields of
100 // the interval data structures. After interval generation is complete,
101 // run through all of the intervals and propagate successor info as
102 // predecessor info.
103 void updatePredecessors(Interval *Int);
104};
105
106} // end namespace llvm
107
108#endif // LLVM_ANALYSIS_INTERVALPARTITION_H
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
std::pair< uint64_t, uint64_t > Interval
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
const_iterator find(KeyT x) const
find - Return an iterator pointing to the first interval ending at or after x, or end().
Definition: IntervalMap.h:1172
const_iterator end() const
Definition: IntervalMap.h:1158
void print(raw_ostream &O, const Module *=nullptr) const override
print - Print out the internal state of the pass.
const std::vector< Interval * > & getIntervals() const
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Interval * getBlockInterval(BasicBlock *BB)
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Interval Class - An Interval is a set of nodes defined such that every node in the interval has all o...
Definition: Interval.h:36
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18