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