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

[SCEV] Remove newline after predicates in dump

update_analyze_test_checks.py will now insert check lines for
empty lines, which means that all the existing test coverage will
have a spurious change

[SCEV] Remove newline after predicates in dump

update_analyze_test_checks.py will now insert check lines for
empty lines, which means that all the existing test coverage will
have a spurious change to check for the newline after "Predicates:".

I don't think we actually want to have that newline, so drop it
before it gets into more test coverage.

show more ...

[IR] Remove zext and sext constant expressions (#71040)

Remove support for zext and sext constant expressions. All places
creating them have been removed beforehand, so this just removes the
APIs

[IR] Remove zext and sext constant expressions (#71040)

Remove support for zext and sext constant expressions. All places
creating them have been removed beforehand, so this just removes the
APIs and uses of these constant expressions in tests.

There is some additional cleanup that can be done on top of this, e.g.
we can remove the ZExtInst vs ZExtOperator footgun.

This is part of
https://discourse.llvm.org/t/rfc-remove-most-constant-expressions/63179.

show more ...

[IR] Require index width to be ule pointer width (#70015)

I don't think there is a use case for having an index type that is wider
than the pointer type, and I'm not entirely clear what semantics t

[IR] Require index width to be ule pointer width (#70015)

I don't think there is a use case for having an index type that is wider
than the pointer type, and I'm not entirely clear what semantics this
would even have.

Also clarify the GEP semantics to explicitly say how they interact with
the index type width.

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.

[ConstExpr] Don't create div/rem expressions

This removes creation of udiv/sdiv/urem/srem constant expressions,
in preparation for their removal. I've added a
ConstantExpr::isDesirableBinOp() predic

[ConstExpr] Don't create div/rem expressions

This removes creation of udiv/sdiv/urem/srem constant expressions,
in preparation for their removal. I've added a
ConstantExpr::isDesirableBinOp() predicate to determine whether
an expression should be created for a certain operator.

With this patch, div/rem expressions can still be created through
explicit IR/bitcode, forbidding them entirely will be the next step.

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

show more ...

[test][NewPM] Remove RUN lines using -analyze

Only tests in llvm/test/Analysis.

-analyze is legacy PM-specific.

This only touches files with `-passes`.

I looked through everything and made sure t

[test][NewPM] Remove RUN lines using -analyze

Only tests in llvm/test/Analysis.

-analyze is legacy PM-specific.

This only touches files with `-passes`.

I looked through everything and made sure that everything had a new PM equivalent.

Reviewed By: MaskRay

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

show more ...

[SCEV] Use both known bits and sign bits when computing range of SCEV unknowns

When computing a range for a SCEVUnknown, today we use computeKnownBits for unsigned ranges, and computeNumSignBots for

[SCEV] Use both known bits and sign bits when computing range of SCEV unknowns

When computing a range for a SCEVUnknown, today we use computeKnownBits for unsigned ranges, and computeNumSignBots for signed ranges. This means we miss opportunities to improve range results.

One common missed pattern is that we have a signed range of a value which CKB can determine is positive, but CNSB doesn't convey that information. The current range includes the negative part, and is thus double the size.

Per the removed comment, the original concern which delayed using both (after some code merging years back) was a compile time concern. CTMark results (provided by Nikita, thanks!) showed a geomean impact of about 0.1%. This doesn't seem large enough to avoid higher quality results.

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

show more ...

[ScalarEvolution] Remove unused check prefixes

[SCEV] Introduce SCEVPtrToIntExpr (PR46786)

And use it to model LLVM IR's `ptrtoint` cast.

This is essentially an alternative to D88806, but with no chance for
all the problems it caused due to hav

[SCEV] Introduce SCEVPtrToIntExpr (PR46786)

And use it to model LLVM IR's `ptrtoint` cast.

This is essentially an alternative to D88806, but with no chance for
all the problems it caused due to having the cast as implicit there.
(see rG7ee6c402474a2f5fd21c403e7529f97f6362fdb3)

As we've established by now, there are at least two reasons why we want this:
* It will allow SCEV to actually model the `ptrtoint` casts
and their operands, instead of treating them as `SCEVUnknown`
* It should help with initial problem of PR46786 - this should eventually allow us
to not loose pointer-ness of an expression in more cases

As discussed in [[ https://bugs.llvm.org/show_bug.cgi?id=46786 | PR46786 ]], in principle,
we could just extend `SCEVUnknown` with a `is ptrtoint` cast, because `ScalarEvolution::getPtrToIntExpr()`
should sink the cast as far down into the expression as possible,
so in the end we should always end up with `SCEVPtrToIntExpr` of `SCEVUnknown`.

But i think that it isn't the best solution, because it doesn't really matter
from memory consumption side - there probably won't be *that* many `SCEVPtrToIntExpr`s
for it to matter, and it allows for much better discoverability.

Reviewed By: mkazantsev

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

show more ...

[SCEV] Strength nowrap flags after constant folding

We should first try to constant fold the add expression and only
strengthen nowrap flags afterwards. This allows us to determine
stronger flags if

[SCEV] Strength nowrap flags after constant folding

We should first try to constant fold the add expression and only
strengthen nowrap flags afterwards. This allows us to determine
stronger flags if e.g. only two operands are left after constant
folding (and thus "guaranteed no wrap region" code applies) or the
resulting operands are non-negative and thus nsw->nuw strengthening
applies.

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(): 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 ...

[NFC][ScalarEvolution] Add tests with ptrtoint in constant context in loop

Reduced from the https://reviews.llvm.org/D88806#2325340