From 47f2a1414bf39de531f764e08faefafc91efd7d9 Mon Sep 17 00:00:00 2001 From: David Neto Date: Sat, 27 Aug 2016 14:49:53 -0400 Subject: [PATCH] Add libspirv::CapabilitySet It's optimized for the common case, where capabilities have value at most 63. --- source/CMakeLists.txt | 2 + source/capability_set.cpp | 75 +++++++++++++++++++ source/capability_set.h | 119 ++++++++++++++++++++++++++++++ source/val/ValidationState.cpp | 2 +- test/CMakeLists.txt | 1 + test/CapabilitySet.cpp | 164 +++++++++++++++++++++++++++++++++++++++++ test/UnitSPIRV.h | 10 +++ 7 files changed, 372 insertions(+), 1 deletion(-) create mode 100644 source/capability_set.cpp create mode 100644 source/capability_set.h create mode 100644 test/CapabilitySet.cpp diff --git a/source/CMakeLists.txt b/source/CMakeLists.txt index 2d7c599..d2a82af 100644 --- a/source/CMakeLists.txt +++ b/source/CMakeLists.txt @@ -129,6 +129,7 @@ set(SPIRV_SOURCES ${CMAKE_CURRENT_SOURCE_DIR}/util/hex_float.h ${CMAKE_CURRENT_SOURCE_DIR}/assembly_grammar.h ${CMAKE_CURRENT_SOURCE_DIR}/binary.h + ${CMAKE_CURRENT_SOURCE_DIR}/capability_set.h ${CMAKE_CURRENT_SOURCE_DIR}/diagnostic.h ${CMAKE_CURRENT_SOURCE_DIR}/ext_inst.h ${CMAKE_CURRENT_SOURCE_DIR}/instruction.h @@ -148,6 +149,7 @@ set(SPIRV_SOURCES ${CMAKE_CURRENT_SOURCE_DIR}/assembly_grammar.cpp ${CMAKE_CURRENT_SOURCE_DIR}/binary.cpp + ${CMAKE_CURRENT_SOURCE_DIR}/capability_set.cpp ${CMAKE_CURRENT_SOURCE_DIR}/diagnostic.cpp ${CMAKE_CURRENT_SOURCE_DIR}/disassemble.cpp ${CMAKE_CURRENT_SOURCE_DIR}/ext_inst.cpp diff --git a/source/capability_set.cpp b/source/capability_set.cpp new file mode 100644 index 0000000..f669fa2 --- /dev/null +++ b/source/capability_set.cpp @@ -0,0 +1,75 @@ +// Copyright (c) 2016 Google Inc. +// +// Permission is hereby granted, free of charge, to any person obtaining a +// copy of this software and/or associated documentation files (the +// "Materials"), to deal in the Materials without restriction, including +// without limitation the rights to use, copy, modify, merge, publish, +// distribute, sublicense, and/or sell copies of the Materials, and to +// permit persons to whom the Materials are furnished to do so, subject to +// the following conditions: +// +// The above copyright notice and this permission notice shall be included +// in all copies or substantial portions of the Materials. +// +// MODIFICATIONS TO THIS FILE MAY MEAN IT NO LONGER ACCURATELY REFLECTS +// KHRONOS STANDARDS. THE UNMODIFIED, NORMATIVE VERSIONS OF KHRONOS +// SPECIFICATIONS AND HEADER INFORMATION ARE LOCATED AT +// https://www.khronos.org/registry/ +// +// THE MATERIALS ARE PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +// IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +// TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +// MATERIALS OR THE USE OR OTHER DEALINGS IN THE MATERIALS. + +#include "capability_set.h" + +#include "spirv/1.1/spirv.hpp" + +namespace { + +// Determines whether the given capability can be represented +// as a bit in a uint64_t mask. If so, then returns that mask bit. +// Otherwise, returns 0. +uint64_t AsMask(uint32_t word) { + if (word > 63) return 0; + return uint64_t(1) << word; +} +} + +namespace libspirv { + +void CapabilitySet::Add(uint32_t word) { + if (auto new_bits = AsMask(word)) { + mask_ |= new_bits; + } else { + Overflow().insert(word); + } +} + +bool CapabilitySet::Contains(uint32_t word) const { + // We shouldn't call Overflow() since this is a const method. + if (auto bits = AsMask(word)) { + return mask_ & bits; + } else if (auto overflow = overflow_.get()) { + return overflow->find(word) != overflow->end(); + } + // The word is large, but the set doesn't have large members, so + // it doesn't have an overflow set. + return false; +} + +// Applies f to each capability in the set, in order from smallest enum +// value to largest. +void CapabilitySet::ForEach(std::function f) const { + for (uint32_t i = 0; i < 64; ++i) { + if (mask_ & AsMask(i)) f(static_cast(i)); + } + if (overflow_) { + for (uint32_t c : *overflow_) f(static_cast(c)); + } +} + +} // namespace libspirv diff --git a/source/capability_set.h b/source/capability_set.h new file mode 100644 index 0000000..c13e48f --- /dev/null +++ b/source/capability_set.h @@ -0,0 +1,119 @@ +// Copyright (c) 2016 Google Inc. +// +// Permission is hereby granted, free of charge, to any person obtaining a +// copy of this software and/or associated documentation files (the +// "Materials"), to deal in the Materials without restriction, including +// without limitation the rights to use, copy, modify, merge, publish, +// distribute, sublicense, and/or sell copies of the Materials, and to +// permit persons to whom the Materials are furnished to do so, subject to +// the following conditions: +// +// The above copyright notice and this permission notice shall be included +// in all copies or substantial portions of the Materials. +// +// MODIFICATIONS TO THIS FILE MAY MEAN IT NO LONGER ACCURATELY REFLECTS +// KHRONOS STANDARDS. THE UNMODIFIED, NORMATIVE VERSIONS OF KHRONOS +// SPECIFICATIONS AND HEADER INFORMATION ARE LOCATED AT +// https://www.khronos.org/registry/ +// +// THE MATERIALS ARE PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +// IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +// TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +// MATERIALS OR THE USE OR OTHER DEALINGS IN THE MATERIALS. + +#ifndef LIBSPIRV_CAPABILITY_SET_H +#define LIBSPIRV_CAPABILITY_SET_H + +#include +#include +#include +#include +#include + +#include "spirv/1.1/spirv.h" + +namespace libspirv { + +// A set of values of type SpvCapability. +// It is fast and compact for the common case, where capability values +// are at most 63. But it can represent capabilities with larger values, +// as may appear in extensions. +class CapabilitySet { + private: + // The ForEach method will call the functor on capabilities in + // enum value order (lowest to highest). To make that easier, use + // an ordered set for the overflow values. + using OverflowSetType = std::set; + + public: + // Construct an empty set. + CapabilitySet() = default; + // Construct an set with just the given capability. + explicit CapabilitySet(SpvCapability c) { Add(c); } + // Construct an set from an initializer list of capabilities. + CapabilitySet(std::initializer_list cs) { + for (auto c : cs) Add(c); + } + // Copy constructor. + CapabilitySet(const CapabilitySet& other) { *this = other; } + // Move constructor. The moved-from set is emptied. + CapabilitySet(CapabilitySet&& other) { + mask_ = other.mask_; + overflow_ = std::move(other.overflow_); + other.mask_ = 0; + other.overflow_.reset(nullptr); + } + // Assignment operator. + CapabilitySet& operator=(const CapabilitySet& other) { + if (&other != this) { + mask_ = other.mask_; + overflow_.reset(other.overflow_ ? new OverflowSetType(*other.overflow_) + : nullptr); + } + return *this; + } + + // Adds the given capability to the set. This has no effect if the + // capability is already in the set. + void Add(SpvCapability c) { Add(static_cast(c)); } + // Adds the given capability (as a 32-bit word) to the set. This has no + // effect if the capability is already in the set. + void Add(uint32_t); + + // Returns true if this capability is in the set. + bool Contains(SpvCapability c) const { + return Contains(static_cast(c)); + } + // Returns true if the capability represented as a 32-bit word is in the set. + bool Contains(uint32_t word) const; + + // Applies f to each capability in the set, in order from smallest enum + // value to largest. + void ForEach(std::function f) const; + + private: + // Returns true if the set has capabilities with value greater than 63. + bool HasOverflow() { return overflow_ != nullptr; } + + // Ensures that overflow_set_ references a set. A new empty set is + // allocated if one doesn't exist yet. Returns overflow_set_. + OverflowSetType& Overflow() { + if (overflow_.get() == nullptr) { + overflow_.reset(new OverflowSetType); + } + return *overflow_; + } + + // Capabilities with values up to 63 are stored as bits in this mask. + uint64_t mask_ = 0; + // Capabilities with values larger than 63 are stored in this set. + // This set should normally be empty or very small. + std::unique_ptr overflow_ = {}; +}; + +} // namespace libspirv + +#endif // LIBSPIRV_CAPABILITY_SET_H diff --git a/source/val/ValidationState.cpp b/source/val/ValidationState.cpp index 9cfe2da..f1eabd7 100644 --- a/source/val/ValidationState.cpp +++ b/source/val/ValidationState.cpp @@ -202,7 +202,7 @@ ValidationState_t::ValidationState_t(spv_diagnostic* diagnostic, operand_names_{}, current_layout_section_(kLayoutCapabilities), module_functions_(), - module_capabilities_(0u), + module_capabilities_(), ordered_instructions_(), all_definitions_(), grammar_(context), diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt index f106258..2215715 100644 --- a/test/CMakeLists.txt +++ b/test/CMakeLists.txt @@ -84,6 +84,7 @@ set(TEST_SOURCES ${CMAKE_CURRENT_SOURCE_DIR}/BinaryParse.cpp ${CMAKE_CURRENT_SOURCE_DIR}/BinaryToText.cpp ${CMAKE_CURRENT_SOURCE_DIR}/BinaryToText.Literal.cpp + ${CMAKE_CURRENT_SOURCE_DIR}/CapabilitySet.cpp ${CMAKE_CURRENT_SOURCE_DIR}/Comment.cpp ${CMAKE_CURRENT_SOURCE_DIR}/DiagnosticDestroy.cpp ${CMAKE_CURRENT_SOURCE_DIR}/DiagnosticPrint.cpp diff --git a/test/CapabilitySet.cpp b/test/CapabilitySet.cpp new file mode 100644 index 0000000..9b3d8c4 --- /dev/null +++ b/test/CapabilitySet.cpp @@ -0,0 +1,164 @@ +// Copyright (c) 2016 Google Inc. +// +// Permission is hereby granted, free of charge, to any person obtaining a +// copy of this software and/or associated documentation files (the +// "Materials"), to deal in the Materials without restriction, including +// without limitation the rights to use, copy, modify, merge, publish, +// distribute, sublicense, and/or sell copies of the Materials, and to +// permit persons to whom the Materials are furnished to do so, subject to +// the following conditions: +// +// The above copyright notice and this permission notice shall be included +// in all copies or substantial portions of the Materials. +// +// MODIFICATIONS TO THIS FILE MAY MEAN IT NO LONGER ACCURATELY REFLECTS +// KHRONOS STANDARDS. THE UNMODIFIED, NORMATIVE VERSIONS OF KHRONOS +// SPECIFICATIONS AND HEADER INFORMATION ARE LOCATED AT +// https://www.khronos.org/registry/ +// +// THE MATERIALS ARE PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +// IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +// TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +// MATERIALS OR THE USE OR OTHER DEALINGS IN THE MATERIALS. + +#include "capability_set.h" + +#include +#include "gmock/gmock.h" + +#include "UnitSPIRV.h" + +namespace { + +using libspirv::CapabilitySet; +using spvtest::ElementsIn; +using ::testing::Eq; +using ::testing::ValuesIn; + +TEST(CapabilitySet, DefaultIsEmpty) { + CapabilitySet c; + for (uint32_t i = 0; i < 1000; ++i) { + EXPECT_FALSE(c.Contains(i)); + EXPECT_FALSE(c.Contains(static_cast(i))); + } +} + +TEST(CapabilitySet, ConstructSingleMemberMatrix) { + CapabilitySet s(SpvCapabilityMatrix); + EXPECT_TRUE(s.Contains(SpvCapabilityMatrix)); + EXPECT_FALSE(s.Contains(SpvCapabilityShader)); + EXPECT_FALSE(s.Contains(1000)); +} + +TEST(CapabilitySet, ConstructSingleMemberMaxInMask) { + CapabilitySet s(static_cast(63)); + EXPECT_FALSE(s.Contains(SpvCapabilityMatrix)); + EXPECT_FALSE(s.Contains(SpvCapabilityShader)); + EXPECT_TRUE(s.Contains(63)); + EXPECT_FALSE(s.Contains(64)); + EXPECT_FALSE(s.Contains(1000)); +} + +TEST(CapabilitySet, ConstructSingleMemberMinOverflow) { + // Check the first one that forces overflow beyond the mask. + CapabilitySet s(static_cast(64)); + EXPECT_FALSE(s.Contains(SpvCapabilityMatrix)); + EXPECT_FALSE(s.Contains(SpvCapabilityShader)); + EXPECT_FALSE(s.Contains(63)); + EXPECT_TRUE(s.Contains(64)); + EXPECT_FALSE(s.Contains(1000)); +} + +TEST(CapabilitySet, ConstructSingleMemberMaxOverflow) { + // Check the max 32-bit signed int. + CapabilitySet s(SpvCapability(0x7fffffffu)); + EXPECT_FALSE(s.Contains(SpvCapabilityMatrix)); + EXPECT_FALSE(s.Contains(SpvCapabilityShader)); + EXPECT_FALSE(s.Contains(1000)); + EXPECT_TRUE(s.Contains(0x7fffffffu)); +} + +TEST(CapabilitySet, AddEnum) { + CapabilitySet s(SpvCapabilityShader); + s.Add(SpvCapabilityKernel); + EXPECT_FALSE(s.Contains(SpvCapabilityMatrix)); + EXPECT_TRUE(s.Contains(SpvCapabilityShader)); + EXPECT_TRUE(s.Contains(SpvCapabilityKernel)); +} + +TEST(CapabilitySet, AddInt) { + CapabilitySet s(SpvCapabilityShader); + s.Add(42); + EXPECT_FALSE(s.Contains(SpvCapabilityMatrix)); + EXPECT_TRUE(s.Contains(SpvCapabilityShader)); + EXPECT_TRUE(s.Contains(42)); + EXPECT_TRUE(s.Contains(static_cast(42))); +} + +TEST(CapabilitySet, InitializerListEmpty) { + CapabilitySet s{}; + for (uint32_t i = 0; i < 1000; i++) { + EXPECT_FALSE(s.Contains(i)); + } +} + +struct ForEachCase { + CapabilitySet capabilities; + std::vector expected; +}; + +using CapabilitySetForEachTest = ::testing::TestWithParam; + +TEST_P(CapabilitySetForEachTest, CallsAsExpected) { + EXPECT_THAT(ElementsIn(GetParam().capabilities), Eq(GetParam().expected)); +} + +TEST_P(CapabilitySetForEachTest, CopyConstructor) { + CapabilitySet copy(GetParam().capabilities); + EXPECT_THAT(ElementsIn(copy), Eq(GetParam().expected)); +} + +TEST_P(CapabilitySetForEachTest, MoveConstructor) { + // We need a writable copy to move from. + CapabilitySet copy(GetParam().capabilities); + CapabilitySet moved(std::move(copy)); + EXPECT_THAT(ElementsIn(moved), Eq(GetParam().expected)); + + // The moved-from set is empty. + EXPECT_THAT(ElementsIn(copy), Eq(std::vector{})); +} + +TEST_P(CapabilitySetForEachTest, OperatorEquals) { + CapabilitySet assigned = GetParam().capabilities; + EXPECT_THAT(ElementsIn(assigned), Eq(GetParam().expected)); +} + +TEST_P(CapabilitySetForEachTest, OperatorEqualsSelfAssign) { + CapabilitySet assigned{GetParam().capabilities}; + assigned = assigned; + EXPECT_THAT(ElementsIn(assigned), Eq(GetParam().expected)); +} + +INSTANTIATE_TEST_CASE_P(Samples, CapabilitySetForEachTest, + ValuesIn(std::vector{ + {{}, {}}, + {{SpvCapabilityMatrix}, {SpvCapabilityMatrix}}, + {{SpvCapabilityKernel, SpvCapabilityShader}, + {SpvCapabilityShader, SpvCapabilityKernel}}, + {{static_cast(999)}, + {static_cast(999)}}, + {{static_cast(0x7fffffff)}, + {static_cast(0x7fffffff)}}, + // Mixture and out of order + {{static_cast(0x7fffffff), + static_cast(100), + SpvCapabilityShader, SpvCapabilityMatrix}, + {SpvCapabilityMatrix, SpvCapabilityShader, + static_cast(100), + static_cast(0x7fffffff)}}, + }), ); + +} // anonymous namespace diff --git a/test/UnitSPIRV.h b/test/UnitSPIRV.h index 5456672..2d91766 100644 --- a/test/UnitSPIRV.h +++ b/test/UnitSPIRV.h @@ -30,9 +30,11 @@ #include #include +#include #include "source/assembly_grammar.h" #include "source/binary.h" +#include "source/capability_set.h" #include "source/diagnostic.h" #include "source/opcode.h" #include "source/spirv_endian.h" @@ -224,5 +226,13 @@ inline std::vector AllTargetEnvironments() { SPV_ENV_OPENGL_4_5}; } +// Returns the capabilities in a CapabilitySet as an ordered vector. +inline std::vector ElementsIn( + const libspirv::CapabilitySet& capabilities) { + std::vector result; + capabilities.ForEach([&result](SpvCapability c) { result.push_back(c); }); + return result; +} + } // namespace spvtest #endif // LIBSPIRV_TEST_UNITSPIRV_H_ -- 2.7.4