llvm dev - May 2021 - Mini-RFC: Support for off-heap definitions

Hello all,

This is a mini-RFC for supporting off-heap definitions, motivated by the
WebAssembly target.  This will allow some global and local variables to
be given addresses that are not in main memory and not in registers --
instead they are in named locations managed by the WebAssembly run-time.

Mostly we lean on non-integral address spaces to make this work, but a
couple of core things need loosening for this to work:

  1. Allowing alloca in multiple address spaces

  2. Assigning a special TargetStackID::Value to these allocations when
     putting static alloca's into MachineFrameInfo

Not much needs to change, but it's sufficiently different from most
targets that I thought I'd send a heads-up.


# Motivation

The WebAssembly target usually compiles global and local variables
definitions to memory allocations.  Unless optimized away, a global
variable denotes an address in memory, in the same address space shared
by other static data, the heap, and the stack.  Similarly, a local
variable starts life as an alloca, and unless lifted to an SSA value by
SROA (as is usually the case), a local variable definition will
eventually lower to an SP-relative address on the stack.

However, the WebAssembly target also supports named definitions that are
not part of main memory.  A WebAssembly module can contain named global
variables, and each function can have named local variables.  These
variables are typed and are accessed only by immediate index; they can't
be addressed by a pointer.

It would be nice if we could support these definitions at the IR level,
in the WebAssembly target.  For our target this has two main advantages:

  1. It allows us to make definitions that can't be accessed
     accidentally at run-time via forging a pointer, as global.ref /
     global.set / local.ref / local.set refer to their operand only via
     an immediate index.

  2. It would allow us to have global and local variables of types that
     can't be written in main memory.  WebAssembly has two kinds of
     types: [number types and reference
     types](https://webassembly.github.io/spec/core/syntax/types.html).
     The former can be written to main memory.  The latter cannot, as
     their representation is opaque.  Reference types are used notably
     as a way to represent values managed the "host" for the
WebAssembly
     program, i.e. JavaScript objects in a web browser.
     
The long-range vision is to allow C/C++ global and local variable
definitions of reference-typed values.  As these definitions can't be
addressed by pointers in memory, we'd apply similar restrictions as
those that the ARM C Language Extensions (ACLE) applies to SVE values in
the front-end.  We are not yet ready to post an RFC for this, but for
those interested, we do have an [early draft design
document](https://docs.google.com/document/d/1aVX0tQChxA2Tlno2KmEUjdruLoNgpwzV5Kv335HvNmI/edit#).


# Changes

## Globals: all good

For off-heap globals, nothing needs to change in core LLVM.  We use a
non-integral address space for these definitions, and lower them
appropriately during instruction selection.  See
https://reviews.llvm.org/D101608 if you are interested.

(It sure would be nice to be able to say `addrspace(GLOBAL)` instead of
`addrspace(1)` though!!)

## https://reviews.llvm.org/D101045: Multiple alloca address spaces

In D101045, we allow a target to specify multiple address spaces that
are valid for alloca.

Recall that right now, by default the result of alloca is in address
space 0, though the target can override that default.  If a target's
datalayout is:

  target datalayout = "e-m:e-p:64:64-i64:64-n32:64-S128-ni:1"

it's the same as

  target datalayout = "e-m:e-p:64:64-i64:64-n32:64-S128-ni:1-A0"

In this patch we allow multiple address spaces.  So to allow alloca also
in address space 1, you can do:

  target datalayout = "e-m:e-p:64:64-i64:64-n32:64-S128-ni:1-A0:1"

## https://reviews.llvm.org/D101140: A TargetStackID for wasm locals

It's fine to associate an abstract FrameIndex to a static alloca in
address space 1, but it would be an error to try to reserve memory for
these objects.  Therefore for the WebAssembly target, we add a WasmLocal
TargetStackID.  It seems like there may be a more general concept here
for systems that have locals that are not addressable in the way that
main memory is, but in the patch it's just named WasmLocal.  Having a
new stack ID appears to be sufficient.

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 per-object hook, and there isn't even a hook that runs between
then and DAG building time, though, so instead the patch hoists stack
objects lazily when they are first used, and then comprehensively after
the DAG is built.  But we have a solution that works for now.


# Conclusion

So just a couple small changes, but they are sufficiently weird that I
thought I'd reach out to see if there's any feedback.  Thanks for
reading!

Andy