GVN: If a branch has two identical successors, we cannot declare either dead.

[pcc]

Summary

This previously caused miscompilations as a result of phi nodes receiving
undef incoming values from blocks dominated by such successors.

[spatel]

I'm by no means a GVN expert, but the code change looks trivially safer, so LGTM.

I'd like to improve the test case though:

1. Please minimize/edit to make it more obvious how this can cause a miscompile.
2. Add a comment to explain why the test exists (something similar to the code comment should do it).

This may not be minimal, and with the 'undefs' I don't think it can actually cause a miscompile, but I whittled it down this far to see what happens before and after the patch:

define void @widget() {
entry:
br label %bb2

bb2:
%t1 = phi i64 [ 0, %entry ], [ %t5, %bb7 ]
%t2 = add i64 %t1, 1
%t3 = icmp ult i64 0, %t2
br i1 %t3, label %bb3, label %bb4

bb3:
%t4 = call i64 @f()
br label %bb4

bb4:
; CHECK-NOT: phi {{.*}} undef
%foo = phi i64 [ %t4, %bb3 ], [ 0, %bb2 ]
br i1 undef, label %bb5, label %bb6

bb5:
br i1 true, label %bb7, label %bb7

bb6:
br i1 true, label %bb7, label %bb7

bb7:
%t5 = add i64 %t1, 1
br i1 undef, label %bb2, label %bb8

bb8:
ret void

}

[pcc]

Thanks for working on reducing the test case! I was able to eliminate the undefinedness in the branches using a function argument. I couldn't find a way to reduce it any further though.

lib/Transforms/Scalar/GVN.cpp

 //  3) Update the PHIs in DF(R) by replacing the operands corresponding to 
 //     dead blocks with "UndefVal" in an hope these PHIs will optimized away.
 //
 // Return true iff *NEW* dead code are found.
 bool GVN::processFoldableCondBr(BranchInst *BI) {
   if (!BI || BI->isUnconditional())
     return false;
 
+  // If a branch has two identical successors, we cannot declare either dead.
+  if (BI->getSuccessor(0) == BI->getSuccessor(1))
+    return false;
+
   ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
   if (!Cond)
     return false;
 
   BasicBlock *DeadRoot = Cond->getZExtValue() ? 
                          BI->getSuccessor(1) : BI->getSuccessor(0);
   if (DeadBlocks.count(DeadRoot))
     return false;

test/Transforms/GVN/br-identical.ll

+; RUN: opt -gvn -S -o - %s | FileCheck %s
+
+define void @widget() {
+bb21:
+  br label %bb22
+
+bb22:
+  %tmp = phi i64 [ 0, %bb21 ], [ %tmp75, %bb74 ]
+  %tmp24 = add i64 %tmp, 1
+  br i1 undef, label %bb27, label %bb59
+
+bb27:
+  %tmp28 = sub i64 %tmp24, 0
+  %tmp29 = icmp ult i64 0, %tmp28
+  br i1 %tmp29, label %bb30, label %bb55
+
+bb30:
+  br label %bb32
+
+bb32:
+  br i1 undef, label %bb38, label %bb32
+
+  %tmp35 = call i8* @f()
+  br label %bb36
+
+bb36:
+  br label %bb38
+
+bb38:
+  %tmp39 = phi i8* [ %tmp35, %bb36 ], [ null, %bb32 ]
+  %tmp40 = bitcast i8* %tmp39 to double*
+  br label %bb52
+
+bb52:
+  %tmp53 = getelementptr double, double* %tmp40
+  %tmp54 = ptrtoint double* %tmp53 to i64
+  br label %bb55
+
+bb55:
+  ; CHECK-NOT: phi {{.*}} undef
+  %1 = phi i64 [ %tmp54, %bb52 ], [ 0, %bb27 ]
+  br label %bb59
+
+bb59:
+  br i1 undef, label %bb73, label %bb72
+
+bb72:
+  br i1 true, label %bb74, label %bb74
+
+bb73:
+  br i1 true, label %bb74, label %bb74
+
+bb74:
+  %tmp75 = add i64 %tmp, 1
+  br i1 undef, label %bb22, label %bb77
+
+bb77:
+  ret void
+}
+
+declare i8* @f()