X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.h;h=5b78342e281d4747e8407546da76edfcdcb4b6f7;hb=91ef460285021b5bf43b3850f0f8958a09b8939c;hp=cecfbbadbdfb98c832757f565df632cbcedf31e1;hpb=6b4edbaaf9021e0434f0ce0c3724eb43ed41b770;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.h b/lib/CodeGen/LiveIntervalAnalysis.h index cecfbbadbdf..5b78342e281 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.h +++ b/lib/CodeGen/LiveIntervalAnalysis.h @@ -9,12 +9,12 @@ // // This file implements the LiveInterval analysis pass. Given some // numbering of each the machine instructions (in this implemention -// depth-first order) an interval [i, j] is said to be a live interval +// depth-first order) an interval [i, j) is said to be a live interval // for register v if there is no instruction with number j' > j such // that v is live at j' abd there is no instruction with number i' < i // such that v is live at i'. In this implementation intervals can -// have holes, i.e. an interval might look like [1,20], [50,65], -// [1000,1001] +// have holes, i.e. an interval might look like [1,20), [50,65), +// [1000,1001) // //===----------------------------------------------------------------------===// @@ -22,14 +22,13 @@ #define LLVM_CODEGEN_LIVEINTERVALS_H #include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/MachineBasicBlock.h" -#include -#include +#include namespace llvm { class LiveVariables; class MRegisterInfo; + class VirtRegMap; class LiveIntervals : public MachineFunctionPass { @@ -40,22 +39,26 @@ namespace llvm { unsigned reg; // the register of this interval float weight; // weight of this interval (number of uses // * 10^loopDepth) - Ranges ranges; // the ranges this register is valid + Ranges ranges; // the ranges in which this register is live Interval(unsigned r); + bool empty() const { return ranges.empty(); } + + bool spilled() const; + unsigned start() const { - assert(!ranges.empty() && "empty interval for register"); + assert(!empty() && "empty interval for register"); return ranges.front().first; } unsigned end() const { - assert(!ranges.empty() && "empty interval for register"); + assert(!empty() && "empty interval for register"); return ranges.back().second; } bool expiredAt(unsigned index) const { - return end() <= index; + return end() <= (index + 1); } bool liveAt(unsigned index) const; @@ -64,10 +67,12 @@ namespace llvm { void addRange(unsigned start, unsigned end); + void join(const Interval& other); + private: - void mergeRangesForward(Ranges::iterator it); + Ranges::iterator mergeRangesForward(Ranges::iterator it); - void mergeRangesBackward(Ranges::iterator it); + Ranges::iterator mergeRangesBackward(Ranges::iterator it); }; struct StartPointComp { @@ -82,8 +87,7 @@ namespace llvm { } }; - typedef std::vector Intervals; - typedef std::vector MachineBasicBlockPtrs; + typedef std::list Intervals; private: MachineFunction* mf_; @@ -93,39 +97,82 @@ namespace llvm { MachineBasicBlock::iterator currentInstr_; LiveVariables* lv_; - std::vector allocatableRegisters_; - typedef std::map MbbIndex2MbbMap; MbbIndex2MbbMap mbbi2mbbMap_; typedef std::map Mi2IndexMap; Mi2IndexMap mi2iMap_; - typedef std::map Reg2IntervalMap; + typedef std::vector Index2MiMap; + Index2MiMap i2miMap_; + + typedef std::map Reg2IntervalMap; Reg2IntervalMap r2iMap_; + typedef std::map Reg2RegMap; + Reg2RegMap r2rMap_; + Intervals intervals_; public: - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - Intervals& getIntervals() { return intervals_; } - MachineBasicBlockPtrs getOrderedMachineBasicBlockPtrs() const { - MachineBasicBlockPtrs result; - for (MbbIndex2MbbMap::const_iterator - it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); - it != itEnd; ++it) { - result.push_back(it->second); - } - return result; + struct InstrSlots + { + enum { + LOAD = 0, + USE = 1, + DEF = 2, + STORE = 3, + NUM = 4, + }; + }; + + static unsigned getBaseIndex(unsigned index) { + return index - (index % InstrSlots::NUM); + } + static unsigned getBoundaryIndex(unsigned index) { + return getBaseIndex(index + InstrSlots::NUM - 1); + } + static unsigned getLoadIndex(unsigned index) { + return getBaseIndex(index) + InstrSlots::LOAD; + } + static unsigned getUseIndex(unsigned index) { + return getBaseIndex(index) + InstrSlots::USE; + } + static unsigned getDefIndex(unsigned index) { + return getBaseIndex(index) + InstrSlots::DEF; + } + static unsigned getStoreIndex(unsigned index) { + return getBaseIndex(index) + InstrSlots::STORE; } - private: + virtual void getAnalysisUsage(AnalysisUsage &AU) const; + virtual void releaseMemory(); + /// runOnMachineFunction - pass entry point - bool runOnMachineFunction(MachineFunction&); + virtual bool runOnMachineFunction(MachineFunction&); + + Interval& getInterval(unsigned reg) { + assert(r2iMap_.count(reg)&& "Interval does not exist for register"); + return *r2iMap_.find(reg)->second; + } + + /// getInstructionIndex - returns the base index of instr + unsigned getInstructionIndex(MachineInstr* instr) const; + /// getInstructionFromIndex - given an index in any slot of an + /// instruction return a pointer the instruction + MachineInstr* getInstructionFromIndex(unsigned index) const; + + Intervals& getIntervals() { return intervals_; } + + void updateSpilledInterval(Interval& i, VirtRegMap& vrm, int slot); + + private: /// computeIntervals - compute live intervals void computeIntervals(); + /// joinIntervals - join compatible live intervals + void joinIntervals(); /// handleRegisterDef - update intervals for a register def /// (calls handlePhysicalRegisterDef and @@ -146,7 +193,10 @@ namespace llvm { MachineBasicBlock::iterator mi, unsigned reg); - unsigned getInstructionIndex(MachineInstr* instr) const; + bool overlapsAliases(const Interval& lhs, const Interval& rhs) const; + + /// rep - returns the representative of this register + unsigned rep(unsigned reg); void printRegName(unsigned reg) const; };