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>

using namespace llvm;

static RegisterRegAlloc
registerPBQPRepAlloc("pbqp", "PBQP register allocator",
                       createDefaultPBQPRegisterAllocator);

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(true), cl::Hidden);


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

namespace {

///
/// PBQP based allocators solve the register allocation problem by mapping
/// register allocation problems to Partitioned Boolean Quadratic
/// Programming problems.
class RegAllocPBQP : public MachineFunctionPass {
public:

  static char ID;

  /// Construct a PBQP register allocator.
  RegAllocPBQP(std::auto_ptr<PBQPBuilder> b) : MachineFunctionPass(ID), builder(b) {}

  /// Return the pass name.
  virtual const char* getPassName() const {
    return "PBQP Register Allocator";
  }

  /// PBQP analysis usage.
  virtual void getAnalysisUsage(AnalysisUsage &au) const;

  /// Perform register allocation
  virtual bool runOnMachineFunction(MachineFunction &MF);

private:

  typedef std::map<const LiveInterval*, unsigned> LI2NodeMap;
  typedef std::vector<const LiveInterval*> Node2LIMap;
  typedef std::vector<unsigned> AllowedSet;
  typedef std::vector<AllowedSet> AllowedSetMap;
  typedef std::pair<unsigned, unsigned> RegPair;
  typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap;
  typedef std::vector<PBQP::Graph::NodeItr> NodeVector;
  typedef std::set<unsigned> RegSet;


  std::auto_ptr<PBQPBuilder> builder;

  MachineFunction *mf;
  const TargetMachine *tm;
  const TargetRegisterInfo *tri;
  const TargetInstrInfo *tii;
  const MachineLoopInfo *loopInfo;
  MachineRegisterInfo *mri;
  RenderMachineFunction *rmf;

  LiveIntervals *lis;
  LiveStacks *lss;
  VirtRegMap *vrm;

  LI2NodeMap li2Node;
  Node2LIMap node2LI;
  AllowedSetMap allowedSets;
  RegSet vregsToAlloc, emptyIntervalVRegs;
  NodeVector problemNodes;


  /// Builds a PBQP cost vector.
  template <typename RegContainer>
  PBQP::Vector buildCostVector(unsigned vReg,
                               const RegContainer &allowed,
                               const CoalesceMap &cealesces,
                               PBQP::PBQPNum spillCost) const;

  /// \brief Builds a PBQP interference matrix.
  ///
  /// @return Either a pointer to a non-zero PBQP matrix representing the
  ///         allocation option costs, or a null pointer for a zero matrix.
  ///
  /// Expects allowed sets for two interfering LiveIntervals. These allowed
  /// sets should contain only allocable registers from the LiveInterval's
  /// register class, with any interfering pre-colored registers removed.
  template <typename RegContainer>
  PBQP::Matrix* buildInterferenceMatrix(const RegContainer &allowed1,
                                        const RegContainer &allowed2) const;

  ///
  /// Expects allowed sets for two potentially coalescable LiveIntervals,
  /// and an estimated benefit due to coalescing. The allowed sets should
  /// contain only allocable registers from the LiveInterval's register
  /// classes, with any interfering pre-colored registers removed.
  template <typename RegContainer>
  PBQP::Matrix* buildCoalescingMatrix(const RegContainer &allowed1,
                                      const RegContainer &allowed2,
                                      PBQP::PBQPNum cBenefit) const;

  /// \brief Finds coalescing opportunities and returns them as a map.
  ///
  /// Any entries in the map are guaranteed coalescable, even if their
  /// corresponding live intervals overlap.
  CoalesceMap findCoalesces();

  /// \brief Finds the initial set of vreg intervals to allocate.
  void findVRegIntervalsToAlloc();

  /// \brief Constructs a PBQP problem representation of the register
  /// allocation problem for this function.
  ///
  /// Old Construction Process - this functionality has been subsumed
  /// by PBQPBuilder. This function will only be hanging around for a little
  /// while until the new system has been fully tested.
  /// 
  /// @return a PBQP solver object for the register allocation problem.
  PBQP::Graph constructPBQPProblemOld();

  /// \brief Adds a stack interval if the given live interval has been
  /// spilled. Used to support stack slot coloring.
  void addStackInterval(const LiveInterval *spilled,MachineRegisterInfo* mri);

  /// \brief Given a solved PBQP problem maps this solution back to a register
  /// assignment.
  ///
  /// Old Construction Process - this functionality has been subsumed
  /// by PBQPBuilder. This function will only be hanging around for a little
  /// while until the new system has been fully tested.
  /// 
  bool mapPBQPToRegAllocOld(const PBQP::Solution &solution);

  /// \brief Given a solved PBQP problem maps this solution back to a register