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" 35 using 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. 51 std::optional<unsigned> 52 WebAssemblyFrameLowering::getLocalForStackObject(MachineFunction &MF, 53 int FrameIndex) { 54 MachineFrameInfo &MFI = MF.getFrameInfo(); 55 56 // If already hoisted to a local, done. 57 if (MFI.getStackID(FrameIndex) == TargetStackID::WasmLocal) 58 return static_cast<unsigned>(MFI.getObjectOffset(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(FrameIndex); 63 if (!AI || !WebAssembly::isWasmVarAddressSpace(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, MF.getDataLayout(), AI->getAllocatedType(), ValueVTs); 73 MFI.setStackID(FrameIndex, 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(FrameIndex, Local); 77 // Allocate WebAssembly locals for each non-aggregate component of the 78 // allocation. 79 for (EVT ValueVT : ValueVTs) 80 FuncInfo->addLocal(ValueVT.getSimpleVT()); 81 // Abuse object size to record number of WebAssembly locals allocated to 82 // this object. 83 MFI.setObjectSize(FrameIndex, 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. 91 bool 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. 99 bool 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. 121 bool 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). 128 bool 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(MRI.use_operands(getSPReg(MF)), 136 [](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. 145 bool 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. 155 bool 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. 163 bool 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(Attribute::NoRedZone); 176 return needsSPForLocalFrame(MF) && !CanUseRedZone; 177 } 178 179 unsigned WebAssemblyFrameLowering::getSPReg(const MachineFunction &MF) { 180 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64() 181 ? WebAssembly::SP64 182 : WebAssembly::SP32; 183 } 184 185 unsigned WebAssemblyFrameLowering::getFPReg(const MachineFunction &MF) { 186 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64() 187 ? WebAssembly::FP64 188 : WebAssembly::FP32; 189 } 190 191 unsigned 192 WebAssemblyFrameLowering::getOpcConst(const MachineFunction &MF) { 193 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64() 194 ? WebAssembly::CONST_I64 195 : WebAssembly::CONST_I32; 196 } 197 198 unsigned WebAssemblyFrameLowering::getOpcAdd(const MachineFunction &MF) { 199 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64() 200 ? WebAssembly::ADD_I64 201 : WebAssembly::ADD_I32; 202 } 203 204 unsigned WebAssemblyFrameLowering::getOpcSub(const MachineFunction &MF) { 205 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64() 206 ? WebAssembly::SUB_I64 207 : WebAssembly::SUB_I32; 208 } 209 210 unsigned WebAssemblyFrameLowering::getOpcAnd(const MachineFunction &MF) { 211 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64() 212 ? WebAssembly::AND_I64 213 : WebAssembly::AND_I32; 214 } 215 216 unsigned 217 WebAssemblyFrameLowering::getOpcGlobGet(const MachineFunction &MF) { 218 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64() 219 ? WebAssembly::GLOBAL_GET_I64 220 : WebAssembly::GLOBAL_GET_I32; 221 } 222 223 unsigned 224 WebAssemblyFrameLowering::getOpcGlobSet(const MachineFunction &MF) { 225 return MF.getSubtarget<WebAssemblySubtarget>().hasAddr64() 226 ? WebAssembly::GLOBAL_SET_I64 227 : WebAssembly::GLOBAL_SET_I32; 228 } 229 230 void 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(ES); 237 238 BuildMI(MBB, InsertStore, DL, TII->get(getOpcGlobSet(MF))) 239 .addExternalSymbol(SPSymbol) 240 .addReg(SrcReg); 241 } 242 243 MachineBasicBlock::iterator 244 WebAssemblyFrameLowering::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(getSPReg(MF), MF, MBB, I, DL); 255 } 256 return MBB.erase(I); 257 } 258 259 void 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(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(PtrRC); 285 286 const char *ES = "__stack_pointer"; 287 auto *SPSymbol = MF.createExternalSymbolName(ES); 288 BuildMI(MBB, InsertPt, DL, TII->get(getOpcGlobGet(MF)), SPReg) 289 .addExternalSymbol(SPSymbol); 290 291 bool HasBP = hasBP(MF); 292 if (HasBP) { 293 auto FI = MF.getInfo<WebAssemblyFunctionInfo>(); 294 Register BasePtr = MRI.createVirtualRegister(PtrRC); 295 FI->setBasePointerVreg(BasePtr); 296 BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::COPY), BasePtr) 297 .addReg(SPReg); 298 } 299 if (StackSize) { 300 // Subtract the frame size 301 Register OffsetReg = MRI.createVirtualRegister(PtrRC); 302 BuildMI(MBB, InsertPt, DL, TII->get(getOpcConst(MF)), OffsetReg) 303 .addImm(StackSize); 304 BuildMI(MBB, InsertPt, DL, TII->get(getOpcSub(MF)), getSPReg(MF)) 305 .addReg(SPReg) 306 .addReg(OffsetReg); 307 } 308 if (HasBP) { 309 Register BitmaskReg = MRI.createVirtualRegister(PtrRC); 310 Align Alignment = MFI.getMaxAlign(); 311 BuildMI(MBB, InsertPt, DL, TII->get(getOpcConst(MF)), BitmaskReg) 312 .addImm((int64_t) ~(Alignment.value() - 1)); 313 BuildMI(MBB, InsertPt, DL, TII->get(getOpcAnd(MF)), getSPReg(MF)) 314 .addReg(getSPReg(MF)) 315 .addReg(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(MBB, InsertPt, DL, TII->get(WebAssembly::COPY), getFPReg(MF)) 322 .addReg(getSPReg(MF)); 323 } 324 if (StackSize && needsSPWriteback(MF)) { 325 writeSPToGlobal(getSPReg(MF), MF, MBB, InsertPt, DL); 326 } 327 } 328 329 void 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(PtrRC); 354 BuildMI(MBB, InsertPt, DL, TII->get(getOpcConst(MF)), OffsetReg) 355 .addImm(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(PtrRC); 360 BuildMI(MBB, InsertPt, DL, TII->get(getOpcAdd(MF)), SPReg) 361 .addReg(SPFPReg) 362 .addReg(OffsetReg); 363 } else { 364 SPReg = SPFPReg; 365 } 366 367 writeSPToGlobal(SPReg, MF, MBB, InsertPt, DL); 368 } 369 370 bool 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 380 TargetFrameLowering::DwarfFrameBase 381 WebAssemblyFrameLowering::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 = {WebAssembly::TI_LOCAL, 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 = {WebAssembly::TI_GLOBAL_RELOC, 0}; 392 } 393 return Loc; 394 } 395