X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveIntervalAnalysis.h;h=b09f8d11106671f5491a1d157adf67a1f7b9b8a0;hb=eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811;hp=d7ff8da02a51a498705731bd8007f888f908f4d4;hpb=cf97036675340bc889cfe04295cda63afe9496e2;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index d7ff8da02a5..b09f8d11106 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -42,7 +42,7 @@ namespace llvm { class TargetInstrInfo; class TargetRegisterClass; class VirtRegMap; - + class LiveIntervals : public MachineFunctionPass { MachineFunction* mf_; MachineRegisterInfo* mri_; @@ -55,7 +55,7 @@ namespace llvm { /// Special pool allocator for VNInfo's (LiveInterval val#). /// - BumpPtrAllocator VNInfoAllocator; + VNInfo::Allocator VNInfoAllocator; typedef DenseMap Reg2IntervalMap; Reg2IntervalMap r2iMap_; @@ -68,12 +68,13 @@ namespace llvm { public: static char ID; // Pass identification, replacement for typeid - LiveIntervals() : MachineFunctionPass(&ID) {} - - static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { - return (isDef + isUse) * powf(10.0F, (float)loopDepth); + LiveIntervals() : MachineFunctionPass(ID) { + initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); } + // 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(); } @@ -98,13 +99,25 @@ namespace llvm { return r2iMap_.count(reg); } + /// isAllocatable - is the physical register reg allocatable in the current + /// function? + bool isAllocatable(unsigned reg) const { + return allocatableRegs_.test(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(); } - + + /// getFuncInstructionCount - Return the number of instructions in the + /// current function. + unsigned getFuncInstructionCount() { + return indexes_->getFunctionSize(); + } + /// getApproximateInstructionCount - computes an estimate of the number /// of instructions in a given LiveInterval. unsigned getApproximateInstructionCount(LiveInterval& I) { @@ -120,11 +133,10 @@ namespace llvm { bool conflictsWithPhysReg(const LiveInterval &li, VirtRegMap &vrm, unsigned reg); - /// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except - /// it can check use as well. - bool conflictsWithPhysRegRef(LiveInterval &li, unsigned Reg, - bool CheckUse, - SmallPtrSet &JoinedCopies); + /// conflictsWithAliasRef - Similar to conflictsWithPhysRegRef except + /// it checks for alias uses and defs. + bool conflictsWithAliasRef(LiveInterval &li, unsigned Reg, + SmallPtrSet &JoinedCopies); // Interval creation LiveInterval &getOrCreateInterval(unsigned reg) { @@ -137,12 +149,18 @@ namespace llvm { /// 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); + /// 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. + void shrinkToUses(LiveInterval *li); + // Interval removal void removeInterval(unsigned Reg) { @@ -151,6 +169,10 @@ namespace llvm { r2iMap_.erase(I); } + SlotIndexes *getSlotIndexes() const { + return indexes_; + } + SlotIndex getZeroIndex() const { return indexes_->getZeroIndex(); } @@ -169,7 +191,7 @@ namespace llvm { SlotIndex getInstructionIndex(const MachineInstr *instr) const { return indexes_->getInstructionIndex(instr); } - + /// Returns the instruction associated with the given index. MachineInstr* getInstructionFromIndex(SlotIndex index) const { return indexes_->getInstructionFromIndex(index); @@ -178,19 +200,35 @@ namespace llvm { /// Return the first index in the given basic block. SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const { return indexes_->getMBBStartIdx(mbb); - } + } /// Return the last index in the given basic block. SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const { return indexes_->getMBBEndIdx(mbb); - } + } - MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { - return indexes_->getMBBFromIndex(index); + bool isLiveInToMBB(const LiveInterval &li, + const MachineBasicBlock *mbb) const { + return li.liveAt(getMBBStartIdx(mbb)); } - SlotIndex getMBBTerminatorGap(const MachineBasicBlock *mbb) { - return indexes_->getTerminatorGap(mbb); + LiveRange* findEnteringRange(LiveInterval &li, + const MachineBasicBlock *mbb) { + return li.getLiveRangeContaining(getMBBStartIdx(mbb)); + } + + bool isLiveOutOfMBB(const LiveInterval &li, + const MachineBasicBlock *mbb) const { + return li.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); } SlotIndex InsertMachineInstrInMaps(MachineInstr *MI) { @@ -205,6 +243,10 @@ namespace llvm { indexes_->replaceMachineInstrInMaps(MI, NewMI); } + void InsertMBBInMaps(MachineBasicBlock *MBB) { + indexes_->insertMBBInMaps(MBB); + } + bool findLiveInMBBs(SlotIndex Start, SlotIndex End, SmallVectorImpl &MBBs) const { return indexes_->findLiveInMBBs(Start, End, MBBs); @@ -214,11 +256,7 @@ namespace llvm { indexes_->renumberIndexes(); } - 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; + VNInfo::Allocator& getVNInfoAllocator() { return VNInfoAllocator; } virtual void getAnalysisUsage(AnalysisUsage &AU) const; virtual void releaseMemory(); @@ -234,14 +272,8 @@ namespace llvm { /// (if any is created) by reference. This is temporary. std::vector addIntervalsForSpills(const LiveInterval& i, - SmallVectorImpl &SpillIs, + const SmallVectorImpl &SpillIs, const MachineLoopInfo *loopInfo, VirtRegMap& vrm); - - /// addIntervalsForSpillsFast - Quickly create new intervals for spilled - /// defs / uses without remat or splitting. - std::vector - addIntervalsForSpillsFast(const LiveInterval &li, - const MachineLoopInfo *loopInfo, VirtRegMap &vrm); /// spillPhysRegAroundRegDefsUses - Spill the specified physical register /// around all defs and uses of the specified interval. Return true if it @@ -253,7 +285,7 @@ namespace llvm { /// 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, - SmallVectorImpl &SpillIs, + const SmallVectorImpl &SpillIs, bool &isLoad); /// isReMaterializable - Returns true if the definition MI of the specified @@ -270,15 +302,21 @@ namespace llvm { unsigned getNumConflictsWithPhysReg(const LiveInterval &li, unsigned PhysReg) const; - /// processImplicitDefs - Process IMPLICIT_DEF instructions. Add isUndef - /// marker to implicit_def defs and their uses. - void processImplicitDefs(); - /// intervalIsInOneMBB - Returns true if the specified interval is entirely /// within a single basic block. bool intervalIsInOneMBB(const LiveInterval &li) const; - private: + /// getLastSplitPoint - Return the last possible insertion point in mbb for + /// spilling and splitting code. This is the first terminator, or the call + /// instruction if li is live into a landing pad successor. + MachineBasicBlock::iterator getLastSplitPoint(const LiveInterval &li, + MachineBasicBlock *mbb) const; + + /// addKillFlags - Add kill flags to any instruction that kills a virtual + /// register. + void addKillFlags(); + + private: /// computeIntervals - Compute live intervals. void computeIntervals(); @@ -290,6 +328,12 @@ namespace llvm { 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, @@ -328,7 +372,7 @@ namespace llvm { /// by reference if the def is a load. bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo, MachineInstr *MI, - SmallVectorImpl &SpillIs, + const SmallVectorImpl &SpillIs, bool &isLoad); /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from