File Manager

003 File Manager

Current Path: /usr/src/contrib/llvm-project/llvm/include/llvm/CodeGen

usr / src / contrib / llvm-project / llvm / include / llvm / CodeGen /

📁 ..
📄 AccelTable.h(13.54 KB)
📄 Analysis.h(6.04 KB)
📄 AntiDepBreaker.h(3.78 KB)
📄 AsmPrinter.h(27.35 KB)
📄 AsmPrinterHandler.h(2.6 KB)
📄 AtomicExpandUtils.h(2.49 KB)
📄 BasicTTIImpl.h(73.64 KB)
📄 BuiltinGCs.h(1008 B)
📄 CSEConfigBase.h(1.09 KB)
📄 CalcSpillWeights.h(4.69 KB)
📄 CallingConvLower.h(21 KB)
📄 CommandFlags.h(3.65 KB)
📄 CostTable.h(1.87 KB)
📄 DAGCombine.h(606 B)
📄 DFAPacketizer.h(7.47 KB)
📄 DIE.h(32.19 KB)
📄 DIEValue.def(1.4 KB)
📄 DbgEntityHistoryCalculator.h(4.37 KB)
📄 DebugHandlerBase.h(4.68 KB)
📄 DwarfStringPoolEntry.h(2.18 KB)
📄 EdgeBundles.h(2.13 KB)
📄 ExecutionDomainFix.h(7.72 KB)
📄 ExpandReductions.h(726 B)
📄 FastISel.h(22.87 KB)
📄 FaultMaps.h(6.66 KB)
📄 FunctionLoweringInfo.h(9.68 KB)
📄 GCMetadata.h(7.24 KB)
📄 GCMetadataPrinter.h(2.46 KB)
📄 GCStrategy.h(5.25 KB)
📁 GlobalISel
📄 ISDOpcodes.h(52.75 KB)
📄 IndirectThunks.h(3.85 KB)
📄 IntrinsicLowering.h(1.67 KB)
📄 LatencyPriorityQueue.h(3.09 KB)
📄 LazyMachineBlockFrequencyInfo.h(2.82 KB)
📄 LexicalScopes.h(10.06 KB)
📄 LinkAllAsmWriterComponents.h(1.34 KB)
📄 LinkAllCodegenComponents.h(2.18 KB)
📄 LiveInterval.h(37.24 KB)
📄 LiveIntervalCalc.h(2.91 KB)
📄 LiveIntervalUnion.h(6.93 KB)
📄 LiveIntervals.h(19.86 KB)
📄 LivePhysRegs.h(7.51 KB)
📄 LiveRangeCalc.h(11.49 KB)
📄 LiveRangeEdit.h(10.45 KB)
📄 LiveRegMatrix.h(6.18 KB)
📄 LiveRegUnits.h(6.24 KB)
📄 LiveStacks.h(3.35 KB)
📄 LiveVariables.h(12.98 KB)
📄 LoopTraversal.h(4.38 KB)
📄 LowLevelType.h(1.28 KB)
📄 MBFIWrapper.h(1.58 KB)
📄 MIRFormatter.h(3.13 KB)
📁 MIRParser
📄 MIRPrinter.h(1.73 KB)
📄 MIRYamlMapping.h(23.95 KB)
📄 MachORelocation.h(2.19 KB)
📄 MachineBasicBlock.h(42.95 KB)
📄 MachineBlockFrequencyInfo.h(3.21 KB)
📄 MachineBranchProbabilityInfo.h(2.69 KB)
📄 MachineCombinerPattern.h(3.5 KB)
📄 MachineConstantPool.h(5.25 KB)
📄 MachineDominanceFrontier.h(2.93 KB)
📄 MachineDominators.h(9.59 KB)
📄 MachineFrameInfo.h(34.84 KB)
📄 MachineFunction.h(42.94 KB)
📄 MachineFunctionPass.h(2.93 KB)
📄 MachineInstr.h(73.72 KB)
📄 MachineInstrBuilder.h(22.84 KB)
📄 MachineInstrBundle.h(10.16 KB)
📄 MachineInstrBundleIterator.h(10.92 KB)
📄 MachineJumpTableInfo.h(4.66 KB)
📄 MachineLoopInfo.h(7.3 KB)
📄 MachineLoopUtils.h(1.74 KB)
📄 MachineMemOperand.h(12.69 KB)
📄 MachineModuleInfo.h(9.88 KB)
📄 MachineModuleInfoImpls.h(3.36 KB)
📄 MachineOperand.h(37.64 KB)
📄 MachineOptimizationRemarkEmitter.h(8.99 KB)
📄 MachineOutliner.h(8.04 KB)
📄 MachinePassRegistry.h(6.1 KB)
📄 MachinePipeliner.h(21.17 KB)
📄 MachinePostDominators.h(2.93 KB)
📄 MachineRegionInfo.h(5.93 KB)
📄 MachineRegisterInfo.h(46.75 KB)
📄 MachineSSAUpdater.h(4.37 KB)
📄 MachineScheduler.h(36.6 KB)
📄 MachineSizeOpts.h(1.86 KB)
📄 MachineTraceMetrics.h(17.17 KB)
📄 MacroFusion.h(1.96 KB)
📄 ModuloSchedule.h(15.8 KB)
📄 NonRelocatableStringpool.h(2.9 KB)
📁 PBQP
📄 PBQPRAConstraint.h(1.83 KB)
📄 ParallelCG.h(1.66 KB)
📄 Passes.h(18.96 KB)
📄 PreISelIntrinsicLowering.h(944 B)
📄 PseudoSourceValue.h(6.21 KB)
📄 RDFGraph.h(33.73 KB)
📄 RDFLiveness.h(5.01 KB)
📄 RDFRegisters.h(6.51 KB)
📄 ReachingDefAnalysis.h(10.68 KB)
📄 RegAllocPBQP.h(16.47 KB)
📄 RegAllocRegistry.h(2.27 KB)
📄 Register.h(5.61 KB)
📄 RegisterClassInfo.h(4.86 KB)
📄 RegisterPressure.h(21.04 KB)
📄 RegisterScavenging.h(8.73 KB)
📄 RegisterUsageInfo.h(2.3 KB)
📄 ResourcePriorityQueue.h(4.19 KB)
📄 RuntimeLibcalls.h(3.05 KB)
📄 SDNodeProperties.td(1.57 KB)
📄 ScheduleDAG.h(28.92 KB)
📄 ScheduleDAGInstrs.h(15.49 KB)
📄 ScheduleDAGMutation.h(1021 B)
📄 ScheduleDFS.h(5.79 KB)
📄 ScheduleHazardRecognizer.h(4.65 KB)
📄 SchedulerRegistry.h(4.27 KB)
📄 ScoreboardHazardRecognizer.h(3.7 KB)
📄 SelectionDAG.h(89.12 KB)
📄 SelectionDAGAddressAnalysis.h(3.58 KB)
📄 SelectionDAGISel.h(13.48 KB)
📄 SelectionDAGNodes.h(91.77 KB)
📄 SelectionDAGTargetInfo.h(7.99 KB)
📄 SlotIndexes.h(24.12 KB)
📄 Spiller.h(1.16 KB)
📄 StackMaps.h(11.45 KB)
📄 StackProtector.h(4.1 KB)
📄 SwiftErrorValueTracking.h(3.87 KB)
📄 SwitchLoweringUtils.h(9.51 KB)
📄 TailDuplicator.h(5.54 KB)
📄 TargetCallingConv.h(8.26 KB)
📄 TargetFrameLowering.h(19.21 KB)
📄 TargetInstrInfo.h(84.48 KB)
📄 TargetLowering.h(194.17 KB)
📄 TargetLoweringObjectFileImpl.h(11.63 KB)
📄 TargetOpcodes.h(1.37 KB)
📄 TargetPassConfig.h(17.9 KB)
📄 TargetRegisterInfo.h(48.65 KB)
📄 TargetSchedule.h(7.75 KB)
📄 TargetSubtargetInfo.h(12.53 KB)
📄 UnreachableBlockElim.h(1.39 KB)
📄 ValueTypes.h(17.2 KB)
📄 ValueTypes.td(11.42 KB)
📄 VirtRegMap.h(6.37 KB)
📄 WasmEHFuncInfo.h(1.92 KB)
📄 WinEHFuncInfo.h(4.01 KB)

Editing: RegAllocPBQP.h

//===- RegAllocPBQP.h -------------------------------------------*- C++ -*-===//
//
// 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 defines the PBQPBuilder interface, for classes which build PBQP
// instances to represent register allocation problems, and the RegAllocPBQP
// interface.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_REGALLOCPBQP_H
#define LLVM_CODEGEN_REGALLOCPBQP_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/CodeGen/PBQP/CostAllocator.h"
#include "llvm/CodeGen/PBQP/Graph.h"
#include "llvm/CodeGen/PBQP/Math.h"
#include "llvm/CodeGen/PBQP/ReductionRules.h"
#include "llvm/CodeGen/PBQP/Solution.h"
#include "llvm/Support/ErrorHandling.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <memory>
#include <set>
#include <vector>

namespace llvm {

class FunctionPass;
class LiveIntervals;
class MachineBlockFrequencyInfo;
class MachineFunction;
class raw_ostream;

namespace PBQP {
namespace RegAlloc {

/// Spill option index.
inline unsigned getSpillOptionIdx() { return 0; }

/// Metadata to speed allocatability test.
///
/// Keeps track of the number of infinities in each row and column.
class MatrixMetadata {
public:
  MatrixMetadata(const Matrix& M)
    : UnsafeRows(new bool[M.getRows() - 1]()),
      UnsafeCols(new bool[M.getCols() - 1]()) {
    unsigned* ColCounts = new unsigned[M.getCols() - 1]();

for (unsigned i = 1; i < M.getRows(); ++i) {
      unsigned RowCount = 0;
      for (unsigned j = 1; j < M.getCols(); ++j) {
        if (M[i][j] == std::numeric_limits<PBQPNum>::infinity()) {
          ++RowCount;
          ++ColCounts[j - 1];
          UnsafeRows[i - 1] = true;
          UnsafeCols[j - 1] = true;
        }
      }
      WorstRow = std::max(WorstRow, RowCount);
    }
    unsigned WorstColCountForCurRow =
      *std::max_element(ColCounts, ColCounts + M.getCols() - 1);
    WorstCol = std::max(WorstCol, WorstColCountForCurRow);
    delete[] ColCounts;
  }

MatrixMetadata(const MatrixMetadata &) = delete;
  MatrixMetadata &operator=(const MatrixMetadata &) = delete;

unsigned getWorstRow() const { return WorstRow; }
  unsigned getWorstCol() const { return WorstCol; }
  const bool* getUnsafeRows() const { return UnsafeRows.get(); }
  const bool* getUnsafeCols() const { return UnsafeCols.get(); }

private:
  unsigned WorstRow = 0;
  unsigned WorstCol = 0;
  std::unique_ptr<bool[]> UnsafeRows;
  std::unique_ptr<bool[]> UnsafeCols;
};

/// Holds a vector of the allowed physical regs for a vreg.
class AllowedRegVector {
  friend hash_code hash_value(const AllowedRegVector &);

public:
  AllowedRegVector() = default;
  AllowedRegVector(AllowedRegVector &&) = default;

AllowedRegVector(const std::vector<unsigned> &OptVec)
    : NumOpts(OptVec.size()), Opts(new unsigned[NumOpts]) {
    std::copy(OptVec.begin(), OptVec.end(), Opts.get());
  }

unsigned size() const { return NumOpts; }
  unsigned operator[](size_t I) const { return Opts[I]; }

bool operator==(const AllowedRegVector &Other) const {
    if (NumOpts != Other.NumOpts)
      return false;
    return std::equal(Opts.get(), Opts.get() + NumOpts, Other.Opts.get());
  }

bool operator!=(const AllowedRegVector &Other) const {
    return !(*this == Other);
  }

private:
  unsigned NumOpts = 0;
  std::unique_ptr<unsigned[]> Opts;
};

inline hash_code hash_value(const AllowedRegVector &OptRegs) {
  unsigned *OStart = OptRegs.Opts.get();
  unsigned *OEnd = OptRegs.Opts.get() + OptRegs.NumOpts;
  return hash_combine(OptRegs.NumOpts,
                      hash_combine_range(OStart, OEnd));
}

/// Holds graph-level metadata relevant to PBQP RA problems.
class GraphMetadata {
private:
  using AllowedRegVecPool = ValuePool<AllowedRegVector>;

public:
  using AllowedRegVecRef = AllowedRegVecPool::PoolRef;

GraphMetadata(MachineFunction &MF,
                LiveIntervals &LIS,
                MachineBlockFrequencyInfo &MBFI)
    : MF(MF), LIS(LIS), MBFI(MBFI) {}

MachineFunction &MF;
  LiveIntervals &LIS;
  MachineBlockFrequencyInfo &MBFI;

void setNodeIdForVReg(unsigned VReg, GraphBase::NodeId NId) {
    VRegToNodeId[VReg] = NId;
  }

GraphBase::NodeId getNodeIdForVReg(unsigned VReg) const {
    auto VRegItr = VRegToNodeId.find(VReg);
    if (VRegItr == VRegToNodeId.end())
      return GraphBase::invalidNodeId();
    return VRegItr->second;
  }

AllowedRegVecRef getAllowedRegs(AllowedRegVector Allowed) {
    return AllowedRegVecs.getValue(std::move(Allowed));
  }

private:
  DenseMap<unsigned, GraphBase::NodeId> VRegToNodeId;
  AllowedRegVecPool AllowedRegVecs;
};

/// Holds solver state and other metadata relevant to each PBQP RA node.
class NodeMetadata {
public:
  using AllowedRegVector = RegAlloc::AllowedRegVector;

// The node's reduction state. The order in this enum is important,
  // as it is assumed nodes can only progress up (i.e. towards being
  // optimally reducible) when reducing the graph.
  using ReductionState = enum {
    Unprocessed,
    NotProvablyAllocatable,
    ConservativelyAllocatable,
    OptimallyReducible
  };

NodeMetadata() = default;

NodeMetadata(const NodeMetadata &Other)
    : RS(Other.RS), NumOpts(Other.NumOpts), DeniedOpts(Other.DeniedOpts),
      OptUnsafeEdges(new unsigned[NumOpts]), VReg(Other.VReg),
      AllowedRegs(Other.AllowedRegs)
#ifndef NDEBUG
      , everConservativelyAllocatable(Other.everConservativelyAllocatable)
#endif
  {
    if (NumOpts > 0) {
      std::copy(&Other.OptUnsafeEdges[0], &Other.OptUnsafeEdges[NumOpts],
                &OptUnsafeEdges[0]);
    }
  }

NodeMetadata(NodeMetadata &&) = default;
  NodeMetadata& operator=(NodeMetadata &&) = default;

void setVReg(unsigned VReg) { this->VReg = VReg; }
  unsigned getVReg() const { return VReg; }

void setAllowedRegs(GraphMetadata::AllowedRegVecRef AllowedRegs) {
    this->AllowedRegs = std::move(AllowedRegs);
  }
  const AllowedRegVector& getAllowedRegs() const { return *AllowedRegs; }

void setup(const Vector& Costs) {
    NumOpts = Costs.getLength() - 1;
    OptUnsafeEdges = std::unique_ptr<unsigned[]>(new unsigned[NumOpts]());
  }

ReductionState getReductionState() const { return RS; }
  void setReductionState(ReductionState RS) {
    assert(RS >= this->RS && "A node's reduction state can not be downgraded");
    this->RS = RS;

#ifndef NDEBUG
    // Remember this state to assert later that a non-infinite register
    // option was available.
    if (RS == ConservativelyAllocatable)
      everConservativelyAllocatable = true;
#endif
  }

void handleAddEdge(const MatrixMetadata& MD, bool Transpose) {
    DeniedOpts += Transpose ? MD.getWorstRow() : MD.getWorstCol();
    const bool* UnsafeOpts =
      Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
    for (unsigned i = 0; i < NumOpts; ++i)
      OptUnsafeEdges[i] += UnsafeOpts[i];
  }

void handleRemoveEdge(const MatrixMetadata& MD, bool Transpose) {
    DeniedOpts -= Transpose ? MD.getWorstRow() : MD.getWorstCol();
    const bool* UnsafeOpts =
      Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
    for (unsigned i = 0; i < NumOpts; ++i)
      OptUnsafeEdges[i] -= UnsafeOpts[i];
  }

bool isConservativelyAllocatable() const {
    return (DeniedOpts < NumOpts) ||
      (std::find(&OptUnsafeEdges[0], &OptUnsafeEdges[NumOpts], 0) !=
       &OptUnsafeEdges[NumOpts]);
  }

#ifndef NDEBUG
  bool wasConservativelyAllocatable() const {
    return everConservativelyAllocatable;
  }
#endif

private:
  ReductionState RS = Unprocessed;
  unsigned NumOpts = 0;
  unsigned DeniedOpts = 0;
  std::unique_ptr<unsigned[]> OptUnsafeEdges;
  unsigned VReg = 0;
  GraphMetadata::AllowedRegVecRef AllowedRegs;

#ifndef NDEBUG
  bool everConservativelyAllocatable = false;
#endif
};

class RegAllocSolverImpl {
private:
  using RAMatrix = MDMatrix<MatrixMetadata>;

public:
  using RawVector = PBQP::Vector;
  using RawMatrix = PBQP::Matrix;
  using Vector = PBQP::Vector;
  using Matrix = RAMatrix;
  using CostAllocator = PBQP::PoolCostAllocator<Vector, Matrix>;

using NodeId = GraphBase::NodeId;
  using EdgeId = GraphBase::EdgeId;

using NodeMetadata = RegAlloc::NodeMetadata;
  struct EdgeMetadata {};
  using GraphMetadata = RegAlloc::GraphMetadata;

using Graph = PBQP::Graph<RegAllocSolverImpl>;

RegAllocSolverImpl(Graph &G) : G(G) {}

Solution solve() {
    G.setSolver(*this);
    Solution S;
    setup();
    S = backpropagate(G, reduce());
    G.unsetSolver();
    return S;
  }

void handleAddNode(NodeId NId) {
    assert(G.getNodeCosts(NId).getLength() > 1 &&
           "PBQP Graph should not contain single or zero-option nodes");
    G.getNodeMetadata(NId).setup(G.getNodeCosts(NId));
  }

void handleRemoveNode(NodeId NId) {}
  void handleSetNodeCosts(NodeId NId, const Vector& newCosts) {}

void handleAddEdge(EdgeId EId) {
    handleReconnectEdge(EId, G.getEdgeNode1Id(EId));
    handleReconnectEdge(EId, G.getEdgeNode2Id(EId));
  }

void handleDisconnectEdge(EdgeId EId, NodeId NId) {
    NodeMetadata& NMd = G.getNodeMetadata(NId);
    const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
    NMd.handleRemoveEdge(MMd, NId == G.getEdgeNode2Id(EId));
    promote(NId, NMd);
  }

void handleReconnectEdge(EdgeId EId, NodeId NId) {
    NodeMetadata& NMd = G.getNodeMetadata(NId);
    const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
    NMd.handleAddEdge(MMd, NId == G.getEdgeNode2Id(EId));
  }

void handleUpdateCosts(EdgeId EId, const Matrix& NewCosts) {
    NodeId N1Id = G.getEdgeNode1Id(EId);
    NodeId N2Id = G.getEdgeNode2Id(EId);
    NodeMetadata& N1Md = G.getNodeMetadata(N1Id);
    NodeMetadata& N2Md = G.getNodeMetadata(N2Id);
    bool Transpose = N1Id != G.getEdgeNode1Id(EId);

// Metadata are computed incrementally. First, update them
    // by removing the old cost.
    const MatrixMetadata& OldMMd = G.getEdgeCosts(EId).getMetadata();
    N1Md.handleRemoveEdge(OldMMd, Transpose);
    N2Md.handleRemoveEdge(OldMMd, !Transpose);

// And update now the metadata with the new cost.
    const MatrixMetadata& MMd = NewCosts.getMetadata();
    N1Md.handleAddEdge(MMd, Transpose);
    N2Md.handleAddEdge(MMd, !Transpose);

// As the metadata may have changed with the update, the nodes may have
    // become ConservativelyAllocatable or OptimallyReducible.
    promote(N1Id, N1Md);
    promote(N2Id, N2Md);
  }

private:
  void promote(NodeId NId, NodeMetadata& NMd) {
    if (G.getNodeDegree(NId) == 3) {
      // This node is becoming optimally reducible.
      moveToOptimallyReducibleNodes(NId);
    } else if (NMd.getReductionState() ==
               NodeMetadata::NotProvablyAllocatable &&
               NMd.isConservativelyAllocatable()) {
      // This node just became conservatively allocatable.
      moveToConservativelyAllocatableNodes(NId);
    }
  }

void removeFromCurrentSet(NodeId NId) {
    switch (G.getNodeMetadata(NId).getReductionState()) {
    case NodeMetadata::Unprocessed: break;
    case NodeMetadata::OptimallyReducible:
      assert(OptimallyReducibleNodes.find(NId) !=
             OptimallyReducibleNodes.end() &&
             "Node not in optimally reducible set.");
      OptimallyReducibleNodes.erase(NId);
      break;
    case NodeMetadata::ConservativelyAllocatable:
      assert(ConservativelyAllocatableNodes.find(NId) !=
             ConservativelyAllocatableNodes.end() &&
             "Node not in conservatively allocatable set.");
      ConservativelyAllocatableNodes.erase(NId);
      break;
    case NodeMetadata::NotProvablyAllocatable:
      assert(NotProvablyAllocatableNodes.find(NId) !=
             NotProvablyAllocatableNodes.end() &&
             "Node not in not-provably-allocatable set.");
      NotProvablyAllocatableNodes.erase(NId);
      break;
    }
  }

void moveToOptimallyReducibleNodes(NodeId NId) {
    removeFromCurrentSet(NId);
    OptimallyReducibleNodes.insert(NId);
    G.getNodeMetadata(NId).setReductionState(
      NodeMetadata::OptimallyReducible);
  }

void moveToConservativelyAllocatableNodes(NodeId NId) {
    removeFromCurrentSet(NId);
    ConservativelyAllocatableNodes.insert(NId);
    G.getNodeMetadata(NId).setReductionState(
      NodeMetadata::ConservativelyAllocatable);
  }

void moveToNotProvablyAllocatableNodes(NodeId NId) {
    removeFromCurrentSet(NId);
    NotProvablyAllocatableNodes.insert(NId);
    G.getNodeMetadata(NId).setReductionState(
      NodeMetadata::NotProvablyAllocatable);
  }

void setup() {
    // Set up worklists.
    for (auto NId : G.nodeIds()) {
      if (G.getNodeDegree(NId) < 3)
        moveToOptimallyReducibleNodes(NId);
      else if (G.getNodeMetadata(NId).isConservativelyAllocatable())
        moveToConservativelyAllocatableNodes(NId);
      else
        moveToNotProvablyAllocatableNodes(NId);
    }
  }

// Compute a reduction order for the graph by iteratively applying PBQP
  // reduction rules. Locally optimal rules are applied whenever possible (R0,
  // R1, R2). If no locally-optimal rules apply then any conservatively
  // allocatable node is reduced. Finally, if no conservatively allocatable
  // node exists then the node with the lowest spill-cost:degree ratio is
  // selected.
  std::vector<GraphBase::NodeId> reduce() {
    assert(!G.empty() && "Cannot reduce empty graph.");

using NodeId = GraphBase::NodeId;
    std::vector<NodeId> NodeStack;

// Consume worklists.
    while (true) {
      if (!OptimallyReducibleNodes.empty()) {
        NodeSet::iterator NItr = OptimallyReducibleNodes.begin();
        NodeId NId = *NItr;
        OptimallyReducibleNodes.erase(NItr);
        NodeStack.push_back(NId);
        switch (G.getNodeDegree(NId)) {
        case 0:
          break;
        case 1:
          applyR1(G, NId);
          break;
        case 2:
          applyR2(G, NId);
          break;
        default: llvm_unreachable("Not an optimally reducible node.");
        }
      } else if (!ConservativelyAllocatableNodes.empty()) {
        // Conservatively allocatable nodes will never spill. For now just
        // take the first node in the set and push it on the stack. When we
        // start optimizing more heavily for register preferencing, it may
        // would be better to push nodes with lower 'expected' or worst-case
        // register costs first (since early nodes are the most
        // constrained).
        NodeSet::iterator NItr = ConservativelyAllocatableNodes.begin();
        NodeId NId = *NItr;
        ConservativelyAllocatableNodes.erase(NItr);
        NodeStack.push_back(NId);
        G.disconnectAllNeighborsFromNode(NId);
      } else if (!NotProvablyAllocatableNodes.empty()) {
        NodeSet::iterator NItr =
          std::min_element(NotProvablyAllocatableNodes.begin(),
                           NotProvablyAllocatableNodes.end(),
                           SpillCostComparator(G));
        NodeId NId = *NItr;
        NotProvablyAllocatableNodes.erase(NItr);
        NodeStack.push_back(NId);
        G.disconnectAllNeighborsFromNode(NId);
      } else
        break;
    }

return NodeStack;
  }

class SpillCostComparator {
  public:
    SpillCostComparator(const Graph& G) : G(G) {}

bool operator()(NodeId N1Id, NodeId N2Id) {
      PBQPNum N1SC = G.getNodeCosts(N1Id)[0];
      PBQPNum N2SC = G.getNodeCosts(N2Id)[0];
      if (N1SC == N2SC)
        return G.getNodeDegree(N1Id) < G.getNodeDegree(N2Id);
      return N1SC < N2SC;
    }

private:
    const Graph& G;
  };

Graph& G;
  using NodeSet = std::set<NodeId>;
  NodeSet OptimallyReducibleNodes;
  NodeSet ConservativelyAllocatableNodes;
  NodeSet NotProvablyAllocatableNodes;
};

class PBQPRAGraph : public PBQP::Graph<RegAllocSolverImpl> {
private:
  using BaseT = PBQP::Graph<RegAllocSolverImpl>;

public:
  PBQPRAGraph(GraphMetadata Metadata) : BaseT(std::move(Metadata)) {}

/// Dump this graph to dbgs().
  void dump() const;

/// Dump this graph to an output stream.
  /// @param OS Output stream to print on.
  void dump(raw_ostream &OS) const;

/// Print a representation of this graph in DOT format.
  /// @param OS Output stream to print on.
  void printDot(raw_ostream &OS) const;
};

inline Solution solve(PBQPRAGraph& G) {
  if (G.empty())
    return Solution();
  RegAllocSolverImpl RegAllocSolver(G);
  return RegAllocSolver.solve();
}

} // end namespace RegAlloc
} // end namespace PBQP

/// Create a PBQP register allocator instance.
FunctionPass *
createPBQPRegisterAllocator(char *customPassID = nullptr);

} // end namespace llvm

#endif // LLVM_CODEGEN_REGALLOCPBQP_H

003 File Manager

Editing: RegAllocPBQP.h

Upload File

Create Folder