Use a bit vector in ADCE
The unordered_set in ADCE that holds all of the live instructions takes
a very long time to be destroyed. In some shaders, it takes over 40% of
the time.
If we look at the unique ids of the live instructions, I believe they
are dense enough make a simple bit vector a good choice for to hold that
data. When I check the density of the bit vector for larger shaders, we
are usually using less than 4 bytes per element in the vector, and
almost always less than 16.
So, in this commit, I introduce a simple bit vector class, and
use it in ADCE.
This help improve the compile time for some shaders on windows by the
40% mentioned above.
Contributes to https://github.com/KhronosGroup/SPIRV-Tools/issues/1328.
diff --git a/source/CMakeLists.txt b/source/CMakeLists.txt
index e944475..d9f5955 100644
--- a/source/CMakeLists.txt
+++ b/source/CMakeLists.txt
@@ -218,6 +218,7 @@
${CMAKE_CURRENT_SOURCE_DIR}/util/bitutils.h
${CMAKE_CURRENT_SOURCE_DIR}/util/bit_stream.h
+ ${CMAKE_CURRENT_SOURCE_DIR}/util/bit_vector.h
${CMAKE_CURRENT_SOURCE_DIR}/util/hex_float.h
${CMAKE_CURRENT_SOURCE_DIR}/util/parse_number.h
${CMAKE_CURRENT_SOURCE_DIR}/util/string_utils.h
@@ -253,6 +254,7 @@
${CMAKE_CURRENT_SOURCE_DIR}/validate.h
${CMAKE_CURRENT_SOURCE_DIR}/util/bit_stream.cpp
+ ${CMAKE_CURRENT_SOURCE_DIR}/util/bit_vector.cpp
${CMAKE_CURRENT_SOURCE_DIR}/util/parse_number.cpp
${CMAKE_CURRENT_SOURCE_DIR}/util/string_utils.cpp
${CMAKE_CURRENT_SOURCE_DIR}/assembly_grammar.cpp
diff --git a/source/opt/aggressive_dead_code_elim_pass.cpp b/source/opt/aggressive_dead_code_elim_pass.cpp
index 014ce00..71ad809 100644
--- a/source/opt/aggressive_dead_code_elim_pass.cpp
+++ b/source/opt/aggressive_dead_code_elim_pass.cpp
@@ -477,11 +477,6 @@
void AggressiveDCEPass::Initialize(ir::IRContext* c) {
InitializeProcessing(c);
- // Clear collections
- worklist_ = std::queue<ir::Instruction*>{};
- live_insts_.clear();
- live_local_vars_.clear();
-
// Initialize extensions whitelist
InitExtensions();
}
diff --git a/source/opt/aggressive_dead_code_elim_pass.h b/source/opt/aggressive_dead_code_elim_pass.h
index 9c1749b..aefdd70 100644
--- a/source/opt/aggressive_dead_code_elim_pass.h
+++ b/source/opt/aggressive_dead_code_elim_pass.h
@@ -17,6 +17,7 @@
#ifndef LIBSPIRV_OPT_AGGRESSIVE_DCE_PASS_H_
#define LIBSPIRV_OPT_AGGRESSIVE_DCE_PASS_H_
+#include <util/bit_vector.h>
#include <algorithm>
#include <map>
#include <queue>
@@ -60,7 +61,7 @@
// Return true if |inst| is marked live.
bool IsLive(const ir::Instruction* inst) const {
- return live_insts_.find(inst) != live_insts_.end();
+ return live_insts_.Get(inst->unique_id());
}
// Returns true if |inst| is dead.
@@ -72,7 +73,9 @@
// Add |inst| to worklist_ and live_insts_.
void AddToWorklist(ir::Instruction* inst) {
- if (live_insts_.insert(inst).second) worklist_.push(inst);
+ if (!live_insts_.Set(inst->unique_id())) {
+ worklist_.push(inst);
+ }
}
// Add all store instruction which use |ptrId|, directly or indirectly,
@@ -168,7 +171,7 @@
std::vector<ir::Instruction*> private_stores_;
// Live Instructions
- std::unordered_set<const ir::Instruction*> live_insts_;
+ utils::BitVector live_insts_;
// Live Local Variables
std::unordered_set<uint32_t> live_local_vars_;
diff --git a/source/util/bit_vector.cpp b/source/util/bit_vector.cpp
new file mode 100644
index 0000000..80c0f0c
--- /dev/null
+++ b/source/util/bit_vector.cpp
@@ -0,0 +1,40 @@
+// Copyright (c) 2018 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "bit_vector.h"
+
+#include <iostream>
+
+namespace spvtools {
+namespace utils {
+
+void BitVector::ReportDensity(std::ostream& out) {
+ uint32_t count = 0;
+
+ for (BitContainer e : bits_) {
+ while (e != 0) {
+ if ((e & 1) != 0) {
+ ++count;
+ }
+ e = e >> 1;
+ }
+ }
+
+ out << "count=" << count
+ << ", total size (bytes)=" << bits_.size() * sizeof(BitContainer)
+ << ", bytes per element="
+ << (double)(bits_.size() * sizeof(BitContainer)) / (double)(count);
+}
+} // namespace utils
+} // namespace spvtools
diff --git a/source/util/bit_vector.h b/source/util/bit_vector.h
new file mode 100644
index 0000000..f8a654d
--- /dev/null
+++ b/source/util/bit_vector.h
@@ -0,0 +1,102 @@
+// Copyright (c) 2018 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef LIBSPIRV_UTILS_BIT_VECTOR_H_
+#define LIBSPIRV_UTILS_BIT_VECTOR_H_
+
+#include <cstdint>
+#include <iosfwd>
+#include <vector>
+
+namespace spvtools {
+namespace utils {
+
+// Implements a bit vector class.
+//
+// All bits default to zero, and the upper bound is 2^32-1.
+class BitVector {
+ private:
+ using BitContainer = uint64_t;
+ enum { kBitContainerSize = 64 };
+ enum { kInitialNumBits = 1024 };
+
+ public:
+ // Creates a bit vector contianing 0s.
+ BitVector() : bits_(kInitialNumBits / kBitContainerSize, 0) {}
+
+ // Sets the |i|th bit to 1. Returns the |i|th bit before it was set.
+ bool Set(uint32_t i) {
+ uint32_t element_index = i / kBitContainerSize;
+ uint32_t bit_in_element = i % kBitContainerSize;
+
+ if (element_index >= bits_.size()) {
+ bits_.resize(element_index + 1, 0);
+ }
+
+ BitContainer original = bits_[element_index];
+ BitContainer ith_bit = static_cast<BitContainer>(1) << bit_in_element;
+
+ if ((original & ith_bit) != 0) {
+ return true;
+ } else {
+ bits_[element_index] = original | ith_bit;
+ return false;
+ }
+ }
+
+ // Sets the |i|th bit to 0. Return the |i|th bit before it was cleared.
+ bool Clear(uint32_t i) {
+ uint32_t element_index = i / kBitContainerSize;
+ uint32_t bit_in_element = i % kBitContainerSize;
+
+ if (element_index >= bits_.size()) {
+ return false;
+ }
+
+ BitContainer original = bits_[element_index];
+ BitContainer ith_bit = static_cast<BitContainer>(1) << bit_in_element;
+
+ if ((original & ith_bit) == 0) {
+ return false;
+ } else {
+ bits_[element_index] = original & (~ith_bit);
+ return true;
+ }
+ }
+
+ // Returns the |i|th bit.
+ bool Get(uint32_t i) const {
+ uint32_t element_index = i / kBitContainerSize;
+ uint32_t bit_in_element = i % kBitContainerSize;
+
+ if (element_index >= bits_.size()) {
+ return false;
+ }
+
+ return (bits_[element_index] &
+ (static_cast<BitContainer>(1) << bit_in_element)) != 0;
+ }
+
+ // Print a report on the densicy of the bit vector, number of 1 bits, number
+ // of bytes, and average bytes for 1 bit, to |out|.
+ void ReportDensity(std::ostream& out);
+
+ private:
+ std::vector<BitContainer> bits_;
+};
+
+} // namespace utils
+} // namespace spvtools
+
+#endif // LIBSPIRV_UTILS_BIT_VECTOR_H_
diff --git a/test/util/CMakeLists.txt b/test/util/CMakeLists.txt
index 9b6ca2c..d3bbc18 100644
--- a/test/util/CMakeLists.txt
+++ b/test/util/CMakeLists.txt
@@ -14,5 +14,8 @@
add_spvtools_unittest(TARGET util_intrusive_list
SRCS ilist_test.cpp
- LIBS SPIRV-Tools-opt
+)
+
+add_spvtools_unittest(TARGET bit_vector
+ SRCS bit_vector_test.cpp
)
diff --git a/test/util/bit_vector_test.cpp b/test/util/bit_vector_test.cpp
new file mode 100644
index 0000000..12528fe
--- /dev/null
+++ b/test/util/bit_vector_test.cpp
@@ -0,0 +1,112 @@
+// Copyright (c) 2017 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include <vector>
+
+#include "gmock/gmock.h"
+
+#include "util/bit_vector.h"
+
+namespace {
+
+using spvtools::utils::BitVector;
+using BitVectorTest = ::testing::Test;
+
+TEST(BitVectorTest, Initialize) {
+ BitVector bvec;
+
+ // Checks that all values are 0. Also tests checking a bit past the end of
+ // the vector containing the bits.
+ for (int i = 1; i < 10000; i *= 2) {
+ EXPECT_FALSE(bvec.Get(i));
+ }
+}
+
+TEST(BitVectorTest, Set) {
+ BitVector bvec;
+
+ // Since 10,000 is larger than the initial size, this tests the resizing
+ // code.
+ for (int i = 3; i < 10000; i *= 2) {
+ bvec.Set(i);
+ }
+
+ // Check that bits that were not set are 0.
+ for (int i = 1; i < 10000; i *= 2) {
+ EXPECT_FALSE(bvec.Get(i));
+ }
+
+ // Check that bits that were set are 1.
+ for (int i = 3; i < 10000; i *= 2) {
+ EXPECT_TRUE(bvec.Get(i));
+ }
+}
+
+TEST(BitVectorTest, SetReturnValue) {
+ BitVector bvec;
+
+ // Make sure |Set| returns false when the bit was not set.
+ for (int i = 3; i < 10000; i *= 2) {
+ EXPECT_FALSE(bvec.Set(i));
+ }
+
+ // Make sure |Set| returns true when the bit was already set.
+ for (int i = 3; i < 10000; i *= 2) {
+ EXPECT_TRUE(bvec.Set(i));
+ }
+}
+
+TEST(BitVectorTest, Clear) {
+ BitVector bvec;
+ for (int i = 3; i < 10000; i *= 2) {
+ bvec.Set(i);
+ }
+
+ // Check that the bits were properly set.
+ for (int i = 3; i < 10000; i *= 2) {
+ EXPECT_TRUE(bvec.Get(i));
+ }
+
+ // Clear all of the bits except for bit 3.
+ for (int i = 6; i < 10000; i *= 2) {
+ bvec.Clear(i);
+ }
+
+ // Make sure bit 3 was not cleared.
+ EXPECT_TRUE(bvec.Get(3));
+
+ // Make sure all of the other bits that were set have been cleared.
+ for (int i = 6; i < 10000; i *= 2) {
+ EXPECT_FALSE(bvec.Get(i));
+ }
+}
+
+TEST(BitVectorTest, ClearReturnValue) {
+ BitVector bvec;
+ for (int i = 3; i < 10000; i *= 2) {
+ bvec.Set(i);
+ }
+
+ // Make sure |Clear| returns true if the bit was set.
+ for (int i = 3; i < 10000; i *= 2) {
+ EXPECT_TRUE(bvec.Clear(i));
+ }
+
+ // Make sure |Clear| returns false if the bit was not set.
+ for (int i = 3; i < 10000; i *= 2) {
+ EXPECT_FALSE(bvec.Clear(i));
+ }
+}
+
+} // namespace
