diff options
Diffstat (limited to 'include/llvm/CodeGen/LiveIntervalAnalysis.h')
-rw-r--r-- | include/llvm/CodeGen/LiveIntervalAnalysis.h | 537 |
1 files changed, 537 insertions, 0 deletions
diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h new file mode 100644 index 0000000000000..7c44cc7dbf28a --- /dev/null +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -0,0 +1,537 @@ +//===-- LiveIntervalAnalysis.h - Live Interval Analysis ---------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// 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' 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). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H +#define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H + +#include "llvm/CodeGen/MachineFunctionPass.h" +#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 <cmath> + +namespace llvm { + + class AliasAnalysis; + class LiveVariables; + class MachineLoopInfo; + class TargetRegisterInfo; + class MachineRegisterInfo; + class TargetInstrInfo; + class TargetRegisterClass; + class VirtRegMap; + typedef std::pair<unsigned, MachineBasicBlock*> 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; + } + }; + + 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#). + /// + BumpPtrAllocator VNInfoAllocator; + + /// MBB2IdxMap - The indexes of the first and last instructions in the + /// specified basic block. + std::vector<std::pair<unsigned, unsigned> > MBB2IdxMap; + + /// Idx2MBBMap - Sorted list of pairs of index of first instruction + /// and MBB id. + std::vector<IdxMBBPair> Idx2MBBMap; + + /// FunctionSize - The number of instructions present in the function + uint64_t FunctionSize; + + typedef DenseMap<MachineInstr*, unsigned> Mi2IndexMap; + Mi2IndexMap mi2iMap_; + + typedef std::vector<MachineInstr*> Index2MiMap; + Index2MiMap i2miMap_; + + typedef DenseMap<unsigned, LiveInterval*> Reg2IntervalMap; + Reg2IntervalMap r2iMap_; + + BitVector allocatableRegs_; + + std::vector<MachineInstr*> ClonedMIs; + + typedef LiveInterval::InstrSlots InstrSlots; + + public: + static char ID; // Pass identification, replacement for typeid + LiveIntervals() : MachineFunctionPass(&ID) {} + + 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 (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; + } + + 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; + } + + /// 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<IdxMBBPair>::const_iterator I = + std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), index); + // Take the pair containing the index + std::vector<IdxMBBPair>::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); + 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]; + } + + /// 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<MachineInstr*,32> &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(unsigned Start, unsigned End, + SmallVectorImpl<MachineBasicBlock*> &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<MachineBasicBlock*> &MBBs) const; + + // Interval creation + + LiveInterval &getOrCreateInterval(unsigned reg) { + Reg2IntervalMap::iterator I = r2iMap_.find(reg); + if (I == r2iMap_.end()) + 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. + LiveRange addLiveRangeToEndOfBlock(unsigned reg, + MachineInstr* startInst); + + // Interval removal + + void removeInterval(unsigned Reg) { + DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.find(Reg); + delete I->second; + r2iMap_.erase(I); + } + + /// 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); + } + + /// 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); + } + } + + /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in + /// maps used by register allocator. + void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) { + Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI); + if (mi2i == mi2iMap_.end()) + return; + i2miMap_[mi2i->second/InstrSlots::NUM] = NewMI; + Mi2IndexMap::iterator it = mi2iMap_.find(MI); + assert(it != mi2iMap_.end() && "Invalid instruction!"); + unsigned Index = it->second; + mi2iMap_.erase(it); + mi2iMap_[NewMI] = Index; + } + + BumpPtrAllocator& getVNInfoAllocator() { return VNInfoAllocator; } + + /// getVNInfoSourceReg - Helper function that parses the specified VNInfo + /// copy field and returns the source register that defines it. + unsigned getVNInfoSourceReg(const VNInfo *VNI) const; + + 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. FIXME: It also returns the weight of the spill slot + /// (if any is created) by reference. This is temporary. + std::vector<LiveInterval*> + addIntervalsForSpills(const LiveInterval& i, + SmallVectorImpl<LiveInterval*> &SpillIs, + const MachineLoopInfo *loopInfo, VirtRegMap& vrm); + + /// addIntervalsForSpillsFast - Quickly create new intervals for spilled + /// defs / uses without remat or splitting. + std::vector<LiveInterval*> + addIntervalsForSpillsFast(const LiveInterval &li, + const MachineLoopInfo *loopInfo, VirtRegMap &vrm); + + /// spillPhysRegAroundRegDefsUses - Spill the specified physical register + /// 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, + SmallVectorImpl<LiveInterval*> &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; + + /// 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(); + + /// 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(); + + /// handleRegisterDef - update intervals for a register def + /// (calls handlePhysicalRegisterDef and + /// handleVirtualRegisterDef) + void handleRegisterDef(MachineBasicBlock *MBB, + MachineBasicBlock::iterator MI, unsigned MIIdx, + MachineOperand& MO, unsigned MOIdx); + + /// handleVirtualRegisterDef - update intervals for a virtual + /// register def + void handleVirtualRegisterDef(MachineBasicBlock *MBB, + MachineBasicBlock::iterator MI, + 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, MachineOperand& MO, + LiveInterval &interval, + MachineInstr *CopyMI); + + /// handleLiveInRegister - Create interval for a livein register. + void handleLiveInRegister(MachineBasicBlock* mbb, + 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. + bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo, + MachineInstr *MI, + SmallVectorImpl<LiveInterval*> &SpillIs, + bool &isLoad); + + /// 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 InstrIdx, + SmallVector<unsigned, 2> &Ops, + bool isSS, int Slot, unsigned Reg); + + /// canFoldMemoryOperand - Return true if the specified load / store + /// folding is possible. + bool canFoldMemoryOperand(MachineInstr *MI, + SmallVector<unsigned, 2> &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. + bool anyKillInMBBAfterIdx(const LiveInterval &li, const VNInfo *VNI, + MachineBasicBlock *MBB, unsigned Idx) 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; + unsigned vreg; + bool canFold; + SRInfo(int i, unsigned vr, bool f) : index(i), vreg(vr), canFold(f) {}; + }; + + bool alsoFoldARestore(int Id, int index, unsigned vr, + BitVector &RestoreMBBs, + DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes); + void eraseRestoreInfo(int Id, int index, unsigned vr, + BitVector &RestoreMBBs, + DenseMap<unsigned,std::vector<SRInfo> >&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<LiveInterval*> &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, 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, const TargetRegisterClass* rc, + SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo, + unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, + DenseMap<unsigned,unsigned> &MBBVRegsMap, + std::vector<LiveInterval*> &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, const TargetRegisterClass* rc, + SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo, + BitVector &SpillMBBs, + DenseMap<unsigned,std::vector<SRInfo> > &SpillIdxes, + BitVector &RestoreMBBs, + DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes, + DenseMap<unsigned,unsigned> &MBBVRegsMap, + std::vector<LiveInterval*> &NewLIs); + + static LiveInterval* createInterval(unsigned Reg); + + void printRegName(unsigned reg) const; + }; + +} // End llvm namespace + +#endif |