X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveIntervalAnalysis.h;h=a94840e89621a39bdb4a9f16ddd2adbca854769f;hb=5eca075b74d62c621b160aa216b4cd50829a2cc7;hp=84c6d6791941c7930c9d01ce8c62d13ac1cf8769;hpb=bdf34bc12bfc39de02c19fa250e83edb5924a6cf;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 84c6d679194..a94840e8962 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -28,10 +28,10 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/Support/Allocator.h" #include -#include namespace llvm { + class AliasAnalysis; class LiveVariables; class MachineLoopInfo; class TargetRegisterInfo; @@ -54,6 +54,20 @@ namespace llvm { return LHS.first < RHS.first; } }; + + // Provide DenseMapInfo for unsigned. + template<> + struct DenseMapInfo { + static inline unsigned getEmptyKey() { return (unsigned)-1; } + static inline unsigned getTombstoneKey() { return (unsigned)-2; } + static unsigned getHashValue(const unsigned Val) { + return Val * 37; + } + static bool isEqual(const unsigned LHS, const unsigned RHS) { + return LHS == RHS; + } + static bool isPod() { return true; } + }; class LiveIntervals : public MachineFunctionPass { MachineFunction* mf_; @@ -61,6 +75,7 @@ namespace llvm { const TargetMachine* tm_; const TargetRegisterInfo* tri_; const TargetInstrInfo* tii_; + AliasAnalysis *aa_; LiveVariables* lv_; /// Special pool allocator for VNInfo's (LiveInterval val#). @@ -75,13 +90,16 @@ namespace llvm { /// and MBB id. std::vector Idx2MBBMap; - typedef std::map Mi2IndexMap; + /// FunctionSize - The number of instructions present in the function + uint64_t FunctionSize; + + typedef DenseMap Mi2IndexMap; Mi2IndexMap mi2iMap_; typedef std::vector Index2MiMap; Index2MiMap i2miMap_; - typedef std::map Reg2IntervalMap; + typedef DenseMap Reg2IntervalMap; Reg2IntervalMap r2iMap_; BitVector allocatableRegs_; @@ -121,12 +139,8 @@ namespace llvm { return getBaseIndex(index) + InstrSlots::STORE; } - static float getSpillWeight(bool isDef, bool isUse, bool isMem, - unsigned loopDepth) { - float Weight = isDef; - if (isUse) - Weight += isMem ? 1.2f : 1.0f; - return Weight * powf(10.0F, (float)loopDepth); + static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { + return (isDef + isUse) * powf(10.0F, (float)loopDepth); } typedef Reg2IntervalMap::iterator iterator; @@ -140,13 +154,13 @@ namespace llvm { LiveInterval &getInterval(unsigned reg) { Reg2IntervalMap::iterator I = r2iMap_.find(reg); assert(I != r2iMap_.end() && "Interval does not exist for register"); - return I->second; + 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; + return *I->second; } bool hasInterval(unsigned reg) const { @@ -173,6 +187,20 @@ namespace llvm { return MBB2IdxMap[MBBNo].second; } + /// getScaledIntervalSize - get the size of an interval in "units," + /// where every function is composed of one thousand units. This + /// measure scales properly with empty index slots in the function. + double getScaledIntervalSize(LiveInterval& I) { + return (1000.0 / InstrSlots::NUM * I.getSize()) / i2miMap_.size(); + } + + /// getApproximateInstructionCount - computes an estimate of the number + /// of instructions in a given LiveInterval. + unsigned getApproximateInstructionCount(LiveInterval& I) { + double IntervalPercentage = getScaledIntervalSize(I) / 1000.0; + return (unsigned)(IntervalPercentage * FunctionSize); + } + /// getMBBFromIndex - given an index in any instruction of an /// MBB return a pointer the MBB MachineBasicBlock* getMBBFromIndex(unsigned index) const { @@ -212,7 +240,7 @@ namespace llvm { /// 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. + /// in which the value is live. bool findLiveInMBBs(const LiveRange &LR, SmallVectorImpl &MBBs) const; @@ -221,8 +249,8 @@ namespace llvm { 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; + I = r2iMap_.insert(std::make_pair(reg, createInterval(reg))).first; + return *I->second; } /// addLiveRangeToEndOfBlock - Given a register and an instruction, @@ -233,7 +261,9 @@ namespace llvm { // Interval removal void removeInterval(unsigned Reg) { - r2iMap_.erase(Reg); + DenseMap::iterator I = r2iMap_.find(Reg); + delete I->second; + r2iMap_.erase(I); } /// isRemoved - returns true if the specified machine instr has been @@ -325,20 +355,20 @@ namespace llvm { /// handleVirtualRegisterDef) void handleRegisterDef(MachineBasicBlock *MBB, MachineBasicBlock::iterator MI, unsigned MIIdx, - unsigned reg); + MachineOperand& MO, unsigned MOIdx); /// handleVirtualRegisterDef - update intervals for a virtual /// register def void handleVirtualRegisterDef(MachineBasicBlock *MBB, MachineBasicBlock::iterator MI, - unsigned MIIdx, - LiveInterval& interval); + unsigned MIIdx, MachineOperand& MO, + unsigned MOIdx, LiveInterval& interval); /// handlePhysicalRegisterDef - update intervals for a physical register /// def. void handlePhysicalRegisterDef(MachineBasicBlock* mbb, MachineBasicBlock::iterator mi, - unsigned MIIdx, + unsigned MIIdx, MachineOperand& MO, LiveInterval &interval, MachineInstr *CopyMI); @@ -403,10 +433,10 @@ namespace llvm { bool alsoFoldARestore(int Id, int index, unsigned vr, BitVector &RestoreMBBs, - std::map >&RestoreIdxes); + DenseMap >&RestoreIdxes); void eraseRestoreInfo(int Id, int index, unsigned vr, BitVector &RestoreMBBs, - std::map >&RestoreIdxes); + DenseMap >&RestoreIdxes); /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being /// spilled and create empty intervals for their uses. @@ -429,7 +459,7 @@ namespace llvm { VirtRegMap &vrm, const TargetRegisterClass* rc, SmallVector &ReMatIds, const MachineLoopInfo *loopInfo, unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, - std::map &MBBVRegsMap, + DenseMap &MBBVRegsMap, std::vector &NewLIs, float &SSWeight); void rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, LiveInterval::Ranges::const_iterator &I, @@ -438,13 +468,13 @@ namespace llvm { VirtRegMap &vrm, const TargetRegisterClass* rc, SmallVector &ReMatIds, const MachineLoopInfo *loopInfo, BitVector &SpillMBBs, - std::map > &SpillIdxes, + DenseMap > &SpillIdxes, BitVector &RestoreMBBs, - std::map > &RestoreIdxes, - std::map &MBBVRegsMap, + DenseMap > &RestoreIdxes, + DenseMap &MBBVRegsMap, std::vector &NewLIs, float &SSWeight); - static LiveInterval createInterval(unsigned Reg); + static LiveInterval* createInterval(unsigned Reg); void printRegName(unsigned reg) const; };