1//===-- WebAssemblyRegStackify.cpp - Register Stackification --------------===//
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 a register stacking pass.
11///
12/// This pass reorders instructions to put register uses and defs in an order
13/// such that they form single-use expression trees. Registers fitting this form
14/// are then marked as "stackified", meaning references to them are replaced by
15/// "push" and "pop" from the value stack.
16///
17/// This is primarily a code size optimization, since temporary values on the
18/// value stack don't need to be named.
19///
20//===----------------------------------------------------------------------===//
21
22#include "MCTargetDesc/WebAssemblyMCTargetDesc.h" // for WebAssembly::ARGUMENT_*
23#include "WebAssembly.h"
24#include "WebAssemblyDebugValueManager.h"
25#include "WebAssemblyMachineFunctionInfo.h"
26#include "WebAssemblySubtarget.h"
27#include "WebAssemblyUtilities.h"
28#include "llvm/CodeGen/LiveIntervals.h"
29#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
30#include "llvm/CodeGen/MachineDominators.h"
31#include "llvm/CodeGen/MachineFunctionAnalysisManager.h"
32#include "llvm/CodeGen/MachineInstrBuilder.h"
33#include "llvm/CodeGen/MachinePassManager.h"
34#include "llvm/CodeGen/MachineRegisterInfo.h"
35#include "llvm/CodeGen/Passes.h"
36#include "llvm/CodeGen/SlotIndexes.h"
37#include "llvm/IR/Analysis.h"
38#include "llvm/IR/GlobalAlias.h"
39#include "llvm/Support/Debug.h"
40#include "llvm/Support/raw_ostream.h"
41#include <iterator>
42using namespace llvm;
43
44#define DEBUG_TYPE "wasm-reg-stackify"
45
46namespace {
47class WebAssemblyRegStackifyLegacy final : public MachineFunctionPass {
48 bool Optimize;
49
50 StringRef getPassName() const override {
51 return "WebAssembly Register Stackify";
52 }
53
54 void getAnalysisUsage(AnalysisUsage &AU) const override {
55 AU.setPreservesCFG();
56 if (Optimize) {
57 AU.addRequired<LiveIntervalsWrapperPass>();
58 AU.addRequired<MachineDominatorTreeWrapperPass>();
59 }
60 AU.addPreserved<SlotIndexesWrapperPass>();
61 AU.addPreserved<LiveIntervalsWrapperPass>();
62 MachineFunctionPass::getAnalysisUsage(AU);
63 }
64
65 bool runOnMachineFunction(MachineFunction &MF) override;
66
67public:
68 static char ID; // Pass identification, replacement for typeid
69 WebAssemblyRegStackifyLegacy(CodeGenOptLevel OptLevel)
70 : MachineFunctionPass(ID), Optimize(OptLevel != CodeGenOptLevel::None) {}
71 WebAssemblyRegStackifyLegacy()
72 : WebAssemblyRegStackifyLegacy(CodeGenOptLevel::Default) {}
73};
74} // end anonymous namespace
75
76char WebAssemblyRegStackifyLegacy::ID = 0;
77INITIALIZE_PASS(WebAssemblyRegStackifyLegacy, DEBUG_TYPE,
78 "Reorder instructions to use the WebAssembly value stack",
79 false, false)
80
81FunctionPass *
82llvm::createWebAssemblyRegStackifyLegacyPass(CodeGenOptLevel OptLevel) {
83 return new WebAssemblyRegStackifyLegacy(OptLevel);
84}
85
86// Decorate the given instruction with implicit operands that enforce the
87// expression stack ordering constraints for an instruction which is on
88// the expression stack.
89static void imposeStackOrdering(MachineInstr *MI) {
90 // Write the opaque VALUE_STACK register.
91 if (!MI->definesRegister(Reg: WebAssembly::VALUE_STACK, /*TRI=*/nullptr))
92 MI->addOperand(Op: MachineOperand::CreateReg(Reg: WebAssembly::VALUE_STACK,
93 /*isDef=*/true,
94 /*isImp=*/true));
95
96 // Also read the opaque VALUE_STACK register.
97 if (!MI->readsRegister(Reg: WebAssembly::VALUE_STACK, /*TRI=*/nullptr))
98 MI->addOperand(Op: MachineOperand::CreateReg(Reg: WebAssembly::VALUE_STACK,
99 /*isDef=*/false,
100 /*isImp=*/true));
101}
102
103// Convert an IMPLICIT_DEF instruction into an instruction which defines
104// a constant zero value.
105static void convertImplicitDefToConstZero(MachineInstr *MI,
106 MachineRegisterInfo &MRI,
107 const TargetInstrInfo *TII,
108 MachineFunction &MF) {
109 assert(MI->getOpcode() == TargetOpcode::IMPLICIT_DEF);
110
111 const auto *RegClass = MRI.getRegClass(Reg: MI->getOperand(i: 0).getReg());
112 if (RegClass == &WebAssembly::I32RegClass) {
113 MI->setDesc(TII->get(Opcode: WebAssembly::CONST_I32));
114 MI->addOperand(Op: MachineOperand::CreateImm(Val: 0));
115 } else if (RegClass == &WebAssembly::I64RegClass) {
116 MI->setDesc(TII->get(Opcode: WebAssembly::CONST_I64));
117 MI->addOperand(Op: MachineOperand::CreateImm(Val: 0));
118 } else if (RegClass == &WebAssembly::F32RegClass) {
119 MI->setDesc(TII->get(Opcode: WebAssembly::CONST_F32));
120 auto *Val = cast<ConstantFP>(Val: Constant::getNullValue(
121 Ty: Type::getFloatTy(C&: MF.getFunction().getContext())));
122 MI->addOperand(Op: MachineOperand::CreateFPImm(CFP: Val));
123 } else if (RegClass == &WebAssembly::F64RegClass) {
124 MI->setDesc(TII->get(Opcode: WebAssembly::CONST_F64));
125 auto *Val = cast<ConstantFP>(Val: Constant::getNullValue(
126 Ty: Type::getDoubleTy(C&: MF.getFunction().getContext())));
127 MI->addOperand(Op: MachineOperand::CreateFPImm(CFP: Val));
128 } else if (RegClass == &WebAssembly::V128RegClass) {
129 MI->setDesc(TII->get(Opcode: WebAssembly::CONST_V128_I64x2));
130 MI->addOperand(Op: MachineOperand::CreateImm(Val: 0));
131 MI->addOperand(Op: MachineOperand::CreateImm(Val: 0));
132 } else {
133 llvm_unreachable("Unexpected reg class");
134 }
135}
136
137// Determine whether a call to the callee referenced by
138// MI->getOperand(CalleeOpNo) reads memory, writes memory, and/or has side
139// effects.
140static void queryCallee(const MachineInstr &MI, bool &Read, bool &Write,
141 bool &Effects, bool &StackPointer) {
142 // All calls can use the stack pointer.
143 StackPointer = true;
144
145 const MachineOperand &MO = WebAssembly::getCalleeOp(MI);
146 if (MO.isGlobal()) {
147 const Constant *GV = MO.getGlobal();
148 if (const auto *GA = dyn_cast<GlobalAlias>(Val: GV))
149 if (!GA->isInterposable())
150 GV = GA->getAliasee();
151
152 if (const auto *F = dyn_cast<Function>(Val: GV)) {
153 if (!F->doesNotThrow())
154 Effects = true;
155 if (F->doesNotAccessMemory())
156 return;
157 if (F->onlyReadsMemory()) {
158 Read = true;
159 return;
160 }
161 }
162 }
163
164 // Assume the worst.
165 Write = true;
166 Read = true;
167 Effects = true;
168}
169
170// Determine whether MI reads memory, writes memory, has side effects,
171// and/or uses the stack pointer value.
172static void query(const MachineInstr &MI, bool &Read, bool &Write,
173 bool &Effects, bool &StackPointer) {
174 assert(!MI.isTerminator());
175
176 if (MI.isDebugInstr() || MI.isPosition())
177 return;
178
179 // Check for loads.
180 if (MI.mayLoad() && !MI.isDereferenceableInvariantLoad())
181 Read = true;
182
183 // Check for stores.
184 if (MI.mayStore()) {
185 Write = true;
186 } else if (MI.hasOrderedMemoryRef()) {
187 switch (MI.getOpcode()) {
188 case WebAssembly::DIV_S_I32:
189 case WebAssembly::DIV_S_I64:
190 case WebAssembly::REM_S_I32:
191 case WebAssembly::REM_S_I64:
192 case WebAssembly::DIV_U_I32:
193 case WebAssembly::DIV_U_I64:
194 case WebAssembly::REM_U_I32:
195 case WebAssembly::REM_U_I64:
196 case WebAssembly::I32_TRUNC_S_F32:
197 case WebAssembly::I64_TRUNC_S_F32:
198 case WebAssembly::I32_TRUNC_S_F64:
199 case WebAssembly::I64_TRUNC_S_F64:
200 case WebAssembly::I32_TRUNC_U_F32:
201 case WebAssembly::I64_TRUNC_U_F32:
202 case WebAssembly::I32_TRUNC_U_F64:
203 case WebAssembly::I64_TRUNC_U_F64:
204 // These instruction have hasUnmodeledSideEffects() returning true
205 // because they trap on overflow and invalid so they can't be arbitrarily
206 // moved, however hasOrderedMemoryRef() interprets this plus their lack
207 // of memoperands as having a potential unknown memory reference.
208 break;
209 default:
210 // Record volatile accesses, unless it's a call, as calls are handled
211 // specially below.
212 if (!MI.isCall()) {
213 Write = true;
214 Effects = true;
215 }
216 break;
217 }
218 }
219
220 // Check for side effects.
221 if (MI.hasUnmodeledSideEffects()) {
222 switch (MI.getOpcode()) {
223 case WebAssembly::DIV_S_I32:
224 case WebAssembly::DIV_S_I64:
225 case WebAssembly::REM_S_I32:
226 case WebAssembly::REM_S_I64:
227 case WebAssembly::DIV_U_I32:
228 case WebAssembly::DIV_U_I64:
229 case WebAssembly::REM_U_I32:
230 case WebAssembly::REM_U_I64:
231 case WebAssembly::I32_TRUNC_S_F32:
232 case WebAssembly::I64_TRUNC_S_F32:
233 case WebAssembly::I32_TRUNC_S_F64:
234 case WebAssembly::I64_TRUNC_S_F64:
235 case WebAssembly::I32_TRUNC_U_F32:
236 case WebAssembly::I64_TRUNC_U_F32:
237 case WebAssembly::I32_TRUNC_U_F64:
238 case WebAssembly::I64_TRUNC_U_F64:
239 // These instructions have hasUnmodeledSideEffects() returning true
240 // because they trap on overflow and invalid so they can't be arbitrarily
241 // moved, however in the specific case of register stackifying, it is safe
242 // to move them because overflow and invalid are Undefined Behavior.
243 break;
244 default:
245 Effects = true;
246 break;
247 }
248 }
249
250 // Check for writes to __stack_pointer global.
251 if ((MI.getOpcode() == WebAssembly::GLOBAL_SET_I32 ||
252 MI.getOpcode() == WebAssembly::GLOBAL_SET_I64) &&
253 MI.getOperand(i: 0).isSymbol() &&
254 !strcmp(s1: MI.getOperand(i: 0).getSymbolName(), s2: "__stack_pointer"))
255 StackPointer = true;
256
257 if (MI.isCall() && MI.getOperand(i: 0).isSymbol() &&
258 !strcmp(s1: MI.getOperand(i: 0).getSymbolName(), s2: "__wasm_get_stack_pointer"))
259 StackPointer = true;
260
261 // Analyze calls.
262 if (MI.isCall()) {
263 queryCallee(MI, Read, Write, Effects, StackPointer);
264 }
265}
266
267// Test whether Def is safe and profitable to rematerialize.
268static bool shouldRematerialize(const MachineInstr &Def,
269 const WebAssemblyInstrInfo *TII) {
270 return Def.isAsCheapAsAMove() && TII->isTriviallyReMaterializable(MI: Def);
271}
272
273// Identify the definition for this register at this point. This is a
274// generalization of MachineRegisterInfo::getUniqueVRegDef that uses
275// LiveIntervals to handle complex cases.
276static MachineInstr *getVRegDef(unsigned Reg, const MachineInstr *Insert,
277 const MachineRegisterInfo &MRI,
278 const LiveIntervals *LIS) {
279 // Most registers are in SSA form here so we try a quick MRI query first.
280 if (MachineInstr *Def = MRI.getUniqueVRegDef(Reg))
281 return Def;
282
283 // MRI doesn't know what the Def is. Try asking LIS.
284 if (LIS != nullptr) {
285 SlotIndex InstIndex = LIS->getInstructionIndex(Instr: *Insert);
286 if (const VNInfo *ValNo = LIS->getInterval(Reg).getVNInfoBefore(Idx: InstIndex))
287 return LIS->getInstructionFromIndex(index: ValNo->def);
288 }
289
290 return nullptr;
291}
292
293// Test whether Reg, as defined at Def, has exactly one use. This is a
294// generalization of MachineRegisterInfo::hasOneNonDBGUse that uses
295// LiveIntervals to handle complex cases in optimized code.
296static bool hasSingleUse(unsigned Reg, MachineRegisterInfo &MRI,
297 const MachineFunction &MF, bool Optimize,
298 MachineInstr *Def, LiveIntervals *LIS) {
299 auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
300 // The frame base always has an implicit DBG use as DW_AT_frame_base.
301 if (MFI.isFrameBaseVirtual() && MFI.getFrameBaseVreg() == Reg) {
302 // When using global thread context, the frame base can be encoded
303 // as an offset from __stack_pointer, so the vreg can be stackified.
304 // However, when using libcall thread context, we need to keep the frame
305 // base vreg around if debug info is enabled, because there is no
306 // global to refer to.
307 bool NeedsRegForDebug =
308 MF.getFunction().getSubprogram() &&
309 MF.getSubtarget<WebAssemblySubtarget>().hasLibcallThreadContext();
310 if (!Optimize || NeedsRegForDebug)
311 return false;
312 }
313 if (!Optimize) {
314 // Using "hasOneUse" instead of "hasOneNonDBGUse" here because we don't
315 // want to stackify DBG_VALUE operands - WASM stack locations are less
316 // useful and less widely supported than WASM local locations.
317 if (!MRI.hasOneUse(RegNo: Reg))
318 return false;
319 return true;
320 }
321
322 // Most registers are in SSA form here so we try a quick MRI query first.
323 if (MRI.hasOneNonDBGUse(RegNo: Reg))
324 return true;
325
326 if (LIS == nullptr)
327 return false;
328
329 bool HasOne = false;
330 const LiveInterval &LI = LIS->getInterval(Reg);
331 const VNInfo *DefVNI =
332 LI.getVNInfoAt(Idx: LIS->getInstructionIndex(Instr: *Def).getRegSlot());
333 assert(DefVNI);
334 for (auto &I : MRI.use_nodbg_operands(Reg)) {
335 const auto &Result = LI.Query(Idx: LIS->getInstructionIndex(Instr: *I.getParent()));
336 if (Result.valueIn() == DefVNI) {
337 if (!Result.isKill())
338 return false;
339 if (HasOne)
340 return false;
341 HasOne = true;
342 }
343 }
344 return HasOne;
345}
346
347// Test whether it's safe to move Def to just before Insert.
348// TODO: Compute memory dependencies in a way that doesn't require always
349// walking the block.
350// TODO: Compute memory dependencies in a way that uses AliasAnalysis to be
351// more precise.
352static bool isSafeToMove(const MachineOperand *Def, const MachineOperand *Use,
353 const MachineInstr *Insert,
354 const WebAssemblyFunctionInfo &MFI,
355 const MachineRegisterInfo &MRI, bool Optimize) {
356 const MachineInstr *DefI = Def->getParent();
357 assert(DefI->getParent() == Insert->getParent());
358 assert(Use->getParent()->getParent() == Insert->getParent());
359
360 // For now avoid stackifying any multi-def instructions. While it's
361 // theoretically possible to do so for the first def in some cases this has
362 // historically led to bugs such as #199910 and #98323. For now this
363 // conservatively skips all multi-def instructions as a consequence. Note that
364 // multi-def instructions are expected to be not all that common so this in
365 // theory doesn't have a massive impact, but nevertheless this'd still be
366 // something to optimize better in the future.
367 if (DefI->getNumExplicitDefs() > 1)
368 return false;
369
370 // If moving is a semantic nop, it is always allowed
371 const MachineBasicBlock *MBB = DefI->getParent();
372 auto NextI = std::next(x: MachineBasicBlock::const_iterator(DefI));
373 for (auto E = MBB->end(); NextI != E && NextI->isDebugInstr(); ++NextI)
374 ;
375 if (NextI == Insert)
376 return true;
377
378 // When not optimizing, we only handle the trivial case above
379 // to guarantee no impact to debugging and to avoid spending
380 // compile time.
381 if (!Optimize)
382 return false;
383
384 // 'catch' and 'catch_all' should be the first instruction of a BB and cannot
385 // move.
386 if (WebAssembly::isCatch(Opc: DefI->getOpcode()))
387 return false;
388
389 // Check for register dependencies.
390 SmallVector<unsigned, 4> MutableRegisters;
391 for (const MachineOperand &MO : DefI->operands()) {
392 if (!MO.isReg() || MO.isUndef())
393 continue;
394 Register Reg = MO.getReg();
395
396 // If the register is dead here and at Insert, ignore it.
397 if (MO.isDead() && Insert->definesRegister(Reg, /*TRI=*/nullptr) &&
398 !Insert->readsRegister(Reg, /*TRI=*/nullptr))
399 continue;
400
401 if (Reg.isPhysical()) {
402 // Ignore ARGUMENTS; it's just used to keep the ARGUMENT_* instructions
403 // from moving down, and we've already checked for that.
404 if (Reg == WebAssembly::ARGUMENTS)
405 continue;
406 // If the physical register is never modified, ignore it.
407 if (!MRI.isPhysRegModified(PhysReg: Reg))
408 continue;
409 // Otherwise, it's a physical register with unknown liveness.
410 return false;
411 }
412
413 // If one of the operands isn't in SSA form, it has different values at
414 // different times, and we need to make sure we don't move our use across
415 // a different def.
416 if (!MO.isDef() && !MRI.hasOneDef(RegNo: Reg))
417 MutableRegisters.push_back(Elt: Reg);
418 }
419
420 bool Read = false, Write = false, Effects = false, StackPointer = false;
421 query(MI: *DefI, Read, Write, Effects, StackPointer);
422
423 // If the instruction does not access memory and has no side effects, it has
424 // no additional dependencies.
425 bool HasMutableRegisters = !MutableRegisters.empty();
426 if (!Read && !Write && !Effects && !StackPointer && !HasMutableRegisters)
427 return true;
428
429 // Scan through the intervening instructions between DefI and Insert.
430 MachineBasicBlock::const_iterator D(DefI), I(Insert);
431 for (--I; I != D; --I) {
432 bool InterveningRead = false;
433 bool InterveningWrite = false;
434 bool InterveningEffects = false;
435 bool InterveningStackPointer = false;
436 query(MI: *I, Read&: InterveningRead, Write&: InterveningWrite, Effects&: InterveningEffects,
437 StackPointer&: InterveningStackPointer);
438 if (Effects && InterveningEffects)
439 return false;
440 if (Read && InterveningWrite)
441 return false;
442 if (Write && (InterveningRead || InterveningWrite))
443 return false;
444 if (StackPointer && InterveningStackPointer)
445 return false;
446
447 for (unsigned Reg : MutableRegisters)
448 for (const MachineOperand &MO : I->operands())
449 if (MO.isReg() && MO.isDef() && MO.getReg() == Reg)
450 return false;
451 }
452
453 return true;
454}
455
456/// Test whether OneUse, a use of Reg, dominates all of Reg's other uses.
457static bool oneUseDominatesOtherUses(unsigned Reg, const MachineOperand &OneUse,
458 const MachineBasicBlock &MBB,
459 const MachineRegisterInfo &MRI,
460 const MachineDominatorTree &MDT,
461 LiveIntervals &LIS,
462 WebAssemblyFunctionInfo &MFI) {
463 const LiveInterval &LI = LIS.getInterval(Reg);
464
465 const MachineInstr *OneUseInst = OneUse.getParent();
466 SlotIndex OneUseIdx = LIS.getInstructionIndex(Instr: *OneUseInst);
467 VNInfo *OneUseVNI = LI.getVNInfoBefore(Idx: OneUseIdx);
468
469 auto OneUseDominates = [&](const MachineInstr *UseI) {
470 if (OneUseInst->getParent() != UseI->getParent())
471 return MDT.dominates(A: OneUseInst->getParent(), B: UseI->getParent());
472 if (OneUseInst == UseI)
473 return true;
474 return SlotIndex::isEarlierInstr(A: OneUseIdx, B: LIS.getInstructionIndex(Instr: *UseI));
475 };
476
477 for (const MachineOperand &Use : MRI.use_nodbg_operands(Reg)) {
478 if (&Use == &OneUse)
479 continue;
480
481 const MachineInstr *UseInst = Use.getParent();
482 VNInfo *UseVNI = LI.getVNInfoBefore(Idx: LIS.getInstructionIndex(Instr: *UseInst));
483
484 if (UseVNI != OneUseVNI)
485 continue;
486
487 if (UseInst == OneUseInst) {
488 // Another use in the same instruction. We need to ensure that the one
489 // selected use happens "before" it.
490 if (&OneUse > &Use)
491 return false;
492 } else {
493 // Test that the use is dominated by the one selected use.
494 while (!OneUseDominates(UseInst)) {
495 // Actually, dominating is over-conservative. Test that the use would
496 // happen after the one selected use in the stack evaluation order.
497 //
498 // This is needed as a consequence of using implicit local.gets for
499 // uses and implicit local.sets for defs.
500 if (UseInst->getDesc().getNumDefs() == 0)
501 return false;
502 const MachineOperand &MO = UseInst->getOperand(i: 0);
503 if (!MO.isReg())
504 return false;
505 Register DefReg = MO.getReg();
506 if (!DefReg.isVirtual() || !MFI.isVRegStackified(VReg: DefReg))
507 return false;
508 assert(MRI.hasOneNonDBGUse(DefReg));
509 const MachineOperand &NewUse = *MRI.use_nodbg_begin(RegNo: DefReg);
510 const MachineInstr *NewUseInst = NewUse.getParent();
511 if (NewUseInst == OneUseInst) {
512 if (&OneUse > &NewUse)
513 return false;
514 break;
515 }
516 UseInst = NewUseInst;
517 }
518 }
519 }
520 return true;
521}
522
523/// Get the appropriate tee opcode for the given register class.
524static unsigned getTeeOpcode(const TargetRegisterClass *RC) {
525 if (RC == &WebAssembly::I32RegClass)
526 return WebAssembly::TEE_I32;
527 if (RC == &WebAssembly::I64RegClass)
528 return WebAssembly::TEE_I64;
529 if (RC == &WebAssembly::F32RegClass)
530 return WebAssembly::TEE_F32;
531 if (RC == &WebAssembly::F64RegClass)
532 return WebAssembly::TEE_F64;
533 if (RC == &WebAssembly::V128RegClass)
534 return WebAssembly::TEE_V128;
535 if (RC == &WebAssembly::EXTERNREFRegClass)
536 return WebAssembly::TEE_EXTERNREF;
537 if (RC == &WebAssembly::FUNCREFRegClass)
538 return WebAssembly::TEE_FUNCREF;
539 if (RC == &WebAssembly::EXNREFRegClass)
540 return WebAssembly::TEE_EXNREF;
541 llvm_unreachable("Unexpected register class");
542}
543
544// Shrink LI to its uses, cleaning up LI.
545static void shrinkToUses(LiveInterval &LI, LiveIntervals &LIS) {
546 if (LIS.shrinkToUses(li: &LI)) {
547 SmallVector<LiveInterval *, 4> SplitLIs;
548 LIS.splitSeparateComponents(LI, SplitLIs);
549 }
550}
551
552/// A single-use def in the same block with no intervening memory or register
553/// dependencies; move the def down and nest it with the current instruction.
554static MachineInstr *moveForSingleUse(unsigned Reg, MachineOperand &Op,
555 MachineInstr *Def, MachineBasicBlock &MBB,
556 MachineInstr *Insert, LiveIntervals *LIS,
557 WebAssemblyFunctionInfo &MFI,
558 MachineRegisterInfo &MRI) {
559 LLVM_DEBUG(dbgs() << "Move for single use: "; Def->dump());
560
561 WebAssemblyDebugValueManager DefDIs(Def);
562 DefDIs.sink(Insert);
563 if (LIS != nullptr)
564 LIS->handleMove(MI&: *Def);
565
566 if (MRI.hasOneDef(RegNo: Reg) && MRI.hasOneNonDBGUse(RegNo: Reg)) {
567 // No one else is using this register for anything so we can just stackify
568 // it in place.
569 MFI.stackifyVReg(MRI, VReg: Reg);
570 } else {
571 // The register may have unrelated uses or defs; create a new register for
572 // just our one def and use so that we can stackify it.
573 Register NewReg = MRI.createVirtualRegister(RegClass: MRI.getRegClass(Reg));
574 Op.setReg(NewReg);
575 DefDIs.updateReg(Reg: NewReg);
576
577 if (LIS != nullptr) {
578 // Tell LiveIntervals about the new register.
579 LIS->createAndComputeVirtRegInterval(Reg: NewReg);
580
581 // Tell LiveIntervals about the changes to the old register.
582 LiveInterval &LI = LIS->getInterval(Reg);
583 LI.removeSegment(Start: LIS->getInstructionIndex(Instr: *Def).getRegSlot(),
584 End: LIS->getInstructionIndex(Instr: *Op.getParent()).getRegSlot(),
585 /*RemoveDeadValNo=*/true);
586 }
587
588 MFI.stackifyVReg(MRI, VReg: NewReg);
589 LLVM_DEBUG(dbgs() << " - Replaced register: "; Def->dump());
590 }
591
592 imposeStackOrdering(MI: Def);
593 return Def;
594}
595
596static MachineInstr *getPrevNonDebugInst(MachineInstr *MI) {
597 for (auto *I = MI->getPrevNode(); I; I = I->getPrevNode())
598 if (!I->isDebugInstr())
599 return I;
600 return nullptr;
601}
602
603/// A trivially cloneable instruction; clone it and nest the new copy with the
604/// current instruction.
605static MachineInstr *
606rematerializeCheapDef(unsigned Reg, MachineOperand &Op, MachineInstr &Def,
607 MachineBasicBlock::instr_iterator Insert,
608 LiveIntervals &LIS, WebAssemblyFunctionInfo &MFI,
609 MachineRegisterInfo &MRI,
610 const WebAssemblyInstrInfo *TII) {
611 LLVM_DEBUG(dbgs() << "Rematerializing cheap def: "; Def.dump());
612 LLVM_DEBUG(dbgs() << " - for use in "; Op.getParent()->dump());
613
614 WebAssemblyDebugValueManager DefDIs(&Def);
615
616 Register NewReg = MRI.createVirtualRegister(RegClass: MRI.getRegClass(Reg));
617 DefDIs.cloneSink(Insert: &*Insert, NewReg);
618 Op.setReg(NewReg);
619 MachineInstr *Clone = getPrevNonDebugInst(MI: &*Insert);
620 assert(Clone);
621 LIS.InsertMachineInstrInMaps(MI&: *Clone);
622 LIS.createAndComputeVirtRegInterval(Reg: NewReg);
623 MFI.stackifyVReg(MRI, VReg: NewReg);
624 imposeStackOrdering(MI: Clone);
625
626 LLVM_DEBUG(dbgs() << " - Cloned to "; Clone->dump());
627
628 // Shrink the interval.
629 bool IsDead = MRI.use_empty(RegNo: Reg);
630 if (!IsDead) {
631 LiveInterval &LI = LIS.getInterval(Reg);
632 shrinkToUses(LI, LIS);
633 IsDead = !LI.liveAt(index: LIS.getInstructionIndex(Instr: Def).getDeadSlot());
634 }
635
636 // If that was the last use of the original, delete the original.
637 if (IsDead) {
638 LLVM_DEBUG(dbgs() << " - Deleting original\n");
639 SlotIndex Idx = LIS.getInstructionIndex(Instr: Def).getRegSlot();
640 LIS.removePhysRegDefAt(Reg: MCRegister::from(Val: WebAssembly::ARGUMENTS), Pos: Idx);
641 LIS.removeInterval(Reg);
642 LIS.RemoveMachineInstrFromMaps(MI&: Def);
643 DefDIs.removeDef();
644 }
645
646 return Clone;
647}
648
649/// A multiple-use def in the same block with no intervening memory or register
650/// dependencies; move the def down, nest it with the current instruction, and
651/// insert a tee to satisfy the rest of the uses. As an illustration, rewrite
652/// this:
653///
654/// Reg = INST ... // Def
655/// INST ..., Reg, ... // Insert
656/// INST ..., Reg, ...
657/// INST ..., Reg, ...
658///
659/// to this:
660///
661/// DefReg = INST ... // Def (to become the new Insert)
662/// TeeReg, Reg = TEE_... DefReg
663/// INST ..., TeeReg, ... // Insert
664/// INST ..., Reg, ...
665/// INST ..., Reg, ...
666///
667/// with DefReg and TeeReg stackified. This eliminates a local.get from the
668/// resulting code.
669static MachineInstr *moveAndTeeForMultiUse(
670 unsigned Reg, MachineOperand &Op, MachineInstr *Def, MachineBasicBlock &MBB,
671 MachineInstr *Insert, LiveIntervals &LIS, WebAssemblyFunctionInfo &MFI,
672 MachineRegisterInfo &MRI, const WebAssemblyInstrInfo *TII) {
673 LLVM_DEBUG(dbgs() << "Move and tee for multi-use:"; Def->dump());
674
675 const auto *RegClass = MRI.getRegClass(Reg);
676 Register TeeReg = MRI.createVirtualRegister(RegClass);
677 Register DefReg = MRI.createVirtualRegister(RegClass);
678
679 // Move Def into place.
680 WebAssemblyDebugValueManager DefDIs(Def);
681 DefDIs.sink(Insert);
682 LIS.handleMove(MI&: *Def);
683
684 // Create the Tee and attach the registers.
685 MachineOperand &DefMO = Def->getOperand(i: 0);
686 MachineInstr *Tee = BuildMI(BB&: MBB, I: Insert, MIMD: Insert->getDebugLoc(),
687 MCID: TII->get(Opcode: getTeeOpcode(RC: RegClass)), DestReg: TeeReg)
688 .addReg(RegNo: Reg, Flags: RegState::Define)
689 .addReg(RegNo: DefReg, Flags: getUndefRegState(B: DefMO.isDead()));
690 Op.setReg(TeeReg);
691 DefDIs.updateReg(Reg: DefReg);
692 SlotIndex TeeIdx = LIS.InsertMachineInstrInMaps(MI&: *Tee).getRegSlot();
693 SlotIndex DefIdx = LIS.getInstructionIndex(Instr: *Def).getRegSlot();
694
695 // Tell LiveIntervals we moved the original vreg def from Def to Tee.
696 LiveInterval &LI = LIS.getInterval(Reg);
697 LiveInterval::iterator I = LI.FindSegmentContaining(Idx: DefIdx);
698 VNInfo *ValNo = LI.getVNInfoAt(Idx: DefIdx);
699 I->start = TeeIdx;
700 ValNo->def = TeeIdx;
701 shrinkToUses(LI, LIS);
702
703 // Finish stackifying the new regs.
704 LIS.createAndComputeVirtRegInterval(Reg: TeeReg);
705 LIS.createAndComputeVirtRegInterval(Reg: DefReg);
706 MFI.stackifyVReg(MRI, VReg: DefReg);
707 MFI.stackifyVReg(MRI, VReg: TeeReg);
708 imposeStackOrdering(MI: Def);
709 imposeStackOrdering(MI: Tee);
710
711 // Even though 'TeeReg, Reg = TEE ...', has two defs, we don't need to clone
712 // DBG_VALUEs for both of them, given that the latter will cancel the former
713 // anyway. Here we only clone DBG_VALUEs for TeeReg, which will be converted
714 // to a local index in ExplicitLocals pass.
715 DefDIs.cloneSink(Insert, NewReg: TeeReg, /* CloneDef */ false);
716
717 LLVM_DEBUG(dbgs() << " - Replaced register: "; Def->dump());
718 LLVM_DEBUG(dbgs() << " - Tee instruction: "; Tee->dump());
719 return Def;
720}
721
722namespace {
723/// A stack for walking the tree of instructions being built, visiting the
724/// MachineOperands in DFS order.
725class TreeWalkerState {
726 using mop_iterator = MachineInstr::mop_iterator;
727 using mop_reverse_iterator = std::reverse_iterator<mop_iterator>;
728 using RangeTy = iterator_range<mop_reverse_iterator>;
729 SmallVector<RangeTy, 4> Worklist;
730
731public:
732 explicit TreeWalkerState(MachineInstr *Insert) {
733 const iterator_range<mop_iterator> &Range = Insert->explicit_uses();
734 if (!Range.empty())
735 Worklist.push_back(Elt: reverse(C: Range));
736 }
737
738 bool done() const { return Worklist.empty(); }
739
740 MachineOperand &pop() {
741 RangeTy &Range = Worklist.back();
742 MachineOperand &Op = *Range.begin();
743 Range = drop_begin(RangeOrContainer&: Range);
744 if (Range.empty())
745 Worklist.pop_back();
746 assert((Worklist.empty() || !Worklist.back().empty()) &&
747 "Empty ranges shouldn't remain in the worklist");
748 return Op;
749 }
750
751 /// Push Instr's operands onto the stack to be visited.
752 void pushOperands(MachineInstr *Instr) {
753 const iterator_range<mop_iterator> &Range(Instr->explicit_uses());
754 if (!Range.empty())
755 Worklist.push_back(Elt: reverse(C: Range));
756 }
757
758 /// Some of Instr's operands are on the top of the stack; remove them and
759 /// re-insert them starting from the beginning (because we've commuted them).
760 void resetTopOperands(MachineInstr *Instr) {
761 assert(hasRemainingOperands(Instr) &&
762 "Resetting operands should only be done when the instruction has "
763 "an operand still on the stack");
764 Worklist.back() = reverse(C: Instr->explicit_uses());
765 }
766
767 /// Test whether Instr has operands remaining to be visited at the top of
768 /// the stack.
769 bool hasRemainingOperands(const MachineInstr *Instr) const {
770 if (Worklist.empty())
771 return false;
772 const RangeTy &Range = Worklist.back();
773 return !Range.empty() && Range.begin()->getParent() == Instr;
774 }
775
776 /// Test whether the given register is present on the stack, indicating an
777 /// operand in the tree that we haven't visited yet. Moving a definition of
778 /// Reg to a point in the tree after that would change its value.
779 ///
780 /// This is needed as a consequence of using implicit local.gets for
781 /// uses and implicit local.sets for defs.
782 bool isOnStack(unsigned Reg) const {
783 for (const RangeTy &Range : Worklist)
784 for (const MachineOperand &MO : Range)
785 if (MO.isReg() && MO.getReg() == Reg)
786 return true;
787 return false;
788 }
789};
790
791/// State to keep track of whether commuting is in flight or whether it's been
792/// tried for the current instruction and didn't work.
793class CommutingState {
794 /// There are effectively three states: the initial state where we haven't
795 /// started commuting anything and we don't know anything yet, the tentative
796 /// state where we've commuted the operands of the current instruction and are
797 /// revisiting it, and the declined state where we've reverted the operands
798 /// back to their original order and will no longer commute it further.
799 bool TentativelyCommuting = false;
800 bool Declined = false;
801
802 /// During the tentative state, these hold the operand indices of the commuted
803 /// operands.
804 unsigned Operand0, Operand1;
805
806public:
807 /// Stackification for an operand was not successful due to ordering
808 /// constraints. If possible, and if we haven't already tried it and declined
809 /// it, commute Insert's operands and prepare to revisit it.
810 void maybeCommute(MachineInstr *Insert, TreeWalkerState &TreeWalker,
811 const WebAssemblyInstrInfo *TII) {
812 if (TentativelyCommuting) {
813 assert(!Declined &&
814 "Don't decline commuting until you've finished trying it");
815 // Commuting didn't help. Revert it.
816 TII->commuteInstruction(MI&: *Insert, /*NewMI=*/false, OpIdx1: Operand0, OpIdx2: Operand1);
817 TentativelyCommuting = false;
818 Declined = true;
819 } else if (!Declined && TreeWalker.hasRemainingOperands(Instr: Insert)) {
820 Operand0 = TargetInstrInfo::CommuteAnyOperandIndex;
821 Operand1 = TargetInstrInfo::CommuteAnyOperandIndex;
822 if (TII->findCommutedOpIndices(MI: *Insert, SrcOpIdx1&: Operand0, SrcOpIdx2&: Operand1)) {
823 // Tentatively commute the operands and try again.
824 TII->commuteInstruction(MI&: *Insert, /*NewMI=*/false, OpIdx1: Operand0, OpIdx2: Operand1);
825 TreeWalker.resetTopOperands(Instr: Insert);
826 TentativelyCommuting = true;
827 Declined = false;
828 }
829 }
830 }
831
832 /// Stackification for some operand was successful. Reset to the default
833 /// state.
834 void reset() {
835 TentativelyCommuting = false;
836 Declined = false;
837 }
838};
839} // end anonymous namespace
840
841static bool regStackify(MachineFunction &MF, bool Optimize,
842 MachineDominatorTree *MDT, LiveIntervals *LIS) {
843 LLVM_DEBUG(dbgs() << "********** Register Stackifying **********\n"
844 "********** Function: "
845 << MF.getName() << '\n');
846
847 bool Changed = false;
848 MachineRegisterInfo &MRI = MF.getRegInfo();
849 WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
850 const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
851 if (Optimize) {
852 assert(MDT && "expected MDT to be available");
853 assert(LIS && "expected LIS to be available");
854 }
855
856 // Walk the instructions from the bottom up. Currently we don't look past
857 // block boundaries, and the blocks aren't ordered so the block visitation
858 // order isn't significant, but we may want to change this in the future.
859 for (MachineBasicBlock &MBB : MF) {
860 // Don't use a range-based for loop, because we modify the list as we're
861 // iterating over it and the end iterator may change.
862 for (auto MII = MBB.rbegin(); MII != MBB.rend(); ++MII) {
863 MachineInstr *Insert = &*MII;
864 // Don't nest anything inside an inline asm, because we don't have
865 // constraints for $push inputs.
866 if (Insert->isInlineAsm())
867 continue;
868
869 // Ignore debugging intrinsics.
870 if (Insert->isDebugValue())
871 continue;
872
873 // Ignore FAKE_USEs, which are no-ops and will be deleted later.
874 if (Insert->isFakeUse())
875 continue;
876
877 // Iterate through the inputs in reverse order, since we'll be pulling
878 // operands off the stack in LIFO order.
879 CommutingState Commuting;
880 TreeWalkerState TreeWalker(Insert);
881 while (!TreeWalker.done()) {
882 MachineOperand &Use = TreeWalker.pop();
883
884 // We're only interested in explicit virtual register operands.
885 if (!Use.isReg())
886 continue;
887
888 Register Reg = Use.getReg();
889 assert(Use.isUse() && "explicit_uses() should only iterate over uses");
890 assert(!Use.isImplicit() &&
891 "explicit_uses() should only iterate over explicit operands");
892 if (Reg.isPhysical())
893 continue;
894
895 // Identify the definition for this register at this point.
896 MachineInstr *DefI = getVRegDef(Reg, Insert, MRI, LIS);
897 if (!DefI)
898 continue;
899
900 // Don't nest an INLINE_ASM def into anything, because we don't have
901 // constraints for $pop outputs.
902 if (DefI->isInlineAsm())
903 continue;
904
905 // Argument instructions represent live-in registers and not real
906 // instructions.
907 if (WebAssembly::isArgument(Opc: DefI->getOpcode()))
908 continue;
909
910 MachineOperand *Def =
911 DefI->findRegisterDefOperand(Reg, /*TRI=*/nullptr);
912 assert(Def != nullptr);
913
914 // Decide which strategy to take. Prefer to move a single-use value
915 // over cloning it, and prefer cloning over introducing a tee.
916 // For moving, we require the def to be in the same block as the use;
917 // this makes things simpler (LiveIntervals' handleMove function only
918 // supports intra-block moves) and it's MachineSink's job to catch all
919 // the sinking opportunities anyway.
920 bool SameBlock = DefI->getParent() == &MBB;
921 bool CanMove = SameBlock &&
922 isSafeToMove(Def, Use: &Use, Insert, MFI, MRI, Optimize) &&
923 !TreeWalker.isOnStack(Reg);
924 if (CanMove && hasSingleUse(Reg, MRI, MF, Optimize, Def: DefI, LIS)) {
925 Insert = moveForSingleUse(Reg, Op&: Use, Def: DefI, MBB, Insert, LIS, MFI, MRI);
926
927 // If we are removing the frame base reg completely, remove the debug
928 // info as well.
929 // TODO: Encode this properly as a stackified value.
930 if (MFI.isFrameBaseVirtual() && MFI.getFrameBaseVreg() == Reg) {
931 assert(
932 Optimize &&
933 "Stackifying away frame base in unoptimized code not expected");
934 MFI.clearFrameBaseVreg();
935 }
936 } else if (Optimize && shouldRematerialize(Def: *DefI, TII)) {
937 Insert = rematerializeCheapDef(Reg, Op&: Use, Def&: *DefI, Insert: Insert->getIterator(),
938 LIS&: *LIS, MFI, MRI, TII);
939 } else if (Optimize && CanMove &&
940 oneUseDominatesOtherUses(Reg, OneUse: Use, MBB, MRI, MDT: *MDT, LIS&: *LIS,
941 MFI)) {
942 Insert = moveAndTeeForMultiUse(Reg, Op&: Use, Def: DefI, MBB, Insert, LIS&: *LIS, MFI,
943 MRI, TII);
944 } else {
945 // We failed to stackify the operand. If the problem was ordering
946 // constraints, Commuting may be able to help.
947 if (!CanMove && SameBlock)
948 Commuting.maybeCommute(Insert, TreeWalker, TII);
949 // Proceed to the next operand.
950 continue;
951 }
952
953 // Stackifying a multivalue def may unlock in-place stackification of
954 // subsequent defs. TODO: Handle the case where the consecutive uses are
955 // not all in the same instruction.
956 auto *SubsequentDef = Insert->defs().begin();
957 auto *SubsequentUse = &Use;
958 while (SubsequentDef != Insert->defs().end() &&
959 SubsequentUse != Use.getParent()->uses().end()) {
960 if (!SubsequentDef->isReg() || !SubsequentUse->isReg())
961 break;
962 Register DefReg = SubsequentDef->getReg();
963 Register UseReg = SubsequentUse->getReg();
964 // TODO: This single-use restriction could be relaxed by using tees
965 if (DefReg != UseReg ||
966 !hasSingleUse(Reg: DefReg, MRI, MF, Optimize, Def: nullptr, LIS: nullptr))
967 break;
968 MFI.stackifyVReg(MRI, VReg: DefReg);
969 ++SubsequentDef;
970 ++SubsequentUse;
971 }
972
973 // If the instruction we just stackified is an IMPLICIT_DEF, convert it
974 // to a constant 0 so that the def is explicit, and the push/pop
975 // correspondence is maintained.
976 if (Insert->getOpcode() == TargetOpcode::IMPLICIT_DEF)
977 convertImplicitDefToConstZero(MI: Insert, MRI, TII, MF);
978
979 // We stackified an operand. Add the defining instruction's operands to
980 // the worklist stack now to continue to build an ever deeper tree.
981 Commuting.reset();
982 TreeWalker.pushOperands(Instr: Insert);
983 }
984
985 // If we stackified any operands, skip over the tree to start looking for
986 // the next instruction we can build a tree on.
987 if (Insert != &*MII) {
988 imposeStackOrdering(MI: &*MII);
989 MII = MachineBasicBlock::iterator(Insert).getReverse();
990 Changed = true;
991 }
992 }
993 }
994
995 // If we used VALUE_STACK anywhere, add it to the live-in sets everywhere so
996 // that it never looks like a use-before-def.
997 if (Changed) {
998 MF.getRegInfo().addLiveIn(Reg: WebAssembly::VALUE_STACK);
999 for (MachineBasicBlock &MBB : MF)
1000 MBB.addLiveIn(PhysReg: WebAssembly::VALUE_STACK);
1001 }
1002
1003#ifndef NDEBUG
1004 // Verify that pushes and pops are performed in LIFO order.
1005 SmallVector<unsigned, 0> Stack;
1006 for (MachineBasicBlock &MBB : MF) {
1007 for (MachineInstr &MI : MBB) {
1008 if (MI.isDebugInstr())
1009 continue;
1010 for (MachineOperand &MO : reverse(MI.explicit_uses())) {
1011 if (!MO.isReg())
1012 continue;
1013 Register Reg = MO.getReg();
1014 if (MFI.isVRegStackified(Reg))
1015 assert(Stack.pop_back_val() == Reg &&
1016 "Register stack pop should be paired with a push");
1017 }
1018 for (MachineOperand &MO : MI.defs()) {
1019 if (!MO.isReg())
1020 continue;
1021 Register Reg = MO.getReg();
1022 if (MFI.isVRegStackified(Reg))
1023 Stack.push_back(MO.getReg());
1024 }
1025 }
1026 // TODO: Generalize this code to support keeping values on the stack across
1027 // basic block boundaries.
1028 assert(Stack.empty() &&
1029 "Register stack pushes and pops should be balanced");
1030 }
1031#endif
1032
1033 return Changed;
1034}
1035
1036bool WebAssemblyRegStackifyLegacy::runOnMachineFunction(MachineFunction &MF) {
1037 MachineDominatorTree *MDT = nullptr;
1038 LiveIntervals *LIS = nullptr;
1039 if (Optimize) {
1040 MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
1041 LIS = &getAnalysis<LiveIntervalsWrapperPass>().getLIS();
1042 }
1043 return regStackify(MF, Optimize, MDT, LIS);
1044}
1045
1046PreservedAnalyses
1047WebAssemblyRegStackifyPass::run(MachineFunction &MF,
1048 MachineFunctionAnalysisManager &MFAM) {
1049 MachineDominatorTree *MDT = nullptr;
1050 LiveIntervals *LIS = nullptr;
1051 if (Optimize) {
1052 MDT = &MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
1053 LIS = &MFAM.getResult<LiveIntervalsAnalysis>(IR&: MF);
1054 }
1055 bool Changed = regStackify(MF, Optimize, MDT, LIS);
1056 if (!Changed)
1057 return PreservedAnalyses::all();
1058 return getMachineFunctionPassPreservedAnalyses()
1059 .preserveSet<CFGAnalyses>()
1060 .preserve<LiveIntervalsAnalysis>()
1061 .preserve<SlotIndexesAnalysis>();
1062}
1063