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 much like SSA
15 /// construction, where each DBG_VALUE instruction assigns the *value* that
16 /// a variable has, and every instruction where the variable is in scope uses
17 /// that variable. The resulting map of instruction-to-value is then translated
18 /// into a register (or spill) location for each variable over each instruction.
19 ///
20 /// This pass determines which DBG_VALUE dominates which instructions, or if
21 /// none do, where values must be merged (like PHI nodes). The added
22 /// complication is that because codegen has already finished, a PHI node may
23 /// be needed for a variable location to be correct, but no register or spill
24 /// slot merges the necessary values. In these circumstances, the variable
25 /// location is dropped.
26 ///
27 /// What makes this analysis non-trivial is loops: we cannot tell in advance
28 /// whether a variable location is live throughout a loop, or whether its
29 /// location is clobbered (or redefined by another DBG_VALUE), without
30 /// exploring all the way through.
31 ///
32 /// To make this simpler we perform two kinds of analysis. First, we identify
33 /// every value defined by every instruction (ignoring those that only move
34 /// another value), then compute a map of which values are available for each
35 /// instruction. This is stronger than a reaching-def analysis, as we create
36 /// PHI values where other values merge.
37 ///
38 /// Secondly, for each variable, we effectively re-construct SSA using each
39 /// DBG_VALUE as a def. The DBG_VALUEs read a value-number computed by the
40 /// first analysis from the location they refer to. We can then compute the
41 /// dominance frontiers of where a variable has a value, and create PHI nodes
42 /// where they merge.
43 /// This isn't precisely SSA-construction though, because the function shape
44 /// is pre-defined. If a variable location requires a PHI node, but no
45 /// PHI for the relevant values is present in the function (as computed by the
46 /// first analysis), the location must be dropped.
47 ///
48 /// Once both are complete, we can pass back over all instructions knowing:
49 /// * What _value_ each variable should contain, either defined by an
50 /// instruction or where control flow merges
51 /// * What the location of that value is (if any).
52 /// Allowing us to create appropriate live-in DBG_VALUEs, and DBG_VALUEs when
53 /// a value moves location. After this pass runs, all variable locations within
54 /// a block should be specified by DBG_VALUEs within that block, allowing
55 /// DbgEntityHistoryCalculator to focus on individual blocks.
56 ///
57 /// This pass is able to go fast because the size of the first
58 /// reaching-definition analysis is proportional to the working-set size of
59 /// the function, which the compiler tries to keep small. (It's also
60 /// proportional to the number of blocks). Additionally, we repeatedly perform
61 /// the second reaching-definition analysis with only the variables and blocks
62 /// in a single lexical scope, exploiting their locality.
63 ///
64 /// Determining where PHIs happen is trickier with this approach, and it comes
65 /// to a head in the major problem for LiveDebugValues: is a value live-through
66 /// a loop, or not? Your garden-variety dataflow analysis aims to build a set of
67 /// facts about a function, however this analysis needs to generate new value
68 /// numbers at joins.
69 ///
70 /// To do this, consider a lattice of all definition values, from instructions
71 /// and from PHIs. Each PHI is characterised by the RPO number of the block it
72 /// occurs in. Each value pair A, B can be ordered by RPO(A) < RPO(B):
73 /// with non-PHI values at the top, and any PHI value in the last block (by RPO
74 /// order) at the bottom.
75 ///
76 /// (Awkwardly: lower-down-the _lattice_ means a greater RPO _number_. Below,
77 /// "rank" always refers to the former).
78 ///
79 /// At any join, for each register, we consider:
80 /// * All incoming values, and
81 /// * The PREVIOUS live-in value at this join.
82 /// If all incoming values agree: that's the live-in value. If they do not, the
83 /// incoming values are ranked according to the partial order, and the NEXT
84 /// LOWEST rank after the PREVIOUS live-in value is picked (multiple values of
85 /// the same rank are ignored as conflicting). If there are no candidate values,
86 /// or if the rank of the live-in would be lower than the rank of the current
87 /// blocks PHIs, create a new PHI value.
88 ///
89 /// Intuitively: if it's not immediately obvious what value a join should result
90 /// in, we iteratively descend from instruction-definitions down through PHI
91 /// values, getting closer to the current block each time. If the current block
92 /// is a loop head, this ordering is effectively searching outer levels of
93 /// loops, to find a value that's live-through the current loop.
94 ///
95 /// If there is no value that's live-through this loop, a PHI is created for
96 /// this location instead. We can't use a lower-ranked PHI because by definition
97 /// it doesn't dominate the current block. We can't create a PHI value any
98 /// earlier, because we risk creating a PHI value at a location where values do
99 /// not in fact merge, thus misrepresenting the truth, and not making the true
100 /// live-through value for variable locations.
101 ///
102 /// This algorithm applies to both calculating the availability of values in
103 /// the first analysis, and the location of variables in the second. However
104 /// for the second we add an extra dimension of pain: creating a variable
105 /// location PHI is only valid if, for each incoming edge,
106 /// * There is a value for the variable on the incoming edge, and
107 /// * All the edges have that value in the same register.
108 /// Or put another way: we can only create a variable-location PHI if there is
109 /// a matching machine-location PHI, each input to which is the variables value
110 /// in the predecessor block.
111 ///
112 /// To accommodate this difference, each point on the lattice is split in
113 /// two: a "proposed" PHI and "definite" PHI. Any PHI that can immediately
114 /// have a location determined are "definite" PHIs, and no further work is
115 /// needed. Otherwise, a location that all non-backedge predecessors agree
116 /// on is picked and propagated as a "proposed" PHI value. If that PHI value
117 /// is truly live-through, it'll appear on the loop backedges on the next
118 /// dataflow iteration, after which the block live-in moves to be a "definite"
119 /// PHI. If it's not truly live-through, the variable value will be downgraded
120 /// further as we explore the lattice, or remains "proposed" and is considered
121 /// invalid once dataflow completes.
122 ///
123 /// ### Terminology
124 ///
125 /// A machine location is a register or spill slot, a value is something that's
126 /// defined by an instruction or PHI node, while a variable value is the value
127 /// assigned to a variable. A variable location is a machine location, that must
128 /// contain the appropriate variable value. A value that is a PHI node is
129 /// occasionally called an mphi.
130 ///
131 /// The first dataflow problem is the "machine value location" problem,
132 /// because we're determining which machine locations contain which values.
133 /// The "locations" are constant: what's unknown is what value they contain.
134 ///
135 /// The second dataflow problem (the one for variables) is the "variable value
136 /// problem", because it's determining what values a variable has, rather than
137 /// what location those values are placed in. Unfortunately, it's not that
138 /// simple, because producing a PHI value always involves picking a location.
139 /// This is an imperfection that we just have to accept, at least for now.
140 ///
141 /// TODO:
142 /// Overlapping fragments
143 /// Entry values
144 /// Add back DEBUG statements for debugging this
145 /// Collect statistics
146 ///
147 //===----------------------------------------------------------------------===//
148 
149 #include "llvm/ADT/DenseMap.h"
151 #include "llvm/ADT/STLExtras.h"
152 #include "llvm/ADT/SmallPtrSet.h"
153 #include "llvm/ADT/SmallSet.h"
154 #include "llvm/ADT/SmallVector.h"
155 #include "llvm/ADT/Statistic.h"
156 #include "llvm/ADT/UniqueVector.h"
175 #include "llvm/Config/llvm-config.h"
176 #include "llvm/IR/DIBuilder.h"
178 #include "llvm/IR/DebugLoc.h"
179 #include "llvm/IR/Function.h"
180 #include "llvm/IR/Module.h"
181 #include "llvm/InitializePasses.h"
182 #include "llvm/MC/MCRegisterInfo.h"
183 #include "llvm/Pass.h"
184 #include "llvm/Support/Casting.h"
185 #include "llvm/Support/Compiler.h"
186 #include "llvm/Support/Debug.h"
187 #include "llvm/Support/TypeSize.h"
191 #include <algorithm>
192 #include <cassert>
193 #include <cstdint>
194 #include <functional>
195 #include <queue>
196 #include <tuple>
197 #include <utility>
198 #include <vector>
199 #include <limits.h>
200 #include <limits>
201 
202 #include "LiveDebugValues.h"
203 
204 using namespace llvm;
205 
206 // SSAUpdaterImple sets DEBUG_TYPE, change it.
207 #undef DEBUG_TYPE
208 #define DEBUG_TYPE "livedebugvalues"
209 
210 // Act more like the VarLoc implementation, by propagating some locations too
211 // far and ignoring some transfers.
212 static cl::opt<bool> EmulateOldLDV("emulate-old-livedebugvalues", cl::Hidden,
213  cl::desc("Act like old LiveDebugValues did"),
214  cl::init(false));
215 
216 namespace {
217 
218 // The location at which a spilled value resides. It consists of a register and
219 // an offset.
220 struct SpillLoc {
221  unsigned SpillBase;
222  StackOffset SpillOffset;
223  bool operator==(const SpillLoc &Other) const {
224  return std::make_pair(SpillBase, SpillOffset) ==
225  std::make_pair(Other.SpillBase, Other.SpillOffset);
226  }
227  bool operator<(const SpillLoc &Other) const {
228  return std::make_tuple(SpillBase, SpillOffset.getFixed(),
229  SpillOffset.getScalable()) <
230  std::make_tuple(Other.SpillBase, Other.SpillOffset.getFixed(),
231  Other.SpillOffset.getScalable());
232  }
233 };
234 
235 class LocIdx {
236  unsigned Location;
237 
238  // Default constructor is private, initializing to an illegal location number.
239  // Use only for "not an entry" elements in IndexedMaps.
240  LocIdx() : Location(UINT_MAX) { }
241 
242 public:
243  #define NUM_LOC_BITS 24
244  LocIdx(unsigned L) : Location(L) {
245  assert(L < (1 << NUM_LOC_BITS) && "Machine locations must fit in 24 bits");
246  }
247 
248  static LocIdx MakeIllegalLoc() {
249  return LocIdx();
250  }
251 
252  bool isIllegal() const {
253  return Location == UINT_MAX;
254  }
255 
256  uint64_t asU64() const {
257  return Location;
258  }
259 
260  bool operator==(unsigned L) const {
261  return Location == L;
262  }
263 
264  bool operator==(const LocIdx &L) const {
265  return Location == L.Location;
266  }
267 
268  bool operator!=(unsigned L) const {
269  return !(*this == L);
270  }
271 
272  bool operator!=(const LocIdx &L) const {
273  return !(*this == L);
274  }
275 
276  bool operator<(const LocIdx &Other) const {
277  return Location < Other.Location;
278  }
279 };
280 
281 class LocIdxToIndexFunctor {
282 public:
283  using argument_type = LocIdx;
284  unsigned operator()(const LocIdx &L) const {
285  return L.asU64();
286  }
287 };
288 
289 /// Unique identifier for a value defined by an instruction, as a value type.
290 /// Casts back and forth to a uint64_t. Probably replacable with something less
291 /// bit-constrained. Each value identifies the instruction and machine location
292 /// where the value is defined, although there may be no corresponding machine
293 /// operand for it (ex: regmasks clobbering values). The instructions are
294 /// one-based, and definitions that are PHIs have instruction number zero.
295 ///
296 /// The obvious limits of a 1M block function or 1M instruction blocks are
297 /// problematic; but by that point we should probably have bailed out of
298 /// trying to analyse the function.
299 class ValueIDNum {
300  uint64_t BlockNo : 20; /// The block where the def happens.
301  uint64_t InstNo : 20; /// The Instruction where the def happens.
302  /// One based, is distance from start of block.
303  uint64_t LocNo : NUM_LOC_BITS; /// The machine location where the def happens.
304 
305 public:
306  // XXX -- temporarily enabled while the live-in / live-out tables are moved
307  // to something more type-y
308  ValueIDNum() : BlockNo(0xFFFFF),
309  InstNo(0xFFFFF),
310  LocNo(0xFFFFFF) { }
311 
312  ValueIDNum(uint64_t Block, uint64_t Inst, uint64_t Loc)
313  : BlockNo(Block), InstNo(Inst), LocNo(Loc) { }
314 
315  ValueIDNum(uint64_t Block, uint64_t Inst, LocIdx Loc)
316  : BlockNo(Block), InstNo(Inst), LocNo(Loc.asU64()) { }
317 
318  uint64_t getBlock() const { return BlockNo; }
319  uint64_t getInst() const { return InstNo; }
320  uint64_t getLoc() const { return LocNo; }
321  bool isPHI() const { return InstNo == 0; }
322 
323  uint64_t asU64() const {
324  uint64_t TmpBlock = BlockNo;
325  uint64_t TmpInst = InstNo;
326  return TmpBlock << 44ull | TmpInst << NUM_LOC_BITS | LocNo;
327  }
328 
329  static ValueIDNum fromU64(uint64_t v) {
330  uint64_t L = (v & 0x3FFF);
331  return {v >> 44ull, ((v >> NUM_LOC_BITS) & 0xFFFFF), L};
332  }
333 
334  bool operator<(const ValueIDNum &Other) const {
335  return asU64() < Other.asU64();
336  }
337 
338  bool operator==(const ValueIDNum &Other) const {
339  return std::tie(BlockNo, InstNo, LocNo) ==
340  std::tie(Other.BlockNo, Other.InstNo, Other.LocNo);
341  }
342 
343  bool operator!=(const ValueIDNum &Other) const { return !(*this == Other); }
344 
345  std::string asString(const std::string &mlocname) const {
346  return Twine("Value{bb: ")
347  .concat(Twine(BlockNo).concat(
348  Twine(", inst: ")
349  .concat((InstNo ? Twine(InstNo) : Twine("live-in"))
350  .concat(Twine(", loc: ").concat(Twine(mlocname)))
351  .concat(Twine("}")))))
352  .str();
353  }
354 
355  static ValueIDNum EmptyValue;
356 };
357 
358 } // end anonymous namespace
359 
360 namespace {
361 
362 /// Meta qualifiers for a value. Pair of whatever expression is used to qualify
363 /// the the value, and Boolean of whether or not it's indirect.
364 class DbgValueProperties {
365 public:
366  DbgValueProperties(const DIExpression *DIExpr, bool Indirect)
367  : DIExpr(DIExpr), Indirect(Indirect) {}
368 
369  /// Extract properties from an existing DBG_VALUE instruction.
370  DbgValueProperties(const MachineInstr &MI) {
371  assert(MI.isDebugValue());
372  DIExpr = MI.getDebugExpression();
373  Indirect = MI.getOperand(1).isImm();
374  }
375 
376  bool operator==(const DbgValueProperties &Other) const {
377  return std::tie(DIExpr, Indirect) == std::tie(Other.DIExpr, Other.Indirect);
378  }
379 
380  bool operator!=(const DbgValueProperties &Other) const {
381  return !(*this == Other);
382  }
383 
384  const DIExpression *DIExpr;
385  bool Indirect;
386 };
387 
388 /// Tracker for what values are in machine locations. Listens to the Things
389 /// being Done by various instructions, and maintains a table of what machine
390 /// locations have what values (as defined by a ValueIDNum).
391 ///
392 /// There are potentially a much larger number of machine locations on the
393 /// target machine than the actual working-set size of the function. On x86 for
394 /// example, we're extremely unlikely to want to track values through control
395 /// or debug registers. To avoid doing so, MLocTracker has several layers of
396 /// indirection going on, with two kinds of ``location'':
397 /// * A LocID uniquely identifies a register or spill location, with a
398 /// predictable value.
399 /// * A LocIdx is a key (in the database sense) for a LocID and a ValueIDNum.
400 /// Whenever a location is def'd or used by a MachineInstr, we automagically
401 /// create a new LocIdx for a location, but not otherwise. This ensures we only
402 /// account for locations that are actually used or defined. The cost is another
403 /// vector lookup (of LocID -> LocIdx) over any other implementation. This is
404 /// fairly cheap, and the compiler tries to reduce the working-set at any one
405 /// time in the function anyway.
406 ///
407 /// Register mask operands completely blow this out of the water; I've just
408 /// piled hacks on top of hacks to get around that.
409 class MLocTracker {
410 public:
411  MachineFunction &MF;
412  const TargetInstrInfo &TII;
413  const TargetRegisterInfo &TRI;
414  const TargetLowering &TLI;
415 
416  /// IndexedMap type, mapping from LocIdx to ValueIDNum.
417  using LocToValueType = IndexedMap<ValueIDNum, LocIdxToIndexFunctor>;
418 
419  /// Map of LocIdxes to the ValueIDNums that they store. This is tightly
420  /// packed, entries only exist for locations that are being tracked.
421  LocToValueType LocIdxToIDNum;
422 
423  /// "Map" of machine location IDs (i.e., raw register or spill number) to the
424  /// LocIdx key / number for that location. There are always at least as many
425  /// as the number of registers on the target -- if the value in the register
426  /// is not being tracked, then the LocIdx value will be zero. New entries are
427  /// appended if a new spill slot begins being tracked.
428  /// This, and the corresponding reverse map persist for the analysis of the
429  /// whole function, and is necessarying for decoding various vectors of
430  /// values.
431  std::vector<LocIdx> LocIDToLocIdx;
432 
433  /// Inverse map of LocIDToLocIdx.
435 
436  /// Unique-ification of spill slots. Used to number them -- their LocID
437  /// number is the index in SpillLocs minus one plus NumRegs.
438  UniqueVector<SpillLoc> SpillLocs;
439 
440  // If we discover a new machine location, assign it an mphi with this
441  // block number.
442  unsigned CurBB;
443 
444  /// Cached local copy of the number of registers the target has.
445  unsigned NumRegs;
446 
447  /// Collection of register mask operands that have been observed. Second part
448  /// of pair indicates the instruction that they happened in. Used to
449  /// reconstruct where defs happened if we start tracking a location later
450  /// on.
452 
453  /// Iterator for locations and the values they contain. Dereferencing
454  /// produces a struct/pair containing the LocIdx key for this location,
455  /// and a reference to the value currently stored. Simplifies the process
456  /// of seeking a particular location.
457  class MLocIterator {
458  LocToValueType &ValueMap;
459  LocIdx Idx;
460 
461  public:
462  class value_type {
463  public:
464  value_type(LocIdx Idx, ValueIDNum &Value) : Idx(Idx), Value(Value) { }
465  const LocIdx Idx; /// Read-only index of this location.
466  ValueIDNum &Value; /// Reference to the stored value at this location.
467  };
468 
469  MLocIterator(LocToValueType &ValueMap, LocIdx Idx)
470  : ValueMap(ValueMap), Idx(Idx) { }
471 
472  bool operator==(const MLocIterator &Other) const {
473  assert(&ValueMap == &Other.ValueMap);
474  return Idx == Other.Idx;
475  }
476 
477  bool operator!=(const MLocIterator &Other) const {
478  return !(*this == Other);
479  }
480 
481  void operator++() {
482  Idx = LocIdx(Idx.asU64() + 1);
483  }
484 
485  value_type operator*() {
486  return value_type(Idx, ValueMap[LocIdx(Idx)]);
487  }
488  };
489 
490  MLocTracker(MachineFunction &MF, const TargetInstrInfo &TII,
491  const TargetRegisterInfo &TRI, const TargetLowering &TLI)
492  : MF(MF), TII(TII), TRI(TRI), TLI(TLI),
493  LocIdxToIDNum(ValueIDNum::EmptyValue),
494  LocIdxToLocID(0) {
495  NumRegs = TRI.getNumRegs();
496  reset();
497  LocIDToLocIdx.resize(NumRegs, LocIdx::MakeIllegalLoc());
498  assert(NumRegs < (1u << NUM_LOC_BITS)); // Detect bit packing failure
499 
500  // Always track SP. This avoids the implicit clobbering caused by regmasks
501  // from affectings its values. (LiveDebugValues disbelieves calls and
502  // regmasks that claim to clobber SP).
504  if (SP) {
505  unsigned ID = getLocID(SP, false);
506  (void)lookupOrTrackRegister(ID);
507  }
508  }
509 
510  /// Produce location ID number for indexing LocIDToLocIdx. Takes the register
511  /// or spill number, and flag for whether it's a spill or not.
512  unsigned getLocID(Register RegOrSpill, bool isSpill) {
513  return (isSpill) ? RegOrSpill.id() + NumRegs - 1 : RegOrSpill.id();
514  }
515 
516  /// Accessor for reading the value at Idx.
517  ValueIDNum getNumAtPos(LocIdx Idx) const {
518  assert(Idx.asU64() < LocIdxToIDNum.size());
519  return LocIdxToIDNum[Idx];
520  }
521 
522  unsigned getNumLocs(void) const { return LocIdxToIDNum.size(); }
523 
524  /// Reset all locations to contain a PHI value at the designated block. Used
525  /// sometimes for actual PHI values, othertimes to indicate the block entry
526  /// value (before any more information is known).
527  void setMPhis(unsigned NewCurBB) {
528  CurBB = NewCurBB;
529  for (auto Location : locations())
530  Location.Value = {CurBB, 0, Location.Idx};
531  }
532 
533  /// Load values for each location from array of ValueIDNums. Take current
534  /// bbnum just in case we read a value from a hitherto untouched register.
535  void loadFromArray(ValueIDNum *Locs, unsigned NewCurBB) {
536  CurBB = NewCurBB;
537  // Iterate over all tracked locations, and load each locations live-in
538  // value into our local index.
539  for (auto Location : locations())
540  Location.Value = Locs[Location.Idx.asU64()];
541  }
542 
543  /// Wipe any un-necessary location records after traversing a block.
544  void reset(void) {
545  // We could reset all the location values too; however either loadFromArray
546  // or setMPhis should be called before this object is re-used. Just
547  // clear Masks, they're definitely not needed.
548  Masks.clear();
549  }
550 
551  /// Clear all data. Destroys the LocID <=> LocIdx map, which makes most of
552  /// the information in this pass uninterpretable.
553  void clear(void) {
554  reset();
555  LocIDToLocIdx.clear();
556  LocIdxToLocID.clear();
557  LocIdxToIDNum.clear();
558  //SpillLocs.reset(); XXX UniqueVector::reset assumes a SpillLoc casts from 0
559  SpillLocs = decltype(SpillLocs)();
560 
561  LocIDToLocIdx.resize(NumRegs, LocIdx::MakeIllegalLoc());
562  }
563 
564  /// Set a locaiton to a certain value.
565  void setMLoc(LocIdx L, ValueIDNum Num) {
566  assert(L.asU64() < LocIdxToIDNum.size());
567  LocIdxToIDNum[L] = Num;
568  }
569 
570  /// Create a LocIdx for an untracked register ID. Initialize it to either an
571  /// mphi value representing a live-in, or a recent register mask clobber.
572  LocIdx trackRegister(unsigned ID) {
573  assert(ID != 0);
574  LocIdx NewIdx = LocIdx(LocIdxToIDNum.size());
575  LocIdxToIDNum.grow(NewIdx);
576  LocIdxToLocID.grow(NewIdx);
577 
578  // Default: it's an mphi.
579  ValueIDNum ValNum = {CurBB, 0, NewIdx};
580  // Was this reg ever touched by a regmask?
581  for (const auto &MaskPair : reverse(Masks)) {
582  if (MaskPair.first->clobbersPhysReg(ID)) {
583  // There was an earlier def we skipped.
584  ValNum = {CurBB, MaskPair.second, NewIdx};
585  break;
586  }
587  }
588 
589  LocIdxToIDNum[NewIdx] = ValNum;
590  LocIdxToLocID[NewIdx] = ID;
591  return NewIdx;
592  }
593 
594  LocIdx lookupOrTrackRegister(unsigned ID) {
595  LocIdx &Index = LocIDToLocIdx[ID];
596  if (Index.isIllegal())
597  Index = trackRegister(ID);
598  return Index;
599  }
600 
601  /// Record a definition of the specified register at the given block / inst.
602  /// This doesn't take a ValueIDNum, because the definition and its location
603  /// are synonymous.
604  void defReg(Register R, unsigned BB, unsigned Inst) {
605  unsigned ID = getLocID(R, false);
606  LocIdx Idx = lookupOrTrackRegister(ID);
607  ValueIDNum ValueID = {BB, Inst, Idx};
608  LocIdxToIDNum[Idx] = ValueID;
609  }
610 
611  /// Set a register to a value number. To be used if the value number is
612  /// known in advance.
613  void setReg(Register R, ValueIDNum ValueID) {
614  unsigned ID = getLocID(R, false);
615  LocIdx Idx = lookupOrTrackRegister(ID);
616  LocIdxToIDNum[Idx] = ValueID;
617  }
618 
619  ValueIDNum readReg(Register R) {
620  unsigned ID = getLocID(R, false);
621  LocIdx Idx = lookupOrTrackRegister(ID);
622  return LocIdxToIDNum[Idx];
623  }
624 
625  /// Reset a register value to zero / empty. Needed to replicate the
626  /// VarLoc implementation where a copy to/from a register effectively
627  /// clears the contents of the source register. (Values can only have one
628  /// machine location in VarLocBasedImpl).
629  void wipeRegister(Register R) {
630  unsigned ID = getLocID(R, false);
631  LocIdx Idx = LocIDToLocIdx[ID];
632  LocIdxToIDNum[Idx] = ValueIDNum::EmptyValue;
633  }
634 
635  /// Determine the LocIdx of an existing register.
636  LocIdx getRegMLoc(Register R) {
637  unsigned ID = getLocID(R, false);
638  return LocIDToLocIdx[ID];
639  }
640 
641  /// Record a RegMask operand being executed. Defs any register we currently
642  /// track, stores a pointer to the mask in case we have to account for it
643  /// later.
644  void writeRegMask(const MachineOperand *MO, unsigned CurBB, unsigned InstID) {
645  // Ensure SP exists, so that we don't override it later.
647 
648  // Def any register we track have that isn't preserved. The regmask
649  // terminates the liveness of a register, meaning its value can't be
650  // relied upon -- we represent this by giving it a new value.
651  for (auto Location : locations()) {
652  unsigned ID = LocIdxToLocID[Location.Idx];
653  // Don't clobber SP, even if the mask says it's clobbered.
654  if (ID < NumRegs && ID != SP && MO->clobbersPhysReg(ID))
655  defReg(ID, CurBB, InstID);
656  }
657  Masks.push_back(std::make_pair(MO, InstID));
658  }
659 
660  /// Find LocIdx for SpillLoc \p L, creating a new one if it's not tracked.
661  LocIdx getOrTrackSpillLoc(SpillLoc L) {
662  unsigned SpillID = SpillLocs.idFor(L);
663  if (SpillID == 0) {
664  SpillID = SpillLocs.insert(L);
665  unsigned L = getLocID(SpillID, true);
666  LocIdx Idx = LocIdx(LocIdxToIDNum.size()); // New idx
667  LocIdxToIDNum.grow(Idx);
668  LocIdxToLocID.grow(Idx);
669  LocIDToLocIdx.push_back(Idx);
670  LocIdxToLocID[Idx] = L;
671  return Idx;
672  } else {
673  unsigned L = getLocID(SpillID, true);
674  LocIdx Idx = LocIDToLocIdx[L];
675  return Idx;
676  }
677  }
678 
679  /// Set the value stored in a spill slot.
680  void setSpill(SpillLoc L, ValueIDNum ValueID) {
681  LocIdx Idx = getOrTrackSpillLoc(L);
682  LocIdxToIDNum[Idx] = ValueID;
683  }
684 
685  /// Read whatever value is in a spill slot, or None if it isn't tracked.
686  Optional<ValueIDNum> readSpill(SpillLoc L) {
687  unsigned SpillID = SpillLocs.idFor(L);
688  if (SpillID == 0)
689  return None;
690 
691  unsigned LocID = getLocID(SpillID, true);
692  LocIdx Idx = LocIDToLocIdx[LocID];
693  return LocIdxToIDNum[Idx];
694  }
695 
696  /// Determine the LocIdx of a spill slot. Return None if it previously
697  /// hasn't had a value assigned.
698  Optional<LocIdx> getSpillMLoc(SpillLoc L) {
699  unsigned SpillID = SpillLocs.idFor(L);
700  if (SpillID == 0)
701  return None;
702  unsigned LocNo = getLocID(SpillID, true);
703  return LocIDToLocIdx[LocNo];
704  }
705 
706  /// Return true if Idx is a spill machine location.
707  bool isSpill(LocIdx Idx) const {
708  return LocIdxToLocID[Idx] >= NumRegs;
709  }
710 
711  MLocIterator begin() {
712  return MLocIterator(LocIdxToIDNum, 0);
713  }
714 
715  MLocIterator end() {
716  return MLocIterator(LocIdxToIDNum, LocIdxToIDNum.size());
717  }
718 
719  /// Return a range over all locations currently tracked.
720  iterator_range<MLocIterator> locations() {
721  return llvm::make_range(begin(), end());
722  }
723 
724  std::string LocIdxToName(LocIdx Idx) const {
725  unsigned ID = LocIdxToLocID[Idx];
726  if (ID >= NumRegs)
727  return Twine("slot ").concat(Twine(ID - NumRegs)).str();
728  else
729  return TRI.getRegAsmName(ID).str();
730  }
731 
732  std::string IDAsString(const ValueIDNum &Num) const {
733  std::string DefName = LocIdxToName(Num.getLoc());
734  return Num.asString(DefName);
735  }
736 
738  void dump() {
739  for (auto Location : locations()) {
740  std::string MLocName = LocIdxToName(Location.Value.getLoc());
741  std::string DefName = Location.Value.asString(MLocName);
742  dbgs() << LocIdxToName(Location.Idx) << " --> " << DefName << "\n";
743  }
744  }
745 
747  void dump_mloc_map() {
748  for (auto Location : locations()) {
749  std::string foo = LocIdxToName(Location.Idx);
750  dbgs() << "Idx " << Location.Idx.asU64() << " " << foo << "\n";
751  }
752  }
753 
754  /// Create a DBG_VALUE based on machine location \p MLoc. Qualify it with the
755  /// information in \pProperties, for variable Var. Don't insert it anywhere,
756  /// just return the builder for it.
757  MachineInstrBuilder emitLoc(Optional<LocIdx> MLoc, const DebugVariable &Var,
758  const DbgValueProperties &Properties) {
760  Var.getVariable()->getScope(),
761  const_cast<DILocation *>(Var.getInlinedAt()));
762  auto MIB = BuildMI(MF, DL, TII.get(TargetOpcode::DBG_VALUE));
763 
764  const DIExpression *Expr = Properties.DIExpr;
765  if (!MLoc) {
766  // No location -> DBG_VALUE $noreg
767  MIB.addReg(0, RegState::Debug);
768  MIB.addReg(0, RegState::Debug);
769  } else if (LocIdxToLocID[*MLoc] >= NumRegs) {
770  unsigned LocID = LocIdxToLocID[*MLoc];
771  const SpillLoc &Spill = SpillLocs[LocID - NumRegs + 1];
772 
773  auto *TRI = MF.getSubtarget().getRegisterInfo();
775  Spill.SpillOffset);
776  unsigned Base = Spill.SpillBase;
777  MIB.addReg(Base, RegState::Debug);
778  MIB.addImm(0);
779  } else {
780  unsigned LocID = LocIdxToLocID[*MLoc];
781  MIB.addReg(LocID, RegState::Debug);
782  if (Properties.Indirect)
783  MIB.addImm(0);
784  else
785  MIB.addReg(0, RegState::Debug);
786  }
787 
788  MIB.addMetadata(Var.getVariable());
789  MIB.addMetadata(Expr);
790  return MIB;
791  }
792 };
793 
794 /// Class recording the (high level) _value_ of a variable. Identifies either
795 /// the value of the variable as a ValueIDNum, or a constant MachineOperand.
796 /// This class also stores meta-information about how the value is qualified.
797 /// Used to reason about variable values when performing the second
798 /// (DebugVariable specific) dataflow analysis.
799 class DbgValue {
800 public:
801  union {
802  /// If Kind is Def, the value number that this value is based on.
803  ValueIDNum ID;
804  /// If Kind is Const, the MachineOperand defining this value.
805  MachineOperand MO;
806  /// For a NoVal DbgValue, which block it was generated in.
807  unsigned BlockNo;
808  };
809  /// Qualifiers for the ValueIDNum above.
810  DbgValueProperties Properties;
811 
812  typedef enum {
813  Undef, // Represents a DBG_VALUE $noreg in the transfer function only.
814  Def, // This value is defined by an inst, or is a PHI value.
815  Const, // A constant value contained in the MachineOperand field.
816  Proposed, // This is a tentative PHI value, which may be confirmed or
817  // invalidated later.
818  NoVal // Empty DbgValue, generated during dataflow. BlockNo stores
819  // which block this was generated in.
820  } KindT;
821  /// Discriminator for whether this is a constant or an in-program value.
822  KindT Kind;
823 
824  DbgValue(const ValueIDNum &Val, const DbgValueProperties &Prop, KindT Kind)
825  : ID(Val), Properties(Prop), Kind(Kind) {
826  assert(Kind == Def || Kind == Proposed);
827  }
828 
829  DbgValue(unsigned BlockNo, const DbgValueProperties &Prop, KindT Kind)
830  : BlockNo(BlockNo), Properties(Prop), Kind(Kind) {
831  assert(Kind == NoVal);
832  }
833 
834  DbgValue(const MachineOperand &MO, const DbgValueProperties &Prop, KindT Kind)
835  : MO(MO), Properties(Prop), Kind(Kind) {
836  assert(Kind == Const);
837  }
838 
839  DbgValue(const DbgValueProperties &Prop, KindT Kind)
840  : Properties(Prop), Kind(Kind) {
841  assert(Kind == Undef &&
842  "Empty DbgValue constructor must pass in Undef kind");
843  }
844 
845  void dump(const MLocTracker *MTrack) const {
846  if (Kind == Const) {
847  MO.dump();
848  } else if (Kind == NoVal) {
849  dbgs() << "NoVal(" << BlockNo << ")";
850  } else if (Kind == Proposed) {
851  dbgs() << "VPHI(" << MTrack->IDAsString(ID) << ")";
852  } else {
853  assert(Kind == Def);
854  dbgs() << MTrack->IDAsString(ID);
855  }
856  if (Properties.Indirect)
857  dbgs() << " indir";
858  if (Properties.DIExpr)
859  dbgs() << " " << *Properties.DIExpr;
860  }
861 
862  bool operator==(const DbgValue &Other) const {
863  if (std::tie(Kind, Properties) != std::tie(Other.Kind, Other.Properties))
864  return false;
865  else if (Kind == Proposed && ID != Other.ID)
866  return false;
867  else if (Kind == Def && ID != Other.ID)
868  return false;
869  else if (Kind == NoVal && BlockNo != Other.BlockNo)
870  return false;
871  else if (Kind == Const)
872  return MO.isIdenticalTo(Other.MO);
873 
874  return true;
875  }
876 
877  bool operator!=(const DbgValue &Other) const { return !(*this == Other); }
878 };
879 
880 /// Types for recording sets of variable fragments that overlap. For a given
881 /// local variable, we record all other fragments of that variable that could
882 /// overlap it, to reduce search time.
883 using FragmentOfVar =
884  std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
885 using OverlapMap =
887 
888 /// Collection of DBG_VALUEs observed when traversing a block. Records each
889 /// variable and the value the DBG_VALUE refers to. Requires the machine value
890 /// location dataflow algorithm to have run already, so that values can be
891 /// identified.
892 class VLocTracker {
893 public:
894  /// Map DebugVariable to the latest Value it's defined to have.
895  /// Needs to be a MapVector because we determine order-in-the-input-MIR from
896  /// the order in this container.
897  /// We only retain the last DbgValue in each block for each variable, to
898  /// determine the blocks live-out variable value. The Vars container forms the
899  /// transfer function for this block, as part of the dataflow analysis. The
900  /// movement of values between locations inside of a block is handled at a
901  /// much later stage, in the TransferTracker class.
905 
906 public:
907  VLocTracker() {}
908 
909  void defVar(const MachineInstr &MI, const DbgValueProperties &Properties,
911  assert(MI.isDebugValue() || MI.isDebugRef());
912  DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
913  MI.getDebugLoc()->getInlinedAt());
914  DbgValue Rec = (ID) ? DbgValue(*ID, Properties, DbgValue::Def)
915  : DbgValue(Properties, DbgValue::Undef);
916 
917  // Attempt insertion; overwrite if it's already mapped.
918  auto Result = Vars.insert(std::make_pair(Var, Rec));
919  if (!Result.second)
920  Result.first->second = Rec;
921  Scopes[Var] = MI.getDebugLoc().get();
922  }
923 
924  void defVar(const MachineInstr &MI, const MachineOperand &MO) {
925  // Only DBG_VALUEs can define constant-valued variables.
926  assert(MI.isDebugValue());
927  DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
928  MI.getDebugLoc()->getInlinedAt());
929  DbgValueProperties Properties(MI);
930  DbgValue Rec = DbgValue(MO, Properties, DbgValue::Const);
931 
932  // Attempt insertion; overwrite if it's already mapped.
933  auto Result = Vars.insert(std::make_pair(Var, Rec));
934  if (!Result.second)
935  Result.first->second = Rec;
936  Scopes[Var] = MI.getDebugLoc().get();
937  }
938 };
939 
940 /// Tracker for converting machine value locations and variable values into
941 /// variable locations (the output of LiveDebugValues), recorded as DBG_VALUEs
942 /// specifying block live-in locations and transfers within blocks.
943 ///
944 /// Operating on a per-block basis, this class takes a (pre-loaded) MLocTracker
945 /// and must be initialized with the set of variable values that are live-in to
946 /// the block. The caller then repeatedly calls process(). TransferTracker picks
947 /// out variable locations for the live-in variable values (if there _is_ a
948 /// location) and creates the corresponding DBG_VALUEs. Then, as the block is
949 /// stepped through, transfers of values between machine locations are
950 /// identified and if profitable, a DBG_VALUE created.
951 ///
952 /// This is where debug use-before-defs would be resolved: a variable with an
953 /// unavailable value could materialize in the middle of a block, when the
954 /// value becomes available. Or, we could detect clobbers and re-specify the
955 /// variable in a backup location. (XXX these are unimplemented).
956 class TransferTracker {
957 public:
958  const TargetInstrInfo *TII;
959  const TargetLowering *TLI;
960  /// This machine location tracker is assumed to always contain the up-to-date
961  /// value mapping for all machine locations. TransferTracker only reads
962  /// information from it. (XXX make it const?)
963  MLocTracker *MTracker;
964  MachineFunction &MF;
965  bool ShouldEmitDebugEntryValues;
966 
967  /// Record of all changes in variable locations at a block position. Awkwardly
968  /// we allow inserting either before or after the point: MBB != nullptr
969  /// indicates it's before, otherwise after.
970  struct Transfer {
971  MachineBasicBlock::instr_iterator Pos; /// Position to insert DBG_VALUes
972  MachineBasicBlock *MBB; /// non-null if we should insert after.
973  SmallVector<MachineInstr *, 4> Insts; /// Vector of DBG_VALUEs to insert.
974  };
975 
976  struct LocAndProperties {
977  LocIdx Loc;
978  DbgValueProperties Properties;
979  };
980 
981  /// Collection of transfers (DBG_VALUEs) to be inserted.
982  SmallVector<Transfer, 32> Transfers;
983 
984  /// Local cache of what-value-is-in-what-LocIdx. Used to identify differences
985  /// between TransferTrackers view of variable locations and MLocTrackers. For
986  /// example, MLocTracker observes all clobbers, but TransferTracker lazily
987  /// does not.
988  std::vector<ValueIDNum> VarLocs;
989 
990  /// Map from LocIdxes to which DebugVariables are based that location.
991  /// Mantained while stepping through the block. Not accurate if
992  /// VarLocs[Idx] != MTracker->LocIdxToIDNum[Idx].
993  std::map<LocIdx, SmallSet<DebugVariable, 4>> ActiveMLocs;
994 
995  /// Map from DebugVariable to it's current location and qualifying meta
996  /// information. To be used in conjunction with ActiveMLocs to construct
997  /// enough information for the DBG_VALUEs for a particular LocIdx.
999 
1000  /// Temporary cache of DBG_VALUEs to be entered into the Transfers collection.
1001  SmallVector<MachineInstr *, 4> PendingDbgValues;
1002 
1003  /// Record of a use-before-def: created when a value that's live-in to the
1004  /// current block isn't available in any machine location, but it will be
1005  /// defined in this block.
1006  struct UseBeforeDef {
1007  /// Value of this variable, def'd in block.
1008  ValueIDNum ID;
1009  /// Identity of this variable.
1010  DebugVariable Var;
1011  /// Additional variable properties.
1012  DbgValueProperties Properties;
1013  };
1014 
1015  /// Map from instruction index (within the block) to the set of UseBeforeDefs
1016  /// that become defined at that instruction.
1018 
1019  /// The set of variables that are in UseBeforeDefs and can become a location
1020  /// once the relevant value is defined. An element being erased from this
1021  /// collection prevents the use-before-def materializing.
1022  DenseSet<DebugVariable> UseBeforeDefVariables;
1023 
1024  const TargetRegisterInfo &TRI;
1025  const BitVector &CalleeSavedRegs;
1026 
1027  TransferTracker(const TargetInstrInfo *TII, MLocTracker *MTracker,
1029  const BitVector &CalleeSavedRegs, const TargetPassConfig &TPC)
1030  : TII(TII), MTracker(MTracker), MF(MF), TRI(TRI),
1031  CalleeSavedRegs(CalleeSavedRegs) {
1032  TLI = MF.getSubtarget().getTargetLowering();
1033  auto &TM = TPC.getTM<TargetMachine>();
1034  ShouldEmitDebugEntryValues = TM.Options.ShouldEmitDebugEntryValues();
1035  }
1036 
1037  /// Load object with live-in variable values. \p mlocs contains the live-in
1038  /// values in each machine location, while \p vlocs the live-in variable
1039  /// values. This method picks variable locations for the live-in variables,
1040  /// creates DBG_VALUEs and puts them in #Transfers, then prepares the other
1041  /// object fields to track variable locations as we step through the block.
1042  /// FIXME: could just examine mloctracker instead of passing in \p mlocs?
1043  void loadInlocs(MachineBasicBlock &MBB, ValueIDNum *MLocs,
1044  SmallVectorImpl<std::pair<DebugVariable, DbgValue>> &VLocs,
1045  unsigned NumLocs) {
1046  ActiveMLocs.clear();
1047  ActiveVLocs.clear();
1048  VarLocs.clear();
1049  VarLocs.reserve(NumLocs);
1050  UseBeforeDefs.clear();
1051  UseBeforeDefVariables.clear();
1052 
1053  auto isCalleeSaved = [&](LocIdx L) {
1054  unsigned Reg = MTracker->LocIdxToLocID[L];
1055  if (Reg >= MTracker->NumRegs)
1056  return false;
1057  for (MCRegAliasIterator RAI(Reg, &TRI, true); RAI.isValid(); ++RAI)
1058  if (CalleeSavedRegs.test(*RAI))
1059  return true;
1060  return false;
1061  };
1062 
1063  // Map of the preferred location for each value.
1064  std::map<ValueIDNum, LocIdx> ValueToLoc;
1065 
1066  // Produce a map of value numbers to the current machine locs they live
1067  // in. When emulating VarLocBasedImpl, there should only be one
1068  // location; when not, we get to pick.
1069  for (auto Location : MTracker->locations()) {
1070  LocIdx Idx = Location.Idx;
1071  ValueIDNum &VNum = MLocs[Idx.asU64()];
1072  VarLocs.push_back(VNum);
1073  auto it = ValueToLoc.find(VNum);
1074  // In order of preference, pick:
1075  // * Callee saved registers,
1076  // * Other registers,
1077  // * Spill slots.
1078  if (it == ValueToLoc.end() || MTracker->isSpill(it->second) ||
1079  (!isCalleeSaved(it->second) && isCalleeSaved(Idx.asU64()))) {
1080  // Insert, or overwrite if insertion failed.
1081  auto PrefLocRes = ValueToLoc.insert(std::make_pair(VNum, Idx));
1082  if (!PrefLocRes.second)
1083  PrefLocRes.first->second = Idx;
1084  }
1085  }
1086 
1087  // Now map variables to their picked LocIdxes.
1088  for (auto Var : VLocs) {
1089  if (Var.second.Kind == DbgValue::Const) {
1090  PendingDbgValues.push_back(
1091  emitMOLoc(Var.second.MO, Var.first, Var.second.Properties));
1092  continue;
1093  }
1094 
1095  // If the value has no location, we can't make a variable location.
1096  const ValueIDNum &Num = Var.second.ID;
1097  auto ValuesPreferredLoc = ValueToLoc.find(Num);
1098  if (ValuesPreferredLoc == ValueToLoc.end()) {
1099  // If it's a def that occurs in this block, register it as a
1100  // use-before-def to be resolved as we step through the block.
1101  if (Num.getBlock() == (unsigned)MBB.getNumber() && !Num.isPHI())
1102  addUseBeforeDef(Var.first, Var.second.Properties, Num);
1103  else
1104  recoverAsEntryValue(Var.first, Var.second.Properties, Num);
1105  continue;
1106  }
1107 
1108  LocIdx M = ValuesPreferredLoc->second;
1109  auto NewValue = LocAndProperties{M, Var.second.Properties};
1110  auto Result = ActiveVLocs.insert(std::make_pair(Var.first, NewValue));
1111  if (!Result.second)
1112  Result.first->second = NewValue;
1113  ActiveMLocs[M].insert(Var.first);
1114  PendingDbgValues.push_back(
1115  MTracker->emitLoc(M, Var.first, Var.second.Properties));
1116  }
1117  flushDbgValues(MBB.begin(), &MBB);
1118  }
1119 
1120  /// Record that \p Var has value \p ID, a value that becomes available
1121  /// later in the function.
1122  void addUseBeforeDef(const DebugVariable &Var,
1123  const DbgValueProperties &Properties, ValueIDNum ID) {
1124  UseBeforeDef UBD = {ID, Var, Properties};
1125  UseBeforeDefs[ID.getInst()].push_back(UBD);
1126  UseBeforeDefVariables.insert(Var);
1127  }
1128 
1129  /// After the instruction at index \p Inst and position \p pos has been
1130  /// processed, check whether it defines a variable value in a use-before-def.
1131  /// If so, and the variable value hasn't changed since the start of the
1132  /// block, create a DBG_VALUE.
1133  void checkInstForNewValues(unsigned Inst, MachineBasicBlock::iterator pos) {
1134  auto MIt = UseBeforeDefs.find(Inst);
1135  if (MIt == UseBeforeDefs.end())
1136  return;
1137 
1138  for (auto &Use : MIt->second) {
1139  LocIdx L = Use.ID.getLoc();
1140 
1141  // If something goes very wrong, we might end up labelling a COPY
1142  // instruction or similar with an instruction number, where it doesn't
1143  // actually define a new value, instead it moves a value. In case this
1144  // happens, discard.
1145  if (MTracker->LocIdxToIDNum[L] != Use.ID)
1146  continue;
1147 
1148  // If a different debug instruction defined the variable value / location
1149  // since the start of the block, don't materialize this use-before-def.
1150  if (!UseBeforeDefVariables.count(Use.Var))
1151  continue;
1152 
1153  PendingDbgValues.push_back(MTracker->emitLoc(L, Use.Var, Use.Properties));
1154  }
1155  flushDbgValues(pos, nullptr);
1156  }
1157 
1158  /// Helper to move created DBG_VALUEs into Transfers collection.
1159  void flushDbgValues(MachineBasicBlock::iterator Pos, MachineBasicBlock *MBB) {
1160  if (PendingDbgValues.size() == 0)
1161  return;
1162 
1163  // Pick out the instruction start position.
1165  if (MBB && Pos == MBB->begin())
1166  BundleStart = MBB->instr_begin();
1167  else
1168  BundleStart = getBundleStart(Pos->getIterator());
1169 
1170  Transfers.push_back({BundleStart, MBB, PendingDbgValues});
1171  PendingDbgValues.clear();
1172  }
1173 
1174  bool isEntryValueVariable(const DebugVariable &Var,
1175  const DIExpression *Expr) const {
1176  if (!Var.getVariable()->isParameter())
1177  return false;
1178 
1179  if (Var.getInlinedAt())
1180  return false;
1181 
1182  if (Expr->getNumElements() > 0)
1183  return false;
1184 
1185  return true;
1186  }
1187 
1188  bool isEntryValueValue(const ValueIDNum &Val) const {
1189  // Must be in entry block (block number zero), and be a PHI / live-in value.
1190  if (Val.getBlock() || !Val.isPHI())
1191  return false;
1192 
1193  // Entry values must enter in a register.
1194  if (MTracker->isSpill(Val.getLoc()))
1195  return false;
1196 
1199  Register Reg = MTracker->LocIdxToLocID[Val.getLoc()];
1200  return Reg != SP && Reg != FP;
1201  }
1202 
1203  bool recoverAsEntryValue(const DebugVariable &Var, DbgValueProperties &Prop,
1204  const ValueIDNum &Num) {
1205  // Is this variable location a candidate to be an entry value. First,
1206  // should we be trying this at all?
1207  if (!ShouldEmitDebugEntryValues)
1208  return false;
1209 
1210  // Is the variable appropriate for entry values (i.e., is a parameter).
1211  if (!isEntryValueVariable(Var, Prop.DIExpr))
1212  return false;
1213 
1214  // Is the value assigned to this variable still the entry value?
1215  if (!isEntryValueValue(Num))
1216  return false;
1217 
1218  // Emit a variable location using an entry value expression.
1221  Register Reg = MTracker->LocIdxToLocID[Num.getLoc()];
1223  MO.setIsDebug(true);
1224 
1225  PendingDbgValues.push_back(emitMOLoc(MO, Var, {NewExpr, Prop.Indirect}));
1226  return true;
1227  }
1228 
1229  /// Change a variable value after encountering a DBG_VALUE inside a block.
1230  void redefVar(const MachineInstr &MI) {
1231  DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
1232  MI.getDebugLoc()->getInlinedAt());
1233  DbgValueProperties Properties(MI);
1234 
1235  const MachineOperand &MO = MI.getOperand(0);
1236 
1237  // Ignore non-register locations, we don't transfer those.
1238  if (!MO.isReg() || MO.getReg() == 0) {
1239  auto It = ActiveVLocs.find(Var);
1240  if (It != ActiveVLocs.end()) {
1241  ActiveMLocs[It->second.Loc].erase(Var);
1242  ActiveVLocs.erase(It);
1243  }
1244  // Any use-before-defs no longer apply.
1245  UseBeforeDefVariables.erase(Var);
1246  return;
1247  }
1248 
1249  Register Reg = MO.getReg();
1250  LocIdx NewLoc = MTracker->getRegMLoc(Reg);
1251  redefVar(MI, Properties, NewLoc);
1252  }
1253 
1254  /// Handle a change in variable location within a block. Terminate the
1255  /// variables current location, and record the value it now refers to, so
1256  /// that we can detect location transfers later on.
1257  void redefVar(const MachineInstr &MI, const DbgValueProperties &Properties,
1258  Optional<LocIdx> OptNewLoc) {
1259  DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
1260  MI.getDebugLoc()->getInlinedAt());
1261  // Any use-before-defs no longer apply.
1262  UseBeforeDefVariables.erase(Var);
1263 
1264  // Erase any previous location,
1265  auto It = ActiveVLocs.find(Var);
1266  if (It != ActiveVLocs.end())
1267  ActiveMLocs[It->second.Loc].erase(Var);
1268 
1269  // If there _is_ no new location, all we had to do was erase.
1270  if (!OptNewLoc)
1271  return;
1272  LocIdx NewLoc = *OptNewLoc;
1273 
1274  // Check whether our local copy of values-by-location in #VarLocs is out of
1275  // date. Wipe old tracking data for the location if it's been clobbered in
1276  // the meantime.
1277  if (MTracker->getNumAtPos(NewLoc) != VarLocs[NewLoc.asU64()]) {
1278  for (auto &P : ActiveMLocs[NewLoc]) {
1279  ActiveVLocs.erase(P);
1280  }
1281  ActiveMLocs[NewLoc.asU64()].clear();
1282  VarLocs[NewLoc.asU64()] = MTracker->getNumAtPos(NewLoc);
1283  }
1284 
1285  ActiveMLocs[NewLoc].insert(Var);
1286  if (It == ActiveVLocs.end()) {
1287  ActiveVLocs.insert(
1288  std::make_pair(Var, LocAndProperties{NewLoc, Properties}));
1289  } else {
1290  It->second.Loc = NewLoc;
1291  It->second.Properties = Properties;
1292  }
1293  }
1294 
1295  /// Account for a location \p mloc being clobbered. Examine the variable
1296  /// locations that will be terminated: and try to recover them by using
1297  /// another location. Optionally, given \p MakeUndef, emit a DBG_VALUE to
1298  /// explicitly terminate a location if it can't be recovered.
1299  void clobberMloc(LocIdx MLoc, MachineBasicBlock::iterator Pos,
1300  bool MakeUndef = true) {
1301  auto ActiveMLocIt = ActiveMLocs.find(MLoc);
1302  if (ActiveMLocIt == ActiveMLocs.end())
1303  return;
1304 
1305  // What was the old variable value?
1306  ValueIDNum OldValue = VarLocs[MLoc.asU64()];
1307  VarLocs[MLoc.asU64()] = ValueIDNum::EmptyValue;
1308 
1309  // Examine the remaining variable locations: if we can find the same value
1310  // again, we can recover the location.
1311  Optional<LocIdx> NewLoc = None;
1312  for (auto Loc : MTracker->locations())
1313  if (Loc.Value == OldValue)
1314  NewLoc = Loc.Idx;
1315 
1316  // If there is no location, and we weren't asked to make the variable
1317  // explicitly undef, then stop here.
1318  if (!NewLoc && !MakeUndef) {
1319  // Try and recover a few more locations with entry values.
1320  for (auto &Var : ActiveMLocIt->second) {
1321  auto &Prop = ActiveVLocs.find(Var)->second.Properties;
1322  recoverAsEntryValue(Var, Prop, OldValue);
1323  }
1324  flushDbgValues(Pos, nullptr);
1325  return;
1326  }
1327 
1328  // Examine all the variables based on this location.
1329  DenseSet<DebugVariable> NewMLocs;
1330  for (auto &Var : ActiveMLocIt->second) {
1331  auto ActiveVLocIt = ActiveVLocs.find(Var);
1332  // Re-state the variable location: if there's no replacement then NewLoc
1333  // is None and a $noreg DBG_VALUE will be created. Otherwise, a DBG_VALUE
1334  // identifying the alternative location will be emitted.
1335  const DIExpression *Expr = ActiveVLocIt->second.Properties.DIExpr;
1336  DbgValueProperties Properties(Expr, false);
1337  PendingDbgValues.push_back(MTracker->emitLoc(NewLoc, Var, Properties));
1338 
1339  // Update machine locations <=> variable locations maps. Defer updating
1340  // ActiveMLocs to avoid invalidaing the ActiveMLocIt iterator.
1341  if (!NewLoc) {
1342  ActiveVLocs.erase(ActiveVLocIt);
1343  } else {
1344  ActiveVLocIt->second.Loc = *NewLoc;
1345  NewMLocs.insert(Var);
1346  }
1347  }
1348 
1349  // Commit any deferred ActiveMLoc changes.
1350  if (!NewMLocs.empty())
1351  for (auto &Var : NewMLocs)
1352  ActiveMLocs[*NewLoc].insert(Var);
1353 
1354  // We lazily track what locations have which values; if we've found a new
1355  // location for the clobbered value, remember it.
1356  if (NewLoc)
1357  VarLocs[NewLoc->asU64()] = OldValue;
1358 
1359  flushDbgValues(Pos, nullptr);
1360 
1361  ActiveMLocIt->second.clear();
1362  }
1363 
1364  /// Transfer variables based on \p Src to be based on \p Dst. This handles
1365  /// both register copies as well as spills and restores. Creates DBG_VALUEs
1366  /// describing the movement.
1367  void transferMlocs(LocIdx Src, LocIdx Dst, MachineBasicBlock::iterator Pos) {
1368  // Does Src still contain the value num we expect? If not, it's been
1369  // clobbered in the meantime, and our variable locations are stale.
1370  if (VarLocs[Src.asU64()] != MTracker->getNumAtPos(Src))
1371  return;
1372 
1373  // assert(ActiveMLocs[Dst].size() == 0);
1374  //^^^ Legitimate scenario on account of un-clobbered slot being assigned to?
1375  ActiveMLocs[Dst] = ActiveMLocs[Src];
1376  VarLocs[Dst.asU64()] = VarLocs[Src.asU64()];
1377 
1378  // For each variable based on Src; create a location at Dst.
1379  for (auto &Var : ActiveMLocs[Src]) {
1380  auto ActiveVLocIt = ActiveVLocs.find(Var);
1381  assert(ActiveVLocIt != ActiveVLocs.end());
1382  ActiveVLocIt->second.Loc = Dst;
1383 
1384  MachineInstr *MI =
1385  MTracker->emitLoc(Dst, Var, ActiveVLocIt->second.Properties);
1386  PendingDbgValues.push_back(MI);
1387  }
1388  ActiveMLocs[Src].clear();
1389  flushDbgValues(Pos, nullptr);
1390 
1391  // XXX XXX XXX "pretend to be old LDV" means dropping all tracking data
1392  // about the old location.
1393  if (EmulateOldLDV)
1394  VarLocs[Src.asU64()] = ValueIDNum::EmptyValue;
1395  }
1396 
1397  MachineInstrBuilder emitMOLoc(const MachineOperand &MO,
1398  const DebugVariable &Var,
1399  const DbgValueProperties &Properties) {
1401  Var.getVariable()->getScope(),
1402  const_cast<DILocation *>(Var.getInlinedAt()));
1403  auto MIB = BuildMI(MF, DL, TII->get(TargetOpcode::DBG_VALUE));
1404  MIB.add(MO);
1405  if (Properties.Indirect)
1406  MIB.addImm(0);
1407  else
1408  MIB.addReg(0);
1409  MIB.addMetadata(Var.getVariable());
1410  MIB.addMetadata(Properties.DIExpr);
1411  return MIB;
1412  }
1413 };
1414 
1415 class InstrRefBasedLDV : public LDVImpl {
1416 private:
1417  using FragmentInfo = DIExpression::FragmentInfo;
1418  using OptFragmentInfo = Optional<DIExpression::FragmentInfo>;
1419 
1420  // Helper while building OverlapMap, a map of all fragments seen for a given
1421  // DILocalVariable.
1422  using VarToFragments =
1424 
1425  /// Machine location/value transfer function, a mapping of which locations
1426  /// are assigned which new values.
1427  using MLocTransferMap = std::map<LocIdx, ValueIDNum>;
1428 
1429  /// Live in/out structure for the variable values: a per-block map of
1430  /// variables to their values. XXX, better name?
1431  using LiveIdxT =
1433 
1434  using VarAndLoc = std::pair<DebugVariable, DbgValue>;
1435 
1436  /// Type for a live-in value: the predecessor block, and its value.
1437  using InValueT = std::pair<MachineBasicBlock *, DbgValue *>;
1438 
1439  /// Vector (per block) of a collection (inner smallvector) of live-ins.
1440  /// Used as the result type for the variable value dataflow problem.
1441  using LiveInsT = SmallVector<SmallVector<VarAndLoc, 8>, 8>;
1442 
1443  const TargetRegisterInfo *TRI;
1444  const TargetInstrInfo *TII;
1445  const TargetFrameLowering *TFI;
1446  const MachineFrameInfo *MFI;
1447  BitVector CalleeSavedRegs;
1448  LexicalScopes LS;
1449  TargetPassConfig *TPC;
1450 
1451  /// Object to track machine locations as we step through a block. Could
1452  /// probably be a field rather than a pointer, as it's always used.
1453  MLocTracker *MTracker;
1454 
1455  /// Number of the current block LiveDebugValues is stepping through.
1456  unsigned CurBB;
1457 
1458  /// Number of the current instruction LiveDebugValues is evaluating.
1459  unsigned CurInst;
1460 
1461  /// Variable tracker -- listens to DBG_VALUEs occurring as InstrRefBasedImpl
1462  /// steps through a block. Reads the values at each location from the
1463  /// MLocTracker object.
1464  VLocTracker *VTracker;
1465 
1466  /// Tracker for transfers, listens to DBG_VALUEs and transfers of values
1467  /// between locations during stepping, creates new DBG_VALUEs when values move
1468  /// location.
1469  TransferTracker *TTracker;
1470 
1471  /// Blocks which are artificial, i.e. blocks which exclusively contain
1472  /// instructions without DebugLocs, or with line 0 locations.
1474 
1475  // Mapping of blocks to and from their RPOT order.
1478  DenseMap<unsigned, unsigned> BBNumToRPO;
1479 
1480  /// Pair of MachineInstr, and its 1-based offset into the containing block.
1481  using InstAndNum = std::pair<const MachineInstr *, unsigned>;
1482  /// Map from debug instruction number to the MachineInstr labelled with that
1483  /// number, and its location within the function. Used to transform
1484  /// instruction numbers in DBG_INSTR_REFs into machine value numbers.
1485  std::map<uint64_t, InstAndNum> DebugInstrNumToInstr;
1486 
1487  /// Record of where we observed a DBG_PHI instruction.
1488  class DebugPHIRecord {
1489  public:
1490  uint64_t InstrNum; ///< Instruction number of this DBG_PHI.
1491  MachineBasicBlock *MBB; ///< Block where DBG_PHI occurred.
1492  ValueIDNum ValueRead; ///< The value number read by the DBG_PHI.
1493  LocIdx ReadLoc; ///< Register/Stack location the DBG_PHI reads.
1494 
1495  operator unsigned() const { return InstrNum; }
1496  };
1497 
1498  /// Map from instruction numbers defined by DBG_PHIs to a record of what that
1499  /// DBG_PHI read and where. Populated and edited during the machine value
1500  /// location problem -- we use LLVMs SSA Updater to fix changes by
1501  /// optimizations that destroy PHI instructions.
1502  SmallVector<DebugPHIRecord, 32> DebugPHINumToValue;
1503 
1504  // Map of overlapping variable fragments.
1505  OverlapMap OverlapFragments;
1506  VarToFragments SeenFragments;
1507 
1508  /// Tests whether this instruction is a spill to a stack slot.
1509  bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF);
1510 
1511  /// Decide if @MI is a spill instruction and return true if it is. We use 2
1512  /// criteria to make this decision:
1513  /// - Is this instruction a store to a spill slot?
1514  /// - Is there a register operand that is both used and killed?
1515  /// TODO: Store optimization can fold spills into other stores (including
1516  /// other spills). We do not handle this yet (more than one memory operand).
1517  bool isLocationSpill(const MachineInstr &MI, MachineFunction *MF,
1518  unsigned &Reg);
1519 
1520  /// If a given instruction is identified as a spill, return the spill slot
1521  /// and set \p Reg to the spilled register.
1522  Optional<SpillLoc> isRestoreInstruction(const MachineInstr &MI,
1523  MachineFunction *MF, unsigned &Reg);
1524 
1525  /// Given a spill instruction, extract the register and offset used to
1526  /// address the spill slot in a target independent way.
1527  SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI);
1528 
1529  /// Observe a single instruction while stepping through a block.
1530  void process(MachineInstr &MI, ValueIDNum **MLiveOuts = nullptr,
1531  ValueIDNum **MLiveIns = nullptr);
1532 
1533  /// Examines whether \p MI is a DBG_VALUE and notifies trackers.
1534  /// \returns true if MI was recognized and processed.
1535  bool transferDebugValue(const MachineInstr &MI);
1536 
1537  /// Examines whether \p MI is a DBG_INSTR_REF and notifies trackers.
1538  /// \returns true if MI was recognized and processed.
1539  bool transferDebugInstrRef(MachineInstr &MI, ValueIDNum **MLiveOuts,
1540  ValueIDNum **MLiveIns);
1541 
1542  /// Stores value-information about where this PHI occurred, and what
1543  /// instruction number is associated with it.
1544  /// \returns true if MI was recognized and processed.
1545  bool transferDebugPHI(MachineInstr &MI);
1546 
1547  /// Examines whether \p MI is copy instruction, and notifies trackers.
1548  /// \returns true if MI was recognized and processed.
1549  bool transferRegisterCopy(MachineInstr &MI);
1550 
1551  /// Examines whether \p MI is stack spill or restore instruction, and
1552  /// notifies trackers. \returns true if MI was recognized and processed.
1553  bool transferSpillOrRestoreInst(MachineInstr &MI);
1554 
1555  /// Examines \p MI for any registers that it defines, and notifies trackers.
1556  void transferRegisterDef(MachineInstr &MI);
1557 
1558  /// Copy one location to the other, accounting for movement of subregisters
1559  /// too.
1560  void performCopy(Register Src, Register Dst);
1561 
1562  void accumulateFragmentMap(MachineInstr &MI);
1563 
1564  /// Determine the machine value number referred to by (potentially several)
1565  /// DBG_PHI instructions. Block duplication and tail folding can duplicate
1566  /// DBG_PHIs, shifting the position where values in registers merge, and
1567  /// forming another mini-ssa problem to solve.
1568  /// \p Here the position of a DBG_INSTR_REF seeking a machine value number
1569  /// \p InstrNum Debug instruction number defined by DBG_PHI instructions.
1570  /// \returns The machine value number at position Here, or None.
1571  Optional<ValueIDNum> resolveDbgPHIs(MachineFunction &MF,
1572  ValueIDNum **MLiveOuts,
1573  ValueIDNum **MLiveIns, MachineInstr &Here,
1574  uint64_t InstrNum);
1575 
1576  /// Step through the function, recording register definitions and movements
1577  /// in an MLocTracker. Convert the observations into a per-block transfer
1578  /// function in \p MLocTransfer, suitable for using with the machine value
1579  /// location dataflow problem.
1580  void
1581  produceMLocTransferFunction(MachineFunction &MF,
1582  SmallVectorImpl<MLocTransferMap> &MLocTransfer,
1583  unsigned MaxNumBlocks);
1584 
1585  /// Solve the machine value location dataflow problem. Takes as input the
1586  /// transfer functions in \p MLocTransfer. Writes the output live-in and
1587  /// live-out arrays to the (initialized to zero) multidimensional arrays in
1588  /// \p MInLocs and \p MOutLocs. The outer dimension is indexed by block
1589  /// number, the inner by LocIdx.
1590  void mlocDataflow(ValueIDNum **MInLocs, ValueIDNum **MOutLocs,
1591  SmallVectorImpl<MLocTransferMap> &MLocTransfer);
1592 
1593  /// Perform a control flow join (lattice value meet) of the values in machine
1594  /// locations at \p MBB. Follows the algorithm described in the file-comment,
1595  /// reading live-outs of predecessors from \p OutLocs, the current live ins
1596  /// from \p InLocs, and assigning the newly computed live ins back into
1597  /// \p InLocs. \returns two bools -- the first indicates whether a change
1598  /// was made, the second whether a lattice downgrade occurred. If the latter
1599  /// is true, revisiting this block is necessary.
1600  std::tuple<bool, bool>
1601  mlocJoin(MachineBasicBlock &MBB,
1603  ValueIDNum **OutLocs, ValueIDNum *InLocs);
1604 
1605  /// Solve the variable value dataflow problem, for a single lexical scope.
1606  /// Uses the algorithm from the file comment to resolve control flow joins,
1607  /// although there are extra hacks, see vlocJoin. Reads the
1608  /// locations of values from the \p MInLocs and \p MOutLocs arrays (see
1609  /// mlocDataflow) and reads the variable values transfer function from
1610  /// \p AllTheVlocs. Live-in and Live-out variable values are stored locally,
1611  /// with the live-ins permanently stored to \p Output once the fixedpoint is
1612  /// reached.
1613  /// \p VarsWeCareAbout contains a collection of the variables in \p Scope
1614  /// that we should be tracking.
1615  /// \p AssignBlocks contains the set of blocks that aren't in \p Scope, but
1616  /// which do contain DBG_VALUEs, which VarLocBasedImpl tracks locations
1617  /// through.
1618  void vlocDataflow(const LexicalScope *Scope, const DILocation *DILoc,
1619  const SmallSet<DebugVariable, 4> &VarsWeCareAbout,
1621  LiveInsT &Output, ValueIDNum **MOutLocs,
1622  ValueIDNum **MInLocs,
1623  SmallVectorImpl<VLocTracker> &AllTheVLocs);
1624 
1625  /// Compute the live-ins to a block, considering control flow merges according
1626  /// to the method in the file comment. Live out and live in variable values
1627  /// are stored in \p VLOCOutLocs and \p VLOCInLocs. The live-ins for \p MBB
1628  /// are computed and stored into \p VLOCInLocs. \returns true if the live-ins
1629  /// are modified.
1630  /// \p InLocsT Output argument, storage for calculated live-ins.
1631  /// \returns two bools -- the first indicates whether a change
1632  /// was made, the second whether a lattice downgrade occurred. If the latter
1633  /// is true, revisiting this block is necessary.
1634  std::tuple<bool, bool>
1635  vlocJoin(MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs,
1637  unsigned BBNum, const SmallSet<DebugVariable, 4> &AllVars,
1638  ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
1642 
1643  /// Continue exploration of the variable-value lattice, as explained in the
1644  /// file-level comment. \p OldLiveInLocation contains the current
1645  /// exploration position, from which we need to descend further. \p Values
1646  /// contains the set of live-in values, \p CurBlockRPONum the RPO number of
1647  /// the current block, and \p CandidateLocations a set of locations that
1648  /// should be considered as PHI locations, if we reach the bottom of the
1649  /// lattice. \returns true if we should downgrade; the value is the agreeing
1650  /// value number in a non-backedge predecessor.
1651  bool vlocDowngradeLattice(const MachineBasicBlock &MBB,
1652  const DbgValue &OldLiveInLocation,
1653  const SmallVectorImpl<InValueT> &Values,
1654  unsigned CurBlockRPONum);
1655 
1656  /// For the given block and live-outs feeding into it, try to find a
1657  /// machine location where they all join. If a solution for all predecessors
1658  /// can't be found, a location where all non-backedge-predecessors join
1659  /// will be returned instead. While this method finds a join location, this
1660  /// says nothing as to whether it should be used.
1661  /// \returns Pair of value ID if found, and true when the correct value
1662  /// is available on all predecessor edges, or false if it's only available
1663  /// for non-backedge predecessors.
1664  std::tuple<Optional<ValueIDNum>, bool>
1665  pickVPHILoc(MachineBasicBlock &MBB, const DebugVariable &Var,
1666  const LiveIdxT &LiveOuts, ValueIDNum **MOutLocs,
1667  ValueIDNum **MInLocs,
1668  const SmallVectorImpl<MachineBasicBlock *> &BlockOrders);
1669 
1670  /// Given the solutions to the two dataflow problems, machine value locations
1671  /// in \p MInLocs and live-in variable values in \p SavedLiveIns, runs the
1672  /// TransferTracker class over the function to produce live-in and transfer
1673  /// DBG_VALUEs, then inserts them. Groups of DBG_VALUEs are inserted in the
1674  /// order given by AllVarsNumbering -- this could be any stable order, but
1675  /// right now "order of appearence in function, when explored in RPO", so
1676  /// that we can compare explictly against VarLocBasedImpl.
1677  void emitLocations(MachineFunction &MF, LiveInsT SavedLiveIns,
1678  ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
1679  DenseMap<DebugVariable, unsigned> &AllVarsNumbering,
1680  const TargetPassConfig &TPC);
1681 
1682  /// Boilerplate computation of some initial sets, artifical blocks and
1683  /// RPOT block ordering.
1684  void initialSetup(MachineFunction &MF);
1685 
1686  bool ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC,
1687  unsigned InputBBLimit, unsigned InputDbgValLimit) override;
1688 
1689 public:
1690  /// Default construct and initialize the pass.
1691  InstrRefBasedLDV();
1692 
1694  void dump_mloc_transfer(const MLocTransferMap &mloc_transfer) const;
1695 
1696  bool isCalleeSaved(LocIdx L) {
1697  unsigned Reg = MTracker->LocIdxToLocID[L];
1698  for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
1699  if (CalleeSavedRegs.test(*RAI))
1700  return true;
1701  return false;
1702  }
1703 };
1704 
1705 } // end anonymous namespace
1706 
1707 //===----------------------------------------------------------------------===//
1708 // Implementation
1709 //===----------------------------------------------------------------------===//
1710 
1711 ValueIDNum ValueIDNum::EmptyValue = {UINT_MAX, UINT_MAX, UINT_MAX};
1712 
1713 /// Default construct and initialize the pass.
1714 InstrRefBasedLDV::InstrRefBasedLDV() {}
1715 
1716 //===----------------------------------------------------------------------===//
1717 // Debug Range Extension Implementation
1718 //===----------------------------------------------------------------------===//
1719 
1720 #ifndef NDEBUG
1721 // Something to restore in the future.
1722 // void InstrRefBasedLDV::printVarLocInMBB(..)
1723 #endif
1724 
1725 SpillLoc
1726 InstrRefBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
1727  assert(MI.hasOneMemOperand() &&
1728  "Spill instruction does not have exactly one memory operand?");
1729  auto MMOI = MI.memoperands_begin();
1730  const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
1732  "Inconsistent memory operand in spill instruction");
1733  int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
1734  const MachineBasicBlock *MBB = MI.getParent();
1735  Register Reg;
1737  return {Reg, Offset};
1738 }
1739 
1740 /// End all previous ranges related to @MI and start a new range from @MI
1741 /// if it is a DBG_VALUE instr.
1742 bool InstrRefBasedLDV::transferDebugValue(const MachineInstr &MI) {
1743  if (!MI.isDebugValue())
1744  return false;
1745 
1746  const DILocalVariable *Var = MI.getDebugVariable();
1747  const DIExpression *Expr = MI.getDebugExpression();
1748  const DILocation *DebugLoc = MI.getDebugLoc();
1749  const DILocation *InlinedAt = DebugLoc->getInlinedAt();
1751  "Expected inlined-at fields to agree");
1752 
1753  DebugVariable V(Var, Expr, InlinedAt);
1754  DbgValueProperties Properties(MI);
1755 
1756  // If there are no instructions in this lexical scope, do no location tracking
1757  // at all, this variable shouldn't get a legitimate location range.
1758  auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get());
1759  if (Scope == nullptr)
1760  return true; // handled it; by doing nothing
1761 
1762  // For now, ignore DBG_VALUE_LISTs when extending ranges. Allow it to
1763  // contribute to locations in this block, but don't propagate further.
1764  // Interpret it like a DBG_VALUE $noreg.
1765  if (MI.isDebugValueList()) {
1766  if (VTracker)
1767  VTracker->defVar(MI, Properties, None);
1768  if (TTracker)
1769  TTracker->redefVar(MI, Properties, None);
1770  return true;
1771  }
1772 
1773  const MachineOperand &MO = MI.getOperand(0);
1774 
1775  // MLocTracker needs to know that this register is read, even if it's only
1776  // read by a debug inst.
1777  if (MO.isReg() && MO.getReg() != 0)
1778  (void)MTracker->readReg(MO.getReg());
1779 
1780  // If we're preparing for the second analysis (variables), the machine value
1781  // locations are already solved, and we report this DBG_VALUE and the value
1782  // it refers to to VLocTracker.
1783  if (VTracker) {
1784  if (MO.isReg()) {
1785  // Feed defVar the new variable location, or if this is a
1786  // DBG_VALUE $noreg, feed defVar None.
1787  if (MO.getReg())
1788  VTracker->defVar(MI, Properties, MTracker->readReg(MO.getReg()));
1789  else
1790  VTracker->defVar(MI, Properties, None);
1791  } else if (MI.getOperand(0).isImm() || MI.getOperand(0).isFPImm() ||
1792  MI.getOperand(0).isCImm()) {
1793  VTracker->defVar(MI, MI.getOperand(0));
1794  }
1795  }
1796 
1797  // If performing final tracking of transfers, report this variable definition
1798  // to the TransferTracker too.
1799  if (TTracker)
1800  TTracker->redefVar(MI);
1801  return true;
1802 }
1803 
1804 bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI,
1805  ValueIDNum **MLiveOuts,
1806  ValueIDNum **MLiveIns) {
1807  if (!MI.isDebugRef())
1808  return false;
1809 
1810  // Only handle this instruction when we are building the variable value
1811  // transfer function.
1812  if (!VTracker)
1813  return false;
1814 
1815  unsigned InstNo = MI.getOperand(0).getImm();
1816  unsigned OpNo = MI.getOperand(1).getImm();
1817 
1818  const DILocalVariable *Var = MI.getDebugVariable();
1819  const DIExpression *Expr = MI.getDebugExpression();
1820  const DILocation *DebugLoc = MI.getDebugLoc();
1821  const DILocation *InlinedAt = DebugLoc->getInlinedAt();
1823  "Expected inlined-at fields to agree");
1824 
1825  DebugVariable V(Var, Expr, InlinedAt);
1826 
1827  auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get());
1828  if (Scope == nullptr)
1829  return true; // Handled by doing nothing. This variable is never in scope.
1830 
1831  const MachineFunction &MF = *MI.getParent()->getParent();
1832 
1833  // Various optimizations may have happened to the value during codegen,
1834  // recorded in the value substitution table. Apply any substitutions to
1835  // the instruction / operand number in this DBG_INSTR_REF, and collect
1836  // any subregister extractions performed during optimization.
1837 
1838  // Create dummy substitution with Src set, for lookup.
1839  auto SoughtSub =
1840  MachineFunction::DebugSubstitution({InstNo, OpNo}, {0, 0}, 0);
1841 
1842  SmallVector<unsigned, 4> SeenSubregs;
1843  auto LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub);
1844  while (LowerBoundIt != MF.DebugValueSubstitutions.end() &&
1845  LowerBoundIt->Src == SoughtSub.Src) {
1846  std::tie(InstNo, OpNo) = LowerBoundIt->Dest;
1847  SoughtSub.Src = LowerBoundIt->Dest;
1848  if (unsigned Subreg = LowerBoundIt->Subreg)
1849  SeenSubregs.push_back(Subreg);
1850  LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub);
1851  }
1852 
1853  // Default machine value number is <None> -- if no instruction defines
1854  // the corresponding value, it must have been optimized out.
1855  Optional<ValueIDNum> NewID = None;
1856 
1857  // Try to lookup the instruction number, and find the machine value number
1858  // that it defines. It could be an instruction, or a PHI.
1859  auto InstrIt = DebugInstrNumToInstr.find(InstNo);
1860  auto PHIIt = std::lower_bound(DebugPHINumToValue.begin(),
1861  DebugPHINumToValue.end(), InstNo);
1862  if (InstrIt != DebugInstrNumToInstr.end()) {
1863  const MachineInstr &TargetInstr = *InstrIt->second.first;
1864  uint64_t BlockNo = TargetInstr.getParent()->getNumber();
1865 
1866  // Pick out the designated operand.
1867  assert(OpNo < TargetInstr.getNumOperands());
1868  const MachineOperand &MO = TargetInstr.getOperand(OpNo);
1869 
1870  // Today, this can only be a register.
1871  assert(MO.isReg() && MO.isDef());
1872 
1873  unsigned LocID = MTracker->getLocID(MO.getReg(), false);
1874  LocIdx L = MTracker->LocIDToLocIdx[LocID];
1875  NewID = ValueIDNum(BlockNo, InstrIt->second.second, L);
1876  } else if (PHIIt != DebugPHINumToValue.end() && PHIIt->InstrNum == InstNo) {
1877  // It's actually a PHI value. Which value it is might not be obvious, use
1878  // the resolver helper to find out.
1879  NewID = resolveDbgPHIs(*MI.getParent()->getParent(), MLiveOuts, MLiveIns,
1880  MI, InstNo);
1881  }
1882 
1883  // Apply any subregister extractions, in reverse. We might have seen code
1884  // like this:
1885  // CALL64 @foo, implicit-def $rax
1886  // %0:gr64 = COPY $rax
1887  // %1:gr32 = COPY %0.sub_32bit
1888  // %2:gr16 = COPY %1.sub_16bit
1889  // %3:gr8 = COPY %2.sub_8bit
1890  // In which case each copy would have been recorded as a substitution with
1891  // a subregister qualifier. Apply those qualifiers now.
1892  if (NewID && !SeenSubregs.empty()) {
1893  unsigned Offset = 0;
1894  unsigned Size = 0;
1895 
1896  // Look at each subregister that we passed through, and progressively
1897  // narrow in, accumulating any offsets that occur. Substitutions should
1898  // only ever be the same or narrower width than what they read from;
1899  // iterate in reverse order so that we go from wide to small.
1900  for (unsigned Subreg : reverse(SeenSubregs)) {
1901  unsigned ThisSize = TRI->getSubRegIdxSize(Subreg);
1902  unsigned ThisOffset = TRI->getSubRegIdxOffset(Subreg);
1903  Offset += ThisOffset;
1904  Size = (Size == 0) ? ThisSize : std::min(Size, ThisSize);
1905  }
1906 
1907  // If that worked, look for an appropriate subregister with the register
1908  // where the define happens. Don't look at values that were defined during
1909  // a stack write: we can't currently express register locations within
1910  // spills.
1911  LocIdx L = NewID->getLoc();
1912  if (NewID && !MTracker->isSpill(L)) {
1913  // Find the register class for the register where this def happened.
1914  // FIXME: no index for this?
1915  Register Reg = MTracker->LocIdxToLocID[L];
1916  const TargetRegisterClass *TRC = nullptr;
1917  for (auto *TRCI : TRI->regclasses())
1918  if (TRCI->contains(Reg))
1919  TRC = TRCI;
1920  assert(TRC && "Couldn't find target register class?");
1921 
1922  // If the register we have isn't the right size or in the right place,
1923  // Try to find a subregister inside it.
1924  unsigned MainRegSize = TRI->getRegSizeInBits(*TRC);
1925  if (Size != MainRegSize || Offset) {
1926  // Enumerate all subregisters, searching.
1927  Register NewReg = 0;
1928  for (MCSubRegIterator SRI(Reg, TRI, false); SRI.isValid(); ++SRI) {
1929  unsigned Subreg = TRI->getSubRegIndex(Reg, *SRI);
1930  unsigned SubregSize = TRI->getSubRegIdxSize(Subreg);
1931  unsigned SubregOffset = TRI->getSubRegIdxOffset(Subreg);
1932  if (SubregSize == Size && SubregOffset == Offset) {
1933  NewReg = *SRI;
1934  break;
1935  }
1936  }
1937 
1938  // If we didn't find anything: there's no way to express our value.
1939  if (!NewReg) {
1940  NewID = None;
1941  } else {
1942  // Re-state the value as being defined within the subregister
1943  // that we found.
1944  LocIdx NewLoc = MTracker->lookupOrTrackRegister(NewReg);
1945  NewID = ValueIDNum(NewID->getBlock(), NewID->getInst(), NewLoc);
1946  }
1947  }
1948  } else {
1949  // If we can't handle subregisters, unset the new value.
1950  NewID = None;
1951  }
1952  }
1953 
1954  // We, we have a value number or None. Tell the variable value tracker about
1955  // it. The rest of this LiveDebugValues implementation acts exactly the same
1956  // for DBG_INSTR_REFs as DBG_VALUEs (just, the former can refer to values that
1957  // aren't immediately available).
1958  DbgValueProperties Properties(Expr, false);
1959  VTracker->defVar(MI, Properties, NewID);
1960 
1961  // If we're on the final pass through the function, decompose this INSTR_REF
1962  // into a plain DBG_VALUE.
1963  if (!TTracker)
1964  return true;
1965 
1966  // Pick a location for the machine value number, if such a location exists.
1967  // (This information could be stored in TransferTracker to make it faster).
1968  Optional<LocIdx> FoundLoc = None;
1969  for (auto Location : MTracker->locations()) {
1970  LocIdx CurL = Location.Idx;
1971  ValueIDNum ID = MTracker->LocIdxToIDNum[CurL];
1972  if (NewID && ID == NewID) {
1973  // If this is the first location with that value, pick it. Otherwise,
1974  // consider whether it's a "longer term" location.
1975  if (!FoundLoc) {
1976  FoundLoc = CurL;
1977  continue;
1978  }
1979 
1980  if (MTracker->isSpill(CurL))
1981  FoundLoc = CurL; // Spills are a longer term location.
1982  else if (!MTracker->isSpill(*FoundLoc) &&
1983  !MTracker->isSpill(CurL) &&
1984  !isCalleeSaved(*FoundLoc) &&
1985  isCalleeSaved(CurL))
1986  FoundLoc = CurL; // Callee saved regs are longer term than normal.
1987  }
1988  }
1989 
1990  // Tell transfer tracker that the variable value has changed.
1991  TTracker->redefVar(MI, Properties, FoundLoc);
1992 
1993  // If there was a value with no location; but the value is defined in a
1994  // later instruction in this block, this is a block-local use-before-def.
1995  if (!FoundLoc && NewID && NewID->getBlock() == CurBB &&
1996  NewID->getInst() > CurInst)
1997  TTracker->addUseBeforeDef(V, {MI.getDebugExpression(), false}, *NewID);
1998 
1999  // Produce a DBG_VALUE representing what this DBG_INSTR_REF meant.
2000  // This DBG_VALUE is potentially a $noreg / undefined location, if
2001  // FoundLoc is None.
2002  // (XXX -- could morph the DBG_INSTR_REF in the future).
2003  MachineInstr *DbgMI = MTracker->emitLoc(FoundLoc, V, Properties);
2004  TTracker->PendingDbgValues.push_back(DbgMI);
2005  TTracker->flushDbgValues(MI.getIterator(), nullptr);
2006  return true;
2007 }
2008 
2009 bool InstrRefBasedLDV::transferDebugPHI(MachineInstr &MI) {
2010  if (!MI.isDebugPHI())
2011  return false;
2012 
2013  // Analyse these only when solving the machine value location problem.
2014  if (VTracker || TTracker)
2015  return true;
2016 
2017  // First operand is the value location, either a stack slot or register.
2018  // Second is the debug instruction number of the original PHI.
2019  const MachineOperand &MO = MI.getOperand(0);
2020  unsigned InstrNum = MI.getOperand(1).getImm();
2021 
2022  if (MO.isReg()) {
2023  // The value is whatever's currently in the register. Read and record it,
2024  // to be analysed later.
2025  Register Reg = MO.getReg();
2026  ValueIDNum Num = MTracker->readReg(Reg);
2027  auto PHIRec = DebugPHIRecord(
2028  {InstrNum, MI.getParent(), Num, MTracker->lookupOrTrackRegister(Reg)});
2029  DebugPHINumToValue.push_back(PHIRec);
2030  } else {
2031  // The value is whatever's in this stack slot.
2032  assert(MO.isFI());
2033  unsigned FI = MO.getIndex();
2034 
2035  // If the stack slot is dead, then this was optimized away.
2036  // FIXME: stack slot colouring should account for slots that get merged.
2037  if (MFI->isDeadObjectIndex(FI))
2038  return true;
2039 
2040  // Identify this spill slot.
2041  Register Base;
2042  StackOffset Offs = TFI->getFrameIndexReference(*MI.getMF(), FI, Base);
2043  SpillLoc SL = {Base, Offs};
2044  Optional<ValueIDNum> Num = MTracker->readSpill(SL);
2045 
2046  if (!Num)
2047  // Nothing ever writes to this slot. Curious, but nothing we can do.
2048  return true;
2049 
2050  // Record this DBG_PHI for later analysis.
2051  auto DbgPHI = DebugPHIRecord(
2052  {InstrNum, MI.getParent(), *Num, *MTracker->getSpillMLoc(SL)});
2053  DebugPHINumToValue.push_back(DbgPHI);
2054  }
2055 
2056  return true;
2057 }
2058 
2059 void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) {
2060  // Meta Instructions do not affect the debug liveness of any register they
2061  // define.
2062  if (MI.isImplicitDef()) {
2063  // Except when there's an implicit def, and the location it's defining has
2064  // no value number. The whole point of an implicit def is to announce that
2065  // the register is live, without be specific about it's value. So define
2066  // a value if there isn't one already.
2067  ValueIDNum Num = MTracker->readReg(MI.getOperand(0).getReg());
2068  // Has a legitimate value -> ignore the implicit def.
2069  if (Num.getLoc() != 0)
2070  return;
2071  // Otherwise, def it here.
2072  } else if (MI.isMetaInstruction())
2073  return;
2074 
2075  MachineFunction *MF = MI.getMF();
2076  const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
2078 
2079  // Find the regs killed by MI, and find regmasks of preserved regs.
2080  // Max out the number of statically allocated elements in `DeadRegs`, as this
2081  // prevents fallback to std::set::count() operations.
2082  SmallSet<uint32_t, 32> DeadRegs;
2085  for (const MachineOperand &MO : MI.operands()) {
2086  // Determine whether the operand is a register def.
2087  if (MO.isReg() && MO.isDef() && MO.getReg() &&
2089  !(MI.isCall() && MO.getReg() == SP)) {
2090  // Remove ranges of all aliased registers.
2091  for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
2092  // FIXME: Can we break out of this loop early if no insertion occurs?
2093  DeadRegs.insert(*RAI);
2094  } else if (MO.isRegMask()) {
2095  RegMasks.push_back(MO.getRegMask());
2096  RegMaskPtrs.push_back(&MO);
2097  }
2098  }
2099 
2100  // Tell MLocTracker about all definitions, of regmasks and otherwise.
2101  for (uint32_t DeadReg : DeadRegs)
2102  MTracker->defReg(DeadReg, CurBB, CurInst);
2103 
2104  for (auto *MO : RegMaskPtrs)
2105  MTracker->writeRegMask(MO, CurBB, CurInst);
2106 
2107  if (!TTracker)
2108  return;
2109 
2110  // When committing variable values to locations: tell transfer tracker that
2111  // we've clobbered things. It may be able to recover the variable from a
2112  // different location.
2113 
2114  // Inform TTracker about any direct clobbers.
2115  for (uint32_t DeadReg : DeadRegs) {
2116  LocIdx Loc = MTracker->lookupOrTrackRegister(DeadReg);
2117  TTracker->clobberMloc(Loc, MI.getIterator(), false);
2118  }
2119 
2120  // Look for any clobbers performed by a register mask. Only test locations
2121  // that are actually being tracked.
2122  for (auto L : MTracker->locations()) {
2123  // Stack locations can't be clobbered by regmasks.
2124  if (MTracker->isSpill(L.Idx))
2125  continue;
2126 
2127  Register Reg = MTracker->LocIdxToLocID[L.Idx];
2128  for (auto *MO : RegMaskPtrs)
2129  if (MO->clobbersPhysReg(Reg))
2130  TTracker->clobberMloc(L.Idx, MI.getIterator(), false);
2131  }
2132 }
2133 
2134 void InstrRefBasedLDV::performCopy(Register SrcRegNum, Register DstRegNum) {
2135  ValueIDNum SrcValue = MTracker->readReg(SrcRegNum);
2136 
2137  MTracker->setReg(DstRegNum, SrcValue);
2138 
2139  // In all circumstances, re-def the super registers. It's definitely a new
2140  // value now. This doesn't uniquely identify the composition of subregs, for
2141  // example, two identical values in subregisters composed in different
2142  // places would not get equal value numbers.
2143  for (MCSuperRegIterator SRI(DstRegNum, TRI); SRI.isValid(); ++SRI)
2144  MTracker->defReg(*SRI, CurBB, CurInst);
2145 
2146  // If we're emulating VarLocBasedImpl, just define all the subregisters.
2147  // DBG_VALUEs of them will expect to be tracked from the DBG_VALUE, not
2148  // through prior copies.
2149  if (EmulateOldLDV) {
2150  for (MCSubRegIndexIterator DRI(DstRegNum, TRI); DRI.isValid(); ++DRI)
2151  MTracker->defReg(DRI.getSubReg(), CurBB, CurInst);
2152  return;
2153  }
2154 
2155  // Otherwise, actually copy subregisters from one location to another.
2156  // XXX: in addition, any subregisters of DstRegNum that don't line up with
2157  // the source register should be def'd.
2158  for (MCSubRegIndexIterator SRI(SrcRegNum, TRI); SRI.isValid(); ++SRI) {
2159  unsigned SrcSubReg = SRI.getSubReg();
2160  unsigned SubRegIdx = SRI.getSubRegIndex();
2161  unsigned DstSubReg = TRI->getSubReg(DstRegNum, SubRegIdx);
2162  if (!DstSubReg)
2163  continue;
2164 
2165  // Do copy. There are two matching subregisters, the source value should
2166  // have been def'd when the super-reg was, the latter might not be tracked
2167  // yet.
2168  // This will force SrcSubReg to be tracked, if it isn't yet.
2169  (void)MTracker->readReg(SrcSubReg);
2170  LocIdx SrcL = MTracker->getRegMLoc(SrcSubReg);
2171  assert(SrcL.asU64());
2172  (void)MTracker->readReg(DstSubReg);
2173  LocIdx DstL = MTracker->getRegMLoc(DstSubReg);
2174  assert(DstL.asU64());
2175  (void)DstL;
2176  ValueIDNum CpyValue = {SrcValue.getBlock(), SrcValue.getInst(), SrcL};
2177 
2178  MTracker->setReg(DstSubReg, CpyValue);
2179  }
2180 }
2181 
2182 bool InstrRefBasedLDV::isSpillInstruction(const MachineInstr &MI,
2183  MachineFunction *MF) {
2184  // TODO: Handle multiple stores folded into one.
2185  if (!MI.hasOneMemOperand())
2186  return false;
2187 
2188  if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII))
2189  return false; // This is not a spill instruction, since no valid size was
2190  // returned from either function.
2191 
2192  return true;
2193 }
2194 
2195 bool InstrRefBasedLDV::isLocationSpill(const MachineInstr &MI,
2196  MachineFunction *MF, unsigned &Reg) {
2197  if (!isSpillInstruction(MI, MF))
2198  return false;
2199 
2200  int FI;
2201  Reg = TII->isStoreToStackSlotPostFE(MI, FI);
2202  return Reg != 0;
2203 }
2204 
2206 InstrRefBasedLDV::isRestoreInstruction(const MachineInstr &MI,
2207  MachineFunction *MF, unsigned &Reg) {
2208  if (!MI.hasOneMemOperand())
2209  return None;
2210 
2211  // FIXME: Handle folded restore instructions with more than one memory
2212  // operand.
2213  if (MI.getRestoreSize(TII)) {
2214  Reg = MI.getOperand(0).getReg();
2215  return extractSpillBaseRegAndOffset(MI);
2216  }
2217  return None;
2218 }
2219 
2220 bool InstrRefBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI) {
2221  // XXX -- it's too difficult to implement VarLocBasedImpl's stack location
2222  // limitations under the new model. Therefore, when comparing them, compare
2223  // versions that don't attempt spills or restores at all.
2224  if (EmulateOldLDV)
2225  return false;
2226 
2227  MachineFunction *MF = MI.getMF();
2228  unsigned Reg;
2229  Optional<SpillLoc> Loc;
2230 
2231  LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump(););
2232 
2233  // First, if there are any DBG_VALUEs pointing at a spill slot that is
2234  // written to, terminate that variable location. The value in memory
2235  // will have changed. DbgEntityHistoryCalculator doesn't try to detect this.
2236  if (isSpillInstruction(MI, MF)) {
2237  Loc = extractSpillBaseRegAndOffset(MI);
2238 
2239  if (TTracker) {
2240  Optional<LocIdx> MLoc = MTracker->getSpillMLoc(*Loc);
2241  if (MLoc) {
2242  // Un-set this location before clobbering, so that we don't salvage
2243  // the variable location back to the same place.
2244  MTracker->setMLoc(*MLoc, ValueIDNum::EmptyValue);
2245  TTracker->clobberMloc(*MLoc, MI.getIterator());
2246  }
2247  }
2248  }
2249 
2250  // Try to recognise spill and restore instructions that may transfer a value.
2251  if (isLocationSpill(MI, MF, Reg)) {
2252  Loc = extractSpillBaseRegAndOffset(MI);
2253  auto ValueID = MTracker->readReg(Reg);
2254 
2255  // If the location is empty, produce a phi, signify it's the live-in value.
2256  if (ValueID.getLoc() == 0)
2257  ValueID = {CurBB, 0, MTracker->getRegMLoc(Reg)};
2258 
2259  MTracker->setSpill(*Loc, ValueID);
2260  auto OptSpillLocIdx = MTracker->getSpillMLoc(*Loc);
2261  assert(OptSpillLocIdx && "Spill slot set but has no LocIdx?");
2262  LocIdx SpillLocIdx = *OptSpillLocIdx;
2263 
2264  // Tell TransferTracker about this spill, produce DBG_VALUEs for it.
2265  if (TTracker)
2266  TTracker->transferMlocs(MTracker->getRegMLoc(Reg), SpillLocIdx,
2267  MI.getIterator());
2268  } else {
2269  if (!(Loc = isRestoreInstruction(MI, MF, Reg)))
2270  return false;
2271 
2272  // Is there a value to be restored?
2273  auto OptValueID = MTracker->readSpill(*Loc);
2274  if (OptValueID) {
2275  ValueIDNum ValueID = *OptValueID;
2276  LocIdx SpillLocIdx = *MTracker->getSpillMLoc(*Loc);
2277  // XXX -- can we recover sub-registers of this value? Until we can, first
2278  // overwrite all defs of the register being restored to.
2279  for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
2280  MTracker->defReg(*RAI, CurBB, CurInst);
2281 
2282  // Now override the reg we're restoring to.
2283  MTracker->setReg(Reg, ValueID);
2284 
2285  // Report this restore to the transfer tracker too.
2286  if (TTracker)
2287  TTracker->transferMlocs(SpillLocIdx, MTracker->getRegMLoc(Reg),
2288  MI.getIterator());
2289  } else {
2290  // There isn't anything in the location; not clear if this is a code path
2291  // that still runs. Def this register anyway just in case.
2292  for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
2293  MTracker->defReg(*RAI, CurBB, CurInst);
2294 
2295  // Force the spill slot to be tracked.
2296  LocIdx L = MTracker->getOrTrackSpillLoc(*Loc);
2297 
2298  // Set the restored value to be a machine phi number, signifying that it's
2299  // whatever the spills live-in value is in this block. Definitely has
2300  // a LocIdx due to the setSpill above.
2301  ValueIDNum ValueID = {CurBB, 0, L};
2302  MTracker->setReg(Reg, ValueID);
2303  MTracker->setSpill(*Loc, ValueID);
2304  }
2305  }
2306  return true;
2307 }
2308 
2309 bool InstrRefBasedLDV::transferRegisterCopy(MachineInstr &MI) {
2310  auto DestSrc = TII->isCopyInstr(MI);
2311  if (!DestSrc)
2312  return false;
2313 
2314  const MachineOperand *DestRegOp = DestSrc->Destination;
2315  const MachineOperand *SrcRegOp = DestSrc->Source;
2316 
2317  auto isCalleeSavedReg = [&](unsigned Reg) {
2318  for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
2319  if (CalleeSavedRegs.test(*RAI))
2320  return true;
2321  return false;
2322  };
2323 
2324  Register SrcReg = SrcRegOp->getReg();
2325  Register DestReg = DestRegOp->getReg();
2326 
2327  // Ignore identity copies. Yep, these make it as far as LiveDebugValues.
2328  if (SrcReg == DestReg)
2329  return true;
2330 
2331  // For emulating VarLocBasedImpl:
2332  // We want to recognize instructions where destination register is callee
2333  // saved register. If register that could be clobbered by the call is
2334  // included, there would be a great chance that it is going to be clobbered
2335  // soon. It is more likely that previous register, which is callee saved, is
2336  // going to stay unclobbered longer, even if it is killed.
2337  //
2338  // For InstrRefBasedImpl, we can track multiple locations per value, so
2339  // ignore this condition.
2340  if (EmulateOldLDV && !isCalleeSavedReg(DestReg))
2341  return false;
2342 
2343  // InstrRefBasedImpl only followed killing copies.
2344  if (EmulateOldLDV && !SrcRegOp->isKill())
2345  return false;
2346 
2347  // Copy MTracker info, including subregs if available.
2348  InstrRefBasedLDV::performCopy(SrcReg, DestReg);
2349 
2350  // Only produce a transfer of DBG_VALUE within a block where old LDV
2351  // would have. We might make use of the additional value tracking in some
2352  // other way, later.
2353  if (TTracker && isCalleeSavedReg(DestReg) && SrcRegOp->isKill())
2354  TTracker->transferMlocs(MTracker->getRegMLoc(SrcReg),
2355  MTracker->getRegMLoc(DestReg), MI.getIterator());
2356 
2357  // VarLocBasedImpl would quit tracking the old location after copying.
2358  if (EmulateOldLDV && SrcReg != DestReg)
2359  MTracker->defReg(SrcReg, CurBB, CurInst);
2360 
2361  // Finally, the copy might have clobbered variables based on the destination
2362  // register. Tell TTracker about it, in case a backup location exists.
2363  if (TTracker) {
2364  for (MCRegAliasIterator RAI(DestReg, TRI, true); RAI.isValid(); ++RAI) {
2365  LocIdx ClobberedLoc = MTracker->getRegMLoc(*RAI);
2366  TTracker->clobberMloc(ClobberedLoc, MI.getIterator(), false);
2367  }
2368  }
2369 
2370  return true;
2371 }
2372 
2373 /// Accumulate a mapping between each DILocalVariable fragment and other
2374 /// fragments of that DILocalVariable which overlap. This reduces work during
2375 /// the data-flow stage from "Find any overlapping fragments" to "Check if the
2376 /// known-to-overlap fragments are present".
2377 /// \param MI A previously unprocessed DEBUG_VALUE instruction to analyze for
2378 /// fragment usage.
2379 void InstrRefBasedLDV::accumulateFragmentMap(MachineInstr &MI) {
2380  DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(),
2381  MI.getDebugLoc()->getInlinedAt());
2382  FragmentInfo ThisFragment = MIVar.getFragmentOrDefault();
2383 
2384  // If this is the first sighting of this variable, then we are guaranteed
2385  // there are currently no overlapping fragments either. Initialize the set
2386  // of seen fragments, record no overlaps for the current one, and return.
2387  auto SeenIt = SeenFragments.find(MIVar.getVariable());
2388  if (SeenIt == SeenFragments.end()) {
2389  SmallSet<FragmentInfo, 4> OneFragment;
2390  OneFragment.insert(ThisFragment);
2391  SeenFragments.insert({MIVar.getVariable(), OneFragment});
2392 
2393  OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}});
2394  return;
2395  }
2396 
2397  // If this particular Variable/Fragment pair already exists in the overlap
2398  // map, it has already been accounted for.
2399  auto IsInOLapMap =
2400  OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}});
2401  if (!IsInOLapMap.second)
2402  return;
2403 
2404  auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;
2405  auto &AllSeenFragments = SeenIt->second;
2406 
2407  // Otherwise, examine all other seen fragments for this variable, with "this"
2408  // fragment being a previously unseen fragment. Record any pair of
2409  // overlapping fragments.
2410  for (auto &ASeenFragment : AllSeenFragments) {
2411  // Does this previously seen fragment overlap?
2412  if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) {
2413  // Yes: Mark the current fragment as being overlapped.
2414  ThisFragmentsOverlaps.push_back(ASeenFragment);
2415  // Mark the previously seen fragment as being overlapped by the current
2416  // one.
2417  auto ASeenFragmentsOverlaps =
2418  OverlapFragments.find({MIVar.getVariable(), ASeenFragment});
2419  assert(ASeenFragmentsOverlaps != OverlapFragments.end() &&
2420  "Previously seen var fragment has no vector of overlaps");
2421  ASeenFragmentsOverlaps->second.push_back(ThisFragment);
2422  }
2423  }
2424 
2425  AllSeenFragments.insert(ThisFragment);
2426 }
2427 
2428 void InstrRefBasedLDV::process(MachineInstr &MI, ValueIDNum **MLiveOuts,
2429  ValueIDNum **MLiveIns) {
2430  // Try to interpret an MI as a debug or transfer instruction. Only if it's
2431  // none of these should we interpret it's register defs as new value
2432  // definitions.
2433  if (transferDebugValue(MI))
2434  return;
2435  if (transferDebugInstrRef(MI, MLiveOuts, MLiveIns))
2436  return;
2437  if (transferDebugPHI(MI))
2438  return;
2439  if (transferRegisterCopy(MI))
2440  return;
2441  if (transferSpillOrRestoreInst(MI))
2442  return;
2443  transferRegisterDef(MI);
2444 }
2445 
2446 void InstrRefBasedLDV::produceMLocTransferFunction(
2448  unsigned MaxNumBlocks) {
2449  // Because we try to optimize around register mask operands by ignoring regs
2450  // that aren't currently tracked, we set up something ugly for later: RegMask
2451  // operands that are seen earlier than the first use of a register, still need
2452  // to clobber that register in the transfer function. But this information
2453  // isn't actively recorded. Instead, we track each RegMask used in each block,
2454  // and accumulated the clobbered but untracked registers in each block into
2455  // the following bitvector. Later, if new values are tracked, we can add
2456  // appropriate clobbers.
2457  SmallVector<BitVector, 32> BlockMasks;
2458  BlockMasks.resize(MaxNumBlocks);
2459 
2460  // Reserve one bit per register for the masks described above.
2461  unsigned BVWords = MachineOperand::getRegMaskSize(TRI->getNumRegs());
2462  for (auto &BV : BlockMasks)
2463  BV.resize(TRI->getNumRegs(), true);
2464 
2465  // Step through all instructions and inhale the transfer function.
2466  for (auto &MBB : MF) {
2467  // Object fields that are read by trackers to know where we are in the
2468  // function.
2469  CurBB = MBB.getNumber();
2470  CurInst = 1;
2471 
2472  // Set all machine locations to a PHI value. For transfer function
2473  // production only, this signifies the live-in value to the block.
2474  MTracker->reset();
2475  MTracker->setMPhis(CurBB);
2476 
2477  // Step through each instruction in this block.
2478  for (auto &MI : MBB) {
2479  process(MI);
2480  // Also accumulate fragment map.
2481  if (MI.isDebugValue())
2482  accumulateFragmentMap(MI);
2483 
2484  // Create a map from the instruction number (if present) to the
2485  // MachineInstr and its position.
2486  if (uint64_t InstrNo = MI.peekDebugInstrNum()) {
2487  auto InstrAndPos = std::make_pair(&MI, CurInst);
2488  auto InsertResult =
2489  DebugInstrNumToInstr.insert(std::make_pair(InstrNo, InstrAndPos));
2490 
2491  // There should never be duplicate instruction numbers.
2492  assert(InsertResult.second);
2493  (void)InsertResult;
2494  }
2495 
2496  ++CurInst;
2497  }
2498 
2499  // Produce the transfer function, a map of machine location to new value. If
2500  // any machine location has the live-in phi value from the start of the
2501  // block, it's live-through and doesn't need recording in the transfer
2502  // function.
2503  for (auto Location : MTracker->locations()) {
2504  LocIdx Idx = Location.Idx;
2505  ValueIDNum &P = Location.Value;
2506  if (P.isPHI() && P.getLoc() == Idx.asU64())
2507  continue;
2508 
2509  // Insert-or-update.
2510  auto &TransferMap = MLocTransfer[CurBB];
2511  auto Result = TransferMap.insert(std::make_pair(Idx.asU64(), P));
2512  if (!Result.second)
2513  Result.first->second = P;
2514  }
2515 
2516  // Accumulate any bitmask operands into the clobberred reg mask for this
2517  // block.
2518  for (auto &P : MTracker->Masks) {
2519  BlockMasks[CurBB].clearBitsNotInMask(P.first->getRegMask(), BVWords);
2520  }
2521  }
2522 
2523  // Compute a bitvector of all the registers that are tracked in this block.
2524  const TargetLowering *TLI = MF.getSubtarget().getTargetLowering();
2526  BitVector UsedRegs(TRI->getNumRegs());
2527  for (auto Location : MTracker->locations()) {
2528  unsigned ID = MTracker->LocIdxToLocID[Location.Idx];
2529  if (ID >= TRI->getNumRegs() || ID == SP)
2530  continue;
2531  UsedRegs.set(ID);
2532  }
2533 
2534  // Check that any regmask-clobber of a register that gets tracked, is not
2535  // live-through in the transfer function. It needs to be clobbered at the
2536  // very least.
2537  for (unsigned int I = 0; I < MaxNumBlocks; ++I) {
2538  BitVector &BV = BlockMasks[I];
2539  BV.flip();
2540  BV &= UsedRegs;
2541  // This produces all the bits that we clobber, but also use. Check that
2542  // they're all clobbered or at least set in the designated transfer
2543  // elem.
2544  for (unsigned Bit : BV.set_bits()) {
2545  unsigned ID = MTracker->getLocID(Bit, false);
2546  LocIdx Idx = MTracker->LocIDToLocIdx[ID];
2547  auto &TransferMap = MLocTransfer[I];
2548 
2549  // Install a value representing the fact that this location is effectively
2550  // written to in this block. As there's no reserved value, instead use
2551  // a value number that is never generated. Pick the value number for the
2552  // first instruction in the block, def'ing this location, which we know
2553  // this block never used anyway.
2554  ValueIDNum NotGeneratedNum = ValueIDNum(I, 1, Idx);
2555  auto Result =
2556  TransferMap.insert(std::make_pair(Idx.asU64(), NotGeneratedNum));
2557  if (!Result.second) {
2558  ValueIDNum &ValueID = Result.first->second;
2559  if (ValueID.getBlock() == I && ValueID.isPHI())
2560  // It was left as live-through. Set it to clobbered.
2561  ValueID = NotGeneratedNum;
2562  }
2563  }
2564  }
2565 }
2566 
2567 std::tuple<bool, bool>
2568 InstrRefBasedLDV::mlocJoin(MachineBasicBlock &MBB,
2570  ValueIDNum **OutLocs, ValueIDNum *InLocs) {
2571  LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
2572  bool Changed = false;
2573  bool DowngradeOccurred = false;
2574 
2575  // Collect predecessors that have been visited. Anything that hasn't been
2576  // visited yet is a backedge on the first iteration, and the meet of it's
2577  // lattice value for all locations will be unaffected.
2579  for (auto Pred : MBB.predecessors()) {
2580  if (Visited.count(Pred)) {
2581  BlockOrders.push_back(Pred);
2582  }
2583  }
2584 
2585  // Visit predecessors in RPOT order.
2586  auto Cmp = [&](const MachineBasicBlock *A, const MachineBasicBlock *B) {
2587  return BBToOrder.find(A)->second < BBToOrder.find(B)->second;
2588  };
2589  llvm::sort(BlockOrders, Cmp);
2590 
2591  // Skip entry block.
2592  if (BlockOrders.size() == 0)
2593  return std::tuple<bool, bool>(false, false);
2594 
2595  // Step through all machine locations, then look at each predecessor and
2596  // detect disagreements.
2597  unsigned ThisBlockRPO = BBToOrder.find(&MBB)->second;
2598  for (auto Location : MTracker->locations()) {
2599  LocIdx Idx = Location.Idx;
2600  // Pick out the first predecessors live-out value for this location. It's
2601  // guaranteed to be not a backedge, as we order by RPO.
2602  ValueIDNum BaseVal = OutLocs[BlockOrders[0]->getNumber()][Idx.asU64()];
2603 
2604  // Some flags for whether there's a disagreement, and whether it's a
2605  // disagreement with a backedge or not.
2606  bool Disagree = false;
2607  bool NonBackEdgeDisagree = false;
2608 
2609  // Loop around everything that wasn't 'base'.
2610  for (unsigned int I = 1; I < BlockOrders.size(); ++I) {
2611  auto *MBB = BlockOrders[I];
2612  if (BaseVal != OutLocs[MBB->getNumber()][Idx.asU64()]) {
2613  // Live-out of a predecessor disagrees with the first predecessor.
2614  Disagree = true;
2615 
2616  // Test whether it's a disagreemnt in the backedges or not.
2617  if (BBToOrder.find(MBB)->second < ThisBlockRPO) // might be self b/e
2618  NonBackEdgeDisagree = true;
2619  }
2620  }
2621 
2622  bool OverRide = false;
2623  if (Disagree && !NonBackEdgeDisagree) {
2624  // Only the backedges disagree. Consider demoting the livein
2625  // lattice value, as per the file level comment. The value we consider
2626  // demoting to is the value that the non-backedge predecessors agree on.
2627  // The order of values is that non-PHIs are \top, a PHI at this block
2628  // \bot, and phis between the two are ordered by their RPO number.
2629  // If there's no agreement, or we've already demoted to this PHI value
2630  // before, replace with a PHI value at this block.
2631 
2632  // Calculate order numbers: zero means normal def, nonzero means RPO
2633  // number.
2634  unsigned BaseBlockRPONum = BBNumToRPO[BaseVal.getBlock()] + 1;
2635  if (!BaseVal.isPHI())
2636  BaseBlockRPONum = 0;
2637 
2638  ValueIDNum &InLocID = InLocs[Idx.asU64()];
2639  unsigned InLocRPONum = BBNumToRPO[InLocID.getBlock()] + 1;
2640  if (!InLocID.isPHI())
2641  InLocRPONum = 0;
2642 
2643  // Should we ignore the disagreeing backedges, and override with the
2644  // value the other predecessors agree on (in "base")?
2645  unsigned ThisBlockRPONum = BBNumToRPO[MBB.getNumber()] + 1;
2646  if (BaseBlockRPONum > InLocRPONum && BaseBlockRPONum < ThisBlockRPONum) {
2647  // Override.
2648  OverRide = true;
2649  DowngradeOccurred = true;
2650  }
2651  }
2652  // else: if we disagree in the non-backedges, then this is definitely
2653  // a control flow merge where different values merge. Make it a PHI.
2654 
2655  // Generate a phi...
2656  ValueIDNum PHI = {(uint64_t)MBB.getNumber(), 0, Idx};
2657  ValueIDNum NewVal = (Disagree && !OverRide) ? PHI : BaseVal;
2658  if (InLocs[Idx.asU64()] != NewVal) {
2659  Changed |= true;
2660  InLocs[Idx.asU64()] = NewVal;
2661  }
2662  }
2663 
2664  // TODO: Reimplement NumInserted and NumRemoved.
2665  return std::tuple<bool, bool>(Changed, DowngradeOccurred);
2666 }
2667 
2668 void InstrRefBasedLDV::mlocDataflow(
2669  ValueIDNum **MInLocs, ValueIDNum **MOutLocs,
2670  SmallVectorImpl<MLocTransferMap> &MLocTransfer) {
2671  std::priority_queue<unsigned int, std::vector<unsigned int>,
2672  std::greater<unsigned int>>
2673  Worklist, Pending;
2674 
2675  // We track what is on the current and pending worklist to avoid inserting
2676  // the same thing twice. We could avoid this with a custom priority queue,
2677  // but this is probably not worth it.
2678  SmallPtrSet<MachineBasicBlock *, 16> OnPending, OnWorklist;
2679 
2680  // Initialize worklist with every block to be visited.
2681  for (unsigned int I = 0; I < BBToOrder.size(); ++I) {
2682  Worklist.push(I);
2683  OnWorklist.insert(OrderToBB[I]);
2684  }
2685 
2686  MTracker->reset();
2687 
2688  // Set inlocs for entry block -- each as a PHI at the entry block. Represents
2689  // the incoming value to the function.
2690  MTracker->setMPhis(0);
2691  for (auto Location : MTracker->locations())
2692  MInLocs[0][Location.Idx.asU64()] = Location.Value;
2693 
2695  while (!Worklist.empty() || !Pending.empty()) {
2696  // Vector for storing the evaluated block transfer function.
2698 
2699  while (!Worklist.empty()) {
2700  MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
2701  CurBB = MBB->getNumber();
2702  Worklist.pop();
2703 
2704  // Join the values in all predecessor blocks.
2705  bool InLocsChanged, DowngradeOccurred;
2706  std::tie(InLocsChanged, DowngradeOccurred) =
2707  mlocJoin(*MBB, Visited, MOutLocs, MInLocs[CurBB]);
2708  InLocsChanged |= Visited.insert(MBB).second;
2709 
2710  // If a downgrade occurred, book us in for re-examination on the next
2711  // iteration.
2712  if (DowngradeOccurred && OnPending.insert(MBB).second)
2713  Pending.push(BBToOrder[MBB]);
2714 
2715  // Don't examine transfer function if we've visited this loc at least
2716  // once, and inlocs haven't changed.
2717  if (!InLocsChanged)
2718  continue;
2719 
2720  // Load the current set of live-ins into MLocTracker.
2721  MTracker->loadFromArray(MInLocs[CurBB], CurBB);
2722 
2723  // Each element of the transfer function can be a new def, or a read of
2724  // a live-in value. Evaluate each element, and store to "ToRemap".
2725  ToRemap.clear();
2726  for (auto &P : MLocTransfer[CurBB]) {
2727  if (P.second.getBlock() == CurBB && P.second.isPHI()) {
2728  // This is a movement of whatever was live in. Read it.
2729  ValueIDNum NewID = MTracker->getNumAtPos(P.second.getLoc());
2730  ToRemap.push_back(std::make_pair(P.first, NewID));
2731  } else {
2732  // It's a def. Just set it.
2733  assert(P.second.getBlock() == CurBB);
2734  ToRemap.push_back(std::make_pair(P.first, P.second));
2735  }
2736  }
2737 
2738  // Commit the transfer function changes into mloc tracker, which
2739  // transforms the contents of the MLocTracker into the live-outs.
2740  for (auto &P : ToRemap)
2741  MTracker->setMLoc(P.first, P.second);
2742 
2743  // Now copy out-locs from mloc tracker into out-loc vector, checking
2744  // whether changes have occurred. These changes can have come from both
2745  // the transfer function, and mlocJoin.
2746  bool OLChanged = false;
2747  for (auto Location : MTracker->locations()) {
2748  OLChanged |= MOutLocs[CurBB][Location.Idx.asU64()] != Location.Value;
2749  MOutLocs[CurBB][Location.Idx.asU64()] = Location.Value;
2750  }
2751 
2752  MTracker->reset();
2753 
2754  // No need to examine successors again if out-locs didn't change.
2755  if (!OLChanged)
2756  continue;
2757 
2758  // All successors should be visited: put any back-edges on the pending
2759  // list for the next dataflow iteration, and any other successors to be
2760  // visited this iteration, if they're not going to be already.
2761  for (auto s : MBB->successors()) {
2762  // Does branching to this successor represent a back-edge?
2763  if (BBToOrder[s] > BBToOrder[MBB]) {
2764  // No: visit it during this dataflow iteration.
2765  if (OnWorklist.insert(s).second)
2766  Worklist.push(BBToOrder[s]);
2767  } else {
2768  // Yes: visit it on the next iteration.
2769  if (OnPending.insert(s).second)
2770  Pending.push(BBToOrder[s]);
2771  }
2772  }
2773  }
2774 
2775  Worklist.swap(Pending);
2776  std::swap(OnPending, OnWorklist);
2777  OnPending.clear();
2778  // At this point, pending must be empty, since it was just the empty
2779  // worklist
2780  assert(Pending.empty() && "Pending should be empty");
2781  }
2782 
2783  // Once all the live-ins don't change on mlocJoin(), we've reached a
2784  // fixedpoint.
2785 }
2786 
2787 bool InstrRefBasedLDV::vlocDowngradeLattice(
2788  const MachineBasicBlock &MBB, const DbgValue &OldLiveInLocation,
2789  const SmallVectorImpl<InValueT> &Values, unsigned CurBlockRPONum) {
2790  // Ranking value preference: see file level comment, the highest rank is
2791  // a plain def, followed by PHI values in reverse post-order. Numerically,
2792  // we assign all defs the rank '0', all PHIs their blocks RPO number plus
2793  // one, and consider the lowest value the highest ranked.
2794  int OldLiveInRank = BBNumToRPO[OldLiveInLocation.ID.getBlock()] + 1;
2795  if (!OldLiveInLocation.ID.isPHI())
2796  OldLiveInRank = 0;
2797 
2798  // Allow any unresolvable conflict to be over-ridden.
2799  if (OldLiveInLocation.Kind == DbgValue::NoVal) {
2800  // Although if it was an unresolvable conflict from _this_ block, then
2801  // all other seeking of downgrades and PHIs must have failed before hand.
2802  if (OldLiveInLocation.BlockNo == (unsigned)MBB.getNumber())
2803  return false;
2804  OldLiveInRank = INT_MIN;
2805  }
2806 
2807  auto &InValue = *Values[0].second;
2808 
2809  if (InValue.Kind == DbgValue::Const || InValue.Kind == DbgValue::NoVal)
2810  return false;
2811 
2812  unsigned ThisRPO = BBNumToRPO[InValue.ID.getBlock()];
2813  int ThisRank = ThisRPO + 1;
2814  if (!InValue.ID.isPHI())
2815  ThisRank = 0;
2816 
2817  // Too far down the lattice?
2818  if (ThisRPO >= CurBlockRPONum)
2819  return false;
2820 
2821  // Higher in the lattice than what we've already explored?
2822  if (ThisRank <= OldLiveInRank)
2823  return false;
2824 
2825  return true;
2826 }
2827 
2828 std::tuple<Optional<ValueIDNum>, bool> InstrRefBasedLDV::pickVPHILoc(
2829  MachineBasicBlock &MBB, const DebugVariable &Var, const LiveIdxT &LiveOuts,
2830  ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
2831  const SmallVectorImpl<MachineBasicBlock *> &BlockOrders) {
2832  // Collect a set of locations from predecessor where its live-out value can
2833  // be found.
2835  unsigned NumLocs = MTracker->getNumLocs();
2836  unsigned BackEdgesStart = 0;
2837 
2838  for (auto p : BlockOrders) {
2839  // Pick out where backedges start in the list of predecessors. Relies on
2840  // BlockOrders being sorted by RPO.
2841  if (BBToOrder[p] < BBToOrder[&MBB])
2842  ++BackEdgesStart;
2843 
2844  // For each predecessor, create a new set of locations.
2845  Locs.resize(Locs.size() + 1);
2846  unsigned ThisBBNum = p->getNumber();
2847  auto LiveOutMap = LiveOuts.find(p);
2848  if (LiveOutMap == LiveOuts.end())
2849  // This predecessor isn't in scope, it must have no live-in/live-out
2850  // locations.
2851  continue;
2852 
2853  auto It = LiveOutMap->second->find(Var);
2854  if (It == LiveOutMap->second->end())
2855  // There's no value recorded for this variable in this predecessor,
2856  // leave an empty set of locations.
2857  continue;
2858 
2859  const DbgValue &OutVal = It->second;
2860 
2861  if (OutVal.Kind == DbgValue::Const || OutVal.Kind == DbgValue::NoVal)
2862  // Consts and no-values cannot have locations we can join on.
2863  continue;
2864 
2865  assert(OutVal.Kind == DbgValue::Proposed || OutVal.Kind == DbgValue::Def);
2866  ValueIDNum ValToLookFor = OutVal.ID;
2867 
2868  // Search the live-outs of the predecessor for the specified value.
2869  for (unsigned int I = 0; I < NumLocs; ++I) {
2870  if (MOutLocs[ThisBBNum][I] == ValToLookFor)
2871  Locs.back().push_back(LocIdx(I));
2872  }
2873  }
2874 
2875  // If there were no locations at all, return an empty result.
2876  if (Locs.empty())
2877  return std::tuple<Optional<ValueIDNum>, bool>(None, false);
2878 
2879  // Lambda for seeking a common location within a range of location-sets.
2880  using LocsIt = SmallVector<SmallVector<LocIdx, 4>, 8>::iterator;
2881  auto SeekLocation =
2882  [&Locs](llvm::iterator_range<LocsIt> SearchRange) -> Optional<LocIdx> {
2883  // Starting with the first set of locations, take the intersection with
2884  // subsequent sets.
2885  SmallVector<LocIdx, 4> base = Locs[0];
2886  for (auto &S : SearchRange) {
2887  SmallVector<LocIdx, 4> new_base;
2888  std::set_intersection(base.begin(), base.end(), S.begin(), S.end(),
2889  std::inserter(new_base, new_base.begin()));
2890  base = new_base;
2891  }
2892  if (base.empty())
2893  return None;
2894 
2895  // We now have a set of LocIdxes that contain the right output value in
2896  // each of the predecessors. Pick the lowest; if there's a register loc,
2897  // that'll be it.
2898  return *base.begin();
2899  };
2900 
2901  // Search for a common location for all predecessors. If we can't, then fall
2902  // back to only finding a common location between non-backedge predecessors.
2903  bool ValidForAllLocs = true;
2904  auto TheLoc = SeekLocation(Locs);
2905  if (!TheLoc) {
2906  ValidForAllLocs = false;
2907  TheLoc =
2908  SeekLocation(make_range(Locs.begin(), Locs.begin() + BackEdgesStart));
2909  }
2910 
2911  if (!TheLoc)
2912  return std::tuple<Optional<ValueIDNum>, bool>(None, false);
2913 
2914  // Return a PHI-value-number for the found location.
2915  LocIdx L = *TheLoc;
2916  ValueIDNum PHIVal = {(unsigned)MBB.getNumber(), 0, L};
2917  return std::tuple<Optional<ValueIDNum>, bool>(PHIVal, ValidForAllLocs);
2918 }
2919 
2920 std::tuple<bool, bool> InstrRefBasedLDV::vlocJoin(
2921  MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs,
2922  SmallPtrSet<const MachineBasicBlock *, 16> *VLOCVisited, unsigned BBNum,
2923  const SmallSet<DebugVariable, 4> &AllVars, ValueIDNum **MOutLocs,
2924  ValueIDNum **MInLocs,
2928  bool DowngradeOccurred = false;
2929 
2930  // To emulate VarLocBasedImpl, process this block if it's not in scope but
2931  // _does_ assign a variable value. No live-ins for this scope are transferred
2932  // in though, so we can return immediately.
2933  if (InScopeBlocks.count(&MBB) == 0 && !ArtificialBlocks.count(&MBB)) {
2934  if (VLOCVisited)
2935  return std::tuple<bool, bool>(true, false);
2936  return std::tuple<bool, bool>(false, false);
2937  }
2938 
2939  LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
2940  bool Changed = false;
2941 
2942  // Find any live-ins computed in a prior iteration.
2943  auto ILSIt = VLOCInLocs.find(&MBB);
2944  assert(ILSIt != VLOCInLocs.end());
2945  auto &ILS = *ILSIt->second;
2946 
2947  // Order predecessors by RPOT order, for exploring them in that order.
2949 
2950  auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
2951  return BBToOrder[A] < BBToOrder[B];
2952  };
2953 
2954  llvm::sort(BlockOrders, Cmp);
2955 
2956  unsigned CurBlockRPONum = BBToOrder[&MBB];
2957 
2958  // Force a re-visit to loop heads in the first dataflow iteration.
2959  // FIXME: if we could "propose" Const values this wouldn't be needed,
2960  // because they'd need to be confirmed before being emitted.
2961  if (!BlockOrders.empty() &&
2962  BBToOrder[BlockOrders[BlockOrders.size() - 1]] >= CurBlockRPONum &&
2963  VLOCVisited)
2964  DowngradeOccurred = true;
2965 
2966  auto ConfirmValue = [&InLocsT](const DebugVariable &DV, DbgValue VR) {
2967  auto Result = InLocsT.insert(std::make_pair(DV, VR));
2968  (void)Result;
2969  assert(Result.second);
2970  };
2971 
2972  auto ConfirmNoVal = [&ConfirmValue, &MBB](const DebugVariable &Var, const DbgValueProperties &Properties) {
2973  DbgValue NoLocPHIVal(MBB.getNumber(), Properties, DbgValue::NoVal);
2974 
2975  ConfirmValue(Var, NoLocPHIVal);
2976  };
2977 
2978  // Attempt to join the values for each variable.
2979  for (auto &Var : AllVars) {
2980  // Collect all the DbgValues for this variable.
2981  SmallVector<InValueT, 8> Values;
2982  bool Bail = false;
2983  unsigned BackEdgesStart = 0;
2984  for (auto p : BlockOrders) {
2985  // If the predecessor isn't in scope / to be explored, we'll never be
2986  // able to join any locations.
2987  if (!BlocksToExplore.contains(p)) {
2988  Bail = true;
2989  break;
2990  }
2991 
2992  // Don't attempt to handle unvisited predecessors: they're implicitly
2993  // "unknown"s in the lattice.
2994  if (VLOCVisited && !VLOCVisited->count(p))
2995  continue;
2996 
2997  // If the predecessors OutLocs is absent, there's not much we can do.
2998  auto OL = VLOCOutLocs.find(p);
2999  if (OL == VLOCOutLocs.end()) {
3000  Bail = true;
3001  break;
3002  }
3003 
3004  // No live-out value for this predecessor also means we can't produce
3005  // a joined value.
3006  auto VIt = OL->second->find(Var);
3007  if (VIt == OL->second->end()) {
3008  Bail = true;
3009  break;
3010  }
3011 
3012  // Keep track of where back-edges begin in the Values vector. Relies on
3013  // BlockOrders being sorted by RPO.
3014  unsigned ThisBBRPONum = BBToOrder[p];
3015  if (ThisBBRPONum < CurBlockRPONum)
3016  ++BackEdgesStart;
3017 
3018  Values.push_back(std::make_pair(p, &VIt->second));
3019  }
3020 
3021  // If there were no values, or one of the predecessors couldn't have a
3022  // value, then give up immediately. It's not safe to produce a live-in
3023  // value.
3024  if (Bail || Values.size() == 0)
3025  continue;
3026 
3027  // Enumeration identifying the current state of the predecessors values.
3028  enum {
3029  Unset = 0,
3030  Agreed, // All preds agree on the variable value.
3031  PropDisagree, // All preds agree, but the value kind is Proposed in some.
3032  BEDisagree, // Only back-edges disagree on variable value.
3033  PHINeeded, // Non-back-edge predecessors have conflicing values.
3034  NoSolution // Conflicting Value metadata makes solution impossible.
3035  } OurState = Unset;
3036 
3037  // All (non-entry) blocks have at least one non-backedge predecessor.
3038  // Pick the variable value from the first of these, to compare against
3039  // all others.
3040  const DbgValue &FirstVal = *Values[0].second;
3041  const ValueIDNum &FirstID = FirstVal.ID;
3042 
3043  // Scan for variable values that can't be resolved: if they have different
3044  // DIExpressions, different indirectness, or are mixed constants /
3045  // non-constants.
3046  for (auto &V : Values) {
3047  if (V.second->Properties != FirstVal.Properties)
3048  OurState = NoSolution;
3049  if (V.second->Kind == DbgValue::Const && FirstVal.Kind != DbgValue::Const)
3050  OurState = NoSolution;
3051  }
3052 
3053  // Flags diagnosing _how_ the values disagree.
3054  bool NonBackEdgeDisagree = false;
3055  bool DisagreeOnPHINess = false;
3056  bool IDDisagree = false;
3057  bool Disagree = false;
3058  if (OurState == Unset) {
3059  for (auto &V : Values) {
3060  if (*V.second == FirstVal)
3061  continue; // No disagreement.
3062 
3063  Disagree = true;
3064 
3065  // Flag whether the value number actually diagrees.
3066  if (V.second->ID != FirstID)
3067  IDDisagree = true;
3068 
3069  // Distinguish whether disagreement happens in backedges or not.
3070  // Relies on Values (and BlockOrders) being sorted by RPO.
3071  unsigned ThisBBRPONum = BBToOrder[V.first];
3072  if (ThisBBRPONum < CurBlockRPONum)
3073  NonBackEdgeDisagree = true;
3074 
3075  // Is there a difference in whether the value is definite or only
3076  // proposed?
3077  if (V.second->Kind != FirstVal.Kind &&
3078  (V.second->Kind == DbgValue::Proposed ||
3079  V.second->Kind == DbgValue::Def) &&
3080  (FirstVal.Kind == DbgValue::Proposed ||
3081  FirstVal.Kind == DbgValue::Def))
3082  DisagreeOnPHINess = true;
3083  }
3084 
3085  // Collect those flags together and determine an overall state for
3086  // what extend the predecessors agree on a live-in value.
3087  if (!Disagree)
3088  OurState = Agreed;
3089  else if (!IDDisagree && DisagreeOnPHINess)
3090  OurState = PropDisagree;
3091  else if (!NonBackEdgeDisagree)
3092  OurState = BEDisagree;
3093  else
3094  OurState = PHINeeded;
3095  }
3096 
3097  // An extra indicator: if we only disagree on whether the value is a
3098  // Def, or proposed, then also flag whether that disagreement happens
3099  // in backedges only.
3100  bool PropOnlyInBEs = Disagree && !IDDisagree && DisagreeOnPHINess &&
3101  !NonBackEdgeDisagree && FirstVal.Kind == DbgValue::Def;
3102 
3103  const auto &Properties = FirstVal.Properties;
3104 
3105  auto OldLiveInIt = ILS.find(Var);
3106  const DbgValue *OldLiveInLocation =
3107  (OldLiveInIt != ILS.end()) ? &OldLiveInIt->second : nullptr;
3108 
3109  bool OverRide = false;
3110  if (OurState == BEDisagree && OldLiveInLocation) {
3111  // Only backedges disagree: we can consider downgrading. If there was a
3112  // previous live-in value, use it to work out whether the current
3113  // incoming value represents a lattice downgrade or not.
3114  OverRide =
3115  vlocDowngradeLattice(MBB, *OldLiveInLocation, Values, CurBlockRPONum);
3116  }
3117 
3118  // Use the current state of predecessor agreement and other flags to work
3119  // out what to do next. Possibilities include:
3120  // * Accept a value all predecessors agree on, or accept one that
3121  // represents a step down the exploration lattice,
3122  // * Use a PHI value number, if one can be found,
3123  // * Propose a PHI value number, and see if it gets confirmed later,
3124  // * Emit a 'NoVal' value, indicating we couldn't resolve anything.
3125  if (OurState == Agreed) {
3126  // Easiest solution: all predecessors agree on the variable value.
3127  ConfirmValue(Var, FirstVal);
3128  } else if (OurState == BEDisagree && OverRide) {
3129  // Only backedges disagree, and the other predecessors have produced
3130  // a new live-in value further down the exploration lattice.
3131  DowngradeOccurred = true;
3132  ConfirmValue(Var, FirstVal);
3133  } else if (OurState == PropDisagree) {
3134  // Predecessors agree on value, but some say it's only a proposed value.
3135  // Propagate it as proposed: unless it was proposed in this block, in
3136  // which case we're able to confirm the value.
3137  if (FirstID.getBlock() == (uint64_t)MBB.getNumber() && FirstID.isPHI()) {
3138  ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Def));
3139  } else if (PropOnlyInBEs) {
3140  // If only backedges disagree, a higher (in RPO) block confirmed this
3141  // location, and we need to propagate it into this loop.
3142  ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Def));
3143  } else {
3144  // Otherwise; a Def meeting a Proposed is still a Proposed.
3145  ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Proposed));
3146  }
3147  } else if ((OurState == PHINeeded || OurState == BEDisagree)) {
3148  // Predecessors disagree and can't be downgraded: this can only be
3149  // solved with a PHI. Use pickVPHILoc to go look for one.
3150  Optional<ValueIDNum> VPHI;
3151  bool AllEdgesVPHI = false;
3152  std::tie(VPHI, AllEdgesVPHI) =
3153  pickVPHILoc(MBB, Var, VLOCOutLocs, MOutLocs, MInLocs, BlockOrders);
3154 
3155  if (VPHI && AllEdgesVPHI) {
3156  // There's a PHI value that's valid for all predecessors -- we can use
3157  // it. If any of the non-backedge predecessors have proposed values
3158  // though, this PHI is also only proposed, until the predecessors are
3159  // confirmed.
3160  DbgValue::KindT K = DbgValue::Def;
3161  for (unsigned int I = 0; I < BackEdgesStart; ++I)
3162  if (Values[I].second->Kind == DbgValue::Proposed)
3163  K = DbgValue::Proposed;
3164 
3165  ConfirmValue(Var, DbgValue(*VPHI, Properties, K));
3166  } else if (VPHI) {
3167  // There's a PHI value, but it's only legal for backedges. Leave this
3168  // as a proposed PHI value: it might come back on the backedges,
3169  // and allow us to confirm it in the future.
3170  DbgValue NoBEValue = DbgValue(*VPHI, Properties, DbgValue::Proposed);
3171  ConfirmValue(Var, NoBEValue);
3172  } else {
3173  ConfirmNoVal(Var, Properties);
3174  }
3175  } else {
3176  // Otherwise: we don't know. Emit a "phi but no real loc" phi.
3177  ConfirmNoVal(Var, Properties);
3178  }
3179  }
3180 
3181  // Store newly calculated in-locs into VLOCInLocs, if they've changed.
3182  Changed = ILS != InLocsT;
3183  if (Changed)
3184  ILS = InLocsT;
3185 
3186  return std::tuple<bool, bool>(Changed, DowngradeOccurred);
3187 }
3188 
3189 void InstrRefBasedLDV::vlocDataflow(
3190  const LexicalScope *Scope, const DILocation *DILoc,
3191  const SmallSet<DebugVariable, 4> &VarsWeCareAbout,
3192  SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, LiveInsT &Output,
3193  ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
3194  SmallVectorImpl<VLocTracker> &AllTheVLocs) {
3195  // This method is much like mlocDataflow: but focuses on a single
3196  // LexicalScope at a time. Pick out a set of blocks and variables that are
3197  // to have their value assignments solved, then run our dataflow algorithm
3198  // until a fixedpoint is reached.
3199  std::priority_queue<unsigned int, std::vector<unsigned int>,
3200  std::greater<unsigned int>>
3201  Worklist, Pending;
3202  SmallPtrSet<MachineBasicBlock *, 16> OnWorklist, OnPending;
3203 
3204  // The set of blocks we'll be examining.
3206 
3207  // The order in which to examine them (RPO).
3209 
3210  // RPO ordering function.
3211  auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
3212  return BBToOrder[A] < BBToOrder[B];
3213  };
3214 
3215  LS.getMachineBasicBlocks(DILoc, BlocksToExplore);
3216 
3217  // A separate container to distinguish "blocks we're exploring" versus
3218  // "blocks that are potentially in scope. See comment at start of vlocJoin.
3219  SmallPtrSet<const MachineBasicBlock *, 8> InScopeBlocks = BlocksToExplore;
3220 
3221  // Old LiveDebugValues tracks variable locations that come out of blocks
3222  // not in scope, where DBG_VALUEs occur. This is something we could
3223  // legitimately ignore, but lets allow it for now.
3224  if (EmulateOldLDV)
3225  BlocksToExplore.insert(AssignBlocks.begin(), AssignBlocks.end());
3226 
3227  // We also need to propagate variable values through any artificial blocks
3228  // that immediately follow blocks in scope.
3230 
3231  // Helper lambda: For a given block in scope, perform a depth first search
3232  // of all the artificial successors, adding them to the ToAdd collection.
3233  auto AccumulateArtificialBlocks =
3234  [this, &ToAdd, &BlocksToExplore,
3235  &InScopeBlocks](const MachineBasicBlock *MBB) {
3236  // Depth-first-search state: each node is a block and which successor
3237  // we're currently exploring.
3238  SmallVector<std::pair<const MachineBasicBlock *,
3240  8>
3241  DFS;
3242 
3243  // Find any artificial successors not already tracked.
3244  for (auto *succ : MBB->successors()) {
3245  if (BlocksToExplore.count(succ) || InScopeBlocks.count(succ))
3246  continue;
3247  if (!ArtificialBlocks.count(succ))
3248  continue;
3249  DFS.push_back(std::make_pair(succ, succ->succ_begin()));
3250  ToAdd.insert(succ);
3251  }
3252 
3253  // Search all those blocks, depth first.
3254  while (!DFS.empty()) {
3255  const MachineBasicBlock *CurBB = DFS.back().first;
3256  MachineBasicBlock::const_succ_iterator &CurSucc = DFS.back().second;
3257  // Walk back if we've explored this blocks successors to the end.
3258  if (CurSucc == CurBB->succ_end()) {
3259  DFS.pop_back();
3260  continue;
3261  }
3262 
3263  // If the current successor is artificial and unexplored, descend into
3264  // it.
3265  if (!ToAdd.count(*CurSucc) && ArtificialBlocks.count(*CurSucc)) {
3266  DFS.push_back(std::make_pair(*CurSucc, (*CurSucc)->succ_begin()));
3267  ToAdd.insert(*CurSucc);
3268  continue;
3269  }
3270 
3271  ++CurSucc;
3272  }
3273  };
3274 
3275  // Search in-scope blocks and those containing a DBG_VALUE from this scope
3276  // for artificial successors.
3277  for (auto *MBB : BlocksToExplore)
3278  AccumulateArtificialBlocks(MBB);
3279  for (auto *MBB : InScopeBlocks)
3280  AccumulateArtificialBlocks(MBB);
3281 
3282  BlocksToExplore.insert(ToAdd.begin(), ToAdd.end());
3283  InScopeBlocks.insert(ToAdd.begin(), ToAdd.end());
3284 
3285  // Single block scope: not interesting! No propagation at all. Note that
3286  // this could probably go above ArtificialBlocks without damage, but
3287  // that then produces output differences from original-live-debug-values,
3288  // which propagates from a single block into many artificial ones.
3289  if (BlocksToExplore.size() == 1)
3290  return;
3291 
3292  // Picks out relevants blocks RPO order and sort them.
3293  for (auto *MBB : BlocksToExplore)
3294  BlockOrders.push_back(const_cast<MachineBasicBlock *>(MBB));
3295 
3296  llvm::sort(BlockOrders, Cmp);
3297  unsigned NumBlocks = BlockOrders.size();
3298 
3299  // Allocate some vectors for storing the live ins and live outs. Large.
3300  SmallVector<DenseMap<DebugVariable, DbgValue>, 32> LiveIns, LiveOuts;
3301  LiveIns.resize(NumBlocks);
3302  LiveOuts.resize(NumBlocks);
3303 
3304  // Produce by-MBB indexes of live-in/live-outs, to ease lookup within
3305  // vlocJoin.
3306  LiveIdxT LiveOutIdx, LiveInIdx;
3307  LiveOutIdx.reserve(NumBlocks);
3308  LiveInIdx.reserve(NumBlocks);
3309  for (unsigned I = 0; I < NumBlocks; ++I) {
3310  LiveOutIdx[BlockOrders[I]] = &LiveOuts[I];
3311  LiveInIdx[BlockOrders[I]] = &LiveIns[I];
3312  }
3313 
3314  for (auto *MBB : BlockOrders) {
3315  Worklist.push(BBToOrder[MBB]);
3316  OnWorklist.insert(MBB);
3317  }
3318 
3319  // Iterate over all the blocks we selected, propagating variable values.
3320  bool FirstTrip = true;
3322  while (!Worklist.empty() || !Pending.empty()) {
3323  while (!Worklist.empty()) {
3324  auto *MBB = OrderToBB[Worklist.top()];
3325  CurBB = MBB->getNumber();
3326  Worklist.pop();
3327 
3328  DenseMap<DebugVariable, DbgValue> JoinedInLocs;
3329 
3330  // Join values from predecessors. Updates LiveInIdx, and writes output
3331  // into JoinedInLocs.
3332  bool InLocsChanged, DowngradeOccurred;
3333  std::tie(InLocsChanged, DowngradeOccurred) = vlocJoin(
3334  *MBB, LiveOutIdx, LiveInIdx, (FirstTrip) ? &VLOCVisited : nullptr,
3335  CurBB, VarsWeCareAbout, MOutLocs, MInLocs, InScopeBlocks,
3336  BlocksToExplore, JoinedInLocs);
3337 
3338  bool FirstVisit = VLOCVisited.insert(MBB).second;
3339 
3340  // Always explore transfer function if inlocs changed, or if we've not
3341  // visited this block before.
3342  InLocsChanged |= FirstVisit;
3343 
3344  // If a downgrade occurred, book us in for re-examination on the next
3345  // iteration.
3346  if (DowngradeOccurred && OnPending.insert(MBB).second)
3347  Pending.push(BBToOrder[MBB]);
3348 
3349  if (!InLocsChanged)
3350  continue;
3351 
3352  // Do transfer function.
3353  auto &VTracker = AllTheVLocs[MBB->getNumber()];
3354  for (auto &Transfer : VTracker.Vars) {
3355  // Is this var we're mangling in this scope?
3356  if (VarsWeCareAbout.count(Transfer.first)) {
3357  // Erase on empty transfer (DBG_VALUE $noreg).
3358  if (Transfer.second.Kind == DbgValue::Undef) {
3359  JoinedInLocs.erase(Transfer.first);
3360  } else {
3361  // Insert new variable value; or overwrite.
3362  auto NewValuePair = std::make_pair(Transfer.first, Transfer.second);
3363  auto Result = JoinedInLocs.insert(NewValuePair);
3364  if (!Result.second)
3365  Result.first->second = Transfer.second;
3366  }
3367  }
3368  }
3369 
3370  // Did the live-out locations change?
3371  bool OLChanged = JoinedInLocs != *LiveOutIdx[MBB];
3372 
3373  // If they haven't changed, there's no need to explore further.
3374  if (!OLChanged)
3375  continue;
3376 
3377  // Commit to the live-out record.
3378  *LiveOutIdx[MBB] = JoinedInLocs;
3379 
3380  // We should visit all successors. Ensure we'll visit any non-backedge
3381  // successors during this dataflow iteration; book backedge successors
3382  // to be visited next time around.
3383  for (auto s : MBB->successors()) {
3384  // Ignore out of scope / not-to-be-explored successors.
3385  if (LiveInIdx.find(s) == LiveInIdx.end())
3386  continue;
3387 
3388  if (BBToOrder[s] > BBToOrder[MBB]) {
3389  if (OnWorklist.insert(s).second)
3390  Worklist.push(BBToOrder[s]);
3391  } else if (OnPending.insert(s).second && (FirstTrip || OLChanged)) {
3392  Pending.push(BBToOrder[s]);
3393  }
3394  }
3395  }
3396  Worklist.swap(Pending);
3397  std::swap(OnWorklist, OnPending);
3398  OnPending.clear();
3399  assert(Pending.empty());
3400  FirstTrip = false;
3401  }
3402 
3403  // Dataflow done. Now what? Save live-ins. Ignore any that are still marked
3404  // as being variable-PHIs, because those did not have their machine-PHI
3405  // value confirmed. Such variable values are places that could have been
3406  // PHIs, but are not.
3407  for (auto *MBB : BlockOrders) {
3408  auto &VarMap = *LiveInIdx[MBB];
3409  for (auto &P : VarMap) {
3410  if (P.second.Kind == DbgValue::Proposed ||
3411  P.second.Kind == DbgValue::NoVal)
3412  continue;
3413  Output[MBB->getNumber()].push_back(P);
3414  }
3415  }
3416 
3417  BlockOrders.clear();
3418  BlocksToExplore.clear();
3419 }
3420 
3421 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3422 void InstrRefBasedLDV::dump_mloc_transfer(
3423  const MLocTransferMap &mloc_transfer) const {
3424  for (auto &P : mloc_transfer) {
3425  std::string foo = MTracker->LocIdxToName(P.first);
3426  std::string bar = MTracker->IDAsString(P.second);
3427  dbgs() << "Loc " << foo << " --> " << bar << "\n";
3428  }
3429 }
3430 #endif
3431 
3432 void InstrRefBasedLDV::emitLocations(
3433  MachineFunction &MF, LiveInsT SavedLiveIns, ValueIDNum **MOutLocs,
3434  ValueIDNum **MInLocs, DenseMap<DebugVariable, unsigned> &AllVarsNumbering,
3435  const TargetPassConfig &TPC) {
3436  TTracker = new TransferTracker(TII, MTracker, MF, *TRI, CalleeSavedRegs, TPC);
3437  unsigned NumLocs = MTracker->getNumLocs();
3438 
3439  // For each block, load in the machine value locations and variable value
3440  // live-ins, then step through each instruction in the block. New DBG_VALUEs
3441  // to be inserted will be created along the way.
3442  for (MachineBasicBlock &MBB : MF) {
3443  unsigned bbnum = MBB.getNumber();
3444  MTracker->reset();
3445  MTracker->loadFromArray(MInLocs[bbnum], bbnum);
3446  TTracker->loadInlocs(MBB, MInLocs[bbnum], SavedLiveIns[MBB.getNumber()],
3447  NumLocs);
3448 
3449  CurBB = bbnum;
3450  CurInst = 1;
3451  for (auto &MI : MBB) {
3452  process(MI, MOutLocs, MInLocs);
3453  TTracker->checkInstForNewValues(CurInst, MI.getIterator());
3454  ++CurInst;
3455  }
3456  }
3457 
3458  // We have to insert DBG_VALUEs in a consistent order, otherwise they appeaer
3459  // in DWARF in different orders. Use the order that they appear when walking
3460  // through each block / each instruction, stored in AllVarsNumbering.
3461  auto OrderDbgValues = [&](const MachineInstr *A,
3462  const MachineInstr *B) -> bool {
3463  DebugVariable VarA(A->getDebugVariable(), A->getDebugExpression(),
3464  A->getDebugLoc()->getInlinedAt());
3465  DebugVariable VarB(B->getDebugVariable(), B->getDebugExpression(),
3466  B->getDebugLoc()->getInlinedAt());
3467  return AllVarsNumbering.find(VarA)->second <
3468  AllVarsNumbering.find(VarB)->second;
3469  };
3470 
3471  // Go through all the transfers recorded in the TransferTracker -- this is
3472  // both the live-ins to a block, and any movements of values that happen
3473  // in the middle.
3474  for (auto &P : TTracker->Transfers) {
3475  // Sort them according to appearance order.
3476  llvm::sort(P.Insts, OrderDbgValues);
3477  // Insert either before or after the designated point...
3478  if (P.MBB) {
3479  MachineBasicBlock &MBB = *P.MBB;
3480  for (auto *MI : P.Insts) {
3481  MBB.insert(P.Pos, MI);
3482  }
3483  } else {
3484  // Terminators, like tail calls, can clobber things. Don't try and place
3485  // transfers after them.
3486  if (P.Pos->isTerminator())
3487  continue;
3488 
3489  MachineBasicBlock &MBB = *P.Pos->getParent();
3490  for (auto *MI : P.Insts) {
3491  MBB.insertAfterBundle(P.Pos, MI);
3492  }
3493  }
3494  }
3495 }
3496 
3497 void InstrRefBasedLDV::initialSetup(MachineFunction &MF) {
3498  // Build some useful data structures.
3499  auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
3500  if (const DebugLoc &DL = MI.getDebugLoc())
3501  return DL.getLine() != 0;
3502  return false;
3503  };
3504  // Collect a set of all the artificial blocks.
3505  for (auto &MBB : MF)
3506  if (none_of(MBB.instrs(), hasNonArtificialLocation))
3507  ArtificialBlocks.insert(&MBB);
3508 
3509  // Compute mappings of block <=> RPO order.
3511  unsigned int RPONumber = 0;
3512  for (MachineBasicBlock *MBB : RPOT) {
3513  OrderToBB[RPONumber] = MBB;
3514  BBToOrder[MBB] = RPONumber;
3515  BBNumToRPO[MBB->getNumber()] = RPONumber;
3516  ++RPONumber;
3517  }
3518 
3519  // Order value substitutions by their "source" operand pair, for quick lookup.
3520  llvm::sort(MF.DebugValueSubstitutions);
3521 
3522 #ifdef EXPENSIVE_CHECKS
3523  // As an expensive check, test whether there are any duplicate substitution
3524  // sources in the collection.
3525  if (MF.DebugValueSubstitutions.size() > 2) {
3526  for (auto It = MF.DebugValueSubstitutions.begin();
3527  It != std::prev(MF.DebugValueSubstitutions.end()); ++It) {
3528  assert(It->Src != std::next(It)->Src && "Duplicate variable location "
3529  "substitution seen");
3530  }
3531  }
3532 #endif
3533 }
3534 
3535 /// Calculate the liveness information for the given machine function and
3536 /// extend ranges across basic blocks.
3537 bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC,
3538  unsigned InputBBLimit,
3539  unsigned InputDbgValLimit) {
3540  // No subprogram means this function contains no debuginfo.
3541  if (!MF.getFunction().getSubprogram())
3542  return false;
3543 
3544  LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
3545  this->TPC = TPC;
3546 
3547  TRI = MF.getSubtarget().getRegisterInfo();
3548  TII = MF.getSubtarget().getInstrInfo();
3549  TFI = MF.getSubtarget().getFrameLowering();
3550  TFI->getCalleeSaves(MF, CalleeSavedRegs);
3551  MFI = &MF.getFrameInfo();
3552  LS.initialize(MF);
3553 
3554  MTracker =
3555  new MLocTracker(MF, *TII, *TRI, *MF.getSubtarget().getTargetLowering());
3556  VTracker = nullptr;
3557  TTracker = nullptr;
3558 
3559  SmallVector<MLocTransferMap, 32> MLocTransfer;
3561  LiveInsT SavedLiveIns;
3562 
3563  int MaxNumBlocks = -1;
3564  for (auto &MBB : MF)
3565  MaxNumBlocks = std::max(MBB.getNumber(), MaxNumBlocks);
3566  assert(MaxNumBlocks >= 0);
3567  ++MaxNumBlocks;
3568 
3569  MLocTransfer.resize(MaxNumBlocks);
3570  vlocs.resize(MaxNumBlocks);
3571  SavedLiveIns.resize(MaxNumBlocks);
3572 
3573  initialSetup(MF);
3574 
3575  produceMLocTransferFunction(MF, MLocTransfer, MaxNumBlocks);
3576 
3577  // Allocate and initialize two array-of-arrays for the live-in and live-out
3578  // machine values. The outer dimension is the block number; while the inner
3579  // dimension is a LocIdx from MLocTracker.
3580  ValueIDNum **MOutLocs = new ValueIDNum *[MaxNumBlocks];
3581  ValueIDNum **MInLocs = new ValueIDNum *[MaxNumBlocks];
3582  unsigned NumLocs = MTracker->getNumLocs();
3583  for (int i = 0; i < MaxNumBlocks; ++i) {
3584  MOutLocs[i] = new ValueIDNum[NumLocs];
3585  MInLocs[i] = new ValueIDNum[NumLocs];
3586  }
3587 
3588  // Solve the machine value dataflow problem using the MLocTransfer function,
3589  // storing the computed live-ins / live-outs into the array-of-arrays. We use
3590  // both live-ins and live-outs for decision making in the variable value
3591  // dataflow problem.
3592  mlocDataflow(MInLocs, MOutLocs, MLocTransfer);
3593 
3594  // Patch up debug phi numbers, turning unknown block-live-in values into
3595  // either live-through machine values, or PHIs.
3596  for (auto &DBG_PHI : DebugPHINumToValue) {
3597  // Identify unresolved block-live-ins.
3598  ValueIDNum &Num = DBG_PHI.ValueRead;
3599  if (!Num.isPHI())
3600  continue;
3601 
3602  unsigned BlockNo = Num.getBlock();
3603  LocIdx LocNo = Num.getLoc();
3604  Num = MInLocs[BlockNo][LocNo.asU64()];
3605  }
3606  // Later, we'll be looking up ranges of instruction numbers.
3607  llvm::sort(DebugPHINumToValue);
3608 
3609  // Walk back through each block / instruction, collecting DBG_VALUE
3610  // instructions and recording what machine value their operands refer to.
3611  for (auto &OrderPair : OrderToBB) {
3612  MachineBasicBlock &MBB = *OrderPair.second;
3613  CurBB = MBB.getNumber();
3614  VTracker = &vlocs[CurBB];
3615  VTracker->MBB = &MBB;
3616  MTracker->loadFromArray(MInLocs[CurBB], CurBB);
3617  CurInst = 1;
3618  for (auto &MI : MBB) {
3619  process(MI, MOutLocs, MInLocs);
3620  ++CurInst;
3621  }
3622  MTracker->reset();
3623  }
3624 
3625  // Number all variables in the order that they appear, to be used as a stable
3626  // insertion order later.
3627  DenseMap<DebugVariable, unsigned> AllVarsNumbering;
3628 
3629  // Map from one LexicalScope to all the variables in that scope.
3631 
3632  // Map from One lexical scope to all blocks in that scope.
3634  ScopeToBlocks;
3635 
3636  // Store a DILocation that describes a scope.
3638 
3639  // To mirror old LiveDebugValues, enumerate variables in RPOT order. Otherwise
3640  // the order is unimportant, it just has to be stable.
3641  unsigned VarAssignCount = 0;
3642  for (unsigned int I = 0; I < OrderToBB.size(); ++I) {
3643  auto *MBB = OrderToBB[I];
3644  auto *VTracker = &vlocs[MBB->getNumber()];
3645  // Collect each variable with a DBG_VALUE in this block.
3646  for (auto &idx : VTracker->Vars) {
3647  const auto &Var = idx.first;
3648  const DILocation *ScopeLoc = VTracker->Scopes[Var];
3649  assert(ScopeLoc != nullptr);
3650  auto *Scope = LS.findLexicalScope(ScopeLoc);
3651 
3652  // No insts in scope -> shouldn't have been recorded.
3653  assert(Scope != nullptr);
3654 
3655  AllVarsNumbering.insert(std::make_pair(Var, AllVarsNumbering.size()));
3656  ScopeToVars[Scope].insert(Var);
3657  ScopeToBlocks[Scope].insert(VTracker->MBB);
3658  ScopeToDILocation[Scope] = ScopeLoc;
3659  ++VarAssignCount;
3660  }
3661  }
3662 
3663  bool Changed = false;
3664 
3665  // If we have an extremely large number of variable assignments and blocks,
3666  // bail out at this point. We've burnt some time doing analysis already,
3667  // however we should cut our losses.
3668  if ((unsigned)MaxNumBlocks > InputBBLimit &&
3669  VarAssignCount > InputDbgValLimit) {
3670  LLVM_DEBUG(dbgs() << "Disabling InstrRefBasedLDV: " << MF.getName()
3671  << " has " << MaxNumBlocks << " basic blocks and "
3672  << VarAssignCount
3673  << " variable assignments, exceeding limits.\n");
3674  } else {
3675  // Compute the extended ranges, iterating over scopes. There might be
3676  // something to be said for ordering them by size/locality, but that's for
3677  // the future. For each scope, solve the variable value problem, producing
3678  // a map of variables to values in SavedLiveIns.
3679  for (auto &P : ScopeToVars) {
3680  vlocDataflow(P.first, ScopeToDILocation[P.first], P.second,
3681  ScopeToBlocks[P.first], SavedLiveIns, MOutLocs, MInLocs,
3682  vlocs);
3683  }
3684 
3685  // Using the computed value locations and variable values for each block,
3686  // create the DBG_VALUE instructions representing the extended variable
3687  // locations.
3688  emitLocations(MF, SavedLiveIns, MOutLocs, MInLocs, AllVarsNumbering, *TPC);
3689 
3690  // Did we actually make any changes? If we created any DBG_VALUEs, then yes.
3691  Changed = TTracker->Transfers.size() != 0;
3692  }
3693 
3694  // Common clean-up of memory.
3695  for (int Idx = 0; Idx < MaxNumBlocks; ++Idx) {
3696  delete[] MOutLocs[Idx];
3697  delete[] MInLocs[Idx];
3698  }
3699  delete[] MOutLocs;
3700  delete[] MInLocs;
3701 
3702  delete MTracker;
3703  delete TTracker;
3704  MTracker = nullptr;
3705  VTracker = nullptr;
3706  TTracker = nullptr;
3707 
3708  ArtificialBlocks.clear();
3709  OrderToBB.clear();
3710  BBToOrder.clear();
3711  BBNumToRPO.clear();
3712  DebugInstrNumToInstr.clear();
3713  DebugPHINumToValue.clear();
3714 
3715  return Changed;
3716 }
3717 
3719  return new InstrRefBasedLDV();
3720 }
3721 
3722 namespace {
3723 class LDVSSABlock;
3724 class LDVSSAUpdater;
3725 
3726 // Pick a type to identify incoming block values as we construct SSA. We
3727 // can't use anything more robust than an integer unfortunately, as SSAUpdater
3728 // expects to zero-initialize the type.
3729 typedef uint64_t BlockValueNum;
3730 
3731 /// Represents an SSA PHI node for the SSA updater class. Contains the block
3732 /// this PHI is in, the value number it would have, and the expected incoming
3733 /// values from parent blocks.
3734 class LDVSSAPhi {
3735 public:
3737  LDVSSABlock *ParentBlock;
3738  BlockValueNum PHIValNum;
3739  LDVSSAPhi(BlockValueNum PHIValNum, LDVSSABlock *ParentBlock)
3740  : ParentBlock(ParentBlock), PHIValNum(PHIValNum) {}
3741 
3742  LDVSSABlock *getParent() { return ParentBlock; }
3743 };
3744 
3745 /// Thin wrapper around a block predecessor iterator. Only difference from a
3746 /// normal block iterator is that it dereferences to an LDVSSABlock.
3747 class LDVSSABlockIterator {
3748 public:
3750  LDVSSAUpdater &Updater;
3751 
3752  LDVSSABlockIterator(MachineBasicBlock::pred_iterator PredIt,
3753  LDVSSAUpdater &Updater)
3754  : PredIt(PredIt), Updater(Updater) {}
3755 
3756  bool operator!=(const LDVSSABlockIterator &OtherIt) const {
3757  return OtherIt.PredIt != PredIt;
3758  }
3759 
3760  LDVSSABlockIterator &operator++() {
3761  ++PredIt;
3762  return *this;
3763  }
3764 
3765  LDVSSABlock *operator*();
3766 };
3767 
3768 /// Thin wrapper around a block for SSA Updater interface. Necessary because
3769 /// we need to track the PHI value(s) that we may have observed as necessary
3770 /// in this block.
3771 class LDVSSABlock {
3772 public:
3774  LDVSSAUpdater &Updater;
3775  using PHIListT = SmallVector<LDVSSAPhi, 1>;
3776  /// List of PHIs in this block. There should only ever be one.
3777  PHIListT PHIList;
3778 
3779  LDVSSABlock(MachineBasicBlock &BB, LDVSSAUpdater &Updater)
3780  : BB(BB), Updater(Updater) {}
3781 
3782  LDVSSABlockIterator succ_begin() {
3783  return LDVSSABlockIterator(BB.succ_begin(), Updater);
3784  }
3785 
3786  LDVSSABlockIterator succ_end() {
3787  return LDVSSABlockIterator(BB.succ_end(), Updater);
3788  }
3789 
3790  /// SSAUpdater has requested a PHI: create that within this block record.
3791  LDVSSAPhi *newPHI(BlockValueNum Value) {
3792  PHIList.emplace_back(Value, this);
3793  return &PHIList.back();
3794  }
3795 
3796  /// SSAUpdater wishes to know what PHIs already exist in this block.
3797  PHIListT &phis() { return PHIList; }
3798 };
3799 
3800 /// Utility class for the SSAUpdater interface: tracks blocks, PHIs and values
3801 /// while SSAUpdater is exploring the CFG. It's passed as a handle / baton to
3802 // SSAUpdaterTraits<LDVSSAUpdater>.
3803 class LDVSSAUpdater {
3804 public:
3805  /// Map of value numbers to PHI records.
3807  /// Map of which blocks generate Undef values -- blocks that are not
3808  /// dominated by any Def.
3810  /// Map of machine blocks to our own records of them.
3812  /// Machine location where any PHI must occur.
3813  LocIdx Loc;
3814  /// Table of live-in machine value numbers for blocks / locations.
3815  ValueIDNum **MLiveIns;
3816 
3817  LDVSSAUpdater(LocIdx L, ValueIDNum **MLiveIns) : Loc(L), MLiveIns(MLiveIns) {}
3818 
3819  void reset() {
3820  for (auto &Block : BlockMap)
3821  delete Block.second;
3822 
3823  PHIs.clear();
3824  UndefMap.clear();
3825  BlockMap.clear();
3826  }
3827 
3828  ~LDVSSAUpdater() { reset(); }
3829 
3830  /// For a given MBB, create a wrapper block for it. Stores it in the
3831  /// LDVSSAUpdater block map.
3832  LDVSSABlock *getSSALDVBlock(MachineBasicBlock *BB) {
3833  auto it = BlockMap.find(BB);
3834  if (it == BlockMap.end()) {
3835  BlockMap[BB] = new LDVSSABlock(*BB, *this);
3836  it = BlockMap.find(BB);
3837  }
3838  return it->second;
3839  }
3840 
3841  /// Find the live-in value number for the given block. Looks up the value at
3842  /// the PHI location on entry.
3843  BlockValueNum getValue(LDVSSABlock *LDVBB) {
3844  return MLiveIns[LDVBB->BB.getNumber()][Loc.asU64()].asU64();
3845  }
3846 };
3847 
3848 LDVSSABlock *LDVSSABlockIterator::operator*() {
3849  return Updater.getSSALDVBlock(*PredIt);
3850 }
3851 
3852 #ifndef NDEBUG
3853 
3854 raw_ostream &operator<<(raw_ostream &out, const LDVSSAPhi &PHI) {
3855  out << "SSALDVPHI " << PHI.PHIValNum;
3856  return out;
3857 }
3858 
3859 #endif
3860 
3861 } // namespace
3862 
3863 namespace llvm {
3864 
3865 /// Template specialization to give SSAUpdater access to CFG and value
3866 /// information. SSAUpdater calls methods in these traits, passing in the
3867 /// LDVSSAUpdater object, to learn about blocks and the values they define.
3868 /// It also provides methods to create PHI nodes and track them.
3869 template <> class SSAUpdaterTraits<LDVSSAUpdater> {
3870 public:
3871  using BlkT = LDVSSABlock;
3872  using ValT = BlockValueNum;
3873  using PhiT = LDVSSAPhi;
3874  using BlkSucc_iterator = LDVSSABlockIterator;
3875 
3876  // Methods to access block successors -- dereferencing to our wrapper class.
3877  static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); }
3878  static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); }
3879 
3880  /// Iterator for PHI operands.
3881  class PHI_iterator {
3882  private:
3883  LDVSSAPhi *PHI;
3884  unsigned Idx;
3885 
3886  public:
3887  explicit PHI_iterator(LDVSSAPhi *P) // begin iterator
3888  : PHI(P), Idx(0) {}
3889  PHI_iterator(LDVSSAPhi *P, bool) // end iterator
3890  : PHI(P), Idx(PHI->IncomingValues.size()) {}
3891 
3892  PHI_iterator &operator++() {
3893  Idx++;
3894  return *this;
3895  }
3896  bool operator==(const PHI_iterator &X) const { return Idx == X.Idx; }
3897  bool operator!=(const PHI_iterator &X) const { return !operator==(X); }
3898 
3899  BlockValueNum getIncomingValue() { return PHI->IncomingValues[Idx].second; }
3900 
3901  LDVSSABlock *getIncomingBlock() { return PHI->IncomingValues[Idx].first; }
3902  };
3903 
3904  static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
3905 
3906  static inline PHI_iterator PHI_end(PhiT *PHI) {
3907  return PHI_iterator(PHI, true);
3908  }
3909 
3910  /// FindPredecessorBlocks - Put the predecessors of BB into the Preds
3911  /// vector.
3912  static void FindPredecessorBlocks(LDVSSABlock *BB,
3914  for (MachineBasicBlock::pred_iterator PI = BB->BB.pred_begin(),
3915  E = BB->BB.pred_end();
3916  PI != E; ++PI)
3917  Preds->push_back(BB->Updater.getSSALDVBlock(*PI));
3918  }
3919 
3920  /// GetUndefVal - Normally creates an IMPLICIT_DEF instruction with a new
3921  /// register. For LiveDebugValues, represents a block identified as not having
3922  /// any DBG_PHI predecessors.
3923  static BlockValueNum GetUndefVal(LDVSSABlock *BB, LDVSSAUpdater *Updater) {
3924  // Create a value number for this block -- it needs to be unique and in the
3925  // "undef" collection, so that we know it's not real. Use a number
3926  // representing a PHI into this block.
3927  BlockValueNum Num = ValueIDNum(BB->BB.getNumber(), 0, Updater->Loc).asU64();
3928  Updater->UndefMap[&BB->BB] = Num;
3929  return Num;
3930  }
3931 
3932  /// CreateEmptyPHI - Create a (representation of a) PHI in the given block.
3933  /// SSAUpdater will populate it with information about incoming values. The
3934  /// value number of this PHI is whatever the machine value number problem
3935  /// solution determined it to be. This includes non-phi values if SSAUpdater
3936  /// tries to create a PHI where the incoming values are identical.
3937  static BlockValueNum CreateEmptyPHI(LDVSSABlock *BB, unsigned NumPreds,
3938  LDVSSAUpdater *Updater) {
3939  BlockValueNum PHIValNum = Updater->getValue(BB);
3940  LDVSSAPhi *PHI = BB->newPHI(PHIValNum);
3941  Updater->PHIs[PHIValNum] = PHI;
3942  return PHIValNum;
3943  }
3944 
3945  /// AddPHIOperand - Add the specified value as an operand of the PHI for
3946  /// the specified predecessor block.
3947  static void AddPHIOperand(LDVSSAPhi *PHI, BlockValueNum Val, LDVSSABlock *Pred) {
3948  PHI->IncomingValues.push_back(std::make_pair(Pred, Val));
3949  }
3950 
3951  /// ValueIsPHI - Check if the instruction that defines the specified value
3952  /// is a PHI instruction.
3953  static LDVSSAPhi *ValueIsPHI(BlockValueNum Val, LDVSSAUpdater *Updater) {
3954  auto PHIIt = Updater->PHIs.find(Val);
3955  if (PHIIt == Updater->PHIs.end())
3956  return nullptr;
3957  return PHIIt->second;
3958  }
3959 
3960  /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
3961  /// operands, i.e., it was just added.
3962  static LDVSSAPhi *ValueIsNewPHI(BlockValueNum Val, LDVSSAUpdater *Updater) {
3963  LDVSSAPhi *PHI = ValueIsPHI(Val, Updater);
3964  if (PHI && PHI->IncomingValues.size() == 0)
3965  return PHI;
3966  return nullptr;
3967  }
3968 
3969  /// GetPHIValue - For the specified PHI instruction, return the value
3970  /// that it defines.
3971  static BlockValueNum GetPHIValue(LDVSSAPhi *PHI) { return PHI->PHIValNum; }
3972 };
3973 
3974 } // end namespace llvm
3975 
3976 Optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIs(MachineFunction &MF,
3977  ValueIDNum **MLiveOuts,
3978  ValueIDNum **MLiveIns,
3979  MachineInstr &Here,
3980  uint64_t InstrNum) {
3981  // Pick out records of DBG_PHI instructions that have been observed. If there
3982  // are none, then we cannot compute a value number.
3983  auto RangePair = std::equal_range(DebugPHINumToValue.begin(),
3984  DebugPHINumToValue.end(), InstrNum);
3985  auto LowerIt = RangePair.first;
3986  auto UpperIt = RangePair.second;
3987 
3988  // No DBG_PHI means there can be no location.
3989  if (LowerIt == UpperIt)
3990  return None;
3991 
3992  // If there's only one DBG_PHI, then that is our value number.
3993  if (std::distance(LowerIt, UpperIt) == 1)
3994  return LowerIt->ValueRead;
3995 
3996  auto DBGPHIRange = make_range(LowerIt, UpperIt);
3997 
3998  // Pick out the location (physreg, slot) where any PHIs must occur. It's
3999  // technically possible for us to merge values in different registers in each
4000  // block, but highly unlikely that LLVM will generate such code after register
4001  // allocation.
4002  LocIdx Loc = LowerIt->ReadLoc;
4003 
4004  // We have several DBG_PHIs, and a use position (the Here inst). All each
4005  // DBG_PHI does is identify a value at a program position. We can treat each
4006  // DBG_PHI like it's a Def of a value, and the use position is a Use of a
4007  // value, just like SSA. We use the bulk-standard LLVM SSA updater class to
4008  // determine which Def is used at the Use, and any PHIs that happen along
4009  // the way.
4010  // Adapted LLVM SSA Updater:
4011  LDVSSAUpdater Updater(Loc, MLiveIns);
4012  // Map of which Def or PHI is the current value in each block.
4014  // Set of PHIs that we have created along the way.
4015  SmallVector<LDVSSAPhi *, 8> CreatedPHIs;
4016 
4017  // Each existing DBG_PHI is a Def'd value under this model. Record these Defs
4018  // for the SSAUpdater.
4019  for (const auto &DBG_PHI : DBGPHIRange) {
4020  LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB);
4021  const ValueIDNum &Num = DBG_PHI.ValueRead;
4022  AvailableValues.insert(std::make_pair(Block, Num.asU64()));
4023  }
4024 
4025  LDVSSABlock *HereBlock = Updater.getSSALDVBlock(Here.getParent());
4026  const auto &AvailIt = AvailableValues.find(HereBlock);
4027  if (AvailIt != AvailableValues.end()) {
4028  // Actually, we already know what the value is -- the Use is in the same
4029  // block as the Def.
4030  return ValueIDNum::fromU64(AvailIt->second);
4031  }
4032 
4033  // Otherwise, we must use the SSA Updater. It will identify the value number
4034  // that we are to use, and the PHIs that must happen along the way.
4035  SSAUpdaterImpl<LDVSSAUpdater> Impl(&Updater, &AvailableValues, &CreatedPHIs);
4036  BlockValueNum ResultInt = Impl.GetValue(Updater.getSSALDVBlock(Here.getParent()));
4037  ValueIDNum Result = ValueIDNum::fromU64(ResultInt);
4038 
4039  // We have the number for a PHI, or possibly live-through value, to be used
4040  // at this Use. There are a number of things we have to check about it though:
4041  // * Does any PHI use an 'Undef' (like an IMPLICIT_DEF) value? If so, this
4042  // Use was not completely dominated by DBG_PHIs and we should abort.
4043  // * Are the Defs or PHIs clobbered in a block? SSAUpdater isn't aware that
4044  // we've left SSA form. Validate that the inputs to each PHI are the
4045  // expected values.
4046  // * Is a PHI we've created actually a merging of values, or are all the
4047  // predecessor values the same, leading to a non-PHI machine value number?
4048  // (SSAUpdater doesn't know that either). Remap validated PHIs into the
4049  // the ValidatedValues collection below to sort this out.
4050  DenseMap<LDVSSABlock *, ValueIDNum> ValidatedValues;
4051 
4052  // Define all the input DBG_PHI values in ValidatedValues.
4053  for (const auto &DBG_PHI : DBGPHIRange) {
4054  LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB);
4055  const ValueIDNum &Num = DBG_PHI.ValueRead;
4056  ValidatedValues.insert(std::make_pair(Block, Num));
4057  }
4058 
4059  // Sort PHIs to validate into RPO-order.
4060  SmallVector<LDVSSAPhi *, 8> SortedPHIs;
4061  for (auto &PHI : CreatedPHIs)
4062  SortedPHIs.push_back(PHI);
4063 
4064  std::sort(
4065  SortedPHIs.begin(), SortedPHIs.end(), [&](LDVSSAPhi *A, LDVSSAPhi *B) {
4066  return BBToOrder[&A->getParent()->BB] < BBToOrder[&B->getParent()->BB];
4067  });
4068 
4069  for (auto &PHI : SortedPHIs) {
4070  ValueIDNum ThisBlockValueNum =
4071  MLiveIns[PHI->ParentBlock->BB.getNumber()][Loc.asU64()];
4072 
4073  // Are all these things actually defined?
4074  for (auto &PHIIt : PHI->IncomingValues) {
4075  // Any undef input means DBG_PHIs didn't dominate the use point.
4076  if (Updater.UndefMap.find(&PHIIt.first->BB) != Updater.UndefMap.end())
4077  return None;
4078 
4079  ValueIDNum ValueToCheck;
4080  ValueIDNum *BlockLiveOuts = MLiveOuts[PHIIt.first->BB.getNumber()];
4081 
4082  auto VVal = ValidatedValues.find(PHIIt.first);
4083  if (VVal == ValidatedValues.end()) {
4084  // We cross a loop, and this is a backedge. LLVMs tail duplication
4085  // happens so late that DBG_PHI instructions should not be able to
4086  // migrate into loops -- meaning we can only be live-through this
4087  // loop.
4088  ValueToCheck = ThisBlockValueNum;
4089  } else {
4090  // Does the block have as a live-out, in the location we're examining,
4091  // the value that we expect? If not, it's been moved or clobbered.
4092  ValueToCheck = VVal->second;
4093  }
4094 
4095  if (BlockLiveOuts[Loc.asU64()] != ValueToCheck)
4096  return None;
4097  }
4098 
4099  // Record this value as validated.
4100  ValidatedValues.insert({PHI->ParentBlock, ThisBlockValueNum});
4101  }
4102 
4103  // All the PHIs are valid: we can return what the SSAUpdater said our value
4104  // number was.
4105  return Result;
4106 }
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:1296
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
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
CmpMode::FP
@ FP
llvm::SSAUpdaterTraits< LDVSSAUpdater >::ValT
BlockValueNum ValT
Definition: InstrRefBasedImpl.cpp:3872
llvm::TargetLoweringBase::getStackPointerRegisterToSaveRestore
Register getStackPointerRegisterToSaveRestore() const
If a physical register, this specifies the register that llvm.savestack/llvm.restorestack should save...
Definition: TargetLowering.h:1738
llvm::SSAUpdaterTraits< LDVSSAUpdater >::PHI_iterator::PHI_iterator
PHI_iterator(LDVSSAPhi *P, bool)
Definition: InstrRefBasedImpl.cpp:3889
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
llvm::SSAUpdaterTraits< LDVSSAUpdater >::PhiT
LDVSSAPhi PhiT
Definition: InstrRefBasedImpl.cpp:3873
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:491
llvm
---------------------— PointerInfo ------------------------------------—
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:3897
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
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:1561
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:3971
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
llvm::TargetFrameLowering
Information about stack frame layout on the target.
Definition: TargetFrameLowering.h:43
llvm::SharedLiveDebugValues::LDVImpl
Definition: LiveDebugValues.h:24
DebugInfoMetadata.h
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
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:1657
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::Register::id
unsigned id() const
Definition: Register.h:111
llvm::MachineBasicBlock::instrs
instr_range instrs()
Definition: MachineBasicBlock.h:263
TypeSize.h
llvm::lltok::bar
@ bar
Definition: LLToken.h:37
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
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::LexicalScope
LexicalScope - This class is used to track scope information.
Definition: LexicalScopes.h:44
llvm::Function::getSubprogram
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1532
llvm::MCRegisterInfo::getNumRegs
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Definition: MCRegisterInfo.h:491
llvm::BitVector::set_bits
iterator_range< const_set_bits_iterator > set_bits() const
Definition: BitVector.h:132
MachineBasicBlock.h
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:1912
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
DenseMap.h
llvm::IndexedMap::clear
void clear()
Definition: IndexedMap.h:63
Module.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:329
TargetInstrInfo.h
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
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::operator!=
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:1976
llvm::Optional
Definition: APInt.h:33
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::DILocalVariable::isParameter
bool isParameter() const
Definition: DebugInfoMetadata.h:3157
llvm::MapVector
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:876
STLExtras.h
llvm::MachineBasicBlock::back
MachineInstr & back()
Definition: MachineBasicBlock.h:248
llvm::DIExpression
DWARF expression.
Definition: DebugInfoMetadata.h:2586
llvm::DenseMap::swap
void swap(DenseMap &RHS)
Definition: DenseMap.h:758
llvm::MachineOperand::isFI
bool isFI() const
isFI - Tests if this is a MO_FrameIndex operand.
Definition: MachineOperand.h:331
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::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
llvm::MachineOperand::dump
void dump() const
Definition: MachineOperand.cpp:969
p
the resulting code requires compare and branches when and if * p
Definition: README.txt:396
llvm::UniqueVector::idFor
unsigned idFor(const T &Entry) const
idFor - return the ID for an existing entry.
Definition: UniqueVector.h:57
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1203
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:3923
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:3962
clear
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:233
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
llvm::MachineBasicBlock::push_back
void push_back(MachineInstr *MI)
Definition: MachineBasicBlock.h:843
TargetLowering.h
llvm::PseudoSourceValue::kind
unsigned kind() const
Definition: PseudoSourceValue.h:66
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
TargetMachine.h
llvm::DILocalVariable
Local variable.
Definition: DebugInfoMetadata.h:3097
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::DIExpression::ApplyOffset
@ ApplyOffset
Definition: DebugInfoMetadata.h:2793
llvm::MachineBasicBlock::succ_end
succ_iterator succ_end()
Definition: MachineBasicBlock.h:334
llvm::SSAUpdaterTraits< LDVSSAUpdater >::PHI_iterator::getIncomingBlock
LDVSSABlock * getIncomingBlock()
Definition: InstrRefBasedImpl.cpp:3901
llvm::MachineOperand::getRegMaskSize
static unsigned getRegMaskSize(unsigned NumRegs)
Returns number of elements needed for a regmask array.
Definition: MachineOperand.h:636
llvm::RegState::Undef
@ Undef
Value of the register doesn't matter.
Definition: MachineInstrBuilder.h:52
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:499
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
llvm::RegState::Debug
@ Debug
Register 'use' is for debugging purpose.
Definition: MachineInstrBuilder.h:56
llvm::TargetLowering
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Definition: TargetLowering.h:3189
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
llvm::IndexedMap
Definition: IndexedMap.h:29
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
SSAUpdaterImpl.h
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:46
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:3937
PseudoSourceValue.h
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")
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
UniqueVector.h
MachineInstrBundle.h
LexicalScopes.h
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::PseudoSourceValue::FixedStack
@ FixedStack
Definition: PseudoSourceValue.h:42
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
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
llvm::BitVector
Definition: BitVector.h:74
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:3947
llvm::PseudoSourceValue
Special value supplied for machine level alias analysis.
Definition: PseudoSourceValue.h:35
llvm::UniqueVector
UniqueVector - This class produces a sequential ID number (base 1) for each unique entry that is adde...
Definition: UniqueVector.h:24
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
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::MachineFrameInfo::isDeadObjectIndex
bool isDeadObjectIndex(int ObjectIdx) const
Returns true if the specified index corresponds to a dead object.
Definition: MachineFrameInfo.h:713
foo
< i32 > tmp foo
Definition: README.txt:383
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:3877
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:3887
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:626
llvm::cl::opt< bool >
llvm::MachineOperand::clobbersPhysReg
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
Definition: MachineOperand.h:617
llvm::SmallSet::count
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164
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
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
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
llvm::SmallPtrSetImpl::end
iterator end() const
Definition: SmallPtrSet.h:407
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:3904
llvm::TargetRegisterInfo::getFrameRegister
virtual Register getFrameRegister(const MachineFunction &MF) const =0
Debug information queries.
llvm::DenseMap
Definition: DenseMap.h:714
llvm::operator<
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:338
I
#define I(x, y, z)
Definition: MD5.cpp:59
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
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::empty
bool empty() const
Definition: DenseSet.h:80
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
MCRegisterInfo.h
llvm::DebugVariable
Identifies a unique instance of a variable.
Definition: DebugInfoMetadata.h:3659
DIBuilder.h
llvm::StackOffset::getScalable
static StackOffset getScalable(ScalarTy Scalable)
Definition: TypeSize.h:144
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:1024
llvm::BitVector::flip
BitVector & flip()
Definition: BitVector.h:423
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
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SSAUpdaterTraits< LDVSSAUpdater >::BlkSucc_end
static BlkSucc_iterator BlkSucc_end(BlkT *BB)
Definition: InstrRefBasedImpl.cpp:3878
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:642
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:225
base
therefore end up llgh r3 lr r0 br r14 but truncating the load would lh r3 br r14 Functions ret i64 and ought to be implemented ngr r0 br r14 but two address optimizations reverse the order of the AND and ngr r2 lgr r0 br r14 CodeGen SystemZ and ll has several examples of this Out of range displacements are usually handled by loading the full address into a register In many cases it would be better to create an anchor point instead E g i64 base
Definition: README.txt:125
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1974
llvm::MCSuperRegIterator
MCSuperRegIterator enumerates all super-registers of Reg.
Definition: MCRegisterInfo.h:641
llvm::MachineOperand::isRegMask
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
Definition: MachineOperand.h:345
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::MachineOperand::setIsDebug
void setIsDebug(bool Val=true)
Definition: MachineOperand.h:528
llvm::makeInstrRefBasedLiveDebugValues
LDVImpl * makeInstrRefBasedLiveDebugValues()
Definition: InstrRefBasedImpl.cpp:3718
llvm::MachineBasicBlock::instr_begin
instr_iterator instr_begin()
Definition: MachineBasicBlock.h:252
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
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::clear
void clear()
Definition: DenseSet.h:92
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1528
llvm::SSAUpdaterTraits< LDVSSAUpdater >::PHI_iterator::operator==
bool operator==(const PHI_iterator &X) const
Definition: InstrRefBasedImpl.cpp:3896
llvm::IndexedMap::grow
void grow(IndexT n)
Definition: IndexedMap.h:67
llvm::operator*
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2098
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:94
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
llvm::MapVector::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: MapVector.h:117
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:355
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:776
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
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:375
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
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::ValueMap
See the file comment.
Definition: ValueMap.h:85
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:3874
llvm::StackOffset::getFixed
static StackOffset getFixed(ScalarTy Fixed)
Definition: TypeSize.h:143
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
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:3892
llvm::MachineFunction::DebugSubstitution
Replacement definition for a debug instruction reference.
Definition: MachineFunction.h:463
llvm::SSAUpdaterTraits< LDVSSAUpdater >::PHI_end
static PHI_iterator PHI_end(PhiT *PHI)
Definition: InstrRefBasedImpl.cpp:3906
llvm::MDNode::getContext
LLVMContext & getContext() const
Definition: Metadata.h:962
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
llvm::BitVector::test
bool test(unsigned Idx) const
Definition: BitVector.h:447
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:592
llvm::TargetSubtargetInfo::getFrameLowering
virtual const TargetFrameLowering * getFrameLowering() const
Definition: TargetSubtargetInfo.h:93
llvm::TargetRegisterInfo::getRegSizeInBits
unsigned getRegSizeInBits(const TargetRegisterClass &RC) const
Return the size in bits of a register from class RC.
Definition: TargetRegisterInfo.h:276
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
llvm::X86::FirstMacroFusionInstKind::Cmp
@ Cmp
llvm::MachineBasicBlock::insert
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
Definition: MachineBasicBlock.cpp:1312
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
MachineFrameInfo.h
llvm::TargetFrameLowering::getFrameIndexReference
virtual StackOffset getFrameIndexReference(const MachineFunction &MF, int FI, Register &FrameReg) const
getFrameIndexReference - This method should return the base register and offset used to reference a f...
Definition: TargetFrameLoweringImpl.cpp:45
llvm::MachineOperand::getIndex
int getIndex() const
Definition: MachineOperand.h:557
llvm::AArch64CC::LS
@ LS
Definition: AArch64BaseInfo.h:264
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< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::size
unsigned size() const
Definition: DenseMap.h:100
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1488
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::SSAUpdaterTraits< LDVSSAUpdater >::PHI_iterator::getIncomingValue
BlockValueNum getIncomingValue()
Definition: InstrRefBasedImpl.cpp:3899
LiveDebugValues.h
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:290
llvm::SSAUpdaterTraits
Definition: MachineSSAUpdater.h:28
llvm::codeview::ModifierOptions::Const
@ Const
llvm::DIExpression::FragmentInfo
Holds the characteristics of one fragment of a larger variable.
Definition: DebugInfoMetadata.h:2750
llvm::MCSubRegIterator
MCSubRegIterator enumerates all sub-registers of Reg.
Definition: MCRegisterInfo.h:594
llvm::MCRegAliasIterator::isValid
bool isValid() const
Definition: MCRegisterInfo.h:805
llvm::MachineFrameInfo
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
Definition: MachineFrameInfo.h:107
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
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::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:484
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:3912
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
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::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::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
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
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::cl::desc
Definition: CommandLine.h:414
RegisterScavenging.h
raw_ostream.h
llvm::LexicalScopes
LexicalScopes - This class provides interface to collect and use lexical scoping information from mac...
Definition: LexicalScopes.h:141
MachineFunction.h
llvm::SmallPtrSetImpl::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:388
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::pdb::PDB_SymType::Block
@ Block
InitializePasses.h
llvm::SSAUpdaterTraits< LDVSSAUpdater >::BlkT
LDVSSABlock BlkT
Definition: InstrRefBasedImpl.cpp:3871
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
TargetRegisterInfo.h
llvm::UniqueVector::insert
unsigned insert(const T &Entry)
insert - Append entry to the vector if it doesn't already exist.
Definition: UniqueVector.h:40
Debug.h
llvm::DIExpression::EntryValue
@ EntryValue
Definition: DebugInfoMetadata.h:2797
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:3953
llvm::TargetRegisterInfo::prependOffsetExpression
DIExpression * prependOffsetExpression(const DIExpression *Expr, unsigned PrependFlags, const StackOffset &Offset) const
Prepends a DWARF expression for Offset to DIExpression Expr.
Definition: TargetRegisterInfo.cpp:649
llvm::MCRegAliasIterator
MCRegAliasIterator enumerates all registers aliasing Reg.
Definition: MCRegisterInfo.h:780
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1172
llvm::MachineOperand::isIdenticalTo
bool isIdenticalTo(const MachineOperand &Other) const
Returns true if this operand is identical to the specified operand except for liveness related flags ...
Definition: MachineOperand.cpp:282
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
SmallSet.h
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
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
llvm::DIExpression::fragmentsOverlap
static bool fragmentsOverlap(const FragmentInfo &A, const FragmentInfo &B)
Check if fragments overlap between a pair of FragmentInfos.
Definition: DebugInfoMetadata.h:2883
NUM_LOC_BITS
#define NUM_LOC_BITS
Definition: InstrRefBasedImpl.cpp:243
llvm::SSAUpdaterImpl
Definition: SSAUpdaterImpl.h:30