[WebAssembly][CodeGen] IR support for WebAssembly local variables

[wingo]

Summary

This patch adds TargetStackID::WasmLocal. This stack holds locations of
values that are only addressable by name -- not via a pointer to memory.
For the WebAssembly target, these objects are lowered to WebAssembly
local variables, which are managed by the WebAssembly run-time and are
not addressable by linear memory.

For the WebAssembly target IR indicates that an AllocaInst should be put
on TargetStackID::WasmLocal by putting it in the non-integral address
space WASM_ADDRESS_SPACE_WASM_VAR, with value 1. SROA will mostly lift
these allocations to SSA locals, but any alloca that reaches instruction
selection (usually in non-optimized builds) will be assigned the new
TargetStackID there. Loads and stores to those values are transformed
to new WebAssemblyISD::LOCAL_GET / WebAssemblyISD::LOCAL_SET nodes,
which then lower to the type-specific LOCAL_GET_I32 etc instructions via
tablegen patterns.

[wingo]

This is an early WIP; posting just to give context for D101045.

[wingo]

Rebase, and add A0:u addrspace qualifier

[tlively]

Nice! This turns out to be relatively simple. It would be good to add more tests with reference typed locals mixed in with normal locals, etc. Also, what happens when one of the alloca values is used by something other than a load or a store? Is it just an ISel failure at that point?

llvm/lib/Target/WebAssembly/WebAssemblyInstrInfo.td

102

I would name this WebAssemblylocal_get to match WebAssemblybr_table, although admittedly the naming convention for these custom nodes is very weird.

llvm/lib/Target/WebAssembly/WebAssemblyInstrRef.td

29 ↗

(On Diff #341100)

Unintentional whitespace change?

llvm/lib/Target/WebAssembly/WebAssemblyMachineFunctionInfo.h

107 ↗

(On Diff #341100)

I believe this should work fine as well. In fact this, whole pattern could be reduced to this:

auto Results = FrameIndex2Local.insert({FrameIndex, Locals.size()});
if (Results.second)
  addLocal(VT);
return Results.first->second + Params.size();

llvm/lib/Target/WebAssembly/WebAssemblyUtilities.h

35 ↗

(On Diff #341100)

Could even do this to make it clearer that this is meant to be used as an unsigned.

llvm/test/CodeGen/WebAssembly/externref-alloca.ll

3–4 ↗

(On Diff #341100)

Would it be possible to use the same address space(s) for locals and globals? In general we can use an fixed, finite number of address spaces, but I would prefer to use as few as possible so there is less to remember :)

[wingo]

In D101140#2724740, @tlively wrote:

Nice! This turns out to be relatively simple. It would be good to add more tests with reference typed locals mixed in with normal locals, etc.

Thanks for the feedback! Agreed with regards to tests obviously. Following up directly as regards the most important question, "is it actually robust":

Also, what happens when one of the alloca values is used by something other than a load or a store? Is it just an ISel failure at that point?

Let us assume that because of source restrictions, all allocas are static (in the sense of AllocaInst::isStaticAlloca()). The alloca's are in a non-integral address space so the only operation you can do on them is to pass the pointer value around, or load from it, or store to it. (If I missed a potential use, I am happy to be corrected.) We handle the load and store cases. Source restrictions prevent passing locals by-reference to other functions, so I think we are good there as well. I have no idea what might happen if the source restrictions aren't respected though -- good thing the SVE people have done most of the work on the front-end already because getting a coherent story there would be complicated otherwise!

There is one "hole in the racket", as apparently we say in french -- externref/funcref locals which have no uses. You wouldn't want these leaving isel as live stack objects in the MachineFrameInfo. I am thinking it may be more robust to run a quick pre-pass through the stack objects after the static alloca's are collected in FunctionLoweringInfo::set to eagerly transform them to locals and mark them dead, even if there are no uses.

[wingo]

Remove reftypes

[wingo]

Rebased on top of https://reviews.llvm.org/D101608, and removed reftypes support, as it turns out that the notion of WebAssembly locals in IR is sufficiently general that externref/funcref can be added in a followup. WDYT @tlively, @dschuff , @pmatos ?

[wingo]

Fix clang datalayout expectations

[tlively]

llvm/include/llvm/CodeGen/MIRYamlMapping.h

351

Is there a good test to demonstrate this change in?

llvm/lib/Target/WebAssembly/Utils/WebAssemblyUtilities.cpp

34–36

Why do this in two places instead of just once comprehensively in the hook? It would be good to explain that in the comment, too.

63–64

Can there be aggregate components? What do we do with them?

[wingo]

Rename "object" to "managed", and add test for stack id

[wingo]

Update in response to parent commit changes

[wingo]

Rebase

[wingo]

Address feedback

llvm/include/llvm/CodeGen/MIRYamlMapping.h

351

Done in ir-locals-stackid.ll

llvm/lib/Target/WebAssembly/Utils/WebAssemblyUtilities.cpp

34–36

👍

63–64

Hoo, it is a good question. I think the high-level answer is that in the same way as you can allocate an i32 to a local, or an externref to a local, you could allocate a struct { i32, externref }. The leaves of that aggregate would be numbered from 0 to N, assigned to consecutive locals of the appropriate primitive types, and accesses would compiled down to direct access to the members. Probably the first person who tries this is going to run into some interesting cases and I think specifically the local.get index mapping isn't quite yet ready. But that would be the idea. WDYT?

[wingo]

Gentle ping here to @tlively :)

[tlively]

LGTM with that one last comment on the test.

llvm/test/CodeGen/WebAssembly/ir-locals.ll

18–21

It might be good to get the value from an external function call rather than from an argument to prevent this transformation from happening.

[wingo]

llvm/test/CodeGen/WebAssembly/ir-locals.ll

18–21

Tx for feedback. Actually it doesn't really matter where the value comes from; store-to-load forwarding happens regardless. If it came from a call it would be allocated a local via the explicit locals pass, as a value with more than one use.

However I was able to inhibit this transformation with an opaque call, so I'll do that.

[wingo]

Adapt test to insert compiler barrier.

[wingo]

Fix build for RISC-V and AMDGPU.

[jrtc27]

Is it just me or does having a backend-specific type in target-independent code feel wrong? It feels like there should be a space for target-specific TargetStackIDs...

[wingo]

In D101140#2786777, @jrtc27 wrote:

Is it just me or does having a backend-specific type in target-independent code feel wrong? It feels like there should be a space for target-specific TargetStackIDs...

Hoo, good question. More support for target-specific handling of stack IDs would be great. However in this case the concept is not purely wasm-specific; I can imagine other targets that might have a similar treatment of locals (if we had a .net target, or a jvm target, or so). The idea is that there is a separate stack consisting of named locals that may not be addressable by pointers to main memory. In earlier drafts of this patch the name was more generic ("Object", then "Managed") but you know, our words in this area are quite overloaded. So instead I went with something quite specific (WasmLocal) to avoid the general question -- but I do think the concept is not specific, even if it doesn't apply to any other target currently in tree. WDYT?

[jrtc27]

In D101140#2786844, @wingo wrote:

In D101140#2786777, @jrtc27 wrote:

Is it just me or does having a backend-specific type in target-independent code feel wrong? It feels like there should be a space for target-specific TargetStackIDs...

Hoo, good question. More support for target-specific handling of stack IDs would be great. However in this case the concept is not purely wasm-specific; I can imagine other targets that might have a similar treatment of locals (if we had a .net target, or a jvm target, or so). The idea is that there is a separate stack consisting of named locals that may not be addressable by pointers to main memory. In earlier drafts of this patch the name was more generic ("Object", then "Managed") but you know, our words in this area are quite overloaded. So instead I went with something quite specific (WasmLocal) to avoid the general question -- but I do think the concept is not specific, even if it doesn't apply to any other target currently in tree. WDYT?

Well, except all the logic for it is in the backend, only the parser and the definition are in target-independent code, so even if another backend were to reuse it it would have its own completely separate logic for it, and thus there's no benefit to reusing a shared name for the thing over each target defining its own? Or would some of the code in the wasm backend be refactored out into CodeGen?

[wingo]

In D101140#2786870, @jrtc27 wrote:

In D101140#2786844, @wingo wrote:

In D101140#2786777, @jrtc27 wrote:

Is it just me or does having a backend-specific type in target-independent code feel wrong? It feels like there should be a space for target-specific TargetStackIDs...

Hoo, good question. More support for target-specific handling of stack IDs would be great. However in this case the concept is not purely wasm-specific; I can imagine other targets that might have a similar treatment of locals (if we had a .net target, or a jvm target, or so). The idea is that there is a separate stack consisting of named locals that may not be addressable by pointers to main memory. In earlier drafts of this patch the name was more generic ("Object", then "Managed") but you know, our words in this area are quite overloaded. So instead I went with something quite specific (WasmLocal) to avoid the general question -- but I do think the concept is not specific, even if it doesn't apply to any other target currently in tree. WDYT?

Well, except all the logic for it is in the backend, only the parser and the definition are in target-independent code, so even if another backend were to reuse it it would have its own completely separate logic for it, and thus there's no benefit to reusing a shared name for the thing over each target defining its own? Or would some of the code in the wasm backend be refactored out into CodeGen?

This is the case for all TargetStackID enumerated values except TargetStackID::Default -- ScalableVector and SGPRSpill have 0 uses outside target backends, though the ScalableVector name is used in RISC-V and AMDGPU. NoAlloc has one mention outside the target backends but no real logic. Still, as a reader who hacks neither on RISC-V nor AMDGPU I find it useful that they share the same stack ID definition for scalable vectors -- lets me compare things a bit easier.

If there is a change to be made in this area (moving these enumerated values elsewhere) it would have to be in a followup I think and would need consultation with the other backends that use these values.

[wingo]

Yarrrgh, broke the shared library build. Fix incoming...

[wingo]

Fix shared-library build by moving util function to WebAssemblyFrameLowering.

[wingo]

Quick r? to @tlively -- OK with having the new util function in WebAssemblyFrameLowering? It didn't work to have it in the utils library because the function needs the vtable of WebAssemblyFunctionInfo.

[tlively]

In D101140#2789199, @wingo wrote:

Quick r? to @tlively -- OK with having the new util function in WebAssemblyFrameLowering? It didn't work to have it in the utils library because the function needs the vtable of WebAssemblyFunctionInfo.

Yes, this sounds reasonable to me.

And regarding the target-specific additions to target-independent code, this addition also seems similar to how we have target-specific MVTs in the target-independent MVT list. Being able to add names (but usually not logic) for target-specific concepts to target-independent namespaces makes it much simpler to handle target-independent and target-specific things in a uniform way in the backends.

llvm/include/llvm/CodeGen/MIRYamlMapping.h

 };
 
 template <>
 struct ScalarEnumerationTraits<TargetStackID::Value> {
   static void enumeration(yaml::IO &IO, TargetStackID::Value &ID) {
     IO.enumCase(ID, "default", TargetStackID::Default);
     IO.enumCase(ID, "sgpr-spill", TargetStackID::SGPRSpill);
     IO.enumCase(ID, "scalable-vector", TargetStackID::ScalableVector);
+    IO.enumCase(ID, "object", TargetStackID::Object);
     IO.enumCase(ID, "noalloc", TargetStackID::NoAlloc);
   }
 };
 
 template <> struct MappingTraits<FixedMachineStackObject> {
   static void mapping(yaml::IO &YamlIO, FixedMachineStackObject &Object) {
     YamlIO.mapRequired("id", Object.ID);
     YamlIO.mapOptional(

llvm/include/llvm/CodeGen/TargetFrameLowering.h

 
 namespace llvm {
   class BitVector;
   class CalleeSavedInfo;
   class MachineFunction;
   class RegScavenger;
 
 namespace TargetStackID {
-  enum Value {
-    Default = 0,
-    SGPRSpill = 1,
-    ScalableVector = 2,
-    NoAlloc = 255
-  };
+  Object = 3,
 }
 
 /// Information about stack frame layout on the target.  It holds the direction
 /// of stack growth, the known stack alignment on entry to each function, and
 /// the offset to the locals area.
 ///
 /// The offset to the local area is the offset from the stack pointer on
 /// function entry to the first location where function data (local variables,

llvm/lib/Target/WebAssembly/Utils/WebAssemblyUtilities.h

 /// This file contains the declaration of the WebAssembly-specific
 /// utility functions.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_TARGET_WEBASSEMBLY_UTILS_WEBASSEMBLYUTILITIES_H
 #define LLVM_LIB_TARGET_WEBASSEMBLY_UTILS_WEBASSEMBLYUTILITIES_H
 
+#include "llvm/ADT/Optional.h"
+
 namespace llvm {
 
 class MachineBasicBlock;
 class MachineInstr;
+class MachineFunction;
 class MachineOperand;
 class MCContext;
 class MCSymbolWasm;
 class StringRef;
 class WebAssemblyFunctionInfo;
 class WebAssemblySubtarget;
 
 namespace WebAssembly {
 
+enum WasmAddressSpace : unsigned {
+  // Default address space, for pointers to unmanaged data in linear memory
+  // (stack, heap, data).
+  WASM_ADDRESS_SPACE_DEFAULT = 0,
+  // A non-integral address space for pointers to named objects outside of
+  // linear memory: static-storage-duration globals, or
+  // automatic-storage-duration locals.  Loads and stores to these pointers are
+  // lowered to global.get / global.set or local.get / local.set, as
+  // appropriate.
+  WASM_ADDRESS_SPACE_OBJECT = 1
+};
+
+inline bool isObjectAddressSpace(unsigned AS) {
+  return AS == WebAssembly::WASM_ADDRESS_SPACE_OBJECT;
+}
+
+// Returns the index of the WebAssembly local to which the stack object
+// FrameIndex in MF should be allocated, or None.
+Optional<unsigned> getLocalForStackObject(MachineFunction &MF, int FrameIndex);
+
 bool isChild(const MachineInstr &MI, const WebAssemblyFunctionInfo &MFI);
 bool mayThrow(const MachineInstr &MI);
 
 // Exception-related function names
 extern const char *const ClangCallTerminateFn;
 extern const char *const CxaBeginCatchFn;
 extern const char *const CxaRethrowFn;
 extern const char *const StdTerminateFn;

llvm/lib/Target/WebAssembly/Utils/WebAssemblyUtilities.cpp

 //===-- WebAssemblyUtilities.cpp - WebAssembly Utility Functions ----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// This file implements several utility functions for WebAssembly.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "WebAssemblyUtilities.h"
 #include "WebAssemblyMachineFunctionInfo.h"
+#include "WebAssemblySubtarget.h"
+#include "llvm/CodeGen/Analysis.h"
+#include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/MC/MCContext.h"
 using namespace llvm;
 
 const char *const WebAssembly::CxaBeginCatchFn = "__cxa_begin_catch";
 const char *const WebAssembly::CxaRethrowFn = "__cxa_rethrow";
 const char *const WebAssembly::StdTerminateFn = "_ZSt9terminatev";
 const char *const WebAssembly::PersonalityWrapperFn =
     "_Unwind_Wasm_CallPersonality";
 
+// In an ideal world, when objects are added to the MachineFrameInfo by
+// FunctionLoweringInfo::set, we could somehow hook into target-specific code to
+// ensure they are assigned the right stack ID.  However there isn't a hook that
+// runs between then and DAG building time, though, so instead we hoist stack
+// objects lazily when they are first used, and comprehensively after the DAG is
+// built via the PreprocessISelDAG hook, called by the
+// SelectionDAGISel::runOnMachineFunction.
+Optional<unsigned> WebAssembly::getLocalForStackObject(MachineFunction &MF,
+                                                       int FrameIndex) {
+  auto &MFI = MF.getFrameInfo();
+
+  // If already hoisted to a local, done.
+  if (MFI.getStackID(FrameIndex) == TargetStackID::Object)
+    return static_cast<unsigned>(MFI.getObjectOffset(FrameIndex));
+
+  // If not allocated in the object address space, this object will be in
+  // linear memory.
+  const AllocaInst *AI = MFI.getObjectAllocation(FrameIndex);
+  if (!AI || !isObjectAddressSpace(AI->getType()->getAddressSpace()))
+    return None;
+
+  // Otherwise, allocate this object in the named value stack, outside of linear
+  // memory.
+  SmallVector<EVT, 4> ValueVTs;
+  const WebAssemblyTargetLowering &TLI =
+      *MF.getSubtarget<WebAssemblySubtarget>().getTargetLowering();
+  WebAssemblyFunctionInfo *FuncInfo = MF.getInfo<WebAssemblyFunctionInfo>();
+  ComputeValueVTs(TLI, MF.getDataLayout(), AI->getAllocatedType(), ValueVTs);
+  MFI.setStackID(FrameIndex, TargetStackID::Object);
+  // Abuse SP offset to record the index of the first local in the object.
+  unsigned Local = FuncInfo->getParams().size() + FuncInfo->getLocals().size();
+  MFI.setObjectOffset(FrameIndex, Local);
+  // Allocate WebAssembly locals for each non-aggregate component of the
+  // allocation.
+  for (EVT ValueVT : ValueVTs)
+    FuncInfo->addLocal(ValueVT.getSimpleVT());
+  // Abuse object size to record number of WebAssembly locals allocated to
+  // this object.
+  MFI.setObjectSize(FrameIndex, ValueVTs.size());
+  return static_cast<unsigned>(Local);
+}
+
 /// Test whether MI is a child of some other node in an expression tree.
 bool WebAssembly::isChild(const MachineInstr &MI,
                           const WebAssemblyFunctionInfo &MFI) {
   if (MI.getNumOperands() == 0)
     return false;
   const MachineOperand &MO = MI.getOperand(0);
   if (!MO.isReg() || MO.isImplicit() || !MO.isDef())
     return false;

llvm/lib/Target/WebAssembly/WebAssemblyExplicitLocals.cpp

for (MachineBasicBlock::iterator I = MF.begin()->begin(),
 
     // Update debug value to point to the local before removing.
     WebAssemblyDebugValueManager(&MI).replaceWithLocal(Local);
 
     MI.eraseFromParent();
     Changed = true;
   }
 
-  // Start assigning local numbers after the last parameter.
+  // Start assigning local numbers after the last parameter and after any
+  // already-assigned locals.
   unsigned CurLocal = static_cast<unsigned>(MFI.getParams().size());
+  CurLocal += static_cast<unsigned>(MFI.getLocals().size());
 
   // Precompute the set of registers that are unused, so that we can insert
   // drops to their defs.
   BitVector UseEmpty(MRI.getNumVirtRegs());
   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I)
     UseEmpty[I] = MRI.use_empty(Register::index2VirtReg(I));
 
   // Visit each instruction in the function.

llvm/lib/Target/WebAssembly/WebAssemblyFastISel.cpp

bool WebAssemblyFastISel::selectBitCast(const Instruction *I) {
   updateValueMap(I, Reg);
   return true;
 }
 
 bool WebAssemblyFastISel::selectLoad(const Instruction *I) {
   const auto *Load = cast<LoadInst>(I);
   if (Load->isAtomic())
     return false;
+  if (Load->getPointerAddressSpace() != WebAssembly::WASM_ADDRESS_SPACE_DEFAULT)
+    return false;
   if (!Subtarget->hasSIMD128() && Load->getType()->isVectorTy())
     return false;
 
   Address Addr;
   if (!computeAddress(Load->getPointerOperand(), Addr))
     return false;
 
   // TODO: Fold a following sign-/zero-extend into the load instruction.
bool WebAssemblyFastISel::selectLoad(const Instruction *I) {
   updateValueMap(Load, ResultReg);
   return true;
 }
 
 bool WebAssemblyFastISel::selectStore(const Instruction *I) {
   const auto *Store = cast<StoreInst>(I);
   if (Store->isAtomic())
     return false;
+  if (Store->getPointerAddressSpace() !=
+      WebAssembly::WASM_ADDRESS_SPACE_DEFAULT)
+    return false;
   if (!Subtarget->hasSIMD128() &&
       Store->getValueOperand()->getType()->isVectorTy())
     return false;
 
   Address Addr;
   if (!computeAddress(Store->getPointerOperand(), Addr))
     return false;
 

llvm/lib/Target/WebAssembly/WebAssemblyFrameLowering.h

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;
+  bool isSupportedStackID(TargetStackID::Value ID) const override;
   DwarfFrameBase getDwarfFrameBase(const MachineFunction &MF) const override;
 
   bool needsPrologForEH(const MachineFunction &MF) const;
 
   /// Write SP back to __stack_pointer global.
   void writeSPToGlobal(unsigned SrcReg, MachineFunction &MF,
                        MachineBasicBlock &MBB,
                        MachineBasicBlock::iterator &InsertStore,

llvm/lib/Target/WebAssembly/WebAssemblyFrameLowering.cpp

BuildMI(MBB, InsertPt, DL, TII->get(getOpcAdd(MF)), SPReg)
         .addReg(OffsetReg);
   } else {
     SPReg = SPFPReg;
   }
 
   writeSPToGlobal(SPReg, MF, MBB, InsertPt, DL);
 }
 
+bool WebAssemblyFrameLowering::isSupportedStackID(
+    TargetStackID::Value ID) const {
+  // Use the Object stack for WebAssembly locals which can only be accessed
+  // by name, not via an address in linear memory.
+  if (ID == TargetStackID::Object)
+    return true;
+
+  return TargetFrameLowering::isSupportedStackID(ID);
+}
+
 TargetFrameLowering::DwarfFrameBase
 WebAssemblyFrameLowering::getDwarfFrameBase(const MachineFunction &MF) const {
   DwarfFrameBase Loc;
   Loc.Kind = DwarfFrameBase::WasmFrameBase;
   const WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
   if (needsSP(MF) && MFI.isFrameBaseVirtual()) {
     unsigned LocalNum = MFI.getFrameBaseLocal();
     Loc.Location.WasmLoc = {WebAssembly::TI_LOCAL, LocalNum};
   } else {
     // TODO: This should work on a breakpoint at a function with no frame,
     // but probably won't work for traversing up the stack.
     Loc.Location.WasmLoc = {WebAssembly::TI_GLOBAL_RELOC, 0};
   }
   return Loc;
 }

llvm/lib/Target/WebAssembly/WebAssemblyISD.def

 //===----------------------------------------------------------------------===//
 
 // NOTE: NO INCLUDE GUARD DESIRED!
 
 HANDLE_NODETYPE(CALL)
 HANDLE_NODETYPE(RET_CALL)
 HANDLE_NODETYPE(RETURN)
 HANDLE_NODETYPE(ARGUMENT)
+HANDLE_NODETYPE(LOCAL_GET)
+HANDLE_NODETYPE(LOCAL_SET)
 // A wrapper node for TargetExternalSymbol, TargetGlobalAddress, and MCSymbol
 HANDLE_NODETYPE(Wrapper)
 // A special wapper used in PIC code for __memory_base/__table_base relative
 // access.
 HANDLE_NODETYPE(WrapperPIC)
 HANDLE_NODETYPE(BR_IF)
 HANDLE_NODETYPE(BR_TABLE)
 HANDLE_NODETYPE(SHUFFLE)

llvm/lib/Target/WebAssembly/WebAssemblyISelDAGToDAG.cpp

 //- WebAssemblyISelDAGToDAG.cpp - A dag to dag inst selector for WebAssembly -//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// This file defines an instruction selector for the WebAssembly target.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
+#include "Utils/WebAssemblyUtilities.h"
 #include "WebAssembly.h"
 #include "WebAssemblyTargetMachine.h"
+#include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/SelectionDAGISel.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Function.h" // To access function attributes.
 #include "llvm/IR/IntrinsicsWebAssembly.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
LLVM_DEBUG(dbgs() << "********** ISelDAGToDAG **********\n"
                          "********** Function: "
                       << MF.getName() << '\n');
 
     Subtarget = &MF.getSubtarget<WebAssemblySubtarget>();
 
     return SelectionDAGISel::runOnMachineFunction(MF);
   }
 
+  void PreprocessISelDAG() override;
+
   void Select(SDNode *Node) override;
 
   bool SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintID,
                                     std::vector<SDValue> &OutOps) override;
 
 // Include the pieces autogenerated from the target description.
 #include "WebAssemblyGenDAGISel.inc"
 
 private:
   // add select functions here...
 };
 } // end anonymous namespace
 
+void WebAssemblyDAGToDAGISel::PreprocessISelDAG() {
+  // Stack objects that should be allocated to locals are hoisted to WebAssembly
+  // locals when they are first used.  However for those without uses, we hoist
+  // them here.  It would be nice if there were some hook to do this when they
+  // are added to the MachineFrameInfo, but that's not the case right now.
+  MachineFrameInfo &FrameInfo = MF->getFrameInfo();
+  for (int Idx = 0; Idx < FrameInfo.getObjectIndexEnd(); Idx++)
+    WebAssembly::getLocalForStackObject(*MF, Idx);
+
+  SelectionDAGISel::PreprocessISelDAG();
+}
+
 void WebAssemblyDAGToDAGISel::Select(SDNode *Node) {
   // If we have a custom node, we already have selected!
   if (Node->isMachineOpcode()) {
     LLVM_DEBUG(errs() << "== "; Node->dump(CurDAG); errs() << "\n");
     Node->setNodeId(-1);
     return;
   }
 

llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.h

 
 class WebAssemblySubtarget;
 
 class WebAssemblyTargetLowering final : public TargetLowering {
 public:
   WebAssemblyTargetLowering(const TargetMachine &TM,
                             const WebAssemblySubtarget &STI);
 
-  enum WasmAddressSpace {
-    // WebAssembly uses the following address spaces:
-    // AS 0 : is the default address space for values in linear memory
-    DEFAULT = 0,
-    // AS 1 : is a non-integral address space for global variables
-    GLOBAL = 1,
-  };
-
 private:
   /// Keep a pointer to the WebAssemblySubtarget around so that we can make the
   /// right decision when generating code for different targets.
   const WebAssemblySubtarget *Subtarget;
 
   AtomicExpansionKind shouldExpandAtomicRMWInIR(AtomicRMWInst *) const override;
   FastISel *createFastISel(FunctionLoweringInfo &FuncInfo,
                            const TargetLibraryInfo *LibInfo) const override;

llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

 //===----------------------------------------------------------------------===//
 
 #include "WebAssemblyISelLowering.h"
 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
 #include "Utils/WebAssemblyUtilities.h"
 #include "WebAssemblyMachineFunctionInfo.h"
 #include "WebAssemblySubtarget.h"
 #include "WebAssemblyTargetMachine.h"
-#include "llvm/CodeGen/Analysis.h"
 #include "llvm/CodeGen/CallingConvLower.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/CodeGen/SelectionDAGNodes.h"
 #include "llvm/CodeGen/WasmEHFuncInfo.h"
case ISD::LOAD:
     return LowerLoad(Op, DAG);
   case ISD::STORE:
     return LowerStore(Op, DAG);
   }
 }
 
 static bool IsWebAssemblyGlobal(SDValue Op) {
   if (const GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Op))
-    return GA->getAddressSpace() ==
-           WebAssemblyTargetLowering::WasmAddressSpace::GLOBAL;
+    return WebAssembly::isObjectAddressSpace(GA->getAddressSpace());
 
   return false;
 }
 
+static Optional<unsigned> IsWebAssemblyLocal(SDValue Op, SelectionDAG &DAG) {
+  const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Op);
+  if (!FI)
+    return None;
+
+  auto &MF = DAG.getMachineFunction();
+  return WebAssembly::getLocalForStackObject(MF, FI->getIndex());
+}
+
 SDValue WebAssemblyTargetLowering::LowerStore(SDValue Op,
                                               SelectionDAG &DAG) const {
   SDLoc DL(Op);
   StoreSDNode *SN = cast<StoreSDNode>(Op.getNode());
   const SDValue &Value = SN->getValue();
   const SDValue &Offset = SN->getOffset();
   const SDValue &Base = SN->getBasePtr();
 
   if (IsWebAssemblyGlobal(Base)) {
     if (!Offset->isUndef())
       report_fatal_error("unexpected offset when storing to webassembly global",
                          false);
 
     SDVTList Tys = DAG.getVTList(MVT::Other);
     SDValue Ops[] = {SN->getChain(), Value, Base};
     return DAG.getMemIntrinsicNode(WebAssemblyISD::GLOBAL_SET, DL, Tys, Ops,
                                    SN->getMemoryVT(), SN->getMemOperand());
   }
 
+  if (Optional<unsigned> Local = IsWebAssemblyLocal(Base, DAG)) {
+    if (!Offset->isUndef())
+      report_fatal_error("unexpected offset when storing to webassembly local",
+                         false);
+
+    SDValue Idx = DAG.getTargetConstant(*Local, Base, MVT::i32);
+    SDVTList Tys = DAG.getVTList(MVT::Other); // The chain.
+    SDValue Ops[] = {SN->getChain(), Idx, Value};
+    return DAG.getNode(WebAssemblyISD::LOCAL_SET, DL, Tys, Ops);
+  }
+
   return Op;
 }
 
 SDValue WebAssemblyTargetLowering::LowerLoad(SDValue Op,
                                              SelectionDAG &DAG) const {
   SDLoc DL(Op);
   LoadSDNode *LN = cast<LoadSDNode>(Op.getNode());
   const SDValue &Base = LN->getBasePtr();
   const SDValue &Offset = LN->getOffset();
 
   if (IsWebAssemblyGlobal(Base)) {
     if (!Offset->isUndef())
       report_fatal_error(
           "unexpected offset when loading from webassembly global", false);
 
     EVT VT = LN->getValueType(0);
     SDValue GlobalGet = DAG.getMemIntrinsicNode(
         WebAssemblyISD::GLOBAL_GET, DL, DAG.getVTList(VT),
         {LN->getChain(), Base}, LN->getMemoryVT(), LN->getMemOperand());
     return DAG.getMergeValues({GlobalGet, LN->getChain()}, DL);
   }
 
+  if (Optional<unsigned> Local = IsWebAssemblyLocal(Base, DAG)) {
+    if (!Offset->isUndef())
+      report_fatal_error(
+          "unexpected offset when loading from webassembly local", false);
+
+    SDValue Idx = DAG.getTargetConstant(*Local, Base, MVT::i32);
+    EVT LocalVT = LN->getValueType(0);
+    SDValue LocalGet = DAG.getNode(WebAssemblyISD::LOCAL_GET, DL, LocalVT,
+                                   {LN->getChain(), Idx});
+    SDValue Result = DAG.getMergeValues({LocalGet, LN->getChain()}, DL);
+    assert(Result->getNumValues() == 2 && "Loads must carry a chain!");
+    return Result;
+  }
+
   return Op;
 }
 
 SDValue WebAssemblyTargetLowering::LowerCopyToReg(SDValue Op,
                                                   SelectionDAG &DAG) const {
   SDValue Src = Op.getOperand(2);
   if (isa<FrameIndexSDNode>(Src.getNode())) {
     // CopyToReg nodes don't support FrameIndex operands. Other targets select

llvm/lib/Target/WebAssembly/WebAssemblyInstrInfo.td

 //===----------------------------------------------------------------------===//
 
 def SDT_WebAssemblyCallSeqStart : SDCallSeqStart<[SDTCisVT<0, iPTR>,
                                                   SDTCisVT<1, iPTR>]>;
 def SDT_WebAssemblyCallSeqEnd :
     SDCallSeqEnd<[SDTCisVT<0, iPTR>, SDTCisVT<1, iPTR>]>;
 def SDT_WebAssemblyBrTable    : SDTypeProfile<0, -1, [SDTCisPtrTy<0>]>;
 def SDT_WebAssemblyArgument   : SDTypeProfile<1, 1, [SDTCisVT<1, i32>]>;
+def SDT_WebAssemblyLocalGet   : SDTypeProfile<1, 1, [SDTCisVT<1, i32>]>;
+def SDT_WebAssemblyLocalSet   : SDTypeProfile<0, 2, [SDTCisVT<0, i32>]>;
 def SDT_WebAssemblyReturn     : SDTypeProfile<0, -1, []>;
 def SDT_WebAssemblyWrapper    : SDTypeProfile<1, 1, [SDTCisSameAs<0, 1>,
                                                      SDTCisPtrTy<0>]>;
 def SDT_WebAssemblyWrapperPIC : SDTypeProfile<1, 1, [SDTCisSameAs<0, 1>,
                                                      SDTCisPtrTy<0>]>;
 def SDT_WebAssemblyThrow      : SDTypeProfile<0, -1, []>;
 def SDT_WebAssemblyCatch      : SDTypeProfile<1, 1, [SDTCisPtrTy<0>]>;
 def SDT_WebAssemblyGlobalGet  : SDTypeProfile<1, 1, [SDTCisPtrTy<1>]>;

 def WebAssemblycallseq_end :
     SDNode<"ISD::CALLSEQ_END", SDT_WebAssemblyCallSeqEnd,
            [SDNPHasChain, SDNPOptInGlue, SDNPOutGlue]>;
 def WebAssemblybr_table : SDNode<"WebAssemblyISD::BR_TABLE",
                                  SDT_WebAssemblyBrTable,
                                  [SDNPHasChain, SDNPVariadic]>;
 def WebAssemblyargument : SDNode<"WebAssemblyISD::ARGUMENT",
                                  SDT_WebAssemblyArgument>;
 def WebAssemblyreturn   : SDNode<"WebAssemblyISD::RETURN",
                                  SDT_WebAssemblyReturn,
                                  [SDNPHasChain, SDNPVariadic]>;
 def WebAssemblywrapper  : SDNode<"WebAssemblyISD::Wrapper",
                                  SDT_WebAssemblyWrapper>;
 def WebAssemblywrapperPIC  : SDNode<"WebAssemblyISD::WrapperPIC",
                                      SDT_WebAssemblyWrapperPIC>;
 def WebAssemblythrow : SDNode<"WebAssemblyISD::THROW", SDT_WebAssemblyThrow,
                               [SDNPHasChain, SDNPVariadic]>;
 def WebAssemblycatch : SDNode<"WebAssemblyISD::CATCH", SDT_WebAssemblyCatch,
                               [SDNPHasChain, SDNPSideEffect]>;
 def WebAssemblyglobal_get :
     SDNode<"WebAssemblyISD::GLOBAL_GET", SDT_WebAssemblyGlobalGet,
            [SDNPHasChain, SDNPMayLoad, SDNPMemOperand]>;
 def WebAssemblyglobal_set :
     SDNode<"WebAssemblyISD::GLOBAL_SET", SDT_WebAssemblyGlobalSet,
            [SDNPHasChain, SDNPMayStore, SDNPMemOperand]>;
+def WebAssemblylocal_get :
+    SDNode<"WebAssemblyISD::LOCAL_GET", SDT_WebAssemblyLocalGet,
+           [SDNPHasChain, SDNPMayLoad]>;
+def WebAssemblylocal_set :
+    SDNode<"WebAssemblyISD::LOCAL_SET", SDT_WebAssemblyLocalSet,
+           [SDNPHasChain, SDNPMayStore]>;
 
 //===----------------------------------------------------------------------===//
 // WebAssembly-specific Operands.
 //===----------------------------------------------------------------------===//
 
 // Default Operand has AsmOperandClass "Imm" which is for integers (and
 // symbols), so specialize one for floats:
 class FPImmAsmOperand<ValueType ty> : AsmOperandClass {
multiclass LOCAL<WebAssemblyRegClass reg, Operand global_op> {
   } // hasSideEffects = 0
   foreach vt = reg.RegTypes in {
     def : Pat<(vt (WebAssemblyglobal_get
                    (WebAssemblywrapper tglobaladdr:$addr))),
               (!cast<NI>("GLOBAL_GET_" # reg) tglobaladdr:$addr)>;
     def : Pat<(WebAssemblyglobal_set
                vt:$src, (WebAssemblywrapper tglobaladdr:$addr)),
               (!cast<NI>("GLOBAL_SET_" # reg) tglobaladdr:$addr, vt:$src)>;
+    def : Pat<(vt (WebAssemblylocal_get (i32 timm:$local))),
+              (!cast<NI>("LOCAL_GET_" # reg) timm:$local)>;
+    def : Pat<(WebAssemblylocal_set timm:$local, vt:$src),
+              (!cast<NI>("LOCAL_SET_" # reg) timm:$local, reg:$src)>;
   }
 }
 defm "" : LOCAL<I32, global_op32>;
 defm "" : LOCAL<I64, global_op64>;  // 64-bit only needed for pointers.
 defm "" : LOCAL<F32, global_op32>;
 defm "" : LOCAL<F64, global_op32>;
 defm "" : LOCAL<V128, global_op32>, Requires<[HasSIMD128]>;
 defm "" : LOCAL<FUNCREF, global_op32>, Requires<[HasReferenceTypes]>;

llvm/lib/Target/WebAssembly/WebAssemblyTargetMachine.cpp

 /// Create an WebAssembly architecture model.
 ///
 WebAssemblyTargetMachine::WebAssemblyTargetMachine(
     const Target &T, const Triple &TT, StringRef CPU, StringRef FS,
     const TargetOptions &Options, Optional<Reloc::Model> RM,
     Optional<CodeModel::Model> CM, CodeGenOpt::Level OL, bool JIT)
     : LLVMTargetMachine(T,
                         TT.isArch64Bit()
-                            ? "e-m:e-p:64:64-i64:64-n32:64-S128-ni:1"
-                            : "e-m:e-p:32:32-i64:64-n32:64-S128-ni:1",
+                            ? "e-m:e-p:64:64-i64:64-n32:64-S128-ni:1-A0:u"
+                            : "e-m:e-p:32:32-i64:64-n32:64-S128-ni:1-A0:u",
                         TT, CPU, FS, Options, getEffectiveRelocModel(RM, TT),
                         getEffectiveCodeModel(CM, CodeModel::Large), OL),
       TLOF(new WebAssemblyTargetObjectFile()) {
   // WebAssembly type-checks instructions, but a noreturn function with a return
   // type that doesn't match the context will cause a check failure. So we lower
   // LLVM 'unreachable' to ISD::TRAP and then lower that to WebAssembly's
   // 'unreachable' instructions which is meant for that case.
   this->Options.TrapUnreachable = true;

llvm/test/CodeGen/WebAssembly/ir-locals.ll

+; RUN: llc < %s --mtriple=wasm32-unknown-unknown -asm-verbose=false | FileCheck %s
+
+%i32_cell = type i32 addrspace(1)*
+%i64_cell = type i64 addrspace(1)*
+%f32_cell = type float addrspace(1)*
+%f64_cell = type double addrspace(1)*
+
+define i32 @ir_local_i32(i32 %arg) {
+ ; CHECK-LABEL: ir_local_i32:
+ ; CHECK-NEXT: .functype ir_local_i32 (i32) -> (i32)
+ %retval = alloca i32, addrspace(1)
+ ; CHECK-NEXT: .local i32
+ store i32 %arg, %i32_cell %retval
+ ; CHECK-NEXT: local.get 0
+ ; CHECK-NEXT: local.set 1
+ %reloaded = load i32, %i32_cell %retval
+ ; The DAG combiner infers that %reloaded is the same as %arg and
+ ; ultimately causes "local.get 0" to be emitted instead of
+ ; "local.get 1".
+ ; CHECK-NEXT: local.get 0
+ ret i32 %reloaded
+ ; CHECK-NEXT: end_function
+}
+
+define i64 @ir_local_i64(i64 %arg) {
+ ; CHECK-LABEL: ir_local_i64:
+ ; CHECK-NEXT: .functype ir_local_i64 (i64) -> (i64)
+ %retval = alloca i64, addrspace(1)
+ ; CHECK-NEXT: .local i64
+ store i64 %arg, %i64_cell %retval
+ ; CHECK-NEXT: local.get 0
+ ; CHECK-NEXT: local.set 1
+ %reloaded = load i64, %i64_cell %retval
+ ; See note in ir_local_i32.
+ ; CHECK-NEXT: local.get 0
+ ret i64 %reloaded
+ ; CHECK-NEXT: end_function
+}
+
+define float @ir_local_f32(float %arg) {
+ ; CHECK-LABEL: ir_local_f32:
+ ; CHECK-NEXT: .functype ir_local_f32 (f32) -> (f32)
+ %retval = alloca float, addrspace(1)
+ ; CHECK-NEXT: .local f32
+ ; CHECK-NEXT: local.get 0
+ ; CHECK-NEXT: local.set 1
+ store float %arg, %f32_cell %retval
+ ; See note in ir_local_i32.
+ ; CHECK-NEXT: local.get 0
+ %reloaded = load float, %f32_cell %retval
+ ; CHECK-NEXT: end_function
+ ret float %reloaded
+}
+
+define double @ir_local_f64(double %arg) {
+ ; CHECK-LABEL: ir_local_f64:
+ ; CHECK-NEXT: .functype ir_local_f64 (f64) -> (f64)
+ %retval = alloca double, addrspace(1)
+ ; CHECK-NEXT: .local f64
+ ; CHECK-NEXT: local.get 0
+ ; CHECK-NEXT: local.set 1
+ store double %arg, %f64_cell %retval
+ ; CHECK-NEXT: local.get 0
+ %reloaded = load double, %f64_cell %retval
+ ; CHECK-NEXT: end_function
+ ret double %reloaded
+}
+
+define void @ir_unreferenced_local() {
+ ; CHECK-LABEL: ir_unreferenced_local:
+ ; CHECK-NEXT: .functype ir_unreferenced_local () -> ()
+ %unused = alloca i32, addrspace(1)
+ ; CHECK-NEXT: .local i32
+ ret void
+ ; CHECK-NEXT: end_function
+}