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