llvm/lib/Target/WebAssembly/WebAssemblyExplicitLocals.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-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 "Utils/WebAssemblyUtilities.h"
  20 #include "WebAssembly.h"
  21 #include "WebAssemblyDebugValueManager.h"
  22 #include "WebAssemblyMachineFunctionInfo.h"
  23 #include "WebAssemblySubtarget.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<MachineBlockFrequencyInfo>();
  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::virtReg2Index(Reg) << '\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   llvm_unreachable("Unexpected register class");
 104 }
 105
 106 /// Get the appropriate local.get opcode for the given register class.
 107 static unsigned getLocalGetOpcode(const TargetRegisterClass *RC) {
 108   if (RC == &WebAssembly::I32RegClass)
 109     return WebAssembly::LOCAL_GET_I32;
 110   if (RC == &WebAssembly::I64RegClass)
 111     return WebAssembly::LOCAL_GET_I64;
 112   if (RC == &WebAssembly::F32RegClass)
 113     return WebAssembly::LOCAL_GET_F32;
 114   if (RC == &WebAssembly::F64RegClass)
 115     return WebAssembly::LOCAL_GET_F64;
 116   if (RC == &WebAssembly::V128RegClass)
 117     return WebAssembly::LOCAL_GET_V128;
 118   if (RC == &WebAssembly::FUNCREFRegClass)
 119     return WebAssembly::LOCAL_GET_FUNCREF;
 120   if (RC == &WebAssembly::EXTERNREFRegClass)
 121     return WebAssembly::LOCAL_GET_EXTERNREF;
 122   llvm_unreachable("Unexpected register class");
 123 }
 124
 125 /// Get the appropriate local.set opcode for the given register class.
 126 static unsigned getLocalSetOpcode(const TargetRegisterClass *RC) {
 127   if (RC == &WebAssembly::I32RegClass)
 128     return WebAssembly::LOCAL_SET_I32;
 129   if (RC == &WebAssembly::I64RegClass)
 130     return WebAssembly::LOCAL_SET_I64;
 131   if (RC == &WebAssembly::F32RegClass)
 132     return WebAssembly::LOCAL_SET_F32;
 133   if (RC == &WebAssembly::F64RegClass)
 134     return WebAssembly::LOCAL_SET_F64;
 135   if (RC == &WebAssembly::V128RegClass)
 136     return WebAssembly::LOCAL_SET_V128;
 137   if (RC == &WebAssembly::FUNCREFRegClass)
 138     return WebAssembly::LOCAL_SET_FUNCREF;
 139   if (RC == &WebAssembly::EXTERNREFRegClass)
 140     return WebAssembly::LOCAL_SET_EXTERNREF;
 141   llvm_unreachable("Unexpected register class");
 142 }
 143
 144 /// Get the appropriate local.tee opcode for the given register class.
 145 static unsigned getLocalTeeOpcode(const TargetRegisterClass *RC) {
 146   if (RC == &WebAssembly::I32RegClass)
 147     return WebAssembly::LOCAL_TEE_I32;
 148   if (RC == &WebAssembly::I64RegClass)
 149     return WebAssembly::LOCAL_TEE_I64;
 150   if (RC == &WebAssembly::F32RegClass)
 151     return WebAssembly::LOCAL_TEE_F32;
 152   if (RC == &WebAssembly::F64RegClass)
 153     return WebAssembly::LOCAL_TEE_F64;
 154   if (RC == &WebAssembly::V128RegClass)
 155     return WebAssembly::LOCAL_TEE_V128;
 156   if (RC == &WebAssembly::FUNCREFRegClass)
 157     return WebAssembly::LOCAL_TEE_FUNCREF;
 158   if (RC == &WebAssembly::EXTERNREFRegClass)
 159     return WebAssembly::LOCAL_TEE_EXTERNREF;
 160   llvm_unreachable("Unexpected register class");
 161 }
 162
 163 /// Get the type associated with the given register class.
 164 static MVT typeForRegClass(const TargetRegisterClass *RC) {
 165   if (RC == &WebAssembly::I32RegClass)
 166     return MVT::i32;
 167   if (RC == &WebAssembly::I64RegClass)
 168     return MVT::i64;
 169   if (RC == &WebAssembly::F32RegClass)
 170     return MVT::f32;
 171   if (RC == &WebAssembly::F64RegClass)
 172     return MVT::f64;
 173   if (RC == &WebAssembly::V128RegClass)
 174     return MVT::v16i8;
 175   if (RC == &WebAssembly::FUNCREFRegClass)
 176     return MVT::funcref;
 177   if (RC == &WebAssembly::EXTERNREFRegClass)
 178     return MVT::externref;
 179   llvm_unreachable("unrecognized register class");
 180 }
 181
 182 /// Given a MachineOperand of a stackified vreg, return the instruction at the
 183 /// start of the expression tree.
 184 static MachineInstr *findStartOfTree(MachineOperand &MO,
 185                                      MachineRegisterInfo &MRI,
 186                                      const WebAssemblyFunctionInfo &MFI) {
 187   Register Reg = MO.getReg();
 188   assert(MFI.isVRegStackified(Reg));
 189   MachineInstr *Def = MRI.getVRegDef(Reg);
 190
 191   // If this instruction has any non-stackified defs, it is the start
 192   for (auto DefReg : Def->defs()) {
 193     if (!MFI.isVRegStackified(DefReg.getReg())) {
 194       return Def;
 195     }
 196   }
 197
 198   // Find the first stackified use and proceed from there.
 199   for (MachineOperand &DefMO : Def->explicit_uses()) {
 200     if (!DefMO.isReg())
 201       continue;
 202     return findStartOfTree(DefMO, MRI, MFI);
 203   }
 204
 205   // If there were no stackified uses, we've reached the start.
 206   return Def;
 207 }
 208
 209 bool WebAssemblyExplicitLocals::runOnMachineFunction(MachineFunction &MF) {
 210   LLVM_DEBUG(dbgs() << "********** Make Locals Explicit **********\n"
 211                        "********** Function: "
 212                     << MF.getName() << '\n');
 213
 214   bool Changed = false;
 215   MachineRegisterInfo &MRI = MF.getRegInfo();
 216   WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
 217   const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
 218
 219   // Map non-stackified virtual registers to their local ids.
 220   DenseMap<unsigned, unsigned> Reg2Local;
 221
 222   // Handle ARGUMENTS first to ensure that they get the designated numbers.
 223   for (MachineBasicBlock::iterator I = MF.begin()->begin(),
 224                                    E = MF.begin()->end();
 225        I != E;) {
 226     MachineInstr &MI = *I++;
 227     if (!WebAssembly::isArgument(MI.getOpcode()))
 228       break;
 229     Register Reg = MI.getOperand(0).getReg();
 230     assert(!MFI.isVRegStackified(Reg));
 231     auto Local = static_cast<unsigned>(MI.getOperand(1).getImm());
 232     Reg2Local[Reg] = Local;
 233     checkFrameBase(MFI, Local, Reg);
 234
 235     // Update debug value to point to the local before removing.
 236     WebAssemblyDebugValueManager(&MI).replaceWithLocal(Local);
 237
 238     MI.eraseFromParent();
 239     Changed = true;
 240   }
 241
 242   // Start assigning local numbers after the last parameter and after any
 243   // already-assigned locals.
 244   unsigned CurLocal = static_cast<unsigned>(MFI.getParams().size());
 245   CurLocal += static_cast<unsigned>(MFI.getLocals().size());
 246
 247   // Precompute the set of registers that are unused, so that we can insert
 248   // drops to their defs.
 249   BitVector UseEmpty(MRI.getNumVirtRegs());
 250   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I)
 251     UseEmpty[I] = MRI.use_empty(Register::index2VirtReg(I));
 252
 253   // Visit each instruction in the function.
 254   for (MachineBasicBlock &MBB : MF) {
 255     for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
 256       MachineInstr &MI = *I++;
 257       assert(!WebAssembly::isArgument(MI.getOpcode()));
 258
 259       if (MI.isDebugInstr() || MI.isLabel())
 260         continue;
 261
 262       if (MI.getOpcode() == WebAssembly::IMPLICIT_DEF) {
 263         MI.eraseFromParent();
 264         Changed = true;
 265         continue;
 266       }
 267
 268       // Replace tee instructions with local.tee. The difference is that tee
 269       // instructions have two defs, while local.tee instructions have one def
 270       // and an index of a local to write to.
 271       if (WebAssembly::isTee(MI.getOpcode())) {
 272         assert(MFI.isVRegStackified(MI.getOperand(0).getReg()));
 273         assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
 274         Register OldReg = MI.getOperand(2).getReg();
 275         const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
 276
 277         // Stackify the input if it isn't stackified yet.
 278         if (!MFI.isVRegStackified(OldReg)) {
 279           unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg);
 280           Register NewReg = MRI.createVirtualRegister(RC);
 281           unsigned Opc = getLocalGetOpcode(RC);
 282           BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), NewReg)
 283               .addImm(LocalId);
 284           MI.getOperand(2).setReg(NewReg);
 285           MFI.stackifyVReg(MRI, NewReg);
 286         }
 287
 288         // Replace the TEE with a LOCAL_TEE.
 289         unsigned LocalId =
 290             getLocalId(Reg2Local, MFI, CurLocal, MI.getOperand(1).getReg());
 291         unsigned Opc = getLocalTeeOpcode(RC);
 292         BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc),
 293                 MI.getOperand(0).getReg())
 294             .addImm(LocalId)
 295             .addReg(MI.getOperand(2).getReg());
 296
 297         WebAssemblyDebugValueManager(&MI).replaceWithLocal(LocalId);
 298
 299         MI.eraseFromParent();
 300         Changed = true;
 301         continue;
 302       }
 303
 304       // Insert local.sets for any defs that aren't stackified yet.
 305       for (auto &Def : MI.defs()) {
 306         Register OldReg = Def.getReg();
 307         if (!MFI.isVRegStackified(OldReg)) {
 308           const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
 309           Register NewReg = MRI.createVirtualRegister(RC);
 310           auto InsertPt = std::next(MI.getIterator());
 311           if (UseEmpty[Register::virtReg2Index(OldReg)]) {
 312             unsigned Opc = getDropOpcode(RC);
 313             MachineInstr *Drop =
 314                 BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
 315                     .addReg(NewReg);
 316             // After the drop instruction, this reg operand will not be used
 317             Drop->getOperand(0).setIsKill();
 318             if (MFI.isFrameBaseVirtual() && OldReg == MFI.getFrameBaseVreg())
 319               MFI.clearFrameBaseVreg();
 320           } else {
 321             unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg);
 322             unsigned Opc = getLocalSetOpcode(RC);
 323
 324             WebAssemblyDebugValueManager(&MI).replaceWithLocal(LocalId);
 325
 326             BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
 327                 .addImm(LocalId)
 328                 .addReg(NewReg);
 329           }
 330           // This register operand of the original instruction is now being used
 331           // by the inserted drop or local.set instruction, so make it not dead
 332           // yet.
 333           Def.setReg(NewReg);
 334           Def.setIsDead(false);
 335           MFI.stackifyVReg(MRI, NewReg);
 336           Changed = true;
 337         }
 338       }
 339
 340       // Insert local.gets for any uses that aren't stackified yet.
 341       MachineInstr *InsertPt = &MI;
 342       for (MachineOperand &MO : reverse(MI.explicit_uses())) {
 343         if (!MO.isReg())
 344           continue;
 345
 346         Register OldReg = MO.getReg();
 347
 348         // Inline asm may have a def in the middle of the operands. Our contract
 349         // with inline asm register operands is to provide local indices as
 350         // immediates.
 351         if (MO.isDef()) {
 352           assert(MI.isInlineAsm());
 353           unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg);
 354           // If this register operand is tied to another operand, we can't
 355           // change it to an immediate. Untie it first.
 356           MI.untieRegOperand(MI.getOperandNo(&MO));
 357           MO.ChangeToImmediate(LocalId);
 358           continue;
 359         }
 360
 361         // If we see a stackified register, prepare to insert subsequent
 362         // local.gets before the start of its tree.
 363         if (MFI.isVRegStackified(OldReg)) {
 364           InsertPt = findStartOfTree(MO, MRI, MFI);
 365           continue;
 366         }
 367
 368         // Our contract with inline asm register operands is to provide local
 369         // indices as immediates.
 370         if (MI.isInlineAsm()) {
 371           unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg);
 372           // Untie it first if this reg operand is tied to another operand.
 373           MI.untieRegOperand(MI.getOperandNo(&MO));
 374           MO.ChangeToImmediate(LocalId);
 375           continue;
 376         }
 377
 378         // Insert a local.get.
 379         unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg);
 380         const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
 381         Register NewReg = MRI.createVirtualRegister(RC);
 382         unsigned Opc = getLocalGetOpcode(RC);
 383         InsertPt =
 384             BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc), NewReg)
 385                 .addImm(LocalId);
 386         MO.setReg(NewReg);
 387         MFI.stackifyVReg(MRI, NewReg);
 388         Changed = true;
 389       }
 390
 391       // Coalesce and eliminate COPY instructions.
 392       if (WebAssembly::isCopy(MI.getOpcode())) {
 393         MRI.replaceRegWith(MI.getOperand(1).getReg(),
 394                            MI.getOperand(0).getReg());
 395         MI.eraseFromParent();
 396         Changed = true;
 397       }
 398     }
 399   }
 400
 401   // Define the locals.
 402   // TODO: Sort the locals for better compression.
 403   MFI.setNumLocals(CurLocal - MFI.getParams().size());
 404   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
 405     unsigned Reg = Register::index2VirtReg(I);
 406     auto RL = Reg2Local.find(Reg);
 407     if (RL == Reg2Local.end() || RL->second < MFI.getParams().size())
 408       continue;
 409
 410     MFI.setLocal(RL->second - MFI.getParams().size(),
 411                  typeForRegClass(MRI.getRegClass(Reg)));
 412     Changed = true;
 413   }
 414
 415 #ifndef NDEBUG
 416   // Assert that all registers have been stackified at this point.
 417   for (const MachineBasicBlock &MBB : MF) {
 418     for (const MachineInstr &MI : MBB) {
 419       if (MI.isDebugInstr() || MI.isLabel())
 420         continue;
 421       for (const MachineOperand &MO : MI.explicit_operands()) {
 422         assert(
 423             (!MO.isReg() || MRI.use_empty(MO.getReg()) ||
 424              MFI.isVRegStackified(MO.getReg())) &&
 425             "WebAssemblyExplicitLocals failed to stackify a register operand");
 426       }
 427     }
 428   }
 429 #endif
 430
 431   return Changed;
 432 }