[SCEV] Extend type hint in analysis output to all backedge kinds

This extends the work from 7755c26 to all of the different backend
taken count kinds that we print for the scev analysis printer. As

[SCEV] Extend type hint in analysis output to all backedge kinds

This extends the work from 7755c26 to all of the different backend
taken count kinds that we print for the scev analysis printer. As
before, the goal is to cut down on confusion as i4 -1 is a very
different (unsigned) value from i32 -1.

show more ...

[SCEV] Print predicate backedge count only if new information available

When printing the result of SCEV's analysis, we can avoid printing
the predicated backedge taken count and the predicates if t

[SCEV] Print predicate backedge count only if new information available

When printing the result of SCEV's analysis, we can avoid printing
the predicated backedge taken count and the predicates if the predicates
are empty and no new information is provided. This helps to reduce the
verbosity of the output.

show more ...

[SCEV] Include type when printing constant max backedge taken count

When printing the result of the analysis, i8 -1 and i64 -1 are quite
different in terms of analysis quality. In a recent conversi

[SCEV] Include type when printing constant max backedge taken count

When printing the result of the analysis, i8 -1 and i64 -1 are quite
different in terms of analysis quality. In a recent conversion with
a new contributor, we ran into exactly this confusion.

Adding the type for constant scevs more globally seems worthwhile, but
introduces a much larger test diff. I'm splitting this off first since
it addresses the immediate need, and then going to do some further
changes to clarify a few related bits of analysis result output.

show more ...

[ValueTracking] Handle more integer intrinsics in `propagatesPoison` (#82749)

This patch extends `propagatesPoison` to handle more integer intrinsics.
It will turn more logical ands/ors into bitwis

[ValueTracking] Handle more integer intrinsics in `propagatesPoison` (#82749)

This patch extends `propagatesPoison` to handle more integer intrinsics.
It will turn more logical ands/ors into bitwise ands/ors.

See also https://reviews.llvm.org/D99671.

show more ...

[SCEV] Regenerate test checks (NFC)

There have been some minor but pervasive changes to the generated
CHECK lines, so regenerate all of them, to minimize future diffs.

[SCEV] Strengthen nowrap flags via ranges for ARs on construction.

At the moment, proveNoWrapViaConstantRanges is only used when creating
SCEV[Zero,Sign]ExtendExprs. We can get significant improveme

[SCEV] Strengthen nowrap flags via ranges for ARs on construction.

At the moment, proveNoWrapViaConstantRanges is only used when creating
SCEV[Zero,Sign]ExtendExprs. We can get significant improvements by
strengthening flags after creating the AddRec.

I'll also share a follow-up patch that removes the code to strengthen
flags when creating SCEV[Zero,Sign]ExtendExprs. Modifying AddRecs while
creating those can lead to surprising changes.

Compile-time looks neutral:
https://llvm-compile-time-tracker.com/compare.php?from=94676cf8a13c511a9acfc24ed53c98964a87bde3&to=aced434e8b103109104882776824c4136c90030d&stat=instructions:u

Reviewed By: mkazantsev, nikic

Differential Revision: https://reviews.llvm.org/D144050

show more ...

[ValueTracking] Consider single poison operands in propgatesPoison.

This patch updates propgatesPoison to take a Use as argument and
propagatesPoison now returns true if the passed in operand causes

[ValueTracking] Consider single poison operands in propgatesPoison.

This patch updates propgatesPoison to take a Use as argument and
propagatesPoison now returns true if the passed in operand causes the
user to yield poison if the operand is poison

This allows propagating poison if the condition of a select is poison.
This helps improve results for programUndefinedIfUndefOrPoison.

Reviewed By: nikic

Differential Revision: https://reviews.llvm.org/D111643

show more ...

[SCEV] Convert some tests to opaque pointers (NFC)

[SCEV] Add printout of symbolic max backedge-taken and block exit count

We do compute it and use in optimizations, but never print it out. We need
to do it in order to be able to track improvements

[SCEV] Add printout of symbolic max backedge-taken and block exit count

We do compute it and use in optimizations, but never print it out. We need
to do it in order to be able to track improvements in its computation.

show more ...

[SCEV] Rename max backedge-taken count -> constant max backedge taken-count in printout

This is a preparatory step for introducing symbolic max backedge-taken count.

[SCEV] Fold umin_seq using known predicate

Fold %x umin_seq %y to %x if %x ule %y. This also subsumes the
special handling for constant operands, as if %y is constant this
folds to umin via implied

[SCEV] Fold umin_seq using known predicate

Fold %x umin_seq %y to %x if %x ule %y. This also subsumes the
special handling for constant operands, as if %y is constant this
folds to umin via implied poison reasoning, and if %x is constant
then either %x is not zero and it folds to umin, or it is known
zero, in which case it is ule anything.

show more ...

[SCEV] Add more tests for umin_seq with known predicate (NFC)

[ScalarEvolution] Fold %x umin_seq %y if %x cannot be zero

Fold %x umin_seq %y to %x umin %y if %x cannot be zero. They only
differ in semantics for %x==0.

More generally %x *_seq %y folds to %x *

[ScalarEvolution] Fold %x umin_seq %y if %x cannot be zero

Fold %x umin_seq %y to %x umin %y if %x cannot be zero. They only
differ in semantics for %x==0.

More generally %x *_seq %y folds to %x * %y if %x cannot be the
saturation fold (though currently we only have umin_seq).

show more ...

[ScalarEvolution] Add tests for umin_seq with non-zero operand (NFC)

[SCEV] Fold umin_seq to umin using implied poison reasoning

Similar to how we convert logical and/or to bitwise and/or, we should
also convert umin_seq to umin based on implied poison reasoning. In

[SCEV] Fold umin_seq to umin using implied poison reasoning

Similar to how we convert logical and/or to bitwise and/or, we should
also convert umin_seq to umin based on implied poison reasoning. In
%x umin_seq %y, if %y being poison implies %x being poison, then we
don't need the sequential evaluation: Having %y contribute towards
the result will never make the result more poisonous. An important
corollary of this is that if %y is never poison, we also don't need
the sequential evaluation.

This avoids some of the regressions in D124910.

Differential Revision: https://reviews.llvm.org/D124921

show more ...

[SCEV] Add additional poison implication tests (NFC)

[SCEV] Add poison implication tests for umin_seq (NFC)

[SCEV] Recognize logical `or` as `not umin_seq (not, not)`

By definition, `umin_seq` has the exact same
poison stopping properties the original `select` had:
https://alive2.llvm.org/ce/z/MUfbTL

[SCEV] Recognize logical `and` as `umin_seq`

By definition, `umin_seq` has the exact same
poison stopping properties the original `select` had:
https://alive2.llvm.org/ce/z/59KuZZ

[SCEV] `getSequentialMinMaxExpr()`: relax 2-op umin_seq w/ constant to umin

Currently, `computeExitLimitFromCondFromBinOp()` does that directly.

[NFC][SCEV] Add test with umin_seq w/ 1op and constant

[SCEV] `getSequentialMinMaxExpr()`: rewrite deduplication to be fully recursive

Since we don't merge/expand non-sequential umin exprs into umin_seq exprs,
we may have umin_seq(umin(umin_seq())) chai

[SCEV] `getSequentialMinMaxExpr()`: rewrite deduplication to be fully recursive

Since we don't merge/expand non-sequential umin exprs into umin_seq exprs,
we may have umin_seq(umin(umin_seq())) chain, and the innermost umin_seq
can have duplicate operands still.

show more ...

[NFC][SCEV] Add test where it's the innermost umin_seq that has a duplicate operand

[SCEV] Don't consider umin_seq scev expr to be more complex that ptrtoint scev expr

Let's consider sequential min/max expression family
to be more complex than their non-sequential counterparts,
pre

[SCEV] Don't consider umin_seq scev expr to be more complex that ptrtoint scev expr

Let's consider sequential min/max expression family
to be more complex than their non-sequential counterparts,
preserving internal ordering within them.

show more ...

[NFC][SCEV] Add test for umin_seq complexity ordering