1 //===-- WebAssemblyExplicitLocals.cpp - Make Locals Explicit --------------===// 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 converts any remaining registers into WebAssembly locals. 11 /// 12 /// After register stackification and register coloring, convert non-stackified 13 /// registers into locals, inserting explicit local.get and local.set 14 /// instructions. 15 /// 16 //===----------------------------------------------------------------------===// 17 18 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h" 19 #include "WebAssembly.h" 20 #include "WebAssemblyDebugValueManager.h" 21 #include "WebAssemblyMachineFunctionInfo.h" 22 #include "WebAssemblySubtarget.h" 23 #include "WebAssemblyUtilities.h" 24 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 25 #include "llvm/CodeGen/MachineInstrBuilder.h" 26 #include "llvm/CodeGen/MachineRegisterInfo.h" 27 #include "llvm/CodeGen/Passes.h" 28 #include "llvm/Support/Debug.h" 29 #include "llvm/Support/raw_ostream.h" 30 using namespace llvm; 31 32 #define DEBUG_TYPE "wasm-explicit-locals" 33 34 namespace { 35 class WebAssemblyExplicitLocals final : public MachineFunctionPass { 36 StringRef getPassName() const override { 37 return "WebAssembly Explicit Locals"; 38 } 39 40 void getAnalysisUsage(AnalysisUsage &AU) const override { 41 AU.setPreservesCFG(); 42 AU.addPreserved<MachineBlockFrequencyInfoWrapperPass>(); 43 MachineFunctionPass::getAnalysisUsage(AU); 44 } 45 46 bool runOnMachineFunction(MachineFunction &MF) override; 47 48 public: 49 static char ID; // Pass identification, replacement for typeid 50 WebAssemblyExplicitLocals() : MachineFunctionPass(ID) {} 51 }; 52 } // end anonymous namespace 53 54 char WebAssemblyExplicitLocals::ID = 0; 55 INITIALIZE_PASS(WebAssemblyExplicitLocals, DEBUG_TYPE, 56 "Convert registers to WebAssembly locals", false, false) 57 58 FunctionPass *llvm::createWebAssemblyExplicitLocals() { 59 return new WebAssemblyExplicitLocals(); 60 } 61 62 static void checkFrameBase(WebAssemblyFunctionInfo &MFI, unsigned Local, 63 unsigned Reg) { 64 // Mark a local for the frame base vreg. 65 if (MFI.isFrameBaseVirtual() && Reg == MFI.getFrameBaseVreg()) { 66 LLVM_DEBUG({ 67 dbgs() << "Allocating local " << Local << "for VReg " 68 << Register(Reg).virtRegIndex() << '\n'; 69 }); 70 MFI.setFrameBaseLocal(Local); 71 } 72 } 73 74 /// Return a local id number for the given register, assigning it a new one 75 /// if it doesn't yet have one. 76 static unsigned getLocalId(DenseMap<unsigned, unsigned> &Reg2Local, 77 WebAssemblyFunctionInfo &MFI, unsigned &CurLocal, 78 unsigned Reg) { 79 auto P = Reg2Local.insert(std::make_pair(Reg, CurLocal)); 80 if (P.second) { 81 checkFrameBase(MFI, CurLocal, Reg); 82 ++CurLocal; 83 } 84 return P.first->second; 85 } 86 87 /// Get the appropriate drop opcode for the given register class. 88 static unsigned getDropOpcode(const TargetRegisterClass *RC) { 89 if (RC == &WebAssembly::I32RegClass) 90 return WebAssembly::DROP_I32; 91 if (RC == &WebAssembly::I64RegClass) 92 return WebAssembly::DROP_I64; 93 if (RC == &WebAssembly::F32RegClass) 94 return WebAssembly::DROP_F32; 95 if (RC == &WebAssembly::F64RegClass) 96 return WebAssembly::DROP_F64; 97 if (RC == &WebAssembly::V128RegClass) 98 return WebAssembly::DROP_V128; 99 if (RC == &WebAssembly::FUNCREFRegClass) 100 return WebAssembly::DROP_FUNCREF; 101 if (RC == &WebAssembly::EXTERNREFRegClass) 102 return WebAssembly::DROP_EXTERNREF; 103 if (RC == &WebAssembly::EXNREFRegClass) 104 return WebAssembly::DROP_EXNREF; 105 llvm_unreachable("Unexpected register class"); 106 } 107 108 /// Get the appropriate local.get opcode for the given register class. 109 static unsigned getLocalGetOpcode(const TargetRegisterClass *RC) { 110 if (RC == &WebAssembly::I32RegClass) 111 return WebAssembly::LOCAL_GET_I32; 112 if (RC == &WebAssembly::I64RegClass) 113 return WebAssembly::LOCAL_GET_I64; 114 if (RC == &WebAssembly::F32RegClass) 115 return WebAssembly::LOCAL_GET_F32; 116 if (RC == &WebAssembly::F64RegClass) 117 return WebAssembly::LOCAL_GET_F64; 118 if (RC == &WebAssembly::V128RegClass) 119 return WebAssembly::LOCAL_GET_V128; 120 if (RC == &WebAssembly::FUNCREFRegClass) 121 return WebAssembly::LOCAL_GET_FUNCREF; 122 if (RC == &WebAssembly::EXTERNREFRegClass) 123 return WebAssembly::LOCAL_GET_EXTERNREF; 124 if (RC == &WebAssembly::EXNREFRegClass) 125 return WebAssembly::LOCAL_GET_EXNREF; 126 llvm_unreachable("Unexpected register class"); 127 } 128 129 /// Get the appropriate local.set opcode for the given register class. 130 static unsigned getLocalSetOpcode(const TargetRegisterClass *RC) { 131 if (RC == &WebAssembly::I32RegClass) 132 return WebAssembly::LOCAL_SET_I32; 133 if (RC == &WebAssembly::I64RegClass) 134 return WebAssembly::LOCAL_SET_I64; 135 if (RC == &WebAssembly::F32RegClass) 136 return WebAssembly::LOCAL_SET_F32; 137 if (RC == &WebAssembly::F64RegClass) 138 return WebAssembly::LOCAL_SET_F64; 139 if (RC == &WebAssembly::V128RegClass) 140 return WebAssembly::LOCAL_SET_V128; 141 if (RC == &WebAssembly::FUNCREFRegClass) 142 return WebAssembly::LOCAL_SET_FUNCREF; 143 if (RC == &WebAssembly::EXTERNREFRegClass) 144 return WebAssembly::LOCAL_SET_EXTERNREF; 145 if (RC == &WebAssembly::EXNREFRegClass) 146 return WebAssembly::LOCAL_SET_EXNREF; 147 llvm_unreachable("Unexpected register class"); 148 } 149 150 /// Get the appropriate local.tee opcode for the given register class. 151 static unsigned getLocalTeeOpcode(const TargetRegisterClass *RC) { 152 if (RC == &WebAssembly::I32RegClass) 153 return WebAssembly::LOCAL_TEE_I32; 154 if (RC == &WebAssembly::I64RegClass) 155 return WebAssembly::LOCAL_TEE_I64; 156 if (RC == &WebAssembly::F32RegClass) 157 return WebAssembly::LOCAL_TEE_F32; 158 if (RC == &WebAssembly::F64RegClass) 159 return WebAssembly::LOCAL_TEE_F64; 160 if (RC == &WebAssembly::V128RegClass) 161 return WebAssembly::LOCAL_TEE_V128; 162 if (RC == &WebAssembly::FUNCREFRegClass) 163 return WebAssembly::LOCAL_TEE_FUNCREF; 164 if (RC == &WebAssembly::EXTERNREFRegClass) 165 return WebAssembly::LOCAL_TEE_EXTERNREF; 166 if (RC == &WebAssembly::EXNREFRegClass) 167 return WebAssembly::LOCAL_TEE_EXNREF; 168 llvm_unreachable("Unexpected register class"); 169 } 170 171 /// Get the type associated with the given register class. 172 static MVT typeForRegClass(const TargetRegisterClass *RC) { 173 if (RC == &WebAssembly::I32RegClass) 174 return MVT::i32; 175 if (RC == &WebAssembly::I64RegClass) 176 return MVT::i64; 177 if (RC == &WebAssembly::F32RegClass) 178 return MVT::f32; 179 if (RC == &WebAssembly::F64RegClass) 180 return MVT::f64; 181 if (RC == &WebAssembly::V128RegClass) 182 return MVT::v16i8; 183 if (RC == &WebAssembly::FUNCREFRegClass) 184 return MVT::funcref; 185 if (RC == &WebAssembly::EXTERNREFRegClass) 186 return MVT::externref; 187 if (RC == &WebAssembly::EXNREFRegClass) 188 return MVT::exnref; 189 llvm_unreachable("unrecognized register class"); 190 } 191 192 /// Given a MachineOperand of a stackified vreg, return the instruction at the 193 /// start of the expression tree. 194 static MachineInstr *findStartOfTree(MachineOperand &MO, 195 MachineRegisterInfo &MRI, 196 const WebAssemblyFunctionInfo &MFI) { 197 Register Reg = MO.getReg(); 198 assert(MFI.isVRegStackified(Reg)); 199 MachineInstr *Def = MRI.getVRegDef(Reg); 200 201 // If this instruction has any non-stackified defs, it is the start 202 for (auto DefReg : Def->defs()) { 203 if (!MFI.isVRegStackified(DefReg.getReg())) { 204 return Def; 205 } 206 } 207 208 // Find the first stackified use and proceed from there. 209 for (MachineOperand &DefMO : Def->explicit_uses()) { 210 if (!DefMO.isReg()) 211 continue; 212 return findStartOfTree(DefMO, MRI, MFI); 213 } 214 215 // If there were no stackified uses, we've reached the start. 216 return Def; 217 } 218 219 // FAKE_USEs are no-ops, so remove them here so that the values used by them 220 // will be correctly dropped later. 221 static void removeFakeUses(MachineFunction &MF) { 222 SmallVector<MachineInstr *> ToDelete; 223 for (auto &MBB : MF) 224 for (auto &MI : MBB) 225 if (MI.isFakeUse()) 226 ToDelete.push_back(&MI); 227 for (auto *MI : ToDelete) 228 MI->eraseFromParent(); 229 } 230 231 bool WebAssemblyExplicitLocals::runOnMachineFunction(MachineFunction &MF) { 232 LLVM_DEBUG(dbgs() << "********** Make Locals Explicit **********\n" 233 "********** Function: " 234 << MF.getName() << '\n'); 235 236 bool Changed = false; 237 MachineRegisterInfo &MRI = MF.getRegInfo(); 238 WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 239 const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 240 241 removeFakeUses(MF); 242 243 // Map non-stackified virtual registers to their local ids. 244 DenseMap<unsigned, unsigned> Reg2Local; 245 246 // Handle ARGUMENTS first to ensure that they get the designated numbers. 247 for (MachineBasicBlock::iterator I = MF.begin()->begin(), 248 E = MF.begin()->end(); 249 I != E;) { 250 MachineInstr &MI = *I++; 251 if (!WebAssembly::isArgument(MI.getOpcode())) 252 break; 253 Register Reg = MI.getOperand(0).getReg(); 254 assert(!MFI.isVRegStackified(Reg)); 255 auto Local = static_cast<unsigned>(MI.getOperand(1).getImm()); 256 Reg2Local[Reg] = Local; 257 checkFrameBase(MFI, Local, Reg); 258 259 // Update debug value to point to the local before removing. 260 WebAssemblyDebugValueManager(&MI).replaceWithLocal(Local); 261 262 MI.eraseFromParent(); 263 Changed = true; 264 } 265 266 // Start assigning local numbers after the last parameter and after any 267 // already-assigned locals. 268 unsigned CurLocal = static_cast<unsigned>(MFI.getParams().size()); 269 CurLocal += static_cast<unsigned>(MFI.getLocals().size()); 270 271 // Precompute the set of registers that are unused, so that we can insert 272 // drops to their defs. 273 // And unstackify any stackified registers that don't have any uses, so that 274 // they can be dropped later. This can happen when transformations after 275 // RegStackify remove instructions using stackified registers. 276 BitVector UseEmpty(MRI.getNumVirtRegs()); 277 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) { 278 Register Reg = Register::index2VirtReg(I); 279 if (MRI.use_empty(Reg)) { 280 UseEmpty[I] = true; 281 MFI.unstackifyVReg(Reg); 282 } 283 } 284 285 // Visit each instruction in the function. 286 for (MachineBasicBlock &MBB : MF) { 287 for (MachineInstr &MI : llvm::make_early_inc_range(MBB)) { 288 assert(!WebAssembly::isArgument(MI.getOpcode())); 289 290 if (MI.isDebugInstr() || MI.isLabel()) 291 continue; 292 293 if (MI.getOpcode() == WebAssembly::IMPLICIT_DEF) { 294 MI.eraseFromParent(); 295 Changed = true; 296 continue; 297 } 298 299 // Replace tee instructions with local.tee. The difference is that tee 300 // instructions have two defs, while local.tee instructions have one def 301 // and an index of a local to write to. 302 // 303 // - Before: 304 // TeeReg, Reg = TEE DefReg 305 // INST ..., TeeReg, ... 306 // INST ..., Reg, ... 307 // INST ..., Reg, ... 308 // * DefReg: may or may not be stackified 309 // * Reg: not stackified 310 // * TeeReg: stackified 311 // 312 // - After (when DefReg was already stackified): 313 // TeeReg = LOCAL_TEE LocalId1, DefReg 314 // INST ..., TeeReg, ... 315 // INST ..., Reg, ... 316 // INST ..., Reg, ... 317 // * Reg: mapped to LocalId1 318 // * TeeReg: stackified 319 // 320 // - After (when DefReg was not already stackified): 321 // NewReg = LOCAL_GET LocalId1 322 // TeeReg = LOCAL_TEE LocalId2, NewReg 323 // INST ..., TeeReg, ... 324 // INST ..., Reg, ... 325 // INST ..., Reg, ... 326 // * DefReg: mapped to LocalId1 327 // * Reg: mapped to LocalId2 328 // * TeeReg: stackified 329 if (WebAssembly::isTee(MI.getOpcode())) { 330 assert(MFI.isVRegStackified(MI.getOperand(0).getReg())); 331 assert(!MFI.isVRegStackified(MI.getOperand(1).getReg())); 332 Register DefReg = MI.getOperand(2).getReg(); 333 const TargetRegisterClass *RC = MRI.getRegClass(DefReg); 334 335 // Stackify the input if it isn't stackified yet. 336 if (!MFI.isVRegStackified(DefReg)) { 337 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, DefReg); 338 Register NewReg = MRI.createVirtualRegister(RC); 339 unsigned Opc = getLocalGetOpcode(RC); 340 BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), NewReg) 341 .addImm(LocalId); 342 MI.getOperand(2).setReg(NewReg); 343 MFI.stackifyVReg(MRI, NewReg); 344 } 345 346 // Replace the TEE with a LOCAL_TEE. 347 unsigned LocalId = 348 getLocalId(Reg2Local, MFI, CurLocal, MI.getOperand(1).getReg()); 349 unsigned Opc = getLocalTeeOpcode(RC); 350 BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), 351 MI.getOperand(0).getReg()) 352 .addImm(LocalId) 353 .addReg(MI.getOperand(2).getReg()); 354 355 WebAssemblyDebugValueManager(&MI).replaceWithLocal(LocalId); 356 357 MI.eraseFromParent(); 358 Changed = true; 359 continue; 360 } 361 362 // Insert local.sets for any defs that aren't stackified yet. 363 for (auto &Def : MI.defs()) { 364 Register OldReg = Def.getReg(); 365 if (!MFI.isVRegStackified(OldReg)) { 366 const TargetRegisterClass *RC = MRI.getRegClass(OldReg); 367 Register NewReg = MRI.createVirtualRegister(RC); 368 auto InsertPt = std::next(MI.getIterator()); 369 if (UseEmpty[OldReg.virtRegIndex()]) { 370 unsigned Opc = getDropOpcode(RC); 371 MachineInstr *Drop = 372 BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc)) 373 .addReg(NewReg); 374 // After the drop instruction, this reg operand will not be used 375 Drop->getOperand(0).setIsKill(); 376 if (MFI.isFrameBaseVirtual() && OldReg == MFI.getFrameBaseVreg()) 377 MFI.clearFrameBaseVreg(); 378 } else { 379 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg); 380 unsigned Opc = getLocalSetOpcode(RC); 381 382 WebAssemblyDebugValueManager(&MI).replaceWithLocal(LocalId); 383 384 BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc)) 385 .addImm(LocalId) 386 .addReg(NewReg); 387 } 388 // This register operand of the original instruction is now being used 389 // by the inserted drop or local.set instruction, so make it not dead 390 // yet. 391 Def.setReg(NewReg); 392 Def.setIsDead(false); 393 MFI.stackifyVReg(MRI, NewReg); 394 Changed = true; 395 } 396 } 397 398 // Insert local.gets for any uses that aren't stackified yet. 399 MachineInstr *InsertPt = &MI; 400 for (MachineOperand &MO : reverse(MI.explicit_uses())) { 401 if (!MO.isReg()) 402 continue; 403 404 Register OldReg = MO.getReg(); 405 406 // Inline asm may have a def in the middle of the operands. Our contract 407 // with inline asm register operands is to provide local indices as 408 // immediates. 409 if (MO.isDef()) { 410 assert(MI.isInlineAsm()); 411 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg); 412 // If this register operand is tied to another operand, we can't 413 // change it to an immediate. Untie it first. 414 MI.untieRegOperand(MO.getOperandNo()); 415 MO.ChangeToImmediate(LocalId); 416 continue; 417 } 418 419 // If we see a stackified register, prepare to insert subsequent 420 // local.gets before the start of its tree. 421 if (MFI.isVRegStackified(OldReg)) { 422 InsertPt = findStartOfTree(MO, MRI, MFI); 423 continue; 424 } 425 426 // Our contract with inline asm register operands is to provide local 427 // indices as immediates. 428 if (MI.isInlineAsm()) { 429 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg); 430 // Untie it first if this reg operand is tied to another operand. 431 MI.untieRegOperand(MO.getOperandNo()); 432 MO.ChangeToImmediate(LocalId); 433 continue; 434 } 435 436 // Insert a local.get. 437 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg); 438 const TargetRegisterClass *RC = MRI.getRegClass(OldReg); 439 Register NewReg = MRI.createVirtualRegister(RC); 440 unsigned Opc = getLocalGetOpcode(RC); 441 // Use a InsertPt as our DebugLoc, since MI may be discontinuous from 442 // the where this local is being inserted, causing non-linear stepping 443 // in the debugger or function entry points where variables aren't live 444 // yet. Alternative is previous instruction, but that is strictly worse 445 // since it can point at the previous statement. 446 // See crbug.com/1251909, crbug.com/1249745 447 InsertPt = BuildMI(MBB, InsertPt, InsertPt->getDebugLoc(), 448 TII->get(Opc), NewReg).addImm(LocalId); 449 MO.setReg(NewReg); 450 MFI.stackifyVReg(MRI, NewReg); 451 Changed = true; 452 } 453 454 // Coalesce and eliminate COPY instructions. 455 if (WebAssembly::isCopy(MI.getOpcode())) { 456 MRI.replaceRegWith(MI.getOperand(1).getReg(), 457 MI.getOperand(0).getReg()); 458 MI.eraseFromParent(); 459 Changed = true; 460 } 461 } 462 } 463 464 // Define the locals. 465 // TODO: Sort the locals for better compression. 466 MFI.setNumLocals(CurLocal - MFI.getParams().size()); 467 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) { 468 Register Reg = Register::index2VirtReg(I); 469 auto RL = Reg2Local.find(Reg); 470 if (RL == Reg2Local.end() || RL->second < MFI.getParams().size()) 471 continue; 472 473 MFI.setLocal(RL->second - MFI.getParams().size(), 474 typeForRegClass(MRI.getRegClass(Reg))); 475 Changed = true; 476 } 477 478 #ifndef NDEBUG 479 // Assert that all registers have been stackified at this point. 480 for (const MachineBasicBlock &MBB : MF) { 481 for (const MachineInstr &MI : MBB) { 482 if (MI.isDebugInstr() || MI.isLabel()) 483 continue; 484 for (const MachineOperand &MO : MI.explicit_operands()) { 485 assert( 486 (!MO.isReg() || MRI.use_empty(MO.getReg()) || 487 MFI.isVRegStackified(MO.getReg())) && 488 "WebAssemblyExplicitLocals failed to stackify a register operand"); 489 } 490 } 491 } 492 #endif 493 494 return Changed; 495 } 496