X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveIntervalAnalysis.h;h=32bf67b8cc0893097f9a0f68595c2d950766fa05;hb=104cf9e02b0ed94d4173869a598af6c6972a8660;hp=a3612b13aa21d31e1a3f46728bdd3dbcdb6c429a;hpb=49bfdd63f481237fa7305525517ea0dc9e1bd23c;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index a3612b13aa2..32bf67b8cc0 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -28,7 +28,6 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/Support/Allocator.h" #include -#include namespace llvm { @@ -55,7 +54,7 @@ namespace llvm { return LHS.first < RHS.first; } }; - + class LiveIntervals : public MachineFunctionPass { MachineFunction* mf_; MachineRegisterInfo* mri_; @@ -80,32 +79,26 @@ namespace llvm { /// FunctionSize - The number of instructions present in the function uint64_t FunctionSize; - typedef DenseMap Mi2IndexMap; + typedef DenseMap Mi2IndexMap; Mi2IndexMap mi2iMap_; typedef std::vector Index2MiMap; Index2MiMap i2miMap_; - typedef std::map Reg2IntervalMap; + typedef DenseMap Reg2IntervalMap; Reg2IntervalMap r2iMap_; + DenseMap terminatorGaps; + BitVector allocatableRegs_; std::vector ClonedMIs; + typedef LiveInterval::InstrSlots InstrSlots; + 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 - }; - }; + LiveIntervals() : MachineFunctionPass(&ID) {} static unsigned getBaseIndex(unsigned index) { return index - (index % InstrSlots::NUM); @@ -141,13 +134,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 { @@ -205,7 +198,7 @@ namespace llvm { } /// getInstructionIndex - returns the base index of instr - unsigned getInstructionIndex(MachineInstr* instr) const { + unsigned getInstructionIndex(const MachineInstr* instr) const { Mi2IndexMap::const_iterator it = mi2iMap_.find(instr); assert(it != mi2iMap_.end() && "Invalid instruction!"); return it->second; @@ -220,15 +213,66 @@ namespace llvm { return i2miMap_[index]; } + /// hasGapBeforeInstr - Return true if the previous instruction slot, + /// i.e. Index - InstrSlots::NUM, is not occupied. + bool hasGapBeforeInstr(unsigned Index) { + Index = getBaseIndex(Index - InstrSlots::NUM); + return getInstructionFromIndex(Index) == 0; + } + + /// hasGapAfterInstr - Return true if the successive instruction slot, + /// i.e. Index + InstrSlots::Num, is not occupied. + bool hasGapAfterInstr(unsigned Index) { + Index = getBaseIndex(Index + InstrSlots::NUM); + return getInstructionFromIndex(Index) == 0; + } + + /// findGapBeforeInstr - Find an empty instruction slot before the + /// specified index. If "Furthest" is true, find one that's furthest + /// away from the index (but before any index that's occupied). + unsigned findGapBeforeInstr(unsigned Index, bool Furthest = false) { + Index = getBaseIndex(Index - InstrSlots::NUM); + if (getInstructionFromIndex(Index)) + return 0; // No gap! + if (!Furthest) + return Index; + unsigned PrevIndex = getBaseIndex(Index - InstrSlots::NUM); + while (getInstructionFromIndex(Index)) { + Index = PrevIndex; + PrevIndex = getBaseIndex(Index - InstrSlots::NUM); + } + return Index; + } + + /// InsertMachineInstrInMaps - Insert the specified machine instruction + /// into the instruction index map at the given index. + void InsertMachineInstrInMaps(MachineInstr *MI, unsigned Index) { + i2miMap_[Index / InstrSlots::NUM] = MI; + Mi2IndexMap::iterator it = mi2iMap_.find(MI); + assert(it == mi2iMap_.end() && "Already in map!"); + mi2iMap_[MI] = 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); + /// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except + /// it can check use as well. + bool conflictsWithPhysRegRef(LiveInterval &li, unsigned Reg, + bool CheckUse, + SmallPtrSet &JoinedCopies); + /// 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 /// in which the value is live. - bool findLiveInMBBs(const LiveRange &LR, + bool findLiveInMBBs(unsigned Start, unsigned End, + SmallVectorImpl &MBBs) const; + + /// findReachableMBBs - Return a list MBB that can be reached via any + /// branch or fallthroughs. Return true if the list is not empty. + bool findReachableMBBs(unsigned Start, unsigned End, SmallVectorImpl &MBBs) const; // Interval creation @@ -236,9 +280,13 @@ 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; } + + /// dupInterval - Duplicate a live interval. The caller is responsible for + /// managing the allocated memory. + LiveInterval *dupInterval(LiveInterval *li); /// addLiveRangeToEndOfBlock - Given a register and an instruction, /// adds a live range from that instruction to the end of its MBB. @@ -248,12 +296,14 @@ 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 - /// removed. - bool isRemoved(MachineInstr* instr) const { + /// isNotInMIMap - returns true if the specified machine instr has been + /// removed or was never entered in the map. + bool isNotInMIMap(MachineInstr* instr) const { return !mi2iMap_.count(instr); } @@ -306,18 +356,32 @@ namespace llvm { /// (if any is created) by reference. This is temporary. std::vector addIntervalsForSpills(const LiveInterval& i, - const MachineLoopInfo *loopInfo, VirtRegMap& vrm, - float &SSWeight); + SmallVectorImpl &SpillIs, + const MachineLoopInfo *loopInfo, VirtRegMap& vrm); + + /// addIntervalsForSpillsFast - Quickly create new intervals for spilled + /// defs / uses without remat or splitting. + std::vector + addIntervalsForSpillsFast(const LiveInterval &li, + const MachineLoopInfo *loopInfo, VirtRegMap &vrm); /// spillPhysRegAroundRegDefsUses - Spill the specified physical register - /// around all defs and uses of the specified interval. - void spillPhysRegAroundRegDefsUses(const LiveInterval &li, + /// around all defs and uses of the specified interval. Return true if it + /// was able to cut its interval. + bool 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); + bool isReMaterializable(const LiveInterval &li, + SmallVectorImpl &SpillIs, + bool &isLoad); + + /// 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); /// getRepresentativeReg - Find the largest super register of the specified /// physical register. @@ -328,9 +392,21 @@ namespace llvm { unsigned getNumConflictsWithPhysReg(const LiveInterval &li, unsigned PhysReg) const; + /// processImplicitDefs - Process IMPLICIT_DEF instructions. Add isUndef + /// marker to implicit_def defs and their uses. + void processImplicitDefs(); + /// computeNumbering - Compute the index numbering. void computeNumbering(); + /// scaleNumbering - Rescale interval numbers to introduce gaps for new + /// instructions + void scaleNumbering(int factor); + + /// intervalIsInOneMBB - Returns true if the specified interval is entirely + /// within a single basic block. + bool intervalIsInOneMBB(const LiveInterval &li) const; + private: /// computeIntervals - Compute live intervals. void computeIntervals(); @@ -378,7 +454,9 @@ namespace llvm { /// val# of the specified interval is re-materializable. Also returns true /// by reference if the def is a load. bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo, - MachineInstr *MI, bool &isLoad); + MachineInstr *MI, + SmallVectorImpl &SpillIs, + bool &isLoad); /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from /// slot / to reg or any rematerialized load into ith operand of specified @@ -400,10 +478,6 @@ namespace llvm { bool anyKillInMBBAfterIdx(const LiveInterval &li, const VNInfo *VNI, MachineBasicBlock *MBB, unsigned Idx) const; - /// intervalIsInOneMBB - Returns true if the specified interval is entirely - /// 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; @@ -418,10 +492,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. @@ -444,8 +518,8 @@ namespace llvm { VirtRegMap &vrm, const TargetRegisterClass* rc, SmallVector &ReMatIds, const MachineLoopInfo *loopInfo, unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, - std::map &MBBVRegsMap, - std::vector &NewLIs, float &SSWeight); + DenseMap &MBBVRegsMap, + std::vector &NewLIs); void rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, LiveInterval::Ranges::const_iterator &I, MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot, @@ -453,13 +527,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, - std::vector &NewLIs, float &SSWeight); + DenseMap > &RestoreIdxes, + DenseMap &MBBVRegsMap, + std::vector &NewLIs); - static LiveInterval createInterval(unsigned Reg); + static LiveInterval* createInterval(unsigned Reg); void printRegName(unsigned reg) const; };