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

[IR] Add operator<< overload for CmpInst::Predicate (NFC)

I regularly try and fail to use this while debugging.

[SCEV] Use fallthoughs in predicate switch when collecting rewrites for loop guard (NFC)

[SCEV] Fix control flow warning (NFC)

[SCEV] Extract a helper to create a SCEV with new operands (NFC)

[SCEV] Remove an unnecessary switch (NFC)

Just the scevUnconditionallyPropagatesPoisonFromOperands() check
is sufficient. Also rename the flag to be more in line with the
more general predicate.

[ScalarEvolution] Factor out RewriteMap utilities in applyLoopGuards (NFC)

This factors out two utilities used with RewriteMap in applyLoopGuards:
- AddRewrite, which puts a rewrite rule in the map

[ScalarEvolution] Factor out RewriteMap utilities in applyLoopGuards (NFC)

This factors out two utilities used with RewriteMap in applyLoopGuards:
- AddRewrite, which puts a rewrite rule in the map and if needed registers
the rewrite in the list of rewritten expressions,
- GetMaybeRewritten, which checks whether an expression has already been
rewritten, and if so, returns the rewrite. Otherwise, returns the given
expression.

This may be needed when adding new rewrite rules as not to copy-paste this
code.

show more ...

Revert "Revert "[SCEV] Add SCEVType to represent `vscale`.""

Relanding after fixing Polly related build error.

This reverts commit 7b26dcae9eaf8cdcba7fef032fd83d060dffd4b4.

Revert "[SCEV] Add SCEVType to represent `vscale`."

This reverts commit 7912f5cc92f65ad0d3c705f3683a0b69dbedcc57.

[SCEV] Add SCEVType to represent `vscale`.

This is part of an effort to remove ConstantExpr based
representations of `vscale` so that its LangRef definiton can
be relaxed to accommodate a less stric

[SCEV] Add SCEVType to represent `vscale`.

This is part of an effort to remove ConstantExpr based
representations of `vscale` so that its LangRef definiton can
be relaxed to accommodate a less strict definition of constant.

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

show more ...

[SCEV] Hoist common cleanup code to function. (NFC)

This allows for easier updating of common code in follow-on patches.

Reviewed By: nikic

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

[SCEV] Make scalable size representation more explicit

Represent scalable type sizes using C * vscale, where vscale is
the vscale constant expression. This exposes a bit more information
to SCEV, be

[SCEV] Make scalable size representation more explicit

Represent scalable type sizes using C * vscale, where vscale is
the vscale constant expression. This exposes a bit more information
to SCEV, because the vscale multiplier is explicitly modeled in SCEV
(rather than part of the sizeof expression).

This is mainly intended as an alternative to D143642.

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

show more ...

[ScalarEvolution] Fix unused variable warnings. NFC.

Replace dyn_cast<> with isa<> as we don't actually need the variable

[SCEV] Ensure SCEV does not replace aliases with their aliasees

Passes in general shouldn't replace an alias with the aliasee (see
https://reviews.llvm.org/D66606). This can lead to situations where

[SCEV] Ensure SCEV does not replace aliases with their aliasees

Passes in general shouldn't replace an alias with the aliasee (see
https://reviews.llvm.org/D66606). This can lead to situations where a
linkonce_odr symbol (which could be interposable if lowered to weak
linkage) can be replaced with a local aliasee which won't be
interposable. SVEC does this when the function is invoked by
FunctionPass Manager -> Loop Pass Manager -> Induction Variable Users in
the codegen pipeline. This was found in hwasan instrumented code where a
linonce_odr alias was replaced with its private aliasee.

This fixes the bug descriped at
https://github.com/llvm/llvm-project/issues/60668.

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

show more ...

Revert "[SCEV] Preserve divisibility and min/max information in applyLoopGuards"

This reverts commit 219ba2fb7b0ae89101f3c81a47fe4fc4aa80dea4.

[SCEV] Preserve divisibility and min/max information in applyLoopGuards

applyLoopGuards doesn't always preserve information when there are multiple assumes.

This patch tries to deal with multiple a

[SCEV] Preserve divisibility and min/max information in applyLoopGuards

applyLoopGuards doesn't always preserve information when there are multiple assumes.

This patch tries to deal with multiple assumes regarding a SCEV's divisibility and min/max values, and rewrite it into a SCEV that still preserves all of the information.
For example, let the trip count of the loop be TC. Consider the 3 following assumes:

1. __builtin_assume(TC % 8 == 0);
2. __builtin_assume(TC > 0);
3. __builtin_assume(TC < 100);

Before this patch, depending on the assume processing order applyLoopGuards could create the following SCEV:
max(min((8 * (TC / 8)) , 99), 1)

Looking at this SCEV, it doesn't preserve the divisibility by 8 information.

After this patch, depending on the assume processing order applyLoopGuards could create the following SCEV:
max(min((8 * (TC / 8)) , 96), 8)

By aligning up 1 to 8, and aligning down 99 to 96, the new SCEV still preserves all of the original assumes.

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

show more ...

[SCEV] Remove unused alignof/offsetof print special cases (NFC)

These shouldn't really reach SCEV without being folded away first,
and we don't have any tests that hit these cases.

The sizeof case

[SCEV] Remove unused alignof/offsetof print special cases (NFC)

These shouldn't really reach SCEV without being folded away first,
and we don't have any tests that hit these cases.

The sizeof case does occur with scalable types.

show more ...

Revert "[AssumptionCache] caches @llvm.experimental.guard's"

This reverts commit f9599bbc7a3f831e1793a549d8a7a19265f3e504.

For some reason it caused us a huge compile time regression in downstream

Revert "[AssumptionCache] caches @llvm.experimental.guard's"

This reverts commit f9599bbc7a3f831e1793a549d8a7a19265f3e504.

For some reason it caused us a huge compile time regression in downstream
workloads. Not sure whether the source of it is in upstream code ir not.
Temporarily reverting until investigated.

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

show more ...

[SCEV] Canonicalize ext(min/max(x, y)) to min/max(ext(x), ext(y))

I stumbled over this while trying to improve our exit count work. These expressions
are equivalent for complementary signed/unsigned

[SCEV] Canonicalize ext(min/max(x, y)) to min/max(ext(x), ext(y))

I stumbled over this while trying to improve our exit count work. These expressions
are equivalent for complementary signed/unsigned ext and min/max (including umin_seq),
but they are not canonicalized and SCEV cannot recognize them as the same.

The benefit of this canonicalization is that SCEV can prove some new equivalences which
it coudln't prove because of different forms. There is 1 test where trip count seems pessimized,
I could not directly figure out why, but it just seems an unrelated issue that we can fix.
Other changes seem neutral or positive to me.

Differential Revision: https://reviews.llvm.org/D141481
Reviewed By: nikic

show more ...

[SCEV] Support umin/smin in SCEVLoopGuardRewriter

Adds support for these SCEVs to cover more cases.

Differential Revision: https://reviews.llvm.org/D143259
Reviewed By: dmakogon, fhahn

Use APInt::count{l,r}_{zero,one} (NFC)

[SCEV] Support sext in SCEVLoopGuardRewriter

There is no particular reason why it's not supported, and it is useful.

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

[SCEV][NFC] Remove check for rewriteable types

I guess its only reason to exist is potential CT optimization, otherwise it is
just creating cohesion between this code and rewriter internals. We plan

[SCEV][NFC] Remove check for rewriteable types

I guess its only reason to exist is potential CT optimization, otherwise it is
just creating cohesion between this code and rewriter internals. We plan to
extend the rewriter. I'd rather not have this cohesion, unless there is a serious
reason to have it.

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

show more ...

[SCEV] Use fact that B >u 0 for A <u B in applyLoopGuards.

If LHS <u RHS holds, RHS should be guaranteed to be > 0. By using
using 'umax(RHS, 1) -1' instead of 'RHS - 1' the results in
applyLoopGuar

[SCEV] Use fact that B >u 0 for A <u B in applyLoopGuards.

If LHS <u RHS holds, RHS should be guaranteed to be > 0. By using
using 'umax(RHS, 1) -1' instead of 'RHS - 1' the results in
applyLoopGuards can be improved in some cases.

Note that the TODO for the tests mentioned the max BTC being 11, but
unless I am missing something 10 should be correct.

https://alive2.llvm.org/ce/z/44nP7F

Reviewed By: mkazantsev

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

show more ...

[AssumptionCache] caches @llvm.experimental.guard's

As discussed in https://github.com/llvm/llvm-project/issues/59901

This change is not NFC. There is one SCEV and EarlyCSE test that have an
improv

[AssumptionCache] caches @llvm.experimental.guard's

As discussed in https://github.com/llvm/llvm-project/issues/59901

This change is not NFC. There is one SCEV and EarlyCSE test that have an
improved analysis/optimization case. Rest of the tests are not failing.

I've mostly only added cleanup to SCEV since that is where this issue
started. As a follow up, I believe there is more cleanup opportunity in
SCEV and other affected passes.

There could be cases where there are missed registerAssumption of
guards, but this case is not so bad because there will be no
miscompilation. AssumptionCacheTracker should take care of deleted
guards.

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

show more ...