1//===- VarLocBasedImpl.cpp - Tracking Debug Value MIs with VarLoc class----===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file VarLocBasedImpl.cpp
10///
11/// LiveDebugValues is an optimistic "available expressions" dataflow
12/// algorithm. The set of expressions is the set of machine locations
13/// (registers, spill slots, constants, and target indices) that a variable
14/// fragment might be located, qualified by a DIExpression and indirect-ness
15/// flag, while each variable is identified by a DebugVariable object. The
16/// availability of an expression begins when a DBG_VALUE instruction specifies
17/// the location of a DebugVariable, and continues until that location is
18/// clobbered or re-specified by a different DBG_VALUE for the same
19/// DebugVariable.
20///
21/// The output of LiveDebugValues is additional DBG_VALUE instructions,
22/// placed to extend variable locations as far they're available. This file
23/// and the VarLocBasedLDV class is an implementation that explicitly tracks
24/// locations, using the VarLoc class.
25///
26/// The canonical "available expressions" problem doesn't have expression
27/// clobbering, instead when a variable is re-assigned, any expressions using
28/// that variable get invalidated. LiveDebugValues can map onto "available
29/// expressions" by having every register represented by a variable, which is
30/// used in an expression that becomes available at a DBG_VALUE instruction.
31/// When the register is clobbered, its variable is effectively reassigned, and
32/// expressions computed from it become unavailable. A similar construct is
33/// needed when a DebugVariable has its location re-specified, to invalidate
34/// all other locations for that DebugVariable.
35///
36/// Using the dataflow analysis to compute the available expressions, we create
37/// a DBG_VALUE at the beginning of each block where the expression is
38/// live-in. This propagates variable locations into every basic block where
39/// the location can be determined, rather than only having DBG_VALUEs in blocks
40/// where locations are specified due to an assignment or some optimization.
41/// Movements of values between registers and spill slots are annotated with
42/// DBG_VALUEs too to track variable values bewteen locations. All this allows
43/// DbgEntityHistoryCalculator to focus on only the locations within individual
44/// blocks, facilitating testing and improving modularity.
45///
46/// We follow an optimisic dataflow approach, with this lattice:
47///
48/// \verbatim
49/// ┬ "Unknown"
50/// |
51/// v
52/// True
53/// |
54/// v
55/// ⊥ False
56/// \endverbatim With "True" signifying that the expression is available (and
57/// thus a DebugVariable's location is the corresponding register), while
58/// "False" signifies that the expression is unavailable. "Unknown"s never
59/// survive to the end of the analysis (see below).
60///
61/// Formally, all DebugVariable locations that are live-out of a block are
62/// initialized to \top. A blocks live-in values take the meet of the lattice
63/// value for every predecessors live-outs, except for the entry block, where
64/// all live-ins are \bot. The usual dataflow propagation occurs: the transfer
65/// function for a block assigns an expression for a DebugVariable to be "True"
66/// if a DBG_VALUE in the block specifies it; "False" if the location is
67/// clobbered; or the live-in value if it is unaffected by the block. We
68/// visit each block in reverse post order until a fixedpoint is reached. The
69/// solution produced is maximal.
70///
71/// Intuitively, we start by assuming that every expression / variable location
72/// is at least "True", and then propagate "False" from the entry block and any
73/// clobbers until there are no more changes to make. This gives us an accurate
74/// solution because all incorrect locations will have a "False" propagated into
75/// them. It also gives us a solution that copes well with loops by assuming
76/// that variable locations are live-through every loop, and then removing those
77/// that are not through dataflow.
78///
79/// Within LiveDebugValues: each variable location is represented by a
80/// VarLoc object that identifies the source variable, the set of
81/// machine-locations that currently describe it (a single location for
82/// DBG_VALUE or multiple for DBG_VALUE_LIST), and the DBG_VALUE inst that
83/// specifies the location. Each VarLoc is indexed in the (function-scope) \p
84/// VarLocMap, giving each VarLoc a set of unique indexes, each of which
85/// corresponds to one of the VarLoc's machine-locations and can be used to
86/// lookup the VarLoc in the VarLocMap. Rather than operate directly on machine
87/// locations, the dataflow analysis in this pass identifies locations by their
88/// indices in the VarLocMap, meaning all the variable locations in a block can
89/// be described by a sparse vector of VarLocMap indices.
90///
91/// All the storage for the dataflow analysis is local to the ExtendRanges
92/// method and passed down to helper methods. "OutLocs" and "InLocs" record the
93/// in and out lattice values for each block. "OpenRanges" maintains a list of
94/// variable locations and, with the "process" method, evaluates the transfer
95/// function of each block. "flushPendingLocs" installs debug value instructions
96/// for each live-in location at the start of blocks, while "Transfers" records
97/// transfers of values between machine-locations.
98///
99/// We avoid explicitly representing the "Unknown" (\top) lattice value in the
100/// implementation. Instead, unvisited blocks implicitly have all lattice
101/// values set as "Unknown". After being visited, there will be path back to
102/// the entry block where the lattice value is "False", and as the transfer
103/// function cannot make new "Unknown" locations, there are no scenarios where
104/// a block can have an "Unknown" location after being visited. Similarly, we
105/// don't enumerate all possible variable locations before exploring the
106/// function: when a new location is discovered, all blocks previously explored
107/// were implicitly "False" but unrecorded, and become explicitly "False" when
108/// a new VarLoc is created with its bit not set in predecessor InLocs or
109/// OutLocs.
110///
111//===----------------------------------------------------------------------===//
112
113#include "LiveDebugValues.h"
114
115#include "llvm/ADT/CoalescingBitVector.h"
116#include "llvm/ADT/DenseMap.h"
117#include "llvm/ADT/PostOrderIterator.h"
118#include "llvm/ADT/SmallPtrSet.h"
119#include "llvm/ADT/SmallSet.h"
120#include "llvm/ADT/SmallVector.h"
121#include "llvm/ADT/Statistic.h"
122#include "llvm/BinaryFormat/Dwarf.h"
123#include "llvm/CodeGen/LexicalScopes.h"
124#include "llvm/CodeGen/MachineBasicBlock.h"
125#include "llvm/CodeGen/MachineFunction.h"
126#include "llvm/CodeGen/MachineInstr.h"
127#include "llvm/CodeGen/MachineInstrBuilder.h"
128#include "llvm/CodeGen/MachineInstrBundle.h"
129#include "llvm/CodeGen/MachineMemOperand.h"
130#include "llvm/CodeGen/MachineOperand.h"
131#include "llvm/CodeGen/PseudoSourceValue.h"
132#include "llvm/CodeGen/TargetFrameLowering.h"
133#include "llvm/CodeGen/TargetInstrInfo.h"
134#include "llvm/CodeGen/TargetLowering.h"
135#include "llvm/CodeGen/TargetRegisterInfo.h"
136#include "llvm/CodeGen/TargetSubtargetInfo.h"
137#include "llvm/Config/llvm-config.h"
138#include "llvm/IR/DebugInfoMetadata.h"
139#include "llvm/IR/DebugLoc.h"
140#include "llvm/IR/Function.h"
141#include "llvm/MC/MCRegisterInfo.h"
142#include "llvm/Support/Casting.h"
143#include "llvm/Support/Debug.h"
144#include "llvm/Support/TypeSize.h"
145#include "llvm/Support/raw_ostream.h"
146#include "llvm/Target/TargetMachine.h"
147#include <cassert>
148#include <cstdint>
149#include <functional>
150#include <map>
151#include <optional>
152#include <queue>
153#include <tuple>
154#include <utility>
155#include <vector>
156
157using namespace llvm;
158
159#define DEBUG_TYPE "live-debug-values"
160
161STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
162
163/// If \p Op is a stack or frame register return true, otherwise return false.
164/// This is used to avoid basing the debug entry values on the registers, since
165/// we do not support it at the moment.
166static bool isRegOtherThanSPAndFP(const MachineOperand &Op,
167 const MachineInstr &MI,
168 const TargetRegisterInfo *TRI) {
169 if (!Op.isReg())
170 return false;
171
172 const MachineFunction *MF = MI.getParent()->getParent();
173 const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
174 Register SP = TLI->getStackPointerRegisterToSaveRestore();
175 Register FP = TRI->getFrameRegister(MF: *MF);
176 Register Reg = Op.getReg();
177
178 return Reg && Reg != SP && Reg != FP;
179}
180
181namespace {
182
183// Max out the number of statically allocated elements in DefinedRegsSet, as
184// this prevents fallback to std::set::count() operations.
185using DefinedRegsSet = SmallSet<Register, 32>;
186
187// The IDs in this set correspond to MachineLocs in VarLocs, as well as VarLocs
188// that represent Entry Values; every VarLoc in the set will also appear
189// exactly once at Location=0.
190// As a result, each VarLoc may appear more than once in this "set", but each
191// range corresponding to a Reg, SpillLoc, or EntryValue type will still be a
192// "true" set (i.e. each VarLoc may appear only once), and the range Location=0
193// is the set of all VarLocs.
194using VarLocSet = CoalescingBitVector<uint64_t>;
195
196/// A type-checked pair of {Register Location (or 0), Index}, used to index
197/// into a \ref VarLocMap. This can be efficiently converted to a 64-bit int
198/// for insertion into a \ref VarLocSet, and efficiently converted back. The
199/// type-checker helps ensure that the conversions aren't lossy.
200///
201/// Why encode a location /into/ the VarLocMap index? This makes it possible
202/// to find the open VarLocs killed by a register def very quickly. This is a
203/// performance-critical operation for LiveDebugValues.
204struct LocIndex {
205 using u32_location_t = uint32_t;
206 using u32_index_t = uint32_t;
207
208 u32_location_t Location; // Physical registers live in the range [1;2^30) (see
209 // \ref MCRegister), so we have plenty of range left
210 // here to encode non-register locations.
211 u32_index_t Index;
212
213 /// The location that has an entry for every VarLoc in the map.
214 static constexpr u32_location_t kUniversalLocation = 0;
215
216 /// The first location that is reserved for VarLocs with locations of kind
217 /// RegisterKind.
218 static constexpr u32_location_t kFirstRegLocation = 1;
219
220 /// The first location greater than 0 that is not reserved for VarLocs with
221 /// locations of kind RegisterKind.
222 static constexpr u32_location_t kFirstInvalidRegLocation = 1 << 30;
223
224 /// A special location reserved for VarLocs with locations of kind
225 /// SpillLocKind.
226 static constexpr u32_location_t kSpillLocation = kFirstInvalidRegLocation;
227
228 /// A special location reserved for VarLocs of kind EntryValueBackupKind and
229 /// EntryValueCopyBackupKind.
230 static constexpr u32_location_t kEntryValueBackupLocation =
231 kFirstInvalidRegLocation + 1;
232
233 /// A special location reserved for VarLocs with locations of kind
234 /// WasmLocKind.
235 /// TODO Placing all Wasm target index locations in this single kWasmLocation
236 /// may cause slowdown in compilation time in very large functions. Consider
237 /// giving a each target index/offset pair its own u32_location_t if this
238 /// becomes a problem.
239 static constexpr u32_location_t kWasmLocation = kFirstInvalidRegLocation + 2;
240
241 /// The first location that is reserved for VarLocs with locations of kind
242 /// VirtualRegisterKind.
243 static constexpr u32_location_t kFirstVirtualRegLocation = 1 << 31;
244
245 LocIndex(u32_location_t Location, u32_index_t Index)
246 : Location(Location), Index(Index) {}
247
248 uint64_t getAsRawInteger() const {
249 return (static_cast<uint64_t>(Location) << 32) | Index;
250 }
251
252 template<typename IntT> static LocIndex fromRawInteger(IntT ID) {
253 static_assert(std::is_unsigned_v<IntT> && sizeof(ID) == sizeof(uint64_t),
254 "Cannot convert raw integer to LocIndex");
255 return {static_cast<u32_location_t>(ID >> 32),
256 static_cast<u32_index_t>(ID)};
257 }
258
259 /// Get the start of the interval reserved for VarLocs of kind RegisterKind
260 /// which reside in \p Reg. The end is at rawIndexForReg(Reg+1)-1.
261 static uint64_t rawIndexForReg(Register Reg) {
262 return LocIndex(Reg, 0).getAsRawInteger();
263 }
264
265 /// Return a range covering all set indices in the interval reserved for
266 /// \p Location in \p Set.
267 static auto indexRangeForLocation(const VarLocSet &Set,
268 u32_location_t Location) {
269 uint64_t Start = LocIndex(Location, 0).getAsRawInteger();
270 uint64_t End = LocIndex(Location + 1, 0).getAsRawInteger();
271 return Set.half_open_range(Start, End);
272 }
273};
274
275// Simple Set for storing all the VarLoc Indices at a Location bucket.
276using VarLocsInRange = SmallSet<LocIndex::u32_index_t, 32>;
277// Vector of all `LocIndex`s for a given VarLoc; the same Location should not
278// appear in any two of these, as each VarLoc appears at most once in any
279// Location bucket.
280using LocIndices = SmallVector<LocIndex, 2>;
281
282class VarLocBasedLDV : public LDVImpl {
283private:
284 const TargetRegisterInfo *TRI;
285 const TargetInstrInfo *TII;
286 const TargetFrameLowering *TFI;
287 bool ShouldEmitDebugEntryValues;
288 BitVector CalleeSavedRegs;
289 LexicalScopes LS;
290 VarLocSet::Allocator Alloc;
291
292 const MachineInstr *LastNonDbgMI;
293
294 enum struct TransferKind { TransferCopy, TransferSpill, TransferRestore };
295
296 using FragmentInfo = DIExpression::FragmentInfo;
297 using OptFragmentInfo = std::optional<DIExpression::FragmentInfo>;
298
299 /// A pair of debug variable and value location.
300 struct VarLoc {
301 // The location at which a spilled variable resides. It consists of a
302 // register and an offset.
303 struct SpillLoc {
304 unsigned SpillBase;
305 StackOffset SpillOffset;
306 bool operator==(const SpillLoc &Other) const {
307 return SpillBase == Other.SpillBase && SpillOffset == Other.SpillOffset;
308 }
309 bool operator!=(const SpillLoc &Other) const {
310 return !(*this == Other);
311 }
312 };
313
314 // Target indices used for wasm-specific locations.
315 struct WasmLoc {
316 // One of TargetIndex values defined in WebAssembly.h. We deal with
317 // local-related TargetIndex in this analysis (TI_LOCAL and
318 // TI_LOCAL_INDIRECT). Stack operands (TI_OPERAND_STACK) will be handled
319 // separately WebAssemblyDebugFixup pass, and we don't associate debug
320 // info with values in global operands (TI_GLOBAL_RELOC) at the moment.
321 int Index;
322 int64_t Offset;
323 bool operator==(const WasmLoc &Other) const {
324 return Index == Other.Index && Offset == Other.Offset;
325 }
326 bool operator!=(const WasmLoc &Other) const { return !(*this == Other); }
327 };
328
329 struct GlobalAddr {
330 const GlobalValue *GV;
331 int64_t Offset;
332 bool operator==(const GlobalAddr &Other) const {
333 return GV == Other.GV && Offset == Other.Offset;
334 }
335 };
336
337 /// Identity of the variable at this location.
338 const DebugVariable Var;
339
340 /// The expression applied to this location.
341 const DIExpression *Expr;
342
343 /// DBG_VALUE to clone var/expr information from if this location
344 /// is moved.
345 const MachineInstr &MI;
346
347 enum class MachineLocKind {
348 InvalidKind = 0,
349 RegisterKind,
350 SpillLocKind,
351 ImmediateKind,
352 WasmLocKind,
353 GlobalAddrKind
354 };
355
356 enum class EntryValueLocKind {
357 NonEntryValueKind = 0,
358 EntryValueKind,
359 EntryValueBackupKind,
360 EntryValueCopyBackupKind
361 } EVKind = EntryValueLocKind::NonEntryValueKind;
362
363 /// The value location. Stored separately to avoid repeatedly
364 /// extracting it from MI.
365 union MachineLocValue {
366 uint64_t RegNo;
367 SpillLoc SpillLocation;
368 uint64_t Hash;
369 int64_t Immediate;
370 const ConstantFP *FPImm;
371 const ConstantInt *CImm;
372 WasmLoc WasmLocation;
373 GlobalAddr GlobalAddress;
374 MachineLocValue() : Hash(0) {}
375 };
376
377 /// A single machine location; its Kind is a register, a spill location, an
378 /// immediate value, a WebAssembly local, or the address of a global.
379 /// If the VarLoc is not a NonEntryValueKind, then it will use only a
380 /// single MachineLoc of RegisterKind.
381 struct MachineLoc {
382 MachineLocKind Kind;
383 MachineLocValue Value;
384 bool operator==(const MachineLoc &Other) const {
385 if (Kind != Other.Kind)
386 return false;
387 switch (Kind) {
388 case MachineLocKind::SpillLocKind:
389 return Value.SpillLocation == Other.Value.SpillLocation;
390 case MachineLocKind::WasmLocKind:
391 return Value.WasmLocation == Other.Value.WasmLocation;
392 case MachineLocKind::GlobalAddrKind:
393 return Value.GlobalAddress == Other.Value.GlobalAddress;
394 case MachineLocKind::RegisterKind:
395 case MachineLocKind::ImmediateKind:
396 return Value.Hash == Other.Value.Hash;
397 default:
398 llvm_unreachable("Invalid kind");
399 }
400 }
401 bool operator<(const MachineLoc &Other) const {
402 // Order by kind first, and only then by the payload. Which union member
403 // is the active one depends on the kind, so reading either side's
404 // payload is only well defined once both kinds are known to agree.
405 if (Kind != Other.Kind)
406 return Kind < Other.Kind;
407 switch (Kind) {
408 case MachineLocKind::SpillLocKind:
409 return std::make_tuple(
410 args: Value.SpillLocation.SpillBase,
411 args: Value.SpillLocation.SpillOffset.getFixed(),
412 args: Value.SpillLocation.SpillOffset.getScalable()) <
413 std::make_tuple(
414 args: Other.Value.SpillLocation.SpillBase,
415 args: Other.Value.SpillLocation.SpillOffset.getFixed(),
416 args: Other.Value.SpillLocation.SpillOffset.getScalable());
417 case MachineLocKind::WasmLocKind:
418 return std::tie(args: Value.WasmLocation.Index, args: Value.WasmLocation.Offset) <
419 std::tie(args: Other.Value.WasmLocation.Index,
420 args: Other.Value.WasmLocation.Offset);
421 case MachineLocKind::GlobalAddrKind:
422 return std::tie(args: Value.GlobalAddress.GV, args: Value.GlobalAddress.Offset) <
423 std::tie(args: Other.Value.GlobalAddress.GV,
424 args: Other.Value.GlobalAddress.Offset);
425 case MachineLocKind::RegisterKind:
426 case MachineLocKind::ImmediateKind:
427 return Value.Hash < Other.Value.Hash;
428 default:
429 llvm_unreachable("Invalid kind");
430 }
431 }
432 };
433
434 /// The set of machine locations used to determine the variable's value, in
435 /// conjunction with Expr. Initially populated with MI's debug operands,
436 /// but may be transformed independently afterwards.
437 SmallVector<MachineLoc, 8> Locs;
438 /// Used to map the index of each location in Locs back to the index of its
439 /// original debug operand in MI. Used when multiple location operands are
440 /// coalesced and the original MI's operands need to be accessed while
441 /// emitting a debug value.
442 SmallVector<unsigned, 8> OrigLocMap;
443
444 VarLoc(const MachineInstr &MI)
445 : Var(MI.getDebugVariable(), MI.getDebugExpression(),
446 MI.getDebugLoc()->getInlinedAt()),
447 Expr(MI.getDebugExpression()), MI(MI) {
448 assert(MI.isDebugValue() && "not a DBG_VALUE");
449 assert((MI.isDebugValueList() || MI.getNumOperands() == 4) &&
450 "malformed DBG_VALUE");
451 for (const MachineOperand &Op : MI.debug_operands()) {
452 MachineLoc ML = GetLocForOp(Op);
453 auto It = find(Range&: Locs, Val: ML);
454 if (It == Locs.end()) {
455 Locs.push_back(Elt: ML);
456 OrigLocMap.push_back(Elt: MI.getDebugOperandIndex(Op: &Op));
457 } else {
458 // ML duplicates an element in Locs; replace references to Op
459 // with references to the duplicating element.
460 unsigned OpIdx = Locs.size();
461 unsigned DuplicatingIdx = std::distance(first: Locs.begin(), last: It);
462 Expr = DIExpression::replaceArg(Expr, OldArg: OpIdx, NewArg: DuplicatingIdx);
463 }
464 }
465
466 // We create the debug entry values from the factory functions rather
467 // than from this ctor.
468 assert(EVKind != EntryValueLocKind::EntryValueKind &&
469 !isEntryBackupLoc());
470 }
471
472 static MachineLoc GetLocForOp(const MachineOperand &Op) {
473 MachineLocKind Kind;
474 MachineLocValue Loc;
475 if (Op.isReg()) {
476 Kind = MachineLocKind::RegisterKind;
477 Loc.RegNo = Op.getReg();
478 } else if (Op.isImm()) {
479 Kind = MachineLocKind::ImmediateKind;
480 Loc.Immediate = Op.getImm();
481 } else if (Op.isFPImm()) {
482 Kind = MachineLocKind::ImmediateKind;
483 Loc.FPImm = Op.getFPImm();
484 } else if (Op.isCImm()) {
485 Kind = MachineLocKind::ImmediateKind;
486 Loc.CImm = Op.getCImm();
487 } else if (Op.isTargetIndex()) {
488 Kind = MachineLocKind::WasmLocKind;
489 Loc.WasmLocation = {.Index: Op.getIndex(), .Offset: Op.getOffset()};
490 } else if (Op.isGlobal()) {
491 Kind = MachineLocKind::GlobalAddrKind;
492 Loc.GlobalAddress = {.GV: Op.getGlobal(), .Offset: Op.getOffset()};
493 } else
494 llvm_unreachable("Invalid Op kind for MachineLoc.");
495 return {.Kind: Kind, .Value: Loc};
496 }
497
498 /// Take the variable and machine-location in DBG_VALUE MI, and build an
499 /// entry location using the given expression.
500 static VarLoc CreateEntryLoc(const MachineInstr &MI,
501 const DIExpression *EntryExpr, Register Reg) {
502 VarLoc VL(MI);
503 assert(VL.Locs.size() == 1 &&
504 VL.Locs[0].Kind == MachineLocKind::RegisterKind);
505 VL.EVKind = EntryValueLocKind::EntryValueKind;
506 VL.Expr = EntryExpr;
507 VL.Locs[0].Value.RegNo = Reg;
508 return VL;
509 }
510
511 /// Take the variable and machine-location from the DBG_VALUE (from the
512 /// function entry), and build an entry value backup location. The backup
513 /// location will turn into the normal location if the backup is valid at
514 /// the time of the primary location clobbering.
515 static VarLoc CreateEntryBackupLoc(const MachineInstr &MI,
516 const DIExpression *EntryExpr) {
517 VarLoc VL(MI);
518 assert(VL.Locs.size() == 1 &&
519 VL.Locs[0].Kind == MachineLocKind::RegisterKind);
520 VL.EVKind = EntryValueLocKind::EntryValueBackupKind;
521 VL.Expr = EntryExpr;
522 return VL;
523 }
524
525 /// Take the variable and machine-location from the DBG_VALUE (from the
526 /// function entry), and build a copy of an entry value backup location by
527 /// setting the register location to NewReg.
528 static VarLoc CreateEntryCopyBackupLoc(const MachineInstr &MI,
529 const DIExpression *EntryExpr,
530 Register NewReg) {
531 VarLoc VL(MI);
532 assert(VL.Locs.size() == 1 &&
533 VL.Locs[0].Kind == MachineLocKind::RegisterKind);
534 VL.EVKind = EntryValueLocKind::EntryValueCopyBackupKind;
535 VL.Expr = EntryExpr;
536 VL.Locs[0].Value.RegNo = NewReg;
537 return VL;
538 }
539
540 /// Copy the register location in DBG_VALUE MI, updating the register to
541 /// be NewReg.
542 static VarLoc CreateCopyLoc(const VarLoc &OldVL, const MachineLoc &OldML,
543 Register NewReg) {
544 VarLoc VL = OldVL;
545 for (MachineLoc &ML : VL.Locs)
546 if (ML == OldML) {
547 ML.Kind = MachineLocKind::RegisterKind;
548 ML.Value.RegNo = NewReg;
549 return VL;
550 }
551 llvm_unreachable("Should have found OldML in new VarLoc.");
552 }
553
554 /// Take the variable described by DBG_VALUE* MI, and create a VarLoc
555 /// locating it in the specified spill location.
556 static VarLoc CreateSpillLoc(const VarLoc &OldVL, const MachineLoc &OldML,
557 unsigned SpillBase, StackOffset SpillOffset) {
558 VarLoc VL = OldVL;
559 for (MachineLoc &ML : VL.Locs)
560 if (ML == OldML) {
561 ML.Kind = MachineLocKind::SpillLocKind;
562 ML.Value.SpillLocation = {.SpillBase: SpillBase, .SpillOffset: SpillOffset};
563 return VL;
564 }
565 llvm_unreachable("Should have found OldML in new VarLoc.");
566 }
567
568 /// Create a DBG_VALUE representing this VarLoc in the given function.
569 /// Copies variable-specific information such as DILocalVariable and
570 /// inlining information from the original DBG_VALUE instruction, which may
571 /// have been several transfers ago.
572 MachineInstr *BuildDbgValue(MachineFunction &MF) const {
573 assert(!isEntryBackupLoc() &&
574 "Tried to produce DBG_VALUE for backup VarLoc");
575 const DebugLoc &DbgLoc = MI.getDebugLoc();
576 bool Indirect = MI.isIndirectDebugValue();
577 const auto &IID = MI.getDesc();
578 const DILocalVariable *Var = MI.getDebugVariable();
579 NumInserted++;
580
581 const DIExpression *DIExpr = Expr;
582 SmallVector<MachineOperand, 8> MOs;
583 for (unsigned I = 0, E = Locs.size(); I < E; ++I) {
584 MachineLocKind LocKind = Locs[I].Kind;
585 MachineLocValue Loc = Locs[I].Value;
586 const MachineOperand &Orig = MI.getDebugOperand(Index: OrigLocMap[I]);
587 switch (LocKind) {
588 case MachineLocKind::RegisterKind:
589 // An entry value is a register location -- but with an updated
590 // expression. The register location of such DBG_VALUE is always the
591 // one from the entry DBG_VALUE, it does not matter if the entry value
592 // was copied in to another register due to some optimizations.
593 // Non-entry value register locations are like the source
594 // DBG_VALUE, but with the register number from this VarLoc.
595 MOs.push_back(Elt: MachineOperand::CreateReg(
596 Reg: EVKind == EntryValueLocKind::EntryValueKind ? Orig.getReg()
597 : Register(Loc.RegNo),
598 isDef: false));
599 break;
600 case MachineLocKind::SpillLocKind: {
601 // Spills are indirect DBG_VALUEs, with a base register and offset.
602 // Use the original DBG_VALUEs expression to build the spilt location
603 // on top of. FIXME: spill locations created before this pass runs
604 // are not recognized, and not handled here.
605 unsigned Base = Loc.SpillLocation.SpillBase;
606 auto *TRI = MF.getSubtarget().getRegisterInfo();
607 if (MI.isNonListDebugValue()) {
608 auto Deref = Indirect ? DIExpression::DerefAfter : 0;
609 DIExpr = TRI->prependOffsetExpression(
610 Expr: DIExpr, PrependFlags: DIExpression::ApplyOffset | Deref,
611 Offset: Loc.SpillLocation.SpillOffset);
612 Indirect = true;
613 } else {
614 SmallVector<uint64_t, 4> Ops;
615 TRI->getOffsetOpcodes(Offset: Loc.SpillLocation.SpillOffset, Ops);
616 Ops.push_back(Elt: dwarf::DW_OP_deref);
617 DIExpr = DIExpression::appendOpsToArg(Expr: DIExpr, Ops, ArgNo: I);
618 }
619 MOs.push_back(Elt: MachineOperand::CreateReg(Reg: Base, isDef: false));
620 break;
621 }
622 case MachineLocKind::ImmediateKind: {
623 MOs.push_back(Elt: Orig);
624 break;
625 }
626 case MachineLocKind::WasmLocKind:
627 case MachineLocKind::GlobalAddrKind: {
628 MOs.push_back(Elt: Orig);
629 break;
630 }
631 case MachineLocKind::InvalidKind:
632 llvm_unreachable("Tried to produce DBG_VALUE for invalid VarLoc");
633 }
634 }
635 return BuildMI(MF, DL: DbgLoc, MCID: IID, IsIndirect: Indirect, MOs, Variable: Var, Expr: DIExpr);
636 }
637
638 /// Is the Loc field a constant or constant object?
639 bool isConstant(MachineLocKind Kind) const {
640 return Kind == MachineLocKind::ImmediateKind ||
641 Kind == MachineLocKind::GlobalAddrKind;
642 }
643
644 /// Check if the Loc field is an entry backup location.
645 bool isEntryBackupLoc() const {
646 return EVKind == EntryValueLocKind::EntryValueBackupKind ||
647 EVKind == EntryValueLocKind::EntryValueCopyBackupKind;
648 }
649
650 /// If this variable is described by register \p Reg holding the entry
651 /// value, return true.
652 bool isEntryValueBackupReg(Register Reg) const {
653 return EVKind == EntryValueLocKind::EntryValueBackupKind && usesReg(Reg);
654 }
655
656 /// If this variable is described by register \p Reg holding a copy of the
657 /// entry value, return true.
658 bool isEntryValueCopyBackupReg(Register Reg) const {
659 return EVKind == EntryValueLocKind::EntryValueCopyBackupKind &&
660 usesReg(Reg);
661 }
662
663 /// If this variable is described in whole or part by \p Reg, return true.
664 bool usesReg(Register Reg) const {
665 MachineLoc RegML;
666 RegML.Kind = MachineLocKind::RegisterKind;
667 RegML.Value.RegNo = Reg;
668 return is_contained(Range: Locs, Element: RegML);
669 }
670
671 /// If this variable is described in whole or part by \p Reg, return true.
672 unsigned getRegIdx(Register Reg) const {
673 for (unsigned Idx = 0; Idx < Locs.size(); ++Idx)
674 if (Locs[Idx].Kind == MachineLocKind::RegisterKind &&
675 Register{static_cast<unsigned>(Locs[Idx].Value.RegNo)} == Reg)
676 return Idx;
677 llvm_unreachable("Could not find given Reg in Locs");
678 }
679
680 /// If this variable is described in whole or part by 1 or more registers,
681 /// add each of them to \p Regs and return true.
682 bool getDescribingRegs(SmallVectorImpl<uint32_t> &Regs) const {
683 bool AnyRegs = false;
684 for (const auto &Loc : Locs)
685 if (Loc.Kind == MachineLocKind::RegisterKind) {
686 Regs.push_back(Elt: Loc.Value.RegNo);
687 AnyRegs = true;
688 }
689 return AnyRegs;
690 }
691
692 bool containsSpillLocs() const {
693 return any_of(Range: Locs, P: [](VarLoc::MachineLoc ML) {
694 return ML.Kind == VarLoc::MachineLocKind::SpillLocKind;
695 });
696 }
697
698 /// If this variable is described in whole or part by \p SpillLocation,
699 /// return true.
700 bool usesSpillLoc(SpillLoc SpillLocation) const {
701 MachineLoc SpillML;
702 SpillML.Kind = MachineLocKind::SpillLocKind;
703 SpillML.Value.SpillLocation = SpillLocation;
704 return is_contained(Range: Locs, Element: SpillML);
705 }
706
707 /// If this variable is described in whole or part by \p SpillLocation,
708 /// return the index .
709 unsigned getSpillLocIdx(SpillLoc SpillLocation) const {
710 for (unsigned Idx = 0; Idx < Locs.size(); ++Idx)
711 if (Locs[Idx].Kind == MachineLocKind::SpillLocKind &&
712 Locs[Idx].Value.SpillLocation == SpillLocation)
713 return Idx;
714 llvm_unreachable("Could not find given SpillLoc in Locs");
715 }
716
717 bool containsWasmLocs() const {
718 return any_of(Range: Locs, P: [](VarLoc::MachineLoc ML) {
719 return ML.Kind == VarLoc::MachineLocKind::WasmLocKind;
720 });
721 }
722
723 /// If this variable is described in whole or part by \p WasmLocation,
724 /// return true.
725 bool usesWasmLoc(WasmLoc WasmLocation) const {
726 MachineLoc WasmML;
727 WasmML.Kind = MachineLocKind::WasmLocKind;
728 WasmML.Value.WasmLocation = WasmLocation;
729 return is_contained(Range: Locs, Element: WasmML);
730 }
731
732 /// Determine whether the lexical scope of this value's debug location
733 /// dominates MBB.
734 bool dominates(LexicalScopes &LS, MachineBasicBlock &MBB) const {
735 return LS.dominates(DL: MI.getDebugLoc().get(), MBB: &MBB);
736 }
737
738#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
739 // TRI and TII can be null.
740 void dump(const TargetRegisterInfo *TRI, const TargetInstrInfo *TII,
741 raw_ostream &Out = dbgs()) const {
742 Out << "VarLoc(";
743 for (const MachineLoc &MLoc : Locs) {
744 if (Locs.begin() != &MLoc)
745 Out << ", ";
746 switch (MLoc.Kind) {
747 case MachineLocKind::RegisterKind:
748 Out << printReg(MLoc.Value.RegNo, TRI);
749 break;
750 case MachineLocKind::SpillLocKind:
751 Out << printReg(MLoc.Value.SpillLocation.SpillBase, TRI);
752 Out << "[" << MLoc.Value.SpillLocation.SpillOffset.getFixed() << " + "
753 << MLoc.Value.SpillLocation.SpillOffset.getScalable()
754 << "x vscale"
755 << "]";
756 break;
757 case MachineLocKind::ImmediateKind:
758 Out << MLoc.Value.Immediate;
759 break;
760 case MachineLocKind::GlobalAddrKind:
761 Out << MLoc.Value.GlobalAddress.GV->getName();
762 if (MLoc.Value.GlobalAddress.Offset)
763 Out << '+' << MLoc.Value.GlobalAddress.Offset;
764 break;
765 case MachineLocKind::WasmLocKind: {
766 if (TII) {
767 auto Indices = TII->getSerializableTargetIndices();
768 auto Found =
769 find_if(Indices, [&](const std::pair<int, const char *> &I) {
770 return I.first == MLoc.Value.WasmLocation.Index;
771 });
772 assert(Found != Indices.end());
773 Out << Found->second;
774 if (MLoc.Value.WasmLocation.Offset > 0)
775 Out << " + " << MLoc.Value.WasmLocation.Offset;
776 } else {
777 Out << "WasmLoc";
778 }
779 break;
780 }
781 case MachineLocKind::InvalidKind:
782 llvm_unreachable("Invalid VarLoc in dump method");
783 }
784 }
785
786 Out << ", \"" << Var.getVariable()->getName() << "\", " << *Expr << ", ";
787 if (Var.getInlinedAt())
788 Out << "!" << Var.getInlinedAt()->getMetadataID() << ")\n";
789 else
790 Out << "(null))";
791
792 if (isEntryBackupLoc())
793 Out << " (backup loc)\n";
794 else
795 Out << "\n";
796 }
797#endif
798
799 bool operator==(const VarLoc &Other) const {
800 return std::tie(args: EVKind, args: Var, args: Expr, args: Locs) ==
801 std::tie(args: Other.EVKind, args: Other.Var, args: Other.Expr, args: Other.Locs);
802 }
803
804 /// This operator guarantees that VarLocs are sorted by Variable first.
805 bool operator<(const VarLoc &Other) const {
806 return std::tie(args: Var, args: EVKind, args: Locs, args: Expr) <
807 std::tie(args: Other.Var, args: Other.EVKind, args: Other.Locs, args: Other.Expr);
808 }
809 };
810
811#ifndef NDEBUG
812 using VarVec = SmallVector<VarLoc, 32>;
813#endif
814
815 /// VarLocMap is used for two things:
816 /// 1) Assigning LocIndices to a VarLoc. The LocIndices can be used to
817 /// virtually insert a VarLoc into a VarLocSet.
818 /// 2) Given a LocIndex, look up the unique associated VarLoc.
819 class VarLocMap {
820 /// Map a VarLoc to an index within the vector reserved for its location
821 /// within Loc2Vars.
822 std::map<VarLoc, LocIndices> Var2Indices;
823
824 /// Map a location to a vector which holds VarLocs which live in that
825 /// location.
826 SmallDenseMap<LocIndex::u32_location_t, std::vector<VarLoc>> Loc2Vars;
827
828 public:
829 /// Retrieve LocIndices for \p VL.
830 LocIndices insert(const VarLoc &VL) {
831 LocIndices &Indices = Var2Indices[VL];
832 // If Indices is not empty, VL is already in the map.
833 if (!Indices.empty())
834 return Indices;
835 SmallVector<LocIndex::u32_location_t, 4> Locations;
836 // LocIndices are determined by EVKind and MLs; each Register has a
837 // unique location, while all SpillLocs use a single bucket, and any EV
838 // VarLocs use only the Backup bucket or none at all (except the
839 // compulsory entry at the universal location index). LocIndices will
840 // always have an index at the universal location index as the last index.
841 if (VL.EVKind == VarLoc::EntryValueLocKind::NonEntryValueKind) {
842 VL.getDescribingRegs(Regs&: Locations);
843 assert(all_of(Locations,
844 [](auto RegNo) {
845 return (RegNo < LocIndex::kFirstInvalidRegLocation) ||
846 (LocIndex::kFirstVirtualRegLocation <= RegNo);
847 }) &&
848 "Physical or virtual register out of range?");
849 if (VL.containsSpillLocs())
850 Locations.push_back(Elt: LocIndex::kSpillLocation);
851 if (VL.containsWasmLocs())
852 Locations.push_back(Elt: LocIndex::kWasmLocation);
853 } else if (VL.EVKind != VarLoc::EntryValueLocKind::EntryValueKind) {
854 LocIndex::u32_location_t Loc = LocIndex::kEntryValueBackupLocation;
855 Locations.push_back(Elt: Loc);
856 }
857 Locations.push_back(Elt: LocIndex::kUniversalLocation);
858 for (LocIndex::u32_location_t Location : Locations) {
859 auto &Vars = Loc2Vars[Location];
860 Indices.push_back(
861 Elt: {Location, static_cast<LocIndex::u32_index_t>(Vars.size())});
862 Vars.push_back(x: VL);
863 }
864 return Indices;
865 }
866
867 LocIndices getAllIndices(const VarLoc &VL) const {
868 auto IndIt = Var2Indices.find(x: VL);
869 assert(IndIt != Var2Indices.end() && "VarLoc not tracked");
870 return IndIt->second;
871 }
872
873 /// Retrieve the unique VarLoc associated with \p ID.
874 const VarLoc &operator[](LocIndex ID) const {
875 auto LocIt = Loc2Vars.find(Val: ID.Location);
876 assert(LocIt != Loc2Vars.end() && "Location not tracked");
877 return LocIt->second[ID.Index];
878 }
879 };
880
881 using VarLocInMBB =
882 SmallDenseMap<const MachineBasicBlock *, std::unique_ptr<VarLocSet>>;
883 struct TransferDebugPair {
884 MachineInstr *TransferInst; ///< Instruction where this transfer occurs.
885 LocIndex LocationID; ///< Location number for the transfer dest.
886 };
887 using TransferMap = SmallVector<TransferDebugPair, 4>;
888 // Types for recording Entry Var Locations emitted by a single MachineInstr,
889 // as well as recording MachineInstr which last defined a register.
890 using InstToEntryLocMap = std::multimap<const MachineInstr *, LocIndex>;
891 using RegDefToInstMap = DenseMap<Register, MachineInstr *>;
892
893 // Types for recording sets of variable fragments that overlap. For a given
894 // local variable, we record all other fragments of that variable that could
895 // overlap it, to reduce search time.
896 using FragmentOfVar =
897 std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
898 using OverlapMap =
899 DenseMap<FragmentOfVar, SmallVector<DIExpression::FragmentInfo, 1>>;
900
901 // Helper while building OverlapMap, a map of all fragments seen for a given
902 // DILocalVariable.
903 using VarToFragments =
904 DenseMap<const DILocalVariable *, SmallSet<FragmentInfo, 4>>;
905
906 /// Collects all VarLocs from \p CollectFrom. Each unique VarLoc is added
907 /// to \p Collected once, in order of insertion into \p VarLocIDs.
908 static void collectAllVarLocs(SmallVectorImpl<VarLoc> &Collected,
909 const VarLocSet &CollectFrom,
910 const VarLocMap &VarLocIDs);
911
912 /// Get the registers which are used by VarLocs of kind RegisterKind tracked
913 /// by \p CollectFrom.
914 void getUsedRegs(const VarLocSet &CollectFrom,
915 SmallVectorImpl<Register> &UsedRegs) const;
916
917 /// This holds the working set of currently open ranges. For fast
918 /// access, this is done both as a set of VarLocIDs, and a map of
919 /// DebugVariable to recent VarLocID. Note that a DBG_VALUE ends all
920 /// previous open ranges for the same variable. In addition, we keep
921 /// two different maps (Vars/EntryValuesBackupVars), so erase/insert
922 /// methods act differently depending on whether a VarLoc is primary
923 /// location or backup one. In the case the VarLoc is backup location
924 /// we will erase/insert from the EntryValuesBackupVars map, otherwise
925 /// we perform the operation on the Vars.
926 class OpenRangesSet {
927 VarLocSet::Allocator &Alloc;
928 VarLocSet VarLocs;
929 // Map the DebugVariable to recent primary location ID.
930 SmallDenseMap<DebugVariable, LocIndices, 8> Vars;
931 // Map the DebugVariable to recent backup location ID.
932 SmallDenseMap<DebugVariable, LocIndices, 8> EntryValuesBackupVars;
933 OverlapMap &OverlappingFragments;
934
935 public:
936 OpenRangesSet(VarLocSet::Allocator &Alloc, OverlapMap &_OLapMap)
937 : Alloc(Alloc), VarLocs(Alloc), OverlappingFragments(_OLapMap) {}
938
939 const VarLocSet &getVarLocs() const { return VarLocs; }
940
941 // Fetches all VarLocs in \p VarLocIDs and inserts them into \p Collected.
942 // This method is needed to get every VarLoc once, as each VarLoc may have
943 // multiple indices in a VarLocMap (corresponding to each applicable
944 // location), but all VarLocs appear exactly once at the universal location
945 // index.
946 void getUniqueVarLocs(SmallVectorImpl<VarLoc> &Collected,
947 const VarLocMap &VarLocIDs) const {
948 collectAllVarLocs(Collected, CollectFrom: VarLocs, VarLocIDs);
949 }
950
951 /// Terminate all open ranges for VL.Var by removing it from the set.
952 void erase(const VarLoc &VL);
953
954 /// Terminate all open ranges listed as indices in \c KillSet with
955 /// \c Location by removing them from the set.
956 void erase(const VarLocsInRange &KillSet, const VarLocMap &VarLocIDs,
957 LocIndex::u32_location_t Location);
958
959 /// Insert a new range into the set.
960 void insert(LocIndices VarLocIDs, const VarLoc &VL);
961
962 /// Insert a set of ranges.
963 void insertFromLocSet(const VarLocSet &ToLoad, const VarLocMap &Map);
964
965 std::optional<LocIndices> getEntryValueBackup(DebugVariable Var);
966
967 /// Empty the set.
968 void clear() {
969 VarLocs.clear();
970 Vars.clear();
971 EntryValuesBackupVars.clear();
972 }
973
974 /// Return whether the set is empty or not.
975 bool empty() const {
976 assert(Vars.empty() == EntryValuesBackupVars.empty() &&
977 Vars.empty() == VarLocs.empty() &&
978 "open ranges are inconsistent");
979 return VarLocs.empty();
980 }
981
982 /// Get an empty range of VarLoc IDs.
983 auto getEmptyVarLocRange() const {
984 return iterator_range<VarLocSet::const_iterator>(getVarLocs().end(),
985 getVarLocs().end());
986 }
987
988 /// Get all set IDs for VarLocs with MLs of kind RegisterKind in \p Reg.
989 auto getRegisterVarLocs(Register Reg) const {
990 return LocIndex::indexRangeForLocation(Set: getVarLocs(), Location: Reg);
991 }
992
993 /// Get all set IDs for VarLocs with MLs of kind SpillLocKind.
994 auto getSpillVarLocs() const {
995 return LocIndex::indexRangeForLocation(Set: getVarLocs(),
996 Location: LocIndex::kSpillLocation);
997 }
998
999 /// Get all set IDs for VarLocs of EVKind EntryValueBackupKind or
1000 /// EntryValueCopyBackupKind.
1001 auto getEntryValueBackupVarLocs() const {
1002 return LocIndex::indexRangeForLocation(
1003 Set: getVarLocs(), Location: LocIndex::kEntryValueBackupLocation);
1004 }
1005
1006 /// Get all set IDs for VarLocs with MLs of kind WasmLocKind.
1007 auto getWasmVarLocs() const {
1008 return LocIndex::indexRangeForLocation(Set: getVarLocs(),
1009 Location: LocIndex::kWasmLocation);
1010 }
1011 };
1012
1013 /// Collect all VarLoc IDs from \p CollectFrom for VarLocs with MLs of kind
1014 /// RegisterKind which are located in any reg in \p Regs. The IDs for each
1015 /// VarLoc correspond to entries in the universal location bucket, which every
1016 /// VarLoc has exactly 1 entry for. Insert collected IDs into \p Collected.
1017 static void collectIDsForRegs(VarLocsInRange &Collected,
1018 ArrayRef<Register> Regs,
1019 const VarLocSet &CollectFrom,
1020 const VarLocMap &VarLocIDs);
1021
1022 VarLocSet &getVarLocsInMBB(const MachineBasicBlock *MBB, VarLocInMBB &Locs) {
1023 std::unique_ptr<VarLocSet> &VLS = Locs[MBB];
1024 if (!VLS)
1025 VLS = std::make_unique<VarLocSet>(args&: Alloc);
1026 return *VLS;
1027 }
1028
1029 const VarLocSet &getVarLocsInMBB(const MachineBasicBlock *MBB,
1030 const VarLocInMBB &Locs) const {
1031 auto It = Locs.find(Val: MBB);
1032 assert(It != Locs.end() && "MBB not in map");
1033 return *It->second;
1034 }
1035
1036 /// Tests whether this instruction is a spill to a stack location.
1037 bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF);
1038
1039 /// Decide if @MI is a spill instruction and return true if it is. We use 2
1040 /// criteria to make this decision:
1041 /// - Is this instruction a store to a spill slot?
1042 /// - Is there a register operand that is both used and killed?
1043 /// TODO: Store optimization can fold spills into other stores (including
1044 /// other spills). We do not handle this yet (more than one memory operand).
1045 bool isLocationSpill(const MachineInstr &MI, MachineFunction *MF,
1046 Register &Reg);
1047
1048 /// Returns true if the given machine instruction is a debug value which we
1049 /// can emit entry values for.
1050 ///
1051 /// Currently, we generate debug entry values only for parameters that are
1052 /// unmodified throughout the function and located in a register.
1053 bool isEntryValueCandidate(const MachineInstr &MI,
1054 const DefinedRegsSet &Regs) const;
1055
1056 /// If a given instruction is identified as a spill, return the spill location
1057 /// and set \p Reg to the spilled register.
1058 std::optional<VarLoc::SpillLoc> isRestoreInstruction(const MachineInstr &MI,
1059 MachineFunction *MF,
1060 Register &Reg);
1061 /// Given a spill instruction, extract the register and offset used to
1062 /// address the spill location in a target independent way.
1063 VarLoc::SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI);
1064 void insertTransferDebugPair(MachineInstr &MI, OpenRangesSet &OpenRanges,
1065 TransferMap &Transfers, VarLocMap &VarLocIDs,
1066 LocIndex OldVarID, TransferKind Kind,
1067 const VarLoc::MachineLoc &OldLoc,
1068 Register NewReg = Register());
1069
1070 void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
1071 VarLocMap &VarLocIDs,
1072 InstToEntryLocMap &EntryValTransfers,
1073 RegDefToInstMap &RegSetInstrs);
1074 void transferSpillOrRestoreInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
1075 VarLocMap &VarLocIDs, TransferMap &Transfers);
1076 void cleanupEntryValueTransfers(const MachineInstr *MI,
1077 OpenRangesSet &OpenRanges,
1078 VarLocMap &VarLocIDs, const VarLoc &EntryVL,
1079 InstToEntryLocMap &EntryValTransfers);
1080 void removeEntryValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
1081 VarLocMap &VarLocIDs, const VarLoc &EntryVL,
1082 InstToEntryLocMap &EntryValTransfers,
1083 RegDefToInstMap &RegSetInstrs);
1084 void emitEntryValues(MachineInstr &MI, OpenRangesSet &OpenRanges,
1085 VarLocMap &VarLocIDs,
1086 InstToEntryLocMap &EntryValTransfers,
1087 VarLocsInRange &KillSet);
1088 void recordEntryValue(const MachineInstr &MI,
1089 const DefinedRegsSet &DefinedRegs,
1090 OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs);
1091 void transferRegisterCopy(MachineInstr &MI, OpenRangesSet &OpenRanges,
1092 VarLocMap &VarLocIDs, TransferMap &Transfers);
1093 void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
1094 VarLocMap &VarLocIDs,
1095 InstToEntryLocMap &EntryValTransfers,
1096 RegDefToInstMap &RegSetInstrs);
1097 void transferWasmDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
1098 VarLocMap &VarLocIDs);
1099 bool transferTerminator(MachineBasicBlock *MBB, OpenRangesSet &OpenRanges,
1100 VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs);
1101
1102 void process(MachineInstr &MI, OpenRangesSet &OpenRanges,
1103 VarLocMap &VarLocIDs, TransferMap &Transfers,
1104 InstToEntryLocMap &EntryValTransfers,
1105 RegDefToInstMap &RegSetInstrs);
1106
1107 void accumulateFragmentMap(MachineInstr &MI, VarToFragments &SeenFragments,
1108 OverlapMap &OLapMap);
1109
1110 bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
1111 const VarLocMap &VarLocIDs,
1112 SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
1113 SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks);
1114
1115 /// Create DBG_VALUE insts for inlocs that have been propagated but
1116 /// had their instruction creation deferred.
1117 void flushPendingLocs(VarLocInMBB &PendingInLocs, VarLocMap &VarLocIDs);
1118
1119 bool ExtendRanges(MachineFunction &MF, MachineDominatorTree *DomTree,
1120 bool ShouldEmitDebugEntryValues, unsigned InputBBLimit,
1121 unsigned InputDbgValLimit) override;
1122
1123public:
1124 /// Default construct and initialize the pass.
1125 VarLocBasedLDV();
1126
1127 ~VarLocBasedLDV() override;
1128
1129 /// Print to ostream with a message.
1130 void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V,
1131 const VarLocMap &VarLocIDs, const char *msg,
1132 raw_ostream &Out) const;
1133};
1134
1135} // end anonymous namespace
1136
1137//===----------------------------------------------------------------------===//
1138// Implementation
1139//===----------------------------------------------------------------------===//
1140
1141VarLocBasedLDV::VarLocBasedLDV() = default;
1142
1143VarLocBasedLDV::~VarLocBasedLDV() = default;
1144
1145/// Erase a variable from the set of open ranges, and additionally erase any
1146/// fragments that may overlap it. If the VarLoc is a backup location, erase
1147/// the variable from the EntryValuesBackupVars set, indicating we should stop
1148/// tracking its backup entry location. Otherwise, if the VarLoc is primary
1149/// location, erase the variable from the Vars set.
1150void VarLocBasedLDV::OpenRangesSet::erase(const VarLoc &VL) {
1151 // Erasure helper.
1152 auto DoErase = [&VL, this](DebugVariable VarToErase) {
1153 auto *EraseFrom = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
1154 auto It = EraseFrom->find(Val: VarToErase);
1155 if (It != EraseFrom->end()) {
1156 LocIndices IDs = It->second;
1157 for (LocIndex ID : IDs)
1158 VarLocs.reset(Index: ID.getAsRawInteger());
1159 EraseFrom->erase(I: It);
1160 }
1161 };
1162
1163 DebugVariable Var = VL.Var;
1164
1165 // Erase the variable/fragment that ends here.
1166 DoErase(Var);
1167
1168 // Extract the fragment. Interpret an empty fragment as one that covers all
1169 // possible bits.
1170 FragmentInfo ThisFragment = Var.getFragmentOrDefault();
1171
1172 // There may be fragments that overlap the designated fragment. Look them up
1173 // in the pre-computed overlap map, and erase them too.
1174 auto MapIt = OverlappingFragments.find(Val: {Var.getVariable(), ThisFragment});
1175 if (MapIt != OverlappingFragments.end()) {
1176 for (auto Fragment : MapIt->second) {
1177 VarLocBasedLDV::OptFragmentInfo FragmentHolder;
1178 if (!DebugVariable::isDefaultFragment(F: Fragment))
1179 FragmentHolder = VarLocBasedLDV::OptFragmentInfo(Fragment);
1180 DoErase({Var.getVariable(), FragmentHolder, Var.getInlinedAt()});
1181 }
1182 }
1183}
1184
1185void VarLocBasedLDV::OpenRangesSet::erase(const VarLocsInRange &KillSet,
1186 const VarLocMap &VarLocIDs,
1187 LocIndex::u32_location_t Location) {
1188 VarLocSet RemoveSet(Alloc);
1189 for (LocIndex::u32_index_t ID : KillSet) {
1190 const VarLoc &VL = VarLocIDs[LocIndex(Location, ID)];
1191 auto *EraseFrom = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
1192 EraseFrom->erase(Val: VL.Var);
1193 LocIndices VLI = VarLocIDs.getAllIndices(VL);
1194 for (LocIndex ID : VLI)
1195 RemoveSet.set(ID.getAsRawInteger());
1196 }
1197 VarLocs.intersectWithComplement(Other: RemoveSet);
1198}
1199
1200void VarLocBasedLDV::OpenRangesSet::insertFromLocSet(const VarLocSet &ToLoad,
1201 const VarLocMap &Map) {
1202 VarLocsInRange UniqueVarLocIDs;
1203 Register UniversalLoc = LocIndex::kUniversalLocation;
1204 collectIDsForRegs(Collected&: UniqueVarLocIDs, Regs: UniversalLoc, CollectFrom: ToLoad, VarLocIDs: Map);
1205 for (uint64_t ID : UniqueVarLocIDs) {
1206 LocIndex Idx = LocIndex::fromRawInteger(ID);
1207 const VarLoc &VarL = Map[Idx];
1208 const LocIndices Indices = Map.getAllIndices(VL: VarL);
1209 insert(VarLocIDs: Indices, VL: VarL);
1210 }
1211}
1212
1213void VarLocBasedLDV::OpenRangesSet::insert(LocIndices VarLocIDs,
1214 const VarLoc &VL) {
1215 auto *InsertInto = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
1216 for (LocIndex ID : VarLocIDs)
1217 VarLocs.set(ID.getAsRawInteger());
1218 InsertInto->insert(KV: {VL.Var, VarLocIDs});
1219}
1220
1221/// Return the Loc ID of an entry value backup location, if it exists for the
1222/// variable.
1223std::optional<LocIndices>
1224VarLocBasedLDV::OpenRangesSet::getEntryValueBackup(DebugVariable Var) {
1225 auto It = EntryValuesBackupVars.find(Val: Var);
1226 if (It != EntryValuesBackupVars.end())
1227 return It->second;
1228
1229 return std::nullopt;
1230}
1231
1232void VarLocBasedLDV::collectIDsForRegs(VarLocsInRange &Collected,
1233 ArrayRef<Register> Regs,
1234 const VarLocSet &CollectFrom,
1235 const VarLocMap &VarLocIDs) {
1236 assert(!Regs.empty() && "Nothing to collect");
1237 if (CollectFrom.empty())
1238 return;
1239 SmallVector<Register, 32> SortedRegs;
1240 append_range(C&: SortedRegs, R&: Regs);
1241 llvm::sort(C&: SortedRegs, Comp: [](Register LHS, Register RHS) { return LHS < RHS; });
1242 SortedRegs.erase(CS: llvm::unique(R&: SortedRegs), CE: SortedRegs.end());
1243 auto It = CollectFrom.find(Index: LocIndex::rawIndexForReg(Reg: SortedRegs.front()));
1244 auto End = CollectFrom.end();
1245 for (Register Reg : SortedRegs) {
1246 // The half-open interval [FirstIndexForReg, FirstInvalidIndex) contains
1247 // all possible VarLoc IDs for VarLocs with MLs of kind RegisterKind which
1248 // live in Reg.
1249 uint64_t FirstIndexForReg = LocIndex::rawIndexForReg(Reg);
1250 uint64_t FirstInvalidIndex = LocIndex::rawIndexForReg(Reg: Reg + 1);
1251 It.advanceToLowerBound(Index: FirstIndexForReg);
1252
1253 // Iterate through that half-open interval and collect all the set IDs.
1254 for (; It != End && *It < FirstInvalidIndex; ++It) {
1255 LocIndex ItIdx = LocIndex::fromRawInteger(ID: *It);
1256 const VarLoc &VL = VarLocIDs[ItIdx];
1257 LocIndices LI = VarLocIDs.getAllIndices(VL);
1258 // For now, the back index is always the universal location index.
1259 assert(LI.back().Location == LocIndex::kUniversalLocation &&
1260 "Unexpected order of LocIndices for VarLoc; was it inserted into "
1261 "the VarLocMap correctly?");
1262 Collected.insert(V: LI.back().Index);
1263 }
1264
1265 if (It == End)
1266 return;
1267 }
1268}
1269
1270void VarLocBasedLDV::getUsedRegs(const VarLocSet &CollectFrom,
1271 SmallVectorImpl<Register> &UsedRegs) const {
1272 // All register-based VarLocs are assigned indices greater than or equal to
1273 // FirstRegIndex.
1274 uint64_t FirstRegIndex =
1275 LocIndex::rawIndexForReg(Reg: LocIndex::kFirstRegLocation);
1276 uint64_t FirstInvalidIndex =
1277 LocIndex::rawIndexForReg(Reg: LocIndex::kFirstInvalidRegLocation);
1278 uint64_t FirstVirtualRegIndex =
1279 LocIndex::rawIndexForReg(Reg: LocIndex::kFirstVirtualRegLocation);
1280 auto doGetUsedRegs = [&](VarLocSet::const_iterator &It) {
1281 // We found a VarLoc ID for a VarLoc that lives in a register. Figure out
1282 // which register and add it to UsedRegs.
1283 uint32_t FoundReg = LocIndex::fromRawInteger(ID: *It).Location;
1284 assert((UsedRegs.empty() || FoundReg != UsedRegs.back()) &&
1285 "Duplicate used reg");
1286 UsedRegs.push_back(Elt: FoundReg);
1287
1288 // Skip to the next /set/ register. Note that this finds a lower bound, so
1289 // even if there aren't any VarLocs living in `FoundReg+1`, we're still
1290 // guaranteed to move on to the next register (or to end()).
1291 uint64_t NextRegIndex = LocIndex::rawIndexForReg(Reg: FoundReg + 1);
1292 It.advanceToLowerBound(Index: NextRegIndex);
1293 };
1294 for (auto It = CollectFrom.find(Index: FirstRegIndex),
1295 End = CollectFrom.find(Index: FirstInvalidIndex);
1296 It != End;) {
1297 doGetUsedRegs(It);
1298 }
1299 for (auto It = CollectFrom.find(Index: FirstVirtualRegIndex),
1300 End = CollectFrom.end();
1301 It != End;) {
1302 doGetUsedRegs(It);
1303 }
1304}
1305
1306//===----------------------------------------------------------------------===//
1307// Debug Range Extension Implementation
1308//===----------------------------------------------------------------------===//
1309
1310#ifndef NDEBUG
1311void VarLocBasedLDV::printVarLocInMBB(const MachineFunction &MF,
1312 const VarLocInMBB &V,
1313 const VarLocMap &VarLocIDs,
1314 const char *msg,
1315 raw_ostream &Out) const {
1316 Out << '\n' << msg << '\n';
1317 for (const MachineBasicBlock &BB : MF) {
1318 if (!V.count(&BB))
1319 continue;
1320 const VarLocSet &L = getVarLocsInMBB(&BB, V);
1321 if (L.empty())
1322 continue;
1323 SmallVector<VarLoc, 32> VarLocs;
1324 collectAllVarLocs(VarLocs, L, VarLocIDs);
1325 Out << "MBB: " << BB.getNumber() << ":\n";
1326 for (const VarLoc &VL : VarLocs) {
1327 Out << " Var: " << VL.Var.getVariable()->getName();
1328 Out << " MI: ";
1329 VL.dump(TRI, TII, Out);
1330 }
1331 }
1332 Out << "\n";
1333}
1334#endif
1335
1336VarLocBasedLDV::VarLoc::SpillLoc
1337VarLocBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
1338 assert(MI.hasOneMemOperand() &&
1339 "Spill instruction does not have exactly one memory operand?");
1340 auto MMOI = MI.memoperands_begin();
1341 const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
1342 assert(PVal->kind() == PseudoSourceValue::FixedStack &&
1343 "Inconsistent memory operand in spill instruction");
1344 int FI = cast<FixedStackPseudoSourceValue>(Val: PVal)->getFrameIndex();
1345 const MachineBasicBlock *MBB = MI.getParent();
1346 Register Reg;
1347 StackOffset Offset = TFI->getFrameIndexReference(MF: *MBB->getParent(), FI, FrameReg&: Reg);
1348 return {.SpillBase: Reg, .SpillOffset: Offset};
1349}
1350
1351/// Do cleanup of \p EntryValTransfers created by \p TRInst, by removing the
1352/// Transfer, which uses the to-be-deleted \p EntryVL.
1353void VarLocBasedLDV::cleanupEntryValueTransfers(
1354 const MachineInstr *TRInst, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs,
1355 const VarLoc &EntryVL, InstToEntryLocMap &EntryValTransfers) {
1356 if (EntryValTransfers.empty() || TRInst == nullptr)
1357 return;
1358
1359 auto TransRange = EntryValTransfers.equal_range(x: TRInst);
1360 for (auto &TDPair : llvm::make_range(p: TransRange)) {
1361 const VarLoc &EmittedEV = VarLocIDs[TDPair.second];
1362 if (std::tie(args: EntryVL.Var, args: EntryVL.Locs[0].Value.RegNo, args: EntryVL.Expr) ==
1363 std::tie(args: EmittedEV.Var, args: EmittedEV.Locs[0].Value.RegNo,
1364 args: EmittedEV.Expr)) {
1365 OpenRanges.erase(VL: EmittedEV);
1366 EntryValTransfers.erase(x: TRInst);
1367 break;
1368 }
1369 }
1370}
1371
1372/// Try to salvage the debug entry value if we encounter a new debug value
1373/// describing the same parameter, otherwise stop tracking the value. Return
1374/// true if we should stop tracking the entry value and do the cleanup of
1375/// emitted Entry Value Transfers, otherwise return false.
1376void VarLocBasedLDV::removeEntryValue(const MachineInstr &MI,
1377 OpenRangesSet &OpenRanges,
1378 VarLocMap &VarLocIDs,
1379 const VarLoc &EntryVL,
1380 InstToEntryLocMap &EntryValTransfers,
1381 RegDefToInstMap &RegSetInstrs) {
1382 // Skip the DBG_VALUE which is the debug entry value itself.
1383 if (&MI == &EntryVL.MI)
1384 return;
1385
1386 // If the parameter's location is not register location, we can not track
1387 // the entry value any more. It doesn't have the TransferInst which defines
1388 // register, so no Entry Value Transfers have been emitted already.
1389 if (!MI.getDebugOperand(Index: 0).isReg())
1390 return;
1391
1392 // Try to get non-debug instruction responsible for the DBG_VALUE.
1393 Register Reg = MI.getDebugOperand(Index: 0).getReg();
1394 const MachineInstr *TransferInst =
1395 Reg.isValid() ? RegSetInstrs.lookup(Val: Reg) : nullptr;
1396
1397 // Case of the parameter's DBG_VALUE at the start of entry MBB.
1398 if (!TransferInst && !LastNonDbgMI && MI.getParent()->isEntryBlock())
1399 return;
1400
1401 // If the debug expression from the DBG_VALUE is not empty, we can assume the
1402 // parameter's value has changed indicating that we should stop tracking its
1403 // entry value as well.
1404 if (MI.getDebugExpression()->getNumElements() == 0 && TransferInst) {
1405 // If the DBG_VALUE comes from a copy instruction that copies the entry
1406 // value, it means the parameter's value has not changed and we should be
1407 // able to use its entry value.
1408 // TODO: Try to keep tracking of an entry value if we encounter a propagated
1409 // DBG_VALUE describing the copy of the entry value. (Propagated entry value
1410 // does not indicate the parameter modification.)
1411 auto DestSrc = TII->isCopyLikeInstr(MI: *TransferInst);
1412 if (DestSrc) {
1413 const MachineOperand *SrcRegOp, *DestRegOp;
1414 SrcRegOp = DestSrc->Source;
1415 DestRegOp = DestSrc->Destination;
1416 if (Reg == DestRegOp->getReg()) {
1417 for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) {
1418 const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(ID)];
1419 if (VL.isEntryValueCopyBackupReg(Reg) &&
1420 // Entry Values should not be variadic.
1421 VL.MI.getDebugOperand(Index: 0).getReg() == SrcRegOp->getReg())
1422 return;
1423 }
1424 }
1425 }
1426 }
1427
1428 LLVM_DEBUG(dbgs() << "Deleting a DBG entry value because of: ";
1429 MI.print(dbgs(), /*IsStandalone*/ false,
1430 /*SkipOpers*/ false, /*SkipDebugLoc*/ false,
1431 /*AddNewLine*/ true, TII));
1432 cleanupEntryValueTransfers(TRInst: TransferInst, OpenRanges, VarLocIDs, EntryVL,
1433 EntryValTransfers);
1434 OpenRanges.erase(VL: EntryVL);
1435}
1436
1437/// End all previous ranges related to @MI and start a new range from @MI
1438/// if it is a DBG_VALUE instr.
1439void VarLocBasedLDV::transferDebugValue(const MachineInstr &MI,
1440 OpenRangesSet &OpenRanges,
1441 VarLocMap &VarLocIDs,
1442 InstToEntryLocMap &EntryValTransfers,
1443 RegDefToInstMap &RegSetInstrs) {
1444 if (!MI.isDebugValue())
1445 return;
1446 const DILocalVariable *Var = MI.getDebugVariable();
1447 const DIExpression *Expr = MI.getDebugExpression();
1448 const DILocation *DebugLoc = MI.getDebugLoc();
1449 const DILocation *InlinedAt = DebugLoc->getInlinedAt();
1450 assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
1451 "Expected inlined-at fields to agree");
1452
1453 DebugVariable V(Var, Expr, InlinedAt);
1454
1455 // Check if this DBG_VALUE indicates a parameter's value changing.
1456 // If that is the case, we should stop tracking its entry value.
1457 auto EntryValBackupID = OpenRanges.getEntryValueBackup(Var: V);
1458 if (Var->isParameter() && EntryValBackupID) {
1459 const VarLoc &EntryVL = VarLocIDs[EntryValBackupID->back()];
1460 removeEntryValue(MI, OpenRanges, VarLocIDs, EntryVL, EntryValTransfers,
1461 RegSetInstrs);
1462 }
1463
1464 if (all_of(Range: MI.debug_operands(), P: [](const MachineOperand &MO) {
1465 return (MO.isReg() && MO.getReg()) || MO.isImm() || MO.isFPImm() ||
1466 MO.isCImm() || MO.isTargetIndex() || MO.isGlobal();
1467 })) {
1468 // Use the normal VarLoc constructor for every operand kind MachineLoc can
1469 // hold directly: registers, immediates, WebAssembly locals and globals.
1470 VarLoc VL(MI);
1471 // End all previous ranges of VL.Var.
1472 OpenRanges.erase(VL);
1473
1474 LocIndices IDs = VarLocIDs.insert(VL);
1475 // Add the VarLoc to OpenRanges from this DBG_VALUE.
1476 OpenRanges.insert(VarLocIDs: IDs, VL);
1477 } else if (MI.memoperands().size() > 0) {
1478 llvm_unreachable("DBG_VALUE with mem operand encountered after regalloc?");
1479 } else {
1480 // This must be an undefined location. If it has an open range, erase it.
1481 assert(MI.isUndefDebugValue() &&
1482 "Unexpected non-undef DBG_VALUE encountered");
1483 VarLoc VL(MI);
1484 OpenRanges.erase(VL);
1485 }
1486}
1487
1488// This should be removed later, doesn't fit the new design.
1489void VarLocBasedLDV::collectAllVarLocs(SmallVectorImpl<VarLoc> &Collected,
1490 const VarLocSet &CollectFrom,
1491 const VarLocMap &VarLocIDs) {
1492 // The half-open interval [FirstIndexForReg, FirstInvalidIndex) contains all
1493 // possible VarLoc IDs for VarLocs with MLs of kind RegisterKind which live
1494 // in Reg.
1495 uint64_t FirstIndex = LocIndex::rawIndexForReg(Reg: LocIndex::kUniversalLocation);
1496 uint64_t FirstInvalidIndex =
1497 LocIndex::rawIndexForReg(Reg: LocIndex::kUniversalLocation + 1);
1498 // Iterate through that half-open interval and collect all the set IDs.
1499 for (auto It = CollectFrom.find(Index: FirstIndex), End = CollectFrom.end();
1500 It != End && *It < FirstInvalidIndex; ++It) {
1501 LocIndex RegIdx = LocIndex::fromRawInteger(ID: *It);
1502 Collected.push_back(Elt: VarLocIDs[RegIdx]);
1503 }
1504}
1505
1506/// Turn the entry value backup locations into primary locations.
1507void VarLocBasedLDV::emitEntryValues(MachineInstr &MI,
1508 OpenRangesSet &OpenRanges,
1509 VarLocMap &VarLocIDs,
1510 InstToEntryLocMap &EntryValTransfers,
1511 VarLocsInRange &KillSet) {
1512 // Do not insert entry value locations after a terminator.
1513 if (MI.isTerminator())
1514 return;
1515
1516 for (uint32_t ID : KillSet) {
1517 // The KillSet IDs are indices for the universal location bucket.
1518 LocIndex Idx = LocIndex(LocIndex::kUniversalLocation, ID);
1519 const VarLoc &VL = VarLocIDs[Idx];
1520 if (!VL.Var.getVariable()->isParameter())
1521 continue;
1522
1523 auto DebugVar = VL.Var;
1524 std::optional<LocIndices> EntryValBackupIDs =
1525 OpenRanges.getEntryValueBackup(Var: DebugVar);
1526
1527 // If the parameter has the entry value backup, it means we should
1528 // be able to use its entry value.
1529 if (!EntryValBackupIDs)
1530 continue;
1531
1532 const VarLoc &EntryVL = VarLocIDs[EntryValBackupIDs->back()];
1533 VarLoc EntryLoc = VarLoc::CreateEntryLoc(MI: EntryVL.MI, EntryExpr: EntryVL.Expr,
1534 Reg: EntryVL.Locs[0].Value.RegNo);
1535 LocIndices EntryValueIDs = VarLocIDs.insert(VL: EntryLoc);
1536 assert(EntryValueIDs.size() == 1 &&
1537 "EntryValue loc should not be variadic");
1538 EntryValTransfers.insert(x: {&MI, EntryValueIDs.back()});
1539 OpenRanges.insert(VarLocIDs: EntryValueIDs, VL: EntryLoc);
1540 }
1541}
1542
1543/// Create new TransferDebugPair and insert it in \p Transfers. The VarLoc
1544/// with \p OldVarID should be deleted form \p OpenRanges and replaced with
1545/// new VarLoc. If \p NewReg is different than default zero value then the
1546/// new location will be register location created by the copy like instruction,
1547/// otherwise it is variable's location on the stack.
1548void VarLocBasedLDV::insertTransferDebugPair(
1549 MachineInstr &MI, OpenRangesSet &OpenRanges, TransferMap &Transfers,
1550 VarLocMap &VarLocIDs, LocIndex OldVarID, TransferKind Kind,
1551 const VarLoc::MachineLoc &OldLoc, Register NewReg) {
1552 const VarLoc &OldVarLoc = VarLocIDs[OldVarID];
1553
1554 auto ProcessVarLoc = [&MI, &OpenRanges, &Transfers, &VarLocIDs](VarLoc &VL) {
1555 LocIndices LocIds = VarLocIDs.insert(VL);
1556
1557 // Close this variable's previous location range.
1558 OpenRanges.erase(VL);
1559
1560 // Record the new location as an open range, and a postponed transfer
1561 // inserting a DBG_VALUE for this location.
1562 OpenRanges.insert(VarLocIDs: LocIds, VL);
1563 assert(!MI.isTerminator() && "Cannot insert DBG_VALUE after terminator");
1564 TransferDebugPair MIP = {.TransferInst: &MI, .LocationID: LocIds.back()};
1565 Transfers.push_back(Elt: MIP);
1566 };
1567
1568 // End all previous ranges of VL.Var.
1569 OpenRanges.erase(VL: VarLocIDs[OldVarID]);
1570 switch (Kind) {
1571 case TransferKind::TransferCopy: {
1572 assert(NewReg &&
1573 "No register supplied when handling a copy of a debug value");
1574 // Create a DBG_VALUE instruction to describe the Var in its new
1575 // register location.
1576 VarLoc VL = VarLoc::CreateCopyLoc(OldVL: OldVarLoc, OldML: OldLoc, NewReg);
1577 ProcessVarLoc(VL);
1578 LLVM_DEBUG({
1579 dbgs() << "Creating VarLoc for register copy:";
1580 VL.dump(TRI, TII);
1581 });
1582 return;
1583 }
1584 case TransferKind::TransferSpill: {
1585 // Create a DBG_VALUE instruction to describe the Var in its spilled
1586 // location.
1587 VarLoc::SpillLoc SpillLocation = extractSpillBaseRegAndOffset(MI);
1588 VarLoc VL = VarLoc::CreateSpillLoc(
1589 OldVL: OldVarLoc, OldML: OldLoc, SpillBase: SpillLocation.SpillBase, SpillOffset: SpillLocation.SpillOffset);
1590 ProcessVarLoc(VL);
1591 LLVM_DEBUG({
1592 dbgs() << "Creating VarLoc for spill:";
1593 VL.dump(TRI, TII);
1594 });
1595 return;
1596 }
1597 case TransferKind::TransferRestore: {
1598 assert(NewReg &&
1599 "No register supplied when handling a restore of a debug value");
1600 // DebugInstr refers to the pre-spill location, therefore we can reuse
1601 // its expression.
1602 VarLoc VL = VarLoc::CreateCopyLoc(OldVL: OldVarLoc, OldML: OldLoc, NewReg);
1603 ProcessVarLoc(VL);
1604 LLVM_DEBUG({
1605 dbgs() << "Creating VarLoc for restore:";
1606 VL.dump(TRI, TII);
1607 });
1608 return;
1609 }
1610 }
1611 llvm_unreachable("Invalid transfer kind");
1612}
1613
1614/// A definition of a register may mark the end of a range.
1615void VarLocBasedLDV::transferRegisterDef(MachineInstr &MI,
1616 OpenRangesSet &OpenRanges,
1617 VarLocMap &VarLocIDs,
1618 InstToEntryLocMap &EntryValTransfers,
1619 RegDefToInstMap &RegSetInstrs) {
1620
1621 // Meta Instructions do not affect the debug liveness of any register they
1622 // define.
1623 if (MI.isMetaInstruction())
1624 return;
1625
1626 MachineFunction *MF = MI.getMF();
1627 const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
1628 Register SP = TLI->getStackPointerRegisterToSaveRestore();
1629
1630 // Find the regs killed by MI, and find regmasks of preserved regs.
1631 SmallVector<Register, 32> DeadRegs;
1632 SmallVector<const uint32_t *, 4> RegMasks;
1633 for (const MachineOperand &MO : MI.operands()) {
1634 // Determine whether the operand is a register def.
1635 if (MO.isReg() && MO.isDef() && MO.getReg() && MO.getReg().isPhysical() &&
1636 !(MI.isCall() && MO.getReg() == SP)) {
1637 // Remove ranges of all aliased registers.
1638 for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
1639 DeadRegs.push_back(Elt: (*RAI).id());
1640 RegSetInstrs.erase(Val: MO.getReg());
1641 RegSetInstrs.insert(KV: {MO.getReg(), &MI});
1642 } else if (MO.isRegMask()) {
1643 RegMasks.push_back(Elt: MO.getRegMask());
1644 }
1645 }
1646
1647 // Erase VarLocs which reside in one of the dead registers. For performance
1648 // reasons, it's critical to not iterate over the full set of open VarLocs.
1649 // Iterate over the set of dying/used regs instead.
1650 if (!RegMasks.empty()) {
1651 SmallVector<Register, 32> UsedRegs;
1652 getUsedRegs(CollectFrom: OpenRanges.getVarLocs(), UsedRegs);
1653 for (Register Reg : UsedRegs) {
1654 // Remove ranges of all clobbered registers. Register masks don't usually
1655 // list SP as preserved. Assume that call instructions never clobber SP,
1656 // because some backends (e.g., AArch64) never list SP in the regmask.
1657 // While the debug info may be off for an instruction or two around
1658 // callee-cleanup calls, transferring the DEBUG_VALUE across the call is
1659 // still a better user experience.
1660 if (Reg == SP)
1661 continue;
1662 bool AnyRegMaskKillsReg =
1663 any_of(Range&: RegMasks, P: [Reg](const uint32_t *RegMask) {
1664 return MachineOperand::clobbersPhysReg(RegMask, PhysReg: Reg);
1665 });
1666 if (AnyRegMaskKillsReg)
1667 DeadRegs.push_back(Elt: Reg);
1668 if (AnyRegMaskKillsReg) {
1669 RegSetInstrs.erase(Val: Reg);
1670 RegSetInstrs.insert(KV: {Reg, &MI});
1671 }
1672 }
1673 }
1674
1675 if (DeadRegs.empty())
1676 return;
1677
1678 VarLocsInRange KillSet;
1679 collectIDsForRegs(Collected&: KillSet, Regs: DeadRegs, CollectFrom: OpenRanges.getVarLocs(), VarLocIDs);
1680 OpenRanges.erase(KillSet, VarLocIDs, Location: LocIndex::kUniversalLocation);
1681
1682 if (ShouldEmitDebugEntryValues)
1683 emitEntryValues(MI, OpenRanges, VarLocIDs, EntryValTransfers, KillSet);
1684}
1685
1686void VarLocBasedLDV::transferWasmDef(MachineInstr &MI,
1687 OpenRangesSet &OpenRanges,
1688 VarLocMap &VarLocIDs) {
1689 // If this is not a Wasm local.set or local.tee, which sets local values,
1690 // return.
1691 int Index;
1692 int64_t Offset;
1693 if (!TII->isExplicitTargetIndexDef(MI, Index, Offset))
1694 return;
1695
1696 // Find the target indices killed by MI, and delete those variable locations
1697 // from the open range.
1698 VarLocsInRange KillSet;
1699 VarLoc::WasmLoc Loc{.Index: Index, .Offset: Offset};
1700 for (uint64_t ID : OpenRanges.getWasmVarLocs()) {
1701 LocIndex Idx = LocIndex::fromRawInteger(ID);
1702 const VarLoc &VL = VarLocIDs[Idx];
1703 assert(VL.containsWasmLocs() && "Broken VarLocSet?");
1704 if (VL.usesWasmLoc(WasmLocation: Loc))
1705 KillSet.insert(V: ID);
1706 }
1707 OpenRanges.erase(KillSet, VarLocIDs, Location: LocIndex::kWasmLocation);
1708}
1709
1710bool VarLocBasedLDV::isSpillInstruction(const MachineInstr &MI,
1711 MachineFunction *MF) {
1712 // TODO: Handle multiple stores folded into one.
1713 if (!MI.hasOneMemOperand())
1714 return false;
1715
1716 if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII))
1717 return false; // This is not a spill instruction, since no valid size was
1718 // returned from either function.
1719
1720 return true;
1721}
1722
1723bool VarLocBasedLDV::isLocationSpill(const MachineInstr &MI,
1724 MachineFunction *MF, Register &Reg) {
1725 if (!isSpillInstruction(MI, MF))
1726 return false;
1727
1728 auto isKilledReg = [&](const MachineOperand MO, Register &Reg) {
1729 if (!MO.isReg() || !MO.isUse()) {
1730 Reg = 0;
1731 return false;
1732 }
1733 Reg = MO.getReg();
1734 return MO.isKill();
1735 };
1736
1737 for (const MachineOperand &MO : MI.operands()) {
1738 // In a spill instruction generated by the InlineSpiller the spilled
1739 // register has its kill flag set.
1740 if (isKilledReg(MO, Reg))
1741 return true;
1742 if (Reg != 0) {
1743 // Check whether next instruction kills the spilled register.
1744 // FIXME: Current solution does not cover search for killed register in
1745 // bundles and instructions further down the chain.
1746 auto NextI = std::next(x: MI.getIterator());
1747 // Skip next instruction that points to basic block end iterator.
1748 if (MI.getParent()->end() == NextI)
1749 continue;
1750 Register RegNext;
1751 for (const MachineOperand &MONext : NextI->operands()) {
1752 // Return true if we came across the register from the
1753 // previous spill instruction that is killed in NextI.
1754 if (isKilledReg(MONext, RegNext) && RegNext == Reg)
1755 return true;
1756 }
1757 }
1758 }
1759 // Return false if we didn't find spilled register.
1760 return false;
1761}
1762
1763std::optional<VarLocBasedLDV::VarLoc::SpillLoc>
1764VarLocBasedLDV::isRestoreInstruction(const MachineInstr &MI,
1765 MachineFunction *MF, Register &Reg) {
1766 if (!MI.hasOneMemOperand())
1767 return std::nullopt;
1768
1769 // FIXME: Handle folded restore instructions with more than one memory
1770 // operand.
1771 if (MI.getRestoreSize(TII)) {
1772 Reg = MI.getOperand(i: 0).getReg();
1773 return extractSpillBaseRegAndOffset(MI);
1774 }
1775 return std::nullopt;
1776}
1777
1778/// A spilled register may indicate that we have to end the current range of
1779/// a variable and create a new one for the spill location.
1780/// A restored register may indicate the reverse situation.
1781/// We don't want to insert any instructions in process(), so we just create
1782/// the DBG_VALUE without inserting it and keep track of it in \p Transfers.
1783/// It will be inserted into the BB when we're done iterating over the
1784/// instructions.
1785void VarLocBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI,
1786 OpenRangesSet &OpenRanges,
1787 VarLocMap &VarLocIDs,
1788 TransferMap &Transfers) {
1789 MachineFunction *MF = MI.getMF();
1790 TransferKind TKind;
1791 Register Reg;
1792 std::optional<VarLoc::SpillLoc> Loc;
1793
1794 LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump(););
1795
1796 // First, if there are any DBG_VALUEs pointing at a spill slot that is
1797 // written to, then close the variable location. The value in memory
1798 // will have changed.
1799 VarLocsInRange KillSet;
1800 if (isSpillInstruction(MI, MF)) {
1801 Loc = extractSpillBaseRegAndOffset(MI);
1802 for (uint64_t ID : OpenRanges.getSpillVarLocs()) {
1803 LocIndex Idx = LocIndex::fromRawInteger(ID);
1804 const VarLoc &VL = VarLocIDs[Idx];
1805 assert(VL.containsSpillLocs() && "Broken VarLocSet?");
1806 if (VL.usesSpillLoc(SpillLocation: *Loc)) {
1807 // This location is overwritten by the current instruction -- terminate
1808 // the open range, and insert an explicit DBG_VALUE $noreg.
1809 //
1810 // Doing this at a later stage would require re-interpreting all
1811 // DBG_VALUes and DIExpressions to identify whether they point at
1812 // memory, and then analysing all memory writes to see if they
1813 // overwrite that memory, which is expensive.
1814 //
1815 // At this stage, we already know which DBG_VALUEs are for spills and
1816 // where they are located; it's best to fix handle overwrites now.
1817 KillSet.insert(V: ID);
1818 unsigned SpillLocIdx = VL.getSpillLocIdx(SpillLocation: *Loc);
1819 VarLoc::MachineLoc OldLoc = VL.Locs[SpillLocIdx];
1820 VarLoc UndefVL = VarLoc::CreateCopyLoc(OldVL: VL, OldML: OldLoc, NewReg: 0);
1821 LocIndices UndefLocIDs = VarLocIDs.insert(VL: UndefVL);
1822 Transfers.push_back(Elt: {.TransferInst: &MI, .LocationID: UndefLocIDs.back()});
1823 }
1824 }
1825 OpenRanges.erase(KillSet, VarLocIDs, Location: LocIndex::kSpillLocation);
1826 }
1827
1828 // Try to recognise spill and restore instructions that may create a new
1829 // variable location.
1830 if (isLocationSpill(MI, MF, Reg)) {
1831 TKind = TransferKind::TransferSpill;
1832 LLVM_DEBUG(dbgs() << "Recognized as spill: "; MI.dump(););
1833 LLVM_DEBUG(dbgs() << "Register: " << Reg.id() << " " << printReg(Reg, TRI)
1834 << "\n");
1835 } else {
1836 if (!(Loc = isRestoreInstruction(MI, MF, Reg)))
1837 return;
1838 TKind = TransferKind::TransferRestore;
1839 LLVM_DEBUG(dbgs() << "Recognized as restore: "; MI.dump(););
1840 LLVM_DEBUG(dbgs() << "Register: " << Reg.id() << " " << printReg(Reg, TRI)
1841 << "\n");
1842 }
1843 // Check if the register or spill location is the location of a debug value.
1844 auto TransferCandidates = OpenRanges.getEmptyVarLocRange();
1845 if (TKind == TransferKind::TransferSpill)
1846 TransferCandidates = OpenRanges.getRegisterVarLocs(Reg);
1847 else if (TKind == TransferKind::TransferRestore)
1848 TransferCandidates = OpenRanges.getSpillVarLocs();
1849 for (uint64_t ID : TransferCandidates) {
1850 LocIndex Idx = LocIndex::fromRawInteger(ID);
1851 const VarLoc &VL = VarLocIDs[Idx];
1852 unsigned LocIdx;
1853 if (TKind == TransferKind::TransferSpill) {
1854 assert(VL.usesReg(Reg) && "Broken VarLocSet?");
1855 LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '('
1856 << VL.Var.getVariable()->getName() << ")\n");
1857 LocIdx = VL.getRegIdx(Reg);
1858 } else {
1859 assert(TKind == TransferKind::TransferRestore && VL.containsSpillLocs() &&
1860 "Broken VarLocSet?");
1861 if (!VL.usesSpillLoc(SpillLocation: *Loc))
1862 // The spill location is not the location of a debug value.
1863 continue;
1864 LLVM_DEBUG(dbgs() << "Restoring Register " << printReg(Reg, TRI) << '('
1865 << VL.Var.getVariable()->getName() << ")\n");
1866 LocIdx = VL.getSpillLocIdx(SpillLocation: *Loc);
1867 }
1868 VarLoc::MachineLoc MLoc = VL.Locs[LocIdx];
1869 insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, OldVarID: Idx, Kind: TKind,
1870 OldLoc: MLoc, NewReg: Reg);
1871 // FIXME: A comment should explain why it's correct to return early here,
1872 // if that is in fact correct.
1873 return;
1874 }
1875}
1876
1877/// If \p MI is a register copy instruction, that copies a previously tracked
1878/// value from one register to another register that is callee saved, we
1879/// create new DBG_VALUE instruction described with copy destination register.
1880void VarLocBasedLDV::transferRegisterCopy(MachineInstr &MI,
1881 OpenRangesSet &OpenRanges,
1882 VarLocMap &VarLocIDs,
1883 TransferMap &Transfers) {
1884 auto DestSrc = TII->isCopyLikeInstr(MI);
1885 if (!DestSrc)
1886 return;
1887
1888 const MachineOperand *DestRegOp = DestSrc->Destination;
1889 const MachineOperand *SrcRegOp = DestSrc->Source;
1890
1891 if (!DestRegOp->isDef())
1892 return;
1893
1894 auto isCalleeSavedReg = [&](Register Reg) {
1895 for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
1896 if (CalleeSavedRegs.test(Idx: (*RAI).id()))
1897 return true;
1898 return false;
1899 };
1900
1901 Register SrcReg = SrcRegOp->getReg();
1902 Register DestReg = DestRegOp->getReg();
1903
1904 // We want to recognize instructions where destination register is callee
1905 // saved register. If register that could be clobbered by the call is
1906 // included, there would be a great chance that it is going to be clobbered
1907 // soon. It is more likely that previous register location, which is callee
1908 // saved, is going to stay unclobbered longer, even if it is killed.
1909 if (!isCalleeSavedReg(DestReg))
1910 return;
1911
1912 // Remember an entry value movement. If we encounter a new debug value of
1913 // a parameter describing only a moving of the value around, rather then
1914 // modifying it, we are still able to use the entry value if needed.
1915 if (isRegOtherThanSPAndFP(Op: *DestRegOp, MI, TRI)) {
1916 for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) {
1917 LocIndex Idx = LocIndex::fromRawInteger(ID);
1918 const VarLoc &VL = VarLocIDs[Idx];
1919 if (VL.isEntryValueBackupReg(Reg: SrcReg)) {
1920 LLVM_DEBUG(dbgs() << "Copy of the entry value: "; MI.dump(););
1921 VarLoc EntryValLocCopyBackup =
1922 VarLoc::CreateEntryCopyBackupLoc(MI: VL.MI, EntryExpr: VL.Expr, NewReg: DestReg);
1923 // Stop tracking the original entry value.
1924 OpenRanges.erase(VL);
1925
1926 // Start tracking the entry value copy.
1927 LocIndices EntryValCopyLocIDs = VarLocIDs.insert(VL: EntryValLocCopyBackup);
1928 OpenRanges.insert(VarLocIDs: EntryValCopyLocIDs, VL: EntryValLocCopyBackup);
1929 break;
1930 }
1931 }
1932 }
1933
1934 if (!SrcRegOp->isKill())
1935 return;
1936
1937 for (uint64_t ID : OpenRanges.getRegisterVarLocs(Reg: SrcReg)) {
1938 LocIndex Idx = LocIndex::fromRawInteger(ID);
1939 assert(VarLocIDs[Idx].usesReg(SrcReg) && "Broken VarLocSet?");
1940 VarLoc::MachineLocValue Loc;
1941 Loc.RegNo = SrcReg;
1942 VarLoc::MachineLoc MLoc{.Kind: VarLoc::MachineLocKind::RegisterKind, .Value: Loc};
1943 insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, OldVarID: Idx,
1944 Kind: TransferKind::TransferCopy, OldLoc: MLoc, NewReg: DestReg);
1945 // FIXME: A comment should explain why it's correct to return early here,
1946 // if that is in fact correct.
1947 return;
1948 }
1949}
1950
1951/// Terminate all open ranges at the end of the current basic block.
1952bool VarLocBasedLDV::transferTerminator(MachineBasicBlock *CurMBB,
1953 OpenRangesSet &OpenRanges,
1954 VarLocInMBB &OutLocs,
1955 const VarLocMap &VarLocIDs) {
1956 bool Changed = false;
1957 LLVM_DEBUG({
1958 VarVec VarLocs;
1959 OpenRanges.getUniqueVarLocs(VarLocs, VarLocIDs);
1960 for (VarLoc &VL : VarLocs) {
1961 // Copy OpenRanges to OutLocs, if not already present.
1962 dbgs() << "Add to OutLocs in MBB #" << CurMBB->getNumber() << ": ";
1963 VL.dump(TRI, TII);
1964 }
1965 });
1966 VarLocSet &VLS = getVarLocsInMBB(MBB: CurMBB, Locs&: OutLocs);
1967 Changed = VLS != OpenRanges.getVarLocs();
1968 // New OutLocs set may be different due to spill, restore or register
1969 // copy instruction processing.
1970 if (Changed)
1971 VLS = OpenRanges.getVarLocs();
1972 OpenRanges.clear();
1973 return Changed;
1974}
1975
1976/// Accumulate a mapping between each DILocalVariable fragment and other
1977/// fragments of that DILocalVariable which overlap. This reduces work during
1978/// the data-flow stage from "Find any overlapping fragments" to "Check if the
1979/// known-to-overlap fragments are present".
1980/// \param MI A previously unprocessed DEBUG_VALUE instruction to analyze for
1981/// fragment usage.
1982/// \param SeenFragments Map from DILocalVariable to all fragments of that
1983/// Variable which are known to exist.
1984/// \param OverlappingFragments The overlap map being constructed, from one
1985/// Var/Fragment pair to a vector of fragments known to overlap.
1986void VarLocBasedLDV::accumulateFragmentMap(MachineInstr &MI,
1987 VarToFragments &SeenFragments,
1988 OverlapMap &OverlappingFragments) {
1989 DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(),
1990 MI.getDebugLoc()->getInlinedAt());
1991 FragmentInfo ThisFragment = MIVar.getFragmentOrDefault();
1992
1993 // If this is the first sighting of this variable, then we are guaranteed
1994 // there are currently no overlapping fragments either. Initialize the set
1995 // of seen fragments, record no overlaps for the current one, and return.
1996 auto [SeenIt, Inserted] = SeenFragments.try_emplace(Key: MIVar.getVariable());
1997 if (Inserted) {
1998 SeenIt->second.insert(V: ThisFragment);
1999
2000 OverlappingFragments.insert(KV: {{MIVar.getVariable(), ThisFragment}, {}});
2001 return;
2002 }
2003
2004 // If this particular Variable/Fragment pair already exists in the overlap
2005 // map, it has already been accounted for.
2006 auto IsInOLapMap =
2007 OverlappingFragments.insert(KV: {{MIVar.getVariable(), ThisFragment}, {}});
2008 if (!IsInOLapMap.second)
2009 return;
2010
2011 auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;
2012 auto &AllSeenFragments = SeenIt->second;
2013
2014 // Otherwise, examine all other seen fragments for this variable, with "this"
2015 // fragment being a previously unseen fragment. Record any pair of
2016 // overlapping fragments.
2017 for (const auto &ASeenFragment : AllSeenFragments) {
2018 // Does this previously seen fragment overlap?
2019 if (DIExpression::fragmentsOverlap(A: ThisFragment, B: ASeenFragment)) {
2020 // Yes: Mark the current fragment as being overlapped.
2021 ThisFragmentsOverlaps.push_back(Elt: ASeenFragment);
2022 // Mark the previously seen fragment as being overlapped by the current
2023 // one.
2024 auto ASeenFragmentsOverlaps =
2025 OverlappingFragments.find(Val: {MIVar.getVariable(), ASeenFragment});
2026 assert(ASeenFragmentsOverlaps != OverlappingFragments.end() &&
2027 "Previously seen var fragment has no vector of overlaps");
2028 ASeenFragmentsOverlaps->second.push_back(Elt: ThisFragment);
2029 }
2030 }
2031
2032 AllSeenFragments.insert(V: ThisFragment);
2033}
2034
2035/// This routine creates OpenRanges.
2036void VarLocBasedLDV::process(MachineInstr &MI, OpenRangesSet &OpenRanges,
2037 VarLocMap &VarLocIDs, TransferMap &Transfers,
2038 InstToEntryLocMap &EntryValTransfers,
2039 RegDefToInstMap &RegSetInstrs) {
2040 if (!MI.isDebugInstr())
2041 LastNonDbgMI = &MI;
2042 transferDebugValue(MI, OpenRanges, VarLocIDs, EntryValTransfers,
2043 RegSetInstrs);
2044 transferRegisterDef(MI, OpenRanges, VarLocIDs, EntryValTransfers,
2045 RegSetInstrs);
2046 transferWasmDef(MI, OpenRanges, VarLocIDs);
2047 transferRegisterCopy(MI, OpenRanges, VarLocIDs, Transfers);
2048 transferSpillOrRestoreInst(MI, OpenRanges, VarLocIDs, Transfers);
2049}
2050
2051/// This routine joins the analysis results of all incoming edges in @MBB by
2052/// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
2053/// source variable in all the predecessors of @MBB reside in the same location.
2054bool VarLocBasedLDV::join(
2055 MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
2056 const VarLocMap &VarLocIDs,
2057 SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
2058 SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks) {
2059 LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
2060
2061 VarLocSet InLocsT(Alloc); // Temporary incoming locations.
2062
2063 // For all predecessors of this MBB, find the set of VarLocs that
2064 // can be joined.
2065 int NumVisited = 0;
2066 for (auto *p : MBB.predecessors()) {
2067 // Ignore backedges if we have not visited the predecessor yet. As the
2068 // predecessor hasn't yet had locations propagated into it, most locations
2069 // will not yet be valid, so treat them as all being uninitialized and
2070 // potentially valid. If a location guessed to be correct here is
2071 // invalidated later, we will remove it when we revisit this block.
2072 if (!Visited.count(Ptr: p)) {
2073 LLVM_DEBUG(dbgs() << " ignoring unvisited pred MBB: " << p->getNumber()
2074 << "\n");
2075 continue;
2076 }
2077 auto OL = OutLocs.find(Val: p);
2078 // Join is null in case of empty OutLocs from any of the pred.
2079 if (OL == OutLocs.end())
2080 return false;
2081
2082 // Just copy over the Out locs to incoming locs for the first visited
2083 // predecessor, and for all other predecessors join the Out locs.
2084 VarLocSet &OutLocVLS = *OL->second;
2085 if (!NumVisited)
2086 InLocsT = OutLocVLS;
2087 else
2088 InLocsT &= OutLocVLS;
2089
2090 LLVM_DEBUG({
2091 if (!InLocsT.empty()) {
2092 VarVec VarLocs;
2093 collectAllVarLocs(VarLocs, InLocsT, VarLocIDs);
2094 for (const VarLoc &VL : VarLocs)
2095 dbgs() << " gathered candidate incoming var: "
2096 << VL.Var.getVariable()->getName() << "\n";
2097 }
2098 });
2099
2100 NumVisited++;
2101 }
2102
2103 // Filter out DBG_VALUES that are out of scope.
2104 VarLocSet KillSet(Alloc);
2105 bool IsArtificial = ArtificialBlocks.count(Ptr: &MBB);
2106 if (!IsArtificial) {
2107 for (uint64_t ID : InLocsT) {
2108 LocIndex Idx = LocIndex::fromRawInteger(ID);
2109 if (!VarLocIDs[Idx].dominates(LS, MBB)) {
2110 KillSet.set(ID);
2111 LLVM_DEBUG({
2112 auto Name = VarLocIDs[Idx].Var.getVariable()->getName();
2113 dbgs() << " killing " << Name << ", it doesn't dominate MBB\n";
2114 });
2115 }
2116 }
2117 }
2118 InLocsT.intersectWithComplement(Other: KillSet);
2119
2120 // As we are processing blocks in reverse post-order we
2121 // should have processed at least one predecessor, unless it
2122 // is the entry block which has no predecessor.
2123 assert((NumVisited || MBB.pred_empty()) &&
2124 "Should have processed at least one predecessor");
2125
2126 VarLocSet &ILS = getVarLocsInMBB(MBB: &MBB, Locs&: InLocs);
2127 bool Changed = false;
2128 if (ILS != InLocsT) {
2129 ILS = InLocsT;
2130 Changed = true;
2131 }
2132
2133 return Changed;
2134}
2135
2136void VarLocBasedLDV::flushPendingLocs(VarLocInMBB &PendingInLocs,
2137 VarLocMap &VarLocIDs) {
2138 // PendingInLocs records all locations propagated into blocks, which have
2139 // not had DBG_VALUE insts created. Go through and create those insts now.
2140 for (auto &Iter : PendingInLocs) {
2141 // Map is keyed on a constant pointer, unwrap it so we can insert insts.
2142 auto &MBB = const_cast<MachineBasicBlock &>(*Iter.first);
2143 VarLocSet &Pending = *Iter.second;
2144
2145 SmallVector<VarLoc, 32> VarLocs;
2146 collectAllVarLocs(Collected&: VarLocs, CollectFrom: Pending, VarLocIDs);
2147
2148 for (VarLoc DiffIt : VarLocs) {
2149 // The ID location is live-in to MBB -- work out what kind of machine
2150 // location it is and create a DBG_VALUE.
2151 if (DiffIt.isEntryBackupLoc())
2152 continue;
2153 MachineInstr *MI = DiffIt.BuildDbgValue(MF&: *MBB.getParent());
2154 MBB.insert(I: MBB.instr_begin(), M: MI);
2155
2156 (void)MI;
2157 LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump(););
2158 }
2159 }
2160}
2161
2162bool VarLocBasedLDV::isEntryValueCandidate(
2163 const MachineInstr &MI, const DefinedRegsSet &DefinedRegs) const {
2164 assert(MI.isDebugValue() && "This must be DBG_VALUE.");
2165
2166 // TODO: Add support for local variables that are expressed in terms of
2167 // parameters entry values.
2168 // TODO: Add support for modified arguments that can be expressed
2169 // by using its entry value.
2170 auto *DIVar = MI.getDebugVariable();
2171 if (!DIVar->isParameter())
2172 return false;
2173
2174 // Do not consider parameters that belong to an inlined function.
2175 if (MI.getDebugLoc()->getInlinedAt())
2176 return false;
2177
2178 // Only consider parameters that are described using registers. Parameters
2179 // that are passed on the stack are not yet supported, so ignore debug
2180 // values that are described by the frame or stack pointer.
2181 if (!isRegOtherThanSPAndFP(Op: MI.getDebugOperand(Index: 0), MI, TRI))
2182 return false;
2183
2184 // If a parameter's value has been propagated from the caller, then the
2185 // parameter's DBG_VALUE may be described using a register defined by some
2186 // instruction in the entry block, in which case we shouldn't create an
2187 // entry value.
2188 if (DefinedRegs.count(V: MI.getDebugOperand(Index: 0).getReg()))
2189 return false;
2190
2191 // TODO: Add support for parameters that have a pre-existing debug expressions
2192 // (e.g. fragments).
2193 // A simple deref expression is equivalent to an indirect debug value.
2194 const DIExpression *Expr = MI.getDebugExpression();
2195 if (Expr->getNumElements() > 0 && !Expr->isDeref())
2196 return false;
2197
2198 return true;
2199}
2200
2201/// Collect all register defines (including aliases) for the given instruction.
2202static void collectRegDefs(const MachineInstr &MI, DefinedRegsSet &Regs,
2203 const TargetRegisterInfo *TRI) {
2204 for (const MachineOperand &MO : MI.all_defs()) {
2205 if (MO.getReg() && MO.getReg().isPhysical()) {
2206 Regs.insert(V: MO.getReg());
2207 for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
2208 Regs.insert(V: *AI);
2209 }
2210 }
2211}
2212
2213/// This routine records the entry values of function parameters. The values
2214/// could be used as backup values. If we loose the track of some unmodified
2215/// parameters, the backup values will be used as a primary locations.
2216void VarLocBasedLDV::recordEntryValue(const MachineInstr &MI,
2217 const DefinedRegsSet &DefinedRegs,
2218 OpenRangesSet &OpenRanges,
2219 VarLocMap &VarLocIDs) {
2220 if (!ShouldEmitDebugEntryValues)
2221 return;
2222
2223 DebugVariable V(MI.getDebugVariable(), MI.getDebugExpression(),
2224 MI.getDebugLoc()->getInlinedAt());
2225
2226 if (!isEntryValueCandidate(MI, DefinedRegs) ||
2227 OpenRanges.getEntryValueBackup(Var: V))
2228 return;
2229
2230 LLVM_DEBUG(dbgs() << "Creating the backup entry location: "; MI.dump(););
2231
2232 // Create the entry value and use it as a backup location until it is
2233 // valid. It is valid until a parameter is not changed.
2234 DIExpression *NewExpr =
2235 DIExpression::prepend(Expr: MI.getDebugExpression(), Flags: DIExpression::EntryValue);
2236 VarLoc EntryValLocAsBackup = VarLoc::CreateEntryBackupLoc(MI, EntryExpr: NewExpr);
2237 LocIndices EntryValLocIDs = VarLocIDs.insert(VL: EntryValLocAsBackup);
2238 OpenRanges.insert(VarLocIDs: EntryValLocIDs, VL: EntryValLocAsBackup);
2239}
2240
2241/// Calculate the liveness information for the given machine function and
2242/// extend ranges across basic blocks.
2243bool VarLocBasedLDV::ExtendRanges(MachineFunction &MF,
2244 MachineDominatorTree *DomTree,
2245 bool ShouldEmitDebugEntryValues,
2246 unsigned InputBBLimit,
2247 unsigned InputDbgValLimit) {
2248 (void)DomTree;
2249 LLVM_DEBUG(dbgs() << "\nDebug Range Extension: " << MF.getName() << "\n");
2250
2251 if (!MF.getFunction().getSubprogram())
2252 // VarLocBaseLDV will already have removed all DBG_VALUEs.
2253 return false;
2254
2255 // Skip functions from NoDebug compilation units.
2256 if (MF.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
2257 DICompileUnit::NoDebug)
2258 return false;
2259
2260 TRI = MF.getSubtarget().getRegisterInfo();
2261 TII = MF.getSubtarget().getInstrInfo();
2262 TFI = MF.getSubtarget().getFrameLowering();
2263 TFI->getCalleeSaves(MF, SavedRegs&: CalleeSavedRegs);
2264 this->ShouldEmitDebugEntryValues = ShouldEmitDebugEntryValues;
2265
2266 LS.scanFunction(MF);
2267
2268 bool Changed = false;
2269 bool OLChanged = false;
2270 bool MBBJoined = false;
2271
2272 VarLocMap VarLocIDs; // Map VarLoc<>unique ID for use in bitvectors.
2273 OverlapMap OverlapFragments; // Map of overlapping variable fragments.
2274 OpenRangesSet OpenRanges(Alloc, OverlapFragments);
2275 // Ranges that are open until end of bb.
2276 VarLocInMBB OutLocs; // Ranges that exist beyond bb.
2277 VarLocInMBB InLocs; // Ranges that are incoming after joining.
2278 TransferMap Transfers; // DBG_VALUEs associated with transfers (such as
2279 // spills, copies and restores).
2280 // Map responsible MI to attached Transfer emitted from Backup Entry Value.
2281 InstToEntryLocMap EntryValTransfers;
2282 // Map a Register to the last MI which clobbered it.
2283 RegDefToInstMap RegSetInstrs;
2284
2285 VarToFragments SeenFragments;
2286
2287 // Blocks which are artificial, i.e. blocks which exclusively contain
2288 // instructions without locations, or with line 0 locations.
2289 SmallPtrSet<const MachineBasicBlock *, 16> ArtificialBlocks;
2290
2291 DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
2292 DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
2293 std::priority_queue<unsigned int, std::vector<unsigned int>,
2294 std::greater<unsigned int>>
2295 Worklist;
2296 std::priority_queue<unsigned int, std::vector<unsigned int>,
2297 std::greater<unsigned int>>
2298 Pending;
2299
2300 // Set of register defines that are seen when traversing the entry block
2301 // looking for debug entry value candidates.
2302 DefinedRegsSet DefinedRegs;
2303
2304 // Only in the case of entry MBB collect DBG_VALUEs representing
2305 // function parameters in order to generate debug entry values for them.
2306 MachineBasicBlock &First_MBB = *(MF.begin());
2307 for (auto &MI : First_MBB) {
2308 collectRegDefs(MI, Regs&: DefinedRegs, TRI);
2309 if (MI.isDebugValue())
2310 recordEntryValue(MI, DefinedRegs, OpenRanges, VarLocIDs);
2311 }
2312
2313 // Initialize per-block structures and scan for fragment overlaps.
2314 for (auto &MBB : MF)
2315 for (auto &MI : MBB)
2316 if (MI.isDebugValue())
2317 accumulateFragmentMap(MI, SeenFragments, OverlappingFragments&: OverlapFragments);
2318
2319 auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
2320 if (const DebugLoc &DL = MI.getDebugLoc())
2321 return DL.getLine() != 0;
2322 return false;
2323 };
2324 for (auto &MBB : MF)
2325 if (none_of(Range: MBB.instrs(), P: hasNonArtificialLocation))
2326 ArtificialBlocks.insert(Ptr: &MBB);
2327
2328 LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
2329 "OutLocs after initialization", dbgs()));
2330
2331 ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
2332 unsigned int RPONumber = 0;
2333 for (MachineBasicBlock *MBB : RPOT) {
2334 OrderToBB[RPONumber] = MBB;
2335 BBToOrder[MBB] = RPONumber;
2336 Worklist.push(x: RPONumber);
2337 ++RPONumber;
2338 }
2339
2340 if (RPONumber > InputBBLimit) {
2341 unsigned NumInputDbgValues = 0;
2342 for (auto &MBB : MF)
2343 for (auto &MI : MBB)
2344 if (MI.isDebugValue())
2345 ++NumInputDbgValues;
2346 if (NumInputDbgValues > InputDbgValLimit) {
2347 LLVM_DEBUG(dbgs() << "Disabling VarLocBasedLDV: " << MF.getName()
2348 << " has " << RPONumber << " basic blocks and "
2349 << NumInputDbgValues
2350 << " input DBG_VALUEs, exceeding limits.\n");
2351 return false;
2352 }
2353 }
2354
2355 // This is a standard "union of predecessor outs" dataflow problem.
2356 // To solve it, we perform join() and process() using the two worklist method
2357 // until the ranges converge.
2358 // Ranges have converged when both worklists are empty.
2359 SmallPtrSet<const MachineBasicBlock *, 16> Visited;
2360 while (!Worklist.empty() || !Pending.empty()) {
2361 // We track what is on the pending worklist to avoid inserting the same
2362 // thing twice. We could avoid this with a custom priority queue, but this
2363 // is probably not worth it.
2364 SmallPtrSet<MachineBasicBlock *, 16> OnPending;
2365 LLVM_DEBUG(dbgs() << "Processing Worklist\n");
2366 while (!Worklist.empty()) {
2367 MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
2368 Worklist.pop();
2369 MBBJoined = join(MBB&: *MBB, OutLocs, InLocs, VarLocIDs, Visited,
2370 ArtificialBlocks);
2371 MBBJoined |= Visited.insert(Ptr: MBB).second;
2372 if (MBBJoined) {
2373 MBBJoined = false;
2374 Changed = true;
2375 // Now that we have started to extend ranges across BBs we need to
2376 // examine spill, copy and restore instructions to see whether they
2377 // operate with registers that correspond to user variables.
2378 // First load any pending inlocs.
2379 OpenRanges.insertFromLocSet(ToLoad: getVarLocsInMBB(MBB, Locs&: InLocs), Map: VarLocIDs);
2380 LastNonDbgMI = nullptr;
2381 RegSetInstrs.clear();
2382 // Iterate through instructions within each packet to handle VLIW
2383 // bundles correctly; this keeps DBG_VALUE placement valid on
2384 // packet-based targets.
2385 for (auto I = MBB->instr_begin(), E = MBB->instr_end(); I != E;) {
2386 auto BStart = llvm::getBundleStart(I);
2387 auto BEnd = llvm::getBundleEnd(I);
2388 bool PacketHasTerminator = false;
2389 for (auto BI = BStart; BI != BEnd; ++BI) {
2390 if (BI->isTerminator()) {
2391 PacketHasTerminator = true;
2392 break;
2393 }
2394 }
2395 if (PacketHasTerminator) {
2396 // FIXME: This drops debug info for spills in terminator bundles;
2397 // DBG_VALUE instructions can't be inserted after the bundle.
2398 // It may be possible to insert the DBG_VALUE elsewhere.
2399 I = BEnd;
2400 continue;
2401 }
2402 auto FirstOp = (BStart->isBundle()) ? std::next(x: BStart) : BStart;
2403 for (auto BI = FirstOp; BI != BEnd; ++BI) {
2404 if (BI->isTerminator())
2405 continue;
2406 process(MI&: *BI, OpenRanges, VarLocIDs, Transfers, EntryValTransfers,
2407 RegSetInstrs);
2408 }
2409 I = BEnd;
2410 }
2411 OLChanged |= transferTerminator(CurMBB: MBB, OpenRanges, OutLocs, VarLocIDs);
2412
2413 LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
2414 "OutLocs after propagating", dbgs()));
2415 LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
2416 "InLocs after propagating", dbgs()));
2417
2418 if (OLChanged) {
2419 OLChanged = false;
2420 for (auto *s : MBB->successors())
2421 if (OnPending.insert(Ptr: s).second) {
2422 Pending.push(x: BBToOrder[s]);
2423 }
2424 }
2425 }
2426 }
2427 Worklist.swap(pq&: Pending);
2428 // At this point, pending must be empty, since it was just the empty
2429 // worklist
2430 assert(Pending.empty() && "Pending should be empty");
2431 }
2432
2433 // Add any DBG_VALUE instructions created by location transfers.
2434 for (auto &TR : Transfers) {
2435 assert(!TR.TransferInst->isTerminator() &&
2436 "Cannot insert DBG_VALUE after terminator");
2437 MachineBasicBlock *MBB = TR.TransferInst->getParent();
2438 const VarLoc &VL = VarLocIDs[TR.LocationID];
2439 MachineInstr *MI = VL.BuildDbgValue(MF);
2440 MBB->insertAfterBundle(I: TR.TransferInst->getIterator(), MI);
2441 }
2442 Transfers.clear();
2443
2444 // Add DBG_VALUEs created using Backup Entry Value location.
2445 for (auto &TR : EntryValTransfers) {
2446 MachineInstr *TRInst = const_cast<MachineInstr *>(TR.first);
2447 assert(!TRInst->isTerminator() &&
2448 "Cannot insert DBG_VALUE after terminator");
2449 MachineBasicBlock *MBB = TRInst->getParent();
2450 const VarLoc &VL = VarLocIDs[TR.second];
2451 MachineInstr *MI = VL.BuildDbgValue(MF);
2452 MBB->insertAfterBundle(I: TRInst->getIterator(), MI);
2453 }
2454 EntryValTransfers.clear();
2455
2456 // Deferred inlocs will not have had any DBG_VALUE insts created; do
2457 // that now.
2458 flushPendingLocs(PendingInLocs&: InLocs, VarLocIDs);
2459
2460 LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs()));
2461 LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs()));
2462 return Changed;
2463}
2464
2465LDVImpl *
2466llvm::makeVarLocBasedLiveDebugValues()
2467{
2468 return new VarLocBasedLDV();
2469}
2470