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