summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/CodeGen')
-rw-r--r--llvm/lib/CodeGen/InlineSpiller.cpp994
-rw-r--r--llvm/lib/CodeGen/LiveRangeEdit.cpp63
-rw-r--r--llvm/lib/CodeGen/RegAllocBase.cpp9
-rw-r--r--llvm/lib/CodeGen/RegAllocBase.h10
-rw-r--r--llvm/lib/CodeGen/RegAllocBasic.cpp5
-rw-r--r--llvm/lib/CodeGen/RegAllocGreedy.cpp31
-rw-r--r--llvm/lib/CodeGen/RegAllocPBQP.cpp21
-rw-r--r--llvm/lib/CodeGen/Spiller.h4
-rw-r--r--llvm/lib/CodeGen/SplitKit.cpp93
-rw-r--r--llvm/lib/CodeGen/SplitKit.h12
10 files changed, 527 insertions, 715 deletions
diff --git a/llvm/lib/CodeGen/InlineSpiller.cpp b/llvm/lib/CodeGen/InlineSpiller.cpp
index e8abb3d0263..693e59fbba2 100644
--- a/llvm/lib/CodeGen/InlineSpiller.cpp
+++ b/llvm/lib/CodeGen/InlineSpiller.cpp
@@ -48,77 +48,13 @@ 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");
+STATISTIC(NumOmitReloadSpill, "Number of omitted spills of reloads");
+STATISTIC(NumHoists, "Number of hoisted spills");
static cl::opt<bool> DisableHoisting("disable-spill-hoist", cl::Hidden,
cl::desc("Disable inline spill hoisting"));
namespace {
-class HoistSpillHelper {
- LiveIntervals &LIS;
- LiveStacks &LSS;
- AliasAnalysis *AA;
- MachineDominatorTree &MDT;
- MachineLoopInfo &Loops;
- VirtRegMap &VRM;
- MachineFrameInfo &MFI;
- MachineRegisterInfo &MRI;
- const TargetInstrInfo &TII;
- const TargetRegisterInfo &TRI;
- const MachineBlockFrequencyInfo &MBFI;
-
- // Map from StackSlot to its original register.
- DenseMap<int, unsigned> StackSlotToReg;
- // 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.
- typedef DenseMap<std::pair<int, VNInfo *>, SmallPtrSet<MachineInstr *, 16>>
- MergeableSpillsMap;
- 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(unsigned OrigReg, 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(unsigned OrigReg, VNInfo &OrigVNI,
- SmallPtrSet<MachineInstr *, 16> &Spills,
- SmallVectorImpl<MachineInstr *> &SpillsToRm,
- DenseMap<MachineBasicBlock *, unsigned> &SpillsToIns);
-
-public:
- HoistSpillHelper(MachineFunctionPass &pass, MachineFunction &mf,
- VirtRegMap &vrm)
- : LIS(pass.getAnalysis<LiveIntervals>()),
- LSS(pass.getAnalysis<LiveStacks>()),
- AA(&pass.getAnalysis<AAResultsWrapperPass>().getAAResults()),
- MDT(pass.getAnalysis<MachineDominatorTree>()),
- Loops(pass.getAnalysis<MachineLoopInfo>()), VRM(vrm),
- MFI(*mf.getFrameInfo()), MRI(mf.getRegInfo()),
- TII(*mf.getSubtarget().getInstrInfo()),
- TRI(*mf.getSubtarget().getRegisterInfo()),
- MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()) {}
-
- void addToMergeableSpills(MachineInstr *Spill, int StackSlot,
- unsigned Original);
- bool rmFromMergeableSpills(MachineInstr *Spill, int StackSlot);
- void hoistAllSpills(LiveRangeEdit &Edit);
-};
-
class InlineSpiller : public Spiller {
MachineFunction &MF;
LiveIntervals &LIS;
@@ -149,12 +85,56 @@ class InlineSpiller : public Spiller {
// Values that failed to remat at some point.
SmallPtrSet<VNInfo*, 8> UsedValues;
+public:
+ // Information about a value that was defined by a copy from a sibling
+ // register.
+ struct SibValueInfo {
+ // True when all reaching defs were reloads: No spill is necessary.
+ bool AllDefsAreReloads;
+
+ // True when value is defined by an original PHI not from splitting.
+ bool DefByOrigPHI;
+
+ // True when the COPY defining this value killed its source.
+ bool KillsSource;
+
+ // The preferred register to spill.
+ unsigned SpillReg;
+
+ // The value of SpillReg that should be spilled.
+ VNInfo *SpillVNI;
+
+ // The block where SpillVNI should be spilled. Currently, this must be the
+ // block containing SpillVNI->def.
+ MachineBasicBlock *SpillMBB;
+
+ // A defining instruction that is not a sibling copy or a reload, or NULL.
+ // This can be used as a template for rematerialization.
+ MachineInstr *DefMI;
+
+ // List of values that depend on this one. These values are actually the
+ // same, but live range splitting has placed them in different registers,
+ // or SSA update needed to insert PHI-defs to preserve SSA form. This is
+ // copies of the current value and phi-kills. Usually only phi-kills cause
+ // more than one dependent value.
+ TinyPtrVector<VNInfo*> Deps;
+
+ SibValueInfo(unsigned Reg, VNInfo *VNI)
+ : AllDefsAreReloads(true), DefByOrigPHI(false), KillsSource(false),
+ SpillReg(Reg), SpillVNI(VNI), SpillMBB(nullptr), DefMI(nullptr) {}
+
+ // Returns true when a def has been found.
+ bool hasDef() const { return DefByOrigPHI || DefMI; }
+ };
+
+private:
+ // Values in RegsToSpill defined by sibling copies.
+ typedef DenseMap<VNInfo*, SibValueInfo> SibValueMap;
+ SibValueMap SibValues;
+
// Dead defs generated during spilling.
SmallVector<MachineInstr*, 8> DeadDefs;
- // Object records spills information and does the hoisting.
- HoistSpillHelper HSpiller;
-
~InlineSpiller() override {}
public:
@@ -167,11 +147,9 @@ public:
MFI(*mf.getFrameInfo()), MRI(mf.getRegInfo()),
TII(*mf.getSubtarget().getInstrInfo()),
TRI(*mf.getSubtarget().getRegisterInfo()),
- MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()),
- HSpiller(pass, mf, vrm) {}
+ MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()) {}
void spill(LiveRangeEdit &) override;
- void postOptimization();
private:
bool isSnippet(const LiveInterval &SnipLI);
@@ -183,7 +161,11 @@ private:
}
bool isSibling(unsigned Reg);
- bool hoistSpillInsideBB(LiveInterval &SpillLI, MachineInstr &CopyMI);
+ MachineInstr *traceSiblingValue(unsigned, VNInfo*, VNInfo*);
+ void propagateSiblingValue(SibValueMap::iterator, VNInfo *VNI = nullptr);
+ void analyzeSiblingValues();
+
+ bool hoistSpill(LiveInterval &SpillLI, MachineInstr &CopyMI);
void eliminateRedundantSpills(LiveInterval &LI, VNInfo *VNI);
void markValueUsed(LiveInterval*, VNInfo*);
@@ -315,45 +297,418 @@ void InlineSpiller::collectRegsToSpill() {
}
}
+
+//===----------------------------------------------------------------------===//
+// Sibling Values
+//===----------------------------------------------------------------------===//
+
+// After live range splitting, some values to be spilled may be defined by
+// copies from sibling registers. We trace the sibling copies back to the
+// original value if it still exists. We need it for rematerialization.
+//
+// Even when the value can't be rematerialized, we still want to determine if
+// the value has already been spilled, or we may want to hoist the spill from a
+// loop.
+
bool InlineSpiller::isSibling(unsigned Reg) {
return TargetRegisterInfo::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:
+#ifndef NDEBUG
+static raw_ostream &operator<<(raw_ostream &OS,
+ const InlineSpiller::SibValueInfo &SVI) {
+ OS << "spill " << PrintReg(SVI.SpillReg) << ':'
+ << SVI.SpillVNI->id << '@' << SVI.SpillVNI->def;
+ if (SVI.SpillMBB)
+ OS << " in BB#" << SVI.SpillMBB->getNumber();
+ if (SVI.AllDefsAreReloads)
+ OS << " all-reloads";
+ if (SVI.DefByOrigPHI)
+ OS << " orig-phi";
+ if (SVI.KillsSource)
+ OS << " kill";
+ OS << " deps[";
+ for (VNInfo *Dep : SVI.Deps)
+ OS << ' ' << Dep->id << '@' << Dep->def;
+ OS << " ]";
+ if (SVI.DefMI)
+ OS << " def: " << *SVI.DefMI;
+ else
+ OS << '\n';
+ return OS;
+}
+#endif
+
+/// propagateSiblingValue - Propagate the value in SVI to dependents if it is
+/// known. Otherwise remember the dependency for later.
///
-/// x = def
-/// y = use x
-/// s = copy x
+/// @param SVIIter SibValues entry to propagate.
+/// @param VNI Dependent value, or NULL to propagate to all saved dependents.
+void InlineSpiller::propagateSiblingValue(SibValueMap::iterator SVIIter,
+ VNInfo *VNI) {
+ SibValueMap::value_type *SVI = &*SVIIter;
+
+ // When VNI is non-NULL, add it to SVI's deps, and only propagate to that.
+ TinyPtrVector<VNInfo*> FirstDeps;
+ if (VNI) {
+ FirstDeps.push_back(VNI);
+ SVI->second.Deps.push_back(VNI);
+ }
+
+ // Has the value been completely determined yet? If not, defer propagation.
+ if (!SVI->second.hasDef())
+ return;
+
+ // Work list of values to propagate.
+ SmallSetVector<SibValueMap::value_type *, 8> WorkList;
+ WorkList.insert(SVI);
+
+ do {
+ SVI = WorkList.pop_back_val();
+ TinyPtrVector<VNInfo*> *Deps = VNI ? &FirstDeps : &SVI->second.Deps;
+ VNI = nullptr;
+
+ SibValueInfo &SV = SVI->second;
+ if (!SV.SpillMBB)
+ SV.SpillMBB = LIS.getMBBFromIndex(SV.SpillVNI->def);
+
+ DEBUG(dbgs() << " prop to " << Deps->size() << ": "
+ << SVI->first->id << '@' << SVI->first->def << ":\t" << SV);
+
+ assert(SV.hasDef() && "Propagating undefined value");
+
+ // Should this value be propagated as a preferred spill candidate? We don't
+ // propagate values of registers that are about to spill.
+ bool PropSpill = !DisableHoisting && !isRegToSpill(SV.SpillReg);
+ unsigned SpillDepth = ~0u;
+
+ for (VNInfo *Dep : *Deps) {
+ SibValueMap::iterator DepSVI = SibValues.find(Dep);
+ assert(DepSVI != SibValues.end() && "Dependent value not in SibValues");
+ SibValueInfo &DepSV = DepSVI->second;
+ if (!DepSV.SpillMBB)
+ DepSV.SpillMBB = LIS.getMBBFromIndex(DepSV.SpillVNI->def);
+
+ bool Changed = false;
+
+ // Propagate defining instruction.
+ if (!DepSV.hasDef()) {
+ Changed = true;
+ DepSV.DefMI = SV.DefMI;
+ DepSV.DefByOrigPHI = SV.DefByOrigPHI;
+ }
+
+ // Propagate AllDefsAreReloads. For PHI values, this computes an AND of
+ // all predecessors.
+ if (!SV.AllDefsAreReloads && DepSV.AllDefsAreReloads) {
+ Changed = true;
+ DepSV.AllDefsAreReloads = false;
+ }
+
+ // Propagate best spill value.
+ if (PropSpill && SV.SpillVNI != DepSV.SpillVNI) {
+ if (SV.SpillMBB == DepSV.SpillMBB) {
+ // DepSV is in the same block. Hoist when dominated.
+ if (DepSV.KillsSource && SV.SpillVNI->def < DepSV.SpillVNI->def) {
+ // This 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 x<kill>
+ //
+ // This hoist only helps when the DepSV copy kills its source.
+ Changed = true;
+ DepSV.SpillReg = SV.SpillReg;
+ DepSV.SpillVNI = SV.SpillVNI;
+ DepSV.SpillMBB = SV.SpillMBB;
+ }
+ } else {
+ // DepSV is in a different block.
+ if (SpillDepth == ~0u)
+ SpillDepth = Loops.getLoopDepth(SV.SpillMBB);
+
+ // Also hoist spills to blocks with smaller loop depth, but make sure
+ // that the new value dominates. Non-phi dependents are always
+ // dominated, phis need checking.
+
+ const BranchProbability MarginProb(4, 5); // 80%
+ // Hoist a spill to outer loop if there are multiple dependents (it
+ // can be beneficial if more than one dependents are hoisted) or
+ // if DepSV (the hoisting source) is hotter than SV (the hoisting
+ // destination) (we add a 80% margin to bias a little towards
+ // loop depth).
+ bool HoistCondition =
+ (MBFI.getBlockFreq(DepSV.SpillMBB) >=
+ (MBFI.getBlockFreq(SV.SpillMBB) * MarginProb)) ||
+ Deps->size() > 1;
+
+ if ((Loops.getLoopDepth(DepSV.SpillMBB) > SpillDepth) &&
+ HoistCondition &&
+ (!DepSVI->first->isPHIDef() ||
+ MDT.dominates(SV.SpillMBB, DepSV.SpillMBB))) {
+ Changed = true;
+ DepSV.SpillReg = SV.SpillReg;
+ DepSV.SpillVNI = SV.SpillVNI;
+ DepSV.SpillMBB = SV.SpillMBB;
+ }
+ }
+ }
+
+ if (!Changed)
+ continue;
+
+ // Something changed in DepSVI. Propagate to dependents.
+ WorkList.insert(&*DepSVI);
+
+ DEBUG(dbgs() << " update " << DepSVI->first->id << '@'
+ << DepSVI->first->def << " to:\t" << DepSV);
+ }
+ } while (!WorkList.empty());
+}
+
+/// traceSiblingValue - Trace a value that is about to be spilled back to the
+/// real defining instructions by looking through sibling copies. Always stay
+/// within the range of OrigVNI so the registers are known to carry the same
+/// value.
///
-/// Hoisting the spill of s to immediately after the def removes the
-/// interference between x and y:
+/// Determine if the value is defined by all reloads, so spilling isn't
+/// necessary - the value is already in the stack slot.
///
-/// x = def
-/// spill x
-/// y = use x<kill>
+/// Return a defining instruction that may be a candidate for rematerialization.
///
-/// This hoist only helps when the copy kills its source.
+MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI,
+ VNInfo *OrigVNI) {
+ // Check if a cached value already exists.
+ SibValueMap::iterator SVI;
+ bool Inserted;
+ std::tie(SVI, Inserted) =
+ SibValues.insert(std::make_pair(UseVNI, SibValueInfo(UseReg, UseVNI)));
+ if (!Inserted) {
+ DEBUG(dbgs() << "Cached value " << PrintReg(UseReg) << ':'
+ << UseVNI->id << '@' << UseVNI->def << ' ' << SVI->second);
+ return SVI->second.DefMI;
+ }
+
+ DEBUG(dbgs() << "Tracing value " << PrintReg(UseReg) << ':'
+ << UseVNI->id << '@' << UseVNI->def << '\n');
+
+ // List of (Reg, VNI) that have been inserted into SibValues, but need to be
+ // processed.
+ SmallVector<std::pair<unsigned, VNInfo*>, 8> WorkList;
+ WorkList.push_back(std::make_pair(UseReg, UseVNI));
+
+ LiveInterval &OrigLI = LIS.getInterval(Original);
+ do {
+ unsigned Reg;
+ VNInfo *VNI;
+ std::tie(Reg, VNI) = WorkList.pop_back_val();
+ DEBUG(dbgs() << " " << PrintReg(Reg) << ':' << VNI->id << '@' << VNI->def
+ << ":\t");
+
+ // First check if this value has already been computed.
+ SVI = SibValues.find(VNI);
+ assert(SVI != SibValues.end() && "Missing SibValues entry");
+
+ // Trace through PHI-defs created by live range splitting.
+ if (VNI->isPHIDef()) {
+ // Stop at original PHIs. We don't know the value at the
+ // predecessors. Look up the VNInfo for the current definition
+ // in OrigLI, to properly determine whether or not this phi was
+ // added by splitting.
+ if (VNI->def == OrigLI.getVNInfoAt(VNI->def)->def) {
+ DEBUG(dbgs() << "orig phi value\n");
+ SVI->second.DefByOrigPHI = true;
+ SVI->second.AllDefsAreReloads = false;
+ propagateSiblingValue(SVI);
+ continue;
+ }
+
+ // This is a PHI inserted by live range splitting. We could trace the
+ // live-out value from predecessor blocks, but that search can be very
+ // expensive if there are many predecessors and many more PHIs as
+ // generated by tail-dup when it sees an indirectbr. Instead, look at
+ // all the non-PHI defs that have the same value as OrigVNI. They must
+ // jointly dominate VNI->def. This is not optimal since VNI may actually
+ // be jointly dominated by a smaller subset of defs, so there is a change
+ // we will miss a AllDefsAreReloads optimization.
+
+ // Separate all values dominated by OrigVNI into PHIs and non-PHIs.
+ SmallVector<VNInfo*, 8> PHIs, NonPHIs;
+ LiveInterval &LI = LIS.getInterval(Reg);
+
+ for (LiveInterval::vni_iterator VI = LI.vni_begin(), VE = LI.vni_end();
+ VI != VE; ++VI) {
+ VNInfo *VNI2 = *VI;
+ if (VNI2->isUnused())
+ continue;
+ if (!OrigLI.containsOneValue() &&
+ OrigLI.getVNInfoAt(VNI2->def) != OrigVNI)
+ continue;
+ if (VNI2->isPHIDef() && VNI2->def != OrigVNI->def)
+ PHIs.push_back(VNI2);
+ else
+ NonPHIs.push_back(VNI2);
+ }
+ DEBUG(dbgs() << "split phi value, checking " << PHIs.size()
+ << " phi-defs, and " << NonPHIs.size()
+ << " non-phi/orig defs\n");
+
+ // Create entries for all the PHIs. Don't add them to the worklist, we
+ // are processing all of them in one go here.
+ for (VNInfo *PHI : PHIs)
+ SibValues.insert(std::make_pair(PHI, SibValueInfo(Reg, PHI)));
+
+ // Add every PHI as a dependent of all the non-PHIs.
+ for (VNInfo *NonPHI : NonPHIs) {
+ // Known value? Try an insertion.
+ std::tie(SVI, Inserted) =
+ SibValues.insert(std::make_pair(NonPHI, SibValueInfo(Reg, NonPHI)));
+ // Add all the PHIs as dependents of NonPHI.
+ SVI->second.Deps.insert(SVI->second.Deps.end(), PHIs.begin(),
+ PHIs.end());
+ // This is the first time we see NonPHI, add it to the worklist.
+ if (Inserted)
+ WorkList.push_back(std::make_pair(Reg, NonPHI));
+ else
+ // Propagate to all inserted PHIs, not just VNI.
+ propagateSiblingValue(SVI);
+ }
+
+ // Next work list item.
+ continue;
+ }
+
+ MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
+ assert(MI && "Missing def");
+
+ // Trace through sibling copies.
+ if (unsigned SrcReg = isFullCopyOf(MI, Reg)) {
+ if (isSibling(SrcReg)) {
+ LiveInterval &SrcLI = LIS.getInterval(SrcReg);
+ LiveQueryResult SrcQ = SrcLI.Query(VNI->def);
+ assert(SrcQ.valueIn() && "Copy from non-existing value");
+ // Check if this COPY kills its source.
+ SVI->second.KillsSource = SrcQ.isKill();
+ VNInfo *SrcVNI = SrcQ.valueIn();
+ DEBUG(dbgs() << "copy of " << PrintReg(SrcReg) << ':'
+ << SrcVNI->id << '@' << SrcVNI->def
+ << " kill=" << unsigned(SVI->second.KillsSource) << '\n');
+ // Known sibling source value? Try an insertion.
+ std::tie(SVI, Inserted) = SibValues.insert(
+ std::make_pair(SrcVNI, SibValueInfo(SrcReg, SrcVNI)));
+ // This is the first time we see Src, add it to the worklist.
+ if (Inserted)
+ WorkList.push_back(std::make_pair(SrcReg, SrcVNI));
+ propagateSiblingValue(SVI, VNI);
+ // Next work list item.
+ continue;
+ }
+ }
+
+ // Track reachable reloads.
+ SVI->second.DefMI = MI;
+ SVI->second.SpillMBB = MI->getParent();
+ int FI;
+ if (Reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot) {
+ DEBUG(dbgs() << "reload\n");
+ propagateSiblingValue(SVI);
+ // Next work list item.
+ continue;
+ }
+
+ // Potential remat candidate.
+ DEBUG(dbgs() << "def " << *MI);
+ SVI->second.AllDefsAreReloads = false;
+ propagateSiblingValue(SVI);
+ } while (!WorkList.empty());
+
+ // Look up the value we were looking for. We already did this lookup at the
+ // top of the function, but SibValues may have been invalidated.
+ SVI = SibValues.find(UseVNI);
+ assert(SVI != SibValues.end() && "Didn't compute requested info");
+ DEBUG(dbgs() << " traced to:\t" << SVI->second);
+ return SVI->second.DefMI;
+}
+
+/// analyzeSiblingValues - Trace values defined by sibling copies back to
+/// something that isn't a sibling copy.
///
-bool InlineSpiller::hoistSpillInsideBB(LiveInterval &SpillLI,
- MachineInstr &CopyMI) {
+/// Keep track of values that may be rematerializable.
+void InlineSpiller::analyzeSiblingValues() {
+ SibValues.clear();
+
+ // No siblings at all?
+ if (Edit->getReg() == Original)
+ return;
+
+ LiveInterval &OrigLI = LIS.getInterval(Original);
+ for (unsigned Reg : RegsToSpill) {
+ LiveInterval &LI = LIS.getInterval(Reg);
+ for (LiveInterval::const_vni_iterator VI = LI.vni_begin(),
+ VE = LI.vni_end(); VI != VE; ++VI) {
+ VNInfo *VNI = *VI;
+ if (VNI->isUnused())
+ continue;
+ MachineInstr *DefMI = nullptr;
+ if (!VNI->isPHIDef()) {
+ DefMI = LIS.getInstructionFromIndex(VNI->def);
+ assert(DefMI && "No defining instruction");
+ }
+ // Check possible sibling copies.
+ if (VNI->isPHIDef() || DefMI->isCopy()) {
+ VNInfo *OrigVNI = OrigLI.getVNInfoAt(VNI->def);
+ assert(OrigVNI && "Def outside original live range");
+ if (OrigVNI->def != VNI->def)
+ DefMI = traceSiblingValue(Reg, VNI, OrigVNI);
+ }
+ if (DefMI && Edit->checkRematerializable(VNI, DefMI, AA)) {
+ DEBUG(dbgs() << "Value " << PrintReg(Reg) << ':' << VNI->id << '@'
+ << VNI->def << " may remat from " << *DefMI);
+ }
+ }
+ }
+}
+
+/// hoistSpill - Given a sibling copy that defines a value to be spilled, insert
+/// a spill at a better location.
+bool InlineSpiller::hoistSpill(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
- unsigned 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())
+ SibValueMap::iterator I = SibValues.find(VNI);
+ if (I == SibValues.end())
+ return false;
+
+ const SibValueInfo &SVI = I->second;
+
+ // Let the normal folding code deal with the boring case.
+ if (!SVI.AllDefsAreReloads && SVI.SpillVNI == VNI)
return false;
+ // SpillReg may have been deleted by remat and DCE.
+ if (!LIS.hasInterval(SVI.SpillReg)) {
+ DEBUG(dbgs() << "Stale interval: " << PrintReg(SVI.SpillReg) << '\n');
+ SibValues.erase(I);
+ return false;
+ }
+
+ LiveInterval &SibLI = LIS.getInterval(SVI.SpillReg);
+ if (!SibLI.containsValue(SVI.SpillVNI)) {
+ DEBUG(dbgs() << "Stale value: " << PrintReg(SVI.SpillReg) << '\n');
+ SibValues.erase(I);
+ 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.
@@ -364,29 +719,35 @@ bool InlineSpiller::hoistSpillInsideBB(LiveInterval &SpillLI,
DEBUG(dbgs() << "\tmerged orig valno " << OrigVNI->id << ": "
<< *StackInt << '\n');
- // We are going to spill SrcVNI immediately after its def, so clear out
+ // Already spilled everywhere.
+ if (SVI.AllDefsAreReloads) {
+ DEBUG(dbgs() << "\tno spill needed: " << SVI);
+ ++NumOmitReloadSpill;
+ return true;
+ }
+ // We are going to spill SVI.SpillVNI immediately after its def, so clear out
// any later spills of the same value.
- eliminateRedundantSpills(SrcLI, SrcVNI);
+ eliminateRedundantSpills(SibLI, SVI.SpillVNI);
- MachineBasicBlock *MBB = LIS.getMBBFromIndex(SrcVNI->def);
+ MachineBasicBlock *MBB = LIS.getMBBFromIndex(SVI.SpillVNI->def);
MachineBasicBlock::iterator MII;
- if (SrcVNI->isPHIDef())
+ if (SVI.SpillVNI->isPHIDef())
MII = MBB->SkipPHIsAndLabels(MBB->begin());
else {
- MachineInstr *DefMI = LIS.getInstructionFromIndex(SrcVNI->def);
+ MachineInstr *DefMI = LIS.getInstructionFromIndex(SVI.SpillVNI->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);
+ TII.storeRegToStackSlot(*MBB, MII, SVI.SpillReg, false, StackSlot,
+ MRI.getRegClass(SVI.SpillReg), &TRI);
--MII; // Point to store instruction.
LIS.InsertMachineInstrInMaps(*MII);
- DEBUG(dbgs() << "\thoisted: " << SrcVNI->def << '\t' << *MII);
+ DEBUG(dbgs() << "\thoisted: " << SVI.SpillVNI->def << '\t' << *MII);
- HSpiller.addToMergeableSpills(&(*MII), StackSlot, Original);
++NumSpills;
+ ++NumHoists;
return true;
}
@@ -444,8 +805,7 @@ void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) {
MI->setDesc(TII.get(TargetOpcode::KILL));
DeadDefs.push_back(MI);
++NumSpillsRemoved;
- if (HSpiller.rmFromMergeableSpills(MI, StackSlot))
- --NumSpills;
+ --NumSpills;
}
}
} while (!WorkList.empty());
@@ -516,12 +876,12 @@ bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, MachineInstr &MI) {
if (SnippetCopies.count(&MI))
return false;
- LiveInterval &OrigLI = LIS.getInterval(Original);
- VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);
+ // Use an OrigVNI from traceSiblingValue when ParentVNI is a sibling copy.
LiveRangeEdit::Remat RM(ParentVNI);
- RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);
-
- if (!Edit->canRematerializeAt(RM, OrigVNI, UseIdx, false)) {
+ SibValueMap::const_iterator SibI = SibValues.find(ParentVNI);
+ if (SibI != SibValues.end())
+ RM.OrigMI = SibI->second.DefMI;
+ if (!Edit->canRematerializeAt(RM, UseIdx, false)) {
markValueUsed(&VirtReg, ParentVNI);
DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << MI);
return false;
@@ -571,6 +931,7 @@ bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, MachineInstr &MI) {
/// reMaterializeAll - Try to rematerialize as many uses as possible,
/// and trim the live ranges after.
void InlineSpiller::reMaterializeAll() {
+ // analyzeSiblingValues has already tested all relevant defining instructions.
if (!Edit->anyRematerializable(AA))
return;
@@ -656,9 +1017,6 @@ bool InlineSpiller::coalesceStackAccess(MachineInstr *MI, unsigned Reg) {
if (InstrReg != Reg || FI != StackSlot)
return false;
- if (!IsLoad)
- HSpiller.rmFromMergeableSpills(MI, StackSlot);
-
DEBUG(dbgs() << "Coalescing stack access: " << *MI);
LIS.RemoveMachineInstrFromMaps(*MI);
MI->eraseFromParent();
@@ -783,9 +1141,6 @@ foldMemoryOperand(ArrayRef<std::pair<MachineInstr*, unsigned> > Ops,
LIS.removePhysRegDefAt(Reg, Idx);
}
- int FI;
- if (TII.isStoreToStackSlot(MI, FI) && HSpiller.rmFromMergeableSpills(MI, FI))
- --NumSpills;
LIS.ReplaceMachineInstrInMaps(*MI, *FoldMI);
MI->eraseFromParent();
@@ -811,10 +1166,9 @@ foldMemoryOperand(ArrayRef<std::pair<MachineInstr*, unsigned> > Ops,
if (!WasCopy)
++NumFolded;
- else if (Ops.front().second == 0) {
+ else if (Ops.front().second == 0)
++NumSpills;
- HSpiller.addToMergeableSpills(FoldMI, StackSlot, Original);
- } else
+ else
++NumReloads;
return true;
}
@@ -849,7 +1203,6 @@ void InlineSpiller::insertSpill(unsigned NewVReg, bool isKill,
DEBUG(dumpMachineInstrRangeWithSlotIndex(std::next(MI), MIS.end(), LIS,
"spill"));
++NumSpills;
- HSpiller.addToMergeableSpills(std::next(MI), StackSlot, Original);
}
/// spillAroundUses - insert spill code around each use of Reg.
@@ -913,7 +1266,8 @@ void InlineSpiller::spillAroundUses(unsigned Reg) {
continue;
}
if (RI.Writes) {
- if (hoistSpillInsideBB(OldLI, *MI)) {
+ // Hoist the spill of a sib-reg copy.
+ if (hoistSpill(OldLI, *MI)) {
// This COPY is now dead, the value is already in the stack slot.
MI->getOperand(0).setIsDead();
DeadDefs.push_back(MI);
@@ -1026,6 +1380,7 @@ void InlineSpiller::spill(LiveRangeEdit &edit) {
assert(DeadDefs.empty() && "Previous spill didn't remove dead defs");
collectRegsToSpill();
+ analyzeSiblingValues();
reMaterializeAll();
// Remat may handle everything.
@@ -1034,394 +1389,3 @@ void InlineSpiller::spill(LiveRangeEdit &edit) {
Edit->calculateRegClassAndHint(MF, Loops, MBFI);
}
-
-/// Optimizations after all the reg selections and spills are done.
-///
-void InlineSpiller::postOptimization() {
- SmallVector<unsigned, 4> NewVRegs;
- LiveRangeEdit LRE(nullptr, NewVRegs, MF, LIS, &VRM, nullptr);
- HSpiller.hoistAllSpills(LRE);
- assert(NewVRegs.size() == 0 &&
- "No new vregs should be generated in hoistAllSpills");
-}
-
-/// When a spill is inserted, add the spill to MergeableSpills map.
-///
-void HoistSpillHelper::addToMergeableSpills(MachineInstr *Spill, int StackSlot,
- unsigned Original) {
- StackSlotToReg[StackSlot] = Original;
- SlotIndex Idx = LIS.getInstructionIndex(*Spill);
- VNInfo *OrigVNI = LIS.getInterval(Original).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) {
- int Original = StackSlotToReg[StackSlot];
- if (!Original)
- return false;
- SlotIndex Idx = LIS.getInstructionIndex(*Spill);
- VNInfo *OrigVNI = LIS.getInterval(Original).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(unsigned OrigReg, VNInfo &OrigVNI,
- MachineBasicBlock &BB, unsigned &LiveReg) {
- SlotIndex Idx;
- MachineBasicBlock::iterator MI = BB.getFirstTerminator();
- if (MI != BB.end())
- Idx = LIS.getInstructionIndex(*MI);
- else
- Idx = LIS.getMBBEndIdx(&BB).getPrevSlot();
- SmallSetVector<unsigned, 16> &Siblings = Virt2SiblingsMap[OrigReg];
- assert((LIS.getInterval(OrigReg)).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 redundent spills in the same BB. Save those redundent 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.DT->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.DT->getNode(Block)] = SpillToKeep;
- } else {
- SpillBBToSpill[MDT.DT->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-redundent 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 redundent and the node containing it will be removed. All the nodes on
- // the path starting from the first node with non-redundent 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 redundent.
- 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.DT->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
- DEBUG(dbgs() << "Orders size is " << Orders.size() << "\n");
- SmallVector<MachineDomTreeNode *, 32>::reverse_iterator RIt = Orders.rbegin();
- for (; RIt != Orders.rend(); RIt++)
- DEBUG(dbgs() << "BB" << (*RIt)->getBlock()->getNumber() << ",");
- 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(
- unsigned OrigReg, 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);
-
- // SpillsInSubTree 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.
- typedef std::pair<SmallPtrSet<MachineDomTreeNode *, 16>, BlockFrequency>
- NodesCostPair;
- 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();
- SmallPtrSet<MachineDomTreeNode *, 16> &SpillsInSubTree =
- SpillsInSubTreeMap[*RIt].first;
- // Total spill costs inside the sub tree.
- BlockFrequency &SubTreeCost = SpillsInSubTreeMap[*RIt].second;
-
- // If Block contains an original spill, simply continue.
- if (SpillsToKeep.find(*RIt) != SpillsToKeep.end() && !SpillsToKeep[*RIt]) {
- SpillsInSubTree.insert(*RIt);
- SubTreeCost = MBFI.getBlockFreq(Block);
- continue;
- }
-
- // Collect spills in subtree of current node (*RIt) to
- // SpillsInSubTree.
- const std::vector<MachineDomTreeNode *> &Children = (*RIt)->getChildren();
- unsigned NumChildren = Children.size();
- for (unsigned i = 0; i != NumChildren; ++i) {
- MachineDomTreeNode *Child = Children[i];
- SpillsInSubTree.insert(SpillsInSubTreeMap[Child].first.begin(),
- SpillsInSubTreeMap[Child].first.end());
- SubTreeCost += SpillsInSubTreeMap[Child].second;
- SpillsInSubTreeMap.erase(Child);
- }
-
- // 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(OrigReg, 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;
- 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 redundent spills and hoist the 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 define instruction and are dominated by the instruction.
-/// Before hoisting all the equal spills, redundent spills inside in the same
-/// BB is first marked to be deleted. Then starting from 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 consider 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(LiveRangeEdit &Edit) {
- // Save the mapping between stackslot and its original reg.
- DenseMap<int, unsigned> SlotToOrigReg;
- for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
- unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
- int Slot = VRM.getStackSlot(Reg);
- if (Slot != VirtRegMap::NO_STACK_SLOT)
- SlotToOrigReg[Slot] = VRM.getOriginal(Reg);
- 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;
- unsigned OrigReg = SlotToOrigReg[Slot];
- VNInfo *OrigVNI = Ent.first.second;
- SmallPtrSet<MachineInstr *, 16> &EqValSpills = Ent.second;
- if (Ent.second.empty())
- continue;
-
- 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(OrigReg, *OrigVNI, EqValSpills, SpillsToRm, SpillsToIns);
-
- 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()) {
- LiveInterval &OrigLI = LIS.getInterval(OrigReg);
- 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 = BB->getFirstTerminator();
- TII.storeRegToStackSlot(*BB, MI, LiveReg, false, Slot,
- MRI.getRegClass(LiveReg), &TRI);
- LIS.InsertMachineInstrRangeInMaps(std::prev(MI), MI);
- ++NumSpills;
- }
-
- // Remove redundent 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, true);
- }
-}
diff --git a/llvm/lib/CodeGen/LiveRangeEdit.cpp b/llvm/lib/CodeGen/LiveRangeEdit.cpp
index 5610c5afa0d..72eafcd0792 100644
--- a/llvm/lib/CodeGen/LiveRangeEdit.cpp
+++ b/llvm/lib/CodeGen/LiveRangeEdit.cpp
@@ -63,13 +63,10 @@ void LiveRangeEdit::scanRemattable(AliasAnalysis *aa) {
for (VNInfo *VNI : getParent().valnos) {
if (VNI->isUnused())
continue;
- unsigned Original = VRM->getOriginal(getReg());
- LiveInterval &OrigLI = LIS.getInterval(Original);
- VNInfo *OrigVNI = OrigLI.getVNInfoAt(VNI->def);
- MachineInstr *DefMI = LIS.getInstructionFromIndex(OrigVNI->def);
+ MachineInstr *DefMI = LIS.getInstructionFromIndex(VNI->def);
if (!DefMI)
continue;
- checkRematerializable(OrigVNI, DefMI, aa);
+ checkRematerializable(VNI, DefMI, aa);
}
ScannedRemattable = true;
}
@@ -116,18 +113,24 @@ bool LiveRangeEdit::allUsesAvailableAt(const MachineInstr *OrigMI,
return true;
}
-bool LiveRangeEdit::canRematerializeAt(Remat &RM, VNInfo *OrigVNI,
- SlotIndex UseIdx, bool cheapAsAMove) {
+bool LiveRangeEdit::canRematerializeAt(Remat &RM,
+ SlotIndex UseIdx,
+ bool cheapAsAMove) {
assert(ScannedRemattable && "Call anyRematerializable first");
// Use scanRemattable info.
- if (!Remattable.count(OrigVNI))
+ if (!Remattable.count(RM.ParentVNI))
return false;
// No defining instruction provided.
SlotIndex DefIdx;
- assert(RM.OrigMI && "No defining instruction for remattable value");
- DefIdx = LIS.getInstructionIndex(*RM.OrigMI);
+ if (RM.OrigMI)
+ DefIdx = LIS.getInstructionIndex(*RM.OrigMI);
+ else {
+ DefIdx = RM.ParentVNI->def;
+ RM.OrigMI = LIS.getInstructionFromIndex(DefIdx);
+ assert(RM.OrigMI && "No defining instruction for remattable value");
+ }
// If only cheap remats were requested, bail out early.
if (cheapAsAMove && !TII.isAsCheapAsAMove(RM.OrigMI))
@@ -258,15 +261,6 @@ void LiveRangeEdit::eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink) {
// Collect virtual registers to be erased after MI is gone.
SmallVector<unsigned, 8> RegsToErase;
bool ReadsPhysRegs = false;
- bool isOrigDef = false;
- unsigned Dest;
- if (VRM && MI->getOperand(0).isReg()) {
- Dest = MI->getOperand(0).getReg();
- unsigned Original = VRM->getOriginal(Dest);
- LiveInterval &OrigLI = LIS.getInterval(Original);
- VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx);
- isOrigDef = SlotIndex::isSameInstr(OrigVNI->def, Idx);
- }
// Check for live intervals that may shrink
for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
@@ -320,24 +314,11 @@ void LiveRangeEdit::eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink) {
}
DEBUG(dbgs() << "Converted physregs to:\t" << *MI);
} else {
- // If the dest of MI is an original reg, don't delete the inst. Replace
- // the dest with a new reg, keep the inst for remat of other siblings.
- // The inst is saved in LiveRangeEdit::DeadRemats and will be deleted
- // after all the allocations of the func are done.
- if (isOrigDef) {
- unsigned NewDest = createFrom(Dest);
- pop_back();
- markDeadRemat(MI);
- const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
- MI->substituteRegister(Dest, NewDest, 0, TRI);
- MI->getOperand(0).setIsDead(false);
- } else {
- if (TheDelegate)
- TheDelegate->LRE_WillEraseInstruction(MI);
- LIS.RemoveMachineInstrFromMaps(*MI);
- MI->eraseFromParent();
- ++NumDCEDeleted;
- }
+ if (TheDelegate)
+ TheDelegate->LRE_WillEraseInstruction(MI);
+ LIS.RemoveMachineInstrFromMaps(*MI);
+ MI->eraseFromParent();
+ ++NumDCEDeleted;
}
// Erase any virtregs that are now empty and unused. There may be <undef>
@@ -351,9 +332,8 @@ void LiveRangeEdit::eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink) {
}
}
-void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl<MachineInstr *> &Dead,
- ArrayRef<unsigned> RegsBeingSpilled,
- bool NoSplit) {
+void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl<MachineInstr*> &Dead,
+ ArrayRef<unsigned> RegsBeingSpilled) {
ToShrinkSet ToShrink;
for (;;) {
@@ -375,9 +355,6 @@ void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl<MachineInstr *> &Dead,
if (!LIS.shrinkToUses(LI, &Dead))
continue;
- if (NoSplit)
- continue;
-
// Don't create new intervals for a register being spilled.
// The new intervals would have to be spilled anyway so its not worth it.
// Also they currently aren't spilled so creating them and not spilling
diff --git a/llvm/lib/CodeGen/RegAllocBase.cpp b/llvm/lib/CodeGen/RegAllocBase.cpp
index 1130d64689d..16ff48e78a7 100644
--- a/llvm/lib/CodeGen/RegAllocBase.cpp
+++ b/llvm/lib/CodeGen/RegAllocBase.cpp
@@ -153,12 +153,3 @@ void RegAllocBase::allocatePhysRegs() {
}
}
}
-
-void RegAllocBase::postOptimization() {
- spiller().postOptimization();
- for (auto DeadInst : DeadRemats) {
- LIS->RemoveMachineInstrFromMaps(*DeadInst);
- DeadInst->eraseFromParent();
- }
- DeadRemats.clear();
-}
diff --git a/llvm/lib/CodeGen/RegAllocBase.h b/llvm/lib/CodeGen/RegAllocBase.h
index 296ffe8692c..659b8f505a2 100644
--- a/llvm/lib/CodeGen/RegAllocBase.h
+++ b/llvm/lib/CodeGen/RegAllocBase.h
@@ -65,12 +65,6 @@ protected:
LiveRegMatrix *Matrix;
RegisterClassInfo RegClassInfo;
- /// Inst which is a def of an original reg and whose defs are already all
- /// dead after remat is saved in DeadRemats. The deletion of such inst is
- /// postponed till all the allocations are done, so its remat expr is
- /// always available for the remat of all the siblings of the original reg.
- SmallPtrSet<MachineInstr *, 32> DeadRemats;
-
RegAllocBase()
: TRI(nullptr), MRI(nullptr), VRM(nullptr), LIS(nullptr), Matrix(nullptr) {}
@@ -83,10 +77,6 @@ protected:
// physical register assignments.
void allocatePhysRegs();
- // Include spiller post optimization and removing dead defs left because of
- // rematerialization.
- virtual void postOptimization();
-
// Get a temporary reference to a Spiller instance.
virtual Spiller &spiller() = 0;
diff --git a/llvm/lib/CodeGen/RegAllocBasic.cpp b/llvm/lib/CodeGen/RegAllocBasic.cpp
index 11dfda67377..cfe367d5115 100644
--- a/llvm/lib/CodeGen/RegAllocBasic.cpp
+++ b/llvm/lib/CodeGen/RegAllocBasic.cpp
@@ -199,7 +199,7 @@ bool RABasic::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg,
Matrix->unassign(Spill);
// Spill the extracted interval.
- LiveRangeEdit LRE(&Spill, SplitVRegs, *MF, *LIS, VRM, nullptr, &DeadRemats);
+ LiveRangeEdit LRE(&Spill, SplitVRegs, *MF, *LIS, VRM);
spiller().spill(LRE);
}
return true;
@@ -258,7 +258,7 @@ unsigned RABasic::selectOrSplit(LiveInterval &VirtReg,
DEBUG(dbgs() << "spilling: " << VirtReg << '\n');
if (!VirtReg.isSpillable())
return ~0u;
- LiveRangeEdit LRE(&VirtReg, SplitVRegs, *MF, *LIS, VRM, nullptr, &DeadRemats);
+ LiveRangeEdit LRE(&VirtReg, SplitVRegs, *MF, *LIS, VRM);
spiller().spill(LRE);
// The live virtual register requesting allocation was spilled, so tell
@@ -283,7 +283,6 @@ bool RABasic::runOnMachineFunction(MachineFunction &mf) {
SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
allocatePhysRegs();
- postOptimization();
// Diagnostic output before rewriting
DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n");
diff --git a/llvm/lib/CodeGen/RegAllocGreedy.cpp b/llvm/lib/CodeGen/RegAllocGreedy.cpp
index 4736da6bcd6..b243d4357bd 100644
--- a/llvm/lib/CodeGen/RegAllocGreedy.cpp
+++ b/llvm/lib/CodeGen/RegAllocGreedy.cpp
@@ -12,6 +12,7 @@
//
//===----------------------------------------------------------------------===//
+#include "llvm/CodeGen/Passes.h"
#include "AllocationOrder.h"
#include "InterferenceCache.h"
#include "LiveDebugVariables.h"
@@ -32,7 +33,6 @@
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/VirtRegMap.h"
@@ -44,7 +44,6 @@
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/Timer.h"
#include "llvm/Support/raw_ostream.h"
-#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
#include <queue>
@@ -56,14 +55,14 @@ STATISTIC(NumGlobalSplits, "Number of split global live ranges");
STATISTIC(NumLocalSplits, "Number of split local live ranges");
STATISTIC(NumEvicted, "Number of interferences evicted");
-static cl::opt<SplitEditor::ComplementSpillMode> SplitSpillMode(
- "split-spill-mode", cl::Hidden,
- cl::desc("Spill mode for splitting live ranges"),
- cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"),
- clEnumValN(SplitEditor::SM_Size, "size", "Optimize for size"),
- clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed"),
- clEnumValEnd),
- cl::init(SplitEditor::SM_Speed));
+static cl::opt<SplitEditor::ComplementSpillMode>
+SplitSpillMode("split-spill-mode", cl::Hidden,
+ cl::desc("Spill mode for splitting live ranges"),
+ cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"),
+ clEnumValN(SplitEditor::SM_Size, "size", "Optimize for size"),
+ clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed"),
+ clEnumValEnd),
+ cl::init(SplitEditor::SM_Partition));
static cl::opt<unsigned>
LastChanceRecoloringMaxDepth("lcr-max-depth", cl::Hidden,
@@ -1466,7 +1465,7 @@ unsigned RAGreedy::doRegionSplit(LiveInterval &VirtReg, unsigned BestCand,
SmallVectorImpl<unsigned> &NewVRegs) {
SmallVector<unsigned, 8> UsedCands;
// Prepare split editor.
- LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
+ LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this);
SE->reset(LREdit, SplitSpillMode);
// Assign all edge bundles to the preferred candidate, or NoCand.
@@ -1514,7 +1513,7 @@ unsigned RAGreedy::tryBlockSplit(LiveInterval &VirtReg, AllocationOrder &Order,
assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed");
unsigned Reg = VirtReg.reg;
bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg));
- LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
+ LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this);
SE->reset(LREdit, SplitSpillMode);
ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
for (unsigned i = 0; i != UseBlocks.size(); ++i) {
@@ -1586,7 +1585,7 @@ RAGreedy::tryInstructionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
// Always enable split spill mode, since we're effectively spilling to a
// register.
- LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
+ LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this);
SE->reset(LREdit, SplitEditor::SM_Size);
ArrayRef<SlotIndex> Uses = SA->getUseSlots();
@@ -1909,7 +1908,7 @@ unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
<< '-' << Uses[BestAfter] << ", " << BestDiff
<< ", " << (BestAfter - BestBefore + 1) << " instrs\n");
- LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
+ LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this);
SE->reset(LREdit);
SE->openIntv();
@@ -2552,7 +2551,7 @@ unsigned RAGreedy::selectOrSplitImpl(LiveInterval &VirtReg,
NewVRegs.push_back(VirtReg.reg);
} else {
NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
- LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
+ LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM, this);
spiller().spill(LRE);
setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done);
@@ -2610,8 +2609,6 @@ bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
allocatePhysRegs();
tryHintsRecoloring();
- postOptimization();
-
releaseMemory();
return true;
}
diff --git a/llvm/lib/CodeGen/RegAllocPBQP.cpp b/llvm/lib/CodeGen/RegAllocPBQP.cpp
index d1221ec59bd..d5b0f96e24a 100644
--- a/llvm/lib/CodeGen/RegAllocPBQP.cpp
+++ b/llvm/lib/CodeGen/RegAllocPBQP.cpp
@@ -123,12 +123,6 @@ private:
RegSet VRegsToAlloc, EmptyIntervalVRegs;
- /// Inst which is a def of an original reg and whose defs are already all
- /// dead after remat is saved in DeadRemats. The deletion of such inst is
- /// postponed till all the allocations are done, so its remat expr is
- /// always available for the remat of all the siblings of the original reg.
- SmallPtrSet<MachineInstr *, 32> DeadRemats;
-
/// \brief Finds the initial set of vreg intervals to allocate.
void findVRegIntervalsToAlloc(const MachineFunction &MF, LiveIntervals &LIS);
@@ -152,7 +146,6 @@ private:
void finalizeAlloc(MachineFunction &MF, LiveIntervals &LIS,
VirtRegMap &VRM) const;
- void postOptimization(Spiller &VRegSpiller, LiveIntervals &LIS);
};
char RegAllocPBQP::ID = 0;
@@ -638,8 +631,7 @@ void RegAllocPBQP::spillVReg(unsigned VReg,
VirtRegMap &VRM, Spiller &VRegSpiller) {
VRegsToAlloc.erase(VReg);
- LiveRangeEdit LRE(&LIS.getInterval(VReg), NewIntervals, MF, LIS, &VRM,
- nullptr, &DeadRemats);
+ LiveRangeEdit LRE(&LIS.getInterval(VReg), NewIntervals, MF, LIS, &VRM);
VRegSpiller.spill(LRE);
const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
@@ -721,16 +713,6 @@ void RegAllocPBQP::finalizeAlloc(MachineFunction &MF,
}
}
-void RegAllocPBQP::postOptimization(Spiller &VRegSpiller, LiveIntervals &LIS) {
- VRegSpiller.postOptimization();
- /// Remove dead defs because of rematerialization.
- for (auto DeadInst : DeadRemats) {
- LIS.RemoveMachineInstrFromMaps(*DeadInst);
- DeadInst->eraseFromParent();
- }
- DeadRemats.clear();
-}
-
static inline float normalizePBQPSpillWeight(float UseDefFreq, unsigned Size,
unsigned NumInstr) {
// All intervals have a spill weight that is mostly proportional to the number
@@ -816,7 +798,6 @@ bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) {
// Finalise allocation, allocate empty ranges.
finalizeAlloc(MF, LIS, VRM);
- postOptimization(*VRegSpiller, LIS);
VRegsToAlloc.clear();
EmptyIntervalVRegs.clear();
diff --git a/llvm/lib/CodeGen/Spiller.h b/llvm/lib/CodeGen/Spiller.h
index 21037e68230..08f99ec78ad 100644
--- a/llvm/lib/CodeGen/Spiller.h
+++ b/llvm/lib/CodeGen/Spiller.h
@@ -16,7 +16,6 @@ namespace llvm {
class MachineFunction;
class MachineFunctionPass;
class VirtRegMap;
- class LiveIntervals;
/// Spiller interface.
///
@@ -29,7 +28,7 @@ namespace llvm {
/// spill - Spill the LRE.getParent() live interval.
virtual void spill(LiveRangeEdit &LRE) = 0;
- virtual void postOptimization() {};
+
};
/// Create and return a spiller that will insert spill code directly instead
@@ -37,6 +36,7 @@ namespace llvm {
Spiller *createInlineSpiller(MachineFunctionPass &pass,
MachineFunction &mf,
VirtRegMap &vrm);
+
}
#endif
diff --git a/llvm/lib/CodeGen/SplitKit.cpp b/llvm/lib/CodeGen/SplitKit.cpp
index 02895199944..5be82b85272 100644
--- a/llvm/lib/CodeGen/SplitKit.cpp
+++ b/llvm/lib/CodeGen/SplitKit.cpp
@@ -16,7 +16,6 @@
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveRangeEdit.h"
-#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
@@ -431,13 +430,8 @@ VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
bool Late = RegIdx != 0;
// Attempt cheap-as-a-copy rematerialization.
- unsigned Original = VRM.getOriginal(Edit->get(RegIdx));
- 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, true)) {
+ if (Edit->canRematerializeAt(RM, UseIdx, true)) {
Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, TRI, Late);
++NumRemats;
} else {
@@ -722,62 +716,7 @@ SplitEditor::findShallowDominator(MachineBasicBlock *MBB,
}
}
-void SplitEditor::computeRedundantBackCopies(
- DenseSet<unsigned> &NotToHoistSet, SmallVectorImpl<VNInfo *> &BackCopies) {
- LiveInterval *LI = &LIS.getInterval(Edit->get(0));
- LiveInterval *Parent = &Edit->getParent();
- SmallVector<SmallPtrSet<VNInfo *, 8>, 8> EqualVNs(Parent->getNumValNums());
- SmallPtrSet<VNInfo *, 8> DominatedVNIs;
-
- // Aggregate VNIs having the same value as ParentVNI.
- for (VNInfo *VNI : LI->valnos) {
- if (VNI->isUnused())
- continue;
- VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
- EqualVNs[ParentVNI->id].insert(VNI);
- }
-
- // For VNI aggregation of each ParentVNI, collect dominated, i.e.,
- // redundant VNIs to BackCopies.
- for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
- VNInfo *ParentVNI = Parent->getValNumInfo(i);
- if (!NotToHoistSet.count(ParentVNI->id))
- continue;
- SmallPtrSetIterator<VNInfo *> It1 = EqualVNs[ParentVNI->id].begin();
- SmallPtrSetIterator<VNInfo *> It2 = It1;
- for (; It1 != EqualVNs[ParentVNI->id].end(); ++It1) {
- It2 = It1;
- for (++It2; It2 != EqualVNs[ParentVNI->id].end(); ++It2) {
- if (DominatedVNIs.count(*It1) || DominatedVNIs.count(*It2))
- continue;
-
- MachineBasicBlock *MBB1 = LIS.getMBBFromIndex((*It1)->def);
- MachineBasicBlock *MBB2 = LIS.getMBBFromIndex((*It2)->def);
- if (MBB1 == MBB2) {
- DominatedVNIs.insert((*It1)->def < (*It2)->def ? (*It2) : (*It1));
- } else if (MDT.dominates(MBB1, MBB2)) {
- DominatedVNIs.insert(*It2);
- } else if (MDT.dominates(MBB2, MBB1)) {
- DominatedVNIs.insert(*It1);
- }
- }
- }
- if (!DominatedVNIs.empty()) {
- forceRecompute(0, ParentVNI);
- for (auto VNI : DominatedVNIs) {
- BackCopies.push_back(VNI);
- }
- DominatedVNIs.clear();
- }
- }
-}
-
-/// For SM_Size mode, find a common dominator for all the back-copies for
-/// the same ParentVNI and hoist the backcopies to the dominator BB.
-/// For SM_Speed mode, if the common dominator is hot and it is not beneficial
-/// to do the hoisting, simply remove the dominated backcopies for the same
-/// ParentVNI.
-void SplitEditor::hoistCopies() {
+void SplitEditor::hoistCopiesForSize() {
// Get the complement interval, always RegIdx 0.
LiveInterval *LI = &LIS.getInterval(Edit->get(0));
LiveInterval *Parent = &Edit->getParent();
@@ -786,11 +725,6 @@ void SplitEditor::hoistCopies() {
// indexed by ParentVNI->id.
typedef std::pair<MachineBasicBlock*, SlotIndex> DomPair;
SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums());
- // The total cost of all the back-copies for each ParentVNI.
- SmallVector<BlockFrequency, 8> Costs(Parent->getNumValNums());
- // The ParentVNI->id set for which hoisting back-copies are not beneficial
- // for Speed.
- DenseSet<unsigned> NotToHoistSet;
// Find the nearest common dominator for parent values with multiple
// back-copies. If a single back-copy dominates, put it in DomPair.second.
@@ -806,7 +740,6 @@ void SplitEditor::hoistCopies() {
continue;
MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def);
-
DomPair &Dom = NearestDom[ParentVNI->id];
// Keep directly defined parent values. This is either a PHI or an
@@ -841,7 +774,6 @@ void SplitEditor::hoistCopies() {
else if (Near != Dom.first)
// None dominate. Hoist to common dominator, need new def.
Dom = DomPair(Near, SlotIndex());
- Costs[ParentVNI->id] += MBFI.getBlockFreq(ValMBB);
}
DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@' << VNI->def
@@ -860,11 +792,6 @@ void SplitEditor::hoistCopies() {
MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def);
// Get a less loopy dominator than Dom.first.
Dom.first = findShallowDominator(Dom.first, DefMBB);
- if (SpillMode == SM_Speed &&
- MBFI.getBlockFreq(Dom.first) > Costs[ParentVNI->id]) {
- NotToHoistSet.insert(ParentVNI->id);
- continue;
- }
SlotIndex Last = LIS.getMBBEndIdx(Dom.first).getPrevSlot();
Dom.second =
defFromParent(0, ParentVNI, Last, *Dom.first,
@@ -879,18 +806,11 @@ void SplitEditor::hoistCopies() {
continue;
VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
const DomPair &Dom = NearestDom[ParentVNI->id];
- if (!Dom.first || Dom.second == VNI->def ||
- NotToHoistSet.count(ParentVNI->id))
+ if (!Dom.first || Dom.second == VNI->def)
continue;
BackCopies.push_back(VNI);
forceRecompute(0, ParentVNI);
}
-
- // If it is not beneficial to hoist all the BackCopies, simply remove
- // redundant BackCopies in speed mode.
- if (SpillMode == SM_Speed && !NotToHoistSet.empty())
- computeRedundantBackCopies(NotToHoistSet, BackCopies);
-
removeBackCopies(BackCopies);
}
@@ -1084,8 +1004,6 @@ void SplitEditor::deleteRematVictims() {
// Dead defs end at the dead slot.
if (S.end != S.valno->def.getDeadSlot())
continue;
- if (S.valno->isPHIDef())
- continue;
MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def);
assert(MI && "Missing instruction for dead def");
MI->addRegisterDead(LI->reg, &TRI);
@@ -1130,9 +1048,10 @@ void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) {
// Leave all back-copies as is.
break;
case SM_Size:
+ hoistCopiesForSize();
+ break;
case SM_Speed:
- // hoistCopies will behave differently between size and speed.
- hoistCopies();
+ llvm_unreachable("Spill mode 'speed' not implemented yet");
}
// Transfer the simply mapped values, check if any are skipped.
diff --git a/llvm/lib/CodeGen/SplitKit.h b/llvm/lib/CodeGen/SplitKit.h
index 6bff9e882a4..69c65ff3f61 100644
--- a/llvm/lib/CodeGen/SplitKit.h
+++ b/llvm/lib/CodeGen/SplitKit.h
@@ -18,7 +18,6 @@
#include "LiveRangeCalc.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/IntervalMap.h"
#include "llvm/ADT/SmallPtrSet.h"
@@ -330,14 +329,9 @@ private:
MachineBasicBlock *findShallowDominator(MachineBasicBlock *MBB,
MachineBasicBlock *DefMBB);
- /// Find out all the backCopies dominated by others.
- void computeRedundantBackCopies(DenseSet<unsigned> &NotToHoistSet,
- SmallVectorImpl<VNInfo *> &BackCopies);
-
- /// Hoist back-copies to the complement interval. It tries to hoist all
- /// the back-copies to one BB if it is beneficial, or else simply remove
- /// redundent backcopies dominated by others.
- void hoistCopies();
+ /// hoistCopiesForSize - Hoist back-copies to the complement interval in a
+ /// way that minimizes code size. This implements the SM_Size spill mode.
+ void hoistCopiesForSize();
/// transferValues - Transfer values to the new ranges.
/// Return true if any ranges were skipped.
OpenPOWER on IntegriCloud