contrib/llvm/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 /// \brief 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 get_local and set_local
  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. Note that this produces output
  35 // which is not valid WebAssembly, though it may be more convenient for writing
  36 // LLVM unit tests with.
  37 static cl::opt<bool> DisableWebAssemblyExplicitLocals(
  38     "disable-wasm-explicit-locals", cl::ReallyHidden,
  39     cl::desc("WebAssembly: Disable emission of get_local/set_local."),
  40     cl::init(false));
  41
  42 namespace {
  43 class WebAssemblyExplicitLocals final : public MachineFunctionPass {
  44   StringRef getPassName() const override {
  45     return "WebAssembly Explicit Locals";
  46   }
  47
  48   void getAnalysisUsage(AnalysisUsage &AU) const override {
  49     AU.setPreservesCFG();
  50     AU.addPreserved<MachineBlockFrequencyInfo>();
  51     MachineFunctionPass::getAnalysisUsage(AU);
  52   }
  53
  54   bool runOnMachineFunction(MachineFunction &MF) override;
  55
  56 public:
  57   static char ID; // Pass identification, replacement for typeid
  58   WebAssemblyExplicitLocals() : MachineFunctionPass(ID) {}
  59 };
  60 } // end anonymous namespace
  61
  62 char WebAssemblyExplicitLocals::ID = 0;
  63 FunctionPass *llvm::createWebAssemblyExplicitLocals() {
  64   return new WebAssemblyExplicitLocals();
  65 }
  66
  67 /// Return a local id number for the given register, assigning it a new one
  68 /// if it doesn't yet have one.
  69 static unsigned getLocalId(DenseMap<unsigned, unsigned> &Reg2Local,
  70                            unsigned &CurLocal, unsigned Reg) {
  71   auto P = Reg2Local.insert(std::make_pair(Reg, CurLocal));
  72   if (P.second)
  73     ++CurLocal;
  74   return P.first->second;
  75 }
  76
  77 /// Get the appropriate drop opcode for the given register class.
  78 static unsigned getDropOpcode(const TargetRegisterClass *RC) {
  79   if (RC == &WebAssembly::I32RegClass)
  80     return WebAssembly::DROP_I32;
  81   if (RC == &WebAssembly::I64RegClass)
  82     return WebAssembly::DROP_I64;
  83   if (RC == &WebAssembly::F32RegClass)
  84     return WebAssembly::DROP_F32;
  85   if (RC == &WebAssembly::F64RegClass)
  86     return WebAssembly::DROP_F64;
  87   if (RC == &WebAssembly::V128RegClass)
  88     return WebAssembly::DROP_V128;
  89   llvm_unreachable("Unexpected register class");
  90 }
  91
  92 /// Get the appropriate get_local opcode for the given register class.
  93 static unsigned getGetLocalOpcode(const TargetRegisterClass *RC) {
  94   if (RC == &WebAssembly::I32RegClass)
  95     return WebAssembly::GET_LOCAL_I32;
  96   if (RC == &WebAssembly::I64RegClass)
  97     return WebAssembly::GET_LOCAL_I64;
  98   if (RC == &WebAssembly::F32RegClass)
  99     return WebAssembly::GET_LOCAL_F32;
 100   if (RC == &WebAssembly::F64RegClass)
 101     return WebAssembly::GET_LOCAL_F64;
 102   if (RC == &WebAssembly::V128RegClass)
 103     return WebAssembly::GET_LOCAL_V128;
 104   llvm_unreachable("Unexpected register class");
 105 }
 106
 107 /// Get the appropriate set_local opcode for the given register class.
 108 static unsigned getSetLocalOpcode(const TargetRegisterClass *RC) {
 109   if (RC == &WebAssembly::I32RegClass)
 110     return WebAssembly::SET_LOCAL_I32;
 111   if (RC == &WebAssembly::I64RegClass)
 112     return WebAssembly::SET_LOCAL_I64;
 113   if (RC == &WebAssembly::F32RegClass)
 114     return WebAssembly::SET_LOCAL_F32;
 115   if (RC == &WebAssembly::F64RegClass)
 116     return WebAssembly::SET_LOCAL_F64;
 117   if (RC == &WebAssembly::V128RegClass)
 118     return WebAssembly::SET_LOCAL_V128;
 119   llvm_unreachable("Unexpected register class");
 120 }
 121
 122 /// Get the appropriate tee_local opcode for the given register class.
 123 static unsigned getTeeLocalOpcode(const TargetRegisterClass *RC) {
 124   if (RC == &WebAssembly::I32RegClass)
 125     return WebAssembly::TEE_LOCAL_I32;
 126   if (RC == &WebAssembly::I64RegClass)
 127     return WebAssembly::TEE_LOCAL_I64;
 128   if (RC == &WebAssembly::F32RegClass)
 129     return WebAssembly::TEE_LOCAL_F32;
 130   if (RC == &WebAssembly::F64RegClass)
 131     return WebAssembly::TEE_LOCAL_F64;
 132   if (RC == &WebAssembly::V128RegClass)
 133     return WebAssembly::TEE_LOCAL_V128;
 134   llvm_unreachable("Unexpected register class");
 135 }
 136
 137 /// Get the type associated with the given register class.
 138 static MVT typeForRegClass(const TargetRegisterClass *RC) {
 139   if (RC == &WebAssembly::I32RegClass)
 140     return MVT::i32;
 141   if (RC == &WebAssembly::I64RegClass)
 142     return MVT::i64;
 143   if (RC == &WebAssembly::F32RegClass)
 144     return MVT::f32;
 145   if (RC == &WebAssembly::F64RegClass)
 146     return MVT::f64;
 147   llvm_unreachable("unrecognized register class");
 148 }
 149
 150 /// Given a MachineOperand of a stackified vreg, return the instruction at the
 151 /// start of the expression tree.
 152 static MachineInstr *FindStartOfTree(MachineOperand &MO,
 153                                      MachineRegisterInfo &MRI,
 154                                      WebAssemblyFunctionInfo &MFI) {
 155   unsigned Reg = MO.getReg();
 156   assert(MFI.isVRegStackified(Reg));
 157   MachineInstr *Def = MRI.getVRegDef(Reg);
 158
 159   // Find the first stackified use and proceed from there.
 160   for (MachineOperand &DefMO : Def->explicit_uses()) {
 161     if (!DefMO.isReg())
 162       continue;
 163     return FindStartOfTree(DefMO, MRI, MFI);
 164   }
 165
 166   // If there were no stackified uses, we've reached the start.
 167   return Def;
 168 }
 169
 170 bool WebAssemblyExplicitLocals::runOnMachineFunction(MachineFunction &MF) {
 171   DEBUG(dbgs() << "********** Make Locals Explicit **********\n"
 172                   "********** Function: "
 173                << MF.getName() << '\n');
 174
 175   // Disable this pass if directed to do so.
 176   if (DisableWebAssemblyExplicitLocals)
 177     return false;
 178
 179   // Disable this pass if we aren't doing direct wasm object emission.
 180   if (MF.getSubtarget<WebAssemblySubtarget>()
 181         .getTargetTriple().isOSBinFormatELF())
 182     return false;
 183
 184   bool Changed = false;
 185   MachineRegisterInfo &MRI = MF.getRegInfo();
 186   WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
 187   const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
 188
 189   // Map non-stackified virtual registers to their local ids.
 190   DenseMap<unsigned, unsigned> Reg2Local;
 191
 192   // Handle ARGUMENTS first to ensure that they get the designated numbers.
 193   for (MachineBasicBlock::iterator I = MF.begin()->begin(),
 194                                    E = MF.begin()->end();
 195        I != E;) {
 196     MachineInstr &MI = *I++;
 197     if (!WebAssembly::isArgument(MI))
 198       break;
 199     unsigned Reg = MI.getOperand(0).getReg();
 200     assert(!MFI.isVRegStackified(Reg));
 201     Reg2Local[Reg] = MI.getOperand(1).getImm();
 202     MI.eraseFromParent();
 203     Changed = true;
 204   }
 205
 206   // Start assigning local numbers after the last parameter.
 207   unsigned CurLocal = MFI.getParams().size();
 208
 209   // Precompute the set of registers that are unused, so that we can insert
 210   // drops to their defs.
 211   BitVector UseEmpty(MRI.getNumVirtRegs());
 212   for (unsigned i = 0, e = MRI.getNumVirtRegs(); i < e; ++i)
 213     UseEmpty[i] = MRI.use_empty(TargetRegisterInfo::index2VirtReg(i));
 214
 215   // Visit each instruction in the function.
 216   for (MachineBasicBlock &MBB : MF) {
 217     for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
 218       MachineInstr &MI = *I++;
 219       assert(!WebAssembly::isArgument(MI));
 220
 221       if (MI.isDebugValue() || MI.isLabel())
 222         continue;
 223
 224       // Replace tee instructions with tee_local. The difference is that tee
 225       // instructins have two defs, while tee_local instructions have one def
 226       // and an index of a local to write to.
 227       if (WebAssembly::isTee(MI)) {
 228         assert(MFI.isVRegStackified(MI.getOperand(0).getReg()));
 229         assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
 230         unsigned OldReg = MI.getOperand(2).getReg();
 231         const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
 232
 233         // Stackify the input if it isn't stackified yet.
 234         if (!MFI.isVRegStackified(OldReg)) {
 235           unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
 236           unsigned NewReg = MRI.createVirtualRegister(RC);
 237           unsigned Opc = getGetLocalOpcode(RC);
 238           BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), NewReg)
 239               .addImm(LocalId);
 240           MI.getOperand(2).setReg(NewReg);
 241           MFI.stackifyVReg(NewReg);
 242         }
 243
 244         // Replace the TEE with a TEE_LOCAL.
 245         unsigned LocalId =
 246             getLocalId(Reg2Local, CurLocal, MI.getOperand(1).getReg());
 247         unsigned Opc = getTeeLocalOpcode(RC);
 248         BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc),
 249                 MI.getOperand(0).getReg())
 250             .addImm(LocalId)
 251             .addReg(MI.getOperand(2).getReg());
 252
 253         MI.eraseFromParent();
 254         Changed = true;
 255         continue;
 256       }
 257
 258       // Insert set_locals for any defs that aren't stackified yet. Currently
 259       // we handle at most one def.
 260       assert(MI.getDesc().getNumDefs() <= 1);
 261       if (MI.getDesc().getNumDefs() == 1) {
 262         unsigned OldReg = MI.getOperand(0).getReg();
 263         if (!MFI.isVRegStackified(OldReg)) {
 264           const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
 265           unsigned NewReg = MRI.createVirtualRegister(RC);
 266           auto InsertPt = std::next(MachineBasicBlock::iterator(&MI));
 267           if (MI.getOpcode() == WebAssembly::IMPLICIT_DEF) {
 268             MI.eraseFromParent();
 269             Changed = true;
 270             continue;
 271           }
 272           if (UseEmpty[TargetRegisterInfo::virtReg2Index(OldReg)]) {
 273             unsigned Opc = getDropOpcode(RC);
 274             BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
 275                 .addReg(NewReg);
 276           } else {
 277             unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
 278             unsigned Opc = getSetLocalOpcode(RC);
 279             BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
 280                 .addImm(LocalId)
 281                 .addReg(NewReg);
 282           }
 283           MI.getOperand(0).setReg(NewReg);
 284           MFI.stackifyVReg(NewReg);
 285           Changed = true;
 286         }
 287       }
 288
 289       // Insert get_locals for any uses that aren't stackified yet.
 290       MachineInstr *InsertPt = &MI;
 291       for (MachineOperand &MO : reverse(MI.explicit_uses())) {
 292         if (!MO.isReg())
 293           continue;
 294
 295         unsigned OldReg = MO.getReg();
 296
 297         // Inline asm may have a def in the middle of the operands. Our contract
 298         // with inline asm register operands is to provide local indices as
 299         // immediates.
 300         if (MO.isDef()) {
 301           assert(MI.getOpcode() == TargetOpcode::INLINEASM);
 302           unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
 303           MRI.removeRegOperandFromUseList(&MO);
 304           MO = MachineOperand::CreateImm(LocalId);
 305           continue;
 306         }
 307
 308         // If we see a stackified register, prepare to insert subsequent
 309         // get_locals before the start of its tree.
 310         if (MFI.isVRegStackified(OldReg)) {
 311           InsertPt = FindStartOfTree(MO, MRI, MFI);
 312           continue;
 313         }
 314
 315         // Our contract with inline asm register operands is to provide local
 316         // indices as immediates.
 317         if (MI.getOpcode() == TargetOpcode::INLINEASM) {
 318           unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
 319           MRI.removeRegOperandFromUseList(&MO);
 320           MO = MachineOperand::CreateImm(LocalId);
 321           continue;
 322         }
 323
 324         // Insert a get_local.
 325         unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
 326         const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
 327         unsigned NewReg = MRI.createVirtualRegister(RC);
 328         unsigned Opc = getGetLocalOpcode(RC);
 329         InsertPt =
 330             BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc), NewReg)
 331                 .addImm(LocalId);
 332         MO.setReg(NewReg);
 333         MFI.stackifyVReg(NewReg);
 334         Changed = true;
 335       }
 336
 337       // Coalesce and eliminate COPY instructions.
 338       if (WebAssembly::isCopy(MI)) {
 339         MRI.replaceRegWith(MI.getOperand(1).getReg(),
 340                            MI.getOperand(0).getReg());
 341         MI.eraseFromParent();
 342         Changed = true;
 343       }
 344     }
 345   }
 346
 347   // Define the locals.
 348   // TODO: Sort the locals for better compression.
 349   MFI.setNumLocals(CurLocal - MFI.getParams().size());
 350   for (size_t i = 0, e = MRI.getNumVirtRegs(); i < e; ++i) {
 351     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
 352     auto I = Reg2Local.find(Reg);
 353     if (I == Reg2Local.end() || I->second < MFI.getParams().size())
 354       continue;
 355
 356     MFI.setLocal(I->second - MFI.getParams().size(),
 357                  typeForRegClass(MRI.getRegClass(Reg)));
 358     Changed = true;
 359   }
 360
 361 #ifndef NDEBUG
 362   // Assert that all registers have been stackified at this point.
 363   for (const MachineBasicBlock &MBB : MF) {
 364     for (const MachineInstr &MI : MBB) {
 365       if (MI.isDebugValue() || MI.isLabel())
 366         continue;
 367       for (const MachineOperand &MO : MI.explicit_operands()) {
 368         assert(
 369             (!MO.isReg() || MRI.use_empty(MO.getReg()) ||
 370              MFI.isVRegStackified(MO.getReg())) &&
 371             "WebAssemblyExplicitLocals failed to stackify a register operand");
 372       }
 373     }
 374   }
 375 #endif
 376
 377   return Changed;
 378 }