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 23 #ifndef LLVM_ANALYSIS_INTERVALPARTITION_H 24 #define LLVM_ANALYSIS_INTERVALPARTITION_H 25 26 #include "llvm/Pass.h" 27 #include <map> 28 #include <vector> 29 30 namespace llvm { 31 32 class BasicBlock; 33 class Interval; 34 35 //===----------------------------------------------------------------------===// 36 // 37 // IntervalPartition - This class builds and holds an "interval partition" for 38 // a function. This partition divides the control flow graph into a set of 39 // maximal intervals, as defined with the properties above. Intuitively, an 40 // interval is a (possibly nonexistent) loop with a "tail" of non-looping 41 // nodes following it. 42 // 43 class IntervalPartition : public FunctionPass { 44 using IntervalMapTy = std::map<BasicBlock *, Interval *>; 45 IntervalMapTy IntervalMap; 46 47 using IntervalListTy = std::vector<Interval *>; 48 Interval *RootInterval = nullptr; 49 std::vector<Interval *> Intervals; 50 51 public: 52 static char ID; // Pass identification, replacement for typeid 53 54 IntervalPartition() : FunctionPass(ID) { 55 initializeIntervalPartitionPass(*PassRegistry::getPassRegistry()); 56 } 57 58 // run - Calculate the interval partition for this function 59 bool runOnFunction(Function &F) override; 60 61 // IntervalPartition ctor - Build a reduced interval partition from an 62 // existing interval graph. This takes an additional boolean parameter to 63 // distinguish it from a copy constructor. Always pass in false for now. 64 IntervalPartition(IntervalPartition &I, bool); 65 66 // print - Show contents in human readable format... 67 void print(raw_ostream &O, const Module* = nullptr) const override; 68 69 // getRootInterval() - Return the root interval that contains the starting 70 // block of the function. 71 inline Interval *getRootInterval() { return RootInterval; } 72 73 // isDegeneratePartition() - Returns true if the interval partition contains 74 // a single interval, and thus cannot be simplified anymore. 75 bool isDegeneratePartition() { return Intervals.size() == 1; } 76 77 // TODO: isIrreducible - look for triangle graph. 78 79 // getBlockInterval - Return the interval that a basic block exists in. 80 inline Interval *getBlockInterval(BasicBlock *BB) { 81 IntervalMapTy::iterator I = IntervalMap.find(BB); 82 return I != IntervalMap.end() ? I->second : nullptr; 83 } 84 85 // getAnalysisUsage - Implement the Pass API 86 void getAnalysisUsage(AnalysisUsage &AU) const override { 87 AU.setPreservesAll(); 88 } 89 90 // Interface to Intervals vector... 91 const std::vector<Interval*> &getIntervals() const { return Intervals; } 92 93 // releaseMemory - Reset state back to before function was analyzed 94 void releaseMemory() override; 95 96 private: 97 // addIntervalToPartition - Add an interval to the internal list of intervals, 98 // and then add mappings from all of the basic blocks in the interval to the 99 // interval itself (in the IntervalMap). 100 void addIntervalToPartition(Interval *I); 101 102 // updatePredecessors - Interval generation only sets the successor fields of 103 // the interval data structures. After interval generation is complete, 104 // run through all of the intervals and propagate successor info as 105 // predecessor info. 106 void updatePredecessors(Interval *Int); 107 }; 108 109 } // end namespace llvm 110 111 #endif // LLVM_ANALYSIS_INTERVALPARTITION_H 112
