Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/LiveDebugValues.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- LiveDebugValues.cpp - Tracking Debug Value MIs ---------------------===//
2
//
3
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
///
10
/// This pass implements a data flow analysis that propagates debug location
11
/// information by inserting additional DBG_VALUE instructions into the machine
12
/// instruction stream. The pass internally builds debug location liveness
13
/// ranges to determine the points where additional DBG_VALUEs need to be
14
/// inserted.
15
///
16
/// This is a separate pass from DbgValueHistoryCalculator to facilitate
17
/// testing and improve modularity.
18
///
19
//===----------------------------------------------------------------------===//
20
21
#include "llvm/ADT/DenseMap.h"
22
#include "llvm/ADT/PostOrderIterator.h"
23
#include "llvm/ADT/SmallPtrSet.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/MachineModuleInfo.h"
37
#include "llvm/CodeGen/MachineOperand.h"
38
#include "llvm/CodeGen/PseudoSourceValue.h"
39
#include "llvm/IR/DebugInfoMetadata.h"
40
#include "llvm/IR/DebugLoc.h"
41
#include "llvm/IR/Function.h"
42
#include "llvm/IR/Module.h"
43
#include "llvm/MC/MCRegisterInfo.h"
44
#include "llvm/Pass.h"
45
#include "llvm/Support/Casting.h"
46
#include "llvm/Support/Compiler.h"
47
#include "llvm/Support/Debug.h"
48
#include "llvm/Support/raw_ostream.h"
49
#include "llvm/Target/TargetFrameLowering.h"
50
#include "llvm/Target/TargetInstrInfo.h"
51
#include "llvm/Target/TargetLowering.h"
52
#include "llvm/Target/TargetRegisterInfo.h"
53
#include "llvm/Target/TargetSubtargetInfo.h"
54
#include <algorithm>
55
#include <cassert>
56
#include <cstdint>
57
#include <functional>
58
#include <queue>
59
#include <utility>
60
#include <vector>
61
62
using namespace llvm;
63
64
#define DEBUG_TYPE "livedebugvalues"
65
66
STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
67
68
// \brief If @MI is a DBG_VALUE with debug value described by a defined
69
// register, returns the number of this register. In the other case, returns 0.
70
3.46k
static unsigned isDbgValueDescribedByReg(const MachineInstr &MI) {
71
3.46k
  assert(MI.isDebugValue() && "expected a DBG_VALUE");
72
3.46k
  assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
73
3.46k
  // If location of variable is described using a register (directly
74
3.46k
  // or indirectly), this register is always a first operand.
75
3.46k
  return MI.getOperand(0).isReg() ? 
MI.getOperand(0).getReg()3.33k
:
0127
;
76
3.46k
}
77
78
namespace {
79
80
class LiveDebugValues : public MachineFunctionPass {
81
private:
82
  const TargetRegisterInfo *TRI;
83
  const TargetInstrInfo *TII;
84
  const TargetFrameLowering *TFI;
85
  LexicalScopes LS;
86
87
  /// Keeps track of lexical scopes associated with a user value's source
88
  /// location.
89
  class UserValueScopes {
90
    DebugLoc DL;
91
    LexicalScopes &LS;
92
    SmallPtrSet<const MachineBasicBlock *, 4> LBlocks;
93
94
  public:
95
1.65k
    UserValueScopes(DebugLoc D, LexicalScopes &L) : DL(std::move(D)), LS(L) {}
96
97
    /// Return true if current scope dominates at least one machine
98
    /// instruction in a given machine basic block.
99
1.22k
    bool dominates(MachineBasicBlock *MBB) {
100
1.22k
      if (LBlocks.empty())
101
172
        LS.getMachineBasicBlocks(DL, LBlocks);
102
284
      return LBlocks.count(MBB) != 0 || LS.dominates(DL, MBB);
103
1.22k
    }
104
  };
105
106
  /// Based on std::pair so it can be used as an index into a DenseMap.
107
  using DebugVariableBase =
108
      std::pair<const DILocalVariable *, const DILocation *>;
109
  /// A potentially inlined instance of a variable.
110
  struct DebugVariable : public DebugVariableBase {
111
    DebugVariable(const DILocalVariable *Var, const DILocation *InlinedAt)
112
3.46k
        : DebugVariableBase(Var, InlinedAt) {}
113
114
10.3k
    const DILocalVariable *getVar() const { return this->first; }
115
60
    const DILocation *getInlinedAt() const { return this->second; }
116
117
2.60k
    bool operator<(const DebugVariable &DV) const {
118
2.60k
      if (getVar() == DV.getVar())
119
30
        return getInlinedAt() < DV.getInlinedAt();
120
2.57k
      return getVar() < DV.getVar();
121
2.57k
    }
122
  };
123
124
  /// A pair of debug variable and value location.
125
  struct VarLoc {
126
    const DebugVariable Var;
127
    const MachineInstr &MI; ///< Only used for cloning a new DBG_VALUE.
128
    mutable UserValueScopes UVS;
129
    enum { InvalidKind = 0, RegisterKind } Kind = InvalidKind;
130
131
    /// The value location. Stored separately to avoid repeatedly
132
    /// extracting it from MI.
133
    union {
134
      uint64_t RegNo;
135
      uint64_t Hash;
136
    } Loc;
137
138
    VarLoc(const MachineInstr &MI, LexicalScopes &LS)
139
        : Var(MI.getDebugVariable(), MI.getDebugLoc()->getInlinedAt()), MI(MI),
140
1.65k
          UVS(MI.getDebugLoc(), LS) {
141
1.65k
      static_assert((sizeof(Loc) == sizeof(uint64_t)),
142
1.65k
                    "hash does not cover all members of Loc");
143
1.65k
      assert(MI.isDebugValue() && "not a DBG_VALUE");
144
1.65k
      assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
145
1.65k
      if (int 
RegNo1.65k
= isDbgValueDescribedByReg(MI)) {
146
1.65k
        Kind = RegisterKind;
147
1.65k
        Loc.RegNo = RegNo;
148
1.65k
      }
149
1.65k
    }
150
151
    /// If this variable is described by a register, return it,
152
    /// otherwise return 0.
153
24.0k
    unsigned isDescribedByReg() const {
154
24.0k
      if (Kind == RegisterKind)
155
24.0k
        return Loc.RegNo;
156
0
      return 0;
157
0
    }
158
159
    /// Determine whether the lexical scope of this value's debug location
160
    /// dominates MBB.
161
1.22k
    bool dominates(MachineBasicBlock &MBB) const { return UVS.dominates(&MBB); }
162
163
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
164
    LLVM_DUMP_METHOD void dump() const { MI.dump(); }
165
#endif
166
167
0
    bool operator==(const VarLoc &Other) const {
168
0
      return Var == Other.Var && Loc.Hash == Other.Loc.Hash;
169
0
    }
170
171
    /// This operator guarantees that VarLocs are sorted by Variable first.
172
5.46k
    bool operator<(const VarLoc &Other) const {
173
5.46k
      if (Var == Other.Var)
174
2.86k
        return Loc.Hash < Other.Loc.Hash;
175
2.60k
      return Var < Other.Var;
176
2.60k
    }
177
  };
178
179
  using VarLocMap = UniqueVector<VarLoc>;
180
  using VarLocSet = SparseBitVector<>;
181
  using VarLocInMBB = SmallDenseMap<const MachineBasicBlock *, VarLocSet>;
182
  struct SpillDebugPair {
183
    MachineInstr *SpillInst;
184
    MachineInstr *DebugInst;
185
  };
186
  using SpillMap = SmallVector<SpillDebugPair, 4>;
187
188
  /// This holds the working set of currently open ranges. For fast
189
  /// access, this is done both as a set of VarLocIDs, and a map of
190
  /// DebugVariable to recent VarLocID. Note that a DBG_VALUE ends all
191
  /// previous open ranges for the same variable.
192
  class OpenRangesSet {
193
    VarLocSet VarLocs;
194
    SmallDenseMap<DebugVariableBase, unsigned, 8> Vars;
195
196
  public:
197
1.67M
    const VarLocSet &getVarLocs() const { return VarLocs; }
198
199
    /// Terminate all open ranges for Var by removing it from the set.
200
1.81k
    void erase(DebugVariable Var) {
201
1.81k
      auto It = Vars.find(Var);
202
1.81k
      if (
It != Vars.end()1.81k
) {
203
331
        unsigned ID = It->second;
204
331
        VarLocs.reset(ID);
205
331
        Vars.erase(It);
206
331
      }
207
1.81k
    }
208
209
    /// Terminate all open ranges listed in \c KillSet by removing
210
    /// them from the set.
211
478k
    void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs) {
212
478k
      VarLocs.intersectWithComplement(KillSet);
213
478k
      for (unsigned ID : KillSet)
214
387
        Vars.erase(VarLocIDs[ID].Var);
215
478k
    }
216
217
    /// Insert a new range into the set.
218
1.65k
    void insert(unsigned VarLocID, DebugVariableBase Var) {
219
1.65k
      VarLocs.set(VarLocID);
220
1.65k
      Vars.insert({Var, VarLocID});
221
1.65k
    }
222
223
    /// Empty the set.
224
456
    void clear() {
225
456
      VarLocs.clear();
226
456
      Vars.clear();
227
456
    }
228
229
    /// Return whether the set is empty or not.
230
69.3k
    bool empty() const {
231
69.3k
      assert(Vars.empty() == VarLocs.empty() && "open ranges are inconsistent");
232
69.3k
      return VarLocs.empty();
233
69.3k
    }
234
  };
235
236
  bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF,
237
                          unsigned &Reg);
238
  int extractSpillBaseRegAndOffset(const MachineInstr &MI, unsigned &Reg);
239
240
  void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
241
                          VarLocMap &VarLocIDs);
242
  void transferSpillInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
243
                         VarLocMap &VarLocIDs, SpillMap &Spills);
244
  void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
245
                           const VarLocMap &VarLocIDs);
246
  bool transferTerminatorInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
247
                              VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs);
248
  bool transfer(MachineInstr &MI, OpenRangesSet &OpenRanges,
249
                VarLocInMBB &OutLocs, VarLocMap &VarLocIDs, SpillMap &Spills,
250
                bool transferSpills);
251
252
  bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
253
            const VarLocMap &VarLocIDs,
254
            SmallPtrSet<const MachineBasicBlock *, 16> &Visited);
255
256
  bool ExtendRanges(MachineFunction &MF);
257
258
public:
259
  static char ID;
260
261
  /// Default construct and initialize the pass.
262
  LiveDebugValues();
263
264
  /// Tell the pass manager which passes we depend on and what
265
  /// information we preserve.
266
  void getAnalysisUsage(AnalysisUsage &AU) const override;
267
268
33.2k
  MachineFunctionProperties getRequiredProperties() const override {
269
33.2k
    return MachineFunctionProperties().set(
270
33.2k
        MachineFunctionProperties::Property::NoVRegs);
271
33.2k
  }
272
273
  /// Print to ostream with a message.
274
  void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V,
275
                        const VarLocMap &VarLocIDs, const char *msg,
276
                        raw_ostream &Out) const;
277
278
  /// Calculate the liveness information for the given machine function.
279
  bool runOnMachineFunction(MachineFunction &MF) override;
280
};
281
282
} // end anonymous namespace
283
284
//===----------------------------------------------------------------------===//
285
//            Implementation
286
//===----------------------------------------------------------------------===//
287
288
char LiveDebugValues::ID = 0;
289
290
char &llvm::LiveDebugValuesID = LiveDebugValues::ID;
291
292
INITIALIZE_PASS(LiveDebugValues, DEBUG_TYPE, "Live DEBUG_VALUE analysis",
293
                false, false)
294
295
/// Default construct and initialize the pass.
296
33.3k
LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
297
33.3k
  initializeLiveDebugValuesPass(*PassRegistry::getPassRegistry());
298
33.3k
}
299
300
/// Tell the pass manager which passes we depend on and what information we
301
/// preserve.
302
33.2k
void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const {
303
33.2k
  AU.setPreservesCFG();
304
33.2k
  MachineFunctionPass::getAnalysisUsage(AU);
305
33.2k
}
306
307
//===----------------------------------------------------------------------===//
308
//            Debug Range Extension Implementation
309
//===----------------------------------------------------------------------===//
310
311
#ifndef NDEBUG
312
void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF,
313
                                       const VarLocInMBB &V,
314
                                       const VarLocMap &VarLocIDs,
315
                                       const char *msg,
316
                                       raw_ostream &Out) const {
317
  Out << '\n' << msg << '\n';
318
  for (const MachineBasicBlock &BB : MF) {
319
    const auto &L = V.lookup(&BB);
320
    Out << "MBB: " << BB.getName() << ":\n";
321
    for (unsigned VLL : L) {
322
      const VarLoc &VL = VarLocIDs[VLL];
323
      Out << " Var: " << VL.Var.getVar()->getName();
324
      Out << " MI: ";
325
      VL.dump();
326
    }
327
  }
328
  Out << "\n";
329
}
330
#endif
331
332
/// Given a spill instruction, extract the register and offset used to
333
/// address the spill location in a target independent way.
334
int LiveDebugValues::extractSpillBaseRegAndOffset(const MachineInstr &MI,
335
7
                                                  unsigned &Reg) {
336
7
  assert(MI.hasOneMemOperand() && 
337
7
         "Spill instruction does not have exactly one memory operand?");
338
7
  auto MMOI = MI.memoperands_begin();
339
7
  const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
340
7
  assert(PVal->kind() == PseudoSourceValue::FixedStack &&
341
7
         "Inconsistent memory operand in spill instruction");
342
7
  int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
343
7
  const MachineBasicBlock *MBB = MI.getParent();
344
7
  return TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg);
345
7
}
346
347
/// End all previous ranges related to @MI and start a new range from @MI
348
/// if it is a DBG_VALUE instr.
349
void LiveDebugValues::transferDebugValue(const MachineInstr &MI,
350
                                         OpenRangesSet &OpenRanges,
351
478k
                                         VarLocMap &VarLocIDs) {
352
478k
  if (!MI.isDebugValue())
353
476k
    return;
354
1.80k
  const DILocalVariable *Var = MI.getDebugVariable();
355
1.80k
  const DILocation *DebugLoc = MI.getDebugLoc();
356
1.80k
  const DILocation *InlinedAt = DebugLoc->getInlinedAt();
357
1.80k
  assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
358
1.80k
         "Expected inlined-at fields to agree");
359
1.80k
360
1.80k
  // End all previous ranges of Var.
361
1.80k
  DebugVariable V(Var, InlinedAt);
362
1.80k
  OpenRanges.erase(V);
363
1.80k
364
1.80k
  // Add the VarLoc to OpenRanges from this DBG_VALUE.
365
1.80k
  // TODO: Currently handles DBG_VALUE which has only reg as location.
366
1.80k
  if (
isDbgValueDescribedByReg(MI)1.80k
) {
367
1.65k
    VarLoc VL(MI, LS);
368
1.65k
    unsigned ID = VarLocIDs.insert(VL);
369
1.65k
    OpenRanges.insert(ID, VL.Var);
370
1.65k
  }
371
478k
}
372
373
/// A definition of a register may mark the end of a range.
374
void LiveDebugValues::transferRegisterDef(MachineInstr &MI,
375
                                          OpenRangesSet &OpenRanges,
376
478k
                                          const VarLocMap &VarLocIDs) {
377
478k
  MachineFunction *MF = MI.getParent()->getParent();
378
478k
  const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
379
478k
  unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
380
478k
  SparseBitVector<> KillSet;
381
1.92M
  for (const MachineOperand &MO : MI.operands()) {
382
1.92M
    // Determine whether the operand is a register def.  Assume that call
383
1.92M
    // instructions never clobber SP, because some backends (e.g., AArch64)
384
1.92M
    // never list SP in the regmask.
385
1.92M
    if (
MO.isReg() && 1.92M
MO.isDef()1.31M
&&
MO.getReg()470k
&&
386
470k
        TRI->isPhysicalRegister(MO.getReg()) &&
387
1.92M
        
!(MI.isCall() && 470k
MO.getReg() == SP55.3k
)) {
388
442k
      // Remove ranges of all aliased registers.
389
2.08M
      for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); 
RAI.isValid()2.08M
;
++RAI1.64M
)
390
1.64M
        for (unsigned ID : OpenRanges.getVarLocs())
391
23.4k
          
if (23.4k
VarLocIDs[ID].isDescribedByReg() == *RAI23.4k
)
392
394
            KillSet.set(ID);
393
1.92M
    } else 
if (1.47M
MO.isRegMask()1.47M
) {
394
29.9k
      // Remove ranges of all clobbered registers. Register masks don't usually
395
29.9k
      // list SP as preserved.  While the debug info may be off for an
396
29.9k
      // instruction or two around callee-cleanup calls, transferring the
397
29.9k
      // DEBUG_VALUE across the call is still a better user experience.
398
476
      for (unsigned ID : OpenRanges.getVarLocs()) {
399
476
        unsigned Reg = VarLocIDs[ID].isDescribedByReg();
400
476
        if (
Reg && 476
Reg != SP476
&&
MO.clobbersPhysReg(Reg)316
)
401
100
          KillSet.set(ID);
402
476
      }
403
1.47M
    }
404
1.92M
  }
405
478k
  OpenRanges.erase(KillSet, VarLocIDs);
406
478k
}
407
408
/// Decide if @MI is a spill instruction and return true if it is. We use 2
409
/// criteria to make this decision:
410
/// - Is this instruction a store to a spill slot?
411
/// - Is there a register operand that is both used and killed?
412
/// TODO: Store optimization can fold spills into other stores (including
413
/// other spills). We do not handle this yet (more than one memory operand).
414
bool LiveDebugValues::isSpillInstruction(const MachineInstr &MI,
415
2.42k
                                         MachineFunction *MF, unsigned &Reg) {
416
2.42k
  const MachineFrameInfo &FrameInfo = MF->getFrameInfo();
417
2.42k
  int FI;
418
2.42k
  const MachineMemOperand *MMO;
419
2.42k
420
2.42k
  // TODO: Handle multiple stores folded into one. 
421
2.42k
  if (!MI.hasOneMemOperand())
422
1.99k
    return false;
423
435
424
435
  // To identify a spill instruction, use the same criteria as in AsmPrinter.
425
435
  
if (435
!((TII->isStoreToStackSlotPostFE(MI, FI) ||
426
407
         TII->hasStoreToStackSlot(MI, MMO, FI)) &&
427
44
        FrameInfo.isSpillSlotObjectIndex(FI)))
428
393
    return false;
429
42
430
42
  // In a spill instruction generated by the InlineSpiller the spilled register
431
42
  // has its kill flag set. Return false if we don't find such a register.
432
42
  Reg = 0;
433
167
  for (const MachineOperand &MO : MI.operands()) {
434
167
    if (
MO.isReg() && 167
MO.isUse()117
&&
MO.isKill()117
) {
435
42
      Reg = MO.getReg();
436
42
      break;
437
42
    }
438
42
  }
439
42
  return Reg != 0;
440
2.42k
}
441
442
/// A spilled register may indicate that we have to end the current range of
443
/// a variable and create a new one for the spill location.
444
/// We don't want to insert any instructions in transfer(), so we just create
445
/// the DBG_VALUE witout inserting it and keep track of it in @Spills.
446
/// It will be inserted into the BB when we're done iterating over the
447
/// instructions.
448
void LiveDebugValues::transferSpillInst(MachineInstr &MI,
449
                                        OpenRangesSet &OpenRanges,
450
                                        VarLocMap &VarLocIDs,
451
2.42k
                                        SpillMap &Spills) {
452
2.42k
  unsigned Reg;
453
2.42k
  MachineFunction *MF = MI.getParent()->getParent();
454
2.42k
  if (!isSpillInstruction(MI, MF, Reg))
455
2.38k
    return;
456
42
457
42
  // Check if the register is the location of a debug value.
458
42
  
for (unsigned ID : OpenRanges.getVarLocs()) 42
{
459
78
    if (
VarLocIDs[ID].isDescribedByReg() == Reg78
) {
460
7
      DEBUG(dbgs() << "Spilling Register " << PrintReg(Reg, TRI) << '('
461
7
                   << VarLocIDs[ID].Var.getVar()->getName() << ")\n");
462
7
463
7
      // Create a DBG_VALUE instruction to describe the Var in its spilled
464
7
      // location, but don't insert it yet to avoid invalidating the
465
7
      // iterator in our caller.
466
7
      unsigned SpillBase;
467
7
      int SpillOffset = extractSpillBaseRegAndOffset(MI, SpillBase);
468
7
      const MachineInstr *DMI = &VarLocIDs[ID].MI;
469
7
      auto *SpillExpr = DIExpression::prepend(
470
7
          DMI->getDebugExpression(), DIExpression::NoDeref, SpillOffset);
471
7
      MachineInstr *SpDMI =
472
7
          BuildMI(*MF, DMI->getDebugLoc(), DMI->getDesc(), true, SpillBase,
473
7
                  DMI->getDebugVariable(), SpillExpr);
474
7
      DEBUG(dbgs() << "Creating DBG_VALUE inst for spill: ";
475
7
            SpDMI->print(dbgs(), false, TII));
476
7
477
7
      // The newly created DBG_VALUE instruction SpDMI must be inserted after
478
7
      // MI. Keep track of the pairing.
479
7
      SpillDebugPair MIP = {&MI, SpDMI};
480
7
      Spills.push_back(MIP);
481
7
482
7
      // End all previous ranges of Var.
483
7
      OpenRanges.erase(VarLocIDs[ID].Var);
484
7
485
7
      // Add the VarLoc to OpenRanges.
486
7
      VarLoc VL(*SpDMI, LS);
487
7
      unsigned SpillLocID = VarLocIDs.insert(VL);
488
7
      OpenRanges.insert(SpillLocID, VL.Var);
489
7
      return;
490
7
    }
491
35
  }
492
2.42k
}
493
494
/// Terminate all open ranges at the end of the current basic block.
495
bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
496
                                             OpenRangesSet &OpenRanges,
497
                                             VarLocInMBB &OutLocs,
498
478k
                                             const VarLocMap &VarLocIDs) {
499
478k
  bool Changed = false;
500
478k
  const MachineBasicBlock *CurMBB = MI.getParent();
501
478k
  if (
!(MI.isTerminator() || 478k
(&MI == &CurMBB->instr_back())426k
))
502
409k
    return false;
503
69.3k
504
69.3k
  
if (69.3k
OpenRanges.empty()69.3k
)
505
68.9k
    return false;
506
456
507
456
  
DEBUG456
(for (unsigned ID : OpenRanges.getVarLocs()) {
508
456
          // Copy OpenRanges to OutLocs, if not already present.
509
456
          dbgs() << "Add to OutLocs: "; VarLocIDs[ID].dump();
510
456
        });
511
456
  VarLocSet &VLS = OutLocs[CurMBB];
512
456
  Changed = VLS |= OpenRanges.getVarLocs();
513
456
  OpenRanges.clear();
514
456
  return Changed;
515
456
}
516
517
/// This routine creates OpenRanges and OutLocs.
518
bool LiveDebugValues::transfer(MachineInstr &MI, OpenRangesSet &OpenRanges,
519
                               VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
520
478k
                               SpillMap &Spills, bool transferSpills) {
521
478k
  bool Changed = false;
522
478k
  transferDebugValue(MI, OpenRanges, VarLocIDs);
523
478k
  transferRegisterDef(MI, OpenRanges, VarLocIDs);
524
478k
  if (transferSpills)
525
2.42k
    transferSpillInst(MI, OpenRanges, VarLocIDs, Spills);
526
478k
  Changed = transferTerminatorInst(MI, OpenRanges, OutLocs, VarLocIDs);
527
478k
  return Changed;
528
478k
}
529
530
/// This routine joins the analysis results of all incoming edges in @MBB by
531
/// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
532
/// source variable in all the predecessors of @MBB reside in the same location.
533
bool LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs,
534
                           VarLocInMBB &InLocs, const VarLocMap &VarLocIDs,
535
65.8k
                           SmallPtrSet<const MachineBasicBlock *, 16> &Visited) {
536
65.8k
  DEBUG(dbgs() << "join MBB: " << MBB.getName() << "\n");
537
65.8k
  bool Changed = false;
538
65.8k
539
65.8k
  VarLocSet InLocsT; // Temporary incoming locations.
540
65.8k
541
65.8k
  // For all predecessors of this MBB, find the set of VarLocs that
542
65.8k
  // can be joined.
543
65.8k
  int NumVisited = 0;
544
57.4k
  for (auto p : MBB.predecessors()) {
545
57.4k
    // Ignore unvisited predecessor blocks.  As we are processing
546
57.4k
    // the blocks in reverse post-order any unvisited block can
547
57.4k
    // be considered to not remove any incoming values.
548
57.4k
    if (!Visited.count(p))
549
848
      continue;
550
56.6k
    auto OL = OutLocs.find(p);
551
56.6k
    // Join is null in case of empty OutLocs from any of the pred.
552
56.6k
    if (OL == OutLocs.end())
553
55.8k
      return false;
554
781
555
781
    // Just copy over the Out locs to incoming locs for the first visited
556
781
    // predecessor, and for all other predecessors join the Out locs.
557
781
    
if (781
!NumVisited781
)
558
556
      InLocsT = OL->second;
559
781
    else
560
225
      InLocsT &= OL->second;
561
57.4k
    NumVisited++;
562
57.4k
  }
563
65.8k
564
65.8k
  // Filter out DBG_VALUES that are out of scope.
565
10.0k
  VarLocSet KillSet;
566
10.0k
  for (auto ID : InLocsT)
567
1.22k
    
if (1.22k
!VarLocIDs[ID].dominates(MBB)1.22k
)
568
53
      KillSet.set(ID);
569
10.0k
  InLocsT.intersectWithComplement(KillSet);
570
10.0k
571
10.0k
  // As we are processing blocks in reverse post-order we
572
10.0k
  // should have processed at least one predecessor, unless it
573
10.0k
  // is the entry block which has no predecessor.
574
10.0k
  assert((NumVisited || MBB.pred_empty()) &&
575
10.0k
         "Should have processed at least one predecessor");
576
10.0k
  if (InLocsT.empty())
577
9.53k
    return false;
578
523
579
523
  VarLocSet &ILS = InLocs[&MBB];
580
523
581
523
  // Insert DBG_VALUE instructions, if not already inserted.
582
523
  VarLocSet Diff = InLocsT;
583
523
  Diff.intersectWithComplement(ILS);
584
680
  for (auto ID : Diff) {
585
680
    // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a
586
680
    // new range is started for the var from the mbb's beginning by inserting
587
680
    // a new DBG_VALUE. transfer() will end this range however appropriate.
588
680
    const VarLoc &DiffIt = VarLocIDs[ID];
589
680
    const MachineInstr *DMI = &DiffIt.MI;
590
680
    MachineInstr *MI =
591
680
        BuildMI(MBB, MBB.instr_begin(), DMI->getDebugLoc(), DMI->getDesc(),
592
680
                DMI->isIndirectDebugValue(), DMI->getOperand(0).getReg(),
593
680
                DMI->getDebugVariable(), DMI->getDebugExpression());
594
680
    if (DMI->isIndirectDebugValue())
595
187
      MI->getOperand(1).setImm(DMI->getOperand(1).getImm());
596
680
    DEBUG(dbgs() << "Inserted: "; MI->dump(););
597
680
    ILS.set(ID);
598
680
    ++NumInserted;
599
680
    Changed = true;
600
680
  }
601
65.8k
  return Changed;
602
65.8k
}
603
604
/// Calculate the liveness information for the given machine function and
605
/// extend ranges across basic blocks.
606
9.51k
bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
607
9.51k
  DEBUG(dbgs() << "\nDebug Range Extension\n");
608
9.51k
609
9.51k
  bool Changed = false;
610
9.51k
  bool OLChanged = false;
611
9.51k
  bool MBBJoined = false;
612
9.51k
613
9.51k
  VarLocMap VarLocIDs;      // Map VarLoc<>unique ID for use in bitvectors.
614
9.51k
  OpenRangesSet OpenRanges; // Ranges that are open until end of bb.
615
9.51k
  VarLocInMBB OutLocs;      // Ranges that exist beyond bb.
616
9.51k
  VarLocInMBB InLocs;       // Ranges that are incoming after joining.
617
9.51k
  SpillMap Spills;          // DBG_VALUEs associated with spills.
618
9.51k
619
9.51k
  DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
620
9.51k
  DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
621
9.51k
  std::priority_queue<unsigned int, std::vector<unsigned int>,
622
9.51k
                      std::greater<unsigned int>>
623
9.51k
      Worklist;
624
9.51k
  std::priority_queue<unsigned int, std::vector<unsigned int>,
625
9.51k
                      std::greater<unsigned int>>
626
9.51k
      Pending;
627
9.51k
628
9.51k
  // Initialize every mbb with OutLocs.
629
9.51k
  // We are not looking at any spill instructions during the initial pass
630
9.51k
  // over the BBs. The LiveDebugVariables pass has already created DBG_VALUE
631
9.51k
  // instructions for spills of registers that are known to be user variables
632
9.51k
  // within the BB in which the spill occurs.
633
9.51k
  for (auto &MBB : MF)
634
65.7k
    for (auto &MI : MBB)
635
476k
      transfer(MI, OpenRanges, OutLocs, VarLocIDs, Spills,
636
476k
               /*transferSpills=*/false);
637
9.51k
638
9.51k
  DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "OutLocs after initialization",
639
9.51k
                         dbgs()));
640
9.51k
641
9.51k
  ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
642
9.51k
  unsigned int RPONumber = 0;
643
75.1k
  for (auto RI = RPOT.begin(), RE = RPOT.end(); 
RI != RE75.1k
;
++RI65.6k
) {
644
65.6k
    OrderToBB[RPONumber] = *RI;
645
65.6k
    BBToOrder[*RI] = RPONumber;
646
65.6k
    Worklist.push(RPONumber);
647
65.6k
    ++RPONumber;
648
65.6k
  }
649
9.51k
  // This is a standard "union of predecessor outs" dataflow problem.
650
9.51k
  // To solve it, we perform join() and transfer() using the two worklist method
651
9.51k
  // until the ranges converge.
652
9.51k
  // Ranges have converged when both worklists are empty.
653
9.51k
  SmallPtrSet<const MachineBasicBlock *, 16> Visited;
654
19.0k
  while (
!Worklist.empty() || 19.0k
!Pending.empty()9.51k
) {
655
9.56k
    // We track what is on the pending worklist to avoid inserting the same
656
9.56k
    // thing twice.  We could avoid this with a custom priority queue, but this
657
9.56k
    // is probably not worth it.
658
9.56k
    SmallPtrSet<MachineBasicBlock *, 16> OnPending;
659
9.56k
    DEBUG(dbgs() << "Processing Worklist\n");
660
75.4k
    while (
!Worklist.empty()75.4k
) {
661
65.8k
      MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
662
65.8k
      Worklist.pop();
663
65.8k
      MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs, Visited);
664
65.8k
      Visited.insert(MBB);
665
65.8k
      if (
MBBJoined65.8k
) {
666
317
        MBBJoined = false;
667
317
        Changed = true;
668
317
        // Now that we have started to extend ranges across BBs we need to
669
317
        // examine spill instructions to see whether they spill registers that
670
317
        // correspond to user variables.
671
317
        for (auto &MI : *MBB)
672
2.42k
          OLChanged |= transfer(MI, OpenRanges, OutLocs, VarLocIDs, Spills,
673
2.42k
                                /*transferSpills=*/true);
674
317
675
317
        // Add any DBG_VALUE instructions necessitated by spills.
676
317
        for (auto &SP : Spills)
677
7
          MBB->insertAfter(MachineBasicBlock::iterator(*SP.SpillInst),
678
7
                           SP.DebugInst);
679
317
        Spills.clear();
680
317
681
317
        DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
682
317
                               "OutLocs after propagating", dbgs()));
683
317
        DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
684
317
                               "InLocs after propagating", dbgs()));
685
317
686
317
        if (
OLChanged317
) {
687
242
          OLChanged = false;
688
242
          for (auto s : MBB->successors())
689
287
            
if (287
OnPending.insert(s).second287
) {
690
214
              Pending.push(BBToOrder[s]);
691
214
            }
692
242
        }
693
317
      }
694
65.8k
    }
695
9.56k
    Worklist.swap(Pending);
696
9.56k
    // At this point, pending must be empty, since it was just the empty
697
9.56k
    // worklist
698
9.56k
    assert(Pending.empty() && "Pending should be empty");
699
9.56k
  }
700
9.51k
701
9.51k
  DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs()));
702
9.51k
  DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs()));
703
9.51k
  return Changed;
704
9.51k
}
705
706
594k
bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
707
594k
  if (!MF.getFunction()->getSubprogram())
708
594k
    // LiveDebugValues will already have removed all DBG_VALUEs.
709
584k
    return false;
710
9.52k
711
9.52k
  // Skip functions from NoDebug compilation units.
712
9.52k
  
if (9.52k
MF.getFunction()->getSubprogram()->getUnit()->getEmissionKind() ==
713
9.52k
      DICompileUnit::NoDebug)
714
15
    return false;
715
9.50k
716
9.50k
  TRI = MF.getSubtarget().getRegisterInfo();
717
9.50k
  TII = MF.getSubtarget().getInstrInfo();
718
9.50k
  TFI = MF.getSubtarget().getFrameLowering();
719
9.50k
  LS.initialize(MF);
720
9.50k
721
9.50k
  bool Changed = ExtendRanges(MF);
722
9.50k
  return Changed;
723
9.50k
}