Initial support for dynamic dispatch using "tagged union" types (#772)

* Initial support for dynamic dispatch using "tagged union" types

Suppose a user declares some generic shader code, like the following:

```hlsl
interface IFrobnicator { ... }
type_param T : IFrobincator;
ParameterBlock<T : IFrobnicator> gFrobnicator;
...
gFrobincator.frobnicate(value);
```

and then they have some concrete implementations of the required interface:

```hlsl
struct A : IFrobnicator { ... }
struct B : IFrobnicator { ... }
```

The current Slang compiler allows them to generate  distinct compiled kernels for the case of `T=A` and the case of `T=B`. This means that the decision of which implementation to use must be made at or before the time when a shader gets bound in the application.

This change adds a new ability where the Slang compiler can generate code to handle the case where `T` might be *either* `A` or `B`, and which case it is will be determined dynamically at runtime. This means a single compiled kernel can handle both cases, and the decision about which code path to run can be made any time before the shader executes.

This new option is supported by defining a *tagged union* type. Via the API, the user specifies that `T` should be specialized to `__TaggedUnion(A,B)` (the double underscore indicates that this is an experimental and unsupported feature at present). We refer to the types `A` and `B` here as the "case" types of the tagged union. Conceptually, the compiler synthesizes a type something like:

```hlsl
struct TU { union { A a; B b; } payload; uint tag; }
```

The user can then allocate a constant buffer to hold their tagged union type, and when they pick a concrete type to use (say `B`), they fill in the first `sizeof(B)` bytes of their buffer with data describing a `B` instance, and then set the `tag` field to the appopriate 0-based index of the case type they chose (in this case the `B` case gets the tag value `1`).

Actually implementing tagged unions takes a few main steps:

* Type parsing was extended to special-case `__TaggedUnion` as a contextual keyword. This is really only intended to be used when parsing types from the API or command-line, and Bad Things are likely to happen if a user ever puts it directly in their code. Eventually construction of tagged unions should be an API feature and not part of the language syntax.

* Semantic checking was extended to recognize that a tagged union like `__TaggedUnion(A,B)` shoud support an interface like `IFrobnicator` whenever all of the case types suport it, as long as the interface is "safe" for use with tagged unions (which means it doesn't use a few of the advancd langauge features like associated types).

* The IR was extended with instructions to represent tagged union types and to extract their tag and the payload for the different cases as needed.

* IR generation was extended to synthesize implementations of interface methods for any interface that a tagged union needs to support. Right now the implementation is simplistic and only handles simple method requirements, which it does by emitting a `switch` instruction to pick between the different cases.

* A new IR pass was introduced to "desugar" any tagged union types used in the code. The downstream HLSL and GLSL compilers don't support `union`s, so we have to instead emit a tagged union as a "bag of bits" and implement loading the data for particular cases from it manually.

* Final code emit mostly Just Works after the above steps, but we had to introduce an explicit IR instruction for bit-casting to handle the output of the desugaring pass.

There are a bunch of gaps and caveats in this implementation, but that seems reasonable for something that is an experimental feature. The various `TODO` comments and assertion failures in unimplemented cases are intended, so that this work can be checked in even if it isn't feature-complete.

* fixup: missing files

* fixup: typos

3 files changed, 116 insertions, 0 deletions

diff --git a/tests/compute/tagged-union.slang b/tests/compute/tagged-union.slang
new file mode 100644
index 000000000..5089ec5a7
--- /dev/null
+++ b/tests/compute/tagged-union.slang
@@ -0,0 +1,108 @@
+// tagged-union.slang
+//TEST(compute):COMPARE_COMPUTE_EX:-slang -compute
+//TEST(compute):COMPARE_COMPUTE_EX:-slang -compute -dx12
+//TEST(compute, vulkan):COMPARE_COMPUTE_EX:-vk -compute
+
+
+// The goal of this test is to show that we can generate
+// dynamic-dispatch logic from Slang code written using
+// interface+generics, entirely from the compiler API side
+// and without code changes.
+
+// We are going to define a dummy interface just for testing
+// purposes, that can be used to see which implmentation
+// got invoked at runtime.
+//
+interface IFrobnicator
+{
+    int frobnicate(int value);
+}
+
+// Now we will define two different implemetnations that
+// "frobnicate" values differently. The first will just
+// add to the value from a member variable.
+//
+struct A : IFrobnicator
+{
+    int a;
+    int frobnicate(int value)
+    {
+        return value + a;
+    }
+}
+
+// The second implementation will have an additional field
+// of local state, and will do a tiny bit more math.
+//
+struct B : IFrobnicator
+{
+    int b;
+    int y;
+    int frobnicate(int value)
+    {
+        return value * b + y;
+    }
+}
+
+// Now we will define the generic type parameter for our shader,
+// which will be constraints to be a type that implements our
+// `IFrobnicator` interface.
+//
+type_param T : IFrobnicator;
+//
+// For the actual test runner, we will instruct it to plug in
+// a tagged-union type over the two concrete implemetnations.
+// Note that while we are writing this line in the source file,
+// it is in comments so that the Slang compiler only knows about
+// our intention when it is informed via the API.
+//
+//TEST_INPUT: type __TaggedUnion(A,B)
+
+// Next we need to pass in the actual parameter data for our
+// chosen `IFrobnicator` implementation. The decalration of
+// the constant buffer follows the conventional approach for
+// using global generic parameters, so there is nothing much
+// to say.
+//
+// Note: We are not using `ParameterBlock<_>` here because
+// the `render-test` tool doesn't yet support code that
+// uses multiple descriptor tables/sets.
+//
+ConstantBuffer<T> gFrobnicator;
+
+// Where things get interesting is when we go to provide the
+// data that will be used by the parameter block.
+//
+// Because we are plugging in a taggd union type, the actual
+// data type that we fill in will be something kind of like:
+//
+//      struct S { union { A a; B b; }; uint tag; };
+//
+// When compiling for D3D, the size of that union will be
+// 8 bytes (for the largest case), and so the tag will come
+// as the third 32-bit value. We will initialize our data
+// buffer for a `B` value then, which will get the tag `1`
+// since it was the second option in our `__TaggedUnion`.
+//
+// In the Vulkan case the size of both `A` and `B` is 16 bytes
+// (because they round up structure sizes to their alignement)
+// and so the tag value will be the fifth 32-bit value.
+// We will thus set up the same data buffer to look like an `A`
+// value to Vulkan!
+//
+//TEST_INPUT: cbuffer(data=[16 9 1 0 0], stride=4):dxbinding(0),glbinding(0)
+
+int test(int val)
+{
+    return gFrobnicator.frobnicate(val);
+}
+
+//TEST_INPUT: ubuffer(data=[0 0 0 0], stride=4):dxbinding(0),glbinding(1),out
+RWStructuredBuffer<int> gOutputBuffer;
+
+[numthreads(4, 1, 1)]
+void computeMain(uint3 dispatchThreadID : SV_DispatchThreadID)
+{
+    uint tid = dispatchThreadID.x;
+    gOutputBuffer[tid] = test(tid);
+}
diff --git a/tests/compute/tagged-union.slang.2.expected.txt b/tests/compute/tagged-union.slang.2.expected.txt
new file mode 100644
index 000000000..a0d427709
--- /dev/null
+++ b/tests/compute/tagged-union.slang.2.expected.txt
@@ -0,0 +1,4 @@
+10
+11
+12
+13
diff --git a/tests/compute/tagged-union.slang.expected.txt b/tests/compute/tagged-union.slang.expected.txt
new file mode 100644
index 000000000..7ba203156
--- /dev/null
+++ b/tests/compute/tagged-union.slang.expected.txt
@@ -0,0 +1,4 @@
+9
+19
+29
+39