X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveIntervalAnalysis.h;h=dc52c0a896c40a0ae4d049930f65c0be667fb8d5;hb=d6b76f9466f267ac5ec8ac0f3afa83da0d810490;hp=d134781cfc7c76a8df3836775865c6aca5b5ddf5;hpb=e742d687369f79702894b6cf302e1f222c5d7432;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index d134781cfc7..dc52c0a896c 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -17,8 +17,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H -#define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H +#ifndef LLVM_CODEGEN_LIVEINTERVALANALYSIS_H +#define LLVM_CODEGEN_LIVEINTERVALANALYSIS_H #include "llvm/ADT/IndexedMap.h" #include "llvm/ADT/SmallVector.h" @@ -27,12 +27,15 @@ #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/SlotIndexes.h" #include "llvm/Support/Allocator.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Target/TargetRegisterInfo.h" #include #include namespace llvm { +extern cl::opt UseSegmentSetForPhysRegs; + class AliasAnalysis; class BitVector; class BlockFrequency; @@ -45,11 +48,11 @@ namespace llvm { class TargetInstrInfo; class TargetRegisterClass; class VirtRegMap; + class MachineBlockFrequencyInfo; class LiveIntervals : public MachineFunctionPass { MachineFunction* MF; MachineRegisterInfo* MRI; - const TargetMachine* TM; const TargetRegisterInfo* TRI; const TargetInstrInfo* TII; AliasAnalysis *AA; @@ -90,9 +93,9 @@ 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; + /// Keeps a live range set for each register unit to track fixed physreg + /// interference. + SmallVector RegUnitRanges; public: static char ID; // Pass identification, replacement for typeid @@ -100,7 +103,9 @@ namespace llvm { virtual ~LiveIntervals(); // Calculate the spill weight to assign to a single instruction. - static float getSpillWeight(bool isDef, bool isUse, BlockFrequency freq); + static float getSpillWeight(bool isDef, bool isUse, + const MachineBlockFrequencyInfo *MBFI, + const MachineInstr *Instr); LiveInterval &getInterval(unsigned Reg) { if (hasInterval(Reg)) @@ -127,20 +132,20 @@ namespace llvm { LiveInterval &createAndComputeVirtRegInterval(unsigned Reg) { LiveInterval &LI = createEmptyInterval(Reg); - computeVirtRegInterval(&LI); + computeVirtRegInterval(LI); return LI; } // Interval removal. void removeInterval(unsigned Reg) { delete VirtRegIntervals[Reg]; - VirtRegIntervals[Reg] = 0; + VirtRegIntervals[Reg] = nullptr; } - /// 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); + /// 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 @@ -150,7 +155,13 @@ namespace llvm { /// Return true if the interval may have been separated into multiple /// connected components. bool shrinkToUses(LiveInterval *li, - SmallVectorImpl *dead = 0); + 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 @@ -160,16 +171,17 @@ namespace llvm { /// extended to be live out of the basic block. /// /// See also LiveRangeCalc::extend(). - void extendToIndices(LiveInterval *LI, ArrayRef Indices); + void extendToIndices(LiveRange &LR, ArrayRef Indices); + - /// 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 + /// 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(LiveInterval *LI, SlotIndex Kill, + void pruneValue(LiveRange &LR, SlotIndex Kill, SmallVectorImpl *EndPoints); SlotIndexes *getSlotIndexes() const { @@ -206,14 +218,14 @@ namespace llvm { return Indexes->getMBBEndIdx(mbb); } - bool isLiveInToMBB(const LiveInterval &li, + bool isLiveInToMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const { - return li.liveAt(getMBBStartIdx(mbb)); + return LR.liveAt(getMBBStartIdx(mbb)); } - bool isLiveOutOfMBB(const LiveInterval &li, + bool isLiveOutOfMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const { - return li.liveAt(getMBBEndIdx(mbb).getPrevSlot()); + return LR.liveAt(getMBBEndIdx(mbb).getPrevSlot()); } MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { @@ -252,14 +264,14 @@ namespace llvm { VNInfo::Allocator& getVNInfoAllocator() { return VNInfoAllocator; } - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual void releaseMemory(); + void getAnalysisUsage(AnalysisUsage &AU) const override; + void releaseMemory() override; /// runOnMachineFunction - pass entry point - virtual bool runOnMachineFunction(MachineFunction&); + bool runOnMachineFunction(MachineFunction&) override; /// print - Implement the dump method. - virtual void print(raw_ostream &O, const Module* = 0) const; + void print(raw_ostream &O, const Module* = nullptr) const override; /// 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, @@ -364,26 +376,36 @@ namespace llvm { /// 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) { + LiveRange &getRegUnit(unsigned Unit) { + LiveRange *LR = RegUnitRanges[Unit]; + if (!LR) { // Compute missing ranges on demand. - RegUnitIntervals[Unit] = LI = new LiveInterval(Unit, HUGE_VALF); - computeRegUnitInterval(LI); + // Use segment set to speed-up initial computation of the live range. + RegUnitRanges[Unit] = LR = new LiveRange(UseSegmentSetForPhysRegs); + computeRegUnitRange(*LR, Unit); } - return *LI; + return *LR; } /// 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]; + LiveRange *getCachedRegUnit(unsigned Unit) { + return RegUnitRanges[Unit]; } - const LiveInterval *getCachedRegUnit(unsigned Unit) const { - return RegUnitIntervals[Unit]; + const LiveRange *getCachedRegUnit(unsigned Unit) const { + return RegUnitRanges[Unit]; } + /// Remove value numbers and related live segments starting at position + /// @p Pos that are part of any liverange of physical register @p Reg or one + /// of its subregisters. + void removePhysRegDefAt(unsigned Reg, SlotIndex Pos); + + /// Remove value number and related live segments of @p LI and its subranges + /// that start at position @p Pos. + void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos); + private: /// Compute live intervals for all virtual registers. void computeVirtRegs(); @@ -391,14 +413,34 @@ namespace llvm { /// Compute RegMaskSlots and RegMaskBits. void computeRegMasks(); + /// 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); + static LiveInterval* createInterval(unsigned Reg); void printInstrs(raw_ostream &O) const; void dumpInstrs() const; void computeLiveInRegUnits(); - void computeRegUnitInterval(LiveInterval*); - void computeVirtRegInterval(LiveInterval*); + void computeRegUnitRange(LiveRange&, unsigned Unit); + void computeVirtRegInterval(LiveInterval&); + + + /// 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; };