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