]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===- IntervalPartition.h - Interval partition Calculation -----*- C++ -*-===// |
2 | // | |
3 | // The LLVM Compiler Infrastructure | |
4 | // | |
5 | // This file is distributed under the University of Illinois Open Source | |
6 | // License. See LICENSE.TXT for details. | |
7 | // | |
8 | //===----------------------------------------------------------------------===// | |
9 | // | |
10 | // This file contains the declaration of the IntervalPartition class, which | |
11 | // calculates and represents the interval partition of a function, or a | |
12 | // preexisting interval partition. | |
13 | // | |
14 | // In this way, the interval partition may be used to reduce a flow graph down | |
15 | // to its degenerate single node interval partition (unless it is irreducible). | |
16 | // | |
17 | // TODO: The IntervalPartition class should take a bool parameter that tells | |
18 | // whether it should add the "tails" of an interval to an interval itself or if | |
19 | // they should be represented as distinct intervals. | |
20 | // | |
21 | //===----------------------------------------------------------------------===// | |
22 | ||
970d7e83 LB |
23 | #ifndef LLVM_ANALYSIS_INTERVALPARTITION_H |
24 | #define LLVM_ANALYSIS_INTERVALPARTITION_H | |
223e47cc LB |
25 | |
26 | #include "llvm/Analysis/Interval.h" | |
27 | #include "llvm/Pass.h" | |
28 | #include <map> | |
29 | ||
30 | namespace llvm { | |
31 | ||
32 | //===----------------------------------------------------------------------===// | |
33 | // | |
34 | // IntervalPartition - This class builds and holds an "interval partition" for | |
35 | // a function. This partition divides the control flow graph into a set of | |
36 | // maximal intervals, as defined with the properties above. Intuitively, an | |
1a4d82fc | 37 | // interval is a (possibly nonexistent) loop with a "tail" of non-looping |
223e47cc LB |
38 | // nodes following it. |
39 | // | |
40 | class IntervalPartition : public FunctionPass { | |
41 | typedef std::map<BasicBlock*, Interval*> IntervalMapTy; | |
42 | IntervalMapTy IntervalMap; | |
43 | ||
44 | typedef std::vector<Interval*> IntervalListTy; | |
45 | Interval *RootInterval; | |
46 | std::vector<Interval*> Intervals; | |
47 | ||
48 | public: | |
49 | static char ID; // Pass identification, replacement for typeid | |
50 | ||
1a4d82fc | 51 | IntervalPartition() : FunctionPass(ID), RootInterval(nullptr) { |
223e47cc LB |
52 | initializeIntervalPartitionPass(*PassRegistry::getPassRegistry()); |
53 | } | |
54 | ||
55 | // run - Calculate the interval partition for this function | |
1a4d82fc | 56 | bool runOnFunction(Function &F) override; |
223e47cc LB |
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. | |
61 | // | |
62 | IntervalPartition(IntervalPartition &I, bool); | |
63 | ||
64 | // print - Show contents in human readable format... | |
1a4d82fc | 65 | void print(raw_ostream &O, const Module* = nullptr) const override; |
223e47cc LB |
66 | |
67 | // getRootInterval() - Return the root interval that contains the starting | |
68 | // block of the function. | |
69 | inline Interval *getRootInterval() { return RootInterval; } | |
70 | ||
71 | // isDegeneratePartition() - Returns true if the interval partition contains | |
72 | // a single interval, and thus cannot be simplified anymore. | |
73 | bool isDegeneratePartition() { return Intervals.size() == 1; } | |
74 | ||
75 | // TODO: isIrreducible - look for triangle graph. | |
76 | ||
77 | // getBlockInterval - Return the interval that a basic block exists in. | |
78 | inline Interval *getBlockInterval(BasicBlock *BB) { | |
79 | IntervalMapTy::iterator I = IntervalMap.find(BB); | |
1a4d82fc | 80 | return I != IntervalMap.end() ? I->second : nullptr; |
223e47cc LB |
81 | } |
82 | ||
83 | // getAnalysisUsage - Implement the Pass API | |
1a4d82fc | 84 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
223e47cc LB |
85 | AU.setPreservesAll(); |
86 | } | |
87 | ||
88 | // Interface to Intervals vector... | |
89 | const std::vector<Interval*> &getIntervals() const { return Intervals; } | |
90 | ||
91 | // releaseMemory - Reset state back to before function was analyzed | |
1a4d82fc | 92 | void releaseMemory() override; |
223e47cc LB |
93 | |
94 | private: | |
95 | // addIntervalToPartition - Add an interval to the internal list of intervals, | |
96 | // and then add mappings from all of the basic blocks in the interval to the | |
97 | // interval itself (in the IntervalMap). | |
98 | // | |
99 | void addIntervalToPartition(Interval *I); | |
100 | ||
101 | // updatePredecessors - Interval generation only sets the successor fields of | |
102 | // the interval data structures. After interval generation is complete, | |
103 | // run through all of the intervals and propagate successor info as | |
104 | // predecessor info. | |
105 | // | |
106 | void updatePredecessors(Interval *Int); | |
107 | }; | |
108 | ||
109 | } // End llvm namespace | |
110 | ||
111 | #endif |