search

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
http://llvm.org
Other
28.96k stars 11.94k forks source link

cse or gvn should replace opposite icmp with xor by true #27805

Open llvmbot opened 8 years ago

llvmbot commented 8 years ago
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.

topperc commented 7 years ago

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

topperc commented 7 years ago

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++.

rotateright commented 7 years ago

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

rotateright commented 7 years ago

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.