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