X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveIntervalAnalysis.h;h=b421753dd5368c2784e13f0e65fe7170a9b5af22;hb=af650354a1de1254c0937a9f6e9c88f447ad3889;hp=bb547c3519a29cf5d042afa05fa0ba2f03f40754;hpb=7824152557cfe3a366963f504b2b956f853ebc3a;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index bb547c3519a..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" @@ -61,14 +62,8 @@ namespace llvm { /// VNInfo::Allocator VNInfoAllocator; - typedef DenseMap Reg2IntervalMap; - Reg2IntervalMap R2IMap; - - /// AllocatableRegs - A bit vector of allocatable registers. - BitVector AllocatableRegs; - - /// ReservedRegs - A bit vector of reserved registers. - BitVector ReservedRegs; + /// Live interval pointers for all the virtual registers. + IndexedMap VirtRegIntervals; /// RegMaskSlots - Sorted list of instructions with register mask operands. /// Always use the 'r' slot, RegMasks are normal clobbers, not early @@ -108,48 +103,33 @@ namespace llvm { // 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]; } - /// isReserved - is the physical register reg reserved in the current - /// function - bool isReserved(unsigned reg) const { - return ReservedRegs.test(reg); + // Interval creation. + LiveInterval &getOrCreateInterval(unsigned Reg) { + if (!hasInterval(Reg)) { + VirtRegIntervals.grow(Reg); + VirtRegIntervals[Reg] = createInterval(Reg); + } + return getInterval(Reg); } - // 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; } /// addLiveRangeToEndOfBlock - Given a register and an instruction, @@ -167,13 +147,25 @@ 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; @@ -251,35 +243,37 @@ 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; + /// 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. - void handleMove(MachineInstr* MI); + /// + /// \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); + void handleMoveIntoBundle(MachineInstr* MI, MachineInstr* BundleStart, + bool UpdateFlags = false); // Register mask functions. // @@ -353,18 +347,18 @@ namespace llvm { return RegUnitIntervals[Unit]; } - /// trackingRegUnits - Does LiveIntervals curently track register units? - /// This function will be removed when regunit tracking is permanently - /// enabled. - bool trackingRegUnits() const { return !RegUnitIntervals.empty(); } - 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, @@ -384,18 +378,6 @@ 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); - - /// handleLiveInRegister - Create interval for a livein register. - void handleLiveInRegister(MachineBasicBlock* mbb, - SlotIndex MIIdx, - LiveInterval &interval); - static LiveInterval* createInterval(unsigned Reg); void printInstrs(raw_ostream &O) const; @@ -403,6 +385,7 @@ namespace llvm { void computeLiveInRegUnits(); void computeRegUnitInterval(LiveInterval*); + void computeVirtRegInterval(LiveInterval*); class HMEditor; };