X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocPBQP.cpp;h=2701fafbf9ba8c0b503a159f8dcff3c0059293d1;hb=80dc116ce3be18be2866db8fe13f03d1d6c4372f;hp=853192ca9d2fdbda32e08d80e950520b199bf095;hpb=bc84ad95b7a4e453f6dd91f535abd7ef9ddc1773;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp index 853192ca9d2..2701fafbf9b 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" @@ -57,12 +58,12 @@ using namespace llvm; static RegisterRegAlloc registerPBQPRepAlloc("pbqp", "PBQP register allocator.", - llvm::createPBQPRegisterAllocator); + llvm::createPBQPRegisterAllocator); static cl::opt pbqpCoalescing("pbqp-coalescing", - cl::desc("Attempt coalescing during PBQP register allocation."), - cl::init(false), cl::Hidden); + cl::desc("Attempt coalescing during PBQP register allocation."), + cl::init(false), cl::Hidden); namespace { @@ -70,11 +71,11 @@ 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(&ID) {} @@ -85,9 +86,12 @@ namespace { /// 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(); @@ -110,6 +114,8 @@ namespace { typedef std::set LiveIntervalSet; + typedef std::vector NodeVector; + MachineFunction *mf; const TargetMachine *tm; const TargetRegisterInfo *tri; @@ -126,6 +132,7 @@ namespace { AllowedSetMap allowedSets; LiveIntervalSet vregIntervalsToAlloc, emptyVRegIntervals; + NodeVector problemNodes; /// Builds a PBQP cost vector. @@ -170,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. @@ -269,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; } @@ -404,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; } @@ -435,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)) { @@ -456,6 +469,11 @@ PBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() { if ((*vniItr)->getCopy() == instr) continue; + if (!(*vniItr)->def.isValid()) { + badDef = true; + break; + } + if (srcLI->liveAt((*vniItr)->def)) { badDef = true; break; @@ -506,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; @@ -549,8 +566,8 @@ PBQP::SimpleGraph PBQPRegAlloc::constructPBQPProblem() { } // 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()); @@ -653,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"; @@ -683,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); @@ -691,19 +704,16 @@ void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled, bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) { - static unsigned round = 0; - (void) round; - // Set to true if we have any spills bool anotherRoundNeeded = false; // Clear the existing allocation. vrm->clearAllVirt(); - + // 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... @@ -711,7 +721,7 @@ 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]; - DEBUG(errs() << "VREG " << virtReg << " -> " + DEBUG(dbgs() << "VREG " << virtReg << " -> " << tri->getName(physReg) << "\n"); assert(physReg != 0); @@ -735,7 +745,7 @@ bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) { addStackInterval(spillInterval, mri); (void) oldSpillWeight; - DEBUG(errs() << "VREG " << virtReg << " -> SPILLED (Cost: " + DEBUG(dbgs() << "VREG " << virtReg << " -> SPILLED (Cost: " << oldSpillWeight << ", New vregs: "); // Copy any newly inserted live intervals into the list of regs to @@ -746,12 +756,12 @@ bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) { assert(!(*itr)->empty() && "Empty spill range."); - DEBUG(errs() << (*itr)->reg << " "); + DEBUG(dbgs() << (*itr)->reg << " "); vregIntervalsToAlloc.insert(*itr); } - DEBUG(errs() << ")\n"); + DEBUG(dbgs() << ")\n"); // We need another round if spill intervals were added. anotherRoundNeeded |= !newSpills.empty(); @@ -767,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; @@ -835,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(); @@ -843,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: // @@ -868,12 +878,11 @@ 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::SimpleGraph problem = constructPBQPProblem(); - PBQP::HeuristicSolver solver; - problem.assignNodeIDs(); - PBQP::Solution solution = solver.solve(problem); + PBQP::Graph problem = constructPBQPProblem(); + PBQP::Solution solution = + PBQP::HeuristicSolver::solve(problem); pbqpAllocComplete = mapPBQPToRegAlloc(solution); @@ -889,8 +898,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());