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