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