X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocPBQP.cpp;h=81cfd8f0bbdc8531ff1438bad486fe428756f338;hb=188a87da79f51b00522b9487ee352a50a01e5ea4;hp=63c7d3d2ddd6a626729471e87700e0b7789d7876;hpb=6699fb27091927528f9f6059c3034d566dbed623;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp index 63c7d3d2ddd..81cfd8f0bbd 100644 --- a/lib/CodeGen/RegAllocPBQP.cpp +++ b/lib/CodeGen/RegAllocPBQP.cpp @@ -32,10 +32,11 @@ #define DEBUG_TYPE "regalloc" #include "PBQP/HeuristicSolver.h" -#include "PBQP/SimpleGraph.h" +#include "PBQP/Graph.h" #include "PBQP/Heuristics/Briggs.h" #include "VirtRegMap.h" #include "VirtRegRewriter.h" +#include "llvm/CodeGen/CalcSpillWeights.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveStackAnalysis.h" #include "llvm/CodeGen/MachineFunctionPass.h" @@ -56,8 +57,13 @@ using namespace llvm; static RegisterRegAlloc -registerPBQPRepAlloc("pbqp", "PBQP register allocator.", - llvm::createPBQPRegisterAllocator); +registerPBQPRepAlloc("pbqp", "PBQP register allocator", + llvm::createPBQPRegisterAllocator); + +static cl::opt +pbqpCoalescing("pbqp-coalescing", + cl::desc("Attempt coalescing during PBQP register allocation."), + cl::init(false), cl::Hidden); namespace { @@ -65,23 +71,27 @@ namespace { /// PBQP based allocators solve the register allocation problem by mapping /// register allocation problems to Partitioned Boolean Quadratic /// Programming problems. - class VISIBILITY_HIDDEN PBQPRegAlloc : public MachineFunctionPass { + class PBQPRegAlloc : public MachineFunctionPass { public: static char ID; - + /// Construct a PBQP register allocator. - PBQPRegAlloc() : MachineFunctionPass((intptr_t)&ID) {} + PBQPRegAlloc() : MachineFunctionPass(&ID) {} /// Return the pass name. - virtual const char* getPassName() const throw() { + virtual const char* getPassName() const { return "PBQP Register Allocator"; } /// PBQP analysis usage. virtual void getAnalysisUsage(AnalysisUsage &au) const { + au.addRequired(); + au.addPreserved(); au.addRequired(); //au.addRequiredID(SplitCriticalEdgesID); + au.addRequired(); + au.addRequired(); au.addRequired(); au.addPreserved(); au.addRequired(); @@ -104,6 +114,8 @@ namespace { typedef std::set LiveIntervalSet; + typedef std::vector NodeVector; + MachineFunction *mf; const TargetMachine *tm; const TargetRegisterInfo *tri; @@ -120,6 +132,7 @@ namespace { AllowedSetMap allowedSets; LiveIntervalSet vregIntervalsToAlloc, emptyVRegIntervals; + NodeVector problemNodes; /// Builds a PBQP cost vector. @@ -164,7 +177,7 @@ namespace { /// allocation problem for this function. /// /// @return a PBQP solver object for the register allocation problem. - PBQP::SimpleGraph constructPBQPProblem(); + PBQP::Graph constructPBQPProblem(); /// \brief Adds a stack interval if the given live interval has been /// spilled. Used to support stack slot coloring. @@ -263,7 +276,7 @@ PBQP::Matrix* PBQPRegAlloc::buildInterferenceMatrix( unsigned reg2 = *a2Itr; // If the row/column regs are identical or alias insert an infinity. - if ((reg1 == reg2) || tri->areAliases(reg1, reg2)) { + if (tri->regsOverlap(reg1, reg2)) { (*m)[ri][ci] = std::numeric_limits::infinity(); isZeroMatrix = false; } @@ -398,16 +411,16 @@ PBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() { // We also need any physical regs to be allocable, coalescing with // a non-allocable register is invalid. if (srcRegIsPhysical) { - if (std::find(srcRegClass->allocation_order_begin(*mf), - srcRegClass->allocation_order_end(*mf), srcReg) == - srcRegClass->allocation_order_end(*mf)) + if (std::find(dstRegClass->allocation_order_begin(*mf), + dstRegClass->allocation_order_end(*mf), srcReg) == + dstRegClass->allocation_order_end(*mf)) continue; } if (dstRegIsPhysical) { - if (std::find(dstRegClass->allocation_order_begin(*mf), - dstRegClass->allocation_order_end(*mf), dstReg) == - dstRegClass->allocation_order_end(*mf)) + if (std::find(srcRegClass->allocation_order_begin(*mf), + srcRegClass->allocation_order_end(*mf), dstReg) == + srcRegClass->allocation_order_end(*mf)) continue; } @@ -429,6 +442,12 @@ PBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() { vniItr = srcLI->vni_begin(), vniEnd = srcLI->vni_end(); vniItr != vniEnd; ++vniItr) { + // If we find a poorly defined def we err on the side of caution. + if (!(*vniItr)->def.isValid()) { + badDef = true; + break; + } + // If we find a def that kills the coalescing opportunity then // record it and break from the loop. if (dstLI->liveAt((*vniItr)->def)) { @@ -447,9 +466,14 @@ PBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() { vniItr != vniEnd; ++vniItr) { // We want to make sure we skip the copy instruction itself. - if ((*vniItr)->copy == instr) + if ((*vniItr)->getCopy() == instr) continue; + if (!(*vniItr)->def.isValid()) { + badDef = true; + break; + } + if (srcLI->liveAt((*vniItr)->def)) { badDef = true; break; @@ -500,11 +524,10 @@ void PBQPRegAlloc::findVRegIntervalsToAlloc() { } } -PBQP::SimpleGraph PBQPRegAlloc::constructPBQPProblem() { +PBQP::Graph PBQPRegAlloc::constructPBQPProblem() { typedef std::vector LIVector; typedef std::vector RegVector; - typedef std::vector NodeVector; // This will store the physical intervals for easy reference. LIVector physIntervals; @@ -536,11 +559,15 @@ PBQP::SimpleGraph PBQPRegAlloc::constructPBQPProblem() { } // Get the set of potential coalesces. - CoalesceMap coalesces;//(findCoalesces()); + CoalesceMap coalesces; + + if (pbqpCoalescing) { + coalesces = findCoalesces(); + } // Construct a PBQP solver for this problem - PBQP::SimpleGraph problem; - NodeVector problemNodes(vregIntervalsToAlloc.size()); + PBQP::Graph problem; + problemNodes.resize(vregIntervalsToAlloc.size()); // Resize allowedSets container appropriately. allowedSets.resize(vregIntervalsToAlloc.size()); @@ -643,12 +670,7 @@ PBQP::SimpleGraph PBQPRegAlloc::constructPBQPProblem() { } } - problem.assignNodeIDs(); - assert(problem.getNumNodes() == allowedSets.size()); - for (unsigned i = 0; i < allowedSets.size(); ++i) { - assert(problem.getNodeItr(i) == problemNodes[i]); - } /* std::cerr << "Allocating for " << problem.getNumNodes() << " nodes, " << problem.getNumEdges() << " edges.\n"; @@ -673,7 +695,8 @@ void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled, if (stackInterval.getNumValNums() != 0) vni = stackInterval.getValNumInfo(0); else - vni = stackInterval.getNextValue(0, 0, false, lss->getVNInfoAllocator()); + vni = stackInterval.getNextValue( + SlotIndex(), 0, false, lss->getVNInfoAllocator()); LiveInterval &rhsInterval = lis->getInterval(spilled->reg); stackInterval.MergeRangesInAsValue(rhsInterval, vni); @@ -681,63 +704,16 @@ void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled, bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) { - static unsigned round = 0; - // Set to true if we have any spills bool anotherRoundNeeded = false; // Clear the existing allocation. vrm->clearAllVirt(); - CoalesceMap coalesces;//(findCoalesces()); - - for (unsigned i = 0; i < node2LI.size(); ++i) { - if (solution.getSelection(i) == 0) { - continue; - } - - unsigned iSel = solution.getSelection(i); - unsigned iAlloc = allowedSets[i][iSel - 1]; - - for (unsigned j = i + 1; j < node2LI.size(); ++j) { - - if (solution.getSelection(j) == 0) { - continue; - } - - unsigned jSel = solution.getSelection(j); - unsigned jAlloc = allowedSets[j][jSel - 1]; - - if ((iAlloc != jAlloc) && !tri->areAliases(iAlloc, jAlloc)) { - continue; - } - - if (node2LI[i]->overlaps(*node2LI[j])) { - if (coalesces.find(RegPair(node2LI[i]->reg, node2LI[j]->reg)) == coalesces.end()) { - DEBUG(errs() << "In round " << ++round << ":\n" - << "Bogusness in " << mf->getFunction()->getName() << "!\n" - << "Live interval " << i << " (reg" << node2LI[i]->reg << ") and\n" - << "Live interval " << j << " (reg" << node2LI[j]->reg << ")\n" - << " were allocated registers " << iAlloc << " (index " << iSel << ") and " - << jAlloc << "(index " << jSel - << ") respectively in a graph of " << solution.numNodes() << " nodes.\n" - << "li[i]->empty() = " << node2LI[i]->empty() << "\n" - << "li[j]->empty() = " << node2LI[j]->empty() << "\n" - << "li[i]->overlaps(li[j]) = " << node2LI[i]->overlaps(*node2LI[j]) << "\n" - << "coalesce = " << (coalesces.find(RegPair(node2LI[i]->reg, node2LI[j]->reg)) != coalesces.end()) << "\n"); - - DEBUG(errs() << "solution.getCost() = " << solution.getCost() << "\n"); - exit(1); - } - } - } - } - - // Iterate over the nodes mapping the PBQP solution to a register assignment. for (unsigned node = 0; node < node2LI.size(); ++node) { unsigned virtReg = node2LI[node]->reg, - allocSelection = solution.getSelection(node); + allocSelection = solution.getSelection(problemNodes[node]); // If the PBQP solution is non-zero it's a physical register... @@ -745,7 +721,8 @@ bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) { // Get the physical reg, subtracting 1 to account for the spill option. unsigned physReg = allowedSets[node][allocSelection - 1]; - DOUT << "VREG " << virtReg << " -> " << tri->getName(physReg) << "\n"; + DEBUG(dbgs() << "VREG " << virtReg << " -> " + << tri->getName(physReg) << "\n"); assert(physReg != 0); @@ -767,8 +744,9 @@ bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) { lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm); addStackInterval(spillInterval, mri); - DOUT << "VREG " << virtReg << " -> SPILLED (Cost: " - << oldSpillWeight << ", New vregs: "; + (void) oldSpillWeight; + DEBUG(dbgs() << "VREG " << virtReg << " -> SPILLED (Cost: " + << oldSpillWeight << ", New vregs: "); // Copy any newly inserted live intervals into the list of regs to // allocate. @@ -778,12 +756,12 @@ bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) { assert(!(*itr)->empty() && "Empty spill range."); - DOUT << (*itr)->reg << " "; + DEBUG(dbgs() << (*itr)->reg << " "); vregIntervalsToAlloc.insert(*itr); } - DOUT << ")\n"; + DEBUG(dbgs() << ")\n"); // We need another round if spill intervals were added. anotherRoundNeeded |= !newSpills.empty(); @@ -799,7 +777,7 @@ void PBQPRegAlloc::finalizeAlloc() const { // First allocate registers for the empty intervals. for (LiveIntervalSet::const_iterator - itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end(); + itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end(); itr != end; ++itr) { LiveInterval *li = *itr; @@ -867,7 +845,7 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { tm = &mf->getTarget(); tri = tm->getRegisterInfo(); tii = tm->getInstrInfo(); - mri = &mf->getRegInfo(); + mri = &mf->getRegInfo(); lis = &getAnalysis(); lss = &getAnalysis(); @@ -875,7 +853,7 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { vrm = &getAnalysis(); - DEBUG(errs() << "PBQP2 Register Allocating for " << mf->getFunction()->getName() << "\n"); + DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n"); // Allocator main loop: // @@ -889,10 +867,6 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { // Find the vreg intervals in need of allocation. findVRegIntervalsToAlloc(); - // If there aren't any then we're done here. - if (vregIntervalsToAlloc.empty() && emptyVRegIntervals.empty()) - return true; - // If there are non-empty intervals allocate them using pbqp. if (!vregIntervalsToAlloc.empty()) { @@ -900,18 +874,12 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { unsigned round = 0; while (!pbqpAllocComplete) { - DEBUG(errs() << " PBQP Regalloc round " << round << ":\n"); + DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n"); + + PBQP::Graph problem = constructPBQPProblem(); + PBQP::Solution solution = + PBQP::HeuristicSolver::solve(problem); - PBQP::SimpleGraph problem = constructPBQPProblem(); - PBQP::HeuristicSolver solver; - problem.assignNodeIDs(); - PBQP::Solution solution = solver.solve(problem); -/* - std::cerr << "Solution:\n"; - for (unsigned i = 0; i < solution.numNodes(); ++i) { - std::cerr << " " << i << " -> " << solution.getSelection(i) << "\n"; - } -*/ pbqpAllocComplete = mapPBQPToRegAlloc(solution); ++round; @@ -926,8 +894,9 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { li2Node.clear(); node2LI.clear(); allowedSets.clear(); + problemNodes.clear(); - DEBUG(errs() << "Post alloc VirtRegMap:\n" << *vrm << "\n"); + DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n"); // Run rewriter std::auto_ptr rewriter(createVirtRegRewriter());