dominator optimizer/gvn fails to recognize identical tests

[echristo]

Bugzilla Link	3921
Resolution	FIXED
Resolved on	Apr 03, 2009 19:18
Version	trunk
OS	All
CC	@lattner

Extended Description

Here's a simple testcase that shows the problem:

extern int a;

int foo (void)
{
if (a == 4) { return 5; }
if (a == 5) { return 4; }
if (a == 4) { return 5 + a; }
if (a == 5) { return 4 + a; }

return a;
}

and the corresponding llvm code (from llvm-gcc -O2):

define i32 @​foo() nounwind readonly ssp {
entry:
%0 = load i32* @​a, align 4 ; [#uses=5]
%1 = icmp eq i32 %0, 4 ; [#uses=2]
br i1 %1, label %bb8, label %bb1

bb1: ; preds = %entry
%2 = icmp eq i32 %0, 5 ; [#uses=2]
br i1 %2, label %bb8, label %bb3

bb3: ; preds = %bb1
br i1 %1, label %bb4, label %bb5

bb4: ; preds = %bb3
%3 = add i32 %0, 5 ; [#uses=1]
ret i32 %3

bb5: ; preds = %bb3
br i1 %2, label %bb6, label %bb8

bb6: ; preds = %bb5
%4 = add i32 %0, 4 ; [#uses=1]
ret i32 %4

bb8: ; preds = %bb5, %bb1, %entry
%.0 = phi i32 [ 5, %entry ], [ 4, %bb1 ], [ %0, %bb5 ] ; [#uses=1]
ret i32 %.0
}

[lattner]

Owen, can this be easily handled in GVN? I'm thinking of something like:

if we see a cond branch on an i1 value with that is not ->hasOneUse(), add an equivalence to the next BB's table that says the i1 is true or false, depending on the edge.

Since GVN often eliminates the redundant conditions, this would let it turn the dominated branches into a branch on constant.

[llvmbot]

I can add it, but it seems like other optzns should be picking this up. Why isn't CondPropagate or SCCP getting this?

[lattner]

Neither follow the dom tree.

[llvmbot]

This is fixed in r68172.

Note that GVN doesn't handle his case very generally, since it's not a constant propagator. For instance, if you pass in the IR Eric posted, the GVN will not be able to simplify it. If you start from the original IR, where it re-does the comparison, then it will successfully simplify it.

[lattner]

nice!

[echristo]

Works for me. Excellent.