Fail to propagate assume to its negation

[llvmbot]

Bugzilla Link	30771
Version	trunk
OS	Linux
Blocks	#30343
Attachments	testcase
Reporter	LLVM Bugzilla Contributor
CC	@Bigcheese,@hfinkel,@RKSimon,@nikic,@rotateright

Extended Description

opt -O3 doesn't simplify this test.

If the two icmps are changed to use the same predicate (eq or ne), the function is simplified to return a constant.

[llvmbot]

So, I took a look at this.

There are 4 possibilities:

1. eq/eq

2. eq/ne

3. ne/eq

4. ne/ne

5. and 2) fold the whole function to ret i64 c where c is a constant (respectively 0 and 4).
   We don't quite need the whole power of -O3, in fact, all the work is done by EarlyCSE.

define i64 @​f(i64 %xxx, i64 %yyy) local_unnamed_addr #​0 {
foo:
ret i64 4
}

3. doesn't simplify the function at all, even at -O3

define i64 @​f(i64 %xxx, i64 %yyy) local_unnamed_addr #​0 {
foo:
%tmp18 = or i64 %yyy, %xxx
%tmp19 = icmp ne i64 %tmp18, 0
tail call void @​llvm.assume(i1 %tmp19)
%tmp22 = icmp eq i64 %tmp18, 0
%tmp23 = select i1 %tmp22, i64 0, i64 4
ret i64 %tmp23
}

4. We propagate the result down to ret, correctly. This happens at -O2 and beyond.
   I expected the first three instruction of the basic block being dead, so they could be removed. But they're not. This is because, I think, we treat assume specially.

Function Attrs: nounwind
define i64 @​f(i64 %xxx, i64 %yyy) local_unnamed_addr #​0 {
foo:
%tmp18 = or i64 %yyy, %xxx
%tmp19 = icmp ne i64 %tmp18, 0
tail call void @​llvm.assume(i1 %tmp19)
ret i64 0
}

We don't really care, because the backend doesn't care and generates the "best" code for this sequence:

$ ./opt -O3 assume.ll | ./llc
.text
.globl f
.p2align 4, 0x90
.type f,@function
f:
xorl %eax, %eax
retq

To sum up, there are two bugs:
3) needs to be analyzed further.
4) I think in this case it's safe to remove the three instructions before the ret. While this is not immediately relevant in this case, it could be indirectly (e.g. influence inlining etc...).

[Bigcheese]

Cases 1 and 2 are handled by SimplifyInstruction and computeKnownBitsFromAssume, but this can only deal with icmp eq, as with icmp ne we just know that at least some bit is set in either %xxx or %yyy.

Case 4 is handled by gvn as both icmps are the same and we have an assume in processAssumeIntrinsic.

Case 3 could be handled by gvn, as %tmp19 and %tmp22 are equivalent, but opposite, but that's probably not a useful thing for gvn to be doing.

I think the proper way to fix this is to make isKnownNonEqual and/or isKnownNonZero reason about assume.

[hfinkel]

I expected the first three instruction of the basic block being dead, so they
could be removed. But they're not. This is because, I think, we treat assume
specially.

We specifically don't remove them, so we still get the assumption if it is inlined. It should not affect the inlining cost, however. If you look at the inlining cost metric (and in several other places) we have a computation of 'ephemeral' instructions (see CodeMetrics::collectEphemeralValues and its callers), specifically to mitigate this issue.

Cases 1 and 2 are handled by SimplifyInstruction and
computeKnownBitsFromAssume, but this can only deal with icmp eq, as with
icmp ne we just know that at least some bit is set in either %xxx or %yyy.

Case 4 is handled by gvn as both icmps are the same and we have an assume in
processAssumeIntrinsic.

Case 3 could be handled by gvn, as %tmp19 and %tmp22 are equivalent, but
opposite, but that's probably not a useful thing for gvn to be doing.

I think the proper way to fix this is to make isKnownNonEqual and/or
isKnownNonZero reason about assume.

This makes sense to me; those two functions should know about assume.

[rotateright]

I forgot about this report and filed bug 31596, so we may want to mark that as a duplicate.

I think the proper way to fix this is to make isKnownNonEqual and/or
isKnownNonZero reason about assume.

I've been trying to chip away at assume-based optimizations as part of solving bug 28430, so this is partly addressed in:
https://reviews.llvm.org/D28204

There, I'm proposing that isKnownNonZero() calls isKnownNonNullAt() for pointers which calls isKnownNonNullFromDominatingCondition(), and there's a suggestion to have that look for llvm.assume.

[rotateright]

I didn't look at the testcase until now:

define i64 @​f(i64 %xxx, i64 %yyy) local_unnamed_addr #​0 {
foo:
%tmp18 = or i64 %yyy, %xxx
%tmp19 = icmp ne i64 %tmp18, 0
tail call void @​llvm.assume(i1 %tmp19)
%tmp22 = icmp eq i64 %tmp18, 0
%tmp23 = select i1 %tmp22, i64 0, i64 4
ret i64 %tmp23
}

; Function Attrs: nounwind
declare void @​llvm.assume(i1) #​0

---

This is related to bug 31512 by the existence of the 'select'; I've proposed an InstCombine (was an InstSimplify) patch to reach into computeKnownBitsFromAssume() for selects:
https://reviews.llvm.org/D28337

[RKSimon]

Is anything outstanding on this? D28337 landed over a year ago.

[rotateright]

Is anything outstanding on this? D28337 landed over a year ago.

That change wasn't enough to solve this case because the select's condition is not directly known via the assume.

Over in bug 31596, the verdict was to let newgvn handle this rather than adding to value tracking's computeKnownBitsFromAssume().

But newgvn kills the information that the assume was providing in this case without actually improving anything:

$ ./opt -newgvn 30771.ll -S
define i64 @​f(i64 %xxx, i64 %yyy) {
foo:
%tmp18 = or i64 %yyy, %xxx
%tmp19 = icmp ne i64 %tmp18, 0
tail call void @​llvm.assume(i1 true) ; ???
%tmp22 = icmp eq i64 %tmp18, 0
%tmp23 = select i1 %tmp22, i64 0, i64 4
ret i64 %tmp23
}

[nikic]

InstSimplify handles assume implications since recently, including for the test case.

A remaining oddity here is that NewGVN (while producing the correctly folded result, presumably via InstSimplify) converts the assume into an assume(true). I thought I fixed that...

[RKSimon]

mentioned in issue #30343

[nikic]

Looks like NewGVN no longer drops the assume (https://llvm.godbolt.org/z/c3a9zj3YP), so this issue should be fully resolved now.