IntervalPartition.h revision 97f51a3024a72ef8500e95b90e6361e6783160fd
1a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner//===- IntervalPartition.h - Interval partition Calculation ------*- C++ -*--=// 2a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// 38fc2f2072de83665ae20e06929e28317f449bcdfChris Lattner// This file contains the declaration of the IntervalPartition class, which 4f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner// calculates and represents the interval partition of a function, or a 5a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// preexisting interval partition. 6a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// 7a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// In this way, the interval partition may be used to reduce a flow graph down 8a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// to its degenerate single node interval partition (unless it is irreducible). 9a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// 10a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// TODO: The IntervalPartition class should take a bool parameter that tells 11a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// whether it should add the "tails" of an interval to an interval itself or if 12a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// they should be represented as distinct intervals. 13a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// 14a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner//===----------------------------------------------------------------------===// 15a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 16a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner#ifndef LLVM_INTERVAL_PARTITION_H 17a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner#define LLVM_INTERVAL_PARTITION_H 18a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 19a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner#include "llvm/Analysis/Interval.h" 20facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner#include "llvm/Pass.h" 21a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 22a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner//===----------------------------------------------------------------------===// 23a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// 24a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// IntervalPartition - This class builds and holds an "interval partition" for 25f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner// a function. This partition divides the control flow graph into a set of 26a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// maximal intervals, as defined with the properties above. Intuitively, a 27a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// BasicBlock is a (possibly nonexistent) loop with a "tail" of non looping 28a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// nodes following it. 29a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// 30f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattnerclass IntervalPartition : public FunctionPass, public std::vector<Interval*> { 31697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner typedef std::map<BasicBlock*, Interval*> IntervalMapTy; 32a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner IntervalMapTy IntervalMap; 33a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 34697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner typedef std::vector<Interval*> IntervalListTy; 35a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner Interval *RootInterval; 36a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 37a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattnerpublic: 38facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner static AnalysisID ID; // We are an analysis, we must have an ID 39facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner 4000444d0630b8baaedd47bff5981a24197a04a44cChris Lattner IntervalPartition() : RootInterval(0) {} 41facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner 42f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner // run - Calculate the interval partition for this function 437e70829632f82de15db187845666aaca6e04b792Chris Lattner virtual bool runOnFunction(Function &F); 44a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 45a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // IntervalPartition ctor - Build a reduced interval partition from an 46a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // existing interval graph. This takes an additional boolean parameter to 47a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // distinguish it from a copy constructor. Always pass in false for now. 48a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // 49a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner IntervalPartition(IntervalPartition &I, bool); 50a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 51a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // Destructor - Free memory 52facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner ~IntervalPartition() { destroy(); } 53a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 5497f51a3024a72ef8500e95b90e6361e6783160fdChris Lattner // print - Show contents in human readable format... 5597f51a3024a72ef8500e95b90e6361e6783160fdChris Lattner virtual void print(std::ostream &O) const; 5697f51a3024a72ef8500e95b90e6361e6783160fdChris Lattner 57a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // getRootInterval() - Return the root interval that contains the starting 58f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner // block of the function. 59a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner inline Interval *getRootInterval() { return RootInterval; } 60a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 61a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // isDegeneratePartition() - Returns true if the interval partition contains 62a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // a single interval, and thus cannot be simplified anymore. 63a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner bool isDegeneratePartition() { return size() == 1; } 64a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 65a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // TODO: isIrreducible - look for triangle graph. 66a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 67a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // getBlockInterval - Return the interval that a basic block exists in. 68a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner inline Interval *getBlockInterval(BasicBlock *BB) { 69a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner IntervalMapTy::iterator I = IntervalMap.find(BB); 70a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner return I != IntervalMap.end() ? I->second : 0; 71a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner } 72a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 73f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner // getAnalysisUsage - Implement the Pass API 74f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 75f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner AU.setPreservesAll(); 76f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner AU.addProvided(ID); 77facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner } 78facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner 79a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattnerprivate: 80f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner // destroy - Reset state back to before function was analyzed 81facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner void destroy(); 82facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner 834dd88f6fbf6dc44ceba03b34aeab458536789b98Chris Lattner // addIntervalToPartition - Add an interval to the internal list of intervals, 844dd88f6fbf6dc44ceba03b34aeab458536789b98Chris Lattner // and then add mappings from all of the basic blocks in the interval to the 854dd88f6fbf6dc44ceba03b34aeab458536789b98Chris Lattner // interval itself (in the IntervalMap). 86a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // 874dd88f6fbf6dc44ceba03b34aeab458536789b98Chris Lattner void addIntervalToPartition(Interval *I); 88a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 89a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // updatePredecessors - Interval generation only sets the successor fields of 90a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // the interval data structures. After interval generation is complete, 91a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // run through all of the intervals and propogate successor info as 92a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // predecessor info. 93a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // 94a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner void updatePredecessors(Interval *Int); 95a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner}; 96a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 97a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner#endif 98