X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveIntervalAnalysis.h;h=c803fbd484daf417f3d078fa37e7322e215a94d3;hb=cada245d06959831b90f8c29f92e77beda4b71cb;hp=4e2cbeba0b003d6b92ac7a2d6b74a4d2e86eca64;hpb=a3b8b5c0e0a1d0942288568b2012592184ca67c5;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 4e2cbeba0b0..c803fbd484d 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -21,139 +21,295 @@ #define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H #include "llvm/CodeGen/MachineFunctionPass.h" -#include "LiveInterval.h" -#include +#include "llvm/CodeGen/LiveInterval.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/Allocator.h" +#include namespace llvm { - class LiveVariables; - class MRegisterInfo; - class VirtRegMap; - - class LiveIntervals : public MachineFunctionPass - { - public: - typedef std::list Intervals; - - private: - MachineFunction* mf_; - const TargetMachine* tm_; - const MRegisterInfo* mri_; - MachineBasicBlock* currentMbb_; - MachineBasicBlock::iterator currentInstr_; - LiveVariables* lv_; - - typedef std::map Mi2IndexMap; - Mi2IndexMap mi2iMap_; - - typedef std::vector Index2MiMap; - Index2MiMap i2miMap_; - - typedef std::map Reg2IntervalMap; - Reg2IntervalMap r2iMap_; - - typedef std::map Reg2RegMap; - Reg2RegMap r2rMap_; - - Intervals intervals_; - - public: - 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; - } - - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual void releaseMemory(); - - /// runOnMachineFunction - pass entry point - virtual bool runOnMachineFunction(MachineFunction&); - - LiveInterval& 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_; } - - std::vector addIntervalsForSpills(const LiveInterval& i, - VirtRegMap& vrm, - int slot); - - 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 - void handlePhysicalRegisterDef(MachineBasicBlock* mbb, - MachineBasicBlock::iterator mi, - LiveInterval& interval); - - bool overlapsAliases(const LiveInterval& lhs, - const LiveInterval& rhs) const; - - - LiveInterval& getOrCreateInterval(unsigned reg); - - /// rep - returns the representative of this register - unsigned rep(unsigned reg); - - void printRegName(unsigned reg) const; + class LiveVariables; + class LoopInfo; + class MRegisterInfo; + class SSARegMap; + class TargetInstrInfo; + class TargetRegisterClass; + class VirtRegMap; + typedef std::pair IdxMBBPair; + + class LiveIntervals : public MachineFunctionPass { + MachineFunction* mf_; + const TargetMachine* tm_; + const MRegisterInfo* mri_; + const TargetInstrInfo* tii_; + LiveVariables* lv_; + + /// Special pool allocator for VNInfo's (LiveInterval val#). + /// + BumpPtrAllocator VNInfoAllocator; + + /// MBB2IdxMap - The indexes of the first and last instructions in the + /// specified basic block. + std::vector > MBB2IdxMap; + + /// Idx2MBBMap - Sorted list of pairs of index of first instruction + /// and MBB id. + std::vector Idx2MBBMap; + + typedef std::map Mi2IndexMap; + Mi2IndexMap mi2iMap_; + + typedef std::vector Index2MiMap; + Index2MiMap i2miMap_; + + typedef std::map Reg2IntervalMap; + Reg2IntervalMap r2iMap_; + + BitVector allocatableRegs_; + + std::vector ClonedMIs; + + public: + static char ID; // Pass identification, replacement for typeid + LiveIntervals() : MachineFunctionPass((intptr_t)&ID) {} + + 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; + } + + static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { + return (isDef + isUse) * powf(10.0F, (float)loopDepth); + } + + 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; + } + + 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; + } + + bool hasInterval(unsigned reg) const { + return r2iMap_.count(reg); + } + + /// getMBBStartIdx - Return the base index of the first instruction in the + /// specified MachineBasicBlock. + unsigned getMBBStartIdx(MachineBasicBlock *MBB) const { + return getMBBStartIdx(MBB->getNumber()); + } + unsigned getMBBStartIdx(unsigned MBBNo) const { + assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!"); + return MBB2IdxMap[MBBNo].first; + } + + /// getMBBEndIdx - Return the store index of the last instruction in the + /// specified MachineBasicBlock. + unsigned getMBBEndIdx(MachineBasicBlock *MBB) const { + return getMBBEndIdx(MBB->getNumber()); + } + unsigned getMBBEndIdx(unsigned MBBNo) const { + assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!"); + return MBB2IdxMap[MBBNo].second; + } + + /// 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; + } + + /// 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]; + } + + /// conflictsWithPhysRegDef - Returns true if the specified register + /// is defined during the duration of the specified interval. + bool conflictsWithPhysRegDef(const LiveInterval &li, VirtRegMap &vrm, + unsigned reg); + + /// findLiveInMBBs - Given a live range, if the value of the range + /// is live in any MBB returns true as well as the list of basic blocks + /// where the value is live in. + bool findLiveInMBBs(const LiveRange &LR, + SmallVectorImpl &MBBs) const; + + // Interval creation + + 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; + } + + // Interval removal + + void removeInterval(unsigned Reg) { + r2iMap_.erase(Reg); + } + + /// isRemoved - returns true if the specified machine instr has been + /// removed. + bool isRemoved(MachineInstr* instr) const { + return !mi2iMap_.count(instr); + } + + /// RemoveMachineInstrFromMaps - This marks the specified machine instr as + /// deleted. + void RemoveMachineInstrFromMaps(MachineInstr *MI) { + // remove index -> MachineInstr and + // MachineInstr -> index mappings + Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI); + if (mi2i != mi2iMap_.end()) { + i2miMap_[mi2i->second/InstrSlots::NUM] = 0; + mi2iMap_.erase(mi2i); + } + } + + BumpPtrAllocator& getVNInfoAllocator() { return VNInfoAllocator; } + + 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; + void print(std::ostream *O, const Module* M = 0) const { + if (O) print(*O, M); + } + + /// addIntervalsForSpills - Create new intervals for spilled defs / uses of + /// the given interval. + std::vector + addIntervalsForSpills(const LiveInterval& i, + const LoopInfo *loopInfo, VirtRegMap& vrm); + + private: + /// computeIntervals - Compute live intervals. + void computeIntervals(); + + /// handleRegisterDef - update intervals for a register def + /// (calls handlePhysicalRegisterDef and + /// handleVirtualRegisterDef) + void handleRegisterDef(MachineBasicBlock *MBB, + MachineBasicBlock::iterator MI, unsigned MIIdx, + unsigned reg); + + /// handleVirtualRegisterDef - update intervals for a virtual + /// register def + void handleVirtualRegisterDef(MachineBasicBlock *MBB, + MachineBasicBlock::iterator MI, + unsigned MIIdx, + LiveInterval& interval); + + /// handlePhysicalRegisterDef - update intervals for a physical register + /// def. + void handlePhysicalRegisterDef(MachineBasicBlock* mbb, + MachineBasicBlock::iterator mi, + unsigned MIIdx, + LiveInterval &interval, + unsigned SrcReg); + + /// handleLiveInRegister - Create interval for a livein register. + void handleLiveInRegister(MachineBasicBlock* mbb, + unsigned MIIdx, + LiveInterval &interval, bool isAlias = false); + + /// isReMaterializable - Returns true if the definition MI of the specified + /// val# of the specified interval is re-materializable. + bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo, + MachineInstr *MI); + + /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from + /// slot / to reg or any rematerialized load into ith operand of specified + /// MI. If it is successul, MI is updated with the newly created MI and + /// returns true. + bool tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm, + MachineInstr *DefMI, unsigned index, unsigned i, + bool isSS, int slot, unsigned reg); + + bool anyKillInMBBAfterIdx(const LiveInterval &li, + MachineBasicBlock *MBB, unsigned Idx, + const VNInfo *VNI = NULL) const; + + bool intervalIsInOneMBB(const LiveInterval &li) const; + + /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions + /// for addIntervalsForSpills to rewrite uses / defs for the given live range. + void rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit, + unsigned id, unsigned index, unsigned end, MachineInstr *MI, + MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot, + bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, + VirtRegMap &vrm, SSARegMap *RegMap, const TargetRegisterClass* rc, + SmallVector &ReMatIds, + unsigned &NewVReg, bool &HasDef, bool &HasUse, const LoopInfo *loopInfo, + std::map &NewVRegs, + std::vector &NewLIs); + void rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, + LiveInterval::Ranges::const_iterator &I, + MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot, + bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, + VirtRegMap &vrm, SSARegMap *RegMap, const TargetRegisterClass* rc, + SmallVector &ReMatIds, const LoopInfo *loopInfo, + BitVector &SpillMBBs, + std::map > &SpillIdxes, + std::map &NewVRegs, + std::vector &NewLIs); + + static LiveInterval createInterval(unsigned Reg); + + void printRegName(unsigned reg) const; + }; + } // End llvm namespace #endif