RegAllocPBQP.cpp

//===------ RegAllocPBQP.cpp ---- PBQP Register Allocator -------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file contains a Partitioned Boolean Quadratic Programming (PBQP) based
// register allocator for LLVM. This allocator works by constructing a PBQP
// problem representing the register allocation problem under consideration,
// solving this using a PBQP solver, and mapping the solution back to a
// register assignment. If any variables are selected for spilling then spill
// code is inserted and the process repeated.
//
// The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned
// for register allocation. For more information on PBQP for register
// allocation, see the following papers:
//
//   (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with
//   PBQP. In Proceedings of the 7th Joint Modular Languages Conference
//   (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361.
//
//   (2) Scholz, B., Eckstein, E. 2002. Register allocation for irregular
//   architectures. In Proceedings of the Joint Conference on Languages,
//   Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New York,
//   NY, USA, 139-148.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "regalloc"

#include "RenderMachineFunction.h"
#include "Splitter.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/RegAllocPBQP.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/PBQP/HeuristicSolver.h"
#include "llvm/CodeGen/PBQP/Graph.h"
#include "llvm/CodeGen/PBQP/Heuristics/Briggs.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
#include "llvm/CodeGen/RegisterCoalescer.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include <limits>
#include <memory>
#include <set>
#include <vector>

namespace llvm {

static RegisterRegAlloc
registerPBQPRepAlloc("pbqp", "PBQP register allocator",
                       llvm::createPBQPRegisterAllocator);

static cl::opt<bool>
pbqpCoalescing("pbqp-coalescing",
                cl::desc("Attempt coalescing during PBQP register allocation."),
                cl::init(false), cl::Hidden);

static cl::opt<bool>
pbqpBuilder("pbqp-builder",
                cl::desc("Use new builder system."),
                cl::init(false), cl::Hidden);


static cl::opt<bool>
pbqpPreSplitting("pbqp-pre-splitting",
                 cl::desc("Pre-splite before PBQP register allocation."),
                 cl::init(false), cl::Hidden);

char RegAllocPBQP::ID = 0;

unsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::ConstNodeItr node) const {
  Node2VReg::const_iterator vregItr = node2VReg.find(node);
  assert(vregItr != node2VReg.end() && "No vreg for node.");
  return vregItr->second;
}

PBQP::Graph::NodeItr PBQPRAProblem::getNodeForVReg(unsigned vreg) const {
  VReg2Node::const_iterator nodeItr = vreg2Node.find(vreg);
  assert(nodeItr != vreg2Node.end() && "No node for vreg.");
  return nodeItr->second;
  
}

const PBQPRAProblem::AllowedSet&
  PBQPRAProblem::getAllowedSet(unsigned vreg) const {
  AllowedSetMap::const_iterator allowedSetItr = allowedSets.find(vreg);
  assert(allowedSetItr != allowedSets.end() && "No pregs for vreg.");
  const AllowedSet &allowedSet = allowedSetItr->second;
  return allowedSet;
}

unsigned PBQPRAProblem::getPRegForOption(unsigned vreg, unsigned option) const {
  assert(isPRegOption(vreg, option) && "Not a preg option.");

  const AllowedSet& allowedSet = getAllowedSet(vreg);
  assert(option <= allowedSet.size() && "Option outside allowed set.");
  return allowedSet[option - 1];
}

std::auto_ptr<PBQPRAProblem> PBQPBuilder::build(MachineFunction *mf,
                                                const LiveIntervals *lis,
                                                const MachineLoopInfo *loopInfo,
                                                const RegSet &vregs) {

  typedef std::vector<const LiveInterval*> LIVector;

  MachineRegisterInfo *mri = &mf->getRegInfo();
  const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo();  

  std::auto_ptr<PBQPRAProblem> p(new PBQPRAProblem());
  PBQP::Graph &g = p->getGraph();
  RegSet pregs;

  // Collect the set of preg intervals, record that they're used in the MF.
  for (LiveIntervals::const_iterator itr = lis->begin(), end = lis->end();
       itr != end; ++itr) {
    if (TargetRegisterInfo::isPhysicalRegister(itr->first)) {
      pregs.insert(itr->first);
      mri->setPhysRegUsed(itr->first);
    }
  }

  BitVector reservedRegs = tri->getReservedRegs(*mf);

  // Iterate over vregs. 
  for (RegSet::const_iterator vregItr = vregs.begin(), vregEnd = vregs.end();
       vregItr != vregEnd; ++vregItr) {
    unsigned vreg = *vregItr;
    const TargetRegisterClass *trc = mri->getRegClass(vreg);
    const LiveInterval *vregLI = &lis->getInterval(vreg);

    // Compute an initial allowed set for the current vreg.
    typedef std::vector<unsigned> VRAllowed;
    VRAllowed vrAllowed;
    for (TargetRegisterClass::iterator aoItr = trc->allocation_order_begin(*mf),
                                       aoEnd = trc->allocation_order_end(*mf);
         aoItr != aoEnd; ++aoItr) {
      unsigned preg = *aoItr;
      if (!reservedRegs.test(preg)) {
        vrAllowed.push_back(preg);
      }
    }

    // Remove any physical registers which overlap.
    for (RegSet::const_iterator pregItr = pregs.begin(),
                                pregEnd = pregs.end();
         pregItr != pregEnd; ++pregItr) {
      unsigned preg = *pregItr;
      const LiveInterval *pregLI = &lis->getInterval(preg);

      if (pregLI->empty())
        continue;

      if (!vregLI->overlaps(*pregLI))
        continue;

      // Remove the register from the allowed set.
      VRAllowed::iterator eraseItr =
        std::find(vrAllowed.begin(), vrAllowed.end(), preg);

      if (eraseItr != vrAllowed.end()) {
        vrAllowed.erase(eraseItr);
      }

      // Also remove any aliases.
      const unsigned *aliasItr = tri->getAliasSet(preg);
      if (aliasItr != 0) {
        for (; *aliasItr != 0; ++aliasItr) {
          VRAllowed::iterator eraseItr =
            std::find(vrAllowed.begin(), vrAllowed.end(), *aliasItr);

          if (eraseItr != vrAllowed.end()) {
            vrAllowed.erase(eraseItr);
          }
        }
      }
    }

    // Construct the node.
    PBQP::Graph::NodeItr node = 
      g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0));

    // Record the mapping and allowed set in the problem.
    p->recordVReg(vreg, node, vrAllowed.begin(), vrAllowed.end());

    PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ?
        vregLI->weight : std::numeric_limits<PBQP::PBQPNum>::min();