496 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8///9/// \file10/// This file converts any remaining registers into WebAssembly locals.11///12/// After register stackification and register coloring, convert non-stackified13/// registers into locals, inserting explicit local.get and local.set14/// 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"30using namespace llvm;31 32#define DEBUG_TYPE "wasm-explicit-locals"33 34namespace {35class 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 48public:49 static char ID; // Pass identification, replacement for typeid50 WebAssemblyExplicitLocals() : MachineFunctionPass(ID) {}51};52} // end anonymous namespace53 54char WebAssemblyExplicitLocals::ID = 0;55INITIALIZE_PASS(WebAssemblyExplicitLocals, DEBUG_TYPE,56 "Convert registers to WebAssembly locals", false, false)57 58FunctionPass *llvm::createWebAssemblyExplicitLocals() {59 return new WebAssemblyExplicitLocals();60}61 62static 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 one75/// if it doesn't yet have one.76static 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.88static 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.109static 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.130static 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.151static 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.172static 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 the193/// start of the expression tree.194static 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 start202 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 them220// will be correctly dropped later.221static 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 231bool 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 any267 // 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 insert272 // drops to their defs.273 // And unstackify any stackified registers that don't have any uses, so that274 // they can be dropped later. This can happen when transformations after275 // 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 tee300 // instructions have two defs, while local.tee instructions have one def301 // and an index of a local to write to.302 //303 // - Before:304 // TeeReg, Reg = TEE DefReg305 // INST ..., TeeReg, ...306 // INST ..., Reg, ...307 // INST ..., Reg, ...308 // * DefReg: may or may not be stackified309 // * Reg: not stackified310 // * TeeReg: stackified311 //312 // - After (when DefReg was already stackified):313 // TeeReg = LOCAL_TEE LocalId1, DefReg314 // INST ..., TeeReg, ...315 // INST ..., Reg, ...316 // INST ..., Reg, ...317 // * Reg: mapped to LocalId1318 // * TeeReg: stackified319 //320 // - After (when DefReg was not already stackified):321 // NewReg = LOCAL_GET LocalId1322 // TeeReg = LOCAL_TEE LocalId2, NewReg323 // INST ..., TeeReg, ...324 // INST ..., Reg, ...325 // INST ..., Reg, ...326 // * DefReg: mapped to LocalId1327 // * Reg: mapped to LocalId2328 // * TeeReg: stackified329 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 used375 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 used389 // by the inserted drop or local.set instruction, so make it not dead390 // 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 contract407 // with inline asm register operands is to provide local indices as408 // 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't413 // 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 subsequent420 // 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 local427 // 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 from442 // the where this local is being inserted, causing non-linear stepping443 // in the debugger or function entry points where variables aren't live444 // yet. Alternative is previous instruction, but that is strictly worse445 // since it can point at the previous statement.446 // See crbug.com/1251909, crbug.com/1249745447 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 NDEBUG479 // 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#endif493 494 return Changed;495}496