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