Stabilize the output of spirv-diff (#4698)
* Reimplement LCS used by spirv-diff
Two improvements are made to the LCS algorithm:
- The LCS algorithm is reimplemented to use a std::stack instead of
being recursive. This prevents stack overflow in the LCSTest.Large
test.
- The LCS algorithm uses an NxM table. Previously, entries of this
table were {size_t, bool, bool}, which is now packed in 32 bits. The
first entry can assume a maximum value of min(N, M), which
realistically for SPIR-V diff will not be larger than 1 billion
instructions. This reduces memory usage of LCS by 75%.
This partially reverts 845f3efb8a4eb32e5f484aa6ea9b9e3716d6f7ec and
enables LCS tests.
* Stabilize the output of spirv-diff
std::map is used instead of std::unordered_map to ensure the output of
spirv-diff is identical everywhere.
This partially reverts 845f3efb8a4eb32e5f484aa6ea9b9e3716d6f7ec and
enables spirv-diff tests.diff --git a/source/diff/diff.cpp b/source/diff/diff.cpp
index f44a9ba..13e1ffa 100644
--- a/source/diff/diff.cpp
+++ b/source/diff/diff.cpp
@@ -36,7 +36,7 @@
// A flat list of instructions in a function for easier iteration.
using InstructionList = std::vector<const opt::Instruction*>;
// A map from a function to its list of instructions.
-using FunctionInstMap = std::unordered_map<uint32_t, InstructionList>;
+using FunctionInstMap = std::map<uint32_t, InstructionList>;
// A list of ids with some similar property, for example functions with the same
// name.
using IdGroup = std::vector<uint32_t>;
@@ -1486,7 +1486,7 @@
LongestCommonSubsequence<std::vector<const opt::Instruction*>> lcs(src_body,
dst_body);
- size_t best_match_length = lcs.Get<const opt::Instruction*>(
+ uint32_t best_match_length = lcs.Get<const opt::Instruction*>(
[this](const opt::Instruction* src_inst,
const opt::Instruction* dst_inst) {
return DoInstructionsMatchFuzzy(src_inst, dst_inst);