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