Add legalization for 0-sized arrays. (#7327)

* Add legalization for 0-sized arrays.

* Allow 0-sized arrays in the front-end.

* More tests.

* Add `Conditional<T, hasValue>` type to core module.

* Update toc.

* Fix wording.

* Update test.

9 files changed, 292 insertions, 19 deletions

diff --git a/source/slang/core.meta.slang b/source/slang/core.meta.slang
index 484f51bfc..51e2f326e 100644
--- a/source/slang/core.meta.slang
+++ b/source/slang/core.meta.slang
@@ -1513,6 +1513,50 @@ bool operator!=(__none_t noneVal, Optional<T> val)
     return val.hasValue;
 }
 
+struct Conditional<T, bool hasValue>
+{
+    internal T storage[hasValue];
+
+    __implicit_conversion($(kConversionCost_ValToOptional))
+    [__unsafeForceInlineEarly]
+    __init(T val) { if (hasValue) storage[0] = val;}
+
+    [__unsafeForceInlineEarly]
+    public Optional<T> get()
+    {
+        if (hasValue)
+        {
+            return Optional<T>(storage[0]);
+        }
+        else
+        {
+            return none;
+        }
+    }
+
+    [__unsafeForceInlineEarly]
+    [mutating]
+    public void set(T value)
+    {
+        if (hasValue)
+            storage[0] = value;
+    }
+}
+
+extension<T> Optional<T>
+{
+    __implicit_conversion($(kConversionCost_ImplicitDereference))
+    __generic<bool condHasValue>
+    [__unsafeForceInlineEarly]
+    __init(Conditional<T, condHasValue> condVal)
+    {
+        if (condHasValue)
+            this = Optional<T>(condVal.storage[0]);
+        else
+            this = none;
+    }
+}
+
 //@public:
 
 /// A variadic generic storing the product of several types.
diff --git a/source/slang/slang-check-decl.cpp b/source/slang/slang-check-decl.cpp
index e3b05ec00..aa84a057f 100644
--- a/source/slang/slang-check-decl.cpp
+++ b/source/slang/slang-check-decl.cpp
@@ -10120,7 +10120,7 @@ void SemanticsVisitor::validateArraySizeForVariable(VarDeclBase* varDecl)
 
     // TODO(tfoley): How to handle the case where bound isn't known?
     auto elementCount = arrayType->getElementCount();
-    if (GetMinBound(elementCount) <= 0)
+    if (GetMinBound(elementCount) < 0)
     {
         getSink()->diagnose(varDecl, Diagnostics::invalidArraySize);
         return;
diff --git a/source/slang/slang-check-expr.cpp b/source/slang/slang-check-expr.cpp
index 1e052a553..66c2f9796 100644
--- a/source/slang/slang-check-expr.cpp
+++ b/source/slang/slang-check-expr.cpp
@@ -2414,10 +2414,10 @@ Expr* SemanticsExprVisitor::visitIndexExpr(IndexExpr* subscriptExpr)
                 nullptr,
                 ConstantFoldingKind::SpecializationConstant);
 
-            // Validate that array size is greater than zero
+            // Validate that array size is non-negative.
             if (auto constElementCount = as<ConstantIntVal>(elementCount))
             {
-                if (constElementCount->getValue() <= 0)
+                if (constElementCount->getValue() < 0)
                 {
                     getSink()->diagnose(
                         subscriptExpr->indexExprs[0],
diff --git a/source/slang/slang-diagnostic-defs.h b/source/slang/slang-diagnostic-defs.h
index 465602a33..3786a0cf3 100644
--- a/source/slang/slang-diagnostic-defs.h
+++ b/source/slang/slang-diagnostic-defs.h
@@ -657,7 +657,7 @@ DIAGNOSTIC(
     Error,
     cannotConvertArrayOfSmallerToLargerSize,
     "Cannot convert array of size $0 to array of size $1 as this would truncate data")
-DIAGNOSTIC(30025, Error, invalidArraySize, "array size must be larger than zero.")
+DIAGNOSTIC(30025, Error, invalidArraySize, "array size must be non-negative.")
 DIAGNOSTIC(
     30026,
     Error,
diff --git a/source/slang/slang-emit.cpp b/source/slang/slang-emit.cpp
index 20459c722..88533d938 100644
--- a/source/slang/slang-emit.cpp
+++ b/source/slang/slang-emit.cpp
@@ -56,6 +56,7 @@
 #include "slang-ir-layout.h"
 #include "slang-ir-legalize-array-return-type.h"
 #include "slang-ir-legalize-binary-operator.h"
+#include "slang-ir-legalize-empty-array.h"
 #include "slang-ir-legalize-global-values.h"
 #include "slang-ir-legalize-image-subscript.h"
 #include "slang-ir-legalize-mesh-outputs.h"
@@ -1158,6 +1159,8 @@ Result linkAndOptimizeIR(
         addUserTypeHintDecorations(irModule);
     }
 
+    legalizeEmptyArray(irModule, sink);
+
     // We don't need the legalize pass for C/C++ based types
     if (options.shouldLegalizeExistentialAndResourceTypes)
     {
diff --git a/source/slang/slang-ir-inst-defs.h b/source/slang/slang-ir-inst-defs.h
index 7a281bac4..eac337deb 100644
--- a/source/slang/slang-ir-inst-defs.h
+++ b/source/slang/slang-ir-inst-defs.h
@@ -428,19 +428,20 @@ INST(Load, load, 1, 0)
 INST(Store, store, 2, 0)
 
 // Atomic Operations
-INST(AtomicLoad, atomicLoad, 1, 0)
-INST(AtomicStore, atomicStore, 2, 0)
-INST(AtomicExchange, atomicExchange, 2, 0)
-INST(AtomicCompareExchange, atomicCompareExchange, 3, 0)
-INST(AtomicAdd, atomicAdd, 2, 0)
-INST(AtomicSub, atomicSub, 2, 0)
-INST(AtomicAnd, atomicAnd, 2, 0)
-INST(AtomicOr, atomicOr, 2, 0)
-INST(AtomicXor, atomicXor, 2, 0)
-INST(AtomicMin, atomicMin, 2, 0)
-INST(AtomicMax, atomicMax, 2, 0)
-INST(AtomicInc, atomicInc, 1, 0)
-INST(AtomicDec, atomicDec, 1, 0)
+    INST(AtomicLoad, atomicLoad, 1, 0)
+    INST(AtomicStore, atomicStore, 2, 0)
+    INST(AtomicExchange, atomicExchange, 2, 0)
+    INST(AtomicCompareExchange, atomicCompareExchange, 3, 0)
+    INST(AtomicAdd, atomicAdd, 2, 0)
+    INST(AtomicSub, atomicSub, 2, 0)
+    INST(AtomicAnd, atomicAnd, 2, 0)
+    INST(AtomicOr, atomicOr, 2, 0)
+    INST(AtomicXor, atomicXor, 2, 0)
+    INST(AtomicMin, atomicMin, 2, 0)
+    INST(AtomicMax, atomicMax, 2, 0)
+    INST(AtomicInc, atomicInc, 1, 0)
+    INST(AtomicDec, atomicDec, 1, 0)
+INST_RANGE(AtomicOperation, AtomicLoad, AtomicDec)
 
 // Produced and removed during backward auto-diff pass as a temporary placeholder representing the
 // currently accumulated derivative to pass to some dOut argument in a nested call.
diff --git a/source/slang/slang-ir-insts.h b/source/slang/slang-ir-insts.h
index b5c1a6475..a1f66d142 100644
--- a/source/slang/slang-ir-insts.h
+++ b/source/slang/slang-ir-insts.h
@@ -2500,7 +2500,14 @@ struct IRLoad : IRInst
     IRInst* getPtr() { return ptr.get(); }
 };
 
-struct IRAtomicLoad : IRInst
+struct IRAtomicOperation : IRInst
+{
+    IR_PARENT_ISA(AtomicOperation);
+
+    IRInst* getPtr() { return getOperand(0); }
+};
+
+struct IRAtomicLoad : IRAtomicOperation
 {
     IRUse ptr;
     IR_LEAF_ISA(AtomicLoad)
@@ -2521,7 +2528,7 @@ struct IRStore : IRInst
     IRUse* getValUse() { return &val; }
 };
 
-struct IRAtomicStore : IRInst
+struct IRAtomicStore : IRAtomicOperation
 {
     IRUse ptr;
     IRUse val;
@@ -3074,6 +3081,17 @@ struct IREach : IRInst
     IRInst* getElement() { return getOperand(0); }
 };
 
+struct IRMakeArray : IRInst
+{
+    IR_LEAF_ISA(MakeArray)
+};
+
+struct IRMakeArrayFromElement : IRInst
+{
+    IR_LEAF_ISA(MakeArrayFromElement)
+};
+
+
 // An Instruction that creates a tuple value.
 struct IRMakeTuple : IRInst
 {
diff --git a/source/slang/slang-ir-legalize-empty-array.cpp b/source/slang/slang-ir-legalize-empty-array.cpp
new file mode 100644
index 000000000..561327565
--- /dev/null
+++ b/source/slang/slang-ir-legalize-empty-array.cpp
@@ -0,0 +1,196 @@
+#include "slang-ir-legalize-empty-array.h"
+
+#include "slang-ir-insts.h"
+#include "slang-ir-util.h"
+#include "slang-ir.h"
+
+namespace Slang
+{
+struct EmptyArrayLoweringContext
+{
+    IRModule* module;
+    DiagnosticSink* sink;
+
+    InstWorkList workList;
+    InstHashSet workListSet;
+
+    Dictionary<IRInst*, IRInst*> replacements;
+
+    EmptyArrayLoweringContext(IRModule* module)
+        : module(module), workList(module), workListSet(module)
+    {
+    }
+
+    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);
+    }
+
+    bool isEmptyArray(IRType* t)
+    {
+        const auto lenLit = composeGetters<IRIntLit>(t, &IRArrayType::getElementCount);
+        return lenLit ? getIntVal(lenLit) == 0 : false;
+    };
+
+    bool hasEmptyArrayType(IRInst* i) { return isEmptyArray(i->getDataType()); }
+
+    bool hasEmptyArrayPtrType(IRInst* i)
+    {
+        const auto ptr = as<IRPtrTypeBase>(i->getDataType());
+        return ptr && isEmptyArray(ptr->getValueType());
+    }
+
+    // Visit each instruction and replace it with legalized instructiosn if necessary.
+    void processInst(IRInst* inst)
+    {
+        IRInst* replacement = nullptr;
+
+        IRBuilder builder(module);
+        builder.setInsertBefore(inst);
+        replacement = instMatch<IRInst*>(
+            inst,
+            nullptr,
+            // The following match instructions which take a 0-sized array as an
+            // operand and produces a result value for the inst.
+            [&](IRGetElement* getElement)
+            {
+                const auto base = getElement->getBase();
+                return hasEmptyArrayType(base) ? builder.emitUndefined(getElement->getDataType())
+                                               : nullptr;
+            },
+            [&](IRGetElementPtr* gep)
+            {
+                const auto base = gep->getBase();
+                return hasEmptyArrayPtrType(base) || base->getOp() == kIROp_undefined
+                           ? builder.emitUndefined(gep->getDataType())
+                           : nullptr;
+            },
+            [&](IRFieldAddress* gep)
+            {
+                const auto base = gep->getBase();
+                return base->getOp() == kIROp_undefined ? builder.emitUndefined(gep->getDataType())
+                                                        : nullptr;
+            },
+            [&](IRLoad* load)
+            {
+                return load->getOperand(0)->getOp() == kIROp_undefined
+                           ? builder.emitUndefined(load->getDataType())
+                           : nullptr;
+            },
+            [&](IRImageLoad* load)
+            {
+                return load->getOperand(0)->getOp() == kIROp_undefined
+                           ? builder.emitUndefined(load->getDataType())
+                           : nullptr;
+            },
+            [&](IRStore* store)
+            {
+                if (store->getPtr()->getOp() == kIROp_undefined)
+                    store->removeAndDeallocate();
+                return nullptr;
+            },
+            [&](IRAtomicStore* store)
+            {
+                if (store->getPtr()->getOp() == kIROp_undefined)
+                    store->removeAndDeallocate();
+                return nullptr;
+            },
+            [&](IRImageStore* store)
+            {
+                if (store->getImage()->getOp() == kIROp_undefined)
+                    store->removeAndDeallocate();
+                return nullptr;
+            },
+            [&](IRImageSubscript* subscript)
+            {
+                return subscript->getImage()->getOp() == kIROp_undefined
+                           ? builder.emitUndefined(subscript->getDataType())
+                           : nullptr;
+            },
+            [&](IRAtomicOperation* atomic)
+            {
+                return atomic->getOperand(0)->getOp() == kIROp_undefined
+                           ? builder.emitUndefined(atomic->getDataType())
+                           : nullptr;
+            },
+            // The following should match any instruction which can construct a 0-sized array.
+            [&](IRMakeArray* makeArray) {
+                return hasEmptyArrayType(makeArray->getDataType()) ? builder.getVoidValue()
+                                                                   : nullptr;
+            },
+            [&](IRMakeArrayFromElement* makeArray) {
+                return hasEmptyArrayType(makeArray->getDataType()) ? builder.getVoidValue()
+                                                                   : nullptr;
+            });
+
+        // If we did get a replacement, add that to our mapping and return
+        // it, otherwise return the original (to maybe be updated later)
+        if (replacement)
+        {
+            inst->replaceUsesWith(replacement);
+            inst->removeAndDeallocate();
+            addToWorkList(replacement);
+            for (auto use = replacement->firstUse; use; use = use->nextUse)
+            {
+                addToWorkList(use->getUser());
+            }
+        }
+        else if (isEmptyArray((IRType*)inst))
+        {
+            replacements.add(inst, builder.getVoidType());
+        }
+    }
+
+    void processModule()
+    {
+        addToWorkList(module->getModuleInst());
+
+        while (workList.getCount() != 0)
+        {
+            IRInst* inst = workList.getLast();
+
+            workList.removeLast();
+            workListSet.remove(inst);
+
+            // Run this inst through the replacer
+            processInst(inst);
+
+            for (auto child = inst->getLastChild(); child; child = child->getPrevInst())
+            {
+                addToWorkList(child);
+            }
+        }
+
+        // Apply all deferred replacements
+        //
+        // It's important to defer this as if we were updating things
+        // on-the-fly we would be losing information about what was
+        // actually a 0-array or not.
+        for (const auto& [old, replacement] : replacements)
+        {
+            if (old != replacement)
+            {
+                old->replaceUsesWith(replacement);
+                old->removeAndDeallocate();
+            }
+        }
+    }
+};
+
+void legalizeEmptyArray(IRModule* module, DiagnosticSink* sink)
+{
+    EmptyArrayLoweringContext context(module);
+    context.sink = sink;
+    context.processModule();
+}
+} // namespace Slang
diff --git a/source/slang/slang-ir-legalize-empty-array.h b/source/slang/slang-ir-legalize-empty-array.h
new file mode 100644
index 000000000..657c18403
--- /dev/null
+++ b/source/slang/slang-ir-legalize-empty-array.h
@@ -0,0 +1,11 @@
+#pragma once
+
+namespace Slang
+{
+struct IRModule;
+class DiagnosticSink;
+
+// Legalize 0-sized arrays to `void` types.
+void legalizeEmptyArray(IRModule* module, DiagnosticSink* sink);
+
+} // namespace Slang