/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/RegAllocPBQP.h

Bug Summary

File:	llvm/include/llvm/CodeGen/RegAllocPBQP.h
Warning:	line 73, column 7 Use of zero-allocated memory

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name RegAllocPBQP.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -fhalf-no-semantic-interposition -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/build-llvm/lib/CodeGen -resource-dir /usr/lib/llvm-13/lib/clang/13.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/build-llvm/include -I /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/lib/llvm-13/lib/clang/13.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/build-llvm/lib/CodeGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-04-14-063029-18377-1 -x c++ /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/CodeGen/RegAllocPBQP.cpp

/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/CodeGen/RegAllocPBQP.cpp

→

1//===- RegAllocPBQP.cpp ---- PBQP Register Allocator ----------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains a Partitioned Boolean Quadratic Programming (PBQP) based
10// register allocator for LLVM. This allocator works by constructing a PBQP
11// problem representing the register allocation problem under consideration,
12// solving this using a PBQP solver, and mapping the solution back to a
13// register assignment. If any variables are selected for spilling then spill
14// code is inserted and the process repeated.
15//
16// The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned
17// for register allocation. For more information on PBQP for register
18// allocation, see the following papers:
19//
20//   (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with
21//   PBQP. In Proceedings of the 7th Joint Modular Languages Conference
22//   (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361.
23//
24//   (2) Scholz, B., Eckstein, E. 2002. Register allocation for irregular
25//   architectures. In Proceedings of the Joint Conference on Languages,
26//   Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New York,
27//   NY, USA, 139-148.
28//
29//===----------------------------------------------------------------------===//

31#include "llvm/CodeGen/RegAllocPBQP.h"
32#include "RegisterCoalescer.h"
33#include "llvm/ADT/ArrayRef.h"
34#include "llvm/ADT/BitVector.h"
35#include "llvm/ADT/DenseMap.h"
36#include "llvm/ADT/DenseSet.h"
37#include "llvm/ADT/STLExtras.h"
38#include "llvm/ADT/SmallPtrSet.h"
39#include "llvm/ADT/SmallVector.h"
40#include "llvm/ADT/StringRef.h"
41#include "llvm/Analysis/AliasAnalysis.h"
42#include "llvm/CodeGen/CalcSpillWeights.h"
43#include "llvm/CodeGen/LiveInterval.h"
44#include "llvm/CodeGen/LiveIntervals.h"
45#include "llvm/CodeGen/LiveRangeEdit.h"
46#include "llvm/CodeGen/LiveStacks.h"
47#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
48#include "llvm/CodeGen/MachineDominators.h"
49#include "llvm/CodeGen/MachineFunction.h"
50#include "llvm/CodeGen/MachineFunctionPass.h"
51#include "llvm/CodeGen/MachineInstr.h"
52#include "llvm/CodeGen/MachineLoopInfo.h"
53#include "llvm/CodeGen/MachineRegisterInfo.h"
54#include "llvm/CodeGen/PBQP/Graph.h"
55#include "llvm/CodeGen/PBQP/Math.h"
56#include "llvm/CodeGen/PBQP/Solution.h"
57#include "llvm/CodeGen/PBQPRAConstraint.h"
58#include "llvm/CodeGen/RegAllocRegistry.h"
59#include "llvm/CodeGen/SlotIndexes.h"
60#include "llvm/CodeGen/Spiller.h"
61#include "llvm/CodeGen/TargetRegisterInfo.h"
62#include "llvm/CodeGen/TargetSubtargetInfo.h"
63#include "llvm/CodeGen/VirtRegMap.h"
64#include "llvm/Config/llvm-config.h"
65#include "llvm/IR/Function.h"
66#include "llvm/IR/Module.h"
67#include "llvm/MC/MCRegisterInfo.h"
68#include "llvm/Pass.h"
69#include "llvm/Support/CommandLine.h"
70#include "llvm/Support/Compiler.h"
71#include "llvm/Support/Debug.h"
72#include "llvm/Support/FileSystem.h"
73#include "llvm/Support/Printable.h"
74#include "llvm/Support/raw_ostream.h"
75#include <algorithm>
76#include <cassert>
77#include <cstddef>
78#include <limits>
79#include <map>
80#include <memory>
81#include <queue>
82#include <set>
83#include <sstream>
84#include <string>
85#include <system_error>
86#include <tuple>
87#include <utility>
88#include <vector>

90using namespace llvm;

92#define DEBUG_TYPE"regalloc" "regalloc"

94static RegisterRegAlloc
95RegisterPBQPRepAlloc("pbqp", "PBQP register allocator",
                     createDefaultPBQPRegisterAllocator);

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

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

110namespace {

112///
113/// PBQP based allocators solve the register allocation problem by mapping
114/// register allocation problems to Partitioned Boolean Quadratic
115/// Programming problems.
116class RegAllocPBQP : public MachineFunctionPass {
117public:
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.
StringRef getPassName() const override { return "PBQP Register Allocator"; }

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

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

MachineFunctionProperties getRequiredProperties() const override {
  return MachineFunctionProperties().set(
      MachineFunctionProperties::Property::NoPHIs);
}

MachineFunctionProperties getClearedProperties() const override {
  return MachineFunctionProperties().set(
    MachineFunctionProperties::Property::IsSSA);
}

148private:
using RegSet = std::set<Register>;

char *customPassID;

RegSet VRegsToAlloc, EmptyIntervalVRegs;

/// Inst which is a def of an original reg and whose defs are already all
/// dead after remat is saved in DeadRemats. The deletion of such inst is
/// postponed till all the allocations are done, so its remat expr is
/// always available for the remat of all the siblings of the original reg.
SmallPtrSet<MachineInstr *, 32> DeadRemats;

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

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

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

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

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

void postOptimization(Spiller &VRegSpiller, LiveIntervals &LIS);
185};

187char RegAllocPBQP::ID = 0;

189/// Set spill costs for each node in the PBQP reg-alloc graph.
190class SpillCosts : public PBQPRAConstraint {
191public:
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));
  }
}
211};

213/// Add interference edges between overlapping vregs.
214class Interference : public PBQPRAConstraint {
215private:
using AllowedRegVecPtr = const PBQP::RegAlloc::AllowedRegVector *;
using IKey = std::pair<AllowedRegVecPtr, AllowedRegVecPtr>;
using IMatrixCache = DenseMap<IKey, PBQPRAGraph::MatrixPtr>;
using DisjointAllowedRegsCache = DenseSet<IKey>;
using IEdgeKey = std::pair<PBQP::GraphBase::NodeId, PBQP::GraphBase::NodeId>;
using IEdgeCache = DenseSet<IEdgeKey>;

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.contains(IKey(NRegs, MRegs));

  return D.contains(IKey(MRegs, NRegs));
}

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")((NRegs != MRegs && "AllowedRegs can not be disjoint with itself"
) ? static_cast<void> (0) : __assert_fail ("NRegs != MRegs && \"AllowedRegs can not be disjoint with itself\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/CodeGen/RegAllocPBQP.cpp"
, 244, __PRETTY_FUNCTION__));

  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.
using IntervalInfo =
    std::tuple<LiveInterval*, size_t, PBQP::GraphBase::NodeId>;

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

303public:
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;

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

  // Start by building the inactive set.
  for (auto NId : G.nodeIds()) {
    Register VReg = G.getNodeMetadata(NId).getVReg();
    LiveInterval &LI = LIS.getInterval(VReg);
    assert(!LI.empty() && "PBQP graph contains node for empty interval")((!LI.empty() && "PBQP graph contains node for empty interval"
) ? static_cast<void> (0) : __assert_fail ("!LI.empty() && \"PBQP graph contains node for empty interval\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/CodeGen/RegAllocPBQP.cpp"
, 335, __PRETTY_FUNCTION__));
    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);
  }
}

390private:
// 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;
  }

  PBQPRAGraph::RawMatrix M(NRegs.size() + 1, MRegs.size() + 1, 0);
  bool NodesInterfere = false;
  for (unsigned I = 0; I != NRegs.size(); ++I) {
    MCRegister PRegN = NRegs[I];
    for (unsigned J = 0; J != MRegs.size(); ++J) {
      MCRegister PRegM = MRegs[J];
      if (TRI.regsOverlap(PRegN, PRegM)) {
        M[I + 1][J + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity();
        NodesInterfere = true;
      }
    }
  }

  if (!NodesInterfere)
    return false;

  PBQPRAGraph::EdgeId EId = G.addEdge(NId, MId, std::move(M));
  C[K] = G.getEdgeCostsPtr(EId);

  return true;
}
433};

435class Coalescing : public PBQPRAConstraint {
436public:
void apply(PBQPRAGraph &G) override {
  MachineFunction &MF = G.getMetadata().MF;
  MachineBlockFrequencyInfo &MBFI = G.getMetadata().MBFI;
  CoalescerPair CP(*MF.getSubtarget().getRegisterInfo());

  // Scan the machine function and add a coalescing cost whenever CoalescerPair
  // gives the Ok.
  for (const auto &MBB : MF) {
    for (const auto &MI : MBB) {
      // Skip not-coalescable or already coalesced copies.
      if (!CP.setRegisters(&MI) || CP.getSrcReg() == CP.getDstReg())
1
Assuming the condition is false→
2
←
Taking false branch→
        continue;

      Register DstReg = CP.getDstReg();
      Register SrcReg = CP.getSrcReg();

      PBQP::PBQPNum CBenefit = MBFI.getBlockFreqRelativeToEntryBlock(&MBB);

      if (CP.isPhys()) {
3
←
Taking false branch→
        if (!MF.getRegInfo().isAllocatable(DstReg))
          continue;

        PBQPRAGraph::NodeId NId = G.getMetadata().getNodeIdForVReg(SrcReg);

        const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed =
          G.getNodeMetadata(NId).getAllowedRegs();

        unsigned PRegOpt = 0;
        while (PRegOpt < Allowed.size() && Allowed[PRegOpt].id() != DstReg)
          ++PRegOpt;

        if (PRegOpt < Allowed.size()) {
          PBQPRAGraph::RawVector NewCosts(G.getNodeCosts(NId));
          NewCosts[PRegOpt + 1] -= CBenefit;
          G.setNodeCosts(NId, std::move(NewCosts));
        }
      } else {
        PBQPRAGraph::NodeId N1Id = G.getMetadata().getNodeIdForVReg(DstReg);
        PBQPRAGraph::NodeId N2Id = G.getMetadata().getNodeIdForVReg(SrcReg);
        const PBQPRAGraph::NodeMetadata::AllowedRegVector *Allowed1 =
          &G.getNodeMetadata(N1Id).getAllowedRegs();
        const PBQPRAGraph::NodeMetadata::AllowedRegVector *Allowed2 =
          &G.getNodeMetadata(N2Id).getAllowedRegs();

        PBQPRAGraph::EdgeId EId = G.findEdge(N1Id, N2Id);
        if (EId == G.invalidEdgeId()) {
4
←
Assuming the condition is true→
5
←
Taking true branch→
          PBQPRAGraph::RawMatrix Costs(Allowed1->size() + 1,
                                       Allowed2->size() + 1, 0);
          addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit);
          G.addEdge(N1Id, N2Id, std::move(Costs));
6
←
Calling 'Graph::addEdge'→
        } else {
          if (G.getEdgeNode1Id(EId) == N2Id) {
            std::swap(N1Id, N2Id);
            std::swap(Allowed1, Allowed2);
          }
          PBQPRAGraph::RawMatrix Costs(G.getEdgeCosts(EId));
          addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit);
          G.updateEdgeCosts(EId, std::move(Costs));
        }
      }
    }
  }
}

501private:
void addVirtRegCoalesce(
                  PBQPRAGraph::RawMatrix &CostMat,
                  const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed1,
                  const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed2,
                  PBQP::PBQPNum Benefit) {
  assert(CostMat.getRows() == Allowed1.size() + 1 && "Size mismatch.")((CostMat.getRows() == Allowed1.size() + 1 && "Size mismatch."
) ? static_cast<void> (0) : __assert_fail ("CostMat.getRows() == Allowed1.size() + 1 && \"Size mismatch.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/CodeGen/RegAllocPBQP.cpp"
, 507, __PRETTY_FUNCTION__));
  assert(CostMat.getCols() == Allowed2.size() + 1 && "Size mismatch.")((CostMat.getCols() == Allowed2.size() + 1 && "Size mismatch."
) ? static_cast<void> (0) : __assert_fail ("CostMat.getCols() == Allowed2.size() + 1 && \"Size mismatch.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/CodeGen/RegAllocPBQP.cpp"
, 508, __PRETTY_FUNCTION__));
  for (unsigned I = 0; I != Allowed1.size(); ++I) {
    MCRegister PReg1 = Allowed1[I];
    for (unsigned J = 0; J != Allowed2.size(); ++J) {
      MCRegister PReg2 = Allowed2[J];
      if (PReg1 == PReg2)
        CostMat[I + 1][J + 1] -= Benefit;
    }
  }
}
518};

520/// PBQP-specific implementation of weight normalization.
521class PBQPVirtRegAuxInfo final : public VirtRegAuxInfo {
float normalize(float UseDefFreq, unsigned Size, unsigned NumInstr) override {
  // All intervals have a spill weight that is mostly proportional to the
  // number of uses, with uses in loops having a bigger weight.
  return NumInstr * VirtRegAuxInfo::normalize(UseDefFreq, Size, 1);
}

528public:
PBQPVirtRegAuxInfo(MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM,
                   const MachineLoopInfo &Loops,
                   const MachineBlockFrequencyInfo &MBFI)
    : VirtRegAuxInfo(MF, LIS, VRM, Loops, MBFI) {}
533};
534} // end anonymous namespace

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

539void PBQPRAConstraint::anchor() {}

541void PBQPRAConstraintList::anchor() {}

543void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const {
au.setPreservesCFG();
au.addRequired<AAResultsWrapperPass>();
au.addPreserved<AAResultsWrapperPass>();
au.addRequired<SlotIndexes>();
au.addPreserved<SlotIndexes>();
au.addRequired<LiveIntervals>();
au.addPreserved<LiveIntervals>();
//au.addRequiredID(SplitCriticalEdgesID);
if (customPassID)
  au.addRequiredID(*customPassID);
au.addRequired<LiveStacks>();
au.addPreserved<LiveStacks>();
au.addRequired<MachineBlockFrequencyInfo>();
au.addPreserved<MachineBlockFrequencyInfo>();
au.addRequired<MachineLoopInfo>();
au.addPreserved<MachineLoopInfo>();
au.addRequired<MachineDominatorTree>();
au.addPreserved<MachineDominatorTree>();
au.addRequired<VirtRegMap>();
au.addPreserved<VirtRegMap>();
MachineFunctionPass::getAnalysisUsage(au);
565}

567void RegAllocPBQP::findVRegIntervalsToAlloc(const MachineFunction &MF,
                                          LiveIntervals &LIS) {
const MachineRegisterInfo &MRI = MF.getRegInfo();

// Iterate over all live ranges.
for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
  Register Reg = Register::index2VirtReg(I);
  if (MRI.reg_nodbg_empty(Reg))
    continue;
  VRegsToAlloc.insert(Reg);
}
578}

580static bool isACalleeSavedRegister(MCRegister Reg,
                                 const TargetRegisterInfo &TRI,
                                 const MachineFunction &MF) {
const MCPhysReg *CSR = MF.getRegInfo().getCalleeSavedRegs();
for (unsigned i = 0; CSR[i] != 0; ++i)
  if (TRI.regsOverlap(Reg, CSR[i]))
    return true;
return false;
588}

590void RegAllocPBQP::initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM,
                                 Spiller &VRegSpiller) {
MachineFunction &MF = G.getMetadata().MF;

LiveIntervals &LIS = G.getMetadata().LIS;
const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo();
const TargetRegisterInfo &TRI =
    *G.getMetadata().MF.getSubtarget().getRegisterInfo();

std::vector<Register> Worklist(VRegsToAlloc.begin(), VRegsToAlloc.end());

std::map<Register, std::vector<MCRegister>> VRegAllowedMap;

while (!Worklist.empty()) {
  Register VReg = Worklist.back();
  Worklist.pop_back();

  LiveInterval &VRegLI = LIS.getInterval(VReg);

  // If this is an empty interval move it to the EmptyIntervalVRegs set then
  // continue.
  if (VRegLI.empty()) {
    EmptyIntervalVRegs.insert(VRegLI.reg());
    VRegsToAlloc.erase(VRegLI.reg());
    continue;
  }

  const TargetRegisterClass *TRC = MRI.getRegClass(VReg);

  // Record any overlaps with regmask operands.
  BitVector RegMaskOverlaps;
  LIS.checkRegMaskInterference(VRegLI, RegMaskOverlaps);

  // Compute an initial allowed set for the current vreg.
  std::vector<MCRegister> VRegAllowed;
  ArrayRef<MCPhysReg> RawPRegOrder = TRC->getRawAllocationOrder(MF);
  for (unsigned I = 0; I != RawPRegOrder.size(); ++I) {
    MCRegister PReg(RawPRegOrder[I]);
    if (MRI.isReserved(PReg))
      continue;

    // vregLI crosses a regmask operand that clobbers preg.
    if (!RegMaskOverlaps.empty() && !RegMaskOverlaps.test(PReg))
      continue;

    // vregLI overlaps fixed regunit interference.
    bool Interference = false;
    for (MCRegUnitIterator Units(PReg, &TRI); Units.isValid(); ++Units) {
      if (VRegLI.overlaps(LIS.getRegUnit(*Units))) {
        Interference = true;
        break;
      }
    }
    if (Interference)
      continue;

    // preg is usable for this virtual register.
    VRegAllowed.push_back(PReg);
  }

  // Check for vregs that have no allowed registers. These should be
  // pre-spilled and the new vregs added to the worklist.
  if (VRegAllowed.empty()) {
    SmallVector<Register, 8> NewVRegs;
    spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller);
    llvm::append_range(Worklist, NewVRegs);
    continue;
  }

  VRegAllowedMap[VReg.id()] = std::move(VRegAllowed);
}

for (auto &KV : VRegAllowedMap) {
  auto VReg = KV.first;

  // Move empty intervals to the EmptyIntervalVReg set.
  if (LIS.getInterval(VReg).empty()) {
    EmptyIntervalVRegs.insert(VReg);
    VRegsToAlloc.erase(VReg);
    continue;
  }

  auto &VRegAllowed = KV.second;

  PBQPRAGraph::RawVector NodeCosts(VRegAllowed.size() + 1, 0);

  // Tweak cost of callee saved registers, as using then force spilling and
  // restoring them. This would only happen in the prologue / epilogue though.
  for (unsigned i = 0; i != VRegAllowed.size(); ++i)
    if (isACalleeSavedRegister(VRegAllowed[i], TRI, MF))
      NodeCosts[1 + i] += 1.0;

  PBQPRAGraph::NodeId NId = G.addNode(std::move(NodeCosts));
  G.getNodeMetadata(NId).setVReg(VReg);
  G.getNodeMetadata(NId).setAllowedRegs(
    G.getMetadata().getAllowedRegs(std::move(VRegAllowed)));
  G.getMetadata().setNodeIdForVReg(VReg, NId);
}
688}

690void RegAllocPBQP::spillVReg(Register VReg,
                           SmallVectorImpl<Register> &NewIntervals,
                           MachineFunction &MF, LiveIntervals &LIS,
                           VirtRegMap &VRM, Spiller &VRegSpiller) {
VRegsToAlloc.erase(VReg);
LiveRangeEdit LRE(&LIS.getInterval(VReg), NewIntervals, MF, LIS, &VRM,
                  nullptr, &DeadRemats);
VRegSpiller.spill(LRE);

const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
(void)TRI;
LLVM_DEBUG(dbgs() << "VREG " << printReg(VReg, &TRI) << " -> SPILLED (Cost: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "VREG " << printReg(VReg
, &TRI) << " -> SPILLED (Cost: " << LRE.getParent
().weight() << ", New vregs: "; } } while (false)
                  << LRE.getParent().weight() << ", New vregs: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "VREG " << printReg(VReg
, &TRI) << " -> SPILLED (Cost: " << LRE.getParent
().weight() << ", New vregs: "; } } while (false);

// Copy any newly inserted live intervals into the list of regs to
// allocate.
for (const Register &R : LRE) {
  const LiveInterval &LI = LIS.getInterval(R);
  assert(!LI.empty() && "Empty spill range.")((!LI.empty() && "Empty spill range.") ? static_cast<
void> (0) : __assert_fail ("!LI.empty() && \"Empty spill range.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/CodeGen/RegAllocPBQP.cpp"
, 708, __PRETTY_FUNCTION__));
  LLVM_DEBUG(dbgs() << printReg(LI.reg(), &TRI) << " ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << printReg(LI.reg(), &TRI) <<
 " "; } } while (false);
  VRegsToAlloc.insert(LI.reg());
}

LLVM_DEBUG(dbgs() << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << ")\n"; } } while (false);
714}

716bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAGraph &G,
                                   const PBQP::Solution &Solution,
                                   VirtRegMap &VRM,
                                   Spiller &VRegSpiller) {
MachineFunction &MF = G.getMetadata().MF;
LiveIntervals &LIS = G.getMetadata().LIS;
const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
(void)TRI;

// Set to true if we have any spills
bool AnotherRoundNeeded = false;

// Clear the existing allocation.
VRM.clearAllVirt();

// Iterate over the nodes mapping the PBQP solution to a register
// assignment.
for (auto NId : G.nodeIds()) {
  Register VReg = G.getNodeMetadata(NId).getVReg();
  unsigned AllocOpt = Solution.getSelection(NId);

  if (AllocOpt != PBQP::RegAlloc::getSpillOptionIdx()) {
    MCRegister PReg = G.getNodeMetadata(NId).getAllowedRegs()[AllocOpt - 1];
    LLVM_DEBUG(dbgs() << "VREG " << printReg(VReg, &TRI) << " -> "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "VREG " << printReg(VReg
, &TRI) << " -> " << TRI.getName(PReg) <<
 "\n"; } } while (false)
                      << TRI.getName(PReg) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "VREG " << printReg(VReg
, &TRI) << " -> " << TRI.getName(PReg) <<
 "\n"; } } while (false);
    assert(PReg != 0 && "Invalid preg selected.")((PReg != 0 && "Invalid preg selected.") ? static_cast
<void> (0) : __assert_fail ("PReg != 0 && \"Invalid preg selected.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/CodeGen/RegAllocPBQP.cpp"
, 741, __PRETTY_FUNCTION__));
    VRM.assignVirt2Phys(VReg, PReg);
  } else {
    // Spill VReg. If this introduces new intervals we'll need another round
    // of allocation.
    SmallVector<Register, 8> NewVRegs;
    spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller);
    AnotherRoundNeeded |= !NewVRegs.empty();
  }
}

return !AnotherRoundNeeded;
753}

755void RegAllocPBQP::finalizeAlloc(MachineFunction &MF,
                               LiveIntervals &LIS,
                               VirtRegMap &VRM) const {
MachineRegisterInfo &MRI = MF.getRegInfo();

// First allocate registers for the empty intervals.
for (const Register &R : EmptyIntervalVRegs) {
  LiveInterval &LI = LIS.getInterval(R);

  Register PReg = MRI.getSimpleHint(LI.reg());

  if (PReg == 0) {
    const TargetRegisterClass &RC = *MRI.getRegClass(LI.reg());
    const ArrayRef<MCPhysReg> RawPRegOrder = RC.getRawAllocationOrder(MF);
    for (MCRegister CandidateReg : RawPRegOrder) {
      if (!VRM.getRegInfo().isReserved(CandidateReg)) {
        PReg = CandidateReg;
        break;
      }
    }
    assert(PReg &&((PReg && "No un-reserved physical registers in this register class"
) ? static_cast<void> (0) : __assert_fail ("PReg && \"No un-reserved physical registers in this register class\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/CodeGen/RegAllocPBQP.cpp"
, 776, __PRETTY_FUNCTION__))
           "No un-reserved physical registers in this register class")((PReg && "No un-reserved physical registers in this register class"
) ? static_cast<void> (0) : __assert_fail ("PReg && \"No un-reserved physical registers in this register class\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/CodeGen/RegAllocPBQP.cpp"
, 776, __PRETTY_FUNCTION__));
  }

  VRM.assignVirt2Phys(LI.reg(), PReg);
}
781}

783void RegAllocPBQP::postOptimization(Spiller &VRegSpiller, LiveIntervals &LIS) {
VRegSpiller.postOptimization();
/// Remove dead defs because of rematerialization.
for (auto DeadInst : DeadRemats) {
  LIS.RemoveMachineInstrFromMaps(*DeadInst);
  DeadInst->eraseFromParent();
}
DeadRemats.clear();
791}

793bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) {
LiveIntervals &LIS = getAnalysis<LiveIntervals>();
MachineBlockFrequencyInfo &MBFI =
  getAnalysis<MachineBlockFrequencyInfo>();

VirtRegMap &VRM = getAnalysis<VirtRegMap>();

PBQPVirtRegAuxInfo VRAI(MF, LIS, VRM, getAnalysis<MachineLoopInfo>(), MBFI);
VRAI.calculateSpillWeightsAndHints();

// FIXME: we create DefaultVRAI here to match existing behavior pre-passing
// the VRAI through the spiller to the live range editor. However, it probably
// makes more sense to pass the PBQP VRAI. The existing behavior had
// LiveRangeEdit make its own VirtRegAuxInfo object.
VirtRegAuxInfo DefaultVRAI(MF, LIS, VRM, getAnalysis<MachineLoopInfo>(),
                           MBFI);
std::unique_ptr<Spiller> VRegSpiller(
    createInlineSpiller(*this, MF, VRM, DefaultVRAI));

MF.getRegInfo().freezeReservedRegs(MF);

LLVM_DEBUG(dbgs() << "PBQP Register Allocating for " << MF.getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "PBQP Register Allocating for "
 << MF.getName() << "\n"; } } while (false);

// Allocator main loop:
//
// * Map current regalloc problem to a PBQP problem
// * Solve the PBQP problem
// * Map the solution back to a register allocation
// * Spill if necessary
//
// This process is continued till no more spills are generated.

// Find the vreg intervals in need of allocation.
findVRegIntervalsToAlloc(MF, LIS);

828#ifndef NDEBUG
const Function &F = MF.getFunction();
std::string FullyQualifiedName =
  F.getParent()->getModuleIdentifier() + "." + F.getName().str();
832#endif

// If there are non-empty intervals allocate them using pbqp.
if (!VRegsToAlloc.empty()) {
  const TargetSubtargetInfo &Subtarget = MF.getSubtarget();
  std::unique_ptr<PBQPRAConstraintList> ConstraintsRoot =
    std::make_unique<PBQPRAConstraintList>();
  ConstraintsRoot->addConstraint(std::make_unique<SpillCosts>());
  ConstraintsRoot->addConstraint(std::make_unique<Interference>());
  if (PBQPCoalescing)
    ConstraintsRoot->addConstraint(std::make_unique<Coalescing>());
  ConstraintsRoot->addConstraint(Subtarget.getCustomPBQPConstraints());

  bool PBQPAllocComplete = false;
  unsigned Round = 0;

  while (!PBQPAllocComplete) {
    LLVM_DEBUG(dbgs() << "  PBQP Regalloc round " << Round << ":\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "  PBQP Regalloc round " <<
 Round << ":\n"; } } while (false);

    PBQPRAGraph G(PBQPRAGraph::GraphMetadata(MF, LIS, MBFI));
    initializeGraph(G, VRM, *VRegSpiller);
    ConstraintsRoot->apply(G);

855#ifndef NDEBUG
    if (PBQPDumpGraphs) {
      std::ostringstream RS;
      RS << Round;
      std::string GraphFileName = FullyQualifiedName + "." + RS.str() +
                                  ".pbqpgraph";
      std::error_code EC;
      raw_fd_ostream OS(GraphFileName, EC, sys::fs::OF_TextWithCRLF);
      LLVM_DEBUG(dbgs() << "Dumping graph for round " << Round << " to \""do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Dumping graph for round " <<
 Round << " to \"" << GraphFileName << "\"\n"
; } } while (false)
                        << GraphFileName << "\"\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Dumping graph for round " <<
 Round << " to \"" << GraphFileName << "\"\n"
; } } while (false);
      G.dump(OS);
    }
867#endif

    PBQP::Solution Solution = PBQP::RegAlloc::solve(G);
    PBQPAllocComplete = mapPBQPToRegAlloc(G, Solution, VRM, *VRegSpiller);
    ++Round;
  }
}

// Finalise allocation, allocate empty ranges.
finalizeAlloc(MF, LIS, VRM);
postOptimization(*VRegSpiller, LIS);
VRegsToAlloc.clear();
EmptyIntervalVRegs.clear();

LLVM_DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << VRM << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Post alloc VirtRegMap:\n" <<
 VRM << "\n"; } } while (false);

return true;
884}

886/// Create Printable object for node and register info.
887static Printable PrintNodeInfo(PBQP::RegAlloc::PBQPRAGraph::NodeId NId,
                             const PBQP::RegAlloc::PBQPRAGraph &G) {
return Printable([NId, &G](raw_ostream &OS) {
  const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo();
  const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
  Register VReg = G.getNodeMetadata(NId).getVReg();
  const char *RegClassName = TRI->getRegClassName(MRI.getRegClass(VReg));
  OS << NId << " (" << RegClassName << ':' << printReg(VReg, TRI) << ')';
});
896}

898#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
899LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) 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.")((Costs.getLength() != 0 && "Empty vector in graph.")
 ? static_cast<void> (0) : __assert_fail ("Costs.getLength() != 0 && \"Empty vector in graph.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/CodeGen/RegAllocPBQP.cpp"
, 902, __PRETTY_FUNCTION__));
  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.")((N1Id != N2Id && "PBQP graphs should not have self-edges."
) ? static_cast<void> (0) : __assert_fail ("N1Id != N2Id && \"PBQP graphs should not have self-edges.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/CodeGen/RegAllocPBQP.cpp"
, 910, __PRETTY_FUNCTION__));
  const Matrix &M = getEdgeCosts(EId);
  assert(M.getRows() != 0 && "No rows in matrix.")((M.getRows() != 0 && "No rows in matrix.") ? static_cast
<void> (0) : __assert_fail ("M.getRows() != 0 && \"No rows in matrix.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/CodeGen/RegAllocPBQP.cpp"
, 912, __PRETTY_FUNCTION__));
  assert(M.getCols() != 0 && "No cols in matrix.")((M.getCols() != 0 && "No cols in matrix.") ? static_cast
<void> (0) : __assert_fail ("M.getCols() != 0 && \"No cols in matrix.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/CodeGen/RegAllocPBQP.cpp"
, 913, __PRETTY_FUNCTION__));
  OS << PrintNodeInfo(N1Id, *this) << ' ' << M.getRows() << " rows / ";
  OS << PrintNodeInfo(N2Id, *this) << ' ' << M.getCols() << " cols:\n";
  OS << M << '\n';
}
918}

920LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void PBQP::RegAlloc::PBQPRAGraph::dump() const {
dump(dbgs());
922}
923#endif

925void PBQP::RegAlloc::PBQPRAGraph::printDot(raw_ostream &OS) const {
OS << "graph {\n";
for (auto NId : nodeIds()) {
  OS << "  node" << NId << " [ label=\""
     << PrintNodeInfo(NId, *this) << "\\n"
     << getNodeCosts(NId) << "\" ]\n";
}

OS << "  edge [ len=" << nodeIds().size() << " ]\n";
for (auto EId : edgeIds()) {
  OS << "  node" << getEdgeNode1Id(EId)
     << " -- node" << getEdgeNode2Id(EId)
     << " [ label=\"";
  const Matrix &EdgeCosts = getEdgeCosts(EId);
  for (unsigned i = 0; i < EdgeCosts.getRows(); ++i) {
    OS << EdgeCosts.getRowAsVector(i) << "\\n";
  }
  OS << "\" ]\n";
}
OS << "}\n";
945}

947FunctionPass *llvm::createPBQPRegisterAllocator(char *customPassID) {
return new RegAllocPBQP(customPassID);
949}

951FunctionPass* llvm::createDefaultPBQPRegisterAllocator() {
return createPBQPRegisterAllocator();
953}

←

/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h

→

1//===- Graph.h - PBQP Graph -------------------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// PBQP Graph class.
10//
11//===----------------------------------------------------------------------===//

13#ifndef LLVM_CODEGEN_PBQP_GRAPH_H
14#define LLVM_CODEGEN_PBQP_GRAPH_H

16#include "llvm/ADT/STLExtras.h"
17#include <algorithm>
18#include <cassert>
19#include <iterator>
20#include <limits>
21#include <vector>

23namespace llvm {
24namespace PBQP {

class GraphBase {
public:
  using NodeId = unsigned;
  using EdgeId = unsigned;

  /// Returns a value representing an invalid (non-existent) node.
  static NodeId invalidNodeId() {
    return std::numeric_limits<NodeId>::max();
  }

  /// Returns a value representing an invalid (non-existent) edge.
  static EdgeId invalidEdgeId() {
    return std::numeric_limits<EdgeId>::max();
  }
};

/// PBQP Graph class.
/// Instances of this class describe PBQP problems.
///
template <typename SolverT>
class Graph : public GraphBase {
private:
  using CostAllocator = typename SolverT::CostAllocator;

public:
  using RawVector = typename SolverT::RawVector;
  using RawMatrix = typename SolverT::RawMatrix;
  using Vector = typename SolverT::Vector;
  using Matrix = typename SolverT::Matrix;
  using VectorPtr = typename CostAllocator::VectorPtr;
  using MatrixPtr = typename CostAllocator::MatrixPtr;
  using NodeMetadata = typename SolverT::NodeMetadata;
  using EdgeMetadata = typename SolverT::EdgeMetadata;
  using GraphMetadata = typename SolverT::GraphMetadata;

private:
  class NodeEntry {
  public:
    using AdjEdgeList = std::vector<EdgeId>;
    using AdjEdgeIdx = AdjEdgeList::size_type;
    using AdjEdgeItr = AdjEdgeList::const_iterator;

    NodeEntry(VectorPtr Costs) : Costs(std::move(Costs)) {}

    static AdjEdgeIdx getInvalidAdjEdgeIdx() {
      return std::numeric_limits<AdjEdgeIdx>::max();
    }

    AdjEdgeIdx addAdjEdgeId(EdgeId EId) {
      AdjEdgeIdx Idx = AdjEdgeIds.size();
      AdjEdgeIds.push_back(EId);
      return Idx;
    }

    void removeAdjEdgeId(Graph &G, NodeId ThisNId, AdjEdgeIdx Idx) {
      // Swap-and-pop for fast removal.
      //   1) Update the adj index of the edge currently at back().
      //   2) Move last Edge down to Idx.
      //   3) pop_back()
      // If Idx == size() - 1 then the setAdjEdgeIdx and swap are
      // redundant, but both operations are cheap.
      G.getEdge(AdjEdgeIds.back()).setAdjEdgeIdx(ThisNId, Idx);
      AdjEdgeIds[Idx] = AdjEdgeIds.back();
      AdjEdgeIds.pop_back();
    }

    const AdjEdgeList& getAdjEdgeIds() const { return AdjEdgeIds; }

    VectorPtr Costs;
    NodeMetadata Metadata;

  private:
    AdjEdgeList AdjEdgeIds;
  };

  class EdgeEntry {
  public:
    EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs)
        : Costs(std::move(Costs)) {
      NIds[0] = N1Id;
      NIds[1] = N2Id;
      ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx();
      ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx();
    }

    void connectToN(Graph &G, EdgeId ThisEdgeId, unsigned NIdx) {
      assert(ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() &&((ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() &&
 "Edge already connected to NIds[NIdx].") ? static_cast<void
> (0) : __assert_fail ("ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() && \"Edge already connected to NIds[NIdx].\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h"
, 113, __PRETTY_FUNCTION__))
             "Edge already connected to NIds[NIdx].")((ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() &&
 "Edge already connected to NIds[NIdx].") ? static_cast<void
> (0) : __assert_fail ("ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() && \"Edge already connected to NIds[NIdx].\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h"
, 113, __PRETTY_FUNCTION__));
      NodeEntry &N = G.getNode(NIds[NIdx]);
      ThisEdgeAdjIdxs[NIdx] = N.addAdjEdgeId(ThisEdgeId);
    }

    void connect(Graph &G, EdgeId ThisEdgeId) {
      connectToN(G, ThisEdgeId, 0);
      connectToN(G, ThisEdgeId, 1);
    }

    void setAdjEdgeIdx(NodeId NId, typename NodeEntry::AdjEdgeIdx NewIdx) {
      if (NId == NIds[0])
        ThisEdgeAdjIdxs[0] = NewIdx;
      else {
        assert(NId == NIds[1] && "Edge not connected to NId")((NId == NIds[1] && "Edge not connected to NId") ? static_cast
<void> (0) : __assert_fail ("NId == NIds[1] && \"Edge not connected to NId\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h"
, 127, __PRETTY_FUNCTION__));
        ThisEdgeAdjIdxs[1] = NewIdx;
      }
    }

    void disconnectFromN(Graph &G, unsigned NIdx) {
      assert(ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() &&((ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() &&
 "Edge not connected to NIds[NIdx].") ? static_cast<void>
 (0) : __assert_fail ("ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() && \"Edge not connected to NIds[NIdx].\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h"
, 134, __PRETTY_FUNCTION__))
             "Edge not connected to NIds[NIdx].")((ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() &&
 "Edge not connected to NIds[NIdx].") ? static_cast<void>
 (0) : __assert_fail ("ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() && \"Edge not connected to NIds[NIdx].\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h"
, 134, __PRETTY_FUNCTION__));
      NodeEntry &N = G.getNode(NIds[NIdx]);
      N.removeAdjEdgeId(G, NIds[NIdx], ThisEdgeAdjIdxs[NIdx]);
      ThisEdgeAdjIdxs[NIdx] = NodeEntry::getInvalidAdjEdgeIdx();
    }

    void disconnectFrom(Graph &G, NodeId NId) {
      if (NId == NIds[0])
        disconnectFromN(G, 0);
      else {
        assert(NId == NIds[1] && "Edge does not connect NId")((NId == NIds[1] && "Edge does not connect NId") ? static_cast
<void> (0) : __assert_fail ("NId == NIds[1] && \"Edge does not connect NId\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h"
, 144, __PRETTY_FUNCTION__));
        disconnectFromN(G, 1);
      }
    }

    NodeId getN1Id() const { return NIds[0]; }
    NodeId getN2Id() const { return NIds[1]; }

    MatrixPtr Costs;
    EdgeMetadata Metadata;

  private:
    NodeId NIds[2];
    typename NodeEntry::AdjEdgeIdx ThisEdgeAdjIdxs[2];
  };

  // ----- MEMBERS -----

  GraphMetadata Metadata;
  CostAllocator CostAlloc;
  SolverT *Solver = nullptr;

  using NodeVector = std::vector<NodeEntry>;
  using FreeNodeVector = std::vector<NodeId>;
  NodeVector Nodes;
  FreeNodeVector FreeNodeIds;

  using EdgeVector = std::vector<EdgeEntry>;
  using FreeEdgeVector = std::vector<EdgeId>;
  EdgeVector Edges;
  FreeEdgeVector FreeEdgeIds;

  Graph(const Graph &Other) {}

  // ----- INTERNAL METHODS -----

  NodeEntry &getNode(NodeId NId) {
    assert(NId < Nodes.size() && "Out of bound NodeId")((NId < Nodes.size() && "Out of bound NodeId") ? static_cast
<void> (0) : __assert_fail ("NId < Nodes.size() && \"Out of bound NodeId\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h"
, 181, __PRETTY_FUNCTION__));
    return Nodes[NId];
  }
  const NodeEntry &getNode(NodeId NId) const {
    assert(NId < Nodes.size() && "Out of bound NodeId")((NId < Nodes.size() && "Out of bound NodeId") ? static_cast
<void> (0) : __assert_fail ("NId < Nodes.size() && \"Out of bound NodeId\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h"
, 185, __PRETTY_FUNCTION__));
    return Nodes[NId];
  }

  EdgeEntry& getEdge(EdgeId EId) { return Edges[EId]; }
  const EdgeEntry& getEdge(EdgeId EId) const { return Edges[EId]; }

  NodeId addConstructedNode(NodeEntry N) {
    NodeId NId = 0;
    if (!FreeNodeIds.empty()) {
      NId = FreeNodeIds.back();
      FreeNodeIds.pop_back();
      Nodes[NId] = std::move(N);
    } else {
      NId = Nodes.size();
      Nodes.push_back(std::move(N));
    }
    return NId;
  }

  EdgeId addConstructedEdge(EdgeEntry E) {
    assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() &&((findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() &&
 "Attempt to add duplicate edge.") ? static_cast<void> (
0) : __assert_fail ("findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() && \"Attempt to add duplicate edge.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h"
, 207, __PRETTY_FUNCTION__))
           "Attempt to add duplicate edge.")((findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() &&
 "Attempt to add duplicate edge.") ? static_cast<void> (
0) : __assert_fail ("findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() && \"Attempt to add duplicate edge.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h"
, 207, __PRETTY_FUNCTION__));
    EdgeId EId = 0;
    if (!FreeEdgeIds.empty()) {
      EId = FreeEdgeIds.back();
      FreeEdgeIds.pop_back();
      Edges[EId] = std::move(E);
    } else {
      EId = Edges.size();
      Edges.push_back(std::move(E));
    }

    EdgeEntry &NE = getEdge(EId);

    // Add the edge to the adjacency sets of its nodes.
    NE.connect(*this, EId);
    return EId;
  }

  void operator=(const Graph &Other) {}

public:
  using AdjEdgeItr = typename NodeEntry::AdjEdgeItr;

  class NodeItr {
  public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = NodeId;
    using difference_type = int;
    using pointer = NodeId *;
    using reference = NodeId &;

    NodeItr(NodeId CurNId, const Graph &G)
      : CurNId(CurNId), EndNId(G.Nodes.size()), FreeNodeIds(G.FreeNodeIds) {
      this->CurNId = findNextInUse(CurNId); // Move to first in-use node id
    }

    bool operator==(const NodeItr &O) const { return CurNId == O.CurNId; }
    bool operator!=(const NodeItr &O) const { return !(*this == O); }
    NodeItr& operator++() { CurNId = findNextInUse(++CurNId); return *this; }
    NodeId operator*() const { return CurNId; }

  private:
    NodeId findNextInUse(NodeId NId) const {
      while (NId < EndNId && is_contained(FreeNodeIds, NId)) {
        ++NId;
      }
      return NId;
    }

    NodeId CurNId, EndNId;
    const FreeNodeVector &FreeNodeIds;
  };

  class EdgeItr {
  public:
    EdgeItr(EdgeId CurEId, const Graph &G)
      : CurEId(CurEId), EndEId(G.Edges.size()), FreeEdgeIds(G.FreeEdgeIds) {
      this->CurEId = findNextInUse(CurEId); // Move to first in-use edge id
    }

    bool operator==(const EdgeItr &O) const { return CurEId == O.CurEId; }
    bool operator!=(const EdgeItr &O) const { return !(*this == O); }
    EdgeItr& operator++() { CurEId = findNextInUse(++CurEId); return *this; }
    EdgeId operator*() const { return CurEId; }

  private:
    EdgeId findNextInUse(EdgeId EId) const {
      while (EId < EndEId && is_contained(FreeEdgeIds, EId)) {
        ++EId;
      }
      return EId;
    }

    EdgeId CurEId, EndEId;
    const FreeEdgeVector &FreeEdgeIds;
  };

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

    NodeItr begin() const { return NodeItr(0, G); }
    NodeItr end() const { return NodeItr(G.Nodes.size(), G); }

    bool empty() const { return G.Nodes.empty(); }

    typename NodeVector::size_type size() const {
      return G.Nodes.size() - G.FreeNodeIds.size();
    }

  private:
    const Graph& G;
  };

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

    EdgeItr begin() const { return EdgeItr(0, G); }
    EdgeItr end() const { return EdgeItr(G.Edges.size(), G); }

    bool empty() const { return G.Edges.empty(); }

    typename NodeVector::size_type size() const {
      return G.Edges.size() - G.FreeEdgeIds.size();
    }

  private:
    const Graph& G;
  };

  class AdjEdgeIdSet {
  public:
    AdjEdgeIdSet(const NodeEntry &NE) : NE(NE) {}

    typename NodeEntry::AdjEdgeItr begin() const {
      return NE.getAdjEdgeIds().begin();
    }

    typename NodeEntry::AdjEdgeItr end() const {
      return NE.getAdjEdgeIds().end();
    }

    bool empty() const { return NE.getAdjEdgeIds().empty(); }

    typename NodeEntry::AdjEdgeList::size_type size() const {
      return NE.getAdjEdgeIds().size();
    }

  private:
    const NodeEntry &NE;
  };

  /// Construct an empty PBQP graph.
  Graph() = default;

  /// Construct an empty PBQP graph with the given graph metadata.
  Graph(GraphMetadata Metadata) : Metadata(std::move(Metadata)) {}

  /// Get a reference to the graph metadata.
  GraphMetadata& getMetadata() { return Metadata; }

  /// Get a const-reference to the graph metadata.
  const GraphMetadata& getMetadata() const { return Metadata; }

  /// Lock this graph to the given solver instance in preparation
  /// for running the solver. This method will call solver.handleAddNode for
  /// each node in the graph, and handleAddEdge for each edge, to give the
  /// solver an opportunity to set up any requried metadata.
  void setSolver(SolverT &S) {
    assert(!Solver && "Solver already set. Call unsetSolver().")((!Solver && "Solver already set. Call unsetSolver()."
) ? static_cast<void> (0) : __assert_fail ("!Solver && \"Solver already set. Call unsetSolver().\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h"
, 357, __PRETTY_FUNCTION__));
    Solver = &S;
    for (auto NId : nodeIds())
      Solver->handleAddNode(NId);
    for (auto EId : edgeIds())
      Solver->handleAddEdge(EId);
  }

  /// Release from solver instance.
  void unsetSolver() {
    assert(Solver && "Solver not set.")((Solver && "Solver not set.") ? static_cast<void>
 (0) : __assert_fail ("Solver && \"Solver not set.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h"
, 367, __PRETTY_FUNCTION__));
    Solver = nullptr;
  }

  /// Add a node with the given costs.
  /// @param Costs Cost vector for the new node.
  /// @return Node iterator for the added node.
  template <typename OtherVectorT>
  NodeId addNode(OtherVectorT Costs) {
    // Get cost vector from the problem domain
    VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
    NodeId NId = addConstructedNode(NodeEntry(AllocatedCosts));
    if (Solver)
      Solver->handleAddNode(NId);
    return NId;
  }

  /// Add a node bypassing the cost allocator.
  /// @param Costs Cost vector ptr for the new node (must be convertible to
  ///        VectorPtr).
  /// @return Node iterator for the added node.
  ///
  ///   This method allows for fast addition of a node whose costs don't need
  /// to be passed through the cost allocator. The most common use case for
  /// this is when duplicating costs from an existing node (when using a
  /// pooling allocator). These have already been uniqued, so we can avoid
  /// re-constructing and re-uniquing them by attaching them directly to the
  /// new node.
  template <typename OtherVectorPtrT>
  NodeId addNodeBypassingCostAllocator(OtherVectorPtrT Costs) {
    NodeId NId = addConstructedNode(NodeEntry(Costs));
    if (Solver)
      Solver->handleAddNode(NId);
    return NId;
  }

  /// Add an edge between the given nodes with the given costs.
  /// @param N1Id First node.
  /// @param N2Id Second node.
  /// @param Costs Cost matrix for new edge.
  /// @return Edge iterator for the added edge.
  template <typename OtherVectorT>
  EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs) {
    assert(getNodeCosts(N1Id).getLength() == Costs.getRows() &&((getNodeCosts(N1Id).getLength() == Costs.getRows() &&
 getNodeCosts(N2Id).getLength() == Costs.getCols() &&
 "Matrix dimensions mismatch.") ? static_cast<void> (0)
 : __assert_fail ("getNodeCosts(N1Id).getLength() == Costs.getRows() && getNodeCosts(N2Id).getLength() == Costs.getCols() && \"Matrix dimensions mismatch.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h"
, 412, __PRETTY_FUNCTION__))
7
←
Assuming the condition is true→
8
←
Assuming the condition is true→
9
←
'?' condition is true→
           getNodeCosts(N2Id).getLength() == Costs.getCols() &&((getNodeCosts(N1Id).getLength() == Costs.getRows() &&
 getNodeCosts(N2Id).getLength() == Costs.getCols() &&
 "Matrix dimensions mismatch.") ? static_cast<void> (0)
 : __assert_fail ("getNodeCosts(N1Id).getLength() == Costs.getRows() && getNodeCosts(N2Id).getLength() == Costs.getCols() && \"Matrix dimensions mismatch.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h"
, 412, __PRETTY_FUNCTION__))
           "Matrix dimensions mismatch.")((getNodeCosts(N1Id).getLength() == Costs.getRows() &&
 getNodeCosts(N2Id).getLength() == Costs.getCols() &&
 "Matrix dimensions mismatch.") ? static_cast<void> (0)
 : __assert_fail ("getNodeCosts(N1Id).getLength() == Costs.getRows() && getNodeCosts(N2Id).getLength() == Costs.getCols() && \"Matrix dimensions mismatch.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h"
, 412, __PRETTY_FUNCTION__));
    // Get cost matrix from the problem domain.
    MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
10
←
Calling 'PoolCostAllocator::getMatrix'→
    EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, AllocatedCosts));
    if (Solver)
      Solver->handleAddEdge(EId);
    return EId;
  }

  /// Add an edge bypassing the cost allocator.
  /// @param N1Id First node.
  /// @param N2Id Second node.
  /// @param Costs Cost matrix for new edge.
  /// @return Edge iterator for the added edge.
  ///
  ///   This method allows for fast addition of an edge whose costs don't need
  /// to be passed through the cost allocator. The most common use case for
  /// this is when duplicating costs from an existing edge (when using a
  /// pooling allocator). These have already been uniqued, so we can avoid
  /// re-constructing and re-uniquing them by attaching them directly to the
  /// new edge.
  template <typename OtherMatrixPtrT>
  NodeId addEdgeBypassingCostAllocator(NodeId N1Id, NodeId N2Id,
                                       OtherMatrixPtrT Costs) {
    assert(getNodeCosts(N1Id).getLength() == Costs->getRows() &&((getNodeCosts(N1Id).getLength() == Costs->getRows() &&
 getNodeCosts(N2Id).getLength() == Costs->getCols() &&
 "Matrix dimensions mismatch.") ? static_cast<void> (0)
 : __assert_fail ("getNodeCosts(N1Id).getLength() == Costs->getRows() && getNodeCosts(N2Id).getLength() == Costs->getCols() && \"Matrix dimensions mismatch.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h"
, 438, __PRETTY_FUNCTION__))
           getNodeCosts(N2Id).getLength() == Costs->getCols() &&((getNodeCosts(N1Id).getLength() == Costs->getRows() &&
 getNodeCosts(N2Id).getLength() == Costs->getCols() &&
 "Matrix dimensions mismatch.") ? static_cast<void> (0)
 : __assert_fail ("getNodeCosts(N1Id).getLength() == Costs->getRows() && getNodeCosts(N2Id).getLength() == Costs->getCols() && \"Matrix dimensions mismatch.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h"
, 438, __PRETTY_FUNCTION__))
           "Matrix dimensions mismatch.")((getNodeCosts(N1Id).getLength() == Costs->getRows() &&
 getNodeCosts(N2Id).getLength() == Costs->getCols() &&
 "Matrix dimensions mismatch.") ? static_cast<void> (0)
 : __assert_fail ("getNodeCosts(N1Id).getLength() == Costs->getRows() && getNodeCosts(N2Id).getLength() == Costs->getCols() && \"Matrix dimensions mismatch.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Graph.h"
, 438, __PRETTY_FUNCTION__));
    // Get cost matrix from the problem domain.
    EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, Costs));
    if (Solver)
      Solver->handleAddEdge(EId);
    return EId;
  }

  /// Returns true if the graph is empty.
  bool empty() const { return NodeIdSet(*this).empty(); }

  NodeIdSet nodeIds() const { return NodeIdSet(*this); }
  EdgeIdSet edgeIds() const { return EdgeIdSet(*this); }

  AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); }

  /// Get the number of nodes in the graph.
  /// @return Number of nodes in the graph.
  unsigned getNumNodes() const { return NodeIdSet(*this).size(); }

  /// Get the number of edges in the graph.
  /// @return Number of edges in the graph.
  unsigned getNumEdges() const { return EdgeIdSet(*this).size(); }

  /// Set a node's cost vector.
  /// @param NId Node to update.
  /// @param Costs New costs to set.
  template <typename OtherVectorT>
  void setNodeCosts(NodeId NId, OtherVectorT Costs) {
    VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
    if (Solver)
      Solver->handleSetNodeCosts(NId, *AllocatedCosts);
    getNode(NId).Costs = AllocatedCosts;
  }

  /// Get a VectorPtr to a node's cost vector. Rarely useful - use
  ///        getNodeCosts where possible.
  /// @param NId Node id.
  /// @return VectorPtr to node cost vector.
  ///
  ///   This method is primarily useful for duplicating costs quickly by
  /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer
  /// getNodeCosts when dealing with node cost values.
  const VectorPtr& getNodeCostsPtr(NodeId NId) const {
    return getNode(NId).Costs;
  }

  /// Get a node's cost vector.
  /// @param NId Node id.
  /// @return Node cost vector.
  const Vector& getNodeCosts(NodeId NId) const {
    return *getNodeCostsPtr(NId);
  }

  NodeMetadata& getNodeMetadata(NodeId NId) {
    return getNode(NId).Metadata;
  }

  const NodeMetadata& getNodeMetadata(NodeId NId) const {
    return getNode(NId).Metadata;
  }

  typename NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const {
    return getNode(NId).getAdjEdgeIds().size();
  }

  /// Update an edge's cost matrix.
  /// @param EId Edge id.
  /// @param Costs New cost matrix.
  template <typename OtherMatrixT>
  void updateEdgeCosts(EdgeId EId, OtherMatrixT Costs) {
    MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
    if (Solver)
      Solver->handleUpdateCosts(EId, *AllocatedCosts);
    getEdge(EId).Costs = AllocatedCosts;
  }

  /// Get a MatrixPtr to a node's cost matrix. Rarely useful - use
  ///        getEdgeCosts where possible.
  /// @param EId Edge id.
  /// @return MatrixPtr to edge cost matrix.
  ///
  ///   This method is primarily useful for duplicating costs quickly by
  /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer
  /// getEdgeCosts when dealing with edge cost values.
  const MatrixPtr& getEdgeCostsPtr(EdgeId EId) const {
    return getEdge(EId).Costs;
  }

  /// Get an edge's cost matrix.
  /// @param EId Edge id.
  /// @return Edge cost matrix.
  const Matrix& getEdgeCosts(EdgeId EId) const {
    return *getEdge(EId).Costs;
  }

  EdgeMetadata& getEdgeMetadata(EdgeId EId) {
    return getEdge(EId).Metadata;
  }

  const EdgeMetadata& getEdgeMetadata(EdgeId EId) const {
    return getEdge(EId).Metadata;
  }

  /// Get the first node connected to this edge.
  /// @param EId Edge id.
  /// @return The first node connected to the given edge.
  NodeId getEdgeNode1Id(EdgeId EId) const {
    return getEdge(EId).getN1Id();
  }

  /// Get the second node connected to this edge.
  /// @param EId Edge id.
  /// @return The second node connected to the given edge.
  NodeId getEdgeNode2Id(EdgeId EId) const {
    return getEdge(EId).getN2Id();
  }

  /// Get the "other" node connected to this edge.
  /// @param EId Edge id.
  /// @param NId Node id for the "given" node.
  /// @return The iterator for the "other" node connected to this edge.
  NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId) {
    EdgeEntry &E = getEdge(EId);
    if (E.getN1Id() == NId) {
      return E.getN2Id();
    } // else
    return E.getN1Id();
  }

  /// Get the edge connecting two nodes.
  /// @param N1Id First node id.
  /// @param N2Id Second node id.
  /// @return An id for edge (N1Id, N2Id) if such an edge exists,
  ///         otherwise returns an invalid edge id.
  EdgeId findEdge(NodeId N1Id, NodeId N2Id) {
    for (auto AEId : adjEdgeIds(N1Id)) {
      if ((getEdgeNode1Id(AEId) == N2Id) ||
          (getEdgeNode2Id(AEId) == N2Id)) {
        return AEId;
      }
    }
    return invalidEdgeId();
  }

  /// Remove a node from the graph.
  /// @param NId Node id.
  void removeNode(NodeId NId) {
    if (Solver)
      Solver->handleRemoveNode(NId);
    NodeEntry &N = getNode(NId);
    // TODO: Can this be for-each'd?
    for (AdjEdgeItr AEItr = N.adjEdgesBegin(),
           AEEnd = N.adjEdgesEnd();
         AEItr != AEEnd;) {
      EdgeId EId = *AEItr;
      ++AEItr;
      removeEdge(EId);
    }
    FreeNodeIds.push_back(NId);
  }

  /// Disconnect an edge from the given node.
  ///
  /// Removes the given edge from the adjacency list of the given node.
  /// This operation leaves the edge in an 'asymmetric' state: It will no
  /// longer appear in an iteration over the given node's (NId's) edges, but
  /// will appear in an iteration over the 'other', unnamed node's edges.
  ///
  /// This does not correspond to any normal graph operation, but exists to
  /// support efficient PBQP graph-reduction based solvers. It is used to
  /// 'effectively' remove the unnamed node from the graph while the solver
  /// is performing the reduction. The solver will later call reconnectNode
  /// to restore the edge in the named node's adjacency list.
  ///
  /// Since the degree of a node is the number of connected edges,
  /// disconnecting an edge from a node 'u' will cause the degree of 'u' to
  /// drop by 1.
  ///
  /// A disconnected edge WILL still appear in an iteration over the graph
  /// edges.
  ///
  /// A disconnected edge should not be removed from the graph, it should be
  /// reconnected first.
  ///
  /// A disconnected edge can be reconnected by calling the reconnectEdge
  /// method.
  void disconnectEdge(EdgeId EId, NodeId NId) {
    if (Solver)
      Solver->handleDisconnectEdge(EId, NId);

    EdgeEntry &E = getEdge(EId);
    E.disconnectFrom(*this, NId);
  }

  /// Convenience method to disconnect all neighbours from the given
  ///        node.
  void disconnectAllNeighborsFromNode(NodeId NId) {
    for (auto AEId : adjEdgeIds(NId))
      disconnectEdge(AEId, getEdgeOtherNodeId(AEId, NId));
  }

  /// Re-attach an edge to its nodes.
  ///
  /// Adds an edge that had been previously disconnected back into the
  /// adjacency set of the nodes that the edge connects.
  void reconnectEdge(EdgeId EId, NodeId NId) {
    EdgeEntry &E = getEdge(EId);
    E.connectTo(*this, EId, NId);
    if (Solver)
      Solver->handleReconnectEdge(EId, NId);
  }

  /// Remove an edge from the graph.
  /// @param EId Edge id.
  void removeEdge(EdgeId EId) {
    if (Solver)
      Solver->handleRemoveEdge(EId);
    EdgeEntry &E = getEdge(EId);
    E.disconnect();
    FreeEdgeIds.push_back(EId);
    Edges[EId].invalidate();
  }

  /// Remove all nodes and edges from the graph.
  void clear() {
    Nodes.clear();
    FreeNodeIds.clear();
    Edges.clear();
    FreeEdgeIds.clear();
  }
};

671} // end namespace PBQP
672} // end namespace llvm

674#endif // LLVM_CODEGEN_PBQP_GRAPH_H

←

/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/CostAllocator.h

→

1//===- CostAllocator.h - PBQP Cost Allocator --------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Defines classes conforming to the PBQP cost value manager concept.
10//
11// Cost value managers are memory managers for PBQP cost values (vectors and
12// matrices). Since PBQP graphs can grow very large (E.g. hundreds of thousands
13// of edges on the largest function in SPEC2006).
14//
15//===----------------------------------------------------------------------===//
16 
17#ifndef LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
18#define LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
19 
20#include "llvm/ADT/DenseSet.h"
21#include <algorithm>
22#include <cstdint>
23#include <memory>
24 
25namespace llvm {
26namespace PBQP {
27 
28template <typename ValueT> class ValuePool {
29public:
30  using PoolRef = std::shared_ptr<const ValueT>;
31 
32private:
33  class PoolEntry : public std::enable_shared_from_this<PoolEntry> {
34  public:
35    template <typename ValueKeyT>
36    PoolEntry(ValuePool &Pool, ValueKeyT Value)
37        : Pool(Pool), Value(std::move(Value)) {}
22
←
Calling constructor for 'MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata>'→
38 
39    ~PoolEntry() { Pool.removeEntry(this); }
40 
41    const ValueT &getValue() const { return Value; }
42 
43  private:
44    ValuePool &Pool;
45    ValueT Value;
46  };
47 
48  class PoolEntryDSInfo {
49  public:
50    static inline PoolEntry *getEmptyKey() { return nullptr; }
51 
52    static inline PoolEntry *getTombstoneKey() {
53      return reinterpret_cast<PoolEntry *>(static_cast<uintptr_t>(1));
54    }
55 
56    template <typename ValueKeyT>
57    static unsigned getHashValue(const ValueKeyT &C) {
58      return hash_value(C);
59    }
60 
61    static unsigned getHashValue(PoolEntry *P) {
62      return getHashValue(P->getValue());
63    }
64 
65    static unsigned getHashValue(const PoolEntry *P) {
66      return getHashValue(P->getValue());
67    }
68 
69    template <typename ValueKeyT1, typename ValueKeyT2>
70    static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
71      return C1 == C2;
72    }
73 
74    template <typename ValueKeyT>
75    static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
76      if (P == getEmptyKey() || P == getTombstoneKey())
77        return false;
78      return isEqual(C, P->getValue());
79    }
80 
81    static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
82      if (P1 == getEmptyKey() || P1 == getTombstoneKey())
83        return P1 == P2;
84      return isEqual(P1->getValue(), P2);
85    }
86  };
87 
88  using EntrySetT = DenseSet<PoolEntry *, PoolEntryDSInfo>;
89 
90  EntrySetT EntrySet;
91 
92  void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
93 
94public:
95  template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) {
96    typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
97 
98    if (I != EntrySet.end())
12
←
Taking false branch→
99      return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
100 
101    auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey));
13
←
Calling 'make_shared<llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata>>::PoolEntry, llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata>> &, llvm::PBQP::Matrix>'→
102    EntrySet.insert(P.get());
103    return PoolRef(std::move(P), &P->getValue());
104  }
105};
106 
107template <typename VectorT, typename MatrixT> class PoolCostAllocator {
108private:
109  using VectorCostPool = ValuePool<VectorT>;
110  using MatrixCostPool = ValuePool<MatrixT>;
111 
112public:
113  using Vector = VectorT;
114  using Matrix = MatrixT;
115  using VectorPtr = typename VectorCostPool::PoolRef;
116  using MatrixPtr = typename MatrixCostPool::PoolRef;
117 
118  template <typename VectorKeyT> VectorPtr getVector(VectorKeyT v) {
119    return VectorPool.getValue(std::move(v));
120  }
121 
122  template <typename MatrixKeyT> MatrixPtr getMatrix(MatrixKeyT m) {
123    return MatrixPool.getValue(std::move(m));
11
←
Calling 'ValuePool::getValue'→
124  }
125 
126private:
127  VectorCostPool VectorPool;
128  MatrixCostPool MatrixPool;
129};
130 
131} // end namespace PBQP
132} // end namespace llvm
133 
134#endif // LLVM_CODEGEN_PBQP_COSTALLOCATOR_H

←

/usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/bits/shared_ptr.h

→

1// shared_ptr and weak_ptr implementation -*- C++ -*-

3// Copyright (C) 2007-2016 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.

11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.

16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.

20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.

25// GCC Note: Based on files from version 1.32.0 of the Boost library.

27//  shared_count.hpp
28//  Copyright (c) 2001, 2002, 2003 Peter Dimov and Multi Media Ltd.

30//  shared_ptr.hpp
31//  Copyright (C) 1998, 1999 Greg Colvin and Beman Dawes.
32//  Copyright (C) 2001, 2002, 2003 Peter Dimov

34//  weak_ptr.hpp
35//  Copyright (C) 2001, 2002, 2003 Peter Dimov

37//  enable_shared_from_this.hpp
38//  Copyright (C) 2002 Peter Dimov

40// Distributed under the Boost Software License, Version 1.0. (See
41// accompanying file LICENSE_1_0.txt or copy at
42// http://www.boost.org/LICENSE_1_0.txt)

44/** @file
*  This is an internal header file, included by other library headers.
*  Do not attempt to use it directly. @headername{memory}
*/

49#ifndef _SHARED_PTR_H1
50#define _SHARED_PTR_H1 1

52#include <bits/shared_ptr_base.h>

54namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
55{
56_GLIBCXX_BEGIN_NAMESPACE_VERSION

/**
 * @addtogroup pointer_abstractions
 * @{
 */

/// 20.7.2.2.11 shared_ptr I/O
template<typename _Ch, typename _Tr, typename _Tp, _Lock_policy _Lp>
  inline std::basic_ostream<_Ch, _Tr>&
  operator<<(std::basic_ostream<_Ch, _Tr>& __os,
      const __shared_ptr<_Tp, _Lp>& __p)
  {
    __os << __p.get();
    return __os;
  }

/// 20.7.2.2.10 shared_ptr get_deleter
template<typename _Del, typename _Tp, _Lock_policy _Lp>
  inline _Del*
  get_deleter(const __shared_ptr<_Tp, _Lp>& __p) noexcept
  {
78#if __cpp_rtti199711L
    return static_cast<_Del*>(__p._M_get_deleter(typeid(_Del)));
80#else
    return 0;
82#endif
  }


/**
 *  @brief  A smart pointer with reference-counted copy semantics.
 *
 *  The object pointed to is deleted when the last shared_ptr pointing to
 *  it is destroyed or reset.
*/
template<typename _Tp>
  class shared_ptr : public __shared_ptr<_Tp>
  {
    template<typename _Ptr>
using _Convertible
 = typename enable_if<is_convertible<_Ptr, _Tp*>::value>::type;

  public:
    /**
     *  @brief  Construct an empty %shared_ptr.
     *  @post   use_count()==0 && get()==0
     */
    constexpr shared_ptr() noexcept
    : __shared_ptr<_Tp>() { }

    shared_ptr(const shared_ptr&) noexcept = default;

    /**
     *  @brief  Construct a %shared_ptr that owns the pointer @a __p.
     *  @param  __p  A pointer that is convertible to element_type*.
     *  @post   use_count() == 1 && get() == __p
     *  @throw  std::bad_alloc, in which case @c delete @a __p is called.
     */
    template<typename _Tp1>
explicit shared_ptr(_Tp1* __p)
      : __shared_ptr<_Tp>(__p) { }

    /**
     *  @brief  Construct a %shared_ptr that owns the pointer @a __p
     *          and the deleter @a __d.
     *  @param  __p  A pointer.
     *  @param  __d  A deleter.
     *  @post   use_count() == 1 && get() == __p
     *  @throw  std::bad_alloc, in which case @a __d(__p) is called.
     *
     *  Requirements: _Deleter's copy constructor and destructor must
     *  not throw
     *
     *  __shared_ptr will release __p by calling __d(__p)
     */
    template<typename _Tp1, typename _Deleter>
shared_ptr(_Tp1* __p, _Deleter __d)
      : __shared_ptr<_Tp>(__p, __d) { }

    /**
     *  @brief  Construct a %shared_ptr that owns a null pointer
     *          and the deleter @a __d.
     *  @param  __p  A null pointer constant.
     *  @param  __d  A deleter.
     *  @post   use_count() == 1 && get() == __p
     *  @throw  std::bad_alloc, in which case @a __d(__p) is called.
     *
     *  Requirements: _Deleter's copy constructor and destructor must
     *  not throw
     *
     *  The last owner will call __d(__p)
     */
    template<typename _Deleter>
shared_ptr(nullptr_t __p, _Deleter __d)
      : __shared_ptr<_Tp>(__p, __d) { }

    /**
     *  @brief  Construct a %shared_ptr that owns the pointer @a __p
     *          and the deleter @a __d.
     *  @param  __p  A pointer.
     *  @param  __d  A deleter.
     *  @param  __a  An allocator.
     *  @post   use_count() == 1 && get() == __p
     *  @throw  std::bad_alloc, in which case @a __d(__p) is called.
     *
     *  Requirements: _Deleter's copy constructor and destructor must
     *  not throw _Alloc's copy constructor and destructor must not
     *  throw.
     *
     *  __shared_ptr will release __p by calling __d(__p)
     */
    template<typename _Tp1, typename _Deleter, typename _Alloc>
shared_ptr(_Tp1* __p, _Deleter __d, _Alloc __a)
: __shared_ptr<_Tp>(__p, __d, std::move(__a)) { }

    /**
     *  @brief  Construct a %shared_ptr that owns a null pointer
     *          and the deleter @a __d.
     *  @param  __p  A null pointer constant.
     *  @param  __d  A deleter.
     *  @param  __a  An allocator.
     *  @post   use_count() == 1 && get() == __p
     *  @throw  std::bad_alloc, in which case @a __d(__p) is called.
     *
     *  Requirements: _Deleter's copy constructor and destructor must
     *  not throw _Alloc's copy constructor and destructor must not
     *  throw.
     *
     *  The last owner will call __d(__p)
     */
    template<typename _Deleter, typename _Alloc>
shared_ptr(nullptr_t __p, _Deleter __d, _Alloc __a)
: __shared_ptr<_Tp>(__p, __d, std::move(__a)) { }

    // Aliasing constructor

    /**
     *  @brief  Constructs a %shared_ptr instance that stores @a __p
     *          and shares ownership with @a __r.
     *  @param  __r  A %shared_ptr.
     *  @param  __p  A pointer that will remain valid while @a *__r is valid.
     *  @post   get() == __p && use_count() == __r.use_count()
     *
     *  This can be used to construct a @c shared_ptr to a sub-object
     *  of an object managed by an existing @c shared_ptr.
     *
     * @code
     * shared_ptr< pair<int,int> > pii(new pair<int,int>());
     * shared_ptr<int> pi(pii, &pii->first);
     * assert(pii.use_count() == 2);
     * @endcode
     */
    template<typename _Tp1>
shared_ptr(const shared_ptr<_Tp1>& __r, _Tp* __p) noexcept
: __shared_ptr<_Tp>(__r, __p) { }

    /**
     *  @brief  If @a __r is empty, constructs an empty %shared_ptr;
     *          otherwise construct a %shared_ptr that shares ownership
     *          with @a __r.
     *  @param  __r  A %shared_ptr.
     *  @post   get() == __r.get() && use_count() == __r.use_count()
     */
    template<typename _Tp1, typename = _Convertible<_Tp1*>>
shared_ptr(const shared_ptr<_Tp1>& __r) noexcept
      : __shared_ptr<_Tp>(__r) { }

    /**
     *  @brief  Move-constructs a %shared_ptr instance from @a __r.
     *  @param  __r  A %shared_ptr rvalue.
     *  @post   *this contains the old value of @a __r, @a __r is empty.
     */
    shared_ptr(shared_ptr&& __r) noexcept
    : __shared_ptr<_Tp>(std::move(__r)) { }

    /**
     *  @brief  Move-constructs a %shared_ptr instance from @a __r.
     *  @param  __r  A %shared_ptr rvalue.
     *  @post   *this contains the old value of @a __r, @a __r is empty.
     */
    template<typename _Tp1, typename = _Convertible<_Tp1*>>
shared_ptr(shared_ptr<_Tp1>&& __r) noexcept
: __shared_ptr<_Tp>(std::move(__r)) { }

    /**
     *  @brief  Constructs a %shared_ptr that shares ownership with @a __r
     *          and stores a copy of the pointer stored in @a __r.
     *  @param  __r  A weak_ptr.
     *  @post   use_count() == __r.use_count()
     *  @throw  bad_weak_ptr when __r.expired(),
     *          in which case the constructor has no effect.
     */
    template<typename _Tp1>
explicit shared_ptr(const weak_ptr<_Tp1>& __r)
: __shared_ptr<_Tp>(__r) { }

253#if _GLIBCXX_USE_DEPRECATED1
    template<typename _Tp1>
shared_ptr(std::auto_ptr<_Tp1>&& __r);
256#endif

    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // 2399. shared_ptr's constructor from unique_ptr should be constrained
    template<typename _Tp1, typename _Del, typename
      = _Convertible<typename unique_ptr<_Tp1, _Del>::pointer>>
shared_ptr(std::unique_ptr<_Tp1, _Del>&& __r)
: __shared_ptr<_Tp>(std::move(__r)) { }

    /**
     *  @brief  Construct an empty %shared_ptr.
     *  @post   use_count() == 0 && get() == nullptr
     */
    constexpr shared_ptr(nullptr_t) noexcept : shared_ptr() { }

    shared_ptr& operator=(const shared_ptr&) noexcept = default;

    template<typename _Tp1>
shared_ptr&
operator=(const shared_ptr<_Tp1>& __r) noexcept
{
 this->__shared_ptr<_Tp>::operator=(__r);
 return *this;
}

281#if _GLIBCXX_USE_DEPRECATED1
    template<typename _Tp1>
shared_ptr&
operator=(std::auto_ptr<_Tp1>&& __r)
{
 this->__shared_ptr<_Tp>::operator=(std::move(__r));
 return *this;
}
289#endif

    shared_ptr&
    operator=(shared_ptr&& __r) noexcept
    {
this->__shared_ptr<_Tp>::operator=(std::move(__r));
return *this;
    }

    template<class _Tp1>
shared_ptr&
operator=(shared_ptr<_Tp1>&& __r) noexcept
{
 this->__shared_ptr<_Tp>::operator=(std::move(__r));
 return *this;
}

    template<typename _Tp1, typename _Del>
shared_ptr&
operator=(std::unique_ptr<_Tp1, _Del>&& __r)
{
 this->__shared_ptr<_Tp>::operator=(std::move(__r));
 return *this;
}

  private:
    // This constructor is non-standard, it is used by allocate_shared.
    template<typename _Alloc, typename... _Args>
shared_ptr(_Sp_make_shared_tag __tag, const _Alloc& __a,
   _Args&&... __args)
: __shared_ptr<_Tp>(__tag, __a, std::forward<_Args>(__args)...)
16
←
Calling constructor for '__shared_ptr<llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata>>::PoolEntry, __gnu_cxx::_S_atomic>'→
{ }

    template<typename _Tp1, typename _Alloc, typename... _Args>
friend shared_ptr<_Tp1>
allocate_shared(const _Alloc& __a, _Args&&... __args);

    // This constructor is non-standard, it is used by weak_ptr::lock().
    shared_ptr(const weak_ptr<_Tp>& __r, std::nothrow_t)
    : __shared_ptr<_Tp>(__r, std::nothrow) { }

    friend class weak_ptr<_Tp>;
  };

// 20.7.2.2.7 shared_ptr comparisons
template<typename _Tp1, typename _Tp2>
  inline bool
  operator==(const shared_ptr<_Tp1>& __a,
      const shared_ptr<_Tp2>& __b) noexcept
  { return __a.get() == __b.get(); }

template<typename _Tp>
  inline bool
  operator==(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
  { return !__a; }

template<typename _Tp>
  inline bool
  operator==(nullptr_t, const shared_ptr<_Tp>& __a) noexcept
  { return !__a; }

template<typename _Tp1, typename _Tp2>
  inline bool
  operator!=(const shared_ptr<_Tp1>& __a,
      const shared_ptr<_Tp2>& __b) noexcept
  { return __a.get() != __b.get(); }

template<typename _Tp>
  inline bool
  operator!=(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
  { return (bool)__a; }

template<typename _Tp>
  inline bool
  operator!=(nullptr_t, const shared_ptr<_Tp>& __a) noexcept
  { return (bool)__a; }

template<typename _Tp1, typename _Tp2>
  inline bool
  operator<(const shared_ptr<_Tp1>& __a,
     const shared_ptr<_Tp2>& __b) noexcept
  {
    typedef typename std::common_type<_Tp1*, _Tp2*>::type _CT;
    return std::less<_CT>()(__a.get(), __b.get());
  }

template<typename _Tp>
  inline bool
  operator<(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
  { return std::less<_Tp*>()(__a.get(), nullptr); }

template<typename _Tp>
  inline bool
  operator<(nullptr_t, const shared_ptr<_Tp>& __a) noexcept
  { return std::less<_Tp*>()(nullptr, __a.get()); }

template<typename _Tp1, typename _Tp2>
  inline bool
  operator<=(const shared_ptr<_Tp1>& __a,
      const shared_ptr<_Tp2>& __b) noexcept
  { return !(__b < __a); }

template<typename _Tp>
  inline bool
  operator<=(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
  { return !(nullptr < __a); }

template<typename _Tp>
  inline bool
  operator<=(nullptr_t, const shared_ptr<_Tp>& __a) noexcept
  { return !(__a < nullptr); }

template<typename _Tp1, typename _Tp2>
  inline bool
  operator>(const shared_ptr<_Tp1>& __a,
     const shared_ptr<_Tp2>& __b) noexcept
  { return (__b < __a); }

template<typename _Tp>
  inline bool
  operator>(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
  { return std::less<_Tp*>()(nullptr, __a.get()); }

template<typename _Tp>
  inline bool
  operator>(nullptr_t, const shared_ptr<_Tp>& __a) noexcept
  { return std::less<_Tp*>()(__a.get(), nullptr); }

template<typename _Tp1, typename _Tp2>
  inline bool
  operator>=(const shared_ptr<_Tp1>& __a,
      const shared_ptr<_Tp2>& __b) noexcept
  { return !(__a < __b); }

template<typename _Tp>
  inline bool
  operator>=(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
  { return !(__a < nullptr); }

template<typename _Tp>
  inline bool
  operator>=(nullptr_t, const shared_ptr<_Tp>& __a) noexcept
  { return !(nullptr < __a); }

template<typename _Tp>
  struct less<shared_ptr<_Tp>> : public _Sp_less<shared_ptr<_Tp>>
  { };

// 20.7.2.2.8 shared_ptr specialized algorithms.
template<typename _Tp>
  inline void
  swap(shared_ptr<_Tp>& __a, shared_ptr<_Tp>& __b) noexcept
  { __a.swap(__b); }

// 20.7.2.2.9 shared_ptr casts.
template<typename _Tp, typename _Tp1>
  inline shared_ptr<_Tp>
  static_pointer_cast(const shared_ptr<_Tp1>& __r) noexcept
  { return shared_ptr<_Tp>(__r, static_cast<_Tp*>(__r.get())); }

template<typename _Tp, typename _Tp1>
  inline shared_ptr<_Tp>
  const_pointer_cast(const shared_ptr<_Tp1>& __r) noexcept
  { return shared_ptr<_Tp>(__r, const_cast<_Tp*>(__r.get())); }

template<typename _Tp, typename _Tp1>
  inline shared_ptr<_Tp>
  dynamic_pointer_cast(const shared_ptr<_Tp1>& __r) noexcept
  {
    if (_Tp* __p = dynamic_cast<_Tp*>(__r.get()))
return shared_ptr<_Tp>(__r, __p);
    return shared_ptr<_Tp>();
  }


/**
 *  @brief  A smart pointer with weak semantics.
 *
 *  With forwarding constructors and assignment operators.
 */
template<typename _Tp>
  class weak_ptr : public __weak_ptr<_Tp>
  {
    template<typename _Ptr>
using _Convertible
 = typename enable_if<is_convertible<_Ptr, _Tp*>::value>::type;

  public:
    constexpr weak_ptr() noexcept = default;

    template<typename _Tp1, typename = _Convertible<_Tp1*>>
weak_ptr(const shared_ptr<_Tp1>& __r) noexcept
: __weak_ptr<_Tp>(__r) { }

    weak_ptr(const weak_ptr&) noexcept = default;

    template<typename _Tp1, typename = _Convertible<_Tp1*>>
weak_ptr(const weak_ptr<_Tp1>& __r) noexcept
: __weak_ptr<_Tp>(__r) { }

    weak_ptr(weak_ptr&&) noexcept = default;

    template<typename _Tp1, typename = _Convertible<_Tp1*>>
weak_ptr(weak_ptr<_Tp1>&& __r) noexcept
: __weak_ptr<_Tp>(std::move(__r)) { }

    weak_ptr&
    operator=(const weak_ptr& __r) noexcept = default;

    template<typename _Tp1>
weak_ptr&
operator=(const weak_ptr<_Tp1>& __r) noexcept
{
 this->__weak_ptr<_Tp>::operator=(__r);
 return *this;
}

    template<typename _Tp1>
weak_ptr&
operator=(const shared_ptr<_Tp1>& __r) noexcept
{
 this->__weak_ptr<_Tp>::operator=(__r);
 return *this;
}

    weak_ptr&
    operator=(weak_ptr&& __r) noexcept = default;

    template<typename _Tp1>
weak_ptr&
operator=(weak_ptr<_Tp1>&& __r) noexcept
{
 this->__weak_ptr<_Tp>::operator=(std::move(__r));
 return *this;
}

    shared_ptr<_Tp>
    lock() const noexcept
    { return shared_ptr<_Tp>(*this, std::nothrow); }
  };

// 20.7.2.3.6 weak_ptr specialized algorithms.
template<typename _Tp>
  inline void
  swap(weak_ptr<_Tp>& __a, weak_ptr<_Tp>& __b) noexcept
  { __a.swap(__b); }


/// Primary template owner_less
template<typename _Tp>
  struct owner_less;

/// Partial specialization of owner_less for shared_ptr.
template<typename _Tp>
  struct owner_less<shared_ptr<_Tp>>
  : public _Sp_owner_less<shared_ptr<_Tp>, weak_ptr<_Tp>>
  { };

/// Partial specialization of owner_less for weak_ptr.
template<typename _Tp>
  struct owner_less<weak_ptr<_Tp>>
  : public _Sp_owner_less<weak_ptr<_Tp>, shared_ptr<_Tp>>
  { };

/**
 *  @brief Base class allowing use of member function shared_from_this.
 */
template<typename _Tp>
  class enable_shared_from_this
  {
  protected:
    constexpr enable_shared_from_this() noexcept { }

    enable_shared_from_this(const enable_shared_from_this&) noexcept { }

    enable_shared_from_this&
    operator=(const enable_shared_from_this&) noexcept
    { return *this; }

    ~enable_shared_from_this() { }

  public:
    shared_ptr<_Tp>
    shared_from_this()
    { return shared_ptr<_Tp>(this->_M_weak_this); }

    shared_ptr<const _Tp>
    shared_from_this() const
    { return shared_ptr<const _Tp>(this->_M_weak_this); }

  private:
    template<typename _Tp1>
void
_M_weak_assign(_Tp1* __p, const __shared_count<>& __n) const noexcept
{ _M_weak_this._M_assign(__p, __n); }

    template<typename _Tp1, typename _Tp2>
friend void
__enable_shared_from_this_helper(const __shared_count<>&,
			 const enable_shared_from_this<_Tp1>*,
			 const _Tp2*) noexcept;

    mutable weak_ptr<_Tp>  _M_weak_this;
  };

template<typename _Tp1, typename _Tp2>
  inline void
  __enable_shared_from_this_helper(const __shared_count<>& __pn,
		     const enable_shared_from_this<_Tp1>*
		     __pe, const _Tp2* __px) noexcept
  {
    if (__pe != nullptr)
__pe->_M_weak_assign(const_cast<_Tp2*>(__px), __pn);
  }

/**
 *  @brief  Create an object that is owned by a shared_ptr.
 *  @param  __a     An allocator.
 *  @param  __args  Arguments for the @a _Tp object's constructor.
 *  @return A shared_ptr that owns the newly created object.
 *  @throw  An exception thrown from @a _Alloc::allocate or from the
 *          constructor of @a _Tp.
 *
 *  A copy of @a __a will be used to allocate memory for the shared_ptr
 *  and the new object.
 */
template<typename _Tp, typename _Alloc, typename... _Args>
  inline shared_ptr<_Tp>
  allocate_shared(const _Alloc& __a, _Args&&... __args)
  {
    return shared_ptr<_Tp>(_Sp_make_shared_tag(), __a,
15
←
Calling constructor for 'shared_ptr<llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata>>::PoolEntry>'→
	     std::forward<_Args>(__args)...);
  }

/**
 *  @brief  Create an object that is owned by a shared_ptr.
 *  @param  __args  Arguments for the @a _Tp object's constructor.
 *  @return A shared_ptr that owns the newly created object.
 *  @throw  std::bad_alloc, or an exception thrown from the
 *          constructor of @a _Tp.
 */
template<typename _Tp, typename... _Args>
  inline shared_ptr<_Tp>
  make_shared(_Args&&... __args)
  {
    typedef typename std::remove_const<_Tp>::type _Tp_nc;
    return std::allocate_shared<_Tp>(std::allocator<_Tp_nc>(),
14
←
Calling 'allocate_shared<llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata>>::PoolEntry, std::allocator<llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata>>::PoolEntry>, llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata>> &, llvm::PBQP::Matrix>'→
		       std::forward<_Args>(__args)...);
  }

/// std::hash specialization for shared_ptr.
template<typename _Tp>
  struct hash<shared_ptr<_Tp>>
  : public __hash_base<size_t, shared_ptr<_Tp>>
  {
    size_t
    operator()(const shared_ptr<_Tp>& __s) const noexcept
    { return std::hash<_Tp*>()(__s.get()); }
  };

// @} group pointer_abstractions

651_GLIBCXX_END_NAMESPACE_VERSION
652} // namespace

654#endif // _SHARED_PTR_H

←

/usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/bits/shared_ptr_base.h

→

1// shared_ptr and weak_ptr implementation details -*- C++ -*-

3// Copyright (C) 2007-2016 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.

11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.

16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.

20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.

25// GCC Note: Based on files from version 1.32.0 of the Boost library.

27//  shared_count.hpp
28//  Copyright (c) 2001, 2002, 2003 Peter Dimov and Multi Media Ltd.

30//  shared_ptr.hpp
31//  Copyright (C) 1998, 1999 Greg Colvin and Beman Dawes.
32//  Copyright (C) 2001, 2002, 2003 Peter Dimov

34//  weak_ptr.hpp
35//  Copyright (C) 2001, 2002, 2003 Peter Dimov

37//  enable_shared_from_this.hpp
38//  Copyright (C) 2002 Peter Dimov

40// Distributed under the Boost Software License, Version 1.0. (See
41// accompanying file LICENSE_1_0.txt or copy at
42// http://www.boost.org/LICENSE_1_0.txt)

44/** @file bits/shared_ptr_base.h
*  This is an internal header file, included by other library headers.
*  Do not attempt to use it directly. @headername{memory}
*/

49#ifndef _SHARED_PTR_BASE_H1
50#define _SHARED_PTR_BASE_H1 1

52#include <typeinfo>
53#include <bits/allocated_ptr.h>
54#include <ext/aligned_buffer.h>

56namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
57{
58_GLIBCXX_BEGIN_NAMESPACE_VERSION

60#if _GLIBCXX_USE_DEPRECATED1
template<typename> class auto_ptr;
62#endif

/**
 *  @brief  Exception possibly thrown by @c shared_ptr.
 *  @ingroup exceptions
 */
class bad_weak_ptr : public std::exception
{
public:
  virtual char const* what() const noexcept;

  virtual ~bad_weak_ptr() noexcept;    
};

// Substitute for bad_weak_ptr object in the case of -fno-exceptions.
inline void
__throw_bad_weak_ptr()
{ _GLIBCXX_THROW_OR_ABORT(bad_weak_ptr())(__builtin_abort()); }

using __gnu_cxx::_Lock_policy;
using __gnu_cxx::__default_lock_policy;
using __gnu_cxx::_S_single;
using __gnu_cxx::_S_mutex;
using __gnu_cxx::_S_atomic;

// Empty helper class except when the template argument is _S_mutex.
template<_Lock_policy _Lp>
  class _Mutex_base
  {
  protected:
    // The atomic policy uses fully-fenced builtins, single doesn't care.
    enum { _S_need_barriers = 0 };
  };

template<>
  class _Mutex_base<_S_mutex>
  : public __gnu_cxx::__mutex
  {
  protected:
    // This policy is used when atomic builtins are not available.
    // The replacement atomic operations might not have the necessary
    // memory barriers.
    enum { _S_need_barriers = 1 };
  };

template<_Lock_policy _Lp = __default_lock_policy>
  class _Sp_counted_base
  : public _Mutex_base<_Lp>
  {
  public:  
    _Sp_counted_base() noexcept
    : _M_use_count(1), _M_weak_count(1) { }
    
    virtual
    ~_Sp_counted_base() noexcept
    { }

    // Called when _M_use_count drops to zero, to release the resources
    // managed by *this.
    virtual void
    _M_dispose() noexcept = 0;
    
    // Called when _M_weak_count drops to zero.
    virtual void
    _M_destroy() noexcept
    { delete this; }
    
    virtual void*
    _M_get_deleter(const std::type_info&) noexcept = 0;

    void
    _M_add_ref_copy()
    { __gnu_cxx::__atomic_add_dispatch(&_M_use_count, 1); }

    void
    _M_add_ref_lock();

    bool
    _M_add_ref_lock_nothrow();

    void
    _M_release() noexcept
    {
      // Be race-detector-friendly.  For more info see bits/c++config.
      _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&_M_use_count);
if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, -1) == 1)
 {
          _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&_M_use_count);
   _M_dispose();
   // There must be a memory barrier between dispose() and destroy()
   // to ensure that the effects of dispose() are observed in the
   // thread that runs destroy().
   // See http://gcc.gnu.org/ml/libstdc++/2005-11/msg00136.html
   if (_Mutex_base<_Lp>::_S_need_barriers)
     {
__atomic_thread_fence (__ATOMIC_ACQ_REL4);
     }

          // Be race-detector-friendly.  For more info see bits/c++config.
          _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&_M_weak_count);
   if (__gnu_cxx::__exchange_and_add_dispatch(&_M_weak_count,
				       -1) == 1)
            {
              _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&_M_weak_count);
       _M_destroy();
            }
 }
    }

    void
    _M_weak_add_ref() noexcept
    { __gnu_cxx::__atomic_add_dispatch(&_M_weak_count, 1); }

    void
    _M_weak_release() noexcept
    {
      // Be race-detector-friendly. For more info see bits/c++config.
      _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&_M_weak_count);
if (__gnu_cxx::__exchange_and_add_dispatch(&_M_weak_count, -1) == 1)
 {
          _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&_M_weak_count);
   if (_Mutex_base<_Lp>::_S_need_barriers)
     {
       // See _M_release(),
       // destroy() must observe results of dispose()
__atomic_thread_fence (__ATOMIC_ACQ_REL4);
     }
   _M_destroy();
 }
    }

    long
    _M_get_use_count() const noexcept
    {
      // No memory barrier is used here so there is no synchronization
      // with other threads.
      return __atomic_load_n(&_M_use_count, __ATOMIC_RELAXED0);
    }

  private:  
    _Sp_counted_base(_Sp_counted_base const&) = delete;
    _Sp_counted_base& operator=(_Sp_counted_base const&) = delete;

    _Atomic_word  _M_use_count;     // #shared
    _Atomic_word  _M_weak_count;    // #weak + (#shared != 0)
  };

template<>
  inline void
  _Sp_counted_base<_S_single>::
  _M_add_ref_lock()
  {
    if (_M_use_count == 0)
__throw_bad_weak_ptr();
    ++_M_use_count;
  }

template<>
  inline void
  _Sp_counted_base<_S_mutex>::
  _M_add_ref_lock()
  {
    __gnu_cxx::__scoped_lock sentry(*this);
    if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, 1) == 0)
{
 _M_use_count = 0;
 __throw_bad_weak_ptr();
}
  }

template<> 
  inline void
  _Sp_counted_base<_S_atomic>::
  _M_add_ref_lock()
  {
    // Perform lock-free add-if-not-zero operation.
    _Atomic_word __count = _M_get_use_count();
    do
{
 if (__count == 0)
   __throw_bad_weak_ptr();
 // Replace the current counter value with the old value + 1, as
 // long as it's not changed meanwhile. 
}
    while (!__atomic_compare_exchange_n(&_M_use_count, &__count, __count + 1,
			  true, __ATOMIC_ACQ_REL4, 
			  __ATOMIC_RELAXED0));
  }

template<>
  inline bool
  _Sp_counted_base<_S_single>::
  _M_add_ref_lock_nothrow()
  {
    if (_M_use_count == 0)
return false;
    ++_M_use_count;
    return true;
  }

template<>
  inline bool
  _Sp_counted_base<_S_mutex>::
  _M_add_ref_lock_nothrow()
  {
    __gnu_cxx::__scoped_lock sentry(*this);
    if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, 1) == 0)
{
 _M_use_count = 0;
 return false;
}
    return true;
  }

template<>
  inline bool
  _Sp_counted_base<_S_atomic>::
  _M_add_ref_lock_nothrow()
  {
    // Perform lock-free add-if-not-zero operation.
    _Atomic_word __count = _M_get_use_count();
    do
{
 if (__count == 0)
   return false;
 // Replace the current counter value with the old value + 1, as
 // long as it's not changed meanwhile.
}
    while (!__atomic_compare_exchange_n(&_M_use_count, &__count, __count + 1,
			  true, __ATOMIC_ACQ_REL4,
			  __ATOMIC_RELAXED0));
    return true;
  }

template<>
  inline void
  _Sp_counted_base<_S_single>::_M_add_ref_copy()
  { ++_M_use_count; }

template<>
  inline void
  _Sp_counted_base<_S_single>::_M_release() noexcept
  {
    if (--_M_use_count == 0)
      {
        _M_dispose();
        if (--_M_weak_count == 0)
          _M_destroy();
      }
  }

template<>
  inline void
  _Sp_counted_base<_S_single>::_M_weak_add_ref() noexcept
  { ++_M_weak_count; }

template<>
  inline void
  _Sp_counted_base<_S_single>::_M_weak_release() noexcept
  {
    if (--_M_weak_count == 0)
      _M_destroy();
  }

template<>
  inline long
  _Sp_counted_base<_S_single>::_M_get_use_count() const noexcept
  { return _M_use_count; }


// Forward declarations.
template<typename _Tp, _Lock_policy _Lp = __default_lock_policy>
  class __shared_ptr;

template<typename _Tp, _Lock_policy _Lp = __default_lock_policy>
  class __weak_ptr;

template<typename _Tp, _Lock_policy _Lp = __default_lock_policy>
  class __enable_shared_from_this;

template<typename _Tp>
  class shared_ptr;

template<typename _Tp>
  class weak_ptr;

template<typename _Tp>
  struct owner_less;

template<typename _Tp>
  class enable_shared_from_this;

template<_Lock_policy _Lp = __default_lock_policy>
  class __weak_count;

template<_Lock_policy _Lp = __default_lock_policy>
  class __shared_count;


// Counted ptr with no deleter or allocator support
template<typename _Ptr, _Lock_policy _Lp>
  class _Sp_counted_ptr final : public _Sp_counted_base<_Lp>
  {
  public:
    explicit
    _Sp_counted_ptr(_Ptr __p) noexcept
    : _M_ptr(__p) { }

    virtual void
    _M_dispose() noexcept
    { delete _M_ptr; }

    virtual void
    _M_destroy() noexcept
    { delete this; }

    virtual void*
    _M_get_deleter(const std::type_info&) noexcept
    { return nullptr; }

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

  private:
    _Ptr             _M_ptr;
  };

template<>
  inline void
  _Sp_counted_ptr<nullptr_t, _S_single>::_M_dispose() noexcept { }

template<>
  inline void
  _Sp_counted_ptr<nullptr_t, _S_mutex>::_M_dispose() noexcept { }

template<>
  inline void
  _Sp_counted_ptr<nullptr_t, _S_atomic>::_M_dispose() noexcept { }

template<int _Nm, typename _Tp,
  bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
  struct _Sp_ebo_helper;

/// Specialization using EBO.
template<int _Nm, typename _Tp>
  struct _Sp_ebo_helper<_Nm, _Tp, true> : private _Tp
  {
    explicit _Sp_ebo_helper(const _Tp& __tp) : _Tp(__tp) { }

    static _Tp&
    _S_get(_Sp_ebo_helper& __eboh) { return static_cast<_Tp&>(__eboh); }
  };

/// Specialization not using EBO.
template<int _Nm, typename _Tp>
  struct _Sp_ebo_helper<_Nm, _Tp, false>
  {
    explicit _Sp_ebo_helper(const _Tp& __tp) : _M_tp(__tp) { }

    static _Tp&
    _S_get(_Sp_ebo_helper& __eboh)
    { return __eboh._M_tp; }

  private:
    _Tp _M_tp;
  };

// Support for custom deleter and/or allocator
template<typename _Ptr, typename _Deleter, typename _Alloc, _Lock_policy _Lp>
  class _Sp_counted_deleter final : public _Sp_counted_base<_Lp>
  {
    class _Impl : _Sp_ebo_helper<0, _Deleter>, _Sp_ebo_helper<1, _Alloc>
    {
typedef _Sp_ebo_helper<0, _Deleter>	_Del_base;
typedef _Sp_ebo_helper<1, _Alloc>	_Alloc_base;

    public:
_Impl(_Ptr __p, _Deleter __d, const _Alloc& __a) noexcept
: _M_ptr(__p), _Del_base(__d), _Alloc_base(__a)
{ }

_Deleter& _M_del() noexcept { return _Del_base::_S_get(*this); }
_Alloc& _M_alloc() noexcept { return _Alloc_base::_S_get(*this); }

_Ptr _M_ptr;
    };

  public:
    using __allocator_type = __alloc_rebind<_Alloc, _Sp_counted_deleter>;

    // __d(__p) must not throw.
    _Sp_counted_deleter(_Ptr __p, _Deleter __d) noexcept
    : _M_impl(__p, __d, _Alloc()) { }

    // __d(__p) must not throw.
    _Sp_counted_deleter(_Ptr __p, _Deleter __d, const _Alloc& __a) noexcept
    : _M_impl(__p, __d, __a) { }

    ~_Sp_counted_deleter() noexcept { }

    virtual void
    _M_dispose() noexcept
    { _M_impl._M_del()(_M_impl._M_ptr); }

    virtual void
    _M_destroy() noexcept
    {
__allocator_type __a(_M_impl._M_alloc());
__allocated_ptr<__allocator_type> __guard_ptr{ __a, this };
this->~_Sp_counted_deleter();
    }

    virtual void*
    _M_get_deleter(const std::type_info& __ti) noexcept
    {
477#if __cpp_rtti199711L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 2400. shared_ptr's get_deleter() should use addressof()
      return __ti == typeid(_Deleter)
 ? std::__addressof(_M_impl._M_del())
 : nullptr;
483#else
      return nullptr;
485#endif
    }

  private:
    _Impl _M_impl;
  };

// helpers for make_shared / allocate_shared

struct _Sp_make_shared_tag { };

template<typename _Tp, typename _Alloc, _Lock_policy _Lp>
  class _Sp_counted_ptr_inplace final : public _Sp_counted_base<_Lp>
  {
    class _Impl : _Sp_ebo_helper<0, _Alloc>
    {
typedef _Sp_ebo_helper<0, _Alloc>	_A_base;

    public:
explicit _Impl(_Alloc __a) noexcept : _A_base(__a) { }

_Alloc& _M_alloc() noexcept { return _A_base::_S_get(*this); }

__gnu_cxx::__aligned_buffer<_Tp> _M_storage;
    };

  public:
    using __allocator_type = __alloc_rebind<_Alloc, _Sp_counted_ptr_inplace>;

    template<typename... _Args>
_Sp_counted_ptr_inplace(_Alloc __a, _Args&&... __args)
: _M_impl(__a)
{
 // _GLIBCXX_RESOLVE_LIB_DEFECTS
 // 2070.  allocate_shared should use allocator_traits<A>::construct
 allocator_traits<_Alloc>::construct(__a, _M_ptr(),
19
←
Calling 'allocator_traits::construct'→
     std::forward<_Args>(__args)...); // might throw
}

    ~_Sp_counted_ptr_inplace() noexcept { }

    virtual void
    _M_dispose() noexcept
    {
allocator_traits<_Alloc>::destroy(_M_impl._M_alloc(), _M_ptr());
    }

    // Override because the allocator needs to know the dynamic type
    virtual void
    _M_destroy() noexcept
    {
__allocator_type __a(_M_impl._M_alloc());
__allocated_ptr<__allocator_type> __guard_ptr{ __a, this };
this->~_Sp_counted_ptr_inplace();
    }

    // Sneaky trick so __shared_ptr can get the managed pointer
    virtual void*
    _M_get_deleter(const std::type_info& __ti) noexcept
    {
545#if __cpp_rtti199711L
if (__ti == typeid(_Sp_make_shared_tag))
 return const_cast<typename remove_cv<_Tp>::type*>(_M_ptr());
548#endif
return nullptr;
    }

  private:
    _Tp* _M_ptr() noexcept { return _M_impl._M_storage._M_ptr(); }

    _Impl _M_impl;
  };


template<_Lock_policy _Lp>
  class __shared_count
  {
  public:
    constexpr __shared_count() noexcept : _M_pi(0)
    { }

    template<typename _Ptr>
      explicit
__shared_count(_Ptr __p) : _M_pi(0)
{
 __tryif (true)
   {
     _M_pi = new _Sp_counted_ptr<_Ptr, _Lp>(__p);
   }
 __catch(...)if (false)
   {
     delete __p;
     __throw_exception_again;
   }
}

    template<typename _Ptr, typename _Deleter>
__shared_count(_Ptr __p, _Deleter __d)
: __shared_count(__p, std::move(__d), allocator<void>())
{ }

    template<typename _Ptr, typename _Deleter, typename _Alloc>
__shared_count(_Ptr __p, _Deleter __d, _Alloc __a) : _M_pi(0)
{
 typedef _Sp_counted_deleter<_Ptr, _Deleter, _Alloc, _Lp> _Sp_cd_type;
 __tryif (true)
   {
     typename _Sp_cd_type::__allocator_type __a2(__a);
     auto __guard = std::__allocate_guarded(__a2);
     _Sp_cd_type* __mem = __guard.get();
     ::new (__mem) _Sp_cd_type(__p, std::move(__d), std::move(__a));
     _M_pi = __mem;
     __guard = nullptr;
   }
 __catch(...)if (false)
   {
     __d(__p); // Call _Deleter on __p.
     __throw_exception_again;
   }
}

    template<typename _Tp, typename _Alloc, typename... _Args>
__shared_count(_Sp_make_shared_tag, _Tp*, const _Alloc& __a,
       _Args&&... __args)
: _M_pi(0)
{
 typedef _Sp_counted_ptr_inplace<_Tp, _Alloc, _Lp> _Sp_cp_type;
 typename _Sp_cp_type::__allocator_type __a2(__a);
 auto __guard = std::__allocate_guarded(__a2);
 _Sp_cp_type* __mem = __guard.get();
 ::new (__mem) _Sp_cp_type(std::move(__a),
18
←
Calling constructor for '_Sp_counted_ptr_inplace<llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata>>::PoolEntry, std::allocator<llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata>>::PoolEntry>, __gnu_cxx::_S_atomic>'→
		    std::forward<_Args>(__args)...);
 _M_pi = __mem;
 __guard = nullptr;
}

621#if _GLIBCXX_USE_DEPRECATED1
    // Special case for auto_ptr<_Tp> to provide the strong guarantee.
    template<typename _Tp>
      explicit
__shared_count(std::auto_ptr<_Tp>&& __r);
626#endif

    // Special case for unique_ptr<_Tp,_Del> to provide the strong guarantee.
    template<typename _Tp, typename _Del>
      explicit
__shared_count(std::unique_ptr<_Tp, _Del>&& __r) : _M_pi(0)
{
 // _GLIBCXX_RESOLVE_LIB_DEFECTS
 // 2415. Inconsistency between unique_ptr and shared_ptr
 if (__r.get() == nullptr)
   return;

 using _Ptr = typename unique_ptr<_Tp, _Del>::pointer;
 using _Del2 = typename conditional<is_reference<_Del>::value,
     reference_wrapper<typename remove_reference<_Del>::type>,
     _Del>::type;
 using _Sp_cd_type
   = _Sp_counted_deleter<_Ptr, _Del2, allocator<void>, _Lp>;
 using _Alloc = allocator<_Sp_cd_type>;
 using _Alloc_traits = allocator_traits<_Alloc>;
 _Alloc __a;
 _Sp_cd_type* __mem = _Alloc_traits::allocate(__a, 1);
 _Alloc_traits::construct(__a, __mem, __r.release(),
		   __r.get_deleter());  // non-throwing
 _M_pi = __mem;
}

    // Throw bad_weak_ptr when __r._M_get_use_count() == 0.
    explicit __shared_count(const __weak_count<_Lp>& __r);

    // Does not throw if __r._M_get_use_count() == 0, caller must check.
    explicit __shared_count(const __weak_count<_Lp>& __r, std::nothrow_t);

    ~__shared_count() noexcept
    {
if (_M_pi != nullptr)
 _M_pi->_M_release();
    }

    __shared_count(const __shared_count& __r) noexcept
    : _M_pi(__r._M_pi)
    {
if (_M_pi != 0)
 _M_pi->_M_add_ref_copy();
    }

    __shared_count&
    operator=(const __shared_count& __r) noexcept
    {
_Sp_counted_base<_Lp>* __tmp = __r._M_pi;
if (__tmp != _M_pi)
 {
   if (__tmp != 0)
     __tmp->_M_add_ref_copy();
   if (_M_pi != 0)
     _M_pi->_M_release();
   _M_pi = __tmp;
 }
return *this;
    }

    void
    _M_swap(__shared_count& __r) noexcept
    {
_Sp_counted_base<_Lp>* __tmp = __r._M_pi;
__r._M_pi = _M_pi;
_M_pi = __tmp;
    }

    long
    _M_get_use_count() const noexcept
    { return _M_pi != 0 ? _M_pi->_M_get_use_count() : 0; }

    bool
    _M_unique() const noexcept
    { return this->_M_get_use_count() == 1; }

    void*
    _M_get_deleter(const std::type_info& __ti) const noexcept
    { return _M_pi ? _M_pi->_M_get_deleter(__ti) : nullptr; }

    bool
    _M_less(const __shared_count& __rhs) const noexcept
    { return std::less<_Sp_counted_base<_Lp>*>()(this->_M_pi, __rhs._M_pi); }

    bool
    _M_less(const __weak_count<_Lp>& __rhs) const noexcept
    { return std::less<_Sp_counted_base<_Lp>*>()(this->_M_pi, __rhs._M_pi); }

    // Friend function injected into enclosing namespace and found by ADL
    friend inline bool
    operator==(const __shared_count& __a, const __shared_count& __b) noexcept
    { return __a._M_pi == __b._M_pi; }

  private:
    friend class __weak_count<_Lp>;

    _Sp_counted_base<_Lp>*  _M_pi;
  };


template<_Lock_policy _Lp>
  class __weak_count
  {
  public:
    constexpr __weak_count() noexcept : _M_pi(nullptr)
    { }

    __weak_count(const __shared_count<_Lp>& __r) noexcept
    : _M_pi(__r._M_pi)
    {
if (_M_pi != nullptr)
 _M_pi->_M_weak_add_ref();
    }

    __weak_count(const __weak_count& __r) noexcept
    : _M_pi(__r._M_pi)
    {
if (_M_pi != nullptr)
 _M_pi->_M_weak_add_ref();
    }

    __weak_count(__weak_count&& __r) noexcept
    : _M_pi(__r._M_pi)
    { __r._M_pi = nullptr; }

    ~__weak_count() noexcept
    {
if (_M_pi != nullptr)
 _M_pi->_M_weak_release();
    }

    __weak_count&
    operator=(const __shared_count<_Lp>& __r) noexcept
    {
_Sp_counted_base<_Lp>* __tmp = __r._M_pi;
if (__tmp != nullptr)
 __tmp->_M_weak_add_ref();
if (_M_pi != nullptr)
 _M_pi->_M_weak_release();
_M_pi = __tmp;
return *this;
    }

    __weak_count&
    operator=(const __weak_count& __r) noexcept
    {
_Sp_counted_base<_Lp>* __tmp = __r._M_pi;
if (__tmp != nullptr)
 __tmp->_M_weak_add_ref();
if (_M_pi != nullptr)
 _M_pi->_M_weak_release();
_M_pi = __tmp;
return *this;
    }

    __weak_count&
    operator=(__weak_count&& __r) noexcept
    {
if (_M_pi != nullptr)
 _M_pi->_M_weak_release();
_M_pi = __r._M_pi;
      __r._M_pi = nullptr;
return *this;
    }

    void
    _M_swap(__weak_count& __r) noexcept
    {
_Sp_counted_base<_Lp>* __tmp = __r._M_pi;
__r._M_pi = _M_pi;
_M_pi = __tmp;
    }

    long
    _M_get_use_count() const noexcept
    { return _M_pi != nullptr ? _M_pi->_M_get_use_count() : 0; }

    bool
    _M_less(const __weak_count& __rhs) const noexcept
    { return std::less<_Sp_counted_base<_Lp>*>()(this->_M_pi, __rhs._M_pi); }

    bool
    _M_less(const __shared_count<_Lp>& __rhs) const noexcept
    { return std::less<_Sp_counted_base<_Lp>*>()(this->_M_pi, __rhs._M_pi); }

    // Friend function injected into enclosing namespace and found by ADL
    friend inline bool
    operator==(const __weak_count& __a, const __weak_count& __b) noexcept
    { return __a._M_pi == __b._M_pi; }

  private:
    friend class __shared_count<_Lp>;

    _Sp_counted_base<_Lp>*  _M_pi;
  };

// Now that __weak_count is defined we can define this constructor:
template<_Lock_policy _Lp>
  inline
  __shared_count<_Lp>::__shared_count(const __weak_count<_Lp>& __r)
  : _M_pi(__r._M_pi)
  {
    if (_M_pi != nullptr)
_M_pi->_M_add_ref_lock();
    else
__throw_bad_weak_ptr();
  }

// Now that __weak_count is defined we can define this constructor:
template<_Lock_policy _Lp>
  inline
  __shared_count<_Lp>::
  __shared_count(const __weak_count<_Lp>& __r, std::nothrow_t)
  : _M_pi(__r._M_pi)
  {
    if (_M_pi != nullptr)
if (!_M_pi->_M_add_ref_lock_nothrow())
 _M_pi = nullptr;
  }

// Support for enable_shared_from_this.

// Friend of __enable_shared_from_this.
template<_Lock_policy _Lp, typename _Tp1, typename _Tp2>
  void
  __enable_shared_from_this_helper(const __shared_count<_Lp>&,
		     const __enable_shared_from_this<_Tp1,
		     _Lp>*, const _Tp2*) noexcept;

// Friend of enable_shared_from_this.
template<typename _Tp1, typename _Tp2>
  void
  __enable_shared_from_this_helper(const __shared_count<>&,
		     const enable_shared_from_this<_Tp1>*,
		     const _Tp2*) noexcept;

template<_Lock_policy _Lp>
  inline void
  __enable_shared_from_this_helper(const __shared_count<_Lp>&, ...) noexcept
  { }


template<typename _Tp, _Lock_policy _Lp>
  class __shared_ptr
  {
    template<typename _Ptr>
using _Convertible
 = typename enable_if<is_convertible<_Ptr, _Tp*>::value>::type;

  public:
    typedef _Tp   element_type;

    constexpr __shared_ptr() noexcept
    : _M_ptr(0), _M_refcount()
    { }

    template<typename _Tp1>
explicit __shared_ptr(_Tp1* __p)
      : _M_ptr(__p), _M_refcount(__p)
{
 __glibcxx_function_requires(_ConvertibleConcept<_Tp1*, _Tp*>)
 static_assert( !is_void<_Tp1>::value, "incomplete type" );
 static_assert( sizeof(_Tp1) > 0, "incomplete type" );
 __enable_shared_from_this_helper(_M_refcount, __p, __p);
}

    template<typename _Tp1, typename _Deleter>
__shared_ptr(_Tp1* __p, _Deleter __d)
: _M_ptr(__p), _M_refcount(__p, __d)
{
 __glibcxx_function_requires(_ConvertibleConcept<_Tp1*, _Tp*>)
 // TODO requires _Deleter CopyConstructible and __d(__p) well-formed
 __enable_shared_from_this_helper(_M_refcount, __p, __p);
}

    template<typename _Tp1, typename _Deleter, typename _Alloc>
__shared_ptr(_Tp1* __p, _Deleter __d, _Alloc __a)
: _M_ptr(__p), _M_refcount(__p, __d, std::move(__a))
{
 __glibcxx_function_requires(_ConvertibleConcept<_Tp1*, _Tp*>)
 // TODO requires _Deleter CopyConstructible and __d(__p) well-formed
 __enable_shared_from_this_helper(_M_refcount, __p, __p);
}

    template<typename _Deleter>
__shared_ptr(nullptr_t __p, _Deleter __d)
: _M_ptr(0), _M_refcount(__p, __d)
{ }

    template<typename _Deleter, typename _Alloc>
      __shared_ptr(nullptr_t __p, _Deleter __d, _Alloc __a)
: _M_ptr(0), _M_refcount(__p, __d, std::move(__a))
{ }

    template<typename _Tp1>
__shared_ptr(const __shared_ptr<_Tp1, _Lp>& __r, _Tp* __p) noexcept
: _M_ptr(__p), _M_refcount(__r._M_refcount) // never throws
{ }

    __shared_ptr(const __shared_ptr&) noexcept = default;
    __shared_ptr& operator=(const __shared_ptr&) noexcept = default;
    ~__shared_ptr() = default;

    template<typename _Tp1, typename = _Convertible<_Tp1*>>
__shared_ptr(const __shared_ptr<_Tp1, _Lp>& __r) noexcept
: _M_ptr(__r._M_ptr), _M_refcount(__r._M_refcount)
{ }

    __shared_ptr(__shared_ptr&& __r) noexcept
    : _M_ptr(__r._M_ptr), _M_refcount()
    {
_M_refcount._M_swap(__r._M_refcount);
__r._M_ptr = 0;
    }

    template<typename _Tp1, typename = _Convertible<_Tp1*>>
__shared_ptr(__shared_ptr<_Tp1, _Lp>&& __r) noexcept
: _M_ptr(__r._M_ptr), _M_refcount()
{
 _M_refcount._M_swap(__r._M_refcount);
 __r._M_ptr = 0;
}

    template<typename _Tp1>
explicit __shared_ptr(const __weak_ptr<_Tp1, _Lp>& __r)
: _M_refcount(__r._M_refcount) // may throw
{
 __glibcxx_function_requires(_ConvertibleConcept<_Tp1*, _Tp*>)

 // It is now safe to copy __r._M_ptr, as
 // _M_refcount(__r._M_refcount) did not throw.
 _M_ptr = __r._M_ptr;
}

    // If an exception is thrown this constructor has no effect.
    template<typename _Tp1, typename _Del, typename
      = _Convertible<typename unique_ptr<_Tp1, _Del>::pointer>>
__shared_ptr(std::unique_ptr<_Tp1, _Del>&& __r)
: _M_ptr(__r.get()), _M_refcount()
{
 __glibcxx_function_requires(_ConvertibleConcept<_Tp1*, _Tp*>)
 auto __raw = _S_raw_ptr(__r.get());
 _M_refcount = __shared_count<_Lp>(std::move(__r));
 __enable_shared_from_this_helper(_M_refcount, __raw, __raw);
}

973#if _GLIBCXX_USE_DEPRECATED1
    // Postcondition: use_count() == 1 and __r.get() == 0
    template<typename _Tp1>
__shared_ptr(std::auto_ptr<_Tp1>&& __r);
977#endif

    constexpr __shared_ptr(nullptr_t) noexcept : __shared_ptr() { }

    template<typename _Tp1>
__shared_ptr&
operator=(const __shared_ptr<_Tp1, _Lp>& __r) noexcept
{
 _M_ptr = __r._M_ptr;
 _M_refcount = __r._M_refcount; // __shared_count::op= doesn't throw
 return *this;
}

990#if _GLIBCXX_USE_DEPRECATED1
    template<typename _Tp1>
__shared_ptr&
operator=(std::auto_ptr<_Tp1>&& __r)
{
 __shared_ptr(std::move(__r)).swap(*this);
 return *this;
}
998#endif

    __shared_ptr&
    operator=(__shared_ptr&& __r) noexcept
    {
__shared_ptr(std::move(__r)).swap(*this);
return *this;
    }

    template<class _Tp1>
__shared_ptr&
operator=(__shared_ptr<_Tp1, _Lp>&& __r) noexcept
{
 __shared_ptr(std::move(__r)).swap(*this);
 return *this;
}

    template<typename _Tp1, typename _Del>
__shared_ptr&
operator=(std::unique_ptr<_Tp1, _Del>&& __r)
{
 __shared_ptr(std::move(__r)).swap(*this);
 return *this;
}

    void
    reset() noexcept
    { __shared_ptr().swap(*this); }

    template<typename _Tp1>
void
reset(_Tp1* __p) // _Tp1 must be complete.
{
 // Catch self-reset errors.
 __glibcxx_assert(__p == 0 || __p != _M_ptr);
 __shared_ptr(__p).swap(*this);
}

    template<typename _Tp1, typename _Deleter>
void
reset(_Tp1* __p, _Deleter __d)
{ __shared_ptr(__p, __d).swap(*this); }

    template<typename _Tp1, typename _Deleter, typename _Alloc>
void
      reset(_Tp1* __p, _Deleter __d, _Alloc __a)
      { __shared_ptr(__p, __d, std::move(__a)).swap(*this); }

    // Allow class instantiation when _Tp is [cv-qual] void.
    typename std::add_lvalue_reference<_Tp>::type
    operator*() const noexcept
    {
__glibcxx_assert(_M_ptr != 0);
return *_M_ptr;
    }

    _Tp*
    operator->() const noexcept
    {
_GLIBCXX_DEBUG_PEDASSERT(_M_ptr != 0);
return _M_ptr;
    }

    _Tp*
    get() const noexcept
    { return _M_ptr; }

    explicit operator bool() const // never throws
    { return _M_ptr == 0 ? false : true; }

    bool
    unique() const noexcept
    { return _M_refcount._M_unique(); }

    long
    use_count() const noexcept
    { return _M_refcount._M_get_use_count(); }

    void
    swap(__shared_ptr<_Tp, _Lp>& __other) noexcept
    {
std::swap(_M_ptr, __other._M_ptr);
_M_refcount._M_swap(__other._M_refcount);
    }

    template<typename _Tp1>
bool
owner_before(__shared_ptr<_Tp1, _Lp> const& __rhs) const
{ return _M_refcount._M_less(__rhs._M_refcount); }

    template<typename _Tp1>
bool
owner_before(__weak_ptr<_Tp1, _Lp> const& __rhs) const
{ return _M_refcount._M_less(__rhs._M_refcount); }

1093#if __cpp_rtti199711L
  protected:
    // This constructor is non-standard, it is used by allocate_shared.
    template<typename _Alloc, typename... _Args>
__shared_ptr(_Sp_make_shared_tag __tag, const _Alloc& __a,
     _Args&&... __args)
: _M_ptr(), _M_refcount(__tag, (_Tp*)0, __a,
17
←
Calling constructor for '__shared_count<__gnu_cxx::_S_atomic>'→
		std::forward<_Args>(__args)...)
{
 // _M_ptr needs to point to the newly constructed object.
 // This relies on _Sp_counted_ptr_inplace::_M_get_deleter.
 void* __p = _M_refcount._M_get_deleter(typeid(__tag));
 _M_ptr = static_cast<_Tp*>(__p);
 __enable_shared_from_this_helper(_M_refcount, _M_ptr, _M_ptr);
}
1108#else
    template<typename _Alloc>
      struct _Deleter
      {
        void operator()(typename _Alloc::value_type* __ptr)
        {
   __allocated_ptr<_Alloc> __guard{ _M_alloc, __ptr };
   allocator_traits<_Alloc>::destroy(_M_alloc, __guard.get());
        }
        _Alloc _M_alloc;
      };

    template<typename _Alloc, typename... _Args>
__shared_ptr(_Sp_make_shared_tag __tag, const _Alloc& __a,
     _Args&&... __args)
: _M_ptr(), _M_refcount()
{
 typedef typename allocator_traits<_Alloc>::template
   rebind_traits<typename std::remove_cv<_Tp>::type> __traits;
 _Deleter<typename __traits::allocator_type> __del = { __a };
 auto __guard = std::__allocate_guarded(__del._M_alloc);
 auto __ptr = __guard.get();
 // _GLIBCXX_RESOLVE_LIB_DEFECTS
 // 2070. allocate_shared should use allocator_traits<A>::construct
 __traits::construct(__del._M_alloc, __ptr,
	      std::forward<_Args>(__args)...);
 __guard = nullptr;
 __shared_count<_Lp> __count(__ptr, __del, __del._M_alloc);
 _M_refcount._M_swap(__count);
 _M_ptr = __ptr;
 __enable_shared_from_this_helper(_M_refcount, _M_ptr, _M_ptr);
}
1140#endif

    template<typename _Tp1, _Lock_policy _Lp1, typename _Alloc,
      typename... _Args>
friend __shared_ptr<_Tp1, _Lp1>
__allocate_shared(const _Alloc& __a, _Args&&... __args);

    // This constructor is used by __weak_ptr::lock() and
    // shared_ptr::shared_ptr(const weak_ptr&, std::nothrow_t).
    __shared_ptr(const __weak_ptr<_Tp, _Lp>& __r, std::nothrow_t)
    : _M_refcount(__r._M_refcount, std::nothrow)
    {
_M_ptr = _M_refcount._M_get_use_count() ? __r._M_ptr : nullptr;
    }

    friend class __weak_ptr<_Tp, _Lp>;

  private:
    void*
    _M_get_deleter(const std::type_info& __ti) const noexcept
    { return _M_refcount._M_get_deleter(__ti); }

    template<typename _Tp1>
static _Tp1*
_S_raw_ptr(_Tp1* __ptr)
{ return __ptr; }

    template<typename _Tp1>
static auto
_S_raw_ptr(_Tp1 __ptr) -> decltype(std::__addressof(*__ptr))
{ return std::__addressof(*__ptr); }

    template<typename _Tp1, _Lock_policy _Lp1> friend class __shared_ptr;
    template<typename _Tp1, _Lock_policy _Lp1> friend class __weak_ptr;

    template<typename _Del, typename _Tp1, _Lock_policy _Lp1>
friend _Del* get_deleter(const __shared_ptr<_Tp1, _Lp1>&) noexcept;

    _Tp*	   	   _M_ptr;         // Contained pointer.
    __shared_count<_Lp>  _M_refcount;    // Reference counter.
  };


// 20.7.2.2.7 shared_ptr comparisons
template<typename _Tp1, typename _Tp2, _Lock_policy _Lp>
  inline bool
  operator==(const __shared_ptr<_Tp1, _Lp>& __a,
      const __shared_ptr<_Tp2, _Lp>& __b) noexcept
  { return __a.get() == __b.get(); }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator==(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
  { return !__a; }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator==(nullptr_t, const __shared_ptr<_Tp, _Lp>& __a) noexcept
  { return !__a; }

template<typename _Tp1, typename _Tp2, _Lock_policy _Lp>
  inline bool
  operator!=(const __shared_ptr<_Tp1, _Lp>& __a,
      const __shared_ptr<_Tp2, _Lp>& __b) noexcept
  { return __a.get() != __b.get(); }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator!=(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
  { return (bool)__a; }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator!=(nullptr_t, const __shared_ptr<_Tp, _Lp>& __a) noexcept
  { return (bool)__a; }

template<typename _Tp1, typename _Tp2, _Lock_policy _Lp>
  inline bool
  operator<(const __shared_ptr<_Tp1, _Lp>& __a,
     const __shared_ptr<_Tp2, _Lp>& __b) noexcept
  {
    typedef typename std::common_type<_Tp1*, _Tp2*>::type _CT;
    return std::less<_CT>()(__a.get(), __b.get());
  }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator<(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
  { return std::less<_Tp*>()(__a.get(), nullptr); }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator<(nullptr_t, const __shared_ptr<_Tp, _Lp>& __a) noexcept
  { return std::less<_Tp*>()(nullptr, __a.get()); }

template<typename _Tp1, typename _Tp2, _Lock_policy _Lp>
  inline bool
  operator<=(const __shared_ptr<_Tp1, _Lp>& __a,
      const __shared_ptr<_Tp2, _Lp>& __b) noexcept
  { return !(__b < __a); }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator<=(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
  { return !(nullptr < __a); }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator<=(nullptr_t, const __shared_ptr<_Tp, _Lp>& __a) noexcept
  { return !(__a < nullptr); }

template<typename _Tp1, typename _Tp2, _Lock_policy _Lp>
  inline bool
  operator>(const __shared_ptr<_Tp1, _Lp>& __a,
     const __shared_ptr<_Tp2, _Lp>& __b) noexcept
  { return (__b < __a); }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator>(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
  { return std::less<_Tp*>()(nullptr, __a.get()); }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator>(nullptr_t, const __shared_ptr<_Tp, _Lp>& __a) noexcept
  { return std::less<_Tp*>()(__a.get(), nullptr); }

template<typename _Tp1, typename _Tp2, _Lock_policy _Lp>
  inline bool
  operator>=(const __shared_ptr<_Tp1, _Lp>& __a,
      const __shared_ptr<_Tp2, _Lp>& __b) noexcept
  { return !(__a < __b); }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator>=(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
  { return !(__a < nullptr); }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator>=(nullptr_t, const __shared_ptr<_Tp, _Lp>& __a) noexcept
  { return !(nullptr < __a); }

template<typename _Sp>
  struct _Sp_less : public binary_function<_Sp, _Sp, bool>
  {
    bool
    operator()(const _Sp& __lhs, const _Sp& __rhs) const noexcept
    {
typedef typename _Sp::element_type element_type;
return std::less<element_type*>()(__lhs.get(), __rhs.get());
    }
  };

template<typename _Tp, _Lock_policy _Lp>
  struct less<__shared_ptr<_Tp, _Lp>>
  : public _Sp_less<__shared_ptr<_Tp, _Lp>>
  { };

// 20.7.2.2.8 shared_ptr specialized algorithms.
template<typename _Tp, _Lock_policy _Lp>
  inline void
  swap(__shared_ptr<_Tp, _Lp>& __a, __shared_ptr<_Tp, _Lp>& __b) noexcept
  { __a.swap(__b); }

// 20.7.2.2.9 shared_ptr casts

// The seemingly equivalent code:
// shared_ptr<_Tp, _Lp>(static_cast<_Tp*>(__r.get()))
// will eventually result in undefined behaviour, attempting to
// delete the same object twice.
/// static_pointer_cast
template<typename _Tp, typename _Tp1, _Lock_policy _Lp>
  inline __shared_ptr<_Tp, _Lp>
  static_pointer_cast(const __shared_ptr<_Tp1, _Lp>& __r) noexcept
  { return __shared_ptr<_Tp, _Lp>(__r, static_cast<_Tp*>(__r.get())); }

// The seemingly equivalent code:
// shared_ptr<_Tp, _Lp>(const_cast<_Tp*>(__r.get()))
// will eventually result in undefined behaviour, attempting to
// delete the same object twice.
/// const_pointer_cast
template<typename _Tp, typename _Tp1, _Lock_policy _Lp>
  inline __shared_ptr<_Tp, _Lp>
  const_pointer_cast(const __shared_ptr<_Tp1, _Lp>& __r) noexcept
  { return __shared_ptr<_Tp, _Lp>(__r, const_cast<_Tp*>(__r.get())); }

// The seemingly equivalent code:
// shared_ptr<_Tp, _Lp>(dynamic_cast<_Tp*>(__r.get()))
// will eventually result in undefined behaviour, attempting to
// delete the same object twice.
/// dynamic_pointer_cast
template<typename _Tp, typename _Tp1, _Lock_policy _Lp>
  inline __shared_ptr<_Tp, _Lp>
  dynamic_pointer_cast(const __shared_ptr<_Tp1, _Lp>& __r) noexcept
  {
    if (_Tp* __p = dynamic_cast<_Tp*>(__r.get()))
return __shared_ptr<_Tp, _Lp>(__r, __p);
    return __shared_ptr<_Tp, _Lp>();
  }


template<typename _Tp, _Lock_policy _Lp>
  class __weak_ptr
  {
    template<typename _Ptr>
using _Convertible
 = typename enable_if<is_convertible<_Ptr, _Tp*>::value>::type;

  public:
    typedef _Tp element_type;

    constexpr __weak_ptr() noexcept
    : _M_ptr(nullptr), _M_refcount()
    { }

    __weak_ptr(const __weak_ptr&) noexcept = default;

    ~__weak_ptr() = default;

    // The "obvious" converting constructor implementation:
    //
    //  template<typename _Tp1>
    //    __weak_ptr(const __weak_ptr<_Tp1, _Lp>& __r)
    //    : _M_ptr(__r._M_ptr), _M_refcount(__r._M_refcount) // never throws
    //    { }
    //
    // has a serious problem.
    //
    //  __r._M_ptr may already have been invalidated. The _M_ptr(__r._M_ptr)
    //  conversion may require access to *__r._M_ptr (virtual inheritance).
    //
    // It is not possible to avoid spurious access violations since
    // in multithreaded programs __r._M_ptr may be invalidated at any point.
    template<typename _Tp1, typename = _Convertible<_Tp1*>>
__weak_ptr(const __weak_ptr<_Tp1, _Lp>& __r) noexcept
: _M_refcount(__r._M_refcount)
      { _M_ptr = __r.lock().get(); }

    template<typename _Tp1, typename = _Convertible<_Tp1*>>
__weak_ptr(const __shared_ptr<_Tp1, _Lp>& __r) noexcept
: _M_ptr(__r._M_ptr), _M_refcount(__r._M_refcount)
{ }

    __weak_ptr(__weak_ptr&& __r) noexcept
    : _M_ptr(__r._M_ptr), _M_refcount(std::move(__r._M_refcount))
    { __r._M_ptr = nullptr; }

    template<typename _Tp1, typename = _Convertible<_Tp1*>>
__weak_ptr(__weak_ptr<_Tp1, _Lp>&& __r) noexcept
: _M_ptr(__r.lock().get()), _M_refcount(std::move(__r._M_refcount))
      { __r._M_ptr = nullptr; }

    __weak_ptr&
    operator=(const __weak_ptr& __r) noexcept = default;

    template<typename _Tp1>
__weak_ptr&
operator=(const __weak_ptr<_Tp1, _Lp>& __r) noexcept
{
 _M_ptr = __r.lock().get();
 _M_refcount = __r._M_refcount;
 return *this;
}

    template<typename _Tp1>
__weak_ptr&
operator=(const __shared_ptr<_Tp1, _Lp>& __r) noexcept
{
 _M_ptr = __r._M_ptr;
 _M_refcount = __r._M_refcount;
 return *this;
}

    __weak_ptr&
    operator=(__weak_ptr&& __r) noexcept
    {
_M_ptr = __r._M_ptr;
_M_refcount = std::move(__r._M_refcount);
__r._M_ptr = nullptr;
return *this;
    }

    template<typename _Tp1>
__weak_ptr&
operator=(__weak_ptr<_Tp1, _Lp>&& __r) noexcept
{
 _M_ptr = __r.lock().get();
 _M_refcount = std::move(__r._M_refcount);
 __r._M_ptr = nullptr;
 return *this;
}

    __shared_ptr<_Tp, _Lp>
    lock() const noexcept
    { return __shared_ptr<element_type, _Lp>(*this, std::nothrow); }

    long
    use_count() const noexcept
    { return _M_refcount._M_get_use_count(); }

    bool
    expired() const noexcept
    { return _M_refcount._M_get_use_count() == 0; }

    template<typename _Tp1>
bool
owner_before(const __shared_ptr<_Tp1, _Lp>& __rhs) const
{ return _M_refcount._M_less(__rhs._M_refcount); }

    template<typename _Tp1>
bool
owner_before(const __weak_ptr<_Tp1, _Lp>& __rhs) const
{ return _M_refcount._M_less(__rhs._M_refcount); }

    void
    reset() noexcept
    { __weak_ptr().swap(*this); }

    void
    swap(__weak_ptr& __s) noexcept
    {
std::swap(_M_ptr, __s._M_ptr);
_M_refcount._M_swap(__s._M_refcount);
    }

  private:
    // Used by __enable_shared_from_this.
    void
    _M_assign(_Tp* __ptr, const __shared_count<_Lp>& __refcount) noexcept
    {
if (use_count() == 0)
 {
   _M_ptr = __ptr;
   _M_refcount = __refcount;
 }
    }

    template<typename _Tp1, _Lock_policy _Lp1> friend class __shared_ptr;
    template<typename _Tp1, _Lock_policy _Lp1> friend class __weak_ptr;
    friend class __enable_shared_from_this<_Tp, _Lp>;
    friend class enable_shared_from_this<_Tp>;

    _Tp*	 	 _M_ptr;         // Contained pointer.
    __weak_count<_Lp>  _M_refcount;    // Reference counter.
  };

// 20.7.2.3.6 weak_ptr specialized algorithms.
template<typename _Tp, _Lock_policy _Lp>
  inline void
  swap(__weak_ptr<_Tp, _Lp>& __a, __weak_ptr<_Tp, _Lp>& __b) noexcept
  { __a.swap(__b); }

template<typename _Tp, typename _Tp1>
  struct _Sp_owner_less : public binary_function<_Tp, _Tp, bool>
  {
    bool
    operator()(const _Tp& __lhs, const _Tp& __rhs) const
    { return __lhs.owner_before(__rhs); }

    bool
    operator()(const _Tp& __lhs, const _Tp1& __rhs) const
    { return __lhs.owner_before(__rhs); }

    bool
    operator()(const _Tp1& __lhs, const _Tp& __rhs) const
    { return __lhs.owner_before(__rhs); }
  };

template<typename _Tp, _Lock_policy _Lp>
  struct owner_less<__shared_ptr<_Tp, _Lp>>
  : public _Sp_owner_less<__shared_ptr<_Tp, _Lp>, __weak_ptr<_Tp, _Lp>>
  { };

template<typename _Tp, _Lock_policy _Lp>
  struct owner_less<__weak_ptr<_Tp, _Lp>>
  : public _Sp_owner_less<__weak_ptr<_Tp, _Lp>, __shared_ptr<_Tp, _Lp>>
  { };


template<typename _Tp, _Lock_policy _Lp>
  class __enable_shared_from_this
  {
  protected:
    constexpr __enable_shared_from_this() noexcept { }

    __enable_shared_from_this(const __enable_shared_from_this&) noexcept { }

    __enable_shared_from_this&
    operator=(const __enable_shared_from_this&) noexcept
    { return *this; }

    ~__enable_shared_from_this() { }

  public:
    __shared_ptr<_Tp, _Lp>
    shared_from_this()
    { return __shared_ptr<_Tp, _Lp>(this->_M_weak_this); }

    __shared_ptr<const _Tp, _Lp>
    shared_from_this() const
    { return __shared_ptr<const _Tp, _Lp>(this->_M_weak_this); }

  private:
    template<typename _Tp1>
void
_M_weak_assign(_Tp1* __p, const __shared_count<_Lp>& __n) const noexcept
{ _M_weak_this._M_assign(__p, __n); }

    template<_Lock_policy _Lp1, typename _Tp1, typename _Tp2>
friend void
__enable_shared_from_this_helper(const __shared_count<_Lp1>&,
			 const __enable_shared_from_this<_Tp1,
			 _Lp1>*, const _Tp2*) noexcept;

    mutable __weak_ptr<_Tp, _Lp>  _M_weak_this;
  };

template<_Lock_policy _Lp1, typename _Tp1, typename _Tp2>
  inline void
  __enable_shared_from_this_helper(const __shared_count<_Lp1>& __pn,
		     const __enable_shared_from_this<_Tp1,
		     _Lp1>* __pe,
		     const _Tp2* __px) noexcept
  {
    if (__pe != nullptr)
__pe->_M_weak_assign(const_cast<_Tp2*>(__px), __pn);
  }

template<typename _Tp, _Lock_policy _Lp, typename _Alloc, typename... _Args>
  inline __shared_ptr<_Tp, _Lp>
  __allocate_shared(const _Alloc& __a, _Args&&... __args)
  {
    return __shared_ptr<_Tp, _Lp>(_Sp_make_shared_tag(), __a,
		    std::forward<_Args>(__args)...);
  }

template<typename _Tp, _Lock_policy _Lp, typename... _Args>
  inline __shared_ptr<_Tp, _Lp>
  __make_shared(_Args&&... __args)
  {
    typedef typename std::remove_const<_Tp>::type _Tp_nc;
    return std::__allocate_shared<_Tp, _Lp>(std::allocator<_Tp_nc>(),
			      std::forward<_Args>(__args)...);
  }

/// std::hash specialization for __shared_ptr.
template<typename _Tp, _Lock_policy _Lp>
  struct hash<__shared_ptr<_Tp, _Lp>>
  : public __hash_base<size_t, __shared_ptr<_Tp, _Lp>>
  {
    size_t
    operator()(const __shared_ptr<_Tp, _Lp>& __s) const noexcept
    { return std::hash<_Tp*>()(__s.get()); }
  };

1596_GLIBCXX_END_NAMESPACE_VERSION
1597} // namespace

1599#endif // _SHARED_PTR_BASE_H

←

/usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/bits/alloc_traits.h

→

1// Allocator traits -*- C++ -*-

3// Copyright (C) 2011-2016 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.

11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.

16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.

20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.

25/** @file bits/alloc_traits.h
*  This is an internal header file, included by other library headers.
*  Do not attempt to use it directly. @headername{memory}
*/

30#ifndef _ALLOC_TRAITS_H1
31#define _ALLOC_TRAITS_H1 1

33#if __cplusplus201402L >= 201103L

35#include <bits/memoryfwd.h>
36#include <bits/ptr_traits.h>
37#include <ext/numeric_traits.h>

39#define __cpp_lib_allocator_traits_is_always_equal201411 201411

41namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
42{
43_GLIBCXX_BEGIN_NAMESPACE_VERSION

struct __allocator_traits_base
{
  template<typename _Tp, typename _Up, typename = void>
    struct __rebind : __replace_first_arg<_Tp, _Up> { };

  template<typename _Tp, typename _Up>
    struct __rebind<_Tp, _Up,
      __void_t<typename _Tp::template rebind<_Up>::other>>
    { using type = typename _Tp::template rebind<_Up>::other; };

protected:
  template<typename _Tp>
    using __pointer = typename _Tp::pointer;
  template<typename _Tp>
    using __c_pointer = typename _Tp::const_pointer;
  template<typename _Tp>
    using __v_pointer = typename _Tp::void_pointer;
  template<typename _Tp>
    using __cv_pointer = typename _Tp::const_void_pointer;
  template<typename _Tp>
    using __pocca = typename _Tp::propagate_on_container_copy_assignment;
  template<typename _Tp>
    using __pocma = typename _Tp::propagate_on_container_move_assignment;
  template<typename _Tp>
    using __pocs = typename _Tp::propagate_on_container_swap;
  template<typename _Tp>
    using __equal = typename _Tp::is_always_equal;
};

template<typename _Alloc, typename _Up>
  using __alloc_rebind
    = typename __allocator_traits_base::template __rebind<_Alloc, _Up>::type;

/**
 * @brief  Uniform interface to all allocator types.
 * @ingroup allocators
*/
template<typename _Alloc>
  struct allocator_traits : __allocator_traits_base
  {
    /// The allocator type
    typedef _Alloc allocator_type;
    /// The allocated type
    typedef typename _Alloc::value_type value_type;

    /**
     * @brief   The allocator's pointer type.
     *
     * @c Alloc::pointer if that type exists, otherwise @c value_type*
    */
    using pointer = __detected_or_t<value_type*, __pointer, _Alloc>;

  private:
    // Select _Func<_Alloc> or pointer_traits<pointer>::rebind<_Tp>
    template<template<typename> class _Func, typename _Tp, typename = void>
struct _Ptr
{
 using type = typename pointer_traits<pointer>::template rebind<_Tp>;
};

    template<template<typename> class _Func, typename _Tp>
struct _Ptr<_Func, _Tp, __void_t<_Func<_Alloc>>>
{
 using type = _Func<_Alloc>;
};

    // Select _A2::difference_type or pointer_traits<_Ptr>::difference_type
    template<typename _A2, typename _PtrT, typename = void>
struct _Diff
{ using type = typename pointer_traits<_PtrT>::difference_type; };

    template<typename _A2, typename _PtrT>
struct _Diff<_A2, _PtrT, __void_t<typename _A2::difference_type>>
{ using type = typename _A2::difference_type; };

    // Select _A2::size_type or make_unsigned<_DiffT>::type
    template<typename _A2, typename _DiffT, typename = void>
struct _Size : make_unsigned<_DiffT> { };

    template<typename _A2, typename _DiffT>
struct _Size<_A2, _DiffT, __void_t<typename _A2::size_type>>
{ using type = typename _A2::size_type; };

  public:
    /**
     * @brief   The allocator's const pointer type.
     *
     * @c Alloc::const_pointer if that type exists, otherwise
     * <tt> pointer_traits<pointer>::rebind<const value_type> </tt>
    */
    using const_pointer = typename _Ptr<__c_pointer, const value_type>::type;

    /**
     * @brief   The allocator's void pointer type.
     *
     * @c Alloc::void_pointer if that type exists, otherwise
     * <tt> pointer_traits<pointer>::rebind<void> </tt>
    */
    using void_pointer = typename _Ptr<__v_pointer, void>::type;

    /**
     * @brief   The allocator's const void pointer type.
     *
     * @c Alloc::const_void_pointer if that type exists, otherwise
     * <tt> pointer_traits<pointer>::rebind<const void> </tt>
    */
    using const_void_pointer = typename _Ptr<__cv_pointer, const void>::type;

    /**
     * @brief   The allocator's difference type
     *
     * @c Alloc::difference_type if that type exists, otherwise
     * <tt> pointer_traits<pointer>::difference_type </tt>
    */
    using difference_type = typename _Diff<_Alloc, pointer>::type;

    /**
     * @brief   The allocator's size type
     *
     * @c Alloc::size_type if that type exists, otherwise
     * <tt> make_unsigned<difference_type>::type </tt>
    */
    using size_type = typename _Size<_Alloc, difference_type>::type;

    /**
     * @brief   How the allocator is propagated on copy assignment
     *
     * @c Alloc::propagate_on_container_copy_assignment if that type exists,
     * otherwise @c false_type
    */
    using propagate_on_container_copy_assignment
= __detected_or_t<false_type, __pocca, _Alloc>;

    /**
     * @brief   How the allocator is propagated on move assignment
     *
     * @c Alloc::propagate_on_container_move_assignment if that type exists,
     * otherwise @c false_type
    */
    using propagate_on_container_move_assignment
= __detected_or_t<false_type, __pocma, _Alloc>;

    /**
     * @brief   How the allocator is propagated on swap
     *
     * @c Alloc::propagate_on_container_swap if that type exists,
     * otherwise @c false_type
    */
    using propagate_on_container_swap
= __detected_or_t<false_type, __pocs, _Alloc>;

    /**
     * @brief   Whether all instances of the allocator type compare equal.
     *
     * @c Alloc::is_always_equal if that type exists,
     * otherwise @c is_empty<Alloc>::type
    */
    using is_always_equal
= __detected_or_t<typename is_empty<_Alloc>::type, __equal, _Alloc>;

    template<typename _Tp>
using rebind_alloc = __alloc_rebind<_Alloc, _Tp>;
    template<typename _Tp>
using rebind_traits = allocator_traits<rebind_alloc<_Tp>>;

  private:
    template<typename _Alloc2>
static auto
_S_allocate(_Alloc2& __a, size_type __n, const_void_pointer __hint, int)
-> decltype(__a.allocate(__n, __hint))
{ return __a.allocate(__n, __hint); }

    template<typename _Alloc2>
static pointer
_S_allocate(_Alloc2& __a, size_type __n, const_void_pointer, ...)
{ return __a.allocate(__n); }

    template<typename _Tp, typename... _Args>
struct __construct_helper
{
 template<typename _Alloc2,
   typename = decltype(std::declval<_Alloc2*>()->construct(
  std::declval<_Tp*>(), std::declval<_Args>()...))>
   static true_type __test(int);

 template<typename>
   static false_type __test(...);

 using type = decltype(__test<_Alloc>(0));
};

    template<typename _Tp, typename... _Args>
using __has_construct
 = typename __construct_helper<_Tp, _Args...>::type;

    template<typename _Tp, typename... _Args>
static _Require<__has_construct<_Tp, _Args...>>
_S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
{ __a.construct(__p, std::forward<_Args>(__args)...); }

    template<typename _Tp, typename... _Args>
static
_Require<__and_<__not_<__has_construct<_Tp, _Args...>>,
	       is_constructible<_Tp, _Args...>>>
_S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
{ ::new((void*)__p) _Tp(std::forward<_Args>(__args)...); }

    template<typename _Alloc2, typename _Tp>
static auto
_S_destroy(_Alloc2& __a, _Tp* __p, int)
-> decltype(__a.destroy(__p))
{ __a.destroy(__p); }

    template<typename _Alloc2, typename _Tp>
static void
_S_destroy(_Alloc2&, _Tp* __p, ...)
{ __p->~_Tp(); }

    template<typename _Alloc2>
static auto
_S_max_size(_Alloc2& __a, int)
-> decltype(__a.max_size())
{ return __a.max_size(); }

    template<typename _Alloc2>
static size_type
_S_max_size(_Alloc2&, ...)
{
 // _GLIBCXX_RESOLVE_LIB_DEFECTS
 // 2466. allocator_traits::max_size() default behavior is incorrect
 return __gnu_cxx::__numeric_traits<size_type>::__max
   / sizeof(value_type);
}

    template<typename _Alloc2>
static auto
_S_select(_Alloc2& __a, int)
-> decltype(__a.select_on_container_copy_construction())
{ return __a.select_on_container_copy_construction(); }

    template<typename _Alloc2>
static _Alloc2
_S_select(_Alloc2& __a, ...)
{ return __a; }

  public:

    /**
     *  @brief  Allocate memory.
     *  @param  __a  An allocator.
     *  @param  __n  The number of objects to allocate space for.
     *
     *  Calls @c a.allocate(n)
    */
    static pointer
    allocate(_Alloc& __a, size_type __n)
    { return __a.allocate(__n); }

    /**
     *  @brief  Allocate memory.
     *  @param  __a  An allocator.
     *  @param  __n  The number of objects to allocate space for.
     *  @param  __hint Aid to locality.
     *  @return Memory of suitable size and alignment for @a n objects
     *          of type @c value_type
     *
     *  Returns <tt> a.allocate(n, hint) </tt> if that expression is
     *  well-formed, otherwise returns @c a.allocate(n)
    */
    static pointer
    allocate(_Alloc& __a, size_type __n, const_void_pointer __hint)
    { return _S_allocate(__a, __n, __hint, 0); }

    /**
     *  @brief  Deallocate memory.
     *  @param  __a  An allocator.
     *  @param  __p  Pointer to the memory to deallocate.
     *  @param  __n  The number of objects space was allocated for.
     *
     *  Calls <tt> a.deallocate(p, n) </tt>
    */
    static void
    deallocate(_Alloc& __a, pointer __p, size_type __n)
    { __a.deallocate(__p, __n); }

    /**
     *  @brief  Construct an object of type @a _Tp
     *  @param  __a  An allocator.
     *  @param  __p  Pointer to memory of suitable size and alignment for Tp
     *  @param  __args Constructor arguments.
     *
     *  Calls <tt> __a.construct(__p, std::forward<Args>(__args)...) </tt>
     *  if that expression is well-formed, otherwise uses placement-new
     *  to construct an object of type @a _Tp at location @a __p from the
     *  arguments @a __args...
    */
    template<typename _Tp, typename... _Args>
static auto construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
-> decltype(_S_construct(__a, __p, std::forward<_Args>(__args)...))
{ _S_construct(__a, __p, std::forward<_Args>(__args)...); }

    /**
     *  @brief  Destroy an object of type @a _Tp
     *  @param  __a  An allocator.
     *  @param  __p  Pointer to the object to destroy
     *
     *  Calls @c __a.destroy(__p) if that expression is well-formed,
     *  otherwise calls @c __p->~_Tp()
    */
    template<typename _Tp>
static void destroy(_Alloc& __a, _Tp* __p)
{ _S_destroy(__a, __p, 0); }

    /**
     *  @brief  The maximum supported allocation size
     *  @param  __a  An allocator.
     *  @return @c __a.max_size() or @c numeric_limits<size_type>::max()
     *
     *  Returns @c __a.max_size() if that expression is well-formed,
     *  otherwise returns @c numeric_limits<size_type>::max()
    */
    static size_type max_size(const _Alloc& __a) noexcept
    { return _S_max_size(__a, 0); }

    /**
     *  @brief  Obtain an allocator to use when copying a container.
     *  @param  __rhs  An allocator.
     *  @return @c __rhs.select_on_container_copy_construction() or @a __rhs
     *
     *  Returns @c __rhs.select_on_container_copy_construction() if that
     *  expression is well-formed, otherwise returns @a __rhs
    */
    static _Alloc
    select_on_container_copy_construction(const _Alloc& __rhs)
    { return _S_select(__rhs, 0); }
  };

/// Partial specialization for std::allocator.
template<typename _Tp>
  struct allocator_traits<allocator<_Tp>>
  {
    /// The allocator type
    using allocator_type = allocator<_Tp>;
    /// The allocated type
    using value_type = _Tp;

    /// The allocator's pointer type.
    using pointer = _Tp*;

    /// The allocator's const pointer type.
    using const_pointer = const _Tp*;

    /// The allocator's void pointer type.
    using void_pointer = void*;

    /// The allocator's const void pointer type.
    using const_void_pointer = const void*;

    /// The allocator's difference type
    using difference_type = std::ptrdiff_t;

    /// The allocator's size type
    using size_type = std::size_t;

    /// How the allocator is propagated on copy assignment
    using propagate_on_container_copy_assignment = false_type;

    /// How the allocator is propagated on move assignment
    using propagate_on_container_move_assignment = true_type;

    /// How the allocator is propagated on swap
    using propagate_on_container_swap = false_type;

    /// Whether all instances of the allocator type compare equal.
    using is_always_equal = true_type;

    template<typename _Up>
using rebind_alloc = allocator<_Up>;

    template<typename _Up>
using rebind_traits = allocator_traits<allocator<_Up>>;

    /**
     *  @brief  Allocate memory.
     *  @param  __a  An allocator.
     *  @param  __n  The number of objects to allocate space for.
     *
     *  Calls @c a.allocate(n)
    */
    static pointer
    allocate(allocator_type& __a, size_type __n)
    { return __a.allocate(__n); }

    /**
     *  @brief  Allocate memory.
     *  @param  __a  An allocator.
     *  @param  __n  The number of objects to allocate space for.
     *  @param  __hint Aid to locality.
     *  @return Memory of suitable size and alignment for @a n objects
     *          of type @c value_type
     *
     *  Returns <tt> a.allocate(n, hint) </tt>
    */
    static pointer
    allocate(allocator_type& __a, size_type __n, const_void_pointer __hint)
    { return __a.allocate(__n, __hint); }

    /**
     *  @brief  Deallocate memory.
     *  @param  __a  An allocator.
     *  @param  __p  Pointer to the memory to deallocate.
     *  @param  __n  The number of objects space was allocated for.
     *
     *  Calls <tt> a.deallocate(p, n) </tt>
    */
    static void
    deallocate(allocator_type& __a, pointer __p, size_type __n)
    { __a.deallocate(__p, __n); }

    /**
     *  @brief  Construct an object of type @a _Up
     *  @param  __a  An allocator.
     *  @param  __p  Pointer to memory of suitable size and alignment for Tp
     *  @param  __args Constructor arguments.
     *
     *  Calls <tt> __a.construct(__p, std::forward<Args>(__args)...) </tt>
    */
    template<typename _Up, typename... _Args>
static void
construct(allocator_type& __a, _Up* __p, _Args&&... __args)
{ __a.construct(__p, std::forward<_Args>(__args)...); }
20
←
Calling 'new_allocator::construct'→

    /**
     *  @brief  Destroy an object of type @a _Up
     *  @param  __a  An allocator.
     *  @param  __p  Pointer to the object to destroy
     *
     *  Calls @c __a.destroy(__p).
    */
    template<typename _Up>
static void
destroy(allocator_type& __a, _Up* __p)
{ __a.destroy(__p); }

    /**
     *  @brief  The maximum supported allocation size
     *  @param  __a  An allocator.
     *  @return @c __a.max_size()
    */
    static size_type
    max_size(const allocator_type& __a) noexcept
    { return __a.max_size(); }

    /**
     *  @brief  Obtain an allocator to use when copying a container.
     *  @param  __rhs  An allocator.
     *  @return @c __rhs
    */
    static allocator_type
    select_on_container_copy_construction(const allocator_type& __rhs)
    { return __rhs; }
  };


template<typename _Alloc>
  inline void
  __do_alloc_on_copy(_Alloc& __one, const _Alloc& __two, true_type)
  { __one = __two; }

template<typename _Alloc>
  inline void
  __do_alloc_on_copy(_Alloc&, const _Alloc&, false_type)
  { }

template<typename _Alloc>
  inline void __alloc_on_copy(_Alloc& __one, const _Alloc& __two)
  {
    typedef allocator_traits<_Alloc> __traits;
    typedef typename __traits::propagate_on_container_copy_assignment __pocca;
    __do_alloc_on_copy(__one, __two, __pocca());
  }

template<typename _Alloc>
  inline _Alloc __alloc_on_copy(const _Alloc& __a)
  {
    typedef allocator_traits<_Alloc> __traits;
    return __traits::select_on_container_copy_construction(__a);
  }

template<typename _Alloc>
  inline void __do_alloc_on_move(_Alloc& __one, _Alloc& __two, true_type)
  { __one = std::move(__two); }

template<typename _Alloc>
  inline void __do_alloc_on_move(_Alloc&, _Alloc&, false_type)
  { }

template<typename _Alloc>
  inline void __alloc_on_move(_Alloc& __one, _Alloc& __two)
  {
    typedef allocator_traits<_Alloc> __traits;
    typedef typename __traits::propagate_on_container_move_assignment __pocma;
    __do_alloc_on_move(__one, __two, __pocma());
  }

template<typename _Alloc>
  inline void __do_alloc_on_swap(_Alloc& __one, _Alloc& __two, true_type)
  {
    using std::swap;
    swap(__one, __two);
  }

template<typename _Alloc>
  inline void __do_alloc_on_swap(_Alloc&, _Alloc&, false_type)
  { }

template<typename _Alloc>
  inline void __alloc_on_swap(_Alloc& __one, _Alloc& __two)
  {
    typedef allocator_traits<_Alloc> __traits;
    typedef typename __traits::propagate_on_container_swap __pocs;
    __do_alloc_on_swap(__one, __two, __pocs());
  }

template<typename _Alloc>
  class __is_copy_insertable_impl
  {
    typedef allocator_traits<_Alloc> _Traits;

    template<typename _Up, typename
      = decltype(_Traits::construct(std::declval<_Alloc&>(),
			     std::declval<_Up*>(),
			     std::declval<const _Up&>()))>
static true_type
_M_select(int);

    template<typename _Up>
static false_type
_M_select(...);

  public:
    typedef decltype(_M_select<typename _Alloc::value_type>(0)) type;
  };

// true if _Alloc::value_type is CopyInsertable into containers using _Alloc
template<typename _Alloc>
  struct __is_copy_insertable
  : __is_copy_insertable_impl<_Alloc>::type
  { };

// std::allocator<_Tp> just requires CopyConstructible
template<typename _Tp>
  struct __is_copy_insertable<allocator<_Tp>>
  : is_copy_constructible<_Tp>
  { };

601_GLIBCXX_END_NAMESPACE_VERSION
602} // namespace std

604#endif
605#endif

←

/usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/ext/new_allocator.h

→

1// Allocator that wraps operator new -*- C++ -*-

3// Copyright (C) 2001-2016 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.

11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.

16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.

20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.

25/** @file ext/new_allocator.h
*  This file is a GNU extension to the Standard C++ Library.
*/

29#ifndef _NEW_ALLOCATOR_H1
30#define _NEW_ALLOCATOR_H1 1

32#include <bits/c++config.h>
33#include <new>
34#include <bits/functexcept.h>
35#include <bits/move.h>
36#if __cplusplus201402L >= 201103L
37#include <type_traits>
38#endif

40namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
41{
42_GLIBCXX_BEGIN_NAMESPACE_VERSION

using std::size_t;
using std::ptrdiff_t;

/**
 *  @brief  An allocator that uses global new, as per [20.4].
 *  @ingroup allocators
 *
 *  This is precisely the allocator defined in the C++ Standard. 
 *    - all allocation calls operator new
 *    - all deallocation calls operator delete
 *
 *  @tparam  _Tp  Type of allocated object.
 */
template<typename _Tp>
  class new_allocator
  {
  public:
    typedef size_t     size_type;
    typedef ptrdiff_t  difference_type;
    typedef _Tp*       pointer;
    typedef const _Tp* const_pointer;
    typedef _Tp&       reference;
    typedef const _Tp& const_reference;
    typedef _Tp        value_type;

    template<typename _Tp1>
      struct rebind
      { typedef new_allocator<_Tp1> other; };

73#if __cplusplus201402L >= 201103L
    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // 2103. propagate_on_container_move_assignment
    typedef std::true_type propagate_on_container_move_assignment;
77#endif

    new_allocator() _GLIBCXX_USE_NOEXCEPTnoexcept { }

    new_allocator(const new_allocator&) _GLIBCXX_USE_NOEXCEPTnoexcept { }

    template<typename _Tp1>
      new_allocator(const new_allocator<_Tp1>&) _GLIBCXX_USE_NOEXCEPTnoexcept { }

    ~new_allocator() _GLIBCXX_USE_NOEXCEPTnoexcept { }

    pointer
    address(reference __x) const _GLIBCXX_NOEXCEPTnoexcept
    { return std::__addressof(__x); }

    const_pointer
    address(const_reference __x) const _GLIBCXX_NOEXCEPTnoexcept
    { return std::__addressof(__x); }

    // NB: __n is permitted to be 0.  The C++ standard says nothing
    // about what the return value is when __n == 0.
    pointer
    allocate(size_type __n, const void* = 0)
    { 
if (__n > this->max_size())
 std::__throw_bad_alloc();

return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
    }

    // __p is not permitted to be a null pointer.
    void
    deallocate(pointer __p, size_type)
    { ::operator delete(__p); }

    size_type
    max_size() const _GLIBCXX_USE_NOEXCEPTnoexcept
    { return size_t(-1) / sizeof(_Tp); }

116#if __cplusplus201402L >= 201103L
    template<typename _Up, typename... _Args>
      void
      construct(_Up* __p, _Args&&... __args)
{ ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
21
←
Calling constructor for 'PoolEntry'→

    template<typename _Up>
      void 
      destroy(_Up* __p) { __p->~_Up(); }
125#else
    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // 402. wrong new expression in [some_] allocator::construct
    void 
    construct(pointer __p, const _Tp& __val) 
    { ::new((void *)__p) _Tp(__val); }

    void 
    destroy(pointer __p) { __p->~_Tp(); }
134#endif
  };

template<typename _Tp>
  inline bool
  operator==(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
  { return true; }

template<typename _Tp>
  inline bool
  operator!=(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
  { return false; }

147_GLIBCXX_END_NAMESPACE_VERSION
148} // namespace

150#endif

←

/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h

→

1//===- Math.h - PBQP Vector and Matrix classes ------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8 
9#ifndef LLVM_CODEGEN_PBQP_MATH_H
10#define LLVM_CODEGEN_PBQP_MATH_H
11 
12#include "llvm/ADT/Hashing.h"
13#include "llvm/ADT/STLExtras.h"
14#include <algorithm>
15#include <cassert>
16#include <functional>
17#include <memory>
18 
19namespace llvm {
20namespace PBQP {
21 
22using PBQPNum = float;
23 
24/// PBQP Vector class.
25class Vector {
26  friend hash_code hash_value(const Vector &);
27 
28public:
29  /// Construct a PBQP vector of the given size.
30  explicit Vector(unsigned Length)
31    : Length(Length), Data(std::make_unique<PBQPNum []>(Length)) {}
32 
33  /// Construct a PBQP vector with initializer.
34  Vector(unsigned Length, PBQPNum InitVal)
35    : Length(Length), Data(std::make_unique<PBQPNum []>(Length)) {
36    std::fill(Data.get(), Data.get() + Length, InitVal);
37  }
38 
39  /// Copy construct a PBQP vector.
40  Vector(const Vector &V)
41    : Length(V.Length), Data(std::make_unique<PBQPNum []>(Length)) {
42    std::copy(V.Data.get(), V.Data.get() + Length, Data.get());
43  }
44 
45  /// Move construct a PBQP vector.
46  Vector(Vector &&V)
47    : Length(V.Length), Data(std::move(V.Data)) {
48    V.Length = 0;
49  }
50 
51  /// Comparison operator.
52  bool operator==(const Vector &V) const {
53    assert(Length != 0 && Data && "Invalid vector")((Length != 0 && Data && "Invalid vector") ? static_cast
<void> (0) : __assert_fail ("Length != 0 && Data && \"Invalid vector\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 53, __PRETTY_FUNCTION__));
54    if (Length != V.Length)
55      return false;
56    return std::equal(Data.get(), Data.get() + Length, V.Data.get());
57  }
58 
59  /// Return the length of the vector
60  unsigned getLength() const {
61    assert(Length != 0 && Data && "Invalid vector")((Length != 0 && Data && "Invalid vector") ? static_cast
<void> (0) : __assert_fail ("Length != 0 && Data && \"Invalid vector\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 61, __PRETTY_FUNCTION__));
62    return Length;
63  }
64 
65  /// Element access.
66  PBQPNum& operator[](unsigned Index) {
67    assert(Length != 0 && Data && "Invalid vector")((Length != 0 && Data && "Invalid vector") ? static_cast
<void> (0) : __assert_fail ("Length != 0 && Data && \"Invalid vector\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 67, __PRETTY_FUNCTION__));
68    assert(Index < Length && "Vector element access out of bounds.")((Index < Length && "Vector element access out of bounds."
) ? static_cast<void> (0) : __assert_fail ("Index < Length && \"Vector element access out of bounds.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 68, __PRETTY_FUNCTION__));
69    return Data[Index];
70  }
71 
72  /// Const element access.
73  const PBQPNum& operator[](unsigned Index) const {
74    assert(Length != 0 && Data && "Invalid vector")((Length != 0 && Data && "Invalid vector") ? static_cast
<void> (0) : __assert_fail ("Length != 0 && Data && \"Invalid vector\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 74, __PRETTY_FUNCTION__));
75    assert(Index < Length && "Vector element access out of bounds.")((Index < Length && "Vector element access out of bounds."
) ? static_cast<void> (0) : __assert_fail ("Index < Length && \"Vector element access out of bounds.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 75, __PRETTY_FUNCTION__));
76    return Data[Index];
77  }
78 
79  /// Add another vector to this one.
80  Vector& operator+=(const Vector &V) {
81    assert(Length != 0 && Data && "Invalid vector")((Length != 0 && Data && "Invalid vector") ? static_cast
<void> (0) : __assert_fail ("Length != 0 && Data && \"Invalid vector\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 81, __PRETTY_FUNCTION__));
82    assert(Length == V.Length && "Vector length mismatch.")((Length == V.Length && "Vector length mismatch.") ? static_cast
<void> (0) : __assert_fail ("Length == V.Length && \"Vector length mismatch.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 82, __PRETTY_FUNCTION__));
83    std::transform(Data.get(), Data.get() + Length, V.Data.get(), Data.get(),
84                   std::plus<PBQPNum>());
85    return *this;
86  }
87 
88  /// Returns the index of the minimum value in this vector
89  unsigned minIndex() const {
90    assert(Length != 0 && Data && "Invalid vector")((Length != 0 && Data && "Invalid vector") ? static_cast
<void> (0) : __assert_fail ("Length != 0 && Data && \"Invalid vector\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 90, __PRETTY_FUNCTION__));
91    return std::min_element(Data.get(), Data.get() + Length) - Data.get();
92  }
93 
94private:
95  unsigned Length;
96  std::unique_ptr<PBQPNum []> Data;
97};
98 
99/// Return a hash_value for the given vector.
100inline hash_code hash_value(const Vector &V) {
101  unsigned *VBegin = reinterpret_cast<unsigned*>(V.Data.get());
102  unsigned *VEnd = reinterpret_cast<unsigned*>(V.Data.get() + V.Length);
103  return hash_combine(V.Length, hash_combine_range(VBegin, VEnd));
104}
105 
106/// Output a textual representation of the given vector on the given
107///        output stream.
108template <typename OStream>
109OStream& operator<<(OStream &OS, const Vector &V) {
110  assert((V.getLength() != 0) && "Zero-length vector badness.")(((V.getLength() != 0) && "Zero-length vector badness."
) ? static_cast<void> (0) : __assert_fail ("(V.getLength() != 0) && \"Zero-length vector badness.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 110, __PRETTY_FUNCTION__));
111 
112  OS << "[ " << V[0];
113  for (unsigned i = 1; i < V.getLength(); ++i)
114    OS << ", " << V[i];
115  OS << " ]";
116 
117  return OS;
118}
119 
120/// PBQP Matrix class
121class Matrix {
122private:
123  friend hash_code hash_value(const Matrix &);
124 
125public:
126  /// Construct a PBQP Matrix with the given dimensions.
127  Matrix(unsigned Rows, unsigned Cols) :
128    Rows(Rows), Cols(Cols), Data(std::make_unique<PBQPNum []>(Rows * Cols)) {
129  }
130 
131  /// Construct a PBQP Matrix with the given dimensions and initial
132  /// value.
133  Matrix(unsigned Rows, unsigned Cols, PBQPNum InitVal)
134    : Rows(Rows), Cols(Cols),
135      Data(std::make_unique<PBQPNum []>(Rows * Cols)) {
136    std::fill(Data.get(), Data.get() + (Rows * Cols), InitVal);
137  }
138 
139  /// Copy construct a PBQP matrix.
140  Matrix(const Matrix &M)
141    : Rows(M.Rows), Cols(M.Cols),
142      Data(std::make_unique<PBQPNum []>(Rows * Cols)) {
143    std::copy(M.Data.get(), M.Data.get() + (Rows * Cols), Data.get());
144  }
145 
146  /// Move construct a PBQP matrix.
147  Matrix(Matrix &&M)
148    : Rows(M.Rows), Cols(M.Cols), Data(std::move(M.Data)) {
149    M.Rows = M.Cols = 0;
150  }
151 
152  /// Comparison operator.
153  bool operator==(const Matrix &M) const {
154    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")((Rows != 0 && Cols != 0 && Data && "Invalid matrix"
) ? static_cast<void> (0) : __assert_fail ("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 154, __PRETTY_FUNCTION__));
155    if (Rows != M.Rows || Cols != M.Cols)
156      return false;
157    return std::equal(Data.get(), Data.get() + (Rows * Cols), M.Data.get());
158  }
159 
160  /// Return the number of rows in this matrix.
161  unsigned getRows() const {
162    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")((Rows != 0 && Cols != 0 && Data && "Invalid matrix"
) ? static_cast<void> (0) : __assert_fail ("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 162, __PRETTY_FUNCTION__));
163    return Rows;
164  }
165 
166  /// Return the number of cols in this matrix.
167  unsigned getCols() const {
168    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")((Rows != 0 && Cols != 0 && Data && "Invalid matrix"
) ? static_cast<void> (0) : __assert_fail ("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 168, __PRETTY_FUNCTION__));
169    return Cols;
170  }
171 
172  /// Matrix element access.
173  PBQPNum* operator[](unsigned R) {
174    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")((Rows != 0 && Cols != 0 && Data && "Invalid matrix"
) ? static_cast<void> (0) : __assert_fail ("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 174, __PRETTY_FUNCTION__));
175    assert(R < Rows && "Row out of bounds.")((R < Rows && "Row out of bounds.") ? static_cast<
void> (0) : __assert_fail ("R < Rows && \"Row out of bounds.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 175, __PRETTY_FUNCTION__));
176    return Data.get() + (R * Cols);
177  }
178 
179  /// Matrix element access.
180  const PBQPNum* operator[](unsigned R) const {
181    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")((Rows != 0 && Cols != 0 && Data && "Invalid matrix"
) ? static_cast<void> (0) : __assert_fail ("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 181, __PRETTY_FUNCTION__));
182    assert(R < Rows && "Row out of bounds.")((R < Rows && "Row out of bounds.") ? static_cast<
void> (0) : __assert_fail ("R < Rows && \"Row out of bounds.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 182, __PRETTY_FUNCTION__));
183    return Data.get() + (R * Cols);
184  }
185 
186  /// Returns the given row as a vector.
187  Vector getRowAsVector(unsigned R) const {
188    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")((Rows != 0 && Cols != 0 && Data && "Invalid matrix"
) ? static_cast<void> (0) : __assert_fail ("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 188, __PRETTY_FUNCTION__));
189    Vector V(Cols);
190    for (unsigned C = 0; C < Cols; ++C)
191      V[C] = (*this)[R][C];
192    return V;
193  }
194 
195  /// Returns the given column as a vector.
196  Vector getColAsVector(unsigned C) const {
197    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")((Rows != 0 && Cols != 0 && Data && "Invalid matrix"
) ? static_cast<void> (0) : __assert_fail ("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 197, __PRETTY_FUNCTION__));
198    Vector V(Rows);
199    for (unsigned R = 0; R < Rows; ++R)
200      V[R] = (*this)[R][C];
201    return V;
202  }
203 
204  /// Matrix transpose.
205  Matrix transpose() const {
206    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")((Rows != 0 && Cols != 0 && Data && "Invalid matrix"
) ? static_cast<void> (0) : __assert_fail ("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 206, __PRETTY_FUNCTION__));
207    Matrix M(Cols, Rows);
208    for (unsigned r = 0; r < Rows; ++r)
209      for (unsigned c = 0; c < Cols; ++c)
210        M[c][r] = (*this)[r][c];
211    return M;
212  }
213 
214  /// Add the given matrix to this one.
215  Matrix& operator+=(const Matrix &M) {
216    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")((Rows != 0 && Cols != 0 && Data && "Invalid matrix"
) ? static_cast<void> (0) : __assert_fail ("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 216, __PRETTY_FUNCTION__));
217    assert(Rows == M.Rows && Cols == M.Cols &&((Rows == M.Rows && Cols == M.Cols && "Matrix dimensions mismatch."
) ? static_cast<void> (0) : __assert_fail ("Rows == M.Rows && Cols == M.Cols && \"Matrix dimensions mismatch.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 218, __PRETTY_FUNCTION__))
218           "Matrix dimensions mismatch.")((Rows == M.Rows && Cols == M.Cols && "Matrix dimensions mismatch."
) ? static_cast<void> (0) : __assert_fail ("Rows == M.Rows && Cols == M.Cols && \"Matrix dimensions mismatch.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 218, __PRETTY_FUNCTION__));
219    std::transform(Data.get(), Data.get() + (Rows * Cols), M.Data.get(),
220                   Data.get(), std::plus<PBQPNum>());
221    return *this;
222  }
223 
224  Matrix operator+(const Matrix &M) {
225    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")((Rows != 0 && Cols != 0 && Data && "Invalid matrix"
) ? static_cast<void> (0) : __assert_fail ("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 225, __PRETTY_FUNCTION__));
226    Matrix Tmp(*this);
227    Tmp += M;
228    return Tmp;
229  }
230 
231private:
232  unsigned Rows, Cols;
233  std::unique_ptr<PBQPNum []> Data;
234};
235 
236/// Return a hash_code for the given matrix.
237inline hash_code hash_value(const Matrix &M) {
238  unsigned *MBegin = reinterpret_cast<unsigned*>(M.Data.get());
239  unsigned *MEnd =
240    reinterpret_cast<unsigned*>(M.Data.get() + (M.Rows * M.Cols));
241  return hash_combine(M.Rows, M.Cols, hash_combine_range(MBegin, MEnd));
242}
243 
244/// Output a textual representation of the given matrix on the given
245///        output stream.
246template <typename OStream>
247OStream& operator<<(OStream &OS, const Matrix &M) {
248  assert((M.getRows() != 0) && "Zero-row matrix badness.")(((M.getRows() != 0) && "Zero-row matrix badness.") ?
 static_cast<void> (0) : __assert_fail ("(M.getRows() != 0) && \"Zero-row matrix badness.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/PBQP/Math.h"
, 248, __PRETTY_FUNCTION__));
249  for (unsigned i = 0; i < M.getRows(); ++i)
250    OS << M.getRowAsVector(i) << "\n";
251  return OS;
252}
253 
254template <typename Metadata>
255class MDVector : public Vector {
256public:
257  MDVector(const Vector &v) : Vector(v), md(*this) {}
258  MDVector(Vector &&v) : Vector(std::move(v)), md(*this) { }
259 
260  const Metadata& getMetadata() const { return md; }
261 
262private:
263  Metadata md;
264};
265 
266template <typename Metadata>
267inline hash_code hash_value(const MDVector<Metadata> &V) {
268  return hash_value(static_cast<const Vector&>(V));
269}
270 
271template <typename Metadata>
272class MDMatrix : public Matrix {
273public:
274  MDMatrix(const Matrix &m) : Matrix(m), md(*this) {}
275  MDMatrix(Matrix &&m) : Matrix(std::move(m)), md(*this) { }
23
←
Calling constructor for 'MatrixMetadata'→
276 
277  const Metadata& getMetadata() const { return md; }
278 
279private:
280  Metadata md;
281};
282 
283template <typename Metadata>
284inline hash_code hash_value(const MDMatrix<Metadata> &M) {
285  return hash_value(static_cast<const Matrix&>(M));
286}
287 
288} // end namespace PBQP
289} // end namespace llvm
290 
291#endif // LLVM_CODEGEN_PBQP_MATH_H

←

/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/RegAllocPBQP.h

1//===- RegAllocPBQP.h -------------------------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the PBQPBuilder interface, for classes which build PBQP
10// instances to represent register allocation problems, and the RegAllocPBQP
11// interface.
12//
13//===----------------------------------------------------------------------===//

15#ifndef LLVM_CODEGEN_REGALLOCPBQP_H
16#define LLVM_CODEGEN_REGALLOCPBQP_H

18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/Hashing.h"
20#include "llvm/CodeGen/PBQP/CostAllocator.h"
21#include "llvm/CodeGen/PBQP/Graph.h"
22#include "llvm/CodeGen/PBQP/Math.h"
23#include "llvm/CodeGen/PBQP/ReductionRules.h"
24#include "llvm/CodeGen/PBQP/Solution.h"
25#include "llvm/CodeGen/Register.h"
26#include "llvm/MC/MCRegister.h"
27#include "llvm/Support/ErrorHandling.h"
28#include <algorithm>
29#include <cassert>
30#include <cstddef>
31#include <limits>
32#include <memory>
33#include <set>
34#include <vector>

36namespace llvm {

38class FunctionPass;
39class LiveIntervals;
40class MachineBlockFrequencyInfo;
41class MachineFunction;
42class raw_ostream;

44namespace PBQP {
45namespace RegAlloc {

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

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

  for (unsigned i = 1; i < M.getRows(); ++i) {
25
←
Loop condition is true.  Entering loop body→
27
←
Loop condition is false. Execution continues on line 73→
    unsigned RowCount = 0;
    for (unsigned j = 1; j < M.getCols(); ++j) {
26
←
Loop condition is false. Execution continues on line 70→
      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);
28
←
Use of zero-allocated memory
  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(); }

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

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

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

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

unsigned size() const { return NumOpts; }
MCRegister 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);
}

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

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

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

136public:
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(Register VReg, GraphBase::NodeId NId) {
  VRegToNodeId[VReg.id()] = NId;
}

GraphBase::NodeId getNodeIdForVReg(Register 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));
}

163private:
DenseMap<Register, GraphBase::NodeId> VRegToNodeId;
AllowedRegVecPool AllowedRegVecs;
166};

168/// Holds solver state and other metadata relevant to each PBQP RA node.
169class NodeMetadata {
170public:
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)
189#ifndef NDEBUG
    , everConservativelyAllocatable(Other.everConservativelyAllocatable)
191#endif
{
  if (NumOpts > 0) {
    std::copy(&Other.OptUnsafeEdges[0], &Other.OptUnsafeEdges[NumOpts],
              &OptUnsafeEdges[0]);
  }
}

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

void setVReg(Register VReg) { this->VReg = VReg; }
Register 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")((RS >= this->RS && "A node's reduction state can not be downgraded"
) ? static_cast<void> (0) : __assert_fail ("RS >= this->RS && \"A node's reduction state can not be downgraded\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/RegAllocPBQP.h"
, 217, __PRETTY_FUNCTION__));
  this->RS = RS;

220#ifndef NDEBUG
  // Remember this state to assert later that a non-infinite register
  // option was available.
  if (RS == ConservativelyAllocatable)
    everConservativelyAllocatable = true;
225#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]);
}

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

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

264#ifndef NDEBUG
bool everConservativelyAllocatable = false;
266#endif
267};

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

273public:
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 &&((G.getNodeCosts(NId).getLength() > 1 && "PBQP Graph should not contain single or zero-option nodes"
) ? static_cast<void> (0) : __assert_fail ("G.getNodeCosts(NId).getLength() > 1 && \"PBQP Graph should not contain single or zero-option nodes\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/RegAllocPBQP.h"
, 302, __PRETTY_FUNCTION__))
         "PBQP Graph should not contain single or zero-option nodes")((G.getNodeCosts(NId).getLength() > 1 && "PBQP Graph should not contain single or zero-option nodes"
) ? static_cast<void> (0) : __assert_fail ("G.getNodeCosts(NId).getLength() > 1 && \"PBQP Graph should not contain single or zero-option nodes\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/RegAllocPBQP.h"
, 302, __PRETTY_FUNCTION__));
  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);
}

351private:
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.find(NId) != OptimallyReducibleNodes
.end() && "Node not in optimally reducible set.") ? static_cast
<void> (0) : __assert_fail ("OptimallyReducibleNodes.find(NId) != OptimallyReducibleNodes.end() && \"Node not in optimally reducible set.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/RegAllocPBQP.h"
, 370, __PRETTY_FUNCTION__))
           OptimallyReducibleNodes.end() &&((OptimallyReducibleNodes.find(NId) != OptimallyReducibleNodes
.end() && "Node not in optimally reducible set.") ? static_cast
<void> (0) : __assert_fail ("OptimallyReducibleNodes.find(NId) != OptimallyReducibleNodes.end() && \"Node not in optimally reducible set.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/RegAllocPBQP.h"
, 370, __PRETTY_FUNCTION__))
           "Node not in optimally reducible set.")((OptimallyReducibleNodes.find(NId) != OptimallyReducibleNodes
.end() && "Node not in optimally reducible set.") ? static_cast
<void> (0) : __assert_fail ("OptimallyReducibleNodes.find(NId) != OptimallyReducibleNodes.end() && \"Node not in optimally reducible set.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/RegAllocPBQP.h"
, 370, __PRETTY_FUNCTION__));
    OptimallyReducibleNodes.erase(NId);
    break;
  case NodeMetadata::ConservativelyAllocatable:
    assert(ConservativelyAllocatableNodes.find(NId) !=((ConservativelyAllocatableNodes.find(NId) != ConservativelyAllocatableNodes
.end() && "Node not in conservatively allocatable set."
) ? static_cast<void> (0) : __assert_fail ("ConservativelyAllocatableNodes.find(NId) != ConservativelyAllocatableNodes.end() && \"Node not in conservatively allocatable set.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/RegAllocPBQP.h"
, 376, __PRETTY_FUNCTION__))
           ConservativelyAllocatableNodes.end() &&((ConservativelyAllocatableNodes.find(NId) != ConservativelyAllocatableNodes
.end() && "Node not in conservatively allocatable set."
) ? static_cast<void> (0) : __assert_fail ("ConservativelyAllocatableNodes.find(NId) != ConservativelyAllocatableNodes.end() && \"Node not in conservatively allocatable set.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/RegAllocPBQP.h"
, 376, __PRETTY_FUNCTION__))
           "Node not in conservatively allocatable set.")((ConservativelyAllocatableNodes.find(NId) != ConservativelyAllocatableNodes
.end() && "Node not in conservatively allocatable set."
) ? static_cast<void> (0) : __assert_fail ("ConservativelyAllocatableNodes.find(NId) != ConservativelyAllocatableNodes.end() && \"Node not in conservatively allocatable set.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/RegAllocPBQP.h"
, 376, __PRETTY_FUNCTION__));
    ConservativelyAllocatableNodes.erase(NId);
    break;
  case NodeMetadata::NotProvablyAllocatable:
    assert(NotProvablyAllocatableNodes.find(NId) !=((NotProvablyAllocatableNodes.find(NId) != NotProvablyAllocatableNodes
.end() && "Node not in not-provably-allocatable set."
) ? static_cast<void> (0) : __assert_fail ("NotProvablyAllocatableNodes.find(NId) != NotProvablyAllocatableNodes.end() && \"Node not in not-provably-allocatable set.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/RegAllocPBQP.h"
, 382, __PRETTY_FUNCTION__))
           NotProvablyAllocatableNodes.end() &&((NotProvablyAllocatableNodes.find(NId) != NotProvablyAllocatableNodes
.end() && "Node not in not-provably-allocatable set."
) ? static_cast<void> (0) : __assert_fail ("NotProvablyAllocatableNodes.find(NId) != NotProvablyAllocatableNodes.end() && \"Node not in not-provably-allocatable set.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/RegAllocPBQP.h"
, 382, __PRETTY_FUNCTION__))
           "Node not in not-provably-allocatable set.")((NotProvablyAllocatableNodes.find(NId) != NotProvablyAllocatableNodes
.end() && "Node not in not-provably-allocatable set."
) ? static_cast<void> (0) : __assert_fail ("NotProvablyAllocatableNodes.find(NId) != NotProvablyAllocatableNodes.end() && \"Node not in not-provably-allocatable set.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/RegAllocPBQP.h"
, 382, __PRETTY_FUNCTION__));
    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.")((!G.empty() && "Cannot reduce empty graph.") ? static_cast
<void> (0) : __assert_fail ("!G.empty() && \"Cannot reduce empty graph.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/RegAllocPBQP.h"
, 428, __PRETTY_FUNCTION__));

  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.")::llvm::llvm_unreachable_internal("Not an optimally reducible node."
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/CodeGen/RegAllocPBQP.h"
, 449);
      }
    } 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;
500};

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

506public:
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;
519};

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

528} // end namespace RegAlloc
529} // end namespace PBQP

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

535} // end namespace llvm

537#endif // LLVM_CODEGEN_REGALLOCPBQP_H