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 static_cast<unsigned>(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 return MFI.getStackSize() || MFI.adjustsStack() || hasFP(MF) ||
139 HasExplicitSPUse;
140}
141
142// In function with EH pads, we need to make a copy of the value of
143// __stack_pointer global in SP32/64 register, in order to use it when
144// restoring __stack_pointer after an exception is caught.
145bool WebAssemblyFrameLowering::needsPrologForEH(
146 const MachineFunction &MF) const {
147 auto EHType = MF.getTarget().getMCAsmInfo()->getExceptionHandlingType();
148 return EHType == ExceptionHandling::Wasm &&
149 MF.getFunction().hasPersonalityFn() && MF.getFrameInfo().hasCalls();
150}
151
152/// Returns true if this function needs a local user-space stack pointer.
153/// Unlike a machine stack pointer, the wasm user stack pointer is a global
154/// variable, so it is loaded into a register in the prolog.
155bool WebAssemblyFrameLowering::needsSP(const MachineFunction &MF) const {
156 return needsSPForLocalFrame(MF) || needsPrologForEH(MF);
157}
158
159/// Returns true if the local user-space stack pointer needs to be written back
160/// to __stack_pointer global by this function (this is not meaningful if
161/// needsSP is false). If false, the stack red zone can be used and only a local
162/// SP is needed.
163bool WebAssemblyFrameLowering::needsSPWriteback(
164 const MachineFunction &MF) const {
165 auto &MFI = MF.getFrameInfo();
166 assert(needsSP(MF));
167 // When we don't need a local stack pointer for its local frame but only to
168 // support EH, we don't need to write SP back in the epilog, because we don't
169 // bump down the stack pointer in the prolog. We need to write SP back in the
170 // epilog only if
171 // 1. We need SP not only for EH support but also because we actually use
172 // stack or we have a frame address taken.
173 // 2. We cannot use the red zone.
174 bool CanUseRedZone = MFI.getStackSize() <= RedZoneSize && !MFI.hasCalls() &&
175 !MF.getFunction().hasFnAttribute(Kind: Attribute::NoRedZone);
176 return needsSPForLocalFrame(MF) && !CanUseRedZone;
177}
178
179unsigned WebAssemblyFrameLowering::getSPReg(const MachineFunction &MF) {
180 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64()
181 ? WebAssembly::SP64
182 : WebAssembly::SP32;
183}
184
185unsigned WebAssemblyFrameLowering::getFPReg(const MachineFunction &MF) {
186 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64()
187 ? WebAssembly::FP64
188 : WebAssembly::FP32;
189}
190
191unsigned
192WebAssemblyFrameLowering::getOpcConst(const MachineFunction &MF) {
193 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64()
194 ? WebAssembly::CONST_I64
195 : WebAssembly::CONST_I32;
196}
197
198unsigned WebAssemblyFrameLowering::getOpcAdd(const MachineFunction &MF) {
199 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64()
200 ? WebAssembly::ADD_I64
201 : WebAssembly::ADD_I32;
202}
203
204unsigned WebAssemblyFrameLowering::getOpcSub(const MachineFunction &MF) {
205 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64()
206 ? WebAssembly::SUB_I64
207 : WebAssembly::SUB_I32;
208}
209
210unsigned WebAssemblyFrameLowering::getOpcAnd(const MachineFunction &MF) {
211 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64()
212 ? WebAssembly::AND_I64
213 : WebAssembly::AND_I32;
214}
215
216unsigned
217WebAssemblyFrameLowering::getOpcGlobGet(const MachineFunction &MF) {
218 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64()
219 ? WebAssembly::GLOBAL_GET_I64
220 : WebAssembly::GLOBAL_GET_I32;
221}
222
223unsigned
224WebAssemblyFrameLowering::getOpcGlobSet(const MachineFunction &MF) {
225 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64()
226 ? WebAssembly::GLOBAL_SET_I64
227 : WebAssembly::GLOBAL_SET_I32;
228}
229
230void WebAssemblyFrameLowering::writeSPToGlobal(
231 unsigned SrcReg, MachineFunction &MF, MachineBasicBlock &MBB,
232 MachineBasicBlock::iterator &InsertStore, const DebugLoc &DL) const {
233 const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
234
235 const char *ES = "__stack_pointer";
236 auto *SPSymbol = MF.createExternalSymbolName(Name: ES);
237
238 BuildMI(BB&: MBB, I: InsertStore, MIMD: DL, MCID: TII->get(Opcode: getOpcGlobSet(MF)))
239 .addExternalSymbol(FnName: SPSymbol)
240 .addReg(RegNo: SrcReg);
241}
242
243MachineBasicBlock::iterator
244WebAssemblyFrameLowering::eliminateCallFramePseudoInstr(
245 MachineFunction &MF, MachineBasicBlock &MBB,
246 MachineBasicBlock::iterator I) const {
247 assert(!I->getOperand(0).getImm() && (hasFP(MF) || hasBP(MF)) &&
248 "Call frame pseudos should only be used for dynamic stack adjustment");
249 auto &ST = MF.getSubtarget<WebAssemblySubtarget>();
250 const auto *TII = ST.getInstrInfo();
251 if (I->getOpcode() == TII->getCallFrameDestroyOpcode() &&
252 needsSPWriteback(MF)) {
253 DebugLoc DL = I->getDebugLoc();
254 writeSPToGlobal(SrcReg: getSPReg(MF), MF, MBB, InsertStore&: I, DL);
255 }
256 return MBB.erase(I);
257}
258
259void WebAssemblyFrameLowering::emitPrologue(MachineFunction &MF,
260 MachineBasicBlock &MBB) const {
261 // TODO: Do ".setMIFlag(MachineInstr::FrameSetup)" on emitted instructions
262 auto &MFI = MF.getFrameInfo();
263 assert(MFI.getCalleeSavedInfo().empty() &&
264 "WebAssembly should not have callee-saved registers");
265
266 if (!needsSP(MF))
267 return;
268 uint64_t StackSize = MFI.getStackSize();
269
270 auto &ST = MF.getSubtarget<WebAssemblySubtarget>();
271 const auto *TII = ST.getInstrInfo();
272 auto &MRI = MF.getRegInfo();
273
274 auto InsertPt = MBB.begin();
275 while (InsertPt != MBB.end() &&
276 WebAssembly::isArgument(Opc: InsertPt->getOpcode()))
277 ++InsertPt;
278 DebugLoc DL;
279
280 const TargetRegisterClass *PtrRC =
281 MRI.getTargetRegisterInfo()->getPointerRegClass(MF);
282 unsigned SPReg = getSPReg(MF);
283 if (StackSize)
284 SPReg = MRI.createVirtualRegister(RegClass: PtrRC);
285
286 const char *ES = "__stack_pointer";
287 auto *SPSymbol = MF.createExternalSymbolName(Name: ES);
288 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: getOpcGlobGet(MF)), DestReg: SPReg)
289 .addExternalSymbol(FnName: SPSymbol);
290
291 bool HasBP = hasBP(MF);
292 if (HasBP) {
293 auto FI = MF.getInfo<WebAssemblyFunctionInfo>();
294 Register BasePtr = MRI.createVirtualRegister(RegClass: PtrRC);
295 FI->setBasePointerVreg(BasePtr);
296 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: WebAssembly::COPY), DestReg: BasePtr)
297 .addReg(RegNo: SPReg);
298 }
299 if (StackSize) {
300 // Subtract the frame size
301 Register OffsetReg = MRI.createVirtualRegister(RegClass: PtrRC);
302 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: getOpcConst(MF)), DestReg: OffsetReg)
303 .addImm(Val: StackSize);
304 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: getOpcSub(MF)), DestReg: getSPReg(MF))
305 .addReg(RegNo: SPReg)
306 .addReg(RegNo: OffsetReg);
307 }
308 if (HasBP) {
309 Register BitmaskReg = MRI.createVirtualRegister(RegClass: PtrRC);
310 Align Alignment = MFI.getMaxAlign();
311 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: getOpcConst(MF)), DestReg: BitmaskReg)
312 .addImm(Val: (int64_t) ~(Alignment.value() - 1));
313 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: getOpcAnd(MF)), DestReg: getSPReg(MF))
314 .addReg(RegNo: getSPReg(MF))
315 .addReg(RegNo: BitmaskReg);
316 }
317 if (hasFP(MF)) {
318 // Unlike most conventional targets (where FP points to the saved FP),
319 // FP points to the bottom of the fixed-size locals, so we can use positive
320 // offsets in load/store instructions.
321 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: WebAssembly::COPY), DestReg: getFPReg(MF))
322 .addReg(RegNo: getSPReg(MF));
323 }
324 if (StackSize && needsSPWriteback(MF)) {
325 writeSPToGlobal(SrcReg: getSPReg(MF), MF, MBB, InsertStore&: InsertPt, DL);
326 }
327}
328
329void WebAssemblyFrameLowering::emitEpilogue(MachineFunction &MF,
330 MachineBasicBlock &MBB) const {
331 uint64_t StackSize = MF.getFrameInfo().getStackSize();
332 if (!needsSP(MF) || !needsSPWriteback(MF))
333 return;
334 auto &ST = MF.getSubtarget<WebAssemblySubtarget>();
335 const auto *TII = ST.getInstrInfo();
336 auto &MRI = MF.getRegInfo();
337 auto InsertPt = MBB.getFirstTerminator();
338 DebugLoc DL;
339
340 if (InsertPt != MBB.end())
341 DL = InsertPt->getDebugLoc();
342
343 // Restore the stack pointer. If we had fixed-size locals, add the offset
344 // subtracted in the prolog.
345 unsigned SPReg = 0;
346 unsigned SPFPReg = hasFP(MF) ? getFPReg(MF) : getSPReg(MF);
347 if (hasBP(MF)) {
348 auto FI = MF.getInfo<WebAssemblyFunctionInfo>();
349 SPReg = FI->getBasePointerVreg();
350 } else if (StackSize) {
351 const TargetRegisterClass *PtrRC =
352 MRI.getTargetRegisterInfo()->getPointerRegClass(MF);
353 Register OffsetReg = MRI.createVirtualRegister(RegClass: PtrRC);
354 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: getOpcConst(MF)), DestReg: OffsetReg)
355 .addImm(Val: StackSize);
356 // In the epilog we don't need to write the result back to the SP32/64
357 // physreg because it won't be used again. We can use a stackified register
358 // instead.
359 SPReg = MRI.createVirtualRegister(RegClass: PtrRC);
360 BuildMI(BB&: MBB, I: InsertPt, MIMD: DL, MCID: TII->get(Opcode: getOpcAdd(MF)), DestReg: SPReg)
361 .addReg(RegNo: SPFPReg)
362 .addReg(RegNo: OffsetReg);
363 } else {
364 SPReg = SPFPReg;
365 }
366
367 writeSPToGlobal(SrcReg: SPReg, MF, MBB, InsertStore&: InsertPt, DL);
368}
369
370bool WebAssemblyFrameLowering::isSupportedStackID(
371 TargetStackID::Value ID) const {
372 // Use the Object stack for WebAssembly locals which can only be accessed
373 // by name, not via an address in linear memory.
374 if (ID == TargetStackID::WasmLocal)
375 return true;
376
377 return TargetFrameLowering::isSupportedStackID(ID);
378}
379
380TargetFrameLowering::DwarfFrameBase
381WebAssemblyFrameLowering::getDwarfFrameBase(const MachineFunction &MF) const {
382 DwarfFrameBase Loc;
383 Loc.Kind = DwarfFrameBase::WasmFrameBase;
384 const WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
385 if (needsSP(MF) && MFI.isFrameBaseVirtual()) {
386 unsigned LocalNum = MFI.getFrameBaseLocal();
387 Loc.Location.WasmLoc = {.Kind: WebAssembly::TI_LOCAL, .Index: LocalNum};
388 } else {
389 // TODO: This should work on a breakpoint at a function with no frame,
390 // but probably won't work for traversing up the stack.
391 Loc.Location.WasmLoc = {.Kind: WebAssembly::TI_GLOBAL_RELOC, .Index: 0};
392 }
393 return Loc;
394}
395