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