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 | |
29 | namespace llvm { |
30 | |
31 | class BasicBlock; |
32 | class 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 | // |
42 | class IntervalPartition : public FunctionPass { |
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 | |
50 | public: |
51 | static char ID; // Pass identification, replacement for typeid |
52 | |
53 | IntervalPartition(); |
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. |
61 | IntervalPartition(IntervalPartition &I, bool); |
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. |
77 | inline Interval *getBlockInterval(BasicBlock *BB) { |
78 | IntervalMapTy::iterator I = IntervalMap.find(x: 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 | |
93 | private: |
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 |
109 | |