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