1193323Sed//===- IntervalPartition.h - Interval partition Calculation -----*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file contains the declaration of the IntervalPartition class, which 11193323Sed// calculates and represents the interval partition of a function, or a 12193323Sed// preexisting interval partition. 13193323Sed// 14193323Sed// In this way, the interval partition may be used to reduce a flow graph down 15193323Sed// to its degenerate single node interval partition (unless it is irreducible). 16193323Sed// 17193323Sed// TODO: The IntervalPartition class should take a bool parameter that tells 18193323Sed// whether it should add the "tails" of an interval to an interval itself or if 19193323Sed// they should be represented as distinct intervals. 20193323Sed// 21193323Sed//===----------------------------------------------------------------------===// 22193323Sed 23249423Sdim#ifndef LLVM_ANALYSIS_INTERVALPARTITION_H 24249423Sdim#define LLVM_ANALYSIS_INTERVALPARTITION_H 25193323Sed 26193323Sed#include "llvm/Analysis/Interval.h" 27193323Sed#include "llvm/Pass.h" 28193323Sed#include <map> 29193323Sed 30193323Sednamespace llvm { 31193323Sed 32193323Sed//===----------------------------------------------------------------------===// 33193323Sed// 34193323Sed// IntervalPartition - This class builds and holds an "interval partition" for 35193323Sed// a function. This partition divides the control flow graph into a set of 36243830Sdim// maximal intervals, as defined with the properties above. Intuitively, an 37243830Sdim// interval is a (possibly nonexistent) loop with a "tail" of non looping 38193323Sed// nodes following it. 39193323Sed// 40193323Sedclass IntervalPartition : public FunctionPass { 41193323Sed typedef std::map<BasicBlock*, Interval*> IntervalMapTy; 42193323Sed IntervalMapTy IntervalMap; 43193323Sed 44193323Sed typedef std::vector<Interval*> IntervalListTy; 45193323Sed Interval *RootInterval; 46193323Sed std::vector<Interval*> Intervals; 47193323Sed 48193323Sedpublic: 49193323Sed static char ID; // Pass identification, replacement for typeid 50193323Sed 51218893Sdim IntervalPartition() : FunctionPass(ID), RootInterval(0) { 52218893Sdim initializeIntervalPartitionPass(*PassRegistry::getPassRegistry()); 53218893Sdim } 54193323Sed 55193323Sed // run - Calculate the interval partition for this function 56193323Sed virtual bool runOnFunction(Function &F); 57193323Sed 58193323Sed // IntervalPartition ctor - Build a reduced interval partition from an 59193323Sed // existing interval graph. This takes an additional boolean parameter to 60193323Sed // distinguish it from a copy constructor. Always pass in false for now. 61193323Sed // 62193323Sed IntervalPartition(IntervalPartition &I, bool); 63193323Sed 64193323Sed // print - Show contents in human readable format... 65198090Srdivacky virtual void print(raw_ostream &O, const Module* = 0) const; 66193323Sed 67193323Sed // getRootInterval() - Return the root interval that contains the starting 68193323Sed // block of the function. 69193323Sed inline Interval *getRootInterval() { return RootInterval; } 70193323Sed 71193323Sed // isDegeneratePartition() - Returns true if the interval partition contains 72193323Sed // a single interval, and thus cannot be simplified anymore. 73193323Sed bool isDegeneratePartition() { return Intervals.size() == 1; } 74193323Sed 75193323Sed // TODO: isIrreducible - look for triangle graph. 76193323Sed 77193323Sed // getBlockInterval - Return the interval that a basic block exists in. 78193323Sed inline Interval *getBlockInterval(BasicBlock *BB) { 79193323Sed IntervalMapTy::iterator I = IntervalMap.find(BB); 80193323Sed return I != IntervalMap.end() ? I->second : 0; 81193323Sed } 82193323Sed 83193323Sed // getAnalysisUsage - Implement the Pass API 84193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const { 85193323Sed AU.setPreservesAll(); 86193323Sed } 87193323Sed 88193323Sed // Interface to Intervals vector... 89193323Sed const std::vector<Interval*> &getIntervals() const { return Intervals; } 90193323Sed 91193323Sed // releaseMemory - Reset state back to before function was analyzed 92193323Sed void releaseMemory(); 93193323Sed 94193323Sedprivate: 95193323Sed // addIntervalToPartition - Add an interval to the internal list of intervals, 96193323Sed // and then add mappings from all of the basic blocks in the interval to the 97193323Sed // interval itself (in the IntervalMap). 98193323Sed // 99193323Sed void addIntervalToPartition(Interval *I); 100193323Sed 101193323Sed // updatePredecessors - Interval generation only sets the successor fields of 102193323Sed // the interval data structures. After interval generation is complete, 103193323Sed // run through all of the intervals and propagate successor info as 104193323Sed // predecessor info. 105193323Sed // 106193323Sed void updatePredecessors(Interval *Int); 107193323Sed}; 108193323Sed 109193323Sed} // End llvm namespace 110193323Sed 111193323Sed#endif 112