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