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