Revert "Optimize DefUseManager allocations (#4709)" (#4846)
This reverts commit d18d0d92e55f44da6af0dc87fb0e3c8034e9a3ac.
This is reverted because it causes a 7X slowdown when legalizing
SPIR-V with NonSemantic.Shader.DebugInfo.100 instructions.
This is due to the creation of very large UseLists for several
heavily used operands for this extension combined with the fact
that the original commit changed the performance of Uselists to O(n).
diff --git a/BUILD.gn b/BUILD.gn
index 9f96c24..71a584f 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -466,7 +466,6 @@
"source/util/make_unique.h",
"source/util/parse_number.cpp",
"source/util/parse_number.h",
- "source/util/pooled_linked_list.h",
"source/util/small_vector.h",
"source/util/string_utils.cpp",
"source/util/string_utils.h",
diff --git a/source/CMakeLists.txt b/source/CMakeLists.txt
index 98559b8..c0974e1 100644
--- a/source/CMakeLists.txt
+++ b/source/CMakeLists.txt
@@ -228,7 +228,6 @@
${CMAKE_CURRENT_SOURCE_DIR}/util/hex_float.h
${CMAKE_CURRENT_SOURCE_DIR}/util/make_unique.h
${CMAKE_CURRENT_SOURCE_DIR}/util/parse_number.h
- ${CMAKE_CURRENT_SOURCE_DIR}/util/pooled_linked_list.h
${CMAKE_CURRENT_SOURCE_DIR}/util/small_vector.h
${CMAKE_CURRENT_SOURCE_DIR}/util/string_utils.h
${CMAKE_CURRENT_SOURCE_DIR}/util/timer.h
diff --git a/source/opt/def_use_manager.cpp b/source/opt/def_use_manager.cpp
index e1e441e..d54fdb6 100644
--- a/source/opt/def_use_manager.cpp
+++ b/source/opt/def_use_manager.cpp
@@ -13,23 +13,11 @@
// limitations under the License.
#include "source/opt/def_use_manager.h"
-#include "source/util/make_unique.h"
namespace spvtools {
namespace opt {
namespace analysis {
-// Don't compact before we have a reasonable number of ids allocated (~32kb).
-static const size_t kCompactThresholdMinTotalIds = (8 * 1024);
-// Compact when fewer than this fraction of the storage is used (should be 2^n
-// for performance).
-static const size_t kCompactThresholdFractionFreeIds = 8;
-
-DefUseManager::DefUseManager() {
- use_pool_ = MakeUnique<UseListPool>();
- used_id_pool_ = MakeUnique<UsedIdListPool>();
-}
-
void DefUseManager::AnalyzeInstDef(Instruction* inst) {
const uint32_t def_id = inst->result_id();
if (def_id != 0) {
@@ -46,15 +34,15 @@
}
void DefUseManager::AnalyzeInstUse(Instruction* inst) {
- // It might have existed before.
- EraseUseRecordsOfOperandIds(inst);
-
// Create entry for the given instruction. Note that the instruction may
// not have any in-operands. In such cases, we still need a entry for those
// instructions so this manager knows it has seen the instruction later.
- UsedIdList& used_ids =
- inst_to_used_id_.insert({inst, UsedIdList(used_id_pool_.get())})
- .first->second;
+ auto* used_ids = &inst_to_used_ids_[inst];
+ if (used_ids->size()) {
+ EraseUseRecordsOfOperandIds(inst);
+ used_ids = &inst_to_used_ids_[inst];
+ }
+ used_ids->clear(); // It might have existed before.
for (uint32_t i = 0; i < inst->NumOperands(); ++i) {
switch (inst->GetOperand(i).type) {
@@ -66,17 +54,8 @@
uint32_t use_id = inst->GetSingleWordOperand(i);
Instruction* def = GetDef(use_id);
assert(def && "Definition is not registered.");
-
- // Add to inst's use records
- used_ids.push_back(use_id);
-
- // Add to the users, taking care to avoid adding duplicates. We know
- // the duplicate for this instruction will always be at the tail.
- UseList& list = inst_to_users_.insert({def, UseList(use_pool_.get())})
- .first->second;
- if (list.empty() || list.back() != inst) {
- list.push_back(inst);
- }
+ id_to_users_.insert(UserEntry{def, inst});
+ used_ids->push_back(use_id);
} break;
default:
break;
@@ -115,6 +94,23 @@
return iter->second;
}
+DefUseManager::IdToUsersMap::const_iterator DefUseManager::UsersBegin(
+ const Instruction* def) const {
+ return id_to_users_.lower_bound(
+ UserEntry{const_cast<Instruction*>(def), nullptr});
+}
+
+bool DefUseManager::UsersNotEnd(const IdToUsersMap::const_iterator& iter,
+ const IdToUsersMap::const_iterator& cached_end,
+ const Instruction* inst) const {
+ return (iter != cached_end && iter->def == inst);
+}
+
+bool DefUseManager::UsersNotEnd(const IdToUsersMap::const_iterator& iter,
+ const Instruction* inst) const {
+ return UsersNotEnd(iter, id_to_users_.end(), inst);
+}
+
bool DefUseManager::WhileEachUser(
const Instruction* def, const std::function<bool(Instruction*)>& f) const {
// Ensure that |def| has been registered.
@@ -122,11 +118,9 @@
"Definition is not registered.");
if (!def->HasResultId()) return true;
- auto iter = inst_to_users_.find(def);
- if (iter != inst_to_users_.end()) {
- for (Instruction* user : iter->second) {
- if (!f(user)) return false;
- }
+ auto end = id_to_users_.end();
+ for (auto iter = UsersBegin(def); UsersNotEnd(iter, end, def); ++iter) {
+ if (!f(iter->user)) return false;
}
return true;
}
@@ -157,15 +151,14 @@
"Definition is not registered.");
if (!def->HasResultId()) return true;
- auto iter = inst_to_users_.find(def);
- if (iter != inst_to_users_.end()) {
- for (Instruction* user : iter->second) {
- for (uint32_t idx = 0; idx != user->NumOperands(); ++idx) {
- const Operand& op = user->GetOperand(idx);
- if (op.type != SPV_OPERAND_TYPE_RESULT_ID && spvIsIdType(op.type)) {
- if (def->result_id() == op.words[0]) {
- if (!f(user, idx)) return false;
- }
+ auto end = id_to_users_.end();
+ for (auto iter = UsersBegin(def); UsersNotEnd(iter, end, def); ++iter) {
+ Instruction* user = iter->user;
+ for (uint32_t idx = 0; idx != user->NumOperands(); ++idx) {
+ const Operand& op = user->GetOperand(idx);
+ if (op.type != SPV_OPERAND_TYPE_RESULT_ID && spvIsIdType(op.type)) {
+ if (def->result_id() == op.words[0]) {
+ if (!f(user, idx)) return false;
}
}
}
@@ -237,18 +230,17 @@
}
void DefUseManager::ClearInst(Instruction* inst) {
- if (inst_to_used_id_.find(inst) != inst_to_used_id_.end()) {
+ auto iter = inst_to_used_ids_.find(inst);
+ if (iter != inst_to_used_ids_.end()) {
EraseUseRecordsOfOperandIds(inst);
- uint32_t const result_id = inst->result_id();
- if (result_id != 0) {
- // For each using instruction, remove result_id from their used ids.
- auto iter = inst_to_users_.find(inst);
- if (iter != inst_to_users_.end()) {
- for (Instruction* use : iter->second) {
- inst_to_used_id_.at(use).remove_first(result_id);
- }
- inst_to_users_.erase(iter);
+ if (inst->result_id() != 0) {
+ // Remove all uses of this inst.
+ auto users_begin = UsersBegin(inst);
+ auto end = id_to_users_.end();
+ auto new_end = users_begin;
+ for (; UsersNotEnd(new_end, end, inst); ++new_end) {
}
+ id_to_users_.erase(users_begin, new_end);
id_to_def_.erase(inst->result_id());
}
}
@@ -257,48 +249,16 @@
void DefUseManager::EraseUseRecordsOfOperandIds(const Instruction* inst) {
// Go through all ids used by this instruction, remove this instruction's
// uses of them.
- auto iter = inst_to_used_id_.find(inst);
- if (iter != inst_to_used_id_.end()) {
- const UsedIdList& used_ids = iter->second;
- for (uint32_t def_id : used_ids) {
- auto def_iter = inst_to_users_.find(GetDef(def_id));
- if (def_iter != inst_to_users_.end()) {
- def_iter->second.remove_first(const_cast<Instruction*>(inst));
- }
+ auto iter = inst_to_used_ids_.find(inst);
+ if (iter != inst_to_used_ids_.end()) {
+ for (auto use_id : iter->second) {
+ id_to_users_.erase(
+ UserEntry{GetDef(use_id), const_cast<Instruction*>(inst)});
}
- inst_to_used_id_.erase(inst);
-
- // If we're using only a fraction of the space in used_ids_, compact storage
- // to prevent memory usage from being unbounded.
- if (used_id_pool_->total_nodes() > kCompactThresholdMinTotalIds &&
- used_id_pool_->used_nodes() <
- used_id_pool_->total_nodes() / kCompactThresholdFractionFreeIds) {
- CompactStorage();
- }
+ inst_to_used_ids_.erase(iter);
}
}
-void DefUseManager::CompactStorage() {
- CompactUseRecords();
- CompactUsedIds();
-}
-
-void DefUseManager::CompactUseRecords() {
- std::unique_ptr<UseListPool> new_pool = MakeUnique<UseListPool>();
- for (auto& iter : inst_to_users_) {
- iter.second.move_nodes(new_pool.get());
- }
- use_pool_ = std::move(new_pool);
-}
-
-void DefUseManager::CompactUsedIds() {
- std::unique_ptr<UsedIdListPool> new_pool = MakeUnique<UsedIdListPool>();
- for (auto& iter : inst_to_used_id_) {
- iter.second.move_nodes(new_pool.get());
- }
- used_id_pool_ = std::move(new_pool);
-}
-
bool CompareAndPrintDifferences(const DefUseManager& lhs,
const DefUseManager& rhs) {
bool same = true;
@@ -317,52 +277,34 @@
same = false;
}
- for (const auto& l : lhs.inst_to_used_id_) {
- std::set<uint32_t> ul, ur;
- lhs.ForEachUse(l.first,
- [&ul](Instruction*, uint32_t id) { ul.insert(id); });
- rhs.ForEachUse(l.first,
- [&ur](Instruction*, uint32_t id) { ur.insert(id); });
- if (ul.size() != ur.size()) {
- printf(
- "Diff in inst_to_used_id_: different number of used ids (%zu != %zu)",
- ul.size(), ur.size());
- same = false;
- } else if (ul != ur) {
- printf("Diff in inst_to_used_id_: different used ids\n");
- same = false;
+ if (lhs.id_to_users_ != rhs.id_to_users_) {
+ for (auto p : lhs.id_to_users_) {
+ if (rhs.id_to_users_.count(p) == 0) {
+ printf("Diff in id_to_users: missing value in rhs\n");
+ }
}
- }
- for (const auto& r : rhs.inst_to_used_id_) {
- auto iter_l = lhs.inst_to_used_id_.find(r.first);
- if (r.second.empty() &&
- !(iter_l == lhs.inst_to_used_id_.end() || iter_l->second.empty())) {
- printf("Diff in inst_to_used_id_: unexpected instr in rhs\n");
- same = false;
+ for (auto p : rhs.id_to_users_) {
+ if (lhs.id_to_users_.count(p) == 0) {
+ printf("Diff in id_to_users: missing value in lhs\n");
+ }
}
+ same = false;
}
- for (const auto& l : lhs.inst_to_users_) {
- std::set<Instruction*> ul, ur;
- lhs.ForEachUser(l.first, [&ul](Instruction* use) { ul.insert(use); });
- rhs.ForEachUser(l.first, [&ur](Instruction* use) { ur.insert(use); });
- if (ul.size() != ur.size()) {
- printf("Diff in inst_to_users_: different number of users (%zu != %zu)",
- ul.size(), ur.size());
- same = false;
- } else if (ul != ur) {
- printf("Diff in inst_to_users_: different users\n");
- same = false;
+ if (lhs.inst_to_used_ids_ != rhs.inst_to_used_ids_) {
+ for (auto p : lhs.inst_to_used_ids_) {
+ if (rhs.inst_to_used_ids_.count(p.first) == 0) {
+ printf("Diff in inst_to_used_ids: missing value in rhs\n");
+ }
}
- }
- for (const auto& r : rhs.inst_to_users_) {
- auto iter_l = lhs.inst_to_users_.find(r.first);
- if (r.second.empty() &&
- !(iter_l == lhs.inst_to_users_.end() || iter_l->second.empty())) {
- printf("Diff in inst_to_users_: unexpected instr in rhs\n");
- same = false;
+ for (auto p : rhs.inst_to_used_ids_) {
+ if (lhs.inst_to_used_ids_.count(p.first) == 0) {
+ printf("Diff in inst_to_used_ids: missing value in lhs\n");
+ }
}
+ same = false;
}
+
return same;
}
diff --git a/source/opt/def_use_manager.h b/source/opt/def_use_manager.h
index cf6cbdf..a8dbbc6 100644
--- a/source/opt/def_use_manager.h
+++ b/source/opt/def_use_manager.h
@@ -21,7 +21,6 @@
#include "source/opt/instruction.h"
#include "source/opt/module.h"
-#include "source/util/pooled_linked_list.h"
#include "spirv-tools/libspirv.hpp"
namespace spvtools {
@@ -50,6 +49,50 @@
return lhs.operand_index < rhs.operand_index;
}
+// Definition should never be null. User can be null, however, such an entry
+// should be used only for searching (e.g. all users of a particular definition)
+// and never stored in a container.
+struct UserEntry {
+ Instruction* def;
+ Instruction* user;
+};
+
+inline bool operator==(const UserEntry& lhs, const UserEntry& rhs) {
+ return lhs.def == rhs.def && lhs.user == rhs.user;
+}
+
+// Orders UserEntry for use in associative containers (i.e. less than ordering).
+//
+// The definition of an UserEntry is treated as the major key and the users as
+// the minor key so that all the users of a particular definition are
+// consecutive in a container.
+//
+// A null user always compares less than a real user. This is done to provide
+// easy values to search for the beginning of the users of a particular
+// definition (i.e. using {def, nullptr}).
+struct UserEntryLess {
+ bool operator()(const UserEntry& lhs, const UserEntry& rhs) const {
+ // If lhs.def and rhs.def are both null, fall through to checking the
+ // second entries.
+ if (!lhs.def && rhs.def) return true;
+ if (lhs.def && !rhs.def) return false;
+
+ // If neither definition is null, then compare unique ids.
+ if (lhs.def && rhs.def) {
+ if (lhs.def->unique_id() < rhs.def->unique_id()) return true;
+ if (rhs.def->unique_id() < lhs.def->unique_id()) return false;
+ }
+
+ // Return false on equality.
+ if (!lhs.user && !rhs.user) return false;
+ if (!lhs.user) return true;
+ if (!rhs.user) return false;
+
+ // If neither user is null then compare unique ids.
+ return lhs.user->unique_id() < rhs.user->unique_id();
+ }
+};
+
// A class for analyzing and managing defs and uses in an Module.
class DefUseManager {
public:
@@ -59,7 +102,7 @@
// will be communicated to the outside via the given message |consumer|. This
// instance only keeps a reference to the |consumer|, so the |consumer| should
// outlive this instance.
- DefUseManager(Module* module) : DefUseManager() { AnalyzeDefUse(module); }
+ DefUseManager(Module* module) { AnalyzeDefUse(module); }
DefUseManager(const DefUseManager&) = delete;
DefUseManager(DefUseManager&&) = delete;
@@ -171,36 +214,35 @@
// uses.
void UpdateDefUse(Instruction* inst);
- // Compacts any internal storage to save memory.
- void CompactStorage();
-
private:
- using UseList = spvtools::utils::PooledLinkedList<Instruction*>;
- using UseListPool = spvtools::utils::PooledLinkedListNodes<Instruction*>;
- // Stores linked lists of Instructions using a def.
- using InstToUsersMap = std::unordered_map<const Instruction*, UseList>;
+ using IdToUsersMap = std::set<UserEntry, UserEntryLess>;
+ using InstToUsedIdsMap =
+ std::unordered_map<const Instruction*, std::vector<uint32_t>>;
- using UsedIdList = spvtools::utils::PooledLinkedList<uint32_t>;
- using UsedIdListPool = spvtools::utils::PooledLinkedListNodes<uint32_t>;
- // Stores mapping from instruction to their UsedIdRange.
- using InstToUsedIdMap = std::unordered_map<const Instruction*, UsedIdList>;
+ // Returns the first location that {|def|, nullptr} could be inserted into the
+ // users map without violating ordering.
+ IdToUsersMap::const_iterator UsersBegin(const Instruction* def) const;
- DefUseManager();
+ // Returns true if |iter| has not reached the end of |def|'s users.
+ //
+ // In the first version |iter| is compared against the end of the map for
+ // validity before other checks. In the second version, |iter| is compared
+ // against |cached_end| for validity before other checks. This allows caching
+ // the map's end which is a performance improvement on some platforms.
+ bool UsersNotEnd(const IdToUsersMap::const_iterator& iter,
+ const Instruction* def) const;
+ bool UsersNotEnd(const IdToUsersMap::const_iterator& iter,
+ const IdToUsersMap::const_iterator& cached_end,
+ const Instruction* def) const;
// Analyzes the defs and uses in the given |module| and populates data
// structures in this class. Does nothing if |module| is nullptr.
void AnalyzeDefUse(Module* module);
- // Removes unused entries in used_records_ and used_ids_.
- void CompactUseRecords();
- void CompactUsedIds();
-
- IdToDefMap id_to_def_; // Mapping from ids to their definitions
- InstToUsersMap inst_to_users_; // Map from def to uses.
- std::unique_ptr<UseListPool> use_pool_;
-
- std::unique_ptr<UsedIdListPool> used_id_pool_;
- InstToUsedIdMap inst_to_used_id_; // Map from instruction to used ids.
+ IdToDefMap id_to_def_; // Mapping from ids to their definitions
+ IdToUsersMap id_to_users_; // Mapping from ids to their users
+ // Mapping from instructions to the ids used in the instruction.
+ InstToUsedIdsMap inst_to_used_ids_;
};
} // namespace analysis
diff --git a/source/util/pooled_linked_list.h b/source/util/pooled_linked_list.h
deleted file mode 100644
index faaa4c4..0000000
--- a/source/util/pooled_linked_list.h
+++ /dev/null
@@ -1,236 +0,0 @@
-// Copyright (c) 2021 The Khronos Group 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.
-
-#ifndef SOURCE_UTIL_POOLED_LINKED_LIST_H_
-#define SOURCE_UTIL_POOLED_LINKED_LIST_H_
-
-#include <cstdint>
-#include <vector>
-
-namespace spvtools {
-namespace utils {
-
-// Shared storage of nodes for PooledLinkedList.
-template <typename T>
-class PooledLinkedListNodes {
- public:
- struct Node {
- Node(T e, int32_t n = -1) : element(e), next(n) {}
-
- T element = {};
- int32_t next = -1;
- };
-
- PooledLinkedListNodes() = default;
- PooledLinkedListNodes(const PooledLinkedListNodes&) = delete;
- PooledLinkedListNodes& operator=(const PooledLinkedListNodes&) = delete;
-
- PooledLinkedListNodes(PooledLinkedListNodes&& that) {
- *this = std::move(that);
- }
-
- PooledLinkedListNodes& operator=(PooledLinkedListNodes&& that) {
- vec_ = std::move(that.vec_);
- free_nodes_ = that.free_nodes_;
- return *this;
- }
-
- size_t total_nodes() { return vec_.size(); }
- size_t free_nodes() { return free_nodes_; }
- size_t used_nodes() { return total_nodes() - free_nodes(); }
-
- private:
- template <typename ListT>
- friend class PooledLinkedList;
-
- Node& at(int32_t index) { return vec_[index]; }
- const Node& at(int32_t index) const { return vec_[index]; }
-
- int32_t insert(T element) {
- int32_t index = int32_t(vec_.size());
- vec_.emplace_back(element);
- return index;
- }
-
- std::vector<Node> vec_;
- size_t free_nodes_ = 0;
-};
-
-// Implements a linked-list where list nodes come from a shared pool. This is
-// meant to be used in scenarios where it is desirable to avoid many small
-// allocations.
-//
-// Instead of pointers, the list uses indices to allow the underlying storage
-// to be modified without needing to modify the list. When removing elements
-// from the list, nodes are not deleted or recycled: to reclaim unused space,
-// perform a sequence of |move_nodes| operations into a temporary pool, which
-// then is moved into the old pool.
-//
-// This does *not* attempt to implement a full stl-compatible interface.
-template <typename T>
-class PooledLinkedList {
- public:
- using NodePool = PooledLinkedListNodes<T>;
- using Node = typename NodePool::Node;
-
- PooledLinkedList() = delete;
- PooledLinkedList(NodePool* nodes) : nodes_(nodes) {}
-
- // Shared iterator implementation (for iterator and const_iterator).
- template <typename ElementT, typename PoolT>
- class iterator_base {
- public:
- iterator_base(const iterator_base& i)
- : nodes_(i.nodes_), index_(i.index_) {}
-
- iterator_base& operator++() {
- index_ = nodes_->at(index_).next;
- return *this;
- }
-
- iterator_base& operator=(const iterator_base& i) {
- nodes_ = i.nodes_;
- index_ = i.index_;
- return *this;
- }
-
- ElementT& operator*() const { return nodes_->at(index_).element; }
- ElementT* operator->() const { return &nodes_->at(index_).element; }
-
- friend inline bool operator==(const iterator_base& lhs,
- const iterator_base& rhs) {
- return lhs.nodes_ == rhs.nodes_ && lhs.index_ == rhs.index_;
- }
- friend inline bool operator!=(const iterator_base& lhs,
- const iterator_base& rhs) {
- return lhs.nodes_ != rhs.nodes_ || lhs.index_ != rhs.index_;
- }
-
- // Define standard iterator types needs so this class can be
- // used with <algorithms>.
- using iterator_category = std::forward_iterator_tag;
- using difference_type = std::ptrdiff_t;
- using value_type = ElementT;
- using pointer = ElementT*;
- using const_pointer = const ElementT*;
- using reference = ElementT&;
- using const_reference = const ElementT&;
- using size_type = size_t;
-
- private:
- friend PooledLinkedList;
-
- iterator_base(PoolT* pool, int32_t index) : nodes_(pool), index_(index) {}
-
- PoolT* nodes_;
- int32_t index_ = -1;
- };
-
- using iterator = iterator_base<T, std::vector<Node>>;
- using const_iterator = iterator_base<const T, const std::vector<Node>>;
-
- bool empty() const { return head_ == -1; }
-
- T& front() { return nodes_->at(head_).element; }
- T& back() { return nodes_->at(tail_).element; }
- const T& front() const { return nodes_->at(head_).element; }
- const T& back() const { return nodes_->at(tail_).element; }
-
- iterator begin() { return iterator(&nodes_->vec_, head_); }
- iterator end() { return iterator(&nodes_->vec_, -1); }
- const_iterator begin() const { return const_iterator(&nodes_->vec_, head_); }
- const_iterator end() const { return const_iterator(&nodes_->vec_, -1); }
-
- // Inserts |element| at the back of the list.
- void push_back(T element) {
- int32_t new_tail = nodes_->insert(element);
- if (head_ == -1) {
- head_ = new_tail;
- tail_ = new_tail;
- } else {
- nodes_->at(tail_).next = new_tail;
- tail_ = new_tail;
- }
- }
-
- // Removes the first occurrence of |element| from the list.
- // Returns if |element| was removed.
- bool remove_first(T element) {
- int32_t* prev_next = &head_;
- for (int32_t prev_index = -1, index = head_; index != -1; /**/) {
- auto& node = nodes_->at(index);
- if (node.element == element) {
- // Snip from of the list, optionally fixing up tail pointer.
- if (tail_ == index) {
- assert(node.next == -1);
- tail_ = prev_index;
- }
- *prev_next = node.next;
- nodes_->free_nodes_++;
- return true;
- } else {
- prev_next = &node.next;
- }
- prev_index = index;
- index = node.next;
- }
- return false;
- }
-
- // Returns the PooledLinkedListNodes that owns this list's nodes.
- NodePool* pool() { return nodes_; }
-
- // Moves the nodes in this list into |new_pool|, providing a way to compact
- // storage and reclaim unused space.
- //
- // Upon completing a sequence of |move_nodes| calls, you must ensure you
- // retain ownership of the new storage your lists point to. Example usage:
- //
- // unique_ptr<NodePool> new_pool = ...;
- // for (PooledLinkedList& list : lists) {
- // list.move_to(new_pool);
- // }
- // my_pool_ = std::move(new_pool);
- void move_nodes(NodePool* new_pool) {
- // Be sure to construct the list in the same order, instead of simply
- // doing a sequence of push_backs.
- int32_t prev_entry = -1;
- int32_t nodes_freed = 0;
- for (int32_t index = head_; index != -1; nodes_freed++) {
- const auto& node = nodes_->at(index);
- int32_t this_entry = new_pool->insert(node.element);
- index = node.next;
- if (prev_entry == -1) {
- head_ = this_entry;
- } else {
- new_pool->at(prev_entry).next = this_entry;
- }
- prev_entry = this_entry;
- }
- tail_ = prev_entry;
- // Update our old pool's free count, now we're a member of the new pool.
- nodes_->free_nodes_ += nodes_freed;
- nodes_ = new_pool;
- }
-
- private:
- NodePool* nodes_;
- int32_t head_ = -1;
- int32_t tail_ = -1;
-};
-
-} // namespace utils
-} // namespace spvtools
-
-#endif // SOURCE_UTIL_POOLED_LINKED_LIST_H_
\ No newline at end of file
diff --git a/test/opt/def_use_test.cpp b/test/opt/def_use_test.cpp
index 48a485e..0210095 100644
--- a/test/opt/def_use_test.cpp
+++ b/test/opt/def_use_test.cpp
@@ -950,369 +950,6 @@
);
// clang-format on
-// We re-use the same replace usecases, we need to similarly exercise the
-// DefUseManager by replacing instructions and uses.
-using CompactIdempotence = ::testing::TestWithParam<ReplaceUseCase>;
-
-TEST_P(CompactIdempotence, Case) {
- const auto& tc = GetParam();
-
- // Build module.
- const std::vector<const char*> text = {tc.before};
- std::unique_ptr<IRContext> context =
- BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, JoinAllInsts(text),
- SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
- ASSERT_NE(nullptr, context);
-
- // Force a re-build of def-use manager.
- context->InvalidateAnalyses(IRContext::Analysis::kAnalysisDefUse);
- (void)context->get_def_use_mgr();
-
- // Do the substitution.
- for (const auto& candidate : tc.candidates) {
- context->ReplaceAllUsesWith(candidate.first, candidate.second);
- }
-
- // Ensure new/uncompacted managers produce the same result
- EXPECT_TRUE(CompareAndPrintDifferences(*context->get_def_use_mgr(),
- DefUseManager(context->module())));
-
- EXPECT_EQ(tc.after, DisassembleModule(context->module()));
- CheckDef(tc.du, context->get_def_use_mgr()->id_to_defs());
- CheckUse(tc.du, context->get_def_use_mgr(), context->module()->IdBound());
-
- // Compare again after compacting the defuse manager's storage
- context->get_def_use_mgr()->CompactStorage();
-
- CheckDef(tc.du, context->get_def_use_mgr()->id_to_defs());
- CheckUse(tc.du, context->get_def_use_mgr(), context->module()->IdBound());
-
- EXPECT_TRUE(CompareAndPrintDifferences(*context->get_def_use_mgr(),
- DefUseManager(context->module())));
-}
-
-// clang-format off
-INSTANTIATE_TEST_SUITE_P(
- TestCase, CompactIdempotence,
- ::testing::ValuesIn(std::vector<ReplaceUseCase>{
- { // no use, no replace request
- "", {}, "", {},
- },
- { // replace one use
- "%1 = OpTypeBool "
- "%2 = OpTypeVector %1 3 "
- "%3 = OpTypeInt 32 0 ",
- {{1, 3}},
- "%1 = OpTypeBool\n"
- "%2 = OpTypeVector %3 3\n"
- "%3 = OpTypeInt 32 0",
- {
- { // defs
- {1, "%1 = OpTypeBool"},
- {2, "%2 = OpTypeVector %3 3"},
- {3, "%3 = OpTypeInt 32 0"},
- },
- { // uses
- {3, {"%2 = OpTypeVector %3 3"}},
- },
- },
- },
- { // replace and then replace back
- "%1 = OpTypeBool "
- "%2 = OpTypeVector %1 3 "
- "%3 = OpTypeInt 32 0",
- {{1, 3}, {3, 1}},
- "%1 = OpTypeBool\n"
- "%2 = OpTypeVector %1 3\n"
- "%3 = OpTypeInt 32 0",
- {
- { // defs
- {1, "%1 = OpTypeBool"},
- {2, "%2 = OpTypeVector %1 3"},
- {3, "%3 = OpTypeInt 32 0"},
- },
- { // uses
- {1, {"%2 = OpTypeVector %1 3"}},
- },
- },
- },
- { // replace with the same id
- "%1 = OpTypeBool "
- "%2 = OpTypeVector %1 3",
- {{1, 1}, {2, 2}, {3, 3}},
- "%1 = OpTypeBool\n"
- "%2 = OpTypeVector %1 3",
- {
- { // defs
- {1, "%1 = OpTypeBool"},
- {2, "%2 = OpTypeVector %1 3"},
- },
- { // uses
- {1, {"%2 = OpTypeVector %1 3"}},
- },
- },
- },
- { // replace in sequence
- "%1 = OpTypeBool "
- "%2 = OpTypeVector %1 3 "
- "%3 = OpTypeInt 32 0 "
- "%4 = OpTypeInt 32 1 ",
- {{1, 3}, {3, 4}},
- "%1 = OpTypeBool\n"
- "%2 = OpTypeVector %4 3\n"
- "%3 = OpTypeInt 32 0\n"
- "%4 = OpTypeInt 32 1",
- {
- { // defs
- {1, "%1 = OpTypeBool"},
- {2, "%2 = OpTypeVector %4 3"},
- {3, "%3 = OpTypeInt 32 0"},
- {4, "%4 = OpTypeInt 32 1"},
- },
- { // uses
- {4, {"%2 = OpTypeVector %4 3"}},
- },
- },
- },
- { // replace multiple uses
- "%1 = OpTypeBool "
- "%2 = OpTypeVector %1 2 "
- "%3 = OpTypeVector %1 3 "
- "%4 = OpTypeVector %1 4 "
- "%5 = OpTypeMatrix %2 2 "
- "%6 = OpTypeMatrix %3 3 "
- "%7 = OpTypeMatrix %4 4 "
- "%8 = OpTypeInt 32 0 "
- "%9 = OpTypeInt 32 1 "
- "%10 = OpTypeInt 64 0",
- {{1, 8}, {2, 9}, {4, 10}},
- "%1 = OpTypeBool\n"
- "%2 = OpTypeVector %8 2\n"
- "%3 = OpTypeVector %8 3\n"
- "%4 = OpTypeVector %8 4\n"
- "%5 = OpTypeMatrix %9 2\n"
- "%6 = OpTypeMatrix %3 3\n"
- "%7 = OpTypeMatrix %10 4\n"
- "%8 = OpTypeInt 32 0\n"
- "%9 = OpTypeInt 32 1\n"
- "%10 = OpTypeInt 64 0",
- {
- { // defs
- {1, "%1 = OpTypeBool"},
- {2, "%2 = OpTypeVector %8 2"},
- {3, "%3 = OpTypeVector %8 3"},
- {4, "%4 = OpTypeVector %8 4"},
- {5, "%5 = OpTypeMatrix %9 2"},
- {6, "%6 = OpTypeMatrix %3 3"},
- {7, "%7 = OpTypeMatrix %10 4"},
- {8, "%8 = OpTypeInt 32 0"},
- {9, "%9 = OpTypeInt 32 1"},
- {10, "%10 = OpTypeInt 64 0"},
- },
- { // uses
- {8,
- {
- "%2 = OpTypeVector %8 2",
- "%3 = OpTypeVector %8 3",
- "%4 = OpTypeVector %8 4",
- }
- },
- {9, {"%5 = OpTypeMatrix %9 2"}},
- {3, {"%6 = OpTypeMatrix %3 3"}},
- {10, {"%7 = OpTypeMatrix %10 4"}},
- },
- },
- },
- { // OpPhi.
- kOpPhiTestFunction,
- // replace one id used by OpPhi, replace one id generated by OpPhi
- {{9, 13}, {11, 9}},
- "%1 = OpTypeVoid\n"
- "%6 = OpTypeInt 32 0\n"
- "%10 = OpTypeFloat 32\n"
- "%16 = OpTypeBool\n"
- "%3 = OpTypeFunction %1\n"
- "%8 = OpConstant %6 0\n"
- "%18 = OpConstant %6 1\n"
- "%12 = OpConstant %10 1\n"
- "%2 = OpFunction %1 None %3\n"
- "%4 = OpLabel\n"
- "OpBranch %5\n"
-
- "%5 = OpLabel\n"
- "%7 = OpPhi %6 %8 %4 %13 %5\n" // %9 -> %13
- "%11 = OpPhi %10 %12 %4 %13 %5\n"
- "%9 = OpIAdd %6 %7 %8\n"
- "%13 = OpFAdd %10 %9 %12\n" // %11 -> %9
- "%17 = OpSLessThan %16 %7 %18\n"
- "OpLoopMerge %19 %5 None\n"
- "OpBranchConditional %17 %5 %19\n"
-
- "%19 = OpLabel\n"
- "OpReturn\n"
- "OpFunctionEnd",
- {
- { // defs.
- {1, "%1 = OpTypeVoid"},
- {2, "%2 = OpFunction %1 None %3"},
- {3, "%3 = OpTypeFunction %1"},
- {4, "%4 = OpLabel"},
- {5, "%5 = OpLabel"},
- {6, "%6 = OpTypeInt 32 0"},
- {7, "%7 = OpPhi %6 %8 %4 %13 %5"},
- {8, "%8 = OpConstant %6 0"},
- {9, "%9 = OpIAdd %6 %7 %8"},
- {10, "%10 = OpTypeFloat 32"},
- {11, "%11 = OpPhi %10 %12 %4 %13 %5"},
- {12, "%12 = OpConstant %10 1.0"},
- {13, "%13 = OpFAdd %10 %9 %12"},
- {16, "%16 = OpTypeBool"},
- {17, "%17 = OpSLessThan %16 %7 %18"},
- {18, "%18 = OpConstant %6 1"},
- {19, "%19 = OpLabel"},
- },
- { // uses
- {1,
- {
- "%2 = OpFunction %1 None %3",
- "%3 = OpTypeFunction %1",
- }
- },
- {3, {"%2 = OpFunction %1 None %3"}},
- {4,
- {
- "%7 = OpPhi %6 %8 %4 %13 %5",
- "%11 = OpPhi %10 %12 %4 %13 %5",
- }
- },
- {5,
- {
- "OpBranch %5",
- "%7 = OpPhi %6 %8 %4 %13 %5",
- "%11 = OpPhi %10 %12 %4 %13 %5",
- "OpLoopMerge %19 %5 None",
- "OpBranchConditional %17 %5 %19",
- }
- },
- {6,
- {
- // Can't properly check constants
- // "%8 = OpConstant %6 0",
- // "%18 = OpConstant %6 1",
- "%7 = OpPhi %6 %8 %4 %13 %5",
- "%9 = OpIAdd %6 %7 %8"
- }
- },
- {7,
- {
- "%9 = OpIAdd %6 %7 %8",
- "%17 = OpSLessThan %16 %7 %18",
- }
- },
- {8,
- {
- "%7 = OpPhi %6 %8 %4 %13 %5",
- "%9 = OpIAdd %6 %7 %8",
- }
- },
- {9, {"%13 = OpFAdd %10 %9 %12"}}, // uses of %9 changed from %7 to %13
- {10,
- {
- "%11 = OpPhi %10 %12 %4 %13 %5",
- // "%12 = OpConstant %10 1",
- "%13 = OpFAdd %10 %9 %12"
- }
- },
- // no more uses of %11
- {12,
- {
- "%11 = OpPhi %10 %12 %4 %13 %5",
- "%13 = OpFAdd %10 %9 %12"
- }
- },
- {13, {
- "%7 = OpPhi %6 %8 %4 %13 %5",
- "%11 = OpPhi %10 %12 %4 %13 %5",
- }
- },
- {16, {"%17 = OpSLessThan %16 %7 %18"}},
- {17, {"OpBranchConditional %17 %5 %19"}},
- {18, {"%17 = OpSLessThan %16 %7 %18"}},
- {19,
- {
- "OpLoopMerge %19 %5 None",
- "OpBranchConditional %17 %5 %19",
- }
- },
- },
- },
- },
- { // OpPhi defining and referencing the same id.
- "%1 = OpTypeBool "
- "%3 = OpTypeFunction %1 "
- "%2 = OpConstantTrue %1 "
-
- "%4 = OpFunction %3 None %1 "
- "%6 = OpLabel "
- " OpBranch %7 "
- "%7 = OpLabel "
- "%8 = OpPhi %1 %8 %7 %2 %6 " // both defines and uses %8
- " OpBranch %7 "
- " OpFunctionEnd",
- {{8, 2}},
- "%1 = OpTypeBool\n"
- "%3 = OpTypeFunction %1\n"
- "%2 = OpConstantTrue %1\n"
-
- "%4 = OpFunction %3 None %1\n"
- "%6 = OpLabel\n"
- "OpBranch %7\n"
- "%7 = OpLabel\n"
- "%8 = OpPhi %1 %2 %7 %2 %6\n" // use of %8 changed to %2
- "OpBranch %7\n"
- "OpFunctionEnd",
- {
- { // defs
- {1, "%1 = OpTypeBool"},
- {2, "%2 = OpConstantTrue %1"},
- {3, "%3 = OpTypeFunction %1"},
- {4, "%4 = OpFunction %3 None %1"},
- {6, "%6 = OpLabel"},
- {7, "%7 = OpLabel"},
- {8, "%8 = OpPhi %1 %2 %7 %2 %6"},
- },
- { // uses
- {1,
- {
- "%2 = OpConstantTrue %1",
- "%3 = OpTypeFunction %1",
- "%4 = OpFunction %3 None %1",
- "%8 = OpPhi %1 %2 %7 %2 %6",
- }
- },
- {2,
- {
- // Only checking users
- "%8 = OpPhi %1 %2 %7 %2 %6",
- }
- },
- {3, {"%4 = OpFunction %3 None %1"}},
- {6, {"%8 = OpPhi %1 %2 %7 %2 %6"}},
- {7,
- {
- "OpBranch %7",
- "%8 = OpPhi %1 %2 %7 %2 %6",
- "OpBranch %7",
- }
- },
- // {8, {"%8 = OpPhi %1 %8 %7 %2 %6"}},
- },
- },
- },
- })
-);
-// clang-format on
-
struct KillDefCase {
const char* before;
std::vector<uint32_t> ids_to_kill;
diff --git a/test/util/CMakeLists.txt b/test/util/CMakeLists.txt
index 6808783..20038f7 100644
--- a/test/util/CMakeLists.txt
+++ b/test/util/CMakeLists.txt
@@ -17,7 +17,6 @@
bit_vector_test.cpp
bitutils_test.cpp
hash_combine_test.cpp
- pooled_linked_list_test.cpp
small_vector_test.cpp
LIBS SPIRV-Tools-opt
)
diff --git a/test/util/pooled_linked_list_test.cpp b/test/util/pooled_linked_list_test.cpp
deleted file mode 100644
index 82fb4ac..0000000
--- a/test/util/pooled_linked_list_test.cpp
+++ /dev/null
@@ -1,185 +0,0 @@
-// Copyright (c) 2021 The Khronos Group 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 <algorithm>
-#include <list>
-#include <utility>
-#include <vector>
-
-#include "gmock/gmock.h"
-#include "source/util/pooled_linked_list.h"
-
-namespace spvtools {
-namespace utils {
-namespace {
-
-using PooledLinkedListTest = ::testing::Test;
-
-template <typename T>
-static std::vector<T> ToVector(const PooledLinkedList<T>& list) {
- std::vector<T> vec;
- for (auto it = list.begin(); it != list.end(); ++it) {
- vec.push_back(*it);
- }
- return vec;
-}
-
-template <typename T>
-static void AppendVector(PooledLinkedList<T>& list, const std::vector<T>& vec) {
- for (const T& t : vec) {
- list.push_back(t);
- }
-}
-
-TEST(PooledLinkedListTest, Empty) {
- PooledLinkedListNodes<uint32_t> pool;
- PooledLinkedList<uint32_t> ll(&pool);
- EXPECT_TRUE(ll.empty());
-
- ll.push_back(1u);
- EXPECT_TRUE(!ll.empty());
-}
-
-TEST(PooledLinkedListTest, Iterator) {
- PooledLinkedListNodes<uint32_t> pool;
- PooledLinkedList<uint32_t> ll(&pool);
-
- EXPECT_EQ(ll.begin(), ll.end());
-
- ll.push_back(1);
- EXPECT_NE(ll.begin(), ll.end());
-
- auto it = ll.begin();
- EXPECT_EQ(*it, 1);
- ++it;
- EXPECT_EQ(it, ll.end());
-}
-
-TEST(PooledLinkedListTest, Iterator_algorithms) {
- PooledLinkedListNodes<uint32_t> pool;
- PooledLinkedList<uint32_t> ll(&pool);
-
- AppendVector(ll, {3, 2, 0, 1});
- EXPECT_EQ(std::distance(ll.begin(), ll.end()), 4);
- EXPECT_EQ(*std::min_element(ll.begin(), ll.end()), 0);
- EXPECT_EQ(*std::max_element(ll.begin(), ll.end()), 3);
-}
-
-TEST(PooledLinkedListTest, FrontBack) {
- PooledLinkedListNodes<uint32_t> pool;
- PooledLinkedList<uint32_t> ll(&pool);
-
- ll.push_back(1);
- EXPECT_EQ(ll.front(), 1);
- EXPECT_EQ(ll.back(), 1);
-
- ll.push_back(2);
- EXPECT_EQ(ll.front(), 1);
- EXPECT_EQ(ll.back(), 2);
-}
-
-TEST(PooledLinkedListTest, PushBack) {
- const std::vector<uint32_t> vec = {1, 2, 3, 4, 5, 6};
-
- PooledLinkedListNodes<uint32_t> pool;
- PooledLinkedList<uint32_t> ll(&pool);
-
- AppendVector(ll, vec);
- EXPECT_EQ(vec, ToVector(ll));
-}
-
-TEST(PooledLinkedListTest, RemoveFirst) {
- const std::vector<uint32_t> vec = {1, 2, 3, 4, 5, 6};
-
- PooledLinkedListNodes<uint32_t> pool;
- PooledLinkedList<uint32_t> ll(&pool);
-
- EXPECT_FALSE(ll.remove_first(0));
- AppendVector(ll, vec);
- EXPECT_FALSE(ll.remove_first(0));
-
- std::vector<uint32_t> tmp = vec;
- while (!tmp.empty()) {
- size_t mid = tmp.size() / 2;
- uint32_t elt = tmp[mid];
- tmp.erase(tmp.begin() + mid);
-
- EXPECT_TRUE(ll.remove_first(elt));
- EXPECT_FALSE(ll.remove_first(elt));
- EXPECT_EQ(tmp, ToVector(ll));
- }
- EXPECT_TRUE(ll.empty());
-}
-
-TEST(PooledLinkedListTest, RemoveFirst_Duplicates) {
- const std::vector<uint32_t> vec = {3, 1, 2, 3, 3, 3, 3, 4, 3, 5, 3, 6, 3};
-
- PooledLinkedListNodes<uint32_t> pool;
- PooledLinkedList<uint32_t> ll(&pool);
- AppendVector(ll, vec);
-
- std::vector<uint32_t> tmp = vec;
- while (!tmp.empty()) {
- size_t mid = tmp.size() / 2;
- uint32_t elt = tmp[mid];
- tmp.erase(std::find(tmp.begin(), tmp.end(), elt));
-
- EXPECT_TRUE(ll.remove_first(elt));
- EXPECT_EQ(tmp, ToVector(ll));
- }
- EXPECT_TRUE(ll.empty());
-}
-
-TEST(PooledLinkedList, MoveTo) {
- const std::vector<uint32_t> vec = {1, 2, 3, 4, 5, 6};
-
- PooledLinkedListNodes<uint32_t> pool;
- PooledLinkedList<uint32_t> ll1(&pool);
- PooledLinkedList<uint32_t> ll2(&pool);
- PooledLinkedList<uint32_t> ll3(&pool);
-
- AppendVector(ll1, vec);
- AppendVector(ll2, vec);
- AppendVector(ll3, vec);
- EXPECT_EQ(pool.total_nodes(), vec.size() * 3);
- EXPECT_EQ(pool.total_nodes(), vec.size() * 3);
- EXPECT_EQ(pool.free_nodes(), 0);
-
- // Move two lists to the new pool
- PooledLinkedListNodes<uint32_t> pool_new;
- ll1.move_nodes(&pool_new);
- ll2.move_nodes(&pool_new);
-
- // Moved nodes should belong to new pool
- EXPECT_EQ(ll1.pool(), &pool_new);
- EXPECT_EQ(ll2.pool(), &pool_new);
-
- // Old pool should be smaller & have free nodes.
- EXPECT_EQ(pool.used_nodes(), vec.size());
- EXPECT_EQ(pool.free_nodes(), vec.size() * 2);
-
- // New pool should be sized exactly and no free nodes.
- EXPECT_EQ(pool_new.total_nodes(), vec.size() * 2);
- EXPECT_EQ(pool_new.used_nodes(), vec.size() * 2);
- EXPECT_EQ(pool_new.free_nodes(), 0);
-
- // All lists should be preserved
- EXPECT_EQ(ToVector(ll1), vec);
- EXPECT_EQ(ToVector(ll2), vec);
- EXPECT_EQ(ToVector(ll3), vec);
-}
-
-} // namespace
-} // namespace utils
-} // namespace spvtools
