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(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