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