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