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