RegAllocPBQP.cpp | Explore in Territory

//===- RegAllocPBQP.cpp ---- PBQP Register Allocator ----------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// 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.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/RegAllocPBQP.h"
#include "RegisterCoalescer.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/CalcSpillWeights.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/LiveRangeEdit.h"
#include "llvm/CodeGen/LiveStacks.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/PBQP/Graph.h"
#include "llvm/CodeGen/PBQP/Math.h"
#include "llvm/CodeGen/PBQP/Solution.h"
#include "llvm/CodeGen/PBQPRAConstraint.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/CodeGen/Spiller.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/CodeGen/VirtRegMap.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Module.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/FileSystem.h"
#include "llvm/Support/Printable.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <system_error>
#include <tuple>
#include <utility>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE …

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);

#ifndef NDEBUG
static cl::opt<bool>
PBQPDumpGraphs("pbqp-dump-graphs",
               cl::desc("Dump graphs for each function/round in the compilation unit."),
               cl::init(false), cl::Hidden);
#endif

namespace {

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

char RegAllocPBQP::ID = …;

/// Set spill costs for each node in the PBQP reg-alloc graph.
class SpillCosts : public PBQPRAConstraint { … };

/// Add interference edges between overlapping vregs.
class Interference : public PBQPRAConstraint { … };

class Coalescing : public PBQPRAConstraint { … };

/// PBQP-specific implementation of weight normalization.
class PBQPVirtRegAuxInfo final : public VirtRegAuxInfo { … };
} // end anonymous namespace

// Out-of-line destructor/anchor for PBQPRAConstraint.
PBQPRAConstraint::~PBQPRAConstraint() = default;

void PBQPRAConstraint::anchor() { … }

void PBQPRAConstraintList::anchor() { … }

void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const { … }

void RegAllocPBQP::findVRegIntervalsToAlloc(const MachineFunction &MF,
                                            LiveIntervals &LIS) { … }

static bool isACalleeSavedRegister(MCRegister Reg,
                                   const TargetRegisterInfo &TRI,
                                   const MachineFunction &MF) { … }

void RegAllocPBQP::initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM,
                                   Spiller &VRegSpiller) { … }

void RegAllocPBQP::spillVReg(Register VReg,
                             SmallVectorImpl<Register> &NewIntervals,
                             MachineFunction &MF, LiveIntervals &LIS,
                             VirtRegMap &VRM, Spiller &VRegSpiller) { … }

bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAGraph &G,
                                     const PBQP::Solution &Solution,
                                     VirtRegMap &VRM,
                                     Spiller &VRegSpiller) { … }

void RegAllocPBQP::finalizeAlloc(MachineFunction &MF,
                                 LiveIntervals &LIS,
                                 VirtRegMap &VRM) const { … }

void RegAllocPBQP::postOptimization(Spiller &VRegSpiller, LiveIntervals &LIS) { … }

bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { … }

/// Create Printable object for node and register info.
static Printable PrintNodeInfo(PBQP::RegAlloc::PBQPRAGraph::NodeId NId,
                               const PBQP::RegAlloc::PBQPRAGraph &G) { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void PBQP::RegAlloc::PBQPRAGraph::dump(raw_ostream &OS) const {
  for (auto NId : nodeIds()) {
    const Vector &Costs = getNodeCosts(NId);
    assert(Costs.getLength() != 0 && "Empty vector in graph.");
    OS << PrintNodeInfo(NId, *this) << ": " << Costs << '\n';
  }
  OS << '\n';

  for (auto EId : edgeIds()) {
    NodeId N1Id = getEdgeNode1Id(EId);
    NodeId N2Id = getEdgeNode2Id(EId);
    assert(N1Id != N2Id && "PBQP graphs should not have self-edges.");
    const Matrix &M = getEdgeCosts(EId);
    assert(M.getRows() != 0 && "No rows in matrix.");
    assert(M.getCols() != 0 && "No cols in matrix.");
    OS << PrintNodeInfo(N1Id, *this) << ' ' << M.getRows() << " rows / ";
    OS << PrintNodeInfo(N2Id, *this) << ' ' << M.getCols() << " cols:\n";
    OS << M << '\n';
  }
}

LLVM_DUMP_METHOD void PBQP::RegAlloc::PBQPRAGraph::dump() const {
  dump(dbgs());
}
#endif

void PBQP::RegAlloc::PBQPRAGraph::printDot(raw_ostream &OS) const { … }

FunctionPass *llvm::createPBQPRegisterAllocator(char *customPassID) { … }

FunctionPass* llvm::createDefaultPBQPRegisterAllocator() { … }
llvm/llvm/lib/CodeGen/RegAllocPBQP.cpp
