[ScalarEvolution] Add bailout to avoid zext of pointer.

The RHS of an isImpliedCond call can be a pointer even if the LHS is
not. This is similar to bfa2a81e.

Not going to include a testcase; an IR

[ScalarEvolution] Add bailout to avoid zext of pointer.

The RHS of an isImpliedCond call can be a pointer even if the LHS is
not. This is similar to bfa2a81e.

Not going to include a testcase; an IR testcase would be extremely
complicated and fragile.

Fixes https://github.com/llvm/llvm-project/issues/51936 .

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

show more ...

[Analysis] Drop an unnecessary const from a return type (NFC)

Identified with readability-const-return-type.

[ScalarEvolution] Handle <= and >= in non infinite loops

Extend scalar evolution to handle >= and <= if a loop is known to be finite and the induction variable guards the condition. Specifically, wi

[ScalarEvolution] Handle <= and >= in non infinite loops

Extend scalar evolution to handle >= and <= if a loop is known to be finite and the induction variable guards the condition. Specifically, with these assumptions lhs <= rhs is equivalent to lhs < rhs + 1 and lhs >= rhs to lhs > rhs -1.

In the case of lhs <= rhs, this is true since the only case these are not equivalent
is when rhs == unsigned/signed intmax, which would have resulted in an infinite loop.

In the case of lhs >= rhs, this is true since the only case these are not equivalent
is when rhs == unsigned/signed intmin, which would again have resulted in an infinite loop.

Reviewed By: lebedev.ri

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

show more ...

[ScalarEvolution] Mark a loop as finite if in a willreturn function

A limited version of (https://reviews.llvm.org/D118090) that only marks a loop as finite if in a willreturn function.

Reviewed By

[ScalarEvolution] Mark a loop as finite if in a willreturn function

A limited version of (https://reviews.llvm.org/D118090) that only marks a loop as finite if in a willreturn function.

Reviewed By: jdoerfert

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

show more ...

[SCEV] Remove an unnecessary GEP type check

The code already checked that the addrec step size and type alloc
size are the same. The actual pointer element type is irrelevant
here.

[NFC] Remove uses of PointerType::getElementType()

Instead use either Type::getPointerElementType() or
Type::getNonOpaquePointerElementType().

This is part of D117885, in preparation for deprecatin

[NFC] Remove uses of PointerType::getElementType()

Instead use either Type::getPointerElementType() or
Type::getNonOpaquePointerElementType().

This is part of D117885, in preparation for deprecating the API.

show more ...

[SCEV] Use lshr in implications

This patch adds support for implication inference logic for the
following pattern:
```
lhs < (y >> z) <= y, y <= rhs --> lhs < rhs
```
We should be able to use the

[SCEV] Use lshr in implications

This patch adds support for implication inference logic for the
following pattern:
```
lhs < (y >> z) <= y, y <= rhs --> lhs < rhs
```
We should be able to use the fact that value shifted to right is
not greater than the original value (provided it is non-negative).

Differential Revision: https://reviews.llvm.org/D116150
Reviewed-By: apilipenko

show more ...

[Analysis] Remove a redundant const from a return type (NFC)

Identified with readability-const-return-type.

[NFC][SCEV] Introduce `getCastExpr()` QoL helper

[NFCI][SCEV] `computeExitLimitFromCondFromBinOp()`: rely on `getSequentialMinMaxExpr()` constant relaxation

`getSequentialMinMaxExpr()` has been taught to perform this relaxation,
so rely on that no

[NFCI][SCEV] `computeExitLimitFromCondFromBinOp()`: rely on `getSequentialMinMaxExpr()` constant relaxation

`getSequentialMinMaxExpr()` has been taught to perform this relaxation,
so rely on that now. Not sure this can be tested.

show more ...

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

Currently, `computeExitLimitFromCondFromBinOp()` does that directly.

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

[SCEV] `getSequentialMinMaxExpr()`: look into `umin` when deduplicating operands

We could just merge all umin into umin_seq, but that is likely
a pessimization, so don't do that, but pretend that we

[SCEV] `getSequentialMinMaxExpr()`: look into `umin` when deduplicating operands

We could just merge all umin into umin_seq, but that is likely
a pessimization, so don't do that, but pretend that we did
for the purpose of deduplication.

show more ...

[SCEV] `getSequentialMinMaxExpr()`: keep only the first instance of an operand

Having the same operand more than once doesn't change the outcome here,
neither reduction-wise nor poison-wise.
We must

[SCEV] `getSequentialMinMaxExpr()`: keep only the first instance of an operand

Having the same operand more than once doesn't change the outcome here,
neither reduction-wise nor poison-wise.
We must keep the first instance specifically though.

show more ...

[SCEV] Reenable umin_seq support and fix the `computeSCEVAtScope()`

This reverts commit f62f47f5e1f641b41d3b7d593c058ebec2883534.

Partial revert of 82fb4f4

Two crashes have been reported. This change disables the new logic while leaving the new node in tree. Hopefully, that's enough to allow investigation without breakage wh

Partial revert of 82fb4f4

Two crashes have been reported. This change disables the new logic while leaving the new node in tree. Hopefully, that's enough to allow investigation without breakage while avoiding massive churn.

show more ...

[SCEV] Sequential/in-order `UMin` expression

As discussed in https://github.com/llvm/llvm-project/issues/53020 / https://reviews.llvm.org/D116692,
SCEV is forbidden from reasoning about 'backedge ta

[SCEV] Sequential/in-order `UMin` expression

As discussed in https://github.com/llvm/llvm-project/issues/53020 / https://reviews.llvm.org/D116692,
SCEV is forbidden from reasoning about 'backedge taken count'
if the branch condition is a poison-safe logical operation,
which is conservatively correct, but is severely limiting.

Instead, we should have a way to express those
poison blocking properties in SCEV expressions.

The proposed semantics is:
```
Sequential/in-order min/max SCEV expressions are non-commutative variants
of commutative min/max SCEV expressions. If none of their operands
are poison, then they are functionally equivalent, otherwise,
if the operand that represents the saturation point* of given expression,
comes before the first poison operand, then the whole expression is not poison,
but is said saturation point.
```
* saturation point - the maximal/minimal possible integer value for the given type

The lowering is straight-forward:
```
compare each operand to the saturation point,
perform sequential in-order logical-or (poison-safe!) ordered reduction
over those checks, and if reduction returned true then return
saturation point else return the naive min/max reduction over the operands
```
https://alive2.llvm.org/ce/z/Q7jxvH (2 ops)
https://alive2.llvm.org/ce/z/QCRrhk (3 ops)
Note that we don't need to check the last operand: https://alive2.llvm.org/ce/z/abvHQS
Note that this is not commutative: https://alive2.llvm.org/ce/z/FK9e97

That allows us to handle the patterns in question.

Reviewed By: nikic, reames

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

show more ...

[NFCI] `ScalarEvolution::getRangeRef()`: collapse `SCEVMinMaxExpr` handling

[SCEV] Compute exit count from overflow check expressed w/ x.with.overflow intrinsics

This ports the logic we generate in instcombine for a single use x.with.overflow check for use in SCEV's analysi

[SCEV] Compute exit count from overflow check expressed w/ x.with.overflow intrinsics

This ports the logic we generate in instcombine for a single use x.with.overflow check for use in SCEV's analysis. The result is that we can prove trip counts for many checks, and (through existing logic) often discharge them.

Motivation comes from compiling a simple example with -ftrapv.

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

show more ...

[SCEV] Drop unused param from new version of computeExitLimitFromICmp [NFC]

[SCEV] Split computeExitLimitFromICmp into two versions [NFC]

This is in advance of a following change which needs to the non-icmp API.

[SCEV] Apply loop guards in reverse order.

This patch updates applyLoopGuards to first collect all conditions and
then applies them in reverse order. This ensures the SCEVs with the
shortest depende

[SCEV] Apply loop guards in reverse order.

This patch updates applyLoopGuards to first collect all conditions and
then applies them in reverse order. This ensures the SCEVs with the
shortest dependency chains are constructed first, limiting the required
stack size.

This fixes a crash reported in D113578.

Note that the order conditions are applied can impact the accuracy of
the result, mostly due to missing min/max simplifications when
constructing SCEVs.

The changed test highlights the impact of the evaluation order. I will
follow up with a SCEV patch to improve min/max simplifications to get
the same results for both orders.

show more ...

[SCEV] Fix unused variable warning (NFC)

[SCEV] Fix ValuesAtScopesUsers consistency

Fixes verification failure reported at:
https://reviews.llvm.org/rGc9f9be0381d1

The issue is that getSCEVAtScope() might compute a result without
insertin

[SCEV] Fix ValuesAtScopesUsers consistency

Fixes verification failure reported at:
https://reviews.llvm.org/rGc9f9be0381d1

The issue is that getSCEVAtScope() might compute a result without
inserting it in the ValuesAtScopes map in degenerate cases,
specifically if the ValuesAtScopes entry is invalidated during the
calculation. Arguably we should still insert the result if no
existing placeholder is found, but for now just tweak the logic
to only update ValuesAtScopesUsers if ValuesAtScopes is updated.

show more ...

[SCEV] Track backedge taken count users (NFCI)

Track which SCEVs are used as ExactNotTaken counts in
BackedgeTakenInfo structures, so we can directly determine which
loops need to be invalidated, ra

[SCEV] Track backedge taken count users (NFCI)

Track which SCEVs are used as ExactNotTaken counts in
BackedgeTakenInfo structures, so we can directly determine which
loops need to be invalidated, rather than iterating over all BECounts.

This gives a small compile-time improvement on average, but the
motivation here is more to ensure there are no degenerate cases,
if the number of backedge taken counts is large.

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

show more ...