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

Issue:
[ spirv-opt ] Infinite recursion/crash with shader
Running the following shader through spirv-opt built to fc42865562700c887463d9a63512d6a73549ae6e with the command line:

`spirv-opt out.spv -Os -o optimized.spv`

results in a crash in the InlineExhaustive pass.

```

; SPIR-V
; Version: 1.5
; Generator: Khronos; 40
; Bound: 60
; Schema: 0
               OpCapability VariablePointers
               OpCapability PhysicalStorageBufferAddresses
               OpCapability Int64
               OpCapability Shader
               OpExtension "SPV_KHR_variable_pointers"
               OpExtension "SPV_KHR_physical_storage_buffer"
               OpMemoryModel PhysicalStorageBuffer64 GLSL450
               OpEntryPoint Fragment %MainPs_0 "main" %g_PushConstants %MainPs
               OpExecutionMode %MainPs_0 OriginUpperLeft
               OpExecutionMode %MainPs_0 DepthReplacing
               OpSource Slang 1
               OpName %vk_BufferPointer_std140 "vk.BufferPointer_std140"
               OpMemberName %vk_BufferPointer_std140 0 "_ptr"
               OpName %TestPushConstant_t_std140 "TestPushConstant_t_std140"
               OpMemberName %TestPushConstant_t_std140 0 "root"
               OpName %g_PushConstants "g_PushConstants"
               OpName %g_PushConstants "g_PushConstants"
               OpName %vk_BufferPointer "vk.BufferPointer"
               OpMemberName %vk_BufferPointer 0 "_ptr"
               OpName %unpackStorage "unpackStorage"
               OpName %vk_BufferPointer_natural "vk.BufferPointer_natural"
               OpMemberName %vk_BufferPointer_natural 0 "_ptr"
               OpName %unpackStorage_0 "unpackStorage"
               OpName %ptr "ptr"
               OpName %_init "$init"
               OpName %MainPs "MainPs"
               OpName %MainPs "MainPs"
               OpName %MainPs_0 "MainPs"
               OpName %block_s_natural "block_s_natural"
               OpMemberName %block_s_natural 0 "x"
               OpMemberName %block_s_natural 1 "next"
               OpDecorate %_ptr_PhysicalStorageBuffer_block_s_natural ArrayStride 24
               OpMemberDecorate %vk_BufferPointer_std140 0 Offset 0
               OpDecorate %TestPushConstant_t_std140 Block
               OpMemberDecorate %TestPushConstant_t_std140 0 Offset 0
               OpMemberDecorate %vk_BufferPointer 0 Offset 0
               OpDecorate %_ptr_PhysicalStorageBuffer_vk_BufferPointer_natural ArrayStride 8
               OpMemberDecorate %vk_BufferPointer_natural 0 Offset 0
               OpDecorate %_ptr_PhysicalStorageBuffer_v4float ArrayStride 16
               OpDecorate %MainPs Location 0
               OpMemberDecorate %block_s_natural 0 Offset 0
               OpMemberDecorate %block_s_natural 1 Offset 16
       %void = OpTypeVoid
          %3 = OpTypeFunction %void
               OpTypeForwardPointer %_ptr_PhysicalStorageBuffer_block_s_natural PhysicalStorageBuffer
%vk_BufferPointer_std140 = OpTypeStruct %_ptr_PhysicalStorageBuffer_block_s_natural
%TestPushConstant_t_std140 = OpTypeStruct %vk_BufferPointer_std140
%_ptr_PushConstant_TestPushConstant_t_std140 = OpTypePointer PushConstant %TestPushConstant_t_std140
        %int = OpTypeInt 32 1
      %int_0 = OpConstant %int 0
%_ptr_PushConstant_vk_BufferPointer_std140 = OpTypePointer PushConstant %vk_BufferPointer_std140
%vk_BufferPointer = OpTypeStruct %_ptr_PhysicalStorageBuffer_block_s_natural
         %21 = OpTypeFunction %vk_BufferPointer %vk_BufferPointer_std140
      %int_1 = OpConstant %int 1
               OpTypeForwardPointer %_ptr_PhysicalStorageBuffer_vk_BufferPointer_natural PhysicalStorageBuffer
%vk_BufferPointer_natural = OpTypeStruct %_ptr_PhysicalStorageBuffer_block_s_natural
         %34 = OpTypeFunction %vk_BufferPointer %vk_BufferPointer_natural
      %ulong = OpTypeInt 64 0
         %42 = OpTypeFunction %ulong %vk_BufferPointer
       %bool = OpTypeBool
    %ulong_0 = OpConstant %ulong 0
      %float = OpTypeFloat 32
    %v4float = OpTypeVector %float 4
%_ptr_PhysicalStorageBuffer_v4float = OpTypePointer PhysicalStorageBuffer %v4float
%_ptr_Output_v4float = OpTypePointer Output %v4float
    %float_0 = OpConstant %float 0
         %58 = OpConstantComposite %v4float %float_0 %float_0 %float_0 %float_0
%block_s_natural = OpTypeStruct %v4float %vk_BufferPointer_natural
%_ptr_PhysicalStorageBuffer_block_s_natural = OpTypePointer PhysicalStorageBuffer %block_s_natural
%_ptr_PhysicalStorageBuffer_vk_BufferPointer_natural = OpTypePointer PhysicalStorageBuffer %vk_BufferPointer_natural
%g_PushConstants = OpVariable %_ptr_PushConstant_TestPushConstant_t_std140 PushConstant
     %MainPs = OpVariable %_ptr_Output_v4float Output
   %MainPs_0 = OpFunction %void None %3
          %4 = OpLabel
         %16 = OpAccessChain %_ptr_PushConstant_vk_BufferPointer_std140 %g_PushConstants %int_0
         %17 = OpLoad %vk_BufferPointer_std140 %16
         %19 = OpFunctionCall %vk_BufferPointer %unpackStorage %17
         %26 = OpCompositeExtract %_ptr_PhysicalStorageBuffer_block_s_natural %19 0
         %30 = OpAccessChain %_ptr_PhysicalStorageBuffer_vk_BufferPointer_natural %26 %int_1
         %31 = OpLoad %vk_BufferPointer_natural %30 Aligned 8
         %32 = OpFunctionCall %vk_BufferPointer %unpackStorage_0 %31
         %40 = OpFunctionCall %ulong %_init %32
         %48 = OpIEqual %bool %40 %ulong_0
               OpSelectionMerge %5 None
               OpBranchConditional %48 %6 %5
          %5 = OpLabel
         %50 = OpCompositeExtract %_ptr_PhysicalStorageBuffer_block_s_natural %32 0
         %54 = OpAccessChain %_ptr_PhysicalStorageBuffer_v4float %50 %int_0
         %55 = OpLoad %v4float %54 Aligned 4
               OpStore %MainPs %55
               OpReturn
          %6 = OpLabel
               OpStore %MainPs %58
               OpReturn
               OpFunctionEnd
%unpackStorage = OpFunction %vk_BufferPointer None %21
         %22 = OpFunctionParameter %vk_BufferPointer_std140
         %23 = OpLabel
         %24 = OpCompositeExtract %_ptr_PhysicalStorageBuffer_block_s_natural %22 0
         %25 = OpCompositeConstruct %vk_BufferPointer %24
               OpReturnValue %25
               OpFunctionEnd
%unpackStorage_0 = OpFunction %vk_BufferPointer None %34
         %35 = OpFunctionParameter %vk_BufferPointer_natural
         %36 = OpLabel
         %37 = OpCompositeExtract %_ptr_PhysicalStorageBuffer_block_s_natural %35 0
         %38 = OpCompositeConstruct %vk_BufferPointer %37
               OpReturnValue %38
               OpFunctionEnd
      %_init = OpFunction %ulong None %42
        %ptr = OpFunctionParameter %vk_BufferPointer
         %44 = OpLabel
         %45 = OpCompositeExtract %_ptr_PhysicalStorageBuffer_block_s_natural %ptr 0
         %46 = OpConvertPtrToU %ulong %45
               OpReturnValue %46
               OpFunctionEnd

```

The callstack of the crash is as follows:

```
[...truncated for brevity..]
 	spirv-opt.exe!spvtools::opt::analysis::TypeManager::RebuildType(const spvtools::opt::analysis::Type & type) Line 597	C++
 	spirv-opt.exe!spvtools::opt::analysis::TypeManager::RebuildType(const spvtools::opt::analysis::Type & type) Line 597	C++
 	spirv-opt.exe!spvtools::opt::analysis::TypeManager::RebuildType(const spvtools::opt::analysis::Type & type) Line 614	C++
 	spirv-opt.exe!spvtools::opt::analysis::TypeManager::RebuildType(const spvtools::opt::analysis::Type & type) Line 597	C++
 	spirv-opt.exe!spvtools::opt::analysis::TypeManager::RebuildType(const spvtools::opt::analysis::Type & type) Line 597	C++
 	spirv-opt.exe!spvtools::opt::analysis::TypeManager::RebuildType(const spvtools::opt::analysis::Type & type) Line 614	C++
 	spirv-opt.exe!spvtools::opt::analysis::TypeManager::RebuildType(const spvtools::opt::analysis::Type & type) Line 597	C++
 	spirv-opt.exe!spvtools::opt::analysis::TypeManager::RebuildType(const spvtools::opt::analysis::Type & type) Line 614	C++
 	spirv-opt.exe!spvtools::opt::analysis::TypeManager::RegisterType(unsigned int id, const spvtools::opt::analysis::Type & type) Line 672	C++
 	spirv-opt.exe!spvtools::opt::analysis::TypeManager::FindPointerToType(unsigned int type_id, spv::StorageClass storage_class) Line 484	C++
 	spirv-opt.exe!spvtools::opt::InlinePass::CreateReturnVar(spvtools::opt::Function * calleeFn, std::vector<std::unique_ptr<spvtools::opt::Instruction,std::default_delete<spvtools::opt::Instruction>>,std::allocator<std::unique_ptr<spvtools::opt::Instruction,std::default_delete<spvtools::opt::Instruction>>>> * new_vars) Line 193	C++
 	spirv-opt.exe!spvtools::opt::InlinePass::GenInlineCode(std::vector<std::unique_ptr<spvtools::opt::BasicBlock,std::default_delete<spvtools::opt::BasicBlock>>,std::allocator<std::unique_ptr<spvtools::opt::BasicBlock,std::default_delete<spvtools::opt::BasicBlock>>>> * new_blocks, std::vector<std::unique_ptr<spvtools::opt::Instruction,std::default_delete<spvtools::opt::Instruction>>,std::allocator<std::unique_ptr<spvtools::opt::Instruction,std::default_delete<spvtools::opt::Instruction>>>> * new_vars, spvtools::opt::InstructionList::iterator call_inst_itr, spvtools::opt::UptrVectorIterator<spvtools::opt::BasicBlock,0> call_block_itr) Line 618	C++
 	spirv-opt.exe!spvtools::opt::InlineExhaustivePass::InlineExhaustive(spvtools::opt::Function * func) Line 33	C++
 	spirv-opt.exe!spvtools::opt::InlineExhaustivePass::ProcessImpl::__l2::<lambda>(spvtools::opt::Function * fp) Line 65	C++
 	spirv-opt.exe!std::invoke<bool <lambda>(spvtools::opt::Function *) &,spvtools::opt::Function *>(spvtools::opt::InlineExhaustivePass::ProcessImpl::__l2::bool <lambda>(spvtools::opt::Function *) & _Obj, spvtools::opt::Function * && _Arg1) Line 1756	C++
 	spirv-opt.exe!std::_Func_impl_no_alloc<bool <lambda>(spvtools::opt::Function *),bool,spvtools::opt::Function *>::_Do_call(spvtools::opt::Function * && <_Args_0>) Line 812	C++
 	spirv-opt.exe!std::_Func_class<bool,spvtools::opt::Function *>::operator()(spvtools::opt::Function * <_Args_0>) Line 855	C++
 	spirv-opt.exe!spvtools::opt::IRContext::ProcessCallTreeFromRoots(std::function<bool __cdecl(spvtools::opt::Function *)> & pfn, std::queue<unsigned int,std::deque<unsigned int,std::allocator<unsigned int>>> * roots) Line 985	C++
 	spirv-opt.exe!spvtools::opt::IRContext::ProcessReachableCallTree(std::function<bool __cdecl(spvtools::opt::Function *)> & pfn) Line 970	C++
 	spirv-opt.exe!spvtools::opt::InlineExhaustivePass::ProcessImpl() Line 69	C++
 	spirv-opt.exe!spvtools::opt::InlineExhaustivePass::Process() Line 77	C++
 	spirv-opt.exe!spvtools::opt::Pass::Run(spvtools::opt::IRContext * ctx) Line 37	C++
 	spirv-opt.exe!spvtools::opt::PassManager::Run(spvtools::opt::IRContext * context) Line 58	C++
 	spirv-opt.exe!spvtools::Optimizer::Run(const unsigned int * original_binary, const unsigned __int64 original_binary_size, std::vector<unsigned int,std::allocator<unsigned int>> * optimized_binary, spv_optimizer_options_t * const opt_options) Line 684	C++
 	spirv-opt.exe!main(int argc, const char * * argv) Line 873	C++

```





Discussion / hints:
Minimal reproducible example from `spirv-reduce`:

```
; SPIR-V
; Version: 1.6
; Generator: Khronos SPIR-V Tools Assembler; 0
; Bound: 66
; Schema: 0
               OpCapability VariablePointers
               OpCapability PhysicalStorageBufferAddresses
               OpCapability Int64
               OpCapability Shader
               OpExtension "SPV_KHR_variable_pointers"
               OpExtension "SPV_KHR_physical_storage_buffer"
               OpMemoryModel PhysicalStorageBuffer64 GLSL450
               OpEntryPoint Fragment %1 "main"
               OpExecutionMode %1 OriginUpperLeft
               OpExecutionMode %1 DepthReplacing
               OpDecorate %_ptr_PhysicalStorageBuffer__struct_12 ArrayStride 24
               OpMemberDecorate %_struct_6 0 Offset 0
               OpMemberDecorate %_struct_8 0 Offset 0
               OpMemberDecorate %_struct_12 0 Offset 16
       %void = OpTypeVoid
         %17 = OpTypeFunction %void
               OpTypeForwardPointer %_ptr_PhysicalStorageBuffer__struct_12 PhysicalStorageBuffer
  %_struct_4 = OpTypeStruct
  %_struct_6 = OpTypeStruct %_ptr_PhysicalStorageBuffer__struct_12
         %22 = OpTypeFunction %_struct_6 %_struct_4
  %_struct_8 = OpTypeStruct %_ptr_PhysicalStorageBuffer__struct_12
       %bool = OpTypeBool
 %_struct_12 = OpTypeStruct %_struct_8
%_ptr_PhysicalStorageBuffer__struct_12 = OpTypePointer PhysicalStorageBuffer %_struct_12
         %60 = OpUndef %_struct_4
         %62 = OpUndef %_struct_6
         %64 = OpUndef %bool
          %1 = OpFunction %void None %17
         %34 = OpLabel
         %37 = OpFunctionCall %_struct_6 %7 %60
               OpSelectionMerge %44 None
               OpBranchConditional %64 %45 %44
         %44 = OpLabel
               OpReturn
         %45 = OpLabel
               OpReturn
               OpFunctionEnd
          %7 = OpFunction %_struct_6 None %22
         %49 = OpFunctionParameter %_struct_4
         %50 = OpLabel
               OpReturnValue %62
               OpFunctionEnd
```
The infinite loop happens when expanding the type for `%62`, there is a circular type reference. I've got a fix in progress.
> The infinite loop happens when expanding the type for `%62`, there is a circular type reference. I've got a fix in progress.

Still incomplete. Long weekend over here. I'll continue next week.
I had some time to look at this today.  The problem here starts when the inliner creates a pointer to the return value, this calls `RegisterType` which in turn calls `RebuildType`. This is where we enter the infinite recursion:

`%62 -> %_struct_6 -> %_ptr_PhysicalStorageBuffer__struct_12 -> %_struct_12 -> %_struct_8 -> %_ptr_PhysicalStorageBuffer__struct_12 -> [...]`

I have implemented a `seen` cache inside `RebuildType` to prevent getting into this, but it's failing some tests. I'm not very familiar with this part of the code, so I'm still a bit confused.  My initial intuition was that I should not need to implement a `seen` cache, since `GetId()` should be non-zero for the types we already have in the pool.  However, I'm getting zero responses from `GetId()` from types that are already in the pool (so I'm not understanding how this pool works).

The on-the-side `seen` cache does work and fixes this case, but I'm getting other failures. I'll investigate them next.
> The on-the-side seen cache does work and fixes this case, but I'm getting other failures. I'll investigate them next.

CC @greg-lunarg @jeremy-lunarg in case they have any advice
I think I found the problem.  When a type is seen, we need to keep the re-constructed type. My code was keep the original type.

Fix patch:
diff --git a/source/opt/type_manager.cpp b/source/opt/type_manager.cpp
index ae320772df..7b609bc776 100644
--- a/source/opt/type_manager.cpp
+++ b/source/opt/type_manager.cpp
@@ -517,13 +517,24 @@ void TypeManager::CreateDecoration(uint32_t target,
   context()->get_def_use_mgr()->AnalyzeInstUse(inst);
 }
 
-Type* TypeManager::RebuildType(const Type& type) {
+Type* TypeManager::RebuildType(uint32_t type_id, const Type& type) {
+  assert(type_id != 0);
+
   // The comparison and hash on the type pool will avoid inserting the rebuilt
   // type if an equivalent type already exists. The rebuilt type will be deleted
   // when it goes out of scope at the end of the function in that case. Repeated
   // insertions of the same Type will, at most, keep one corresponding object in
   // the type pool.
   std::unique_ptr<Type> rebuilt_ty;
+
+  // If |type_id| is already present in the type pool, return the existing type.
+  // This saves extra work in the type builder and prevents running into
+  // circular issues (https://github.com/KhronosGroup/SPIRV-Tools/issues/5623).
+  Type* pool_ty = GetType(type_id);
+  if (pool_ty != nullptr) {
+    return pool_ty;
+  }
+
   switch (type.kind()) {
 #define DefineNoSubtypeCase(kind)             \
   case Type::k##kind:                         \
@@ -550,43 +561,46 @@ Type* TypeManager::RebuildType(const Type& type) {
     case Type::kVector: {
       const Vector* vec_ty = type.AsVector();
       const Type* ele_ty = vec_ty->element_type();
-      rebuilt_ty =
-          MakeUnique<Vector>(RebuildType(*ele_ty), vec_ty->element_count());
+      rebuilt_ty = MakeUnique<Vector>(RebuildType(GetId(ele_ty), *ele_ty),
+                                      vec_ty->element_count());
       break;
     }
     case Type::kMatrix: {
       const Matrix* mat_ty = type.AsMatrix();
       const Type* ele_ty = mat_ty->element_type();
-      rebuilt_ty =
-          MakeUnique<Matrix>(RebuildType(*ele_ty), mat_ty->element_count());
+      rebuilt_ty = MakeUnique<Matrix>(RebuildType(GetId(ele_ty), *ele_ty),
+                                      mat_ty->element_count());
       break;
     }
     case Type::kImage: {
       const Image* image_ty = type.AsImage();
       const Type* ele_ty = image_ty->sampled_type();
-      rebuilt_ty =
-          MakeUnique<Image>(RebuildType(*ele_ty), image_ty->dim(),
-                            image_ty->depth(), image_ty->is_arrayed(),
-                            image_ty->is_multisampled(), image_ty->sampled(),
-                            image_ty->format(), image_ty->access_qualifier());
+      rebuilt_ty = MakeUnique<Image>(
+          RebuildType(GetId(ele_ty), *ele_ty), image_ty->dim(),
+          image_ty->depth(), image_ty->is_arrayed(),
+          image_ty->is_multisampled(), image_ty->sampled(), image_ty->format(),
+          image_ty->access_qualifier());
       break;
     }
     case Type::kSampledImage: {
       const SampledImage* image_ty = type.AsSampledImage();
       const Type* ele_ty = image_ty->image_type();
-      rebuilt_ty = MakeUnique<SampledImage>(RebuildType(*ele_ty));
+      rebuilt_ty =
+          MakeUnique<SampledImage>(RebuildType(GetId(ele_ty), *ele_ty));
       break;
     }
     case Type::kArray: {
       const Array* array_ty = type.AsArray();
-      rebuilt_ty =
-          MakeUnique<Array>(array_ty->element_type(), array_ty->length_info());
+      const Type* ele_ty = array_ty->element_type();
+      rebuilt_ty = MakeUnique<Array>(RebuildType(GetId(ele_ty), *ele_ty),
+                                     array_ty->length_info());
       break;
     }
     case Type::kRuntimeArray: {
       const RuntimeArray* array_ty = type.AsRuntimeArray();
       const Type* ele_ty = array_ty->element_type();
-      rebuilt_ty = MakeUnique<RuntimeArray>(RebuildType(*ele_ty));
+      rebuilt_ty =
+          MakeUnique<RuntimeArray>(RebuildType(GetId(ele_ty), *ele_ty));
       break;
     }
     case Type::kStruct: {
@@ -594,7 +608,7 @@ Type* TypeManager::RebuildType(const Type& type) {
       std::vector<const Type*> subtypes;
       subtypes.reserve(struct_ty->element_types().size());
       for (const auto* ele_ty : struct_ty->element_types()) {
-        subtypes.push_back(RebuildType(*ele_ty));
+        subtypes.push_back(RebuildType(GetId(ele_ty), *ele_ty));
       }
       rebuilt_ty = MakeUnique<Struct>(subtypes);
       Struct* rebuilt_struct = rebuilt_ty->AsStruct();
@@ -611,7 +625,7 @@ Type* TypeManager::RebuildType(const Type& type) {
     case Type::kPointer: {
       const Pointer* pointer_ty = type.AsPointer();
       const Type* ele_ty = pointer_ty->pointee_type();
-      rebuilt_ty = MakeUnique<Pointer>(RebuildType(*ele_ty),
+      rebuilt_ty = MakeUnique<Pointer>(RebuildType(GetId(ele_ty), *ele_ty),
                                        pointer_ty->storage_class());
       break;
     }
@@ -621,9 +635,10 @@ Type* TypeManager::RebuildType(const Type& type) {
       std::vector<const Type*> param_types;
       param_types.reserve(function_ty->param_types().size());
       for (const auto* param_ty : function_ty->param_types()) {
-        param_types.push_back(RebuildType(*param_ty));
+        param_types.push_back(RebuildType(GetId(param_ty), *param_ty));
       }
-      rebuilt_ty = MakeUnique<Function>(RebuildType(*ret_ty), param_types);
+      rebuilt_ty = MakeUnique<Function>(RebuildType(GetId(ret_ty), *ret_ty),
+                                        param_types);
       break;
     }
     case Type::kForwardPointer: {
@@ -633,7 +648,7 @@ Type* TypeManager::RebuildType(const Type& type) {
       const Pointer* target_ptr = forward_ptr_ty->target_pointer();
       if (target_ptr) {
         rebuilt_ty->AsForwardPointer()->SetTargetPointer(
-            RebuildType(*target_ptr)->AsPointer());
+            RebuildType(GetId(target_ptr), *target_ptr)->AsPointer());
       }
       break;
     }
@@ -641,16 +656,17 @@ Type* TypeManager::RebuildType(const Type& type) {
       const CooperativeMatrixNV* cm_type = type.AsCooperativeMatrixNV();
       const Type* component_type = cm_type->component_type();
       rebuilt_ty = MakeUnique<CooperativeMatrixNV>(
-          RebuildType(*component_type), cm_type->scope_id(), cm_type->rows_id(),
-          cm_type->columns_id());
+          RebuildType(GetId(component_type), *component_type),
+          cm_type->scope_id(), cm_type->rows_id(), cm_type->columns_id());
       break;
     }
     case Type::kCooperativeMatrixKHR: {
       const CooperativeMatrixKHR* cm_type = type.AsCooperativeMatrixKHR();
       const Type* component_type = cm_type->component_type();
       rebuilt_ty = MakeUnique<CooperativeMatrixKHR>(
-          RebuildType(*component_type), cm_type->scope_id(), cm_type->rows_id(),
-          cm_type->columns_id(), cm_type->use_id());
+          RebuildType(GetId(component_type), *component_type),
+          cm_type->scope_id(), cm_type->rows_id(), cm_type->columns_id(),
+          cm_type->use_id());
       break;
     }
     default:
@@ -669,7 +685,7 @@ Type* TypeManager::RebuildType(const Type& type) {
 void TypeManager::RegisterType(uint32_t id, const Type& type) {
   // Rebuild |type| so it and all its constituent types are owned by the type
   // pool.
-  Type* rebuilt = RebuildType(type);
+  Type* rebuilt = RebuildType(id, type);
   assert(rebuilt->IsSame(&type));
   id_to_type_[id] = rebuilt;
   if (GetId(rebuilt) == 0) {
diff --git a/source/opt/type_manager.h b/source/opt/type_manager.h
index a70c371db0..948b691bac 100644
--- a/source/opt/type_manager.h
+++ b/source/opt/type_manager.h
@@ -260,7 +260,9 @@ class TypeManager {
   // Returns an equivalent pointer to |type| built in terms of pointers owned by
   // |type_pool_|. For example, if |type| is a vec3 of bool, it will be rebuilt
   // replacing the bool subtype with one owned by |type_pool_|.
-  Type* RebuildType(const Type& type);
+  //
+  // The re-built type will have ID |type_id|.
+  Type* RebuildType(uint32_t type_id, const Type& type);
 
   // Completes the incomplete type |type|, by replaces all references to
   // ForwardPointer by the defining Pointer.


Test patch:
diff --git a/test/opt/type_manager_test.cpp b/test/opt/type_manager_test.cpp
index 946f06cc08..d4d0fef524 100644
--- a/test/opt/type_manager_test.cpp
+++ b/test/opt/type_manager_test.cpp
@@ -942,10 +942,11 @@ OpMemoryModel Logical GLSL450
   EXPECT_NE(context, nullptr);
 
   std::vector<std::unique_ptr<Type>> types = GenerateAllTypes();
-  uint32_t id = 1u;
+  uint32_t id = 0u;
   for (auto& t : types) {
-    context->get_type_mgr()->RegisterType(id, *t);
+    context->get_type_mgr()->RegisterType(++id, *t);
     EXPECT_EQ(*t, *context->get_type_mgr()->GetType(id));
+    EXPECT_EQ(id, context->get_type_mgr()->GetId(t.get()));
   }
   types.clear();
 
@@ -1199,6 +1200,39 @@ OpMemoryModel Logical GLSL450
   Match(text, context.get());
 }
 
+// Structures containing circular type references
+// (from https://github.com/KhronosGroup/SPIRV-Tools/issues/5623).
+TEST(TypeManager, CircularPointerToStruct) {
+  const std::string text = R"(
+               OpCapability VariablePointers
+               OpCapability PhysicalStorageBufferAddresses
+               OpCapability Int64
+               OpCapability Shader
+               OpExtension "SPV_KHR_variable_pointers"
+               OpExtension "SPV_KHR_physical_storage_buffer"
+               OpMemoryModel PhysicalStorageBuffer64 GLSL450
+               OpEntryPoint Fragment %1 "main"
+               OpExecutionMode %1 OriginUpperLeft
+               OpExecutionMode %1 DepthReplacing
+               OpDecorate %1200 ArrayStride 24
+               OpMemberDecorate %600 0 Offset 0
+               OpMemberDecorate %800 0 Offset 0
+               OpMemberDecorate %120 0 Offset 16
+               OpTypeForwardPointer %1200 PhysicalStorageBuffer
+                 %600 = OpTypeStruct %1200
+                 %800 = OpTypeStruct %1200
+                 %120 = OpTypeStruct %800
+                %1200 = OpTypePointer PhysicalStorageBuffer %120
+  )";
+
+  std::unique_ptr<IRContext> context =
+      BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
+                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+  TypeManager manager(nullptr, context.get());
+  uint32_t id = manager.FindPointerToType(600, spv::StorageClass::Function);
+  EXPECT_EQ(id, 1201);
+}
+
 }  // namespace
 }  // namespace analysis
 }  // namespace opt