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 static char ID;
46
47 WebAssemblyDAGToDAGISel() = delete;
48
49 WebAssemblyDAGToDAGISel(WebAssemblyTargetMachine &TM,
50 CodeGenOptLevel 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,
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
77private:
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
87char WebAssemblyDAGToDAGISel::ID;
88
89INITIALIZE_PASS(WebAssemblyDAGToDAGISel, DEBUG_TYPE, PASS_NAME, false, false)
90
91void 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&: *MF, FrameIndex: Idx);
99
100 SelectionDAGISel::PreprocessISelDAG();
101}
102
103static 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(DL: DAG->getDataLayout());
108 const char *SymName = Tag == WebAssembly::CPP_EXCEPTION
109 ? MF.createExternalSymbolName(Name: "__cpp_exception")
110 : MF.createExternalSymbolName(Name: "__c_longjmp");
111 return DAG->getTargetExternalSymbol(Sym: SymName, VT: PtrVT);
112}
113
114void 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(DL: 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(Num: 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(Num: 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(Num: 0) // inchain
156 );
157 break;
158 default:
159 llvm_unreachable("Unknown scope!");
160 }
161
162 ReplaceNode(F: Node, T: Fence);
163 CurDAG->RemoveDeadNode(N: Node);
164 return;
165 }
166
167 case ISD::INTRINSIC_WO_CHAIN: {
168 unsigned IntNo = Node->getConstantOperandVal(Num: 0);
169 switch (IntNo) {
170 case Intrinsic::wasm_tls_size: {
171 MachineSDNode *TLSSize = CurDAG->getMachineNode(
172 GlobalGetIns, DL, PtrVT,
173 CurDAG->getTargetExternalSymbol(Sym: "__tls_size", VT: PtrVT));
174 ReplaceNode(F: Node, T: TLSSize);
175 return;
176 }
177
178 case Intrinsic::wasm_tls_align: {
179 MachineSDNode *TLSAlign = CurDAG->getMachineNode(
180 GlobalGetIns, DL, PtrVT,
181 CurDAG->getTargetExternalSymbol(Sym: "__tls_align", VT: PtrVT));
182 ReplaceNode(F: Node, T: TLSAlign);
183 return;
184 }
185 }
186 break;
187 }
188
189 case ISD::INTRINSIC_W_CHAIN: {
190 unsigned IntNo = Node->getConstantOperandVal(Num: 1);
191 const auto &TLI = CurDAG->getTargetLoweringInfo();
192 MVT PtrVT = TLI.getPointerTy(DL: 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(Sym: "__tls_base", VT: PtrVT),
198 Node->getOperand(Num: 0));
199 ReplaceNode(F: Node, T: TLSBase);
200 return;
201 }
202
203 case Intrinsic::wasm_catch: {
204 int Tag = Node->getConstantOperandVal(Num: 2);
205 SDValue SymNode = getTagSymNode(Tag, DAG: 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(F: Node, T: Catch);
217 return;
218 }
219 }
220 break;
221 }
222
223 case ISD::INTRINSIC_VOID: {
224 unsigned IntNo = Node->getConstantOperandVal(Num: 1);
225 switch (IntNo) {
226 case Intrinsic::wasm_throw: {
227 int Tag = Node->getConstantOperandVal(Num: 2);
228 SDValue SymNode = getTagSymNode(Tag, DAG: CurDAG);
229 MachineSDNode *Throw =
230 CurDAG->getMachineNode(WebAssembly::THROW, DL,
231 MVT::Other, // outchain type
232 {
233 SymNode, // exception symbol
234 Node->getOperand(Num: 3), // thrown value
235 Node->getOperand(Num: 0) // inchain
236 });
237 ReplaceNode(F: Node, T: 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(Num: 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(Num: 0);
261 if (auto *GlobalOp = dyn_cast<GlobalAddressSDNode>(Val: NewOp.getNode())) {
262 if (isa<Function>(
263 Val: GlobalOp->getGlobal()->stripPointerCastsAndAliases()))
264 Op = NewOp;
265 } else if (isa<ExternalSymbolSDNode>(Val: NewOp.getNode())) {
266 Op = NewOp;
267 }
268 }
269 Ops.push_back(Elt: Op);
270 }
271
272 // Add the chain last
273 Ops.push_back(Elt: Node->getOperand(Num: 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(Opcode: Results, dl: DL, VTs: Node->getVTList(), Ops: Link);
284 ReplaceNode(F: Node, T: CallResults);
285 return;
286 }
287
288 default:
289 break;
290 }
291
292 // Select the default instruction.
293 SelectCode(Node);
294}
295
296bool 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(x: Op);
304 return false;
305 default:
306 break;
307 }
308
309 return true;
310}
311
312bool 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: i == 0 ? 1 : 0);
327
328 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Val&: Op)) {
329 Offset =
330 CurDAG->getTargetConstant(Val: CN->getZExtValue(), DL: SDLoc(N), VT: OffsetType);
331 Addr = OtherOp;
332 return true;
333 }
334 }
335 return false;
336}
337
338bool 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(i: 0);
349
350 if (Op.getOpcode() == ISD::TargetGlobalAddress) {
351 Offset = Op;
352 Addr = SDValue(
353 CurDAG->getMachineNode(Opcode: ConstOpc, dl: DL, VT: AddrType,
354 Op1: CurDAG->getTargetConstant(Val: 0, DL, VT: 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(OffsetType: 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>(Val: N.getOperand(i: 1))) {
370 OrIsAdd =
371 CurDAG->MaskedValueIsZero(Op: N->getOperand(Num: 0), Mask: CN->getAPIntValue());
372 } else {
373 KnownBits Known0 = CurDAG->computeKnownBits(Op: N->getOperand(Num: 0), Depth: 0);
374 KnownBits Known1 = CurDAG->computeKnownBits(Op: N->getOperand(Num: 1), Depth: 0);
375 OrIsAdd = (~Known0.Zero & ~Known1.Zero) == 0;
376 }
377
378 if (OrIsAdd && SelectAddrAddOperands(OffsetType: AddrType, N, Offset, Addr))
379 return true;
380 }
381
382 // Fold constant addresses into the offset.
383 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Val&: N)) {
384 Offset = CurDAG->getTargetConstant(Val: CN->getZExtValue(), DL, VT: AddrType);
385 Addr = SDValue(
386 CurDAG->getMachineNode(Opcode: ConstOpc, dl: DL, VT: AddrType,
387 Op1: CurDAG->getTargetConstant(Val: 0, DL, VT: AddrType)),
388 0);
389 return true;
390 }
391
392 // Else it's a plain old load/store with no offset.
393 Offset = CurDAG->getTargetConstant(Val: 0, DL, VT: AddrType);
394 Addr = N;
395 return true;
396}
397
398bool WebAssemblyDAGToDAGISel::SelectAddrOperands32(SDValue Op, SDValue &Offset,
399 SDValue &Addr) {
400 return SelectAddrOperands(MVT::AddrType: i32, WebAssembly::ConstOpc: CONST_I32, N: Op, Offset, Addr);
401}
402
403bool WebAssemblyDAGToDAGISel::SelectAddrOperands64(SDValue Op, SDValue &Offset,
404 SDValue &Addr) {
405 return SelectAddrOperands(MVT::AddrType: i64, WebAssembly::ConstOpc: CONST_I64, N: Op, Offset, Addr);
406}
407
408/// This pass converts a legalized DAG into a WebAssembly-specific DAG, ready
409/// for instruction scheduling.
410FunctionPass *llvm::createWebAssemblyISelDag(WebAssemblyTargetMachine &TM,
411 CodeGenOptLevel OptLevel) {
412 return new WebAssemblyDAGToDAGISel(TM, OptLevel);
413}
414

source code of llvm/lib/Target/WebAssembly/WebAssemblyISelDAGToDAG.cpp