X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FInlineSpiller.cpp;h=0c46aeb6aa1c8f15646bf776c08eae555f209252;hb=6b6e32d954233ddeeae7f99e358ff85059f1176a;hp=d5c1da9d4b0263790433a7c1d4430c0390db8f15;hpb=2c207a0f677a2d78b768acb559e6b9f6f112a50d;p=oota-llvm.git diff --git a/lib/CodeGen/InlineSpiller.cpp b/lib/CodeGen/InlineSpiller.cpp index d5c1da9d4b0..0c46aeb6aa1 100644 --- a/lib/CodeGen/InlineSpiller.cpp +++ b/lib/CodeGen/InlineSpiller.cpp @@ -120,11 +120,6 @@ private: typedef DenseMap SibValueMap; SibValueMap SibValues; - // Values live-out from basic blocks. This is the same as - // LI.getVNInfoAt(LIS.getMBBEndIdx(MBB).getPrevSlot()) - typedef DenseMap LiveOutMap; - LiveOutMap LiveOutValues; - // Dead defs generated during spilling. SmallVector DeadDefs; @@ -314,10 +309,16 @@ 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"; + 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 @@ -333,109 +334,121 @@ static raw_ostream &operator<<(raw_ostream &OS, /// @param VNI Dependent value, or NULL to propagate to all saved dependents. void InlineSpiller::propagateSiblingValue(SibValueMap::iterator SVI, VNInfo *VNI) { - SibValueInfo &SV = SVI->second; - - if (!SV.SpillMBB) - SV.SpillMBB = LIS.getMBBFromIndex(SV.SpillVNI->def); - - // Should this value be propagated as a preferred spill candidate? We don't - // propagate values of registers that are about to spill. - bool PropSpill = !isRegToSpill(SV.SpillReg); - unsigned SpillDepth = ~0u; - - // Further values that need to be updated. - SmallVector WorkList; - - // Defer propagation if the value is not known yet. + // When VNI is non-NULL, add it to SVI's deps, and only propagate to that. + TinyPtrVector FirstDeps; if (VNI) { - SV.Deps.push_back(VNI); - // Don't propagate to other dependents than VNI. SVI hasn't changed. - WorkList.push_back(VNI); - } else { - // No VNI given, update all Deps. - WorkList.append(SV.Deps.begin(), SV.Deps.end()); + FirstDeps.push_back(VNI); + SVI->second.Deps.push_back(VNI); } // Has the value been completely determined yet? If not, defer propagation. - if (!SV.hasDef()) + if (!SVI->second.hasDef()) return; - while (!WorkList.empty()) { - SibValueMap::iterator DepSVI = SibValues.find(WorkList.pop_back_val()); - assert(DepSVI != SibValues.end() && "Dependent value not in SibValues"); - SibValueInfo &DepSV = DepSVI->second; - bool Changed = false; - - if (!DepSV.SpillMBB) - DepSV.SpillMBB = LIS.getMBBFromIndex(DepSV.SpillVNI->def); + // Work list of values to propagate. It would be nice to use a SetVector + // here, but then we would be forced to use a SmallSet. + SmallVector WorkList(1, SVI); + SmallPtrSet WorkSet; - // Propagate defining instruction. - if (!DepSV.hasDef()) { - Changed = true; - DepSV.DefMI = SV.DefMI; - DepSV.DefByOrigPHI = SV.DefByOrigPHI; - } + do { + SVI = WorkList.pop_back_val(); + WorkSet.erase(SVI->first); + TinyPtrVector *Deps = VNI ? &FirstDeps : &SVI->second.Deps; + VNI = 0; + + 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 = !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 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 (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 - // - 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. - if ((Loops.getLoopDepth(DepSV.SpillMBB) > SpillDepth) && - (!DepSVI->first->isPHIDef() || - MDT.dominates(SV.SpillMBB, DepSV.SpillMBB))) { - Changed = true; - DepSV.SpillReg = SV.SpillReg; - DepSV.SpillVNI = SV.SpillVNI; - DepSV.SpillMBB = SV.SpillMBB; + // 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 (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 + // + 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. + if ((Loops.getLoopDepth(DepSV.SpillMBB) > SpillDepth) && + (!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; + if (!Changed) + continue; - // Something changed in DepSVI. Propagate to dependents. - WorkList.append(DepSV.Deps.begin(), DepSV.Deps.end()); + // Something changed in DepSVI. Propagate to dependents. + if (WorkSet.insert(DepSVI->first)) + WorkList.push_back(DepSVI); - DEBUG(dbgs() << " update " << DepSVI->first->id << '@' - << DepSVI->first->def << " to:\t" << DepSV); - } + 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 @@ -482,6 +495,7 @@ MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI, // 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. if (VNI->def == OrigVNI->def) { DEBUG(dbgs() << "orig phi value\n"); SVI->second.DefByOrigPHI = true; @@ -489,28 +503,60 @@ MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI, propagateSiblingValue(SVI); continue; } - // Get values live-out of predecessors. + + // 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); - MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); - DEBUG(dbgs() << "split phi value, check " << MBB->pred_size() - << " preds\n"); - for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), - PE = MBB->pred_end(); PI != PE; ++PI) { - // Use a cache of block live-out values. This is faster than using - // getVNInfoAt on complex intervals. - VNInfo *&PVNI = LiveOutValues[*PI]; - if (!PVNI) - PVNI = LI.getVNInfoAt(LIS.getMBBEndIdx(*PI).getPrevSlot()); - if (!PVNI) + LiveInterval &OrigLI = LIS.getInterval(Original); + + 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; - // Known predecessor value? Try an insertion. + 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. tie(SVI, Inserted) = - SibValues.insert(std::make_pair(PVNI, SibValueInfo(Reg, PVNI))); - // This is the first time we see PVNI, add it to the worklist. + SibValues.insert(std::make_pair(NonPHI, SibValueInfo(Reg, NonPHI))); + // Add all the PHIs as dependents of NonPHI. + for (unsigned pi = 0, pe = PHIs.size(); pi != pe; ++pi) + SVI->second.Deps.push_back(PHIs[pi]); + // This is the first time we see NonPHI, add it to the worklist. if (Inserted) - WorkList.push_back(std::make_pair(Reg, PVNI)); - propagateSiblingValue(SVI, VNI); + WorkList.push_back(std::make_pair(Reg, NonPHI)); + else + // Propagate to all inserted PHIs, not just VNI. + propagateSiblingValue(SVI); } + // Next work list item. continue; } @@ -569,7 +615,6 @@ MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI, /// Keep track of values that may be rematerializable. void InlineSpiller::analyzeSiblingValues() { SibValues.clear(); - LiveOutValues.clear(); // No siblings at all? if (Edit->getReg() == Original)