Bug Summary

File:llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp
Warning:line 2692, column 5
Use of zero-allocated memory

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -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 -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/CodeGen -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/CodeGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/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//===----------------------------------------------------------------------===//
148
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>
201
202#include "LiveDebugValues.h"
203
204using namespace llvm;
205
206// SSAUpdaterImple sets DEBUG_TYPE, change it.
207#undef DEBUG_TYPE"livedebugvalues"
208#define DEBUG_TYPE"livedebugvalues" "livedebugvalues"
209
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,
213 cl::desc("Act like old LiveDebugValues did"),
214 cl::init(false));
215
216namespace {
217
218// The location at which a spilled value resides. It consists of a register and
219// an offset.
220struct SpillLoc {
221 unsigned SpillBase;
222 StackOffset SpillOffset;
223 bool operator==(const SpillLoc &Other) const {
224 return std::make_pair(SpillBase, SpillOffset) ==
225 std::make_pair(Other.SpillBase, Other.SpillOffset);
226 }
227 bool operator<(const SpillLoc &Other) const {
228 return std::make_tuple(SpillBase, SpillOffset.getFixed(),
229 SpillOffset.getScalable()) <
230 std::make_tuple(Other.SpillBase, Other.SpillOffset.getFixed(),
231 Other.SpillOffset.getScalable());
232 }
233};
234
235class LocIdx {
236 unsigned Location;
237
238 // Default constructor is private, initializing to an illegal location number.
239 // Use only for "not an entry" elements in IndexedMaps.
240 LocIdx() : Location(UINT_MAX(2147483647 *2U +1U)) { }
241
242public:
243 #define NUM_LOC_BITS24 24
244 LocIdx(unsigned L) : Location(L) {
245 assert(L < (1 << NUM_LOC_BITS) && "Machine locations must fit in 24 bits")(static_cast<void> (0));
246 }
247
248 static LocIdx MakeIllegalLoc() {
249 return LocIdx();
250 }
251
252 bool isIllegal() const {
253 return Location == UINT_MAX(2147483647 *2U +1U);
254 }
255
256 uint64_t asU64() const {
257 return Location;
258 }
259
260 bool operator==(unsigned L) const {
261 return Location == L;
262 }
263
264 bool operator==(const LocIdx &L) const {
265 return Location == L.Location;
266 }
267
268 bool operator!=(unsigned L) const {
269 return !(*this == L);
270 }
271
272 bool operator!=(const LocIdx &L) const {
273 return !(*this == L);
274 }
275
276 bool operator<(const LocIdx &Other) const {
277 return Location < Other.Location;
278 }
279};
280
281class LocIdxToIndexFunctor {
282public:
283 using argument_type = LocIdx;
284 unsigned operator()(const LocIdx &L) const {
285 return L.asU64();
286 }
287};
288
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 {
300 uint64_t BlockNo : 20; /// The block where the def happens.
301 uint64_t InstNo : 20; /// The Instruction where the def happens.
302 /// One based, is distance from start of block.
303 uint64_t LocNo : NUM_LOC_BITS24; /// The machine location where the def happens.
304
305public:
306 // XXX -- temporarily enabled while the live-in / live-out tables are moved
307 // to something more type-y
308 ValueIDNum() : BlockNo(0xFFFFF),
309 InstNo(0xFFFFF),
310 LocNo(0xFFFFFF) { }
311
312 ValueIDNum(uint64_t Block, uint64_t Inst, uint64_t Loc)
313 : BlockNo(Block), InstNo(Inst), LocNo(Loc) { }
314
315 ValueIDNum(uint64_t Block, uint64_t Inst, LocIdx Loc)
316 : BlockNo(Block), InstNo(Inst), LocNo(Loc.asU64()) { }
317
318 uint64_t getBlock() const { return BlockNo; }
319 uint64_t getInst() const { return InstNo; }
320 uint64_t getLoc() const { return LocNo; }
321 bool isPHI() const { return InstNo == 0; }
322
323 uint64_t asU64() const {
324 uint64_t TmpBlock = BlockNo;
325 uint64_t TmpInst = InstNo;
326 return TmpBlock << 44ull | TmpInst << NUM_LOC_BITS24 | LocNo;
327 }
328
329 static ValueIDNum fromU64(uint64_t v) {
330 uint64_t L = (v & 0x3FFF);
331 return {v >> 44ull, ((v >> NUM_LOC_BITS24) & 0xFFFFF), L};
332 }
333
334 bool operator<(const ValueIDNum &Other) const {
335 return asU64() < Other.asU64();
336 }
337
338 bool operator==(const ValueIDNum &Other) const {
339 return std::tie(BlockNo, InstNo, LocNo) ==
340 std::tie(Other.BlockNo, Other.InstNo, Other.LocNo);
341 }
342
343 bool operator!=(const ValueIDNum &Other) const { return !(*this == Other); }
344
345 std::string asString(const std::string &mlocname) const {
346 return Twine("Value{bb: ")
347 .concat(Twine(BlockNo).concat(
348 Twine(", inst: ")
349 .concat((InstNo ? Twine(InstNo) : Twine("live-in"))
350 .concat(Twine(", loc: ").concat(Twine(mlocname)))
351 .concat(Twine("}")))))
352 .str();
353 }
354
355 static ValueIDNum EmptyValue;
356};
357
358} // end anonymous namespace
359
360namespace {
361
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:
366 DbgValueProperties(const DIExpression *DIExpr, bool Indirect)
367 : DIExpr(DIExpr), Indirect(Indirect) {}
368
369 /// Extract properties from an existing DBG_VALUE instruction.
370 DbgValueProperties(const MachineInstr &MI) {
371 assert(MI.isDebugValue())(static_cast<void> (0));
372 DIExpr = MI.getDebugExpression();
373 Indirect = MI.getOperand(1).isImm();
374 }
375
376 bool operator==(const DbgValueProperties &Other) const {
377 return std::tie(DIExpr, Indirect) == std::tie(Other.DIExpr, Other.Indirect);
378 }
379
380 bool operator!=(const DbgValueProperties &Other) const {
381 return !(*this == Other);
382 }
383
384 const DIExpression *DIExpr;
385 bool Indirect;
386};
387
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:
411 MachineFunction &MF;
412 const TargetInstrInfo &TII;
413 const TargetRegisterInfo &TRI;
414 const TargetLowering &TLI;
415
416 /// IndexedMap type, mapping from LocIdx to ValueIDNum.
417 using LocToValueType = IndexedMap<ValueIDNum, LocIdxToIndexFunctor>;
418
419 /// Map of LocIdxes to the ValueIDNums that they store. This is tightly
420 /// packed, entries only exist for locations that are being tracked.
421 LocToValueType LocIdxToIDNum;
422
423 /// "Map" of machine location IDs (i.e., raw register or spill number) to the
424 /// LocIdx key / number for that location. There are always at least as many
425 /// as the number of registers on the target -- if the value in the register
426 /// is not being tracked, then the LocIdx value will be zero. New entries are
427 /// appended if a new spill slot begins being tracked.
428 /// This, and the corresponding reverse map persist for the analysis of the
429 /// whole function, and is necessarying for decoding various vectors of
430 /// values.
431 std::vector<LocIdx> LocIDToLocIdx;
432
433 /// Inverse map of LocIDToLocIdx.
434 IndexedMap<unsigned, LocIdxToIndexFunctor> LocIdxToLocID;
435
436 /// Unique-ification of spill slots. Used to number them -- their LocID
437 /// number is the index in SpillLocs minus one plus NumRegs.
438 UniqueVector<SpillLoc> SpillLocs;
439
440 // If we discover a new machine location, assign it an mphi with this
441 // block number.
442 unsigned CurBB;
443
444 /// Cached local copy of the number of registers the target has.
445 unsigned NumRegs;
446
447 /// Collection of register mask operands that have been observed. Second part
448 /// of pair indicates the instruction that they happened in. Used to
449 /// reconstruct where defs happened if we start tracking a location later
450 /// on.
451 SmallVector<std::pair<const MachineOperand *, unsigned>, 32> Masks;
452
453 /// Iterator for locations and the values they contain. Dereferencing
454 /// produces a struct/pair containing the LocIdx key for this location,
455 /// and a reference to the value currently stored. Simplifies the process
456 /// of seeking a particular location.
457 class MLocIterator {
458 LocToValueType &ValueMap;
459 LocIdx Idx;
460
461 public:
462 class value_type {
463 public:
464 value_type(LocIdx Idx, ValueIDNum &Value) : Idx(Idx), Value(Value) { }
465 const LocIdx Idx; /// Read-only index of this location.
466 ValueIDNum &Value; /// Reference to the stored value at this location.
467 };
468
469 MLocIterator(LocToValueType &ValueMap, LocIdx Idx)
470 : ValueMap(ValueMap), Idx(Idx) { }
471
472 bool operator==(const MLocIterator &Other) const {
473 assert(&ValueMap == &Other.ValueMap)(static_cast<void> (0));
474 return Idx == Other.Idx;
475 }
476
477 bool operator!=(const MLocIterator &Other) const {
478 return !(*this == Other);
479 }
480
481 void operator++() {
482 Idx = LocIdx(Idx.asU64() + 1);
483 }
484
485 value_type operator*() {
486 return value_type(Idx, ValueMap[LocIdx(Idx)]);
487 }
488 };
489
490 MLocTracker(MachineFunction &MF, const TargetInstrInfo &TII,
491 const TargetRegisterInfo &TRI, const TargetLowering &TLI)
492 : MF(MF), TII(TII), TRI(TRI), TLI(TLI),
493 LocIdxToIDNum(ValueIDNum::EmptyValue),
494 LocIdxToLocID(0) {
495 NumRegs = TRI.getNumRegs();
496 reset();
497 LocIDToLocIdx.resize(NumRegs, LocIdx::MakeIllegalLoc());
498 assert(NumRegs < (1u << NUM_LOC_BITS))(static_cast<void> (0)); // Detect bit packing failure
499
500 // Always track SP. This avoids the implicit clobbering caused by regmasks
501 // from affectings its values. (LiveDebugValues disbelieves calls and
502 // regmasks that claim to clobber SP).
503 Register SP = TLI.getStackPointerRegisterToSaveRestore();
504 if (SP) {
505 unsigned ID = getLocID(SP, false);
506 (void)lookupOrTrackRegister(ID);
507 }
508 }
509
510 /// Produce location ID number for indexing LocIDToLocIdx. Takes the register
511 /// or spill number, and flag for whether it's a spill or not.
512 unsigned getLocID(Register RegOrSpill, bool isSpill) {
513 return (isSpill) ? RegOrSpill.id() + NumRegs - 1 : RegOrSpill.id();
514 }
515
516 /// Accessor for reading the value at Idx.
517 ValueIDNum getNumAtPos(LocIdx Idx) const {
518 assert(Idx.asU64() < LocIdxToIDNum.size())(static_cast<void> (0));
519 return LocIdxToIDNum[Idx];
520 }
521
522 unsigned getNumLocs(void) const { return LocIdxToIDNum.size(); }
523
524 /// Reset all locations to contain a PHI value at the designated block. Used
525 /// sometimes for actual PHI values, othertimes to indicate the block entry
526 /// value (before any more information is known).
527 void setMPhis(unsigned NewCurBB) {
528 CurBB = NewCurBB;
529 for (auto Location : locations())
530 Location.Value = {CurBB, 0, Location.Idx};
531 }
532
533 /// Load values for each location from array of ValueIDNums. Take current
534 /// bbnum just in case we read a value from a hitherto untouched register.
535 void loadFromArray(ValueIDNum *Locs, unsigned NewCurBB) {
536 CurBB = NewCurBB;
537 // Iterate over all tracked locations, and load each locations live-in
538 // value into our local index.
539 for (auto Location : locations())
540 Location.Value = Locs[Location.Idx.asU64()];
541 }
542
543 /// Wipe any un-necessary location records after traversing a block.
544 void reset(void) {
545 // We could reset all the location values too; however either loadFromArray
546 // or setMPhis should be called before this object is re-used. Just
547 // clear Masks, they're definitely not needed.
548 Masks.clear();
549 }
550
551 /// Clear all data. Destroys the LocID <=> LocIdx map, which makes most of
552 /// the information in this pass uninterpretable.
553 void clear(void) {
554 reset();
555 LocIDToLocIdx.clear();
556 LocIdxToLocID.clear();
557 LocIdxToIDNum.clear();
558 //SpillLocs.reset(); XXX UniqueVector::reset assumes a SpillLoc casts from 0
559 SpillLocs = decltype(SpillLocs)();
560
561 LocIDToLocIdx.resize(NumRegs, LocIdx::MakeIllegalLoc());
562 }
563
564 /// Set a locaiton to a certain value.
565 void setMLoc(LocIdx L, ValueIDNum Num) {
566 assert(L.asU64() < LocIdxToIDNum.size())(static_cast<void> (0));
567 LocIdxToIDNum[L] = Num;
568 }
569
570 /// Create a LocIdx for an untracked register ID. Initialize it to either an
571 /// mphi value representing a live-in, or a recent register mask clobber.
572 LocIdx trackRegister(unsigned ID) {
573 assert(ID != 0)(static_cast<void> (0));
574 LocIdx NewIdx = LocIdx(LocIdxToIDNum.size());
575 LocIdxToIDNum.grow(NewIdx);
576 LocIdxToLocID.grow(NewIdx);
577
578 // Default: it's an mphi.
579 ValueIDNum ValNum = {CurBB, 0, NewIdx};
580 // Was this reg ever touched by a regmask?
581 for (const auto &MaskPair : reverse(Masks)) {
582 if (MaskPair.first->clobbersPhysReg(ID)) {
583 // There was an earlier def we skipped.
584 ValNum = {CurBB, MaskPair.second, NewIdx};
585 break;
586 }
587 }
588
589 LocIdxToIDNum[NewIdx] = ValNum;
590 LocIdxToLocID[NewIdx] = ID;
591 return NewIdx;
592 }
593
594 LocIdx lookupOrTrackRegister(unsigned ID) {
595 LocIdx &Index = LocIDToLocIdx[ID];
596 if (Index.isIllegal())
597 Index = trackRegister(ID);
598 return Index;
599 }
600
601 /// Record a definition of the specified register at the given block / inst.
602 /// This doesn't take a ValueIDNum, because the definition and its location
603 /// are synonymous.
604 void defReg(Register R, unsigned BB, unsigned Inst) {
605 unsigned ID = getLocID(R, false);
606 LocIdx Idx = lookupOrTrackRegister(ID);
607 ValueIDNum ValueID = {BB, Inst, Idx};
608 LocIdxToIDNum[Idx] = ValueID;
609 }
610
611 /// Set a register to a value number. To be used if the value number is
612 /// known in advance.
613 void setReg(Register R, ValueIDNum ValueID) {
614 unsigned ID = getLocID(R, false);
615 LocIdx Idx = lookupOrTrackRegister(ID);
616 LocIdxToIDNum[Idx] = ValueID;
617 }
618
619 ValueIDNum readReg(Register R) {
620 unsigned ID = getLocID(R, false);
621 LocIdx Idx = lookupOrTrackRegister(ID);
622 return LocIdxToIDNum[Idx];
623 }
624
625 /// Reset a register value to zero / empty. Needed to replicate the
626 /// VarLoc implementation where a copy to/from a register effectively
627 /// clears the contents of the source register. (Values can only have one
628 /// machine location in VarLocBasedImpl).
629 void wipeRegister(Register R) {
630 unsigned ID = getLocID(R, false);
631 LocIdx Idx = LocIDToLocIdx[ID];
632 LocIdxToIDNum[Idx] = ValueIDNum::EmptyValue;
633 }
634
635 /// Determine the LocIdx of an existing register.
636 LocIdx getRegMLoc(Register R) {
637 unsigned ID = getLocID(R, false);
638 return LocIDToLocIdx[ID];
639 }
640
641 /// Record a RegMask operand being executed. Defs any register we currently
642 /// track, stores a pointer to the mask in case we have to account for it
643 /// later.
644 void writeRegMask(const MachineOperand *MO, unsigned CurBB, unsigned InstID) {
645 // Ensure SP exists, so that we don't override it later.
646 Register SP = TLI.getStackPointerRegisterToSaveRestore();
647
648 // Def any register we track have that isn't preserved. The regmask
649 // terminates the liveness of a register, meaning its value can't be
650 // relied upon -- we represent this by giving it a new value.
651 for (auto Location : locations()) {
652 unsigned ID = LocIdxToLocID[Location.Idx];
653 // Don't clobber SP, even if the mask says it's clobbered.
654 if (ID < NumRegs && ID != SP && MO->clobbersPhysReg(ID))
655 defReg(ID, CurBB, InstID);
656 }
657 Masks.push_back(std::make_pair(MO, InstID));
658 }
659
660 /// Find LocIdx for SpillLoc \p L, creating a new one if it's not tracked.
661 LocIdx getOrTrackSpillLoc(SpillLoc L) {
662 unsigned SpillID = SpillLocs.idFor(L);
663 if (SpillID == 0) {
664 SpillID = SpillLocs.insert(L);
665 unsigned L = getLocID(SpillID, true);
666 LocIdx Idx = LocIdx(LocIdxToIDNum.size()); // New idx
667 LocIdxToIDNum.grow(Idx);
668 LocIdxToLocID.grow(Idx);
669 LocIDToLocIdx.push_back(Idx);
670 LocIdxToLocID[Idx] = L;
671 return Idx;
672 } else {
673 unsigned L = getLocID(SpillID, true);
674 LocIdx Idx = LocIDToLocIdx[L];
675 return Idx;
676 }
677 }
678
679 /// Set the value stored in a spill slot.
680 void setSpill(SpillLoc L, ValueIDNum ValueID) {
681 LocIdx Idx = getOrTrackSpillLoc(L);
682 LocIdxToIDNum[Idx] = ValueID;
683 }
684
685 /// Read whatever value is in a spill slot, or None if it isn't tracked.
686 Optional<ValueIDNum> readSpill(SpillLoc L) {
687 unsigned SpillID = SpillLocs.idFor(L);
688 if (SpillID == 0)
689 return None;
690
691 unsigned LocID = getLocID(SpillID, true);
692 LocIdx Idx = LocIDToLocIdx[LocID];
693 return LocIdxToIDNum[Idx];
694 }
695
696 /// Determine the LocIdx of a spill slot. Return None if it previously
697 /// hasn't had a value assigned.
698 Optional<LocIdx> getSpillMLoc(SpillLoc L) {
699 unsigned SpillID = SpillLocs.idFor(L);
700 if (SpillID == 0)
701 return None;
702 unsigned LocNo = getLocID(SpillID, true);
703 return LocIDToLocIdx[LocNo];
704 }
705
706 /// Return true if Idx is a spill machine location.
707 bool isSpill(LocIdx Idx) const {
708 return LocIdxToLocID[Idx] >= NumRegs;
709 }
710
711 MLocIterator begin() {
712 return MLocIterator(LocIdxToIDNum, 0);
713 }
714
715 MLocIterator end() {
716 return MLocIterator(LocIdxToIDNum, LocIdxToIDNum.size());
717 }
718
719 /// Return a range over all locations currently tracked.
720 iterator_range<MLocIterator> locations() {
721 return llvm::make_range(begin(), end());
722 }
723
724 std::string LocIdxToName(LocIdx Idx) const {
725 unsigned ID = LocIdxToLocID[Idx];
726 if (ID >= NumRegs)
727 return Twine("slot ").concat(Twine(ID - NumRegs)).str();
728 else
729 return TRI.getRegAsmName(ID).str();
730 }
731
732 std::string IDAsString(const ValueIDNum &Num) const {
733 std::string DefName = LocIdxToName(Num.getLoc());
734 return Num.asString(DefName);
735 }
736
737 LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__))
738 void dump() {
739 for (auto Location : locations()) {
740 std::string MLocName = LocIdxToName(Location.Value.getLoc());
741 std::string DefName = Location.Value.asString(MLocName);
742 dbgs() << LocIdxToName(Location.Idx) << " --> " << DefName << "\n";
743 }
744 }
745
746 LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__))
747 void dump_mloc_map() {
748 for (auto Location : locations()) {
749 std::string foo = LocIdxToName(Location.Idx);
750 dbgs() << "Idx " << Location.Idx.asU64() << " " << foo << "\n";
751 }
752 }
753
754 /// Create a DBG_VALUE based on machine location \p MLoc. Qualify it with the
755 /// information in \pProperties, for variable Var. Don't insert it anywhere,
756 /// just return the builder for it.
757 MachineInstrBuilder emitLoc(Optional<LocIdx> MLoc, const DebugVariable &Var,
758 const DbgValueProperties &Properties) {
759 DebugLoc DL = DILocation::get(Var.getVariable()->getContext(), 0, 0,
760 Var.getVariable()->getScope(),
761 const_cast<DILocation *>(Var.getInlinedAt()));
762 auto MIB = BuildMI(MF, DL, TII.get(TargetOpcode::DBG_VALUE));
763
764 const DIExpression *Expr = Properties.DIExpr;
765 if (!MLoc) {
766 // No location -> DBG_VALUE $noreg
767 MIB.addReg(0, RegState::Debug);
768 MIB.addReg(0, RegState::Debug);
769 } else if (LocIdxToLocID[*MLoc] >= NumRegs) {
770 unsigned LocID = LocIdxToLocID[*MLoc];
771 const SpillLoc &Spill = SpillLocs[LocID - NumRegs + 1];
772
773 auto *TRI = MF.getSubtarget().getRegisterInfo();
774 Expr = TRI->prependOffsetExpression(Expr, DIExpression::ApplyOffset,
775 Spill.SpillOffset);
776 unsigned Base = Spill.SpillBase;
777 MIB.addReg(Base, RegState::Debug);
778 MIB.addImm(0);
779 } else {
780 unsigned LocID = LocIdxToLocID[*MLoc];
781 MIB.addReg(LocID, RegState::Debug);
782 if (Properties.Indirect)
783 MIB.addImm(0);
784 else
785 MIB.addReg(0, RegState::Debug);
786 }
787
788 MIB.addMetadata(Var.getVariable());
789 MIB.addMetadata(Expr);
790 return MIB;
791 }
792};
793
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:
801 union {
802 /// If Kind is Def, the value number that this value is based on.
803 ValueIDNum ID;
804 /// If Kind is Const, the MachineOperand defining this value.
805 MachineOperand MO;
806 /// For a NoVal DbgValue, which block it was generated in.
807 unsigned BlockNo;
808 };
809 /// Qualifiers for the ValueIDNum above.
810 DbgValueProperties Properties;
811
812 typedef enum {
813 Undef, // Represents a DBG_VALUE $noreg in the transfer function only.
814 Def, // This value is defined by an inst, or is a PHI value.
815 Const, // A constant value contained in the MachineOperand field.
816 Proposed, // This is a tentative PHI value, which may be confirmed or
817 // invalidated later.
818 NoVal // Empty DbgValue, generated during dataflow. BlockNo stores
819 // which block this was generated in.
820 } KindT;
821 /// Discriminator for whether this is a constant or an in-program value.
822 KindT Kind;
823
824 DbgValue(const ValueIDNum &Val, const DbgValueProperties &Prop, KindT Kind)
825 : ID(Val), Properties(Prop), Kind(Kind) {
826 assert(Kind == Def || Kind == Proposed)(static_cast<void> (0));
827 }
828
829 DbgValue(unsigned BlockNo, const DbgValueProperties &Prop, KindT Kind)
830 : BlockNo(BlockNo), Properties(Prop), Kind(Kind) {
831 assert(Kind == NoVal)(static_cast<void> (0));
832 }
833
834 DbgValue(const MachineOperand &MO, const DbgValueProperties &Prop, KindT Kind)
835 : MO(MO), Properties(Prop), Kind(Kind) {
836 assert(Kind == Const)(static_cast<void> (0));
837 }
838
839 DbgValue(const DbgValueProperties &Prop, KindT Kind)
840 : Properties(Prop), Kind(Kind) {
841 assert(Kind == Undef &&(static_cast<void> (0))
842 "Empty DbgValue constructor must pass in Undef kind")(static_cast<void> (0));
843 }
844
845 void dump(const MLocTracker *MTrack) const {
846 if (Kind == Const) {
847 MO.dump();
848 } else if (Kind == NoVal) {
849 dbgs() << "NoVal(" << BlockNo << ")";
850 } else if (Kind == Proposed) {
851 dbgs() << "VPHI(" << MTrack->IDAsString(ID) << ")";
852 } else {
853 assert(Kind == Def)(static_cast<void> (0));
854 dbgs() << MTrack->IDAsString(ID);
855 }
856 if (Properties.Indirect)
857 dbgs() << " indir";
858 if (Properties.DIExpr)
859 dbgs() << " " << *Properties.DIExpr;
860 }
861
862 bool operator==(const DbgValue &Other) const {
863 if (std::tie(Kind, Properties) != std::tie(Other.Kind, Other.Properties))
864 return false;
865 else if (Kind == Proposed && ID != Other.ID)
866 return false;
867 else if (Kind == Def && ID != Other.ID)
868 return false;
869 else if (Kind == NoVal && BlockNo != Other.BlockNo)
870 return false;
871 else if (Kind == Const)
872 return MO.isIdenticalTo(Other.MO);
873
874 return true;
875 }
876
877 bool operator!=(const DbgValue &Other) const { return !(*this == Other); }
878};
879
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 =
884 std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
885using OverlapMap =
886 DenseMap<FragmentOfVar, SmallVector<DIExpression::FragmentInfo, 1>>;
887
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:
894 /// Map DebugVariable to the latest Value it's defined to have.
895 /// Needs to be a MapVector because we determine order-in-the-input-MIR from
896 /// the order in this container.
897 /// We only retain the last DbgValue in each block for each variable, to
898 /// determine the blocks live-out variable value. The Vars container forms the
899 /// transfer function for this block, as part of the dataflow analysis. The
900 /// movement of values between locations inside of a block is handled at a
901 /// much later stage, in the TransferTracker class.
902 MapVector<DebugVariable, DbgValue> Vars;
903 DenseMap<DebugVariable, const DILocation *> Scopes;
904 MachineBasicBlock *MBB;
905
906public:
907 VLocTracker() {}
908
909 void defVar(const MachineInstr &MI, const DbgValueProperties &Properties,
910 Optional<ValueIDNum> ID) {
911 assert(MI.isDebugValue() || MI.isDebugRef())(static_cast<void> (0));
912 DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
913 MI.getDebugLoc()->getInlinedAt());
914 DbgValue Rec = (ID) ? DbgValue(*ID, Properties, DbgValue::Def)
915 : DbgValue(Properties, DbgValue::Undef);
916
917 // Attempt insertion; overwrite if it's already mapped.
918 auto Result = Vars.insert(std::make_pair(Var, Rec));
919 if (!Result.second)
920 Result.first->second = Rec;
921 Scopes[Var] = MI.getDebugLoc().get();
922 }
923
924 void defVar(const MachineInstr &MI, const MachineOperand &MO) {
925 // Only DBG_VALUEs can define constant-valued variables.
926 assert(MI.isDebugValue())(static_cast<void> (0));
927 DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
928 MI.getDebugLoc()->getInlinedAt());
929 DbgValueProperties Properties(MI);
930 DbgValue Rec = DbgValue(MO, Properties, DbgValue::Const);
931
932 // Attempt insertion; overwrite if it's already mapped.
933 auto Result = Vars.insert(std::make_pair(Var, Rec));
934 if (!Result.second)
935 Result.first->second = Rec;
936 Scopes[Var] = MI.getDebugLoc().get();
937 }
938};
939
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:
958 const TargetInstrInfo *TII;
959 const TargetLowering *TLI;
960 /// This machine location tracker is assumed to always contain the up-to-date
961 /// value mapping for all machine locations. TransferTracker only reads
962 /// information from it. (XXX make it const?)
963 MLocTracker *MTracker;
964 MachineFunction &MF;
965 bool ShouldEmitDebugEntryValues;
966
967 /// Record of all changes in variable locations at a block position. Awkwardly
968 /// we allow inserting either before or after the point: MBB != nullptr
969 /// indicates it's before, otherwise after.
970 struct Transfer {
971 MachineBasicBlock::instr_iterator Pos; /// Position to insert DBG_VALUes
972 MachineBasicBlock *MBB; /// non-null if we should insert after.
973 SmallVector<MachineInstr *, 4> Insts; /// Vector of DBG_VALUEs to insert.
974 };
975
976 struct LocAndProperties {
977 LocIdx Loc;
978 DbgValueProperties Properties;
979 };
980
981 /// Collection of transfers (DBG_VALUEs) to be inserted.
982 SmallVector<Transfer, 32> Transfers;
983
984 /// Local cache of what-value-is-in-what-LocIdx. Used to identify differences
985 /// between TransferTrackers view of variable locations and MLocTrackers. For
986 /// example, MLocTracker observes all clobbers, but TransferTracker lazily
987 /// does not.
988 std::vector<ValueIDNum> VarLocs;
989
990 /// Map from LocIdxes to which DebugVariables are based that location.
991 /// Mantained while stepping through the block. Not accurate if
992 /// VarLocs[Idx] != MTracker->LocIdxToIDNum[Idx].
993 std::map<LocIdx, SmallSet<DebugVariable, 4>> ActiveMLocs;
994
995 /// Map from DebugVariable to it's current location and qualifying meta
996 /// information. To be used in conjunction with ActiveMLocs to construct
997 /// enough information for the DBG_VALUEs for a particular LocIdx.
998 DenseMap<DebugVariable, LocAndProperties> ActiveVLocs;
999
1000 /// Temporary cache of DBG_VALUEs to be entered into the Transfers collection.
1001 SmallVector<MachineInstr *, 4> PendingDbgValues;
1002
1003 /// Record of a use-before-def: created when a value that's live-in to the
1004 /// current block isn't available in any machine location, but it will be
1005 /// defined in this block.
1006 struct UseBeforeDef {
1007 /// Value of this variable, def'd in block.
1008 ValueIDNum ID;
1009 /// Identity of this variable.
1010 DebugVariable Var;
1011 /// Additional variable properties.
1012 DbgValueProperties Properties;
1013 };
1014
1015 /// Map from instruction index (within the block) to the set of UseBeforeDefs
1016 /// that become defined at that instruction.
1017 DenseMap<unsigned, SmallVector<UseBeforeDef, 1>> UseBeforeDefs;
1018
1019 /// The set of variables that are in UseBeforeDefs and can become a location
1020 /// once the relevant value is defined. An element being erased from this
1021 /// collection prevents the use-before-def materializing.
1022 DenseSet<DebugVariable> UseBeforeDefVariables;
1023
1024 const TargetRegisterInfo &TRI;
1025 const BitVector &CalleeSavedRegs;
1026
1027 TransferTracker(const TargetInstrInfo *TII, MLocTracker *MTracker,
1028 MachineFunction &MF, const TargetRegisterInfo &TRI,
1029 const BitVector &CalleeSavedRegs, const TargetPassConfig &TPC)
1030 : TII(TII), MTracker(MTracker), MF(MF), TRI(TRI),
1031 CalleeSavedRegs(CalleeSavedRegs) {
1032 TLI = MF.getSubtarget().getTargetLowering();
1033 auto &TM = TPC.getTM<TargetMachine>();
1034 ShouldEmitDebugEntryValues = TM.Options.ShouldEmitDebugEntryValues();
1035 }
1036
1037 /// Load object with live-in variable values. \p mlocs contains the live-in
1038 /// values in each machine location, while \p vlocs the live-in variable
1039 /// values. This method picks variable locations for the live-in variables,
1040 /// creates DBG_VALUEs and puts them in #Transfers, then prepares the other
1041 /// object fields to track variable locations as we step through the block.
1042 /// FIXME: could just examine mloctracker instead of passing in \p mlocs?
1043 void loadInlocs(MachineBasicBlock &MBB, ValueIDNum *MLocs,
1044 SmallVectorImpl<std::pair<DebugVariable, DbgValue>> &VLocs,
1045 unsigned NumLocs) {
1046 ActiveMLocs.clear();
1047 ActiveVLocs.clear();
1048 VarLocs.clear();
1049 VarLocs.reserve(NumLocs);
1050 UseBeforeDefs.clear();
1051 UseBeforeDefVariables.clear();
1052
1053 auto isCalleeSaved = [&](LocIdx L) {
1054 unsigned Reg = MTracker->LocIdxToLocID[L];
1055 if (Reg >= MTracker->NumRegs)
1056 return false;
1057 for (MCRegAliasIterator RAI(Reg, &TRI, true); RAI.isValid(); ++RAI)
1058 if (CalleeSavedRegs.test(*RAI))
1059 return true;
1060 return false;
1061 };
1062
1063 // Map of the preferred location for each value.
1064 std::map<ValueIDNum, LocIdx> ValueToLoc;
1065
1066 // Produce a map of value numbers to the current machine locs they live
1067 // in. When emulating VarLocBasedImpl, there should only be one
1068 // location; when not, we get to pick.
1069 for (auto Location : MTracker->locations()) {
1070 LocIdx Idx = Location.Idx;
1071 ValueIDNum &VNum = MLocs[Idx.asU64()];
1072 VarLocs.push_back(VNum);
1073 auto it = ValueToLoc.find(VNum);
1074 // In order of preference, pick:
1075 // * Callee saved registers,
1076 // * Other registers,
1077 // * Spill slots.
1078 if (it == ValueToLoc.end() || MTracker->isSpill(it->second) ||
1079 (!isCalleeSaved(it->second) && isCalleeSaved(Idx.asU64()))) {
1080 // Insert, or overwrite if insertion failed.
1081 auto PrefLocRes = ValueToLoc.insert(std::make_pair(VNum, Idx));
1082 if (!PrefLocRes.second)
1083 PrefLocRes.first->second = Idx;
1084 }
1085 }
1086
1087 // Now map variables to their picked LocIdxes.
1088 for (auto Var : VLocs) {
1089 if (Var.second.Kind == DbgValue::Const) {
1090 PendingDbgValues.push_back(
1091 emitMOLoc(Var.second.MO, Var.first, Var.second.Properties));
1092 continue;
1093 }
1094
1095 // If the value has no location, we can't make a variable location.
1096 const ValueIDNum &Num = Var.second.ID;
1097 auto ValuesPreferredLoc = ValueToLoc.find(Num);
1098 if (ValuesPreferredLoc == ValueToLoc.end()) {
1099 // If it's a def that occurs in this block, register it as a
1100 // use-before-def to be resolved as we step through the block.
1101 if (Num.getBlock() == (unsigned)MBB.getNumber() && !Num.isPHI())
1102 addUseBeforeDef(Var.first, Var.second.Properties, Num);
1103 else
1104 recoverAsEntryValue(Var.first, Var.second.Properties, Num);
1105 continue;
1106 }
1107
1108 LocIdx M = ValuesPreferredLoc->second;
1109 auto NewValue = LocAndProperties{M, Var.second.Properties};
1110 auto Result = ActiveVLocs.insert(std::make_pair(Var.first, NewValue));
1111 if (!Result.second)
1112 Result.first->second = NewValue;
1113 ActiveMLocs[M].insert(Var.first);
1114 PendingDbgValues.push_back(
1115 MTracker->emitLoc(M, Var.first, Var.second.Properties));
1116 }
1117 flushDbgValues(MBB.begin(), &MBB);
1118 }
1119
1120 /// Record that \p Var has value \p ID, a value that becomes available
1121 /// later in the function.
1122 void addUseBeforeDef(const DebugVariable &Var,
1123 const DbgValueProperties &Properties, ValueIDNum ID) {
1124 UseBeforeDef UBD = {ID, Var, Properties};
1125 UseBeforeDefs[ID.getInst()].push_back(UBD);
1126 UseBeforeDefVariables.insert(Var);
1127 }
1128
1129 /// After the instruction at index \p Inst and position \p pos has been
1130 /// processed, check whether it defines a variable value in a use-before-def.
1131 /// If so, and the variable value hasn't changed since the start of the
1132 /// block, create a DBG_VALUE.
1133 void checkInstForNewValues(unsigned Inst, MachineBasicBlock::iterator pos) {
1134 auto MIt = UseBeforeDefs.find(Inst);
1135 if (MIt == UseBeforeDefs.end())
1136 return;
1137
1138 for (auto &Use : MIt->second) {
1139 LocIdx L = Use.ID.getLoc();
1140
1141 // If something goes very wrong, we might end up labelling a COPY
1142 // instruction or similar with an instruction number, where it doesn't
1143 // actually define a new value, instead it moves a value. In case this
1144 // happens, discard.
1145 if (MTracker->LocIdxToIDNum[L] != Use.ID)
1146 continue;
1147
1148 // If a different debug instruction defined the variable value / location
1149 // since the start of the block, don't materialize this use-before-def.
1150 if (!UseBeforeDefVariables.count(Use.Var))
1151 continue;
1152
1153 PendingDbgValues.push_back(MTracker->emitLoc(L, Use.Var, Use.Properties));
1154 }
1155 flushDbgValues(pos, nullptr);
1156 }
1157
1158 /// Helper to move created DBG_VALUEs into Transfers collection.
1159 void flushDbgValues(MachineBasicBlock::iterator Pos, MachineBasicBlock *MBB) {
1160 if (PendingDbgValues.size() == 0)
1161 return;
1162
1163 // Pick out the instruction start position.
1164 MachineBasicBlock::instr_iterator BundleStart;
1165 if (MBB && Pos == MBB->begin())
1166 BundleStart = MBB->instr_begin();
1167 else
1168 BundleStart = getBundleStart(Pos->getIterator());
1169
1170 Transfers.push_back({BundleStart, MBB, PendingDbgValues});
1171 PendingDbgValues.clear();
1172 }
1173
1174 bool isEntryValueVariable(const DebugVariable &Var,
1175 const DIExpression *Expr) const {
1176 if (!Var.getVariable()->isParameter())
1177 return false;
1178
1179 if (Var.getInlinedAt())
1180 return false;
1181
1182 if (Expr->getNumElements() > 0)
1183 return false;
1184
1185 return true;
1186 }
1187
1188 bool isEntryValueValue(const ValueIDNum &Val) const {
1189 // Must be in entry block (block number zero), and be a PHI / live-in value.
1190 if (Val.getBlock() || !Val.isPHI())
1191 return false;
1192
1193 // Entry values must enter in a register.
1194 if (MTracker->isSpill(Val.getLoc()))
1195 return false;
1196
1197 Register SP = TLI->getStackPointerRegisterToSaveRestore();
1198 Register FP = TRI.getFrameRegister(MF);
1199 Register Reg = MTracker->LocIdxToLocID[Val.getLoc()];
1200 return Reg != SP && Reg != FP;
1201 }
1202
1203 bool recoverAsEntryValue(const DebugVariable &Var, DbgValueProperties &Prop,
1204 const ValueIDNum &Num) {
1205 // Is this variable location a candidate to be an entry value. First,
1206 // should we be trying this at all?
1207 if (!ShouldEmitDebugEntryValues)
1208 return false;
1209
1210 // Is the variable appropriate for entry values (i.e., is a parameter).
1211 if (!isEntryValueVariable(Var, Prop.DIExpr))
1212 return false;
1213
1214 // Is the value assigned to this variable still the entry value?
1215 if (!isEntryValueValue(Num))
1216 return false;
1217
1218 // Emit a variable location using an entry value expression.
1219 DIExpression *NewExpr =
1220 DIExpression::prepend(Prop.DIExpr, DIExpression::EntryValue);
1221 Register Reg = MTracker->LocIdxToLocID[Num.getLoc()];
1222 MachineOperand MO = MachineOperand::CreateReg(Reg, false);
1223 MO.setIsDebug(true);
1224
1225 PendingDbgValues.push_back(emitMOLoc(MO, Var, {NewExpr, Prop.Indirect}));
1226 return true;
1227 }
1228
1229 /// Change a variable value after encountering a DBG_VALUE inside a block.
1230 void redefVar(const MachineInstr &MI) {
1231 DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
1232 MI.getDebugLoc()->getInlinedAt());
1233 DbgValueProperties Properties(MI);
1234
1235 const MachineOperand &MO = MI.getOperand(0);
1236
1237 // Ignore non-register locations, we don't transfer those.
1238 if (!MO.isReg() || MO.getReg() == 0) {
1239 auto It = ActiveVLocs.find(Var);
1240 if (It != ActiveVLocs.end()) {
1241 ActiveMLocs[It->second.Loc].erase(Var);
1242 ActiveVLocs.erase(It);
1243 }
1244 // Any use-before-defs no longer apply.
1245 UseBeforeDefVariables.erase(Var);
1246 return;
1247 }
1248
1249 Register Reg = MO.getReg();
1250 LocIdx NewLoc = MTracker->getRegMLoc(Reg);
1251 redefVar(MI, Properties, NewLoc);
1252 }
1253
1254 /// Handle a change in variable location within a block. Terminate the
1255 /// variables current location, and record the value it now refers to, so
1256 /// that we can detect location transfers later on.
1257 void redefVar(const MachineInstr &MI, const DbgValueProperties &Properties,
1258 Optional<LocIdx> OptNewLoc) {
1259 DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
1260 MI.getDebugLoc()->getInlinedAt());
1261 // Any use-before-defs no longer apply.
1262 UseBeforeDefVariables.erase(Var);
1263
1264 // Erase any previous location,
1265 auto It = ActiveVLocs.find(Var);
1266 if (It != ActiveVLocs.end())
1267 ActiveMLocs[It->second.Loc].erase(Var);
1268
1269 // If there _is_ no new location, all we had to do was erase.
1270 if (!OptNewLoc)
1271 return;
1272 LocIdx NewLoc = *OptNewLoc;
1273
1274 // Check whether our local copy of values-by-location in #VarLocs is out of
1275 // date. Wipe old tracking data for the location if it's been clobbered in
1276 // the meantime.
1277 if (MTracker->getNumAtPos(NewLoc) != VarLocs[NewLoc.asU64()]) {
1278 for (auto &P : ActiveMLocs[NewLoc]) {
1279 ActiveVLocs.erase(P);
1280 }
1281 ActiveMLocs[NewLoc.asU64()].clear();
1282 VarLocs[NewLoc.asU64()] = MTracker->getNumAtPos(NewLoc);
1283 }
1284
1285 ActiveMLocs[NewLoc].insert(Var);
1286 if (It == ActiveVLocs.end()) {
1287 ActiveVLocs.insert(
1288 std::make_pair(Var, LocAndProperties{NewLoc, Properties}));
1289 } else {
1290 It->second.Loc = NewLoc;
1291 It->second.Properties = Properties;
1292 }
1293 }
1294
1295 /// Account for a location \p mloc being clobbered. Examine the variable
1296 /// locations that will be terminated: and try to recover them by using
1297 /// another location. Optionally, given \p MakeUndef, emit a DBG_VALUE to
1298 /// explicitly terminate a location if it can't be recovered.
1299 void clobberMloc(LocIdx MLoc, MachineBasicBlock::iterator Pos,
1300 bool MakeUndef = true) {
1301 auto ActiveMLocIt = ActiveMLocs.find(MLoc);
1302 if (ActiveMLocIt == ActiveMLocs.end())
1303 return;
1304
1305 // What was the old variable value?
1306 ValueIDNum OldValue = VarLocs[MLoc.asU64()];
1307 VarLocs[MLoc.asU64()] = ValueIDNum::EmptyValue;
1308
1309 // Examine the remaining variable locations: if we can find the same value
1310 // again, we can recover the location.
1311 Optional<LocIdx> NewLoc = None;
1312 for (auto Loc : MTracker->locations())
1313 if (Loc.Value == OldValue)
1314 NewLoc = Loc.Idx;
1315
1316 // If there is no location, and we weren't asked to make the variable
1317 // explicitly undef, then stop here.
1318 if (!NewLoc && !MakeUndef) {
1319 // Try and recover a few more locations with entry values.
1320 for (auto &Var : ActiveMLocIt->second) {
1321 auto &Prop = ActiveVLocs.find(Var)->second.Properties;
1322 recoverAsEntryValue(Var, Prop, OldValue);
1323 }
1324 flushDbgValues(Pos, nullptr);
1325 return;
1326 }
1327
1328 // Examine all the variables based on this location.
1329 DenseSet<DebugVariable> NewMLocs;
1330 for (auto &Var : ActiveMLocIt->second) {
1331 auto ActiveVLocIt = ActiveVLocs.find(Var);
1332 // Re-state the variable location: if there's no replacement then NewLoc
1333 // is None and a $noreg DBG_VALUE will be created. Otherwise, a DBG_VALUE
1334 // identifying the alternative location will be emitted.
1335 const DIExpression *Expr = ActiveVLocIt->second.Properties.DIExpr;
1336 DbgValueProperties Properties(Expr, false);
1337 PendingDbgValues.push_back(MTracker->emitLoc(NewLoc, Var, Properties));
1338
1339 // Update machine locations <=> variable locations maps. Defer updating
1340 // ActiveMLocs to avoid invalidaing the ActiveMLocIt iterator.
1341 if (!NewLoc) {
1342 ActiveVLocs.erase(ActiveVLocIt);
1343 } else {
1344 ActiveVLocIt->second.Loc = *NewLoc;
1345 NewMLocs.insert(Var);
1346 }
1347 }
1348
1349 // Commit any deferred ActiveMLoc changes.
1350 if (!NewMLocs.empty())
1351 for (auto &Var : NewMLocs)
1352 ActiveMLocs[*NewLoc].insert(Var);
1353
1354 // We lazily track what locations have which values; if we've found a new
1355 // location for the clobbered value, remember it.
1356 if (NewLoc)
1357 VarLocs[NewLoc->asU64()] = OldValue;
1358
1359 flushDbgValues(Pos, nullptr);
1360
1361 ActiveMLocIt->second.clear();
1362 }
1363
1364 /// Transfer variables based on \p Src to be based on \p Dst. This handles
1365 /// both register copies as well as spills and restores. Creates DBG_VALUEs
1366 /// describing the movement.
1367 void transferMlocs(LocIdx Src, LocIdx Dst, MachineBasicBlock::iterator Pos) {
1368 // Does Src still contain the value num we expect? If not, it's been
1369 // clobbered in the meantime, and our variable locations are stale.
1370 if (VarLocs[Src.asU64()] != MTracker->getNumAtPos(Src))
1371 return;
1372
1373 // assert(ActiveMLocs[Dst].size() == 0);
1374 //^^^ Legitimate scenario on account of un-clobbered slot being assigned to?
1375 ActiveMLocs[Dst] = ActiveMLocs[Src];
1376 VarLocs[Dst.asU64()] = VarLocs[Src.asU64()];
1377
1378 // For each variable based on Src; create a location at Dst.
1379 for (auto &Var : ActiveMLocs[Src]) {
1380 auto ActiveVLocIt = ActiveVLocs.find(Var);
1381 assert(ActiveVLocIt != ActiveVLocs.end())(static_cast<void> (0));
1382 ActiveVLocIt->second.Loc = Dst;
1383
1384 MachineInstr *MI =
1385 MTracker->emitLoc(Dst, Var, ActiveVLocIt->second.Properties);
1386 PendingDbgValues.push_back(MI);
1387 }
1388 ActiveMLocs[Src].clear();
1389 flushDbgValues(Pos, nullptr);
1390
1391 // XXX XXX XXX "pretend to be old LDV" means dropping all tracking data
1392 // about the old location.
1393 if (EmulateOldLDV)
1394 VarLocs[Src.asU64()] = ValueIDNum::EmptyValue;
1395 }
1396
1397 MachineInstrBuilder emitMOLoc(const MachineOperand &MO,
1398 const DebugVariable &Var,
1399 const DbgValueProperties &Properties) {
1400 DebugLoc DL = DILocation::get(Var.getVariable()->getContext(), 0, 0,
1401 Var.getVariable()->getScope(),
1402 const_cast<DILocation *>(Var.getInlinedAt()));
1403 auto MIB = BuildMI(MF, DL, TII->get(TargetOpcode::DBG_VALUE));
1404 MIB.add(MO);
1405 if (Properties.Indirect)
1406 MIB.addImm(0);
1407 else
1408 MIB.addReg(0);
1409 MIB.addMetadata(Var.getVariable());
1410 MIB.addMetadata(Properties.DIExpr);
1411 return MIB;
1412 }
1413};
1414
1415class InstrRefBasedLDV : public LDVImpl {
1416private:
1417 using FragmentInfo = DIExpression::FragmentInfo;
1418 using OptFragmentInfo = Optional<DIExpression::FragmentInfo>;
1419
1420 // Helper while building OverlapMap, a map of all fragments seen for a given
1421 // DILocalVariable.
1422 using VarToFragments =
1423 DenseMap<const DILocalVariable *, SmallSet<FragmentInfo, 4>>;
1424
1425 /// Machine location/value transfer function, a mapping of which locations
1426 /// are assigned which new values.
1427 using MLocTransferMap = std::map<LocIdx, ValueIDNum>;
1428
1429 /// Live in/out structure for the variable values: a per-block map of
1430 /// variables to their values. XXX, better name?
1431 using LiveIdxT =
1432 DenseMap<const MachineBasicBlock *, DenseMap<DebugVariable, DbgValue> *>;
1433
1434 using VarAndLoc = std::pair<DebugVariable, DbgValue>;
1435
1436 /// Type for a live-in value: the predecessor block, and its value.
1437 using InValueT = std::pair<MachineBasicBlock *, DbgValue *>;
1438
1439 /// Vector (per block) of a collection (inner smallvector) of live-ins.
1440 /// Used as the result type for the variable value dataflow problem.
1441 using LiveInsT = SmallVector<SmallVector<VarAndLoc, 8>, 8>;
1442
1443 const TargetRegisterInfo *TRI;
1444 const TargetInstrInfo *TII;
1445 const TargetFrameLowering *TFI;
1446 const MachineFrameInfo *MFI;
1447 BitVector CalleeSavedRegs;
1448 LexicalScopes LS;
1449 TargetPassConfig *TPC;
1450
1451 /// Object to track machine locations as we step through a block. Could
1452 /// probably be a field rather than a pointer, as it's always used.
1453 MLocTracker *MTracker;
1454
1455 /// Number of the current block LiveDebugValues is stepping through.
1456 unsigned CurBB;
1457
1458 /// Number of the current instruction LiveDebugValues is evaluating.
1459 unsigned CurInst;
1460
1461 /// Variable tracker -- listens to DBG_VALUEs occurring as InstrRefBasedImpl
1462 /// steps through a block. Reads the values at each location from the
1463 /// MLocTracker object.
1464 VLocTracker *VTracker;
1465
1466 /// Tracker for transfers, listens to DBG_VALUEs and transfers of values
1467 /// between locations during stepping, creates new DBG_VALUEs when values move
1468 /// location.
1469 TransferTracker *TTracker;
1470
1471 /// Blocks which are artificial, i.e. blocks which exclusively contain
1472 /// instructions without DebugLocs, or with line 0 locations.
1473 SmallPtrSet<const MachineBasicBlock *, 16> ArtificialBlocks;
1474
1475 // Mapping of blocks to and from their RPOT order.
1476 DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
1477 DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
1478 DenseMap<unsigned, unsigned> BBNumToRPO;
1479
1480 /// Pair of MachineInstr, and its 1-based offset into the containing block.
1481 using InstAndNum = std::pair<const MachineInstr *, unsigned>;
1482 /// Map from debug instruction number to the MachineInstr labelled with that
1483 /// number, and its location within the function. Used to transform
1484 /// instruction numbers in DBG_INSTR_REFs into machine value numbers.
1485 std::map<uint64_t, InstAndNum> DebugInstrNumToInstr;
1486
1487 /// Record of where we observed a DBG_PHI instruction.
1488 class DebugPHIRecord {
1489 public:
1490 uint64_t InstrNum; ///< Instruction number of this DBG_PHI.
1491 MachineBasicBlock *MBB; ///< Block where DBG_PHI occurred.
1492 ValueIDNum ValueRead; ///< The value number read by the DBG_PHI.
1493 LocIdx ReadLoc; ///< Register/Stack location the DBG_PHI reads.
1494
1495 operator unsigned() const { return InstrNum; }
1496 };
1497
1498 /// Map from instruction numbers defined by DBG_PHIs to a record of what that
1499 /// DBG_PHI read and where. Populated and edited during the machine value
1500 /// location problem -- we use LLVMs SSA Updater to fix changes by
1501 /// optimizations that destroy PHI instructions.
1502 SmallVector<DebugPHIRecord, 32> DebugPHINumToValue;
1503
1504 // Map of overlapping variable fragments.
1505 OverlapMap OverlapFragments;
1506 VarToFragments SeenFragments;
1507
1508 /// Tests whether this instruction is a spill to a stack slot.
1509 bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF);
1510
1511 /// Decide if @MI is a spill instruction and return true if it is. We use 2
1512 /// criteria to make this decision:
1513 /// - Is this instruction a store to a spill slot?
1514 /// - Is there a register operand that is both used and killed?
1515 /// TODO: Store optimization can fold spills into other stores (including
1516 /// other spills). We do not handle this yet (more than one memory operand).
1517 bool isLocationSpill(const MachineInstr &MI, MachineFunction *MF,
1518 unsigned &Reg);
1519
1520 /// If a given instruction is identified as a spill, return the spill slot
1521 /// and set \p Reg to the spilled register.
1522 Optional<SpillLoc> isRestoreInstruction(const MachineInstr &MI,
1523 MachineFunction *MF, unsigned &Reg);
1524
1525 /// Given a spill instruction, extract the register and offset used to
1526 /// address the spill slot in a target independent way.
1527 SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI);
1528
1529 /// Observe a single instruction while stepping through a block.
1530 void process(MachineInstr &MI, ValueIDNum **MLiveOuts = nullptr,
1531 ValueIDNum **MLiveIns = nullptr);
1532
1533 /// Examines whether \p MI is a DBG_VALUE and notifies trackers.
1534 /// \returns true if MI was recognized and processed.
1535 bool transferDebugValue(const MachineInstr &MI);
1536
1537 /// Examines whether \p MI is a DBG_INSTR_REF and notifies trackers.
1538 /// \returns true if MI was recognized and processed.
1539 bool transferDebugInstrRef(MachineInstr &MI, ValueIDNum **MLiveOuts,
1540 ValueIDNum **MLiveIns);
1541
1542 /// Stores value-information about where this PHI occurred, and what
1543 /// instruction number is associated with it.
1544 /// \returns true if MI was recognized and processed.
1545 bool transferDebugPHI(MachineInstr &MI);
1546
1547 /// Examines whether \p MI is copy instruction, and notifies trackers.
1548 /// \returns true if MI was recognized and processed.
1549 bool transferRegisterCopy(MachineInstr &MI);
1550
1551 /// Examines whether \p MI is stack spill or restore instruction, and
1552 /// notifies trackers. \returns true if MI was recognized and processed.
1553 bool transferSpillOrRestoreInst(MachineInstr &MI);
1554
1555 /// Examines \p MI for any registers that it defines, and notifies trackers.
1556 void transferRegisterDef(MachineInstr &MI);
1557
1558 /// Copy one location to the other, accounting for movement of subregisters
1559 /// too.
1560 void performCopy(Register Src, Register Dst);
1561
1562 void accumulateFragmentMap(MachineInstr &MI);
1563
1564 /// Determine the machine value number referred to by (potentially several)
1565 /// DBG_PHI instructions. Block duplication and tail folding can duplicate
1566 /// DBG_PHIs, shifting the position where values in registers merge, and
1567 /// forming another mini-ssa problem to solve.
1568 /// \p Here the position of a DBG_INSTR_REF seeking a machine value number
1569 /// \p InstrNum Debug instruction number defined by DBG_PHI instructions.
1570 /// \returns The machine value number at position Here, or None.
1571 Optional<ValueIDNum> resolveDbgPHIs(MachineFunction &MF,
1572 ValueIDNum **MLiveOuts,
1573 ValueIDNum **MLiveIns, MachineInstr &Here,
1574 uint64_t InstrNum);
1575
1576 /// Step through the function, recording register definitions and movements
1577 /// in an MLocTracker. Convert the observations into a per-block transfer
1578 /// function in \p MLocTransfer, suitable for using with the machine value
1579 /// location dataflow problem.
1580 void
1581 produceMLocTransferFunction(MachineFunction &MF,
1582 SmallVectorImpl<MLocTransferMap> &MLocTransfer,
1583 unsigned MaxNumBlocks);
1584
1585 /// Solve the machine value location dataflow problem. Takes as input the
1586 /// transfer functions in \p MLocTransfer. Writes the output live-in and
1587 /// live-out arrays to the (initialized to zero) multidimensional arrays in
1588 /// \p MInLocs and \p MOutLocs. The outer dimension is indexed by block
1589 /// number, the inner by LocIdx.
1590 void mlocDataflow(ValueIDNum **MInLocs, ValueIDNum **MOutLocs,
1591 SmallVectorImpl<MLocTransferMap> &MLocTransfer);
1592
1593 /// Perform a control flow join (lattice value meet) of the values in machine
1594 /// locations at \p MBB. Follows the algorithm described in the file-comment,
1595 /// reading live-outs of predecessors from \p OutLocs, the current live ins
1596 /// from \p InLocs, and assigning the newly computed live ins back into
1597 /// \p InLocs. \returns two bools -- the first indicates whether a change
1598 /// was made, the second whether a lattice downgrade occurred. If the latter
1599 /// is true, revisiting this block is necessary.
1600 std::tuple<bool, bool>
1601 mlocJoin(MachineBasicBlock &MBB,
1602 SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
1603 ValueIDNum **OutLocs, ValueIDNum *InLocs);
1604
1605 /// Solve the variable value dataflow problem, for a single lexical scope.
1606 /// Uses the algorithm from the file comment to resolve control flow joins,
1607 /// although there are extra hacks, see vlocJoin. Reads the
1608 /// locations of values from the \p MInLocs and \p MOutLocs arrays (see
1609 /// mlocDataflow) and reads the variable values transfer function from
1610 /// \p AllTheVlocs. Live-in and Live-out variable values are stored locally,
1611 /// with the live-ins permanently stored to \p Output once the fixedpoint is
1612 /// reached.
1613 /// \p VarsWeCareAbout contains a collection of the variables in \p Scope
1614 /// that we should be tracking.
1615 /// \p AssignBlocks contains the set of blocks that aren't in \p Scope, but
1616 /// which do contain DBG_VALUEs, which VarLocBasedImpl tracks locations
1617 /// through.
1618 void vlocDataflow(const LexicalScope *Scope, const DILocation *DILoc,
1619 const SmallSet<DebugVariable, 4> &VarsWeCareAbout,
1620 SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks,
1621 LiveInsT &Output, ValueIDNum **MOutLocs,
1622 ValueIDNum **MInLocs,
1623 SmallVectorImpl<VLocTracker> &AllTheVLocs);
1624
1625 /// Compute the live-ins to a block, considering control flow merges according
1626 /// to the method in the file comment. Live out and live in variable values
1627 /// are stored in \p VLOCOutLocs and \p VLOCInLocs. The live-ins for \p MBB
1628 /// are computed and stored into \p VLOCInLocs. \returns true if the live-ins
1629 /// are modified.
1630 /// \p InLocsT Output argument, storage for calculated live-ins.
1631 /// \returns two bools -- the first indicates whether a change
1632 /// was made, the second whether a lattice downgrade occurred. If the latter
1633 /// is true, revisiting this block is necessary.
1634 std::tuple<bool, bool>
1635 vlocJoin(MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs,
1636 SmallPtrSet<const MachineBasicBlock *, 16> *VLOCVisited,
1637 unsigned BBNum, const SmallSet<DebugVariable, 4> &AllVars,
1638 ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
1639 SmallPtrSet<const MachineBasicBlock *, 8> &InScopeBlocks,
1640 SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore,
1641 DenseMap<DebugVariable, DbgValue> &InLocsT);
1642
1643 /// Continue exploration of the variable-value lattice, as explained in the
1644 /// file-level comment. \p OldLiveInLocation contains the current
1645 /// exploration position, from which we need to descend further. \p Values
1646 /// contains the set of live-in values, \p CurBlockRPONum the RPO number of
1647 /// the current block, and \p CandidateLocations a set of locations that
1648 /// should be considered as PHI locations, if we reach the bottom of the
1649 /// lattice. \returns true if we should downgrade; the value is the agreeing
1650 /// value number in a non-backedge predecessor.
1651 bool vlocDowngradeLattice(const MachineBasicBlock &MBB,
1652 const DbgValue &OldLiveInLocation,
1653 const SmallVectorImpl<InValueT> &Values,
1654 unsigned CurBlockRPONum);
1655
1656 /// For the given block and live-outs feeding into it, try to find a
1657 /// machine location where they all join. If a solution for all predecessors
1658 /// can't be found, a location where all non-backedge-predecessors join
1659 /// will be returned instead. While this method finds a join location, this
1660 /// says nothing as to whether it should be used.
1661 /// \returns Pair of value ID if found, and true when the correct value
1662 /// is available on all predecessor edges, or false if it's only available
1663 /// for non-backedge predecessors.
1664 std::tuple<Optional<ValueIDNum>, bool>
1665 pickVPHILoc(MachineBasicBlock &MBB, const DebugVariable &Var,
1666 const LiveIdxT &LiveOuts, ValueIDNum **MOutLocs,
1667 ValueIDNum **MInLocs,
1668 const SmallVectorImpl<MachineBasicBlock *> &BlockOrders);
1669
1670 /// Given the solutions to the two dataflow problems, machine value locations
1671 /// in \p MInLocs and live-in variable values in \p SavedLiveIns, runs the
1672 /// TransferTracker class over the function to produce live-in and transfer
1673 /// DBG_VALUEs, then inserts them. Groups of DBG_VALUEs are inserted in the
1674 /// order given by AllVarsNumbering -- this could be any stable order, but
1675 /// right now "order of appearence in function, when explored in RPO", so
1676 /// that we can compare explictly against VarLocBasedImpl.
1677 void emitLocations(MachineFunction &MF, LiveInsT SavedLiveIns,
1678 ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
1679 DenseMap<DebugVariable, unsigned> &AllVarsNumbering,
1680 const TargetPassConfig &TPC);
1681
1682 /// Boilerplate computation of some initial sets, artifical blocks and
1683 /// RPOT block ordering.
1684 void initialSetup(MachineFunction &MF);
1685
1686 bool ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC,
1687 unsigned InputBBLimit, unsigned InputDbgValLimit) override;
1688
1689public:
1690 /// Default construct and initialize the pass.
1691 InstrRefBasedLDV();
1692
1693 LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__))
1694 void dump_mloc_transfer(const MLocTransferMap &mloc_transfer) const;
1695
1696 bool isCalleeSaved(LocIdx L) {
1697 unsigned Reg = MTracker->LocIdxToLocID[L];
1698 for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
1699 if (CalleeSavedRegs.test(*RAI))
1700 return true;
1701 return false;
1702 }
1703};
1704
1705} // end anonymous namespace
1706
1707//===----------------------------------------------------------------------===//
1708// Implementation
1709//===----------------------------------------------------------------------===//
1710
1711ValueIDNum ValueIDNum::EmptyValue = {UINT_MAX(2147483647 *2U +1U), UINT_MAX(2147483647 *2U +1U), UINT_MAX(2147483647 *2U +1U)};
1712
1713/// Default construct and initialize the pass.
1714InstrRefBasedLDV::InstrRefBasedLDV() {}
1715
1716//===----------------------------------------------------------------------===//
1717// Debug Range Extension Implementation
1718//===----------------------------------------------------------------------===//
1719
1720#ifndef NDEBUG1
1721// Something to restore in the future.
1722// void InstrRefBasedLDV::printVarLocInMBB(..)
1723#endif
1724
1725SpillLoc
1726InstrRefBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
1727 assert(MI.hasOneMemOperand() &&(static_cast<void> (0))
1728 "Spill instruction does not have exactly one memory operand?")(static_cast<void> (0));
1729 auto MMOI = MI.memoperands_begin();
1730 const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
1731 assert(PVal->kind() == PseudoSourceValue::FixedStack &&(static_cast<void> (0))
1732 "Inconsistent memory operand in spill instruction")(static_cast<void> (0));
1733 int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
1734 const MachineBasicBlock *MBB = MI.getParent();
1735 Register Reg;
1736 StackOffset Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg);
1737 return {Reg, Offset};
1738}
1739
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) {
1743 if (!MI.isDebugValue())
1744 return false;
1745
1746 const DILocalVariable *Var = MI.getDebugVariable();
1747 const DIExpression *Expr = MI.getDebugExpression();
1748 const DILocation *DebugLoc = MI.getDebugLoc();
1749 const DILocation *InlinedAt = DebugLoc->getInlinedAt();
1750 assert(Var->isValidLocationForIntrinsic(DebugLoc) &&(static_cast<void> (0))
1751 "Expected inlined-at fields to agree")(static_cast<void> (0));
1752
1753 DebugVariable V(Var, Expr, InlinedAt);
1754 DbgValueProperties Properties(MI);
1755
1756 // If there are no instructions in this lexical scope, do no location tracking
1757 // at all, this variable shouldn't get a legitimate location range.
1758 auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get());
1759 if (Scope == nullptr)
1760 return true; // handled it; by doing nothing
1761
1762 // For now, ignore DBG_VALUE_LISTs when extending ranges. Allow it to
1763 // contribute to locations in this block, but don't propagate further.
1764 // Interpret it like a DBG_VALUE $noreg.
1765 if (MI.isDebugValueList()) {
1766 if (VTracker)
1767 VTracker->defVar(MI, Properties, None);
1768 if (TTracker)
1769 TTracker->redefVar(MI, Properties, None);
1770 return true;
1771 }
1772
1773 const MachineOperand &MO = MI.getOperand(0);
1774
1775 // MLocTracker needs to know that this register is read, even if it's only
1776 // read by a debug inst.
1777 if (MO.isReg() && MO.getReg() != 0)
1778 (void)MTracker->readReg(MO.getReg());
1779
1780 // If we're preparing for the second analysis (variables), the machine value
1781 // locations are already solved, and we report this DBG_VALUE and the value
1782 // it refers to to VLocTracker.
1783 if (VTracker) {
1784 if (MO.isReg()) {
1785 // Feed defVar the new variable location, or if this is a
1786 // DBG_VALUE $noreg, feed defVar None.
1787 if (MO.getReg())
1788 VTracker->defVar(MI, Properties, MTracker->readReg(MO.getReg()));
1789 else
1790 VTracker->defVar(MI, Properties, None);
1791 } else if (MI.getOperand(0).isImm() || MI.getOperand(0).isFPImm() ||
1792 MI.getOperand(0).isCImm()) {
1793 VTracker->defVar(MI, MI.getOperand(0));
1794 }
1795 }
1796
1797 // If performing final tracking of transfers, report this variable definition
1798 // to the TransferTracker too.
1799 if (TTracker)
1800 TTracker->redefVar(MI);
1801 return true;
1802}
1803
1804bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI,
1805 ValueIDNum **MLiveOuts,
1806 ValueIDNum **MLiveIns) {
1807 if (!MI.isDebugRef())
1808 return false;
1809
1810 // Only handle this instruction when we are building the variable value
1811 // transfer function.
1812 if (!VTracker)
1813 return false;
1814
1815 unsigned InstNo = MI.getOperand(0).getImm();
1816 unsigned OpNo = MI.getOperand(1).getImm();
1817
1818 const DILocalVariable *Var = MI.getDebugVariable();
1819 const DIExpression *Expr = MI.getDebugExpression();
1820 const DILocation *DebugLoc = MI.getDebugLoc();
1821 const DILocation *InlinedAt = DebugLoc->getInlinedAt();
1822 assert(Var->isValidLocationForIntrinsic(DebugLoc) &&(static_cast<void> (0))
1823 "Expected inlined-at fields to agree")(static_cast<void> (0));
1824
1825 DebugVariable V(Var, Expr, InlinedAt);
1826
1827 auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get());
1828 if (Scope == nullptr)
1829 return true; // Handled by doing nothing. This variable is never in scope.
1830
1831 const MachineFunction &MF = *MI.getParent()->getParent();
1832
1833 // Various optimizations may have happened to the value during codegen,
1834 // recorded in the value substitution table. Apply any substitutions to
1835 // the instruction / operand number in this DBG_INSTR_REF, and collect
1836 // any subregister extractions performed during optimization.
1837
1838 // Create dummy substitution with Src set, for lookup.
1839 auto SoughtSub =
1840 MachineFunction::DebugSubstitution({InstNo, OpNo}, {0, 0}, 0);
1841
1842 SmallVector<unsigned, 4> SeenSubregs;
1843 auto LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub);
1844 while (LowerBoundIt != MF.DebugValueSubstitutions.end() &&
1845 LowerBoundIt->Src == SoughtSub.Src) {
1846 std::tie(InstNo, OpNo) = LowerBoundIt->Dest;
1847 SoughtSub.Src = LowerBoundIt->Dest;
1848 if (unsigned Subreg = LowerBoundIt->Subreg)
1849 SeenSubregs.push_back(Subreg);
1850 LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub);
1851 }
1852
1853 // Default machine value number is <None> -- if no instruction defines
1854 // the corresponding value, it must have been optimized out.
1855 Optional<ValueIDNum> NewID = None;
1856
1857 // Try to lookup the instruction number, and find the machine value number
1858 // that it defines. It could be an instruction, or a PHI.
1859 auto InstrIt = DebugInstrNumToInstr.find(InstNo);
1860 auto PHIIt = std::lower_bound(DebugPHINumToValue.begin(),
1861 DebugPHINumToValue.end(), InstNo);
1862 if (InstrIt != DebugInstrNumToInstr.end()) {
1863 const MachineInstr &TargetInstr = *InstrIt->second.first;
1864 uint64_t BlockNo = TargetInstr.getParent()->getNumber();
1865
1866 // Pick out the designated operand.
1867 assert(OpNo < TargetInstr.getNumOperands())(static_cast<void> (0));
1868 const MachineOperand &MO = TargetInstr.getOperand(OpNo);
1869
1870 // Today, this can only be a register.
1871 assert(MO.isReg() && MO.isDef())(static_cast<void> (0));
1872
1873 unsigned LocID = MTracker->getLocID(MO.getReg(), false);
1874 LocIdx L = MTracker->LocIDToLocIdx[LocID];
1875 NewID = ValueIDNum(BlockNo, InstrIt->second.second, L);
1876 } else if (PHIIt != DebugPHINumToValue.end() && PHIIt->InstrNum == InstNo) {
1877 // It's actually a PHI value. Which value it is might not be obvious, use
1878 // the resolver helper to find out.
1879 NewID = resolveDbgPHIs(*MI.getParent()->getParent(), MLiveOuts, MLiveIns,
1880 MI, InstNo);
1881 }
1882
1883 // Apply any subregister extractions, in reverse. We might have seen code
1884 // like this:
1885 // CALL64 @foo, implicit-def $rax
1886 // %0:gr64 = COPY $rax
1887 // %1:gr32 = COPY %0.sub_32bit
1888 // %2:gr16 = COPY %1.sub_16bit
1889 // %3:gr8 = COPY %2.sub_8bit
1890 // In which case each copy would have been recorded as a substitution with
1891 // a subregister qualifier. Apply those qualifiers now.
1892 if (NewID && !SeenSubregs.empty()) {
1893 unsigned Offset = 0;
1894 unsigned Size = 0;
1895
1896 // Look at each subregister that we passed through, and progressively
1897 // narrow in, accumulating any offsets that occur. Substitutions should
1898 // only ever be the same or narrower width than what they read from;
1899 // iterate in reverse order so that we go from wide to small.
1900 for (unsigned Subreg : reverse(SeenSubregs)) {
1901 unsigned ThisSize = TRI->getSubRegIdxSize(Subreg);
1902 unsigned ThisOffset = TRI->getSubRegIdxOffset(Subreg);
1903 Offset += ThisOffset;
1904 Size = (Size == 0) ? ThisSize : std::min(Size, ThisSize);
1905 }
1906
1907 // If that worked, look for an appropriate subregister with the register
1908 // where the define happens. Don't look at values that were defined during
1909 // a stack write: we can't currently express register locations within
1910 // spills.
1911 LocIdx L = NewID->getLoc();
1912 if (NewID && !MTracker->isSpill(L)) {
1913 // Find the register class for the register where this def happened.
1914 // FIXME: no index for this?
1915 Register Reg = MTracker->LocIdxToLocID[L];
1916 const TargetRegisterClass *TRC = nullptr;
1917 for (auto *TRCI : TRI->regclasses())
1918 if (TRCI->contains(Reg))
1919 TRC = TRCI;
1920 assert(TRC && "Couldn't find target register class?")(static_cast<void> (0));
1921
1922 // If the register we have isn't the right size or in the right place,
1923 // Try to find a subregister inside it.
1924 unsigned MainRegSize = TRI->getRegSizeInBits(*TRC);
1925 if (Size != MainRegSize || Offset) {
1926 // Enumerate all subregisters, searching.
1927 Register NewReg = 0;
1928 for (MCSubRegIterator SRI(Reg, TRI, false); SRI.isValid(); ++SRI) {
1929 unsigned Subreg = TRI->getSubRegIndex(Reg, *SRI);
1930 unsigned SubregSize = TRI->getSubRegIdxSize(Subreg);
1931 unsigned SubregOffset = TRI->getSubRegIdxOffset(Subreg);
1932 if (SubregSize == Size && SubregOffset == Offset) {
1933 NewReg = *SRI;
1934 break;
1935 }
1936 }
1937
1938 // If we didn't find anything: there's no way to express our value.
1939 if (!NewReg) {
1940 NewID = None;
1941 } else {
1942 // Re-state the value as being defined within the subregister
1943 // that we found.
1944 LocIdx NewLoc = MTracker->lookupOrTrackRegister(NewReg);
1945 NewID = ValueIDNum(NewID->getBlock(), NewID->getInst(), NewLoc);
1946 }
1947 }
1948 } else {
1949 // If we can't handle subregisters, unset the new value.
1950 NewID = None;
1951 }
1952 }
1953
1954 // We, we have a value number or None. Tell the variable value tracker about
1955 // it. The rest of this LiveDebugValues implementation acts exactly the same
1956 // for DBG_INSTR_REFs as DBG_VALUEs (just, the former can refer to values that
1957 // aren't immediately available).
1958 DbgValueProperties Properties(Expr, false);
1959 VTracker->defVar(MI, Properties, NewID);
1960
1961 // If we're on the final pass through the function, decompose this INSTR_REF
1962 // into a plain DBG_VALUE.
1963 if (!TTracker)
1964 return true;
1965
1966 // Pick a location for the machine value number, if such a location exists.
1967 // (This information could be stored in TransferTracker to make it faster).
1968 Optional<LocIdx> FoundLoc = None;
1969 for (auto Location : MTracker->locations()) {
1970 LocIdx CurL = Location.Idx;
1971 ValueIDNum ID = MTracker->LocIdxToIDNum[CurL];
1972 if (NewID && ID == NewID) {
1973 // If this is the first location with that value, pick it. Otherwise,
1974 // consider whether it's a "longer term" location.
1975 if (!FoundLoc) {
1976 FoundLoc = CurL;
1977 continue;
1978 }
1979
1980 if (MTracker->isSpill(CurL))
1981 FoundLoc = CurL; // Spills are a longer term location.
1982 else if (!MTracker->isSpill(*FoundLoc) &&
1983 !MTracker->isSpill(CurL) &&
1984 !isCalleeSaved(*FoundLoc) &&
1985 isCalleeSaved(CurL))
1986 FoundLoc = CurL; // Callee saved regs are longer term than normal.
1987 }
1988 }
1989
1990 // Tell transfer tracker that the variable value has changed.
1991 TTracker->redefVar(MI, Properties, FoundLoc);
1992
1993 // If there was a value with no location; but the value is defined in a
1994 // later instruction in this block, this is a block-local use-before-def.
1995 if (!FoundLoc && NewID && NewID->getBlock() == CurBB &&
1996 NewID->getInst() > CurInst)
1997 TTracker->addUseBeforeDef(V, {MI.getDebugExpression(), false}, *NewID);
1998
1999 // Produce a DBG_VALUE representing what this DBG_INSTR_REF meant.
2000 // This DBG_VALUE is potentially a $noreg / undefined location, if
2001 // FoundLoc is None.
2002 // (XXX -- could morph the DBG_INSTR_REF in the future).
2003 MachineInstr *DbgMI = MTracker->emitLoc(FoundLoc, V, Properties);
2004 TTracker->PendingDbgValues.push_back(DbgMI);
2005 TTracker->flushDbgValues(MI.getIterator(), nullptr);
2006 return true;
2007}
2008
2009bool InstrRefBasedLDV::transferDebugPHI(MachineInstr &MI) {
2010 if (!MI.isDebugPHI())
2011 return false;
2012
2013 // Analyse these only when solving the machine value location problem.
2014 if (VTracker || TTracker)
2015 return true;
2016
2017 // First operand is the value location, either a stack slot or register.
2018 // Second is the debug instruction number of the original PHI.
2019 const MachineOperand &MO = MI.getOperand(0);
2020 unsigned InstrNum = MI.getOperand(1).getImm();
2021
2022 if (MO.isReg()) {
2023 // The value is whatever's currently in the register. Read and record it,
2024 // to be analysed later.
2025 Register Reg = MO.getReg();
2026 ValueIDNum Num = MTracker->readReg(Reg);
2027 auto PHIRec = DebugPHIRecord(
2028 {InstrNum, MI.getParent(), Num, MTracker->lookupOrTrackRegister(Reg)});
2029 DebugPHINumToValue.push_back(PHIRec);
2030 } else {
2031 // The value is whatever's in this stack slot.
2032 assert(MO.isFI())(static_cast<void> (0));
2033 unsigned FI = MO.getIndex();
2034
2035 // If the stack slot is dead, then this was optimized away.
2036 // FIXME: stack slot colouring should account for slots that get merged.
2037 if (MFI->isDeadObjectIndex(FI))
2038 return true;
2039
2040 // Identify this spill slot.
2041 Register Base;
2042 StackOffset Offs = TFI->getFrameIndexReference(*MI.getMF(), FI, Base);
2043 SpillLoc SL = {Base, Offs};
2044 Optional<ValueIDNum> Num = MTracker->readSpill(SL);
2045
2046 if (!Num)
2047 // Nothing ever writes to this slot. Curious, but nothing we can do.
2048 return true;
2049
2050 // Record this DBG_PHI for later analysis.
2051 auto DbgPHI = DebugPHIRecord(
2052 {InstrNum, MI.getParent(), *Num, *MTracker->getSpillMLoc(SL)});
2053 DebugPHINumToValue.push_back(DbgPHI);
2054 }
2055
2056 return true;
2057}
2058
2059void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) {
2060 // Meta Instructions do not affect the debug liveness of any register they
2061 // define.
2062 if (MI.isImplicitDef()) {
2063 // Except when there's an implicit def, and the location it's defining has
2064 // no value number. The whole point of an implicit def is to announce that
2065 // the register is live, without be specific about it's value. So define
2066 // a value if there isn't one already.
2067 ValueIDNum Num = MTracker->readReg(MI.getOperand(0).getReg());
2068 // Has a legitimate value -> ignore the implicit def.
2069 if (Num.getLoc() != 0)
2070 return;
2071 // Otherwise, def it here.
2072 } else if (MI.isMetaInstruction())
2073 return;
2074
2075 MachineFunction *MF = MI.getMF();
2076 const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
2077 Register SP = TLI->getStackPointerRegisterToSaveRestore();
2078
2079 // Find the regs killed by MI, and find regmasks of preserved regs.
2080 // Max out the number of statically allocated elements in `DeadRegs`, as this
2081 // prevents fallback to std::set::count() operations.
2082 SmallSet<uint32_t, 32> DeadRegs;
2083 SmallVector<const uint32_t *, 4> RegMasks;
2084 SmallVector<const MachineOperand *, 4> RegMaskPtrs;
2085 for (const MachineOperand &MO : MI.operands()) {
2086 // Determine whether the operand is a register def.
2087 if (MO.isReg() && MO.isDef() && MO.getReg() &&
2088 Register::isPhysicalRegister(MO.getReg()) &&
2089 !(MI.isCall() && MO.getReg() == SP)) {
2090 // Remove ranges of all aliased registers.
2091 for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
2092 // FIXME: Can we break out of this loop early if no insertion occurs?
2093 DeadRegs.insert(*RAI);
2094 } else if (MO.isRegMask()) {
2095 RegMasks.push_back(MO.getRegMask());
2096 RegMaskPtrs.push_back(&MO);
2097 }
2098 }
2099
2100 // Tell MLocTracker about all definitions, of regmasks and otherwise.
2101 for (uint32_t DeadReg : DeadRegs)
2102 MTracker->defReg(DeadReg, CurBB, CurInst);
2103
2104 for (auto *MO : RegMaskPtrs)
2105 MTracker->writeRegMask(MO, CurBB, CurInst);
2106
2107 if (!TTracker)
2108 return;
2109
2110 // When committing variable values to locations: tell transfer tracker that
2111 // we've clobbered things. It may be able to recover the variable from a
2112 // different location.
2113
2114 // Inform TTracker about any direct clobbers.
2115 for (uint32_t DeadReg : DeadRegs) {
2116 LocIdx Loc = MTracker->lookupOrTrackRegister(DeadReg);
2117 TTracker->clobberMloc(Loc, MI.getIterator(), false);
2118 }
2119
2120 // Look for any clobbers performed by a register mask. Only test locations
2121 // that are actually being tracked.
2122 for (auto L : MTracker->locations()) {
2123 // Stack locations can't be clobbered by regmasks.
2124 if (MTracker->isSpill(L.Idx))
2125 continue;
2126
2127 Register Reg = MTracker->LocIdxToLocID[L.Idx];
2128 for (auto *MO : RegMaskPtrs)
2129 if (MO->clobbersPhysReg(Reg))
2130 TTracker->clobberMloc(L.Idx, MI.getIterator(), false);
2131 }
2132}
2133
2134void InstrRefBasedLDV::performCopy(Register SrcRegNum, Register DstRegNum) {
2135 ValueIDNum SrcValue = MTracker->readReg(SrcRegNum);
2136
2137 MTracker->setReg(DstRegNum, SrcValue);
2138
2139 // In all circumstances, re-def the super registers. It's definitely a new
2140 // value now. This doesn't uniquely identify the composition of subregs, for
2141 // example, two identical values in subregisters composed in different
2142 // places would not get equal value numbers.
2143 for (MCSuperRegIterator SRI(DstRegNum, TRI); SRI.isValid(); ++SRI)
2144 MTracker->defReg(*SRI, CurBB, CurInst);
2145
2146 // If we're emulating VarLocBasedImpl, just define all the subregisters.
2147 // DBG_VALUEs of them will expect to be tracked from the DBG_VALUE, not
2148 // through prior copies.
2149 if (EmulateOldLDV) {
2150 for (MCSubRegIndexIterator DRI(DstRegNum, TRI); DRI.isValid(); ++DRI)
2151 MTracker->defReg(DRI.getSubReg(), CurBB, CurInst);
2152 return;
2153 }
2154
2155 // Otherwise, actually copy subregisters from one location to another.
2156 // XXX: in addition, any subregisters of DstRegNum that don't line up with
2157 // the source register should be def'd.
2158 for (MCSubRegIndexIterator SRI(SrcRegNum, TRI); SRI.isValid(); ++SRI) {
2159 unsigned SrcSubReg = SRI.getSubReg();
2160 unsigned SubRegIdx = SRI.getSubRegIndex();
2161 unsigned DstSubReg = TRI->getSubReg(DstRegNum, SubRegIdx);
2162 if (!DstSubReg)
2163 continue;
2164
2165 // Do copy. There are two matching subregisters, the source value should
2166 // have been def'd when the super-reg was, the latter might not be tracked
2167 // yet.
2168 // This will force SrcSubReg to be tracked, if it isn't yet.
2169 (void)MTracker->readReg(SrcSubReg);
2170 LocIdx SrcL = MTracker->getRegMLoc(SrcSubReg);
2171 assert(SrcL.asU64())(static_cast<void> (0));
2172 (void)MTracker->readReg(DstSubReg);
2173 LocIdx DstL = MTracker->getRegMLoc(DstSubReg);
2174 assert(DstL.asU64())(static_cast<void> (0));
2175 (void)DstL;
2176 ValueIDNum CpyValue = {SrcValue.getBlock(), SrcValue.getInst(), SrcL};
2177
2178 MTracker->setReg(DstSubReg, CpyValue);
2179 }
2180}
2181
2182bool InstrRefBasedLDV::isSpillInstruction(const MachineInstr &MI,
2183 MachineFunction *MF) {
2184 // TODO: Handle multiple stores folded into one.
2185 if (!MI.hasOneMemOperand())
2186 return false;
2187
2188 if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII))
2189 return false; // This is not a spill instruction, since no valid size was
2190 // returned from either function.
2191
2192 return true;
2193}
2194
2195bool InstrRefBasedLDV::isLocationSpill(const MachineInstr &MI,
2196 MachineFunction *MF, unsigned &Reg) {
2197 if (!isSpillInstruction(MI, MF))
2198 return false;
2199
2200 int FI;
2201 Reg = TII->isStoreToStackSlotPostFE(MI, FI);
2202 return Reg != 0;
2203}
2204
2205Optional<SpillLoc>
2206InstrRefBasedLDV::isRestoreInstruction(const MachineInstr &MI,
2207 MachineFunction *MF, unsigned &Reg) {
2208 if (!MI.hasOneMemOperand())
2209 return None;
2210
2211 // FIXME: Handle folded restore instructions with more than one memory
2212 // operand.
2213 if (MI.getRestoreSize(TII)) {
2214 Reg = MI.getOperand(0).getReg();
2215 return extractSpillBaseRegAndOffset(MI);
2216 }
2217 return None;
2218}
2219
2220bool InstrRefBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI) {
2221 // XXX -- it's too difficult to implement VarLocBasedImpl's stack location
2222 // limitations under the new model. Therefore, when comparing them, compare
2223 // versions that don't attempt spills or restores at all.
2224 if (EmulateOldLDV)
2225 return false;
2226
2227 MachineFunction *MF = MI.getMF();
2228 unsigned Reg;
2229 Optional<SpillLoc> Loc;
2230
2231 LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump();)do { } while (false);
2232
2233 // First, if there are any DBG_VALUEs pointing at a spill slot that is
2234 // written to, terminate that variable location. The value in memory
2235 // will have changed. DbgEntityHistoryCalculator doesn't try to detect this.
2236 if (isSpillInstruction(MI, MF)) {
2237 Loc = extractSpillBaseRegAndOffset(MI);
2238
2239 if (TTracker) {
2240 Optional<LocIdx> MLoc = MTracker->getSpillMLoc(*Loc);
2241 if (MLoc) {
2242 // Un-set this location before clobbering, so that we don't salvage
2243 // the variable location back to the same place.
2244 MTracker->setMLoc(*MLoc, ValueIDNum::EmptyValue);
2245 TTracker->clobberMloc(*MLoc, MI.getIterator());
2246 }
2247 }
2248 }
2249
2250 // Try to recognise spill and restore instructions that may transfer a value.
2251 if (isLocationSpill(MI, MF, Reg)) {
2252 Loc = extractSpillBaseRegAndOffset(MI);
2253 auto ValueID = MTracker->readReg(Reg);
2254
2255 // If the location is empty, produce a phi, signify it's the live-in value.
2256 if (ValueID.getLoc() == 0)
2257 ValueID = {CurBB, 0, MTracker->getRegMLoc(Reg)};
2258
2259 MTracker->setSpill(*Loc, ValueID);
2260 auto OptSpillLocIdx = MTracker->getSpillMLoc(*Loc);
2261 assert(OptSpillLocIdx && "Spill slot set but has no LocIdx?")(static_cast<void> (0));
2262 LocIdx SpillLocIdx = *OptSpillLocIdx;
2263
2264 // Tell TransferTracker about this spill, produce DBG_VALUEs for it.
2265 if (TTracker)
2266 TTracker->transferMlocs(MTracker->getRegMLoc(Reg), SpillLocIdx,
2267 MI.getIterator());
2268 } else {
2269 if (!(Loc = isRestoreInstruction(MI, MF, Reg)))
2270 return false;
2271
2272 // Is there a value to be restored?
2273 auto OptValueID = MTracker->readSpill(*Loc);
2274 if (OptValueID) {
2275 ValueIDNum ValueID = *OptValueID;
2276 LocIdx SpillLocIdx = *MTracker->getSpillMLoc(*Loc);
2277 // XXX -- can we recover sub-registers of this value? Until we can, first
2278 // overwrite all defs of the register being restored to.
2279 for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
2280 MTracker->defReg(*RAI, CurBB, CurInst);
2281
2282 // Now override the reg we're restoring to.
2283 MTracker->setReg(Reg, ValueID);
2284
2285 // Report this restore to the transfer tracker too.
2286 if (TTracker)
2287 TTracker->transferMlocs(SpillLocIdx, MTracker->getRegMLoc(Reg),
2288 MI.getIterator());
2289 } else {
2290 // There isn't anything in the location; not clear if this is a code path
2291 // that still runs. Def this register anyway just in case.
2292 for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
2293 MTracker->defReg(*RAI, CurBB, CurInst);
2294
2295 // Force the spill slot to be tracked.
2296 LocIdx L = MTracker->getOrTrackSpillLoc(*Loc);
2297
2298 // Set the restored value to be a machine phi number, signifying that it's
2299 // whatever the spills live-in value is in this block. Definitely has
2300 // a LocIdx due to the setSpill above.
2301 ValueIDNum ValueID = {CurBB, 0, L};
2302 MTracker->setReg(Reg, ValueID);
2303 MTracker->setSpill(*Loc, ValueID);
2304 }
2305 }
2306 return true;
2307}
2308
2309bool InstrRefBasedLDV::transferRegisterCopy(MachineInstr &MI) {
2310 auto DestSrc = TII->isCopyInstr(MI);
2311 if (!DestSrc)
2312 return false;
2313
2314 const MachineOperand *DestRegOp = DestSrc->Destination;
2315 const MachineOperand *SrcRegOp = DestSrc->Source;
2316
2317 auto isCalleeSavedReg = [&](unsigned Reg) {
2318 for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
2319 if (CalleeSavedRegs.test(*RAI))
2320 return true;
2321 return false;
2322 };
2323
2324 Register SrcReg = SrcRegOp->getReg();
2325 Register DestReg = DestRegOp->getReg();
2326
2327 // Ignore identity copies. Yep, these make it as far as LiveDebugValues.
2328 if (SrcReg == DestReg)
2329 return true;
2330
2331 // For emulating VarLocBasedImpl:
2332 // We want to recognize instructions where destination register is callee
2333 // saved register. If register that could be clobbered by the call is
2334 // included, there would be a great chance that it is going to be clobbered
2335 // soon. It is more likely that previous register, which is callee saved, is
2336 // going to stay unclobbered longer, even if it is killed.
2337 //
2338 // For InstrRefBasedImpl, we can track multiple locations per value, so
2339 // ignore this condition.
2340 if (EmulateOldLDV && !isCalleeSavedReg(DestReg))
2341 return false;
2342
2343 // InstrRefBasedImpl only followed killing copies.
2344 if (EmulateOldLDV && !SrcRegOp->isKill())
2345 return false;
2346
2347 // Copy MTracker info, including subregs if available.
2348 InstrRefBasedLDV::performCopy(SrcReg, DestReg);
2349
2350 // Only produce a transfer of DBG_VALUE within a block where old LDV
2351 // would have. We might make use of the additional value tracking in some
2352 // other way, later.
2353 if (TTracker && isCalleeSavedReg(DestReg) && SrcRegOp->isKill())
2354 TTracker->transferMlocs(MTracker->getRegMLoc(SrcReg),
2355 MTracker->getRegMLoc(DestReg), MI.getIterator());
2356
2357 // VarLocBasedImpl would quit tracking the old location after copying.
2358 if (EmulateOldLDV && SrcReg != DestReg)
2359 MTracker->defReg(SrcReg, CurBB, CurInst);
2360
2361 // Finally, the copy might have clobbered variables based on the destination
2362 // register. Tell TTracker about it, in case a backup location exists.
2363 if (TTracker) {
2364 for (MCRegAliasIterator RAI(DestReg, TRI, true); RAI.isValid(); ++RAI) {
2365 LocIdx ClobberedLoc = MTracker->getRegMLoc(*RAI);
2366 TTracker->clobberMloc(ClobberedLoc, MI.getIterator(), false);
2367 }
2368 }
2369
2370 return true;
2371}
2372
2373/// Accumulate a mapping between each DILocalVariable fragment and other
2374/// fragments of that DILocalVariable which overlap. This reduces work during
2375/// the data-flow stage from "Find any overlapping fragments" to "Check if the
2376/// known-to-overlap fragments are present".
2377/// \param MI A previously unprocessed DEBUG_VALUE instruction to analyze for
2378/// fragment usage.
2379void InstrRefBasedLDV::accumulateFragmentMap(MachineInstr &MI) {
2380 DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(),
2381 MI.getDebugLoc()->getInlinedAt());
2382 FragmentInfo ThisFragment = MIVar.getFragmentOrDefault();
2383
2384 // If this is the first sighting of this variable, then we are guaranteed
2385 // there are currently no overlapping fragments either. Initialize the set
2386 // of seen fragments, record no overlaps for the current one, and return.
2387 auto SeenIt = SeenFragments.find(MIVar.getVariable());
2388 if (SeenIt == SeenFragments.end()) {
2389 SmallSet<FragmentInfo, 4> OneFragment;
2390 OneFragment.insert(ThisFragment);
2391 SeenFragments.insert({MIVar.getVariable(), OneFragment});
2392
2393 OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}});
2394 return;
2395 }
2396
2397 // If this particular Variable/Fragment pair already exists in the overlap
2398 // map, it has already been accounted for.
2399 auto IsInOLapMap =
2400 OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}});
2401 if (!IsInOLapMap.second)
2402 return;
2403
2404 auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;
2405 auto &AllSeenFragments = SeenIt->second;
2406
2407 // Otherwise, examine all other seen fragments for this variable, with "this"
2408 // fragment being a previously unseen fragment. Record any pair of
2409 // overlapping fragments.
2410 for (auto &ASeenFragment : AllSeenFragments) {
2411 // Does this previously seen fragment overlap?
2412 if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) {
2413 // Yes: Mark the current fragment as being overlapped.
2414 ThisFragmentsOverlaps.push_back(ASeenFragment);
2415 // Mark the previously seen fragment as being overlapped by the current
2416 // one.
2417 auto ASeenFragmentsOverlaps =
2418 OverlapFragments.find({MIVar.getVariable(), ASeenFragment});
2419 assert(ASeenFragmentsOverlaps != OverlapFragments.end() &&(static_cast<void> (0))
2420 "Previously seen var fragment has no vector of overlaps")(static_cast<void> (0));
2421 ASeenFragmentsOverlaps->second.push_back(ThisFragment);
2422 }
2423 }
2424
2425 AllSeenFragments.insert(ThisFragment);
2426}
2427
2428void InstrRefBasedLDV::process(MachineInstr &MI, ValueIDNum **MLiveOuts,
2429 ValueIDNum **MLiveIns) {
2430 // Try to interpret an MI as a debug or transfer instruction. Only if it's
2431 // none of these should we interpret it's register defs as new value
2432 // definitions.
2433 if (transferDebugValue(MI))
2434 return;
2435 if (transferDebugInstrRef(MI, MLiveOuts, MLiveIns))
2436 return;
2437 if (transferDebugPHI(MI))
2438 return;
2439 if (transferRegisterCopy(MI))
2440 return;
2441 if (transferSpillOrRestoreInst(MI))
2442 return;
2443 transferRegisterDef(MI);
2444}
2445
2446void InstrRefBasedLDV::produceMLocTransferFunction(
2447 MachineFunction &MF, SmallVectorImpl<MLocTransferMap> &MLocTransfer,
2448 unsigned MaxNumBlocks) {
2449 // Because we try to optimize around register mask operands by ignoring regs
2450 // that aren't currently tracked, we set up something ugly for later: RegMask
2451 // operands that are seen earlier than the first use of a register, still need
2452 // to clobber that register in the transfer function. But this information
2453 // isn't actively recorded. Instead, we track each RegMask used in each block,
2454 // and accumulated the clobbered but untracked registers in each block into
2455 // the following bitvector. Later, if new values are tracked, we can add
2456 // appropriate clobbers.
2457 SmallVector<BitVector, 32> BlockMasks;
2458 BlockMasks.resize(MaxNumBlocks);
2459
2460 // Reserve one bit per register for the masks described above.
2461 unsigned BVWords = MachineOperand::getRegMaskSize(TRI->getNumRegs());
2462 for (auto &BV : BlockMasks)
2463 BV.resize(TRI->getNumRegs(), true);
2464
2465 // Step through all instructions and inhale the transfer function.
2466 for (auto &MBB : MF) {
2467 // Object fields that are read by trackers to know where we are in the
2468 // function.
2469 CurBB = MBB.getNumber();
2470 CurInst = 1;
2471
2472 // Set all machine locations to a PHI value. For transfer function
2473 // production only, this signifies the live-in value to the block.
2474 MTracker->reset();
2475 MTracker->setMPhis(CurBB);
2476
2477 // Step through each instruction in this block.
2478 for (auto &MI : MBB) {
2479 process(MI);
2480 // Also accumulate fragment map.
2481 if (MI.isDebugValue())
2482 accumulateFragmentMap(MI);
2483
2484 // Create a map from the instruction number (if present) to the
2485 // MachineInstr and its position.
2486 if (uint64_t InstrNo = MI.peekDebugInstrNum()) {
2487 auto InstrAndPos = std::make_pair(&MI, CurInst);
2488 auto InsertResult =
2489 DebugInstrNumToInstr.insert(std::make_pair(InstrNo, InstrAndPos));
2490
2491 // There should never be duplicate instruction numbers.
2492 assert(InsertResult.second)(static_cast<void> (0));
2493 (void)InsertResult;
2494 }
2495
2496 ++CurInst;
2497 }
2498
2499 // Produce the transfer function, a map of machine location to new value. If
2500 // any machine location has the live-in phi value from the start of the
2501 // block, it's live-through and doesn't need recording in the transfer
2502 // function.
2503 for (auto Location : MTracker->locations()) {
2504 LocIdx Idx = Location.Idx;
2505 ValueIDNum &P = Location.Value;
2506 if (P.isPHI() && P.getLoc() == Idx.asU64())
2507 continue;
2508
2509 // Insert-or-update.
2510 auto &TransferMap = MLocTransfer[CurBB];
2511 auto Result = TransferMap.insert(std::make_pair(Idx.asU64(), P));
2512 if (!Result.second)
2513 Result.first->second = P;
2514 }
2515
2516 // Accumulate any bitmask operands into the clobberred reg mask for this
2517 // block.
2518 for (auto &P : MTracker->Masks) {
2519 BlockMasks[CurBB].clearBitsNotInMask(P.first->getRegMask(), BVWords);
2520 }
2521 }
2522
2523 // Compute a bitvector of all the registers that are tracked in this block.
2524 const TargetLowering *TLI = MF.getSubtarget().getTargetLowering();
2525 Register SP = TLI->getStackPointerRegisterToSaveRestore();
2526 BitVector UsedRegs(TRI->getNumRegs());
2527 for (auto Location : MTracker->locations()) {
2528 unsigned ID = MTracker->LocIdxToLocID[Location.Idx];
2529 if (ID >= TRI->getNumRegs() || ID == SP)
2530 continue;
2531 UsedRegs.set(ID);
2532 }
2533
2534 // Check that any regmask-clobber of a register that gets tracked, is not
2535 // live-through in the transfer function. It needs to be clobbered at the
2536 // very least.
2537 for (unsigned int I = 0; I < MaxNumBlocks; ++I) {
2538 BitVector &BV = BlockMasks[I];
2539 BV.flip();
2540 BV &= UsedRegs;
2541 // This produces all the bits that we clobber, but also use. Check that
2542 // they're all clobbered or at least set in the designated transfer
2543 // elem.
2544 for (unsigned Bit : BV.set_bits()) {
2545 unsigned ID = MTracker->getLocID(Bit, false);
2546 LocIdx Idx = MTracker->LocIDToLocIdx[ID];
2547 auto &TransferMap = MLocTransfer[I];
2548
2549 // Install a value representing the fact that this location is effectively
2550 // written to in this block. As there's no reserved value, instead use
2551 // a value number that is never generated. Pick the value number for the
2552 // first instruction in the block, def'ing this location, which we know
2553 // this block never used anyway.
2554 ValueIDNum NotGeneratedNum = ValueIDNum(I, 1, Idx);
2555 auto Result =
2556 TransferMap.insert(std::make_pair(Idx.asU64(), NotGeneratedNum));
2557 if (!Result.second) {
2558 ValueIDNum &ValueID = Result.first->second;
2559 if (ValueID.getBlock() == I && ValueID.isPHI())
2560 // It was left as live-through. Set it to clobbered.
2561 ValueID = NotGeneratedNum;
2562 }
2563 }
2564 }
2565}
2566
2567std::tuple<bool, bool>
2568InstrRefBasedLDV::mlocJoin(MachineBasicBlock &MBB,
2569 SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
2570 ValueIDNum **OutLocs, ValueIDNum *InLocs) {
2571 LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n")do { } while (false);
2572 bool Changed = false;
2573 bool DowngradeOccurred = false;
2574
2575 // Collect predecessors that have been visited. Anything that hasn't been
2576 // visited yet is a backedge on the first iteration, and the meet of it's
2577 // lattice value for all locations will be unaffected.
2578 SmallVector<const MachineBasicBlock *, 8> BlockOrders;
2579 for (auto Pred : MBB.predecessors()) {
2580 if (Visited.count(Pred)) {
2581 BlockOrders.push_back(Pred);
2582 }
2583 }
2584
2585 // Visit predecessors in RPOT order.
2586 auto Cmp = [&](const MachineBasicBlock *A, const MachineBasicBlock *B) {
2587 return BBToOrder.find(A)->second < BBToOrder.find(B)->second;
2588 };
2589 llvm::sort(BlockOrders, Cmp);
2590
2591 // Skip entry block.
2592 if (BlockOrders.size() == 0)
2593 return std::tuple<bool, bool>(false, false);
2594
2595 // Step through all machine locations, then look at each predecessor and
2596 // detect disagreements.
2597 unsigned ThisBlockRPO = BBToOrder.find(&MBB)->second;
2598 for (auto Location : MTracker->locations()) {
2599 LocIdx Idx = Location.Idx;
2600 // Pick out the first predecessors live-out value for this location. It's
2601 // guaranteed to be not a backedge, as we order by RPO.
2602 ValueIDNum BaseVal = OutLocs[BlockOrders[0]->getNumber()][Idx.asU64()];
2603
2604 // Some flags for whether there's a disagreement, and whether it's a
2605 // disagreement with a backedge or not.
2606 bool Disagree = false;
2607 bool NonBackEdgeDisagree = false;
2608
2609 // Loop around everything that wasn't 'base'.
2610 for (unsigned int I = 1; I < BlockOrders.size(); ++I) {
2611 auto *MBB = BlockOrders[I];
2612 if (BaseVal != OutLocs[MBB->getNumber()][Idx.asU64()]) {
2613 // Live-out of a predecessor disagrees with the first predecessor.
2614 Disagree = true;
2615
2616 // Test whether it's a disagreemnt in the backedges or not.
2617 if (BBToOrder.find(MBB)->second < ThisBlockRPO) // might be self b/e
2618 NonBackEdgeDisagree = true;
2619 }
2620 }
2621
2622 bool OverRide = false;
2623 if (Disagree && !NonBackEdgeDisagree) {
2624 // Only the backedges disagree. Consider demoting the livein
2625 // lattice value, as per the file level comment. The value we consider
2626 // demoting to is the value that the non-backedge predecessors agree on.
2627 // The order of values is that non-PHIs are \top, a PHI at this block
2628 // \bot, and phis between the two are ordered by their RPO number.
2629 // If there's no agreement, or we've already demoted to this PHI value
2630 // before, replace with a PHI value at this block.
2631
2632 // Calculate order numbers: zero means normal def, nonzero means RPO
2633 // number.
2634 unsigned BaseBlockRPONum = BBNumToRPO[BaseVal.getBlock()] + 1;
2635 if (!BaseVal.isPHI())
2636 BaseBlockRPONum = 0;
2637
2638 ValueIDNum &InLocID = InLocs[Idx.asU64()];
2639 unsigned InLocRPONum = BBNumToRPO[InLocID.getBlock()] + 1;
2640 if (!InLocID.isPHI())
2641 InLocRPONum = 0;
2642
2643 // Should we ignore the disagreeing backedges, and override with the
2644 // value the other predecessors agree on (in "base")?
2645 unsigned ThisBlockRPONum = BBNumToRPO[MBB.getNumber()] + 1;
2646 if (BaseBlockRPONum > InLocRPONum && BaseBlockRPONum < ThisBlockRPONum) {
2647 // Override.
2648 OverRide = true;
2649 DowngradeOccurred = true;
2650 }
2651 }
2652 // else: if we disagree in the non-backedges, then this is definitely
2653 // a control flow merge where different values merge. Make it a PHI.
2654
2655 // Generate a phi...
2656 ValueIDNum PHI = {(uint64_t)MBB.getNumber(), 0, Idx};
2657 ValueIDNum NewVal = (Disagree && !OverRide) ? PHI : BaseVal;
2658 if (InLocs[Idx.asU64()] != NewVal) {
2659 Changed |= true;
2660 InLocs[Idx.asU64()] = NewVal;
2661 }
2662 }
2663
2664 // TODO: Reimplement NumInserted and NumRemoved.
2665 return std::tuple<bool, bool>(Changed, DowngradeOccurred);
2666}
2667
2668void InstrRefBasedLDV::mlocDataflow(
2669 ValueIDNum **MInLocs, ValueIDNum **MOutLocs,
2670 SmallVectorImpl<MLocTransferMap> &MLocTransfer) {
2671 std::priority_queue<unsigned int, std::vector<unsigned int>,
2672 std::greater<unsigned int>>
2673 Worklist, Pending;
2674
2675 // We track what is on the current and pending worklist to avoid inserting
2676 // the same thing twice. We could avoid this with a custom priority queue,
2677 // but this is probably not worth it.
2678 SmallPtrSet<MachineBasicBlock *, 16> OnPending, OnWorklist;
2679
2680 // Initialize worklist with every block to be visited.
2681 for (unsigned int I = 0; I < BBToOrder.size(); ++I) {
7
Assuming the condition is false
8
Loop condition is false. Execution continues on line 2686
2682 Worklist.push(I);
2683 OnWorklist.insert(OrderToBB[I]);
2684 }
2685
2686 MTracker->reset();
2687
2688 // Set inlocs for entry block -- each as a PHI at the entry block. Represents
2689 // the incoming value to the function.
2690 MTracker->setMPhis(0);
2691 for (auto Location : MTracker->locations())
2692 MInLocs[0][Location.Idx.asU64()] = Location.Value;
9
Use of zero-allocated memory
2693
2694 SmallPtrSet<const MachineBasicBlock *, 16> Visited;
2695 while (!Worklist.empty() || !Pending.empty()) {
2696 // Vector for storing the evaluated block transfer function.
2697 SmallVector<std::pair<LocIdx, ValueIDNum>, 32> ToRemap;
2698
2699 while (!Worklist.empty()) {
2700 MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
2701 CurBB = MBB->getNumber();
2702 Worklist.pop();
2703
2704 // Join the values in all predecessor blocks.
2705 bool InLocsChanged, DowngradeOccurred;
2706 std::tie(InLocsChanged, DowngradeOccurred) =
2707 mlocJoin(*MBB, Visited, MOutLocs, MInLocs[CurBB]);
2708 InLocsChanged |= Visited.insert(MBB).second;
2709
2710 // If a downgrade occurred, book us in for re-examination on the next
2711 // iteration.
2712 if (DowngradeOccurred && OnPending.insert(MBB).second)
2713 Pending.push(BBToOrder[MBB]);
2714
2715 // Don't examine transfer function if we've visited this loc at least
2716 // once, and inlocs haven't changed.
2717 if (!InLocsChanged)
2718 continue;
2719
2720 // Load the current set of live-ins into MLocTracker.
2721 MTracker->loadFromArray(MInLocs[CurBB], CurBB);
2722
2723 // Each element of the transfer function can be a new def, or a read of
2724 // a live-in value. Evaluate each element, and store to "ToRemap".
2725 ToRemap.clear();
2726 for (auto &P : MLocTransfer[CurBB]) {
2727 if (P.second.getBlock() == CurBB && P.second.isPHI()) {
2728 // This is a movement of whatever was live in. Read it.
2729 ValueIDNum NewID = MTracker->getNumAtPos(P.second.getLoc());
2730 ToRemap.push_back(std::make_pair(P.first, NewID));
2731 } else {
2732 // It's a def. Just set it.
2733 assert(P.second.getBlock() == CurBB)(static_cast<void> (0));
2734 ToRemap.push_back(std::make_pair(P.first, P.second));
2735 }
2736 }
2737
2738 // Commit the transfer function changes into mloc tracker, which
2739 // transforms the contents of the MLocTracker into the live-outs.
2740 for (auto &P : ToRemap)
2741 MTracker->setMLoc(P.first, P.second);
2742
2743 // Now copy out-locs from mloc tracker into out-loc vector, checking
2744 // whether changes have occurred. These changes can have come from both
2745 // the transfer function, and mlocJoin.
2746 bool OLChanged = false;
2747 for (auto Location : MTracker->locations()) {
2748 OLChanged |= MOutLocs[CurBB][Location.Idx.asU64()] != Location.Value;
2749 MOutLocs[CurBB][Location.Idx.asU64()] = Location.Value;
2750 }
2751
2752 MTracker->reset();
2753
2754 // No need to examine successors again if out-locs didn't change.
2755 if (!OLChanged)
2756 continue;
2757
2758 // All successors should be visited: put any back-edges on the pending
2759 // list for the next dataflow iteration, and any other successors to be
2760 // visited this iteration, if they're not going to be already.
2761 for (auto s : MBB->successors()) {
2762 // Does branching to this successor represent a back-edge?
2763 if (BBToOrder[s] > BBToOrder[MBB]) {
2764 // No: visit it during this dataflow iteration.
2765 if (OnWorklist.insert(s).second)
2766 Worklist.push(BBToOrder[s]);
2767 } else {
2768 // Yes: visit it on the next iteration.
2769 if (OnPending.insert(s).second)
2770 Pending.push(BBToOrder[s]);
2771 }
2772 }
2773 }
2774
2775 Worklist.swap(Pending);
2776 std::swap(OnPending, OnWorklist);
2777 OnPending.clear();
2778 // At this point, pending must be empty, since it was just the empty
2779 // worklist
2780 assert(Pending.empty() && "Pending should be empty")(static_cast<void> (0));
2781 }
2782
2783 // Once all the live-ins don't change on mlocJoin(), we've reached a
2784 // fixedpoint.
2785}
2786
2787bool InstrRefBasedLDV::vlocDowngradeLattice(
2788 const MachineBasicBlock &MBB, const DbgValue &OldLiveInLocation,
2789 const SmallVectorImpl<InValueT> &Values, unsigned CurBlockRPONum) {
2790 // Ranking value preference: see file level comment, the highest rank is
2791 // a plain def, followed by PHI values in reverse post-order. Numerically,
2792 // we assign all defs the rank '0', all PHIs their blocks RPO number plus
2793 // one, and consider the lowest value the highest ranked.
2794 int OldLiveInRank = BBNumToRPO[OldLiveInLocation.ID.getBlock()] + 1;
2795 if (!OldLiveInLocation.ID.isPHI())
2796 OldLiveInRank = 0;
2797
2798 // Allow any unresolvable conflict to be over-ridden.
2799 if (OldLiveInLocation.Kind == DbgValue::NoVal) {
2800 // Although if it was an unresolvable conflict from _this_ block, then
2801 // all other seeking of downgrades and PHIs must have failed before hand.
2802 if (OldLiveInLocation.BlockNo == (unsigned)MBB.getNumber())
2803 return false;
2804 OldLiveInRank = INT_MIN(-2147483647 -1);
2805 }
2806
2807 auto &InValue = *Values[0].second;
2808
2809 if (InValue.Kind == DbgValue::Const || InValue.Kind == DbgValue::NoVal)
2810 return false;
2811
2812 unsigned ThisRPO = BBNumToRPO[InValue.ID.getBlock()];
2813 int ThisRank = ThisRPO + 1;
2814 if (!InValue.ID.isPHI())
2815 ThisRank = 0;
2816
2817 // Too far down the lattice?
2818 if (ThisRPO >= CurBlockRPONum)
2819 return false;
2820
2821 // Higher in the lattice than what we've already explored?
2822 if (ThisRank <= OldLiveInRank)
2823 return false;
2824
2825 return true;
2826}
2827
2828std::tuple<Optional<ValueIDNum>, bool> InstrRefBasedLDV::pickVPHILoc(
2829 MachineBasicBlock &MBB, const DebugVariable &Var, const LiveIdxT &LiveOuts,
2830 ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
2831 const SmallVectorImpl<MachineBasicBlock *> &BlockOrders) {
2832 // Collect a set of locations from predecessor where its live-out value can
2833 // be found.
2834 SmallVector<SmallVector<LocIdx, 4>, 8> Locs;
2835 unsigned NumLocs = MTracker->getNumLocs();
2836 unsigned BackEdgesStart = 0;
2837
2838 for (auto p : BlockOrders) {
2839 // Pick out where backedges start in the list of predecessors. Relies on
2840 // BlockOrders being sorted by RPO.
2841 if (BBToOrder[p] < BBToOrder[&MBB])
2842 ++BackEdgesStart;
2843
2844 // For each predecessor, create a new set of locations.
2845 Locs.resize(Locs.size() + 1);
2846 unsigned ThisBBNum = p->getNumber();
2847 auto LiveOutMap = LiveOuts.find(p);
2848 if (LiveOutMap == LiveOuts.end())
2849 // This predecessor isn't in scope, it must have no live-in/live-out
2850 // locations.
2851 continue;
2852
2853 auto It = LiveOutMap->second->find(Var);
2854 if (It == LiveOutMap->second->end())
2855 // There's no value recorded for this variable in this predecessor,
2856 // leave an empty set of locations.
2857 continue;
2858
2859 const DbgValue &OutVal = It->second;
2860
2861 if (OutVal.Kind == DbgValue::Const || OutVal.Kind == DbgValue::NoVal)
2862 // Consts and no-values cannot have locations we can join on.
2863 continue;
2864
2865 assert(OutVal.Kind == DbgValue::Proposed || OutVal.Kind == DbgValue::Def)(static_cast<void> (0));
2866 ValueIDNum ValToLookFor = OutVal.ID;
2867
2868 // Search the live-outs of the predecessor for the specified value.
2869 for (unsigned int I = 0; I < NumLocs; ++I) {
2870 if (MOutLocs[ThisBBNum][I] == ValToLookFor)
2871 Locs.back().push_back(LocIdx(I));
2872 }
2873 }
2874
2875 // If there were no locations at all, return an empty result.
2876 if (Locs.empty())
2877 return std::tuple<Optional<ValueIDNum>, bool>(None, false);
2878
2879 // Lambda for seeking a common location within a range of location-sets.
2880 using LocsIt = SmallVector<SmallVector<LocIdx, 4>, 8>::iterator;
2881 auto SeekLocation =
2882 [&Locs](llvm::iterator_range<LocsIt> SearchRange) -> Optional<LocIdx> {
2883 // Starting with the first set of locations, take the intersection with
2884 // subsequent sets.
2885 SmallVector<LocIdx, 4> base = Locs[0];
2886 for (auto &S : SearchRange) {
2887 SmallVector<LocIdx, 4> new_base;
2888 std::set_intersection(base.begin(), base.end(), S.begin(), S.end(),
2889 std::inserter(new_base, new_base.begin()));
2890 base = new_base;
2891 }
2892 if (base.empty())
2893 return None;
2894
2895 // We now have a set of LocIdxes that contain the right output value in
2896 // each of the predecessors. Pick the lowest; if there's a register loc,
2897 // that'll be it.
2898 return *base.begin();
2899 };
2900
2901 // Search for a common location for all predecessors. If we can't, then fall
2902 // back to only finding a common location between non-backedge predecessors.
2903 bool ValidForAllLocs = true;
2904 auto TheLoc = SeekLocation(Locs);
2905 if (!TheLoc) {
2906 ValidForAllLocs = false;
2907 TheLoc =
2908 SeekLocation(make_range(Locs.begin(), Locs.begin() + BackEdgesStart));
2909 }
2910
2911 if (!TheLoc)
2912 return std::tuple<Optional<ValueIDNum>, bool>(None, false);
2913
2914 // Return a PHI-value-number for the found location.
2915 LocIdx L = *TheLoc;
2916 ValueIDNum PHIVal = {(unsigned)MBB.getNumber(), 0, L};
2917 return std::tuple<Optional<ValueIDNum>, bool>(PHIVal, ValidForAllLocs);
2918}
2919
2920std::tuple<bool, bool> InstrRefBasedLDV::vlocJoin(
2921 MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs,
2922 SmallPtrSet<const MachineBasicBlock *, 16> *VLOCVisited, unsigned BBNum,
2923 const SmallSet<DebugVariable, 4> &AllVars, ValueIDNum **MOutLocs,
2924 ValueIDNum **MInLocs,
2925 SmallPtrSet<const MachineBasicBlock *, 8> &InScopeBlocks,
2926 SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore,
2927 DenseMap<DebugVariable, DbgValue> &InLocsT) {
2928 bool DowngradeOccurred = false;
2929
2930 // To emulate VarLocBasedImpl, process this block if it's not in scope but
2931 // _does_ assign a variable value. No live-ins for this scope are transferred
2932 // in though, so we can return immediately.
2933 if (InScopeBlocks.count(&MBB) == 0 && !ArtificialBlocks.count(&MBB)) {
2934 if (VLOCVisited)
2935 return std::tuple<bool, bool>(true, false);
2936 return std::tuple<bool, bool>(false, false);
2937 }
2938
2939 LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n")do { } while (false);
2940 bool Changed = false;
2941
2942 // Find any live-ins computed in a prior iteration.
2943 auto ILSIt = VLOCInLocs.find(&MBB);
2944 assert(ILSIt != VLOCInLocs.end())(static_cast<void> (0));
2945 auto &ILS = *ILSIt->second;
2946
2947 // Order predecessors by RPOT order, for exploring them in that order.
2948 SmallVector<MachineBasicBlock *, 8> BlockOrders(MBB.predecessors());
2949
2950 auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
2951 return BBToOrder[A] < BBToOrder[B];
2952 };
2953
2954 llvm::sort(BlockOrders, Cmp);
2955
2956 unsigned CurBlockRPONum = BBToOrder[&MBB];
2957
2958 // Force a re-visit to loop heads in the first dataflow iteration.
2959 // FIXME: if we could "propose" Const values this wouldn't be needed,
2960 // because they'd need to be confirmed before being emitted.
2961 if (!BlockOrders.empty() &&
2962 BBToOrder[BlockOrders[BlockOrders.size() - 1]] >= CurBlockRPONum &&
2963 VLOCVisited)
2964 DowngradeOccurred = true;
2965
2966 auto ConfirmValue = [&InLocsT](const DebugVariable &DV, DbgValue VR) {
2967 auto Result = InLocsT.insert(std::make_pair(DV, VR));
2968 (void)Result;
2969 assert(Result.second)(static_cast<void> (0));
2970 };
2971
2972 auto ConfirmNoVal = [&ConfirmValue, &MBB](const DebugVariable &Var, const DbgValueProperties &Properties) {
2973 DbgValue NoLocPHIVal(MBB.getNumber(), Properties, DbgValue::NoVal);
2974
2975 ConfirmValue(Var, NoLocPHIVal);
2976 };
2977
2978 // Attempt to join the values for each variable.
2979 for (auto &Var : AllVars) {
2980 // Collect all the DbgValues for this variable.
2981 SmallVector<InValueT, 8> Values;
2982 bool Bail = false;
2983 unsigned BackEdgesStart = 0;
2984 for (auto p : BlockOrders) {
2985 // If the predecessor isn't in scope / to be explored, we'll never be
2986 // able to join any locations.
2987 if (!BlocksToExplore.contains(p)) {
2988 Bail = true;
2989 break;
2990 }
2991
2992 // Don't attempt to handle unvisited predecessors: they're implicitly
2993 // "unknown"s in the lattice.
2994 if (VLOCVisited && !VLOCVisited->count(p))
2995 continue;
2996
2997 // If the predecessors OutLocs is absent, there's not much we can do.
2998 auto OL = VLOCOutLocs.find(p);
2999 if (OL == VLOCOutLocs.end()) {
3000 Bail = true;
3001 break;
3002 }
3003
3004 // No live-out value for this predecessor also means we can't produce
3005 // a joined value.
3006 auto VIt = OL->second->find(Var);
3007 if (VIt == OL->second->end()) {
3008 Bail = true;
3009 break;
3010 }
3011
3012 // Keep track of where back-edges begin in the Values vector. Relies on
3013 // BlockOrders being sorted by RPO.
3014 unsigned ThisBBRPONum = BBToOrder[p];
3015 if (ThisBBRPONum < CurBlockRPONum)
3016 ++BackEdgesStart;
3017
3018 Values.push_back(std::make_pair(p, &VIt->second));
3019 }
3020
3021 // If there were no values, or one of the predecessors couldn't have a
3022 // value, then give up immediately. It's not safe to produce a live-in
3023 // value.
3024 if (Bail || Values.size() == 0)
3025 continue;
3026
3027 // Enumeration identifying the current state of the predecessors values.
3028 enum {
3029 Unset = 0,
3030 Agreed, // All preds agree on the variable value.
3031 PropDisagree, // All preds agree, but the value kind is Proposed in some.
3032 BEDisagree, // Only back-edges disagree on variable value.
3033 PHINeeded, // Non-back-edge predecessors have conflicing values.
3034 NoSolution // Conflicting Value metadata makes solution impossible.
3035 } OurState = Unset;
3036
3037 // All (non-entry) blocks have at least one non-backedge predecessor.
3038 // Pick the variable value from the first of these, to compare against
3039 // all others.
3040 const DbgValue &FirstVal = *Values[0].second;
3041 const ValueIDNum &FirstID = FirstVal.ID;
3042
3043 // Scan for variable values that can't be resolved: if they have different
3044 // DIExpressions, different indirectness, or are mixed constants /
3045 // non-constants.
3046 for (auto &V : Values) {
3047 if (V.second->Properties != FirstVal.Properties)
3048 OurState = NoSolution;
3049 if (V.second->Kind == DbgValue::Const && FirstVal.Kind != DbgValue::Const)
3050 OurState = NoSolution;
3051 }
3052
3053 // Flags diagnosing _how_ the values disagree.
3054 bool NonBackEdgeDisagree = false;
3055 bool DisagreeOnPHINess = false;
3056 bool IDDisagree = false;
3057 bool Disagree = false;
3058 if (OurState == Unset) {
3059 for (auto &V : Values) {
3060 if (*V.second == FirstVal)
3061 continue; // No disagreement.
3062
3063 Disagree = true;
3064
3065 // Flag whether the value number actually diagrees.
3066 if (V.second->ID != FirstID)
3067 IDDisagree = true;
3068
3069 // Distinguish whether disagreement happens in backedges or not.
3070 // Relies on Values (and BlockOrders) being sorted by RPO.
3071 unsigned ThisBBRPONum = BBToOrder[V.first];
3072 if (ThisBBRPONum < CurBlockRPONum)
3073 NonBackEdgeDisagree = true;
3074
3075 // Is there a difference in whether the value is definite or only
3076 // proposed?
3077 if (V.second->Kind != FirstVal.Kind &&
3078 (V.second->Kind == DbgValue::Proposed ||
3079 V.second->Kind == DbgValue::Def) &&
3080 (FirstVal.Kind == DbgValue::Proposed ||
3081 FirstVal.Kind == DbgValue::Def))
3082 DisagreeOnPHINess = true;
3083 }
3084
3085 // Collect those flags together and determine an overall state for
3086 // what extend the predecessors agree on a live-in value.
3087 if (!Disagree)
3088 OurState = Agreed;
3089 else if (!IDDisagree && DisagreeOnPHINess)
3090 OurState = PropDisagree;
3091 else if (!NonBackEdgeDisagree)
3092 OurState = BEDisagree;
3093 else
3094 OurState = PHINeeded;
3095 }
3096
3097 // An extra indicator: if we only disagree on whether the value is a
3098 // Def, or proposed, then also flag whether that disagreement happens
3099 // in backedges only.
3100 bool PropOnlyInBEs = Disagree && !IDDisagree && DisagreeOnPHINess &&
3101 !NonBackEdgeDisagree && FirstVal.Kind == DbgValue::Def;
3102
3103 const auto &Properties = FirstVal.Properties;
3104
3105 auto OldLiveInIt = ILS.find(Var);
3106 const DbgValue *OldLiveInLocation =
3107 (OldLiveInIt != ILS.end()) ? &OldLiveInIt->second : nullptr;
3108
3109 bool OverRide = false;
3110 if (OurState == BEDisagree && OldLiveInLocation) {
3111 // Only backedges disagree: we can consider downgrading. If there was a
3112 // previous live-in value, use it to work out whether the current
3113 // incoming value represents a lattice downgrade or not.
3114 OverRide =
3115 vlocDowngradeLattice(MBB, *OldLiveInLocation, Values, CurBlockRPONum);
3116 }
3117
3118 // Use the current state of predecessor agreement and other flags to work
3119 // out what to do next. Possibilities include:
3120 // * Accept a value all predecessors agree on, or accept one that
3121 // represents a step down the exploration lattice,
3122 // * Use a PHI value number, if one can be found,
3123 // * Propose a PHI value number, and see if it gets confirmed later,
3124 // * Emit a 'NoVal' value, indicating we couldn't resolve anything.
3125 if (OurState == Agreed) {
3126 // Easiest solution: all predecessors agree on the variable value.
3127 ConfirmValue(Var, FirstVal);
3128 } else if (OurState == BEDisagree && OverRide) {
3129 // Only backedges disagree, and the other predecessors have produced
3130 // a new live-in value further down the exploration lattice.
3131 DowngradeOccurred = true;
3132 ConfirmValue(Var, FirstVal);
3133 } else if (OurState == PropDisagree) {
3134 // Predecessors agree on value, but some say it's only a proposed value.
3135 // Propagate it as proposed: unless it was proposed in this block, in
3136 // which case we're able to confirm the value.
3137 if (FirstID.getBlock() == (uint64_t)MBB.getNumber() && FirstID.isPHI()) {
3138 ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Def));
3139 } else if (PropOnlyInBEs) {
3140 // If only backedges disagree, a higher (in RPO) block confirmed this
3141 // location, and we need to propagate it into this loop.
3142 ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Def));
3143 } else {
3144 // Otherwise; a Def meeting a Proposed is still a Proposed.
3145 ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Proposed));
3146 }
3147 } else if ((OurState == PHINeeded || OurState == BEDisagree)) {
3148 // Predecessors disagree and can't be downgraded: this can only be
3149 // solved with a PHI. Use pickVPHILoc to go look for one.
3150 Optional<ValueIDNum> VPHI;
3151 bool AllEdgesVPHI = false;
3152 std::tie(VPHI, AllEdgesVPHI) =
3153 pickVPHILoc(MBB, Var, VLOCOutLocs, MOutLocs, MInLocs, BlockOrders);
3154
3155 if (VPHI && AllEdgesVPHI) {
3156 // There's a PHI value that's valid for all predecessors -- we can use
3157 // it. If any of the non-backedge predecessors have proposed values
3158 // though, this PHI is also only proposed, until the predecessors are
3159 // confirmed.
3160 DbgValue::KindT K = DbgValue::Def;
3161 for (unsigned int I = 0; I < BackEdgesStart; ++I)
3162 if (Values[I].second->Kind == DbgValue::Proposed)
3163 K = DbgValue::Proposed;
3164
3165 ConfirmValue(Var, DbgValue(*VPHI, Properties, K));
3166 } else if (VPHI) {
3167 // There's a PHI value, but it's only legal for backedges. Leave this
3168 // as a proposed PHI value: it might come back on the backedges,
3169 // and allow us to confirm it in the future.
3170 DbgValue NoBEValue = DbgValue(*VPHI, Properties, DbgValue::Proposed);
3171 ConfirmValue(Var, NoBEValue);
3172 } else {
3173 ConfirmNoVal(Var, Properties);
3174 }
3175 } else {
3176 // Otherwise: we don't know. Emit a "phi but no real loc" phi.
3177 ConfirmNoVal(Var, Properties);
3178 }
3179 }
3180
3181 // Store newly calculated in-locs into VLOCInLocs, if they've changed.
3182 Changed = ILS != InLocsT;
3183 if (Changed)
3184 ILS = InLocsT;
3185
3186 return std::tuple<bool, bool>(Changed, DowngradeOccurred);
3187}
3188
3189void InstrRefBasedLDV::vlocDataflow(
3190 const LexicalScope *Scope, const DILocation *DILoc,
3191 const SmallSet<DebugVariable, 4> &VarsWeCareAbout,
3192 SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, LiveInsT &Output,
3193 ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
3194 SmallVectorImpl<VLocTracker> &AllTheVLocs) {
3195 // This method is much like mlocDataflow: but focuses on a single
3196 // LexicalScope at a time. Pick out a set of blocks and variables that are
3197 // to have their value assignments solved, then run our dataflow algorithm
3198 // until a fixedpoint is reached.
3199 std::priority_queue<unsigned int, std::vector<unsigned int>,
3200 std::greater<unsigned int>>
3201 Worklist, Pending;
3202 SmallPtrSet<MachineBasicBlock *, 16> OnWorklist, OnPending;
3203
3204 // The set of blocks we'll be examining.
3205 SmallPtrSet<const MachineBasicBlock *, 8> BlocksToExplore;
3206
3207 // The order in which to examine them (RPO).
3208 SmallVector<MachineBasicBlock *, 8> BlockOrders;
3209
3210 // RPO ordering function.
3211 auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
3212 return BBToOrder[A] < BBToOrder[B];
3213 };
3214
3215 LS.getMachineBasicBlocks(DILoc, BlocksToExplore);
3216
3217 // A separate container to distinguish "blocks we're exploring" versus
3218 // "blocks that are potentially in scope. See comment at start of vlocJoin.
3219 SmallPtrSet<const MachineBasicBlock *, 8> InScopeBlocks = BlocksToExplore;
3220
3221 // Old LiveDebugValues tracks variable locations that come out of blocks
3222 // not in scope, where DBG_VALUEs occur. This is something we could
3223 // legitimately ignore, but lets allow it for now.
3224 if (EmulateOldLDV)
3225 BlocksToExplore.insert(AssignBlocks.begin(), AssignBlocks.end());
3226
3227 // We also need to propagate variable values through any artificial blocks
3228 // that immediately follow blocks in scope.
3229 DenseSet<const MachineBasicBlock *> ToAdd;
3230
3231 // Helper lambda: For a given block in scope, perform a depth first search
3232 // of all the artificial successors, adding them to the ToAdd collection.
3233 auto AccumulateArtificialBlocks =
3234 [this, &ToAdd, &BlocksToExplore,
3235 &InScopeBlocks](const MachineBasicBlock *MBB) {
3236 // Depth-first-search state: each node is a block and which successor
3237 // we're currently exploring.
3238 SmallVector<std::pair<const MachineBasicBlock *,
3239 MachineBasicBlock::const_succ_iterator>,
3240 8>
3241 DFS;
3242
3243 // Find any artificial successors not already tracked.
3244 for (auto *succ : MBB->successors()) {
3245 if (BlocksToExplore.count(succ) || InScopeBlocks.count(succ))
3246 continue;
3247 if (!ArtificialBlocks.count(succ))
3248 continue;
3249 DFS.push_back(std::make_pair(succ, succ->succ_begin()));
3250 ToAdd.insert(succ);
3251 }
3252
3253 // Search all those blocks, depth first.
3254 while (!DFS.empty()) {
3255 const MachineBasicBlock *CurBB = DFS.back().first;
3256 MachineBasicBlock::const_succ_iterator &CurSucc = DFS.back().second;
3257 // Walk back if we've explored this blocks successors to the end.
3258 if (CurSucc == CurBB->succ_end()) {
3259 DFS.pop_back();
3260 continue;
3261 }
3262
3263 // If the current successor is artificial and unexplored, descend into
3264 // it.
3265 if (!ToAdd.count(*CurSucc) && ArtificialBlocks.count(*CurSucc)) {
3266 DFS.push_back(std::make_pair(*CurSucc, (*CurSucc)->succ_begin()));
3267 ToAdd.insert(*CurSucc);
3268 continue;
3269 }
3270
3271 ++CurSucc;
3272 }
3273 };
3274
3275 // Search in-scope blocks and those containing a DBG_VALUE from this scope
3276 // for artificial successors.
3277 for (auto *MBB : BlocksToExplore)
3278 AccumulateArtificialBlocks(MBB);
3279 for (auto *MBB : InScopeBlocks)
3280 AccumulateArtificialBlocks(MBB);
3281
3282 BlocksToExplore.insert(ToAdd.begin(), ToAdd.end());
3283 InScopeBlocks.insert(ToAdd.begin(), ToAdd.end());
3284
3285 // Single block scope: not interesting! No propagation at all. Note that
3286 // this could probably go above ArtificialBlocks without damage, but
3287 // that then produces output differences from original-live-debug-values,
3288 // which propagates from a single block into many artificial ones.
3289 if (BlocksToExplore.size() == 1)
3290 return;
3291
3292 // Picks out relevants blocks RPO order and sort them.
3293 for (auto *MBB : BlocksToExplore)
3294 BlockOrders.push_back(const_cast<MachineBasicBlock *>(MBB));
3295
3296 llvm::sort(BlockOrders, Cmp);
3297 unsigned NumBlocks = BlockOrders.size();
3298
3299 // Allocate some vectors for storing the live ins and live outs. Large.
3300 SmallVector<DenseMap<DebugVariable, DbgValue>, 32> LiveIns, LiveOuts;
3301 LiveIns.resize(NumBlocks);
3302 LiveOuts.resize(NumBlocks);
3303
3304 // Produce by-MBB indexes of live-in/live-outs, to ease lookup within
3305 // vlocJoin.
3306 LiveIdxT LiveOutIdx, LiveInIdx;
3307 LiveOutIdx.reserve(NumBlocks);
3308 LiveInIdx.reserve(NumBlocks);
3309 for (unsigned I = 0; I < NumBlocks; ++I) {
3310 LiveOutIdx[BlockOrders[I]] = &LiveOuts[I];
3311 LiveInIdx[BlockOrders[I]] = &LiveIns[I];
3312 }
3313
3314 for (auto *MBB : BlockOrders) {
3315 Worklist.push(BBToOrder[MBB]);
3316 OnWorklist.insert(MBB);
3317 }
3318
3319 // Iterate over all the blocks we selected, propagating variable values.
3320 bool FirstTrip = true;
3321 SmallPtrSet<const MachineBasicBlock *, 16> VLOCVisited;
3322 while (!Worklist.empty() || !Pending.empty()) {
3323 while (!Worklist.empty()) {
3324 auto *MBB = OrderToBB[Worklist.top()];
3325 CurBB = MBB->getNumber();
3326 Worklist.pop();
3327
3328 DenseMap<DebugVariable, DbgValue> JoinedInLocs;
3329
3330 // Join values from predecessors. Updates LiveInIdx, and writes output
3331 // into JoinedInLocs.
3332 bool InLocsChanged, DowngradeOccurred;
3333 std::tie(InLocsChanged, DowngradeOccurred) = vlocJoin(
3334 *MBB, LiveOutIdx, LiveInIdx, (FirstTrip) ? &VLOCVisited : nullptr,
3335 CurBB, VarsWeCareAbout, MOutLocs, MInLocs, InScopeBlocks,
3336 BlocksToExplore, JoinedInLocs);
3337
3338 bool FirstVisit = VLOCVisited.insert(MBB).second;
3339
3340 // Always explore transfer function if inlocs changed, or if we've not
3341 // visited this block before.
3342 InLocsChanged |= FirstVisit;
3343
3344 // If a downgrade occurred, book us in for re-examination on the next
3345 // iteration.
3346 if (DowngradeOccurred && OnPending.insert(MBB).second)
3347 Pending.push(BBToOrder[MBB]);
3348
3349 if (!InLocsChanged)
3350 continue;
3351
3352 // Do transfer function.
3353 auto &VTracker = AllTheVLocs[MBB->getNumber()];
3354 for (auto &Transfer : VTracker.Vars) {
3355 // Is this var we're mangling in this scope?
3356 if (VarsWeCareAbout.count(Transfer.first)) {
3357 // Erase on empty transfer (DBG_VALUE $noreg).
3358 if (Transfer.second.Kind == DbgValue::Undef) {
3359 JoinedInLocs.erase(Transfer.first);
3360 } else {
3361 // Insert new variable value; or overwrite.
3362 auto NewValuePair = std::make_pair(Transfer.first, Transfer.second);
3363 auto Result = JoinedInLocs.insert(NewValuePair);
3364 if (!Result.second)
3365 Result.first->second = Transfer.second;
3366 }
3367 }
3368 }
3369
3370 // Did the live-out locations change?
3371 bool OLChanged = JoinedInLocs != *LiveOutIdx[MBB];
3372
3373 // If they haven't changed, there's no need to explore further.
3374 if (!OLChanged)
3375 continue;
3376
3377 // Commit to the live-out record.
3378 *LiveOutIdx[MBB] = JoinedInLocs;
3379
3380 // We should visit all successors. Ensure we'll visit any non-backedge
3381 // successors during this dataflow iteration; book backedge successors
3382 // to be visited next time around.
3383 for (auto s : MBB->successors()) {
3384 // Ignore out of scope / not-to-be-explored successors.
3385 if (LiveInIdx.find(s) == LiveInIdx.end())
3386 continue;
3387
3388 if (BBToOrder[s] > BBToOrder[MBB]) {
3389 if (OnWorklist.insert(s).second)
3390 Worklist.push(BBToOrder[s]);
3391 } else if (OnPending.insert(s).second && (FirstTrip || OLChanged)) {
3392 Pending.push(BBToOrder[s]);
3393 }
3394 }
3395 }
3396 Worklist.swap(Pending);
3397 std::swap(OnWorklist, OnPending);
3398 OnPending.clear();
3399 assert(Pending.empty())(static_cast<void> (0));
3400 FirstTrip = false;
3401 }
3402
3403 // Dataflow done. Now what? Save live-ins. Ignore any that are still marked
3404 // as being variable-PHIs, because those did not have their machine-PHI
3405 // value confirmed. Such variable values are places that could have been
3406 // PHIs, but are not.
3407 for (auto *MBB : BlockOrders) {
3408 auto &VarMap = *LiveInIdx[MBB];
3409 for (auto &P : VarMap) {
3410 if (P.second.Kind == DbgValue::Proposed ||
3411 P.second.Kind == DbgValue::NoVal)
3412 continue;
3413 Output[MBB->getNumber()].push_back(P);
3414 }
3415 }
3416
3417 BlockOrders.clear();
3418 BlocksToExplore.clear();
3419}
3420
3421#if !defined(NDEBUG1) || defined(LLVM_ENABLE_DUMP)
3422void InstrRefBasedLDV::dump_mloc_transfer(
3423 const MLocTransferMap &mloc_transfer) const {
3424 for (auto &P : mloc_transfer) {
3425 std::string foo = MTracker->LocIdxToName(P.first);
3426 std::string bar = MTracker->IDAsString(P.second);
3427 dbgs() << "Loc " << foo << " --> " << bar << "\n";
3428 }
3429}
3430#endif
3431
3432void InstrRefBasedLDV::emitLocations(
3433 MachineFunction &MF, LiveInsT SavedLiveIns, ValueIDNum **MOutLocs,
3434 ValueIDNum **MInLocs, DenseMap<DebugVariable, unsigned> &AllVarsNumbering,
3435 const TargetPassConfig &TPC) {
3436 TTracker = new TransferTracker(TII, MTracker, MF, *TRI, CalleeSavedRegs, TPC);
3437 unsigned NumLocs = MTracker->getNumLocs();
3438
3439 // For each block, load in the machine value locations and variable value
3440 // live-ins, then step through each instruction in the block. New DBG_VALUEs
3441 // to be inserted will be created along the way.
3442 for (MachineBasicBlock &MBB : MF) {
3443 unsigned bbnum = MBB.getNumber();
3444 MTracker->reset();
3445 MTracker->loadFromArray(MInLocs[bbnum], bbnum);
3446 TTracker->loadInlocs(MBB, MInLocs[bbnum], SavedLiveIns[MBB.getNumber()],
3447 NumLocs);
3448
3449 CurBB = bbnum;
3450 CurInst = 1;
3451 for (auto &MI : MBB) {
3452 process(MI, MOutLocs, MInLocs);
3453 TTracker->checkInstForNewValues(CurInst, MI.getIterator());
3454 ++CurInst;
3455 }
3456 }
3457
3458 // We have to insert DBG_VALUEs in a consistent order, otherwise they appeaer
3459 // in DWARF in different orders. Use the order that they appear when walking
3460 // through each block / each instruction, stored in AllVarsNumbering.
3461 auto OrderDbgValues = [&](const MachineInstr *A,
3462 const MachineInstr *B) -> bool {
3463 DebugVariable VarA(A->getDebugVariable(), A->getDebugExpression(),
3464 A->getDebugLoc()->getInlinedAt());
3465 DebugVariable VarB(B->getDebugVariable(), B->getDebugExpression(),
3466 B->getDebugLoc()->getInlinedAt());
3467 return AllVarsNumbering.find(VarA)->second <
3468 AllVarsNumbering.find(VarB)->second;
3469 };
3470
3471 // Go through all the transfers recorded in the TransferTracker -- this is
3472 // both the live-ins to a block, and any movements of values that happen
3473 // in the middle.
3474 for (auto &P : TTracker->Transfers) {
3475 // Sort them according to appearance order.
3476 llvm::sort(P.Insts, OrderDbgValues);
3477 // Insert either before or after the designated point...
3478 if (P.MBB) {
3479 MachineBasicBlock &MBB = *P.MBB;
3480 for (auto *MI : P.Insts) {
3481 MBB.insert(P.Pos, MI);
3482 }
3483 } else {
3484 // Terminators, like tail calls, can clobber things. Don't try and place
3485 // transfers after them.
3486 if (P.Pos->isTerminator())
3487 continue;
3488
3489 MachineBasicBlock &MBB = *P.Pos->getParent();
3490 for (auto *MI : P.Insts) {
3491 MBB.insertAfterBundle(P.Pos, MI);
3492 }
3493 }
3494 }
3495}
3496
3497void InstrRefBasedLDV::initialSetup(MachineFunction &MF) {
3498 // Build some useful data structures.
3499 auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
3500 if (const DebugLoc &DL = MI.getDebugLoc())
3501 return DL.getLine() != 0;
3502 return false;
3503 };
3504 // Collect a set of all the artificial blocks.
3505 for (auto &MBB : MF)
3506 if (none_of(MBB.instrs(), hasNonArtificialLocation))
3507 ArtificialBlocks.insert(&MBB);
3508
3509 // Compute mappings of block <=> RPO order.
3510 ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
3511 unsigned int RPONumber = 0;
3512 for (MachineBasicBlock *MBB : RPOT) {
3513 OrderToBB[RPONumber] = MBB;
3514 BBToOrder[MBB] = RPONumber;
3515 BBNumToRPO[MBB->getNumber()] = RPONumber;
3516 ++RPONumber;
3517 }
3518
3519 // Order value substitutions by their "source" operand pair, for quick lookup.
3520 llvm::sort(MF.DebugValueSubstitutions);
3521
3522#ifdef EXPENSIVE_CHECKS
3523 // As an expensive check, test whether there are any duplicate substitution
3524 // sources in the collection.
3525 if (MF.DebugValueSubstitutions.size() > 2) {
3526 for (auto It = MF.DebugValueSubstitutions.begin();
3527 It != std::prev(MF.DebugValueSubstitutions.end()); ++It) {
3528 assert(It->Src != std::next(It)->Src && "Duplicate variable location "(static_cast<void> (0))
3529 "substitution seen")(static_cast<void> (0));
3530 }
3531 }
3532#endif
3533}
3534
3535/// Calculate the liveness information for the given machine function and
3536/// extend ranges across basic blocks.
3537bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC,
3538 unsigned InputBBLimit,
3539 unsigned InputDbgValLimit) {
3540 // No subprogram means this function contains no debuginfo.
3541 if (!MF.getFunction().getSubprogram())
1
Assuming the condition is false
2
Taking false branch
3542 return false;
3543
3544 LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n")do { } while (false);
3
Loop condition is false. Exiting loop
3545 this->TPC = TPC;
3546
3547 TRI = MF.getSubtarget().getRegisterInfo();
3548 TII = MF.getSubtarget().getInstrInfo();
3549 TFI = MF.getSubtarget().getFrameLowering();
3550 TFI->getCalleeSaves(MF, CalleeSavedRegs);
3551 MFI = &MF.getFrameInfo();
3552 LS.initialize(MF);
3553
3554 MTracker =
3555 new MLocTracker(MF, *TII, *TRI, *MF.getSubtarget().getTargetLowering());
3556 VTracker = nullptr;
3557 TTracker = nullptr;
3558
3559 SmallVector<MLocTransferMap, 32> MLocTransfer;
3560 SmallVector<VLocTracker, 8> vlocs;
3561 LiveInsT SavedLiveIns;
3562
3563 int MaxNumBlocks = -1;
3564 for (auto &MBB : MF)
3565 MaxNumBlocks = std::max(MBB.getNumber(), MaxNumBlocks);
3566 assert(MaxNumBlocks >= 0)(static_cast<void> (0));
3567 ++MaxNumBlocks;
3568
3569 MLocTransfer.resize(MaxNumBlocks);
3570 vlocs.resize(MaxNumBlocks);
3571 SavedLiveIns.resize(MaxNumBlocks);
3572
3573 initialSetup(MF);
3574
3575 produceMLocTransferFunction(MF, MLocTransfer, MaxNumBlocks);
3576
3577 // Allocate and initialize two array-of-arrays for the live-in and live-out
3578 // machine values. The outer dimension is the block number; while the inner
3579 // dimension is a LocIdx from MLocTracker.
3580 ValueIDNum **MOutLocs = new ValueIDNum *[MaxNumBlocks];
3581 ValueIDNum **MInLocs = new ValueIDNum *[MaxNumBlocks];
4
Memory is allocated
3582 unsigned NumLocs = MTracker->getNumLocs();
3583 for (int i = 0; i < MaxNumBlocks; ++i) {
5
Loop condition is false. Execution continues on line 3592
3584 MOutLocs[i] = new ValueIDNum[NumLocs];
3585 MInLocs[i] = new ValueIDNum[NumLocs];
3586 }
3587
3588 // Solve the machine value dataflow problem using the MLocTransfer function,
3589 // storing the computed live-ins / live-outs into the array-of-arrays. We use
3590 // both live-ins and live-outs for decision making in the variable value
3591 // dataflow problem.
3592 mlocDataflow(MInLocs, MOutLocs, MLocTransfer);
6
Calling 'InstrRefBasedLDV::mlocDataflow'
3593
3594 // Patch up debug phi numbers, turning unknown block-live-in values into
3595 // either live-through machine values, or PHIs.
3596 for (auto &DBG_PHI : DebugPHINumToValue) {
3597 // Identify unresolved block-live-ins.
3598 ValueIDNum &Num = DBG_PHI.ValueRead;
3599 if (!Num.isPHI())
3600 continue;
3601
3602 unsigned BlockNo = Num.getBlock();
3603 LocIdx LocNo = Num.getLoc();
3604 Num = MInLocs[BlockNo][LocNo.asU64()];
3605 }
3606 // Later, we'll be looking up ranges of instruction numbers.
3607 llvm::sort(DebugPHINumToValue);
3608
3609 // Walk back through each block / instruction, collecting DBG_VALUE
3610 // instructions and recording what machine value their operands refer to.
3611 for (auto &OrderPair : OrderToBB) {
3612 MachineBasicBlock &MBB = *OrderPair.second;
3613 CurBB = MBB.getNumber();
3614 VTracker = &vlocs[CurBB];
3615 VTracker->MBB = &MBB;
3616 MTracker->loadFromArray(MInLocs[CurBB], CurBB);
3617 CurInst = 1;
3618 for (auto &MI : MBB) {
3619 process(MI, MOutLocs, MInLocs);
3620 ++CurInst;
3621 }
3622 MTracker->reset();
3623 }
3624
3625 // Number all variables in the order that they appear, to be used as a stable
3626 // insertion order later.
3627 DenseMap<DebugVariable, unsigned> AllVarsNumbering;
3628
3629 // Map from one LexicalScope to all the variables in that scope.
3630 DenseMap<const LexicalScope *, SmallSet<DebugVariable, 4>> ScopeToVars;
3631
3632 // Map from One lexical scope to all blocks in that scope.
3633 DenseMap<const LexicalScope *, SmallPtrSet<MachineBasicBlock *, 4>>
3634 ScopeToBlocks;
3635
3636 // Store a DILocation that describes a scope.
3637 DenseMap<const LexicalScope *, const DILocation *> ScopeToDILocation;
3638
3639 // To mirror old LiveDebugValues, enumerate variables in RPOT order. Otherwise
3640 // the order is unimportant, it just has to be stable.
3641 unsigned VarAssignCount = 0;
3642 for (unsigned int I = 0; I < OrderToBB.size(); ++I) {
3643 auto *MBB = OrderToBB[I];
3644 auto *VTracker = &vlocs[MBB->getNumber()];
3645 // Collect each variable with a DBG_VALUE in this block.
3646 for (auto &idx : VTracker->Vars) {
3647 const auto &Var = idx.first;
3648 const DILocation *ScopeLoc = VTracker->Scopes[Var];
3649 assert(ScopeLoc != nullptr)(static_cast<void> (0));
3650 auto *Scope = LS.findLexicalScope(ScopeLoc);
3651
3652 // No insts in scope -> shouldn't have been recorded.
3653 assert(Scope != nullptr)(static_cast<void> (0));
3654
3655 AllVarsNumbering.insert(std::make_pair(Var, AllVarsNumbering.size()));
3656 ScopeToVars[Scope].insert(Var);
3657 ScopeToBlocks[Scope].insert(VTracker->MBB);
3658 ScopeToDILocation[Scope] = ScopeLoc;
3659 ++VarAssignCount;
3660 }
3661 }
3662
3663 bool Changed = false;
3664
3665 // If we have an extremely large number of variable assignments and blocks,
3666 // bail out at this point. We've burnt some time doing analysis already,
3667 // however we should cut our losses.
3668 if ((unsigned)MaxNumBlocks > InputBBLimit &&
3669 VarAssignCount > InputDbgValLimit) {
3670 LLVM_DEBUG(dbgs() << "Disabling InstrRefBasedLDV: " << MF.getName()do { } while (false)
3671 << " has " << MaxNumBlocks << " basic blocks and "do { } while (false)
3672 << VarAssignCountdo { } while (false)
3673 << " variable assignments, exceeding limits.\n")do { } while (false);
3674 } else {
3675 // Compute the extended ranges, iterating over scopes. There might be
3676 // something to be said for ordering them by size/locality, but that's for
3677 // the future. For each scope, solve the variable value problem, producing
3678 // a map of variables to values in SavedLiveIns.
3679 for (auto &P : ScopeToVars) {
3680 vlocDataflow(P.first, ScopeToDILocation[P.first], P.second,
3681 ScopeToBlocks[P.first], SavedLiveIns, MOutLocs, MInLocs,
3682 vlocs);
3683 }
3684
3685 // Using the computed value locations and variable values for each block,
3686 // create the DBG_VALUE instructions representing the extended variable
3687 // locations.
3688 emitLocations(MF, SavedLiveIns, MOutLocs, MInLocs, AllVarsNumbering, *TPC);
3689
3690 // Did we actually make any changes? If we created any DBG_VALUEs, then yes.
3691 Changed = TTracker->Transfers.size() != 0;
3692 }
3693
3694 // Common clean-up of memory.
3695 for (int Idx = 0; Idx < MaxNumBlocks; ++Idx) {
3696 delete[] MOutLocs[Idx];
3697 delete[] MInLocs[Idx];
3698 }
3699 delete[] MOutLocs;
3700 delete[] MInLocs;
3701
3702 delete MTracker;
3703 delete TTracker;
3704 MTracker = nullptr;
3705 VTracker = nullptr;
3706 TTracker = nullptr;
3707
3708 ArtificialBlocks.clear();
3709 OrderToBB.clear();
3710 BBToOrder.clear();
3711 BBNumToRPO.clear();
3712 DebugInstrNumToInstr.clear();
3713 DebugPHINumToValue.clear();
3714
3715 return Changed;
3716}
3717
3718LDVImpl *llvm::makeInstrRefBasedLiveDebugValues() {
3719 return new InstrRefBasedLDV();
3720}
3721
3722namespace {
3723class LDVSSABlock;
3724class LDVSSAUpdater;
3725
3726// Pick a type to identify incoming block values as we construct SSA. We
3727// can't use anything more robust than an integer unfortunately, as SSAUpdater
3728// expects to zero-initialize the type.
3729typedef uint64_t BlockValueNum;
3730
3731/// Represents an SSA PHI node for the SSA updater class. Contains the block
3732/// this PHI is in, the value number it would have, and the expected incoming
3733/// values from parent blocks.
3734class LDVSSAPhi {
3735public:
3736 SmallVector<std::pair<LDVSSABlock *, BlockValueNum>, 4> IncomingValues;
3737 LDVSSABlock *ParentBlock;
3738 BlockValueNum PHIValNum;
3739 LDVSSAPhi(BlockValueNum PHIValNum, LDVSSABlock *ParentBlock)
3740 : ParentBlock(ParentBlock), PHIValNum(PHIValNum) {}
3741
3742 LDVSSABlock *getParent() { return ParentBlock; }
3743};
3744
3745/// Thin wrapper around a block predecessor iterator. Only difference from a
3746/// normal block iterator is that it dereferences to an LDVSSABlock.
3747class LDVSSABlockIterator {
3748public:
3749 MachineBasicBlock::pred_iterator PredIt;
3750 LDVSSAUpdater &Updater;
3751
3752 LDVSSABlockIterator(MachineBasicBlock::pred_iterator PredIt,
3753 LDVSSAUpdater &Updater)
3754 : PredIt(PredIt), Updater(Updater) {}
3755
3756 bool operator!=(const LDVSSABlockIterator &OtherIt) const {
3757 return OtherIt.PredIt != PredIt;
3758 }
3759
3760 LDVSSABlockIterator &operator++() {
3761 ++PredIt;
3762 return *this;
3763 }
3764
3765 LDVSSABlock *operator*();
3766};
3767
3768/// Thin wrapper around a block for SSA Updater interface. Necessary because
3769/// we need to track the PHI value(s) that we may have observed as necessary
3770/// in this block.
3771class LDVSSABlock {
3772public:
3773 MachineBasicBlock &BB;
3774 LDVSSAUpdater &Updater;
3775 using PHIListT = SmallVector<LDVSSAPhi, 1>;
3776 /// List of PHIs in this block. There should only ever be one.
3777 PHIListT PHIList;
3778
3779 LDVSSABlock(MachineBasicBlock &BB, LDVSSAUpdater &Updater)
3780 : BB(BB), Updater(Updater) {}
3781
3782 LDVSSABlockIterator succ_begin() {
3783 return LDVSSABlockIterator(BB.succ_begin(), Updater);
3784 }
3785
3786 LDVSSABlockIterator succ_end() {
3787 return LDVSSABlockIterator(BB.succ_end(), Updater);
3788 }
3789
3790 /// SSAUpdater has requested a PHI: create that within this block record.
3791 LDVSSAPhi *newPHI(BlockValueNum Value) {
3792 PHIList.emplace_back(Value, this);
3793 return &PHIList.back();
3794 }
3795
3796 /// SSAUpdater wishes to know what PHIs already exist in this block.
3797 PHIListT &phis() { return PHIList; }
3798};
3799
3800/// Utility class for the SSAUpdater interface: tracks blocks, PHIs and values
3801/// while SSAUpdater is exploring the CFG. It's passed as a handle / baton to
3802// SSAUpdaterTraits<LDVSSAUpdater>.
3803class LDVSSAUpdater {
3804public:
3805 /// Map of value numbers to PHI records.
3806 DenseMap<BlockValueNum, LDVSSAPhi *> PHIs;
3807 /// Map of which blocks generate Undef values -- blocks that are not
3808 /// dominated by any Def.
3809 DenseMap<MachineBasicBlock *, BlockValueNum> UndefMap;
3810 /// Map of machine blocks to our own records of them.
3811 DenseMap<MachineBasicBlock *, LDVSSABlock *> BlockMap;
3812 /// Machine location where any PHI must occur.
3813 LocIdx Loc;
3814 /// Table of live-in machine value numbers for blocks / locations.
3815 ValueIDNum **MLiveIns;
3816
3817 LDVSSAUpdater(LocIdx L, ValueIDNum **MLiveIns) : Loc(L), MLiveIns(MLiveIns) {}
3818
3819 void reset() {
3820 for (auto &Block : BlockMap)
3821 delete Block.second;
3822
3823 PHIs.clear();
3824 UndefMap.clear();
3825 BlockMap.clear();
3826 }
3827
3828 ~LDVSSAUpdater() { reset(); }
3829
3830 /// For a given MBB, create a wrapper block for it. Stores it in the
3831 /// LDVSSAUpdater block map.
3832 LDVSSABlock *getSSALDVBlock(MachineBasicBlock *BB) {
3833 auto it = BlockMap.find(BB);
3834 if (it == BlockMap.end()) {
3835 BlockMap[BB] = new LDVSSABlock(*BB, *this);
3836 it = BlockMap.find(BB);
3837 }
3838 return it->second;
3839 }
3840
3841 /// Find the live-in value number for the given block. Looks up the value at
3842 /// the PHI location on entry.
3843 BlockValueNum getValue(LDVSSABlock *LDVBB) {
3844 return MLiveIns[LDVBB->BB.getNumber()][Loc.asU64()].asU64();
3845 }
3846};
3847
3848LDVSSABlock *LDVSSABlockIterator::operator*() {
3849 return Updater.getSSALDVBlock(*PredIt);
3850}
3851
3852#ifndef NDEBUG1
3853
3854raw_ostream &operator<<(raw_ostream &out, const LDVSSAPhi &PHI) {
3855 out << "SSALDVPHI " << PHI.PHIValNum;
3856 return out;
3857}
3858
3859#endif
3860
3861} // namespace
3862
3863namespace llvm {
3864
3865/// Template specialization to give SSAUpdater access to CFG and value
3866/// information. SSAUpdater calls methods in these traits, passing in the
3867/// LDVSSAUpdater object, to learn about blocks and the values they define.
3868/// It also provides methods to create PHI nodes and track them.
3869template <> class SSAUpdaterTraits<LDVSSAUpdater> {
3870public:
3871 using BlkT = LDVSSABlock;
3872 using ValT = BlockValueNum;
3873 using PhiT = LDVSSAPhi;
3874 using BlkSucc_iterator = LDVSSABlockIterator;
3875
3876 // Methods to access block successors -- dereferencing to our wrapper class.
3877 static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); }
3878 static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); }
3879
3880 /// Iterator for PHI operands.
3881 class PHI_iterator {
3882 private:
3883 LDVSSAPhi *PHI;
3884 unsigned Idx;
3885
3886 public:
3887 explicit PHI_iterator(LDVSSAPhi *P) // begin iterator
3888 : PHI(P), Idx(0) {}
3889 PHI_iterator(LDVSSAPhi *P, bool) // end iterator
3890 : PHI(P), Idx(PHI->IncomingValues.size()) {}
3891
3892 PHI_iterator &operator++() {
3893 Idx++;
3894 return *this;
3895 }
3896 bool operator==(const PHI_iterator &X) const { return Idx == X.Idx; }
3897 bool operator!=(const PHI_iterator &X) const { return !operator==(X); }
3898
3899 BlockValueNum getIncomingValue() { return PHI->IncomingValues[Idx].second; }
3900
3901 LDVSSABlock *getIncomingBlock() { return PHI->IncomingValues[Idx].first; }
3902 };
3903
3904 static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
3905
3906 static inline PHI_iterator PHI_end(PhiT *PHI) {
3907 return PHI_iterator(PHI, true);
3908 }
3909
3910 /// FindPredecessorBlocks - Put the predecessors of BB into the Preds
3911 /// vector.
3912 static void FindPredecessorBlocks(LDVSSABlock *BB,
3913 SmallVectorImpl<LDVSSABlock *> *Preds) {
3914 for (MachineBasicBlock::pred_iterator PI = BB->BB.pred_begin(),
3915 E = BB->BB.pred_end();
3916 PI != E; ++PI)
3917 Preds->push_back(BB->Updater.getSSALDVBlock(*PI));
3918 }
3919
3920 /// GetUndefVal - Normally creates an IMPLICIT_DEF instruction with a new
3921 /// register. For LiveDebugValues, represents a block identified as not having
3922 /// any DBG_PHI predecessors.
3923 static BlockValueNum GetUndefVal(LDVSSABlock *BB, LDVSSAUpdater *Updater) {
3924 // Create a value number for this block -- it needs to be unique and in the
3925 // "undef" collection, so that we know it's not real. Use a number
3926 // representing a PHI into this block.
3927 BlockValueNum Num = ValueIDNum(BB->BB.getNumber(), 0, Updater->Loc).asU64();
3928 Updater->UndefMap[&BB->BB] = Num;
3929 return Num;
3930 }
3931
3932 /// CreateEmptyPHI - Create a (representation of a) PHI in the given block.
3933 /// SSAUpdater will populate it with information about incoming values. The
3934 /// value number of this PHI is whatever the machine value number problem
3935 /// solution determined it to be. This includes non-phi values if SSAUpdater
3936 /// tries to create a PHI where the incoming values are identical.
3937 static BlockValueNum CreateEmptyPHI(LDVSSABlock *BB, unsigned NumPreds,
3938 LDVSSAUpdater *Updater) {
3939 BlockValueNum PHIValNum = Updater->getValue(BB);
3940 LDVSSAPhi *PHI = BB->newPHI(PHIValNum);
3941 Updater->PHIs[PHIValNum] = PHI;
3942 return PHIValNum;
3943 }
3944
3945 /// AddPHIOperand - Add the specified value as an operand of the PHI for
3946 /// the specified predecessor block.
3947 static void AddPHIOperand(LDVSSAPhi *PHI, BlockValueNum Val, LDVSSABlock *Pred) {
3948 PHI->IncomingValues.push_back(std::make_pair(Pred, Val));
3949 }
3950
3951 /// ValueIsPHI - Check if the instruction that defines the specified value
3952 /// is a PHI instruction.
3953 static LDVSSAPhi *ValueIsPHI(BlockValueNum Val, LDVSSAUpdater *Updater) {
3954 auto PHIIt = Updater->PHIs.find(Val);
3955 if (PHIIt == Updater->PHIs.end())
3956 return nullptr;
3957 return PHIIt->second;
3958 }
3959
3960 /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
3961 /// operands, i.e., it was just added.
3962 static LDVSSAPhi *ValueIsNewPHI(BlockValueNum Val, LDVSSAUpdater *Updater) {
3963 LDVSSAPhi *PHI = ValueIsPHI(Val, Updater);
3964 if (PHI && PHI->IncomingValues.size() == 0)
3965 return PHI;
3966 return nullptr;
3967 }
3968
3969 /// GetPHIValue - For the specified PHI instruction, return the value
3970 /// that it defines.
3971 static BlockValueNum GetPHIValue(LDVSSAPhi *PHI) { return PHI->PHIValNum; }
3972};
3973
3974} // end namespace llvm
3975
3976Optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIs(MachineFunction &MF,
3977 ValueIDNum **MLiveOuts,
3978 ValueIDNum **MLiveIns,
3979 MachineInstr &Here,
3980 uint64_t InstrNum) {
3981 // Pick out records of DBG_PHI instructions that have been observed. If there
3982 // are none, then we cannot compute a value number.
3983 auto RangePair = std::equal_range(DebugPHINumToValue.begin(),
3984 DebugPHINumToValue.end(), InstrNum);
3985 auto LowerIt = RangePair.first;
3986 auto UpperIt = RangePair.second;
3987
3988 // No DBG_PHI means there can be no location.
3989 if (LowerIt == UpperIt)
3990 return None;
3991
3992 // If there's only one DBG_PHI, then that is our value number.
3993 if (std::distance(LowerIt, UpperIt) == 1)
3994 return LowerIt->ValueRead;
3995
3996 auto DBGPHIRange = make_range(LowerIt, UpperIt);
3997
3998 // Pick out the location (physreg, slot) where any PHIs must occur. It's
3999 // technically possible for us to merge values in different registers in each
4000 // block, but highly unlikely that LLVM will generate such code after register
4001 // allocation.
4002 LocIdx Loc = LowerIt->ReadLoc;
4003
4004 // We have several DBG_PHIs, and a use position (the Here inst). All each
4005 // DBG_PHI does is identify a value at a program position. We can treat each
4006 // DBG_PHI like it's a Def of a value, and the use position is a Use of a
4007 // value, just like SSA. We use the bulk-standard LLVM SSA updater class to
4008 // determine which Def is used at the Use, and any PHIs that happen along
4009 // the way.
4010 // Adapted LLVM SSA Updater:
4011 LDVSSAUpdater Updater(Loc, MLiveIns);
4012 // Map of which Def or PHI is the current value in each block.
4013 DenseMap<LDVSSABlock *, BlockValueNum> AvailableValues;
4014 // Set of PHIs that we have created along the way.
4015 SmallVector<LDVSSAPhi *, 8> CreatedPHIs;
4016
4017 // Each existing DBG_PHI is a Def'd value under this model. Record these Defs
4018 // for the SSAUpdater.
4019 for (const auto &DBG_PHI : DBGPHIRange) {
4020 LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB);
4021 const ValueIDNum &Num = DBG_PHI.ValueRead;
4022 AvailableValues.insert(std::make_pair(Block, Num.asU64()));
4023 }
4024
4025 LDVSSABlock *HereBlock = Updater.getSSALDVBlock(Here.getParent());
4026 const auto &AvailIt = AvailableValues.find(HereBlock);
4027 if (AvailIt != AvailableValues.end()) {
4028 // Actually, we already know what the value is -- the Use is in the same
4029 // block as the Def.
4030 return ValueIDNum::fromU64(AvailIt->second);
4031 }
4032
4033 // Otherwise, we must use the SSA Updater. It will identify the value number
4034 // that we are to use, and the PHIs that must happen along the way.
4035 SSAUpdaterImpl<LDVSSAUpdater> Impl(&Updater, &AvailableValues, &CreatedPHIs);
4036 BlockValueNum ResultInt = Impl.GetValue(Updater.getSSALDVBlock(Here.getParent()));
4037 ValueIDNum Result = ValueIDNum::fromU64(ResultInt);
4038
4039 // We have the number for a PHI, or possibly live-through value, to be used
4040 // at this Use. There are a number of things we have to check about it though:
4041 // * Does any PHI use an 'Undef' (like an IMPLICIT_DEF) value? If so, this
4042 // Use was not completely dominated by DBG_PHIs and we should abort.
4043 // * Are the Defs or PHIs clobbered in a block? SSAUpdater isn't aware that
4044 // we've left SSA form. Validate that the inputs to each PHI are the
4045 // expected values.
4046 // * Is a PHI we've created actually a merging of values, or are all the
4047 // predecessor values the same, leading to a non-PHI machine value number?
4048 // (SSAUpdater doesn't know that either). Remap validated PHIs into the
4049 // the ValidatedValues collection below to sort this out.
4050 DenseMap<LDVSSABlock *, ValueIDNum> ValidatedValues;
4051
4052 // Define all the input DBG_PHI values in ValidatedValues.
4053 for (const auto &DBG_PHI : DBGPHIRange) {
4054 LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB);
4055 const ValueIDNum &Num = DBG_PHI.ValueRead;
4056 ValidatedValues.insert(std::make_pair(Block, Num));
4057 }
4058
4059 // Sort PHIs to validate into RPO-order.
4060 SmallVector<LDVSSAPhi *, 8> SortedPHIs;
4061 for (auto &PHI : CreatedPHIs)
4062 SortedPHIs.push_back(PHI);
4063
4064 std::sort(
4065 SortedPHIs.begin(), SortedPHIs.end(), [&](LDVSSAPhi *A, LDVSSAPhi *B) {
4066 return BBToOrder[&A->getParent()->BB] < BBToOrder[&B->getParent()->BB];
4067 });
4068
4069 for (auto &PHI : SortedPHIs) {
4070 ValueIDNum ThisBlockValueNum =
4071 MLiveIns[PHI->ParentBlock->BB.getNumber()][Loc.asU64()];
4072
4073 // Are all these things actually defined?
4074 for (auto &PHIIt : PHI->IncomingValues) {
4075 // Any undef input means DBG_PHIs didn't dominate the use point.
4076 if (Updater.UndefMap.find(&PHIIt.first->BB) != Updater.UndefMap.end())
4077 return None;
4078
4079 ValueIDNum ValueToCheck;
4080 ValueIDNum *BlockLiveOuts = MLiveOuts[PHIIt.first->BB.getNumber()];
4081
4082 auto VVal = ValidatedValues.find(PHIIt.first);
4083 if (VVal == ValidatedValues.end()) {
4084 // We cross a loop, and this is a backedge. LLVMs tail duplication
4085 // happens so late that DBG_PHI instructions should not be able to
4086 // migrate into loops -- meaning we can only be live-through this
4087 // loop.
4088 ValueToCheck = ThisBlockValueNum;
4089 } else {
4090 // Does the block have as a live-out, in the location we're examining,
4091 // the value that we expect? If not, it's been moved or clobbered.
4092 ValueToCheck = VVal->second;
4093 }
4094
4095 if (BlockLiveOuts[Loc.asU64()] != ValueToCheck)
4096 return None;
4097 }
4098
4099 // Record this value as validated.
4100 ValidatedValues.insert({PHI->ParentBlock, ThisBlockValueNum});
4101 }
4102
4103 // All the PHIs are valid: we can return what the SSAUpdater said our value
4104 // number was.
4105 return Result;
4106}