Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/LiveDebugValues.cpp
Line
Count
Source (jump to first uncovered line)
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 instructions into the machine
11
/// instruction stream. The pass internally builds debug location liveness
12
/// ranges to determine the points where additional DBG_VALUEs need to be
13
/// inserted.
14
///
15
/// This is a separate pass from DbgValueHistoryCalculator to facilitate
16
/// testing and improve modularity.
17
///
18
//===----------------------------------------------------------------------===//
19
20
#include "llvm/ADT/DenseMap.h"
21
#include "llvm/ADT/PostOrderIterator.h"
22
#include "llvm/ADT/SmallPtrSet.h"
23
#include "llvm/ADT/SmallSet.h"
24
#include "llvm/ADT/SmallVector.h"
25
#include "llvm/ADT/SparseBitVector.h"
26
#include "llvm/ADT/Statistic.h"
27
#include "llvm/ADT/UniqueVector.h"
28
#include "llvm/CodeGen/LexicalScopes.h"
29
#include "llvm/CodeGen/MachineBasicBlock.h"
30
#include "llvm/CodeGen/MachineFrameInfo.h"
31
#include "llvm/CodeGen/MachineFunction.h"
32
#include "llvm/CodeGen/MachineFunctionPass.h"
33
#include "llvm/CodeGen/MachineInstr.h"
34
#include "llvm/CodeGen/MachineInstrBuilder.h"
35
#include "llvm/CodeGen/MachineMemOperand.h"
36
#include "llvm/CodeGen/MachineOperand.h"
37
#include "llvm/CodeGen/PseudoSourceValue.h"
38
#include "llvm/CodeGen/RegisterScavenging.h"
39
#include "llvm/CodeGen/TargetFrameLowering.h"
40
#include "llvm/CodeGen/TargetInstrInfo.h"
41
#include "llvm/CodeGen/TargetLowering.h"
42
#include "llvm/CodeGen/TargetPassConfig.h"
43
#include "llvm/CodeGen/TargetRegisterInfo.h"
44
#include "llvm/CodeGen/TargetSubtargetInfo.h"
45
#include "llvm/Config/llvm-config.h"
46
#include "llvm/IR/DIBuilder.h"
47
#include "llvm/IR/DebugInfoMetadata.h"
48
#include "llvm/IR/DebugLoc.h"
49
#include "llvm/IR/Function.h"
50
#include "llvm/IR/Module.h"
51
#include "llvm/MC/MCRegisterInfo.h"
52
#include "llvm/Pass.h"
53
#include "llvm/Support/Casting.h"
54
#include "llvm/Support/Compiler.h"
55
#include "llvm/Support/Debug.h"
56
#include "llvm/Support/raw_ostream.h"
57
#include <algorithm>
58
#include <cassert>
59
#include <cstdint>
60
#include <functional>
61
#include <queue>
62
#include <tuple>
63
#include <utility>
64
#include <vector>
65
66
using namespace llvm;
67
68
#define DEBUG_TYPE "livedebugvalues"
69
70
STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
71
72
// If @MI is a DBG_VALUE with debug value described by a defined
73
// register, returns the number of this register. In the other case, returns 0.
74
12.8k
static Register isDbgValueDescribedByReg(const MachineInstr &MI) {
75
12.8k
  assert(MI.isDebugValue() && "expected a DBG_VALUE");
76
12.8k
  assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
77
12.8k
  // If location of variable is described using a register (directly
78
12.8k
  // or indirectly), this register is always a first operand.
79
12.8k
  return MI.getOperand(0).isReg() ? 
MI.getOperand(0).getReg()4.36k
:
Register()8.50k
;
80
12.8k
}
81
82
namespace {
83
84
class LiveDebugValues : public MachineFunctionPass {
85
private:
86
  const TargetRegisterInfo *TRI;
87
  const TargetInstrInfo *TII;
88
  const TargetFrameLowering *TFI;
89
  BitVector CalleeSavedRegs;
90
  LexicalScopes LS;
91
92
  enum struct TransferKind { TransferCopy, TransferSpill, TransferRestore };
93
94
  /// Keeps track of lexical scopes associated with a user value's source
95
  /// location.
96
  class UserValueScopes {
97
    DebugLoc DL;
98
    LexicalScopes &LS;
99
    SmallPtrSet<const MachineBasicBlock *, 4> LBlocks;
100
101
  public:
102
6.42k
    UserValueScopes(DebugLoc D, LexicalScopes &L) : DL(std::move(D)), LS(L) {}
103
104
    /// Return true if current scope dominates at least one machine
105
    /// instruction in a given machine basic block.
106
1.39k
    bool dominates(MachineBasicBlock *MBB) {
107
1.39k
      if (LBlocks.empty())
108
277
        LS.getMachineBasicBlocks(DL, LBlocks);
109
1.39k
      return LBlocks.count(MBB) != 0 || 
LS.dominates(DL, MBB)344
;
110
1.39k
    }
111
  };
112
113
  using FragmentInfo = DIExpression::FragmentInfo;
114
  using OptFragmentInfo = Optional<DIExpression::FragmentInfo>;
115
116
  /// Storage for identifying a potentially inlined instance of a variable,
117
  /// or a fragment thereof.
118
  class DebugVariable {
119
    const DILocalVariable *Variable;
120
    OptFragmentInfo Fragment;
121
    const DILocation *InlinedAt;
122
123
    /// Fragment that will overlap all other fragments. Used as default when
124
    /// caller demands a fragment.
125
    static const FragmentInfo DefaultFragment;
126
127
  public:
128
    DebugVariable(const DILocalVariable *Var, OptFragmentInfo &&FragmentInfo,
129
                  const DILocation *InlinedAt)
130
173k
        : Variable(Var), Fragment(FragmentInfo), InlinedAt(InlinedAt) {}
131
132
    DebugVariable(const DILocalVariable *Var, OptFragmentInfo &FragmentInfo,
133
                  const DILocation *InlinedAt)
134
11
        : Variable(Var), Fragment(FragmentInfo), InlinedAt(InlinedAt) {}
135
136
    DebugVariable(const DILocalVariable *Var, const DIExpression *DIExpr,
137
                  const DILocation *InlinedAt)
138
6.47k
        : DebugVariable(Var, DIExpr->getFragmentInfo(), InlinedAt) {}
139
140
    DebugVariable(const MachineInstr &MI)
141
        : DebugVariable(MI.getDebugVariable(),
142
                        MI.getDebugExpression()->getFragmentInfo(),
143
11.7k
                        MI.getDebugLoc()->getInlinedAt()) {}
144
145
37.7k
    const DILocalVariable *getVar() const { return Variable; }
146
19.6k
    const OptFragmentInfo &getFragment() const { return Fragment; }
147
19.7k
    const DILocation *getInlinedAt() const { return InlinedAt; }
148
149
11.8k
    const FragmentInfo getFragmentDefault() const {
150
11.8k
      return Fragment.getValueOr(DefaultFragment);
151
11.8k
    }
152
153
11
    static bool isFragmentDefault(FragmentInfo &F) {
154
11
      return F == DefaultFragment;
155
11
    }
156
157
6.00M
    bool operator==(const DebugVariable &Other) const {
158
6.00M
      return std::tie(Variable, Fragment, InlinedAt) ==
159
6.00M
             std::tie(Other.Variable, Other.Fragment, Other.InlinedAt);
160
6.00M
    }
161
162
234k
    bool operator<(const DebugVariable &Other) const {
163
234k
      return std::tie(Variable, Fragment, InlinedAt) <
164
234k
             std::tie(Other.Variable, Other.Fragment, Other.InlinedAt);
165
234k
    }
166
  };
167
168
  friend struct llvm::DenseMapInfo<DebugVariable>;
169
170
  /// A pair of debug variable and value location.
171
  struct VarLoc {
172
    // The location at which a spilled variable resides. It consists of a
173
    // register and an offset.
174
    struct SpillLoc {
175
      unsigned SpillBase;
176
      int SpillOffset;
177
195
      bool operator==(const SpillLoc &Other) const {
178
195
        return SpillBase == Other.SpillBase && 
SpillOffset == Other.SpillOffset102
;
179
195
      }
180
    };
181
182
    const DebugVariable Var;
183
    const MachineInstr &MI; ///< Only used for cloning a new DBG_VALUE.
184
    mutable UserValueScopes UVS;
185
    enum VarLocKind {
186
      InvalidKind = 0,
187
      RegisterKind,
188
      SpillLocKind,
189
      ImmediateKind,
190
      EntryValueKind
191
    } Kind = InvalidKind;
192
193
    /// The value location. Stored separately to avoid repeatedly
194
    /// extracting it from MI.
195
    union {
196
      uint64_t RegNo;
197
      SpillLoc SpillLocation;
198
      uint64_t Hash;
199
      int64_t Immediate;
200
      const ConstantFP *FPImm;
201
      const ConstantInt *CImm;
202
    } Loc;
203
204
    VarLoc(const MachineInstr &MI, LexicalScopes &LS,
205
          VarLocKind K = InvalidKind)
206
6.39k
        : Var(MI), MI(MI), UVS(MI.getDebugLoc(), LS){
207
6.39k
      static_assert((sizeof(Loc) == sizeof(uint64_t)),
208
6.39k
                    "hash does not cover all members of Loc");
209
6.39k
      assert(MI.isDebugValue() && "not a DBG_VALUE");
210
6.39k
      assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
211
6.39k
      if (int RegNo = isDbgValueDescribedByReg(MI)) {
212
2.14k
        Kind = MI.isDebugEntryValue() ? 
EntryValueKind5
:
RegisterKind2.14k
;
213
2.14k
        Loc.RegNo = RegNo;
214
4.25k
      } else if (MI.getOperand(0).isImm()) {
215
4.24k
        Kind = ImmediateKind;
216
4.24k
        Loc.Immediate = MI.getOperand(0).getImm();
217
4.24k
      } else 
if (9
MI.getOperand(0).isFPImm()9
) {
218
8
        Kind = ImmediateKind;
219
8
        Loc.FPImm = MI.getOperand(0).getFPImm();
220
8
      } else 
if (1
MI.getOperand(0).isCImm()1
) {
221
1
        Kind = ImmediateKind;
222
1
        Loc.CImm = MI.getOperand(0).getCImm();
223
1
      }
224
6.39k
      assert((Kind != ImmediateKind || !MI.isDebugEntryValue()) &&
225
6.39k
             "entry values must be register locations");
226
6.39k
    }
227
228
    /// The constructor for spill locations.
229
    VarLoc(const MachineInstr &MI, unsigned SpillBase, int SpillOffset,
230
           LexicalScopes &LS)
231
21
        : Var(MI), MI(MI), UVS(MI.getDebugLoc(), LS) {
232
21
      assert(MI.isDebugValue() && "not a DBG_VALUE");
233
21
      assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
234
21
      Kind = SpillLocKind;
235
21
      Loc.SpillLocation = {SpillBase, SpillOffset};
236
21
    }
237
238
    // Is the Loc field a constant or constant object?
239
929
    bool isConstant() const { return Kind == ImmediateKind; }
240
241
    /// If this variable is described by a register, return it,
242
    /// otherwise return 0.
243
197k
    unsigned isDescribedByReg() const {
244
197k
      if (Kind == RegisterKind)
245
50.6k
        return Loc.RegNo;
246
146k
      return 0;
247
146k
    }
248
249
    /// Determine whether the lexical scope of this value's debug location
250
    /// dominates MBB.
251
1.39k
    bool dominates(MachineBasicBlock &MBB) const { return UVS.dominates(&MBB); }
252
253
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
254
    LLVM_DUMP_METHOD void dump() const { MI.dump(); }
255
#endif
256
257
0
    bool operator==(const VarLoc &Other) const {
258
0
      return Kind == Other.Kind && Var == Other.Var &&
259
0
             Loc.Hash == Other.Loc.Hash;
260
0
    }
261
262
    /// This operator guarantees that VarLocs are sorted by Variable first.
263
155k
    bool operator<(const VarLoc &Other) const {
264
155k
      return std::tie(Var, Kind, Loc.Hash) <
265
155k
             std::tie(Other.Var, Other.Kind, Other.Loc.Hash);
266
155k
    }
267
  };
268
269
  using DebugParamMap = SmallDenseMap<const DILocalVariable *, MachineInstr *>;
270
  using VarLocMap = UniqueVector<VarLoc>;
271
  using VarLocSet = SparseBitVector<>;
272
  using VarLocInMBB = SmallDenseMap<const MachineBasicBlock *, VarLocSet>;
273
  struct TransferDebugPair {
274
    MachineInstr *TransferInst;
275
    MachineInstr *DebugInst;
276
  };
277
  using TransferMap = SmallVector<TransferDebugPair, 4>;
278
279
  // Types for recording sets of variable fragments that overlap. For a given
280
  // local variable, we record all other fragments of that variable that could
281
  // overlap it, to reduce search time.
282
  using FragmentOfVar =
283
      std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
284
  using OverlapMap =
285
      DenseMap<FragmentOfVar, SmallVector<DIExpression::FragmentInfo, 1>>;
286
287
  // Helper while building OverlapMap, a map of all fragments seen for a given
288
  // DILocalVariable.
289
  using VarToFragments =
290
      DenseMap<const DILocalVariable *, SmallSet<FragmentInfo, 4>>;
291
292
  /// This holds the working set of currently open ranges. For fast
293
  /// access, this is done both as a set of VarLocIDs, and a map of
294
  /// DebugVariable to recent VarLocID. Note that a DBG_VALUE ends all
295
  /// previous open ranges for the same variable.
296
  class OpenRangesSet {
297
    VarLocSet VarLocs;
298
    SmallDenseMap<DebugVariable, unsigned, 8> Vars;
299
    OverlapMap &OverlappingFragments;
300
301
  public:
302
35.7k
    OpenRangesSet(OverlapMap &_OLapMap) : OverlappingFragments(_OLapMap) {}
303
304
15.3M
    const VarLocSet &getVarLocs() const { return VarLocs; }
305
306
    /// Terminate all open ranges for Var by removing it from the set.
307
    void erase(DebugVariable Var);
308
309
    /// Terminate all open ranges listed in \c KillSet by removing
310
    /// them from the set.
311
2.59M
    void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs) {
312
2.59M
      VarLocs.intersectWithComplement(KillSet);
313
2.59M
      for (unsigned ID : KillSet)
314
528
        Vars.erase(VarLocIDs[ID].Var);
315
2.59M
    }
316
317
    /// Insert a new range into the set.
318
6.42k
    void insert(unsigned VarLocID, DebugVariable Var) {
319
6.42k
      VarLocs.set(VarLocID);
320
6.42k
      Vars.insert({Var, VarLocID});
321
6.42k
    }
322
323
    /// Empty the set.
324
672
    void clear() {
325
672
      VarLocs.clear();
326
672
      Vars.clear();
327
672
    }
328
329
    /// Return whether the set is empty or not.
330
385k
    bool empty() const {
331
385k
      assert(Vars.empty() == VarLocs.empty() && "open ranges are inconsistent");
332
385k
      return VarLocs.empty();
333
385k
    }
334
  };
335
336
  bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF,
337
                          unsigned &Reg);
338
  /// If a given instruction is identified as a spill, return the spill location
339
  /// and set \p Reg to the spilled register.
340
  Optional<VarLoc::SpillLoc> isRestoreInstruction(const MachineInstr &MI,
341
                                                  MachineFunction *MF,
342
                                                  unsigned &Reg);
343
  /// Given a spill instruction, extract the register and offset used to
344
  /// address the spill location in a target independent way.
345
  VarLoc::SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI);
346
  void insertTransferDebugPair(MachineInstr &MI, OpenRangesSet &OpenRanges,
347
                               TransferMap &Transfers, VarLocMap &VarLocIDs,
348
                               unsigned OldVarID, TransferKind Kind,
349
                               unsigned NewReg = 0);
350
351
  void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
352
                          VarLocMap &VarLocIDs);
353
  void transferSpillOrRestoreInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
354
                                  VarLocMap &VarLocIDs, TransferMap &Transfers);
355
  void emitEntryValues(MachineInstr &MI, OpenRangesSet &OpenRanges,
356
                       VarLocMap &VarLocIDs, TransferMap &Transfers,
357
                       DebugParamMap &DebugEntryVals,
358
                       SparseBitVector<> &KillSet);
359
  void transferRegisterCopy(MachineInstr &MI, OpenRangesSet &OpenRanges,
360
                            VarLocMap &VarLocIDs, TransferMap &Transfers);
361
  void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
362
                           VarLocMap &VarLocIDs, TransferMap &Transfers,
363
                           DebugParamMap &DebugEntryVals);
364
  bool transferTerminatorInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
365
                              VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs);
366
367
  bool process(MachineInstr &MI, OpenRangesSet &OpenRanges,
368
               VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
369
               TransferMap &Transfers, DebugParamMap &DebugEntryVals,
370
               bool transferChanges, OverlapMap &OverlapFragments,
371
               VarToFragments &SeenFragments);
372
373
  void accumulateFragmentMap(MachineInstr &MI, VarToFragments &SeenFragments,
374
                             OverlapMap &OLapMap);
375
376
  bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
377
            const VarLocMap &VarLocIDs,
378
            SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
379
            SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks);
380
381
  bool ExtendRanges(MachineFunction &MF);
382
383
public:
384
  static char ID;
385
386
  /// Default construct and initialize the pass.
387
  LiveDebugValues();
388
389
  /// Tell the pass manager which passes we depend on and what
390
  /// information we preserve.
391
  void getAnalysisUsage(AnalysisUsage &AU) const override;
392
393
35.3k
  MachineFunctionProperties getRequiredProperties() const override {
394
35.3k
    return MachineFunctionProperties().set(
395
35.3k
        MachineFunctionProperties::Property::NoVRegs);
396
35.3k
  }
397
398
  /// Print to ostream with a message.
399
  void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V,
400
                        const VarLocMap &VarLocIDs, const char *msg,
401
                        raw_ostream &Out) const;
402
403
  /// Calculate the liveness information for the given machine function.
404
  bool runOnMachineFunction(MachineFunction &MF) override;
405
};
406
407
} // end anonymous namespace
408
409
namespace llvm {
410
411
template <> struct DenseMapInfo<LiveDebugValues::DebugVariable> {
412
  using DV = LiveDebugValues::DebugVariable;
413
  using OptFragmentInfo = LiveDebugValues::OptFragmentInfo;
414
  using FragmentInfo = LiveDebugValues::FragmentInfo;
415
416
  // Empty key: no key should be generated that has no DILocalVariable.
417
98.2k
  static inline DV getEmptyKey() {
418
98.2k
    return DV(nullptr, OptFragmentInfo(), nullptr);
419
98.2k
  }
420
421
  // Difference in tombstone is that the Optional is meaningful
422
57.0k
  static inline DV getTombstoneKey() {
423
57.0k
    return DV(nullptr, OptFragmentInfo({0, 0}), nullptr);
424
57.0k
  }
425
426
19.6k
  static unsigned getHashValue(const DV &D) {
427
19.6k
    unsigned HV = 0;
428
19.6k
    const OptFragmentInfo &Fragment = D.getFragment();
429
19.6k
    if (Fragment)
430
14.6k
      HV = DenseMapInfo<FragmentInfo>::getHashValue(*Fragment);
431
19.6k
432
19.6k
    return hash_combine(D.getVar(), HV, D.getInlinedAt());
433
19.6k
  }
434
435
6.00M
  static bool isEqual(const DV &A, const DV &B) { return A == B; }
436
};
437
438
} // namespace llvm
439
440
//===----------------------------------------------------------------------===//
441
//            Implementation
442
//===----------------------------------------------------------------------===//
443
444
const DIExpression::FragmentInfo
445
    LiveDebugValues::DebugVariable::DefaultFragment = {
446
        std::numeric_limits<uint64_t>::max(),
447
        std::numeric_limits<uint64_t>::min()};
448
449
char LiveDebugValues::ID = 0;
450
451
char &llvm::LiveDebugValuesID = LiveDebugValues::ID;
452
453
INITIALIZE_PASS(LiveDebugValues, DEBUG_TYPE, "Live DEBUG_VALUE analysis",
454
                false, false)
455
456
/// Default construct and initialize the pass.
457
35.6k
LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
458
35.6k
  initializeLiveDebugValuesPass(*PassRegistry::getPassRegistry());
459
35.6k
}
460
461
/// Tell the pass manager which passes we depend on and what information we
462
/// preserve.
463
35.3k
void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const {
464
35.3k
  AU.setPreservesCFG();
465
35.3k
  MachineFunctionPass::getAnalysisUsage(AU);
466
35.3k
}
467
468
/// Erase a variable from the set of open ranges, and additionally erase any
469
/// fragments that may overlap it.
470
6.54k
void LiveDebugValues::OpenRangesSet::erase(DebugVariable Var) {
471
6.54k
  // Erasure helper.
472
6.55k
  auto DoErase = [this](DebugVariable VarToErase) {
473
6.55k
    auto It = Vars.find(VarToErase);
474
6.55k
    if (It != Vars.end()) {
475
440
      unsigned ID = It->second;
476
440
      VarLocs.reset(ID);
477
440
      Vars.erase(It);
478
440
    }
479
6.55k
  };
480
6.54k
481
6.54k
  // Erase the variable/fragment that ends here.
482
6.54k
  DoErase(Var);
483
6.54k
484
6.54k
  // Extract the fragment. Interpret an empty fragment as one that covers all
485
6.54k
  // possible bits.
486
6.54k
  FragmentInfo ThisFragment = Var.getFragmentDefault();
487
6.54k
488
6.54k
  // There may be fragments that overlap the designated fragment. Look them up
489
6.54k
  // in the pre-computed overlap map, and erase them too.
490
6.54k
  auto MapIt = OverlappingFragments.find({Var.getVar(), ThisFragment});
491
6.54k
  if (MapIt != OverlappingFragments.end()) {
492
1.68k
    for (auto Fragment : MapIt->second) {
493
11
      LiveDebugValues::OptFragmentInfo FragmentHolder;
494
11
      if (!DebugVariable::isFragmentDefault(Fragment))
495
8
        FragmentHolder = LiveDebugValues::OptFragmentInfo(Fragment);
496
11
      DoErase({Var.getVar(), FragmentHolder, Var.getInlinedAt()});
497
11
    }
498
1.68k
  }
499
6.54k
}
500
501
//===----------------------------------------------------------------------===//
502
//            Debug Range Extension Implementation
503
//===----------------------------------------------------------------------===//
504
505
#ifndef NDEBUG
506
void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF,
507
                                       const VarLocInMBB &V,
508
                                       const VarLocMap &VarLocIDs,
509
                                       const char *msg,
510
                                       raw_ostream &Out) const {
511
  Out << '\n' << msg << '\n';
512
  for (const MachineBasicBlock &BB : MF) {
513
    const VarLocSet &L = V.lookup(&BB);
514
    if (L.empty())
515
      continue;
516
    Out << "MBB: " << BB.getNumber() << ":\n";
517
    for (unsigned VLL : L) {
518
      const VarLoc &VL = VarLocIDs[VLL];
519
      Out << " Var: " << VL.Var.getVar()->getName();
520
      Out << " MI: ";
521
      VL.dump();
522
    }
523
  }
524
  Out << "\n";
525
}
526
#endif
527
528
LiveDebugValues::VarLoc::SpillLoc
529
105
LiveDebugValues::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
530
105
  assert(MI.hasOneMemOperand() &&
531
105
         "Spill instruction does not have exactly one memory operand?");
532
105
  auto MMOI = MI.memoperands_begin();
533
105
  const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
534
105
  assert(PVal->kind() == PseudoSourceValue::FixedStack &&
535
105
         "Inconsistent memory operand in spill instruction");
536
105
  int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
537
105
  const MachineBasicBlock *MBB = MI.getParent();
538
105
  unsigned Reg;
539
105
  int Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg);
540
105
  return {Reg, Offset};
541
105
}
542
543
/// End all previous ranges related to @MI and start a new range from @MI
544
/// if it is a DBG_VALUE instr.
545
void LiveDebugValues::transferDebugValue(const MachineInstr &MI,
546
                                         OpenRangesSet &OpenRanges,
547
2.59M
                                         VarLocMap &VarLocIDs) {
548
2.59M
  if (!MI.isDebugValue())
549
2.58M
    return;
550
6.47k
  const DILocalVariable *Var = MI.getDebugVariable();
551
6.47k
  const DIExpression *Expr = MI.getDebugExpression();
552
6.47k
  const DILocation *DebugLoc = MI.getDebugLoc();
553
6.47k
  const DILocation *InlinedAt = DebugLoc->getInlinedAt();
554
6.47k
  assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
555
6.47k
         "Expected inlined-at fields to agree");
556
6.47k
557
6.47k
  // End all previous ranges of Var.
558
6.47k
  DebugVariable V(Var, Expr, InlinedAt);
559
6.47k
  OpenRanges.erase(V);
560
6.47k
561
6.47k
  // Add the VarLoc to OpenRanges from this DBG_VALUE.
562
6.47k
  unsigned ID;
563
6.47k
  if (isDbgValueDescribedByReg(MI) || 
MI.getOperand(0).isImm()4.35k
||
564
6.47k
      
MI.getOperand(0).isFPImm()105
||
MI.getOperand(0).isCImm()97
) {
565
6.38k
    // Use normal VarLoc constructor for registers and immediates.
566
6.38k
    VarLoc VL(MI, LS);
567
6.38k
    ID = VarLocIDs.insert(VL);
568
6.38k
    OpenRanges.insert(ID, VL.Var);
569
6.38k
  } else 
if (96
MI.hasOneMemOperand()96
) {
570
0
    // It's a stack spill -- fetch spill base and offset.
571
0
    VarLoc::SpillLoc SpillLocation = extractSpillBaseRegAndOffset(MI);
572
0
    VarLoc VL(MI, SpillLocation.SpillBase, SpillLocation.SpillOffset, LS);
573
0
    ID = VarLocIDs.insert(VL);
574
0
    OpenRanges.insert(ID, VL.Var);
575
96
  } else {
576
96
    // This must be an undefined location. We should leave OpenRanges closed.
577
96
    assert(MI.getOperand(0).isReg() && MI.getOperand(0).getReg() == 0 &&
578
96
           "Unexpected non-undef DBG_VALUE encountered");
579
96
  }
580
6.47k
}
581
582
void LiveDebugValues::emitEntryValues(MachineInstr &MI,
583
                                      OpenRangesSet &OpenRanges,
584
                                      VarLocMap &VarLocIDs,
585
                                      TransferMap &Transfers,
586
                                      DebugParamMap &DebugEntryVals,
587
14
                                      SparseBitVector<> &KillSet) {
588
14
  MachineFunction *MF = MI.getParent()->getParent();
589
14
  for (unsigned ID : KillSet) {
590
5
    if (!VarLocIDs[ID].Var.getVar()->isParameter())
591
0
      continue;
592
5
593
5
    const MachineInstr *CurrDebugInstr = &VarLocIDs[ID].MI;
594
5
595
5
    // If parameter's DBG_VALUE is not in the map that means we can't
596
5
    // generate parameter's entry value.
597
5
    if (!DebugEntryVals.count(CurrDebugInstr->getDebugVariable()))
598
0
      continue;
599
5
600
5
    auto ParamDebugInstr = DebugEntryVals[CurrDebugInstr->getDebugVariable()];
601
5
    DIExpression *NewExpr = DIExpression::prepend(
602
5
        ParamDebugInstr->getDebugExpression(), DIExpression::EntryValue);
603
5
    MachineInstr *EntryValDbgMI =
604
5
        BuildMI(*MF, ParamDebugInstr->getDebugLoc(), ParamDebugInstr->getDesc(),
605
5
                ParamDebugInstr->isIndirectDebugValue(),
606
5
                ParamDebugInstr->getOperand(0).getReg(),
607
5
                ParamDebugInstr->getDebugVariable(), NewExpr);
608
5
609
5
    if (ParamDebugInstr->isIndirectDebugValue())
610
0
      EntryValDbgMI->getOperand(1).setImm(
611
0
          ParamDebugInstr->getOperand(1).getImm());
612
5
613
5
    Transfers.push_back({&MI, EntryValDbgMI});
614
5
    VarLoc VL(*EntryValDbgMI, LS);
615
5
    unsigned EntryValLocID = VarLocIDs.insert(VL);
616
5
    OpenRanges.insert(EntryValLocID, VL.Var);
617
5
  }
618
14
}
619
620
/// Create new TransferDebugPair and insert it in \p Transfers. The VarLoc
621
/// with \p OldVarID should be deleted form \p OpenRanges and replaced with
622
/// new VarLoc. If \p NewReg is different than default zero value then the
623
/// new location will be register location created by the copy like instruction,
624
/// otherwise it is variable's location on the stack.
625
void LiveDebugValues::insertTransferDebugPair(
626
    MachineInstr &MI, OpenRangesSet &OpenRanges, TransferMap &Transfers,
627
    VarLocMap &VarLocIDs, unsigned OldVarID, TransferKind Kind,
628
33
    unsigned NewReg) {
629
33
  const MachineInstr *DebugInstr = &VarLocIDs[OldVarID].MI;
630
33
  MachineFunction *MF = MI.getParent()->getParent();
631
33
  MachineInstr *NewDebugInstr;
632
33
633
33
  auto ProcessVarLoc = [&MI, &OpenRanges, &Transfers, &DebugInstr,
634
33
                        &VarLocIDs](VarLoc &VL, MachineInstr *NewDebugInstr) {
635
33
    unsigned LocId = VarLocIDs.insert(VL);
636
33
637
33
    // Close this variable's previous location range.
638
33
    DebugVariable V(*DebugInstr);
639
33
    OpenRanges.erase(V);
640
33
641
33
    OpenRanges.insert(LocId, VL.Var);
642
33
    // The newly created DBG_VALUE instruction NewDebugInstr must be inserted
643
33
    // after MI. Keep track of the pairing.
644
33
    TransferDebugPair MIP = {&MI, NewDebugInstr};
645
33
    Transfers.push_back(MIP);
646
33
  };
647
33
648
33
  // End all previous ranges of Var.
649
33
  OpenRanges.erase(VarLocIDs[OldVarID].Var);
650
33
  switch (Kind) {
651
33
  case TransferKind::TransferCopy: {
652
9
    assert(NewReg &&
653
9
           "No register supplied when handling a copy of a debug value");
654
9
    // Create a DBG_VALUE instruction to describe the Var in its new
655
9
    // register location.
656
9
    NewDebugInstr = BuildMI(
657
9
        *MF, DebugInstr->getDebugLoc(), DebugInstr->getDesc(),
658
9
        DebugInstr->isIndirectDebugValue(), NewReg,
659
9
        DebugInstr->getDebugVariable(), DebugInstr->getDebugExpression());
660
9
    if (DebugInstr->isIndirectDebugValue())
661
0
      NewDebugInstr->getOperand(1).setImm(DebugInstr->getOperand(1).getImm());
662
9
    VarLoc VL(*NewDebugInstr, LS);
663
9
    ProcessVarLoc(VL, NewDebugInstr);
664
9
    LLVM_DEBUG(dbgs() << "Creating DBG_VALUE inst for register copy: ";
665
9
               NewDebugInstr->print(dbgs(), /*IsStandalone*/false,
666
9
                                    /*SkipOpers*/false, /*SkipDebugLoc*/false,
667
9
                                    /*AddNewLine*/true, TII));
668
9
    return;
669
33
  }
670
33
  case TransferKind::TransferSpill: {
671
21
    // Create a DBG_VALUE instruction to describe the Var in its spilled
672
21
    // location.
673
21
    VarLoc::SpillLoc SpillLocation = extractSpillBaseRegAndOffset(MI);
674
21
    auto *SpillExpr = DIExpression::prepend(DebugInstr->getDebugExpression(),
675
21
                                            DIExpression::ApplyOffset,
676
21
                                            SpillLocation.SpillOffset);
677
21
    NewDebugInstr = BuildMI(
678
21
        *MF, DebugInstr->getDebugLoc(), DebugInstr->getDesc(), true,
679
21
        SpillLocation.SpillBase, DebugInstr->getDebugVariable(), SpillExpr);
680
21
    VarLoc VL(*NewDebugInstr, SpillLocation.SpillBase,
681
21
              SpillLocation.SpillOffset, LS);
682
21
    ProcessVarLoc(VL, NewDebugInstr);
683
21
    LLVM_DEBUG(dbgs() << "Creating DBG_VALUE inst for spill: ";
684
21
               NewDebugInstr->print(dbgs(), /*IsStandalone*/false,
685
21
                                    /*SkipOpers*/false, /*SkipDebugLoc*/false,
686
21
                                    /*AddNewLine*/true, TII));
687
21
    return;
688
33
  }
689
33
  case TransferKind::TransferRestore: {
690
3
    assert(NewReg &&
691
3
           "No register supplied when handling a restore of a debug value");
692
3
    MachineFunction *MF = MI.getMF();
693
3
    DIBuilder DIB(*const_cast<Function &>(MF->getFunction()).getParent());
694
3
    NewDebugInstr =
695
3
        BuildMI(*MF, DebugInstr->getDebugLoc(), DebugInstr->getDesc(), false,
696
3
                NewReg, DebugInstr->getDebugVariable(), DIB.createExpression());
697
3
    VarLoc VL(*NewDebugInstr, LS);
698
3
    ProcessVarLoc(VL, NewDebugInstr);
699
3
    LLVM_DEBUG(dbgs() << "Creating DBG_VALUE inst for register restore: ";
700
3
               NewDebugInstr->print(dbgs(), /*IsStandalone*/false,
701
3
                                    /*SkipOpers*/false, /*SkipDebugLoc*/false,
702
3
                                    /*AddNewLine*/true, TII));
703
3
    return;
704
0
  }
705
0
  }
706
0
  llvm_unreachable("Invalid transfer kind");
707
0
}
708
709
/// A definition of a register may mark the end of a range.
710
void LiveDebugValues::transferRegisterDef(
711
    MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs,
712
2.59M
    TransferMap &Transfers, DebugParamMap &DebugEntryVals) {
713
2.59M
  MachineFunction *MF = MI.getMF();
714
2.59M
  const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
715
2.59M
  unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
716
2.59M
  SparseBitVector<> KillSet;
717
10.7M
  for (const MachineOperand &MO : MI.operands()) {
718
10.7M
    // Determine whether the operand is a register def.  Assume that call
719
10.7M
    // instructions never clobber SP, because some backends (e.g., AArch64)
720
10.7M
    // never list SP in the regmask.
721
10.7M
    if (MO.isReg() && 
MO.isDef()7.38M
&&
MO.getReg()2.71M
&&
722
10.7M
        
TRI->isPhysicalRegister(MO.getReg())2.71M
&&
723
10.7M
        
!(2.71M
MI.isCall()2.71M
&&
MO.getReg() == SP482k
)) {
724
2.51M
      // Remove ranges of all aliased registers.
725
17.7M
      for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); 
++RAI15.1M
)
726
15.1M
        for (unsigned ID : OpenRanges.getVarLocs())
727
192k
          if (VarLocIDs[ID].isDescribedByReg() == *RAI)
728
860
            KillSet.set(ID);
729
8.20M
    } else if (MO.isRegMask()) {
730
203k
      // Remove ranges of all clobbered registers. Register masks don't usually
731
203k
      // list SP as preserved.  While the debug info may be off for an
732
203k
      // instruction or two around callee-cleanup calls, transferring the
733
203k
      // DEBUG_VALUE across the call is still a better user experience.
734
203k
      for (unsigned ID : OpenRanges.getVarLocs()) {
735
4.72k
        unsigned Reg = VarLocIDs[ID].isDescribedByReg();
736
4.72k
        if (Reg && 
Reg != SP643
&&
MO.clobbersPhysReg(Reg)475
)
737
130
          KillSet.set(ID);
738
4.72k
      }
739
203k
    }
740
10.7M
  }
741
2.59M
  OpenRanges.erase(KillSet, VarLocIDs);
742
2.59M
743
2.59M
  if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) {
744
2.59M
    auto &TM = TPC->getTM<TargetMachine>();
745
2.59M
    if (TM.Options.EnableDebugEntryValues)
746
14
      emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, DebugEntryVals,
747
14
                      KillSet);
748
2.59M
  }
749
2.59M
}
750
751
/// Decide if @MI is a spill instruction and return true if it is. We use 2
752
/// criteria to make this decision:
753
/// - Is this instruction a store to a spill slot?
754
/// - Is there a register operand that is both used and killed?
755
/// TODO: Store optimization can fold spills into other stores (including
756
/// other spills). We do not handle this yet (more than one memory operand).
757
bool LiveDebugValues::isSpillInstruction(const MachineInstr &MI,
758
2.94k
                                         MachineFunction *MF, unsigned &Reg) {
759
2.94k
  SmallVector<const MachineMemOperand*, 1> Accesses;
760
2.94k
761
2.94k
  // TODO: Handle multiple stores folded into one.
762
2.94k
  if (!MI.hasOneMemOperand())
763
2.55k
    return false;
764
383
765
383
  if (!MI.getSpillSize(TII) && 
!MI.getFoldedSpillSize(TII)313
)
766
297
    return false; // This is not a spill instruction, since no valid size was
767
86
                  // returned from either function.
768
86
769
735
  
auto isKilledReg = [&](const MachineOperand MO, unsigned &Reg) 86
{
770
735
    if (!MO.isReg() || 
!MO.isUse()476
) {
771
279
      Reg = 0;
772
279
      return false;
773
279
    }
774
456
    Reg = MO.getReg();
775
456
    return MO.isKill();
776
456
  };
777
86
778
421
  for (const MachineOperand &MO : MI.operands()) {
779
421
    // In a spill instruction generated by the InlineSpiller the spilled
780
421
    // register has its kill flag set.
781
421
    if (isKilledReg(MO, Reg))
782
84
      return true;
783
337
    if (Reg != 0) {
784
69
      // Check whether next instruction kills the spilled register.
785
69
      // FIXME: Current solution does not cover search for killed register in
786
69
      // bundles and instructions further down the chain.
787
69
      auto NextI = std::next(MI.getIterator());
788
69
      // Skip next instruction that points to basic block end iterator.
789
69
      if (MI.getParent()->end() == NextI)
790
11
        continue;
791
58
      unsigned RegNext;
792
314
      for (const MachineOperand &MONext : NextI->operands()) {
793
314
        // Return true if we came across the register from the
794
314
        // previous spill instruction that is killed in NextI.
795
314
        if (isKilledReg(MONext, RegNext) && 
RegNext == Reg41
)
796
1
          return true;
797
314
      }
798
58
    }
799
337
  }
800
86
  // Return false if we didn't find spilled register.
801
86
  
return false1
;
802
86
}
803
804
Optional<LiveDebugValues::VarLoc::SpillLoc>
805
LiveDebugValues::isRestoreInstruction(const MachineInstr &MI,
806
2.85k
                                      MachineFunction *MF, unsigned &Reg) {
807
2.85k
  if (!MI.hasOneMemOperand())
808
2.55k
    return None;
809
298
810
298
  // FIXME: Handle folded restore instructions with more than one memory
811
298
  // operand.
812
298
  if (MI.getRestoreSize(TII)) {
813
84
    Reg = MI.getOperand(0).getReg();
814
84
    return extractSpillBaseRegAndOffset(MI);
815
84
  }
816
214
  return None;
817
214
}
818
819
/// A spilled register may indicate that we have to end the current range of
820
/// a variable and create a new one for the spill location.
821
/// A restored register may indicate the reverse situation.
822
/// We don't want to insert any instructions in process(), so we just create
823
/// the DBG_VALUE without inserting it and keep track of it in \p Transfers.
824
/// It will be inserted into the BB when we're done iterating over the
825
/// instructions.
826
void LiveDebugValues::transferSpillOrRestoreInst(MachineInstr &MI,
827
                                                 OpenRangesSet &OpenRanges,
828
                                                 VarLocMap &VarLocIDs,
829
2.94k
                                                 TransferMap &Transfers) {
830
2.94k
  MachineFunction *MF = MI.getMF();
831
2.94k
  TransferKind TKind;
832
2.94k
  unsigned Reg;
833
2.94k
  Optional<VarLoc::SpillLoc> Loc;
834
2.94k
835
2.94k
  LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump(););
836
2.94k
837
2.94k
  if (isSpillInstruction(MI, MF, Reg)) {
838
85
    TKind = TransferKind::TransferSpill;
839
85
    LLVM_DEBUG(dbgs() << "Recognized as spill: "; MI.dump(););
840
85
    LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI)
841
85
                      << "\n");
842
2.85k
  } else {
843
2.85k
    if (!(Loc = isRestoreInstruction(MI, MF, Reg)))
844
2.77k
      return;
845
84
    TKind = TransferKind::TransferRestore;
846
84
    LLVM_DEBUG(dbgs() << "Recognized as restore: "; MI.dump(););
847
84
    LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI)
848
84
                      << "\n");
849
84
  }
850
2.94k
  // Check if the register or spill location is the location of a debug value.
851
2.94k
  
for (unsigned ID : OpenRanges.getVarLocs())169
{
852
423
    if (TKind == TransferKind::TransferSpill &&
853
423
        
VarLocIDs[ID].isDescribedByReg() == Reg228
) {
854
21
      LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '('
855
21
                        << VarLocIDs[ID].Var.getVar()->getName() << ")\n");
856
402
    } else if (TKind == TransferKind::TransferRestore &&
857
402
               
VarLocIDs[ID].Loc.SpillLocation == *Loc195
) {
858
3
      LLVM_DEBUG(dbgs() << "Restoring Register " << printReg(Reg, TRI) << '('
859
3
                        << VarLocIDs[ID].Var.getVar()->getName() << ")\n");
860
3
    } else
861
399
      continue;
862
24
    insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID, TKind,
863
24
                            Reg);
864
24
    return;
865
24
  }
866
169
}
867
868
/// If \p MI is a register copy instruction, that copies a previously tracked
869
/// value from one register to another register that is callee saved, we
870
/// create new DBG_VALUE instruction  described with copy destination register.
871
void LiveDebugValues::transferRegisterCopy(MachineInstr &MI,
872
                                           OpenRangesSet &OpenRanges,
873
                                           VarLocMap &VarLocIDs,
874
2.94k
                                           TransferMap &Transfers) {
875
2.94k
  const MachineOperand *SrcRegOp, *DestRegOp;
876
2.94k
877
2.94k
  if (!TII->isCopyInstr(MI, SrcRegOp, DestRegOp) || 
!SrcRegOp->isKill()202
||
878
2.94k
      
!DestRegOp->isDef()79
)
879
2.86k
    return;
880
79
881
79
  auto isCalleSavedReg = [&](unsigned Reg) {
882
663
    for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); 
++RAI584
)
883
595
      if (CalleeSavedRegs.test(*RAI))
884
11
        return true;
885
79
    
return false68
;
886
79
  };
887
79
888
79
  unsigned SrcReg = SrcRegOp->getReg();
889
79
  unsigned DestReg = DestRegOp->getReg();
890
79
891
79
  // We want to recognize instructions where destination register is callee
892
79
  // saved register. If register that could be clobbered by the call is
893
79
  // included, there would be a great chance that it is going to be clobbered
894
79
  // soon. It is more likely that previous register location, which is callee
895
79
  // saved, is going to stay unclobbered longer, even if it is killed.
896
79
  if (!isCalleSavedReg(DestReg))
897
68
    return;
898
11
899
23
  
for (unsigned ID : OpenRanges.getVarLocs())11
{
900
23
    if (VarLocIDs[ID].isDescribedByReg() == SrcReg) {
901
9
      insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID,
902
9
                              TransferKind::TransferCopy, DestReg);
903
9
      return;
904
9
    }
905
23
  }
906
11
}
907
908
/// Terminate all open ranges at the end of the current basic block.
909
bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
910
                                             OpenRangesSet &OpenRanges,
911
                                             VarLocInMBB &OutLocs,
912
2.59M
                                             const VarLocMap &VarLocIDs) {
913
2.59M
  bool Changed = false;
914
2.59M
  const MachineBasicBlock *CurMBB = MI.getParent();
915
2.59M
  if (!(MI.isTerminator() || 
(&MI == &CurMBB->back())2.28M
))
916
2.20M
    return false;
917
385k
918
385k
  if (OpenRanges.empty())
919
385k
    return false;
920
672
921
672
  LLVM_DEBUG(for (unsigned ID
922
672
                  : OpenRanges.getVarLocs()) {
923
672
    // Copy OpenRanges to OutLocs, if not already present.
924
672
    dbgs() << "Add to OutLocs in MBB #" << CurMBB->getNumber() << ":  ";
925
672
    VarLocIDs[ID].dump();
926
672
  });
927
672
  VarLocSet &VLS = OutLocs[CurMBB];
928
672
  Changed = VLS |= OpenRanges.getVarLocs();
929
672
  // New OutLocs set may be different due to spill, restore or register
930
672
  // copy instruction processing.
931
672
  if (Changed)
932
645
    VLS = OpenRanges.getVarLocs();
933
672
  OpenRanges.clear();
934
672
  return Changed;
935
672
}
936
937
/// Accumulate a mapping between each DILocalVariable fragment and other
938
/// fragments of that DILocalVariable which overlap. This reduces work during
939
/// the data-flow stage from "Find any overlapping fragments" to "Check if the
940
/// known-to-overlap fragments are present".
941
/// \param MI A previously unprocessed DEBUG_VALUE instruction to analyze for
942
///           fragment usage.
943
/// \param SeenFragments Map from DILocalVariable to all fragments of that
944
///           Variable which are known to exist.
945
/// \param OverlappingFragments The overlap map being constructed, from one
946
///           Var/Fragment pair to a vector of fragments known to overlap.
947
void LiveDebugValues::accumulateFragmentMap(MachineInstr &MI,
948
                                            VarToFragments &SeenFragments,
949
5.33k
                                            OverlapMap &OverlappingFragments) {
950
5.33k
  DebugVariable MIVar(MI);
951
5.33k
  FragmentInfo ThisFragment = MIVar.getFragmentDefault();
952
5.33k
953
5.33k
  // If this is the first sighting of this variable, then we are guaranteed
954
5.33k
  // there are currently no overlapping fragments either. Initialize the set
955
5.33k
  // of seen fragments, record no overlaps for the current one, and return.
956
5.33k
  auto SeenIt = SeenFragments.find(MIVar.getVar());
957
5.33k
  if (SeenIt == SeenFragments.end()) {
958
791
    SmallSet<FragmentInfo, 4> OneFragment;
959
791
    OneFragment.insert(ThisFragment);
960
791
    SeenFragments.insert({MIVar.getVar(), OneFragment});
961
791
962
791
    OverlappingFragments.insert({{MIVar.getVar(), ThisFragment}, {}});
963
791
    return;
964
791
  }
965
4.54k
966
4.54k
  // If this particular Variable/Fragment pair already exists in the overlap
967
4.54k
  // map, it has already been accounted for.
968
4.54k
  auto IsInOLapMap =
969
4.54k
      OverlappingFragments.insert({{MIVar.getVar(), ThisFragment}, {}});
970
4.54k
  if (!IsInOLapMap.second)
971
476
    return;
972
4.06k
973
4.06k
  auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;
974
4.06k
  auto &AllSeenFragments = SeenIt->second;
975
4.06k
976
4.06k
  // Otherwise, examine all other seen fragments for this variable, with "this"
977
4.06k
  // fragment being a previously unseen fragment. Record any pair of
978
4.06k
  // overlapping fragments.
979
7.99M
  for (auto &ASeenFragment : AllSeenFragments) {
980
7.99M
    // Does this previously seen fragment overlap?
981
7.99M
    if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) {
982
5
      // Yes: Mark the current fragment as being overlapped.
983
5
      ThisFragmentsOverlaps.push_back(ASeenFragment);
984
5
      // Mark the previously seen fragment as being overlapped by the current
985
5
      // one.
986
5
      auto ASeenFragmentsOverlaps =
987
5
          OverlappingFragments.find({MIVar.getVar(), ASeenFragment});
988
5
      assert(ASeenFragmentsOverlaps != OverlappingFragments.end() &&
989
5
             "Previously seen var fragment has no vector of overlaps");
990
5
      ASeenFragmentsOverlaps->second.push_back(ThisFragment);
991
5
    }
992
7.99M
  }
993
4.06k
994
4.06k
  AllSeenFragments.insert(ThisFragment);
995
4.06k
}
996
997
/// This routine creates OpenRanges and OutLocs.
998
bool LiveDebugValues::process(MachineInstr &MI, OpenRangesSet &OpenRanges,
999
                              VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
1000
                              TransferMap &Transfers, DebugParamMap &DebugEntryVals,
1001
                              bool transferChanges,
1002
                              OverlapMap &OverlapFragments,
1003
2.59M
                              VarToFragments &SeenFragments) {
1004
2.59M
  bool Changed = false;
1005
2.59M
  transferDebugValue(MI, OpenRanges, VarLocIDs);
1006
2.59M
  transferRegisterDef(MI, OpenRanges, VarLocIDs, Transfers,
1007
2.59M
                      DebugEntryVals);
1008
2.59M
  if (transferChanges) {
1009
2.94k
    transferRegisterCopy(MI, OpenRanges, VarLocIDs, Transfers);
1010
2.94k
    transferSpillOrRestoreInst(MI, OpenRanges, VarLocIDs, Transfers);
1011
2.58M
  } else {
1012
2.58M
    // Build up a map of overlapping fragments on the first run through.
1013
2.58M
    if (MI.isDebugValue())
1014
5.33k
      accumulateFragmentMap(MI, SeenFragments, OverlapFragments);
1015
2.58M
  }
1016
2.59M
  Changed = transferTerminatorInst(MI, OpenRanges, OutLocs, VarLocIDs);
1017
2.59M
  return Changed;
1018
2.59M
}
1019
1020
/// This routine joins the analysis results of all incoming edges in @MBB by
1021
/// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
1022
/// source variable in all the predecessors of @MBB reside in the same location.
1023
bool LiveDebugValues::join(
1024
    MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
1025
    const VarLocMap &VarLocIDs,
1026
    SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
1027
364k
    SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks) {
1028
364k
  LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
1029
364k
  bool Changed = false;
1030
364k
1031
364k
  VarLocSet InLocsT; // Temporary incoming locations.
1032
364k
1033
364k
  // For all predecessors of this MBB, find the set of VarLocs that
1034
364k
  // can be joined.
1035
364k
  int NumVisited = 0;
1036
364k
  for (auto p : MBB.predecessors()) {
1037
337k
    // Ignore unvisited predecessor blocks.  As we are processing
1038
337k
    // the blocks in reverse post-order any unvisited block can
1039
337k
    // be considered to not remove any incoming values.
1040
337k
    if (!Visited.count(p)) {
1041
8.68k
      LLVM_DEBUG(dbgs() << "  ignoring unvisited pred MBB: " << p->getNumber()
1042
8.68k
                        << "\n");
1043
8.68k
      continue;
1044
8.68k
    }
1045
329k
    auto OL = OutLocs.find(p);
1046
329k
    // Join is null in case of empty OutLocs from any of the pred.
1047
329k
    if (OL == OutLocs.end())
1048
328k
      return false;
1049
905
1050
905
    // Just copy over the Out locs to incoming locs for the first visited
1051
905
    // predecessor, and for all other predecessors join the Out locs.
1052
905
    if (!NumVisited)
1053
633
      InLocsT = OL->second;
1054
272
    else
1055
272
      InLocsT &= OL->second;
1056
905
1057
905
    LLVM_DEBUG({
1058
905
      if (!InLocsT.empty()) {
1059
905
        for (auto ID : InLocsT)
1060
905
          dbgs() << "  gathered candidate incoming var: "
1061
905
                 << VarLocIDs[ID].Var.getVar()->getName() << "\n";
1062
905
      }
1063
905
    });
1064
905
1065
905
    NumVisited++;
1066
905
  }
1067
364k
1068
364k
  // Filter out DBG_VALUES that are out of scope.
1069
364k
  VarLocSet KillSet;
1070
36.3k
  bool IsArtificial = ArtificialBlocks.count(&MBB);
1071
36.3k
  if (!IsArtificial) {
1072
35.5k
    for (auto ID : InLocsT) {
1073
1.39k
      if (!VarLocIDs[ID].dominates(MBB)) {
1074
44
        KillSet.set(ID);
1075
44
        LLVM_DEBUG({
1076
44
          auto Name = VarLocIDs[ID].Var.getVar()->getName();
1077
44
          dbgs() << "  killing " << Name << ", it doesn't dominate MBB\n";
1078
44
        });
1079
44
      }
1080
1.39k
    }
1081
35.5k
  }
1082
36.3k
  InLocsT.intersectWithComplement(KillSet);
1083
36.3k
1084
36.3k
  // As we are processing blocks in reverse post-order we
1085
36.3k
  // should have processed at least one predecessor, unless it
1086
36.3k
  // is the entry block which has no predecessor.
1087
36.3k
  assert((NumVisited || MBB.pred_empty()) &&
1088
36.3k
         "Should have processed at least one predecessor");
1089
36.3k
  if (InLocsT.empty())
1090
35.7k
    return false;
1091
586
1092
586
  VarLocSet &ILS = InLocs[&MBB];
1093
586
1094
586
  // Insert DBG_VALUE instructions, if not already inserted.
1095
586
  VarLocSet Diff = InLocsT;
1096
586
  Diff.intersectWithComplement(ILS);
1097
929
  for (auto ID : Diff) {
1098
929
    // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a
1099
929
    // new range is started for the var from the mbb's beginning by inserting
1100
929
    // a new DBG_VALUE. process() will end this range however appropriate.
1101
929
    const VarLoc &DiffIt = VarLocIDs[ID];
1102
929
    const MachineInstr *DebugInstr = &DiffIt.MI;
1103
929
    MachineInstr *MI = nullptr;
1104
929
    if (DiffIt.isConstant()) {
1105
98
      MachineOperand MO(DebugInstr->getOperand(0));
1106
98
      MI = BuildMI(MBB, MBB.instr_begin(), DebugInstr->getDebugLoc(),
1107
98
                   DebugInstr->getDesc(), false, MO,
1108
98
                   DebugInstr->getDebugVariable(),
1109
98
                   DebugInstr->getDebugExpression());
1110
831
    } else {
1111
831
      MI = BuildMI(MBB, MBB.instr_begin(), DebugInstr->getDebugLoc(),
1112
831
                   DebugInstr->getDesc(), DebugInstr->isIndirectDebugValue(),
1113
831
                   DebugInstr->getOperand(0).getReg(),
1114
831
                   DebugInstr->getDebugVariable(),
1115
831
                   DebugInstr->getDebugExpression());
1116
831
      if (DebugInstr->isIndirectDebugValue())
1117
156
        MI->getOperand(1).setImm(DebugInstr->getOperand(1).getImm());
1118
831
    }
1119
929
    LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump(););
1120
929
    ILS.set(ID);
1121
929
    ++NumInserted;
1122
929
    Changed = true;
1123
929
  }
1124
586
  return Changed;
1125
586
}
1126
1127
/// Calculate the liveness information for the given machine function and
1128
/// extend ranges across basic blocks.
1129
35.7k
bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
1130
35.7k
  LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
1131
35.7k
1132
35.7k
  bool Changed = false;
1133
35.7k
  bool OLChanged = false;
1134
35.7k
  bool MBBJoined = false;
1135
35.7k
1136
35.7k
  VarLocMap VarLocIDs;         // Map VarLoc<>unique ID for use in bitvectors.
1137
35.7k
  OverlapMap OverlapFragments; // Map of overlapping variable fragments
1138
35.7k
  OpenRangesSet OpenRanges(OverlapFragments);
1139
35.7k
                              // Ranges that are open until end of bb.
1140
35.7k
  VarLocInMBB OutLocs;        // Ranges that exist beyond bb.
1141
35.7k
  VarLocInMBB InLocs;         // Ranges that are incoming after joining.
1142
35.7k
  TransferMap Transfers;      // DBG_VALUEs associated with spills.
1143
35.7k
1144
35.7k
  VarToFragments SeenFragments;
1145
35.7k
1146
35.7k
  // Blocks which are artificial, i.e. blocks which exclusively contain
1147
35.7k
  // instructions without locations, or with line 0 locations.
1148
35.7k
  SmallPtrSet<const MachineBasicBlock *, 16> ArtificialBlocks;
1149
35.7k
1150
35.7k
  DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
1151
35.7k
  DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
1152
35.7k
  std::priority_queue<unsigned int, std::vector<unsigned int>,
1153
35.7k
                      std::greater<unsigned int>>
1154
35.7k
      Worklist;
1155
35.7k
  std::priority_queue<unsigned int, std::vector<unsigned int>,
1156
35.7k
                      std::greater<unsigned int>>
1157
35.7k
      Pending;
1158
35.7k
1159
35.7k
  enum : bool { dontTransferChanges = false, transferChanges = true };
1160
35.7k
1161
35.7k
  // Besides parameter's modification, check whether a DBG_VALUE is inlined
1162
35.7k
  // in order to deduce whether the variable that it tracks comes from
1163
35.7k
  // a different function. If that is the case we can't track its entry value.
1164
35.7k
  auto IsUnmodifiedFuncParam = [&](const MachineInstr &MI) {
1165
5.04k
    auto *DIVar = MI.getDebugVariable();
1166
5.04k
    return DIVar->isParameter() && 
DIVar->isNotModified()4.66k
&&
1167
5.04k
           
!MI.getDebugLoc()->getInlinedAt()6
;
1168
5.04k
  };
1169
35.7k
1170
35.7k
  const TargetLowering *TLI = MF.getSubtarget().getTargetLowering();
1171
35.7k
  unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
1172
35.7k
  unsigned FP = TRI->getFrameRegister(MF);
1173
35.7k
  auto IsRegOtherThanSPAndFP = [&](const MachineOperand &Op) -> bool {
1174
6
    return Op.isReg() && Op.getReg() != SP && Op.getReg() != FP;
1175
6
  };
1176
35.7k
1177
35.7k
  // Working set of currently collected debug variables mapped to DBG_VALUEs
1178
35.7k
  // representing candidates for production of debug entry values.
1179
35.7k
  DebugParamMap DebugEntryVals;
1180
35.7k
1181
35.7k
  MachineBasicBlock &First_MBB = *(MF.begin());
1182
35.7k
  // Only in the case of entry MBB collect DBG_VALUEs representing
1183
35.7k
  // function parameters in order to generate debug entry values for them.
1184
35.7k
  // Currently, we generate debug entry values only for parameters that are
1185
35.7k
  // unmodified throughout the function and located in a register.
1186
35.7k
  // TODO: Add support for parameters that are described as fragments.
1187
35.7k
  // TODO: Add support for modified arguments that can be expressed
1188
35.7k
  // by using its entry value.
1189
35.7k
  // TODO: Add support for local variables that are expressed in terms of
1190
35.7k
  // parameters entry values.
1191
35.7k
  for (auto &MI : First_MBB)
1192
662k
    if (MI.isDebugValue() && 
IsUnmodifiedFuncParam(MI)5.04k
&&
1193
662k
        
!MI.isIndirectDebugValue()6
&&
IsRegOtherThanSPAndFP(MI.getOperand(0))6
&&
1194
662k
        
!DebugEntryVals.count(MI.getDebugVariable())6
&&
1195
662k
        
!MI.getDebugExpression()->isFragment()5
)
1196
5
      DebugEntryVals[MI.getDebugVariable()] = &MI;
1197
35.7k
1198
35.7k
  // Initialize every mbb with OutLocs.
1199
35.7k
  // We are not looking at any spill instructions during the initial pass
1200
35.7k
  // over the BBs. The LiveDebugVariables pass has already created DBG_VALUE
1201
35.7k
  // instructions for spills of registers that are known to be user variables
1202
35.7k
  // within the BB in which the spill occurs.
1203
364k
  for (auto &MBB : MF) {
1204
2.58M
    for (auto &MI : MBB) {
1205
2.58M
      process(MI, OpenRanges, OutLocs, VarLocIDs, Transfers, DebugEntryVals,
1206
2.58M
              dontTransferChanges, OverlapFragments, SeenFragments);
1207
2.58M
    }
1208
364k
    // Add any entry DBG_VALUE instructions necessitated by parameter
1209
364k
    // clobbering.
1210
364k
    for (auto &TR : Transfers) {
1211
5
      MBB.insertAfter(MachineBasicBlock::iterator(*TR.TransferInst),
1212
5
                     TR.DebugInst);
1213
5
    }
1214
364k
    Transfers.clear();
1215
364k
  }
1216
35.7k
1217
835k
  auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
1218
835k
    if (const DebugLoc &DL = MI.getDebugLoc())
1219
393k
      return DL.getLine() != 0;
1220
442k
    return false;
1221
442k
  };
1222
35.7k
  for (auto &MBB : MF)
1223
364k
    if (none_of(MBB.instrs(), hasNonArtificialLocation))
1224
22.3k
      ArtificialBlocks.insert(&MBB);
1225
35.7k
1226
35.7k
  LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
1227
35.7k
                              "OutLocs after initialization", dbgs()));
1228
35.7k
1229
35.7k
  ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
1230
35.7k
  unsigned int RPONumber = 0;
1231
400k
  for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; 
++RI364k
) {
1232
364k
    OrderToBB[RPONumber] = *RI;
1233
364k
    BBToOrder[*RI] = RPONumber;
1234
364k
    Worklist.push(RPONumber);
1235
364k
    ++RPONumber;
1236
364k
  }
1237
35.7k
  // This is a standard "union of predecessor outs" dataflow problem.
1238
35.7k
  // To solve it, we perform join() and process() using the two worklist method
1239
35.7k
  // until the ranges converge.
1240
35.7k
  // Ranges have converged when both worklists are empty.
1241
35.7k
  SmallPtrSet<const MachineBasicBlock *, 16> Visited;
1242
71.5k
  while (!Worklist.empty() || 
!Pending.empty()35.7k
) {
1243
35.7k
    // We track what is on the pending worklist to avoid inserting the same
1244
35.7k
    // thing twice.  We could avoid this with a custom priority queue, but this
1245
35.7k
    // is probably not worth it.
1246
35.7k
    SmallPtrSet<MachineBasicBlock *, 16> OnPending;
1247
35.7k
    LLVM_DEBUG(dbgs() << "Processing Worklist\n");
1248
400k
    while (!Worklist.empty()) {
1249
364k
      MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
1250
364k
      Worklist.pop();
1251
364k
      MBBJoined =
1252
364k
          join(*MBB, OutLocs, InLocs, VarLocIDs, Visited, ArtificialBlocks);
1253
364k
      Visited.insert(MBB);
1254
364k
      if (MBBJoined) {
1255
365
        MBBJoined = false;
1256
365
        Changed = true;
1257
365
        // Now that we have started to extend ranges across BBs we need to
1258
365
        // examine spill instructions to see whether they spill registers that
1259
365
        // correspond to user variables.
1260
365
        for (auto &MI : *MBB)
1261
2.94k
          OLChanged |=
1262
2.94k
              process(MI, OpenRanges, OutLocs, VarLocIDs, Transfers,
1263
2.94k
                      DebugEntryVals, transferChanges, OverlapFragments,
1264
2.94k
                      SeenFragments);
1265
365
1266
365
        // Add any DBG_VALUE instructions necessitated by spills.
1267
365
        for (auto &TR : Transfers)
1268
33
          MBB->insertAfter(MachineBasicBlock::iterator(*TR.TransferInst),
1269
33
                           TR.DebugInst);
1270
365
        Transfers.clear();
1271
365
1272
365
        LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
1273
365
                                    "OutLocs after propagating", dbgs()));
1274
365
        LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
1275
365
                                    "InLocs after propagating", dbgs()));
1276
365
1277
365
        if (OLChanged) {
1278
293
          OLChanged = false;
1279
293
          for (auto s : MBB->successors())
1280
327
            if (OnPending.insert(s).second) {
1281
238
              Pending.push(BBToOrder[s]);
1282
238
            }
1283
293
        }
1284
365
      }
1285
364k
    }
1286
35.7k
    Worklist.swap(Pending);
1287
35.7k
    // At this point, pending must be empty, since it was just the empty
1288
35.7k
    // worklist
1289
35.7k
    assert(Pending.empty() && "Pending should be empty");
1290
35.7k
  }
1291
35.7k
1292
35.7k
  LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs()));
1293
35.7k
  LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs()));
1294
35.7k
  return Changed;
1295
35.7k
}
1296
1297
492k
bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
1298
492k
  if (!MF.getFunction().getSubprogram())
1299
456k
    // LiveDebugValues will already have removed all DBG_VALUEs.
1300
456k
    return false;
1301
35.7k
1302
35.7k
  // Skip functions from NoDebug compilation units.
1303
35.7k
  if (MF.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
1304
35.7k
      DICompileUnit::NoDebug)
1305
24
    return false;
1306
35.7k
1307
35.7k
  TRI = MF.getSubtarget().getRegisterInfo();
1308
35.7k
  TII = MF.getSubtarget().getInstrInfo();
1309
35.7k
  TFI = MF.getSubtarget().getFrameLowering();
1310
35.7k
  TFI->determineCalleeSaves(MF, CalleeSavedRegs,
1311
35.7k
                            make_unique<RegScavenger>().get());
1312
35.7k
  LS.initialize(MF);
1313
35.7k
1314
35.7k
  bool Changed = ExtendRanges(MF);
1315
35.7k
  return Changed;
1316
35.7k
}