X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveIntervalAnalysis.h;h=92c3b844c9cf53b3e67447da8dd2dd845a106151;hb=72e04099c6f3d365b36b48834c8cd2f87efc00c2;hp=4f3af88787b2a15591508ddce18ef022a6cf55b4;hpb=edeffb37dc41591b3d3943a5c02c04e55d348524;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 4f3af88787b..92c3b844c9c 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -2,15 +2,15 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// 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' abd 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). @@ -23,26 +23,58 @@ #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/LiveInterval.h" #include "llvm/ADT/BitVector.h" -#include "llvm/ADT/IndexedMap.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/Allocator.h" +#include +#include namespace llvm { class LiveVariables; - class MRegisterInfo; + 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; + } + }; class LiveIntervals : public MachineFunctionPass { MachineFunction* mf_; + MachineRegisterInfo* mri_; const TargetMachine* tm_; - const MRegisterInfo* mri_; + const TargetRegisterInfo* tri_; const TargetInstrInfo* tii_; LiveVariables* lv_; - /// MBB2IdxMap - The index of the first instruction in the specified basic - /// block. - std::vector MBB2IdxMap; - + /// 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; + + /// Idx2MBBMap - Sorted list of pairs of index of first instruction + /// and MBB id. + std::vector Idx2MBBMap; + typedef std::map Mi2IndexMap; Mi2IndexMap mi2iMap_; @@ -52,23 +84,14 @@ namespace llvm { typedef std::map Reg2IntervalMap; Reg2IntervalMap r2iMap_; - typedef IndexedMap Reg2RegMap; - Reg2RegMap r2rMap_; - BitVector allocatableRegs_; + std::vector ClonedMIs; + public: - struct CopyRec { - MachineInstr *MI; - unsigned SrcReg, DstReg; - }; - CopyRec getCopyRec(MachineInstr *MI, unsigned SrcReg, unsigned DstReg) { - CopyRec R; - R.MI = MI; - R.SrcReg = SrcReg; - R.DstReg = DstReg; - return R; - } + static char ID; // Pass identification, replacement for typeid + LiveIntervals() : MachineFunctionPass((intptr_t)&ID) {} + struct InstrSlots { enum { LOAD = 0, @@ -98,13 +121,17 @@ namespace llvm { 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 r2iMap_.size(); } + unsigned getNumIntervals() const { return (unsigned)r2iMap_.size(); } LiveInterval &getInterval(unsigned reg) { Reg2IntervalMap::iterator I = r2iMap_.find(reg); @@ -119,8 +146,7 @@ namespace llvm { } bool hasInterval(unsigned reg) const { - Reg2IntervalMap::const_iterator I = r2iMap_.find(reg); - return I != r2iMap_.end(); + return r2iMap_.count(reg); } /// getMBBStartIdx - Return the base index of the first instruction in the @@ -128,10 +154,44 @@ namespace llvm { unsigned getMBBStartIdx(MachineBasicBlock *MBB) const { return getMBBStartIdx(MBB->getNumber()); } - unsigned getMBBStartIdx(unsigned MBBNo) const { assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!"); - return MBB2IdxMap[MBBNo]; + 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; + } + + /// getIntervalSize - 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. + unsigned getScaledIntervalSize(LiveInterval& I) { + // Factor of 250 comes from 1000 units per function divided + // by four slots per instruction. + return (250 * I.getSize()) / i2miMap_.size(); + } + + /// 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; } /// getInstructionIndex - returns the base index of instr @@ -149,29 +209,38 @@ namespace llvm { "index does not correspond to an instruction"); return i2miMap_[index]; } - - std::vector addIntervalsForSpills(const LiveInterval& i, - VirtRegMap& vrm, - int slot); - /// CreateNewLiveInterval - Create a new live interval with the given live - /// ranges. The new live interval will have an infinite spill weight. - LiveInterval &CreateNewLiveInterval(const LiveInterval *LI, - const std::vector &LRs); + /// 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); - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual void releaseMemory(); + /// 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 + /// where the value is live in. + bool findLiveInMBBs(const LiveRange &LR, + SmallVectorImpl &MBBs) const; - /// runOnMachineFunction - pass entry point - virtual bool runOnMachineFunction(MachineFunction&); + // Interval creation - /// 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); + LiveInterval &getOrCreateInterval(unsigned reg) { + Reg2IntervalMap::iterator I = r2iMap_.find(reg); + if (I == r2iMap_.end()) + I = r2iMap_.insert(I, std::make_pair(reg, createInterval(reg))); + 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); + + // Interval removal + + void removeInterval(unsigned Reg) { + r2iMap_.erase(Reg); } - private: /// isRemoved - returns true if the specified machine instr has been /// removed. bool isRemoved(MachineInstr* instr) const { @@ -189,39 +258,72 @@ namespace llvm { 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 + 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(); - - /// joinIntervals - join compatible live intervals - void joinIntervals(); - - /// CopyCoallesceInMBB - Coallsece copies in the specified MBB, putting - /// copies that cannot yet be coallesced into the "TryAgain" list. - void CopyCoallesceInMBB(MachineBasicBlock *MBB, - std::vector &TryAgain); - - /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, - /// which are the src/dst of the copy instruction CopyMI. This returns true - /// if the copy was successfully coallesced away, or if it is never possible - /// to coallesce these this copy, due to register constraints. It returns - /// false if it is not currently possible to coallesce this interval, but - /// it may be possible if other things get coallesced. - bool JoinCopy(MachineInstr *CopyMI, unsigned SrcReg, unsigned DstReg); - - /// JoinIntervals - Attempt to join these two intervals. On failure, this - /// returns false. Otherwise, if one of the intervals being joined is a - /// physreg, this method always canonicalizes DestInt to be it. The output - /// "SrcInt" will not have been modified, so we can use this information - /// below to update aliases. - bool JoinIntervals(LiveInterval &LHS, LiveInterval &RHS); - - /// SimpleJoin - Attempt to join the specified interval into this one. The - /// caller of this method must guarantee that the RHS only contains a single - /// value number and that the RHS is not defined by a copy from this - /// interval. This returns false if the intervals are not joinable, or it - /// joins them and returns true. - bool SimpleJoin(LiveInterval &LHS, LiveInterval &RHS); /// handleRegisterDef - update intervals for a register def /// (calls handlePhysicalRegisterDef and @@ -243,52 +345,112 @@ namespace llvm { MachineBasicBlock::iterator mi, unsigned MIIdx, LiveInterval &interval, - unsigned SrcReg); + MachineInstr *CopyMI); /// handleLiveInRegister - Create interval for a livein register. void handleLiveInRegister(MachineBasicBlock* mbb, unsigned MIIdx, - LiveInterval &interval); - - /// Return true if the two specified registers belong to different - /// register classes. The registers may be either phys or virt regs. - bool differingRegisterClasses(unsigned RegA, unsigned RegB) const; - - - bool AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, - MachineInstr *CopyMI); - - /// lastRegisterUse - Returns the last use of the specific register between - /// cycles Start and End. It also returns the use operand by reference. It - /// returns NULL if there are no uses. - MachineInstr *lastRegisterUse(unsigned Reg, unsigned Start, unsigned End, - MachineOperand *&MOU); + 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) {}; + }; - /// unsetRegisterKill - Unset IsKill property of all uses of specific - /// register of the specific instruction. - void unsetRegisterKill(MachineInstr *MI, unsigned Reg); + bool alsoFoldARestore(int Id, int index, unsigned vr, + BitVector &RestoreMBBs, + std::map >&RestoreIdxes); + void eraseRestoreInfo(int Id, int index, unsigned vr, + BitVector &RestoreMBBs, + std::map >&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, + std::map &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, + std::map > &SpillIdxes, + BitVector &RestoreMBBs, + std::map > &RestoreIdxes, + std::map &MBBVRegsMap, + std::vector &NewLIs, float &SSWeight); static LiveInterval createInterval(unsigned Reg); - void removeInterval(unsigned Reg) { - r2iMap_.erase(Reg); - } - - LiveInterval &getOrCreateInterval(unsigned reg) { - Reg2IntervalMap::iterator I = r2iMap_.find(reg); - if (I == r2iMap_.end()) - I = r2iMap_.insert(I, std::make_pair(reg, createInterval(reg))); - return I->second; - } - - /// rep - returns the representative of this register - unsigned rep(unsigned Reg) { - unsigned Rep = r2rMap_[Reg]; - if (Rep) - return r2rMap_[Reg] = rep(Rep); - return Reg; - } - void printRegName(unsigned reg) const; };