X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveIntervalAnalysis.h;h=b421753dd5368c2784e13f0e65fe7170a9b5af22;hb=afac0478f41b0f0106a6470060ad22d2eec32e22;hp=3492168774baed7dec0e626298cab6e53936ac27;hpb=c4a2715a548cc150064db162bd18bee1f10cb300;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 3492168774b..b421753dd53 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -20,12 +20,13 @@ #ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H #define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H +#include "llvm/Target/TargetRegisterInfo.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/LiveInterval.h" #include "llvm/CodeGen/SlotIndexes.h" #include "llvm/ADT/BitVector.h" -#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/IndexedMap.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Support/Allocator.h" @@ -35,7 +36,9 @@ namespace llvm { class AliasAnalysis; + class LiveRangeCalc; class LiveVariables; + class MachineDominatorTree; class MachineLoopInfo; class TargetRegisterInfo; class MachineRegisterInfo; @@ -44,96 +47,91 @@ namespace llvm { class VirtRegMap; class LiveIntervals : public MachineFunctionPass { - MachineFunction* mf_; - MachineRegisterInfo* mri_; - const TargetMachine* tm_; - const TargetRegisterInfo* tri_; - const TargetInstrInfo* tii_; - AliasAnalysis *aa_; - LiveVariables* lv_; - SlotIndexes* indexes_; + MachineFunction* MF; + MachineRegisterInfo* MRI; + const TargetMachine* TM; + const TargetRegisterInfo* TRI; + const TargetInstrInfo* TII; + AliasAnalysis *AA; + LiveVariables* LV; + SlotIndexes* Indexes; + MachineDominatorTree *DomTree; + LiveRangeCalc *LRCalc; /// Special pool allocator for VNInfo's (LiveInterval val#). /// VNInfo::Allocator VNInfoAllocator; - typedef DenseMap Reg2IntervalMap; - Reg2IntervalMap r2iMap_; + /// Live interval pointers for all the virtual registers. + IndexedMap VirtRegIntervals; - /// allocatableRegs_ - A bit vector of allocatable registers. - BitVector allocatableRegs_; + /// RegMaskSlots - Sorted list of instructions with register mask operands. + /// Always use the 'r' slot, RegMasks are normal clobbers, not early + /// clobbers. + SmallVector RegMaskSlots; + + /// RegMaskBits - This vector is parallel to RegMaskSlots, it holds a + /// pointer to the corresponding register mask. This pointer can be + /// recomputed as: + /// + /// MI = Indexes->getInstructionFromIndex(RegMaskSlot[N]); + /// unsigned OpNum = findRegMaskOperand(MI); + /// RegMaskBits[N] = MI->getOperand(OpNum).getRegMask(); + /// + /// This is kept in a separate vector partly because some standard + /// libraries don't support lower_bound() with mixed objects, partly to + /// improve locality when searching in RegMaskSlots. + /// Also see the comment in LiveInterval::find(). + SmallVector RegMaskBits; + + /// For each basic block number, keep (begin, size) pairs indexing into the + /// RegMaskSlots and RegMaskBits arrays. + /// Note that basic block numbers may not be layout contiguous, that's why + /// we can't just keep track of the first register mask in each basic + /// block. + SmallVector, 8> RegMaskBlocks; + + /// RegUnitIntervals - Keep a live interval for each register unit as a way + /// of tracking fixed physreg interference. + SmallVector RegUnitIntervals; public: static char ID; // Pass identification, replacement for typeid - LiveIntervals() : MachineFunctionPass(ID) { - initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); - } + LiveIntervals(); + virtual ~LiveIntervals(); // Calculate the spill weight to assign to a single instruction. static float getSpillWeight(bool isDef, bool isUse, unsigned 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; + LiveInterval &getInterval(unsigned Reg) { + LiveInterval *LI = VirtRegIntervals[Reg]; + assert(LI && "Interval does not exist for virtual register"); + return *LI; } - bool hasInterval(unsigned reg) const { - return r2iMap_.count(reg); + const LiveInterval &getInterval(unsigned Reg) const { + return const_cast(this)->getInterval(Reg); } - /// isAllocatable - is the physical register reg allocatable in the current - /// function? - bool isAllocatable(unsigned reg) const { - return allocatableRegs_.test(reg); + bool hasInterval(unsigned Reg) const { + return VirtRegIntervals.inBounds(Reg) && VirtRegIntervals[Reg]; } - /// 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 * I.getSize()) / indexes_->getIndexesLength(); + // Interval creation. + LiveInterval &getOrCreateInterval(unsigned Reg) { + if (!hasInterval(Reg)) { + VirtRegIntervals.grow(Reg); + VirtRegIntervals[Reg] = createInterval(Reg); + } + return getInterval(Reg); } - /// getFuncInstructionCount - Return the number of instructions in the - /// current function. - unsigned getFuncInstructionCount() { - return indexes_->getFunctionSize(); - } - - /// 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 * indexes_->getFunctionSize()); - } - - // 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; + // Interval removal. + void removeInterval(unsigned Reg) { + delete VirtRegIntervals[Reg]; + VirtRegIntervals[Reg] = 0; } - /// 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, @@ -149,42 +147,58 @@ namespace llvm { bool shrinkToUses(LiveInterval *li, SmallVectorImpl *dead = 0); - // Interval removal + /// extendToIndices - Extend the live range of LI to reach all points in + /// Indices. The points in the Indices array must be jointly dominated by + /// existing defs in LI. PHI-defs are added as needed to maintain SSA form. + /// + /// If a SlotIndex in Indices is the end index of a basic block, LI will be + /// extended to be live out of the basic block. + /// + /// See also LiveRangeCalc::extend(). + void extendToIndices(LiveInterval *LI, ArrayRef Indices); - void removeInterval(unsigned Reg) { - DenseMap::iterator I = r2iMap_.find(Reg); - delete I->second; - r2iMap_.erase(I); - } + /// pruneValue - If an LI value is live at Kill, prune its live range by + /// removing any liveness reachable from Kill. Add live range end points to + /// EndPoints such that extendToIndices(LI, EndPoints) will reconstruct the + /// value's live range. + /// + /// Calling pruneValue() and extendToIndices() can be used to reconstruct + /// SSA form after adding defs to a virtual register. + void pruneValue(LiveInterval *LI, SlotIndex Kill, + SmallVectorImpl *EndPoints); SlotIndexes *getSlotIndexes() const { - return indexes_; + return Indexes; + } + + AliasAnalysis *getAliasAnalysis() const { + return AA; } /// isNotInMIMap - returns true if the specified machine instr has been /// removed or was never entered in the map. bool isNotInMIMap(const MachineInstr* Instr) const { - return !indexes_->hasIndex(Instr); + return !Indexes->hasIndex(Instr); } /// Returns the base index of the given instruction. SlotIndex getInstructionIndex(const MachineInstr *instr) const { - return indexes_->getInstructionIndex(instr); + return Indexes->getInstructionIndex(instr); } /// Returns the instruction associated with the given index. MachineInstr* getInstructionFromIndex(SlotIndex index) const { - return indexes_->getInstructionFromIndex(index); + return Indexes->getInstructionFromIndex(index); } /// Return the first index in the given basic block. SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const { - return indexes_->getMBBStartIdx(mbb); + return Indexes->getMBBStartIdx(mbb); } /// Return the last index in the given basic block. SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const { - return indexes_->getMBBEndIdx(mbb); + return Indexes->getMBBEndIdx(mbb); } bool isLiveInToMBB(const LiveInterval &li, @@ -192,48 +206,30 @@ namespace llvm { return li.liveAt(getMBBStartIdx(mbb)); } - LiveRange* findEnteringRange(LiveInterval &li, - const MachineBasicBlock *mbb) { - return li.getLiveRangeContaining(getMBBStartIdx(mbb)); - } - bool isLiveOutOfMBB(const LiveInterval &li, const MachineBasicBlock *mbb) const { return li.liveAt(getMBBEndIdx(mbb).getPrevSlot()); } - LiveRange* findExitingRange(LiveInterval &li, - const MachineBasicBlock *mbb) { - return li.getLiveRangeContaining(getMBBEndIdx(mbb).getPrevSlot()); - } - MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { - return indexes_->getMBBFromIndex(index); + return Indexes->getMBBFromIndex(index); } SlotIndex InsertMachineInstrInMaps(MachineInstr *MI) { - return indexes_->insertMachineInstrInMaps(MI); + return Indexes->insertMachineInstrInMaps(MI); } void RemoveMachineInstrFromMaps(MachineInstr *MI) { - indexes_->removeMachineInstrFromMaps(MI); + Indexes->removeMachineInstrFromMaps(MI); } void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) { - indexes_->replaceMachineInstrInMaps(MI, NewMI); - } - - void InsertMBBInMaps(MachineBasicBlock *MBB) { - indexes_->insertMBBInMaps(MBB); + Indexes->replaceMachineInstrInMaps(MI, NewMI); } bool findLiveInMBBs(SlotIndex Start, SlotIndex End, SmallVectorImpl &MBBs) const { - return indexes_->findLiveInMBBs(Start, End, MBBs); - } - - void renumber() { - indexes_->renumberIndexes(); + return Indexes->findLiveInMBBs(Start, End, MBBs); } VNInfo::Allocator& getVNInfoAllocator() { return VNInfoAllocator; } @@ -247,33 +243,122 @@ namespace llvm { /// print - Implement the dump method. virtual void print(raw_ostream &O, const Module* = 0) const; - /// 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, - const SmallVectorImpl *SpillIs, - bool &isLoad); + /// intervalIsInOneMBB - If LI is confined to a single basic block, return + /// a pointer to that block. If LI is live in to or out of any block, + /// return NULL. + MachineBasicBlock *intervalIsInOneMBB(const LiveInterval &LI) const; - /// intervalIsInOneMBB - Returns true if the specified interval is entirely - /// within a single basic block. - bool intervalIsInOneMBB(const LiveInterval &li) const; + /// Returns true if VNI is killed by any PHI-def values in LI. + /// This may conservatively return true to avoid expensive computations. + bool hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const; /// addKillFlags - Add kill flags to any instruction that kills a virtual /// register. - void addKillFlags(); + void addKillFlags(const VirtRegMap*); + + /// handleMove - call this method to notify LiveIntervals that + /// instruction 'mi' has been moved within a basic block. This will update + /// the live intervals for all operands of mi. Moves between basic blocks + /// are not supported. + /// + /// \param UpdateFlags Update live intervals for nonallocatable physregs. + void handleMove(MachineInstr* MI, bool UpdateFlags = false); + + /// moveIntoBundle - Update intervals for operands of MI so that they + /// begin/end on the SlotIndex for BundleStart. + /// + /// \param UpdateFlags Update live intervals for nonallocatable physregs. + /// + /// Requires MI and BundleStart to have SlotIndexes, and assumes + /// existing liveness is accurate. BundleStart should be the first + /// instruction in the Bundle. + void handleMoveIntoBundle(MachineInstr* MI, MachineInstr* BundleStart, + bool UpdateFlags = false); + + // Register mask functions. + // + // Machine instructions may use a register mask operand to indicate that a + // large number of registers are clobbered by the instruction. This is + // typically used for calls. + // + // For compile time performance reasons, these clobbers are not recorded in + // the live intervals for individual physical registers. Instead, + // LiveIntervalAnalysis maintains a sorted list of instructions with + // register mask operands. + + /// getRegMaskSlots - Returns a sorted array of slot indices of all + /// instructions with register mask operands. + ArrayRef getRegMaskSlots() const { return RegMaskSlots; } + + /// getRegMaskSlotsInBlock - Returns a sorted array of slot indices of all + /// instructions with register mask operands in the basic block numbered + /// MBBNum. + ArrayRef getRegMaskSlotsInBlock(unsigned MBBNum) const { + std::pair P = RegMaskBlocks[MBBNum]; + return getRegMaskSlots().slice(P.first, P.second); + } + + /// getRegMaskBits() - Returns an array of register mask pointers + /// corresponding to getRegMaskSlots(). + ArrayRef getRegMaskBits() const { return RegMaskBits; } - /// moveInstr - Move MachineInstr mi to insertPt, updating the live - /// intervals of mi's operands to reflect the new position. The insertion - /// point can be above or below mi, but must be in the same basic block. - void moveInstr(MachineBasicBlock::iterator insertPt, MachineInstr* mi); + /// getRegMaskBitsInBlock - Returns an array of mask pointers corresponding + /// to getRegMaskSlotsInBlock(MBBNum). + ArrayRef getRegMaskBitsInBlock(unsigned MBBNum) const { + std::pair P = RegMaskBlocks[MBBNum]; + return getRegMaskBits().slice(P.first, P.second); + } + + /// checkRegMaskInterference - Test if LI is live across any register mask + /// instructions, and compute a bit mask of physical registers that are not + /// clobbered by any of them. + /// + /// Returns false if LI doesn't cross any register mask instructions. In + /// that case, the bit vector is not filled in. + bool checkRegMaskInterference(LiveInterval &LI, + BitVector &UsableRegs); + + // Register unit functions. + // + // Fixed interference occurs when MachineInstrs use physregs directly + // instead of virtual registers. This typically happens when passing + // arguments to a function call, or when instructions require operands in + // fixed registers. + // + // Each physreg has one or more register units, see MCRegisterInfo. We + // track liveness per register unit to handle aliasing registers more + // efficiently. + + /// getRegUnit - Return the live range for Unit. + /// It will be computed if it doesn't exist. + LiveInterval &getRegUnit(unsigned Unit) { + LiveInterval *LI = RegUnitIntervals[Unit]; + if (!LI) { + // Compute missing ranges on demand. + RegUnitIntervals[Unit] = LI = new LiveInterval(Unit, HUGE_VALF); + computeRegUnitInterval(LI); + } + return *LI; + } + + /// getCachedRegUnit - Return the live range for Unit if it has already + /// been computed, or NULL if it hasn't been computed yet. + LiveInterval *getCachedRegUnit(unsigned Unit) { + return RegUnitIntervals[Unit]; + } private: /// computeIntervals - Compute live intervals. void computeIntervals(); + /// Compute live intervals for all virtual registers. + void computeVirtRegs(); + + /// Compute RegMaskSlots and RegMaskBits. + void computeRegMasks(); + /// handleRegisterDef - update intervals for a register def - /// (calls handlePhysicalRegisterDef and - /// handleVirtualRegisterDef) + /// (calls handleVirtualRegisterDef) void handleRegisterDef(MachineBasicBlock *MBB, MachineBasicBlock::iterator MI, SlotIndex MIIdx, @@ -293,43 +378,16 @@ namespace llvm { unsigned MOIdx, LiveInterval& interval); - /// handlePhysicalRegisterDef - update intervals for a physical register - /// def. - void handlePhysicalRegisterDef(MachineBasicBlock* mbb, - MachineBasicBlock::iterator mi, - SlotIndex MIIdx, MachineOperand& MO, - LiveInterval &interval, - MachineInstr *CopyMI); - - /// handleLiveInRegister - Create interval for a livein register. - void handleLiveInRegister(MachineBasicBlock* mbb, - SlotIndex 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, - SlotIndex 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, - const SmallVectorImpl *SpillIs, - bool &isLoad); - static LiveInterval* createInterval(unsigned Reg); void printInstrs(raw_ostream &O) const; void dumpInstrs() const; + + void computeLiveInRegUnits(); + void computeRegUnitInterval(LiveInterval*); + void computeVirtRegInterval(LiveInterval*); + + class HMEditor; }; } // End llvm namespace