LLVM  14.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 
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 //
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 
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 
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
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::Function
Definition: Function.h:62
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
llvm::IntervalPartition::getRootInterval
Interval * getRootInterval()
Definition: IntervalPartition.h:68
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::IntervalPartition::isDegeneratePartition
bool isDegeneratePartition()
Definition: IntervalPartition.h:72
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::IntervalPartition::IntervalPartition
IntervalPartition()
Definition: IntervalPartition.cpp:26
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:197
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
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
llvm::IntervalMap::find
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:1126
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::IntervalMap::end
const_iterator end() const
Definition: IntervalMap.h:1112
llvm::IntervalPartition::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
llvm::IntervalPartition::ID
static char ID
Definition: IntervalPartition.h:51
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::IntervalPartition::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: IntervalPartition.h:83
llvm::IntervalMap
Definition: IntervalMap.h:938
llvm::IntervalPartition::getIntervals
const std::vector< Interval * > & getIntervals() const
Definition: IntervalPartition.h:88
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
Interval
std::pair< uint64_t, uint64_t > Interval
Definition: MappedBlockStream.cpp:38