Initial work on a "VM" for Slang code (#189)

At a high level, this commit adds two things:

1. A "bytecode" format for serializing Slang IR instructions and related structure (functions, "registers")

2. A virtual machine that can load and then execute code in that bytecode format.

The reason for kicking off this work right now is that we *need* a way to run tests on Slang code generation that doesn't rely on having a GPU present (given that our CI runs on VM instances without GPUs), nor on textual comparison to the output of other compilers. With these features I've implemented a slapdash `slang-eval-test` test fixture that can run a (trivial) compute shader to very our compilation flow through to bytecode.

Some key design constraints/challenges:

- The bytecode format should be "position independent" so that a user can just load a blob of data and then inspect it without having to deserialize into another format, allocate memory, etc. Eventually the bytecode format might be a replacement for out current reflection API (we used to base reflection off a similar format, but the cost/benefit wasn't there at the time and we switched to just using the AST).

- The VM should be able to execute bytecode functions without doing any per-operation translation, JIT, etc. (translation of more coarse-grained symbols is okay). For now the VM is just being used to run tests, but eventually I'd like it to be viable for:
  - Running Slang-based code in the context of the compiler itself. This starts with stuff like constant-folding in the front-end, but could expand to more general metaprogramming features.
  - Running Slang-based ocde within a runtime application (e.g., a game engine) that wants to be able to run things like "parameter shader" code, or even just evaluate compute-like code on CPU (e.g., when supporting particles on both CPU and GPU).

- Finally, the bytecode format should ideally be able to round-trip back to the IR without unacceptable loss of information. This requirement and the previous one play off of each other, because things like a traditional SSA phi operation is ugly when you have to actually *execute* it. This doesn't matter right now when we don't have SSA yet, but it might be part of the decision-making here.

The actual implementation is centralized in `bytecode.{h,cpp}` and `vm.{h.cpp}`.
Big picture notes:

- The space of opcodes is shared between IR and bytecode (BC), with the hope that this makes translation of operations between the two easy.

- The actual bytecode instruction stream relies on a variable-length encoding for integer values, including opcodes and operand numbers, so that the common case is single-byte encoding.
  - In the long term I intend to have a rule that if you use a single-byte encoding for an opcode, then all operands are required to use single-byte encodings too. Operations that need multi-byte operands would then be forced to use a multi-byte encoding of the op, and would be sent down a slower path in the interpeter.

- The "bytecode"'s outer structure is based on ordinary data structures linked with pointers, but they are "relative pointers" so the actual structure is position-independent.

- There are two main kinds of operands: registers and "constants." An operand is a signed integer where non-negatie values indicate registers (with `index == operandVal`) and negative values indicate constants (with `index == ~operandVal`).

  - Registers are stored in the "stack frame" for a VM function call, and each has a fixed offset based on the size of the type and those that come before it. Conceptually, registers are allowed to overlap if they aren't live at the same time, and we manage this with a simple stack model: every register is supposed to identify the register that comes directly before it (this isn't implemented yet).

  - "Constants" are more realistically a representation of "captured" values, but they are currently also how constants come in. Basically we can use a compact range of indices in the bytecode for a function, and each of these indices indirectly refers to some value in the next outer scope.

- The actual encoding of bytecode instructions right now is largely ad-hoc and very wasteful (we encode the type on everything, and we also encode everything as if it had varargs).

- In some cases, an instruction needs to know the types of the values involved (e.g., because it needs to load an array element, which means copying a number of bytes based on the size). The way the VM works we have types attached to our registers, so we currently get sneaky and look at those types in some ops. Longer term is makes sense to encode the required type info directly in the BC.

- There's a whole lot of hand-waving going on with how the actual top-level bytecode module gets loaded, because of the way we currently treat the top-level module as an instruction stream in the IR. This means that we try to represent the loaded module as a "stack frame" for a call to the module as a function, but that approach as serious problems, and isn't realistically what we want to do.

1 files changed, 187 insertions, 0 deletions

diff --git a/source/slang/bytecode.h b/source/slang/bytecode.h
new file mode 100644
index 000000000..e073763cf
--- /dev/null
+++ b/source/slang/bytecode.h
@@ -0,0 +1,187 @@
+// bytecode.h
+#ifndef SLANG_BYTECODE_H_INCLUDED
+#define SLANG_BYTECODE_H_INCLUDED
+
+// This file defines a "bytecode" format for storing shader code
+// that has been generated via the Slang IR. The bytecode has
+// two main goals, that can end up in a bit of conflict:
+//
+// 1) It is the official serialized form of the Slang IR, and
+//    so it is of some importance that constructs in the IR be
+//    able to round-trip through the bytecode.
+//
+// 2) It should support being directly executed/interpreted,
+//    so that Slang code can be executed on CPUs when
+//    performance isn't critical (or when a JIT just isn't
+//    an option).
+//
+
+#include "../core/basic.h"
+
+namespace Slang
+{
+template<typename T>
+struct BytecodeGenerationPtr;
+
+// A "pointer" stored in a serialized bytecode file, which
+// is represented as a byte offset relative to itself.
+//
+template<typename T>
+struct BCPtr
+{
+    typedef int32_t RawVal;
+
+    RawVal rawVal;
+
+    BCPtr() : rawVal(0) {}
+
+    BCPtr(T* ptr)
+        : rawVal(0)
+    {
+        *this = ptr;
+    }
+
+    BCPtr(BCPtr<T> const& ptr)
+        : rawVal(0)
+    {
+        *this = ptr.getPtr();
+    }
+
+    void operator=(BCPtr<T> const& ptr)
+    {
+        *this = ptr.getPtr();
+    }
+
+    void operator=(T* ptr)
+    {
+        if (ptr)
+        {
+            rawVal = (char*)ptr - (char*)this;
+        }
+        else
+        {
+            rawVal = 0;
+        }
+    }
+
+    operator T*() const { return getPtr(); }
+
+    T* getPtr() const
+    {
+        if(!rawVal) return nullptr;
+        return (T*)((char const*)this + rawVal);
+    }
+};
+
+struct BCType
+{
+    uint32_t op;
+};
+
+struct BCSymbol
+{
+    // The opcode that was used to define
+    // this symbol; used to categorize things
+    uint32_t op;
+
+    // The type of the symbol is represent
+    // as an index into the global-scope symbol
+    // list of the module.
+    //
+    // Note: This currently precludes having
+    // a register with a type that is not
+    // statically determined, but that is
+    // probably okay.
+    uint32_t   typeGlobalID;
+
+    // The name of this symbol (which might
+    // be a mangled name at some point,
+    // so it is really only meant to be
+    // used for linkage...)
+    BCPtr<char> name;
+};
+
+typedef uint8_t BCOp;
+
+struct BCReg : BCSymbol
+{
+    // The index of the variable/register
+    // that should be stored immediately
+    // preceding this one.
+    uint32_t    previousVarIndexPlusOne;
+};
+
+struct BCConst
+{
+    // The ID of the symbol in the global
+    // scope that we are trying to refer
+    // to.
+    //
+    // TODO: eventually, if we have general
+    // nesting, then this might be the
+    // entry in the outer scope that
+    // is being referenced.
+    uint32_t    globalID;
+};
+
+struct BCBlock
+{
+    // The start of the bytecode for this block
+    BCPtr<BCOp> code;
+
+    // The list of parameters of the block
+    uint32_t        paramCount;
+    BCPtr<BCReg>    params;
+};
+
+struct BCFunc : BCSymbol
+{
+    // A list of "registers" used to hold
+    // intermediate values during execution
+    // of this function.
+    uint32_t        regCount;
+    BCPtr<BCReg>    regs;
+
+    // The basic blocks of the function
+    uint32_t        blockCount;
+    BCPtr<BCBlock>  blocks;
+
+    // A list of "constants" which are values
+    // from the global scope that this function
+    // wants to be able to refer to. We could
+    // just encode global values directly,
+    // but this would make the encoding less dense.
+    uint32_t        constCount;
+    BCPtr<BCConst>  consts;
+
+    // Data for "nested" symbols (e.g., a function
+    // nested inside this function).
+    uint32_t                    nestedSymbolCount;
+    BCPtr<BCPtr<BCSymbol>>      nestedSymbols;
+};
+
+// A module is encoded more or less like a function.
+struct BCModule : BCFunc
+{
+};
+
+struct BCHeader
+{
+    char                magic[8];
+    uint32_t            version;
+
+    // TODO: probably want a section-based file
+    // format so that we can add/remove different
+    // kinds of data without having to revise
+    // the schema here.
+
+    // The bytecode representation of the module
+    BCPtr<BCModule>     module;
+};
+
+
+
+}
+
+
+#endif