X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveIntervalAnalysis.h;h=65f36e725666d438da8f6c6ee234468bb0d762e5;hb=5a9462587d2c9b4b70519d8a368f5a61485c1ca3;hp=a94840e89621a39bdb4a9f16ddd2adbca854769f;hpb=289983123ba4170c8a27e9638935818f8142bc89;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index a94840e8962..61c705e04d2 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -17,468 +17,420 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H -#define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H +#ifndef LLVM_CODEGEN_LIVEINTERVALANALYSIS_H +#define LLVM_CODEGEN_LIVEINTERVALANALYSIS_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/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/SlotIndexes.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; - typedef std::pair 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; - } - }; - - // Provide DenseMapInfo for unsigned. - template<> - struct DenseMapInfo { - static inline unsigned getEmptyKey() { return (unsigned)-1; } - static inline unsigned getTombstoneKey() { return (unsigned)-2; } - static unsigned getHashValue(const unsigned Val) { - return Val * 37; - } - static bool isEqual(const unsigned LHS, const unsigned RHS) { - return LHS == RHS; - } - static bool isPod() { return true; } - }; + class MachineBlockFrequencyInfo; class LiveIntervals : public MachineFunctionPass { - MachineFunction* mf_; - MachineRegisterInfo* mri_; - const TargetMachine* tm_; - const TargetRegisterInfo* tri_; - const TargetInstrInfo* tii_; - AliasAnalysis *aa_; - LiveVariables* lv_; + 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#). /// - BumpPtrAllocator VNInfoAllocator; - - /// MBB2IdxMap - The indexes of the first and last instructions in the - /// specified basic block. - std::vector > MBB2IdxMap; + VNInfo::Allocator VNInfoAllocator; - /// Idx2MBBMap - Sorted list of pairs of index of first instruction - /// and MBB id. - std::vector Idx2MBBMap; + /// Live interval pointers for all the virtual registers. + IndexedMap VirtRegIntervals; - /// FunctionSize - The number of instructions present in the function - uint64_t FunctionSize; + /// RegMaskSlots - Sorted list of instructions with register mask operands. + /// Always use the 'r' slot, RegMasks are normal clobbers, not early + /// clobbers. + SmallVector RegMaskSlots; - typedef DenseMap Mi2IndexMap; - Mi2IndexMap mi2iMap_; - - typedef std::vector Index2MiMap; - Index2MiMap i2miMap_; + /// 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; - typedef DenseMap Reg2IntervalMap; - Reg2IntervalMap r2iMap_; + public: + static char ID; // Pass identification, replacement for typeid + LiveIntervals(); + virtual ~LiveIntervals(); + + // Calculate the spill weight to assign to a single instruction. + 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); + } - BitVector allocatableRegs_; + const LiveInterval &getInterval(unsigned Reg) const { + return const_cast(this)->getInterval(Reg); + } - std::vector ClonedMIs; + bool hasInterval(unsigned Reg) const { + return VirtRegIntervals.inBounds(Reg) && VirtRegIntervals[Reg]; + } - 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 - }; - }; - - static unsigned getBaseIndex(unsigned index) { - return index - (index % InstrSlots::NUM); + // Interval creation. + LiveInterval &createEmptyInterval(unsigned Reg) { + assert(!hasInterval(Reg) && "Interval already exists!"); + VirtRegIntervals.grow(Reg); + VirtRegIntervals[Reg] = createInterval(Reg); + return *VirtRegIntervals[Reg]; } - static unsigned getBoundaryIndex(unsigned index) { - return getBaseIndex(index + InstrSlots::NUM - 1); + + LiveInterval &createAndComputeVirtRegInterval(unsigned Reg) { + LiveInterval &LI = createEmptyInterval(Reg); + computeVirtRegInterval(LI); + return LI; } - static unsigned getLoadIndex(unsigned index) { - return getBaseIndex(index) + InstrSlots::LOAD; + + // Interval removal. + void removeInterval(unsigned Reg) { + delete VirtRegIntervals[Reg]; + VirtRegIntervals[Reg] = nullptr; } - static unsigned getUseIndex(unsigned index) { - return getBaseIndex(index) + InstrSlots::USE; + + /// 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 + /// defs for new uses, and it doesn't remove dead defs. + /// Dead PHIDef values are marked as unused. + /// New dead machine instructions are added to the dead vector. + /// Return true if the interval may have been separated into multiple + /// connected components. + bool shrinkToUses(LiveInterval *li, + SmallVectorImpl *dead = nullptr); + + /// Specialized version of + /// shrinkToUses(LiveInterval *li, SmallVectorImpl *dead) + /// that works on a subregister live range and only looks at uses matching + /// the lane mask of the subregister range. + void shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg); + + /// 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); + + + /// If @p LR has a live value at @p 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(LiveRange &LR, SlotIndex Kill, + SmallVectorImpl *EndPoints); + + SlotIndexes *getSlotIndexes() const { + return Indexes; } - static unsigned getDefIndex(unsigned index) { - return getBaseIndex(index) + InstrSlots::DEF; + + AliasAnalysis *getAliasAnalysis() const { + return AA; } - static unsigned getStoreIndex(unsigned index) { - return getBaseIndex(index) + InstrSlots::STORE; + + /// 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); } - static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { - return (isDef + isUse) * powf(10.0F, (float)loopDepth); + /// Returns the base index of the given instruction. + SlotIndex getInstructionIndex(const MachineInstr *instr) const { + return Indexes->getInstructionIndex(instr); } - 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; + /// Returns the instruction associated with the given index. + MachineInstr* getInstructionFromIndex(SlotIndex index) const { + return Indexes->getInstructionFromIndex(index); } - 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 the first index in the given basic block. + SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const { + return Indexes->getMBBStartIdx(mbb); } - bool hasInterval(unsigned reg) const { - return r2iMap_.count(reg); + /// Return the last index in the given basic block. + SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const { + return Indexes->getMBBEndIdx(mbb); } - /// getMBBStartIdx - Return the base index of the first instruction in the - /// specified MachineBasicBlock. - unsigned getMBBStartIdx(MachineBasicBlock *MBB) const { - return getMBBStartIdx(MBB->getNumber()); + bool isLiveInToMBB(const LiveRange &LR, + const MachineBasicBlock *mbb) const { + return LR.liveAt(getMBBStartIdx(mbb)); } - unsigned getMBBStartIdx(unsigned MBBNo) const { - assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!"); - return MBB2IdxMap[MBBNo].first; + + bool isLiveOutOfMBB(const LiveRange &LR, + const MachineBasicBlock *mbb) const { + return LR.liveAt(getMBBEndIdx(mbb).getPrevSlot()); } - /// getMBBEndIdx - Return the store index of the last instruction in the - /// specified MachineBasicBlock. - unsigned getMBBEndIdx(MachineBasicBlock *MBB) const { - return getMBBEndIdx(MBB->getNumber()); + MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { + return Indexes->getMBBFromIndex(index); } - unsigned getMBBEndIdx(unsigned MBBNo) const { - assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!"); - return MBB2IdxMap[MBBNo].second; + + 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)); } - /// 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(); + SlotIndex InsertMachineInstrInMaps(MachineInstr *MI) { + return Indexes->insertMachineInstrInMaps(MI); } - - /// 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); + + void InsertMachineInstrRangeInMaps(MachineBasicBlock::iterator B, + MachineBasicBlock::iterator E) { + for (MachineBasicBlock::iterator I = B; I != E; ++I) + Indexes->insertMachineInstrInMaps(I); } - /// getMBBFromIndex - given an index in any instruction of an - /// MBB return a pointer the MBB - MachineBasicBlock* getMBBFromIndex(unsigned index) const { - std::vector::const_iterator I = - std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), index); - // Take the pair containing the index - std::vector::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; + void RemoveMachineInstrFromMaps(MachineInstr *MI) { + Indexes->removeMachineInstrFromMaps(MI); } - /// 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; + void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) { + Indexes->replaceMachineInstrInMaps(MI, NewMI); } - /// 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]; + bool findLiveInMBBs(SlotIndex Start, SlotIndex End, + SmallVectorImpl &MBBs) const { + return Indexes->findLiveInMBBs(Start, End, MBBs); } - /// 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); + VNInfo::Allocator& getVNInfoAllocator() { return VNInfoAllocator; } + + void getAnalysisUsage(AnalysisUsage &AU) const override; + void releaseMemory() override; - /// 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, - SmallVectorImpl &MBBs) const; + /// runOnMachineFunction - pass entry point + bool runOnMachineFunction(MachineFunction&) override; - // Interval creation + /// print - Implement the dump method. + void print(raw_ostream &O, const Module* = nullptr) const override; - 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; - } - - /// 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); + /// 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; - // Interval removal + /// 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; - void removeInterval(unsigned Reg) { - DenseMap::iterator I = r2iMap_.find(Reg); - delete I->second; - r2iMap_.erase(I); + /// addKillFlags - Add kill flags to any instruction that kills a virtual + /// register. + 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); } - /// isRemoved - returns true if the specified machine instr has been - /// removed. - bool isRemoved(MachineInstr* instr) const { - return !mi2iMap_.count(instr); + /// 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); } - /// 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); + /// 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; } - /// 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; + /// 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]; } - BumpPtrAllocator& getVNInfoAllocator() { return VNInfoAllocator; } + private: + /// Compute live intervals for all virtual registers. + void computeVirtRegs(); - /// getVNInfoSourceReg - Helper function that parses the specified VNInfo - /// copy field and returns the source register that defines it. - unsigned getVNInfoSourceReg(const VNInfo *VNI) const; + /// Compute RegMaskSlots and RegMaskBits. + void computeRegMasks(); - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual void releaseMemory(); + /// Walk the values in @p LI and check for dead values: + /// - Dead PHIDef values are marked as unused. + /// - Dead operands are marked as such. + /// - Completely dead machine instructions are added to the @p dead vector + /// if it is not nullptr. + /// Returns true if any PHI value numbers have been removed which may + /// have separated the interval into multiple connected components. + bool computeDeadValues(LiveInterval &LI, + SmallVectorImpl *dead); - /// runOnMachineFunction - pass entry point - virtual bool runOnMachineFunction(MachineFunction&); + static LiveInterval* createInterval(unsigned Reg); - /// 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); - } + void printInstrs(raw_ostream &O) const; + void dumpInstrs() const; - /// 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 - addIntervalsForSpills(const LiveInterval& i, - const MachineLoopInfo *loopInfo, VirtRegMap& vrm, - float &SSWeight); - - /// spillPhysRegAroundRegDefsUses - Spill the specified physical register - /// around all defs and uses of the specified interval. - void 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); - - /// 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(); - - 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, 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 &Ops, - bool isSS, int Slot, unsigned Reg); - - /// canFoldMemoryOperand - Return true if the specified load / store - /// folding is possible. - bool canFoldMemoryOperand(MachineInstr *MI, - SmallVector &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; - - /// 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; - - /// 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 >&RestoreIdxes); - void eraseRestoreInfo(int Id, int index, unsigned vr, - BitVector &RestoreMBBs, - DenseMap >&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 &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 &ReMatIds, const MachineLoopInfo *loopInfo, - unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, - DenseMap &MBBVRegsMap, - std::vector &NewLIs, float &SSWeight); - 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 &ReMatIds, const MachineLoopInfo *loopInfo, - BitVector &SpillMBBs, - DenseMap > &SpillIdxes, - BitVector &RestoreMBBs, - DenseMap > &RestoreIdxes, - DenseMap &MBBVRegsMap, - std::vector &NewLIs, float &SSWeight); + void computeLiveInRegUnits(); + void computeRegUnitRange(LiveRange&, unsigned Unit); + void computeVirtRegInterval(LiveInterval&); - static LiveInterval* createInterval(unsigned Reg); - void printRegName(unsigned reg) const; - }; + /// Helper function for repairIntervalsInRange(), walks backwards and + /// creates/modifies live segments in @p LR to match the operands found. + /// Only full operands or operands with subregisters matching @p LaneMask + /// are considered. + void repairOldRegInRange(MachineBasicBlock::iterator Begin, + MachineBasicBlock::iterator End, + const SlotIndex endIdx, LiveRange &LR, + unsigned Reg, unsigned LaneMask = ~0u); + class HMEditor; + }; } // End llvm namespace #endif