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