[ir] Avoid validating an array element type multiple times

The logic in CheckType for validating element types of composites was
falling through to the case were we validate the type of every element
type separately. For large arrays this was causing excessively long IR
validation times.

Fix the logic so that we never do the per-element validation if every
element has the same type. Use an if-else block instead of an early
continue to make it clearer that these are mutually exclusive paths
(and add some comments).

The unit test takes from ~1 minute (release mode) to 10+ minutes
(debug mode) on my laptop without this change, and <1ms with the
change.

Change-Id: Iead1395f969ac54553d1b6f1f1c5684146376222
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/290575
Commit-Queue: James Price <jrprice@google.com>
Auto-Submit: James Price <jrprice@google.com>
Commit-Queue: dan sinclair <dsinclair@chromium.org>
Reviewed-by: dan sinclair <dsinclair@chromium.org>

src/tint/lang/core/ir/validator.cc

diff --git a/src/tint/lang/core/ir/validator.cc b/src/tint/lang/core/ir/validator.cc
index 0744061..b0c926d 100644
--- a/src/tint/lang/core/ir/validator.cc
+++ b/src/tint/lang/core/ir/validator.cc
@@ -2490,15 +2490,21 @@
             continue;
         }
 
+        // Visit the elements of a composite type.
         auto type_count = ty->Elements();
-        if (type_count.type && seen.Add(type_count.type)) {
-            stack.Push(type_count.type);
-            continue;
-        }
-
-        for (uint32_t i = 0; i < type_count.count; i++) {
-            if (auto* subtype = ty->Element(i); subtype && seen.Add(subtype)) {
-                stack.Push(subtype);
+        if (type_count.type) {
+            // Every element has the same type (e.g. array, vector, matrix, ...), so validate that
+            // type once if it has not been seen before.
+            if (seen.Add(type_count.type)) {
+                stack.Push(type_count.type);
+            }
+        } else {
+            // Different elements have different types (e.g. a struct), so we need to validate each
+            // of them if they have not been seen before.
+            for (uint32_t i = 0; i < type_count.count; i++) {
+                if (auto* subtype = ty->Element(i); subtype && seen.Add(subtype)) {
+                    stack.Push(subtype);
+                }
             }
         }
     }

src/tint/lang/core/ir/validator_type_test.cc

diff --git a/src/tint/lang/core/ir/validator_type_test.cc b/src/tint/lang/core/ir/validator_type_test.cc
index 0f6c5eb..18e6a07 100644
--- a/src/tint/lang/core/ir/validator_type_test.cc
+++ b/src/tint/lang/core/ir/validator_type_test.cc
@@ -729,6 +729,28 @@
                                          std::make_tuple(true, TypeBuilder<core::type::Bool>),
                                          std::make_tuple(false, TypeBuilder<core::type::Void>)));
 
+// Test that validation time does not increase in relation to the size of the array.
+TEST_F(IR_ValidatorTest, LargeArrays) {
+    // The arrays are all different sizes so that they don't get skipped over by CheckType for
+    // having been "seen" already.
+    auto* str_ty =
+        ty.Struct(mod.symbols.New("MyStruct"),
+                  {
+                      {mod.symbols.New("a0"), ty.u32(), {}},
+                      {mod.symbols.New("a1"), ty.array<u32, (1ull << 32ull) - 4u>(), {}},
+                      {mod.symbols.New("a2"), ty.array<u32, (1ull << 32ull) - 8u>(), {}},
+                      {mod.symbols.New("a3"), ty.array<u32, (1ull << 32ull) - 12u>(), {}},
+                      {mod.symbols.New("a4"), ty.array<u32, (1ull << 32ull) - 16u>(), {}},
+                      {mod.symbols.New("a5"), ty.array<u32, (1ull << 32ull) - 20u>(), {}},
+                      {mod.symbols.New("a6"), ty.array<u32, (1ull << 32ull) - 24u>(), {}},
+                      {mod.symbols.New("a7"), ty.array<u32, (1ull << 32ull) - 28u>(), {}},
+                      {mod.symbols.New("a8"), ty.array<u32, (1ull << 32ull) - 32u>(), {}},
+                  });
+    mod.root_block->Append(b.Var(ty.ptr<workgroup>(str_ty)));
+    auto res = ir::Validate(mod);
+    ASSERT_EQ(res, Success) << res.Failure();
+}
+
 using Type_VectorElements = TypeTest;
 
 TEST_P(Type_VectorElements, Test) {