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