From e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8 Mon Sep 17 00:00:00 2001 From: Lang Hames Date: Tue, 21 Sep 2010 13:19:36 +0000 Subject: [PATCH] Added an additional PBQP problem builder which adds coalescing costs (both between pairs of virtuals, and between virtuals and physicals). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114429 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/PBQP/Heuristics/Briggs.h | 8 +- include/llvm/CodeGen/RegAllocPBQP.h | 26 +++- lib/CodeGen/RegAllocPBQP.cpp | 141 ++++++++++++++++-- 3 files changed, 158 insertions(+), 17 deletions(-) diff --git a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h index 18eaf7c0da9..47a287ccf2f 100644 --- a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h +++ b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h @@ -63,8 +63,12 @@ namespace PBQP { SpillCostComparator(HeuristicSolverImpl &s) : s(&s), g(&s.getGraph()) {} bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const { - PBQPNum cost1 = g->getNodeCosts(n1Itr)[0] / s->getSolverDegree(n1Itr), - cost2 = g->getNodeCosts(n2Itr)[0] / s->getSolverDegree(n2Itr); + const PBQP::Vector &cv1 = g->getNodeCosts(n1Itr); + const PBQP::Vector &cv2 = g->getNodeCosts(n2Itr); + + PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Itr); + PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Itr); + if (cost1 < cost2) return true; return false; diff --git a/include/llvm/CodeGen/RegAllocPBQP.h b/include/llvm/CodeGen/RegAllocPBQP.h index ee3baf36a92..2d9bac6e0d3 100644 --- a/include/llvm/CodeGen/RegAllocPBQP.h +++ b/include/llvm/CodeGen/RegAllocPBQP.h @@ -27,6 +27,7 @@ namespace llvm { class LiveInterval; class MachineFunction; + class MachineLoopInfo; /// This class wraps up a PBQP instance representing a register allocation /// problem, plus the structures necessary to map back from the PBQP solution @@ -113,7 +114,6 @@ namespace llvm { typedef std::set RegSet; - /// Default constructor. PBQPBuilder() {} @@ -125,6 +125,7 @@ namespace llvm { virtual std::auto_ptr build( MachineFunction *mf, const LiveIntervals *lis, + const MachineLoopInfo *loopInfo, const RegSet &vregs); private: @@ -136,6 +137,29 @@ namespace llvm { const TargetRegisterInfo *tri); }; + /// Extended builder which adds coalescing constraints to a problem. + class PBQPBuilderWithCoalescing : public PBQPBuilder { + public: + + /// Build a PBQP instance to represent the register allocation problem for + /// the given MachineFunction. + virtual std::auto_ptr build( + MachineFunction *mf, + const LiveIntervals *lis, + const MachineLoopInfo *loopInfo, + const RegSet &vregs); + + private: + + void addPhysRegCoalesce(PBQP::Vector &costVec, unsigned pregOption, + PBQP::PBQPNum benefit); + + void addVirtRegCoalesce(PBQP::Matrix &costMat, + const PBQPRAProblem::AllowedSet &vr1Allowed, + const PBQPRAProblem::AllowedSet &vr2Allowed, + PBQP::PBQPNum benefit); + }; + /// /// PBQP based allocators solve the register allocation problem by mapping /// register allocation problems to Partitioned Boolean Quadratic diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp index f79cadef49f..672a7d4e63b 100644 --- a/lib/CodeGen/RegAllocPBQP.cpp +++ b/lib/CodeGen/RegAllocPBQP.cpp @@ -58,9 +58,6 @@ namespace llvm { -using namespace PBQP; - using namespace PBQP::Heuristics; - static RegisterRegAlloc registerPBQPRepAlloc("pbqp", "PBQP register allocator", llvm::createPBQPRegisterAllocator); @@ -112,10 +109,10 @@ unsigned PBQPRAProblem::getPRegForOption(unsigned vreg, unsigned option) const { return allowedSet[option - 1]; } -std::auto_ptr PBQPBuilder::build( - MachineFunction *mf, - const LiveIntervals *lis, - const RegSet &vregs) { +std::auto_ptr PBQPBuilder::build(MachineFunction *mf, + const LiveIntervals *lis, + const MachineLoopInfo *loopInfo, + const RegSet &vregs) { typedef std::vector LIVector; @@ -235,10 +232,11 @@ void PBQPBuilder::addSpillCosts(PBQP::Vector &costVec, costVec[0] = spillCost; } -void PBQPBuilder::addInterferenceCosts(PBQP::Matrix &costMat, - const PBQPRAProblem::AllowedSet &vr1Allowed, - const PBQPRAProblem::AllowedSet &vr2Allowed, - const TargetRegisterInfo *tri) { +void PBQPBuilder::addInterferenceCosts( + PBQP::Matrix &costMat, + const PBQPRAProblem::AllowedSet &vr1Allowed, + const PBQPRAProblem::AllowedSet &vr2Allowed, + const TargetRegisterInfo *tri) { assert(costMat.getRows() == vr1Allowed.size() + 1 && "Matrix height mismatch."); assert(costMat.getCols() == vr2Allowed.size() + 1 && "Matrix width mismatch."); @@ -255,6 +253,115 @@ void PBQPBuilder::addInterferenceCosts(PBQP::Matrix &costMat, } } +std::auto_ptr PBQPBuilderWithCoalescing::build( + MachineFunction *mf, + const LiveIntervals *lis, + const MachineLoopInfo *loopInfo, + const RegSet &vregs) { + + std::auto_ptr p = PBQPBuilder::build(mf, lis, loopInfo, vregs); + PBQP::Graph &g = p->getGraph(); + + const TargetMachine &tm = mf->getTarget(); + CoalescerPair cp(*tm.getInstrInfo(), *tm.getRegisterInfo()); + + // Scan the machine function and add a coalescing cost whenever CoalescerPair + // gives the Ok. + for (MachineFunction::const_iterator mbbItr = mf->begin(), + mbbEnd = mf->end(); + mbbItr != mbbEnd; ++mbbItr) { + const MachineBasicBlock *mbb = &*mbbItr; + + for (MachineBasicBlock::const_iterator miItr = mbb->begin(), + miEnd = mbb->end(); + miItr != miEnd; ++miItr) { + const MachineInstr *mi = &*miItr; + + if (!mi->isCopy() && !mi->isSubregToReg()) + continue; // Not coalescable. + + if (!cp.setRegisters(mi)) + continue; // Not coalescable. + + if (cp.getSrcReg() == cp.getDstReg()) + continue; // Already coalesced. + + if (cp.isCoalescable(mi)) { + + unsigned dst = cp.getDstReg(), + src = cp.getSrcReg(); + + + + PBQP::PBQPNum cBenefit = std::pow(10.0f, loopInfo->getLoopDepth(mbb)); + + if (cp.isPhys()) { + if (!lis->isAllocatable(dst)) + continue; + + const PBQPRAProblem::AllowedSet &allowed = p->getAllowedSet(src); + unsigned pregOpt = 0; + while (pregOpt < allowed.size() && allowed[pregOpt] != dst) + ++pregOpt; + if (pregOpt < allowed.size()) { + ++pregOpt; // +1 to account for spill option. + PBQP::Graph::NodeItr node = p->getNodeForVReg(src); + addPhysRegCoalesce(g.getNodeCosts(node), pregOpt, cBenefit); + } + } else { + const PBQPRAProblem::AllowedSet *allowed1 = &p->getAllowedSet(dst); + const PBQPRAProblem::AllowedSet *allowed2 = &p->getAllowedSet(src); + PBQP::Graph::NodeItr node1 = p->getNodeForVReg(dst); + PBQP::Graph::NodeItr node2 = p->getNodeForVReg(src); + PBQP::Graph::EdgeItr edge = g.findEdge(node1, node2); + if (edge == g.edgesEnd()) { + edge = g.addEdge(node1, node2, PBQP::Matrix(allowed1->size() + 1, + allowed2->size() + 1, + 0)); + } else { + if (g.getEdgeNode1(edge) == node2) { + std::swap(node1, node2); + std::swap(allowed1, allowed2); + } + } + + addVirtRegCoalesce(g.getEdgeCosts(edge), *allowed1, *allowed2, + cBenefit); + } + } + } + } + + return p; +} + + +void PBQPBuilderWithCoalescing::addPhysRegCoalesce(PBQP::Vector &costVec, + unsigned pregOption, + PBQP::PBQPNum benefit) { + costVec[pregOption] += -benefit; +} + +void PBQPBuilderWithCoalescing::addVirtRegCoalesce( + PBQP::Matrix &costMat, + const PBQPRAProblem::AllowedSet &vr1Allowed, + const PBQPRAProblem::AllowedSet &vr2Allowed, + PBQP::PBQPNum benefit) { + + assert(costMat.getRows() == vr1Allowed.size() + 1 && "Size mismatch."); + assert(costMat.getCols() == vr2Allowed.size() + 1 && "Size mismatch."); + + for (unsigned i = 0; i < vr1Allowed.size(); ++i) { + unsigned preg1 = vr1Allowed[i]; + for (unsigned j = 0; j < vr2Allowed.size(); ++j) { + unsigned preg2 = vr2Allowed[j]; + + if (preg1 == preg2) { + costMat[i + 1][j + 1] += -benefit; + } + } + } +} void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const { @@ -1037,9 +1144,10 @@ bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n"); std::auto_ptr problem = - builder->build(mf, lis, vregsToAlloc); + builder->build(mf, lis, loopInfo, vregsToAlloc); PBQP::Solution solution = - HeuristicSolver::solve(problem->getGraph()); + PBQP::HeuristicSolver::solve( + problem->getGraph()); pbqpAllocComplete = mapPBQPToRegAlloc2(*problem, solution); @@ -1071,7 +1179,12 @@ bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { } FunctionPass* createPBQPRegisterAllocator() { - return new RegAllocPBQP(std::auto_ptr(new PBQPBuilder())); + if (pbqpCoalescing) { + return new RegAllocPBQP( + std::auto_ptr(new PBQPBuilderWithCoalescing())); + } // else + return new RegAllocPBQP( + std::auto_ptr(new PBQPBuilder())); } } -- 2.34.1