1//===-- WebAssemblyFrameLowering.cpp - WebAssembly Frame Lowering ----------==//
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 contains the WebAssembly implementation of
11/// TargetFrameLowering class.
12///
13/// On WebAssembly, there aren't a lot of things to do here. There are no
14/// callee-saved registers to save, and no spill slots.
15///
16/// The stack grows downward.
17///
18//===----------------------------------------------------------------------===//
19
20#include "WebAssemblyFrameLowering.h"
21#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
22#include "Utils/WebAssemblyTypeUtilities.h"
23#include "WebAssembly.h"
24#include "WebAssemblyInstrInfo.h"
25#include "WebAssemblyMachineFunctionInfo.h"
26#include "WebAssemblySubtarget.h"
27#include "llvm/CodeGen/Analysis.h"
28#include "llvm/CodeGen/MachineFrameInfo.h"
29#include "llvm/CodeGen/MachineFunction.h"
30#include "llvm/CodeGen/MachineInstrBuilder.h"
31#include "llvm/CodeGen/MachineRegisterInfo.h"
32#include "llvm/IR/Instructions.h"
33#include "llvm/IR/Module.h"
34using namespace llvm;
35
36#define DEBUG_TYPE "wasm-frame-info"
37
38// TODO: wasm64
39// TODO: Emit TargetOpcode::CFI_INSTRUCTION instructions
40
41// In an ideal world, when objects are added to the MachineFrameInfo by
42// FunctionLoweringInfo::set, we could somehow hook into target-specific code to
43// ensure they are assigned the right stack ID. However there isn't a hook that
44// runs between then and DAG building time, though, so instead we hoist stack
45// objects lazily when they are first used, and comprehensively after the DAG is
46// built via the PreprocessISelDAG hook, called by the
47// SelectionDAGISel::runOnMachineFunction. We have to do it in two places
48// because we want to do it while building the selection DAG for uses of alloca,
49// but not all alloca instructions are used so we have to follow up afterwards.
50std::optional<unsigned>
51WebAssemblyFrameLowering::getLocalForStackObject(MachineFunction &MF,
52 int FrameIndex) {
53 MachineFrameInfo &MFI = MF.getFrameInfo();
54
55 // If already hoisted to a local, done.
56 if (MFI.getStackID(ObjectIdx: FrameIndex) == TargetStackID::WasmLocal)
57 return static_cast<unsigned>(MFI.getObjectOffset(ObjectIdx: FrameIndex));
58
59 // If not allocated in the object address space, this object will be in
60 // linear memory.
61 const AllocaInst *AI = MFI.getObjectAllocation(ObjectIdx: FrameIndex);
62 if (!AI || !WebAssembly::isWasmVarAddressSpace(AS: AI->getAddressSpace()))
63 return std::nullopt;
64
65 // Otherwise, allocate this object in the named value stack, outside of linear
66 // memory.
67 SmallVector<EVT, 4> ValueVTs;
68 const WebAssemblyTargetLowering &TLI =
69 *MF.getSubtarget<WebAssemblySubtarget>().getTargetLowering();
70 WebAssemblyFunctionInfo *FuncInfo = MF.getInfo<WebAssemblyFunctionInfo>();
71 ComputeValueVTs(TLI, DL: MF.getDataLayout(), Ty: AI->getAllocatedType(), ValueVTs);
72 MFI.setStackID(ObjectIdx: FrameIndex, ID: TargetStackID::WasmLocal);
73 // Abuse SP offset to record the index of the first local in the object.
74 unsigned Local = FuncInfo->getParams().size() + FuncInfo->getLocals().size();
75 MFI.setObjectOffset(ObjectIdx: FrameIndex, SPOffset: Local);
76 // Allocate WebAssembly locals for each non-aggregate component of the
77 // allocation.
78 for (EVT ValueVT : ValueVTs)
79 FuncInfo->addLocal(VT: ValueVT.getSimpleVT());
80 // Abuse object size to record number of WebAssembly locals allocated to
81 // this object.
82 MFI.setObjectSize(ObjectIdx: FrameIndex, Size: ValueVTs.size());
83 return Local;
84}
85
86/// We need a base pointer in the case of having items on the stack that
87/// require stricter alignment than the stack pointer itself. Because we need
88/// to shift the stack pointer by some unknown amount to force the alignment,
89/// we need to record the value of the stack pointer on entry to the function.
90bool WebAssemblyFrameLowering::hasBP(const MachineFunction &MF) const {
91 const auto *RegInfo =
92 MF.getSubtarget<WebAssemblySubtarget>().getRegisterInfo();
93 return RegInfo->hasStackRealignment(MF);
94}
95
96/// Return true if the specified function should have a dedicated frame pointer
97/// register.
98bool WebAssemblyFrameLowering::hasFPImpl(const MachineFunction &MF) const {
99 const MachineFrameInfo &MFI = MF.getFrameInfo();
100
101 // When we have var-sized objects, we move the stack pointer by an unknown
102 // amount, and need to emit a frame pointer to restore the stack to where we
103 // were on function entry.
104 // If we already need a base pointer, we use that to fix up the stack pointer.
105 // If there are no fixed-size objects, we would have no use of a frame
106 // pointer, and thus should not emit one.
107 bool HasFixedSizedObjects = MFI.getStackSize() > 0;
108 bool NeedsFixedReference = !hasBP(MF) || HasFixedSizedObjects;
109
110 return MFI.isFrameAddressTaken() ||
111 (MFI.hasVarSizedObjects() && NeedsFixedReference) ||
112 MFI.hasStackMap() || MFI.hasPatchPoint();
113}
114
115/// Under normal circumstances, when a frame pointer is not required, we reserve
116/// argument space for call sites in the function immediately on entry to the
117/// current function. This eliminates the need for add/sub sp brackets around
118/// call sites. Returns true if the call frame is included as part of the stack
119/// frame.
120bool WebAssemblyFrameLowering::hasReservedCallFrame(
121 const MachineFunction &MF) const {
122 return !MF.getFrameInfo().hasVarSizedObjects();
123}
124
125// Returns true if this function needs a local user-space stack pointer for its
126// local frame (not for exception handling).
127bool WebAssemblyFrameLowering::needsSPForLocalFrame(
128 const MachineFunction &MF) const {
129 auto &MFI = MF.getFrameInfo();
130 auto &MRI = MF.getRegInfo();
131 // llvm.stacksave can explicitly read SP register and it can appear without
132 // dynamic alloca.
133 bool HasExplicitSPUse =
134 any_of(Range: MRI.use_operands(Reg: getSPReg(MF)),
135 P: [](MachineOperand &MO) { return !MO.isImplicit(); });
136
137 // With libcall thread context, we need SP in the prolog when debug
138 // info is present so we can allocate a local for DWARF to reference.
139 bool NeedsSPForDebug =
140 MF.getFunction().getSubprogram() &&
141 MF.getSubtarget<WebAssemblySubtarget>().hasLibcallThreadContext();
142
143 return MFI.getStackSize() || MFI.adjustsStack() || hasFP(MF) ||
144 HasExplicitSPUse || NeedsSPForDebug;
145}
146
147// In function with EH pads, we need to make a copy of the value of
148// the stack pointer in the SP32/64 register, in order to use it when
149// restoring the stack pointer after an exception is caught.
150bool WebAssemblyFrameLowering::needsPrologForEH(
151 const MachineFunction &MF) const {
152 return MF.getFunction().hasPersonalityFn() && MF.getFrameInfo().hasCalls() &&
153 MF.getFunction().getParent()->getExceptionModel() ==
154 ExceptionHandling::Wasm;
155}
156
157/// Returns true if this function needs a local user-space stack pointer.
158/// Unlike a machine stack pointer, the wasm user stack pointer is a global
159/// variable or managed by library calls, so it is loaded
160/// into a register in the prolog.
161bool WebAssemblyFrameLowering::needsSP(const MachineFunction &MF) const {
162 return needsSPForLocalFrame(MF) || needsPrologForEH(MF);
163}
164
165/// Returns true if the local user-space stack pointer needs to be written back
166/// to the stack pointer global/thread context by this function (this is not
167/// meaningful if needsSP is false). If false, the stack red zone can be used
168/// and only a local SP is needed.
169bool WebAssemblyFrameLowering::needsSPWriteback(
170 const MachineFunction &MF) const {
171 auto &MFI = MF.getFrameInfo();
172 assert(needsSP(MF));
173 // When we don't need a local stack pointer for its local frame but only to
174 // support EH, we don't need to write SP back in the epilog, because we don't
175 // bump down the stack pointer in the prolog. We need to write SP back in the
176 // epilog only if
177 // 1. We need SP not only for EH support but also because we actually use
178 // stack or we have a frame address taken.
179 // 2. We cannot use the red zone.
180 bool CanUseRedZone = MFI.getStackSize() <= RedZoneSize && !MFI.hasCalls() &&
181 !MF.getFunction().hasFnAttribute(Kind: Attribute::NoRedZone);
182 return needsSPForLocalFrame(MF) && !CanUseRedZone;
183}
184
185unsigned WebAssemblyFrameLowering::getSPReg(const MachineFunction &MF) {
186 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64()
187 ? WebAssembly::SP64
188 : WebAssembly::SP32;
189}
190
191unsigned WebAssemblyFrameLowering::getFPReg(const MachineFunction &MF) {
192 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64()
193 ? WebAssembly::FP64
194 : WebAssembly::FP32;
195}
196
197unsigned
198WebAssemblyFrameLowering::getOpcConst(const MachineFunction &MF) {
199 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64()
200 ? WebAssembly::CONST_I64
201 : WebAssembly::CONST_I32;
202}
203
204unsigned WebAssemblyFrameLowering::getOpcAdd(const MachineFunction &MF) {
205 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64()
206 ? WebAssembly::ADD_I64
207 : WebAssembly::ADD_I32;
208}
209
210unsigned WebAssemblyFrameLowering::getOpcSub(const MachineFunction &MF) {
211 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64()
212 ? WebAssembly::SUB_I64
213 : WebAssembly::SUB_I32;
214}
215
216unsigned WebAssemblyFrameLowering::getOpcAnd(const MachineFunction &MF) {
217 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64()
218 ? WebAssembly::AND_I64
219 : WebAssembly::AND_I32;
220}
221
222unsigned
223WebAssemblyFrameLowering::getOpcGlobGet(const MachineFunction &MF) {
224 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64()
225 ? WebAssembly::GLOBAL_GET_I64
226 : WebAssembly::GLOBAL_GET_I32;
227}
228
229unsigned
230WebAssemblyFrameLowering::getOpcGlobSet(const MachineFunction &MF) {
231 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64()
232 ? WebAssembly::GLOBAL_SET_I64
233 : WebAssembly::GLOBAL_SET_I32;
234}
235
236void WebAssemblyFrameLowering::writeBackSP(
237 unsigned SrcReg, MachineFunction &MF, MachineBasicBlock &MBB,
238 MachineBasicBlock::iterator &InsertStore, const DebugLoc &DL) const {
239 const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
240
241 if (MF.getSubtarget<WebAssemblySubtarget>().hasLibcallThreadContext()) {
242 const char *ES = "__wasm_set_stack_pointer";
243 auto *SPSymbol = MF.createExternalSymbolName(Name: ES);
244 BuildMI(BB&: MBB, I: InsertStore, MIMD: DL, MCID: TII->get(Opcode: WebAssembly::CALL))
245 .addExternalSymbol(FnName: SPSymbol)
246 .addReg(RegNo: SrcReg);
247 } else {
248 const char *ES = "__stack_pointer";
249 auto *SPSymbol = MF.createExternalSymbolName(Name: ES);
250
251 BuildMI(BB&: MBB, I: InsertStore, MIMD: DL, MCID: TII->get(Opcode: getOpcGlobSet(MF)))
252 .addExternalSymbol(FnName: SPSymbol)
253 .addReg(RegNo: SrcReg);
254 }
255}
256
257MachineBasicBlock::iterator
258WebAssemblyFrameLowering::eliminateCallFramePseudoInstr(
259 MachineFunction &MF, MachineBasicBlock &MBB,
260 MachineBasicBlock::iterator I) const {
261 assert(!I->getOperand(0).getImm() && (hasFP(MF) || hasBP(MF)) &&
262 "Call frame pseudos should only be used for dynamic stack adjustment");
263 auto &ST = MF.getSubtarget<WebAssemblySubtarget>();
264 const auto *TII = ST.getInstrInfo();
265 if (I->getOpcode() == TII->getCallFrameDestroyOpcode() &&
266 needsSPWriteback(MF)) {
267 DebugLoc DL = I->getDebugLoc();
268 writeBackSP(SrcReg: getSPReg(MF), MF, MBB, InsertStore&: I, DL);
269 }
270 return MBB.erase(I);
271}
272
273void WebAssemblyFrameLowering::emitPrologue(MachineFunction &MF,
274 MachineBasicBlock &MBB) const {
275 // TODO: Do ".setMIFlag(MachineInstr::FrameSetup)" on emitted instructions
276 auto &MFI = MF.getFrameInfo();
277 assert(MFI.getCalleeSavedInfo().empty() &&
278 "WebAssembly should not have callee-saved registers");
279
280 if (!needsSP(MF))
281 return;
282 uint64_t StackSize = MFI.getStackSize();
283
284 auto &ST = MF.getSubtarget<WebAssemblySubtarget>();
285 const auto *TII = ST.getInstrInfo();
286 auto &MRI = MF.getRegInfo();
287
288 auto InsertPt = MBB.begin();
289 while (InsertPt != MBB.end() &&
290 WebAssembly::isArgument(Opc: InsertPt->getOpcode()))
291 ++InsertPt;
292 DebugLoc DL;
293
294 const TargetRegisterClass *PtrRC =
295 TII->getRegClass(MCID: TII->get(Opcode: getOpcConst(MF)), OpNum: 0);
296 unsigned SPReg = getSPReg(MF);
297 if (StackSize)
298 SPReg = MRI.createVirtualRegister(RegClass: PtrRC);
299
300 if (ST.hasLibcallThreadContext()) {
301 const char *ES = "__wasm_get_stack_pointer";
302 auto *SPSymbol = MF.createExternalSymbolName(Name: ES);
303 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: WebAssembly::CALL), DestReg: SPReg)
304 .addExternalSymbol(FnName: SPSymbol);
305 } else {
306 const char *ES = "__stack_pointer";
307 auto *SPSymbol = MF.createExternalSymbolName(Name: ES);
308 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: getOpcGlobGet(MF)), DestReg: SPReg)
309 .addExternalSymbol(FnName: SPSymbol);
310 }
311
312 bool HasBP = hasBP(MF);
313 if (HasBP) {
314 auto FI = MF.getInfo<WebAssemblyFunctionInfo>();
315 Register BasePtr = MRI.createVirtualRegister(RegClass: PtrRC);
316 FI->setBasePointerVreg(BasePtr);
317 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: WebAssembly::COPY), DestReg: BasePtr)
318 .addReg(RegNo: SPReg);
319 }
320 if (StackSize) {
321 // Subtract the frame size
322 Register OffsetReg = MRI.createVirtualRegister(RegClass: PtrRC);
323 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: getOpcConst(MF)), DestReg: OffsetReg)
324 .addImm(Val: StackSize);
325 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: getOpcSub(MF)), DestReg: getSPReg(MF))
326 .addReg(RegNo: SPReg)
327 .addReg(RegNo: OffsetReg);
328 }
329 if (HasBP) {
330 Register BitmaskReg = MRI.createVirtualRegister(RegClass: PtrRC);
331 Align Alignment = MFI.getMaxAlign();
332 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: getOpcConst(MF)), DestReg: BitmaskReg)
333 .addImm(Val: (int64_t) ~(Alignment.value() - 1));
334 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: getOpcAnd(MF)), DestReg: getSPReg(MF))
335 .addReg(RegNo: getSPReg(MF))
336 .addReg(RegNo: BitmaskReg);
337 }
338 if (hasFP(MF)) {
339 // Unlike most conventional targets (where FP points to the saved FP),
340 // FP points to the bottom of the fixed-size locals, so we can use positive
341 // offsets in load/store instructions.
342 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: WebAssembly::COPY), DestReg: getFPReg(MF))
343 .addReg(RegNo: getSPReg(MF));
344 }
345 if (StackSize && needsSPWriteback(MF)) {
346 writeBackSP(SrcReg: getSPReg(MF), MF, MBB, InsertStore&: InsertPt, DL);
347 }
348}
349
350void WebAssemblyFrameLowering::emitEpilogue(MachineFunction &MF,
351 MachineBasicBlock &MBB) const {
352 uint64_t StackSize = MF.getFrameInfo().getStackSize();
353 if (!needsSP(MF) || !needsSPWriteback(MF))
354 return;
355 auto &ST = MF.getSubtarget<WebAssemblySubtarget>();
356 const auto *TII = ST.getInstrInfo();
357 auto &MRI = MF.getRegInfo();
358 auto InsertPt = MBB.getFirstTerminator();
359 DebugLoc DL;
360
361 if (InsertPt != MBB.end())
362 DL = InsertPt->getDebugLoc();
363
364 // Restore the stack pointer. If we had fixed-size locals, add the offset
365 // subtracted in the prolog.
366 unsigned SPReg = 0;
367 unsigned SPFPReg = hasFP(MF) ? getFPReg(MF) : getSPReg(MF);
368 if (hasBP(MF)) {
369 auto FI = MF.getInfo<WebAssemblyFunctionInfo>();
370 SPReg = FI->getBasePointerVreg();
371 } else if (StackSize) {
372 const TargetRegisterClass *PtrRC =
373 TII->getRegClass(MCID: TII->get(Opcode: getOpcConst(MF)), OpNum: 0);
374 Register OffsetReg = MRI.createVirtualRegister(RegClass: PtrRC);
375 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: getOpcConst(MF)), DestReg: OffsetReg)
376 .addImm(Val: StackSize);
377 // In the epilog we don't need to write the result back to the SP32/64
378 // physreg because it won't be used again. We can use a stackified register
379 // instead.
380 SPReg = MRI.createVirtualRegister(RegClass: PtrRC);
381 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: getOpcAdd(MF)), DestReg: SPReg)
382 .addReg(RegNo: SPFPReg)
383 .addReg(RegNo: OffsetReg);
384 } else {
385 SPReg = SPFPReg;
386 }
387
388 writeBackSP(SrcReg: SPReg, MF, MBB, InsertStore&: InsertPt, DL);
389}
390
391bool WebAssemblyFrameLowering::isSupportedStackID(
392 TargetStackID::Value ID) const {
393 // Use the Object stack for WebAssembly locals which can only be accessed
394 // by name, not via an address in linear memory.
395 if (ID == TargetStackID::WasmLocal)
396 return true;
397
398 return TargetFrameLowering::isSupportedStackID(ID);
399}
400
401TargetFrameLowering::DwarfFrameBase
402WebAssemblyFrameLowering::getDwarfFrameBase(const MachineFunction &MF) const {
403 DwarfFrameBase Loc;
404 Loc.Kind = DwarfFrameBase::WasmFrameBase;
405 const WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
406 if (needsSP(MF) && MFI.isFrameBaseVirtual()) {
407 unsigned LocalNum = MFI.getFrameBaseLocal();
408 Loc.Location.WasmLoc = {.Kind: WebAssembly::TI_LOCAL, .Index: LocalNum};
409 } else {
410 // There is no __stack_pointer global in libcall thread context mode, so
411 // TI_GLOBAL_RELOC would produce a bogus relocation. We take care to ensure
412 // that this code is not reached in that case, but assert here to be sure.
413 assert(!MF.getSubtarget<WebAssemblySubtarget>().hasLibcallThreadContext());
414
415 // The __stack_pointer global holds only the innermost frame's stack
416 // pointer, so this frame base is correct only for the innermost frame.
417 // TODO: Describe outer frames, which need a per-frame stack pointer value.
418 Loc.Location.WasmLoc = {.Kind: WebAssembly::TI_GLOBAL_RELOC, .Index: 0};
419 }
420 return Loc;
421}
422