[WebAssembly] Implement red zone for user stack

[dschuff]

Summary

Implements a mostly-conventional redzone for the userspace
stack. Because we have unsigned load/store offsets we continue to use a
local SP subtracted from the incoming SP but do not write it back to
memory.

[dschuff]

The redzone size of 128 matches some real targets, but unlike those we don't yet have to worry about exception handlers (and in any case they could use another stack). Given that, (and the overflow behavior is the same either way), is there any reason not to make the red zone larger? It seems like infinite size might be bad but not sure what a useful limit would be.

[sunfish]

LGTM. Please add brief description comments for needsSP and needsSPWriteback.

What the size should be is a good question. I think it makes sense to leave it at 128 for now -- big enough to be useful, but not so big that we won't get some test coverage of the non-redzone case in this early phase of development. A TODO comment or so to remind us to go back and revisit this would be good. Perhaps we should start a convention of an "ABI" comment, for things we should re-evaluate before declaring a stable ABI.

llvm/trunk/lib/Target/WebAssembly/WebAssemblyFrameLowering.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_TARGET_WEBASSEMBLY_WEBASSEMBLYFRAMELOWERING_H
 #define LLVM_LIB_TARGET_WEBASSEMBLY_WEBASSEMBLYFRAMELOWERING_H
 
 #include "llvm/Target/TargetFrameLowering.h"
 
 namespace llvm {
+class MachineFrameInfo;
 
 class WebAssemblyFrameLowering final : public TargetFrameLowering {
  public:
+  static const size_t RedZoneSize = 128;
+
   WebAssemblyFrameLowering()
       : TargetFrameLowering(StackGrowsDown, /*StackAlignment=*/16,
                             /*LocalAreaOffset=*/0,
                             /*TransientStackAlignment=*/16,
                             /*StackRealignable=*/true) {}
 
   void eliminateCallFramePseudoInstr(
       MachineFunction &MF, MachineBasicBlock &MBB,
       MachineBasicBlock::iterator I) const override;
 
   /// These methods insert prolog and epilog code into the function.
   void emitPrologue(MachineFunction &MF, MachineBasicBlock &MBB) const override;
   void emitEpilogue(MachineFunction &MF, MachineBasicBlock &MBB) const override;
 
   bool hasFP(const MachineFunction &MF) const override;
   bool hasReservedCallFrame(const MachineFunction &MF) const override;
+
+ private:
+  bool needsSP(const MachineFunction &MF, const MachineFrameInfo &MFI) const;
+  bool needsSPWriteback(const MachineFunction &MF,
+                        const MachineFrameInfo &MFI) const;
 };
 
 }  // end namespace llvm
 
 #endif

llvm/trunk/lib/Target/WebAssembly/WebAssemblyFrameLowering.cpp

 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/Debug.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "wasm-frame-info"
 
-// TODO: Implement a red zone?
 // TODO: wasm64
 // TODO: Emit TargetOpcode::CFI_INSTRUCTION instructions
 
 /// Return true if the specified function should have a dedicated frame pointer
 /// register.
 bool WebAssemblyFrameLowering::hasFP(const MachineFunction &MF) const {
   const MachineFrameInfo *MFI = MF.getFrameInfo();
   const auto *RegInfo =
       MF.getSubtarget<WebAssemblySubtarget>().getRegisterInfo();
   return MFI->isFrameAddressTaken() || MFI->hasVarSizedObjects() ||
          MFI->hasStackMap() || MFI->hasPatchPoint() ||
          RegInfo->needsStackRealignment(MF);
 }
 
 /// Under normal circumstances, when a frame pointer is not required, we reserve
 /// argument space for call sites in the function immediately on entry to the
 /// current function. This eliminates the need for add/sub sp brackets around
 /// call sites. Returns true if the call frame is included as part of the stack
 /// frame.
 bool WebAssemblyFrameLowering::hasReservedCallFrame(
     const MachineFunction &MF) const {
   return !MF.getFrameInfo()->hasVarSizedObjects();
 }
 
+
+/// Returns true if this function needs a local user-space stack pointer.
+/// Unlike a machine stack pointer, the wasm user stack pointer is a global
+/// variable, so it is loaded into a register in the prolog.
+bool WebAssemblyFrameLowering::needsSP(const MachineFunction &MF,
+                                       const MachineFrameInfo &MFI) const {
+  return MFI.getStackSize() || MFI.adjustsStack() || hasFP(MF);
+}
+
+/// Returns true if the local user-space stack pointer needs to be written back
+/// to memory by this function (this is not meaningful if needsSP is false). If
+/// false, the stack red zone can be used and only a local SP is needed.
+bool WebAssemblyFrameLowering::needsSPWriteback(
+    const MachineFunction &MF, const MachineFrameInfo &MFI) const {
+  return MFI.getStackSize() > RedZoneSize || MFI.hasCalls() ||
+         MF.getFunction()->hasFnAttribute(Attribute::NoRedZone);
+}
+
 static void writeSPToMemory(unsigned SrcReg, MachineFunction &MF,
                             MachineBasicBlock &MBB,
                             MachineBasicBlock::iterator &InsertPt,
                             DebugLoc DL) {
   auto *SPSymbol = MF.createExternalSymbolName("__stack_pointer");
   unsigned SPAddr =
       MF.getRegInfo().createVirtualRegister(&WebAssembly::I32RegClass);
   const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();

 }
 
 void WebAssemblyFrameLowering::eliminateCallFramePseudoInstr(
     MachineFunction &MF, MachineBasicBlock &MBB,
     MachineBasicBlock::iterator I) const {
   assert(!I->getOperand(0).getImm() && hasFP(MF) &&
          "Call frame pseudos should only be used for dynamic stack adjustment");
   const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
-  if (I->getOpcode() == TII->getCallFrameDestroyOpcode()) {
+  if (I->getOpcode() == TII->getCallFrameDestroyOpcode() &&
+      needsSPWriteback(MF, *MF.getFrameInfo())) {
     DebugLoc DL = I->getDebugLoc();
     writeSPToMemory(WebAssembly::SP32, MF, MBB, I, DL);
   }
   MBB.erase(I);
 }
 
 void WebAssemblyFrameLowering::emitPrologue(MachineFunction &MF,
                                             MachineBasicBlock &MBB) const {
   // TODO: Do ".setMIFlag(MachineInstr::FrameSetup)" on emitted instructions
   auto *MFI = MF.getFrameInfo();
   assert(MFI->getCalleeSavedInfo().empty() &&
          "WebAssembly should not have callee-saved registers");
   auto *WFI = MF.getInfo<WebAssemblyFunctionInfo>();
 
+  if (!needsSP(MF, *MFI)) return;
   uint64_t StackSize = MFI->getStackSize();
-  if (!StackSize && !MFI->adjustsStack() && !hasFP(MF)) return;
 
   const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
   auto &MRI = MF.getRegInfo();
 
   auto InsertPt = MBB.begin();
   DebugLoc DL;
 
   unsigned SPAddr = MRI.createVirtualRegister(&WebAssembly::I32RegClass);
void WebAssemblyFrameLowering::emitPrologue(MachineFunction &MF,
   if (hasFP(MF)) {
     // Unlike most conventional targets (where FP points to the saved FP),
     // FP points to the bottom of the fixed-size locals, so we can use positive
     // offsets in load/store instructions.
     BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::COPY_LOCAL_I32),
             WebAssembly::FP32)
         .addReg(WebAssembly::SP32);
   }
-  if (StackSize) {
+  if (StackSize && needsSPWriteback(MF, *MFI)) {
     writeSPToMemory(WebAssembly::SP32, MF, MBB, InsertPt, DL);
   }
 }
 
 void WebAssemblyFrameLowering::emitEpilogue(MachineFunction &MF,
                                             MachineBasicBlock &MBB) const {
   auto *MFI = MF.getFrameInfo();
   uint64_t StackSize = MFI->getStackSize();
-  if (!StackSize && !MFI->adjustsStack() && !hasFP(MF)) return;
+  if (!needsSP(MF, *MFI) || !needsSPWriteback(MF, *MFI)) return;
   auto *WFI = MF.getInfo<WebAssemblyFunctionInfo>();
   const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
   auto &MRI = MF.getRegInfo();
   auto InsertPt = MBB.getFirstTerminator();
   DebugLoc DL;
 
   if (InsertPt != MBB.end()) {
     DL = InsertPt->getDebugLoc();

llvm/trunk/test/CodeGen/WebAssembly/userstack.ll

 ; RUN: llc < %s -asm-verbose=false | FileCheck %s
 ; RUN: llc < %s -asm-verbose=false -fast-isel | FileCheck %s
 
 
 target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
 target triple = "wasm32-unknown-unknown"
 
+declare void @ext_func(i64* %ptr)
+declare void @ext_func_i32(i32* %ptr)
+
 ; CHECK-LABEL: alloca32:
 ; Check that there is an extra local for the stack pointer.
 ; CHECK: .local i32{{$}}
-define void @alloca32() {
+define void @alloca32() noredzone {
  ; CHECK: i32.const $push[[L1:.+]]=, __stack_pointer{{$}}
  ; CHECK-NEXT: i32.load $push[[L2:.+]]=, 0($pop[[L1]])
  ; CHECK-NEXT: i32.const $push[[L3:.+]]=, 16
  ; CHECK-NEXT: i32.sub [[SP:.+]]=, $pop[[L2]], $pop[[L3]]
  ; CHECK-NEXT: i32.const $push[[L4:.+]]=, __stack_pointer{{$}}
  ; CHECK-NEXT: i32.store $discard=, 0($pop[[L4]]), [[SP]]
  %retval = alloca i32
  ; CHECK: i32.const $push[[L0:.+]]=, 0
  ; CHECK: i32.store {{.*}}=, 12([[SP]]), $pop[[L0]]
  store i32 0, i32* %retval
  ; CHECK: i32.const $push[[L5:.+]]=, 16
  ; CHECK-NEXT: i32.add [[SP]]=, [[SP]], $pop[[L5]]
  ; CHECK-NEXT: i32.const $push[[L6:.+]]=, __stack_pointer
  ; CHECK-NEXT: i32.store $discard=, 0($pop[[L6]]), [[SP]]
  ret void
 }
 
 ; CHECK-LABEL: alloca3264:
 ; CHECK: .local i32{{$}}
 define void @alloca3264() {
  ; CHECK: i32.const $push[[L1:.+]]=, __stack_pointer
  ; CHECK-NEXT: i32.load $push[[L2:.+]]=, 0($pop[[L1]])
  ; CHECK-NEXT: i32.const $push[[L3:.+]]=, 16
  ; CHECK-NEXT: i32.sub [[SP:.+]]=, $pop[[L2]], $pop[[L3]]
- ; CHECK-NEXT: i32.const $push[[L4:.+]]=, __stack_pointer{{$}}
- ; CHECK-NEXT: i32.store $discard=, 0($pop[[L4]]), [[SP]]
  %r1 = alloca i32
  %r2 = alloca double
- ; CHECK: i32.const $push[[L3:.+]]=, 0
- ; CHECK: i32.store {{.*}}=, 12([[SP]]), $pop[[L3]]
+ ; CHECK-NEXT: i32.const $push[[L3:.+]]=, 0
+ ; CHECK-NEXT: i32.store {{.*}}=, 12([[SP]]), $pop[[L3]]
  store i32 0, i32* %r1
- ; CHECK: i64.const $push[[L0:.+]]=, 0
- ; CHECK: i64.store {{.*}}=, 0([[SP]]), $pop[[L0]]
+ ; CHECK-NEXT: i64.const $push[[L0:.+]]=, 0
+ ; CHECK-NEXT: i64.store {{.*}}=, 0([[SP]]), $pop[[L0]]
  store double 0.0, double* %r2
- ; CHECK: i32.const $push[[L5:.+]]=, 16
- ; CHECK-NEXT: i32.add [[SP]]=, [[SP]], $pop[[L5]]
- ; CHECK-NEXT: i32.const $push[[L6:.+]]=, __stack_pointer
- ; CHECK-NEXT: i32.store $discard=, 0($pop[[L6]]), [[SP]]
+ ; CHECK-NEXT: return
  ret void
 }
 
 ; CHECK-LABEL: allocarray:
 ; CHECK: .local i32, i32{{$}}
 define void @allocarray() {
  ; CHECK: i32.const $push[[L1:.+]]=, __stack_pointer
  ; CHECK-NEXT: i32.load $push[[L2:.+]]=, 0($pop[[L1]])
- ; CHECK-NEXT: i32.const $push[[L3:.+]]=, 32{{$}}
+ ; CHECK-NEXT: i32.const $push[[L3:.+]]=, 144{{$}}
  ; CHECK-NEXT: i32.sub [[SP:.+]]=, $pop[[L2]], $pop[[L3]]
  ; CHECK-NEXT: i32.const $push[[L4:.+]]=, __stack_pointer{{$}}
  ; CHECK-NEXT: i32.store $discard=, 0($pop[[L4]]), [[SP]]
- %r = alloca [5 x i32]
+ %r = alloca [33 x i32]
 
  ; CHECK-NEXT: i32.const $push[[L4:.+]]=, 12
  ; CHECK-NEXT: i32.const [[L5:.+]]=, 12
  ; CHECK-NEXT: i32.add [[L5]]=, [[SP]], [[L5]]
  ; CHECK-NEXT: i32.add $push[[L6:.+]]=, [[L5]], $pop[[L4]]
  ; CHECK-NEXT: i32.const $push[[L9:.+]]=, 1{{$}}
  ; CHECK-NEXT: i32.store $push[[L10:.+]]=, 12([[SP]]), $pop[[L9]]{{$}}
  ; CHECK-NEXT: i32.store $discard=, 0($pop3), $pop[[L10]]{{$}}
- %p = getelementptr [5 x i32], [5 x i32]* %r, i32 0, i32 0
+ %p = getelementptr [33 x i32], [33 x i32]* %r, i32 0, i32 0
  store i32 1, i32* %p
- %p2 = getelementptr [5 x i32], [5 x i32]* %r, i32 0, i32 3
+ %p2 = getelementptr [33 x i32], [33 x i32]* %r, i32 0, i32 3
  store i32 1, i32* %p2
 
- ; CHECK: i32.const $push[[L11:.+]]=, 32
+ ; CHECK: i32.const $push[[L11:.+]]=, 144
  ; CHECK-NEXT: i32.add [[SP]]=, [[SP]], $pop[[L11]]
  ; CHECK-NEXT: i32.const $push[[L12:.+]]=, __stack_pointer
  ; CHECK-NEXT: i32.store $discard=, 0($pop[[L12]]), [[SP]]
  ret void
 }
 
-declare void @ext_func(i64* %ptr)
 ; CHECK-LABEL: non_mem_use
 define void @non_mem_use(i8** %addr) {
  ; CHECK: i32.const $push[[L1:.+]]=, 48
  ; CHECK-NEXT: i32.sub [[SP:.+]]=, {{.+}}, $pop[[L1]]
  %buf = alloca [27 x i8], align 16
  %r = alloca i64
  %r2 = alloca i64
  ; %r is at SP+8

  ; CHECK: i32.const $push[[L3:.+]]=, 1
  ; CHECK: i32.store {{.*}}=, 12([[SP]]), $pop[[L3]]
  %p = getelementptr inbounds [5 x i32], [5 x i32]* %r, i32 0, i32 0
  store i32 1, i32* %p
  ; This store should have both the GEP and the FI folded into it.
  ; CHECK-NEXT: i32.store {{.*}}=, 24([[SP]]), $pop
  %p2 = getelementptr inbounds [5 x i32], [5 x i32]* %r, i32 0, i32 3
  store i32 1, i32* %p2
+ call void @ext_func(i64* null);
  ; CHECK: i32.const $push[[L5:.+]]=, 32
  ; CHECK-NEXT: i32.add [[SP]]=, [[SP]], $pop[[L5]]
  ; CHECK-NEXT: i32.const $push[[L6:.+]]=, __stack_pointer
  ; CHECK-NEXT: i32.store $discard=, 0($pop[[L6]]), [[SP]]
  ret void
 }
 
 ; CHECK-LABEL: dynamic_alloca:
 define void @dynamic_alloca(i32 %alloc) {
  ; CHECK: i32.const $push[[L1:.+]]=, __stack_pointer
  ; CHECK-NEXT: i32.load [[SP:.+]]=, 0($pop[[L1]])
  ; CHECK-NEXT: copy_local [[FP:.+]]=, [[SP]]
  ; Target independent codegen bumps the stack pointer.
  ; CHECK: i32.sub
  ; CHECK-NEXT: copy_local [[SP]]=,
  ; Check that SP is written back to memory after decrement
  ; CHECK-NEXT: i32.const $push[[L4:.+]]=, __stack_pointer{{$}}
  ; CHECK-NEXT: i32.store $discard=, 0($pop[[L4]]), [[SP]]
  %r = alloca i32, i32 %alloc
  ; Target-independent codegen also calculates the store addr
- store i32 0, i32* %r
+ ; CHECK: call ext_func_i32@FUNCTION
+ call void @ext_func_i32(i32* %r)
  ; CHECK: i32.const $push[[L3:.+]]=, __stack_pointer
  ; CHECK-NEXT: i32.store [[SP]]=, 0($pop[[L3]]), [[FP]]
  ret void
 }
 
+; CHECK-LABEL: dynamic_alloca_redzone:
+define void @dynamic_alloca_redzone(i32 %alloc) {
+ ; CHECK: i32.const $push[[L1:.+]]=, __stack_pointer
+ ; CHECK-NEXT: i32.load [[SP:.+]]=, 0($pop[[L1]])
+ ; CHECK-NEXT: copy_local [[FP:.+]]=, [[SP]]
+ ; Target independent codegen bumps the stack pointer
+ ; CHECK: i32.sub [[R:.+]]=,
+ ; CHECK-NEXT: copy_local [[SP]]=, [[R]]
+ %r = alloca i32, i32 %alloc
+ ; check-next here asserts that SP is not written back.
+ ; CHECK-NEXT: i32.const $push[[ZERO:.+]]=, 0
+ ; CHECK-NEXT: i32.store $discard=, 0([[R]]), $pop[[ZERO]]
+ store i32 0, i32* %r
+ ; CHECK-NEXT: return
+ ret void
+}
+
 ; CHECK-LABEL: dynamic_static_alloca:
-define void @dynamic_static_alloca(i32 %alloc) {
+define void @dynamic_static_alloca(i32 %alloc) noredzone {
  ; Decrement SP in the prolog by the static amount and writeback to memory.
  ; CHECK: i32.const $push[[L1:.+]]=, __stack_pointer
  ; CHECK-NEXT: i32.load $push[[L2:.+]]=, 0($pop[[L1]])
  ; CHECK-NEXT: i32.const $push[[L3:.+]]=, 16
  ; CHECK-NEXT: i32.sub [[SP:.+]]=, $pop[[L2]], $pop[[L3]]
  ; CHECK-NEXT: copy_local [[FP:.+]]=, [[SP]]
  ; CHECK-NEXT: i32.const $push[[L4:.+]]=, __stack_pointer
  ; CHECK-NEXT: i32.store {{.*}}=, 0($pop[[L4]]), [[SP]]

 declare i8* @llvm.frameaddress(i32)
 
 ; Test __builtin_frame_address(0).
 ; CHECK-LABEL: frameaddress_0:
 ; CHECK: i32.const $push[[L1:.+]]=, __stack_pointer
 ; CHECK-NEXT: i32.load [[SP:.+]]=, 0($pop[[L1]])
 ; CHECK-NEXT: copy_local [[FP:.+]]=, [[SP]]
 ; CHECK-NEXT: call use_i8_star@FUNCTION, [[FP]]
-; CHECK-NEXT: i32.const $push[[L6:.+]]=, __stack_pointer
-; CHECK-NEXT: i32.store [[SP]]=, 0($pop[[L6]]), [[FP]]
+; CHEC K-NEXT: i32.const $push[[L6:.+]]=, __stack_pointer
+; CHEC K-NEXT: i32.store [[SP]]=, 0($pop[[L6]]), [[FP]]
 define void @frameaddress_0() {
   %t = call i8* @llvm.frameaddress(i32 0)
   call void @use_i8_star(i8* %t)
   ret void
 }
 
 ; Test __builtin_frame_address(1).