lib/CodeGen/RegAllocPBQP.cpp

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",
72                 cl::desc("Attempt coalescing during PBQP register allocation."),
85 /// PBQP based allocators solve the register allocation problem by mapping
93   /// Construct a PBQP register allocator.
104     return "PBQP Register Allocator";
107   /// PBQP analysis usage.
120   typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap;
145   /// \brief Given a solved PBQP problem maps this solution back to a register
148                          const PBQP::Solution &solution);
160 unsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::NodeId node) const {
166 PBQP::Graph::NodeId PBQPRAProblem::getNodeForVReg(unsigned vreg) const {
198   PBQP::Graph &g = p->getGraph();
249     PBQP::Graph::NodeId node =
250       g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0));
255     PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ?
256         vregLI->weight : std::numeric_limits<PBQP::PBQPNum>::min();
275         PBQP::Graph::EdgeId edge =
277                     PBQP::Matrix(vr1Allowed.size()+1, vr2Allowed.size()+1, 0));
287 void PBQPBuilder::addSpillCosts(PBQP::Vector &costVec,
288                                 PBQP::PBQPNum spillCost) {
293                                     PBQP::Matrix &costMat,
307         costMat[i + 1][j + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity();
319   PBQP::Graph &g = p->getGraph();
350       PBQP::PBQPNum cBenefit =
366           PBQP::Graph::NodeId node = p->getNodeForVReg(src);
372         PBQP::Graph::NodeId node1 = p->getNodeForVReg(dst);
373         PBQP::Graph::NodeId node2 = p->getNodeForVReg(src);
374         PBQP::Graph::EdgeId edge = g.findEdge(node1, node2);
376           edge = g.addEdge(node1, node2, PBQP::Matrix(allowed1->size() + 1,
395 void PBQPBuilderWithCoalescing::addPhysRegCoalesce(PBQP::Vector &costVec,
397                                                    PBQP::PBQPNum benefit) {
402                                     PBQP::Matrix &costMat,
405                                     PBQP::PBQPNum benefit) {
468                                      const PBQP::Solution &solution) {
475   const PBQP::Graph &g = problem.getGraph();
476   // Iterate over the nodes mapping the PBQP solution to a register
478   for (PBQP::Graph::NodeItr nodeItr = g.nodesBegin(),
560   DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getName() << "\n");
564   // * Map current regalloc problem to a PBQP problem
565   // * Solve the PBQP problem
588       DEBUG(dbgs() << "  PBQP Regalloc round " << round << ":\n");
606       PBQP::Solution solution =
607         PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve(