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