[LLVMdev] RFC: canonical icmp predicates?

[Philip Reames]

I ran into an issue where we are missing optimization opportunities by 
not recognizing that:
$cmp1 = icmp eq i8* %p, null
br i1 %cmp1, label %is_null,  label %not_null

Is equivalent to:
$cmp1 = icmp ne i8* %p, null
br i1 %cmp1, label %not_null,  label %is_null

We do recognize and exploit this in GVN.  However, that leaves us with a 
pass ordering problem where other passes are less effective. The biggest 
impact in practice appears to be on jump threading (missed 
optimizations) and unswitching (wasted compile time unswitching 
conditions which are actually known outside the loop).

I can see two ways of approaching this and would value feedback about 
which is the right one.

Option 1 - We can teach EarlyCSE, & JumpThreading to specifically 
optimize this pattern.  This doesn't solve the general pass ordering 
problem, but it does give us far more chances to exploit the equivalent 
control flow for each run of the optimization pipeline (e.g. each round 
of inlining iteration).

Option 2 - We could teach InstCombine to canonicalize one form into the 
other.  On the surface, this seems like the "right" answer, but it also 
seems too easy.  I suspect there's a reason this approach hasn't been 
done and that I simply don't know what it is.  :)

The only thing I could come up with is that inverting the branch 
direction might perturb code placement for compilations without 
profiling data.  Is that the concern?

Philip