[WebAssembly] Implement prolog/epilog insertion and FrameIndex elimination

[dschuff]

Summary

Use the SP32 physical register as the base for FrameIndex lowering. Update it and the __stack_pointer global var in the prolog and epilog. Extend the mapping of virtual registers to wasm locals to include the physical registers.

Rather than modify the target-independent PrologEpilogInserter (which asserts that there are no virtual registers left) Include a slightly-modified copy for Wasm that does not have this assertion and only clears the virtual registers if scavenging was needed (which of course it isn't for wasm).

[dschuff]

Nevermind, this won't work. I'll just make it an MCSymbol in MI too. hold off on the review

[dschuff]

• Use SP32 as phys reg for FI lowering and update printer to handle it. Make prolog/epilog update SP global var

[dschuff]

In this version the SP32 physical register is used as the base for FrameIndex lowering. It and the @SP global var are updated in the prolog and epilog. An alternative would be just to use an arbitrary virtual register (which would be have to be stashed by the prolog e.g. in WebAssemblyRegisterInfo) but using SP seems easier to understand in the IR and not really any different in the final output.

[sunfish]

I'm still reviewing this, but here are a few initial comments.

lib/Target/WebAssembly/WebAssemblyFrameLowering.cpp

74

We also need a prologue when MFI->adjustsStack(). Can you assert that doesn't happen for now?

84

Instead of using getNamedGlobal on the Module, which requires a declaration in LLVM IR, we can use MF.createExternalSymbolName (and addExternalSymbol below), which creates an ExternalSymbol, which is a very lightweight thing that doesn't require any up-front setup.

Also, "SP" is in the C/C++ user namespace. What do you think about "__stack_pointer"?

110

Can you assert MFI->getCalleeSavedInfo().empty(), just to double-check ourselves?

145

This code doesn't yet set up FP; can you assert !hasFP(MF) for now?

Can you add TODO comments for:

• Do ".setMIFlag(MachineInstr::FrameSetup)" on emitted instructions
• Emit TargetOpcode::CFI_INSTRUCTION instructions

[dschuff]

• Use SP32 as phys reg for FI lowering and update printer to handle it. Make prolog/epilog update SP global var
• Address first round of comments

lib/Target/WebAssembly/WebAssemblyFrameLowering.cpp

84

Done. One consequence is that the MachinePointerInfo no longer has the reference to the stack pointer, but that's probably OK.

145

hasFP() currently includes MFI->hasCalls(), which seems wrong, at least for wasm. I took that out.

Added the former TODO to EmitPrologue and the latter to the top with the other TODOs.

[sunfish]

Looks good.

lib/Target/WebAssembly/WebAssemblyFrameLowering.cpp

84

Ah. This might be a job for PseudoSourceValue::ExternalSymbolCallEntry then. In fact, it looks like it would work to just use that right now; the only odd part is the "Call" in the name, which may be an artifact of the fact that the only thing using it right now is doing GOT loads for calls. Perhaps we could rename/generalize it though. In any case, this isn't urgent, so perhaps just add a comment mentioning this.

146

Sounds good.

test/CodeGen/WebAssembly/userstack.ll

9

With ExternalSymbol to get __stack_pointer, we no longer need to declare it at the LLVM IR level.

14

Is this function still needed now that we're using an ExternalSymbol for __stack_pointer?

[dschuff]

• Address final comments

test/CodeGen/WebAssembly/userstack.ll

14

No, in fact it was never actually needed, just leftover.

[dschuff]

• Remove changes to target-independent PEI, add WasmPEI

[dschuff]

Based on the current state of the discussion, either supporting virtual registers after RA or switching to physical registers will be a longer-term proposition. So I've included a modified PEI pass for WebAssembly and reverted the changes to the target-independent one (similarly to NVPTX) to allow us to make progress for now.

[sunfish]

lgtm (with the new changes).

lib/Target/WebAssembly/WebAssembly.h

42 ↗

(On Diff #42589)

It isn't stated so, but the passes above are ordered in the order that they run (except for Relooper, which is not currently run). Would you mind moving the PEI pass up just below RegColoring?

lib/Target/WebAssembly/WebAssemblyFrameLowering.cpp

144

Nit: unnecessary blank line here.

lib/Target/WebAssembly/WebAssemblyPEI.cpp

185 ↗

(On Diff #42589)

This is one of the changes to the generic PEI, right? Could you add a comment?

[dschuff]

• Address comments on updated CL

lib/Target/WebAssembly/WebAssemblyPEI.cpp

233 ↗

(On Diff #42589)

Also added comment here, the other "real" diff from generic PEI

lib/CodeGen/PrologEpilogInserter.cpp

 /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
 /// frame indexes with appropriate references.
 ///
 bool PEI::runOnMachineFunction(MachineFunction &Fn) {
   const Function* F = Fn.getFunction();
   const TargetRegisterInfo *TRI = Fn.getSubtarget().getRegisterInfo();
   const TargetFrameLowering *TFI = Fn.getSubtarget().getFrameLowering();
 
-  assert(!Fn.getRegInfo().getNumVirtRegs() && "Regalloc must assign all vregs");
+  //assert(!Fn.getRegInfo().getNumVirtRegs() && "Regalloc must assign all vregs");
 
   RS = TRI->requiresRegisterScavenging(Fn) ? new RegScavenger() : nullptr;
   FrameIndexVirtualScavenging = TRI->requiresFrameIndexScavenging(Fn);
 
   // Calculate the MaxCallFrameSize and AdjustsStack variables for the
   // function's frame information. Also eliminates call frame pseudo
   // instructions.
   calculateCallsInformation(Fn);
bool PEI::runOnMachineFunction(MachineFunction &Fn) {
   // Replace all MO_FrameIndex operands with physical register references
   // and actual offsets.
   //
   replaceFrameIndices(Fn);
 
   // If register scavenging is needed, as we've enabled doing it as a
   // post-pass, scavenge the virtual registers that frame index elimination
   // inserted.
-  if (TRI->requiresRegisterScavenging(Fn) && FrameIndexVirtualScavenging)
+  if (TRI->requiresRegisterScavenging(Fn) && FrameIndexVirtualScavenging) {
     scavengeFrameVirtualRegs(Fn);
-
     // Clear any vregs created by virtual scavenging.
     Fn.getRegInfo().clearVirtRegs();
+  }
 
   // Warn on stack size when we exceeds the given limit.
   MachineFrameInfo *MFI = Fn.getFrameInfo();
   uint64_t StackSize = MFI->getStackSize();
   if (WarnStackSize.getNumOccurrences() > 0 && WarnStackSize < StackSize) {
     DiagnosticInfoStackSize DiagStackSize(*F, StackSize);
     F->getContext().diagnose(DiagStackSize);
   }

lib/Target/WebAssembly/WebAssemblyFrameLowering.cpp

 #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: Prolog/epilog should be stackified too. This pass runs after register
+//       stackification, so we'll have to do it manually.
+
 
 /// 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->hasCalls() || MFI->hasVarSizedObjects() ||

 }
 
 void WebAssemblyFrameLowering::eliminateCallFramePseudoInstr(
     MachineFunction & /*MF*/, MachineBasicBlock & /*MBB*/,
     MachineBasicBlock::iterator /*I*/) const {
   llvm_unreachable("TODO: implement eliminateCallFramePseudoInstr");
 }
 
-void WebAssemblyFrameLowering::emitPrologue(MachineFunction & /*MF*/,
-                                            MachineBasicBlock & /*MBB*/) const {
-  llvm_unreachable("TODO: implement emitPrologue");
+void WebAssemblyFrameLowering::emitPrologue(MachineFunction &MF,
+                                            MachineBasicBlock &MBB) const {
+  uint64_t StackSize = MF.getFrameInfo()->getStackSize();
+  if (!StackSize)
+    return;
+  const auto *TII = MF.getSubtarget().getInstrInfo();
+  auto &MRI = MF.getRegInfo();
+  auto InsertPt = MBB.begin();
+  DebugLoc DL;
+
+  // Get the current stacktop
+  // TODO: To support dynamic alloc, also copy to FP
+  unsigned SPReg = MRI.createVirtualRegister(&WebAssembly::I32RegClass);
+  auto *SPSymbol = MF.getFunction()->getParent()
+      ->getNamedGlobal("SP");
+  BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::CONST_I32), SPReg)
+      .addGlobalAddress(SPSymbol);
+  auto *LoadMMO = new MachineMemOperand(MachinePointerInfo(SPSymbol),
+                                        MachineMemOperand::MOLoad, 4, 4);
+  BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::LOAD_I32), SPReg)
+      .addImm(0)
+      .addReg(SPReg)
+      .addMemOperand(LoadMMO);
+  // Subtract the frame size
+  unsigned OffsetReg = MRI.createVirtualRegister(&WebAssembly::I32RegClass);
+  BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::CONST_I32), OffsetReg)
+      .addImm(StackSize);
+  BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::SUB_I32), WebAssembly::SP32)
+      .addReg(SPReg)
+      .addReg(OffsetReg);
+  // The SP32 register now has the new stacktop. Also write it back to memory.
+  BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::CONST_I32), OffsetReg)
+      .addGlobalAddress(SPSymbol);
+  auto *MMO = new MachineMemOperand(MachinePointerInfo(SPSymbol),
+                                    MachineMemOperand::MOStore, 4, 4);
+  BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::STORE_I32), WebAssembly::SP32)
+      .addImm(0)
+      .addReg(OffsetReg)
+      .addReg(WebAssembly::SP32)
+      .addMemOperand(MMO);
 }
 
-void WebAssemblyFrameLowering::emitEpilogue(MachineFunction & /*MF*/,
-                                            MachineBasicBlock & /*MBB*/) const {
-  llvm_unreachable("TODO: implement emitEpilogue");
+void WebAssemblyFrameLowering::emitEpilogue(MachineFunction &MF,
+                                            MachineBasicBlock &MBB) const {
+  uint64_t StackSize = MF.getFrameInfo()->getStackSize();
+  if (!StackSize)
+    return;
+  const auto *TII = MF.getSubtarget().getInstrInfo();
+  auto &MRI = MF.getRegInfo();
+  unsigned OffsetReg = MRI.createVirtualRegister(&WebAssembly::I32RegClass);
+  auto InsertPt = MBB.getFirstTerminator();
+  DebugLoc DL;
+
+  if (InsertPt != MBB.end()) {
+    DL = InsertPt->getDebugLoc();
+  }
+
+  // Restore the stack pointer. Without FP its value is just SP32 - stacksize
+  BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::CONST_I32), OffsetReg)
+      .addImm(StackSize);
+  auto *SPSymbol = MF.getFunction()->getParent()
+      ->getNamedGlobal("SP");
+  BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::ADD_I32), WebAssembly::SP32)
+      .addReg(WebAssembly::SP32)
+      .addReg(OffsetReg);
+  // Re-use OffsetReg to hold the address of the stacktop
+  BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::CONST_I32), OffsetReg)
+      .addGlobalAddress(SPSymbol);
+  auto *MMO = new MachineMemOperand(MachinePointerInfo(SPSymbol),
+                                    MachineMemOperand::MOStore, 4, 4);
+  BuildMI(MBB, InsertPt, DL, TII->get(WebAssembly::STORE_I32), WebAssembly::SP32)
+      .addImm(0)
+      .addReg(OffsetReg)
+      .addReg(WebAssembly::SP32)
+      .addMemOperand(MMO);
+
 }

lib/Target/WebAssembly/WebAssemblyISelLowering.h

private:
   SDValue LowerFormalArguments(SDValue Chain, CallingConv::ID CallConv,
                                bool IsVarArg,
                                const SmallVectorImpl<ISD::InputArg> &Ins,
                                SDLoc DL, SelectionDAG &DAG,
                                SmallVectorImpl<SDValue> &InVals) const override;
 
   // Custom lowering hooks.
   SDValue LowerOperation(SDValue Op, SelectionDAG &DAG) const override;
+  SDValue LowerFrameIndex(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerGlobalAddress(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerExternalSymbol(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerBR_JT(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerJumpTable(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerVASTART(SDValue Op, SelectionDAG &DAG) const;
 };
 
 namespace WebAssembly {
 FastISel *createFastISel(FunctionLoweringInfo &funcInfo,
                          const TargetLibraryInfo *libInfo);
 } // end namespace WebAssembly
 
 } // end namespace llvm
 
 #endif

lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

WebAssemblyTargetLowering::WebAssemblyTargetLowering(
   for (auto T : {MVT::i1, MVT::i8, MVT::i16})
     setOperationAction(ISD::SIGN_EXTEND_INREG, T, Expand);
 
   // Dynamic stack allocation: use the default expansion.
   setOperationAction(ISD::STACKSAVE, MVT::Other, Expand);
   setOperationAction(ISD::STACKRESTORE, MVT::Other, Expand);
   setOperationAction(ISD::DYNAMIC_STACKALLOC, MVTPtr, Expand);
 
+  setOperationAction(ISD::FrameIndex, MVT::i32, Custom);
+
   // Expand these forms; we pattern-match the forms that we can handle in isel.
   for (auto T : {MVT::i32, MVT::i64, MVT::f32, MVT::f64})
     for (auto Op : {ISD::BR_CC, ISD::SELECT_CC})
       setOperationAction(Op, T, Expand);
 
   // We have custom switch handling.
   setOperationAction(ISD::BR_JT, MVT::Other, Custom);
 

 //===----------------------------------------------------------------------===//
 
 SDValue WebAssemblyTargetLowering::LowerOperation(SDValue Op,
                                                   SelectionDAG &DAG) const {
   switch (Op.getOpcode()) {
   default:
     llvm_unreachable("unimplemented operation lowering");
     return SDValue();
+  case ISD::FrameIndex:
+    return LowerFrameIndex(Op, DAG);
   case ISD::GlobalAddress:
     return LowerGlobalAddress(Op, DAG);
   case ISD::ExternalSymbol:
     return LowerExternalSymbol(Op, DAG);
   case ISD::JumpTable:
     return LowerJumpTable(Op, DAG);
   case ISD::BR_JT:
     return LowerBR_JT(Op, DAG);
   case ISD::VASTART:
     return LowerVASTART(Op, DAG);
   }
 }
 
+SDValue WebAssemblyTargetLowering::LowerFrameIndex(SDValue Op,
+                                                   SelectionDAG &DAG) const {
+  int FI = cast<FrameIndexSDNode>(Op)->getIndex();
+  return DAG.getTargetFrameIndex(FI, Op.getValueType());
+}
+
 SDValue WebAssemblyTargetLowering::LowerGlobalAddress(SDValue Op,
                                                       SelectionDAG &DAG) const {
   SDLoc DL(Op);
   const auto *GA = cast<GlobalAddressSDNode>(Op);
   EVT VT = Op.getValueType();
   assert(GA->getTargetFlags() == 0 && "WebAssembly doesn't set target flags");
   if (GA->getAddressSpace() != 0)
     fail(DL, DAG, "WebAssembly only expects the 0 address space");

lib/Target/WebAssembly/WebAssemblyMachineFunctionInfo.h

 /// \brief This file declares WebAssembly-specific per-machine-function
 /// information.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_TARGET_WEBASSEMBLY_WEBASSEMBLYMACHINEFUNCTIONINFO_H
 #define LLVM_LIB_TARGET_WEBASSEMBLY_WEBASSEMBLYMACHINEFUNCTIONINFO_H
 
+#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 
 namespace llvm {
 
 /// This class is derived from MachineFunctionInfo and contains private
 /// WebAssembly-specific information for each MachineFunction.
 class WebAssemblyFunctionInfo final : public MachineFunctionInfo {
   MachineFunction &MF;
 
   std::vector<MVT> Params;
 
   /// A mapping from CodeGen vreg index to WebAssembly register number.
   std::vector<unsigned> WARegs;
 
   /// A mapping from CodeGen vreg index to a boolean value indicating whether
   /// the given register is considered to be "stackified", meaning it has been
   /// determined or made to meet the stack requirements:
   ///   - single use (per path)
   ///   - single def (per path)
   ///   - defined and used in LIFO order with other stack registers
   BitVector VRegStackified;
 
+  // One entry for each possible target reg. we expect it to be small.
+  std::vector<unsigned> PhysRegs;
+
 public:
-  explicit WebAssemblyFunctionInfo(MachineFunction &MF) : MF(MF) {}
+  explicit WebAssemblyFunctionInfo(MachineFunction &MF) : MF(MF) {
+    PhysRegs.resize(WebAssembly::NUM_TARGET_REGS, -1U);
+  }
   ~WebAssemblyFunctionInfo() override;
 
   void addParam(MVT VT) { Params.push_back(VT); }
   const std::vector<MVT> &getParams() const { return Params; }
 
   static const unsigned UnusedReg = -1u;
 
   void stackifyVReg(unsigned VReg) {
     if (TargetRegisterInfo::virtReg2Index(VReg) >= VRegStackified.size())
       VRegStackified.resize(TargetRegisterInfo::virtReg2Index(VReg) + 1);
     VRegStackified.set(TargetRegisterInfo::virtReg2Index(VReg));
   }
   bool isVRegStackified(unsigned VReg) const {
     if (TargetRegisterInfo::virtReg2Index(VReg) >= VRegStackified.size())
       return false;
     return VRegStackified.test(TargetRegisterInfo::virtReg2Index(VReg));
   }
 
   void initWARegs();
   void setWAReg(unsigned VReg, unsigned WAReg) {
     assert(WAReg != UnusedReg);
     assert(TargetRegisterInfo::virtReg2Index(VReg) < WARegs.size());
     WARegs[TargetRegisterInfo::virtReg2Index(VReg)] = WAReg;
   }
-  unsigned getWAReg(unsigned VReg) const {
-    assert(TargetRegisterInfo::virtReg2Index(VReg) < WARegs.size());
-    return WARegs[TargetRegisterInfo::virtReg2Index(VReg)];
+  unsigned getWAReg(unsigned Reg) const {
+    if (TargetRegisterInfo::isVirtualRegister(Reg)) {
+      assert(TargetRegisterInfo::virtReg2Index(Reg) < WARegs.size());
+      return WARegs[TargetRegisterInfo::virtReg2Index(Reg)];
+    }
+    return PhysRegs[Reg];
   }
   // If new virtual registers are created after initWARegs has been called,
   // this function can be used to add WebAssembly register mappings for them.
   void addWAReg(unsigned VReg, unsigned WAReg) {
     assert(VReg = WARegs.size());
     WARegs.push_back(WAReg);
   }
+
+  void addPReg(unsigned PReg, unsigned WAReg) {
+    assert(PReg < WebAssembly::NUM_TARGET_REGS);
+    assert(WAReg < -1U);
+    PhysRegs[PReg] = WAReg;
+  }
 };
 
 } // end namespace llvm
 
 #endif

lib/Target/WebAssembly/WebAssemblyPeephole.cpp

for (auto &MI : MBB)
       case WebAssembly::STORE_F64:
       case WebAssembly::STORE_I32:
       case WebAssembly::STORE_I64: {
         // Store instructions return their value operand. If we ended up using
         // the same register for both, replace it with a dead def so that it
         // can use $discard instead.
         MachineOperand &MO = MI.getOperand(0);
         unsigned OldReg = MO.getReg();
-        if (OldReg == MI.getOperand(3).getReg()) {
+        // TODO: Handle SP/physregs
+        if (OldReg == MI.getOperand(3).getReg()
+            && TargetRegisterInfo::isVirtualRegister(MI.getOperand(3).getReg())) {
           unsigned NewReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg));
           MO.setReg(NewReg);
           MO.setIsDead();
           MFI.stackifyVReg(NewReg);
           MFI.addWAReg(NewReg, WebAssemblyFunctionInfo::UnusedReg);
         }
       }
       }
 
   return Changed;
 }

lib/Target/WebAssembly/WebAssemblyRegNumbering.cpp

 //===----------------------------------------------------------------------===//
 
 #include "WebAssembly.h"
 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
 #include "WebAssemblyMachineFunctionInfo.h"
 #include "WebAssemblySubtarget.h"
 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 

 
 bool WebAssemblyRegNumbering::runOnMachineFunction(MachineFunction &MF) {
   DEBUG(dbgs() << "********** Register Numbering **********\n"
                   "********** Function: "
                << MF.getName() << '\n');
 
   WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
   MachineRegisterInfo &MRI = MF.getRegInfo();
+  const MachineFrameInfo &FrameInfo = *MF.getFrameInfo();
 
   MFI.initWARegs();
 
   // WebAssembly argument registers are in the same index space as local
   // variables. Assign the numbers for them first.
   MachineBasicBlock &EntryMBB = MF.front();
   for (MachineInstr &MI : EntryMBB) {
     switch (MI.getOpcode()) {
if (MFI.isVRegStackified(VReg)) {
       continue;
     }
     // Skip unused registers.
     if (MRI.use_empty(VReg))
       continue;
     if (MFI.getWAReg(VReg) == WebAssemblyFunctionInfo::UnusedReg)
       MFI.setWAReg(VReg, NumArgRegs + CurReg++);
   }
+  // Allocate locals for used physical registers
+  if (FrameInfo.getStackSize() > 0)
+    MFI.addPReg(WebAssembly::SP32, CurReg++);
 
   return true;
 }

lib/Target/WebAssembly/WebAssemblyRegisterInfo.cpp

WebAssemblyRegisterInfo::getReservedRegs(const MachineFunction & /*MF*/) const {
   BitVector Reserved(getNumRegs());
   for (auto Reg : {WebAssembly::SP32, WebAssembly::SP64, WebAssembly::FP32,
                    WebAssembly::FP64})
     Reserved.set(Reg);
   return Reserved;
 }
 
 void WebAssemblyRegisterInfo::eliminateFrameIndex(
-    MachineBasicBlock::iterator /*II*/, int /*SPAdj*/,
-    unsigned /*FIOperandNum*/, RegScavenger * /*RS*/) const {
-  llvm_unreachable(
-      "TODO: implement WebAssemblyRegisterInfo::eliminateFrameIndex");
+    MachineBasicBlock::iterator II, int SPAdj,
+    unsigned FIOperandNum, RegScavenger * /*RS*/) const {
+  assert(SPAdj == 0);
+  MachineInstr &MI = *II;
+
+  MachineBasicBlock &MBB = *MI.getParent();
+  MachineFunction &MF = *MBB.getParent();
+  int FrameIndex = MI.getOperand(FIOperandNum).getIndex();
+  const MachineFrameInfo& MFI = *MF.getFrameInfo();
+  int FrameOffset = MFI.getStackSize() + MFI.getObjectOffset(FrameIndex);
+
+  if (MI.mayLoadOrStore()) {
+    // If this is a load or store, make it relative to SP and fold the frame
+    // offset directly in
+    assert(MI.getOperand(1).getImm() == 0 &&
+           "Can't eliminate FI yet if offset is already set");
+    MI.getOperand(1).setImm(FrameOffset);
+    MI.getOperand(2).ChangeToRegister(WebAssembly::SP32, /*IsDef=*/false);
+  } else {
+    // Otherwise create an i32.add SP, offset and make it the operand
+    auto &MRI = MF.getRegInfo();
+    const auto *TII = MF.getSubtarget().getInstrInfo();
+
+    unsigned OffsetReg = MRI.createVirtualRegister(&WebAssembly::I32RegClass);
+    BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(WebAssembly::CONST_I32), OffsetReg)
+        .addImm(FrameOffset);
+    BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(WebAssembly::ADD_I32), OffsetReg)
+        .addReg(WebAssembly::SP32)
+        .addReg(OffsetReg);
+    MI.getOperand(FIOperandNum).ChangeToRegister(OffsetReg, /*IsDef=*/false);
+  }
 }
 
 unsigned
 WebAssemblyRegisterInfo::getFrameRegister(const MachineFunction &MF) const {
   static const unsigned Regs[2][2] = {
       /*            !isArch64Bit       isArch64Bit      */
       /* !hasFP */ {WebAssembly::SP32, WebAssembly::SP64},
       /*  hasFP */ {WebAssembly::FP32, WebAssembly::FP64}};

lib/Target/WebAssembly/WebAssemblyTargetMachine.cpp

void WebAssemblyPassConfig::addPreRegAlloc() {
   addPass(createWebAssemblyRegStackify());
 }
 
 void WebAssemblyPassConfig::addPostRegAlloc() {
   // TODO: The following CodeGen passes don't currently support code containing
   // virtual registers. Consider removing their restrictions and re-enabling
   // them.
   //
-  // Fails with: Regalloc must assign all vregs.
-  disablePass(&PrologEpilogCodeInserterID);
   // Fails with: should be run after register allocation.
   disablePass(&MachineCopyPropagationID);
 
   // Run the register coloring pass to reduce the total number of registers.
   addPass(createWebAssemblyRegColoring());
 
   TargetPassConfig::addPostRegAlloc();
 }

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-p:32:32-i64:64-n32:64-S128"
+target triple = "wasm32-unknown-unknown"
+
+@SP = external global i32
+
+define void @s1() {
+  store i32 1, i32* @SP
+  ret void
+}
+
+; CHECK-LABEL: alloca32:
+define void @alloca32() {
+ ; CHECK: i32.const [[L1:.+]]=, SP
+ ; CHECK-NEXT: i32.load [[L1]]=, 0([[L1]])
+ ; CHECK-NEXT: i32.const [[L2:.+]]=, 16
+ ; CHECK-NEXT: i32.sub [[SP:.+]]=, [[L1]], [[L2]]
+ %retval = alloca i32
+ ; CHECK: i32.const $push[[L3:.+]]=, 0
+ ; CHECK: i32.store {{.*}}=, 12([[SP]]), $pop[[L3]]
+ store i32 0, i32* %retval
+ ; CHECK: i32.const [[L4:.+]]=, 16
+ ; CHECK-NEXT: i32.add [[SP]]=, [[SP]], [[L4]]
+ ; CHECK-NEXT: i32.const [[L5:.+]]=, SP
+ ; CHECK-NEXT: i32.store [[SP]]=, 0([[L5]]), [[SP]]
+ ret void
+}
+
+; CHECK-LABEL: alloca3264:
+define void @alloca3264() {
+ ; CHECK: i32.const [[L1:.+]]=, SP
+ ; CHECK-NEXT: i32.load [[L1]]=, 0([[L1]])
+ ; CHECK-NEXT: i32.const [[L2:.+]]=, 16
+ ; CHECK-NEXT: i32.sub [[SP:.+]]=, [[L1]], [[L2]]
+ %r1 = alloca i32
+ %r2 = alloca double
+ ; CHECK: i32.const $push[[L3:.+]]=, 0
+ ; CHECK: i32.store {{.*}}=, 12([[SP]]), $pop[[L3]]
+ store i32 0, i32* %r1
+ ; CHECK: i64.const $push[[L4:.+]]=, 0
+ ; CHECK: i64.store {{.*}}=, 0([[SP]]), $pop[[L4]]
+ store double 0.0, double* %r2
+ ; CHECK: i32.const [[L4:.+]]=, 16
+ ; CHECK-NEXT: i32.add [[SP]]=, [[SP]], [[L4]]
+ ; CHECK-NEXT: i32.const [[L5:.+]]=, SP
+ ; CHECK-NEXT: i32.store [[SP]]=, 0([[L5]]), [[SP]]
+ ret void
+}
+
+define void @allocarray() {
+ ; CHECK: i32.const [[L1:.+]]=, SP
+ ; CHECK-NEXT: i32.load [[L1]]=, 0([[L1]])
+ ; CHECK-NEXT: i32.const [[L2:.+]]=, 32
+ ; CHECK-NEXT: i32.sub [[SP:.+]]=, [[L1]], [[L2]]
+ %r = alloca [5 x i32]
+ ; CHECK: i32.const $push[[L3:.+]]=, 1
+ ; CHECK: i32.store {{.*}}=, 12([[SP]]), $pop[[L3]]
+ %p = getelementptr [5 x i32], [5 x i32]* %r, i32 0, i32 0
+ store i32 1, i32* %p
+ ; CHECK: i32.const $push[[L4:.+]]=, 4
+ ; CHECK: i32.const [[L5:.+]]=, 12
+ ; CHECK: i32.add [[L5]]=, [[SP]], [[L5]]
+ ; CHECK: i32.add $push[[L6:.+]]=, [[L5]], $pop[[L4]]
+ ; CHECK: i32.store {{.*}}=, 0($pop[[L6]]), ${{.+}}
+ %p2 = getelementptr [5 x i32], [5 x i32]* %r, i32 0, i32 1
+ store i32 1, i32* %p2
+ ; CHECK: i32.const [[L7:.+]]=, 32
+ ; CHECK-NEXT: i32.add [[SP]]=, [[SP]], [[L7]]
+ ; CHECK-NEXT: i32.const [[L8:.+]]=, SP
+ ; CHECK-NEXT: i32.store [[SP]]=, 0([[L7]]), [[SP]]
+ ret void
+}
+
+; TODO: test aligned alloc