1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===- IntervalPartition.h - Interval partition Calculation -----*- C++ -*-===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file contains the declaration of the IntervalPartition class, which 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// calculates and represents the interval partition of a function, or a 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// preexisting interval partition. 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// In this way, the interval partition may be used to reduce a flow graph down 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// to its degenerate single node interval partition (unless it is irreducible). 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// TODO: The IntervalPartition class should take a bool parameter that tells 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// whether it should add the "tails" of an interval to an interval itself or if 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// they should be represented as distinct intervals. 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef LLVM_INTERVAL_PARTITION_H 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define LLVM_INTERVAL_PARTITION_H 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Analysis/Interval.h" 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Pass.h" 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <map> 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace llvm { 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// IntervalPartition - This class builds and holds an "interval partition" for 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// a function. This partition divides the control flow graph into a set of 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// maximal intervals, as defined with the properties above. Intuitively, a 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// BasicBlock is a (possibly nonexistent) loop with a "tail" of non looping 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// nodes following it. 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass IntervalPartition : public FunctionPass { 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef std::map<BasicBlock*, Interval*> IntervalMapTy; 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman IntervalMapTy IntervalMap; 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef std::vector<Interval*> IntervalListTy; 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Interval *RootInterval; 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<Interval*> Intervals; 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static char ID; // Pass identification, replacement for typeid 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 5119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntervalPartition() : FunctionPass(ID), RootInterval(0) { 5219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman initializeIntervalPartitionPass(*PassRegistry::getPassRegistry()); 5319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // run - Calculate the interval partition for this function 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual bool runOnFunction(Function &F); 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // IntervalPartition ctor - Build a reduced interval partition from an 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // existing interval graph. This takes an additional boolean parameter to 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // distinguish it from a copy constructor. Always pass in false for now. 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman IntervalPartition(IntervalPartition &I, bool); 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // print - Show contents in human readable format... 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void print(raw_ostream &O, const Module* = 0) const; 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // getRootInterval() - Return the root interval that contains the starting 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // block of the function. 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline Interval *getRootInterval() { return RootInterval; } 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // isDegeneratePartition() - Returns true if the interval partition contains 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // a single interval, and thus cannot be simplified anymore. 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isDegeneratePartition() { return Intervals.size() == 1; } 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // TODO: isIrreducible - look for triangle graph. 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // getBlockInterval - Return the interval that a basic block exists in. 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline Interval *getBlockInterval(BasicBlock *BB) { 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman IntervalMapTy::iterator I = IntervalMap.find(BB); 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return I != IntervalMap.end() ? I->second : 0; 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // getAnalysisUsage - Implement the Pass API 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.setPreservesAll(); 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Interface to Intervals vector... 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const std::vector<Interval*> &getIntervals() const { return Intervals; } 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // releaseMemory - Reset state back to before function was analyzed 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void releaseMemory(); 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanprivate: 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // addIntervalToPartition - Add an interval to the internal list of intervals, 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // and then add mappings from all of the basic blocks in the interval to the 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // interval itself (in the IntervalMap). 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void addIntervalToPartition(Interval *I); 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // updatePredecessors - Interval generation only sets the successor fields of 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the interval data structures. After interval generation is complete, 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // run through all of the intervals and propagate successor info as 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // predecessor info. 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void updatePredecessors(Interval *Int); 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} // End llvm namespace 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 112