LLVM  10.0.0svn
LiveDebugValues.cpp
Go to the documentation of this file.
1 //===- LiveDebugValues.cpp - Tracking Debug Value MIs ---------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// This pass implements a data flow analysis that propagates debug location
10 /// information by inserting additional DBG_VALUE insts into the machine
11 /// instruction stream. Before running, each DBG_VALUE inst corresponds to a
12 /// source assignment of a variable. Afterwards, a DBG_VALUE inst specifies a
13 /// variable location for the current basic block (see SourceLevelDebugging.rst).
14 ///
15 /// This is a separate pass from DbgValueHistoryCalculator to facilitate
16 /// testing and improve modularity.
17 ///
18 /// Each variable location is represented by a VarLoc object that identifies the
19 /// source variable, its current machine-location, and the DBG_VALUE inst that
20 /// specifies the location. Each VarLoc is indexed in the (function-scope)
21 /// VarLocMap, giving each VarLoc a unique index. Rather than operate directly
22 /// on machine locations, the dataflow analysis in this pass identifies
23 /// locations by their index in the VarLocMap, meaning all the variable
24 /// locations in a block can be described by a sparse vector of VarLocMap
25 /// indexes.
26 ///
27 //===----------------------------------------------------------------------===//
28 
29 #include "llvm/ADT/DenseMap.h"
31 #include "llvm/ADT/SmallPtrSet.h"
32 #include "llvm/ADT/SmallSet.h"
33 #include "llvm/ADT/SmallVector.h"
35 #include "llvm/ADT/Statistic.h"
36 #include "llvm/ADT/UniqueVector.h"
54 #include "llvm/Config/llvm-config.h"
55 #include "llvm/IR/DIBuilder.h"
57 #include "llvm/IR/DebugLoc.h"
58 #include "llvm/IR/Function.h"
59 #include "llvm/IR/Module.h"
60 #include "llvm/MC/MCRegisterInfo.h"
61 #include "llvm/Pass.h"
62 #include "llvm/Support/Casting.h"
63 #include "llvm/Support/Compiler.h"
64 #include "llvm/Support/Debug.h"
66 #include <algorithm>
67 #include <cassert>
68 #include <cstdint>
69 #include <functional>
70 #include <queue>
71 #include <tuple>
72 #include <utility>
73 #include <vector>
74 
75 using namespace llvm;
76 
77 #define DEBUG_TYPE "livedebugvalues"
78 
79 STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
80 STATISTIC(NumRemoved, "Number of DBG_VALUE instructions removed");
81 
82 // If @MI is a DBG_VALUE with debug value described by a defined
83 // register, returns the number of this register. In the other case, returns 0.
85  assert(MI.isDebugValue() && "expected a DBG_VALUE");
86  assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
87  // If location of variable is described using a register (directly
88  // or indirectly), this register is always a first operand.
89  return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : Register();
90 }
91 
92 namespace {
93 
94 class LiveDebugValues : public MachineFunctionPass {
95 private:
96  const TargetRegisterInfo *TRI;
97  const TargetInstrInfo *TII;
98  const TargetFrameLowering *TFI;
99  BitVector CalleeSavedRegs;
101 
102  enum struct TransferKind { TransferCopy, TransferSpill, TransferRestore };
103 
104  /// Keeps track of lexical scopes associated with a user value's source
105  /// location.
106  class UserValueScopes {
107  DebugLoc DL;
108  LexicalScopes &LS;
110 
111  public:
112  UserValueScopes(DebugLoc D, LexicalScopes &L) : DL(std::move(D)), LS(L) {}
113 
114  /// Return true if current scope dominates at least one machine
115  /// instruction in a given machine basic block.
116  bool dominates(MachineBasicBlock *MBB) {
117  if (LBlocks.empty())
118  LS.getMachineBasicBlocks(DL, LBlocks);
119  return LBlocks.count(MBB) != 0 || LS.dominates(DL, MBB);
120  }
121  };
122 
123  using FragmentInfo = DIExpression::FragmentInfo;
124  using OptFragmentInfo = Optional<DIExpression::FragmentInfo>;
125 
126  /// Storage for identifying a potentially inlined instance of a variable,
127  /// or a fragment thereof.
128  class DebugVariable {
129  const DILocalVariable *Variable;
130  OptFragmentInfo Fragment;
131  const DILocation *InlinedAt;
132 
133  /// Fragment that will overlap all other fragments. Used as default when
134  /// caller demands a fragment.
135  static const FragmentInfo DefaultFragment;
136 
137  public:
138  DebugVariable(const DILocalVariable *Var, OptFragmentInfo &&FragmentInfo,
139  const DILocation *InlinedAt)
140  : Variable(Var), Fragment(FragmentInfo), InlinedAt(InlinedAt) {}
141 
142  DebugVariable(const DILocalVariable *Var, OptFragmentInfo &FragmentInfo,
143  const DILocation *InlinedAt)
144  : Variable(Var), Fragment(FragmentInfo), InlinedAt(InlinedAt) {}
145 
146  DebugVariable(const DILocalVariable *Var, const DIExpression *DIExpr,
147  const DILocation *InlinedAt)
148  : DebugVariable(Var, DIExpr->getFragmentInfo(), InlinedAt) {}
149 
150  DebugVariable(const MachineInstr &MI)
151  : DebugVariable(MI.getDebugVariable(),
153  MI.getDebugLoc()->getInlinedAt()) {}
154 
155  const DILocalVariable *getVar() const { return Variable; }
156  const OptFragmentInfo &getFragment() const { return Fragment; }
157  const DILocation *getInlinedAt() const { return InlinedAt; }
158 
159  const FragmentInfo getFragmentDefault() const {
160  return Fragment.getValueOr(DefaultFragment);
161  }
162 
163  static bool isFragmentDefault(FragmentInfo &F) {
164  return F == DefaultFragment;
165  }
166 
167  bool operator==(const DebugVariable &Other) const {
168  return std::tie(Variable, Fragment, InlinedAt) ==
169  std::tie(Other.Variable, Other.Fragment, Other.InlinedAt);
170  }
171 
172  bool operator<(const DebugVariable &Other) const {
173  return std::tie(Variable, Fragment, InlinedAt) <
174  std::tie(Other.Variable, Other.Fragment, Other.InlinedAt);
175  }
176  };
177 
178  friend struct llvm::DenseMapInfo<DebugVariable>;
179 
180  /// A pair of debug variable and value location.
181  struct VarLoc {
182  // The location at which a spilled variable resides. It consists of a
183  // register and an offset.
184  struct SpillLoc {
185  unsigned SpillBase;
186  int SpillOffset;
187  bool operator==(const SpillLoc &Other) const {
188  return SpillBase == Other.SpillBase && SpillOffset == Other.SpillOffset;
189  }
190  };
191 
192  /// Identity of the variable at this location.
193  const DebugVariable Var;
194 
195  /// The expression applied to this location.
196  const DIExpression *Expr;
197 
198  /// DBG_VALUE to clone var/expr information from if this location
199  /// is moved.
200  const MachineInstr &MI;
201 
202  mutable UserValueScopes UVS;
203  enum VarLocKind {
204  InvalidKind = 0,
205  RegisterKind,
206  SpillLocKind,
207  ImmediateKind,
208  EntryValueKind
209  } Kind = InvalidKind;
210 
211  /// The value location. Stored separately to avoid repeatedly
212  /// extracting it from MI.
213  union {
214  uint64_t RegNo;
215  SpillLoc SpillLocation;
216  uint64_t Hash;
217  int64_t Immediate;
218  const ConstantFP *FPImm;
219  const ConstantInt *CImm;
220  } Loc;
221 
222  VarLoc(const MachineInstr &MI, LexicalScopes &LS)
223  : Var(MI), Expr(MI.getDebugExpression()), MI(MI),
224  UVS(MI.getDebugLoc(), LS) {
225  static_assert((sizeof(Loc) == sizeof(uint64_t)),
226  "hash does not cover all members of Loc");
227  assert(MI.isDebugValue() && "not a DBG_VALUE");
228  assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
229  if (int RegNo = isDbgValueDescribedByReg(MI)) {
230  Kind = MI.isDebugEntryValue() ? EntryValueKind : RegisterKind;
231  Loc.RegNo = RegNo;
232  } else if (MI.getOperand(0).isImm()) {
233  Kind = ImmediateKind;
234  Loc.Immediate = MI.getOperand(0).getImm();
235  } else if (MI.getOperand(0).isFPImm()) {
236  Kind = ImmediateKind;
237  Loc.FPImm = MI.getOperand(0).getFPImm();
238  } else if (MI.getOperand(0).isCImm()) {
239  Kind = ImmediateKind;
240  Loc.CImm = MI.getOperand(0).getCImm();
241  }
242  assert((Kind != ImmediateKind || !MI.isDebugEntryValue()) &&
243  "entry values must be register locations");
244  }
245 
246  /// Take the variable and machine-location in DBG_VALUE MI, and build an
247  /// entry location using the given expression.
248  static VarLoc CreateEntryLoc(const MachineInstr &MI, LexicalScopes &LS,
249  const DIExpression *EntryExpr) {
250  VarLoc VL(MI, LS);
251  VL.Kind = EntryValueKind;
252  VL.Expr = EntryExpr;
253  return VL;
254  }
255 
256  /// Copy the register location in DBG_VALUE MI, updating the register to
257  /// be NewReg.
258  static VarLoc CreateCopyLoc(const MachineInstr &MI, LexicalScopes &LS,
259  unsigned NewReg) {
260  VarLoc VL(MI, LS);
261  assert(VL.Kind == RegisterKind);
262  VL.Loc.RegNo = NewReg;
263  return VL;
264  }
265 
266  /// Take the variable described by DBG_VALUE MI, and create a VarLoc
267  /// locating it in the specified spill location.
268  static VarLoc CreateSpillLoc(const MachineInstr &MI, unsigned SpillBase,
269  int SpillOffset, LexicalScopes &LS) {
270  VarLoc VL(MI, LS);
271  assert(VL.Kind == RegisterKind);
272  VL.Kind = SpillLocKind;
273  VL.Loc.SpillLocation = {SpillBase, SpillOffset};
274  return VL;
275  }
276 
277  /// Create a DBG_VALUE representing this VarLoc in the given function.
278  /// Copies variable-specific information such as DILocalVariable and
279  /// inlining information from the original DBG_VALUE instruction, which may
280  /// have been several transfers ago.
281  MachineInstr *BuildDbgValue(MachineFunction &MF) const {
282  const DebugLoc &DbgLoc = MI.getDebugLoc();
283  bool Indirect = MI.isIndirectDebugValue();
284  const auto &IID = MI.getDesc();
285  const DILocalVariable *Var = MI.getDebugVariable();
286  const DIExpression *DIExpr = MI.getDebugExpression();
287 
288  switch (Kind) {
289  case EntryValueKind:
290  // An entry value is a register location -- but with an updated
291  // expression.
292  return BuildMI(MF, DbgLoc, IID, Indirect, Loc.RegNo, Var, Expr);
293  case RegisterKind:
294  // Register locations are like the source DBG_VALUE, but with the
295  // register number from this VarLoc.
296  return BuildMI(MF, DbgLoc, IID, Indirect, Loc.RegNo, Var, DIExpr);
297  case SpillLocKind: {
298  // Spills are indirect DBG_VALUEs, with a base register and offset.
299  // Use the original DBG_VALUEs expression to build the spilt location
300  // on top of. FIXME: spill locations created before this pass runs
301  // are not recognized, and not handled here.
302  auto *SpillExpr = DIExpression::prepend(
303  DIExpr, DIExpression::ApplyOffset, Loc.SpillLocation.SpillOffset);
304  unsigned Base = Loc.SpillLocation.SpillBase;
305  return BuildMI(MF, DbgLoc, IID, true, Base, Var, SpillExpr);
306  }
307  case ImmediateKind: {
308  MachineOperand MO = MI.getOperand(0);
309  return BuildMI(MF, DbgLoc, IID, Indirect, MO, Var, DIExpr);
310  }
311  case InvalidKind:
312  llvm_unreachable("Tried to produce DBG_VALUE for invalid VarLoc");
313  }
314  llvm_unreachable("Unrecognized LiveDebugValues.VarLoc.Kind enum");
315  }
316 
317  /// Is the Loc field a constant or constant object?
318  bool isConstant() const { return Kind == ImmediateKind; }
319 
320  /// If this variable is described by a register, return it,
321  /// otherwise return 0.
322  unsigned isDescribedByReg() const {
323  if (Kind == RegisterKind)
324  return Loc.RegNo;
325  return 0;
326  }
327 
328  /// Determine whether the lexical scope of this value's debug location
329  /// dominates MBB.
330  bool dominates(MachineBasicBlock &MBB) const { return UVS.dominates(&MBB); }
331 
332 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
333  // TRI can be null.
334  void dump(const TargetRegisterInfo *TRI, raw_ostream &Out = dbgs()) const {
335  dbgs() << "VarLoc(";
336  switch (Kind) {
337  case RegisterKind:
338  case EntryValueKind:
339  dbgs() << printReg(Loc.RegNo, TRI);
340  break;
341  case SpillLocKind:
342  dbgs() << printReg(Loc.SpillLocation.SpillBase, TRI);
343  dbgs() << "[" << Loc.SpillLocation.SpillOffset << "]";
344  break;
345  case ImmediateKind:
346  dbgs() << Loc.Immediate;
347  break;
348  case InvalidKind:
349  llvm_unreachable("Invalid VarLoc in dump method");
350  }
351 
352  dbgs() << ", \"" << Var.getVar()->getName() << "\", " << *Expr << ", ";
353  if (Var.getInlinedAt())
354  dbgs() << "!" << Var.getInlinedAt()->getMetadataID() << ")\n";
355  else
356  dbgs() << "(null))\n";
357  }
358 #endif
359 
360  bool operator==(const VarLoc &Other) const {
361  return Kind == Other.Kind && Var == Other.Var &&
362  Loc.Hash == Other.Loc.Hash && Expr == Other.Expr;
363  }
364 
365  /// This operator guarantees that VarLocs are sorted by Variable first.
366  bool operator<(const VarLoc &Other) const {
367  return std::tie(Var, Kind, Loc.Hash, Expr) <
368  std::tie(Other.Var, Other.Kind, Other.Loc.Hash, Other.Expr);
369  }
370  };
371 
373  using VarLocMap = UniqueVector<VarLoc>;
374  using VarLocSet = SparseBitVector<>;
376  struct TransferDebugPair {
377  MachineInstr *TransferInst; /// Instruction where this transfer occurs.
378  unsigned LocationID; /// Location number for the transfer dest.
379  };
380  using TransferMap = SmallVector<TransferDebugPair, 4>;
381 
382  // Types for recording sets of variable fragments that overlap. For a given
383  // local variable, we record all other fragments of that variable that could
384  // overlap it, to reduce search time.
385  using FragmentOfVar =
386  std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
387  using OverlapMap =
389 
390  // Helper while building OverlapMap, a map of all fragments seen for a given
391  // DILocalVariable.
392  using VarToFragments =
394 
395  /// This holds the working set of currently open ranges. For fast
396  /// access, this is done both as a set of VarLocIDs, and a map of
397  /// DebugVariable to recent VarLocID. Note that a DBG_VALUE ends all
398  /// previous open ranges for the same variable.
399  class OpenRangesSet {
400  VarLocSet VarLocs;
402  OverlapMap &OverlappingFragments;
403 
404  public:
405  OpenRangesSet(OverlapMap &_OLapMap) : OverlappingFragments(_OLapMap) {}
406 
407  const VarLocSet &getVarLocs() const { return VarLocs; }
408 
409  /// Terminate all open ranges for Var by removing it from the set.
410  void erase(DebugVariable Var);
411 
412  /// Terminate all open ranges listed in \c KillSet by removing
413  /// them from the set.
414  void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs) {
415  VarLocs.intersectWithComplement(KillSet);
416  for (unsigned ID : KillSet)
417  Vars.erase(VarLocIDs[ID].Var);
418  }
419 
420  /// Insert a new range into the set.
421  void insert(unsigned VarLocID, DebugVariable Var) {
422  VarLocs.set(VarLocID);
423  Vars.insert({Var, VarLocID});
424  }
425 
426  /// Insert a set of ranges.
427  void insertFromLocSet(const VarLocSet &ToLoad, const VarLocMap &Map) {
428  for (unsigned Id : ToLoad) {
429  const VarLoc &Var = Map[Id];
430  insert(Id, Var.Var);
431  }
432  }
433 
434  /// Empty the set.
435  void clear() {
436  VarLocs.clear();
437  Vars.clear();
438  }
439 
440  /// Return whether the set is empty or not.
441  bool empty() const {
442  assert(Vars.empty() == VarLocs.empty() && "open ranges are inconsistent");
443  return VarLocs.empty();
444  }
445  };
446 
447  /// Tests whether this instruction is a spill to a stack location.
448  bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF);
449 
450  /// Decide if @MI is a spill instruction and return true if it is. We use 2
451  /// criteria to make this decision:
452  /// - Is this instruction a store to a spill slot?
453  /// - Is there a register operand that is both used and killed?
454  /// TODO: Store optimization can fold spills into other stores (including
455  /// other spills). We do not handle this yet (more than one memory operand).
456  bool isLocationSpill(const MachineInstr &MI, MachineFunction *MF,
457  unsigned &Reg);
458 
459  /// If a given instruction is identified as a spill, return the spill location
460  /// and set \p Reg to the spilled register.
461  Optional<VarLoc::SpillLoc> isRestoreInstruction(const MachineInstr &MI,
462  MachineFunction *MF,
463  unsigned &Reg);
464  /// Given a spill instruction, extract the register and offset used to
465  /// address the spill location in a target independent way.
466  VarLoc::SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI);
467  void insertTransferDebugPair(MachineInstr &MI, OpenRangesSet &OpenRanges,
468  TransferMap &Transfers, VarLocMap &VarLocIDs,
469  unsigned OldVarID, TransferKind Kind,
470  unsigned NewReg = 0);
471 
472  void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
473  VarLocMap &VarLocIDs);
474  void transferSpillOrRestoreInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
475  VarLocMap &VarLocIDs, TransferMap &Transfers);
476  void emitEntryValues(MachineInstr &MI, OpenRangesSet &OpenRanges,
477  VarLocMap &VarLocIDs, TransferMap &Transfers,
478  DebugParamMap &DebugEntryVals,
479  SparseBitVector<> &KillSet);
480  void transferRegisterCopy(MachineInstr &MI, OpenRangesSet &OpenRanges,
481  VarLocMap &VarLocIDs, TransferMap &Transfers);
482  void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
483  VarLocMap &VarLocIDs, TransferMap &Transfers,
484  DebugParamMap &DebugEntryVals);
485  bool transferTerminator(MachineBasicBlock *MBB, OpenRangesSet &OpenRanges,
486  VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs);
487 
488  void process(MachineInstr &MI, OpenRangesSet &OpenRanges,
489  VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
490  TransferMap &Transfers, DebugParamMap &DebugEntryVals,
491  OverlapMap &OverlapFragments,
492  VarToFragments &SeenFragments);
493 
494  void accumulateFragmentMap(MachineInstr &MI, VarToFragments &SeenFragments,
495  OverlapMap &OLapMap);
496 
497  bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
498  const VarLocMap &VarLocIDs,
501  VarLocInMBB &PendingInLocs);
502 
503  /// Create DBG_VALUE insts for inlocs that have been propagated but
504  /// had their instruction creation deferred.
505  void flushPendingLocs(VarLocInMBB &PendingInLocs, VarLocMap &VarLocIDs);
506 
507  bool ExtendRanges(MachineFunction &MF);
508 
509 public:
510  static char ID;
511 
512  /// Default construct and initialize the pass.
513  LiveDebugValues();
514 
515  /// Tell the pass manager which passes we depend on and what
516  /// information we preserve.
517  void getAnalysisUsage(AnalysisUsage &AU) const override;
518 
519  MachineFunctionProperties getRequiredProperties() const override {
522  }
523 
524  /// Print to ostream with a message.
525  void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V,
526  const VarLocMap &VarLocIDs, const char *msg,
527  raw_ostream &Out) const;
528 
529  /// Calculate the liveness information for the given machine function.
530  bool runOnMachineFunction(MachineFunction &MF) override;
531 };
532 
533 } // end anonymous namespace
534 
535 namespace llvm {
536 
537 template <> struct DenseMapInfo<LiveDebugValues::DebugVariable> {
538  using DV = LiveDebugValues::DebugVariable;
541 
542  // Empty key: no key should be generated that has no DILocalVariable.
543  static inline DV getEmptyKey() {
544  return DV(nullptr, OptFragmentInfo(), nullptr);
545  }
546 
547  // Difference in tombstone is that the Optional is meaningful
548  static inline DV getTombstoneKey() {
549  return DV(nullptr, OptFragmentInfo({0, 0}), nullptr);
550  }
551 
552  static unsigned getHashValue(const DV &D) {
553  unsigned HV = 0;
554  const OptFragmentInfo &Fragment = D.getFragment();
555  if (Fragment)
557 
558  return hash_combine(D.getVar(), HV, D.getInlinedAt());
559  }
560 
561  static bool isEqual(const DV &A, const DV &B) { return A == B; }
562 };
563 
564 } // namespace llvm
565 
566 //===----------------------------------------------------------------------===//
567 // Implementation
568 //===----------------------------------------------------------------------===//
569 
571  LiveDebugValues::DebugVariable::DefaultFragment = {
573  std::numeric_limits<uint64_t>::min()};
574 
575 char LiveDebugValues::ID = 0;
576 
578 
579 INITIALIZE_PASS(LiveDebugValues, DEBUG_TYPE, "Live DEBUG_VALUE analysis",
580  false, false)
581 
582 /// Default construct and initialize the pass.
583 LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
585 }
586 
587 /// Tell the pass manager which passes we depend on and what information we
588 /// preserve.
589 void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const {
590  AU.setPreservesCFG();
592 }
593 
594 /// Erase a variable from the set of open ranges, and additionally erase any
595 /// fragments that may overlap it.
596 void LiveDebugValues::OpenRangesSet::erase(DebugVariable Var) {
597  // Erasure helper.
598  auto DoErase = [this](DebugVariable VarToErase) {
599  auto It = Vars.find(VarToErase);
600  if (It != Vars.end()) {
601  unsigned ID = It->second;
602  VarLocs.reset(ID);
603  Vars.erase(It);
604  }
605  };
606 
607  // Erase the variable/fragment that ends here.
608  DoErase(Var);
609 
610  // Extract the fragment. Interpret an empty fragment as one that covers all
611  // possible bits.
612  FragmentInfo ThisFragment = Var.getFragmentDefault();
613 
614  // There may be fragments that overlap the designated fragment. Look them up
615  // in the pre-computed overlap map, and erase them too.
616  auto MapIt = OverlappingFragments.find({Var.getVar(), ThisFragment});
617  if (MapIt != OverlappingFragments.end()) {
618  for (auto Fragment : MapIt->second) {
619  LiveDebugValues::OptFragmentInfo FragmentHolder;
620  if (!DebugVariable::isFragmentDefault(Fragment))
621  FragmentHolder = LiveDebugValues::OptFragmentInfo(Fragment);
622  DoErase({Var.getVar(), FragmentHolder, Var.getInlinedAt()});
623  }
624  }
625 }
626 
627 //===----------------------------------------------------------------------===//
628 // Debug Range Extension Implementation
629 //===----------------------------------------------------------------------===//
630 
631 #ifndef NDEBUG
632 void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF,
633  const VarLocInMBB &V,
634  const VarLocMap &VarLocIDs,
635  const char *msg,
636  raw_ostream &Out) const {
637  Out << '\n' << msg << '\n';
638  for (const MachineBasicBlock &BB : MF) {
639  const VarLocSet &L = V.lookup(&BB);
640  if (L.empty())
641  continue;
642  Out << "MBB: " << BB.getNumber() << ":\n";
643  for (unsigned VLL : L) {
644  const VarLoc &VL = VarLocIDs[VLL];
645  Out << " Var: " << VL.Var.getVar()->getName();
646  Out << " MI: ";
647  VL.dump(TRI, Out);
648  }
649  }
650  Out << "\n";
651 }
652 #endif
653 
654 LiveDebugValues::VarLoc::SpillLoc
655 LiveDebugValues::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
656  assert(MI.hasOneMemOperand() &&
657  "Spill instruction does not have exactly one memory operand?");
658  auto MMOI = MI.memoperands_begin();
659  const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
661  "Inconsistent memory operand in spill instruction");
662  int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
663  const MachineBasicBlock *MBB = MI.getParent();
664  unsigned Reg;
665  int Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg);
666  return {Reg, Offset};
667 }
668 
669 /// End all previous ranges related to @MI and start a new range from @MI
670 /// if it is a DBG_VALUE instr.
671 void LiveDebugValues::transferDebugValue(const MachineInstr &MI,
672  OpenRangesSet &OpenRanges,
673  VarLocMap &VarLocIDs) {
674  if (!MI.isDebugValue())
675  return;
676  const DILocalVariable *Var = MI.getDebugVariable();
677  const DIExpression *Expr = MI.getDebugExpression();
678  const DILocation *DebugLoc = MI.getDebugLoc();
679  const DILocation *InlinedAt = DebugLoc->getInlinedAt();
680  assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
681  "Expected inlined-at fields to agree");
682 
683  // End all previous ranges of Var.
684  DebugVariable V(Var, Expr, InlinedAt);
685  OpenRanges.erase(V);
686 
687  // Add the VarLoc to OpenRanges from this DBG_VALUE.
688  unsigned ID;
689  if (isDbgValueDescribedByReg(MI) || MI.getOperand(0).isImm() ||
690  MI.getOperand(0).isFPImm() || MI.getOperand(0).isCImm()) {
691  // Use normal VarLoc constructor for registers and immediates.
692  VarLoc VL(MI, LS);
693  ID = VarLocIDs.insert(VL);
694  OpenRanges.insert(ID, VL.Var);
695  } else if (MI.hasOneMemOperand()) {
696  llvm_unreachable("DBG_VALUE with mem operand encountered after regalloc?");
697  } else {
698  // This must be an undefined location. We should leave OpenRanges closed.
699  assert(MI.getOperand(0).isReg() && MI.getOperand(0).getReg() == 0 &&
700  "Unexpected non-undef DBG_VALUE encountered");
701  }
702 }
703 
704 void LiveDebugValues::emitEntryValues(MachineInstr &MI,
705  OpenRangesSet &OpenRanges,
706  VarLocMap &VarLocIDs,
707  TransferMap &Transfers,
708  DebugParamMap &DebugEntryVals,
709  SparseBitVector<> &KillSet) {
710  for (unsigned ID : KillSet) {
711  if (!VarLocIDs[ID].Var.getVar()->isParameter())
712  continue;
713 
714  const MachineInstr *CurrDebugInstr = &VarLocIDs[ID].MI;
715 
716  // If parameter's DBG_VALUE is not in the map that means we can't
717  // generate parameter's entry value.
718  if (!DebugEntryVals.count(CurrDebugInstr->getDebugVariable()))
719  continue;
720 
721  auto ParamDebugInstr = DebugEntryVals[CurrDebugInstr->getDebugVariable()];
723  ParamDebugInstr->getDebugExpression(), DIExpression::EntryValue);
724 
725  VarLoc EntryLoc = VarLoc::CreateEntryLoc(*ParamDebugInstr, LS, NewExpr);
726 
727  unsigned EntryValLocID = VarLocIDs.insert(EntryLoc);
728  Transfers.push_back({&MI, EntryValLocID});
729  OpenRanges.insert(EntryValLocID, EntryLoc.Var);
730  }
731 }
732 
733 /// Create new TransferDebugPair and insert it in \p Transfers. The VarLoc
734 /// with \p OldVarID should be deleted form \p OpenRanges and replaced with
735 /// new VarLoc. If \p NewReg is different than default zero value then the
736 /// new location will be register location created by the copy like instruction,
737 /// otherwise it is variable's location on the stack.
738 void LiveDebugValues::insertTransferDebugPair(
739  MachineInstr &MI, OpenRangesSet &OpenRanges, TransferMap &Transfers,
740  VarLocMap &VarLocIDs, unsigned OldVarID, TransferKind Kind,
741  unsigned NewReg) {
742  const MachineInstr *DebugInstr = &VarLocIDs[OldVarID].MI;
743 
744  auto ProcessVarLoc = [&MI, &OpenRanges, &Transfers, &DebugInstr,
745  &VarLocIDs](VarLoc &VL) {
746  unsigned LocId = VarLocIDs.insert(VL);
747 
748  // Close this variable's previous location range.
749  DebugVariable V(*DebugInstr);
750  OpenRanges.erase(V);
751 
752  // Record the new location as an open range, and a postponed transfer
753  // inserting a DBG_VALUE for this location.
754  OpenRanges.insert(LocId, VL.Var);
755  TransferDebugPair MIP = {&MI, LocId};
756  Transfers.push_back(MIP);
757  };
758 
759  // End all previous ranges of Var.
760  OpenRanges.erase(VarLocIDs[OldVarID].Var);
761  switch (Kind) {
762  case TransferKind::TransferCopy: {
763  assert(NewReg &&
764  "No register supplied when handling a copy of a debug value");
765  // Create a DBG_VALUE instruction to describe the Var in its new
766  // register location.
767  VarLoc VL = VarLoc::CreateCopyLoc(*DebugInstr, LS, NewReg);
768  ProcessVarLoc(VL);
769  LLVM_DEBUG({
770  dbgs() << "Creating VarLoc for register copy:";
771  VL.dump(TRI);
772  });
773  return;
774  }
775  case TransferKind::TransferSpill: {
776  // Create a DBG_VALUE instruction to describe the Var in its spilled
777  // location.
778  VarLoc::SpillLoc SpillLocation = extractSpillBaseRegAndOffset(MI);
779  VarLoc VL = VarLoc::CreateSpillLoc(*DebugInstr, SpillLocation.SpillBase,
780  SpillLocation.SpillOffset, LS);
781  ProcessVarLoc(VL);
782  LLVM_DEBUG({
783  dbgs() << "Creating VarLoc for spill:";
784  VL.dump(TRI);
785  });
786  return;
787  }
788  case TransferKind::TransferRestore: {
789  assert(NewReg &&
790  "No register supplied when handling a restore of a debug value");
791  MachineFunction *MF = MI.getMF();
792  DIBuilder DIB(*const_cast<Function &>(MF->getFunction()).getParent());
793  // DebugInstr refers to the pre-spill location, therefore we can reuse
794  // its expression.
795  VarLoc VL = VarLoc::CreateCopyLoc(*DebugInstr, LS, NewReg);
796  ProcessVarLoc(VL);
797  LLVM_DEBUG({
798  dbgs() << "Creating VarLoc for restore:";
799  VL.dump(TRI);
800  });
801  return;
802  }
803  }
804  llvm_unreachable("Invalid transfer kind");
805 }
806 
807 /// A definition of a register may mark the end of a range.
808 void LiveDebugValues::transferRegisterDef(
809  MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs,
810  TransferMap &Transfers, DebugParamMap &DebugEntryVals) {
811  MachineFunction *MF = MI.getMF();
812  const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
813  unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
814  SparseBitVector<> KillSet;
815  for (const MachineOperand &MO : MI.operands()) {
816  // Determine whether the operand is a register def. Assume that call
817  // instructions never clobber SP, because some backends (e.g., AArch64)
818  // never list SP in the regmask.
819  if (MO.isReg() && MO.isDef() && MO.getReg() &&
820  Register::isPhysicalRegister(MO.getReg()) &&
821  !(MI.isCall() && MO.getReg() == SP)) {
822  // Remove ranges of all aliased registers.
823  for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
824  for (unsigned ID : OpenRanges.getVarLocs())
825  if (VarLocIDs[ID].isDescribedByReg() == *RAI)
826  KillSet.set(ID);
827  } else if (MO.isRegMask()) {
828  // Remove ranges of all clobbered registers. Register masks don't usually
829  // list SP as preserved. While the debug info may be off for an
830  // instruction or two around callee-cleanup calls, transferring the
831  // DEBUG_VALUE across the call is still a better user experience.
832  for (unsigned ID : OpenRanges.getVarLocs()) {
833  unsigned Reg = VarLocIDs[ID].isDescribedByReg();
834  if (Reg && Reg != SP && MO.clobbersPhysReg(Reg))
835  KillSet.set(ID);
836  }
837  }
838  }
839  OpenRanges.erase(KillSet, VarLocIDs);
840 
841  if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) {
842  auto &TM = TPC->getTM<TargetMachine>();
843  if (TM.Options.EnableDebugEntryValues)
844  emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, DebugEntryVals,
845  KillSet);
846  }
847 }
848 
849 bool LiveDebugValues::isSpillInstruction(const MachineInstr &MI,
850  MachineFunction *MF) {
851  // TODO: Handle multiple stores folded into one.
852  if (!MI.hasOneMemOperand())
853  return false;
854 
855  if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII))
856  return false; // This is not a spill instruction, since no valid size was
857  // returned from either function.
858 
859  return true;
860 }
861 
862 bool LiveDebugValues::isLocationSpill(const MachineInstr &MI,
863  MachineFunction *MF, unsigned &Reg) {
864  if (!isSpillInstruction(MI, MF))
865  return false;
866 
867  auto isKilledReg = [&](const MachineOperand MO, unsigned &Reg) {
868  if (!MO.isReg() || !MO.isUse()) {
869  Reg = 0;
870  return false;
871  }
872  Reg = MO.getReg();
873  return MO.isKill();
874  };
875 
876  for (const MachineOperand &MO : MI.operands()) {
877  // In a spill instruction generated by the InlineSpiller the spilled
878  // register has its kill flag set.
879  if (isKilledReg(MO, Reg))
880  return true;
881  if (Reg != 0) {
882  // Check whether next instruction kills the spilled register.
883  // FIXME: Current solution does not cover search for killed register in
884  // bundles and instructions further down the chain.
885  auto NextI = std::next(MI.getIterator());
886  // Skip next instruction that points to basic block end iterator.
887  if (MI.getParent()->end() == NextI)
888  continue;
889  unsigned RegNext;
890  for (const MachineOperand &MONext : NextI->operands()) {
891  // Return true if we came across the register from the
892  // previous spill instruction that is killed in NextI.
893  if (isKilledReg(MONext, RegNext) && RegNext == Reg)
894  return true;
895  }
896  }
897  }
898  // Return false if we didn't find spilled register.
899  return false;
900 }
901 
903 LiveDebugValues::isRestoreInstruction(const MachineInstr &MI,
904  MachineFunction *MF, unsigned &Reg) {
905  if (!MI.hasOneMemOperand())
906  return None;
907 
908  // FIXME: Handle folded restore instructions with more than one memory
909  // operand.
910  if (MI.getRestoreSize(TII)) {
911  Reg = MI.getOperand(0).getReg();
912  return extractSpillBaseRegAndOffset(MI);
913  }
914  return None;
915 }
916 
917 /// A spilled register may indicate that we have to end the current range of
918 /// a variable and create a new one for the spill location.
919 /// A restored register may indicate the reverse situation.
920 /// We don't want to insert any instructions in process(), so we just create
921 /// the DBG_VALUE without inserting it and keep track of it in \p Transfers.
922 /// It will be inserted into the BB when we're done iterating over the
923 /// instructions.
924 void LiveDebugValues::transferSpillOrRestoreInst(MachineInstr &MI,
925  OpenRangesSet &OpenRanges,
926  VarLocMap &VarLocIDs,
927  TransferMap &Transfers) {
928  MachineFunction *MF = MI.getMF();
929  TransferKind TKind;
930  unsigned Reg;
932 
933  LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump(););
934 
935  // First, if there are any DBG_VALUEs pointing at a spill slot that is
936  // written to, then close the variable location. The value in memory
937  // will have changed.
938  VarLocSet KillSet;
939  if (isSpillInstruction(MI, MF)) {
940  Loc = extractSpillBaseRegAndOffset(MI);
941  for (unsigned ID : OpenRanges.getVarLocs()) {
942  const VarLoc &VL = VarLocIDs[ID];
943  if (VL.Kind == VarLoc::SpillLocKind && VL.Loc.SpillLocation == *Loc) {
944  // This location is overwritten by the current instruction -- terminate
945  // the open range, and insert an explicit DBG_VALUE $noreg.
946  //
947  // Doing this at a later stage would require re-interpreting all
948  // DBG_VALUes and DIExpressions to identify whether they point at
949  // memory, and then analysing all memory writes to see if they
950  // overwrite that memory, which is expensive.
951  //
952  // At this stage, we already know which DBG_VALUEs are for spills and
953  // where they are located; it's best to fix handle overwrites now.
954  KillSet.set(ID);
955  VarLoc UndefVL = VarLoc::CreateCopyLoc(VL.MI, LS, 0);
956  unsigned UndefLocID = VarLocIDs.insert(UndefVL);
957  Transfers.push_back({&MI, UndefLocID});
958  }
959  }
960  OpenRanges.erase(KillSet, VarLocIDs);
961  }
962 
963  // Try to recognise spill and restore instructions that may create a new
964  // variable location.
965  if (isLocationSpill(MI, MF, Reg)) {
966  TKind = TransferKind::TransferSpill;
967  LLVM_DEBUG(dbgs() << "Recognized as spill: "; MI.dump(););
968  LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI)
969  << "\n");
970  } else {
971  if (!(Loc = isRestoreInstruction(MI, MF, Reg)))
972  return;
973  TKind = TransferKind::TransferRestore;
974  LLVM_DEBUG(dbgs() << "Recognized as restore: "; MI.dump(););
975  LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI)
976  << "\n");
977  }
978  // Check if the register or spill location is the location of a debug value.
979  for (unsigned ID : OpenRanges.getVarLocs()) {
980  if (TKind == TransferKind::TransferSpill &&
981  VarLocIDs[ID].isDescribedByReg() == Reg) {
982  LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '('
983  << VarLocIDs[ID].Var.getVar()->getName() << ")\n");
984  } else if (TKind == TransferKind::TransferRestore &&
985  VarLocIDs[ID].Kind == VarLoc::SpillLocKind &&
986  VarLocIDs[ID].Loc.SpillLocation == *Loc) {
987  LLVM_DEBUG(dbgs() << "Restoring Register " << printReg(Reg, TRI) << '('
988  << VarLocIDs[ID].Var.getVar()->getName() << ")\n");
989  } else
990  continue;
991  insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID, TKind,
992  Reg);
993  return;
994  }
995 }
996 
997 /// If \p MI is a register copy instruction, that copies a previously tracked
998 /// value from one register to another register that is callee saved, we
999 /// create new DBG_VALUE instruction described with copy destination register.
1000 void LiveDebugValues::transferRegisterCopy(MachineInstr &MI,
1001  OpenRangesSet &OpenRanges,
1002  VarLocMap &VarLocIDs,
1003  TransferMap &Transfers) {
1004  const MachineOperand *SrcRegOp, *DestRegOp;
1005 
1006  if (!TII->isCopyInstr(MI, SrcRegOp, DestRegOp) || !SrcRegOp->isKill() ||
1007  !DestRegOp->isDef())
1008  return;
1009 
1010  auto isCalleSavedReg = [&](unsigned Reg) {
1011  for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
1012  if (CalleeSavedRegs.test(*RAI))
1013  return true;
1014  return false;
1015  };
1016 
1017  Register SrcReg = SrcRegOp->getReg();
1018  Register DestReg = DestRegOp->getReg();
1019 
1020  // We want to recognize instructions where destination register is callee
1021  // saved register. If register that could be clobbered by the call is
1022  // included, there would be a great chance that it is going to be clobbered
1023  // soon. It is more likely that previous register location, which is callee
1024  // saved, is going to stay unclobbered longer, even if it is killed.
1025  if (!isCalleSavedReg(DestReg))
1026  return;
1027 
1028  for (unsigned ID : OpenRanges.getVarLocs()) {
1029  if (VarLocIDs[ID].isDescribedByReg() == SrcReg) {
1030  insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID,
1031  TransferKind::TransferCopy, DestReg);
1032  return;
1033  }
1034  }
1035 }
1036 
1037 /// Terminate all open ranges at the end of the current basic block.
1038 bool LiveDebugValues::transferTerminator(MachineBasicBlock *CurMBB,
1039  OpenRangesSet &OpenRanges,
1040  VarLocInMBB &OutLocs,
1041  const VarLocMap &VarLocIDs) {
1042  bool Changed = false;
1043 
1044  LLVM_DEBUG(for (unsigned ID
1045  : OpenRanges.getVarLocs()) {
1046  // Copy OpenRanges to OutLocs, if not already present.
1047  dbgs() << "Add to OutLocs in MBB #" << CurMBB->getNumber() << ": ";
1048  VarLocIDs[ID].dump(TRI);
1049  });
1050  VarLocSet &VLS = OutLocs[CurMBB];
1051  Changed = VLS != OpenRanges.getVarLocs();
1052  // New OutLocs set may be different due to spill, restore or register
1053  // copy instruction processing.
1054  if (Changed)
1055  VLS = OpenRanges.getVarLocs();
1056  OpenRanges.clear();
1057  return Changed;
1058 }
1059 
1060 /// Accumulate a mapping between each DILocalVariable fragment and other
1061 /// fragments of that DILocalVariable which overlap. This reduces work during
1062 /// the data-flow stage from "Find any overlapping fragments" to "Check if the
1063 /// known-to-overlap fragments are present".
1064 /// \param MI A previously unprocessed DEBUG_VALUE instruction to analyze for
1065 /// fragment usage.
1066 /// \param SeenFragments Map from DILocalVariable to all fragments of that
1067 /// Variable which are known to exist.
1068 /// \param OverlappingFragments The overlap map being constructed, from one
1069 /// Var/Fragment pair to a vector of fragments known to overlap.
1070 void LiveDebugValues::accumulateFragmentMap(MachineInstr &MI,
1071  VarToFragments &SeenFragments,
1072  OverlapMap &OverlappingFragments) {
1073  DebugVariable MIVar(MI);
1074  FragmentInfo ThisFragment = MIVar.getFragmentDefault();
1075 
1076  // If this is the first sighting of this variable, then we are guaranteed
1077  // there are currently no overlapping fragments either. Initialize the set
1078  // of seen fragments, record no overlaps for the current one, and return.
1079  auto SeenIt = SeenFragments.find(MIVar.getVar());
1080  if (SeenIt == SeenFragments.end()) {
1081  SmallSet<FragmentInfo, 4> OneFragment;
1082  OneFragment.insert(ThisFragment);
1083  SeenFragments.insert({MIVar.getVar(), OneFragment});
1084 
1085  OverlappingFragments.insert({{MIVar.getVar(), ThisFragment}, {}});
1086  return;
1087  }
1088 
1089  // If this particular Variable/Fragment pair already exists in the overlap
1090  // map, it has already been accounted for.
1091  auto IsInOLapMap =
1092  OverlappingFragments.insert({{MIVar.getVar(), ThisFragment}, {}});
1093  if (!IsInOLapMap.second)
1094  return;
1095 
1096  auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;
1097  auto &AllSeenFragments = SeenIt->second;
1098 
1099  // Otherwise, examine all other seen fragments for this variable, with "this"
1100  // fragment being a previously unseen fragment. Record any pair of
1101  // overlapping fragments.
1102  for (auto &ASeenFragment : AllSeenFragments) {
1103  // Does this previously seen fragment overlap?
1104  if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) {
1105  // Yes: Mark the current fragment as being overlapped.
1106  ThisFragmentsOverlaps.push_back(ASeenFragment);
1107  // Mark the previously seen fragment as being overlapped by the current
1108  // one.
1109  auto ASeenFragmentsOverlaps =
1110  OverlappingFragments.find({MIVar.getVar(), ASeenFragment});
1111  assert(ASeenFragmentsOverlaps != OverlappingFragments.end() &&
1112  "Previously seen var fragment has no vector of overlaps");
1113  ASeenFragmentsOverlaps->second.push_back(ThisFragment);
1114  }
1115  }
1116 
1117  AllSeenFragments.insert(ThisFragment);
1118 }
1119 
1120 /// This routine creates OpenRanges and OutLocs.
1121 void LiveDebugValues::process(MachineInstr &MI, OpenRangesSet &OpenRanges,
1122  VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
1123  TransferMap &Transfers,
1124  DebugParamMap &DebugEntryVals,
1125  OverlapMap &OverlapFragments,
1126  VarToFragments &SeenFragments) {
1127  transferDebugValue(MI, OpenRanges, VarLocIDs);
1128  transferRegisterDef(MI, OpenRanges, VarLocIDs, Transfers,
1129  DebugEntryVals);
1130  transferRegisterCopy(MI, OpenRanges, VarLocIDs, Transfers);
1131  transferSpillOrRestoreInst(MI, OpenRanges, VarLocIDs, Transfers);
1132 }
1133 
1134 /// This routine joins the analysis results of all incoming edges in @MBB by
1135 /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
1136 /// source variable in all the predecessors of @MBB reside in the same location.
1138  MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
1139  const VarLocMap &VarLocIDs,
1142  VarLocInMBB &PendingInLocs) {
1143  LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
1144  bool Changed = false;
1145 
1146  VarLocSet InLocsT; // Temporary incoming locations.
1147 
1148  // For all predecessors of this MBB, find the set of VarLocs that
1149  // can be joined.
1150  int NumVisited = 0;
1151  for (auto p : MBB.predecessors()) {
1152  // Ignore backedges if we have not visited the predecessor yet. As the
1153  // predecessor hasn't yet had locations propagated into it, most locations
1154  // will not yet be valid, so treat them as all being uninitialized and
1155  // potentially valid. If a location guessed to be correct here is
1156  // invalidated later, we will remove it when we revisit this block.
1157  if (!Visited.count(p)) {
1158  LLVM_DEBUG(dbgs() << " ignoring unvisited pred MBB: " << p->getNumber()
1159  << "\n");
1160  continue;
1161  }
1162  auto OL = OutLocs.find(p);
1163  // Join is null in case of empty OutLocs from any of the pred.
1164  if (OL == OutLocs.end())
1165  return false;
1166 
1167  // Just copy over the Out locs to incoming locs for the first visited
1168  // predecessor, and for all other predecessors join the Out locs.
1169  if (!NumVisited)
1170  InLocsT = OL->second;
1171  else
1172  InLocsT &= OL->second;
1173 
1174  LLVM_DEBUG({
1175  if (!InLocsT.empty()) {
1176  for (auto ID : InLocsT)
1177  dbgs() << " gathered candidate incoming var: "
1178  << VarLocIDs[ID].Var.getVar()->getName() << "\n";
1179  }
1180  });
1181 
1182  NumVisited++;
1183  }
1184 
1185  // Filter out DBG_VALUES that are out of scope.
1186  VarLocSet KillSet;
1187  bool IsArtificial = ArtificialBlocks.count(&MBB);
1188  if (!IsArtificial) {
1189  for (auto ID : InLocsT) {
1190  if (!VarLocIDs[ID].dominates(MBB)) {
1191  KillSet.set(ID);
1192  LLVM_DEBUG({
1193  auto Name = VarLocIDs[ID].Var.getVar()->getName();
1194  dbgs() << " killing " << Name << ", it doesn't dominate MBB\n";
1195  });
1196  }
1197  }
1198  }
1199  InLocsT.intersectWithComplement(KillSet);
1200 
1201  // As we are processing blocks in reverse post-order we
1202  // should have processed at least one predecessor, unless it
1203  // is the entry block which has no predecessor.
1204  assert((NumVisited || MBB.pred_empty()) &&
1205  "Should have processed at least one predecessor");
1206 
1207  VarLocSet &ILS = InLocs[&MBB];
1208  VarLocSet &Pending = PendingInLocs[&MBB];
1209 
1210  // New locations will have DBG_VALUE insts inserted at the start of the
1211  // block, after location propagation has finished. Record the insertions
1212  // that we need to perform in the Pending set.
1213  VarLocSet Diff = InLocsT;
1214  Diff.intersectWithComplement(ILS);
1215  for (auto ID : Diff) {
1216  Pending.set(ID);
1217  ILS.set(ID);
1218  ++NumInserted;
1219  Changed = true;
1220  }
1221 
1222  // We may have lost locations by learning about a predecessor that either
1223  // loses or moves a variable. Find any locations in ILS that are not in the
1224  // new in-locations, and delete those.
1225  VarLocSet Removed = ILS;
1226  Removed.intersectWithComplement(InLocsT);
1227  for (auto ID : Removed) {
1228  Pending.reset(ID);
1229  ILS.reset(ID);
1230  ++NumRemoved;
1231  Changed = true;
1232  }
1233 
1234  return Changed;
1235 }
1236 
1237 void LiveDebugValues::flushPendingLocs(VarLocInMBB &PendingInLocs,
1238  VarLocMap &VarLocIDs) {
1239  // PendingInLocs records all locations propagated into blocks, which have
1240  // not had DBG_VALUE insts created. Go through and create those insts now.
1241  for (auto &Iter : PendingInLocs) {
1242  // Map is keyed on a constant pointer, unwrap it so we can insert insts.
1243  auto &MBB = const_cast<MachineBasicBlock &>(*Iter.first);
1244  VarLocSet &Pending = Iter.second;
1245 
1246  for (unsigned ID : Pending) {
1247  // The ID location is live-in to MBB -- work out what kind of machine
1248  // location it is and create a DBG_VALUE.
1249  const VarLoc &DiffIt = VarLocIDs[ID];
1250  MachineInstr *MI = DiffIt.BuildDbgValue(*MBB.getParent());
1251  MBB.insert(MBB.instr_begin(), MI);
1252 
1253  (void)MI;
1254  LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump(););
1255  }
1256  }
1257 }
1258 
1259 /// Calculate the liveness information for the given machine function and
1260 /// extend ranges across basic blocks.
1261 bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
1262  LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
1263 
1264  bool Changed = false;
1265  bool OLChanged = false;
1266  bool MBBJoined = false;
1267 
1268  VarLocMap VarLocIDs; // Map VarLoc<>unique ID for use in bitvectors.
1269  OverlapMap OverlapFragments; // Map of overlapping variable fragments
1270  OpenRangesSet OpenRanges(OverlapFragments);
1271  // Ranges that are open until end of bb.
1272  VarLocInMBB OutLocs; // Ranges that exist beyond bb.
1273  VarLocInMBB InLocs; // Ranges that are incoming after joining.
1274  TransferMap Transfers; // DBG_VALUEs associated with spills.
1275  VarLocInMBB PendingInLocs; // Ranges that are incoming after joining, but
1276  // that we have deferred creating DBG_VALUE insts
1277  // for immediately.
1278 
1279  VarToFragments SeenFragments;
1280 
1281  // Blocks which are artificial, i.e. blocks which exclusively contain
1282  // instructions without locations, or with line 0 locations.
1284 
1287  std::priority_queue<unsigned int, std::vector<unsigned int>,
1288  std::greater<unsigned int>>
1289  Worklist;
1290  std::priority_queue<unsigned int, std::vector<unsigned int>,
1291  std::greater<unsigned int>>
1292  Pending;
1293 
1294  // Besides parameter's modification, check whether a DBG_VALUE is inlined
1295  // in order to deduce whether the variable that it tracks comes from
1296  // a different function. If that is the case we can't track its entry value.
1297  auto IsUnmodifiedFuncParam = [&](const MachineInstr &MI) {
1298  auto *DIVar = MI.getDebugVariable();
1299  return DIVar->isParameter() && DIVar->isNotModified() &&
1300  !MI.getDebugLoc()->getInlinedAt();
1301  };
1302 
1303  const TargetLowering *TLI = MF.getSubtarget().getTargetLowering();
1304  unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
1305  Register FP = TRI->getFrameRegister(MF);
1306  auto IsRegOtherThanSPAndFP = [&](const MachineOperand &Op) -> bool {
1307  return Op.isReg() && Op.getReg() != SP && Op.getReg() != FP;
1308  };
1309 
1310  // Working set of currently collected debug variables mapped to DBG_VALUEs
1311  // representing candidates for production of debug entry values.
1312  DebugParamMap DebugEntryVals;
1313 
1314  MachineBasicBlock &First_MBB = *(MF.begin());
1315  // Only in the case of entry MBB collect DBG_VALUEs representing
1316  // function parameters in order to generate debug entry values for them.
1317  // Currently, we generate debug entry values only for parameters that are
1318  // unmodified throughout the function and located in a register.
1319  // TODO: Add support for parameters that are described as fragments.
1320  // TODO: Add support for modified arguments that can be expressed
1321  // by using its entry value.
1322  // TODO: Add support for local variables that are expressed in terms of
1323  // parameters entry values.
1324  for (auto &MI : First_MBB)
1325  if (MI.isDebugValue() && IsUnmodifiedFuncParam(MI) &&
1326  !MI.isIndirectDebugValue() && IsRegOtherThanSPAndFP(MI.getOperand(0)) &&
1327  !DebugEntryVals.count(MI.getDebugVariable()) &&
1328  !MI.getDebugExpression()->isFragment())
1329  DebugEntryVals[MI.getDebugVariable()] = &MI;
1330 
1331  // Initialize per-block structures and scan for fragment overlaps.
1332  for (auto &MBB : MF) {
1333  PendingInLocs[&MBB] = VarLocSet();
1334 
1335  for (auto &MI : MBB) {
1336  if (MI.isDebugValue())
1337  accumulateFragmentMap(MI, SeenFragments, OverlapFragments);
1338  }
1339  }
1340 
1341  auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
1342  if (const DebugLoc &DL = MI.getDebugLoc())
1343  return DL.getLine() != 0;
1344  return false;
1345  };
1346  for (auto &MBB : MF)
1347  if (none_of(MBB.instrs(), hasNonArtificialLocation))
1348  ArtificialBlocks.insert(&MBB);
1349 
1350  LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
1351  "OutLocs after initialization", dbgs()));
1352 
1354  unsigned int RPONumber = 0;
1355  for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
1356  OrderToBB[RPONumber] = *RI;
1357  BBToOrder[*RI] = RPONumber;
1358  Worklist.push(RPONumber);
1359  ++RPONumber;
1360  }
1361  // This is a standard "union of predecessor outs" dataflow problem.
1362  // To solve it, we perform join() and process() using the two worklist method
1363  // until the ranges converge.
1364  // Ranges have converged when both worklists are empty.
1366  while (!Worklist.empty() || !Pending.empty()) {
1367  // We track what is on the pending worklist to avoid inserting the same
1368  // thing twice. We could avoid this with a custom priority queue, but this
1369  // is probably not worth it.
1371  LLVM_DEBUG(dbgs() << "Processing Worklist\n");
1372  while (!Worklist.empty()) {
1373  MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
1374  Worklist.pop();
1375  MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs, Visited,
1376  ArtificialBlocks, PendingInLocs);
1377  MBBJoined |= Visited.insert(MBB).second;
1378  if (MBBJoined) {
1379  MBBJoined = false;
1380  Changed = true;
1381  // Now that we have started to extend ranges across BBs we need to
1382  // examine spill instructions to see whether they spill registers that
1383  // correspond to user variables.
1384  // First load any pending inlocs.
1385  OpenRanges.insertFromLocSet(PendingInLocs[MBB], VarLocIDs);
1386  for (auto &MI : *MBB)
1387  process(MI, OpenRanges, OutLocs, VarLocIDs, Transfers,
1388  DebugEntryVals, OverlapFragments, SeenFragments);
1389  OLChanged |= transferTerminator(MBB, OpenRanges, OutLocs, VarLocIDs);
1390 
1391  LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
1392  "OutLocs after propagating", dbgs()));
1393  LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
1394  "InLocs after propagating", dbgs()));
1395 
1396  if (OLChanged) {
1397  OLChanged = false;
1398  for (auto s : MBB->successors())
1399  if (OnPending.insert(s).second) {
1400  Pending.push(BBToOrder[s]);
1401  }
1402  }
1403  }
1404  }
1405  Worklist.swap(Pending);
1406  // At this point, pending must be empty, since it was just the empty
1407  // worklist
1408  assert(Pending.empty() && "Pending should be empty");
1409  }
1410 
1411  // Add any DBG_VALUE instructions created by location transfers.
1412  for (auto &TR : Transfers) {
1413  MachineBasicBlock *MBB = TR.TransferInst->getParent();
1414  const VarLoc &VL = VarLocIDs[TR.LocationID];
1415  MachineInstr *MI = VL.BuildDbgValue(MF);
1416  MBB->insertAfterBundle(TR.TransferInst->getIterator(), MI);
1417  }
1418  Transfers.clear();
1419 
1420  // Deferred inlocs will not have had any DBG_VALUE insts created; do
1421  // that now.
1422  flushPendingLocs(PendingInLocs, VarLocIDs);
1423 
1424  LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs()));
1425  LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs()));
1426  return Changed;
1427 }
1428 
1429 bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
1430  if (!MF.getFunction().getSubprogram())
1431  // LiveDebugValues will already have removed all DBG_VALUEs.
1432  return false;
1433 
1434  // Skip functions from NoDebug compilation units.
1435  if (MF.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
1437  return false;
1438 
1439  TRI = MF.getSubtarget().getRegisterInfo();
1440  TII = MF.getSubtarget().getInstrInfo();
1441  TFI = MF.getSubtarget().getFrameLowering();
1442  TFI->determineCalleeSaves(MF, CalleeSavedRegs,
1443  std::make_unique<RegScavenger>().get());
1444  LS.initialize(MF);
1445 
1446  bool Changed = ExtendRanges(MF);
1447  return Changed;
1448 }
static bool isConstant(const MachineInstr &MI)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
instr_iterator instr_begin()
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:656
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, otherwise insert MI immediately after I.
static bool fragmentsOverlap(const FragmentInfo &A, const FragmentInfo &B)
Check if fragments overlap between a pair of FragmentInfos.
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
void set(unsigned Idx)
bool dominates(const DILocation *DL, MachineBasicBlock *MBB)
dominates - Return true if DebugLoc&#39;s lexical scope dominates at least one machine instruction&#39;s lexi...
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:384
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:63
unsigned Reg
virtual const TargetLowering * getTargetLowering() const
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:953
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
A debug info location.
Definition: DebugLoc.h:33
F(f)
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.
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:476
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
static Register isDescribedByReg(const MachineInstr &MI)
virtual void determineCalleeSaves(MachineFunction &MF, BitVector &SavedRegs, RegScavenger *RS=nullptr) const
This method determines which of the registers reported by TargetRegisterInfo::getCalleeSavedRegs() sh...
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 ...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
RegisterKind
const ConstantFP * getFPImm() const
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:413
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:1179
static Register isDbgValueDescribedByReg(const MachineInstr &MI)
std::string join(IteratorT Begin, IteratorT End, StringRef Separator)
Joins the strings in the range [Begin, End), adding Separator between the elements.
Definition: StringExtras.h:370
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:407
Holds the characteristics of one fragment of a larger variable.
Optional< unsigned > getRestoreSize(const TargetInstrInfo *TII) const
Return a valid size if the instruction is a restore instruction.
INITIALIZE_PASS(LiveDebugValues, DEBUG_TYPE, "Live DEBUG_VALUE analysis", false, false) LiveDebugValues
Default construct and initialize the pass.
static Optional< FragmentInfo > getFragmentInfo(expr_op_iterator Start, expr_op_iterator End)
Retrieve the details of this fragment expression.
bool isFPImm() const
isFPImm - Tests if this is a MO_FPImmediate operand.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
virtual const TargetInstrInfo * getInstrInfo() const
Debug location.
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
void initializeLiveDebugValuesPass(PassRegistry &)
TargetInstrInfo - Interface to description of machine instruction set.
Optional< unsigned > getSpillSize(const TargetInstrInfo *TII) const
Return a valid size if the instruction is a spill instruction.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
#define DEBUG_TYPE
This file declares the machine register scavenger class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1522
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:263
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:370
bool isCImm() const
isCImm - Test if this is a MO_CImmediate operand.
bool isValidLocationForIntrinsic(const DILocation *DL) const
Check that a location is valid for this variable.
MCRegAliasIterator enumerates all registers aliasing Reg.
Represent the analysis usage information of a pass.
bool hasOneMemOperand() const
Return true if this instruction has exactly one MachineMemOperand.
Definition: MachineInstr.h:566
char & LiveDebugValuesID
LiveDebugValues pass.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
self_iterator getIterator()
Definition: ilist_node.h:81
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:180
iterator_range< pred_iterator > predecessors()
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Optional< unsigned > getFoldedSpillSize(const TargetInstrInfo *TII) const
Return a valid size if the instruction is a folded spill instruction.
void getMachineBasicBlocks(const DILocation *DL, SmallPtrSetImpl< const MachineBasicBlock *> &MBBs)
getMachineBasicBlocks - Populate given set using machine basic blocks which have machine instructions...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
const DIExpression * getDebugExpression() const
Return the complex address expression referenced by this DBG_VALUE instruction.
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:197
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:390
mmo_iterator memoperands_begin() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:551
bool isDebugValue() const
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Module.h This file contains the declarations for the Module class.
Information about stack frame layout on the target.
Promote Memory to Register
Definition: Mem2Reg.cpp:109
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
int64_t getImm() const
DWARF expression.
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:599
Special value supplied for machine level alias analysis.
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:225
static bool isEqual(const DV &A, const DV &B)
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:255
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:63
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
LexicalScopes - This class provides interface to collect and use lexical scoping information from mac...
virtual const TargetFrameLowering * getFrameLowering() const
bool isDebugEntryValue() const
A DBG_VALUE is an entry value iff its debug expression contains the DW_OP_LLVM_entry_value operation...
bool isReg() const
isReg - Tests if this is a MO_Register operand.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:343
unsigned getStackPointerRegisterToSaveRestore() const
If a physical register, this specifies the register that llvm.savestack/llvm.restorestack should save...
const DILocalVariable * getDebugVariable() const
Return the debug variable referenced by this DBG_VALUE instruction.
static const Function * getParent(const Value *V)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:65
IRTranslator LLVM IR MI
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1975
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:415
bool isFragment() const
Return whether this is a piece of an aggregate variable.
const ConstantInt * getCImm() const
bool isIndirectDebugValue() const
A DBG_VALUE is indirect iff the first operand is a register and the second operand is an immediate...
UniqueVector - This class produces a sequential ID number (base 1) for each unique entry that is adde...
Definition: UniqueVector.h:24
Properties which a MachineFunction may have at a given point in time.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
This file describes how to lower LLVM code to machine code.