LLVM  9.0.0svn
DbgEntityHistoryCalculator.cpp
Go to the documentation of this file.
1 //===- llvm/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp -------------===//
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 
10 #include "llvm/ADT/BitVector.h"
11 #include "llvm/ADT/STLExtras.h"
12 #include "llvm/ADT/SmallSet.h"
13 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/IR/DebugLoc.h"
23 #include "llvm/MC/MCRegisterInfo.h"
24 #include "llvm/Support/Debug.h"
26 #include <cassert>
27 #include <map>
28 #include <utility>
29 
30 using namespace llvm;
31 
32 #define DEBUG_TYPE "dwarfdebug"
33 
34 namespace {
35 using EntryIndex = DbgValueHistoryMap::EntryIndex;
36 }
37 
38 // If @MI is a DBG_VALUE with debug value described by a
39 // defined register, returns the number of this register.
40 // In the other case, returns 0.
41 static unsigned isDescribedByReg(const MachineInstr &MI) {
42  assert(MI.isDebugValue());
43  assert(MI.getNumOperands() == 4);
44  // If location of variable is described using a register (directly or
45  // indirectly), this register is always a first operand.
46  return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : 0;
47 }
48 
50  const MachineInstr &MI,
51  EntryIndex &NewIndex) {
52  // Instruction range should start with a DBG_VALUE instruction for the
53  // variable.
54  assert(MI.isDebugValue() && "not a DBG_VALUE");
55  auto &Entries = VarEntries[Var];
56  if (!Entries.empty() && Entries.back().isDbgValue() &&
57  !Entries.back().isClosed() &&
58  Entries.back().getInstr()->isIdenticalTo(MI)) {
59  LLVM_DEBUG(dbgs() << "Coalescing identical DBG_VALUE entries:\n"
60  << "\t" << Entries.back().getInstr() << "\t" << MI
61  << "\n");
62  return false;
63  }
64  Entries.emplace_back(&MI, Entry::DbgValue);
65  NewIndex = Entries.size() - 1;
66  return true;
67 }
68 
70  const MachineInstr &MI) {
71  auto &Entries = VarEntries[Var];
72  // If an instruction clobbers multiple registers that the variable is
73  // described by, then we may have already created a clobbering instruction.
74  if (Entries.back().isClobber() && Entries.back().getInstr() == &MI)
75  return Entries.size() - 1;
76  Entries.emplace_back(&MI, Entry::Clobber);
77  return Entries.size() - 1;
78 }
79 
81  // For now, instruction ranges are not allowed to cross basic block
82  // boundaries.
83  assert(isDbgValue() && "Setting end index for non-debug value");
84  assert(!isClosed() && "End index has already been set");
85  EndIndex = Index;
86 }
87 
89  assert(MI.isDebugLabel() && "not a DBG_LABEL");
90  LabelInstr[Label] = &MI;
91 }
92 
93 namespace {
94 
95 // Maps physreg numbers to the variables they describe.
97 using RegDescribedVarsMap = std::map<unsigned, SmallVector<InlinedEntity, 1>>;
98 
99 // Keeps track of the debug value entries that are currently live for each
100 // inlined entity. As the history map entries are stored in a SmallVector, they
101 // may be moved at insertion of new entries, so store indices rather than
102 // pointers.
103 using DbgValueEntriesMap = std::map<InlinedEntity, SmallSet<EntryIndex, 1>>;
104 
105 } // end anonymous namespace
106 
107 // Claim that @Var is not described by @RegNo anymore.
108 static void dropRegDescribedVar(RegDescribedVarsMap &RegVars, unsigned RegNo,
109  InlinedEntity Var) {
110  const auto &I = RegVars.find(RegNo);
111  assert(RegNo != 0U && I != RegVars.end());
112  auto &VarSet = I->second;
113  const auto &VarPos = llvm::find(VarSet, Var);
114  assert(VarPos != VarSet.end());
115  VarSet.erase(VarPos);
116  // Don't keep empty sets in a map to keep it as small as possible.
117  if (VarSet.empty())
118  RegVars.erase(I);
119 }
120 
121 // Claim that @Var is now described by @RegNo.
122 static void addRegDescribedVar(RegDescribedVarsMap &RegVars, unsigned RegNo,
123  InlinedEntity Var) {
124  assert(RegNo != 0U);
125  auto &VarSet = RegVars[RegNo];
126  assert(!is_contained(VarSet, Var));
127  VarSet.push_back(Var);
128 }
129 
130 /// Create a clobbering entry and end all open debug value entries
131 /// for \p Var that are described by \p RegNo using that entry.
132 static void clobberRegEntries(InlinedEntity Var, unsigned RegNo,
133  const MachineInstr &ClobberingInstr,
134  DbgValueEntriesMap &LiveEntries,
135  DbgValueHistoryMap &HistMap) {
136  EntryIndex ClobberIndex = HistMap.startClobber(Var, ClobberingInstr);
137 
138  // Close all entries whose values are described by the register.
139  SmallVector<EntryIndex, 4> IndicesToErase;
140  for (auto Index : LiveEntries[Var]) {
141  auto &Entry = HistMap.getEntry(Var, Index);
142  assert(Entry.isDbgValue() && "Not a DBG_VALUE in LiveEntries");
143  if (isDescribedByReg(*Entry.getInstr()) == RegNo) {
144  IndicesToErase.push_back(Index);
145  Entry.endEntry(ClobberIndex);
146  }
147  }
148 
149  // Drop all entries that have ended.
150  for (auto Index : IndicesToErase)
151  LiveEntries[Var].erase(Index);
152 }
153 
154 /// Add a new debug value for \p Var. Closes all overlapping debug values.
155 static void handleNewDebugValue(InlinedEntity Var, const MachineInstr &DV,
156  RegDescribedVarsMap &RegVars,
157  DbgValueEntriesMap &LiveEntries,
158  DbgValueHistoryMap &HistMap) {
159  EntryIndex NewIndex;
160  if (HistMap.startDbgValue(Var, DV, NewIndex)) {
162 
163  // If we have created a new debug value entry, close all preceding
164  // live entries that overlap.
165  SmallVector<EntryIndex, 4> IndicesToErase;
166  const DIExpression *DIExpr = DV.getDebugExpression();
167  for (auto Index : LiveEntries[Var]) {
168  auto &Entry = HistMap.getEntry(Var, Index);
169  assert(Entry.isDbgValue() && "Not a DBG_VALUE in LiveEntries");
170  const MachineInstr &DV = *Entry.getInstr();
171  bool Overlaps = DIExpr->fragmentsOverlap(DV.getDebugExpression());
172  if (Overlaps) {
173  IndicesToErase.push_back(Index);
174  Entry.endEntry(NewIndex);
175  }
176  if (unsigned Reg = isDescribedByReg(DV))
177  TrackedRegs[Reg] |= !Overlaps;
178  }
179 
180  // If the new debug value is described by a register, add tracking of
181  // that register if it is not already tracked.
182  if (unsigned NewReg = isDescribedByReg(DV)) {
183  if (!TrackedRegs.count(NewReg))
184  addRegDescribedVar(RegVars, NewReg, Var);
185  LiveEntries[Var].insert(NewIndex);
186  TrackedRegs[NewReg] = true;
187  }
188 
189  // Drop tracking of registers that are no longer used.
190  for (auto I : TrackedRegs)
191  if (!I.second)
192  dropRegDescribedVar(RegVars, I.first, Var);
193 
194  // Drop all entries that have ended, and mark the new entry as live.
195  for (auto Index : IndicesToErase)
196  LiveEntries[Var].erase(Index);
197  LiveEntries[Var].insert(NewIndex);
198  }
199 }
200 
201 // Terminate the location range for variables described by register at
202 // @I by inserting @ClobberingInstr to their history.
203 static void clobberRegisterUses(RegDescribedVarsMap &RegVars,
204  RegDescribedVarsMap::iterator I,
205  DbgValueHistoryMap &HistMap,
206  DbgValueEntriesMap &LiveEntries,
207  const MachineInstr &ClobberingInstr) {
208  // Iterate over all variables described by this register and add this
209  // instruction to their history, clobbering it.
210  for (const auto &Var : I->second)
211  clobberRegEntries(Var, I->first, ClobberingInstr, LiveEntries, HistMap);
212  RegVars.erase(I);
213 }
214 
215 // Terminate the location range for variables described by register
216 // @RegNo by inserting @ClobberingInstr to their history.
217 static void clobberRegisterUses(RegDescribedVarsMap &RegVars, unsigned RegNo,
218  DbgValueHistoryMap &HistMap,
219  DbgValueEntriesMap &LiveEntries,
220  const MachineInstr &ClobberingInstr) {
221  const auto &I = RegVars.find(RegNo);
222  if (I == RegVars.end())
223  return;
224  clobberRegisterUses(RegVars, I, HistMap, LiveEntries, ClobberingInstr);
225 }
226 
227 // Returns the first instruction in @MBB which corresponds to
228 // the function epilogue, or nullptr if @MBB doesn't contain an epilogue.
230  auto LastMI = MBB.getLastNonDebugInstr();
231  if (LastMI == MBB.end() || !LastMI->isReturn())
232  return nullptr;
233  // Assume that epilogue starts with instruction having the same debug location
234  // as the return instruction.
235  DebugLoc LastLoc = LastMI->getDebugLoc();
236  auto Res = LastMI;
237  for (MachineBasicBlock::const_reverse_iterator I = LastMI.getReverse(),
238  E = MBB.rend();
239  I != E; ++I) {
240  if (I->getDebugLoc() != LastLoc)
241  return &*Res;
242  Res = &*I;
243  }
244  // If all instructions have the same debug location, assume whole MBB is
245  // an epilogue.
246  return &*MBB.begin();
247 }
248 
249 // Collect registers that are modified in the function body (their
250 // contents is changed outside of the prologue and epilogue).
251 static void collectChangingRegs(const MachineFunction *MF,
252  const TargetRegisterInfo *TRI,
253  BitVector &Regs) {
254  for (const auto &MBB : *MF) {
255  auto FirstEpilogueInst = getFirstEpilogueInst(MBB);
256 
257  for (const auto &MI : MBB) {
258  // Avoid looking at prologue or epilogue instructions.
259  if (&MI == FirstEpilogueInst)
260  break;
261  if (MI.getFlag(MachineInstr::FrameSetup))
262  continue;
263 
264  // Look for register defs and register masks. Register masks are
265  // typically on calls and they clobber everything not in the mask.
266  for (const MachineOperand &MO : MI.operands()) {
267  // Skip virtual registers since they are handled by the parent.
268  if (MO.isReg() && MO.isDef() && MO.getReg() &&
269  !TRI->isVirtualRegister(MO.getReg())) {
270  for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid();
271  ++AI)
272  Regs.set(*AI);
273  } else if (MO.isRegMask()) {
274  Regs.setBitsNotInMask(MO.getRegMask());
275  }
276  }
277  }
278  }
279 }
280 
282  const TargetRegisterInfo *TRI,
283  DbgValueHistoryMap &DbgValues,
284  DbgLabelInstrMap &DbgLabels) {
285  BitVector ChangingRegs(TRI->getNumRegs());
286  collectChangingRegs(MF, TRI, ChangingRegs);
287 
288  const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
289  unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
290  RegDescribedVarsMap RegVars;
291  DbgValueEntriesMap LiveEntries;
292  for (const auto &MBB : *MF) {
293  for (const auto &MI : MBB) {
294  if (!MI.isDebugInstr()) {
295  // Not a DBG_VALUE instruction. It may clobber registers which describe
296  // some variables.
297  for (const MachineOperand &MO : MI.operands()) {
298  if (MO.isReg() && MO.isDef() && MO.getReg()) {
299  // Ignore call instructions that claim to clobber SP. The AArch64
300  // backend does this for aggregate function arguments.
301  if (MI.isCall() && MO.getReg() == SP)
302  continue;
303  // If this is a virtual register, only clobber it since it doesn't
304  // have aliases.
305  if (TRI->isVirtualRegister(MO.getReg()))
306  clobberRegisterUses(RegVars, MO.getReg(), DbgValues, LiveEntries,
307  MI);
308  // If this is a register def operand, it may end a debug value
309  // range.
310  else {
311  for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid();
312  ++AI)
313  if (ChangingRegs.test(*AI))
314  clobberRegisterUses(RegVars, *AI, DbgValues, LiveEntries, MI);
315  }
316  } else if (MO.isRegMask()) {
317  // If this is a register mask operand, clobber all debug values in
318  // non-CSRs.
319  for (unsigned I : ChangingRegs.set_bits()) {
320  // Don't consider SP to be clobbered by register masks.
321  if (unsigned(I) != SP && TRI->isPhysicalRegister(I) &&
322  MO.clobbersPhysReg(I)) {
323  clobberRegisterUses(RegVars, I, DbgValues, LiveEntries, MI);
324  }
325  }
326  }
327  }
328  continue;
329  }
330 
331  if (MI.isDebugValue()) {
332  assert(MI.getNumOperands() > 1 && "Invalid DBG_VALUE instruction!");
333  // Use the base variable (without any DW_OP_piece expressions)
334  // as index into History. The full variables including the
335  // piece expressions are attached to the MI.
336  const DILocalVariable *RawVar = MI.getDebugVariable();
337  assert(RawVar->isValidLocationForIntrinsic(MI.getDebugLoc()) &&
338  "Expected inlined-at fields to agree");
339  InlinedEntity Var(RawVar, MI.getDebugLoc()->getInlinedAt());
340 
341  handleNewDebugValue(Var, MI, RegVars, LiveEntries, DbgValues);
342  } else if (MI.isDebugLabel()) {
343  assert(MI.getNumOperands() == 1 && "Invalid DBG_LABEL instruction!");
344  const DILabel *RawLabel = MI.getDebugLabel();
345  assert(RawLabel->isValidLocationForIntrinsic(MI.getDebugLoc()) &&
346  "Expected inlined-at fields to agree");
347  // When collecting debug information for labels, there is no MCSymbol
348  // generated for it. So, we keep MachineInstr in DbgLabels in order
349  // to query MCSymbol afterward.
350  InlinedEntity L(RawLabel, MI.getDebugLoc()->getInlinedAt());
351  DbgLabels.addInstr(L, MI);
352  }
353  }
354 
355  // Make sure locations for register-described variables are valid only
356  // until the end of the basic block (unless it's the last basic block, in
357  // which case let their liveness run off to the end of the function).
358  if (!MBB.empty() && &MBB != &MF->back()) {
359  for (auto I = RegVars.begin(), E = RegVars.end(); I != E;) {
360  auto CurElem = I++; // CurElem can be erased below.
361  if (TRI->isVirtualRegister(CurElem->first) ||
362  ChangingRegs.test(CurElem->first))
363  clobberRegisterUses(RegVars, CurElem, DbgValues, LiveEntries,
364  MBB.back());
365  }
366  }
367  }
368 }
369 
370 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
372  dbgs() << "DbgValueHistoryMap:\n";
373  for (const auto &VarRangePair : *this) {
374  const InlinedEntity &Var = VarRangePair.first;
375  const Entries &Entries = VarRangePair.second;
376 
377  const DILocalVariable *LocalVar = cast<DILocalVariable>(Var.first);
378  const DILocation *Location = Var.second;
379 
380  dbgs() << " - " << LocalVar->getName() << " at ";
381 
382  if (Location)
383  dbgs() << Location->getFilename() << ":" << Location->getLine() << ":"
384  << Location->getColumn();
385  else
386  dbgs() << "<unknown location>";
387 
388  dbgs() << " --\n";
389 
390  for (const auto &E : enumerate(Entries)) {
391  const auto &Entry = E.value();
392  dbgs() << " Entry[" << E.index() << "]: ";
393  if (Entry.isDbgValue())
394  dbgs() << "Debug value\n";
395  else
396  dbgs() << "Clobber\n";
397  dbgs() << " Instr: " << *Entry.getInstr();
398  if (Entry.isDbgValue()) {
399  if (Entry.getEndIndex() == NoEntry)
400  dbgs() << " - Valid until end of function\n";
401  else
402  dbgs() << " - Closed by Entry[" << Entry.getEndIndex() << "]\n";
403  }
404  dbgs() << "\n";
405  }
406  }
407 }
408 #endif
For each inlined instance of a source-level label, keep the corresponding DBG_LABEL instruction...
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:645
BitVector & set()
Definition: BitVector.h:397
bool isDebugLabel() const
Definition: MachineInstr.h:997
static void dropRegDescribedVar(RegDescribedVarsMap &RegVars, unsigned RegNo, InlinedEntity Var)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:473
static const MachineInstr * getFirstEpilogueInst(const MachineBasicBlock &MBB)
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
unsigned Reg
virtual const TargetLowering * getTargetLowering() const
void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
setBitsNotInMask - Add a bit to this vector for every &#39;0&#39; bit in Mask.
Definition: BitVector.h:787
unsigned const TargetRegisterInfo * TRI
A debug info location.
Definition: DebugLoc.h:33
For each user variable, keep a list of instruction ranges where this variable is accessible.
void calculateDbgEntityHistory(const MachineFunction *MF, const TargetRegisterInfo *TRI, DbgValueHistoryMap &DbgValues, DbgLabelInstrMap &DbgLabels)
std::pair< const DINode *, const DILocation * > InlinedEntity
StringRef getName() const
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:411
MachineBasicBlock iterator that automatically skips over MIs that are inside bundles (i...
static void clobberRegEntries(InlinedEntity Var, unsigned RegNo, const MachineInstr &ClobberingInstr, DbgValueEntriesMap &LiveEntries, DbgValueHistoryMap &HistMap)
Create a clobbering entry and end all open debug value entries for Var that are described by RegNo us...
static void addRegDescribedVar(RegDescribedVarsMap &RegVars, unsigned RegNo, InlinedEntity Var)
size_t EntryIndex
Index in the entry vector.
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
iterator getLastNonDebugInstr()
Returns an iterator to the last non-debug instruction in the basic block, or end().
Debug location.
reverse_iterator rend()
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Specifies a change in a variable&#39;s debug value history.
MCRegAliasIterator enumerates all registers aliasing Reg.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
size_t size() const
Definition: SmallVector.h:52
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1206
static unsigned isDescribedByReg(const MachineInstr &MI)
const DIExpression * getDebugExpression() const
Return the complex address expression referenced by this DBG_VALUE instruction.
std::pair< const DINode *, const DILocation * > InlinedEntity
void addInstr(InlinedEntity Label, const MachineInstr &MI)
bool isDebugValue() const
Definition: MachineInstr.h:996
MachineOperand class - Representation of each machine instruction operand.
DWARF expression.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
bool fragmentsOverlap(const DIExpression *Other) const
Check if fragments overlap between this DIExpression and Other.
static cl::opt< bool > NoEntry("spp-no-entry", cl::Hidden, cl::init(false))
Representation of each machine instruction.
Definition: MachineInstr.h:63
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
#define I(x, y, z)
Definition: MD5.cpp:58
Entry & getEntry(InlinedEntity Var, EntryIndex Index)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:171
bool isReg() const
isReg - Tests if this is a MO_Register operand.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getStackPointerRegisterToSaveRestore() const
If a physical register, this specifies the register that llvm.savestack/llvm.restorestack should save...
static void collectChangingRegs(const MachineFunction *MF, const TargetRegisterInfo *TRI, BitVector &Regs)
static void clobberRegisterUses(RegDescribedVarsMap &RegVars, RegDescribedVarsMap::iterator I, DbgValueHistoryMap &HistMap, DbgValueEntriesMap &LiveEntries, const MachineInstr &ClobberingInstr)
IRTranslator LLVM IR MI
const MachineInstr * getInstr() const
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:413
bool startDbgValue(InlinedEntity Var, const MachineInstr &MI, EntryIndex &NewIndex)
LLVM_DUMP_METHOD void dump() const
EntryIndex startClobber(InlinedEntity Var, const MachineInstr &MI)
detail::enumerator< R > enumerate(R &&TheRange)
Given an input range, returns a new range whose values are are pair (A,B) such that A is the 0-based ...
Definition: STLExtras.h:1571
This file describes how to lower LLVM code to machine code.
static void handleNewDebugValue(InlinedEntity Var, const MachineInstr &DV, RegDescribedVarsMap &RegVars, DbgValueEntriesMap &LiveEntries, DbgValueHistoryMap &HistMap)
Add a new debug value for Var. Closes all overlapping debug values.
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1244