resolver: Deterministic constant ID allocation
Use global declaration order for allocating implicit
pipeline-overridable constant IDs, instead of iterating over an
unordered_map.
Bug: tint:1155
Change-Id: Ia5ff534c617b0d57e45fc20dd0a5a591854e6473
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/65522
Kokoro: Kokoro <noreply+kokoro@google.com>
Reviewed-by: Ben Clayton <bclayton@google.com>
diff --git a/src/resolver/pipeline_overridable_constant_test.cc b/src/resolver/pipeline_overridable_constant_test.cc
index 5d0571f..1ff83dc 100644
--- a/src/resolver/pipeline_overridable_constant_test.cc
+++ b/src/resolver/pipeline_overridable_constant_test.cc
@@ -14,16 +14,26 @@
#include "src/resolver/resolver.h"
-#include "gmock/gmock.h"
#include "src/resolver/resolver_test_helper.h"
-using ::testing::UnorderedElementsAre;
-
namespace tint {
namespace resolver {
namespace {
-using ResolverPipelineOverridableConstantTest = ResolverTest;
+class ResolverPipelineOverridableConstantTest : public ResolverTest {
+ protected:
+ /// Verify that the AST node `var` was resolved to an overridable constant
+ /// with an ID equal to `id`.
+ /// @param var the overridable constant AST node
+ /// @param id the expected constant ID
+ void ExpectConstantId(const ast::Variable* var, uint16_t id) {
+ auto* sem = Sem().Get<sem::GlobalVariable>(var);
+ ASSERT_NE(sem, nullptr);
+ EXPECT_EQ(sem->Declaration(), var);
+ EXPECT_TRUE(sem->IsPipelineConstant());
+ EXPECT_EQ(sem->ConstantId(), id);
+ }
+};
TEST_F(ResolverPipelineOverridableConstantTest, NonOverridable) {
auto* a = GlobalConst("a", ty.f32(), Construct(ty.f32()));
@@ -41,11 +51,7 @@
EXPECT_TRUE(r()->Resolve()) << r()->error();
- auto* sem_a = Sem().Get<sem::GlobalVariable>(a);
- ASSERT_NE(sem_a, nullptr);
- EXPECT_EQ(sem_a->Declaration(), a);
- EXPECT_TRUE(sem_a->IsPipelineConstant());
- EXPECT_EQ(sem_a->ConstantId(), 7u);
+ ExpectConstantId(a, 7u);
}
TEST_F(ResolverPipelineOverridableConstantTest, WithoutId) {
@@ -53,37 +59,27 @@
EXPECT_TRUE(r()->Resolve()) << r()->error();
- auto* sem_a = Sem().Get<sem::GlobalVariable>(a);
- ASSERT_NE(sem_a, nullptr);
- EXPECT_EQ(sem_a->Declaration(), a);
- EXPECT_TRUE(sem_a->IsPipelineConstant());
- EXPECT_EQ(sem_a->ConstantId(), 0u);
+ ExpectConstantId(a, 0u);
}
TEST_F(ResolverPipelineOverridableConstantTest, WithAndWithoutIds) {
std::vector<ast::Variable*> variables;
- variables.push_back(
- GlobalConst("a", ty.f32(), Construct(ty.f32()), {Override()}));
- variables.push_back(
- GlobalConst("b", ty.f32(), Construct(ty.f32()), {Override()}));
- variables.push_back(
- GlobalConst("c", ty.f32(), Construct(ty.f32()), {Override(2u)}));
- variables.push_back(
- GlobalConst("d", ty.f32(), Construct(ty.f32()), {Override(4u)}));
- variables.push_back(
- GlobalConst("e", ty.f32(), Construct(ty.f32()), {Override()}));
- variables.push_back(
- GlobalConst("f", ty.f32(), Construct(ty.f32()), {Override(1u)}));
+ auto* a = GlobalConst("a", ty.f32(), Construct(ty.f32()), {Override()});
+ auto* b = GlobalConst("b", ty.f32(), Construct(ty.f32()), {Override()});
+ auto* c = GlobalConst("c", ty.f32(), Construct(ty.f32()), {Override(2u)});
+ auto* d = GlobalConst("d", ty.f32(), Construct(ty.f32()), {Override(4u)});
+ auto* e = GlobalConst("e", ty.f32(), Construct(ty.f32()), {Override()});
+ auto* f = GlobalConst("f", ty.f32(), Construct(ty.f32()), {Override(1u)});
EXPECT_TRUE(r()->Resolve()) << r()->error();
- std::vector<uint16_t> constant_ids;
- for (auto* var : variables) {
- auto* sem = Sem().Get<sem::GlobalVariable>(var);
- ASSERT_NE(sem, nullptr);
- constant_ids.push_back(static_cast<uint16_t>(sem->ConstantId()));
- }
- EXPECT_THAT(constant_ids, UnorderedElementsAre(0u, 3u, 2u, 4u, 5u, 1u));
+ // Verify that constant id allocation order is deterministic.
+ ExpectConstantId(a, 0u);
+ ExpectConstantId(b, 3u);
+ ExpectConstantId(c, 2u);
+ ExpectConstantId(d, 4u);
+ ExpectConstantId(e, 5u);
+ ExpectConstantId(f, 1u);
}
TEST_F(ResolverPipelineOverridableConstantTest, DuplicateIds) {
diff --git a/src/resolver/resolver.cc b/src/resolver/resolver.cc
index 6eb4470..9617d5d 100644
--- a/src/resolver/resolver.cc
+++ b/src/resolver/resolver.cc
@@ -264,6 +264,8 @@
}
}
+ AllocateOverridableConstantIds();
+
if (!ValidatePipelineStages()) {
return false;
}
@@ -576,6 +578,46 @@
return ast::Access::kReadWrite;
}
+void Resolver::AllocateOverridableConstantIds() {
+ // The next pipeline constant ID to try to allocate.
+ uint16_t next_constant_id = 0;
+
+ // Allocate constant IDs in global declaration order, so that they are
+ // deterministic.
+ // TODO(crbug.com/tint/1192): If a transform changes the order or removes an
+ // unused constant, the allocation may change on the next Resolver pass.
+ for (auto* decl : builder_->AST().GlobalDeclarations()) {
+ auto* var = decl->As<ast::Variable>();
+ if (!var) {
+ continue;
+ }
+ auto* override_deco =
+ ast::GetDecoration<ast::OverrideDecoration>(var->decorations());
+ if (!override_deco) {
+ continue;
+ }
+
+ uint16_t constant_id;
+ if (override_deco->HasValue()) {
+ constant_id = static_cast<uint16_t>(override_deco->value());
+ } else {
+ // No ID was specified, so allocate the next available ID.
+ constant_id = next_constant_id;
+ while (constant_ids_.count(constant_id)) {
+ if (constant_id == UINT16_MAX) {
+ TINT_ICE(Resolver, builder_->Diagnostics())
+ << "no more pipeline constant IDs available";
+ return;
+ }
+ constant_id++;
+ }
+ next_constant_id = constant_id + 1;
+ }
+
+ variable_to_info_[var]->constant_id = constant_id;
+ }
+}
+
bool Resolver::ValidateVariableConstructor(const ast::Variable* var,
ast::StorageClass storage_class,
const sem::Type* storage_type,
@@ -3709,9 +3751,6 @@
}
}
- // The next pipeline constant ID to try to allocate.
- uint16_t next_constant_id = 0;
-
// Create semantic nodes for all ast::Variables
std::unordered_map<const tint::ast::Variable*, sem::Parameter*> sem_params;
for (auto it : variable_to_info_) {
@@ -3720,28 +3759,10 @@
sem::Variable* sem_var = nullptr;
- if (auto* override_deco =
- ast::GetDecoration<ast::OverrideDecoration>(var->decorations())) {
+ if (ast::HasDecoration<ast::OverrideDecoration>(var->decorations())) {
// Create a pipeline overridable constant.
- uint16_t constant_id;
- if (override_deco->HasValue()) {
- constant_id = static_cast<uint16_t>(override_deco->value());
- } else {
- // No ID was specified, so allocate the next available ID.
- constant_id = next_constant_id;
- while (constant_ids_.count(constant_id)) {
- if (constant_id == UINT16_MAX) {
- TINT_ICE(Resolver, builder_->Diagnostics())
- << "no more pipeline constant IDs available";
- return;
- }
- constant_id++;
- }
- next_constant_id = constant_id + 1;
- }
-
- sem_var =
- builder_->create<sem::GlobalVariable>(var, info->type, constant_id);
+ sem_var = builder_->create<sem::GlobalVariable>(var, info->type,
+ info->constant_id);
} else {
switch (info->kind) {
case VariableKind::kGlobal:
diff --git a/src/resolver/resolver.h b/src/resolver/resolver.h
index ccbb97b..18965be 100644
--- a/src/resolver/resolver.h
+++ b/src/resolver/resolver.h
@@ -116,6 +116,7 @@
sem::BindingPoint binding_point;
VariableKind kind;
uint32_t index = 0; // Parameter index, if kind == kParameter
+ uint16_t constant_id = 0;
};
struct IntrinsicCallInfo {
@@ -268,7 +269,7 @@
/// root node, and ending with leaf nodes
/// @return true on success, false on error
bool TraverseExpressions(ast::Expression* root,
- std::vector<ast::Expression*>& out);
+ std::vector<ast::Expression*>& out);
// AST and Type validation methods
// Each return true on success, false on failure.
@@ -391,6 +392,9 @@
/// @returns the default access control for the given storage class
ast::Access DefaultAccessForStorageClass(ast::StorageClass storage_class);
+ /// Allocate constant IDs for pipeline-overridable constants.
+ void AllocateOverridableConstantIds();
+
/// @returns the resolved type of the ast::Expression `expr`
/// @param expr the expression
sem::Type* TypeOf(const ast::Expression* expr);