X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.h;h=f7f4569cb3518b05f08268bd8311d03642bf8014;hb=151c80be8180a7a0aa1594848699aa6b678b3998;hp=59441fb3bb8312e2a98958b794a8445c67fb23bf;hpb=32bdd4ea65f58e3227176b9a5a43013fb13f06a5;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.h b/lib/CodeGen/LiveIntervalAnalysis.h index 59441fb3bb8..f7f4569cb35 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.h +++ b/lib/CodeGen/LiveIntervalAnalysis.h @@ -1,4 +1,4 @@ -//===-- llvm/CodeGen/LiveInterval.h - Live Interval Analysis ----*- C++ -*-===// +//===-- LiveIntervalAnalysis.h - Live Interval Analysis ---------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -7,175 +7,191 @@ // //===----------------------------------------------------------------------===// // -// 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 -// 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) +// 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 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). // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_LIVEINTERVALS_H -#define LLVM_CODEGEN_LIVEINTERVALS_H +#ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H +#define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H +#include "llvm/ADT/DenseMap.h" #include "llvm/CodeGen/MachineFunctionPass.h" -#include +#include "LiveInterval.h" namespace llvm { - class LiveVariables; - class MRegisterInfo; + class LiveVariables; + class MRegisterInfo; + class TargetInstrInfo; + class VirtRegMap; - class LiveIntervals : public MachineFunctionPass - { - public: - struct Interval { - typedef std::pair Range; - typedef std::vector Ranges; - unsigned reg; // the register of this interval - float weight; // weight of this interval (number of uses - // * 10^loopDepth) - Ranges ranges; // the ranges in which this register is live + class LiveIntervals : public MachineFunctionPass { + MachineFunction* mf_; + const TargetMachine* tm_; + const MRegisterInfo* mri_; + const TargetInstrInfo* tii_; + LiveVariables* lv_; + + typedef std::map Mi2IndexMap; + Mi2IndexMap mi2iMap_; - Interval(unsigned r); + typedef std::vector Index2MiMap; + Index2MiMap i2miMap_; - unsigned start() const { - assert(!ranges.empty() && "empty interval for register"); - return ranges.front().first; - } + typedef std::map Reg2IntervalMap; + Reg2IntervalMap r2iMap_; - unsigned end() const { - assert(!ranges.empty() && "empty interval for register"); - return ranges.back().second; - } - - bool expiredAt(unsigned index) const { - return end() <= (index + 1); - } - - bool liveAt(unsigned index) const; - - bool overlaps(const Interval& other) const; - - void addRange(unsigned start, unsigned end); + typedef DenseMap Reg2RegMap; + Reg2RegMap r2rMap_; - void join(const Interval& other); - - private: - Ranges::iterator mergeRangesForward(Ranges::iterator it); - - Ranges::iterator mergeRangesBackward(Ranges::iterator it); - }; - - struct StartPointComp { - bool operator()(const Interval& lhs, const Interval& rhs) { - return lhs.ranges.front().first < rhs.ranges.front().first; - } - }; - - struct EndPointComp { - bool operator()(const Interval& lhs, const Interval& rhs) { - return lhs.ranges.back().second < rhs.ranges.back().second; - } - }; - - typedef std::list Intervals; - typedef std::map Reg2RegMap; - typedef std::vector MachineBasicBlockPtrs; - - private: - MachineFunction* mf_; - const TargetMachine* tm_; - const MRegisterInfo* mri_; - MachineBasicBlock* currentMbb_; - MachineBasicBlock::iterator currentInstr_; - LiveVariables* lv_; - - typedef std::map MbbIndex2MbbMap; - MbbIndex2MbbMap mbbi2mbbMap_; - - typedef std::map Mi2IndexMap; - Mi2IndexMap mi2iMap_; - - typedef std::map Reg2IntervalMap; - Reg2IntervalMap r2iMap_; - - Reg2RegMap r2rMap_; - - Intervals intervals_; - - public: - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual void releaseMemory(); - - /// runOnMachineFunction - pass entry point - virtual bool runOnMachineFunction(MachineFunction&); - - 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; - } - - const Reg2RegMap& getJoinedRegMap() const { - return r2rMap_; - } - - /// rep - returns the representative of this register - unsigned rep(unsigned reg); + std::vector allocatableRegs_; - private: - /// computeIntervals - compute live intervals - void computeIntervals(); + public: + struct InstrSlots + { + enum { + LOAD = 0, + USE = 1, + DEF = 2, + STORE = 3, + NUM = 4, + }; + }; - /// joinIntervals - join compatible live intervals - void joinIntervals(); + 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; + } - /// handleRegisterDef - update intervals for a register def - /// (calls handlePhysicalRegisterDef and - /// handleVirtualRegisterDef) - void handleRegisterDef(MachineBasicBlock* mbb, - MachineBasicBlock::iterator mi, - unsigned reg); + typedef Reg2IntervalMap::iterator iterator; + typedef Reg2IntervalMap::const_iterator const_iterator; + const_iterator begin() const { return r2iMap_.begin(); } + const_iterator end() const { return r2iMap_.end(); } + iterator begin() { return r2iMap_.begin(); } + iterator end() { return r2iMap_.end(); } + unsigned getNumIntervals() const { return r2iMap_.size(); } + + LiveInterval &getInterval(unsigned reg) { + Reg2IntervalMap::iterator I = r2iMap_.find(reg); + assert(I != r2iMap_.end() && "Interval does not exist for register"); + return I->second; + } - /// handleVirtualRegisterDef - update intervals for a virtual - /// register def - void handleVirtualRegisterDef(MachineBasicBlock* mbb, - MachineBasicBlock::iterator mi, - unsigned reg); + const LiveInterval &getInterval(unsigned reg) const { + Reg2IntervalMap::const_iterator I = r2iMap_.find(reg); + assert(I != r2iMap_.end() && "Interval does not exist for register"); + return I->second; + } - /// handlePhysicalRegisterDef - update intervals for a - /// physical register def - void handlePhysicalRegisterDef(MachineBasicBlock* mbb, - MachineBasicBlock::iterator mi, - unsigned reg); + /// getInstructionIndex - returns the base index of instr + unsigned getInstructionIndex(MachineInstr* instr) const { + Mi2IndexMap::const_iterator it = mi2iMap_.find(instr); + assert(it != mi2iMap_.end() && "Invalid instruction!"); + return it->second; + } - bool overlapsAliases(const Interval& lhs, const Interval& rhs) const; + /// getInstructionFromIndex - given an index in any slot of an + /// instruction return a pointer the instruction + MachineInstr* getInstructionFromIndex(unsigned index) const { + index /= InstrSlots::NUM; // convert index to vector index + assert(index < i2miMap_.size() && + "index does not correspond to an instruction"); + return i2miMap_[index]; + } - unsigned getInstructionIndex(MachineInstr* instr) const { - assert(mi2iMap_.count(instr) && "instruction not assigned a number"); - return mi2iMap_.find(instr)->second; - } - - void printRegName(unsigned reg) const; - }; + std::vector addIntervalsForSpills(const LiveInterval& i, + VirtRegMap& vrm, + int slot); + + virtual void getAnalysisUsage(AnalysisUsage &AU) const; + virtual void releaseMemory(); + + /// runOnMachineFunction - pass entry point + virtual bool runOnMachineFunction(MachineFunction&); + + /// print - Implement the dump method. + virtual void print(std::ostream &O, const Module* = 0) const; + + private: + /// computeIntervals - compute live intervals + void computeIntervals(); + + /// joinIntervals - join compatible live intervals + void joinIntervals(); + + /// joinIntervalsInMachineBB - Join intervals based on move + /// instructions in the specified basic block. + void joinIntervalsInMachineBB(MachineBasicBlock *MBB); + + /// handleRegisterDef - update intervals for a register def + /// (calls handlePhysicalRegisterDef and + /// handleVirtualRegisterDef) + void handleRegisterDef(MachineBasicBlock* mbb, + MachineBasicBlock::iterator mi, + unsigned reg); + + /// handleVirtualRegisterDef - update intervals for a virtual + /// register def + void handleVirtualRegisterDef(MachineBasicBlock* mbb, + MachineBasicBlock::iterator mi, + LiveInterval& interval); + + /// handlePhysicalRegisterDef - update intervals for a physical register + /// def. If the defining instruction is a move instruction, SrcReg will be + /// the input register, and DestReg will be the result. Note that Interval + /// may not match DestReg (it might be an alias instead). + /// + void handlePhysicalRegisterDef(MachineBasicBlock* mbb, + MachineBasicBlock::iterator mi, + LiveInterval& interval, + unsigned SrcReg, unsigned DestReg); + + /// Return true if the two specified registers belong to different + /// register classes. The registers may be either phys or virt regs. + bool differingRegisterClasses(unsigned RegA, unsigned RegB) const; + + bool overlapsAliases(const LiveInterval *lhs, + const LiveInterval *rhs) const; + + static LiveInterval createInterval(unsigned Reg); + + LiveInterval &getOrCreateInterval(unsigned reg) { + Reg2IntervalMap::iterator I = r2iMap_.find(reg); + if (I == r2iMap_.end()) + I = r2iMap_.insert(I, std::make_pair(reg, createInterval(reg))); + return I->second; + } - inline bool operator==(const LiveIntervals::Interval& lhs, - const LiveIntervals::Interval& rhs) { - return lhs.reg == rhs.reg; + /// rep - returns the representative of this register + unsigned rep(unsigned Reg) { + unsigned Rep = r2rMap_[Reg]; + if (Rep) + return r2rMap_[Reg] = rep(Rep); + return Reg; } - std::ostream& operator<<(std::ostream& os, - const LiveIntervals::Interval& li); + void printRegName(unsigned reg) const; + }; } // End llvm namespace