IR support for Tuple types. (#1492)

* Tuple types.

* Fix x86 warning

* Improved deduplication

Co-authored-by: Tim Foley <tfoleyNV@users.noreply.github.com>

11 files changed, 389 insertions, 1 deletions

diff --git a/source/slang/slang-emit-c-like.cpp b/source/slang/slang-emit-c-like.cpp
index 4ed7c2fac..0708bc9a8 100644
--- a/source/slang/slang-emit-c-like.cpp
+++ b/source/slang/slang-emit-c-like.cpp
@@ -3813,6 +3813,8 @@ void CLikeSourceEmitter::ensureGlobalInst(ComputeEmitActionsContext* ctx, IRInst
     default:
         break;
     }
+    if (as<IRBasicType>(inst))
+        return;
 
     // Have we already processed this instruction?
     EmitAction::Level existingLevel;
diff --git a/source/slang/slang-emit.cpp b/source/slang/slang-emit.cpp
index 31ff3c4f9..0b09338b3 100644
--- a/source/slang/slang-emit.cpp
+++ b/source/slang/slang-emit.cpp
@@ -17,6 +17,7 @@
 #include "slang-ir-legalize-varying-params.h"
 #include "slang-ir-link.h"
 #include "slang-ir-lower-generics.h"
+#include "slang-ir-lower-tuple-types.h"
 #include "slang-ir-restructure.h"
 #include "slang-ir-restructure-scoping.h"
 #include "slang-ir-specialize.h"
@@ -323,6 +324,10 @@ Result linkAndOptimizeIR(
     if (sink->getErrorCount() != 0)
         return SLANG_FAIL;
 
+    lowerTuples(irModule, sink);
+    if (sink->getErrorCount() != 0)
+        return SLANG_FAIL;
+
     // TODO(DG): There are multiple DCE steps here, which need to be changed
     //   so that they don't just throw out any non-entry point code
     // Debugging code for IR transformations...
diff --git a/source/slang/slang-ir-deduplicate.cpp b/source/slang/slang-ir-deduplicate.cpp
new file mode 100644
index 000000000..81bb2371e
--- /dev/null
+++ b/source/slang/slang-ir-deduplicate.cpp
@@ -0,0 +1,80 @@
+#include "slang-ir-insts.h"
+
+namespace Slang
+{
+    struct DeduplicateContext
+    {
+        SharedIRBuilder* builder;
+        IRInst* addValue(IRInst* value)
+        {
+            if (!value) return nullptr;
+            if (as<IRType>(value))
+                return addTypeValue(value);
+            if (auto constValue = as<IRConstant>(value))
+                return addConstantValue(constValue);
+            return value;
+        }
+        IRInst* addConstantValue(IRConstant* value)
+        {
+            IRConstantKey key = { value };
+            if (auto newValue = builder->constantMap.TryGetValue(key))
+                return *newValue;
+            builder->constantMap[key] = value;
+            return value;
+        }
+        IRInst* addTypeValue(IRInst* value)
+        {
+            // Do not deduplicate struct types.
+            switch (value->op)
+            {
+            case kIROp_StructType:
+                return value;
+            default:
+                break;
+            }
+
+            IRInstKey key = { value };
+            if (auto newValue = builder->globalValueNumberingMap.TryGetValue(key))
+                return *newValue;
+
+            for (UInt i = 0; i < value->getOperandCount(); i++)
+            {
+                value->setOperand(i, addValue(value->getOperand(i)));
+            }
+            value->setFullType((IRType*)addValue(value->getFullType()));
+            builder->globalValueNumberingMap[key] = value;
+            return value;
+        }
+    };
+    void SharedIRBuilder::deduplicateAndRebuildGlobalNumberingMap()
+    {
+        DeduplicateContext context;
+        context.builder = this;
+        bool changed = true;
+        constantMap.Clear();
+        for (auto inst : module->getGlobalInsts())
+        {
+            if (auto constVal = as<IRConstant>(inst))
+            {
+                context.addConstantValue(constVal);
+            }
+        }
+        globalValueNumberingMap.Clear();
+        List<IRInst*> instToRemove;
+        for (auto inst : module->getGlobalInsts())
+        {
+            if (as<IRType>(inst))
+            {
+                auto newInst = context.addTypeValue(inst);
+                if (newInst != inst)
+                {
+                    changed = true;
+                    inst->replaceUsesWith(newInst);
+                    instToRemove.add(inst);
+                }
+            }
+        }
+        for (auto inst : instToRemove)
+            inst->removeAndDeallocate();
+    }
+}
diff --git a/source/slang/slang-ir-inst-defs.h b/source/slang/slang-ir-inst-defs.h
index 5b442354a..3761828b9 100644
--- a/source/slang/slang-ir-inst-defs.h
+++ b/source/slang/slang-ir-inst-defs.h
@@ -176,6 +176,7 @@ INST(InterfaceType, interface, 0, 0)
 INST(AssociatedType, associated_type, 0, 0)
 INST(ThisType, this_type, 0, 0)
 INST(RTTIType, rtti_type, 0, 0)
+INST(TupleType, tuple_type, 0, 0)
 
 // A TypeType-typed IRValue represents a IRType.
 // It is used to represent a type parameter/argument in a generics.
@@ -235,6 +236,8 @@ INST(makeVector, makeVector, 0, 0)
 INST(MakeMatrix, makeMatrix, 0, 0)
 INST(makeArray, makeArray, 0, 0)
 INST(makeStruct, makeStruct, 0, 0)
+INST(MakeTuple, makeTuple, 0, 0)
+INST(GetTupleElement, getTupleElement, 2, 0)
 
 INST(Call, call, 1, 0)
 
diff --git a/source/slang/slang-ir-insts.h b/source/slang/slang-ir-insts.h
index e022b353c..55af7db78 100644
--- a/source/slang/slang-ir-insts.h
+++ b/source/slang/slang-ir-insts.h
@@ -1568,6 +1568,18 @@ struct IRBindGlobalGenericParam : IRInst
     IR_LEAF_ISA(BindGlobalGenericParam)
 };
 
+// An Instruction that creates a tuple value.
+struct IRMakeTuple : IRInst
+{
+    IR_LEAF_ISA(MakeTuple)
+};
+
+struct IRGetTupleElement : IRInst
+{
+    IR_LEAF_ISA(GetTupleElement)
+    IRInst* getTuple() { return getOperand(0); }
+    IRInst* getElementIndex() { return getOperand(1); }
+};
 
     /// An instruction that packs a concrete value into an existential-type "box"
 struct IRMakeExistential : IRInst
@@ -1590,6 +1602,20 @@ struct IRWrapExistential : IRInst
     IR_LEAF_ISA(WrapExistential)
 };
 
+struct IRExtractExistentialValue : IRInst
+{
+    IR_LEAF_ISA(ExtractExistentialValue);
+};
+
+struct IRExtractExistentialType : IRInst
+{
+    IR_LEAF_ISA(ExtractExistentialType);
+};
+
+struct IRExtractExistentialWitnessTable : IRInst
+{
+    IR_LEAF_ISA(ExtractExistentialWitnessTable);
+};
 
 // Description of an instruction to be used for global value numbering
 struct IRInstKey
@@ -1638,6 +1664,10 @@ struct SharedIRBuilder
     Dictionary<IRConstantKey,   IRConstant*>    constantMap;
 
     void insertBlockAlongEdge(IREdge const& edge);
+
+    // Rebuilds `globalValueNumberingMap`. This is necessary if any existing
+    // keys are modified (thus its hash code is changed).
+    void deduplicateAndRebuildGlobalNumberingMap();
 };
 
 struct IRBuilderSourceLocRAII;
@@ -1703,6 +1733,10 @@ struct IRBuilder
     IRAnyValueType* getAnyValueType(IRIntegerValue size);
     IRAnyValueType* getAnyValueType(IRInst* size);
 
+    IRTupleType* getTupleType(UInt count, IRType* const* types);
+    IRTupleType* getTupleType(IRType* type0, IRType* type1);
+    IRTupleType* getTupleType(IRType* type0, IRType* type1, IRType* type2);
+
     IRBasicBlockType*   getBasicBlockType();
     IRWitnessTableType* getWitnessTableType(IRType* baseType);
     IRType* getTypeType() { return getType(IROp::kIROp_TypeType); }
@@ -1850,6 +1884,10 @@ struct IRBuilder
     // Creates an RTTI object. Result is of `IRRTTIType`.
     IRInst* emitMakeRTTIObject(IRInst* typeInst);
 
+    IRInst* emitMakeTuple(IRType* type, UInt count, IRInst* const* args);
+
+    IRInst* emitGetTupleElement(IRType* type, IRInst* tuple, UInt element);
+
     IRInst* emitMakeVector(
         IRType*         type,
         UInt            argCount,
diff --git a/source/slang/slang-ir-lower-tuple-types.cpp b/source/slang/slang-ir-lower-tuple-types.cpp
new file mode 100644
index 000000000..814f92283
--- /dev/null
+++ b/source/slang/slang-ir-lower-tuple-types.cpp
@@ -0,0 +1,197 @@
+// slang-ir-lower-tuple-types.cpp
+
+#include "slang-ir-lower-tuple-types.h"
+#include "slang-ir.h"
+#include "slang-ir-insts.h"
+
+namespace Slang
+{
+    struct TupleLoweringContext
+    {
+        IRModule* module;
+        DiagnosticSink* sink;
+
+        SharedIRBuilder sharedBuilderStorage;
+
+        List<IRInst*> workList;
+        HashSet<IRInst*> workListSet;
+
+        struct LoweredTupleInfo : public RefObject
+        {
+            IRType* tupleType;
+            IRStructType* structType;
+            List<IRStructField*> fields;
+        };
+        Dictionary<IRInst*, RefPtr<LoweredTupleInfo>> mapLoweredStructToTupleInfo;
+        Dictionary<IRInst*, RefPtr<LoweredTupleInfo>> loweredTuples;
+
+        IRType* maybeLowerTupleType(IRBuilder* builder, IRType* type)
+        {
+            if (auto info = getLoweredTupleType(builder, type))
+                return info->structType;
+            else
+                return type;
+        }
+
+        void appendTypeName(StringBuilder& sb, IRInst* inst)
+        {
+            if (auto name = inst->findDecoration<IRNameHintDecoration>())
+            {
+                sb << name->getName();
+            }
+        }
+
+        LoweredTupleInfo* getLoweredTupleType(IRBuilder* builder, IRInst* type)
+        {
+            if (auto loweredInfo = loweredTuples.TryGetValue(type))
+                return loweredInfo->Ptr();
+            if (auto loweredInfo = mapLoweredStructToTupleInfo.TryGetValue(type))
+                return loweredInfo->Ptr();
+
+            if (!type)
+                return nullptr;
+            if (type->op != kIROp_TupleType)
+                return nullptr;
+
+            RefPtr<LoweredTupleInfo> info = new LoweredTupleInfo();
+            info->tupleType = (IRType*)type;
+            auto structType = builder->createStructType();
+            info->structType = structType;
+            StringBuilder nameSb, fieldNameSb;
+            nameSb << "Tuple";
+            for (UInt i = 0; i < type->getOperandCount(); i++)
+            {
+                auto elementType = maybeLowerTupleType(builder, (IRType*)(type->getOperand(i)));
+                nameSb << "_";
+                appendTypeName(nameSb, elementType);
+                auto key = builder->createStructKey();
+                fieldNameSb.Clear();
+                fieldNameSb << "value" << i;
+                builder->addNameHintDecoration(key, fieldNameSb.getUnownedSlice());
+                auto field = builder->createStructField(structType, key, (IRType*)elementType);
+                info->fields.add(field);
+            }
+            builder->addNameHintDecoration(structType, nameSb.getUnownedSlice());
+            mapLoweredStructToTupleInfo[structType] = info;
+            loweredTuples[type] = info;
+            return info.Ptr();
+        }
+
+        void addToWorkList(
+            IRInst* inst)
+        {
+            for (auto ii = inst->getParent(); ii; ii = ii->getParent())
+            {
+                if (as<IRGeneric>(ii))
+                    return;
+            }
+
+            if (workListSet.Contains(inst))
+                return;
+
+            workList.add(inst);
+            workListSet.Add(inst);
+        }
+
+        void processMakeTuple(IRMakeTuple* inst)
+        {
+            IRBuilder builderStorage;
+            auto builder = &builderStorage;
+            builder->sharedBuilder = &sharedBuilderStorage;
+            builder->setInsertBefore(inst);
+
+            auto info = getLoweredTupleType(builder, inst->getDataType());
+            auto var = builder->emitVar(info->structType);
+            for (Index i = 0; i < info->fields.getCount(); i++)
+            {
+                SLANG_ASSERT(i < (Index)inst->getOperandCount());
+                auto ptrType = builder->getPtrType(info->fields[i]->getFieldType());
+                auto addr = builder->emitFieldAddress(ptrType, var, info->fields[i]->getKey());
+                builder->emitStore(addr, inst->getOperand((UInt)i));
+            }
+            auto load = builder->emitLoad(var);
+            inst->replaceUsesWith(load);
+            inst->removeAndDeallocate();
+        }
+
+        void processGetTupleElement(IRGetTupleElement* inst)
+        {
+            IRBuilder builderStorage;
+            auto builder = &builderStorage;
+            builder->sharedBuilder = &sharedBuilderStorage;
+            builder->setInsertBefore(inst);
+
+            auto base = inst->getTuple();
+            auto loweredTupleInfo = getLoweredTupleType(builder, base->getDataType());
+            SLANG_ASSERT(loweredTupleInfo);
+            auto elementIndex = getIntVal(inst->getElementIndex());
+            SLANG_ASSERT((Index)elementIndex < loweredTupleInfo->fields.getCount());
+
+            auto field = loweredTupleInfo->fields[(Index)elementIndex];
+            auto getElement = builder->emitFieldExtract(field->getFieldType(), base, field->getKey());
+            inst->replaceUsesWith(getElement);
+            inst->removeAndDeallocate();
+        }
+
+        void processInst(IRInst* inst)
+        {
+            switch (inst->op)
+            {
+            case kIROp_MakeTuple:
+                processMakeTuple((IRMakeTuple*)inst);
+                break;
+            case kIROp_GetTupleElement:
+                processGetTupleElement((IRGetTupleElement*)inst);
+                break;
+            default:
+                break;
+            }
+        }
+
+        void processModule()
+        {
+            SharedIRBuilder* sharedBuilder = &sharedBuilderStorage;
+            sharedBuilder->module = module;
+            sharedBuilder->session = module->session;
+
+            // Deduplicate equivalent types.
+            sharedBuilder->deduplicateAndRebuildGlobalNumberingMap();
+
+            addToWorkList(module->getModuleInst());
+
+            while (workList.getCount() != 0)
+            {
+                // We will then iterate until our work list goes dry.
+                //
+                while (workList.getCount() != 0)
+                {
+                    IRInst* inst = workList.getLast();
+
+                    workList.removeLast();
+                    workListSet.Remove(inst);
+
+                    processInst(inst);
+
+                    for (auto child = inst->getLastChild(); child; child = child->getPrevInst())
+                    {
+                        addToWorkList(child);
+                    }
+                }
+            }
+
+            // Replace all tuple types with lowered struct types.
+            for (auto kv : loweredTuples)
+            {
+                kv.Key->replaceUsesWith(kv.Value->structType);
+            }
+        }
+    };
+    
+    void lowerTuples(IRModule* module, DiagnosticSink* sink)
+    {
+        TupleLoweringContext context;
+        context.module = module;
+        context.sink = sink;
+        context.processModule();
+    }
+}
diff --git a/source/slang/slang-ir-lower-tuple-types.h b/source/slang/slang-ir-lower-tuple-types.h
new file mode 100644
index 000000000..88c737a91
--- /dev/null
+++ b/source/slang/slang-ir-lower-tuple-types.h
@@ -0,0 +1,16 @@
+// slang-ir-lower-tuple-types.h
+#pragma once
+
+#include "slang-ir.h"
+
+namespace Slang
+{
+    struct IRModule;
+    class DiagnosticSink;
+
+    /// Lower tuple types to ordinary `struct`s.
+    void lowerTuples(
+        IRModule* module,
+        DiagnosticSink* sink);
+
+}
diff --git a/source/slang/slang-ir.cpp b/source/slang/slang-ir.cpp
index 1a6187a92..13840a84a 100644
--- a/source/slang/slang-ir.cpp
+++ b/source/slang/slang-ir.cpp
@@ -2270,6 +2270,23 @@ namespace Slang
         return (IRAnyValueType*)getType(kIROp_AnyValueType, size);
     }
 
+    IRTupleType* IRBuilder::getTupleType(UInt count, IRType* const* types)
+    {
+        return (IRTupleType*)getType(kIROp_TupleType, count, (IRInst*const*)types);
+    }
+
+    IRTupleType* IRBuilder::getTupleType(IRType* type0, IRType* type1)
+    {
+        IRType* operands[] = { type0, type1 };
+        return getTupleType(2, operands);
+    }
+
+    IRTupleType* IRBuilder::getTupleType(IRType* type0, IRType* type1, IRType* type2)
+    {
+        IRType* operands[] = { type0, type1, type2 };
+        return getTupleType(3, operands);
+    }
+
     IRBasicBlockType*   IRBuilder::getBasicBlockType()
     {
         return (IRBasicBlockType*)getType(kIROp_BasicBlockType);
@@ -2721,6 +2738,17 @@ namespace Slang
         return inst;
     }
 
+    IRInst* IRBuilder::emitMakeTuple(IRType* type, UInt count, IRInst* const* args)
+    {
+        return emitIntrinsicInst(type, kIROp_MakeTuple, count, args);
+    }
+
+    IRInst* IRBuilder::emitGetTupleElement(IRType* type, IRInst* tuple, UInt element)
+    {
+        IRInst* args[] = { tuple, getIntValue(getIntType(), element) };
+        return emitIntrinsicInst(type, kIROp_GetTupleElement, 2, args);
+    }
+
     IRInst* IRBuilder::emitMakeVector(
         IRType*         type,
         UInt            argCount,
diff --git a/source/slang/slang-ir.h b/source/slang/slang-ir.h
index 9316c0228..d6c655a7c 100644
--- a/source/slang/slang-ir.h
+++ b/source/slang/slang-ir.h
@@ -1247,6 +1247,13 @@ struct IRTaggedUnionType : IRType
     IR_LEAF_ISA(TaggedUnionType)
 };
 
+/// Represents a tuple. Tuples are created by `IRMakeTuple` and its elements
+/// are accessed via `GetTupleElement(tupleValue, IRIntLit)`.
+struct IRTupleType : IRType
+{
+    IR_LEAF_ISA(TupleType)
+};
+
 struct IRTypeType : IRType
 {
     IR_LEAF_ISA(TypeType);
diff --git a/source/slang/slang.vcxproj b/source/slang/slang.vcxproj
index 97f4bba25..44ea96309 100644
--- a/source/slang/slang.vcxproj
+++ b/source/slang/slang.vcxproj
@@ -245,6 +245,7 @@
     <ClInclude Include="slang-ir-lower-generic-function.h" />
     <ClInclude Include="slang-ir-lower-generic-type.h" />
     <ClInclude Include="slang-ir-lower-generics.h" />
+    <ClInclude Include="slang-ir-lower-tuple-types.h" />
     <ClInclude Include="slang-ir-missing-return.h" />
     <ClInclude Include="slang-ir-restructure-scoping.h" />
     <ClInclude Include="slang-ir-restructure.h" />
@@ -331,6 +332,7 @@
     <ClCompile Include="slang-ir-collect-global-uniforms.cpp" />
     <ClCompile Include="slang-ir-constexpr.cpp" />
     <ClCompile Include="slang-ir-dce.cpp" />
+    <ClCompile Include="slang-ir-deduplicate.cpp" />
     <ClCompile Include="slang-ir-dominators.cpp" />
     <ClCompile Include="slang-ir-entry-point-raw-ptr-params.cpp" />
     <ClCompile Include="slang-ir-entry-point-uniforms.cpp" />
@@ -347,6 +349,7 @@
     <ClCompile Include="slang-ir-lower-generic-function.cpp" />
     <ClCompile Include="slang-ir-lower-generic-type.cpp" />
     <ClCompile Include="slang-ir-lower-generics.cpp" />
+    <ClCompile Include="slang-ir-lower-tuple-types.cpp" />
     <ClCompile Include="slang-ir-missing-return.cpp" />
     <ClCompile Include="slang-ir-restructure-scoping.cpp" />
     <ClCompile Include="slang-ir-restructure.cpp" />
@@ -406,4 +409,4 @@
   <Import Project="$(VCTargetsPath)\Microsoft.Cpp.targets" />
   <ImportGroup Label="ExtensionTargets">
   </ImportGroup>
-</Project> 
\ No newline at end of file
+</Project>
\ No newline at end of file
diff --git a/source/slang/slang.vcxproj.filters b/source/slang/slang.vcxproj.filters
index 679e773d0..73caa41ac 100644
--- a/source/slang/slang.vcxproj.filters
+++ b/source/slang/slang.vcxproj.filters
@@ -186,6 +186,9 @@
     <ClInclude Include="slang-ir-lower-generics.h">
       <Filter>Header Files</Filter>
     </ClInclude>
+    <ClInclude Include="slang-ir-lower-tuple-types.h">
+      <Filter>Header Files</Filter>
+    </ClInclude>
     <ClInclude Include="slang-ir-missing-return.h">
       <Filter>Header Files</Filter>
     </ClInclude>
@@ -440,6 +443,9 @@
     <ClCompile Include="slang-ir-dce.cpp">
       <Filter>Source Files</Filter>
     </ClCompile>
+    <ClCompile Include="slang-ir-deduplicate.cpp">
+      <Filter>Source Files</Filter>
+    </ClCompile>
     <ClCompile Include="slang-ir-dominators.cpp">
       <Filter>Source Files</Filter>
     </ClCompile>
@@ -488,6 +494,9 @@
     <ClCompile Include="slang-ir-lower-generics.cpp">
       <Filter>Source Files</Filter>
     </ClCompile>
+    <ClCompile Include="slang-ir-lower-tuple-types.cpp">
+      <Filter>Source Files</Filter>
+    </ClCompile>
     <ClCompile Include="slang-ir-missing-return.cpp">
       <Filter>Source Files</Filter>
     </ClCompile>