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, 192 insertions, 7 deletions

diff --git a/source/slang/lower-to-ir.cpp b/source/slang/lower-to-ir.cpp
index 5ee6d5460..6f64a2215 100644
--- a/source/slang/lower-to-ir.cpp
+++ b/source/slang/lower-to-ir.cpp
@@ -1,6 +1,8 @@
 // lower.cpp
 #include "lower-to-ir.h"
 
+#include "../../slang.h"
+
 #include "ir.h"
 #include "ir-insts.h"
 #include "type-layout.h"
@@ -354,6 +356,73 @@ LoweredValInfo emitCompoundAssignOp(
     return LoweredValInfo::ptr(leftPtr);
 }
 
+IRInst* getOneValOfType(
+    IRGenContext*   context,
+    IRType*         type)
+{
+    switch(type->op)
+    {
+    case kIROp_Int32Type:
+    case kIROp_UInt32Type:
+        return context->irBuilder->getIntValue(type, 1);
+
+    case kIROp_Float32Type:
+        return context->irBuilder->getFloatValue(type, 1.0);
+
+    default:
+        SLANG_UNEXPECTED("inc/dec type");
+        return nullptr;
+    }
+}
+
+LoweredValInfo emitPreOp(
+    IRGenContext*   context,
+    IRType*         type,
+    IROp            op,
+    UInt            argCount,
+    IRValue* const* args)
+{
+    auto builder = context->irBuilder;
+
+    assert(argCount == 1);
+    auto argPtr = args[0];
+
+    auto preVal = builder->emitLoad(argPtr);
+
+    IRInst* oneVal = getOneValOfType(context, type);
+
+    IRInst* innerArgs[] = { preVal, oneVal };
+    auto innerOp = builder->emitIntrinsicInst(type, op, 2, innerArgs);
+
+    builder->emitStore(argPtr, innerOp);
+
+    return LoweredValInfo::simple(preVal);
+}
+
+LoweredValInfo emitPostOp(
+    IRGenContext*   context,
+    IRType*         type,
+    IROp            op,
+    UInt            argCount,
+    IRValue* const* args)
+{
+    auto builder = context->irBuilder;
+
+    assert(argCount == 1);
+    auto argPtr = args[0];
+
+    auto preVal = builder->emitLoad(argPtr);
+
+    IRInst* oneVal = getOneValOfType(context, type);
+
+    IRInst* innerArgs[] = { preVal, oneVal };
+    auto innerOp = builder->emitIntrinsicInst(type, op, 2, innerArgs);
+
+    builder->emitStore(argPtr, innerOp);
+
+    return LoweredValInfo::ptr(argPtr);
+}
+
 // Given a `DeclRef` for something callable, along with a bunch of
 // arguments, emit an appropriate call to it.
 LoweredValInfo emitCallToDeclRef(
@@ -444,6 +513,18 @@ LoweredValInfo emitCallToDeclRef(
 
 #undef CASE
 
+#define CASE(COMPOUND, OP)  \
+            case COMPOUND: return emitPreOp(context, type, OP, argCount, args)
+            CASE(kIRPseudoOp_PreInc, kIROp_Add);
+            CASE(kIRPseudoOp_PreDec, kIROp_Sub);
+#undef CASE
+
+#define CASE(COMPOUND, OP)  \
+            case COMPOUND: return emitPostOp(context, type, OP, argCount, args)
+            CASE(kIRPseudoOp_PostInc, kIROp_Add);
+            CASE(kIRPseudoOp_PostDec, kIROp_Sub);
+#undef CASE
+
             default:
                 SLANG_UNIMPLEMENTED_X("IR pseudo-op");
                 break;
@@ -1603,6 +1684,65 @@ struct StmtLoweringVisitor : StmtVisitor<StmtLoweringVisitor>
         insertBlock(breakLabel);
     }
 
+    void visitWhileStmt(WhileStmt* stmt)
+    {
+        // Generating IR for `while` statement is similar to a
+        // `for` statement, but without a lot of the complications.
+
+        auto builder = getBuilder();
+
+        // We will create blocks for the various places
+        // we need to jump to inside the control flow,
+        // including the blocks that will be referenced
+        // by `continue` or `break` statements.
+        auto loopHead = createBlock();
+        auto bodyLabel = createBlock();
+        auto breakLabel = createBlock();
+
+        // A `continue` inside a `while` loop always
+        // jumps to the head of hte loop.
+        auto continueLabel = loopHead;
+
+        // TODO: register appropriate targets for
+        // break/continue statements.
+
+        // Emit the branch that will start out loop,
+        // and then insert the block for the head.
+
+        auto loopInst = builder->emitLoop(
+            loopHead,
+            breakLabel,
+            continueLabel);
+
+        addLoopDecorations(loopInst, stmt);
+
+        insertBlock(loopHead);
+
+        // Now that we are within the header block, we
+        // want to emit the expression for the loop condition:
+        if (auto condExpr = stmt->Predicate)
+        {
+            auto irCondition = getSimpleVal(context,
+                lowerRValueExpr(context, condExpr));
+
+            // Now we want to `break` if the loop condition is false.
+            builder->emitLoopTest(
+                irCondition,
+                bodyLabel,
+                breakLabel);
+        }
+
+        // Emit the body of the loop
+        insertBlock(bodyLabel);
+        lowerStmt(context, stmt->Statement);
+
+        // At the end of the body we need to jump back to the top.
+        builder->emitBranch(loopHead);
+
+        // Finally we insert the label that a `break` will jump to
+        insertBlock(breakLabel);
+    }
+
     void visitExpressionStmt(ExpressionStmt* stmt)
     {
         // The statement evaluates an expression
@@ -1993,17 +2133,61 @@ struct DeclLoweringVisitor : DeclVisitor<DeclLoweringVisitor, LoweredValInfo>
         for( auto paramDecl : declForParameters->GetParameters() )
         {
             IRType* irParamType = lowerSimpleType(context, paramDecl->getType());
-            paramTypes.Add(irParamType);
 
-            IRParam* irParam = subBuilder->emitParam(irParamType);
+            LoweredValInfo paramVal;
 
-            subBuilder->addHighLevelDeclDecoration(irParam, paramDecl);
+            if (paramDecl->HasModifier<OutModifier>()
+                || paramDecl->HasModifier<InOutModifier>())
+            {
+                // The parameter is being used for input/output purposes,
+                // so it will lower to an actual parameter with a pointer type.
+                //
+                // TODO: Is this the best representation we can use?
 
-            DeclRef<ParamDecl> paramDeclRef = makeDeclRef(paramDecl.Ptr());
+                auto irPtrType = subBuilder->getPtrType(irParamType);
+                paramTypes.Add(irPtrType);
+
+                IRParam* irParamPtr = subBuilder->emitParam(irPtrType);
+                subBuilder->addHighLevelDeclDecoration(irParamPtr, paramDecl);
 
-            LoweredValInfo irParamVal = LoweredValInfo::simple(irParam);
+                paramVal = LoweredValInfo::ptr(irParamPtr);
 
-            subContext->shared->declValues.Add(paramDeclRef, irParamVal);
+                // TODO: We might want to copy the pointed-to value into
+                // a temporary at the start of the function, and then copy
+                // back out at the end, so that we don't have to worry
+                // about things like aliasing in the function body.
+                //
+                // For now we will just use the storage that was passed
+                // in by the caller, knowing that our current lowering
+                // at call sites will guarantee a fresh/unique location.
+            }
+            else
+            {
+                // Simple case of a by-value input parameter.
+                // But note that HLSL allows an input parameter
+                // to be used as a local variable inside of a
+                // function body, so we need to introduce a temporary
+                // and then copy over to it...
+                //
+                // TODO: we could skip this step if we knew
+                // the parameter was marked `const` or similar.
+
+                paramTypes.Add(irParamType);
+
+                IRParam* irParam = subBuilder->emitParam(irParamType);
+                subBuilder->addHighLevelDeclDecoration(irParam, paramDecl);
+                paramVal = LoweredValInfo::simple(irParam);
+
+                auto irLocal = subBuilder->emitVar(irParamType);
+                auto localVal = LoweredValInfo::ptr(irLocal);
+
+                assign(subContext, localVal, paramVal);
+
+                paramVal = localVal;
+            }
+
+            DeclRef<ParamDecl> paramDeclRef = makeDeclRef(paramDecl.Ptr());
+            subContext->shared->declValues.Add(paramDeclRef, paramVal);
         }
 
         auto irResultType = lowerSimpleType(context, declForReturnType->ReturnType);
@@ -2235,4 +2419,5 @@ String emitSlangIRAssemblyForEntryPoint(
     return getSlangIRAssembly(irModule);
 }
 
-}
+
+} // namespace Slang