LLVM  12.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, its current
80 /// machine-location, and the DBG_VALUE inst that specifies the location. Each
81 /// VarLoc is indexed in the (function-scope) \p VarLocMap, giving each VarLoc a
82 /// unique index. Rather than operate directly on machine locations, the
83 /// dataflow analysis in this pass identifies locations by their index in the
84 /// VarLocMap, meaning all the variable locations in a block can be described
85 /// by a sparse vector of VarLocMap indicies.
86 ///
87 /// All the storage for the dataflow analysis is local to the ExtendRanges
88 /// method and passed down to helper methods. "OutLocs" and "InLocs" record the
89 /// in and out lattice values for each block. "OpenRanges" maintains a list of
90 /// variable locations and, with the "process" method, evaluates the transfer
91 /// function of each block. "flushPendingLocs" installs DBG_VALUEs for each
92 /// live-in location at the start of blocks, while "Transfers" records
93 /// transfers of values between machine-locations.
94 ///
95 /// We avoid explicitly representing the "Unknown" (\top) lattice value in the
96 /// implementation. Instead, unvisited blocks implicitly have all lattice
97 /// values set as "Unknown". After being visited, there will be path back to
98 /// the entry block where the lattice value is "False", and as the transfer
99 /// function cannot make new "Unknown" locations, there are no scenarios where
100 /// a block can have an "Unknown" location after being visited. Similarly, we
101 /// don't enumerate all possible variable locations before exploring the
102 /// function: when a new location is discovered, all blocks previously explored
103 /// were implicitly "False" but unrecorded, and become explicitly "False" when
104 /// a new VarLoc is created with its bit not set in predecessor InLocs or
105 /// OutLocs.
106 ///
107 //===----------------------------------------------------------------------===//
108 
109 #include "LiveDebugValues.h"
110 
112 #include "llvm/ADT/DenseMap.h"
114 #include "llvm/ADT/SmallPtrSet.h"
115 #include "llvm/ADT/SmallSet.h"
116 #include "llvm/ADT/SmallVector.h"
117 #include "llvm/ADT/Statistic.h"
118 #include "llvm/ADT/UniqueVector.h"
136 #include "llvm/Config/llvm-config.h"
137 #include "llvm/IR/DIBuilder.h"
139 #include "llvm/IR/DebugLoc.h"
140 #include "llvm/IR/Function.h"
141 #include "llvm/IR/Module.h"
142 #include "llvm/InitializePasses.h"
143 #include "llvm/MC/MCRegisterInfo.h"
144 #include "llvm/Pass.h"
145 #include "llvm/Support/Casting.h"
146 #include "llvm/Support/Compiler.h"
147 #include "llvm/Support/Debug.h"
148 #include "llvm/Support/TypeSize.h"
151 #include <algorithm>
152 #include <cassert>
153 #include <cstdint>
154 #include <functional>
155 #include <queue>
156 #include <tuple>
157 #include <utility>
158 #include <vector>
159 
160 using namespace llvm;
161 
162 #define DEBUG_TYPE "livedebugvalues"
163 
164 STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
165 
166 // Options to prevent pathological compile-time behavior. If InputBBLimit and
167 // InputDbgValueLimit are both exceeded, range extension is disabled.
169  "livedebugvalues-input-bb-limit",
170  cl::desc("Maximum input basic blocks before DBG_VALUE limit applies"),
171  cl::init(10000), cl::Hidden);
173  "livedebugvalues-input-dbg-value-limit",
174  cl::desc(
175  "Maximum input DBG_VALUE insts supported by debug range extension"),
176  cl::init(50000), cl::Hidden);
177 
178 // If @MI is a DBG_VALUE with debug value described by a defined
179 // register, returns the number of this register. In the other case, returns 0.
181  assert(MI.isDebugValue() && "expected a DBG_VALUE");
182  assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
183  // If location of variable is described using a register (directly
184  // or indirectly), this register is always a first operand.
185  return MI.getDebugOperand(0).isReg() ? MI.getDebugOperand(0).getReg()
186  : Register();
187 }
188 
189 /// If \p Op is a stack or frame register return true, otherwise return false.
190 /// This is used to avoid basing the debug entry values on the registers, since
191 /// we do not support it at the moment.
193  const MachineInstr &MI,
194  const TargetRegisterInfo *TRI) {
195  if (!Op.isReg())
196  return false;
197 
198  const MachineFunction *MF = MI.getParent()->getParent();
199  const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
201  Register FP = TRI->getFrameRegister(*MF);
202  Register Reg = Op.getReg();
203 
204  return Reg && Reg != SP && Reg != FP;
205 }
206 
207 namespace {
208 
209 // Max out the number of statically allocated elements in DefinedRegsSet, as
210 // this prevents fallback to std::set::count() operations.
211 using DefinedRegsSet = SmallSet<Register, 32>;
212 
213 using VarLocSet = CoalescingBitVector<uint64_t>;
214 
215 /// A type-checked pair of {Register Location (or 0), Index}, used to index
216 /// into a \ref VarLocMap. This can be efficiently converted to a 64-bit int
217 /// for insertion into a \ref VarLocSet, and efficiently converted back. The
218 /// type-checker helps ensure that the conversions aren't lossy.
219 ///
220 /// Why encode a location /into/ the VarLocMap index? This makes it possible
221 /// to find the open VarLocs killed by a register def very quickly. This is a
222 /// performance-critical operation for LiveDebugValues.
223 struct LocIndex {
224  using u32_location_t = uint32_t;
225  using u32_index_t = uint32_t;
226 
227  u32_location_t Location; // Physical registers live in the range [1;2^30) (see
228  // \ref MCRegister), so we have plenty of range left
229  // here to encode non-register locations.
230  u32_index_t Index;
231 
232  /// The first location greater than 0 that is not reserved for VarLocs of
233  /// kind RegisterKind.
234  static constexpr u32_location_t kFirstInvalidRegLocation = 1 << 30;
235 
236  /// A special location reserved for VarLocs of kind SpillLocKind.
237  static constexpr u32_location_t kSpillLocation = kFirstInvalidRegLocation;
238 
239  /// A special location reserved for VarLocs of kind EntryValueBackupKind and
240  /// EntryValueCopyBackupKind.
241  static constexpr u32_location_t kEntryValueBackupLocation =
242  kFirstInvalidRegLocation + 1;
243 
244  LocIndex(u32_location_t Location, u32_index_t Index)
245  : Location(Location), Index(Index) {}
246 
247  uint64_t getAsRawInteger() const {
248  return (static_cast<uint64_t>(Location) << 32) | Index;
249  }
250 
251  template<typename IntT> static LocIndex fromRawInteger(IntT ID) {
252  static_assert(std::is_unsigned<IntT>::value &&
253  sizeof(ID) == sizeof(uint64_t),
254  "Cannot convert raw integer to LocIndex");
255  return {static_cast<u32_location_t>(ID >> 32),
256  static_cast<u32_index_t>(ID)};
257  }
258 
259  /// Get the start of the interval reserved for VarLocs of kind RegisterKind
260  /// which reside in \p Reg. The end is at rawIndexForReg(Reg+1)-1.
261  static uint64_t rawIndexForReg(uint32_t Reg) {
262  return LocIndex(Reg, 0).getAsRawInteger();
263  }
264 
265  /// Return a range covering all set indices in the interval reserved for
266  /// \p Location in \p Set.
267  static auto indexRangeForLocation(const VarLocSet &Set,
268  u32_location_t Location) {
269  uint64_t Start = LocIndex(Location, 0).getAsRawInteger();
270  uint64_t End = LocIndex(Location + 1, 0).getAsRawInteger();
271  return Set.half_open_range(Start, End);
272  }
273 };
274 
275 class VarLocBasedLDV : public LDVImpl {
276 private:
277  const TargetRegisterInfo *TRI;
278  const TargetInstrInfo *TII;
279  const TargetFrameLowering *TFI;
280  TargetPassConfig *TPC;
281  BitVector CalleeSavedRegs;
283  VarLocSet::Allocator Alloc;
284 
285  enum struct TransferKind { TransferCopy, TransferSpill, TransferRestore };
286 
287  using FragmentInfo = DIExpression::FragmentInfo;
288  using OptFragmentInfo = Optional<DIExpression::FragmentInfo>;
289 
290  /// A pair of debug variable and value location.
291  struct VarLoc {
292  // The location at which a spilled variable resides. It consists of a
293  // register and an offset.
294  struct SpillLoc {
295  unsigned SpillBase;
296  StackOffset SpillOffset;
297  bool operator==(const SpillLoc &Other) const {
298  return SpillBase == Other.SpillBase && SpillOffset == Other.SpillOffset;
299  }
300  bool operator!=(const SpillLoc &Other) const {
301  return !(*this == Other);
302  }
303  };
304 
305  /// Identity of the variable at this location.
306  const DebugVariable Var;
307 
308  /// The expression applied to this location.
309  const DIExpression *Expr;
310 
311  /// DBG_VALUE to clone var/expr information from if this location
312  /// is moved.
313  const MachineInstr &MI;
314 
315  enum VarLocKind {
316  InvalidKind = 0,
317  RegisterKind,
318  SpillLocKind,
319  ImmediateKind,
320  EntryValueKind,
321  EntryValueBackupKind,
322  EntryValueCopyBackupKind
323  } Kind = InvalidKind;
324 
325  /// The value location. Stored separately to avoid repeatedly
326  /// extracting it from MI.
327  union LocUnion {
328  uint64_t RegNo;
329  SpillLoc SpillLocation;
330  uint64_t Hash;
331  int64_t Immediate;
332  const ConstantFP *FPImm;
333  const ConstantInt *CImm;
334  LocUnion() : Hash(0) {}
335  } Loc;
336 
337  VarLoc(const MachineInstr &MI, LexicalScopes &LS)
338  : Var(MI.getDebugVariable(), MI.getDebugExpression(),
339  MI.getDebugLoc()->getInlinedAt()),
340  Expr(MI.getDebugExpression()), MI(MI) {
341  assert(MI.isDebugValue() && "not a DBG_VALUE");
342  assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
343  if (int RegNo = isDbgValueDescribedByReg(MI)) {
344  Kind = RegisterKind;
345  Loc.RegNo = RegNo;
346  } else if (MI.getDebugOperand(0).isImm()) {
347  Kind = ImmediateKind;
348  Loc.Immediate = MI.getDebugOperand(0).getImm();
349  } else if (MI.getDebugOperand(0).isFPImm()) {
350  Kind = ImmediateKind;
351  Loc.FPImm = MI.getDebugOperand(0).getFPImm();
352  } else if (MI.getDebugOperand(0).isCImm()) {
353  Kind = ImmediateKind;
354  Loc.CImm = MI.getDebugOperand(0).getCImm();
355  }
356 
357  // We create the debug entry values from the factory functions rather than
358  // from this ctor.
359  assert(Kind != EntryValueKind && !isEntryBackupLoc());
360  }
361 
362  /// Take the variable and machine-location in DBG_VALUE MI, and build an
363  /// entry location using the given expression.
364  static VarLoc CreateEntryLoc(const MachineInstr &MI, LexicalScopes &LS,
365  const DIExpression *EntryExpr, Register Reg) {
366  VarLoc VL(MI, LS);
367  assert(VL.Kind == RegisterKind);
368  VL.Kind = EntryValueKind;
369  VL.Expr = EntryExpr;
370  VL.Loc.RegNo = Reg;
371  return VL;
372  }
373 
374  /// Take the variable and machine-location from the DBG_VALUE (from the
375  /// function entry), and build an entry value backup location. The backup
376  /// location will turn into the normal location if the backup is valid at
377  /// the time of the primary location clobbering.
378  static VarLoc CreateEntryBackupLoc(const MachineInstr &MI,
379  LexicalScopes &LS,
380  const DIExpression *EntryExpr) {
381  VarLoc VL(MI, LS);
382  assert(VL.Kind == RegisterKind);
383  VL.Kind = EntryValueBackupKind;
384  VL.Expr = EntryExpr;
385  return VL;
386  }
387 
388  /// Take the variable and machine-location from the DBG_VALUE (from the
389  /// function entry), and build a copy of an entry value backup location by
390  /// setting the register location to NewReg.
391  static VarLoc CreateEntryCopyBackupLoc(const MachineInstr &MI,
392  LexicalScopes &LS,
393  const DIExpression *EntryExpr,
394  Register NewReg) {
395  VarLoc VL(MI, LS);
396  assert(VL.Kind == RegisterKind);
397  VL.Kind = EntryValueCopyBackupKind;
398  VL.Expr = EntryExpr;
399  VL.Loc.RegNo = NewReg;
400  return VL;
401  }
402 
403  /// Copy the register location in DBG_VALUE MI, updating the register to
404  /// be NewReg.
405  static VarLoc CreateCopyLoc(const MachineInstr &MI, LexicalScopes &LS,
406  Register NewReg) {
407  VarLoc VL(MI, LS);
408  assert(VL.Kind == RegisterKind);
409  VL.Loc.RegNo = NewReg;
410  return VL;
411  }
412 
413  /// Take the variable described by DBG_VALUE MI, and create a VarLoc
414  /// locating it in the specified spill location.
415  static VarLoc CreateSpillLoc(const MachineInstr &MI, unsigned SpillBase,
416  StackOffset SpillOffset, LexicalScopes &LS) {
417  VarLoc VL(MI, LS);
418  assert(VL.Kind == RegisterKind);
419  VL.Kind = SpillLocKind;
420  VL.Loc.SpillLocation = {SpillBase, SpillOffset};
421  return VL;
422  }
423 
424  /// Create a DBG_VALUE representing this VarLoc in the given function.
425  /// Copies variable-specific information such as DILocalVariable and
426  /// inlining information from the original DBG_VALUE instruction, which may
427  /// have been several transfers ago.
428  MachineInstr *BuildDbgValue(MachineFunction &MF) const {
429  const DebugLoc &DbgLoc = MI.getDebugLoc();
430  bool Indirect = MI.isIndirectDebugValue();
431  const auto &IID = MI.getDesc();
432  const DILocalVariable *Var = MI.getDebugVariable();
433  const DIExpression *DIExpr = MI.getDebugExpression();
434  NumInserted++;
435 
436  switch (Kind) {
437  case EntryValueKind:
438  // An entry value is a register location -- but with an updated
439  // expression. The register location of such DBG_VALUE is always the one
440  // from the entry DBG_VALUE, it does not matter if the entry value was
441  // copied in to another register due to some optimizations.
442  return BuildMI(MF, DbgLoc, IID, Indirect,
443  MI.getDebugOperand(0).getReg(), Var, Expr);
444  case RegisterKind:
445  // Register locations are like the source DBG_VALUE, but with the
446  // register number from this VarLoc.
447  return BuildMI(MF, DbgLoc, IID, Indirect, Loc.RegNo, Var, DIExpr);
448  case SpillLocKind: {
449  // Spills are indirect DBG_VALUEs, with a base register and offset.
450  // Use the original DBG_VALUEs expression to build the spilt location
451  // on top of. FIXME: spill locations created before this pass runs
452  // are not recognized, and not handled here.
453  auto *TRI = MF.getSubtarget().getRegisterInfo();
454  auto *SpillExpr = TRI->prependOffsetExpression(
455  DIExpr, DIExpression::ApplyOffset, Loc.SpillLocation.SpillOffset);
456  unsigned Base = Loc.SpillLocation.SpillBase;
457  return BuildMI(MF, DbgLoc, IID, true, Base, Var, SpillExpr);
458  }
459  case ImmediateKind: {
460  MachineOperand MO = MI.getDebugOperand(0);
461  return BuildMI(MF, DbgLoc, IID, Indirect, MO, Var, DIExpr);
462  }
463  case EntryValueBackupKind:
464  case EntryValueCopyBackupKind:
465  case InvalidKind:
467  "Tried to produce DBG_VALUE for invalid or backup VarLoc");
468  }
469  llvm_unreachable("Unrecognized VarLocBasedLDV.VarLoc.Kind enum");
470  }
471 
472  /// Is the Loc field a constant or constant object?
473  bool isConstant() const { return Kind == ImmediateKind; }
474 
475  /// Check if the Loc field is an entry backup location.
476  bool isEntryBackupLoc() const {
477  return Kind == EntryValueBackupKind || Kind == EntryValueCopyBackupKind;
478  }
479 
480  /// If this variable is described by a register holding the entry value,
481  /// return it, otherwise return 0.
482  unsigned getEntryValueBackupReg() const {
483  if (Kind == EntryValueBackupKind)
484  return Loc.RegNo;
485  return 0;
486  }
487 
488  /// If this variable is described by a register holding the copy of the
489  /// entry value, return it, otherwise return 0.
490  unsigned getEntryValueCopyBackupReg() const {
491  if (Kind == EntryValueCopyBackupKind)
492  return Loc.RegNo;
493  return 0;
494  }
495 
496  /// If this variable is described by a register, return it,
497  /// otherwise return 0.
498  unsigned isDescribedByReg() const {
499  if (Kind == RegisterKind)
500  return Loc.RegNo;
501  return 0;
502  }
503 
504  /// Determine whether the lexical scope of this value's debug location
505  /// dominates MBB.
507  return LS.dominates(MI.getDebugLoc().get(), &MBB);
508  }
509 
510 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
511  // TRI can be null.
512  void dump(const TargetRegisterInfo *TRI, raw_ostream &Out = dbgs()) const {
513  Out << "VarLoc(";
514  switch (Kind) {
515  case RegisterKind:
516  case EntryValueKind:
517  case EntryValueBackupKind:
518  case EntryValueCopyBackupKind:
519  Out << printReg(Loc.RegNo, TRI);
520  break;
521  case SpillLocKind:
522  Out << printReg(Loc.SpillLocation.SpillBase, TRI);
523  Out << "[" << Loc.SpillLocation.SpillOffset.getFixed() << " + "
524  << Loc.SpillLocation.SpillOffset.getScalable() << "x vscale"
525  << "]";
526  break;
527  case ImmediateKind:
528  Out << Loc.Immediate;
529  break;
530  case InvalidKind:
531  llvm_unreachable("Invalid VarLoc in dump method");
532  }
533 
534  Out << ", \"" << Var.getVariable()->getName() << "\", " << *Expr << ", ";
535  if (Var.getInlinedAt())
536  Out << "!" << Var.getInlinedAt()->getMetadataID() << ")\n";
537  else
538  Out << "(null))";
539 
540  if (isEntryBackupLoc())
541  Out << " (backup loc)\n";
542  else
543  Out << "\n";
544  }
545 #endif
546 
547  bool operator==(const VarLoc &Other) const {
548  if (Kind != Other.Kind || !(Var == Other.Var) || Expr != Other.Expr)
549  return false;
550 
551  switch (Kind) {
552  case SpillLocKind:
553  return Loc.SpillLocation == Other.Loc.SpillLocation;
554  case RegisterKind:
555  case ImmediateKind:
556  case EntryValueKind:
557  case EntryValueBackupKind:
558  case EntryValueCopyBackupKind:
559  return Loc.Hash == Other.Loc.Hash;
560  default:
561  llvm_unreachable("Invalid kind");
562  }
563  }
564 
565  /// This operator guarantees that VarLocs are sorted by Variable first.
566  bool operator<(const VarLoc &Other) const {
567  switch (Kind) {
568  case SpillLocKind:
569  return std::make_tuple(Var, Kind, Loc.SpillLocation.SpillBase,
570  Loc.SpillLocation.SpillOffset.getFixed(),
571  Loc.SpillLocation.SpillOffset.getScalable(),
572  Expr) <
573  std::make_tuple(
574  Other.Var, Other.Kind, Other.Loc.SpillLocation.SpillBase,
575  Other.Loc.SpillLocation.SpillOffset.getFixed(),
576  Other.Loc.SpillLocation.SpillOffset.getScalable(),
577  Other.Expr);
578  case RegisterKind:
579  case ImmediateKind:
580  case EntryValueKind:
581  case EntryValueBackupKind:
582  case EntryValueCopyBackupKind:
583  return std::tie(Var, Kind, Loc.Hash, Expr) <
584  std::tie(Other.Var, Other.Kind, Other.Loc.Hash, Other.Expr);
585  default:
586  llvm_unreachable("Invalid kind");
587  }
588  }
589  };
590 
591  /// VarLocMap is used for two things:
592  /// 1) Assigning a unique LocIndex to a VarLoc. This LocIndex can be used to
593  /// virtually insert a VarLoc into a VarLocSet.
594  /// 2) Given a LocIndex, look up the unique associated VarLoc.
595  class VarLocMap {
596  /// Map a VarLoc to an index within the vector reserved for its location
597  /// within Loc2Vars.
598  std::map<VarLoc, LocIndex::u32_index_t> Var2Index;
599 
600  /// Map a location to a vector which holds VarLocs which live in that
601  /// location.
603 
604  /// Determine the 32-bit location reserved for \p VL, based on its kind.
605  static LocIndex::u32_location_t getLocationForVar(const VarLoc &VL) {
606  switch (VL.Kind) {
608  assert((VL.Loc.RegNo < LocIndex::kFirstInvalidRegLocation) &&
609  "Physreg out of range?");
610  return VL.Loc.RegNo;
611  case VarLoc::SpillLocKind:
612  return LocIndex::kSpillLocation;
613  case VarLoc::EntryValueBackupKind:
614  case VarLoc::EntryValueCopyBackupKind:
615  return LocIndex::kEntryValueBackupLocation;
616  default:
617  return 0;
618  }
619  }
620 
621  public:
622  /// Retrieve a unique LocIndex for \p VL.
623  LocIndex insert(const VarLoc &VL) {
624  LocIndex::u32_location_t Location = getLocationForVar(VL);
625  LocIndex::u32_index_t &Index = Var2Index[VL];
626  if (!Index) {
627  auto &Vars = Loc2Vars[Location];
628  Vars.push_back(VL);
629  Index = Vars.size();
630  }
631  return {Location, Index - 1};
632  }
633 
634  /// Retrieve the unique VarLoc associated with \p ID.
635  const VarLoc &operator[](LocIndex ID) const {
636  auto LocIt = Loc2Vars.find(ID.Location);
637  assert(LocIt != Loc2Vars.end() && "Location not tracked");
638  return LocIt->second[ID.Index];
639  }
640  };
641 
642  using VarLocInMBB =
644  struct TransferDebugPair {
645  MachineInstr *TransferInst; ///< Instruction where this transfer occurs.
646  LocIndex LocationID; ///< Location number for the transfer dest.
647  };
648  using TransferMap = SmallVector<TransferDebugPair, 4>;
649 
650  // Types for recording sets of variable fragments that overlap. For a given
651  // local variable, we record all other fragments of that variable that could
652  // overlap it, to reduce search time.
653  using FragmentOfVar =
654  std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
655  using OverlapMap =
657 
658  // Helper while building OverlapMap, a map of all fragments seen for a given
659  // DILocalVariable.
660  using VarToFragments =
662 
663  /// This holds the working set of currently open ranges. For fast
664  /// access, this is done both as a set of VarLocIDs, and a map of
665  /// DebugVariable to recent VarLocID. Note that a DBG_VALUE ends all
666  /// previous open ranges for the same variable. In addition, we keep
667  /// two different maps (Vars/EntryValuesBackupVars), so erase/insert
668  /// methods act differently depending on whether a VarLoc is primary
669  /// location or backup one. In the case the VarLoc is backup location
670  /// we will erase/insert from the EntryValuesBackupVars map, otherwise
671  /// we perform the operation on the Vars.
672  class OpenRangesSet {
673  VarLocSet VarLocs;
674  // Map the DebugVariable to recent primary location ID.
676  // Map the DebugVariable to recent backup location ID.
677  SmallDenseMap<DebugVariable, LocIndex, 8> EntryValuesBackupVars;
678  OverlapMap &OverlappingFragments;
679 
680  public:
681  OpenRangesSet(VarLocSet::Allocator &Alloc, OverlapMap &_OLapMap)
682  : VarLocs(Alloc), OverlappingFragments(_OLapMap) {}
683 
684  const VarLocSet &getVarLocs() const { return VarLocs; }
685 
686  /// Terminate all open ranges for VL.Var by removing it from the set.
687  void erase(const VarLoc &VL);
688 
689  /// Terminate all open ranges listed in \c KillSet by removing
690  /// them from the set.
691  void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs);
692 
693  /// Insert a new range into the set.
694  void insert(LocIndex VarLocID, const VarLoc &VL);
695 
696  /// Insert a set of ranges.
697  void insertFromLocSet(const VarLocSet &ToLoad, const VarLocMap &Map) {
698  for (uint64_t ID : ToLoad) {
699  LocIndex Idx = LocIndex::fromRawInteger(ID);
700  const VarLoc &VarL = Map[Idx];
701  insert(Idx, VarL);
702  }
703  }
704 
705  llvm::Optional<LocIndex> getEntryValueBackup(DebugVariable Var);
706 
707  /// Empty the set.
708  void clear() {
709  VarLocs.clear();
710  Vars.clear();
711  EntryValuesBackupVars.clear();
712  }
713 
714  /// Return whether the set is empty or not.
715  bool empty() const {
716  assert(Vars.empty() == EntryValuesBackupVars.empty() &&
717  Vars.empty() == VarLocs.empty() &&
718  "open ranges are inconsistent");
719  return VarLocs.empty();
720  }
721 
722  /// Get an empty range of VarLoc IDs.
723  auto getEmptyVarLocRange() const {
724  return iterator_range<VarLocSet::const_iterator>(getVarLocs().end(),
725  getVarLocs().end());
726  }
727 
728  /// Get all set IDs for VarLocs of kind RegisterKind in \p Reg.
729  auto getRegisterVarLocs(Register Reg) const {
730  return LocIndex::indexRangeForLocation(getVarLocs(), Reg);
731  }
732 
733  /// Get all set IDs for VarLocs of kind SpillLocKind.
734  auto getSpillVarLocs() const {
735  return LocIndex::indexRangeForLocation(getVarLocs(),
736  LocIndex::kSpillLocation);
737  }
738 
739  /// Get all set IDs for VarLocs of kind EntryValueBackupKind or
740  /// EntryValueCopyBackupKind.
741  auto getEntryValueBackupVarLocs() const {
742  return LocIndex::indexRangeForLocation(
743  getVarLocs(), LocIndex::kEntryValueBackupLocation);
744  }
745  };
746 
747  /// Collect all VarLoc IDs from \p CollectFrom for VarLocs of kind
748  /// RegisterKind which are located in any reg in \p Regs. Insert collected IDs
749  /// into \p Collected.
750  void collectIDsForRegs(VarLocSet &Collected, const DefinedRegsSet &Regs,
751  const VarLocSet &CollectFrom) const;
752 
753  /// Get the registers which are used by VarLocs of kind RegisterKind tracked
754  /// by \p CollectFrom.
755  void getUsedRegs(const VarLocSet &CollectFrom,
756  SmallVectorImpl<uint32_t> &UsedRegs) const;
757 
758  VarLocSet &getVarLocsInMBB(const MachineBasicBlock *MBB, VarLocInMBB &Locs) {
759  std::unique_ptr<VarLocSet> &VLS = Locs[MBB];
760  if (!VLS)
761  VLS = std::make_unique<VarLocSet>(Alloc);
762  return *VLS.get();
763  }
764 
765  const VarLocSet &getVarLocsInMBB(const MachineBasicBlock *MBB,
766  const VarLocInMBB &Locs) const {
767  auto It = Locs.find(MBB);
768  assert(It != Locs.end() && "MBB not in map");
769  return *It->second.get();
770  }
771 
772  /// Tests whether this instruction is a spill to a stack location.
773  bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF);
774 
775  /// Decide if @MI is a spill instruction and return true if it is. We use 2
776  /// criteria to make this decision:
777  /// - Is this instruction a store to a spill slot?
778  /// - Is there a register operand that is both used and killed?
779  /// TODO: Store optimization can fold spills into other stores (including
780  /// other spills). We do not handle this yet (more than one memory operand).
781  bool isLocationSpill(const MachineInstr &MI, MachineFunction *MF,
782  Register &Reg);
783 
784  /// Returns true if the given machine instruction is a debug value which we
785  /// can emit entry values for.
786  ///
787  /// Currently, we generate debug entry values only for parameters that are
788  /// unmodified throughout the function and located in a register.
789  bool isEntryValueCandidate(const MachineInstr &MI,
790  const DefinedRegsSet &Regs) const;
791 
792  /// If a given instruction is identified as a spill, return the spill location
793  /// and set \p Reg to the spilled register.
794  Optional<VarLoc::SpillLoc> isRestoreInstruction(const MachineInstr &MI,
795  MachineFunction *MF,
796  Register &Reg);
797  /// Given a spill instruction, extract the register and offset used to
798  /// address the spill location in a target independent way.
799  VarLoc::SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI);
800  void insertTransferDebugPair(MachineInstr &MI, OpenRangesSet &OpenRanges,
801  TransferMap &Transfers, VarLocMap &VarLocIDs,
802  LocIndex OldVarID, TransferKind Kind,
803  Register NewReg = Register());
804 
805  void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
806  VarLocMap &VarLocIDs);
807  void transferSpillOrRestoreInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
808  VarLocMap &VarLocIDs, TransferMap &Transfers);
809  bool removeEntryValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
810  VarLocMap &VarLocIDs, const VarLoc &EntryVL);
811  void emitEntryValues(MachineInstr &MI, OpenRangesSet &OpenRanges,
812  VarLocMap &VarLocIDs, TransferMap &Transfers,
813  VarLocSet &KillSet);
814  void recordEntryValue(const MachineInstr &MI,
815  const DefinedRegsSet &DefinedRegs,
816  OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs);
817  void transferRegisterCopy(MachineInstr &MI, OpenRangesSet &OpenRanges,
818  VarLocMap &VarLocIDs, TransferMap &Transfers);
819  void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
820  VarLocMap &VarLocIDs, TransferMap &Transfers);
821  bool transferTerminator(MachineBasicBlock *MBB, OpenRangesSet &OpenRanges,
822  VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs);
823 
824  void process(MachineInstr &MI, OpenRangesSet &OpenRanges,
825  VarLocMap &VarLocIDs, TransferMap &Transfers);
826 
827  void accumulateFragmentMap(MachineInstr &MI, VarToFragments &SeenFragments,
828  OverlapMap &OLapMap);
829 
830  bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
831  const VarLocMap &VarLocIDs,
834 
835  /// Create DBG_VALUE insts for inlocs that have been propagated but
836  /// had their instruction creation deferred.
837  void flushPendingLocs(VarLocInMBB &PendingInLocs, VarLocMap &VarLocIDs);
838 
839  bool ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) override;
840 
841 public:
842  /// Default construct and initialize the pass.
843  VarLocBasedLDV();
844 
845  ~VarLocBasedLDV();
846 
847  /// Print to ostream with a message.
848  void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V,
849  const VarLocMap &VarLocIDs, const char *msg,
850  raw_ostream &Out) const;
851 };
852 
853 } // end anonymous namespace
854 
855 //===----------------------------------------------------------------------===//
856 // Implementation
857 //===----------------------------------------------------------------------===//
858 
859 VarLocBasedLDV::VarLocBasedLDV() { }
860 
861 VarLocBasedLDV::~VarLocBasedLDV() { }
862 
863 /// Erase a variable from the set of open ranges, and additionally erase any
864 /// fragments that may overlap it. If the VarLoc is a backup location, erase
865 /// the variable from the EntryValuesBackupVars set, indicating we should stop
866 /// tracking its backup entry location. Otherwise, if the VarLoc is primary
867 /// location, erase the variable from the Vars set.
868 void VarLocBasedLDV::OpenRangesSet::erase(const VarLoc &VL) {
869  // Erasure helper.
870  auto DoErase = [VL, this](DebugVariable VarToErase) {
871  auto *EraseFrom = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
872  auto It = EraseFrom->find(VarToErase);
873  if (It != EraseFrom->end()) {
874  LocIndex ID = It->second;
875  VarLocs.reset(ID.getAsRawInteger());
876  EraseFrom->erase(It);
877  }
878  };
879 
880  DebugVariable Var = VL.Var;
881 
882  // Erase the variable/fragment that ends here.
883  DoErase(Var);
884 
885  // Extract the fragment. Interpret an empty fragment as one that covers all
886  // possible bits.
887  FragmentInfo ThisFragment = Var.getFragmentOrDefault();
888 
889  // There may be fragments that overlap the designated fragment. Look them up
890  // in the pre-computed overlap map, and erase them too.
891  auto MapIt = OverlappingFragments.find({Var.getVariable(), ThisFragment});
892  if (MapIt != OverlappingFragments.end()) {
893  for (auto Fragment : MapIt->second) {
894  VarLocBasedLDV::OptFragmentInfo FragmentHolder;
895  if (!DebugVariable::isDefaultFragment(Fragment))
896  FragmentHolder = VarLocBasedLDV::OptFragmentInfo(Fragment);
897  DoErase({Var.getVariable(), FragmentHolder, Var.getInlinedAt()});
898  }
899  }
900 }
901 
902 void VarLocBasedLDV::OpenRangesSet::erase(const VarLocSet &KillSet,
903  const VarLocMap &VarLocIDs) {
904  VarLocs.intersectWithComplement(KillSet);
905  for (uint64_t ID : KillSet) {
906  const VarLoc *VL = &VarLocIDs[LocIndex::fromRawInteger(ID)];
907  auto *EraseFrom = VL->isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
908  EraseFrom->erase(VL->Var);
909  }
910 }
911 
912 void VarLocBasedLDV::OpenRangesSet::insert(LocIndex VarLocID,
913  const VarLoc &VL) {
914  auto *InsertInto = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
915  VarLocs.set(VarLocID.getAsRawInteger());
916  InsertInto->insert({VL.Var, VarLocID});
917 }
918 
919 /// Return the Loc ID of an entry value backup location, if it exists for the
920 /// variable.
922 VarLocBasedLDV::OpenRangesSet::getEntryValueBackup(DebugVariable Var) {
923  auto It = EntryValuesBackupVars.find(Var);
924  if (It != EntryValuesBackupVars.end())
925  return It->second;
926 
927  return llvm::None;
928 }
929 
930 void VarLocBasedLDV::collectIDsForRegs(VarLocSet &Collected,
931  const DefinedRegsSet &Regs,
932  const VarLocSet &CollectFrom) const {
933  assert(!Regs.empty() && "Nothing to collect");
934  SmallVector<uint32_t, 32> SortedRegs;
935  for (Register Reg : Regs)
936  SortedRegs.push_back(Reg);
937  array_pod_sort(SortedRegs.begin(), SortedRegs.end());
938  auto It = CollectFrom.find(LocIndex::rawIndexForReg(SortedRegs.front()));
939  auto End = CollectFrom.end();
940  for (uint32_t Reg : SortedRegs) {
941  // The half-open interval [FirstIndexForReg, FirstInvalidIndex) contains all
942  // possible VarLoc IDs for VarLocs of kind RegisterKind which live in Reg.
943  uint64_t FirstIndexForReg = LocIndex::rawIndexForReg(Reg);
944  uint64_t FirstInvalidIndex = LocIndex::rawIndexForReg(Reg + 1);
945  It.advanceToLowerBound(FirstIndexForReg);
946 
947  // Iterate through that half-open interval and collect all the set IDs.
948  for (; It != End && *It < FirstInvalidIndex; ++It)
949  Collected.set(*It);
950 
951  if (It == End)
952  return;
953  }
954 }
955 
956 void VarLocBasedLDV::getUsedRegs(const VarLocSet &CollectFrom,
957  SmallVectorImpl<uint32_t> &UsedRegs) const {
958  // All register-based VarLocs are assigned indices greater than or equal to
959  // FirstRegIndex.
960  uint64_t FirstRegIndex = LocIndex::rawIndexForReg(1);
961  uint64_t FirstInvalidIndex =
962  LocIndex::rawIndexForReg(LocIndex::kFirstInvalidRegLocation);
963  for (auto It = CollectFrom.find(FirstRegIndex),
964  End = CollectFrom.find(FirstInvalidIndex);
965  It != End;) {
966  // We found a VarLoc ID for a VarLoc that lives in a register. Figure out
967  // which register and add it to UsedRegs.
968  uint32_t FoundReg = LocIndex::fromRawInteger(*It).Location;
969  assert((UsedRegs.empty() || FoundReg != UsedRegs.back()) &&
970  "Duplicate used reg");
971  UsedRegs.push_back(FoundReg);
972 
973  // Skip to the next /set/ register. Note that this finds a lower bound, so
974  // even if there aren't any VarLocs living in `FoundReg+1`, we're still
975  // guaranteed to move on to the next register (or to end()).
976  uint64_t NextRegIndex = LocIndex::rawIndexForReg(FoundReg + 1);
977  It.advanceToLowerBound(NextRegIndex);
978  }
979 }
980 
981 //===----------------------------------------------------------------------===//
982 // Debug Range Extension Implementation
983 //===----------------------------------------------------------------------===//
984 
985 #ifndef NDEBUG
986 void VarLocBasedLDV::printVarLocInMBB(const MachineFunction &MF,
987  const VarLocInMBB &V,
988  const VarLocMap &VarLocIDs,
989  const char *msg,
990  raw_ostream &Out) const {
991  Out << '\n' << msg << '\n';
992  for (const MachineBasicBlock &BB : MF) {
993  if (!V.count(&BB))
994  continue;
995  const VarLocSet &L = getVarLocsInMBB(&BB, V);
996  if (L.empty())
997  continue;
998  Out << "MBB: " << BB.getNumber() << ":\n";
999  for (uint64_t VLL : L) {
1000  const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(VLL)];
1001  Out << " Var: " << VL.Var.getVariable()->getName();
1002  Out << " MI: ";
1003  VL.dump(TRI, Out);
1004  }
1005  }
1006  Out << "\n";
1007 }
1008 #endif
1009 
1010 VarLocBasedLDV::VarLoc::SpillLoc
1011 VarLocBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
1012  assert(MI.hasOneMemOperand() &&
1013  "Spill instruction does not have exactly one memory operand?");
1014  auto MMOI = MI.memoperands_begin();
1015  const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
1017  "Inconsistent memory operand in spill instruction");
1018  int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
1019  const MachineBasicBlock *MBB = MI.getParent();
1020  Register Reg;
1022  return {Reg, Offset};
1023 }
1024 
1025 /// Try to salvage the debug entry value if we encounter a new debug value
1026 /// describing the same parameter, otherwise stop tracking the value. Return
1027 /// true if we should stop tracking the entry value, otherwise return false.
1028 bool VarLocBasedLDV::removeEntryValue(const MachineInstr &MI,
1029  OpenRangesSet &OpenRanges,
1030  VarLocMap &VarLocIDs,
1031  const VarLoc &EntryVL) {
1032  // Skip the DBG_VALUE which is the debug entry value itself.
1033  if (MI.isIdenticalTo(EntryVL.MI))
1034  return false;
1035 
1036  // If the parameter's location is not register location, we can not track
1037  // the entry value any more. In addition, if the debug expression from the
1038  // DBG_VALUE is not empty, we can assume the parameter's value has changed
1039  // indicating that we should stop tracking its entry value as well.
1040  if (!MI.getDebugOperand(0).isReg() ||
1041  MI.getDebugExpression()->getNumElements() != 0)
1042  return true;
1043 
1044  // If the DBG_VALUE comes from a copy instruction that copies the entry value,
1045  // it means the parameter's value has not changed and we should be able to use
1046  // its entry value.
1047  bool TrySalvageEntryValue = false;
1048  Register Reg = MI.getDebugOperand(0).getReg();
1049  auto I = std::next(MI.getReverseIterator());
1050  const MachineOperand *SrcRegOp, *DestRegOp;
1051  if (I != MI.getParent()->rend()) {
1052  // TODO: Try to keep tracking of an entry value if we encounter a propagated
1053  // DBG_VALUE describing the copy of the entry value. (Propagated entry value
1054  // does not indicate the parameter modification.)
1055  auto DestSrc = TII->isCopyInstr(*I);
1056  if (!DestSrc)
1057  return true;
1058 
1059  SrcRegOp = DestSrc->Source;
1060  DestRegOp = DestSrc->Destination;
1061  if (Reg != DestRegOp->getReg())
1062  return true;
1063  TrySalvageEntryValue = true;
1064  }
1065 
1066  if (TrySalvageEntryValue) {
1067  for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) {
1068  const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(ID)];
1069  if (VL.getEntryValueCopyBackupReg() == Reg &&
1070  VL.MI.getDebugOperand(0).getReg() == SrcRegOp->getReg())
1071  return false;
1072  }
1073  }
1074 
1075  return true;
1076 }
1077 
1078 /// End all previous ranges related to @MI and start a new range from @MI
1079 /// if it is a DBG_VALUE instr.
1080 void VarLocBasedLDV::transferDebugValue(const MachineInstr &MI,
1081  OpenRangesSet &OpenRanges,
1082  VarLocMap &VarLocIDs) {
1083  if (!MI.isDebugValue())
1084  return;
1085  const DILocalVariable *Var = MI.getDebugVariable();
1086  const DIExpression *Expr = MI.getDebugExpression();
1087  const DILocation *DebugLoc = MI.getDebugLoc();
1088  const DILocation *InlinedAt = DebugLoc->getInlinedAt();
1090  "Expected inlined-at fields to agree");
1091 
1092  DebugVariable V(Var, Expr, InlinedAt);
1093 
1094  // Check if this DBG_VALUE indicates a parameter's value changing.
1095  // If that is the case, we should stop tracking its entry value.
1096  auto EntryValBackupID = OpenRanges.getEntryValueBackup(V);
1097  if (Var->isParameter() && EntryValBackupID) {
1098  const VarLoc &EntryVL = VarLocIDs[*EntryValBackupID];
1099  if (removeEntryValue(MI, OpenRanges, VarLocIDs, EntryVL)) {
1100  LLVM_DEBUG(dbgs() << "Deleting a DBG entry value because of: ";
1101  MI.print(dbgs(), /*IsStandalone*/ false,
1102  /*SkipOpers*/ false, /*SkipDebugLoc*/ false,
1103  /*AddNewLine*/ true, TII));
1104  OpenRanges.erase(EntryVL);
1105  }
1106  }
1107 
1108  if (isDbgValueDescribedByReg(MI) || MI.getDebugOperand(0).isImm() ||
1109  MI.getDebugOperand(0).isFPImm() || MI.getDebugOperand(0).isCImm()) {
1110  // Use normal VarLoc constructor for registers and immediates.
1111  VarLoc VL(MI, LS);
1112  // End all previous ranges of VL.Var.
1113  OpenRanges.erase(VL);
1114 
1115  LocIndex ID = VarLocIDs.insert(VL);
1116  // Add the VarLoc to OpenRanges from this DBG_VALUE.
1117  OpenRanges.insert(ID, VL);
1118  } else if (MI.hasOneMemOperand()) {
1119  llvm_unreachable("DBG_VALUE with mem operand encountered after regalloc?");
1120  } else {
1121  // This must be an undefined location. If it has an open range, erase it.
1122  assert(MI.getDebugOperand(0).isReg() &&
1123  MI.getDebugOperand(0).getReg() == 0 &&
1124  "Unexpected non-undef DBG_VALUE encountered");
1125  VarLoc VL(MI, LS);
1126  OpenRanges.erase(VL);
1127  }
1128 }
1129 
1130 /// Turn the entry value backup locations into primary locations.
1131 void VarLocBasedLDV::emitEntryValues(MachineInstr &MI,
1132  OpenRangesSet &OpenRanges,
1133  VarLocMap &VarLocIDs,
1134  TransferMap &Transfers,
1135  VarLocSet &KillSet) {
1136  // Do not insert entry value locations after a terminator.
1137  if (MI.isTerminator())
1138  return;
1139 
1140  for (uint64_t ID : KillSet) {
1141  LocIndex Idx = LocIndex::fromRawInteger(ID);
1142  const VarLoc &VL = VarLocIDs[Idx];
1143  if (!VL.Var.getVariable()->isParameter())
1144  continue;
1145 
1146  auto DebugVar = VL.Var;
1147  Optional<LocIndex> EntryValBackupID =
1148  OpenRanges.getEntryValueBackup(DebugVar);
1149 
1150  // If the parameter has the entry value backup, it means we should
1151  // be able to use its entry value.
1152  if (!EntryValBackupID)
1153  continue;
1154 
1155  const VarLoc &EntryVL = VarLocIDs[*EntryValBackupID];
1156  VarLoc EntryLoc =
1157  VarLoc::CreateEntryLoc(EntryVL.MI, LS, EntryVL.Expr, EntryVL.Loc.RegNo);
1158  LocIndex EntryValueID = VarLocIDs.insert(EntryLoc);
1159  Transfers.push_back({&MI, EntryValueID});
1160  OpenRanges.insert(EntryValueID, EntryLoc);
1161  }
1162 }
1163 
1164 /// Create new TransferDebugPair and insert it in \p Transfers. The VarLoc
1165 /// with \p OldVarID should be deleted form \p OpenRanges and replaced with
1166 /// new VarLoc. If \p NewReg is different than default zero value then the
1167 /// new location will be register location created by the copy like instruction,
1168 /// otherwise it is variable's location on the stack.
1169 void VarLocBasedLDV::insertTransferDebugPair(
1170  MachineInstr &MI, OpenRangesSet &OpenRanges, TransferMap &Transfers,
1171  VarLocMap &VarLocIDs, LocIndex OldVarID, TransferKind Kind,
1172  Register NewReg) {
1173  const MachineInstr *DebugInstr = &VarLocIDs[OldVarID].MI;
1174 
1175  auto ProcessVarLoc = [&MI, &OpenRanges, &Transfers, &VarLocIDs](VarLoc &VL) {
1176  LocIndex LocId = VarLocIDs.insert(VL);
1177 
1178  // Close this variable's previous location range.
1179  OpenRanges.erase(VL);
1180 
1181  // Record the new location as an open range, and a postponed transfer
1182  // inserting a DBG_VALUE for this location.
1183  OpenRanges.insert(LocId, VL);
1184  assert(!MI.isTerminator() && "Cannot insert DBG_VALUE after terminator");
1185  TransferDebugPair MIP = {&MI, LocId};
1186  Transfers.push_back(MIP);
1187  };
1188 
1189  // End all previous ranges of VL.Var.
1190  OpenRanges.erase(VarLocIDs[OldVarID]);
1191  switch (Kind) {
1192  case TransferKind::TransferCopy: {
1193  assert(NewReg &&
1194  "No register supplied when handling a copy of a debug value");
1195  // Create a DBG_VALUE instruction to describe the Var in its new
1196  // register location.
1197  VarLoc VL = VarLoc::CreateCopyLoc(*DebugInstr, LS, NewReg);
1198  ProcessVarLoc(VL);
1199  LLVM_DEBUG({
1200  dbgs() << "Creating VarLoc for register copy:";
1201  VL.dump(TRI);
1202  });
1203  return;
1204  }
1205  case TransferKind::TransferSpill: {
1206  // Create a DBG_VALUE instruction to describe the Var in its spilled
1207  // location.
1208  VarLoc::SpillLoc SpillLocation = extractSpillBaseRegAndOffset(MI);
1209  VarLoc VL = VarLoc::CreateSpillLoc(*DebugInstr, SpillLocation.SpillBase,
1210  SpillLocation.SpillOffset, LS);
1211  ProcessVarLoc(VL);
1212  LLVM_DEBUG({
1213  dbgs() << "Creating VarLoc for spill:";
1214  VL.dump(TRI);
1215  });
1216  return;
1217  }
1218  case TransferKind::TransferRestore: {
1219  assert(NewReg &&
1220  "No register supplied when handling a restore of a debug value");
1221  // DebugInstr refers to the pre-spill location, therefore we can reuse
1222  // its expression.
1223  VarLoc VL = VarLoc::CreateCopyLoc(*DebugInstr, LS, NewReg);
1224  ProcessVarLoc(VL);
1225  LLVM_DEBUG({
1226  dbgs() << "Creating VarLoc for restore:";
1227  VL.dump(TRI);
1228  });
1229  return;
1230  }
1231  }
1232  llvm_unreachable("Invalid transfer kind");
1233 }
1234 
1235 /// A definition of a register may mark the end of a range.
1236 void VarLocBasedLDV::transferRegisterDef(
1237  MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs,
1238  TransferMap &Transfers) {
1239 
1240  // Meta Instructions do not affect the debug liveness of any register they
1241  // define.
1242  if (MI.isMetaInstruction())
1243  return;
1244 
1245  MachineFunction *MF = MI.getMF();
1246  const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
1248 
1249  // Find the regs killed by MI, and find regmasks of preserved regs.
1250  DefinedRegsSet DeadRegs;
1252  for (const MachineOperand &MO : MI.operands()) {
1253  // Determine whether the operand is a register def.
1254  if (MO.isReg() && MO.isDef() && MO.getReg() &&
1255  Register::isPhysicalRegister(MO.getReg()) &&
1256  !(MI.isCall() && MO.getReg() == SP)) {
1257  // Remove ranges of all aliased registers.
1258  for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
1259  // FIXME: Can we break out of this loop early if no insertion occurs?
1260  DeadRegs.insert(*RAI);
1261  } else if (MO.isRegMask()) {
1262  RegMasks.push_back(MO.getRegMask());
1263  }
1264  }
1265 
1266  // Erase VarLocs which reside in one of the dead registers. For performance
1267  // reasons, it's critical to not iterate over the full set of open VarLocs.
1268  // Iterate over the set of dying/used regs instead.
1269  if (!RegMasks.empty()) {
1270  SmallVector<uint32_t, 32> UsedRegs;
1271  getUsedRegs(OpenRanges.getVarLocs(), UsedRegs);
1272  for (uint32_t Reg : UsedRegs) {
1273  // Remove ranges of all clobbered registers. Register masks don't usually
1274  // list SP as preserved. Assume that call instructions never clobber SP,
1275  // because some backends (e.g., AArch64) never list SP in the regmask.
1276  // While the debug info may be off for an instruction or two around
1277  // callee-cleanup calls, transferring the DEBUG_VALUE across the call is
1278  // still a better user experience.
1279  if (Reg == SP)
1280  continue;
1281  bool AnyRegMaskKillsReg =
1282  any_of(RegMasks, [Reg](const uint32_t *RegMask) {
1283  return MachineOperand::clobbersPhysReg(RegMask, Reg);
1284  });
1285  if (AnyRegMaskKillsReg)
1286  DeadRegs.insert(Reg);
1287  }
1288  }
1289 
1290  if (DeadRegs.empty())
1291  return;
1292 
1293  VarLocSet KillSet(Alloc);
1294  collectIDsForRegs(KillSet, DeadRegs, OpenRanges.getVarLocs());
1295  OpenRanges.erase(KillSet, VarLocIDs);
1296 
1297  if (TPC) {
1298  auto &TM = TPC->getTM<TargetMachine>();
1299  if (TM.Options.ShouldEmitDebugEntryValues())
1300  emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, KillSet);
1301  }
1302 }
1303 
1304 bool VarLocBasedLDV::isSpillInstruction(const MachineInstr &MI,
1305  MachineFunction *MF) {
1306  // TODO: Handle multiple stores folded into one.
1307  if (!MI.hasOneMemOperand())
1308  return false;
1309 
1310  if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII))
1311  return false; // This is not a spill instruction, since no valid size was
1312  // returned from either function.
1313 
1314  return true;
1315 }
1316 
1317 bool VarLocBasedLDV::isLocationSpill(const MachineInstr &MI,
1318  MachineFunction *MF, Register &Reg) {
1319  if (!isSpillInstruction(MI, MF))
1320  return false;
1321 
1322  auto isKilledReg = [&](const MachineOperand MO, Register &Reg) {
1323  if (!MO.isReg() || !MO.isUse()) {
1324  Reg = 0;
1325  return false;
1326  }
1327  Reg = MO.getReg();
1328  return MO.isKill();
1329  };
1330 
1331  for (const MachineOperand &MO : MI.operands()) {
1332  // In a spill instruction generated by the InlineSpiller the spilled
1333  // register has its kill flag set.
1334  if (isKilledReg(MO, Reg))
1335  return true;
1336  if (Reg != 0) {
1337  // Check whether next instruction kills the spilled register.
1338  // FIXME: Current solution does not cover search for killed register in
1339  // bundles and instructions further down the chain.
1340  auto NextI = std::next(MI.getIterator());
1341  // Skip next instruction that points to basic block end iterator.
1342  if (MI.getParent()->end() == NextI)
1343  continue;
1344  Register RegNext;
1345  for (const MachineOperand &MONext : NextI->operands()) {
1346  // Return true if we came across the register from the
1347  // previous spill instruction that is killed in NextI.
1348  if (isKilledReg(MONext, RegNext) && RegNext == Reg)
1349  return true;
1350  }
1351  }
1352  }
1353  // Return false if we didn't find spilled register.
1354  return false;
1355 }
1356 
1358 VarLocBasedLDV::isRestoreInstruction(const MachineInstr &MI,
1359  MachineFunction *MF, Register &Reg) {
1360  if (!MI.hasOneMemOperand())
1361  return None;
1362 
1363  // FIXME: Handle folded restore instructions with more than one memory
1364  // operand.
1365  if (MI.getRestoreSize(TII)) {
1366  Reg = MI.getOperand(0).getReg();
1367  return extractSpillBaseRegAndOffset(MI);
1368  }
1369  return None;
1370 }
1371 
1372 /// A spilled register may indicate that we have to end the current range of
1373 /// a variable and create a new one for the spill location.
1374 /// A restored register may indicate the reverse situation.
1375 /// We don't want to insert any instructions in process(), so we just create
1376 /// the DBG_VALUE without inserting it and keep track of it in \p Transfers.
1377 /// It will be inserted into the BB when we're done iterating over the
1378 /// instructions.
1379 void VarLocBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI,
1380  OpenRangesSet &OpenRanges,
1381  VarLocMap &VarLocIDs,
1382  TransferMap &Transfers) {
1383  MachineFunction *MF = MI.getMF();
1384  TransferKind TKind;
1385  Register Reg;
1387 
1388  LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump(););
1389 
1390  // First, if there are any DBG_VALUEs pointing at a spill slot that is
1391  // written to, then close the variable location. The value in memory
1392  // will have changed.
1393  VarLocSet KillSet(Alloc);
1394  if (isSpillInstruction(MI, MF)) {
1395  Loc = extractSpillBaseRegAndOffset(MI);
1396  for (uint64_t ID : OpenRanges.getSpillVarLocs()) {
1397  LocIndex Idx = LocIndex::fromRawInteger(ID);
1398  const VarLoc &VL = VarLocIDs[Idx];
1399  assert(VL.Kind == VarLoc::SpillLocKind && "Broken VarLocSet?");
1400  if (VL.Loc.SpillLocation == *Loc) {
1401  // This location is overwritten by the current instruction -- terminate
1402  // the open range, and insert an explicit DBG_VALUE $noreg.
1403  //
1404  // Doing this at a later stage would require re-interpreting all
1405  // DBG_VALUes and DIExpressions to identify whether they point at
1406  // memory, and then analysing all memory writes to see if they
1407  // overwrite that memory, which is expensive.
1408  //
1409  // At this stage, we already know which DBG_VALUEs are for spills and
1410  // where they are located; it's best to fix handle overwrites now.
1411  KillSet.set(ID);
1412  VarLoc UndefVL = VarLoc::CreateCopyLoc(VL.MI, LS, 0);
1413  LocIndex UndefLocID = VarLocIDs.insert(UndefVL);
1414  Transfers.push_back({&MI, UndefLocID});
1415  }
1416  }
1417  OpenRanges.erase(KillSet, VarLocIDs);
1418  }
1419 
1420  // Try to recognise spill and restore instructions that may create a new
1421  // variable location.
1422  if (isLocationSpill(MI, MF, Reg)) {
1423  TKind = TransferKind::TransferSpill;
1424  LLVM_DEBUG(dbgs() << "Recognized as spill: "; MI.dump(););
1425  LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI)
1426  << "\n");
1427  } else {
1428  if (!(Loc = isRestoreInstruction(MI, MF, Reg)))
1429  return;
1430  TKind = TransferKind::TransferRestore;
1431  LLVM_DEBUG(dbgs() << "Recognized as restore: "; MI.dump(););
1432  LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI)
1433  << "\n");
1434  }
1435  // Check if the register or spill location is the location of a debug value.
1436  auto TransferCandidates = OpenRanges.getEmptyVarLocRange();
1437  if (TKind == TransferKind::TransferSpill)
1438  TransferCandidates = OpenRanges.getRegisterVarLocs(Reg);
1439  else if (TKind == TransferKind::TransferRestore)
1440  TransferCandidates = OpenRanges.getSpillVarLocs();
1441  for (uint64_t ID : TransferCandidates) {
1442  LocIndex Idx = LocIndex::fromRawInteger(ID);
1443  const VarLoc &VL = VarLocIDs[Idx];
1444  if (TKind == TransferKind::TransferSpill) {
1445  assert(VL.isDescribedByReg() == Reg && "Broken VarLocSet?");
1446  LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '('
1447  << VL.Var.getVariable()->getName() << ")\n");
1448  } else {
1449  assert(TKind == TransferKind::TransferRestore &&
1450  VL.Kind == VarLoc::SpillLocKind && "Broken VarLocSet?");
1451  if (VL.Loc.SpillLocation != *Loc)
1452  // The spill location is not the location of a debug value.
1453  continue;
1454  LLVM_DEBUG(dbgs() << "Restoring Register " << printReg(Reg, TRI) << '('
1455  << VL.Var.getVariable()->getName() << ")\n");
1456  }
1457  insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, Idx, TKind,
1458  Reg);
1459  // FIXME: A comment should explain why it's correct to return early here,
1460  // if that is in fact correct.
1461  return;
1462  }
1463 }
1464 
1465 /// If \p MI is a register copy instruction, that copies a previously tracked
1466 /// value from one register to another register that is callee saved, we
1467 /// create new DBG_VALUE instruction described with copy destination register.
1468 void VarLocBasedLDV::transferRegisterCopy(MachineInstr &MI,
1469  OpenRangesSet &OpenRanges,
1470  VarLocMap &VarLocIDs,
1471  TransferMap &Transfers) {
1472  auto DestSrc = TII->isCopyInstr(MI);
1473  if (!DestSrc)
1474  return;
1475 
1476  const MachineOperand *DestRegOp = DestSrc->Destination;
1477  const MachineOperand *SrcRegOp = DestSrc->Source;
1478 
1479  if (!DestRegOp->isDef())
1480  return;
1481 
1482  auto isCalleeSavedReg = [&](Register Reg) {
1483  for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
1484  if (CalleeSavedRegs.test(*RAI))
1485  return true;
1486  return false;
1487  };
1488 
1489  Register SrcReg = SrcRegOp->getReg();
1490  Register DestReg = DestRegOp->getReg();
1491 
1492  // We want to recognize instructions where destination register is callee
1493  // saved register. If register that could be clobbered by the call is
1494  // included, there would be a great chance that it is going to be clobbered
1495  // soon. It is more likely that previous register location, which is callee
1496  // saved, is going to stay unclobbered longer, even if it is killed.
1497  if (!isCalleeSavedReg(DestReg))
1498  return;
1499 
1500  // Remember an entry value movement. If we encounter a new debug value of
1501  // a parameter describing only a moving of the value around, rather then
1502  // modifying it, we are still able to use the entry value if needed.
1503  if (isRegOtherThanSPAndFP(*DestRegOp, MI, TRI)) {
1504  for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) {
1505  LocIndex Idx = LocIndex::fromRawInteger(ID);
1506  const VarLoc &VL = VarLocIDs[Idx];
1507  if (VL.getEntryValueBackupReg() == SrcReg) {
1508  LLVM_DEBUG(dbgs() << "Copy of the entry value: "; MI.dump(););
1509  VarLoc EntryValLocCopyBackup =
1510  VarLoc::CreateEntryCopyBackupLoc(VL.MI, LS, VL.Expr, DestReg);
1511 
1512  // Stop tracking the original entry value.
1513  OpenRanges.erase(VL);
1514 
1515  // Start tracking the entry value copy.
1516  LocIndex EntryValCopyLocID = VarLocIDs.insert(EntryValLocCopyBackup);
1517  OpenRanges.insert(EntryValCopyLocID, EntryValLocCopyBackup);
1518  break;
1519  }
1520  }
1521  }
1522 
1523  if (!SrcRegOp->isKill())
1524  return;
1525 
1526  for (uint64_t ID : OpenRanges.getRegisterVarLocs(SrcReg)) {
1527  LocIndex Idx = LocIndex::fromRawInteger(ID);
1528  assert(VarLocIDs[Idx].isDescribedByReg() == SrcReg && "Broken VarLocSet?");
1529  insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, Idx,
1530  TransferKind::TransferCopy, DestReg);
1531  // FIXME: A comment should explain why it's correct to return early here,
1532  // if that is in fact correct.
1533  return;
1534  }
1535 }
1536 
1537 /// Terminate all open ranges at the end of the current basic block.
1538 bool VarLocBasedLDV::transferTerminator(MachineBasicBlock *CurMBB,
1539  OpenRangesSet &OpenRanges,
1540  VarLocInMBB &OutLocs,
1541  const VarLocMap &VarLocIDs) {
1542  bool Changed = false;
1543 
1544  LLVM_DEBUG(for (uint64_t ID
1545  : OpenRanges.getVarLocs()) {
1546  // Copy OpenRanges to OutLocs, if not already present.
1547  dbgs() << "Add to OutLocs in MBB #" << CurMBB->getNumber() << ": ";
1548  VarLocIDs[LocIndex::fromRawInteger(ID)].dump(TRI);
1549  });
1550  VarLocSet &VLS = getVarLocsInMBB(CurMBB, OutLocs);
1551  Changed = VLS != OpenRanges.getVarLocs();
1552  // New OutLocs set may be different due to spill, restore or register
1553  // copy instruction processing.
1554  if (Changed)
1555  VLS = OpenRanges.getVarLocs();
1556  OpenRanges.clear();
1557  return Changed;
1558 }
1559 
1560 /// Accumulate a mapping between each DILocalVariable fragment and other
1561 /// fragments of that DILocalVariable which overlap. This reduces work during
1562 /// the data-flow stage from "Find any overlapping fragments" to "Check if the
1563 /// known-to-overlap fragments are present".
1564 /// \param MI A previously unprocessed DEBUG_VALUE instruction to analyze for
1565 /// fragment usage.
1566 /// \param SeenFragments Map from DILocalVariable to all fragments of that
1567 /// Variable which are known to exist.
1568 /// \param OverlappingFragments The overlap map being constructed, from one
1569 /// Var/Fragment pair to a vector of fragments known to overlap.
1570 void VarLocBasedLDV::accumulateFragmentMap(MachineInstr &MI,
1571  VarToFragments &SeenFragments,
1572  OverlapMap &OverlappingFragments) {
1573  DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(),
1574  MI.getDebugLoc()->getInlinedAt());
1575  FragmentInfo ThisFragment = MIVar.getFragmentOrDefault();
1576 
1577  // If this is the first sighting of this variable, then we are guaranteed
1578  // there are currently no overlapping fragments either. Initialize the set
1579  // of seen fragments, record no overlaps for the current one, and return.
1580  auto SeenIt = SeenFragments.find(MIVar.getVariable());
1581  if (SeenIt == SeenFragments.end()) {
1582  SmallSet<FragmentInfo, 4> OneFragment;
1583  OneFragment.insert(ThisFragment);
1584  SeenFragments.insert({MIVar.getVariable(), OneFragment});
1585 
1586  OverlappingFragments.insert({{MIVar.getVariable(), ThisFragment}, {}});
1587  return;
1588  }
1589 
1590  // If this particular Variable/Fragment pair already exists in the overlap
1591  // map, it has already been accounted for.
1592  auto IsInOLapMap =
1593  OverlappingFragments.insert({{MIVar.getVariable(), ThisFragment}, {}});
1594  if (!IsInOLapMap.second)
1595  return;
1596 
1597  auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;
1598  auto &AllSeenFragments = SeenIt->second;
1599 
1600  // Otherwise, examine all other seen fragments for this variable, with "this"
1601  // fragment being a previously unseen fragment. Record any pair of
1602  // overlapping fragments.
1603  for (auto &ASeenFragment : AllSeenFragments) {
1604  // Does this previously seen fragment overlap?
1605  if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) {
1606  // Yes: Mark the current fragment as being overlapped.
1607  ThisFragmentsOverlaps.push_back(ASeenFragment);
1608  // Mark the previously seen fragment as being overlapped by the current
1609  // one.
1610  auto ASeenFragmentsOverlaps =
1611  OverlappingFragments.find({MIVar.getVariable(), ASeenFragment});
1612  assert(ASeenFragmentsOverlaps != OverlappingFragments.end() &&
1613  "Previously seen var fragment has no vector of overlaps");
1614  ASeenFragmentsOverlaps->second.push_back(ThisFragment);
1615  }
1616  }
1617 
1618  AllSeenFragments.insert(ThisFragment);
1619 }
1620 
1621 /// This routine creates OpenRanges.
1622 void VarLocBasedLDV::process(MachineInstr &MI, OpenRangesSet &OpenRanges,
1623  VarLocMap &VarLocIDs, TransferMap &Transfers) {
1624  transferDebugValue(MI, OpenRanges, VarLocIDs);
1625  transferRegisterDef(MI, OpenRanges, VarLocIDs, Transfers);
1626  transferRegisterCopy(MI, OpenRanges, VarLocIDs, Transfers);
1627  transferSpillOrRestoreInst(MI, OpenRanges, VarLocIDs, Transfers);
1628 }
1629 
1630 /// This routine joins the analysis results of all incoming edges in @MBB by
1631 /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
1632 /// source variable in all the predecessors of @MBB reside in the same location.
1633 bool VarLocBasedLDV::join(
1634  MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
1635  const VarLocMap &VarLocIDs,
1637  SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks) {
1638  LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
1639 
1640  VarLocSet InLocsT(Alloc); // Temporary incoming locations.
1641 
1642  // For all predecessors of this MBB, find the set of VarLocs that
1643  // can be joined.
1644  int NumVisited = 0;
1645  for (auto p : MBB.predecessors()) {
1646  // Ignore backedges if we have not visited the predecessor yet. As the
1647  // predecessor hasn't yet had locations propagated into it, most locations
1648  // will not yet be valid, so treat them as all being uninitialized and
1649  // potentially valid. If a location guessed to be correct here is
1650  // invalidated later, we will remove it when we revisit this block.
1651  if (!Visited.count(p)) {
1652  LLVM_DEBUG(dbgs() << " ignoring unvisited pred MBB: " << p->getNumber()
1653  << "\n");
1654  continue;
1655  }
1656  auto OL = OutLocs.find(p);
1657  // Join is null in case of empty OutLocs from any of the pred.
1658  if (OL == OutLocs.end())
1659  return false;
1660 
1661  // Just copy over the Out locs to incoming locs for the first visited
1662  // predecessor, and for all other predecessors join the Out locs.
1663  VarLocSet &OutLocVLS = *OL->second.get();
1664  if (!NumVisited)
1665  InLocsT = OutLocVLS;
1666  else
1667  InLocsT &= OutLocVLS;
1668 
1669  LLVM_DEBUG({
1670  if (!InLocsT.empty()) {
1671  for (uint64_t ID : InLocsT)
1672  dbgs() << " gathered candidate incoming var: "
1673  << VarLocIDs[LocIndex::fromRawInteger(ID)]
1674  .Var.getVariable()
1675  ->getName()
1676  << "\n";
1677  }
1678  });
1679 
1680  NumVisited++;
1681  }
1682 
1683  // Filter out DBG_VALUES that are out of scope.
1684  VarLocSet KillSet(Alloc);
1685  bool IsArtificial = ArtificialBlocks.count(&MBB);
1686  if (!IsArtificial) {
1687  for (uint64_t ID : InLocsT) {
1688  LocIndex Idx = LocIndex::fromRawInteger(ID);
1689  if (!VarLocIDs[Idx].dominates(LS, MBB)) {
1690  KillSet.set(ID);
1691  LLVM_DEBUG({
1692  auto Name = VarLocIDs[Idx].Var.getVariable()->getName();
1693  dbgs() << " killing " << Name << ", it doesn't dominate MBB\n";
1694  });
1695  }
1696  }
1697  }
1698  InLocsT.intersectWithComplement(KillSet);
1699 
1700  // As we are processing blocks in reverse post-order we
1701  // should have processed at least one predecessor, unless it
1702  // is the entry block which has no predecessor.
1703  assert((NumVisited || MBB.pred_empty()) &&
1704  "Should have processed at least one predecessor");
1705 
1706  VarLocSet &ILS = getVarLocsInMBB(&MBB, InLocs);
1707  bool Changed = false;
1708  if (ILS != InLocsT) {
1709  ILS = InLocsT;
1710  Changed = true;
1711  }
1712 
1713  return Changed;
1714 }
1715 
1716 void VarLocBasedLDV::flushPendingLocs(VarLocInMBB &PendingInLocs,
1717  VarLocMap &VarLocIDs) {
1718  // PendingInLocs records all locations propagated into blocks, which have
1719  // not had DBG_VALUE insts created. Go through and create those insts now.
1720  for (auto &Iter : PendingInLocs) {
1721  // Map is keyed on a constant pointer, unwrap it so we can insert insts.
1722  auto &MBB = const_cast<MachineBasicBlock &>(*Iter.first);
1723  VarLocSet &Pending = *Iter.second.get();
1724 
1725  for (uint64_t ID : Pending) {
1726  // The ID location is live-in to MBB -- work out what kind of machine
1727  // location it is and create a DBG_VALUE.
1728  const VarLoc &DiffIt = VarLocIDs[LocIndex::fromRawInteger(ID)];
1729  if (DiffIt.isEntryBackupLoc())
1730  continue;
1731  MachineInstr *MI = DiffIt.BuildDbgValue(*MBB.getParent());
1732  MBB.insert(MBB.instr_begin(), MI);
1733 
1734  (void)MI;
1735  LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump(););
1736  }
1737  }
1738 }
1739 
1740 bool VarLocBasedLDV::isEntryValueCandidate(
1741  const MachineInstr &MI, const DefinedRegsSet &DefinedRegs) const {
1742  assert(MI.isDebugValue() && "This must be DBG_VALUE.");
1743 
1744  // TODO: Add support for local variables that are expressed in terms of
1745  // parameters entry values.
1746  // TODO: Add support for modified arguments that can be expressed
1747  // by using its entry value.
1748  auto *DIVar = MI.getDebugVariable();
1749  if (!DIVar->isParameter())
1750  return false;
1751 
1752  // Do not consider parameters that belong to an inlined function.
1753  if (MI.getDebugLoc()->getInlinedAt())
1754  return false;
1755 
1756  // Only consider parameters that are described using registers. Parameters
1757  // that are passed on the stack are not yet supported, so ignore debug
1758  // values that are described by the frame or stack pointer.
1759  if (!isRegOtherThanSPAndFP(MI.getDebugOperand(0), MI, TRI))
1760  return false;
1761 
1762  // If a parameter's value has been propagated from the caller, then the
1763  // parameter's DBG_VALUE may be described using a register defined by some
1764  // instruction in the entry block, in which case we shouldn't create an
1765  // entry value.
1766  if (DefinedRegs.count(MI.getDebugOperand(0).getReg()))
1767  return false;
1768 
1769  // TODO: Add support for parameters that have a pre-existing debug expressions
1770  // (e.g. fragments).
1771  if (MI.getDebugExpression()->getNumElements() > 0)
1772  return false;
1773 
1774  return true;
1775 }
1776 
1777 /// Collect all register defines (including aliases) for the given instruction.
1778 static void collectRegDefs(const MachineInstr &MI, DefinedRegsSet &Regs,
1779  const TargetRegisterInfo *TRI) {
1780  for (const MachineOperand &MO : MI.operands())
1781  if (MO.isReg() && MO.isDef() && MO.getReg())
1782  for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
1783  Regs.insert(*AI);
1784 }
1785 
1786 /// This routine records the entry values of function parameters. The values
1787 /// could be used as backup values. If we loose the track of some unmodified
1788 /// parameters, the backup values will be used as a primary locations.
1789 void VarLocBasedLDV::recordEntryValue(const MachineInstr &MI,
1790  const DefinedRegsSet &DefinedRegs,
1791  OpenRangesSet &OpenRanges,
1792  VarLocMap &VarLocIDs) {
1793  if (TPC) {
1794  auto &TM = TPC->getTM<TargetMachine>();
1795  if (!TM.Options.ShouldEmitDebugEntryValues())
1796  return;
1797  }
1798 
1799  DebugVariable V(MI.getDebugVariable(), MI.getDebugExpression(),
1800  MI.getDebugLoc()->getInlinedAt());
1801 
1802  if (!isEntryValueCandidate(MI, DefinedRegs) ||
1803  OpenRanges.getEntryValueBackup(V))
1804  return;
1805 
1806  LLVM_DEBUG(dbgs() << "Creating the backup entry location: "; MI.dump(););
1807 
1808  // Create the entry value and use it as a backup location until it is
1809  // valid. It is valid until a parameter is not changed.
1811  DIExpression::prepend(MI.getDebugExpression(), DIExpression::EntryValue);
1812  VarLoc EntryValLocAsBackup = VarLoc::CreateEntryBackupLoc(MI, LS, NewExpr);
1813  LocIndex EntryValLocID = VarLocIDs.insert(EntryValLocAsBackup);
1814  OpenRanges.insert(EntryValLocID, EntryValLocAsBackup);
1815 }
1816 
1817 /// Calculate the liveness information for the given machine function and
1818 /// extend ranges across basic blocks.
1819 bool VarLocBasedLDV::ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) {
1820  LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
1821 
1822  if (!MF.getFunction().getSubprogram())
1823  // VarLocBaseLDV will already have removed all DBG_VALUEs.
1824  return false;
1825 
1826  // Skip functions from NoDebug compilation units.
1827  if (MF.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
1829  return false;
1830 
1831  TRI = MF.getSubtarget().getRegisterInfo();
1832  TII = MF.getSubtarget().getInstrInfo();
1833  TFI = MF.getSubtarget().getFrameLowering();
1834  TFI->getCalleeSaves(MF, CalleeSavedRegs);
1835  this->TPC = TPC;
1836  LS.initialize(MF);
1837 
1838  bool Changed = false;
1839  bool OLChanged = false;
1840  bool MBBJoined = false;
1841 
1842  VarLocMap VarLocIDs; // Map VarLoc<>unique ID for use in bitvectors.
1843  OverlapMap OverlapFragments; // Map of overlapping variable fragments.
1844  OpenRangesSet OpenRanges(Alloc, OverlapFragments);
1845  // Ranges that are open until end of bb.
1846  VarLocInMBB OutLocs; // Ranges that exist beyond bb.
1847  VarLocInMBB InLocs; // Ranges that are incoming after joining.
1848  TransferMap Transfers; // DBG_VALUEs associated with transfers (such as
1849  // spills, copies and restores).
1850 
1851  VarToFragments SeenFragments;
1852 
1853  // Blocks which are artificial, i.e. blocks which exclusively contain
1854  // instructions without locations, or with line 0 locations.
1856 
1859  std::priority_queue<unsigned int, std::vector<unsigned int>,
1860  std::greater<unsigned int>>
1861  Worklist;
1862  std::priority_queue<unsigned int, std::vector<unsigned int>,
1863  std::greater<unsigned int>>
1864  Pending;
1865 
1866  // Set of register defines that are seen when traversing the entry block
1867  // looking for debug entry value candidates.
1868  DefinedRegsSet DefinedRegs;
1869 
1870  // Only in the case of entry MBB collect DBG_VALUEs representing
1871  // function parameters in order to generate debug entry values for them.
1872  MachineBasicBlock &First_MBB = *(MF.begin());
1873  for (auto &MI : First_MBB) {
1874  collectRegDefs(MI, DefinedRegs, TRI);
1875  if (MI.isDebugValue())
1876  recordEntryValue(MI, DefinedRegs, OpenRanges, VarLocIDs);
1877  }
1878 
1879  // Initialize per-block structures and scan for fragment overlaps.
1880  for (auto &MBB : MF)
1881  for (auto &MI : MBB)
1882  if (MI.isDebugValue())
1883  accumulateFragmentMap(MI, SeenFragments, OverlapFragments);
1884 
1885  auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
1886  if (const DebugLoc &DL = MI.getDebugLoc())
1887  return DL.getLine() != 0;
1888  return false;
1889  };
1890  for (auto &MBB : MF)
1891  if (none_of(MBB.instrs(), hasNonArtificialLocation))
1892  ArtificialBlocks.insert(&MBB);
1893 
1894  LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
1895  "OutLocs after initialization", dbgs()));
1896 
1898  unsigned int RPONumber = 0;
1899  for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
1900  OrderToBB[RPONumber] = *RI;
1901  BBToOrder[*RI] = RPONumber;
1902  Worklist.push(RPONumber);
1903  ++RPONumber;
1904  }
1905 
1906  if (RPONumber > InputBBLimit) {
1907  unsigned NumInputDbgValues = 0;
1908  for (auto &MBB : MF)
1909  for (auto &MI : MBB)
1910  if (MI.isDebugValue())
1911  ++NumInputDbgValues;
1912  if (NumInputDbgValues > InputDbgValueLimit) {
1913  LLVM_DEBUG(dbgs() << "Disabling VarLocBasedLDV: " << MF.getName()
1914  << " has " << RPONumber << " basic blocks and "
1915  << NumInputDbgValues
1916  << " input DBG_VALUEs, exceeding limits.\n");
1917  return false;
1918  }
1919  }
1920 
1921  // This is a standard "union of predecessor outs" dataflow problem.
1922  // To solve it, we perform join() and process() using the two worklist method
1923  // until the ranges converge.
1924  // Ranges have converged when both worklists are empty.
1926  while (!Worklist.empty() || !Pending.empty()) {
1927  // We track what is on the pending worklist to avoid inserting the same
1928  // thing twice. We could avoid this with a custom priority queue, but this
1929  // is probably not worth it.
1931  LLVM_DEBUG(dbgs() << "Processing Worklist\n");
1932  while (!Worklist.empty()) {
1933  MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
1934  Worklist.pop();
1935  MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs, Visited,
1936  ArtificialBlocks);
1937  MBBJoined |= Visited.insert(MBB).second;
1938  if (MBBJoined) {
1939  MBBJoined = false;
1940  Changed = true;
1941  // Now that we have started to extend ranges across BBs we need to
1942  // examine spill, copy and restore instructions to see whether they
1943  // operate with registers that correspond to user variables.
1944  // First load any pending inlocs.
1945  OpenRanges.insertFromLocSet(getVarLocsInMBB(MBB, InLocs), VarLocIDs);
1946  for (auto &MI : *MBB)
1947  process(MI, OpenRanges, VarLocIDs, Transfers);
1948  OLChanged |= transferTerminator(MBB, OpenRanges, OutLocs, VarLocIDs);
1949 
1950  LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
1951  "OutLocs after propagating", dbgs()));
1952  LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
1953  "InLocs after propagating", dbgs()));
1954 
1955  if (OLChanged) {
1956  OLChanged = false;
1957  for (auto s : MBB->successors())
1958  if (OnPending.insert(s).second) {
1959  Pending.push(BBToOrder[s]);
1960  }
1961  }
1962  }
1963  }
1964  Worklist.swap(Pending);
1965  // At this point, pending must be empty, since it was just the empty
1966  // worklist
1967  assert(Pending.empty() && "Pending should be empty");
1968  }
1969 
1970  // Add any DBG_VALUE instructions created by location transfers.
1971  for (auto &TR : Transfers) {
1972  assert(!TR.TransferInst->isTerminator() &&
1973  "Cannot insert DBG_VALUE after terminator");
1974  MachineBasicBlock *MBB = TR.TransferInst->getParent();
1975  const VarLoc &VL = VarLocIDs[TR.LocationID];
1976  MachineInstr *MI = VL.BuildDbgValue(MF);
1977  MBB->insertAfterBundle(TR.TransferInst->getIterator(), MI);
1978  }
1979  Transfers.clear();
1980 
1981  // Deferred inlocs will not have had any DBG_VALUE insts created; do
1982  // that now.
1983  flushPendingLocs(InLocs, VarLocIDs);
1984 
1985  LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs()));
1986  LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs()));
1987  return Changed;
1988 }
1989 
1990 LDVImpl *
1992 {
1993  return new VarLocBasedLDV();
1994 }
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
const NoneType None
Definition: None.h:23
const FragmentInfo getFragmentOrDefault() const
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
static bool isConstant(const MachineInstr &MI)
instr_iterator instr_begin()
StackOffset is a class to represent an offset with 2 dimensions, named fixed and scalable,...
Definition: TypeSize.h:130
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,...
static bool fragmentsOverlap(const FragmentInfo &A, const FragmentInfo &B)
Check if fragments overlap between a pair of FragmentInfos.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
void push_back(const T &Elt)
Definition: SmallVector.h:379
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
unsigned Reg
virtual const TargetLowering * getTargetLowering() const
bool test(unsigned Idx) const
Definition: BitVector.h:484
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
A debug info location.
Definition: DebugLoc.h:33
TMC & getTM() const
Get the right type of TargetMachine for this target.
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.
static Register isDescribedByReg(const MachineInstr &MI)
iterator_range< succ_iterator > successors()
Function & getFunction()
Return the LLVM function that this machine code represents.
MachineBasicBlock & MBB
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 ...
Identifies a unique instance of a variable.
StringRef getName() const
const HexagonInstrInfo * TII
RegisterKind
LDVImpl * makeVarLocBasedLiveDebugValues()
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
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:1512
Target-Independent Code Generator Pass Configuration Options.
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Holds the characteristics of one fragment of a larger variable.
void dump() const
Definition: Pass.cpp:131
unsigned getMetadataID() const
Definition: Metadata.h:100
const DILocation * getInlinedAt() const
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
virtual const TargetInstrInfo * getInstrInfo() const
Debug location.
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
static void collectRegDefs(const MachineInstr &MI, DefinedRegsSet &Regs, const TargetRegisterInfo *TRI)
Collect all register defines (including aliases) for the given instruction.
TargetInstrInfo - Interface to description of machine instruction set.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:427
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:1397
static cl::opt< unsigned > InputDbgValueLimit("livedebugvalues-input-dbg-value-limit", cl::desc("Maximum input DBG_VALUE insts supported by debug range extension"), cl::init(50000), cl::Hidden)
This file declares the machine register scavenger class.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1513
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...
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:273
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
bool isValidLocationForIntrinsic(const DILocation *DL) const
Check that a location is valid for this variable.
MCRegAliasIterator enumerates all registers aliasing Reg.
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:1505
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:375
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
iterator_range< pred_iterator > predecessors()
Register getStackPointerRegisterToSaveRestore() const
If a physical register, this specifies the register that llvm.savestack/llvm.restorestack should save...
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:263
Basic Register Allocator
uint64_t Offset
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:442
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
MachineOperand class - Representation of each machine instruction operand.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1116
Module.h This file contains the declarations for the Module class.
uint32_t Index
Information about stack frame layout on the target.
Promote Memory to Register
Definition: Mem2Reg.cpp:110
DWARF expression.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
A range adaptor for a pair of iterators.
Special value supplied for machine level alias analysis.
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:232
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:721
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.
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:2037
Representation of each machine instruction.
Definition: MachineInstr.h:62
virtual void getCalleeSaves(const MachineFunction &MF, BitVector &SavedRegs) const
Returns the callee-saved registers as computed by determineCalleeSaves in the BitVector SavedRegs.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
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.
LexicalScopes - This class provides interface to collect and use lexical scoping information from mac...
static Register isDbgValueDescribedByReg(const MachineInstr &MI)
static cl::opt< unsigned > InputBBLimit("livedebugvalues-input-bb-limit", cl::desc("Maximum input basic blocks before DBG_VALUE limit applies"), cl::init(10000), cl::Hidden)
#define I(x, y, z)
Definition: MD5.cpp:59
virtual const TargetFrameLowering * getFrameLowering() const
virtual void print(raw_ostream &OS, const Module *M) const
print - Print out the internal state of the pass.
Definition: Pass.cpp:125
const DILocalVariable * getVariable() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:343
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:77
IRTranslator LLVM IR MI
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:2035
Register getReg() const
getReg - Returns the register number.
static bool dominates(MachineBasicBlock &MBB, MachineBasicBlock::const_iterator A, MachineBasicBlock::const_iterator B)
#define LLVM_DEBUG(X)
Definition: Debug.h:122
A bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals.
static bool isDefaultFragment(const FragmentInfo F)
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
This file describes how to lower LLVM code to machine code.
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL