LLVM  15.0.0git
InstrRefBasedImpl.cpp
Go to the documentation of this file.
1 //===- InstrRefBasedImpl.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 /// \file InstrRefBasedImpl.cpp
9 ///
10 /// This is a separate implementation of LiveDebugValues, see
11 /// LiveDebugValues.cpp and VarLocBasedImpl.cpp for more information.
12 ///
13 /// This pass propagates variable locations between basic blocks, resolving
14 /// control flow conflicts between them. The problem is SSA construction, where
15 /// each debug instruction assigns the *value* that a variable has, and every
16 /// instruction where the variable is in scope uses that variable. The resulting
17 /// map of instruction-to-value is then translated into a register (or spill)
18 /// location for each variable over each instruction.
19 ///
20 /// The primary difference from normal SSA construction is that we cannot
21 /// _create_ PHI values that contain variable values. CodeGen has already
22 /// completed, and we can't alter it just to make debug-info complete. Thus:
23 /// we can identify function positions where we would like a PHI value for a
24 /// variable, but must search the MachineFunction to see whether such a PHI is
25 /// available. If no such PHI exists, the variable location must be dropped.
26 ///
27 /// To achieve this, we perform two kinds of analysis. First, we identify
28 /// every value defined by every instruction (ignoring those that only move
29 /// another value), then re-compute an SSA-form representation of the
30 /// MachineFunction, using value propagation to eliminate any un-necessary
31 /// PHI values. This gives us a map of every value computed in the function,
32 /// and its location within the register file / stack.
33 ///
34 /// Secondly, for each variable we perform the same analysis, where each debug
35 /// instruction is considered a def, and every instruction where the variable
36 /// is in lexical scope as a use. Value propagation is used again to eliminate
37 /// any un-necessary PHIs. This gives us a map of each variable to the value
38 /// it should have in a block.
39 ///
40 /// Once both are complete, we have two maps for each block:
41 /// * Variables to the values they should have,
42 /// * Values to the register / spill slot they are located in.
43 /// After which we can marry-up variable values with a location, and emit
44 /// DBG_VALUE instructions specifying those locations. Variable locations may
45 /// be dropped in this process due to the desired variable value not being
46 /// resident in any machine location, or because there is no PHI value in any
47 /// location that accurately represents the desired value. The building of
48 /// location lists for each block is left to DbgEntityHistoryCalculator.
49 ///
50 /// This pass is kept efficient because the size of the first SSA problem
51 /// is proportional to the working-set size of the function, which the compiler
52 /// tries to keep small. (It's also proportional to the number of blocks).
53 /// Additionally, we repeatedly perform the second SSA problem analysis with
54 /// only the variables and blocks in a single lexical scope, exploiting their
55 /// locality.
56 ///
57 /// ### Terminology
58 ///
59 /// A machine location is a register or spill slot, a value is something that's
60 /// defined by an instruction or PHI node, while a variable value is the value
61 /// assigned to a variable. A variable location is a machine location, that must
62 /// contain the appropriate variable value. A value that is a PHI node is
63 /// occasionally called an mphi.
64 ///
65 /// The first SSA problem is the "machine value location" problem,
66 /// because we're determining which machine locations contain which values.
67 /// The "locations" are constant: what's unknown is what value they contain.
68 ///
69 /// The second SSA problem (the one for variables) is the "variable value
70 /// problem", because it's determining what values a variable has, rather than
71 /// what location those values are placed in.
72 ///
73 /// TODO:
74 /// Overlapping fragments
75 /// Entry values
76 /// Add back DEBUG statements for debugging this
77 /// Collect statistics
78 ///
79 //===----------------------------------------------------------------------===//
80 
81 #include "llvm/ADT/DenseMap.h"
83 #include "llvm/ADT/STLExtras.h"
84 #include "llvm/ADT/SmallPtrSet.h"
85 #include "llvm/ADT/SmallSet.h"
86 #include "llvm/ADT/SmallVector.h"
105 #include "llvm/Config/llvm-config.h"
107 #include "llvm/IR/DebugLoc.h"
108 #include "llvm/IR/Function.h"
109 #include "llvm/MC/MCRegisterInfo.h"
110 #include "llvm/Support/Casting.h"
111 #include "llvm/Support/Compiler.h"
112 #include "llvm/Support/Debug.h"
114 #include "llvm/Support/TypeSize.h"
118 #include <algorithm>
119 #include <cassert>
120 #include <climits>
121 #include <cstdint>
122 #include <functional>
123 #include <queue>
124 #include <tuple>
125 #include <utility>
126 #include <vector>
127 
128 #include "InstrRefBasedImpl.h"
129 #include "LiveDebugValues.h"
130 
131 using namespace llvm;
132 using namespace LiveDebugValues;
133 
134 // SSAUpdaterImple sets DEBUG_TYPE, change it.
135 #undef DEBUG_TYPE
136 #define DEBUG_TYPE "livedebugvalues"
137 
138 // Act more like the VarLoc implementation, by propagating some locations too
139 // far and ignoring some transfers.
140 static cl::opt<bool> EmulateOldLDV("emulate-old-livedebugvalues", cl::Hidden,
141  cl::desc("Act like old LiveDebugValues did"),
142  cl::init(false));
143 
144 // Limit for the maximum number of stack slots we should track, past which we
145 // will ignore any spills. InstrRefBasedLDV gathers detailed information on all
146 // stack slots which leads to high memory consumption, and in some scenarios
147 // (such as asan with very many locals) the working set of the function can be
148 // very large, causing many spills. In these scenarios, it is very unlikely that
149 // the developer has hundreds of variables live at the same time that they're
150 // carefully thinking about -- instead, they probably autogenerated the code.
151 // When this happens, gracefully stop tracking excess spill slots, rather than
152 // consuming all the developer's memory.
153 static cl::opt<unsigned>
154  StackWorkingSetLimit("livedebugvalues-max-stack-slots", cl::Hidden,
155  cl::desc("livedebugvalues-stack-ws-limit"),
156  cl::init(250));
157 
158 /// Tracker for converting machine value locations and variable values into
159 /// variable locations (the output of LiveDebugValues), recorded as DBG_VALUEs
160 /// specifying block live-in locations and transfers within blocks.
161 ///
162 /// Operating on a per-block basis, this class takes a (pre-loaded) MLocTracker
163 /// and must be initialized with the set of variable values that are live-in to
164 /// the block. The caller then repeatedly calls process(). TransferTracker picks
165 /// out variable locations for the live-in variable values (if there _is_ a
166 /// location) and creates the corresponding DBG_VALUEs. Then, as the block is
167 /// stepped through, transfers of values between machine locations are
168 /// identified and if profitable, a DBG_VALUE created.
169 ///
170 /// This is where debug use-before-defs would be resolved: a variable with an
171 /// unavailable value could materialize in the middle of a block, when the
172 /// value becomes available. Or, we could detect clobbers and re-specify the
173 /// variable in a backup location. (XXX these are unimplemented).
175 public:
178  /// This machine location tracker is assumed to always contain the up-to-date
179  /// value mapping for all machine locations. TransferTracker only reads
180  /// information from it. (XXX make it const?)
184 
185  /// Record of all changes in variable locations at a block position. Awkwardly
186  /// we allow inserting either before or after the point: MBB != nullptr
187  /// indicates it's before, otherwise after.
188  struct Transfer {
189  MachineBasicBlock::instr_iterator Pos; /// Position to insert DBG_VALUes
190  MachineBasicBlock *MBB; /// non-null if we should insert after.
191  SmallVector<MachineInstr *, 4> Insts; /// Vector of DBG_VALUEs to insert.
192  };
193 
197  };
198 
199  /// Collection of transfers (DBG_VALUEs) to be inserted.
201 
202  /// Local cache of what-value-is-in-what-LocIdx. Used to identify differences
203  /// between TransferTrackers view of variable locations and MLocTrackers. For
204  /// example, MLocTracker observes all clobbers, but TransferTracker lazily
205  /// does not.
207 
208  /// Map from LocIdxes to which DebugVariables are based that location.
209  /// Mantained while stepping through the block. Not accurate if
210  /// VarLocs[Idx] != MTracker->LocIdxToIDNum[Idx].
212 
213  /// Map from DebugVariable to it's current location and qualifying meta
214  /// information. To be used in conjunction with ActiveMLocs to construct
215  /// enough information for the DBG_VALUEs for a particular LocIdx.
217 
218  /// Temporary cache of DBG_VALUEs to be entered into the Transfers collection.
220 
221  /// Record of a use-before-def: created when a value that's live-in to the
222  /// current block isn't available in any machine location, but it will be
223  /// defined in this block.
224  struct UseBeforeDef {
225  /// Value of this variable, def'd in block.
227  /// Identity of this variable.
229  /// Additional variable properties.
231  };
232 
233  /// Map from instruction index (within the block) to the set of UseBeforeDefs
234  /// that become defined at that instruction.
236 
237  /// The set of variables that are in UseBeforeDefs and can become a location
238  /// once the relevant value is defined. An element being erased from this
239  /// collection prevents the use-before-def materializing.
241 
244 
247  const BitVector &CalleeSavedRegs, const TargetPassConfig &TPC)
248  : TII(TII), MTracker(MTracker), MF(MF), TRI(TRI),
249  CalleeSavedRegs(CalleeSavedRegs) {
250  TLI = MF.getSubtarget().getTargetLowering();
251  auto &TM = TPC.getTM<TargetMachine>();
252  ShouldEmitDebugEntryValues = TM.Options.ShouldEmitDebugEntryValues();
253  }
254 
255  /// Load object with live-in variable values. \p mlocs contains the live-in
256  /// values in each machine location, while \p vlocs the live-in variable
257  /// values. This method picks variable locations for the live-in variables,
258  /// creates DBG_VALUEs and puts them in #Transfers, then prepares the other
259  /// object fields to track variable locations as we step through the block.
260  /// FIXME: could just examine mloctracker instead of passing in \p mlocs?
261  void
263  const SmallVectorImpl<std::pair<DebugVariable, DbgValue>> &VLocs,
264  unsigned NumLocs) {
265  ActiveMLocs.clear();
266  ActiveVLocs.clear();
267  VarLocs.clear();
268  VarLocs.reserve(NumLocs);
269  UseBeforeDefs.clear();
270  UseBeforeDefVariables.clear();
271 
272  auto isCalleeSaved = [&](LocIdx L) {
273  unsigned Reg = MTracker->LocIdxToLocID[L];
274  if (Reg >= MTracker->NumRegs)
275  return false;
276  for (MCRegAliasIterator RAI(Reg, &TRI, true); RAI.isValid(); ++RAI)
277  if (CalleeSavedRegs.test(*RAI))
278  return true;
279  return false;
280  };
281 
282  // Map of the preferred location for each value.
283  DenseMap<ValueIDNum, LocIdx> ValueToLoc;
284 
285  // Initialized the preferred-location map with illegal locations, to be
286  // filled in later.
287  for (auto &VLoc : VLocs)
288  if (VLoc.second.Kind == DbgValue::Def)
289  ValueToLoc.insert({VLoc.second.ID, LocIdx::MakeIllegalLoc()});
290 
291  ActiveMLocs.reserve(VLocs.size());
292  ActiveVLocs.reserve(VLocs.size());
293 
294  // Produce a map of value numbers to the current machine locs they live
295  // in. When emulating VarLocBasedImpl, there should only be one
296  // location; when not, we get to pick.
297  for (auto Location : MTracker->locations()) {
298  LocIdx Idx = Location.Idx;
299  ValueIDNum &VNum = MLocs[Idx.asU64()];
300  VarLocs.push_back(VNum);
301 
302  // Is there a variable that wants a location for this value? If not, skip.
303  auto VIt = ValueToLoc.find(VNum);
304  if (VIt == ValueToLoc.end())
305  continue;
306 
307  LocIdx CurLoc = VIt->second;
308  // In order of preference, pick:
309  // * Callee saved registers,
310  // * Other registers,
311  // * Spill slots.
312  if (CurLoc.isIllegal() || MTracker->isSpill(CurLoc) ||
313  (!isCalleeSaved(CurLoc) && isCalleeSaved(Idx.asU64()))) {
314  // Insert, or overwrite if insertion failed.
315  VIt->second = Idx;
316  }
317  }
318 
319  // Now map variables to their picked LocIdxes.
320  for (const auto &Var : VLocs) {
321  if (Var.second.Kind == DbgValue::Const) {
322  PendingDbgValues.push_back(
323  emitMOLoc(*Var.second.MO, Var.first, Var.second.Properties));
324  continue;
325  }
326 
327  // If the value has no location, we can't make a variable location.
328  const ValueIDNum &Num = Var.second.ID;
329  auto ValuesPreferredLoc = ValueToLoc.find(Num);
330  if (ValuesPreferredLoc->second.isIllegal()) {
331  // If it's a def that occurs in this block, register it as a
332  // use-before-def to be resolved as we step through the block.
333  if (Num.getBlock() == (unsigned)MBB.getNumber() && !Num.isPHI())
334  addUseBeforeDef(Var.first, Var.second.Properties, Num);
335  else
336  recoverAsEntryValue(Var.first, Var.second.Properties, Num);
337  continue;
338  }
339 
340  LocIdx M = ValuesPreferredLoc->second;
341  auto NewValue = LocAndProperties{M, Var.second.Properties};
342  auto Result = ActiveVLocs.insert(std::make_pair(Var.first, NewValue));
343  if (!Result.second)
344  Result.first->second = NewValue;
345  ActiveMLocs[M].insert(Var.first);
346  PendingDbgValues.push_back(
347  MTracker->emitLoc(M, Var.first, Var.second.Properties));
348  }
349  flushDbgValues(MBB.begin(), &MBB);
350  }
351 
352  /// Record that \p Var has value \p ID, a value that becomes available
353  /// later in the function.
355  const DbgValueProperties &Properties, ValueIDNum ID) {
356  UseBeforeDef UBD = {ID, Var, Properties};
357  UseBeforeDefs[ID.getInst()].push_back(UBD);
358  UseBeforeDefVariables.insert(Var);
359  }
360 
361  /// After the instruction at index \p Inst and position \p pos has been
362  /// processed, check whether it defines a variable value in a use-before-def.
363  /// If so, and the variable value hasn't changed since the start of the
364  /// block, create a DBG_VALUE.
366  auto MIt = UseBeforeDefs.find(Inst);
367  if (MIt == UseBeforeDefs.end())
368  return;
369 
370  for (auto &Use : MIt->second) {
371  LocIdx L = Use.ID.getLoc();
372 
373  // If something goes very wrong, we might end up labelling a COPY
374  // instruction or similar with an instruction number, where it doesn't
375  // actually define a new value, instead it moves a value. In case this
376  // happens, discard.
377  if (MTracker->readMLoc(L) != Use.ID)
378  continue;
379 
380  // If a different debug instruction defined the variable value / location
381  // since the start of the block, don't materialize this use-before-def.
382  if (!UseBeforeDefVariables.count(Use.Var))
383  continue;
384 
385  PendingDbgValues.push_back(MTracker->emitLoc(L, Use.Var, Use.Properties));
386  }
387  flushDbgValues(pos, nullptr);
388  }
389 
390  /// Helper to move created DBG_VALUEs into Transfers collection.
392  if (PendingDbgValues.size() == 0)
393  return;
394 
395  // Pick out the instruction start position.
397  if (MBB && Pos == MBB->begin())
398  BundleStart = MBB->instr_begin();
399  else
400  BundleStart = getBundleStart(Pos->getIterator());
401 
402  Transfers.push_back({BundleStart, MBB, PendingDbgValues});
403  PendingDbgValues.clear();
404  }
405 
407  const DIExpression *Expr) const {
408  if (!Var.getVariable()->isParameter())
409  return false;
410 
411  if (Var.getInlinedAt())
412  return false;
413 
414  if (Expr->getNumElements() > 0)
415  return false;
416 
417  return true;
418  }
419 
420  bool isEntryValueValue(const ValueIDNum &Val) const {
421  // Must be in entry block (block number zero), and be a PHI / live-in value.
422  if (Val.getBlock() || !Val.isPHI())
423  return false;
424 
425  // Entry values must enter in a register.
426  if (MTracker->isSpill(Val.getLoc()))
427  return false;
428 
431  Register Reg = MTracker->LocIdxToLocID[Val.getLoc()];
432  return Reg != SP && Reg != FP;
433  }
434 
436  const DbgValueProperties &Prop,
437  const ValueIDNum &Num) {
438  // Is this variable location a candidate to be an entry value. First,
439  // should we be trying this at all?
440  if (!ShouldEmitDebugEntryValues)
441  return false;
442 
443  // Is the variable appropriate for entry values (i.e., is a parameter).
444  if (!isEntryValueVariable(Var, Prop.DIExpr))
445  return false;
446 
447  // Is the value assigned to this variable still the entry value?
448  if (!isEntryValueValue(Num))
449  return false;
450 
451  // Emit a variable location using an entry value expression.
454  Register Reg = MTracker->LocIdxToLocID[Num.getLoc()];
456 
457  PendingDbgValues.push_back(emitMOLoc(MO, Var, {NewExpr, Prop.Indirect}));
458  return true;
459  }
460 
461  /// Change a variable value after encountering a DBG_VALUE inside a block.
462  void redefVar(const MachineInstr &MI) {
463  DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
464  MI.getDebugLoc()->getInlinedAt());
465  DbgValueProperties Properties(MI);
466 
467  const MachineOperand &MO = MI.getOperand(0);
468 
469  // Ignore non-register locations, we don't transfer those.
470  if (!MO.isReg() || MO.getReg() == 0) {
471  auto It = ActiveVLocs.find(Var);
472  if (It != ActiveVLocs.end()) {
473  ActiveMLocs[It->second.Loc].erase(Var);
474  ActiveVLocs.erase(It);
475  }
476  // Any use-before-defs no longer apply.
477  UseBeforeDefVariables.erase(Var);
478  return;
479  }
480 
481  Register Reg = MO.getReg();
482  LocIdx NewLoc = MTracker->getRegMLoc(Reg);
483  redefVar(MI, Properties, NewLoc);
484  }
485 
486  /// Handle a change in variable location within a block. Terminate the
487  /// variables current location, and record the value it now refers to, so
488  /// that we can detect location transfers later on.
489  void redefVar(const MachineInstr &MI, const DbgValueProperties &Properties,
490  Optional<LocIdx> OptNewLoc) {
491  DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
492  MI.getDebugLoc()->getInlinedAt());
493  // Any use-before-defs no longer apply.
494  UseBeforeDefVariables.erase(Var);
495 
496  // Erase any previous location,
497  auto It = ActiveVLocs.find(Var);
498  if (It != ActiveVLocs.end())
499  ActiveMLocs[It->second.Loc].erase(Var);
500 
501  // If there _is_ no new location, all we had to do was erase.
502  if (!OptNewLoc)
503  return;
504  LocIdx NewLoc = *OptNewLoc;
505 
506  // Check whether our local copy of values-by-location in #VarLocs is out of
507  // date. Wipe old tracking data for the location if it's been clobbered in
508  // the meantime.
509  if (MTracker->readMLoc(NewLoc) != VarLocs[NewLoc.asU64()]) {
510  for (auto &P : ActiveMLocs[NewLoc]) {
511  ActiveVLocs.erase(P);
512  }
513  ActiveMLocs[NewLoc.asU64()].clear();
514  VarLocs[NewLoc.asU64()] = MTracker->readMLoc(NewLoc);
515  }
516 
517  ActiveMLocs[NewLoc].insert(Var);
518  if (It == ActiveVLocs.end()) {
519  ActiveVLocs.insert(
520  std::make_pair(Var, LocAndProperties{NewLoc, Properties}));
521  } else {
522  It->second.Loc = NewLoc;
523  It->second.Properties = Properties;
524  }
525  }
526 
527  /// Account for a location \p mloc being clobbered. Examine the variable
528  /// locations that will be terminated: and try to recover them by using
529  /// another location. Optionally, given \p MakeUndef, emit a DBG_VALUE to
530  /// explicitly terminate a location if it can't be recovered.
532  bool MakeUndef = true) {
533  auto ActiveMLocIt = ActiveMLocs.find(MLoc);
534  if (ActiveMLocIt == ActiveMLocs.end())
535  return;
536 
537  // What was the old variable value?
538  ValueIDNum OldValue = VarLocs[MLoc.asU64()];
539  VarLocs[MLoc.asU64()] = ValueIDNum::EmptyValue;
540 
541  // Examine the remaining variable locations: if we can find the same value
542  // again, we can recover the location.
543  Optional<LocIdx> NewLoc = None;
544  for (auto Loc : MTracker->locations())
545  if (Loc.Value == OldValue)
546  NewLoc = Loc.Idx;
547 
548  // If there is no location, and we weren't asked to make the variable
549  // explicitly undef, then stop here.
550  if (!NewLoc && !MakeUndef) {
551  // Try and recover a few more locations with entry values.
552  for (auto &Var : ActiveMLocIt->second) {
553  auto &Prop = ActiveVLocs.find(Var)->second.Properties;
554  recoverAsEntryValue(Var, Prop, OldValue);
555  }
556  flushDbgValues(Pos, nullptr);
557  return;
558  }
559 
560  // Examine all the variables based on this location.
561  DenseSet<DebugVariable> NewMLocs;
562  for (auto &Var : ActiveMLocIt->second) {
563  auto ActiveVLocIt = ActiveVLocs.find(Var);
564  // Re-state the variable location: if there's no replacement then NewLoc
565  // is None and a $noreg DBG_VALUE will be created. Otherwise, a DBG_VALUE
566  // identifying the alternative location will be emitted.
567  const DbgValueProperties &Properties = ActiveVLocIt->second.Properties;
568  PendingDbgValues.push_back(MTracker->emitLoc(NewLoc, Var, Properties));
569 
570  // Update machine locations <=> variable locations maps. Defer updating
571  // ActiveMLocs to avoid invalidaing the ActiveMLocIt iterator.
572  if (!NewLoc) {
573  ActiveVLocs.erase(ActiveVLocIt);
574  } else {
575  ActiveVLocIt->second.Loc = *NewLoc;
576  NewMLocs.insert(Var);
577  }
578  }
579 
580  // Commit any deferred ActiveMLoc changes.
581  if (!NewMLocs.empty())
582  for (auto &Var : NewMLocs)
583  ActiveMLocs[*NewLoc].insert(Var);
584 
585  // We lazily track what locations have which values; if we've found a new
586  // location for the clobbered value, remember it.
587  if (NewLoc)
588  VarLocs[NewLoc->asU64()] = OldValue;
589 
590  flushDbgValues(Pos, nullptr);
591 
592  // Re-find ActiveMLocIt, iterator could have been invalidated.
593  ActiveMLocIt = ActiveMLocs.find(MLoc);
594  ActiveMLocIt->second.clear();
595  }
596 
597  /// Transfer variables based on \p Src to be based on \p Dst. This handles
598  /// both register copies as well as spills and restores. Creates DBG_VALUEs
599  /// describing the movement.
601  // Does Src still contain the value num we expect? If not, it's been
602  // clobbered in the meantime, and our variable locations are stale.
603  if (VarLocs[Src.asU64()] != MTracker->readMLoc(Src))
604  return;
605 
606  // assert(ActiveMLocs[Dst].size() == 0);
607  //^^^ Legitimate scenario on account of un-clobbered slot being assigned to?
608 
609  // Move set of active variables from one location to another.
610  auto MovingVars = ActiveMLocs[Src];
611  ActiveMLocs[Dst] = MovingVars;
612  VarLocs[Dst.asU64()] = VarLocs[Src.asU64()];
613 
614  // For each variable based on Src; create a location at Dst.
615  for (auto &Var : MovingVars) {
616  auto ActiveVLocIt = ActiveVLocs.find(Var);
617  assert(ActiveVLocIt != ActiveVLocs.end());
618  ActiveVLocIt->second.Loc = Dst;
619 
620  MachineInstr *MI =
621  MTracker->emitLoc(Dst, Var, ActiveVLocIt->second.Properties);
622  PendingDbgValues.push_back(MI);
623  }
624  ActiveMLocs[Src].clear();
625  flushDbgValues(Pos, nullptr);
626 
627  // XXX XXX XXX "pretend to be old LDV" means dropping all tracking data
628  // about the old location.
629  if (EmulateOldLDV)
630  VarLocs[Src.asU64()] = ValueIDNum::EmptyValue;
631  }
632 
634  const DebugVariable &Var,
635  const DbgValueProperties &Properties) {
637  Var.getVariable()->getScope(),
638  const_cast<DILocation *>(Var.getInlinedAt()));
639  auto MIB = BuildMI(MF, DL, TII->get(TargetOpcode::DBG_VALUE));
640  MIB.add(MO);
641  if (Properties.Indirect)
642  MIB.addImm(0);
643  else
644  MIB.addReg(0);
645  MIB.addMetadata(Var.getVariable());
646  MIB.addMetadata(Properties.DIExpr);
647  return MIB;
648  }
649 };
650 
651 //===----------------------------------------------------------------------===//
652 // Implementation
653 //===----------------------------------------------------------------------===//
654 
655 ValueIDNum ValueIDNum::EmptyValue = {UINT_MAX, UINT_MAX, UINT_MAX};
656 ValueIDNum ValueIDNum::TombstoneValue = {UINT_MAX, UINT_MAX, UINT_MAX - 1};
657 
658 #ifndef NDEBUG
659 void DbgValue::dump(const MLocTracker *MTrack) const {
660  if (Kind == Const) {
661  MO->dump();
662  } else if (Kind == NoVal) {
663  dbgs() << "NoVal(" << BlockNo << ")";
664  } else if (Kind == VPHI) {
665  dbgs() << "VPHI(" << BlockNo << "," << MTrack->IDAsString(ID) << ")";
666  } else {
667  assert(Kind == Def);
668  dbgs() << MTrack->IDAsString(ID);
669  }
670  if (Properties.Indirect)
671  dbgs() << " indir";
672  if (Properties.DIExpr)
673  dbgs() << " " << *Properties.DIExpr;
674 }
675 #endif
676 
678  const TargetRegisterInfo &TRI,
679  const TargetLowering &TLI)
680  : MF(MF), TII(TII), TRI(TRI), TLI(TLI),
681  LocIdxToIDNum(ValueIDNum::EmptyValue), LocIdxToLocID(0) {
682  NumRegs = TRI.getNumRegs();
683  reset();
685  assert(NumRegs < (1u << NUM_LOC_BITS)); // Detect bit packing failure
686 
687  // Always track SP. This avoids the implicit clobbering caused by regmasks
688  // from affectings its values. (LiveDebugValues disbelieves calls and
689  // regmasks that claim to clobber SP).
691  if (SP) {
692  unsigned ID = getLocID(SP);
693  (void)lookupOrTrackRegister(ID);
694 
695  for (MCRegAliasIterator RAI(SP, &TRI, true); RAI.isValid(); ++RAI)
696  SPAliases.insert(*RAI);
697  }
698 
699  // Build some common stack positions -- full registers being spilt to the
700  // stack.
701  StackSlotIdxes.insert({{8, 0}, 0});
702  StackSlotIdxes.insert({{16, 0}, 1});
703  StackSlotIdxes.insert({{32, 0}, 2});
704  StackSlotIdxes.insert({{64, 0}, 3});
705  StackSlotIdxes.insert({{128, 0}, 4});
706  StackSlotIdxes.insert({{256, 0}, 5});
707  StackSlotIdxes.insert({{512, 0}, 6});
708 
709  // Traverse all the subregister idxes, and ensure there's an index for them.
710  // Duplicates are no problem: we're interested in their position in the
711  // stack slot, we don't want to type the slot.
712  for (unsigned int I = 1; I < TRI.getNumSubRegIndices(); ++I) {
713  unsigned Size = TRI.getSubRegIdxSize(I);
714  unsigned Offs = TRI.getSubRegIdxOffset(I);
715  unsigned Idx = StackSlotIdxes.size();
716 
717  // Some subregs have -1, -2 and so forth fed into their fields, to mean
718  // special backend things. Ignore those.
719  if (Size > 60000 || Offs > 60000)
720  continue;
721 
722  StackSlotIdxes.insert({{Size, Offs}, Idx});
723  }
724 
725  // There may also be strange register class sizes (think x86 fp80s).
726  for (const TargetRegisterClass *RC : TRI.regclasses()) {
727  unsigned Size = TRI.getRegSizeInBits(*RC);
728 
729  // We might see special reserved values as sizes, and classes for other
730  // stuff the machine tries to model. If it's more than 512 bits, then it
731  // is very unlikely to be a register than can be spilt.
732  if (Size > 512)
733  continue;
734 
735  unsigned Idx = StackSlotIdxes.size();
736  StackSlotIdxes.insert({{Size, 0}, Idx});
737  }
738 
739  for (auto &Idx : StackSlotIdxes)
740  StackIdxesToPos[Idx.second] = Idx.first;
741 
743 }
744 
746  assert(ID != 0);
747  LocIdx NewIdx = LocIdx(LocIdxToIDNum.size());
748  LocIdxToIDNum.grow(NewIdx);
749  LocIdxToLocID.grow(NewIdx);
750 
751  // Default: it's an mphi.
752  ValueIDNum ValNum = {CurBB, 0, NewIdx};
753  // Was this reg ever touched by a regmask?
754  for (const auto &MaskPair : reverse(Masks)) {
755  if (MaskPair.first->clobbersPhysReg(ID)) {
756  // There was an earlier def we skipped.
757  ValNum = {CurBB, MaskPair.second, NewIdx};
758  break;
759  }
760  }
761 
762  LocIdxToIDNum[NewIdx] = ValNum;
763  LocIdxToLocID[NewIdx] = ID;
764  return NewIdx;
765 }
766 
767 void MLocTracker::writeRegMask(const MachineOperand *MO, unsigned CurBB,
768  unsigned InstID) {
769  // Def any register we track have that isn't preserved. The regmask
770  // terminates the liveness of a register, meaning its value can't be
771  // relied upon -- we represent this by giving it a new value.
772  for (auto Location : locations()) {
773  unsigned ID = LocIdxToLocID[Location.Idx];
774  // Don't clobber SP, even if the mask says it's clobbered.
775  if (ID < NumRegs && !SPAliases.count(ID) && MO->clobbersPhysReg(ID))
776  defReg(ID, CurBB, InstID);
777  }
778  Masks.push_back(std::make_pair(MO, InstID));
779 }
780 
782  SpillLocationNo SpillID(SpillLocs.idFor(L));
783 
784  if (SpillID.id() == 0) {
785  // If there is no location, and we have reached the limit of how many stack
786  // slots to track, then don't track this one.
787  if (SpillLocs.size() >= StackWorkingSetLimit)
788  return None;
789 
790  // Spill location is untracked: create record for this one, and all
791  // subregister slots too.
792  SpillID = SpillLocationNo(SpillLocs.insert(L));
793  for (unsigned StackIdx = 0; StackIdx < NumSlotIdxes; ++StackIdx) {
794  unsigned L = getSpillIDWithIdx(SpillID, StackIdx);
795  LocIdx Idx = LocIdx(LocIdxToIDNum.size()); // New idx
796  LocIdxToIDNum.grow(Idx);
797  LocIdxToLocID.grow(Idx);
798  LocIDToLocIdx.push_back(Idx);
799  LocIdxToLocID[Idx] = L;
800  // Initialize to PHI value; corresponds to the location's live-in value
801  // during transfer function construction.
802  LocIdxToIDNum[Idx] = ValueIDNum(CurBB, 0, Idx);
803  }
804  }
805  return SpillID;
806 }
807 
808 std::string MLocTracker::LocIdxToName(LocIdx Idx) const {
809  unsigned ID = LocIdxToLocID[Idx];
810  if (ID >= NumRegs) {
812  ID -= NumRegs;
813  unsigned Slot = ID / NumSlotIdxes;
814  return Twine("slot ")
815  .concat(Twine(Slot).concat(Twine(" sz ").concat(Twine(Pos.first)
816  .concat(Twine(" offs ").concat(Twine(Pos.second))))))
817  .str();
818  } else {
819  return TRI.getRegAsmName(ID).str();
820  }
821 }
822 
823 std::string MLocTracker::IDAsString(const ValueIDNum &Num) const {
824  std::string DefName = LocIdxToName(Num.getLoc());
825  return Num.asString(DefName);
826 }
827 
828 #ifndef NDEBUG
830  for (auto Location : locations()) {
831  std::string MLocName = LocIdxToName(Location.Value.getLoc());
832  std::string DefName = Location.Value.asString(MLocName);
833  dbgs() << LocIdxToName(Location.Idx) << " --> " << DefName << "\n";
834  }
835 }
836 
838  for (auto Location : locations()) {
839  std::string foo = LocIdxToName(Location.Idx);
840  dbgs() << "Idx " << Location.Idx.asU64() << " " << foo << "\n";
841  }
842 }
843 #endif
844 
846  const DebugVariable &Var,
847  const DbgValueProperties &Properties) {
849  Var.getVariable()->getScope(),
850  const_cast<DILocation *>(Var.getInlinedAt()));
851  auto MIB = BuildMI(MF, DL, TII.get(TargetOpcode::DBG_VALUE));
852 
853  const DIExpression *Expr = Properties.DIExpr;
854  if (!MLoc) {
855  // No location -> DBG_VALUE $noreg
856  MIB.addReg(0);
857  MIB.addReg(0);
858  } else if (LocIdxToLocID[*MLoc] >= NumRegs) {
859  unsigned LocID = LocIdxToLocID[*MLoc];
860  SpillLocationNo SpillID = locIDToSpill(LocID);
861  StackSlotPos StackIdx = locIDToSpillIdx(LocID);
862  unsigned short Offset = StackIdx.second;
863 
864  // TODO: support variables that are located in spill slots, with non-zero
865  // offsets from the start of the spill slot. It would require some more
866  // complex DIExpression calculations. This doesn't seem to be produced by
867  // LLVM right now, so don't try and support it.
868  // Accept no-subregister slots and subregisters where the offset is zero.
869  // The consumer should already have type information to work out how large
870  // the variable is.
871  if (Offset == 0) {
872  const SpillLoc &Spill = SpillLocs[SpillID.id()];
873  unsigned Base = Spill.SpillBase;
874  MIB.addReg(Base);
875 
876  // There are several ways we can dereference things, and several inputs
877  // to consider:
878  // * NRVO variables will appear with IsIndirect set, but should have
879  // nothing else in their DIExpressions,
880  // * Variables with DW_OP_stack_value in their expr already need an
881  // explicit dereference of the stack location,
882  // * Values that don't match the variable size need DW_OP_deref_size,
883  // * Everything else can just become a simple location expression.
884 
885  // We need to use deref_size whenever there's a mismatch between the
886  // size of value and the size of variable portion being read.
887  // Additionally, we should use it whenever dealing with stack_value
888  // fragments, to avoid the consumer having to determine the deref size
889  // from DW_OP_piece.
890  bool UseDerefSize = false;
891  unsigned ValueSizeInBits = getLocSizeInBits(*MLoc);
892  unsigned DerefSizeInBytes = ValueSizeInBits / 8;
893  if (auto Fragment = Var.getFragment()) {
894  unsigned VariableSizeInBits = Fragment->SizeInBits;
895  if (VariableSizeInBits != ValueSizeInBits || Expr->isComplex())
896  UseDerefSize = true;
897  } else if (auto Size = Var.getVariable()->getSizeInBits()) {
898  if (*Size != ValueSizeInBits) {
899  UseDerefSize = true;
900  }
901  }
902 
903  if (Properties.Indirect) {
904  // This is something like an NRVO variable, where the pointer has been
905  // spilt to the stack, or a dbg.addr pointing at a coroutine frame
906  // field. It should end up being a memory location, with the pointer
907  // to the variable loaded off the stack with a deref. It can't be a
908  // DW_OP_stack_value expression.
909  assert(!Expr->isImplicit());
911  Expr, DIExpression::ApplyOffset | DIExpression::DerefAfter,
912  Spill.SpillOffset);
913  MIB.addImm(0);
914  } else if (UseDerefSize) {
915  // We're loading a value off the stack that's not the same size as the
916  // variable. Add / subtract stack offset, explicitly deref with a size,
917  // and add DW_OP_stack_value if not already present.
918  SmallVector<uint64_t, 2> Ops = {dwarf::DW_OP_deref_size,
919  DerefSizeInBytes};
920  Expr = DIExpression::prependOpcodes(Expr, Ops, true);
921  unsigned Flags = DIExpression::StackValue | DIExpression::ApplyOffset;
922  Expr = TRI.prependOffsetExpression(Expr, Flags, Spill.SpillOffset);
923  MIB.addReg(0);
924  } else if (Expr->isComplex()) {
925  // A variable with no size ambiguity, but with extra elements in it's
926  // expression. Manually dereference the stack location.
927  assert(Expr->isComplex());
929  Expr, DIExpression::ApplyOffset | DIExpression::DerefAfter,
930  Spill.SpillOffset);
931  MIB.addReg(0);
932  } else {
933  // A plain value that has been spilt to the stack, with no further
934  // context. Request a location expression, marking the DBG_VALUE as
935  // IsIndirect.
936  Expr = TRI.prependOffsetExpression(Expr, DIExpression::ApplyOffset,
937  Spill.SpillOffset);
938  MIB.addImm(0);
939  }
940  } else {
941  // This is a stack location with a weird subregister offset: emit an undef
942  // DBG_VALUE instead.
943  MIB.addReg(0);
944  MIB.addReg(0);
945  }
946  } else {
947  // Non-empty, non-stack slot, must be a plain register.
948  unsigned LocID = LocIdxToLocID[*MLoc];
949  MIB.addReg(LocID);
950  if (Properties.Indirect)
951  MIB.addImm(0);
952  else
953  MIB.addReg(0);
954  }
955 
956  MIB.addMetadata(Var.getVariable());
957  MIB.addMetadata(Expr);
958  return MIB;
959 }
960 
961 /// Default construct and initialize the pass.
963 
965  unsigned Reg = MTracker->LocIdxToLocID[L];
966  for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
967  if (CalleeSavedRegs.test(*RAI))
968  return true;
969  return false;
970 }
971 
972 //===----------------------------------------------------------------------===//
973 // Debug Range Extension Implementation
974 //===----------------------------------------------------------------------===//
975 
976 #ifndef NDEBUG
977 // Something to restore in the future.
978 // void InstrRefBasedLDV::printVarLocInMBB(..)
979 #endif
980 
982 InstrRefBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
983  assert(MI.hasOneMemOperand() &&
984  "Spill instruction does not have exactly one memory operand?");
985  auto MMOI = MI.memoperands_begin();
986  const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
987  assert(PVal->kind() == PseudoSourceValue::FixedStack &&
988  "Inconsistent memory operand in spill instruction");
989  int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
990  const MachineBasicBlock *MBB = MI.getParent();
991  Register Reg;
992  StackOffset Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg);
993  return MTracker->getOrTrackSpillLoc({Reg, Offset});
994 }
995 
998  Optional<SpillLocationNo> SpillLoc = extractSpillBaseRegAndOffset(MI);
999  if (!SpillLoc)
1000  return None;
1001 
1002  // Where in the stack slot is this value defined -- i.e., what size of value
1003  // is this? An important question, because it could be loaded into a register
1004  // from the stack at some point. Happily the memory operand will tell us
1005  // the size written to the stack.
1006  auto *MemOperand = *MI.memoperands_begin();
1007  unsigned SizeInBits = MemOperand->getSizeInBits();
1008 
1009  // Find that position in the stack indexes we're tracking.
1010  auto IdxIt = MTracker->StackSlotIdxes.find({SizeInBits, 0});
1011  if (IdxIt == MTracker->StackSlotIdxes.end())
1012  // That index is not tracked. This is suprising, and unlikely to ever
1013  // occur, but the safe action is to indicate the variable is optimised out.
1014  return None;
1015 
1016  unsigned SpillID = MTracker->getSpillIDWithIdx(*SpillLoc, IdxIt->second);
1017  return MTracker->getSpillMLoc(SpillID);
1018 }
1019 
1020 /// End all previous ranges related to @MI and start a new range from @MI
1021 /// if it is a DBG_VALUE instr.
1022 bool InstrRefBasedLDV::transferDebugValue(const MachineInstr &MI) {
1023  if (!MI.isDebugValue())
1024  return false;
1025 
1026  const DILocalVariable *Var = MI.getDebugVariable();
1027  const DIExpression *Expr = MI.getDebugExpression();
1028  const DILocation *DebugLoc = MI.getDebugLoc();
1029  const DILocation *InlinedAt = DebugLoc->getInlinedAt();
1031  "Expected inlined-at fields to agree");
1032 
1033  DebugVariable V(Var, Expr, InlinedAt);
1034  DbgValueProperties Properties(MI);
1035 
1036  // If there are no instructions in this lexical scope, do no location tracking
1037  // at all, this variable shouldn't get a legitimate location range.
1038  auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get());
1039  if (Scope == nullptr)
1040  return true; // handled it; by doing nothing
1041 
1042  // For now, ignore DBG_VALUE_LISTs when extending ranges. Allow it to
1043  // contribute to locations in this block, but don't propagate further.
1044  // Interpret it like a DBG_VALUE $noreg.
1045  if (MI.isDebugValueList()) {
1046  if (VTracker)
1047  VTracker->defVar(MI, Properties, None);
1048  if (TTracker)
1049  TTracker->redefVar(MI, Properties, None);
1050  return true;
1051  }
1052 
1053  const MachineOperand &MO = MI.getOperand(0);
1054 
1055  // MLocTracker needs to know that this register is read, even if it's only
1056  // read by a debug inst.
1057  if (MO.isReg() && MO.getReg() != 0)
1058  (void)MTracker->readReg(MO.getReg());
1059 
1060  // If we're preparing for the second analysis (variables), the machine value
1061  // locations are already solved, and we report this DBG_VALUE and the value
1062  // it refers to to VLocTracker.
1063  if (VTracker) {
1064  if (MO.isReg()) {
1065  // Feed defVar the new variable location, or if this is a
1066  // DBG_VALUE $noreg, feed defVar None.
1067  if (MO.getReg())
1068  VTracker->defVar(MI, Properties, MTracker->readReg(MO.getReg()));
1069  else
1070  VTracker->defVar(MI, Properties, None);
1071  } else if (MI.getOperand(0).isImm() || MI.getOperand(0).isFPImm() ||
1072  MI.getOperand(0).isCImm()) {
1073  VTracker->defVar(MI, MI.getOperand(0));
1074  }
1075  }
1076 
1077  // If performing final tracking of transfers, report this variable definition
1078  // to the TransferTracker too.
1079  if (TTracker)
1080  TTracker->redefVar(MI);
1081  return true;
1082 }
1083 
1084 bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI,
1085  const ValueTable *MLiveOuts,
1086  const ValueTable *MLiveIns) {
1087  if (!MI.isDebugRef())
1088  return false;
1089 
1090  // Only handle this instruction when we are building the variable value
1091  // transfer function.
1092  if (!VTracker && !TTracker)
1093  return false;
1094 
1095  unsigned InstNo = MI.getOperand(0).getImm();
1096  unsigned OpNo = MI.getOperand(1).getImm();
1097 
1098  const DILocalVariable *Var = MI.getDebugVariable();
1099  const DIExpression *Expr = MI.getDebugExpression();
1100  const DILocation *DebugLoc = MI.getDebugLoc();
1101  const DILocation *InlinedAt = DebugLoc->getInlinedAt();
1103  "Expected inlined-at fields to agree");
1104 
1105  DebugVariable V(Var, Expr, InlinedAt);
1106 
1107  auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get());
1108  if (Scope == nullptr)
1109  return true; // Handled by doing nothing. This variable is never in scope.
1110 
1111  const MachineFunction &MF = *MI.getParent()->getParent();
1112 
1113  // Various optimizations may have happened to the value during codegen,
1114  // recorded in the value substitution table. Apply any substitutions to
1115  // the instruction / operand number in this DBG_INSTR_REF, and collect
1116  // any subregister extractions performed during optimization.
1117 
1118  // Create dummy substitution with Src set, for lookup.
1119  auto SoughtSub =
1120  MachineFunction::DebugSubstitution({InstNo, OpNo}, {0, 0}, 0);
1121 
1122  SmallVector<unsigned, 4> SeenSubregs;
1123  auto LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub);
1124  while (LowerBoundIt != MF.DebugValueSubstitutions.end() &&
1125  LowerBoundIt->Src == SoughtSub.Src) {
1126  std::tie(InstNo, OpNo) = LowerBoundIt->Dest;
1127  SoughtSub.Src = LowerBoundIt->Dest;
1128  if (unsigned Subreg = LowerBoundIt->Subreg)
1129  SeenSubregs.push_back(Subreg);
1130  LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub);
1131  }
1132 
1133  // Default machine value number is <None> -- if no instruction defines
1134  // the corresponding value, it must have been optimized out.
1135  Optional<ValueIDNum> NewID = None;
1136 
1137  // Try to lookup the instruction number, and find the machine value number
1138  // that it defines. It could be an instruction, or a PHI.
1139  auto InstrIt = DebugInstrNumToInstr.find(InstNo);
1140  auto PHIIt = std::lower_bound(DebugPHINumToValue.begin(),
1141  DebugPHINumToValue.end(), InstNo);
1142  if (InstrIt != DebugInstrNumToInstr.end()) {
1143  const MachineInstr &TargetInstr = *InstrIt->second.first;
1144  uint64_t BlockNo = TargetInstr.getParent()->getNumber();
1145 
1146  // Pick out the designated operand. It might be a memory reference, if
1147  // a register def was folded into a stack store.
1148  if (OpNo == MachineFunction::DebugOperandMemNumber &&
1149  TargetInstr.hasOneMemOperand()) {
1151  if (L)
1152  NewID = ValueIDNum(BlockNo, InstrIt->second.second, *L);
1153  } else if (OpNo != MachineFunction::DebugOperandMemNumber) {
1154  // Permit the debug-info to be completely wrong: identifying a nonexistant
1155  // operand, or one that is not a register definition, means something
1156  // unexpected happened during optimisation. Broken debug-info, however,
1157  // shouldn't crash the compiler -- instead leave the variable value as
1158  // None, which will make it appear "optimised out".
1159  if (OpNo < TargetInstr.getNumOperands()) {
1160  const MachineOperand &MO = TargetInstr.getOperand(OpNo);
1161 
1162  if (MO.isReg() && MO.isDef() && MO.getReg()) {
1163  unsigned LocID = MTracker->getLocID(MO.getReg());
1164  LocIdx L = MTracker->LocIDToLocIdx[LocID];
1165  NewID = ValueIDNum(BlockNo, InstrIt->second.second, L);
1166  }
1167  }
1168 
1169  if (!NewID) {
1170  LLVM_DEBUG(
1171  { dbgs() << "Seen instruction reference to illegal operand\n"; });
1172  }
1173  }
1174  // else: NewID is left as None.
1175  } else if (PHIIt != DebugPHINumToValue.end() && PHIIt->InstrNum == InstNo) {
1176  // It's actually a PHI value. Which value it is might not be obvious, use
1177  // the resolver helper to find out.
1178  NewID = resolveDbgPHIs(*MI.getParent()->getParent(), MLiveOuts, MLiveIns,
1179  MI, InstNo);
1180  }
1181 
1182  // Apply any subregister extractions, in reverse. We might have seen code
1183  // like this:
1184  // CALL64 @foo, implicit-def $rax
1185  // %0:gr64 = COPY $rax
1186  // %1:gr32 = COPY %0.sub_32bit
1187  // %2:gr16 = COPY %1.sub_16bit
1188  // %3:gr8 = COPY %2.sub_8bit
1189  // In which case each copy would have been recorded as a substitution with
1190  // a subregister qualifier. Apply those qualifiers now.
1191  if (NewID && !SeenSubregs.empty()) {
1192  unsigned Offset = 0;
1193  unsigned Size = 0;
1194 
1195  // Look at each subregister that we passed through, and progressively
1196  // narrow in, accumulating any offsets that occur. Substitutions should
1197  // only ever be the same or narrower width than what they read from;
1198  // iterate in reverse order so that we go from wide to small.
1199  for (unsigned Subreg : reverse(SeenSubregs)) {
1200  unsigned ThisSize = TRI->getSubRegIdxSize(Subreg);
1201  unsigned ThisOffset = TRI->getSubRegIdxOffset(Subreg);
1202  Offset += ThisOffset;
1203  Size = (Size == 0) ? ThisSize : std::min(Size, ThisSize);
1204  }
1205 
1206  // If that worked, look for an appropriate subregister with the register
1207  // where the define happens. Don't look at values that were defined during
1208  // a stack write: we can't currently express register locations within
1209  // spills.
1210  LocIdx L = NewID->getLoc();
1211  if (NewID && !MTracker->isSpill(L)) {
1212  // Find the register class for the register where this def happened.
1213  // FIXME: no index for this?
1214  Register Reg = MTracker->LocIdxToLocID[L];
1215  const TargetRegisterClass *TRC = nullptr;
1216  for (auto *TRCI : TRI->regclasses())
1217  if (TRCI->contains(Reg))
1218  TRC = TRCI;
1219  assert(TRC && "Couldn't find target register class?");
1220 
1221  // If the register we have isn't the right size or in the right place,
1222  // Try to find a subregister inside it.
1223  unsigned MainRegSize = TRI->getRegSizeInBits(*TRC);
1224  if (Size != MainRegSize || Offset) {
1225  // Enumerate all subregisters, searching.
1226  Register NewReg = 0;
1227  for (MCSubRegIterator SRI(Reg, TRI, false); SRI.isValid(); ++SRI) {
1228  unsigned Subreg = TRI->getSubRegIndex(Reg, *SRI);
1229  unsigned SubregSize = TRI->getSubRegIdxSize(Subreg);
1230  unsigned SubregOffset = TRI->getSubRegIdxOffset(Subreg);
1231  if (SubregSize == Size && SubregOffset == Offset) {
1232  NewReg = *SRI;
1233  break;
1234  }
1235  }
1236 
1237  // If we didn't find anything: there's no way to express our value.
1238  if (!NewReg) {
1239  NewID = None;
1240  } else {
1241  // Re-state the value as being defined within the subregister
1242  // that we found.
1243  LocIdx NewLoc = MTracker->lookupOrTrackRegister(NewReg);
1244  NewID = ValueIDNum(NewID->getBlock(), NewID->getInst(), NewLoc);
1245  }
1246  }
1247  } else {
1248  // If we can't handle subregisters, unset the new value.
1249  NewID = None;
1250  }
1251  }
1252 
1253  // We, we have a value number or None. Tell the variable value tracker about
1254  // it. The rest of this LiveDebugValues implementation acts exactly the same
1255  // for DBG_INSTR_REFs as DBG_VALUEs (just, the former can refer to values that
1256  // aren't immediately available).
1257  DbgValueProperties Properties(Expr, false);
1258  if (VTracker)
1259  VTracker->defVar(MI, Properties, NewID);
1260 
1261  // If we're on the final pass through the function, decompose this INSTR_REF
1262  // into a plain DBG_VALUE.
1263  if (!TTracker)
1264  return true;
1265 
1266  // Pick a location for the machine value number, if such a location exists.
1267  // (This information could be stored in TransferTracker to make it faster).
1268  Optional<LocIdx> FoundLoc = None;
1269  for (auto Location : MTracker->locations()) {
1270  LocIdx CurL = Location.Idx;
1271  ValueIDNum ID = MTracker->readMLoc(CurL);
1272  if (NewID && ID == NewID) {
1273  // If this is the first location with that value, pick it. Otherwise,
1274  // consider whether it's a "longer term" location.
1275  if (!FoundLoc) {
1276  FoundLoc = CurL;
1277  continue;
1278  }
1279 
1280  if (MTracker->isSpill(CurL))
1281  FoundLoc = CurL; // Spills are a longer term location.
1282  else if (!MTracker->isSpill(*FoundLoc) &&
1283  !MTracker->isSpill(CurL) &&
1284  !isCalleeSaved(*FoundLoc) &&
1285  isCalleeSaved(CurL))
1286  FoundLoc = CurL; // Callee saved regs are longer term than normal.
1287  }
1288  }
1289 
1290  // Tell transfer tracker that the variable value has changed.
1291  TTracker->redefVar(MI, Properties, FoundLoc);
1292 
1293  // If there was a value with no location; but the value is defined in a
1294  // later instruction in this block, this is a block-local use-before-def.
1295  if (!FoundLoc && NewID && NewID->getBlock() == CurBB &&
1296  NewID->getInst() > CurInst)
1297  TTracker->addUseBeforeDef(V, {MI.getDebugExpression(), false}, *NewID);
1298 
1299  // Produce a DBG_VALUE representing what this DBG_INSTR_REF meant.
1300  // This DBG_VALUE is potentially a $noreg / undefined location, if
1301  // FoundLoc is None.
1302  // (XXX -- could morph the DBG_INSTR_REF in the future).
1303  MachineInstr *DbgMI = MTracker->emitLoc(FoundLoc, V, Properties);
1304  TTracker->PendingDbgValues.push_back(DbgMI);
1305  TTracker->flushDbgValues(MI.getIterator(), nullptr);
1306  return true;
1307 }
1308 
1309 bool InstrRefBasedLDV::transferDebugPHI(MachineInstr &MI) {
1310  if (!MI.isDebugPHI())
1311  return false;
1312 
1313  // Analyse these only when solving the machine value location problem.
1314  if (VTracker || TTracker)
1315  return true;
1316 
1317  // First operand is the value location, either a stack slot or register.
1318  // Second is the debug instruction number of the original PHI.
1319  const MachineOperand &MO = MI.getOperand(0);
1320  unsigned InstrNum = MI.getOperand(1).getImm();
1321 
1322  auto EmitBadPHI = [this, &MI, InstrNum](void) -> bool {
1323  // Helper lambda to do any accounting when we fail to find a location for
1324  // a DBG_PHI. This can happen if DBG_PHIs are malformed, or refer to a
1325  // dead stack slot, for example.
1326  // Record a DebugPHIRecord with an empty value + location.
1327  DebugPHINumToValue.push_back({InstrNum, MI.getParent(), None, None});
1328  return true;
1329  };
1330 
1331  if (MO.isReg() && MO.getReg()) {
1332  // The value is whatever's currently in the register. Read and record it,
1333  // to be analysed later.
1334  Register Reg = MO.getReg();
1335  ValueIDNum Num = MTracker->readReg(Reg);
1336  auto PHIRec = DebugPHIRecord(
1337  {InstrNum, MI.getParent(), Num, MTracker->lookupOrTrackRegister(Reg)});
1338  DebugPHINumToValue.push_back(PHIRec);
1339 
1340  // Ensure this register is tracked.
1341  for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
1342  MTracker->lookupOrTrackRegister(*RAI);
1343  } else if (MO.isFI()) {
1344  // The value is whatever's in this stack slot.
1345  unsigned FI = MO.getIndex();
1346 
1347  // If the stack slot is dead, then this was optimized away.
1348  // FIXME: stack slot colouring should account for slots that get merged.
1349  if (MFI->isDeadObjectIndex(FI))
1350  return EmitBadPHI();
1351 
1352  // Identify this spill slot, ensure it's tracked.
1353  Register Base;
1354  StackOffset Offs = TFI->getFrameIndexReference(*MI.getMF(), FI, Base);
1355  SpillLoc SL = {Base, Offs};
1356  Optional<SpillLocationNo> SpillNo = MTracker->getOrTrackSpillLoc(SL);
1357 
1358  // We might be able to find a value, but have chosen not to, to avoid
1359  // tracking too much stack information.
1360  if (!SpillNo)
1361  return EmitBadPHI();
1362 
1363  // Any stack location DBG_PHI should have an associate bit-size.
1364  assert(MI.getNumOperands() == 3 && "Stack DBG_PHI with no size?");
1365  unsigned slotBitSize = MI.getOperand(2).getImm();
1366 
1367  unsigned SpillID = MTracker->getLocID(*SpillNo, {slotBitSize, 0});
1368  LocIdx SpillLoc = MTracker->getSpillMLoc(SpillID);
1369  ValueIDNum Result = MTracker->readMLoc(SpillLoc);
1370 
1371  // Record this DBG_PHI for later analysis.
1372  auto DbgPHI = DebugPHIRecord({InstrNum, MI.getParent(), Result, SpillLoc});
1373  DebugPHINumToValue.push_back(DbgPHI);
1374  } else {
1375  // Else: if the operand is neither a legal register or a stack slot, then
1376  // we're being fed illegal debug-info. Record an empty PHI, so that any
1377  // debug users trying to read this number will be put off trying to
1378  // interpret the value.
1379  LLVM_DEBUG(
1380  { dbgs() << "Seen DBG_PHI with unrecognised operand format\n"; });
1381  return EmitBadPHI();
1382  }
1383 
1384  return true;
1385 }
1386 
1387 void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) {
1388  // Meta Instructions do not affect the debug liveness of any register they
1389  // define.
1390  if (MI.isImplicitDef()) {
1391  // Except when there's an implicit def, and the location it's defining has
1392  // no value number. The whole point of an implicit def is to announce that
1393  // the register is live, without be specific about it's value. So define
1394  // a value if there isn't one already.
1395  ValueIDNum Num = MTracker->readReg(MI.getOperand(0).getReg());
1396  // Has a legitimate value -> ignore the implicit def.
1397  if (Num.getLoc() != 0)
1398  return;
1399  // Otherwise, def it here.
1400  } else if (MI.isMetaInstruction())
1401  return;
1402 
1403  // We always ignore SP defines on call instructions, they don't actually
1404  // change the value of the stack pointer... except for win32's _chkstk. This
1405  // is rare: filter quickly for the common case (no stack adjustments, not a
1406  // call, etc). If it is a call that modifies SP, recognise the SP register
1407  // defs.
1408  bool CallChangesSP = false;
1409  if (AdjustsStackInCalls && MI.isCall() && MI.getOperand(0).isSymbol() &&
1410  !strcmp(MI.getOperand(0).getSymbolName(), StackProbeSymbolName.data()))
1411  CallChangesSP = true;
1412 
1413  // Test whether we should ignore a def of this register due to it being part
1414  // of the stack pointer.
1415  auto IgnoreSPAlias = [this, &MI, CallChangesSP](Register R) -> bool {
1416  if (CallChangesSP)
1417  return false;
1418  return MI.isCall() && MTracker->SPAliases.count(R);
1419  };
1420 
1421  // Find the regs killed by MI, and find regmasks of preserved regs.
1422  // Max out the number of statically allocated elements in `DeadRegs`, as this
1423  // prevents fallback to std::set::count() operations.
1424  SmallSet<uint32_t, 32> DeadRegs;
1427  for (const MachineOperand &MO : MI.operands()) {
1428  // Determine whether the operand is a register def.
1429  if (MO.isReg() && MO.isDef() && MO.getReg() &&
1430  Register::isPhysicalRegister(MO.getReg()) &&
1431  !IgnoreSPAlias(MO.getReg())) {
1432  // Remove ranges of all aliased registers.
1433  for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
1434  // FIXME: Can we break out of this loop early if no insertion occurs?
1435  DeadRegs.insert(*RAI);
1436  } else if (MO.isRegMask()) {
1437  RegMasks.push_back(MO.getRegMask());
1438  RegMaskPtrs.push_back(&MO);
1439  }
1440  }
1441 
1442  // Tell MLocTracker about all definitions, of regmasks and otherwise.
1443  for (uint32_t DeadReg : DeadRegs)
1444  MTracker->defReg(DeadReg, CurBB, CurInst);
1445 
1446  for (auto *MO : RegMaskPtrs)
1447  MTracker->writeRegMask(MO, CurBB, CurInst);
1448 
1449  // If this instruction writes to a spill slot, def that slot.
1450  if (hasFoldedStackStore(MI)) {
1451  if (Optional<SpillLocationNo> SpillNo = extractSpillBaseRegAndOffset(MI)) {
1452  for (unsigned int I = 0; I < MTracker->NumSlotIdxes; ++I) {
1453  unsigned SpillID = MTracker->getSpillIDWithIdx(*SpillNo, I);
1454  LocIdx L = MTracker->getSpillMLoc(SpillID);
1455  MTracker->setMLoc(L, ValueIDNum(CurBB, CurInst, L));
1456  }
1457  }
1458  }
1459 
1460  if (!TTracker)
1461  return;
1462 
1463  // When committing variable values to locations: tell transfer tracker that
1464  // we've clobbered things. It may be able to recover the variable from a
1465  // different location.
1466 
1467  // Inform TTracker about any direct clobbers.
1468  for (uint32_t DeadReg : DeadRegs) {
1469  LocIdx Loc = MTracker->lookupOrTrackRegister(DeadReg);
1470  TTracker->clobberMloc(Loc, MI.getIterator(), false);
1471  }
1472 
1473  // Look for any clobbers performed by a register mask. Only test locations
1474  // that are actually being tracked.
1475  if (!RegMaskPtrs.empty()) {
1476  for (auto L : MTracker->locations()) {
1477  // Stack locations can't be clobbered by regmasks.
1478  if (MTracker->isSpill(L.Idx))
1479  continue;
1480 
1481  Register Reg = MTracker->LocIdxToLocID[L.Idx];
1482  if (IgnoreSPAlias(Reg))
1483  continue;
1484 
1485  for (auto *MO : RegMaskPtrs)
1486  if (MO->clobbersPhysReg(Reg))
1487  TTracker->clobberMloc(L.Idx, MI.getIterator(), false);
1488  }
1489  }
1490 
1491  // Tell TTracker about any folded stack store.
1492  if (hasFoldedStackStore(MI)) {
1493  if (Optional<SpillLocationNo> SpillNo = extractSpillBaseRegAndOffset(MI)) {
1494  for (unsigned int I = 0; I < MTracker->NumSlotIdxes; ++I) {
1495  unsigned SpillID = MTracker->getSpillIDWithIdx(*SpillNo, I);
1496  LocIdx L = MTracker->getSpillMLoc(SpillID);
1497  TTracker->clobberMloc(L, MI.getIterator(), true);
1498  }
1499  }
1500  }
1501 }
1502 
1503 void InstrRefBasedLDV::performCopy(Register SrcRegNum, Register DstRegNum) {
1504  // In all circumstances, re-def all aliases. It's definitely a new value now.
1505  for (MCRegAliasIterator RAI(DstRegNum, TRI, true); RAI.isValid(); ++RAI)
1506  MTracker->defReg(*RAI, CurBB, CurInst);
1507 
1508  ValueIDNum SrcValue = MTracker->readReg(SrcRegNum);
1509  MTracker->setReg(DstRegNum, SrcValue);
1510 
1511  // Copy subregisters from one location to another.
1512  for (MCSubRegIndexIterator SRI(SrcRegNum, TRI); SRI.isValid(); ++SRI) {
1513  unsigned SrcSubReg = SRI.getSubReg();
1514  unsigned SubRegIdx = SRI.getSubRegIndex();
1515  unsigned DstSubReg = TRI->getSubReg(DstRegNum, SubRegIdx);
1516  if (!DstSubReg)
1517  continue;
1518 
1519  // Do copy. There are two matching subregisters, the source value should
1520  // have been def'd when the super-reg was, the latter might not be tracked
1521  // yet.
1522  // This will force SrcSubReg to be tracked, if it isn't yet. Will read
1523  // mphi values if it wasn't tracked.
1524  LocIdx SrcL = MTracker->lookupOrTrackRegister(SrcSubReg);
1525  LocIdx DstL = MTracker->lookupOrTrackRegister(DstSubReg);
1526  (void)SrcL;
1527  (void)DstL;
1528  ValueIDNum CpyValue = MTracker->readReg(SrcSubReg);
1529 
1530  MTracker->setReg(DstSubReg, CpyValue);
1531  }
1532 }
1533 
1535 InstrRefBasedLDV::isSpillInstruction(const MachineInstr &MI,
1536  MachineFunction *MF) {
1537  // TODO: Handle multiple stores folded into one.
1538  if (!MI.hasOneMemOperand())
1539  return None;
1540 
1541  // Reject any memory operand that's aliased -- we can't guarantee its value.
1542  auto MMOI = MI.memoperands_begin();
1543  const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
1544  if (PVal->isAliased(MFI))
1545  return None;
1546 
1547  if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII))
1548  return None; // This is not a spill instruction, since no valid size was
1549  // returned from either function.
1550 
1551  return extractSpillBaseRegAndOffset(MI);
1552 }
1553 
1554 bool InstrRefBasedLDV::isLocationSpill(const MachineInstr &MI,
1555  MachineFunction *MF, unsigned &Reg) {
1556  if (!isSpillInstruction(MI, MF))
1557  return false;
1558 
1559  int FI;
1560  Reg = TII->isStoreToStackSlotPostFE(MI, FI);
1561  return Reg != 0;
1562 }
1563 
1565 InstrRefBasedLDV::isRestoreInstruction(const MachineInstr &MI,
1566  MachineFunction *MF, unsigned &Reg) {
1567  if (!MI.hasOneMemOperand())
1568  return None;
1569 
1570  // FIXME: Handle folded restore instructions with more than one memory
1571  // operand.
1572  if (MI.getRestoreSize(TII)) {
1573  Reg = MI.getOperand(0).getReg();
1574  return extractSpillBaseRegAndOffset(MI);
1575  }
1576  return None;
1577 }
1578 
1579 bool InstrRefBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI) {
1580  // XXX -- it's too difficult to implement VarLocBasedImpl's stack location
1581  // limitations under the new model. Therefore, when comparing them, compare
1582  // versions that don't attempt spills or restores at all.
1583  if (EmulateOldLDV)
1584  return false;
1585 
1586  // Strictly limit ourselves to plain loads and stores, not all instructions
1587  // that can access the stack.
1588  int DummyFI = -1;
1589  if (!TII->isStoreToStackSlotPostFE(MI, DummyFI) &&
1590  !TII->isLoadFromStackSlotPostFE(MI, DummyFI))
1591  return false;
1592 
1593  MachineFunction *MF = MI.getMF();
1594  unsigned Reg;
1595 
1596  LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump(););
1597 
1598  // Strictly limit ourselves to plain loads and stores, not all instructions
1599  // that can access the stack.
1600  int FIDummy;
1601  if (!TII->isStoreToStackSlotPostFE(MI, FIDummy) &&
1602  !TII->isLoadFromStackSlotPostFE(MI, FIDummy))
1603  return false;
1604 
1605  // First, if there are any DBG_VALUEs pointing at a spill slot that is
1606  // written to, terminate that variable location. The value in memory
1607  // will have changed. DbgEntityHistoryCalculator doesn't try to detect this.
1608  if (Optional<SpillLocationNo> Loc = isSpillInstruction(MI, MF)) {
1609  // Un-set this location and clobber, so that earlier locations don't
1610  // continue past this store.
1611  for (unsigned SlotIdx = 0; SlotIdx < MTracker->NumSlotIdxes; ++SlotIdx) {
1612  unsigned SpillID = MTracker->getSpillIDWithIdx(*Loc, SlotIdx);
1613  Optional<LocIdx> MLoc = MTracker->getSpillMLoc(SpillID);
1614  if (!MLoc)
1615  continue;
1616 
1617  // We need to over-write the stack slot with something (here, a def at
1618  // this instruction) to ensure no values are preserved in this stack slot
1619  // after the spill. It also prevents TTracker from trying to recover the
1620  // location and re-installing it in the same place.
1621  ValueIDNum Def(CurBB, CurInst, *MLoc);
1622  MTracker->setMLoc(*MLoc, Def);
1623  if (TTracker)
1624  TTracker->clobberMloc(*MLoc, MI.getIterator());
1625  }
1626  }
1627 
1628  // Try to recognise spill and restore instructions that may transfer a value.
1629  if (isLocationSpill(MI, MF, Reg)) {
1630  // isLocationSpill returning true should guarantee we can extract a
1631  // location.
1632  SpillLocationNo Loc = *extractSpillBaseRegAndOffset(MI);
1633 
1634  auto DoTransfer = [&](Register SrcReg, unsigned SpillID) {
1635  auto ReadValue = MTracker->readReg(SrcReg);
1636  LocIdx DstLoc = MTracker->getSpillMLoc(SpillID);
1637  MTracker->setMLoc(DstLoc, ReadValue);
1638 
1639  if (TTracker) {
1640  LocIdx SrcLoc = MTracker->getRegMLoc(SrcReg);
1641  TTracker->transferMlocs(SrcLoc, DstLoc, MI.getIterator());
1642  }
1643  };
1644 
1645  // Then, transfer subreg bits.
1646  for (MCSubRegIterator SRI(Reg, TRI, false); SRI.isValid(); ++SRI) {
1647  // Ensure this reg is tracked,
1648  (void)MTracker->lookupOrTrackRegister(*SRI);
1649  unsigned SubregIdx = TRI->getSubRegIndex(Reg, *SRI);
1650  unsigned SpillID = MTracker->getLocID(Loc, SubregIdx);
1651  DoTransfer(*SRI, SpillID);
1652  }
1653 
1654  // Directly lookup size of main source reg, and transfer.
1655  unsigned Size = TRI->getRegSizeInBits(Reg, *MRI);
1656  unsigned SpillID = MTracker->getLocID(Loc, {Size, 0});
1657  DoTransfer(Reg, SpillID);
1658  } else {
1659  Optional<SpillLocationNo> Loc = isRestoreInstruction(MI, MF, Reg);
1660  if (!Loc)
1661  return false;
1662 
1663  // Assumption: we're reading from the base of the stack slot, not some
1664  // offset into it. It seems very unlikely LLVM would ever generate
1665  // restores where this wasn't true. This then becomes a question of what
1666  // subregisters in the destination register line up with positions in the
1667  // stack slot.
1668 
1669  // Def all registers that alias the destination.
1670  for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
1671  MTracker->defReg(*RAI, CurBB, CurInst);
1672 
1673  // Now find subregisters within the destination register, and load values
1674  // from stack slot positions.
1675  auto DoTransfer = [&](Register DestReg, unsigned SpillID) {
1676  LocIdx SrcIdx = MTracker->getSpillMLoc(SpillID);
1677  auto ReadValue = MTracker->readMLoc(SrcIdx);
1678  MTracker->setReg(DestReg, ReadValue);
1679  };
1680 
1681  for (MCSubRegIterator SRI(Reg, TRI, false); SRI.isValid(); ++SRI) {
1682  unsigned Subreg = TRI->getSubRegIndex(Reg, *SRI);
1683  unsigned SpillID = MTracker->getLocID(*Loc, Subreg);
1684  DoTransfer(*SRI, SpillID);
1685  }
1686 
1687  // Directly look up this registers slot idx by size, and transfer.
1688  unsigned Size = TRI->getRegSizeInBits(Reg, *MRI);
1689  unsigned SpillID = MTracker->getLocID(*Loc, {Size, 0});
1690  DoTransfer(Reg, SpillID);
1691  }
1692  return true;
1693 }
1694 
1695 bool InstrRefBasedLDV::transferRegisterCopy(MachineInstr &MI) {
1696  auto DestSrc = TII->isCopyInstr(MI);
1697  if (!DestSrc)
1698  return false;
1699 
1700  const MachineOperand *DestRegOp = DestSrc->Destination;
1701  const MachineOperand *SrcRegOp = DestSrc->Source;
1702 
1703  auto isCalleeSavedReg = [&](unsigned Reg) {
1704  for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
1705  if (CalleeSavedRegs.test(*RAI))
1706  return true;
1707  return false;
1708  };
1709 
1710  Register SrcReg = SrcRegOp->getReg();
1711  Register DestReg = DestRegOp->getReg();
1712 
1713  // Ignore identity copies. Yep, these make it as far as LiveDebugValues.
1714  if (SrcReg == DestReg)
1715  return true;
1716 
1717  // For emulating VarLocBasedImpl:
1718  // We want to recognize instructions where destination register is callee
1719  // saved register. If register that could be clobbered by the call is
1720  // included, there would be a great chance that it is going to be clobbered
1721  // soon. It is more likely that previous register, which is callee saved, is
1722  // going to stay unclobbered longer, even if it is killed.
1723  //
1724  // For InstrRefBasedImpl, we can track multiple locations per value, so
1725  // ignore this condition.
1726  if (EmulateOldLDV && !isCalleeSavedReg(DestReg))
1727  return false;
1728 
1729  // InstrRefBasedImpl only followed killing copies.
1730  if (EmulateOldLDV && !SrcRegOp->isKill())
1731  return false;
1732 
1733  // Copy MTracker info, including subregs if available.
1734  InstrRefBasedLDV::performCopy(SrcReg, DestReg);
1735 
1736  // Only produce a transfer of DBG_VALUE within a block where old LDV
1737  // would have. We might make use of the additional value tracking in some
1738  // other way, later.
1739  if (TTracker && isCalleeSavedReg(DestReg) && SrcRegOp->isKill())
1740  TTracker->transferMlocs(MTracker->getRegMLoc(SrcReg),
1741  MTracker->getRegMLoc(DestReg), MI.getIterator());
1742 
1743  // VarLocBasedImpl would quit tracking the old location after copying.
1744  if (EmulateOldLDV && SrcReg != DestReg)
1745  MTracker->defReg(SrcReg, CurBB, CurInst);
1746 
1747  // Finally, the copy might have clobbered variables based on the destination
1748  // register. Tell TTracker about it, in case a backup location exists.
1749  if (TTracker) {
1750  for (MCRegAliasIterator RAI(DestReg, TRI, true); RAI.isValid(); ++RAI) {
1751  LocIdx ClobberedLoc = MTracker->getRegMLoc(*RAI);
1752  TTracker->clobberMloc(ClobberedLoc, MI.getIterator(), false);
1753  }
1754  }
1755 
1756  return true;
1757 }
1758 
1759 /// Accumulate a mapping between each DILocalVariable fragment and other
1760 /// fragments of that DILocalVariable which overlap. This reduces work during
1761 /// the data-flow stage from "Find any overlapping fragments" to "Check if the
1762 /// known-to-overlap fragments are present".
1763 /// \param MI A previously unprocessed debug instruction to analyze for
1764 /// fragment usage.
1765 void InstrRefBasedLDV::accumulateFragmentMap(MachineInstr &MI) {
1766  assert(MI.isDebugValue() || MI.isDebugRef());
1767  DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(),
1768  MI.getDebugLoc()->getInlinedAt());
1769  FragmentInfo ThisFragment = MIVar.getFragmentOrDefault();
1770 
1771  // If this is the first sighting of this variable, then we are guaranteed
1772  // there are currently no overlapping fragments either. Initialize the set
1773  // of seen fragments, record no overlaps for the current one, and return.
1774  auto SeenIt = SeenFragments.find(MIVar.getVariable());
1775  if (SeenIt == SeenFragments.end()) {
1776  SmallSet<FragmentInfo, 4> OneFragment;
1777  OneFragment.insert(ThisFragment);
1778  SeenFragments.insert({MIVar.getVariable(), OneFragment});
1779 
1780  OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}});
1781  return;
1782  }
1783 
1784  // If this particular Variable/Fragment pair already exists in the overlap
1785  // map, it has already been accounted for.
1786  auto IsInOLapMap =
1787  OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}});
1788  if (!IsInOLapMap.second)
1789  return;
1790 
1791  auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;
1792  auto &AllSeenFragments = SeenIt->second;
1793 
1794  // Otherwise, examine all other seen fragments for this variable, with "this"
1795  // fragment being a previously unseen fragment. Record any pair of
1796  // overlapping fragments.
1797  for (auto &ASeenFragment : AllSeenFragments) {
1798  // Does this previously seen fragment overlap?
1799  if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) {
1800  // Yes: Mark the current fragment as being overlapped.
1801  ThisFragmentsOverlaps.push_back(ASeenFragment);
1802  // Mark the previously seen fragment as being overlapped by the current
1803  // one.
1804  auto ASeenFragmentsOverlaps =
1805  OverlapFragments.find({MIVar.getVariable(), ASeenFragment});
1806  assert(ASeenFragmentsOverlaps != OverlapFragments.end() &&
1807  "Previously seen var fragment has no vector of overlaps");
1808  ASeenFragmentsOverlaps->second.push_back(ThisFragment);
1809  }
1810  }
1811 
1812  AllSeenFragments.insert(ThisFragment);
1813 }
1814 
1815 void InstrRefBasedLDV::process(MachineInstr &MI, const ValueTable *MLiveOuts,
1816  const ValueTable *MLiveIns) {
1817  // Try to interpret an MI as a debug or transfer instruction. Only if it's
1818  // none of these should we interpret it's register defs as new value
1819  // definitions.
1820  if (transferDebugValue(MI))
1821  return;
1822  if (transferDebugInstrRef(MI, MLiveOuts, MLiveIns))
1823  return;
1824  if (transferDebugPHI(MI))
1825  return;
1826  if (transferRegisterCopy(MI))
1827  return;
1828  if (transferSpillOrRestoreInst(MI))
1829  return;
1830  transferRegisterDef(MI);
1831 }
1832 
1833 void InstrRefBasedLDV::produceMLocTransferFunction(
1835  unsigned MaxNumBlocks) {
1836  // Because we try to optimize around register mask operands by ignoring regs
1837  // that aren't currently tracked, we set up something ugly for later: RegMask
1838  // operands that are seen earlier than the first use of a register, still need
1839  // to clobber that register in the transfer function. But this information
1840  // isn't actively recorded. Instead, we track each RegMask used in each block,
1841  // and accumulated the clobbered but untracked registers in each block into
1842  // the following bitvector. Later, if new values are tracked, we can add
1843  // appropriate clobbers.
1844  SmallVector<BitVector, 32> BlockMasks;
1845  BlockMasks.resize(MaxNumBlocks);
1846 
1847  // Reserve one bit per register for the masks described above.
1848  unsigned BVWords = MachineOperand::getRegMaskSize(TRI->getNumRegs());
1849  for (auto &BV : BlockMasks)
1850  BV.resize(TRI->getNumRegs(), true);
1851 
1852  // Step through all instructions and inhale the transfer function.
1853  for (auto &MBB : MF) {
1854  // Object fields that are read by trackers to know where we are in the
1855  // function.
1856  CurBB = MBB.getNumber();
1857  CurInst = 1;
1858 
1859  // Set all machine locations to a PHI value. For transfer function
1860  // production only, this signifies the live-in value to the block.
1861  MTracker->reset();
1862  MTracker->setMPhis(CurBB);
1863 
1864  // Step through each instruction in this block.
1865  for (auto &MI : MBB) {
1866  // Pass in an empty unique_ptr for the value tables when accumulating the
1867  // machine transfer function.
1868  process(MI, nullptr, nullptr);
1869 
1870  // Also accumulate fragment map.
1871  if (MI.isDebugValue() || MI.isDebugRef())
1872  accumulateFragmentMap(MI);
1873 
1874  // Create a map from the instruction number (if present) to the
1875  // MachineInstr and its position.
1876  if (uint64_t InstrNo = MI.peekDebugInstrNum()) {
1877  auto InstrAndPos = std::make_pair(&MI, CurInst);
1878  auto InsertResult =
1879  DebugInstrNumToInstr.insert(std::make_pair(InstrNo, InstrAndPos));
1880 
1881  // There should never be duplicate instruction numbers.
1882  assert(InsertResult.second);
1883  (void)InsertResult;
1884  }
1885 
1886  ++CurInst;
1887  }
1888 
1889  // Produce the transfer function, a map of machine location to new value. If
1890  // any machine location has the live-in phi value from the start of the
1891  // block, it's live-through and doesn't need recording in the transfer
1892  // function.
1893  for (auto Location : MTracker->locations()) {
1894  LocIdx Idx = Location.Idx;
1895  ValueIDNum &P = Location.Value;
1896  if (P.isPHI() && P.getLoc() == Idx.asU64())
1897  continue;
1898 
1899  // Insert-or-update.
1900  auto &TransferMap = MLocTransfer[CurBB];
1901  auto Result = TransferMap.insert(std::make_pair(Idx.asU64(), P));
1902  if (!Result.second)
1903  Result.first->second = P;
1904  }
1905 
1906  // Accumulate any bitmask operands into the clobberred reg mask for this
1907  // block.
1908  for (auto &P : MTracker->Masks) {
1909  BlockMasks[CurBB].clearBitsNotInMask(P.first->getRegMask(), BVWords);
1910  }
1911  }
1912 
1913  // Compute a bitvector of all the registers that are tracked in this block.
1914  BitVector UsedRegs(TRI->getNumRegs());
1915  for (auto Location : MTracker->locations()) {
1916  unsigned ID = MTracker->LocIdxToLocID[Location.Idx];
1917  // Ignore stack slots, and aliases of the stack pointer.
1918  if (ID >= TRI->getNumRegs() || MTracker->SPAliases.count(ID))
1919  continue;
1920  UsedRegs.set(ID);
1921  }
1922 
1923  // Check that any regmask-clobber of a register that gets tracked, is not
1924  // live-through in the transfer function. It needs to be clobbered at the
1925  // very least.
1926  for (unsigned int I = 0; I < MaxNumBlocks; ++I) {
1927  BitVector &BV = BlockMasks[I];
1928  BV.flip();
1929  BV &= UsedRegs;
1930  // This produces all the bits that we clobber, but also use. Check that
1931  // they're all clobbered or at least set in the designated transfer
1932  // elem.
1933  for (unsigned Bit : BV.set_bits()) {
1934  unsigned ID = MTracker->getLocID(Bit);
1935  LocIdx Idx = MTracker->LocIDToLocIdx[ID];
1936  auto &TransferMap = MLocTransfer[I];
1937 
1938  // Install a value representing the fact that this location is effectively
1939  // written to in this block. As there's no reserved value, instead use
1940  // a value number that is never generated. Pick the value number for the
1941  // first instruction in the block, def'ing this location, which we know
1942  // this block never used anyway.
1943  ValueIDNum NotGeneratedNum = ValueIDNum(I, 1, Idx);
1944  auto Result =
1945  TransferMap.insert(std::make_pair(Idx.asU64(), NotGeneratedNum));
1946  if (!Result.second) {
1947  ValueIDNum &ValueID = Result.first->second;
1948  if (ValueID.getBlock() == I && ValueID.isPHI())
1949  // It was left as live-through. Set it to clobbered.
1950  ValueID = NotGeneratedNum;
1951  }
1952  }
1953  }
1954 }
1955 
1956 bool InstrRefBasedLDV::mlocJoin(
1958  FuncValueTable &OutLocs, ValueTable &InLocs) {
1959  LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
1960  bool Changed = false;
1961 
1962  // Handle value-propagation when control flow merges on entry to a block. For
1963  // any location without a PHI already placed, the location has the same value
1964  // as its predecessors. If a PHI is placed, test to see whether it's now a
1965  // redundant PHI that we can eliminate.
1966 
1968  for (auto Pred : MBB.predecessors())
1969  BlockOrders.push_back(Pred);
1970 
1971  // Visit predecessors in RPOT order.
1972  auto Cmp = [&](const MachineBasicBlock *A, const MachineBasicBlock *B) {
1973  return BBToOrder.find(A)->second < BBToOrder.find(B)->second;
1974  };
1975  llvm::sort(BlockOrders, Cmp);
1976 
1977  // Skip entry block.
1978  if (BlockOrders.size() == 0)
1979  return false;
1980 
1981  // Step through all machine locations, look at each predecessor and test
1982  // whether we can eliminate redundant PHIs.
1983  for (auto Location : MTracker->locations()) {
1984  LocIdx Idx = Location.Idx;
1985 
1986  // Pick out the first predecessors live-out value for this location. It's
1987  // guaranteed to not be a backedge, as we order by RPO.
1988  ValueIDNum FirstVal = OutLocs[BlockOrders[0]->getNumber()][Idx.asU64()];
1989 
1990  // If we've already eliminated a PHI here, do no further checking, just
1991  // propagate the first live-in value into this block.
1992  if (InLocs[Idx.asU64()] != ValueIDNum(MBB.getNumber(), 0, Idx)) {
1993  if (InLocs[Idx.asU64()] != FirstVal) {
1994  InLocs[Idx.asU64()] = FirstVal;
1995  Changed |= true;
1996  }
1997  continue;
1998  }
1999 
2000  // We're now examining a PHI to see whether it's un-necessary. Loop around
2001  // the other live-in values and test whether they're all the same.
2002  bool Disagree = false;
2003  for (unsigned int I = 1; I < BlockOrders.size(); ++I) {
2004  const MachineBasicBlock *PredMBB = BlockOrders[I];
2005  const ValueIDNum &PredLiveOut =
2006  OutLocs[PredMBB->getNumber()][Idx.asU64()];
2007 
2008  // Incoming values agree, continue trying to eliminate this PHI.
2009  if (FirstVal == PredLiveOut)
2010  continue;
2011 
2012  // We can also accept a PHI value that feeds back into itself.
2013  if (PredLiveOut == ValueIDNum(MBB.getNumber(), 0, Idx))
2014  continue;
2015 
2016  // Live-out of a predecessor disagrees with the first predecessor.
2017  Disagree = true;
2018  }
2019 
2020  // No disagreement? No PHI. Otherwise, leave the PHI in live-ins.
2021  if (!Disagree) {
2022  InLocs[Idx.asU64()] = FirstVal;
2023  Changed |= true;
2024  }
2025  }
2026 
2027  // TODO: Reimplement NumInserted and NumRemoved.
2028  return Changed;
2029 }
2030 
2031 void InstrRefBasedLDV::findStackIndexInterference(
2032  SmallVectorImpl<unsigned> &Slots) {
2033  // We could spend a bit of time finding the exact, minimal, set of stack
2034  // indexes that interfere with each other, much like reg units. Or, we can
2035  // rely on the fact that:
2036  // * The smallest / lowest index will interfere with everything at zero
2037  // offset, which will be the largest set of registers,
2038  // * Most indexes with non-zero offset will end up being interference units
2039  // anyway.
2040  // So just pick those out and return them.
2041 
2042  // We can rely on a single-byte stack index existing already, because we
2043  // initialize them in MLocTracker.
2044  auto It = MTracker->StackSlotIdxes.find({8, 0});
2045  assert(It != MTracker->StackSlotIdxes.end());
2046  Slots.push_back(It->second);
2047 
2048  // Find anything that has a non-zero offset and add that too.
2049  for (auto &Pair : MTracker->StackSlotIdxes) {
2050  // Is offset zero? If so, ignore.
2051  if (!Pair.first.second)
2052  continue;
2053  Slots.push_back(Pair.second);
2054  }
2055 }
2056 
2057 void InstrRefBasedLDV::placeMLocPHIs(
2059  FuncValueTable &MInLocs, SmallVectorImpl<MLocTransferMap> &MLocTransfer) {
2060  SmallVector<unsigned, 4> StackUnits;
2061  findStackIndexInterference(StackUnits);
2062 
2063  // To avoid repeatedly running the PHI placement algorithm, leverage the
2064  // fact that a def of register MUST also def its register units. Find the
2065  // units for registers, place PHIs for them, and then replicate them for
2066  // aliasing registers. Some inputs that are never def'd (DBG_PHIs of
2067  // arguments) don't lead to register units being tracked, just place PHIs for
2068  // those registers directly. Stack slots have their own form of "unit",
2069  // store them to one side.
2070  SmallSet<Register, 32> RegUnitsToPHIUp;
2071  SmallSet<LocIdx, 32> NormalLocsToPHI;
2072  SmallSet<SpillLocationNo, 32> StackSlots;
2073  for (auto Location : MTracker->locations()) {
2074  LocIdx L = Location.Idx;
2075  if (MTracker->isSpill(L)) {
2076  StackSlots.insert(MTracker->locIDToSpill(MTracker->LocIdxToLocID[L]));
2077  continue;
2078  }
2079 
2080  Register R = MTracker->LocIdxToLocID[L];
2081  SmallSet<Register, 8> FoundRegUnits;
2082  bool AnyIllegal = false;
2083  for (MCRegUnitIterator RUI(R.asMCReg(), TRI); RUI.isValid(); ++RUI) {
2084  for (MCRegUnitRootIterator URoot(*RUI, TRI); URoot.isValid(); ++URoot){
2085  if (!MTracker->isRegisterTracked(*URoot)) {
2086  // Not all roots were loaded into the tracking map: this register
2087  // isn't actually def'd anywhere, we only read from it. Generate PHIs
2088  // for this reg, but don't iterate units.
2089  AnyIllegal = true;
2090  } else {
2091  FoundRegUnits.insert(*URoot);
2092  }
2093  }
2094  }
2095 
2096  if (AnyIllegal) {
2097  NormalLocsToPHI.insert(L);
2098  continue;
2099  }
2100 
2101  RegUnitsToPHIUp.insert(FoundRegUnits.begin(), FoundRegUnits.end());
2102  }
2103 
2104  // Lambda to fetch PHIs for a given location, and write into the PHIBlocks
2105  // collection.
2107  auto CollectPHIsForLoc = [&](LocIdx L) {
2108  // Collect the set of defs.
2110  for (unsigned int I = 0; I < OrderToBB.size(); ++I) {
2111  MachineBasicBlock *MBB = OrderToBB[I];
2112  const auto &TransferFunc = MLocTransfer[MBB->getNumber()];
2113  if (TransferFunc.find(L) != TransferFunc.end())
2114  DefBlocks.insert(MBB);
2115  }
2116 
2117  // The entry block defs the location too: it's the live-in / argument value.
2118  // Only insert if there are other defs though; everything is trivially live
2119  // through otherwise.
2120  if (!DefBlocks.empty())
2121  DefBlocks.insert(&*MF.begin());
2122 
2123  // Ask the SSA construction algorithm where we should put PHIs. Clear
2124  // anything that might have been hanging around from earlier.
2125  PHIBlocks.clear();
2126  BlockPHIPlacement(AllBlocks, DefBlocks, PHIBlocks);
2127  };
2128 
2129  auto InstallPHIsAtLoc = [&PHIBlocks, &MInLocs](LocIdx L) {
2130  for (const MachineBasicBlock *MBB : PHIBlocks)
2131  MInLocs[MBB->getNumber()][L.asU64()] = ValueIDNum(MBB->getNumber(), 0, L);
2132  };
2133 
2134  // For locations with no reg units, just place PHIs.
2135  for (LocIdx L : NormalLocsToPHI) {
2136  CollectPHIsForLoc(L);
2137  // Install those PHI values into the live-in value array.
2138  InstallPHIsAtLoc(L);
2139  }
2140 
2141  // For stack slots, calculate PHIs for the equivalent of the units, then
2142  // install for each index.
2143  for (SpillLocationNo Slot : StackSlots) {
2144  for (unsigned Idx : StackUnits) {
2145  unsigned SpillID = MTracker->getSpillIDWithIdx(Slot, Idx);
2146  LocIdx L = MTracker->getSpillMLoc(SpillID);
2147  CollectPHIsForLoc(L);
2148  InstallPHIsAtLoc(L);
2149 
2150  // Find anything that aliases this stack index, install PHIs for it too.
2151  unsigned Size, Offset;
2152  std::tie(Size, Offset) = MTracker->StackIdxesToPos[Idx];
2153  for (auto &Pair : MTracker->StackSlotIdxes) {
2154  unsigned ThisSize, ThisOffset;
2155  std::tie(ThisSize, ThisOffset) = Pair.first;
2156  if (ThisSize + ThisOffset <= Offset || Size + Offset <= ThisOffset)
2157  continue;
2158 
2159  unsigned ThisID = MTracker->getSpillIDWithIdx(Slot, Pair.second);
2160  LocIdx ThisL = MTracker->getSpillMLoc(ThisID);
2161  InstallPHIsAtLoc(ThisL);
2162  }
2163  }
2164  }
2165 
2166  // For reg units, place PHIs, and then place them for any aliasing registers.
2167  for (Register R : RegUnitsToPHIUp) {
2168  LocIdx L = MTracker->lookupOrTrackRegister(R);
2169  CollectPHIsForLoc(L);
2170 
2171  // Install those PHI values into the live-in value array.
2172  InstallPHIsAtLoc(L);
2173 
2174  // Now find aliases and install PHIs for those.
2175  for (MCRegAliasIterator RAI(R, TRI, true); RAI.isValid(); ++RAI) {
2176  // Super-registers that are "above" the largest register read/written by
2177  // the function will alias, but will not be tracked.
2178  if (!MTracker->isRegisterTracked(*RAI))
2179  continue;
2180 
2181  LocIdx AliasLoc = MTracker->lookupOrTrackRegister(*RAI);
2182  InstallPHIsAtLoc(AliasLoc);
2183  }
2184  }
2185 }
2186 
2187 void InstrRefBasedLDV::buildMLocValueMap(
2188  MachineFunction &MF, FuncValueTable &MInLocs, FuncValueTable &MOutLocs,
2189  SmallVectorImpl<MLocTransferMap> &MLocTransfer) {
2190  std::priority_queue<unsigned int, std::vector<unsigned int>,
2191  std::greater<unsigned int>>
2192  Worklist, Pending;
2193 
2194  // We track what is on the current and pending worklist to avoid inserting
2195  // the same thing twice. We could avoid this with a custom priority queue,
2196  // but this is probably not worth it.
2197  SmallPtrSet<MachineBasicBlock *, 16> OnPending, OnWorklist;
2198 
2199  // Initialize worklist with every block to be visited. Also produce list of
2200  // all blocks.
2202  for (unsigned int I = 0; I < BBToOrder.size(); ++I) {
2203  Worklist.push(I);
2204  OnWorklist.insert(OrderToBB[I]);
2205  AllBlocks.insert(OrderToBB[I]);
2206  }
2207 
2208  // Initialize entry block to PHIs. These represent arguments.
2209  for (auto Location : MTracker->locations())
2210  MInLocs[0][Location.Idx.asU64()] = ValueIDNum(0, 0, Location.Idx);
2211 
2212  MTracker->reset();
2213 
2214  // Start by placing PHIs, using the usual SSA constructor algorithm. Consider
2215  // any machine-location that isn't live-through a block to be def'd in that
2216  // block.
2217  placeMLocPHIs(MF, AllBlocks, MInLocs, MLocTransfer);
2218 
2219  // Propagate values to eliminate redundant PHIs. At the same time, this
2220  // produces the table of Block x Location => Value for the entry to each
2221  // block.
2222  // The kind of PHIs we can eliminate are, for example, where one path in a
2223  // conditional spills and restores a register, and the register still has
2224  // the same value once control flow joins, unbeknowns to the PHI placement
2225  // code. Propagating values allows us to identify such un-necessary PHIs and
2226  // remove them.
2228  while (!Worklist.empty() || !Pending.empty()) {
2229  // Vector for storing the evaluated block transfer function.
2231 
2232  while (!Worklist.empty()) {
2233  MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
2234  CurBB = MBB->getNumber();
2235  Worklist.pop();
2236 
2237  // Join the values in all predecessor blocks.
2238  bool InLocsChanged;
2239  InLocsChanged = mlocJoin(*MBB, Visited, MOutLocs, MInLocs[CurBB]);
2240  InLocsChanged |= Visited.insert(MBB).second;
2241 
2242  // Don't examine transfer function if we've visited this loc at least
2243  // once, and inlocs haven't changed.
2244  if (!InLocsChanged)
2245  continue;
2246 
2247  // Load the current set of live-ins into MLocTracker.
2248  MTracker->loadFromArray(MInLocs[CurBB], CurBB);
2249 
2250  // Each element of the transfer function can be a new def, or a read of
2251  // a live-in value. Evaluate each element, and store to "ToRemap".
2252  ToRemap.clear();
2253  for (auto &P : MLocTransfer[CurBB]) {
2254  if (P.second.getBlock() == CurBB && P.second.isPHI()) {
2255  // This is a movement of whatever was live in. Read it.
2256  ValueIDNum NewID = MTracker->readMLoc(P.second.getLoc());
2257  ToRemap.push_back(std::make_pair(P.first, NewID));
2258  } else {
2259  // It's a def. Just set it.
2260  assert(P.second.getBlock() == CurBB);
2261  ToRemap.push_back(std::make_pair(P.first, P.second));
2262  }
2263  }
2264 
2265  // Commit the transfer function changes into mloc tracker, which
2266  // transforms the contents of the MLocTracker into the live-outs.
2267  for (auto &P : ToRemap)
2268  MTracker->setMLoc(P.first, P.second);
2269 
2270  // Now copy out-locs from mloc tracker into out-loc vector, checking
2271  // whether changes have occurred. These changes can have come from both
2272  // the transfer function, and mlocJoin.
2273  bool OLChanged = false;
2274  for (auto Location : MTracker->locations()) {
2275  OLChanged |= MOutLocs[CurBB][Location.Idx.asU64()] != Location.Value;
2276  MOutLocs[CurBB][Location.Idx.asU64()] = Location.Value;
2277  }
2278 
2279  MTracker->reset();
2280 
2281  // No need to examine successors again if out-locs didn't change.
2282  if (!OLChanged)
2283  continue;
2284 
2285  // All successors should be visited: put any back-edges on the pending
2286  // list for the next pass-through, and any other successors to be
2287  // visited this pass, if they're not going to be already.
2288  for (auto s : MBB->successors()) {
2289  // Does branching to this successor represent a back-edge?
2290  if (BBToOrder[s] > BBToOrder[MBB]) {
2291  // No: visit it during this dataflow iteration.
2292  if (OnWorklist.insert(s).second)
2293  Worklist.push(BBToOrder[s]);
2294  } else {
2295  // Yes: visit it on the next iteration.
2296  if (OnPending.insert(s).second)
2297  Pending.push(BBToOrder[s]);
2298  }
2299  }
2300  }
2301 
2302  Worklist.swap(Pending);
2303  std::swap(OnPending, OnWorklist);
2304  OnPending.clear();
2305  // At this point, pending must be empty, since it was just the empty
2306  // worklist
2307  assert(Pending.empty() && "Pending should be empty");
2308  }
2309 
2310  // Once all the live-ins don't change on mlocJoin(), we've eliminated all
2311  // redundant PHIs.
2312 }
2313 
2314 void InstrRefBasedLDV::BlockPHIPlacement(
2315  const SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks,
2316  const SmallPtrSetImpl<MachineBasicBlock *> &DefBlocks,
2318  // Apply IDF calculator to the designated set of location defs, storing
2319  // required PHIs into PHIBlocks. Uses the dominator tree stored in the
2320  // InstrRefBasedLDV object.
2322 
2323  IDF.setLiveInBlocks(AllBlocks);
2324  IDF.setDefiningBlocks(DefBlocks);
2325  IDF.calculate(PHIBlocks);
2326 }
2327 
2328 Optional<ValueIDNum> InstrRefBasedLDV::pickVPHILoc(
2329  const MachineBasicBlock &MBB, const DebugVariable &Var,
2330  const LiveIdxT &LiveOuts, FuncValueTable &MOutLocs,
2331  const SmallVectorImpl<const MachineBasicBlock *> &BlockOrders) {
2332  // Collect a set of locations from predecessor where its live-out value can
2333  // be found.
2336  unsigned NumLocs = MTracker->getNumLocs();
2337 
2338  // No predecessors means no PHIs.
2339  if (BlockOrders.empty())
2340  return None;
2341 
2342  for (auto p : BlockOrders) {
2343  unsigned ThisBBNum = p->getNumber();
2344  auto OutValIt = LiveOuts.find(p);
2345  if (OutValIt == LiveOuts.end())
2346  // If we have a predecessor not in scope, we'll never find a PHI position.
2347  return None;
2348  const DbgValue &OutVal = *OutValIt->second;
2349 
2350  if (OutVal.Kind == DbgValue::Const || OutVal.Kind == DbgValue::NoVal)
2351  // Consts and no-values cannot have locations we can join on.
2352  return None;
2353 
2354  Properties.push_back(&OutVal.Properties);
2355 
2356  // Create new empty vector of locations.
2357  Locs.resize(Locs.size() + 1);
2358 
2359  // If the live-in value is a def, find the locations where that value is
2360  // present. Do the same for VPHIs where we know the VPHI value.
2361  if (OutVal.Kind == DbgValue::Def ||
2362  (OutVal.Kind == DbgValue::VPHI && OutVal.BlockNo != MBB.getNumber() &&
2363  OutVal.ID != ValueIDNum::EmptyValue)) {
2364  ValueIDNum ValToLookFor = OutVal.ID;
2365  // Search the live-outs of the predecessor for the specified value.
2366  for (unsigned int I = 0; I < NumLocs; ++I) {
2367  if (MOutLocs[ThisBBNum][I] == ValToLookFor)
2368  Locs.back().push_back(LocIdx(I));
2369  }
2370  } else {
2371  assert(OutVal.Kind == DbgValue::VPHI);
2372  // For VPHIs where we don't know the location, we definitely can't find
2373  // a join loc.
2374  if (OutVal.BlockNo != MBB.getNumber())
2375  return None;
2376 
2377  // Otherwise: this is a VPHI on a backedge feeding back into itself, i.e.
2378  // a value that's live-through the whole loop. (It has to be a backedge,
2379  // because a block can't dominate itself). We can accept as a PHI location
2380  // any location where the other predecessors agree, _and_ the machine
2381  // locations feed back into themselves. Therefore, add all self-looping
2382  // machine-value PHI locations.
2383  for (unsigned int I = 0; I < NumLocs; ++I) {
2384  ValueIDNum MPHI(MBB.getNumber(), 0, LocIdx(I));
2385  if (MOutLocs[ThisBBNum][I] == MPHI)
2386  Locs.back().push_back(LocIdx(I));
2387  }
2388  }
2389  }
2390 
2391  // We should have found locations for all predecessors, or returned.
2392  assert(Locs.size() == BlockOrders.size());
2393 
2394  // Check that all properties are the same. We can't pick a location if they're
2395  // not.
2396  const DbgValueProperties *Properties0 = Properties[0];
2397  for (auto *Prop : Properties)
2398  if (*Prop != *Properties0)
2399  return None;
2400 
2401  // Starting with the first set of locations, take the intersection with
2402  // subsequent sets.
2403  SmallVector<LocIdx, 4> CandidateLocs = Locs[0];
2404  for (unsigned int I = 1; I < Locs.size(); ++I) {
2405  auto &LocVec = Locs[I];
2406  SmallVector<LocIdx, 4> NewCandidates;
2407  std::set_intersection(CandidateLocs.begin(), CandidateLocs.end(),
2408  LocVec.begin(), LocVec.end(), std::inserter(NewCandidates, NewCandidates.begin()));
2409  CandidateLocs = NewCandidates;
2410  }
2411  if (CandidateLocs.empty())
2412  return None;
2413 
2414  // We now have a set of LocIdxes that contain the right output value in
2415  // each of the predecessors. Pick the lowest; if there's a register loc,
2416  // that'll be it.
2417  LocIdx L = *CandidateLocs.begin();
2418 
2419  // Return a PHI-value-number for the found location.
2420  ValueIDNum PHIVal = {(unsigned)MBB.getNumber(), 0, L};
2421  return PHIVal;
2422 }
2423 
2424 bool InstrRefBasedLDV::vlocJoin(
2425  MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs,
2427  DbgValue &LiveIn) {
2428  LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
2429  bool Changed = false;
2430 
2431  // Order predecessors by RPOT order, for exploring them in that order.
2433 
2434  auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
2435  return BBToOrder[A] < BBToOrder[B];
2436  };
2437 
2438  llvm::sort(BlockOrders, Cmp);
2439 
2440  unsigned CurBlockRPONum = BBToOrder[&MBB];
2441 
2442  // Collect all the incoming DbgValues for this variable, from predecessor
2443  // live-out values.
2444  SmallVector<InValueT, 8> Values;
2445  bool Bail = false;
2446  int BackEdgesStart = 0;
2447  for (auto p : BlockOrders) {
2448  // If the predecessor isn't in scope / to be explored, we'll never be
2449  // able to join any locations.
2450  if (!BlocksToExplore.contains(p)) {
2451  Bail = true;
2452  break;
2453  }
2454 
2455  // All Live-outs will have been initialized.
2456  DbgValue &OutLoc = *VLOCOutLocs.find(p)->second;
2457 
2458  // Keep track of where back-edges begin in the Values vector. Relies on
2459  // BlockOrders being sorted by RPO.
2460  unsigned ThisBBRPONum = BBToOrder[p];
2461  if (ThisBBRPONum < CurBlockRPONum)
2462  ++BackEdgesStart;
2463 
2464  Values.push_back(std::make_pair(p, &OutLoc));
2465  }
2466 
2467  // If there were no values, or one of the predecessors couldn't have a
2468  // value, then give up immediately. It's not safe to produce a live-in
2469  // value. Leave as whatever it was before.
2470  if (Bail || Values.size() == 0)
2471  return false;
2472 
2473  // All (non-entry) blocks have at least one non-backedge predecessor.
2474  // Pick the variable value from the first of these, to compare against
2475  // all others.
2476  const DbgValue &FirstVal = *Values[0].second;
2477 
2478  // If the old live-in value is not a PHI then either a) no PHI is needed
2479  // here, or b) we eliminated the PHI that was here. If so, we can just
2480  // propagate in the first parent's incoming value.
2481  if (LiveIn.Kind != DbgValue::VPHI || LiveIn.BlockNo != MBB.getNumber()) {
2482  Changed = LiveIn != FirstVal;
2483  if (Changed)
2484  LiveIn = FirstVal;
2485  return Changed;
2486  }
2487 
2488  // Scan for variable values that can never be resolved: if they have
2489  // different DIExpressions, different indirectness, or are mixed constants /
2490  // non-constants.
2491  for (auto &V : Values) {
2492  if (V.second->Properties != FirstVal.Properties)
2493  return false;
2494  if (V.second->Kind == DbgValue::NoVal)
2495  return false;
2496  if (V.second->Kind == DbgValue::Const && FirstVal.Kind != DbgValue::Const)
2497  return false;
2498  }
2499 
2500  // Try to eliminate this PHI. Do the incoming values all agree?
2501  bool Disagree = false;
2502  for (auto &V : Values) {
2503  if (*V.second == FirstVal)
2504  continue; // No disagreement.
2505 
2506  // Eliminate if a backedge feeds a VPHI back into itself.
2507  if (V.second->Kind == DbgValue::VPHI &&
2508  V.second->BlockNo == MBB.getNumber() &&
2509  // Is this a backedge?
2510  std::distance(Values.begin(), &V) >= BackEdgesStart)
2511  continue;
2512 
2513  Disagree = true;
2514  }
2515 
2516  // No disagreement -> live-through value.
2517  if (!Disagree) {
2518  Changed = LiveIn != FirstVal;
2519  if (Changed)
2520  LiveIn = FirstVal;
2521  return Changed;
2522  } else {
2523  // Otherwise use a VPHI.
2524  DbgValue VPHI(MBB.getNumber(), FirstVal.Properties, DbgValue::VPHI);
2525  Changed = LiveIn != VPHI;
2526  if (Changed)
2527  LiveIn = VPHI;
2528  return Changed;
2529  }
2530 }
2531 
2532 void InstrRefBasedLDV::getBlocksForScope(
2533  const DILocation *DILoc,
2535  const SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks) {
2536  // Get the set of "normal" in-lexical-scope blocks.
2537  LS.getMachineBasicBlocks(DILoc, BlocksToExplore);
2538 
2539  // VarLoc LiveDebugValues tracks variable locations that are defined in
2540  // blocks not in scope. This is something we could legitimately ignore, but
2541  // lets allow it for now for the sake of coverage.
2542  BlocksToExplore.insert(AssignBlocks.begin(), AssignBlocks.end());
2543 
2544  // Storage for artificial blocks we intend to add to BlocksToExplore.
2546 
2547  // To avoid needlessly dropping large volumes of variable locations, propagate
2548  // variables through aritifical blocks, i.e. those that don't have any
2549  // instructions in scope at all. To accurately replicate VarLoc
2550  // LiveDebugValues, this means exploring all artificial successors too.
2551  // Perform a depth-first-search to enumerate those blocks.
2552  for (auto *MBB : BlocksToExplore) {
2553  // Depth-first-search state: each node is a block and which successor
2554  // we're currently exploring.
2555  SmallVector<std::pair<const MachineBasicBlock *,
2557  8>
2558  DFS;
2559 
2560  // Find any artificial successors not already tracked.
2561  for (auto *succ : MBB->successors()) {
2562  if (BlocksToExplore.count(succ))
2563  continue;
2564  if (!ArtificialBlocks.count(succ))
2565  continue;
2566  ToAdd.insert(succ);
2567  DFS.push_back({succ, succ->succ_begin()});
2568  }
2569 
2570  // Search all those blocks, depth first.
2571  while (!DFS.empty()) {
2572  const MachineBasicBlock *CurBB = DFS.back().first;
2573  MachineBasicBlock::const_succ_iterator &CurSucc = DFS.back().second;
2574  // Walk back if we've explored this blocks successors to the end.
2575  if (CurSucc == CurBB->succ_end()) {
2576  DFS.pop_back();
2577  continue;
2578  }
2579 
2580  // If the current successor is artificial and unexplored, descend into
2581  // it.
2582  if (!ToAdd.count(*CurSucc) && ArtificialBlocks.count(*CurSucc)) {
2583  ToAdd.insert(*CurSucc);
2584  DFS.push_back({*CurSucc, (*CurSucc)->succ_begin()});
2585  continue;
2586  }
2587 
2588  ++CurSucc;
2589  }
2590  };
2591 
2592  BlocksToExplore.insert(ToAdd.begin(), ToAdd.end());
2593 }
2594 
2595 void InstrRefBasedLDV::buildVLocValueMap(
2596  const DILocation *DILoc, const SmallSet<DebugVariable, 4> &VarsWeCareAbout,
2597  SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, LiveInsT &Output,
2598  FuncValueTable &MOutLocs, FuncValueTable &MInLocs,
2599  SmallVectorImpl<VLocTracker> &AllTheVLocs) {
2600  // This method is much like buildMLocValueMap: but focuses on a single
2601  // LexicalScope at a time. Pick out a set of blocks and variables that are
2602  // to have their value assignments solved, then run our dataflow algorithm
2603  // until a fixedpoint is reached.
2604  std::priority_queue<unsigned int, std::vector<unsigned int>,
2605  std::greater<unsigned int>>
2606  Worklist, Pending;
2607  SmallPtrSet<MachineBasicBlock *, 16> OnWorklist, OnPending;
2608 
2609  // The set of blocks we'll be examining.
2611 
2612  // The order in which to examine them (RPO).
2614 
2615  // RPO ordering function.
2616  auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
2617  return BBToOrder[A] < BBToOrder[B];
2618  };
2619 
2620  getBlocksForScope(DILoc, BlocksToExplore, AssignBlocks);
2621 
2622  // Single block scope: not interesting! No propagation at all. Note that
2623  // this could probably go above ArtificialBlocks without damage, but
2624  // that then produces output differences from original-live-debug-values,
2625  // which propagates from a single block into many artificial ones.
2626  if (BlocksToExplore.size() == 1)
2627  return;
2628 
2629  // Convert a const set to a non-const set. LexicalScopes
2630  // getMachineBasicBlocks returns const MBB pointers, IDF wants mutable ones.
2631  // (Neither of them mutate anything).
2632  SmallPtrSet<MachineBasicBlock *, 8> MutBlocksToExplore;
2633  for (const auto *MBB : BlocksToExplore)
2634  MutBlocksToExplore.insert(const_cast<MachineBasicBlock *>(MBB));
2635 
2636  // Picks out relevants blocks RPO order and sort them.
2637  for (auto *MBB : BlocksToExplore)
2638  BlockOrders.push_back(const_cast<MachineBasicBlock *>(MBB));
2639 
2640  llvm::sort(BlockOrders, Cmp);
2641  unsigned NumBlocks = BlockOrders.size();
2642 
2643  // Allocate some vectors for storing the live ins and live outs. Large.
2644  SmallVector<DbgValue, 32> LiveIns, LiveOuts;
2645  LiveIns.reserve(NumBlocks);
2646  LiveOuts.reserve(NumBlocks);
2647 
2648  // Initialize all values to start as NoVals. This signifies "it's live
2649  // through, but we don't know what it is".
2650  DbgValueProperties EmptyProperties(EmptyExpr, false);
2651  for (unsigned int I = 0; I < NumBlocks; ++I) {
2652  DbgValue EmptyDbgValue(I, EmptyProperties, DbgValue::NoVal);
2653  LiveIns.push_back(EmptyDbgValue);
2654  LiveOuts.push_back(EmptyDbgValue);
2655  }
2656 
2657  // Produce by-MBB indexes of live-in/live-outs, to ease lookup within
2658  // vlocJoin.
2659  LiveIdxT LiveOutIdx, LiveInIdx;
2660  LiveOutIdx.reserve(NumBlocks);
2661  LiveInIdx.reserve(NumBlocks);
2662  for (unsigned I = 0; I < NumBlocks; ++I) {
2663  LiveOutIdx[BlockOrders[I]] = &LiveOuts[I];
2664  LiveInIdx[BlockOrders[I]] = &LiveIns[I];
2665  }
2666 
2667  // Loop over each variable and place PHIs for it, then propagate values
2668  // between blocks. This keeps the locality of working on one lexical scope at
2669  // at time, but avoids re-processing variable values because some other
2670  // variable has been assigned.
2671  for (auto &Var : VarsWeCareAbout) {
2672  // Re-initialize live-ins and live-outs, to clear the remains of previous
2673  // variables live-ins / live-outs.
2674  for (unsigned int I = 0; I < NumBlocks; ++I) {
2675  DbgValue EmptyDbgValue(I, EmptyProperties, DbgValue::NoVal);
2676  LiveIns[I] = EmptyDbgValue;
2677  LiveOuts[I] = EmptyDbgValue;
2678  }
2679 
2680  // Place PHIs for variable values, using the LLVM IDF calculator.
2681  // Collect the set of blocks where variables are def'd.
2683  for (const MachineBasicBlock *ExpMBB : BlocksToExplore) {
2684  auto &TransferFunc = AllTheVLocs[ExpMBB->getNumber()].Vars;
2685  if (TransferFunc.find(Var) != TransferFunc.end())
2686  DefBlocks.insert(const_cast<MachineBasicBlock *>(ExpMBB));
2687  }
2688 
2690 
2691  // Request the set of PHIs we should insert for this variable. If there's
2692  // only one value definition, things are very simple.
2693  if (DefBlocks.size() == 1) {
2694  placePHIsForSingleVarDefinition(MutBlocksToExplore, *DefBlocks.begin(),
2695  AllTheVLocs, Var, Output);
2696  continue;
2697  }
2698 
2699  // Otherwise: we need to place PHIs through SSA and propagate values.
2700  BlockPHIPlacement(MutBlocksToExplore, DefBlocks, PHIBlocks);
2701 
2702  // Insert PHIs into the per-block live-in tables for this variable.
2703  for (MachineBasicBlock *PHIMBB : PHIBlocks) {
2704  unsigned BlockNo = PHIMBB->getNumber();
2705  DbgValue *LiveIn = LiveInIdx[PHIMBB];
2706  *LiveIn = DbgValue(BlockNo, EmptyProperties, DbgValue::VPHI);
2707  }
2708 
2709  for (auto *MBB : BlockOrders) {
2710  Worklist.push(BBToOrder[MBB]);
2711  OnWorklist.insert(MBB);
2712  }
2713 
2714  // Iterate over all the blocks we selected, propagating the variables value.
2715  // This loop does two things:
2716  // * Eliminates un-necessary VPHIs in vlocJoin,
2717  // * Evaluates the blocks transfer function (i.e. variable assignments) and
2718  // stores the result to the blocks live-outs.
2719  // Always evaluate the transfer function on the first iteration, and when
2720  // the live-ins change thereafter.
2721  bool FirstTrip = true;
2722  while (!Worklist.empty() || !Pending.empty()) {
2723  while (!Worklist.empty()) {
2724  auto *MBB = OrderToBB[Worklist.top()];
2725  CurBB = MBB->getNumber();
2726  Worklist.pop();
2727 
2728  auto LiveInsIt = LiveInIdx.find(MBB);
2729  assert(LiveInsIt != LiveInIdx.end());
2730  DbgValue *LiveIn = LiveInsIt->second;
2731 
2732  // Join values from predecessors. Updates LiveInIdx, and writes output
2733  // into JoinedInLocs.
2734  bool InLocsChanged =
2735  vlocJoin(*MBB, LiveOutIdx, BlocksToExplore, *LiveIn);
2736 
2738  for (const auto *Pred : MBB->predecessors())
2739  Preds.push_back(Pred);
2740 
2741  // If this block's live-in value is a VPHI, try to pick a machine-value
2742  // for it. This makes the machine-value available and propagated
2743  // through all blocks by the time value propagation finishes. We can't
2744  // do this any earlier as it needs to read the block live-outs.
2745  if (LiveIn->Kind == DbgValue::VPHI && LiveIn->BlockNo == (int)CurBB) {
2746  // There's a small possibility that on a preceeding path, a VPHI is
2747  // eliminated and transitions from VPHI-with-location to
2748  // live-through-value. As a result, the selected location of any VPHI
2749  // might change, so we need to re-compute it on each iteration.
2750  Optional<ValueIDNum> ValueNum =
2751  pickVPHILoc(*MBB, Var, LiveOutIdx, MOutLocs, Preds);
2752 
2753  if (ValueNum) {
2754  InLocsChanged |= LiveIn->ID != *ValueNum;
2755  LiveIn->ID = *ValueNum;
2756  }
2757  }
2758 
2759  if (!InLocsChanged && !FirstTrip)
2760  continue;
2761 
2762  DbgValue *LiveOut = LiveOutIdx[MBB];
2763  bool OLChanged = false;
2764 
2765  // Do transfer function.
2766  auto &VTracker = AllTheVLocs[MBB->getNumber()];
2767  auto TransferIt = VTracker.Vars.find(Var);
2768  if (TransferIt != VTracker.Vars.end()) {
2769  // Erase on empty transfer (DBG_VALUE $noreg).
2770  if (TransferIt->second.Kind == DbgValue::Undef) {
2771  DbgValue NewVal(MBB->getNumber(), EmptyProperties, DbgValue::NoVal);
2772  if (*LiveOut != NewVal) {
2773  *LiveOut = NewVal;
2774  OLChanged = true;
2775  }
2776  } else {
2777  // Insert new variable value; or overwrite.
2778  if (*LiveOut != TransferIt->second) {
2779  *LiveOut = TransferIt->second;
2780  OLChanged = true;
2781  }
2782  }
2783  } else {
2784  // Just copy live-ins to live-outs, for anything not transferred.
2785  if (*LiveOut != *LiveIn) {
2786  *LiveOut = *LiveIn;
2787  OLChanged = true;
2788  }
2789  }
2790 
2791  // If no live-out value changed, there's no need to explore further.
2792  if (!OLChanged)
2793  continue;
2794 
2795  // We should visit all successors. Ensure we'll visit any non-backedge
2796  // successors during this dataflow iteration; book backedge successors
2797  // to be visited next time around.
2798  for (auto s : MBB->successors()) {
2799  // Ignore out of scope / not-to-be-explored successors.
2800  if (LiveInIdx.find(s) == LiveInIdx.end())
2801  continue;
2802 
2803  if (BBToOrder[s] > BBToOrder[MBB]) {
2804  if (OnWorklist.insert(s).second)
2805  Worklist.push(BBToOrder[s]);
2806  } else if (OnPending.insert(s).second && (FirstTrip || OLChanged)) {
2807  Pending.push(BBToOrder[s]);
2808  }
2809  }
2810  }
2811  Worklist.swap(Pending);
2812  std::swap(OnWorklist, OnPending);
2813  OnPending.clear();
2814  assert(Pending.empty());
2815  FirstTrip = false;
2816  }
2817 
2818  // Save live-ins to output vector. Ignore any that are still marked as being
2819  // VPHIs with no location -- those are variables that we know the value of,
2820  // but are not actually available in the register file.
2821  for (auto *MBB : BlockOrders) {
2822  DbgValue *BlockLiveIn = LiveInIdx[MBB];
2823  if (BlockLiveIn->Kind == DbgValue::NoVal)
2824  continue;
2825  if (BlockLiveIn->Kind == DbgValue::VPHI &&
2826  BlockLiveIn->ID == ValueIDNum::EmptyValue)
2827  continue;
2828  if (BlockLiveIn->Kind == DbgValue::VPHI)
2829  BlockLiveIn->Kind = DbgValue::Def;
2830  assert(BlockLiveIn->Properties.DIExpr->getFragmentInfo() ==
2831  Var.getFragment() && "Fragment info missing during value prop");
2832  Output[MBB->getNumber()].push_back(std::make_pair(Var, *BlockLiveIn));
2833  }
2834  } // Per-variable loop.
2835 
2836  BlockOrders.clear();
2837  BlocksToExplore.clear();
2838 }
2839 
2840 void InstrRefBasedLDV::placePHIsForSingleVarDefinition(
2841  const SmallPtrSetImpl<MachineBasicBlock *> &InScopeBlocks,
2842  MachineBasicBlock *AssignMBB, SmallVectorImpl<VLocTracker> &AllTheVLocs,
2843  const DebugVariable &Var, LiveInsT &Output) {
2844  // If there is a single definition of the variable, then working out it's
2845  // value everywhere is very simple: it's every block dominated by the
2846  // definition. At the dominance frontier, the usual algorithm would:
2847  // * Place PHIs,
2848  // * Propagate values into them,
2849  // * Find there's no incoming variable value from the other incoming branches
2850  // of the dominance frontier,
2851  // * Specify there's no variable value in blocks past the frontier.
2852  // This is a common case, hence it's worth special-casing it.
2853 
2854  // Pick out the variables value from the block transfer function.
2855  VLocTracker &VLocs = AllTheVLocs[AssignMBB->getNumber()];
2856  auto ValueIt = VLocs.Vars.find(Var);
2857  const DbgValue &Value = ValueIt->second;
2858 
2859  // If it's an explicit assignment of "undef", that means there is no location
2860  // anyway, anywhere.
2861  if (Value.Kind == DbgValue::Undef)
2862  return;
2863 
2864  // Assign the variable value to entry to each dominated block that's in scope.
2865  // Skip the definition block -- it's assigned the variable value in the middle
2866  // of the block somewhere.
2867  for (auto *ScopeBlock : InScopeBlocks) {
2868  if (!DomTree->properlyDominates(AssignMBB, ScopeBlock))
2869  continue;
2870 
2871  Output[ScopeBlock->getNumber()].push_back({Var, Value});
2872  }
2873 
2874  // All blocks that aren't dominated have no live-in value, thus no variable
2875  // value will be given to them.
2876 }
2877 
2878 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2880  const MLocTransferMap &mloc_transfer) const {
2881  for (auto &P : mloc_transfer) {
2882  std::string foo = MTracker->LocIdxToName(P.first);
2883  std::string bar = MTracker->IDAsString(P.second);
2884  dbgs() << "Loc " << foo << " --> " << bar << "\n";
2885  }
2886 }
2887 #endif
2888 
2889 void InstrRefBasedLDV::initialSetup(MachineFunction &MF) {
2890  // Build some useful data structures.
2891 
2893  EmptyExpr = DIExpression::get(Context, {});
2894 
2895  auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
2896  if (const DebugLoc &DL = MI.getDebugLoc())
2897  return DL.getLine() != 0;
2898  return false;
2899  };
2900  // Collect a set of all the artificial blocks.
2901  for (auto &MBB : MF)
2902  if (none_of(MBB.instrs(), hasNonArtificialLocation))
2903  ArtificialBlocks.insert(&MBB);
2904 
2905  // Compute mappings of block <=> RPO order.
2907  unsigned int RPONumber = 0;
2908  for (MachineBasicBlock *MBB : RPOT) {
2909  OrderToBB[RPONumber] = MBB;
2910  BBToOrder[MBB] = RPONumber;
2911  BBNumToRPO[MBB->getNumber()] = RPONumber;
2912  ++RPONumber;
2913  }
2914 
2915  // Order value substitutions by their "source" operand pair, for quick lookup.
2916  llvm::sort(MF.DebugValueSubstitutions);
2917 
2918 #ifdef EXPENSIVE_CHECKS
2919  // As an expensive check, test whether there are any duplicate substitution
2920  // sources in the collection.
2921  if (MF.DebugValueSubstitutions.size() > 2) {
2922  for (auto It = MF.DebugValueSubstitutions.begin();
2923  It != std::prev(MF.DebugValueSubstitutions.end()); ++It) {
2924  assert(It->Src != std::next(It)->Src && "Duplicate variable location "
2925  "substitution seen");
2926  }
2927  }
2928 #endif
2929 }
2930 
2931 // Produce an "ejection map" for blocks, i.e., what's the highest-numbered
2932 // lexical scope it's used in. When exploring in DFS order and we pass that
2933 // scope, the block can be processed and any tracking information freed.
2934 void InstrRefBasedLDV::makeDepthFirstEjectionMap(
2935  SmallVectorImpl<unsigned> &EjectionMap,
2936  const ScopeToDILocT &ScopeToDILocation,
2937  ScopeToAssignBlocksT &ScopeToAssignBlocks) {
2940  auto *TopScope = LS.getCurrentFunctionScope();
2941 
2942  // Unlike lexical scope explorers, we explore in reverse order, to find the
2943  // "last" lexical scope used for each block early.
2944  WorkStack.push_back({TopScope, TopScope->getChildren().size() - 1});
2945 
2946  while (!WorkStack.empty()) {
2947  auto &ScopePosition = WorkStack.back();
2948  LexicalScope *WS = ScopePosition.first;
2949  ssize_t ChildNum = ScopePosition.second--;
2950 
2951  const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
2952  if (ChildNum >= 0) {
2953  // If ChildNum is positive, there are remaining children to explore.
2954  // Push the child and its children-count onto the stack.
2955  auto &ChildScope = Children[ChildNum];
2956  WorkStack.push_back(
2957  std::make_pair(ChildScope, ChildScope->getChildren().size() - 1));
2958  } else {
2959  WorkStack.pop_back();
2960 
2961  // We've explored all children and any later blocks: examine all blocks
2962  // in our scope. If they haven't yet had an ejection number set, then
2963  // this scope will be the last to use that block.
2964  auto DILocationIt = ScopeToDILocation.find(WS);
2965  if (DILocationIt != ScopeToDILocation.end()) {
2966  getBlocksForScope(DILocationIt->second, BlocksToExplore,
2967  ScopeToAssignBlocks.find(WS)->second);
2968  for (auto *MBB : BlocksToExplore) {
2969  unsigned BBNum = MBB->getNumber();
2970  if (EjectionMap[BBNum] == 0)
2971  EjectionMap[BBNum] = WS->getDFSOut();
2972  }
2973 
2974  BlocksToExplore.clear();
2975  }
2976  }
2977  }
2978 }
2979 
2980 bool InstrRefBasedLDV::depthFirstVLocAndEmit(
2981  unsigned MaxNumBlocks, const ScopeToDILocT &ScopeToDILocation,
2982  const ScopeToVarsT &ScopeToVars, ScopeToAssignBlocksT &ScopeToAssignBlocks,
2983  LiveInsT &Output, FuncValueTable &MOutLocs, FuncValueTable &MInLocs,
2985  DenseMap<DebugVariable, unsigned> &AllVarsNumbering,
2986  const TargetPassConfig &TPC) {
2987  TTracker = new TransferTracker(TII, MTracker, MF, *TRI, CalleeSavedRegs, TPC);
2988  unsigned NumLocs = MTracker->getNumLocs();
2989  VTracker = nullptr;
2990 
2991  // No scopes? No variable locations.
2992  if (!LS.getCurrentFunctionScope())
2993  return false;
2994 
2995  // Build map from block number to the last scope that uses the block.
2996  SmallVector<unsigned, 16> EjectionMap;
2997  EjectionMap.resize(MaxNumBlocks, 0);
2998  makeDepthFirstEjectionMap(EjectionMap, ScopeToDILocation,
2999  ScopeToAssignBlocks);
3000 
3001  // Helper lambda for ejecting a block -- if nothing is going to use the block,
3002  // we can translate the variable location information into DBG_VALUEs and then
3003  // free all of InstrRefBasedLDV's data structures.
3004  auto EjectBlock = [&](MachineBasicBlock &MBB) -> void {
3005  unsigned BBNum = MBB.getNumber();
3006  AllTheVLocs[BBNum].clear();
3007 
3008  // Prime the transfer-tracker, and then step through all the block
3009  // instructions, installing transfers.
3010  MTracker->reset();
3011  MTracker->loadFromArray(MInLocs[BBNum], BBNum);
3012  TTracker->loadInlocs(MBB, MInLocs[BBNum], Output[BBNum], NumLocs);
3013 
3014  CurBB = BBNum;
3015  CurInst = 1;
3016  for (auto &MI : MBB) {
3017  process(MI, MOutLocs.get(), MInLocs.get());
3018  TTracker->checkInstForNewValues(CurInst, MI.getIterator());
3019  ++CurInst;
3020  }
3021 
3022  // Free machine-location tables for this block.
3023  MInLocs[BBNum].reset();
3024  MOutLocs[BBNum].reset();
3025  // We don't need live-in variable values for this block either.
3026  Output[BBNum].clear();
3027  AllTheVLocs[BBNum].clear();
3028  };
3029 
3032  WorkStack.push_back({LS.getCurrentFunctionScope(), 0});
3033  unsigned HighestDFSIn = 0;
3034 
3035  // Proceed to explore in depth first order.
3036  while (!WorkStack.empty()) {
3037  auto &ScopePosition = WorkStack.back();
3038  LexicalScope *WS = ScopePosition.first;
3039  ssize_t ChildNum = ScopePosition.second++;
3040 
3041  // We obesrve scopes with children twice here, once descending in, once
3042  // ascending out of the scope nest. Use HighestDFSIn as a ratchet to ensure
3043  // we don't process a scope twice. Additionally, ignore scopes that don't
3044  // have a DILocation -- by proxy, this means we never tracked any variable
3045  // assignments in that scope.
3046  auto DILocIt = ScopeToDILocation.find(WS);
3047  if (HighestDFSIn <= WS->getDFSIn() && DILocIt != ScopeToDILocation.end()) {
3048  const DILocation *DILoc = DILocIt->second;
3049  auto &VarsWeCareAbout = ScopeToVars.find(WS)->second;
3050  auto &BlocksInScope = ScopeToAssignBlocks.find(WS)->second;
3051 
3052  buildVLocValueMap(DILoc, VarsWeCareAbout, BlocksInScope, Output, MOutLocs,
3053  MInLocs, AllTheVLocs);
3054  }
3055 
3056  HighestDFSIn = std::max(HighestDFSIn, WS->getDFSIn());
3057 
3058  // Descend into any scope nests.
3059  const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
3060  if (ChildNum < (ssize_t)Children.size()) {
3061  // There are children to explore -- push onto stack and continue.
3062  auto &ChildScope = Children[ChildNum];
3063  WorkStack.push_back(std::make_pair(ChildScope, 0));
3064  } else {
3065  WorkStack.pop_back();
3066 
3067  // We've explored a leaf, or have explored all the children of a scope.
3068  // Try to eject any blocks where this is the last scope it's relevant to.
3069  auto DILocationIt = ScopeToDILocation.find(WS);
3070  if (DILocationIt == ScopeToDILocation.end())
3071  continue;
3072 
3073  getBlocksForScope(DILocationIt->second, BlocksToExplore,
3074  ScopeToAssignBlocks.find(WS)->second);
3075  for (auto *MBB : BlocksToExplore)
3076  if (WS->getDFSOut() == EjectionMap[MBB->getNumber()])
3077  EjectBlock(const_cast<MachineBasicBlock &>(*MBB));
3078 
3079  BlocksToExplore.clear();
3080  }
3081  }
3082 
3083  // Some artificial blocks may not have been ejected, meaning they're not
3084  // connected to an actual legitimate scope. This can technically happen
3085  // with things like the entry block. In theory, we shouldn't need to do
3086  // anything for such out-of-scope blocks, but for the sake of being similar
3087  // to VarLocBasedLDV, eject these too.
3088  for (auto *MBB : ArtificialBlocks)
3089  if (MOutLocs[MBB->getNumber()])
3090  EjectBlock(*MBB);
3091 
3092  return emitTransfers(AllVarsNumbering);
3093 }
3094 
3095 bool InstrRefBasedLDV::emitTransfers(
3096  DenseMap<DebugVariable, unsigned> &AllVarsNumbering) {
3097  // Go through all the transfers recorded in the TransferTracker -- this is
3098  // both the live-ins to a block, and any movements of values that happen
3099  // in the middle.
3100  for (const auto &P : TTracker->Transfers) {
3101  // We have to insert DBG_VALUEs in a consistent order, otherwise they
3102  // appear in DWARF in different orders. Use the order that they appear
3103  // when walking through each block / each instruction, stored in
3104  // AllVarsNumbering.
3106  for (MachineInstr *MI : P.Insts) {
3107  DebugVariable Var(MI->getDebugVariable(), MI->getDebugExpression(),
3108  MI->getDebugLoc()->getInlinedAt());
3109  Insts.emplace_back(AllVarsNumbering.find(Var)->second, MI);
3110  }
3111  llvm::sort(Insts,
3112  [](const auto &A, const auto &B) { return A.first < B.first; });
3113 
3114  // Insert either before or after the designated point...
3115  if (P.MBB) {
3116  MachineBasicBlock &MBB = *P.MBB;
3117  for (const auto &Pair : Insts)
3118  MBB.insert(P.Pos, Pair.second);
3119  } else {
3120  // Terminators, like tail calls, can clobber things. Don't try and place
3121  // transfers after them.
3122  if (P.Pos->isTerminator())
3123  continue;
3124 
3125  MachineBasicBlock &MBB = *P.Pos->getParent();
3126  for (const auto &Pair : Insts)
3127  MBB.insertAfterBundle(P.Pos, Pair.second);
3128  }
3129  }
3130 
3131  return TTracker->Transfers.size() != 0;
3132 }
3133 
3134 /// Calculate the liveness information for the given machine function and
3135 /// extend ranges across basic blocks.
3136 bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
3137  MachineDominatorTree *DomTree,
3138  TargetPassConfig *TPC,
3139  unsigned InputBBLimit,
3140  unsigned InputDbgValLimit) {
3141  // No subprogram means this function contains no debuginfo.
3142  if (!MF.getFunction().getSubprogram())
3143  return false;
3144 
3145  LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
3146  this->TPC = TPC;
3147 
3148  this->DomTree = DomTree;
3149  TRI = MF.getSubtarget().getRegisterInfo();
3150  MRI = &MF.getRegInfo();
3151  TII = MF.getSubtarget().getInstrInfo();
3152  TFI = MF.getSubtarget().getFrameLowering();
3153  TFI->getCalleeSaves(MF, CalleeSavedRegs);
3154  MFI = &MF.getFrameInfo();
3155  LS.initialize(MF);
3156 
3157  const auto &STI = MF.getSubtarget();
3158  AdjustsStackInCalls = MFI->adjustsStack() &&
3159  STI.getFrameLowering()->stackProbeFunctionModifiesSP();
3160  if (AdjustsStackInCalls)
3161  StackProbeSymbolName = STI.getTargetLowering()->getStackProbeSymbolName(MF);
3162 
3163  MTracker =
3164  new MLocTracker(MF, *TII, *TRI, *MF.getSubtarget().getTargetLowering());
3165  VTracker = nullptr;
3166  TTracker = nullptr;
3167 
3168  SmallVector<MLocTransferMap, 32> MLocTransfer;
3170  LiveInsT SavedLiveIns;
3171 
3172  int MaxNumBlocks = -1;
3173  for (auto &MBB : MF)
3174  MaxNumBlocks = std::max(MBB.getNumber(), MaxNumBlocks);
3175  assert(MaxNumBlocks >= 0);
3176  ++MaxNumBlocks;
3177 
3178  initialSetup(MF);
3179 
3180  MLocTransfer.resize(MaxNumBlocks);
3181  vlocs.resize(MaxNumBlocks, VLocTracker(OverlapFragments, EmptyExpr));
3182  SavedLiveIns.resize(MaxNumBlocks);
3183 
3184  produceMLocTransferFunction(MF, MLocTransfer, MaxNumBlocks);
3185 
3186  // Allocate and initialize two array-of-arrays for the live-in and live-out
3187  // machine values. The outer dimension is the block number; while the inner
3188  // dimension is a LocIdx from MLocTracker.
3189  FuncValueTable MOutLocs = std::make_unique<ValueTable[]>(MaxNumBlocks);
3190  FuncValueTable MInLocs = std::make_unique<ValueTable[]>(MaxNumBlocks);
3191  unsigned NumLocs = MTracker->getNumLocs();
3192  for (int i = 0; i < MaxNumBlocks; ++i) {
3193  // These all auto-initialize to ValueIDNum::EmptyValue
3194  MOutLocs[i] = std::make_unique<ValueIDNum[]>(NumLocs);
3195  MInLocs[i] = std::make_unique<ValueIDNum[]>(NumLocs);
3196  }
3197 
3198  // Solve the machine value dataflow problem using the MLocTransfer function,
3199  // storing the computed live-ins / live-outs into the array-of-arrays. We use
3200  // both live-ins and live-outs for decision making in the variable value
3201  // dataflow problem.
3202  buildMLocValueMap(MF, MInLocs, MOutLocs, MLocTransfer);
3203 
3204  // Patch up debug phi numbers, turning unknown block-live-in values into
3205  // either live-through machine values, or PHIs.
3206  for (auto &DBG_PHI : DebugPHINumToValue) {
3207  // Identify unresolved block-live-ins.
3208  if (!DBG_PHI.ValueRead)
3209  continue;
3210 
3211  ValueIDNum &Num = *DBG_PHI.ValueRead;
3212  if (!Num.isPHI())
3213  continue;
3214 
3215  unsigned BlockNo = Num.getBlock();
3216  LocIdx LocNo = Num.getLoc();
3217  Num = MInLocs[BlockNo][LocNo.asU64()];
3218  }
3219  // Later, we'll be looking up ranges of instruction numbers.
3220  llvm::sort(DebugPHINumToValue);
3221 
3222  // Walk back through each block / instruction, collecting DBG_VALUE
3223  // instructions and recording what machine value their operands refer to.
3224  for (auto &OrderPair : OrderToBB) {
3225  MachineBasicBlock &MBB = *OrderPair.second;
3226  CurBB = MBB.getNumber();
3227  VTracker = &vlocs[CurBB];
3228  VTracker->MBB = &MBB;
3229  MTracker->loadFromArray(MInLocs[CurBB], CurBB);
3230  CurInst = 1;
3231  for (auto &MI : MBB) {
3232  process(MI, MOutLocs.get(), MInLocs.get());
3233  ++CurInst;
3234  }
3235  MTracker->reset();
3236  }
3237 
3238  // Number all variables in the order that they appear, to be used as a stable
3239  // insertion order later.
3240  DenseMap<DebugVariable, unsigned> AllVarsNumbering;
3241 
3242  // Map from one LexicalScope to all the variables in that scope.
3243  ScopeToVarsT ScopeToVars;
3244 
3245  // Map from One lexical scope to all blocks where assignments happen for
3246  // that scope.
3247  ScopeToAssignBlocksT ScopeToAssignBlocks;
3248 
3249  // Store map of DILocations that describes scopes.
3250  ScopeToDILocT ScopeToDILocation;
3251 
3252  // To mirror old LiveDebugValues, enumerate variables in RPOT order. Otherwise
3253  // the order is unimportant, it just has to be stable.
3254  unsigned VarAssignCount = 0;
3255  for (unsigned int I = 0; I < OrderToBB.size(); ++I) {
3256  auto *MBB = OrderToBB[I];
3257  auto *VTracker = &vlocs[MBB->getNumber()];
3258  // Collect each variable with a DBG_VALUE in this block.
3259  for (auto &idx : VTracker->Vars) {
3260  const auto &Var = idx.first;
3261  const DILocation *ScopeLoc = VTracker->Scopes[Var];
3262  assert(ScopeLoc != nullptr);
3263  auto *Scope = LS.findLexicalScope(ScopeLoc);
3264 
3265  // No insts in scope -> shouldn't have been recorded.
3266  assert(Scope != nullptr);
3267 
3268  AllVarsNumbering.insert(std::make_pair(Var, AllVarsNumbering.size()));
3269  ScopeToVars[Scope].insert(Var);
3270  ScopeToAssignBlocks[Scope].insert(VTracker->MBB);
3271  ScopeToDILocation[Scope] = ScopeLoc;
3272  ++VarAssignCount;
3273  }
3274  }
3275 
3276  bool Changed = false;
3277 
3278  // If we have an extremely large number of variable assignments and blocks,
3279  // bail out at this point. We've burnt some time doing analysis already,
3280  // however we should cut our losses.
3281  if ((unsigned)MaxNumBlocks > InputBBLimit &&
3282  VarAssignCount > InputDbgValLimit) {
3283  LLVM_DEBUG(dbgs() << "Disabling InstrRefBasedLDV: " << MF.getName()
3284  << " has " << MaxNumBlocks << " basic blocks and "
3285  << VarAssignCount
3286  << " variable assignments, exceeding limits.\n");
3287  } else {
3288  // Optionally, solve the variable value problem and emit to blocks by using
3289  // a lexical-scope-depth search. It should be functionally identical to
3290  // the "else" block of this condition.
3291  Changed = depthFirstVLocAndEmit(
3292  MaxNumBlocks, ScopeToDILocation, ScopeToVars, ScopeToAssignBlocks,
3293  SavedLiveIns, MOutLocs, MInLocs, vlocs, MF, AllVarsNumbering, *TPC);
3294  }
3295 
3296  delete MTracker;
3297  delete TTracker;
3298  MTracker = nullptr;
3299  VTracker = nullptr;
3300  TTracker = nullptr;
3301 
3302  ArtificialBlocks.clear();
3303  OrderToBB.clear();
3304  BBToOrder.clear();
3305  BBNumToRPO.clear();
3306  DebugInstrNumToInstr.clear();
3307  DebugPHINumToValue.clear();
3308  OverlapFragments.clear();
3309  SeenFragments.clear();
3310  SeenDbgPHIs.clear();
3311 
3312  return Changed;
3313 }
3314 
3316  return new InstrRefBasedLDV();
3317 }
3318 
3319 namespace {
3320 class LDVSSABlock;
3321 class LDVSSAUpdater;
3322 
3323 // Pick a type to identify incoming block values as we construct SSA. We
3324 // can't use anything more robust than an integer unfortunately, as SSAUpdater
3325 // expects to zero-initialize the type.
3326 typedef uint64_t BlockValueNum;
3327 
3328 /// Represents an SSA PHI node for the SSA updater class. Contains the block
3329 /// this PHI is in, the value number it would have, and the expected incoming
3330 /// values from parent blocks.
3331 class LDVSSAPhi {
3332 public:
3334  LDVSSABlock *ParentBlock;
3335  BlockValueNum PHIValNum;
3336  LDVSSAPhi(BlockValueNum PHIValNum, LDVSSABlock *ParentBlock)
3337  : ParentBlock(ParentBlock), PHIValNum(PHIValNum) {}
3338 
3339  LDVSSABlock *getParent() { return ParentBlock; }
3340 };
3341 
3342 /// Thin wrapper around a block predecessor iterator. Only difference from a
3343 /// normal block iterator is that it dereferences to an LDVSSABlock.
3344 class LDVSSABlockIterator {
3345 public:
3347  LDVSSAUpdater &Updater;
3348 
3349  LDVSSABlockIterator(MachineBasicBlock::pred_iterator PredIt,
3350  LDVSSAUpdater &Updater)
3351  : PredIt(PredIt), Updater(Updater) {}
3352 
3353  bool operator!=(const LDVSSABlockIterator &OtherIt) const {
3354  return OtherIt.PredIt != PredIt;
3355  }
3356 
3357  LDVSSABlockIterator &operator++() {
3358  ++PredIt;
3359  return *this;
3360  }
3361 
3362  LDVSSABlock *operator*();
3363 };
3364 
3365 /// Thin wrapper around a block for SSA Updater interface. Necessary because
3366 /// we need to track the PHI value(s) that we may have observed as necessary
3367 /// in this block.
3368 class LDVSSABlock {
3369 public:
3371  LDVSSAUpdater &Updater;
3372  using PHIListT = SmallVector<LDVSSAPhi, 1>;
3373  /// List of PHIs in this block. There should only ever be one.
3374  PHIListT PHIList;
3375 
3376  LDVSSABlock(MachineBasicBlock &BB, LDVSSAUpdater &Updater)
3377  : BB(BB), Updater(Updater) {}
3378 
3379  LDVSSABlockIterator succ_begin() {
3380  return LDVSSABlockIterator(BB.succ_begin(), Updater);
3381  }
3382 
3383  LDVSSABlockIterator succ_end() {
3384  return LDVSSABlockIterator(BB.succ_end(), Updater);
3385  }
3386 
3387  /// SSAUpdater has requested a PHI: create that within this block record.
3388  LDVSSAPhi *newPHI(BlockValueNum Value) {
3389  PHIList.emplace_back(Value, this);
3390  return &PHIList.back();
3391  }
3392 
3393  /// SSAUpdater wishes to know what PHIs already exist in this block.
3394  PHIListT &phis() { return PHIList; }
3395 };
3396 
3397 /// Utility class for the SSAUpdater interface: tracks blocks, PHIs and values
3398 /// while SSAUpdater is exploring the CFG. It's passed as a handle / baton to
3399 // SSAUpdaterTraits<LDVSSAUpdater>.
3400 class LDVSSAUpdater {
3401 public:
3402  /// Map of value numbers to PHI records.
3404  /// Map of which blocks generate Undef values -- blocks that are not
3405  /// dominated by any Def.
3407  /// Map of machine blocks to our own records of them.
3409  /// Machine location where any PHI must occur.
3410  LocIdx Loc;
3411  /// Table of live-in machine value numbers for blocks / locations.
3412  const ValueTable *MLiveIns;
3413 
3414  LDVSSAUpdater(LocIdx L, const ValueTable *MLiveIns)
3415  : Loc(L), MLiveIns(MLiveIns) {}
3416 
3417  void reset() {
3418  for (auto &Block : BlockMap)
3419  delete Block.second;
3420 
3421  PHIs.clear();
3422  UndefMap.clear();
3423  BlockMap.clear();
3424  }
3425 
3426  ~LDVSSAUpdater() { reset(); }
3427 
3428  /// For a given MBB, create a wrapper block for it. Stores it in the
3429  /// LDVSSAUpdater block map.
3430  LDVSSABlock *getSSALDVBlock(MachineBasicBlock *BB) {
3431  auto it = BlockMap.find(BB);
3432  if (it == BlockMap.end()) {
3433  BlockMap[BB] = new LDVSSABlock(*BB, *this);
3434  it = BlockMap.find(BB);
3435  }
3436  return it->second;
3437  }
3438 
3439  /// Find the live-in value number for the given block. Looks up the value at
3440  /// the PHI location on entry.
3441  BlockValueNum getValue(LDVSSABlock *LDVBB) {
3442  return MLiveIns[LDVBB->BB.getNumber()][Loc.asU64()].asU64();
3443  }
3444 };
3445 
3446 LDVSSABlock *LDVSSABlockIterator::operator*() {
3447  return Updater.getSSALDVBlock(*PredIt);
3448 }
3449 
3450 #ifndef NDEBUG
3451 
3452 raw_ostream &operator<<(raw_ostream &out, const LDVSSAPhi &PHI) {
3453  out << "SSALDVPHI " << PHI.PHIValNum;
3454  return out;
3455 }
3456 
3457 #endif
3458 
3459 } // namespace
3460 
3461 namespace llvm {
3462 
3463 /// Template specialization to give SSAUpdater access to CFG and value
3464 /// information. SSAUpdater calls methods in these traits, passing in the
3465 /// LDVSSAUpdater object, to learn about blocks and the values they define.
3466 /// It also provides methods to create PHI nodes and track them.
3467 template <> class SSAUpdaterTraits<LDVSSAUpdater> {
3468 public:
3469  using BlkT = LDVSSABlock;
3470  using ValT = BlockValueNum;
3471  using PhiT = LDVSSAPhi;
3472  using BlkSucc_iterator = LDVSSABlockIterator;
3473 
3474  // Methods to access block successors -- dereferencing to our wrapper class.
3475  static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); }
3476  static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); }
3477 
3478  /// Iterator for PHI operands.
3479  class PHI_iterator {
3480  private:
3481  LDVSSAPhi *PHI;
3482  unsigned Idx;
3483 
3484  public:
3485  explicit PHI_iterator(LDVSSAPhi *P) // begin iterator
3486  : PHI(P), Idx(0) {}
3487  PHI_iterator(LDVSSAPhi *P, bool) // end iterator
3488  : PHI(P), Idx(PHI->IncomingValues.size()) {}
3489 
3490  PHI_iterator &operator++() {
3491  Idx++;
3492  return *this;
3493  }
3494  bool operator==(const PHI_iterator &X) const { return Idx == X.Idx; }
3495  bool operator!=(const PHI_iterator &X) const { return !operator==(X); }
3496 
3497  BlockValueNum getIncomingValue() { return PHI->IncomingValues[Idx].second; }
3498 
3499  LDVSSABlock *getIncomingBlock() { return PHI->IncomingValues[Idx].first; }
3500  };
3501 
3502  static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
3503 
3504  static inline PHI_iterator PHI_end(PhiT *PHI) {
3505  return PHI_iterator(PHI, true);
3506  }
3507 
3508  /// FindPredecessorBlocks - Put the predecessors of BB into the Preds
3509  /// vector.
3510  static void FindPredecessorBlocks(LDVSSABlock *BB,
3512  for (MachineBasicBlock *Pred : BB->BB.predecessors())
3513  Preds->push_back(BB->Updater.getSSALDVBlock(Pred));
3514  }
3515 
3516  /// GetUndefVal - Normally creates an IMPLICIT_DEF instruction with a new
3517  /// register. For LiveDebugValues, represents a block identified as not having
3518  /// any DBG_PHI predecessors.
3519  static BlockValueNum GetUndefVal(LDVSSABlock *BB, LDVSSAUpdater *Updater) {
3520  // Create a value number for this block -- it needs to be unique and in the
3521  // "undef" collection, so that we know it's not real. Use a number
3522  // representing a PHI into this block.
3523  BlockValueNum Num = ValueIDNum(BB->BB.getNumber(), 0, Updater->Loc).asU64();
3524  Updater->UndefMap[&BB->BB] = Num;
3525  return Num;
3526  }
3527 
3528  /// CreateEmptyPHI - Create a (representation of a) PHI in the given block.
3529  /// SSAUpdater will populate it with information about incoming values. The
3530  /// value number of this PHI is whatever the machine value number problem
3531  /// solution determined it to be. This includes non-phi values if SSAUpdater
3532  /// tries to create a PHI where the incoming values are identical.
3533  static BlockValueNum CreateEmptyPHI(LDVSSABlock *BB, unsigned NumPreds,
3534  LDVSSAUpdater *Updater) {
3535  BlockValueNum PHIValNum = Updater->getValue(BB);
3536  LDVSSAPhi *PHI = BB->newPHI(PHIValNum);
3537  Updater->PHIs[PHIValNum] = PHI;
3538  return PHIValNum;
3539  }
3540 
3541  /// AddPHIOperand - Add the specified value as an operand of the PHI for
3542  /// the specified predecessor block.
3543  static void AddPHIOperand(LDVSSAPhi *PHI, BlockValueNum Val, LDVSSABlock *Pred) {
3544  PHI->IncomingValues.push_back(std::make_pair(Pred, Val));
3545  }
3546 
3547  /// ValueIsPHI - Check if the instruction that defines the specified value
3548  /// is a PHI instruction.
3549  static LDVSSAPhi *ValueIsPHI(BlockValueNum Val, LDVSSAUpdater *Updater) {
3550  auto PHIIt = Updater->PHIs.find(Val);
3551  if (PHIIt == Updater->PHIs.end())
3552  return nullptr;
3553  return PHIIt->second;
3554  }
3555 
3556  /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
3557  /// operands, i.e., it was just added.
3558  static LDVSSAPhi *ValueIsNewPHI(BlockValueNum Val, LDVSSAUpdater *Updater) {
3559  LDVSSAPhi *PHI = ValueIsPHI(Val, Updater);
3560  if (PHI && PHI->IncomingValues.size() == 0)
3561  return PHI;
3562  return nullptr;
3563  }
3564 
3565  /// GetPHIValue - For the specified PHI instruction, return the value
3566  /// that it defines.
3567  static BlockValueNum GetPHIValue(LDVSSAPhi *PHI) { return PHI->PHIValNum; }
3568 };
3569 
3570 } // end namespace llvm
3571 
3572 Optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIs(
3573  MachineFunction &MF, const ValueTable *MLiveOuts,
3574  const ValueTable *MLiveIns, MachineInstr &Here, uint64_t InstrNum) {
3575  assert(MLiveOuts && MLiveIns &&
3576  "Tried to resolve DBG_PHI before location "
3577  "tables allocated?");
3578 
3579  // This function will be called twice per DBG_INSTR_REF, and might end up
3580  // computing lots of SSA information: memoize it.
3581  auto SeenDbgPHIIt = SeenDbgPHIs.find(&Here);
3582  if (SeenDbgPHIIt != SeenDbgPHIs.end())
3583  return SeenDbgPHIIt->second;
3584 
3586  resolveDbgPHIsImpl(MF, MLiveOuts, MLiveIns, Here, InstrNum);
3587  SeenDbgPHIs.insert({&Here, Result});
3588  return Result;
3589 }
3590 
3591 Optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIsImpl(
3592  MachineFunction &MF, const ValueTable *MLiveOuts,
3593  const ValueTable *MLiveIns, MachineInstr &Here, uint64_t InstrNum) {
3594  // Pick out records of DBG_PHI instructions that have been observed. If there
3595  // are none, then we cannot compute a value number.
3596  auto RangePair = std::equal_range(DebugPHINumToValue.begin(),
3597  DebugPHINumToValue.end(), InstrNum);
3598  auto LowerIt = RangePair.first;
3599  auto UpperIt = RangePair.second;
3600 
3601  // No DBG_PHI means there can be no location.
3602  if (LowerIt == UpperIt)
3603  return None;
3604 
3605  // If any DBG_PHIs referred to a location we didn't understand, don't try to
3606  // compute a value. There might be scenarios where we could recover a value
3607  // for some range of DBG_INSTR_REFs, but at this point we can have high
3608  // confidence that we've seen a bug.
3609  auto DBGPHIRange = make_range(LowerIt, UpperIt);
3610  for (const DebugPHIRecord &DBG_PHI : DBGPHIRange)
3611  if (!DBG_PHI.ValueRead)
3612  return None;
3613 
3614  // If there's only one DBG_PHI, then that is our value number.
3615  if (std::distance(LowerIt, UpperIt) == 1)
3616  return *LowerIt->ValueRead;
3617 
3618  // Pick out the location (physreg, slot) where any PHIs must occur. It's
3619  // technically possible for us to merge values in different registers in each
3620  // block, but highly unlikely that LLVM will generate such code after register
3621  // allocation.
3622  LocIdx Loc = *LowerIt->ReadLoc;
3623 
3624  // We have several DBG_PHIs, and a use position (the Here inst). All each
3625  // DBG_PHI does is identify a value at a program position. We can treat each
3626  // DBG_PHI like it's a Def of a value, and the use position is a Use of a
3627  // value, just like SSA. We use the bulk-standard LLVM SSA updater class to
3628  // determine which Def is used at the Use, and any PHIs that happen along
3629  // the way.
3630  // Adapted LLVM SSA Updater:
3631  LDVSSAUpdater Updater(Loc, MLiveIns);
3632  // Map of which Def or PHI is the current value in each block.
3634  // Set of PHIs that we have created along the way.
3635  SmallVector<LDVSSAPhi *, 8> CreatedPHIs;
3636 
3637  // Each existing DBG_PHI is a Def'd value under this model. Record these Defs
3638  // for the SSAUpdater.
3639  for (const auto &DBG_PHI : DBGPHIRange) {
3640  LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB);
3641  const ValueIDNum &Num = *DBG_PHI.ValueRead;
3642  AvailableValues.insert(std::make_pair(Block, Num.asU64()));
3643  }
3644 
3645  LDVSSABlock *HereBlock = Updater.getSSALDVBlock(Here.getParent());
3646  const auto &AvailIt = AvailableValues.find(HereBlock);
3647  if (AvailIt != AvailableValues.end()) {
3648  // Actually, we already know what the value is -- the Use is in the same
3649  // block as the Def.
3650  return ValueIDNum::fromU64(AvailIt->second);
3651  }
3652 
3653  // Otherwise, we must use the SSA Updater. It will identify the value number
3654  // that we are to use, and the PHIs that must happen along the way.
3655  SSAUpdaterImpl<LDVSSAUpdater> Impl(&Updater, &AvailableValues, &CreatedPHIs);
3656  BlockValueNum ResultInt = Impl.GetValue(Updater.getSSALDVBlock(Here.getParent()));
3657  ValueIDNum Result = ValueIDNum::fromU64(ResultInt);
3658 
3659  // We have the number for a PHI, or possibly live-through value, to be used
3660  // at this Use. There are a number of things we have to check about it though:
3661  // * Does any PHI use an 'Undef' (like an IMPLICIT_DEF) value? If so, this
3662  // Use was not completely dominated by DBG_PHIs and we should abort.
3663  // * Are the Defs or PHIs clobbered in a block? SSAUpdater isn't aware that
3664  // we've left SSA form. Validate that the inputs to each PHI are the
3665  // expected values.
3666  // * Is a PHI we've created actually a merging of values, or are all the
3667  // predecessor values the same, leading to a non-PHI machine value number?
3668  // (SSAUpdater doesn't know that either). Remap validated PHIs into the
3669  // the ValidatedValues collection below to sort this out.
3670  DenseMap<LDVSSABlock *, ValueIDNum> ValidatedValues;
3671 
3672  // Define all the input DBG_PHI values in ValidatedValues.
3673  for (const auto &DBG_PHI : DBGPHIRange) {
3674  LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB);
3675  const ValueIDNum &Num = *DBG_PHI.ValueRead;
3676  ValidatedValues.insert(std::make_pair(Block, Num));
3677  }
3678 
3679  // Sort PHIs to validate into RPO-order.
3680  SmallVector<LDVSSAPhi *, 8> SortedPHIs;
3681  for (auto &PHI : CreatedPHIs)
3682  SortedPHIs.push_back(PHI);
3683 
3684  std::sort(
3685  SortedPHIs.begin(), SortedPHIs.end(), [&](LDVSSAPhi *A, LDVSSAPhi *B) {
3686  return BBToOrder[&A->getParent()->BB] < BBToOrder[&B->getParent()->BB];
3687  });
3688 
3689  for (auto &PHI : SortedPHIs) {
3690  ValueIDNum ThisBlockValueNum =
3691  MLiveIns[PHI->ParentBlock->BB.getNumber()][Loc.asU64()];
3692 
3693  // Are all these things actually defined?
3694  for (auto &PHIIt : PHI->IncomingValues) {
3695  // Any undef input means DBG_PHIs didn't dominate the use point.
3696  if (Updater.UndefMap.find(&PHIIt.first->BB) != Updater.UndefMap.end())
3697  return None;
3698 
3699  ValueIDNum ValueToCheck;
3700  const ValueTable &BlockLiveOuts = MLiveOuts[PHIIt.first->BB.getNumber()];
3701 
3702  auto VVal = ValidatedValues.find(PHIIt.first);
3703  if (VVal == ValidatedValues.end()) {
3704  // We cross a loop, and this is a backedge. LLVMs tail duplication
3705  // happens so late that DBG_PHI instructions should not be able to
3706  // migrate into loops -- meaning we can only be live-through this
3707  // loop.
3708  ValueToCheck = ThisBlockValueNum;
3709  } else {
3710  // Does the block have as a live-out, in the location we're examining,
3711  // the value that we expect? If not, it's been moved or clobbered.
3712  ValueToCheck = VVal->second;
3713  }
3714 
3715  if (BlockLiveOuts[Loc.asU64()] != ValueToCheck)
3716  return None;
3717  }
3718 
3719  // Record this value as validated.
3720  ValidatedValues.insert({PHI->ParentBlock, ThisBlockValueNum});
3721  }
3722 
3723  // All the PHIs are valid: we can return what the SSAUpdater said our value
3724  // number was.
3725  return Result;
3726 }
llvm::DIExpression::prepend
static DIExpression * prepend(const DIExpression *Expr, uint8_t Flags, int64_t Offset=0)
Prepend DIExpr with a deref and offset operation and optionally turn it into a stack value or/and an ...
Definition: DebugInfoMetadata.cpp:1451
llvm::Check::Size
@ Size
Definition: FileCheck.h:77
i
i
Definition: README.txt:29
llvm::TargetRegisterInfo::getRegAsmName
virtual StringRef getRegAsmName(MCRegister Reg) const
Return the assembly name for Reg.
Definition: TargetRegisterInfo.h:1022
LiveDebugValues::MLocTracker::setReg
void setReg(Register R, ValueIDNum ValueID)
Set a register to a value number.
Definition: InstrRefBasedImpl.h:587
llvm::TargetFrameLowering::getCalleeSaves
virtual void getCalleeSaves(const MachineFunction &MF, BitVector &SavedRegs) const
Returns the callee-saved registers as computed by determineCalleeSaves in the BitVector SavedRegs.
Definition: TargetFrameLoweringImpl.cpp:70
LiveDebugValues::MLocTracker::trackRegister
LocIdx trackRegister(unsigned ID)
Create a LocIdx for an untracked register ID.
Definition: InstrRefBasedImpl.cpp:745
CmpMode::FP
@ FP
llvm::SSAUpdaterTraits< LDVSSAUpdater >::ValT
BlockValueNum ValT
Definition: InstrRefBasedImpl.cpp:3470
LiveDebugValues::InstrRefBasedLDV::ScopeToVarsT
DenseMap< const LexicalScope *, SmallSet< DebugVariable, 4 > > ScopeToVarsT
Mapping from lexical scopes to variables in that scope.
Definition: InstrRefBasedImpl.h:810
TransferTracker::UseBeforeDefs
DenseMap< unsigned, SmallVector< UseBeforeDef, 1 > > UseBeforeDefs
Map from instruction index (within the block) to the set of UseBeforeDefs that become defined at that...
Definition: InstrRefBasedImpl.cpp:235
LiveDebugValues::MLocTracker::locations
iterator_range< MLocIterator > locations()
Return a range over all locations currently tracked.
Definition: InstrRefBasedImpl.h:656
llvm::TargetLoweringBase::getStackPointerRegisterToSaveRestore
Register getStackPointerRegisterToSaveRestore() const
If a physical register, this specifies the register that llvm.savestack/llvm.restorestack should save...
Definition: TargetLowering.h:1788
llvm::SSAUpdaterTraits< LDVSSAUpdater >::PHI_iterator::PHI_iterator
PHI_iterator(LDVSSAPhi *P, bool)
Definition: InstrRefBasedImpl.cpp:3487
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
llvm::SSAUpdaterTraits< LDVSSAUpdater >::PhiT
LDVSSAPhi PhiT
Definition: InstrRefBasedImpl.cpp:3471
MachineInstr.h
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:494
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::SSAUpdaterTraits< LDVSSAUpdater >::PHI_iterator::operator!=
bool operator!=(const PHI_iterator &X) const
Definition: InstrRefBasedImpl.cpp:3495
LiveDebugValues::ValueIDNum::asU64
uint64_t asU64() const
Definition: InstrRefBasedImpl.h:137
LiveDebugValues::DbgValueProperties::DIExpr
const DIExpression * DIExpr
Definition: InstrRefBasedImpl.h:220
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::MCSubRegIndexIterator
Iterator that enumerates the sub-registers of a Reg and the associated sub-register indices.
Definition: MCRegisterInfo.h:610
it
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in it
Definition: README-SSE.txt:81
llvm::none_of
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1631
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::SSAUpdaterTraits< LDVSSAUpdater >::GetPHIValue
static BlockValueNum GetPHIValue(LDVSSAPhi *PHI)
GetPHIValue - For the specified PHI instruction, return the value that it defines.
Definition: InstrRefBasedImpl.cpp:3567
TargetFrameLowering.h
llvm::MachineOperand::CreateReg
static MachineOperand CreateReg(Register Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)
Definition: MachineOperand.h:800
TransferTracker::UseBeforeDef::Var
DebugVariable Var
Identity of this variable.
Definition: InstrRefBasedImpl.cpp:228
llvm::PseudoSourceValue::isAliased
virtual bool isAliased(const MachineFrameInfo *) const
Test whether the memory pointed to by this PseudoSourceValue may also be pointed to by an LLVM IR Val...
Definition: PseudoSourceValue.cpp:47
LiveDebugValues::MLocTracker::NumRegs
unsigned NumRegs
Cached local copy of the number of registers the target has.
Definition: InstrRefBasedImpl.h:387
llvm::SharedLiveDebugValues::LDVImpl
Definition: LiveDebugValues.h:25
llvm::MachineDominatorTree::properlyDominates
bool properlyDominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Definition: MachineDominators.h:146
DebugInfoMetadata.h
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
LiveDebugValues::MLocTracker::MLocTracker
MLocTracker(MachineFunction &MF, const TargetInstrInfo &TII, const TargetRegisterInfo &TRI, const TargetLowering &TLI)
Definition: InstrRefBasedImpl.cpp:677
llvm::lower_bound
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1736
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:93
llvm::MachineBasicBlock::instrs
instr_range instrs()
Definition: MachineBasicBlock.h:273
LiveDebugValues::InstrRefBasedLDV::InstrRefBasedLDV
InstrRefBasedLDV()
Default construct and initialize the pass.
TypeSize.h
TransferTracker::Transfer::MBB
MachineBasicBlock * MBB
Position to insert DBG_VALUes.
Definition: InstrRefBasedImpl.cpp:190
llvm::lltok::bar
@ bar
Definition: LLToken.h:37
llvm::SmallVector< MachineInstr *, 4 >
LiveDebugValues::MLocTracker::writeRegMask
void writeRegMask(const MachineOperand *MO, unsigned CurBB, unsigned InstID)
Record a RegMask operand being executed.
Definition: InstrRefBasedImpl.cpp:767
LiveDebugValues::ValueIDNum
Unique identifier for a value defined by an instruction, as a value type.
Definition: InstrRefBasedImpl.h:105
llvm::DIVariable::getSizeInBits
Optional< uint64_t > getSizeInBits() const
Determines the size of the variable's type.
Definition: DebugInfoMetadata.cpp:1176
llvm::MachineBasicBlock::insertAfterBundle
instr_iterator insertAfterBundle(instr_iterator I, MachineInstr *MI)
If I is bundled then insert MI into the instruction list after the end of the bundle,...
Definition: MachineBasicBlock.h:913
llvm::LexicalScope
LexicalScope - This class is used to track scope information.
Definition: LexicalScopes.h:44
llvm::Function::getSubprogram
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1571
TransferTracker::PendingDbgValues
SmallVector< MachineInstr *, 4 > PendingDbgValues
Temporary cache of DBG_VALUEs to be entered into the Transfers collection.
Definition: InstrRefBasedImpl.cpp:219
llvm::MCRegisterInfo::getNumRegs
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Definition: MCRegisterInfo.h:491
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
LiveDebugValues::InstrRefBasedLDV::LiveIdxT
DenseMap< const MachineBasicBlock *, DbgValue * > LiveIdxT
Live in/out structure for the variable values: a per-block map of variables to their values.
Definition: InstrRefBasedImpl.h:795
TransferTracker::isEntryValueVariable
bool isEntryValueVariable(const DebugVariable &Var, const DIExpression *Expr) const
Definition: InstrRefBasedImpl.cpp:406
llvm::SmallDenseMap
Definition: DenseMap.h:882
llvm::BitVector::set_bits
iterator_range< const_set_bits_iterator > set_bits() const
Definition: BitVector.h:133
LiveDebugValues::MLocTracker::setMLoc
void setMLoc(LocIdx L, ValueIDNum Num)
Set a locaiton to a certain value.
Definition: InstrRefBasedImpl.h:547
MachineBasicBlock.h
llvm::TargetSubtargetInfo::getRegisterInfo
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Definition: TargetSubtargetInfo.h:125
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
LiveDebugValues::MLocTracker::getOrTrackSpillLoc
Optional< SpillLocationNo > getOrTrackSpillLoc(SpillLoc L)
Find LocIdx for SpillLoc L, creating a new one if it's not tracked.
Definition: InstrRefBasedImpl.cpp:781
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:304
NewExpr
Definition: ItaniumDemangle.h:1922
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:234
llvm::LexicalScope::getDFSIn
unsigned getDFSIn() const
Definition: LexicalScopes.h:115
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1557
llvm::Function::getContext
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:319
DenseMap.h
NUM_LOC_BITS
#define NUM_LOC_BITS
Definition: InstrRefBasedImpl.h:49
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
llvm::DebugVariable::getFragment
Optional< FragmentInfo > getFragment() const
Definition: DebugInfoMetadata.h:3643
TargetInstrInfo.h
LiveDebugValues::VLocTracker::Scopes
SmallDenseMap< DebugVariable, const DILocation *, 8 > Scopes
Definition: InstrRefBasedImpl.h:700
TransferTracker::flushDbgValues
void flushDbgValues(MachineBasicBlock::iterator Pos, MachineBasicBlock *MBB)
Helper to move created DBG_VALUEs into Transfers collection.
Definition: InstrRefBasedImpl.cpp:391
TransferTracker::Transfers
SmallVector< Transfer, 32 > Transfers
Collection of transfers (DBG_VALUEs) to be inserted.
Definition: InstrRefBasedImpl.cpp:200
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
TransferTracker::recoverAsEntryValue
bool recoverAsEntryValue(const DebugVariable &Var, const DbgValueProperties &Prop, const ValueIDNum &Num)
Definition: InstrRefBasedImpl.cpp:435
llvm::LexicalScopes::getMachineBasicBlocks
void getMachineBasicBlocks(const DILocation *DL, SmallPtrSetImpl< const MachineBasicBlock * > &MBBs)
getMachineBasicBlocks - Populate given set using machine basic blocks which have machine instructions...
Definition: LexicalScopes.cpp:280
llvm::operator!=
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:1992
llvm::Optional
Definition: APInt.h:33
llvm::TargetInstrInfo::isCopyInstr
Optional< DestSourcePair > isCopyInstr(const MachineInstr &MI) const
If the specific machine instruction is a instruction that moves/copies value from one register to ano...
Definition: TargetInstrInfo.h:1025
llvm::DILocalVariable::isParameter
bool isParameter() const
Definition: DebugInfoMetadata.h:3120
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
LiveDebugValues::MLocTracker::TRI
const TargetRegisterInfo & TRI
Definition: InstrRefBasedImpl.h:350
STLExtras.h
llvm::MachineBasicBlock::back
MachineInstr & back()
Definition: MachineBasicBlock.h:258
LiveDebugValues::ValueIDNum::isPHI
bool isPHI() const
Definition: InstrRefBasedImpl.h:135
llvm::DIExpression
DWARF expression.
Definition: DebugInfoMetadata.h:2558
llvm::LexicalScopes::initialize
void initialize(const MachineFunction &)
initialize - Scan machine function and constuct lexical scope nest, resets the instance if necessary.
Definition: LexicalScopes.cpp:51
llvm::MachineOperand::isFI
bool isFI() const
isFI - Tests if this is a MO_FrameIndex operand.
Definition: MachineOperand.h:330
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::detail::DenseSetImpl::count
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
LiveDebugValues::MLocTracker::TII
const TargetInstrInfo & TII
Definition: InstrRefBasedImpl.h:349
llvm::MCRegisterInfo::getNumSubRegIndices
unsigned getNumSubRegIndices() const
Return the number of sub-register indices understood by the target.
Definition: MCRegisterInfo.h:498
TransferTracker
Tracker for converting machine value locations and variable values into variable locations (the outpu...
Definition: InstrRefBasedImpl.cpp:174
TransferTracker::redefVar
void redefVar(const MachineInstr &MI)
Change a variable value after encountering a DBG_VALUE inside a block.
Definition: InstrRefBasedImpl.cpp:462
p
the resulting code requires compare and branches when and if * p
Definition: README.txt:396
TransferTracker::transferMlocs
void transferMlocs(LocIdx Src, LocIdx Dst, MachineBasicBlock::iterator Pos)
Transfer variables based on Src to be based on Dst.
Definition: InstrRefBasedImpl.cpp:600
llvm::MachineInstr::hasOneMemOperand
bool hasOneMemOperand() const
Return true if this instruction has exactly one MachineMemOperand.
Definition: MachineInstr.h:724
LiveDebugValues::DbgValue::ID
ValueIDNum ID
If Kind is Def, the value number that this value is based on.
Definition: InstrRefBasedImpl.h:234
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1300
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:240
LiveDebugValues
Definition: InstrRefBasedImpl.h:30
llvm::SSAUpdaterTraits< LDVSSAUpdater >::GetUndefVal
static BlockValueNum GetUndefVal(LDVSSABlock *BB, LDVSSAUpdater *Updater)
GetUndefVal - Normally creates an IMPLICIT_DEF instruction with a new register.
Definition: InstrRefBasedImpl.cpp:3519
LiveDebugValues::FuncValueTable
std::unique_ptr< ValueTable[]> FuncValueTable
Type for a table-of-table-of-values, i.e., the collection of either live-in or live-out values for ea...
Definition: InstrRefBasedImpl.h:176
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::SSAUpdaterTraits< LDVSSAUpdater >::ValueIsNewPHI
static LDVSSAPhi * ValueIsNewPHI(BlockValueNum Val, LDVSSAUpdater *Updater)
ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source operands, i....
Definition: InstrRefBasedImpl.cpp:3558
TransferTracker::emitMOLoc
MachineInstrBuilder emitMOLoc(const MachineOperand &MO, const DebugVariable &Var, const DbgValueProperties &Properties)
Definition: InstrRefBasedImpl.cpp:633
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::end
iterator end()
Definition: DenseSet.h:174
llvm::MachineOperand::isKill
bool isKill() const
Definition: MachineOperand.h:389
LiveDebugValues::MLocTracker::StackSlotPos
std::pair< unsigned short, unsigned short > StackSlotPos
Pair for describing a position within a stack slot – first the size in bits, then the offset.
Definition: InstrRefBasedImpl.h:402
LiveDebugValues::MLocTracker::Masks
SmallVector< std::pair< const MachineOperand *, unsigned >, 32 > Masks
Collection of register mask operands that have been observed.
Definition: InstrRefBasedImpl.h:398
TransferTracker::UseBeforeDef::Properties
DbgValueProperties Properties
Additional variable properties.
Definition: InstrRefBasedImpl.cpp:230
TargetLowering.h
TransferTracker::Transfer::Pos
MachineBasicBlock::instr_iterator Pos
Definition: InstrRefBasedImpl.cpp:189
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:666
llvm::PseudoSourceValue::kind
unsigned kind() const
Definition: PseudoSourceValue.h:66
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
TargetMachine.h
LiveDebugValues::MLocTracker::reset
void reset()
Wipe any un-necessary location records after traversing a block.
Definition: InstrRefBasedImpl.h:523
llvm::DILocalVariable
Local variable.
Definition: DebugInfoMetadata.h:3058
llvm::IndexedMap::size
StorageT::size_type size() const
Definition: IndexedMap.h:78
LiveDebugValues::MLocTracker::getNumLocs
unsigned getNumLocs() const
Definition: InstrRefBasedImpl.h:501
llvm::MachineBasicBlock::succ_end
succ_iterator succ_end()
Definition: MachineBasicBlock.h:344
TransferTracker::MF
MachineFunction & MF
Definition: InstrRefBasedImpl.cpp:182
llvm::SSAUpdaterTraits< LDVSSAUpdater >::PHI_iterator::getIncomingBlock
LDVSSABlock * getIncomingBlock()
Definition: InstrRefBasedImpl.cpp:3499
LiveDebugValues::MLocTracker::TLI
const TargetLowering & TLI
Definition: InstrRefBasedImpl.h:351
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:501
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
LiveDebugValues::MLocTracker::locIDToSpillIdx
StackSlotPos locIDToSpillIdx(unsigned ID) const
Returns the spill-slot size/offs that a location ID corresponds to.
Definition: InstrRefBasedImpl.h:494
llvm::TargetLowering
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Definition: TargetLowering.h:3412
llvm::MachineOperand::getRegMask
const uint32_t * getRegMask() const
getRegMask - Returns a bit mask of registers preserved by this RegMask operand.
Definition: MachineOperand.h:639
llvm::MCSubRegIndexIterator::isValid
bool isValid() const
Returns true if this iterator is not yet at the end.
Definition: MCRegisterInfo.h:633
LiveDebugValues::MLocTracker::LocIDToLocIdx
std::vector< LocIdx > LocIDToLocIdx
"Map" of machine location IDs (i.e., raw register or spill number) to the LocIdx key / number for tha...
Definition: InstrRefBasedImpl.h:368
SSAUpdaterImpl.h
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:45
TransferTracker::UseBeforeDef
Record of a use-before-def: created when a value that's live-in to the current block isn't available ...
Definition: InstrRefBasedImpl.cpp:224
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::SSAUpdaterTraits< LDVSSAUpdater >::CreateEmptyPHI
static BlockValueNum CreateEmptyPHI(LDVSSABlock *BB, unsigned NumPreds, LDVSSAUpdater *Updater)
CreateEmptyPHI - Create a (representation of a) PHI in the given block.
Definition: InstrRefBasedImpl.cpp:3533
LiveDebugValues::MLocTracker::emitLoc
MachineInstrBuilder emitLoc(Optional< LocIdx > MLoc, const DebugVariable &Var, const DbgValueProperties &Properties)
Create a DBG_VALUE based on machine location MLoc.
Definition: InstrRefBasedImpl.cpp:845
PseudoSourceValue.h
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::MCRegisterInfo::getSubRegIndex
unsigned getSubRegIndex(MCRegister RegNo, MCRegister SubRegNo) const
For a given register pair, return the sub-register index if the second register is a sub-register of ...
Definition: MCRegisterInfo.cpp:44
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
TransferTracker::UseBeforeDef::ID
ValueIDNum ID
Value of this variable, def'd in block.
Definition: InstrRefBasedImpl.cpp:226
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
LiveDebugValues::MLocTracker::MF
MachineFunction & MF
Definition: InstrRefBasedImpl.h:348
LiveDebugValues::MLocTracker::getSpillMLoc
LocIdx getSpillMLoc(unsigned SpillID)
Definition: InstrRefBasedImpl.h:628
LiveDebugValues::DbgValueProperties::Indirect
bool Indirect
Definition: InstrRefBasedImpl.h:221
MachineInstrBundle.h
LexicalScopes.h
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:619
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
LiveDebugValues::InstrRefBasedLDV::LiveInsT
SmallVector< SmallVector< VarAndLoc, 8 >, 8 > LiveInsT
Vector (per block) of a collection (inner smallvector) of live-ins.
Definition: InstrRefBasedImpl.h:804
llvm::MachineFunction::begin
iterator begin()
Definition: MachineFunction.h:853
llvm::DILocalVariable::isValidLocationForIntrinsic
bool isValidLocationForIntrinsic(const DILocation *DL) const
Check that a location is valid for this variable.
Definition: DebugInfoMetadata.h:3137
DebugLoc.h
llvm::LexicalScope::getDFSOut
unsigned getDFSOut() const
Definition: LexicalScopes.h:113
llvm::SPIRV::StorageClass::Output
@ Output
SmallPtrSet.h
LiveDebugValues::MLocTracker::getLocID
unsigned getLocID(Register Reg)
Produce location ID number for a Register.
Definition: InstrRefBasedImpl.h:451
llvm::BitVector
Definition: BitVector.h:75
LiveDebugValues::LocIdx::asU64
uint64_t asU64() const
Definition: InstrRefBasedImpl.h:63
llvm::SSAUpdaterTraits< LDVSSAUpdater >::AddPHIOperand
static void AddPHIOperand(LDVSSAPhi *PHI, BlockValueNum Val, LDVSSABlock *Pred)
AddPHIOperand - Add the specified value as an operand of the PHI for the specified predecessor block.
Definition: InstrRefBasedImpl.cpp:3543
llvm::PseudoSourceValue
Special value supplied for machine level alias analysis.
Definition: PseudoSourceValue.h:35
LiveDebugValues::ValueIDNum::getBlock
uint64_t getBlock() const
Definition: InstrRefBasedImpl.h:132
TransferTracker::UseBeforeDefVariables
DenseSet< DebugVariable > UseBeforeDefVariables
The set of variables that are in UseBeforeDefs and can become a location once the relevant value is d...
Definition: InstrRefBasedImpl.cpp:240
LiveDebugValues::ValueIDNum::getLoc
uint64_t getLoc() const
Definition: InstrRefBasedImpl.h:134
LiveDebugValues::MLocTracker::defReg
void defReg(Register R, unsigned BB, unsigned Inst)
Record a definition of the specified register at the given block / inst.
Definition: InstrRefBasedImpl.h:578
llvm::StringRef::str
LLVM_NODISCARD std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:249
llvm::None
const NoneType None
Definition: None.h:24
llvm::DebugVariable::getVariable
const DILocalVariable * getVariable() const
Definition: DebugInfoMetadata.h:3642
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
LiveDebugValues::DbgValue::Properties
DbgValueProperties Properties
Qualifiers for the ValueIDNum above.
Definition: InstrRefBasedImpl.h:241
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::MCRegUnitRootIterator::isValid
bool isValid() const
Check if the iterator is at the end of the list.
Definition: MCRegisterInfo.h:773
llvm::MachineFrameInfo::isDeadObjectIndex
bool isDeadObjectIndex(int ObjectIdx) const
Returns true if the specified index corresponds to a dead object.
Definition: MachineFrameInfo.h:737
LiveDebugValues::MLocTracker::LocIdxToLocID
IndexedMap< unsigned, LocIdxToIndexFunctor > LocIdxToLocID
Inverse map of LocIDToLocIdx.
Definition: InstrRefBasedImpl.h:371
foo
< i32 > tmp foo
Definition: README.txt:383
TransferTracker::Transfer
Record of all changes in variable locations at a block position.
Definition: InstrRefBasedImpl.cpp:188
llvm::Twine::str
std::string str() const
Return the twine contents as a std::string.
Definition: Twine.cpp:17
llvm::TargetRegisterInfo::regclasses
iterator_range< regclass_iterator > regclasses() const
Definition: TargetRegisterInfo.h:740
llvm::SSAUpdaterTraits< LDVSSAUpdater >::BlkSucc_begin
static BlkSucc_iterator BlkSucc_begin(BlkT *BB)
Definition: InstrRefBasedImpl.cpp:3475
LiveDebugValues::SpillLoc
Definition: InstrRefBasedImpl.h:80
llvm::DILocalVariable::getScope
DILocalScope * getScope() const
Get the local scope for this variable.
Definition: DebugInfoMetadata.h:3116
LiveDebugValues::MLocTracker::loadFromArray
void loadFromArray(ValueTable &Locs, unsigned NewCurBB)
Load values for each location from array of ValueIDNums.
Definition: InstrRefBasedImpl.h:514
llvm::TargetPassConfig
Target-Independent Code Generator Pass Configuration Options.
Definition: TargetPassConfig.h:84
llvm::SSAUpdaterTraits< LDVSSAUpdater >::PHI_iterator::PHI_iterator
PHI_iterator(LDVSSAPhi *P)
Definition: InstrRefBasedImpl.cpp:3485
LiveDebugValues::VLocTracker::MBB
MachineBasicBlock * MBB
Definition: InstrRefBasedImpl.h:701
llvm::DIExpression::isImplicit
bool isImplicit() const
Return whether this is an implicit location description.
Definition: DebugInfoMetadata.cpp:1331
llvm::DenseSet< DebugVariable >
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:656
LiveDebugValues::MLocTracker::lookupOrTrackRegister
LocIdx lookupOrTrackRegister(unsigned ID)
Definition: InstrRefBasedImpl.h:562
llvm::cl::opt< bool >
llvm::MachineOperand::clobbersPhysReg
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
Definition: MachineOperand.h:626
LiveDebugValues::DbgValue
Class recording the (high level) value of a variable.
Definition: InstrRefBasedImpl.h:229
LiveDebugValues::MLocTracker::dump_mloc_map
LLVM_DUMP_METHOD void dump_mloc_map()
Definition: InstrRefBasedImpl.cpp:837
llvm::AMDGPU::Hwreg::Offset
Offset
Definition: SIDefines.h:413
TransferTracker::clobberMloc
void clobberMloc(LocIdx MLoc, MachineBasicBlock::iterator Pos, bool MakeUndef=true)
Account for a location mloc being clobbered.
Definition: InstrRefBasedImpl.cpp:531
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:112
TransferTracker::loadInlocs
void loadInlocs(MachineBasicBlock &MBB, ValueTable &MLocs, const SmallVectorImpl< std::pair< DebugVariable, DbgValue >> &VLocs, unsigned NumLocs)
Load object with live-in variable values.
Definition: InstrRefBasedImpl.cpp:262
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:320
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::MachineInstrBuilder
Definition: MachineInstrBuilder.h:69
uint64_t
GenericIteratedDominanceFrontier.h
llvm::SmallPtrSetImpl::end
iterator end() const
Definition: SmallPtrSet.h:408
LiveDebugValues::InstrRefBasedLDV::ScopeToAssignBlocksT
DenseMap< const LexicalScope *, SmallPtrSet< MachineBasicBlock *, 4 > > ScopeToAssignBlocksT
Mapping from lexical scopes to blocks where variables in that scope are assigned.
Definition: InstrRefBasedImpl.h:815
LiveDebugValues::InstrRefBasedLDV::isCalleeSaved
bool isCalleeSaved(LocIdx L) const
Definition: InstrRefBasedImpl.cpp:964
s
multiplies can be turned into SHL s
Definition: README.txt:370
llvm::SSAUpdaterTraits< LDVSSAUpdater >::PHI_begin
static PHI_iterator PHI_begin(PhiT *PHI)
Definition: InstrRefBasedImpl.cpp:3502
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::TargetRegisterInfo::getFrameRegister
virtual Register getFrameRegister(const MachineFunction &MF) const =0
Debug information queries.
TransferTracker::TII
const TargetInstrInfo * TII
Definition: InstrRefBasedImpl.cpp:176
llvm::DenseMap
Definition: DenseMap.h:716
I
#define I(x, y, z)
Definition: MD5.cpp:58
TransferTracker::TransferTracker
TransferTracker(const TargetInstrInfo *TII, MLocTracker *MTracker, MachineFunction &MF, const TargetRegisterInfo &TRI, const BitVector &CalleeSavedRegs, const TargetPassConfig &TPC)
Definition: InstrRefBasedImpl.cpp:245
llvm::succ_begin
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
TransferTracker::ActiveMLocs
DenseMap< LocIdx, SmallSet< DebugVariable, 4 > > ActiveMLocs
Map from LocIdxes to which DebugVariables are based that location.
Definition: InstrRefBasedImpl.cpp:211
llvm::detail::DenseSetImpl::empty
bool empty() const
Definition: DenseSet.h:80
TransferTracker::VarLocs
SmallVector< ValueIDNum, 32 > VarLocs
Local cache of what-value-is-in-what-LocIdx.
Definition: InstrRefBasedImpl.cpp:206
LiveDebugValues::LocIdx::isIllegal
bool isIllegal() const
Definition: InstrRefBasedImpl.h:61
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
TransferTracker::ShouldEmitDebugEntryValues
bool ShouldEmitDebugEntryValues
Definition: InstrRefBasedImpl.cpp:183
MCRegisterInfo.h
llvm::DebugVariable
Identifies a unique instance of a variable.
Definition: DebugInfoMetadata.h:3620
size
i< reg-> size
Definition: README.txt:166
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:403
llvm::concat
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&... Ranges)
Concatenated range across two or more ranges.
Definition: STLExtras.h:1085
LiveDebugValues::DbgValue::NoVal
@ NoVal
Definition: InstrRefBasedImpl.h:249
LiveDebugValues::DbgValue::dump
void dump(const MLocTracker *MTrack) const
Definition: InstrRefBasedImpl.cpp:659
llvm::BitVector::flip
BitVector & flip()
Definition: BitVector.h:424
llvm::TargetInstrInfo::isStoreToStackSlotPostFE
virtual unsigned isStoreToStackSlotPostFE(const MachineInstr &MI, int &FrameIndex) const
Check for post-frame ptr elimination stack locations as well.
Definition: TargetInstrInfo.h:318
TargetPassConfig.h
llvm::MachineBasicBlock::pred_iterator
std::vector< MachineBasicBlock * >::iterator pred_iterator
Definition: MachineBasicBlock.h:314
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::begin
iterator begin()
Definition: DenseSet.h:173
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:152
LiveDebugValues::VLocTracker
Collection of DBG_VALUEs observed when traversing a block.
Definition: InstrRefBasedImpl.h:689
LiveDebugValues::MLocTracker::StackIdxesToPos
DenseMap< unsigned, StackSlotPos > StackIdxesToPos
Inverse of StackSlotIdxes.
Definition: InstrRefBasedImpl.h:410
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SSAUpdaterTraits< LDVSSAUpdater >::BlkSucc_end
static BlkSucc_iterator BlkSucc_end(BlkT *BB)
Definition: InstrRefBasedImpl.cpp:3476
llvm::TargetMachine
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:77
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::MachineFunction::getFrameInfo
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
Definition: MachineFunction.h:672
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:234
llvm::TargetInstrInfo::isLoadFromStackSlotPostFE
virtual unsigned isLoadFromStackSlotPostFE(const MachineInstr &MI, int &FrameIndex) const
Check for post-frame ptr elimination stack locations as well.
Definition: TargetInstrInfo.h:280
llvm::SmallSet::begin
const_iterator begin() const
Definition: SmallSet.h:225
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1990
llvm::MachineOperand::isRegMask
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
Definition: MachineOperand.h:344
LiveDebugValues::InstrRefBasedLDV::hasFoldedStackStore
bool hasFoldedStackStore(const MachineInstr &MI)
Definition: InstrRefBasedImpl.h:1142
LiveDebugValues::SpillLocationNo::id
unsigned id() const
Definition: InstrRefBasedImpl.h:184
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:359
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:359
llvm::makeInstrRefBasedLiveDebugValues
LDVImpl * makeInstrRefBasedLiveDebugValues()
Definition: InstrRefBasedImpl.cpp:3315
llvm::MachineBasicBlock::instr_begin
instr_iterator instr_begin()
Definition: MachineBasicBlock.h:262
LiveDebugValues::MLocTracker
Tracker for what values are in machine locations.
Definition: InstrRefBasedImpl.h:346
LiveDebugValues::InstrRefBasedLDV::FragmentInfo
DIExpression::FragmentInfo FragmentInfo
Definition: InstrRefBasedImpl.h:781
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::detail::DenseSetImpl::clear
void clear()
Definition: DenseSet.h:92
llvm::SSAUpdaterTraits< LDVSSAUpdater >::PHI_iterator::operator==
bool operator==(const PHI_iterator &X) const
Definition: InstrRefBasedImpl.cpp:3494
LiveDebugValues::MLocTracker::SpillLocs
UniqueVector< SpillLoc > SpillLocs
Unique-ification of spill.
Definition: InstrRefBasedImpl.h:380
LiveDebugValues::SpillLoc::SpillOffset
StackOffset SpillOffset
Definition: InstrRefBasedImpl.h:82
LiveDebugValues::LocIdx
Handle-class for a particular "location".
Definition: InstrRefBasedImpl.h:41
llvm::IndexedMap::grow
void grow(IndexT n)
Definition: IndexedMap.h:68
LiveDebugValues::ValueIDNum::getInst
uint64_t getInst() const
Definition: InstrRefBasedImpl.h:133
llvm::operator*
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2114
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:95
LiveDebugValues::ValueIDNum::fromU64
static ValueIDNum fromU64(uint64_t v)
Definition: InstrRefBasedImpl.h:139
LiveDebugValues::InstrRefBasedLDV::dump_mloc_transfer
LLVM_DUMP_METHOD void dump_mloc_transfer(const MLocTransferMap &mloc_transfer) const
Definition: InstrRefBasedImpl.cpp:2879
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1088
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
LiveDebugValues::InstrRefBasedLDV::findLocationForMemOperand
Optional< LocIdx > findLocationForMemOperand(const MachineInstr &MI)
Definition: InstrRefBasedImpl.cpp:997
LiveDebugValues::VLocTracker::defVar
void defVar(const MachineInstr &MI, const DbgValueProperties &Properties, Optional< ValueIDNum > ID)
Definition: InstrRefBasedImpl.h:709
TransferTracker::ActiveVLocs
DenseMap< DebugVariable, LocAndProperties > ActiveVLocs
Map from DebugVariable to it's current location and qualifying meta information.
Definition: InstrRefBasedImpl.cpp:216
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:365
Dwarf.h
TransferTracker::LocAndProperties::Properties
DbgValueProperties Properties
Definition: InstrRefBasedImpl.cpp:196
LiveDebugValues::MLocTracker::SPAliases
SmallSet< Register, 8 > SPAliases
When clobbering register masks, we chose to not believe the machine model and don't clobber SP.
Definition: InstrRefBasedImpl.h:376
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:845
uint32_t
llvm::StackOffset
StackOffset is a class to represent an offset with 2 dimensions, named fixed and scalable,...
Definition: TypeSize.h:134
Compiler.h
llvm::getBundleStart
MachineBasicBlock::instr_iterator getBundleStart(MachineBasicBlock::instr_iterator I)
Returns an iterator to the first instruction in the bundle containing I.
Definition: MachineInstrBundle.h:44
TargetSubtargetInfo.h
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::TargetPassConfig::getTM
TMC & getTM() const
Get the right type of TargetMachine for this target.
Definition: TargetPassConfig.h:151
InstrRefBasedImpl.h
LiveDebugValues::MLocTracker::locIDToSpill
SpillLocationNo locIDToSpill(unsigned ID) const
Return the spill number that a location ID corresponds to.
Definition: InstrRefBasedImpl.h:485
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:374
LiveDebugValues::MLocTracker::getLocSizeInBits
unsigned getLocSizeInBits(LocIdx L) const
How large is this location (aka, how wide is a value defined there?).
Definition: InstrRefBasedImpl.h:637
LiveDebugValues::DbgValueProperties
Meta qualifiers for a value.
Definition: InstrRefBasedImpl.h:200
llvm::SmallSet::insert
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:182
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:288
llvm::Pass::dump
void dump() const
Definition: Pass.cpp:135
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:209
llvm::SSAUpdaterTraits< LDVSSAUpdater >::BlkSucc_iterator
LDVSSABlockIterator BlkSucc_iterator
Definition: InstrRefBasedImpl.cpp:3472
LiveDebugValues::MLocTracker::getSpillIDWithIdx
unsigned getSpillIDWithIdx(SpillLocationNo Spill, unsigned Idx)
Given a spill number, and a slot within the spill, calculate the ID number for that location.
Definition: InstrRefBasedImpl.h:476
LiveDebugValues::LocIdx::MakeIllegalLoc
static LocIdx MakeIllegalLoc()
Definition: InstrRefBasedImpl.h:54
TransferTracker::TLI
const TargetLowering * TLI
Definition: InstrRefBasedImpl.cpp:177
TransferTracker::LocAndProperties::Loc
LocIdx Loc
Definition: InstrRefBasedImpl.cpp:195
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:93
LiveDebugValues::DbgValue::Kind
KindT Kind
Discriminator for whether this is a constant or an in-program value.
Definition: InstrRefBasedImpl.h:253
EmulateOldLDV
static cl::opt< bool > EmulateOldLDV("emulate-old-livedebugvalues", cl::Hidden, cl::desc("Act like old LiveDebugValues did"), cl::init(false))
llvm::SSAUpdaterTraits< LDVSSAUpdater >::PHI_iterator::operator++
PHI_iterator & operator++()
Definition: InstrRefBasedImpl.cpp:3490
StackWorkingSetLimit
static cl::opt< unsigned > StackWorkingSetLimit("livedebugvalues-max-stack-slots", cl::Hidden, cl::desc("livedebugvalues-stack-ws-limit"), cl::init(250))
llvm::MachineFunction::DebugSubstitution
Replacement definition for a debug instruction reference.
Definition: MachineFunction.h:484
llvm::SSAUpdaterTraits< LDVSSAUpdater >::PHI_end
static PHI_iterator PHI_end(PhiT *PHI)
Definition: InstrRefBasedImpl.cpp:3504
llvm::MDNode::getContext
LLVMContext & getContext() const
Definition: Metadata.h:1031
llvm::DIExpression::getFragmentInfo
static Optional< FragmentInfo > getFragmentInfo(expr_op_iterator Start, expr_op_iterator End)
Retrieve the details of this fragment expression.
Definition: DebugInfoMetadata.cpp:1374
TransferTracker::TRI
const TargetRegisterInfo & TRI
Definition: InstrRefBasedImpl.cpp:242
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
LiveDebugValues::MLocTracker::StackSlotIdxes
DenseMap< StackSlotPos, unsigned > StackSlotIdxes
Map from a size/offset pair describing a position in a stack slot, to a numeric identifier for that p...
Definition: InstrRefBasedImpl.h:407
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
LiveDebugValues::VLocTracker::Vars
MapVector< DebugVariable, DbgValue > Vars
Map DebugVariable to the latest Value it's defined to have.
Definition: InstrRefBasedImpl.h:699
llvm::BitVector::test
bool test(unsigned Idx) const
Definition: BitVector.h:454
LiveDebugValues::MLocTracker::readReg
ValueIDNum readReg(Register R)
Definition: InstrRefBasedImpl.h:593
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:622
llvm::TargetSubtargetInfo::getFrameLowering
virtual const TargetFrameLowering * getFrameLowering() const
Definition: TargetSubtargetInfo.h:94
LiveDebugValues::InstrRefBasedLDV
Definition: InstrRefBasedImpl.h:777
llvm::TargetRegisterInfo::getRegSizeInBits
unsigned getRegSizeInBits(const TargetRegisterClass &RC) const
Return the size in bits of a register from class RC.
Definition: TargetRegisterInfo.h:277
TransferTracker::redefVar
void redefVar(const MachineInstr &MI, const DbgValueProperties &Properties, Optional< LocIdx > OptNewLoc)
Handle a change in variable location within a block.
Definition: InstrRefBasedImpl.cpp:489
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:84
LiveDebugValues::InstrRefBasedLDV::ScopeToDILocT
DenseMap< const LexicalScope *, const DILocation * > ScopeToDILocT
Mapping from lexical scopes to a DILocation in that scope.
Definition: InstrRefBasedImpl.h:807
LiveDebugValues::SpillLocationNo
Thin wrapper around an integer – designed to give more type safety to spill location numbers.
Definition: InstrRefBasedImpl.h:180
llvm::X86::FirstMacroFusionInstKind::Cmp
@ Cmp
llvm::MachineBasicBlock::insert
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
Definition: MachineBasicBlock.cpp:1312
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
MachineFrameInfo.h
llvm::TargetFrameLowering::getFrameIndexReference
virtual StackOffset getFrameIndexReference(const MachineFunction &MF, int FI, Register &FrameReg) const
getFrameIndexReference - This method should return the base register and offset used to reference a f...
Definition: TargetFrameLoweringImpl.cpp:50
llvm::MachineOperand::getIndex
int getIndex() const
Definition: MachineOperand.h:566
TransferTracker::checkInstForNewValues
void checkInstForNewValues(unsigned Inst, MachineBasicBlock::iterator pos)
After the instruction at index Inst and position pos has been processed, check whether it defines a v...
Definition: InstrRefBasedImpl.cpp:365
LiveDebugValues::MLocTracker::getRegMLoc
LocIdx getRegMLoc(Register R)
Determine the LocIdx of an existing register.
Definition: InstrRefBasedImpl.h:610
llvm::MachineBasicBlock::instr_iterator
Instructions::iterator instr_iterator
Definition: MachineBasicBlock.h:237
llvm::LexicalScopes::findLexicalScope
LexicalScope * findLexicalScope(const DILocation *DL)
findLexicalScope - Find lexical scope, either regular or inlined, for the given DebugLoc.
Definition: LexicalScopes.cpp:124
InputBBLimit
static cl::opt< unsigned > InputBBLimit("livedebugvalues-input-bb-limit", cl::desc("Maximum input basic blocks before DBG_VALUE limit applies"), cl::init(10000), cl::Hidden)
Casting.h
llvm::DIExpression::isComplex
bool isComplex() const
Return whether the location is computed on the expression stack, meaning it cannot be a simple regist...
Definition: DebugInfoMetadata.cpp:1351
Function.h
llvm::DenseMapBase::size
unsigned size() const
Definition: DenseMap.h:101
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1562
TransferTracker::LocAndProperties
Definition: InstrRefBasedImpl.cpp:194
llvm::IDFCalculatorBase
Determine the iterated dominance frontier, given a set of defining blocks, and optionally,...
Definition: GenericIteratedDominanceFrontier.h:57
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
LiveDebugValues::MLocTracker::LocIdxToIDNum
LocToValueType LocIdxToIDNum
Map of LocIdxes to the ValueIDNums that they store.
Definition: InstrRefBasedImpl.h:358
llvm::SSAUpdaterTraits< LDVSSAUpdater >::PHI_iterator::getIncomingValue
BlockValueNum getIncomingValue()
Definition: InstrRefBasedImpl.cpp:3497
LiveDebugValues.h
LiveDebugValues::MLocTracker::isSpill
bool isSpill(LocIdx Idx) const
Return true if Idx is a spill machine location.
Definition: InstrRefBasedImpl.h:634
LiveDebugValues::ValueTable
std::unique_ptr< ValueIDNum[]> ValueTable
Type for a table of values in a block.
Definition: InstrRefBasedImpl.h:172
llvm::SmallSet::end
const_iterator end() const
Definition: SmallSet.h:231
LiveDebugValues::ValueIDNum::asString
std::string asString(const std::string &mlocname) const
Definition: InstrRefBasedImpl.h:155
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:291
llvm::SSAUpdaterTraits
Definition: MachineSSAUpdater.h:28
LiveDebugValues::DbgValue::MO
Optional< MachineOperand > MO
If Kind is Const, the MachineOperand defining this value.
Definition: InstrRefBasedImpl.h:236
TransferTracker::MTracker
MLocTracker * MTracker
This machine location tracker is assumed to always contain the up-to-date value mapping for all machi...
Definition: InstrRefBasedImpl.cpp:181
LiveDebugValues::SpillLoc::SpillBase
unsigned SpillBase
Definition: InstrRefBasedImpl.h:81
llvm::MCSubRegIterator
MCSubRegIterator enumerates all sub-registers of Reg.
Definition: MCRegisterInfo.h:597
LiveDebugValues::MLocTracker::setMPhis
void setMPhis(unsigned NewCurBB)
Reset all locations to contain a PHI value at the designated block.
Definition: InstrRefBasedImpl.h:506
llvm::MCRegUnitIterator
Definition: MCRegisterInfo.h:680
llvm::MCRegUnitRootIterator
MCRegUnitRootIterator enumerates the root registers of a register unit.
Definition: MCRegisterInfo.h:754
LiveDebugValues::MLocTracker::dump
LLVM_DUMP_METHOD void dump()
Definition: InstrRefBasedImpl.cpp:829
llvm::MCRegAliasIterator::isValid
bool isValid() const
Definition: MCRegisterInfo.h:813
PostOrderIterator.h
llvm::TargetSubtargetInfo::getTargetLowering
virtual const TargetLowering * getTargetLowering() const
Definition: TargetSubtargetInfo.h:97
SmallVector.h
llvm::MachineDominatorTree::getBase
MachineDomTree & getBase()
Definition: MachineDominators.h:91
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:278
MachineInstrBuilder.h
LiveDebugValues::DbgValue::Undef
@ Undef
Definition: InstrRefBasedImpl.h:244
TransferTracker::CalleeSavedRegs
const BitVector & CalleeSavedRegs
Definition: InstrRefBasedImpl.cpp:243
llvm::SPIRV::Decoration::Location
@ Location
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:328
llvm::SmallPtrSetImplBase::empty
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:92
llvm::MCRegisterInfo::DiffListIterator::isValid
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Definition: MCRegisterInfo.h:224
llvm::MachineFunction::DebugValueSubstitutions
SmallVector< DebugSubstitution, 8 > DebugValueSubstitutions
Debug value substitutions: a collection of DebugSubstitution objects, recording changes in where a va...
Definition: MachineFunction.h:505
llvm::MachineInstr::getNumOperands
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:494
llvm::SSAUpdaterTraits< LDVSSAUpdater >::FindPredecessorBlocks
static void FindPredecessorBlocks(LDVSSABlock *BB, SmallVectorImpl< LDVSSABlock * > *Preds)
FindPredecessorBlocks - Put the predecessors of BB into the Preds vector.
Definition: InstrRefBasedImpl.cpp:3510
LiveDebugValues::ValueIDNum::EmptyValue
static ValueIDNum EmptyValue
Definition: InstrRefBasedImpl.h:167
llvm::tgtok::Bit
@ Bit
Definition: TGLexer.h:50
llvm::MachineBasicBlock::const_succ_iterator
std::vector< MachineBasicBlock * >::const_iterator const_succ_iterator
Definition: MachineBasicBlock.h:317
llvm::LexicalScopes::getCurrentFunctionScope
LexicalScope * getCurrentFunctionScope() const
getCurrentFunctionScope - Return lexical scope for the current function.
Definition: LexicalScopes.h:156
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::reserve
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
Definition: DenseMap.h:105
llvm::detail::DenseSetImpl::erase
bool erase(const ValueT &V)
Definition: DenseSet.h:101
llvm::DIExpression::getNumElements
unsigned getNumElements() const
Definition: DebugInfoMetadata.h:2584
llvm::StringRef::data
const LLVM_NODISCARD char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:149
llvm::MCRegisterInfo::getSubRegIdxOffset
unsigned getSubRegIdxOffset(unsigned Idx) const
Get the offset of the bit range covered by a sub-register index.
Definition: MCRegisterInfo.cpp:62
MachineMemOperand.h
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
MachineOperand.h
llvm::TargetRegisterInfo::getSubReg
MCRegister getSubReg(MCRegister Reg, unsigned Idx) const
Returns the physical register number of sub-register "Index" for physical register RegNo.
Definition: TargetRegisterInfo.h:1113
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
TM
const char LLVMTargetMachineRef TM
Definition: PassBuilderBindings.cpp:47
LiveDebugValues::ValueIDNum::TombstoneValue
static ValueIDNum TombstoneValue
Definition: InstrRefBasedImpl.h:168
TransferTracker::Transfer::Insts
SmallVector< MachineInstr *, 4 > Insts
non-null if we should insert after.
Definition: InstrRefBasedImpl.cpp:191
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
LiveDebugValues::MLocTracker::LocIdxToName
std::string LocIdxToName(LocIdx Idx) const
Definition: InstrRefBasedImpl.cpp:808
llvm::MCInstrInfo::get
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
Definition: MCInstrInfo.h:63
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::MachineFrameInfo::adjustsStack
bool adjustsStack() const
Return true if this function adjusts the stack – e.g., when calling another function.
Definition: MachineFrameInfo.h:601
LiveDebugValues::MLocTracker::isRegisterTracked
bool isRegisterTracked(Register R)
Is register R currently tracked by MLocTracker?
Definition: InstrRefBasedImpl.h:570
llvm::cl::desc
Definition: CommandLine.h:405
raw_ostream.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:51
MachineFunction.h
llvm::SmallPtrSetImpl::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:644
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::pdb::PDB_SymType::Block
@ Block
LiveDebugValues::DbgValue::Const
@ Const
Definition: InstrRefBasedImpl.h:246
LiveDebugValues::MLocTracker::readMLoc
ValueIDNum readMLoc(LocIdx L)
Read the value of a particular location.
Definition: InstrRefBasedImpl.h:553
llvm::SSAUpdaterTraits< LDVSSAUpdater >::BlkT
LDVSSABlock BlkT
Definition: InstrRefBasedImpl.cpp:3469
LiveDebugValues::DbgValue::BlockNo
int BlockNo
For a NoVal or VPHI DbgValue, which block it was generated in.
Definition: InstrRefBasedImpl.h:238
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
TargetRegisterInfo.h
Debug.h
llvm::DIExpression::EntryValue
@ EntryValue
Definition: DebugInfoMetadata.h:2767
LiveDebugValues::DbgValue::Def
@ Def
Definition: InstrRefBasedImpl.h:245
llvm::SSAUpdaterTraits< LDVSSAUpdater >::ValueIsPHI
static LDVSSAPhi * ValueIsPHI(BlockValueNum Val, LDVSSAUpdater *Updater)
ValueIsPHI - Check if the instruction that defines the specified value is a PHI instruction.
Definition: InstrRefBasedImpl.cpp:3549
llvm::LexicalScope::getChildren
SmallVectorImpl< LexicalScope * > & getChildren()
Definition: LexicalScopes.h:65
llvm::TargetRegisterInfo::prependOffsetExpression
DIExpression * prependOffsetExpression(const DIExpression *Expr, unsigned PrependFlags, const StackOffset &Offset) const
Prepends a DWARF expression for Offset to DIExpression Expr.
Definition: TargetRegisterInfo.cpp:650
llvm::MCRegAliasIterator
MCRegAliasIterator enumerates all registers aliasing Reg.
Definition: MCRegisterInfo.h:788
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
TransferTracker::addUseBeforeDef
void addUseBeforeDef(const DebugVariable &Var, const DbgValueProperties &Properties, ValueIDNum ID)
Record that Var has value ID, a value that becomes available later in the function.
Definition: InstrRefBasedImpl.cpp:354
TransferTracker::isEntryValueValue
bool isEntryValueValue(const ValueIDNum &Val) const
Definition: InstrRefBasedImpl.cpp:420
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
MachineDominators.h
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:927
LiveDebugValues::MLocTracker::NumSlotIdxes
unsigned NumSlotIdxes
Number of slot indexes the target has – distinct segments of a stack slot that can take on the value ...
Definition: InstrRefBasedImpl.h:392
LiveDebugValues::MLocTracker::IDAsString
std::string IDAsString(const ValueIDNum &Num) const
Definition: InstrRefBasedImpl.cpp:823
SmallSet.h
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
LiveDebugValues::MLocTracker::CurBB
unsigned CurBB
Definition: InstrRefBasedImpl.h:384
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::DebugVariable::getInlinedAt
const DILocation * getInlinedAt() const
Definition: DebugInfoMetadata.h:3644
llvm::Twine::concat
Twine concat(const Twine &Suffix) const
Definition: Twine.h:510
llvm::MCRegisterInfo::getSubRegIdxSize
unsigned getSubRegIdxSize(unsigned Idx) const
Get the size of the bit range covered by a sub-register index.
Definition: MCRegisterInfo.cpp:56
LiveDebugValues::DbgValue::VPHI
@ VPHI
Definition: InstrRefBasedImpl.h:247
llvm::SSAUpdaterImpl
Definition: SSAUpdaterImpl.h:30