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