Lines Matching refs:PBQP
1 //===------ RegAllocPBQP.cpp ---- PBQP Register Allocator -------*- C++ -*-===//
10 // This file contains a Partitioned Boolean Quadratic Programming (PBQP) based
11 // register allocator for LLVM. This allocator works by constructing a PBQP
13 // solving this using a PBQP solver, and mapping the solution back to a
17 // The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned
18 // for register allocation. For more information on PBQP for register
22 // PBQP. In Proceedings of the 7th Joint Modular Languages Conference
49 #include "llvm/CodeGen/PBQP/HeuristicSolver.h"
50 #include "llvm/CodeGen/PBQP/Graph.h"
51 #include "llvm/CodeGen/PBQP/Heuristics/Briggs.h"
66 registerPBQPRepAlloc("pbqp", "PBQP register allocator",
70 pbqpCoalescing("pbqp-coalescing",
71 cl::desc("Attempt coalescing during PBQP register allocation."),
76 pbqpDumpGraphs("pbqp-dump-graphs",
84 /// PBQP based allocators solve the register allocation problem by mapping
92 /// Construct a PBQP register allocator.
106 return "PBQP Register Allocator";
109 /// PBQP analysis usage.
122 typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap;
123 typedef std::vector<PBQP::Graph::NodeItr> NodeVector;
149 /// \brief Given a solved PBQP problem maps this solution back to a register
152 const PBQP::Solution &solution);
164 unsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::ConstNodeItr node) const {
170 PBQP::Graph::NodeItr PBQPRAProblem::getNodeForVReg(unsigned vreg) const {
204 PBQP::Graph &g = p->getGraph();
308 PBQP::Graph::NodeItr node =
309 g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0));
314 PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ?
315 vregLI->weight : std::numeric_limits<PBQP::PBQPNum>::min();
334 PBQP::Graph::EdgeItr edge =
336 PBQP::Matrix(vr1Allowed.size()+1, vr2Allowed.size()+1, 0));
346 void PBQPBuilder::addSpillCosts(PBQP::Vector &costVec,
347 PBQP::PBQPNum spillCost) {
352 PBQP::Matrix &costMat,
366 costMat[i + 1][j + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity();
379 PBQP::Graph &g = p->getGraph();
410 PBQP::PBQPNum cBenefit =
426 PBQP::Graph::NodeItr node = p->getNodeForVReg(src);
432 PBQP::Graph::NodeItr node1 = p->getNodeForVReg(dst);
433 PBQP::Graph::NodeItr node2 = p->getNodeForVReg(src);
434 PBQP::Graph::EdgeItr edge = g.findEdge(node1, node2);
436 edge = g.addEdge(node1, node2, PBQP::Matrix(allowed1->size() + 1,
455 void PBQPBuilderWithCoalescing::addPhysRegCoalesce(PBQP::Vector &costVec,
457 PBQP::PBQPNum benefit) {
462 PBQP::Matrix &costMat,
465 PBQP::PBQPNum benefit) {
517 // If this live interval is non-empty we will use pbqp to allocate it.
529 const PBQP::Solution &solution) {
536 const PBQP::Graph &g = problem.getGraph();
537 // Iterate over the nodes mapping the PBQP solution to a register
539 for (PBQP::Graph::ConstNodeItr node = g.nodesBegin(),
665 DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n");
669 // * Map current regalloc problem to a PBQP problem
670 // * Solve the PBQP problem
685 // If there are non-empty intervals allocate them using pbqp.
692 DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n");
710 PBQP::Solution solution =
711 PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve(
723 rmf->renderMachineFunction("After PBQP register allocation.", vrm);
