X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveIntervalAnalysis.h;h=a94840e89621a39bdb4a9f16ddd2adbca854769f;hb=5eca075b74d62c621b160aa216b4cd50829a2cc7;hp=440ae6ec5b6944fef852dde0764d057b7f18f9e1;hpb=c8d044e4f779fdcfc5e7d592927740fd8f672a70;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 440ae6ec5b6..a94840e8962 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -10,7 +10,7 @@ // 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 j' > j such that v is live at j' and 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). @@ -31,6 +31,7 @@ namespace llvm { + class AliasAnalysis; class LiveVariables; class MachineLoopInfo; class TargetRegisterInfo; @@ -40,11 +41,41 @@ namespace llvm { class VirtRegMap; typedef std::pair IdxMBBPair; + inline bool operator<(unsigned V, const IdxMBBPair &IM) { + return V < IM.first; + } + + inline bool operator<(const IdxMBBPair &IM, unsigned V) { + return IM.first < V; + } + + struct Idx2MBBCompare { + bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const { + 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_; + MachineRegisterInfo* mri_; const TargetMachine* tm_; const TargetRegisterInfo* tri_; const TargetInstrInfo* tii_; + AliasAnalysis *aa_; LiveVariables* lv_; /// Special pool allocator for VNInfo's (LiveInterval val#). @@ -59,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_; @@ -115,18 +149,18 @@ namespace llvm { const_iterator end() const { return r2iMap_.end(); } iterator begin() { return r2iMap_.begin(); } iterator end() { return r2iMap_.end(); } - unsigned getNumIntervals() const { return r2iMap_.size(); } + unsigned getNumIntervals() const { return (unsigned)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; + 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 { @@ -153,6 +187,36 @@ 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 { + std::vector::const_iterator I = + std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), index); + // Take the pair containing the index + std::vector::const_iterator J = + ((I != Idx2MBBMap.end() && I->first > index) || + (I == Idx2MBBMap.end() && Idx2MBBMap.size()>0)) ? (I-1): I; + + assert(J != Idx2MBBMap.end() && J->first < index+1 && + index <= getMBBEndIdx(J->second) && + "index does not correspond to an MBB"); + return J->second; + } + /// getInstructionIndex - returns the base index of instr unsigned getInstructionIndex(MachineInstr* instr) const { Mi2IndexMap::const_iterator it = mi2iMap_.find(instr); @@ -176,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; @@ -185,14 +249,21 @@ 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, + /// adds a live range from that instruction to the end of its MBB. + LiveRange addLiveRangeToEndOfBlock(unsigned reg, + MachineInstr* startInst); // 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 @@ -246,16 +317,35 @@ namespace llvm { } /// addIntervalsForSpills - Create new intervals for spilled defs / uses of - /// the given interval. + /// the given interval. FIXME: It also returns the weight of the spill slot + /// (if any is created) by reference. This is temporary. std::vector addIntervalsForSpills(const LiveInterval& i, - const MachineLoopInfo *loopInfo, VirtRegMap& vrm); + const MachineLoopInfo *loopInfo, VirtRegMap& vrm, + float &SSWeight); + + /// spillPhysRegAroundRegDefsUses - Spill the specified physical register + /// around all defs and uses of the specified interval. + void spillPhysRegAroundRegDefsUses(const LiveInterval &li, + unsigned PhysReg, VirtRegMap &vrm); /// isReMaterializable - Returns true if every definition of MI of every /// val# of the specified interval is re-materializable. Also returns true /// by reference if all of the defs are load instructions. bool isReMaterializable(const LiveInterval &li, bool &isLoad); + /// getRepresentativeReg - Find the largest super register of the specified + /// physical register. + unsigned getRepresentativeReg(unsigned Reg) const; + + /// getNumConflictsWithPhysReg - Return the number of uses and defs of the + /// specified interval that conflicts with the specified physical register. + unsigned getNumConflictsWithPhysReg(const LiveInterval &li, + unsigned PhysReg) const; + + /// computeNumbering - Compute the index numbering. + void computeNumbering(); + private: /// computeIntervals - Compute live intervals. void computeIntervals(); @@ -265,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); @@ -287,6 +377,18 @@ namespace llvm { unsigned MIIdx, LiveInterval &interval, bool isAlias = false); + /// getReMatImplicitUse - If the remat definition MI has one (for now, we + /// only allow one) virtual register operand, then its uses are implicitly + /// using the register. Returns the virtual register. + unsigned getReMatImplicitUse(const LiveInterval &li, + MachineInstr *MI) const; + + /// isValNoAvailableAt - Return true if the val# of the specified interval + /// which reaches the given instruction also reaches the specified use + /// index. + bool isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, + unsigned UseIdx) const; + /// isReMaterializable - Returns true if the definition MI of the specified /// val# of the specified interval is re-materializable. Also returns true /// by reference if the def is a load. @@ -302,10 +404,11 @@ namespace llvm { SmallVector &Ops, bool isSS, int Slot, unsigned Reg); - /// canFoldMemoryOperand - Returns true if the specified load / store + /// canFoldMemoryOperand - Return true if the specified load / store /// folding is possible. bool canFoldMemoryOperand(MachineInstr *MI, - SmallVector &Ops) const; + SmallVector &Ops, + bool ReMatLoadSS) const; /// anyKillInMBBAfterIdx - Returns true if there is a kill of the specified /// VNInfo that's after the specified index but is within the basic block. @@ -316,6 +419,10 @@ namespace llvm { /// within a single basic block. bool intervalIsInOneMBB(const LiveInterval &li) const; + /// hasAllocatableSuperReg - Return true if the specified physical register + /// has any super register that's allocatable. + bool hasAllocatableSuperReg(unsigned Reg) const; + /// SRInfo - Spill / restore info. struct SRInfo { int index; @@ -326,40 +433,48 @@ 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. + void handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, + const TargetRegisterClass* rc, + std::vector &NewLIs); + + /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of + /// interval on to-be re-materialized operands of MI) with new register. + void rewriteImplicitOps(const LiveInterval &li, + MachineInstr *MI, unsigned NewVReg, VirtRegMap &vrm); /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper /// functions for addIntervalsForSpills to rewrite uses / defs for the given /// live range. - bool rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit, - unsigned id, unsigned index, unsigned end, MachineInstr *MI, + bool rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, + bool TrySplit, unsigned index, unsigned end, MachineInstr *MI, MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot, bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, - VirtRegMap &vrm, MachineRegisterInfo &RegMap, - const TargetRegisterClass* rc, - SmallVector &ReMatIds, - unsigned &NewVReg, bool &HasDef, bool &HasUse, - const MachineLoopInfo *loopInfo, - std::map &MBBVRegsMap, - std::vector &NewLIs); + VirtRegMap &vrm, const TargetRegisterClass* rc, + SmallVector &ReMatIds, const MachineLoopInfo *loopInfo, + unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, + DenseMap &MBBVRegsMap, + std::vector &NewLIs, float &SSWeight); 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, MachineRegisterInfo &RegMap, - const TargetRegisterClass* rc, + 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, - std::vector &NewLIs); + DenseMap > &RestoreIdxes, + DenseMap &MBBVRegsMap, + std::vector &NewLIs, float &SSWeight); - static LiveInterval createInterval(unsigned Reg); + static LiveInterval* createInterval(unsigned Reg); void printRegName(unsigned reg) const; };