This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Fold icmp (select c,const,arg), null if icmp arg, null can be simplified
ClosedPublic

Authored by aqjune on Feb 14 2021, 5:17 AM.

Details

Summary

This patch folds icmp (select c,const,arg), null if icmp arg, null can be simplified.

Resolves llvm.org/pr48975.

Diff Detail

Event Timeline

aqjune created this revision.Feb 14 2021, 5:17 AM
aqjune requested review of this revision.Feb 14 2021, 5:17 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 14 2021, 5:17 AM

SimplifyCFG adds llvm.assume for “cond”, we should do it here as well.

ojeda added a subscriber: ojeda.Feb 14 2021, 8:10 PM

SimplifyCFG adds llvm.assume for “cond”, we should do it here as well.

It seems SimplifyCFG is introducing llvm.assume to preserve information after removing a conditional branch.
In this case, the nonnull attribute is still there, so it might be okay to do the transformation without introducing assume IMO. What do you think?

SimplifyCFG adds llvm.assume for “cond”, we should do it here as well.

It seems SimplifyCFG is introducing llvm.assume to preserve information after removing a conditional branch.
In this case, the nonnull attribute is still there, so it might be okay to do the transformation without introducing assume IMO. What do you think?

But when we remove select, we can remove condition too (if trivially dead) - so maybe worth to preserve info that cond must be true/false?

aqjune updated this revision to Diff 325167.Feb 20 2021, 12:05 AM

It sounds like a good idea, I updated the patch to insert assume(cond).

I think this is allowed only when nonnull is accompanied with noundef attribute:
llvm.assume(cond) immediately raises UB whereas passing null to nonnull is equivalent
to passing poison; noundef is needed for this according to LangRef.

Yes, thanks. LG.

Other reviewers?

nikic added a comment.Feb 20 2021, 2:44 AM

I don't think this should be creating assumptions. It's pretty common for InstCombine transforms to lose some information while making folds, and we currently don't have any other InstCombine folds that try to preserve information through assumptions. Unless there is something specific to this transform that makes this particularly worthwhile, we should not deviate from the general pattern.

I think we can say that this is conceptually equivalent to SimplifyCFG that removes a conditional branch, and SimplifyCFG inserts an assumption when removing a condition (test9_null_callsite at llvm/test/Transforms/SimplifyCFG/UnreachableEliminate.ll), so this transformation is also chosen to insert assume.
To speak generally, we can say that control flow information is preserved using assume in InstCombine, and the scheme should be consistent with what SimplifyCFG says.
But would it be a big change though?

^ Yes, this is exactly what I had in my mind too.

The code duplication suggests that we should have a common place for this logic (especially if it already exists in SimplifyCFG).
Could it be added to ValueTracking's isKnownNonZero() or wrap around that?
It might already be in there under isKnownNonNullFromDominatingCondition(), but we need to fix it up to deal with selects?

The code duplication suggests that we should have a common place for this logic (especially if it already exists in SimplifyCFG).
Could it be added to ValueTracking's isKnownNonZero() or wrap around that?
It might already be in there under isKnownNonNullFromDominatingCondition(), but we need to fix it up to deal with selects?

Hmm, as you said, adding the "assume((select cond, null, p) != null)" pattern to isKnownNonZeroFromAssume seems enough?
Compiling the Rust code snippet from pr48975 already creates llvm.assume: https://godbolt.org/z/8KxWKP
That being said, it might be a good idea to update passingValueIsAlwaysUndefined to check CB->paramHasAttr(ArgIdx, Attribute::Dereferenceable) as well because dereferenceable is quite common. dereferenceable implies noundef, so it is valid to assume that passing null to nonnull dereferenceable is UB. What do you think?

The code duplication suggests that we should have a common place for this logic (especially if it already exists in SimplifyCFG).
Could it be added to ValueTracking's isKnownNonZero() or wrap around that?
It might already be in there under isKnownNonNullFromDominatingCondition(), but we need to fix it up to deal with selects?

Hmm, as you said, adding the "assume((select cond, null, p) != null)" pattern to isKnownNonZeroFromAssume seems enough?
Compiling the Rust code snippet from pr48975 already creates llvm.assume: https://godbolt.org/z/8KxWKP
That being said, it might be a good idea to update passingValueIsAlwaysUndefined to check CB->paramHasAttr(ArgIdx, Attribute::Dereferenceable) as well because dereferenceable is quite common. dereferenceable implies noundef, so it is valid to assume that passing null to nonnull dereferenceable is UB. What do you think?

If we can make the value tracking analysis better without adding or relying on llvm.assume, that would be best. I'm not sure about the current thinking on assume intrinsics, but we had found cases where the extra instructions/uses were interfering with optimization rather than helping. We've also seen cases like https://llvm.org/PR49171 where the cost of analyzing assumes is extreme. Not sure if those problems are overcome by assume bundles:
https://llvm.org/docs/LangRef.html#assume-operand-bundles

ATM I don't have a clear idea about how to implement it in ValueTracking without relying on assume..

BTW, before diving into ValueTracking's update, I made D97244 to make SimplifyCFG slightly stronger. As @ojeda mentioned in the bug report, dereferenceable implies noundef, and the attribute is pretty common, so I think it is a good idea to update this first and see how it goes.
@ojeda Is it possible to compile Rust using a custom LLVM build? Then, maybe I can play with this a bit.

ojeda added a comment.Feb 22 2021, 9:29 PM

Is it possible to compile Rust using a custom LLVM build?

Yeah, it is, although currently it is based on LLVM 11. For LLVM 12 support, take a look at https://github.com/rust-lang/rust/pull/81451. For LLVM 13, you probably need further tweaks.

When you configure Rust for building, use options like:

[llvm]
download-ci-llvm = false
skip-rebuild = true

[target.x86_64-unknown-linux-gnu]
llvm-config = "../your-custom-llvm-build/bin/llvm-config"

In general, take a look at config.toml.example, with src/bootstrap/defaults/config.codegen.toml as a start.

The guide is at https://rustc-dev-guide.rust-lang.org/building/how-to-build-and-run.html

aqjune updated this revision to Diff 325981.Feb 23 2021, 9:59 PM

Make foldICmpInstWithConstantNotInt fold (select cond, null, arg) == null if arg has nonnullattr instead

aqjune updated this revision to Diff 325982.Feb 23 2021, 10:02 PM

Add a negative test

aqjune retitled this revision from [InstCombine] Fold nonnull (select c,null,p) to nonnull p to [InstCombine] Fold icmp (select c,const,arg), null if arg has nonnullattr.Feb 23 2021, 10:05 PM
aqjune edited the summary of this revision. (Show Details)
ojeda added inline comments.Feb 23 2021, 10:12 PM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3299

Instead of adding two transformations, I tweaked InstCombinerImpl::foldICmpInstWithConstantNotInt so it fires if icmp is comparing to null and select's true/false operands are either a constant or nonnullattr argument.
It allows:

  %.0.i = select i1 %2, i8* null, i8* %x
  %4 = icmp ne i8* %.0.i, null
  call void @llvm.assume(i1 %4)
  ret i8* %.0.1
=>
  %.0.i = select i1 %2, i8* null, i8* %x
  %temp = xor i1 %2, 1
  call void @llvm.assume(i1 %temp)
  ret i8* %.0.1
=>  
  ...
  ret i8* %x

BTW, fixing SimplifyCFG to replace phi operand with null doesn't work for the Rust example because phi is already folded into select before inlining. It roughly looks like this: https://godbolt.org/z/c38qon

aqjune marked an inline comment as done.Feb 23 2021, 10:17 PM
aqjune added inline comments.Feb 23 2021, 10:23 PM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3332

To support example_negative, this needed to be relaxed; I chose a safer direction that would less cause possible performance issues.

The code duplication suggests that we should have a common place for this logic (especially if it already exists in SimplifyCFG).
Could it be added to ValueTracking's isKnownNonZero() or wrap around that?
It might already be in there under isKnownNonNullFromDominatingCondition(), but we need to fix it up to deal with selects?

I dont think this could be unified so easily.

Make foldICmpInstWithConstantNotInt fold (select cond, null, arg) == null if arg has nonnullattr instead

But original fold was more powerful and general IMHO.

Make foldICmpInstWithConstantNotInt fold (select cond, null, arg) == null if arg has nonnullattr instead

But original fold was more powerful and general IMHO.

I think it is hard to tell which version is more general - the previous patch was explicitly relying on uses that have nonnull attributes whereas the new one relies on assume calls.
This patch has more power if there are many assume calls.

RKSimon resigned from this revision.Mar 1 2021, 4:15 AM
aqjune added a comment.Mar 1 2021, 6:20 AM

Ping - I think this approach is a good direction to fix the bug without increasing the depth of uses to search.

xbolva00 accepted this revision.Apr 24 2021, 4:33 AM

Ping - I think this approach is a good direction to fix the bug without increasing the depth of uses to search.

Yes. I think this is ready to go and already sits here for a long time. Wait a day for additional comments if any.

This revision is now accepted and ready to land.Apr 24 2021, 4:33 AM
nikic added inline comments.Apr 24 2021, 8:16 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3265

As this is already on InstCombinerImpl, is the Q argument necessary?

llvm/test/Transforms/InstCombine/assume-icmp-null-select.ll
21

I find the presence of assume in this example a bit confusing, as your transform does not actually use information from the assume. I'd replace it with a more generic "use".

nikic added inline comments.Apr 24 2021, 8:50 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3301

I don't really like this non-null attr specific case. I would suggest to simply always use SimplifyICmpInst for the isNullValue() case (and add a test for some non-attribute example).

I checked that doing so doesn't have any visible impact on CTMark (https://llvm-compile-time-tracker.com/compare.php?from=7baa2392fba0193c3e6631376c8e6a3c0318a743&to=45c227240929d8139da3dbee517e03d706555f23&stat=instructions).

aqjune updated this revision to Diff 350275.Jun 7 2021, 7:00 AM

Address comments

aqjune marked 2 inline comments as done.Jun 7 2021, 7:09 AM
aqjune added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3265

Removed it, thanks

llvm/test/Transforms/InstCombine/assume-icmp-null-select.ll
21

llvm.assume is necessary because it tells that %y_is_null is false, helping ret i8* %res to be transformed into ret i8* %x.

The series of transformations looks like this:

(1) InstCombine visits %nonnull = icmp ne i8* %res, null
(2) foldICmpInstWithConstantNotInt looks into the definition of %res which is select i1 %y_is_null, i8* null, i8* %x and folds %nonnull into select i1 %y_is_null, false, true.
During this folding, %x's dereferenceable tag is used by ValueTracking to answer isNonNull query.
(3) The llvm.assume now tells that %y_is_null is false, allowing the ret i8* %res to be transformed into ret i8* %x.

aqjune marked an inline comment as done.Jun 7 2021, 7:09 AM
aqjune retitled this revision from [InstCombine] Fold icmp (select c,const,arg), null if arg has nonnullattr to [InstCombine] Fold icmp (select c,const,arg), null if icmp arg, null can be simplified.
aqjune edited the summary of this revision. (Show Details)

ping

As suggested, the argument's nonnull check is fixed to use SimplifyICmpInst instead
May I land this patch?

nikic accepted this revision.Jun 21 2021, 12:40 AM

LGTM