1 //===-- WebAssemblyFrameLowering.cpp - WebAssembly Frame Lowering ----------==//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// \brief This file contains the WebAssembly implementation of
12 /// TargetFrameLowering class.
13 ///
14 /// On WebAssembly, there aren't a lot of things to do here. There are no
15 /// callee-saved registers to save, and no spill slots.
16 ///
17 /// The stack grows downward.
18 ///
19 //===----------------------------------------------------------------------===//
20 
21 #include "WebAssemblyFrameLowering.h"
22 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
23 #include "WebAssemblyInstrInfo.h"
24 #include "WebAssemblyMachineFunctionInfo.h"
25 #include "WebAssemblySubtarget.h"
26 #include "WebAssemblyTargetMachine.h"
27 #include "WebAssemblyUtilities.h"
28 #include "llvm/CodeGen/MachineFrameInfo.h"
29 #include "llvm/CodeGen/MachineFunction.h"
30 #include "llvm/CodeGen/MachineInstrBuilder.h"
31 #include "llvm/CodeGen/MachineModuleInfoImpls.h"
32 #include "llvm/CodeGen/MachineRegisterInfo.h"
33 #include "llvm/Support/Debug.h"
34 using namespace llvm;
35 
36 #define DEBUG_TYPE "wasm-frame-info"
37 
38 // TODO: wasm64
39 // TODO: Emit TargetOpcode::CFI_INSTRUCTION instructions
40 
41 /// We need a base pointer in the case of having items on the stack that
42 /// require stricter alignment than the stack pointer itself.  Because we need
43 /// to shift the stack pointer by some unknown amount to force the alignment,
44 /// we need to record the value of the stack pointer on entry to the function.
45 bool WebAssemblyFrameLowering::hasBP(
46     const MachineFunction &MF) const {
47   const auto *RegInfo =
48       MF.getSubtarget<WebAssemblySubtarget>().getRegisterInfo();
49   return RegInfo->needsStackRealignment(MF);
50 }
51 
52 /// Return true if the specified function should have a dedicated frame pointer
53 /// register.
54 bool WebAssemblyFrameLowering::hasFP(const MachineFunction &MF) const {
55   const MachineFrameInfo &MFI = MF.getFrameInfo();
56 
57   // When we have var-sized objects, we move the stack pointer by an unknown
58   // amount, and need to emit a frame pointer to restore the stack to where we
59   // were on function entry.
60   // If we already need a base pointer, we use that to fix up the stack pointer.
61   // If there are no fixed-size objects, we would have no use of a frame
62   // pointer, and thus should not emit one.
63   bool HasFixedSizedObjects = MFI.getStackSize() > 0;
64   bool NeedsFixedReference = !hasBP(MF) || HasFixedSizedObjects;
65 
66   return MFI.isFrameAddressTaken() ||
67          (MFI.hasVarSizedObjects() && NeedsFixedReference) ||
68          MFI.hasStackMap() || MFI.hasPatchPoint();
69 }
70 
71 /// Under normal circumstances, when a frame pointer is not required, we reserve
72 /// argument space for call sites in the function immediately on entry to the
73 /// current function. This eliminates the need for add/sub sp brackets around
74 /// call sites. Returns true if the call frame is included as part of the stack
75 /// frame.
76 bool WebAssemblyFrameLowering::hasReservedCallFrame(
77     const MachineFunction &MF) const {
78   return !MF.getFrameInfo().hasVarSizedObjects();
79 }
80 
81 
82 /// Returns true if this function needs a local user-space stack pointer.
83 /// Unlike a machine stack pointer, the wasm user stack pointer is a global
84 /// variable, so it is loaded into a register in the prolog.
85 bool WebAssemblyFrameLowering::needsSP(const MachineFunction &MF,
86                                        const MachineFrameInfo &MFI) const {
87   return MFI.getStackSize() || MFI.adjustsStack() || hasFP(MF);
88 }
89 
90 /// Returns true if the local user-space stack pointer needs to be written back
91 /// to memory by this function (this is not meaningful if needsSP is false). If
92 /// false, the stack red zone can be used and only a local SP is needed.
93 bool WebAssemblyFrameLowering::needsSPWriteback(
94     const MachineFunction &MF, const MachineFrameInfo &MFI) const {
95   assert(needsSP(MF, MFI));
96   return MFI.getStackSize() > RedZoneSize || MFI.hasCalls() ||
97          MF.getFunction()->hasFnAttribute(Attribute::NoRedZone);
98 }
99 
100 static void writeSPToMemory(unsigned SrcReg, MachineFunction &MF,
101                             MachineBasicBlock &MBB,
102                             MachineBasicBlock::iterator &InsertAddr,
103                             MachineBasicBlock::iterator &InsertStore,
104                             const DebugLoc &DL) {
105   const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
106 
107   if (MF.getSubtarget<WebAssemblySubtarget>()
108         .getTargetTriple().isOSBinFormatELF()) {
109     const char *ES = "__stack_pointer";
110     auto *SPSymbol = MF.createExternalSymbolName(ES);
111     MachineRegisterInfo &MRI = MF.getRegInfo();
112     const TargetRegisterClass *PtrRC =
113         MRI.getTargetRegisterInfo()->getPointerRegClass(MF);
114     unsigned Zero = MRI.createVirtualRegister(PtrRC);
115 
116     BuildMI(MBB, InsertAddr, DL, TII->get(WebAssembly::CONST_I32), Zero)
117         .addImm(0);
118     MachineMemOperand *MMO = MF.getMachineMemOperand(
119         MachinePointerInfo(MF.getPSVManager().getExternalSymbolCallEntry(ES)),
120         MachineMemOperand::MOStore, 4, 4);
121     BuildMI(MBB, InsertStore, DL, TII->get(WebAssembly::STORE_I32))
122         .addImm(2)  // p2align
123         .addExternalSymbol(SPSymbol)
124         .addReg(Zero)
125         .addReg(SrcReg)
126         .addMemOperand(MMO);
127   } else {
128     MachineModuleInfoWasm &MMIW =
129         MF.getMMI().getObjFileInfo<MachineModuleInfoWasm>();
130     BuildMI(MBB, InsertStore, DL, TII->get(WebAssembly::SET_GLOBAL_I32))
131         .addImm(MMIW.getStackPointerGlobal())
132         .addReg(SrcReg);
133   }
134 }
135 
136 MachineBasicBlock::iterator
137 WebAssemblyFrameLowering::eliminateCallFramePseudoInstr(
138     MachineFunction &MF, MachineBasicBlock &MBB,
139     MachineBasicBlock::iterator I) const {
140   assert(!I->getOperand(0).getImm() && (hasFP(MF) || hasBP(MF)) &&
141          "Call frame pseudos should only be used for dynamic stack adjustment");
142   const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
143   if (I->getOpcode() == TII->getCallFrameDestroyOpcode() &&
144       needsSPWriteback(MF, MF.getFrameInfo())) {
145     DebugLoc DL = I->getDebugLoc();
146     writeSPToMemory(WebAssembly::SP32, MF, MBB, I, I, DL);
147   }
148   return MBB.erase(I);
149 }
150 
151 void WebAssemblyFrameLowering::emitPrologue(MachineFunction &MF,
152                                             MachineBasicBlock &MBB) const {
153   // TODO: Do ".setMIFlag(MachineInstr::FrameSetup)" on emitted instructions
154   auto &MFI = MF.getFrameInfo();
155   assert(MFI.getCalleeSavedInfo().empty() &&
156          "WebAssembly should not have callee-saved registers");
157 
158   if (!needsSP(MF, MFI)) return;
159   uint64_t StackSize = MFI.getStackSize();
160 
161   const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
162   auto &MRI = MF.getRegInfo();
163 
164   auto InsertPt = MBB.begin();
165   while (InsertPt != MBB.end() && WebAssembly::isArgument(*InsertPt))
166     ++InsertPt;
167   DebugLoc DL;
168 
169   const TargetRegisterClass *PtrRC =
170       MRI.getTargetRegisterInfo()->getPointerRegClass(MF);
171   unsigned SPReg = WebAssembly::SP32;
172   if (StackSize)
173     SPReg = MRI.createVirtualRegister(PtrRC);
174   if (MF.getSubtarget<WebAssemblySubtarget>()
175         .getTargetTriple().isOSBinFormatELF()) {
176     const char *ES = "__stack_pointer";
177     auto *SPSymbol = MF.createExternalSymbolName(ES);
178     unsigned Zero = MRI.createVirtualRegister(PtrRC);
179 
180     BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::CONST_I32), Zero)
181         .addImm(0);
182     MachineMemOperand *LoadMMO = MF.getMachineMemOperand(
183         MachinePointerInfo(MF.getPSVManager().getExternalSymbolCallEntry(ES)),
184         MachineMemOperand::MOLoad, 4, 4);
185     // Load the SP value.
186     BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::LOAD_I32), SPReg)
187         .addImm(2)       // p2align
188         .addExternalSymbol(SPSymbol)
189         .addReg(Zero)    // addr
190         .addMemOperand(LoadMMO);
191   } else {
192     auto &MMIW = MF.getMMI().getObjFileInfo<MachineModuleInfoWasm>();
193     if (!MMIW.hasStackPointerGlobal()) {
194       MMIW.setStackPointerGlobal(MMIW.getGlobals().size());
195       MMIW.addGlobal(MVT::i32);
196     }
197     BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::GET_GLOBAL_I32), SPReg)
198         .addImm(MMIW.getStackPointerGlobal());
199   }
200 
201   bool HasBP = hasBP(MF);
202   if (HasBP) {
203     auto FI = MF.getInfo<WebAssemblyFunctionInfo>();
204     unsigned BasePtr = MRI.createVirtualRegister(PtrRC);
205     FI->setBasePointerVreg(BasePtr);
206     BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::COPY), BasePtr)
207         .addReg(SPReg);
208   }
209   if (StackSize) {
210     // Subtract the frame size
211     unsigned OffsetReg = MRI.createVirtualRegister(PtrRC);
212     BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::CONST_I32), OffsetReg)
213         .addImm(StackSize);
214     BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::SUB_I32),
215             WebAssembly::SP32)
216         .addReg(SPReg)
217         .addReg(OffsetReg);
218   }
219   if (HasBP) {
220     unsigned BitmaskReg = MRI.createVirtualRegister(PtrRC);
221     unsigned Alignment = MFI.getMaxAlignment();
222     assert((1u << countTrailingZeros(Alignment)) == Alignment &&
223       "Alignment must be a power of 2");
224     BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::CONST_I32), BitmaskReg)
225         .addImm((int)~(Alignment - 1));
226     BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::AND_I32),
227             WebAssembly::SP32)
228         .addReg(WebAssembly::SP32)
229         .addReg(BitmaskReg);
230   }
231   if (hasFP(MF)) {
232     // Unlike most conventional targets (where FP points to the saved FP),
233     // FP points to the bottom of the fixed-size locals, so we can use positive
234     // offsets in load/store instructions.
235     BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::COPY),
236             WebAssembly::FP32)
237         .addReg(WebAssembly::SP32);
238   }
239   if (StackSize && needsSPWriteback(MF, MFI)) {
240     writeSPToMemory(WebAssembly::SP32, MF, MBB, InsertPt, InsertPt, DL);
241   }
242 }
243 
244 void WebAssemblyFrameLowering::emitEpilogue(MachineFunction &MF,
245                                             MachineBasicBlock &MBB) const {
246   auto &MFI = MF.getFrameInfo();
247   uint64_t StackSize = MFI.getStackSize();
248   if (!needsSP(MF, MFI) || !needsSPWriteback(MF, MFI)) return;
249   const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
250   auto &MRI = MF.getRegInfo();
251   auto InsertPt = MBB.getFirstTerminator();
252   DebugLoc DL;
253 
254   if (InsertPt != MBB.end())
255     DL = InsertPt->getDebugLoc();
256 
257   // Restore the stack pointer. If we had fixed-size locals, add the offset
258   // subtracted in the prolog.
259   unsigned SPReg = 0;
260   MachineBasicBlock::iterator InsertAddr = InsertPt;
261   if (hasBP(MF)) {
262     auto FI = MF.getInfo<WebAssemblyFunctionInfo>();
263     SPReg = FI->getBasePointerVreg();
264   } else if (StackSize) {
265     const TargetRegisterClass *PtrRC =
266         MRI.getTargetRegisterInfo()->getPointerRegClass(MF);
267     unsigned OffsetReg = MRI.createVirtualRegister(PtrRC);
268     InsertAddr =
269         BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::CONST_I32), OffsetReg)
270             .addImm(StackSize);
271     // In the epilog we don't need to write the result back to the SP32 physreg
272     // because it won't be used again. We can use a stackified register instead.
273     SPReg = MRI.createVirtualRegister(PtrRC);
274     BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::ADD_I32), SPReg)
275         .addReg(hasFP(MF) ? WebAssembly::FP32 : WebAssembly::SP32)
276         .addReg(OffsetReg);
277   } else {
278     SPReg = hasFP(MF) ? WebAssembly::FP32 : WebAssembly::SP32;
279   }
280 
281   writeSPToMemory(SPReg, MF, MBB, InsertAddr, InsertPt, DL);
282 }
283