557 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8///9/// \file10/// 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 "WebAssemblyUtilities.h"19#include "llvm/CodeGen/MachineFrameInfo.h"20#include "llvm/CodeGen/SelectionDAGISel.h"21#include "llvm/CodeGen/WasmEHFuncInfo.h"22#include "llvm/IR/DiagnosticInfo.h"23#include "llvm/IR/Function.h" // To access function attributes.24#include "llvm/IR/IntrinsicsWebAssembly.h"25#include "llvm/MC/MCSymbolWasm.h"26#include "llvm/Support/Debug.h"27#include "llvm/Support/KnownBits.h"28#include "llvm/Support/raw_ostream.h"29 30using namespace llvm;31 32#define DEBUG_TYPE "wasm-isel"33#define PASS_NAME "WebAssembly Instruction Selection"34 35//===--------------------------------------------------------------------===//36/// WebAssembly-specific code to select WebAssembly machine instructions for37/// SelectionDAG operations.38///39namespace {40class WebAssemblyDAGToDAGISel final : public SelectionDAGISel {41 /// Keep a pointer to the WebAssemblySubtarget around so that we can make the42 /// right decision when generating code for different targets.43 const WebAssemblySubtarget *Subtarget;44 45public:46 WebAssemblyDAGToDAGISel() = delete;47 48 WebAssemblyDAGToDAGISel(WebAssemblyTargetMachine &TM,49 CodeGenOptLevel OptLevel)50 : SelectionDAGISel(TM, OptLevel), Subtarget(nullptr) {}51 52 bool runOnMachineFunction(MachineFunction &MF) override {53 LLVM_DEBUG(dbgs() << "********** ISelDAGToDAG **********\n"54 "********** Function: "55 << MF.getName() << '\n');56 57 Subtarget = &MF.getSubtarget<WebAssemblySubtarget>();58 59 return SelectionDAGISel::runOnMachineFunction(MF);60 }61 62 void PreprocessISelDAG() override;63 64 void Select(SDNode *Node) override;65 66 bool SelectInlineAsmMemoryOperand(const SDValue &Op,67 InlineAsm::ConstraintCode ConstraintID,68 std::vector<SDValue> &OutOps) override;69 70 bool SelectAddrOperands32(SDValue Op, SDValue &Offset, SDValue &Addr);71 bool SelectAddrOperands64(SDValue Op, SDValue &Offset, SDValue &Addr);72 73// Include the pieces autogenerated from the target description.74#include "WebAssemblyGenDAGISel.inc"75 76private:77 // add select functions here...78 79 bool SelectAddrOperands(MVT AddrType, unsigned ConstOpc, SDValue Op,80 SDValue &Offset, SDValue &Addr);81 bool SelectAddrAddOperands(MVT OffsetType, SDValue N, SDValue &Offset,82 SDValue &Addr);83};84 85class WebAssemblyDAGToDAGISelLegacy : public SelectionDAGISelLegacy {86public:87 static char ID;88 explicit WebAssemblyDAGToDAGISelLegacy(WebAssemblyTargetMachine &TM,89 CodeGenOptLevel OptLevel)90 : SelectionDAGISelLegacy(91 ID, std::make_unique<WebAssemblyDAGToDAGISel>(TM, OptLevel)) {}92};93} // end anonymous namespace94 95char WebAssemblyDAGToDAGISelLegacy::ID;96 97INITIALIZE_PASS(WebAssemblyDAGToDAGISelLegacy, DEBUG_TYPE, PASS_NAME, false,98 false)99 100void WebAssemblyDAGToDAGISel::PreprocessISelDAG() {101 // Stack objects that should be allocated to locals are hoisted to WebAssembly102 // locals when they are first used. However for those without uses, we hoist103 // them here. It would be nice if there were some hook to do this when they104 // are added to the MachineFrameInfo, but that's not the case right now.105 MachineFrameInfo &FrameInfo = MF->getFrameInfo();106 for (int Idx = 0; Idx < FrameInfo.getObjectIndexEnd(); Idx++)107 WebAssemblyFrameLowering::getLocalForStackObject(*MF, Idx);108 109 SelectionDAGISel::PreprocessISelDAG();110}111 112static SDValue getTagSymNode(int Tag, SelectionDAG *DAG) {113 assert(Tag == WebAssembly::CPP_EXCEPTION || Tag == WebAssembly::C_LONGJMP);114 auto &MF = DAG->getMachineFunction();115 const auto &TLI = DAG->getTargetLoweringInfo();116 MVT PtrVT = TLI.getPointerTy(DAG->getDataLayout());117 const char *SymName = Tag == WebAssembly::CPP_EXCEPTION118 ? MF.createExternalSymbolName("__cpp_exception")119 : MF.createExternalSymbolName("__c_longjmp");120 return DAG->getTargetExternalSymbol(SymName, PtrVT);121}122 123static APInt encodeFunctionSignature(SelectionDAG *DAG, SDLoc &DL,124 SmallVector<MVT, 4> &Returns,125 SmallVector<MVT, 4> &Params) {126 auto toWasmValType = [](MVT VT) {127 if (VT == MVT::i32) {128 return wasm::ValType::I32;129 }130 if (VT == MVT::i64) {131 return wasm::ValType::I64;132 }133 if (VT == MVT::f32) {134 return wasm::ValType::F32;135 }136 if (VT == MVT::f64) {137 return wasm::ValType::F64;138 }139 if (VT == MVT::externref) {140 return wasm::ValType::EXTERNREF;141 }142 if (VT == MVT::funcref) {143 return wasm::ValType::FUNCREF;144 }145 if (VT == MVT::exnref) {146 return wasm::ValType::EXNREF;147 }148 LLVM_DEBUG(errs() << "Unhandled type for llvm.wasm.ref.test.func: " << VT149 << "\n");150 llvm_unreachable("Unhandled type for llvm.wasm.ref.test.func");151 };152 auto NParams = Params.size();153 auto NReturns = Returns.size();154 auto BitWidth = (NParams + NReturns + 2) * 64;155 auto Sig = APInt(BitWidth, 0);156 157 // Annoying special case: if getSignificantBits() <= 64 then InstrEmitter will158 // emit an Imm instead of a CImm. It simplifies WebAssemblyMCInstLower if we159 // always emit a CImm. So xor NParams with 0x7ffffff to ensure160 // getSignificantBits() > 64161 Sig |= NReturns ^ 0x7ffffff;162 for (auto &Return : Returns) {163 auto V = toWasmValType(Return);164 Sig <<= 64;165 Sig |= (int64_t)V;166 }167 Sig <<= 64;168 Sig |= NParams;169 for (auto &Param : Params) {170 auto V = toWasmValType(Param);171 Sig <<= 64;172 Sig |= (int64_t)V;173 }174 return Sig;175}176 177void WebAssemblyDAGToDAGISel::Select(SDNode *Node) {178 // If we have a custom node, we already have selected!179 if (Node->isMachineOpcode()) {180 LLVM_DEBUG(errs() << "== "; Node->dump(CurDAG); errs() << "\n");181 Node->setNodeId(-1);182 return;183 }184 185 MVT PtrVT = TLI->getPointerTy(CurDAG->getDataLayout());186 auto GlobalGetIns = PtrVT == MVT::i64 ? WebAssembly::GLOBAL_GET_I64187 : WebAssembly::GLOBAL_GET_I32;188 189 // Few custom selection stuff.190 SDLoc DL(Node);191 MachineFunction &MF = CurDAG->getMachineFunction();192 switch (Node->getOpcode()) {193 case ISD::ATOMIC_FENCE: {194 if (!MF.getSubtarget<WebAssemblySubtarget>().hasAtomics())195 break;196 197 uint64_t SyncScopeID = Node->getConstantOperandVal(2);198 MachineSDNode *Fence = nullptr;199 switch (SyncScopeID) {200 case SyncScope::SingleThread:201 // We lower a single-thread fence to a pseudo compiler barrier instruction202 // preventing instruction reordering. This will not be emitted in final203 // binary.204 Fence = CurDAG->getMachineNode(WebAssembly::COMPILER_FENCE,205 DL, // debug loc206 MVT::Other, // outchain type207 Node->getOperand(0) // inchain208 );209 break;210 case SyncScope::System:211 // Currently wasm only supports sequentially consistent atomics, so we212 // always set the order to 0 (sequentially consistent).213 Fence = CurDAG->getMachineNode(214 WebAssembly::ATOMIC_FENCE,215 DL, // debug loc216 MVT::Other, // outchain type217 CurDAG->getTargetConstant(0, DL, MVT::i32), // order218 Node->getOperand(0) // inchain219 );220 break;221 default:222 llvm_unreachable("Unknown scope!");223 }224 225 ReplaceNode(Node, Fence);226 CurDAG->RemoveDeadNode(Node);227 return;228 }229 230 case ISD::INTRINSIC_WO_CHAIN: {231 unsigned IntNo = Node->getConstantOperandVal(0);232 switch (IntNo) {233 case Intrinsic::wasm_tls_size: {234 MachineSDNode *TLSSize = CurDAG->getMachineNode(235 GlobalGetIns, DL, PtrVT,236 CurDAG->getTargetExternalSymbol("__tls_size", PtrVT));237 ReplaceNode(Node, TLSSize);238 return;239 }240 241 case Intrinsic::wasm_tls_align: {242 MachineSDNode *TLSAlign = CurDAG->getMachineNode(243 GlobalGetIns, DL, PtrVT,244 CurDAG->getTargetExternalSymbol("__tls_align", PtrVT));245 ReplaceNode(Node, TLSAlign);246 return;247 }248 case Intrinsic::wasm_ref_test_func: {249 // First emit the TABLE_GET instruction to convert function pointer ==>250 // funcref251 MachineFunction &MF = CurDAG->getMachineFunction();252 auto PtrVT = MVT::getIntegerVT(MF.getDataLayout().getPointerSizeInBits());253 MCSymbol *Table = WebAssembly::getOrCreateFunctionTableSymbol(254 MF.getContext(), Subtarget);255 SDValue TableSym = CurDAG->getMCSymbol(Table, PtrVT);256 SDValue FuncPtr = Node->getOperand(1);257 if (Subtarget->hasAddr64() && FuncPtr.getValueType() == MVT::i64) {258 // table.get expects an i32 but on 64 bit platforms the function pointer259 // is an i64. In that case, i32.wrap_i64 to convert.260 FuncPtr = SDValue(CurDAG->getMachineNode(WebAssembly::I32_WRAP_I64, DL,261 MVT::i32, FuncPtr),262 0);263 }264 SDValue FuncRef =265 SDValue(CurDAG->getMachineNode(WebAssembly::TABLE_GET_FUNCREF, DL,266 MVT::funcref, TableSym, FuncPtr),267 0);268 269 // Encode the signature information into the type index placeholder.270 // This gets decoded and converted into the actual type signature in271 // WebAssemblyMCInstLower.cpp.272 SmallVector<MVT, 4> Params;273 SmallVector<MVT, 4> Returns;274 275 bool IsParam = false;276 // Operand 0 is the return register, Operand 1 is the function pointer.277 // The remaining operands encode the type of the function we are testing278 // for.279 for (unsigned I = 2, E = Node->getNumOperands(); I < E; ++I) {280 MVT VT = Node->getOperand(I).getValueType().getSimpleVT();281 if (VT == MVT::Untyped) {282 IsParam = true;283 continue;284 }285 if (IsParam) {286 Params.push_back(VT);287 } else {288 Returns.push_back(VT);289 }290 }291 auto Sig = encodeFunctionSignature(CurDAG, DL, Returns, Params);292 293 auto SigOp = CurDAG->getTargetConstant(294 Sig, DL, EVT::getIntegerVT(*CurDAG->getContext(), Sig.getBitWidth()));295 MachineSDNode *RefTestNode = CurDAG->getMachineNode(296 WebAssembly::REF_TEST_FUNCREF, DL, MVT::i32, {SigOp, FuncRef});297 ReplaceNode(Node, RefTestNode);298 return;299 }300 }301 break;302 }303 304 case ISD::INTRINSIC_W_CHAIN: {305 unsigned IntNo = Node->getConstantOperandVal(1);306 const auto &TLI = CurDAG->getTargetLoweringInfo();307 MVT PtrVT = TLI.getPointerTy(CurDAG->getDataLayout());308 switch (IntNo) {309 case Intrinsic::wasm_tls_base: {310 MachineSDNode *TLSBase = CurDAG->getMachineNode(311 GlobalGetIns, DL, PtrVT, MVT::Other,312 CurDAG->getTargetExternalSymbol("__tls_base", PtrVT),313 Node->getOperand(0));314 ReplaceNode(Node, TLSBase);315 return;316 }317 318 case Intrinsic::wasm_catch: {319 int Tag = Node->getConstantOperandVal(2);320 SDValue SymNode = getTagSymNode(Tag, CurDAG);321 unsigned CatchOpcode = WebAssembly::WasmUseLegacyEH322 ? WebAssembly::CATCH_LEGACY323 : WebAssembly::CATCH;324 MachineSDNode *Catch =325 CurDAG->getMachineNode(CatchOpcode, DL,326 {327 PtrVT, // exception pointer328 MVT::Other // outchain type329 },330 {331 SymNode, // exception symbol332 Node->getOperand(0) // inchain333 });334 ReplaceNode(Node, Catch);335 return;336 }337 }338 break;339 }340 341 case ISD::INTRINSIC_VOID: {342 unsigned IntNo = Node->getConstantOperandVal(1);343 switch (IntNo) {344 case Intrinsic::wasm_throw: {345 int Tag = Node->getConstantOperandVal(2);346 SDValue SymNode = getTagSymNode(Tag, CurDAG);347 MachineSDNode *Throw =348 CurDAG->getMachineNode(WebAssembly::THROW, DL,349 MVT::Other, // outchain type350 {351 SymNode, // exception symbol352 Node->getOperand(3), // thrown value353 Node->getOperand(0) // inchain354 });355 ReplaceNode(Node, Throw);356 return;357 }358 case Intrinsic::wasm_rethrow: {359 // RETHROW's BB argument will be populated in LateEHPrepare. Just use a360 // '0' as a placeholder for now.361 MachineSDNode *Rethrow = CurDAG->getMachineNode(362 WebAssembly::RETHROW, DL,363 MVT::Other, // outchain type364 {365 CurDAG->getConstant(0, DL, MVT::i32), // placeholder366 Node->getOperand(0) // inchain367 });368 ReplaceNode(Node, Rethrow);369 return;370 }371 }372 break;373 }374 375 case WebAssemblyISD::CALL:376 case WebAssemblyISD::RET_CALL: {377 // CALL has both variable operands and variable results, but ISel only378 // supports one or the other. Split calls into two nodes glued together, one379 // for the operands and one for the results. These two nodes will be380 // recombined in a custom inserter hook into a single MachineInstr.381 SmallVector<SDValue, 16> Ops;382 for (size_t i = 1; i < Node->getNumOperands(); ++i) {383 SDValue Op = Node->getOperand(i);384 // Remove the wrapper when the call target is a function, an external385 // symbol (which will be lowered to a library function), or an alias of386 // a function. If the target is not a function/external symbol, we387 // shouldn't remove the wrapper, because we cannot call it directly and388 // instead we want it to be loaded with a CONST instruction and called389 // with a call_indirect later.390 if (i == 1 && Op->getOpcode() == WebAssemblyISD::Wrapper) {391 SDValue NewOp = Op->getOperand(0);392 if (auto *GlobalOp = dyn_cast<GlobalAddressSDNode>(NewOp.getNode())) {393 if (isa<Function>(394 GlobalOp->getGlobal()->stripPointerCastsAndAliases()))395 Op = NewOp;396 } else if (isa<ExternalSymbolSDNode>(NewOp.getNode())) {397 Op = NewOp;398 }399 }400 Ops.push_back(Op);401 }402 403 // Add the chain last404 Ops.push_back(Node->getOperand(0));405 MachineSDNode *CallParams =406 CurDAG->getMachineNode(WebAssembly::CALL_PARAMS, DL, MVT::Glue, Ops);407 408 unsigned Results = Node->getOpcode() == WebAssemblyISD::CALL409 ? WebAssembly::CALL_RESULTS410 : WebAssembly::RET_CALL_RESULTS;411 412 SDValue Link(CallParams, 0);413 MachineSDNode *CallResults =414 CurDAG->getMachineNode(Results, DL, Node->getVTList(), Link);415 ReplaceNode(Node, CallResults);416 return;417 }418 419 default:420 break;421 }422 423 // Select the default instruction.424 SelectCode(Node);425}426 427bool WebAssemblyDAGToDAGISel::SelectInlineAsmMemoryOperand(428 const SDValue &Op, InlineAsm::ConstraintCode ConstraintID,429 std::vector<SDValue> &OutOps) {430 switch (ConstraintID) {431 case InlineAsm::ConstraintCode::m:432 // We just support simple memory operands that just have a single address433 // operand and need no special handling.434 OutOps.push_back(Op);435 return false;436 default:437 break;438 }439 440 return true;441}442 443bool WebAssemblyDAGToDAGISel::SelectAddrAddOperands(MVT OffsetType, SDValue N,444 SDValue &Offset,445 SDValue &Addr) {446 assert(N.getNumOperands() == 2 && "Attempting to fold in a non-binary op");447 448 // WebAssembly constant offsets are performed as unsigned with infinite449 // precision, so we need to check for NoUnsignedWrap so that we don't fold an450 // offset for an add that needs wrapping.451 if (N.getOpcode() == ISD::ADD && !N.getNode()->getFlags().hasNoUnsignedWrap())452 return false;453 454 for (size_t i = 0; i < 2; ++i) {455 SDValue Op = N.getOperand(i);456 SDValue OtherOp = N.getOperand(i == 0 ? 1 : 0);457 458 // Folds constants in an add into the offset.459 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Op)) {460 Offset =461 CurDAG->getTargetConstant(CN->getZExtValue(), SDLoc(N), OffsetType);462 Addr = OtherOp;463 return true;464 }465 466 // Fold target global addresses into the offset.467 if (!TM.isPositionIndependent()) {468 if (Op.getOpcode() == WebAssemblyISD::Wrapper)469 Op = Op.getOperand(0);470 471 if (Op.getOpcode() == ISD::TargetGlobalAddress) {472 Addr = OtherOp;473 Offset = Op;474 return true;475 }476 }477 }478 return false;479}480 481bool WebAssemblyDAGToDAGISel::SelectAddrOperands(MVT AddrType,482 unsigned ConstOpc, SDValue N,483 SDValue &Offset,484 SDValue &Addr) {485 SDLoc DL(N);486 487 // Fold target global addresses into the offset.488 if (!TM.isPositionIndependent()) {489 SDValue Op(N);490 if (Op.getOpcode() == WebAssemblyISD::Wrapper)491 Op = Op.getOperand(0);492 493 if (Op.getOpcode() == ISD::TargetGlobalAddress) {494 Offset = Op;495 Addr = SDValue(496 CurDAG->getMachineNode(ConstOpc, DL, AddrType,497 CurDAG->getTargetConstant(0, DL, AddrType)),498 0);499 return true;500 }501 }502 503 // Fold anything inside an add into the offset.504 if (N.getOpcode() == ISD::ADD &&505 SelectAddrAddOperands(AddrType, N, Offset, Addr))506 return true;507 508 // Likewise, treat an 'or' node as an 'add' if the or'ed bits are known to be509 // zero and fold them into the offset too.510 if (N.getOpcode() == ISD::OR) {511 bool OrIsAdd;512 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {513 OrIsAdd =514 CurDAG->MaskedValueIsZero(N->getOperand(0), CN->getAPIntValue());515 } else {516 KnownBits Known0 = CurDAG->computeKnownBits(N->getOperand(0), 0);517 KnownBits Known1 = CurDAG->computeKnownBits(N->getOperand(1), 0);518 OrIsAdd = (~Known0.Zero & ~Known1.Zero) == 0;519 }520 521 if (OrIsAdd && SelectAddrAddOperands(AddrType, N, Offset, Addr))522 return true;523 }524 525 // Fold constant addresses into the offset.526 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) {527 Offset = CurDAG->getTargetConstant(CN->getZExtValue(), DL, AddrType);528 Addr = SDValue(529 CurDAG->getMachineNode(ConstOpc, DL, AddrType,530 CurDAG->getTargetConstant(0, DL, AddrType)),531 0);532 return true;533 }534 535 // Else it's a plain old load/store with no offset.536 Offset = CurDAG->getTargetConstant(0, DL, AddrType);537 Addr = N;538 return true;539}540 541bool WebAssemblyDAGToDAGISel::SelectAddrOperands32(SDValue Op, SDValue &Offset,542 SDValue &Addr) {543 return SelectAddrOperands(MVT::i32, WebAssembly::CONST_I32, Op, Offset, Addr);544}545 546bool WebAssemblyDAGToDAGISel::SelectAddrOperands64(SDValue Op, SDValue &Offset,547 SDValue &Addr) {548 return SelectAddrOperands(MVT::i64, WebAssembly::CONST_I64, Op, Offset, Addr);549}550 551/// This pass converts a legalized DAG into a WebAssembly-specific DAG, ready552/// for instruction scheduling.553FunctionPass *llvm::createWebAssemblyISelDag(WebAssemblyTargetMachine &TM,554 CodeGenOptLevel OptLevel) {555 return new WebAssemblyDAGToDAGISelLegacy(TM, OptLevel);556}557