<commit_before>//===------ 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) <NAME>. and <NAME>. 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) <NAME>., <NAME>. 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 "Spiller.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/CalcSpillWeights.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveRangeEdit.h"
#include "llvm/CodeGen/LiveStackAnalysis.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
#include "llvm/CodeGen/VirtRegMap.h"
#include "llvm/IR/Module.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/FileSystem.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
#include <limits>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <vector>

using namespace llvm;

#define DEBUG_TYPE "regalloc"

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 {
public:

  static char ID;

  /// Construct a PBQP register allocator.
  RegAllocPBQP(char *cPassID = nullptr)
      : MachineFunctionPass(ID), customPassID(cPassID) {
    initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
    initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
    initializeLiveStacksPass(*PassRegistry::getPassRegistry());
    initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
  }

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

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

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

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::set<unsigned> RegSet;

  char *customPassID;

  RegSet VRegsToAlloc, EmptyIntervalVRegs;

  /// \brief Finds the initial set of vreg intervals to allocate.
  void findVRegIntervalsToAlloc(const MachineFunction &MF, LiveIntervals &LIS);

  /// \brief Constructs an initial graph.
  void initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM, Spiller &VRegSpiller);

  /// \brief Spill the given VReg.
  void spillVReg(unsigned VReg, SmallVectorImpl<unsigned> &NewIntervals,
                 MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM,
                 Spiller &VRegSpiller);

  /// \brief Given a solved PBQP problem maps this solution back to a register
  /// assignment.
  bool mapPBQPToRegAlloc(const PBQPRAGraph &G,
                         const PBQP::Solution &Solution,
                         VirtRegMap &VRM,
                         Spiller &VRegSpiller);

  /// \brief Postprocessing before final spilling. Sets basic block "live in"
  /// variables.
  void finalizeAlloc(MachineFunction &MF, LiveIntervals &LIS,
                     VirtRegMap &VRM) const;

};

char RegAllocPBQP::ID = 0;

/// @brief Set spill costs for each node in the PBQP reg-alloc graph.
class SpillCosts : public PBQPRAConstraint {
public:
  void apply(PBQPRAGraph &G) override {
    LiveIntervals &LIS = G.getMetadata().LIS;

    // A minimum spill costs, so that register constraints can can be set
    // without normalization in the [0.0:MinSpillCost( interval.
    const PBQP::PBQPNum MinSpillCost = 10.0;

    for (auto NId : G.nodeIds()) {
      PBQP::PBQPNum SpillCost =
        LIS.getInterval(G.getNodeMetadata(NId).getVReg()).weight;
      if (SpillCost == 0.0)
        SpillCost = std::numeric_limits<PBQP::PBQPNum>::min();
      else
        SpillCost += MinSpillCost;
      PBQPRAGraph::RawVector NodeCosts(G.getNodeCosts(NId));
      NodeCosts[PBQP::RegAlloc::getSpillOptionIdx()] = SpillCost;
      G.setNodeCosts(NId, std::move(NodeCosts));
    }
  }
};

/// @brief Add interference edges between overlapping vregs.
class Interference : public PBQPRAConstraint {
private:

  typedef const PBQP::RegAlloc::AllowedRegVector* AllowedRegVecPtr;
  typedef std::pair<AllowedRegVecPtr, AllowedRegVecPtr> IKey;
  typedef DenseMap<IKey, PBQPRAGraph::MatrixPtr> IMatrixCache;
  typedef DenseSet<IKey> DisjointAllowedRegsCache;

  bool haveDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId,
                               PBQPRAGraph::NodeId MId,
                               const DisjointAllowedRegsCache &D) const {
    const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs();
    const auto *MRegs = &G.getNodeMetadata(MId).getAllowedRegs();

    if (NRegs == MRegs)
      return false;

    if (NRegs < MRegs)
      return D.count(IKey(NRegs, MRegs)) > 0;

    return D.count(IKey(MRegs, NRegs)) > 0;
  }

  void setDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId,
                              PBQPRAGraph::NodeId MId,
                              DisjointAllowedRegsCache &D) {
    const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs();
    const auto *MRegs = &G.getNodeMetadata(MId).getAllowedRegs();

    assert(NRegs != MRegs && "AllowedRegs can not be disjoint with itself");

    if (NRegs < MRegs)
      D.insert(IKey(NRegs, MRegs));
    else
      D.insert(IKey(MRegs, NRegs));
  }

  // Holds (Interval, CurrentSegmentID, and NodeId). The first two are required
  // for the fast interference graph construction algorithm. The last is there
  // to save us from looking up node ids via the VRegToNode map in the graph
  // metadata.
  typedef std::tuple<LiveInterval*, size_t, PBQP::GraphBase::NodeId>
    IntervalInfo;

  static SlotIndex getStartPoint(const IntervalInfo &I) {
    return std::get<0>(I)->segments[std::get<1>(I)].start;
  }

  static SlotIndex getEndPoint(const IntervalInfo &I) {
    return std::get<0>(I)->segments[std::get<1>(I)].end;
  }

  static PBQP::GraphBase::NodeId getNodeId(const IntervalInfo &I) {
    return std::get<2>(I);
  }

  static bool lowestStartPoint(const IntervalInfo &I1,
                               const IntervalInfo &I2) {
    // Condition reversed because priority queue has the *highest* element at
    // the front, rather than the lowest.
    return getStartPoint(I1) > getStartPoint(I2);
  }

  static bool lowestEndPoint(const IntervalInfo &I1,
                             const IntervalInfo &I2) {
    SlotIndex E1 = getEndPoint(I1);
    SlotIndex E2 = getEndPoint(I2);

    if (E1 < E2)
      return true;

    if (E1 > E2)
      return false;

    // If two intervals end at the same point, we need a way to break the tie or
    // the set will assume they're actually equal and refuse to insert a
    // "duplicate". Just compare the vregs - fast and guaranteed unique.
    return std::get<0>(I1)->reg < std::get<0>(I2)->reg;
  }

  static bool isAtLastSegment(const IntervalInfo &I) {
    return std::get<1>(I) == std::get<0>(I)->size() - 1;
  }

  static IntervalInfo nextSegment(const IntervalInfo &I) {
    return std::make_tuple(std::get<0>(I), std::get<1>(I) + 1, std::get<2>(I));
  }

public:

  void apply(PBQPRAGraph &G) override {
    // The following is loosely based on the linear scan algorithm introduced in
    // "Linear Scan Register Allocation" by Poletto and Sarkar. This version
    // isn't linear, because the size of the active set isn't bound by the
    // number of registers, but rather the size of the largest clique in the
    // graph. Still, we expect this to be better than N^2.
    LiveIntervals &LIS = G.getMetadata().LIS;

    // Interferenc matrices are incredibly regular - they're only a function of
    // the allowed sets, so we cache them to avoid the overhead of constructing
    // and uniquing them.
    IMatrixCache C;

    // Cache known disjoint allowed registers pairs
    DisjointAllowedRegsCache D;

    typedef std::set<IntervalInfo, decltype(&lowestEndPoint)> IntervalSet;
    typedef std::priority_queue<IntervalInfo, std::vector<IntervalInfo>,
                                decltype(&lowestStartPoint)> IntervalQueue;
    IntervalSet Active(lowestEndPoint);
    IntervalQueue Inactive(lowestStartPoint);

    // Start by building the inactive set.
    for (auto NId : G.nodeIds()) {
      unsigned VReg = G.getNodeMetadata(NId).getVReg();
      LiveInterval &LI = LIS.getInterval(VReg);
      assert(!LI.empty() && "PBQP graph contains node for empty interval");
      Inactive.push(std::make_tuple(&LI, 0, NId));
    }

    while (!Inactive.empty()) {
      // Tentatively grab the "next" interval - this choice may be overriden
      // below.
      IntervalInfo Cur = Inactive.top();

      // Retire any active intervals that end before Cur starts.
      IntervalSet::iterator RetireItr = Active.begin();
      while (RetireItr != Active.end() &&
             (getEndPoint(*RetireItr) <= getStartPoint(Cur))) {
        // If this interval has subsequent segments, add the next one to the
        // inactive list.
        if (!isAtLastSegment(*RetireItr))
          Inactive.push(nextSegment(*RetireItr));

        ++RetireItr;
      }
      Active.erase(Active.begin(), RetireItr);

      // One of the newly retired segments may actually start before the
      // Cur segment, so re-grab the front of the inactive list.
      Cur = Inactive.top();
      Inactive.pop();

      // At this point we know that Cur overlaps all active intervals. Add the
      // interference edges.
      PBQP::GraphBase::NodeId NId = getNodeId(Cur);
      for (const auto &A : Active) {
        PBQP::GraphBase::NodeId MId = getNodeId(A);

        // Do not add an edge when the nodes' allowed registers do not
        // intersect: there is obviously no interference.
        if (haveDisjointAllowedRegs(G, NId, MId, D))
          continue;

        // Check that we haven't already added this edge
        // FIXME: findEdge is expensive in the worst case (O(max_clique(G))).
        //        It might be better to replace this with a local bit-matrix.
        if (G.findEdge(NId, MId) != PBQPRAGraph::invalidEdgeId())
          continue;

        // This is a new edge - add it to the graph.
        if (!createInterferenceEdge(G, NId, MId, C))
          setDisjointAllowedRegs(G, NId, MId, D);
      }

      // Finally, add Cur to the Active set.
      Active.insert(Cur);
    }
  }

private:

  // Create an Interference edge and add it to the graph, unless it is
  // a null matrix, meaning the nodes' allowed registers do not have any
  // interference. This case occurs frequently between integer and floating
  // point registers for example.
  // return true iff both nodes interferes.
  bool createInterferenceEdge(PBQPRAGraph &G,
                              PBQPRAGraph::NodeId NId, PBQPRAGraph::NodeId MId,
                              IMatrixCache &C) {

    const TargetRegisterInfo &TRI =
        *G.getMetadata().MF.getSubtarget().getRegisterInfo();
    const auto &NRegs = G.getNodeMetadata(NId).getAllowedRegs();
    const auto &MRegs = G.getNodeMetadata(MId).getAllowedRegs();

    // Try looking the edge costs up in the IMatrixCache first.
    IKey K(&NRegs, &MRegs);
    IMatrixCache::iterator I = C.find(K);
    if (I != C.end()) {
      G.addEdgeBypassingCostAllocator(NId, MId, I->second);
      return true;<commit_msg>[PBQP] Use a local bit-matrix to speedup searching an edge in the graph.<commit_after>//===------ 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) <NAME>. and <NAME>. 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) <NAME>., <NAME>. 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 "Spiller.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/CalcSpillWeights.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveRangeEdit.h"
#include "llvm/CodeGen/LiveStackAnalysis.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
#include "llvm/CodeGen/VirtRegMap.h"
#include "llvm/IR/Module.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/FileSystem.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
#include <limits>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <vector>

using namespace llvm;

#define DEBUG_TYPE "regalloc"

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 {
public:

  static char ID;

  /// Construct a PBQP register allocator.
  RegAllocPBQP(char *cPassID = nullptr)
      : MachineFunctionPass(ID), customPassID(cPassID) {
    initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
    initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
    initializeLiveStacksPass(*PassRegistry::getPassRegistry());
    initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
  }

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

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

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

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::set<unsigned> RegSet;

  char *customPassID;

  RegSet VRegsToAlloc, EmptyIntervalVRegs;

  /// \brief Finds the initial set of vreg intervals to allocate.
  void findVRegIntervalsToAlloc(const MachineFunction &MF, LiveIntervals &LIS);

  /// \brief Constructs an initial graph.
  void initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM, Spiller &VRegSpiller);

  /// \brief Spill the given VReg.
  void spillVReg(unsigned VReg, SmallVectorImpl<unsigned> &NewIntervals,
                 MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM,
                 Spiller &VRegSpiller);

  /// \brief Given a solved PBQP problem maps this solution back to a register
  /// assignment.
  bool mapPBQPToRegAlloc(const PBQPRAGraph &G,
                         const PBQP::Solution &Solution,
                         VirtRegMap &VRM,
                         Spiller &VRegSpiller);

  /// \brief Postprocessing before final spilling. Sets basic block "live in"
  /// variables.
  void finalizeAlloc(MachineFunction &MF, LiveIntervals &LIS,
                     VirtRegMap &VRM) const;

};

char RegAllocPBQP::ID = 0;

/// @brief Set spill costs for each node in the PBQP reg-alloc graph.
class SpillCosts : public PBQPRAConstraint {
public:
  void apply(PBQPRAGraph &G) override {
    LiveIntervals &LIS = G.getMetadata().LIS;

    // A minimum spill costs, so that register constraints can can be set
    // without normalization in the [0.0:MinSpillCost( interval.
    const PBQP::PBQPNum MinSpillCost = 10.0;

    for (auto NId : G.nodeIds()) {
      PBQP::PBQPNum SpillCost =
        LIS.getInterval(G.getNodeMetadata(NId).getVReg()).weight;
      if (SpillCost == 0.0)
        SpillCost = std::numeric_limits<PBQP::PBQPNum>::min();
      else
        SpillCost += MinSpillCost;
      PBQPRAGraph::RawVector NodeCosts(G.getNodeCosts(NId));
      NodeCosts[PBQP::RegAlloc::getSpillOptionIdx()] = SpillCost;
      G.setNodeCosts(NId, std::move(NodeCosts));
    }
  }
};

/// @brief Add interference edges between overlapping vregs.
class Interference : public PBQPRAConstraint {
private:

  typedef const PBQP::RegAlloc::AllowedRegVector* AllowedRegVecPtr;
  typedef std::pair<AllowedRegVecPtr, AllowedRegVecPtr> IKey;
  typedef DenseMap<IKey, PBQPRAGraph::MatrixPtr> IMatrixCache;
  typedef DenseSet<IKey> DisjointAllowedRegsCache;
  typedef std::pair<PBQP::GraphBase::NodeId, PBQP::GraphBase::NodeId> IEdgeKey;
  typedef DenseSet<IEdgeKey> IEdgeCache;

  bool haveDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId,
                               PBQPRAGraph::NodeId MId,
                               const DisjointAllowedRegsCache &D) const {
    const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs();
    const auto *MRegs = &G.getNodeMetadata(MId).getAllowedRegs();

    if (NRegs == MRegs)
      return false;

    if (NRegs < MRegs)
      return D.count(IKey(NRegs, MRegs)) > 0;

    return D.count(IKey(MRegs, NRegs)) > 0;
  }

  void setDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId,
                              PBQPRAGraph::NodeId MId,
                              DisjointAllowedRegsCache &D) {
    const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs();
    const auto *MRegs = &G.getNodeMetadata(MId).getAllowedRegs();

    assert(NRegs != MRegs && "AllowedRegs can not be disjoint with itself");

    if (NRegs < MRegs)
      D.insert(IKey(NRegs, MRegs));
    else
      D.insert(IKey(MRegs, NRegs));
  }

  // Holds (Interval, CurrentSegmentID, and NodeId). The first two are required
  // for the fast interference graph construction algorithm. The last is there
  // to save us from looking up node ids via the VRegToNode map in the graph
  // metadata.
  typedef std::tuple<LiveInterval*, size_t, PBQP::GraphBase::NodeId>
    IntervalInfo;

  static SlotIndex getStartPoint(const IntervalInfo &I) {
    return std::get<0>(I)->segments[std::get<1>(I)].start;
  }

  static SlotIndex getEndPoint(const IntervalInfo &I) {
    return std::get<0>(I)->segments[std::get<1>(I)].end;
  }

  static PBQP::GraphBase::NodeId getNodeId(const IntervalInfo &I) {
    return std::get<2>(I);
  }

  static bool lowestStartPoint(const IntervalInfo &I1,
                               const IntervalInfo &I2) {
    // Condition reversed because priority queue has the *highest* element at
    // the front, rather than the lowest.
    return getStartPoint(I1) > getStartPoint(I2);
  }

  static bool lowestEndPoint(const IntervalInfo &I1,
                             const IntervalInfo &I2) {
    SlotIndex E1 = getEndPoint(I1);
    SlotIndex E2 = getEndPoint(I2);

    if (E1 < E2)
      return true;

    if (E1 > E2)
      return false;

    // If two intervals end at the same point, we need a way to break the tie or
    // the set will assume they're actually equal and refuse to insert a
    // "duplicate". Just compare the vregs - fast and guaranteed unique.
    return std::get<0>(I1)->reg < std::get<0>(I2)->reg;
  }

  static bool isAtLastSegment(const IntervalInfo &I) {
    return std::get<1>(I) == std::get<0>(I)->size() - 1;
  }

  static IntervalInfo nextSegment(const IntervalInfo &I) {
    return std::make_tuple(std::get<0>(I), std::get<1>(I) + 1, std::get<2>(I));
  }

public:

  void apply(PBQPRAGraph &G) override {
    // The following is loosely based on the linear scan algorithm introduced in
    // "Linear Scan Register Allocation" by Poletto and Sarkar. This version
    // isn't linear, because the size of the active set isn't bound by the
    // number of registers, but rather the size of the largest clique in the
    // graph. Still, we expect this to be better than N^2.
    LiveIntervals &LIS = G.getMetadata().LIS;

    // Interferenc matrices are incredibly regular - they're only a function of
    // the allowed sets, so we cache them to avoid the overhead of constructing
    // and uniquing them.
    IMatrixCache C;

    // Finding an edge is expensive in the worst case (O(max_clique(G))). So
    // cache locally edges we have already seen.
    IEdgeCache EC;

    // Cache known disjoint allowed registers pairs
    DisjointAllowedRegsCache D;

    typedef std::set<IntervalInfo, decltype(&lowestEndPoint)> IntervalSet;
    typedef std::priority_queue<IntervalInfo, std::vector<IntervalInfo>,
                                decltype(&lowestStartPoint)> IntervalQueue;
    IntervalSet Active(lowestEndPoint);
    IntervalQueue Inactive(lowestStartPoint);

    // Start by building the inactive set.
    for (auto NId : G.nodeIds()) {
      unsigned VReg = G.getNodeMetadata(NId).getVReg();
      LiveInterval &LI = LIS.getInterval(VReg);
      assert(!LI.empty() && "PBQP graph contains node for empty interval");
      Inactive.push(std::make_tuple(&LI, 0, NId));
    }

    while (!Inactive.empty()) {
      // Tentatively grab the "next" interval - this choice may be overriden
      // below.
      IntervalInfo Cur = Inactive.top();

      // Retire any active intervals that end before Cur starts.
      IntervalSet::iterator RetireItr = Active.begin();
      while (RetireItr != Active.end() &&
             (getEndPoint(*RetireItr) <= getStartPoint(Cur))) {
        // If this interval has subsequent segments, add the next one to the
        // inactive list.
        if (!isAtLastSegment(*RetireItr))
          Inactive.push(nextSegment(*RetireItr));

        ++RetireItr;
      }
      Active.erase(Active.begin(), RetireItr);

      // One of the newly retired segments may actually start before the
      // Cur segment, so re-grab the front of the inactive list.
      Cur = Inactive.top();
      Inactive.pop();

      // At this point we know that Cur overlaps all active intervals. Add the
      // interference edges.
      PBQP::GraphBase::NodeId NId = getNodeId(Cur);
      for (const auto &A : Active) {
        PBQP::GraphBase::NodeId MId = getNodeId(A);

        // Do not add an edge when the nodes' allowed registers do not
        // intersect: there is obviously no interference.
        if (haveDisjointAllowedRegs(G, NId, MId, D))
          continue;

        // Check that we haven't already added this edge
        IEdgeKey EK(std::min(NId, MId), std::max(NId, MId));
        if (EC.count(EK))
          continue;

        // This is a new edge - add it to the graph.
        if (!createInterferenceEdge(G, NId, MId, C))
          setDisjointAllowedRegs(G, NId, MId, D);
        else
          EC.insert(EK);
      }

      // Finally, add Cur to the Active set.
      Active.insert(Cur);
    }
  }

private:

  // Create an Interference edge and add it to the graph, unless it is
  // a null matrix, meaning the nodes' allowed registers do not have any
  // interference. This case occurs frequently between integer and floating
  // point registers for example.
  // return true iff both nodes interferes.
  bool createInterferenceEdge(PBQPRAGraph &G,
                              PBQPRAGraph::NodeId NId, PBQPRAGraph::NodeId MId,
                              IMatrixCache &C) {

    const TargetRegisterInfo &TRI =
        *G.getMetadata().MF.getSubtarget().getRegisterInfo();
    const auto &NRegs = G.getNodeMetadata(NId).getAllowedRegs();
    const auto &MRegs = G.getNodeMetadata(MId).getAllowedRegs();

    // Try looking the edge costs up in the IMatrixCache first.
    IKey K(&NRegs, &MRegs);
    IMatrixCache::iterator I = C.find(K);
    if (I != C.end()) {
      G.addEdgeBypassingCostAllocator(NId, MId, I->second);
      return true;
{'fraction_non_alphanumeric': 0.1197420383319445, 'fraction_numerical': 0.0054345857034165425, 'mean_word_length': 3.0259626604434073, 'pattern_counts': {'":': 0, '<': 95, '<?xml version=': 0, '>': 105, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5602141', 'n_tokens_mistral': 8647, 'n_tokens_neox': 8236, 'n_words': 2467}