Index: lib/CodeGen/InlineSpiller.cpp =================================================================== --- lib/CodeGen/InlineSpiller.cpp +++ lib/CodeGen/InlineSpiller.cpp @@ -48,8 +48,6 @@ 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 DisableHoisting("disable-spill-hoist", cl::Hidden, cl::desc("Disable inline spill hoisting")); @@ -85,53 +83,6 @@ // Values that failed to remat at some point. SmallPtrSet 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 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 SibValueMap; - SibValueMap SibValues; - // Dead defs generated during spilling. SmallVector DeadDefs; @@ -161,11 +112,7 @@ } bool isSibling(unsigned Reg); - 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*); @@ -297,463 +244,11 @@ } } - -//===----------------------------------------------------------------------===// -// 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; } -#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 (unsigned i = 0, e = SVI.Deps.size(); i != e; ++i) - OS << ' ' << SVI.Deps[i]->id << '@' << SVI.Deps[i]->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. -/// -/// @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 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 WorkList; - WorkList.insert(SVI); - - do { - SVI = WorkList.pop_back_val(); - TinyPtrVector *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 (TinyPtrVector::iterator DepI = Deps->begin(), - DepE = Deps->end(); DepI != DepE; ++DepI) { - SibValueMap::iterator DepSVI = SibValues.find(*DepI); - 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 - // - // 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. -/// -/// Determine if the value is defined by all reloads, so spilling isn't -/// necessary - the value is already in the stack slot. -/// -/// Return a defining instruction that may be a candidate for rematerialization. -/// -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, 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 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 (unsigned i = 0, e = PHIs.size(); i != e; ++i) - SibValues.insert(std::make_pair(PHIs[i], SibValueInfo(Reg, PHIs[i]))); - - // Add every PHI as a dependent of all the non-PHIs. - for (unsigned i = 0, e = NonPHIs.size(); i != e; ++i) { - VNInfo *NonPHI = NonPHIs[i]; - // 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. -/// -/// 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 i = 0, e = RegsToSpill.size(); i != e; ++i) { - unsigned Reg = RegsToSpill[i]; - 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); - VNInfo *VNI = SpillLI.getVNInfoAt(Idx.getRegSlot()); - assert(VNI && VNI->def == Idx.getRegSlot() && "Not defined by copy"); - 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. - assert(StackInt && "No stack slot assigned yet."); - LiveInterval &OrigLI = LIS.getInterval(Original); - VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx); - StackInt->MergeValueInAsValue(OrigLI, OrigVNI, StackInt->getValNumInfo(0)); - DEBUG(dbgs() << "\tmerged orig valno " << OrigVNI->id << ": " - << *StackInt << '\n'); - - // 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(SibLI, SVI.SpillVNI); - - MachineBasicBlock *MBB = LIS.getMBBFromIndex(SVI.SpillVNI->def); - MachineBasicBlock::iterator MII; - if (SVI.SpillVNI->isPHIDef()) - MII = MBB->SkipPHIsAndLabels(MBB->begin()); - else { - 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, SVI.SpillReg, false, StackSlot, - MRI.getRegClass(SVI.SpillReg), &TRI); - --MII; // Point to store instruction. - LIS.InsertMachineInstrInMaps(MII); - DEBUG(dbgs() << "\thoisted: " << SVI.SpillVNI->def << '\t' << *MII); - - ++NumSpills; - ++NumHoists; - 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) { @@ -883,9 +378,6 @@ // Use an OrigVNI from traceSiblingValue when ParentVNI is a sibling copy. LiveRangeEdit::Remat RM(ParentVNI); - 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); @@ -936,7 +428,6 @@ /// 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; @@ -1272,15 +763,7 @@ SnippetCopies.insert(MI); continue; } - if (RI.Writes) { - // 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); - continue; - } - } else { + if (!RI.Writes) { // This is a reload for a sib-reg copy. Drop spills downstream. LiveInterval &SibLI = LIS.getInterval(SibReg); eliminateRedundantSpills(SibLI, SibLI.getVNInfoAt(Idx)); @@ -1387,7 +870,6 @@ assert(DeadDefs.empty() && "Previous spill didn't remove dead defs"); collectRegsToSpill(); - analyzeSiblingValues(); reMaterializeAll(); // Remat may handle everything.