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