diff --git a/source/opt/ccp_pass.cpp b/source/opt/ccp_pass.cpp
index 2d19bcb..d84f13f 100644
--- a/source/opt/ccp_pass.cpp
+++ b/source/opt/ccp_pass.cpp
@@ -135,23 +135,15 @@
     }
     return it->second;
   };
-  uint32_t next_id = context()->module()->IdBound();
   Instruction* folded_inst =
       context()->get_instruction_folder().FoldInstructionToConstant(instr,
                                                                     map_func);
+
   if (folded_inst != nullptr) {
     // We do not want to change the body of the function by adding new
     // instructions.  When folding we can only generate new constants.
     assert(folded_inst->IsConstant() && "CCP is only interested in constant.");
     values_[instr->result_id()] = folded_inst->result_id();
-
-    // If the folded instruction has just been created, its result ID will
-    // match the previous ID bound. When this happens, we need to indicate
-    // that CCP has modified the IR, independently of whether the constant is
-    // actually propagated. See
-    // https://github.com/KhronosGroup/SPIRV-Tools/issues/3636 for details.
-    if (folded_inst->result_id() >= next_id) created_new_constant_ = true;
-
     return SSAPropagator::kInteresting;
   }
 
@@ -278,10 +270,14 @@
   // Even if we make no changes to the function's IR, propagation may have
   // created new constants.  Even if those constants cannot be replaced in
   // the IR, the constant definition itself is a change.  To reflect this,
-  // we initialize the IR changed indicator with the value of the
-  // created_new_constant_ indicator.  For an example, see the bug reported
-  // in https://github.com/KhronosGroup/SPIRV-Tools/issues/3636.
-  bool changed_ir = created_new_constant_;
+  // we check whether the next ID to be given by the module is different than
+  // the original bound ID. If that happens, new instructions were added to the
+  // module during propagation.
+  //
+  // See https://github.com/KhronosGroup/SPIRV-Tools/issues/3636 and
+  // https://github.com/KhronosGroup/SPIRV-Tools/issues/3991 for details.
+  bool changed_ir = (context()->module()->IdBound() > original_id_bound_);
+
   for (const auto& it : values_) {
     uint32_t id = it.first;
     uint32_t cst_id = it.second;
@@ -290,6 +286,7 @@
       changed_ir |= context()->ReplaceAllUsesWith(id, cst_id);
     }
   }
+
   return changed_ir;
 }
 
@@ -329,7 +326,7 @@
     }
   }
 
-  created_new_constant_ = false;
+  original_id_bound_ = context()->module()->IdBound();
 }
 
 Pass::Status CCPPass::Process() {
diff --git a/source/opt/ccp_pass.h b/source/opt/ccp_pass.h
index 83c4ab9..fb20c78 100644
--- a/source/opt/ccp_pass.h
+++ b/source/opt/ccp_pass.h
@@ -106,8 +106,9 @@
   // Propagator engine used.
   std::unique_ptr<SSAPropagator> propagator_;
 
-  // True if the pass created new constant instructions during propagation.
-  bool created_new_constant_;
+  // Value for the module's ID bound before running CCP. Used to detect whether
+  // propagation created new instructions.
+  uint32_t original_id_bound_;
 };
 
 }  // namespace opt
diff --git a/test/opt/ccp_test.cpp b/test/opt/ccp_test.cpp
index 943bc6c..ef73435 100644
--- a/test/opt/ccp_test.cpp
+++ b/test/opt/ccp_test.cpp
@@ -1158,6 +1158,56 @@
   auto result = SinglePassRunAndMatch<CCPPass>(text, true);
   EXPECT_EQ(std::get<1>(result), Pass::Status::SuccessWithChange);
 }
+
+// Test from https://github.com/KhronosGroup/SPIRV-Tools/issues/3991
+// Similar to the previous one but constants are created even when no
+// instruction are ever folded during propagation.
+TEST_F(CCPTest, CCPNoChangeFailureWithUnfoldableInstr) {
+  const std::string text = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %2 "main"
+               OpExecutionMode %2 OriginUpperLeft
+       %void = OpTypeVoid
+          %4 = OpTypeFunction %void
+      %float = OpTypeFloat 32
+    %v3float = OpTypeVector %float 3
+       %uint = OpTypeInt 32 0
+     %uint_0 = OpConstant %uint 0
+       %bool = OpTypeBool
+    %float_0 = OpConstant %float 0
+         %11 = OpConstantComposite %v3float %float_0 %float_0 %float_0
+%float_0_300000012 = OpConstant %float 0.300000012
+         %13 = OpConstantComposite %v3float %float_0_300000012 %float_0_300000012 %float_0_300000012
+
+; CCP generates two constants when trying to fold an instruction, which it
+; ultimately fails to fold. The instruction folder in CCP was only
+; checking for newly added constants if the instruction folds successfully.
+;
+; CHECK: %float_1 = OpConstant %float 1
+; CHECK: %float_0_699999988 = OpConstant %float 0.69999998
+
+          %2 = OpFunction %void None %4
+         %14 = OpLabel
+         %15 = OpBitcast %uint %float_0_300000012
+         %16 = OpUGreaterThan %bool %15 %uint_0
+               OpBranch %17
+         %17 = OpLabel
+         %18 = OpPhi %v3float %11 %14 %13 %19
+               OpLoopMerge %20 %19 None
+               OpBranchConditional %16 %19 %20
+         %19 = OpLabel
+               OpBranch %17
+         %20 = OpLabel
+         %21 = OpExtInst %v3float %1 FMix %11 %18 %13
+               OpReturn
+               OpFunctionEnd
+)";
+
+  auto result = SinglePassRunAndMatch<CCPPass>(text, true);
+  EXPECT_EQ(std::get<1>(result), Pass::Status::SuccessWithChange);
+}
 }  // namespace
 }  // namespace opt
 }  // namespace spvtools