[SCEV] Use APIntOps::umin to select best max BC count (NFC).

Suggested in D102267, but I missed this in the committed version.

[DebugInfo][LSR] Add more stringent checks on IV selection and salvage
attempts

Prevent the selection of IVs that have a SCEV containing an undef. Also
prevent salvaging attempts for values for whic

[DebugInfo][LSR] Add more stringent checks on IV selection and salvage
attempts

Prevent the selection of IVs that have a SCEV containing an undef. Also
prevent salvaging attempts for values for which a SCEV could not be
created by ScalarEvolution and have only SCEVUknown.

Reviewed by: Orlando

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

show more ...

[llvm] Use llvm::reverse (NFC)

[SCEV] Use constant range of RHS to prove NUW on narrow IV in trip count logic

The basic idea here is that given a zero extended narrow IV, we can prove the inner IV to be NUW if we can prove there'

[SCEV] Use constant range of RHS to prove NUW on narrow IV in trip count logic

The basic idea here is that given a zero extended narrow IV, we can prove the inner IV to be NUW if we can prove there's a value the inner IV must take before overflow which must exit the loop.

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

show more ...

[ScalarEvolution] Infer loop max trip count from array accesses

Data references in a loop should not access elements over the
statically allocated size. So we can infer a loop max trip count
from th

[ScalarEvolution] Infer loop max trip count from array accesses

Data references in a loop should not access elements over the
statically allocated size. So we can infer a loop max trip count
from this undefined behavior.

Reviewed By: reames, mkazantsev, nikic

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

show more ...

[SCEV] Only add direct loop users (NFC)

It it now sufficient to track only direct addrec users of a loop,
and let the SCEVUsers mechanism track and invalidate transitive users.

Differential Revisio

[SCEV] Only add direct loop users (NFC)

It it now sufficient to track only direct addrec users of a loop,
and let the SCEVUsers mechanism track and invalidate transitive users.

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

show more ...

[SCEV][NFC] Factor out common API for getting unique operands of a SCEV

This function is used at least in 2 places, to it makes sense to make it separate.

Differential Revision: https://reviews.llv

[SCEV][NFC] Factor out common API for getting unique operands of a SCEV

This function is used at least in 2 places, to it makes sense to make it separate.

Differential Revision: https://reviews.llvm.org/D112516
Reviewed By: reames

show more ...

[SCEV] Invalidate user SCEVs along with operand SCEVs to avoid cache corruption

Following discussion in D110390, it seems that we are suffering from unability
to traverse users of a SCEV being inval

[SCEV] Invalidate user SCEVs along with operand SCEVs to avoid cache corruption

Following discussion in D110390, it seems that we are suffering from unability
to traverse users of a SCEV being invalidated. The result of that is that ScalarEvolution's
inner caches may store obsolete data about SCEVs even if their operands are
forgotten. It creates problems when we try to verify the contents of those caches.

It's also a frequent situation when messing with cache causes very sneaky and
hard-to-analyze bugs related to corruption of memory when dealing with cached
data. They are lurking there because ScalarEvolution's veirfication is not powerful
enough and misses many problematic cases. I plan to make SCEV's verification
much stricter in follow-ups, and this requires dangling-pointers-free caches.

This patch makes sure that, whenever we forget cached information for a SCEV,
we also forget it for all SCEVs that (transitively) use it.

This may have negative compile time impact. It's a sacrifice we are more
than willing to make to enforce correctness. We can also save some time by
reworking invokers of forgetMemoizedResults (maybe we can forget multiple
SCEVs with single query).

Differential Revision: https://reviews.llvm.org/D111533
Reviewed By: reames

show more ...

[SCEV][NFC] Verify intergity of SCEVUsers

Make sure that, for every living SCEV, we have all its direct
operand tracking it as their user.

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

[SCEV][NFC] Verify intergity of SCEVUsers

Make sure that, for every living SCEV, we have all its direct
operand tracking it as their user.

Differential Revision: https://reviews.llvm.org/D112402
Reviewed By: reames

show more ...

[SCEV] Move SCEVLostPoisonFlags() check into SCEVExpander

Always insert values into ExprValueMap, and instead skip using them
in SCEVExpander if poison-generating flags have been lost. This
ensures

[SCEV] Move SCEVLostPoisonFlags() check into SCEVExpander

Always insert values into ExprValueMap, and instead skip using them
in SCEVExpander if poison-generating flags have been lost. This
ensures that all values that are in ValueExprMap are also in
ExprValueMap, so we can use the latter to invalidate the former.

This change is probably not entirely NFC for the case where
originally the SCEV had no nowrap flags but they were inferred
later, in which case that would now allow reusing the existing
value for expansion.

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

show more ...

[SCEV] Fix a warning on an unused lambda capture

This patch fixes:

llvm/lib/Analysis/ScalarEvolution.cpp:12770:37: error: lambda
capture 'this' is not used [-Werror,-Wunused-lambda-capture]

[SCEV][NFC] Win some compile time from mass forgetMemoizedResults

Mass forgetMemoizedResults can be done more efficiently than bunch
of individual invocations of helper because we can traverse maps

[SCEV][NFC] Win some compile time from mass forgetMemoizedResults

Mass forgetMemoizedResults can be done more efficiently than bunch
of individual invocations of helper because we can traverse maps being
updated just once, rather than doing this for each invidivual SCEV.

Should be NFC and supposedly improves compile time.

Differential Revision: https://reviews.llvm.org/D112294
Reviewed By: reames

show more ...

[SCEV][NFC] Apply mass forgetMemoizedResults queries where possible

When forgetting multiple SCEVs, rather than doing this one by one, we can
instead use mass updates. We plan to make them more effi

[SCEV][NFC] Apply mass forgetMemoizedResults queries where possible

When forgetting multiple SCEVs, rather than doing this one by one, we can
instead use mass updates. We plan to make them more efficient than they
are now, potentially improving compile time.

Differential Revision: https://reviews.llvm.org/D111602
Reviewed By: reames

show more ...

[SCEV][NFC] Introduce API for mass forgetMemoizedResults query

This patch changes signature of forgetMemoizedResults to be able to work with
multiple SCEVs. Usage will come in follow-ups. We also pl

[SCEV][NFC] Introduce API for mass forgetMemoizedResults query

This patch changes signature of forgetMemoizedResults to be able to work with
multiple SCEVs. Usage will come in follow-ups. We also plan to optimize it in the
future to work faster than individual invalidation updates. Should not change
behavior in any sense.

Split-off from D111602.

Differential Revision: https://reviews.llvm.org/D112293
Reviewed By: reames

show more ...

[NFC][SCEV] Do not track users of SCEVConstants

Follow-up from D112295, suggested by Nikita: we can avoid tracking
users of SCEVConstants because dropping their cached info is unlikely
to give any n

[NFC][SCEV] Do not track users of SCEVConstants

Follow-up from D112295, suggested by Nikita: we can avoid tracking
users of SCEVConstants because dropping their cached info is unlikely
to give any new prospects for fact inference, and it should not introduce
any correctness problems.

show more ...

[SCEV][NFC] API for tracking of SCEV users

This patch introduces API that keeps track of SCEVs users of
another SCEVs, required to handle invalidations of users along
with operands that comes in fol

[SCEV][NFC] API for tracking of SCEV users

This patch introduces API that keeps track of SCEVs users of
another SCEVs, required to handle invalidations of users along
with operands that comes in follow-up patches.

Differential Revision: https://reviews.llvm.org/D112295
Reviewed By: reames

show more ...

[SCEV] Remove computeLoadConstantCompareExitLimit() (NFCI)

The functionality of this method is already covered by
computeExitCountExhaustively() in a more general fashion. It was
added at a time whe

[SCEV] Remove computeLoadConstantCompareExitLimit() (NFCI)

The functionality of this method is already covered by
computeExitCountExhaustively() in a more general fashion. It was
added at a time when exhaustive exit count calculation did not
support constant folding loads yet. I double checked that dropping
this code causes no binary changes in test-suite.

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

show more ...

[SCEV] Fix formatting error introduced by D112080

Accidentally pushed D112080 without this clang-format cleanup.

[SCEV] Avoid compile time explosion in ScalarEvolution::isImpliedCond

As seen in PR51869 the ScalarEvolution::isImpliedCond function might
end up spending lots of time when doing the isKnownPredicat

[SCEV] Avoid compile time explosion in ScalarEvolution::isImpliedCond

As seen in PR51869 the ScalarEvolution::isImpliedCond function might
end up spending lots of time when doing the isKnownPredicate checks.

Calling isKnownPredicate for example result in isKnownViaInduction
being called, which might result in isLoopBackedgeGuardedByCond being
called, and then we might get one or more new calls to isImpliedCond.
Even if the scenario described here isn't an infinite loop, using
some random generated C programs as input indicates that those
isKnownPredicate checks quite often returns true. On the other hand,
the third condition that needs to be fulfilled in order to "prove
implications via truncation", i.e. the isImpliedCondBalancedTypes
check, is rarely fulfilled.
I also made some similar experiments to look at how often we would
get the same result when using isKnownViaNonRecursiveReasoning instead
of isKnownPredicate. So far I haven't seen a single case when codegen
is negatively impacted by using isKnownViaNonRecursiveReasoning. On
the other hand, it seems like we get rid of the compile time explosion
seen in PR51869 that way. Hence this patch.

Reviewed By: nikic

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

show more ...

[SCEV] Prove implication of predicates to their sign-flipped counterparts

This patch teaches SCEV two implication rules:

x <u y && y >=s 0 --> x <s y,
x <s y && y <s 0 --> x <u y.

And all equi

[SCEV] Prove implication of predicates to their sign-flipped counterparts

This patch teaches SCEV two implication rules:

x <u y && y >=s 0 --> x <s y,
x <s y && y <s 0 --> x <u y.

And all equivalents with signs/parts swapped.

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

show more ...

[SCEV][NFC] Reduce memory footprint & compile time via DFS refactoring

Current implementations of DFS in SCEV check unique-visited of traversed
values on pop, and not on push. As result, the same va

[SCEV][NFC] Reduce memory footprint & compile time via DFS refactoring

Current implementations of DFS in SCEV check unique-visited of traversed
values on pop, and not on push. As result, the same value may be pushed
multiple times just to be thrown away when popped. These operations are
meaningless and only waste time and increase memory footprint of the
worklist.

This patch reworks the DFS strategy to check uniqueness before push.
Should be NFC.

Differential Revision: https://reviews.llvm.org/D111774
Reviewed By: nikic, reames

show more ...

[SCEV][NFC] Simplify check with CI->isZero() exit condition

Replace check with
if ((ExitIfTrue && CI->isZero()) || (!ExitIfTrue && CI->isOne()))
with equivalent and simpler version
if (ExitI

[SCEV][NFC] Simplify check with CI->isZero() exit condition

Replace check with
if ((ExitIfTrue && CI->isZero()) || (!ExitIfTrue && CI->isOne()))
with equivalent and simpler version
if (ExitIfTrue == CI->isZero())

show more ...

[SCEV][NFC] Reorder checks to delay call of all_of

Check lightweight getter condition before calling all_of.

[SCEV] Extend trip count to avoid overflow by default

As a brief reminder, an "exit count" is the number of times the backedge executes before some event. It can be zero if we exit before the backed

[SCEV] Extend trip count to avoid overflow by default

As a brief reminder, an "exit count" is the number of times the backedge executes before some event. It can be zero if we exit before the backedge is reached. A "trip count" is the number of times the loop header is entered if we branch into the loop. In general, TC = BTC + 1 and thus a zero trip count is ill defined

There is a cornercases which we don't handle well. Let's assume i8 for our examples to keep things simple. If BTC = 255, then the correct trip count is 256. However, 256 is not representable in i8.

In theory, code which needs to reason about trip counts is responsible for checking for this cornercase, and either bailing out, or handling it correctly. Historically, we don't have a great track record about actually doing so.

When reviewing D109676, I found myself asking a basic question. Was there any good reason to preserve the current wrap-to-zero behavior when converting from backedge taken counts to trip counts? After reviewing existing code, I could not find a single case which appears to correctly and precisely handle the overflow case.

This patch changes the default behavior to extend instead of wrap. That is, if the result might be 256, we return a value of i9 type to ensure we interpret the count correctly. I did leave the legacy behavior as an option since a) loop-flatten stops triggering if I extend due to weirdly specific pattern matching I didn't understand and b) we could reasonably use the mode if we'd externally established a lack of overflow.

I want to emphasize that this change is *not* NFC. There are two call sites (one in ScalarEvolution.cpp, one in LoopCacheAnalysis.cpp) which are switched to the extend semantics. The former appears imprecise (but correct) for a constant 255 BTC. The later appears incorrect, though I don't have a test case.

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

show more ...

Add iterator range variants of isGuaranteedToTransferExecutionToSuccessor [mostly-nfc]

This factors out utilities for scanning a bounded block of instructions since we have this code repeated in a b

Add iterator range variants of isGuaranteedToTransferExecutionToSuccessor [mostly-nfc]

This factors out utilities for scanning a bounded block of instructions since we have this code repeated in a bunch of places. The change to InlineFunction isn't strictly NFC as the limit mechanism there didn't handle debug instructions correctly.

show more ...