xref: /netbsd-src/external/apache2/llvm/dist/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp (revision 82d56013d7b633d116a93943de88e08335357a7c)
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"
150 #include "llvm/ADT/PostOrderIterator.h"
151 #include "llvm/ADT/SmallPtrSet.h"
152 #include "llvm/ADT/SmallSet.h"
153 #include "llvm/ADT/SmallVector.h"
154 #include "llvm/ADT/Statistic.h"
155 #include "llvm/ADT/UniqueVector.h"
156 #include "llvm/CodeGen/LexicalScopes.h"
157 #include "llvm/CodeGen/MachineBasicBlock.h"
158 #include "llvm/CodeGen/MachineFrameInfo.h"
159 #include "llvm/CodeGen/MachineFunction.h"
160 #include "llvm/CodeGen/MachineFunctionPass.h"
161 #include "llvm/CodeGen/MachineInstr.h"
162 #include "llvm/CodeGen/MachineInstrBuilder.h"
163 #include "llvm/CodeGen/MachineMemOperand.h"
164 #include "llvm/CodeGen/MachineOperand.h"
165 #include "llvm/CodeGen/PseudoSourceValue.h"
166 #include "llvm/CodeGen/RegisterScavenging.h"
167 #include "llvm/CodeGen/TargetFrameLowering.h"
168 #include "llvm/CodeGen/TargetInstrInfo.h"
169 #include "llvm/CodeGen/TargetLowering.h"
170 #include "llvm/CodeGen/TargetPassConfig.h"
171 #include "llvm/CodeGen/TargetRegisterInfo.h"
172 #include "llvm/CodeGen/TargetSubtargetInfo.h"
173 #include "llvm/Config/llvm-config.h"
174 #include "llvm/IR/DIBuilder.h"
175 #include "llvm/IR/DebugInfoMetadata.h"
176 #include "llvm/IR/DebugLoc.h"
177 #include "llvm/IR/Function.h"
178 #include "llvm/IR/Module.h"
179 #include "llvm/InitializePasses.h"
180 #include "llvm/MC/MCRegisterInfo.h"
181 #include "llvm/Pass.h"
182 #include "llvm/Support/Casting.h"
183 #include "llvm/Support/Compiler.h"
184 #include "llvm/Support/Debug.h"
185 #include "llvm/Support/TypeSize.h"
186 #include "llvm/Support/raw_ostream.h"
187 #include <algorithm>
188 #include <cassert>
189 #include <cstdint>
190 #include <functional>
191 #include <queue>
192 #include <tuple>
193 #include <utility>
194 #include <vector>
195 #include <limits.h>
196 #include <limits>
197 
198 #include "LiveDebugValues.h"
199 
200 using namespace llvm;
201 
202 #define DEBUG_TYPE "livedebugvalues"
203 
204 // Act more like the VarLoc implementation, by propagating some locations too
205 // far and ignoring some transfers.
206 static cl::opt<bool> EmulateOldLDV("emulate-old-livedebugvalues", cl::Hidden,
207                                    cl::desc("Act like old LiveDebugValues did"),
208                                    cl::init(false));
209 
210 // Rely on isStoreToStackSlotPostFE and similar to observe all stack spills.
211 static cl::opt<bool>
212     ObserveAllStackops("observe-all-stack-ops", cl::Hidden,
213                        cl::desc("Allow non-kill spill and restores"),
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;
operator ==__anon45b083930111::SpillLoc223   bool operator==(const SpillLoc &Other) const {
224     return std::make_pair(SpillBase, SpillOffset) ==
225            std::make_pair(Other.SpillBase, Other.SpillOffset);
226   }
operator <__anon45b083930111::SpillLoc227   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.
LocIdx()240   LocIdx() : Location(UINT_MAX) { }
241 
242 public:
243   #define NUM_LOC_BITS 24
LocIdx(unsigned L)244   LocIdx(unsigned L) : Location(L) {
245     assert(L < (1 << NUM_LOC_BITS) && "Machine locations must fit in 24 bits");
246   }
247 
MakeIllegalLoc()248   static LocIdx MakeIllegalLoc() {
249     return LocIdx();
250   }
251 
isIllegal() const252   bool isIllegal() const {
253     return Location == UINT_MAX;
254   }
255 
asU64() const256   uint64_t asU64() const {
257     return Location;
258   }
259 
operator ==(unsigned L) const260   bool operator==(unsigned L) const {
261     return Location == L;
262   }
263 
operator ==(const LocIdx & L) const264   bool operator==(const LocIdx &L) const {
265     return Location == L.Location;
266   }
267 
operator !=(unsigned L) const268   bool operator!=(unsigned L) const {
269     return !(*this == L);
270   }
271 
operator !=(const LocIdx & L) const272   bool operator!=(const LocIdx &L) const {
273     return !(*this == L);
274   }
275 
operator <(const LocIdx & Other) const276   bool operator<(const LocIdx &Other) const {
277     return Location < Other.Location;
278   }
279 };
280 
281 class LocIdxToIndexFunctor {
282 public:
283   using argument_type = LocIdx;
operator ()(const LocIdx & L) const284   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
ValueIDNum()308   ValueIDNum() : BlockNo(0xFFFFF),
309                  InstNo(0xFFFFF),
310                  LocNo(0xFFFFFF) { }
311 
ValueIDNum(uint64_t Block,uint64_t Inst,uint64_t Loc)312   ValueIDNum(uint64_t Block, uint64_t Inst, uint64_t Loc)
313     : BlockNo(Block), InstNo(Inst), LocNo(Loc) { }
314 
ValueIDNum(uint64_t Block,uint64_t Inst,LocIdx Loc)315   ValueIDNum(uint64_t Block, uint64_t Inst, LocIdx Loc)
316     : BlockNo(Block), InstNo(Inst), LocNo(Loc.asU64()) { }
317 
getBlock() const318   uint64_t getBlock() const { return BlockNo; }
getInst() const319   uint64_t getInst() const { return InstNo; }
getLoc() const320   uint64_t getLoc() const { return LocNo; }
isPHI() const321   bool isPHI() const { return InstNo == 0; }
322 
asU64() const323   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 
fromU64(uint64_t v)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 
operator <(const ValueIDNum & Other) const334   bool operator<(const ValueIDNum &Other) const {
335     return asU64() < Other.asU64();
336   }
337 
operator ==(const ValueIDNum & Other) const338   bool operator==(const ValueIDNum &Other) const {
339     return std::tie(BlockNo, InstNo, LocNo) ==
340            std::tie(Other.BlockNo, Other.InstNo, Other.LocNo);
341   }
342 
operator !=(const ValueIDNum & Other) const343   bool operator!=(const ValueIDNum &Other) const { return !(*this == Other); }
344 
asString(const std::string & mlocname) const345   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:
DbgValueProperties(const DIExpression * DIExpr,bool Indirect)366   DbgValueProperties(const DIExpression *DIExpr, bool Indirect)
367       : DIExpr(DIExpr), Indirect(Indirect) {}
368 
369   /// Extract properties from an existing DBG_VALUE instruction.
DbgValueProperties(const MachineInstr & MI)370   DbgValueProperties(const MachineInstr &MI) {
371     assert(MI.isDebugValue());
372     DIExpr = MI.getDebugExpression();
373     Indirect = MI.getOperand(1).isImm();
374   }
375 
operator ==(const DbgValueProperties & Other) const376   bool operator==(const DbgValueProperties &Other) const {
377     return std::tie(DIExpr, Indirect) == std::tie(Other.DIExpr, Other.Indirect);
378   }
379 
operator !=(const DbgValueProperties & Other) const380   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.
434   IndexedMap<unsigned, LocIdxToIndexFunctor> LocIdxToLocID;
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.
451   SmallVector<std::pair<const MachineOperand *, unsigned>, 32> Masks;
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:
value_type(LocIdx Idx,ValueIDNum & Value)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 
MLocIterator(LocToValueType & ValueMap,LocIdx Idx)469     MLocIterator(LocToValueType &ValueMap, LocIdx Idx)
470       : ValueMap(ValueMap), Idx(Idx) { }
471 
operator ==(const MLocIterator & Other) const472     bool operator==(const MLocIterator &Other) const {
473       assert(&ValueMap == &Other.ValueMap);
474       return Idx == Other.Idx;
475     }
476 
operator !=(const MLocIterator & Other) const477     bool operator!=(const MLocIterator &Other) const {
478       return !(*this == Other);
479     }
480 
operator ++()481     void operator++() {
482       Idx = LocIdx(Idx.asU64() + 1);
483     }
484 
operator *()485     value_type operator*() {
486       return value_type(Idx, ValueMap[LocIdx(Idx)]);
487     }
488   };
489 
MLocTracker(MachineFunction & MF,const TargetInstrInfo & TII,const TargetRegisterInfo & TRI,const TargetLowering & TLI)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).
503     Register SP = TLI.getStackPointerRegisterToSaveRestore();
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.
getLocID(Register RegOrSpill,bool isSpill)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.
getNumAtPos(LocIdx Idx) const517   ValueIDNum getNumAtPos(LocIdx Idx) const {
518     assert(Idx.asU64() < LocIdxToIDNum.size());
519     return LocIdxToIDNum[Idx];
520   }
521 
getNumLocs(void) const522   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).
setMPhis(unsigned NewCurBB)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.
loadFromArray(ValueIDNum * Locs,unsigned NewCurBB)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.
reset(void)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.
clear(void)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.
setMLoc(LocIdx L,ValueIDNum Num)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.
trackRegister(unsigned ID)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 
lookupOrTrackRegister(unsigned ID)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.
defReg(Register R,unsigned BB,unsigned Inst)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.
setReg(Register R,ValueIDNum ValueID)613   void setReg(Register R, ValueIDNum ValueID) {
614     unsigned ID = getLocID(R, false);
615     LocIdx Idx = lookupOrTrackRegister(ID);
616     LocIdxToIDNum[Idx] = ValueID;
617   }
618 
readReg(Register R)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).
wipeRegister(Register R)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.
getRegMLoc(Register R)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.
writeRegMask(const MachineOperand * MO,unsigned CurBB,unsigned InstID)644   void writeRegMask(const MachineOperand *MO, unsigned CurBB, unsigned InstID) {
645     // Ensure SP exists, so that we don't override it later.
646     Register SP = TLI.getStackPointerRegisterToSaveRestore();
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.
getOrTrackSpillLoc(SpillLoc L)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.
setSpill(SpillLoc L,ValueIDNum ValueID)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.
readSpill(SpillLoc L)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.
getSpillMLoc(SpillLoc L)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.
isSpill(LocIdx Idx) const707   bool isSpill(LocIdx Idx) const {
708     return LocIdxToLocID[Idx] >= NumRegs;
709   }
710 
begin()711   MLocIterator begin() {
712     return MLocIterator(LocIdxToIDNum, 0);
713   }
714 
end()715   MLocIterator end() {
716     return MLocIterator(LocIdxToIDNum, LocIdxToIDNum.size());
717   }
718 
719   /// Return a range over all locations currently tracked.
locations()720   iterator_range<MLocIterator> locations() {
721     return llvm::make_range(begin(), end());
722   }
723 
LocIdxToName(LocIdx Idx) const724   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 
IDAsString(const ValueIDNum & Num) const732   std::string IDAsString(const ValueIDNum &Num) const {
733     std::string DefName = LocIdxToName(Num.getLoc());
734     return Num.asString(DefName);
735   }
736 
737   LLVM_DUMP_METHOD
dump()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 
746   LLVM_DUMP_METHOD
dump_mloc_map()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.
emitLoc(Optional<LocIdx> MLoc,const DebugVariable & Var,const DbgValueProperties & Properties)757   MachineInstrBuilder emitLoc(Optional<LocIdx> MLoc, const DebugVariable &Var,
758                               const DbgValueProperties &Properties) {
759     DebugLoc DL = DILocation::get(Var.getVariable()->getContext(), 0, 0,
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();
774       Expr = TRI->prependOffsetExpression(Expr, DIExpression::ApplyOffset,
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 
DbgValue(const ValueIDNum & Val,const DbgValueProperties & Prop,KindT Kind)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 
DbgValue(unsigned BlockNo,const DbgValueProperties & Prop,KindT Kind)829   DbgValue(unsigned BlockNo, const DbgValueProperties &Prop, KindT Kind)
830     : BlockNo(BlockNo), Properties(Prop), Kind(Kind) {
831     assert(Kind == NoVal);
832   }
833 
DbgValue(const MachineOperand & MO,const DbgValueProperties & Prop,KindT Kind)834   DbgValue(const MachineOperand &MO, const DbgValueProperties &Prop, KindT Kind)
835     : MO(MO), Properties(Prop), Kind(Kind) {
836     assert(Kind == Const);
837   }
838 
DbgValue(const DbgValueProperties & Prop,KindT Kind)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 
dump(const MLocTracker * MTrack) const845   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 
operator ==(const DbgValue & Other) const862   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 
operator !=(const DbgValue & Other) const877   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 =
886     DenseMap<FragmentOfVar, SmallVector<DIExpression::FragmentInfo, 1>>;
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.
902   MapVector<DebugVariable, DbgValue> Vars;
903   DenseMap<DebugVariable, const DILocation *> Scopes;
904   MachineBasicBlock *MBB;
905 
906 public:
VLocTracker()907   VLocTracker() {}
908 
defVar(const MachineInstr & MI,const DbgValueProperties & Properties,Optional<ValueIDNum> ID)909   void defVar(const MachineInstr &MI, const DbgValueProperties &Properties,
910               Optional<ValueIDNum> ID) {
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 
defVar(const MachineInstr & MI,const MachineOperand & MO)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   /// This machine location tracker is assumed to always contain the up-to-date
960   /// value mapping for all machine locations. TransferTracker only reads
961   /// information from it. (XXX make it const?)
962   MLocTracker *MTracker;
963   MachineFunction &MF;
964 
965   /// Record of all changes in variable locations at a block position. Awkwardly
966   /// we allow inserting either before or after the point: MBB != nullptr
967   /// indicates it's before, otherwise after.
968   struct Transfer {
969     MachineBasicBlock::iterator Pos; /// Position to insert DBG_VALUes
970     MachineBasicBlock *MBB;          /// non-null if we should insert after.
971     SmallVector<MachineInstr *, 4> Insts; /// Vector of DBG_VALUEs to insert.
972   };
973 
974   typedef struct {
975     LocIdx Loc;
976     DbgValueProperties Properties;
977   } LocAndProperties;
978 
979   /// Collection of transfers (DBG_VALUEs) to be inserted.
980   SmallVector<Transfer, 32> Transfers;
981 
982   /// Local cache of what-value-is-in-what-LocIdx. Used to identify differences
983   /// between TransferTrackers view of variable locations and MLocTrackers. For
984   /// example, MLocTracker observes all clobbers, but TransferTracker lazily
985   /// does not.
986   std::vector<ValueIDNum> VarLocs;
987 
988   /// Map from LocIdxes to which DebugVariables are based that location.
989   /// Mantained while stepping through the block. Not accurate if
990   /// VarLocs[Idx] != MTracker->LocIdxToIDNum[Idx].
991   std::map<LocIdx, SmallSet<DebugVariable, 4>> ActiveMLocs;
992 
993   /// Map from DebugVariable to it's current location and qualifying meta
994   /// information. To be used in conjunction with ActiveMLocs to construct
995   /// enough information for the DBG_VALUEs for a particular LocIdx.
996   DenseMap<DebugVariable, LocAndProperties> ActiveVLocs;
997 
998   /// Temporary cache of DBG_VALUEs to be entered into the Transfers collection.
999   SmallVector<MachineInstr *, 4> PendingDbgValues;
1000 
1001   /// Record of a use-before-def: created when a value that's live-in to the
1002   /// current block isn't available in any machine location, but it will be
1003   /// defined in this block.
1004   struct UseBeforeDef {
1005     /// Value of this variable, def'd in block.
1006     ValueIDNum ID;
1007     /// Identity of this variable.
1008     DebugVariable Var;
1009     /// Additional variable properties.
1010     DbgValueProperties Properties;
1011   };
1012 
1013   /// Map from instruction index (within the block) to the set of UseBeforeDefs
1014   /// that become defined at that instruction.
1015   DenseMap<unsigned, SmallVector<UseBeforeDef, 1>> UseBeforeDefs;
1016 
1017   /// The set of variables that are in UseBeforeDefs and can become a location
1018   /// once the relevant value is defined. An element being erased from this
1019   /// collection prevents the use-before-def materializing.
1020   DenseSet<DebugVariable> UseBeforeDefVariables;
1021 
1022   const TargetRegisterInfo &TRI;
1023   const BitVector &CalleeSavedRegs;
1024 
TransferTracker(const TargetInstrInfo * TII,MLocTracker * MTracker,MachineFunction & MF,const TargetRegisterInfo & TRI,const BitVector & CalleeSavedRegs)1025   TransferTracker(const TargetInstrInfo *TII, MLocTracker *MTracker,
1026                   MachineFunction &MF, const TargetRegisterInfo &TRI,
1027                   const BitVector &CalleeSavedRegs)
1028       : TII(TII), MTracker(MTracker), MF(MF), TRI(TRI),
1029         CalleeSavedRegs(CalleeSavedRegs) {}
1030 
1031   /// Load object with live-in variable values. \p mlocs contains the live-in
1032   /// values in each machine location, while \p vlocs the live-in variable
1033   /// values. This method picks variable locations for the live-in variables,
1034   /// creates DBG_VALUEs and puts them in #Transfers, then prepares the other
1035   /// object fields to track variable locations as we step through the block.
1036   /// FIXME: could just examine mloctracker instead of passing in \p mlocs?
loadInlocs(MachineBasicBlock & MBB,ValueIDNum * MLocs,SmallVectorImpl<std::pair<DebugVariable,DbgValue>> & VLocs,unsigned NumLocs)1037   void loadInlocs(MachineBasicBlock &MBB, ValueIDNum *MLocs,
1038                   SmallVectorImpl<std::pair<DebugVariable, DbgValue>> &VLocs,
1039                   unsigned NumLocs) {
1040     ActiveMLocs.clear();
1041     ActiveVLocs.clear();
1042     VarLocs.clear();
1043     VarLocs.reserve(NumLocs);
1044     UseBeforeDefs.clear();
1045     UseBeforeDefVariables.clear();
1046 
1047     auto isCalleeSaved = [&](LocIdx L) {
1048       unsigned Reg = MTracker->LocIdxToLocID[L];
1049       if (Reg >= MTracker->NumRegs)
1050         return false;
1051       for (MCRegAliasIterator RAI(Reg, &TRI, true); RAI.isValid(); ++RAI)
1052         if (CalleeSavedRegs.test(*RAI))
1053           return true;
1054       return false;
1055     };
1056 
1057     // Map of the preferred location for each value.
1058     std::map<ValueIDNum, LocIdx> ValueToLoc;
1059 
1060     // Produce a map of value numbers to the current machine locs they live
1061     // in. When emulating VarLocBasedImpl, there should only be one
1062     // location; when not, we get to pick.
1063     for (auto Location : MTracker->locations()) {
1064       LocIdx Idx = Location.Idx;
1065       ValueIDNum &VNum = MLocs[Idx.asU64()];
1066       VarLocs.push_back(VNum);
1067       auto it = ValueToLoc.find(VNum);
1068       // In order of preference, pick:
1069       //  * Callee saved registers,
1070       //  * Other registers,
1071       //  * Spill slots.
1072       if (it == ValueToLoc.end() || MTracker->isSpill(it->second) ||
1073           (!isCalleeSaved(it->second) && isCalleeSaved(Idx.asU64()))) {
1074         // Insert, or overwrite if insertion failed.
1075         auto PrefLocRes = ValueToLoc.insert(std::make_pair(VNum, Idx));
1076         if (!PrefLocRes.second)
1077           PrefLocRes.first->second = Idx;
1078       }
1079     }
1080 
1081     // Now map variables to their picked LocIdxes.
1082     for (auto Var : VLocs) {
1083       if (Var.second.Kind == DbgValue::Const) {
1084         PendingDbgValues.push_back(
1085             emitMOLoc(Var.second.MO, Var.first, Var.second.Properties));
1086         continue;
1087       }
1088 
1089       // If the value has no location, we can't make a variable location.
1090       const ValueIDNum &Num = Var.second.ID;
1091       auto ValuesPreferredLoc = ValueToLoc.find(Num);
1092       if (ValuesPreferredLoc == ValueToLoc.end()) {
1093         // If it's a def that occurs in this block, register it as a
1094         // use-before-def to be resolved as we step through the block.
1095         if (Num.getBlock() == (unsigned)MBB.getNumber() && !Num.isPHI())
1096           addUseBeforeDef(Var.first, Var.second.Properties, Num);
1097         continue;
1098       }
1099 
1100       LocIdx M = ValuesPreferredLoc->second;
1101       auto NewValue = LocAndProperties{M, Var.second.Properties};
1102       auto Result = ActiveVLocs.insert(std::make_pair(Var.first, NewValue));
1103       if (!Result.second)
1104         Result.first->second = NewValue;
1105       ActiveMLocs[M].insert(Var.first);
1106       PendingDbgValues.push_back(
1107           MTracker->emitLoc(M, Var.first, Var.second.Properties));
1108     }
1109     flushDbgValues(MBB.begin(), &MBB);
1110   }
1111 
1112   /// Record that \p Var has value \p ID, a value that becomes available
1113   /// later in the function.
addUseBeforeDef(const DebugVariable & Var,const DbgValueProperties & Properties,ValueIDNum ID)1114   void addUseBeforeDef(const DebugVariable &Var,
1115                        const DbgValueProperties &Properties, ValueIDNum ID) {
1116     UseBeforeDef UBD = {ID, Var, Properties};
1117     UseBeforeDefs[ID.getInst()].push_back(UBD);
1118     UseBeforeDefVariables.insert(Var);
1119   }
1120 
1121   /// After the instruction at index \p Inst and position \p pos has been
1122   /// processed, check whether it defines a variable value in a use-before-def.
1123   /// If so, and the variable value hasn't changed since the start of the
1124   /// block, create a DBG_VALUE.
checkInstForNewValues(unsigned Inst,MachineBasicBlock::iterator pos)1125   void checkInstForNewValues(unsigned Inst, MachineBasicBlock::iterator pos) {
1126     auto MIt = UseBeforeDefs.find(Inst);
1127     if (MIt == UseBeforeDefs.end())
1128       return;
1129 
1130     for (auto &Use : MIt->second) {
1131       LocIdx L = Use.ID.getLoc();
1132 
1133       // If something goes very wrong, we might end up labelling a COPY
1134       // instruction or similar with an instruction number, where it doesn't
1135       // actually define a new value, instead it moves a value. In case this
1136       // happens, discard.
1137       if (MTracker->LocIdxToIDNum[L] != Use.ID)
1138         continue;
1139 
1140       // If a different debug instruction defined the variable value / location
1141       // since the start of the block, don't materialize this use-before-def.
1142       if (!UseBeforeDefVariables.count(Use.Var))
1143         continue;
1144 
1145       PendingDbgValues.push_back(MTracker->emitLoc(L, Use.Var, Use.Properties));
1146     }
1147     flushDbgValues(pos, nullptr);
1148   }
1149 
1150   /// Helper to move created DBG_VALUEs into Transfers collection.
flushDbgValues(MachineBasicBlock::iterator Pos,MachineBasicBlock * MBB)1151   void flushDbgValues(MachineBasicBlock::iterator Pos, MachineBasicBlock *MBB) {
1152     if (PendingDbgValues.size() > 0) {
1153       Transfers.push_back({Pos, MBB, PendingDbgValues});
1154       PendingDbgValues.clear();
1155     }
1156   }
1157 
1158   /// Change a variable value after encountering a DBG_VALUE inside a block.
redefVar(const MachineInstr & MI)1159   void redefVar(const MachineInstr &MI) {
1160     DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
1161                       MI.getDebugLoc()->getInlinedAt());
1162     DbgValueProperties Properties(MI);
1163 
1164     const MachineOperand &MO = MI.getOperand(0);
1165 
1166     // Ignore non-register locations, we don't transfer those.
1167     if (!MO.isReg() || MO.getReg() == 0) {
1168       auto It = ActiveVLocs.find(Var);
1169       if (It != ActiveVLocs.end()) {
1170         ActiveMLocs[It->second.Loc].erase(Var);
1171         ActiveVLocs.erase(It);
1172      }
1173       // Any use-before-defs no longer apply.
1174       UseBeforeDefVariables.erase(Var);
1175       return;
1176     }
1177 
1178     Register Reg = MO.getReg();
1179     LocIdx NewLoc = MTracker->getRegMLoc(Reg);
1180     redefVar(MI, Properties, NewLoc);
1181   }
1182 
1183   /// Handle a change in variable location within a block. Terminate the
1184   /// variables current location, and record the value it now refers to, so
1185   /// that we can detect location transfers later on.
redefVar(const MachineInstr & MI,const DbgValueProperties & Properties,Optional<LocIdx> OptNewLoc)1186   void redefVar(const MachineInstr &MI, const DbgValueProperties &Properties,
1187                 Optional<LocIdx> OptNewLoc) {
1188     DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
1189                       MI.getDebugLoc()->getInlinedAt());
1190     // Any use-before-defs no longer apply.
1191     UseBeforeDefVariables.erase(Var);
1192 
1193     // Erase any previous location,
1194     auto It = ActiveVLocs.find(Var);
1195     if (It != ActiveVLocs.end())
1196       ActiveMLocs[It->second.Loc].erase(Var);
1197 
1198     // If there _is_ no new location, all we had to do was erase.
1199     if (!OptNewLoc)
1200       return;
1201     LocIdx NewLoc = *OptNewLoc;
1202 
1203     // Check whether our local copy of values-by-location in #VarLocs is out of
1204     // date. Wipe old tracking data for the location if it's been clobbered in
1205     // the meantime.
1206     if (MTracker->getNumAtPos(NewLoc) != VarLocs[NewLoc.asU64()]) {
1207       for (auto &P : ActiveMLocs[NewLoc]) {
1208         ActiveVLocs.erase(P);
1209       }
1210       ActiveMLocs[NewLoc.asU64()].clear();
1211       VarLocs[NewLoc.asU64()] = MTracker->getNumAtPos(NewLoc);
1212     }
1213 
1214     ActiveMLocs[NewLoc].insert(Var);
1215     if (It == ActiveVLocs.end()) {
1216       ActiveVLocs.insert(
1217           std::make_pair(Var, LocAndProperties{NewLoc, Properties}));
1218     } else {
1219       It->second.Loc = NewLoc;
1220       It->second.Properties = Properties;
1221     }
1222   }
1223 
1224   /// Explicitly terminate variable locations based on \p mloc. Creates undef
1225   /// DBG_VALUEs for any variables that were located there, and clears
1226   /// #ActiveMLoc / #ActiveVLoc tracking information for that location.
clobberMloc(LocIdx MLoc,MachineBasicBlock::iterator Pos)1227   void clobberMloc(LocIdx MLoc, MachineBasicBlock::iterator Pos) {
1228     assert(MTracker->isSpill(MLoc));
1229     auto ActiveMLocIt = ActiveMLocs.find(MLoc);
1230     if (ActiveMLocIt == ActiveMLocs.end())
1231       return;
1232 
1233     VarLocs[MLoc.asU64()] = ValueIDNum::EmptyValue;
1234 
1235     for (auto &Var : ActiveMLocIt->second) {
1236       auto ActiveVLocIt = ActiveVLocs.find(Var);
1237       // Create an undef. We can't feed in a nullptr DIExpression alas,
1238       // so use the variables last expression. Pass None as the location.
1239       const DIExpression *Expr = ActiveVLocIt->second.Properties.DIExpr;
1240       DbgValueProperties Properties(Expr, false);
1241       PendingDbgValues.push_back(MTracker->emitLoc(None, Var, Properties));
1242       ActiveVLocs.erase(ActiveVLocIt);
1243     }
1244     flushDbgValues(Pos, nullptr);
1245 
1246     ActiveMLocIt->second.clear();
1247   }
1248 
1249   /// Transfer variables based on \p Src to be based on \p Dst. This handles
1250   /// both register copies as well as spills and restores. Creates DBG_VALUEs
1251   /// describing the movement.
transferMlocs(LocIdx Src,LocIdx Dst,MachineBasicBlock::iterator Pos)1252   void transferMlocs(LocIdx Src, LocIdx Dst, MachineBasicBlock::iterator Pos) {
1253     // Does Src still contain the value num we expect? If not, it's been
1254     // clobbered in the meantime, and our variable locations are stale.
1255     if (VarLocs[Src.asU64()] != MTracker->getNumAtPos(Src))
1256       return;
1257 
1258     // assert(ActiveMLocs[Dst].size() == 0);
1259     //^^^ Legitimate scenario on account of un-clobbered slot being assigned to?
1260     ActiveMLocs[Dst] = ActiveMLocs[Src];
1261     VarLocs[Dst.asU64()] = VarLocs[Src.asU64()];
1262 
1263     // For each variable based on Src; create a location at Dst.
1264     for (auto &Var : ActiveMLocs[Src]) {
1265       auto ActiveVLocIt = ActiveVLocs.find(Var);
1266       assert(ActiveVLocIt != ActiveVLocs.end());
1267       ActiveVLocIt->second.Loc = Dst;
1268 
1269       assert(Dst != 0);
1270       MachineInstr *MI =
1271           MTracker->emitLoc(Dst, Var, ActiveVLocIt->second.Properties);
1272       PendingDbgValues.push_back(MI);
1273     }
1274     ActiveMLocs[Src].clear();
1275     flushDbgValues(Pos, nullptr);
1276 
1277     // XXX XXX XXX "pretend to be old LDV" means dropping all tracking data
1278     // about the old location.
1279     if (EmulateOldLDV)
1280       VarLocs[Src.asU64()] = ValueIDNum::EmptyValue;
1281   }
1282 
emitMOLoc(const MachineOperand & MO,const DebugVariable & Var,const DbgValueProperties & Properties)1283   MachineInstrBuilder emitMOLoc(const MachineOperand &MO,
1284                                 const DebugVariable &Var,
1285                                 const DbgValueProperties &Properties) {
1286     DebugLoc DL = DILocation::get(Var.getVariable()->getContext(), 0, 0,
1287                                   Var.getVariable()->getScope(),
1288                                   const_cast<DILocation *>(Var.getInlinedAt()));
1289     auto MIB = BuildMI(MF, DL, TII->get(TargetOpcode::DBG_VALUE));
1290     MIB.add(MO);
1291     if (Properties.Indirect)
1292       MIB.addImm(0);
1293     else
1294       MIB.addReg(0);
1295     MIB.addMetadata(Var.getVariable());
1296     MIB.addMetadata(Properties.DIExpr);
1297     return MIB;
1298   }
1299 };
1300 
1301 class InstrRefBasedLDV : public LDVImpl {
1302 private:
1303   using FragmentInfo = DIExpression::FragmentInfo;
1304   using OptFragmentInfo = Optional<DIExpression::FragmentInfo>;
1305 
1306   // Helper while building OverlapMap, a map of all fragments seen for a given
1307   // DILocalVariable.
1308   using VarToFragments =
1309       DenseMap<const DILocalVariable *, SmallSet<FragmentInfo, 4>>;
1310 
1311   /// Machine location/value transfer function, a mapping of which locations
1312   /// are assigned which new values.
1313   using MLocTransferMap = std::map<LocIdx, ValueIDNum>;
1314 
1315   /// Live in/out structure for the variable values: a per-block map of
1316   /// variables to their values. XXX, better name?
1317   using LiveIdxT =
1318       DenseMap<const MachineBasicBlock *, DenseMap<DebugVariable, DbgValue> *>;
1319 
1320   using VarAndLoc = std::pair<DebugVariable, DbgValue>;
1321 
1322   /// Type for a live-in value: the predecessor block, and its value.
1323   using InValueT = std::pair<MachineBasicBlock *, DbgValue *>;
1324 
1325   /// Vector (per block) of a collection (inner smallvector) of live-ins.
1326   /// Used as the result type for the variable value dataflow problem.
1327   using LiveInsT = SmallVector<SmallVector<VarAndLoc, 8>, 8>;
1328 
1329   const TargetRegisterInfo *TRI;
1330   const TargetInstrInfo *TII;
1331   const TargetFrameLowering *TFI;
1332   BitVector CalleeSavedRegs;
1333   LexicalScopes LS;
1334   TargetPassConfig *TPC;
1335 
1336   /// Object to track machine locations as we step through a block. Could
1337   /// probably be a field rather than a pointer, as it's always used.
1338   MLocTracker *MTracker;
1339 
1340   /// Number of the current block LiveDebugValues is stepping through.
1341   unsigned CurBB;
1342 
1343   /// Number of the current instruction LiveDebugValues is evaluating.
1344   unsigned CurInst;
1345 
1346   /// Variable tracker -- listens to DBG_VALUEs occurring as InstrRefBasedImpl
1347   /// steps through a block. Reads the values at each location from the
1348   /// MLocTracker object.
1349   VLocTracker *VTracker;
1350 
1351   /// Tracker for transfers, listens to DBG_VALUEs and transfers of values
1352   /// between locations during stepping, creates new DBG_VALUEs when values move
1353   /// location.
1354   TransferTracker *TTracker;
1355 
1356   /// Blocks which are artificial, i.e. blocks which exclusively contain
1357   /// instructions without DebugLocs, or with line 0 locations.
1358   SmallPtrSet<const MachineBasicBlock *, 16> ArtificialBlocks;
1359 
1360   // Mapping of blocks to and from their RPOT order.
1361   DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
1362   DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
1363   DenseMap<unsigned, unsigned> BBNumToRPO;
1364 
1365   /// Pair of MachineInstr, and its 1-based offset into the containing block.
1366   using InstAndNum = std::pair<const MachineInstr *, unsigned>;
1367   /// Map from debug instruction number to the MachineInstr labelled with that
1368   /// number, and its location within the function. Used to transform
1369   /// instruction numbers in DBG_INSTR_REFs into machine value numbers.
1370   std::map<uint64_t, InstAndNum> DebugInstrNumToInstr;
1371 
1372   // Map of overlapping variable fragments.
1373   OverlapMap OverlapFragments;
1374   VarToFragments SeenFragments;
1375 
1376   /// Tests whether this instruction is a spill to a stack slot.
1377   bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF);
1378 
1379   /// Decide if @MI is a spill instruction and return true if it is. We use 2
1380   /// criteria to make this decision:
1381   /// - Is this instruction a store to a spill slot?
1382   /// - Is there a register operand that is both used and killed?
1383   /// TODO: Store optimization can fold spills into other stores (including
1384   /// other spills). We do not handle this yet (more than one memory operand).
1385   bool isLocationSpill(const MachineInstr &MI, MachineFunction *MF,
1386                        unsigned &Reg);
1387 
1388   /// If a given instruction is identified as a spill, return the spill slot
1389   /// and set \p Reg to the spilled register.
1390   Optional<SpillLoc> isRestoreInstruction(const MachineInstr &MI,
1391                                           MachineFunction *MF, unsigned &Reg);
1392 
1393   /// Given a spill instruction, extract the register and offset used to
1394   /// address the spill slot in a target independent way.
1395   SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI);
1396 
1397   /// Observe a single instruction while stepping through a block.
1398   void process(MachineInstr &MI);
1399 
1400   /// Examines whether \p MI is a DBG_VALUE and notifies trackers.
1401   /// \returns true if MI was recognized and processed.
1402   bool transferDebugValue(const MachineInstr &MI);
1403 
1404   /// Examines whether \p MI is a DBG_INSTR_REF and notifies trackers.
1405   /// \returns true if MI was recognized and processed.
1406   bool transferDebugInstrRef(MachineInstr &MI);
1407 
1408   /// Examines whether \p MI is copy instruction, and notifies trackers.
1409   /// \returns true if MI was recognized and processed.
1410   bool transferRegisterCopy(MachineInstr &MI);
1411 
1412   /// Examines whether \p MI is stack spill or restore  instruction, and
1413   /// notifies trackers. \returns true if MI was recognized and processed.
1414   bool transferSpillOrRestoreInst(MachineInstr &MI);
1415 
1416   /// Examines \p MI for any registers that it defines, and notifies trackers.
1417   void transferRegisterDef(MachineInstr &MI);
1418 
1419   /// Copy one location to the other, accounting for movement of subregisters
1420   /// too.
1421   void performCopy(Register Src, Register Dst);
1422 
1423   void accumulateFragmentMap(MachineInstr &MI);
1424 
1425   /// Step through the function, recording register definitions and movements
1426   /// in an MLocTracker. Convert the observations into a per-block transfer
1427   /// function in \p MLocTransfer, suitable for using with the machine value
1428   /// location dataflow problem.
1429   void
1430   produceMLocTransferFunction(MachineFunction &MF,
1431                               SmallVectorImpl<MLocTransferMap> &MLocTransfer,
1432                               unsigned MaxNumBlocks);
1433 
1434   /// Solve the machine value location dataflow problem. Takes as input the
1435   /// transfer functions in \p MLocTransfer. Writes the output live-in and
1436   /// live-out arrays to the (initialized to zero) multidimensional arrays in
1437   /// \p MInLocs and \p MOutLocs. The outer dimension is indexed by block
1438   /// number, the inner by LocIdx.
1439   void mlocDataflow(ValueIDNum **MInLocs, ValueIDNum **MOutLocs,
1440                     SmallVectorImpl<MLocTransferMap> &MLocTransfer);
1441 
1442   /// Perform a control flow join (lattice value meet) of the values in machine
1443   /// locations at \p MBB. Follows the algorithm described in the file-comment,
1444   /// reading live-outs of predecessors from \p OutLocs, the current live ins
1445   /// from \p InLocs, and assigning the newly computed live ins back into
1446   /// \p InLocs. \returns two bools -- the first indicates whether a change
1447   /// was made, the second whether a lattice downgrade occurred. If the latter
1448   /// is true, revisiting this block is necessary.
1449   std::tuple<bool, bool>
1450   mlocJoin(MachineBasicBlock &MBB,
1451            SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
1452            ValueIDNum **OutLocs, ValueIDNum *InLocs);
1453 
1454   /// Solve the variable value dataflow problem, for a single lexical scope.
1455   /// Uses the algorithm from the file comment to resolve control flow joins,
1456   /// although there are extra hacks, see vlocJoin. Reads the
1457   /// locations of values from the \p MInLocs and \p MOutLocs arrays (see
1458   /// mlocDataflow) and reads the variable values transfer function from
1459   /// \p AllTheVlocs. Live-in and Live-out variable values are stored locally,
1460   /// with the live-ins permanently stored to \p Output once the fixedpoint is
1461   /// reached.
1462   /// \p VarsWeCareAbout contains a collection of the variables in \p Scope
1463   /// that we should be tracking.
1464   /// \p AssignBlocks contains the set of blocks that aren't in \p Scope, but
1465   /// which do contain DBG_VALUEs, which VarLocBasedImpl tracks locations
1466   /// through.
1467   void vlocDataflow(const LexicalScope *Scope, const DILocation *DILoc,
1468                     const SmallSet<DebugVariable, 4> &VarsWeCareAbout,
1469                     SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks,
1470                     LiveInsT &Output, ValueIDNum **MOutLocs,
1471                     ValueIDNum **MInLocs,
1472                     SmallVectorImpl<VLocTracker> &AllTheVLocs);
1473 
1474   /// Compute the live-ins to a block, considering control flow merges according
1475   /// to the method in the file comment. Live out and live in variable values
1476   /// are stored in \p VLOCOutLocs and \p VLOCInLocs. The live-ins for \p MBB
1477   /// are computed and stored into \p VLOCInLocs. \returns true if the live-ins
1478   /// are modified.
1479   /// \p InLocsT Output argument, storage for calculated live-ins.
1480   /// \returns two bools -- the first indicates whether a change
1481   /// was made, the second whether a lattice downgrade occurred. If the latter
1482   /// is true, revisiting this block is necessary.
1483   std::tuple<bool, bool>
1484   vlocJoin(MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs,
1485            SmallPtrSet<const MachineBasicBlock *, 16> *VLOCVisited,
1486            unsigned BBNum, const SmallSet<DebugVariable, 4> &AllVars,
1487            ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
1488            SmallPtrSet<const MachineBasicBlock *, 8> &InScopeBlocks,
1489            SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore,
1490            DenseMap<DebugVariable, DbgValue> &InLocsT);
1491 
1492   /// Continue exploration of the variable-value lattice, as explained in the
1493   /// file-level comment. \p OldLiveInLocation contains the current
1494   /// exploration position, from which we need to descend further. \p Values
1495   /// contains the set of live-in values, \p CurBlockRPONum the RPO number of
1496   /// the current block, and \p CandidateLocations a set of locations that
1497   /// should be considered as PHI locations, if we reach the bottom of the
1498   /// lattice. \returns true if we should downgrade; the value is the agreeing
1499   /// value number in a non-backedge predecessor.
1500   bool vlocDowngradeLattice(const MachineBasicBlock &MBB,
1501                             const DbgValue &OldLiveInLocation,
1502                             const SmallVectorImpl<InValueT> &Values,
1503                             unsigned CurBlockRPONum);
1504 
1505   /// For the given block and live-outs feeding into it, try to find a
1506   /// machine location where they all join. If a solution for all predecessors
1507   /// can't be found, a location where all non-backedge-predecessors join
1508   /// will be returned instead. While this method finds a join location, this
1509   /// says nothing as to whether it should be used.
1510   /// \returns Pair of value ID if found, and true when the correct value
1511   /// is available on all predecessor edges, or false if it's only available
1512   /// for non-backedge predecessors.
1513   std::tuple<Optional<ValueIDNum>, bool>
1514   pickVPHILoc(MachineBasicBlock &MBB, const DebugVariable &Var,
1515               const LiveIdxT &LiveOuts, ValueIDNum **MOutLocs,
1516               ValueIDNum **MInLocs,
1517               const SmallVectorImpl<MachineBasicBlock *> &BlockOrders);
1518 
1519   /// Given the solutions to the two dataflow problems, machine value locations
1520   /// in \p MInLocs and live-in variable values in \p SavedLiveIns, runs the
1521   /// TransferTracker class over the function to produce live-in and transfer
1522   /// DBG_VALUEs, then inserts them. Groups of DBG_VALUEs are inserted in the
1523   /// order given by AllVarsNumbering -- this could be any stable order, but
1524   /// right now "order of appearence in function, when explored in RPO", so
1525   /// that we can compare explictly against VarLocBasedImpl.
1526   void emitLocations(MachineFunction &MF, LiveInsT SavedLiveIns,
1527                      ValueIDNum **MInLocs,
1528                      DenseMap<DebugVariable, unsigned> &AllVarsNumbering);
1529 
1530   /// Boilerplate computation of some initial sets, artifical blocks and
1531   /// RPOT block ordering.
1532   void initialSetup(MachineFunction &MF);
1533 
1534   bool ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) override;
1535 
1536 public:
1537   /// Default construct and initialize the pass.
1538   InstrRefBasedLDV();
1539 
1540   LLVM_DUMP_METHOD
1541   void dump_mloc_transfer(const MLocTransferMap &mloc_transfer) const;
1542 
isCalleeSaved(LocIdx L)1543   bool isCalleeSaved(LocIdx L) {
1544     unsigned Reg = MTracker->LocIdxToLocID[L];
1545     for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
1546       if (CalleeSavedRegs.test(*RAI))
1547         return true;
1548     return false;
1549   }
1550 };
1551 
1552 } // end anonymous namespace
1553 
1554 //===----------------------------------------------------------------------===//
1555 //            Implementation
1556 //===----------------------------------------------------------------------===//
1557 
1558 ValueIDNum ValueIDNum::EmptyValue = {UINT_MAX, UINT_MAX, UINT_MAX};
1559 
1560 /// Default construct and initialize the pass.
InstrRefBasedLDV()1561 InstrRefBasedLDV::InstrRefBasedLDV() {}
1562 
1563 //===----------------------------------------------------------------------===//
1564 //            Debug Range Extension Implementation
1565 //===----------------------------------------------------------------------===//
1566 
1567 #ifndef NDEBUG
1568 // Something to restore in the future.
1569 // void InstrRefBasedLDV::printVarLocInMBB(..)
1570 #endif
1571 
1572 SpillLoc
extractSpillBaseRegAndOffset(const MachineInstr & MI)1573 InstrRefBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
1574   assert(MI.hasOneMemOperand() &&
1575          "Spill instruction does not have exactly one memory operand?");
1576   auto MMOI = MI.memoperands_begin();
1577   const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
1578   assert(PVal->kind() == PseudoSourceValue::FixedStack &&
1579          "Inconsistent memory operand in spill instruction");
1580   int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
1581   const MachineBasicBlock *MBB = MI.getParent();
1582   Register Reg;
1583   StackOffset Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg);
1584   return {Reg, Offset};
1585 }
1586 
1587 /// End all previous ranges related to @MI and start a new range from @MI
1588 /// if it is a DBG_VALUE instr.
transferDebugValue(const MachineInstr & MI)1589 bool InstrRefBasedLDV::transferDebugValue(const MachineInstr &MI) {
1590   if (!MI.isDebugValue())
1591     return false;
1592 
1593   const DILocalVariable *Var = MI.getDebugVariable();
1594   const DIExpression *Expr = MI.getDebugExpression();
1595   const DILocation *DebugLoc = MI.getDebugLoc();
1596   const DILocation *InlinedAt = DebugLoc->getInlinedAt();
1597   assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
1598          "Expected inlined-at fields to agree");
1599 
1600   DebugVariable V(Var, Expr, InlinedAt);
1601   DbgValueProperties Properties(MI);
1602 
1603   // If there are no instructions in this lexical scope, do no location tracking
1604   // at all, this variable shouldn't get a legitimate location range.
1605   auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get());
1606   if (Scope == nullptr)
1607     return true; // handled it; by doing nothing
1608 
1609   const MachineOperand &MO = MI.getOperand(0);
1610 
1611   // MLocTracker needs to know that this register is read, even if it's only
1612   // read by a debug inst.
1613   if (MO.isReg() && MO.getReg() != 0)
1614     (void)MTracker->readReg(MO.getReg());
1615 
1616   // If we're preparing for the second analysis (variables), the machine value
1617   // locations are already solved, and we report this DBG_VALUE and the value
1618   // it refers to to VLocTracker.
1619   if (VTracker) {
1620     if (MO.isReg()) {
1621       // Feed defVar the new variable location, or if this is a
1622       // DBG_VALUE $noreg, feed defVar None.
1623       if (MO.getReg())
1624         VTracker->defVar(MI, Properties, MTracker->readReg(MO.getReg()));
1625       else
1626         VTracker->defVar(MI, Properties, None);
1627     } else if (MI.getOperand(0).isImm() || MI.getOperand(0).isFPImm() ||
1628                MI.getOperand(0).isCImm()) {
1629       VTracker->defVar(MI, MI.getOperand(0));
1630     }
1631   }
1632 
1633   // If performing final tracking of transfers, report this variable definition
1634   // to the TransferTracker too.
1635   if (TTracker)
1636     TTracker->redefVar(MI);
1637   return true;
1638 }
1639 
transferDebugInstrRef(MachineInstr & MI)1640 bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI) {
1641   if (!MI.isDebugRef())
1642     return false;
1643 
1644   // Only handle this instruction when we are building the variable value
1645   // transfer function.
1646   if (!VTracker)
1647     return false;
1648 
1649   unsigned InstNo = MI.getOperand(0).getImm();
1650   unsigned OpNo = MI.getOperand(1).getImm();
1651 
1652   const DILocalVariable *Var = MI.getDebugVariable();
1653   const DIExpression *Expr = MI.getDebugExpression();
1654   const DILocation *DebugLoc = MI.getDebugLoc();
1655   const DILocation *InlinedAt = DebugLoc->getInlinedAt();
1656   assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
1657          "Expected inlined-at fields to agree");
1658 
1659   DebugVariable V(Var, Expr, InlinedAt);
1660 
1661   auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get());
1662   if (Scope == nullptr)
1663     return true; // Handled by doing nothing. This variable is never in scope.
1664 
1665   const MachineFunction &MF = *MI.getParent()->getParent();
1666 
1667   // Various optimizations may have happened to the value during codegen,
1668   // recorded in the value substitution table. Apply any substitutions to
1669   // the instruction / operand number in this DBG_INSTR_REF.
1670   auto Sub = MF.DebugValueSubstitutions.find(std::make_pair(InstNo, OpNo));
1671   while (Sub != MF.DebugValueSubstitutions.end()) {
1672     InstNo = Sub->second.first;
1673     OpNo = Sub->second.second;
1674     Sub = MF.DebugValueSubstitutions.find(std::make_pair(InstNo, OpNo));
1675   }
1676 
1677   // Default machine value number is <None> -- if no instruction defines
1678   // the corresponding value, it must have been optimized out.
1679   Optional<ValueIDNum> NewID = None;
1680 
1681   // Try to lookup the instruction number, and find the machine value number
1682   // that it defines.
1683   auto InstrIt = DebugInstrNumToInstr.find(InstNo);
1684   if (InstrIt != DebugInstrNumToInstr.end()) {
1685     const MachineInstr &TargetInstr = *InstrIt->second.first;
1686     uint64_t BlockNo = TargetInstr.getParent()->getNumber();
1687 
1688     // Pick out the designated operand.
1689     assert(OpNo < TargetInstr.getNumOperands());
1690     const MachineOperand &MO = TargetInstr.getOperand(OpNo);
1691 
1692     // Today, this can only be a register.
1693     assert(MO.isReg() && MO.isDef());
1694 
1695     unsigned LocID = MTracker->getLocID(MO.getReg(), false);
1696     LocIdx L = MTracker->LocIDToLocIdx[LocID];
1697     NewID = ValueIDNum(BlockNo, InstrIt->second.second, L);
1698   }
1699 
1700   // We, we have a value number or None. Tell the variable value tracker about
1701   // it. The rest of this LiveDebugValues implementation acts exactly the same
1702   // for DBG_INSTR_REFs as DBG_VALUEs (just, the former can refer to values that
1703   // aren't immediately available).
1704   DbgValueProperties Properties(Expr, false);
1705   VTracker->defVar(MI, Properties, NewID);
1706 
1707   // If we're on the final pass through the function, decompose this INSTR_REF
1708   // into a plain DBG_VALUE.
1709   if (!TTracker)
1710     return true;
1711 
1712   // Pick a location for the machine value number, if such a location exists.
1713   // (This information could be stored in TransferTracker to make it faster).
1714   Optional<LocIdx> FoundLoc = None;
1715   for (auto Location : MTracker->locations()) {
1716     LocIdx CurL = Location.Idx;
1717     ValueIDNum ID = MTracker->LocIdxToIDNum[CurL];
1718     if (NewID && ID == NewID) {
1719       // If this is the first location with that value, pick it. Otherwise,
1720       // consider whether it's a "longer term" location.
1721       if (!FoundLoc) {
1722         FoundLoc = CurL;
1723         continue;
1724       }
1725 
1726       if (MTracker->isSpill(CurL))
1727         FoundLoc = CurL; // Spills are a longer term location.
1728       else if (!MTracker->isSpill(*FoundLoc) &&
1729                !MTracker->isSpill(CurL) &&
1730                !isCalleeSaved(*FoundLoc) &&
1731                isCalleeSaved(CurL))
1732         FoundLoc = CurL; // Callee saved regs are longer term than normal.
1733     }
1734   }
1735 
1736   // Tell transfer tracker that the variable value has changed.
1737   TTracker->redefVar(MI, Properties, FoundLoc);
1738 
1739   // If there was a value with no location; but the value is defined in a
1740   // later instruction in this block, this is a block-local use-before-def.
1741   if (!FoundLoc && NewID && NewID->getBlock() == CurBB &&
1742       NewID->getInst() > CurInst)
1743     TTracker->addUseBeforeDef(V, {MI.getDebugExpression(), false}, *NewID);
1744 
1745   // Produce a DBG_VALUE representing what this DBG_INSTR_REF meant.
1746   // This DBG_VALUE is potentially a $noreg / undefined location, if
1747   // FoundLoc is None.
1748   // (XXX -- could morph the DBG_INSTR_REF in the future).
1749   MachineInstr *DbgMI = MTracker->emitLoc(FoundLoc, V, Properties);
1750   TTracker->PendingDbgValues.push_back(DbgMI);
1751   TTracker->flushDbgValues(MI.getIterator(), nullptr);
1752 
1753   return true;
1754 }
1755 
transferRegisterDef(MachineInstr & MI)1756 void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) {
1757   // Meta Instructions do not affect the debug liveness of any register they
1758   // define.
1759   if (MI.isImplicitDef()) {
1760     // Except when there's an implicit def, and the location it's defining has
1761     // no value number. The whole point of an implicit def is to announce that
1762     // the register is live, without be specific about it's value. So define
1763     // a value if there isn't one already.
1764     ValueIDNum Num = MTracker->readReg(MI.getOperand(0).getReg());
1765     // Has a legitimate value -> ignore the implicit def.
1766     if (Num.getLoc() != 0)
1767       return;
1768     // Otherwise, def it here.
1769   } else if (MI.isMetaInstruction())
1770     return;
1771 
1772   MachineFunction *MF = MI.getMF();
1773   const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
1774   Register SP = TLI->getStackPointerRegisterToSaveRestore();
1775 
1776   // Find the regs killed by MI, and find regmasks of preserved regs.
1777   // Max out the number of statically allocated elements in `DeadRegs`, as this
1778   // prevents fallback to std::set::count() operations.
1779   SmallSet<uint32_t, 32> DeadRegs;
1780   SmallVector<const uint32_t *, 4> RegMasks;
1781   SmallVector<const MachineOperand *, 4> RegMaskPtrs;
1782   for (const MachineOperand &MO : MI.operands()) {
1783     // Determine whether the operand is a register def.
1784     if (MO.isReg() && MO.isDef() && MO.getReg() &&
1785         Register::isPhysicalRegister(MO.getReg()) &&
1786         !(MI.isCall() && MO.getReg() == SP)) {
1787       // Remove ranges of all aliased registers.
1788       for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
1789         // FIXME: Can we break out of this loop early if no insertion occurs?
1790         DeadRegs.insert(*RAI);
1791     } else if (MO.isRegMask()) {
1792       RegMasks.push_back(MO.getRegMask());
1793       RegMaskPtrs.push_back(&MO);
1794     }
1795   }
1796 
1797   // Tell MLocTracker about all definitions, of regmasks and otherwise.
1798   for (uint32_t DeadReg : DeadRegs)
1799     MTracker->defReg(DeadReg, CurBB, CurInst);
1800 
1801   for (auto *MO : RegMaskPtrs)
1802     MTracker->writeRegMask(MO, CurBB, CurInst);
1803 }
1804 
performCopy(Register SrcRegNum,Register DstRegNum)1805 void InstrRefBasedLDV::performCopy(Register SrcRegNum, Register DstRegNum) {
1806   ValueIDNum SrcValue = MTracker->readReg(SrcRegNum);
1807 
1808   MTracker->setReg(DstRegNum, SrcValue);
1809 
1810   // In all circumstances, re-def the super registers. It's definitely a new
1811   // value now. This doesn't uniquely identify the composition of subregs, for
1812   // example, two identical values in subregisters composed in different
1813   // places would not get equal value numbers.
1814   for (MCSuperRegIterator SRI(DstRegNum, TRI); SRI.isValid(); ++SRI)
1815     MTracker->defReg(*SRI, CurBB, CurInst);
1816 
1817   // If we're emulating VarLocBasedImpl, just define all the subregisters.
1818   // DBG_VALUEs of them will expect to be tracked from the DBG_VALUE, not
1819   // through prior copies.
1820   if (EmulateOldLDV) {
1821     for (MCSubRegIndexIterator DRI(DstRegNum, TRI); DRI.isValid(); ++DRI)
1822       MTracker->defReg(DRI.getSubReg(), CurBB, CurInst);
1823     return;
1824   }
1825 
1826   // Otherwise, actually copy subregisters from one location to another.
1827   // XXX: in addition, any subregisters of DstRegNum that don't line up with
1828   // the source register should be def'd.
1829   for (MCSubRegIndexIterator SRI(SrcRegNum, TRI); SRI.isValid(); ++SRI) {
1830     unsigned SrcSubReg = SRI.getSubReg();
1831     unsigned SubRegIdx = SRI.getSubRegIndex();
1832     unsigned DstSubReg = TRI->getSubReg(DstRegNum, SubRegIdx);
1833     if (!DstSubReg)
1834       continue;
1835 
1836     // Do copy. There are two matching subregisters, the source value should
1837     // have been def'd when the super-reg was, the latter might not be tracked
1838     // yet.
1839     // This will force SrcSubReg to be tracked, if it isn't yet.
1840     (void)MTracker->readReg(SrcSubReg);
1841     LocIdx SrcL = MTracker->getRegMLoc(SrcSubReg);
1842     assert(SrcL.asU64());
1843     (void)MTracker->readReg(DstSubReg);
1844     LocIdx DstL = MTracker->getRegMLoc(DstSubReg);
1845     assert(DstL.asU64());
1846     (void)DstL;
1847     ValueIDNum CpyValue = {SrcValue.getBlock(), SrcValue.getInst(), SrcL};
1848 
1849     MTracker->setReg(DstSubReg, CpyValue);
1850   }
1851 }
1852 
isSpillInstruction(const MachineInstr & MI,MachineFunction * MF)1853 bool InstrRefBasedLDV::isSpillInstruction(const MachineInstr &MI,
1854                                           MachineFunction *MF) {
1855   // TODO: Handle multiple stores folded into one.
1856   if (!MI.hasOneMemOperand())
1857     return false;
1858 
1859   if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII))
1860     return false; // This is not a spill instruction, since no valid size was
1861                   // returned from either function.
1862 
1863   return true;
1864 }
1865 
isLocationSpill(const MachineInstr & MI,MachineFunction * MF,unsigned & Reg)1866 bool InstrRefBasedLDV::isLocationSpill(const MachineInstr &MI,
1867                                        MachineFunction *MF, unsigned &Reg) {
1868   if (!isSpillInstruction(MI, MF))
1869     return false;
1870 
1871   // XXX FIXME: On x86, isStoreToStackSlotPostFE returns '1' instead of an
1872   // actual register number.
1873   if (ObserveAllStackops) {
1874     int FI;
1875     Reg = TII->isStoreToStackSlotPostFE(MI, FI);
1876     return Reg != 0;
1877   }
1878 
1879   auto isKilledReg = [&](const MachineOperand MO, unsigned &Reg) {
1880     if (!MO.isReg() || !MO.isUse()) {
1881       Reg = 0;
1882       return false;
1883     }
1884     Reg = MO.getReg();
1885     return MO.isKill();
1886   };
1887 
1888   for (const MachineOperand &MO : MI.operands()) {
1889     // In a spill instruction generated by the InlineSpiller the spilled
1890     // register has its kill flag set.
1891     if (isKilledReg(MO, Reg))
1892       return true;
1893     if (Reg != 0) {
1894       // Check whether next instruction kills the spilled register.
1895       // FIXME: Current solution does not cover search for killed register in
1896       // bundles and instructions further down the chain.
1897       auto NextI = std::next(MI.getIterator());
1898       // Skip next instruction that points to basic block end iterator.
1899       if (MI.getParent()->end() == NextI)
1900         continue;
1901       unsigned RegNext;
1902       for (const MachineOperand &MONext : NextI->operands()) {
1903         // Return true if we came across the register from the
1904         // previous spill instruction that is killed in NextI.
1905         if (isKilledReg(MONext, RegNext) && RegNext == Reg)
1906           return true;
1907       }
1908     }
1909   }
1910   // Return false if we didn't find spilled register.
1911   return false;
1912 }
1913 
1914 Optional<SpillLoc>
isRestoreInstruction(const MachineInstr & MI,MachineFunction * MF,unsigned & Reg)1915 InstrRefBasedLDV::isRestoreInstruction(const MachineInstr &MI,
1916                                        MachineFunction *MF, unsigned &Reg) {
1917   if (!MI.hasOneMemOperand())
1918     return None;
1919 
1920   // FIXME: Handle folded restore instructions with more than one memory
1921   // operand.
1922   if (MI.getRestoreSize(TII)) {
1923     Reg = MI.getOperand(0).getReg();
1924     return extractSpillBaseRegAndOffset(MI);
1925   }
1926   return None;
1927 }
1928 
transferSpillOrRestoreInst(MachineInstr & MI)1929 bool InstrRefBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI) {
1930   // XXX -- it's too difficult to implement VarLocBasedImpl's  stack location
1931   // limitations under the new model. Therefore, when comparing them, compare
1932   // versions that don't attempt spills or restores at all.
1933   if (EmulateOldLDV)
1934     return false;
1935 
1936   MachineFunction *MF = MI.getMF();
1937   unsigned Reg;
1938   Optional<SpillLoc> Loc;
1939 
1940   LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump(););
1941 
1942   // First, if there are any DBG_VALUEs pointing at a spill slot that is
1943   // written to, terminate that variable location. The value in memory
1944   // will have changed. DbgEntityHistoryCalculator doesn't try to detect this.
1945   if (isSpillInstruction(MI, MF)) {
1946     Loc = extractSpillBaseRegAndOffset(MI);
1947 
1948     if (TTracker) {
1949       Optional<LocIdx> MLoc = MTracker->getSpillMLoc(*Loc);
1950       if (MLoc)
1951         TTracker->clobberMloc(*MLoc, MI.getIterator());
1952     }
1953   }
1954 
1955   // Try to recognise spill and restore instructions that may transfer a value.
1956   if (isLocationSpill(MI, MF, Reg)) {
1957     Loc = extractSpillBaseRegAndOffset(MI);
1958     auto ValueID = MTracker->readReg(Reg);
1959 
1960     // If the location is empty, produce a phi, signify it's the live-in value.
1961     if (ValueID.getLoc() == 0)
1962       ValueID = {CurBB, 0, MTracker->getRegMLoc(Reg)};
1963 
1964     MTracker->setSpill(*Loc, ValueID);
1965     auto OptSpillLocIdx = MTracker->getSpillMLoc(*Loc);
1966     assert(OptSpillLocIdx && "Spill slot set but has no LocIdx?");
1967     LocIdx SpillLocIdx = *OptSpillLocIdx;
1968 
1969     // Tell TransferTracker about this spill, produce DBG_VALUEs for it.
1970     if (TTracker)
1971       TTracker->transferMlocs(MTracker->getRegMLoc(Reg), SpillLocIdx,
1972                               MI.getIterator());
1973   } else {
1974     if (!(Loc = isRestoreInstruction(MI, MF, Reg)))
1975       return false;
1976 
1977     // Is there a value to be restored?
1978     auto OptValueID = MTracker->readSpill(*Loc);
1979     if (OptValueID) {
1980       ValueIDNum ValueID = *OptValueID;
1981       LocIdx SpillLocIdx = *MTracker->getSpillMLoc(*Loc);
1982       // XXX -- can we recover sub-registers of this value? Until we can, first
1983       // overwrite all defs of the register being restored to.
1984       for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
1985         MTracker->defReg(*RAI, CurBB, CurInst);
1986 
1987       // Now override the reg we're restoring to.
1988       MTracker->setReg(Reg, ValueID);
1989 
1990       // Report this restore to the transfer tracker too.
1991       if (TTracker)
1992         TTracker->transferMlocs(SpillLocIdx, MTracker->getRegMLoc(Reg),
1993                                 MI.getIterator());
1994     } else {
1995       // There isn't anything in the location; not clear if this is a code path
1996       // that still runs. Def this register anyway just in case.
1997       for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
1998         MTracker->defReg(*RAI, CurBB, CurInst);
1999 
2000       // Force the spill slot to be tracked.
2001       LocIdx L = MTracker->getOrTrackSpillLoc(*Loc);
2002 
2003       // Set the restored value to be a machine phi number, signifying that it's
2004       // whatever the spills live-in value is in this block. Definitely has
2005       // a LocIdx due to the setSpill above.
2006       ValueIDNum ValueID = {CurBB, 0, L};
2007       MTracker->setReg(Reg, ValueID);
2008       MTracker->setSpill(*Loc, ValueID);
2009     }
2010   }
2011   return true;
2012 }
2013 
transferRegisterCopy(MachineInstr & MI)2014 bool InstrRefBasedLDV::transferRegisterCopy(MachineInstr &MI) {
2015   auto DestSrc = TII->isCopyInstr(MI);
2016   if (!DestSrc)
2017     return false;
2018 
2019   const MachineOperand *DestRegOp = DestSrc->Destination;
2020   const MachineOperand *SrcRegOp = DestSrc->Source;
2021 
2022   auto isCalleeSavedReg = [&](unsigned Reg) {
2023     for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
2024       if (CalleeSavedRegs.test(*RAI))
2025         return true;
2026     return false;
2027   };
2028 
2029   Register SrcReg = SrcRegOp->getReg();
2030   Register DestReg = DestRegOp->getReg();
2031 
2032   // Ignore identity copies. Yep, these make it as far as LiveDebugValues.
2033   if (SrcReg == DestReg)
2034     return true;
2035 
2036   // For emulating VarLocBasedImpl:
2037   // We want to recognize instructions where destination register is callee
2038   // saved register. If register that could be clobbered by the call is
2039   // included, there would be a great chance that it is going to be clobbered
2040   // soon. It is more likely that previous register, which is callee saved, is
2041   // going to stay unclobbered longer, even if it is killed.
2042   //
2043   // For InstrRefBasedImpl, we can track multiple locations per value, so
2044   // ignore this condition.
2045   if (EmulateOldLDV && !isCalleeSavedReg(DestReg))
2046     return false;
2047 
2048   // InstrRefBasedImpl only followed killing copies.
2049   if (EmulateOldLDV && !SrcRegOp->isKill())
2050     return false;
2051 
2052   // Copy MTracker info, including subregs if available.
2053   InstrRefBasedLDV::performCopy(SrcReg, DestReg);
2054 
2055   // Only produce a transfer of DBG_VALUE within a block where old LDV
2056   // would have. We might make use of the additional value tracking in some
2057   // other way, later.
2058   if (TTracker && isCalleeSavedReg(DestReg) && SrcRegOp->isKill())
2059     TTracker->transferMlocs(MTracker->getRegMLoc(SrcReg),
2060                             MTracker->getRegMLoc(DestReg), MI.getIterator());
2061 
2062   // VarLocBasedImpl would quit tracking the old location after copying.
2063   if (EmulateOldLDV && SrcReg != DestReg)
2064     MTracker->defReg(SrcReg, CurBB, CurInst);
2065 
2066   return true;
2067 }
2068 
2069 /// Accumulate a mapping between each DILocalVariable fragment and other
2070 /// fragments of that DILocalVariable which overlap. This reduces work during
2071 /// the data-flow stage from "Find any overlapping fragments" to "Check if the
2072 /// known-to-overlap fragments are present".
2073 /// \param MI A previously unprocessed DEBUG_VALUE instruction to analyze for
2074 ///           fragment usage.
accumulateFragmentMap(MachineInstr & MI)2075 void InstrRefBasedLDV::accumulateFragmentMap(MachineInstr &MI) {
2076   DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(),
2077                       MI.getDebugLoc()->getInlinedAt());
2078   FragmentInfo ThisFragment = MIVar.getFragmentOrDefault();
2079 
2080   // If this is the first sighting of this variable, then we are guaranteed
2081   // there are currently no overlapping fragments either. Initialize the set
2082   // of seen fragments, record no overlaps for the current one, and return.
2083   auto SeenIt = SeenFragments.find(MIVar.getVariable());
2084   if (SeenIt == SeenFragments.end()) {
2085     SmallSet<FragmentInfo, 4> OneFragment;
2086     OneFragment.insert(ThisFragment);
2087     SeenFragments.insert({MIVar.getVariable(), OneFragment});
2088 
2089     OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}});
2090     return;
2091   }
2092 
2093   // If this particular Variable/Fragment pair already exists in the overlap
2094   // map, it has already been accounted for.
2095   auto IsInOLapMap =
2096       OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}});
2097   if (!IsInOLapMap.second)
2098     return;
2099 
2100   auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;
2101   auto &AllSeenFragments = SeenIt->second;
2102 
2103   // Otherwise, examine all other seen fragments for this variable, with "this"
2104   // fragment being a previously unseen fragment. Record any pair of
2105   // overlapping fragments.
2106   for (auto &ASeenFragment : AllSeenFragments) {
2107     // Does this previously seen fragment overlap?
2108     if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) {
2109       // Yes: Mark the current fragment as being overlapped.
2110       ThisFragmentsOverlaps.push_back(ASeenFragment);
2111       // Mark the previously seen fragment as being overlapped by the current
2112       // one.
2113       auto ASeenFragmentsOverlaps =
2114           OverlapFragments.find({MIVar.getVariable(), ASeenFragment});
2115       assert(ASeenFragmentsOverlaps != OverlapFragments.end() &&
2116              "Previously seen var fragment has no vector of overlaps");
2117       ASeenFragmentsOverlaps->second.push_back(ThisFragment);
2118     }
2119   }
2120 
2121   AllSeenFragments.insert(ThisFragment);
2122 }
2123 
process(MachineInstr & MI)2124 void InstrRefBasedLDV::process(MachineInstr &MI) {
2125   // Try to interpret an MI as a debug or transfer instruction. Only if it's
2126   // none of these should we interpret it's register defs as new value
2127   // definitions.
2128   if (transferDebugValue(MI))
2129     return;
2130   if (transferDebugInstrRef(MI))
2131     return;
2132   if (transferRegisterCopy(MI))
2133     return;
2134   if (transferSpillOrRestoreInst(MI))
2135     return;
2136   transferRegisterDef(MI);
2137 }
2138 
produceMLocTransferFunction(MachineFunction & MF,SmallVectorImpl<MLocTransferMap> & MLocTransfer,unsigned MaxNumBlocks)2139 void InstrRefBasedLDV::produceMLocTransferFunction(
2140     MachineFunction &MF, SmallVectorImpl<MLocTransferMap> &MLocTransfer,
2141     unsigned MaxNumBlocks) {
2142   // Because we try to optimize around register mask operands by ignoring regs
2143   // that aren't currently tracked, we set up something ugly for later: RegMask
2144   // operands that are seen earlier than the first use of a register, still need
2145   // to clobber that register in the transfer function. But this information
2146   // isn't actively recorded. Instead, we track each RegMask used in each block,
2147   // and accumulated the clobbered but untracked registers in each block into
2148   // the following bitvector. Later, if new values are tracked, we can add
2149   // appropriate clobbers.
2150   SmallVector<BitVector, 32> BlockMasks;
2151   BlockMasks.resize(MaxNumBlocks);
2152 
2153   // Reserve one bit per register for the masks described above.
2154   unsigned BVWords = MachineOperand::getRegMaskSize(TRI->getNumRegs());
2155   for (auto &BV : BlockMasks)
2156     BV.resize(TRI->getNumRegs(), true);
2157 
2158   // Step through all instructions and inhale the transfer function.
2159   for (auto &MBB : MF) {
2160     // Object fields that are read by trackers to know where we are in the
2161     // function.
2162     CurBB = MBB.getNumber();
2163     CurInst = 1;
2164 
2165     // Set all machine locations to a PHI value. For transfer function
2166     // production only, this signifies the live-in value to the block.
2167     MTracker->reset();
2168     MTracker->setMPhis(CurBB);
2169 
2170     // Step through each instruction in this block.
2171     for (auto &MI : MBB) {
2172       process(MI);
2173       // Also accumulate fragment map.
2174       if (MI.isDebugValue())
2175         accumulateFragmentMap(MI);
2176 
2177       // Create a map from the instruction number (if present) to the
2178       // MachineInstr and its position.
2179       if (uint64_t InstrNo = MI.peekDebugInstrNum()) {
2180         auto InstrAndPos = std::make_pair(&MI, CurInst);
2181         auto InsertResult =
2182             DebugInstrNumToInstr.insert(std::make_pair(InstrNo, InstrAndPos));
2183 
2184         // There should never be duplicate instruction numbers.
2185         assert(InsertResult.second);
2186         (void)InsertResult;
2187       }
2188 
2189       ++CurInst;
2190     }
2191 
2192     // Produce the transfer function, a map of machine location to new value. If
2193     // any machine location has the live-in phi value from the start of the
2194     // block, it's live-through and doesn't need recording in the transfer
2195     // function.
2196     for (auto Location : MTracker->locations()) {
2197       LocIdx Idx = Location.Idx;
2198       ValueIDNum &P = Location.Value;
2199       if (P.isPHI() && P.getLoc() == Idx.asU64())
2200         continue;
2201 
2202       // Insert-or-update.
2203       auto &TransferMap = MLocTransfer[CurBB];
2204       auto Result = TransferMap.insert(std::make_pair(Idx.asU64(), P));
2205       if (!Result.second)
2206         Result.first->second = P;
2207     }
2208 
2209     // Accumulate any bitmask operands into the clobberred reg mask for this
2210     // block.
2211     for (auto &P : MTracker->Masks) {
2212       BlockMasks[CurBB].clearBitsNotInMask(P.first->getRegMask(), BVWords);
2213     }
2214   }
2215 
2216   // Compute a bitvector of all the registers that are tracked in this block.
2217   const TargetLowering *TLI = MF.getSubtarget().getTargetLowering();
2218   Register SP = TLI->getStackPointerRegisterToSaveRestore();
2219   BitVector UsedRegs(TRI->getNumRegs());
2220   for (auto Location : MTracker->locations()) {
2221     unsigned ID = MTracker->LocIdxToLocID[Location.Idx];
2222     if (ID >= TRI->getNumRegs() || ID == SP)
2223       continue;
2224     UsedRegs.set(ID);
2225   }
2226 
2227   // Check that any regmask-clobber of a register that gets tracked, is not
2228   // live-through in the transfer function. It needs to be clobbered at the
2229   // very least.
2230   for (unsigned int I = 0; I < MaxNumBlocks; ++I) {
2231     BitVector &BV = BlockMasks[I];
2232     BV.flip();
2233     BV &= UsedRegs;
2234     // This produces all the bits that we clobber, but also use. Check that
2235     // they're all clobbered or at least set in the designated transfer
2236     // elem.
2237     for (unsigned Bit : BV.set_bits()) {
2238       unsigned ID = MTracker->getLocID(Bit, false);
2239       LocIdx Idx = MTracker->LocIDToLocIdx[ID];
2240       auto &TransferMap = MLocTransfer[I];
2241 
2242       // Install a value representing the fact that this location is effectively
2243       // written to in this block. As there's no reserved value, instead use
2244       // a value number that is never generated. Pick the value number for the
2245       // first instruction in the block, def'ing this location, which we know
2246       // this block never used anyway.
2247       ValueIDNum NotGeneratedNum = ValueIDNum(I, 1, Idx);
2248       auto Result =
2249         TransferMap.insert(std::make_pair(Idx.asU64(), NotGeneratedNum));
2250       if (!Result.second) {
2251         ValueIDNum &ValueID = Result.first->second;
2252         if (ValueID.getBlock() == I && ValueID.isPHI())
2253           // It was left as live-through. Set it to clobbered.
2254           ValueID = NotGeneratedNum;
2255       }
2256     }
2257   }
2258 }
2259 
2260 std::tuple<bool, bool>
mlocJoin(MachineBasicBlock & MBB,SmallPtrSet<const MachineBasicBlock *,16> & Visited,ValueIDNum ** OutLocs,ValueIDNum * InLocs)2261 InstrRefBasedLDV::mlocJoin(MachineBasicBlock &MBB,
2262                            SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
2263                            ValueIDNum **OutLocs, ValueIDNum *InLocs) {
2264   LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
2265   bool Changed = false;
2266   bool DowngradeOccurred = false;
2267 
2268   // Collect predecessors that have been visited. Anything that hasn't been
2269   // visited yet is a backedge on the first iteration, and the meet of it's
2270   // lattice value for all locations will be unaffected.
2271   SmallVector<const MachineBasicBlock *, 8> BlockOrders;
2272   for (auto Pred : MBB.predecessors()) {
2273     if (Visited.count(Pred)) {
2274       BlockOrders.push_back(Pred);
2275     }
2276   }
2277 
2278   // Visit predecessors in RPOT order.
2279   auto Cmp = [&](const MachineBasicBlock *A, const MachineBasicBlock *B) {
2280     return BBToOrder.find(A)->second < BBToOrder.find(B)->second;
2281   };
2282   llvm::sort(BlockOrders, Cmp);
2283 
2284   // Skip entry block.
2285   if (BlockOrders.size() == 0)
2286     return std::tuple<bool, bool>(false, false);
2287 
2288   // Step through all machine locations, then look at each predecessor and
2289   // detect disagreements.
2290   unsigned ThisBlockRPO = BBToOrder.find(&MBB)->second;
2291   for (auto Location : MTracker->locations()) {
2292     LocIdx Idx = Location.Idx;
2293     // Pick out the first predecessors live-out value for this location. It's
2294     // guaranteed to be not a backedge, as we order by RPO.
2295     ValueIDNum BaseVal = OutLocs[BlockOrders[0]->getNumber()][Idx.asU64()];
2296 
2297     // Some flags for whether there's a disagreement, and whether it's a
2298     // disagreement with a backedge or not.
2299     bool Disagree = false;
2300     bool NonBackEdgeDisagree = false;
2301 
2302     // Loop around everything that wasn't 'base'.
2303     for (unsigned int I = 1; I < BlockOrders.size(); ++I) {
2304       auto *MBB = BlockOrders[I];
2305       if (BaseVal != OutLocs[MBB->getNumber()][Idx.asU64()]) {
2306         // Live-out of a predecessor disagrees with the first predecessor.
2307         Disagree = true;
2308 
2309         // Test whether it's a disagreemnt in the backedges or not.
2310         if (BBToOrder.find(MBB)->second < ThisBlockRPO) // might be self b/e
2311           NonBackEdgeDisagree = true;
2312       }
2313     }
2314 
2315     bool OverRide = false;
2316     if (Disagree && !NonBackEdgeDisagree) {
2317       // Only the backedges disagree. Consider demoting the livein
2318       // lattice value, as per the file level comment. The value we consider
2319       // demoting to is the value that the non-backedge predecessors agree on.
2320       // The order of values is that non-PHIs are \top, a PHI at this block
2321       // \bot, and phis between the two are ordered by their RPO number.
2322       // If there's no agreement, or we've already demoted to this PHI value
2323       // before, replace with a PHI value at this block.
2324 
2325       // Calculate order numbers: zero means normal def, nonzero means RPO
2326       // number.
2327       unsigned BaseBlockRPONum = BBNumToRPO[BaseVal.getBlock()] + 1;
2328       if (!BaseVal.isPHI())
2329         BaseBlockRPONum = 0;
2330 
2331       ValueIDNum &InLocID = InLocs[Idx.asU64()];
2332       unsigned InLocRPONum = BBNumToRPO[InLocID.getBlock()] + 1;
2333       if (!InLocID.isPHI())
2334         InLocRPONum = 0;
2335 
2336       // Should we ignore the disagreeing backedges, and override with the
2337       // value the other predecessors agree on (in "base")?
2338       unsigned ThisBlockRPONum = BBNumToRPO[MBB.getNumber()] + 1;
2339       if (BaseBlockRPONum > InLocRPONum && BaseBlockRPONum < ThisBlockRPONum) {
2340         // Override.
2341         OverRide = true;
2342         DowngradeOccurred = true;
2343       }
2344     }
2345     // else: if we disagree in the non-backedges, then this is definitely
2346     // a control flow merge where different values merge. Make it a PHI.
2347 
2348     // Generate a phi...
2349     ValueIDNum PHI = {(uint64_t)MBB.getNumber(), 0, Idx};
2350     ValueIDNum NewVal = (Disagree && !OverRide) ? PHI : BaseVal;
2351     if (InLocs[Idx.asU64()] != NewVal) {
2352       Changed |= true;
2353       InLocs[Idx.asU64()] = NewVal;
2354     }
2355   }
2356 
2357   // TODO: Reimplement NumInserted and NumRemoved.
2358   return std::tuple<bool, bool>(Changed, DowngradeOccurred);
2359 }
2360 
mlocDataflow(ValueIDNum ** MInLocs,ValueIDNum ** MOutLocs,SmallVectorImpl<MLocTransferMap> & MLocTransfer)2361 void InstrRefBasedLDV::mlocDataflow(
2362     ValueIDNum **MInLocs, ValueIDNum **MOutLocs,
2363     SmallVectorImpl<MLocTransferMap> &MLocTransfer) {
2364   std::priority_queue<unsigned int, std::vector<unsigned int>,
2365                       std::greater<unsigned int>>
2366       Worklist, Pending;
2367 
2368   // We track what is on the current and pending worklist to avoid inserting
2369   // the same thing twice. We could avoid this with a custom priority queue,
2370   // but this is probably not worth it.
2371   SmallPtrSet<MachineBasicBlock *, 16> OnPending, OnWorklist;
2372 
2373   // Initialize worklist with every block to be visited.
2374   for (unsigned int I = 0; I < BBToOrder.size(); ++I) {
2375     Worklist.push(I);
2376     OnWorklist.insert(OrderToBB[I]);
2377   }
2378 
2379   MTracker->reset();
2380 
2381   // Set inlocs for entry block -- each as a PHI at the entry block. Represents
2382   // the incoming value to the function.
2383   MTracker->setMPhis(0);
2384   for (auto Location : MTracker->locations())
2385     MInLocs[0][Location.Idx.asU64()] = Location.Value;
2386 
2387   SmallPtrSet<const MachineBasicBlock *, 16> Visited;
2388   while (!Worklist.empty() || !Pending.empty()) {
2389     // Vector for storing the evaluated block transfer function.
2390     SmallVector<std::pair<LocIdx, ValueIDNum>, 32> ToRemap;
2391 
2392     while (!Worklist.empty()) {
2393       MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
2394       CurBB = MBB->getNumber();
2395       Worklist.pop();
2396 
2397       // Join the values in all predecessor blocks.
2398       bool InLocsChanged, DowngradeOccurred;
2399       std::tie(InLocsChanged, DowngradeOccurred) =
2400           mlocJoin(*MBB, Visited, MOutLocs, MInLocs[CurBB]);
2401       InLocsChanged |= Visited.insert(MBB).second;
2402 
2403       // If a downgrade occurred, book us in for re-examination on the next
2404       // iteration.
2405       if (DowngradeOccurred && OnPending.insert(MBB).second)
2406         Pending.push(BBToOrder[MBB]);
2407 
2408       // Don't examine transfer function if we've visited this loc at least
2409       // once, and inlocs haven't changed.
2410       if (!InLocsChanged)
2411         continue;
2412 
2413       // Load the current set of live-ins into MLocTracker.
2414       MTracker->loadFromArray(MInLocs[CurBB], CurBB);
2415 
2416       // Each element of the transfer function can be a new def, or a read of
2417       // a live-in value. Evaluate each element, and store to "ToRemap".
2418       ToRemap.clear();
2419       for (auto &P : MLocTransfer[CurBB]) {
2420         if (P.second.getBlock() == CurBB && P.second.isPHI()) {
2421           // This is a movement of whatever was live in. Read it.
2422           ValueIDNum NewID = MTracker->getNumAtPos(P.second.getLoc());
2423           ToRemap.push_back(std::make_pair(P.first, NewID));
2424         } else {
2425           // It's a def. Just set it.
2426           assert(P.second.getBlock() == CurBB);
2427           ToRemap.push_back(std::make_pair(P.first, P.second));
2428         }
2429       }
2430 
2431       // Commit the transfer function changes into mloc tracker, which
2432       // transforms the contents of the MLocTracker into the live-outs.
2433       for (auto &P : ToRemap)
2434         MTracker->setMLoc(P.first, P.second);
2435 
2436       // Now copy out-locs from mloc tracker into out-loc vector, checking
2437       // whether changes have occurred. These changes can have come from both
2438       // the transfer function, and mlocJoin.
2439       bool OLChanged = false;
2440       for (auto Location : MTracker->locations()) {
2441         OLChanged |= MOutLocs[CurBB][Location.Idx.asU64()] != Location.Value;
2442         MOutLocs[CurBB][Location.Idx.asU64()] = Location.Value;
2443       }
2444 
2445       MTracker->reset();
2446 
2447       // No need to examine successors again if out-locs didn't change.
2448       if (!OLChanged)
2449         continue;
2450 
2451       // All successors should be visited: put any back-edges on the pending
2452       // list for the next dataflow iteration, and any other successors to be
2453       // visited this iteration, if they're not going to be already.
2454       for (auto s : MBB->successors()) {
2455         // Does branching to this successor represent a back-edge?
2456         if (BBToOrder[s] > BBToOrder[MBB]) {
2457           // No: visit it during this dataflow iteration.
2458           if (OnWorklist.insert(s).second)
2459             Worklist.push(BBToOrder[s]);
2460         } else {
2461           // Yes: visit it on the next iteration.
2462           if (OnPending.insert(s).second)
2463             Pending.push(BBToOrder[s]);
2464         }
2465       }
2466     }
2467 
2468     Worklist.swap(Pending);
2469     std::swap(OnPending, OnWorklist);
2470     OnPending.clear();
2471     // At this point, pending must be empty, since it was just the empty
2472     // worklist
2473     assert(Pending.empty() && "Pending should be empty");
2474   }
2475 
2476   // Once all the live-ins don't change on mlocJoin(), we've reached a
2477   // fixedpoint.
2478 }
2479 
vlocDowngradeLattice(const MachineBasicBlock & MBB,const DbgValue & OldLiveInLocation,const SmallVectorImpl<InValueT> & Values,unsigned CurBlockRPONum)2480 bool InstrRefBasedLDV::vlocDowngradeLattice(
2481     const MachineBasicBlock &MBB, const DbgValue &OldLiveInLocation,
2482     const SmallVectorImpl<InValueT> &Values, unsigned CurBlockRPONum) {
2483   // Ranking value preference: see file level comment, the highest rank is
2484   // a plain def, followed by PHI values in reverse post-order. Numerically,
2485   // we assign all defs the rank '0', all PHIs their blocks RPO number plus
2486   // one, and consider the lowest value the highest ranked.
2487   int OldLiveInRank = BBNumToRPO[OldLiveInLocation.ID.getBlock()] + 1;
2488   if (!OldLiveInLocation.ID.isPHI())
2489     OldLiveInRank = 0;
2490 
2491   // Allow any unresolvable conflict to be over-ridden.
2492   if (OldLiveInLocation.Kind == DbgValue::NoVal) {
2493     // Although if it was an unresolvable conflict from _this_ block, then
2494     // all other seeking of downgrades and PHIs must have failed before hand.
2495     if (OldLiveInLocation.BlockNo == (unsigned)MBB.getNumber())
2496       return false;
2497     OldLiveInRank = INT_MIN;
2498   }
2499 
2500   auto &InValue = *Values[0].second;
2501 
2502   if (InValue.Kind == DbgValue::Const || InValue.Kind == DbgValue::NoVal)
2503     return false;
2504 
2505   unsigned ThisRPO = BBNumToRPO[InValue.ID.getBlock()];
2506   int ThisRank = ThisRPO + 1;
2507   if (!InValue.ID.isPHI())
2508     ThisRank = 0;
2509 
2510   // Too far down the lattice?
2511   if (ThisRPO >= CurBlockRPONum)
2512     return false;
2513 
2514   // Higher in the lattice than what we've already explored?
2515   if (ThisRank <= OldLiveInRank)
2516     return false;
2517 
2518   return true;
2519 }
2520 
pickVPHILoc(MachineBasicBlock & MBB,const DebugVariable & Var,const LiveIdxT & LiveOuts,ValueIDNum ** MOutLocs,ValueIDNum ** MInLocs,const SmallVectorImpl<MachineBasicBlock * > & BlockOrders)2521 std::tuple<Optional<ValueIDNum>, bool> InstrRefBasedLDV::pickVPHILoc(
2522     MachineBasicBlock &MBB, const DebugVariable &Var, const LiveIdxT &LiveOuts,
2523     ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
2524     const SmallVectorImpl<MachineBasicBlock *> &BlockOrders) {
2525   // Collect a set of locations from predecessor where its live-out value can
2526   // be found.
2527   SmallVector<SmallVector<LocIdx, 4>, 8> Locs;
2528   unsigned NumLocs = MTracker->getNumLocs();
2529   unsigned BackEdgesStart = 0;
2530 
2531   for (auto p : BlockOrders) {
2532     // Pick out where backedges start in the list of predecessors. Relies on
2533     // BlockOrders being sorted by RPO.
2534     if (BBToOrder[p] < BBToOrder[&MBB])
2535       ++BackEdgesStart;
2536 
2537     // For each predecessor, create a new set of locations.
2538     Locs.resize(Locs.size() + 1);
2539     unsigned ThisBBNum = p->getNumber();
2540     auto LiveOutMap = LiveOuts.find(p);
2541     if (LiveOutMap == LiveOuts.end())
2542       // This predecessor isn't in scope, it must have no live-in/live-out
2543       // locations.
2544       continue;
2545 
2546     auto It = LiveOutMap->second->find(Var);
2547     if (It == LiveOutMap->second->end())
2548       // There's no value recorded for this variable in this predecessor,
2549       // leave an empty set of locations.
2550       continue;
2551 
2552     const DbgValue &OutVal = It->second;
2553 
2554     if (OutVal.Kind == DbgValue::Const || OutVal.Kind == DbgValue::NoVal)
2555       // Consts and no-values cannot have locations we can join on.
2556       continue;
2557 
2558     assert(OutVal.Kind == DbgValue::Proposed || OutVal.Kind == DbgValue::Def);
2559     ValueIDNum ValToLookFor = OutVal.ID;
2560 
2561     // Search the live-outs of the predecessor for the specified value.
2562     for (unsigned int I = 0; I < NumLocs; ++I) {
2563       if (MOutLocs[ThisBBNum][I] == ValToLookFor)
2564         Locs.back().push_back(LocIdx(I));
2565     }
2566   }
2567 
2568   // If there were no locations at all, return an empty result.
2569   if (Locs.empty())
2570     return std::tuple<Optional<ValueIDNum>, bool>(None, false);
2571 
2572   // Lambda for seeking a common location within a range of location-sets.
2573   using LocsIt = SmallVector<SmallVector<LocIdx, 4>, 8>::iterator;
2574   auto SeekLocation =
2575       [&Locs](llvm::iterator_range<LocsIt> SearchRange) -> Optional<LocIdx> {
2576     // Starting with the first set of locations, take the intersection with
2577     // subsequent sets.
2578     SmallVector<LocIdx, 4> base = Locs[0];
2579     for (auto &S : SearchRange) {
2580       SmallVector<LocIdx, 4> new_base;
2581       std::set_intersection(base.begin(), base.end(), S.begin(), S.end(),
2582                             std::inserter(new_base, new_base.begin()));
2583       base = new_base;
2584     }
2585     if (base.empty())
2586       return None;
2587 
2588     // We now have a set of LocIdxes that contain the right output value in
2589     // each of the predecessors. Pick the lowest; if there's a register loc,
2590     // that'll be it.
2591     return *base.begin();
2592   };
2593 
2594   // Search for a common location for all predecessors. If we can't, then fall
2595   // back to only finding a common location between non-backedge predecessors.
2596   bool ValidForAllLocs = true;
2597   auto TheLoc = SeekLocation(Locs);
2598   if (!TheLoc) {
2599     ValidForAllLocs = false;
2600     TheLoc =
2601         SeekLocation(make_range(Locs.begin(), Locs.begin() + BackEdgesStart));
2602   }
2603 
2604   if (!TheLoc)
2605     return std::tuple<Optional<ValueIDNum>, bool>(None, false);
2606 
2607   // Return a PHI-value-number for the found location.
2608   LocIdx L = *TheLoc;
2609   ValueIDNum PHIVal = {(unsigned)MBB.getNumber(), 0, L};
2610   return std::tuple<Optional<ValueIDNum>, bool>(PHIVal, ValidForAllLocs);
2611 }
2612 
vlocJoin(MachineBasicBlock & MBB,LiveIdxT & VLOCOutLocs,LiveIdxT & VLOCInLocs,SmallPtrSet<const MachineBasicBlock *,16> * VLOCVisited,unsigned BBNum,const SmallSet<DebugVariable,4> & AllVars,ValueIDNum ** MOutLocs,ValueIDNum ** MInLocs,SmallPtrSet<const MachineBasicBlock *,8> & InScopeBlocks,SmallPtrSet<const MachineBasicBlock *,8> & BlocksToExplore,DenseMap<DebugVariable,DbgValue> & InLocsT)2613 std::tuple<bool, bool> InstrRefBasedLDV::vlocJoin(
2614     MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs,
2615     SmallPtrSet<const MachineBasicBlock *, 16> *VLOCVisited, unsigned BBNum,
2616     const SmallSet<DebugVariable, 4> &AllVars, ValueIDNum **MOutLocs,
2617     ValueIDNum **MInLocs,
2618     SmallPtrSet<const MachineBasicBlock *, 8> &InScopeBlocks,
2619     SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore,
2620     DenseMap<DebugVariable, DbgValue> &InLocsT) {
2621   bool DowngradeOccurred = false;
2622 
2623   // To emulate VarLocBasedImpl, process this block if it's not in scope but
2624   // _does_ assign a variable value. No live-ins for this scope are transferred
2625   // in though, so we can return immediately.
2626   if (InScopeBlocks.count(&MBB) == 0 && !ArtificialBlocks.count(&MBB)) {
2627     if (VLOCVisited)
2628       return std::tuple<bool, bool>(true, false);
2629     return std::tuple<bool, bool>(false, false);
2630   }
2631 
2632   LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
2633   bool Changed = false;
2634 
2635   // Find any live-ins computed in a prior iteration.
2636   auto ILSIt = VLOCInLocs.find(&MBB);
2637   assert(ILSIt != VLOCInLocs.end());
2638   auto &ILS = *ILSIt->second;
2639 
2640   // Order predecessors by RPOT order, for exploring them in that order.
2641   SmallVector<MachineBasicBlock *, 8> BlockOrders(MBB.predecessors());
2642 
2643   auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
2644     return BBToOrder[A] < BBToOrder[B];
2645   };
2646 
2647   llvm::sort(BlockOrders, Cmp);
2648 
2649   unsigned CurBlockRPONum = BBToOrder[&MBB];
2650 
2651   // Force a re-visit to loop heads in the first dataflow iteration.
2652   // FIXME: if we could "propose" Const values this wouldn't be needed,
2653   // because they'd need to be confirmed before being emitted.
2654   if (!BlockOrders.empty() &&
2655       BBToOrder[BlockOrders[BlockOrders.size() - 1]] >= CurBlockRPONum &&
2656       VLOCVisited)
2657     DowngradeOccurred = true;
2658 
2659   auto ConfirmValue = [&InLocsT](const DebugVariable &DV, DbgValue VR) {
2660     auto Result = InLocsT.insert(std::make_pair(DV, VR));
2661     (void)Result;
2662     assert(Result.second);
2663   };
2664 
2665   auto ConfirmNoVal = [&ConfirmValue, &MBB](const DebugVariable &Var, const DbgValueProperties &Properties) {
2666     DbgValue NoLocPHIVal(MBB.getNumber(), Properties, DbgValue::NoVal);
2667 
2668     ConfirmValue(Var, NoLocPHIVal);
2669   };
2670 
2671   // Attempt to join the values for each variable.
2672   for (auto &Var : AllVars) {
2673     // Collect all the DbgValues for this variable.
2674     SmallVector<InValueT, 8> Values;
2675     bool Bail = false;
2676     unsigned BackEdgesStart = 0;
2677     for (auto p : BlockOrders) {
2678       // If the predecessor isn't in scope / to be explored, we'll never be
2679       // able to join any locations.
2680       if (!BlocksToExplore.contains(p)) {
2681         Bail = true;
2682         break;
2683       }
2684 
2685       // Don't attempt to handle unvisited predecessors: they're implicitly
2686       // "unknown"s in the lattice.
2687       if (VLOCVisited && !VLOCVisited->count(p))
2688         continue;
2689 
2690       // If the predecessors OutLocs is absent, there's not much we can do.
2691       auto OL = VLOCOutLocs.find(p);
2692       if (OL == VLOCOutLocs.end()) {
2693         Bail = true;
2694         break;
2695       }
2696 
2697       // No live-out value for this predecessor also means we can't produce
2698       // a joined value.
2699       auto VIt = OL->second->find(Var);
2700       if (VIt == OL->second->end()) {
2701         Bail = true;
2702         break;
2703       }
2704 
2705       // Keep track of where back-edges begin in the Values vector. Relies on
2706       // BlockOrders being sorted by RPO.
2707       unsigned ThisBBRPONum = BBToOrder[p];
2708       if (ThisBBRPONum < CurBlockRPONum)
2709         ++BackEdgesStart;
2710 
2711       Values.push_back(std::make_pair(p, &VIt->second));
2712     }
2713 
2714     // If there were no values, or one of the predecessors couldn't have a
2715     // value, then give up immediately. It's not safe to produce a live-in
2716     // value.
2717     if (Bail || Values.size() == 0)
2718       continue;
2719 
2720     // Enumeration identifying the current state of the predecessors values.
2721     enum {
2722       Unset = 0,
2723       Agreed,       // All preds agree on the variable value.
2724       PropDisagree, // All preds agree, but the value kind is Proposed in some.
2725       BEDisagree,   // Only back-edges disagree on variable value.
2726       PHINeeded,    // Non-back-edge predecessors have conflicing values.
2727       NoSolution    // Conflicting Value metadata makes solution impossible.
2728     } OurState = Unset;
2729 
2730     // All (non-entry) blocks have at least one non-backedge predecessor.
2731     // Pick the variable value from the first of these, to compare against
2732     // all others.
2733     const DbgValue &FirstVal = *Values[0].second;
2734     const ValueIDNum &FirstID = FirstVal.ID;
2735 
2736     // Scan for variable values that can't be resolved: if they have different
2737     // DIExpressions, different indirectness, or are mixed constants /
2738     // non-constants.
2739     for (auto &V : Values) {
2740       if (V.second->Properties != FirstVal.Properties)
2741         OurState = NoSolution;
2742       if (V.second->Kind == DbgValue::Const && FirstVal.Kind != DbgValue::Const)
2743         OurState = NoSolution;
2744     }
2745 
2746     // Flags diagnosing _how_ the values disagree.
2747     bool NonBackEdgeDisagree = false;
2748     bool DisagreeOnPHINess = false;
2749     bool IDDisagree = false;
2750     bool Disagree = false;
2751     if (OurState == Unset) {
2752       for (auto &V : Values) {
2753         if (*V.second == FirstVal)
2754           continue; // No disagreement.
2755 
2756         Disagree = true;
2757 
2758         // Flag whether the value number actually diagrees.
2759         if (V.second->ID != FirstID)
2760           IDDisagree = true;
2761 
2762         // Distinguish whether disagreement happens in backedges or not.
2763         // Relies on Values (and BlockOrders) being sorted by RPO.
2764         unsigned ThisBBRPONum = BBToOrder[V.first];
2765         if (ThisBBRPONum < CurBlockRPONum)
2766           NonBackEdgeDisagree = true;
2767 
2768         // Is there a difference in whether the value is definite or only
2769         // proposed?
2770         if (V.second->Kind != FirstVal.Kind &&
2771             (V.second->Kind == DbgValue::Proposed ||
2772              V.second->Kind == DbgValue::Def) &&
2773             (FirstVal.Kind == DbgValue::Proposed ||
2774              FirstVal.Kind == DbgValue::Def))
2775           DisagreeOnPHINess = true;
2776       }
2777 
2778       // Collect those flags together and determine an overall state for
2779       // what extend the predecessors agree on a live-in value.
2780       if (!Disagree)
2781         OurState = Agreed;
2782       else if (!IDDisagree && DisagreeOnPHINess)
2783         OurState = PropDisagree;
2784       else if (!NonBackEdgeDisagree)
2785         OurState = BEDisagree;
2786       else
2787         OurState = PHINeeded;
2788     }
2789 
2790     // An extra indicator: if we only disagree on whether the value is a
2791     // Def, or proposed, then also flag whether that disagreement happens
2792     // in backedges only.
2793     bool PropOnlyInBEs = Disagree && !IDDisagree && DisagreeOnPHINess &&
2794                          !NonBackEdgeDisagree && FirstVal.Kind == DbgValue::Def;
2795 
2796     const auto &Properties = FirstVal.Properties;
2797 
2798     auto OldLiveInIt = ILS.find(Var);
2799     const DbgValue *OldLiveInLocation =
2800         (OldLiveInIt != ILS.end()) ? &OldLiveInIt->second : nullptr;
2801 
2802     bool OverRide = false;
2803     if (OurState == BEDisagree && OldLiveInLocation) {
2804       // Only backedges disagree: we can consider downgrading. If there was a
2805       // previous live-in value, use it to work out whether the current
2806       // incoming value represents a lattice downgrade or not.
2807       OverRide =
2808           vlocDowngradeLattice(MBB, *OldLiveInLocation, Values, CurBlockRPONum);
2809     }
2810 
2811     // Use the current state of predecessor agreement and other flags to work
2812     // out what to do next. Possibilities include:
2813     //  * Accept a value all predecessors agree on, or accept one that
2814     //    represents a step down the exploration lattice,
2815     //  * Use a PHI value number, if one can be found,
2816     //  * Propose a PHI value number, and see if it gets confirmed later,
2817     //  * Emit a 'NoVal' value, indicating we couldn't resolve anything.
2818     if (OurState == Agreed) {
2819       // Easiest solution: all predecessors agree on the variable value.
2820       ConfirmValue(Var, FirstVal);
2821     } else if (OurState == BEDisagree && OverRide) {
2822       // Only backedges disagree, and the other predecessors have produced
2823       // a new live-in value further down the exploration lattice.
2824       DowngradeOccurred = true;
2825       ConfirmValue(Var, FirstVal);
2826     } else if (OurState == PropDisagree) {
2827       // Predecessors agree on value, but some say it's only a proposed value.
2828       // Propagate it as proposed: unless it was proposed in this block, in
2829       // which case we're able to confirm the value.
2830       if (FirstID.getBlock() == (uint64_t)MBB.getNumber() && FirstID.isPHI()) {
2831         ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Def));
2832       } else if (PropOnlyInBEs) {
2833         // If only backedges disagree, a higher (in RPO) block confirmed this
2834         // location, and we need to propagate it into this loop.
2835         ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Def));
2836       } else {
2837         // Otherwise; a Def meeting a Proposed is still a Proposed.
2838         ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Proposed));
2839       }
2840     } else if ((OurState == PHINeeded || OurState == BEDisagree)) {
2841       // Predecessors disagree and can't be downgraded: this can only be
2842       // solved with a PHI. Use pickVPHILoc to go look for one.
2843       Optional<ValueIDNum> VPHI;
2844       bool AllEdgesVPHI = false;
2845       std::tie(VPHI, AllEdgesVPHI) =
2846           pickVPHILoc(MBB, Var, VLOCOutLocs, MOutLocs, MInLocs, BlockOrders);
2847 
2848       if (VPHI && AllEdgesVPHI) {
2849         // There's a PHI value that's valid for all predecessors -- we can use
2850         // it. If any of the non-backedge predecessors have proposed values
2851         // though, this PHI is also only proposed, until the predecessors are
2852         // confirmed.
2853         DbgValue::KindT K = DbgValue::Def;
2854         for (unsigned int I = 0; I < BackEdgesStart; ++I)
2855           if (Values[I].second->Kind == DbgValue::Proposed)
2856             K = DbgValue::Proposed;
2857 
2858         ConfirmValue(Var, DbgValue(*VPHI, Properties, K));
2859       } else if (VPHI) {
2860         // There's a PHI value, but it's only legal for backedges. Leave this
2861         // as a proposed PHI value: it might come back on the backedges,
2862         // and allow us to confirm it in the future.
2863         DbgValue NoBEValue = DbgValue(*VPHI, Properties, DbgValue::Proposed);
2864         ConfirmValue(Var, NoBEValue);
2865       } else {
2866         ConfirmNoVal(Var, Properties);
2867       }
2868     } else {
2869       // Otherwise: we don't know. Emit a "phi but no real loc" phi.
2870       ConfirmNoVal(Var, Properties);
2871     }
2872   }
2873 
2874   // Store newly calculated in-locs into VLOCInLocs, if they've changed.
2875   Changed = ILS != InLocsT;
2876   if (Changed)
2877     ILS = InLocsT;
2878 
2879   return std::tuple<bool, bool>(Changed, DowngradeOccurred);
2880 }
2881 
vlocDataflow(const LexicalScope * Scope,const DILocation * DILoc,const SmallSet<DebugVariable,4> & VarsWeCareAbout,SmallPtrSetImpl<MachineBasicBlock * > & AssignBlocks,LiveInsT & Output,ValueIDNum ** MOutLocs,ValueIDNum ** MInLocs,SmallVectorImpl<VLocTracker> & AllTheVLocs)2882 void InstrRefBasedLDV::vlocDataflow(
2883     const LexicalScope *Scope, const DILocation *DILoc,
2884     const SmallSet<DebugVariable, 4> &VarsWeCareAbout,
2885     SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, LiveInsT &Output,
2886     ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
2887     SmallVectorImpl<VLocTracker> &AllTheVLocs) {
2888   // This method is much like mlocDataflow: but focuses on a single
2889   // LexicalScope at a time. Pick out a set of blocks and variables that are
2890   // to have their value assignments solved, then run our dataflow algorithm
2891   // until a fixedpoint is reached.
2892   std::priority_queue<unsigned int, std::vector<unsigned int>,
2893                       std::greater<unsigned int>>
2894       Worklist, Pending;
2895   SmallPtrSet<MachineBasicBlock *, 16> OnWorklist, OnPending;
2896 
2897   // The set of blocks we'll be examining.
2898   SmallPtrSet<const MachineBasicBlock *, 8> BlocksToExplore;
2899 
2900   // The order in which to examine them (RPO).
2901   SmallVector<MachineBasicBlock *, 8> BlockOrders;
2902 
2903   // RPO ordering function.
2904   auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
2905     return BBToOrder[A] < BBToOrder[B];
2906   };
2907 
2908   LS.getMachineBasicBlocks(DILoc, BlocksToExplore);
2909 
2910   // A separate container to distinguish "blocks we're exploring" versus
2911   // "blocks that are potentially in scope. See comment at start of vlocJoin.
2912   SmallPtrSet<const MachineBasicBlock *, 8> InScopeBlocks = BlocksToExplore;
2913 
2914   // Old LiveDebugValues tracks variable locations that come out of blocks
2915   // not in scope, where DBG_VALUEs occur. This is something we could
2916   // legitimately ignore, but lets allow it for now.
2917   if (EmulateOldLDV)
2918     BlocksToExplore.insert(AssignBlocks.begin(), AssignBlocks.end());
2919 
2920   // We also need to propagate variable values through any artificial blocks
2921   // that immediately follow blocks in scope.
2922   DenseSet<const MachineBasicBlock *> ToAdd;
2923 
2924   // Helper lambda: For a given block in scope, perform a depth first search
2925   // of all the artificial successors, adding them to the ToAdd collection.
2926   auto AccumulateArtificialBlocks =
2927       [this, &ToAdd, &BlocksToExplore,
2928        &InScopeBlocks](const MachineBasicBlock *MBB) {
2929         // Depth-first-search state: each node is a block and which successor
2930         // we're currently exploring.
2931         SmallVector<std::pair<const MachineBasicBlock *,
2932                               MachineBasicBlock::const_succ_iterator>,
2933                     8>
2934             DFS;
2935 
2936         // Find any artificial successors not already tracked.
2937         for (auto *succ : MBB->successors()) {
2938           if (BlocksToExplore.count(succ) || InScopeBlocks.count(succ))
2939             continue;
2940           if (!ArtificialBlocks.count(succ))
2941             continue;
2942           DFS.push_back(std::make_pair(succ, succ->succ_begin()));
2943           ToAdd.insert(succ);
2944         }
2945 
2946         // Search all those blocks, depth first.
2947         while (!DFS.empty()) {
2948           const MachineBasicBlock *CurBB = DFS.back().first;
2949           MachineBasicBlock::const_succ_iterator &CurSucc = DFS.back().second;
2950           // Walk back if we've explored this blocks successors to the end.
2951           if (CurSucc == CurBB->succ_end()) {
2952             DFS.pop_back();
2953             continue;
2954           }
2955 
2956           // If the current successor is artificial and unexplored, descend into
2957           // it.
2958           if (!ToAdd.count(*CurSucc) && ArtificialBlocks.count(*CurSucc)) {
2959             DFS.push_back(std::make_pair(*CurSucc, (*CurSucc)->succ_begin()));
2960             ToAdd.insert(*CurSucc);
2961             continue;
2962           }
2963 
2964           ++CurSucc;
2965         }
2966       };
2967 
2968   // Search in-scope blocks and those containing a DBG_VALUE from this scope
2969   // for artificial successors.
2970   for (auto *MBB : BlocksToExplore)
2971     AccumulateArtificialBlocks(MBB);
2972   for (auto *MBB : InScopeBlocks)
2973     AccumulateArtificialBlocks(MBB);
2974 
2975   BlocksToExplore.insert(ToAdd.begin(), ToAdd.end());
2976   InScopeBlocks.insert(ToAdd.begin(), ToAdd.end());
2977 
2978   // Single block scope: not interesting! No propagation at all. Note that
2979   // this could probably go above ArtificialBlocks without damage, but
2980   // that then produces output differences from original-live-debug-values,
2981   // which propagates from a single block into many artificial ones.
2982   if (BlocksToExplore.size() == 1)
2983     return;
2984 
2985   // Picks out relevants blocks RPO order and sort them.
2986   for (auto *MBB : BlocksToExplore)
2987     BlockOrders.push_back(const_cast<MachineBasicBlock *>(MBB));
2988 
2989   llvm::sort(BlockOrders, Cmp);
2990   unsigned NumBlocks = BlockOrders.size();
2991 
2992   // Allocate some vectors for storing the live ins and live outs. Large.
2993   SmallVector<DenseMap<DebugVariable, DbgValue>, 32> LiveIns, LiveOuts;
2994   LiveIns.resize(NumBlocks);
2995   LiveOuts.resize(NumBlocks);
2996 
2997   // Produce by-MBB indexes of live-in/live-outs, to ease lookup within
2998   // vlocJoin.
2999   LiveIdxT LiveOutIdx, LiveInIdx;
3000   LiveOutIdx.reserve(NumBlocks);
3001   LiveInIdx.reserve(NumBlocks);
3002   for (unsigned I = 0; I < NumBlocks; ++I) {
3003     LiveOutIdx[BlockOrders[I]] = &LiveOuts[I];
3004     LiveInIdx[BlockOrders[I]] = &LiveIns[I];
3005   }
3006 
3007   for (auto *MBB : BlockOrders) {
3008     Worklist.push(BBToOrder[MBB]);
3009     OnWorklist.insert(MBB);
3010   }
3011 
3012   // Iterate over all the blocks we selected, propagating variable values.
3013   bool FirstTrip = true;
3014   SmallPtrSet<const MachineBasicBlock *, 16> VLOCVisited;
3015   while (!Worklist.empty() || !Pending.empty()) {
3016     while (!Worklist.empty()) {
3017       auto *MBB = OrderToBB[Worklist.top()];
3018       CurBB = MBB->getNumber();
3019       Worklist.pop();
3020 
3021       DenseMap<DebugVariable, DbgValue> JoinedInLocs;
3022 
3023       // Join values from predecessors. Updates LiveInIdx, and writes output
3024       // into JoinedInLocs.
3025       bool InLocsChanged, DowngradeOccurred;
3026       std::tie(InLocsChanged, DowngradeOccurred) = vlocJoin(
3027           *MBB, LiveOutIdx, LiveInIdx, (FirstTrip) ? &VLOCVisited : nullptr,
3028           CurBB, VarsWeCareAbout, MOutLocs, MInLocs, InScopeBlocks,
3029           BlocksToExplore, JoinedInLocs);
3030 
3031       bool FirstVisit = VLOCVisited.insert(MBB).second;
3032 
3033       // Always explore transfer function if inlocs changed, or if we've not
3034       // visited this block before.
3035       InLocsChanged |= FirstVisit;
3036 
3037       // If a downgrade occurred, book us in for re-examination on the next
3038       // iteration.
3039       if (DowngradeOccurred && OnPending.insert(MBB).second)
3040         Pending.push(BBToOrder[MBB]);
3041 
3042       if (!InLocsChanged)
3043         continue;
3044 
3045       // Do transfer function.
3046       auto &VTracker = AllTheVLocs[MBB->getNumber()];
3047       for (auto &Transfer : VTracker.Vars) {
3048         // Is this var we're mangling in this scope?
3049         if (VarsWeCareAbout.count(Transfer.first)) {
3050           // Erase on empty transfer (DBG_VALUE $noreg).
3051           if (Transfer.second.Kind == DbgValue::Undef) {
3052             JoinedInLocs.erase(Transfer.first);
3053           } else {
3054             // Insert new variable value; or overwrite.
3055             auto NewValuePair = std::make_pair(Transfer.first, Transfer.second);
3056             auto Result = JoinedInLocs.insert(NewValuePair);
3057             if (!Result.second)
3058               Result.first->second = Transfer.second;
3059           }
3060         }
3061       }
3062 
3063       // Did the live-out locations change?
3064       bool OLChanged = JoinedInLocs != *LiveOutIdx[MBB];
3065 
3066       // If they haven't changed, there's no need to explore further.
3067       if (!OLChanged)
3068         continue;
3069 
3070       // Commit to the live-out record.
3071       *LiveOutIdx[MBB] = JoinedInLocs;
3072 
3073       // We should visit all successors. Ensure we'll visit any non-backedge
3074       // successors during this dataflow iteration; book backedge successors
3075       // to be visited next time around.
3076       for (auto s : MBB->successors()) {
3077         // Ignore out of scope / not-to-be-explored successors.
3078         if (LiveInIdx.find(s) == LiveInIdx.end())
3079           continue;
3080 
3081         if (BBToOrder[s] > BBToOrder[MBB]) {
3082           if (OnWorklist.insert(s).second)
3083             Worklist.push(BBToOrder[s]);
3084         } else if (OnPending.insert(s).second && (FirstTrip || OLChanged)) {
3085           Pending.push(BBToOrder[s]);
3086         }
3087       }
3088     }
3089     Worklist.swap(Pending);
3090     std::swap(OnWorklist, OnPending);
3091     OnPending.clear();
3092     assert(Pending.empty());
3093     FirstTrip = false;
3094   }
3095 
3096   // Dataflow done. Now what? Save live-ins. Ignore any that are still marked
3097   // as being variable-PHIs, because those did not have their machine-PHI
3098   // value confirmed. Such variable values are places that could have been
3099   // PHIs, but are not.
3100   for (auto *MBB : BlockOrders) {
3101     auto &VarMap = *LiveInIdx[MBB];
3102     for (auto &P : VarMap) {
3103       if (P.second.Kind == DbgValue::Proposed ||
3104           P.second.Kind == DbgValue::NoVal)
3105         continue;
3106       Output[MBB->getNumber()].push_back(P);
3107     }
3108   }
3109 
3110   BlockOrders.clear();
3111   BlocksToExplore.clear();
3112 }
3113 
3114 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump_mloc_transfer(const MLocTransferMap & mloc_transfer) const3115 void InstrRefBasedLDV::dump_mloc_transfer(
3116     const MLocTransferMap &mloc_transfer) const {
3117   for (auto &P : mloc_transfer) {
3118     std::string foo = MTracker->LocIdxToName(P.first);
3119     std::string bar = MTracker->IDAsString(P.second);
3120     dbgs() << "Loc " << foo << " --> " << bar << "\n";
3121   }
3122 }
3123 #endif
3124 
emitLocations(MachineFunction & MF,LiveInsT SavedLiveIns,ValueIDNum ** MInLocs,DenseMap<DebugVariable,unsigned> & AllVarsNumbering)3125 void InstrRefBasedLDV::emitLocations(
3126     MachineFunction &MF, LiveInsT SavedLiveIns, ValueIDNum **MInLocs,
3127     DenseMap<DebugVariable, unsigned> &AllVarsNumbering) {
3128   TTracker = new TransferTracker(TII, MTracker, MF, *TRI, CalleeSavedRegs);
3129   unsigned NumLocs = MTracker->getNumLocs();
3130 
3131   // For each block, load in the machine value locations and variable value
3132   // live-ins, then step through each instruction in the block. New DBG_VALUEs
3133   // to be inserted will be created along the way.
3134   for (MachineBasicBlock &MBB : MF) {
3135     unsigned bbnum = MBB.getNumber();
3136     MTracker->reset();
3137     MTracker->loadFromArray(MInLocs[bbnum], bbnum);
3138     TTracker->loadInlocs(MBB, MInLocs[bbnum], SavedLiveIns[MBB.getNumber()],
3139                          NumLocs);
3140 
3141     CurBB = bbnum;
3142     CurInst = 1;
3143     for (auto &MI : MBB) {
3144       process(MI);
3145       TTracker->checkInstForNewValues(CurInst, MI.getIterator());
3146       ++CurInst;
3147     }
3148   }
3149 
3150   // We have to insert DBG_VALUEs in a consistent order, otherwise they appeaer
3151   // in DWARF in different orders. Use the order that they appear when walking
3152   // through each block / each instruction, stored in AllVarsNumbering.
3153   auto OrderDbgValues = [&](const MachineInstr *A,
3154                             const MachineInstr *B) -> bool {
3155     DebugVariable VarA(A->getDebugVariable(), A->getDebugExpression(),
3156                        A->getDebugLoc()->getInlinedAt());
3157     DebugVariable VarB(B->getDebugVariable(), B->getDebugExpression(),
3158                        B->getDebugLoc()->getInlinedAt());
3159     return AllVarsNumbering.find(VarA)->second <
3160            AllVarsNumbering.find(VarB)->second;
3161   };
3162 
3163   // Go through all the transfers recorded in the TransferTracker -- this is
3164   // both the live-ins to a block, and any movements of values that happen
3165   // in the middle.
3166   for (auto &P : TTracker->Transfers) {
3167     // Sort them according to appearance order.
3168     llvm::sort(P.Insts, OrderDbgValues);
3169     // Insert either before or after the designated point...
3170     if (P.MBB) {
3171       MachineBasicBlock &MBB = *P.MBB;
3172       for (auto *MI : P.Insts) {
3173         MBB.insert(P.Pos, MI);
3174       }
3175     } else {
3176       MachineBasicBlock &MBB = *P.Pos->getParent();
3177       for (auto *MI : P.Insts) {
3178         MBB.insertAfter(P.Pos, MI);
3179       }
3180     }
3181   }
3182 }
3183 
initialSetup(MachineFunction & MF)3184 void InstrRefBasedLDV::initialSetup(MachineFunction &MF) {
3185   // Build some useful data structures.
3186   auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
3187     if (const DebugLoc &DL = MI.getDebugLoc())
3188       return DL.getLine() != 0;
3189     return false;
3190   };
3191   // Collect a set of all the artificial blocks.
3192   for (auto &MBB : MF)
3193     if (none_of(MBB.instrs(), hasNonArtificialLocation))
3194       ArtificialBlocks.insert(&MBB);
3195 
3196   // Compute mappings of block <=> RPO order.
3197   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
3198   unsigned int RPONumber = 0;
3199   for (MachineBasicBlock *MBB : RPOT) {
3200     OrderToBB[RPONumber] = MBB;
3201     BBToOrder[MBB] = RPONumber;
3202     BBNumToRPO[MBB->getNumber()] = RPONumber;
3203     ++RPONumber;
3204   }
3205 }
3206 
3207 /// Calculate the liveness information for the given machine function and
3208 /// extend ranges across basic blocks.
ExtendRanges(MachineFunction & MF,TargetPassConfig * TPC)3209 bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
3210                                     TargetPassConfig *TPC) {
3211   // No subprogram means this function contains no debuginfo.
3212   if (!MF.getFunction().getSubprogram())
3213     return false;
3214 
3215   LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
3216   this->TPC = TPC;
3217 
3218   TRI = MF.getSubtarget().getRegisterInfo();
3219   TII = MF.getSubtarget().getInstrInfo();
3220   TFI = MF.getSubtarget().getFrameLowering();
3221   TFI->getCalleeSaves(MF, CalleeSavedRegs);
3222   LS.initialize(MF);
3223 
3224   MTracker =
3225       new MLocTracker(MF, *TII, *TRI, *MF.getSubtarget().getTargetLowering());
3226   VTracker = nullptr;
3227   TTracker = nullptr;
3228 
3229   SmallVector<MLocTransferMap, 32> MLocTransfer;
3230   SmallVector<VLocTracker, 8> vlocs;
3231   LiveInsT SavedLiveIns;
3232 
3233   int MaxNumBlocks = -1;
3234   for (auto &MBB : MF)
3235     MaxNumBlocks = std::max(MBB.getNumber(), MaxNumBlocks);
3236   assert(MaxNumBlocks >= 0);
3237   ++MaxNumBlocks;
3238 
3239   MLocTransfer.resize(MaxNumBlocks);
3240   vlocs.resize(MaxNumBlocks);
3241   SavedLiveIns.resize(MaxNumBlocks);
3242 
3243   initialSetup(MF);
3244 
3245   produceMLocTransferFunction(MF, MLocTransfer, MaxNumBlocks);
3246 
3247   // Allocate and initialize two array-of-arrays for the live-in and live-out
3248   // machine values. The outer dimension is the block number; while the inner
3249   // dimension is a LocIdx from MLocTracker.
3250   ValueIDNum **MOutLocs = new ValueIDNum *[MaxNumBlocks];
3251   ValueIDNum **MInLocs = new ValueIDNum *[MaxNumBlocks];
3252   unsigned NumLocs = MTracker->getNumLocs();
3253   for (int i = 0; i < MaxNumBlocks; ++i) {
3254     MOutLocs[i] = new ValueIDNum[NumLocs];
3255     MInLocs[i] = new ValueIDNum[NumLocs];
3256   }
3257 
3258   // Solve the machine value dataflow problem using the MLocTransfer function,
3259   // storing the computed live-ins / live-outs into the array-of-arrays. We use
3260   // both live-ins and live-outs for decision making in the variable value
3261   // dataflow problem.
3262   mlocDataflow(MInLocs, MOutLocs, MLocTransfer);
3263 
3264   // Walk back through each block / instruction, collecting DBG_VALUE
3265   // instructions and recording what machine value their operands refer to.
3266   for (auto &OrderPair : OrderToBB) {
3267     MachineBasicBlock &MBB = *OrderPair.second;
3268     CurBB = MBB.getNumber();
3269     VTracker = &vlocs[CurBB];
3270     VTracker->MBB = &MBB;
3271     MTracker->loadFromArray(MInLocs[CurBB], CurBB);
3272     CurInst = 1;
3273     for (auto &MI : MBB) {
3274       process(MI);
3275       ++CurInst;
3276     }
3277     MTracker->reset();
3278   }
3279 
3280   // Number all variables in the order that they appear, to be used as a stable
3281   // insertion order later.
3282   DenseMap<DebugVariable, unsigned> AllVarsNumbering;
3283 
3284   // Map from one LexicalScope to all the variables in that scope.
3285   DenseMap<const LexicalScope *, SmallSet<DebugVariable, 4>> ScopeToVars;
3286 
3287   // Map from One lexical scope to all blocks in that scope.
3288   DenseMap<const LexicalScope *, SmallPtrSet<MachineBasicBlock *, 4>>
3289       ScopeToBlocks;
3290 
3291   // Store a DILocation that describes a scope.
3292   DenseMap<const LexicalScope *, const DILocation *> ScopeToDILocation;
3293 
3294   // To mirror old LiveDebugValues, enumerate variables in RPOT order. Otherwise
3295   // the order is unimportant, it just has to be stable.
3296   for (unsigned int I = 0; I < OrderToBB.size(); ++I) {
3297     auto *MBB = OrderToBB[I];
3298     auto *VTracker = &vlocs[MBB->getNumber()];
3299     // Collect each variable with a DBG_VALUE in this block.
3300     for (auto &idx : VTracker->Vars) {
3301       const auto &Var = idx.first;
3302       const DILocation *ScopeLoc = VTracker->Scopes[Var];
3303       assert(ScopeLoc != nullptr);
3304       auto *Scope = LS.findLexicalScope(ScopeLoc);
3305 
3306       // No insts in scope -> shouldn't have been recorded.
3307       assert(Scope != nullptr);
3308 
3309       AllVarsNumbering.insert(std::make_pair(Var, AllVarsNumbering.size()));
3310       ScopeToVars[Scope].insert(Var);
3311       ScopeToBlocks[Scope].insert(VTracker->MBB);
3312       ScopeToDILocation[Scope] = ScopeLoc;
3313     }
3314   }
3315 
3316   // OK. Iterate over scopes: there might be something to be said for
3317   // ordering them by size/locality, but that's for the future. For each scope,
3318   // solve the variable value problem, producing a map of variables to values
3319   // in SavedLiveIns.
3320   for (auto &P : ScopeToVars) {
3321     vlocDataflow(P.first, ScopeToDILocation[P.first], P.second,
3322                  ScopeToBlocks[P.first], SavedLiveIns, MOutLocs, MInLocs,
3323                  vlocs);
3324   }
3325 
3326   // Using the computed value locations and variable values for each block,
3327   // create the DBG_VALUE instructions representing the extended variable
3328   // locations.
3329   emitLocations(MF, SavedLiveIns, MInLocs, AllVarsNumbering);
3330 
3331   for (int Idx = 0; Idx < MaxNumBlocks; ++Idx) {
3332     delete[] MOutLocs[Idx];
3333     delete[] MInLocs[Idx];
3334   }
3335   delete[] MOutLocs;
3336   delete[] MInLocs;
3337 
3338   // Did we actually make any changes? If we created any DBG_VALUEs, then yes.
3339   bool Changed = TTracker->Transfers.size() != 0;
3340 
3341   delete MTracker;
3342   delete TTracker;
3343   MTracker = nullptr;
3344   VTracker = nullptr;
3345   TTracker = nullptr;
3346 
3347   ArtificialBlocks.clear();
3348   OrderToBB.clear();
3349   BBToOrder.clear();
3350   BBNumToRPO.clear();
3351   DebugInstrNumToInstr.clear();
3352 
3353   return Changed;
3354 }
3355 
makeInstrRefBasedLiveDebugValues()3356 LDVImpl *llvm::makeInstrRefBasedLiveDebugValues() {
3357   return new InstrRefBasedLDV();
3358 }
3359