1//===- InstrRefBasedImpl.cpp - Tracking Debug Value MIs -------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8/// \file InstrRefBasedImpl.cpp
9///
10/// This is a separate implementation of LiveDebugValues, see
11/// LiveDebugValues.cpp and VarLocBasedImpl.cpp for more information.
12///
13/// This pass propagates variable locations between basic blocks, resolving
14/// control flow conflicts between them. The problem is SSA construction, where
15/// each debug instruction assigns the *value* that a variable has, and every
16/// instruction where the variable is in scope uses that variable. The resulting
17/// map of instruction-to-value is then translated into a register (or spill)
18/// location for each variable over each instruction.
19///
20/// The primary difference from normal SSA construction is that we cannot
21/// _create_ PHI values that contain variable values. CodeGen has already
22/// completed, and we can't alter it just to make debug-info complete. Thus:
23/// we can identify function positions where we would like a PHI value for a
24/// variable, but must search the MachineFunction to see whether such a PHI is
25/// available. If no such PHI exists, the variable location must be dropped.
26///
27/// To achieve this, we perform two kinds of analysis. First, we identify
28/// every value defined by every instruction (ignoring those that only move
29/// another value), then re-compute an SSA-form representation of the
30/// MachineFunction, using value propagation to eliminate any un-necessary
31/// PHI values. This gives us a map of every value computed in the function,
32/// and its location within the register file / stack.
33///
34/// Secondly, for each variable we perform the same analysis, where each debug
35/// instruction is considered a def, and every instruction where the variable
36/// is in lexical scope as a use. Value propagation is used again to eliminate
37/// any un-necessary PHIs. This gives us a map of each variable to the value
38/// it should have in a block.
39///
40/// Once both are complete, we have two maps for each block:
41/// * Variables to the values they should have,
42/// * Values to the register / spill slot they are located in.
43/// After which we can marry-up variable values with a location, and emit
44/// DBG_VALUE instructions specifying those locations. Variable locations may
45/// be dropped in this process due to the desired variable value not being
46/// resident in any machine location, or because there is no PHI value in any
47/// location that accurately represents the desired value. The building of
48/// location lists for each block is left to DbgEntityHistoryCalculator.
49///
50/// This pass is kept efficient because the size of the first SSA problem
51/// is proportional to the working-set size of the function, which the compiler
52/// tries to keep small. (It's also proportional to the number of blocks).
53/// Additionally, we repeatedly perform the second SSA problem analysis with
54/// only the variables and blocks in a single lexical scope, exploiting their
55/// locality.
56///
57/// ### Terminology
58///
59/// A machine location is a register or spill slot, a value is something that's
60/// defined by an instruction or PHI node, while a variable value is the value
61/// assigned to a variable. A variable location is a machine location, that must
62/// contain the appropriate variable value. A value that is a PHI node is
63/// occasionally called an mphi.
64///
65/// The first SSA problem is the "machine value location" problem,
66/// because we're determining which machine locations contain which values.
67/// The "locations" are constant: what's unknown is what value they contain.
68///
69/// The second SSA problem (the one for variables) is the "variable value
70/// problem", because it's determining what values a variable has, rather than
71/// what location those values are placed in.
72///
73/// TODO:
74/// Overlapping fragments
75/// Entry values
76/// Add back DEBUG statements for debugging this
77/// Collect statistics
78///
79//===----------------------------------------------------------------------===//
80
81#include "llvm/ADT/DenseMap.h"
82#include "llvm/ADT/PostOrderIterator.h"
83#include "llvm/ADT/STLExtras.h"
84#include "llvm/ADT/SmallPtrSet.h"
85#include "llvm/ADT/SmallSet.h"
86#include "llvm/ADT/SmallVector.h"
87#include "llvm/BinaryFormat/Dwarf.h"
88#include "llvm/CodeGen/LexicalScopes.h"
89#include "llvm/CodeGen/MachineBasicBlock.h"
90#include "llvm/CodeGen/MachineDominators.h"
91#include "llvm/CodeGen/MachineFrameInfo.h"
92#include "llvm/CodeGen/MachineFunction.h"
93#include "llvm/CodeGen/MachineInstr.h"
94#include "llvm/CodeGen/MachineInstrBuilder.h"
95#include "llvm/CodeGen/MachineInstrBundle.h"
96#include "llvm/CodeGen/MachineMemOperand.h"
97#include "llvm/CodeGen/MachineOperand.h"
98#include "llvm/CodeGen/PseudoSourceValue.h"
99#include "llvm/CodeGen/TargetFrameLowering.h"
100#include "llvm/CodeGen/TargetInstrInfo.h"
101#include "llvm/CodeGen/TargetLowering.h"
102#include "llvm/CodeGen/TargetRegisterInfo.h"
103#include "llvm/CodeGen/TargetSubtargetInfo.h"
104#include "llvm/Config/llvm-config.h"
105#include "llvm/IR/DebugInfoMetadata.h"
106#include "llvm/IR/DebugLoc.h"
107#include "llvm/IR/Function.h"
108#include "llvm/MC/MCRegisterInfo.h"
109#include "llvm/Support/Casting.h"
110#include "llvm/Support/Compiler.h"
111#include "llvm/Support/Debug.h"
112#include "llvm/Support/GenericIteratedDominanceFrontier.h"
113#include "llvm/Support/TypeSize.h"
114#include "llvm/Support/raw_ostream.h"
115#include "llvm/Target/TargetMachine.h"
116#include "llvm/Transforms/Utils/SSAUpdaterImpl.h"
117#include <algorithm>
118#include <cassert>
119#include <climits>
120#include <cstdint>
121#include <functional>
122#include <queue>
123#include <tuple>
124#include <utility>
125#include <vector>
126
127#include "InstrRefBasedImpl.h"
128#include "LiveDebugValues.h"
129#include <optional>
130
131using namespace llvm;
132using namespace LiveDebugValues;
133
134// SSAUpdaterImple sets DEBUG_TYPE, change it.
135#undef DEBUG_TYPE
136#define DEBUG_TYPE "live-debug-values"
137
138// Act more like the VarLoc implementation, by propagating some locations too
139// far and ignoring some transfers.
140static cl::opt<bool> EmulateOldLDV("emulate-old-livedebugvalues", cl::Hidden,
141 cl::desc("Act like old LiveDebugValues did"),
142 cl::init(Val: false));
143
144// Limit for the maximum number of stack slots we should track, past which we
145// will ignore any spills. InstrRefBasedLDV gathers detailed information on all
146// stack slots which leads to high memory consumption, and in some scenarios
147// (such as asan with very many locals) the working set of the function can be
148// very large, causing many spills. In these scenarios, it is very unlikely that
149// the developer has hundreds of variables live at the same time that they're
150// carefully thinking about -- instead, they probably autogenerated the code.
151// When this happens, gracefully stop tracking excess spill slots, rather than
152// consuming all the developer's memory.
153static cl::opt<unsigned>
154 StackWorkingSetLimit("livedebugvalues-max-stack-slots", cl::Hidden,
155 cl::desc("livedebugvalues-stack-ws-limit"),
156 cl::init(Val: 250));
157
158// Limit for the maximum number of stack slot indexes, past which we stop
159// tracking spills altogether. MLocTracker reserves a location per subregister
160// index per tracked slot, so this cost grows sharply on targets with many
161// subregister indexes.
162static cl::opt<unsigned>
163 StackSlotIdxesLimit("livedebugvalues-max-stack-slot-idxes", cl::Hidden,
164 cl::desc("livedebugvalues-max-stack-slot-idxes"),
165 cl::init(Val: 128));
166
167DbgOpID DbgOpID::UndefID = DbgOpID(0xffffffff);
168
169/// Tracker for converting machine value locations and variable values into
170/// variable locations (the output of LiveDebugValues), recorded as DBG_VALUEs
171/// specifying block live-in locations and transfers within blocks.
172///
173/// Operating on a per-block basis, this class takes a (pre-loaded) MLocTracker
174/// and must be initialized with the set of variable values that are live-in to
175/// the block. The caller then repeatedly calls process(). TransferTracker picks
176/// out variable locations for the live-in variable values (if there _is_ a
177/// location) and creates the corresponding DBG_VALUEs. Then, as the block is
178/// stepped through, transfers of values between machine locations are
179/// identified and if profitable, a DBG_VALUE created.
180///
181/// This is where debug use-before-defs would be resolved: a variable with an
182/// unavailable value could materialize in the middle of a block, when the
183/// value becomes available. Or, we could detect clobbers and re-specify the
184/// variable in a backup location. (XXX these are unimplemented).
185class TransferTracker {
186public:
187 const TargetInstrInfo *TII;
188 const TargetLowering *TLI;
189 /// This machine location tracker is assumed to always contain the up-to-date
190 /// value mapping for all machine locations. TransferTracker only reads
191 /// information from it. (XXX make it const?)
192 MLocTracker *MTracker;
193 MachineFunction &MF;
194 const DebugVariableMap &DVMap;
195 bool ShouldEmitDebugEntryValues;
196
197 /// Record of all changes in variable locations at a block position. Awkwardly
198 /// we allow inserting either before or after the point: MBB != nullptr
199 /// indicates it's before, otherwise after.
200 struct Transfer {
201 MachineBasicBlock::instr_iterator Pos; /// Position to insert DBG_VALUes
202 MachineBasicBlock *MBB; /// non-null if we should insert after.
203 /// Vector of DBG_VALUEs to insert. Store with their DebugVariableID so that
204 /// they can be sorted into a stable order for emission at a later time.
205 SmallVector<std::pair<DebugVariableID, MachineInstr *>, 4> Insts;
206 };
207
208 /// Stores the resolved operands (machine locations and constants) and
209 /// qualifying meta-information needed to construct a concrete DBG_VALUE-like
210 /// instruction.
211 struct ResolvedDbgValue {
212 SmallVector<ResolvedDbgOp> Ops;
213 DbgValueProperties Properties;
214
215 ResolvedDbgValue(SmallVectorImpl<ResolvedDbgOp> &Ops,
216 DbgValueProperties Properties)
217 : Ops(Ops.begin(), Ops.end()), Properties(Properties) {}
218
219 /// Returns all the LocIdx values used in this struct, in the order in which
220 /// they appear as operands in the debug value; may contain duplicates.
221 auto loc_indices() const {
222 return map_range(
223 C: make_filter_range(
224 Range: Ops, Pred: [](const ResolvedDbgOp &Op) { return !Op.IsConst; }),
225 F: [](const ResolvedDbgOp &Op) { return Op.Loc; });
226 }
227 };
228
229 /// Collection of transfers (DBG_VALUEs) to be inserted.
230 SmallVector<Transfer, 32> Transfers;
231
232 /// Local cache of what-value-is-in-what-LocIdx. Used to identify differences
233 /// between TransferTrackers view of variable locations and MLocTrackers. For
234 /// example, MLocTracker observes all clobbers, but TransferTracker lazily
235 /// does not.
236 SmallVector<ValueIDNum, 32> VarLocs;
237
238 /// Map from LocIdxes to which DebugVariables are based that location.
239 /// Mantained while stepping through the block. Not accurate if
240 /// VarLocs[Idx] != MTracker->LocIdxToIDNum[Idx].
241 DenseMap<LocIdx, SmallSet<DebugVariableID, 4>> ActiveMLocs;
242
243 /// Map from DebugVariable to it's current location and qualifying meta
244 /// information. To be used in conjunction with ActiveMLocs to construct
245 /// enough information for the DBG_VALUEs for a particular LocIdx.
246 DenseMap<DebugVariableID, ResolvedDbgValue> ActiveVLocs;
247
248 /// Temporary cache of DBG_VALUEs to be entered into the Transfers collection.
249 SmallVector<std::pair<DebugVariableID, MachineInstr *>, 4> PendingDbgValues;
250
251 /// Record of a use-before-def: created when a value that's live-in to the
252 /// current block isn't available in any machine location, but it will be
253 /// defined in this block.
254 struct UseBeforeDef {
255 /// Value of this variable, def'd in block.
256 SmallVector<DbgOp> Values;
257 /// Identity of this variable.
258 DebugVariableID VarID;
259 /// Additional variable properties.
260 DbgValueProperties Properties;
261 UseBeforeDef(ArrayRef<DbgOp> Values, DebugVariableID VarID,
262 const DbgValueProperties &Properties)
263 : Values(Values), VarID(VarID), Properties(Properties) {}
264 };
265
266 /// Map from instruction index (within the block) to the set of UseBeforeDefs
267 /// that become defined at that instruction.
268 DenseMap<unsigned, SmallVector<UseBeforeDef, 1>> UseBeforeDefs;
269
270 /// The set of variables that are in UseBeforeDefs and can become a location
271 /// once the relevant value is defined. An element being erased from this
272 /// collection prevents the use-before-def materializing.
273 DenseSet<DebugVariableID> UseBeforeDefVariables;
274
275 const TargetRegisterInfo &TRI;
276 const BitVector &CalleeSavedRegs;
277
278 TransferTracker(const TargetInstrInfo *TII, MLocTracker *MTracker,
279 MachineFunction &MF, const DebugVariableMap &DVMap,
280 const TargetRegisterInfo &TRI,
281 const BitVector &CalleeSavedRegs,
282 bool ShouldEmitDebugEntryValues)
283 : TII(TII), MTracker(MTracker), MF(MF), DVMap(DVMap), TRI(TRI),
284 CalleeSavedRegs(CalleeSavedRegs) {
285 TLI = MF.getSubtarget().getTargetLowering();
286 this->ShouldEmitDebugEntryValues = ShouldEmitDebugEntryValues;
287 }
288
289 bool isCalleeSaved(LocIdx L) const {
290 unsigned Reg = MTracker->LocIdxToLocID[L];
291 if (Reg >= MTracker->NumRegs)
292 return false;
293 for (MCRegAliasIterator RAI(Reg, &TRI, true); RAI.isValid(); ++RAI)
294 if (CalleeSavedRegs.test(Idx: (*RAI).id()))
295 return true;
296 return false;
297 };
298
299 // An estimate of the expected lifespan of values at a machine location, with
300 // a greater value corresponding to a longer expected lifespan, i.e. spill
301 // slots generally live longer than callee-saved registers which generally
302 // live longer than non-callee-saved registers. The minimum value of 0
303 // corresponds to an illegal location that cannot have a "lifespan" at all.
304 enum class LocationQuality : unsigned char {
305 Illegal = 0,
306 Register,
307 CalleeSavedRegister,
308 SpillSlot,
309 Best = SpillSlot
310 };
311
312 class LocationAndQuality {
313 unsigned Location : 24;
314 unsigned Quality : 8;
315
316 public:
317 LocationAndQuality() : Location(0), Quality(0) {}
318 LocationAndQuality(LocIdx L, LocationQuality Q)
319 : Location(L.asU64()), Quality(static_cast<unsigned>(Q)) {}
320 LocIdx getLoc() const {
321 if (!Quality)
322 return LocIdx::MakeIllegalLoc();
323 return LocIdx(Location);
324 }
325 LocationQuality getQuality() const { return LocationQuality(Quality); }
326 bool isIllegal() const { return !Quality; }
327 bool isBest() const { return getQuality() == LocationQuality::Best; }
328 };
329
330 using ValueLocPair = std::pair<ValueIDNum, LocationAndQuality>;
331
332 static inline bool ValueToLocSort(const ValueLocPair &A,
333 const ValueLocPair &B) {
334 return A.first < B.first;
335 };
336
337 // Returns the LocationQuality for the location L iff the quality of L is
338 // is strictly greater than the provided minimum quality.
339 std::optional<LocationQuality>
340 getLocQualityIfBetter(LocIdx L, LocationQuality Min) const {
341 if (L.isIllegal())
342 return std::nullopt;
343 if (Min >= LocationQuality::SpillSlot)
344 return std::nullopt;
345 if (MTracker->isSpill(Idx: L))
346 return LocationQuality::SpillSlot;
347 if (Min >= LocationQuality::CalleeSavedRegister)
348 return std::nullopt;
349 if (isCalleeSaved(L))
350 return LocationQuality::CalleeSavedRegister;
351 if (Min >= LocationQuality::Register)
352 return std::nullopt;
353 return LocationQuality::Register;
354 }
355
356 /// For a variable \p Var with the live-in value \p Value, attempts to resolve
357 /// the DbgValue to a concrete DBG_VALUE, emitting that value and loading the
358 /// tracking information to track Var throughout the block.
359 /// \p ValueToLoc is a map containing the best known location for every
360 /// ValueIDNum that Value may use.
361 /// \p MBB is the basic block that we are loading the live-in value for.
362 /// \p DbgOpStore is the map containing the DbgOpID->DbgOp mapping needed to
363 /// determine the values used by Value.
364 void loadVarInloc(MachineBasicBlock &MBB, DbgOpIDMap &DbgOpStore,
365 const SmallVectorImpl<ValueLocPair> &ValueToLoc,
366 DebugVariableID VarID, DbgValue Value) {
367 SmallVector<DbgOp> DbgOps;
368 SmallVector<ResolvedDbgOp> ResolvedDbgOps;
369 bool IsValueValid = true;
370 unsigned LastUseBeforeDef = 0;
371 bool DbgLocAvailableAndIsEntryVal = false;
372
373 // If every value used by the incoming DbgValue is available at block
374 // entry, ResolvedDbgOps will contain the machine locations/constants for
375 // those values and will be used to emit a debug location.
376 // If one or more values are not yet available, but will all be defined in
377 // this block, then LastUseBeforeDef will track the instruction index in
378 // this BB at which the last of those values is defined, DbgOps will
379 // contain the values that we will emit when we reach that instruction.
380 // If one or more values are undef or not available throughout this block,
381 // and we can't recover as an entry value, we set IsValueValid=false and
382 // skip this variable.
383 for (DbgOpID ID : Value.getDbgOpIDs()) {
384 DbgOp Op = DbgOpStore.find(ID);
385 DbgOps.push_back(Elt: Op);
386 if (ID.isUndef()) {
387 IsValueValid = false;
388 break;
389 }
390 if (ID.isConst()) {
391 ResolvedDbgOps.push_back(Elt: Op.MO);
392 continue;
393 }
394
395 // Search for the desired ValueIDNum, to examine the best location found
396 // for it. Use an empty ValueLocPair to search for an entry in ValueToLoc.
397 const ValueIDNum &Num = Op.ID;
398 ValueLocPair Probe(Num, LocationAndQuality());
399 auto ValuesPreferredLoc =
400 llvm::lower_bound(Range: ValueToLoc, Value&: Probe, C: ValueToLocSort);
401
402 // There must be a legitimate entry found for Num.
403 assert(ValuesPreferredLoc != ValueToLoc.end() &&
404 ValuesPreferredLoc->first == Num);
405
406 if (ValuesPreferredLoc->second.isIllegal()) {
407 // If it's a def that occurs in this block, register it as a
408 // use-before-def to be resolved as we step through the block.
409 // Continue processing values so that we add any other UseBeforeDef
410 // entries needed for later.
411 if (Num.getBlock() == (unsigned)MBB.getNumber() && !Num.isPHI()) {
412 LastUseBeforeDef = std::max(a: LastUseBeforeDef,
413 b: static_cast<unsigned>(Num.getInst()));
414 continue;
415 }
416 recoverAsEntryValue(VarID, Prop: Value.Properties, Num);
417 IsValueValid = false;
418 break;
419 }
420
421 // Defer modifying ActiveVLocs until after we've confirmed we have a
422 // live range.
423 LocIdx M = ValuesPreferredLoc->second.getLoc();
424 ResolvedDbgOps.push_back(Elt: M);
425 if (Value.Properties.DIExpr->isEntryValue())
426 DbgLocAvailableAndIsEntryVal = true;
427 }
428
429 // If we cannot produce a valid value for the LiveIn value within this
430 // block, skip this variable.
431 if (!IsValueValid)
432 return;
433
434 // Add UseBeforeDef entry for the last value to be defined in this block.
435 if (LastUseBeforeDef) {
436 addUseBeforeDef(VarID, Properties: Value.Properties, DbgOps, Inst: LastUseBeforeDef);
437 return;
438 }
439
440 auto &[Var, DILoc] = DVMap.lookupDVID(ID: VarID);
441 PendingDbgValues.push_back(
442 Elt: std::make_pair(x&: VarID, y: &*MTracker->emitLoc(DbgOps: ResolvedDbgOps, Var, DILoc,
443 Properties: Value.Properties)));
444
445 // If the location is available at block entry and is an entry value, skip
446 // tracking and recording thr transfer.
447 if (DbgLocAvailableAndIsEntryVal)
448 return;
449
450 // The LiveIn value is available at block entry, begin tracking and record
451 // the transfer.
452 for (const ResolvedDbgOp &Op : ResolvedDbgOps)
453 if (!Op.IsConst)
454 ActiveMLocs[Op.Loc].insert(V: VarID);
455 auto NewValue = ResolvedDbgValue{ResolvedDbgOps, Value.Properties};
456 ActiveVLocs.insert_or_assign(Key: VarID, Val: std::move(NewValue));
457 }
458
459 /// Load object with live-in variable values. \p mlocs contains the live-in
460 /// values in each machine location, while \p vlocs the live-in variable
461 /// values. This method picks variable locations for the live-in variables,
462 /// creates DBG_VALUEs and puts them in #Transfers, then prepares the other
463 /// object fields to track variable locations as we step through the block.
464 /// FIXME: could just examine mloctracker instead of passing in \p mlocs?
465 void
466 loadInlocs(MachineBasicBlock &MBB, ValueTable &MLocs, DbgOpIDMap &DbgOpStore,
467 const SmallVectorImpl<std::pair<DebugVariableID, DbgValue>> &VLocs,
468 unsigned NumLocs) {
469 ActiveMLocs.clear();
470 ActiveVLocs.clear();
471 VarLocs.clear();
472 VarLocs.reserve(N: NumLocs);
473 UseBeforeDefs.clear();
474 UseBeforeDefVariables.clear();
475
476 // Mapping of the preferred locations for each value. Collected into this
477 // vector then sorted for easy searching.
478 SmallVector<ValueLocPair, 16> ValueToLoc;
479
480 // Initialized the preferred-location map with illegal locations, to be
481 // filled in later.
482 for (const auto &VLoc : VLocs)
483 if (VLoc.second.Kind == DbgValue::Def)
484 for (DbgOpID OpID : VLoc.second.getDbgOpIDs())
485 if (!OpID.ID.IsConst)
486 ValueToLoc.push_back(
487 Elt: {DbgOpStore.find(ID: OpID).ID, LocationAndQuality()});
488
489 llvm::sort(C&: ValueToLoc, Comp: ValueToLocSort);
490 ActiveMLocs.reserve(NumEntries: VLocs.size());
491 ActiveVLocs.reserve(NumEntries: VLocs.size());
492
493 // Produce a map of value numbers to the current machine locs they live
494 // in. When emulating VarLocBasedImpl, there should only be one
495 // location; when not, we get to pick.
496 for (auto Location : MTracker->locations()) {
497 LocIdx Idx = Location.Idx;
498 ValueIDNum &VNum = MLocs[Idx.asU64()];
499 if (VNum == ValueIDNum::EmptyValue)
500 continue;
501 VarLocs.push_back(Elt: VNum);
502
503 // Is there a variable that wants a location for this value? If not, skip.
504 ValueLocPair Probe(VNum, LocationAndQuality());
505 auto VIt = llvm::lower_bound(Range&: ValueToLoc, Value&: Probe, C: ValueToLocSort);
506 if (VIt == ValueToLoc.end() || VIt->first != VNum)
507 continue;
508
509 auto &Previous = VIt->second;
510 // If this is the first location with that value, pick it. Otherwise,
511 // consider whether it's a "longer term" location.
512 std::optional<LocationQuality> ReplacementQuality =
513 getLocQualityIfBetter(L: Idx, Min: Previous.getQuality());
514 if (ReplacementQuality)
515 Previous = LocationAndQuality(Idx, *ReplacementQuality);
516 }
517
518 // Now map variables to their picked LocIdxes.
519 for (const auto &Var : VLocs) {
520 loadVarInloc(MBB, DbgOpStore, ValueToLoc, VarID: Var.first, Value: Var.second);
521 }
522 flushDbgValues(Pos: MBB.begin(), MBB: &MBB);
523 }
524
525 /// Record that \p Var has value \p ID, a value that becomes available
526 /// later in the function.
527 void addUseBeforeDef(DebugVariableID VarID,
528 const DbgValueProperties &Properties,
529 const SmallVectorImpl<DbgOp> &DbgOps, unsigned Inst) {
530 UseBeforeDefs[Inst].emplace_back(Args: DbgOps, Args&: VarID, Args: Properties);
531 UseBeforeDefVariables.insert(V: VarID);
532 }
533
534 /// After the instruction at index \p Inst and position \p pos has been
535 /// processed, check whether it defines a variable value in a use-before-def.
536 /// If so, and the variable value hasn't changed since the start of the
537 /// block, create a DBG_VALUE.
538 void checkInstForNewValues(unsigned Inst, MachineBasicBlock::iterator pos) {
539 auto MIt = UseBeforeDefs.find(Val: Inst);
540 if (MIt == UseBeforeDefs.end())
541 return;
542
543 // Map of values to the locations that store them for every value used by
544 // the variables that may have become available.
545 SmallDenseMap<ValueIDNum, LocationAndQuality> ValueToLoc;
546
547 // Populate ValueToLoc with illegal default mappings for every value used by
548 // any UseBeforeDef variables for this instruction.
549 for (auto &Use : MIt->second) {
550 if (!UseBeforeDefVariables.count(V: Use.VarID))
551 continue;
552
553 for (DbgOp &Op : Use.Values) {
554 assert(!Op.isUndef() && "UseBeforeDef erroneously created for a "
555 "DbgValue with undef values.");
556 if (Op.IsConst)
557 continue;
558
559 ValueToLoc.insert(KV: {Op.ID, LocationAndQuality()});
560 }
561 }
562
563 // Exit early if we have no DbgValues to produce.
564 if (ValueToLoc.empty())
565 return;
566
567 // Determine the best location for each desired value.
568 for (auto Location : MTracker->locations()) {
569 LocIdx Idx = Location.Idx;
570 ValueIDNum &LocValueID = Location.Value;
571
572 // Is there a variable that wants a location for this value? If not, skip.
573 auto VIt = ValueToLoc.find(Val: LocValueID);
574 if (VIt == ValueToLoc.end())
575 continue;
576
577 auto &Previous = VIt->second;
578 // If this is the first location with that value, pick it. Otherwise,
579 // consider whether it's a "longer term" location.
580 std::optional<LocationQuality> ReplacementQuality =
581 getLocQualityIfBetter(L: Idx, Min: Previous.getQuality());
582 if (ReplacementQuality)
583 Previous = LocationAndQuality(Idx, *ReplacementQuality);
584 }
585
586 // Using the map of values to locations, produce a final set of values for
587 // this variable.
588 for (auto &Use : MIt->second) {
589 if (!UseBeforeDefVariables.count(V: Use.VarID))
590 continue;
591
592 SmallVector<ResolvedDbgOp> DbgOps;
593
594 for (DbgOp &Op : Use.Values) {
595 if (Op.IsConst) {
596 DbgOps.push_back(Elt: Op.MO);
597 continue;
598 }
599 LocIdx NewLoc = ValueToLoc.find(Val: Op.ID)->second.getLoc();
600 if (NewLoc.isIllegal())
601 break;
602 DbgOps.push_back(Elt: NewLoc);
603 }
604
605 // If at least one value used by this debug value is no longer available,
606 // i.e. one of the values was killed before we finished defining all of
607 // the values used by this variable, discard.
608 if (DbgOps.size() != Use.Values.size())
609 continue;
610
611 // Otherwise, we're good to go.
612 auto &[Var, DILoc] = DVMap.lookupDVID(ID: Use.VarID);
613 PendingDbgValues.push_back(Elt: std::make_pair(
614 x&: Use.VarID, y: MTracker->emitLoc(DbgOps, Var, DILoc, Properties: Use.Properties)));
615 }
616 flushDbgValues(Pos: pos, MBB: nullptr);
617 }
618
619 /// Helper to move created DBG_VALUEs into Transfers collection.
620 void flushDbgValues(MachineBasicBlock::iterator Pos, MachineBasicBlock *MBB) {
621 if (PendingDbgValues.size() == 0)
622 return;
623
624 // Pick out the instruction start position.
625 MachineBasicBlock::instr_iterator BundleStart;
626 if (MBB && Pos == MBB->begin())
627 BundleStart = MBB->instr_begin();
628 else
629 BundleStart = getBundleStart(I: Pos->getIterator());
630
631 Transfers.push_back(Elt: {.Pos: BundleStart, .MBB: MBB, .Insts: PendingDbgValues});
632 PendingDbgValues.clear();
633 }
634
635 bool isEntryValueVariable(const DebugVariable &Var,
636 const DIExpression *Expr) const {
637 if (!Var.getVariable()->isParameter())
638 return false;
639
640 if (Var.getInlinedAt())
641 return false;
642
643 if (Expr->getNumElements() > 0 && !Expr->isDeref())
644 return false;
645
646 return true;
647 }
648
649 bool isEntryValueValue(const ValueIDNum &Val) const {
650 // Must be in entry block (block number zero), and be a PHI / live-in value.
651 if (Val.getBlock() || !Val.isPHI())
652 return false;
653
654 // Entry values must enter in a register.
655 if (MTracker->isSpill(Idx: Val.getLoc()))
656 return false;
657
658 Register SP = TLI->getStackPointerRegisterToSaveRestore();
659 Register FP = TRI.getFrameRegister(MF);
660 Register Reg = MTracker->LocIdxToLocID[Val.getLoc()];
661 return Reg != SP && Reg != FP;
662 }
663
664 bool recoverAsEntryValue(DebugVariableID VarID,
665 const DbgValueProperties &Prop,
666 const ValueIDNum &Num) {
667 // Is this variable location a candidate to be an entry value. First,
668 // should we be trying this at all?
669 if (!ShouldEmitDebugEntryValues)
670 return false;
671
672 const DIExpression *DIExpr = Prop.DIExpr;
673
674 // We don't currently emit entry values for DBG_VALUE_LISTs.
675 if (Prop.IsVariadic) {
676 // If this debug value can be converted to be non-variadic, then do so;
677 // otherwise give up.
678 auto NonVariadicExpression =
679 DIExpression::convertToNonVariadicExpression(Expr: DIExpr);
680 if (!NonVariadicExpression)
681 return false;
682 DIExpr = *NonVariadicExpression;
683 }
684
685 auto &[Var, DILoc] = DVMap.lookupDVID(ID: VarID);
686
687 // If the expression is a DW_OP_entry_value, emit the variable location
688 // as-is.
689 if (DIExpr->isEntryValue()) {
690 Register Reg = MTracker->LocIdxToLocID[Num.getLoc()];
691 MachineOperand MO = MachineOperand::CreateReg(Reg, isDef: false);
692 PendingDbgValues.push_back(Elt: std::make_pair(
693 x&: VarID, y: &*emitMOLoc(MO, Var, Properties: {DIExpr, Prop.Indirect, false})));
694 return true;
695 }
696
697 // Is the variable appropriate for entry values (i.e., is a parameter).
698 if (!isEntryValueVariable(Var, Expr: DIExpr))
699 return false;
700
701 // Is the value assigned to this variable still the entry value?
702 if (!isEntryValueValue(Val: Num))
703 return false;
704
705 // Emit a variable location using an entry value expression.
706 DIExpression *NewExpr =
707 DIExpression::prepend(Expr: DIExpr, Flags: DIExpression::EntryValue);
708 Register Reg = MTracker->LocIdxToLocID[Num.getLoc()];
709 MachineOperand MO = MachineOperand::CreateReg(Reg, isDef: false);
710 PendingDbgValues.push_back(Elt: std::make_pair(
711 x&: VarID, y: &*emitMOLoc(MO, Var, Properties: {NewExpr, Prop.Indirect, false})));
712 return true;
713 }
714
715 /// Change a variable value after encountering a DBG_VALUE inside a block.
716 void redefVar(const MachineInstr &MI) {
717 DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
718 MI.getDebugLoc()->getInlinedAt());
719 DbgValueProperties Properties(MI);
720 DebugVariableID VarID = DVMap.getDVID(Var);
721
722 // Ignore non-register locations, we don't transfer those.
723 if (MI.isUndefDebugValue() || MI.getDebugExpression()->isEntryValue() ||
724 all_of(Range: MI.debug_operands(),
725 P: [](const MachineOperand &MO) { return !MO.isReg(); })) {
726 auto It = ActiveVLocs.find(Val: VarID);
727 if (It != ActiveVLocs.end()) {
728 for (LocIdx Loc : It->second.loc_indices())
729 ActiveMLocs[Loc].erase(V: VarID);
730 ActiveVLocs.erase(I: It);
731 }
732 // Any use-before-defs no longer apply.
733 UseBeforeDefVariables.erase(V: VarID);
734 return;
735 }
736
737 SmallVector<ResolvedDbgOp> NewLocs;
738 for (const MachineOperand &MO : MI.debug_operands()) {
739 if (MO.isReg()) {
740 // Any undef regs have already been filtered out above.
741 Register Reg = MO.getReg();
742 LocIdx NewLoc = MTracker->getRegMLoc(R: Reg);
743 NewLocs.push_back(Elt: NewLoc);
744 } else {
745 NewLocs.push_back(Elt: MO);
746 }
747 }
748
749 redefVar(MI, Properties, NewLocs);
750 }
751
752 /// Handle a change in variable location within a block. Terminate the
753 /// variables current location, and record the value it now refers to, so
754 /// that we can detect location transfers later on.
755 void redefVar(const MachineInstr &MI, const DbgValueProperties &Properties,
756 SmallVectorImpl<ResolvedDbgOp> &NewLocs) {
757 DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
758 MI.getDebugLoc()->getInlinedAt());
759 DebugVariableID VarID = DVMap.getDVID(Var);
760 // Any use-before-defs no longer apply.
761 UseBeforeDefVariables.erase(V: VarID);
762
763 // Erase any previous location.
764 auto It = ActiveVLocs.find(Val: VarID);
765 if (It != ActiveVLocs.end()) {
766 for (LocIdx Loc : It->second.loc_indices())
767 ActiveMLocs[Loc].erase(V: VarID);
768 }
769
770 // If there _is_ no new location, all we had to do was erase.
771 if (NewLocs.empty()) {
772 if (It != ActiveVLocs.end())
773 ActiveVLocs.erase(I: It);
774 return;
775 }
776
777 SmallVector<std::pair<LocIdx, DebugVariableID>> LostMLocs;
778 for (ResolvedDbgOp &Op : NewLocs) {
779 if (Op.IsConst)
780 continue;
781
782 LocIdx NewLoc = Op.Loc;
783
784 // Check whether our local copy of values-by-location in #VarLocs is out
785 // of date. Wipe old tracking data for the location if it's been clobbered
786 // in the meantime.
787 if (MTracker->readMLoc(L: NewLoc) != VarLocs[NewLoc.asU64()]) {
788 for (const auto &P : ActiveMLocs[NewLoc]) {
789 auto LostVLocIt = ActiveVLocs.find(Val: P);
790 if (LostVLocIt != ActiveVLocs.end()) {
791 for (LocIdx Loc : LostVLocIt->second.loc_indices()) {
792 // Every active variable mapping for NewLoc will be cleared, no
793 // need to track individual variables.
794 if (Loc == NewLoc)
795 continue;
796 LostMLocs.emplace_back(Args&: Loc, Args: P);
797 }
798 }
799 ActiveVLocs.erase(Val: P);
800 }
801 for (const auto &LostMLoc : LostMLocs)
802 ActiveMLocs[LostMLoc.first].erase(V: LostMLoc.second);
803 LostMLocs.clear();
804 It = ActiveVLocs.find(Val: VarID);
805 ActiveMLocs[NewLoc.asU64()].clear();
806 VarLocs[NewLoc.asU64()] = MTracker->readMLoc(L: NewLoc);
807 }
808
809 ActiveMLocs[NewLoc].insert(V: VarID);
810 }
811
812 if (It == ActiveVLocs.end()) {
813 ActiveVLocs.insert(
814 KV: std::make_pair(x&: VarID, y: ResolvedDbgValue(NewLocs, Properties)));
815 } else {
816 It->second.Ops.assign(RHS: NewLocs);
817 It->second.Properties = Properties;
818 }
819 }
820
821 /// Account for a location \p mloc being clobbered. Examine the variable
822 /// locations that will be terminated: and try to recover them by using
823 /// another location. Optionally, given \p MakeUndef, emit a DBG_VALUE to
824 /// explicitly terminate a location if it can't be recovered.
825 void clobberMloc(LocIdx MLoc, MachineBasicBlock::iterator Pos,
826 bool MakeUndef = true) {
827 auto ActiveMLocIt = ActiveMLocs.find(Val: MLoc);
828 if (ActiveMLocIt == ActiveMLocs.end())
829 return;
830
831 // What was the old variable value?
832 ValueIDNum OldValue = VarLocs[MLoc.asU64()];
833 clobberMloc(MLoc, OldValue, Pos, MakeUndef);
834 }
835 /// Overload that takes an explicit value \p OldValue for when the value in
836 /// \p MLoc has changed and the TransferTracker's locations have not been
837 /// updated yet.
838 void clobberMloc(LocIdx MLoc, ValueIDNum OldValue,
839 MachineBasicBlock::iterator Pos, bool MakeUndef = true) {
840 auto ActiveMLocIt = ActiveMLocs.find(Val: MLoc);
841 if (ActiveMLocIt == ActiveMLocs.end())
842 return;
843
844 VarLocs[MLoc.asU64()] = ValueIDNum::EmptyValue;
845
846 // Examine the remaining variable locations: if we can find the same value
847 // again, we can recover the location.
848 std::optional<LocIdx> NewLoc;
849 for (auto Loc : MTracker->locations())
850 if (Loc.Value == OldValue)
851 NewLoc = Loc.Idx;
852
853 // If there is no location, and we weren't asked to make the variable
854 // explicitly undef, then stop here.
855 if (!NewLoc && !MakeUndef) {
856 // Try and recover a few more locations with entry values.
857 for (DebugVariableID VarID : ActiveMLocIt->second) {
858 auto &Prop = ActiveVLocs.find(Val: VarID)->second.Properties;
859 recoverAsEntryValue(VarID, Prop, Num: OldValue);
860 }
861 flushDbgValues(Pos, MBB: nullptr);
862 return;
863 }
864
865 // Examine all the variables based on this location.
866 DenseSet<DebugVariableID> NewMLocs;
867 // If no new location has been found, every variable that depends on this
868 // MLoc is dead, so end their existing MLoc->Var mappings as well.
869 SmallVector<std::pair<LocIdx, DebugVariableID>> LostMLocs;
870 for (DebugVariableID VarID : ActiveMLocIt->second) {
871 auto ActiveVLocIt = ActiveVLocs.find(Val: VarID);
872 // Re-state the variable location: if there's no replacement then NewLoc
873 // is std::nullopt and a $noreg DBG_VALUE will be created. Otherwise, a
874 // DBG_VALUE identifying the alternative location will be emitted.
875 const DbgValueProperties &Properties = ActiveVLocIt->second.Properties;
876
877 // Produce the new list of debug ops - an empty list if no new location
878 // was found, or the existing list with the substitution MLoc -> NewLoc
879 // otherwise.
880 SmallVector<ResolvedDbgOp> DbgOps;
881 if (NewLoc) {
882 ResolvedDbgOp OldOp(MLoc);
883 ResolvedDbgOp NewOp(*NewLoc);
884 // Insert illegal ops to overwrite afterwards.
885 DbgOps.insert(I: DbgOps.begin(), NumToInsert: ActiveVLocIt->second.Ops.size(),
886 Elt: ResolvedDbgOp(LocIdx::MakeIllegalLoc()));
887 replace_copy(Range&: ActiveVLocIt->second.Ops, Out: DbgOps.begin(), OldValue: OldOp, NewValue: NewOp);
888 }
889
890 auto &[Var, DILoc] = DVMap.lookupDVID(ID: VarID);
891 PendingDbgValues.push_back(Elt: std::make_pair(
892 x&: VarID, y: &*MTracker->emitLoc(DbgOps, Var, DILoc, Properties)));
893
894 // Update machine locations <=> variable locations maps. Defer updating
895 // ActiveMLocs to avoid invalidating the ActiveMLocIt iterator.
896 if (!NewLoc) {
897 for (LocIdx Loc : ActiveVLocIt->second.loc_indices()) {
898 if (Loc != MLoc)
899 LostMLocs.emplace_back(Args&: Loc, Args&: VarID);
900 }
901 ActiveVLocs.erase(I: ActiveVLocIt);
902 } else {
903 ActiveVLocIt->second.Ops = DbgOps;
904 NewMLocs.insert(V: VarID);
905 }
906 }
907
908 // Remove variables from ActiveMLocs if they no longer use any other MLocs
909 // due to being killed by this clobber.
910 for (auto &LocVarIt : LostMLocs) {
911 auto LostMLocIt = ActiveMLocs.find(Val: LocVarIt.first);
912 assert(LostMLocIt != ActiveMLocs.end() &&
913 "Variable was using this MLoc, but ActiveMLocs[MLoc] has no "
914 "entries?");
915 LostMLocIt->second.erase(V: LocVarIt.second);
916 }
917
918 // We lazily track what locations have which values; if we've found a new
919 // location for the clobbered value, remember it.
920 if (NewLoc)
921 VarLocs[NewLoc->asU64()] = OldValue;
922
923 flushDbgValues(Pos, MBB: nullptr);
924
925 // Commit ActiveMLoc changes.
926 ActiveMLocIt->second.clear();
927 if (!NewMLocs.empty())
928 ActiveMLocs[*NewLoc].insert_range(R&: NewMLocs);
929 }
930
931 /// Transfer variables based on \p Src to be based on \p Dst. This handles
932 /// both register copies as well as spills and restores. Creates DBG_VALUEs
933 /// describing the movement.
934 void transferMlocs(LocIdx Src, LocIdx Dst, MachineBasicBlock::iterator Pos) {
935 // Does Src still contain the value num we expect? If not, it's been
936 // clobbered in the meantime, and our variable locations are stale.
937 if (VarLocs[Src.asU64()] != MTracker->readMLoc(L: Src))
938 return;
939
940 // assert(ActiveMLocs[Dst].size() == 0);
941 //^^^ Legitimate scenario on account of un-clobbered slot being assigned to?
942
943 // Move set of active variables from one location to another.
944 auto MovingVars = ActiveMLocs[Src];
945 ActiveMLocs[Dst].insert_range(R&: MovingVars);
946 VarLocs[Dst.asU64()] = VarLocs[Src.asU64()];
947
948 // For each variable based on Src; create a location at Dst.
949 ResolvedDbgOp SrcOp(Src);
950 ResolvedDbgOp DstOp(Dst);
951 for (DebugVariableID VarID : MovingVars) {
952 auto ActiveVLocIt = ActiveVLocs.find(Val: VarID);
953 assert(ActiveVLocIt != ActiveVLocs.end());
954
955 // Update all instances of Src in the variable's tracked values to Dst.
956 llvm::replace(Range&: ActiveVLocIt->second.Ops, OldValue: SrcOp, NewValue: DstOp);
957
958 auto &[Var, DILoc] = DVMap.lookupDVID(ID: VarID);
959 MachineInstr *MI = MTracker->emitLoc(DbgOps: ActiveVLocIt->second.Ops, Var, DILoc,
960 Properties: ActiveVLocIt->second.Properties);
961 PendingDbgValues.push_back(Elt: std::make_pair(x&: VarID, y&: MI));
962 }
963 ActiveMLocs[Src].clear();
964 flushDbgValues(Pos, MBB: nullptr);
965
966 // XXX XXX XXX "pretend to be old LDV" means dropping all tracking data
967 // about the old location.
968 if (EmulateOldLDV)
969 VarLocs[Src.asU64()] = ValueIDNum::EmptyValue;
970 }
971
972 MachineInstrBuilder emitMOLoc(const MachineOperand &MO,
973 const DebugVariable &Var,
974 const DbgValueProperties &Properties) {
975 DebugLoc DL = DILocation::get(Context&: Var.getVariable()->getContext(), Line: 0, Column: 0,
976 Scope: Var.getVariable()->getScope(),
977 InlinedAt: const_cast<DILocation *>(Var.getInlinedAt()));
978 auto MIB = BuildMI(MF, MIMD: DL, MCID: TII->get(Opcode: TargetOpcode::DBG_VALUE));
979 MIB.add(MO);
980 if (Properties.Indirect)
981 MIB.addImm(Val: 0);
982 else
983 MIB.addReg(RegNo: 0);
984 MIB.addMetadata(MD: Var.getVariable());
985 MIB.addMetadata(MD: Properties.DIExpr);
986 return MIB;
987 }
988};
989
990//===----------------------------------------------------------------------===//
991// Implementation
992//===----------------------------------------------------------------------===//
993
994ValueIDNum ValueIDNum::EmptyValue = {UINT_MAX, UINT_MAX, UINT_MAX};
995
996#ifndef NDEBUG
997void ResolvedDbgOp::dump(const MLocTracker *MTrack) const {
998 if (IsConst) {
999 dbgs() << MO;
1000 } else {
1001 dbgs() << MTrack->LocIdxToName(Loc);
1002 }
1003}
1004void DbgOp::dump(const MLocTracker *MTrack) const {
1005 if (IsConst) {
1006 dbgs() << MO;
1007 } else if (!isUndef()) {
1008 dbgs() << MTrack->IDAsString(ID);
1009 }
1010}
1011void DbgOpID::dump(const MLocTracker *MTrack, const DbgOpIDMap *OpStore) const {
1012 if (!OpStore) {
1013 dbgs() << "ID(" << asU32() << ")";
1014 } else {
1015 OpStore->find(*this).dump(MTrack);
1016 }
1017}
1018void DbgValue::dump(const MLocTracker *MTrack,
1019 const DbgOpIDMap *OpStore) const {
1020 if (Kind == NoVal) {
1021 dbgs() << "NoVal(" << BlockNo << ")";
1022 } else if (Kind == VPHI || Kind == Def) {
1023 if (Kind == VPHI)
1024 dbgs() << "VPHI(" << BlockNo << ",";
1025 else
1026 dbgs() << "Def(";
1027 for (unsigned Idx = 0; Idx < getDbgOpIDs().size(); ++Idx) {
1028 getDbgOpID(Idx).dump(MTrack, OpStore);
1029 if (Idx != 0)
1030 dbgs() << ",";
1031 }
1032 dbgs() << ")";
1033 }
1034 if (Properties.Indirect)
1035 dbgs() << " indir";
1036 if (Properties.DIExpr)
1037 dbgs() << " " << *Properties.DIExpr;
1038}
1039#endif
1040
1041MLocTracker::MLocTracker(MachineFunction &MF, const TargetInstrInfo &TII,
1042 const TargetRegisterInfo &TRI,
1043 const TargetLowering &TLI)
1044 : MF(MF), TII(TII), TRI(TRI), TLI(TLI),
1045 LocIdxToIDNum(ValueIDNum::EmptyValue), LocIdxToLocID(0) {
1046 NumRegs = TRI.getNumRegs();
1047 reset();
1048 LocIDToLocIdx.resize(new_size: NumRegs, x: LocIdx::MakeIllegalLoc());
1049 assert(NumRegs < (1u << NUM_LOC_BITS)); // Detect bit packing failure
1050
1051 // Always track SP. This avoids the implicit clobbering caused by regmasks
1052 // from affectings its values. (LiveDebugValues disbelieves calls and
1053 // regmasks that claim to clobber SP).
1054 Register SP = TLI.getStackPointerRegisterToSaveRestore();
1055 if (SP) {
1056 unsigned ID = getLocID(Reg: SP);
1057 (void)lookupOrTrackRegister(ID);
1058
1059 for (MCRegAliasIterator RAI(SP, &TRI, true); RAI.isValid(); ++RAI)
1060 SPAliases.insert(V: *RAI);
1061 }
1062
1063 // Build some common stack positions -- full registers being spilt to the
1064 // stack.
1065 StackSlotIdxes.insert(KV: {{8, 0}, 0});
1066 StackSlotIdxes.insert(KV: {{16, 0}, 1});
1067 StackSlotIdxes.insert(KV: {{32, 0}, 2});
1068 StackSlotIdxes.insert(KV: {{64, 0}, 3});
1069 StackSlotIdxes.insert(KV: {{128, 0}, 4});
1070 StackSlotIdxes.insert(KV: {{256, 0}, 5});
1071 StackSlotIdxes.insert(KV: {{512, 0}, 6});
1072
1073 // Traverse all the subregister idxes, and ensure there's an index for them.
1074 // Duplicates are no problem: we're interested in their position in the
1075 // stack slot, we don't want to type the slot.
1076 for (unsigned int I = 1; I < TRI.getNumSubRegIndices(); ++I) {
1077 unsigned Size = TRI.getSubRegIdxSize(Idx: I);
1078 unsigned Offs = TRI.getSubRegIdxOffset(Idx: I);
1079 unsigned Idx = StackSlotIdxes.size();
1080
1081 // Some subregs have -1, -2 and so forth fed into their fields, to mean
1082 // special backend things. Ignore those.
1083 if (Size > 60000 || Offs > 60000)
1084 continue;
1085
1086 StackSlotIdxes.insert(KV: {{Size, Offs}, Idx});
1087 }
1088
1089 // There may also be strange register class sizes (think x86 fp80s).
1090 for (const TargetRegisterClass &RC : TRI.regclasses()) {
1091 unsigned Size = TRI.getRegSizeInBits(RC);
1092
1093 // We might see special reserved values as sizes, and classes for other
1094 // stuff the machine tries to model. If it's more than 512 bits, then it
1095 // is very unlikely to be a register than can be spilt.
1096 if (Size > 512)
1097 continue;
1098
1099 unsigned Idx = StackSlotIdxes.size();
1100 StackSlotIdxes.insert(KV: {{Size, 0}, Idx});
1101 }
1102
1103 for (auto &Idx : StackSlotIdxes)
1104 StackIdxesToPos[Idx.second] = Idx.first;
1105
1106 NumSlotIdxes = StackSlotIdxes.size();
1107}
1108
1109LocIdx MLocTracker::trackRegister(unsigned ID) {
1110 assert(ID != 0);
1111 LocIdx NewIdx = LocIdx(LocIdxToIDNum.size());
1112 LocIdxToIDNum.grow(N: NewIdx);
1113 LocIdxToLocID.grow(N: NewIdx);
1114
1115 // Default: it's an mphi.
1116 ValueIDNum ValNum = {CurBB, 0, NewIdx};
1117 // Was this reg ever touched by a regmask?
1118 for (const auto &MaskPair : reverse(C&: Masks)) {
1119 if (MaskPair.first->clobbersPhysReg(PhysReg: ID)) {
1120 // There was an earlier def we skipped.
1121 ValNum = {CurBB, MaskPair.second, NewIdx};
1122 break;
1123 }
1124 }
1125
1126 LocIdxToIDNum[NewIdx] = ValNum;
1127 LocIdxToLocID[NewIdx] = ID;
1128 return NewIdx;
1129}
1130
1131void MLocTracker::writeRegMask(const MachineOperand *MO, unsigned CurBB,
1132 unsigned InstID) {
1133 // Def any register we track have that isn't preserved. The regmask
1134 // terminates the liveness of a register, meaning its value can't be
1135 // relied upon -- we represent this by giving it a new value.
1136 for (auto Location : locations()) {
1137 unsigned ID = LocIdxToLocID[Location.Idx];
1138 // Don't clobber SP, even if the mask says it's clobbered.
1139 if (ID < NumRegs && !SPAliases.count(V: ID) && MO->clobbersPhysReg(PhysReg: ID))
1140 defReg(R: ID, BB: CurBB, Inst: InstID);
1141 }
1142 Masks.push_back(Elt: std::make_pair(x&: MO, y&: InstID));
1143}
1144
1145std::optional<SpillLocationNo> MLocTracker::getOrTrackSpillLoc(SpillLoc L) {
1146 // Don't track spills at all on targets with a large number of slot indexes.
1147 if (NumSlotIdxes >= StackSlotIdxesLimit)
1148 return std::nullopt;
1149
1150 SpillLocationNo SpillID(SpillLocs.idFor(Entry: L));
1151
1152 if (SpillID.id() == 0) {
1153 // If there is no location, and we have reached the limit of how many stack
1154 // slots to track, then don't track this one.
1155 if (SpillLocs.size() >= StackWorkingSetLimit)
1156 return std::nullopt;
1157
1158 // Spill location is untracked: create record for this one, and all
1159 // subregister slots too.
1160 SpillID = SpillLocationNo(SpillLocs.insert(Entry: L));
1161 for (unsigned StackIdx = 0; StackIdx < NumSlotIdxes; ++StackIdx) {
1162 unsigned L = getSpillIDWithIdx(Spill: SpillID, Idx: StackIdx);
1163 LocIdx Idx = LocIdx(LocIdxToIDNum.size()); // New idx
1164 LocIdxToIDNum.grow(N: Idx);
1165 LocIdxToLocID.grow(N: Idx);
1166 LocIDToLocIdx.push_back(x: Idx);
1167 LocIdxToLocID[Idx] = L;
1168 // Initialize to PHI value; corresponds to the location's live-in value
1169 // during transfer function construction.
1170 LocIdxToIDNum[Idx] = ValueIDNum(CurBB, 0, Idx);
1171 }
1172 }
1173 return SpillID;
1174}
1175
1176std::string MLocTracker::LocIdxToName(LocIdx Idx) const {
1177 unsigned ID = LocIdxToLocID[Idx];
1178 if (ID >= NumRegs) {
1179 StackSlotPos Pos = locIDToSpillIdx(ID);
1180 ID -= NumRegs;
1181 unsigned Slot = ID / NumSlotIdxes;
1182 return Twine("slot ")
1183 .concat(Suffix: Twine(Slot).concat(Suffix: Twine(" sz ").concat(Suffix: Twine(Pos.first)
1184 .concat(Suffix: Twine(" offs ").concat(Suffix: Twine(Pos.second))))))
1185 .str();
1186 } else {
1187 return TRI.getRegAsmName(Reg: ID).str();
1188 }
1189}
1190
1191std::string MLocTracker::IDAsString(const ValueIDNum &Num) const {
1192 std::string DefName = LocIdxToName(Idx: Num.getLoc());
1193 return Num.asString(mlocname: DefName);
1194}
1195
1196#ifndef NDEBUG
1197LLVM_DUMP_METHOD void MLocTracker::dump() {
1198 for (auto Location : locations()) {
1199 std::string MLocName = LocIdxToName(Location.Value.getLoc());
1200 std::string DefName = Location.Value.asString(MLocName);
1201 dbgs() << LocIdxToName(Location.Idx) << " --> " << DefName << "\n";
1202 }
1203}
1204
1205LLVM_DUMP_METHOD void MLocTracker::dump_mloc_map() {
1206 for (auto Location : locations()) {
1207 std::string foo = LocIdxToName(Location.Idx);
1208 dbgs() << "Idx " << Location.Idx.asU64() << " " << foo << "\n";
1209 }
1210}
1211#endif
1212
1213MachineInstrBuilder
1214MLocTracker::emitLoc(const SmallVectorImpl<ResolvedDbgOp> &DbgOps,
1215 const DebugVariable &Var, const DILocation *DILoc,
1216 const DbgValueProperties &Properties) {
1217 DebugLoc DL = DebugLoc(DILoc);
1218
1219 const MCInstrDesc &Desc = Properties.IsVariadic
1220 ? TII.get(Opcode: TargetOpcode::DBG_VALUE_LIST)
1221 : TII.get(Opcode: TargetOpcode::DBG_VALUE);
1222
1223#ifdef EXPENSIVE_CHECKS
1224 assert(all_of(DbgOps,
1225 [](const ResolvedDbgOp &Op) {
1226 return Op.IsConst || !Op.Loc.isIllegal();
1227 }) &&
1228 "Did not expect illegal ops in DbgOps.");
1229 assert((DbgOps.size() == 0 ||
1230 DbgOps.size() == Properties.getLocationOpCount()) &&
1231 "Expected to have either one DbgOp per MI LocationOp, or none.");
1232#endif
1233
1234 auto GetRegOp = [](unsigned Reg) -> MachineOperand {
1235 return MachineOperand::CreateReg(
1236 /* Reg */ Reg, /* isDef */ false, /* isImp */ false,
1237 /* isKill */ false, /* isDead */ false,
1238 /* isUndef */ false, /* isEarlyClobber */ false,
1239 /* SubReg */ 0, /* isDebug */ true);
1240 };
1241
1242 SmallVector<MachineOperand> MOs;
1243
1244 auto EmitUndef = [&]() {
1245 MOs.clear();
1246 MOs.assign(NumElts: Properties.getLocationOpCount(), Elt: GetRegOp(0));
1247 return BuildMI(MF, DL, MCID: Desc, IsIndirect: false, MOs, Variable: Var.getVariable(),
1248 Expr: Properties.DIExpr);
1249 };
1250
1251 // Don't bother passing any real operands to BuildMI if any of them would be
1252 // $noreg.
1253 if (DbgOps.empty())
1254 return EmitUndef();
1255
1256 bool Indirect = Properties.Indirect;
1257
1258 const DIExpression *Expr = Properties.DIExpr;
1259
1260 assert(DbgOps.size() == Properties.getLocationOpCount());
1261
1262 // If all locations are valid, accumulate them into our list of
1263 // MachineOperands. For any spilled locations, either update the indirectness
1264 // register or apply the appropriate transformations in the DIExpression.
1265 for (size_t Idx = 0; Idx < Properties.getLocationOpCount(); ++Idx) {
1266 const ResolvedDbgOp &Op = DbgOps[Idx];
1267
1268 if (Op.IsConst) {
1269 MOs.push_back(Elt: Op.MO);
1270 continue;
1271 }
1272
1273 LocIdx MLoc = Op.Loc;
1274 unsigned LocID = LocIdxToLocID[MLoc];
1275 if (LocID >= NumRegs) {
1276 SpillLocationNo SpillID = locIDToSpill(ID: LocID);
1277 StackSlotPos StackIdx = locIDToSpillIdx(ID: LocID);
1278 unsigned short Offset = StackIdx.second;
1279
1280 // TODO: support variables that are located in spill slots, with non-zero
1281 // offsets from the start of the spill slot. It would require some more
1282 // complex DIExpression calculations. This doesn't seem to be produced by
1283 // LLVM right now, so don't try and support it.
1284 // Accept no-subregister slots and subregisters where the offset is zero.
1285 // The consumer should already have type information to work out how large
1286 // the variable is.
1287 if (Offset == 0) {
1288 const SpillLoc &Spill = SpillLocs[SpillID.id()];
1289 unsigned Base = Spill.SpillBase;
1290
1291 // There are several ways we can dereference things, and several inputs
1292 // to consider:
1293 // * NRVO variables will appear with IsIndirect set, but should have
1294 // nothing else in their DIExpressions,
1295 // * Variables with DW_OP_stack_value in their expr already need an
1296 // explicit dereference of the stack location,
1297 // * Values that don't match the variable size need DW_OP_deref_size,
1298 // * Everything else can just become a simple location expression.
1299
1300 // We need to use deref_size whenever there's a mismatch between the
1301 // size of value and the size of variable portion being read.
1302 // Additionally, we should use it whenever dealing with stack_value
1303 // fragments, to avoid the consumer having to determine the deref size
1304 // from DW_OP_piece.
1305 bool UseDerefSize = false;
1306 unsigned ValueSizeInBits = getLocSizeInBits(L: MLoc);
1307 unsigned DerefSizeInBytes = ValueSizeInBits / 8;
1308 if (auto Fragment = Var.getFragment()) {
1309 unsigned VariableSizeInBits = Fragment->SizeInBits;
1310 if (VariableSizeInBits != ValueSizeInBits || Expr->isComplex())
1311 UseDerefSize = true;
1312 } else if (auto Size = Var.getVariable()->getSizeInBits()) {
1313 if (*Size != ValueSizeInBits) {
1314 UseDerefSize = true;
1315 }
1316 }
1317
1318 // https://github.com/llvm/llvm-project/issues/64093
1319 // in particular #issuecomment-2531264124. We use variable locations
1320 // such as DBG_VALUE $xmm0 as shorthand to refer to "the low lane of
1321 // $xmm0", and this is reflected in how DWARF is interpreted too.
1322 // However InstrRefBasedLDV tries to be smart and interprets such a
1323 // DBG_VALUE as a 128-bit reference. We then issue a DW_OP_deref_size
1324 // of 128 bits to the stack, which isn't permitted by DWARF (it's
1325 // larger than a pointer).
1326 //
1327 // Solve this for now by not using DW_OP_deref_size if it would be
1328 // illegal. Instead we'll use DW_OP_deref, and the consumer will load
1329 // the variable type from the stack, which should be correct.
1330 //
1331 // There's still a risk of imprecision when LLVM decides to use
1332 // smaller or larger value types than the source-variable type, which
1333 // manifests as too-little or too-much memory being read from the stack.
1334 // However we can't solve that without putting more type information in
1335 // debug-info.
1336 if (ValueSizeInBits > MF.getDataLayout().getPointerSizeInBits(AS: 0))
1337 UseDerefSize = false;
1338
1339 SmallVector<uint64_t, 5> OffsetOps;
1340 TRI.getOffsetOpcodes(Offset: Spill.SpillOffset, Ops&: OffsetOps);
1341 bool StackValue = false;
1342
1343 if (Properties.Indirect) {
1344 // This is something like an NRVO variable, where the pointer has been
1345 // spilt to the stack. It should end up being a memory location, with
1346 // the pointer to the variable loaded off the stack with a deref:
1347 assert(!Expr->isImplicit());
1348 OffsetOps.push_back(Elt: dwarf::DW_OP_deref);
1349 } else if (UseDerefSize && Expr->isSingleLocationExpression()) {
1350 // TODO: Figure out how to handle deref size issues for variadic
1351 // values.
1352 // We're loading a value off the stack that's not the same size as the
1353 // variable. Add / subtract stack offset, explicitly deref with a
1354 // size, and add DW_OP_stack_value if not already present.
1355 OffsetOps.push_back(Elt: dwarf::DW_OP_deref_size);
1356 OffsetOps.push_back(Elt: DerefSizeInBytes);
1357 StackValue = true;
1358 } else if (Expr->isComplex() || Properties.IsVariadic) {
1359 // A variable with no size ambiguity, but with extra elements in it's
1360 // expression. Manually dereference the stack location.
1361 OffsetOps.push_back(Elt: dwarf::DW_OP_deref);
1362 } else {
1363 // A plain value that has been spilt to the stack, with no further
1364 // context. Request a location expression, marking the DBG_VALUE as
1365 // IsIndirect.
1366 Indirect = true;
1367 }
1368
1369 Expr = DIExpression::appendOpsToArg(Expr, Ops: OffsetOps, ArgNo: Idx, StackValue);
1370 MOs.push_back(Elt: GetRegOp(Base));
1371 } else {
1372 // This is a stack location with a weird subregister offset: emit an
1373 // undef DBG_VALUE instead.
1374 return EmitUndef();
1375 }
1376 } else {
1377 // Non-empty, non-stack slot, must be a plain register.
1378 MOs.push_back(Elt: GetRegOp(LocID));
1379 }
1380 }
1381
1382 return BuildMI(MF, DL, MCID: Desc, IsIndirect: Indirect, MOs, Variable: Var.getVariable(), Expr);
1383}
1384
1385/// Default construct and initialize the pass.
1386InstrRefBasedLDV::InstrRefBasedLDV() = default;
1387
1388bool InstrRefBasedLDV::isCalleeSaved(LocIdx L) const {
1389 unsigned Reg = MTracker->LocIdxToLocID[L];
1390 return isCalleeSavedReg(R: Reg);
1391}
1392bool InstrRefBasedLDV::isCalleeSavedReg(Register R) const {
1393 for (MCRegAliasIterator RAI(R, TRI, true); RAI.isValid(); ++RAI)
1394 if (CalleeSavedRegs.test(Idx: (*RAI).id()))
1395 return true;
1396 return false;
1397}
1398
1399//===----------------------------------------------------------------------===//
1400// Debug Range Extension Implementation
1401//===----------------------------------------------------------------------===//
1402
1403#ifndef NDEBUG
1404// Something to restore in the future.
1405// void InstrRefBasedLDV::printVarLocInMBB(..)
1406#endif
1407
1408std::optional<SpillLocationNo>
1409InstrRefBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
1410 assert(MI.hasOneMemOperand() &&
1411 "Spill instruction does not have exactly one memory operand?");
1412 auto MMOI = MI.memoperands_begin();
1413 const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
1414 assert(PVal->kind() == PseudoSourceValue::FixedStack &&
1415 "Inconsistent memory operand in spill instruction");
1416 int FI = cast<FixedStackPseudoSourceValue>(Val: PVal)->getFrameIndex();
1417 const MachineBasicBlock *MBB = MI.getParent();
1418 Register Reg;
1419 StackOffset Offset = TFI->getFrameIndexReference(MF: *MBB->getParent(), FI, FrameReg&: Reg);
1420 return MTracker->getOrTrackSpillLoc(L: {.SpillBase: Reg, .SpillOffset: Offset});
1421}
1422
1423std::optional<LocIdx>
1424InstrRefBasedLDV::findLocationForMemOperand(const MachineInstr &MI) {
1425 std::optional<SpillLocationNo> SpillLoc = extractSpillBaseRegAndOffset(MI);
1426 if (!SpillLoc)
1427 return std::nullopt;
1428
1429 // Where in the stack slot is this value defined -- i.e., what size of value
1430 // is this? An important question, because it could be loaded into a register
1431 // from the stack at some point. Happily the memory operand will tell us
1432 // the size written to the stack.
1433 auto *MemOperand = *MI.memoperands_begin();
1434 LocationSize SizeInBits = MemOperand->getSizeInBits();
1435 assert(SizeInBits.hasValue() && "Expected to find a valid size!");
1436
1437 // Find that position in the stack indexes we're tracking.
1438 auto IdxIt = MTracker->StackSlotIdxes.find(Val: {SizeInBits.getValue(), 0});
1439 if (IdxIt == MTracker->StackSlotIdxes.end())
1440 // That index is not tracked. This is suprising, and unlikely to ever
1441 // occur, but the safe action is to indicate the variable is optimised out.
1442 return std::nullopt;
1443
1444 unsigned SpillID = MTracker->getSpillIDWithIdx(Spill: *SpillLoc, Idx: IdxIt->second);
1445 return MTracker->getSpillMLoc(SpillID);
1446}
1447
1448/// End all previous ranges related to @MI and start a new range from @MI
1449/// if it is a DBG_VALUE instr.
1450bool InstrRefBasedLDV::transferDebugValue(const MachineInstr &MI) {
1451 if (!MI.isDebugValue())
1452 return false;
1453
1454 assert(MI.getDebugVariable()->isValidLocationForIntrinsic(MI.getDebugLoc()) &&
1455 "Expected inlined-at fields to agree");
1456
1457 // If there are no instructions in this lexical scope, do no location tracking
1458 // at all, this variable shouldn't get a legitimate location range.
1459 auto *Scope = LS.findLexicalScope(DL: MI.getDebugLoc().get());
1460 if (Scope == nullptr)
1461 return true; // handled it; by doing nothing
1462
1463 // MLocTracker needs to know that this register is read, even if it's only
1464 // read by a debug inst.
1465 for (const MachineOperand &MO : MI.debug_operands())
1466 if (MO.isReg() && MO.getReg() != 0)
1467 (void)MTracker->readReg(R: MO.getReg());
1468
1469 // If we're preparing for the second analysis (variables), the machine value
1470 // locations are already solved, and we report this DBG_VALUE and the value
1471 // it refers to to VLocTracker.
1472 if (VTracker) {
1473 SmallVector<DbgOpID> DebugOps;
1474 // Feed defVar the new variable location, or if this is a DBG_VALUE $noreg,
1475 // feed defVar None.
1476 if (!MI.isUndefDebugValue()) {
1477 for (const MachineOperand &MO : MI.debug_operands()) {
1478 // There should be no undef registers here, as we've screened for undef
1479 // debug values.
1480 if (MO.isReg()) {
1481 DebugOps.push_back(Elt: DbgOpStore.insert(Op: MTracker->readReg(R: MO.getReg())));
1482 } else if (MO.isImm() || MO.isFPImm() || MO.isCImm() || MO.isGlobal()) {
1483 DebugOps.push_back(Elt: DbgOpStore.insert(Op: MO));
1484 } else {
1485 llvm_unreachable("Unexpected debug operand type.");
1486 }
1487 }
1488 }
1489 VTracker->defVar(MI, Properties: DbgValueProperties(MI), DebugOps);
1490 }
1491
1492 // If performing final tracking of transfers, report this variable definition
1493 // to the TransferTracker too.
1494 if (TTracker)
1495 TTracker->redefVar(MI);
1496 return true;
1497}
1498
1499std::optional<ValueIDNum> InstrRefBasedLDV::getValueForInstrRef(
1500 unsigned InstNo, unsigned OpNo, MachineInstr &MI,
1501 const FuncValueTable *MLiveOuts, const FuncValueTable *MLiveIns) {
1502 // Various optimizations may have happened to the value during codegen,
1503 // recorded in the value substitution table. Apply any substitutions to
1504 // the instruction / operand number in this DBG_INSTR_REF, and collect
1505 // any subregister extractions performed during optimization.
1506 const MachineFunction &MF = *MI.getParent()->getParent();
1507
1508 // Create dummy substitution with Src set, for lookup.
1509 auto SoughtSub =
1510 MachineFunction::DebugSubstitution({InstNo, OpNo}, {0, 0}, 0);
1511
1512 SmallVector<unsigned, 4> SeenSubregs;
1513 auto LowerBoundIt = llvm::lower_bound(Range: MF.DebugValueSubstitutions, Value&: SoughtSub);
1514 while (LowerBoundIt != MF.DebugValueSubstitutions.end() &&
1515 LowerBoundIt->Src == SoughtSub.Src) {
1516 std::tie(args&: InstNo, args&: OpNo) = LowerBoundIt->Dest;
1517 SoughtSub.Src = LowerBoundIt->Dest;
1518 if (unsigned Subreg = LowerBoundIt->Subreg)
1519 SeenSubregs.push_back(Elt: Subreg);
1520 LowerBoundIt = llvm::lower_bound(Range: MF.DebugValueSubstitutions, Value&: SoughtSub);
1521 }
1522
1523 // Default machine value number is <None> -- if no instruction defines
1524 // the corresponding value, it must have been optimized out.
1525 std::optional<ValueIDNum> NewID;
1526
1527 // Try to lookup the instruction number, and find the machine value number
1528 // that it defines. It could be an instruction, or a PHI.
1529 auto InstrIt = DebugInstrNumToInstr.find(x: InstNo);
1530 auto PHIIt = llvm::lower_bound(Range&: DebugPHINumToValue, Value&: InstNo);
1531 if (InstrIt != DebugInstrNumToInstr.end()) {
1532 const MachineInstr &TargetInstr = *InstrIt->second.first;
1533 uint64_t BlockNo = TargetInstr.getParent()->getNumber();
1534
1535 // Pick out the designated operand. It might be a memory reference, if
1536 // a register def was folded into a stack store.
1537 if (OpNo == MachineFunction::DebugOperandMemNumber &&
1538 TargetInstr.hasOneMemOperand()) {
1539 std::optional<LocIdx> L = findLocationForMemOperand(MI: TargetInstr);
1540 if (L)
1541 NewID = ValueIDNum(BlockNo, InstrIt->second.second, *L);
1542 } else if (OpNo != MachineFunction::DebugOperandMemNumber) {
1543 // Permit the debug-info to be completely wrong: identifying a nonexistant
1544 // operand, or one that is not a register definition, means something
1545 // unexpected happened during optimisation. Broken debug-info, however,
1546 // shouldn't crash the compiler -- instead leave the variable value as
1547 // None, which will make it appear "optimised out".
1548 if (OpNo < TargetInstr.getNumOperands()) {
1549 const MachineOperand &MO = TargetInstr.getOperand(i: OpNo);
1550
1551 if (MO.isReg() && MO.isDef() && MO.getReg()) {
1552 unsigned LocID = MTracker->getLocID(Reg: MO.getReg());
1553 LocIdx L = MTracker->LocIDToLocIdx[LocID];
1554 NewID = ValueIDNum(BlockNo, InstrIt->second.second, L);
1555 }
1556 }
1557
1558 if (!NewID) {
1559 LLVM_DEBUG(
1560 { dbgs() << "Seen instruction reference to illegal operand\n"; });
1561 }
1562 }
1563 // else: NewID is left as None.
1564 } else if (PHIIt != DebugPHINumToValue.end() && PHIIt->InstrNum == InstNo) {
1565 // It's actually a PHI value. Which value it is might not be obvious, use
1566 // the resolver helper to find out.
1567 assert(MLiveOuts && MLiveIns);
1568 NewID = resolveDbgPHIs(MF&: *MI.getParent()->getParent(), MLiveOuts: *MLiveOuts, MLiveIns: *MLiveIns,
1569 Here&: MI, InstrNum: InstNo);
1570 }
1571
1572 // Apply any subregister extractions, in reverse. We might have seen code
1573 // like this:
1574 // CALL64 @foo, implicit-def $rax
1575 // %0:gr64 = COPY $rax
1576 // %1:gr32 = COPY %0.sub_32bit
1577 // %2:gr16 = COPY %1.sub_16bit
1578 // %3:gr8 = COPY %2.sub_8bit
1579 // In which case each copy would have been recorded as a substitution with
1580 // a subregister qualifier. Apply those qualifiers now.
1581 if (NewID && !SeenSubregs.empty()) {
1582 unsigned Offset = 0;
1583 unsigned Size = 0;
1584
1585 // Look at each subregister that we passed through, and progressively
1586 // narrow in, accumulating any offsets that occur. Substitutions should
1587 // only ever be the same or narrower width than what they read from;
1588 // iterate in reverse order so that we go from wide to small.
1589 for (unsigned Subreg : reverse(C&: SeenSubregs)) {
1590 unsigned ThisSize = TRI->getSubRegIdxSize(Idx: Subreg);
1591 unsigned ThisOffset = TRI->getSubRegIdxOffset(Idx: Subreg);
1592 Offset += ThisOffset;
1593 Size = (Size == 0) ? ThisSize : std::min(a: Size, b: ThisSize);
1594 }
1595
1596 // If that worked, look for an appropriate subregister with the register
1597 // where the define happens. Don't look at values that were defined during
1598 // a stack write: we can't currently express register locations within
1599 // spills.
1600 LocIdx L = NewID->getLoc();
1601 if (NewID && !MTracker->isSpill(Idx: L)) {
1602 // Find the register class for the register where this def happened.
1603 // FIXME: no index for this?
1604 Register Reg = MTracker->LocIdxToLocID[L];
1605 const TargetRegisterClass *TRC = nullptr;
1606 for (const auto &TRCI : TRI->regclasses())
1607 if (TRCI.contains(Reg))
1608 TRC = &TRCI;
1609 assert(TRC && "Couldn't find target register class?");
1610
1611 // If the register we have isn't the right size or in the right place,
1612 // Try to find a subregister inside it.
1613 unsigned MainRegSize = TRI->getRegSizeInBits(RC: *TRC);
1614 if (Size != MainRegSize || Offset) {
1615 // Enumerate all subregisters, searching.
1616 Register NewReg = Register();
1617 for (MCRegister SR : TRI->subregs(Reg)) {
1618 unsigned Subreg = TRI->getSubRegIndex(RegNo: Reg, SubRegNo: SR);
1619 unsigned SubregSize = TRI->getSubRegIdxSize(Idx: Subreg);
1620 unsigned SubregOffset = TRI->getSubRegIdxOffset(Idx: Subreg);
1621 if (SubregSize == Size && SubregOffset == Offset) {
1622 NewReg = SR;
1623 break;
1624 }
1625 }
1626
1627 // If we didn't find anything: there's no way to express our value.
1628 if (!NewReg) {
1629 NewID = std::nullopt;
1630 } else {
1631 // Re-state the value as being defined within the subregister
1632 // that we found.
1633 LocIdx NewLoc =
1634 MTracker->lookupOrTrackRegister(ID: MTracker->getLocID(Reg: NewReg));
1635 NewID = ValueIDNum(NewID->getBlock(), NewID->getInst(), NewLoc);
1636 }
1637 }
1638 } else {
1639 // If we can't handle subregisters, unset the new value.
1640 NewID = std::nullopt;
1641 }
1642 }
1643
1644 return NewID;
1645}
1646
1647bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI,
1648 const FuncValueTable *MLiveOuts,
1649 const FuncValueTable *MLiveIns) {
1650 if (!MI.isDebugRef())
1651 return false;
1652
1653 // Only handle this instruction when we are building the variable value
1654 // transfer function.
1655 if (!VTracker && !TTracker)
1656 return false;
1657
1658 const DILocalVariable *Var = MI.getDebugVariable();
1659 const DIExpression *Expr = MI.getDebugExpression();
1660 const DILocation *DebugLoc = MI.getDebugLoc();
1661 const DILocation *InlinedAt = DebugLoc->getInlinedAt();
1662 assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
1663 "Expected inlined-at fields to agree");
1664
1665 DebugVariable V(Var, Expr, InlinedAt);
1666
1667 auto *Scope = LS.findLexicalScope(DL: MI.getDebugLoc().get());
1668 if (Scope == nullptr)
1669 return true; // Handled by doing nothing. This variable is never in scope.
1670
1671 SmallVector<DbgOpID> DbgOpIDs;
1672 for (const MachineOperand &MO : MI.debug_operands()) {
1673 if (!MO.isDbgInstrRef()) {
1674 assert(!MO.isReg() && "DBG_INSTR_REF should not contain registers");
1675 DbgOpID ConstOpID = DbgOpStore.insert(Op: DbgOp(MO));
1676 DbgOpIDs.push_back(Elt: ConstOpID);
1677 continue;
1678 }
1679
1680 unsigned InstNo = MO.getInstrRefInstrIndex();
1681 unsigned OpNo = MO.getInstrRefOpIndex();
1682
1683 // Default machine value number is <None> -- if no instruction defines
1684 // the corresponding value, it must have been optimized out.
1685 std::optional<ValueIDNum> NewID =
1686 getValueForInstrRef(InstNo, OpNo, MI, MLiveOuts, MLiveIns);
1687 // We have a value number or std::nullopt. If the latter, then kill the
1688 // entire debug value.
1689 if (NewID) {
1690 DbgOpIDs.push_back(Elt: DbgOpStore.insert(Op: *NewID));
1691 } else {
1692 DbgOpIDs.clear();
1693 break;
1694 }
1695 }
1696
1697 // We have a DbgOpID for every value or for none. Tell the variable value
1698 // tracker about it. The rest of this LiveDebugValues implementation acts
1699 // exactly the same for DBG_INSTR_REFs as DBG_VALUEs (just, the former can
1700 // refer to values that aren't immediately available).
1701 DbgValueProperties Properties(Expr, false, true);
1702 if (VTracker)
1703 VTracker->defVar(MI, Properties, DebugOps: DbgOpIDs);
1704
1705 // If we're on the final pass through the function, decompose this INSTR_REF
1706 // into a plain DBG_VALUE.
1707 if (!TTracker)
1708 return true;
1709
1710 // Fetch the concrete DbgOps now, as we will need them later.
1711 SmallVector<DbgOp> DbgOps;
1712 for (DbgOpID OpID : DbgOpIDs) {
1713 DbgOps.push_back(Elt: DbgOpStore.find(ID: OpID));
1714 }
1715
1716 // Pick a location for the machine value number, if such a location exists.
1717 // (This information could be stored in TransferTracker to make it faster).
1718 SmallDenseMap<ValueIDNum, TransferTracker::LocationAndQuality> FoundLocs;
1719 SmallVector<ValueIDNum> ValuesToFind;
1720 // Initialized the preferred-location map with illegal locations, to be
1721 // filled in later.
1722 for (const DbgOp &Op : DbgOps) {
1723 if (!Op.IsConst)
1724 if (FoundLocs.try_emplace(Key: Op.ID).second)
1725 ValuesToFind.push_back(Elt: Op.ID);
1726 }
1727
1728 for (auto Location : MTracker->locations()) {
1729 LocIdx CurL = Location.Idx;
1730 ValueIDNum ID = MTracker->readMLoc(L: CurL);
1731 auto ValueToFindIt = find(Range&: ValuesToFind, Val: ID);
1732 if (ValueToFindIt == ValuesToFind.end())
1733 continue;
1734 auto &Previous = FoundLocs.find(Val: ID)->second;
1735 // If this is the first location with that value, pick it. Otherwise,
1736 // consider whether it's a "longer term" location.
1737 std::optional<TransferTracker::LocationQuality> ReplacementQuality =
1738 TTracker->getLocQualityIfBetter(L: CurL, Min: Previous.getQuality());
1739 if (ReplacementQuality) {
1740 Previous = TransferTracker::LocationAndQuality(CurL, *ReplacementQuality);
1741 if (Previous.isBest()) {
1742 ValuesToFind.erase(CI: ValueToFindIt);
1743 if (ValuesToFind.empty())
1744 break;
1745 }
1746 }
1747 }
1748
1749 SmallVector<ResolvedDbgOp> NewLocs;
1750 for (const DbgOp &DbgOp : DbgOps) {
1751 if (DbgOp.IsConst) {
1752 NewLocs.push_back(Elt: DbgOp.MO);
1753 continue;
1754 }
1755 LocIdx FoundLoc = FoundLocs.find(Val: DbgOp.ID)->second.getLoc();
1756 if (FoundLoc.isIllegal()) {
1757 NewLocs.clear();
1758 break;
1759 }
1760 NewLocs.push_back(Elt: FoundLoc);
1761 }
1762 // Tell transfer tracker that the variable value has changed.
1763 TTracker->redefVar(MI, Properties, NewLocs);
1764
1765 // If there were values with no location, but all such values are defined in
1766 // later instructions in this block, this is a block-local use-before-def.
1767 if (!DbgOps.empty() && NewLocs.empty()) {
1768 bool IsValidUseBeforeDef = true;
1769 uint64_t LastUseBeforeDef = 0;
1770 for (auto ValueLoc : FoundLocs) {
1771 ValueIDNum NewID = ValueLoc.first;
1772 LocIdx FoundLoc = ValueLoc.second.getLoc();
1773 if (!FoundLoc.isIllegal())
1774 continue;
1775 // If we have an value with no location that is not defined in this block,
1776 // then it has no location in this block, leaving this value undefined.
1777 if (NewID.getBlock() != CurBB || NewID.getInst() <= CurInst) {
1778 IsValidUseBeforeDef = false;
1779 break;
1780 }
1781 LastUseBeforeDef = std::max(a: LastUseBeforeDef, b: NewID.getInst());
1782 }
1783 if (IsValidUseBeforeDef) {
1784 DebugVariableID VID = DVMap.insertDVID(Var&: V, Loc: MI.getDebugLoc().get());
1785 TTracker->addUseBeforeDef(VarID: VID, Properties: {MI.getDebugExpression(), false, true},
1786 DbgOps, Inst: LastUseBeforeDef);
1787 }
1788 }
1789
1790 // Produce a DBG_VALUE representing what this DBG_INSTR_REF meant.
1791 // This DBG_VALUE is potentially a $noreg / undefined location, if
1792 // FoundLoc is illegal.
1793 // (XXX -- could morph the DBG_INSTR_REF in the future).
1794 MachineInstr *DbgMI =
1795 MTracker->emitLoc(DbgOps: NewLocs, Var: V, DILoc: MI.getDebugLoc().get(), Properties);
1796 DebugVariableID ID = DVMap.getDVID(Var: V);
1797
1798 TTracker->PendingDbgValues.push_back(Elt: std::make_pair(x&: ID, y&: DbgMI));
1799 TTracker->flushDbgValues(Pos: MI.getIterator(), MBB: nullptr);
1800 return true;
1801}
1802
1803bool InstrRefBasedLDV::transferDebugPHI(MachineInstr &MI) {
1804 if (!MI.isDebugPHI())
1805 return false;
1806
1807 // Analyse these only when solving the machine value location problem.
1808 if (VTracker || TTracker)
1809 return true;
1810
1811 // First operand is the value location, either a stack slot or register.
1812 // Second is the debug instruction number of the original PHI.
1813 const MachineOperand &MO = MI.getOperand(i: 0);
1814 unsigned InstrNum = MI.getOperand(i: 1).getImm();
1815
1816 auto EmitBadPHI = [this, &MI, InstrNum]() -> bool {
1817 // Helper lambda to do any accounting when we fail to find a location for
1818 // a DBG_PHI. This can happen if DBG_PHIs are malformed, or refer to a
1819 // dead stack slot, for example.
1820 // Record a DebugPHIRecord with an empty value + location.
1821 DebugPHINumToValue.push_back(
1822 Elt: {.InstrNum: InstrNum, .MBB: MI.getParent(), .ValueRead: std::nullopt, .ReadLoc: std::nullopt});
1823 return true;
1824 };
1825
1826 if (MO.isReg() && MO.getReg()) {
1827 // The value is whatever's currently in the register. Read and record it,
1828 // to be analysed later.
1829 Register Reg = MO.getReg();
1830 ValueIDNum Num = MTracker->readReg(R: Reg);
1831 auto PHIRec = DebugPHIRecord(
1832 {.InstrNum: InstrNum, .MBB: MI.getParent(), .ValueRead: Num,
1833 .ReadLoc: MTracker->lookupOrTrackRegister(ID: MTracker->getLocID(Reg))});
1834 DebugPHINumToValue.push_back(Elt: PHIRec);
1835
1836 // Ensure this register is tracked.
1837 for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
1838 MTracker->lookupOrTrackRegister(ID: MTracker->getLocID(Reg: *RAI));
1839 } else if (MO.isFI()) {
1840 // The value is whatever's in this stack slot.
1841 unsigned FI = MO.getIndex();
1842
1843 // If the stack slot is dead, then this was optimized away.
1844 // FIXME: stack slot colouring should account for slots that get merged.
1845 if (MFI->isDeadObjectIndex(ObjectIdx: FI))
1846 return EmitBadPHI();
1847
1848 // Identify this spill slot, ensure it's tracked.
1849 Register Base;
1850 StackOffset Offs = TFI->getFrameIndexReference(MF: *MI.getMF(), FI, FrameReg&: Base);
1851 SpillLoc SL = {.SpillBase: Base, .SpillOffset: Offs};
1852 std::optional<SpillLocationNo> SpillNo = MTracker->getOrTrackSpillLoc(L: SL);
1853
1854 // We might be able to find a value, but have chosen not to, to avoid
1855 // tracking too much stack information.
1856 if (!SpillNo)
1857 return EmitBadPHI();
1858
1859 // Any stack location DBG_PHI should have an associate bit-size.
1860 assert(MI.getNumOperands() == 3 && "Stack DBG_PHI with no size?");
1861 unsigned slotBitSize = MI.getOperand(i: 2).getImm();
1862
1863 unsigned SpillID = MTracker->getLocID(Spill: *SpillNo, Idx: {slotBitSize, 0});
1864 LocIdx SpillLoc = MTracker->getSpillMLoc(SpillID);
1865 ValueIDNum Result = MTracker->readMLoc(L: SpillLoc);
1866
1867 // Record this DBG_PHI for later analysis.
1868 auto DbgPHI = DebugPHIRecord({.InstrNum: InstrNum, .MBB: MI.getParent(), .ValueRead: Result, .ReadLoc: SpillLoc});
1869 DebugPHINumToValue.push_back(Elt: DbgPHI);
1870 } else {
1871 // Else: if the operand is neither a legal register or a stack slot, then
1872 // we're being fed illegal debug-info. Record an empty PHI, so that any
1873 // debug users trying to read this number will be put off trying to
1874 // interpret the value.
1875 LLVM_DEBUG(
1876 { dbgs() << "Seen DBG_PHI with unrecognised operand format\n"; });
1877 return EmitBadPHI();
1878 }
1879
1880 return true;
1881}
1882
1883void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) {
1884 // Meta Instructions do not affect the debug liveness of any register they
1885 // define.
1886 if (MI.isImplicitDef()) {
1887 // Except when there's an implicit def, and the location it's defining has
1888 // no value number. The whole point of an implicit def is to announce that
1889 // the register is live, without be specific about it's value. So define
1890 // a value if there isn't one already.
1891 ValueIDNum Num = MTracker->readReg(R: MI.getOperand(i: 0).getReg());
1892 // Has a legitimate value -> ignore the implicit def.
1893 if (Num.getLoc() != 0)
1894 return;
1895 // Otherwise, def it here.
1896 } else if (MI.isMetaInstruction())
1897 return;
1898
1899 // We always ignore SP defines on call instructions, they don't actually
1900 // change the value of the stack pointer... except for win32's _chkstk. This
1901 // is rare: filter quickly for the common case (no stack adjustments, not a
1902 // call, etc). If it is a call that modifies SP, recognise the SP register
1903 // defs.
1904 bool CallChangesSP = false;
1905 if (AdjustsStackInCalls && MI.isCall() && MI.getOperand(i: 0).isSymbol() &&
1906 !strcmp(s1: MI.getOperand(i: 0).getSymbolName(), s2: StackProbeSymbolName.data()))
1907 CallChangesSP = true;
1908
1909 // Test whether we should ignore a def of this register due to it being part
1910 // of the stack pointer.
1911 auto IgnoreSPAlias = [this, &MI, CallChangesSP](Register R) -> bool {
1912 if (CallChangesSP)
1913 return false;
1914 return MI.isCall() && MTracker->SPAliases.count(V: R);
1915 };
1916
1917 // Find the regs killed by MI, and find regmasks of preserved regs.
1918 // Max out the number of statically allocated elements in `DeadRegs`, as this
1919 // prevents fallback to std::set::count() operations.
1920 SmallSet<uint32_t, 32> DeadRegs;
1921 SmallVector<const uint32_t *, 4> RegMasks;
1922 SmallVector<const MachineOperand *, 4> RegMaskPtrs;
1923 for (const MachineOperand &MO : MI.operands()) {
1924 // Determine whether the operand is a register def.
1925 if (MO.isReg() && MO.isDef() && MO.getReg() && MO.getReg().isPhysical() &&
1926 !IgnoreSPAlias(MO.getReg())) {
1927 // Remove ranges of all aliased registers.
1928 for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
1929 // FIXME: Can we break out of this loop early if no insertion occurs?
1930 DeadRegs.insert(V: (*RAI).id());
1931 } else if (MO.isRegMask()) {
1932 RegMasks.push_back(Elt: MO.getRegMask());
1933 RegMaskPtrs.push_back(Elt: &MO);
1934 }
1935 }
1936
1937 // Tell MLocTracker about all definitions, of regmasks and otherwise.
1938 for (uint32_t DeadReg : DeadRegs)
1939 MTracker->defReg(R: DeadReg, BB: CurBB, Inst: CurInst);
1940
1941 for (const auto *MO : RegMaskPtrs)
1942 MTracker->writeRegMask(MO, CurBB, InstID: CurInst);
1943
1944 // If this instruction writes to a spill slot, def that slot.
1945 if (hasFoldedStackStore(MI)) {
1946 if (std::optional<SpillLocationNo> SpillNo =
1947 extractSpillBaseRegAndOffset(MI)) {
1948 for (unsigned int I = 0; I < MTracker->NumSlotIdxes; ++I) {
1949 unsigned SpillID = MTracker->getSpillIDWithIdx(Spill: *SpillNo, Idx: I);
1950 LocIdx L = MTracker->getSpillMLoc(SpillID);
1951 MTracker->setMLoc(L, Num: ValueIDNum(CurBB, CurInst, L));
1952 }
1953 }
1954 }
1955
1956 if (!TTracker)
1957 return;
1958
1959 // When committing variable values to locations: tell transfer tracker that
1960 // we've clobbered things. It may be able to recover the variable from a
1961 // different location.
1962
1963 // Inform TTracker about any direct clobbers.
1964 for (MCRegister DeadReg : DeadRegs) {
1965 LocIdx Loc = MTracker->lookupOrTrackRegister(ID: MTracker->getLocID(Reg: DeadReg));
1966 TTracker->clobberMloc(MLoc: Loc, Pos: MI.getIterator(), MakeUndef: false);
1967 }
1968
1969 // Look for any clobbers performed by a register mask. Only test locations
1970 // that are actually being tracked.
1971 if (!RegMaskPtrs.empty()) {
1972 for (auto L : MTracker->locations()) {
1973 // Stack locations can't be clobbered by regmasks.
1974 if (MTracker->isSpill(Idx: L.Idx))
1975 continue;
1976
1977 Register Reg = MTracker->LocIdxToLocID[L.Idx];
1978 if (IgnoreSPAlias(Reg))
1979 continue;
1980
1981 for (const auto *MO : RegMaskPtrs)
1982 if (MO->clobbersPhysReg(PhysReg: Reg))
1983 TTracker->clobberMloc(MLoc: L.Idx, Pos: MI.getIterator(), MakeUndef: false);
1984 }
1985 }
1986
1987 // Tell TTracker about any folded stack store.
1988 if (hasFoldedStackStore(MI)) {
1989 if (std::optional<SpillLocationNo> SpillNo =
1990 extractSpillBaseRegAndOffset(MI)) {
1991 for (unsigned int I = 0; I < MTracker->NumSlotIdxes; ++I) {
1992 unsigned SpillID = MTracker->getSpillIDWithIdx(Spill: *SpillNo, Idx: I);
1993 LocIdx L = MTracker->getSpillMLoc(SpillID);
1994 TTracker->clobberMloc(MLoc: L, Pos: MI.getIterator(), MakeUndef: true);
1995 }
1996 }
1997 }
1998}
1999
2000void InstrRefBasedLDV::performCopy(Register SrcRegNum, Register DstRegNum) {
2001 // In all circumstances, re-def all aliases. It's definitely a new value now.
2002 for (MCRegAliasIterator RAI(DstRegNum, TRI, true); RAI.isValid(); ++RAI)
2003 MTracker->defReg(R: *RAI, BB: CurBB, Inst: CurInst);
2004
2005 ValueIDNum SrcValue = MTracker->readReg(R: SrcRegNum);
2006 MTracker->setReg(R: DstRegNum, ValueID: SrcValue);
2007
2008 // Copy subregisters from one location to another.
2009 for (MCSubRegIndexIterator SRI(SrcRegNum, TRI); SRI.isValid(); ++SRI) {
2010 MCRegister SrcSubReg = SRI.getSubReg();
2011 unsigned SubRegIdx = SRI.getSubRegIndex();
2012 MCRegister DstSubReg = TRI->getSubReg(Reg: DstRegNum, Idx: SubRegIdx);
2013 if (!DstSubReg)
2014 continue;
2015
2016 // Do copy. There are two matching subregisters, the source value should
2017 // have been def'd when the super-reg was, the latter might not be tracked
2018 // yet.
2019 // This will force SrcSubReg to be tracked, if it isn't yet. Will read
2020 // mphi values if it wasn't tracked.
2021 LocIdx SrcL =
2022 MTracker->lookupOrTrackRegister(ID: MTracker->getLocID(Reg: SrcSubReg));
2023 LocIdx DstL =
2024 MTracker->lookupOrTrackRegister(ID: MTracker->getLocID(Reg: DstSubReg));
2025 (void)SrcL;
2026 (void)DstL;
2027 ValueIDNum CpyValue = MTracker->readReg(R: SrcSubReg);
2028
2029 MTracker->setReg(R: DstSubReg, ValueID: CpyValue);
2030 }
2031}
2032
2033std::optional<SpillLocationNo>
2034InstrRefBasedLDV::isSpillInstruction(const MachineInstr &MI,
2035 MachineFunction *MF) {
2036 // TODO: Handle multiple stores folded into one.
2037 if (!MI.hasOneMemOperand())
2038 return std::nullopt;
2039
2040 // Reject any memory operand that's aliased -- we can't guarantee its value.
2041 auto MMOI = MI.memoperands_begin();
2042 const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
2043 if (PVal->isAliased(MFI))
2044 return std::nullopt;
2045
2046 if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII))
2047 return std::nullopt; // This is not a spill instruction, since no valid size
2048 // was returned from either function.
2049
2050 return extractSpillBaseRegAndOffset(MI);
2051}
2052
2053bool InstrRefBasedLDV::isLocationSpill(const MachineInstr &MI,
2054 MachineFunction *MF, unsigned &Reg) {
2055 if (!isSpillInstruction(MI, MF))
2056 return false;
2057
2058 int FI;
2059 Reg = TII->isStoreToStackSlotPostFE(MI, FrameIndex&: FI);
2060 return Reg != 0;
2061}
2062
2063std::optional<SpillLocationNo>
2064InstrRefBasedLDV::isRestoreInstruction(const MachineInstr &MI,
2065 MachineFunction *MF, unsigned &Reg) {
2066 if (!MI.hasOneMemOperand())
2067 return std::nullopt;
2068
2069 // FIXME: Handle folded restore instructions with more than one memory
2070 // operand.
2071 if (MI.getRestoreSize(TII)) {
2072 Reg = MI.getOperand(i: 0).getReg();
2073 return extractSpillBaseRegAndOffset(MI);
2074 }
2075 return std::nullopt;
2076}
2077
2078bool InstrRefBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI) {
2079 // XXX -- it's too difficult to implement VarLocBasedImpl's stack location
2080 // limitations under the new model. Therefore, when comparing them, compare
2081 // versions that don't attempt spills or restores at all.
2082 if (EmulateOldLDV)
2083 return false;
2084
2085 // Strictly limit ourselves to plain loads and stores, not all instructions
2086 // that can access the stack.
2087 int DummyFI = -1;
2088 if (!TII->isStoreToStackSlotPostFE(MI, FrameIndex&: DummyFI) &&
2089 !TII->isLoadFromStackSlotPostFE(MI, FrameIndex&: DummyFI))
2090 return false;
2091
2092 MachineFunction *MF = MI.getMF();
2093 unsigned Reg;
2094
2095 LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump(););
2096
2097 // Strictly limit ourselves to plain loads and stores, not all instructions
2098 // that can access the stack.
2099 int FIDummy;
2100 if (!TII->isStoreToStackSlotPostFE(MI, FrameIndex&: FIDummy) &&
2101 !TII->isLoadFromStackSlotPostFE(MI, FrameIndex&: FIDummy))
2102 return false;
2103
2104 // First, if there are any DBG_VALUEs pointing at a spill slot that is
2105 // written to, terminate that variable location. The value in memory
2106 // will have changed. DbgEntityHistoryCalculator doesn't try to detect this.
2107 if (std::optional<SpillLocationNo> Loc = isSpillInstruction(MI, MF)) {
2108 // Un-set this location and clobber, so that earlier locations don't
2109 // continue past this store.
2110 for (unsigned SlotIdx = 0; SlotIdx < MTracker->NumSlotIdxes; ++SlotIdx) {
2111 unsigned SpillID = MTracker->getSpillIDWithIdx(Spill: *Loc, Idx: SlotIdx);
2112 std::optional<LocIdx> MLoc = MTracker->getSpillMLoc(SpillID);
2113 if (!MLoc)
2114 continue;
2115
2116 // We need to over-write the stack slot with something (here, a def at
2117 // this instruction) to ensure no values are preserved in this stack slot
2118 // after the spill. It also prevents TTracker from trying to recover the
2119 // location and re-installing it in the same place.
2120 ValueIDNum Def(CurBB, CurInst, *MLoc);
2121 MTracker->setMLoc(L: *MLoc, Num: Def);
2122 if (TTracker)
2123 TTracker->clobberMloc(MLoc: *MLoc, Pos: MI.getIterator());
2124 }
2125 }
2126
2127 // Try to recognise spill and restore instructions that may transfer a value.
2128 if (isLocationSpill(MI, MF, Reg)) {
2129 // isLocationSpill returning true should guarantee we can extract a
2130 // location.
2131 SpillLocationNo Loc = *extractSpillBaseRegAndOffset(MI);
2132
2133 auto DoTransfer = [&](Register SrcReg, unsigned SpillID) {
2134 auto ReadValue = MTracker->readReg(R: SrcReg);
2135 LocIdx DstLoc = MTracker->getSpillMLoc(SpillID);
2136 MTracker->setMLoc(L: DstLoc, Num: ReadValue);
2137
2138 if (TTracker) {
2139 LocIdx SrcLoc = MTracker->getRegMLoc(R: SrcReg);
2140 TTracker->transferMlocs(Src: SrcLoc, Dst: DstLoc, Pos: MI.getIterator());
2141 }
2142 };
2143
2144 // Then, transfer subreg bits.
2145 for (MCPhysReg SR : TRI->subregs(Reg)) {
2146 // Ensure this reg is tracked,
2147 (void)MTracker->lookupOrTrackRegister(ID: MTracker->getLocID(Reg: SR));
2148 unsigned SubregIdx = TRI->getSubRegIndex(RegNo: Reg, SubRegNo: SR);
2149 unsigned SpillID = MTracker->getLocID(Spill: Loc, SpillSubReg: SubregIdx);
2150 DoTransfer(SR, SpillID);
2151 }
2152
2153 // Directly lookup size of main source reg, and transfer.
2154 unsigned Size = TRI->getRegSizeInBits(Reg, MRI: *MRI);
2155 unsigned SpillID = MTracker->getLocID(Spill: Loc, Idx: {Size, 0});
2156 DoTransfer(Reg, SpillID);
2157 } else {
2158 std::optional<SpillLocationNo> Loc = isRestoreInstruction(MI, MF, Reg);
2159 if (!Loc)
2160 return false;
2161
2162 // Assumption: we're reading from the base of the stack slot, not some
2163 // offset into it. It seems very unlikely LLVM would ever generate
2164 // restores where this wasn't true. This then becomes a question of what
2165 // subregisters in the destination register line up with positions in the
2166 // stack slot.
2167
2168 // Def all registers that alias the destination.
2169 for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
2170 MTracker->defReg(R: *RAI, BB: CurBB, Inst: CurInst);
2171
2172 // Now find subregisters within the destination register, and load values
2173 // from stack slot positions.
2174 auto DoTransfer = [&](Register DestReg, unsigned SpillID) {
2175 LocIdx SrcIdx = MTracker->getSpillMLoc(SpillID);
2176 auto ReadValue = MTracker->readMLoc(L: SrcIdx);
2177 MTracker->setReg(R: DestReg, ValueID: ReadValue);
2178 };
2179
2180 for (MCPhysReg SR : TRI->subregs(Reg)) {
2181 unsigned Subreg = TRI->getSubRegIndex(RegNo: Reg, SubRegNo: SR);
2182 unsigned SpillID = MTracker->getLocID(Spill: *Loc, SpillSubReg: Subreg);
2183 DoTransfer(SR, SpillID);
2184 }
2185
2186 // Directly look up this registers slot idx by size, and transfer.
2187 unsigned Size = TRI->getRegSizeInBits(Reg, MRI: *MRI);
2188 unsigned SpillID = MTracker->getLocID(Spill: *Loc, Idx: {Size, 0});
2189 DoTransfer(Reg, SpillID);
2190 }
2191 return true;
2192}
2193
2194bool InstrRefBasedLDV::transferRegisterCopy(MachineInstr &MI) {
2195 auto DestSrc = TII->isCopyLikeInstr(MI);
2196 if (!DestSrc)
2197 return false;
2198
2199 const MachineOperand *DestRegOp = DestSrc->Destination;
2200 const MachineOperand *SrcRegOp = DestSrc->Source;
2201
2202 Register SrcReg = SrcRegOp->getReg();
2203 Register DestReg = DestRegOp->getReg();
2204
2205 // Ignore identity copies. Yep, these make it as far as LiveDebugValues.
2206 if (SrcReg == DestReg)
2207 return true;
2208
2209 // For emulating VarLocBasedImpl:
2210 // We want to recognize instructions where destination register is callee
2211 // saved register. If register that could be clobbered by the call is
2212 // included, there would be a great chance that it is going to be clobbered
2213 // soon. It is more likely that previous register, which is callee saved, is
2214 // going to stay unclobbered longer, even if it is killed.
2215 //
2216 // For InstrRefBasedImpl, we can track multiple locations per value, so
2217 // ignore this condition.
2218 if (EmulateOldLDV && !isCalleeSavedReg(R: DestReg))
2219 return false;
2220
2221 // InstrRefBasedImpl only followed killing copies.
2222 if (EmulateOldLDV && !SrcRegOp->isKill())
2223 return false;
2224
2225 // Before we update MTracker, remember which values were present in each of
2226 // the locations about to be overwritten, so that we can recover any
2227 // potentially clobbered variables.
2228 DenseMap<LocIdx, ValueIDNum> ClobberedLocs;
2229 if (TTracker) {
2230 for (MCRegAliasIterator RAI(DestReg, TRI, true); RAI.isValid(); ++RAI) {
2231 LocIdx ClobberedLoc = MTracker->getRegMLoc(R: *RAI);
2232 auto MLocIt = TTracker->ActiveMLocs.find(Val: ClobberedLoc);
2233 // If ActiveMLocs isn't tracking this location or there are no variables
2234 // using it, don't bother remembering.
2235 if (MLocIt == TTracker->ActiveMLocs.end() || MLocIt->second.empty())
2236 continue;
2237 ValueIDNum Value = MTracker->readReg(R: *RAI);
2238 ClobberedLocs[ClobberedLoc] = Value;
2239 }
2240 }
2241
2242 // Copy MTracker info, including subregs if available.
2243 InstrRefBasedLDV::performCopy(SrcRegNum: SrcReg, DstRegNum: DestReg);
2244
2245 // The copy might have clobbered variables based on the destination register.
2246 // Tell TTracker about it, passing the old ValueIDNum to search for
2247 // alternative locations (or else terminating those variables).
2248 if (TTracker) {
2249 for (auto LocVal : ClobberedLocs) {
2250 TTracker->clobberMloc(MLoc: LocVal.first, OldValue: LocVal.second, Pos: MI.getIterator(), MakeUndef: false);
2251 }
2252 }
2253
2254 // Only produce a transfer of DBG_VALUE within a block where old LDV
2255 // would have. We might make use of the additional value tracking in some
2256 // other way, later.
2257 if (TTracker && isCalleeSavedReg(R: DestReg) && SrcRegOp->isKill())
2258 TTracker->transferMlocs(Src: MTracker->getRegMLoc(R: SrcReg),
2259 Dst: MTracker->getRegMLoc(R: DestReg), Pos: MI.getIterator());
2260
2261 // VarLocBasedImpl would quit tracking the old location after copying.
2262 if (EmulateOldLDV && SrcReg != DestReg)
2263 MTracker->defReg(R: SrcReg, BB: CurBB, Inst: CurInst);
2264
2265 return true;
2266}
2267
2268/// Accumulate a mapping between each DILocalVariable fragment and other
2269/// fragments of that DILocalVariable which overlap. This reduces work during
2270/// the data-flow stage from "Find any overlapping fragments" to "Check if the
2271/// known-to-overlap fragments are present".
2272/// \param MI A previously unprocessed debug instruction to analyze for
2273/// fragment usage.
2274void InstrRefBasedLDV::accumulateFragmentMap(MachineInstr &MI) {
2275 assert(MI.isDebugValueLike());
2276 DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(),
2277 MI.getDebugLoc()->getInlinedAt());
2278 FragmentInfo ThisFragment = MIVar.getFragmentOrDefault();
2279
2280 // If this is the first sighting of this variable, then we are guaranteed
2281 // there are currently no overlapping fragments either. Initialize the set
2282 // of seen fragments, record no overlaps for the current one, and return.
2283 auto [SeenIt, Inserted] = SeenFragments.try_emplace(Key: MIVar.getVariable());
2284 if (Inserted) {
2285 SeenIt->second.insert(V: ThisFragment);
2286
2287 OverlapFragments.insert(KV: {{MIVar.getVariable(), ThisFragment}, {}});
2288 return;
2289 }
2290
2291 // If this particular Variable/Fragment pair already exists in the overlap
2292 // map, it has already been accounted for.
2293 auto IsInOLapMap =
2294 OverlapFragments.insert(KV: {{MIVar.getVariable(), ThisFragment}, {}});
2295 if (!IsInOLapMap.second)
2296 return;
2297
2298 auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;
2299 auto &AllSeenFragments = SeenIt->second;
2300
2301 // Otherwise, examine all other seen fragments for this variable, with "this"
2302 // fragment being a previously unseen fragment. Record any pair of
2303 // overlapping fragments.
2304 for (const auto &ASeenFragment : AllSeenFragments) {
2305 // Does this previously seen fragment overlap?
2306 if (DIExpression::fragmentsOverlap(A: ThisFragment, B: ASeenFragment)) {
2307 // Yes: Mark the current fragment as being overlapped.
2308 ThisFragmentsOverlaps.push_back(Elt: ASeenFragment);
2309 // Mark the previously seen fragment as being overlapped by the current
2310 // one.
2311 auto ASeenFragmentsOverlaps =
2312 OverlapFragments.find(Val: {MIVar.getVariable(), ASeenFragment});
2313 assert(ASeenFragmentsOverlaps != OverlapFragments.end() &&
2314 "Previously seen var fragment has no vector of overlaps");
2315 ASeenFragmentsOverlaps->second.push_back(Elt: ThisFragment);
2316 }
2317 }
2318
2319 AllSeenFragments.insert(V: ThisFragment);
2320}
2321
2322void InstrRefBasedLDV::process(MachineInstr &MI,
2323 const FuncValueTable *MLiveOuts,
2324 const FuncValueTable *MLiveIns) {
2325 // Try to interpret an MI as a debug or transfer instruction. Only if it's
2326 // none of these should we interpret it's register defs as new value
2327 // definitions.
2328 if (transferDebugValue(MI))
2329 return;
2330 if (transferDebugInstrRef(MI, MLiveOuts, MLiveIns))
2331 return;
2332 if (transferDebugPHI(MI))
2333 return;
2334 if (transferRegisterCopy(MI))
2335 return;
2336 if (transferSpillOrRestoreInst(MI))
2337 return;
2338 transferRegisterDef(MI);
2339}
2340
2341void InstrRefBasedLDV::produceMLocTransferFunction(
2342 MachineFunction &MF, SmallVectorImpl<MLocTransferMap> &MLocTransfer,
2343 unsigned MaxNumBlocks) {
2344 // Because we try to optimize around register mask operands by ignoring regs
2345 // that aren't currently tracked, we set up something ugly for later: RegMask
2346 // operands that are seen earlier than the first use of a register, still need
2347 // to clobber that register in the transfer function. But this information
2348 // isn't actively recorded. Instead, we track each RegMask used in each block,
2349 // and accumulated the clobbered but untracked registers in each block into
2350 // the following bitvector. Later, if new values are tracked, we can add
2351 // appropriate clobbers.
2352 SmallVector<BitVector, 32> BlockMasks;
2353 BlockMasks.resize(N: MaxNumBlocks);
2354
2355 // Reserve one bit per register for the masks described above.
2356 unsigned BVWords = MachineOperand::getRegMaskSize(NumRegs: TRI->getNumRegs());
2357 for (auto &BV : BlockMasks)
2358 BV.resize(N: TRI->getNumRegs(), t: true);
2359
2360 // Step through all instructions and inhale the transfer function.
2361 for (auto &MBB : MF) {
2362 // Object fields that are read by trackers to know where we are in the
2363 // function.
2364 CurBB = MBB.getNumber();
2365 CurInst = 1;
2366
2367 // Set all machine locations to a PHI value. For transfer function
2368 // production only, this signifies the live-in value to the block.
2369 MTracker->reset();
2370 MTracker->setMPhis(CurBB);
2371
2372 // Step through each instruction in this block.
2373 for (auto &MI : MBB) {
2374 // Pass in an empty unique_ptr for the value tables when accumulating the
2375 // machine transfer function.
2376 process(MI, MLiveOuts: nullptr, MLiveIns: nullptr);
2377
2378 // Also accumulate fragment map.
2379 if (MI.isDebugValueLike())
2380 accumulateFragmentMap(MI);
2381
2382 // Create a map from the instruction number (if present) to the
2383 // MachineInstr and its position.
2384 if (uint64_t InstrNo = MI.peekDebugInstrNum()) {
2385 auto InstrAndPos = std::make_pair(x: &MI, y&: CurInst);
2386 auto InsertResult =
2387 DebugInstrNumToInstr.insert(x: std::make_pair(x&: InstrNo, y&: InstrAndPos));
2388
2389 // There should never be duplicate instruction numbers.
2390 assert(InsertResult.second);
2391 (void)InsertResult;
2392 }
2393
2394 ++CurInst;
2395 }
2396
2397 // Produce the transfer function, a map of machine location to new value. If
2398 // any machine location has the live-in phi value from the start of the
2399 // block, it's live-through and doesn't need recording in the transfer
2400 // function.
2401 for (auto Location : MTracker->locations()) {
2402 LocIdx Idx = Location.Idx;
2403 ValueIDNum &P = Location.Value;
2404 if (P.isPHI() && P.getLoc() == Idx.asU64())
2405 continue;
2406
2407 // Insert-or-update.
2408 auto &TransferMap = MLocTransfer[CurBB];
2409 auto Result = TransferMap.insert(KV: std::make_pair(x: Idx.asU64(), y&: P));
2410 if (!Result.second)
2411 Result.first->second = P;
2412 }
2413
2414 // Accumulate any bitmask operands into the clobbered reg mask for this
2415 // block.
2416 for (auto &P : MTracker->Masks) {
2417 BlockMasks[CurBB].clearBitsNotInMask(Mask: P.first->getRegMask(), MaskWords: BVWords);
2418 }
2419 }
2420
2421 // Compute a bitvector of all the registers that are tracked in this block.
2422 BitVector UsedRegs(TRI->getNumRegs());
2423 for (auto Location : MTracker->locations()) {
2424 unsigned ID = MTracker->LocIdxToLocID[Location.Idx];
2425 // Ignore stack slots, and aliases of the stack pointer.
2426 if (ID >= TRI->getNumRegs() || MTracker->SPAliases.count(V: ID))
2427 continue;
2428 UsedRegs.set(ID);
2429 }
2430
2431 // Check that any regmask-clobber of a register that gets tracked, is not
2432 // live-through in the transfer function. It needs to be clobbered at the
2433 // very least.
2434 for (unsigned int I = 0; I < MaxNumBlocks; ++I) {
2435 BitVector &BV = BlockMasks[I];
2436 BV.flip();
2437 BV &= UsedRegs;
2438 // This produces all the bits that we clobber, but also use. Check that
2439 // they're all clobbered or at least set in the designated transfer
2440 // elem.
2441 for (unsigned Bit : BV.set_bits()) {
2442 unsigned ID = MTracker->getLocID(Reg: Bit);
2443 LocIdx Idx = MTracker->LocIDToLocIdx[ID];
2444 auto &TransferMap = MLocTransfer[I];
2445
2446 // Install a value representing the fact that this location is effectively
2447 // written to in this block. As there's no reserved value, instead use
2448 // a value number that is never generated. Pick the value number for the
2449 // first instruction in the block, def'ing this location, which we know
2450 // this block never used anyway.
2451 ValueIDNum NotGeneratedNum = ValueIDNum(I, 1, Idx);
2452 auto Result =
2453 TransferMap.insert(KV: std::make_pair(x: Idx.asU64(), y&: NotGeneratedNum));
2454 if (!Result.second) {
2455 ValueIDNum &ValueID = Result.first->second;
2456 if (ValueID.getBlock() == I && ValueID.isPHI())
2457 // It was left as live-through. Set it to clobbered.
2458 ValueID = NotGeneratedNum;
2459 }
2460 }
2461 }
2462}
2463
2464bool InstrRefBasedLDV::mlocJoin(
2465 MachineBasicBlock &MBB, SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
2466 FuncValueTable &OutLocs, ValueTable &InLocs) {
2467 LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
2468 bool Changed = false;
2469
2470 // Handle value-propagation when control flow merges on entry to a block. For
2471 // any location without a PHI already placed, the location has the same value
2472 // as its predecessors. If a PHI is placed, test to see whether it's now a
2473 // redundant PHI that we can eliminate.
2474
2475 SmallVector<const MachineBasicBlock *, 8> BlockOrders(MBB.predecessors());
2476
2477 // Visit predecessors in RPOT order.
2478 auto Cmp = [&](const MachineBasicBlock *A, const MachineBasicBlock *B) {
2479 return BBToOrder.find(Val: A)->second < BBToOrder.find(Val: B)->second;
2480 };
2481 llvm::sort(C&: BlockOrders, Comp: Cmp);
2482
2483 // Skip entry block.
2484 if (BlockOrders.size() == 0) {
2485 // FIXME: We don't use assert here to prevent instr-ref-unreachable.mir
2486 // failing.
2487 LLVM_DEBUG(if (!MBB.isEntryBlock()) dbgs()
2488 << "Found not reachable block " << MBB.getFullName()
2489 << " from entry which may lead out of "
2490 "bound access to VarLocs\n");
2491 return false;
2492 }
2493
2494 // Step through all machine locations, look at each predecessor and test
2495 // whether we can eliminate redundant PHIs.
2496 for (auto Location : MTracker->locations()) {
2497 LocIdx Idx = Location.Idx;
2498
2499 // Pick out the first predecessors live-out value for this location. It's
2500 // guaranteed to not be a backedge, as we order by RPO.
2501 ValueIDNum FirstVal = OutLocs[*BlockOrders[0]][Idx.asU64()];
2502
2503 // If we've already eliminated a PHI here, do no further checking, just
2504 // propagate the first live-in value into this block.
2505 if (InLocs[Idx.asU64()] != ValueIDNum(MBB.getNumber(), 0, Idx)) {
2506 if (InLocs[Idx.asU64()] != FirstVal) {
2507 InLocs[Idx.asU64()] = FirstVal;
2508 Changed |= true;
2509 }
2510 continue;
2511 }
2512
2513 // We're now examining a PHI to see whether it's un-necessary. Loop around
2514 // the other live-in values and test whether they're all the same.
2515 bool Disagree = false;
2516 for (unsigned int I = 1; I < BlockOrders.size(); ++I) {
2517 const MachineBasicBlock *PredMBB = BlockOrders[I];
2518 const ValueIDNum &PredLiveOut = OutLocs[*PredMBB][Idx.asU64()];
2519
2520 // Incoming values agree, continue trying to eliminate this PHI.
2521 if (FirstVal == PredLiveOut)
2522 continue;
2523
2524 // We can also accept a PHI value that feeds back into itself.
2525 if (PredLiveOut == ValueIDNum(MBB.getNumber(), 0, Idx))
2526 continue;
2527
2528 // Live-out of a predecessor disagrees with the first predecessor.
2529 Disagree = true;
2530 }
2531
2532 // No disagreement? No PHI. Otherwise, leave the PHI in live-ins.
2533 if (!Disagree) {
2534 InLocs[Idx.asU64()] = FirstVal;
2535 Changed |= true;
2536 }
2537 }
2538
2539 // TODO: Reimplement NumInserted and NumRemoved.
2540 return Changed;
2541}
2542
2543void InstrRefBasedLDV::findStackIndexInterference(
2544 SmallVectorImpl<unsigned> &Slots) {
2545 // We could spend a bit of time finding the exact, minimal, set of stack
2546 // indexes that interfere with each other, much like reg units. Or, we can
2547 // rely on the fact that:
2548 // * The smallest / lowest index will interfere with everything at zero
2549 // offset, which will be the largest set of registers,
2550 // * Most indexes with non-zero offset will end up being interference units
2551 // anyway.
2552 // So just pick those out and return them.
2553
2554 // We can rely on a single-byte stack index existing already, because we
2555 // initialize them in MLocTracker.
2556 auto It = MTracker->StackSlotIdxes.find(Val: {8, 0});
2557 assert(It != MTracker->StackSlotIdxes.end());
2558 Slots.push_back(Elt: It->second);
2559
2560 // Find anything that has a non-zero offset and add that too.
2561 for (auto &Pair : MTracker->StackSlotIdxes) {
2562 // Is offset zero? If so, ignore.
2563 if (!Pair.first.second)
2564 continue;
2565 Slots.push_back(Elt: Pair.second);
2566 }
2567}
2568
2569void InstrRefBasedLDV::placeMLocPHIs(
2570 MachineFunction &MF, SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks,
2571 FuncValueTable &MInLocs, SmallVectorImpl<MLocTransferMap> &MLocTransfer) {
2572 SmallVector<unsigned, 4> StackUnits;
2573 findStackIndexInterference(Slots&: StackUnits);
2574
2575 // To avoid repeatedly running the PHI placement algorithm, leverage the
2576 // fact that a def of register MUST also def its register units. Find the
2577 // units for registers, place PHIs for them, and then replicate them for
2578 // aliasing registers. Some inputs that are never def'd (DBG_PHIs of
2579 // arguments) don't lead to register units being tracked, just place PHIs for
2580 // those registers directly. Stack slots have their own form of "unit",
2581 // store them to one side.
2582 SmallSet<Register, 32> RegUnitsToPHIUp;
2583 SmallSet<LocIdx, 32> NormalLocsToPHI;
2584 SmallSet<SpillLocationNo, 32> StackSlots;
2585 for (auto Location : MTracker->locations()) {
2586 LocIdx L = Location.Idx;
2587 if (MTracker->isSpill(Idx: L)) {
2588 StackSlots.insert(V: MTracker->locIDToSpill(ID: MTracker->LocIdxToLocID[L]));
2589 continue;
2590 }
2591
2592 Register R = MTracker->LocIdxToLocID[L];
2593 SmallSet<Register, 8> FoundRegUnits;
2594 bool AnyIllegal = false;
2595 for (MCRegUnit Unit : TRI->regunits(Reg: R.asMCReg())) {
2596 for (MCRegUnitRootIterator URoot(Unit, TRI); URoot.isValid(); ++URoot) {
2597 if (!MTracker->isRegisterTracked(R: *URoot)) {
2598 // Not all roots were loaded into the tracking map: this register
2599 // isn't actually def'd anywhere, we only read from it. Generate PHIs
2600 // for this reg, but don't iterate units.
2601 AnyIllegal = true;
2602 } else {
2603 FoundRegUnits.insert(V: *URoot);
2604 }
2605 }
2606 }
2607
2608 if (AnyIllegal) {
2609 NormalLocsToPHI.insert(V: L);
2610 continue;
2611 }
2612
2613 RegUnitsToPHIUp.insert_range(R&: FoundRegUnits);
2614 }
2615
2616 // Lambda to fetch PHIs for a given location, and write into the PHIBlocks
2617 // collection.
2618 SmallVector<MachineBasicBlock *, 32> PHIBlocks;
2619 auto CollectPHIsForLoc = [&](LocIdx L) {
2620 // Collect the set of defs.
2621 SmallPtrSet<MachineBasicBlock *, 32> DefBlocks;
2622 for (MachineBasicBlock *MBB : OrderToBB) {
2623 const auto &TransferFunc = MLocTransfer[MBB->getNumber()];
2624 if (TransferFunc.contains(Val: L))
2625 DefBlocks.insert(Ptr: MBB);
2626 }
2627
2628 // The entry block defs the location too: it's the live-in / argument value.
2629 // Only insert if there are other defs though; everything is trivially live
2630 // through otherwise.
2631 if (!DefBlocks.empty())
2632 DefBlocks.insert(Ptr: &*MF.begin());
2633
2634 // Ask the SSA construction algorithm where we should put PHIs. Clear
2635 // anything that might have been hanging around from earlier.
2636 PHIBlocks.clear();
2637 BlockPHIPlacement(AllBlocks, DefBlocks, PHIBlocks);
2638 };
2639
2640 auto InstallPHIsAtLoc = [&PHIBlocks, &MInLocs](LocIdx L) {
2641 for (const MachineBasicBlock *MBB : PHIBlocks)
2642 MInLocs[*MBB][L.asU64()] = ValueIDNum(MBB->getNumber(), 0, L);
2643 };
2644
2645 // For locations with no reg units, just place PHIs.
2646 for (LocIdx L : NormalLocsToPHI) {
2647 CollectPHIsForLoc(L);
2648 // Install those PHI values into the live-in value array.
2649 InstallPHIsAtLoc(L);
2650 }
2651
2652 // For stack slots, calculate PHIs for the equivalent of the units, then
2653 // install for each index.
2654 for (SpillLocationNo Slot : StackSlots) {
2655 for (unsigned Idx : StackUnits) {
2656 unsigned SpillID = MTracker->getSpillIDWithIdx(Spill: Slot, Idx);
2657 LocIdx L = MTracker->getSpillMLoc(SpillID);
2658 CollectPHIsForLoc(L);
2659 InstallPHIsAtLoc(L);
2660
2661 // Find anything that aliases this stack index, install PHIs for it too.
2662 unsigned Size, Offset;
2663 std::tie(args&: Size, args&: Offset) = MTracker->StackIdxesToPos[Idx];
2664 for (auto &Pair : MTracker->StackSlotIdxes) {
2665 unsigned ThisSize, ThisOffset;
2666 std::tie(args&: ThisSize, args&: ThisOffset) = Pair.first;
2667 if (ThisSize + ThisOffset <= Offset || Size + Offset <= ThisOffset)
2668 continue;
2669
2670 unsigned ThisID = MTracker->getSpillIDWithIdx(Spill: Slot, Idx: Pair.second);
2671 LocIdx ThisL = MTracker->getSpillMLoc(SpillID: ThisID);
2672 InstallPHIsAtLoc(ThisL);
2673 }
2674 }
2675 }
2676
2677 // For reg units, place PHIs, and then place them for any aliasing registers.
2678 for (Register R : RegUnitsToPHIUp) {
2679 LocIdx L = MTracker->lookupOrTrackRegister(ID: MTracker->getLocID(Reg: R));
2680 CollectPHIsForLoc(L);
2681
2682 // Install those PHI values into the live-in value array.
2683 InstallPHIsAtLoc(L);
2684
2685 // Now find aliases and install PHIs for those.
2686 for (MCRegAliasIterator RAI(R, TRI, true); RAI.isValid(); ++RAI) {
2687 // Super-registers that are "above" the largest register read/written by
2688 // the function will alias, but will not be tracked.
2689 if (!MTracker->isRegisterTracked(R: *RAI))
2690 continue;
2691
2692 LocIdx AliasLoc =
2693 MTracker->lookupOrTrackRegister(ID: MTracker->getLocID(Reg: *RAI));
2694 InstallPHIsAtLoc(AliasLoc);
2695 }
2696 }
2697}
2698
2699void InstrRefBasedLDV::buildMLocValueMap(
2700 MachineFunction &MF, FuncValueTable &MInLocs, FuncValueTable &MOutLocs,
2701 SmallVectorImpl<MLocTransferMap> &MLocTransfer) {
2702 std::priority_queue<unsigned int, std::vector<unsigned int>,
2703 std::greater<unsigned int>>
2704 Worklist, Pending;
2705
2706 // We track what is on the current and pending worklist to avoid inserting
2707 // the same thing twice. We could avoid this with a custom priority queue,
2708 // but this is probably not worth it.
2709 SmallPtrSet<MachineBasicBlock *, 16> OnPending, OnWorklist;
2710
2711 // Initialize worklist with every block to be visited. Also produce list of
2712 // all blocks.
2713 SmallPtrSet<MachineBasicBlock *, 32> AllBlocks;
2714 for (unsigned int I = 0; I < BBToOrder.size(); ++I) {
2715 Worklist.push(x: I);
2716 OnWorklist.insert(Ptr: OrderToBB[I]);
2717 AllBlocks.insert(Ptr: OrderToBB[I]);
2718 }
2719
2720 // Initialize entry block to PHIs. These represent arguments.
2721 for (auto Location : MTracker->locations())
2722 MInLocs.tableForEntryMBB()[Location.Idx.asU64()] =
2723 ValueIDNum(0, 0, Location.Idx);
2724
2725 MTracker->reset();
2726
2727 // Start by placing PHIs, using the usual SSA constructor algorithm. Consider
2728 // any machine-location that isn't live-through a block to be def'd in that
2729 // block.
2730 placeMLocPHIs(MF, AllBlocks, MInLocs, MLocTransfer);
2731
2732 // Propagate values to eliminate redundant PHIs. At the same time, this
2733 // produces the table of Block x Location => Value for the entry to each
2734 // block.
2735 // The kind of PHIs we can eliminate are, for example, where one path in a
2736 // conditional spills and restores a register, and the register still has
2737 // the same value once control flow joins, unbeknowns to the PHI placement
2738 // code. Propagating values allows us to identify such un-necessary PHIs and
2739 // remove them.
2740 SmallPtrSet<const MachineBasicBlock *, 16> Visited;
2741 while (!Worklist.empty() || !Pending.empty()) {
2742 // Vector for storing the evaluated block transfer function.
2743 SmallVector<std::pair<LocIdx, ValueIDNum>, 32> ToRemap;
2744
2745 while (!Worklist.empty()) {
2746 MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
2747 CurBB = MBB->getNumber();
2748 Worklist.pop();
2749
2750 // Join the values in all predecessor blocks.
2751 bool InLocsChanged;
2752 InLocsChanged = mlocJoin(MBB&: *MBB, Visited, OutLocs&: MOutLocs, InLocs&: MInLocs[*MBB]);
2753 InLocsChanged |= Visited.insert(Ptr: MBB).second;
2754
2755 // Don't examine transfer function if we've visited this loc at least
2756 // once, and inlocs haven't changed.
2757 if (!InLocsChanged)
2758 continue;
2759
2760 // Load the current set of live-ins into MLocTracker.
2761 MTracker->loadFromArray(Locs&: MInLocs[*MBB], NewCurBB: CurBB);
2762
2763 // Each element of the transfer function can be a new def, or a read of
2764 // a live-in value. Evaluate each element, and store to "ToRemap".
2765 ToRemap.clear();
2766 for (auto &P : MLocTransfer[CurBB]) {
2767 if (P.second.getBlock() == CurBB && P.second.isPHI()) {
2768 // This is a movement of whatever was live in. Read it.
2769 ValueIDNum NewID = MTracker->readMLoc(L: P.second.getLoc());
2770 ToRemap.push_back(Elt: std::make_pair(x&: P.first, y&: NewID));
2771 } else {
2772 // It's a def. Just set it.
2773 assert(P.second.getBlock() == CurBB);
2774 ToRemap.push_back(Elt: std::make_pair(x&: P.first, y&: P.second));
2775 }
2776 }
2777
2778 // Commit the transfer function changes into mloc tracker, which
2779 // transforms the contents of the MLocTracker into the live-outs.
2780 for (auto &P : ToRemap)
2781 MTracker->setMLoc(L: P.first, Num: P.second);
2782
2783 // Now copy out-locs from mloc tracker into out-loc vector, checking
2784 // whether changes have occurred. These changes can have come from both
2785 // the transfer function, and mlocJoin.
2786 bool OLChanged = false;
2787 for (auto Location : MTracker->locations()) {
2788 OLChanged |= MOutLocs[*MBB][Location.Idx.asU64()] != Location.Value;
2789 MOutLocs[*MBB][Location.Idx.asU64()] = Location.Value;
2790 }
2791
2792 MTracker->reset();
2793
2794 // No need to examine successors again if out-locs didn't change.
2795 if (!OLChanged)
2796 continue;
2797
2798 // All successors should be visited: put any back-edges on the pending
2799 // list for the next pass-through, and any other successors to be
2800 // visited this pass, if they're not going to be already.
2801 for (auto *s : MBB->successors()) {
2802 // Does branching to this successor represent a back-edge?
2803 unsigned Order = BBToOrder[s];
2804 if (Order > BBToOrder[MBB]) {
2805 // No: visit it during this dataflow iteration.
2806 if (OnWorklist.insert(Ptr: s).second)
2807 Worklist.push(x: Order);
2808 } else {
2809 // Yes: visit it on the next iteration.
2810 if (OnPending.insert(Ptr: s).second)
2811 Pending.push(x: Order);
2812 }
2813 }
2814 }
2815
2816 Worklist.swap(pq&: Pending);
2817 std::swap(LHS&: OnPending, RHS&: OnWorklist);
2818 OnPending.clear();
2819 // At this point, pending must be empty, since it was just the empty
2820 // worklist
2821 assert(Pending.empty() && "Pending should be empty");
2822 }
2823
2824 // Once all the live-ins don't change on mlocJoin(), we've eliminated all
2825 // redundant PHIs.
2826}
2827
2828void InstrRefBasedLDV::BlockPHIPlacement(
2829 const SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks,
2830 const SmallPtrSetImpl<MachineBasicBlock *> &DefBlocks,
2831 SmallVectorImpl<MachineBasicBlock *> &PHIBlocks) {
2832 // Apply IDF calculator to the designated set of location defs, storing
2833 // required PHIs into PHIBlocks. Uses the dominator tree stored in the
2834 // InstrRefBasedLDV object.
2835 IDFCalculatorBase<MachineBasicBlock, false> IDF(*DomTree);
2836
2837 IDF.setLiveInBlocks(AllBlocks);
2838 IDF.setDefiningBlocks(DefBlocks);
2839 IDF.calculate(IDFBlocks&: PHIBlocks);
2840}
2841
2842bool InstrRefBasedLDV::pickVPHILoc(
2843 SmallVectorImpl<DbgOpID> &OutValues, const MachineBasicBlock &MBB,
2844 const LiveIdxT &LiveOuts, FuncValueTable &MOutLocs,
2845 const SmallVectorImpl<const MachineBasicBlock *> &BlockOrders) {
2846
2847 // No predecessors means no PHIs.
2848 if (BlockOrders.empty())
2849 return false;
2850
2851 // All the location operands that do not already agree need to be joined,
2852 // track the indices of each such location operand here.
2853 SmallDenseSet<unsigned> LocOpsToJoin;
2854
2855 auto FirstValueIt = LiveOuts.find(Val: BlockOrders[0]);
2856 if (FirstValueIt == LiveOuts.end())
2857 return false;
2858 const DbgValue &FirstValue = *FirstValueIt->second;
2859
2860 for (const auto p : BlockOrders) {
2861 auto OutValIt = LiveOuts.find(Val: p);
2862 if (OutValIt == LiveOuts.end())
2863 // If we have a predecessor not in scope, we'll never find a PHI position.
2864 return false;
2865 const DbgValue &OutVal = *OutValIt->second;
2866
2867 // No-values cannot have locations we can join on.
2868 if (OutVal.Kind == DbgValue::NoVal)
2869 return false;
2870
2871 // For unjoined VPHIs where we don't know the location, we definitely
2872 // can't find a join loc unless the VPHI is a backedge.
2873 if (OutVal.isUnjoinedPHI() && OutVal.BlockNo != MBB.getNumber())
2874 return false;
2875
2876 if (!FirstValue.Properties.isJoinable(Other: OutVal.Properties))
2877 return false;
2878
2879 for (unsigned Idx = 0; Idx < FirstValue.getLocationOpCount(); ++Idx) {
2880 // An unjoined PHI has no defined locations, and so a shared location must
2881 // be found for every operand.
2882 if (OutVal.isUnjoinedPHI()) {
2883 LocOpsToJoin.insert(V: Idx);
2884 continue;
2885 }
2886 DbgOpID FirstValOp = FirstValue.getDbgOpID(Index: Idx);
2887 DbgOpID OutValOp = OutVal.getDbgOpID(Index: Idx);
2888 if (FirstValOp != OutValOp) {
2889 // We can never join constant ops - the ops must either both be equal
2890 // constant ops or non-const ops.
2891 if (FirstValOp.isConst() || OutValOp.isConst())
2892 return false;
2893 else
2894 LocOpsToJoin.insert(V: Idx);
2895 }
2896 }
2897 }
2898
2899 SmallVector<DbgOpID> NewDbgOps;
2900
2901 for (unsigned Idx = 0; Idx < FirstValue.getLocationOpCount(); ++Idx) {
2902 // If this op doesn't need to be joined because the values agree, use that
2903 // already-agreed value.
2904 if (!LocOpsToJoin.contains(V: Idx)) {
2905 NewDbgOps.push_back(Elt: FirstValue.getDbgOpID(Index: Idx));
2906 continue;
2907 }
2908
2909 std::optional<ValueIDNum> JoinedOpLoc =
2910 pickOperandPHILoc(DbgOpIdx: Idx, MBB, LiveOuts, MOutLocs, BlockOrders);
2911
2912 if (!JoinedOpLoc)
2913 return false;
2914
2915 NewDbgOps.push_back(Elt: DbgOpStore.insert(Op: *JoinedOpLoc));
2916 }
2917
2918 OutValues.append(RHS: NewDbgOps);
2919 return true;
2920}
2921
2922std::optional<ValueIDNum> InstrRefBasedLDV::pickOperandPHILoc(
2923 unsigned DbgOpIdx, const MachineBasicBlock &MBB, const LiveIdxT &LiveOuts,
2924 FuncValueTable &MOutLocs,
2925 const SmallVectorImpl<const MachineBasicBlock *> &BlockOrders) {
2926
2927 // Collect a set of locations from predecessor where its live-out value can
2928 // be found.
2929 SmallVector<SmallVector<LocIdx, 4>, 8> Locs;
2930 unsigned NumLocs = MTracker->getNumLocs();
2931
2932 for (const auto p : BlockOrders) {
2933 auto OutValIt = LiveOuts.find(Val: p);
2934 assert(OutValIt != LiveOuts.end());
2935 const DbgValue &OutVal = *OutValIt->second;
2936 DbgOpID OutValOpID = OutVal.getDbgOpID(Index: DbgOpIdx);
2937 DbgOp OutValOp = DbgOpStore.find(ID: OutValOpID);
2938 assert(!OutValOp.IsConst);
2939
2940 // Create new empty vector of locations.
2941 Locs.resize(N: Locs.size() + 1);
2942
2943 // If the live-in value is a def, find the locations where that value is
2944 // present. Do the same for VPHIs where we know the VPHI value.
2945 if (OutVal.Kind == DbgValue::Def ||
2946 (OutVal.Kind == DbgValue::VPHI && OutVal.BlockNo != MBB.getNumber() &&
2947 !OutValOp.isUndef())) {
2948 ValueIDNum ValToLookFor = OutValOp.ID;
2949 // Search the live-outs of the predecessor for the specified value.
2950 for (unsigned int I = 0; I < NumLocs; ++I) {
2951 if (MOutLocs[*p][I] == ValToLookFor)
2952 Locs.back().push_back(Elt: LocIdx(I));
2953 }
2954 } else {
2955 assert(OutVal.Kind == DbgValue::VPHI);
2956 // Otherwise: this is a VPHI on a backedge feeding back into itself, i.e.
2957 // a value that's live-through the whole loop. (It has to be a backedge,
2958 // because a block can't dominate itself). We can accept as a PHI location
2959 // any location where the other predecessors agree, _and_ the machine
2960 // locations feed back into themselves. Therefore, add all self-looping
2961 // machine-value PHI locations.
2962 for (unsigned int I = 0; I < NumLocs; ++I) {
2963 ValueIDNum MPHI(MBB.getNumber(), 0, LocIdx(I));
2964 if (MOutLocs[*p][I] == MPHI)
2965 Locs.back().push_back(Elt: LocIdx(I));
2966 }
2967 }
2968 }
2969 // We should have found locations for all predecessors, or returned.
2970 assert(Locs.size() == BlockOrders.size());
2971
2972 // Starting with the first set of locations, take the intersection with
2973 // subsequent sets.
2974 SmallVector<LocIdx, 4> CandidateLocs = Locs[0];
2975 for (unsigned int I = 1; I < Locs.size(); ++I) {
2976 auto &LocVec = Locs[I];
2977 SmallVector<LocIdx, 4> NewCandidates;
2978 std::set_intersection(first1: CandidateLocs.begin(), last1: CandidateLocs.end(),
2979 first2: LocVec.begin(), last2: LocVec.end(), result: std::inserter(x&: NewCandidates, i: NewCandidates.begin()));
2980 CandidateLocs = std::move(NewCandidates);
2981 }
2982 if (CandidateLocs.empty())
2983 return std::nullopt;
2984
2985 // We now have a set of LocIdxes that contain the right output value in
2986 // each of the predecessors. Pick the lowest; if there's a register loc,
2987 // that'll be it.
2988 LocIdx L = *CandidateLocs.begin();
2989
2990 // Return a PHI-value-number for the found location.
2991 ValueIDNum PHIVal = {(unsigned)MBB.getNumber(), 0, L};
2992 return PHIVal;
2993}
2994
2995bool InstrRefBasedLDV::vlocJoin(
2996 MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs,
2997 SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore,
2998 DbgValue &LiveIn) {
2999 LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
3000 bool Changed = false;
3001
3002 // Order predecessors by RPOT order, for exploring them in that order.
3003 SmallVector<MachineBasicBlock *, 8> BlockOrders(MBB.predecessors());
3004
3005 auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
3006 return BBToOrder[A] < BBToOrder[B];
3007 };
3008
3009 llvm::sort(C&: BlockOrders, Comp: Cmp);
3010
3011 unsigned CurBlockRPONum = BBToOrder[&MBB];
3012
3013 // Collect all the incoming DbgValues for this variable, from predecessor
3014 // live-out values.
3015 SmallVector<InValueT, 8> Values;
3016 bool Bail = false;
3017 int BackEdgesStart = 0;
3018 for (auto *p : BlockOrders) {
3019 // If the predecessor isn't in scope / to be explored, we'll never be
3020 // able to join any locations.
3021 if (!BlocksToExplore.contains(Ptr: p)) {
3022 Bail = true;
3023 break;
3024 }
3025
3026 // All Live-outs will have been initialized.
3027 DbgValue &OutLoc = *VLOCOutLocs.find(Val: p)->second;
3028
3029 // Keep track of where back-edges begin in the Values vector. Relies on
3030 // BlockOrders being sorted by RPO.
3031 unsigned ThisBBRPONum = BBToOrder[p];
3032 if (ThisBBRPONum < CurBlockRPONum)
3033 ++BackEdgesStart;
3034
3035 Values.push_back(Elt: std::make_pair(x&: p, y: &OutLoc));
3036 }
3037
3038 // If there were no values, or one of the predecessors couldn't have a
3039 // value, then give up immediately. It's not safe to produce a live-in
3040 // value. Leave as whatever it was before.
3041 if (Bail || Values.size() == 0)
3042 return false;
3043
3044 // All (non-entry) blocks have at least one non-backedge predecessor.
3045 // Pick the variable value from the first of these, to compare against
3046 // all others.
3047 const DbgValue &FirstVal = *Values[0].second;
3048
3049 // If the old live-in value is not a PHI then either a) no PHI is needed
3050 // here, or b) we eliminated the PHI that was here. If so, we can just
3051 // propagate in the first parent's incoming value.
3052 if (LiveIn.Kind != DbgValue::VPHI || LiveIn.BlockNo != MBB.getNumber()) {
3053 Changed = LiveIn != FirstVal;
3054 if (Changed)
3055 LiveIn = FirstVal;
3056 return Changed;
3057 }
3058
3059 // Scan for variable values that can never be resolved: if they have
3060 // different DIExpressions, different indirectness, or are mixed constants /
3061 // non-constants.
3062 for (const auto &V : Values) {
3063 if (!V.second->Properties.isJoinable(Other: FirstVal.Properties))
3064 return false;
3065 if (V.second->Kind == DbgValue::NoVal)
3066 return false;
3067 if (!V.second->hasJoinableLocOps(Other: FirstVal))
3068 return false;
3069 }
3070
3071 // Try to eliminate this PHI. Do the incoming values all agree?
3072 bool Disagree = false;
3073 for (auto &V : Values) {
3074 if (*V.second == FirstVal)
3075 continue; // No disagreement.
3076
3077 // If both values are not equal but have equal non-empty IDs then they refer
3078 // to the same value from different sources (e.g. one is VPHI and the other
3079 // is Def), which does not cause disagreement.
3080 if (V.second->hasIdenticalValidLocOps(Other: FirstVal))
3081 continue;
3082
3083 // Eliminate if a backedge feeds a VPHI back into itself.
3084 if (V.second->Kind == DbgValue::VPHI &&
3085 V.second->BlockNo == MBB.getNumber() &&
3086 // Is this a backedge?
3087 std::distance(first: Values.begin(), last: &V) >= BackEdgesStart)
3088 continue;
3089
3090 Disagree = true;
3091 }
3092
3093 // No disagreement -> live-through value.
3094 if (!Disagree) {
3095 Changed = LiveIn != FirstVal;
3096 if (Changed)
3097 LiveIn = FirstVal;
3098 return Changed;
3099 } else {
3100 // Otherwise use a VPHI.
3101 DbgValue VPHI(MBB.getNumber(), FirstVal.Properties, DbgValue::VPHI);
3102 Changed = LiveIn != VPHI;
3103 if (Changed)
3104 LiveIn = VPHI;
3105 return Changed;
3106 }
3107}
3108
3109void InstrRefBasedLDV::getBlocksForScope(
3110 const DILocation *DILoc,
3111 SmallPtrSetImpl<const MachineBasicBlock *> &BlocksToExplore,
3112 const SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks) {
3113 // Get the set of "normal" in-lexical-scope blocks.
3114 LS.getMachineBasicBlocks(DL: DILoc, MBBs&: BlocksToExplore);
3115
3116 // VarLoc LiveDebugValues tracks variable locations that are defined in
3117 // blocks not in scope. This is something we could legitimately ignore, but
3118 // lets allow it for now for the sake of coverage.
3119 BlocksToExplore.insert_range(R: AssignBlocks);
3120
3121 // Storage for artificial blocks we intend to add to BlocksToExplore.
3122 DenseSet<const MachineBasicBlock *> ToAdd;
3123
3124 // To avoid needlessly dropping large volumes of variable locations, propagate
3125 // variables through aritifical blocks, i.e. those that don't have any
3126 // instructions in scope at all. To accurately replicate VarLoc
3127 // LiveDebugValues, this means exploring all artificial successors too.
3128 // Perform a depth-first-search to enumerate those blocks.
3129 for (const auto *MBB : BlocksToExplore) {
3130 // Depth-first-search state: each node is a block and which successor
3131 // we're currently exploring.
3132 SmallVector<std::pair<const MachineBasicBlock *,
3133 MachineBasicBlock::const_succ_iterator>,
3134 8>
3135 DFS;
3136
3137 // Find any artificial successors not already tracked.
3138 for (auto *succ : MBB->successors()) {
3139 if (BlocksToExplore.count(Ptr: succ))
3140 continue;
3141 if (!ArtificialBlocks.count(Ptr: succ))
3142 continue;
3143 ToAdd.insert(V: succ);
3144 DFS.push_back(Elt: {succ, succ->succ_begin()});
3145 }
3146
3147 // Search all those blocks, depth first.
3148 while (!DFS.empty()) {
3149 const MachineBasicBlock *CurBB = DFS.back().first;
3150 MachineBasicBlock::const_succ_iterator &CurSucc = DFS.back().second;
3151 // Walk back if we've explored this blocks successors to the end.
3152 if (CurSucc == CurBB->succ_end()) {
3153 DFS.pop_back();
3154 continue;
3155 }
3156
3157 // If the current successor is artificial and unexplored, descend into
3158 // it.
3159 if (!ToAdd.count(V: *CurSucc) && ArtificialBlocks.count(Ptr: *CurSucc)) {
3160 ToAdd.insert(V: *CurSucc);
3161 DFS.push_back(Elt: {*CurSucc, (*CurSucc)->succ_begin()});
3162 continue;
3163 }
3164
3165 ++CurSucc;
3166 }
3167 };
3168
3169 BlocksToExplore.insert_range(R&: ToAdd);
3170}
3171
3172void InstrRefBasedLDV::buildVLocValueMap(
3173 const DILocation *DILoc,
3174 const SmallSet<DebugVariableID, 4> &VarsWeCareAbout,
3175 SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, LiveInsT &Output,
3176 FuncValueTable &MOutLocs, FuncValueTable &MInLocs,
3177 SmallVectorImpl<VLocTracker> &AllTheVLocs) {
3178 // This method is much like buildMLocValueMap: but focuses on a single
3179 // LexicalScope at a time. Pick out a set of blocks and variables that are
3180 // to have their value assignments solved, then run our dataflow algorithm
3181 // until a fixedpoint is reached.
3182 std::priority_queue<unsigned int, std::vector<unsigned int>,
3183 std::greater<unsigned int>>
3184 Worklist, Pending;
3185 SmallPtrSet<MachineBasicBlock *, 16> OnWorklist, OnPending;
3186
3187 // The set of blocks we'll be examining.
3188 SmallPtrSet<const MachineBasicBlock *, 8> BlocksToExplore;
3189
3190 // The order in which to examine them (RPO).
3191 SmallVector<MachineBasicBlock *, 16> BlockOrders;
3192 SmallVector<unsigned, 32> BlockOrderNums;
3193
3194 getBlocksForScope(DILoc, BlocksToExplore, AssignBlocks);
3195
3196 // Single block scope: not interesting! No propagation at all. Note that
3197 // this could probably go above ArtificialBlocks without damage, but
3198 // that then produces output differences from original-live-debug-values,
3199 // which propagates from a single block into many artificial ones.
3200 if (BlocksToExplore.size() == 1)
3201 return;
3202
3203 // Convert a const set to a non-const set. LexicalScopes
3204 // getMachineBasicBlocks returns const MBB pointers, IDF wants mutable ones.
3205 // (Neither of them mutate anything).
3206 SmallPtrSet<MachineBasicBlock *, 8> MutBlocksToExplore;
3207 for (const auto *MBB : BlocksToExplore)
3208 MutBlocksToExplore.insert(Ptr: const_cast<MachineBasicBlock *>(MBB));
3209
3210 // Picks out relevants blocks RPO order and sort them. Sort their
3211 // order-numbers and map back to MBB pointers later, to avoid repeated
3212 // DenseMap queries during comparisons.
3213 for (const auto *MBB : BlocksToExplore)
3214 BlockOrderNums.push_back(Elt: BBToOrder[MBB]);
3215
3216 llvm::sort(C&: BlockOrderNums);
3217 for (unsigned int I : BlockOrderNums)
3218 BlockOrders.push_back(Elt: OrderToBB[I]);
3219 BlockOrderNums.clear();
3220 unsigned NumBlocks = BlockOrders.size();
3221
3222 // Allocate some vectors for storing the live ins and live outs. Large.
3223 SmallVector<DbgValue, 32> LiveIns, LiveOuts;
3224 LiveIns.reserve(N: NumBlocks);
3225 LiveOuts.reserve(N: NumBlocks);
3226
3227 // Initialize all values to start as NoVals. This signifies "it's live
3228 // through, but we don't know what it is".
3229 DbgValueProperties EmptyProperties(EmptyExpr, false, false);
3230 for (unsigned int I = 0; I < NumBlocks; ++I) {
3231 DbgValue EmptyDbgValue(I, EmptyProperties, DbgValue::NoVal);
3232 LiveIns.push_back(Elt: EmptyDbgValue);
3233 LiveOuts.push_back(Elt: EmptyDbgValue);
3234 }
3235
3236 // Produce by-MBB indexes of live-in/live-outs, to ease lookup within
3237 // vlocJoin.
3238 LiveIdxT LiveOutIdx, LiveInIdx;
3239 LiveOutIdx.reserve(NumEntries: NumBlocks);
3240 LiveInIdx.reserve(NumEntries: NumBlocks);
3241 for (unsigned I = 0; I < NumBlocks; ++I) {
3242 LiveOutIdx[BlockOrders[I]] = &LiveOuts[I];
3243 LiveInIdx[BlockOrders[I]] = &LiveIns[I];
3244 }
3245
3246 // Loop over each variable and place PHIs for it, then propagate values
3247 // between blocks. This keeps the locality of working on one lexical scope at
3248 // at time, but avoids re-processing variable values because some other
3249 // variable has been assigned.
3250 for (DebugVariableID VarID : VarsWeCareAbout) {
3251 // Re-initialize live-ins and live-outs, to clear the remains of previous
3252 // variables live-ins / live-outs.
3253 for (unsigned int I = 0; I < NumBlocks; ++I) {
3254 DbgValue EmptyDbgValue(I, EmptyProperties, DbgValue::NoVal);
3255 LiveIns[I] = EmptyDbgValue;
3256 LiveOuts[I] = EmptyDbgValue;
3257 }
3258
3259 // Place PHIs for variable values, using the LLVM IDF calculator.
3260 // Collect the set of blocks where variables are def'd.
3261 SmallPtrSet<MachineBasicBlock *, 32> DefBlocks;
3262 for (const MachineBasicBlock *ExpMBB : BlocksToExplore) {
3263 auto &TransferFunc = AllTheVLocs[ExpMBB->getNumber()].Vars;
3264 if (TransferFunc.contains(Key: VarID))
3265 DefBlocks.insert(Ptr: const_cast<MachineBasicBlock *>(ExpMBB));
3266 }
3267
3268 SmallVector<MachineBasicBlock *, 32> PHIBlocks;
3269
3270 // Request the set of PHIs we should insert for this variable. If there's
3271 // only one value definition, things are very simple.
3272 if (DefBlocks.size() == 1) {
3273 placePHIsForSingleVarDefinition(InScopeBlocks: MutBlocksToExplore, MBB: *DefBlocks.begin(),
3274 AllTheVLocs, Var: VarID, Output);
3275 continue;
3276 }
3277
3278 // Otherwise: we need to place PHIs through SSA and propagate values.
3279 BlockPHIPlacement(AllBlocks: MutBlocksToExplore, DefBlocks, PHIBlocks);
3280
3281 // Insert PHIs into the per-block live-in tables for this variable.
3282 for (MachineBasicBlock *PHIMBB : PHIBlocks) {
3283 unsigned BlockNo = PHIMBB->getNumber();
3284 DbgValue *LiveIn = LiveInIdx[PHIMBB];
3285 *LiveIn = DbgValue(BlockNo, EmptyProperties, DbgValue::VPHI);
3286 }
3287
3288 for (auto *MBB : BlockOrders) {
3289 Worklist.push(x: BBToOrder[MBB]);
3290 OnWorklist.insert(Ptr: MBB);
3291 }
3292
3293 // Iterate over all the blocks we selected, propagating the variables value.
3294 // This loop does two things:
3295 // * Eliminates un-necessary VPHIs in vlocJoin,
3296 // * Evaluates the blocks transfer function (i.e. variable assignments) and
3297 // stores the result to the blocks live-outs.
3298 // Always evaluate the transfer function on the first iteration, and when
3299 // the live-ins change thereafter.
3300 bool FirstTrip = true;
3301 while (!Worklist.empty() || !Pending.empty()) {
3302 while (!Worklist.empty()) {
3303 auto *MBB = OrderToBB[Worklist.top()];
3304 CurBB = MBB->getNumber();
3305 Worklist.pop();
3306
3307 auto LiveInsIt = LiveInIdx.find(Val: MBB);
3308 assert(LiveInsIt != LiveInIdx.end());
3309 DbgValue *LiveIn = LiveInsIt->second;
3310
3311 // Join values from predecessors. Updates LiveInIdx, and writes output
3312 // into JoinedInLocs.
3313 bool InLocsChanged =
3314 vlocJoin(MBB&: *MBB, VLOCOutLocs&: LiveOutIdx, BlocksToExplore, LiveIn&: *LiveIn);
3315
3316 SmallVector<const MachineBasicBlock *, 8> Preds(MBB->predecessors());
3317
3318 // If this block's live-in value is a VPHI, try to pick a machine-value
3319 // for it. This makes the machine-value available and propagated
3320 // through all blocks by the time value propagation finishes. We can't
3321 // do this any earlier as it needs to read the block live-outs.
3322 if (LiveIn->Kind == DbgValue::VPHI && LiveIn->BlockNo == (int)CurBB) {
3323 // There's a small possibility that on a preceeding path, a VPHI is
3324 // eliminated and transitions from VPHI-with-location to
3325 // live-through-value. As a result, the selected location of any VPHI
3326 // might change, so we need to re-compute it on each iteration.
3327 SmallVector<DbgOpID> JoinedOps;
3328
3329 if (pickVPHILoc(OutValues&: JoinedOps, MBB: *MBB, LiveOuts: LiveOutIdx, MOutLocs, BlockOrders: Preds)) {
3330 bool NewLocPicked = !equal(LRange: LiveIn->getDbgOpIDs(), RRange&: JoinedOps);
3331 InLocsChanged |= NewLocPicked;
3332 if (NewLocPicked)
3333 LiveIn->setDbgOpIDs(JoinedOps);
3334 }
3335 }
3336
3337 if (!InLocsChanged && !FirstTrip)
3338 continue;
3339
3340 DbgValue *LiveOut = LiveOutIdx[MBB];
3341 bool OLChanged = false;
3342
3343 // Do transfer function.
3344 auto &VTracker = AllTheVLocs[MBB->getNumber()];
3345 auto TransferIt = VTracker.Vars.find(Key: VarID);
3346 if (TransferIt != VTracker.Vars.end()) {
3347 // Erase on empty transfer (DBG_VALUE $noreg).
3348 if (TransferIt->second.Kind == DbgValue::Undef) {
3349 DbgValue NewVal(MBB->getNumber(), EmptyProperties, DbgValue::NoVal);
3350 if (*LiveOut != NewVal) {
3351 *LiveOut = NewVal;
3352 OLChanged = true;
3353 }
3354 } else {
3355 // Insert new variable value; or overwrite.
3356 if (*LiveOut != TransferIt->second) {
3357 *LiveOut = TransferIt->second;
3358 OLChanged = true;
3359 }
3360 }
3361 } else {
3362 // Just copy live-ins to live-outs, for anything not transferred.
3363 if (*LiveOut != *LiveIn) {
3364 *LiveOut = *LiveIn;
3365 OLChanged = true;
3366 }
3367 }
3368
3369 // If no live-out value changed, there's no need to explore further.
3370 if (!OLChanged)
3371 continue;
3372
3373 // We should visit all successors. Ensure we'll visit any non-backedge
3374 // successors during this dataflow iteration; book backedge successors
3375 // to be visited next time around.
3376 for (auto *s : MBB->successors()) {
3377 // Ignore out of scope / not-to-be-explored successors.
3378 if (!LiveInIdx.contains(Val: s))
3379 continue;
3380
3381 unsigned Order = BBToOrder[s];
3382 if (Order > BBToOrder[MBB]) {
3383 if (OnWorklist.insert(Ptr: s).second)
3384 Worklist.push(x: Order);
3385 } else if (OnPending.insert(Ptr: s).second && (FirstTrip || OLChanged)) {
3386 Pending.push(x: Order);
3387 }
3388 }
3389 }
3390 Worklist.swap(pq&: Pending);
3391 std::swap(LHS&: OnWorklist, RHS&: OnPending);
3392 OnPending.clear();
3393 assert(Pending.empty());
3394 FirstTrip = false;
3395 }
3396
3397 // Save live-ins to output vector. Ignore any that are still marked as being
3398 // VPHIs with no location -- those are variables that we know the value of,
3399 // but are not actually available in the register file.
3400 for (auto *MBB : BlockOrders) {
3401 DbgValue *BlockLiveIn = LiveInIdx[MBB];
3402 if (BlockLiveIn->Kind == DbgValue::NoVal)
3403 continue;
3404 if (BlockLiveIn->isUnjoinedPHI())
3405 continue;
3406 if (BlockLiveIn->Kind == DbgValue::VPHI)
3407 BlockLiveIn->Kind = DbgValue::Def;
3408 [[maybe_unused]] auto &[Var, DILoc] = DVMap.lookupDVID(ID: VarID);
3409 assert(BlockLiveIn->Properties.DIExpr->getFragmentInfo() ==
3410 Var.getFragment() &&
3411 "Fragment info missing during value prop");
3412 Output[MBB->getNumber()].push_back(Elt: std::make_pair(x&: VarID, y&: *BlockLiveIn));
3413 }
3414 } // Per-variable loop.
3415
3416 BlockOrders.clear();
3417 BlocksToExplore.clear();
3418}
3419
3420void InstrRefBasedLDV::placePHIsForSingleVarDefinition(
3421 const SmallPtrSetImpl<MachineBasicBlock *> &InScopeBlocks,
3422 MachineBasicBlock *AssignMBB, SmallVectorImpl<VLocTracker> &AllTheVLocs,
3423 DebugVariableID VarID, LiveInsT &Output) {
3424 // If there is a single definition of the variable, then working out it's
3425 // value everywhere is very simple: it's every block dominated by the
3426 // definition. At the dominance frontier, the usual algorithm would:
3427 // * Place PHIs,
3428 // * Propagate values into them,
3429 // * Find there's no incoming variable value from the other incoming branches
3430 // of the dominance frontier,
3431 // * Specify there's no variable value in blocks past the frontier.
3432 // This is a common case, hence it's worth special-casing it.
3433
3434 // Pick out the variables value from the block transfer function.
3435 VLocTracker &VLocs = AllTheVLocs[AssignMBB->getNumber()];
3436 auto ValueIt = VLocs.Vars.find(Key: VarID);
3437 const DbgValue &Value = ValueIt->second;
3438
3439 // If it's an explicit assignment of "undef", that means there is no location
3440 // anyway, anywhere.
3441 if (Value.Kind == DbgValue::Undef)
3442 return;
3443
3444 // Assign the variable value to entry to each dominated block that's in scope.
3445 // Skip the definition block -- it's assigned the variable value in the middle
3446 // of the block somewhere.
3447 for (auto *ScopeBlock : InScopeBlocks) {
3448 if (!DomTree->properlyDominates(A: AssignMBB, B: ScopeBlock))
3449 continue;
3450
3451 Output[ScopeBlock->getNumber()].push_back(Elt: {VarID, Value});
3452 }
3453
3454 // All blocks that aren't dominated have no live-in value, thus no variable
3455 // value will be given to them.
3456}
3457
3458#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3459void InstrRefBasedLDV::dump_mloc_transfer(
3460 const MLocTransferMap &mloc_transfer) const {
3461 for (const auto &P : mloc_transfer) {
3462 std::string foo = MTracker->LocIdxToName(P.first);
3463 std::string bar = MTracker->IDAsString(P.second);
3464 dbgs() << "Loc " << foo << " --> " << bar << "\n";
3465 }
3466}
3467#endif
3468
3469void InstrRefBasedLDV::initialSetup(MachineFunction &MF) {
3470 // Build some useful data structures.
3471
3472 LLVMContext &Context = MF.getFunction().getContext();
3473 EmptyExpr = DIExpression::get(Context, Elements: {});
3474
3475 auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
3476 if (const DebugLoc &DL = MI.getDebugLoc())
3477 return DL.getLine() != 0;
3478 return false;
3479 };
3480
3481 // Collect a set of all the artificial blocks. Collect the size too, ilist
3482 // size calls are O(n).
3483 unsigned int Size = 0;
3484 for (auto &MBB : MF) {
3485 ++Size;
3486 if (none_of(Range: MBB.instrs(), P: hasNonArtificialLocation))
3487 ArtificialBlocks.insert(Ptr: &MBB);
3488 }
3489
3490 // Compute mappings of block <=> RPO order.
3491 ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
3492 unsigned int RPONumber = 0;
3493 OrderToBB.reserve(N: Size);
3494 BBToOrder.reserve(NumEntries: Size);
3495 BBNumToRPO.reserve(NumEntries: Size);
3496 auto processMBB = [&](MachineBasicBlock *MBB) {
3497 OrderToBB.push_back(Elt: MBB);
3498 BBToOrder[MBB] = RPONumber;
3499 BBNumToRPO[MBB->getNumber()] = RPONumber;
3500 ++RPONumber;
3501 };
3502 for (MachineBasicBlock *MBB : RPOT)
3503 processMBB(MBB);
3504 for (MachineBasicBlock &MBB : MF)
3505 if (!BBToOrder.contains(Val: &MBB))
3506 processMBB(&MBB);
3507
3508 // Order value substitutions by their "source" operand pair, for quick lookup.
3509 llvm::sort(C&: MF.DebugValueSubstitutions);
3510
3511#ifdef EXPENSIVE_CHECKS
3512 // As an expensive check, test whether there are any duplicate substitution
3513 // sources in the collection.
3514 if (MF.DebugValueSubstitutions.size() > 2) {
3515 for (auto It = MF.DebugValueSubstitutions.begin();
3516 It != std::prev(MF.DebugValueSubstitutions.end()); ++It) {
3517 assert(It->Src != std::next(It)->Src && "Duplicate variable location "
3518 "substitution seen");
3519 }
3520 }
3521#endif
3522}
3523
3524// Produce an "ejection map" for blocks, i.e., what's the highest-numbered
3525// lexical scope it's used in. When exploring in DFS order and we pass that
3526// scope, the block can be processed and any tracking information freed.
3527void InstrRefBasedLDV::makeDepthFirstEjectionMap(
3528 SmallVectorImpl<unsigned> &EjectionMap,
3529 const ScopeToDILocT &ScopeToDILocation,
3530 ScopeToAssignBlocksT &ScopeToAssignBlocks) {
3531 SmallPtrSet<const MachineBasicBlock *, 8> BlocksToExplore;
3532 SmallVector<std::pair<LexicalScope *, ssize_t>, 4> WorkStack;
3533 auto *TopScope = LS.getCurrentFunctionScope();
3534
3535 // Unlike lexical scope explorers, we explore in reverse order, to find the
3536 // "last" lexical scope used for each block early.
3537 WorkStack.push_back(Elt: {TopScope, TopScope->getChildren().size() - 1});
3538
3539 while (!WorkStack.empty()) {
3540 auto &ScopePosition = WorkStack.back();
3541 LexicalScope *WS = ScopePosition.first;
3542 ssize_t ChildNum = ScopePosition.second--;
3543
3544 const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
3545 if (ChildNum >= 0) {
3546 // If ChildNum is positive, there are remaining children to explore.
3547 // Push the child and its children-count onto the stack.
3548 auto &ChildScope = Children[ChildNum];
3549 WorkStack.push_back(
3550 Elt: std::make_pair(x: ChildScope, y: ChildScope->getChildren().size() - 1));
3551 } else {
3552 WorkStack.pop_back();
3553
3554 // We've explored all children and any later blocks: examine all blocks
3555 // in our scope. If they haven't yet had an ejection number set, then
3556 // this scope will be the last to use that block.
3557 auto DILocationIt = ScopeToDILocation.find(Val: WS);
3558 if (DILocationIt != ScopeToDILocation.end()) {
3559 getBlocksForScope(DILoc: DILocationIt->second, BlocksToExplore,
3560 AssignBlocks: ScopeToAssignBlocks.find(Val: WS)->second);
3561 for (const auto *MBB : BlocksToExplore) {
3562 unsigned BBNum = MBB->getNumber();
3563 if (EjectionMap[BBNum] == 0)
3564 EjectionMap[BBNum] = WS->getDFSOut();
3565 }
3566
3567 BlocksToExplore.clear();
3568 }
3569 }
3570 }
3571}
3572
3573bool InstrRefBasedLDV::depthFirstVLocAndEmit(
3574 unsigned MaxNumBlocks, const ScopeToDILocT &ScopeToDILocation,
3575 const ScopeToVarsT &ScopeToVars, ScopeToAssignBlocksT &ScopeToAssignBlocks,
3576 LiveInsT &Output, FuncValueTable &MOutLocs, FuncValueTable &MInLocs,
3577 SmallVectorImpl<VLocTracker> &AllTheVLocs, MachineFunction &MF,
3578 bool ShouldEmitDebugEntryValues) {
3579 TTracker = new TransferTracker(TII, MTracker, MF, DVMap, *TRI,
3580 CalleeSavedRegs, ShouldEmitDebugEntryValues);
3581 unsigned NumLocs = MTracker->getNumLocs();
3582 VTracker = nullptr;
3583
3584 // No scopes? No variable locations.
3585 if (!LS.getCurrentFunctionScope())
3586 return false;
3587
3588 // Build map from block number to the last scope that uses the block.
3589 SmallVector<unsigned, 16> EjectionMap;
3590 EjectionMap.resize(N: MaxNumBlocks, NV: 0);
3591 makeDepthFirstEjectionMap(EjectionMap, ScopeToDILocation,
3592 ScopeToAssignBlocks);
3593
3594 // Helper lambda for ejecting a block -- if nothing is going to use the block,
3595 // we can translate the variable location information into DBG_VALUEs and then
3596 // free all of InstrRefBasedLDV's data structures.
3597 auto EjectBlock = [&](MachineBasicBlock &MBB) -> void {
3598 unsigned BBNum = MBB.getNumber();
3599 AllTheVLocs[BBNum].clear();
3600
3601 // Prime the transfer-tracker, and then step through all the block
3602 // instructions, installing transfers.
3603 MTracker->reset();
3604 MTracker->loadFromArray(Locs&: MInLocs[MBB], NewCurBB: BBNum);
3605 TTracker->loadInlocs(MBB, MLocs&: MInLocs[MBB], DbgOpStore, VLocs: Output[BBNum], NumLocs);
3606
3607 CurBB = BBNum;
3608 CurInst = 1;
3609 for (auto &MI : MBB) {
3610 process(MI, MLiveOuts: &MOutLocs, MLiveIns: &MInLocs);
3611 TTracker->checkInstForNewValues(Inst: CurInst, pos: MI.getIterator());
3612 ++CurInst;
3613 }
3614
3615 // Free machine-location tables for this block.
3616 MInLocs.ejectTableForBlock(MBB);
3617 MOutLocs.ejectTableForBlock(MBB);
3618 // We don't need live-in variable values for this block either.
3619 Output[BBNum].clear();
3620 AllTheVLocs[BBNum].clear();
3621 };
3622
3623 SmallPtrSet<const MachineBasicBlock *, 8> BlocksToExplore;
3624 SmallVector<std::pair<LexicalScope *, ssize_t>, 4> WorkStack;
3625 WorkStack.push_back(Elt: {LS.getCurrentFunctionScope(), 0});
3626 unsigned HighestDFSIn = 0;
3627
3628 // Proceed to explore in depth first order.
3629 while (!WorkStack.empty()) {
3630 auto &ScopePosition = WorkStack.back();
3631 LexicalScope *WS = ScopePosition.first;
3632 ssize_t ChildNum = ScopePosition.second++;
3633
3634 // We obesrve scopes with children twice here, once descending in, once
3635 // ascending out of the scope nest. Use HighestDFSIn as a ratchet to ensure
3636 // we don't process a scope twice. Additionally, ignore scopes that don't
3637 // have a DILocation -- by proxy, this means we never tracked any variable
3638 // assignments in that scope.
3639 auto DILocIt = ScopeToDILocation.find(Val: WS);
3640 if (HighestDFSIn <= WS->getDFSIn() && DILocIt != ScopeToDILocation.end()) {
3641 const DILocation *DILoc = DILocIt->second;
3642 auto &VarsWeCareAbout = ScopeToVars.find(Val: WS)->second;
3643 auto &BlocksInScope = ScopeToAssignBlocks.find(Val: WS)->second;
3644
3645 buildVLocValueMap(DILoc, VarsWeCareAbout, AssignBlocks&: BlocksInScope, Output, MOutLocs,
3646 MInLocs, AllTheVLocs);
3647 }
3648
3649 HighestDFSIn = std::max(a: HighestDFSIn, b: WS->getDFSIn());
3650
3651 // Descend into any scope nests.
3652 const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
3653 if (ChildNum < (ssize_t)Children.size()) {
3654 // There are children to explore -- push onto stack and continue.
3655 auto &ChildScope = Children[ChildNum];
3656 WorkStack.push_back(Elt: std::make_pair(x: ChildScope, y: 0));
3657 } else {
3658 WorkStack.pop_back();
3659
3660 // We've explored a leaf, or have explored all the children of a scope.
3661 // Try to eject any blocks where this is the last scope it's relevant to.
3662 auto DILocationIt = ScopeToDILocation.find(Val: WS);
3663 if (DILocationIt == ScopeToDILocation.end())
3664 continue;
3665
3666 getBlocksForScope(DILoc: DILocationIt->second, BlocksToExplore,
3667 AssignBlocks: ScopeToAssignBlocks.find(Val: WS)->second);
3668 for (const auto *MBB : BlocksToExplore)
3669 if (WS->getDFSOut() == EjectionMap[MBB->getNumber()])
3670 EjectBlock(const_cast<MachineBasicBlock &>(*MBB));
3671
3672 BlocksToExplore.clear();
3673 }
3674 }
3675
3676 // Some artificial blocks may not have been ejected, meaning they're not
3677 // connected to an actual legitimate scope. This can technically happen
3678 // with things like the entry block. In theory, we shouldn't need to do
3679 // anything for such out-of-scope blocks, but for the sake of being similar
3680 // to VarLocBasedLDV, eject these too.
3681 for (auto *MBB : ArtificialBlocks)
3682 if (MInLocs.hasTableFor(MBB&: *MBB))
3683 EjectBlock(*MBB);
3684
3685 return emitTransfers();
3686}
3687
3688bool InstrRefBasedLDV::emitTransfers() {
3689 // Go through all the transfers recorded in the TransferTracker -- this is
3690 // both the live-ins to a block, and any movements of values that happen
3691 // in the middle.
3692 for (auto &P : TTracker->Transfers) {
3693 // We have to insert DBG_VALUEs in a consistent order, otherwise they
3694 // appear in DWARF in different orders. Use the order that they appear
3695 // when walking through each block / each instruction, stored in
3696 // DVMap.
3697 llvm::sort(C&: P.Insts, Comp: llvm::less_first());
3698
3699 // Insert either before or after the designated point...
3700 if (P.MBB) {
3701 MachineBasicBlock &MBB = *P.MBB;
3702 for (const auto &Pair : P.Insts)
3703 MBB.insert(I: P.Pos, M: Pair.second);
3704 } else {
3705 // Terminators, like tail calls, can clobber things. Don't try and place
3706 // transfers after them.
3707 if (P.Pos->isTerminator())
3708 continue;
3709
3710 MachineBasicBlock &MBB = *P.Pos->getParent();
3711 for (const auto &Pair : P.Insts)
3712 MBB.insertAfterBundle(I: P.Pos, MI: Pair.second);
3713 }
3714 }
3715
3716 return TTracker->Transfers.size() != 0;
3717}
3718
3719/// Calculate the liveness information for the given machine function and
3720/// extend ranges across basic blocks.
3721bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
3722 MachineDominatorTree *DomTree,
3723 bool ShouldEmitDebugEntryValues,
3724 unsigned InputBBLimit,
3725 unsigned InputDbgValLimit) {
3726 // No subprogram means this function contains no debuginfo.
3727 if (!MF.getFunction().getSubprogram())
3728 return false;
3729
3730 LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
3731
3732 this->DomTree = DomTree;
3733 TRI = MF.getSubtarget().getRegisterInfo();
3734 MRI = &MF.getRegInfo();
3735 TII = MF.getSubtarget().getInstrInfo();
3736 TFI = MF.getSubtarget().getFrameLowering();
3737 TFI->getCalleeSaves(MF, SavedRegs&: CalleeSavedRegs);
3738 MFI = &MF.getFrameInfo();
3739 LS.scanFunction(MF);
3740
3741 const auto &STI = MF.getSubtarget();
3742 AdjustsStackInCalls = MFI->adjustsStack() &&
3743 STI.getFrameLowering()->stackProbeFunctionModifiesSP();
3744 if (AdjustsStackInCalls)
3745 StackProbeSymbolName = STI.getTargetLowering()->getStackProbeSymbolName(MF);
3746
3747 MTracker =
3748 new MLocTracker(MF, *TII, *TRI, *MF.getSubtarget().getTargetLowering());
3749 VTracker = nullptr;
3750 TTracker = nullptr;
3751
3752 LLVM_DEBUG(if (MTracker->NumSlotIdxes >= StackSlotIdxesLimit) {
3753 dbgs() << "Disabling InstrRefBasedLDV spill tracking for " << MF.getName()
3754 << " since target has too many potential stack slot indexes ("
3755 << MTracker->NumSlotIdxes << ", limit is " << StackSlotIdxesLimit
3756 << ")\n";
3757 });
3758
3759 SmallVector<MLocTransferMap, 32> MLocTransfer;
3760 SmallVector<VLocTracker, 8> vlocs;
3761 LiveInsT SavedLiveIns;
3762
3763 int MaxNumBlocks = -1;
3764 for (auto &MBB : MF)
3765 MaxNumBlocks = std::max(a: MBB.getNumber(), b: MaxNumBlocks);
3766 assert(MaxNumBlocks >= 0);
3767 ++MaxNumBlocks;
3768
3769 initialSetup(MF);
3770
3771 MLocTransfer.resize(N: MaxNumBlocks);
3772 vlocs.resize(N: MaxNumBlocks, NV: VLocTracker(DVMap, OverlapFragments, EmptyExpr));
3773 SavedLiveIns.resize(N: MaxNumBlocks);
3774
3775 produceMLocTransferFunction(MF, MLocTransfer, MaxNumBlocks);
3776
3777 // Allocate and initialize two array-of-arrays for the live-in and live-out
3778 // machine values. The outer dimension is the block number; while the inner
3779 // dimension is a LocIdx from MLocTracker.
3780 unsigned NumLocs = MTracker->getNumLocs();
3781 FuncValueTable MOutLocs(MaxNumBlocks, NumLocs);
3782 FuncValueTable MInLocs(MaxNumBlocks, NumLocs);
3783
3784 // Solve the machine value dataflow problem using the MLocTransfer function,
3785 // storing the computed live-ins / live-outs into the array-of-arrays. We use
3786 // both live-ins and live-outs for decision making in the variable value
3787 // dataflow problem.
3788 buildMLocValueMap(MF, MInLocs, MOutLocs, MLocTransfer);
3789
3790 // Patch up debug phi numbers, turning unknown block-live-in values into
3791 // either live-through machine values, or PHIs.
3792 for (auto &DBG_PHI : DebugPHINumToValue) {
3793 // Identify unresolved block-live-ins.
3794 if (!DBG_PHI.ValueRead)
3795 continue;
3796
3797 ValueIDNum &Num = *DBG_PHI.ValueRead;
3798 if (!Num.isPHI())
3799 continue;
3800
3801 unsigned BlockNo = Num.getBlock();
3802 LocIdx LocNo = Num.getLoc();
3803 ValueIDNum ResolvedValue = MInLocs[BlockNo][LocNo.asU64()];
3804 // If there is no resolved value for this live-in then it is not directly
3805 // reachable from the entry block -- model it as a PHI on entry to this
3806 // block, which means we leave the ValueIDNum unchanged.
3807 if (ResolvedValue != ValueIDNum::EmptyValue)
3808 Num = ResolvedValue;
3809 }
3810 // Later, we'll be looking up ranges of instruction numbers.
3811 llvm::sort(C&: DebugPHINumToValue);
3812
3813 // Walk back through each block / instruction, collecting DBG_VALUE
3814 // instructions and recording what machine value their operands refer to.
3815 for (MachineBasicBlock *MBB : OrderToBB) {
3816 CurBB = MBB->getNumber();
3817 VTracker = &vlocs[CurBB];
3818 VTracker->MBB = MBB;
3819 MTracker->loadFromArray(Locs&: MInLocs[*MBB], NewCurBB: CurBB);
3820 CurInst = 1;
3821 for (auto &MI : *MBB) {
3822 process(MI, MLiveOuts: &MOutLocs, MLiveIns: &MInLocs);
3823 ++CurInst;
3824 }
3825 MTracker->reset();
3826 }
3827
3828 // Map from one LexicalScope to all the variables in that scope.
3829 ScopeToVarsT ScopeToVars;
3830
3831 // Map from One lexical scope to all blocks where assignments happen for
3832 // that scope.
3833 ScopeToAssignBlocksT ScopeToAssignBlocks;
3834
3835 // Store map of DILocations that describes scopes.
3836 ScopeToDILocT ScopeToDILocation;
3837
3838 // To mirror old LiveDebugValues, enumerate variables in RPOT order. Otherwise
3839 // the order is unimportant, it just has to be stable.
3840 unsigned VarAssignCount = 0;
3841 for (MachineBasicBlock *MBB : OrderToBB) {
3842 auto *VTracker = &vlocs[MBB->getNumber()];
3843 // Collect each variable with a DBG_VALUE in this block.
3844 for (auto &idx : VTracker->Vars) {
3845 DebugVariableID VarID = idx.first;
3846 const DILocation *ScopeLoc = VTracker->Scopes[VarID];
3847 assert(ScopeLoc != nullptr);
3848 auto *Scope = LS.findLexicalScope(DL: ScopeLoc);
3849
3850 // No insts in scope -> shouldn't have been recorded.
3851 assert(Scope != nullptr);
3852
3853 ScopeToVars[Scope].insert(V: VarID);
3854 ScopeToAssignBlocks[Scope].insert(Ptr: VTracker->MBB);
3855 ScopeToDILocation[Scope] = ScopeLoc;
3856 ++VarAssignCount;
3857 }
3858 }
3859
3860 bool Changed = false;
3861
3862 // If we have an extremely large number of variable assignments and blocks,
3863 // bail out at this point. We've burnt some time doing analysis already,
3864 // however we should cut our losses.
3865 if ((unsigned)MaxNumBlocks > InputBBLimit &&
3866 VarAssignCount > InputDbgValLimit) {
3867 LLVM_DEBUG(dbgs() << "Disabling InstrRefBasedLDV: " << MF.getName()
3868 << " has " << MaxNumBlocks << " basic blocks and "
3869 << VarAssignCount
3870 << " variable assignments, exceeding limits.\n");
3871 } else {
3872 // Optionally, solve the variable value problem and emit to blocks by using
3873 // a lexical-scope-depth search. It should be functionally identical to
3874 // the "else" block of this condition.
3875 Changed = depthFirstVLocAndEmit(
3876 MaxNumBlocks, ScopeToDILocation, ScopeToVars, ScopeToAssignBlocks,
3877 Output&: SavedLiveIns, MOutLocs, MInLocs, AllTheVLocs&: vlocs, MF, ShouldEmitDebugEntryValues);
3878 }
3879
3880 delete MTracker;
3881 delete TTracker;
3882 MTracker = nullptr;
3883 VTracker = nullptr;
3884 TTracker = nullptr;
3885
3886 ArtificialBlocks.clear();
3887 OrderToBB.clear();
3888 BBToOrder.clear();
3889 BBNumToRPO.clear();
3890 DebugInstrNumToInstr.clear();
3891 DebugPHINumToValue.clear();
3892 OverlapFragments.clear();
3893 SeenFragments.clear();
3894 SeenDbgPHIs.clear();
3895 DbgOpStore.clear();
3896 DVMap.clear();
3897
3898 return Changed;
3899}
3900
3901LDVImpl *llvm::makeInstrRefBasedLiveDebugValues() {
3902 return new InstrRefBasedLDV();
3903}
3904
3905namespace {
3906class LDVSSABlock;
3907class LDVSSAUpdater;
3908
3909// Pick a type to identify incoming block values as we construct SSA. We
3910// can't use anything more robust than an integer unfortunately, as SSAUpdater
3911// expects to zero-initialize the type.
3912typedef uint64_t BlockValueNum;
3913
3914/// Represents an SSA PHI node for the SSA updater class. Contains the block
3915/// this PHI is in, the value number it would have, and the expected incoming
3916/// values from parent blocks.
3917class LDVSSAPhi {
3918public:
3919 SmallVector<std::pair<LDVSSABlock *, BlockValueNum>, 4> IncomingValues;
3920 LDVSSABlock *ParentBlock;
3921 BlockValueNum PHIValNum;
3922 LDVSSAPhi(BlockValueNum PHIValNum, LDVSSABlock *ParentBlock)
3923 : ParentBlock(ParentBlock), PHIValNum(PHIValNum) {}
3924
3925 LDVSSABlock *getParent() { return ParentBlock; }
3926};
3927
3928/// Thin wrapper around a block predecessor iterator. Only difference from a
3929/// normal block iterator is that it dereferences to an LDVSSABlock.
3930class LDVSSABlockIterator {
3931public:
3932 MachineBasicBlock::pred_iterator PredIt;
3933 LDVSSAUpdater &Updater;
3934
3935 LDVSSABlockIterator(MachineBasicBlock::pred_iterator PredIt,
3936 LDVSSAUpdater &Updater)
3937 : PredIt(PredIt), Updater(Updater) {}
3938
3939 bool operator!=(const LDVSSABlockIterator &OtherIt) const {
3940 return OtherIt.PredIt != PredIt;
3941 }
3942
3943 LDVSSABlockIterator &operator++() {
3944 ++PredIt;
3945 return *this;
3946 }
3947
3948 LDVSSABlock *operator*();
3949};
3950
3951/// Thin wrapper around a block for SSA Updater interface. Necessary because
3952/// we need to track the PHI value(s) that we may have observed as necessary
3953/// in this block.
3954class LDVSSABlock {
3955public:
3956 MachineBasicBlock &BB;
3957 LDVSSAUpdater &Updater;
3958 using PHIListT = SmallVector<LDVSSAPhi, 1>;
3959 /// List of PHIs in this block. There should only ever be one.
3960 PHIListT PHIList;
3961
3962 LDVSSABlock(MachineBasicBlock &BB, LDVSSAUpdater &Updater)
3963 : BB(BB), Updater(Updater) {}
3964
3965 LDVSSABlockIterator succ_begin() {
3966 return LDVSSABlockIterator(BB.succ_begin(), Updater);
3967 }
3968
3969 LDVSSABlockIterator succ_end() {
3970 return LDVSSABlockIterator(BB.succ_end(), Updater);
3971 }
3972
3973 /// SSAUpdater has requested a PHI: create that within this block record.
3974 LDVSSAPhi *newPHI(BlockValueNum Value) {
3975 PHIList.emplace_back(Args&: Value, Args: this);
3976 return &PHIList.back();
3977 }
3978
3979 /// SSAUpdater wishes to know what PHIs already exist in this block.
3980 PHIListT &phis() { return PHIList; }
3981};
3982
3983/// Utility class for the SSAUpdater interface: tracks blocks, PHIs and values
3984/// while SSAUpdater is exploring the CFG. It's passed as a handle / baton to
3985// SSAUpdaterTraits<LDVSSAUpdater>.
3986class LDVSSAUpdater {
3987public:
3988 /// Map of value numbers to PHI records.
3989 DenseMap<BlockValueNum, LDVSSAPhi *> PHIs;
3990 /// Map of which blocks generate Undef values -- blocks that are not
3991 /// dominated by any Def.
3992 DenseMap<MachineBasicBlock *, BlockValueNum> PoisonMap;
3993 /// Map of machine blocks to our own records of them.
3994 DenseMap<MachineBasicBlock *, LDVSSABlock *> BlockMap;
3995 /// Machine location where any PHI must occur.
3996 LocIdx Loc;
3997 /// Table of live-in machine value numbers for blocks / locations.
3998 const FuncValueTable &MLiveIns;
3999
4000 LDVSSAUpdater(LocIdx L, const FuncValueTable &MLiveIns)
4001 : Loc(L), MLiveIns(MLiveIns) {}
4002
4003 void reset() {
4004 for (auto &Block : BlockMap)
4005 delete Block.second;
4006
4007 PHIs.clear();
4008 PoisonMap.clear();
4009 BlockMap.clear();
4010 }
4011
4012 ~LDVSSAUpdater() { reset(); }
4013
4014 /// For a given MBB, create a wrapper block for it. Stores it in the
4015 /// LDVSSAUpdater block map.
4016 LDVSSABlock *getSSALDVBlock(MachineBasicBlock *BB) {
4017 auto [It, Inserted] = BlockMap.try_emplace(Key: BB);
4018 if (Inserted)
4019 It->second = new LDVSSABlock(*BB, *this);
4020 return It->second;
4021 }
4022
4023 /// Find the live-in value number for the given block. Looks up the value at
4024 /// the PHI location on entry.
4025 BlockValueNum getValue(LDVSSABlock *LDVBB) {
4026 return MLiveIns[LDVBB->BB][Loc.asU64()].asU64();
4027 }
4028};
4029
4030LDVSSABlock *LDVSSABlockIterator::operator*() {
4031 return Updater.getSSALDVBlock(BB: *PredIt);
4032}
4033
4034#ifndef NDEBUG
4035
4036raw_ostream &operator<<(raw_ostream &out, const LDVSSAPhi &PHI) {
4037 out << "SSALDVPHI " << PHI.PHIValNum;
4038 return out;
4039}
4040
4041#endif
4042
4043} // namespace
4044
4045namespace llvm {
4046
4047/// Template specialization to give SSAUpdater access to CFG and value
4048/// information. SSAUpdater calls methods in these traits, passing in the
4049/// LDVSSAUpdater object, to learn about blocks and the values they define.
4050/// It also provides methods to create PHI nodes and track them.
4051template <> class SSAUpdaterTraits<LDVSSAUpdater> {
4052public:
4053 using BlkT = LDVSSABlock;
4054 using ValT = BlockValueNum;
4055 using PhiT = LDVSSAPhi;
4056 using BlkSucc_iterator = LDVSSABlockIterator;
4057
4058 // Methods to access block successors -- dereferencing to our wrapper class.
4059 static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); }
4060 static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); }
4061
4062 /// Iterator for PHI operands.
4063 class PHI_iterator {
4064 private:
4065 LDVSSAPhi *PHI;
4066 unsigned Idx;
4067
4068 public:
4069 explicit PHI_iterator(LDVSSAPhi *P) // begin iterator
4070 : PHI(P), Idx(0) {}
4071 PHI_iterator(LDVSSAPhi *P, bool) // end iterator
4072 : PHI(P), Idx(PHI->IncomingValues.size()) {}
4073
4074 PHI_iterator &operator++() {
4075 Idx++;
4076 return *this;
4077 }
4078 bool operator==(const PHI_iterator &X) const { return Idx == X.Idx; }
4079 bool operator!=(const PHI_iterator &X) const { return !operator==(X); }
4080
4081 BlockValueNum getIncomingValue() { return PHI->IncomingValues[Idx].second; }
4082
4083 LDVSSABlock *getIncomingBlock() { return PHI->IncomingValues[Idx].first; }
4084 };
4085
4086 static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
4087
4088 static inline PHI_iterator PHI_end(PhiT *PHI) {
4089 return PHI_iterator(PHI, true);
4090 }
4091
4092 /// FindPredecessorBlocks - Put the predecessors of BB into the Preds
4093 /// vector.
4094 static void FindPredecessorBlocks(LDVSSABlock *BB,
4095 SmallVectorImpl<LDVSSABlock *> *Preds) {
4096 for (MachineBasicBlock *Pred : BB->BB.predecessors())
4097 Preds->push_back(Elt: BB->Updater.getSSALDVBlock(BB: Pred));
4098 }
4099
4100 /// GetPoisonVal - Normally creates an IMPLICIT_DEF instruction with a new
4101 /// register. For LiveDebugValues, represents a block identified as not having
4102 /// any DBG_PHI predecessors.
4103 static BlockValueNum GetPoisonVal(LDVSSABlock *BB, LDVSSAUpdater *Updater) {
4104 // Create a value number for this block -- it needs to be unique and in the
4105 // "poison" collection, so that we know it's not real. Use a number
4106 // representing a PHI into this block.
4107 BlockValueNum Num = ValueIDNum(BB->BB.getNumber(), 0, Updater->Loc).asU64();
4108 Updater->PoisonMap[&BB->BB] = Num;
4109 return Num;
4110 }
4111
4112 /// CreateEmptyPHI - Create a (representation of a) PHI in the given block.
4113 /// SSAUpdater will populate it with information about incoming values. The
4114 /// value number of this PHI is whatever the machine value number problem
4115 /// solution determined it to be. This includes non-phi values if SSAUpdater
4116 /// tries to create a PHI where the incoming values are identical.
4117 static BlockValueNum CreateEmptyPHI(LDVSSABlock *BB, unsigned NumPreds,
4118 LDVSSAUpdater *Updater) {
4119 BlockValueNum PHIValNum = Updater->getValue(LDVBB: BB);
4120 LDVSSAPhi *PHI = BB->newPHI(Value: PHIValNum);
4121 Updater->PHIs[PHIValNum] = PHI;
4122 return PHIValNum;
4123 }
4124
4125 /// AddPHIOperand - Add the specified value as an operand of the PHI for
4126 /// the specified predecessor block.
4127 static void AddPHIOperand(LDVSSAPhi *PHI, BlockValueNum Val, LDVSSABlock *Pred) {
4128 PHI->IncomingValues.push_back(Elt: std::make_pair(x&: Pred, y&: Val));
4129 }
4130
4131 /// ValueIsPHI - Check if the instruction that defines the specified value
4132 /// is a PHI instruction.
4133 static LDVSSAPhi *ValueIsPHI(BlockValueNum Val, LDVSSAUpdater *Updater) {
4134 return Updater->PHIs.lookup(Val);
4135 }
4136
4137 /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
4138 /// operands, i.e., it was just added.
4139 static LDVSSAPhi *ValueIsNewPHI(BlockValueNum Val, LDVSSAUpdater *Updater) {
4140 LDVSSAPhi *PHI = ValueIsPHI(Val, Updater);
4141 if (PHI && PHI->IncomingValues.size() == 0)
4142 return PHI;
4143 return nullptr;
4144 }
4145
4146 /// GetPHIValue - For the specified PHI instruction, return the value
4147 /// that it defines.
4148 static BlockValueNum GetPHIValue(LDVSSAPhi *PHI) { return PHI->PHIValNum; }
4149};
4150
4151} // end namespace llvm
4152
4153std::optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIs(
4154 MachineFunction &MF, const FuncValueTable &MLiveOuts,
4155 const FuncValueTable &MLiveIns, MachineInstr &Here, uint64_t InstrNum) {
4156 // This function will be called twice per DBG_INSTR_REF, and might end up
4157 // computing lots of SSA information: memoize it.
4158 auto SeenDbgPHIIt = SeenDbgPHIs.find(Val: std::make_pair(x: &Here, y&: InstrNum));
4159 if (SeenDbgPHIIt != SeenDbgPHIs.end())
4160 return SeenDbgPHIIt->second;
4161
4162 std::optional<ValueIDNum> Result =
4163 resolveDbgPHIsImpl(MF, MLiveOuts, MLiveIns, Here, InstrNum);
4164 SeenDbgPHIs.insert(KV: {std::make_pair(x: &Here, y&: InstrNum), Result});
4165 return Result;
4166}
4167
4168std::optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIsImpl(
4169 MachineFunction &MF, const FuncValueTable &MLiveOuts,
4170 const FuncValueTable &MLiveIns, MachineInstr &Here, uint64_t InstrNum) {
4171 // Pick out records of DBG_PHI instructions that have been observed. If there
4172 // are none, then we cannot compute a value number.
4173 auto RangePair = std::equal_range(first: DebugPHINumToValue.begin(),
4174 last: DebugPHINumToValue.end(), val: InstrNum);
4175 auto LowerIt = RangePair.first;
4176 auto UpperIt = RangePair.second;
4177
4178 // No DBG_PHI means there can be no location.
4179 if (LowerIt == UpperIt)
4180 return std::nullopt;
4181
4182 // If any DBG_PHIs referred to a location we didn't understand, don't try to
4183 // compute a value. There might be scenarios where we could recover a value
4184 // for some range of DBG_INSTR_REFs, but at this point we can have high
4185 // confidence that we've seen a bug.
4186 auto DBGPHIRange = make_range(x: LowerIt, y: UpperIt);
4187 for (const DebugPHIRecord &DBG_PHI : DBGPHIRange)
4188 if (!DBG_PHI.ValueRead)
4189 return std::nullopt;
4190
4191 // If there's only one DBG_PHI, then that is our value number.
4192 if (std::distance(first: LowerIt, last: UpperIt) == 1)
4193 return *LowerIt->ValueRead;
4194
4195 // Pick out the location (physreg, slot) where any PHIs must occur. It's
4196 // technically possible for us to merge values in different registers in each
4197 // block, but highly unlikely that LLVM will generate such code after register
4198 // allocation.
4199 LocIdx Loc = *LowerIt->ReadLoc;
4200
4201 // We have several DBG_PHIs, and a use position (the Here inst). All each
4202 // DBG_PHI does is identify a value at a program position. We can treat each
4203 // DBG_PHI like it's a Def of a value, and the use position is a Use of a
4204 // value, just like SSA. We use the bulk-standard LLVM SSA updater class to
4205 // determine which Def is used at the Use, and any PHIs that happen along
4206 // the way.
4207 // Adapted LLVM SSA Updater:
4208 LDVSSAUpdater Updater(Loc, MLiveIns);
4209 // Map of which Def or PHI is the current value in each block.
4210 DenseMap<LDVSSABlock *, BlockValueNum> AvailableValues;
4211 // Set of PHIs that we have created along the way.
4212 SmallVector<LDVSSAPhi *, 8> CreatedPHIs;
4213
4214 // Each existing DBG_PHI is a Def'd value under this model. Record these Defs
4215 // for the SSAUpdater.
4216 for (const auto &DBG_PHI : DBGPHIRange) {
4217 LDVSSABlock *Block = Updater.getSSALDVBlock(BB: DBG_PHI.MBB);
4218 const ValueIDNum &Num = *DBG_PHI.ValueRead;
4219 AvailableValues.insert(KV: std::make_pair(x&: Block, y: Num.asU64()));
4220 }
4221
4222 LDVSSABlock *HereBlock = Updater.getSSALDVBlock(BB: Here.getParent());
4223 const auto &AvailIt = AvailableValues.find(Val: HereBlock);
4224 if (AvailIt != AvailableValues.end()) {
4225 // Actually, we already know what the value is -- the Use is in the same
4226 // block as the Def.
4227 return ValueIDNum::fromU64(v: AvailIt->second);
4228 }
4229
4230 // Otherwise, we must use the SSA Updater. It will identify the value number
4231 // that we are to use, and the PHIs that must happen along the way.
4232 SSAUpdaterImpl<LDVSSAUpdater> Impl(&Updater, &AvailableValues, &CreatedPHIs);
4233 BlockValueNum ResultInt = Impl.GetValue(BB: Updater.getSSALDVBlock(BB: Here.getParent()));
4234 ValueIDNum Result = ValueIDNum::fromU64(v: ResultInt);
4235
4236 // We have the number for a PHI, or possibly live-through value, to be used
4237 // at this Use. There are a number of things we have to check about it though:
4238 // * Does any PHI use an 'Undef' (like an IMPLICIT_DEF) value? If so, this
4239 // Use was not completely dominated by DBG_PHIs and we should abort.
4240 // * Are the Defs or PHIs clobbered in a block? SSAUpdater isn't aware that
4241 // we've left SSA form. Validate that the inputs to each PHI are the
4242 // expected values.
4243 // * Is a PHI we've created actually a merging of values, or are all the
4244 // predecessor values the same, leading to a non-PHI machine value number?
4245 // (SSAUpdater doesn't know that either). Remap validated PHIs into the
4246 // the ValidatedValues collection below to sort this out.
4247 DenseMap<LDVSSABlock *, ValueIDNum> ValidatedValues;
4248
4249 // Define all the input DBG_PHI values in ValidatedValues.
4250 for (const auto &DBG_PHI : DBGPHIRange) {
4251 LDVSSABlock *Block = Updater.getSSALDVBlock(BB: DBG_PHI.MBB);
4252 const ValueIDNum &Num = *DBG_PHI.ValueRead;
4253 ValidatedValues.insert(KV: std::make_pair(x&: Block, y: Num));
4254 }
4255
4256 // Sort PHIs to validate into RPO-order.
4257 SmallVector<LDVSSAPhi *, 8> SortedPHIs(CreatedPHIs);
4258
4259 llvm::sort(C&: SortedPHIs, Comp: [&](LDVSSAPhi *A, LDVSSAPhi *B) {
4260 return BBToOrder[&A->getParent()->BB] < BBToOrder[&B->getParent()->BB];
4261 });
4262
4263 for (auto &PHI : SortedPHIs) {
4264 ValueIDNum ThisBlockValueNum = MLiveIns[PHI->ParentBlock->BB][Loc.asU64()];
4265
4266 // Are all these things actually defined?
4267 for (auto &PHIIt : PHI->IncomingValues) {
4268 // Any undef input means DBG_PHIs didn't dominate the use point.
4269 if (Updater.PoisonMap.contains(Val: &PHIIt.first->BB))
4270 return std::nullopt;
4271
4272 ValueIDNum ValueToCheck;
4273 const ValueTable &BlockLiveOuts = MLiveOuts[PHIIt.first->BB];
4274
4275 auto VVal = ValidatedValues.find(Val: PHIIt.first);
4276 if (VVal == ValidatedValues.end()) {
4277 // We cross a loop, and this is a backedge. LLVMs tail duplication
4278 // happens so late that DBG_PHI instructions should not be able to
4279 // migrate into loops -- meaning we can only be live-through this
4280 // loop.
4281 ValueToCheck = ThisBlockValueNum;
4282 } else {
4283 // Does the block have as a live-out, in the location we're examining,
4284 // the value that we expect? If not, it's been moved or clobbered.
4285 ValueToCheck = VVal->second;
4286 }
4287
4288 if (BlockLiveOuts[Loc.asU64()] != ValueToCheck)
4289 return std::nullopt;
4290 }
4291
4292 // Record this value as validated.
4293 ValidatedValues.insert(KV: {PHI->ParentBlock, ThisBlockValueNum});
4294 }
4295
4296 // All the PHIs are valid: we can return what the SSAUpdater said our value
4297 // number was.
4298 return Result;
4299}
4300