lib/Target/WebAssembly/WebAssemblyExplicitLocals.cpp

   1 //===-- WebAssemblyExplicitLocals.cpp - Make Locals Explicit --------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 ///
  10 /// \file
  11 /// This file converts any remaining registers into WebAssembly locals.
  12 ///
  13 /// After register stackification and register coloring, convert non-stackified
  14 /// registers into locals, inserting explicit local.get and local.set
  15 /// instructions.
  16 ///
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
  20 #include "WebAssembly.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 // A command-line option to disable this pass, and keep implicit locals
  35 // for the purpose of testing with lit/llc ONLY.
  36 // This produces output which is not valid WebAssembly, and is not supported
  37 // by assemblers/disassemblers and other MC based tools.
  38 static cl::opt<bool> WasmDisableExplicitLocals(
  39     "wasm-disable-explicit-locals", cl::Hidden,
  40     cl::desc("WebAssembly: output implicit locals in"
  41              " instruction output for test purposes only."),
  42     cl::init(false));
  43
  44 namespace {
  45 class WebAssemblyExplicitLocals final : public MachineFunctionPass {
  46   StringRef getPassName() const override {
  47     return "WebAssembly Explicit Locals";
  48   }
  49
  50   void getAnalysisUsage(AnalysisUsage &AU) const override {
  51     AU.setPreservesCFG();
  52     AU.addPreserved<MachineBlockFrequencyInfo>();
  53     MachineFunctionPass::getAnalysisUsage(AU);
  54   }
  55
  56   bool runOnMachineFunction(MachineFunction &MF) override;
  57
  58 public:
  59   static char ID; // Pass identification, replacement for typeid
  60   WebAssemblyExplicitLocals() : MachineFunctionPass(ID) {}
  61 };
  62 } // end anonymous namespace
  63
  64 char WebAssemblyExplicitLocals::ID = 0;
  65 INITIALIZE_PASS(WebAssemblyExplicitLocals, DEBUG_TYPE,
  66                 "Convert registers to WebAssembly locals", false, false)
  67
  68 FunctionPass *llvm::createWebAssemblyExplicitLocals() {
  69   return new WebAssemblyExplicitLocals();
  70 }
  71
  72 /// Return a local id number for the given register, assigning it a new one
  73 /// if it doesn't yet have one.
  74 static unsigned getLocalId(DenseMap<unsigned, unsigned> &Reg2Local,
  75                            unsigned &CurLocal, unsigned Reg) {
  76   auto P = Reg2Local.insert(std::make_pair(Reg, CurLocal));
  77   if (P.second)
  78     ++CurLocal;
  79   return P.first->second;
  80 }
  81
  82 /// Get the appropriate drop opcode for the given register class.
  83 static unsigned getDropOpcode(const TargetRegisterClass *RC) {
  84   if (RC == &WebAssembly::I32RegClass)
  85     return WebAssembly::DROP_I32;
  86   if (RC == &WebAssembly::I64RegClass)
  87     return WebAssembly::DROP_I64;
  88   if (RC == &WebAssembly::F32RegClass)
  89     return WebAssembly::DROP_F32;
  90   if (RC == &WebAssembly::F64RegClass)
  91     return WebAssembly::DROP_F64;
  92   if (RC == &WebAssembly::V128RegClass)
  93     return WebAssembly::DROP_V128;
  94   if (RC == &WebAssembly::EXCEPT_REFRegClass)
  95     return WebAssembly::DROP_EXCEPT_REF;
  96   llvm_unreachable("Unexpected register class");
  97 }
  98
  99 /// Get the appropriate local.get opcode for the given register class.
 100 static unsigned getGetLocalOpcode(const TargetRegisterClass *RC) {
 101   if (RC == &WebAssembly::I32RegClass)
 102     return WebAssembly::LOCAL_GET_I32;
 103   if (RC == &WebAssembly::I64RegClass)
 104     return WebAssembly::LOCAL_GET_I64;
 105   if (RC == &WebAssembly::F32RegClass)
 106     return WebAssembly::LOCAL_GET_F32;
 107   if (RC == &WebAssembly::F64RegClass)
 108     return WebAssembly::LOCAL_GET_F64;
 109   if (RC == &WebAssembly::V128RegClass)
 110     return WebAssembly::LOCAL_GET_V128;
 111   if (RC == &WebAssembly::EXCEPT_REFRegClass)
 112     return WebAssembly::LOCAL_GET_EXCEPT_REF;
 113   llvm_unreachable("Unexpected register class");
 114 }
 115
 116 /// Get the appropriate local.set opcode for the given register class.
 117 static unsigned getSetLocalOpcode(const TargetRegisterClass *RC) {
 118   if (RC == &WebAssembly::I32RegClass)
 119     return WebAssembly::LOCAL_SET_I32;
 120   if (RC == &WebAssembly::I64RegClass)
 121     return WebAssembly::LOCAL_SET_I64;
 122   if (RC == &WebAssembly::F32RegClass)
 123     return WebAssembly::LOCAL_SET_F32;
 124   if (RC == &WebAssembly::F64RegClass)
 125     return WebAssembly::LOCAL_SET_F64;
 126   if (RC == &WebAssembly::V128RegClass)
 127     return WebAssembly::LOCAL_SET_V128;
 128   if (RC == &WebAssembly::EXCEPT_REFRegClass)
 129     return WebAssembly::LOCAL_SET_EXCEPT_REF;
 130   llvm_unreachable("Unexpected register class");
 131 }
 132
 133 /// Get the appropriate local.tee opcode for the given register class.
 134 static unsigned getTeeLocalOpcode(const TargetRegisterClass *RC) {
 135   if (RC == &WebAssembly::I32RegClass)
 136     return WebAssembly::LOCAL_TEE_I32;
 137   if (RC == &WebAssembly::I64RegClass)
 138     return WebAssembly::LOCAL_TEE_I64;
 139   if (RC == &WebAssembly::F32RegClass)
 140     return WebAssembly::LOCAL_TEE_F32;
 141   if (RC == &WebAssembly::F64RegClass)
 142     return WebAssembly::LOCAL_TEE_F64;
 143   if (RC == &WebAssembly::V128RegClass)
 144     return WebAssembly::LOCAL_TEE_V128;
 145   if (RC == &WebAssembly::EXCEPT_REFRegClass)
 146     return WebAssembly::LOCAL_TEE_EXCEPT_REF;
 147   llvm_unreachable("Unexpected register class");
 148 }
 149
 150 /// Get the type associated with the given register class.
 151 static MVT typeForRegClass(const TargetRegisterClass *RC) {
 152   if (RC == &WebAssembly::I32RegClass)
 153     return MVT::i32;
 154   if (RC == &WebAssembly::I64RegClass)
 155     return MVT::i64;
 156   if (RC == &WebAssembly::F32RegClass)
 157     return MVT::f32;
 158   if (RC == &WebAssembly::F64RegClass)
 159     return MVT::f64;
 160   if (RC == &WebAssembly::V128RegClass)
 161     return MVT::v16i8;
 162   if (RC == &WebAssembly::EXCEPT_REFRegClass)
 163     return MVT::ExceptRef;
 164   llvm_unreachable("unrecognized register class");
 165 }
 166
 167 /// Given a MachineOperand of a stackified vreg, return the instruction at the
 168 /// start of the expression tree.
 169 static MachineInstr *findStartOfTree(MachineOperand &MO,
 170                                      MachineRegisterInfo &MRI,
 171                                      WebAssemblyFunctionInfo &MFI) {
 172   unsigned Reg = MO.getReg();
 173   assert(MFI.isVRegStackified(Reg));
 174   MachineInstr *Def = MRI.getVRegDef(Reg);
 175
 176   // Find the first stackified use and proceed from there.
 177   for (MachineOperand &DefMO : Def->explicit_uses()) {
 178     if (!DefMO.isReg())
 179       continue;
 180     return findStartOfTree(DefMO, MRI, MFI);
 181   }
 182
 183   // If there were no stackified uses, we've reached the start.
 184   return Def;
 185 }
 186
 187 bool WebAssemblyExplicitLocals::runOnMachineFunction(MachineFunction &MF) {
 188   LLVM_DEBUG(dbgs() << "********** Make Locals Explicit **********\n"
 189                        "********** Function: "
 190                     << MF.getName() << '\n');
 191
 192   // Disable this pass if directed to do so.
 193   if (WasmDisableExplicitLocals)
 194     return false;
 195
 196   bool Changed = false;
 197   MachineRegisterInfo &MRI = MF.getRegInfo();
 198   WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
 199   const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
 200
 201   // Map non-stackified virtual registers to their local ids.
 202   DenseMap<unsigned, unsigned> Reg2Local;
 203
 204   // Handle ARGUMENTS first to ensure that they get the designated numbers.
 205   for (MachineBasicBlock::iterator I = MF.begin()->begin(),
 206                                    E = MF.begin()->end();
 207        I != E;) {
 208     MachineInstr &MI = *I++;
 209     if (!WebAssembly::isArgument(MI))
 210       break;
 211     unsigned Reg = MI.getOperand(0).getReg();
 212     assert(!MFI.isVRegStackified(Reg));
 213     Reg2Local[Reg] = static_cast<unsigned>(MI.getOperand(1).getImm());
 214     MI.eraseFromParent();
 215     Changed = true;
 216   }
 217
 218   // Start assigning local numbers after the last parameter.
 219   unsigned CurLocal = static_cast<unsigned>(MFI.getParams().size());
 220
 221   // Precompute the set of registers that are unused, so that we can insert
 222   // drops to their defs.
 223   BitVector UseEmpty(MRI.getNumVirtRegs());
 224   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I)
 225     UseEmpty[I] = MRI.use_empty(TargetRegisterInfo::index2VirtReg(I));
 226
 227   // Visit each instruction in the function.
 228   for (MachineBasicBlock &MBB : MF) {
 229     for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
 230       MachineInstr &MI = *I++;
 231       assert(!WebAssembly::isArgument(MI));
 232
 233       if (MI.isDebugInstr() || MI.isLabel())
 234         continue;
 235
 236       // Replace tee instructions with local.tee. The difference is that tee
 237       // instructions have two defs, while local.tee instructions have one def
 238       // and an index of a local to write to.
 239       if (WebAssembly::isTee(MI)) {
 240         assert(MFI.isVRegStackified(MI.getOperand(0).getReg()));
 241         assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
 242         unsigned OldReg = MI.getOperand(2).getReg();
 243         const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
 244
 245         // Stackify the input if it isn't stackified yet.
 246         if (!MFI.isVRegStackified(OldReg)) {
 247           unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
 248           unsigned NewReg = MRI.createVirtualRegister(RC);
 249           unsigned Opc = getGetLocalOpcode(RC);
 250           BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), NewReg)
 251               .addImm(LocalId);
 252           MI.getOperand(2).setReg(NewReg);
 253           MFI.stackifyVReg(NewReg);
 254         }
 255
 256         // Replace the TEE with a LOCAL_TEE.
 257         unsigned LocalId =
 258             getLocalId(Reg2Local, CurLocal, MI.getOperand(1).getReg());
 259         unsigned Opc = getTeeLocalOpcode(RC);
 260         BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc),
 261                 MI.getOperand(0).getReg())
 262             .addImm(LocalId)
 263             .addReg(MI.getOperand(2).getReg());
 264
 265         MI.eraseFromParent();
 266         Changed = true;
 267         continue;
 268       }
 269
 270       // Insert local.sets for any defs that aren't stackified yet. Currently
 271       // we handle at most one def.
 272       assert(MI.getDesc().getNumDefs() <= 1);
 273       if (MI.getDesc().getNumDefs() == 1) {
 274         unsigned OldReg = MI.getOperand(0).getReg();
 275         if (!MFI.isVRegStackified(OldReg)) {
 276           const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
 277           unsigned NewReg = MRI.createVirtualRegister(RC);
 278           auto InsertPt = std::next(MachineBasicBlock::iterator(&MI));
 279           if (MI.getOpcode() == WebAssembly::IMPLICIT_DEF) {
 280             MI.eraseFromParent();
 281             Changed = true;
 282             continue;
 283           }
 284           if (UseEmpty[TargetRegisterInfo::virtReg2Index(OldReg)]) {
 285             unsigned Opc = getDropOpcode(RC);
 286             MachineInstr *Drop =
 287                 BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
 288                     .addReg(NewReg);
 289             // After the drop instruction, this reg operand will not be used
 290             Drop->getOperand(0).setIsKill();
 291           } else {
 292             unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
 293             unsigned Opc = getSetLocalOpcode(RC);
 294             BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
 295                 .addImm(LocalId)
 296                 .addReg(NewReg);
 297           }
 298           MI.getOperand(0).setReg(NewReg);
 299           // This register operand of the original instruction is now being used
 300           // by the inserted drop or local.set instruction, so make it not dead
 301           // yet.
 302           MI.getOperand(0).setIsDead(false);
 303           MFI.stackifyVReg(NewReg);
 304           Changed = true;
 305         }
 306       }
 307
 308       // Insert local.gets for any uses that aren't stackified yet.
 309       MachineInstr *InsertPt = &MI;
 310       for (MachineOperand &MO : reverse(MI.explicit_uses())) {
 311         if (!MO.isReg())
 312           continue;
 313
 314         unsigned OldReg = MO.getReg();
 315
 316         // Inline asm may have a def in the middle of the operands. Our contract
 317         // with inline asm register operands is to provide local indices as
 318         // immediates.
 319         if (MO.isDef()) {
 320           assert(MI.getOpcode() == TargetOpcode::INLINEASM);
 321           unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
 322           // If this register operand is tied to another operand, we can't
 323           // change it to an immediate. Untie it first.
 324           MI.untieRegOperand(MI.getOperandNo(&MO));
 325           MO.ChangeToImmediate(LocalId);
 326           continue;
 327         }
 328
 329         // If we see a stackified register, prepare to insert subsequent
 330         // local.gets before the start of its tree.
 331         if (MFI.isVRegStackified(OldReg)) {
 332           InsertPt = findStartOfTree(MO, MRI, MFI);
 333           continue;
 334         }
 335
 336         // Our contract with inline asm register operands is to provide local
 337         // indices as immediates.
 338         if (MI.getOpcode() == TargetOpcode::INLINEASM) {
 339           unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
 340           // Untie it first if this reg operand is tied to another operand.
 341           MI.untieRegOperand(MI.getOperandNo(&MO));
 342           MO.ChangeToImmediate(LocalId);
 343           continue;
 344         }
 345
 346         // Insert a local.get.
 347         unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
 348         const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
 349         unsigned NewReg = MRI.createVirtualRegister(RC);
 350         unsigned Opc = getGetLocalOpcode(RC);
 351         InsertPt =
 352             BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc), NewReg)
 353                 .addImm(LocalId);
 354         MO.setReg(NewReg);
 355         MFI.stackifyVReg(NewReg);
 356         Changed = true;
 357       }
 358
 359       // Coalesce and eliminate COPY instructions.
 360       if (WebAssembly::isCopy(MI)) {
 361         MRI.replaceRegWith(MI.getOperand(1).getReg(),
 362                            MI.getOperand(0).getReg());
 363         MI.eraseFromParent();
 364         Changed = true;
 365       }
 366     }
 367   }
 368
 369   // Define the locals.
 370   // TODO: Sort the locals for better compression.
 371   MFI.setNumLocals(CurLocal - MFI.getParams().size());
 372   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
 373     unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
 374     auto RL = Reg2Local.find(Reg);
 375     if (RL == Reg2Local.end() || RL->second < MFI.getParams().size())
 376       continue;
 377
 378     MFI.setLocal(RL->second - MFI.getParams().size(),
 379                  typeForRegClass(MRI.getRegClass(Reg)));
 380     Changed = true;
 381   }
 382
 383 #ifndef NDEBUG
 384   // Assert that all registers have been stackified at this point.
 385   for (const MachineBasicBlock &MBB : MF) {
 386     for (const MachineInstr &MI : MBB) {
 387       if (MI.isDebugInstr() || MI.isLabel())
 388         continue;
 389       for (const MachineOperand &MO : MI.explicit_operands()) {
 390         assert(
 391             (!MO.isReg() || MRI.use_empty(MO.getReg()) ||
 392              MFI.isVRegStackified(MO.getReg())) &&
 393             "WebAssemblyExplicitLocals failed to stackify a register operand");
 394       }
 395     }
 396   }
 397 #endif
 398
 399   return Changed;
 400 }