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//
42class 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
50public:
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
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
109

source code of llvm/include/llvm/Analysis/IntervalPartition.h