Linker does not deduplicate equivalent array types

[blue42u]

The linker does not deduplicate equivalent array types between modules, which causes type mismatch errors when sharing an array type (or types based on an array) between modules. Can verify fails for variables and for functions (when used as an argument, directly and pointer to).

Example, causes a type mismatch on symbol "x":

; a.spv
               OpCapability Linkage
               OpCapability Shader
               OpMemoryModel Logical Simple
               OpDecorate %1 LinkageAttributes "x" Import
       %void = OpTypeVoid
       %uint = OpTypeInt 32 0
     %uint_7 = OpConstant %uint 7
%_arr_uint_uint_7 = OpTypeArray %uint %uint_7
%_ptr_Workgroup__arr_uint_uint_7 = OpTypePointer Workgroup %_arr_uint_uint_7
          %1 = OpVariable %_ptr_Workgroup__arr_uint_uint_7 Workgroup

; b.spv, differs from a.spv only in changing Import -> Export
               OpCapability Linkage
               OpCapability Shader
               OpMemoryModel Logical Simple
               OpDecorate %1 LinkageAttributes "x" Export
       %void = OpTypeVoid
       %uint = OpTypeInt 32 0
     %uint_7 = OpConstant %uint 7
%_arr_uint_uint_7 = OpTypeArray %uint %uint_7
%_ptr_Workgroup__arr_uint_uint_7 = OpTypePointer Workgroup %_arr_uint_uint_7
          %1 = OpVariable %_ptr_Workgroup__arr_uint_uint_7 Workgroup

Removing the OpDecorate instructions produces duplicates of both the constant and types:

               OpCapability Shader
               OpMemoryModel Logical Simple
               OpModuleProcessed "Linked by SPIR-V Tools Linker"
       %void = OpTypeVoid
       %uint = OpTypeInt 32 0
     %uint_7 = OpConstant %uint 7
%_arr_uint_uint_7 = OpTypeArray %uint %uint_7
%_ptr_Workgroup__arr_uint_uint_7 = OpTypePointer Workgroup %_arr_uint_uint_7
          %6 = OpVariable %_ptr_Workgroup__arr_uint_uint_7 Workgroup
   %uint_7_0 = OpConstant %uint 7
%_arr_uint_uint_7_0 = OpTypeArray %uint %uint_7_0
%_ptr_Workgroup__arr_uint_uint_7_0 = OpTypePointer Workgroup %_arr_uint_uint_7_0
         %10 = OpVariable %_ptr_Workgroup__arr_uint_uint_7_0 Workgroup

[pierremoreau]

Thank you for the bug report and the simple example for reproducing the issue.

AFAICT, it comes from the fact that

1. the type comparison for arrays checks that both array types have the same ID for the constant instruction defining the length, and
2. constants are not de-duplicated after merging all the inputs.

I’ll try to write a fix over the weekend.

[pierremoreau]

@dneto0 Do you have any ideas how this should be handled? The problem is that Array::IsSameImpl() only compares the IDs for the length and not the actual values. This most likely works in the general case, but is a problem for the linking as the types will be duplicated and the constants as well.

I can think of the following solutions:

1. I could try to add a constant de-duplication pass before comparing the types, but I fear that we would end up with the same problem that when checking whether two constants are the same, their types won’t match due to having different constants ID.
2. The linker implements its own type comparison.
3. Array::IsSameImpl() is edited to also compare the actual values if the IDs differ, but for that we either need to:
   1. Pass in extra info to IsSameImpl() so that it can fetch the constant associated to the ID, and all.
   2. Store the constant value and SpecId locally when creating the Array type.

Both 3.i) and 3.ii) seem like reasonable solutions, with 3.ii) probably having an edge performance-wise.

[pierremoreau]

@blue42u I opened a pull request (see above) that fixes the type mismatch error (and could also solve the types not being deduplicated with little effort). However I am unsure if we want to keep that code specific to the linker or merge it in the common type manager, hence the WIP tag.

[blue42u]

@pierremoreau Thank you for the partial fix, I'll look into writing some extra tests for this kind of issue. So far the output on a larger case seems to look good (although it fails validation from the type duplication).

[pierremoreau]

The updated MR should take care of removing the duplicate types; I’ll try to make a proper fix by next week.
I expect you’ll be hitting similar issues with any types whose definition reference an ID (for example TypeVector, TypeImage, etc.).