From 3e172254c136ce8170f17ad01f0706bd6e2e0505 Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Fri, 20 Jun 2008 21:45:16 +0000 Subject: [PATCH] Enhanced heuristic to determine the *best* register to spill. Instead of picking the register with the lowest spill weight. Consider (up to) 2 additional registers with spill weights that are close to the lowest spill weight. The one with fewest defs and uses that conflicts with the current interval (weighted by loop depth) is the spill candidate. This is not always a win, but there are much more wins than loses and wins tend to be more noticeable. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52554 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/RegAllocLinearScan.cpp | 242 +++++++++++++++++++++-------- 1 file changed, 176 insertions(+), 66 deletions(-) diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index d29f6da7fdf..f4a1c007e80 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -43,6 +43,11 @@ STATISTIC(NumIters , "Number of iterations performed"); STATISTIC(NumBacktracks, "Number of times we had to backtrack"); STATISTIC(NumCoalesce, "Number of copies coalesced"); +static cl::opt +NewHeuristic("new-spilling-heuristic", + cl::desc("Use new spilling heuristic"), + cl::init(false), cl::Hidden); + static RegisterRegAlloc linearscanRegAlloc("linearscan", " linear scan register allocator", createLinearScanRegisterAllocator); @@ -62,6 +67,7 @@ namespace { std::map OneClassForEachPhysReg; MachineFunction* mf_; + MachineRegisterInfo* mri_; const TargetMachine* tm_; const TargetRegisterInfo* tri_; const TargetInstrInfo* tii_; @@ -136,6 +142,15 @@ namespace { /// is available, or spill. void assignRegOrStackSlotAtInterval(LiveInterval* cur); + /// findIntervalsToSpill - Determine the intervals to spill for the + /// specified interval. It's passed the physical registers whose spill + /// weight is the lowest among all the registers whose live intervals + /// conflict with the interval. + void findIntervalsToSpill(LiveInterval *cur, + std::vector > &Candidates, + unsigned NumCands, + SmallVector &SpillIntervals); + /// attemptTrivialCoalescing - If a simple interval is defined by a copy, /// try allocate the definition the same register as the source register /// if the register is not defined during live time of the interval. This @@ -259,6 +274,7 @@ unsigned RALinScan::attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg) { bool RALinScan::runOnMachineFunction(MachineFunction &fn) { mf_ = &fn; + mri_ = &fn.getRegInfo(); tm_ = &fn.getTarget(); tri_ = tm_->getRegisterInfo(); tii_ = tm_->getInstrInfo(); @@ -534,6 +550,107 @@ static void addStackInterval(LiveInterval *cur, LiveStacks *ls_, SI.MergeRangesInAsValue(RI, VNI); } +/// getConflictWeight - Return the number of conflicts between cur +/// live interval and defs and uses of Reg weighted by loop depthes. +static float getConflictWeight(LiveInterval *cur, unsigned Reg, + LiveIntervals *li_, + MachineRegisterInfo *mri_, + const MachineLoopInfo *loopInfo) { + float Conflicts = 0; + for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(Reg), + E = mri_->reg_end(); I != E; ++I) { + MachineInstr *MI = &*I; + if (cur->liveAt(li_->getInstructionIndex(MI))) { + unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); + Conflicts += powf(10.0f, (float)loopDepth); + } + } + return Conflicts; +} + +/// findIntervalsToSpill - Determine the intervals to spill for the +/// specified interval. It's passed the physical registers whose spill +/// weight is the lowest among all the registers whose live intervals +/// conflict with the interval. +void RALinScan::findIntervalsToSpill(LiveInterval *cur, + std::vector > &Candidates, + unsigned NumCands, + SmallVector &SpillIntervals) { + // We have figured out the *best* register to spill. But there are other + // registers that are pretty good as well (spill weight within 3%). Spill + // the one that has fewest defs and uses that conflict with cur. + float Conflicts[3] = { 0.0f, 0.0f, 0.0f }; + SmallVector SLIs[3]; + + DOUT << "\tConsidering " << NumCands << " candidates: "; + DEBUG(for (unsigned i = 0; i != NumCands; ++i) + DOUT << tri_->getName(Candidates[i].first) << " "; + DOUT << "\n";); + + // Calculate the number of conflicts of each candidate. + for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) { + unsigned Reg = i->first->reg; + unsigned PhysReg = vrm_->getPhys(Reg); + if (!cur->overlapsFrom(*i->first, i->second)) + continue; + for (unsigned j = 0; j < NumCands; ++j) { + unsigned Candidate = Candidates[j].first; + if (tri_->regsOverlap(PhysReg, Candidate)) { + if (NumCands > 1) + Conflicts[j] += getConflictWeight(cur, Reg, li_, mri_, loopInfo); + SLIs[j].push_back(i->first); + } + } + } + + for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ++i){ + unsigned Reg = i->first->reg; + unsigned PhysReg = vrm_->getPhys(Reg); + if (!cur->overlapsFrom(*i->first, i->second-1)) + continue; + for (unsigned j = 0; j < NumCands; ++j) { + unsigned Candidate = Candidates[j].first; + if (tri_->regsOverlap(PhysReg, Candidate)) { + if (NumCands > 1) + Conflicts[j] += getConflictWeight(cur, Reg, li_, mri_, loopInfo); + SLIs[j].push_back(i->first); + } + } + } + + // Which is the best candidate? + unsigned BestCandidate = 0; + float MinConflicts = Conflicts[0]; + for (unsigned i = 1; i != NumCands; ++i) { + if (Conflicts[i] < MinConflicts) { + BestCandidate = i; + MinConflicts = Conflicts[i]; + } + } + + std::copy(SLIs[BestCandidate].begin(), SLIs[BestCandidate].end(), + std::back_inserter(SpillIntervals)); +} + +namespace { + struct WeightCompare { + typedef std::pair RegWeightPair; + bool operator()(const RegWeightPair &LHS, const RegWeightPair &RHS) const { + return LHS.second < RHS.second; + } + }; +} + +static bool weightsAreClose(float w1, float w2) { + if (!NewHeuristic) + return false; + + float diff = w1 - w2; + if (diff <= 0.02f) // Within 0.02f + return true; + return (diff / w2) <= 0.05f; // Within 5%. +} + /// assignRegOrStackSlotAtInterval - assign a register if one is available, or /// spill. void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) @@ -682,7 +799,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) DOUT << "no free registers\n"; // Compile the spill weights into an array that is better for scanning. - std::vector SpillWeights(tri_->getNumRegs(), 0.0); + std::vector SpillWeights(tri_->getNumRegs(), 0.0f); for (std::vector >::iterator I = SpillWeightsToAdd.begin(), E = SpillWeightsToAdd.end(); I != E; ++I) updateSpillWeights(SpillWeights, I->first, I->second, tri_); @@ -701,44 +818,56 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // Find a register to spill. float minWeight = HUGE_VALF; - unsigned minReg = cur->preference; // Try the preferred register first. - + unsigned minReg = 0; /*cur->preference*/; // Try the preferred register first. + + bool Found = false; + std::vector > RegsWeights; if (!minReg || SpillWeights[minReg] == HUGE_VALF) for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_), e = RC->allocation_order_end(*mf_); i != e; ++i) { unsigned reg = *i; - if (minWeight > SpillWeights[reg]) { - minWeight = SpillWeights[reg]; - minReg = reg; - } + float regWeight = SpillWeights[reg]; + if (minWeight > regWeight) + Found = true; + RegsWeights.push_back(std::make_pair(reg, regWeight)); } // If we didn't find a register that is spillable, try aliases? - if (!minReg) { + if (!Found) { for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_), e = RC->allocation_order_end(*mf_); i != e; ++i) { unsigned reg = *i; // No need to worry about if the alias register size < regsize of RC. // We are going to spill all registers that alias it anyway. - for (const unsigned* as = tri_->getAliasSet(reg); *as; ++as) { - if (minWeight > SpillWeights[*as]) { - minWeight = SpillWeights[*as]; - minReg = *as; - } - } + for (const unsigned* as = tri_->getAliasSet(reg); *as; ++as) + RegsWeights.push_back(std::make_pair(*as, SpillWeights[*as])); } + } + // Sort all potential spill candidates by weight. + std::sort(RegsWeights.begin(), RegsWeights.end(), WeightCompare()); + minReg = RegsWeights[0].first; + minWeight = RegsWeights[0].second; + if (minWeight == HUGE_VALF) { // All registers must have inf weight. Just grab one! - if (!minReg) { - minReg = BestPhysReg ? BestPhysReg : *RC->allocation_order_begin(*mf_); - if (cur->weight == HUGE_VALF || cur->getSize() == 1) - // Spill a physical register around defs and uses. - li_->spillPhysRegAroundRegDefsUses(*cur, minReg, *vrm_); - } + minReg = BestPhysReg ? BestPhysReg : *RC->allocation_order_begin(*mf_); + if (cur->weight == HUGE_VALF || cur->getSize() == 1) + // Spill a physical register around defs and uses. + li_->spillPhysRegAroundRegDefsUses(*cur, minReg, *vrm_); } - - DOUT << "\t\tregister with min weight: " - << tri_->getName(minReg) << " (" << minWeight << ")\n"; + + // Find up to 3 registers to consider as spill candidates. + unsigned LastCandidate = RegsWeights.size() >= 3 ? 3 : 1; + while (LastCandidate > 1) { + if (weightsAreClose(RegsWeights[LastCandidate-1].second, minWeight)) + break; + --LastCandidate; + } + + DOUT << "\t\tregister(s) with min weight(s): "; + DEBUG(for (unsigned i = 0; i != LastCandidate; ++i) + DOUT << tri_->getName(RegsWeights[i].first) + << " (" << RegsWeights[i].second << ")\n"); // if the current has the minimum weight, we need to spill it and // add any added intervals back to unhandled, and restart @@ -767,60 +896,41 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // should go back right in the front of the list unhandled_.push(cur); - // otherwise we spill all intervals aliasing the register with - // minimum weight, rollback to the interval with the earliest - // start point and let the linear scan algorithm run again - std::vector added; assert(TargetRegisterInfo::isPhysicalRegister(minReg) && "did not choose a register to spill?"); - BitVector toSpill(tri_->getNumRegs()); - // We are going to spill minReg and all its aliases. - toSpill[minReg] = true; - for (const unsigned* as = tri_->getAliasSet(minReg); *as; ++as) - toSpill[*as] = true; + // We spill all intervals aliasing the register with + // minimum weight, rollback to the interval with the earliest + // start point and let the linear scan algorithm run again + SmallVector spillIs; + + // Determine which intervals have to be spilled. + findIntervalsToSpill(cur, RegsWeights, LastCandidate, spillIs); - // the earliest start of a spilled interval indicates up to where + // Set of spilled vregs (used later to rollback properly) + SmallSet spilled; + + // The earliest start of a Spilled interval indicates up to where // in handled we need to roll back unsigned earliestStart = cur->beginNumber(); - // set of spilled vregs (used later to rollback properly) - SmallSet spilled; - - // spill live intervals of virtual regs mapped to the physical register we + // Spill live intervals of virtual regs mapped to the physical register we // want to clear (and its aliases). We only spill those that overlap with the // current interval as the rest do not affect its allocation. we also keep // track of the earliest start of all spilled live intervals since this will // mark our rollback point. - for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) { - unsigned reg = i->first->reg; - if (//TargetRegisterInfo::isVirtualRegister(reg) && - toSpill[vrm_->getPhys(reg)] && - cur->overlapsFrom(*i->first, i->second)) { - DOUT << "\t\t\tspilling(a): " << *i->first << '\n'; - earliestStart = std::min(earliestStart, i->first->beginNumber()); - float SSWeight; - std::vector newIs = - li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_, SSWeight); - addStackInterval(i->first, ls_, li_, SSWeight, *vrm_); - std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); - spilled.insert(reg); - } - } - for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ++i){ - unsigned reg = i->first->reg; - if (//TargetRegisterInfo::isVirtualRegister(reg) && - toSpill[vrm_->getPhys(reg)] && - cur->overlapsFrom(*i->first, i->second-1)) { - DOUT << "\t\t\tspilling(i): " << *i->first << '\n'; - earliestStart = std::min(earliestStart, i->first->beginNumber()); - float SSWeight; - std::vector newIs = - li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_, SSWeight); - addStackInterval(i->first, ls_, li_, SSWeight, *vrm_); - std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); - spilled.insert(reg); - } + std::vector added; + while (!spillIs.empty()) { + LiveInterval *sli = spillIs.back(); + spillIs.pop_back(); + DOUT << "\t\t\tspilling(a): " << *sli << '\n'; + earliestStart = std::min(earliestStart, sli->beginNumber()); + float SSWeight; + std::vector newIs = + li_->addIntervalsForSpills(*sli, loopInfo, *vrm_, SSWeight); + addStackInterval(sli, ls_, li_, SSWeight, *vrm_); + std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); + spilled.insert(sli->reg); } DOUT << "\t\trolling back to: " << earliestStart << '\n'; -- 2.34.1