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