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