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 WebAssemblyDAGToDAGISel() = delete;
46
47 WebAssemblyDAGToDAGISel(WebAssemblyTargetMachine &TM,
48 CodeGenOptLevel OptLevel)
49 : SelectionDAGISel(TM, OptLevel), Subtarget(nullptr) {}
50
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&: 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
75private:
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
84class WebAssemblyDAGToDAGISelLegacy : public SelectionDAGISelLegacy {
85public:
86 static char ID;
87 explicit WebAssemblyDAGToDAGISelLegacy(WebAssemblyTargetMachine &TM,
88 CodeGenOptLevel OptLevel)
89 : SelectionDAGISelLegacy(
90 ID, std::make_unique<WebAssemblyDAGToDAGISel>(args&: TM, args&: OptLevel)) {}
91};
92} // end anonymous namespace
93
94char WebAssemblyDAGToDAGISelLegacy::ID;
95
96INITIALIZE_PASS(WebAssemblyDAGToDAGISelLegacy, DEBUG_TYPE, PASS_NAME, false,
97 false)
98
99void 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&: *MF, FrameIndex: Idx);
107
108 SelectionDAGISel::PreprocessISelDAG();
109}
110
111static 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(DL: DAG->getDataLayout());
116 const char *SymName = Tag == WebAssembly::CPP_EXCEPTION
117 ? MF.createExternalSymbolName(Name: "__cpp_exception")
118 : MF.createExternalSymbolName(Name: "__c_longjmp");
119 return DAG->getTargetExternalSymbol(Sym: SymName, VT: PtrVT);
120}
121
122void 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(DL: 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(Num: 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(Opcode: WebAssembly::COMPILER_FENCE,
150 dl: DL, // debug loc
151 VT: MVT::Other, // outchain type
152 Op1: Node->getOperand(Num: 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 Opcode: WebAssembly::ATOMIC_FENCE,
160 dl: DL, // debug loc
161 VT: MVT::Other, // outchain type
162 Op1: CurDAG->getTargetConstant(Val: 0, DL, VT: MVT::i32), // order
163 Op2: Node->getOperand(Num: 0) // inchain
164 );
165 break;
166 default:
167 llvm_unreachable("Unknown scope!");
168 }
169
170 ReplaceNode(F: Node, T: Fence);
171 CurDAG->RemoveDeadNode(N: Node);
172 return;
173 }
174
175 case ISD::INTRINSIC_WO_CHAIN: {
176 unsigned IntNo = Node->getConstantOperandVal(Num: 0);
177 switch (IntNo) {
178 case Intrinsic::wasm_tls_size: {
179 MachineSDNode *TLSSize = CurDAG->getMachineNode(
180 Opcode: GlobalGetIns, dl: DL, VT: PtrVT,
181 Op1: CurDAG->getTargetExternalSymbol(Sym: "__tls_size", VT: PtrVT));
182 ReplaceNode(F: Node, T: TLSSize);
183 return;
184 }
185
186 case Intrinsic::wasm_tls_align: {
187 MachineSDNode *TLSAlign = CurDAG->getMachineNode(
188 Opcode: GlobalGetIns, dl: DL, VT: PtrVT,
189 Op1: CurDAG->getTargetExternalSymbol(Sym: "__tls_align", VT: PtrVT));
190 ReplaceNode(F: Node, T: TLSAlign);
191 return;
192 }
193 }
194 break;
195 }
196
197 case ISD::INTRINSIC_W_CHAIN: {
198 unsigned IntNo = Node->getConstantOperandVal(Num: 1);
199 const auto &TLI = CurDAG->getTargetLoweringInfo();
200 MVT PtrVT = TLI.getPointerTy(DL: CurDAG->getDataLayout());
201 switch (IntNo) {
202 case Intrinsic::wasm_tls_base: {
203 MachineSDNode *TLSBase = CurDAG->getMachineNode(
204 Opcode: GlobalGetIns, dl: DL, VT1: PtrVT, VT2: MVT::Other,
205 Op1: CurDAG->getTargetExternalSymbol(Sym: "__tls_base", VT: PtrVT),
206 Op2: Node->getOperand(Num: 0));
207 ReplaceNode(F: Node, T: TLSBase);
208 return;
209 }
210
211 case Intrinsic::wasm_catch: {
212 int Tag = Node->getConstantOperandVal(Num: 2);
213 SDValue SymNode = getTagSymNode(Tag, DAG: CurDAG);
214 MachineSDNode *Catch =
215 CurDAG->getMachineNode(Opcode: WebAssembly::CATCH, dl: DL,
216 ResultTys: {
217 PtrVT, // exception pointer
218 MVT::Other // outchain type
219 },
220 Ops: {
221 SymNode, // exception symbol
222 Node->getOperand(Num: 0) // inchain
223 });
224 ReplaceNode(F: Node, T: Catch);
225 return;
226 }
227 }
228 break;
229 }
230
231 case ISD::INTRINSIC_VOID: {
232 unsigned IntNo = Node->getConstantOperandVal(Num: 1);
233 switch (IntNo) {
234 case Intrinsic::wasm_throw: {
235 int Tag = Node->getConstantOperandVal(Num: 2);
236 SDValue SymNode = getTagSymNode(Tag, DAG: CurDAG);
237 MachineSDNode *Throw =
238 CurDAG->getMachineNode(Opcode: WebAssembly::THROW, dl: DL,
239 VT: MVT::Other, // outchain type
240 Ops: {
241 SymNode, // exception symbol
242 Node->getOperand(Num: 3), // thrown value
243 Node->getOperand(Num: 0) // inchain
244 });
245 ReplaceNode(F: Node, T: Throw);
246 return;
247 }
248 }
249 break;
250 }
251
252 case WebAssemblyISD::CALL:
253 case WebAssemblyISD::RET_CALL: {
254 // CALL has both variable operands and variable results, but ISel only
255 // supports one or the other. Split calls into two nodes glued together, one
256 // for the operands and one for the results. These two nodes will be
257 // recombined in a custom inserter hook into a single MachineInstr.
258 SmallVector<SDValue, 16> Ops;
259 for (size_t i = 1; i < Node->getNumOperands(); ++i) {
260 SDValue Op = Node->getOperand(Num: i);
261 // Remove the wrapper when the call target is a function, an external
262 // symbol (which will be lowered to a library function), or an alias of
263 // a function. If the target is not a function/external symbol, we
264 // shouldn't remove the wrapper, because we cannot call it directly and
265 // instead we want it to be loaded with a CONST instruction and called
266 // with a call_indirect later.
267 if (i == 1 && Op->getOpcode() == WebAssemblyISD::Wrapper) {
268 SDValue NewOp = Op->getOperand(Num: 0);
269 if (auto *GlobalOp = dyn_cast<GlobalAddressSDNode>(Val: NewOp.getNode())) {
270 if (isa<Function>(
271 Val: GlobalOp->getGlobal()->stripPointerCastsAndAliases()))
272 Op = NewOp;
273 } else if (isa<ExternalSymbolSDNode>(Val: NewOp.getNode())) {
274 Op = NewOp;
275 }
276 }
277 Ops.push_back(Elt: Op);
278 }
279
280 // Add the chain last
281 Ops.push_back(Elt: Node->getOperand(Num: 0));
282 MachineSDNode *CallParams =
283 CurDAG->getMachineNode(Opcode: WebAssembly::CALL_PARAMS, dl: DL, VT: MVT::Glue, Ops);
284
285 unsigned Results = Node->getOpcode() == WebAssemblyISD::CALL
286 ? WebAssembly::CALL_RESULTS
287 : WebAssembly::RET_CALL_RESULTS;
288
289 SDValue Link(CallParams, 0);
290 MachineSDNode *CallResults =
291 CurDAG->getMachineNode(Opcode: Results, dl: DL, VTs: Node->getVTList(), Ops: Link);
292 ReplaceNode(F: Node, T: CallResults);
293 return;
294 }
295
296 default:
297 break;
298 }
299
300 // Select the default instruction.
301 SelectCode(N: Node);
302}
303
304bool WebAssemblyDAGToDAGISel::SelectInlineAsmMemoryOperand(
305 const SDValue &Op, InlineAsm::ConstraintCode ConstraintID,
306 std::vector<SDValue> &OutOps) {
307 switch (ConstraintID) {
308 case InlineAsm::ConstraintCode::m:
309 // We just support simple memory operands that just have a single address
310 // operand and need no special handling.
311 OutOps.push_back(x: Op);
312 return false;
313 default:
314 break;
315 }
316
317 return true;
318}
319
320bool WebAssemblyDAGToDAGISel::SelectAddrAddOperands(MVT OffsetType, SDValue N,
321 SDValue &Offset,
322 SDValue &Addr) {
323 assert(N.getNumOperands() == 2 && "Attempting to fold in a non-binary op");
324
325 // WebAssembly constant offsets are performed as unsigned with infinite
326 // precision, so we need to check for NoUnsignedWrap so that we don't fold an
327 // offset for an add that needs wrapping.
328 if (N.getOpcode() == ISD::ADD && !N.getNode()->getFlags().hasNoUnsignedWrap())
329 return false;
330
331 // Folds constants in an add into the offset.
332 for (size_t i = 0; i < 2; ++i) {
333 SDValue Op = N.getOperand(i);
334 SDValue OtherOp = N.getOperand(i: i == 0 ? 1 : 0);
335
336 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Val&: Op)) {
337 Offset =
338 CurDAG->getTargetConstant(Val: CN->getZExtValue(), DL: SDLoc(N), VT: OffsetType);
339 Addr = OtherOp;
340 return true;
341 }
342 }
343 return false;
344}
345
346bool WebAssemblyDAGToDAGISel::SelectAddrOperands(MVT AddrType,
347 unsigned ConstOpc, SDValue N,
348 SDValue &Offset,
349 SDValue &Addr) {
350 SDLoc DL(N);
351
352 // Fold target global addresses into the offset.
353 if (!TM.isPositionIndependent()) {
354 SDValue Op(N);
355 if (Op.getOpcode() == WebAssemblyISD::Wrapper)
356 Op = Op.getOperand(i: 0);
357
358 if (Op.getOpcode() == ISD::TargetGlobalAddress) {
359 Offset = Op;
360 Addr = SDValue(
361 CurDAG->getMachineNode(Opcode: ConstOpc, dl: DL, VT: AddrType,
362 Op1: CurDAG->getTargetConstant(Val: 0, DL, VT: AddrType)),
363 0);
364 return true;
365 }
366 }
367
368 // Fold anything inside an add into the offset.
369 if (N.getOpcode() == ISD::ADD &&
370 SelectAddrAddOperands(OffsetType: AddrType, N, Offset, Addr))
371 return true;
372
373 // Likewise, treat an 'or' node as an 'add' if the or'ed bits are known to be
374 // zero and fold them into the offset too.
375 if (N.getOpcode() == ISD::OR) {
376 bool OrIsAdd;
377 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Val: N.getOperand(i: 1))) {
378 OrIsAdd =
379 CurDAG->MaskedValueIsZero(Op: N->getOperand(Num: 0), Mask: CN->getAPIntValue());
380 } else {
381 KnownBits Known0 = CurDAG->computeKnownBits(Op: N->getOperand(Num: 0), Depth: 0);
382 KnownBits Known1 = CurDAG->computeKnownBits(Op: N->getOperand(Num: 1), Depth: 0);
383 OrIsAdd = (~Known0.Zero & ~Known1.Zero) == 0;
384 }
385
386 if (OrIsAdd && SelectAddrAddOperands(OffsetType: AddrType, N, Offset, Addr))
387 return true;
388 }
389
390 // Fold constant addresses into the offset.
391 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Val&: N)) {
392 Offset = CurDAG->getTargetConstant(Val: CN->getZExtValue(), DL, VT: AddrType);
393 Addr = SDValue(
394 CurDAG->getMachineNode(Opcode: ConstOpc, dl: DL, VT: AddrType,
395 Op1: CurDAG->getTargetConstant(Val: 0, DL, VT: AddrType)),
396 0);
397 return true;
398 }
399
400 // Else it's a plain old load/store with no offset.
401 Offset = CurDAG->getTargetConstant(Val: 0, DL, VT: AddrType);
402 Addr = N;
403 return true;
404}
405
406bool WebAssemblyDAGToDAGISel::SelectAddrOperands32(SDValue Op, SDValue &Offset,
407 SDValue &Addr) {
408 return SelectAddrOperands(AddrType: MVT::i32, ConstOpc: WebAssembly::CONST_I32, N: Op, Offset, Addr);
409}
410
411bool WebAssemblyDAGToDAGISel::SelectAddrOperands64(SDValue Op, SDValue &Offset,
412 SDValue &Addr) {
413 return SelectAddrOperands(AddrType: MVT::i64, ConstOpc: WebAssembly::CONST_I64, N: Op, Offset, Addr);
414}
415
416/// This pass converts a legalized DAG into a WebAssembly-specific DAG, ready
417/// for instruction scheduling.
418FunctionPass *llvm::createWebAssemblyISelDag(WebAssemblyTargetMachine &TM,
419 CodeGenOptLevel OptLevel) {
420 return new WebAssemblyDAGToDAGISelLegacy(TM, OptLevel);
421}
422