X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveIntervalAnalysis.h;h=b421753dd5368c2784e13f0e65fe7170a9b5af22;hb=4823be3be1d87632fbd51ce8e51a58ee5e44b115;hp=76f12eb9159baafa0aec8f169c3127af70eed20e;hpb=9a314da5812dc14bb37df47b89041f8059efc8b1;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 76f12eb9159..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; @@ -52,19 +55,15 @@ namespace llvm { 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; - - /// 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 @@ -92,57 +91,45 @@ namespace llvm { /// 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; + LiveInterval &getInterval(unsigned Reg) { + LiveInterval *LI = VirtRegIntervals[Reg]; + assert(LI && "Interval does not exist for virtual register"); + return *LI; } - 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; + const LiveInterval &getInterval(unsigned Reg) const { + return const_cast(this)->getInterval(Reg); } - bool hasInterval(unsigned reg) const { - return R2IMap.count(reg); + bool hasInterval(unsigned Reg) const { + return VirtRegIntervals.inBounds(Reg) && VirtRegIntervals[Reg]; } - /// isAllocatable - is the physical register reg allocatable in the current - /// function? - bool isAllocatable(unsigned reg) const { - return AllocatableRegs.test(reg); + // Interval creation. + LiveInterval &getOrCreateInterval(unsigned Reg) { + if (!hasInterval(Reg)) { + VirtRegIntervals.grow(Reg); + VirtRegIntervals[Reg] = createInterval(Reg); + } + return getInterval(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) { - 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, @@ -160,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; @@ -244,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. // @@ -317,13 +318,47 @@ namespace llvm { 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, @@ -343,23 +378,15 @@ 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; void dumpInstrs() const; + void computeLiveInRegUnits(); + void computeRegUnitInterval(LiveInterval*); + void computeVirtRegInterval(LiveInterval*); + class HMEditor; }; } // End llvm namespace