LLVM API Documentation
00001 //===- IntervalPartition.h - Interval partition Calculation -----*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file contains the declaration of the IntervalPartition class, which 00011 // calculates and represents the interval partition of a function, or a 00012 // preexisting interval partition. 00013 // 00014 // In this way, the interval partition may be used to reduce a flow graph down 00015 // to its degenerate single node interval partition (unless it is irreducible). 00016 // 00017 // TODO: The IntervalPartition class should take a bool parameter that tells 00018 // whether it should add the "tails" of an interval to an interval itself or if 00019 // they should be represented as distinct intervals. 00020 // 00021 //===----------------------------------------------------------------------===// 00022 00023 #ifndef LLVM_INTERVAL_PARTITION_H 00024 #define LLVM_INTERVAL_PARTITION_H 00025 00026 #include "llvm/Analysis/Interval.h" 00027 #include "llvm/Pass.h" 00028 00029 namespace llvm { 00030 00031 //===----------------------------------------------------------------------===// 00032 // 00033 // IntervalPartition - This class builds and holds an "interval partition" for 00034 // a function. This partition divides the control flow graph into a set of 00035 // maximal intervals, as defined with the properties above. Intuitively, a 00036 // BasicBlock is a (possibly nonexistent) loop with a "tail" of non looping 00037 // nodes following it. 00038 // 00039 class IntervalPartition : public FunctionPass { 00040 typedef std::map<BasicBlock*, Interval*> IntervalMapTy; 00041 IntervalMapTy IntervalMap; 00042 00043 typedef std::vector<Interval*> IntervalListTy; 00044 Interval *RootInterval; 00045 std::vector<Interval*> Intervals; 00046 00047 public: 00048 IntervalPartition() : RootInterval(0) {} 00049 00050 // run - Calculate the interval partition for this function 00051 virtual bool runOnFunction(Function &F); 00052 00053 // IntervalPartition ctor - Build a reduced interval partition from an 00054 // existing interval graph. This takes an additional boolean parameter to 00055 // distinguish it from a copy constructor. Always pass in false for now. 00056 // 00057 IntervalPartition(IntervalPartition &I, bool); 00058 00059 // Destructor - Free memory 00060 ~IntervalPartition() { destroy(); } 00061 00062 // print - Show contents in human readable format... 00063 virtual void print(std::ostream &O, const Module* = 0) const; 00064 00065 // getRootInterval() - Return the root interval that contains the starting 00066 // block of the function. 00067 inline Interval *getRootInterval() { return RootInterval; } 00068 00069 // isDegeneratePartition() - Returns true if the interval partition contains 00070 // a single interval, and thus cannot be simplified anymore. 00071 bool isDegeneratePartition() { return Intervals.size() == 1; } 00072 00073 // TODO: isIrreducible - look for triangle graph. 00074 00075 // getBlockInterval - Return the interval that a basic block exists in. 00076 inline Interval *getBlockInterval(BasicBlock *BB) { 00077 IntervalMapTy::iterator I = IntervalMap.find(BB); 00078 return I != IntervalMap.end() ? I->second : 0; 00079 } 00080 00081 // getAnalysisUsage - Implement the Pass API 00082 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00083 AU.setPreservesAll(); 00084 } 00085 00086 // Interface to Intervals vector... 00087 const std::vector<Interval*> &getIntervals() const { return Intervals; } 00088 00089 private: 00090 // destroy - Reset state back to before function was analyzed 00091 void destroy(); 00092 00093 // addIntervalToPartition - Add an interval to the internal list of intervals, 00094 // and then add mappings from all of the basic blocks in the interval to the 00095 // interval itself (in the IntervalMap). 00096 // 00097 void addIntervalToPartition(Interval *I); 00098 00099 // updatePredecessors - Interval generation only sets the successor fields of 00100 // the interval data structures. After interval generation is complete, 00101 // run through all of the intervals and propagate successor info as 00102 // predecessor info. 00103 // 00104 void updatePredecessors(Interval *Int); 00105 }; 00106 00107 } // End llvm namespace 00108 00109 #endif