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