cse or gvn should replace opposite icmp with xor by true

[llvmbot]

Bugzilla Link	27431
Version	trunk
OS	Linux
Reporter	LLVM Bugzilla Contributor
CC	@topperc,@hfinkel,@sanjoy,@rotateright

Extended Description

Reduced testcase:

; ModuleID = 'gvn-icmp.ll'
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

declare void @​use(i1)

define void @​fn1(i32 %A) {
entry:
%iszero = icmp eq i32 %A, 0
%isnotzero = icmp ne i32 %A, 0 ;; %isnotzero = xor i1 %iszero, true
tail call void @​use(i1 %iszero)
tail call void @​use(i1 %isnotzero)
ret void
}

Something in llvm should turn subsequent comparisons into nots of the original comparison to expose further correlations between values. In particular they should work across blocks, the right places for this might be early-cse and gvn.

Here's a larger C testcase, 77.c from Regehr's souper results:

int a;
char b;
int fn1() { return a && b || a && b; }

If I apply the proposed transformation by hand, it reduces from 12 instructions in 3 blocks down to a single block with load+load+icmp+icmp+and+zext+ret.

[rotateright]

This question came up in:
https://reviews.llvm.org/D32725

And I suggested extending the existing InstCombine canonicalization:
// xor (cmp A, B), true = not (cmp A, B) = !cmp A, B

We currently do this transform only when the cmp has one use, but I think it makes sense in general because we remove a dependency between the first icmp and its 'not' value by inverting the predicate.

But if that makes life harder for other passes, then that would be a reason to leave it as-is in InstCombine.

[rotateright]

I posted a question related to this example on the dev-list:
http://lists.llvm.org/pipermail/llvm-dev/2017-July/115398.html

[topperc]

Interestingly, this code compiles to a much shorter sequence when compiled as C++

int a;
char b;
int fn1() { return a && b || a && b; }

Seems to have something to do with 'b' being sign extended to i32 type before comparing with 0 under C++.

[topperc]

Oops I had that backwards, the C version has extra sign extend instructions.