Index: llvm/test/tools/llvm-diff/phinode-1.ll
===================================================================
--- /dev/null
+++ llvm/test/tools/llvm-diff/phinode-1.ll
@@ -0,0 +1,15 @@
+; Issue: https://github.com/llvm/llvm-project/issues/56076
+; RUN: llvm-diff %s %s
+
+define double @foo() {
+entry:
+  br i1 true, label %else, label %exit
+
+else:
+  %0 = extractelement <2 x double> zeroinitializer, i64 0
+  br label %exit
+
+exit:
+  %res = phi double [ 0.000000e+00, %entry ], [ %0, %else ]
+  ret double 0.000000e+00
+}
Index: llvm/tools/llvm-diff/lib/DifferenceEngine.cpp
===================================================================
--- llvm/tools/llvm-diff/lib/DifferenceEngine.cpp
+++ llvm/tools/llvm-diff/lib/DifferenceEngine.cpp
@@ -590,7 +590,8 @@
       return equivalentAsOperands(cast<Constant>(L), cast<Constant>(R));
 
     if (isa<Instruction>(L))
-      return Values[L] == R || TentativeValues.count(std::make_pair(L, R));
+      return Values[L] == R || TentativeValues.count(std::make_pair(L, R)) ||
+             !diff(cast<Instruction>(L), cast<Instruction>(R), false, false);
 
     if (isa<Argument>(L))
       return Values[L] == R;