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 | |
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 | |
77 | private: |
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 | |
87 | char WebAssemblyDAGToDAGISel::ID; |
88 | |
89 | INITIALIZE_PASS(WebAssemblyDAGToDAGISel, DEBUG_TYPE, PASS_NAME, false, false) |
90 | |
91 | void 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 | |
103 | static 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 | |
114 | void 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 | |
296 | bool 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 | |
312 | bool 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 | |
338 | bool 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 | |
398 | bool 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 | |
403 | bool 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. |
410 | FunctionPass *llvm::createWebAssemblyISelDag(WebAssemblyTargetMachine &TM, |
411 | CodeGenOptLevel OptLevel) { |
412 | return new WebAssemblyDAGToDAGISel(TM, OptLevel); |
413 | } |
414 | |