Repository: KhronosGroup/SPIRV-Tools (language: python)

Issue:
spirv-diff reports spurious differences in `OpFunctionParameter` instructions
`spirv-diff` seems to sometimes draw a distinction between `OpFunctionParameter` instructions that seem equivalent to me, resulting in spurious differences.

For example, given the two attached files, running

    $ spirv-diff before.spvasm after.spvasm

produces output that begins as follows:

```diff
                OpCapability Shader
           %1 = OpExtInstImport "GLSL.std.450"
                OpMemoryModel Logical GLSL450
                OpEntryPoint GLCompute %48 "main"
                OpExecutionMode %48 LocalSize 1 1 1
           %2 = OpTypeVoid
           %4 = OpTypeBool
           %3 = OpConstantTrue %4
           %7 = OpTypeFunction %2
          %14 = OpTypePointer Function %4
          %15 = OpConstantNull %4
          %17 = OpConstantNull %4
          %21 = OpTypeFunction %2 %4
          %32 = OpConstantNull %4
          %34 = OpConstantNull %4
           %6 = OpFunction %2 None %7
           %5 = OpLabel
                OpBranch %8
           %8 = OpLabel
                OpBranch %9
           %9 = OpLabel
                OpLoopMerge %10 %12 None
                OpBranch %11
          %11 = OpLabel
                OpBranch %12
          %12 = OpLabel
                OpBranchConditional %3 %10 %9
          %10 = OpLabel
                OpReturn
                OpFunctionEnd
          %20 = OpFunction %2 None %21
-         %19 = OpFunctionParameter %4
+         %50 = OpFunctionParameter %4
          %18 = OpLabel
          %13 = OpVariable %14 Function %15
          %16 = OpVariable %14 Function %17
                OpBranch %22
          %22 = OpLabel
                OpBranch %23
          %23 = OpLabel
                OpLoopMerge %24 %26 None
                OpBranch %25
          %25 = OpLabel
                OpBranch %26
          %26 = OpLabel
-               OpStore %13 %19
+               OpStore %13 %50
          %27 = OpLoad %4 %13
-         %28 = OpLogicalNotEqual %4 %19 %27
+         %28 = OpLogicalNotEqual %4 %50 %27
                OpStore %16 %28
          %29 = OpLoad %4 %16
-         %30 = OpLogicalEqual %4 %19 %29
+         %30 = OpLogicalEqual %4 %50 %29
                OpBranchConditional %30 %24 %23
          %24 = OpLabel
                OpReturn
                OpFunctionEnd
```

It seems to me that `%19` and `%50` are identical.

[spirv-diff-spurious.zip](https://github.com/KhronosGroup/SPIRV-Tools/files/11448227/spirv-diff-spurious.zip)



Discussion / hints:
Here's another case:

```diff
 ; SPIR-V
 ; Version: 1.6
 ; Generator: Khronos SPIR-V Tools Assembler; 0
 ; Bound: 109
 ; Schema: 0
                OpCapability Shader
           %1 = OpExtInstImport "GLSL.std.450"
                OpMemoryModel Logical GLSL450
                OpEntryPoint Fragment %36 "main_vec4vec3" %24 %26 %28 %30 %32 %34
-               OpEntryPoint Fragment %85 "main_vec2scalar" %73 %75 %77 %79 %81 %83
+               OpEntryPoint Fragment %85 "main_vec2scalar" %73 %75 %77 %79 %81 %83
                OpExecutionMode %36 OriginUpperLeft
                OpExecutionMode %85 OriginUpperLeft
                OpMemberDecorate %15 0 Offset 0
                OpMemberDecorate %15 1 Offset 16
```

[spirv-diff-another.zip](https://github.com/KhronosGroup/SPIRV-Tools/files/11448256/spirv-diff-another.zip)

@ShabbyX PTAL
`spirv-diff` heavily relies on debug information to match variables. It's obvious in this case that these two variables should have been matched, but things quickly get ambiguous when there are multiple variables.

For example, say `f(float a, float b, float c)` is being matched with `f(float d, float e)`, i.e. the function has one parameter reduced. How do you match these variables? One possibility is to brute-force all possibilities and see which diff is the smallest, which might just be fast enough in practice.

I've also seriously considered if it's just better to run some optimization algorithm (like genetic algorithm or something) that matches instructions and get the minimum diff it can find instead of trying to be smart about it :shrug:

All that said, if you are able to, you'll have a better time diffing if you can make sure debug info is retained. At the same time, I'll see what I can do about the unnamed variable matching; in the very least, if there's only one of a given type it's most likely a match.
The second one looks like a bug, the instructions are identical!
These are output files from the Naga shader translator's test suite. I could make Naga attach debug information to function parameters.

However, I've seen this behavior with functions that take only one parameter.

In the cases that are causing difficulty for me (spirv-diff is a wonderful tool, by the way!! Incredibly helpful), the diff would go away entirely if spirv-diff chose the simplest pairing of instructions, so my guess is that this is probably not about improving heuristics in ambiguous cases.
Reduced test case.
[spirv-diff-another.zip](https://github.com/KhronosGroup/SPIRV-Tools/files/11522894/spirv-diff-another.zip)


Fix patch:
diff --git a/source/diff/diff.cpp b/source/diff/diff.cpp
index 6daed321d1..c8bb27edca 100644
--- a/source/diff/diff.cpp
+++ b/source/diff/diff.cpp
@@ -101,6 +101,13 @@ class IdMap {
     return from < id_map_.size() && id_map_[from] != 0;
   }
 
+  bool IsMapped(const opt::Instruction* from_inst) const {
+    assert(from_inst != nullptr);
+    assert(!from_inst->HasResultId());
+
+    return inst_map_.find(from_inst) != inst_map_.end();
+  }
+
   // Map any ids in src and dst that have not been mapped to new ids in dst and
   // src respectively.
   void MapUnmatchedIds(IdMap& other_way);
@@ -150,6 +157,9 @@ class SrcDstIdMap {
 
   bool IsSrcMapped(uint32_t src) { return src_to_dst_.IsMapped(src); }
   bool IsDstMapped(uint32_t dst) { return dst_to_src_.IsMapped(dst); }
+  bool IsDstMapped(const opt::Instruction* dst_inst) {
+    return dst_to_src_.IsMapped(dst_inst);
+  }
 
   // Map any ids in src and dst that have not been mapped to new ids in dst and
   // src respectively.
@@ -1419,7 +1429,6 @@ void Differ::MatchTypeForwardPointersByName(const IdGroup& src,
   GroupIdsAndMatch<std::string>(
       src, dst, "", &Differ::GetSanitizedName,
       [this](const IdGroup& src_group, const IdGroup& dst_group) {
-
         // Match only if there's a unique forward declaration with this debug
         // name.
         if (src_group.size() == 1 && dst_group.size() == 1) {
@@ -1598,7 +1607,6 @@ void Differ::MatchFunctionParamIds(const opt::Function* src_func,
   GroupIdsAndMatch<std::string>(
       src_params, dst_params, "", &Differ::GetSanitizedName,
       [this](const IdGroup& src_group, const IdGroup& dst_group) {
-
         // There shouldn't be two parameters with the same name, so the ids
         // should match. There is nothing restricting the SPIR-V however to have
         // two parameters with the same name, so be resilient against that.
@@ -1613,7 +1621,6 @@ void Differ::MatchFunctionParamIds(const opt::Function* src_func,
       src_params, dst_params, 0, &Differ::GroupIdsHelperGetTypeId,
       [this](const IdGroup& src_group_by_type_id,
              const IdGroup& dst_group_by_type_id) {
-
         const size_t shared_param_count =
             std::min(src_group_by_type_id.size(), dst_group_by_type_id.size());
 
@@ -2064,9 +2071,10 @@ void Differ::MatchEntryPointIds() {
     }
 
     // Otherwise match them by name.
-    bool matched = false;
     for (const opt::Instruction* src_inst : src_insts) {
       for (const opt::Instruction* dst_inst : dst_insts) {
+        if (id_map_.IsDstMapped(dst_inst)) continue;
+
         const opt::Operand& src_name = src_inst->GetOperand(2);
         const opt::Operand& dst_name = dst_inst->GetOperand(2);
 
@@ -2075,13 +2083,9 @@ void Differ::MatchEntryPointIds() {
           uint32_t dst_id = dst_inst->GetSingleWordOperand(1);
           id_map_.MapIds(src_id, dst_id);
           id_map_.MapInsts(src_inst, dst_inst);
-          matched = true;
           break;
         }
       }
-      if (matched) {
-        break;
-      }
     }
   }
 }
@@ -2126,7 +2130,6 @@ void Differ::MatchTypeForwardPointers() {
       spv::StorageClass::Max, &Differ::GroupIdsHelperGetTypePointerStorageClass,
       [this](const IdGroup& src_group_by_storage_class,
              const IdGroup& dst_group_by_storage_class) {
-
         // Group them further by the type they are pointing to and loop over
         // them.
         GroupIdsAndMatch<spv::Op>(
@@ -2134,7 +2137,6 @@ void Differ::MatchTypeForwardPointers() {
             spv::Op::Max, &Differ::GroupIdsHelperGetTypePointerTypeOp,
             [this](const IdGroup& src_group_by_type_op,
                    const IdGroup& dst_group_by_type_op) {
-
               // Group them even further by debug info, if possible and match by
               // debug name.
               MatchTypeForwardPointersByName(src_group_by_type_op,
@@ -2378,7 +2380,6 @@ void Differ::MatchFunctions() {
   GroupIdsAndMatch<std::string>(
       src_func_ids, dst_func_ids, "", &Differ::GetSanitizedName,
       [this](const IdGroup& src_group, const IdGroup& dst_group) {
-
         // If there is a single function with this name in src and dst, it's a
         // definite match.
         if (src_group.size() == 1 && dst_group.size() == 1) {
@@ -2392,7 +2393,6 @@ void Differ::MatchFunctions() {
                                    &Differ::GroupIdsHelperGetTypeId,
                                    [this](const IdGroup& src_group_by_type_id,
                                           const IdGroup& dst_group_by_type_id) {
-
                                      if (src_group_by_type_id.size() == 1 &&
                                          dst_group_by_type_id.size() == 1) {
                                        id_map_.MapIds(src_group_by_type_id[0],
@@ -2437,7 +2437,6 @@ void Differ::MatchFunctions() {
       src_func_ids, dst_func_ids, 0, &Differ::GroupIdsHelperGetTypeId,
       [this](const IdGroup& src_group_by_type_id,
              const IdGroup& dst_group_by_type_id) {
-
         BestEffortMatchFunctions(src_group_by_type_id, dst_group_by_type_id,
                                  src_func_insts_, dst_func_insts_);
       });


Test patch:
diff --git a/test/diff/diff_files/multiple_same_entry_points_autogen.cpp b/test/diff/diff_files/multiple_same_entry_points_autogen.cpp
index 9d011661c6..00bee6be3a 100644
--- a/test/diff/diff_files/multiple_same_entry_points_autogen.cpp
+++ b/test/diff/diff_files/multiple_same_entry_points_autogen.cpp
@@ -125,9 +125,8 @@ TEST(DiffTest, MultipleSameEntryPoints) {
  OpCapability Shader
  %1 = OpExtInstImport "GLSL.std.450"
  OpMemoryModel Logical GLSL450
-+OpEntryPoint Vertex %12 "main2" %13 %14 %15
  OpEntryPoint Vertex %4 "main1" %8 %10
--OpEntryPoint Vertex %12 "main2" %13 %14 %15
+ OpEntryPoint Vertex %12 "main2" %13 %14 %15
  OpSource ESSL 310
  OpName %4 "main1"
  OpName %12 "main2"
@@ -257,9 +256,8 @@ TEST(DiffTest, MultipleSameEntryPointsNoDebug) {
  OpCapability Shader
  %1 = OpExtInstImport "GLSL.std.450"
  OpMemoryModel Logical GLSL450
-+OpEntryPoint Vertex %12 "main2" %13 %14 %15
  OpEntryPoint Vertex %4 "main1" %8 %10
--OpEntryPoint Vertex %12 "main2" %13 %14 %15
+ OpEntryPoint Vertex %12 "main2" %13 %14 %15
  OpSource ESSL 310
  OpDecorate %8 Location 0
  OpDecorate %10 Location 0
@@ -304,9 +302,8 @@ TEST(DiffTest, MultipleSameEntryPointsDumpIds) {
  OpCapability Shader
  %1 = OpExtInstImport "GLSL.std.450"
  OpMemoryModel Logical GLSL450
-+OpEntryPoint Vertex %12 "main2" %13 %14 %15
  OpEntryPoint Vertex %4 "main1" %8 %10
--OpEntryPoint Vertex %12 "main2" %13 %14 %15
+ OpEntryPoint Vertex %12 "main2" %13 %14 %15
  OpSource ESSL 310
  OpName %4 "main1"
  OpName %12 "main2"