/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/CodeGen/InlineSpiller.cpp

Bug Summary

File:	src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/CodeGen/InlineSpiller.cpp
Warning:	line 1348, column 14 Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name InlineSpiller.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 -mrelocation-model pic -pic-level 1 -fhalf-no-semantic-interposition -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Analysis -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ASMParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/BinaryFormat -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitstream -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /include/llvm/CodeGen -I /include/llvm/CodeGen/PBQP -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Coroutines -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData/Coverage -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/CodeView -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/DWARF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/MSF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/PDB -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Demangle -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/JITLink -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/Orc -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenACC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenMP -I /include/llvm/CodeGen/GlobalISel -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IRReader -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/LTO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Linker -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC/MCParser -I /include/llvm/CodeGen/MIRParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Object -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Option -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Passes -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Scalar -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ADT -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/Symbolize -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Target -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Utils -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Vectorize -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/IPO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include -I /usr/src/gnu/usr.bin/clang/libLLVM/../include -I /usr/src/gnu/usr.bin/clang/libLLVM/obj -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include -D NDEBUG -D __STDC_LIMIT_MACROS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D LLVM_PREFIX="/usr" -D PIC -internal-isystem /usr/include/c++/v1 -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -ferror-limit 19 -fvisibility-inlines-hidden -fwrapv -D_RET_PROTECTOR -ret-protector -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c++ /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/CodeGen/InlineSpiller.cpp

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/CodeGen/InlineSpiller.cpp

→

1//===- InlineSpiller.cpp - Insert spills and restores inline --------------===//
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// The inline spiller modifies the machine function directly instead of
10// inserting spills and restores in VirtRegMap.
11//
12//===----------------------------------------------------------------------===//

14#include "SplitKit.h"
15#include "llvm/ADT/ArrayRef.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/MapVector.h"
18#include "llvm/ADT/None.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SetVector.h"
21#include "llvm/ADT/SmallPtrSet.h"
22#include "llvm/ADT/SmallVector.h"
23#include "llvm/ADT/Statistic.h"
24#include "llvm/Analysis/AliasAnalysis.h"
25#include "llvm/CodeGen/LiveInterval.h"
26#include "llvm/CodeGen/LiveIntervalCalc.h"
27#include "llvm/CodeGen/LiveIntervals.h"
28#include "llvm/CodeGen/LiveRangeEdit.h"
29#include "llvm/CodeGen/LiveStacks.h"
30#include "llvm/CodeGen/MachineBasicBlock.h"
31#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
32#include "llvm/CodeGen/MachineDominators.h"
33#include "llvm/CodeGen/MachineFunction.h"
34#include "llvm/CodeGen/MachineFunctionPass.h"
35#include "llvm/CodeGen/MachineInstr.h"
36#include "llvm/CodeGen/MachineInstrBuilder.h"
37#include "llvm/CodeGen/MachineInstrBundle.h"
38#include "llvm/CodeGen/MachineLoopInfo.h"
39#include "llvm/CodeGen/MachineOperand.h"
40#include "llvm/CodeGen/MachineRegisterInfo.h"
41#include "llvm/CodeGen/SlotIndexes.h"
42#include "llvm/CodeGen/Spiller.h"
43#include "llvm/CodeGen/StackMaps.h"
44#include "llvm/CodeGen/TargetInstrInfo.h"
45#include "llvm/CodeGen/TargetOpcodes.h"
46#include "llvm/CodeGen/TargetRegisterInfo.h"
47#include "llvm/CodeGen/TargetSubtargetInfo.h"
48#include "llvm/CodeGen/VirtRegMap.h"
49#include "llvm/Config/llvm-config.h"
50#include "llvm/Support/BlockFrequency.h"
51#include "llvm/Support/BranchProbability.h"
52#include "llvm/Support/CommandLine.h"
53#include "llvm/Support/Compiler.h"
54#include "llvm/Support/Debug.h"
55#include "llvm/Support/ErrorHandling.h"
56#include "llvm/Support/raw_ostream.h"
57#include <cassert>
58#include <iterator>
59#include <tuple>
60#include <utility>
61#include <vector>

63using namespace llvm;

65#define DEBUG_TYPE"regalloc" "regalloc"

67STATISTIC(NumSpilledRanges,   "Number of spilled live ranges")static llvm::Statistic NumSpilledRanges = {"regalloc", "NumSpilledRanges"
, "Number of spilled live ranges"};
68STATISTIC(NumSnippets,        "Number of spilled snippets")static llvm::Statistic NumSnippets = {"regalloc", "NumSnippets"
, "Number of spilled snippets"};
69STATISTIC(NumSpills,          "Number of spills inserted")static llvm::Statistic NumSpills = {"regalloc", "NumSpills", "Number of spills inserted"
};
70STATISTIC(NumSpillsRemoved,   "Number of spills removed")static llvm::Statistic NumSpillsRemoved = {"regalloc", "NumSpillsRemoved"
, "Number of spills removed"};
71STATISTIC(NumReloads,         "Number of reloads inserted")static llvm::Statistic NumReloads = {"regalloc", "NumReloads"
, "Number of reloads inserted"};
72STATISTIC(NumReloadsRemoved,  "Number of reloads removed")static llvm::Statistic NumReloadsRemoved = {"regalloc", "NumReloadsRemoved"
, "Number of reloads removed"};
73STATISTIC(NumFolded,          "Number of folded stack accesses")static llvm::Statistic NumFolded = {"regalloc", "NumFolded", "Number of folded stack accesses"
};
74STATISTIC(NumFoldedLoads,     "Number of folded loads")static llvm::Statistic NumFoldedLoads = {"regalloc", "NumFoldedLoads"
, "Number of folded loads"};
75STATISTIC(NumRemats,          "Number of rematerialized defs for spilling")static llvm::Statistic NumRemats = {"regalloc", "NumRemats", "Number of rematerialized defs for spilling"
};

77static cl::opt<bool> DisableHoisting("disable-spill-hoist", cl::Hidden,
                                   cl::desc("Disable inline spill hoisting"));
79static cl::opt<bool>
80RestrictStatepointRemat("restrict-statepoint-remat",
                     cl::init(false), cl::Hidden,
                     cl::desc("Restrict remat for statepoint operands"));

84namespace {

86class HoistSpillHelper : private LiveRangeEdit::Delegate {
MachineFunction &MF;
LiveIntervals &LIS;
LiveStacks &LSS;
AliasAnalysis *AA;
MachineDominatorTree &MDT;
MachineLoopInfo &Loops;
VirtRegMap &VRM;
MachineRegisterInfo &MRI;
const TargetInstrInfo &TII;
const TargetRegisterInfo &TRI;
const MachineBlockFrequencyInfo &MBFI;

InsertPointAnalysis IPA;

// Map from StackSlot to the LiveInterval of the original register.
// Note the LiveInterval of the original register may have been deleted
// after it is spilled. We keep a copy here to track the range where
// spills can be moved.
DenseMap<int, std::unique_ptr<LiveInterval>> StackSlotToOrigLI;

// Map from pair of (StackSlot and Original VNI) to a set of spills which
// have the same stackslot and have equal values defined by Original VNI.
// These spills are mergeable and are hoist candiates.
using MergeableSpillsMap =
    MapVector<std::pair<int, VNInfo *>, SmallPtrSet<MachineInstr *, 16>>;
MergeableSpillsMap MergeableSpills;

/// This is the map from original register to a set containing all its
/// siblings. To hoist a spill to another BB, we need to find out a live
/// sibling there and use it as the source of the new spill.
DenseMap<Register, SmallSetVector<Register, 16>> Virt2SiblingsMap;

bool isSpillCandBB(LiveInterval &OrigLI, VNInfo &OrigVNI,
                   MachineBasicBlock &BB, Register &LiveReg);

void rmRedundantSpills(
    SmallPtrSet<MachineInstr *, 16> &Spills,
    SmallVectorImpl<MachineInstr *> &SpillsToRm,
    DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill);

void getVisitOrders(
    MachineBasicBlock *Root, SmallPtrSet<MachineInstr *, 16> &Spills,
    SmallVectorImpl<MachineDomTreeNode *> &Orders,
    SmallVectorImpl<MachineInstr *> &SpillsToRm,
    DenseMap<MachineDomTreeNode *, unsigned> &SpillsToKeep,
    DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill);

void runHoistSpills(LiveInterval &OrigLI, VNInfo &OrigVNI,
                    SmallPtrSet<MachineInstr *, 16> &Spills,
                    SmallVectorImpl<MachineInstr *> &SpillsToRm,
                    DenseMap<MachineBasicBlock *, unsigned> &SpillsToIns);

139public:
HoistSpillHelper(MachineFunctionPass &pass, MachineFunction &mf,
                 VirtRegMap &vrm)
    : MF(mf), LIS(pass.getAnalysis<LiveIntervals>()),
      LSS(pass.getAnalysis<LiveStacks>()),
      AA(&pass.getAnalysis<AAResultsWrapperPass>().getAAResults()),
      MDT(pass.getAnalysis<MachineDominatorTree>()),
      Loops(pass.getAnalysis<MachineLoopInfo>()), VRM(vrm),
      MRI(mf.getRegInfo()), TII(*mf.getSubtarget().getInstrInfo()),
      TRI(*mf.getSubtarget().getRegisterInfo()),
      MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()),
      IPA(LIS, mf.getNumBlockIDs()) {}

void addToMergeableSpills(MachineInstr &Spill, int StackSlot,
                          unsigned Original);
bool rmFromMergeableSpills(MachineInstr &Spill, int StackSlot);
void hoistAllSpills();
void LRE_DidCloneVirtReg(Register, Register) override;
157};

159class InlineSpiller : public Spiller {
MachineFunction &MF;
LiveIntervals &LIS;
LiveStacks &LSS;
AliasAnalysis *AA;
MachineDominatorTree &MDT;
MachineLoopInfo &Loops;
VirtRegMap &VRM;
MachineRegisterInfo &MRI;
const TargetInstrInfo &TII;
const TargetRegisterInfo &TRI;
const MachineBlockFrequencyInfo &MBFI;

// Variables that are valid during spill(), but used by multiple methods.
LiveRangeEdit *Edit;
LiveInterval *StackInt;
int StackSlot;
Register Original;

// All registers to spill to StackSlot, including the main register.
SmallVector<Register, 8> RegsToSpill;

// All COPY instructions to/from snippets.
// They are ignored since both operands refer to the same stack slot.
SmallPtrSet<MachineInstr*, 8> SnippetCopies;

// Values that failed to remat at some point.
SmallPtrSet<VNInfo*, 8> UsedValues;

// Dead defs generated during spilling.
SmallVector<MachineInstr*, 8> DeadDefs;

// Object records spills information and does the hoisting.
HoistSpillHelper HSpiller;

// Live range weight calculator.
VirtRegAuxInfo &VRAI;

~InlineSpiller() override = default;

199public:
InlineSpiller(MachineFunctionPass &Pass, MachineFunction &MF, VirtRegMap &VRM,
              VirtRegAuxInfo &VRAI)
    : MF(MF), LIS(Pass.getAnalysis<LiveIntervals>()),
      LSS(Pass.getAnalysis<LiveStacks>()),
      AA(&Pass.getAnalysis<AAResultsWrapperPass>().getAAResults()),
      MDT(Pass.getAnalysis<MachineDominatorTree>()),
      Loops(Pass.getAnalysis<MachineLoopInfo>()), VRM(VRM),
      MRI(MF.getRegInfo()), TII(*MF.getSubtarget().getInstrInfo()),
      TRI(*MF.getSubtarget().getRegisterInfo()),
      MBFI(Pass.getAnalysis<MachineBlockFrequencyInfo>()),
      HSpiller(Pass, MF, VRM), VRAI(VRAI) {}

void spill(LiveRangeEdit &) override;
void postOptimization() override;

215private:
bool isSnippet(const LiveInterval &SnipLI);
void collectRegsToSpill();

bool isRegToSpill(Register Reg) { return is_contained(RegsToSpill, Reg); }

bool isSibling(Register Reg);
bool hoistSpillInsideBB(LiveInterval &SpillLI, MachineInstr &CopyMI);
void eliminateRedundantSpills(LiveInterval &LI, VNInfo *VNI);

void markValueUsed(LiveInterval*, VNInfo*);
bool canGuaranteeAssignmentAfterRemat(Register VReg, MachineInstr &MI);
bool reMaterializeFor(LiveInterval &, MachineInstr &MI);
void reMaterializeAll();

bool coalesceStackAccess(MachineInstr *MI, Register Reg);
bool foldMemoryOperand(ArrayRef<std::pair<MachineInstr *, unsigned>>,
                       MachineInstr *LoadMI = nullptr);
void insertReload(Register VReg, SlotIndex, MachineBasicBlock::iterator MI);
void insertSpill(Register VReg, bool isKill, MachineBasicBlock::iterator MI);

void spillAroundUses(Register Reg);
void spillAll();
238};

240} // end anonymous namespace

242Spiller::~Spiller() = default;

244void Spiller::anchor() {}

246Spiller *llvm::createInlineSpiller(MachineFunctionPass &Pass,
                                 MachineFunction &MF, VirtRegMap &VRM,
                                 VirtRegAuxInfo &VRAI) {
return new InlineSpiller(Pass, MF, VRM, VRAI);
250}

252//===----------------------------------------------------------------------===//
253//                                Snippets
254//===----------------------------------------------------------------------===//

256// When spilling a virtual register, we also spill any snippets it is connected
257// to. The snippets are small live ranges that only have a single real use,
258// leftovers from live range splitting. Spilling them enables memory operand
259// folding or tightens the live range around the single use.
260//
261// This minimizes register pressure and maximizes the store-to-load distance for
262// spill slots which can be important in tight loops.

264/// isFullCopyOf - If MI is a COPY to or from Reg, return the other register,
265/// otherwise return 0.
266static Register isFullCopyOf(const MachineInstr &MI, Register Reg) {
if (!MI.isFullCopy())
  return Register();
if (MI.getOperand(0).getReg() == Reg)
  return MI.getOperand(1).getReg();
if (MI.getOperand(1).getReg() == Reg)
  return MI.getOperand(0).getReg();
return Register();
274}

276static void getVDefInterval(const MachineInstr &MI, LiveIntervals &LIS) {
for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
  const MachineOperand &MO = MI.getOperand(I);
  if (MO.isReg() && MO.isDef() && Register::isVirtualRegister(MO.getReg()))
    LIS.getInterval(MO.getReg());
}
282}

284/// isSnippet - Identify if a live interval is a snippet that should be spilled.
285/// It is assumed that SnipLI is a virtual register with the same original as
286/// Edit->getReg().
287bool InlineSpiller::isSnippet(const LiveInterval &SnipLI) {
Register Reg = Edit->getReg();

// A snippet is a tiny live range with only a single instruction using it
// besides copies to/from Reg or spills/fills. We accept:
//
//   %snip = COPY %Reg / FILL fi#
//   %snip = USE %snip
//   %Reg = COPY %snip / SPILL %snip, fi#
//
if (SnipLI.getNumValNums() > 2 || !LIS.intervalIsInOneMBB(SnipLI))
  return false;

MachineInstr *UseMI = nullptr;

// Check that all uses satisfy our criteria.
for (MachineRegisterInfo::reg_instr_nodbg_iterator
         RI = MRI.reg_instr_nodbg_begin(SnipLI.reg()),
         E = MRI.reg_instr_nodbg_end();
     RI != E;) {
  MachineInstr &MI = *RI++;

  // Allow copies to/from Reg.
  if (isFullCopyOf(MI, Reg))
    continue;

  // Allow stack slot loads.
  int FI;
  if (SnipLI.reg() == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot)
    continue;

  // Allow stack slot stores.
  if (SnipLI.reg() == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot)
    continue;

  // Allow a single additional instruction.
  if (UseMI && &MI != UseMI)
    return false;
  UseMI = &MI;
}
return true;
328}

330/// collectRegsToSpill - Collect live range snippets that only have a single
331/// real use.
332void InlineSpiller::collectRegsToSpill() {
Register Reg = Edit->getReg();

// Main register always spills.
RegsToSpill.assign(1, Reg);
SnippetCopies.clear();

// Snippets all have the same original, so there can't be any for an original
// register.
if (Original == Reg)
  return;

for (MachineRegisterInfo::reg_instr_iterator
     RI = MRI.reg_instr_begin(Reg), E = MRI.reg_instr_end(); RI != E; ) {
  MachineInstr &MI = *RI++;
  Register SnipReg = isFullCopyOf(MI, Reg);
  if (!isSibling(SnipReg))
    continue;
  LiveInterval &SnipLI = LIS.getInterval(SnipReg);
  if (!isSnippet(SnipLI))
    continue;
  SnippetCopies.insert(&MI);
  if (isRegToSpill(SnipReg))
    continue;
  RegsToSpill.push_back(SnipReg);
  LLVM_DEBUG(dbgs() << "\talso spill snippet " << SnipLI << '\n')do { } while (false);
  ++NumSnippets;
}
360}

362bool InlineSpiller::isSibling(Register Reg) {
return Reg.isVirtual() && VRM.getOriginal(Reg) == Original;
364}

366/// It is beneficial to spill to earlier place in the same BB in case
367/// as follows:
368/// There is an alternative def earlier in the same MBB.
369/// Hoist the spill as far as possible in SpillMBB. This can ease
370/// register pressure:
371///
372///   x = def
373///   y = use x
374///   s = copy x
375///
376/// Hoisting the spill of s to immediately after the def removes the
377/// interference between x and y:
378///
379///   x = def
380///   spill x
381///   y = use killed x
382///
383/// This hoist only helps when the copy kills its source.
384///
385bool InlineSpiller::hoistSpillInsideBB(LiveInterval &SpillLI,
                                     MachineInstr &CopyMI) {
SlotIndex Idx = LIS.getInstructionIndex(CopyMI);
388#ifndef NDEBUG1
VNInfo *VNI = SpillLI.getVNInfoAt(Idx.getRegSlot());
assert(VNI && VNI->def == Idx.getRegSlot() && "Not defined by copy")((void)0);
391#endif

Register SrcReg = CopyMI.getOperand(1).getReg();
LiveInterval &SrcLI = LIS.getInterval(SrcReg);
VNInfo *SrcVNI = SrcLI.getVNInfoAt(Idx);
LiveQueryResult SrcQ = SrcLI.Query(Idx);
MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(SrcVNI->def);
if (DefMBB != CopyMI.getParent() || !SrcQ.isKill())
  return false;

// Conservatively extend the stack slot range to the range of the original
// value. We may be able to do better with stack slot coloring by being more
// careful here.
assert(StackInt && "No stack slot assigned yet.")((void)0);
LiveInterval &OrigLI = LIS.getInterval(Original);
VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx);
StackInt->MergeValueInAsValue(OrigLI, OrigVNI, StackInt->getValNumInfo(0));
LLVM_DEBUG(dbgs() << "\tmerged orig valno " << OrigVNI->id << ": "do { } while (false)
                  << *StackInt << '\n')do { } while (false);

// We are going to spill SrcVNI immediately after its def, so clear out
// any later spills of the same value.
eliminateRedundantSpills(SrcLI, SrcVNI);

MachineBasicBlock *MBB = LIS.getMBBFromIndex(SrcVNI->def);
MachineBasicBlock::iterator MII;
if (SrcVNI->isPHIDef())
  MII = MBB->SkipPHIsLabelsAndDebug(MBB->begin());
else {
  MachineInstr *DefMI = LIS.getInstructionFromIndex(SrcVNI->def);
  assert(DefMI && "Defining instruction disappeared")((void)0);
  MII = DefMI;
  ++MII;
}
MachineInstrSpan MIS(MII, MBB);
// Insert spill without kill flag immediately after def.
TII.storeRegToStackSlot(*MBB, MII, SrcReg, false, StackSlot,
                        MRI.getRegClass(SrcReg), &TRI);
LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MII);
for (const MachineInstr &MI : make_range(MIS.begin(), MII))
  getVDefInterval(MI, LIS);
--MII; // Point to store instruction.
LLVM_DEBUG(dbgs() << "\thoisted: " << SrcVNI->def << '\t' << *MII)do { } while (false);

// If there is only 1 store instruction is required for spill, add it
// to mergeable list. In X86 AMX, 2 intructions are required to store.
// We disable the merge for this case.
if (MIS.begin() == MII)
  HSpiller.addToMergeableSpills(*MII, StackSlot, Original);
++NumSpills;
return true;
442}

444/// eliminateRedundantSpills - SLI:VNI is known to be on the stack. Remove any
445/// redundant spills of this value in SLI.reg and sibling copies.
446void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) {
assert(VNI && "Missing value")((void)0);
SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList;
WorkList.push_back(std::make_pair(&SLI, VNI));
assert(StackInt && "No stack slot assigned yet.")((void)0);

do {
  LiveInterval *LI;
  std::tie(LI, VNI) = WorkList.pop_back_val();
  Register Reg = LI->reg();
  LLVM_DEBUG(dbgs() << "Checking redundant spills for " << VNI->id << '@'do { } while (false)
                    << VNI->def << " in " << *LI << '\n')do { } while (false);

  // Regs to spill are taken care of.
  if (isRegToSpill(Reg))
    continue;

  // Add all of VNI's live range to StackInt.
  StackInt->MergeValueInAsValue(*LI, VNI, StackInt->getValNumInfo(0));
  LLVM_DEBUG(dbgs() << "Merged to stack int: " << *StackInt << '\n')do { } while (false);

  // Find all spills and copies of VNI.
  for (MachineRegisterInfo::use_instr_nodbg_iterator
       UI = MRI.use_instr_nodbg_begin(Reg), E = MRI.use_instr_nodbg_end();
       UI != E; ) {
    MachineInstr &MI = *UI++;
    if (!MI.isCopy() && !MI.mayStore())
      continue;
    SlotIndex Idx = LIS.getInstructionIndex(MI);
    if (LI->getVNInfoAt(Idx) != VNI)
      continue;

    // Follow sibling copies down the dominator tree.
    if (Register DstReg = isFullCopyOf(MI, Reg)) {
      if (isSibling(DstReg)) {
         LiveInterval &DstLI = LIS.getInterval(DstReg);
         VNInfo *DstVNI = DstLI.getVNInfoAt(Idx.getRegSlot());
         assert(DstVNI && "Missing defined value")((void)0);
         assert(DstVNI->def == Idx.getRegSlot() && "Wrong copy def slot")((void)0);
         WorkList.push_back(std::make_pair(&DstLI, DstVNI));
      }
      continue;
    }

    // Erase spills.
    int FI;
    if (Reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) {
      LLVM_DEBUG(dbgs() << "Redundant spill " << Idx << '\t' << MI)do { } while (false);
      // eliminateDeadDefs won't normally remove stores, so switch opcode.
      MI.setDesc(TII.get(TargetOpcode::KILL));
      DeadDefs.push_back(&MI);
      ++NumSpillsRemoved;
      if (HSpiller.rmFromMergeableSpills(MI, StackSlot))
        --NumSpills;
    }
  }
} while (!WorkList.empty());
503}

505//===----------------------------------------------------------------------===//
506//                            Rematerialization
507//===----------------------------------------------------------------------===//

509/// markValueUsed - Remember that VNI failed to rematerialize, so its defining
510/// instruction cannot be eliminated. See through snippet copies
511void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) {
SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList;
WorkList.push_back(std::make_pair(LI, VNI));
do {
  std::tie(LI, VNI) = WorkList.pop_back_val();
  if (!UsedValues.insert(VNI).second)
    continue;

  if (VNI->isPHIDef()) {
    MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
    for (MachineBasicBlock *P : MBB->predecessors()) {
      VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(P));
      if (PVNI)
        WorkList.push_back(std::make_pair(LI, PVNI));
    }
    continue;
  }

  // Follow snippet copies.
  MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
  if (!SnippetCopies.count(MI))
    continue;
  LiveInterval &SnipLI = LIS.getInterval(MI->getOperand(1).getReg());
  assert(isRegToSpill(SnipLI.reg()) && "Unexpected register in copy")((void)0);
  VNInfo *SnipVNI = SnipLI.getVNInfoAt(VNI->def.getRegSlot(true));
  assert(SnipVNI && "Snippet undefined before copy")((void)0);
  WorkList.push_back(std::make_pair(&SnipLI, SnipVNI));
} while (!WorkList.empty());
539}

541bool InlineSpiller::canGuaranteeAssignmentAfterRemat(Register VReg,
                                                   MachineInstr &MI) {
if (!RestrictStatepointRemat)
  return true;
// Here's a quick explanation of the problem we're trying to handle here:
// * There are some pseudo instructions with more vreg uses than there are
//   physical registers on the machine.
// * This is normally handled by spilling the vreg, and folding the reload
//   into the user instruction.  (Thus decreasing the number of used vregs
//   until the remainder can be assigned to physregs.)
// * However, since we may try to spill vregs in any order, we can end up
//   trying to spill each operand to the instruction, and then rematting it
//   instead.  When that happens, the new live intervals (for the remats) are
//   expected to be trivially assignable (i.e. RS_Done).  However, since we
//   may have more remats than physregs, we're guaranteed to fail to assign
//   one.
// At the moment, we only handle this for STATEPOINTs since they're the only
// pseudo op where we've seen this.  If we start seeing other instructions
// with the same problem, we need to revisit this.
if (MI.getOpcode() != TargetOpcode::STATEPOINT)
  return true;
// For STATEPOINTs we allow re-materialization for fixed arguments only hoping
// that number of physical registers is enough to cover all fixed arguments.
// If it is not true we need to revisit it.
for (unsigned Idx = StatepointOpers(&MI).getVarIdx(),
              EndIdx = MI.getNumOperands();
     Idx < EndIdx; ++Idx) {
  MachineOperand &MO = MI.getOperand(Idx);
  if (MO.isReg() && MO.getReg() == VReg)
    return false;
}
return true;
573}

575/// reMaterializeFor - Attempt to rematerialize before MI instead of reloading.
576bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, MachineInstr &MI) {
// Analyze instruction
SmallVector<std::pair<MachineInstr *, unsigned>, 8> Ops;
VirtRegInfo RI = AnalyzeVirtRegInBundle(MI, VirtReg.reg(), &Ops);

if (!RI.Reads)
  return false;

SlotIndex UseIdx = LIS.getInstructionIndex(MI).getRegSlot(true);
VNInfo *ParentVNI = VirtReg.getVNInfoAt(UseIdx.getBaseIndex());

if (!ParentVNI) {
  LLVM_DEBUG(dbgs() << "\tadding <undef> flags: ")do { } while (false);
  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
    MachineOperand &MO = MI.getOperand(i);
    if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg())
      MO.setIsUndef();
  }
  LLVM_DEBUG(dbgs() << UseIdx << '\t' << MI)do { } while (false);
  return true;
}

if (SnippetCopies.count(&MI))
  return false;

LiveInterval &OrigLI = LIS.getInterval(Original);
VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);
LiveRangeEdit::Remat RM(ParentVNI);
RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);

if (!Edit->canRematerializeAt(RM, OrigVNI, UseIdx, false)) {
  markValueUsed(&VirtReg, ParentVNI);
  LLVM_DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << MI)do { } while (false);
  return false;
}

// If the instruction also writes VirtReg.reg, it had better not require the
// same register for uses and defs.
if (RI.Tied) {
  markValueUsed(&VirtReg, ParentVNI);
  LLVM_DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << MI)do { } while (false);
  return false;
}

// Before rematerializing into a register for a single instruction, try to
// fold a load into the instruction. That avoids allocating a new register.
if (RM.OrigMI->canFoldAsLoad() &&
    foldMemoryOperand(Ops, RM.OrigMI)) {
  Edit->markRematerialized(RM.ParentVNI);
  ++NumFoldedLoads;
  return true;
}

// If we can't guarantee that we'll be able to actually assign the new vreg,
// we can't remat.
if (!canGuaranteeAssignmentAfterRemat(VirtReg.reg(), MI)) {
  markValueUsed(&VirtReg, ParentVNI);
  LLVM_DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << MI)do { } while (false);
  return false;
}

// Allocate a new register for the remat.
Register NewVReg = Edit->createFrom(Original);

// Finally we can rematerialize OrigMI before MI.
SlotIndex DefIdx =
    Edit->rematerializeAt(*MI.getParent(), MI, NewVReg, RM, TRI);

// We take the DebugLoc from MI, since OrigMI may be attributed to a
// different source location.
auto *NewMI = LIS.getInstructionFromIndex(DefIdx);
NewMI->setDebugLoc(MI.getDebugLoc());

(void)DefIdx;
LLVM_DEBUG(dbgs() << "\tremat:  " << DefIdx << '\t'do { } while (false)
                  << *LIS.getInstructionFromIndex(DefIdx))do { } while (false);

// Replace operands
for (const auto &OpPair : Ops) {
  MachineOperand &MO = OpPair.first->getOperand(OpPair.second);
  if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg()) {
    MO.setReg(NewVReg);
    MO.setIsKill();
  }
}
LLVM_DEBUG(dbgs() << "\t        " << UseIdx << '\t' << MI << '\n')do { } while (false);

++NumRemats;
return true;
665}

667/// reMaterializeAll - Try to rematerialize as many uses as possible,
668/// and trim the live ranges after.
669void InlineSpiller::reMaterializeAll() {
if (!Edit->anyRematerializable(AA))
  return;

UsedValues.clear();

// Try to remat before all uses of snippets.
bool anyRemat = false;
for (Register Reg : RegsToSpill) {
  LiveInterval &LI = LIS.getInterval(Reg);
  for (MachineRegisterInfo::reg_bundle_iterator
         RegI = MRI.reg_bundle_begin(Reg), E = MRI.reg_bundle_end();
       RegI != E; ) {
    MachineInstr &MI = *RegI++;

    // Debug values are not allowed to affect codegen.
    if (MI.isDebugValue())
      continue;

    assert(!MI.isDebugInstr() && "Did not expect to find a use in debug "((void)0)
           "instruction that isn't a DBG_VALUE")((void)0);

    anyRemat |= reMaterializeFor(LI, MI);
  }
}
if (!anyRemat)
  return;

// Remove any values that were completely rematted.
for (Register Reg : RegsToSpill) {
  LiveInterval &LI = LIS.getInterval(Reg);
  for (LiveInterval::vni_iterator I = LI.vni_begin(), E = LI.vni_end();
       I != E; ++I) {
    VNInfo *VNI = *I;
    if (VNI->isUnused() || VNI->isPHIDef() || UsedValues.count(VNI))
      continue;
    MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
    MI->addRegisterDead(Reg, &TRI);
    if (!MI->allDefsAreDead())
      continue;
    LLVM_DEBUG(dbgs() << "All defs dead: " << *MI)do { } while (false);
    DeadDefs.push_back(MI);
  }
}

// Eliminate dead code after remat. Note that some snippet copies may be
// deleted here.
if (DeadDefs.empty())
  return;
LLVM_DEBUG(dbgs() << "Remat created " << DeadDefs.size() << " dead defs.\n")do { } while (false);
Edit->eliminateDeadDefs(DeadDefs, RegsToSpill, AA);

// LiveRangeEdit::eliminateDeadDef is used to remove dead define instructions
// after rematerialization.  To remove a VNI for a vreg from its LiveInterval,
// LiveIntervals::removeVRegDefAt is used. However, after non-PHI VNIs are all
// removed, PHI VNI are still left in the LiveInterval.
// So to get rid of unused reg, we need to check whether it has non-dbg
// reference instead of whether it has non-empty interval.
unsigned ResultPos = 0;
for (Register Reg : RegsToSpill) {
  if (MRI.reg_nodbg_empty(Reg)) {
    Edit->eraseVirtReg(Reg);
    continue;
  }

  assert(LIS.hasInterval(Reg) &&((void)0)
         (!LIS.getInterval(Reg).empty() || !MRI.reg_nodbg_empty(Reg)) &&((void)0)
         "Empty and not used live-range?!")((void)0);

  RegsToSpill[ResultPos++] = Reg;
}
RegsToSpill.erase(RegsToSpill.begin() + ResultPos, RegsToSpill.end());
LLVM_DEBUG(dbgs() << RegsToSpill.size()do { } while (false)
                  << " registers to spill after remat.\n")do { } while (false);
743}

745//===----------------------------------------------------------------------===//
746//                                 Spilling
747//===----------------------------------------------------------------------===//

749/// If MI is a load or store of StackSlot, it can be removed.
750bool InlineSpiller::coalesceStackAccess(MachineInstr *MI, Register Reg) {
int FI = 0;
Register InstrReg = TII.isLoadFromStackSlot(*MI, FI);
bool IsLoad = InstrReg;
if (!IsLoad)
  InstrReg = TII.isStoreToStackSlot(*MI, FI);

// We have a stack access. Is it the right register and slot?
if (InstrReg != Reg || FI != StackSlot)
  return false;

if (!IsLoad)
  HSpiller.rmFromMergeableSpills(*MI, StackSlot);

LLVM_DEBUG(dbgs() << "Coalescing stack access: " << *MI)do { } while (false);
LIS.RemoveMachineInstrFromMaps(*MI);
MI->eraseFromParent();

if (IsLoad) {
  ++NumReloadsRemoved;
  --NumReloads;
} else {
  ++NumSpillsRemoved;
  --NumSpills;
}

return true;
777}

779#if !defined(NDEBUG1) || defined(LLVM_ENABLE_DUMP)
780LLVM_DUMP_METHOD__attribute__((noinline))
781// Dump the range of instructions from B to E with their slot indexes.
782static void dumpMachineInstrRangeWithSlotIndex(MachineBasicBlock::iterator B,
                                             MachineBasicBlock::iterator E,
                                             LiveIntervals const &LIS,
                                             const char *const header,
                                             Register VReg = Register()) {
char NextLine = '\n';
char SlotIndent = '\t';

if (std::next(B) == E) {
  NextLine = ' ';
  SlotIndent = ' ';
}

dbgs() << '\t' << header << ": " << NextLine;

for (MachineBasicBlock::iterator I = B; I != E; ++I) {
  SlotIndex Idx = LIS.getInstructionIndex(*I).getRegSlot();

  // If a register was passed in and this instruction has it as a
  // destination that is marked as an early clobber, print the
  // early-clobber slot index.
  if (VReg) {
    MachineOperand *MO = I->findRegisterDefOperand(VReg);
    if (MO && MO->isEarlyClobber())
      Idx = Idx.getRegSlot(true);
  }

  dbgs() << SlotIndent << Idx << '\t' << *I;
}
811}
812#endif

814/// foldMemoryOperand - Try folding stack slot references in Ops into their
815/// instructions.
816///
817/// @param Ops    Operand indices from AnalyzeVirtRegInBundle().
818/// @param LoadMI Load instruction to use instead of stack slot when non-null.
819/// @return       True on success.
820bool InlineSpiller::
821foldMemoryOperand(ArrayRef<std::pair<MachineInstr *, unsigned>> Ops,
                MachineInstr *LoadMI) {
if (Ops.empty())
  return false;
// Don't attempt folding in bundles.
MachineInstr *MI = Ops.front().first;
if (Ops.back().first != MI || MI->isBundled())
  return false;

bool WasCopy = MI->isCopy();
Register ImpReg;

// TII::foldMemoryOperand will do what we need here for statepoint
// (fold load into use and remove corresponding def). We will replace
// uses of removed def with loads (spillAroundUses).
// For that to work we need to untie def and use to pass it through
// foldMemoryOperand and signal foldPatchpoint that it is allowed to
// fold them.
bool UntieRegs = MI->getOpcode() == TargetOpcode::STATEPOINT;

// Spill subregs if the target allows it.
// We always want to spill subregs for stackmap/patchpoint pseudos.
bool SpillSubRegs = TII.isSubregFoldable() ||
                    MI->getOpcode() == TargetOpcode::STATEPOINT ||
                    MI->getOpcode() == TargetOpcode::PATCHPOINT ||
                    MI->getOpcode() == TargetOpcode::STACKMAP;

// TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied
// operands.
SmallVector<unsigned, 8> FoldOps;
for (const auto &OpPair : Ops) {
  unsigned Idx = OpPair.second;
  assert(MI == OpPair.first && "Instruction conflict during operand folding")((void)0);
  MachineOperand &MO = MI->getOperand(Idx);
  if (MO.isImplicit()) {
    ImpReg = MO.getReg();
    continue;
  }

  if (!SpillSubRegs && MO.getSubReg())
    return false;
  // We cannot fold a load instruction into a def.
  if (LoadMI && MO.isDef())
    return false;
  // Tied use operands should not be passed to foldMemoryOperand.
  if (UntieRegs || !MI->isRegTiedToDefOperand(Idx))
    FoldOps.push_back(Idx);
}

// If we only have implicit uses, we won't be able to fold that.
// Moreover, TargetInstrInfo::foldMemoryOperand will assert if we try!
if (FoldOps.empty())
  return false;

MachineInstrSpan MIS(MI, MI->getParent());

SmallVector<std::pair<unsigned, unsigned> > TiedOps;
if (UntieRegs)
  for (unsigned Idx : FoldOps) {
    MachineOperand &MO = MI->getOperand(Idx);
    if (!MO.isTied())
      continue;
    unsigned Tied = MI->findTiedOperandIdx(Idx);
    if (MO.isUse())
      TiedOps.emplace_back(Tied, Idx);
    else {
      assert(MO.isDef() && "Tied to not use and def?")((void)0);
      TiedOps.emplace_back(Idx, Tied);
    }
    MI->untieRegOperand(Idx);
  }

MachineInstr *FoldMI =
    LoadMI ? TII.foldMemoryOperand(*MI, FoldOps, *LoadMI, &LIS)
           : TII.foldMemoryOperand(*MI, FoldOps, StackSlot, &LIS, &VRM);
if (!FoldMI) {
  // Re-tie operands.
  for (auto Tied : TiedOps)
    MI->tieOperands(Tied.first, Tied.second);
  return false;
}

// Remove LIS for any dead defs in the original MI not in FoldMI.
for (MIBundleOperands MO(*MI); MO.isValid(); ++MO) {
  if (!MO->isReg())
    continue;
  Register Reg = MO->getReg();
  if (!Reg || Register::isVirtualRegister(Reg) || MRI.isReserved(Reg)) {
    continue;
  }
  // Skip non-Defs, including undef uses and internal reads.
  if (MO->isUse())
    continue;
  PhysRegInfo RI = AnalyzePhysRegInBundle(*FoldMI, Reg, &TRI);
  if (RI.FullyDefined)
    continue;
  // FoldMI does not define this physreg. Remove the LI segment.
  assert(MO->isDead() && "Cannot fold physreg def")((void)0);
  SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();
  LIS.removePhysRegDefAt(Reg.asMCReg(), Idx);
}

int FI;
if (TII.isStoreToStackSlot(*MI, FI) &&
    HSpiller.rmFromMergeableSpills(*MI, FI))
  --NumSpills;
LIS.ReplaceMachineInstrInMaps(*MI, *FoldMI);
// Update the call site info.
if (MI->isCandidateForCallSiteEntry())
  MI->getMF()->moveCallSiteInfo(MI, FoldMI);
MI->eraseFromParent();

// Insert any new instructions other than FoldMI into the LIS maps.
assert(!MIS.empty() && "Unexpected empty span of instructions!")((void)0);
for (MachineInstr &MI : MIS)
  if (&MI != FoldMI)
    LIS.InsertMachineInstrInMaps(MI);

// TII.foldMemoryOperand may have left some implicit operands on the
// instruction.  Strip them.
if (ImpReg)
  for (unsigned i = FoldMI->getNumOperands(); i; --i) {
    MachineOperand &MO = FoldMI->getOperand(i - 1);
    if (!MO.isReg() || !MO.isImplicit())
      break;
    if (MO.getReg() == ImpReg)
      FoldMI->RemoveOperand(i - 1);
  }

LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MIS.end(), LIS,do { } while (false)
                                              "folded"))do { } while (false);

if (!WasCopy)
  ++NumFolded;
else if (Ops.front().second == 0) {
  ++NumSpills;
  // If there is only 1 store instruction is required for spill, add it
  // to mergeable list. In X86 AMX, 2 intructions are required to store.
  // We disable the merge for this case.
  if (std::distance(MIS.begin(), MIS.end()) <= 1)
    HSpiller.addToMergeableSpills(*FoldMI, StackSlot, Original);
} else
  ++NumReloads;
return true;
965}

967void InlineSpiller::insertReload(Register NewVReg,
                               SlotIndex Idx,
                               MachineBasicBlock::iterator MI) {
MachineBasicBlock &MBB = *MI->getParent();

MachineInstrSpan MIS(MI, &MBB);
TII.loadRegFromStackSlot(MBB, MI, NewVReg, StackSlot,
                         MRI.getRegClass(NewVReg), &TRI);

LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MI);

LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MI, LIS, "reload",do { } while (false)
                                              NewVReg))do { } while (false);
++NumReloads;
981}

983/// Check if \p Def fully defines a VReg with an undefined value.
984/// If that's the case, that means the value of VReg is actually
985/// not relevant.
986static bool isRealSpill(const MachineInstr &Def) {
if (!Def.isImplicitDef())
  return true;
assert(Def.getNumOperands() == 1 &&((void)0)
       "Implicit def with more than one definition")((void)0);
// We can say that the VReg defined by Def is undef, only if it is
// fully defined by Def. Otherwise, some of the lanes may not be
// undef and the value of the VReg matters.
return Def.getOperand(0).getSubReg();
995}

997/// insertSpill - Insert a spill of NewVReg after MI.
998void InlineSpiller::insertSpill(Register NewVReg, bool isKill,
                               MachineBasicBlock::iterator MI) {
// Spill are not terminators, so inserting spills after terminators will
// violate invariants in MachineVerifier.
assert(!MI->isTerminator() && "Inserting a spill after a terminator")((void)0);
MachineBasicBlock &MBB = *MI->getParent();

MachineInstrSpan MIS(MI, &MBB);
MachineBasicBlock::iterator SpillBefore = std::next(MI);
bool IsRealSpill = isRealSpill(*MI);

if (IsRealSpill)
  TII.storeRegToStackSlot(MBB, SpillBefore, NewVReg, isKill, StackSlot,
                          MRI.getRegClass(NewVReg), &TRI);
else
  // Don't spill undef value.
  // Anything works for undef, in particular keeping the memory
  // uninitialized is a viable option and it saves code size and
  // run time.
  BuildMI(MBB, SpillBefore, MI->getDebugLoc(), TII.get(TargetOpcode::KILL))
      .addReg(NewVReg, getKillRegState(isKill));

MachineBasicBlock::iterator Spill = std::next(MI);
LIS.InsertMachineInstrRangeInMaps(Spill, MIS.end());
for (const MachineInstr &MI : make_range(Spill, MIS.end()))
  getVDefInterval(MI, LIS);

LLVM_DEBUG(do { } while (false)
    dumpMachineInstrRangeWithSlotIndex(Spill, MIS.end(), LIS, "spill"))do { } while (false);
++NumSpills;
// If there is only 1 store instruction is required for spill, add it
// to mergeable list. In X86 AMX, 2 intructions are required to store.
// We disable the merge for this case.
if (IsRealSpill && std::distance(Spill, MIS.end()) <= 1)
  HSpiller.addToMergeableSpills(*Spill, StackSlot, Original);
1033}

1035/// spillAroundUses - insert spill code around each use of Reg.
1036void InlineSpiller::spillAroundUses(Register Reg) {
LLVM_DEBUG(dbgs() << "spillAroundUses " << printReg(Reg) << '\n')do { } while (false);
LiveInterval &OldLI = LIS.getInterval(Reg);

// Iterate over instructions using Reg.
for (MachineRegisterInfo::reg_bundle_iterator
     RegI = MRI.reg_bundle_begin(Reg), E = MRI.reg_bundle_end();
     RegI != E; ) {
  MachineInstr *MI = &*(RegI++);

  // Debug values are not allowed to affect codegen.
  if (MI->isDebugValue()) {
    // Modify DBG_VALUE now that the value is in a spill slot.
    MachineBasicBlock *MBB = MI->getParent();
    LLVM_DEBUG(dbgs() << "Modifying debug info due to spill:\t" << *MI)do { } while (false);
    buildDbgValueForSpill(*MBB, MI, *MI, StackSlot, Reg);
    MBB->erase(MI);
    continue;
  }

  assert(!MI->isDebugInstr() && "Did not expect to find a use in debug "((void)0)
         "instruction that isn't a DBG_VALUE")((void)0);

  // Ignore copies to/from snippets. We'll delete them.
  if (SnippetCopies.count(MI))
    continue;

  // Stack slot accesses may coalesce away.
  if (coalesceStackAccess(MI, Reg))
    continue;

  // Analyze instruction.
  SmallVector<std::pair<MachineInstr*, unsigned>, 8> Ops;
  VirtRegInfo RI = AnalyzeVirtRegInBundle(*MI, Reg, &Ops);

  // Find the slot index where this instruction reads and writes OldLI.
  // This is usually the def slot, except for tied early clobbers.
  SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();
  if (VNInfo *VNI = OldLI.getVNInfoAt(Idx.getRegSlot(true)))
    if (SlotIndex::isSameInstr(Idx, VNI->def))
      Idx = VNI->def;

  // Check for a sibling copy.
  Register SibReg = isFullCopyOf(*MI, Reg);
  if (SibReg && isSibling(SibReg)) {
    // This may actually be a copy between snippets.
    if (isRegToSpill(SibReg)) {
      LLVM_DEBUG(dbgs() << "Found new snippet copy: " << *MI)do { } while (false);
      SnippetCopies.insert(MI);
      continue;
    }
    if (RI.Writes) {
      if (hoistSpillInsideBB(OldLI, *MI)) {
        // This COPY is now dead, the value is already in the stack slot.
        MI->getOperand(0).setIsDead();
        DeadDefs.push_back(MI);
        continue;
      }
    } else {
      // This is a reload for a sib-reg copy. Drop spills downstream.
      LiveInterval &SibLI = LIS.getInterval(SibReg);
      eliminateRedundantSpills(SibLI, SibLI.getVNInfoAt(Idx));
      // The COPY will fold to a reload below.
    }
  }

  // Attempt to fold memory ops.
  if (foldMemoryOperand(Ops))
    continue;

  // Create a new virtual register for spill/fill.
  // FIXME: Infer regclass from instruction alone.
  Register NewVReg = Edit->createFrom(Reg);

  if (RI.Reads)
    insertReload(NewVReg, Idx, MI);

  // Rewrite instruction operands.
  bool hasLiveDef = false;
  for (const auto &OpPair : Ops) {
    MachineOperand &MO = OpPair.first->getOperand(OpPair.second);
    MO.setReg(NewVReg);
    if (MO.isUse()) {
      if (!OpPair.first->isRegTiedToDefOperand(OpPair.second))
        MO.setIsKill();
    } else {
      if (!MO.isDead())
        hasLiveDef = true;
    }
  }
  LLVM_DEBUG(dbgs() << "\trewrite: " << Idx << '\t' << *MI << '\n')do { } while (false);

  // FIXME: Use a second vreg if instruction has no tied ops.
  if (RI.Writes)
    if (hasLiveDef)
      insertSpill(NewVReg, true, MI);
}
1133}

1135/// spillAll - Spill all registers remaining after rematerialization.
1136void InlineSpiller::spillAll() {
// Update LiveStacks now that we are committed to spilling.
if (StackSlot == VirtRegMap::NO_STACK_SLOT) {
  StackSlot = VRM.assignVirt2StackSlot(Original);
  StackInt = &LSS.getOrCreateInterval(StackSlot, MRI.getRegClass(Original));
  StackInt->getNextValue(SlotIndex(), LSS.getVNInfoAllocator());
} else
  StackInt = &LSS.getInterval(StackSlot);

if (Original != Edit->getReg())
  VRM.assignVirt2StackSlot(Edit->getReg(), StackSlot);

assert(StackInt->getNumValNums() == 1 && "Bad stack interval values")((void)0);
for (Register Reg : RegsToSpill)
  StackInt->MergeSegmentsInAsValue(LIS.getInterval(Reg),
                                   StackInt->getValNumInfo(0));
LLVM_DEBUG(dbgs() << "Merged spilled regs: " << *StackInt << '\n')do { } while (false);

// Spill around uses of all RegsToSpill.
for (Register Reg : RegsToSpill)
  spillAroundUses(Reg);

// Hoisted spills may cause dead code.
if (!DeadDefs.empty()) {
  LLVM_DEBUG(dbgs() << "Eliminating " << DeadDefs.size() << " dead defs\n")do { } while (false);
  Edit->eliminateDeadDefs(DeadDefs, RegsToSpill, AA);
}

// Finally delete the SnippetCopies.
for (Register Reg : RegsToSpill) {
  for (MachineRegisterInfo::reg_instr_iterator
       RI = MRI.reg_instr_begin(Reg), E = MRI.reg_instr_end();
       RI != E; ) {
    MachineInstr &MI = *(RI++);
    assert(SnippetCopies.count(&MI) && "Remaining use wasn't a snippet copy")((void)0);
    // FIXME: Do this with a LiveRangeEdit callback.
    LIS.RemoveMachineInstrFromMaps(MI);
    MI.eraseFromParent();
  }
}

// Delete all spilled registers.
for (Register Reg : RegsToSpill)
  Edit->eraseVirtReg(Reg);
1180}

1182void InlineSpiller::spill(LiveRangeEdit &edit) {
++NumSpilledRanges;
Edit = &edit;
assert(!Register::isStackSlot(edit.getReg()) &&((void)0)
       "Trying to spill a stack slot.")((void)0);
// Share a stack slot among all descendants of Original.
Original = VRM.getOriginal(edit.getReg());
StackSlot = VRM.getStackSlot(Original);
StackInt = nullptr;

LLVM_DEBUG(dbgs() << "Inline spilling "do { } while (false)
                  << TRI.getRegClassName(MRI.getRegClass(edit.getReg()))do { } while (false)
                  << ':' << edit.getParent() << "\nFrom original "do { } while (false)
                  << printReg(Original) << '\n')do { } while (false);
assert(edit.getParent().isSpillable() &&((void)0)
       "Attempting to spill already spilled value.")((void)0);
assert(DeadDefs.empty() && "Previous spill didn't remove dead defs")((void)0);

collectRegsToSpill();
reMaterializeAll();

// Remat may handle everything.
if (!RegsToSpill.empty())
  spillAll();

Edit->calculateRegClassAndHint(MF, VRAI);
1208}

1210/// Optimizations after all the reg selections and spills are done.
1211void InlineSpiller::postOptimization() { HSpiller.hoistAllSpills(); }
1
Calling 'HoistSpillHelper::hoistAllSpills'→

1213/// When a spill is inserted, add the spill to MergeableSpills map.
1214void HoistSpillHelper::addToMergeableSpills(MachineInstr &Spill, int StackSlot,
                                          unsigned Original) {
BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
LiveInterval &OrigLI = LIS.getInterval(Original);
// save a copy of LiveInterval in StackSlotToOrigLI because the original
// LiveInterval may be cleared after all its references are spilled.
if (StackSlotToOrigLI.find(StackSlot) == StackSlotToOrigLI.end()) {
  auto LI = std::make_unique<LiveInterval>(OrigLI.reg(), OrigLI.weight());
  LI->assign(OrigLI, Allocator);
  StackSlotToOrigLI[StackSlot] = std::move(LI);
}
SlotIndex Idx = LIS.getInstructionIndex(Spill);
VNInfo *OrigVNI = StackSlotToOrigLI[StackSlot]->getVNInfoAt(Idx.getRegSlot());
std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);
MergeableSpills[MIdx].insert(&Spill);
1229}

1231/// When a spill is removed, remove the spill from MergeableSpills map.
1232/// Return true if the spill is removed successfully.
1233bool HoistSpillHelper::rmFromMergeableSpills(MachineInstr &Spill,
                                           int StackSlot) {
auto It = StackSlotToOrigLI.find(StackSlot);
if (It == StackSlotToOrigLI.end())
  return false;
SlotIndex Idx = LIS.getInstructionIndex(Spill);
VNInfo *OrigVNI = It->second->getVNInfoAt(Idx.getRegSlot());
std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);
return MergeableSpills[MIdx].erase(&Spill);
1242}

1244/// Check BB to see if it is a possible target BB to place a hoisted spill,
1245/// i.e., there should be a living sibling of OrigReg at the insert point.
1246bool HoistSpillHelper::isSpillCandBB(LiveInterval &OrigLI, VNInfo &OrigVNI,
                                   MachineBasicBlock &BB, Register &LiveReg) {
SlotIndex Idx = IPA.getLastInsertPoint(OrigLI, BB);
// The original def could be after the last insert point in the root block,
// we can't hoist to here.
if (Idx < OrigVNI.def) {
  // TODO: We could be better here. If LI is not alive in landing pad
  // we could hoist spill after LIP.
  LLVM_DEBUG(dbgs() << "can't spill in root block - def after LIP\n")do { } while (false);
  return false;
}
Register OrigReg = OrigLI.reg();
SmallSetVector<Register, 16> &Siblings = Virt2SiblingsMap[OrigReg];
assert(OrigLI.getVNInfoAt(Idx) == &OrigVNI && "Unexpected VNI")((void)0);

for (const Register &SibReg : Siblings) {
  LiveInterval &LI = LIS.getInterval(SibReg);
  VNInfo *VNI = LI.getVNInfoAt(Idx);
  if (VNI) {
    LiveReg = SibReg;
    return true;
  }
}
return false;
1270}

1272/// Remove redundant spills in the same BB. Save those redundant spills in
1273/// SpillsToRm, and save the spill to keep and its BB in SpillBBToSpill map.
1274void HoistSpillHelper::rmRedundantSpills(
  SmallPtrSet<MachineInstr *, 16> &Spills,
  SmallVectorImpl<MachineInstr *> &SpillsToRm,
  DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill) {
// For each spill saw, check SpillBBToSpill[] and see if its BB already has
// another spill inside. If a BB contains more than one spill, only keep the
// earlier spill with smaller SlotIndex.
for (const auto CurrentSpill : Spills) {
  MachineBasicBlock *Block = CurrentSpill->getParent();
  MachineDomTreeNode *Node = MDT.getBase().getNode(Block);
  MachineInstr *PrevSpill = SpillBBToSpill[Node];
  if (PrevSpill) {
    SlotIndex PIdx = LIS.getInstructionIndex(*PrevSpill);
    SlotIndex CIdx = LIS.getInstructionIndex(*CurrentSpill);
    MachineInstr *SpillToRm = (CIdx > PIdx) ? CurrentSpill : PrevSpill;
    MachineInstr *SpillToKeep = (CIdx > PIdx) ? PrevSpill : CurrentSpill;
    SpillsToRm.push_back(SpillToRm);
    SpillBBToSpill[MDT.getBase().getNode(Block)] = SpillToKeep;
  } else {
    SpillBBToSpill[MDT.getBase().getNode(Block)] = CurrentSpill;
  }
}
for (const auto SpillToRm : SpillsToRm)
  Spills.erase(SpillToRm);
1298}

1300/// Starting from \p Root find a top-down traversal order of the dominator
1301/// tree to visit all basic blocks containing the elements of \p Spills.
1302/// Redundant spills will be found and put into \p SpillsToRm at the same
1303/// time. \p SpillBBToSpill will be populated as part of the process and
1304/// maps a basic block to the first store occurring in the basic block.
1305/// \post SpillsToRm.union(Spills\@post) == Spills\@pre
1306void HoistSpillHelper::getVisitOrders(
  MachineBasicBlock *Root, SmallPtrSet<MachineInstr *, 16> &Spills,
  SmallVectorImpl<MachineDomTreeNode *> &Orders,
  SmallVectorImpl<MachineInstr *> &SpillsToRm,
  DenseMap<MachineDomTreeNode *, unsigned> &SpillsToKeep,
  DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill) {
// The set contains all the possible BB nodes to which we may hoist
// original spills.
SmallPtrSet<MachineDomTreeNode *, 8> WorkSet;
// Save the BB nodes on the path from the first BB node containing
// non-redundant spill to the Root node.
SmallPtrSet<MachineDomTreeNode *, 8> NodesOnPath;
// All the spills to be hoisted must originate from a single def instruction
// to the OrigReg. It means the def instruction should dominate all the spills
// to be hoisted. We choose the BB where the def instruction is located as
// the Root.
MachineDomTreeNode *RootIDomNode = MDT[Root]->getIDom();
// For every node on the dominator tree with spill, walk up on the dominator
// tree towards the Root node until it is reached. If there is other node
// containing spill in the middle of the path, the previous spill saw will
// be redundant and the node containing it will be removed. All the nodes on
// the path starting from the first node with non-redundant spill to the Root
// node will be added to the WorkSet, which will contain all the possible
// locations where spills may be hoisted to after the loop below is done.
for (const auto Spill : Spills) {
  MachineBasicBlock *Block = Spill->getParent();
  MachineDomTreeNode *Node = MDT[Block];
8
←
Calling 'MachineDominatorTree::operator[]'→
21
←
Returning from 'MachineDominatorTree::operator[]'→
22
←
'Node' initialized here→
  MachineInstr *SpillToRm = nullptr;
  while (Node != RootIDomNode) {
23
←
Assuming 'Node' is not equal to 'RootIDomNode'→
24
←
Loop condition is true.  Entering loop body→
    // If Node dominates Block, and it already contains a spill, the spill in
    // Block will be redundant.
    if (Node != MDT[Block] && SpillBBToSpill[Node]) {
25
←
Assuming the condition is false→
26
←
Assuming pointer value is null→
      SpillToRm = SpillBBToSpill[MDT[Block]];
      break;
      /// If we see the Node already in WorkSet, the path from the Node to
      /// the Root node must already be traversed by another spill.
      /// Then no need to repeat.
    } else if (WorkSet.count(Node)) {
27
←
Assuming the condition is false→
28
←
Taking false branch→
      break;
    } else {
      NodesOnPath.insert(Node);
    }
    Node = Node->getIDom();
29
←
Called C++ object pointer is null
  }
  if (SpillToRm) {
    SpillsToRm.push_back(SpillToRm);
  } else {
    // Add a BB containing the original spills to SpillsToKeep -- i.e.,
    // set the initial status before hoisting start. The value of BBs
    // containing original spills is set to 0, in order to descriminate
    // with BBs containing hoisted spills which will be inserted to
    // SpillsToKeep later during hoisting.
    SpillsToKeep[MDT[Block]] = 0;
    WorkSet.insert(NodesOnPath.begin(), NodesOnPath.end());
  }
  NodesOnPath.clear();
}

// Sort the nodes in WorkSet in top-down order and save the nodes
// in Orders. Orders will be used for hoisting in runHoistSpills.
unsigned idx = 0;
Orders.push_back(MDT.getBase().getNode(Root));
do {
  MachineDomTreeNode *Node = Orders[idx++];
  for (MachineDomTreeNode *Child : Node->children()) {
    if (WorkSet.count(Child))
      Orders.push_back(Child);
  }
} while (idx != Orders.size());
assert(Orders.size() == WorkSet.size() &&((void)0)
       "Orders have different size with WorkSet")((void)0);

1378#ifndef NDEBUG1
LLVM_DEBUG(dbgs() << "Orders size is " << Orders.size() << "\n")do { } while (false);
SmallVector<MachineDomTreeNode *, 32>::reverse_iterator RIt = Orders.rbegin();
for (; RIt != Orders.rend(); RIt++)
  LLVM_DEBUG(dbgs() << "BB" << (*RIt)->getBlock()->getNumber() << ",")do { } while (false);
LLVM_DEBUG(dbgs() << "\n")do { } while (false);
1384#endif
1385}

1387/// Try to hoist spills according to BB hotness. The spills to removed will
1388/// be saved in \p SpillsToRm. The spills to be inserted will be saved in
1389/// \p SpillsToIns.
1390void HoistSpillHelper::runHoistSpills(
  LiveInterval &OrigLI, VNInfo &OrigVNI,
  SmallPtrSet<MachineInstr *, 16> &Spills,
  SmallVectorImpl<MachineInstr *> &SpillsToRm,
  DenseMap<MachineBasicBlock *, unsigned> &SpillsToIns) {
// Visit order of dominator tree nodes.
SmallVector<MachineDomTreeNode *, 32> Orders;
// SpillsToKeep contains all the nodes where spills are to be inserted
// during hoisting. If the spill to be inserted is an original spill
// (not a hoisted one), the value of the map entry is 0. If the spill
// is a hoisted spill, the value of the map entry is the VReg to be used
// as the source of the spill.
DenseMap<MachineDomTreeNode *, unsigned> SpillsToKeep;
// Map from BB to the first spill inside of it.
DenseMap<MachineDomTreeNode *, MachineInstr *> SpillBBToSpill;

rmRedundantSpills(Spills, SpillsToRm, SpillBBToSpill);

MachineBasicBlock *Root = LIS.getMBBFromIndex(OrigVNI.def);
getVisitOrders(Root, Spills, Orders, SpillsToRm, SpillsToKeep,
7
←
Calling 'HoistSpillHelper::getVisitOrders'→
               SpillBBToSpill);

// SpillsInSubTreeMap keeps the map from a dom tree node to a pair of
// nodes set and the cost of all the spills inside those nodes.
// The nodes set are the locations where spills are to be inserted
// in the subtree of current node.
using NodesCostPair =
    std::pair<SmallPtrSet<MachineDomTreeNode *, 16>, BlockFrequency>;
DenseMap<MachineDomTreeNode *, NodesCostPair> SpillsInSubTreeMap;

// Iterate Orders set in reverse order, which will be a bottom-up order
// in the dominator tree. Once we visit a dom tree node, we know its
// children have already been visited and the spill locations in the
// subtrees of all the children have been determined.
SmallVector<MachineDomTreeNode *, 32>::reverse_iterator RIt = Orders.rbegin();
for (; RIt != Orders.rend(); RIt++) {
  MachineBasicBlock *Block = (*RIt)->getBlock();

  // If Block contains an original spill, simply continue.
  if (SpillsToKeep.find(*RIt) != SpillsToKeep.end() && !SpillsToKeep[*RIt]) {
    SpillsInSubTreeMap[*RIt].first.insert(*RIt);
    // SpillsInSubTreeMap[*RIt].second contains the cost of spill.
    SpillsInSubTreeMap[*RIt].second = MBFI.getBlockFreq(Block);
    continue;
  }

  // Collect spills in subtree of current node (*RIt) to
  // SpillsInSubTreeMap[*RIt].first.
  for (MachineDomTreeNode *Child : (*RIt)->children()) {
    if (SpillsInSubTreeMap.find(Child) == SpillsInSubTreeMap.end())
      continue;
    // The stmt "SpillsInSubTree = SpillsInSubTreeMap[*RIt].first" below
    // should be placed before getting the begin and end iterators of
    // SpillsInSubTreeMap[Child].first, or else the iterators may be
    // invalidated when SpillsInSubTreeMap[*RIt] is seen the first time
    // and the map grows and then the original buckets in the map are moved.
    SmallPtrSet<MachineDomTreeNode *, 16> &SpillsInSubTree =
        SpillsInSubTreeMap[*RIt].first;
    BlockFrequency &SubTreeCost = SpillsInSubTreeMap[*RIt].second;
    SubTreeCost += SpillsInSubTreeMap[Child].second;
    auto BI = SpillsInSubTreeMap[Child].first.begin();
    auto EI = SpillsInSubTreeMap[Child].first.end();
    SpillsInSubTree.insert(BI, EI);
    SpillsInSubTreeMap.erase(Child);
  }

  SmallPtrSet<MachineDomTreeNode *, 16> &SpillsInSubTree =
        SpillsInSubTreeMap[*RIt].first;
  BlockFrequency &SubTreeCost = SpillsInSubTreeMap[*RIt].second;
  // No spills in subtree, simply continue.
  if (SpillsInSubTree.empty())
    continue;

  // Check whether Block is a possible candidate to insert spill.
  Register LiveReg;
  if (!isSpillCandBB(OrigLI, OrigVNI, *Block, LiveReg))
    continue;

  // If there are multiple spills that could be merged, bias a little
  // to hoist the spill.
  BranchProbability MarginProb = (SpillsInSubTree.size() > 1)
                                     ? BranchProbability(9, 10)
                                     : BranchProbability(1, 1);
  if (SubTreeCost > MBFI.getBlockFreq(Block) * MarginProb) {
    // Hoist: Move spills to current Block.
    for (const auto SpillBB : SpillsInSubTree) {
      // When SpillBB is a BB contains original spill, insert the spill
      // to SpillsToRm.
      if (SpillsToKeep.find(SpillBB) != SpillsToKeep.end() &&
          !SpillsToKeep[SpillBB]) {
        MachineInstr *SpillToRm = SpillBBToSpill[SpillBB];
        SpillsToRm.push_back(SpillToRm);
      }
      // SpillBB will not contain spill anymore, remove it from SpillsToKeep.
      SpillsToKeep.erase(SpillBB);
    }
    // Current Block is the BB containing the new hoisted spill. Add it to
    // SpillsToKeep. LiveReg is the source of the new spill.
    SpillsToKeep[*RIt] = LiveReg;
    LLVM_DEBUG({do { } while (false)
      dbgs() << "spills in BB: ";do { } while (false)
      for (const auto Rspill : SpillsInSubTree)do { } while (false)
        dbgs() << Rspill->getBlock()->getNumber() << " ";do { } while (false)
      dbgs() << "were promoted to BB" << (*RIt)->getBlock()->getNumber()do { } while (false)
             << "\n";do { } while (false)
    })do { } while (false);
    SpillsInSubTree.clear();
    SpillsInSubTree.insert(*RIt);
    SubTreeCost = MBFI.getBlockFreq(Block);
  }
}
// For spills in SpillsToKeep with LiveReg set (i.e., not original spill),
// save them to SpillsToIns.
for (const auto &Ent : SpillsToKeep) {
  if (Ent.second)
    SpillsToIns[Ent.first->getBlock()] = Ent.second;
}
1507}

1509/// For spills with equal values, remove redundant spills and hoist those left
1510/// to less hot spots.
1511///
1512/// Spills with equal values will be collected into the same set in
1513/// MergeableSpills when spill is inserted. These equal spills are originated
1514/// from the same defining instruction and are dominated by the instruction.
1515/// Before hoisting all the equal spills, redundant spills inside in the same
1516/// BB are first marked to be deleted. Then starting from the spills left, walk
1517/// up on the dominator tree towards the Root node where the define instruction
1518/// is located, mark the dominated spills to be deleted along the way and
1519/// collect the BB nodes on the path from non-dominated spills to the define
1520/// instruction into a WorkSet. The nodes in WorkSet are the candidate places
1521/// where we are considering to hoist the spills. We iterate the WorkSet in
1522/// bottom-up order, and for each node, we will decide whether to hoist spills
1523/// inside its subtree to that node. In this way, we can get benefit locally
1524/// even if hoisting all the equal spills to one cold place is impossible.
1525void HoistSpillHelper::hoistAllSpills() {
SmallVector<Register, 4> NewVRegs;
LiveRangeEdit Edit(nullptr, NewVRegs, MF, LIS, &VRM, this);

for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
2
←
Assuming 'i' is equal to 'e'→
3
←
Loop condition is false. Execution continues on line 1537→
  Register Reg = Register::index2VirtReg(i);
  Register Original = VRM.getPreSplitReg(Reg);
  if (!MRI.def_empty(Reg))
    Virt2SiblingsMap[Original].insert(Reg);
}

// Each entry in MergeableSpills contains a spill set with equal values.
for (auto &Ent : MergeableSpills) {
  int Slot = Ent.first.first;
  LiveInterval &OrigLI = *StackSlotToOrigLI[Slot];
  VNInfo *OrigVNI = Ent.first.second;
  SmallPtrSet<MachineInstr *, 16> &EqValSpills = Ent.second;
  if (Ent.second.empty())
4
←
Taking false branch→
    continue;

  LLVM_DEBUG({do { } while (false)
5
←
Loop condition is false.  Exiting loop→
    dbgs() << "\nFor Slot" << Slot << " and VN" << OrigVNI->id << ":\n"do { } while (false)
           << "Equal spills in BB: ";do { } while (false)
    for (const auto spill : EqValSpills)do { } while (false)
      dbgs() << spill->getParent()->getNumber() << " ";do { } while (false)
    dbgs() << "\n";do { } while (false)
  })do { } while (false);

  // SpillsToRm is the spill set to be removed from EqValSpills.
  SmallVector<MachineInstr *, 16> SpillsToRm;
  // SpillsToIns is the spill set to be newly inserted after hoisting.
  DenseMap<MachineBasicBlock *, unsigned> SpillsToIns;

  runHoistSpills(OrigLI, *OrigVNI, EqValSpills, SpillsToRm, SpillsToIns);
6
←
Calling 'HoistSpillHelper::runHoistSpills'→

  LLVM_DEBUG({do { } while (false)
    dbgs() << "Finally inserted spills in BB: ";do { } while (false)
    for (const auto &Ispill : SpillsToIns)do { } while (false)
      dbgs() << Ispill.first->getNumber() << " ";do { } while (false)
    dbgs() << "\nFinally removed spills in BB: ";do { } while (false)
    for (const auto Rspill : SpillsToRm)do { } while (false)
      dbgs() << Rspill->getParent()->getNumber() << " ";do { } while (false)
    dbgs() << "\n";do { } while (false)
  })do { } while (false);

  // Stack live range update.
  LiveInterval &StackIntvl = LSS.getInterval(Slot);
  if (!SpillsToIns.empty() || !SpillsToRm.empty())
    StackIntvl.MergeValueInAsValue(OrigLI, OrigVNI,
                                   StackIntvl.getValNumInfo(0));

  // Insert hoisted spills.
  for (auto const &Insert : SpillsToIns) {
    MachineBasicBlock *BB = Insert.first;
    Register LiveReg = Insert.second;
    MachineBasicBlock::iterator MII = IPA.getLastInsertPointIter(OrigLI, *BB);
    MachineInstrSpan MIS(MII, BB);
    TII.storeRegToStackSlot(*BB, MII, LiveReg, false, Slot,
                            MRI.getRegClass(LiveReg), &TRI);
    LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MII);
    for (const MachineInstr &MI : make_range(MIS.begin(), MII))
      getVDefInterval(MI, LIS);
    ++NumSpills;
  }

  // Remove redundant spills or change them to dead instructions.
  NumSpills -= SpillsToRm.size();
  for (auto const RMEnt : SpillsToRm) {
    RMEnt->setDesc(TII.get(TargetOpcode::KILL));
    for (unsigned i = RMEnt->getNumOperands(); i; --i) {
      MachineOperand &MO = RMEnt->getOperand(i - 1);
      if (MO.isReg() && MO.isImplicit() && MO.isDef() && !MO.isDead())
        RMEnt->RemoveOperand(i - 1);
    }
  }
  Edit.eliminateDeadDefs(SpillsToRm, None, AA);
}
1602}

1604/// For VirtReg clone, the \p New register should have the same physreg or
1605/// stackslot as the \p old register.
1606void HoistSpillHelper::LRE_DidCloneVirtReg(Register New, Register Old) {
if (VRM.hasPhys(Old))
  VRM.assignVirt2Phys(New, VRM.getPhys(Old));
else if (VRM.getStackSlot(Old) != VirtRegMap::NO_STACK_SLOT)
  VRM.assignVirt2StackSlot(New, VRM.getStackSlot(Old));
else
  llvm_unreachable("VReg should be assigned either physreg or stackslot")__builtin_unreachable();
if (VRM.hasShape(Old))
  VRM.assignVirt2Shape(New, VRM.getShape(Old));
1615}

←

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/CodeGen/MachineDominators.h

→

1//==- llvm/CodeGen/MachineDominators.h - Machine Dom Calculation -*- 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 classes mirroring those in llvm/Analysis/Dominators.h,
10// but for target-specific code rather than target-independent IR.
11//
12//===----------------------------------------------------------------------===//

14#ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H
15#define LLVM_CODEGEN_MACHINEDOMINATORS_H

17#include "llvm/ADT/SmallSet.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/CodeGen/MachineBasicBlock.h"
20#include "llvm/CodeGen/MachineFunctionPass.h"
21#include "llvm/CodeGen/MachineInstr.h"
22#include "llvm/Support/GenericDomTree.h"
23#include "llvm/Support/GenericDomTreeConstruction.h"
24#include <cassert>
25#include <memory>

27namespace llvm {

29template <>
30inline void DominatorTreeBase<MachineBasicBlock, false>::addRoot(
  MachineBasicBlock *MBB) {
this->Roots.push_back(MBB);
33}

35extern template class DomTreeNodeBase<MachineBasicBlock>;
36extern template class DominatorTreeBase<MachineBasicBlock, false>; // DomTree
37extern template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTree

39using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>;

41//===-------------------------------------
42/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
43/// compute a normal dominator tree.
44///
45class MachineDominatorTree : public MachineFunctionPass {
using DomTreeT = DomTreeBase<MachineBasicBlock>;

/// Helper structure used to hold all the basic blocks
/// involved in the split of a critical edge.
struct CriticalEdge {
  MachineBasicBlock *FromBB;
  MachineBasicBlock *ToBB;
  MachineBasicBlock *NewBB;
};

/// Pile up all the critical edges to be split.
/// The splitting of a critical edge is local and thus, it is possible
/// to apply several of those changes at the same time.
mutable SmallVector<CriticalEdge, 32> CriticalEdgesToSplit;

/// Remember all the basic blocks that are inserted during
/// edge splitting.
/// Invariant: NewBBs == all the basic blocks contained in the NewBB
/// field of all the elements of CriticalEdgesToSplit.
/// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs
/// such as BB == elt.NewBB.
mutable SmallSet<MachineBasicBlock *, 32> NewBBs;

/// The DominatorTreeBase that is used to compute a normal dominator tree.
std::unique_ptr<DomTreeT> DT;

/// Apply all the recorded critical edges to the DT.
/// This updates the underlying DT information in a way that uses
/// the fast query path of DT as much as possible.
///
/// \post CriticalEdgesToSplit.empty().
void applySplitCriticalEdges() const;

79public:
static char ID; // Pass ID, replacement for typeid

MachineDominatorTree();
explicit MachineDominatorTree(MachineFunction &MF) : MachineFunctionPass(ID) {
  calculate(MF);
}

DomTreeT &getBase() {
  if (!DT) DT.reset(new DomTreeT());
  applySplitCriticalEdges();
  return *DT;
}

void getAnalysisUsage(AnalysisUsage &AU) const override;

MachineBasicBlock *getRoot() const {
  applySplitCriticalEdges();
  return DT->getRoot();
}

MachineDomTreeNode *getRootNode() const {
  applySplitCriticalEdges();
  return DT->getRootNode();
}

bool runOnMachineFunction(MachineFunction &F) override;

void calculate(MachineFunction &F);

bool dominates(const MachineDomTreeNode *A,
               const MachineDomTreeNode *B) const {
  applySplitCriticalEdges();
  return DT->dominates(A, B);
}

bool dominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const {
  applySplitCriticalEdges();
  return DT->dominates(A, B);
}

// dominates - Return true if A dominates B. This performs the
// special checks necessary if A and B are in the same basic block.
bool dominates(const MachineInstr *A, const MachineInstr *B) const {
  applySplitCriticalEdges();
  const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent();
  if (BBA != BBB) return DT->dominates(BBA, BBB);

  // Loop through the basic block until we find A or B.
  MachineBasicBlock::const_iterator I = BBA->begin();
  for (; &*I != A && &*I != B; ++I)
    /*empty*/ ;

  return &*I == A;
}

bool properlyDominates(const MachineDomTreeNode *A,
                       const MachineDomTreeNode *B) const {
  applySplitCriticalEdges();
  return DT->properlyDominates(A, B);
}

bool properlyDominates(const MachineBasicBlock *A,
                       const MachineBasicBlock *B) const {
  applySplitCriticalEdges();
  return DT->properlyDominates(A, B);
}

/// findNearestCommonDominator - Find nearest common dominator basic block
/// for basic block A and B. If there is no such block then return NULL.
MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A,
                                              MachineBasicBlock *B) {
  applySplitCriticalEdges();
  return DT->findNearestCommonDominator(A, B);
}

MachineDomTreeNode *operator[](MachineBasicBlock *BB) const {
  applySplitCriticalEdges();
  return DT->getNode(BB);
9
←
Calling 'DominatorTreeBase::getNode'→
19
←
Returning from 'DominatorTreeBase::getNode'→
20
←
Returning pointer→
}

/// getNode - return the (Post)DominatorTree node for the specified basic
/// block.  This is the same as using operator[] on this class.
///
MachineDomTreeNode *getNode(MachineBasicBlock *BB) const {
  applySplitCriticalEdges();
  return DT->getNode(BB);
}

/// addNewBlock - Add a new node to the dominator tree information.  This
/// creates a new node as a child of DomBB dominator node,linking it into
/// the children list of the immediate dominator.
MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB,
                                MachineBasicBlock *DomBB) {
  applySplitCriticalEdges();
  return DT->addNewBlock(BB, DomBB);
}

/// changeImmediateDominator - This method is used to update the dominator
/// tree information when a node's immediate dominator changes.
///
void changeImmediateDominator(MachineBasicBlock *N,
                              MachineBasicBlock *NewIDom) {
  applySplitCriticalEdges();
  DT->changeImmediateDominator(N, NewIDom);
}

void changeImmediateDominator(MachineDomTreeNode *N,
                              MachineDomTreeNode *NewIDom) {
  applySplitCriticalEdges();
  DT->changeImmediateDominator(N, NewIDom);
}

/// eraseNode - Removes a node from  the dominator tree. Block must not
/// dominate any other blocks. Removes node from its immediate dominator's
/// children list. Deletes dominator node associated with basic block BB.
void eraseNode(MachineBasicBlock *BB) {
  applySplitCriticalEdges();
  DT->eraseNode(BB);
}

/// splitBlock - BB is split and now it has one successor. Update dominator
/// tree to reflect this change.
void splitBlock(MachineBasicBlock* NewBB) {
  applySplitCriticalEdges();
  DT->splitBlock(NewBB);
}

/// isReachableFromEntry - Return true if A is dominated by the entry
/// block of the function containing it.
bool isReachableFromEntry(const MachineBasicBlock *A) {
  applySplitCriticalEdges();
  return DT->isReachableFromEntry(A);
}

void releaseMemory() override;

void verifyAnalysis() const override;

void print(raw_ostream &OS, const Module*) const override;

/// Record that the critical edge (FromBB, ToBB) has been
/// split with NewBB.
/// This is best to use this method instead of directly update the
/// underlying information, because this helps mitigating the
/// number of time the DT information is invalidated.
///
/// \note Do not use this method with regular edges.
///
/// \note To benefit from the compile time improvement incurred by this
/// method, the users of this method have to limit the queries to the DT
/// interface between two edges splitting. In other words, they have to
/// pack the splitting of critical edges as much as possible.
void recordSplitCriticalEdge(MachineBasicBlock *FromBB,
                            MachineBasicBlock *ToBB,
                            MachineBasicBlock *NewBB) {
  bool Inserted = NewBBs.insert(NewBB).second;
  (void)Inserted;
  assert(Inserted &&((void)0)
         "A basic block inserted via edge splitting cannot appear twice")((void)0);
  CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB});
}
241};

243//===-------------------------------------
244/// DominatorTree GraphTraits specialization so the DominatorTree can be
245/// iterable by generic graph iterators.
246///

248template <class Node, class ChildIterator>
249struct MachineDomTreeGraphTraitsBase {
using NodeRef = Node *;
using ChildIteratorType = ChildIterator;

static NodeRef getEntryNode(NodeRef N) { return N; }
static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
static ChildIteratorType child_end(NodeRef N) { return N->end(); }
256};

258template <class T> struct GraphTraits;

260template <>
261struct GraphTraits<MachineDomTreeNode *>
  : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode,
                                         MachineDomTreeNode::const_iterator> {
264};

266template <>
267struct GraphTraits<const MachineDomTreeNode *>
  : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode,
                                         MachineDomTreeNode::const_iterator> {
270};

272template <> struct GraphTraits<MachineDominatorTree*>
: public GraphTraits<MachineDomTreeNode *> {
static NodeRef getEntryNode(MachineDominatorTree *DT) {
  return DT->getRootNode();
}
277};

279} // end namespace llvm

281#endif // LLVM_CODEGEN_MACHINEDOMINATORS_H

←

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support/GenericDomTree.h

→

1//===- GenericDomTree.h - Generic dominator trees for graphs ----*- 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/// \file
9///
10/// This file defines a set of templates that efficiently compute a dominator
11/// tree over a generic graph. This is used typically in LLVM for fast
12/// dominance queries on the CFG, but is fully generic w.r.t. the underlying
13/// graph types.
14///
15/// Unlike ADT/* graph algorithms, generic dominator tree has more requirements
16/// on the graph's NodeRef. The NodeRef should be a pointer and,
17/// NodeRef->getParent() must return the parent node that is also a pointer.
18///
19/// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits.
20///
21//===----------------------------------------------------------------------===//

23#ifndef LLVM_SUPPORT_GENERICDOMTREE_H
24#define LLVM_SUPPORT_GENERICDOMTREE_H

26#include "llvm/ADT/DenseMap.h"
27#include "llvm/ADT/GraphTraits.h"
28#include "llvm/ADT/STLExtras.h"
29#include "llvm/ADT/SmallPtrSet.h"
30#include "llvm/ADT/SmallVector.h"
31#include "llvm/Support/CFGDiff.h"
32#include "llvm/Support/CFGUpdate.h"
33#include "llvm/Support/raw_ostream.h"
34#include <algorithm>
35#include <cassert>
36#include <cstddef>
37#include <iterator>
38#include <memory>
39#include <type_traits>
40#include <utility>

42namespace llvm {

44template <typename NodeT, bool IsPostDom>
45class DominatorTreeBase;

47namespace DomTreeBuilder {
48template <typename DomTreeT>
49struct SemiNCAInfo;
50}  // namespace DomTreeBuilder

52/// Base class for the actual dominator tree node.
53template <class NodeT> class DomTreeNodeBase {
friend class PostDominatorTree;
friend class DominatorTreeBase<NodeT, false>;
friend class DominatorTreeBase<NodeT, true>;
friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, false>>;
friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, true>>;

NodeT *TheBB;
DomTreeNodeBase *IDom;
unsigned Level;
SmallVector<DomTreeNodeBase *, 4> Children;
mutable unsigned DFSNumIn = ~0;
mutable unsigned DFSNumOut = ~0;

public:
DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
    : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}

using iterator = typename SmallVector<DomTreeNodeBase *, 4>::iterator;
using const_iterator =
    typename SmallVector<DomTreeNodeBase *, 4>::const_iterator;

iterator begin() { return Children.begin(); }
iterator end() { return Children.end(); }
const_iterator begin() const { return Children.begin(); }
const_iterator end() const { return Children.end(); }

DomTreeNodeBase *const &back() const { return Children.back(); }
DomTreeNodeBase *&back() { return Children.back(); }

iterator_range<iterator> children() { return make_range(begin(), end()); }
iterator_range<const_iterator> children() const {
  return make_range(begin(), end());
}

NodeT *getBlock() const { return TheBB; }
DomTreeNodeBase *getIDom() const { return IDom; }
unsigned getLevel() const { return Level; }

std::unique_ptr<DomTreeNodeBase> addChild(
    std::unique_ptr<DomTreeNodeBase> C) {
  Children.push_back(C.get());
  return C;
}

bool isLeaf() const { return Children.empty(); }
size_t getNumChildren() const { return Children.size(); }

void clearAllChildren() { Children.clear(); }

bool compare(const DomTreeNodeBase *Other) const {
  if (getNumChildren() != Other->getNumChildren())
    return true;

  if (Level != Other->Level) return true;

  SmallPtrSet<const NodeT *, 4> OtherChildren;
  for (const DomTreeNodeBase *I : *Other) {
    const NodeT *Nd = I->getBlock();
    OtherChildren.insert(Nd);
  }

  for (const DomTreeNodeBase *I : *this) {
    const NodeT *N = I->getBlock();
    if (OtherChildren.count(N) == 0)
      return true;
  }
  return false;
}

void setIDom(DomTreeNodeBase *NewIDom) {
  assert(IDom && "No immediate dominator?")((void)0);
  if (IDom == NewIDom) return;

  auto I = find(IDom->Children, this);
  assert(I != IDom->Children.end() &&((void)0)
         "Not in immediate dominator children set!")((void)0);
  // I am no longer your child...
  IDom->Children.erase(I);

  // Switch to new dominator
  IDom = NewIDom;
  IDom->Children.push_back(this);

  UpdateLevel();
}

/// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes
/// in the dominator tree. They are only guaranteed valid if
/// updateDFSNumbers() has been called.
unsigned getDFSNumIn() const { return DFSNumIn; }
unsigned getDFSNumOut() const { return DFSNumOut; }

146private:
// Return true if this node is dominated by other. Use this only if DFS info
// is valid.
bool DominatedBy(const DomTreeNodeBase *other) const {
  return this->DFSNumIn >= other->DFSNumIn &&
         this->DFSNumOut <= other->DFSNumOut;
}

void UpdateLevel() {
  assert(IDom)((void)0);
  if (Level == IDom->Level + 1) return;

  SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};

  while (!WorkStack.empty()) {
    DomTreeNodeBase *Current = WorkStack.pop_back_val();
    Current->Level = Current->IDom->Level + 1;

    for (DomTreeNodeBase *C : *Current) {
      assert(C->IDom)((void)0);
      if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
    }
  }
}
170};

172template <class NodeT>
173raw_ostream &operator<<(raw_ostream &O, const DomTreeNodeBase<NodeT> *Node) {
if (Node->getBlock())
  Node->getBlock()->printAsOperand(O, false);
else
  O << " <<exit node>>";

O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["
  << Node->getLevel() << "]\n";

return O;
183}

185template <class NodeT>
186void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O,
                unsigned Lev) {
O.indent(2 * Lev) << "[" << Lev << "] " << N;
for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
                                                     E = N->end();
     I != E; ++I)
  PrintDomTree<NodeT>(*I, O, Lev + 1);
193}

195namespace DomTreeBuilder {
196// The routines below are provided in a separate header but referenced here.
197template <typename DomTreeT>
198void Calculate(DomTreeT &DT);

200template <typename DomTreeT>
201void CalculateWithUpdates(DomTreeT &DT,
                        ArrayRef<typename DomTreeT::UpdateType> Updates);

204template <typename DomTreeT>
205void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
              typename DomTreeT::NodePtr To);

208template <typename DomTreeT>
209void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
              typename DomTreeT::NodePtr To);

212template <typename DomTreeT>
213void ApplyUpdates(DomTreeT &DT,
                GraphDiff<typename DomTreeT::NodePtr,
                          DomTreeT::IsPostDominator> &PreViewCFG,
                GraphDiff<typename DomTreeT::NodePtr,
                          DomTreeT::IsPostDominator> *PostViewCFG);

219template <typename DomTreeT>
220bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
221}  // namespace DomTreeBuilder

223/// Core dominator tree base class.
224///
225/// This class is a generic template over graph nodes. It is instantiated for
226/// various graphs in the LLVM IR or in the code generator.
227template <typename NodeT, bool IsPostDom>
228class DominatorTreeBase {
public:
static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value,
              "Currently DominatorTreeBase supports only pointer nodes");
using NodeType = NodeT;
using NodePtr = NodeT *;
using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
static_assert(std::is_pointer<ParentPtr>::value,
              "Currently NodeT's parent must be a pointer type");
using ParentType = std::remove_pointer_t<ParentPtr>;
static constexpr bool IsPostDominator = IsPostDom;

using UpdateType = cfg::Update<NodePtr>;
using UpdateKind = cfg::UpdateKind;
static constexpr UpdateKind Insert = UpdateKind::Insert;
static constexpr UpdateKind Delete = UpdateKind::Delete;

enum class VerificationLevel { Fast, Basic, Full };

247protected:
// Dominators always have a single root, postdominators can have more.
SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots;

using DomTreeNodeMapType =
   DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
DomTreeNodeMapType DomTreeNodes;
DomTreeNodeBase<NodeT> *RootNode = nullptr;
ParentPtr Parent = nullptr;

mutable bool DFSInfoValid = false;
mutable unsigned int SlowQueries = 0;

friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>;

public:
DominatorTreeBase() {}

DominatorTreeBase(DominatorTreeBase &&Arg)
    : Roots(std::move(Arg.Roots)),
      DomTreeNodes(std::move(Arg.DomTreeNodes)),
      RootNode(Arg.RootNode),
      Parent(Arg.Parent),
      DFSInfoValid(Arg.DFSInfoValid),
      SlowQueries(Arg.SlowQueries) {
  Arg.wipe();
}

DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
  Roots = std::move(RHS.Roots);
  DomTreeNodes = std::move(RHS.DomTreeNodes);
  RootNode = RHS.RootNode;
  Parent = RHS.Parent;
  DFSInfoValid = RHS.DFSInfoValid;
  SlowQueries = RHS.SlowQueries;
  RHS.wipe();
  return *this;
}

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

/// Iteration over roots.
///
/// This may include multiple blocks if we are computing post dominators.
/// For forward dominators, this will always be a single block (the entry
/// block).
using root_iterator = typename SmallVectorImpl<NodeT *>::iterator;
using const_root_iterator = typename SmallVectorImpl<NodeT *>::const_iterator;

root_iterator root_begin() { return Roots.begin(); }
const_root_iterator root_begin() const { return Roots.begin(); }
root_iterator root_end() { return Roots.end(); }
const_root_iterator root_end() const { return Roots.end(); }

size_t root_size() const { return Roots.size(); }

iterator_range<root_iterator> roots() {
  return make_range(root_begin(), root_end());
}
iterator_range<const_root_iterator> roots() const {
  return make_range(root_begin(), root_end());
}

/// isPostDominator - Returns true if analysis based of postdoms
///
bool isPostDominator() const { return IsPostDominator; }

/// compare - Return false if the other dominator tree base matches this
/// dominator tree base. Otherwise return true.
bool compare(const DominatorTreeBase &Other) const {
  if (Parent != Other.Parent) return true;

  if (Roots.size() != Other.Roots.size())
    return true;

  if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))
    return true;

  const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
  if (DomTreeNodes.size() != OtherDomTreeNodes.size())
    return true;

  for (const auto &DomTreeNode : DomTreeNodes) {
    NodeT *BB = DomTreeNode.first;
    typename DomTreeNodeMapType::const_iterator OI =
        OtherDomTreeNodes.find(BB);
    if (OI == OtherDomTreeNodes.end())
      return true;

    DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
    DomTreeNodeBase<NodeT> &OtherNd = *OI->second;

    if (MyNd.compare(&OtherNd))
      return true;
  }

  return false;
}

/// getNode - return the (Post)DominatorTree node for the specified basic
/// block.  This is the same as using operator[] on this class.  The result
/// may (but is not required to) be null for a forward (backwards)
/// statically unreachable block.
DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
  auto I = DomTreeNodes.find(BB);
  if (I != DomTreeNodes.end())
10
←
Calling 'operator!='→
16
←
Returning from 'operator!='→
17
←
Taking true branch→
    return I->second.get();
18
←
Returning pointer→
  return nullptr;
}

/// See getNode.
DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const {
  return getNode(BB);
}

/// getRootNode - This returns the entry node for the CFG of the function.  If
/// this tree represents the post-dominance relations for a function, however,
/// this root may be a node with the block == NULL.  This is the case when
/// there are multiple exit nodes from a particular function.  Consumers of
/// post-dominance information must be capable of dealing with this
/// possibility.
///
DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }

/// Get all nodes dominated by R, including R itself.
void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
  Result.clear();
  const DomTreeNodeBase<NodeT> *RN = getNode(R);
  if (!RN)
    return; // If R is unreachable, it will not be present in the DOM tree.
  SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;
  WL.push_back(RN);

  while (!WL.empty()) {
    const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
    Result.push_back(N->getBlock());
    WL.append(N->begin(), N->end());
  }
}

/// properlyDominates - Returns true iff A dominates B and A != B.
/// Note that this is not a constant time operation!
///
bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
                       const DomTreeNodeBase<NodeT> *B) const {
  if (!A || !B)
    return false;
  if (A == B)
    return false;
  return dominates(A, B);
}

bool properlyDominates(const NodeT *A, const NodeT *B) const;

/// isReachableFromEntry - Return true if A is dominated by the entry
/// block of the function containing it.
bool isReachableFromEntry(const NodeT *A) const {
  assert(!this->isPostDominator() &&((void)0)
         "This is not implemented for post dominators")((void)0);
  return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
}

bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }

/// dominates - Returns true iff A dominates B.  Note that this is not a
/// constant time operation!
///
bool dominates(const DomTreeNodeBase<NodeT> *A,
               const DomTreeNodeBase<NodeT> *B) const {
  // A node trivially dominates itself.
  if (B == A)
    return true;

  // An unreachable node is dominated by anything.
  if (!isReachableFromEntry(B))
    return true;

  // And dominates nothing.
  if (!isReachableFromEntry(A))
    return false;

  if (B->getIDom() == A) return true;

  if (A->getIDom() == B) return false;

  // A can only dominate B if it is higher in the tree.
  if (A->getLevel() >= B->getLevel()) return false;

  // Compare the result of the tree walk and the dfs numbers, if expensive
  // checks are enabled.
439#ifdef EXPENSIVE_CHECKS
  assert((!DFSInfoValid ||((void)0)
          (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&((void)0)
         "Tree walk disagrees with dfs numbers!")((void)0);
443#endif

  if (DFSInfoValid)
    return B->DominatedBy(A);

  // If we end up with too many slow queries, just update the
  // DFS numbers on the theory that we are going to keep querying.
  SlowQueries++;
  if (SlowQueries > 32) {
    updateDFSNumbers();
    return B->DominatedBy(A);
  }

  return dominatedBySlowTreeWalk(A, B);
}

bool dominates(const NodeT *A, const NodeT *B) const;

NodeT *getRoot() const {
  assert(this->Roots.size() == 1 && "Should always have entry node!")((void)0);
  return this->Roots[0];
}

/// Find nearest common dominator basic block for basic block A and B. A and B
/// must have tree nodes.
NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
  assert(A && B && "Pointers are not valid")((void)0);
  assert(A->getParent() == B->getParent() &&((void)0)
         "Two blocks are not in same function")((void)0);

  // If either A or B is a entry block then it is nearest common dominator
  // (for forward-dominators).
  if (!isPostDominator()) {
    NodeT &Entry = A->getParent()->front();
    if (A == &Entry || B == &Entry)
      return &Entry;
  }

  DomTreeNodeBase<NodeT> *NodeA = getNode(A);
  DomTreeNodeBase<NodeT> *NodeB = getNode(B);
  assert(NodeA && "A must be in the tree")((void)0);
  assert(NodeB && "B must be in the tree")((void)0);

  // Use level information to go up the tree until the levels match. Then
  // continue going up til we arrive at the same node.
  while (NodeA != NodeB) {
    if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);

    NodeA = NodeA->IDom;
  }

  return NodeA->getBlock();
}

const NodeT *findNearestCommonDominator(const NodeT *A,
                                        const NodeT *B) const {
  // Cast away the const qualifiers here. This is ok since
  // const is re-introduced on the return type.
  return findNearestCommonDominator(const_cast<NodeT *>(A),
                                    const_cast<NodeT *>(B));
}

bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
  return isPostDominator() && !A->getBlock();
}

//===--------------------------------------------------------------------===//
// API to update (Post)DominatorTree information based on modifications to
// the CFG...

/// Inform the dominator tree about a sequence of CFG edge insertions and
/// deletions and perform a batch update on the tree.
///
/// This function should be used when there were multiple CFG updates after
/// the last dominator tree update. It takes care of performing the updates
/// in sync with the CFG and optimizes away the redundant operations that
/// cancel each other.
/// The functions expects the sequence of updates to be balanced. Eg.:
///  - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because
///    logically it results in a single insertions.
///  - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make
///    sense to insert the same edge twice.
///
/// What's more, the functions assumes that it's safe to ask every node in the
/// CFG about its children and inverse children. This implies that deletions
/// of CFG edges must not delete the CFG nodes before calling this function.
///
/// The applyUpdates function can reorder the updates and remove redundant
/// ones internally. The batch updater is also able to detect sequences of
/// zero and exactly one update -- it's optimized to do less work in these
/// cases.
///
/// Note that for postdominators it automatically takes care of applying
/// updates on reverse edges internally (so there's no need to swap the
/// From and To pointers when constructing DominatorTree::UpdateType).
/// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
/// with the same template parameter T.
///
/// \param Updates An unordered sequence of updates to perform. The current
/// CFG and the reverse of these updates provides the pre-view of the CFG.
///
void applyUpdates(ArrayRef<UpdateType> Updates) {
  GraphDiff<NodePtr, IsPostDominator> PreViewCFG(
      Updates, /*ReverseApplyUpdates=*/true);
  DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, nullptr);
}

/// \param Updates An unordered sequence of updates to perform. The current
/// CFG and the reverse of these updates provides the pre-view of the CFG.
/// \param PostViewUpdates An unordered sequence of update to perform in order
/// to obtain a post-view of the CFG. The DT will be updated assuming the
/// obtained PostViewCFG is the desired end state.
void applyUpdates(ArrayRef<UpdateType> Updates,
                  ArrayRef<UpdateType> PostViewUpdates) {
  if (Updates.empty()) {
    GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates);
    DomTreeBuilder::ApplyUpdates(*this, PostViewCFG, &PostViewCFG);
  } else {
    // PreViewCFG needs to merge Updates and PostViewCFG. The updates in
    // Updates need to be reversed, and match the direction in PostViewCFG.
    // The PostViewCFG is created with updates reversed (equivalent to changes
    // made to the CFG), so the PreViewCFG needs all the updates reverse
    // applied.
    SmallVector<UpdateType> AllUpdates(Updates.begin(), Updates.end());
    append_range(AllUpdates, PostViewUpdates);
    GraphDiff<NodePtr, IsPostDom> PreViewCFG(AllUpdates,
                                             /*ReverseApplyUpdates=*/true);
    GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates);
    DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, &PostViewCFG);
  }
}

/// Inform the dominator tree about a CFG edge insertion and update the tree.
///
/// This function has to be called just before or just after making the update
/// on the actual CFG. There cannot be any other updates that the dominator
/// tree doesn't know about.
///
/// Note that for postdominators it automatically takes care of inserting
/// a reverse edge internally (so there's no need to swap the parameters).
///
void insertEdge(NodeT *From, NodeT *To) {
  assert(From)((void)0);
  assert(To)((void)0);
  assert(From->getParent() == Parent)((void)0);
  assert(To->getParent() == Parent)((void)0);
  DomTreeBuilder::InsertEdge(*this, From, To);
}

/// Inform the dominator tree about a CFG edge deletion and update the tree.
///
/// This function has to be called just after making the update on the actual
/// CFG. An internal functions checks if the edge doesn't exist in the CFG in
/// DEBUG mode. There cannot be any other updates that the
/// dominator tree doesn't know about.
///
/// Note that for postdominators it automatically takes care of deleting
/// a reverse edge internally (so there's no need to swap the parameters).
///
void deleteEdge(NodeT *From, NodeT *To) {
  assert(From)((void)0);
  assert(To)((void)0);
  assert(From->getParent() == Parent)((void)0);
  assert(To->getParent() == Parent)((void)0);
  DomTreeBuilder::DeleteEdge(*this, From, To);
}

/// Add a new node to the dominator tree information.
///
/// This creates a new node as a child of DomBB dominator node, linking it
/// into the children list of the immediate dominator.
///
/// \param BB New node in CFG.
/// \param DomBB CFG node that is dominator for BB.
/// \returns New dominator tree node that represents new CFG node.
///
DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
  assert(getNode(BB) == nullptr && "Block already in dominator tree!")((void)0);
  DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
  assert(IDomNode && "Not immediate dominator specified for block!")((void)0);
  DFSInfoValid = false;
  return createChild(BB, IDomNode);
}

/// Add a new node to the forward dominator tree and make it a new root.
///
/// \param BB New node in CFG.
/// \returns New dominator tree node that represents new CFG node.
///
DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) {
  assert(getNode(BB) == nullptr && "Block already in dominator tree!")((void)0);
  assert(!this->isPostDominator() &&((void)0)
         "Cannot change root of post-dominator tree")((void)0);
  DFSInfoValid = false;
  DomTreeNodeBase<NodeT> *NewNode = createNode(BB);
  if (Roots.empty()) {
    addRoot(BB);
  } else {
    assert(Roots.size() == 1)((void)0);
    NodeT *OldRoot = Roots.front();
    auto &OldNode = DomTreeNodes[OldRoot];
    OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
    OldNode->IDom = NewNode;
    OldNode->UpdateLevel();
    Roots[0] = BB;
  }
  return RootNode = NewNode;
}

/// changeImmediateDominator - This method is used to update the dominator
/// tree information when a node's immediate dominator changes.
///
void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
                              DomTreeNodeBase<NodeT> *NewIDom) {
  assert(N && NewIDom && "Cannot change null node pointers!")((void)0);
  DFSInfoValid = false;
  N->setIDom(NewIDom);
}

void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
  changeImmediateDominator(getNode(BB), getNode(NewBB));
}

/// eraseNode - Removes a node from the dominator tree. Block must not
/// dominate any other blocks. Removes node from its immediate dominator's
/// children list. Deletes dominator node associated with basic block BB.
void eraseNode(NodeT *BB) {
  DomTreeNodeBase<NodeT> *Node = getNode(BB);
  assert(Node && "Removing node that isn't in dominator tree.")((void)0);
  assert(Node->isLeaf() && "Node is not a leaf node.")((void)0);

  DFSInfoValid = false;

  // Remove node from immediate dominator's children list.
  DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
  if (IDom) {
    const auto I = find(IDom->Children, Node);
    assert(I != IDom->Children.end() &&((void)0)
           "Not in immediate dominator children set!")((void)0);
    // I am no longer your child...
    IDom->Children.erase(I);
  }

  DomTreeNodes.erase(BB);

  if (!IsPostDom) return;

  // Remember to update PostDominatorTree roots.
  auto RIt = llvm::find(Roots, BB);
  if (RIt != Roots.end()) {
    std::swap(*RIt, Roots.back());
    Roots.pop_back();
  }
}

/// splitBlock - BB is split and now it has one successor. Update dominator
/// tree to reflect this change.
void splitBlock(NodeT *NewBB) {
  if (IsPostDominator)
    Split<Inverse<NodeT *>>(NewBB);
  else
    Split<NodeT *>(NewBB);
}

/// print - Convert to human readable form
///
void print(raw_ostream &O) const {
  O << "=============================--------------------------------\n";
  if (IsPostDominator)
    O << "Inorder PostDominator Tree: ";
  else
    O << "Inorder Dominator Tree: ";
  if (!DFSInfoValid)
    O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
  O << "\n";

  // The postdom tree can have a null root if there are no returns.
  if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
  O << "Roots: ";
  for (const NodePtr Block : Roots) {
    Block->printAsOperand(O, false);
    O << " ";
  }
  O << "\n";
}

729public:
/// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
/// dominator tree in dfs order.
void updateDFSNumbers() const {
  if (DFSInfoValid) {
    SlowQueries = 0;
    return;
  }

  SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
                        typename DomTreeNodeBase<NodeT>::const_iterator>,
              32> WorkStack;

  const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
  assert((!Parent || ThisRoot) && "Empty constructed DomTree")((void)0);
  if (!ThisRoot)
    return;

  // Both dominators and postdominators have a single root node. In the case
  // case of PostDominatorTree, this node is a virtual root.
  WorkStack.push_back({ThisRoot, ThisRoot->begin()});

  unsigned DFSNum = 0;
  ThisRoot->DFSNumIn = DFSNum++;

  while (!WorkStack.empty()) {
    const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
    const auto ChildIt = WorkStack.back().second;

    // If we visited all of the children of this node, "recurse" back up the
    // stack setting the DFOutNum.
    if (ChildIt == Node->end()) {
      Node->DFSNumOut = DFSNum++;
      WorkStack.pop_back();
    } else {
      // Otherwise, recursively visit this child.
      const DomTreeNodeBase<NodeT> *Child = *ChildIt;
      ++WorkStack.back().second;

      WorkStack.push_back({Child, Child->begin()});
      Child->DFSNumIn = DFSNum++;
    }
  }

  SlowQueries = 0;
  DFSInfoValid = true;
}

/// recalculate - compute a dominator tree for the given function
void recalculate(ParentType &Func) {
  Parent = &Func;
  DomTreeBuilder::Calculate(*this);
}

void recalculate(ParentType &Func, ArrayRef<UpdateType> Updates) {
  Parent = &Func;
  DomTreeBuilder::CalculateWithUpdates(*this, Updates);
}

/// verify - checks if the tree is correct. There are 3 level of verification:
///  - Full --  verifies if the tree is correct by making sure all the
///             properties (including the parent and the sibling property)
///             hold.
///             Takes O(N^3) time.
///
///  - Basic -- checks if the tree is correct, but compares it to a freshly
///             constructed tree instead of checking the sibling property.
///             Takes O(N^2) time.
///
///  - Fast  -- checks basic tree structure and compares it with a freshly
///             constructed tree.
///             Takes O(N^2) time worst case, but is faster in practise (same
///             as tree construction).
bool verify(VerificationLevel VL = VerificationLevel::Full) const {
  return DomTreeBuilder::Verify(*this, VL);
}

void reset() {
  DomTreeNodes.clear();
  Roots.clear();
  RootNode = nullptr;
  Parent = nullptr;
  DFSInfoValid = false;
  SlowQueries = 0;
}

815protected:
void addRoot(NodeT *BB) { this->Roots.push_back(BB); }

DomTreeNodeBase<NodeT> *createChild(NodeT *BB, DomTreeNodeBase<NodeT> *IDom) {
  return (DomTreeNodes[BB] = IDom->addChild(
              std::make_unique<DomTreeNodeBase<NodeT>>(BB, IDom)))
      .get();
}

DomTreeNodeBase<NodeT> *createNode(NodeT *BB) {
  return (DomTreeNodes[BB] =
              std::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr))
      .get();
}

// NewBB is split and now it has one successor. Update dominator tree to
// reflect this change.
template <class N>
void Split(typename GraphTraits<N>::NodeRef NewBB) {
  using GraphT = GraphTraits<N>;
  using NodeRef = typename GraphT::NodeRef;
  assert(std::distance(GraphT::child_begin(NewBB),((void)0)
                       GraphT::child_end(NewBB)) == 1 &&((void)0)
         "NewBB should have a single successor!")((void)0);
  NodeRef NewBBSucc = *GraphT::child_begin(NewBB);

  SmallVector<NodeRef, 4> PredBlocks(children<Inverse<N>>(NewBB));

  assert(!PredBlocks.empty() && "No predblocks?")((void)0);

  bool NewBBDominatesNewBBSucc = true;
  for (auto Pred : children<Inverse<N>>(NewBBSucc)) {
    if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
        isReachableFromEntry(Pred)) {
      NewBBDominatesNewBBSucc = false;
      break;
    }
  }

  // Find NewBB's immediate dominator and create new dominator tree node for
  // NewBB.
  NodeT *NewBBIDom = nullptr;
  unsigned i = 0;
  for (i = 0; i < PredBlocks.size(); ++i)
    if (isReachableFromEntry(PredBlocks[i])) {
      NewBBIDom = PredBlocks[i];
      break;
    }

  // It's possible that none of the predecessors of NewBB are reachable;
  // in that case, NewBB itself is unreachable, so nothing needs to be
  // changed.
  if (!NewBBIDom) return;

  for (i = i + 1; i < PredBlocks.size(); ++i) {
    if (isReachableFromEntry(PredBlocks[i]))
      NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
  }

  // Create the new dominator tree node... and set the idom of NewBB.
  DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);

  // If NewBB strictly dominates other blocks, then it is now the immediate
  // dominator of NewBBSucc.  Update the dominator tree as appropriate.
  if (NewBBDominatesNewBBSucc) {
    DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
    changeImmediateDominator(NewBBSuccNode, NewBBNode);
  }
}

private:
bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
                             const DomTreeNodeBase<NodeT> *B) const {
  assert(A != B)((void)0);
  assert(isReachableFromEntry(B))((void)0);
  assert(isReachableFromEntry(A))((void)0);

  const unsigned ALevel = A->getLevel();
  const DomTreeNodeBase<NodeT> *IDom;

  // Don't walk nodes above A's subtree. When we reach A's level, we must
  // either find A or be in some other subtree not dominated by A.
  while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel)
    B = IDom;  // Walk up the tree

  return B == A;
}

/// Wipe this tree's state without releasing any resources.
///
/// This is essentially a post-move helper only. It leaves the object in an
/// assignable and destroyable state, but otherwise invalid.
void wipe() {
  DomTreeNodes.clear();
  RootNode = nullptr;
  Parent = nullptr;
}
912};

914template <typename T>
915using DomTreeBase = DominatorTreeBase<T, false>;

917template <typename T>
918using PostDomTreeBase = DominatorTreeBase<T, true>;

920// These two functions are declared out of line as a workaround for building
921// with old (< r147295) versions of clang because of pr11642.
922template <typename NodeT, bool IsPostDom>
923bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A,
                                                  const NodeT *B) const {
if (A == B)
  return true;

// Cast away the const qualifiers here. This is ok since
// this function doesn't actually return the values returned
// from getNode.
return dominates(getNode(const_cast<NodeT *>(A)),
                 getNode(const_cast<NodeT *>(B)));
933}
934template <typename NodeT, bool IsPostDom>
935bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates(
  const NodeT *A, const NodeT *B) const {
if (A == B)
  return false;

// Cast away the const qualifiers here. This is ok since
// this function doesn't actually return the values returned
// from getNode.
return dominates(getNode(const_cast<NodeT *>(A)),
                 getNode(const_cast<NodeT *>(B)));
945}

947} // end namespace llvm

949#endif // LLVM_SUPPORT_GENERICDOMTREE_H

←

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ADT/DenseMap.h

1//===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- 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 DenseMap class.
10//
11//===----------------------------------------------------------------------===//

13#ifndef LLVM_ADT_DENSEMAP_H
14#define LLVM_ADT_DENSEMAP_H

16#include "llvm/ADT/DenseMapInfo.h"
17#include "llvm/ADT/EpochTracker.h"
18#include "llvm/Support/AlignOf.h"
19#include "llvm/Support/Compiler.h"
20#include "llvm/Support/MathExtras.h"
21#include "llvm/Support/MemAlloc.h"
22#include "llvm/Support/ReverseIteration.h"
23#include "llvm/Support/type_traits.h"
24#include <algorithm>
25#include <cassert>
26#include <cstddef>
27#include <cstring>
28#include <initializer_list>
29#include <iterator>
30#include <new>
31#include <type_traits>
32#include <utility>

34namespace llvm {

36namespace detail {

38// We extend a pair to allow users to override the bucket type with their own
39// implementation without requiring two members.
40template <typename KeyT, typename ValueT>
41struct DenseMapPair : public std::pair<KeyT, ValueT> {
using std::pair<KeyT, ValueT>::pair;

KeyT &getFirst() { return std::pair<KeyT, ValueT>::first; }
const KeyT &getFirst() const { return std::pair<KeyT, ValueT>::first; }
ValueT &getSecond() { return std::pair<KeyT, ValueT>::second; }
const ValueT &getSecond() const { return std::pair<KeyT, ValueT>::second; }
48};

50} // end namespace detail

52template <typename KeyT, typename ValueT,
        typename KeyInfoT = DenseMapInfo<KeyT>,
        typename Bucket = llvm::detail::DenseMapPair<KeyT, ValueT>,
        bool IsConst = false>
56class DenseMapIterator;

58template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
        typename BucketT>
60class DenseMapBase : public DebugEpochBase {
template <typename T>
using const_arg_type_t = typename const_pointer_or_const_ref<T>::type;

64public:
using size_type = unsigned;
using key_type = KeyT;
using mapped_type = ValueT;
using value_type = BucketT;

using iterator = DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT>;
using const_iterator =
    DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT, true>;

inline iterator begin() {
  // When the map is empty, avoid the overhead of advancing/retreating past
  // empty buckets.
  if (empty())
    return end();
  if (shouldReverseIterate<KeyT>())
    return makeIterator(getBucketsEnd() - 1, getBuckets(), *this);
  return makeIterator(getBuckets(), getBucketsEnd(), *this);
}
inline iterator end() {
  return makeIterator(getBucketsEnd(), getBucketsEnd(), *this, true);
}
inline const_iterator begin() const {
  if (empty())
    return end();
  if (shouldReverseIterate<KeyT>())
    return makeConstIterator(getBucketsEnd() - 1, getBuckets(), *this);
  return makeConstIterator(getBuckets(), getBucketsEnd(), *this);
}
inline const_iterator end() const {
  return makeConstIterator(getBucketsEnd(), getBucketsEnd(), *this, true);
}

LLVM_NODISCARD[[clang::warn_unused_result]] bool empty() const {
  return getNumEntries() == 0;
}
unsigned size() const { return getNumEntries(); }

/// Grow the densemap so that it can contain at least \p NumEntries items
/// before resizing again.
void reserve(size_type NumEntries) {
  auto NumBuckets = getMinBucketToReserveForEntries(NumEntries);
  incrementEpoch();
  if (NumBuckets > getNumBuckets())
    grow(NumBuckets);
}

void clear() {
  incrementEpoch();
  if (getNumEntries() == 0 && getNumTombstones() == 0) return;

  // If the capacity of the array is huge, and the # elements used is small,
  // shrink the array.
  if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) {
    shrink_and_clear();
    return;
  }

  const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
  if (std::is_trivially_destructible<ValueT>::value) {
    // Use a simpler loop when values don't need destruction.
    for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P)
      P->getFirst() = EmptyKey;
  } else {
    unsigned NumEntries = getNumEntries();
    for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
      if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) {
        if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
          P->getSecond().~ValueT();
          --NumEntries;
        }
        P->getFirst() = EmptyKey;
      }
    }
    assert(NumEntries == 0 && "Node count imbalance!")((void)0);
  }
  setNumEntries(0);
  setNumTombstones(0);
}

/// Return 1 if the specified key is in the map, 0 otherwise.
size_type count(const_arg_type_t<KeyT> Val) const {
  const BucketT *TheBucket;
  return LookupBucketFor(Val, TheBucket) ? 1 : 0;
}

iterator find(const_arg_type_t<KeyT> Val) {
  BucketT *TheBucket;
  if (LookupBucketFor(Val, TheBucket))
    return makeIterator(TheBucket,
                        shouldReverseIterate<KeyT>() ? getBuckets()
                                                     : getBucketsEnd(),
                        *this, true);
  return end();
}
const_iterator find(const_arg_type_t<KeyT> Val) const {
  const BucketT *TheBucket;
  if (LookupBucketFor(Val, TheBucket))
    return makeConstIterator(TheBucket,
                             shouldReverseIterate<KeyT>() ? getBuckets()
                                                          : getBucketsEnd(),
                             *this, true);
  return end();
}

/// Alternate version of find() which allows a different, and possibly
/// less expensive, key type.
/// The DenseMapInfo is responsible for supplying methods
/// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
/// type used.
template<class LookupKeyT>
iterator find_as(const LookupKeyT &Val) {
  BucketT *TheBucket;
  if (LookupBucketFor(Val, TheBucket))
    return makeIterator(TheBucket,
                        shouldReverseIterate<KeyT>() ? getBuckets()
                                                     : getBucketsEnd(),
                        *this, true);
  return end();
}
template<class LookupKeyT>
const_iterator find_as(const LookupKeyT &Val) const {
  const BucketT *TheBucket;
  if (LookupBucketFor(Val, TheBucket))
    return makeConstIterator(TheBucket,
                             shouldReverseIterate<KeyT>() ? getBuckets()
                                                          : getBucketsEnd(),
                             *this, true);
  return end();
}

/// lookup - Return the entry for the specified key, or a default
/// constructed value if no such entry exists.
ValueT lookup(const_arg_type_t<KeyT> Val) const {
  const BucketT *TheBucket;
  if (LookupBucketFor(Val, TheBucket))
    return TheBucket->getSecond();
  return ValueT();
}

// Inserts key,value pair into the map if the key isn't already in the map.
// If the key is already in the map, it returns false and doesn't update the
// value.
std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
  return try_emplace(KV.first, KV.second);
}

// Inserts key,value pair into the map if the key isn't already in the map.
// If the key is already in the map, it returns false and doesn't update the
// value.
std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
  return try_emplace(std::move(KV.first), std::move(KV.second));
}

// Inserts key,value pair into the map if the key isn't already in the map.
// The value is constructed in-place if the key is not in the map, otherwise
// it is not moved.
template <typename... Ts>
std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&... Args) {
  BucketT *TheBucket;
  if (LookupBucketFor(Key, TheBucket))
    return std::make_pair(makeIterator(TheBucket,
                                       shouldReverseIterate<KeyT>()
                                           ? getBuckets()
                                           : getBucketsEnd(),
                                       *this, true),
                          false); // Already in map.

  // Otherwise, insert the new element.
  TheBucket =
      InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...);
  return std::make_pair(makeIterator(TheBucket,
                                     shouldReverseIterate<KeyT>()
                                         ? getBuckets()
                                         : getBucketsEnd(),
                                     *this, true),
                        true);
}

// Inserts key,value pair into the map if the key isn't already in the map.
// The value is constructed in-place if the key is not in the map, otherwise
// it is not moved.
template <typename... Ts>
std::pair<iterator, bool> try_emplace(const KeyT &Key, Ts &&... Args) {
  BucketT *TheBucket;
  if (LookupBucketFor(Key, TheBucket))
    return std::make_pair(makeIterator(TheBucket,
                                       shouldReverseIterate<KeyT>()
                                           ? getBuckets()
                                           : getBucketsEnd(),
                                       *this, true),
                          false); // Already in map.

  // Otherwise, insert the new element.
  TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...);
  return std::make_pair(makeIterator(TheBucket,
                                     shouldReverseIterate<KeyT>()
                                         ? getBuckets()
                                         : getBucketsEnd(),
                                     *this, true),
                        true);
}

/// Alternate version of insert() which allows a different, and possibly
/// less expensive, key type.
/// The DenseMapInfo is responsible for supplying methods
/// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
/// type used.
template <typename LookupKeyT>
std::pair<iterator, bool> insert_as(std::pair<KeyT, ValueT> &&KV,
                                    const LookupKeyT &Val) {
  BucketT *TheBucket;
  if (LookupBucketFor(Val, TheBucket))
    return std::make_pair(makeIterator(TheBucket,
                                       shouldReverseIterate<KeyT>()
                                           ? getBuckets()
                                           : getBucketsEnd(),
                                       *this, true),
                          false); // Already in map.

  // Otherwise, insert the new element.
  TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first),
                                         std::move(KV.second), Val);
  return std::make_pair(makeIterator(TheBucket,
                                     shouldReverseIterate<KeyT>()
                                         ? getBuckets()
                                         : getBucketsEnd(),
                                     *this, true),
                        true);
}

/// insert - Range insertion of pairs.
template<typename InputIt>
void insert(InputIt I, InputIt E) {
  for (; I != E; ++I)
    insert(*I);
}

bool erase(const KeyT &Val) {
  BucketT *TheBucket;
  if (!LookupBucketFor(Val, TheBucket))
    return false; // not in map.

  TheBucket->getSecond().~ValueT();
  TheBucket->getFirst() = getTombstoneKey();
  decrementNumEntries();
  incrementNumTombstones();
  return true;
}
void erase(iterator I) {
  BucketT *TheBucket = &*I;
  TheBucket->getSecond().~ValueT();
  TheBucket->getFirst() = getTombstoneKey();
  decrementNumEntries();
  incrementNumTombstones();
}

value_type& FindAndConstruct(const KeyT &Key) {
  BucketT *TheBucket;
  if (LookupBucketFor(Key, TheBucket))
    return *TheBucket;

  return *InsertIntoBucket(TheBucket, Key);
}

ValueT &operator[](const KeyT &Key) {
  return FindAndConstruct(Key).second;
}

value_type& FindAndConstruct(KeyT &&Key) {
  BucketT *TheBucket;
  if (LookupBucketFor(Key, TheBucket))
    return *TheBucket;

  return *InsertIntoBucket(TheBucket, std::move(Key));
}

ValueT &operator[](KeyT &&Key) {
  return FindAndConstruct(std::move(Key)).second;
}

/// isPointerIntoBucketsArray - Return true if the specified pointer points
/// somewhere into the DenseMap's array of buckets (i.e. either to a key or
/// value in the DenseMap).
bool isPointerIntoBucketsArray(const void *Ptr) const {
  return Ptr >= getBuckets() && Ptr < getBucketsEnd();
}

/// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
/// array.  In conjunction with the previous method, this can be used to
/// determine whether an insertion caused the DenseMap to reallocate.
const void *getPointerIntoBucketsArray() const { return getBuckets(); }

357protected:
DenseMapBase() = default;

void destroyAll() {
  if (getNumBuckets() == 0) // Nothing to do.
    return;

  const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
  for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
    if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
        !KeyInfoT::isEqual(P->getFirst(), TombstoneKey))
      P->getSecond().~ValueT();
    P->getFirst().~KeyT();
  }
}

void initEmpty() {
  setNumEntries(0);
  setNumTombstones(0);

  assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&((void)0)
         "# initial buckets must be a power of two!")((void)0);
  const KeyT EmptyKey = getEmptyKey();
  for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B)
    ::new (&B->getFirst()) KeyT(EmptyKey);
}

/// Returns the number of buckets to allocate to ensure that the DenseMap can
/// accommodate \p NumEntries without need to grow().
unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
  // Ensure that "NumEntries * 4 < NumBuckets * 3"
  if (NumEntries == 0)
    return 0;
  // +1 is required because of the strict equality.
  // For example if NumEntries is 48, we need to return 401.
  return NextPowerOf2(NumEntries * 4 / 3 + 1);
}

void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) {
  initEmpty();

  // Insert all the old elements.
  const KeyT EmptyKey = getEmptyKey();
  const KeyT TombstoneKey = getTombstoneKey();
  for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) {
    if (!KeyInfoT::isEqual(B->getFirst(), EmptyKey) &&
        !KeyInfoT::isEqual(B->getFirst(), TombstoneKey)) {
      // Insert the key/value into the new table.
      BucketT *DestBucket;
      bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket);
      (void)FoundVal; // silence warning.
      assert(!FoundVal && "Key already in new map?")((void)0);
      DestBucket->getFirst() = std::move(B->getFirst());
      ::new (&DestBucket->getSecond()) ValueT(std::move(B->getSecond()));
      incrementNumEntries();

      // Free the value.
      B->getSecond().~ValueT();
    }
    B->getFirst().~KeyT();
  }
}

template <typename OtherBaseT>
void copyFrom(
    const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT, BucketT> &other) {
  assert(&other != this)((void)0);
  assert(getNumBuckets() == other.getNumBuckets())((void)0);

  setNumEntries(other.getNumEntries());
  setNumTombstones(other.getNumTombstones());

  if (std::is_trivially_copyable<KeyT>::value &&
      std::is_trivially_copyable<ValueT>::value)
    memcpy(reinterpret_cast<void *>(getBuckets()), other.getBuckets(),
           getNumBuckets() * sizeof(BucketT));
  else
    for (size_t i = 0; i < getNumBuckets(); ++i) {
      ::new (&getBuckets()[i].getFirst())
          KeyT(other.getBuckets()[i].getFirst());
      if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) &&
          !KeyInfoT::isEqual(getBuckets()[i].getFirst(), getTombstoneKey()))
        ::new (&getBuckets()[i].getSecond())
            ValueT(other.getBuckets()[i].getSecond());
    }
}

static unsigned getHashValue(const KeyT &Val) {
  return KeyInfoT::getHashValue(Val);
}

template<typename LookupKeyT>
static unsigned getHashValue(const LookupKeyT &Val) {
  return KeyInfoT::getHashValue(Val);
}

static const KeyT getEmptyKey() {
  static_assert(std::is_base_of<DenseMapBase, DerivedT>::value,
                "Must pass the derived type to this template!");
  return KeyInfoT::getEmptyKey();
}

static const KeyT getTombstoneKey() {
  return KeyInfoT::getTombstoneKey();
}

463private:
iterator makeIterator(BucketT *P, BucketT *E,
                      DebugEpochBase &Epoch,
                      bool NoAdvance=false) {
  if (shouldReverseIterate<KeyT>()) {
    BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1;
    return iterator(B, E, Epoch, NoAdvance);
  }
  return iterator(P, E, Epoch, NoAdvance);
}

const_iterator makeConstIterator(const BucketT *P, const BucketT *E,
                                 const DebugEpochBase &Epoch,
                                 const bool NoAdvance=false) const {
  if (shouldReverseIterate<KeyT>()) {
    const BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1;
    return const_iterator(B, E, Epoch, NoAdvance);
  }
  return const_iterator(P, E, Epoch, NoAdvance);
}

unsigned getNumEntries() const {
  return static_cast<const DerivedT *>(this)->getNumEntries();
}

void setNumEntries(unsigned Num) {
  static_cast<DerivedT *>(this)->setNumEntries(Num);
}

void incrementNumEntries() {
  setNumEntries(getNumEntries() + 1);
}

void decrementNumEntries() {
  setNumEntries(getNumEntries() - 1);
}

unsigned getNumTombstones() const {
  return static_cast<const DerivedT *>(this)->getNumTombstones();
}

void setNumTombstones(unsigned Num) {
  static_cast<DerivedT *>(this)->setNumTombstones(Num);
}

void incrementNumTombstones() {
  setNumTombstones(getNumTombstones() + 1);
}

void decrementNumTombstones() {
  setNumTombstones(getNumTombstones() - 1);
}

const BucketT *getBuckets() const {
  return static_cast<const DerivedT *>(this)->getBuckets();
}

BucketT *getBuckets() {
  return static_cast<DerivedT *>(this)->getBuckets();
}

unsigned getNumBuckets() const {
  return static_cast<const DerivedT *>(this)->getNumBuckets();
}

BucketT *getBucketsEnd() {
  return getBuckets() + getNumBuckets();
}

const BucketT *getBucketsEnd() const {
  return getBuckets() + getNumBuckets();
}

void grow(unsigned AtLeast) {
  static_cast<DerivedT *>(this)->grow(AtLeast);
}

void shrink_and_clear() {
  static_cast<DerivedT *>(this)->shrink_and_clear();
}

template <typename KeyArg, typename... ValueArgs>
BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key,
                          ValueArgs &&... Values) {
  TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);

  TheBucket->getFirst() = std::forward<KeyArg>(Key);
  ::new (&TheBucket->getSecond()) ValueT(std::forward<ValueArgs>(Values)...);
  return TheBucket;
}

template <typename LookupKeyT>
BucketT *InsertIntoBucketWithLookup(BucketT *TheBucket, KeyT &&Key,
                                    ValueT &&Value, LookupKeyT &Lookup) {
  TheBucket = InsertIntoBucketImpl(Key, Lookup, TheBucket);

  TheBucket->getFirst() = std::move(Key);
  ::new (&TheBucket->getSecond()) ValueT(std::move(Value));
  return TheBucket;
}

template <typename LookupKeyT>
BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup,
                              BucketT *TheBucket) {
  incrementEpoch();

  // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
  // the buckets are empty (meaning that many are filled with tombstones),
  // grow the table.
  //
  // The later case is tricky.  For example, if we had one empty bucket with
  // tons of tombstones, failing lookups (e.g. for insertion) would have to
  // probe almost the entire table until it found the empty bucket.  If the
  // table completely filled with tombstones, no lookup would ever succeed,
  // causing infinite loops in lookup.
  unsigned NewNumEntries = getNumEntries() + 1;
  unsigned NumBuckets = getNumBuckets();
  if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)__builtin_expect((bool)(NewNumEntries * 4 >= NumBuckets * 3
), false)) {
    this->grow(NumBuckets * 2);
    LookupBucketFor(Lookup, TheBucket);
    NumBuckets = getNumBuckets();
  } else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=__builtin_expect((bool)(NumBuckets-(NewNumEntries+getNumTombstones
()) <= NumBuckets/8), false)
                           NumBuckets/8)__builtin_expect((bool)(NumBuckets-(NewNumEntries+getNumTombstones
()) <= NumBuckets/8), false)) {
    this->grow(NumBuckets);
    LookupBucketFor(Lookup, TheBucket);
  }
  assert(TheBucket)((void)0);

  // Only update the state after we've grown our bucket space appropriately
  // so that when growing buckets we have self-consistent entry count.
  incrementNumEntries();

  // If we are writing over a tombstone, remember this.
  const KeyT EmptyKey = getEmptyKey();
  if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey))
    decrementNumTombstones();

  return TheBucket;
}

/// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
/// FoundBucket.  If the bucket contains the key and a value, this returns
/// true, otherwise it returns a bucket with an empty marker or tombstone and
/// returns false.
template<typename LookupKeyT>
bool LookupBucketFor(const LookupKeyT &Val,
                     const BucketT *&FoundBucket) const {
  const BucketT *BucketsPtr = getBuckets();
  const unsigned NumBuckets = getNumBuckets();

  if (NumBuckets == 0) {
    FoundBucket = nullptr;
    return false;
  }

  // FoundTombstone - Keep track of whether we find a tombstone while probing.
  const BucketT *FoundTombstone = nullptr;
  const KeyT EmptyKey = getEmptyKey();
  const KeyT TombstoneKey = getTombstoneKey();
  assert(!KeyInfoT::isEqual(Val, EmptyKey) &&((void)0)
         !KeyInfoT::isEqual(Val, TombstoneKey) &&((void)0)
         "Empty/Tombstone value shouldn't be inserted into map!")((void)0);

  unsigned BucketNo = getHashValue(Val) & (NumBuckets-1);
  unsigned ProbeAmt = 1;
  while (true) {
    const BucketT *ThisBucket = BucketsPtr + BucketNo;
    // Found Val's bucket?  If so, return it.
    if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))__builtin_expect((bool)(KeyInfoT::isEqual(Val, ThisBucket->
getFirst())), true)) {
      FoundBucket = ThisBucket;
      return true;
    }

    // If we found an empty bucket, the key doesn't exist in the set.
    // Insert it and return the default value.
    if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))__builtin_expect((bool)(KeyInfoT::isEqual(ThisBucket->getFirst
(), EmptyKey)), true)) {
      // If we've already seen a tombstone while probing, fill it in instead
      // of the empty bucket we eventually probed to.
      FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
      return false;
    }

    // If this is a tombstone, remember it.  If Val ends up not in the map, we
    // prefer to return it than something that would require more probing.
    if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) &&
        !FoundTombstone)
      FoundTombstone = ThisBucket;  // Remember the first tombstone found.

    // Otherwise, it's a hash collision or a tombstone, continue quadratic
    // probing.
    BucketNo += ProbeAmt++;
    BucketNo &= (NumBuckets-1);
  }
}

template <typename LookupKeyT>
bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) {
  const BucketT *ConstFoundBucket;
  bool Result = const_cast<const DenseMapBase *>(this)
    ->LookupBucketFor(Val, ConstFoundBucket);
  FoundBucket = const_cast<BucketT *>(ConstFoundBucket);
  return Result;
}

667public:
/// Return the approximate size (in bytes) of the actual map.
/// This is just the raw memory used by DenseMap.
/// If entries are pointers to objects, the size of the referenced objects
/// are not included.
size_t getMemorySize() const {
  return getNumBuckets() * sizeof(BucketT);
}
675};

677/// Equality comparison for DenseMap.
678///
679/// Iterates over elements of LHS confirming that each (key, value) pair in LHS
680/// is also in RHS, and that no additional pairs are in RHS.
681/// Equivalent to N calls to RHS.find and N value comparisons. Amortized
682/// complexity is linear, worst case is O(N^2) (if every hash collides).
683template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
        typename BucketT>
685bool operator==(
  const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS,
  const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) {
if (LHS.size() != RHS.size())
  return false;

for (auto &KV : LHS) {
  auto I = RHS.find(KV.first);
  if (I == RHS.end() || I->second != KV.second)
    return false;
}

return true;
698}

700/// Inequality comparison for DenseMap.
701///
702/// Equivalent to !(LHS == RHS). See operator== for performance notes.
703template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
        typename BucketT>
705bool operator!=(
  const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS,
  const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) {
return !(LHS == RHS);
709}

711template <typename KeyT, typename ValueT,
        typename KeyInfoT = DenseMapInfo<KeyT>,
        typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>>
714class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
                                   KeyT, ValueT, KeyInfoT, BucketT> {
friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;

// Lift some types from the dependent base class into this class for
// simplicity of referring to them.
using BaseT = DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;

BucketT *Buckets;
unsigned NumEntries;
unsigned NumTombstones;
unsigned NumBuckets;

727public:
/// Create a DenseMap with an optional \p InitialReserve that guarantee that
/// this number of elements can be inserted in the map without grow()
explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve); }

DenseMap(const DenseMap &other) : BaseT() {
  init(0);
  copyFrom(other);
}

DenseMap(DenseMap &&other) : BaseT() {
  init(0);
  swap(other);
}

template<typename InputIt>
DenseMap(const InputIt &I, const InputIt &E) {
  init(std::distance(I, E));
  this->insert(I, E);
}

DenseMap(std::initializer_list<typename BaseT::value_type> Vals) {
  init(Vals.size());
  this->insert(Vals.begin(), Vals.end());
}

~DenseMap() {
  this->destroyAll();
  deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT));
}

void swap(DenseMap& RHS) {
  this->incrementEpoch();
  RHS.incrementEpoch();
  std::swap(Buckets, RHS.Buckets);
  std::swap(NumEntries, RHS.NumEntries);
  std::swap(NumTombstones, RHS.NumTombstones);
  std::swap(NumBuckets, RHS.NumBuckets);
}

DenseMap& operator=(const DenseMap& other) {
  if (&other != this)
    copyFrom(other);
  return *this;
}

DenseMap& operator=(DenseMap &&other) {
  this->destroyAll();
  deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT));
  init(0);
  swap(other);
  return *this;
}

void copyFrom(const DenseMap& other) {
  this->destroyAll();
  deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT));
  if (allocateBuckets(other.NumBuckets)) {
    this->BaseT::copyFrom(other);
  } else {
    NumEntries = 0;
    NumTombstones = 0;
  }
}

void init(unsigned InitNumEntries) {
  auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries);
  if (allocateBuckets(InitBuckets)) {
    this->BaseT::initEmpty();
  } else {
    NumEntries = 0;
    NumTombstones = 0;
  }
}

void grow(unsigned AtLeast) {
  unsigned OldNumBuckets = NumBuckets;
  BucketT *OldBuckets = Buckets;

  allocateBuckets(std::max<unsigned>(64, static_cast<unsigned>(NextPowerOf2(AtLeast-1))));
  assert(Buckets)((void)0);
  if (!OldBuckets) {
    this->BaseT::initEmpty();
    return;
  }

  this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets);

  // Free the old table.
  deallocate_buffer(OldBuckets, sizeof(BucketT) * OldNumBuckets,
                    alignof(BucketT));
}

void shrink_and_clear() {
  unsigned OldNumBuckets = NumBuckets;
  unsigned OldNumEntries = NumEntries;
  this->destroyAll();

  // Reduce the number of buckets.
  unsigned NewNumBuckets = 0;
  if (OldNumEntries)
    NewNumBuckets = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1));
  if (NewNumBuckets == NumBuckets) {
    this->BaseT::initEmpty();
    return;
  }

  deallocate_buffer(Buckets, sizeof(BucketT) * OldNumBuckets,
                    alignof(BucketT));
  init(NewNumBuckets);
}

839private:
unsigned getNumEntries() const {
  return NumEntries;
}

void setNumEntries(unsigned Num) {
  NumEntries = Num;
}

unsigned getNumTombstones() const {
  return NumTombstones;
}

void setNumTombstones(unsigned Num) {
  NumTombstones = Num;
}

BucketT *getBuckets() const {
  return Buckets;
}

unsigned getNumBuckets() const {
  return NumBuckets;
}

bool allocateBuckets(unsigned Num) {
  NumBuckets = Num;
  if (NumBuckets == 0) {
    Buckets = nullptr;
    return false;
  }

  Buckets = static_cast<BucketT *>(
      allocate_buffer(sizeof(BucketT) * NumBuckets, alignof(BucketT)));
  return true;
}
875};

877template <typename KeyT, typename ValueT, unsigned InlineBuckets = 4,
        typename KeyInfoT = DenseMapInfo<KeyT>,
        typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>>
880class SmallDenseMap
  : public DenseMapBase<
        SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT,
        ValueT, KeyInfoT, BucketT> {
friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>;

// Lift some types from the dependent base class into this class for
// simplicity of referring to them.
using BaseT = DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>;

static_assert(isPowerOf2_64(InlineBuckets),
              "InlineBuckets must be a power of 2.");

unsigned Small : 1;
unsigned NumEntries : 31;
unsigned NumTombstones;

struct LargeRep {
  BucketT *Buckets;
  unsigned NumBuckets;
};

/// A "union" of an inline bucket array and the struct representing
/// a large bucket. This union will be discriminated by the 'Small' bit.
AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage;

906public:
explicit SmallDenseMap(unsigned NumInitBuckets = 0) {
  init(NumInitBuckets);
}

SmallDenseMap(const SmallDenseMap &other) : BaseT() {
  init(0);
  copyFrom(other);
}

SmallDenseMap(SmallDenseMap &&other) : BaseT() {
  init(0);
  swap(other);
}

template<typename InputIt>
SmallDenseMap(const InputIt &I, const InputIt &E) {
  init(NextPowerOf2(std::distance(I, E)));
  this->insert(I, E);
}

SmallDenseMap(std::initializer_list<typename BaseT::value_type> Vals)
    : SmallDenseMap(Vals.begin(), Vals.end()) {}

~SmallDenseMap() {
  this->destroyAll();
  deallocateBuckets();
}

void swap(SmallDenseMap& RHS) {
  unsigned TmpNumEntries = RHS.NumEntries;
  RHS.NumEntries = NumEntries;
  NumEntries = TmpNumEntries;
  std::swap(NumTombstones, RHS.NumTombstones);

  const KeyT EmptyKey = this->getEmptyKey();
  const KeyT TombstoneKey = this->getTombstoneKey();
  if (Small && RHS.Small) {
    // If we're swapping inline bucket arrays, we have to cope with some of
    // the tricky bits of DenseMap's storage system: the buckets are not
    // fully initialized. Thus we swap every key, but we may have
    // a one-directional move of the value.
    for (unsigned i = 0, e = InlineBuckets; i != e; ++i) {
      BucketT *LHSB = &getInlineBuckets()[i],
              *RHSB = &RHS.getInlineBuckets()[i];
      bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->getFirst(), EmptyKey) &&
                          !KeyInfoT::isEqual(LHSB->getFirst(), TombstoneKey));
      bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->getFirst(), EmptyKey) &&
                          !KeyInfoT::isEqual(RHSB->getFirst(), TombstoneKey));
      if (hasLHSValue && hasRHSValue) {
        // Swap together if we can...
        std::swap(*LHSB, *RHSB);
        continue;
      }
      // Swap separately and handle any asymmetry.
      std::swap(LHSB->getFirst(), RHSB->getFirst());
      if (hasLHSValue) {
        ::new (&RHSB->getSecond()) ValueT(std::move(LHSB->getSecond()));
        LHSB->getSecond().~ValueT();
      } else if (hasRHSValue) {
        ::new (&LHSB->getSecond()) ValueT(std::move(RHSB->getSecond()));
        RHSB->getSecond().~ValueT();
      }
    }
    return;
  }
  if (!Small && !RHS.Small) {
    std::swap(getLargeRep()->Buckets, RHS.getLargeRep()->Buckets);
    std::swap(getLargeRep()->NumBuckets, RHS.getLargeRep()->NumBuckets);
    return;
  }

  SmallDenseMap &SmallSide = Small ? *this : RHS;
  SmallDenseMap &LargeSide = Small ? RHS : *this;

  // First stash the large side's rep and move the small side across.
  LargeRep TmpRep = std::move(*LargeSide.getLargeRep());
  LargeSide.getLargeRep()->~LargeRep();
  LargeSide.Small = true;
  // This is similar to the standard move-from-old-buckets, but the bucket
  // count hasn't actually rotated in this case. So we have to carefully
  // move construct the keys and values into their new locations, but there
  // is no need to re-hash things.
  for (unsigned i = 0, e = InlineBuckets; i != e; ++i) {
    BucketT *NewB = &LargeSide.getInlineBuckets()[i],
            *OldB = &SmallSide.getInlineBuckets()[i];
    ::new (&NewB->getFirst()) KeyT(std::move(OldB->getFirst()));
    OldB->getFirst().~KeyT();
    if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) &&
        !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) {
      ::new (&NewB->getSecond()) ValueT(std::move(OldB->getSecond()));
      OldB->getSecond().~ValueT();
    }
  }

  // The hard part of moving the small buckets across is done, just move
  // the TmpRep into its new home.
  SmallSide.Small = false;
  new (SmallSide.getLargeRep()) LargeRep(std::move(TmpRep));
}

SmallDenseMap& operator=(const SmallDenseMap& other) {
  if (&other != this)
    copyFrom(other);
  return *this;
}

SmallDenseMap& operator=(SmallDenseMap &&other) {
  this->destroyAll();
  deallocateBuckets();
  init(0);
  swap(other);
  return *this;
}

void copyFrom(const SmallDenseMap& other) {
  this->destroyAll();
  deallocateBuckets();
  Small = true;
  if (other.getNumBuckets() > InlineBuckets) {
    Small = false;
    new (getLargeRep()) LargeRep(allocateBuckets(other.getNumBuckets()));
  }
  this->BaseT::copyFrom(other);
}

void init(unsigned InitBuckets) {
  Small = true;
  if (InitBuckets > InlineBuckets) {
    Small = false;
    new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets));
  }
  this->BaseT::initEmpty();
}

void grow(unsigned AtLeast) {
  if (AtLeast > InlineBuckets)
    AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast-1));

  if (Small) {
    // First move the inline buckets into a temporary storage.
    AlignedCharArrayUnion<BucketT[InlineBuckets]> TmpStorage;
    BucketT *TmpBegin = reinterpret_cast<BucketT *>(&TmpStorage);
    BucketT *TmpEnd = TmpBegin;

    // Loop over the buckets, moving non-empty, non-tombstones into the
    // temporary storage. Have the loop move the TmpEnd forward as it goes.
    const KeyT EmptyKey = this->getEmptyKey();
    const KeyT TombstoneKey = this->getTombstoneKey();
    for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) {
      if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
          !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
        assert(size_t(TmpEnd - TmpBegin) < InlineBuckets &&((void)0)
               "Too many inline buckets!")((void)0);
        ::new (&TmpEnd->getFirst()) KeyT(std::move(P->getFirst()));
        ::new (&TmpEnd->getSecond()) ValueT(std::move(P->getSecond()));
        ++TmpEnd;
        P->getSecond().~ValueT();
      }
      P->getFirst().~KeyT();
    }

    // AtLeast == InlineBuckets can happen if there are many tombstones,
    // and grow() is used to remove them. Usually we always switch to the
    // large rep here.
    if (AtLeast > InlineBuckets) {
      Small = false;
      new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
    }
    this->moveFromOldBuckets(TmpBegin, TmpEnd);
    return;
  }

  LargeRep OldRep = std::move(*getLargeRep());
  getLargeRep()->~LargeRep();
  if (AtLeast <= InlineBuckets) {
    Small = true;
  } else {
    new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
  }

  this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets);

  // Free the old table.
  deallocate_buffer(OldRep.Buckets, sizeof(BucketT) * OldRep.NumBuckets,
                    alignof(BucketT));
}

void shrink_and_clear() {
  unsigned OldSize = this->size();
  this->destroyAll();

  // Reduce the number of buckets.
  unsigned NewNumBuckets = 0;
  if (OldSize) {
    NewNumBuckets = 1 << (Log2_32_Ceil(OldSize) + 1);
    if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u)
      NewNumBuckets = 64;
  }
  if ((Small && NewNumBuckets <= InlineBuckets) ||
      (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) {
    this->BaseT::initEmpty();
    return;
  }

  deallocateBuckets();
  init(NewNumBuckets);
}

1115private:
unsigned getNumEntries() const {
  return NumEntries;
}

void setNumEntries(unsigned Num) {
  // NumEntries is hardcoded to be 31 bits wide.
  assert(Num < (1U << 31) && "Cannot support more than 1<<31 entries")((void)0);
  NumEntries = Num;
}

unsigned getNumTombstones() const {
  return NumTombstones;
}

void setNumTombstones(unsigned Num) {
  NumTombstones = Num;
}

const BucketT *getInlineBuckets() const {
  assert(Small)((void)0);
  // Note that this cast does not violate aliasing rules as we assert that
  // the memory's dynamic type is the small, inline bucket buffer, and the
  // 'storage' is a POD containing a char buffer.
  return reinterpret_cast<const BucketT *>(&storage);
}

BucketT *getInlineBuckets() {
  return const_cast<BucketT *>(
    const_cast<const SmallDenseMap *>(this)->getInlineBuckets());
}

const LargeRep *getLargeRep() const {
  assert(!Small)((void)0);
  // Note, same rule about aliasing as with getInlineBuckets.
  return reinterpret_cast<const LargeRep *>(&storage);
}

LargeRep *getLargeRep() {
  return const_cast<LargeRep *>(
    const_cast<const SmallDenseMap *>(this)->getLargeRep());
}

const BucketT *getBuckets() const {
  return Small ? getInlineBuckets() : getLargeRep()->Buckets;
}

BucketT *getBuckets() {
  return const_cast<BucketT *>(
    const_cast<const SmallDenseMap *>(this)->getBuckets());
}

unsigned getNumBuckets() const {
  return Small ? InlineBuckets : getLargeRep()->NumBuckets;
}

void deallocateBuckets() {
  if (Small)
    return;

  deallocate_buffer(getLargeRep()->Buckets,
                    sizeof(BucketT) * getLargeRep()->NumBuckets,
                    alignof(BucketT));
  getLargeRep()->~LargeRep();
}

LargeRep allocateBuckets(unsigned Num) {
  assert(Num > InlineBuckets && "Must allocate more buckets than are inline")((void)0);
  LargeRep Rep = {static_cast<BucketT *>(allocate_buffer(
                      sizeof(BucketT) * Num, alignof(BucketT))),
                  Num};
  return Rep;
}
1188};

1190template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket,
        bool IsConst>
1192class DenseMapIterator : DebugEpochBase::HandleBase {
friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>;
friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false>;

1196public:
using difference_type = ptrdiff_t;
using value_type =
    typename std::conditional<IsConst, const Bucket, Bucket>::type;
using pointer = value_type *;
using reference = value_type &;
using iterator_category = std::forward_iterator_tag;

1204private:
pointer Ptr = nullptr;
pointer End = nullptr;

1208public:
DenseMapIterator() = default;

DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch,
                 bool NoAdvance = false)
    : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) {
  assert(isHandleInSync() && "invalid construction!")((void)0);

  if (NoAdvance) return;
  if (shouldReverseIterate<KeyT>()) {
    RetreatPastEmptyBuckets();
    return;
  }
  AdvancePastEmptyBuckets();
}

// Converting ctor from non-const iterators to const iterators. SFINAE'd out
// for const iterator destinations so it doesn't end up as a user defined copy
// constructor.
template <bool IsConstSrc,
          typename = std::enable_if_t<!IsConstSrc && IsConst>>
DenseMapIterator(
    const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc> &I)
    : DebugEpochBase::HandleBase(I), Ptr(I.Ptr), End(I.End) {}

reference operator*() const {
  assert(isHandleInSync() && "invalid iterator access!")((void)0);
  assert(Ptr != End && "dereferencing end() iterator")((void)0);
  if (shouldReverseIterate<KeyT>())
    return Ptr[-1];
  return *Ptr;
}
pointer operator->() const {
  assert(isHandleInSync() && "invalid iterator access!")((void)0);
  assert(Ptr != End && "dereferencing end() iterator")((void)0);
  if (shouldReverseIterate<KeyT>())
    return &(Ptr[-1]);
  return Ptr;
}

friend bool operator==(const DenseMapIterator &LHS,
                       const DenseMapIterator &RHS) {
  assert((!LHS.Ptr || LHS.isHandleInSync()) && "handle not in sync!")((void)0);
  assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!")((void)0);
  assert(LHS.getEpochAddress() == RHS.getEpochAddress() &&((void)0)
         "comparing incomparable iterators!")((void)0);
  return LHS.Ptr == RHS.Ptr;
12
←
Assuming 'LHS.Ptr' is not equal to 'RHS.Ptr'→
13
←
Returning zero, which participates in a condition later→
}

friend bool operator!=(const DenseMapIterator &LHS,
                       const DenseMapIterator &RHS) {
  return !(LHS == RHS);
11
←
Calling 'operator=='→
14
←
Returning from 'operator=='→
15
←
Returning the value 1, which participates in a condition later→
}

inline DenseMapIterator& operator++() {  // Preincrement
  assert(isHandleInSync() && "invalid iterator access!")((void)0);
  assert(Ptr != End && "incrementing end() iterator")((void)0);
  if (shouldReverseIterate<KeyT>()) {
    --Ptr;
    RetreatPastEmptyBuckets();
    return *this;
  }
  ++Ptr;
  AdvancePastEmptyBuckets();
  return *this;
}
DenseMapIterator operator++(int) {  // Postincrement
  assert(isHandleInSync() && "invalid iterator access!")((void)0);
  DenseMapIterator tmp = *this; ++*this; return tmp;
}

1279private:
void AdvancePastEmptyBuckets() {
  assert(Ptr <= End)((void)0);
  const KeyT Empty = KeyInfoT::getEmptyKey();
  const KeyT Tombstone = KeyInfoT::getTombstoneKey();

  while (Ptr != End && (KeyInfoT::isEqual(Ptr->getFirst(), Empty) ||
                        KeyInfoT::isEqual(Ptr->getFirst(), Tombstone)))
    ++Ptr;
}

void RetreatPastEmptyBuckets() {
  assert(Ptr >= End)((void)0);
  const KeyT Empty = KeyInfoT::getEmptyKey();
  const KeyT Tombstone = KeyInfoT::getTombstoneKey();

  while (Ptr != End && (KeyInfoT::isEqual(Ptr[-1].getFirst(), Empty) ||
                        KeyInfoT::isEqual(Ptr[-1].getFirst(), Tombstone)))
    --Ptr;
}
1299};

1301template <typename KeyT, typename ValueT, typename KeyInfoT>
1302inline size_t capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) {
return X.getMemorySize();
1304}

1306} // end namespace llvm

1308#endif // LLVM_ADT_DENSEMAP_H