[LVI][CVP] Make use of condition known at use

[nikic]

Summary

When an instruction is only used in a select or phi operand, we might be able to make use of additional information from the select/branch condition. For example in

%sub = call i16 @llvm.usub.sat.i16(i16 %x, i16 10)
%cmp = icmp uge i16 %x, 10
%sel = select i1 %cmp, i16 %sub, i16 42

the usub.sat is only used in a select where %x uge 10 is known to hold, so we can fold it based on that knowledge.

This addresses the regression reported at https://reviews.llvm.org/D140798#4039748, but also provides a solution to a recurring problem we've had, where we fail to make use of range information after a branch+phi has been converted into a select. Our current solution to this is to hope that IPSCCP can perform the fold before that happens, but handling this in LVI is a somewhat more general solution.

Currently we only make use of this for the willNotOverflow() fold, but I plan to adjust other folds to use the new API as well.

[TimNN]

Thanks a lot @nikic! I've verified that this unbreaks Rust's codegen test.

[spatel]

Seems like a nice improvement to me, but adding some more potential reviewers in case there are other opinions.

If the intent is to eventually call from other places, the most basic case would be something like this?

define i16 @sel_true_cond(i16 %x) {
  %cmp = icmp eq i16 %x, 10
  %sel = select i1 %cmp, i16 %x, i16 42   ; can replace %x with 10
  ret i16 %sel
}

If so, might want to adjust the test names because patterns with an overflow intrinsic are not the minimal case.

llvm/lib/Analysis/LazyValueInfo.cpp

1662

The meaning of this loop wasn't clear to me on first reading.

If the intent is to experiment with optimization power vs. compile-time, make this a cl::opt or give the limit a name like static const unsigned MaxUserRangesToIntersect?

[nikic]

In D141482#4044348, @spatel wrote:

Seems like a nice improvement to me, but adding some more potential reviewers in case there are other opinions.

If the intent is to eventually call from other places, the most basic case would be something like this?

define i16 @sel_true_cond(i16 %x) {
  %cmp = icmp eq i16 %x, 10
  %sel = select i1 %cmp, i16 %x, i16 42   ; can replace %x with 10
  ret i16 %sel
}

Basically yes, but CVP doesn't actually perform folds that simple (just replacing a value with a known constant), it's generally some kind of instruction simplification (we do this in InstCombine though, in foldSelectValueEquivalence).

[nikic]

Give magic constant 2 a name.

[StephenFan]

llvm/lib/Analysis/LazyValueInfo.cpp

1680

Is limiting the number of uses a consideration of compile-time? If we can give it a mutable limit and support handling multiple uses?

[nikic]

llvm/lib/Analysis/LazyValueInfo.cpp

1680

It's a correctness requirement for the current implementation. For multiple uses, we would have to intersect with the union of conditions at all uses. This is more complex, expensive and unlikely to be useful.

[spatel]

LGTM

llvm/lib/Analysis/LazyValueInfo.cpp

1680

Since there was a question about the hasOneUse(), it would be good to include that reasoning as a code comment.