1//===-- WebAssemblyDebugValueManager.cpp - WebAssembly DebugValue Manager -===//
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///
9/// \file
10/// This file implements the manager for MachineInstr DebugValues.
11///
12//===----------------------------------------------------------------------===//
13
14#include "WebAssemblyDebugValueManager.h"
15#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
16#include "WebAssembly.h"
17#include "WebAssemblyMachineFunctionInfo.h"
18#include "llvm/ADT/DenseSet.h"
19#include "llvm/CodeGen/MachineInstr.h"
20#include "llvm/CodeGen/MachineRegisterInfo.h"
21#include "llvm/IR/DebugInfoMetadata.h"
22#include "llvm/IR/Function.h"
23
24using namespace llvm;
25
26WebAssemblyDebugValueManager::WebAssemblyDebugValueManager(MachineInstr *Def)
27 : Def(Def) {
28 if (!Def->getMF()->getFunction().getSubprogram())
29 return;
30
31 // This code differs from MachineInstr::collectDebugValues in that it scans
32 // all users in the BB, not just contiguous DBG_VALUEs, until another
33 // definition to the same register is encountered.
34 if (!Def->getOperand(i: 0).isReg())
35 return;
36 CurrentReg = Def->getOperand(i: 0).getReg();
37
38 // Collect all the uses of this def.
39 MachineRegisterInfo &MRI = Def->getMF()->getRegInfo();
40 MachineBasicBlock *MBB = Def->getParent();
41 unsigned RemainingUses = 0;
42 for (MachineInstr &MI : MRI.use_instructions(Reg: CurrentReg))
43 if (MI.isDebugValue() && MI.getParent() == MBB)
44 ++RemainingUses;
45 if (RemainingUses == 0)
46 return;
47
48 // Scan forward to collect DBG_VALUEs in block order.
49 // Scan backward at the same pace to account for earlier uses and stop once
50 // all possible matches have been found.
51 // Only the forward scan collects DBG_VALUEs.
52 MachineBasicBlock::iterator Down = std::next(x: Def->getIterator()),
53 DownEnd = MBB->end(), Up = Def->getIterator(),
54 UpBegin = MBB->begin();
55 while (RemainingUses > 0 && Down != DownEnd) {
56 if (Down->isDebugValue()) {
57 if (Down->hasDebugOperandForReg(Reg: CurrentReg)) {
58 DbgValues.push_back(Elt: &*Down);
59 --RemainingUses;
60 }
61 } else if (Down->definesRegister(Reg: CurrentReg, /*TRI=*/nullptr)) {
62 break;
63 }
64 ++Down;
65 if (Up != UpBegin) {
66 --Up;
67 if (Up->isDebugValue() && Up->hasDebugOperandForReg(Reg: CurrentReg))
68 --RemainingUses;
69 }
70 }
71}
72
73// Returns true if both A and B are the same CONST_I32/I64/F32/F64 instructions.
74// Doesn't include CONST_V128.
75static bool isSameScalarConst(const MachineInstr *A, const MachineInstr *B) {
76 if (A->getOpcode() != B->getOpcode() ||
77 !WebAssembly::isScalarConst(Opc: A->getOpcode()) ||
78 !WebAssembly::isScalarConst(Opc: B->getOpcode()))
79 return false;
80 const MachineOperand &OpA = A->getOperand(i: 1), &OpB = B->getOperand(i: 1);
81 if ((OpA.isImm() && OpB.isImm() && OpA.getImm() == OpB.getImm()) ||
82 (OpA.isFPImm() && OpB.isFPImm() && OpA.getFPImm() == OpB.getFPImm()) ||
83 (OpA.isGlobal() && OpB.isGlobal() && OpA.getGlobal() == OpB.getGlobal()))
84 return true;
85 return false;
86}
87
88SmallVector<MachineInstr *, 1>
89WebAssemblyDebugValueManager::getSinkableDebugValues(
90 MachineInstr *Insert) const {
91 if (DbgValues.empty())
92 return {};
93
94 // If Def and Insert are in different BBs, we only handle a simple case in
95 // which Insert's BB is a successor of Def's BB.
96 if (Def->getParent() != Insert->getParent() &&
97 !Def->getParent()->isSuccessor(MBB: Insert->getParent()))
98 return {};
99
100 SmallDenseSet<DebugVariable, 4> OurVars;
101 for (MachineInstr *DV : DbgValues)
102 OurVars.insert(V: DebugVariable(DV->getDebugVariable(),
103 DV->getDebugExpression(),
104 DV->getDebugLoc()->getInlinedAt()));
105
106 SmallDenseMap<DebugVariable, SmallVector<MachineInstr *, 2>>
107 SeenDbgVarToDbgValues;
108 auto RecordDbgValue = [&](MachineInstr &MI) {
109 if (!MI.isDebugValue())
110 return;
111 DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
112 MI.getDebugLoc()->getInlinedAt());
113 if (OurVars.contains(V: Var) && !llvm::is_contained(Range: DbgValues, Element: &MI))
114 SeenDbgVarToDbgValues[Var].push_back(Elt: &MI);
115 };
116
117 if (Def->getParent() == Insert->getParent()) {
118 // Search both ways to quickly determine whether Insert follows Def.
119 // Only the forward scan collects DBG_VALUEs.
120 MachineBasicBlock::iterator Down = std::next(x: Def->getIterator()),
121 DownEnd = Def->getParent()->end(),
122 Up = Def->getIterator(),
123 UpBegin = Def->getParent()->begin();
124 bool DefFirst = false;
125 while (Down != DownEnd || Up != UpBegin) {
126 if (Down != DownEnd) {
127 if (&*Down == Insert) {
128 DefFirst = true;
129 break;
130 }
131 RecordDbgValue(*Down);
132 ++Down;
133 }
134 if (Up != UpBegin) {
135 --Up;
136 if (&*Up == Insert)
137 break;
138 }
139 }
140 if (!DefFirst) // Not a sink
141 return {};
142
143 } else { // Def and Insert are in different BBs
144 // Gather DBG_VALUEs between 'Def~Def BB's end' and
145 // 'Insert BB's begin~Insert'
146 for (MachineBasicBlock::iterator MI = std::next(x: Def->getIterator()),
147 ME = Def->getParent()->end();
148 MI != ME; ++MI)
149 RecordDbgValue(*MI);
150 for (MachineBasicBlock::iterator MI = Insert->getParent()->begin(),
151 ME = Insert->getIterator();
152 MI != ME; ++MI)
153 RecordDbgValue(*MI);
154 }
155
156 // Gather sinkable DBG_VALUEs. We should not sink a DBG_VALUE if there is
157 // another DBG_VALUE between Def and Insert referring to the same
158 // DebugVariable. For example,
159 // %0 = someinst
160 // DBG_VALUE %0, !"a", !DIExpression() // Should not sink with %0
161 // %1 = anotherinst
162 // DBG_VALUE %1, !"a", !DIExpression()
163 // Where if %0 were to sink, the DBG_VAUE should not sink with it, as that
164 // would re-order assignments.
165 SmallVector<MachineInstr *, 1> SinkableDbgValues;
166 MachineRegisterInfo &MRI = Def->getParent()->getParent()->getRegInfo();
167 for (auto *DV : DbgValues) {
168 DebugVariable Var(DV->getDebugVariable(), DV->getDebugExpression(),
169 DV->getDebugLoc()->getInlinedAt());
170 auto It = SeenDbgVarToDbgValues.find(Val: Var);
171 if (It == SeenDbgVarToDbgValues.end()) {
172 SinkableDbgValues.push_back(Elt: DV);
173 continue;
174 }
175 if (!WebAssembly::isScalarConst(Opc: Def->getOpcode()))
176 continue;
177 auto &OverlappingDbgValues = It->second;
178 bool Sinkable = true;
179 for (auto *OverlappingDV : OverlappingDbgValues) {
180 MachineOperand &DbgOp = OverlappingDV->getDebugOperand(Index: 0);
181 if (!DbgOp.isReg()) {
182 Sinkable = false;
183 break;
184 }
185 Register OtherReg = DbgOp.getReg();
186 MachineInstr *OtherDef = MRI.getUniqueVRegDef(Reg: OtherReg);
187 // We have an exception to allow encountering other DBG_VALUEs with the
188 // same DebugVariables, only when they are referring to the same scalar
189 // CONST instruction. For example,
190 // %0 = CONST_I32 1
191 // DBG_VALUE %0, !"a", !DIExpression() // Can sink with %0
192 // %1 = CONST_I32 1
193 // DBG_VALUE %1, !"a", !DIExpression()
194 // When %0 were to be sunk/cloneed, the DBG_VALUE can be sunk/cloned with
195 // it because even though the second DBG_VALUE refers to the same
196 // DebugVariable, its value in effect is the same CONST instruction.
197 //
198 // This is to allow a case that can happen with RegStackify's
199 // "rematerializeCheapDef". For example, we have this program with two
200 // BBs:
201 // bb0:
202 // %0 = CONST_I32 1
203 // DBG_VALUE %0, !"a", ...
204 // ...
205 // INST0 ..., $0 ...
206 // bb1:
207 // INST1 ..., $0 ...
208 // INST2 ..., $0 ...
209 //
210 // We process bb0 first. Because %0 is used multiple times, %0 is cloned
211 // before INST0:
212 // bb0:
213 // %0 = CONST_I32 1
214 // DBG_VALUE %0, !"a", ...
215 // ...
216 // %1 = CONST_I32 1
217 // DBG_VALUE %1, !"a", ...
218 // INST0 ..., $1 ...
219 //
220 // And when we process bb1, we clone %0 and its DBG_VALUE again:
221 // bb0:
222 // %0 = CONST_I32 1
223 // DBG_VALUE %0, !"a", ...
224 // ...
225 // %1 = CONST_I32 1
226 // DBG_VALUE %1, !"a", ...
227 // INST0 ..., $1 ...
228 // bb1:
229 // %2 = CONST_I32 1
230 // DBG_VALUE %2, !"a", ... // !!!
231 // INST1 ..., $2 ...
232 // %3 = CONST_I32 1
233 // DBG_VALUE %3, !"a", ... // !!!
234 // INST2 ..., $3 ...
235 //
236 // But (without this exception) the cloned DBG_VALUEs marked with !!! are
237 // not possible to be cloned, because there is a previously cloned
238 // 'DBG_VALUE %1, !"a"' at the end of bb0 referring to the same
239 // DebugVariable "a". But in this case they are OK to be cloned, because
240 // the interfering DBG_VALUE is pointing to the same 'CONST_I32 1',
241 // because it was cloned from the same instruction.
242 if (!OtherDef || !isSameScalarConst(A: Def, B: OtherDef)) {
243 Sinkable = false;
244 break;
245 }
246 }
247 if (Sinkable)
248 SinkableDbgValues.push_back(Elt: DV);
249 }
250 return SinkableDbgValues;
251}
252
253// Returns true if the insertion point is the same as the current place.
254// Following DBG_VALUEs for 'Def' are ignored.
255bool WebAssemblyDebugValueManager::isInsertSamePlace(
256 MachineInstr *Insert) const {
257 if (Def->getParent() != Insert->getParent())
258 return false;
259 for (MachineBasicBlock::iterator MI = std::next(x: Def->getIterator()),
260 ME = Insert;
261 MI != ME; ++MI) {
262 if (!llvm::is_contained(Range: DbgValues, Element: MI)) {
263 return false;
264 }
265 }
266 return true;
267}
268
269// Returns true if any instruction in MBB has the same debug location as DL.
270// Also returns true if DL is an empty location.
271static bool hasSameDebugLoc(const MachineBasicBlock *MBB, DebugLoc DL) {
272 for (const auto &MI : *MBB)
273 if (MI.getDebugLoc() == DL)
274 return true;
275 return false;
276}
277
278// Sink 'Def', and also sink its eligible DBG_VALUEs to the place before
279// 'Insert'. Convert the original DBG_VALUEs into undefs.
280//
281// For DBG_VALUEs to sink properly, if 'Def' and 'Insert' are within the same
282// BB, 'Insert' should be below 'Def'; if they are in different BBs, 'Insert'
283// should be in one of 'Def's BBs successors. Def will be sunk regardless of the
284// location.
285//
286// This DebugValueManager's new Def and DbgValues will be updated to the newly
287// sinked Def + DBG_VALUEs.
288void WebAssemblyDebugValueManager::sink(MachineInstr *Insert) {
289 // In case Def is requested to be sunk to
290 // the same place, we don't need to do anything. If we actually do the sink,
291 // it will create unnecessary undef DBG_VALUEs. For example, if the original
292 // code is:
293 // %0 = someinst // Def
294 // DBG_VALUE %0, ...
295 // %1 = anotherinst // Insert
296 //
297 // If we actually sink %0 and the following DBG_VALUE and setting the original
298 // DBG_VALUE undef, the result will be:
299 // DBG_VALUE %noreg, ... // Unnecessary!
300 // %0 = someinst // Def
301 // DBG_VALUE %0, ...
302 // %1 = anotherinst // Insert
303 if (isInsertSamePlace(Insert))
304 return;
305
306 MachineBasicBlock *MBB = Insert->getParent();
307 MachineFunction *MF = MBB->getParent();
308
309 // Get the list of sinkable DBG_VALUEs. This should be done before sinking
310 // Def, because we need to examine instructions between Def and Insert.
311 SmallVector<MachineInstr *, 1> SinkableDbgValues =
312 getSinkableDebugValues(Insert);
313
314 // Sink Def first.
315 //
316 // When moving to a different BB, we preserve the debug loc only if the
317 // destination BB contains the same location. See
318 // https://llvm.org/docs/HowToUpdateDebugInfo.html#when-to-preserve-an-instruction-location.
319 if (Def->getParent() != MBB && !hasSameDebugLoc(MBB, DL: Def->getDebugLoc()))
320 Def->setDebugLoc(DebugLoc());
321 MBB->splice(Where: Insert, Other: Def->getParent(), From: Def);
322
323 if (DbgValues.empty())
324 return;
325
326 // Clone sinkable DBG_VALUEs and insert them.
327 SmallVector<MachineInstr *, 1> NewDbgValues;
328 for (MachineInstr *DV : SinkableDbgValues) {
329 MachineInstr *Clone = MF->CloneMachineInstr(Orig: DV);
330 MBB->insert(I: Insert, MI: Clone);
331 NewDbgValues.push_back(Elt: Clone);
332 }
333
334 // When sinking a Def and its DBG_VALUEs, we shouldn't just remove the
335 // original DBG_VALUE instructions; we should set them to undef not to create
336 // an impossible combination of variable assignments in the original program.
337 // For example, this is the original program in order:
338 // %0 = CONST_I32 0
339 // DBG_VALUE %0, !"a", !DIExpression() // a = 0, b = ?
340 // %1 = CONST_I32 1
341 // DBG_VALUE %1, !"b", !DIExpression() // a = 0, b = 1
342 // %2 = CONST_I32 2
343 // DBG_VALUE %2, !"a", !DIExpression() // a = 2, b = 1
344 // %3 = CONST_I32 3
345 // DBG_VALUE %3, !"b", !DIExpression() // a = 2, b = 3
346 //
347 // If %2 were to sink below %3, if we just sink DBG_VALUE %1 with it, the
348 // debug info will show the variable "b" is updated to 2, creating the
349 // variable assignment combination of (a = 0, b = 3), which is not possible in
350 // the original program:
351 // %0 = CONST_I32 0
352 // DBG_VALUE %0, !"a", !DIExpression() // a = 0, b = ?
353 // %1 = CONST_I32 1
354 // DBG_VALUE %1, !"b", !DIExpression() // a = 0, b = 1
355 // %3 = CONST_I32 3
356 // DBG_VALUE %3, !"b", !DIExpression() // a = 0, b = 3 (Incorrect!)
357 // %2 = CONST_I32 2
358 // DBG_VALUE %2, !"a", !DIExpression() // a = 2, b = 3
359 //
360 // To fix this,we leave an undef DBG_VALUE in its original place, so that the
361 // result will be
362 // %0 = CONST_I32 0
363 // DBG_VALUE %0, !"a", !DIExpression() // a = 0, b = ?
364 // %1 = CONST_I32 1
365 // DBG_VALUE %1, !"b", !DIExpression() // a = 0, b = 1
366 // DBG_VALUE $noreg, !"a", !DIExpression() // a = ?, b = 1
367 // %3 = CONST_I32 3
368 // DBG_VALUE %3, !"b", !DIExpression() // a = ?, b = 3
369 // %2 = CONST_I32 2
370 // DBG_VALUE %2, !"a", !DIExpression() // a = 2, b = 3
371 // Now in the middle "a" will be shown as "optimized out", but it wouldn't
372 // show the impossible combination of (a = 0, b = 3).
373 for (MachineInstr *DV : DbgValues)
374 DV->setDebugValueUndef();
375
376 DbgValues.swap(RHS&: NewDbgValues);
377}
378
379// Clone 'Def', and also clone its eligible DBG_VALUEs to the place before
380// 'Insert'.
381//
382// For DBG_VALUEs to be cloned properly, if 'Def' and 'Insert' are within the
383// same BB, 'Insert' should be below 'Def'; if they are in different BBs,
384// 'Insert' should be in one of 'Def's BBs successors. Def will be cloned
385// regardless of the location.
386//
387// If NewReg is not $noreg, the newly cloned DBG_VALUEs will have the new
388// register as its operand.
389void WebAssemblyDebugValueManager::cloneSink(MachineInstr *Insert,
390 Register NewReg,
391 bool CloneDef) const {
392 MachineBasicBlock *MBB = Insert->getParent();
393 MachineFunction *MF = MBB->getParent();
394
395 SmallVector<MachineInstr *> SinkableDbgValues =
396 getSinkableDebugValues(Insert);
397
398 // Clone Def first.
399 if (CloneDef) {
400 MachineInstr *Clone = MF->CloneMachineInstr(Orig: Def);
401 // When cloning to a different BB, we preserve the debug loc only if the
402 // destination BB contains the same location. See
403 // https://llvm.org/docs/HowToUpdateDebugInfo.html#when-to-preserve-an-instruction-location.
404 if (Def->getParent() != MBB && !hasSameDebugLoc(MBB, DL: Def->getDebugLoc()))
405 Clone->setDebugLoc(DebugLoc());
406 if (NewReg != CurrentReg && NewReg.isValid())
407 Clone->getOperand(i: 0).setReg(NewReg);
408 MBB->insert(I: Insert, MI: Clone);
409 }
410
411 if (DbgValues.empty())
412 return;
413
414 // Clone sinkable DBG_VALUEs and insert them.
415 SmallVector<MachineInstr *, 1> NewDbgValues;
416 for (MachineInstr *DV : SinkableDbgValues) {
417 MachineInstr *Clone = MF->CloneMachineInstr(Orig: DV);
418 MBB->insert(I: Insert, MI: Clone);
419 NewDbgValues.push_back(Elt: Clone);
420 }
421
422 if (NewReg != CurrentReg && NewReg.isValid())
423 for (auto *DBI : NewDbgValues)
424 for (auto &MO : DBI->getDebugOperandsForReg(Reg: CurrentReg))
425 MO.setReg(NewReg);
426}
427
428// Update the register for Def and DBG_VALUEs.
429void WebAssemblyDebugValueManager::updateReg(Register Reg) {
430 if (Reg != CurrentReg && Reg.isValid()) {
431 for (auto *DBI : DbgValues)
432 for (auto &MO : DBI->getDebugOperandsForReg(Reg: CurrentReg))
433 MO.setReg(Reg);
434 CurrentReg = Reg;
435 Def->getOperand(i: 0).setReg(Reg);
436 }
437}
438
439void WebAssemblyDebugValueManager::replaceWithLocal(unsigned LocalId) {
440 for (auto *DBI : DbgValues) {
441 auto IndexType = DBI->isIndirectDebugValue()
442 ? llvm::WebAssembly::TI_LOCAL_INDIRECT
443 : llvm::WebAssembly::TI_LOCAL;
444 for (auto &MO : DBI->getDebugOperandsForReg(Reg: CurrentReg))
445 MO.ChangeToTargetIndex(Idx: IndexType, Offset: LocalId);
446 }
447}
448
449// Remove Def, and set its DBG_VALUEs to undef.
450void WebAssemblyDebugValueManager::removeDef() {
451 Def->removeFromParent();
452 for (MachineInstr *DV : DbgValues)
453 DV->setDebugValueUndef();
454}
455