[SCEV][NFC] Cache symbolic max exit count

We want to have a caching version of symbolic BE exit count
rather than recompute it every time we need it.

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

[SCEV][NFC] Cache symbolic max exit count

We want to have a caching version of symbolic BE exit count
rather than recompute it every time we need it.

Differential Revision: https://reviews.llvm.org/D89954
Reviewed By: nikic, efriedma

show more ...

[SCEV][NFC] Simplify internals of BackedgeTakenInfo

[SCEV][NFC] Rename MaxAndComplete -> ConstantMaxAndComplete

This better reflects what this variable is about.

[SCEV][NFC] Rename getMax -> getConstantMax

This better reflects what this logic actually does.

Revert "[SCEV] Prove implications of different type via truncation"

This reverts commit 80852a4f2fb154c6094bb9d9e3457757d5a60ad1.

Test is now broken because underlying required patch was also rever

Revert "[SCEV] Prove implications of different type via truncation"

This reverts commit 80852a4f2fb154c6094bb9d9e3457757d5a60ad1.

Test is now broken because underlying required patch was also reverted SUDDENLY.

show more ...

[SCEV] Prove implications of different type via truncation

When we need to prove implication of expressions of different type width,
the default strategy is to widen everything to wider type and pro

[SCEV] Prove implications of different type via truncation

When we need to prove implication of expressions of different type width,
the default strategy is to widen everything to wider type and prove in this
type. This does not interact well with AddRecs with negative steps and
unsigned predicates: such AddRec will likely not have a `nuw` flag, and its
`zext` to wider type will not be an AddRec. In contraty, `trunc` of an AddRec
in some cases can easily be proved to be an `AddRec` too.

This patch introduces an alternative way to handling implications of different
type widths. If we can prove that wider type values actually fit in the narrow type,
we truncate them and prove the implication in narrow type.

Differential Revision: https://reviews.llvm.org/D89548
Reviewed By: fhahn

show more ...

Revert D89381 "[SCEV] Recommit "Use nw flag and symbolic iteration count to sharpen ranges of AddRecs", attempt 2"

This reverts commit a10a64e7e334dc878d281aba9a46f751fe606567.

It broke polly/test/

Revert D89381 "[SCEV] Recommit "Use nw flag and symbolic iteration count to sharpen ranges of AddRecs", attempt 2"

This reverts commit a10a64e7e334dc878d281aba9a46f751fe606567.

It broke polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll
The difference suggests that this may be a serious issue.

show more ...

[SCEV] Recommit "Use nw flag and symbolic iteration count to sharpen ranges of AddRecs", attempt 2

Fixed wrapping range case & proof methods reduced to constant range
checks to save compile time.

D

[SCEV] Recommit "Use nw flag and symbolic iteration count to sharpen ranges of AddRecs", attempt 2

Fixed wrapping range case & proof methods reduced to constant range
checks to save compile time.

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

show more ...

[NFCI][SCEV] Always refer to enum SCEVTypes as enum, not integer

The main tricky thing here is forward-declaring the enum:
we have to specify it's underlying data type.

In particular, this avoids t

[NFCI][SCEV] Always refer to enum SCEVTypes as enum, not integer

The main tricky thing here is forward-declaring the enum:
we have to specify it's underlying data type.

In particular, this avoids the danger of switching over the SCEVTypes,
but actually switching over an integer, and not being notified
when some case is not handled.

I have updated most of such switches to be exaustive and not have
a default case, where it's pretty obvious to be the intent,
however not all of them.

show more ...

[NFC][SCEV] BuildConstantFromSCEV(): reformat, NFC

Makes diff in next commit more readable

[NFC][SCEV] Rename SCEVCastExpr into SCEVIntegralCastExpr

All existing SCEV cast types operate on integers.
D89456 will add SCEVPtrToIntExpr cast expression type.
I believe this is best for consiste

[NFC][SCEV] Rename SCEVCastExpr into SCEVIntegralCastExpr

All existing SCEV cast types operate on integers.
D89456 will add SCEVPtrToIntExpr cast expression type.
I believe this is best for consistency.

Reviewed By: mkazantsev

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

show more ...

[NFC][SCEV] Use getMinusOne where possible

[SCEV] Model `ashr exact x, C` as `(abs(x) EXACT/u (1<<C)) * signum(x)`

It's not pretty, but probably better than modelling it
as an opaque SCEVUnknown, i guess.

It is relevant e.g. for the loop th

[SCEV] Model `ashr exact x, C` as `(abs(x) EXACT/u (1<<C)) * signum(x)`

It's not pretty, but probably better than modelling it
as an opaque SCEVUnknown, i guess.

It is relevant e.g. for the loop that was brought up in
https://bugs.llvm.org/show_bug.cgi?id=46786#c26
as an example of what we'd be able to better analyze
once SCEV handles `ptrtoint` (D89456).

But as it is evident, even if we deal with `ptrtoint` there,
we also fail to model such an `ashr`.
Also, modeling of mul-of-exact-shr/div could use improvement.

As per alive2:
https://alive2.llvm.org/ce/z/tnfZKd
```
define i8 @src(i8 %0) {
%2 = ashr exact i8 %0, 4
ret i8 %2
}

declare i8 @llvm.abs(i8, i1)
declare i8 @llvm.smin(i8, i8)
declare i8 @llvm.smax(i8, i8)

define i8 @tgt(i8 %x) {
%abs_x = call i8 @llvm.abs(i8 %x, i1 false)
%div = udiv exact i8 %abs_x, 16
%t0 = call i8 @llvm.smax(i8 %x, i8 -1)
%t1 = call i8 @llvm.smin(i8 %t0, i8 1)
%r = mul nsw i8 %div, %t1
ret i8 %r
}
```
Transformation seems to be correct!

show more ...

[NFC][SCEV] Refactor getAbsExpr() out of createSCEV()

[NFC][SCEV] Add 'getMinusOne()' method

Revert "Recommit "[SCEV] Use nw flag and symbolic iteration count to sharpen ranges of AddRecs""

This reverts commit 32b72c3165bf65cca2e8e6197b59eb4c4b60392a.

While better than before, this change

Revert "Recommit "[SCEV] Use nw flag and symbolic iteration count to sharpen ranges of AddRecs""

This reverts commit 32b72c3165bf65cca2e8e6197b59eb4c4b60392a.

While better than before, this change still introduces a large
compile-time regression (>3% on mafft):
https://llvm-compile-time-tracker.com/compare.php?from=fbd62fe60fb2281ca33da35dc25ca3c87ec0bb51&to=32b72c3165bf65cca2e8e6197b59eb4c4b60392a&stat=instructions

Additionally, the logic here doesn't look quite right to me,
I will comment in more detail on the differential revision.

show more ...

Recommit "[SCEV] Use nw flag and symbolic iteration count to sharpen ranges of AddRecs"

It was reverted because of negative compile time impact. In this version,
less powerful proof methods are used

Recommit "[SCEV] Use nw flag and symbolic iteration count to sharpen ranges of AddRecs"

It was reverted because of negative compile time impact. In this version,
less powerful proof methods are used (non-recursive reasoning only), and
scope limited to constant End values to avoid explision of complex proofs.

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

show more ...

Revert "[SCEV] Use nw flag and symbolic iteration count to sharpen ranges of AddRecs"

This reverts commit 905101c36025fe1c8ecdf9a20cd59db036676073.

This causes a large compile-time regression:
http

Revert "[SCEV] Use nw flag and symbolic iteration count to sharpen ranges of AddRecs"

This reverts commit 905101c36025fe1c8ecdf9a20cd59db036676073.

This causes a large compile-time regression:
https://llvm-compile-time-tracker.com/compare.php?from=cc175c2cc8e638462bab74e0781e06f9b6eb5017&to=905101c36025fe1c8ecdf9a20cd59db036676073&stat=instructions

show more ...

[SCEV][NFC] Split out type balancing in implication engine

We plan to introduce more advanced ways of dealing with different types.

[SCEV] Use nw flag and symbolic iteration count to sharpen ranges of AddRecs

We can sharpen the range of a AddRec if we know that it does not
self-wrap and know the symbolic iteration count in the l

[SCEV] Use nw flag and symbolic iteration count to sharpen ranges of AddRecs

We can sharpen the range of a AddRec if we know that it does not
self-wrap and know the symbolic iteration count in the loop. If we can
evaluate the value of AddRec on the last iteration and prove that at least
one its intermediate value lies between start and end, then no-wrap flag
allows us to conclude that all of them also lie between start and end. So
the estimate of range can be improved to union of ranges of start and end.

Differential Revision: https://reviews.llvm.org/D89381
Reviewed By: efriedma

show more ...

Revert "Reland "[SCEV] Model ptrtoint(SCEVUnknown) cast not as unknown, but as zext/trunc/self of SCEVUnknown"" and it's follow-ups

While we haven't encountered an earth-shattering problem with this

Revert "Reland "[SCEV] Model ptrtoint(SCEVUnknown) cast not as unknown, but as zext/trunc/self of SCEVUnknown"" and it's follow-ups

While we haven't encountered an earth-shattering problem with this yet,
by now it is pretty evident that trying to model the ptr->int cast
implicitly leads to having to update every single place that assumed
no such cast could be needed. That is of course the wrong approach.

Let's back this out, and re-attempt with some another approach,
possibly one originally suggested by Eli Friedman in
https://bugs.llvm.org/show_bug.cgi?id=46786#c20
which should hopefully spare us this pain and more.

This reverts commits 1fb610429308a7c29c5065f5cc35dcc3fd69c8b1,
7324616660fc0995fa8c166e3c392361222d5dbc,
aaafe350bb65dfc24c2cdad4839059ac81899fbe,
e92a8e0c743f83552fac37ecf21e625ba3a4b11e.

I've kept&improved the tests though.

show more ...

[SCEV] BuildConstantFromSCEV(): actually properly handle SExt-of-pointer case

As being pointed out by @efriedma in
https://reviews.llvm.org/rGaaafe350bb65#inline-4883
of course we can't just call pt

[SCEV] BuildConstantFromSCEV(): actually properly handle SExt-of-pointer case

As being pointed out by @efriedma in
https://reviews.llvm.org/rGaaafe350bb65#inline-4883
of course we can't just call ptrtoint in sign-extending case
and be done with it, because it will zero-extend.

I'm not sure what i was thinking there.

This is very much not an NFC, however looking at the user of
BuildConstantFromSCEV() i'm not sure how to actually show that
it results in a different constant expression.

show more ...

[SCEV] BuildConstantFromSCEV(): properly handle SCEVSignExtend from ptr

Much similar to the ZExt/Trunc handling.
Thanks goes to Alexander Richardson for nudging towards noticing this one proactively

[SCEV] BuildConstantFromSCEV(): properly handle SCEVSignExtend from ptr

Much similar to the ZExt/Trunc handling.
Thanks goes to Alexander Richardson for nudging towards noticing this one proactively.

The appropriate (currently crashing) test coverage added.

show more ...

[SCEV] BuildConstantFromSCEV(): properly handle SCEVZeroExtend from ptr

As being reported in https://reviews.llvm.org/D88806#2326944,
this is pretty much the sibling problem of https://reviews.llvm.

[SCEV] BuildConstantFromSCEV(): properly handle SCEVZeroExtend from ptr

As being reported in https://reviews.llvm.org/D88806#2326944,
this is pretty much the sibling problem of https://reviews.llvm.org/D88806#2325340,
with root cause being that SCEV now models `ptrtoint` as trunc/zext/self of unknown.

The appropriate (currently crashing) test coverage added.

show more ...

Reland "[SCEV] Model ptrtoint(SCEVUnknown) cast not as unknown, but as zext/trunc/self of SCEVUnknown"

This relands commit 1c021c64caef83cccb719c9bf0a2554faa6563af which was
reverted in commit 17cec

Reland "[SCEV] Model ptrtoint(SCEVUnknown) cast not as unknown, but as zext/trunc/self of SCEVUnknown"

This relands commit 1c021c64caef83cccb719c9bf0a2554faa6563af which was
reverted in commit 17cec6a11a12f815052d56a17ef738cf246a2d9a because
an assertion was being triggered, since `BuildConstantFromSCEV()`
wasn't updated to handle the case where the constant we want to truncate
is actually a pointer. I was unsuccessful in coming up with a test case
where we'd end there with constant zext/sext of a pointer,
so i didn't handle those cases there until there is a test case.

Original commit message:

While we indeed can't treat them as no-ops, i believe we can/should
do better than just modelling them as `unknown`. `inttoptr` story
is complicated, but for `ptrtoint`, it seems straight-forward
to model it just as a zext-or-trunc of unknown.

This may be important now that we track towards
making inttoptr/ptrtoint casts not no-op,
and towards preventing folding them into loads/etc
(see D88979/D88789/D88788)

Reviewed By: mkazantsev

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

show more ...