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

Bug Summary

File:	src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp
Warning:	line 2681, column 5 Use of zero-allocated memory
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 InstrRefBasedImpl.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/LiveDebugValues/InstrRefBasedImpl.cpp
1//===- InstrRefBasedImpl.cpp - Tracking Debug Value MIs -------------------===//
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 InstrRefBasedImpl.cpp
9///
10/// This is a separate implementation of LiveDebugValues, see
11/// LiveDebugValues.cpp and VarLocBasedImpl.cpp for more information.
12///
13/// This pass propagates variable locations between basic blocks, resolving
14/// control flow conflicts between them. The problem is much like SSA
15/// construction, where each DBG_VALUE instruction assigns the *value* that
16/// a variable has, and every instruction where the variable is in scope uses
17/// that variable. The resulting map of instruction-to-value is then translated
18/// into a register (or spill) location for each variable over each instruction.
19///
20/// This pass determines which DBG_VALUE dominates which instructions, or if
21/// none do, where values must be merged (like PHI nodes). The added
22/// complication is that because codegen has already finished, a PHI node may
23/// be needed for a variable location to be correct, but no register or spill
24/// slot merges the necessary values. In these circumstances, the variable
25/// location is dropped.
26///
27/// What makes this analysis non-trivial is loops: we cannot tell in advance
28/// whether a variable location is live throughout a loop, or whether its
29/// location is clobbered (or redefined by another DBG_VALUE), without
30/// exploring all the way through.
31///
32/// To make this simpler we perform two kinds of analysis. First, we identify
33/// every value defined by every instruction (ignoring those that only move
34/// another value), then compute a map of which values are available for each
35/// instruction. This is stronger than a reaching-def analysis, as we create
36/// PHI values where other values merge.
37///
38/// Secondly, for each variable, we effectively re-construct SSA using each
39/// DBG_VALUE as a def. The DBG_VALUEs read a value-number computed by the
40/// first analysis from the location they refer to. We can then compute the
41/// dominance frontiers of where a variable has a value, and create PHI nodes
42/// where they merge.
43/// This isn't precisely SSA-construction though, because the function shape
44/// is pre-defined. If a variable location requires a PHI node, but no
45/// PHI for the relevant values is present in the function (as computed by the
46/// first analysis), the location must be dropped.
47///
48/// Once both are complete, we can pass back over all instructions knowing:
49///  * What _value_ each variable should contain, either defined by an
50///    instruction or where control flow merges
51///  * What the location of that value is (if any).
52/// Allowing us to create appropriate live-in DBG_VALUEs, and DBG_VALUEs when
53/// a value moves location. After this pass runs, all variable locations within
54/// a block should be specified by DBG_VALUEs within that block, allowing
55/// DbgEntityHistoryCalculator to focus on individual blocks.
56///
57/// This pass is able to go fast because the size of the first
58/// reaching-definition analysis is proportional to the working-set size of
59/// the function, which the compiler tries to keep small. (It's also
60/// proportional to the number of blocks). Additionally, we repeatedly perform
61/// the second reaching-definition analysis with only the variables and blocks
62/// in a single lexical scope, exploiting their locality.
63///
64/// Determining where PHIs happen is trickier with this approach, and it comes
65/// to a head in the major problem for LiveDebugValues: is a value live-through
66/// a loop, or not? Your garden-variety dataflow analysis aims to build a set of
67/// facts about a function, however this analysis needs to generate new value
68/// numbers at joins.
69///
70/// To do this, consider a lattice of all definition values, from instructions
71/// and from PHIs. Each PHI is characterised by the RPO number of the block it
72/// occurs in. Each value pair A, B can be ordered by RPO(A) < RPO(B):
73/// with non-PHI values at the top, and any PHI value in the last block (by RPO
74/// order) at the bottom.
75///
76/// (Awkwardly: lower-down-the _lattice_ means a greater RPO _number_. Below,
77/// "rank" always refers to the former).
78///
79/// At any join, for each register, we consider:
80///  * All incoming values, and
81///  * The PREVIOUS live-in value at this join.
82/// If all incoming values agree: that's the live-in value. If they do not, the
83/// incoming values are ranked according to the partial order, and the NEXT
84/// LOWEST rank after the PREVIOUS live-in value is picked (multiple values of
85/// the same rank are ignored as conflicting). If there are no candidate values,
86/// or if the rank of the live-in would be lower than the rank of the current
87/// blocks PHIs, create a new PHI value.
88///
89/// Intuitively: if it's not immediately obvious what value a join should result
90/// in, we iteratively descend from instruction-definitions down through PHI
91/// values, getting closer to the current block each time. If the current block
92/// is a loop head, this ordering is effectively searching outer levels of
93/// loops, to find a value that's live-through the current loop.
94///
95/// If there is no value that's live-through this loop, a PHI is created for
96/// this location instead. We can't use a lower-ranked PHI because by definition
97/// it doesn't dominate the current block. We can't create a PHI value any
98/// earlier, because we risk creating a PHI value at a location where values do
99/// not in fact merge, thus misrepresenting the truth, and not making the true
100/// live-through value for variable locations.
101///
102/// This algorithm applies to both calculating the availability of values in
103/// the first analysis, and the location of variables in the second. However
104/// for the second we add an extra dimension of pain: creating a variable
105/// location PHI is only valid if, for each incoming edge,
106///  * There is a value for the variable on the incoming edge, and
107///  * All the edges have that value in the same register.
108/// Or put another way: we can only create a variable-location PHI if there is
109/// a matching machine-location PHI, each input to which is the variables value
110/// in the predecessor block.
111///
112/// To accommodate this difference, each point on the lattice is split in
113/// two: a "proposed" PHI and "definite" PHI. Any PHI that can immediately
114/// have a location determined are "definite" PHIs, and no further work is
115/// needed. Otherwise, a location that all non-backedge predecessors agree
116/// on is picked and propagated as a "proposed" PHI value. If that PHI value
117/// is truly live-through, it'll appear on the loop backedges on the next
118/// dataflow iteration, after which the block live-in moves to be a "definite"
119/// PHI. If it's not truly live-through, the variable value will be downgraded
120/// further as we explore the lattice, or remains "proposed" and is considered
121/// invalid once dataflow completes.
122///
123/// ### Terminology
124///
125/// A machine location is a register or spill slot, a value is something that's
126/// defined by an instruction or PHI node, while a variable value is the value
127/// assigned to a variable. A variable location is a machine location, that must
128/// contain the appropriate variable value. A value that is a PHI node is
129/// occasionally called an mphi.
130///
131/// The first dataflow problem is the "machine value location" problem,
132/// because we're determining which machine locations contain which values.
133/// The "locations" are constant: what's unknown is what value they contain.
134///
135/// The second dataflow problem (the one for variables) is the "variable value
136/// problem", because it's determining what values a variable has, rather than
137/// what location those values are placed in. Unfortunately, it's not that
138/// simple, because producing a PHI value always involves picking a location.
139/// This is an imperfection that we just have to accept, at least for now.
140///
141/// TODO:
142///   Overlapping fragments
143///   Entry values
144///   Add back DEBUG statements for debugging this
145///   Collect statistics
146///
147//===----------------------------------------------------------------------===//

149#include "llvm/ADT/DenseMap.h"
150#include "llvm/ADT/PostOrderIterator.h"
151#include "llvm/ADT/STLExtras.h"
152#include "llvm/ADT/SmallPtrSet.h"
153#include "llvm/ADT/SmallSet.h"
154#include "llvm/ADT/SmallVector.h"
155#include "llvm/ADT/Statistic.h"
156#include "llvm/ADT/UniqueVector.h"
157#include "llvm/CodeGen/LexicalScopes.h"
158#include "llvm/CodeGen/MachineBasicBlock.h"
159#include "llvm/CodeGen/MachineFrameInfo.h"
160#include "llvm/CodeGen/MachineFunction.h"
161#include "llvm/CodeGen/MachineFunctionPass.h"
162#include "llvm/CodeGen/MachineInstr.h"
163#include "llvm/CodeGen/MachineInstrBuilder.h"
164#include "llvm/CodeGen/MachineInstrBundle.h"
165#include "llvm/CodeGen/MachineMemOperand.h"
166#include "llvm/CodeGen/MachineOperand.h"
167#include "llvm/CodeGen/PseudoSourceValue.h"
168#include "llvm/CodeGen/RegisterScavenging.h"
169#include "llvm/CodeGen/TargetFrameLowering.h"
170#include "llvm/CodeGen/TargetInstrInfo.h"
171#include "llvm/CodeGen/TargetLowering.h"
172#include "llvm/CodeGen/TargetPassConfig.h"
173#include "llvm/CodeGen/TargetRegisterInfo.h"
174#include "llvm/CodeGen/TargetSubtargetInfo.h"
175#include "llvm/Config/llvm-config.h"
176#include "llvm/IR/DIBuilder.h"
177#include "llvm/IR/DebugInfoMetadata.h"
178#include "llvm/IR/DebugLoc.h"
179#include "llvm/IR/Function.h"
180#include "llvm/IR/Module.h"
181#include "llvm/InitializePasses.h"
182#include "llvm/MC/MCRegisterInfo.h"
183#include "llvm/Pass.h"
184#include "llvm/Support/Casting.h"
185#include "llvm/Support/Compiler.h"
186#include "llvm/Support/Debug.h"
187#include "llvm/Support/TypeSize.h"
188#include "llvm/Support/raw_ostream.h"
189#include "llvm/Target/TargetMachine.h"
190#include "llvm/Transforms/Utils/SSAUpdaterImpl.h"
191#include <algorithm>
192#include <cassert>
193#include <cstdint>
194#include <functional>
195#include <queue>
196#include <tuple>
197#include <utility>
198#include <vector>
199#include <limits.h>
200#include <limits>

202#include "LiveDebugValues.h"

204using namespace llvm;

206// SSAUpdaterImple sets DEBUG_TYPE, change it.
207#undef DEBUG_TYPE"livedebugvalues"
208#define DEBUG_TYPE"livedebugvalues" "livedebugvalues"

210// Act more like the VarLoc implementation, by propagating some locations too
211// far and ignoring some transfers.
212static cl::opt<bool> EmulateOldLDV("emulate-old-livedebugvalues", cl::Hidden,
                                 cl::desc("Act like old LiveDebugValues did"),
                                 cl::init(false));

216namespace {

218// The location at which a spilled value resides. It consists of a register and
219// an offset.
220struct SpillLoc {
unsigned SpillBase;
StackOffset SpillOffset;
bool operator==(const SpillLoc &Other) const {
  return std::make_pair(SpillBase, SpillOffset) ==
         std::make_pair(Other.SpillBase, Other.SpillOffset);
}
bool operator<(const SpillLoc &Other) const {
  return std::make_tuple(SpillBase, SpillOffset.getFixed(),
                  SpillOffset.getScalable()) <
         std::make_tuple(Other.SpillBase, Other.SpillOffset.getFixed(),
                  Other.SpillOffset.getScalable());
}
233};

235class LocIdx {
unsigned Location;

// Default constructor is private, initializing to an illegal location number.
// Use only for "not an entry" elements in IndexedMaps.
LocIdx() : Location(UINT_MAX(2147483647 *2U +1U)) { }

242public:
#define NUM_LOC_BITS24 24
LocIdx(unsigned L) : Location(L) {
  assert(L < (1 << NUM_LOC_BITS) && "Machine locations must fit in 24 bits")((void)0);
}

static LocIdx MakeIllegalLoc() {
  return LocIdx();
}

bool isIllegal() const {
  return Location == UINT_MAX(2147483647 *2U +1U);
}

uint64_t asU64() const {
  return Location;
}

bool operator==(unsigned L) const {
  return Location == L;
}

bool operator==(const LocIdx &L) const {
  return Location == L.Location;
}

bool operator!=(unsigned L) const {
  return !(*this == L);
}

bool operator!=(const LocIdx &L) const {
  return !(*this == L);
}

bool operator<(const LocIdx &Other) const {
  return Location < Other.Location;
}
279};

281class LocIdxToIndexFunctor {
282public:
using argument_type = LocIdx;
unsigned operator()(const LocIdx &L) const {
  return L.asU64();
}
287};

289/// Unique identifier for a value defined by an instruction, as a value type.
290/// Casts back and forth to a uint64_t. Probably replacable with something less
291/// bit-constrained. Each value identifies the instruction and machine location
292/// where the value is defined, although there may be no corresponding machine
293/// operand for it (ex: regmasks clobbering values). The instructions are
294/// one-based, and definitions that are PHIs have instruction number zero.
295///
296/// The obvious limits of a 1M block function or 1M instruction blocks are
297/// problematic; but by that point we should probably have bailed out of
298/// trying to analyse the function.
299class ValueIDNum {
uint64_t BlockNo : 20;         /// The block where the def happens.
uint64_t InstNo : 20;          /// The Instruction where the def happens.
                               /// One based, is distance from start of block.
uint64_t LocNo : NUM_LOC_BITS24; /// The machine location where the def happens.

305public:
// XXX -- temporarily enabled while the live-in / live-out tables are moved
// to something more type-y
ValueIDNum() : BlockNo(0xFFFFF),
               InstNo(0xFFFFF),
               LocNo(0xFFFFFF) { }

ValueIDNum(uint64_t Block, uint64_t Inst, uint64_t Loc)
  : BlockNo(Block), InstNo(Inst), LocNo(Loc) { }

ValueIDNum(uint64_t Block, uint64_t Inst, LocIdx Loc)
  : BlockNo(Block), InstNo(Inst), LocNo(Loc.asU64()) { }

uint64_t getBlock() const { return BlockNo; }
uint64_t getInst() const { return InstNo; }
uint64_t getLoc() const { return LocNo; }
bool isPHI() const { return InstNo == 0; }

uint64_t asU64() const {
  uint64_t TmpBlock = BlockNo;
  uint64_t TmpInst = InstNo;
  return TmpBlock << 44ull | TmpInst << NUM_LOC_BITS24 | LocNo;
}

static ValueIDNum fromU64(uint64_t v) {
  uint64_t L = (v & 0x3FFF);
  return {v >> 44ull, ((v >> NUM_LOC_BITS24) & 0xFFFFF), L};
}

bool operator<(const ValueIDNum &Other) const {
  return asU64() < Other.asU64();
}

bool operator==(const ValueIDNum &Other) const {
  return std::tie(BlockNo, InstNo, LocNo) ==
         std::tie(Other.BlockNo, Other.InstNo, Other.LocNo);
}

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

std::string asString(const std::string &mlocname) const {
  return Twine("Value{bb: ")
      .concat(Twine(BlockNo).concat(
          Twine(", inst: ")
              .concat((InstNo ? Twine(InstNo) : Twine("live-in"))
                          .concat(Twine(", loc: ").concat(Twine(mlocname)))
                          .concat(Twine("}")))))
      .str();
}

static ValueIDNum EmptyValue;
356};

358} // end anonymous namespace

360namespace {

362/// Meta qualifiers for a value. Pair of whatever expression is used to qualify
363/// the the value, and Boolean of whether or not it's indirect.
364class DbgValueProperties {
365public:
DbgValueProperties(const DIExpression *DIExpr, bool Indirect)
    : DIExpr(DIExpr), Indirect(Indirect) {}

/// Extract properties from an existing DBG_VALUE instruction.
DbgValueProperties(const MachineInstr &MI) {
  assert(MI.isDebugValue())((void)0);
  DIExpr = MI.getDebugExpression();
  Indirect = MI.getOperand(1).isImm();
}

bool operator==(const DbgValueProperties &Other) const {
  return std::tie(DIExpr, Indirect) == std::tie(Other.DIExpr, Other.Indirect);
}

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

const DIExpression *DIExpr;
bool Indirect;
386};

388/// Tracker for what values are in machine locations. Listens to the Things
389/// being Done by various instructions, and maintains a table of what machine
390/// locations have what values (as defined by a ValueIDNum).
391///
392/// There are potentially a much larger number of machine locations on the
393/// target machine than the actual working-set size of the function. On x86 for
394/// example, we're extremely unlikely to want to track values through control
395/// or debug registers. To avoid doing so, MLocTracker has several layers of
396/// indirection going on, with two kinds of ``location'':
397///  * A LocID uniquely identifies a register or spill location, with a
398///    predictable value.
399///  * A LocIdx is a key (in the database sense) for a LocID and a ValueIDNum.
400/// Whenever a location is def'd or used by a MachineInstr, we automagically
401/// create a new LocIdx for a location, but not otherwise. This ensures we only
402/// account for locations that are actually used or defined. The cost is another
403/// vector lookup (of LocID -> LocIdx) over any other implementation. This is
404/// fairly cheap, and the compiler tries to reduce the working-set at any one
405/// time in the function anyway.
406///
407/// Register mask operands completely blow this out of the water; I've just
408/// piled hacks on top of hacks to get around that.
409class MLocTracker {
410public:
MachineFunction &MF;
const TargetInstrInfo &TII;
const TargetRegisterInfo &TRI;
const TargetLowering &TLI;

/// IndexedMap type, mapping from LocIdx to ValueIDNum.
using LocToValueType = IndexedMap<ValueIDNum, LocIdxToIndexFunctor>;

/// Map of LocIdxes to the ValueIDNums that they store. This is tightly
/// packed, entries only exist for locations that are being tracked.
LocToValueType LocIdxToIDNum;

/// "Map" of machine location IDs (i.e., raw register or spill number) to the
/// LocIdx key / number for that location. There are always at least as many
/// as the number of registers on the target -- if the value in the register
/// is not being tracked, then the LocIdx value will be zero. New entries are
/// appended if a new spill slot begins being tracked.
/// This, and the corresponding reverse map persist for the analysis of the
/// whole function, and is necessarying for decoding various vectors of
/// values.
std::vector<LocIdx> LocIDToLocIdx;

/// Inverse map of LocIDToLocIdx.
IndexedMap<unsigned, LocIdxToIndexFunctor> LocIdxToLocID;

/// Unique-ification of spill slots. Used to number them -- their LocID
/// number is the index in SpillLocs minus one plus NumRegs.
UniqueVector<SpillLoc> SpillLocs;

// If we discover a new machine location, assign it an mphi with this
// block number.
unsigned CurBB;

/// Cached local copy of the number of registers the target has.
unsigned NumRegs;

/// Collection of register mask operands that have been observed. Second part
/// of pair indicates the instruction that they happened in. Used to
/// reconstruct where defs happened if we start tracking a location later
/// on.
SmallVector<std::pair<const MachineOperand *, unsigned>, 32> Masks;

/// Iterator for locations and the values they contain. Dereferencing
/// produces a struct/pair containing the LocIdx key for this location,
/// and a reference to the value currently stored. Simplifies the process
/// of seeking a particular location.
class MLocIterator {
  LocToValueType &ValueMap;
  LocIdx Idx;

public:
  class value_type {
    public:
    value_type(LocIdx Idx, ValueIDNum &Value) : Idx(Idx), Value(Value) { }
    const LocIdx Idx;  /// Read-only index of this location.
    ValueIDNum &Value; /// Reference to the stored value at this location.
  };

  MLocIterator(LocToValueType &ValueMap, LocIdx Idx)
    : ValueMap(ValueMap), Idx(Idx) { }

  bool operator==(const MLocIterator &Other) const {
    assert(&ValueMap == &Other.ValueMap)((void)0);
    return Idx == Other.Idx;
  }

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

  void operator++() {
    Idx = LocIdx(Idx.asU64() + 1);
  }

  value_type operator*() {
    return value_type(Idx, ValueMap[LocIdx(Idx)]);
  }
};

MLocTracker(MachineFunction &MF, const TargetInstrInfo &TII,
            const TargetRegisterInfo &TRI, const TargetLowering &TLI)
    : MF(MF), TII(TII), TRI(TRI), TLI(TLI),
      LocIdxToIDNum(ValueIDNum::EmptyValue),
      LocIdxToLocID(0) {
  NumRegs = TRI.getNumRegs();
  reset();
  LocIDToLocIdx.resize(NumRegs, LocIdx::MakeIllegalLoc());
  assert(NumRegs < (1u << NUM_LOC_BITS))((void)0); // Detect bit packing failure

  // Always track SP. This avoids the implicit clobbering caused by regmasks
  // from affectings its values. (LiveDebugValues disbelieves calls and
  // regmasks that claim to clobber SP).
  Register SP = TLI.getStackPointerRegisterToSaveRestore();
  if (SP) {
    unsigned ID = getLocID(SP, false);
    (void)lookupOrTrackRegister(ID);
  }
}

/// Produce location ID number for indexing LocIDToLocIdx. Takes the register
/// or spill number, and flag for whether it's a spill or not.
unsigned getLocID(Register RegOrSpill, bool isSpill) {
  return (isSpill) ? RegOrSpill.id() + NumRegs - 1 : RegOrSpill.id();
}

/// Accessor for reading the value at Idx.
ValueIDNum getNumAtPos(LocIdx Idx) const {
  assert(Idx.asU64() < LocIdxToIDNum.size())((void)0);
  return LocIdxToIDNum[Idx];
}

unsigned getNumLocs(void) const { return LocIdxToIDNum.size(); }

/// Reset all locations to contain a PHI value at the designated block. Used
/// sometimes for actual PHI values, othertimes to indicate the block entry
/// value (before any more information is known).
void setMPhis(unsigned NewCurBB) {
  CurBB = NewCurBB;
  for (auto Location : locations())
    Location.Value = {CurBB, 0, Location.Idx};
}

/// Load values for each location from array of ValueIDNums. Take current
/// bbnum just in case we read a value from a hitherto untouched register.
void loadFromArray(ValueIDNum *Locs, unsigned NewCurBB) {
  CurBB = NewCurBB;
  // Iterate over all tracked locations, and load each locations live-in
  // value into our local index.
  for (auto Location : locations())
    Location.Value = Locs[Location.Idx.asU64()];
}

/// Wipe any un-necessary location records after traversing a block.
void reset(void) {
  // We could reset all the location values too; however either loadFromArray
  // or setMPhis should be called before this object is re-used. Just
  // clear Masks, they're definitely not needed.
  Masks.clear();
}

/// Clear all data. Destroys the LocID <=> LocIdx map, which makes most of
/// the information in this pass uninterpretable.
void clear(void) {
  reset();
  LocIDToLocIdx.clear();
  LocIdxToLocID.clear();
  LocIdxToIDNum.clear();
  //SpillLocs.reset(); XXX UniqueVector::reset assumes a SpillLoc casts from 0
  SpillLocs = decltype(SpillLocs)();

  LocIDToLocIdx.resize(NumRegs, LocIdx::MakeIllegalLoc());
}

/// Set a locaiton to a certain value.
void setMLoc(LocIdx L, ValueIDNum Num) {
  assert(L.asU64() < LocIdxToIDNum.size())((void)0);
  LocIdxToIDNum[L] = Num;
}

/// Create a LocIdx for an untracked register ID. Initialize it to either an
/// mphi value representing a live-in, or a recent register mask clobber.
LocIdx trackRegister(unsigned ID) {
  assert(ID != 0)((void)0);
  LocIdx NewIdx = LocIdx(LocIdxToIDNum.size());
  LocIdxToIDNum.grow(NewIdx);
  LocIdxToLocID.grow(NewIdx);

  // Default: it's an mphi.
  ValueIDNum ValNum = {CurBB, 0, NewIdx};
  // Was this reg ever touched by a regmask?
  for (const auto &MaskPair : reverse(Masks)) {
    if (MaskPair.first->clobbersPhysReg(ID)) {
      // There was an earlier def we skipped.
      ValNum = {CurBB, MaskPair.second, NewIdx};
      break;
    }
  }

  LocIdxToIDNum[NewIdx] = ValNum;
  LocIdxToLocID[NewIdx] = ID;
  return NewIdx;
}

LocIdx lookupOrTrackRegister(unsigned ID) {
  LocIdx &Index = LocIDToLocIdx[ID];
  if (Index.isIllegal())
    Index = trackRegister(ID);
  return Index;
}

/// Record a definition of the specified register at the given block / inst.
/// This doesn't take a ValueIDNum, because the definition and its location
/// are synonymous.
void defReg(Register R, unsigned BB, unsigned Inst) {
  unsigned ID = getLocID(R, false);
  LocIdx Idx = lookupOrTrackRegister(ID);
  ValueIDNum ValueID = {BB, Inst, Idx};
  LocIdxToIDNum[Idx] = ValueID;
}

/// Set a register to a value number. To be used if the value number is
/// known in advance.
void setReg(Register R, ValueIDNum ValueID) {
  unsigned ID = getLocID(R, false);
  LocIdx Idx = lookupOrTrackRegister(ID);
  LocIdxToIDNum[Idx] = ValueID;
}

ValueIDNum readReg(Register R) {
  unsigned ID = getLocID(R, false);
  LocIdx Idx = lookupOrTrackRegister(ID);
  return LocIdxToIDNum[Idx];
}

/// Reset a register value to zero / empty. Needed to replicate the
/// VarLoc implementation where a copy to/from a register effectively
/// clears the contents of the source register. (Values can only have one
///  machine location in VarLocBasedImpl).
void wipeRegister(Register R) {
  unsigned ID = getLocID(R, false);
  LocIdx Idx = LocIDToLocIdx[ID];
  LocIdxToIDNum[Idx] = ValueIDNum::EmptyValue;
}

/// Determine the LocIdx of an existing register.
LocIdx getRegMLoc(Register R) {
  unsigned ID = getLocID(R, false);
  return LocIDToLocIdx[ID];
}

/// Record a RegMask operand being executed. Defs any register we currently
/// track, stores a pointer to the mask in case we have to account for it
/// later.
void writeRegMask(const MachineOperand *MO, unsigned CurBB, unsigned InstID) {
  // Ensure SP exists, so that we don't override it later.
  Register SP = TLI.getStackPointerRegisterToSaveRestore();

  // Def any register we track have that isn't preserved. The regmask
  // terminates the liveness of a register, meaning its value can't be
  // relied upon -- we represent this by giving it a new value.
  for (auto Location : locations()) {
    unsigned ID = LocIdxToLocID[Location.Idx];
    // Don't clobber SP, even if the mask says it's clobbered.
    if (ID < NumRegs && ID != SP && MO->clobbersPhysReg(ID))
      defReg(ID, CurBB, InstID);
  }
  Masks.push_back(std::make_pair(MO, InstID));
}

/// Find LocIdx for SpillLoc \p L, creating a new one if it's not tracked.
LocIdx getOrTrackSpillLoc(SpillLoc L) {
  unsigned SpillID = SpillLocs.idFor(L);
  if (SpillID == 0) {
    SpillID = SpillLocs.insert(L);
    unsigned L = getLocID(SpillID, true);
    LocIdx Idx = LocIdx(LocIdxToIDNum.size()); // New idx
    LocIdxToIDNum.grow(Idx);
    LocIdxToLocID.grow(Idx);
    LocIDToLocIdx.push_back(Idx);
    LocIdxToLocID[Idx] = L;
    return Idx;
  } else {
    unsigned L = getLocID(SpillID, true);
    LocIdx Idx = LocIDToLocIdx[L];
    return Idx;
  }
}

/// Set the value stored in a spill slot.
void setSpill(SpillLoc L, ValueIDNum ValueID) {
  LocIdx Idx = getOrTrackSpillLoc(L);
  LocIdxToIDNum[Idx] = ValueID;
}

/// Read whatever value is in a spill slot, or None if it isn't tracked.
Optional<ValueIDNum> readSpill(SpillLoc L) {
  unsigned SpillID = SpillLocs.idFor(L);
  if (SpillID == 0)
    return None;

  unsigned LocID = getLocID(SpillID, true);
  LocIdx Idx = LocIDToLocIdx[LocID];
  return LocIdxToIDNum[Idx];
}

/// Determine the LocIdx of a spill slot. Return None if it previously
/// hasn't had a value assigned.
Optional<LocIdx> getSpillMLoc(SpillLoc L) {
  unsigned SpillID = SpillLocs.idFor(L);
  if (SpillID == 0)
    return None;
  unsigned LocNo = getLocID(SpillID, true);
  return LocIDToLocIdx[LocNo];
}

/// Return true if Idx is a spill machine location.
bool isSpill(LocIdx Idx) const {
  return LocIdxToLocID[Idx] >= NumRegs;
}

MLocIterator begin() {
  return MLocIterator(LocIdxToIDNum, 0);
}

MLocIterator end() {
  return MLocIterator(LocIdxToIDNum, LocIdxToIDNum.size());
}

/// Return a range over all locations currently tracked.
iterator_range<MLocIterator> locations() {
  return llvm::make_range(begin(), end());
}

std::string LocIdxToName(LocIdx Idx) const {
  unsigned ID = LocIdxToLocID[Idx];
  if (ID >= NumRegs)
    return Twine("slot ").concat(Twine(ID - NumRegs)).str();
  else
    return TRI.getRegAsmName(ID).str();
}

std::string IDAsString(const ValueIDNum &Num) const {
  std::string DefName = LocIdxToName(Num.getLoc());
  return Num.asString(DefName);
}

LLVM_DUMP_METHOD__attribute__((noinline))
void dump() {
  for (auto Location : locations()) {
    std::string MLocName = LocIdxToName(Location.Value.getLoc());
    std::string DefName = Location.Value.asString(MLocName);
    dbgs() << LocIdxToName(Location.Idx) << " --> " << DefName << "\n";
  }
}

LLVM_DUMP_METHOD__attribute__((noinline))
void dump_mloc_map() {
  for (auto Location : locations()) {
    std::string foo = LocIdxToName(Location.Idx);
    dbgs() << "Idx " << Location.Idx.asU64() << " " << foo << "\n";
  }
}

/// Create a DBG_VALUE based on  machine location \p MLoc. Qualify it with the
/// information in \pProperties, for variable Var. Don't insert it anywhere,
/// just return the builder for it.
MachineInstrBuilder emitLoc(Optional<LocIdx> MLoc, const DebugVariable &Var,
                            const DbgValueProperties &Properties) {
  DebugLoc DL = DILocation::get(Var.getVariable()->getContext(), 0, 0,
                                Var.getVariable()->getScope(),
                                const_cast<DILocation *>(Var.getInlinedAt()));
  auto MIB = BuildMI(MF, DL, TII.get(TargetOpcode::DBG_VALUE));

  const DIExpression *Expr = Properties.DIExpr;
  if (!MLoc) {
    // No location -> DBG_VALUE $noreg
    MIB.addReg(0, RegState::Debug);
    MIB.addReg(0, RegState::Debug);
  } else if (LocIdxToLocID[*MLoc] >= NumRegs) {
    unsigned LocID = LocIdxToLocID[*MLoc];
    const SpillLoc &Spill = SpillLocs[LocID - NumRegs + 1];

    auto *TRI = MF.getSubtarget().getRegisterInfo();
    Expr = TRI->prependOffsetExpression(Expr, DIExpression::ApplyOffset,
                                        Spill.SpillOffset);
    unsigned Base = Spill.SpillBase;
    MIB.addReg(Base, RegState::Debug);
    MIB.addImm(0);
  } else {
    unsigned LocID = LocIdxToLocID[*MLoc];
    MIB.addReg(LocID, RegState::Debug);
    if (Properties.Indirect)
      MIB.addImm(0);
    else
      MIB.addReg(0, RegState::Debug);
  }

  MIB.addMetadata(Var.getVariable());
  MIB.addMetadata(Expr);
  return MIB;
}
792};

794/// Class recording the (high level) _value_ of a variable. Identifies either
795/// the value of the variable as a ValueIDNum, or a constant MachineOperand.
796/// This class also stores meta-information about how the value is qualified.
797/// Used to reason about variable values when performing the second
798/// (DebugVariable specific) dataflow analysis.
799class DbgValue {
800public:
union {
  /// If Kind is Def, the value number that this value is based on.
  ValueIDNum ID;
  /// If Kind is Const, the MachineOperand defining this value.
  MachineOperand MO;
  /// For a NoVal DbgValue, which block it was generated in.
  unsigned BlockNo;
};
/// Qualifiers for the ValueIDNum above.
DbgValueProperties Properties;

typedef enum {
  Undef,     // Represents a DBG_VALUE $noreg in the transfer function only.
  Def,       // This value is defined by an inst, or is a PHI value.
  Const,     // A constant value contained in the MachineOperand field.
  Proposed,  // This is a tentative PHI value, which may be confirmed or
             // invalidated later.
  NoVal      // Empty DbgValue, generated during dataflow. BlockNo stores
             // which block this was generated in.
 } KindT;
/// Discriminator for whether this is a constant or an in-program value.
KindT Kind;

DbgValue(const ValueIDNum &Val, const DbgValueProperties &Prop, KindT Kind)
  : ID(Val), Properties(Prop), Kind(Kind) {
  assert(Kind == Def || Kind == Proposed)((void)0);
}

DbgValue(unsigned BlockNo, const DbgValueProperties &Prop, KindT Kind)
  : BlockNo(BlockNo), Properties(Prop), Kind(Kind) {
  assert(Kind == NoVal)((void)0);
}

DbgValue(const MachineOperand &MO, const DbgValueProperties &Prop, KindT Kind)
  : MO(MO), Properties(Prop), Kind(Kind) {
  assert(Kind == Const)((void)0);
}

DbgValue(const DbgValueProperties &Prop, KindT Kind)
  : Properties(Prop), Kind(Kind) {
  assert(Kind == Undef &&((void)0)
         "Empty DbgValue constructor must pass in Undef kind")((void)0);
}

void dump(const MLocTracker *MTrack) const {
  if (Kind == Const) {
    MO.dump();
  } else if (Kind == NoVal) {
    dbgs() << "NoVal(" << BlockNo << ")";
  } else if (Kind == Proposed) {
    dbgs() << "VPHI(" << MTrack->IDAsString(ID) << ")";
  } else {
    assert(Kind == Def)((void)0);
    dbgs() << MTrack->IDAsString(ID);
  }
  if (Properties.Indirect)
    dbgs() << " indir";
  if (Properties.DIExpr)
    dbgs() << " " << *Properties.DIExpr;
}

bool operator==(const DbgValue &Other) const {
  if (std::tie(Kind, Properties) != std::tie(Other.Kind, Other.Properties))
    return false;
  else if (Kind == Proposed && ID != Other.ID)
    return false;
  else if (Kind == Def && ID != Other.ID)
    return false;
  else if (Kind == NoVal && BlockNo != Other.BlockNo)
    return false;
  else if (Kind == Const)
    return MO.isIdenticalTo(Other.MO);

  return true;
}

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

880/// Types for recording sets of variable fragments that overlap. For a given
881/// local variable, we record all other fragments of that variable that could
882/// overlap it, to reduce search time.
883using FragmentOfVar =
  std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
885using OverlapMap =
  DenseMap<FragmentOfVar, SmallVector<DIExpression::FragmentInfo, 1>>;

888/// Collection of DBG_VALUEs observed when traversing a block. Records each
889/// variable and the value the DBG_VALUE refers to. Requires the machine value
890/// location dataflow algorithm to have run already, so that values can be
891/// identified.
892class VLocTracker {
893public:
/// Map DebugVariable to the latest Value it's defined to have.
/// Needs to be a MapVector because we determine order-in-the-input-MIR from
/// the order in this container.
/// We only retain the last DbgValue in each block for each variable, to
/// determine the blocks live-out variable value. The Vars container forms the
/// transfer function for this block, as part of the dataflow analysis. The
/// movement of values between locations inside of a block is handled at a
/// much later stage, in the TransferTracker class.
MapVector<DebugVariable, DbgValue> Vars;
DenseMap<DebugVariable, const DILocation *> Scopes;
MachineBasicBlock *MBB;

906public:
VLocTracker() {}

void defVar(const MachineInstr &MI, const DbgValueProperties &Properties,
            Optional<ValueIDNum> ID) {
  assert(MI.isDebugValue() || MI.isDebugRef())((void)0);
  DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
                    MI.getDebugLoc()->getInlinedAt());
  DbgValue Rec = (ID) ? DbgValue(*ID, Properties, DbgValue::Def)
                      : DbgValue(Properties, DbgValue::Undef);

  // Attempt insertion; overwrite if it's already mapped.
  auto Result = Vars.insert(std::make_pair(Var, Rec));
  if (!Result.second)
    Result.first->second = Rec;
  Scopes[Var] = MI.getDebugLoc().get();
}

void defVar(const MachineInstr &MI, const MachineOperand &MO) {
  // Only DBG_VALUEs can define constant-valued variables.
  assert(MI.isDebugValue())((void)0);
  DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
                    MI.getDebugLoc()->getInlinedAt());
  DbgValueProperties Properties(MI);
  DbgValue Rec = DbgValue(MO, Properties, DbgValue::Const);

  // Attempt insertion; overwrite if it's already mapped.
  auto Result = Vars.insert(std::make_pair(Var, Rec));
  if (!Result.second)
    Result.first->second = Rec;
  Scopes[Var] = MI.getDebugLoc().get();
}
938};

940/// Tracker for converting machine value locations and variable values into
941/// variable locations (the output of LiveDebugValues), recorded as DBG_VALUEs
942/// specifying block live-in locations and transfers within blocks.
943///
944/// Operating on a per-block basis, this class takes a (pre-loaded) MLocTracker
945/// and must be initialized with the set of variable values that are live-in to
946/// the block. The caller then repeatedly calls process(). TransferTracker picks
947/// out variable locations for the live-in variable values (if there _is_ a
948/// location) and creates the corresponding DBG_VALUEs. Then, as the block is
949/// stepped through, transfers of values between machine locations are
950/// identified and if profitable, a DBG_VALUE created.
951///
952/// This is where debug use-before-defs would be resolved: a variable with an
953/// unavailable value could materialize in the middle of a block, when the
954/// value becomes available. Or, we could detect clobbers and re-specify the
955/// variable in a backup location. (XXX these are unimplemented).
956class TransferTracker {
957public:
const TargetInstrInfo *TII;
const TargetLowering *TLI;
/// This machine location tracker is assumed to always contain the up-to-date
/// value mapping for all machine locations. TransferTracker only reads
/// information from it. (XXX make it const?)
MLocTracker *MTracker;
MachineFunction &MF;
bool ShouldEmitDebugEntryValues;

/// Record of all changes in variable locations at a block position. Awkwardly
/// we allow inserting either before or after the point: MBB != nullptr
/// indicates it's before, otherwise after.
struct Transfer {
  MachineBasicBlock::instr_iterator Pos; /// Position to insert DBG_VALUes
  MachineBasicBlock *MBB; /// non-null if we should insert after.
  SmallVector<MachineInstr *, 4> Insts; /// Vector of DBG_VALUEs to insert.
};

struct LocAndProperties {
  LocIdx Loc;
  DbgValueProperties Properties;
};

/// Collection of transfers (DBG_VALUEs) to be inserted.
SmallVector<Transfer, 32> Transfers;

/// Local cache of what-value-is-in-what-LocIdx. Used to identify differences
/// between TransferTrackers view of variable locations and MLocTrackers. For
/// example, MLocTracker observes all clobbers, but TransferTracker lazily
/// does not.
std::vector<ValueIDNum> VarLocs;

/// Map from LocIdxes to which DebugVariables are based that location.
/// Mantained while stepping through the block. Not accurate if
/// VarLocs[Idx] != MTracker->LocIdxToIDNum[Idx].
std::map<LocIdx, SmallSet<DebugVariable, 4>> ActiveMLocs;

/// Map from DebugVariable to it's current location and qualifying meta
/// information. To be used in conjunction with ActiveMLocs to construct
/// enough information for the DBG_VALUEs for a particular LocIdx.
DenseMap<DebugVariable, LocAndProperties> ActiveVLocs;

/// Temporary cache of DBG_VALUEs to be entered into the Transfers collection.
SmallVector<MachineInstr *, 4> PendingDbgValues;

/// Record of a use-before-def: created when a value that's live-in to the
/// current block isn't available in any machine location, but it will be
/// defined in this block.
struct UseBeforeDef {
  /// Value of this variable, def'd in block.
  ValueIDNum ID;
  /// Identity of this variable.
  DebugVariable Var;
  /// Additional variable properties.
  DbgValueProperties Properties;
};

/// Map from instruction index (within the block) to the set of UseBeforeDefs
/// that become defined at that instruction.
DenseMap<unsigned, SmallVector<UseBeforeDef, 1>> UseBeforeDefs;

/// The set of variables that are in UseBeforeDefs and can become a location
/// once the relevant value is defined. An element being erased from this
/// collection prevents the use-before-def materializing.
DenseSet<DebugVariable> UseBeforeDefVariables;

const TargetRegisterInfo &TRI;
const BitVector &CalleeSavedRegs;

TransferTracker(const TargetInstrInfo *TII, MLocTracker *MTracker,
                MachineFunction &MF, const TargetRegisterInfo &TRI,
                const BitVector &CalleeSavedRegs, const TargetPassConfig &TPC)
    : TII(TII), MTracker(MTracker), MF(MF), TRI(TRI),
      CalleeSavedRegs(CalleeSavedRegs) {
  TLI = MF.getSubtarget().getTargetLowering();
  auto &TM = TPC.getTM<TargetMachine>();
  ShouldEmitDebugEntryValues = TM.Options.ShouldEmitDebugEntryValues();
}

/// Load object with live-in variable values. \p mlocs contains the live-in
/// values in each machine location, while \p vlocs the live-in variable
/// values. This method picks variable locations for the live-in variables,
/// creates DBG_VALUEs and puts them in #Transfers, then prepares the other
/// object fields to track variable locations as we step through the block.
/// FIXME: could just examine mloctracker instead of passing in \p mlocs?
void loadInlocs(MachineBasicBlock &MBB, ValueIDNum *MLocs,
                SmallVectorImpl<std::pair<DebugVariable, DbgValue>> &VLocs,
                unsigned NumLocs) {
  ActiveMLocs.clear();
  ActiveVLocs.clear();
  VarLocs.clear();
  VarLocs.reserve(NumLocs);
  UseBeforeDefs.clear();
  UseBeforeDefVariables.clear();

  auto isCalleeSaved = [&](LocIdx L) {
    unsigned Reg = MTracker->LocIdxToLocID[L];
    if (Reg >= MTracker->NumRegs)
      return false;
    for (MCRegAliasIterator RAI(Reg, &TRI, true); RAI.isValid(); ++RAI)
      if (CalleeSavedRegs.test(*RAI))
        return true;
    return false;
  };

  // Map of the preferred location for each value.
  std::map<ValueIDNum, LocIdx> ValueToLoc;

  // Produce a map of value numbers to the current machine locs they live
  // in. When emulating VarLocBasedImpl, there should only be one
  // location; when not, we get to pick.
  for (auto Location : MTracker->locations()) {
    LocIdx Idx = Location.Idx;
    ValueIDNum &VNum = MLocs[Idx.asU64()];
    VarLocs.push_back(VNum);
    auto it = ValueToLoc.find(VNum);
    // In order of preference, pick:
    //  * Callee saved registers,
    //  * Other registers,
    //  * Spill slots.
    if (it == ValueToLoc.end() || MTracker->isSpill(it->second) ||
        (!isCalleeSaved(it->second) && isCalleeSaved(Idx.asU64()))) {
      // Insert, or overwrite if insertion failed.
      auto PrefLocRes = ValueToLoc.insert(std::make_pair(VNum, Idx));
      if (!PrefLocRes.second)
        PrefLocRes.first->second = Idx;
    }
  }

  // Now map variables to their picked LocIdxes.
  for (auto Var : VLocs) {
    if (Var.second.Kind == DbgValue::Const) {
      PendingDbgValues.push_back(
          emitMOLoc(Var.second.MO, Var.first, Var.second.Properties));
      continue;
    }

    // If the value has no location, we can't make a variable location.
    const ValueIDNum &Num = Var.second.ID;
    auto ValuesPreferredLoc = ValueToLoc.find(Num);
    if (ValuesPreferredLoc == ValueToLoc.end()) {
      // If it's a def that occurs in this block, register it as a
      // use-before-def to be resolved as we step through the block.
      if (Num.getBlock() == (unsigned)MBB.getNumber() && !Num.isPHI())
        addUseBeforeDef(Var.first, Var.second.Properties, Num);
      else
        recoverAsEntryValue(Var.first, Var.second.Properties, Num);
      continue;
    }

    LocIdx M = ValuesPreferredLoc->second;
    auto NewValue = LocAndProperties{M, Var.second.Properties};
    auto Result = ActiveVLocs.insert(std::make_pair(Var.first, NewValue));
    if (!Result.second)
      Result.first->second = NewValue;
    ActiveMLocs[M].insert(Var.first);
    PendingDbgValues.push_back(
        MTracker->emitLoc(M, Var.first, Var.second.Properties));
  }
  flushDbgValues(MBB.begin(), &MBB);
}

/// Record that \p Var has value \p ID, a value that becomes available
/// later in the function.
void addUseBeforeDef(const DebugVariable &Var,
                     const DbgValueProperties &Properties, ValueIDNum ID) {
  UseBeforeDef UBD = {ID, Var, Properties};
  UseBeforeDefs[ID.getInst()].push_back(UBD);
  UseBeforeDefVariables.insert(Var);
}

/// After the instruction at index \p Inst and position \p pos has been
/// processed, check whether it defines a variable value in a use-before-def.
/// If so, and the variable value hasn't changed since the start of the
/// block, create a DBG_VALUE.
void checkInstForNewValues(unsigned Inst, MachineBasicBlock::iterator pos) {
  auto MIt = UseBeforeDefs.find(Inst);
  if (MIt == UseBeforeDefs.end())
    return;

  for (auto &Use : MIt->second) {
    LocIdx L = Use.ID.getLoc();

    // If something goes very wrong, we might end up labelling a COPY
    // instruction or similar with an instruction number, where it doesn't
    // actually define a new value, instead it moves a value. In case this
    // happens, discard.
    if (MTracker->LocIdxToIDNum[L] != Use.ID)
      continue;

    // If a different debug instruction defined the variable value / location
    // since the start of the block, don't materialize this use-before-def.
    if (!UseBeforeDefVariables.count(Use.Var))
      continue;

    PendingDbgValues.push_back(MTracker->emitLoc(L, Use.Var, Use.Properties));
  }
  flushDbgValues(pos, nullptr);
}

/// Helper to move created DBG_VALUEs into Transfers collection.
void flushDbgValues(MachineBasicBlock::iterator Pos, MachineBasicBlock *MBB) {
  if (PendingDbgValues.size() == 0)
    return;

  // Pick out the instruction start position.
  MachineBasicBlock::instr_iterator BundleStart;
  if (MBB && Pos == MBB->begin())
    BundleStart = MBB->instr_begin();
  else
    BundleStart = getBundleStart(Pos->getIterator());

  Transfers.push_back({BundleStart, MBB, PendingDbgValues});
  PendingDbgValues.clear();
}

bool isEntryValueVariable(const DebugVariable &Var,
                          const DIExpression *Expr) const {
  if (!Var.getVariable()->isParameter())
    return false;

  if (Var.getInlinedAt())
    return false;

  if (Expr->getNumElements() > 0)
    return false;

  return true;
}

bool isEntryValueValue(const ValueIDNum &Val) const {
  // Must be in entry block (block number zero), and be a PHI / live-in value.
  if (Val.getBlock() || !Val.isPHI())
    return false;

  // Entry values must enter in a register.
  if (MTracker->isSpill(Val.getLoc()))
    return false;

  Register SP = TLI->getStackPointerRegisterToSaveRestore();
  Register FP = TRI.getFrameRegister(MF);
  Register Reg = MTracker->LocIdxToLocID[Val.getLoc()];
  return Reg != SP && Reg != FP;
}

bool recoverAsEntryValue(const DebugVariable &Var, DbgValueProperties &Prop,
                         const ValueIDNum &Num) {
  // Is this variable location a candidate to be an entry value. First,
  // should we be trying this at all?
  if (!ShouldEmitDebugEntryValues)
    return false;

  // Is the variable appropriate for entry values (i.e., is a parameter).
  if (!isEntryValueVariable(Var, Prop.DIExpr))
    return false;

  // Is the value assigned to this variable still the entry value?
  if (!isEntryValueValue(Num))
    return false;

  // Emit a variable location using an entry value expression.
  DIExpression *NewExpr =
      DIExpression::prepend(Prop.DIExpr, DIExpression::EntryValue);
  Register Reg = MTracker->LocIdxToLocID[Num.getLoc()];
  MachineOperand MO = MachineOperand::CreateReg(Reg, false);
  MO.setIsDebug(true);

  PendingDbgValues.push_back(emitMOLoc(MO, Var, {NewExpr, Prop.Indirect}));
  return true;
}

/// Change a variable value after encountering a DBG_VALUE inside a block.
void redefVar(const MachineInstr &MI) {
  DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
                    MI.getDebugLoc()->getInlinedAt());
  DbgValueProperties Properties(MI);

  const MachineOperand &MO = MI.getOperand(0);

  // Ignore non-register locations, we don't transfer those.
  if (!MO.isReg() || MO.getReg() == 0) {
    auto It = ActiveVLocs.find(Var);
    if (It != ActiveVLocs.end()) {
      ActiveMLocs[It->second.Loc].erase(Var);
      ActiveVLocs.erase(It);
   }
    // Any use-before-defs no longer apply.
    UseBeforeDefVariables.erase(Var);
    return;
  }

  Register Reg = MO.getReg();
  LocIdx NewLoc = MTracker->getRegMLoc(Reg);
  redefVar(MI, Properties, NewLoc);
}

/// Handle a change in variable location within a block. Terminate the
/// variables current location, and record the value it now refers to, so
/// that we can detect location transfers later on.
void redefVar(const MachineInstr &MI, const DbgValueProperties &Properties,
              Optional<LocIdx> OptNewLoc) {
  DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
                    MI.getDebugLoc()->getInlinedAt());
  // Any use-before-defs no longer apply.
  UseBeforeDefVariables.erase(Var);

  // Erase any previous location,
  auto It = ActiveVLocs.find(Var);
  if (It != ActiveVLocs.end())
    ActiveMLocs[It->second.Loc].erase(Var);

  // If there _is_ no new location, all we had to do was erase.
  if (!OptNewLoc)
    return;
  LocIdx NewLoc = *OptNewLoc;

  // Check whether our local copy of values-by-location in #VarLocs is out of
  // date. Wipe old tracking data for the location if it's been clobbered in
  // the meantime.
  if (MTracker->getNumAtPos(NewLoc) != VarLocs[NewLoc.asU64()]) {
    for (auto &P : ActiveMLocs[NewLoc]) {
      ActiveVLocs.erase(P);
    }
    ActiveMLocs[NewLoc.asU64()].clear();
    VarLocs[NewLoc.asU64()] = MTracker->getNumAtPos(NewLoc);
  }

  ActiveMLocs[NewLoc].insert(Var);
  if (It == ActiveVLocs.end()) {
    ActiveVLocs.insert(
        std::make_pair(Var, LocAndProperties{NewLoc, Properties}));
  } else {
    It->second.Loc = NewLoc;
    It->second.Properties = Properties;
  }
}

/// Account for a location \p mloc being clobbered. Examine the variable
/// locations that will be terminated: and try to recover them by using
/// another location. Optionally, given \p MakeUndef, emit a DBG_VALUE to
/// explicitly terminate a location if it can't be recovered.
void clobberMloc(LocIdx MLoc, MachineBasicBlock::iterator Pos,
                 bool MakeUndef = true) {
  auto ActiveMLocIt = ActiveMLocs.find(MLoc);
  if (ActiveMLocIt == ActiveMLocs.end())
    return;

  // What was the old variable value?
  ValueIDNum OldValue = VarLocs[MLoc.asU64()];
  VarLocs[MLoc.asU64()] = ValueIDNum::EmptyValue;

  // Examine the remaining variable locations: if we can find the same value
  // again, we can recover the location.
  Optional<LocIdx> NewLoc = None;
  for (auto Loc : MTracker->locations())
    if (Loc.Value == OldValue)
      NewLoc = Loc.Idx;

  // If there is no location, and we weren't asked to make the variable
  // explicitly undef, then stop here.
  if (!NewLoc && !MakeUndef) {
    // Try and recover a few more locations with entry values.
    for (auto &Var : ActiveMLocIt->second) {
      auto &Prop = ActiveVLocs.find(Var)->second.Properties;
      recoverAsEntryValue(Var, Prop, OldValue);
    }
    flushDbgValues(Pos, nullptr);
    return;
  }

  // Examine all the variables based on this location.
  DenseSet<DebugVariable> NewMLocs;
  for (auto &Var : ActiveMLocIt->second) {
    auto ActiveVLocIt = ActiveVLocs.find(Var);
    // Re-state the variable location: if there's no replacement then NewLoc
    // is None and a $noreg DBG_VALUE will be created. Otherwise, a DBG_VALUE
    // identifying the alternative location will be emitted.
    const DIExpression *Expr = ActiveVLocIt->second.Properties.DIExpr;
    DbgValueProperties Properties(Expr, false);
    PendingDbgValues.push_back(MTracker->emitLoc(NewLoc, Var, Properties));

    // Update machine locations <=> variable locations maps. Defer updating
    // ActiveMLocs to avoid invalidaing the ActiveMLocIt iterator.
    if (!NewLoc) {
      ActiveVLocs.erase(ActiveVLocIt);
    } else {
      ActiveVLocIt->second.Loc = *NewLoc;
      NewMLocs.insert(Var);
    }
  }

  // Commit any deferred ActiveMLoc changes.
  if (!NewMLocs.empty())
    for (auto &Var : NewMLocs)
      ActiveMLocs[*NewLoc].insert(Var);

  // We lazily track what locations have which values; if we've found a new
  // location for the clobbered value, remember it.
  if (NewLoc)
    VarLocs[NewLoc->asU64()] = OldValue;

  flushDbgValues(Pos, nullptr);

  ActiveMLocIt->second.clear();
}

/// Transfer variables based on \p Src to be based on \p Dst. This handles
/// both register copies as well as spills and restores. Creates DBG_VALUEs
/// describing the movement.
void transferMlocs(LocIdx Src, LocIdx Dst, MachineBasicBlock::iterator Pos) {
  // Does Src still contain the value num we expect? If not, it's been
  // clobbered in the meantime, and our variable locations are stale.
  if (VarLocs[Src.asU64()] != MTracker->getNumAtPos(Src))
    return;

  // assert(ActiveMLocs[Dst].size() == 0);
  //^^^ Legitimate scenario on account of un-clobbered slot being assigned to?
  ActiveMLocs[Dst] = ActiveMLocs[Src];
  VarLocs[Dst.asU64()] = VarLocs[Src.asU64()];

  // For each variable based on Src; create a location at Dst.
  for (auto &Var : ActiveMLocs[Src]) {
    auto ActiveVLocIt = ActiveVLocs.find(Var);
    assert(ActiveVLocIt != ActiveVLocs.end())((void)0);
    ActiveVLocIt->second.Loc = Dst;

    assert(Dst != 0)((void)0);
    MachineInstr *MI =
        MTracker->emitLoc(Dst, Var, ActiveVLocIt->second.Properties);
    PendingDbgValues.push_back(MI);
  }
  ActiveMLocs[Src].clear();
  flushDbgValues(Pos, nullptr);

  // XXX XXX XXX "pretend to be old LDV" means dropping all tracking data
  // about the old location.
  if (EmulateOldLDV)
    VarLocs[Src.asU64()] = ValueIDNum::EmptyValue;
}

MachineInstrBuilder emitMOLoc(const MachineOperand &MO,
                              const DebugVariable &Var,
                              const DbgValueProperties &Properties) {
  DebugLoc DL = DILocation::get(Var.getVariable()->getContext(), 0, 0,
                                Var.getVariable()->getScope(),
                                const_cast<DILocation *>(Var.getInlinedAt()));
  auto MIB = BuildMI(MF, DL, TII->get(TargetOpcode::DBG_VALUE));
  MIB.add(MO);
  if (Properties.Indirect)
    MIB.addImm(0);
  else
    MIB.addReg(0);
  MIB.addMetadata(Var.getVariable());
  MIB.addMetadata(Properties.DIExpr);
  return MIB;
}
1414};

1416class InstrRefBasedLDV : public LDVImpl {
1417private:
using FragmentInfo = DIExpression::FragmentInfo;
using OptFragmentInfo = Optional<DIExpression::FragmentInfo>;

// Helper while building OverlapMap, a map of all fragments seen for a given
// DILocalVariable.
using VarToFragments =
    DenseMap<const DILocalVariable *, SmallSet<FragmentInfo, 4>>;

/// Machine location/value transfer function, a mapping of which locations
/// are assigned which new values.
using MLocTransferMap = std::map<LocIdx, ValueIDNum>;

/// Live in/out structure for the variable values: a per-block map of
/// variables to their values. XXX, better name?
using LiveIdxT =
    DenseMap<const MachineBasicBlock *, DenseMap<DebugVariable, DbgValue> *>;

using VarAndLoc = std::pair<DebugVariable, DbgValue>;

/// Type for a live-in value: the predecessor block, and its value.
using InValueT = std::pair<MachineBasicBlock *, DbgValue *>;

/// Vector (per block) of a collection (inner smallvector) of live-ins.
/// Used as the result type for the variable value dataflow problem.
using LiveInsT = SmallVector<SmallVector<VarAndLoc, 8>, 8>;

const TargetRegisterInfo *TRI;
const TargetInstrInfo *TII;
const TargetFrameLowering *TFI;
const MachineFrameInfo *MFI;
BitVector CalleeSavedRegs;
LexicalScopes LS;
TargetPassConfig *TPC;

/// Object to track machine locations as we step through a block. Could
/// probably be a field rather than a pointer, as it's always used.
MLocTracker *MTracker;

/// Number of the current block LiveDebugValues is stepping through.
unsigned CurBB;

/// Number of the current instruction LiveDebugValues is evaluating.
unsigned CurInst;

/// Variable tracker -- listens to DBG_VALUEs occurring as InstrRefBasedImpl
/// steps through a block. Reads the values at each location from the
/// MLocTracker object.
VLocTracker *VTracker;

/// Tracker for transfers, listens to DBG_VALUEs and transfers of values
/// between locations during stepping, creates new DBG_VALUEs when values move
/// location.
TransferTracker *TTracker;

/// Blocks which are artificial, i.e. blocks which exclusively contain
/// instructions without DebugLocs, or with line 0 locations.
SmallPtrSet<const MachineBasicBlock *, 16> ArtificialBlocks;

// Mapping of blocks to and from their RPOT order.
DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
DenseMap<unsigned, unsigned> BBNumToRPO;

/// Pair of MachineInstr, and its 1-based offset into the containing block.
using InstAndNum = std::pair<const MachineInstr *, unsigned>;
/// Map from debug instruction number to the MachineInstr labelled with that
/// number, and its location within the function. Used to transform
/// instruction numbers in DBG_INSTR_REFs into machine value numbers.
std::map<uint64_t, InstAndNum> DebugInstrNumToInstr;

/// Record of where we observed a DBG_PHI instruction.
class DebugPHIRecord {
public:
  uint64_t InstrNum;      ///< Instruction number of this DBG_PHI.
  MachineBasicBlock *MBB; ///< Block where DBG_PHI occurred.
  ValueIDNum ValueRead;   ///< The value number read by the DBG_PHI.
  LocIdx ReadLoc;         ///< Register/Stack location the DBG_PHI reads.

  operator unsigned() const { return InstrNum; }
};

/// Map from instruction numbers defined by DBG_PHIs to a record of what that
/// DBG_PHI read and where. Populated and edited during the machine value
/// location problem -- we use LLVMs SSA Updater to fix changes by
/// optimizations that destroy PHI instructions.
SmallVector<DebugPHIRecord, 32> DebugPHINumToValue;

// Map of overlapping variable fragments.
OverlapMap OverlapFragments;
VarToFragments SeenFragments;

/// Tests whether this instruction is a spill to a stack slot.
bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF);

/// Decide if @MI is a spill instruction and return true if it is. We use 2
/// criteria to make this decision:
/// - Is this instruction a store to a spill slot?
/// - Is there a register operand that is both used and killed?
/// TODO: Store optimization can fold spills into other stores (including
/// other spills). We do not handle this yet (more than one memory operand).
bool isLocationSpill(const MachineInstr &MI, MachineFunction *MF,
                     unsigned &Reg);

/// If a given instruction is identified as a spill, return the spill slot
/// and set \p Reg to the spilled register.
Optional<SpillLoc> isRestoreInstruction(const MachineInstr &MI,
                                        MachineFunction *MF, unsigned &Reg);

/// Given a spill instruction, extract the register and offset used to
/// address the spill slot in a target independent way.
SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI);

/// Observe a single instruction while stepping through a block.
void process(MachineInstr &MI, ValueIDNum **MLiveOuts = nullptr,
             ValueIDNum **MLiveIns = nullptr);

/// Examines whether \p MI is a DBG_VALUE and notifies trackers.
/// \returns true if MI was recognized and processed.
bool transferDebugValue(const MachineInstr &MI);

/// Examines whether \p MI is a DBG_INSTR_REF and notifies trackers.
/// \returns true if MI was recognized and processed.
bool transferDebugInstrRef(MachineInstr &MI, ValueIDNum **MLiveOuts,
                           ValueIDNum **MLiveIns);

/// Stores value-information about where this PHI occurred, and what
/// instruction number is associated with it.
/// \returns true if MI was recognized and processed.
bool transferDebugPHI(MachineInstr &MI);

/// Examines whether \p MI is copy instruction, and notifies trackers.
/// \returns true if MI was recognized and processed.
bool transferRegisterCopy(MachineInstr &MI);

/// Examines whether \p MI is stack spill or restore  instruction, and
/// notifies trackers. \returns true if MI was recognized and processed.
bool transferSpillOrRestoreInst(MachineInstr &MI);

/// Examines \p MI for any registers that it defines, and notifies trackers.
void transferRegisterDef(MachineInstr &MI);

/// Copy one location to the other, accounting for movement of subregisters
/// too.
void performCopy(Register Src, Register Dst);

void accumulateFragmentMap(MachineInstr &MI);

/// Determine the machine value number referred to by (potentially several)
/// DBG_PHI instructions. Block duplication and tail folding can duplicate
/// DBG_PHIs, shifting the position where values in registers merge, and
/// forming another mini-ssa problem to solve.
/// \p Here the position of a DBG_INSTR_REF seeking a machine value number
/// \p InstrNum Debug instruction number defined by DBG_PHI instructions.
/// \returns The machine value number at position Here, or None.
Optional<ValueIDNum> resolveDbgPHIs(MachineFunction &MF,
                                    ValueIDNum **MLiveOuts,
                                    ValueIDNum **MLiveIns, MachineInstr &Here,
                                    uint64_t InstrNum);

/// Step through the function, recording register definitions and movements
/// in an MLocTracker. Convert the observations into a per-block transfer
/// function in \p MLocTransfer, suitable for using with the machine value
/// location dataflow problem.
void
produceMLocTransferFunction(MachineFunction &MF,
                            SmallVectorImpl<MLocTransferMap> &MLocTransfer,
                            unsigned MaxNumBlocks);

/// Solve the machine value location dataflow problem. Takes as input the
/// transfer functions in \p MLocTransfer. Writes the output live-in and
/// live-out arrays to the (initialized to zero) multidimensional arrays in
/// \p MInLocs and \p MOutLocs. The outer dimension is indexed by block
/// number, the inner by LocIdx.
void mlocDataflow(ValueIDNum **MInLocs, ValueIDNum **MOutLocs,
                  SmallVectorImpl<MLocTransferMap> &MLocTransfer);

/// Perform a control flow join (lattice value meet) of the values in machine
/// locations at \p MBB. Follows the algorithm described in the file-comment,
/// reading live-outs of predecessors from \p OutLocs, the current live ins
/// from \p InLocs, and assigning the newly computed live ins back into
/// \p InLocs. \returns two bools -- the first indicates whether a change
/// was made, the second whether a lattice downgrade occurred. If the latter
/// is true, revisiting this block is necessary.
std::tuple<bool, bool>
mlocJoin(MachineBasicBlock &MBB,
         SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
         ValueIDNum **OutLocs, ValueIDNum *InLocs);

/// Solve the variable value dataflow problem, for a single lexical scope.
/// Uses the algorithm from the file comment to resolve control flow joins,
/// although there are extra hacks, see vlocJoin. Reads the
/// locations of values from the \p MInLocs and \p MOutLocs arrays (see
/// mlocDataflow) and reads the variable values transfer function from
/// \p AllTheVlocs. Live-in and Live-out variable values are stored locally,
/// with the live-ins permanently stored to \p Output once the fixedpoint is
/// reached.
/// \p VarsWeCareAbout contains a collection of the variables in \p Scope
/// that we should be tracking.
/// \p AssignBlocks contains the set of blocks that aren't in \p Scope, but
/// which do contain DBG_VALUEs, which VarLocBasedImpl tracks locations
/// through.
void vlocDataflow(const LexicalScope *Scope, const DILocation *DILoc,
                  const SmallSet<DebugVariable, 4> &VarsWeCareAbout,
                  SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks,
                  LiveInsT &Output, ValueIDNum **MOutLocs,
                  ValueIDNum **MInLocs,
                  SmallVectorImpl<VLocTracker> &AllTheVLocs);

/// Compute the live-ins to a block, considering control flow merges according
/// to the method in the file comment. Live out and live in variable values
/// are stored in \p VLOCOutLocs and \p VLOCInLocs. The live-ins for \p MBB
/// are computed and stored into \p VLOCInLocs. \returns true if the live-ins
/// are modified.
/// \p InLocsT Output argument, storage for calculated live-ins.
/// \returns two bools -- the first indicates whether a change
/// was made, the second whether a lattice downgrade occurred. If the latter
/// is true, revisiting this block is necessary.
std::tuple<bool, bool>
vlocJoin(MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs,
         SmallPtrSet<const MachineBasicBlock *, 16> *VLOCVisited,
         unsigned BBNum, const SmallSet<DebugVariable, 4> &AllVars,
         ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
         SmallPtrSet<const MachineBasicBlock *, 8> &InScopeBlocks,
         SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore,
         DenseMap<DebugVariable, DbgValue> &InLocsT);

/// Continue exploration of the variable-value lattice, as explained in the
/// file-level comment. \p OldLiveInLocation contains the current
/// exploration position, from which we need to descend further. \p Values
/// contains the set of live-in values, \p CurBlockRPONum the RPO number of
/// the current block, and \p CandidateLocations a set of locations that
/// should be considered as PHI locations, if we reach the bottom of the
/// lattice. \returns true if we should downgrade; the value is the agreeing
/// value number in a non-backedge predecessor.
bool vlocDowngradeLattice(const MachineBasicBlock &MBB,
                          const DbgValue &OldLiveInLocation,
                          const SmallVectorImpl<InValueT> &Values,
                          unsigned CurBlockRPONum);

/// For the given block and live-outs feeding into it, try to find a
/// machine location where they all join. If a solution for all predecessors
/// can't be found, a location where all non-backedge-predecessors join
/// will be returned instead. While this method finds a join location, this
/// says nothing as to whether it should be used.
/// \returns Pair of value ID if found, and true when the correct value
/// is available on all predecessor edges, or false if it's only available
/// for non-backedge predecessors.
std::tuple<Optional<ValueIDNum>, bool>
pickVPHILoc(MachineBasicBlock &MBB, const DebugVariable &Var,
            const LiveIdxT &LiveOuts, ValueIDNum **MOutLocs,
            ValueIDNum **MInLocs,
            const SmallVectorImpl<MachineBasicBlock *> &BlockOrders);

/// Given the solutions to the two dataflow problems, machine value locations
/// in \p MInLocs and live-in variable values in \p SavedLiveIns, runs the
/// TransferTracker class over the function to produce live-in and transfer
/// DBG_VALUEs, then inserts them. Groups of DBG_VALUEs are inserted in the
/// order given by AllVarsNumbering -- this could be any stable order, but
/// right now "order of appearence in function, when explored in RPO", so
/// that we can compare explictly against VarLocBasedImpl.
void emitLocations(MachineFunction &MF, LiveInsT SavedLiveIns,
                   ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
                   DenseMap<DebugVariable, unsigned> &AllVarsNumbering,
                   const TargetPassConfig &TPC);

/// Boilerplate computation of some initial sets, artifical blocks and
/// RPOT block ordering.
void initialSetup(MachineFunction &MF);

bool ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) override;

1689public:
/// Default construct and initialize the pass.
InstrRefBasedLDV();

LLVM_DUMP_METHOD__attribute__((noinline))
void dump_mloc_transfer(const MLocTransferMap &mloc_transfer) const;

bool isCalleeSaved(LocIdx L) {
  unsigned Reg = MTracker->LocIdxToLocID[L];
  for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
    if (CalleeSavedRegs.test(*RAI))
      return true;
  return false;
}
1703};

1705} // end anonymous namespace

1707//===----------------------------------------------------------------------===//
1708//            Implementation
1709//===----------------------------------------------------------------------===//

1711ValueIDNum ValueIDNum::EmptyValue = {UINT_MAX(2147483647 *2U +1U), UINT_MAX(2147483647 *2U +1U), UINT_MAX(2147483647 *2U +1U)};

1713/// Default construct and initialize the pass.
1714InstrRefBasedLDV::InstrRefBasedLDV() {}

1716//===----------------------------------------------------------------------===//
1717//            Debug Range Extension Implementation
1718//===----------------------------------------------------------------------===//

1720#ifndef NDEBUG1
1721// Something to restore in the future.
1722// void InstrRefBasedLDV::printVarLocInMBB(..)
1723#endif

1725SpillLoc
1726InstrRefBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
assert(MI.hasOneMemOperand() &&((void)0)
       "Spill instruction does not have exactly one memory operand?")((void)0);
auto MMOI = MI.memoperands_begin();
const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
assert(PVal->kind() == PseudoSourceValue::FixedStack &&((void)0)
       "Inconsistent memory operand in spill instruction")((void)0);
int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
const MachineBasicBlock *MBB = MI.getParent();
Register Reg;
StackOffset Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg);
return {Reg, Offset};
1738}

1740/// End all previous ranges related to @MI and start a new range from @MI
1741/// if it is a DBG_VALUE instr.
1742bool InstrRefBasedLDV::transferDebugValue(const MachineInstr &MI) {
if (!MI.isDebugValue())
  return false;

const DILocalVariable *Var = MI.getDebugVariable();
const DIExpression *Expr = MI.getDebugExpression();
const DILocation *DebugLoc = MI.getDebugLoc();
const DILocation *InlinedAt = DebugLoc->getInlinedAt();
assert(Var->isValidLocationForIntrinsic(DebugLoc) &&((void)0)
       "Expected inlined-at fields to agree")((void)0);

DebugVariable V(Var, Expr, InlinedAt);
DbgValueProperties Properties(MI);

// If there are no instructions in this lexical scope, do no location tracking
// at all, this variable shouldn't get a legitimate location range.
auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get());
if (Scope == nullptr)
  return true; // handled it; by doing nothing

const MachineOperand &MO = MI.getOperand(0);

// MLocTracker needs to know that this register is read, even if it's only
// read by a debug inst.
if (MO.isReg() && MO.getReg() != 0)
  (void)MTracker->readReg(MO.getReg());

// If we're preparing for the second analysis (variables), the machine value
// locations are already solved, and we report this DBG_VALUE and the value
// it refers to to VLocTracker.
if (VTracker) {
  if (MO.isReg()) {
    // Feed defVar the new variable location, or if this is a
    // DBG_VALUE $noreg, feed defVar None.
    if (MO.getReg())
      VTracker->defVar(MI, Properties, MTracker->readReg(MO.getReg()));
    else
      VTracker->defVar(MI, Properties, None);
  } else if (MI.getOperand(0).isImm() || MI.getOperand(0).isFPImm() ||
             MI.getOperand(0).isCImm()) {
    VTracker->defVar(MI, MI.getOperand(0));
  }
}

// If performing final tracking of transfers, report this variable definition
// to the TransferTracker too.
if (TTracker)
  TTracker->redefVar(MI);
return true;
1791}

1793bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI,
                                           ValueIDNum **MLiveOuts,
                                           ValueIDNum **MLiveIns) {
if (!MI.isDebugRef())
  return false;

// Only handle this instruction when we are building the variable value
// transfer function.
if (!VTracker)
  return false;

unsigned InstNo = MI.getOperand(0).getImm();
unsigned OpNo = MI.getOperand(1).getImm();

const DILocalVariable *Var = MI.getDebugVariable();
const DIExpression *Expr = MI.getDebugExpression();
const DILocation *DebugLoc = MI.getDebugLoc();
const DILocation *InlinedAt = DebugLoc->getInlinedAt();
assert(Var->isValidLocationForIntrinsic(DebugLoc) &&((void)0)
       "Expected inlined-at fields to agree")((void)0);

DebugVariable V(Var, Expr, InlinedAt);

auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get());
if (Scope == nullptr)
  return true; // Handled by doing nothing. This variable is never in scope.

const MachineFunction &MF = *MI.getParent()->getParent();

// Various optimizations may have happened to the value during codegen,
// recorded in the value substitution table. Apply any substitutions to
// the instruction / operand number in this DBG_INSTR_REF, and collect
// any subregister extractions performed during optimization.

// Create dummy substitution with Src set, for lookup.
auto SoughtSub =
    MachineFunction::DebugSubstitution({InstNo, OpNo}, {0, 0}, 0);

SmallVector<unsigned, 4> SeenSubregs;
auto LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub);
while (LowerBoundIt != MF.DebugValueSubstitutions.end() &&
       LowerBoundIt->Src == SoughtSub.Src) {
  std::tie(InstNo, OpNo) = LowerBoundIt->Dest;
  SoughtSub.Src = LowerBoundIt->Dest;
  if (unsigned Subreg = LowerBoundIt->Subreg)
    SeenSubregs.push_back(Subreg);
  LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub);
}

// Default machine value number is <None> -- if no instruction defines
// the corresponding value, it must have been optimized out.
Optional<ValueIDNum> NewID = None;

// Try to lookup the instruction number, and find the machine value number
// that it defines. It could be an instruction, or a PHI.
auto InstrIt = DebugInstrNumToInstr.find(InstNo);
auto PHIIt = std::lower_bound(DebugPHINumToValue.begin(),
                              DebugPHINumToValue.end(), InstNo);
if (InstrIt != DebugInstrNumToInstr.end()) {
  const MachineInstr &TargetInstr = *InstrIt->second.first;
  uint64_t BlockNo = TargetInstr.getParent()->getNumber();

  // Pick out the designated operand.
  assert(OpNo < TargetInstr.getNumOperands())((void)0);
  const MachineOperand &MO = TargetInstr.getOperand(OpNo);

  // Today, this can only be a register.
  assert(MO.isReg() && MO.isDef())((void)0);

  unsigned LocID = MTracker->getLocID(MO.getReg(), false);
  LocIdx L = MTracker->LocIDToLocIdx[LocID];
  NewID = ValueIDNum(BlockNo, InstrIt->second.second, L);
} else if (PHIIt != DebugPHINumToValue.end() && PHIIt->InstrNum == InstNo) {
  // It's actually a PHI value. Which value it is might not be obvious, use
  // the resolver helper to find out.
  NewID = resolveDbgPHIs(*MI.getParent()->getParent(), MLiveOuts, MLiveIns,
                         MI, InstNo);
}

// Apply any subregister extractions, in reverse. We might have seen code
// like this:
//    CALL64 @foo, implicit-def $rax
//    %0:gr64 = COPY $rax
//    %1:gr32 = COPY %0.sub_32bit
//    %2:gr16 = COPY %1.sub_16bit
//    %3:gr8  = COPY %2.sub_8bit
// In which case each copy would have been recorded as a substitution with
// a subregister qualifier. Apply those qualifiers now.
if (NewID && !SeenSubregs.empty()) {
  unsigned Offset = 0;
  unsigned Size = 0;

  // Look at each subregister that we passed through, and progressively
  // narrow in, accumulating any offsets that occur. Substitutions should
  // only ever be the same or narrower width than what they read from;
  // iterate in reverse order so that we go from wide to small.
  for (unsigned Subreg : reverse(SeenSubregs)) {
    unsigned ThisSize = TRI->getSubRegIdxSize(Subreg);
    unsigned ThisOffset = TRI->getSubRegIdxOffset(Subreg);
    Offset += ThisOffset;
    Size = (Size == 0) ? ThisSize : std::min(Size, ThisSize);
  }

  // If that worked, look for an appropriate subregister with the register
  // where the define happens. Don't look at values that were defined during
  // a stack write: we can't currently express register locations within
  // spills.
  LocIdx L = NewID->getLoc();
  if (NewID && !MTracker->isSpill(L)) {
    // Find the register class for the register where this def happened.
    // FIXME: no index for this?
    Register Reg = MTracker->LocIdxToLocID[L];
    const TargetRegisterClass *TRC = nullptr;
    for (auto *TRCI : TRI->regclasses())
      if (TRCI->contains(Reg))
        TRC = TRCI;
    assert(TRC && "Couldn't find target register class?")((void)0);

    // If the register we have isn't the right size or in the right place,
    // Try to find a subregister inside it.
    unsigned MainRegSize = TRI->getRegSizeInBits(*TRC);
    if (Size != MainRegSize || Offset) {
      // Enumerate all subregisters, searching.
      Register NewReg = 0;
      for (MCSubRegIterator SRI(Reg, TRI, false); SRI.isValid(); ++SRI) {
        unsigned Subreg = TRI->getSubRegIndex(Reg, *SRI);
        unsigned SubregSize = TRI->getSubRegIdxSize(Subreg);
        unsigned SubregOffset = TRI->getSubRegIdxOffset(Subreg);
        if (SubregSize == Size && SubregOffset == Offset) {
          NewReg = *SRI;
          break;
        }
      }

      // If we didn't find anything: there's no way to express our value.
      if (!NewReg) {
        NewID = None;
      } else {
        // Re-state the value as being defined within the subregister
        // that we found.
        LocIdx NewLoc = MTracker->lookupOrTrackRegister(NewReg);
        NewID = ValueIDNum(NewID->getBlock(), NewID->getInst(), NewLoc);
      }
    }
  } else {
    // If we can't handle subregisters, unset the new value.
    NewID = None;
  }
}

// We, we have a value number or None. Tell the variable value tracker about
// it. The rest of this LiveDebugValues implementation acts exactly the same
// for DBG_INSTR_REFs as DBG_VALUEs (just, the former can refer to values that
// aren't immediately available).
DbgValueProperties Properties(Expr, false);
VTracker->defVar(MI, Properties, NewID);

// If we're on the final pass through the function, decompose this INSTR_REF
// into a plain DBG_VALUE.
if (!TTracker)
  return true;

// Pick a location for the machine value number, if such a location exists.
// (This information could be stored in TransferTracker to make it faster).
Optional<LocIdx> FoundLoc = None;
for (auto Location : MTracker->locations()) {
  LocIdx CurL = Location.Idx;
  ValueIDNum ID = MTracker->LocIdxToIDNum[CurL];
  if (NewID && ID == NewID) {
    // If this is the first location with that value, pick it. Otherwise,
    // consider whether it's a "longer term" location.
    if (!FoundLoc) {
      FoundLoc = CurL;
      continue;
    }

    if (MTracker->isSpill(CurL))
      FoundLoc = CurL; // Spills are a longer term location.
    else if (!MTracker->isSpill(*FoundLoc) &&
             !MTracker->isSpill(CurL) &&
             !isCalleeSaved(*FoundLoc) &&
             isCalleeSaved(CurL))
      FoundLoc = CurL; // Callee saved regs are longer term than normal.
  }
}

// Tell transfer tracker that the variable value has changed.
TTracker->redefVar(MI, Properties, FoundLoc);

// If there was a value with no location; but the value is defined in a
// later instruction in this block, this is a block-local use-before-def.
if (!FoundLoc && NewID && NewID->getBlock() == CurBB &&
    NewID->getInst() > CurInst)
  TTracker->addUseBeforeDef(V, {MI.getDebugExpression(), false}, *NewID);

// Produce a DBG_VALUE representing what this DBG_INSTR_REF meant.
// This DBG_VALUE is potentially a $noreg / undefined location, if
// FoundLoc is None.
// (XXX -- could morph the DBG_INSTR_REF in the future).
MachineInstr *DbgMI = MTracker->emitLoc(FoundLoc, V, Properties);
TTracker->PendingDbgValues.push_back(DbgMI);
TTracker->flushDbgValues(MI.getIterator(), nullptr);
return true;
1996}

1998bool InstrRefBasedLDV::transferDebugPHI(MachineInstr &MI) {
if (!MI.isDebugPHI())
  return false;

// Analyse these only when solving the machine value location problem.
if (VTracker || TTracker)
  return true;

// First operand is the value location, either a stack slot or register.
// Second is the debug instruction number of the original PHI.
const MachineOperand &MO = MI.getOperand(0);
unsigned InstrNum = MI.getOperand(1).getImm();

if (MO.isReg()) {
  // The value is whatever's currently in the register. Read and record it,
  // to be analysed later.
  Register Reg = MO.getReg();
  ValueIDNum Num = MTracker->readReg(Reg);
  auto PHIRec = DebugPHIRecord(
      {InstrNum, MI.getParent(), Num, MTracker->lookupOrTrackRegister(Reg)});
  DebugPHINumToValue.push_back(PHIRec);
} else {
  // The value is whatever's in this stack slot.
  assert(MO.isFI())((void)0);
  unsigned FI = MO.getIndex();

  // If the stack slot is dead, then this was optimized away.
  // FIXME: stack slot colouring should account for slots that get merged.
  if (MFI->isDeadObjectIndex(FI))
    return true;

  // Identify this spill slot.
  Register Base;
  StackOffset Offs = TFI->getFrameIndexReference(*MI.getMF(), FI, Base);
  SpillLoc SL = {Base, Offs};
  Optional<ValueIDNum> Num = MTracker->readSpill(SL);

  if (!Num)
    // Nothing ever writes to this slot. Curious, but nothing we can do.
    return true;

  // Record this DBG_PHI for later analysis.
  auto DbgPHI = DebugPHIRecord(
      {InstrNum, MI.getParent(), *Num, *MTracker->getSpillMLoc(SL)});
  DebugPHINumToValue.push_back(DbgPHI);
}

return true;
2046}

2048void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) {
// Meta Instructions do not affect the debug liveness of any register they
// define.
if (MI.isImplicitDef()) {
  // Except when there's an implicit def, and the location it's defining has
  // no value number. The whole point of an implicit def is to announce that
  // the register is live, without be specific about it's value. So define
  // a value if there isn't one already.
  ValueIDNum Num = MTracker->readReg(MI.getOperand(0).getReg());
  // Has a legitimate value -> ignore the implicit def.
  if (Num.getLoc() != 0)
    return;
  // Otherwise, def it here.
} else if (MI.isMetaInstruction())
  return;

MachineFunction *MF = MI.getMF();
const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
Register SP = TLI->getStackPointerRegisterToSaveRestore();

// Find the regs killed by MI, and find regmasks of preserved regs.
// Max out the number of statically allocated elements in `DeadRegs`, as this
// prevents fallback to std::set::count() operations.
SmallSet<uint32_t, 32> DeadRegs;
SmallVector<const uint32_t *, 4> RegMasks;
SmallVector<const MachineOperand *, 4> RegMaskPtrs;
for (const MachineOperand &MO : MI.operands()) {
  // Determine whether the operand is a register def.
  if (MO.isReg() && MO.isDef() && MO.getReg() &&
      Register::isPhysicalRegister(MO.getReg()) &&
      !(MI.isCall() && MO.getReg() == SP)) {
    // Remove ranges of all aliased registers.
    for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
      // FIXME: Can we break out of this loop early if no insertion occurs?
      DeadRegs.insert(*RAI);
  } else if (MO.isRegMask()) {
    RegMasks.push_back(MO.getRegMask());
    RegMaskPtrs.push_back(&MO);
  }
}

// Tell MLocTracker about all definitions, of regmasks and otherwise.
for (uint32_t DeadReg : DeadRegs)
  MTracker->defReg(DeadReg, CurBB, CurInst);

for (auto *MO : RegMaskPtrs)
  MTracker->writeRegMask(MO, CurBB, CurInst);

if (!TTracker)
  return;

// When committing variable values to locations: tell transfer tracker that
// we've clobbered things. It may be able to recover the variable from a
// different location.

// Inform TTracker about any direct clobbers.
for (uint32_t DeadReg : DeadRegs) {
  LocIdx Loc = MTracker->lookupOrTrackRegister(DeadReg);
  TTracker->clobberMloc(Loc, MI.getIterator(), false);
}

// Look for any clobbers performed by a register mask. Only test locations
// that are actually being tracked.
for (auto L : MTracker->locations()) {
  // Stack locations can't be clobbered by regmasks.
  if (MTracker->isSpill(L.Idx))
    continue;

  Register Reg = MTracker->LocIdxToLocID[L.Idx];
  for (auto *MO : RegMaskPtrs)
    if (MO->clobbersPhysReg(Reg))
      TTracker->clobberMloc(L.Idx, MI.getIterator(), false);
}
2121}

2123void InstrRefBasedLDV::performCopy(Register SrcRegNum, Register DstRegNum) {
ValueIDNum SrcValue = MTracker->readReg(SrcRegNum);

MTracker->setReg(DstRegNum, SrcValue);

// In all circumstances, re-def the super registers. It's definitely a new
// value now. This doesn't uniquely identify the composition of subregs, for
// example, two identical values in subregisters composed in different
// places would not get equal value numbers.
for (MCSuperRegIterator SRI(DstRegNum, TRI); SRI.isValid(); ++SRI)
  MTracker->defReg(*SRI, CurBB, CurInst);

// If we're emulating VarLocBasedImpl, just define all the subregisters.
// DBG_VALUEs of them will expect to be tracked from the DBG_VALUE, not
// through prior copies.
if (EmulateOldLDV) {
  for (MCSubRegIndexIterator DRI(DstRegNum, TRI); DRI.isValid(); ++DRI)
    MTracker->defReg(DRI.getSubReg(), CurBB, CurInst);
  return;
}

// Otherwise, actually copy subregisters from one location to another.
// XXX: in addition, any subregisters of DstRegNum that don't line up with
// the source register should be def'd.
for (MCSubRegIndexIterator SRI(SrcRegNum, TRI); SRI.isValid(); ++SRI) {
  unsigned SrcSubReg = SRI.getSubReg();
  unsigned SubRegIdx = SRI.getSubRegIndex();
  unsigned DstSubReg = TRI->getSubReg(DstRegNum, SubRegIdx);
  if (!DstSubReg)
    continue;

  // Do copy. There are two matching subregisters, the source value should
  // have been def'd when the super-reg was, the latter might not be tracked
  // yet.
  // This will force SrcSubReg to be tracked, if it isn't yet.
  (void)MTracker->readReg(SrcSubReg);
  LocIdx SrcL = MTracker->getRegMLoc(SrcSubReg);
  assert(SrcL.asU64())((void)0);
  (void)MTracker->readReg(DstSubReg);
  LocIdx DstL = MTracker->getRegMLoc(DstSubReg);
  assert(DstL.asU64())((void)0);
  (void)DstL;
  ValueIDNum CpyValue = {SrcValue.getBlock(), SrcValue.getInst(), SrcL};

  MTracker->setReg(DstSubReg, CpyValue);
}
2169}

2171bool InstrRefBasedLDV::isSpillInstruction(const MachineInstr &MI,
                                        MachineFunction *MF) {
// TODO: Handle multiple stores folded into one.
if (!MI.hasOneMemOperand())
  return false;

if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII))
  return false; // This is not a spill instruction, since no valid size was
                // returned from either function.

return true;
2182}

2184bool InstrRefBasedLDV::isLocationSpill(const MachineInstr &MI,
                                     MachineFunction *MF, unsigned &Reg) {
if (!isSpillInstruction(MI, MF))
  return false;

int FI;
Reg = TII->isStoreToStackSlotPostFE(MI, FI);
return Reg != 0;
2192}

2194Optional<SpillLoc>
2195InstrRefBasedLDV::isRestoreInstruction(const MachineInstr &MI,
                                     MachineFunction *MF, unsigned &Reg) {
if (!MI.hasOneMemOperand())
  return None;

// FIXME: Handle folded restore instructions with more than one memory
// operand.
if (MI.getRestoreSize(TII)) {
  Reg = MI.getOperand(0).getReg();
  return extractSpillBaseRegAndOffset(MI);
}
return None;
2207}

2209bool InstrRefBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI) {
// XXX -- it's too difficult to implement VarLocBasedImpl's  stack location
// limitations under the new model. Therefore, when comparing them, compare
// versions that don't attempt spills or restores at all.
if (EmulateOldLDV)
  return false;

MachineFunction *MF = MI.getMF();
unsigned Reg;
Optional<SpillLoc> Loc;

LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump();)do { } while (false);

// First, if there are any DBG_VALUEs pointing at a spill slot that is
// written to, terminate that variable location. The value in memory
// will have changed. DbgEntityHistoryCalculator doesn't try to detect this.
if (isSpillInstruction(MI, MF)) {
  Loc = extractSpillBaseRegAndOffset(MI);

  if (TTracker) {
    Optional<LocIdx> MLoc = MTracker->getSpillMLoc(*Loc);
    if (MLoc) {
      // Un-set this location before clobbering, so that we don't salvage
      // the variable location back to the same place.
      MTracker->setMLoc(*MLoc, ValueIDNum::EmptyValue);
      TTracker->clobberMloc(*MLoc, MI.getIterator());
    }
  }
}

// Try to recognise spill and restore instructions that may transfer a value.
if (isLocationSpill(MI, MF, Reg)) {
  Loc = extractSpillBaseRegAndOffset(MI);
  auto ValueID = MTracker->readReg(Reg);

  // If the location is empty, produce a phi, signify it's the live-in value.
  if (ValueID.getLoc() == 0)
    ValueID = {CurBB, 0, MTracker->getRegMLoc(Reg)};

  MTracker->setSpill(*Loc, ValueID);
  auto OptSpillLocIdx = MTracker->getSpillMLoc(*Loc);
  assert(OptSpillLocIdx && "Spill slot set but has no LocIdx?")((void)0);
  LocIdx SpillLocIdx = *OptSpillLocIdx;

  // Tell TransferTracker about this spill, produce DBG_VALUEs for it.
  if (TTracker)
    TTracker->transferMlocs(MTracker->getRegMLoc(Reg), SpillLocIdx,
                            MI.getIterator());
} else {
  if (!(Loc = isRestoreInstruction(MI, MF, Reg)))
    return false;

  // Is there a value to be restored?
  auto OptValueID = MTracker->readSpill(*Loc);
  if (OptValueID) {
    ValueIDNum ValueID = *OptValueID;
    LocIdx SpillLocIdx = *MTracker->getSpillMLoc(*Loc);
    // XXX -- can we recover sub-registers of this value? Until we can, first
    // overwrite all defs of the register being restored to.
    for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
      MTracker->defReg(*RAI, CurBB, CurInst);

    // Now override the reg we're restoring to.
    MTracker->setReg(Reg, ValueID);

    // Report this restore to the transfer tracker too.
    if (TTracker)
      TTracker->transferMlocs(SpillLocIdx, MTracker->getRegMLoc(Reg),
                              MI.getIterator());
  } else {
    // There isn't anything in the location; not clear if this is a code path
    // that still runs. Def this register anyway just in case.
    for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
      MTracker->defReg(*RAI, CurBB, CurInst);

    // Force the spill slot to be tracked.
    LocIdx L = MTracker->getOrTrackSpillLoc(*Loc);

    // Set the restored value to be a machine phi number, signifying that it's
    // whatever the spills live-in value is in this block. Definitely has
    // a LocIdx due to the setSpill above.
    ValueIDNum ValueID = {CurBB, 0, L};
    MTracker->setReg(Reg, ValueID);
    MTracker->setSpill(*Loc, ValueID);
  }
}
return true;
2296}

2298bool InstrRefBasedLDV::transferRegisterCopy(MachineInstr &MI) {
auto DestSrc = TII->isCopyInstr(MI);
if (!DestSrc)
  return false;

const MachineOperand *DestRegOp = DestSrc->Destination;
const MachineOperand *SrcRegOp = DestSrc->Source;

auto isCalleeSavedReg = [&](unsigned Reg) {
  for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
    if (CalleeSavedRegs.test(*RAI))
      return true;
  return false;
};

Register SrcReg = SrcRegOp->getReg();
Register DestReg = DestRegOp->getReg();

// Ignore identity copies. Yep, these make it as far as LiveDebugValues.
if (SrcReg == DestReg)
  return true;

// For emulating VarLocBasedImpl:
// We want to recognize instructions where destination register is callee
// saved register. If register that could be clobbered by the call is
// included, there would be a great chance that it is going to be clobbered
// soon. It is more likely that previous register, which is callee saved, is
// going to stay unclobbered longer, even if it is killed.
//
// For InstrRefBasedImpl, we can track multiple locations per value, so
// ignore this condition.
if (EmulateOldLDV && !isCalleeSavedReg(DestReg))
  return false;

// InstrRefBasedImpl only followed killing copies.
if (EmulateOldLDV && !SrcRegOp->isKill())
  return false;

// Copy MTracker info, including subregs if available.
InstrRefBasedLDV::performCopy(SrcReg, DestReg);

// Only produce a transfer of DBG_VALUE within a block where old LDV
// would have. We might make use of the additional value tracking in some
// other way, later.
if (TTracker && isCalleeSavedReg(DestReg) && SrcRegOp->isKill())
  TTracker->transferMlocs(MTracker->getRegMLoc(SrcReg),
                          MTracker->getRegMLoc(DestReg), MI.getIterator());

// VarLocBasedImpl would quit tracking the old location after copying.
if (EmulateOldLDV && SrcReg != DestReg)
  MTracker->defReg(SrcReg, CurBB, CurInst);

// Finally, the copy might have clobbered variables based on the destination
// register. Tell TTracker about it, in case a backup location exists.
if (TTracker) {
  for (MCRegAliasIterator RAI(DestReg, TRI, true); RAI.isValid(); ++RAI) {
    LocIdx ClobberedLoc = MTracker->getRegMLoc(*RAI);
    TTracker->clobberMloc(ClobberedLoc, MI.getIterator(), false);
  }
}

return true;
2360}

2362/// Accumulate a mapping between each DILocalVariable fragment and other
2363/// fragments of that DILocalVariable which overlap. This reduces work during
2364/// the data-flow stage from "Find any overlapping fragments" to "Check if the
2365/// known-to-overlap fragments are present".
2366/// \param MI A previously unprocessed DEBUG_VALUE instruction to analyze for
2367///           fragment usage.
2368void InstrRefBasedLDV::accumulateFragmentMap(MachineInstr &MI) {
DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(),
                    MI.getDebugLoc()->getInlinedAt());
FragmentInfo ThisFragment = MIVar.getFragmentOrDefault();

// If this is the first sighting of this variable, then we are guaranteed
// there are currently no overlapping fragments either. Initialize the set
// of seen fragments, record no overlaps for the current one, and return.
auto SeenIt = SeenFragments.find(MIVar.getVariable());
if (SeenIt == SeenFragments.end()) {
  SmallSet<FragmentInfo, 4> OneFragment;
  OneFragment.insert(ThisFragment);
  SeenFragments.insert({MIVar.getVariable(), OneFragment});

  OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}});
  return;
}

// If this particular Variable/Fragment pair already exists in the overlap
// map, it has already been accounted for.
auto IsInOLapMap =
    OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}});
if (!IsInOLapMap.second)
  return;

auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;
auto &AllSeenFragments = SeenIt->second;

// Otherwise, examine all other seen fragments for this variable, with "this"
// fragment being a previously unseen fragment. Record any pair of
// overlapping fragments.
for (auto &ASeenFragment : AllSeenFragments) {
  // Does this previously seen fragment overlap?
  if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) {
    // Yes: Mark the current fragment as being overlapped.
    ThisFragmentsOverlaps.push_back(ASeenFragment);
    // Mark the previously seen fragment as being overlapped by the current
    // one.
    auto ASeenFragmentsOverlaps =
        OverlapFragments.find({MIVar.getVariable(), ASeenFragment});
    assert(ASeenFragmentsOverlaps != OverlapFragments.end() &&((void)0)
           "Previously seen var fragment has no vector of overlaps")((void)0);
    ASeenFragmentsOverlaps->second.push_back(ThisFragment);
  }
}

AllSeenFragments.insert(ThisFragment);
2415}

2417void InstrRefBasedLDV::process(MachineInstr &MI, ValueIDNum **MLiveOuts,
                             ValueIDNum **MLiveIns) {
// Try to interpret an MI as a debug or transfer instruction. Only if it's
// none of these should we interpret it's register defs as new value
// definitions.
if (transferDebugValue(MI))
  return;
if (transferDebugInstrRef(MI, MLiveOuts, MLiveIns))
  return;
if (transferDebugPHI(MI))
  return;
if (transferRegisterCopy(MI))
  return;
if (transferSpillOrRestoreInst(MI))
  return;
transferRegisterDef(MI);
2433}

2435void InstrRefBasedLDV::produceMLocTransferFunction(
  MachineFunction &MF, SmallVectorImpl<MLocTransferMap> &MLocTransfer,
  unsigned MaxNumBlocks) {
// Because we try to optimize around register mask operands by ignoring regs
// that aren't currently tracked, we set up something ugly for later: RegMask
// operands that are seen earlier than the first use of a register, still need
// to clobber that register in the transfer function. But this information
// isn't actively recorded. Instead, we track each RegMask used in each block,
// and accumulated the clobbered but untracked registers in each block into
// the following bitvector. Later, if new values are tracked, we can add
// appropriate clobbers.
SmallVector<BitVector, 32> BlockMasks;
BlockMasks.resize(MaxNumBlocks);

// Reserve one bit per register for the masks described above.
unsigned BVWords = MachineOperand::getRegMaskSize(TRI->getNumRegs());
for (auto &BV : BlockMasks)
  BV.resize(TRI->getNumRegs(), true);

// Step through all instructions and inhale the transfer function.
for (auto &MBB : MF) {
  // Object fields that are read by trackers to know where we are in the
  // function.
  CurBB = MBB.getNumber();
  CurInst = 1;

  // Set all machine locations to a PHI value. For transfer function
  // production only, this signifies the live-in value to the block.
  MTracker->reset();
  MTracker->setMPhis(CurBB);

  // Step through each instruction in this block.
  for (auto &MI : MBB) {
    process(MI);
    // Also accumulate fragment map.
    if (MI.isDebugValue())
      accumulateFragmentMap(MI);

    // Create a map from the instruction number (if present) to the
    // MachineInstr and its position.
    if (uint64_t InstrNo = MI.peekDebugInstrNum()) {
      auto InstrAndPos = std::make_pair(&MI, CurInst);
      auto InsertResult =
          DebugInstrNumToInstr.insert(std::make_pair(InstrNo, InstrAndPos));

      // There should never be duplicate instruction numbers.
      assert(InsertResult.second)((void)0);
      (void)InsertResult;
    }

    ++CurInst;
  }

  // Produce the transfer function, a map of machine location to new value. If
  // any machine location has the live-in phi value from the start of the
  // block, it's live-through and doesn't need recording in the transfer
  // function.
  for (auto Location : MTracker->locations()) {
    LocIdx Idx = Location.Idx;
    ValueIDNum &P = Location.Value;
    if (P.isPHI() && P.getLoc() == Idx.asU64())
      continue;

    // Insert-or-update.
    auto &TransferMap = MLocTransfer[CurBB];
    auto Result = TransferMap.insert(std::make_pair(Idx.asU64(), P));
    if (!Result.second)
      Result.first->second = P;
  }

  // Accumulate any bitmask operands into the clobberred reg mask for this
  // block.
  for (auto &P : MTracker->Masks) {
    BlockMasks[CurBB].clearBitsNotInMask(P.first->getRegMask(), BVWords);
  }
}

// Compute a bitvector of all the registers that are tracked in this block.
const TargetLowering *TLI = MF.getSubtarget().getTargetLowering();
Register SP = TLI->getStackPointerRegisterToSaveRestore();
BitVector UsedRegs(TRI->getNumRegs());
for (auto Location : MTracker->locations()) {
  unsigned ID = MTracker->LocIdxToLocID[Location.Idx];
  if (ID >= TRI->getNumRegs() || ID == SP)
    continue;
  UsedRegs.set(ID);
}

// Check that any regmask-clobber of a register that gets tracked, is not
// live-through in the transfer function. It needs to be clobbered at the
// very least.
for (unsigned int I = 0; I < MaxNumBlocks; ++I) {
  BitVector &BV = BlockMasks[I];
  BV.flip();
  BV &= UsedRegs;
  // This produces all the bits that we clobber, but also use. Check that
  // they're all clobbered or at least set in the designated transfer
  // elem.
  for (unsigned Bit : BV.set_bits()) {
    unsigned ID = MTracker->getLocID(Bit, false);
    LocIdx Idx = MTracker->LocIDToLocIdx[ID];
    auto &TransferMap = MLocTransfer[I];

    // Install a value representing the fact that this location is effectively
    // written to in this block. As there's no reserved value, instead use
    // a value number that is never generated. Pick the value number for the
    // first instruction in the block, def'ing this location, which we know
    // this block never used anyway.
    ValueIDNum NotGeneratedNum = ValueIDNum(I, 1, Idx);
    auto Result =
      TransferMap.insert(std::make_pair(Idx.asU64(), NotGeneratedNum));
    if (!Result.second) {
      ValueIDNum &ValueID = Result.first->second;
      if (ValueID.getBlock() == I && ValueID.isPHI())
        // It was left as live-through. Set it to clobbered.
        ValueID = NotGeneratedNum;
    }
  }
}
2554}

2556std::tuple<bool, bool>
2557InstrRefBasedLDV::mlocJoin(MachineBasicBlock &MBB,
                         SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
                         ValueIDNum **OutLocs, ValueIDNum *InLocs) {
LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n")do { } while (false);
bool Changed = false;
bool DowngradeOccurred = false;

// Collect predecessors that have been visited. Anything that hasn't been
// visited yet is a backedge on the first iteration, and the meet of it's
// lattice value for all locations will be unaffected.
SmallVector<const MachineBasicBlock *, 8> BlockOrders;
for (auto Pred : MBB.predecessors()) {
  if (Visited.count(Pred)) {
    BlockOrders.push_back(Pred);
  }
}

// Visit predecessors in RPOT order.
auto Cmp = [&](const MachineBasicBlock *A, const MachineBasicBlock *B) {
  return BBToOrder.find(A)->second < BBToOrder.find(B)->second;
};
llvm::sort(BlockOrders, Cmp);

// Skip entry block.
if (BlockOrders.size() == 0)
  return std::tuple<bool, bool>(false, false);

// Step through all machine locations, then look at each predecessor and
// detect disagreements.
unsigned ThisBlockRPO = BBToOrder.find(&MBB)->second;
for (auto Location : MTracker->locations()) {
  LocIdx Idx = Location.Idx;
  // Pick out the first predecessors live-out value for this location. It's
  // guaranteed to be not a backedge, as we order by RPO.
  ValueIDNum BaseVal = OutLocs[BlockOrders[0]->getNumber()][Idx.asU64()];

  // Some flags for whether there's a disagreement, and whether it's a
  // disagreement with a backedge or not.
  bool Disagree = false;
  bool NonBackEdgeDisagree = false;

  // Loop around everything that wasn't 'base'.
  for (unsigned int I = 1; I < BlockOrders.size(); ++I) {
    auto *MBB = BlockOrders[I];
    if (BaseVal != OutLocs[MBB->getNumber()][Idx.asU64()]) {
      // Live-out of a predecessor disagrees with the first predecessor.
      Disagree = true;

      // Test whether it's a disagreemnt in the backedges or not.
      if (BBToOrder.find(MBB)->second < ThisBlockRPO) // might be self b/e
        NonBackEdgeDisagree = true;
    }
  }

  bool OverRide = false;
  if (Disagree && !NonBackEdgeDisagree) {
    // Only the backedges disagree. Consider demoting the livein
    // lattice value, as per the file level comment. The value we consider
    // demoting to is the value that the non-backedge predecessors agree on.
    // The order of values is that non-PHIs are \top, a PHI at this block
    // \bot, and phis between the two are ordered by their RPO number.
    // If there's no agreement, or we've already demoted to this PHI value
    // before, replace with a PHI value at this block.

    // Calculate order numbers: zero means normal def, nonzero means RPO
    // number.
    unsigned BaseBlockRPONum = BBNumToRPO[BaseVal.getBlock()] + 1;
    if (!BaseVal.isPHI())
      BaseBlockRPONum = 0;

    ValueIDNum &InLocID = InLocs[Idx.asU64()];
    unsigned InLocRPONum = BBNumToRPO[InLocID.getBlock()] + 1;
    if (!InLocID.isPHI())
      InLocRPONum = 0;

    // Should we ignore the disagreeing backedges, and override with the
    // value the other predecessors agree on (in "base")?
    unsigned ThisBlockRPONum = BBNumToRPO[MBB.getNumber()] + 1;
    if (BaseBlockRPONum > InLocRPONum && BaseBlockRPONum < ThisBlockRPONum) {
      // Override.
      OverRide = true;
      DowngradeOccurred = true;
    }
  }
  // else: if we disagree in the non-backedges, then this is definitely
  // a control flow merge where different values merge. Make it a PHI.

  // Generate a phi...
  ValueIDNum PHI = {(uint64_t)MBB.getNumber(), 0, Idx};
  ValueIDNum NewVal = (Disagree && !OverRide) ? PHI : BaseVal;
  if (InLocs[Idx.asU64()] != NewVal) {
    Changed |= true;
    InLocs[Idx.asU64()] = NewVal;
  }
}

// TODO: Reimplement NumInserted and NumRemoved.
return std::tuple<bool, bool>(Changed, DowngradeOccurred);
2655}

2657void InstrRefBasedLDV::mlocDataflow(
  ValueIDNum **MInLocs, ValueIDNum **MOutLocs,
  SmallVectorImpl<MLocTransferMap> &MLocTransfer) {
std::priority_queue<unsigned int, std::vector<unsigned int>,
                    std::greater<unsigned int>>
    Worklist, Pending;

// We track what is on the current and pending worklist to avoid inserting
// the same thing twice. We could avoid this with a custom priority queue,
// but this is probably not worth it.
SmallPtrSet<MachineBasicBlock *, 16> OnPending, OnWorklist;

// Initialize worklist with every block to be visited.
for (unsigned int I = 0; I < BBToOrder.size(); ++I) {
7
←
Assuming the condition is false→
8
←
Loop condition is false. Execution continues on line 2675→
  Worklist.push(I);
  OnWorklist.insert(OrderToBB[I]);
}

MTracker->reset();

// Set inlocs for entry block -- each as a PHI at the entry block. Represents
// the incoming value to the function.
MTracker->setMPhis(0);
for (auto Location : MTracker->locations())
  MInLocs[0][Location.Idx.asU64()] = Location.Value;
9
←
Use of zero-allocated memory

SmallPtrSet<const MachineBasicBlock *, 16> Visited;
while (!Worklist.empty() || !Pending.empty()) {
  // Vector for storing the evaluated block transfer function.
  SmallVector<std::pair<LocIdx, ValueIDNum>, 32> ToRemap;

  while (!Worklist.empty()) {
    MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
    CurBB = MBB->getNumber();
    Worklist.pop();

    // Join the values in all predecessor blocks.
    bool InLocsChanged, DowngradeOccurred;
    std::tie(InLocsChanged, DowngradeOccurred) =
        mlocJoin(*MBB, Visited, MOutLocs, MInLocs[CurBB]);
    InLocsChanged |= Visited.insert(MBB).second;

    // If a downgrade occurred, book us in for re-examination on the next
    // iteration.
    if (DowngradeOccurred && OnPending.insert(MBB).second)
      Pending.push(BBToOrder[MBB]);

    // Don't examine transfer function if we've visited this loc at least
    // once, and inlocs haven't changed.
    if (!InLocsChanged)
      continue;

    // Load the current set of live-ins into MLocTracker.
    MTracker->loadFromArray(MInLocs[CurBB], CurBB);

    // Each element of the transfer function can be a new def, or a read of
    // a live-in value. Evaluate each element, and store to "ToRemap".
    ToRemap.clear();
    for (auto &P : MLocTransfer[CurBB]) {
      if (P.second.getBlock() == CurBB && P.second.isPHI()) {
        // This is a movement of whatever was live in. Read it.
        ValueIDNum NewID = MTracker->getNumAtPos(P.second.getLoc());
        ToRemap.push_back(std::make_pair(P.first, NewID));
      } else {
        // It's a def. Just set it.
        assert(P.second.getBlock() == CurBB)((void)0);
        ToRemap.push_back(std::make_pair(P.first, P.second));
      }
    }

    // Commit the transfer function changes into mloc tracker, which
    // transforms the contents of the MLocTracker into the live-outs.
    for (auto &P : ToRemap)
      MTracker->setMLoc(P.first, P.second);

    // Now copy out-locs from mloc tracker into out-loc vector, checking
    // whether changes have occurred. These changes can have come from both
    // the transfer function, and mlocJoin.
    bool OLChanged = false;
    for (auto Location : MTracker->locations()) {
      OLChanged |= MOutLocs[CurBB][Location.Idx.asU64()] != Location.Value;
      MOutLocs[CurBB][Location.Idx.asU64()] = Location.Value;
    }

    MTracker->reset();

    // No need to examine successors again if out-locs didn't change.
    if (!OLChanged)
      continue;

    // All successors should be visited: put any back-edges on the pending
    // list for the next dataflow iteration, and any other successors to be
    // visited this iteration, if they're not going to be already.
    for (auto s : MBB->successors()) {
      // Does branching to this successor represent a back-edge?
      if (BBToOrder[s] > BBToOrder[MBB]) {
        // No: visit it during this dataflow iteration.
        if (OnWorklist.insert(s).second)
          Worklist.push(BBToOrder[s]);
      } else {
        // Yes: visit it on the next iteration.
        if (OnPending.insert(s).second)
          Pending.push(BBToOrder[s]);
      }
    }
  }

  Worklist.swap(Pending);
  std::swap(OnPending, OnWorklist);
  OnPending.clear();
  // At this point, pending must be empty, since it was just the empty
  // worklist
  assert(Pending.empty() && "Pending should be empty")((void)0);
}

// Once all the live-ins don't change on mlocJoin(), we've reached a
// fixedpoint.
2774}

2776bool InstrRefBasedLDV::vlocDowngradeLattice(
  const MachineBasicBlock &MBB, const DbgValue &OldLiveInLocation,
  const SmallVectorImpl<InValueT> &Values, unsigned CurBlockRPONum) {
// Ranking value preference: see file level comment, the highest rank is
// a plain def, followed by PHI values in reverse post-order. Numerically,
// we assign all defs the rank '0', all PHIs their blocks RPO number plus
// one, and consider the lowest value the highest ranked.
int OldLiveInRank = BBNumToRPO[OldLiveInLocation.ID.getBlock()] + 1;
if (!OldLiveInLocation.ID.isPHI())
  OldLiveInRank = 0;

// Allow any unresolvable conflict to be over-ridden.
if (OldLiveInLocation.Kind == DbgValue::NoVal) {
  // Although if it was an unresolvable conflict from _this_ block, then
  // all other seeking of downgrades and PHIs must have failed before hand.
  if (OldLiveInLocation.BlockNo == (unsigned)MBB.getNumber())
    return false;
  OldLiveInRank = INT_MIN(-2147483647 -1);
}

auto &InValue = *Values[0].second;

if (InValue.Kind == DbgValue::Const || InValue.Kind == DbgValue::NoVal)
  return false;

unsigned ThisRPO = BBNumToRPO[InValue.ID.getBlock()];
int ThisRank = ThisRPO + 1;
if (!InValue.ID.isPHI())
  ThisRank = 0;

// Too far down the lattice?
if (ThisRPO >= CurBlockRPONum)
  return false;

// Higher in the lattice than what we've already explored?
if (ThisRank <= OldLiveInRank)
  return false;

return true;
2815}

2817std::tuple<Optional<ValueIDNum>, bool> InstrRefBasedLDV::pickVPHILoc(
  MachineBasicBlock &MBB, const DebugVariable &Var, const LiveIdxT &LiveOuts,
  ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
  const SmallVectorImpl<MachineBasicBlock *> &BlockOrders) {
// Collect a set of locations from predecessor where its live-out value can
// be found.
SmallVector<SmallVector<LocIdx, 4>, 8> Locs;
unsigned NumLocs = MTracker->getNumLocs();
unsigned BackEdgesStart = 0;

for (auto p : BlockOrders) {
  // Pick out where backedges start in the list of predecessors. Relies on
  // BlockOrders being sorted by RPO.
  if (BBToOrder[p] < BBToOrder[&MBB])
    ++BackEdgesStart;

  // For each predecessor, create a new set of locations.
  Locs.resize(Locs.size() + 1);
  unsigned ThisBBNum = p->getNumber();
  auto LiveOutMap = LiveOuts.find(p);
  if (LiveOutMap == LiveOuts.end())
    // This predecessor isn't in scope, it must have no live-in/live-out
    // locations.
    continue;

  auto It = LiveOutMap->second->find(Var);
  if (It == LiveOutMap->second->end())
    // There's no value recorded for this variable in this predecessor,
    // leave an empty set of locations.
    continue;

  const DbgValue &OutVal = It->second;

  if (OutVal.Kind == DbgValue::Const || OutVal.Kind == DbgValue::NoVal)
    // Consts and no-values cannot have locations we can join on.
    continue;

  assert(OutVal.Kind == DbgValue::Proposed || OutVal.Kind == DbgValue::Def)((void)0);
  ValueIDNum ValToLookFor = OutVal.ID;

  // Search the live-outs of the predecessor for the specified value.
  for (unsigned int I = 0; I < NumLocs; ++I) {
    if (MOutLocs[ThisBBNum][I] == ValToLookFor)
      Locs.back().push_back(LocIdx(I));
  }
}

// If there were no locations at all, return an empty result.
if (Locs.empty())
  return std::tuple<Optional<ValueIDNum>, bool>(None, false);

// Lambda for seeking a common location within a range of location-sets.
using LocsIt = SmallVector<SmallVector<LocIdx, 4>, 8>::iterator;
auto SeekLocation =
    [&Locs](llvm::iterator_range<LocsIt> SearchRange) -> Optional<LocIdx> {
  // Starting with the first set of locations, take the intersection with
  // subsequent sets.
  SmallVector<LocIdx, 4> base = Locs[0];
  for (auto &S : SearchRange) {
    SmallVector<LocIdx, 4> new_base;
    std::set_intersection(base.begin(), base.end(), S.begin(), S.end(),
                          std::inserter(new_base, new_base.begin()));
    base = new_base;
  }
  if (base.empty())
    return None;

  // We now have a set of LocIdxes that contain the right output value in
  // each of the predecessors. Pick the lowest; if there's a register loc,
  // that'll be it.
  return *base.begin();
};

// Search for a common location for all predecessors. If we can't, then fall
// back to only finding a common location between non-backedge predecessors.
bool ValidForAllLocs = true;
auto TheLoc = SeekLocation(Locs);
if (!TheLoc) {
  ValidForAllLocs = false;
  TheLoc =
      SeekLocation(make_range(Locs.begin(), Locs.begin() + BackEdgesStart));
}

if (!TheLoc)
  return std::tuple<Optional<ValueIDNum>, bool>(None, false);

// Return a PHI-value-number for the found location.
LocIdx L = *TheLoc;
ValueIDNum PHIVal = {(unsigned)MBB.getNumber(), 0, L};
return std::tuple<Optional<ValueIDNum>, bool>(PHIVal, ValidForAllLocs);
2907}

2909std::tuple<bool, bool> InstrRefBasedLDV::vlocJoin(
  MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs,
  SmallPtrSet<const MachineBasicBlock *, 16> *VLOCVisited, unsigned BBNum,
  const SmallSet<DebugVariable, 4> &AllVars, ValueIDNum **MOutLocs,
  ValueIDNum **MInLocs,
  SmallPtrSet<const MachineBasicBlock *, 8> &InScopeBlocks,
  SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore,
  DenseMap<DebugVariable, DbgValue> &InLocsT) {
bool DowngradeOccurred = false;

// To emulate VarLocBasedImpl, process this block if it's not in scope but
// _does_ assign a variable value. No live-ins for this scope are transferred
// in though, so we can return immediately.
if (InScopeBlocks.count(&MBB) == 0 && !ArtificialBlocks.count(&MBB)) {
  if (VLOCVisited)
    return std::tuple<bool, bool>(true, false);
  return std::tuple<bool, bool>(false, false);
}

LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n")do { } while (false);
bool Changed = false;

// Find any live-ins computed in a prior iteration.
auto ILSIt = VLOCInLocs.find(&MBB);
assert(ILSIt != VLOCInLocs.end())((void)0);
auto &ILS = *ILSIt->second;

// Order predecessors by RPOT order, for exploring them in that order.
SmallVector<MachineBasicBlock *, 8> BlockOrders(MBB.predecessors());

auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
  return BBToOrder[A] < BBToOrder[B];
};

llvm::sort(BlockOrders, Cmp);

unsigned CurBlockRPONum = BBToOrder[&MBB];

// Force a re-visit to loop heads in the first dataflow iteration.
// FIXME: if we could "propose" Const values this wouldn't be needed,
// because they'd need to be confirmed before being emitted.
if (!BlockOrders.empty() &&
    BBToOrder[BlockOrders[BlockOrders.size() - 1]] >= CurBlockRPONum &&
    VLOCVisited)
  DowngradeOccurred = true;

auto ConfirmValue = [&InLocsT](const DebugVariable &DV, DbgValue VR) {
  auto Result = InLocsT.insert(std::make_pair(DV, VR));
  (void)Result;
  assert(Result.second)((void)0);
};

auto ConfirmNoVal = [&ConfirmValue, &MBB](const DebugVariable &Var, const DbgValueProperties &Properties) {
  DbgValue NoLocPHIVal(MBB.getNumber(), Properties, DbgValue::NoVal);

  ConfirmValue(Var, NoLocPHIVal);
};

// Attempt to join the values for each variable.
for (auto &Var : AllVars) {
  // Collect all the DbgValues for this variable.
  SmallVector<InValueT, 8> Values;
  bool Bail = false;
  unsigned BackEdgesStart = 0;
  for (auto p : BlockOrders) {
    // If the predecessor isn't in scope / to be explored, we'll never be
    // able to join any locations.
    if (!BlocksToExplore.contains(p)) {
      Bail = true;
      break;
    }

    // Don't attempt to handle unvisited predecessors: they're implicitly
    // "unknown"s in the lattice.
    if (VLOCVisited && !VLOCVisited->count(p))
      continue;

    // If the predecessors OutLocs is absent, there's not much we can do.
    auto OL = VLOCOutLocs.find(p);
    if (OL == VLOCOutLocs.end()) {
      Bail = true;
      break;
    }

    // No live-out value for this predecessor also means we can't produce
    // a joined value.
    auto VIt = OL->second->find(Var);
    if (VIt == OL->second->end()) {
      Bail = true;
      break;
    }

    // Keep track of where back-edges begin in the Values vector. Relies on
    // BlockOrders being sorted by RPO.
    unsigned ThisBBRPONum = BBToOrder[p];
    if (ThisBBRPONum < CurBlockRPONum)
      ++BackEdgesStart;

    Values.push_back(std::make_pair(p, &VIt->second));
  }

  // If there were no values, or one of the predecessors couldn't have a
  // value, then give up immediately. It's not safe to produce a live-in
  // value.
  if (Bail || Values.size() == 0)
    continue;

  // Enumeration identifying the current state of the predecessors values.
  enum {
    Unset = 0,
    Agreed,       // All preds agree on the variable value.
    PropDisagree, // All preds agree, but the value kind is Proposed in some.
    BEDisagree,   // Only back-edges disagree on variable value.
    PHINeeded,    // Non-back-edge predecessors have conflicing values.
    NoSolution    // Conflicting Value metadata makes solution impossible.
  } OurState = Unset;

  // All (non-entry) blocks have at least one non-backedge predecessor.
  // Pick the variable value from the first of these, to compare against
  // all others.
  const DbgValue &FirstVal = *Values[0].second;
  const ValueIDNum &FirstID = FirstVal.ID;

  // Scan for variable values that can't be resolved: if they have different
  // DIExpressions, different indirectness, or are mixed constants /
  // non-constants.
  for (auto &V : Values) {
    if (V.second->Properties != FirstVal.Properties)
      OurState = NoSolution;
    if (V.second->Kind == DbgValue::Const && FirstVal.Kind != DbgValue::Const)
      OurState = NoSolution;
  }

  // Flags diagnosing _how_ the values disagree.
  bool NonBackEdgeDisagree = false;
  bool DisagreeOnPHINess = false;
  bool IDDisagree = false;
  bool Disagree = false;
  if (OurState == Unset) {
    for (auto &V : Values) {
      if (*V.second == FirstVal)
        continue; // No disagreement.

      Disagree = true;

      // Flag whether the value number actually diagrees.
      if (V.second->ID != FirstID)
        IDDisagree = true;

      // Distinguish whether disagreement happens in backedges or not.
      // Relies on Values (and BlockOrders) being sorted by RPO.
      unsigned ThisBBRPONum = BBToOrder[V.first];
      if (ThisBBRPONum < CurBlockRPONum)
        NonBackEdgeDisagree = true;

      // Is there a difference in whether the value is definite or only
      // proposed?
      if (V.second->Kind != FirstVal.Kind &&
          (V.second->Kind == DbgValue::Proposed ||
           V.second->Kind == DbgValue::Def) &&
          (FirstVal.Kind == DbgValue::Proposed ||
           FirstVal.Kind == DbgValue::Def))
        DisagreeOnPHINess = true;
    }

    // Collect those flags together and determine an overall state for
    // what extend the predecessors agree on a live-in value.
    if (!Disagree)
      OurState = Agreed;
    else if (!IDDisagree && DisagreeOnPHINess)
      OurState = PropDisagree;
    else if (!NonBackEdgeDisagree)
      OurState = BEDisagree;
    else
      OurState = PHINeeded;
  }

  // An extra indicator: if we only disagree on whether the value is a
  // Def, or proposed, then also flag whether that disagreement happens
  // in backedges only.
  bool PropOnlyInBEs = Disagree && !IDDisagree && DisagreeOnPHINess &&
                       !NonBackEdgeDisagree && FirstVal.Kind == DbgValue::Def;

  const auto &Properties = FirstVal.Properties;

  auto OldLiveInIt = ILS.find(Var);
  const DbgValue *OldLiveInLocation =
      (OldLiveInIt != ILS.end()) ? &OldLiveInIt->second : nullptr;

  bool OverRide = false;
  if (OurState == BEDisagree && OldLiveInLocation) {
    // Only backedges disagree: we can consider downgrading. If there was a
    // previous live-in value, use it to work out whether the current
    // incoming value represents a lattice downgrade or not.
    OverRide =
        vlocDowngradeLattice(MBB, *OldLiveInLocation, Values, CurBlockRPONum);
  }

  // Use the current state of predecessor agreement and other flags to work
  // out what to do next. Possibilities include:
  //  * Accept a value all predecessors agree on, or accept one that
  //    represents a step down the exploration lattice,
  //  * Use a PHI value number, if one can be found,
  //  * Propose a PHI value number, and see if it gets confirmed later,
  //  * Emit a 'NoVal' value, indicating we couldn't resolve anything.
  if (OurState == Agreed) {
    // Easiest solution: all predecessors agree on the variable value.
    ConfirmValue(Var, FirstVal);
  } else if (OurState == BEDisagree && OverRide) {
    // Only backedges disagree, and the other predecessors have produced
    // a new live-in value further down the exploration lattice.
    DowngradeOccurred = true;
    ConfirmValue(Var, FirstVal);
  } else if (OurState == PropDisagree) {
    // Predecessors agree on value, but some say it's only a proposed value.
    // Propagate it as proposed: unless it was proposed in this block, in
    // which case we're able to confirm the value.
    if (FirstID.getBlock() == (uint64_t)MBB.getNumber() && FirstID.isPHI()) {
      ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Def));
    } else if (PropOnlyInBEs) {
      // If only backedges disagree, a higher (in RPO) block confirmed this
      // location, and we need to propagate it into this loop.
      ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Def));
    } else {
      // Otherwise; a Def meeting a Proposed is still a Proposed.
      ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Proposed));
    }
  } else if ((OurState == PHINeeded || OurState == BEDisagree)) {
    // Predecessors disagree and can't be downgraded: this can only be
    // solved with a PHI. Use pickVPHILoc to go look for one.
    Optional<ValueIDNum> VPHI;
    bool AllEdgesVPHI = false;
    std::tie(VPHI, AllEdgesVPHI) =
        pickVPHILoc(MBB, Var, VLOCOutLocs, MOutLocs, MInLocs, BlockOrders);

    if (VPHI && AllEdgesVPHI) {
      // There's a PHI value that's valid for all predecessors -- we can use
      // it. If any of the non-backedge predecessors have proposed values
      // though, this PHI is also only proposed, until the predecessors are
      // confirmed.
      DbgValue::KindT K = DbgValue::Def;
      for (unsigned int I = 0; I < BackEdgesStart; ++I)
        if (Values[I].second->Kind == DbgValue::Proposed)
          K = DbgValue::Proposed;

      ConfirmValue(Var, DbgValue(*VPHI, Properties, K));
    } else if (VPHI) {
      // There's a PHI value, but it's only legal for backedges. Leave this
      // as a proposed PHI value: it might come back on the backedges,
      // and allow us to confirm it in the future.
      DbgValue NoBEValue = DbgValue(*VPHI, Properties, DbgValue::Proposed);
      ConfirmValue(Var, NoBEValue);
    } else {
      ConfirmNoVal(Var, Properties);
    }
  } else {
    // Otherwise: we don't know. Emit a "phi but no real loc" phi.
    ConfirmNoVal(Var, Properties);
  }
}

// Store newly calculated in-locs into VLOCInLocs, if they've changed.
Changed = ILS != InLocsT;
if (Changed)
  ILS = InLocsT;

return std::tuple<bool, bool>(Changed, DowngradeOccurred);
3176}

3178void InstrRefBasedLDV::vlocDataflow(
  const LexicalScope *Scope, const DILocation *DILoc,
  const SmallSet<DebugVariable, 4> &VarsWeCareAbout,
  SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, LiveInsT &Output,
  ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
  SmallVectorImpl<VLocTracker> &AllTheVLocs) {
// This method is much like mlocDataflow: but focuses on a single
// LexicalScope at a time. Pick out a set of blocks and variables that are
// to have their value assignments solved, then run our dataflow algorithm
// until a fixedpoint is reached.
std::priority_queue<unsigned int, std::vector<unsigned int>,
                    std::greater<unsigned int>>
    Worklist, Pending;
SmallPtrSet<MachineBasicBlock *, 16> OnWorklist, OnPending;

// The set of blocks we'll be examining.
SmallPtrSet<const MachineBasicBlock *, 8> BlocksToExplore;

// The order in which to examine them (RPO).
SmallVector<MachineBasicBlock *, 8> BlockOrders;

// RPO ordering function.
auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
  return BBToOrder[A] < BBToOrder[B];
};

LS.getMachineBasicBlocks(DILoc, BlocksToExplore);

// A separate container to distinguish "blocks we're exploring" versus
// "blocks that are potentially in scope. See comment at start of vlocJoin.
SmallPtrSet<const MachineBasicBlock *, 8> InScopeBlocks = BlocksToExplore;

// Old LiveDebugValues tracks variable locations that come out of blocks
// not in scope, where DBG_VALUEs occur. This is something we could
// legitimately ignore, but lets allow it for now.
if (EmulateOldLDV)
  BlocksToExplore.insert(AssignBlocks.begin(), AssignBlocks.end());

// We also need to propagate variable values through any artificial blocks
// that immediately follow blocks in scope.
DenseSet<const MachineBasicBlock *> ToAdd;

// Helper lambda: For a given block in scope, perform a depth first search
// of all the artificial successors, adding them to the ToAdd collection.
auto AccumulateArtificialBlocks =
    [this, &ToAdd, &BlocksToExplore,
     &InScopeBlocks](const MachineBasicBlock *MBB) {
      // Depth-first-search state: each node is a block and which successor
      // we're currently exploring.
      SmallVector<std::pair<const MachineBasicBlock *,
                            MachineBasicBlock::const_succ_iterator>,
                  8>
          DFS;

      // Find any artificial successors not already tracked.
      for (auto *succ : MBB->successors()) {
        if (BlocksToExplore.count(succ) || InScopeBlocks.count(succ))
          continue;
        if (!ArtificialBlocks.count(succ))
          continue;
        DFS.push_back(std::make_pair(succ, succ->succ_begin()));
        ToAdd.insert(succ);
      }

      // Search all those blocks, depth first.
      while (!DFS.empty()) {
        const MachineBasicBlock *CurBB = DFS.back().first;
        MachineBasicBlock::const_succ_iterator &CurSucc = DFS.back().second;
        // Walk back if we've explored this blocks successors to the end.
        if (CurSucc == CurBB->succ_end()) {
          DFS.pop_back();
          continue;
        }

        // If the current successor is artificial and unexplored, descend into
        // it.
        if (!ToAdd.count(*CurSucc) && ArtificialBlocks.count(*CurSucc)) {
          DFS.push_back(std::make_pair(*CurSucc, (*CurSucc)->succ_begin()));
          ToAdd.insert(*CurSucc);
          continue;
        }

        ++CurSucc;
      }
    };

// Search in-scope blocks and those containing a DBG_VALUE from this scope
// for artificial successors.
for (auto *MBB : BlocksToExplore)
  AccumulateArtificialBlocks(MBB);
for (auto *MBB : InScopeBlocks)
  AccumulateArtificialBlocks(MBB);

BlocksToExplore.insert(ToAdd.begin(), ToAdd.end());
InScopeBlocks.insert(ToAdd.begin(), ToAdd.end());

// Single block scope: not interesting! No propagation at all. Note that
// this could probably go above ArtificialBlocks without damage, but
// that then produces output differences from original-live-debug-values,
// which propagates from a single block into many artificial ones.
if (BlocksToExplore.size() == 1)
  return;

// Picks out relevants blocks RPO order and sort them.
for (auto *MBB : BlocksToExplore)
  BlockOrders.push_back(const_cast<MachineBasicBlock *>(MBB));

llvm::sort(BlockOrders, Cmp);
unsigned NumBlocks = BlockOrders.size();

// Allocate some vectors for storing the live ins and live outs. Large.
SmallVector<DenseMap<DebugVariable, DbgValue>, 32> LiveIns, LiveOuts;
LiveIns.resize(NumBlocks);
LiveOuts.resize(NumBlocks);

// Produce by-MBB indexes of live-in/live-outs, to ease lookup within
// vlocJoin.
LiveIdxT LiveOutIdx, LiveInIdx;
LiveOutIdx.reserve(NumBlocks);
LiveInIdx.reserve(NumBlocks);
for (unsigned I = 0; I < NumBlocks; ++I) {
  LiveOutIdx[BlockOrders[I]] = &LiveOuts[I];
  LiveInIdx[BlockOrders[I]] = &LiveIns[I];
}

for (auto *MBB : BlockOrders) {
  Worklist.push(BBToOrder[MBB]);
  OnWorklist.insert(MBB);
}

// Iterate over all the blocks we selected, propagating variable values.
bool FirstTrip = true;
SmallPtrSet<const MachineBasicBlock *, 16> VLOCVisited;
while (!Worklist.empty() || !Pending.empty()) {
  while (!Worklist.empty()) {
    auto *MBB = OrderToBB[Worklist.top()];
    CurBB = MBB->getNumber();
    Worklist.pop();

    DenseMap<DebugVariable, DbgValue> JoinedInLocs;

    // Join values from predecessors. Updates LiveInIdx, and writes output
    // into JoinedInLocs.
    bool InLocsChanged, DowngradeOccurred;
    std::tie(InLocsChanged, DowngradeOccurred) = vlocJoin(
        *MBB, LiveOutIdx, LiveInIdx, (FirstTrip) ? &VLOCVisited : nullptr,
        CurBB, VarsWeCareAbout, MOutLocs, MInLocs, InScopeBlocks,
        BlocksToExplore, JoinedInLocs);

    bool FirstVisit = VLOCVisited.insert(MBB).second;

    // Always explore transfer function if inlocs changed, or if we've not
    // visited this block before.
    InLocsChanged |= FirstVisit;

    // If a downgrade occurred, book us in for re-examination on the next
    // iteration.
    if (DowngradeOccurred && OnPending.insert(MBB).second)
      Pending.push(BBToOrder[MBB]);

    if (!InLocsChanged)
      continue;

    // Do transfer function.
    auto &VTracker = AllTheVLocs[MBB->getNumber()];
    for (auto &Transfer : VTracker.Vars) {
      // Is this var we're mangling in this scope?
      if (VarsWeCareAbout.count(Transfer.first)) {
        // Erase on empty transfer (DBG_VALUE $noreg).
        if (Transfer.second.Kind == DbgValue::Undef) {
          JoinedInLocs.erase(Transfer.first);
        } else {
          // Insert new variable value; or overwrite.
          auto NewValuePair = std::make_pair(Transfer.first, Transfer.second);
          auto Result = JoinedInLocs.insert(NewValuePair);
          if (!Result.second)
            Result.first->second = Transfer.second;
        }
      }
    }

    // Did the live-out locations change?
    bool OLChanged = JoinedInLocs != *LiveOutIdx[MBB];

    // If they haven't changed, there's no need to explore further.
    if (!OLChanged)
      continue;

    // Commit to the live-out record.
    *LiveOutIdx[MBB] = JoinedInLocs;

    // We should visit all successors. Ensure we'll visit any non-backedge
    // successors during this dataflow iteration; book backedge successors
    // to be visited next time around.
    for (auto s : MBB->successors()) {
      // Ignore out of scope / not-to-be-explored successors.
      if (LiveInIdx.find(s) == LiveInIdx.end())
        continue;

      if (BBToOrder[s] > BBToOrder[MBB]) {
        if (OnWorklist.insert(s).second)
          Worklist.push(BBToOrder[s]);
      } else if (OnPending.insert(s).second && (FirstTrip || OLChanged)) {
        Pending.push(BBToOrder[s]);
      }
    }
  }
  Worklist.swap(Pending);
  std::swap(OnWorklist, OnPending);
  OnPending.clear();
  assert(Pending.empty())((void)0);
  FirstTrip = false;
}

// Dataflow done. Now what? Save live-ins. Ignore any that are still marked
// as being variable-PHIs, because those did not have their machine-PHI
// value confirmed. Such variable values are places that could have been
// PHIs, but are not.
for (auto *MBB : BlockOrders) {
  auto &VarMap = *LiveInIdx[MBB];
  for (auto &P : VarMap) {
    if (P.second.Kind == DbgValue::Proposed ||
        P.second.Kind == DbgValue::NoVal)
      continue;
    Output[MBB->getNumber()].push_back(P);
  }
}

BlockOrders.clear();
BlocksToExplore.clear();
3408}

3410#if !defined(NDEBUG1) || defined(LLVM_ENABLE_DUMP)
3411void InstrRefBasedLDV::dump_mloc_transfer(
  const MLocTransferMap &mloc_transfer) const {
for (auto &P : mloc_transfer) {
  std::string foo = MTracker->LocIdxToName(P.first);
  std::string bar = MTracker->IDAsString(P.second);
  dbgs() << "Loc " << foo << " --> " << bar << "\n";
}
3418}
3419#endif

3421void InstrRefBasedLDV::emitLocations(
  MachineFunction &MF, LiveInsT SavedLiveIns, ValueIDNum **MOutLocs,
  ValueIDNum **MInLocs, DenseMap<DebugVariable, unsigned> &AllVarsNumbering,
  const TargetPassConfig &TPC) {
TTracker = new TransferTracker(TII, MTracker, MF, *TRI, CalleeSavedRegs, TPC);
unsigned NumLocs = MTracker->getNumLocs();

// For each block, load in the machine value locations and variable value
// live-ins, then step through each instruction in the block. New DBG_VALUEs
// to be inserted will be created along the way.
for (MachineBasicBlock &MBB : MF) {
  unsigned bbnum = MBB.getNumber();
  MTracker->reset();
  MTracker->loadFromArray(MInLocs[bbnum], bbnum);
  TTracker->loadInlocs(MBB, MInLocs[bbnum], SavedLiveIns[MBB.getNumber()],
                       NumLocs);

  CurBB = bbnum;
  CurInst = 1;
  for (auto &MI : MBB) {
    process(MI, MOutLocs, MInLocs);
    TTracker->checkInstForNewValues(CurInst, MI.getIterator());
    ++CurInst;
  }
}

// We have to insert DBG_VALUEs in a consistent order, otherwise they appeaer
// in DWARF in different orders. Use the order that they appear when walking
// through each block / each instruction, stored in AllVarsNumbering.
auto OrderDbgValues = [&](const MachineInstr *A,
                          const MachineInstr *B) -> bool {
  DebugVariable VarA(A->getDebugVariable(), A->getDebugExpression(),
                     A->getDebugLoc()->getInlinedAt());
  DebugVariable VarB(B->getDebugVariable(), B->getDebugExpression(),
                     B->getDebugLoc()->getInlinedAt());
  return AllVarsNumbering.find(VarA)->second <
         AllVarsNumbering.find(VarB)->second;
};

// Go through all the transfers recorded in the TransferTracker -- this is
// both the live-ins to a block, and any movements of values that happen
// in the middle.
for (auto &P : TTracker->Transfers) {
  // Sort them according to appearance order.
  llvm::sort(P.Insts, OrderDbgValues);
  // Insert either before or after the designated point...
  if (P.MBB) {
    MachineBasicBlock &MBB = *P.MBB;
    for (auto *MI : P.Insts) {
      MBB.insert(P.Pos, MI);
    }
  } else {
    // Terminators, like tail calls, can clobber things. Don't try and place
    // transfers after them.
    if (P.Pos->isTerminator())
      continue;

    MachineBasicBlock &MBB = *P.Pos->getParent();
    for (auto *MI : P.Insts) {
      MBB.insertAfterBundle(P.Pos, MI);
    }
  }
}
3484}

3486void InstrRefBasedLDV::initialSetup(MachineFunction &MF) {
// Build some useful data structures.
auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
  if (const DebugLoc &DL = MI.getDebugLoc())
    return DL.getLine() != 0;
  return false;
};
// Collect a set of all the artificial blocks.
for (auto &MBB : MF)
  if (none_of(MBB.instrs(), hasNonArtificialLocation))
    ArtificialBlocks.insert(&MBB);

// Compute mappings of block <=> RPO order.
ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
unsigned int RPONumber = 0;
for (MachineBasicBlock *MBB : RPOT) {
  OrderToBB[RPONumber] = MBB;
  BBToOrder[MBB] = RPONumber;
  BBNumToRPO[MBB->getNumber()] = RPONumber;
  ++RPONumber;
}

// Order value substitutions by their "source" operand pair, for quick lookup.
llvm::sort(MF.DebugValueSubstitutions);

3511#ifdef EXPENSIVE_CHECKS
// As an expensive check, test whether there are any duplicate substitution
// sources in the collection.
if (MF.DebugValueSubstitutions.size() > 2) {
  for (auto It = MF.DebugValueSubstitutions.begin();
       It != std::prev(MF.DebugValueSubstitutions.end()); ++It) {
    assert(It->Src != std::next(It)->Src && "Duplicate variable location "((void)0)
                                            "substitution seen")((void)0);
  }
}
3521#endif
3522}

3524/// Calculate the liveness information for the given machine function and
3525/// extend ranges across basic blocks.
3526bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
                                  TargetPassConfig *TPC) {
// No subprogram means this function contains no debuginfo.
if (!MF.getFunction().getSubprogram())
1
Assuming the condition is false→
2
←
Taking false branch→
  return false;

LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n")do { } while (false);
3
←
Loop condition is false.  Exiting loop→
this->TPC = TPC;

TRI = MF.getSubtarget().getRegisterInfo();
TII = MF.getSubtarget().getInstrInfo();
TFI = MF.getSubtarget().getFrameLowering();
TFI->getCalleeSaves(MF, CalleeSavedRegs);
MFI = &MF.getFrameInfo();
LS.initialize(MF);

MTracker =
    new MLocTracker(MF, *TII, *TRI, *MF.getSubtarget().getTargetLowering());
VTracker = nullptr;
TTracker = nullptr;

SmallVector<MLocTransferMap, 32> MLocTransfer;
SmallVector<VLocTracker, 8> vlocs;
LiveInsT SavedLiveIns;

int MaxNumBlocks = -1;
for (auto &MBB : MF)
  MaxNumBlocks = std::max(MBB.getNumber(), MaxNumBlocks);
assert(MaxNumBlocks >= 0)((void)0);
++MaxNumBlocks;

MLocTransfer.resize(MaxNumBlocks);
vlocs.resize(MaxNumBlocks);
SavedLiveIns.resize(MaxNumBlocks);

initialSetup(MF);

produceMLocTransferFunction(MF, MLocTransfer, MaxNumBlocks);

// Allocate and initialize two array-of-arrays for the live-in and live-out
// machine values. The outer dimension is the block number; while the inner
// dimension is a LocIdx from MLocTracker.
ValueIDNum **MOutLocs = new ValueIDNum *[MaxNumBlocks];
ValueIDNum **MInLocs = new ValueIDNum *[MaxNumBlocks];
4
←
Memory is allocated→
unsigned NumLocs = MTracker->getNumLocs();
for (int i = 0; i < MaxNumBlocks; ++i) {
5
←
Loop condition is false. Execution continues on line 3580→
  MOutLocs[i] = new ValueIDNum[NumLocs];
  MInLocs[i] = new ValueIDNum[NumLocs];
}

// Solve the machine value dataflow problem using the MLocTransfer function,
// storing the computed live-ins / live-outs into the array-of-arrays. We use
// both live-ins and live-outs for decision making in the variable value
// dataflow problem.
mlocDataflow(MInLocs, MOutLocs, MLocTransfer);
6
←
Calling 'InstrRefBasedLDV::mlocDataflow'→

// Patch up debug phi numbers, turning unknown block-live-in values into
// either live-through machine values, or PHIs.
for (auto &DBG_PHI : DebugPHINumToValue) {
  // Identify unresolved block-live-ins.
  ValueIDNum &Num = DBG_PHI.ValueRead;
  if (!Num.isPHI())
    continue;

  unsigned BlockNo = Num.getBlock();
  LocIdx LocNo = Num.getLoc();
  Num = MInLocs[BlockNo][LocNo.asU64()];
}
// Later, we'll be looking up ranges of instruction numbers.
llvm::sort(DebugPHINumToValue);

// Walk back through each block / instruction, collecting DBG_VALUE
// instructions and recording what machine value their operands refer to.
for (auto &OrderPair : OrderToBB) {
  MachineBasicBlock &MBB = *OrderPair.second;
  CurBB = MBB.getNumber();
  VTracker = &vlocs[CurBB];
  VTracker->MBB = &MBB;
  MTracker->loadFromArray(MInLocs[CurBB], CurBB);
  CurInst = 1;
  for (auto &MI : MBB) {
    process(MI, MOutLocs, MInLocs);
    ++CurInst;
  }
  MTracker->reset();
}

// Number all variables in the order that they appear, to be used as a stable
// insertion order later.
DenseMap<DebugVariable, unsigned> AllVarsNumbering;

// Map from one LexicalScope to all the variables in that scope.
DenseMap<const LexicalScope *, SmallSet<DebugVariable, 4>> ScopeToVars;

// Map from One lexical scope to all blocks in that scope.
DenseMap<const LexicalScope *, SmallPtrSet<MachineBasicBlock *, 4>>
    ScopeToBlocks;

// Store a DILocation that describes a scope.
DenseMap<const LexicalScope *, const DILocation *> ScopeToDILocation;

// To mirror old LiveDebugValues, enumerate variables in RPOT order. Otherwise
// the order is unimportant, it just has to be stable.
for (unsigned int I = 0; I < OrderToBB.size(); ++I) {
  auto *MBB = OrderToBB[I];
  auto *VTracker = &vlocs[MBB->getNumber()];
  // Collect each variable with a DBG_VALUE in this block.
  for (auto &idx : VTracker->Vars) {
    const auto &Var = idx.first;
    const DILocation *ScopeLoc = VTracker->Scopes[Var];
    assert(ScopeLoc != nullptr)((void)0);
    auto *Scope = LS.findLexicalScope(ScopeLoc);

    // No insts in scope -> shouldn't have been recorded.
    assert(Scope != nullptr)((void)0);

    AllVarsNumbering.insert(std::make_pair(Var, AllVarsNumbering.size()));
    ScopeToVars[Scope].insert(Var);
    ScopeToBlocks[Scope].insert(VTracker->MBB);
    ScopeToDILocation[Scope] = ScopeLoc;
  }
}

// OK. Iterate over scopes: there might be something to be said for
// ordering them by size/locality, but that's for the future. For each scope,
// solve the variable value problem, producing a map of variables to values
// in SavedLiveIns.
for (auto &P : ScopeToVars) {
  vlocDataflow(P.first, ScopeToDILocation[P.first], P.second,
               ScopeToBlocks[P.first], SavedLiveIns, MOutLocs, MInLocs,
               vlocs);
}

// Using the computed value locations and variable values for each block,
// create the DBG_VALUE instructions representing the extended variable
// locations.
emitLocations(MF, SavedLiveIns, MOutLocs, MInLocs, AllVarsNumbering, *TPC);

for (int Idx = 0; Idx < MaxNumBlocks; ++Idx) {
  delete[] MOutLocs[Idx];
  delete[] MInLocs[Idx];
}
delete[] MOutLocs;
delete[] MInLocs;

// Did we actually make any changes? If we created any DBG_VALUEs, then yes.
bool Changed = TTracker->Transfers.size() != 0;

delete MTracker;
delete TTracker;
MTracker = nullptr;
VTracker = nullptr;
TTracker = nullptr;

ArtificialBlocks.clear();
OrderToBB.clear();
BBToOrder.clear();
BBNumToRPO.clear();
DebugInstrNumToInstr.clear();
DebugPHINumToValue.clear();

return Changed;
3688}

3690LDVImpl *llvm::makeInstrRefBasedLiveDebugValues() {
return new InstrRefBasedLDV();
3692}

3694namespace {
3695class LDVSSABlock;
3696class LDVSSAUpdater;

3698// Pick a type to identify incoming block values as we construct SSA. We
3699// can't use anything more robust than an integer unfortunately, as SSAUpdater
3700// expects to zero-initialize the type.
3701typedef uint64_t BlockValueNum;

3703/// Represents an SSA PHI node for the SSA updater class. Contains the block
3704/// this PHI is in, the value number it would have, and the expected incoming
3705/// values from parent blocks.
3706class LDVSSAPhi {
3707public:
SmallVector<std::pair<LDVSSABlock *, BlockValueNum>, 4> IncomingValues;
LDVSSABlock *ParentBlock;
BlockValueNum PHIValNum;
LDVSSAPhi(BlockValueNum PHIValNum, LDVSSABlock *ParentBlock)
    : ParentBlock(ParentBlock), PHIValNum(PHIValNum) {}

LDVSSABlock *getParent() { return ParentBlock; }
3715};

3717/// Thin wrapper around a block predecessor iterator. Only difference from a
3718/// normal block iterator is that it dereferences to an LDVSSABlock.
3719class LDVSSABlockIterator {
3720public:
MachineBasicBlock::pred_iterator PredIt;
LDVSSAUpdater &Updater;

LDVSSABlockIterator(MachineBasicBlock::pred_iterator PredIt,
                    LDVSSAUpdater &Updater)
    : PredIt(PredIt), Updater(Updater) {}

bool operator!=(const LDVSSABlockIterator &OtherIt) const {
  return OtherIt.PredIt != PredIt;
}

LDVSSABlockIterator &operator++() {
  ++PredIt;
  return *this;
}

LDVSSABlock *operator*();
3738};

3740/// Thin wrapper around a block for SSA Updater interface. Necessary because
3741/// we need to track the PHI value(s) that we may have observed as necessary
3742/// in this block.
3743class LDVSSABlock {
3744public:
MachineBasicBlock &BB;
LDVSSAUpdater &Updater;
using PHIListT = SmallVector<LDVSSAPhi, 1>;
/// List of PHIs in this block. There should only ever be one.
PHIListT PHIList;

LDVSSABlock(MachineBasicBlock &BB, LDVSSAUpdater &Updater)
    : BB(BB), Updater(Updater) {}

LDVSSABlockIterator succ_begin() {
  return LDVSSABlockIterator(BB.succ_begin(), Updater);
}

LDVSSABlockIterator succ_end() {
  return LDVSSABlockIterator(BB.succ_end(), Updater);
}

/// SSAUpdater has requested a PHI: create that within this block record.
LDVSSAPhi *newPHI(BlockValueNum Value) {
  PHIList.emplace_back(Value, this);
  return &PHIList.back();
}

/// SSAUpdater wishes to know what PHIs already exist in this block.
PHIListT &phis() { return PHIList; }
3770};

3772/// Utility class for the SSAUpdater interface: tracks blocks, PHIs and values
3773/// while SSAUpdater is exploring the CFG. It's passed as a handle / baton to
3774// SSAUpdaterTraits<LDVSSAUpdater>.
3775class LDVSSAUpdater {
3776public:
/// Map of value numbers to PHI records.
DenseMap<BlockValueNum, LDVSSAPhi *> PHIs;
/// Map of which blocks generate Undef values -- blocks that are not
/// dominated by any Def.
DenseMap<MachineBasicBlock *, BlockValueNum> UndefMap;
/// Map of machine blocks to our own records of them.
DenseMap<MachineBasicBlock *, LDVSSABlock *> BlockMap;
/// Machine location where any PHI must occur.
LocIdx Loc;
/// Table of live-in machine value numbers for blocks / locations.
ValueIDNum **MLiveIns;

LDVSSAUpdater(LocIdx L, ValueIDNum **MLiveIns) : Loc(L), MLiveIns(MLiveIns) {}

void reset() {
  for (auto &Block : BlockMap)
    delete Block.second;

  PHIs.clear();
  UndefMap.clear();
  BlockMap.clear();
}

~LDVSSAUpdater() { reset(); }

/// For a given MBB, create a wrapper block for it. Stores it in the
/// LDVSSAUpdater block map.
LDVSSABlock *getSSALDVBlock(MachineBasicBlock *BB) {
  auto it = BlockMap.find(BB);
  if (it == BlockMap.end()) {
    BlockMap[BB] = new LDVSSABlock(*BB, *this);
    it = BlockMap.find(BB);
  }
  return it->second;
}

/// Find the live-in value number for the given block. Looks up the value at
/// the PHI location on entry.
BlockValueNum getValue(LDVSSABlock *LDVBB) {
  return MLiveIns[LDVBB->BB.getNumber()][Loc.asU64()].asU64();
}
3818};

3820LDVSSABlock *LDVSSABlockIterator::operator*() {
return Updater.getSSALDVBlock(*PredIt);
3822}

3824#ifndef NDEBUG1

3826raw_ostream &operator<<(raw_ostream &out, const LDVSSAPhi &PHI) {
out << "SSALDVPHI " << PHI.PHIValNum;
return out;
3829}

3831#endif

3833} // namespace

3835namespace llvm {

3837/// Template specialization to give SSAUpdater access to CFG and value
3838/// information. SSAUpdater calls methods in these traits, passing in the
3839/// LDVSSAUpdater object, to learn about blocks and the values they define.
3840/// It also provides methods to create PHI nodes and track them.
3841template <> class SSAUpdaterTraits<LDVSSAUpdater> {
3842public:
using BlkT = LDVSSABlock;
using ValT = BlockValueNum;
using PhiT = LDVSSAPhi;
using BlkSucc_iterator = LDVSSABlockIterator;

// Methods to access block successors -- dereferencing to our wrapper class.
static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); }
static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); }

/// Iterator for PHI operands.
class PHI_iterator {
private:
  LDVSSAPhi *PHI;
  unsigned Idx;

public:
  explicit PHI_iterator(LDVSSAPhi *P) // begin iterator
      : PHI(P), Idx(0) {}
  PHI_iterator(LDVSSAPhi *P, bool) // end iterator
      : PHI(P), Idx(PHI->IncomingValues.size()) {}

  PHI_iterator &operator++() {
    Idx++;
    return *this;
  }
  bool operator==(const PHI_iterator &X) const { return Idx == X.Idx; }
  bool operator!=(const PHI_iterator &X) const { return !operator==(X); }

  BlockValueNum getIncomingValue() { return PHI->IncomingValues[Idx].second; }

  LDVSSABlock *getIncomingBlock() { return PHI->IncomingValues[Idx].first; }
};

static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }

static inline PHI_iterator PHI_end(PhiT *PHI) {
  return PHI_iterator(PHI, true);
}

/// FindPredecessorBlocks - Put the predecessors of BB into the Preds
/// vector.
static void FindPredecessorBlocks(LDVSSABlock *BB,
                                  SmallVectorImpl<LDVSSABlock *> *Preds) {
  for (MachineBasicBlock::pred_iterator PI = BB->BB.pred_begin(),
                                        E = BB->BB.pred_end();
       PI != E; ++PI)
    Preds->push_back(BB->Updater.getSSALDVBlock(*PI));
}

/// GetUndefVal - Normally creates an IMPLICIT_DEF instruction with a new
/// register. For LiveDebugValues, represents a block identified as not having
/// any DBG_PHI predecessors.
static BlockValueNum GetUndefVal(LDVSSABlock *BB, LDVSSAUpdater *Updater) {
  // Create a value number for this block -- it needs to be unique and in the
  // "undef" collection, so that we know it's not real. Use a number
  // representing a PHI into this block.
  BlockValueNum Num = ValueIDNum(BB->BB.getNumber(), 0, Updater->Loc).asU64();
  Updater->UndefMap[&BB->BB] = Num;
  return Num;
}

/// CreateEmptyPHI - Create a (representation of a) PHI in the given block.
/// SSAUpdater will populate it with information about incoming values. The
/// value number of this PHI is whatever the  machine value number problem
/// solution determined it to be. This includes non-phi values if SSAUpdater
/// tries to create a PHI where the incoming values are identical.
static BlockValueNum CreateEmptyPHI(LDVSSABlock *BB, unsigned NumPreds,
                                 LDVSSAUpdater *Updater) {
  BlockValueNum PHIValNum = Updater->getValue(BB);
  LDVSSAPhi *PHI = BB->newPHI(PHIValNum);
  Updater->PHIs[PHIValNum] = PHI;
  return PHIValNum;
}

/// AddPHIOperand - Add the specified value as an operand of the PHI for
/// the specified predecessor block.
static void AddPHIOperand(LDVSSAPhi *PHI, BlockValueNum Val, LDVSSABlock *Pred) {
  PHI->IncomingValues.push_back(std::make_pair(Pred, Val));
}

/// ValueIsPHI - Check if the instruction that defines the specified value
/// is a PHI instruction.
static LDVSSAPhi *ValueIsPHI(BlockValueNum Val, LDVSSAUpdater *Updater) {
  auto PHIIt = Updater->PHIs.find(Val);
  if (PHIIt == Updater->PHIs.end())
    return nullptr;
  return PHIIt->second;
}

/// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
/// operands, i.e., it was just added.
static LDVSSAPhi *ValueIsNewPHI(BlockValueNum Val, LDVSSAUpdater *Updater) {
  LDVSSAPhi *PHI = ValueIsPHI(Val, Updater);
  if (PHI && PHI->IncomingValues.size() == 0)
    return PHI;
  return nullptr;
}

/// GetPHIValue - For the specified PHI instruction, return the value
/// that it defines.
static BlockValueNum GetPHIValue(LDVSSAPhi *PHI) { return PHI->PHIValNum; }
3944};

3946} // end namespace llvm

3948Optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIs(MachineFunction &MF,
                                                    ValueIDNum **MLiveOuts,
                                                    ValueIDNum **MLiveIns,
                                                    MachineInstr &Here,
                                                    uint64_t InstrNum) {
// Pick out records of DBG_PHI instructions that have been observed. If there
// are none, then we cannot compute a value number.
auto RangePair = std::equal_range(DebugPHINumToValue.begin(),
                                  DebugPHINumToValue.end(), InstrNum);
auto LowerIt = RangePair.first;
auto UpperIt = RangePair.second;

// No DBG_PHI means there can be no location.
if (LowerIt == UpperIt)
  return None;

// If there's only one DBG_PHI, then that is our value number.
if (std::distance(LowerIt, UpperIt) == 1)
  return LowerIt->ValueRead;

auto DBGPHIRange = make_range(LowerIt, UpperIt);

// Pick out the location (physreg, slot) where any PHIs must occur. It's
// technically possible for us to merge values in different registers in each
// block, but highly unlikely that LLVM will generate such code after register
// allocation.
LocIdx Loc = LowerIt->ReadLoc;

// We have several DBG_PHIs, and a use position (the Here inst). All each
// DBG_PHI does is identify a value at a program position. We can treat each
// DBG_PHI like it's a Def of a value, and the use position is a Use of a
// value, just like SSA. We use the bulk-standard LLVM SSA updater class to
// determine which Def is used at the Use, and any PHIs that happen along
// the way.
// Adapted LLVM SSA Updater:
LDVSSAUpdater Updater(Loc, MLiveIns);
// Map of which Def or PHI is the current value in each block.
DenseMap<LDVSSABlock *, BlockValueNum> AvailableValues;
// Set of PHIs that we have created along the way.
SmallVector<LDVSSAPhi *, 8> CreatedPHIs;

// Each existing DBG_PHI is a Def'd value under this model. Record these Defs
// for the SSAUpdater.
for (const auto &DBG_PHI : DBGPHIRange) {
  LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB);
  const ValueIDNum &Num = DBG_PHI.ValueRead;
  AvailableValues.insert(std::make_pair(Block, Num.asU64()));
}

LDVSSABlock *HereBlock = Updater.getSSALDVBlock(Here.getParent());
const auto &AvailIt = AvailableValues.find(HereBlock);
if (AvailIt != AvailableValues.end()) {
  // Actually, we already know what the value is -- the Use is in the same
  // block as the Def.
  return ValueIDNum::fromU64(AvailIt->second);
}

// Otherwise, we must use the SSA Updater. It will identify the value number
// that we are to use, and the PHIs that must happen along the way.
SSAUpdaterImpl<LDVSSAUpdater> Impl(&Updater, &AvailableValues, &CreatedPHIs);
BlockValueNum ResultInt = Impl.GetValue(Updater.getSSALDVBlock(Here.getParent()));
ValueIDNum Result = ValueIDNum::fromU64(ResultInt);

// We have the number for a PHI, or possibly live-through value, to be used
// at this Use. There are a number of things we have to check about it though:
//  * Does any PHI use an 'Undef' (like an IMPLICIT_DEF) value? If so, this
//    Use was not completely dominated by DBG_PHIs and we should abort.
//  * Are the Defs or PHIs clobbered in a block? SSAUpdater isn't aware that
//    we've left SSA form. Validate that the inputs to each PHI are the
//    expected values.
//  * Is a PHI we've created actually a merging of values, or are all the
//    predecessor values the same, leading to a non-PHI machine value number?
//    (SSAUpdater doesn't know that either). Remap validated PHIs into the
//    the ValidatedValues collection below to sort this out.
DenseMap<LDVSSABlock *, ValueIDNum> ValidatedValues;

// Define all the input DBG_PHI values in ValidatedValues.
for (const auto &DBG_PHI : DBGPHIRange) {
  LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB);
  const ValueIDNum &Num = DBG_PHI.ValueRead;
  ValidatedValues.insert(std::make_pair(Block, Num));
}

// Sort PHIs to validate into RPO-order.
SmallVector<LDVSSAPhi *, 8> SortedPHIs;
for (auto &PHI : CreatedPHIs)
  SortedPHIs.push_back(PHI);

std::sort(
    SortedPHIs.begin(), SortedPHIs.end(), [&](LDVSSAPhi *A, LDVSSAPhi *B) {
      return BBToOrder[&A->getParent()->BB] < BBToOrder[&B->getParent()->BB];
    });

for (auto &PHI : SortedPHIs) {
  ValueIDNum ThisBlockValueNum =
      MLiveIns[PHI->ParentBlock->BB.getNumber()][Loc.asU64()];

  // Are all these things actually defined?
  for (auto &PHIIt : PHI->IncomingValues) {
    // Any undef input means DBG_PHIs didn't dominate the use point.
    if (Updater.UndefMap.find(&PHIIt.first->BB) != Updater.UndefMap.end())
      return None;

    ValueIDNum ValueToCheck;
    ValueIDNum *BlockLiveOuts = MLiveOuts[PHIIt.first->BB.getNumber()];

    auto VVal = ValidatedValues.find(PHIIt.first);
    if (VVal == ValidatedValues.end()) {
      // We cross a loop, and this is a backedge. LLVMs tail duplication
      // happens so late that DBG_PHI instructions should not be able to
      // migrate into loops -- meaning we can only be live-through this
      // loop.
      ValueToCheck = ThisBlockValueNum;
    } else {
      // Does the block have as a live-out, in the location we're examining,
      // the value that we expect? If not, it's been moved or clobbered.
      ValueToCheck = VVal->second;
    }

    if (BlockLiveOuts[Loc.asU64()] != ValueToCheck)
      return None;
  }

  // Record this value as validated.
  ValidatedValues.insert({PHI->ParentBlock, ThisBlockValueNum});
}

// All the PHIs are valid: we can return what the SSAUpdater said our value
// number was.
return Result;
4078}