IR generation cleanup work

- Make all instructions store their argument count for now, so we can iterate over them easily.
  - Longer term we might try to optimize for space because the common case is that the operand count is known, but keeping it simpler seems better for now

- Split apart the creation of an instruction from adding it to a parent

- Use the above capability to make sure that we add a function to its parent *after* all the parameter/result type emission has occured.

- Perform simple value numbering for types during IR creation
  - This logic also tries to pick a good parent for any type instructions, so that types don't get created local to a function unless they really need to

- Create all constants at global scope, and re-use when values are identical

5 files changed, 409 insertions, 73 deletions

diff --git a/source/core/hash.h b/source/core/hash.h
index 07a14099b..dd2086305 100644
--- a/source/core/hash.h
+++ b/source/core/hash.h
@@ -95,7 +95,10 @@ namespace Slang
 		return PointerHash<std::is_pointer<TKey>::value>::GetHashCode(key);
 	}
 
-		
+    inline int combineHash(int left, int right)
+    {
+        return (left * 16777619) ^ right;
+    }
 }
 
 #endif
\ No newline at end of file
diff --git a/source/slang/emit.cpp b/source/slang/emit.cpp
index c8f3f06cb..d9b2ffcd6 100644
--- a/source/slang/emit.cpp
+++ b/source/slang/emit.cpp
@@ -3951,11 +3951,11 @@ String emitEntryPoint(
         throw 99;
 
     }
-    else if(translationUnit->compileRequest->loadedModulesList.Count() != 0)
+    else if(
 #else
-    if(!(translationUnit->compileFlags & SLANG_COMPILE_FLAG_NO_CHECKING )
-        || translationUnit->compileRequest->loadedModulesList.Count() != 0)
+    if(!(translationUnit->compileFlags & SLANG_COMPILE_FLAG_NO_CHECKING ) ||
 #endif
+        translationUnit->compileRequest->loadedModulesList.Count() != 0)
     {
         // The user has `import`ed some Slang modules, and so we are in case (2)
         //
diff --git a/source/slang/ir.cpp b/source/slang/ir.cpp
index 9e5169bd2..c40b0f048 100644
--- a/source/slang/ir.cpp
+++ b/source/slang/ir.cpp
@@ -80,15 +80,9 @@ namespace Slang
 
     //
 
-    // Add an instruction into the current scope
-    static void addInst(
-        IRBuilder*  builder,
-        IRInst*     inst)
+    // Add an instruction to a specific parent
+    void IRBuilder::addInst(IRParentInst* parent, IRInst* inst)
     {
-        auto parent = builder->parentInst;
-        if (!parent)
-            return;
-
         inst->parent = parent;
 
         if (!parent->firstChild)
@@ -111,6 +105,17 @@ namespace Slang
         }
     }
 
+    // Add an instruction into the current scope
+    void IRBuilder::addInst(
+        IRInst*     inst)
+    {
+        auto parent = parentInst;
+        if (!parent)
+            return;
+
+        addInst(parent, inst);
+    }
+
     // Create an IR instruction/value and initialize it.
     //
     // In this case `argCount` and `args` represnt the
@@ -129,7 +134,7 @@ namespace Slang
 
         IRUse* instArgs = inst->getArgs();
 
-        auto module = builder->module;
+        auto module = builder->getModule();
         if (!module || (type && type->op == &kIROpInfo_VoidType))
         {
             // Can't or shouldn't assign an ID to this op
@@ -138,6 +143,7 @@ namespace Slang
         {
             inst->id = ++module->idCounter;
         }
+        inst->argCount = argCount + 1;
 
         inst->op = op;
 
@@ -148,8 +154,6 @@ namespace Slang
             instArgs[aa+1].init(inst, args[aa]);
         }
 
-        addInst(builder, inst);
-
         return inst;
     }
 
@@ -241,7 +245,7 @@ namespace Slang
     }
 
     template<typename T>
-    static T* createValueWithTrailingArgs(
+    static T* createInstWithTrailingArgs(
         IRBuilder*      builder,
         IROpInfo const* op,
         IRType*         type,
@@ -257,16 +261,283 @@ namespace Slang
             args);
     }
 
+    //
+
+    bool operator==(IRInstKey const& left, IRInstKey const& right)
+    {
+        if(left.inst->op != right.inst->op) return false;
+        if(left.inst->parent != right.inst->parent) return false;
+        if(left.inst->argCount != right.inst->argCount) return false;
+
+        auto argCount = left.inst->argCount;
+        auto leftArgs = left.inst->getArgs();
+        auto rightArgs = right.inst->getArgs();
+        for( UInt aa = 0; aa < argCount; ++aa )
+        {
+            if(leftArgs[aa].usedValue != rightArgs[aa].usedValue)
+                return false;
+        }
+
+        return true;
+    }
+
+    int IRInstKey::GetHashCode()
+    {
+        auto code = Slang::GetHashCode(inst->op);
+        code = combineHash(code, Slang::GetHashCode(inst->parent));
+        code = combineHash(code, Slang::GetHashCode(inst->argCount));
+
+        auto argCount = inst->argCount;
+        auto args = inst->getArgs();
+        for( UInt aa = 0; aa < argCount; ++aa )
+        {
+            code = combineHash(code, Slang::GetHashCode(args[aa].usedValue));
+        }
+        return code;
+    }
+
+    static IRParentInst* joinParentInstsForInsertion(
+        IRParentInst*   left,
+        IRParentInst*   right)
+    {
+        // Are they the same? Easy.
+        if(left == right) return left;
+
+        // Have we already failed to find a location? Then bail.
+        if(!left) return nullptr;
+        if(!right) return nullptr;
+
+        // Is one inst a parent of the other? Pick the child.
+        for( auto ll = left; ll; ll = ll->parent )
+        {
+            // Did we find the right node in the parent list of the left?
+            if(ll == right) return left;
+        }
+        for( auto rr = right; rr; rr = rr->parent )
+        {
+            // Did we find the left node in the parent list of the right?
+            if(rr == left) return right;
+        }
+
+        // Seems like they are unrelated, so we should play it safe
+        return nullptr;
+    }
+
+
+    static IRInst* findOrEmitInstImpl(
+        IRBuilder*      builder,
+        UInt            size,
+        IROpInfo const* op,
+        IRType*         type,
+        UInt            argCount,
+        IRValue* const* args)
+    {
+        // First, we need to pick a good insertion point
+        // for the instruction, which we do by looking
+        // at its operands.
+        //
+
+        IRParentInst* parent = builder->shared->module;
+        if( type )
+        {
+            parent = joinParentInstsForInsertion(parent, type->parent);
+        }
+        for( UInt aa = 0; aa < argCount; ++aa )
+        {
+            auto arg = args[aa];
+            parent = joinParentInstsForInsertion(parent, arg->parent);
+        }
+
+        // If we failed to find a good insertion point, then insert locally.
+        if( !parent )
+        {
+            parent = builder->parentInst;
+        }
+
+        if( parent->op == &kIROpInfo_Func )
+        {
+            // We are trying to insert into a function, and we should really
+            // be inserting into its entry block.
+            assert(parent->firstChild);
+            parent = (IRBlock*) ((IRFunc*) parent)->firstChild;
+        }
+
+        // We now know where we want to insert, but there might
+        // already be an equivalent instruction in that block.
+        //
+        // We will check for such an instruction in a slightly hacky
+        // way: we will construct a temporary instruction and
+        // then use it to look up in a cache of instructions.
+
+        IRInst* keyInst = createInstImpl(builder, size, op, type, argCount ,args);
+        keyInst->parent = parent;
+
+        IRInstKey key;
+        key.inst = keyInst;
+
+        IRInst* inst = nullptr;
+        if( builder->shared->globalValueNumberingMap.TryGetValue(key, inst) )
+        {
+            // We found a match, so just use that.
+
+            free(keyInst);
+            return inst;
+        }
+
+        // No match, so use our "key" instruction for real.
+        inst = keyInst;
+
+        builder->shared->globalValueNumberingMap.Add(key, inst);
+
+        keyInst->parent = nullptr;
+        builder->addInst(parent, inst);
+
+        return inst;
+    }
+
+    template<typename T>
+    static T* findOrEmitInst(
+        IRBuilder*      builder,
+        IROpInfo const* op,
+        IRType*         type,
+        UInt            argCount,
+        IRValue* const* args)
+    {
+        return (T*) findOrEmitInstImpl(
+            builder,
+            sizeof(T),
+            op,
+            type,
+            argCount,
+            args);
+    }
+
+    template<typename T>
+    static T* findOrEmitInst(
+        IRBuilder*      builder,
+        IROpInfo const* op,
+        IRType*         type)
+    {
+        return (T*) findOrEmitInstImpl(
+            builder,
+            sizeof(T),
+            op,
+            type,
+            0,
+            nullptr);
+    }
+
+    template<typename T>
+    static T* findOrEmitInst(
+        IRBuilder*      builder,
+        IROpInfo const* op,
+        IRType*         type,
+        IRInst*         arg)
+    {
+        return (T*) findOrEmitInstImpl(
+            builder,
+            sizeof(T),
+            op,
+            type,
+            1,
+            &arg);
+    }
+
+    template<typename T>
+    static T* findOrEmitInst(
+        IRBuilder*      builder,
+        IROpInfo const* op,
+        IRType*         type,
+        IRInst*         arg1,
+        IRInst*         arg2)
+    {
+        IRInst* args[] = { arg1, arg2 };
+        return (T*) findOrEmitInstImpl(
+            builder,
+            sizeof(T),
+            op,
+            type,
+            2,
+            &args[0]);
+    }
+
+    //
+
+    bool operator==(IRConstantKey const& left, IRConstantKey const& right)
+    {
+        if(left.inst->op             != right.inst->op)             return false;
+        if(left.inst->type.usedValue != right.inst->type.usedValue) return false;
+        if(left.inst->u.ptrData[0]   != right.inst->u.ptrData[0])   return false;
+        if(left.inst->u.ptrData[1]   != right.inst->u.ptrData[1])   return false;
+        return true;
+    }
+
+    int IRConstantKey::GetHashCode()
+    {
+        auto code = Slang::GetHashCode(inst->op);
+        code = combineHash(code, Slang::GetHashCode(inst->type.usedValue));
+        code = combineHash(code, Slang::GetHashCode(inst->u.ptrData[0]));
+        code = combineHash(code, Slang::GetHashCode(inst->u.ptrData[1]));
+        return code;
+    }
+
+    static IRConstant* findOrEmitConstant(
+        IRBuilder*              builder,
+        IROpInfo const*         op,
+        IRType*                 type,
+        UInt                    valueSize,
+        void const*             value)
+    {
+        // First, we need to pick a good insertion point
+        // for the instruction, which we do by looking
+        // at its operands.
+        //
+
+        IRParentInst* parent = builder->shared->module;
+
+        IRConstant keyInst;
+        keyInst.op = op;
+        keyInst.type.usedValue = type;
+        memcpy(&keyInst.u, value, valueSize);
+
+        IRConstantKey key;
+        key.inst = &keyInst;
+
+        IRConstant* inst = nullptr;
+        if( builder->shared->constantMap.TryGetValue(key, inst) )
+        {
+            // We found a match, so just use that.
+            return inst;
+        }
+
+        // We now know where we want to insert, but there might
+        // already be an equivalent instruction in that block.
+        //
+        // We will check for such an instruction in a slightly hacky
+        // way: we will construct a temporary instruction and
+        // then use it to look up in a cache of instructions.
+
+        inst = createInst<IRConstant>(builder, op, type);
+        memcpy(&inst->u, value, valueSize);
+
+        key.inst = inst;
+        builder->shared->constantMap.Add(key, inst);
+
+        builder->addInst(parent, inst);
+
+        return inst;
+    }
 
 
     //
 
     static IRType* getBaseTypeImpl(IRBuilder* builder, IROpInfo const* op)
     {
-        return createInst<IRType>(
+        auto inst = findOrEmitInst<IRType>(
             builder,
             op,
             builder->getTypeType());
+        return inst;
     }
 
     IRType* IRBuilder::getBaseType(BaseType flavor)
@@ -291,8 +562,7 @@ namespace Slang
 
     IRType* IRBuilder::getVectorType(IRType* elementType, IRValue* elementCount)
     {
-        // TODO: should unique things
-         return createInst<IRVectorType>(
+        return findOrEmitInst<IRVectorType>(
             this,
             &kIROpInfo_VectorType,
             getTypeType(),
@@ -302,22 +572,15 @@ namespace Slang
 
     IRType* IRBuilder::getTypeType()
     {
-        // TODO: should unique things
-        IRType* type = createInst<IRType>(
+        return findOrEmitInst<IRType>(
             this,
             &kIROpInfo_TypeType,
             nullptr);
-
-        // TODO: we need some way to stop this recursion,
-        // but just saying that `Type isa Type` is unfounded.
-        type->type.init(type, type);
-
-        return type;
     }
 
     IRType* IRBuilder::getVoidType()
     {
-        return createInst<IRType>(
+        return findOrEmitInst<IRType>(
             this,
             &kIROpInfo_VoidType,
             getTypeType());
@@ -325,7 +588,7 @@ namespace Slang
 
     IRType* IRBuilder::getBlockType()
     {
-        return createInst<IRType>(
+        return findOrEmitInst<IRType>(
             this,
             &kIROpInfo_BlockType,
             getTypeType());
@@ -335,12 +598,14 @@ namespace Slang
         UInt            fieldCount,
         IRType* const*  fieldTypes)
     {
-        return createValueWithTrailingArgs<IRStructType>(
+        auto inst = createInstWithTrailingArgs<IRStructType>(
             this,
             &kIROpInfo_StructType,
             getTypeType(),
             fieldCount,
             (IRValue* const*)fieldTypes);
+        addInst(inst);
+        return inst;
     }
 
     IRValue* IRBuilder::getBoolValue(bool value)
@@ -350,19 +615,22 @@ namespace Slang
 
     IRValue* IRBuilder::getIntValue(IRType* type, IRIntegerValue value)
     {
-        IRIntLit* val = createInst<IRIntLit>(
+        return findOrEmitConstant(
             this,
             &kIROpInfo_IntLit,
-            type);
-
-        val->value = value;
-
-        return val;
+            type,
+            sizeof(value),
+            &value);
     }
 
     IRValue* IRBuilder::getFloatValue(IRType* type, IRFloatingPointValue value)
     {
-        SLANG_UNIMPLEMENTED_X("IR");
+        return findOrEmitConstant(
+            this,
+            &kIROpInfo_FloatLit,
+            type,
+            sizeof(value),
+            &value);
     }
 
     IRInst* IRBuilder::emitIntrinsicInst(
@@ -371,12 +639,14 @@ namespace Slang
         UInt            argCount,
         IRValue* const* args)
     {
-        return createValueWithTrailingArgs<IRInst>(
+        auto inst = createInstWithTrailingArgs<IRInst>(
             this,
             kIRIntrinsicOpInfos[(int)intrinsicOp],
             type,
             argCount,
             args);
+        addInst(inst);
+        return inst;
     }
 
     IRInst* IRBuilder::emitConstructorInst(
@@ -384,12 +654,14 @@ namespace Slang
         UInt            argCount,
         IRValue* const* args)
     {
-        return createValueWithTrailingArgs<IRInst>(
+        auto inst = createInstWithTrailingArgs<IRInst>(
             this,
             &kIROpInfo_Construct,
             type,
             argCount,
             args);
+        addInst(inst);
+        return inst;
     }
 
     IRModule* IRBuilder::createModule()
@@ -417,47 +689,61 @@ namespace Slang
             getBlockType());
     }
 
-    IRParam* IRBuilder::createParam(
+    IRBlock* IRBuilder::emitBlock()
+    {
+        auto inst = createBlock();
+        addInst(inst);
+        return inst;
+    }
+
+    IRParam* IRBuilder::emitParam(
         IRType* type)
     {
-        return createInst<IRParam>(
+        auto inst = createInst<IRParam>(
             this,
             &kIROpInfo_Param,
             type);
+        addInst(inst);
+        return inst;
     }
 
-    IRInst* IRBuilder::createFieldExtract(
+    IRInst* IRBuilder::emitFieldExtract(
         IRType*     type,
         IRValue*    base,
         UInt        fieldIndex)
     {
-        IRFieldExtract* irInst = createInst<IRFieldExtract>(
+        auto inst = createInst<IRFieldExtract>(
             this,
             &kIROpInfo_FieldExtract,
             type,
             base);
 
-        irInst->fieldIndex = fieldIndex;
+        inst->fieldIndex = fieldIndex;
 
-        return irInst;
+        addInst(inst);
+        return inst;
     }
 
-    IRInst* IRBuilder::createReturn(
+    IRInst* IRBuilder::emitReturn(
         IRValue*    val)
     {
-        return createInst<IRReturnVal>(
+        auto inst = createInst<IRReturnVal>(
             this,
             &kIROpInfo_ReturnVal,
             getVoidType(),
             val);
+        addInst(inst);
+        return inst;
     }
 
-    IRInst* IRBuilder::createReturn()
+    IRInst* IRBuilder::emitReturn()
     {
-        return createInst<IRReturnVoid>(
+        auto inst = createInst<IRReturnVoid>(
             this,
             &kIROpInfo_ReturnVoid,
             getVoidType());
+        addInst(inst);
+        return inst;
     }
 
     struct IRDumpContext
@@ -527,8 +813,8 @@ namespace Slang
         dump(context, op->name);
 
         // TODO: dump operands
-        unsigned argCount = op->fixedArgCount + 1;
-        for (unsigned ii = 0; ii < argCount; ++ii)
+        uint32_t argCount = inst->argCount;
+        for (uint32_t ii = 0; ii < argCount; ++ii)
         {
             if (ii != 0)
                 dump(context, ", ");
diff --git a/source/slang/ir.h b/source/slang/ir.h
index 95dec6007..0a0c8d612 100644
--- a/source/slang/ir.h
+++ b/source/slang/ir.h
@@ -60,6 +60,8 @@ struct IRUse
     void init(IRInst* user, IRInst* usedValue);
 };
 
+typedef uint32_t IRInstID;
+
 // In the IR, almost *everything* is an instruction,
 // in order to make the representation as uniform as possible.
 struct IRInst
@@ -70,7 +72,11 @@ struct IRInst
     // A unique ID to represent the op when printing
     // (or zero to indicate that the value of this
     // op isn't special).
-    UInt id;
+    IRInstID id;
+
+    // The total number of arguments of this instruction
+    // (including the type)
+    uint32_t argCount;
 
     // The parent of this instruction.
     // This will often be a basic block, but we
@@ -95,14 +101,16 @@ typedef IRInst IRValue;
 typedef long long IRIntegerValue;
 typedef double IRFloatingPointValue;
 
-struct IRIntLit : IRInst
-{
-    IRIntegerValue value;
-};
-
-struct IRFloatLit : IRInst
+struct IRConstant : IRInst
 {
-    IRFloatingPointValue value;
+    union
+    {
+        IRIntegerValue          intVal;
+        IRFloatingPointValue    floatVal;
+
+        // HACK: allows us to hash the value easily
+        void*                   ptrData[2];
+    } u;
 };
 
 // Representation of a type at the IR level.
@@ -188,20 +196,52 @@ struct IRFunc : IRParentInst
 struct IRModule : IRParentInst
 {
     // The designated entry-point function, if any
-    IRFunc* entryPoint;
+    IRFunc*     entryPoint;
 
     // A special counter used to assign logical ids to instructions in this module.
-    UInt    idCounter;
+    IRInstID    idCounter;
 };
 
-struct IRBuilder
+// Description of an instruction to be used for global value numbering
+struct IRInstKey
+{
+    IRInst* inst;
+
+    int GetHashCode();
+};
+
+bool operator==(IRInstKey const& left, IRInstKey const& right);
+
+struct IRConstantKey
+{
+    IRConstant* inst;
+
+    int GetHashCode();
+};
+bool operator==(IRConstantKey const& left, IRConstantKey const& right);
+
+struct SharedIRBuilder
 {
     // The module that will own all of the IR
     IRModule*       module;
 
+    Dictionary<IRInstKey,       IRInst*>    globalValueNumberingMap;
+    Dictionary<IRConstantKey,   IRConstant*>    constantMap;
+};
+
+struct IRBuilder
+{
+    // Shared state for all IR builders working on the same module
+    SharedIRBuilder*    shared;
+
+    IRModule* getModule() { return shared->module; }
+
     // The parent instruction to add children to.
     IRParentInst*   parentInst;
 
+    void addInst(IRParentInst* parent, IRInst* inst);
+    void addInst(IRInst* inst);
+
     IRType* getBaseType(BaseType flavor);
     IRType* getBoolType();
     IRType* getVectorType(IRType* elementType, IRValue* elementCount);
@@ -232,19 +272,20 @@ struct IRBuilder
     IRFunc* createFunc();
 
     IRBlock* createBlock();
+    IRBlock* emitBlock();
 
-    IRParam* createParam(
+    IRParam* emitParam(
         IRType* type);
 
-    IRInst* createFieldExtract(
+    IRInst* emitFieldExtract(
         IRType*     type,
         IRValue*    base,
         UInt        fieldIndex);
 
-    IRInst* createReturn(
+    IRInst* emitReturn(
         IRValue*    val);
 
-    IRInst* createReturn();
+    IRInst* emitReturn();
 };
 
 void dumpIR(IRModule* module);
diff --git a/source/slang/lower-to-ir.cpp b/source/slang/lower-to-ir.cpp
index e00dffa1d..a01279f2e 100644
--- a/source/slang/lower-to-ir.cpp
+++ b/source/slang/lower-to-ir.cpp
@@ -402,7 +402,7 @@ struct ExprLoweringVisitor : ExprVisitor<ExprLoweringVisitor, LoweredValInfo>
             {
                 IRValue* irBase = base.val;
                 return LoweredValInfo::simple(
-                    getBuilder()->createFieldExtract(
+                    getBuilder()->emitFieldExtract(
                         getSimpleType(fieldType),
                         irBase,
                         fieldIndex));
@@ -517,11 +517,11 @@ struct StmtLoweringVisitor : StmtVisitor<StmtLoweringVisitor>
         {
             auto loweredExpr = lowerExpr(context, expr);
 
-            getBuilder()->createReturn(getSimpleVal(loweredExpr));
+            getBuilder()->emitReturn(getSimpleVal(loweredExpr));
         }
         else
         {
-            getBuilder()->createReturn();
+            getBuilder()->emitReturn();
         }
     }
 };
@@ -599,7 +599,7 @@ struct DeclLoweringVisitor : DeclVisitor<DeclLoweringVisitor, LoweredValInfo>
         IRFunc* irFunc = subBuilder->createFunc();
         subBuilder->parentInst = irFunc;
 
-        IRBlock* entryBlock = subBuilder->createBlock();
+        IRBlock* entryBlock = subBuilder->emitBlock();
         subBuilder->parentInst = entryBlock;
 
         IRGenContext subContextStorage = *context;
@@ -611,7 +611,7 @@ struct DeclLoweringVisitor : DeclVisitor<DeclLoweringVisitor, LoweredValInfo>
         for( auto paramDecl : decl->GetParameters() )
         {
             IRType* irParamType = lowerSimpleType(context, paramDecl->getType());
-            IRParam* irParam = subBuilder->createParam(irParamType);
+            IRParam* irParam = subBuilder->emitParam(irParamType);
 
             DeclRef<ParamDecl> paramDeclRef = makeDeclRef(paramDecl.Ptr());
 
@@ -625,6 +625,8 @@ struct DeclLoweringVisitor : DeclVisitor<DeclLoweringVisitor, LoweredValInfo>
 
         lowerStmt(subContext, decl->Body);
 
+        getBuilder()->addInst(irFunc);
+
         return LoweredValInfo::simple(irFunc);
     }
 };
@@ -713,13 +715,17 @@ IRModule* lowerEntryPointToIR(
 
     context->shared = sharedContext;
 
+    SharedIRBuilder sharedBuilderStorage;
+    SharedIRBuilder* sharedBuilder = &sharedBuilderStorage;
+    sharedBuilder->module = nullptr;
+
     IRBuilder builderStorage;
     IRBuilder* builder = &builderStorage;
-    builder->module = nullptr;
+    builder->shared = sharedBuilder;
     builder->parentInst = nullptr;
 
     IRModule* module = builder->createModule();
-    builder->module = module;
+    sharedBuilder->module = module;
     builder->parentInst = module;
 
     context->irBuilder = builder;