Initial work on support code generation for generics with constraints (#233)

This change includes a lot of infrastructure work, but the main point is to allow code like the following:

```
// define an interface
interface Helper { float help(); }

// define a generic function that uses the interface
float test<T : Helper>( T t ) { return t.help(); }

// define a type that implements the interface
struct A : Helper { float help() { return 1.0 } }

// define an ordinary function that calls the
// generic function with a concrete type:
float doIt()
{
    A a;
    return test<A>(a);
}

```

Getting this to generate valid code involves a lot of steps. This change includes the initial version of all of these steps, but leaves a lot of gaps where more complete implementation is required.

The changes include:

- Member lookup on types has been centralized, and now handles the case where the type we are looking for a member in is a generic parameter (e.g., given `t.help()` we can now look up `help` in `Helper` by knowing that `t` is a `T` and `T` conforms to `Helper`).
  - There is an obvious cleanup still to be done here where the same exact logic should be used to look up available "constructor" declarations inside a type when the type is used like a function.

- Add a notion of subtype constraint "wittnesses" to the type system. When a generic is declared as taking `<T : Helper>` it really takes two generic parameters: the type `T` and a proof that `T` conforms to `Helper`. The actual arguments to a generic will then include both the type argument and a suitable witness argument (both type-level values).
  - As it stands right now, a witness wraps a `DeclRef` to the declaration that represents the appropriate subtype relationship. So if we have `struct A : Helper`, that `: Helper` part turns into an `InheritanceDecl` member, and a reference to that member can serve as a witness to the fact that `A` conforms to `Helper`.

- Make explicit generic application `G<A,B>` synthesize the additional arguments that represent conformances required by the generic.
  - This does *not* yet deal with the case where a generic is implicitly specialized as part of an ordinary call `G(a,b)`

- A bug fix to not auto-specialize generics during lookup. The problem here was related to an attempted fix of an earlier issue.
  During checking of a method nested in a generic type, we were running into problems where `DeclRefType::create()` was getting called on an un-specialized reference to `vector`, and this was leading to a crash when the code looked for the arguments for the generic. This was worked around by having name lookup automatically specialize any generics it runs into while going through lookup contexts.

  That choice creates the problem that in a generic method like this:

  ```
  void test<T>(T val) { ... }
  ```

  any reference to `val` inside the body of `test` will end up getting specialized so that it is effectively `test<T>::val`, when that isn't really needed.

- Add front-end logic to check that when a type claims to conform to an interface it actually must provide the methods required by the interface. The checking process goes ahead and builds a front-end "witness table" that maps declarations in the interface being conformed to over to their concrete implementations for the type.
  - At the moment the checking is completely broken and bad: it assumes that *any* member with the right name is an appropriate declaration to satisfy a requirement. That obviously needs to be fixed.

- Add an explicit operation to the IR for lookup of methods: `lookup_interface_method(w, r)` where `w` is a reference to the "witness" value and `r` is an `IRDeclRef` for the member we want to look up.

- Add an explicit notion of witness tables to the IR. These end up being the IR representation of an `InheritanceDecl` in a type, and they are generated by enumerating the members that satisfy the interface requirements (which were handily already enumerated by the front-end checking). The witness table is an explicit IR value, and so it will be referenced/used at the site where conformance is being exploited (e.g., as part of a `specialize` call), so it should be safe to eliminate witness tables that are unused (since they represent conformances that aren't actually exploited). Similarly, the entries in a witness table are uses of the functions that implement interface methods, and so keep those live.
  - In order to implement the above, I did a bit of a cleanup pass on the IR representation so that there is an `IRUser` base that `IRInst` inherits from, so that we can have users of values that aren't instructions.

- One annoying thing is that because of how types and generics are handled in the IR, we needed a way to have a type-level `Val` that wraps an IR-level value: e.g., to allow an IR-level witness table to be used as one of the arguments for specialization of a generic. The design I chose here is to have a "proxy" `Val` subclass (`IRProxyVal`) that wraps an `IRValue*`. These should only ever appear as part of types and `DeclRef`s that are used by the IR.
  - One annoying bit here is that an IR value might then have a use that is not manifest in the set of IR instructions, and instead only appears as part of a type somewhere.
  - I'm not 100% happy with this design, but it seems like we'd have to tackle similar issues if/when we eventually allow functions to have `constexpr` or `@Constant` parameters

- Make generic specialization also propagate witness table arguments through to their use sites (this is mostly just the existing substitution machinery, once we have `IRProxyVal`), and then include logic to specialize `lookup_interface_method` instructions when their first operand is a concrete witness table.

All of this work allows a single limited test using generics with constraints to pass, but more work is needed to make the solution robust.

1 files changed, 43 insertions, 103 deletions

diff --git a/source/slang/emit.cpp b/source/slang/emit.cpp
index f76ab1db1..6b411a25d 100644
--- a/source/slang/emit.cpp
+++ b/source/slang/emit.cpp
@@ -5172,7 +5172,7 @@ emitDeclImpl(decl, nullptr);
             // Start by emitting the non-terminator instructions in the block.
             auto terminator = block->getLastInst();
             assert(isTerminatorInst(terminator));
-            for (auto inst = block->getFirstInst(); inst != terminator; inst = inst->nextInst)
+            for (auto inst = block->getFirstInst(); inst != terminator; inst = inst->getNextInst())
             {
                 emitIRInst(context, inst);
             }
@@ -5508,6 +5508,26 @@ emitDeclImpl(decl, nullptr);
         EmitContext*    context,
         IRFunc*         func)
     {
+        // We don't want to declare generic functions,
+        // because none of our targets actually support them.
+        if(func->genericDecl)
+            return;
+
+        // We also don't want to emit declarations for operations
+        // that only appear in the IR as stand-ins for built-in
+        // operations on that target.
+        if (isTargetIntrinsic(context, func))
+            return;
+
+        // Finally, don't emit a declaration for an entry point,
+        // because it might need meta-data attributes attached
+        // to it, and the HLSL compiler will get upset if the
+        // forward declaration doesn't *also* have those
+        // attributes.
+        if(asEntryPoint(func))
+            return;
+
+
         // A function declaration doesn't have any IR basic blocks,
         // and as a result it *also* doesn't have the IR `param` instructions,
         // so we need to emit a declaration entirely from the type.
@@ -5566,82 +5586,6 @@ emitDeclImpl(decl, nullptr);
         return nullptr;
     }
 
-#if 0
-    void emitGLSLEntryPointFunc(
-        EmitContext*    context,
-        IRFunc*         func)
-    {
-        auto funcType = func->getType();
-        auto resultType = func->getResultType();
-
-        auto entryPointLayout = getEntryPointLayout(context, func);
-        assert(entryPointLayout);
-
-        // TODO: need to deal with decorations on the entry point
-        // that should be turned into global-scope `layout` qualifiers.
-
-        // TODO: emit kernel inputs and outputs to globals.
-
-        // Emit a global `out` declaration to hold the output from our shader
-        // kernel.
-        //
-        // TODO: need to generate unique names beter than this
-        //
-        // TODO: need to handle the case where the output is
-        // a structure (should that be fixed up at the IR level,
-        // or here?).
-        // Best option might be to translate the entry-point
-        // result parameter into an `out` parameter, so that
-        // we can handle those uniformly.
-        //
-        String resultName = getIRName(func) + "_result";
-        emitGLSLLayoutQualifiers(entryPointLayout->resultLayout);
-        emit("out ");
-        emitIRType(context, resultType, resultName);
-        emit(";\n");
-
-        // Emit global `in` and/or `out` declarations for the
-        // parameters of our shader kernel.
-        //
-        // TODO: We need to make sure these names don't collide with anything.
-        //
-        // TODO: We need to handle scalarization here.
-        //
-        auto firstParam = func->getFirstParam();
-        for( auto pp = firstParam; pp; pp = pp->getNextParam() )
-        {
-            // TODO: actually handle `out` parameters here.
-
-            auto paramLayout = getVarLayout(context, pp);
-            auto paramName = getIRName(pp);
-            emitGLSLLayoutQualifiers(paramLayout);
-            emit("in ");
-            emitIRType(context, pp->getType(), paramName);
-            emit(";\n");
-        }
-
-        // Now that we've emitted our parameter declarations,
-        // we can start to emit the body of the entry point:
-        //
-        emit("void main()\n{\n");
-
-        // We had better not be trying to output an entry
-        // point from a declaration rather than a definition.
-        assert(isDefinition(func));
-
-        // At the most basic, we just want to emit the operations in
-        // the entry point function directly, but with the small catch
-        // that if there was a `return` statement in there somewhere,
-        // we need to turn that into a write to our output variable.
-        //
-        // TODO: yeah, that should get cleared up at the IR level...
-        //
-        emitIRStmtsForBlocks(context, func->getFirstBlock(), nullptr);
-
-        emit("}\n");
-    }
-#endif
-
     EntryPointLayout* asEntryPoint(IRFunc* func)
     {
         if (auto layoutDecoration = func->findDecoration<IRLayoutDecoration>())
@@ -5697,26 +5641,11 @@ emitDeclImpl(decl, nullptr);
         EmitContext*    context,
         IRFunc*         func)
     {
-#if 0
-        if( getTarget(context) == CodeGenTarget::GLSL
-            && isEntryPoint(func) )
-        {
-            // We have a shader entry point, and that
-            // requires a different strategy for source
-            // code generation in GLSL, because the
-            // parameters/result of the entry point
-            // need to be translated into globals.
-            //
-
-            emitGLSLEntryPointFunc(context, func);
-        }
-        else
-#endif
         if(func->genericDecl)
         {
             Emit("/* ");
             emitIRFuncDecl(context, func);
-            Emit(" */");
+            Emit(" */\n");
             return;
         }
 
@@ -6129,12 +6058,6 @@ emitDeclImpl(decl, nullptr);
             emitIRGlobalVar(context, (IRGlobalVar*) inst);
             break;
 
-#if 0
-        case kIROp_StructType:
-            emitIRStruct(context, (IRStructDecl*) inst);
-            break;
-#endif
-
         case kIROp_Var:
             emitIRVar(context, (IRVar*) inst);
             break;
@@ -6257,7 +6180,7 @@ emitDeclImpl(decl, nullptr);
                         emitIRUsedTypesForValue(context, pp);
                     }
 
-                    for( auto ii = bb->getFirstInst(); ii; ii = ii->nextInst )
+                    for( auto ii = bb->getFirstInst(); ii; ii = ii->getNextInst() )
                     {
                         emitIRUsedTypesForValue(context, ii);
                     }
@@ -6289,6 +6212,20 @@ emitDeclImpl(decl, nullptr);
     {
         emitIRUsedTypesForModule(context, module);
 
+        // Before we emit code, we need to forward-declare
+        // all of our functions so that we don't have to
+        // sort them by dependencies.
+        for( auto gv = module->getFirstGlobalValue(); gv; gv = gv->getNextValue() )
+        {
+            if(gv->op != kIROp_Func)
+                continue;
+
+            auto func = (IRFunc*) gv;
+            emitIRFuncDecl(context, func);
+        }
+
+
+
         for( auto gv = module->getFirstGlobalValue(); gv; gv = gv->getNextValue() )
         {
             emitIRGlobalInst(context, gv);
@@ -6454,9 +6391,12 @@ String emitEntryPoint(
 
         specializeGenerics(lowered);
 
-//        fprintf(stderr, "###\n");
-//        dumpIR(lowered);
-//        fprintf(stderr, "###\n");
+        // Debugging code for IR transformations...
+#if 0
+        fprintf(stderr, "###\n");
+        dumpIR(lowered);
+        fprintf(stderr, "###\n");
+#endif
 
         //
         // TODO: Need to decide whether to do these before or after