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
48 #include "llvm/CodeGen/PBQP/Graph.h"
49 #include "llvm/CodeGen/PBQP/HeuristicSolver.h"
50 #include "llvm/CodeGen/PBQP/Heuristics/Briggs.h"
67 registerPBQPRepAlloc("pbqp", "PBQP register allocator",
71 pbqpCoalescing("pbqp-coalescing",
72 cl::desc("Attempt coalescing during PBQP register allocation."),
77 pbqpDumpGraphs("pbqp-dump-graphs",
85 /// PBQP based allocators solve the register allocation problem by mapping
93 /// Construct a PBQP register allocator.
105 return "PBQP Register Allocator";
108 /// PBQP analysis usage.
121 typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap;
146 /// \brief Given a solved PBQP problem maps this solution back to a register
149 const PBQP::Solution &solution);
161 unsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::ConstNodeItr node) const {
167 PBQP::Graph::NodeItr PBQPRAProblem::getNodeForVReg(unsigned vreg) const {
199 PBQP::Graph &g = p->getGraph();
250 PBQP::Graph::NodeItr node =
251 g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0));
256 PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ?
257 vregLI->weight : std::numeric_limits<PBQP::PBQPNum>::min();
276 PBQP::Graph::EdgeItr edge =
278 PBQP::Matrix(vr1Allowed.size()+1, vr2Allowed.size()+1, 0));
288 void PBQPBuilder::addSpillCosts(PBQP::Vector &costVec,
289 PBQP::PBQPNum spillCost) {
294 PBQP::Matrix &costMat,
308 costMat[i + 1][j + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity();
320 PBQP::Graph &g = p->getGraph();
351 PBQP::PBQPNum cBenefit =
367 PBQP::Graph::NodeItr node = p->getNodeForVReg(src);
373 PBQP::Graph::NodeItr node1 = p->getNodeForVReg(dst);
374 PBQP::Graph::NodeItr node2 = p->getNodeForVReg(src);
375 PBQP::Graph::EdgeItr edge = g.findEdge(node1, node2);
377 edge = g.addEdge(node1, node2, PBQP::Matrix(allowed1->size() + 1,
396 void PBQPBuilderWithCoalescing::addPhysRegCoalesce(PBQP::Vector &costVec,
398 PBQP::PBQPNum benefit) {
403 PBQP::Matrix &costMat,
406 PBQP::PBQPNum benefit) {
458 // If this live interval is non-empty we will use pbqp to allocate it.
470 const PBQP::Solution &solution) {
477 const PBQP::Graph &g = problem.getGraph();
478 // Iterate over the nodes mapping the PBQP solution to a register
480 for (PBQP::Graph::ConstNodeItr node = g.nodesBegin(),
558 DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getName() << "\n");
562 // * Map current regalloc problem to a PBQP problem
563 // * Solve the PBQP problem
579 // If there are non-empty intervals allocate them using pbqp.
586 DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n");
604 PBQP::Solution solution =
605 PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve(
