1 //- WebAssemblyISelDAGToDAG.cpp - A dag to dag inst selector for WebAssembly -// 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 defines an instruction selector for the WebAssembly target. 11 /// 12 //===----------------------------------------------------------------------===// 13 14 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h" 15 #include "WebAssembly.h" 16 #include "WebAssemblyISelLowering.h" 17 #include "WebAssemblyTargetMachine.h" 18 #include "llvm/CodeGen/MachineFrameInfo.h" 19 #include "llvm/CodeGen/SelectionDAGISel.h" 20 #include "llvm/CodeGen/WasmEHFuncInfo.h" 21 #include "llvm/IR/DiagnosticInfo.h" 22 #include "llvm/IR/Function.h" // To access function attributes. 23 #include "llvm/IR/IntrinsicsWebAssembly.h" 24 #include "llvm/Support/Debug.h" 25 #include "llvm/Support/KnownBits.h" 26 #include "llvm/Support/raw_ostream.h" 27 28 using namespace llvm; 29 30 #define DEBUG_TYPE "wasm-isel" 31 #define PASS_NAME "WebAssembly Instruction Selection" 32 33 //===--------------------------------------------------------------------===// 34 /// WebAssembly-specific code to select WebAssembly machine instructions for 35 /// SelectionDAG operations. 36 /// 37 namespace { 38 class WebAssemblyDAGToDAGISel final : public SelectionDAGISel { 39 /// Keep a pointer to the WebAssemblySubtarget around so that we can make the 40 /// right decision when generating code for different targets. 41 const WebAssemblySubtarget *Subtarget; 42 43 public: 44 WebAssemblyDAGToDAGISel() = delete; 45 46 WebAssemblyDAGToDAGISel(WebAssemblyTargetMachine &TM, 47 CodeGenOptLevel OptLevel) 48 : SelectionDAGISel(TM, OptLevel), Subtarget(nullptr) {} 49 50 bool runOnMachineFunction(MachineFunction &MF) override { 51 LLVM_DEBUG(dbgs() << "********** ISelDAGToDAG **********\n" 52 "********** Function: " 53 << MF.getName() << '\n'); 54 55 Subtarget = &MF.getSubtarget<WebAssemblySubtarget>(); 56 57 return SelectionDAGISel::runOnMachineFunction(MF); 58 } 59 60 void PreprocessISelDAG() override; 61 62 void Select(SDNode *Node) override; 63 64 bool SelectInlineAsmMemoryOperand(const SDValue &Op, 65 InlineAsm::ConstraintCode ConstraintID, 66 std::vector<SDValue> &OutOps) override; 67 68 bool SelectAddrOperands32(SDValue Op, SDValue &Offset, SDValue &Addr); 69 bool SelectAddrOperands64(SDValue Op, SDValue &Offset, SDValue &Addr); 70 71 // Include the pieces autogenerated from the target description. 72 #include "WebAssemblyGenDAGISel.inc" 73 74 private: 75 // add select functions here... 76 77 bool SelectAddrOperands(MVT AddrType, unsigned ConstOpc, SDValue Op, 78 SDValue &Offset, SDValue &Addr); 79 bool SelectAddrAddOperands(MVT OffsetType, SDValue N, SDValue &Offset, 80 SDValue &Addr); 81 }; 82 83 class WebAssemblyDAGToDAGISelLegacy : public SelectionDAGISelLegacy { 84 public: 85 static char ID; 86 explicit WebAssemblyDAGToDAGISelLegacy(WebAssemblyTargetMachine &TM, 87 CodeGenOptLevel OptLevel) 88 : SelectionDAGISelLegacy( 89 ID, std::make_unique<WebAssemblyDAGToDAGISel>(TM, OptLevel)) {} 90 }; 91 } // end anonymous namespace 92 93 char WebAssemblyDAGToDAGISelLegacy::ID; 94 95 INITIALIZE_PASS(WebAssemblyDAGToDAGISelLegacy, DEBUG_TYPE, PASS_NAME, false, 96 false) 97 98 void WebAssemblyDAGToDAGISel::PreprocessISelDAG() { 99 // Stack objects that should be allocated to locals are hoisted to WebAssembly 100 // locals when they are first used. However for those without uses, we hoist 101 // them here. It would be nice if there were some hook to do this when they 102 // are added to the MachineFrameInfo, but that's not the case right now. 103 MachineFrameInfo &FrameInfo = MF->getFrameInfo(); 104 for (int Idx = 0; Idx < FrameInfo.getObjectIndexEnd(); Idx++) 105 WebAssemblyFrameLowering::getLocalForStackObject(*MF, Idx); 106 107 SelectionDAGISel::PreprocessISelDAG(); 108 } 109 110 static SDValue getTagSymNode(int Tag, SelectionDAG *DAG) { 111 assert(Tag == WebAssembly::CPP_EXCEPTION || WebAssembly::C_LONGJMP); 112 auto &MF = DAG->getMachineFunction(); 113 const auto &TLI = DAG->getTargetLoweringInfo(); 114 MVT PtrVT = TLI.getPointerTy(DAG->getDataLayout()); 115 const char *SymName = Tag == WebAssembly::CPP_EXCEPTION 116 ? MF.createExternalSymbolName("__cpp_exception") 117 : MF.createExternalSymbolName("__c_longjmp"); 118 return DAG->getTargetExternalSymbol(SymName, PtrVT); 119 } 120 121 void WebAssemblyDAGToDAGISel::Select(SDNode *Node) { 122 // If we have a custom node, we already have selected! 123 if (Node->isMachineOpcode()) { 124 LLVM_DEBUG(errs() << "== "; Node->dump(CurDAG); errs() << "\n"); 125 Node->setNodeId(-1); 126 return; 127 } 128 129 MVT PtrVT = TLI->getPointerTy(CurDAG->getDataLayout()); 130 auto GlobalGetIns = PtrVT == MVT::i64 ? WebAssembly::GLOBAL_GET_I64 131 : WebAssembly::GLOBAL_GET_I32; 132 133 // Few custom selection stuff. 134 SDLoc DL(Node); 135 MachineFunction &MF = CurDAG->getMachineFunction(); 136 switch (Node->getOpcode()) { 137 case ISD::ATOMIC_FENCE: { 138 if (!MF.getSubtarget<WebAssemblySubtarget>().hasAtomics()) 139 break; 140 141 uint64_t SyncScopeID = Node->getConstantOperandVal(2); 142 MachineSDNode *Fence = nullptr; 143 switch (SyncScopeID) { 144 case SyncScope::SingleThread: 145 // We lower a single-thread fence to a pseudo compiler barrier instruction 146 // preventing instruction reordering. This will not be emitted in final 147 // binary. 148 Fence = CurDAG->getMachineNode(WebAssembly::COMPILER_FENCE, 149 DL, // debug loc 150 MVT::Other, // outchain type 151 Node->getOperand(0) // inchain 152 ); 153 break; 154 case SyncScope::System: 155 // Currently wasm only supports sequentially consistent atomics, so we 156 // always set the order to 0 (sequentially consistent). 157 Fence = CurDAG->getMachineNode( 158 WebAssembly::ATOMIC_FENCE, 159 DL, // debug loc 160 MVT::Other, // outchain type 161 CurDAG->getTargetConstant(0, DL, MVT::i32), // order 162 Node->getOperand(0) // inchain 163 ); 164 break; 165 default: 166 llvm_unreachable("Unknown scope!"); 167 } 168 169 ReplaceNode(Node, Fence); 170 CurDAG->RemoveDeadNode(Node); 171 return; 172 } 173 174 case ISD::INTRINSIC_WO_CHAIN: { 175 unsigned IntNo = Node->getConstantOperandVal(0); 176 switch (IntNo) { 177 case Intrinsic::wasm_tls_size: { 178 MachineSDNode *TLSSize = CurDAG->getMachineNode( 179 GlobalGetIns, DL, PtrVT, 180 CurDAG->getTargetExternalSymbol("__tls_size", PtrVT)); 181 ReplaceNode(Node, TLSSize); 182 return; 183 } 184 185 case Intrinsic::wasm_tls_align: { 186 MachineSDNode *TLSAlign = CurDAG->getMachineNode( 187 GlobalGetIns, DL, PtrVT, 188 CurDAG->getTargetExternalSymbol("__tls_align", PtrVT)); 189 ReplaceNode(Node, TLSAlign); 190 return; 191 } 192 } 193 break; 194 } 195 196 case ISD::INTRINSIC_W_CHAIN: { 197 unsigned IntNo = Node->getConstantOperandVal(1); 198 const auto &TLI = CurDAG->getTargetLoweringInfo(); 199 MVT PtrVT = TLI.getPointerTy(CurDAG->getDataLayout()); 200 switch (IntNo) { 201 case Intrinsic::wasm_tls_base: { 202 MachineSDNode *TLSBase = CurDAG->getMachineNode( 203 GlobalGetIns, DL, PtrVT, MVT::Other, 204 CurDAG->getTargetExternalSymbol("__tls_base", PtrVT), 205 Node->getOperand(0)); 206 ReplaceNode(Node, TLSBase); 207 return; 208 } 209 210 case Intrinsic::wasm_catch: { 211 int Tag = Node->getConstantOperandVal(2); 212 SDValue SymNode = getTagSymNode(Tag, CurDAG); 213 unsigned CatchOpcode = WebAssembly::WasmUseLegacyEH 214 ? WebAssembly::CATCH_LEGACY 215 : WebAssembly::CATCH; 216 MachineSDNode *Catch = 217 CurDAG->getMachineNode(CatchOpcode, DL, 218 { 219 PtrVT, // exception pointer 220 MVT::Other // outchain type 221 }, 222 { 223 SymNode, // exception symbol 224 Node->getOperand(0) // inchain 225 }); 226 ReplaceNode(Node, Catch); 227 return; 228 } 229 } 230 break; 231 } 232 233 case ISD::INTRINSIC_VOID: { 234 unsigned IntNo = Node->getConstantOperandVal(1); 235 switch (IntNo) { 236 case Intrinsic::wasm_throw: { 237 int Tag = Node->getConstantOperandVal(2); 238 SDValue SymNode = getTagSymNode(Tag, CurDAG); 239 MachineSDNode *Throw = 240 CurDAG->getMachineNode(WebAssembly::THROW, DL, 241 MVT::Other, // outchain type 242 { 243 SymNode, // exception symbol 244 Node->getOperand(3), // thrown value 245 Node->getOperand(0) // inchain 246 }); 247 ReplaceNode(Node, Throw); 248 return; 249 } 250 case Intrinsic::wasm_rethrow: { 251 // RETHROW's BB argument will be populated in LateEHPrepare. Just use a 252 // '0' as a placeholder for now. 253 MachineSDNode *Rethrow = CurDAG->getMachineNode( 254 WebAssembly::RETHROW, DL, 255 MVT::Other, // outchain type 256 { 257 CurDAG->getConstant(0, DL, MVT::i32), // placeholder 258 Node->getOperand(0) // inchain 259 }); 260 ReplaceNode(Node, Rethrow); 261 return; 262 } 263 } 264 break; 265 } 266 267 case WebAssemblyISD::CALL: 268 case WebAssemblyISD::RET_CALL: { 269 // CALL has both variable operands and variable results, but ISel only 270 // supports one or the other. Split calls into two nodes glued together, one 271 // for the operands and one for the results. These two nodes will be 272 // recombined in a custom inserter hook into a single MachineInstr. 273 SmallVector<SDValue, 16> Ops; 274 for (size_t i = 1; i < Node->getNumOperands(); ++i) { 275 SDValue Op = Node->getOperand(i); 276 // Remove the wrapper when the call target is a function, an external 277 // symbol (which will be lowered to a library function), or an alias of 278 // a function. If the target is not a function/external symbol, we 279 // shouldn't remove the wrapper, because we cannot call it directly and 280 // instead we want it to be loaded with a CONST instruction and called 281 // with a call_indirect later. 282 if (i == 1 && Op->getOpcode() == WebAssemblyISD::Wrapper) { 283 SDValue NewOp = Op->getOperand(0); 284 if (auto *GlobalOp = dyn_cast<GlobalAddressSDNode>(NewOp.getNode())) { 285 if (isa<Function>( 286 GlobalOp->getGlobal()->stripPointerCastsAndAliases())) 287 Op = NewOp; 288 } else if (isa<ExternalSymbolSDNode>(NewOp.getNode())) { 289 Op = NewOp; 290 } 291 } 292 Ops.push_back(Op); 293 } 294 295 // Add the chain last 296 Ops.push_back(Node->getOperand(0)); 297 MachineSDNode *CallParams = 298 CurDAG->getMachineNode(WebAssembly::CALL_PARAMS, DL, MVT::Glue, Ops); 299 300 unsigned Results = Node->getOpcode() == WebAssemblyISD::CALL 301 ? WebAssembly::CALL_RESULTS 302 : WebAssembly::RET_CALL_RESULTS; 303 304 SDValue Link(CallParams, 0); 305 MachineSDNode *CallResults = 306 CurDAG->getMachineNode(Results, DL, Node->getVTList(), Link); 307 ReplaceNode(Node, CallResults); 308 return; 309 } 310 311 default: 312 break; 313 } 314 315 // Select the default instruction. 316 SelectCode(Node); 317 } 318 319 bool WebAssemblyDAGToDAGISel::SelectInlineAsmMemoryOperand( 320 const SDValue &Op, InlineAsm::ConstraintCode ConstraintID, 321 std::vector<SDValue> &OutOps) { 322 switch (ConstraintID) { 323 case InlineAsm::ConstraintCode::m: 324 // We just support simple memory operands that just have a single address 325 // operand and need no special handling. 326 OutOps.push_back(Op); 327 return false; 328 default: 329 break; 330 } 331 332 return true; 333 } 334 335 bool WebAssemblyDAGToDAGISel::SelectAddrAddOperands(MVT OffsetType, SDValue N, 336 SDValue &Offset, 337 SDValue &Addr) { 338 assert(N.getNumOperands() == 2 && "Attempting to fold in a non-binary op"); 339 340 // WebAssembly constant offsets are performed as unsigned with infinite 341 // precision, so we need to check for NoUnsignedWrap so that we don't fold an 342 // offset for an add that needs wrapping. 343 if (N.getOpcode() == ISD::ADD && !N.getNode()->getFlags().hasNoUnsignedWrap()) 344 return false; 345 346 // Folds constants in an add into the offset. 347 for (size_t i = 0; i < 2; ++i) { 348 SDValue Op = N.getOperand(i); 349 SDValue OtherOp = N.getOperand(i == 0 ? 1 : 0); 350 351 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Op)) { 352 Offset = 353 CurDAG->getTargetConstant(CN->getZExtValue(), SDLoc(N), OffsetType); 354 Addr = OtherOp; 355 return true; 356 } 357 } 358 return false; 359 } 360 361 bool WebAssemblyDAGToDAGISel::SelectAddrOperands(MVT AddrType, 362 unsigned ConstOpc, SDValue N, 363 SDValue &Offset, 364 SDValue &Addr) { 365 SDLoc DL(N); 366 367 // Fold target global addresses into the offset. 368 if (!TM.isPositionIndependent()) { 369 SDValue Op(N); 370 if (Op.getOpcode() == WebAssemblyISD::Wrapper) 371 Op = Op.getOperand(0); 372 373 if (Op.getOpcode() == ISD::TargetGlobalAddress) { 374 Offset = Op; 375 Addr = SDValue( 376 CurDAG->getMachineNode(ConstOpc, DL, AddrType, 377 CurDAG->getTargetConstant(0, DL, AddrType)), 378 0); 379 return true; 380 } 381 } 382 383 // Fold anything inside an add into the offset. 384 if (N.getOpcode() == ISD::ADD && 385 SelectAddrAddOperands(AddrType, N, Offset, Addr)) 386 return true; 387 388 // Likewise, treat an 'or' node as an 'add' if the or'ed bits are known to be 389 // zero and fold them into the offset too. 390 if (N.getOpcode() == ISD::OR) { 391 bool OrIsAdd; 392 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) { 393 OrIsAdd = 394 CurDAG->MaskedValueIsZero(N->getOperand(0), CN->getAPIntValue()); 395 } else { 396 KnownBits Known0 = CurDAG->computeKnownBits(N->getOperand(0), 0); 397 KnownBits Known1 = CurDAG->computeKnownBits(N->getOperand(1), 0); 398 OrIsAdd = (~Known0.Zero & ~Known1.Zero) == 0; 399 } 400 401 if (OrIsAdd && SelectAddrAddOperands(AddrType, N, Offset, Addr)) 402 return true; 403 } 404 405 // Fold constant addresses into the offset. 406 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) { 407 Offset = CurDAG->getTargetConstant(CN->getZExtValue(), DL, AddrType); 408 Addr = SDValue( 409 CurDAG->getMachineNode(ConstOpc, DL, AddrType, 410 CurDAG->getTargetConstant(0, DL, AddrType)), 411 0); 412 return true; 413 } 414 415 // Else it's a plain old load/store with no offset. 416 Offset = CurDAG->getTargetConstant(0, DL, AddrType); 417 Addr = N; 418 return true; 419 } 420 421 bool WebAssemblyDAGToDAGISel::SelectAddrOperands32(SDValue Op, SDValue &Offset, 422 SDValue &Addr) { 423 return SelectAddrOperands(MVT::i32, WebAssembly::CONST_I32, Op, Offset, Addr); 424 } 425 426 bool WebAssemblyDAGToDAGISel::SelectAddrOperands64(SDValue Op, SDValue &Offset, 427 SDValue &Addr) { 428 return SelectAddrOperands(MVT::i64, WebAssembly::CONST_I64, Op, Offset, Addr); 429 } 430 431 /// This pass converts a legalized DAG into a WebAssembly-specific DAG, ready 432 /// for instruction scheduling. 433 FunctionPass *llvm::createWebAssemblyISelDag(WebAssemblyTargetMachine &TM, 434 CodeGenOptLevel OptLevel) { 435 return new WebAssemblyDAGToDAGISelLegacy(TM, OptLevel); 436 } 437