Index: include/llvm/CodeGen/CalcSpillWeights.h =================================================================== --- include/llvm/CodeGen/CalcSpillWeights.h +++ include/llvm/CodeGen/CalcSpillWeights.h @@ -1,82 +1,106 @@ -//===---------------- lib/CodeGen/CalcSpillWeights.h ------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - - -#ifndef LLVM_CODEGEN_CALCSPILLWEIGHTS_H -#define LLVM_CODEGEN_CALCSPILLWEIGHTS_H - -#include "llvm/ADT/DenseMap.h" -#include "llvm/CodeGen/SlotIndexes.h" - -namespace llvm { - - class LiveInterval; - class LiveIntervals; - class MachineBlockFrequencyInfo; - class MachineLoopInfo; - class VirtRegMap; - - /// \brief Normalize the spill weight of a live interval - /// - /// The spill weight of a live interval is computed as: - /// - /// (sum(use freq) + sum(def freq)) / (K + size) - /// - /// @param UseDefFreq Expected number of executed use and def instructions - /// per function call. Derived from block frequencies. - /// @param Size Size of live interval as returnexd by getSize() - /// @param NumInstr Number of instructions using this live interval - /// - static inline float normalizeSpillWeight(float UseDefFreq, unsigned Size, - unsigned NumInstr) { - // The constant 25 instructions is added to avoid depending too much on - // accidental SlotIndex gaps for small intervals. The effect is that small - // intervals have a spill weight that is mostly proportional to the number - // of uses, while large intervals get a spill weight that is closer to a use - // density. - return UseDefFreq / (Size + 25*SlotIndex::InstrDist); - } - - /// \brief Calculate auxiliary information for a virtual register such as its - /// spill weight and allocation hint. - class VirtRegAuxInfo { - public: - typedef float (*NormalizingFn)(float, unsigned, unsigned); - - private: - MachineFunction &MF; - LiveIntervals &LIS; - VirtRegMap *VRM; - const MachineLoopInfo &Loops; - const MachineBlockFrequencyInfo &MBFI; - DenseMap Hint; - NormalizingFn normalize; - - public: - VirtRegAuxInfo(MachineFunction &mf, LiveIntervals &lis, - VirtRegMap *vrm, const MachineLoopInfo &loops, - const MachineBlockFrequencyInfo &mbfi, - NormalizingFn norm = normalizeSpillWeight) - : MF(mf), LIS(lis), VRM(vrm), Loops(loops), MBFI(mbfi), normalize(norm) {} - - /// \brief (re)compute li's spill weight and allocation hint. - void calculateSpillWeightAndHint(LiveInterval &li); - }; - - /// \brief Compute spill weights and allocation hints for all virtual register - /// live intervals. - void calculateSpillWeightsAndHints(LiveIntervals &LIS, MachineFunction &MF, - VirtRegMap *VRM, - const MachineLoopInfo &MLI, - const MachineBlockFrequencyInfo &MBFI, - VirtRegAuxInfo::NormalizingFn norm = - normalizeSpillWeight); -} - -#endif // LLVM_CODEGEN_CALCSPILLWEIGHTS_H +//===---------------- lib/CodeGen/CalcSpillWeights.h ------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + + +#ifndef LLVM_CODEGEN_CALCSPILLWEIGHTS_H +#define LLVM_CODEGEN_CALCSPILLWEIGHTS_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/CodeGen/SlotIndexes.h" + +namespace llvm { + + class LiveInterval; + class LiveIntervals; + class MachineBlockFrequencyInfo; + class MachineLoopInfo; + class VirtRegMap; + + /// \brief Normalize the spill weight of a live interval + /// + /// The spill weight of a live interval is computed as: + /// + /// (sum(use freq) + sum(def freq)) / (K + size) + /// + /// @param UseDefFreq Expected number of executed use and def instructions + /// per function call. Derived from block frequencies. + /// @param Size Size of live interval as returnexd by getSize() + /// @param NumInstr Number of instructions using this live interval + /// + static inline float normalizeSpillWeight(float UseDefFreq, unsigned Size, + unsigned NumInstr) { + // The constant 25 instructions is added to avoid depending too much on + // accidental SlotIndex gaps for small intervals. The effect is that small + // intervals have a spill weight that is mostly proportional to the number + // of uses, while large intervals get a spill weight that is closer to a use + // density. + return UseDefFreq / (Size + 25*SlotIndex::InstrDist); + } + + /// \brief Calculate auxiliary information for a virtual register such as its + /// spill weight and allocation hint. + class VirtRegAuxInfo { + public: + typedef float (*NormalizingFn)(float, unsigned, unsigned); + + private: + MachineFunction &MF; + LiveIntervals &LIS; + VirtRegMap *VRM; + const MachineLoopInfo &Loops; + const MachineBlockFrequencyInfo &MBFI; + DenseMap Hint; + NormalizingFn normalize; + + public: + VirtRegAuxInfo(MachineFunction &mf, LiveIntervals &lis, + VirtRegMap *vrm, const MachineLoopInfo &loops, + const MachineBlockFrequencyInfo &mbfi, + NormalizingFn norm = normalizeSpillWeight) + : MF(mf), LIS(lis), VRM(vrm), Loops(loops), MBFI(mbfi), normalize(norm) {} + + /// \brief (re)compute li's spill weight and allocation hint. + void calculateSpillWeightAndHint(LiveInterval &li); + /// \brief Compute future expected spill weight of a split artifact of li + /// that will span between start and end slot indexes. + /// \param li The live interval to be split. + /// \param start The expected begining of the split artifact. Instructions + /// before start will not affect the weight. + /// \param end The expected end of the split artifact. Instructions + /// after end will not affect the weight. + /// \return The expected spill weight of the split artifact. Returns + /// negative weight for unspillable li. + float futureWeight(LiveInterval &li, SlotIndex start, SlotIndex end); + /// \brief Helper function for weight calculations. + /// (Re)compute li's spill weight and allocation hint, or, for non null + /// start and end - compute future expected spill weight of a split + /// artifact of li that will span between start and end slot indexes. + /// \param li The live interval for which to compute the weight. + /// \param start The expected begining of the split artifact. Instructions + /// before start will not affect the weight. Relevant for + /// weight calculation of future split artifact. + /// \param end The expected end of the split artifact. Instructions + /// after end will not affect the weight. Relevant for + /// weight calculation of future split artifact. + /// \return The spill weight. Returns negative weight for unspillable li. + float weightCalcHelper(LiveInterval &li, SlotIndex *start = nullptr, + SlotIndex *end = nullptr); + }; + + /// \brief Compute spill weights and allocation hints for all virtual register + /// live intervals. + void calculateSpillWeightsAndHints(LiveIntervals &LIS, MachineFunction &MF, + VirtRegMap *VRM, + const MachineLoopInfo &MLI, + const MachineBlockFrequencyInfo &MBFI, + VirtRegAuxInfo::NormalizingFn norm = + normalizeSpillWeight); +} + +#endif // LLVM_CODEGEN_CALCSPILLWEIGHTS_H Index: include/llvm/CodeGen/LiveIntervalAnalysis.h =================================================================== --- include/llvm/CodeGen/LiveIntervalAnalysis.h +++ include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -1,476 +1,481 @@ -//===- LiveIntervalAnalysis.h - Live Interval Analysis ----------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -/// \file This file implements the LiveInterval analysis pass. Given some -/// numbering of each the machine instructions (in this implemention depth-first -/// order) an interval [i, j) is said to be a live interval for register v if -/// there is no instruction with number j' > j such that v is live at j' and -/// there is no instruction with number i' < i such that v is live at i'. In -/// this implementation intervals can have holes, i.e. an interval might look -/// like [1,20), [50,65), [1000,1001). -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CODEGEN_LIVEINTERVALANALYSIS_H -#define LLVM_CODEGEN_LIVEINTERVALANALYSIS_H - -#include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/IndexedMap.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/CodeGen/LiveInterval.h" -#include "llvm/CodeGen/MachineBasicBlock.h" -#include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/SlotIndexes.h" -#include "llvm/MC/LaneBitmask.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Compiler.h" -#include "llvm/Support/ErrorHandling.h" -#include "llvm/Target/TargetRegisterInfo.h" -#include -#include -#include - -namespace llvm { - -extern cl::opt UseSegmentSetForPhysRegs; - -class BitVector; -class LiveRangeCalc; -class MachineBlockFrequencyInfo; -class MachineDominatorTree; -class MachineFunction; -class MachineInstr; -class MachineRegisterInfo; -class raw_ostream; -class TargetInstrInfo; -class VirtRegMap; - - class LiveIntervals : public MachineFunctionPass { - MachineFunction* MF; - MachineRegisterInfo* MRI; - const TargetRegisterInfo* TRI; - const TargetInstrInfo* TII; - AliasAnalysis *AA; - SlotIndexes* Indexes; - MachineDominatorTree *DomTree = nullptr; - LiveRangeCalc *LRCalc = nullptr; - - /// Special pool allocator for VNInfo's (LiveInterval val#). - VNInfo::Allocator VNInfoAllocator; - - /// Live interval pointers for all the virtual registers. - IndexedMap VirtRegIntervals; - - /// Sorted list of instructions with register mask operands. Always use the - /// 'r' slot, RegMasks are normal clobbers, not early clobbers. - SmallVector RegMaskSlots; - - /// This vector is parallel to RegMaskSlots, it holds a pointer to the - /// corresponding register mask. This pointer can be recomputed as: - /// - /// MI = Indexes->getInstructionFromIndex(RegMaskSlot[N]); - /// unsigned OpNum = findRegMaskOperand(MI); - /// RegMaskBits[N] = MI->getOperand(OpNum).getRegMask(); - /// - /// This is kept in a separate vector partly because some standard - /// libraries don't support lower_bound() with mixed objects, partly to - /// improve locality when searching in RegMaskSlots. - /// Also see the comment in LiveInterval::find(). - SmallVector RegMaskBits; - - /// For each basic block number, keep (begin, size) pairs indexing into the - /// RegMaskSlots and RegMaskBits arrays. - /// Note that basic block numbers may not be layout contiguous, that's why - /// we can't just keep track of the first register mask in each basic - /// block. - SmallVector, 8> RegMaskBlocks; - - /// Keeps a live range set for each register unit to track fixed physreg - /// interference. - SmallVector RegUnitRanges; - - public: - static char ID; - - LiveIntervals(); - ~LiveIntervals() override; - - /// Calculate the spill weight to assign to a single instruction. - static float getSpillWeight(bool isDef, bool isUse, - const MachineBlockFrequencyInfo *MBFI, - const MachineInstr &Instr); - - LiveInterval &getInterval(unsigned Reg) { - if (hasInterval(Reg)) - return *VirtRegIntervals[Reg]; - else - return createAndComputeVirtRegInterval(Reg); - } - - const LiveInterval &getInterval(unsigned Reg) const { - return const_cast(this)->getInterval(Reg); - } - - bool hasInterval(unsigned Reg) const { - return VirtRegIntervals.inBounds(Reg) && VirtRegIntervals[Reg]; - } - - /// Interval creation. - 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] = nullptr; - } - - /// 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); - - /// 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. New dead machine instructions - /// are added to the dead vector. Returns true if the interval may have been - /// separated into multiple connected components. - bool shrinkToUses(LiveInterval *li, - 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. - /// This may leave the subrange empty which needs to be cleaned up with - /// LiveInterval::removeEmptySubranges() afterwards. - void shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg); - - /// Extend the live range \p LR to reach all points in \p Indices. The - /// points in the \p Indices array must be jointly dominated by the union - /// of the existing defs in \p LR and points in \p Undefs. - /// - /// PHI-defs are added as needed to maintain SSA form. - /// - /// If a SlotIndex in \p Indices is the end index of a basic block, \p LR - /// will be extended to be live out of the basic block. - /// If a SlotIndex in \p Indices is jointy dominated only by points in - /// \p Undefs, the live range will not be extended to that point. - /// - /// See also LiveRangeCalc::extend(). - void extendToIndices(LiveRange &LR, ArrayRef Indices, - ArrayRef Undefs); - - void extendToIndices(LiveRange &LR, ArrayRef Indices) { - extendToIndices(LR, Indices, /*Undefs=*/{}); - } - - /// 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(LiveRange &LR, SlotIndex Kill, - SmallVectorImpl *EndPoints); - - /// This function should not be used. Its intend is to tell you that - /// you are doing something wrong if you call pruveValue directly on a - /// LiveInterval. Indeed, you are supposed to call pruneValue on the main - /// LiveRange and all the LiveRange of the subranges if any. - LLVM_ATTRIBUTE_UNUSED void pruneValue(LiveInterval &, SlotIndex, - SmallVectorImpl *) { - llvm_unreachable( - "Use pruneValue on the main LiveRange and on each subrange"); - } - - SlotIndexes *getSlotIndexes() const { - return Indexes; - } - - AliasAnalysis *getAliasAnalysis() const { - return AA; - } - - /// Returns true if the specified machine instr has been removed or was - /// never entered in the map. - bool isNotInMIMap(const MachineInstr &Instr) const { - return !Indexes->hasIndex(Instr); - } - - /// Returns the base index of the given instruction. - 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); - } - - /// 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); - } - - bool isLiveInToMBB(const LiveRange &LR, - const MachineBasicBlock *mbb) const { - return LR.liveAt(getMBBStartIdx(mbb)); - } - - bool isLiveOutOfMBB(const LiveRange &LR, - const MachineBasicBlock *mbb) const { - 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); - } - - SlotIndex ReplaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI) { - return Indexes->replaceMachineInstrInMaps(MI, NewMI); - } - - VNInfo::Allocator& getVNInfoAllocator() { return VNInfoAllocator; } - - void getAnalysisUsage(AnalysisUsage &AU) const override; - void releaseMemory() override; - - /// Pass entry point; Calculates LiveIntervals. - bool runOnMachineFunction(MachineFunction&) override; - - /// Implement the dump method. - void print(raw_ostream &O, const Module* = nullptr) const override; - - /// 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; - - /// Add kill flags to any instruction that kills a virtual register. - void addKillFlags(const VirtRegMap*); - - /// Call this method to notify LiveIntervals that instruction \p MI has been - /// moved within a basic block. This will update the live intervals for all - /// operands of \p MI. Moves between basic blocks are not supported. - /// - /// \param UpdateFlags Update live intervals for nonallocatable physregs. - void handleMove(MachineInstr &MI, bool UpdateFlags = false); - - /// Update intervals for operands of \p MI so that they begin/end on the - /// SlotIndex for \p 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, - bool UpdateFlags = false); - - /// 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 - // large number of registers are clobbered by the instruction. This is - // typically used for calls. - // - // For compile time performance reasons, these clobbers are not recorded in - // the live intervals for individual physical registers. Instead, - // LiveIntervalAnalysis maintains a sorted list of instructions with - // register mask operands. - - /// Returns a sorted array of slot indices of all instructions with - /// register mask operands. - ArrayRef getRegMaskSlots() const { return RegMaskSlots; } - - /// Returns a sorted array of slot indices of all instructions with register - /// mask operands in the basic block numbered \p MBBNum. - ArrayRef getRegMaskSlotsInBlock(unsigned MBBNum) const { - std::pair P = RegMaskBlocks[MBBNum]; - return getRegMaskSlots().slice(P.first, P.second); - } - - /// Returns an array of register mask pointers corresponding to - /// getRegMaskSlots(). - ArrayRef getRegMaskBits() const { return RegMaskBits; } - - /// Returns an array of mask pointers corresponding to - /// getRegMaskSlotsInBlock(MBBNum). - ArrayRef getRegMaskBitsInBlock(unsigned MBBNum) const { - std::pair P = RegMaskBlocks[MBBNum]; - return getRegMaskBits().slice(P.first, P.second); - } - - /// Test if \p LI is live across any register mask instructions, and - /// compute a bit mask of physical registers that are not clobbered by any - /// of them. - /// - /// Returns false if \p LI doesn't cross any register mask instructions. In - /// that case, the bit vector is not filled in. - 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. - - /// Return the live range for register unit \p Unit. It will be computed if - /// it doesn't exist. - LiveRange &getRegUnit(unsigned Unit) { - LiveRange *LR = RegUnitRanges[Unit]; - if (!LR) { - // Compute missing ranges on demand. - // Use segment set to speed-up initial computation of the live range. - RegUnitRanges[Unit] = LR = new LiveRange(UseSegmentSetForPhysRegs); - computeRegUnitRange(*LR, Unit); - } - return *LR; - } - - /// Return the live range for register unit \p Unit if it has already been - /// computed, or nullptr if it hasn't been computed yet. - LiveRange *getCachedRegUnit(unsigned Unit) { - return RegUnitRanges[Unit]; - } - - const LiveRange *getCachedRegUnit(unsigned Unit) const { - return RegUnitRanges[Unit]; - } - - /// Remove computed live range for register unit \p Unit. Subsequent uses - /// should rely on on-demand recomputation. - void removeRegUnit(unsigned Unit) { - delete RegUnitRanges[Unit]; - RegUnitRanges[Unit] = nullptr; - } - - /// 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); - - /// Split separate components in LiveInterval \p LI into separate intervals. - void splitSeparateComponents(LiveInterval &LI, - SmallVectorImpl &SplitLIs); - - /// For live interval \p LI with correct SubRanges construct matching - /// information for the main live range. Expects the main live range to not - /// have any segments or value numbers. - void constructMainRangeFromSubranges(LiveInterval &LI); - - private: - /// Compute live intervals for all virtual registers. - void computeVirtRegs(); - - /// 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 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, - LaneBitmask LaneMask = LaneBitmask::getAll()); - - class HMEditor; - }; - -} // end namespace llvm - -#endif // LLVM_CODEGEN_LIVEINTERVALANALYSIS_H +//===- LiveIntervalAnalysis.h - Live Interval Analysis ----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +/// \file This file implements the LiveInterval analysis pass. Given some +/// numbering of each the machine instructions (in this implemention depth-first +/// order) an interval [i, j) is said to be a live interval for register v if +/// there is no instruction with number j' > j such that v is live at j' and +/// there is no instruction with number i' < i such that v is live at i'. In +/// this implementation intervals can have holes, i.e. an interval might look +/// like [1,20), [50,65), [1000,1001). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_LIVEINTERVALANALYSIS_H +#define LLVM_CODEGEN_LIVEINTERVALANALYSIS_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/IndexedMap.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/CodeGen/LiveInterval.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/SlotIndexes.h" +#include "llvm/MC/LaneBitmask.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include +#include +#include + +namespace llvm { + +extern cl::opt UseSegmentSetForPhysRegs; + +class BitVector; +class LiveRangeCalc; +class MachineBlockFrequencyInfo; +class MachineDominatorTree; +class MachineFunction; +class MachineInstr; +class MachineRegisterInfo; +class raw_ostream; +class TargetInstrInfo; +class VirtRegMap; + + class LiveIntervals : public MachineFunctionPass { + MachineFunction* MF; + MachineRegisterInfo* MRI; + const TargetRegisterInfo* TRI; + const TargetInstrInfo* TII; + AliasAnalysis *AA; + SlotIndexes* Indexes; + MachineDominatorTree *DomTree = nullptr; + LiveRangeCalc *LRCalc = nullptr; + + /// Special pool allocator for VNInfo's (LiveInterval val#). + VNInfo::Allocator VNInfoAllocator; + + /// Live interval pointers for all the virtual registers. + IndexedMap VirtRegIntervals; + + /// Sorted list of instructions with register mask operands. Always use the + /// 'r' slot, RegMasks are normal clobbers, not early clobbers. + SmallVector RegMaskSlots; + + /// This vector is parallel to RegMaskSlots, it holds a pointer to the + /// corresponding register mask. This pointer can be recomputed as: + /// + /// MI = Indexes->getInstructionFromIndex(RegMaskSlot[N]); + /// unsigned OpNum = findRegMaskOperand(MI); + /// RegMaskBits[N] = MI->getOperand(OpNum).getRegMask(); + /// + /// This is kept in a separate vector partly because some standard + /// libraries don't support lower_bound() with mixed objects, partly to + /// improve locality when searching in RegMaskSlots. + /// Also see the comment in LiveInterval::find(). + SmallVector RegMaskBits; + + /// For each basic block number, keep (begin, size) pairs indexing into the + /// RegMaskSlots and RegMaskBits arrays. + /// Note that basic block numbers may not be layout contiguous, that's why + /// we can't just keep track of the first register mask in each basic + /// block. + SmallVector, 8> RegMaskBlocks; + + /// Keeps a live range set for each register unit to track fixed physreg + /// interference. + SmallVector RegUnitRanges; + + public: + static char ID; + + LiveIntervals(); + ~LiveIntervals() override; + + /// Calculate the spill weight to assign to a single instruction. + static float getSpillWeight(bool isDef, bool isUse, + const MachineBlockFrequencyInfo *MBFI, + const MachineInstr &Instr); + + /// Calculate the spill weight to assign to a single instruction. + static float getSpillWeight(bool isDef, bool isUse, + const MachineBlockFrequencyInfo *MBFI, + const MachineBasicBlock *MBB); + + LiveInterval &getInterval(unsigned Reg) { + if (hasInterval(Reg)) + return *VirtRegIntervals[Reg]; + else + return createAndComputeVirtRegInterval(Reg); + } + + const LiveInterval &getInterval(unsigned Reg) const { + return const_cast(this)->getInterval(Reg); + } + + bool hasInterval(unsigned Reg) const { + return VirtRegIntervals.inBounds(Reg) && VirtRegIntervals[Reg]; + } + + /// Interval creation. + 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] = nullptr; + } + + /// 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); + + /// 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. New dead machine instructions + /// are added to the dead vector. Returns true if the interval may have been + /// separated into multiple connected components. + bool shrinkToUses(LiveInterval *li, + 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. + /// This may leave the subrange empty which needs to be cleaned up with + /// LiveInterval::removeEmptySubranges() afterwards. + void shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg); + + /// Extend the live range \p LR to reach all points in \p Indices. The + /// points in the \p Indices array must be jointly dominated by the union + /// of the existing defs in \p LR and points in \p Undefs. + /// + /// PHI-defs are added as needed to maintain SSA form. + /// + /// If a SlotIndex in \p Indices is the end index of a basic block, \p LR + /// will be extended to be live out of the basic block. + /// If a SlotIndex in \p Indices is jointy dominated only by points in + /// \p Undefs, the live range will not be extended to that point. + /// + /// See also LiveRangeCalc::extend(). + void extendToIndices(LiveRange &LR, ArrayRef Indices, + ArrayRef Undefs); + + void extendToIndices(LiveRange &LR, ArrayRef Indices) { + extendToIndices(LR, Indices, /*Undefs=*/{}); + } + + /// 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(LiveRange &LR, SlotIndex Kill, + SmallVectorImpl *EndPoints); + + /// This function should not be used. Its intend is to tell you that + /// you are doing something wrong if you call pruveValue directly on a + /// LiveInterval. Indeed, you are supposed to call pruneValue on the main + /// LiveRange and all the LiveRange of the subranges if any. + LLVM_ATTRIBUTE_UNUSED void pruneValue(LiveInterval &, SlotIndex, + SmallVectorImpl *) { + llvm_unreachable( + "Use pruneValue on the main LiveRange and on each subrange"); + } + + SlotIndexes *getSlotIndexes() const { + return Indexes; + } + + AliasAnalysis *getAliasAnalysis() const { + return AA; + } + + /// Returns true if the specified machine instr has been removed or was + /// never entered in the map. + bool isNotInMIMap(const MachineInstr &Instr) const { + return !Indexes->hasIndex(Instr); + } + + /// Returns the base index of the given instruction. + 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); + } + + /// 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); + } + + bool isLiveInToMBB(const LiveRange &LR, + const MachineBasicBlock *mbb) const { + return LR.liveAt(getMBBStartIdx(mbb)); + } + + bool isLiveOutOfMBB(const LiveRange &LR, + const MachineBasicBlock *mbb) const { + 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); + } + + SlotIndex ReplaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI) { + return Indexes->replaceMachineInstrInMaps(MI, NewMI); + } + + VNInfo::Allocator& getVNInfoAllocator() { return VNInfoAllocator; } + + void getAnalysisUsage(AnalysisUsage &AU) const override; + void releaseMemory() override; + + /// Pass entry point; Calculates LiveIntervals. + bool runOnMachineFunction(MachineFunction&) override; + + /// Implement the dump method. + void print(raw_ostream &O, const Module* = nullptr) const override; + + /// 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; + + /// Add kill flags to any instruction that kills a virtual register. + void addKillFlags(const VirtRegMap*); + + /// Call this method to notify LiveIntervals that instruction \p MI has been + /// moved within a basic block. This will update the live intervals for all + /// operands of \p MI. Moves between basic blocks are not supported. + /// + /// \param UpdateFlags Update live intervals for nonallocatable physregs. + void handleMove(MachineInstr &MI, bool UpdateFlags = false); + + /// Update intervals for operands of \p MI so that they begin/end on the + /// SlotIndex for \p 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, + bool UpdateFlags = false); + + /// 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 + // large number of registers are clobbered by the instruction. This is + // typically used for calls. + // + // For compile time performance reasons, these clobbers are not recorded in + // the live intervals for individual physical registers. Instead, + // LiveIntervalAnalysis maintains a sorted list of instructions with + // register mask operands. + + /// Returns a sorted array of slot indices of all instructions with + /// register mask operands. + ArrayRef getRegMaskSlots() const { return RegMaskSlots; } + + /// Returns a sorted array of slot indices of all instructions with register + /// mask operands in the basic block numbered \p MBBNum. + ArrayRef getRegMaskSlotsInBlock(unsigned MBBNum) const { + std::pair P = RegMaskBlocks[MBBNum]; + return getRegMaskSlots().slice(P.first, P.second); + } + + /// Returns an array of register mask pointers corresponding to + /// getRegMaskSlots(). + ArrayRef getRegMaskBits() const { return RegMaskBits; } + + /// Returns an array of mask pointers corresponding to + /// getRegMaskSlotsInBlock(MBBNum). + ArrayRef getRegMaskBitsInBlock(unsigned MBBNum) const { + std::pair P = RegMaskBlocks[MBBNum]; + return getRegMaskBits().slice(P.first, P.second); + } + + /// Test if \p LI is live across any register mask instructions, and + /// compute a bit mask of physical registers that are not clobbered by any + /// of them. + /// + /// Returns false if \p LI doesn't cross any register mask instructions. In + /// that case, the bit vector is not filled in. + 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. + + /// Return the live range for register unit \p Unit. It will be computed if + /// it doesn't exist. + LiveRange &getRegUnit(unsigned Unit) { + LiveRange *LR = RegUnitRanges[Unit]; + if (!LR) { + // Compute missing ranges on demand. + // Use segment set to speed-up initial computation of the live range. + RegUnitRanges[Unit] = LR = new LiveRange(UseSegmentSetForPhysRegs); + computeRegUnitRange(*LR, Unit); + } + return *LR; + } + + /// Return the live range for register unit \p Unit if it has already been + /// computed, or nullptr if it hasn't been computed yet. + LiveRange *getCachedRegUnit(unsigned Unit) { + return RegUnitRanges[Unit]; + } + + const LiveRange *getCachedRegUnit(unsigned Unit) const { + return RegUnitRanges[Unit]; + } + + /// Remove computed live range for register unit \p Unit. Subsequent uses + /// should rely on on-demand recomputation. + void removeRegUnit(unsigned Unit) { + delete RegUnitRanges[Unit]; + RegUnitRanges[Unit] = nullptr; + } + + /// 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); + + /// Split separate components in LiveInterval \p LI into separate intervals. + void splitSeparateComponents(LiveInterval &LI, + SmallVectorImpl &SplitLIs); + + /// For live interval \p LI with correct SubRanges construct matching + /// information for the main live range. Expects the main live range to not + /// have any segments or value numbers. + void constructMainRangeFromSubranges(LiveInterval &LI); + + private: + /// Compute live intervals for all virtual registers. + void computeVirtRegs(); + + /// 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 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, + LaneBitmask LaneMask = LaneBitmask::getAll()); + + class HMEditor; + }; + +} // end namespace llvm + +#endif // LLVM_CODEGEN_LIVEINTERVALANALYSIS_H Index: include/llvm/Target/TargetSubtargetInfo.h =================================================================== --- include/llvm/Target/TargetSubtargetInfo.h +++ include/llvm/Target/TargetSubtargetInfo.h @@ -1,248 +1,253 @@ -//===- llvm/Target/TargetSubtargetInfo.h - Target Information ---*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file describes the subtarget options of a Target machine. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_TARGET_TARGETSUBTARGETINFO_H -#define LLVM_TARGET_TARGETSUBTARGETINFO_H - -#include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/StringRef.h" -#include "llvm/CodeGen/PBQPRAConstraint.h" -#include "llvm/CodeGen/ScheduleDAGMutation.h" -#include "llvm/CodeGen/SchedulerRegistry.h" -#include "llvm/MC/MCSubtargetInfo.h" -#include "llvm/Support/CodeGen.h" -#include -#include - - -namespace llvm { - -class CallLowering; -class InstrItineraryData; -struct InstrStage; -class InstructionSelector; -class LegalizerInfo; -class MachineInstr; -struct MachineSchedPolicy; -struct MCReadAdvanceEntry; -struct MCWriteLatencyEntry; -struct MCWriteProcResEntry; -class RegisterBankInfo; -class SDep; -class SelectionDAGTargetInfo; -struct SubtargetFeatureKV; -struct SubtargetInfoKV; -class SUnit; -class TargetFrameLowering; -class TargetInstrInfo; -class TargetLowering; -class TargetRegisterClass; -class TargetRegisterInfo; -class TargetSchedModel; -class Triple; - -//===----------------------------------------------------------------------===// -/// -/// TargetSubtargetInfo - Generic base class for all target subtargets. All -/// Target-specific options that control code generation and printing should -/// be exposed through a TargetSubtargetInfo-derived class. -/// -class TargetSubtargetInfo : public MCSubtargetInfo { -protected: // Can only create subclasses... - TargetSubtargetInfo(const Triple &TT, StringRef CPU, StringRef FS, - ArrayRef PF, - ArrayRef PD, - const SubtargetInfoKV *ProcSched, - const MCWriteProcResEntry *WPR, - const MCWriteLatencyEntry *WL, - const MCReadAdvanceEntry *RA, const InstrStage *IS, - const unsigned *OC, const unsigned *FP); - -public: - // AntiDepBreakMode - Type of anti-dependence breaking that should - // be performed before post-RA scheduling. - using AntiDepBreakMode = enum { ANTIDEP_NONE, ANTIDEP_CRITICAL, ANTIDEP_ALL }; - using RegClassVector = SmallVectorImpl; - - TargetSubtargetInfo() = delete; - TargetSubtargetInfo(const TargetSubtargetInfo &) = delete; - TargetSubtargetInfo &operator=(const TargetSubtargetInfo &) = delete; - ~TargetSubtargetInfo() override; - - virtual bool isXRaySupported() const { return false; } - - // Interfaces to the major aspects of target machine information: - // - // -- Instruction opcode and operand information - // -- Pipelines and scheduling information - // -- Stack frame information - // -- Selection DAG lowering information - // -- Call lowering information - // - // N.B. These objects may change during compilation. It's not safe to cache - // them between functions. - virtual const TargetInstrInfo *getInstrInfo() const { return nullptr; } - virtual const TargetFrameLowering *getFrameLowering() const { - return nullptr; - } - virtual const TargetLowering *getTargetLowering() const { return nullptr; } - virtual const SelectionDAGTargetInfo *getSelectionDAGInfo() const { - return nullptr; - } - virtual const CallLowering *getCallLowering() const { return nullptr; } - - // FIXME: This lets targets specialize the selector by subtarget (which lets - // us do things like a dedicated avx512 selector). However, we might want - // to also specialize selectors by MachineFunction, which would let us be - // aware of optsize/optnone and such. - virtual const InstructionSelector *getInstructionSelector() const { - return nullptr; - } - - /// Target can subclass this hook to select a different DAG scheduler. - virtual RegisterScheduler::FunctionPassCtor - getDAGScheduler(CodeGenOpt::Level) const { - return nullptr; - } - - virtual const LegalizerInfo *getLegalizerInfo() const { return nullptr; } - - /// getRegisterInfo - If register information is available, return it. If - /// not, return null. - virtual const TargetRegisterInfo *getRegisterInfo() const { return nullptr; } - - /// If the information for the register banks is available, return it. - /// Otherwise return nullptr. - virtual const RegisterBankInfo *getRegBankInfo() const { return nullptr; } - - /// getInstrItineraryData - Returns instruction itinerary data for the target - /// or specific subtarget. - virtual const InstrItineraryData *getInstrItineraryData() const { - return nullptr; - } - - /// Resolve a SchedClass at runtime, where SchedClass identifies an - /// MCSchedClassDesc with the isVariant property. This may return the ID of - /// another variant SchedClass, but repeated invocation must quickly terminate - /// in a nonvariant SchedClass. - virtual unsigned resolveSchedClass(unsigned SchedClass, - const MachineInstr *MI, - const TargetSchedModel *SchedModel) const { - return 0; - } - - /// \brief True if the subtarget should run MachineScheduler after aggressive - /// coalescing. - /// - /// This currently replaces the SelectionDAG scheduler with the "source" order - /// scheduler (though see below for an option to turn this off and use the - /// TargetLowering preference). It does not yet disable the postRA scheduler. - virtual bool enableMachineScheduler() const; - - /// \brief Support printing of [latency:throughput] comment in output .S file. - virtual bool supportPrintSchedInfo() const { return false; } - - /// \brief True if the machine scheduler should disable the TLI preference - /// for preRA scheduling with the source level scheduler. - virtual bool enableMachineSchedDefaultSched() const { return true; } - - /// \brief True if the subtarget should enable joining global copies. - /// - /// By default this is enabled if the machine scheduler is enabled, but - /// can be overridden. - virtual bool enableJoinGlobalCopies() const; - - /// True if the subtarget should run a scheduler after register allocation. - /// - /// By default this queries the PostRAScheduling bit in the scheduling model - /// which is the preferred way to influence this. - virtual bool enablePostRAScheduler() const; - - /// \brief True if the subtarget should run the atomic expansion pass. - virtual bool enableAtomicExpand() const; - - /// \brief Override generic scheduling policy within a region. - /// - /// This is a convenient way for targets that don't provide any custom - /// scheduling heuristics (no custom MachineSchedStrategy) to make - /// changes to the generic scheduling policy. - virtual void overrideSchedPolicy(MachineSchedPolicy &Policy, - unsigned NumRegionInstrs) const {} - - // \brief Perform target specific adjustments to the latency of a schedule - // dependency. - virtual void adjustSchedDependency(SUnit *def, SUnit *use, SDep &dep) const {} - - // For use with PostRAScheduling: get the anti-dependence breaking that should - // be performed before post-RA scheduling. - virtual AntiDepBreakMode getAntiDepBreakMode() const { return ANTIDEP_NONE; } - - // For use with PostRAScheduling: in CriticalPathRCs, return any register - // classes that should only be considered for anti-dependence breaking if they - // are on the critical path. - virtual void getCriticalPathRCs(RegClassVector &CriticalPathRCs) const { - return CriticalPathRCs.clear(); - } - - // \brief Provide an ordered list of schedule DAG mutations for the post-RA - // scheduler. - virtual void getPostRAMutations( - std::vector> &Mutations) const { - } - - // \brief Provide an ordered list of schedule DAG mutations for the machine - // pipeliner. - virtual void getSMSMutations( - std::vector> &Mutations) const { - } - - // For use with PostRAScheduling: get the minimum optimization level needed - // to enable post-RA scheduling. - virtual CodeGenOpt::Level getOptLevelToEnablePostRAScheduler() const { - return CodeGenOpt::Default; - } - - /// \brief True if the subtarget should run the local reassignment - /// heuristic of the register allocator. - /// This heuristic may be compile time intensive, \p OptLevel provides - /// a finer grain to tune the register allocator. - virtual bool enableRALocalReassignment(CodeGenOpt::Level OptLevel) const; - - /// \brief Enable use of alias analysis during code generation (during MI - /// scheduling, DAGCombine, etc.). - virtual bool useAA() const; - - /// \brief Enable the use of the early if conversion pass. - virtual bool enableEarlyIfConversion() const { return false; } - - /// \brief Return PBQPConstraint(s) for the target. - /// - /// Override to provide custom PBQP constraints. - virtual std::unique_ptr getCustomPBQPConstraints() const { - return nullptr; - } - - /// Enable tracking of subregister liveness in register allocator. - /// Please use MachineRegisterInfo::subRegLivenessEnabled() instead where - /// possible. - virtual bool enableSubRegLiveness() const { return false; } - - /// Returns string representation of scheduler comment - std::string getSchedInfoStr(const MachineInstr &MI) const override; - std::string getSchedInfoStr(MCInst const &MCI) const override; -}; - -} // end namespace llvm - -#endif // LLVM_TARGET_TARGETSUBTARGETINFO_H +//===- llvm/Target/TargetSubtargetInfo.h - Target Information ---*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file describes the subtarget options of a Target machine. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TARGET_TARGETSUBTARGETINFO_H +#define LLVM_TARGET_TARGETSUBTARGETINFO_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/CodeGen/PBQPRAConstraint.h" +#include "llvm/CodeGen/ScheduleDAGMutation.h" +#include "llvm/CodeGen/SchedulerRegistry.h" +#include "llvm/MC/MCSubtargetInfo.h" +#include "llvm/Support/CodeGen.h" +#include +#include + + +namespace llvm { + +class CallLowering; +class InstrItineraryData; +struct InstrStage; +class InstructionSelector; +class LegalizerInfo; +class MachineInstr; +struct MachineSchedPolicy; +struct MCReadAdvanceEntry; +struct MCWriteLatencyEntry; +struct MCWriteProcResEntry; +class RegisterBankInfo; +class SDep; +class SelectionDAGTargetInfo; +struct SubtargetFeatureKV; +struct SubtargetInfoKV; +class SUnit; +class TargetFrameLowering; +class TargetInstrInfo; +class TargetLowering; +class TargetRegisterClass; +class TargetRegisterInfo; +class TargetSchedModel; +class Triple; + +//===----------------------------------------------------------------------===// +/// +/// TargetSubtargetInfo - Generic base class for all target subtargets. All +/// Target-specific options that control code generation and printing should +/// be exposed through a TargetSubtargetInfo-derived class. +/// +class TargetSubtargetInfo : public MCSubtargetInfo { +protected: // Can only create subclasses... + TargetSubtargetInfo(const Triple &TT, StringRef CPU, StringRef FS, + ArrayRef PF, + ArrayRef PD, + const SubtargetInfoKV *ProcSched, + const MCWriteProcResEntry *WPR, + const MCWriteLatencyEntry *WL, + const MCReadAdvanceEntry *RA, const InstrStage *IS, + const unsigned *OC, const unsigned *FP); + +public: + // AntiDepBreakMode - Type of anti-dependence breaking that should + // be performed before post-RA scheduling. + using AntiDepBreakMode = enum { ANTIDEP_NONE, ANTIDEP_CRITICAL, ANTIDEP_ALL }; + using RegClassVector = SmallVectorImpl; + + TargetSubtargetInfo() = delete; + TargetSubtargetInfo(const TargetSubtargetInfo &) = delete; + TargetSubtargetInfo &operator=(const TargetSubtargetInfo &) = delete; + ~TargetSubtargetInfo() override; + + virtual bool isXRaySupported() const { return false; } + + // Interfaces to the major aspects of target machine information: + // + // -- Instruction opcode and operand information + // -- Pipelines and scheduling information + // -- Stack frame information + // -- Selection DAG lowering information + // -- Call lowering information + // + // N.B. These objects may change during compilation. It's not safe to cache + // them between functions. + virtual const TargetInstrInfo *getInstrInfo() const { return nullptr; } + virtual const TargetFrameLowering *getFrameLowering() const { + return nullptr; + } + virtual const TargetLowering *getTargetLowering() const { return nullptr; } + virtual const SelectionDAGTargetInfo *getSelectionDAGInfo() const { + return nullptr; + } + virtual const CallLowering *getCallLowering() const { return nullptr; } + + // FIXME: This lets targets specialize the selector by subtarget (which lets + // us do things like a dedicated avx512 selector). However, we might want + // to also specialize selectors by MachineFunction, which would let us be + // aware of optsize/optnone and such. + virtual const InstructionSelector *getInstructionSelector() const { + return nullptr; + } + + /// Target can subclass this hook to select a different DAG scheduler. + virtual RegisterScheduler::FunctionPassCtor + getDAGScheduler(CodeGenOpt::Level) const { + return nullptr; + } + + virtual const LegalizerInfo *getLegalizerInfo() const { return nullptr; } + + /// getRegisterInfo - If register information is available, return it. If + /// not, return null. + virtual const TargetRegisterInfo *getRegisterInfo() const { return nullptr; } + + /// If the information for the register banks is available, return it. + /// Otherwise return nullptr. + virtual const RegisterBankInfo *getRegBankInfo() const { return nullptr; } + + /// getInstrItineraryData - Returns instruction itinerary data for the target + /// or specific subtarget. + virtual const InstrItineraryData *getInstrItineraryData() const { + return nullptr; + } + + /// Resolve a SchedClass at runtime, where SchedClass identifies an + /// MCSchedClassDesc with the isVariant property. This may return the ID of + /// another variant SchedClass, but repeated invocation must quickly terminate + /// in a nonvariant SchedClass. + virtual unsigned resolveSchedClass(unsigned SchedClass, + const MachineInstr *MI, + const TargetSchedModel *SchedModel) const { + return 0; + } + + /// \brief True if the subtarget should run MachineScheduler after aggressive + /// coalescing. + /// + /// This currently replaces the SelectionDAG scheduler with the "source" order + /// scheduler (though see below for an option to turn this off and use the + /// TargetLowering preference). It does not yet disable the postRA scheduler. + virtual bool enableMachineScheduler() const; + + /// \brief Support printing of [latency:throughput] comment in output .S file. + virtual bool supportPrintSchedInfo() const { return false; } + + /// \brief True if the machine scheduler should disable the TLI preference + /// for preRA scheduling with the source level scheduler. + virtual bool enableMachineSchedDefaultSched() const { return true; } + + /// \brief True if the subtarget should enable joining global copies. + /// + /// By default this is enabled if the machine scheduler is enabled, but + /// can be overridden. + virtual bool enableJoinGlobalCopies() const; + + /// True if the subtarget should run a scheduler after register allocation. + /// + /// By default this queries the PostRAScheduling bit in the scheduling model + /// which is the preferred way to influence this. + virtual bool enablePostRAScheduler() const; + + /// \brief True if the subtarget should run the atomic expansion pass. + virtual bool enableAtomicExpand() const; + + /// \brief Override generic scheduling policy within a region. + /// + /// This is a convenient way for targets that don't provide any custom + /// scheduling heuristics (no custom MachineSchedStrategy) to make + /// changes to the generic scheduling policy. + virtual void overrideSchedPolicy(MachineSchedPolicy &Policy, + unsigned NumRegionInstrs) const {} + + // \brief Perform target specific adjustments to the latency of a schedule + // dependency. + virtual void adjustSchedDependency(SUnit *def, SUnit *use, SDep &dep) const {} + + // For use with PostRAScheduling: get the anti-dependence breaking that should + // be performed before post-RA scheduling. + virtual AntiDepBreakMode getAntiDepBreakMode() const { return ANTIDEP_NONE; } + + // For use with PostRAScheduling: in CriticalPathRCs, return any register + // classes that should only be considered for anti-dependence breaking if they + // are on the critical path. + virtual void getCriticalPathRCs(RegClassVector &CriticalPathRCs) const { + return CriticalPathRCs.clear(); + } + + // \brief Provide an ordered list of schedule DAG mutations for the post-RA + // scheduler. + virtual void getPostRAMutations( + std::vector> &Mutations) const { + } + + // \brief Provide an ordered list of schedule DAG mutations for the machine + // pipeliner. + virtual void getSMSMutations( + std::vector> &Mutations) const { + } + + // For use with PostRAScheduling: get the minimum optimization level needed + // to enable post-RA scheduling. + virtual CodeGenOpt::Level getOptLevelToEnablePostRAScheduler() const { + return CodeGenOpt::Default; + } + + /// \brief True if the subtarget should run the local reassignment + /// heuristic of the register allocator. + /// This heuristic may be compile time intensive, \p OptLevel provides + /// a finer grain to tune the register allocator. + virtual bool enableRALocalReassignment(CodeGenOpt::Level OptLevel) const; + + /// \brief True if the subtarget should consider the cost of local intervals + /// created by a split candidate when choosing the best split candidate. This + /// heuristic may be compile time intensive. + virtual bool enableAdvancedRASplitCost() const; + + /// \brief Enable use of alias analysis during code generation (during MI + /// scheduling, DAGCombine, etc.). + virtual bool useAA() const; + + /// \brief Enable the use of the early if conversion pass. + virtual bool enableEarlyIfConversion() const { return false; } + + /// \brief Return PBQPConstraint(s) for the target. + /// + /// Override to provide custom PBQP constraints. + virtual std::unique_ptr getCustomPBQPConstraints() const { + return nullptr; + } + + /// Enable tracking of subregister liveness in register allocator. + /// Please use MachineRegisterInfo::subRegLivenessEnabled() instead where + /// possible. + virtual bool enableSubRegLiveness() const { return false; } + + /// Returns string representation of scheduler comment + std::string getSchedInfoStr(const MachineInstr &MI) const override; + std::string getSchedInfoStr(MCInst const &MCI) const override; +}; + +} // end namespace llvm + +#endif // LLVM_TARGET_TARGETSUBTARGETINFO_H Index: lib/CodeGen/CalcSpillWeights.cpp =================================================================== --- lib/CodeGen/CalcSpillWeights.cpp +++ lib/CodeGen/CalcSpillWeights.cpp @@ -1,236 +1,282 @@ -//===------------------------ CalcSpillWeights.cpp ------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "llvm/CodeGen/CalcSpillWeights.h" -#include "llvm/CodeGen/LiveIntervalAnalysis.h" -#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" -#include "llvm/CodeGen/MachineFunction.h" -#include "llvm/CodeGen/MachineLoopInfo.h" -#include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/VirtRegMap.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/Target/TargetSubtargetInfo.h" -using namespace llvm; - -#define DEBUG_TYPE "calcspillweights" - -void llvm::calculateSpillWeightsAndHints(LiveIntervals &LIS, - MachineFunction &MF, - VirtRegMap *VRM, - const MachineLoopInfo &MLI, - const MachineBlockFrequencyInfo &MBFI, - VirtRegAuxInfo::NormalizingFn norm) { - DEBUG(dbgs() << "********** Compute Spill Weights **********\n" - << "********** Function: " << MF.getName() << '\n'); - - MachineRegisterInfo &MRI = MF.getRegInfo(); - VirtRegAuxInfo VRAI(MF, LIS, VRM, MLI, MBFI, norm); - for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) { - unsigned Reg = TargetRegisterInfo::index2VirtReg(i); - if (MRI.reg_nodbg_empty(Reg)) - continue; - VRAI.calculateSpillWeightAndHint(LIS.getInterval(Reg)); - } -} - -// Return the preferred allocation register for reg, given a COPY instruction. -static unsigned copyHint(const MachineInstr *mi, unsigned reg, - const TargetRegisterInfo &tri, - const MachineRegisterInfo &mri) { - unsigned sub, hreg, hsub; - if (mi->getOperand(0).getReg() == reg) { - sub = mi->getOperand(0).getSubReg(); - hreg = mi->getOperand(1).getReg(); - hsub = mi->getOperand(1).getSubReg(); - } else { - sub = mi->getOperand(1).getSubReg(); - hreg = mi->getOperand(0).getReg(); - hsub = mi->getOperand(0).getSubReg(); - } - - if (!hreg) - return 0; - - if (TargetRegisterInfo::isVirtualRegister(hreg)) - return sub == hsub ? hreg : 0; - - const TargetRegisterClass *rc = mri.getRegClass(reg); - - // Only allow physreg hints in rc. - if (sub == 0) - return rc->contains(hreg) ? hreg : 0; - - // reg:sub should match the physreg hreg. - return tri.getMatchingSuperReg(hreg, sub, rc); -} - -// Check if all values in LI are rematerializable -static bool isRematerializable(const LiveInterval &LI, - const LiveIntervals &LIS, - VirtRegMap *VRM, - const TargetInstrInfo &TII) { - unsigned Reg = LI.reg; - unsigned Original = VRM ? VRM->getOriginal(Reg) : 0; - for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end(); - I != E; ++I) { - const VNInfo *VNI = *I; - if (VNI->isUnused()) - continue; - if (VNI->isPHIDef()) - return false; - - MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); - assert(MI && "Dead valno in interval"); - - // Trace copies introduced by live range splitting. The inline - // spiller can rematerialize through these copies, so the spill - // weight must reflect this. - if (VRM) { - while (MI->isFullCopy()) { - // The copy destination must match the interval register. - if (MI->getOperand(0).getReg() != Reg) - return false; - - // Get the source register. - Reg = MI->getOperand(1).getReg(); - - // If the original (pre-splitting) registers match this - // copy came from a split. - if (!TargetRegisterInfo::isVirtualRegister(Reg) || - VRM->getOriginal(Reg) != Original) - return false; - - // Follow the copy live-in value. - const LiveInterval &SrcLI = LIS.getInterval(Reg); - LiveQueryResult SrcQ = SrcLI.Query(VNI->def); - VNI = SrcQ.valueIn(); - assert(VNI && "Copy from non-existing value"); - if (VNI->isPHIDef()) - return false; - MI = LIS.getInstructionFromIndex(VNI->def); - assert(MI && "Dead valno in interval"); - } - } - - if (!TII.isTriviallyReMaterializable(*MI, LIS.getAliasAnalysis())) - return false; - } - return true; -} - -void -VirtRegAuxInfo::calculateSpillWeightAndHint(LiveInterval &li) { - MachineRegisterInfo &mri = MF.getRegInfo(); - const TargetRegisterInfo &tri = *MF.getSubtarget().getRegisterInfo(); - MachineBasicBlock *mbb = nullptr; - MachineLoop *loop = nullptr; - bool isExiting = false; - float totalWeight = 0; - unsigned numInstr = 0; // Number of instructions using li - SmallPtrSet visited; - - // Find the best physreg hint and the best virtreg hint. - float bestPhys = 0, bestVirt = 0; - unsigned hintPhys = 0, hintVirt = 0; - - // Don't recompute a target specific hint. - bool noHint = mri.getRegAllocationHint(li.reg).first != 0; - - // Don't recompute spill weight for an unspillable register. - bool Spillable = li.isSpillable(); - - for (MachineRegisterInfo::reg_instr_iterator - I = mri.reg_instr_begin(li.reg), E = mri.reg_instr_end(); - I != E; ) { - MachineInstr *mi = &*(I++); - numInstr++; - if (mi->isIdentityCopy() || mi->isImplicitDef() || mi->isDebugValue()) - continue; - if (!visited.insert(mi).second) - continue; - - float weight = 1.0f; - if (Spillable) { - // Get loop info for mi. - if (mi->getParent() != mbb) { - mbb = mi->getParent(); - loop = Loops.getLoopFor(mbb); - isExiting = loop ? loop->isLoopExiting(mbb) : false; - } - - // Calculate instr weight. - bool reads, writes; - std::tie(reads, writes) = mi->readsWritesVirtualRegister(li.reg); - weight = LiveIntervals::getSpillWeight(writes, reads, &MBFI, *mi); - - // Give extra weight to what looks like a loop induction variable update. - if (writes && isExiting && LIS.isLiveOutOfMBB(li, mbb)) - weight *= 3; - - totalWeight += weight; - } - - // Get allocation hints from copies. - if (noHint || !mi->isCopy()) - continue; - unsigned hint = copyHint(mi, li.reg, tri, mri); - if (!hint) - continue; - // Force hweight onto the stack so that x86 doesn't add hidden precision, - // making the comparison incorrectly pass (i.e., 1 > 1 == true??). - // - // FIXME: we probably shouldn't use floats at all. - volatile float hweight = Hint[hint] += weight; - if (TargetRegisterInfo::isPhysicalRegister(hint)) { - if (hweight > bestPhys && mri.isAllocatable(hint)) { - bestPhys = hweight; - hintPhys = hint; - } - } else { - if (hweight > bestVirt) { - bestVirt = hweight; - hintVirt = hint; - } - } - } - - Hint.clear(); - - // Always prefer the physreg hint. - if (unsigned hint = hintPhys ? hintPhys : hintVirt) { - mri.setRegAllocationHint(li.reg, 0, hint); - // Weakly boost the spill weight of hinted registers. - totalWeight *= 1.01F; - } - - // If the live interval was already unspillable, leave it that way. - if (!Spillable) - return; - - // Mark li as unspillable if all live ranges are tiny and the interval - // is not live at any reg mask. If the interval is live at a reg mask - // spilling may be required. - if (li.isZeroLength(LIS.getSlotIndexes()) && - !li.isLiveAtIndexes(LIS.getRegMaskSlots())) { - li.markNotSpillable(); - return; - } - - // If all of the definitions of the interval are re-materializable, - // it is a preferred candidate for spilling. - // FIXME: this gets much more complicated once we support non-trivial - // re-materialization. - if (isRematerializable(li, LIS, VRM, *MF.getSubtarget().getInstrInfo())) - totalWeight *= 0.5F; - - li.weight = normalize(totalWeight, li.getSize(), numInstr); -} +//===------------------------ CalcSpillWeights.cpp ------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/CalcSpillWeights.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/VirtRegMap.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" +using namespace llvm; + +#define DEBUG_TYPE "calcspillweights" + +void llvm::calculateSpillWeightsAndHints(LiveIntervals &LIS, + MachineFunction &MF, + VirtRegMap *VRM, + const MachineLoopInfo &MLI, + const MachineBlockFrequencyInfo &MBFI, + VirtRegAuxInfo::NormalizingFn norm) { + DEBUG(dbgs() << "********** Compute Spill Weights **********\n" + << "********** Function: " << MF.getName() << '\n'); + + MachineRegisterInfo &MRI = MF.getRegInfo(); + VirtRegAuxInfo VRAI(MF, LIS, VRM, MLI, MBFI, norm); + for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) { + unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + if (MRI.reg_nodbg_empty(Reg)) + continue; + VRAI.calculateSpillWeightAndHint(LIS.getInterval(Reg)); + } +} + +// Return the preferred allocation register for reg, given a COPY instruction. +static unsigned copyHint(const MachineInstr *mi, unsigned reg, + const TargetRegisterInfo &tri, + const MachineRegisterInfo &mri) { + unsigned sub, hreg, hsub; + if (mi->getOperand(0).getReg() == reg) { + sub = mi->getOperand(0).getSubReg(); + hreg = mi->getOperand(1).getReg(); + hsub = mi->getOperand(1).getSubReg(); + } else { + sub = mi->getOperand(1).getSubReg(); + hreg = mi->getOperand(0).getReg(); + hsub = mi->getOperand(0).getSubReg(); + } + + if (!hreg) + return 0; + + if (TargetRegisterInfo::isVirtualRegister(hreg)) + return sub == hsub ? hreg : 0; + + const TargetRegisterClass *rc = mri.getRegClass(reg); + + // Only allow physreg hints in rc. + if (sub == 0) + return rc->contains(hreg) ? hreg : 0; + + // reg:sub should match the physreg hreg. + return tri.getMatchingSuperReg(hreg, sub, rc); +} + +// Check if all values in LI are rematerializable +static bool isRematerializable(const LiveInterval &LI, + const LiveIntervals &LIS, + VirtRegMap *VRM, + const TargetInstrInfo &TII) { + unsigned Reg = LI.reg; + unsigned Original = VRM ? VRM->getOriginal(Reg) : 0; + for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end(); + I != E; ++I) { + const VNInfo *VNI = *I; + if (VNI->isUnused()) + continue; + if (VNI->isPHIDef()) + return false; + + MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); + assert(MI && "Dead valno in interval"); + + // Trace copies introduced by live range splitting. The inline + // spiller can rematerialize through these copies, so the spill + // weight must reflect this. + if (VRM) { + while (MI->isFullCopy()) { + // The copy destination must match the interval register. + if (MI->getOperand(0).getReg() != Reg) + return false; + + // Get the source register. + Reg = MI->getOperand(1).getReg(); + + // If the original (pre-splitting) registers match this + // copy came from a split. + if (!TargetRegisterInfo::isVirtualRegister(Reg) || + VRM->getOriginal(Reg) != Original) + return false; + + // Follow the copy live-in value. + const LiveInterval &SrcLI = LIS.getInterval(Reg); + LiveQueryResult SrcQ = SrcLI.Query(VNI->def); + VNI = SrcQ.valueIn(); + assert(VNI && "Copy from non-existing value"); + if (VNI->isPHIDef()) + return false; + MI = LIS.getInstructionFromIndex(VNI->def); + assert(MI && "Dead valno in interval"); + } + } + + if (!TII.isTriviallyReMaterializable(*MI, LIS.getAliasAnalysis())) + return false; + } + return true; +} + +void VirtRegAuxInfo::calculateSpillWeightAndHint(LiveInterval &li) { + float weight = weightCalcHelper(li); + // Check if unspillable. + if (weight < 0) + return; + li.weight = weight; +} + +float VirtRegAuxInfo::futureWeight(LiveInterval &li, SlotIndex start, + SlotIndex end) { + return weightCalcHelper(li, &start, &end); +} + +float VirtRegAuxInfo::weightCalcHelper(LiveInterval &li, SlotIndex *start, + SlotIndex *end) { + MachineRegisterInfo &mri = MF.getRegInfo(); + const TargetRegisterInfo &tri = *MF.getSubtarget().getRegisterInfo(); + MachineBasicBlock *mbb = nullptr; + MachineLoop *loop = nullptr; + bool isExiting = false; + float totalWeight = 0; + unsigned numInstr = 0; // Number of instructions using li + SmallPtrSet visited; + + // Find the best physreg hint and the best virtreg hint. + float bestPhys = 0, bestVirt = 0; + unsigned hintPhys = 0, hintVirt = 0; + + // Don't recompute a target specific hint. + bool noHint = mri.getRegAllocationHint(li.reg).first != 0; + + // Don't recompute spill weight for an unspillable register. + bool Spillable = li.isSpillable(); + + bool LocalSplitArtifact = start && end; + + // Do not update future local split artifacts. + bool UpdateLI = !LocalSplitArtifact; + + if (LocalSplitArtifact) { + MachineBasicBlock *LocalMBB = LIS.getMBBFromIndex(*end); + assert(LocalMBB == LIS.getMBBFromIndex(*start) && + "start and end are expected to be in the same basic block"); + + // Local split artifact will have 2 additional copy instructions and they + // will be in the same BB. + // localLI = COPY other + // ... + // other = COPY localLI + totalWeight += LiveIntervals::getSpillWeight(true, false, &MBFI, LocalMBB); + totalWeight += LiveIntervals::getSpillWeight(false, true, &MBFI, LocalMBB); + + numInstr += 2; + } + + for (MachineRegisterInfo::reg_instr_iterator + I = mri.reg_instr_begin(li.reg), E = mri.reg_instr_end(); + I != E; ) { + MachineInstr *mi = &*(I++); + + // For local split artifacts, we are interested only in instructions between + // the expected start and end of the range. + SlotIndex SI = LIS.getInstructionIndex(*mi); + if (LocalSplitArtifact && ((SI < *start) || (SI > *end))) + continue; + + numInstr++; + if (mi->isIdentityCopy() || mi->isImplicitDef() || mi->isDebugValue()) + continue; + if (!visited.insert(mi).second) + continue; + + float weight = 1.0f; + if (Spillable) { + // Get loop info for mi. + if (mi->getParent() != mbb) { + mbb = mi->getParent(); + loop = Loops.getLoopFor(mbb); + isExiting = loop ? loop->isLoopExiting(mbb) : false; + } + + // Calculate instr weight. + bool reads, writes; + std::tie(reads, writes) = mi->readsWritesVirtualRegister(li.reg); + weight = LiveIntervals::getSpillWeight(writes, reads, &MBFI, *mi); + + // Give extra weight to what looks like a loop induction variable update. + if (writes && isExiting && LIS.isLiveOutOfMBB(li, mbb)) + weight *= 3; + + totalWeight += weight; + } + + // Get allocation hints from copies. + if (noHint || !mi->isCopy()) + continue; + unsigned hint = copyHint(mi, li.reg, tri, mri); + if (!hint) + continue; + // Force hweight onto the stack so that x86 doesn't add hidden precision, + // making the comparison incorrectly pass (i.e., 1 > 1 == true??). + // + // FIXME: we probably shouldn't use floats at all. + volatile float hweight = Hint[hint] += weight; + if (TargetRegisterInfo::isPhysicalRegister(hint)) { + if (hweight > bestPhys && mri.isAllocatable(hint)) { + bestPhys = hweight; + hintPhys = hint; + } + } else { + if (hweight > bestVirt) { + bestVirt = hweight; + hintVirt = hint; + } + } + } + + Hint.clear(); + + // Always prefer the physreg hint. + if (UpdateLI) { + if (unsigned hint = hintPhys ? hintPhys : hintVirt) { + mri.setRegAllocationHint(li.reg, 0, hint); + // Weakly boost the spill weight of hinted registers. + totalWeight *= 1.01F; + } + } + + // If the live interval was already unspillable, leave it that way. + if (!Spillable) + return -1.0; + + // Mark li as unspillable if all live ranges are tiny and the interval + // is not live at any reg mask. If the interval is live at a reg mask + // spilling may be required. + if (UpdateLI && li.isZeroLength(LIS.getSlotIndexes()) && + !li.isLiveAtIndexes(LIS.getRegMaskSlots())) { + li.markNotSpillable(); + return -1.0; + } + + // If all of the definitions of the interval are re-materializable, + // it is a preferred candidate for spilling. + // FIXME: this gets much more complicated once we support non-trivial + // re-materialization. + if (isRematerializable(li, LIS, VRM, *MF.getSubtarget().getInstrInfo())) + totalWeight *= 0.5F; + + if (LocalSplitArtifact) + return normalize(totalWeight, start->distance(*end), numInstr); + return normalize(totalWeight, li.getSize(), numInstr); +} + Index: lib/CodeGen/LiveIntervalAnalysis.cpp =================================================================== --- lib/CodeGen/LiveIntervalAnalysis.cpp +++ lib/CodeGen/LiveIntervalAnalysis.cpp @@ -1,1588 +1,1594 @@ -//===- LiveIntervalAnalysis.cpp - Live Interval Analysis ------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -/// \file This file implements the LiveInterval analysis pass which is used -/// by the Linear Scan Register allocator. This pass linearizes the -/// basic blocks of the function in DFS order and computes live intervals for -/// each virtual and physical register. -// -//===----------------------------------------------------------------------===// - -#include "llvm/CodeGen/LiveIntervalAnalysis.h" -#include "LiveRangeCalc.h" -#include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/DepthFirstIterator.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/iterator_range.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/CodeGen/LiveInterval.h" -#include "llvm/CodeGen/LiveVariables.h" -#include "llvm/CodeGen/MachineBasicBlock.h" -#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" -#include "llvm/CodeGen/MachineDominators.h" -#include "llvm/CodeGen/MachineFunction.h" -#include "llvm/CodeGen/MachineInstr.h" -#include "llvm/CodeGen/MachineInstrBundle.h" -#include "llvm/CodeGen/MachineOperand.h" -#include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/Passes.h" -#include "llvm/CodeGen/SlotIndexes.h" -#include "llvm/CodeGen/VirtRegMap.h" -#include "llvm/MC/LaneBitmask.h" -#include "llvm/MC/MCRegisterInfo.h" -#include "llvm/Pass.h" -#include "llvm/Support/BlockFrequency.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Compiler.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/MathExtras.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/Target/TargetSubtargetInfo.h" -#include -#include -#include -#include -#include -#include - -using namespace llvm; - -#define DEBUG_TYPE "regalloc" - -char LiveIntervals::ID = 0; -char &llvm::LiveIntervalsID = LiveIntervals::ID; -INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", - "Live Interval Analysis", false, false) -INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) -INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) -INITIALIZE_PASS_DEPENDENCY(SlotIndexes) -INITIALIZE_PASS_END(LiveIntervals, "liveintervals", - "Live Interval Analysis", false, false) - -#ifndef NDEBUG -static cl::opt EnablePrecomputePhysRegs( - "precompute-phys-liveness", cl::Hidden, - cl::desc("Eagerly compute live intervals for all physreg units.")); -#else -static bool EnablePrecomputePhysRegs = false; -#endif // NDEBUG - -namespace llvm { - -cl::opt UseSegmentSetForPhysRegs( - "use-segment-set-for-physregs", cl::Hidden, cl::init(true), - cl::desc( - "Use segment set for the computation of the live ranges of physregs.")); - -} // end namespace llvm - -void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesCFG(); - AU.addRequired(); - AU.addPreserved(); - AU.addPreserved(); - AU.addPreservedID(MachineLoopInfoID); - AU.addRequiredTransitiveID(MachineDominatorsID); - AU.addPreservedID(MachineDominatorsID); - AU.addPreserved(); - AU.addRequiredTransitive(); - MachineFunctionPass::getAnalysisUsage(AU); -} - -LiveIntervals::LiveIntervals() : MachineFunctionPass(ID) { - initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); -} - -LiveIntervals::~LiveIntervals() { - delete LRCalc; -} - -void LiveIntervals::releaseMemory() { - // Free the live intervals themselves. - for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i) - delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)]; - VirtRegIntervals.clear(); - RegMaskSlots.clear(); - RegMaskBits.clear(); - RegMaskBlocks.clear(); - - for (LiveRange *LR : RegUnitRanges) - delete LR; - RegUnitRanges.clear(); - - // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd. - VNInfoAllocator.Reset(); -} - -bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { - MF = &fn; - MRI = &MF->getRegInfo(); - TRI = MF->getSubtarget().getRegisterInfo(); - TII = MF->getSubtarget().getInstrInfo(); - AA = &getAnalysis().getAAResults(); - Indexes = &getAnalysis(); - DomTree = &getAnalysis(); - - if (!LRCalc) - LRCalc = new LiveRangeCalc(); - - // Allocate space for all virtual registers. - VirtRegIntervals.resize(MRI->getNumVirtRegs()); - - computeVirtRegs(); - computeRegMasks(); - computeLiveInRegUnits(); - - if (EnablePrecomputePhysRegs) { - // For stress testing, precompute live ranges of all physical register - // units, including reserved registers. - for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i) - getRegUnit(i); - } - DEBUG(dump()); - return true; -} - -void LiveIntervals::print(raw_ostream &OS, const Module* ) const { - OS << "********** INTERVALS **********\n"; - - // Dump the regunits. - for (unsigned Unit = 0, UnitE = RegUnitRanges.size(); Unit != UnitE; ++Unit) - if (LiveRange *LR = RegUnitRanges[Unit]) - OS << PrintRegUnit(Unit, TRI) << ' ' << *LR << '\n'; - - // Dump the virtregs. - for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { - unsigned Reg = TargetRegisterInfo::index2VirtReg(i); - if (hasInterval(Reg)) - OS << getInterval(Reg) << '\n'; - } - - OS << "RegMasks:"; - for (SlotIndex Idx : RegMaskSlots) - OS << ' ' << Idx; - OS << '\n'; - - printInstrs(OS); -} - -void LiveIntervals::printInstrs(raw_ostream &OS) const { - OS << "********** MACHINEINSTRS **********\n"; - MF->print(OS, Indexes); -} - -#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) -LLVM_DUMP_METHOD void LiveIntervals::dumpInstrs() const { - printInstrs(dbgs()); -} -#endif - -LiveInterval* LiveIntervals::createInterval(unsigned reg) { - float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? huge_valf : 0.0F; - return new LiveInterval(reg, Weight); -} - -/// Compute the live interval of a virtual register, based on defs and uses. -void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { - assert(LRCalc && "LRCalc not initialized."); - assert(LI.empty() && "Should only compute empty intervals."); - LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); - LRCalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg)); - computeDeadValues(LI, nullptr); -} - -void LiveIntervals::computeVirtRegs() { - for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { - unsigned Reg = TargetRegisterInfo::index2VirtReg(i); - if (MRI->reg_nodbg_empty(Reg)) - continue; - createAndComputeVirtRegInterval(Reg); - } -} - -void LiveIntervals::computeRegMasks() { - RegMaskBlocks.resize(MF->getNumBlockIDs()); - - // Find all instructions with regmask operands. - for (const MachineBasicBlock &MBB : *MF) { - std::pair &RMB = RegMaskBlocks[MBB.getNumber()]; - RMB.first = RegMaskSlots.size(); - - // Some block starts, such as EH funclets, create masks. - if (const uint32_t *Mask = MBB.getBeginClobberMask(TRI)) { - RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB)); - RegMaskBits.push_back(Mask); - } - - for (const MachineInstr &MI : MBB) { - for (const MachineOperand &MO : MI.operands()) { - if (!MO.isRegMask()) - continue; - RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot()); - RegMaskBits.push_back(MO.getRegMask()); - } - } - - // Some block ends, such as funclet returns, create masks. Put the mask on - // the last instruction of the block, because MBB slot index intervals are - // half-open. - if (const uint32_t *Mask = MBB.getEndClobberMask(TRI)) { - assert(!MBB.empty() && "empty return block?"); - RegMaskSlots.push_back( - Indexes->getInstructionIndex(MBB.back()).getRegSlot()); - RegMaskBits.push_back(Mask); - } - - // Compute the number of register mask instructions in this block. - RMB.second = RegMaskSlots.size() - RMB.first; - } -} - -//===----------------------------------------------------------------------===// -// Register Unit Liveness -//===----------------------------------------------------------------------===// -// -// Fixed interference typically comes from ABI boundaries: Function arguments -// and return values are passed in fixed registers, and so are exception -// pointers entering landing pads. Certain instructions require values to be -// present in specific registers. That is also represented through fixed -// interference. -// - -/// Compute the live range of a register unit, based on the uses and defs of -/// aliasing registers. The range should be empty, or contain only dead -/// phi-defs from ABI blocks. -void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) { - assert(LRCalc && "LRCalc not initialized."); - LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); - - // The physregs aliasing Unit are the roots and their super-registers. - // Create all values as dead defs before extending to uses. Note that roots - // may share super-registers. That's OK because createDeadDefs() is - // idempotent. It is very rare for a register unit to have multiple roots, so - // uniquing super-registers is probably not worthwhile. - bool IsReserved = true; - for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) { - for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true); - Super.isValid(); ++Super) { - unsigned Reg = *Super; - if (!MRI->reg_empty(Reg)) - LRCalc->createDeadDefs(LR, Reg); - // A register unit is considered reserved if all its roots and all their - // super registers are reserved. - if (!MRI->isReserved(Reg)) - IsReserved = false; - } - } - - // Now extend LR to reach all uses. - // Ignore uses of reserved registers. We only track defs of those. - if (!IsReserved) { - for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) { - for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true); - Super.isValid(); ++Super) { - unsigned Reg = *Super; - if (!MRI->reg_empty(Reg)) - LRCalc->extendToUses(LR, Reg); - } - } - } - - // Flush the segment set to the segment vector. - if (UseSegmentSetForPhysRegs) - LR.flushSegmentSet(); -} - -/// Precompute the live ranges of any register units that are live-in to an ABI -/// block somewhere. Register values can appear without a corresponding def when -/// entering the entry block or a landing pad. -void LiveIntervals::computeLiveInRegUnits() { - RegUnitRanges.resize(TRI->getNumRegUnits()); - DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n"); - - // Keep track of the live range sets allocated. - SmallVector NewRanges; - - // Check all basic blocks for live-ins. - for (const MachineBasicBlock &MBB : *MF) { - // We only care about ABI blocks: Entry + landing pads. - if ((&MBB != &MF->front() && !MBB.isEHPad()) || MBB.livein_empty()) - continue; - - // Create phi-defs at Begin for all live-in registers. - SlotIndex Begin = Indexes->getMBBStartIdx(&MBB); - DEBUG(dbgs() << Begin << "\tBB#" << MBB.getNumber()); - for (const auto &LI : MBB.liveins()) { - for (MCRegUnitIterator Units(LI.PhysReg, TRI); Units.isValid(); ++Units) { - unsigned Unit = *Units; - LiveRange *LR = RegUnitRanges[Unit]; - if (!LR) { - // Use segment set to speed-up initial computation of the live range. - LR = RegUnitRanges[Unit] = new LiveRange(UseSegmentSetForPhysRegs); - NewRanges.push_back(Unit); - } - VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator()); - (void)VNI; - DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id); - } - } - DEBUG(dbgs() << '\n'); - } - DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n"); - - // Compute the 'normal' part of the ranges. - for (unsigned Unit : NewRanges) - computeRegUnitRange(*RegUnitRanges[Unit], Unit); -} - -static void createSegmentsForValues(LiveRange &LR, - iterator_range VNIs) { - for (VNInfo *VNI : VNIs) { - if (VNI->isUnused()) - continue; - SlotIndex Def = VNI->def; - LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI)); - } -} - -using ShrinkToUsesWorkList = SmallVector, 16>; - -static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes, - ShrinkToUsesWorkList &WorkList, - const LiveRange &OldRange) { - // Keep track of the PHIs that are in use. - SmallPtrSet UsedPHIs; - // Blocks that have already been added to WorkList as live-out. - SmallPtrSet LiveOut; - - // Extend intervals to reach all uses in WorkList. - while (!WorkList.empty()) { - SlotIndex Idx = WorkList.back().first; - VNInfo *VNI = WorkList.back().second; - WorkList.pop_back(); - const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(Idx.getPrevSlot()); - SlotIndex BlockStart = Indexes.getMBBStartIdx(MBB); - - // Extend the live range for VNI to be live at Idx. - if (VNInfo *ExtVNI = LR.extendInBlock(BlockStart, Idx)) { - assert(ExtVNI == VNI && "Unexpected existing value number"); - (void)ExtVNI; - // Is this a PHIDef we haven't seen before? - if (!VNI->isPHIDef() || VNI->def != BlockStart || - !UsedPHIs.insert(VNI).second) - continue; - // The PHI is live, make sure the predecessors are live-out. - for (const MachineBasicBlock *Pred : MBB->predecessors()) { - if (!LiveOut.insert(Pred).second) - continue; - SlotIndex Stop = Indexes.getMBBEndIdx(Pred); - // A predecessor is not required to have a live-out value for a PHI. - if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop)) - WorkList.push_back(std::make_pair(Stop, PVNI)); - } - continue; - } - - // VNI is live-in to MBB. - DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); - LR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI)); - - // Make sure VNI is live-out from the predecessors. - for (const MachineBasicBlock *Pred : MBB->predecessors()) { - if (!LiveOut.insert(Pred).second) - continue; - SlotIndex Stop = Indexes.getMBBEndIdx(Pred); - assert(OldRange.getVNInfoBefore(Stop) == VNI && - "Wrong value out of predecessor"); - WorkList.push_back(std::make_pair(Stop, VNI)); - } - } -} - -bool LiveIntervals::shrinkToUses(LiveInterval *li, - SmallVectorImpl *dead) { - DEBUG(dbgs() << "Shrink: " << *li << '\n'); - assert(TargetRegisterInfo::isVirtualRegister(li->reg) - && "Can only shrink virtual registers"); - - // Shrink subregister live ranges. - bool NeedsCleanup = false; - for (LiveInterval::SubRange &S : li->subranges()) { - shrinkToUses(S, li->reg); - if (S.empty()) - NeedsCleanup = true; - } - if (NeedsCleanup) - li->removeEmptySubRanges(); - - // Find all the values used, including PHI kills. - ShrinkToUsesWorkList WorkList; - - // Visit all instructions reading li->reg. - unsigned Reg = li->reg; - for (MachineInstr &UseMI : MRI->reg_instructions(Reg)) { - if (UseMI.isDebugValue() || !UseMI.readsVirtualRegister(Reg)) - continue; - SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); - LiveQueryResult LRQ = li->Query(Idx); - VNInfo *VNI = LRQ.valueIn(); - if (!VNI) { - // This shouldn't happen: readsVirtualRegister returns true, but there is - // no live value. It is likely caused by a target getting flags - // wrong. - DEBUG(dbgs() << Idx << '\t' << UseMI - << "Warning: Instr claims to read non-existent value in " - << *li << '\n'); - continue; - } - // Special case: An early-clobber tied operand reads and writes the - // register one slot early. - if (VNInfo *DefVNI = LRQ.valueDefined()) - Idx = DefVNI->def; - - WorkList.push_back(std::make_pair(Idx, VNI)); - } - - // Create new live ranges with only minimal live segments per def. - LiveRange NewLR; - createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end())); - extendSegmentsToUses(NewLR, *Indexes, WorkList, *li); - - // Move the trimmed segments back. - li->segments.swap(NewLR.segments); - - // Handle dead values. - bool CanSeparate = computeDeadValues(*li, dead); - DEBUG(dbgs() << "Shrunk: " << *li << '\n'); - return CanSeparate; -} - -bool LiveIntervals::computeDeadValues(LiveInterval &LI, - SmallVectorImpl *dead) { - bool MayHaveSplitComponents = false; - for (VNInfo *VNI : LI.valnos) { - if (VNI->isUnused()) - continue; - SlotIndex Def = VNI->def; - LiveRange::iterator I = LI.FindSegmentContaining(Def); - assert(I != LI.end() && "Missing segment for VNI"); - - // Is the register live before? Otherwise we may have to add a read-undef - // flag for subregister defs. - unsigned VReg = LI.reg; - if (MRI->shouldTrackSubRegLiveness(VReg)) { - if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) { - MachineInstr *MI = getInstructionFromIndex(Def); - MI->setRegisterDefReadUndef(VReg); - } - } - - if (I->end != Def.getDeadSlot()) - continue; - if (VNI->isPHIDef()) { - // This is a dead PHI. Remove it. - VNI->markUnused(); - LI.removeSegment(I); - DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n"); - MayHaveSplitComponents = true; - } else { - // This is a dead def. Make sure the instruction knows. - MachineInstr *MI = getInstructionFromIndex(Def); - assert(MI && "No instruction defining live value"); - MI->addRegisterDead(LI.reg, TRI); - if (dead && MI->allDefsAreDead()) { - DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI); - dead->push_back(MI); - } - } - } - return MayHaveSplitComponents; -} - -void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) { - DEBUG(dbgs() << "Shrink: " << SR << '\n'); - assert(TargetRegisterInfo::isVirtualRegister(Reg) - && "Can only shrink virtual registers"); - // Find all the values used, including PHI kills. - ShrinkToUsesWorkList WorkList; - - // Visit all instructions reading Reg. - SlotIndex LastIdx; - for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) { - // Skip "undef" uses. - if (!MO.readsReg()) - continue; - // Maybe the operand is for a subregister we don't care about. - unsigned SubReg = MO.getSubReg(); - if (SubReg != 0) { - LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg); - if ((LaneMask & SR.LaneMask).none()) - continue; - } - // We only need to visit each instruction once. - MachineInstr *UseMI = MO.getParent(); - SlotIndex Idx = getInstructionIndex(*UseMI).getRegSlot(); - if (Idx == LastIdx) - continue; - LastIdx = Idx; - - LiveQueryResult LRQ = SR.Query(Idx); - VNInfo *VNI = LRQ.valueIn(); - // For Subranges it is possible that only undef values are left in that - // part of the subregister, so there is no real liverange at the use - if (!VNI) - continue; - - // Special case: An early-clobber tied operand reads and writes the - // register one slot early. - if (VNInfo *DefVNI = LRQ.valueDefined()) - Idx = DefVNI->def; - - WorkList.push_back(std::make_pair(Idx, VNI)); - } - - // Create a new live ranges with only minimal live segments per def. - LiveRange NewLR; - createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end())); - extendSegmentsToUses(NewLR, *Indexes, WorkList, SR); - - // Move the trimmed ranges back. - SR.segments.swap(NewLR.segments); - - // Remove dead PHI value numbers - for (VNInfo *VNI : SR.valnos) { - if (VNI->isUnused()) - continue; - const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def); - assert(Segment != nullptr && "Missing segment for VNI"); - if (Segment->end != VNI->def.getDeadSlot()) - continue; - if (VNI->isPHIDef()) { - // This is a dead PHI. Remove it. - DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); - VNI->markUnused(); - SR.removeSegment(*Segment); - } - } - - DEBUG(dbgs() << "Shrunk: " << SR << '\n'); -} - -void LiveIntervals::extendToIndices(LiveRange &LR, - ArrayRef Indices, - ArrayRef Undefs) { - assert(LRCalc && "LRCalc not initialized."); - LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); - for (SlotIndex Idx : Indices) - LRCalc->extend(LR, Idx, /*PhysReg=*/0, Undefs); -} - -void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill, - SmallVectorImpl *EndPoints) { - LiveQueryResult LRQ = LR.Query(Kill); - VNInfo *VNI = LRQ.valueOutOrDead(); - if (!VNI) - return; - - MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill); - SlotIndex MBBEnd = Indexes->getMBBEndIdx(KillMBB); - - // If VNI isn't live out from KillMBB, the value is trivially pruned. - if (LRQ.endPoint() < MBBEnd) { - LR.removeSegment(Kill, LRQ.endPoint()); - if (EndPoints) EndPoints->push_back(LRQ.endPoint()); - return; - } - - // VNI is live out of KillMBB. - LR.removeSegment(Kill, MBBEnd); - if (EndPoints) EndPoints->push_back(MBBEnd); - - // Find all blocks that are reachable from KillMBB without leaving VNI's live - // range. It is possible that KillMBB itself is reachable, so start a DFS - // from each successor. - using VisitedTy = df_iterator_default_set; - VisitedTy Visited; - for (MachineBasicBlock *Succ : KillMBB->successors()) { - for (df_ext_iterator - I = df_ext_begin(Succ, Visited), E = df_ext_end(Succ, Visited); - I != E;) { - MachineBasicBlock *MBB = *I; - - // Check if VNI is live in to MBB. - SlotIndex MBBStart, MBBEnd; - std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB); - LiveQueryResult LRQ = LR.Query(MBBStart); - if (LRQ.valueIn() != VNI) { - // This block isn't part of the VNI segment. Prune the search. - I.skipChildren(); - continue; - } - - // Prune the search if VNI is killed in MBB. - if (LRQ.endPoint() < MBBEnd) { - LR.removeSegment(MBBStart, LRQ.endPoint()); - if (EndPoints) EndPoints->push_back(LRQ.endPoint()); - I.skipChildren(); - continue; - } - - // VNI is live through MBB. - LR.removeSegment(MBBStart, MBBEnd); - if (EndPoints) EndPoints->push_back(MBBEnd); - ++I; - } - } -} - -//===----------------------------------------------------------------------===// -// Register allocator hooks. -// - -void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { - // Keep track of regunit ranges. - SmallVector, 8> RU; - // Keep track of subregister ranges. - SmallVector, 4> SRs; - - for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { - unsigned Reg = TargetRegisterInfo::index2VirtReg(i); - if (MRI->reg_nodbg_empty(Reg)) - continue; - const LiveInterval &LI = getInterval(Reg); - if (LI.empty()) - continue; - - // Find the regunit intervals for the assigned register. They may overlap - // the virtual register live range, cancelling any kills. - RU.clear(); - for (MCRegUnitIterator Unit(VRM->getPhys(Reg), TRI); Unit.isValid(); - ++Unit) { - const LiveRange &RURange = getRegUnit(*Unit); - if (RURange.empty()) - continue; - RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end))); - } - - if (MRI->subRegLivenessEnabled()) { - SRs.clear(); - for (const LiveInterval::SubRange &SR : LI.subranges()) { - SRs.push_back(std::make_pair(&SR, SR.find(LI.begin()->end))); - } - } - - // Every instruction that kills Reg corresponds to a segment range end - // point. - for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE; - ++RI) { - // A block index indicates an MBB edge. - if (RI->end.isBlock()) - continue; - MachineInstr *MI = getInstructionFromIndex(RI->end); - if (!MI) - continue; - - // Check if any of the regunits are live beyond the end of RI. That could - // happen when a physreg is defined as a copy of a virtreg: - // - // %EAX = COPY %vreg5 - // FOO %vreg5 <--- MI, cancel kill because %EAX is live. - // BAR %EAX - // - // There should be no kill flag on FOO when %vreg5 is rewritten as %EAX. - for (auto &RUP : RU) { - const LiveRange &RURange = *RUP.first; - LiveRange::const_iterator &I = RUP.second; - if (I == RURange.end()) - continue; - I = RURange.advanceTo(I, RI->end); - if (I == RURange.end() || I->start >= RI->end) - continue; - // I is overlapping RI. - goto CancelKill; - } - - if (MRI->subRegLivenessEnabled()) { - // When reading a partial undefined value we must not add a kill flag. - // The regalloc might have used the undef lane for something else. - // Example: - // %vreg1 = ... ; R32: %vreg1 - // %vreg2:high16 = ... ; R64: %vreg2 - // = read %vreg2 ; R64: %vreg2 - // = read %vreg1 ; R32: %vreg1 - // The flag is correct for %vreg2, but the register allocator may - // assign R0L to %vreg1, and R0 to %vreg2 because the low 32bits of R0 - // are actually never written by %vreg2. After assignment the - // flag at the read instruction is invalid. - LaneBitmask DefinedLanesMask; - if (!SRs.empty()) { - // Compute a mask of lanes that are defined. - DefinedLanesMask = LaneBitmask::getNone(); - for (auto &SRP : SRs) { - const LiveInterval::SubRange &SR = *SRP.first; - LiveRange::const_iterator &I = SRP.second; - if (I == SR.end()) - continue; - I = SR.advanceTo(I, RI->end); - if (I == SR.end() || I->start >= RI->end) - continue; - // I is overlapping RI - DefinedLanesMask |= SR.LaneMask; - } - } else - DefinedLanesMask = LaneBitmask::getAll(); - - bool IsFullWrite = false; - for (const MachineOperand &MO : MI->operands()) { - if (!MO.isReg() || MO.getReg() != Reg) - continue; - if (MO.isUse()) { - // Reading any undefined lanes? - LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg()); - if ((UseMask & ~DefinedLanesMask).any()) - goto CancelKill; - } else if (MO.getSubReg() == 0) { - // Writing to the full register? - assert(MO.isDef()); - IsFullWrite = true; - } - } - - // If an instruction writes to a subregister, a new segment starts in - // the LiveInterval. But as this is only overriding part of the register - // adding kill-flags is not correct here after registers have been - // assigned. - if (!IsFullWrite) { - // Next segment has to be adjacent in the subregister write case. - LiveRange::const_iterator N = std::next(RI); - if (N != LI.end() && N->start == RI->end) - goto CancelKill; - } - } - - MI->addRegisterKilled(Reg, nullptr); - continue; -CancelKill: - MI->clearRegisterKills(Reg, nullptr); - } - } -} - -MachineBasicBlock* -LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const { - // A local live range must be fully contained inside the block, meaning it is - // defined and killed at instructions, not at block boundaries. It is not - // live in or or out of any block. - // - // It is technically possible to have a PHI-defined live range identical to a - // single block, but we are going to return false in that case. - - SlotIndex Start = LI.beginIndex(); - if (Start.isBlock()) - return nullptr; - - SlotIndex Stop = LI.endIndex(); - if (Stop.isBlock()) - return nullptr; - - // getMBBFromIndex doesn't need to search the MBB table when both indexes - // belong to proper instructions. - MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start); - MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop); - return MBB1 == MBB2 ? MBB1 : nullptr; -} - -bool -LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const { - for (const VNInfo *PHI : LI.valnos) { - if (PHI->isUnused() || !PHI->isPHIDef()) - continue; - const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def); - // Conservatively return true instead of scanning huge predecessor lists. - if (PHIMBB->pred_size() > 100) - return true; - for (const MachineBasicBlock *Pred : PHIMBB->predecessors()) - if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(Pred))) - return true; - } - return false; -} - -float LiveIntervals::getSpillWeight(bool isDef, bool isUse, - const MachineBlockFrequencyInfo *MBFI, - const MachineInstr &MI) { - BlockFrequency Freq = MBFI->getBlockFreq(MI.getParent()); - const float Scale = 1.0f / MBFI->getEntryFreq(); - return (isDef + isUse) * (Freq.getFrequency() * Scale); -} - -LiveRange::Segment -LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr &startInst) { - LiveInterval& Interval = createEmptyInterval(reg); - VNInfo *VN = Interval.getNextValue( - SlotIndex(getInstructionIndex(startInst).getRegSlot()), - getVNInfoAllocator()); - LiveRange::Segment S(SlotIndex(getInstructionIndex(startInst).getRegSlot()), - getMBBEndIdx(startInst.getParent()), VN); - Interval.addSegment(S); - - return S; -} - -//===----------------------------------------------------------------------===// -// Register mask functions -//===----------------------------------------------------------------------===// - -bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI, - BitVector &UsableRegs) { - if (LI.empty()) - return false; - LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end(); - - // Use a smaller arrays for local live ranges. - ArrayRef Slots; - ArrayRef Bits; - if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) { - Slots = getRegMaskSlotsInBlock(MBB->getNumber()); - Bits = getRegMaskBitsInBlock(MBB->getNumber()); - } else { - Slots = getRegMaskSlots(); - Bits = getRegMaskBits(); - } - - // We are going to enumerate all the register mask slots contained in LI. - // Start with a binary search of RegMaskSlots to find a starting point. - ArrayRef::iterator SlotI = - std::lower_bound(Slots.begin(), Slots.end(), LiveI->start); - ArrayRef::iterator SlotE = Slots.end(); - - // No slots in range, LI begins after the last call. - if (SlotI == SlotE) - return false; - - bool Found = false; - while (true) { - assert(*SlotI >= LiveI->start); - // Loop over all slots overlapping this segment. - while (*SlotI < LiveI->end) { - // *SlotI overlaps LI. Collect mask bits. - if (!Found) { - // This is the first overlap. Initialize UsableRegs to all ones. - UsableRegs.clear(); - UsableRegs.resize(TRI->getNumRegs(), true); - Found = true; - } - // Remove usable registers clobbered by this mask. - UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]); - if (++SlotI == SlotE) - return Found; - } - // *SlotI is beyond the current LI segment. - LiveI = LI.advanceTo(LiveI, *SlotI); - if (LiveI == LiveE) - return Found; - // Advance SlotI until it overlaps. - while (*SlotI < LiveI->start) - if (++SlotI == SlotE) - return Found; - } -} - -//===----------------------------------------------------------------------===// -// IntervalUpdate class. -//===----------------------------------------------------------------------===// - -/// Toolkit used by handleMove to trim or extend live intervals. -class LiveIntervals::HMEditor { -private: - LiveIntervals& LIS; - const MachineRegisterInfo& MRI; - const TargetRegisterInfo& TRI; - SlotIndex OldIdx; - SlotIndex NewIdx; - SmallPtrSet Updated; - bool UpdateFlags; - -public: - HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI, - const TargetRegisterInfo& TRI, - SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags) - : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx), - UpdateFlags(UpdateFlags) {} - - // FIXME: UpdateFlags is a workaround that creates live intervals for all - // physregs, even those that aren't needed for regalloc, in order to update - // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill - // flags, and postRA passes will use a live register utility instead. - LiveRange *getRegUnitLI(unsigned Unit) { - if (UpdateFlags) - return &LIS.getRegUnit(Unit); - return LIS.getCachedRegUnit(Unit); - } - - /// Update all live ranges touched by MI, assuming a move from OldIdx to - /// NewIdx. - void updateAllRanges(MachineInstr *MI) { - DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": " << *MI); - bool hasRegMask = false; - for (MachineOperand &MO : MI->operands()) { - if (MO.isRegMask()) - hasRegMask = true; - if (!MO.isReg()) - continue; - if (MO.isUse()) { - if (!MO.readsReg()) - continue; - // Aggressively clear all kill flags. - // They are reinserted by VirtRegRewriter. - MO.setIsKill(false); - } - - unsigned Reg = MO.getReg(); - if (!Reg) - continue; - if (TargetRegisterInfo::isVirtualRegister(Reg)) { - LiveInterval &LI = LIS.getInterval(Reg); - if (LI.hasSubRanges()) { - unsigned SubReg = MO.getSubReg(); - LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg) - : MRI.getMaxLaneMaskForVReg(Reg); - for (LiveInterval::SubRange &S : LI.subranges()) { - if ((S.LaneMask & LaneMask).none()) - continue; - updateRange(S, Reg, S.LaneMask); - } - } - updateRange(LI, Reg, LaneBitmask::getNone()); - continue; - } - - // For physregs, only update the regunits that actually have a - // precomputed live range. - for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units) - if (LiveRange *LR = getRegUnitLI(*Units)) - updateRange(*LR, *Units, LaneBitmask::getNone()); - } - if (hasRegMask) - updateRegMaskSlots(); - } - -private: - /// Update a single live range, assuming an instruction has been moved from - /// OldIdx to NewIdx. - void updateRange(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) { - if (!Updated.insert(&LR).second) - return; - DEBUG({ - dbgs() << " "; - if (TargetRegisterInfo::isVirtualRegister(Reg)) { - dbgs() << PrintReg(Reg); - if (LaneMask.any()) - dbgs() << " L" << PrintLaneMask(LaneMask); - } else { - dbgs() << PrintRegUnit(Reg, &TRI); - } - dbgs() << ":\t" << LR << '\n'; - }); - if (SlotIndex::isEarlierInstr(OldIdx, NewIdx)) - handleMoveDown(LR); - else - handleMoveUp(LR, Reg, LaneMask); - DEBUG(dbgs() << " -->\t" << LR << '\n'); - LR.verify(); - } - - /// Update LR to reflect an instruction has been moved downwards from OldIdx - /// to NewIdx (OldIdx < NewIdx). - void handleMoveDown(LiveRange &LR) { - LiveRange::iterator E = LR.end(); - // Segment going into OldIdx. - LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex()); - - // No value live before or after OldIdx? Nothing to do. - if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start)) - return; - - LiveRange::iterator OldIdxOut; - // Do we have a value live-in to OldIdx? - if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) { - // If the live-in value already extends to NewIdx, there is nothing to do. - if (SlotIndex::isEarlierEqualInstr(NewIdx, OldIdxIn->end)) - return; - // Aggressively remove all kill flags from the old kill point. - // Kill flags shouldn't be used while live intervals exist, they will be - // reinserted by VirtRegRewriter. - if (MachineInstr *KillMI = LIS.getInstructionFromIndex(OldIdxIn->end)) - for (MIBundleOperands MO(*KillMI); MO.isValid(); ++MO) - if (MO->isReg() && MO->isUse()) - MO->setIsKill(false); - - // Is there a def before NewIdx which is not OldIdx? - LiveRange::iterator Next = std::next(OldIdxIn); - if (Next != E && !SlotIndex::isSameInstr(OldIdx, Next->start) && - SlotIndex::isEarlierInstr(Next->start, NewIdx)) { - // If we are here then OldIdx was just a use but not a def. We only have - // to ensure liveness extends to NewIdx. - LiveRange::iterator NewIdxIn = - LR.advanceTo(Next, NewIdx.getBaseIndex()); - // Extend the segment before NewIdx if necessary. - if (NewIdxIn == E || - !SlotIndex::isEarlierInstr(NewIdxIn->start, NewIdx)) { - LiveRange::iterator Prev = std::prev(NewIdxIn); - Prev->end = NewIdx.getRegSlot(); - } - // Extend OldIdxIn. - OldIdxIn->end = Next->start; - return; - } - - // Adjust OldIdxIn->end to reach NewIdx. This may temporarily make LR - // invalid by overlapping ranges. - bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end); - OldIdxIn->end = NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber()); - // If this was not a kill, then there was no def and we're done. - if (!isKill) - return; - - // Did we have a Def at OldIdx? - OldIdxOut = Next; - if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start)) - return; - } else { - OldIdxOut = OldIdxIn; - } - - // If we are here then there is a Definition at OldIdx. OldIdxOut points - // to the segment starting there. - assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) && - "No def?"); - VNInfo *OldIdxVNI = OldIdxOut->valno; - assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def"); - - // If the defined value extends beyond NewIdx, just move the beginning - // of the segment to NewIdx. - SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber()); - if (SlotIndex::isEarlierInstr(NewIdxDef, OldIdxOut->end)) { - OldIdxVNI->def = NewIdxDef; - OldIdxOut->start = OldIdxVNI->def; - return; - } - - // If we are here then we have a Definition at OldIdx which ends before - // NewIdx. - - // Is there an existing Def at NewIdx? - LiveRange::iterator AfterNewIdx - = LR.advanceTo(OldIdxOut, NewIdx.getRegSlot()); - bool OldIdxDefIsDead = OldIdxOut->end.isDead(); - if (!OldIdxDefIsDead && - SlotIndex::isEarlierInstr(OldIdxOut->end, NewIdxDef)) { - // OldIdx is not a dead def, and NewIdxDef is inside a new interval. - VNInfo *DefVNI; - if (OldIdxOut != LR.begin() && - !SlotIndex::isEarlierInstr(std::prev(OldIdxOut)->end, - OldIdxOut->start)) { - // There is no gap between OldIdxOut and its predecessor anymore, - // merge them. - LiveRange::iterator IPrev = std::prev(OldIdxOut); - DefVNI = OldIdxVNI; - IPrev->end = OldIdxOut->end; - } else { - // The value is live in to OldIdx - LiveRange::iterator INext = std::next(OldIdxOut); - assert(INext != E && "Must have following segment"); - // We merge OldIdxOut and its successor. As we're dealing with subreg - // reordering, there is always a successor to OldIdxOut in the same BB - // We don't need INext->valno anymore and will reuse for the new segment - // we create later. - DefVNI = OldIdxVNI; - INext->start = OldIdxOut->end; - INext->valno->def = INext->start; - } - // If NewIdx is behind the last segment, extend that and append a new one. - if (AfterNewIdx == E) { - // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up - // one position. - // |- ?/OldIdxOut -| |- X0 -| ... |- Xn -| end - // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS -| end - std::copy(std::next(OldIdxOut), E, OldIdxOut); - // The last segment is undefined now, reuse it for a dead def. - LiveRange::iterator NewSegment = std::prev(E); - *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(), - DefVNI); - DefVNI->def = NewIdxDef; - - LiveRange::iterator Prev = std::prev(NewSegment); - Prev->end = NewIdxDef; - } else { - // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up - // one position. - // |- ?/OldIdxOut -| |- X0 -| ... |- Xn/AfterNewIdx -| |- Next -| - // => |- X0/OldIdxOut -| ... |- Xn -| |- Xn/AfterNewIdx -| |- Next -| - std::copy(std::next(OldIdxOut), std::next(AfterNewIdx), OldIdxOut); - LiveRange::iterator Prev = std::prev(AfterNewIdx); - // We have two cases: - if (SlotIndex::isEarlierInstr(Prev->start, NewIdxDef)) { - // Case 1: NewIdx is inside a liverange. Split this liverange at - // NewIdxDef into the segment "Prev" followed by "NewSegment". - LiveRange::iterator NewSegment = AfterNewIdx; - *NewSegment = LiveRange::Segment(NewIdxDef, Prev->end, Prev->valno); - Prev->valno->def = NewIdxDef; - - *Prev = LiveRange::Segment(Prev->start, NewIdxDef, DefVNI); - DefVNI->def = Prev->start; - } else { - // Case 2: NewIdx is in a lifetime hole. Keep AfterNewIdx as is and - // turn Prev into a segment from NewIdx to AfterNewIdx->start. - *Prev = LiveRange::Segment(NewIdxDef, AfterNewIdx->start, DefVNI); - DefVNI->def = NewIdxDef; - assert(DefVNI != AfterNewIdx->valno); - } - } - return; - } - - if (AfterNewIdx != E && - SlotIndex::isSameInstr(AfterNewIdx->start, NewIdxDef)) { - // There is an existing def at NewIdx. The def at OldIdx is coalesced into - // that value. - assert(AfterNewIdx->valno != OldIdxVNI && "Multiple defs of value?"); - LR.removeValNo(OldIdxVNI); - } else { - // There was no existing def at NewIdx. We need to create a dead def - // at NewIdx. Shift segments over the old OldIdxOut segment, this frees - // a new segment at the place where we want to construct the dead def. - // |- OldIdxOut -| |- X0 -| ... |- Xn -| |- AfterNewIdx -| - // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS. -| |- AfterNewIdx -| - assert(AfterNewIdx != OldIdxOut && "Inconsistent iterators"); - std::copy(std::next(OldIdxOut), AfterNewIdx, OldIdxOut); - // We can reuse OldIdxVNI now. - LiveRange::iterator NewSegment = std::prev(AfterNewIdx); - VNInfo *NewSegmentVNI = OldIdxVNI; - NewSegmentVNI->def = NewIdxDef; - *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(), - NewSegmentVNI); - } - } - - /// Update LR to reflect an instruction has been moved upwards from OldIdx - /// to NewIdx (NewIdx < OldIdx). - void handleMoveUp(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) { - LiveRange::iterator E = LR.end(); - // Segment going into OldIdx. - LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex()); - - // No value live before or after OldIdx? Nothing to do. - if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start)) - return; - - LiveRange::iterator OldIdxOut; - // Do we have a value live-in to OldIdx? - if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) { - // If the live-in value isn't killed here, then we have no Def at - // OldIdx, moreover the value must be live at NewIdx so there is nothing - // to do. - bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end); - if (!isKill) - return; - - // At this point we have to move OldIdxIn->end back to the nearest - // previous use or (dead-)def but no further than NewIdx. - SlotIndex DefBeforeOldIdx - = std::max(OldIdxIn->start.getDeadSlot(), - NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber())); - OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, Reg, LaneMask); - - // Did we have a Def at OldIdx? If not we are done now. - OldIdxOut = std::next(OldIdxIn); - if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start)) - return; - } else { - OldIdxOut = OldIdxIn; - OldIdxIn = OldIdxOut != LR.begin() ? std::prev(OldIdxOut) : E; - } - - // If we are here then there is a Definition at OldIdx. OldIdxOut points - // to the segment starting there. - assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) && - "No def?"); - VNInfo *OldIdxVNI = OldIdxOut->valno; - assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def"); - bool OldIdxDefIsDead = OldIdxOut->end.isDead(); - - // Is there an existing def at NewIdx? - SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber()); - LiveRange::iterator NewIdxOut = LR.find(NewIdx.getRegSlot()); - if (SlotIndex::isSameInstr(NewIdxOut->start, NewIdx)) { - assert(NewIdxOut->valno != OldIdxVNI && - "Same value defined more than once?"); - // If OldIdx was a dead def remove it. - if (!OldIdxDefIsDead) { - // Remove segment starting at NewIdx and move begin of OldIdxOut to - // NewIdx so it can take its place. - OldIdxVNI->def = NewIdxDef; - OldIdxOut->start = NewIdxDef; - LR.removeValNo(NewIdxOut->valno); - } else { - // Simply remove the dead def at OldIdx. - LR.removeValNo(OldIdxVNI); - } - } else { - // Previously nothing was live after NewIdx, so all we have to do now is - // move the begin of OldIdxOut to NewIdx. - if (!OldIdxDefIsDead) { - // Do we have any intermediate Defs between OldIdx and NewIdx? - if (OldIdxIn != E && - SlotIndex::isEarlierInstr(NewIdxDef, OldIdxIn->start)) { - // OldIdx is not a dead def and NewIdx is before predecessor start. - LiveRange::iterator NewIdxIn = NewIdxOut; - assert(NewIdxIn == LR.find(NewIdx.getBaseIndex())); - const SlotIndex SplitPos = NewIdxDef; - OldIdxVNI = OldIdxIn->valno; - - // Merge the OldIdxIn and OldIdxOut segments into OldIdxOut. - OldIdxOut->valno->def = OldIdxIn->start; - *OldIdxOut = LiveRange::Segment(OldIdxIn->start, OldIdxOut->end, - OldIdxOut->valno); - // OldIdxIn and OldIdxVNI are now undef and can be overridden. - // We Slide [NewIdxIn, OldIdxIn) down one position. - // |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -| - // => |- undef/NexIdxIn -| |- X0 -| ... |- Xn-1 -| |- Xn/OldIdxOut -| - std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut); - // NewIdxIn is now considered undef so we can reuse it for the moved - // value. - LiveRange::iterator NewSegment = NewIdxIn; - LiveRange::iterator Next = std::next(NewSegment); - if (SlotIndex::isEarlierInstr(Next->start, NewIdx)) { - // There is no gap between NewSegment and its predecessor. - *NewSegment = LiveRange::Segment(Next->start, SplitPos, - Next->valno); - *Next = LiveRange::Segment(SplitPos, Next->end, OldIdxVNI); - Next->valno->def = SplitPos; - } else { - // There is a gap between NewSegment and its predecessor - // Value becomes live in. - *NewSegment = LiveRange::Segment(SplitPos, Next->start, OldIdxVNI); - NewSegment->valno->def = SplitPos; - } - } else { - // Leave the end point of a live def. - OldIdxOut->start = NewIdxDef; - OldIdxVNI->def = NewIdxDef; - if (OldIdxIn != E && SlotIndex::isEarlierInstr(NewIdx, OldIdxIn->end)) - OldIdxIn->end = NewIdx.getRegSlot(); - } - } else { - // OldIdxVNI is a dead def. It may have been moved across other values - // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut) - // down one position. - // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - | - // => |- undef/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -| - std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut)); - // OldIdxVNI can be reused now to build a new dead def segment. - LiveRange::iterator NewSegment = NewIdxOut; - VNInfo *NewSegmentVNI = OldIdxVNI; - *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(), - NewSegmentVNI); - NewSegmentVNI->def = NewIdxDef; - } - } - } - - void updateRegMaskSlots() { - SmallVectorImpl::iterator RI = - std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(), - OldIdx); - assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() && - "No RegMask at OldIdx."); - *RI = NewIdx.getRegSlot(); - assert((RI == LIS.RegMaskSlots.begin() || - SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) && - "Cannot move regmask instruction above another call"); - assert((std::next(RI) == LIS.RegMaskSlots.end() || - SlotIndex::isEarlierInstr(*RI, *std::next(RI))) && - "Cannot move regmask instruction below another call"); - } - - // Return the last use of reg between NewIdx and OldIdx. - SlotIndex findLastUseBefore(SlotIndex Before, unsigned Reg, - LaneBitmask LaneMask) { - if (TargetRegisterInfo::isVirtualRegister(Reg)) { - SlotIndex LastUse = Before; - for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) { - if (MO.isUndef()) - continue; - unsigned SubReg = MO.getSubReg(); - if (SubReg != 0 && LaneMask.any() - && (TRI.getSubRegIndexLaneMask(SubReg) & LaneMask).none()) - continue; - - const MachineInstr &MI = *MO.getParent(); - SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI); - if (InstSlot > LastUse && InstSlot < OldIdx) - LastUse = InstSlot.getRegSlot(); - } - return LastUse; - } - - // This is a regunit interval, so scanning the use list could be very - // expensive. Scan upwards from OldIdx instead. - assert(Before < OldIdx && "Expected upwards move"); - SlotIndexes *Indexes = LIS.getSlotIndexes(); - MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Before); - - // OldIdx may not correspond to an instruction any longer, so set MII to - // point to the next instruction after OldIdx, or MBB->end(). - MachineBasicBlock::iterator MII = MBB->end(); - if (MachineInstr *MI = Indexes->getInstructionFromIndex( - Indexes->getNextNonNullIndex(OldIdx))) - if (MI->getParent() == MBB) - MII = MI; - - MachineBasicBlock::iterator Begin = MBB->begin(); - while (MII != Begin) { - if ((--MII)->isDebugValue()) - continue; - SlotIndex Idx = Indexes->getInstructionIndex(*MII); - - // Stop searching when Before is reached. - if (!SlotIndex::isEarlierInstr(Before, Idx)) - return Before; - - // Check if MII uses Reg. - for (MIBundleOperands MO(*MII); MO.isValid(); ++MO) - if (MO->isReg() && !MO->isUndef() && - TargetRegisterInfo::isPhysicalRegister(MO->getReg()) && - TRI.hasRegUnit(MO->getReg(), Reg)) - return Idx.getRegSlot(); - } - // Didn't reach Before. It must be the first instruction in the block. - return Before; - } -}; - -void LiveIntervals::handleMove(MachineInstr &MI, bool UpdateFlags) { - assert(!MI.isBundled() && "Can't handle bundled instructions yet."); - SlotIndex OldIndex = Indexes->getInstructionIndex(MI); - Indexes->removeMachineInstrFromMaps(MI); - SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI); - assert(getMBBStartIdx(MI.getParent()) <= OldIndex && - OldIndex < getMBBEndIdx(MI.getParent()) && - "Cannot handle moves across basic block boundaries."); - - HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); - HME.updateAllRanges(&MI); -} - -void LiveIntervals::handleMoveIntoBundle(MachineInstr &MI, - MachineInstr &BundleStart, - bool UpdateFlags) { - SlotIndex OldIndex = Indexes->getInstructionIndex(MI); - SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart); - HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); - HME.updateAllRanges(&MI); -} - -void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin, - const MachineBasicBlock::iterator End, - const SlotIndex endIdx, - LiveRange &LR, const unsigned Reg, - LaneBitmask LaneMask) { - LiveInterval::iterator LII = LR.find(endIdx); - SlotIndex lastUseIdx; - if (LII == LR.begin()) { - // This happens when the function is called for a subregister that only - // occurs _after_ the range that is to be repaired. - return; - } - if (LII != LR.end() && LII->start < endIdx) - lastUseIdx = LII->end; - else - --LII; - - for (MachineBasicBlock::iterator I = End; I != Begin;) { - --I; - MachineInstr &MI = *I; - if (MI.isDebugValue()) - continue; - - SlotIndex instrIdx = getInstructionIndex(MI); - bool isStartValid = getInstructionFromIndex(LII->start); - bool isEndValid = getInstructionFromIndex(LII->end); - - // FIXME: This doesn't currently handle early-clobber or multiple removed - // defs inside of the region to repair. - for (MachineInstr::mop_iterator OI = MI.operands_begin(), - OE = MI.operands_end(); - OI != OE; ++OI) { - const MachineOperand &MO = *OI; - if (!MO.isReg() || MO.getReg() != Reg) - continue; - - unsigned SubReg = MO.getSubReg(); - LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg); - if ((Mask & LaneMask).none()) - continue; - - if (MO.isDef()) { - if (!isStartValid) { - if (LII->end.isDead()) { - SlotIndex prevStart; - if (LII != LR.begin()) - prevStart = std::prev(LII)->start; - - // FIXME: This could be more efficient if there was a - // removeSegment method that returned an iterator. - LR.removeSegment(*LII, true); - if (prevStart.isValid()) - LII = LR.find(prevStart); - else - LII = LR.begin(); - } else { - LII->start = instrIdx.getRegSlot(); - LII->valno->def = instrIdx.getRegSlot(); - if (MO.getSubReg() && !MO.isUndef()) - lastUseIdx = instrIdx.getRegSlot(); - else - lastUseIdx = SlotIndex(); - continue; - } - } - - if (!lastUseIdx.isValid()) { - VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator); - LiveRange::Segment S(instrIdx.getRegSlot(), - instrIdx.getDeadSlot(), VNI); - LII = LR.addSegment(S); - } else if (LII->start != instrIdx.getRegSlot()) { - VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator); - LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI); - LII = LR.addSegment(S); - } - - if (MO.getSubReg() && !MO.isUndef()) - lastUseIdx = instrIdx.getRegSlot(); - else - lastUseIdx = SlotIndex(); - } else if (MO.isUse()) { - // FIXME: This should probably be handled outside of this branch, - // either as part of the def case (for defs inside of the region) or - // after the loop over the region. - if (!isEndValid && !LII->end.isBlock()) - LII->end = instrIdx.getRegSlot(); - if (!lastUseIdx.isValid()) - lastUseIdx = instrIdx.getRegSlot(); - } - } - } -} - -void -LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB, - MachineBasicBlock::iterator Begin, - MachineBasicBlock::iterator End, - ArrayRef OrigRegs) { - // Find anchor points, which are at the beginning/end of blocks or at - // instructions that already have indexes. - while (Begin != MBB->begin() && !Indexes->hasIndex(*Begin)) - --Begin; - while (End != MBB->end() && !Indexes->hasIndex(*End)) - ++End; - - SlotIndex endIdx; - if (End == MBB->end()) - endIdx = getMBBEndIdx(MBB).getPrevSlot(); - else - endIdx = getInstructionIndex(*End); - - Indexes->repairIndexesInRange(MBB, Begin, End); - - for (MachineBasicBlock::iterator I = End; I != Begin;) { - --I; - MachineInstr &MI = *I; - if (MI.isDebugValue()) - continue; - for (MachineInstr::const_mop_iterator MOI = MI.operands_begin(), - MOE = MI.operands_end(); - MOI != MOE; ++MOI) { - if (MOI->isReg() && - TargetRegisterInfo::isVirtualRegister(MOI->getReg()) && - !hasInterval(MOI->getReg())) { - createAndComputeVirtRegInterval(MOI->getReg()); - } - } - } - - for (unsigned Reg : OrigRegs) { - if (!TargetRegisterInfo::isVirtualRegister(Reg)) - continue; - - LiveInterval &LI = getInterval(Reg); - // FIXME: Should we support undefs that gain defs? - if (!LI.hasAtLeastOneValue()) - continue; - - for (LiveInterval::SubRange &S : LI.subranges()) - repairOldRegInRange(Begin, End, endIdx, S, Reg, S.LaneMask); - - repairOldRegInRange(Begin, End, endIdx, LI, Reg); - } -} - -void LiveIntervals::removePhysRegDefAt(unsigned Reg, SlotIndex Pos) { - for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) { - if (LiveRange *LR = getCachedRegUnit(*Unit)) - if (VNInfo *VNI = LR->getVNInfoAt(Pos)) - LR->removeValNo(VNI); - } -} - -void LiveIntervals::removeVRegDefAt(LiveInterval &LI, SlotIndex Pos) { - // LI may not have the main range computed yet, but its subranges may - // be present. - VNInfo *VNI = LI.getVNInfoAt(Pos); - if (VNI != nullptr) { - assert(VNI->def.getBaseIndex() == Pos.getBaseIndex()); - LI.removeValNo(VNI); - } - - // Also remove the value defined in subranges. - for (LiveInterval::SubRange &S : LI.subranges()) { - if (VNInfo *SVNI = S.getVNInfoAt(Pos)) - if (SVNI->def.getBaseIndex() == Pos.getBaseIndex()) - S.removeValNo(SVNI); - } - LI.removeEmptySubRanges(); -} - -void LiveIntervals::splitSeparateComponents(LiveInterval &LI, - SmallVectorImpl &SplitLIs) { - ConnectedVNInfoEqClasses ConEQ(*this); - unsigned NumComp = ConEQ.Classify(LI); - if (NumComp <= 1) - return; - DEBUG(dbgs() << " Split " << NumComp << " components: " << LI << '\n'); - unsigned Reg = LI.reg; - const TargetRegisterClass *RegClass = MRI->getRegClass(Reg); - for (unsigned I = 1; I < NumComp; ++I) { - unsigned NewVReg = MRI->createVirtualRegister(RegClass); - LiveInterval &NewLI = createEmptyInterval(NewVReg); - SplitLIs.push_back(&NewLI); - } - ConEQ.Distribute(LI, SplitLIs.data(), *MRI); -} - -void LiveIntervals::constructMainRangeFromSubranges(LiveInterval &LI) { - assert(LRCalc && "LRCalc not initialized."); - LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); - LRCalc->constructMainRangeFromSubranges(LI); -} +//===- LiveIntervalAnalysis.cpp - Live Interval Analysis ------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +/// \file This file implements the LiveInterval analysis pass which is used +/// by the Linear Scan Register allocator. This pass linearizes the +/// basic blocks of the function in DFS order and computes live intervals for +/// each virtual and physical register. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "LiveRangeCalc.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/iterator_range.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/CodeGen/LiveInterval.h" +#include "llvm/CodeGen/LiveVariables.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineInstrBundle.h" +#include "llvm/CodeGen/MachineOperand.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/SlotIndexes.h" +#include "llvm/CodeGen/VirtRegMap.h" +#include "llvm/MC/LaneBitmask.h" +#include "llvm/MC/MCRegisterInfo.h" +#include "llvm/Pass.h" +#include "llvm/Support/BlockFrequency.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/MathExtras.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" +#include +#include +#include +#include +#include +#include + +using namespace llvm; + +#define DEBUG_TYPE "regalloc" + +char LiveIntervals::ID = 0; +char &llvm::LiveIntervalsID = LiveIntervals::ID; +INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", + "Live Interval Analysis", false, false) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) +INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) +INITIALIZE_PASS_DEPENDENCY(SlotIndexes) +INITIALIZE_PASS_END(LiveIntervals, "liveintervals", + "Live Interval Analysis", false, false) + +#ifndef NDEBUG +static cl::opt EnablePrecomputePhysRegs( + "precompute-phys-liveness", cl::Hidden, + cl::desc("Eagerly compute live intervals for all physreg units.")); +#else +static bool EnablePrecomputePhysRegs = false; +#endif // NDEBUG + +namespace llvm { + +cl::opt UseSegmentSetForPhysRegs( + "use-segment-set-for-physregs", cl::Hidden, cl::init(true), + cl::desc( + "Use segment set for the computation of the live ranges of physregs.")); + +} // end namespace llvm + +void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); + AU.addRequired(); + AU.addPreserved(); + AU.addPreserved(); + AU.addPreservedID(MachineLoopInfoID); + AU.addRequiredTransitiveID(MachineDominatorsID); + AU.addPreservedID(MachineDominatorsID); + AU.addPreserved(); + AU.addRequiredTransitive(); + MachineFunctionPass::getAnalysisUsage(AU); +} + +LiveIntervals::LiveIntervals() : MachineFunctionPass(ID) { + initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); +} + +LiveIntervals::~LiveIntervals() { + delete LRCalc; +} + +void LiveIntervals::releaseMemory() { + // Free the live intervals themselves. + for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i) + delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)]; + VirtRegIntervals.clear(); + RegMaskSlots.clear(); + RegMaskBits.clear(); + RegMaskBlocks.clear(); + + for (LiveRange *LR : RegUnitRanges) + delete LR; + RegUnitRanges.clear(); + + // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd. + VNInfoAllocator.Reset(); +} + +bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { + MF = &fn; + MRI = &MF->getRegInfo(); + TRI = MF->getSubtarget().getRegisterInfo(); + TII = MF->getSubtarget().getInstrInfo(); + AA = &getAnalysis().getAAResults(); + Indexes = &getAnalysis(); + DomTree = &getAnalysis(); + + if (!LRCalc) + LRCalc = new LiveRangeCalc(); + + // Allocate space for all virtual registers. + VirtRegIntervals.resize(MRI->getNumVirtRegs()); + + computeVirtRegs(); + computeRegMasks(); + computeLiveInRegUnits(); + + if (EnablePrecomputePhysRegs) { + // For stress testing, precompute live ranges of all physical register + // units, including reserved registers. + for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i) + getRegUnit(i); + } + DEBUG(dump()); + return true; +} + +void LiveIntervals::print(raw_ostream &OS, const Module* ) const { + OS << "********** INTERVALS **********\n"; + + // Dump the regunits. + for (unsigned Unit = 0, UnitE = RegUnitRanges.size(); Unit != UnitE; ++Unit) + if (LiveRange *LR = RegUnitRanges[Unit]) + OS << PrintRegUnit(Unit, TRI) << ' ' << *LR << '\n'; + + // Dump the virtregs. + for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { + unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + if (hasInterval(Reg)) + OS << getInterval(Reg) << '\n'; + } + + OS << "RegMasks:"; + for (SlotIndex Idx : RegMaskSlots) + OS << ' ' << Idx; + OS << '\n'; + + printInstrs(OS); +} + +void LiveIntervals::printInstrs(raw_ostream &OS) const { + OS << "********** MACHINEINSTRS **********\n"; + MF->print(OS, Indexes); +} + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +LLVM_DUMP_METHOD void LiveIntervals::dumpInstrs() const { + printInstrs(dbgs()); +} +#endif + +LiveInterval* LiveIntervals::createInterval(unsigned reg) { + float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? huge_valf : 0.0F; + return new LiveInterval(reg, Weight); +} + +/// Compute the live interval of a virtual register, based on defs and uses. +void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { + assert(LRCalc && "LRCalc not initialized."); + assert(LI.empty() && "Should only compute empty intervals."); + LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); + LRCalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg)); + computeDeadValues(LI, nullptr); +} + +void LiveIntervals::computeVirtRegs() { + for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { + unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + if (MRI->reg_nodbg_empty(Reg)) + continue; + createAndComputeVirtRegInterval(Reg); + } +} + +void LiveIntervals::computeRegMasks() { + RegMaskBlocks.resize(MF->getNumBlockIDs()); + + // Find all instructions with regmask operands. + for (const MachineBasicBlock &MBB : *MF) { + std::pair &RMB = RegMaskBlocks[MBB.getNumber()]; + RMB.first = RegMaskSlots.size(); + + // Some block starts, such as EH funclets, create masks. + if (const uint32_t *Mask = MBB.getBeginClobberMask(TRI)) { + RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB)); + RegMaskBits.push_back(Mask); + } + + for (const MachineInstr &MI : MBB) { + for (const MachineOperand &MO : MI.operands()) { + if (!MO.isRegMask()) + continue; + RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot()); + RegMaskBits.push_back(MO.getRegMask()); + } + } + + // Some block ends, such as funclet returns, create masks. Put the mask on + // the last instruction of the block, because MBB slot index intervals are + // half-open. + if (const uint32_t *Mask = MBB.getEndClobberMask(TRI)) { + assert(!MBB.empty() && "empty return block?"); + RegMaskSlots.push_back( + Indexes->getInstructionIndex(MBB.back()).getRegSlot()); + RegMaskBits.push_back(Mask); + } + + // Compute the number of register mask instructions in this block. + RMB.second = RegMaskSlots.size() - RMB.first; + } +} + +//===----------------------------------------------------------------------===// +// Register Unit Liveness +//===----------------------------------------------------------------------===// +// +// Fixed interference typically comes from ABI boundaries: Function arguments +// and return values are passed in fixed registers, and so are exception +// pointers entering landing pads. Certain instructions require values to be +// present in specific registers. That is also represented through fixed +// interference. +// + +/// Compute the live range of a register unit, based on the uses and defs of +/// aliasing registers. The range should be empty, or contain only dead +/// phi-defs from ABI blocks. +void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) { + assert(LRCalc && "LRCalc not initialized."); + LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); + + // The physregs aliasing Unit are the roots and their super-registers. + // Create all values as dead defs before extending to uses. Note that roots + // may share super-registers. That's OK because createDeadDefs() is + // idempotent. It is very rare for a register unit to have multiple roots, so + // uniquing super-registers is probably not worthwhile. + bool IsReserved = true; + for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) { + for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true); + Super.isValid(); ++Super) { + unsigned Reg = *Super; + if (!MRI->reg_empty(Reg)) + LRCalc->createDeadDefs(LR, Reg); + // A register unit is considered reserved if all its roots and all their + // super registers are reserved. + if (!MRI->isReserved(Reg)) + IsReserved = false; + } + } + + // Now extend LR to reach all uses. + // Ignore uses of reserved registers. We only track defs of those. + if (!IsReserved) { + for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) { + for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true); + Super.isValid(); ++Super) { + unsigned Reg = *Super; + if (!MRI->reg_empty(Reg)) + LRCalc->extendToUses(LR, Reg); + } + } + } + + // Flush the segment set to the segment vector. + if (UseSegmentSetForPhysRegs) + LR.flushSegmentSet(); +} + +/// Precompute the live ranges of any register units that are live-in to an ABI +/// block somewhere. Register values can appear without a corresponding def when +/// entering the entry block or a landing pad. +void LiveIntervals::computeLiveInRegUnits() { + RegUnitRanges.resize(TRI->getNumRegUnits()); + DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n"); + + // Keep track of the live range sets allocated. + SmallVector NewRanges; + + // Check all basic blocks for live-ins. + for (const MachineBasicBlock &MBB : *MF) { + // We only care about ABI blocks: Entry + landing pads. + if ((&MBB != &MF->front() && !MBB.isEHPad()) || MBB.livein_empty()) + continue; + + // Create phi-defs at Begin for all live-in registers. + SlotIndex Begin = Indexes->getMBBStartIdx(&MBB); + DEBUG(dbgs() << Begin << "\tBB#" << MBB.getNumber()); + for (const auto &LI : MBB.liveins()) { + for (MCRegUnitIterator Units(LI.PhysReg, TRI); Units.isValid(); ++Units) { + unsigned Unit = *Units; + LiveRange *LR = RegUnitRanges[Unit]; + if (!LR) { + // Use segment set to speed-up initial computation of the live range. + LR = RegUnitRanges[Unit] = new LiveRange(UseSegmentSetForPhysRegs); + NewRanges.push_back(Unit); + } + VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator()); + (void)VNI; + DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id); + } + } + DEBUG(dbgs() << '\n'); + } + DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n"); + + // Compute the 'normal' part of the ranges. + for (unsigned Unit : NewRanges) + computeRegUnitRange(*RegUnitRanges[Unit], Unit); +} + +static void createSegmentsForValues(LiveRange &LR, + iterator_range VNIs) { + for (VNInfo *VNI : VNIs) { + if (VNI->isUnused()) + continue; + SlotIndex Def = VNI->def; + LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI)); + } +} + +using ShrinkToUsesWorkList = SmallVector, 16>; + +static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes, + ShrinkToUsesWorkList &WorkList, + const LiveRange &OldRange) { + // Keep track of the PHIs that are in use. + SmallPtrSet UsedPHIs; + // Blocks that have already been added to WorkList as live-out. + SmallPtrSet LiveOut; + + // Extend intervals to reach all uses in WorkList. + while (!WorkList.empty()) { + SlotIndex Idx = WorkList.back().first; + VNInfo *VNI = WorkList.back().second; + WorkList.pop_back(); + const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(Idx.getPrevSlot()); + SlotIndex BlockStart = Indexes.getMBBStartIdx(MBB); + + // Extend the live range for VNI to be live at Idx. + if (VNInfo *ExtVNI = LR.extendInBlock(BlockStart, Idx)) { + assert(ExtVNI == VNI && "Unexpected existing value number"); + (void)ExtVNI; + // Is this a PHIDef we haven't seen before? + if (!VNI->isPHIDef() || VNI->def != BlockStart || + !UsedPHIs.insert(VNI).second) + continue; + // The PHI is live, make sure the predecessors are live-out. + for (const MachineBasicBlock *Pred : MBB->predecessors()) { + if (!LiveOut.insert(Pred).second) + continue; + SlotIndex Stop = Indexes.getMBBEndIdx(Pred); + // A predecessor is not required to have a live-out value for a PHI. + if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop)) + WorkList.push_back(std::make_pair(Stop, PVNI)); + } + continue; + } + + // VNI is live-in to MBB. + DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); + LR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI)); + + // Make sure VNI is live-out from the predecessors. + for (const MachineBasicBlock *Pred : MBB->predecessors()) { + if (!LiveOut.insert(Pred).second) + continue; + SlotIndex Stop = Indexes.getMBBEndIdx(Pred); + assert(OldRange.getVNInfoBefore(Stop) == VNI && + "Wrong value out of predecessor"); + WorkList.push_back(std::make_pair(Stop, VNI)); + } + } +} + +bool LiveIntervals::shrinkToUses(LiveInterval *li, + SmallVectorImpl *dead) { + DEBUG(dbgs() << "Shrink: " << *li << '\n'); + assert(TargetRegisterInfo::isVirtualRegister(li->reg) + && "Can only shrink virtual registers"); + + // Shrink subregister live ranges. + bool NeedsCleanup = false; + for (LiveInterval::SubRange &S : li->subranges()) { + shrinkToUses(S, li->reg); + if (S.empty()) + NeedsCleanup = true; + } + if (NeedsCleanup) + li->removeEmptySubRanges(); + + // Find all the values used, including PHI kills. + ShrinkToUsesWorkList WorkList; + + // Visit all instructions reading li->reg. + unsigned Reg = li->reg; + for (MachineInstr &UseMI : MRI->reg_instructions(Reg)) { + if (UseMI.isDebugValue() || !UseMI.readsVirtualRegister(Reg)) + continue; + SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); + LiveQueryResult LRQ = li->Query(Idx); + VNInfo *VNI = LRQ.valueIn(); + if (!VNI) { + // This shouldn't happen: readsVirtualRegister returns true, but there is + // no live value. It is likely caused by a target getting flags + // wrong. + DEBUG(dbgs() << Idx << '\t' << UseMI + << "Warning: Instr claims to read non-existent value in " + << *li << '\n'); + continue; + } + // Special case: An early-clobber tied operand reads and writes the + // register one slot early. + if (VNInfo *DefVNI = LRQ.valueDefined()) + Idx = DefVNI->def; + + WorkList.push_back(std::make_pair(Idx, VNI)); + } + + // Create new live ranges with only minimal live segments per def. + LiveRange NewLR; + createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end())); + extendSegmentsToUses(NewLR, *Indexes, WorkList, *li); + + // Move the trimmed segments back. + li->segments.swap(NewLR.segments); + + // Handle dead values. + bool CanSeparate = computeDeadValues(*li, dead); + DEBUG(dbgs() << "Shrunk: " << *li << '\n'); + return CanSeparate; +} + +bool LiveIntervals::computeDeadValues(LiveInterval &LI, + SmallVectorImpl *dead) { + bool MayHaveSplitComponents = false; + for (VNInfo *VNI : LI.valnos) { + if (VNI->isUnused()) + continue; + SlotIndex Def = VNI->def; + LiveRange::iterator I = LI.FindSegmentContaining(Def); + assert(I != LI.end() && "Missing segment for VNI"); + + // Is the register live before? Otherwise we may have to add a read-undef + // flag for subregister defs. + unsigned VReg = LI.reg; + if (MRI->shouldTrackSubRegLiveness(VReg)) { + if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) { + MachineInstr *MI = getInstructionFromIndex(Def); + MI->setRegisterDefReadUndef(VReg); + } + } + + if (I->end != Def.getDeadSlot()) + continue; + if (VNI->isPHIDef()) { + // This is a dead PHI. Remove it. + VNI->markUnused(); + LI.removeSegment(I); + DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n"); + MayHaveSplitComponents = true; + } else { + // This is a dead def. Make sure the instruction knows. + MachineInstr *MI = getInstructionFromIndex(Def); + assert(MI && "No instruction defining live value"); + MI->addRegisterDead(LI.reg, TRI); + if (dead && MI->allDefsAreDead()) { + DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI); + dead->push_back(MI); + } + } + } + return MayHaveSplitComponents; +} + +void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) { + DEBUG(dbgs() << "Shrink: " << SR << '\n'); + assert(TargetRegisterInfo::isVirtualRegister(Reg) + && "Can only shrink virtual registers"); + // Find all the values used, including PHI kills. + ShrinkToUsesWorkList WorkList; + + // Visit all instructions reading Reg. + SlotIndex LastIdx; + for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) { + // Skip "undef" uses. + if (!MO.readsReg()) + continue; + // Maybe the operand is for a subregister we don't care about. + unsigned SubReg = MO.getSubReg(); + if (SubReg != 0) { + LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg); + if ((LaneMask & SR.LaneMask).none()) + continue; + } + // We only need to visit each instruction once. + MachineInstr *UseMI = MO.getParent(); + SlotIndex Idx = getInstructionIndex(*UseMI).getRegSlot(); + if (Idx == LastIdx) + continue; + LastIdx = Idx; + + LiveQueryResult LRQ = SR.Query(Idx); + VNInfo *VNI = LRQ.valueIn(); + // For Subranges it is possible that only undef values are left in that + // part of the subregister, so there is no real liverange at the use + if (!VNI) + continue; + + // Special case: An early-clobber tied operand reads and writes the + // register one slot early. + if (VNInfo *DefVNI = LRQ.valueDefined()) + Idx = DefVNI->def; + + WorkList.push_back(std::make_pair(Idx, VNI)); + } + + // Create a new live ranges with only minimal live segments per def. + LiveRange NewLR; + createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end())); + extendSegmentsToUses(NewLR, *Indexes, WorkList, SR); + + // Move the trimmed ranges back. + SR.segments.swap(NewLR.segments); + + // Remove dead PHI value numbers + for (VNInfo *VNI : SR.valnos) { + if (VNI->isUnused()) + continue; + const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def); + assert(Segment != nullptr && "Missing segment for VNI"); + if (Segment->end != VNI->def.getDeadSlot()) + continue; + if (VNI->isPHIDef()) { + // This is a dead PHI. Remove it. + DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); + VNI->markUnused(); + SR.removeSegment(*Segment); + } + } + + DEBUG(dbgs() << "Shrunk: " << SR << '\n'); +} + +void LiveIntervals::extendToIndices(LiveRange &LR, + ArrayRef Indices, + ArrayRef Undefs) { + assert(LRCalc && "LRCalc not initialized."); + LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); + for (SlotIndex Idx : Indices) + LRCalc->extend(LR, Idx, /*PhysReg=*/0, Undefs); +} + +void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill, + SmallVectorImpl *EndPoints) { + LiveQueryResult LRQ = LR.Query(Kill); + VNInfo *VNI = LRQ.valueOutOrDead(); + if (!VNI) + return; + + MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill); + SlotIndex MBBEnd = Indexes->getMBBEndIdx(KillMBB); + + // If VNI isn't live out from KillMBB, the value is trivially pruned. + if (LRQ.endPoint() < MBBEnd) { + LR.removeSegment(Kill, LRQ.endPoint()); + if (EndPoints) EndPoints->push_back(LRQ.endPoint()); + return; + } + + // VNI is live out of KillMBB. + LR.removeSegment(Kill, MBBEnd); + if (EndPoints) EndPoints->push_back(MBBEnd); + + // Find all blocks that are reachable from KillMBB without leaving VNI's live + // range. It is possible that KillMBB itself is reachable, so start a DFS + // from each successor. + using VisitedTy = df_iterator_default_set; + VisitedTy Visited; + for (MachineBasicBlock *Succ : KillMBB->successors()) { + for (df_ext_iterator + I = df_ext_begin(Succ, Visited), E = df_ext_end(Succ, Visited); + I != E;) { + MachineBasicBlock *MBB = *I; + + // Check if VNI is live in to MBB. + SlotIndex MBBStart, MBBEnd; + std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB); + LiveQueryResult LRQ = LR.Query(MBBStart); + if (LRQ.valueIn() != VNI) { + // This block isn't part of the VNI segment. Prune the search. + I.skipChildren(); + continue; + } + + // Prune the search if VNI is killed in MBB. + if (LRQ.endPoint() < MBBEnd) { + LR.removeSegment(MBBStart, LRQ.endPoint()); + if (EndPoints) EndPoints->push_back(LRQ.endPoint()); + I.skipChildren(); + continue; + } + + // VNI is live through MBB. + LR.removeSegment(MBBStart, MBBEnd); + if (EndPoints) EndPoints->push_back(MBBEnd); + ++I; + } + } +} + +//===----------------------------------------------------------------------===// +// Register allocator hooks. +// + +void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { + // Keep track of regunit ranges. + SmallVector, 8> RU; + // Keep track of subregister ranges. + SmallVector, 4> SRs; + + for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { + unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + if (MRI->reg_nodbg_empty(Reg)) + continue; + const LiveInterval &LI = getInterval(Reg); + if (LI.empty()) + continue; + + // Find the regunit intervals for the assigned register. They may overlap + // the virtual register live range, cancelling any kills. + RU.clear(); + for (MCRegUnitIterator Unit(VRM->getPhys(Reg), TRI); Unit.isValid(); + ++Unit) { + const LiveRange &RURange = getRegUnit(*Unit); + if (RURange.empty()) + continue; + RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end))); + } + + if (MRI->subRegLivenessEnabled()) { + SRs.clear(); + for (const LiveInterval::SubRange &SR : LI.subranges()) { + SRs.push_back(std::make_pair(&SR, SR.find(LI.begin()->end))); + } + } + + // Every instruction that kills Reg corresponds to a segment range end + // point. + for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE; + ++RI) { + // A block index indicates an MBB edge. + if (RI->end.isBlock()) + continue; + MachineInstr *MI = getInstructionFromIndex(RI->end); + if (!MI) + continue; + + // Check if any of the regunits are live beyond the end of RI. That could + // happen when a physreg is defined as a copy of a virtreg: + // + // %EAX = COPY %vreg5 + // FOO %vreg5 <--- MI, cancel kill because %EAX is live. + // BAR %EAX + // + // There should be no kill flag on FOO when %vreg5 is rewritten as %EAX. + for (auto &RUP : RU) { + const LiveRange &RURange = *RUP.first; + LiveRange::const_iterator &I = RUP.second; + if (I == RURange.end()) + continue; + I = RURange.advanceTo(I, RI->end); + if (I == RURange.end() || I->start >= RI->end) + continue; + // I is overlapping RI. + goto CancelKill; + } + + if (MRI->subRegLivenessEnabled()) { + // When reading a partial undefined value we must not add a kill flag. + // The regalloc might have used the undef lane for something else. + // Example: + // %vreg1 = ... ; R32: %vreg1 + // %vreg2:high16 = ... ; R64: %vreg2 + // = read %vreg2 ; R64: %vreg2 + // = read %vreg1 ; R32: %vreg1 + // The flag is correct for %vreg2, but the register allocator may + // assign R0L to %vreg1, and R0 to %vreg2 because the low 32bits of R0 + // are actually never written by %vreg2. After assignment the + // flag at the read instruction is invalid. + LaneBitmask DefinedLanesMask; + if (!SRs.empty()) { + // Compute a mask of lanes that are defined. + DefinedLanesMask = LaneBitmask::getNone(); + for (auto &SRP : SRs) { + const LiveInterval::SubRange &SR = *SRP.first; + LiveRange::const_iterator &I = SRP.second; + if (I == SR.end()) + continue; + I = SR.advanceTo(I, RI->end); + if (I == SR.end() || I->start >= RI->end) + continue; + // I is overlapping RI + DefinedLanesMask |= SR.LaneMask; + } + } else + DefinedLanesMask = LaneBitmask::getAll(); + + bool IsFullWrite = false; + for (const MachineOperand &MO : MI->operands()) { + if (!MO.isReg() || MO.getReg() != Reg) + continue; + if (MO.isUse()) { + // Reading any undefined lanes? + LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg()); + if ((UseMask & ~DefinedLanesMask).any()) + goto CancelKill; + } else if (MO.getSubReg() == 0) { + // Writing to the full register? + assert(MO.isDef()); + IsFullWrite = true; + } + } + + // If an instruction writes to a subregister, a new segment starts in + // the LiveInterval. But as this is only overriding part of the register + // adding kill-flags is not correct here after registers have been + // assigned. + if (!IsFullWrite) { + // Next segment has to be adjacent in the subregister write case. + LiveRange::const_iterator N = std::next(RI); + if (N != LI.end() && N->start == RI->end) + goto CancelKill; + } + } + + MI->addRegisterKilled(Reg, nullptr); + continue; +CancelKill: + MI->clearRegisterKills(Reg, nullptr); + } + } +} + +MachineBasicBlock* +LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const { + // A local live range must be fully contained inside the block, meaning it is + // defined and killed at instructions, not at block boundaries. It is not + // live in or or out of any block. + // + // It is technically possible to have a PHI-defined live range identical to a + // single block, but we are going to return false in that case. + + SlotIndex Start = LI.beginIndex(); + if (Start.isBlock()) + return nullptr; + + SlotIndex Stop = LI.endIndex(); + if (Stop.isBlock()) + return nullptr; + + // getMBBFromIndex doesn't need to search the MBB table when both indexes + // belong to proper instructions. + MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start); + MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop); + return MBB1 == MBB2 ? MBB1 : nullptr; +} + +bool +LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const { + for (const VNInfo *PHI : LI.valnos) { + if (PHI->isUnused() || !PHI->isPHIDef()) + continue; + const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def); + // Conservatively return true instead of scanning huge predecessor lists. + if (PHIMBB->pred_size() > 100) + return true; + for (const MachineBasicBlock *Pred : PHIMBB->predecessors()) + if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(Pred))) + return true; + } + return false; +} + +float LiveIntervals::getSpillWeight(bool isDef, bool isUse, + const MachineBlockFrequencyInfo *MBFI, + const MachineInstr &MI) { + return getSpillWeight(isDef, isUse, MBFI, MI.getParent()); +} + +float LiveIntervals::getSpillWeight(bool isDef, bool isUse, + const MachineBlockFrequencyInfo *MBFI, + const MachineBasicBlock *MBB) { + BlockFrequency Freq = MBFI->getBlockFreq(MBB); + const float Scale = 1.0f / MBFI->getEntryFreq(); + return (isDef + isUse) * (Freq.getFrequency() * Scale); +} + +LiveRange::Segment +LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr &startInst) { + LiveInterval& Interval = createEmptyInterval(reg); + VNInfo *VN = Interval.getNextValue( + SlotIndex(getInstructionIndex(startInst).getRegSlot()), + getVNInfoAllocator()); + LiveRange::Segment S(SlotIndex(getInstructionIndex(startInst).getRegSlot()), + getMBBEndIdx(startInst.getParent()), VN); + Interval.addSegment(S); + + return S; +} + +//===----------------------------------------------------------------------===// +// Register mask functions +//===----------------------------------------------------------------------===// + +bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI, + BitVector &UsableRegs) { + if (LI.empty()) + return false; + LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end(); + + // Use a smaller arrays for local live ranges. + ArrayRef Slots; + ArrayRef Bits; + if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) { + Slots = getRegMaskSlotsInBlock(MBB->getNumber()); + Bits = getRegMaskBitsInBlock(MBB->getNumber()); + } else { + Slots = getRegMaskSlots(); + Bits = getRegMaskBits(); + } + + // We are going to enumerate all the register mask slots contained in LI. + // Start with a binary search of RegMaskSlots to find a starting point. + ArrayRef::iterator SlotI = + std::lower_bound(Slots.begin(), Slots.end(), LiveI->start); + ArrayRef::iterator SlotE = Slots.end(); + + // No slots in range, LI begins after the last call. + if (SlotI == SlotE) + return false; + + bool Found = false; + while (true) { + assert(*SlotI >= LiveI->start); + // Loop over all slots overlapping this segment. + while (*SlotI < LiveI->end) { + // *SlotI overlaps LI. Collect mask bits. + if (!Found) { + // This is the first overlap. Initialize UsableRegs to all ones. + UsableRegs.clear(); + UsableRegs.resize(TRI->getNumRegs(), true); + Found = true; + } + // Remove usable registers clobbered by this mask. + UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]); + if (++SlotI == SlotE) + return Found; + } + // *SlotI is beyond the current LI segment. + LiveI = LI.advanceTo(LiveI, *SlotI); + if (LiveI == LiveE) + return Found; + // Advance SlotI until it overlaps. + while (*SlotI < LiveI->start) + if (++SlotI == SlotE) + return Found; + } +} + +//===----------------------------------------------------------------------===// +// IntervalUpdate class. +//===----------------------------------------------------------------------===// + +/// Toolkit used by handleMove to trim or extend live intervals. +class LiveIntervals::HMEditor { +private: + LiveIntervals& LIS; + const MachineRegisterInfo& MRI; + const TargetRegisterInfo& TRI; + SlotIndex OldIdx; + SlotIndex NewIdx; + SmallPtrSet Updated; + bool UpdateFlags; + +public: + HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI, + const TargetRegisterInfo& TRI, + SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags) + : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx), + UpdateFlags(UpdateFlags) {} + + // FIXME: UpdateFlags is a workaround that creates live intervals for all + // physregs, even those that aren't needed for regalloc, in order to update + // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill + // flags, and postRA passes will use a live register utility instead. + LiveRange *getRegUnitLI(unsigned Unit) { + if (UpdateFlags) + return &LIS.getRegUnit(Unit); + return LIS.getCachedRegUnit(Unit); + } + + /// Update all live ranges touched by MI, assuming a move from OldIdx to + /// NewIdx. + void updateAllRanges(MachineInstr *MI) { + DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": " << *MI); + bool hasRegMask = false; + for (MachineOperand &MO : MI->operands()) { + if (MO.isRegMask()) + hasRegMask = true; + if (!MO.isReg()) + continue; + if (MO.isUse()) { + if (!MO.readsReg()) + continue; + // Aggressively clear all kill flags. + // They are reinserted by VirtRegRewriter. + MO.setIsKill(false); + } + + unsigned Reg = MO.getReg(); + if (!Reg) + continue; + if (TargetRegisterInfo::isVirtualRegister(Reg)) { + LiveInterval &LI = LIS.getInterval(Reg); + if (LI.hasSubRanges()) { + unsigned SubReg = MO.getSubReg(); + LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg) + : MRI.getMaxLaneMaskForVReg(Reg); + for (LiveInterval::SubRange &S : LI.subranges()) { + if ((S.LaneMask & LaneMask).none()) + continue; + updateRange(S, Reg, S.LaneMask); + } + } + updateRange(LI, Reg, LaneBitmask::getNone()); + continue; + } + + // For physregs, only update the regunits that actually have a + // precomputed live range. + for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units) + if (LiveRange *LR = getRegUnitLI(*Units)) + updateRange(*LR, *Units, LaneBitmask::getNone()); + } + if (hasRegMask) + updateRegMaskSlots(); + } + +private: + /// Update a single live range, assuming an instruction has been moved from + /// OldIdx to NewIdx. + void updateRange(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) { + if (!Updated.insert(&LR).second) + return; + DEBUG({ + dbgs() << " "; + if (TargetRegisterInfo::isVirtualRegister(Reg)) { + dbgs() << PrintReg(Reg); + if (LaneMask.any()) + dbgs() << " L" << PrintLaneMask(LaneMask); + } else { + dbgs() << PrintRegUnit(Reg, &TRI); + } + dbgs() << ":\t" << LR << '\n'; + }); + if (SlotIndex::isEarlierInstr(OldIdx, NewIdx)) + handleMoveDown(LR); + else + handleMoveUp(LR, Reg, LaneMask); + DEBUG(dbgs() << " -->\t" << LR << '\n'); + LR.verify(); + } + + /// Update LR to reflect an instruction has been moved downwards from OldIdx + /// to NewIdx (OldIdx < NewIdx). + void handleMoveDown(LiveRange &LR) { + LiveRange::iterator E = LR.end(); + // Segment going into OldIdx. + LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex()); + + // No value live before or after OldIdx? Nothing to do. + if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start)) + return; + + LiveRange::iterator OldIdxOut; + // Do we have a value live-in to OldIdx? + if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) { + // If the live-in value already extends to NewIdx, there is nothing to do. + if (SlotIndex::isEarlierEqualInstr(NewIdx, OldIdxIn->end)) + return; + // Aggressively remove all kill flags from the old kill point. + // Kill flags shouldn't be used while live intervals exist, they will be + // reinserted by VirtRegRewriter. + if (MachineInstr *KillMI = LIS.getInstructionFromIndex(OldIdxIn->end)) + for (MIBundleOperands MO(*KillMI); MO.isValid(); ++MO) + if (MO->isReg() && MO->isUse()) + MO->setIsKill(false); + + // Is there a def before NewIdx which is not OldIdx? + LiveRange::iterator Next = std::next(OldIdxIn); + if (Next != E && !SlotIndex::isSameInstr(OldIdx, Next->start) && + SlotIndex::isEarlierInstr(Next->start, NewIdx)) { + // If we are here then OldIdx was just a use but not a def. We only have + // to ensure liveness extends to NewIdx. + LiveRange::iterator NewIdxIn = + LR.advanceTo(Next, NewIdx.getBaseIndex()); + // Extend the segment before NewIdx if necessary. + if (NewIdxIn == E || + !SlotIndex::isEarlierInstr(NewIdxIn->start, NewIdx)) { + LiveRange::iterator Prev = std::prev(NewIdxIn); + Prev->end = NewIdx.getRegSlot(); + } + // Extend OldIdxIn. + OldIdxIn->end = Next->start; + return; + } + + // Adjust OldIdxIn->end to reach NewIdx. This may temporarily make LR + // invalid by overlapping ranges. + bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end); + OldIdxIn->end = NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber()); + // If this was not a kill, then there was no def and we're done. + if (!isKill) + return; + + // Did we have a Def at OldIdx? + OldIdxOut = Next; + if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start)) + return; + } else { + OldIdxOut = OldIdxIn; + } + + // If we are here then there is a Definition at OldIdx. OldIdxOut points + // to the segment starting there. + assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) && + "No def?"); + VNInfo *OldIdxVNI = OldIdxOut->valno; + assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def"); + + // If the defined value extends beyond NewIdx, just move the beginning + // of the segment to NewIdx. + SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber()); + if (SlotIndex::isEarlierInstr(NewIdxDef, OldIdxOut->end)) { + OldIdxVNI->def = NewIdxDef; + OldIdxOut->start = OldIdxVNI->def; + return; + } + + // If we are here then we have a Definition at OldIdx which ends before + // NewIdx. + + // Is there an existing Def at NewIdx? + LiveRange::iterator AfterNewIdx + = LR.advanceTo(OldIdxOut, NewIdx.getRegSlot()); + bool OldIdxDefIsDead = OldIdxOut->end.isDead(); + if (!OldIdxDefIsDead && + SlotIndex::isEarlierInstr(OldIdxOut->end, NewIdxDef)) { + // OldIdx is not a dead def, and NewIdxDef is inside a new interval. + VNInfo *DefVNI; + if (OldIdxOut != LR.begin() && + !SlotIndex::isEarlierInstr(std::prev(OldIdxOut)->end, + OldIdxOut->start)) { + // There is no gap between OldIdxOut and its predecessor anymore, + // merge them. + LiveRange::iterator IPrev = std::prev(OldIdxOut); + DefVNI = OldIdxVNI; + IPrev->end = OldIdxOut->end; + } else { + // The value is live in to OldIdx + LiveRange::iterator INext = std::next(OldIdxOut); + assert(INext != E && "Must have following segment"); + // We merge OldIdxOut and its successor. As we're dealing with subreg + // reordering, there is always a successor to OldIdxOut in the same BB + // We don't need INext->valno anymore and will reuse for the new segment + // we create later. + DefVNI = OldIdxVNI; + INext->start = OldIdxOut->end; + INext->valno->def = INext->start; + } + // If NewIdx is behind the last segment, extend that and append a new one. + if (AfterNewIdx == E) { + // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up + // one position. + // |- ?/OldIdxOut -| |- X0 -| ... |- Xn -| end + // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS -| end + std::copy(std::next(OldIdxOut), E, OldIdxOut); + // The last segment is undefined now, reuse it for a dead def. + LiveRange::iterator NewSegment = std::prev(E); + *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(), + DefVNI); + DefVNI->def = NewIdxDef; + + LiveRange::iterator Prev = std::prev(NewSegment); + Prev->end = NewIdxDef; + } else { + // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up + // one position. + // |- ?/OldIdxOut -| |- X0 -| ... |- Xn/AfterNewIdx -| |- Next -| + // => |- X0/OldIdxOut -| ... |- Xn -| |- Xn/AfterNewIdx -| |- Next -| + std::copy(std::next(OldIdxOut), std::next(AfterNewIdx), OldIdxOut); + LiveRange::iterator Prev = std::prev(AfterNewIdx); + // We have two cases: + if (SlotIndex::isEarlierInstr(Prev->start, NewIdxDef)) { + // Case 1: NewIdx is inside a liverange. Split this liverange at + // NewIdxDef into the segment "Prev" followed by "NewSegment". + LiveRange::iterator NewSegment = AfterNewIdx; + *NewSegment = LiveRange::Segment(NewIdxDef, Prev->end, Prev->valno); + Prev->valno->def = NewIdxDef; + + *Prev = LiveRange::Segment(Prev->start, NewIdxDef, DefVNI); + DefVNI->def = Prev->start; + } else { + // Case 2: NewIdx is in a lifetime hole. Keep AfterNewIdx as is and + // turn Prev into a segment from NewIdx to AfterNewIdx->start. + *Prev = LiveRange::Segment(NewIdxDef, AfterNewIdx->start, DefVNI); + DefVNI->def = NewIdxDef; + assert(DefVNI != AfterNewIdx->valno); + } + } + return; + } + + if (AfterNewIdx != E && + SlotIndex::isSameInstr(AfterNewIdx->start, NewIdxDef)) { + // There is an existing def at NewIdx. The def at OldIdx is coalesced into + // that value. + assert(AfterNewIdx->valno != OldIdxVNI && "Multiple defs of value?"); + LR.removeValNo(OldIdxVNI); + } else { + // There was no existing def at NewIdx. We need to create a dead def + // at NewIdx. Shift segments over the old OldIdxOut segment, this frees + // a new segment at the place where we want to construct the dead def. + // |- OldIdxOut -| |- X0 -| ... |- Xn -| |- AfterNewIdx -| + // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS. -| |- AfterNewIdx -| + assert(AfterNewIdx != OldIdxOut && "Inconsistent iterators"); + std::copy(std::next(OldIdxOut), AfterNewIdx, OldIdxOut); + // We can reuse OldIdxVNI now. + LiveRange::iterator NewSegment = std::prev(AfterNewIdx); + VNInfo *NewSegmentVNI = OldIdxVNI; + NewSegmentVNI->def = NewIdxDef; + *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(), + NewSegmentVNI); + } + } + + /// Update LR to reflect an instruction has been moved upwards from OldIdx + /// to NewIdx (NewIdx < OldIdx). + void handleMoveUp(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) { + LiveRange::iterator E = LR.end(); + // Segment going into OldIdx. + LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex()); + + // No value live before or after OldIdx? Nothing to do. + if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start)) + return; + + LiveRange::iterator OldIdxOut; + // Do we have a value live-in to OldIdx? + if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) { + // If the live-in value isn't killed here, then we have no Def at + // OldIdx, moreover the value must be live at NewIdx so there is nothing + // to do. + bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end); + if (!isKill) + return; + + // At this point we have to move OldIdxIn->end back to the nearest + // previous use or (dead-)def but no further than NewIdx. + SlotIndex DefBeforeOldIdx + = std::max(OldIdxIn->start.getDeadSlot(), + NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber())); + OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, Reg, LaneMask); + + // Did we have a Def at OldIdx? If not we are done now. + OldIdxOut = std::next(OldIdxIn); + if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start)) + return; + } else { + OldIdxOut = OldIdxIn; + OldIdxIn = OldIdxOut != LR.begin() ? std::prev(OldIdxOut) : E; + } + + // If we are here then there is a Definition at OldIdx. OldIdxOut points + // to the segment starting there. + assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) && + "No def?"); + VNInfo *OldIdxVNI = OldIdxOut->valno; + assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def"); + bool OldIdxDefIsDead = OldIdxOut->end.isDead(); + + // Is there an existing def at NewIdx? + SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber()); + LiveRange::iterator NewIdxOut = LR.find(NewIdx.getRegSlot()); + if (SlotIndex::isSameInstr(NewIdxOut->start, NewIdx)) { + assert(NewIdxOut->valno != OldIdxVNI && + "Same value defined more than once?"); + // If OldIdx was a dead def remove it. + if (!OldIdxDefIsDead) { + // Remove segment starting at NewIdx and move begin of OldIdxOut to + // NewIdx so it can take its place. + OldIdxVNI->def = NewIdxDef; + OldIdxOut->start = NewIdxDef; + LR.removeValNo(NewIdxOut->valno); + } else { + // Simply remove the dead def at OldIdx. + LR.removeValNo(OldIdxVNI); + } + } else { + // Previously nothing was live after NewIdx, so all we have to do now is + // move the begin of OldIdxOut to NewIdx. + if (!OldIdxDefIsDead) { + // Do we have any intermediate Defs between OldIdx and NewIdx? + if (OldIdxIn != E && + SlotIndex::isEarlierInstr(NewIdxDef, OldIdxIn->start)) { + // OldIdx is not a dead def and NewIdx is before predecessor start. + LiveRange::iterator NewIdxIn = NewIdxOut; + assert(NewIdxIn == LR.find(NewIdx.getBaseIndex())); + const SlotIndex SplitPos = NewIdxDef; + OldIdxVNI = OldIdxIn->valno; + + // Merge the OldIdxIn and OldIdxOut segments into OldIdxOut. + OldIdxOut->valno->def = OldIdxIn->start; + *OldIdxOut = LiveRange::Segment(OldIdxIn->start, OldIdxOut->end, + OldIdxOut->valno); + // OldIdxIn and OldIdxVNI are now undef and can be overridden. + // We Slide [NewIdxIn, OldIdxIn) down one position. + // |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -| + // => |- undef/NexIdxIn -| |- X0 -| ... |- Xn-1 -| |- Xn/OldIdxOut -| + std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut); + // NewIdxIn is now considered undef so we can reuse it for the moved + // value. + LiveRange::iterator NewSegment = NewIdxIn; + LiveRange::iterator Next = std::next(NewSegment); + if (SlotIndex::isEarlierInstr(Next->start, NewIdx)) { + // There is no gap between NewSegment and its predecessor. + *NewSegment = LiveRange::Segment(Next->start, SplitPos, + Next->valno); + *Next = LiveRange::Segment(SplitPos, Next->end, OldIdxVNI); + Next->valno->def = SplitPos; + } else { + // There is a gap between NewSegment and its predecessor + // Value becomes live in. + *NewSegment = LiveRange::Segment(SplitPos, Next->start, OldIdxVNI); + NewSegment->valno->def = SplitPos; + } + } else { + // Leave the end point of a live def. + OldIdxOut->start = NewIdxDef; + OldIdxVNI->def = NewIdxDef; + if (OldIdxIn != E && SlotIndex::isEarlierInstr(NewIdx, OldIdxIn->end)) + OldIdxIn->end = NewIdx.getRegSlot(); + } + } else { + // OldIdxVNI is a dead def. It may have been moved across other values + // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut) + // down one position. + // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - | + // => |- undef/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -| + std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut)); + // OldIdxVNI can be reused now to build a new dead def segment. + LiveRange::iterator NewSegment = NewIdxOut; + VNInfo *NewSegmentVNI = OldIdxVNI; + *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(), + NewSegmentVNI); + NewSegmentVNI->def = NewIdxDef; + } + } + } + + void updateRegMaskSlots() { + SmallVectorImpl::iterator RI = + std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(), + OldIdx); + assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() && + "No RegMask at OldIdx."); + *RI = NewIdx.getRegSlot(); + assert((RI == LIS.RegMaskSlots.begin() || + SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) && + "Cannot move regmask instruction above another call"); + assert((std::next(RI) == LIS.RegMaskSlots.end() || + SlotIndex::isEarlierInstr(*RI, *std::next(RI))) && + "Cannot move regmask instruction below another call"); + } + + // Return the last use of reg between NewIdx and OldIdx. + SlotIndex findLastUseBefore(SlotIndex Before, unsigned Reg, + LaneBitmask LaneMask) { + if (TargetRegisterInfo::isVirtualRegister(Reg)) { + SlotIndex LastUse = Before; + for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) { + if (MO.isUndef()) + continue; + unsigned SubReg = MO.getSubReg(); + if (SubReg != 0 && LaneMask.any() + && (TRI.getSubRegIndexLaneMask(SubReg) & LaneMask).none()) + continue; + + const MachineInstr &MI = *MO.getParent(); + SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI); + if (InstSlot > LastUse && InstSlot < OldIdx) + LastUse = InstSlot.getRegSlot(); + } + return LastUse; + } + + // This is a regunit interval, so scanning the use list could be very + // expensive. Scan upwards from OldIdx instead. + assert(Before < OldIdx && "Expected upwards move"); + SlotIndexes *Indexes = LIS.getSlotIndexes(); + MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Before); + + // OldIdx may not correspond to an instruction any longer, so set MII to + // point to the next instruction after OldIdx, or MBB->end(). + MachineBasicBlock::iterator MII = MBB->end(); + if (MachineInstr *MI = Indexes->getInstructionFromIndex( + Indexes->getNextNonNullIndex(OldIdx))) + if (MI->getParent() == MBB) + MII = MI; + + MachineBasicBlock::iterator Begin = MBB->begin(); + while (MII != Begin) { + if ((--MII)->isDebugValue()) + continue; + SlotIndex Idx = Indexes->getInstructionIndex(*MII); + + // Stop searching when Before is reached. + if (!SlotIndex::isEarlierInstr(Before, Idx)) + return Before; + + // Check if MII uses Reg. + for (MIBundleOperands MO(*MII); MO.isValid(); ++MO) + if (MO->isReg() && !MO->isUndef() && + TargetRegisterInfo::isPhysicalRegister(MO->getReg()) && + TRI.hasRegUnit(MO->getReg(), Reg)) + return Idx.getRegSlot(); + } + // Didn't reach Before. It must be the first instruction in the block. + return Before; + } +}; + +void LiveIntervals::handleMove(MachineInstr &MI, bool UpdateFlags) { + assert(!MI.isBundled() && "Can't handle bundled instructions yet."); + SlotIndex OldIndex = Indexes->getInstructionIndex(MI); + Indexes->removeMachineInstrFromMaps(MI); + SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI); + assert(getMBBStartIdx(MI.getParent()) <= OldIndex && + OldIndex < getMBBEndIdx(MI.getParent()) && + "Cannot handle moves across basic block boundaries."); + + HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); + HME.updateAllRanges(&MI); +} + +void LiveIntervals::handleMoveIntoBundle(MachineInstr &MI, + MachineInstr &BundleStart, + bool UpdateFlags) { + SlotIndex OldIndex = Indexes->getInstructionIndex(MI); + SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart); + HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); + HME.updateAllRanges(&MI); +} + +void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin, + const MachineBasicBlock::iterator End, + const SlotIndex endIdx, + LiveRange &LR, const unsigned Reg, + LaneBitmask LaneMask) { + LiveInterval::iterator LII = LR.find(endIdx); + SlotIndex lastUseIdx; + if (LII == LR.begin()) { + // This happens when the function is called for a subregister that only + // occurs _after_ the range that is to be repaired. + return; + } + if (LII != LR.end() && LII->start < endIdx) + lastUseIdx = LII->end; + else + --LII; + + for (MachineBasicBlock::iterator I = End; I != Begin;) { + --I; + MachineInstr &MI = *I; + if (MI.isDebugValue()) + continue; + + SlotIndex instrIdx = getInstructionIndex(MI); + bool isStartValid = getInstructionFromIndex(LII->start); + bool isEndValid = getInstructionFromIndex(LII->end); + + // FIXME: This doesn't currently handle early-clobber or multiple removed + // defs inside of the region to repair. + for (MachineInstr::mop_iterator OI = MI.operands_begin(), + OE = MI.operands_end(); + OI != OE; ++OI) { + const MachineOperand &MO = *OI; + if (!MO.isReg() || MO.getReg() != Reg) + continue; + + unsigned SubReg = MO.getSubReg(); + LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg); + if ((Mask & LaneMask).none()) + continue; + + if (MO.isDef()) { + if (!isStartValid) { + if (LII->end.isDead()) { + SlotIndex prevStart; + if (LII != LR.begin()) + prevStart = std::prev(LII)->start; + + // FIXME: This could be more efficient if there was a + // removeSegment method that returned an iterator. + LR.removeSegment(*LII, true); + if (prevStart.isValid()) + LII = LR.find(prevStart); + else + LII = LR.begin(); + } else { + LII->start = instrIdx.getRegSlot(); + LII->valno->def = instrIdx.getRegSlot(); + if (MO.getSubReg() && !MO.isUndef()) + lastUseIdx = instrIdx.getRegSlot(); + else + lastUseIdx = SlotIndex(); + continue; + } + } + + if (!lastUseIdx.isValid()) { + VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator); + LiveRange::Segment S(instrIdx.getRegSlot(), + instrIdx.getDeadSlot(), VNI); + LII = LR.addSegment(S); + } else if (LII->start != instrIdx.getRegSlot()) { + VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator); + LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI); + LII = LR.addSegment(S); + } + + if (MO.getSubReg() && !MO.isUndef()) + lastUseIdx = instrIdx.getRegSlot(); + else + lastUseIdx = SlotIndex(); + } else if (MO.isUse()) { + // FIXME: This should probably be handled outside of this branch, + // either as part of the def case (for defs inside of the region) or + // after the loop over the region. + if (!isEndValid && !LII->end.isBlock()) + LII->end = instrIdx.getRegSlot(); + if (!lastUseIdx.isValid()) + lastUseIdx = instrIdx.getRegSlot(); + } + } + } +} + +void +LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB, + MachineBasicBlock::iterator Begin, + MachineBasicBlock::iterator End, + ArrayRef OrigRegs) { + // Find anchor points, which are at the beginning/end of blocks or at + // instructions that already have indexes. + while (Begin != MBB->begin() && !Indexes->hasIndex(*Begin)) + --Begin; + while (End != MBB->end() && !Indexes->hasIndex(*End)) + ++End; + + SlotIndex endIdx; + if (End == MBB->end()) + endIdx = getMBBEndIdx(MBB).getPrevSlot(); + else + endIdx = getInstructionIndex(*End); + + Indexes->repairIndexesInRange(MBB, Begin, End); + + for (MachineBasicBlock::iterator I = End; I != Begin;) { + --I; + MachineInstr &MI = *I; + if (MI.isDebugValue()) + continue; + for (MachineInstr::const_mop_iterator MOI = MI.operands_begin(), + MOE = MI.operands_end(); + MOI != MOE; ++MOI) { + if (MOI->isReg() && + TargetRegisterInfo::isVirtualRegister(MOI->getReg()) && + !hasInterval(MOI->getReg())) { + createAndComputeVirtRegInterval(MOI->getReg()); + } + } + } + + for (unsigned Reg : OrigRegs) { + if (!TargetRegisterInfo::isVirtualRegister(Reg)) + continue; + + LiveInterval &LI = getInterval(Reg); + // FIXME: Should we support undefs that gain defs? + if (!LI.hasAtLeastOneValue()) + continue; + + for (LiveInterval::SubRange &S : LI.subranges()) + repairOldRegInRange(Begin, End, endIdx, S, Reg, S.LaneMask); + + repairOldRegInRange(Begin, End, endIdx, LI, Reg); + } +} + +void LiveIntervals::removePhysRegDefAt(unsigned Reg, SlotIndex Pos) { + for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) { + if (LiveRange *LR = getCachedRegUnit(*Unit)) + if (VNInfo *VNI = LR->getVNInfoAt(Pos)) + LR->removeValNo(VNI); + } +} + +void LiveIntervals::removeVRegDefAt(LiveInterval &LI, SlotIndex Pos) { + // LI may not have the main range computed yet, but its subranges may + // be present. + VNInfo *VNI = LI.getVNInfoAt(Pos); + if (VNI != nullptr) { + assert(VNI->def.getBaseIndex() == Pos.getBaseIndex()); + LI.removeValNo(VNI); + } + + // Also remove the value defined in subranges. + for (LiveInterval::SubRange &S : LI.subranges()) { + if (VNInfo *SVNI = S.getVNInfoAt(Pos)) + if (SVNI->def.getBaseIndex() == Pos.getBaseIndex()) + S.removeValNo(SVNI); + } + LI.removeEmptySubRanges(); +} + +void LiveIntervals::splitSeparateComponents(LiveInterval &LI, + SmallVectorImpl &SplitLIs) { + ConnectedVNInfoEqClasses ConEQ(*this); + unsigned NumComp = ConEQ.Classify(LI); + if (NumComp <= 1) + return; + DEBUG(dbgs() << " Split " << NumComp << " components: " << LI << '\n'); + unsigned Reg = LI.reg; + const TargetRegisterClass *RegClass = MRI->getRegClass(Reg); + for (unsigned I = 1; I < NumComp; ++I) { + unsigned NewVReg = MRI->createVirtualRegister(RegClass); + LiveInterval &NewLI = createEmptyInterval(NewVReg); + SplitLIs.push_back(&NewLI); + } + ConEQ.Distribute(LI, SplitLIs.data(), *MRI); +} + +void LiveIntervals::constructMainRangeFromSubranges(LiveInterval &LI) { + assert(LRCalc && "LRCalc not initialized."); + LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); + LRCalc->constructMainRangeFromSubranges(LI); +} Index: lib/CodeGen/RegAllocGreedy.cpp =================================================================== --- lib/CodeGen/RegAllocGreedy.cpp +++ lib/CodeGen/RegAllocGreedy.cpp @@ -23,6 +23,7 @@ #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/IndexedMap.h" +#include "llvm/ADT/MapVector.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" @@ -129,6 +130,12 @@ cl::desc("Cost for first time use of callee-saved register."), cl::init(0), cl::Hidden); +static cl::opt ConsiderLocalIntervalCost( + "condsider-local-interval-cost", cl::Hidden, + cl::desc("Consider the cost of local intervals created by a split " + "candidate when choosing the best split candidate."), + cl::init(false)); + static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", createGreedyRegisterAllocator); @@ -277,6 +284,57 @@ } }; + /// EvictionTrack - Keeps track of past evictions in order to optimize region + /// split decision. + class EvictionTrack { + + public: + using EvictorInfo = + std::pair; + using EvicteeInfo = llvm::MapVector; + + private: + /// Each Vreg that has been evicted in the last stage of selectOrSplit will + /// be mapped to the evictor Vreg and the PhysReg it was evicted from. + EvicteeInfo Evictees; + + public: + /// \breif Clear all eviction information. + void Clear() { Evictees.clear(); } + + /// \breif Clear eviction information for the given evictee Vreg. + /// E.g. when Vreg get's a new allocation, the old eviction info is no + /// longer relevant. + /// \param Evictee The evictee Vreg for whom we want to clear collected + /// eviction info. + void ClearEvicteeInfo(unsigned Evictee) { Evictees.erase(Evictee); } + + /// \breif Track new eviction. + /// The Evictor vreg has evicted the Evictee vreg from Physreg. + /// \praram PhysReg The phisical register Evictee was evicted from. + /// \praram Evictor The evictor Vreg that evicted Evictee. + /// \praram Evictee The evictee Vreg. + void AddEviction(unsigned PhysReg, unsigned Evictor, unsigned Evictee) { + Evictees[Evictee].first = Evictor; + Evictees[Evictee].second = PhysReg; + } + + /// Return the Evictor Vreg which evicted Evictee Vreg from PhysReg. + /// \praram Evictee The evictee vreg. + /// \return The Evictor vreg which evicted Evictee vreg from PhysReg. 0 if + /// nobody has evicted Evictee from PhysReg. + EvictorInfo GetEvictor(unsigned Evictee) { + if (Evictees.count(Evictee)) { + return Evictees[Evictee]; + } + + return EvictorInfo(0, 0); + } + }; + + // Keeps track of past evictions in order to optimize region split decision. + EvictionTrack LastEvicted; + // splitting state. std::unique_ptr SA; std::unique_ptr SE; @@ -340,6 +398,10 @@ /// obtained from the TargetSubtargetInfo. bool EnableLocalReassign; + /// Enable or not the the consideration of the cost of local intervals created + /// by a split candidate when choosing the best split candidate. + bool EnableAdvancedRASplitCost; + /// Set of broken hints that may be reconciled later because of eviction. SmallSetVector SetOfBrokenHints; @@ -382,13 +444,24 @@ bool addSplitConstraints(InterferenceCache::Cursor, BlockFrequency&); void addThroughConstraints(InterferenceCache::Cursor, ArrayRef); void growRegion(GlobalSplitCandidate &Cand); - BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate&); + bool splitCanCauseEvictionChain(unsigned Evictee, GlobalSplitCandidate &Cand, + unsigned BBNumber, + const AllocationOrder &Order); + BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate &, + const AllocationOrder &Order, + bool *canCauseEvictionChain); bool calcCompactRegion(GlobalSplitCandidate&); void splitAroundRegion(LiveRangeEdit&, ArrayRef); void calcGapWeights(unsigned, SmallVectorImpl&); unsigned canReassign(LiveInterval &VirtReg, unsigned PhysReg); bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool); bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&); + bool canEvictInterferenceInRange(LiveInterval &VirtReg, unsigned PhysReg, + SlotIndex Start, SlotIndex End, + EvictionCost &MaxCost); + unsigned getCheapestEvicteeWeight(const AllocationOrder &Order, + LiveInterval &VirtReg, SlotIndex Start, + SlotIndex End, float *BestEvictWeight); void evictInterference(LiveInterval&, unsigned, SmallVectorImpl&); bool mayRecolorAllInterferences(unsigned PhysReg, LiveInterval &VirtReg, @@ -405,7 +478,8 @@ unsigned calculateRegionSplitCost(LiveInterval &VirtReg, AllocationOrder &Order, BlockFrequency &BestCost, - unsigned &NumCands, bool IgnoreCSR); + unsigned &NumCands, bool IgnoreCSR, + bool *canCauseEvictionChain = nullptr); /// Perform region splitting. unsigned doRegionSplit(LiveInterval &VirtReg, unsigned BestCand, bool HasCompact, @@ -856,6 +930,92 @@ return true; } +/// \brief Return true if all interferences between VirtReg and PhysReg between +/// Start and End can be evicted. +/// +/// \param VirtReg Live range that is about to be assigned. +/// \param PhysReg Desired register for assignment. +/// \param Start Start of range to look for interferences. +/// \param End End of range to look for interferences. +/// \param MaxCost Only look for cheaper candidates and update with new cost +/// when returning true. +/// \return True when interference can be evicted cheaper than MaxCost. +bool RAGreedy::canEvictInterferenceInRange(LiveInterval &VirtReg, + unsigned PhysReg, SlotIndex Start, + SlotIndex End, + EvictionCost &MaxCost) { + EvictionCost Cost; + + for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { + LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); + + // Check if any interfering live range is heavier than MaxWeight. + for (unsigned i = Q.interferingVRegs().size(); i; --i) { + LiveInterval *Intf = Q.interferingVRegs()[i - 1]; + + // Check if interference overlast the segment in interest. + if (!Intf->overlaps(Start, End)) + continue; + + // Cannot evict non virtual reg interference. + if (!TargetRegisterInfo::isVirtualRegister(Intf->reg)) + return false; + // Never evict spill products. They cannot split or spill. + if (getStage(*Intf) == RS_Done) + return false; + + // Would this break a satisfied hint? + bool BreaksHint = VRM->hasPreferredPhys(Intf->reg); + // Update eviction cost. + Cost.BrokenHints += BreaksHint; + Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight); + // Abort if this would be too expensive. + if (!(Cost < MaxCost)) + return false; + } + } + + if (Cost.MaxWeight == 0) + return false; + + MaxCost = Cost; + return true; +} + +/// \brief Return tthe physical register that will be best +/// candidate for eviction by a local split interval that will be created +/// between Start and End. +/// +/// \param Order The allocation order +/// \param VirtReg Live range that is about to be assigned. +/// \param Start Start of range to look for interferences +/// \param End End of range to look for interferences +/// \param BestEvictweight The eviction cost of that eviction +/// \return The PhysReg which is the best candidate for eviction and the +/// eviction cost in BestEvictweight +unsigned RAGreedy::getCheapestEvicteeWeight(const AllocationOrder &Order, + LiveInterval &VirtReg, + SlotIndex Start, SlotIndex End, + float *BestEvictweight) { + EvictionCost BestEvictCost; + BestEvictCost.setMax(); + BestEvictCost.MaxWeight = VirtReg.weight; + unsigned BestEvicteePhys = 0; + + // Go over all physical registers and find the best candidate for eviction + for (auto PhysReg : Order.getOrder()) { + + if (!canEvictInterferenceInRange(VirtReg, PhysReg, Start, End, + BestEvictCost)) + continue; + + // Best so far. + BestEvicteePhys = PhysReg; + } + *BestEvictweight = BestEvictCost.MaxWeight; + return BestEvicteePhys; +} + /// evictInterference - Evict any interferring registers that prevent VirtReg /// from being assigned to Physreg. This assumes that canEvictInterference /// returned true. @@ -890,6 +1050,9 @@ // The same VirtReg may be present in multiple RegUnits. Skip duplicates. if (!VRM->hasPhys(Intf->reg)) continue; + + LastEvicted.AddEviction(PhysReg, VirtReg.reg, Intf->reg); + Matrix->unassign(*Intf); assert((ExtraRegInfo[Intf->reg].Cascade < Cascade || VirtReg.isSpillable() < Intf->isSpillable()) && @@ -1211,13 +1374,117 @@ return Cost; } +/// \brief Chek if splitting Evictee will create a local split interval in basic +/// block number BBNumber that may cause a bad eviction chain. This is intended +/// to prevent bad eviction sequences like: +/// movl %ebp, 8(%esp) # 4-byte Spill +/// movl %ecx, %ebp +/// movl %ebx, %ecx +/// movl %edi, %ebx +/// movl %edx, %edi +/// cltd +/// idivl %esi +/// movl %edi, %edx +/// movl %ebx, %edi +/// movl %ecx, %ebx +/// movl %ebp, %ecx +/// movl 16(%esp), %ebp # 4 - byte Reload +/// +/// Such sequences are created in 2 scenarios: +/// +/// Scenario #1: +/// vreg0 is evicted from physreg0 by vreg1. +/// Evictee vreg0 is intended for region splitting with split candidate +/// physreg0 (the reg vreg0 was evicted from). +/// Region splitting creates a local interval because of interference with the +/// evictor vreg1 (normally region spliitting creates 2 interval, the "by reg" +/// and "by stack" intervals and local interval created when interference +/// occurs). +/// One of the split intervals ends up evicting vreg2 from physreg1. +/// Evictee vreg2 is intended for region splitting with split candidate +/// physreg1. +/// One of the split intervals ends up evicting vreg3 from physreg2, etc. +/// +/// Scenario #2 +/// vreg0 is evicted from physreg0 by vreg1. +/// vreg2 is evicted from physreg2 by vreg3 etc. +/// Evictee vreg0 is intended for region splitting with split candidate +/// physreg1. +/// Region splitting creates a local interval because of interference with the +/// evictor vreg1. +/// One of the split intervals ends up evicting back original evictor vreg1 +/// from physreg0 (the reg vreg0 was evicted from). +/// Another evictee vreg2 is intended for region splitting with split candidate +/// physreg1. +/// One of the split intervals ends up evicting vreg3 from physreg2, etc. +/// +/// \param Evictee The register considered to be split. +/// \param Cand The split candidate that determines the physical register +/// we are splitting for and the interferences. +/// \param BBNumber The number of a BB for which the region split process will +/// create a local split interval. +/// \param Order The phisical registers that may get evicted by a split +/// artifact of Evictee. +/// \return True if splitting Evictee may cause a bad eviction chain, false +/// otherwise. +bool RAGreedy::splitCanCauseEvictionChain(unsigned Evictee, + GlobalSplitCandidate &Cand, + unsigned BBNumber, + const AllocationOrder &Order) { + EvictionTrack::EvictorInfo VregEvictorInfo = LastEvicted.GetEvictor(Evictee); + unsigned Evictor = VregEvictorInfo.first; + unsigned PhysReg = VregEvictorInfo.second; + + // No actual evictor. + if (!Evictor || !PhysReg) + return false; + + float MaxWeight = 0; + unsigned FutureEvictedPhysReg = + getCheapestEvicteeWeight(Order, LIS->getInterval(Evictee), + Cand.Intf.first(), Cand.Intf.last(), &MaxWeight); + + // The bad eviction chain occurs when either the split candidate the the + // evited reg or one of the split artifact will evict the evicting reg. + if ((PhysReg != Cand.PhysReg) && (PhysReg != FutureEvictedPhysReg)) + return false; + + Cand.Intf.moveToBlock(BBNumber); + + // Check to see if the Evictor contains interference (with Evictee) in the + // given BB. If so, this interference caused the eviction of Evictee from + // PhysReg. This suggest that we will create a local interval during the + // region split to avoid this interference This local interval may cause a bad + // eviction chain. + if (!LIS->hasInterval(Evictor)) + return false; + LiveInterval &evictorLI = LIS->getInterval(Evictor); + if (evictorLI.FindSegmentContaining(Cand.Intf.first()) == evictorLI.end()) + return false; + + // Now, check to see if the local interval we will create is going to be + // expensive enough to evict somebody If so, this may cause a bad eviction + // chain. + VirtRegAuxInfo VRAI(*MF, *LIS, VRM, getAnalysis(), *MBFI); + float splitArtifactWeight = + VRAI.futureWeight(LIS->getInterval(Evictee), + Cand.Intf.first().getPrevIndex(), Cand.Intf.last()); + if (splitArtifactWeight >= 0 && splitArtifactWeight < MaxWeight) + return false; + + return true; +} + /// calcGlobalSplitCost - Return the global split cost of following the split /// pattern in LiveBundles. This cost should be added to the local cost of the /// interference pattern in SplitConstraints. /// -BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand) { +BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand, + const AllocationOrder &Order, + bool *canCauseEvictionChain) { BlockFrequency GlobalCost = 0; const BitVector &LiveBundles = Cand.LiveBundles; + unsigned VirtRegToSplit = SA->getParent().reg; ArrayRef UseBlocks = SA->getUseBlocks(); for (unsigned i = 0; i != UseBlocks.size(); ++i) { const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; @@ -1226,6 +1493,24 @@ bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, true)]; unsigned Ins = 0; + Cand.Intf.moveToBlock(BC.Number); + // Check wheather a local interval is going to be created during the region + // split. + if (EnableAdvancedRASplitCost && canCauseEvictionChain && + Cand.Intf.hasInterference() && BI.LiveIn && BI.LiveOut && RegIn && + RegOut) { + + if (splitCanCauseEvictionChain(VirtRegToSplit, Cand, BC.Number, Order)) { + // This interfernce cause our eviction from this assignment, we might + // evict somebody else, add that cost. + // See splitCanCauseEvictionChain for detailed description of scenarios. + GlobalCost += SpillPlacer->getBlockFrequency(BC.Number); + GlobalCost += SpillPlacer->getBlockFrequency(BC.Number); + + *canCauseEvictionChain = true; + } + } + if (BI.LiveIn) Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg); if (BI.LiveOut) @@ -1246,6 +1531,20 @@ if (Cand.Intf.hasInterference()) { GlobalCost += SpillPlacer->getBlockFrequency(Number); GlobalCost += SpillPlacer->getBlockFrequency(Number); + + // Check wheather a local interval is going to be created during the + // region split. + if (EnableAdvancedRASplitCost && canCauseEvictionChain && + splitCanCauseEvictionChain(VirtRegToSplit, Cand, Number, Order)) { + // This interfernce cause our eviction from this assignment, we might + // evict somebody else, add that cost. + // See splitCanCauseEvictionChain for detailed description of + // scenarios. + GlobalCost += SpillPlacer->getBlockFrequency(Number); + GlobalCost += SpillPlacer->getBlockFrequency(Number); + + *canCauseEvictionChain = true; + } } continue; } @@ -1410,6 +1709,7 @@ unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl &NewVRegs) { unsigned NumCands = 0; + BlockFrequency SpillCost = calcSpillCost(); BlockFrequency BestCost; // Check if we can split this live range around a compact region. @@ -1421,14 +1721,24 @@ } else { // No benefit from the compact region, our fallback will be per-block // splitting. Make sure we find a solution that is cheaper than spilling. - BestCost = calcSpillCost(); + BestCost = SpillCost; DEBUG(dbgs() << "Cost of isolating all blocks = "; MBFI->printBlockFreq(dbgs(), BestCost) << '\n'); } + bool canCauseEvictionChain = false; unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost, NumCands, - false/*IgnoreCSR*/); + false /*IgnoreCSR*/, &canCauseEvictionChain); + + // Split candidates with compact regions can cause a bad eviction sequence. + // See splitCanCauseEvictionChain for detailed description of scenarios. + // To avoid it, we need to comapre the cost with the spill cost and not the + // current max frequency. + if (HasCompact && (BestCost > SpillCost) && (BestCand != NoCand) && + canCauseEvictionChain) { + return 0; + } // No solutions found, fall back to single block splitting. if (!HasCompact && BestCand == NoCand) @@ -1440,8 +1750,8 @@ unsigned RAGreedy::calculateRegionSplitCost(LiveInterval &VirtReg, AllocationOrder &Order, BlockFrequency &BestCost, - unsigned &NumCands, - bool IgnoreCSR) { + unsigned &NumCands, bool IgnoreCSR, + bool *canCauseEvictionChain) { unsigned BestCand = NoCand; Order.rewind(); while (unsigned PhysReg = Order.next()) { @@ -1501,7 +1811,8 @@ continue; } - Cost += calcGlobalSplitCost(Cand); + bool hasEvictionChain = false; + Cost += calcGlobalSplitCost(Cand, Order, &hasEvictionChain); DEBUG({ dbgs() << ", total = "; MBFI->printBlockFreq(dbgs(), Cost) << " with bundles"; @@ -1512,9 +1823,24 @@ if (Cost < BestCost) { BestCand = NumCands; BestCost = Cost; + // See splitCanCauseEvictionChain for detailed description of bad + // eviction chain scenarios. + if (canCauseEvictionChain) + *canCauseEvictionChain = hasEvictionChain; } ++NumCands; } + + if (canCauseEvictionChain && BestCand != NoCand) { + // See splitCanCauseEvictionChain for detailed description of bad + // eviction chain scenarios. + DEBUG(dbgs() << "Best split candidate of vreg " + << PrintReg(VirtReg.reg, TRI) << " may "); + if (!(*canCauseEvictionChain)) + DEBUG(dbgs() << "not "); + DEBUG(dbgs() << "cause bad eviction chain\n"); + } + return BestCand; } @@ -2565,6 +2891,8 @@ // First try assigning a free register. AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix); if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) { + // If VirtReg got an assignment, the eviction info is no longre relevant. + LastEvicted.ClearEvicteeInfo(VirtReg.reg); // When NewVRegs is not empty, we may have made decisions such as evicting // a virtual register, go with the earlier decisions and use the physical // register. @@ -2598,6 +2926,9 @@ // copy-related live-ranges. if (Hint && Hint != PhysReg) SetOfBrokenHints.insert(&VirtReg); + // If VirtReg eviction someone, the eviction info for it as an evictee is + // no longre relevant. + LastEvicted.ClearEvicteeInfo(VirtReg.reg); return PhysReg; } @@ -2617,8 +2948,11 @@ // Try splitting VirtReg or interferences. unsigned NewVRegSizeBefore = NewVRegs.size(); unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); - if (PhysReg || (NewVRegs.size() - NewVRegSizeBefore)) + if (PhysReg || (NewVRegs.size() - NewVRegSizeBefore)) { + // If VirtReg got split, the eviction info is no longre relevant. + LastEvicted.ClearEvicteeInfo(VirtReg.reg); return PhysReg; + } } // If we couldn't allocate a register from spilling, there is probably some @@ -2729,6 +3063,9 @@ MF->getSubtarget().enableRALocalReassignment( MF->getTarget().getOptLevel()); + EnableAdvancedRASplitCost = ConsiderLocalIntervalCost || + MF->getSubtarget().enableAdvancedRASplitCost(); + if (VerifyEnabled) MF->verify(this, "Before greedy register allocator"); @@ -2760,6 +3097,7 @@ IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI); GlobalCand.resize(32); // This will grow as needed. SetOfBrokenHints.clear(); + LastEvicted.Clear(); allocatePhysRegs(); tryHintsRecoloring(); Index: lib/CodeGen/TargetSubtargetInfo.cpp =================================================================== --- lib/CodeGen/TargetSubtargetInfo.cpp +++ lib/CodeGen/TargetSubtargetInfo.cpp @@ -50,6 +50,10 @@ return true; } +bool TargetSubtargetInfo::enableAdvancedRASplitCost() const { + return false; +} + bool TargetSubtargetInfo::enablePostRAScheduler() const { return getSchedModel().PostRAScheduler; } Index: lib/Target/X86/X86Subtarget.h =================================================================== --- lib/Target/X86/X86Subtarget.h +++ lib/Target/X86/X86Subtarget.h @@ -655,6 +655,10 @@ AntiDepBreakMode getAntiDepBreakMode() const override { return TargetSubtargetInfo::ANTIDEP_CRITICAL; } + + virtual bool enableAdvancedRASplitCost() const { + return true; + } }; } // end namespace llvm Index: test/CodeGen/X86/bug26810.ll =================================================================== --- /dev/null +++ test/CodeGen/X86/bug26810.ll @@ -0,0 +1,312 @@ +; RUN: llc < %s -march=x86 -regalloc=greedy -stop-after=greedy | FileCheck %s +; Make sure bad eviction sequence doesnt occur + +; Fix for bugzilla 26810. +; This test is meant to make sure bad eviction sequence like the one described +; below does not occur +; +; movapd %xmm7, 160(%esp) # 16-byte Spill +; movapd %xmm5, %xmm7 +; movapd %xmm4, %xmm5 +; movapd %xmm3, %xmm4 +; movapd %xmm2, %xmm3 +; some_inst +; movapd %xmm3, %xmm2 +; movapd %xmm4, %xmm3 +; movapd %xmm5, %xmm4 +; movapd %xmm7, %xmm5 +; movapd 160(%esp), %xmm7 # 16-byte Reload + +; Make sure we have no redundant copies in the problematic code section +; CHECK-LABEL: name: loop +; CHECK: bb.2.for.body: +; CHECK: SUBPDrr +; CHECK-NEXT: MOVAPSmr +; CHECK-NEXT: MOVAPSrm +; CHECK-NEXT: MULPDrm +; CHECK-NEXT: ADDPDrr +; CHECK-NEXT: ADD32ri8 + +target datalayout = "e-m:x-p:32:32-i64:64-f80:32-n8:16:32-a:0:32-S32" +target triple = "i386-pc-linux-gnu" + +%struct._iobuf = type { i8* } + +$"\01??_C@_01NOFIACDB@w?$AA@" = comdat any + +$"\01??_C@_09LAIDGMDM@?1dev?1null?$AA@" = comdat any + +@"\01?v@@3PAU__m128d@@A" = global [8 x <2 x double>] zeroinitializer, align 16 +@"\01?m1@@3PAU__m128d@@A" = local_unnamed_addr global [76800000 x <2 x double>] zeroinitializer, align 16 +@"\01?m2@@3PAU__m128d@@A" = local_unnamed_addr global [8 x <2 x double>] zeroinitializer, align 16 +@"\01??_C@_01NOFIACDB@w?$AA@" = linkonce_odr unnamed_addr constant [2 x i8] c"w\00", comdat, align 1 +@"\01??_C@_09LAIDGMDM@?1dev?1null?$AA@" = linkonce_odr unnamed_addr constant [10 x i8] c"/dev/null\00", comdat, align 1 + +; Function Attrs: norecurse +define i32 @main() local_unnamed_addr #0 { +entry: + tail call void @init() + %0 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 0), align 16, !tbaa !8 + %1 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 1), align 16, !tbaa !8 + %2 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 2), align 16, !tbaa !8 + %3 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 3), align 16, !tbaa !8 + %4 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 4), align 16, !tbaa !8 + %5 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 5), align 16, !tbaa !8 + %6 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 6), align 16, !tbaa !8 + %7 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 7), align 16, !tbaa !8 + %.promoted.i = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 0), align 16, !tbaa !8 + %.promoted51.i = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 1), align 16, !tbaa !8 + %.promoted53.i = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 2), align 16, !tbaa !8 + %.promoted55.i = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 3), align 16, !tbaa !8 + %.promoted57.i = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 4), align 16, !tbaa !8 + %.promoted59.i = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 5), align 16, !tbaa !8 + %.promoted61.i = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 6), align 16, !tbaa !8 + %.promoted63.i = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 7), align 16, !tbaa !8 + br label %for.body.i + +for.body.i: ; preds = %for.body.i, %entry + %add.i64.i = phi <2 x double> [ %.promoted63.i, %entry ], [ %add.i.i, %for.body.i ] + %add.i3662.i = phi <2 x double> [ %.promoted61.i, %entry ], [ %add.i36.i, %for.body.i ] + %add.i3860.i = phi <2 x double> [ %.promoted59.i, %entry ], [ %add.i38.i, %for.body.i ] + %add.i4058.i = phi <2 x double> [ %.promoted57.i, %entry ], [ %add.i40.i, %for.body.i ] + %add.i4256.i = phi <2 x double> [ %.promoted55.i, %entry ], [ %add.i42.i, %for.body.i ] + %add.i4454.i = phi <2 x double> [ %.promoted53.i, %entry ], [ %add.i44.i, %for.body.i ] + %add.i4652.i = phi <2 x double> [ %.promoted51.i, %entry ], [ %add.i46.i, %for.body.i ] + %add.i4850.i = phi <2 x double> [ %.promoted.i, %entry ], [ %add.i48.i, %for.body.i ] + %i.049.i = phi i32 [ 0, %entry ], [ %inc.i, %for.body.i ] + %arrayidx.i = getelementptr inbounds [76800000 x <2 x double>], [76800000 x <2 x double>]* @"\01?m1@@3PAU__m128d@@A", i32 0, i32 %i.049.i + %8 = load <2 x double>, <2 x double>* %arrayidx.i, align 16, !tbaa !8 + %mul.i.i = fmul <2 x double> %0, %8 + %add.i48.i = fadd <2 x double> %add.i4850.i, %mul.i.i + %mul.i47.i = fmul <2 x double> %1, %8 + %add.i46.i = fadd <2 x double> %add.i4652.i, %mul.i47.i + %mul.i45.i = fmul <2 x double> %2, %8 + %add.i44.i = fadd <2 x double> %add.i4454.i, %mul.i45.i + %mul.i43.i = fmul <2 x double> %3, %8 + %add.i42.i = fadd <2 x double> %add.i4256.i, %mul.i43.i + %mul.i41.i = fmul <2 x double> %4, %8 + %add.i40.i = fadd <2 x double> %add.i4058.i, %mul.i41.i + %mul.i39.i = fmul <2 x double> %5, %8 + %add.i38.i = fadd <2 x double> %add.i3860.i, %mul.i39.i + %mul.i37.i = fmul <2 x double> %6, %8 + %add.i36.i = fsub <2 x double> %add.i3662.i, %mul.i37.i + %mul.i35.i = fmul <2 x double> %7, %8 + %add.i.i = fadd <2 x double> %add.i64.i, %mul.i35.i + %inc.i = add nuw nsw i32 %i.049.i, 1 + %exitcond.i = icmp eq i32 %inc.i, 76800000 + br i1 %exitcond.i, label %loop.exit, label %for.body.i + +loop.exit: ; preds = %for.body.i + store <2 x double> %add.i48.i, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 0), align 16, !tbaa !8 + store <2 x double> %add.i46.i, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 1), align 16, !tbaa !8 + store <2 x double> %add.i46.i, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 1), align 16, !tbaa !8 + store <2 x double> %add.i44.i, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 2), align 16, !tbaa !8 + store <2 x double> %add.i42.i, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 3), align 16, !tbaa !8 + store <2 x double> %add.i40.i, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 4), align 16, !tbaa !8 + store <2 x double> %add.i38.i, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 5), align 16, !tbaa !8 + store <2 x double> %add.i36.i, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 6), align 16, !tbaa !8 + store <2 x double> %add.i.i, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 7), align 16, !tbaa !8 + %call.i = tail call %struct._iobuf* @fopen(i8* getelementptr inbounds ([10 x i8], [10 x i8]* @"\01??_C@_09LAIDGMDM@?1dev?1null?$AA@", i32 0, i32 0), i8* getelementptr inbounds ([2 x i8], [2 x i8]* @"\01??_C@_01NOFIACDB@w?$AA@", i32 0, i32 0)) #7 + %call1.i = tail call i32 @fwrite(i8* bitcast ([8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A" to i8*), i32 16, i32 8, %struct._iobuf* %call.i) #7 + %call2.i = tail call i32 @fclose(%struct._iobuf* %call.i) #7 + ret i32 0 +} + +define void @init() local_unnamed_addr #1 { +entry: + call void @llvm.memset.p0i8.i32(i8* bitcast ([8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A" to i8*), i8 0, i32 128, i32 16, i1 false) + %call.i = tail call i64 @_time64(i64* null) + %conv = trunc i64 %call.i to i32 + tail call void @srand(i32 %conv) + br label %for.body6 + +for.body6: ; preds = %for.body6, %entry + %i2.051 = phi i32 [ 0, %entry ], [ %inc14, %for.body6 ] + %call7 = tail call i32 @rand() + %conv8 = sitofp i32 %call7 to double + %tmp.sroa.0.0.vec.insert = insertelement <2 x double> undef, double %conv8, i32 0 + %call9 = tail call i32 @rand() + %conv10 = sitofp i32 %call9 to double + %tmp.sroa.0.8.vec.insert = insertelement <2 x double> %tmp.sroa.0.0.vec.insert, double %conv10, i32 1 + %arrayidx12 = getelementptr inbounds [76800000 x <2 x double>], [76800000 x <2 x double>]* @"\01?m1@@3PAU__m128d@@A", i32 0, i32 %i2.051 + store <2 x double> %tmp.sroa.0.8.vec.insert, <2 x double>* %arrayidx12, align 16, !tbaa !8 + %inc14 = add nuw nsw i32 %i2.051, 1 + %exitcond = icmp eq i32 %inc14, 76800000 + br i1 %exitcond, label %for.body21.preheader, label %for.body6 + +for.body21.preheader: ; preds = %for.body6 + %call25 = tail call i32 @rand() + %conv26 = sitofp i32 %call25 to double + %tmp23.sroa.0.0.vec.insert = insertelement <2 x double> undef, double %conv26, i32 0 + %call28 = tail call i32 @rand() + %conv29 = sitofp i32 %call28 to double + %tmp23.sroa.0.8.vec.insert = insertelement <2 x double> %tmp23.sroa.0.0.vec.insert, double %conv29, i32 1 + store <2 x double> %tmp23.sroa.0.8.vec.insert, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 0), align 16, !tbaa !8 + %call25.1 = tail call i32 @rand() + %conv26.1 = sitofp i32 %call25.1 to double + %tmp23.sroa.0.0.vec.insert.1 = insertelement <2 x double> undef, double %conv26.1, i32 0 + %call28.1 = tail call i32 @rand() + %conv29.1 = sitofp i32 %call28.1 to double + %tmp23.sroa.0.8.vec.insert.1 = insertelement <2 x double> %tmp23.sroa.0.0.vec.insert.1, double %conv29.1, i32 1 + store <2 x double> %tmp23.sroa.0.8.vec.insert.1, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 1), align 16, !tbaa !8 + %call25.2 = tail call i32 @rand() + %conv26.2 = sitofp i32 %call25.2 to double + %tmp23.sroa.0.0.vec.insert.2 = insertelement <2 x double> undef, double %conv26.2, i32 0 + %call28.2 = tail call i32 @rand() + %conv29.2 = sitofp i32 %call28.2 to double + %tmp23.sroa.0.8.vec.insert.2 = insertelement <2 x double> %tmp23.sroa.0.0.vec.insert.2, double %conv29.2, i32 1 + store <2 x double> %tmp23.sroa.0.8.vec.insert.2, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 2), align 16, !tbaa !8 + %call25.3 = tail call i32 @rand() + %conv26.3 = sitofp i32 %call25.3 to double + %tmp23.sroa.0.0.vec.insert.3 = insertelement <2 x double> undef, double %conv26.3, i32 0 + %call28.3 = tail call i32 @rand() + %conv29.3 = sitofp i32 %call28.3 to double + %tmp23.sroa.0.8.vec.insert.3 = insertelement <2 x double> %tmp23.sroa.0.0.vec.insert.3, double %conv29.3, i32 1 + store <2 x double> %tmp23.sroa.0.8.vec.insert.3, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 3), align 16, !tbaa !8 + %call25.4 = tail call i32 @rand() + %conv26.4 = sitofp i32 %call25.4 to double + %tmp23.sroa.0.0.vec.insert.4 = insertelement <2 x double> undef, double %conv26.4, i32 0 + %call28.4 = tail call i32 @rand() + %conv29.4 = sitofp i32 %call28.4 to double + %tmp23.sroa.0.8.vec.insert.4 = insertelement <2 x double> %tmp23.sroa.0.0.vec.insert.4, double %conv29.4, i32 1 + store <2 x double> %tmp23.sroa.0.8.vec.insert.4, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 4), align 16, !tbaa !8 + %call25.5 = tail call i32 @rand() + %conv26.5 = sitofp i32 %call25.5 to double + %tmp23.sroa.0.0.vec.insert.5 = insertelement <2 x double> undef, double %conv26.5, i32 0 + %call28.5 = tail call i32 @rand() + %conv29.5 = sitofp i32 %call28.5 to double + %tmp23.sroa.0.8.vec.insert.5 = insertelement <2 x double> %tmp23.sroa.0.0.vec.insert.5, double %conv29.5, i32 1 + store <2 x double> %tmp23.sroa.0.8.vec.insert.5, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 5), align 16, !tbaa !8 + %call25.6 = tail call i32 @rand() + %conv26.6 = sitofp i32 %call25.6 to double + %tmp23.sroa.0.0.vec.insert.6 = insertelement <2 x double> undef, double %conv26.6, i32 0 + %call28.6 = tail call i32 @rand() + %conv29.6 = sitofp i32 %call28.6 to double + %tmp23.sroa.0.8.vec.insert.6 = insertelement <2 x double> %tmp23.sroa.0.0.vec.insert.6, double %conv29.6, i32 1 + store <2 x double> %tmp23.sroa.0.8.vec.insert.6, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 6), align 16, !tbaa !8 + %call25.7 = tail call i32 @rand() + %conv26.7 = sitofp i32 %call25.7 to double + %tmp23.sroa.0.0.vec.insert.7 = insertelement <2 x double> undef, double %conv26.7, i32 0 + %call28.7 = tail call i32 @rand() + %conv29.7 = sitofp i32 %call28.7 to double + %tmp23.sroa.0.8.vec.insert.7 = insertelement <2 x double> %tmp23.sroa.0.0.vec.insert.7, double %conv29.7, i32 1 + store <2 x double> %tmp23.sroa.0.8.vec.insert.7, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 7), align 16, !tbaa !8 + ret void +} + +; Function Attrs: norecurse nounwind +define void @loop() local_unnamed_addr #2 { +entry: + %0 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 0), align 16, !tbaa !8 + %1 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 1), align 16, !tbaa !8 + %2 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 2), align 16, !tbaa !8 + %3 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 3), align 16, !tbaa !8 + %4 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 4), align 16, !tbaa !8 + %5 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 5), align 16, !tbaa !8 + %6 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 6), align 16, !tbaa !8 + %7 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?m2@@3PAU__m128d@@A", i32 0, i32 7), align 16, !tbaa !8 + %.promoted = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 0), align 16, !tbaa !8 + %.promoted51 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 1), align 16, !tbaa !8 + %.promoted53 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 2), align 16, !tbaa !8 + %.promoted55 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 3), align 16, !tbaa !8 + %.promoted57 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 4), align 16, !tbaa !8 + %.promoted59 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 5), align 16, !tbaa !8 + %.promoted61 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 6), align 16, !tbaa !8 + %.promoted63 = load <2 x double>, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 7), align 16, !tbaa !8 + br label %for.body + +for.cond.cleanup: ; preds = %for.body + store <2 x double> %add.i48, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 0), align 16, !tbaa !8 + store <2 x double> %add.i46, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 1), align 16, !tbaa !8 + store <2 x double> %add.i44, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 2), align 16, !tbaa !8 + store <2 x double> %add.i42, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 3), align 16, !tbaa !8 + store <2 x double> %add.i40, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 4), align 16, !tbaa !8 + store <2 x double> %add.i38, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 5), align 16, !tbaa !8 + store <2 x double> %add.i36, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 6), align 16, !tbaa !8 + store <2 x double> %add.i, <2 x double>* getelementptr inbounds ([8 x <2 x double>], [8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A", i32 0, i32 7), align 16, !tbaa !8 + ret void + +for.body: ; preds = %for.body, %entry + %add.i64 = phi <2 x double> [ %.promoted63, %entry ], [ %add.i, %for.body ] + %add.i3662 = phi <2 x double> [ %.promoted61, %entry ], [ %add.i36, %for.body ] + %add.i3860 = phi <2 x double> [ %.promoted59, %entry ], [ %add.i38, %for.body ] + %add.i4058 = phi <2 x double> [ %.promoted57, %entry ], [ %add.i40, %for.body ] + %add.i4256 = phi <2 x double> [ %.promoted55, %entry ], [ %add.i42, %for.body ] + %add.i4454 = phi <2 x double> [ %.promoted53, %entry ], [ %add.i44, %for.body ] + %add.i4652 = phi <2 x double> [ %.promoted51, %entry ], [ %add.i46, %for.body ] + %add.i4850 = phi <2 x double> [ %.promoted, %entry ], [ %add.i48, %for.body ] + %i.049 = phi i32 [ 0, %entry ], [ %inc, %for.body ] + %arrayidx = getelementptr inbounds [76800000 x <2 x double>], [76800000 x <2 x double>]* @"\01?m1@@3PAU__m128d@@A", i32 0, i32 %i.049 + %8 = load <2 x double>, <2 x double>* %arrayidx, align 16, !tbaa !8 + %mul.i = fmul <2 x double> %8, %0 + %add.i48 = fadd <2 x double> %add.i4850, %mul.i + %mul.i47 = fmul <2 x double> %8, %1 + %add.i46 = fadd <2 x double> %add.i4652, %mul.i47 + %mul.i45 = fmul <2 x double> %8, %2 + %add.i44 = fadd <2 x double> %add.i4454, %mul.i45 + %mul.i43 = fmul <2 x double> %8, %3 + %add.i42 = fadd <2 x double> %add.i4256, %mul.i43 + %mul.i41 = fmul <2 x double> %8, %4 + %add.i40 = fadd <2 x double> %add.i4058, %mul.i41 + %mul.i39 = fmul <2 x double> %8, %5 + %add.i38 = fadd <2 x double> %add.i3860, %mul.i39 + %mul.i37 = fmul <2 x double> %8, %6 + %add.i36 = fsub <2 x double> %add.i3662, %mul.i37 + %mul.i35 = fmul <2 x double> %8, %7 + %add.i = fadd <2 x double> %add.i64, %mul.i35 + %inc = add nuw nsw i32 %i.049, 1 + %exitcond = icmp eq i32 %inc, 76800000 + br i1 %exitcond, label %for.cond.cleanup, label %for.body +} + +; Function Attrs: nounwind +define void @"\01?dump@@YAXXZ"() local_unnamed_addr #3 { +entry: + %call = tail call %struct._iobuf* @fopen(i8* getelementptr inbounds ([10 x i8], [10 x i8]* @"\01??_C@_09LAIDGMDM@?1dev?1null?$AA@", i32 0, i32 0), i8* getelementptr inbounds ([2 x i8], [2 x i8]* @"\01??_C@_01NOFIACDB@w?$AA@", i32 0, i32 0)) + %call1 = tail call i32 @fwrite(i8* bitcast ([8 x <2 x double>]* @"\01?v@@3PAU__m128d@@A" to i8*), i32 16, i32 8, %struct._iobuf* %call) + %call2 = tail call i32 @fclose(%struct._iobuf* %call) + ret void +} + +declare void @srand(i32) local_unnamed_addr #4 + +declare i32 @rand() local_unnamed_addr #4 + +; Function Attrs: nounwind +declare noalias %struct._iobuf* @fopen(i8* nocapture readonly, i8* nocapture readonly) local_unnamed_addr #5 + +; Function Attrs: nounwind +declare i32 @fwrite(i8* nocapture, i32, i32, %struct._iobuf* nocapture) local_unnamed_addr #5 + +; Function Attrs: nounwind +declare i32 @fclose(%struct._iobuf* nocapture) local_unnamed_addr #5 + +declare i64 @_time64(i64*) local_unnamed_addr #4 + +; Function Attrs: argmemonly nounwind +declare void @llvm.memset.p0i8.i32(i8* nocapture writeonly, i8, i32, i32, i1) #6 + +attributes #0 = { norecurse "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="pentium4" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } +attributes #1 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="pentium4" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } +attributes #2 = { norecurse nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="pentium4" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } +attributes #3 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="pentium4" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } +attributes #4 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="pentium4" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } +attributes #5 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="pentium4" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } +attributes #6 = { argmemonly nounwind } +attributes #7 = { nounwind } + +!llvm.linker.options = !{!0, !1, !2, !3, !4} +!llvm.module.flags = !{!5, !6} +!llvm.ident = !{!7} + +!0 = !{!"/FAILIFMISMATCH:\22_MSC_VER=1900\22"} +!1 = !{!"/FAILIFMISMATCH:\22_ITERATOR_DEBUG_LEVEL=0\22"} +!2 = !{!"/FAILIFMISMATCH:\22RuntimeLibrary=MT_StaticRelease\22"} +!3 = !{!"/DEFAULTLIB:libcpmt.lib"} +!4 = !{!"/FAILIFMISMATCH:\22_CRT_STDIO_ISO_WIDE_SPECIFIERS=0\22"} +!5 = !{i32 1, !"NumRegisterParameters", i32 0} +!6 = !{i32 1, !"wchar_size", i32 2} +!7 = !{!"clang version 5.0.0 (cfe/trunk 305640)"} +!8 = !{!9, !9, i64 0} +!9 = !{!"omnipotent char", !10, i64 0} +!10 = !{!"Simple C++ TBAA"} Index: test/CodeGen/X86/greedy_regalloc_bad_eviction_sequence.ll =================================================================== --- /dev/null +++ test/CodeGen/X86/greedy_regalloc_bad_eviction_sequence.ll @@ -0,0 +1,116 @@ +; RUN: llc < %s -march=x86 -regalloc=greedy -stop-after=greedy | FileCheck %s +; Make sure bad eviction sequence doesnt occur + +; Part of the fix for bugzilla 26810. +; This test is meant to make sure bad eviction sequence like the one described +; below does not occur +; +; movl %ebp, 8(%esp) # 4-byte Spill +; movl %ecx, %ebp +; movl %ebx, %ecx +; movl %edi, %ebx +; movl %edx, %edi +; cltd +; idivl %esi +; movl %edi, %edx +; movl %ebx, %edi +; movl %ecx, %ebx +; movl %ebp, %ecx +; movl 16(%esp), %ebp # 4 - byte Reload + +; Make sure we have no redundant copies in the problematic code seqtion +; CHECK-LABEL: name: bar +; CHECK: bb.3.for.body: +; CHECK: %eax = COPY +; CHECK-NEXT: CDQ +; CHECK-NEXT: IDIV32r +; CHECK-NEXT: ADD32rr + + +target datalayout = "e-m:x-p:32:32-i64:64-f80:32-n8:16:32-a:0:32-S32" +target triple = "i386-pc-linux-gnu" + + +; Function Attrs: norecurse nounwind readonly +define i32 @bar(i32 %size, i32* nocapture readonly %arr, i32* nocapture readnone %tmp) local_unnamed_addr #1 { +entry: + %0 = load i32, i32* %arr, align 4, !tbaa !3 + %arrayidx3 = getelementptr inbounds i32, i32* %arr, i32 1 + %1 = load i32, i32* %arrayidx3, align 4, !tbaa !3 + %arrayidx5 = getelementptr inbounds i32, i32* %arr, i32 2 + %2 = load i32, i32* %arrayidx5, align 4, !tbaa !3 + %arrayidx7 = getelementptr inbounds i32, i32* %arr, i32 3 + %3 = load i32, i32* %arrayidx7, align 4, !tbaa !3 + %arrayidx9 = getelementptr inbounds i32, i32* %arr, i32 4 + %4 = load i32, i32* %arrayidx9, align 4, !tbaa !3 + %arrayidx11 = getelementptr inbounds i32, i32* %arr, i32 5 + %5 = load i32, i32* %arrayidx11, align 4, !tbaa !3 + %arrayidx13 = getelementptr inbounds i32, i32* %arr, i32 6 + %6 = load i32, i32* %arrayidx13, align 4, !tbaa !3 + %arrayidx15 = getelementptr inbounds i32, i32* %arr, i32 7 + %7 = load i32, i32* %arrayidx15, align 4, !tbaa !3 + %arrayidx17 = getelementptr inbounds i32, i32* %arr, i32 8 + %8 = load i32, i32* %arrayidx17, align 4, !tbaa !3 + %cmp69 = icmp sgt i32 %size, 1 + br i1 %cmp69, label %for.body, label %for.cond.cleanup + +for.cond.cleanup: ; preds = %for.body, %entry + %x0.0.lcssa = phi i32 [ %0, %entry ], [ %add, %for.body ] + %x1.0.lcssa = phi i32 [ %1, %entry ], [ %sub, %for.body ] + %x2.0.lcssa = phi i32 [ %2, %entry ], [ %mul, %for.body ] + %x3.0.lcssa = phi i32 [ %3, %entry ], [ %div, %for.body ] + %x4.0.lcssa = phi i32 [ %4, %entry ], [ %add19, %for.body ] + %x5.0.lcssa = phi i32 [ %5, %entry ], [ %sub20, %for.body ] + %x6.0.lcssa = phi i32 [ %6, %entry ], [ %add21, %for.body ] + %x7.0.lcssa = phi i32 [ %7, %entry ], [ %mul22, %for.body ] + %x8.0.lcssa = phi i32 [ %8, %entry ], [ %sub23, %for.body ] + %mul24 = mul nsw i32 %x1.0.lcssa, %x0.0.lcssa + %mul25 = mul nsw i32 %mul24, %x2.0.lcssa + %mul26 = mul nsw i32 %mul25, %x3.0.lcssa + %mul27 = mul nsw i32 %mul26, %x4.0.lcssa + %mul28 = mul nsw i32 %mul27, %x5.0.lcssa + %mul29 = mul nsw i32 %mul28, %x6.0.lcssa + %mul30 = mul nsw i32 %mul29, %x7.0.lcssa + %mul31 = mul nsw i32 %mul30, %x8.0.lcssa + ret i32 %mul31 + +for.body: ; preds = %entry, %for.body + %i.079 = phi i32 [ %inc, %for.body ], [ 1, %entry ] + %x8.078 = phi i32 [ %sub23, %for.body ], [ %8, %entry ] + %x7.077 = phi i32 [ %mul22, %for.body ], [ %7, %entry ] + %x6.076 = phi i32 [ %add21, %for.body ], [ %6, %entry ] + %x5.075 = phi i32 [ %sub20, %for.body ], [ %5, %entry ] + %x4.074 = phi i32 [ %add19, %for.body ], [ %4, %entry ] + %x3.073 = phi i32 [ %div, %for.body ], [ %3, %entry ] + %x2.072 = phi i32 [ %mul, %for.body ], [ %2, %entry ] + %x1.071 = phi i32 [ %sub, %for.body ], [ %1, %entry ] + %x0.070 = phi i32 [ %add, %for.body ], [ %0, %entry ] + %add = add nsw i32 %x1.071, %x0.070 + %sub = sub nsw i32 %x1.071, %x2.072 + %mul = mul nsw i32 %x3.073, %x2.072 + %div = sdiv i32 %x3.073, %x4.074 + %add19 = add nsw i32 %x5.075, %x4.074 + %sub20 = sub nsw i32 %x5.075, %x6.076 + %add21 = add nsw i32 %x7.077, %x6.076 + %mul22 = mul nsw i32 %x8.078, %x7.077 + %sub23 = sub nsw i32 %x8.078, %add + %inc = add nuw nsw i32 %i.079, 1 + %exitcond = icmp eq i32 %inc, %size + br i1 %exitcond, label %for.cond.cleanup, label %for.body, !llvm.loop !7 +} + +attributes #0 = { norecurse nounwind readnone "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-features"="+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } +attributes #1 = { norecurse nounwind readonly "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-features"="+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } + +!llvm.module.flags = !{!0, !1} +!llvm.ident = !{!2} + +!0 = !{i32 1, !"NumRegisterParameters", i32 0} +!1 = !{i32 1, !"wchar_size", i32 2} +!2 = !{!"clang version 5.0.0 (cfe/trunk 305640)"} +!3 = !{!4, !4, i64 0} +!4 = !{!"int", !5, i64 0} +!5 = !{!"omnipotent char", !6, i64 0} +!6 = !{!"Simple C/C++ TBAA"} +!7 = distinct !{!7, !8} +!8 = !{!"llvm.loop.unroll.disable"}