LLVM 19.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 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
61 }
62
63 void PreprocessISelDAG() override;
64
65 void Select(SDNode *Node) override;
66
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,
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++)
99
101}
102
105 auto &MF = DAG->getMachineFunction();
106 const auto &TLI = DAG->getTargetLoweringInfo();
107 MVT PtrVT = TLI.getPointerTy(DAG->getDataLayout());
108 const char *SymName = Tag == WebAssembly::CPP_EXCEPTION
109 ? MF.createExternalSymbolName("__cpp_exception")
110 : MF.createExternalSymbolName("__c_longjmp");
111 return DAG->getTargetExternalSymbol(SymName, 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(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: {
132 break;
133
134 uint64_t SyncScopeID = Node->getConstantOperandVal(2);
135 MachineSDNode *Fence = nullptr;
136 switch (SyncScopeID) {
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(0) // inchain
145 );
146 break;
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(0) // inchain
156 );
157 break;
158 default:
159 llvm_unreachable("Unknown scope!");
160 }
161
162 ReplaceNode(Node, Fence);
163 CurDAG->RemoveDeadNode(Node);
164 return;
165 }
166
168 unsigned IntNo = Node->getConstantOperandVal(0);
169 switch (IntNo) {
170 case Intrinsic::wasm_tls_size: {
171 MachineSDNode *TLSSize = CurDAG->getMachineNode(
172 GlobalGetIns, DL, PtrVT,
173 CurDAG->getTargetExternalSymbol("__tls_size", PtrVT));
174 ReplaceNode(Node, TLSSize);
175 return;
176 }
177
178 case Intrinsic::wasm_tls_align: {
179 MachineSDNode *TLSAlign = CurDAG->getMachineNode(
180 GlobalGetIns, DL, PtrVT,
181 CurDAG->getTargetExternalSymbol("__tls_align", PtrVT));
182 ReplaceNode(Node, TLSAlign);
183 return;
184 }
185 }
186 break;
187 }
188
190 unsigned IntNo = Node->getConstantOperandVal(1);
191 const auto &TLI = CurDAG->getTargetLoweringInfo();
192 MVT PtrVT = TLI.getPointerTy(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("__tls_base", PtrVT),
198 Node->getOperand(0));
199 ReplaceNode(Node, TLSBase);
200 return;
201 }
202
203 case Intrinsic::wasm_catch: {
204 int Tag = Node->getConstantOperandVal(2);
205 SDValue SymNode = getTagSymNode(Tag, CurDAG);
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(Node, Catch);
217 return;
218 }
219 }
220 break;
221 }
222
223 case ISD::INTRINSIC_VOID: {
224 unsigned IntNo = Node->getConstantOperandVal(1);
225 switch (IntNo) {
226 case Intrinsic::wasm_throw: {
227 int Tag = Node->getConstantOperandVal(2);
228 SDValue SymNode = getTagSymNode(Tag, CurDAG);
229 MachineSDNode *Throw =
230 CurDAG->getMachineNode(WebAssembly::THROW, DL,
231 MVT::Other, // outchain type
232 {
233 SymNode, // exception symbol
234 Node->getOperand(3), // thrown value
235 Node->getOperand(0) // inchain
236 });
237 ReplaceNode(Node, 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.
251 for (size_t i = 1; i < Node->getNumOperands(); ++i) {
252 SDValue Op = Node->getOperand(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(0);
261 if (auto *GlobalOp = dyn_cast<GlobalAddressSDNode>(NewOp.getNode())) {
262 if (isa<Function>(
263 GlobalOp->getGlobal()->stripPointerCastsAndAliases()))
264 Op = NewOp;
265 } else if (isa<ExternalSymbolSDNode>(NewOp.getNode())) {
266 Op = NewOp;
267 }
268 }
269 Ops.push_back(Op);
270 }
271
272 // Add the chain last
273 Ops.push_back(Node->getOperand(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(Results, DL, Node->getVTList(), Link);
284 ReplaceNode(Node, 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(Op);
304 return false;
305 default:
306 break;
307 }
308
309 return true;
310}
311
312bool WebAssemblyDAGToDAGISel::SelectAddrAddOperands(MVT OffsetType, SDValue N,
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 == 0 ? 1 : 0);
327
328 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Op)) {
329 Offset =
330 CurDAG->getTargetConstant(CN->getZExtValue(), SDLoc(N), OffsetType);
331 Addr = OtherOp;
332 return true;
333 }
334 }
335 return false;
336}
337
338bool WebAssemblyDAGToDAGISel::SelectAddrOperands(MVT AddrType,
339 unsigned ConstOpc, SDValue N,
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(0);
349
350 if (Op.getOpcode() == ISD::TargetGlobalAddress) {
351 Offset = Op;
352 Addr = SDValue(
353 CurDAG->getMachineNode(ConstOpc, DL, AddrType,
354 CurDAG->getTargetConstant(0, DL, 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(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>(N.getOperand(1))) {
370 OrIsAdd =
371 CurDAG->MaskedValueIsZero(N->getOperand(0), CN->getAPIntValue());
372 } else {
373 KnownBits Known0 = CurDAG->computeKnownBits(N->getOperand(0), 0);
374 KnownBits Known1 = CurDAG->computeKnownBits(N->getOperand(1), 0);
375 OrIsAdd = (~Known0.Zero & ~Known1.Zero) == 0;
376 }
377
378 if (OrIsAdd && SelectAddrAddOperands(AddrType, N, Offset, Addr))
379 return true;
380 }
381
382 // Fold constant addresses into the offset.
383 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) {
384 Offset = CurDAG->getTargetConstant(CN->getZExtValue(), DL, AddrType);
385 Addr = SDValue(
386 CurDAG->getMachineNode(ConstOpc, DL, AddrType,
387 CurDAG->getTargetConstant(0, DL, AddrType)),
388 0);
389 return true;
390 }
391
392 // Else it's a plain old load/store with no offset.
393 Offset = CurDAG->getTargetConstant(0, DL, AddrType);
394 Addr = N;
395 return true;
396}
397
398bool WebAssemblyDAGToDAGISel::SelectAddrOperands32(SDValue Op, SDValue &Offset,
399 SDValue &Addr) {
400 return SelectAddrOperands(MVT::i32, WebAssembly::CONST_I32, Op, Offset, Addr);
401}
402
403bool WebAssemblyDAGToDAGISel::SelectAddrOperands64(SDValue Op, SDValue &Offset,
404 SDValue &Addr) {
405 return SelectAddrOperands(MVT::i64, WebAssembly::CONST_I64, Op, Offset, Addr);
406}
407
408/// This pass converts a legalized DAG into a WebAssembly-specific DAG, ready
409/// for instruction scheduling.
411 CodeGenOptLevel OptLevel) {
412 return new WebAssemblyDAGToDAGISel(TM, OptLevel);
413}
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
This class represents an Operation in the Expression.
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 bool SelectInlineAsmMemoryOperand(const SDValue &Op, InlineAsm::ConstraintCode ConstraintID, std::vector< SDValue > &OutOps)
SelectInlineAsmMemoryOperand - Select the specified address as a target addressing mode,...
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...
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:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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
@ 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:1233
@ 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:456
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
FunctionPass * createWebAssemblyISelDag(WebAssemblyTargetMachine &TM, CodeGenOptLevel OptLevel)
This pass converts a legalized DAG into a WebAssembly-specific DAG, ready for instruction scheduling.
CodeGenOptLevel
Code generation optimization level.
Definition: CodeGen.h:54
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
DWARFExpression::Operation Op
#define N