spirv-val: Optimize struct field decoration lookup (#4809)
A std::set is used instead of std::vector, where the elements are
ordered by member index first. Decorations for fields are now looked up
by going over the range of decorations for the member only, instead of
the whole set.
In an ANGLE test that generates a struct with 4096 members, validation
goes down from ~140ms to ~90ms. On debug builds, the difference is more
pronounced, going down from ~2.5s to ~600ms.
diff --git a/source/val/decoration.h b/source/val/decoration.h
index ed3320f..4f53f20 100644
--- a/source/val/decoration.h
+++ b/source/val/decoration.h
@@ -69,6 +69,15 @@
std::vector<uint32_t>& params() { return params_; }
const std::vector<uint32_t>& params() const { return params_; }
+ inline bool operator<(const Decoration& rhs) const {
+ // Note: Sort by struct_member_index_ first, then type, so look up can be
+ // efficient using lower_bound() and upper_bound().
+ if (struct_member_index_ < rhs.struct_member_index_) return true;
+ if (rhs.struct_member_index_ < struct_member_index_) return false;
+ if (dec_type_ < rhs.dec_type_) return true;
+ if (rhs.dec_type_ < dec_type_) return false;
+ return params_ < rhs.params_;
+ }
inline bool operator==(const Decoration& rhs) const {
return (dec_type_ == rhs.dec_type_ && params_ == rhs.params_ &&
struct_member_index_ == rhs.struct_member_index_);
diff --git a/source/val/validate_annotation.cpp b/source/val/validate_annotation.cpp
index 40f2118..c27c799 100644
--- a/source/val/validate_annotation.cpp
+++ b/source/val/validate_annotation.cpp
@@ -581,7 +581,7 @@
// Word 1 is the group <id>. All subsequent words are target <id>s that
// are going to be decorated with the decorations.
const uint32_t decoration_group_id = inst->word(1);
- std::vector<Decoration>& group_decorations =
+ std::set<Decoration>& group_decorations =
_.id_decorations(decoration_group_id);
for (size_t i = 2; i < inst->words().size(); ++i) {
const uint32_t target_id = inst->word(i);
@@ -595,7 +595,7 @@
// pairs. All decorations of the group should be applied to all the struct
// members that are specified in the instructions.
const uint32_t decoration_group_id = inst->word(1);
- std::vector<Decoration>& group_decorations =
+ std::set<Decoration>& group_decorations =
_.id_decorations(decoration_group_id);
// Grammar checks ensures that the number of arguments to this instruction
// is an odd number: 1 decoration group + (id,literal) pairs.
diff --git a/source/val/validate_decorations.cpp b/source/val/validate_decorations.cpp
index 73d512a..b9448e3 100644
--- a/source/val/validate_decorations.cpp
+++ b/source/val/validate_decorations.cpp
@@ -346,10 +346,13 @@
const auto& lastMember = members.back();
uint32_t offset = 0xffffffff;
// Find the offset of the last element and add the size.
- for (auto& decoration : vstate.id_decorations(member_id)) {
- if (SpvDecorationOffset == decoration.dec_type() &&
- decoration.struct_member_index() == (int)lastIdx) {
- offset = decoration.params()[0];
+ auto member_decorations =
+ vstate.id_member_decorations(member_id, lastIdx);
+ for (auto decoration = member_decorations.begin;
+ decoration != member_decorations.end; ++decoration) {
+ assert(decoration->struct_member_index() == (int)lastIdx);
+ if (SpvDecorationOffset == decoration->dec_type()) {
+ offset = decoration->params()[0];
}
}
// This check depends on the fact that all members have offsets. This
@@ -445,15 +448,17 @@
for (uint32_t memberIdx = 0, numMembers = uint32_t(members.size());
memberIdx < numMembers; memberIdx++) {
uint32_t offset = 0xffffffff;
- for (auto& decoration : vstate.id_decorations(struct_id)) {
- if (decoration.struct_member_index() == (int)memberIdx) {
- switch (decoration.dec_type()) {
- case SpvDecorationOffset:
- offset = decoration.params()[0];
- break;
- default:
- break;
- }
+ auto member_decorations =
+ vstate.id_member_decorations(struct_id, memberIdx);
+ for (auto decoration = member_decorations.begin;
+ decoration != member_decorations.end; ++decoration) {
+ assert(decoration->struct_member_index() == (int)memberIdx);
+ switch (decoration->dec_type()) {
+ case SpvDecorationOffset:
+ offset = decoration->params()[0];
+ break;
+ default:
+ break;
}
}
member_offsets.push_back(
@@ -878,21 +883,23 @@
LayoutConstraints& constraint =
(*constraints)[std::make_pair(struct_id, memberIdx)];
constraint = inherited;
- for (auto& decoration : vstate.id_decorations(struct_id)) {
- if (decoration.struct_member_index() == (int)memberIdx) {
- switch (decoration.dec_type()) {
- case SpvDecorationRowMajor:
- constraint.majorness = kRowMajor;
- break;
- case SpvDecorationColMajor:
- constraint.majorness = kColumnMajor;
- break;
- case SpvDecorationMatrixStride:
- constraint.matrix_stride = decoration.params()[0];
- break;
- default:
- break;
- }
+ auto member_decorations =
+ vstate.id_member_decorations(struct_id, memberIdx);
+ for (auto decoration = member_decorations.begin;
+ decoration != member_decorations.end; ++decoration) {
+ assert(decoration->struct_member_index() == (int)memberIdx);
+ switch (decoration->dec_type()) {
+ case SpvDecorationRowMajor:
+ constraint.majorness = kRowMajor;
+ break;
+ case SpvDecorationColMajor:
+ constraint.majorness = kColumnMajor;
+ break;
+ case SpvDecorationMatrixStride:
+ constraint.matrix_stride = decoration->params()[0];
+ break;
+ default:
+ break;
}
}
diff --git a/source/val/validate_memory.cpp b/source/val/validate_memory.cpp
index af9da67..cfdea73 100644
--- a/source/val/validate_memory.cpp
+++ b/source/val/validate_memory.cpp
@@ -35,8 +35,8 @@
const Instruction*);
bool HaveSameLayoutDecorations(ValidationState_t&, const Instruction*,
const Instruction*);
-bool HasConflictingMemberOffsets(const std::vector<Decoration>&,
- const std::vector<Decoration>&);
+bool HasConflictingMemberOffsets(const std::set<Decoration>&,
+ const std::set<Decoration>&);
bool IsAllowedTypeOrArrayOfSame(ValidationState_t& _, const Instruction* type,
std::initializer_list<uint32_t> allowed) {
@@ -105,10 +105,8 @@
"type1 must be an OpTypeStruct instruction.");
assert(type2->opcode() == SpvOpTypeStruct &&
"type2 must be an OpTypeStruct instruction.");
- const std::vector<Decoration>& type1_decorations =
- _.id_decorations(type1->id());
- const std::vector<Decoration>& type2_decorations =
- _.id_decorations(type2->id());
+ const std::set<Decoration>& type1_decorations = _.id_decorations(type1->id());
+ const std::set<Decoration>& type2_decorations = _.id_decorations(type2->id());
// TODO: Will have to add other check for arrays an matricies if we want to
// handle them.
@@ -120,8 +118,8 @@
}
bool HasConflictingMemberOffsets(
- const std::vector<Decoration>& type1_decorations,
- const std::vector<Decoration>& type2_decorations) {
+ const std::set<Decoration>& type1_decorations,
+ const std::set<Decoration>& type2_decorations) {
{
// We are interested in conflicting decoration. If a decoration is in one
// list but not the other, then we will assume the code is correct. We are
diff --git a/source/val/validation_state.h b/source/val/validation_state.h
index 4888840..2178046 100644
--- a/source/val/validation_state.h
+++ b/source/val/validation_state.h
@@ -375,17 +375,14 @@
/// Registers the decoration for the given <id>
void RegisterDecorationForId(uint32_t id, const Decoration& dec) {
auto& dec_list = id_decorations_[id];
- auto lb = std::find(dec_list.begin(), dec_list.end(), dec);
- if (lb == dec_list.end()) {
- dec_list.push_back(dec);
- }
+ dec_list.insert(dec);
}
/// Registers the list of decorations for the given <id>
template <class InputIt>
void RegisterDecorationsForId(uint32_t id, InputIt begin, InputIt end) {
- std::vector<Decoration>& cur_decs = id_decorations_[id];
- cur_decs.insert(cur_decs.end(), begin, end);
+ std::set<Decoration>& cur_decs = id_decorations_[id];
+ cur_decs.insert(begin, end);
}
/// Registers the list of decorations for the given member of the given
@@ -394,21 +391,44 @@
void RegisterDecorationsForStructMember(uint32_t struct_id,
uint32_t member_index, InputIt begin,
InputIt end) {
- RegisterDecorationsForId(struct_id, begin, end);
- for (auto& decoration : id_decorations_[struct_id]) {
- decoration.set_struct_member_index(member_index);
+ std::set<Decoration>& cur_decs = id_decorations_[struct_id];
+ for (InputIt iter = begin; iter != end; ++iter) {
+ Decoration dec = *iter;
+ dec.set_struct_member_index(member_index);
+ cur_decs.insert(dec);
}
}
/// Returns all the decorations for the given <id>. If no decorations exist
- /// for the <id>, it registers an empty vector for it in the map and
- /// returns the empty vector.
- std::vector<Decoration>& id_decorations(uint32_t id) {
+ /// for the <id>, it registers an empty set for it in the map and
+ /// returns the empty set.
+ std::set<Decoration>& id_decorations(uint32_t id) {
return id_decorations_[id];
}
+ /// Returns the range of decorations for the given field of the given <id>.
+ struct FieldDecorationsIter {
+ std::set<Decoration>::const_iterator begin;
+ std::set<Decoration>::const_iterator end;
+ };
+ FieldDecorationsIter id_member_decorations(uint32_t id,
+ uint32_t member_index) {
+ const auto& decorations = id_decorations_[id];
+
+ // The decorations are sorted by member_index, so this look up will give the
+ // exact range of decorations for this member index.
+ Decoration min_decoration((SpvDecoration)0, {}, member_index);
+ Decoration max_decoration(SpvDecorationMax, {}, member_index);
+
+ FieldDecorationsIter result;
+ result.begin = decorations.lower_bound(min_decoration);
+ result.end = decorations.upper_bound(max_decoration);
+
+ return result;
+ }
+
// Returns const pointer to the internal decoration container.
- const std::map<uint32_t, std::vector<Decoration>>& id_decorations() const {
+ const std::map<uint32_t, std::set<Decoration>>& id_decorations() const {
return id_decorations_;
}
@@ -826,7 +846,7 @@
struct_has_nested_blockorbufferblock_struct_;
/// Stores the list of decorations for a given <id>
- std::map<uint32_t, std::vector<Decoration>> id_decorations_;
+ std::map<uint32_t, std::set<Decoration>> id_decorations_;
/// Stores type declarations which need to be unique (i.e. non-aggregates),
/// in the form [opcode, operand words], result_id is not stored.
diff --git a/test/val/val_decoration_test.cpp b/test/val/val_decoration_test.cpp
index e7ecb61..3c68263 100644
--- a/test/val/val_decoration_test.cpp
+++ b/test/val/val_decoration_test.cpp
@@ -62,8 +62,8 @@
// Must have 2 decorations.
EXPECT_THAT(
vstate_->id_decorations(id),
- Eq(std::vector<Decoration>{Decoration(SpvDecorationArrayStride, {4}),
- Decoration(SpvDecorationRelaxedPrecision)}));
+ Eq(std::set<Decoration>{Decoration(SpvDecorationArrayStride, {4}),
+ Decoration(SpvDecorationRelaxedPrecision)}));
}
TEST_F(ValidateDecorations, ValidateOpMemberDecorateRegistration) {
@@ -88,15 +88,15 @@
const uint32_t arr_id = 1;
EXPECT_THAT(
vstate_->id_decorations(arr_id),
- Eq(std::vector<Decoration>{Decoration(SpvDecorationArrayStride, {4})}));
+ Eq(std::set<Decoration>{Decoration(SpvDecorationArrayStride, {4})}));
// The struct must have 3 decorations.
const uint32_t struct_id = 2;
EXPECT_THAT(
vstate_->id_decorations(struct_id),
- Eq(std::vector<Decoration>{Decoration(SpvDecorationNonReadable, {}, 2),
- Decoration(SpvDecorationOffset, {2}, 2),
- Decoration(SpvDecorationBufferBlock)}));
+ Eq(std::set<Decoration>{Decoration(SpvDecorationNonReadable, {}, 2),
+ Decoration(SpvDecorationOffset, {2}, 2),
+ Decoration(SpvDecorationBufferBlock)}));
}
TEST_F(ValidateDecorations, ValidateOpMemberDecorateOutOfBound) {
@@ -151,9 +151,9 @@
// Decoration group has 3 decorations.
auto expected_decorations =
- std::vector<Decoration>{Decoration(SpvDecorationDescriptorSet, {0}),
- Decoration(SpvDecorationRelaxedPrecision),
- Decoration(SpvDecorationRestrict)};
+ std::set<Decoration>{Decoration(SpvDecorationDescriptorSet, {0}),
+ Decoration(SpvDecorationRelaxedPrecision),
+ Decoration(SpvDecorationRestrict)};
// Decoration group is applied to id 1, 2, 3, and 4. Note that id 1 (which is
// the decoration group id) also has all the decorations.
@@ -181,7 +181,7 @@
EXPECT_EQ(SPV_SUCCESS, ValidateAndRetrieveValidationState());
// Decoration group has 1 decoration.
auto expected_decorations =
- std::vector<Decoration>{Decoration(SpvDecorationOffset, {3}, 3)};
+ std::set<Decoration>{Decoration(SpvDecorationOffset, {3}, 3)};
// Decoration group is applied to id 2, 3, and 4.
EXPECT_THAT(vstate_->id_decorations(2), Eq(expected_decorations));
