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