[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

101

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

Unintentional whitespace change?

llvm/lib/Target/WebAssembly/WebAssemblyMachineFunctionInfo.h

107

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

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

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 ↗

(On Diff #342669)

Is there a good test to demonstrate this change in?

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

34–36 ↗

(On Diff #342669)

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 ↗

(On Diff #342669)

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 ↗

(On Diff #342669)

Done in ir-locals-stackid.ll

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

34–36 ↗

(On Diff #342669)

👍

63–64 ↗

(On Diff #342669)

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

17–20 ↗

(On Diff #346990)

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

17–20 ↗

(On Diff #346990)

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/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/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/WebAssemblyISelLowering.h

 
 class WebAssemblySubtarget;
 
 class WebAssemblyTargetLowering final : public TargetLowering {
 public:
   WebAssemblyTargetLowering(const TargetMachine &TM,
                             const WebAssemblySubtarget &STI);
 
-  enum WasmAddressSpace {
-    DEFAULT = 0,
-    EXTERNREF = 1,
-    EXTERNREF_GLOBAL = 2,
-    FUNCREF = 3,
-    FUNCREF_GLOBAL = 4,
-  };
-
-  // WebAssembly uses 5 different address spaces [0, 4]:
-  // AS 0 : is the default address space
-  // AS 1 : is a non-integral address space for externref values
-  // AS 2 : is an integral address space for globals of externref values
-  // AS 3 : is an non-integral address space for funcref values
-  // AS 4 : is an integral address spaces for globals of funcref values
-  MVT getPointerTy(const DataLayout &DL, uint32_t AS = 0) const override {
-    if (AS == WasmAddressSpace::EXTERNREF)
-      return MVT::externref;
-    else if (AS == WasmAddressSpace::FUNCREF)
-      return MVT::funcref;
-    return TargetLowering::getPointerTy(DL, AS);
-  }
+  // Pointers in well-known non-default address spaces lower to reference types,
+  // not linear memory pointers.
+  MVT getPointerTy(const DataLayout &DL, uint32_t AS = 0) const override;
 
 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;
   MVT getScalarShiftAmountTy(const DataLayout &DL, EVT) const override;
   MachineBasicBlock *
   EmitInstrWithCustomInserter(MachineInstr &MI,
                               MachineBasicBlock *MBB) const override;
   const char *getTargetNodeName(unsigned Opcode) const override;
   std::pair<unsigned, const TargetRegisterClass *>
   getRegForInlineAsmConstraint(const TargetRegisterInfo *TRI,
                                StringRef Constraint, MVT VT) const override;
   bool isCheapToSpeculateCttz() const override;
   bool isCheapToSpeculateCtlz() const override;
   bool isLegalAddressingMode(const DataLayout &DL, const AddrMode &AM, Type *Ty,
                              unsigned AS,
                              Instruction *I = nullptr) const override;
-  bool isExternrefGlobal(SDValue Op) const;
-  bool isFuncrefGlobal(SDValue Op) const;
-  bool isFuncref(const Value *Op) const;
   bool allowsMisalignedMemoryAccesses(EVT, unsigned AddrSpace, Align Alignment,
                                       MachineMemOperand::Flags Flags,
                                       bool *Fast) const override;
   bool isIntDivCheap(EVT VT, AttributeList Attr) const override;
   bool isVectorLoadExtDesirable(SDValue ExtVal) const override;
   EVT getSetCCResultType(const DataLayout &DL, LLVMContext &Context,
                          EVT VT) const override;
   bool getTgtMemIntrinsic(IntrinsicInfo &Info, const CallInst &I,

llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

WebAssemblyTargetLowering::WebAssemblyTargetLowering(
   setLibcallName(RTLIB::RETURN_ADDRESS, "emscripten_return_address");
 
   // Always convert switches to br_tables unless there is only one case, which
   // is equivalent to a simple branch. This reduces code size for wasm, and we
   // defer possible jump table optimizations to the VM.
   setMinimumJumpTableEntries(2);
 }
 
+// With the reference-types feature, WebAssembly programs can have a mix of
+// pointers to data in linear memory and "opaque" data managed by the run-time.
+// For example, in a web embedding, these values might be garbage-collected
+// JavaScript values from the host.  In LLVM we allow references to
+// reference-typed values to be represented as pointers on the IR level, in
+// order to represent mutable global variables (which lower to WebAssembly
+// globals), global arrays (which lower to WebAssembly tables), and local
+// variables (which lower to WebAssembly locals).
+//
+// On the IR level, we distinguish these different kinds of
+// pointers-to-reference-types by putting the pointers into different address
+// spaces.  When translating an IR pointer to an MVT, the address space is the
+// only way to choose an MVT; notably, we don't have the llvm::PointerType.
+MVT WebAssemblyTargetLowering::getPointerTy(const DataLayout &DL,
+                                            uint32_t AS) const {
+  switch (AS) {
+  case WebAssembly::WASM_ADDRESS_SPACE_EXTERNREF:
+    // Externref values, punned as pointers in a specific address space.
+    return MVT::externref;
+  case WebAssembly::WASM_ADDRESS_SPACE_EXTERNREF_GLOBAL:
+  case WebAssembly::WASM_ADDRESS_SPACE_EXTERNREF_LOCAL:
+    // Externref locations.  Abuse MVT::externref because they really aren't
+    // normal pointers.
+    return MVT::externref;
+  case WebAssembly::WASM_ADDRESS_SPACE_FUNCREF:
+    // Funcref values.
+    return MVT::funcref;
+  case WebAssembly::WASM_ADDRESS_SPACE_FUNCREF_GLOBAL:
+  case WebAssembly::WASM_ADDRESS_SPACE_FUNCREF_LOCAL:
+    // Funcref locations, as in EXTERNREF_GLOBAL / EXTERNREF_LOCAL.
+    return MVT::funcref;
+  default:
+    return TargetLowering::getPointerTy(DL, AS);
+  }
+}
+
 TargetLowering::AtomicExpansionKind
 WebAssemblyTargetLowering::shouldExpandAtomicRMWInIR(AtomicRMWInst *AI) const {
   // We have wasm instructions for these
   switch (AI->getOperation()) {
   case AtomicRMWInst::Add:
   case AtomicRMWInst::Sub:
   case AtomicRMWInst::And:
   case AtomicRMWInst::Or:
return CallConv == CallingConv::C || CallConv == CallingConv::Fast ||
          CallConv == CallingConv::Cold ||
          CallConv == CallingConv::PreserveMost ||
          CallConv == CallingConv::PreserveAll ||
          CallConv == CallingConv::CXX_FAST_TLS ||
          CallConv == CallingConv::WASM_EmscriptenInvoke ||
          CallConv == CallingConv::Swift;
 }
 
+static bool IsFuncref(const Value *Op) {
+  const Type *Ty = Op->getType();
+
+  return isa<PointerType>(Ty) && Ty->getPointerAddressSpace() ==
+                                     WebAssembly::WASM_ADDRESS_SPACE_FUNCREF;
+}
+
 SDValue
 WebAssemblyTargetLowering::LowerCall(CallLoweringInfo &CLI,
                                      SmallVectorImpl<SDValue> &InVals) const {
   SelectionDAG &DAG = CLI.DAG;
   SDLoc DL = CLI.DL;
   SDValue Chain = CLI.Chain;
   SDValue Callee = CLI.Callee;
   MachineFunction &MF = DAG.getMachineFunction();
if (In.Flags.isInConsecutiveRegsLast())
            "WebAssembly hasn't implemented cons regs last return values");
     // Ignore In.getNonZeroOrigAlign() because all our arguments are passed in
     // registers.
     InTys.push_back(In.VT);
   }
 
   // Lastly, if this is a call to a funcref we need to add an instruction
   // table.set to the chain and transform the call.
-  if (CLI.CB && isFuncref(CLI.CB->getCalledOperand())) {
+  if (CLI.CB && IsFuncref(CLI.CB->getCalledOperand())) {
     // In the absence of function references proposal where a funcref call is
     // lowered to call_ref, using reference types we generate a table.set to set
     // the funcref to a special table used solely for this purpose, followed by
     // a call_indirect. Here we just generate the table set, and return the
     // SDValue of the table.set so that LowerCall can finalize the lowering by
     // generating the call_indirect.
     SDValue Chain = Ops[0];
 
case ISD::FP_TO_UINT_SAT:
     return LowerFP_TO_INT_SAT(Op, DAG);
   case ISD::LOAD:
     return LowerLoad(Op, DAG);
   case ISD::STORE:
     return LowerStore(Op, DAG);
   }
 }
 
-bool WebAssemblyTargetLowering::isExternrefGlobal(SDValue Op) const {
+static Optional<MVT> GetGlobalReferenceType(SDValue Op) {
   const GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Op);
-  if (!GA || GA->getAddressSpace() != WasmAddressSpace::EXTERNREF_GLOBAL)
-    return false;
+  if (!GA)
+    return None;
 
-  return true;
+  switch (GA->getAddressSpace()) {
+  case WebAssembly::WASM_ADDRESS_SPACE_FUNCREF_GLOBAL:
+    return MVT(MVT::funcref);
+  case WebAssembly::WASM_ADDRESS_SPACE_EXTERNREF_GLOBAL:
+    return MVT(MVT::externref);
+  default:
+    return None;
+  }
 }
 
-bool WebAssemblyTargetLowering::isFuncrefGlobal(SDValue Op) const {
-  const GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Op);
-  if (!GA || GA->getAddressSpace() != WasmAddressSpace::FUNCREF_GLOBAL)
+static bool ResolveLocal(SDValue Op, SelectionDAG &DAG, MVT *VT,
+                         unsigned *Local) {
+  const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Op);
+  if (!FI)
     return false;
 
-  return true;
-}
+  int FrameIndex = FI->getIndex();
+  auto &MFI = DAG.getMachineFunction().getFrameInfo();
+  const AllocaInst *AI = MFI.getObjectAllocation(FrameIndex);
 
-bool WebAssemblyTargetLowering::isFuncref(const Value *Op) const {
-  const Type *Ty = Op->getType();
+  if (!AI)
+    return false;
+
+  switch (AI->getType()->getAddressSpace()) {
+  case WebAssembly::WASM_ADDRESS_SPACE_FUNCREF_LOCAL:
+    *VT = MVT::funcref;
+    break;
+  case WebAssembly::WASM_ADDRESS_SPACE_EXTERNREF_LOCAL:
+    *VT = MVT::externref;
+    break;
+  default:
+    return false;
+  }
 
-  return isa<PointerType>(Ty) &&
-         Ty->getPointerAddressSpace() == WasmAddressSpace::FUNCREF;
+  auto *FuncInfo = DAG.getMachineFunction().getInfo<WebAssemblyFunctionInfo>();
+  *Local = FuncInfo->getLocalForStackObject(FrameIndex, *VT);
+  // Mark stack object as dead, as it will be replaced by the local.
+  if (!MFI.isDeadObjectIndex(FrameIndex))
+    MFI.RemoveStackObject(FrameIndex);
+  return true;
 }
 
 SDValue WebAssemblyTargetLowering::LowerStore(SDValue Op,
                                               SelectionDAG &DAG) const {
   SDLoc DL(Op);
 
   StoreSDNode *SN = cast<StoreSDNode>(Op.getNode());
-
   const SDValue &Value = SN->getValue();
-
-  // Expect Offset to be undef for externref global stores
-  const SDValue &Offset = SN->getOffset();
-  if (!Offset->isUndef())
-    return Op;
-
-  // Expect Base to be an externref GlobalAddress
   const SDValue &Base = SN->getBasePtr();
-  if (!isExternrefGlobal(Base) && !isFuncrefGlobal(Base))
-    return Op;
 
+  if (SN->getOffset()->isUndef()) {
+    if (Optional<MVT> VT = GetGlobalReferenceType(Base)) {
       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());
     }
 
+    MVT LocalVT;
+    unsigned LocalIdx;
+    if (ResolveLocal(Base, DAG, &LocalVT, &LocalIdx)) {
+      SDValue Idx = DAG.getTargetConstant(LocalIdx, 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();
 
-  // Check Base is a Global Address
-  if (!isExternrefGlobal(Base) && !isFuncrefGlobal(Base))
-    return Op;
-
-  // Check Offset if undef
-  const SDValue &Offset = LN->getOffset();
-  if (!Offset->isUndef())
-    return Op;
-
-  EVT VT = isExternrefGlobal(Base) ? MVT::externref : MVT::funcref;
-
+  if (LN->getOffset()->isUndef()) {
+    if (Optional<MVT> VT = GetGlobalReferenceType(Base)) {
       SDValue GlobalGet = DAG.getMemIntrinsicNode(
-      WebAssemblyISD::GLOBAL_GET, DL, DAG.getVTList(VT), {LN->getChain(), Base},
-      LN->getMemoryVT(), LN->getMemOperand());
+          WebAssemblyISD::GLOBAL_GET, DL, DAG.getVTList(*VT),
+          {LN->getChain(), Base}, LN->getMemoryVT(), LN->getMemOperand());
       SDValue Result = DAG.getMergeValues({GlobalGet, LN->getChain()}, DL);
       assert(Result->getNumValues() == 2 && "Loads must carry a chain!");
+      return Result;
+    }
 
+    MVT LocalVT;
+    unsigned LocalIdx;
+    if (ResolveLocal(Base, DAG, &LocalVT, &LocalIdx)) {
+      SDValue Idx = DAG.getTargetConstant(LocalIdx, Base, MVT::i32);
+      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
     // the FI to some LEA-like instruction, but since we don't have that, we
     // need to insert some kind of instruction that can take an FI operand and
return Op.getNode()->getNumValues() == 1
                                                            : SDValue());
   }
   return SDValue();
 }
 
 SDValue WebAssemblyTargetLowering::LowerFrameIndex(SDValue Op,
                                                    SelectionDAG &DAG) const {
   int FI = cast<FrameIndexSDNode>(Op)->getIndex();
+  assert(!DAG.getMachineFunction().getFrameInfo().isDeadObjectIndex(FI));
   return DAG.getTargetFrameIndex(FI, Op.getValueType());
 }
 
 SDValue WebAssemblyTargetLowering::LowerRETURNADDR(SDValue Op,
                                                    SelectionDAG &DAG) const {
   SDLoc DL(Op);
 
   if (!Subtarget->getTargetTriple().isOSEmscripten()) {

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>]>;
 
 //===----------------------------------------------------------------------===//
 // WebAssembly-specific DAG Nodes.
 //===----------------------------------------------------------------------===//
 
 def WebAssemblycallseq_start :
     SDNode<"ISD::CALLSEQ_START", SDT_WebAssemblyCallSeqStart,
            [SDNPHasChain, SDNPOutGlue]>;
 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 WebAssemblylocalGet : SDNode<"WebAssemblyISD::LOCAL_GET",
+                                 SDT_WebAssemblyLocalGet,
+                                 [SDNPHasChain, SDNPMayLoad]>;
+def WebAssemblylocalSet : SDNode<"WebAssemblyISD::LOCAL_SET",
+                                 SDT_WebAssemblyLocalSet,
+                                 [SDNPHasChain, SDNPMayStore]>;
 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,

llvm/lib/Target/WebAssembly/WebAssemblyInstrRef.td

defm REF_NULL_#reg : I<(outs reg:$res), (ins HeapType:$heaptype),
                        Requires<[HasReferenceTypes]>;
   defm SELECT_#reg: I<(outs reg:$dst), (ins reg:$lhs, reg:$rhs, I32:$cond),
                       (outs), (ins),
                       [(set reg:$dst,
                         (select I32:$cond, reg:$lhs, reg:$rhs))],
                       vt#".select\t$dst, $lhs, $rhs, $cond",
                       vt#".select", 0x1b>,
                     Requires<[HasReferenceTypes]>;
+
 }
 
 defm "" : REF_I<FUNCREF, funcref>;
 defm "" : REF_I<EXTERNREF, externref>;
 
 foreach reg = [FUNCREF, EXTERNREF] in {
 def : Pat<(select (i32 (setne I32:$cond, 0)), reg:$lhs, reg:$rhs),
           (!cast<Instruction>("SELECT_"#reg) reg:$lhs, reg:$rhs, I32:$cond)>;
 def : Pat<(select (i32 (seteq I32:$cond, 0)), reg:$lhs, reg:$rhs),
           (!cast<Instruction>("SELECT_"#reg) reg:$rhs, reg:$lhs, I32:$cond)>;
+
+  // Legalization will lower reference-typed alloca to locals, and lower
+  // their uses to WebAssemblyISD::LOCAL_GET /
+  // WebAssemblyISD::LOCAL_SET; see WebAssemblyTargetLowering::LowerLoad
+  // and WebAssemblyTargetLowering::LowerStore.  These patterns then
+  // selct the corresponding machine instructions.
+  foreach vt = reg.RegTypes in {
+    def : Pat<(vt (WebAssemblylocalGet (i32 timm:$local))),
+              (!cast<NI>("LOCAL_GET_" # reg) timm:$local)>,
+          Requires<[HasReferenceTypes]>;
+    def : Pat<(WebAssemblylocalSet timm:$local, vt:$src),
+              (!cast<NI>("LOCAL_SET_" # reg) timm:$local, reg:$src)>,
+          Requires<[HasReferenceTypes]>;
+  }
 }

llvm/lib/Target/WebAssembly/WebAssemblyMachineFunctionInfo.h

 /// WebAssembly-specific information for each MachineFunction.
 class WebAssemblyFunctionInfo final : public MachineFunctionInfo {
   const MachineFunction &MF;
 
   std::vector<MVT> Params;
   std::vector<MVT> Results;
   std::vector<MVT> Locals;
 
+  DenseMap<int, unsigned> FrameIndex2Local;
+
   /// 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)
void clearParamsAndResults() {
     Results.clear();
   }
 
   void setNumLocals(size_t NumLocals) { Locals.resize(NumLocals, MVT::i32); }
   void setLocal(size_t i, MVT VT) { Locals[i] = VT; }
   void addLocal(MVT VT) { Locals.push_back(VT); }
   const std::vector<MVT> &getLocals() const { return Locals; }
 
+  unsigned getLocalForStackObject(int FrameIndex, MVT VT) {
+    const auto &Iter = FrameIndex2Local.find(FrameIndex);
+    unsigned LocalIdx;
+    if (Iter == FrameIndex2Local.end()) {
+      LocalIdx = Locals.size();
+      // Add an entry that records the stack object at FrameIndex as being
+      // replaced by the WebAssembly local with index LocalIdx.  The caller is
+      // responsible for marking the stack object as dead in the frame.
+      FrameIndex2Local.insert(std::make_pair(FrameIndex, LocalIdx));
+      addLocal(VT);
+    } else {
+      LocalIdx = Iter->second;
+    }
+    return LocalIdx + Params.size();
+  }
+
   unsigned getVarargBufferVreg() const {
     assert(VarargVreg != -1U && "Vararg vreg hasn't been set");
     return VarargVreg;
   }
   void setVarargBufferVreg(unsigned Reg) { VarargVreg = Reg; }
 
   unsigned getBasePointerVreg() const {
     assert(BasePtrVreg != -1U && "Base ptr vreg hasn't been set");

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()
-                            ? (hasReferenceTypes(FS)
-                                   ? "e-m:e-p:64:64-i64:64-n32:64-S128-ni:1:3"
-                                   : "e-m:e-p:64:64-i64:64-n32:64-S128")
-                            : (hasReferenceTypes(FS)
-                                   ? "e-m:e-p:32:32-i64:64-n32:64-S128-ni:1:3"
-                                   : "e-m:e-p:32:32-i64:64-n32:64-S128"),
-                        TT, CPU, FS, Options, getEffectiveRelocModel(RM, TT),
-                        getEffectiveCodeModel(CM, CodeModel::Large), OL),
+    : LLVMTargetMachine(
+          T,
+                     ? "e-m:e-p:64:64-i64:64-n32:64-S128-ni:1:3:5:6-A0:u"
+                     ? "e-m:e-p:32:32-i64:64-n32:64-S128-ni:1:3:5:6-A0:u"
       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;
 
   // WebAssembly treats each function as an independent unit. Force

llvm/lib/Target/WebAssembly/WebAssemblyUtilities.h

 class MCContext;
 class MCSymbolWasm;
 class StringRef;
 class WebAssemblyFunctionInfo;
 class WebAssemblySubtarget;
 
 namespace WebAssembly {
 
+// FIXME: Renumber so that EXTERNREF_LOCAL is contiguous with EXTERNREF and
+// EXTERNREF_GLOBAL.
+// An unscoped enum, as address spaces are often produced and consumed as
+// uint32_t or unsigned.
+enum WasmAddressSpace {
+  // Default address space, for pointers to unmanaged data in linear memory
+  // (stack, heap, data).
+  WASM_ADDRESS_SPACE_DEFAULT = 0,
+  // A non-integral address space used to represent externref values.  We use a
+  // separate address space to prevent LLVM from attempting to write them to
+  // linear memory.  Because you can't add an offset to one externref value to
+  // get a new externref value, we mark this address space as non-integral.
+  WASM_ADDRESS_SPACE_EXTERNREF = 1,
+  // An integral address space for static-storage-duration locations of
+  // externref values.  This address space is integral, to allow for tables to
+  // be represented as arrays in IR.
+  WASM_ADDRESS_SPACE_EXTERNREF_GLOBAL = 2,
+  // A non-integral address space for automatic-storage-duration locations of
+  // externref values (local variables).  Non-integral because having the
+  // location of one local doesn't give you access to any other local.
+  WASM_ADDRESS_SPACE_EXTERNREF_LOCAL = 5,
+  // Same as above, but for funcref values.
+  WASM_ADDRESS_SPACE_FUNCREF = 3,
+  WASM_ADDRESS_SPACE_FUNCREF_GLOBAL = 4,
+  WASM_ADDRESS_SPACE_FUNCREF_LOCAL = 6,
+};
+
 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/test/CodeGen/WebAssembly/externref-alloca.ll

+; RUN: llc < %s -mtriple=wasm32-unknown-unknown -asm-verbose=false -mattr=+reference-types | FileCheck %s
+
+;; Address space 1 is for externref values, and address space 5 is for
+;; externref-valued local variables.
+
+%extern = type opaque
+%externref = type %extern addrspace(1)*
+%externref_local = type %externref addrspace(5)*
+
+; CHECK-LABEL: alloca_externref:
+define %externref @alloca_externref(%externref %param) {
+ ; CHECK-NEXT: .functype alloca_externref (externref) -> (externref)
+ %retval = alloca %externref, addrspace(5)
+ ; CHECK-NEXT: .local externref
+ ; CHECK-NEXT: local.get 0
+ ; CHECK-NEXT: local.set 1
+ store %externref %param, %externref_local %retval
+ ; CHECK-NEXT: local.get 1
+ %reloaded = load %externref, %externref_local %retval
+ ; CHECK-NEXT: end_function
+ ret %externref %reloaded
+}