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 
WebAssemblyDAGToDAGISel(WebAssemblyTargetMachine & TM,CodeGenOptLevel OptLevel)49   WebAssemblyDAGToDAGISel(WebAssemblyTargetMachine &TM,
50                           CodeGenOptLevel OptLevel)
51       : SelectionDAGISel(ID, TM, OptLevel), Subtarget(nullptr) {}
52 
runOnMachineFunction(MachineFunction & MF)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 
77 private:
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 
87 char WebAssemblyDAGToDAGISel::ID;
88 
INITIALIZE_PASS(WebAssemblyDAGToDAGISel,DEBUG_TYPE,PASS_NAME,false,false)89 INITIALIZE_PASS(WebAssemblyDAGToDAGISel, DEBUG_TYPE, PASS_NAME, false, false)
90 
91 void 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 
getTagSymNode(int Tag,SelectionDAG * DAG)103 static 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 
Select(SDNode * Node)114 void 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 
SelectInlineAsmMemoryOperand(const SDValue & Op,InlineAsm::ConstraintCode ConstraintID,std::vector<SDValue> & OutOps)296 bool 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 
SelectAddrAddOperands(MVT OffsetType,SDValue N,SDValue & Offset,SDValue & Addr)312 bool 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 
SelectAddrOperands(MVT AddrType,unsigned ConstOpc,SDValue N,SDValue & Offset,SDValue & Addr)338 bool 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 
SelectAddrOperands32(SDValue Op,SDValue & Offset,SDValue & Addr)398 bool WebAssemblyDAGToDAGISel::SelectAddrOperands32(SDValue Op, SDValue &Offset,
399                                                    SDValue &Addr) {
400   return SelectAddrOperands(MVT::i32, WebAssembly::CONST_I32, Op, Offset, Addr);
401 }
402 
SelectAddrOperands64(SDValue Op,SDValue & Offset,SDValue & Addr)403 bool 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.
createWebAssemblyISelDag(WebAssemblyTargetMachine & TM,CodeGenOptLevel OptLevel)410 FunctionPass *llvm::createWebAssemblyISelDag(WebAssemblyTargetMachine &TM,
411                                              CodeGenOptLevel OptLevel) {
412   return new WebAssemblyDAGToDAGISel(TM, OptLevel);
413 }
414