X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveIntervalAnalysis.h;h=32bf67b8cc0893097f9a0f68595c2d950766fa05;hb=104cf9e02b0ed94d4173869a598af6c6972a8660;hp=e62c31d4e6f73e90b790e77954ac78dd142ded72;hpb=f522068412218cd14b2c2df74a3437717d255381;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index e62c31d4e6f..32bf67b8cc0 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -79,7 +79,7 @@ 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; @@ -88,24 +88,18 @@ namespace llvm { 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(&ID) {} - struct InstrSlots { - enum { - LOAD = 0, - USE = 1, - DEF = 2, - STORE = 3, - NUM = 4 - }; - }; - static unsigned getBaseIndex(unsigned index) { return index - (index % InstrSlots::NUM); } @@ -204,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; @@ -219,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 @@ -238,6 +283,10 @@ namespace llvm { 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. @@ -252,9 +301,9 @@ namespace llvm { 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); } @@ -308,19 +357,18 @@ namespace llvm { std::vector addIntervalsForSpills(const LiveInterval& i, SmallVectorImpl &SpillIs, - const MachineLoopInfo *loopInfo, VirtRegMap& vrm, - float &SSWeight); + 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, float& SSWeight); + 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 @@ -330,6 +378,11 @@ namespace llvm { 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. unsigned getRepresentativeReg(unsigned Reg) const; @@ -339,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(); @@ -413,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; @@ -458,7 +519,7 @@ namespace llvm { SmallVector &ReMatIds, const MachineLoopInfo *loopInfo, unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, DenseMap &MBBVRegsMap, - std::vector &NewLIs, float &SSWeight); + std::vector &NewLIs); void rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, LiveInterval::Ranges::const_iterator &I, MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot, @@ -470,7 +531,7 @@ namespace llvm { BitVector &RestoreMBBs, DenseMap > &RestoreIdxes, DenseMap &MBBVRegsMap, - std::vector &NewLIs, float &SSWeight); + std::vector &NewLIs); static LiveInterval* createInterval(unsigned Reg);