X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveIntervalAnalysis.h;h=f9bd31754da9bd491e8efacd926aec3aa2170cf9;hb=cfe761c9e6cf97dc804725df08247b9402085f84;hp=3492168774baed7dec0e626298cab6e53936ac27;hpb=c4a2715a548cc150064db162bd18bee1f10cb300;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 3492168774b..f9bd31754da 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -17,127 +17,132 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H -#define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H +#ifndef LLVM_CODEGEN_LIVEINTERVALANALYSIS_H +#define LLVM_CODEGEN_LIVEINTERVALANALYSIS_H +#include "llvm/ADT/IndexedMap.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/CodeGen/LiveInterval.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/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.h" #include "llvm/Support/Allocator.h" +#include "llvm/Target/TargetRegisterInfo.h" #include #include namespace llvm { class AliasAnalysis; + class BitVector; + class BlockFrequency; + class LiveRangeCalc; class LiveVariables; + class MachineDominatorTree; class MachineLoopInfo; class TargetRegisterInfo; class MachineRegisterInfo; class TargetInstrInfo; class TargetRegisterClass; class VirtRegMap; + class MachineBlockFrequencyInfo; 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 TargetRegisterInfo* TRI; + const TargetInstrInfo* TII; + AliasAnalysis *AA; + 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; + + /// Keeps a live range set for each register unit to track fixed physreg + /// interference. + SmallVector RegUnitRanges; 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; + static float getSpillWeight(bool isDef, bool isUse, + const MachineBlockFrequencyInfo *MBFI, + const MachineInstr *Instr); + + LiveInterval &getInterval(unsigned Reg) { + if (hasInterval(Reg)) + return *VirtRegIntervals[Reg]; + else + return createAndComputeVirtRegInterval(Reg); } - 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 &createEmptyInterval(unsigned Reg) { + assert(!hasInterval(Reg) && "Interval already exists!"); + VirtRegIntervals.grow(Reg); + VirtRegIntervals[Reg] = createInterval(Reg); + return *VirtRegIntervals[Reg]; } - /// getFuncInstructionCount - Return the number of instructions in the - /// current function. - unsigned getFuncInstructionCount() { - return indexes_->getFunctionSize(); + LiveInterval &createAndComputeVirtRegInterval(unsigned Reg) { + LiveInterval &LI = createEmptyInterval(Reg); + computeVirtRegInterval(LI); + return LI; } - /// 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] = nullptr; } - /// 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); + /// Given a register and an instruction, adds a live segment from that + /// instruction to the end of its MBB. + LiveInterval::Segment addSegmentToEndOfBlock(unsigned reg, + MachineInstr* startInst); /// shrinkToUses - After removing some uses of a register, shrink its live /// range to just the remaining uses. This method does not compute reaching @@ -147,189 +152,268 @@ namespace llvm { /// Return true if the interval may have been separated into multiple /// connected components. bool shrinkToUses(LiveInterval *li, - SmallVectorImpl *dead = 0); + SmallVectorImpl *dead = nullptr); + + /// \brief Walk the values in the given interval and compute which ones + /// are dead. Dead values are not deleted, however: + /// - Dead PHIDef values are marked as unused. + /// - New dead machine instructions are added to the dead vector. + /// - CanSeparate is set to true if the interval may have been separated + /// into multiple connected components. + void computeDeadValues(LiveInterval *li, + LiveRange &LR, + bool *CanSeparate, + SmallVectorImpl *dead); + + /// 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(LiveRange &LR, ArrayRef Indices); - // Interval removal + /// 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); - void removeInterval(unsigned Reg) { - DenseMap::iterator I = r2iMap_.find(Reg); - delete I->second; - r2iMap_.erase(I); + SlotIndexes *getSlotIndexes() const { + return Indexes; } - SlotIndexes *getSlotIndexes() const { - 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, + bool isLiveInToMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const { - return li.liveAt(getMBBStartIdx(mbb)); - } - - LiveRange* findEnteringRange(LiveInterval &li, - const MachineBasicBlock *mbb) { - return li.getLiveRangeContaining(getMBBStartIdx(mbb)); + return LR.liveAt(getMBBStartIdx(mbb)); } - bool isLiveOutOfMBB(const LiveInterval &li, + bool isLiveOutOfMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const { - return li.liveAt(getMBBEndIdx(mbb).getPrevSlot()); + return LR.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); } - MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { - return indexes_->getMBBFromIndex(index); + void insertMBBInMaps(MachineBasicBlock *MBB) { + Indexes->insertMBBInMaps(MBB); + assert(unsigned(MBB->getNumber()) == RegMaskBlocks.size() && + "Blocks must be added in order."); + RegMaskBlocks.push_back(std::make_pair(RegMaskSlots.size(), 0)); } SlotIndex InsertMachineInstrInMaps(MachineInstr *MI) { - return indexes_->insertMachineInstrInMaps(MI); + return Indexes->insertMachineInstrInMaps(MI); } - void RemoveMachineInstrFromMaps(MachineInstr *MI) { - indexes_->removeMachineInstrFromMaps(MI); + void InsertMachineInstrRangeInMaps(MachineBasicBlock::iterator B, + MachineBasicBlock::iterator E) { + for (MachineBasicBlock::iterator I = B; I != E; ++I) + Indexes->insertMachineInstrInMaps(I); } - void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) { - indexes_->replaceMachineInstrInMaps(MI, NewMI); + void RemoveMachineInstrFromMaps(MachineInstr *MI) { + Indexes->removeMachineInstrFromMaps(MI); } - void InsertMBBInMaps(MachineBasicBlock *MBB) { - indexes_->insertMBBInMaps(MBB); + void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) { + 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; } - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual void releaseMemory(); + void getAnalysisUsage(AnalysisUsage &AU) const override; + void releaseMemory() override; /// runOnMachineFunction - pass entry point - virtual bool runOnMachineFunction(MachineFunction&); + bool runOnMachineFunction(MachineFunction&) override; /// print - Implement the dump method. - virtual void print(raw_ostream &O, const Module* = 0) const; + void print(raw_ostream &O, const Module* = nullptr) const override; - /// 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); + + /// repairIntervalsInRange - Update live intervals for instructions in a + /// range of iterators. It is intended for use after target hooks that may + /// insert or remove instructions, and is only efficient for a small number + /// of instructions. + /// + /// OrigRegs is a vector of registers that were originally used by the + /// instructions in the range between the two iterators. + /// + /// Currently, the only only changes that are supported are simple removal + /// and addition of uses. + void repairIntervalsInRange(MachineBasicBlock *MBB, + MachineBasicBlock::iterator Begin, + MachineBasicBlock::iterator End, + ArrayRef OrigRegs); + + // 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); + } - /// 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); + /// getRegMaskBits() - Returns an array of register mask pointers + /// corresponding to getRegMaskSlots(). + ArrayRef getRegMaskBits() const { return RegMaskBits; } + + /// 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. + LiveRange &getRegUnit(unsigned Unit) { + LiveRange *LR = RegUnitRanges[Unit]; + if (!LR) { + // Compute missing ranges on demand. + RegUnitRanges[Unit] = LR = new LiveRange(); + computeRegUnitRange(*LR, Unit); + } + return *LR; + } + + /// getCachedRegUnit - Return the live range for Unit if it has already + /// been computed, or NULL if it hasn't been computed yet. + LiveRange *getCachedRegUnit(unsigned Unit) { + return RegUnitRanges[Unit]; + } + + const LiveRange *getCachedRegUnit(unsigned Unit) const { + return RegUnitRanges[Unit]; + } 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, - SlotIndex MIIdx, - MachineOperand& MO, unsigned MOIdx); - - /// isPartialRedef - Return true if the specified def at the specific index - /// is partially re-defining the specified live interval. A common case of - /// this is a definition of the sub-register. - bool isPartialRedef(SlotIndex MIIdx, MachineOperand &MO, - LiveInterval &interval); - - /// handleVirtualRegisterDef - update intervals for a virtual - /// register def - void handleVirtualRegisterDef(MachineBasicBlock *MBB, - MachineBasicBlock::iterator MI, - SlotIndex MIIdx, MachineOperand& MO, - 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); + /// Compute live intervals for all virtual registers. + void computeVirtRegs(); + + /// Compute RegMaskSlots and RegMaskBits. + void computeRegMasks(); static LiveInterval* createInterval(unsigned Reg); void printInstrs(raw_ostream &O) const; void dumpInstrs() const; + + void computeLiveInRegUnits(); + void computeRegUnitRange(LiveRange&, unsigned Unit); + void computeVirtRegInterval(LiveInterval&); + + class HMEditor; }; } // End llvm namespace