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  VarLocKind K = InvalidKind)
224  : Var(MI), Expr(MI.getDebugExpression()), MI(MI),
225  UVS(MI.getDebugLoc(), LS) {
226  static_assert((sizeof(Loc) == sizeof(uint64_t)),
227  "hash does not cover all members of Loc");
228  assert(MI.isDebugValue() && "not a DBG_VALUE");
229  assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
230  if (int RegNo = isDbgValueDescribedByReg(MI)) {
231  Kind = MI.isDebugEntryValue() ? EntryValueKind : RegisterKind;
232  Loc.RegNo = RegNo;
233  } else if (MI.getOperand(0).isImm()) {
234  Kind = ImmediateKind;
235  Loc.Immediate = MI.getOperand(0).getImm();
236  } else if (MI.getOperand(0).isFPImm()) {
237  Kind = ImmediateKind;
238  Loc.FPImm = MI.getOperand(0).getFPImm();
239  } else if (MI.getOperand(0).isCImm()) {
240  Kind = ImmediateKind;
241  Loc.CImm = MI.getOperand(0).getCImm();
242  }
243  assert((Kind != ImmediateKind || !MI.isDebugEntryValue()) &&
244  "entry values must be register locations");
245  }
246 
247  /// The constructor for spill locations.
248  VarLoc(const MachineInstr &MI, unsigned SpillBase, int SpillOffset,
249  LexicalScopes &LS, const MachineInstr &OrigMI)
250  : Var(MI), Expr(MI.getDebugExpression()), MI(OrigMI),
251  UVS(MI.getDebugLoc(), LS) {
252  assert(MI.isDebugValue() && "not a DBG_VALUE");
253  assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
254  Kind = SpillLocKind;
255  Loc.SpillLocation = {SpillBase, SpillOffset};
256  }
257 
258  // Is the Loc field a constant or constant object?
259  bool isConstant() const { return Kind == ImmediateKind; }
260 
261  /// If this variable is described by a register, return it,
262  /// otherwise return 0.
263  unsigned isDescribedByReg() const {
264  if (Kind == RegisterKind)
265  return Loc.RegNo;
266  return 0;
267  }
268 
269  /// Determine whether the lexical scope of this value's debug location
270  /// dominates MBB.
271  bool dominates(MachineBasicBlock &MBB) const { return UVS.dominates(&MBB); }
272 
273 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
274  LLVM_DUMP_METHOD void dump() const { MI.dump(); }
275 #endif
276 
277  bool operator==(const VarLoc &Other) const {
278  return Kind == Other.Kind && Var == Other.Var &&
279  Loc.Hash == Other.Loc.Hash && Expr == Other.Expr;
280  }
281 
282  /// This operator guarantees that VarLocs are sorted by Variable first.
283  bool operator<(const VarLoc &Other) const {
284  return std::tie(Var, Kind, Loc.Hash, Expr) <
285  std::tie(Other.Var, Other.Kind, Other.Loc.Hash, Other.Expr);
286  }
287  };
288 
290  using VarLocMap = UniqueVector<VarLoc>;
291  using VarLocSet = SparseBitVector<>;
293  struct TransferDebugPair {
294  MachineInstr *TransferInst;
295  MachineInstr *DebugInst;
296  };
297  using TransferMap = SmallVector<TransferDebugPair, 4>;
298 
299  // Types for recording sets of variable fragments that overlap. For a given
300  // local variable, we record all other fragments of that variable that could
301  // overlap it, to reduce search time.
302  using FragmentOfVar =
303  std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
304  using OverlapMap =
306 
307  // Helper while building OverlapMap, a map of all fragments seen for a given
308  // DILocalVariable.
309  using VarToFragments =
311 
312  /// This holds the working set of currently open ranges. For fast
313  /// access, this is done both as a set of VarLocIDs, and a map of
314  /// DebugVariable to recent VarLocID. Note that a DBG_VALUE ends all
315  /// previous open ranges for the same variable.
316  class OpenRangesSet {
317  VarLocSet VarLocs;
319  OverlapMap &OverlappingFragments;
320 
321  public:
322  OpenRangesSet(OverlapMap &_OLapMap) : OverlappingFragments(_OLapMap) {}
323 
324  const VarLocSet &getVarLocs() const { return VarLocs; }
325 
326  /// Terminate all open ranges for Var by removing it from the set.
327  void erase(DebugVariable Var);
328 
329  /// Terminate all open ranges listed in \c KillSet by removing
330  /// them from the set.
331  void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs) {
332  VarLocs.intersectWithComplement(KillSet);
333  for (unsigned ID : KillSet)
334  Vars.erase(VarLocIDs[ID].Var);
335  }
336 
337  /// Insert a new range into the set.
338  void insert(unsigned VarLocID, DebugVariable Var) {
339  VarLocs.set(VarLocID);
340  Vars.insert({Var, VarLocID});
341  }
342 
343  /// Insert a set of ranges.
344  void insertFromLocSet(const VarLocSet &ToLoad, const VarLocMap &Map) {
345  for (unsigned Id : ToLoad) {
346  const VarLoc &Var = Map[Id];
347  insert(Id, Var.Var);
348  }
349  }
350 
351  /// Empty the set.
352  void clear() {
353  VarLocs.clear();
354  Vars.clear();
355  }
356 
357  /// Return whether the set is empty or not.
358  bool empty() const {
359  assert(Vars.empty() == VarLocs.empty() && "open ranges are inconsistent");
360  return VarLocs.empty();
361  }
362  };
363 
364  /// Tests whether this instruction is a spill to a stack location.
365  bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF);
366 
367  /// Decide if @MI is a spill instruction and return true if it is. We use 2
368  /// criteria to make this decision:
369  /// - Is this instruction a store to a spill slot?
370  /// - Is there a register operand that is both used and killed?
371  /// TODO: Store optimization can fold spills into other stores (including
372  /// other spills). We do not handle this yet (more than one memory operand).
373  bool isLocationSpill(const MachineInstr &MI, MachineFunction *MF,
374  unsigned &Reg);
375 
376  /// If a given instruction is identified as a spill, return the spill location
377  /// and set \p Reg to the spilled register.
378  Optional<VarLoc::SpillLoc> isRestoreInstruction(const MachineInstr &MI,
379  MachineFunction *MF,
380  unsigned &Reg);
381  /// Given a spill instruction, extract the register and offset used to
382  /// address the spill location in a target independent way.
383  VarLoc::SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI);
384  void insertTransferDebugPair(MachineInstr &MI, OpenRangesSet &OpenRanges,
385  TransferMap &Transfers, VarLocMap &VarLocIDs,
386  unsigned OldVarID, TransferKind Kind,
387  unsigned NewReg = 0);
388 
389  void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
390  VarLocMap &VarLocIDs);
391  void transferSpillOrRestoreInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
392  VarLocMap &VarLocIDs, TransferMap &Transfers);
393  void emitEntryValues(MachineInstr &MI, OpenRangesSet &OpenRanges,
394  VarLocMap &VarLocIDs, TransferMap &Transfers,
395  DebugParamMap &DebugEntryVals,
396  SparseBitVector<> &KillSet);
397  void transferRegisterCopy(MachineInstr &MI, OpenRangesSet &OpenRanges,
398  VarLocMap &VarLocIDs, TransferMap &Transfers);
399  void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
400  VarLocMap &VarLocIDs, TransferMap &Transfers,
401  DebugParamMap &DebugEntryVals);
402  bool transferTerminator(MachineBasicBlock *MBB, OpenRangesSet &OpenRanges,
403  VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs);
404 
405  void process(MachineInstr &MI, OpenRangesSet &OpenRanges,
406  VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
407  TransferMap &Transfers, DebugParamMap &DebugEntryVals,
408  OverlapMap &OverlapFragments,
409  VarToFragments &SeenFragments);
410 
411  void accumulateFragmentMap(MachineInstr &MI, VarToFragments &SeenFragments,
412  OverlapMap &OLapMap);
413 
414  bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
415  const VarLocMap &VarLocIDs,
418  VarLocInMBB &PendingInLocs);
419 
420  /// Create DBG_VALUE insts for inlocs that have been propagated but
421  /// had their instruction creation deferred.
422  void flushPendingLocs(VarLocInMBB &PendingInLocs, VarLocMap &VarLocIDs);
423 
424  bool ExtendRanges(MachineFunction &MF);
425 
426 public:
427  static char ID;
428 
429  /// Default construct and initialize the pass.
430  LiveDebugValues();
431 
432  /// Tell the pass manager which passes we depend on and what
433  /// information we preserve.
434  void getAnalysisUsage(AnalysisUsage &AU) const override;
435 
436  MachineFunctionProperties getRequiredProperties() const override {
439  }
440 
441  /// Print to ostream with a message.
442  void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V,
443  const VarLocMap &VarLocIDs, const char *msg,
444  raw_ostream &Out) const;
445 
446  /// Calculate the liveness information for the given machine function.
447  bool runOnMachineFunction(MachineFunction &MF) override;
448 };
449 
450 } // end anonymous namespace
451 
452 namespace llvm {
453 
454 template <> struct DenseMapInfo<LiveDebugValues::DebugVariable> {
455  using DV = LiveDebugValues::DebugVariable;
458 
459  // Empty key: no key should be generated that has no DILocalVariable.
460  static inline DV getEmptyKey() {
461  return DV(nullptr, OptFragmentInfo(), nullptr);
462  }
463 
464  // Difference in tombstone is that the Optional is meaningful
465  static inline DV getTombstoneKey() {
466  return DV(nullptr, OptFragmentInfo({0, 0}), nullptr);
467  }
468 
469  static unsigned getHashValue(const DV &D) {
470  unsigned HV = 0;
471  const OptFragmentInfo &Fragment = D.getFragment();
472  if (Fragment)
474 
475  return hash_combine(D.getVar(), HV, D.getInlinedAt());
476  }
477 
478  static bool isEqual(const DV &A, const DV &B) { return A == B; }
479 };
480 
481 } // namespace llvm
482 
483 //===----------------------------------------------------------------------===//
484 // Implementation
485 //===----------------------------------------------------------------------===//
486 
488  LiveDebugValues::DebugVariable::DefaultFragment = {
490  std::numeric_limits<uint64_t>::min()};
491 
492 char LiveDebugValues::ID = 0;
493 
495 
496 INITIALIZE_PASS(LiveDebugValues, DEBUG_TYPE, "Live DEBUG_VALUE analysis",
497  false, false)
498 
499 /// Default construct and initialize the pass.
500 LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
502 }
503 
504 /// Tell the pass manager which passes we depend on and what information we
505 /// preserve.
506 void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const {
507  AU.setPreservesCFG();
509 }
510 
511 /// Erase a variable from the set of open ranges, and additionally erase any
512 /// fragments that may overlap it.
513 void LiveDebugValues::OpenRangesSet::erase(DebugVariable Var) {
514  // Erasure helper.
515  auto DoErase = [this](DebugVariable VarToErase) {
516  auto It = Vars.find(VarToErase);
517  if (It != Vars.end()) {
518  unsigned ID = It->second;
519  VarLocs.reset(ID);
520  Vars.erase(It);
521  }
522  };
523 
524  // Erase the variable/fragment that ends here.
525  DoErase(Var);
526 
527  // Extract the fragment. Interpret an empty fragment as one that covers all
528  // possible bits.
529  FragmentInfo ThisFragment = Var.getFragmentDefault();
530 
531  // There may be fragments that overlap the designated fragment. Look them up
532  // in the pre-computed overlap map, and erase them too.
533  auto MapIt = OverlappingFragments.find({Var.getVar(), ThisFragment});
534  if (MapIt != OverlappingFragments.end()) {
535  for (auto Fragment : MapIt->second) {
536  LiveDebugValues::OptFragmentInfo FragmentHolder;
537  if (!DebugVariable::isFragmentDefault(Fragment))
538  FragmentHolder = LiveDebugValues::OptFragmentInfo(Fragment);
539  DoErase({Var.getVar(), FragmentHolder, Var.getInlinedAt()});
540  }
541  }
542 }
543 
544 //===----------------------------------------------------------------------===//
545 // Debug Range Extension Implementation
546 //===----------------------------------------------------------------------===//
547 
548 #ifndef NDEBUG
549 void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF,
550  const VarLocInMBB &V,
551  const VarLocMap &VarLocIDs,
552  const char *msg,
553  raw_ostream &Out) const {
554  Out << '\n' << msg << '\n';
555  for (const MachineBasicBlock &BB : MF) {
556  const VarLocSet &L = V.lookup(&BB);
557  if (L.empty())
558  continue;
559  Out << "MBB: " << BB.getNumber() << ":\n";
560  for (unsigned VLL : L) {
561  const VarLoc &VL = VarLocIDs[VLL];
562  Out << " Var: " << VL.Var.getVar()->getName();
563  Out << " MI: ";
564  VL.dump();
565  }
566  }
567  Out << "\n";
568 }
569 #endif
570 
571 LiveDebugValues::VarLoc::SpillLoc
572 LiveDebugValues::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
573  assert(MI.hasOneMemOperand() &&
574  "Spill instruction does not have exactly one memory operand?");
575  auto MMOI = MI.memoperands_begin();
576  const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
578  "Inconsistent memory operand in spill instruction");
579  int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
580  const MachineBasicBlock *MBB = MI.getParent();
581  unsigned Reg;
582  int Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg);
583  return {Reg, Offset};
584 }
585 
586 /// End all previous ranges related to @MI and start a new range from @MI
587 /// if it is a DBG_VALUE instr.
588 void LiveDebugValues::transferDebugValue(const MachineInstr &MI,
589  OpenRangesSet &OpenRanges,
590  VarLocMap &VarLocIDs) {
591  if (!MI.isDebugValue())
592  return;
593  const DILocalVariable *Var = MI.getDebugVariable();
594  const DIExpression *Expr = MI.getDebugExpression();
595  const DILocation *DebugLoc = MI.getDebugLoc();
596  const DILocation *InlinedAt = DebugLoc->getInlinedAt();
597  assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
598  "Expected inlined-at fields to agree");
599 
600  // End all previous ranges of Var.
601  DebugVariable V(Var, Expr, InlinedAt);
602  OpenRanges.erase(V);
603 
604  // Add the VarLoc to OpenRanges from this DBG_VALUE.
605  unsigned ID;
606  if (isDbgValueDescribedByReg(MI) || MI.getOperand(0).isImm() ||
607  MI.getOperand(0).isFPImm() || MI.getOperand(0).isCImm()) {
608  // Use normal VarLoc constructor for registers and immediates.
609  VarLoc VL(MI, LS);
610  ID = VarLocIDs.insert(VL);
611  OpenRanges.insert(ID, VL.Var);
612  } else if (MI.hasOneMemOperand()) {
613  llvm_unreachable("DBG_VALUE with mem operand encountered after regalloc?");
614  } else {
615  // This must be an undefined location. We should leave OpenRanges closed.
616  assert(MI.getOperand(0).isReg() && MI.getOperand(0).getReg() == 0 &&
617  "Unexpected non-undef DBG_VALUE encountered");
618  }
619 }
620 
621 void LiveDebugValues::emitEntryValues(MachineInstr &MI,
622  OpenRangesSet &OpenRanges,
623  VarLocMap &VarLocIDs,
624  TransferMap &Transfers,
625  DebugParamMap &DebugEntryVals,
626  SparseBitVector<> &KillSet) {
627  MachineFunction *MF = MI.getParent()->getParent();
628  for (unsigned ID : KillSet) {
629  if (!VarLocIDs[ID].Var.getVar()->isParameter())
630  continue;
631 
632  const MachineInstr *CurrDebugInstr = &VarLocIDs[ID].MI;
633 
634  // If parameter's DBG_VALUE is not in the map that means we can't
635  // generate parameter's entry value.
636  if (!DebugEntryVals.count(CurrDebugInstr->getDebugVariable()))
637  continue;
638 
639  auto ParamDebugInstr = DebugEntryVals[CurrDebugInstr->getDebugVariable()];
641  ParamDebugInstr->getDebugExpression(), DIExpression::EntryValue);
642  MachineInstr *EntryValDbgMI =
643  BuildMI(*MF, ParamDebugInstr->getDebugLoc(), ParamDebugInstr->getDesc(),
644  ParamDebugInstr->isIndirectDebugValue(),
645  ParamDebugInstr->getOperand(0).getReg(),
646  ParamDebugInstr->getDebugVariable(), NewExpr);
647 
648  if (ParamDebugInstr->isIndirectDebugValue())
649  EntryValDbgMI->getOperand(1).setImm(
650  ParamDebugInstr->getOperand(1).getImm());
651 
652  Transfers.push_back({&MI, EntryValDbgMI});
653  VarLoc VL(*EntryValDbgMI, LS);
654  unsigned EntryValLocID = VarLocIDs.insert(VL);
655  OpenRanges.insert(EntryValLocID, VL.Var);
656  }
657 }
658 
659 /// Create new TransferDebugPair and insert it in \p Transfers. The VarLoc
660 /// with \p OldVarID should be deleted form \p OpenRanges and replaced with
661 /// new VarLoc. If \p NewReg is different than default zero value then the
662 /// new location will be register location created by the copy like instruction,
663 /// otherwise it is variable's location on the stack.
664 void LiveDebugValues::insertTransferDebugPair(
665  MachineInstr &MI, OpenRangesSet &OpenRanges, TransferMap &Transfers,
666  VarLocMap &VarLocIDs, unsigned OldVarID, TransferKind Kind,
667  unsigned NewReg) {
668  const MachineInstr *DebugInstr = &VarLocIDs[OldVarID].MI;
669  MachineFunction *MF = MI.getParent()->getParent();
670  MachineInstr *NewDebugInstr;
671 
672  auto ProcessVarLoc = [&MI, &OpenRanges, &Transfers, &DebugInstr,
673  &VarLocIDs](VarLoc &VL, MachineInstr *NewDebugInstr) {
674  unsigned LocId = VarLocIDs.insert(VL);
675 
676  // Close this variable's previous location range.
677  DebugVariable V(*DebugInstr);
678  OpenRanges.erase(V);
679 
680  OpenRanges.insert(LocId, VL.Var);
681  // The newly created DBG_VALUE instruction NewDebugInstr must be inserted
682  // after MI. Keep track of the pairing.
683  TransferDebugPair MIP = {&MI, NewDebugInstr};
684  Transfers.push_back(MIP);
685  };
686 
687  // End all previous ranges of Var.
688  OpenRanges.erase(VarLocIDs[OldVarID].Var);
689  switch (Kind) {
690  case TransferKind::TransferCopy: {
691  assert(NewReg &&
692  "No register supplied when handling a copy of a debug value");
693  // Create a DBG_VALUE instruction to describe the Var in its new
694  // register location.
695  NewDebugInstr = BuildMI(
696  *MF, DebugInstr->getDebugLoc(), DebugInstr->getDesc(),
697  DebugInstr->isIndirectDebugValue(), NewReg,
698  DebugInstr->getDebugVariable(), DebugInstr->getDebugExpression());
699  if (DebugInstr->isIndirectDebugValue())
700  NewDebugInstr->getOperand(1).setImm(DebugInstr->getOperand(1).getImm());
701  VarLoc VL(*NewDebugInstr, LS);
702  ProcessVarLoc(VL, NewDebugInstr);
703  LLVM_DEBUG(dbgs() << "Creating DBG_VALUE inst for register copy: ";
704  NewDebugInstr->print(dbgs(), /*IsStandalone*/false,
705  /*SkipOpers*/false, /*SkipDebugLoc*/false,
706  /*AddNewLine*/true, TII));
707  return;
708  }
709  case TransferKind::TransferSpill: {
710  // Create a DBG_VALUE instruction to describe the Var in its spilled
711  // location.
712  VarLoc::SpillLoc SpillLocation = extractSpillBaseRegAndOffset(MI);
713  auto *SpillExpr = DIExpression::prepend(DebugInstr->getDebugExpression(),
715  SpillLocation.SpillOffset);
716  NewDebugInstr = BuildMI(
717  *MF, DebugInstr->getDebugLoc(), DebugInstr->getDesc(), true,
718  SpillLocation.SpillBase, DebugInstr->getDebugVariable(), SpillExpr);
719  VarLoc VL(*NewDebugInstr, SpillLocation.SpillBase,
720  SpillLocation.SpillOffset, LS, *DebugInstr);
721  ProcessVarLoc(VL, NewDebugInstr);
722  LLVM_DEBUG(dbgs() << "Creating DBG_VALUE inst for spill: ";
723  NewDebugInstr->print(dbgs(), /*IsStandalone*/false,
724  /*SkipOpers*/false, /*SkipDebugLoc*/false,
725  /*AddNewLine*/true, TII));
726  return;
727  }
728  case TransferKind::TransferRestore: {
729  assert(NewReg &&
730  "No register supplied when handling a restore of a debug value");
731  MachineFunction *MF = MI.getMF();
732  DIBuilder DIB(*const_cast<Function &>(MF->getFunction()).getParent());
733  // DebugInstr refers to the pre-spill location, therefore we can reuse
734  // its expression.
735  NewDebugInstr = BuildMI(
736  *MF, DebugInstr->getDebugLoc(), DebugInstr->getDesc(), false, NewReg,
737  DebugInstr->getDebugVariable(), DebugInstr->getDebugExpression());
738  VarLoc VL(*NewDebugInstr, LS);
739  ProcessVarLoc(VL, NewDebugInstr);
740  LLVM_DEBUG(dbgs() << "Creating DBG_VALUE inst for register restore: ";
741  NewDebugInstr->print(dbgs(), /*IsStandalone*/false,
742  /*SkipOpers*/false, /*SkipDebugLoc*/false,
743  /*AddNewLine*/true, TII));
744  return;
745  }
746  }
747  llvm_unreachable("Invalid transfer kind");
748 }
749 
750 /// A definition of a register may mark the end of a range.
751 void LiveDebugValues::transferRegisterDef(
752  MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs,
753  TransferMap &Transfers, DebugParamMap &DebugEntryVals) {
754  MachineFunction *MF = MI.getMF();
755  const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
756  unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
757  SparseBitVector<> KillSet;
758  for (const MachineOperand &MO : MI.operands()) {
759  // Determine whether the operand is a register def. Assume that call
760  // instructions never clobber SP, because some backends (e.g., AArch64)
761  // never list SP in the regmask.
762  if (MO.isReg() && MO.isDef() && MO.getReg() &&
763  Register::isPhysicalRegister(MO.getReg()) &&
764  !(MI.isCall() && MO.getReg() == SP)) {
765  // Remove ranges of all aliased registers.
766  for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
767  for (unsigned ID : OpenRanges.getVarLocs())
768  if (VarLocIDs[ID].isDescribedByReg() == *RAI)
769  KillSet.set(ID);
770  } else if (MO.isRegMask()) {
771  // Remove ranges of all clobbered registers. Register masks don't usually
772  // list SP as preserved. While the debug info may be off for an
773  // instruction or two around callee-cleanup calls, transferring the
774  // DEBUG_VALUE across the call is still a better user experience.
775  for (unsigned ID : OpenRanges.getVarLocs()) {
776  unsigned Reg = VarLocIDs[ID].isDescribedByReg();
777  if (Reg && Reg != SP && MO.clobbersPhysReg(Reg))
778  KillSet.set(ID);
779  }
780  }
781  }
782  OpenRanges.erase(KillSet, VarLocIDs);
783 
784  if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) {
785  auto &TM = TPC->getTM<TargetMachine>();
786  if (TM.Options.EnableDebugEntryValues)
787  emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, DebugEntryVals,
788  KillSet);
789  }
790 }
791 
792 bool LiveDebugValues::isSpillInstruction(const MachineInstr &MI,
793  MachineFunction *MF) {
794  // TODO: Handle multiple stores folded into one.
795  if (!MI.hasOneMemOperand())
796  return false;
797 
798  if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII))
799  return false; // This is not a spill instruction, since no valid size was
800  // returned from either function.
801 
802  return true;
803 }
804 
805 bool LiveDebugValues::isLocationSpill(const MachineInstr &MI,
806  MachineFunction *MF, unsigned &Reg) {
807  if (!isSpillInstruction(MI, MF))
808  return false;
809 
810  auto isKilledReg = [&](const MachineOperand MO, unsigned &Reg) {
811  if (!MO.isReg() || !MO.isUse()) {
812  Reg = 0;
813  return false;
814  }
815  Reg = MO.getReg();
816  return MO.isKill();
817  };
818 
819  for (const MachineOperand &MO : MI.operands()) {
820  // In a spill instruction generated by the InlineSpiller the spilled
821  // register has its kill flag set.
822  if (isKilledReg(MO, Reg))
823  return true;
824  if (Reg != 0) {
825  // Check whether next instruction kills the spilled register.
826  // FIXME: Current solution does not cover search for killed register in
827  // bundles and instructions further down the chain.
828  auto NextI = std::next(MI.getIterator());
829  // Skip next instruction that points to basic block end iterator.
830  if (MI.getParent()->end() == NextI)
831  continue;
832  unsigned RegNext;
833  for (const MachineOperand &MONext : NextI->operands()) {
834  // Return true if we came across the register from the
835  // previous spill instruction that is killed in NextI.
836  if (isKilledReg(MONext, RegNext) && RegNext == Reg)
837  return true;
838  }
839  }
840  }
841  // Return false if we didn't find spilled register.
842  return false;
843 }
844 
846 LiveDebugValues::isRestoreInstruction(const MachineInstr &MI,
847  MachineFunction *MF, unsigned &Reg) {
848  if (!MI.hasOneMemOperand())
849  return None;
850 
851  // FIXME: Handle folded restore instructions with more than one memory
852  // operand.
853  if (MI.getRestoreSize(TII)) {
854  Reg = MI.getOperand(0).getReg();
855  return extractSpillBaseRegAndOffset(MI);
856  }
857  return None;
858 }
859 
860 /// A spilled register may indicate that we have to end the current range of
861 /// a variable and create a new one for the spill location.
862 /// A restored register may indicate the reverse situation.
863 /// We don't want to insert any instructions in process(), so we just create
864 /// the DBG_VALUE without inserting it and keep track of it in \p Transfers.
865 /// It will be inserted into the BB when we're done iterating over the
866 /// instructions.
867 void LiveDebugValues::transferSpillOrRestoreInst(MachineInstr &MI,
868  OpenRangesSet &OpenRanges,
869  VarLocMap &VarLocIDs,
870  TransferMap &Transfers) {
871  MachineFunction *MF = MI.getMF();
872  TransferKind TKind;
873  unsigned Reg;
875 
876  LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump(););
877 
878  // First, if there are any DBG_VALUEs pointing at a spill slot that is
879  // written to, then close the variable location. The value in memory
880  // will have changed.
881  VarLocSet KillSet;
882  if (isSpillInstruction(MI, MF)) {
883  Loc = extractSpillBaseRegAndOffset(MI);
884  for (unsigned ID : OpenRanges.getVarLocs()) {
885  const VarLoc &VL = VarLocIDs[ID];
886  if (VL.Kind == VarLoc::SpillLocKind && VL.Loc.SpillLocation == *Loc) {
887  // This location is overwritten by the current instruction -- terminate
888  // the open range, and insert an explicit DBG_VALUE $noreg.
889  //
890  // Doing this at a later stage would require re-interpreting all
891  // DBG_VALUes and DIExpressions to identify whether they point at
892  // memory, and then analysing all memory writes to see if they
893  // overwrite that memory, which is expensive.
894  //
895  // At this stage, we already know which DBG_VALUEs are for spills and
896  // where they are located; it's best to fix handle overwrites now.
897  KillSet.set(ID);
898  MachineInstr *NewDebugInstr =
899  BuildMI(*MF, VL.MI.getDebugLoc(), VL.MI.getDesc(),
900  VL.MI.isIndirectDebugValue(), 0, // $noreg
901  VL.MI.getDebugVariable(), VL.MI.getDebugExpression());
902  Transfers.push_back({&MI, NewDebugInstr});
903  }
904  }
905  OpenRanges.erase(KillSet, VarLocIDs);
906  }
907 
908  // Try to recognise spill and restore instructions that may create a new
909  // variable location.
910  if (isLocationSpill(MI, MF, Reg)) {
911  TKind = TransferKind::TransferSpill;
912  LLVM_DEBUG(dbgs() << "Recognized as spill: "; MI.dump(););
913  LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI)
914  << "\n");
915  } else {
916  if (!(Loc = isRestoreInstruction(MI, MF, Reg)))
917  return;
918  TKind = TransferKind::TransferRestore;
919  LLVM_DEBUG(dbgs() << "Recognized as restore: "; MI.dump(););
920  LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI)
921  << "\n");
922  }
923  // Check if the register or spill location is the location of a debug value.
924  for (unsigned ID : OpenRanges.getVarLocs()) {
925  if (TKind == TransferKind::TransferSpill &&
926  VarLocIDs[ID].isDescribedByReg() == Reg) {
927  LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '('
928  << VarLocIDs[ID].Var.getVar()->getName() << ")\n");
929  } else if (TKind == TransferKind::TransferRestore &&
930  VarLocIDs[ID].Kind == VarLoc::SpillLocKind &&
931  VarLocIDs[ID].Loc.SpillLocation == *Loc) {
932  LLVM_DEBUG(dbgs() << "Restoring Register " << printReg(Reg, TRI) << '('
933  << VarLocIDs[ID].Var.getVar()->getName() << ")\n");
934  } else
935  continue;
936  insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID, TKind,
937  Reg);
938  return;
939  }
940 }
941 
942 /// If \p MI is a register copy instruction, that copies a previously tracked
943 /// value from one register to another register that is callee saved, we
944 /// create new DBG_VALUE instruction described with copy destination register.
945 void LiveDebugValues::transferRegisterCopy(MachineInstr &MI,
946  OpenRangesSet &OpenRanges,
947  VarLocMap &VarLocIDs,
948  TransferMap &Transfers) {
949  const MachineOperand *SrcRegOp, *DestRegOp;
950 
951  if (!TII->isCopyInstr(MI, SrcRegOp, DestRegOp) || !SrcRegOp->isKill() ||
952  !DestRegOp->isDef())
953  return;
954 
955  auto isCalleSavedReg = [&](unsigned Reg) {
956  for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
957  if (CalleeSavedRegs.test(*RAI))
958  return true;
959  return false;
960  };
961 
962  Register SrcReg = SrcRegOp->getReg();
963  Register DestReg = DestRegOp->getReg();
964 
965  // We want to recognize instructions where destination register is callee
966  // saved register. If register that could be clobbered by the call is
967  // included, there would be a great chance that it is going to be clobbered
968  // soon. It is more likely that previous register location, which is callee
969  // saved, is going to stay unclobbered longer, even if it is killed.
970  if (!isCalleSavedReg(DestReg))
971  return;
972 
973  for (unsigned ID : OpenRanges.getVarLocs()) {
974  if (VarLocIDs[ID].isDescribedByReg() == SrcReg) {
975  insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID,
976  TransferKind::TransferCopy, DestReg);
977  return;
978  }
979  }
980 }
981 
982 /// Terminate all open ranges at the end of the current basic block.
983 bool LiveDebugValues::transferTerminator(MachineBasicBlock *CurMBB,
984  OpenRangesSet &OpenRanges,
985  VarLocInMBB &OutLocs,
986  const VarLocMap &VarLocIDs) {
987  bool Changed = false;
988 
989  if (OpenRanges.empty())
990  return false;
991 
992  LLVM_DEBUG(for (unsigned ID
993  : OpenRanges.getVarLocs()) {
994  // Copy OpenRanges to OutLocs, if not already present.
995  dbgs() << "Add to OutLocs in MBB #" << CurMBB->getNumber() << ": ";
996  VarLocIDs[ID].dump();
997  });
998  VarLocSet &VLS = OutLocs[CurMBB];
999  Changed = VLS != OpenRanges.getVarLocs();
1000  // New OutLocs set may be different due to spill, restore or register
1001  // copy instruction processing.
1002  if (Changed)
1003  VLS = OpenRanges.getVarLocs();
1004  OpenRanges.clear();
1005  return Changed;
1006 }
1007 
1008 /// Accumulate a mapping between each DILocalVariable fragment and other
1009 /// fragments of that DILocalVariable which overlap. This reduces work during
1010 /// the data-flow stage from "Find any overlapping fragments" to "Check if the
1011 /// known-to-overlap fragments are present".
1012 /// \param MI A previously unprocessed DEBUG_VALUE instruction to analyze for
1013 /// fragment usage.
1014 /// \param SeenFragments Map from DILocalVariable to all fragments of that
1015 /// Variable which are known to exist.
1016 /// \param OverlappingFragments The overlap map being constructed, from one
1017 /// Var/Fragment pair to a vector of fragments known to overlap.
1018 void LiveDebugValues::accumulateFragmentMap(MachineInstr &MI,
1019  VarToFragments &SeenFragments,
1020  OverlapMap &OverlappingFragments) {
1021  DebugVariable MIVar(MI);
1022  FragmentInfo ThisFragment = MIVar.getFragmentDefault();
1023 
1024  // If this is the first sighting of this variable, then we are guaranteed
1025  // there are currently no overlapping fragments either. Initialize the set
1026  // of seen fragments, record no overlaps for the current one, and return.
1027  auto SeenIt = SeenFragments.find(MIVar.getVar());
1028  if (SeenIt == SeenFragments.end()) {
1029  SmallSet<FragmentInfo, 4> OneFragment;
1030  OneFragment.insert(ThisFragment);
1031  SeenFragments.insert({MIVar.getVar(), OneFragment});
1032 
1033  OverlappingFragments.insert({{MIVar.getVar(), ThisFragment}, {}});
1034  return;
1035  }
1036 
1037  // If this particular Variable/Fragment pair already exists in the overlap
1038  // map, it has already been accounted for.
1039  auto IsInOLapMap =
1040  OverlappingFragments.insert({{MIVar.getVar(), ThisFragment}, {}});
1041  if (!IsInOLapMap.second)
1042  return;
1043 
1044  auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;
1045  auto &AllSeenFragments = SeenIt->second;
1046 
1047  // Otherwise, examine all other seen fragments for this variable, with "this"
1048  // fragment being a previously unseen fragment. Record any pair of
1049  // overlapping fragments.
1050  for (auto &ASeenFragment : AllSeenFragments) {
1051  // Does this previously seen fragment overlap?
1052  if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) {
1053  // Yes: Mark the current fragment as being overlapped.
1054  ThisFragmentsOverlaps.push_back(ASeenFragment);
1055  // Mark the previously seen fragment as being overlapped by the current
1056  // one.
1057  auto ASeenFragmentsOverlaps =
1058  OverlappingFragments.find({MIVar.getVar(), ASeenFragment});
1059  assert(ASeenFragmentsOverlaps != OverlappingFragments.end() &&
1060  "Previously seen var fragment has no vector of overlaps");
1061  ASeenFragmentsOverlaps->second.push_back(ThisFragment);
1062  }
1063  }
1064 
1065  AllSeenFragments.insert(ThisFragment);
1066 }
1067 
1068 /// This routine creates OpenRanges and OutLocs.
1069 void LiveDebugValues::process(MachineInstr &MI, OpenRangesSet &OpenRanges,
1070  VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
1071  TransferMap &Transfers,
1072  DebugParamMap &DebugEntryVals,
1073  OverlapMap &OverlapFragments,
1074  VarToFragments &SeenFragments) {
1075  transferDebugValue(MI, OpenRanges, VarLocIDs);
1076  transferRegisterDef(MI, OpenRanges, VarLocIDs, Transfers,
1077  DebugEntryVals);
1078  transferRegisterCopy(MI, OpenRanges, VarLocIDs, Transfers);
1079  transferSpillOrRestoreInst(MI, OpenRanges, VarLocIDs, Transfers);
1080 }
1081 
1082 /// This routine joins the analysis results of all incoming edges in @MBB by
1083 /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
1084 /// source variable in all the predecessors of @MBB reside in the same location.
1086  MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
1087  const VarLocMap &VarLocIDs,
1090  VarLocInMBB &PendingInLocs) {
1091  LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
1092  bool Changed = false;
1093 
1094  VarLocSet InLocsT; // Temporary incoming locations.
1095 
1096  // For all predecessors of this MBB, find the set of VarLocs that
1097  // can be joined.
1098  int NumVisited = 0;
1099  for (auto p : MBB.predecessors()) {
1100  // Ignore backedges if we have not visited the predecessor yet. As the
1101  // predecessor hasn't yet had locations propagated into it, most locations
1102  // will not yet be valid, so treat them as all being uninitialized and
1103  // potentially valid. If a location guessed to be correct here is
1104  // invalidated later, we will remove it when we revisit this block.
1105  if (!Visited.count(p)) {
1106  LLVM_DEBUG(dbgs() << " ignoring unvisited pred MBB: " << p->getNumber()
1107  << "\n");
1108  continue;
1109  }
1110  auto OL = OutLocs.find(p);
1111  // Join is null in case of empty OutLocs from any of the pred.
1112  if (OL == OutLocs.end())
1113  return false;
1114 
1115  // Just copy over the Out locs to incoming locs for the first visited
1116  // predecessor, and for all other predecessors join the Out locs.
1117  if (!NumVisited)
1118  InLocsT = OL->second;
1119  else
1120  InLocsT &= OL->second;
1121 
1122  LLVM_DEBUG({
1123  if (!InLocsT.empty()) {
1124  for (auto ID : InLocsT)
1125  dbgs() << " gathered candidate incoming var: "
1126  << VarLocIDs[ID].Var.getVar()->getName() << "\n";
1127  }
1128  });
1129 
1130  NumVisited++;
1131  }
1132 
1133  // Filter out DBG_VALUES that are out of scope.
1134  VarLocSet KillSet;
1135  bool IsArtificial = ArtificialBlocks.count(&MBB);
1136  if (!IsArtificial) {
1137  for (auto ID : InLocsT) {
1138  if (!VarLocIDs[ID].dominates(MBB)) {
1139  KillSet.set(ID);
1140  LLVM_DEBUG({
1141  auto Name = VarLocIDs[ID].Var.getVar()->getName();
1142  dbgs() << " killing " << Name << ", it doesn't dominate MBB\n";
1143  });
1144  }
1145  }
1146  }
1147  InLocsT.intersectWithComplement(KillSet);
1148 
1149  // As we are processing blocks in reverse post-order we
1150  // should have processed at least one predecessor, unless it
1151  // is the entry block which has no predecessor.
1152  assert((NumVisited || MBB.pred_empty()) &&
1153  "Should have processed at least one predecessor");
1154 
1155  VarLocSet &ILS = InLocs[&MBB];
1156  VarLocSet &Pending = PendingInLocs[&MBB];
1157 
1158  // New locations will have DBG_VALUE insts inserted at the start of the
1159  // block, after location propagation has finished. Record the insertions
1160  // that we need to perform in the Pending set.
1161  VarLocSet Diff = InLocsT;
1162  Diff.intersectWithComplement(ILS);
1163  for (auto ID : Diff) {
1164  Pending.set(ID);
1165  ILS.set(ID);
1166  ++NumInserted;
1167  Changed = true;
1168  }
1169 
1170  // We may have lost locations by learning about a predecessor that either
1171  // loses or moves a variable. Find any locations in ILS that are not in the
1172  // new in-locations, and delete those.
1173  VarLocSet Removed = ILS;
1174  Removed.intersectWithComplement(InLocsT);
1175  for (auto ID : Removed) {
1176  Pending.reset(ID);
1177  ILS.reset(ID);
1178  ++NumRemoved;
1179  Changed = true;
1180  }
1181 
1182  return Changed;
1183 }
1184 
1185 void LiveDebugValues::flushPendingLocs(VarLocInMBB &PendingInLocs,
1186  VarLocMap &VarLocIDs) {
1187  // PendingInLocs records all locations propagated into blocks, which have
1188  // not had DBG_VALUE insts created. Go through and create those insts now.
1189  for (auto &Iter : PendingInLocs) {
1190  // Map is keyed on a constant pointer, unwrap it so we can insert insts.
1191  auto &MBB = const_cast<MachineBasicBlock &>(*Iter.first);
1192  VarLocSet &Pending = Iter.second;
1193 
1194  for (unsigned ID : Pending) {
1195  // The ID location is live-in to MBB -- work out what kind of machine
1196  // location it is and create a DBG_VALUE.
1197  const VarLoc &DiffIt = VarLocIDs[ID];
1198  const MachineInstr *DebugInstr = &DiffIt.MI;
1199  MachineInstr *MI = nullptr;
1200 
1201  if (DiffIt.isConstant()) {
1202  MachineOperand MO(DebugInstr->getOperand(0));
1203  MI = BuildMI(MBB, MBB.instr_begin(), DebugInstr->getDebugLoc(),
1204  DebugInstr->getDesc(), false, MO,
1205  DebugInstr->getDebugVariable(),
1206  DebugInstr->getDebugExpression());
1207  } else {
1208  auto *DebugExpr = DebugInstr->getDebugExpression();
1209  Register Reg = DebugInstr->getOperand(0).getReg();
1210  bool IsIndirect = DebugInstr->isIndirectDebugValue();
1211 
1212  if (DiffIt.Kind == VarLoc::SpillLocKind) {
1213  // This is is a spilt location; DebugInstr refers to the unspilt
1214  // location. We need to rebuild the spilt location expression and
1215  // point the DBG_VALUE at the frame register.
1216  DebugExpr = DIExpression::prepend(
1218  DiffIt.Loc.SpillLocation.SpillOffset);
1219  Reg = TRI->getFrameRegister(*DebugInstr->getMF());
1220  IsIndirect = true;
1221  }
1222 
1223  MI = BuildMI(MBB, MBB.instr_begin(), DebugInstr->getDebugLoc(),
1224  DebugInstr->getDesc(), IsIndirect, Reg,
1225  DebugInstr->getDebugVariable(), DebugExpr);
1226  }
1227  (void)MI;
1228  LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump(););
1229  }
1230  }
1231 }
1232 
1233 /// Calculate the liveness information for the given machine function and
1234 /// extend ranges across basic blocks.
1235 bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
1236  LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
1237 
1238  bool Changed = false;
1239  bool OLChanged = false;
1240  bool MBBJoined = false;
1241 
1242  VarLocMap VarLocIDs; // Map VarLoc<>unique ID for use in bitvectors.
1243  OverlapMap OverlapFragments; // Map of overlapping variable fragments
1244  OpenRangesSet OpenRanges(OverlapFragments);
1245  // Ranges that are open until end of bb.
1246  VarLocInMBB OutLocs; // Ranges that exist beyond bb.
1247  VarLocInMBB InLocs; // Ranges that are incoming after joining.
1248  TransferMap Transfers; // DBG_VALUEs associated with spills.
1249  VarLocInMBB PendingInLocs; // Ranges that are incoming after joining, but
1250  // that we have deferred creating DBG_VALUE insts
1251  // for immediately.
1252 
1253  VarToFragments SeenFragments;
1254 
1255  // Blocks which are artificial, i.e. blocks which exclusively contain
1256  // instructions without locations, or with line 0 locations.
1258 
1261  std::priority_queue<unsigned int, std::vector<unsigned int>,
1262  std::greater<unsigned int>>
1263  Worklist;
1264  std::priority_queue<unsigned int, std::vector<unsigned int>,
1265  std::greater<unsigned int>>
1266  Pending;
1267 
1268  // Besides parameter's modification, check whether a DBG_VALUE is inlined
1269  // in order to deduce whether the variable that it tracks comes from
1270  // a different function. If that is the case we can't track its entry value.
1271  auto IsUnmodifiedFuncParam = [&](const MachineInstr &MI) {
1272  auto *DIVar = MI.getDebugVariable();
1273  return DIVar->isParameter() && DIVar->isNotModified() &&
1274  !MI.getDebugLoc()->getInlinedAt();
1275  };
1276 
1277  const TargetLowering *TLI = MF.getSubtarget().getTargetLowering();
1278  unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
1279  Register FP = TRI->getFrameRegister(MF);
1280  auto IsRegOtherThanSPAndFP = [&](const MachineOperand &Op) -> bool {
1281  return Op.isReg() && Op.getReg() != SP && Op.getReg() != FP;
1282  };
1283 
1284  // Working set of currently collected debug variables mapped to DBG_VALUEs
1285  // representing candidates for production of debug entry values.
1286  DebugParamMap DebugEntryVals;
1287 
1288  MachineBasicBlock &First_MBB = *(MF.begin());
1289  // Only in the case of entry MBB collect DBG_VALUEs representing
1290  // function parameters in order to generate debug entry values for them.
1291  // Currently, we generate debug entry values only for parameters that are
1292  // unmodified throughout the function and located in a register.
1293  // TODO: Add support for parameters that are described as fragments.
1294  // TODO: Add support for modified arguments that can be expressed
1295  // by using its entry value.
1296  // TODO: Add support for local variables that are expressed in terms of
1297  // parameters entry values.
1298  for (auto &MI : First_MBB)
1299  if (MI.isDebugValue() && IsUnmodifiedFuncParam(MI) &&
1300  !MI.isIndirectDebugValue() && IsRegOtherThanSPAndFP(MI.getOperand(0)) &&
1301  !DebugEntryVals.count(MI.getDebugVariable()) &&
1302  !MI.getDebugExpression()->isFragment())
1303  DebugEntryVals[MI.getDebugVariable()] = &MI;
1304 
1305  // Initialize per-block structures and scan for fragment overlaps.
1306  for (auto &MBB : MF) {
1307  PendingInLocs[&MBB] = VarLocSet();
1308 
1309  for (auto &MI : MBB) {
1310  if (MI.isDebugValue())
1311  accumulateFragmentMap(MI, SeenFragments, OverlapFragments);
1312  }
1313  }
1314 
1315  auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
1316  if (const DebugLoc &DL = MI.getDebugLoc())
1317  return DL.getLine() != 0;
1318  return false;
1319  };
1320  for (auto &MBB : MF)
1321  if (none_of(MBB.instrs(), hasNonArtificialLocation))
1322  ArtificialBlocks.insert(&MBB);
1323 
1324  LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
1325  "OutLocs after initialization", dbgs()));
1326 
1328  unsigned int RPONumber = 0;
1329  for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
1330  OrderToBB[RPONumber] = *RI;
1331  BBToOrder[*RI] = RPONumber;
1332  Worklist.push(RPONumber);
1333  ++RPONumber;
1334  }
1335  // This is a standard "union of predecessor outs" dataflow problem.
1336  // To solve it, we perform join() and process() using the two worklist method
1337  // until the ranges converge.
1338  // Ranges have converged when both worklists are empty.
1340  while (!Worklist.empty() || !Pending.empty()) {
1341  // We track what is on the pending worklist to avoid inserting the same
1342  // thing twice. We could avoid this with a custom priority queue, but this
1343  // is probably not worth it.
1345  LLVM_DEBUG(dbgs() << "Processing Worklist\n");
1346  while (!Worklist.empty()) {
1347  MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
1348  Worklist.pop();
1349  MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs, Visited,
1350  ArtificialBlocks, PendingInLocs);
1351  MBBJoined |= Visited.insert(MBB).second;
1352  if (MBBJoined) {
1353  MBBJoined = false;
1354  Changed = true;
1355  // Now that we have started to extend ranges across BBs we need to
1356  // examine spill instructions to see whether they spill registers that
1357  // correspond to user variables.
1358  // First load any pending inlocs.
1359  OpenRanges.insertFromLocSet(PendingInLocs[MBB], VarLocIDs);
1360  for (auto &MI : *MBB)
1361  process(MI, OpenRanges, OutLocs, VarLocIDs, Transfers,
1362  DebugEntryVals, OverlapFragments, SeenFragments);
1363  OLChanged |= transferTerminator(MBB, OpenRanges, OutLocs, VarLocIDs);
1364 
1365  // Add any DBG_VALUE instructions necessitated by spills.
1366  for (auto &TR : Transfers)
1367  MBB->insertAfterBundle(TR.TransferInst->getIterator(), TR.DebugInst);
1368  Transfers.clear();
1369 
1370  LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
1371  "OutLocs after propagating", dbgs()));
1372  LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
1373  "InLocs after propagating", dbgs()));
1374 
1375  if (OLChanged) {
1376  OLChanged = false;
1377  for (auto s : MBB->successors())
1378  if (OnPending.insert(s).second) {
1379  Pending.push(BBToOrder[s]);
1380  }
1381  }
1382  }
1383  }
1384  Worklist.swap(Pending);
1385  // At this point, pending must be empty, since it was just the empty
1386  // worklist
1387  assert(Pending.empty() && "Pending should be empty");
1388  }
1389 
1390  // Deferred inlocs will not have had any DBG_VALUE insts created; do
1391  // that now.
1392  flushPendingLocs(PendingInLocs, VarLocIDs);
1393 
1394  LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs()));
1395  LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs()));
1396  return Changed;
1397 }
1398 
1399 bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
1400  if (!MF.getFunction().getSubprogram())
1401  // LiveDebugValues will already have removed all DBG_VALUEs.
1402  return false;
1403 
1404  // Skip functions from NoDebug compilation units.
1405  if (MF.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
1407  return false;
1408 
1409  TRI = MF.getSubtarget().getRegisterInfo();
1410  TII = MF.getSubtarget().getInstrInfo();
1411  TFI = MF.getSubtarget().getFrameLowering();
1412  TFI->determineCalleeSaves(MF, CalleeSavedRegs,
1413  std::make_unique<RegScavenger>().get());
1414  LS.initialize(MF);
1415 
1416  bool Changed = ExtendRanges(MF);
1417  return Changed;
1418 }
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()
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:651
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
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:476
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:385
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:477
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:414
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
bool isDebugEntryValue() const
A DBG_VALUE is an entry value iff its debug expression contains the DW_OP_entry_value DWARF operation...
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:408
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.
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:1504
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:567
char & LiveDebugValuesID
LiveDebugValues pass.
void setImm(int64_t immVal)
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()
void print(raw_ostream &OS, bool IsStandalone=true, bool SkipOpers=false, bool SkipDebugLoc=false, bool AddNewLine=true, const TargetInstrInfo *TII=nullptr) const
Print this MI to OS.
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
mmo_iterator memoperands_begin() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:552
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:600
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:256
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:64
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 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:416
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.