LLVM 17.0.0git
WebAssemblyISelDAGToDAG.cpp
Go to the documentation of this file.
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
15#include "WebAssembly.h"
22#include "llvm/IR/Function.h" // To access function attributes.
23#include "llvm/IR/IntrinsicsWebAssembly.h"
24#include "llvm/Support/Debug.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 CodeGenOpt::Level 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
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
76private:
77 // add select functions here...
78
79 bool SelectAddrOperands(MVT AddrType, unsigned ConstOpc, SDValue Op,
81 bool SelectAddrAddOperands(MVT OffsetType, SDValue N, SDValue &Offset,
82 SDValue &Addr);
83};
84} // end anonymous namespace
85
86char WebAssemblyDAGToDAGISel::ID;
87
88INITIALIZE_PASS(WebAssemblyDAGToDAGISel, DEBUG_TYPE, PASS_NAME, false, false)
89
90void 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++)
98
100}
101
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
113void 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: {
131 break;
132
133 uint64_t SyncScopeID = Node->getConstantOperandVal(2);
134 MachineSDNode *Fence = nullptr;
135 switch (SyncScopeID) {
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;
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
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
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);
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.
250 for (size_t i = 1; i < Node->getNumOperands(); ++i) {
251 SDValue Op = Node->getOperand(i);
252 // Remove the wrapper when the call target is a function, an external
253 // symbol (which will be lowered to a library function), or an alias of
254 // a function. If the target is not a function/external symbol, we
255 // shouldn't remove the wrapper, because we cannot call it directly and
256 // instead we want it to be loaded with a CONST instruction and called
257 // with a call_indirect later.
258 if (i == 1 && Op->getOpcode() == WebAssemblyISD::Wrapper) {
259 SDValue NewOp = Op->getOperand(0);
260 if (auto *GlobalOp = dyn_cast<GlobalAddressSDNode>(NewOp.getNode())) {
261 if (isa<Function>(
262 GlobalOp->getGlobal()->stripPointerCastsAndAliases()))
263 Op = NewOp;
264 } else if (isa<ExternalSymbolSDNode>(NewOp.getNode())) {
265 Op = NewOp;
266 }
267 }
268 Ops.push_back(Op);
269 }
270
271 // Add the chain last
272 Ops.push_back(Node->getOperand(0));
273 MachineSDNode *CallParams =
274 CurDAG->getMachineNode(WebAssembly::CALL_PARAMS, DL, MVT::Glue, Ops);
275
276 unsigned Results = Node->getOpcode() == WebAssemblyISD::CALL
277 ? WebAssembly::CALL_RESULTS
278 : WebAssembly::RET_CALL_RESULTS;
279
280 SDValue Link(CallParams, 0);
281 MachineSDNode *CallResults =
282 CurDAG->getMachineNode(Results, DL, Node->getVTList(), Link);
283 ReplaceNode(Node, CallResults);
284 return;
285 }
286
287 default:
288 break;
289 }
290
291 // Select the default instruction.
292 SelectCode(Node);
293}
294
295bool WebAssemblyDAGToDAGISel::SelectInlineAsmMemoryOperand(
296 const SDValue &Op, unsigned ConstraintID, std::vector<SDValue> &OutOps) {
297 switch (ConstraintID) {
299 // We just support simple memory operands that just have a single address
300 // operand and need no special handling.
301 OutOps.push_back(Op);
302 return false;
303 default:
304 break;
305 }
306
307 return true;
308}
309
310bool WebAssemblyDAGToDAGISel::SelectAddrAddOperands(MVT OffsetType, SDValue N,
312 SDValue &Addr) {
313 assert(N.getNumOperands() == 2 && "Attempting to fold in a non-binary op");
314
315 // WebAssembly constant offsets are performed as unsigned with infinite
316 // precision, so we need to check for NoUnsignedWrap so that we don't fold an
317 // offset for an add that needs wrapping.
318 if (N.getOpcode() == ISD::ADD && !N.getNode()->getFlags().hasNoUnsignedWrap())
319 return false;
320
321 // Folds constants in an add into the offset.
322 for (size_t i = 0; i < 2; ++i) {
323 SDValue Op = N.getOperand(i);
324 SDValue OtherOp = N.getOperand(i == 0 ? 1 : 0);
325
326 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Op)) {
327 Offset =
328 CurDAG->getTargetConstant(CN->getZExtValue(), SDLoc(N), OffsetType);
329 Addr = OtherOp;
330 return true;
331 }
332 }
333 return false;
334}
335
336bool WebAssemblyDAGToDAGISel::SelectAddrOperands(MVT AddrType,
337 unsigned ConstOpc, SDValue N,
339 SDValue &Addr) {
340 SDLoc DL(N);
341
342 // Fold target global addresses into the offset.
343 if (!TM.isPositionIndependent()) {
344 SDValue Op(N);
345 if (Op.getOpcode() == WebAssemblyISD::Wrapper)
346 Op = Op.getOperand(0);
347
348 if (Op.getOpcode() == ISD::TargetGlobalAddress) {
349 Offset = Op;
350 Addr = SDValue(
351 CurDAG->getMachineNode(ConstOpc, DL, AddrType,
352 CurDAG->getTargetConstant(0, DL, AddrType)),
353 0);
354 return true;
355 }
356 }
357
358 // Fold anything inside an add into the offset.
359 if (N.getOpcode() == ISD::ADD &&
360 SelectAddrAddOperands(AddrType, N, Offset, Addr))
361 return true;
362
363 // Likewise, treat an 'or' node as an 'add' if the or'ed bits are known to be
364 // zero and fold them into the offset too.
365 if (N.getOpcode() == ISD::OR) {
366 bool OrIsAdd;
367 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
368 OrIsAdd =
369 CurDAG->MaskedValueIsZero(N->getOperand(0), CN->getAPIntValue());
370 } else {
371 KnownBits Known0 = CurDAG->computeKnownBits(N->getOperand(0), 0);
372 KnownBits Known1 = CurDAG->computeKnownBits(N->getOperand(1), 0);
373 OrIsAdd = (~Known0.Zero & ~Known1.Zero) == 0;
374 }
375
376 if (OrIsAdd && SelectAddrAddOperands(AddrType, N, Offset, Addr))
377 return true;
378 }
379
380 // Fold constant addresses into the offset.
381 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) {
382 Offset = CurDAG->getTargetConstant(CN->getZExtValue(), DL, AddrType);
383 Addr = SDValue(
384 CurDAG->getMachineNode(ConstOpc, DL, AddrType,
385 CurDAG->getTargetConstant(0, DL, AddrType)),
386 0);
387 return true;
388 }
389
390 // Else it's a plain old load/store with no offset.
391 Offset = CurDAG->getTargetConstant(0, DL, AddrType);
392 Addr = N;
393 return true;
394}
395
396bool WebAssemblyDAGToDAGISel::SelectAddrOperands32(SDValue Op, SDValue &Offset,
397 SDValue &Addr) {
398 return SelectAddrOperands(MVT::i32, WebAssembly::CONST_I32, Op, Offset, Addr);
399}
400
401bool WebAssemblyDAGToDAGISel::SelectAddrOperands64(SDValue Op, SDValue &Offset,
402 SDValue &Addr) {
403 return SelectAddrOperands(MVT::i64, WebAssembly::CONST_I64, Op, Offset, Addr);
404}
405
406/// This pass converts a legalized DAG into a WebAssembly-specific DAG, ready
407/// for instruction scheduling.
409 CodeGenOpt::Level OptLevel) {
410 return new WebAssemblyDAGToDAGISel(TM, OptLevel);
411}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu AMDGPU Register Bank Select
Function Alias Analysis Results
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
uint64_t Addr
const char LLVMTargetMachineRef TM
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static SDValue getTagSymNode(int Tag, SelectionDAG *DAG)
#define PASS_NAME
#define DEBUG_TYPE
This file defines the interfaces that WebAssembly uses to lower LLVM code into a selection DAG.
This file provides WebAssembly-specific target descriptions.
This file declares the WebAssembly-specific subclass of TargetMachine.
This file contains the entry points for global functions defined in the LLVM WebAssembly back-end.
DEMANGLE_DUMP_METHOD void dump() const
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
Machine Value Type.
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
int getObjectIndexEnd() const
Return one past the maximum frame object index.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
An SDNode that represents everything that will be needed to construct a MachineInstr.
Wrapper class for IR location info (IR ordering and DebugLoc) to be passed into SDNode creation funct...
Represents one node in the SelectionDAG.
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
SDNode * getNode() const
get the SDNode which holds the desired result
SelectionDAGISel - This is the common base class used for SelectionDAG-based pattern-matching instruc...
virtual void PreprocessISelDAG()
PreprocessISelDAG - This hook allows targets to hack on the graph before instruction selection starts...
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintID, std::vector< SDValue > &OutOps)
SelectInlineAsmMemoryOperand - Select the specified address as a target addressing mode,...
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
Definition: SelectionDAG.h:225
const TargetLowering & getTargetLoweringInfo() const
Definition: SelectionDAG.h:478
const DataLayout & getDataLayout() const
Definition: SelectionDAG.h:472
MachineFunction & getMachineFunction() const
Definition: SelectionDAG.h:469
SDValue getTargetExternalSymbol(const char *Sym, EVT VT, unsigned TargetFlags=0)
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
static std::optional< unsigned > getLocalForStackObject(MachineFunction &MF, int FrameIndex)
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Level
Code generation optimization level.
Definition: CodeGen.h:57
@ ADD
Simple integer binary arithmetic operators.
Definition: ISDOpcodes.h:239
@ INTRINSIC_VOID
OUTCHAIN = INTRINSIC_VOID(INCHAIN, INTRINSICID, arg1, arg2, ...) This node represents a target intrin...
Definition: ISDOpcodes.h:199
@ ATOMIC_FENCE
OUTCHAIN = ATOMIC_FENCE(INCHAIN, ordering, scope) This corresponds to the fence instruction.
Definition: ISDOpcodes.h:1170
@ TargetGlobalAddress
TargetGlobalAddress - Like GlobalAddress, but the DAG does no folding or anything else with this node...
Definition: ISDOpcodes.h:164
@ INTRINSIC_WO_CHAIN
RESULT = INTRINSIC_WO_CHAIN(INTRINSICID, arg1, arg2, ...) This node represents a target intrinsic fun...
Definition: ISDOpcodes.h:184
@ INTRINSIC_W_CHAIN
RESULT,OUTCHAIN = INTRINSIC_W_CHAIN(INCHAIN, INTRINSICID, arg1, ...) This node represents a target in...
Definition: ISDOpcodes.h:192
@ SingleThread
Synchronized with respect to signal handlers executing in the same thread.
Definition: LLVMContext.h:54
@ System
Synchronized with respect to all concurrently executing threads.
Definition: LLVMContext.h:57
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:406
FunctionPass * createWebAssemblyISelDag(WebAssemblyTargetMachine &TM, CodeGenOpt::Level OptLevel)
This pass converts a legalized DAG into a WebAssembly-specific DAG, ready for instruction scheduling.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
#define N