X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveIntervalAnalysis.h;h=dc52c0a896c40a0ae4d049930f65c0be667fb8d5;hb=d6b76f9466f267ac5ec8ac0f3afa83da0d810490;hp=73def2cd1d696464a6fe71bd8f84e2ef0afc8f98;hpb=27c28cef11da5373d9a146060f9c10a3c6ab58e3;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 73def2cd1d6..dc52c0a896c 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -17,25 +17,28 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H -#define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H +#ifndef LLVM_CODEGEN_LIVEINTERVALANALYSIS_H +#define LLVM_CODEGEN_LIVEINTERVALANALYSIS_H -#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/ADT/IndexedMap.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/CodeGen/LiveInterval.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/IndexedMap.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.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; class LiveRangeCalc; class LiveVariables; class MachineDominatorTree; @@ -45,15 +48,14 @@ 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; - LiveVariables* LV; SlotIndexes* Indexes; MachineDominatorTree *DomTree; LiveRangeCalc *LRCalc; @@ -91,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 @@ -101,12 +103,15 @@ namespace llvm { virtual ~LiveIntervals(); // Calculate the spill weight to assign to a single instruction. - static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth); + static float getSpillWeight(bool isDef, bool isUse, + const MachineBlockFrequencyInfo *MBFI, + const MachineInstr *Instr); LiveInterval &getInterval(unsigned Reg) { - LiveInterval *LI = VirtRegIntervals[Reg]; - assert(LI && "Interval does not exist for virtual register"); - return *LI; + if (hasInterval(Reg)) + return *VirtRegIntervals[Reg]; + else + return createAndComputeVirtRegInterval(Reg); } const LiveInterval &getInterval(unsigned Reg) const { @@ -118,24 +123,29 @@ namespace llvm { } // Interval creation. - LiveInterval &getOrCreateInterval(unsigned Reg) { - if (!hasInterval(Reg)) { - VirtRegIntervals.grow(Reg); - VirtRegIntervals[Reg] = createInterval(Reg); - } - return getInterval(Reg); + LiveInterval &createEmptyInterval(unsigned Reg) { + assert(!hasInterval(Reg) && "Interval already exists!"); + VirtRegIntervals.grow(Reg); + VirtRegIntervals[Reg] = createInterval(Reg); + return *VirtRegIntervals[Reg]; + } + + LiveInterval &createAndComputeVirtRegInterval(unsigned Reg) { + LiveInterval &LI = createEmptyInterval(Reg); + 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 @@ -145,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 @@ -155,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 { @@ -201,24 +218,37 @@ 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 { return Indexes->getMBBFromIndex(index); } + void insertMBBInMaps(MachineBasicBlock *MBB) { + Indexes->insertMBBInMaps(MBB); + assert(unsigned(MBB->getNumber()) == RegMaskBlocks.size() && + "Blocks must be added in order."); + RegMaskBlocks.push_back(std::make_pair(RegMaskSlots.size(), 0)); + } + SlotIndex InsertMachineInstrInMaps(MachineInstr *MI) { return Indexes->insertMachineInstrInMaps(MI); } + void InsertMachineInstrRangeInMaps(MachineBasicBlock::iterator B, + MachineBasicBlock::iterator E) { + for (MachineBasicBlock::iterator I = B; I != E; ++I) + Indexes->insertMachineInstrInMaps(I); + } + void RemoveMachineInstrFromMaps(MachineInstr *MI) { Indexes->removeMachineInstrFromMaps(MI); } @@ -234,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, @@ -261,13 +291,13 @@ namespace llvm { /// the live intervals for all operands of mi. Moves between basic blocks /// are not supported. /// - /// \param updateFlags Update live intervals for nonallocatable physregs. + /// \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. + /// \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 @@ -275,6 +305,21 @@ namespace llvm { void handleMoveIntoBundle(MachineInstr* MI, MachineInstr* BundleStart, bool UpdateFlags = false); + /// repairIntervalsInRange - Update live intervals for instructions in a + /// range of iterators. It is intended for use after target hooks that may + /// insert or remove instructions, and is only efficient for a small number + /// of instructions. + /// + /// OrigRegs is a vector of registers that were originally used by the + /// instructions in the range between the two iterators. + /// + /// Currently, the only only changes that are supported are simple removal + /// and addition of uses. + void repairIntervalsInRange(MachineBasicBlock *MBB, + MachineBasicBlock::iterator Begin, + MachineBasicBlock::iterator End, + ArrayRef OrigRegs); + // Register mask functions. // // Machine instructions may use a register mask operand to indicate that a @@ -331,52 +376,52 @@ 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]; } - private: - /// computeIntervals - Compute live intervals. - void computeIntervals(); + 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(); /// Compute RegMaskSlots and RegMaskBits. void computeRegMasks(); - /// handleRegisterDef - update intervals for a register def - /// (calls handleVirtualRegisterDef) - void handleRegisterDef(MachineBasicBlock *MBB, - MachineBasicBlock::iterator MI, - 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, - MachineBasicBlock::iterator MI, - SlotIndex MIIdx, MachineOperand& MO, - unsigned MOIdx, - LiveInterval& interval); + /// 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); @@ -384,8 +429,18 @@ namespace llvm { 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; };