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 } 393