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

Issue:
spirv-opt: scalar-replacement can produce invalid SPIR-V with buffer references
Running spirv-opt on the shaders from https://github.com/KhronosGroup/glslang/issues/3188 with -Os results in SPIR-V validation error as such: 
```
error: line 122: Result type (OpTypePointer) does not match the type that results from indexing into the composite (OpTypePointer).
  %678 = OpCompositeExtract %_ptr_PhysicalStorageBuffer_MeshVertexNormals %414 0
```
Additionally passing --validate-after-all points to the scalar-replacement pass
```
error: line 189: OpVariable 677: expected AliasedPointer or RestrictPointer for PhysicalStorageBuffer pointer.
  %677 = OpVariable %_ptr_Function__ptr_PhysicalStorageBuffer_MeshVertexNormals Function

error: line 0: Validation failed after pass scalar-replacement=0
```
The SPIR-V before and after optimization are attached, these are from a cut-down version of the shaders in the original glslang issue.
[files.zip](https://github.com/KhronosGroup/SPIRV-Tools/files/11237236/files.zip)



Discussion / hints:
It appears that what is happening is that there are two separate PhysicalStorageBuffer types where the contents of the pointed-to struct are structurally identical but the struct types are distinct, and those are being used interchangeably when they shouldn't be.
Yes. This has tripped up the shader tool chain before in different ways. That is, two SPIR-V types that are structurally identical, but are (correctly) considered different only because they have different result ids.

There are probably a couple different ways to deal with this. One way (perhaps the best way) is to create a type canonicalization pass such that all type uses in the module use only the type registered in the TypeManager and remove unused types afterward using a simple, static, dead code elimination. In essence, a pass that eliminates redundant types. We would probably call it near the beginning of any optimization recipe.

We probably would not want to use the aggressive dead code elimination here to get rid of the unused types. Rather just do a simple single pass from the bottom of the module to the top, eliminating unused instructions as you go. You might have to do first pass to record uses by phi functions and other forward declarations. I am not sure if there is such a pass in spirv-opt. You might have to write it.


Since we want to allow anyone to use their own order for the optimizations, I would like to see if we can fix this in scalar replacement first. The solution of adding another pass to canonicalize would be nice, but adds extra knowledge that users picking their own pass would have to think about. I would prefer to not have to do that if we do not have it.
The thing is it's not really an issue with scalar replacement per se, it's going to give the same problem with any pass that add instructions referencing these types, because there are 2 types with distinct IDs that are being represented by a single type in the type manager.
> Since we want to allow anyone to use their own order for the optimizations, I would like to see if we can fix this in scalar replacement first. The solution of adding another pass to canonicalize would be nice, but adds extra knowledge that users picking their own pass would have to think about. I would prefer to not have to do that if we do not have it.

I was just imagining the possibly cascading extra logic that might be required to deal with this situation on an ad hoc basis. It seems much cleaner to just get rid of the redundant types to begin with.

But you are right. We don't want to require users to have this extra knowledge.

What if we just hard coded calls at the beginning of scalar replacement to the proposed passes to clean up redundant types?

Or what if we improved the generation of the TypeManager to get rid of redundant types?

Then the fix/solution is built-in and doesn't require special knowledge.

> Or what if we improved the generation of the TypeManager to get rid of redundant types?

We have talked about this in our team, but did not get to a fully satisfactory solution. The problem is that some types can only be defined once, while other types can be defined multiple times. We wanted something like the type manager so that we did not accidentally create multiple 32-bit unsigned integer types. We did not realize at the time how much of a problem this might cause, and we used the type manager in places we should not have. If I were to reimplement it, I would probably limit the type manager to just the type that could not be duplicated. 

Given what we have, I kinda want to add a restrict to certain functions, and add an assert to `TypeManager::GetId` if it is used on a type that could have a duplicate. This should let us know all of the places this type of error could happen, and then we can fix all of them. I'll look into this next week.

If we were to just add the deduplication to scalar replacement, then it would not fix all uses of the type manager, and is probably just as easy to get scalar replacement to stop relying on the type manager. 
The problem is not in scalar-replacement. The validation error after scalar replacement is picking up that the original shader is invalid, even if the validator does not say so.

The spir-v module contains:

```
%Mesh = OpTypeStruct %_ptr_PhysicalStorageBuffer_MeshVertexPositions %_ptr_PhysicalStorageBuffer_MeshVertexNormals
%_ptr_Function_Mesh = OpTypePointer Function %Mesh
%meshData = OpVariable %_ptr_Function_Mesh Function
```

From my understanding `%meshData` must have either an `AliasedPointer` or `RestrictPointer`. See [here](https://registry.khronos.org/SPIR-V/specs/unified1/SPIRV.html#:~:text=If%20the%20type%20an%20OpVariable%20points%20to%20is%20a%20pointer%20(or%20contains%20a%20pointer)%20in%20the%20PhysicalStorageBuffer%20storage%20class%2C%20the%20OpVariable%20must%20be%20decorated%20with%20exactly%20one%20of%20AliasedPointer%20or%20RestrictPointer.).

When scalar replacement replaces `%meshData` with two variables (one for each member), it does not add a decoration for the new symbols, and the validator starts to complain.  After adding `AliasedPointer` to `%meshData`, spirv-opt produces spir-v that validates.

The first task is to fix glslang. Then there is probably a hidden bug in spirv-tools that I will try to find another way to track down.




Fix patch:
diff --git a/source/opt/scalar_replacement_pass.cpp b/source/opt/scalar_replacement_pass.cpp
index ae1a2a363e..38c8aeccc6 100644
--- a/source/opt/scalar_replacement_pass.cpp
+++ b/source/opt/scalar_replacement_pass.cpp
@@ -466,9 +466,9 @@ void ScalarReplacementPass::TransferAnnotations(
 }
 
 void ScalarReplacementPass::CreateVariable(
-    uint32_t typeId, Instruction* varInst, uint32_t index,
+    uint32_t type_id, Instruction* var_inst, uint32_t index,
     std::vector<Instruction*>* replacements) {
-  uint32_t ptrId = GetOrCreatePointerType(typeId);
+  uint32_t ptr_id = GetOrCreatePointerType(type_id);
   uint32_t id = TakeNextId();
 
   if (id == 0) {
@@ -476,51 +476,22 @@ void ScalarReplacementPass::CreateVariable(
   }
 
   std::unique_ptr<Instruction> variable(
-      new Instruction(context(), spv::Op::OpVariable, ptrId, id,
+      new Instruction(context(), spv::Op::OpVariable, ptr_id, id,
                       std::initializer_list<Operand>{
                           {SPV_OPERAND_TYPE_STORAGE_CLASS,
                            {uint32_t(spv::StorageClass::Function)}}}));
 
-  BasicBlock* block = context()->get_instr_block(varInst);
+  BasicBlock* block = context()->get_instr_block(var_inst);
   block->begin().InsertBefore(std::move(variable));
   Instruction* inst = &*block->begin();
 
   // If varInst was initialized, make sure to initialize its replacement.
-  GetOrCreateInitialValue(varInst, index, inst);
+  GetOrCreateInitialValue(var_inst, index, inst);
   get_def_use_mgr()->AnalyzeInstDefUse(inst);
   context()->set_instr_block(inst, block);
 
-  // Copy decorations from the member to the new variable.
-  Instruction* typeInst = GetStorageType(varInst);
-  for (auto dec_inst :
-       get_decoration_mgr()->GetDecorationsFor(typeInst->result_id(), false)) {
-    uint32_t decoration;
-    if (dec_inst->opcode() != spv::Op::OpMemberDecorate) {
-      continue;
-    }
-
-    if (dec_inst->GetSingleWordInOperand(1) != index) {
-      continue;
-    }
-
-    decoration = dec_inst->GetSingleWordInOperand(2u);
-    switch (spv::Decoration(decoration)) {
-      case spv::Decoration::RelaxedPrecision: {
-        std::unique_ptr<Instruction> new_dec_inst(
-            new Instruction(context(), spv::Op::OpDecorate, 0, 0, {}));
-        new_dec_inst->AddOperand(Operand(SPV_OPERAND_TYPE_ID, {id}));
-        for (uint32_t i = 2; i < dec_inst->NumInOperandWords(); ++i) {
-          new_dec_inst->AddOperand(Operand(dec_inst->GetInOperand(i)));
-        }
-        context()->AddAnnotationInst(std::move(new_dec_inst));
-      } break;
-      default:
-        break;
-    }
-  }
-
-  // Update the DebugInfo debug information.
-  inst->UpdateDebugInfoFrom(varInst);
+  CopyDecorationsToVariable(var_inst, inst, index);
+  inst->UpdateDebugInfoFrom(var_inst);
 
   replacements->push_back(inst);
 }
@@ -529,52 +500,11 @@ uint32_t ScalarReplacementPass::GetOrCreatePointerType(uint32_t id) {
   auto iter = pointee_to_pointer_.find(id);
   if (iter != pointee_to_pointer_.end()) return iter->second;
 
-  analysis::Type* pointeeTy;
-  std::unique_ptr<analysis::Pointer> pointerTy;
-  std::tie(pointeeTy, pointerTy) =
-      context()->get_type_mgr()->GetTypeAndPointerType(
-          id, spv::StorageClass::Function);
-  uint32_t ptrId = 0;
-  if (pointeeTy->IsUniqueType()) {
-    // Non-ambiguous type, just ask the type manager for an id.
-    ptrId = context()->get_type_mgr()->GetTypeInstruction(pointerTy.get());
-    pointee_to_pointer_[id] = ptrId;
-    return ptrId;
-  }
-
-  // Ambiguous type. We must perform a linear search to try and find the right
-  // type.
-  for (auto global : context()->types_values()) {
-    if (global.opcode() == spv::Op::OpTypePointer &&
-        spv::StorageClass(global.GetSingleWordInOperand(0u)) ==
-            spv::StorageClass::Function &&
-        global.GetSingleWordInOperand(1u) == id) {
-      if (get_decoration_mgr()->GetDecorationsFor(id, false).empty()) {
-        // Only reuse a decoration-less pointer of the correct type.
-        ptrId = global.result_id();
-        break;
-      }
-    }
-  }
-
-  if (ptrId != 0) {
-    pointee_to_pointer_[id] = ptrId;
-    return ptrId;
-  }
-
-  ptrId = TakeNextId();
-  context()->AddType(MakeUnique<Instruction>(
-      context(), spv::Op::OpTypePointer, 0, ptrId,
-      std::initializer_list<Operand>{{SPV_OPERAND_TYPE_STORAGE_CLASS,
-                                      {uint32_t(spv::StorageClass::Function)}},
-                                     {SPV_OPERAND_TYPE_ID, {id}}}));
-  Instruction* ptr = &*--context()->types_values_end();
-  get_def_use_mgr()->AnalyzeInstDefUse(ptr);
-  pointee_to_pointer_[id] = ptrId;
-  // Register with the type manager if necessary.
-  context()->get_type_mgr()->RegisterType(ptrId, *pointerTy);
-
-  return ptrId;
+  analysis::TypeManager* type_mgr = context()->get_type_mgr();
+  uint32_t ptr_type_id =
+      type_mgr->FindPointerToType(id, spv::StorageClass::Function);
+  pointee_to_pointer_[id] = ptr_type_id;
+  return ptr_type_id;
 }
 
 void ScalarReplacementPass::GetOrCreateInitialValue(Instruction* source,
@@ -761,6 +691,8 @@ bool ScalarReplacementPass::CheckTypeAnnotations(
       case spv::Decoration::AlignmentId:
       case spv::Decoration::MaxByteOffset:
       case spv::Decoration::RelaxedPrecision:
+      case spv::Decoration::AliasedPointer:
+      case spv::Decoration::RestrictPointer:
         break;
       default:
         return false;
@@ -781,6 +713,8 @@ bool ScalarReplacementPass::CheckAnnotations(const Instruction* varInst) const {
       case spv::Decoration::Alignment:
       case spv::Decoration::AlignmentId:
       case spv::Decoration::MaxByteOffset:
+      case spv::Decoration::AliasedPointer:
+      case spv::Decoration::RestrictPointer:
         break;
       default:
         return false;
@@ -1011,5 +945,69 @@ uint64_t ScalarReplacementPass::GetMaxLegalIndex(
   return 0;
 }
 
+void ScalarReplacementPass::CopyDecorationsToVariable(Instruction* from,
+                                                      Instruction* to,
+                                                      uint32_t member_index) {
+  CopyPointerDecorationsToVariable(from, to);
+  CopyNecessaryMemberDecorationsToVariable(from, to, member_index);
+}
+
+void ScalarReplacementPass::CopyPointerDecorationsToVariable(Instruction* from,
+                                                             Instruction* to) {
+  // The RestrictPointer and AliasedPointer decorations are copied to all
+  // members even if the new variable does not contain a pointer. It does
+  // not hurt to do so.
+  for (auto dec_inst :
+       get_decoration_mgr()->GetDecorationsFor(from->result_id(), false)) {
+    uint32_t decoration;
+    decoration = dec_inst->GetSingleWordInOperand(1u);
+    switch (spv::Decoration(decoration)) {
+      case spv::Decoration::AliasedPointer:
+      case spv::Decoration::RestrictPointer: {
+        std::unique_ptr<Instruction> new_dec_inst(dec_inst->Clone(context()));
+        new_dec_inst->SetInOperand(0, {to->result_id()});
+        context()->AddAnnotationInst(std::move(new_dec_inst));
+      } break;
+      default:
+        break;
+    }
+  }
+}
+
+void ScalarReplacementPass::CopyNecessaryMemberDecorationsToVariable(
+    Instruction* from, Instruction* to, uint32_t member_index) {
+  Instruction* type_inst = GetStorageType(from);
+  for (auto dec_inst :
+       get_decoration_mgr()->GetDecorationsFor(type_inst->result_id(), false)) {
+    uint32_t decoration;
+    if (dec_inst->opcode() == spv::Op::OpMemberDecorate) {
+      if (dec_inst->GetSingleWordInOperand(1) != member_index) {
+        continue;
+      }
+
+      decoration = dec_inst->GetSingleWordInOperand(2u);
+      switch (spv::Decoration(decoration)) {
+        case spv::Decoration::ArrayStride:
+        case spv::Decoration::Alignment:
+        case spv::Decoration::AlignmentId:
+        case spv::Decoration::MaxByteOffset:
+        case spv::Decoration::MaxByteOffsetId:
+        case spv::Decoration::RelaxedPrecision: {
+          std::unique_ptr<Instruction> new_dec_inst(
+              new Instruction(context(), spv::Op::OpDecorate, 0, 0, {}));
+          new_dec_inst->AddOperand(
+              Operand(SPV_OPERAND_TYPE_ID, {to->result_id()}));
+          for (uint32_t i = 2; i < dec_inst->NumInOperandWords(); ++i) {
+            new_dec_inst->AddOperand(Operand(dec_inst->GetInOperand(i)));
+          }
+          context()->AddAnnotationInst(std::move(new_dec_inst));
+        } break;
+        default:
+          break;
+      }
+    }
+  }
+}
+
 }  // namespace opt
 }  // namespace spvtools
diff --git a/source/opt/scalar_replacement_pass.h b/source/opt/scalar_replacement_pass.h
index 0bcd2a4e40..c73ecfd98b 100644
--- a/source/opt/scalar_replacement_pass.h
+++ b/source/opt/scalar_replacement_pass.h
@@ -262,9 +262,26 @@ class ScalarReplacementPass : public MemPass {
   // that we will be willing to split.
   bool IsLargerThanSizeLimit(uint64_t length) const;
 
+  // Copies all relevant decorations from `from` to `to`. This includes
+  // decorations applied to the variable, and to the members of the type.
+  // It is assumed that `to` is a variable that is intended to replace the
+  // `member_index`th member of `from`.
+  void CopyDecorationsToVariable(Instruction* from, Instruction* to,
+                                 uint32_t member_index);
+
+  // Copies pointer related decoration from `from` to `to` if they exist.
+  void CopyPointerDecorationsToVariable(Instruction* from, Instruction* to);
+
+  // Copies decorations that are needed from the `member_index` of `from` to
+  // `to, if there was one.
+  void CopyNecessaryMemberDecorationsToVariable(Instruction* from,
+                                                Instruction* to,
+                                                uint32_t member_index);
+
   // Limit on the number of members in an object that will be replaced.
   // 0 means there is no limit.
   uint32_t max_num_elements_;
+
   // This has to be big enough to fit "scalar-replacement=" followed by a
   // uint32_t number written in decimal (so 10 digits), and then a
   // terminating nul.
diff --git a/source/opt/type_manager.cpp b/source/opt/type_manager.cpp
index 6e4c054ef4..1b1aeadc8a 100644
--- a/source/opt/type_manager.cpp
+++ b/source/opt/type_manager.cpp
@@ -178,7 +178,7 @@ void TypeManager::RemoveId(uint32_t id) {
   if (iter == id_to_type_.end()) return;
 
   auto& type = iter->second;
-  if (!type->IsUniqueType(true)) {
+  if (!type->IsUniqueType()) {
     auto tIter = type_to_id_.find(type);
     if (tIter != type_to_id_.end() && tIter->second == id) {
       // |type| currently maps to |id|.
@@ -437,7 +437,7 @@ uint32_t TypeManager::FindPointerToType(uint32_t type_id,
                                         spv::StorageClass storage_class) {
   Type* pointeeTy = GetType(type_id);
   Pointer pointerTy(pointeeTy, storage_class);
-  if (pointeeTy->IsUniqueType(true)) {
+  if (pointeeTy->IsUniqueType()) {
     // Non-ambiguous type. Get the pointer type through the type manager.
     return GetTypeInstruction(&pointerTy);
   }
diff --git a/source/opt/types.cpp b/source/opt/types.cpp
index 2f1836281b..49eec9b743 100644
--- a/source/opt/types.cpp
+++ b/source/opt/types.cpp
@@ -84,10 +84,9 @@ bool Type::HasSameDecorations(const Type* that) const {
   return CompareTwoVectors(decorations_, that->decorations_);
 }
 
-bool Type::IsUniqueType(bool allowVariablePointers) const {
+bool Type::IsUniqueType() const {
   switch (kind_) {
     case kPointer:
-      return !allowVariablePointers;
     case kStruct:
     case kArray:
     case kRuntimeArray:
diff --git a/source/opt/types.h b/source/opt/types.h
index 1f329373b1..26c058c6f8 100644
--- a/source/opt/types.h
+++ b/source/opt/types.h
@@ -148,12 +148,16 @@ class Type {
   // Returns a clone of |this| minus any decorations.
   std::unique_ptr<Type> RemoveDecorations() const;
 
-  // Returns true if this type must be unique.
+  // Returns true if this cannot hash to the same value as another type in the
+  // module. For example, structs are not unique types because the module could
+  // have two types
   //
-  // If variable pointers are allowed, then pointers are not required to be
-  // unique.
-  // TODO(alanbaker): Update this if variable pointers become a core feature.
-  bool IsUniqueType(bool allowVariablePointers = false) const;
+  //  %1 = OpTypeStruct %int
+  //  %2 = OpTypeStruct %int
+  //
+  // The only way to distinguish these types is the result id. The type manager
+  // will hash them to the same value.
+  bool IsUniqueType() const;
 
   bool operator==(const Type& other) const;
 


Test patch:
diff --git a/test/opt/scalar_replacement_test.cpp b/test/opt/scalar_replacement_test.cpp
index b63a6b6c11..0ba285bb62 100644
--- a/test/opt/scalar_replacement_test.cpp
+++ b/test/opt/scalar_replacement_test.cpp
@@ -2308,6 +2308,54 @@ TEST_F(ScalarReplacementTest, UndefImageMember) {
   SinglePassRunAndMatch<ScalarReplacementPass>(text, true);
 }
 
+TEST_F(ScalarReplacementTest, RestrictPointer) {
+  // This test makes sure that a variable with the restrict pointer decoration
+  // is replaced, and that the pointer is applied to the new variable.
+  const std::string text = R"(
+; CHECK: OpDecorate [[new_var:%\w+]] RestrictPointer
+; CHECK: [[struct_type:%\w+]] = OpTypeStruct %int
+; CHECK: [[ptr_type:%\w+]] = OpTypePointer PhysicalStorageBuffer [[struct_type]]
+; CHECK: [[dup_struct_type:%\w+]] = OpTypeStruct %int
+; CHECK: {{%\w+}} = OpTypePointer PhysicalStorageBuffer [[dup_struct_type]]
+; CHECK: [[var_type:%\w+]] = OpTypePointer Function [[ptr_type]]
+; CHECK: [[new_var]] = OpVariable [[var_type]] Function
+               OpCapability Shader
+               OpCapability PhysicalStorageBufferAddresses
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel PhysicalStorageBuffer64 GLSL450
+               OpEntryPoint Fragment %2 "main"
+               OpExecutionMode %2 OriginUpperLeft
+               OpMemberDecorate %3 0 Offset 0
+               OpDecorate %3 Block
+               OpMemberDecorate %4 0 Offset 0
+               OpDecorate %4 Block
+               OpDecorate %5 RestrictPointer
+          %6 = OpTypeVoid
+          %7 = OpTypeFunction %6
+          %8 = OpTypeInt 32 1
+          %9 = OpConstant %8 0
+          %3 = OpTypeStruct %8
+         %10 = OpTypePointer PhysicalStorageBuffer %3
+         %11 = OpTypeStruct %10
+          %4 = OpTypeStruct %8
+         %12 = OpTypePointer PhysicalStorageBuffer %4
+         %13 = OpTypePointer Function %11
+         %14 = OpTypePointer Function %10
+         %15 = OpTypePointer Function %12
+         %16 = OpUndef %11
+          %2 = OpFunction %6 None %7
+         %17 = OpLabel
+          %5 = OpVariable %13 Function
+               OpStore %5 %16
+         %18 = OpAccessChain %14 %5 %9
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  SetTargetEnv(SPV_ENV_UNIVERSAL_1_6);
+  SinglePassRunAndMatch<ScalarReplacementPass>(text, true);
+}
+
 }  // namespace
 }  // namespace opt
 }  // namespace spvtools
diff --git a/test/opt/types_test.cpp b/test/opt/types_test.cpp
index 4352b7cf58..4ceeb1400c 100644
--- a/test/opt/types_test.cpp
+++ b/test/opt/types_test.cpp
@@ -391,18 +391,13 @@ TEST(Types, IsUniqueType) {
       case Type::kArray:
       case Type::kRuntimeArray:
       case Type::kStruct:
+      case Type::kPointer:
         expectation = false;
         break;
       default:
         break;
     }
-    EXPECT_EQ(t->IsUniqueType(false), expectation)
-        << "expected '" << t->str() << "' to be a "
-        << (expectation ? "" : "non-") << "unique type";
-
-    // Allowing variables pointers.
-    if (t->AsPointer()) expectation = false;
-    EXPECT_EQ(t->IsUniqueType(true), expectation)
+    EXPECT_EQ(t->IsUniqueType(), expectation)
         << "expected '" << t->str() << "' to be a "
         << (expectation ? "" : "non-") << "unique type";
   }