X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocPBQP.cpp;h=81cfd8f0bbdc8531ff1438bad486fe428756f338;hb=99be8ae3898d87373ef0c8f1159b287e28a8d81b;hp=33d82d0cefb2d6ec84d9873514299f81b163c766;hpb=a279bc3da55691784064cb47200a1c584408b8ab;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp index 33d82d0cefb..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,13 +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); + cl::desc("Attempt coalescing during PBQP register allocation."), + cl::init(false), cl::Hidden); namespace { @@ -70,7 +71,7 @@ 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; @@ -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. @@ -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"; @@ -684,13 +696,14 @@ void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled, vni = stackInterval.getValNumInfo(0); else vni = stackInterval.getNextValue( - MachineInstrIndex(), 0, false, lss->getVNInfoAllocator()); + SlotIndex(), 0, false, lss->getVNInfoAllocator()); LiveInterval &rhsInterval = lis->getInterval(spilled->reg); stackInterval.MergeRangesInAsValue(rhsInterval, vni); } bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) { + // Set to true if we have any spills bool anotherRoundNeeded = false; @@ -700,7 +713,7 @@ bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) { // 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... @@ -708,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); @@ -732,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 @@ -743,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(); @@ -832,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(); @@ -840,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: // @@ -854,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()) { @@ -865,12 +874,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); @@ -886,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());