[llvm] Construct SmallVector with iterator ranges (NFC)

[SCEV] Simplify trunc to zero based on known bits

Let getTruncateExpr() short-circuit to zero when the value being truncated is
known to have at least as many trailing zeros as the target type.

Dif

[SCEV] Simplify trunc to zero based on known bits

Let getTruncateExpr() short-circuit to zero when the value being truncated is
known to have at least as many trailing zeros as the target type.

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

show more ...

[SCEV] recognize logical and/or pattern

This patch makes SCEV recognize 'select A, B, false' and 'select A, true, B'.
This is a performance improvement that will be helpful after unsound select -> a

[SCEV] recognize logical and/or pattern

This patch makes SCEV recognize 'select A, B, false' and 'select A, true, B'.
This is a performance improvement that will be helpful after unsound select -> and/or transformation is removed, as discussed in D93065.

SCEV's answers for the select form should be a bit more conservative than the equivalent `and A, B` / `or A, B`.
Take this example: https://alive2.llvm.org/ce/z/NsP9ue .
To check whether it is valid for SCEV's computeExitLimit to return min(n, m) as ExactNotTaken value, I put llvm.assume at tgt.
It fails because the exit limit becomes poison if n is zero and m is poison. This is problematic if e.g. the exit value of i is replaced with min(n, m).
If either n or m is constant, we can revive the analysis again. I added relevant tests and put alive2 links there.

If and is used instead, this is okay: https://alive2.llvm.org/ce/z/K9rbJk . Hence the existing analysis is sound.

Reviewed By: nikic

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

show more ...

[Analysis] Use llvm::append_range (NFC)

[Analysis, IR, CodeGen] Use llvm::erase_if (NFC)

[SCEV] Add missing type check into getRangeForAffineNoSelfWrappingAR

We make type widening without checking if it's needed. Bail if the max
iteration count is wider than AR's type.

[Analysis] Use is_contained (NFC)

Revert "Return "[SCEV] Use isBasicBlockEntryGuardedByCond in isLoopBackedgeGuardedByCond", 2nd try"

This reverts commit f690986f314fbf3f4b3ca9ec0b87b95166008dc1.

Compile time then and again...

Return "[SCEV] Use isBasicBlockEntryGuardedByCond in isLoopBackedgeGuardedByCond", 2nd try

Reverted because the compile time impact is still too high.

isKnownViaNonRecursiveReasoning is used twice,

Return "[SCEV] Use isBasicBlockEntryGuardedByCond in isLoopBackedgeGuardedByCond", 2nd try

Reverted because the compile time impact is still too high.

isKnownViaNonRecursiveReasoning is used twice, we can do it just once.

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

show more ...

Revert "[SCEV] Use isBasicBlockEntryGuardedByCond in isLoopBackedgeGuardedByCond"

This reverts commit 3d4c0460ec6040fc071e56dc113afd181294591e.

Compile time impact is still high. Need to understand

Revert "[SCEV] Use isBasicBlockEntryGuardedByCond in isLoopBackedgeGuardedByCond"

This reverts commit 3d4c0460ec6040fc071e56dc113afd181294591e.

Compile time impact is still high. Need to understand why.

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

show more ...

[SCEV] Use isBasicBlockEntryGuardedByCond in isLoopBackedgeGuardedByCond

Previously we tried to using isKnownPredicateAt, but it makes an
extra query to isKnownPredicate, which has negative impact o

[SCEV] Use isBasicBlockEntryGuardedByCond in isLoopBackedgeGuardedByCond

Previously we tried to using isKnownPredicateAt, but it makes an
extra query to isKnownPredicate, which has negative impact on compile
time. Let's try to use more lightweight isBasicBlockEntryGuardedByCond.

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

show more ...

Revert "[SCEV] Use isKnownPredicateAt in isLoopBackedgeGuardedByCond"

This reverts commit 14f2ad0e3cc54d5eb254b545a469e8ffdb62b119.

Reverting to investigate compile time drop.

Differential Revisio

Revert "[SCEV] Use isKnownPredicateAt in isLoopBackedgeGuardedByCond"

This reverts commit 14f2ad0e3cc54d5eb254b545a469e8ffdb62b119.

Reverting to investigate compile time drop.

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

show more ...

[SCEV] Use isKnownPredicateAt in isLoopBackedgeGuardedByCond

A piece of code in `isLoopBackedgeGuardedByCond` basically duplicates
the dominators traversal from `isBlockEntryGuardedByCond` called fr

[SCEV] Use isKnownPredicateAt in isLoopBackedgeGuardedByCond

A piece of code in `isLoopBackedgeGuardedByCond` basically duplicates
the dominators traversal from `isBlockEntryGuardedByCond` called from
`isKnownPredicateAt`, but it's less powerful because it does not give context
to `isImpliedCond`. This patch reuses the `isKnownPredicateAt `function there,
reducing the amount of code duplication and making it more powerful.

Differential Revision: https://reviews.llvm.org/D92152
Reviewed By: skatkov

show more ...

[IndVars] Use isLoopBackedgeGuardedByCond for last iteration check

Use more context to prove contextual facts about the last iteration. It is
only executed when the backedge is taken, so we can use

[IndVars] Use isLoopBackedgeGuardedByCond for last iteration check

Use more context to prove contextual facts about the last iteration. It is
only executed when the backedge is taken, so we can use `isLoopBackedgeGuardedByCond`
to make this check.

Differential Revision: https://reviews.llvm.org/D91535
Reviewed By: skatkov

show more ...

[SVE] Fix TypeSize warning in RuntimePointerChecking::insert

The TypeSize warning would occur because RuntimePointerChecking::insert
was not scalable vector aware. The fix is to use
ScalarEvolution:

[SVE] Fix TypeSize warning in RuntimePointerChecking::insert

The TypeSize warning would occur because RuntimePointerChecking::insert
was not scalable vector aware. The fix is to use
ScalarEvolution::getSizeOfExpr to grab the size of types.

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

show more ...

Revert "[SCEV] Generalize no-self-wrap check in isLoopInvariantExitCondDuringFirstIterations"

This reverts commit 7dcc8899174f44b7447bc48a9f2ff27f5458f8b7.

This patch introduced a logical error tha

Revert "[SCEV] Generalize no-self-wrap check in isLoopInvariantExitCondDuringFirstIterations"

This reverts commit 7dcc8899174f44b7447bc48a9f2ff27f5458f8b7.

This patch introduced a logical error that breaks whole logic of this analysis.
All checks we are making are supposed to be loop-independent, so that we could
safely remove the range check. The 'nw' fact is loop-dependent, so we can remove
the check basing on facts from this very check.

Motivating examples will follow-up.

show more ...

Revert "[NFC][SCEV] Generalize monotonicity check for full and limited iteration space"

This reverts commit 2734a9ebf4a31df0131acdfc739395a5e692c342.

This patch appeared to not be a NFC. It introdu

Revert "[NFC][SCEV] Generalize monotonicity check for full and limited iteration space"

This reverts commit 2734a9ebf4a31df0131acdfc739395a5e692c342.

This patch appeared to not be a NFC. It introduced an execution path where
monotonicity check on limited space started relying in existing nsw/nuw
flags, which is illegal. The motivating test will follow-up.

show more ...

[SCEV] Fix incorrect treatment of max taken count. PR48225

SCEV makes a logical mistake when handling EitherMayExit in
case when both conditions must be met to exit the loop. The
mistake looks like

[SCEV] Fix incorrect treatment of max taken count. PR48225

SCEV makes a logical mistake when handling EitherMayExit in
case when both conditions must be met to exit the loop. The
mistake looks like follows: "if condition `A` fails within at most `X` first
iterations, and `B` fails within at most `Y` first iterations, then `A & B`
fails at most within `min (X, Y)` first iterations". This is wrong, because
both of them must fail at the same time.

Simple example illustrating this is following: we have an IV with step 1,
condition `A` = "IV is even", condition `B` = "IV is odd". Both `A` and `B`
will fail within first two iterations. But it doesn't mean that both of them
will fail within first two first iterations at the same time, which would mean
that IV is neither even nor odd at the same time within first 2 iterations.

We can only do so for known exact BE counts, but not for max.

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

show more ...

[NFC] Reduce code duplication in binop processing in computeExitLimitFromCondCached

Handling of `and` and `or` vastly uses copy-paste. Factored out into
a helper function as preparation step for fur

[NFC] Reduce code duplication in binop processing in computeExitLimitFromCondCached

Handling of `and` and `or` vastly uses copy-paste. Factored out into
a helper function as preparation step for further fix (see PR48225).

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

show more ...

test commit for new client

[SCEV] Factor out part of wrap flag detection logic [NFC](try 2)

This is a cut down version of 1ec6e1 which was reverted due to a compile time issue. The key changes made from that patch: 1) only i

[SCEV] Factor out part of wrap flag detection logic [NFC](try 2)

This is a cut down version of 1ec6e1 which was reverted due to a compile time issue. The key changes made from that patch: 1) only infer the flags needed along each path, 2) be careful to preserve order of checks, and 3) avoid computing NW flags at all since we need to prove the stronger property (does not cross 0) in the caller anyways.

Assuming this doesn't trip regressions, I'm going to try weakening (1). My end objective is to move flag inference into addrec construction. If I can't weaken (1) without compile time impact, I'll have a problem.

show more ...

Revert "[SCEV] Factor out part of wrap flag detection logic [NFC-ish]"

This reverts commit 1ec6e1eb8a084bffae8a40236eb9925d8026dd07.

This change causes a significant compile-time regression:
https:

Revert "[SCEV] Factor out part of wrap flag detection logic [NFC-ish]"

This reverts commit 1ec6e1eb8a084bffae8a40236eb9925d8026dd07.

This change causes a significant compile-time regression:
https://llvm-compile-time-tracker.com/compare.php?from=dd0b8b94d0796bd895cc998dd163b4fbebceb0b8&to=1ec6e1eb8a084bffae8a40236eb9925d8026dd07&stat=instructions

I assume that this is due to the non-NFC part of the change, which
now performs expensive nowrap inference even for nowrap flags that
are not used by the particular code.

show more ...

[SCEV] Factor out part of wrap flag detection logic [NFC-ish]

In an effort to make code around flag determination more readable, and (possibly) prepare for a follow up change, factor out some of the

[SCEV] Factor out part of wrap flag detection logic [NFC-ish]

In an effort to make code around flag determination more readable, and (possibly) prepare for a follow up change, factor out some of the flag detection logic. In the process, reduce the number of locations we mutate wrap flags by a couple.

Note that this isn't NFC. The old code tried for NSW xor (NUW || NW). This is, two different paths computed different sets of wrap flags. The new code will try for all three. The result is that some expressions end up with a few extra flags set.

show more ...

[SCEV] Fix nsw flags for GEP expressions

The SCEV code for constructing GEP expressions currently assumes
that the addition of the base and all the offsets is nsw if the GEP
is inbounds. While the a

[SCEV] Fix nsw flags for GEP expressions

The SCEV code for constructing GEP expressions currently assumes
that the addition of the base and all the offsets is nsw if the GEP
is inbounds. While the addition of the offsets is indeed nsw, the
addition to the base address is not, as the base address is
interpreted as an unsigned value.

Fix the GEP expression code to not assume nsw for the base+offset
calculation. However, do assume nuw if we know that the offset is
non-negative. With this, we use the same behavior as the
construction of GEP addrecs does. (Modulo the fact that we
disregard SCEV unification, as the pre-existing FIXME points out).

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

show more ...

[NFC] Refactor loop-invariant getters to return Optional