diff options
Diffstat (limited to 'llvm/lib/CodeGen/InlineSpiller.cpp')
| -rw-r--r-- | llvm/lib/CodeGen/InlineSpiller.cpp | 1540 |
1 files changed, 1540 insertions, 0 deletions
diff --git a/llvm/lib/CodeGen/InlineSpiller.cpp b/llvm/lib/CodeGen/InlineSpiller.cpp new file mode 100644 index 000000000000..2408f18678e4 --- /dev/null +++ b/llvm/lib/CodeGen/InlineSpiller.cpp @@ -0,0 +1,1540 @@ +//===- InlineSpiller.cpp - Insert spills and restores inline --------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// The inline spiller modifies the machine function directly instead of +// inserting spills and restores in VirtRegMap. +// +//===----------------------------------------------------------------------===// + +#include "Spiller.h" +#include "SplitKit.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/MapVector.h" +#include "llvm/ADT/None.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/CodeGen/LiveInterval.h" +#include "llvm/CodeGen/LiveIntervals.h" +#include "llvm/CodeGen/LiveRangeCalc.h" +#include "llvm/CodeGen/LiveRangeEdit.h" +#include "llvm/CodeGen/LiveStacks.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/MachineInstrBundle.h" +#include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/CodeGen/MachineOperand.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/SlotIndexes.h" +#include "llvm/CodeGen/TargetInstrInfo.h" +#include "llvm/CodeGen/TargetOpcodes.h" +#include "llvm/CodeGen/TargetRegisterInfo.h" +#include "llvm/CodeGen/TargetSubtargetInfo.h" +#include "llvm/CodeGen/VirtRegMap.h" +#include "llvm/Config/llvm-config.h" +#include "llvm/Support/BlockFrequency.h" +#include "llvm/Support/BranchProbability.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" +#include <cassert> +#include <iterator> +#include <tuple> +#include <utility> +#include <vector> + +using namespace llvm; + +#define DEBUG_TYPE "regalloc" + +STATISTIC(NumSpilledRanges, "Number of spilled live ranges"); +STATISTIC(NumSnippets, "Number of spilled snippets"); +STATISTIC(NumSpills, "Number of spills inserted"); +STATISTIC(NumSpillsRemoved, "Number of spills removed"); +STATISTIC(NumReloads, "Number of reloads inserted"); +STATISTIC(NumReloadsRemoved, "Number of reloads removed"); +STATISTIC(NumFolded, "Number of folded stack accesses"); +STATISTIC(NumFoldedLoads, "Number of folded loads"); +STATISTIC(NumRemats, "Number of rematerialized defs for spilling"); + +static cl::opt<bool> DisableHoisting("disable-spill-hoist", cl::Hidden, + cl::desc("Disable inline spill hoisting")); +static cl::opt<bool> +RestrictStatepointRemat("restrict-statepoint-remat", + cl::init(false), cl::Hidden, + cl::desc("Restrict remat for statepoint operands")); + +namespace { + +class HoistSpillHelper : private LiveRangeEdit::Delegate { + MachineFunction &MF; + LiveIntervals &LIS; + LiveStacks &LSS; + AliasAnalysis *AA; + MachineDominatorTree &MDT; + MachineLoopInfo &Loops; + VirtRegMap &VRM; + MachineRegisterInfo &MRI; + const TargetInstrInfo &TII; + const TargetRegisterInfo &TRI; + const MachineBlockFrequencyInfo &MBFI; + + InsertPointAnalysis IPA; + + // Map from StackSlot to the LiveInterval of the original register. + // Note the LiveInterval of the original register may have been deleted + // after it is spilled. We keep a copy here to track the range where + // spills can be moved. + DenseMap<int, std::unique_ptr<LiveInterval>> StackSlotToOrigLI; + + // Map from pair of (StackSlot and Original VNI) to a set of spills which + // have the same stackslot and have equal values defined by Original VNI. + // These spills are mergeable and are hoist candiates. + using MergeableSpillsMap = + MapVector<std::pair<int, VNInfo *>, SmallPtrSet<MachineInstr *, 16>>; + MergeableSpillsMap MergeableSpills; + + /// This is the map from original register to a set containing all its + /// siblings. To hoist a spill to another BB, we need to find out a live + /// sibling there and use it as the source of the new spill. + DenseMap<unsigned, SmallSetVector<unsigned, 16>> Virt2SiblingsMap; + + bool isSpillCandBB(LiveInterval &OrigLI, VNInfo &OrigVNI, + MachineBasicBlock &BB, unsigned &LiveReg); + + void rmRedundantSpills( + SmallPtrSet<MachineInstr *, 16> &Spills, + SmallVectorImpl<MachineInstr *> &SpillsToRm, + DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill); + + void getVisitOrders( + MachineBasicBlock *Root, SmallPtrSet<MachineInstr *, 16> &Spills, + SmallVectorImpl<MachineDomTreeNode *> &Orders, + SmallVectorImpl<MachineInstr *> &SpillsToRm, + DenseMap<MachineDomTreeNode *, unsigned> &SpillsToKeep, + DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill); + + void runHoistSpills(LiveInterval &OrigLI, VNInfo &OrigVNI, + SmallPtrSet<MachineInstr *, 16> &Spills, + SmallVectorImpl<MachineInstr *> &SpillsToRm, + DenseMap<MachineBasicBlock *, unsigned> &SpillsToIns); + +public: + HoistSpillHelper(MachineFunctionPass &pass, MachineFunction &mf, + VirtRegMap &vrm) + : MF(mf), LIS(pass.getAnalysis<LiveIntervals>()), + LSS(pass.getAnalysis<LiveStacks>()), + AA(&pass.getAnalysis<AAResultsWrapperPass>().getAAResults()), + MDT(pass.getAnalysis<MachineDominatorTree>()), + Loops(pass.getAnalysis<MachineLoopInfo>()), VRM(vrm), + MRI(mf.getRegInfo()), TII(*mf.getSubtarget().getInstrInfo()), + TRI(*mf.getSubtarget().getRegisterInfo()), + MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()), + IPA(LIS, mf.getNumBlockIDs()) {} + + void addToMergeableSpills(MachineInstr &Spill, int StackSlot, + unsigned Original); + bool rmFromMergeableSpills(MachineInstr &Spill, int StackSlot); + void hoistAllSpills(); + void LRE_DidCloneVirtReg(unsigned, unsigned) override; +}; + +class InlineSpiller : public Spiller { + MachineFunction &MF; + LiveIntervals &LIS; + LiveStacks &LSS; + AliasAnalysis *AA; + MachineDominatorTree &MDT; + MachineLoopInfo &Loops; + VirtRegMap &VRM; + MachineRegisterInfo &MRI; + const TargetInstrInfo &TII; + const TargetRegisterInfo &TRI; + const MachineBlockFrequencyInfo &MBFI; + + // Variables that are valid during spill(), but used by multiple methods. + LiveRangeEdit *Edit; + LiveInterval *StackInt; + int StackSlot; + unsigned Original; + + // All registers to spill to StackSlot, including the main register. + SmallVector<unsigned, 8> RegsToSpill; + + // All COPY instructions to/from snippets. + // They are ignored since both operands refer to the same stack slot. + SmallPtrSet<MachineInstr*, 8> SnippetCopies; + + // Values that failed to remat at some point. + SmallPtrSet<VNInfo*, 8> UsedValues; + + // Dead defs generated during spilling. + SmallVector<MachineInstr*, 8> DeadDefs; + + // Object records spills information and does the hoisting. + HoistSpillHelper HSpiller; + + ~InlineSpiller() override = default; + +public: + InlineSpiller(MachineFunctionPass &pass, MachineFunction &mf, VirtRegMap &vrm) + : MF(mf), LIS(pass.getAnalysis<LiveIntervals>()), + LSS(pass.getAnalysis<LiveStacks>()), + AA(&pass.getAnalysis<AAResultsWrapperPass>().getAAResults()), + MDT(pass.getAnalysis<MachineDominatorTree>()), + Loops(pass.getAnalysis<MachineLoopInfo>()), VRM(vrm), + MRI(mf.getRegInfo()), TII(*mf.getSubtarget().getInstrInfo()), + TRI(*mf.getSubtarget().getRegisterInfo()), + MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()), + HSpiller(pass, mf, vrm) {} + + void spill(LiveRangeEdit &) override; + void postOptimization() override; + +private: + bool isSnippet(const LiveInterval &SnipLI); + void collectRegsToSpill(); + + bool isRegToSpill(unsigned Reg) { return is_contained(RegsToSpill, Reg); } + + bool isSibling(unsigned Reg); + bool hoistSpillInsideBB(LiveInterval &SpillLI, MachineInstr &CopyMI); + void eliminateRedundantSpills(LiveInterval &LI, VNInfo *VNI); + + void markValueUsed(LiveInterval*, VNInfo*); + bool canGuaranteeAssignmentAfterRemat(unsigned VReg, MachineInstr &MI); + bool reMaterializeFor(LiveInterval &, MachineInstr &MI); + void reMaterializeAll(); + + bool coalesceStackAccess(MachineInstr *MI, unsigned Reg); + bool foldMemoryOperand(ArrayRef<std::pair<MachineInstr *, unsigned>>, + MachineInstr *LoadMI = nullptr); + void insertReload(unsigned VReg, SlotIndex, MachineBasicBlock::iterator MI); + void insertSpill(unsigned VReg, bool isKill, MachineBasicBlock::iterator MI); + + void spillAroundUses(unsigned Reg); + void spillAll(); +}; + +} // end anonymous namespace + +Spiller::~Spiller() = default; + +void Spiller::anchor() {} + +Spiller *llvm::createInlineSpiller(MachineFunctionPass &pass, + MachineFunction &mf, + VirtRegMap &vrm) { + return new InlineSpiller(pass, mf, vrm); +} + +//===----------------------------------------------------------------------===// +// Snippets +//===----------------------------------------------------------------------===// + +// When spilling a virtual register, we also spill any snippets it is connected +// to. The snippets are small live ranges that only have a single real use, +// leftovers from live range splitting. Spilling them enables memory operand +// folding or tightens the live range around the single use. +// +// This minimizes register pressure and maximizes the store-to-load distance for +// spill slots which can be important in tight loops. + +/// isFullCopyOf - If MI is a COPY to or from Reg, return the other register, +/// otherwise return 0. +static unsigned isFullCopyOf(const MachineInstr &MI, unsigned Reg) { + if (!MI.isFullCopy()) + return 0; + if (MI.getOperand(0).getReg() == Reg) + return MI.getOperand(1).getReg(); + if (MI.getOperand(1).getReg() == Reg) + return MI.getOperand(0).getReg(); + return 0; +} + +/// isSnippet - Identify if a live interval is a snippet that should be spilled. +/// It is assumed that SnipLI is a virtual register with the same original as +/// Edit->getReg(). +bool InlineSpiller::isSnippet(const LiveInterval &SnipLI) { + unsigned Reg = Edit->getReg(); + + // A snippet is a tiny live range with only a single instruction using it + // besides copies to/from Reg or spills/fills. We accept: + // + // %snip = COPY %Reg / FILL fi# + // %snip = USE %snip + // %Reg = COPY %snip / SPILL %snip, fi# + // + if (SnipLI.getNumValNums() > 2 || !LIS.intervalIsInOneMBB(SnipLI)) + return false; + + MachineInstr *UseMI = nullptr; + + // Check that all uses satisfy our criteria. + for (MachineRegisterInfo::reg_instr_nodbg_iterator + RI = MRI.reg_instr_nodbg_begin(SnipLI.reg), + E = MRI.reg_instr_nodbg_end(); RI != E; ) { + MachineInstr &MI = *RI++; + + // Allow copies to/from Reg. + if (isFullCopyOf(MI, Reg)) + continue; + + // Allow stack slot loads. + int FI; + if (SnipLI.reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot) + continue; + + // Allow stack slot stores. + if (SnipLI.reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) + continue; + + // Allow a single additional instruction. + if (UseMI && &MI != UseMI) + return false; + UseMI = &MI; + } + return true; +} + +/// collectRegsToSpill - Collect live range snippets that only have a single +/// real use. +void InlineSpiller::collectRegsToSpill() { + unsigned Reg = Edit->getReg(); + + // Main register always spills. + RegsToSpill.assign(1, Reg); + SnippetCopies.clear(); + + // Snippets all have the same original, so there can't be any for an original + // register. + if (Original == Reg) + return; + + for (MachineRegisterInfo::reg_instr_iterator + RI = MRI.reg_instr_begin(Reg), E = MRI.reg_instr_end(); RI != E; ) { + MachineInstr &MI = *RI++; + unsigned SnipReg = isFullCopyOf(MI, Reg); + if (!isSibling(SnipReg)) + continue; + LiveInterval &SnipLI = LIS.getInterval(SnipReg); + if (!isSnippet(SnipLI)) + continue; + SnippetCopies.insert(&MI); + if (isRegToSpill(SnipReg)) + continue; + RegsToSpill.push_back(SnipReg); + LLVM_DEBUG(dbgs() << "\talso spill snippet " << SnipLI << '\n'); + ++NumSnippets; + } +} + +bool InlineSpiller::isSibling(unsigned Reg) { + return Register::isVirtualRegister(Reg) && VRM.getOriginal(Reg) == Original; +} + +/// It is beneficial to spill to earlier place in the same BB in case +/// as follows: +/// There is an alternative def earlier in the same MBB. +/// Hoist the spill as far as possible in SpillMBB. This can ease +/// register pressure: +/// +/// x = def +/// y = use x +/// s = copy x +/// +/// Hoisting the spill of s to immediately after the def removes the +/// interference between x and y: +/// +/// x = def +/// spill x +/// y = use killed x +/// +/// This hoist only helps when the copy kills its source. +/// +bool InlineSpiller::hoistSpillInsideBB(LiveInterval &SpillLI, + MachineInstr &CopyMI) { + SlotIndex Idx = LIS.getInstructionIndex(CopyMI); +#ifndef NDEBUG + VNInfo *VNI = SpillLI.getVNInfoAt(Idx.getRegSlot()); + assert(VNI && VNI->def == Idx.getRegSlot() && "Not defined by copy"); +#endif + + Register SrcReg = CopyMI.getOperand(1).getReg(); + LiveInterval &SrcLI = LIS.getInterval(SrcReg); + VNInfo *SrcVNI = SrcLI.getVNInfoAt(Idx); + LiveQueryResult SrcQ = SrcLI.Query(Idx); + MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(SrcVNI->def); + if (DefMBB != CopyMI.getParent() || !SrcQ.isKill()) + return false; + + // Conservatively extend the stack slot range to the range of the original + // value. We may be able to do better with stack slot coloring by being more + // careful here. + assert(StackInt && "No stack slot assigned yet."); + LiveInterval &OrigLI = LIS.getInterval(Original); + VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx); + StackInt->MergeValueInAsValue(OrigLI, OrigVNI, StackInt->getValNumInfo(0)); + LLVM_DEBUG(dbgs() << "\tmerged orig valno " << OrigVNI->id << ": " + << *StackInt << '\n'); + + // We are going to spill SrcVNI immediately after its def, so clear out + // any later spills of the same value. + eliminateRedundantSpills(SrcLI, SrcVNI); + + MachineBasicBlock *MBB = LIS.getMBBFromIndex(SrcVNI->def); + MachineBasicBlock::iterator MII; + if (SrcVNI->isPHIDef()) + MII = MBB->SkipPHIsLabelsAndDebug(MBB->begin()); + else { + MachineInstr *DefMI = LIS.getInstructionFromIndex(SrcVNI->def); + assert(DefMI && "Defining instruction disappeared"); + MII = DefMI; + ++MII; + } + // Insert spill without kill flag immediately after def. + TII.storeRegToStackSlot(*MBB, MII, SrcReg, false, StackSlot, + MRI.getRegClass(SrcReg), &TRI); + --MII; // Point to store instruction. + LIS.InsertMachineInstrInMaps(*MII); + LLVM_DEBUG(dbgs() << "\thoisted: " << SrcVNI->def << '\t' << *MII); + + HSpiller.addToMergeableSpills(*MII, StackSlot, Original); + ++NumSpills; + return true; +} + +/// eliminateRedundantSpills - SLI:VNI is known to be on the stack. Remove any +/// redundant spills of this value in SLI.reg and sibling copies. +void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) { + assert(VNI && "Missing value"); + SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList; + WorkList.push_back(std::make_pair(&SLI, VNI)); + assert(StackInt && "No stack slot assigned yet."); + + do { + LiveInterval *LI; + std::tie(LI, VNI) = WorkList.pop_back_val(); + unsigned Reg = LI->reg; + LLVM_DEBUG(dbgs() << "Checking redundant spills for " << VNI->id << '@' + << VNI->def << " in " << *LI << '\n'); + + // Regs to spill are taken care of. + if (isRegToSpill(Reg)) + continue; + + // Add all of VNI's live range to StackInt. + StackInt->MergeValueInAsValue(*LI, VNI, StackInt->getValNumInfo(0)); + LLVM_DEBUG(dbgs() << "Merged to stack int: " << *StackInt << '\n'); + + // Find all spills and copies of VNI. + for (MachineRegisterInfo::use_instr_nodbg_iterator + UI = MRI.use_instr_nodbg_begin(Reg), E = MRI.use_instr_nodbg_end(); + UI != E; ) { + MachineInstr &MI = *UI++; + if (!MI.isCopy() && !MI.mayStore()) + continue; + SlotIndex Idx = LIS.getInstructionIndex(MI); + if (LI->getVNInfoAt(Idx) != VNI) + continue; + + // Follow sibling copies down the dominator tree. + if (unsigned DstReg = isFullCopyOf(MI, Reg)) { + if (isSibling(DstReg)) { + LiveInterval &DstLI = LIS.getInterval(DstReg); + VNInfo *DstVNI = DstLI.getVNInfoAt(Idx.getRegSlot()); + assert(DstVNI && "Missing defined value"); + assert(DstVNI->def == Idx.getRegSlot() && "Wrong copy def slot"); + WorkList.push_back(std::make_pair(&DstLI, DstVNI)); + } + continue; + } + + // Erase spills. + int FI; + if (Reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) { + LLVM_DEBUG(dbgs() << "Redundant spill " << Idx << '\t' << MI); + // eliminateDeadDefs won't normally remove stores, so switch opcode. + MI.setDesc(TII.get(TargetOpcode::KILL)); + DeadDefs.push_back(&MI); + ++NumSpillsRemoved; + if (HSpiller.rmFromMergeableSpills(MI, StackSlot)) + --NumSpills; + } + } + } while (!WorkList.empty()); +} + +//===----------------------------------------------------------------------===// +// Rematerialization +//===----------------------------------------------------------------------===// + +/// markValueUsed - Remember that VNI failed to rematerialize, so its defining +/// instruction cannot be eliminated. See through snippet copies +void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) { + SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList; + WorkList.push_back(std::make_pair(LI, VNI)); + do { + std::tie(LI, VNI) = WorkList.pop_back_val(); + if (!UsedValues.insert(VNI).second) + continue; + + if (VNI->isPHIDef()) { + MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); + for (MachineBasicBlock *P : MBB->predecessors()) { + VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(P)); + if (PVNI) + WorkList.push_back(std::make_pair(LI, PVNI)); + } + continue; + } + + // Follow snippet copies. + MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); + if (!SnippetCopies.count(MI)) + continue; + LiveInterval &SnipLI = LIS.getInterval(MI->getOperand(1).getReg()); + assert(isRegToSpill(SnipLI.reg) && "Unexpected register in copy"); + VNInfo *SnipVNI = SnipLI.getVNInfoAt(VNI->def.getRegSlot(true)); + assert(SnipVNI && "Snippet undefined before copy"); + WorkList.push_back(std::make_pair(&SnipLI, SnipVNI)); + } while (!WorkList.empty()); +} + +bool InlineSpiller::canGuaranteeAssignmentAfterRemat(unsigned VReg, + MachineInstr &MI) { + if (!RestrictStatepointRemat) + return true; + // Here's a quick explanation of the problem we're trying to handle here: + // * There are some pseudo instructions with more vreg uses than there are + // physical registers on the machine. + // * This is normally handled by spilling the vreg, and folding the reload + // into the user instruction. (Thus decreasing the number of used vregs + // until the remainder can be assigned to physregs.) + // * However, since we may try to spill vregs in any order, we can end up + // trying to spill each operand to the instruction, and then rematting it + // instead. When that happens, the new live intervals (for the remats) are + // expected to be trivially assignable (i.e. RS_Done). However, since we + // may have more remats than physregs, we're guaranteed to fail to assign + // one. + // At the moment, we only handle this for STATEPOINTs since they're the only + // psuedo op where we've seen this. If we start seeing other instructions + // with the same problem, we need to revisit this. + return (MI.getOpcode() != TargetOpcode::STATEPOINT); +} + +/// reMaterializeFor - Attempt to rematerialize before MI instead of reloading. +bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, MachineInstr &MI) { + // Analyze instruction + SmallVector<std::pair<MachineInstr *, unsigned>, 8> Ops; + MIBundleOperands::VirtRegInfo RI = + MIBundleOperands(MI).analyzeVirtReg(VirtReg.reg, &Ops); + + if (!RI.Reads) + return false; + + SlotIndex UseIdx = LIS.getInstructionIndex(MI).getRegSlot(true); + VNInfo *ParentVNI = VirtReg.getVNInfoAt(UseIdx.getBaseIndex()); + + if (!ParentVNI) { + LLVM_DEBUG(dbgs() << "\tadding <undef> flags: "); + for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI.getOperand(i); + if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg) + MO.setIsUndef(); + } + LLVM_DEBUG(dbgs() << UseIdx << '\t' << MI); + return true; + } + + if (SnippetCopies.count(&MI)) + return false; + + LiveInterval &OrigLI = LIS.getInterval(Original); + VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx); + LiveRangeEdit::Remat RM(ParentVNI); + RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def); + + if (!Edit->canRematerializeAt(RM, OrigVNI, UseIdx, false)) { + markValueUsed(&VirtReg, ParentVNI); + LLVM_DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << MI); + return false; + } + + // If the instruction also writes VirtReg.reg, it had better not require the + // same register for uses and defs. + if (RI.Tied) { + markValueUsed(&VirtReg, ParentVNI); + LLVM_DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << MI); + return false; + } + + // Before rematerializing into a register for a single instruction, try to + // fold a load into the instruction. That avoids allocating a new register. + if (RM.OrigMI->canFoldAsLoad() && + foldMemoryOperand(Ops, RM.OrigMI)) { + Edit->markRematerialized(RM.ParentVNI); + ++NumFoldedLoads; + return true; + } + + // If we can't guarantee that we'll be able to actually assign the new vreg, + // we can't remat. + if (!canGuaranteeAssignmentAfterRemat(VirtReg.reg, MI)) { + markValueUsed(&VirtReg, ParentVNI); + LLVM_DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << MI); + return false; + } + + // Allocate a new register for the remat. + unsigned NewVReg = Edit->createFrom(Original); + + // Finally we can rematerialize OrigMI before MI. + SlotIndex DefIdx = + Edit->rematerializeAt(*MI.getParent(), MI, NewVReg, RM, TRI); + + // We take the DebugLoc from MI, since OrigMI may be attributed to a + // different source location. + auto *NewMI = LIS.getInstructionFromIndex(DefIdx); + NewMI->setDebugLoc(MI.getDebugLoc()); + + (void)DefIdx; + LLVM_DEBUG(dbgs() << "\tremat: " << DefIdx << '\t' + << *LIS.getInstructionFromIndex(DefIdx)); + + // Replace operands + for (const auto &OpPair : Ops) { + MachineOperand &MO = OpPair.first->getOperand(OpPair.second); + if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg) { + MO.setReg(NewVReg); + MO.setIsKill(); + } + } + LLVM_DEBUG(dbgs() << "\t " << UseIdx << '\t' << MI << '\n'); + + ++NumRemats; + return true; +} + +/// reMaterializeAll - Try to rematerialize as many uses as possible, +/// and trim the live ranges after. +void InlineSpiller::reMaterializeAll() { + if (!Edit->anyRematerializable(AA)) + return; + + UsedValues.clear(); + + // Try to remat before all uses of snippets. + bool anyRemat = false; + for (unsigned Reg : RegsToSpill) { + LiveInterval &LI = LIS.getInterval(Reg); + for (MachineRegisterInfo::reg_bundle_iterator + RegI = MRI.reg_bundle_begin(Reg), E = MRI.reg_bundle_end(); + RegI != E; ) { + MachineInstr &MI = *RegI++; + + // Debug values are not allowed to affect codegen. + if (MI.isDebugValue()) + continue; + + assert(!MI.isDebugInstr() && "Did not expect to find a use in debug " + "instruction that isn't a DBG_VALUE"); + + anyRemat |= reMaterializeFor(LI, MI); + } + } + if (!anyRemat) + return; + + // Remove any values that were completely rematted. + for (unsigned Reg : RegsToSpill) { + LiveInterval &LI = LIS.getInterval(Reg); + for (LiveInterval::vni_iterator I = LI.vni_begin(), E = LI.vni_end(); + I != E; ++I) { + VNInfo *VNI = *I; + if (VNI->isUnused() || VNI->isPHIDef() || UsedValues.count(VNI)) + continue; + MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); + MI->addRegisterDead(Reg, &TRI); + if (!MI->allDefsAreDead()) + continue; + LLVM_DEBUG(dbgs() << "All defs dead: " << *MI); + DeadDefs.push_back(MI); + } + } + + // Eliminate dead code after remat. Note that some snippet copies may be + // deleted here. + if (DeadDefs.empty()) + return; + LLVM_DEBUG(dbgs() << "Remat created " << DeadDefs.size() << " dead defs.\n"); + Edit->eliminateDeadDefs(DeadDefs, RegsToSpill, AA); + + // LiveRangeEdit::eliminateDeadDef is used to remove dead define instructions + // after rematerialization. To remove a VNI for a vreg from its LiveInterval, + // LiveIntervals::removeVRegDefAt is used. However, after non-PHI VNIs are all + // removed, PHI VNI are still left in the LiveInterval. + // So to get rid of unused reg, we need to check whether it has non-dbg + // reference instead of whether it has non-empty interval. + unsigned ResultPos = 0; + for (unsigned Reg : RegsToSpill) { + if (MRI.reg_nodbg_empty(Reg)) { + Edit->eraseVirtReg(Reg); + continue; + } + + assert(LIS.hasInterval(Reg) && + (!LIS.getInterval(Reg).empty() || !MRI.reg_nodbg_empty(Reg)) && + "Empty and not used live-range?!"); + + RegsToSpill[ResultPos++] = Reg; + } + RegsToSpill.erase(RegsToSpill.begin() + ResultPos, RegsToSpill.end()); + LLVM_DEBUG(dbgs() << RegsToSpill.size() + << " registers to spill after remat.\n"); +} + +//===----------------------------------------------------------------------===// +// Spilling +//===----------------------------------------------------------------------===// + +/// If MI is a load or store of StackSlot, it can be removed. +bool InlineSpiller::coalesceStackAccess(MachineInstr *MI, unsigned Reg) { + int FI = 0; + unsigned InstrReg = TII.isLoadFromStackSlot(*MI, FI); + bool IsLoad = InstrReg; + if (!IsLoad) + InstrReg = TII.isStoreToStackSlot(*MI, FI); + + // We have a stack access. Is it the right register and slot? + if (InstrReg != Reg || FI != StackSlot) + return false; + + if (!IsLoad) + HSpiller.rmFromMergeableSpills(*MI, StackSlot); + + LLVM_DEBUG(dbgs() << "Coalescing stack access: " << *MI); + LIS.RemoveMachineInstrFromMaps(*MI); + MI->eraseFromParent(); + + if (IsLoad) { + ++NumReloadsRemoved; + --NumReloads; + } else { + ++NumSpillsRemoved; + --NumSpills; + } + + return true; +} + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +LLVM_DUMP_METHOD +// Dump the range of instructions from B to E with their slot indexes. +static void dumpMachineInstrRangeWithSlotIndex(MachineBasicBlock::iterator B, + MachineBasicBlock::iterator E, + LiveIntervals const &LIS, + const char *const header, + unsigned VReg =0) { + char NextLine = '\n'; + char SlotIndent = '\t'; + + if (std::next(B) == E) { + NextLine = ' '; + SlotIndent = ' '; + } + + dbgs() << '\t' << header << ": " << NextLine; + + for (MachineBasicBlock::iterator I = B; I != E; ++I) { + SlotIndex Idx = LIS.getInstructionIndex(*I).getRegSlot(); + + // If a register was passed in and this instruction has it as a + // destination that is marked as an early clobber, print the + // early-clobber slot index. + if (VReg) { + MachineOperand *MO = I->findRegisterDefOperand(VReg); + if (MO && MO->isEarlyClobber()) + Idx = Idx.getRegSlot(true); + } + + dbgs() << SlotIndent << Idx << '\t' << *I; + } +} +#endif + +/// foldMemoryOperand - Try folding stack slot references in Ops into their +/// instructions. +/// +/// @param Ops Operand indices from analyzeVirtReg(). +/// @param LoadMI Load instruction to use instead of stack slot when non-null. +/// @return True on success. +bool InlineSpiller:: +foldMemoryOperand(ArrayRef<std::pair<MachineInstr *, unsigned>> Ops, + MachineInstr *LoadMI) { + if (Ops.empty()) + return false; + // Don't attempt folding in bundles. + MachineInstr *MI = Ops.front().first; + if (Ops.back().first != MI || MI->isBundled()) + return false; + + bool WasCopy = MI->isCopy(); + unsigned ImpReg = 0; + + // Spill subregs if the target allows it. + // We always want to spill subregs for stackmap/patchpoint pseudos. + bool SpillSubRegs = TII.isSubregFoldable() || + MI->getOpcode() == TargetOpcode::STATEPOINT || + MI->getOpcode() == TargetOpcode::PATCHPOINT || + MI->getOpcode() == TargetOpcode::STACKMAP; + + // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied + // operands. + SmallVector<unsigned, 8> FoldOps; + for (const auto &OpPair : Ops) { + unsigned Idx = OpPair.second; + assert(MI == OpPair.first && "Instruction conflict during operand folding"); + MachineOperand &MO = MI->getOperand(Idx); + if (MO.isImplicit()) { + ImpReg = MO.getReg(); + continue; + } + + if (!SpillSubRegs && MO.getSubReg()) + return false; + // We cannot fold a load instruction into a def. + if (LoadMI && MO.isDef()) + return false; + // Tied use operands should not be passed to foldMemoryOperand. + if (!MI->isRegTiedToDefOperand(Idx)) + FoldOps.push_back(Idx); + } + + // If we only have implicit uses, we won't be able to fold that. + // Moreover, TargetInstrInfo::foldMemoryOperand will assert if we try! + if (FoldOps.empty()) + return false; + + MachineInstrSpan MIS(MI, MI->getParent()); + + MachineInstr *FoldMI = + LoadMI ? TII.foldMemoryOperand(*MI, FoldOps, *LoadMI, &LIS) + : TII.foldMemoryOperand(*MI, FoldOps, StackSlot, &LIS, &VRM); + if (!FoldMI) + return false; + + // Remove LIS for any dead defs in the original MI not in FoldMI. + for (MIBundleOperands MO(*MI); MO.isValid(); ++MO) { + if (!MO->isReg()) + continue; + Register Reg = MO->getReg(); + if (!Reg || Register::isVirtualRegister(Reg) || MRI.isReserved(Reg)) { + continue; + } + // Skip non-Defs, including undef uses and internal reads. + if (MO->isUse()) + continue; + MIBundleOperands::PhysRegInfo RI = + MIBundleOperands(*FoldMI).analyzePhysReg(Reg, &TRI); + if (RI.FullyDefined) + continue; + // FoldMI does not define this physreg. Remove the LI segment. + assert(MO->isDead() && "Cannot fold physreg def"); + SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot(); + LIS.removePhysRegDefAt(Reg, Idx); + } + + int FI; + if (TII.isStoreToStackSlot(*MI, FI) && + HSpiller.rmFromMergeableSpills(*MI, FI)) + --NumSpills; + LIS.ReplaceMachineInstrInMaps(*MI, *FoldMI); + if (MI->isCall()) + MI->getMF()->moveCallSiteInfo(MI, FoldMI); + MI->eraseFromParent(); + + // Insert any new instructions other than FoldMI into the LIS maps. + assert(!MIS.empty() && "Unexpected empty span of instructions!"); + for (MachineInstr &MI : MIS) + if (&MI != FoldMI) + LIS.InsertMachineInstrInMaps(MI); + + // TII.foldMemoryOperand may have left some implicit operands on the + // instruction. Strip them. + if (ImpReg) + for (unsigned i = FoldMI->getNumOperands(); i; --i) { + MachineOperand &MO = FoldMI->getOperand(i - 1); + if (!MO.isReg() || !MO.isImplicit()) + break; + if (MO.getReg() == ImpReg) + FoldMI->RemoveOperand(i - 1); + } + + LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MIS.end(), LIS, + "folded")); + + if (!WasCopy) + ++NumFolded; + else if (Ops.front().second == 0) { + ++NumSpills; + HSpiller.addToMergeableSpills(*FoldMI, StackSlot, Original); + } else + ++NumReloads; + return true; +} + +void InlineSpiller::insertReload(unsigned NewVReg, + SlotIndex Idx, + MachineBasicBlock::iterator MI) { + MachineBasicBlock &MBB = *MI->getParent(); + + MachineInstrSpan MIS(MI, &MBB); + TII.loadRegFromStackSlot(MBB, MI, NewVReg, StackSlot, + MRI.getRegClass(NewVReg), &TRI); + + LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MI); + + LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MI, LIS, "reload", + NewVReg)); + ++NumReloads; +} + +/// Check if \p Def fully defines a VReg with an undefined value. +/// If that's the case, that means the value of VReg is actually +/// not relevant. +static bool isFullUndefDef(const MachineInstr &Def) { + if (!Def.isImplicitDef()) + return false; + assert(Def.getNumOperands() == 1 && + "Implicit def with more than one definition"); + // We can say that the VReg defined by Def is undef, only if it is + // fully defined by Def. Otherwise, some of the lanes may not be + // undef and the value of the VReg matters. + return !Def.getOperand(0).getSubReg(); +} + +/// insertSpill - Insert a spill of NewVReg after MI. +void InlineSpiller::insertSpill(unsigned NewVReg, bool isKill, + MachineBasicBlock::iterator MI) { + MachineBasicBlock &MBB = *MI->getParent(); + + MachineInstrSpan MIS(MI, &MBB); + bool IsRealSpill = true; + if (isFullUndefDef(*MI)) { + // Don't spill undef value. + // Anything works for undef, in particular keeping the memory + // uninitialized is a viable option and it saves code size and + // run time. + BuildMI(MBB, std::next(MI), MI->getDebugLoc(), TII.get(TargetOpcode::KILL)) + .addReg(NewVReg, getKillRegState(isKill)); + IsRealSpill = false; + } else + TII.storeRegToStackSlot(MBB, std::next(MI), NewVReg, isKill, StackSlot, + MRI.getRegClass(NewVReg), &TRI); + + LIS.InsertMachineInstrRangeInMaps(std::next(MI), MIS.end()); + + LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(std::next(MI), MIS.end(), LIS, + "spill")); + ++NumSpills; + if (IsRealSpill) + HSpiller.addToMergeableSpills(*std::next(MI), StackSlot, Original); +} + +/// spillAroundUses - insert spill code around each use of Reg. +void InlineSpiller::spillAroundUses(unsigned Reg) { + LLVM_DEBUG(dbgs() << "spillAroundUses " << printReg(Reg) << '\n'); + LiveInterval &OldLI = LIS.getInterval(Reg); + + // Iterate over instructions using Reg. + for (MachineRegisterInfo::reg_bundle_iterator + RegI = MRI.reg_bundle_begin(Reg), E = MRI.reg_bundle_end(); + RegI != E; ) { + MachineInstr *MI = &*(RegI++); + + // Debug values are not allowed to affect codegen. + if (MI->isDebugValue()) { + // Modify DBG_VALUE now that the value is in a spill slot. + MachineBasicBlock *MBB = MI->getParent(); + LLVM_DEBUG(dbgs() << "Modifying debug info due to spill:\t" << *MI); + buildDbgValueForSpill(*MBB, MI, *MI, StackSlot); + MBB->erase(MI); + continue; + } + + assert(!MI->isDebugInstr() && "Did not expect to find a use in debug " + "instruction that isn't a DBG_VALUE"); + + // Ignore copies to/from snippets. We'll delete them. + if (SnippetCopies.count(MI)) + continue; + + // Stack slot accesses may coalesce away. + if (coalesceStackAccess(MI, Reg)) + continue; + + // Analyze instruction. + SmallVector<std::pair<MachineInstr*, unsigned>, 8> Ops; + MIBundleOperands::VirtRegInfo RI = + MIBundleOperands(*MI).analyzeVirtReg(Reg, &Ops); + + // Find the slot index where this instruction reads and writes OldLI. + // This is usually the def slot, except for tied early clobbers. + SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot(); + if (VNInfo *VNI = OldLI.getVNInfoAt(Idx.getRegSlot(true))) + if (SlotIndex::isSameInstr(Idx, VNI->def)) + Idx = VNI->def; + + // Check for a sibling copy. + unsigned SibReg = isFullCopyOf(*MI, Reg); + if (SibReg && isSibling(SibReg)) { + // This may actually be a copy between snippets. + if (isRegToSpill(SibReg)) { + LLVM_DEBUG(dbgs() << "Found new snippet copy: " << *MI); + SnippetCopies.insert(MI); + continue; + } + if (RI.Writes) { + if (hoistSpillInsideBB(OldLI, *MI)) { + // This COPY is now dead, the value is already in the stack slot. + MI->getOperand(0).setIsDead(); + DeadDefs.push_back(MI); + continue; + } + } else { + // This is a reload for a sib-reg copy. Drop spills downstream. + LiveInterval &SibLI = LIS.getInterval(SibReg); + eliminateRedundantSpills(SibLI, SibLI.getVNInfoAt(Idx)); + // The COPY will fold to a reload below. + } + } + + // Attempt to fold memory ops. + if (foldMemoryOperand(Ops)) + continue; + + // Create a new virtual register for spill/fill. + // FIXME: Infer regclass from instruction alone. + unsigned NewVReg = Edit->createFrom(Reg); + + if (RI.Reads) + insertReload(NewVReg, Idx, MI); + + // Rewrite instruction operands. + bool hasLiveDef = false; + for (const auto &OpPair : Ops) { + MachineOperand &MO = OpPair.first->getOperand(OpPair.second); + MO.setReg(NewVReg); + if (MO.isUse()) { + if (!OpPair.first->isRegTiedToDefOperand(OpPair.second)) + MO.setIsKill(); + } else { + if (!MO.isDead()) + hasLiveDef = true; + } + } + LLVM_DEBUG(dbgs() << "\trewrite: " << Idx << '\t' << *MI << '\n'); + + // FIXME: Use a second vreg if instruction has no tied ops. + if (RI.Writes) + if (hasLiveDef) + insertSpill(NewVReg, true, MI); + } +} + +/// spillAll - Spill all registers remaining after rematerialization. +void InlineSpiller::spillAll() { + // Update LiveStacks now that we are committed to spilling. + if (StackSlot == VirtRegMap::NO_STACK_SLOT) { + StackSlot = VRM.assignVirt2StackSlot(Original); + StackInt = &LSS.getOrCreateInterval(StackSlot, MRI.getRegClass(Original)); + StackInt->getNextValue(SlotIndex(), LSS.getVNInfoAllocator()); + } else + StackInt = &LSS.getInterval(StackSlot); + + if (Original != Edit->getReg()) + VRM.assignVirt2StackSlot(Edit->getReg(), StackSlot); + + assert(StackInt->getNumValNums() == 1 && "Bad stack interval values"); + for (unsigned Reg : RegsToSpill) + StackInt->MergeSegmentsInAsValue(LIS.getInterval(Reg), + StackInt->getValNumInfo(0)); + LLVM_DEBUG(dbgs() << "Merged spilled regs: " << *StackInt << '\n'); + + // Spill around uses of all RegsToSpill. + for (unsigned Reg : RegsToSpill) + spillAroundUses(Reg); + + // Hoisted spills may cause dead code. + if (!DeadDefs.empty()) { + LLVM_DEBUG(dbgs() << "Eliminating " << DeadDefs.size() << " dead defs\n"); + Edit->eliminateDeadDefs(DeadDefs, RegsToSpill, AA); + } + + // Finally delete the SnippetCopies. + for (unsigned Reg : RegsToSpill) { + for (MachineRegisterInfo::reg_instr_iterator + RI = MRI.reg_instr_begin(Reg), E = MRI.reg_instr_end(); + RI != E; ) { + MachineInstr &MI = *(RI++); + assert(SnippetCopies.count(&MI) && "Remaining use wasn't a snippet copy"); + // FIXME: Do this with a LiveRangeEdit callback. + LIS.RemoveMachineInstrFromMaps(MI); + MI.eraseFromParent(); + } + } + + // Delete all spilled registers. + for (unsigned Reg : RegsToSpill) + Edit->eraseVirtReg(Reg); +} + +void InlineSpiller::spill(LiveRangeEdit &edit) { + ++NumSpilledRanges; + Edit = &edit; + assert(!Register::isStackSlot(edit.getReg()) && + "Trying to spill a stack slot."); + // Share a stack slot among all descendants of Original. + Original = VRM.getOriginal(edit.getReg()); + StackSlot = VRM.getStackSlot(Original); + StackInt = nullptr; + + LLVM_DEBUG(dbgs() << "Inline spilling " + << TRI.getRegClassName(MRI.getRegClass(edit.getReg())) + << ':' << edit.getParent() << "\nFrom original " + << printReg(Original) << '\n'); + assert(edit.getParent().isSpillable() && + "Attempting to spill already spilled value."); + assert(DeadDefs.empty() && "Previous spill didn't remove dead defs"); + + collectRegsToSpill(); + reMaterializeAll(); + + // Remat may handle everything. + if (!RegsToSpill.empty()) + spillAll(); + + Edit->calculateRegClassAndHint(MF, Loops, MBFI); +} + +/// Optimizations after all the reg selections and spills are done. +void InlineSpiller::postOptimization() { HSpiller.hoistAllSpills(); } + +/// When a spill is inserted, add the spill to MergeableSpills map. +void HoistSpillHelper::addToMergeableSpills(MachineInstr &Spill, int StackSlot, + unsigned Original) { + BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator(); + LiveInterval &OrigLI = LIS.getInterval(Original); + // save a copy of LiveInterval in StackSlotToOrigLI because the original + // LiveInterval may be cleared after all its references are spilled. + if (StackSlotToOrigLI.find(StackSlot) == StackSlotToOrigLI.end()) { + auto LI = std::make_unique<LiveInterval>(OrigLI.reg, OrigLI.weight); + LI->assign(OrigLI, Allocator); + StackSlotToOrigLI[StackSlot] = std::move(LI); + } + SlotIndex Idx = LIS.getInstructionIndex(Spill); + VNInfo *OrigVNI = StackSlotToOrigLI[StackSlot]->getVNInfoAt(Idx.getRegSlot()); + std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI); + MergeableSpills[MIdx].insert(&Spill); +} + +/// When a spill is removed, remove the spill from MergeableSpills map. +/// Return true if the spill is removed successfully. +bool HoistSpillHelper::rmFromMergeableSpills(MachineInstr &Spill, + int StackSlot) { + auto It = StackSlotToOrigLI.find(StackSlot); + if (It == StackSlotToOrigLI.end()) + return false; + SlotIndex Idx = LIS.getInstructionIndex(Spill); + VNInfo *OrigVNI = It->second->getVNInfoAt(Idx.getRegSlot()); + std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI); + return MergeableSpills[MIdx].erase(&Spill); +} + +/// Check BB to see if it is a possible target BB to place a hoisted spill, +/// i.e., there should be a living sibling of OrigReg at the insert point. +bool HoistSpillHelper::isSpillCandBB(LiveInterval &OrigLI, VNInfo &OrigVNI, + MachineBasicBlock &BB, unsigned &LiveReg) { + SlotIndex Idx; + unsigned OrigReg = OrigLI.reg; + MachineBasicBlock::iterator MI = IPA.getLastInsertPointIter(OrigLI, BB); + if (MI != BB.end()) + Idx = LIS.getInstructionIndex(*MI); + else + Idx = LIS.getMBBEndIdx(&BB).getPrevSlot(); + SmallSetVector<unsigned, 16> &Siblings = Virt2SiblingsMap[OrigReg]; + assert(OrigLI.getVNInfoAt(Idx) == &OrigVNI && "Unexpected VNI"); + + for (auto const SibReg : Siblings) { + LiveInterval &LI = LIS.getInterval(SibReg); + VNInfo *VNI = LI.getVNInfoAt(Idx); + if (VNI) { + LiveReg = SibReg; + return true; + } + } + return false; +} + +/// Remove redundant spills in the same BB. Save those redundant spills in +/// SpillsToRm, and save the spill to keep and its BB in SpillBBToSpill map. +void HoistSpillHelper::rmRedundantSpills( + SmallPtrSet<MachineInstr *, 16> &Spills, + SmallVectorImpl<MachineInstr *> &SpillsToRm, + DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill) { + // For each spill saw, check SpillBBToSpill[] and see if its BB already has + // another spill inside. If a BB contains more than one spill, only keep the + // earlier spill with smaller SlotIndex. + for (const auto CurrentSpill : Spills) { + MachineBasicBlock *Block = CurrentSpill->getParent(); + MachineDomTreeNode *Node = MDT.getBase().getNode(Block); + MachineInstr *PrevSpill = SpillBBToSpill[Node]; + if (PrevSpill) { + SlotIndex PIdx = LIS.getInstructionIndex(*PrevSpill); + SlotIndex CIdx = LIS.getInstructionIndex(*CurrentSpill); + MachineInstr *SpillToRm = (CIdx > PIdx) ? CurrentSpill : PrevSpill; + MachineInstr *SpillToKeep = (CIdx > PIdx) ? PrevSpill : CurrentSpill; + SpillsToRm.push_back(SpillToRm); + SpillBBToSpill[MDT.getBase().getNode(Block)] = SpillToKeep; + } else { + SpillBBToSpill[MDT.getBase().getNode(Block)] = CurrentSpill; + } + } + for (const auto SpillToRm : SpillsToRm) + Spills.erase(SpillToRm); +} + +/// Starting from \p Root find a top-down traversal order of the dominator +/// tree to visit all basic blocks containing the elements of \p Spills. +/// Redundant spills will be found and put into \p SpillsToRm at the same +/// time. \p SpillBBToSpill will be populated as part of the process and +/// maps a basic block to the first store occurring in the basic block. +/// \post SpillsToRm.union(Spills\@post) == Spills\@pre +void HoistSpillHelper::getVisitOrders( + MachineBasicBlock *Root, SmallPtrSet<MachineInstr *, 16> &Spills, + SmallVectorImpl<MachineDomTreeNode *> &Orders, + SmallVectorImpl<MachineInstr *> &SpillsToRm, + DenseMap<MachineDomTreeNode *, unsigned> &SpillsToKeep, + DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill) { + // The set contains all the possible BB nodes to which we may hoist + // original spills. + SmallPtrSet<MachineDomTreeNode *, 8> WorkSet; + // Save the BB nodes on the path from the first BB node containing + // non-redundant spill to the Root node. + SmallPtrSet<MachineDomTreeNode *, 8> NodesOnPath; + // All the spills to be hoisted must originate from a single def instruction + // to the OrigReg. It means the def instruction should dominate all the spills + // to be hoisted. We choose the BB where the def instruction is located as + // the Root. + MachineDomTreeNode *RootIDomNode = MDT[Root]->getIDom(); + // For every node on the dominator tree with spill, walk up on the dominator + // tree towards the Root node until it is reached. If there is other node + // containing spill in the middle of the path, the previous spill saw will + // be redundant and the node containing it will be removed. All the nodes on + // the path starting from the first node with non-redundant spill to the Root + // node will be added to the WorkSet, which will contain all the possible + // locations where spills may be hoisted to after the loop below is done. + for (const auto Spill : Spills) { + MachineBasicBlock *Block = Spill->getParent(); + MachineDomTreeNode *Node = MDT[Block]; + MachineInstr *SpillToRm = nullptr; + while (Node != RootIDomNode) { + // If Node dominates Block, and it already contains a spill, the spill in + // Block will be redundant. + if (Node != MDT[Block] && SpillBBToSpill[Node]) { + SpillToRm = SpillBBToSpill[MDT[Block]]; + break; + /// If we see the Node already in WorkSet, the path from the Node to + /// the Root node must already be traversed by another spill. + /// Then no need to repeat. + } else if (WorkSet.count(Node)) { + break; + } else { + NodesOnPath.insert(Node); + } + Node = Node->getIDom(); + } + if (SpillToRm) { + SpillsToRm.push_back(SpillToRm); + } else { + // Add a BB containing the original spills to SpillsToKeep -- i.e., + // set the initial status before hoisting start. The value of BBs + // containing original spills is set to 0, in order to descriminate + // with BBs containing hoisted spills which will be inserted to + // SpillsToKeep later during hoisting. + SpillsToKeep[MDT[Block]] = 0; + WorkSet.insert(NodesOnPath.begin(), NodesOnPath.end()); + } + NodesOnPath.clear(); + } + + // Sort the nodes in WorkSet in top-down order and save the nodes + // in Orders. Orders will be used for hoisting in runHoistSpills. + unsigned idx = 0; + Orders.push_back(MDT.getBase().getNode(Root)); + do { + MachineDomTreeNode *Node = Orders[idx++]; + const std::vector<MachineDomTreeNode *> &Children = Node->getChildren(); + unsigned NumChildren = Children.size(); + for (unsigned i = 0; i != NumChildren; ++i) { + MachineDomTreeNode *Child = Children[i]; + if (WorkSet.count(Child)) + Orders.push_back(Child); + } + } while (idx != Orders.size()); + assert(Orders.size() == WorkSet.size() && + "Orders have different size with WorkSet"); + +#ifndef NDEBUG + LLVM_DEBUG(dbgs() << "Orders size is " << Orders.size() << "\n"); + SmallVector<MachineDomTreeNode *, 32>::reverse_iterator RIt = Orders.rbegin(); + for (; RIt != Orders.rend(); RIt++) + LLVM_DEBUG(dbgs() << "BB" << (*RIt)->getBlock()->getNumber() << ","); + LLVM_DEBUG(dbgs() << "\n"); +#endif +} + +/// Try to hoist spills according to BB hotness. The spills to removed will +/// be saved in \p SpillsToRm. The spills to be inserted will be saved in +/// \p SpillsToIns. +void HoistSpillHelper::runHoistSpills( + LiveInterval &OrigLI, VNInfo &OrigVNI, + SmallPtrSet<MachineInstr *, 16> &Spills, + SmallVectorImpl<MachineInstr *> &SpillsToRm, + DenseMap<MachineBasicBlock *, unsigned> &SpillsToIns) { + // Visit order of dominator tree nodes. + SmallVector<MachineDomTreeNode *, 32> Orders; + // SpillsToKeep contains all the nodes where spills are to be inserted + // during hoisting. If the spill to be inserted is an original spill + // (not a hoisted one), the value of the map entry is 0. If the spill + // is a hoisted spill, the value of the map entry is the VReg to be used + // as the source of the spill. + DenseMap<MachineDomTreeNode *, unsigned> SpillsToKeep; + // Map from BB to the first spill inside of it. + DenseMap<MachineDomTreeNode *, MachineInstr *> SpillBBToSpill; + + rmRedundantSpills(Spills, SpillsToRm, SpillBBToSpill); + + MachineBasicBlock *Root = LIS.getMBBFromIndex(OrigVNI.def); + getVisitOrders(Root, Spills, Orders, SpillsToRm, SpillsToKeep, + SpillBBToSpill); + + // SpillsInSubTreeMap keeps the map from a dom tree node to a pair of + // nodes set and the cost of all the spills inside those nodes. + // The nodes set are the locations where spills are to be inserted + // in the subtree of current node. + using NodesCostPair = + std::pair<SmallPtrSet<MachineDomTreeNode *, 16>, BlockFrequency>; + DenseMap<MachineDomTreeNode *, NodesCostPair> SpillsInSubTreeMap; + + // Iterate Orders set in reverse order, which will be a bottom-up order + // in the dominator tree. Once we visit a dom tree node, we know its + // children have already been visited and the spill locations in the + // subtrees of all the children have been determined. + SmallVector<MachineDomTreeNode *, 32>::reverse_iterator RIt = Orders.rbegin(); + for (; RIt != Orders.rend(); RIt++) { + MachineBasicBlock *Block = (*RIt)->getBlock(); + + // If Block contains an original spill, simply continue. + if (SpillsToKeep.find(*RIt) != SpillsToKeep.end() && !SpillsToKeep[*RIt]) { + SpillsInSubTreeMap[*RIt].first.insert(*RIt); + // SpillsInSubTreeMap[*RIt].second contains the cost of spill. + SpillsInSubTreeMap[*RIt].second = MBFI.getBlockFreq(Block); + continue; + } + + // Collect spills in subtree of current node (*RIt) to + // SpillsInSubTreeMap[*RIt].first. + const std::vector<MachineDomTreeNode *> &Children = (*RIt)->getChildren(); + unsigned NumChildren = Children.size(); + for (unsigned i = 0; i != NumChildren; ++i) { + MachineDomTreeNode *Child = Children[i]; + if (SpillsInSubTreeMap.find(Child) == SpillsInSubTreeMap.end()) + continue; + // The stmt "SpillsInSubTree = SpillsInSubTreeMap[*RIt].first" below + // should be placed before getting the begin and end iterators of + // SpillsInSubTreeMap[Child].first, or else the iterators may be + // invalidated when SpillsInSubTreeMap[*RIt] is seen the first time + // and the map grows and then the original buckets in the map are moved. + SmallPtrSet<MachineDomTreeNode *, 16> &SpillsInSubTree = + SpillsInSubTreeMap[*RIt].first; + BlockFrequency &SubTreeCost = SpillsInSubTreeMap[*RIt].second; + SubTreeCost += SpillsInSubTreeMap[Child].second; + auto BI = SpillsInSubTreeMap[Child].first.begin(); + auto EI = SpillsInSubTreeMap[Child].first.end(); + SpillsInSubTree.insert(BI, EI); + SpillsInSubTreeMap.erase(Child); + } + + SmallPtrSet<MachineDomTreeNode *, 16> &SpillsInSubTree = + SpillsInSubTreeMap[*RIt].first; + BlockFrequency &SubTreeCost = SpillsInSubTreeMap[*RIt].second; + // No spills in subtree, simply continue. + if (SpillsInSubTree.empty()) + continue; + + // Check whether Block is a possible candidate to insert spill. + unsigned LiveReg = 0; + if (!isSpillCandBB(OrigLI, OrigVNI, *Block, LiveReg)) + continue; + + // If there are multiple spills that could be merged, bias a little + // to hoist the spill. + BranchProbability MarginProb = (SpillsInSubTree.size() > 1) + ? BranchProbability(9, 10) + : BranchProbability(1, 1); + if (SubTreeCost > MBFI.getBlockFreq(Block) * MarginProb) { + // Hoist: Move spills to current Block. + for (const auto SpillBB : SpillsInSubTree) { + // When SpillBB is a BB contains original spill, insert the spill + // to SpillsToRm. + if (SpillsToKeep.find(SpillBB) != SpillsToKeep.end() && + !SpillsToKeep[SpillBB]) { + MachineInstr *SpillToRm = SpillBBToSpill[SpillBB]; + SpillsToRm.push_back(SpillToRm); + } + // SpillBB will not contain spill anymore, remove it from SpillsToKeep. + SpillsToKeep.erase(SpillBB); + } + // Current Block is the BB containing the new hoisted spill. Add it to + // SpillsToKeep. LiveReg is the source of the new spill. + SpillsToKeep[*RIt] = LiveReg; + LLVM_DEBUG({ + dbgs() << "spills in BB: "; + for (const auto Rspill : SpillsInSubTree) + dbgs() << Rspill->getBlock()->getNumber() << " "; + dbgs() << "were promoted to BB" << (*RIt)->getBlock()->getNumber() + << "\n"; + }); + SpillsInSubTree.clear(); + SpillsInSubTree.insert(*RIt); + SubTreeCost = MBFI.getBlockFreq(Block); + } + } + // For spills in SpillsToKeep with LiveReg set (i.e., not original spill), + // save them to SpillsToIns. + for (const auto Ent : SpillsToKeep) { + if (Ent.second) + SpillsToIns[Ent.first->getBlock()] = Ent.second; + } +} + +/// For spills with equal values, remove redundant spills and hoist those left +/// to less hot spots. +/// +/// Spills with equal values will be collected into the same set in +/// MergeableSpills when spill is inserted. These equal spills are originated +/// from the same defining instruction and are dominated by the instruction. +/// Before hoisting all the equal spills, redundant spills inside in the same +/// BB are first marked to be deleted. Then starting from the spills left, walk +/// up on the dominator tree towards the Root node where the define instruction +/// is located, mark the dominated spills to be deleted along the way and +/// collect the BB nodes on the path from non-dominated spills to the define +/// instruction into a WorkSet. The nodes in WorkSet are the candidate places +/// where we are considering to hoist the spills. We iterate the WorkSet in +/// bottom-up order, and for each node, we will decide whether to hoist spills +/// inside its subtree to that node. In this way, we can get benefit locally +/// even if hoisting all the equal spills to one cold place is impossible. +void HoistSpillHelper::hoistAllSpills() { + SmallVector<unsigned, 4> NewVRegs; + LiveRangeEdit Edit(nullptr, NewVRegs, MF, LIS, &VRM, this); + + for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) { + unsigned Reg = Register::index2VirtReg(i); + unsigned Original = VRM.getPreSplitReg(Reg); + if (!MRI.def_empty(Reg)) + Virt2SiblingsMap[Original].insert(Reg); + } + + // Each entry in MergeableSpills contains a spill set with equal values. + for (auto &Ent : MergeableSpills) { + int Slot = Ent.first.first; + LiveInterval &OrigLI = *StackSlotToOrigLI[Slot]; + VNInfo *OrigVNI = Ent.first.second; + SmallPtrSet<MachineInstr *, 16> &EqValSpills = Ent.second; + if (Ent.second.empty()) + continue; + + LLVM_DEBUG({ + dbgs() << "\nFor Slot" << Slot << " and VN" << OrigVNI->id << ":\n" + << "Equal spills in BB: "; + for (const auto spill : EqValSpills) + dbgs() << spill->getParent()->getNumber() << " "; + dbgs() << "\n"; + }); + + // SpillsToRm is the spill set to be removed from EqValSpills. + SmallVector<MachineInstr *, 16> SpillsToRm; + // SpillsToIns is the spill set to be newly inserted after hoisting. + DenseMap<MachineBasicBlock *, unsigned> SpillsToIns; + + runHoistSpills(OrigLI, *OrigVNI, EqValSpills, SpillsToRm, SpillsToIns); + + LLVM_DEBUG({ + dbgs() << "Finally inserted spills in BB: "; + for (const auto Ispill : SpillsToIns) + dbgs() << Ispill.first->getNumber() << " "; + dbgs() << "\nFinally removed spills in BB: "; + for (const auto Rspill : SpillsToRm) + dbgs() << Rspill->getParent()->getNumber() << " "; + dbgs() << "\n"; + }); + + // Stack live range update. + LiveInterval &StackIntvl = LSS.getInterval(Slot); + if (!SpillsToIns.empty() || !SpillsToRm.empty()) + StackIntvl.MergeValueInAsValue(OrigLI, OrigVNI, + StackIntvl.getValNumInfo(0)); + + // Insert hoisted spills. + for (auto const Insert : SpillsToIns) { + MachineBasicBlock *BB = Insert.first; + unsigned LiveReg = Insert.second; + MachineBasicBlock::iterator MI = IPA.getLastInsertPointIter(OrigLI, *BB); + TII.storeRegToStackSlot(*BB, MI, LiveReg, false, Slot, + MRI.getRegClass(LiveReg), &TRI); + LIS.InsertMachineInstrRangeInMaps(std::prev(MI), MI); + ++NumSpills; + } + + // Remove redundant spills or change them to dead instructions. + NumSpills -= SpillsToRm.size(); + for (auto const RMEnt : SpillsToRm) { + RMEnt->setDesc(TII.get(TargetOpcode::KILL)); + for (unsigned i = RMEnt->getNumOperands(); i; --i) { + MachineOperand &MO = RMEnt->getOperand(i - 1); + if (MO.isReg() && MO.isImplicit() && MO.isDef() && !MO.isDead()) + RMEnt->RemoveOperand(i - 1); + } + } + Edit.eliminateDeadDefs(SpillsToRm, None, AA); + } +} + +/// For VirtReg clone, the \p New register should have the same physreg or +/// stackslot as the \p old register. +void HoistSpillHelper::LRE_DidCloneVirtReg(unsigned New, unsigned Old) { + if (VRM.hasPhys(Old)) + VRM.assignVirt2Phys(New, VRM.getPhys(Old)); + else if (VRM.getStackSlot(Old) != VirtRegMap::NO_STACK_SLOT) + VRM.assignVirt2StackSlot(New, VRM.getStackSlot(Old)); + else + llvm_unreachable("VReg should be assigned either physreg or stackslot"); +} |