Add a mechanism for finding the best tier for a set of limits

Multiple groups of limits may be defined via macros.
ApplyLimitTiers degrades the incoming limits such that
each limit value within a group is clamped to the
best possible tier. A device may be in Tier 2 for one
limit group, but Tier 1 for another limit group.

Also adds equality operators to dawn_native generated structs
for comparison of expected limits in the test.

Bug: dawn:685
Change-Id: Ibdf947f2ccd44f70d66f48bed472ff5681230633
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/64720
Reviewed-by: Corentin Wallez <cwallez@chromium.org>
Reviewed-by: Brandon Jones <bajones@chromium.org>
Commit-Queue: Austin Eng <enga@chromium.org>
diff --git a/generator/templates/dawn_native/wgpu_structs.cpp b/generator/templates/dawn_native/wgpu_structs.cpp
index 642cb13..e1ed8b2 100644
--- a/generator/templates/dawn_native/wgpu_structs.cpp
+++ b/generator/templates/dawn_native/wgpu_structs.cpp
@@ -14,6 +14,8 @@
 
 #include "dawn_native/wgpu_structs_autogen.h"
 
+#include <tuple>
+
 #ifdef __GNUC__
 // error: 'offsetof' within non-standard-layout type 'wgpu::XXX' is conditionally-supported
 #pragma GCC diagnostic ignored "-Winvalid-offsetof"
@@ -47,5 +49,21 @@
                     "offsetof mismatch for {{CppType}}::{{memberName}}");
         {% endfor %}
 
+        bool {{CppType}}::operator==(const {{as_cppType(type.name)}}& rhs) const {
+            return {% if type.extensible or type.chained -%}
+                (nextInChain == rhs.nextInChain) &&
+            {%- endif %} std::tie(
+                {% for member in type.members %}
+                    {{member.name.camelCase()-}}
+                    {{ "," if not loop.last else "" }}
+                {% endfor %}
+            ) == std::tie(
+                {% for member in type.members %}
+                    rhs.{{member.name.camelCase()-}}
+                    {{ "," if not loop.last else "" }}
+                {% endfor %}
+            );
+        }
+
     {% endfor %}
 }
diff --git a/generator/templates/dawn_native/wgpu_structs.h b/generator/templates/dawn_native/wgpu_structs.h
index 5291d83..6085793 100644
--- a/generator/templates/dawn_native/wgpu_structs.h
+++ b/generator/templates/dawn_native/wgpu_structs.h
@@ -60,6 +60,10 @@
                     {{member_declaration}};
                 {% endif %}
             {% endfor %}
+
+            // Equality operators, mostly for testing. Note that this tests
+            // strict pointer-pointer equality if the struct contains member pointers.
+            bool operator==(const {{as_cppType(type.name)}}& rhs) const;
         };
 
     {% endfor %}
diff --git a/src/dawn_native/Adapter.cpp b/src/dawn_native/Adapter.cpp
index 7cdd1f2..c311df0 100644
--- a/src/dawn_native/Adapter.cpp
+++ b/src/dawn_native/Adapter.cpp
@@ -83,10 +83,7 @@
             return false;
         }
         if (mUseTieredLimits) {
-            // TODO(crbug.com/dawn/685): Apply limit tiers.
-            // For now, set all limits to the defaults until tiers are
-            // defined.
-            GetDefaultLimits(&limits->limits);
+            limits->limits = ApplyLimitTiers(mLimits.v1);
         } else {
             limits->limits = mLimits.v1;
         }
@@ -131,7 +128,7 @@
 
         if (descriptor != nullptr && descriptor->requiredLimits != nullptr) {
             DAWN_TRY(ValidateLimits(
-                mLimits.v1,
+                mUseTieredLimits ? ApplyLimitTiers(mLimits.v1) : mLimits.v1,
                 reinterpret_cast<const RequiredLimits*>(descriptor->requiredLimits)->limits));
 
             if (descriptor->requiredLimits->nextInChain != nullptr) {
diff --git a/src/dawn_native/Limits.cpp b/src/dawn_native/Limits.cpp
index b4b61c9..5c55a55 100644
--- a/src/dawn_native/Limits.cpp
+++ b/src/dawn_native/Limits.cpp
@@ -16,36 +16,71 @@
 
 #include "common/Assert.h"
 
-#define LIMITS(X)                                           \
-    X(Higher, maxTextureDimension1D, 8192)                  \
-    X(Higher, maxTextureDimension2D, 8192)                  \
-    X(Higher, maxTextureDimension3D, 2048)                  \
-    X(Higher, maxTextureArrayLayers, 256)                   \
-    X(Higher, maxBindGroups, 4)                             \
-    X(Higher, maxDynamicUniformBuffersPerPipelineLayout, 8) \
-    X(Higher, maxDynamicStorageBuffersPerPipelineLayout, 4) \
-    X(Higher, maxSampledTexturesPerShaderStage, 16)         \
-    X(Higher, maxSamplersPerShaderStage, 16)                \
-    X(Higher, maxStorageBuffersPerShaderStage, 8)           \
-    X(Higher, maxStorageTexturesPerShaderStage, 4)          \
-    X(Higher, maxUniformBuffersPerShaderStage, 12)          \
-    X(Higher, maxUniformBufferBindingSize, 16384)           \
-    X(Higher, maxStorageBufferBindingSize, 134217728)       \
-    X(Lower, minUniformBufferOffsetAlignment, 256)          \
-    X(Lower, minStorageBufferOffsetAlignment, 256)          \
-    X(Higher, maxVertexBuffers, 8)                          \
-    X(Higher, maxVertexAttributes, 16)                      \
-    X(Higher, maxVertexBufferArrayStride, 2048)             \
-    X(Higher, maxInterStageShaderComponents, 60)            \
-    X(Higher, maxComputeWorkgroupStorageSize, 16352)        \
-    X(Higher, maxComputeInvocationsPerWorkgroup, 256)       \
-    X(Higher, maxComputeWorkgroupSizeX, 256)                \
-    X(Higher, maxComputeWorkgroupSizeY, 256)                \
-    X(Higher, maxComputeWorkgroupSizeZ, 64)                 \
-    X(Higher, maxComputeWorkgroupsPerDimension, 65535)
+#include <array>
+
+// clang-format off
+// TODO(crbug.com/dawn/685):
+// For now, only expose these tiers until metrics can determine better ones.
+#define LIMITS_WORKGROUP_STORAGE_SIZE(X)                                  \
+    X(Higher, maxComputeWorkgroupStorageSize, 16352, 32768, 49152, 65536)
+
+#define LIMITS_STORAGE_BUFFER_BINDING_SIZE(X)                                             \
+    X(Higher, maxStorageBufferBindingSize, 134217728, 1073741824, 2147483647, 4294967295)
+
+// TODO(crbug.com/dawn/685):
+// These limits don't have tiers yet. Define two tiers with the same values since the macros
+// in this file expect more than one tier.
+#define LIMITS_OTHER(X)                                                \
+    X(Higher,                     maxTextureDimension1D,  8192,  8192) \
+    X(Higher,                     maxTextureDimension2D,  8192,  8192) \
+    X(Higher,                     maxTextureDimension3D,  2048,  2048) \
+    X(Higher,                     maxTextureArrayLayers,   256,   256) \
+    X(Higher,                             maxBindGroups,     4,     4) \
+    X(Higher, maxDynamicUniformBuffersPerPipelineLayout,     8,     8) \
+    X(Higher, maxDynamicStorageBuffersPerPipelineLayout,     4,     4) \
+    X(Higher,          maxSampledTexturesPerShaderStage,    16,    16) \
+    X(Higher,                 maxSamplersPerShaderStage,    16,    16) \
+    X(Higher,           maxStorageBuffersPerShaderStage,     8,     8) \
+    X(Higher,          maxStorageTexturesPerShaderStage,     4,     4) \
+    X(Higher,           maxUniformBuffersPerShaderStage,    12,    12) \
+    X(Higher,               maxUniformBufferBindingSize, 16384, 16384) \
+    X( Lower,           minUniformBufferOffsetAlignment,   256,   256) \
+    X( Lower,           minStorageBufferOffsetAlignment,   256,   256) \
+    X(Higher,                          maxVertexBuffers,     8,     8) \
+    X(Higher,                       maxVertexAttributes,    16,    16) \
+    X(Higher,                maxVertexBufferArrayStride,  2048,  2048) \
+    X(Higher,             maxInterStageShaderComponents,    60,    60) \
+    X(Higher,         maxComputeInvocationsPerWorkgroup,   256,   256) \
+    X(Higher,                  maxComputeWorkgroupSizeX,   256,   256) \
+    X(Higher,                  maxComputeWorkgroupSizeY,   256,   256) \
+    X(Higher,                  maxComputeWorkgroupSizeZ,    64,    64) \
+    X(Higher,          maxComputeWorkgroupsPerDimension, 65535, 65535)
+// clang-format on
+
+#define LIMITS_EACH_GROUP(X)              \
+    X(LIMITS_WORKGROUP_STORAGE_SIZE)      \
+    X(LIMITS_STORAGE_BUFFER_BINDING_SIZE) \
+    X(LIMITS_OTHER)
+
+#define LIMITS(X)                         \
+    LIMITS_WORKGROUP_STORAGE_SIZE(X)      \
+    LIMITS_STORAGE_BUFFER_BINDING_SIZE(X) \
+    LIMITS_OTHER(X)
 
 namespace dawn_native {
     namespace {
+        template <uint32_t A, uint32_t B>
+        constexpr void StaticAssertSame() {
+            static_assert(A == B, "Mismatching tier count in limit group.");
+        }
+
+        template <uint32_t I, uint32_t... Is>
+        constexpr uint32_t ReduceSameValue(std::integer_sequence<uint32_t, I, Is...>) {
+            int unused[] = {0, (StaticAssertSame<I, Is>(), 0)...};
+            DAWN_UNUSED(unused);
+            return I;
+        }
+
         enum class LimitBetterDirection {
             Lower,
             Higher,
@@ -106,21 +141,21 @@
 
     void GetDefaultLimits(Limits* limits) {
         ASSERT(limits != nullptr);
-#define X(Better, limitName, defaultValue) limits->limitName = defaultValue;
+#define X(Better, limitName, base, ...) limits->limitName = base;
         LIMITS(X)
 #undef X
     }
 
     Limits ReifyDefaultLimits(const Limits& limits) {
         Limits out;
-#define X(Better, limitName, defaultValue)                                              \
-    if (IsLimitUndefined(limits.limitName) ||                                           \
-        CheckLimit<LimitBetterDirection::Better>::IsBetter(                             \
-            static_cast<decltype(limits.limitName)>(defaultValue), limits.limitName)) { \
-        /* If the limit is undefined or the default is better, use the default */       \
-        out.limitName = defaultValue;                                                   \
-    } else {                                                                            \
-        out.limitName = limits.limitName;                                               \
+#define X(Better, limitName, base, ...)                                           \
+    if (IsLimitUndefined(limits.limitName) ||                                     \
+        CheckLimit<LimitBetterDirection::Better>::IsBetter(                       \
+            static_cast<decltype(limits.limitName)>(base), limits.limitName)) {   \
+        /* If the limit is undefined or the default is better, use the default */ \
+        out.limitName = base;                                                     \
+    } else {                                                                      \
+        out.limitName = limits.limitName;                                         \
     }
         LIMITS(X)
 #undef X
@@ -128,7 +163,7 @@
     }
 
     MaybeError ValidateLimits(const Limits& supportedLimits, const Limits& requiredLimits) {
-#define X(Better, limitName, defaultValue)                                                      \
+#define X(Better, limitName, ...)                                                               \
     if (!IsLimitUndefined(requiredLimits.limitName)) {                                          \
         DAWN_TRY(CheckLimit<LimitBetterDirection::Better>::Validate(supportedLimits.limitName,  \
                                                                     requiredLimits.limitName)); \
@@ -138,4 +173,40 @@
         return {};
     }
 
+    Limits ApplyLimitTiers(Limits limits) {
+#define X_TIER_COUNT(Better, limitName, ...) , std::integer_sequence<uint64_t, __VA_ARGS__>{}.size()
+#define GET_TIER_COUNT(LIMIT_GROUP) \
+    ReduceSameValue(std::integer_sequence<uint32_t LIMIT_GROUP(X_TIER_COUNT)>{})
+
+#define X_EACH_GROUP(LIMIT_GROUP)                                    \
+    {                                                                \
+        constexpr uint32_t kTierCount = GET_TIER_COUNT(LIMIT_GROUP); \
+        for (uint32_t i = kTierCount; i != 0; --i) {                 \
+            LIMIT_GROUP(X_CHECK_BETTER_AND_CLAMP)                    \
+            /* Limits fit in tier and have been clamped. Break. */   \
+            break;                                                   \
+        }                                                            \
+    }
+
+#define X_CHECK_BETTER_AND_CLAMP(Better, limitName, ...)                                       \
+    {                                                                                          \
+        constexpr std::array<decltype(Limits::limitName), kTierCount> tiers{__VA_ARGS__};      \
+        decltype(Limits::limitName) tierValue = tiers[i - 1];                                  \
+        if (CheckLimit<LimitBetterDirection::Better>::IsBetter(tierValue, limits.limitName)) { \
+            /* The tier is better. Go to the next tier. */                                     \
+            continue;                                                                          \
+        } else if (tierValue != limits.limitName) {                                            \
+            /* Better than the tier. Degrade |limits| to the tier. */                          \
+            limits.limitName = tiers[i - 1];                                                   \
+        }                                                                                      \
+    }
+
+        LIMITS_EACH_GROUP(X_EACH_GROUP)
+#undef X_CHECK_BETTER
+#undef X_EACH_GROUP
+#undef GET_TIER_COUNT
+#undef X_TIER_COUNT
+        return limits;
+    }
+
 }  // namespace dawn_native
diff --git a/src/dawn_native/Limits.h b/src/dawn_native/Limits.h
index 409c1ff..4beed2e 100644
--- a/src/dawn_native/Limits.h
+++ b/src/dawn_native/Limits.h
@@ -35,6 +35,9 @@
     // Validate that |requiredLimits| are no better than |supportedLimits|.
     MaybeError ValidateLimits(const Limits& supportedLimits, const Limits& requiredLimits);
 
+    // Returns a copy of |limits| where limit tiers are applied.
+    Limits ApplyLimitTiers(Limits limits);
+
 }  // namespace dawn_native
 
 #endif  // DAWNNATIVE_LIMITS_H_
diff --git a/src/tests/unittests/LimitsTests.cpp b/src/tests/unittests/LimitsTests.cpp
index b8b403e..e931855 100644
--- a/src/tests/unittests/LimitsTests.cpp
+++ b/src/tests/unittests/LimitsTests.cpp
@@ -110,3 +110,91 @@
         EXPECT_TRUE(ValidateLimits(defaults, required).IsSuccess());
     }
 }
+
+// Test that |ApplyLimitTiers| degrades limits to the next best tier.
+TEST(Limits, ApplyLimitTiers) {
+    auto SetLimitsStorageBufferBindingSizeTier2 = [](dawn_native::Limits* limits) {
+        limits->maxStorageBufferBindingSize = 1073741824;
+    };
+    dawn_native::Limits limitsStorageBufferBindingSizeTier2;
+    dawn_native::GetDefaultLimits(&limitsStorageBufferBindingSizeTier2);
+    SetLimitsStorageBufferBindingSizeTier2(&limitsStorageBufferBindingSizeTier2);
+
+    auto SetLimitsStorageBufferBindingSizeTier3 = [](dawn_native::Limits* limits) {
+        limits->maxStorageBufferBindingSize = 2147483647;
+    };
+    dawn_native::Limits limitsStorageBufferBindingSizeTier3;
+    dawn_native::GetDefaultLimits(&limitsStorageBufferBindingSizeTier3);
+    SetLimitsStorageBufferBindingSizeTier3(&limitsStorageBufferBindingSizeTier3);
+
+    auto SetLimitsComputeWorkgroupStorageSizeTier1 = [](dawn_native::Limits* limits) {
+        limits->maxComputeWorkgroupStorageSize = 16352;
+    };
+    dawn_native::Limits limitsComputeWorkgroupStorageSizeTier1;
+    dawn_native::GetDefaultLimits(&limitsComputeWorkgroupStorageSizeTier1);
+    SetLimitsComputeWorkgroupStorageSizeTier1(&limitsComputeWorkgroupStorageSizeTier1);
+
+    auto SetLimitsComputeWorkgroupStorageSizeTier3 = [](dawn_native::Limits* limits) {
+        limits->maxComputeWorkgroupStorageSize = 65536;
+    };
+    dawn_native::Limits limitsComputeWorkgroupStorageSizeTier3;
+    dawn_native::GetDefaultLimits(&limitsComputeWorkgroupStorageSizeTier3);
+    SetLimitsComputeWorkgroupStorageSizeTier3(&limitsComputeWorkgroupStorageSizeTier3);
+
+    // Test that applying tiers to limits that are exactly
+    // equal to a tier returns the same values.
+    {
+        dawn_native::Limits limits = limitsStorageBufferBindingSizeTier2;
+        EXPECT_EQ(ApplyLimitTiers(limits), limits);
+
+        limits = limitsStorageBufferBindingSizeTier3;
+        EXPECT_EQ(ApplyLimitTiers(limits), limits);
+    }
+
+    // Test all limits slightly worse than tier 3.
+    {
+        dawn_native::Limits limits = limitsStorageBufferBindingSizeTier3;
+        limits.maxStorageBufferBindingSize -= 1;
+        EXPECT_EQ(ApplyLimitTiers(limits), limitsStorageBufferBindingSizeTier2);
+    }
+
+    // Test that limits may match one tier exactly and be degraded in another tier.
+    // Degrading to one tier does not affect the other tier.
+    {
+        dawn_native::Limits limits = limitsComputeWorkgroupStorageSizeTier3;
+        // Set tier 3 and change one limit to be insufficent.
+        SetLimitsStorageBufferBindingSizeTier3(&limits);
+        limits.maxStorageBufferBindingSize -= 1;
+
+        dawn_native::Limits tiered = ApplyLimitTiers(limits);
+
+        // Check that |tiered| has the limits of memorySize tier 2
+        dawn_native::Limits tieredWithMemorySizeTier2 = tiered;
+        SetLimitsStorageBufferBindingSizeTier2(&tieredWithMemorySizeTier2);
+        EXPECT_EQ(tiered, tieredWithMemorySizeTier2);
+
+        // Check that |tiered| has the limits of bindingSpace tier 3
+        dawn_native::Limits tieredWithBindingSpaceTier3 = tiered;
+        SetLimitsComputeWorkgroupStorageSizeTier3(&tieredWithBindingSpaceTier3);
+        EXPECT_EQ(tiered, tieredWithBindingSpaceTier3);
+    }
+
+    // Test that limits may be simultaneously degraded in two tiers independently.
+    {
+        dawn_native::Limits limits;
+        dawn_native::GetDefaultLimits(&limits);
+        SetLimitsComputeWorkgroupStorageSizeTier3(&limits);
+        SetLimitsStorageBufferBindingSizeTier3(&limits);
+        limits.maxComputeWorkgroupStorageSize =
+            limitsComputeWorkgroupStorageSizeTier1.maxComputeWorkgroupStorageSize + 1;
+        limits.maxStorageBufferBindingSize =
+            limitsStorageBufferBindingSizeTier2.maxStorageBufferBindingSize + 1;
+
+        dawn_native::Limits tiered = ApplyLimitTiers(limits);
+
+        dawn_native::Limits expected = tiered;
+        SetLimitsComputeWorkgroupStorageSizeTier1(&expected);
+        SetLimitsStorageBufferBindingSizeTier2(&expected);
+        EXPECT_EQ(tiered, expected);
+    }
+}