[SCEV] Make getPostIncExpr guaranteed to return AddRec

The current implementation of `getPostIncExpr` invokes `getAddExpr` for two recurrencies
and expects that it always returns it a recurrency. Bu

[SCEV] Make getPostIncExpr guaranteed to return AddRec

The current implementation of `getPostIncExpr` invokes `getAddExpr` for two recurrencies
and expects that it always returns it a recurrency. But this is not guaranteed to happen if we
have reached max recursion depth or refused to make SCEV simplification for other reasons.

This patch changes its implementation so that now it always returns SCEVAddRec without
relying on `getAddExpr`.

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

llvm-svn: 324866

show more ...

Re-enable "[SCEV] Make isLoopEntryGuardedByCond a bit smarter"

The failures happened because of assert which was overconfident about
SCEV's proving capabilities and is generally not valid.

Differen

Re-enable "[SCEV] Make isLoopEntryGuardedByCond a bit smarter"

The failures happened because of assert which was overconfident about
SCEV's proving capabilities and is generally not valid.

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

llvm-svn: 324473

show more ...

Revert [SCEV] Make isLoopEntryGuardedByCond a bit smarter

Revert rL324453 commit which causes buildbot failures.

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

llvm-svn: 324462

[SCEV] Make isLoopEntryGuardedByCond a bit smarter

Sometimes `isLoopEntryGuardedByCond` cannot prove predicate `a > b` directly.
But it is a common situation when `a >= b` is known from ranges and `

[SCEV] Make isLoopEntryGuardedByCond a bit smarter

Sometimes `isLoopEntryGuardedByCond` cannot prove predicate `a > b` directly.
But it is a common situation when `a >= b` is known from ranges and `a != b` is
known from a dominating condition. Thia patch teaches SCEV to sum these facts
together and prove strict comparison via non-strict one.

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

llvm-svn: 324453

show more ...

Re-apply [SCEV] Fix isLoopEntryGuardedByCond usage

ScalarEvolution::isKnownPredicate invokes isLoopEntryGuardedByCond without check
that SCEV is available at entry point of the loop. It is incorrect

Re-apply [SCEV] Fix isLoopEntryGuardedByCond usage

ScalarEvolution::isKnownPredicate invokes isLoopEntryGuardedByCond without check
that SCEV is available at entry point of the loop. It is incorrect and fixed by patch.

To bugs additionally fixed:
assert is moved after the check whether loop is not a nullptr.
Usage of isLoopEntryGuardedByCond in ScalarEvolution::isImpliedCondOperandsViaNoOverflow
is guarded by isAvailableAtLoopEntry.

Reviewers: sanjoy, mkazantsev, anna, dorit, reames
Reviewed By: mkazantsev
Subscribers: llvm-commits
Differential Revision: https://reviews.llvm.org/D42417

llvm-svn: 324204

show more ...

Revert [SCEV] Fix isLoopEntryGuardedByCond usage

It causes buildbot failures. New added assert is fired.
It seems not all usages of isLoopEntryGuardedByCond are fixed.

llvm-svn: 323079

[SCEV] Fix isLoopEntryGuardedByCond usage

ScalarEvolution::isKnownPredicate invokes isLoopEntryGuardedByCond without check
that SCEV is available at entry point of the loop. It is incorrect and fixe

[SCEV] Fix isLoopEntryGuardedByCond usage

ScalarEvolution::isKnownPredicate invokes isLoopEntryGuardedByCond without check
that SCEV is available at entry point of the loop. It is incorrect and fixed by patch.

Reviewers: sanjoy, mkazantsev, anna, dorit
Reviewed By: mkazantsev
Subscribers: llvm-commits
Differential Revision: https://reviews.llvm.org/D42165

llvm-svn: 323077

show more ...

[SCEV] Do not cache S -> V if S is not equivalent of V

SCEV tracks the correspondence of created SCEV to original instruction.
However during creation of SCEV it is possible that nuw/nsw/exact flags

[SCEV] Do not cache S -> V if S is not equivalent of V

SCEV tracks the correspondence of created SCEV to original instruction.
However during creation of SCEV it is possible that nuw/nsw/exact flags are
lost.

As a result during expansion of the SCEV the instruction with nuw/nsw/exact
will be used where it was expected and we produce poison incorreclty.

Reviewers: sanjoy, mkazantsev, sebpop, jbhateja
Reviewed By: sanjoy
Subscribers: llvm-commits
Differential Revision: https://reviews.llvm.org/D41578

llvm-svn: 322058

show more ...

Use phi ranges to simplify code. No functionality change intended.

llvm-svn: 321585

[SCEV] Missing depth propagation in recursive call

llvm-svn: 321550

[SCEV] Do not insert if it is already in cache

This is fix for the crash caused by ScalarEvolution::getTruncateExpr.

It expects that if it checked the condition that SCEV is not in UniqueSCEVs cach

[SCEV] Do not insert if it is already in cache

This is fix for the crash caused by ScalarEvolution::getTruncateExpr.

It expects that if it checked the condition that SCEV is not in UniqueSCEVs cache in
the beginning that it will not be there inside this method.

However during recursion and transformation/simplification for sub expression,
it is possible that these modifications will end up with the same SCEV as we started from.

So we must always check whether SCEV is in cache and do not insert item if it is already there.

Reviewers: sanjoy, mkazantsev, craig.topper
Reviewed By: sanjoy
Subscribers: llvm-commits
Differential Revision: https://reviews.llvm.org/D41380

llvm-svn: 321472

show more ...

Silence a bunch of implicit fallthrough warnings

llvm-svn: 321114

[LV] Support efficient vectorization of an induction with redundant casts

D30041 extended SCEVPredicateRewriter to improve handling of Phi nodes whose
update chain involves casts; PSCEV can now buil

[LV] Support efficient vectorization of an induction with redundant casts

D30041 extended SCEVPredicateRewriter to improve handling of Phi nodes whose
update chain involves casts; PSCEV can now build an AddRecurrence for some
forms of such phi nodes, under the proper runtime overflow test. This means
that we can identify such phi nodes as an induction, and the loop-vectorizer
can now vectorize such inductions, however inefficiently. The vectorizer
doesn't know that it can ignore the casts, and so it vectorizes them.

This patch records the casts in the InductionDescriptor, so that they could
be marked to be ignored for cost calculation (we use VecValuesToIgnore for
that) and ignored for vectorization/widening/scalarization (i.e. treated as
TriviallyDead).

In addition to marking all these casts to be ignored, we also need to make
sure that each cast is mapped to the right vector value in the vector loop body
(be it a widened, vectorized, or scalarized induction). So whenever an
induction phi is mapped to a vector value (during vectorization/widening/
scalarization), we also map the respective cast instruction (if exists) to that
vector value. (If the phi-update sequence of an induction involves more than one
cast, then the above mapping to vector value is relevant only for the last cast
of the sequence as we allow only the "last cast" to be used outside the
induction update chain itself).

This is the last step in addressing PR30654.

llvm-svn: 320672

show more ...

[SCEV] Fix wrong Equal predicate created in getAddRecForPhiWithCasts

CreateAddRecFromPHIWithCastsImpl() adds an IncrementNUSW overflow predicate
which allows the PSCEV rewriter to rewrite this scev

[SCEV] Fix wrong Equal predicate created in getAddRecForPhiWithCasts

CreateAddRecFromPHIWithCastsImpl() adds an IncrementNUSW overflow predicate
which allows the PSCEV rewriter to rewrite this scev expression:
(zext i8 {0, + , (trunc i32 step to i8)} to i32)
into
{0, +, (sext i8 (trunc i32 step to i8) to i32)}

But then it adds the wrong Equal predicate:
%step == (zext i8 (trunc i32 %step to i8) to i32).
instead of:
%step == (sext i8 (trunc i32 %step to i8) to i32)

This is fixed here.

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

llvm-svn: 320298

show more ...

[NFC] Rename variable from Cond to Pred to make it more sound

llvm-svn: 320144

[SCEV] Fix predicate usage in computeExitLimitFromICmp

In this method, we invoke `SimplifyICmpOperands` which takes the `Cond` predicate
by reference and may change it along with `LHS` and `RHS` SCE

[SCEV] Fix predicate usage in computeExitLimitFromICmp

In this method, we invoke `SimplifyICmpOperands` which takes the `Cond` predicate
by reference and may change it along with `LHS` and `RHS` SCEVs. But then we invoke
`computeShiftCompareExitLimit` with Values from which the SCEVs have been derived,
these Values have not been modified while `Cond` could be.

One of possible outcomes of this is that we may falsely prove that an infinite loop ends
within some finite number of iterations.

In this patch, we save the original `Cond` and pass it along with original operands.
This logic may be removed in future once `computeShiftCompareExitLimit` works
with SCEVs instead of value operands.

Reviewed By: sanjoy
Differential Revision: https://reviews.llvm.org/D40953

llvm-svn: 320142

show more ...

[SCEV][NFC] Check NoWrap flags before lexicographical comparison of SCEVs

Lexicographical comparison of SCEV trees is potentially expensive for big
expression trees. We can define ordering between t

[SCEV][NFC] Check NoWrap flags before lexicographical comparison of SCEVs

Lexicographical comparison of SCEV trees is potentially expensive for big
expression trees. We can define ordering between them for AddRecs and
N-ary operations by SCEV NoWrap flags to make non-equality check
cheaper.

This change does not prevent grouping eqivalent SCEVs together and is
not supposed to have any meaningful impact on behavior of any transforms.


Reviewed By: sanjoy
Differential Revision: https://reviews.llvm.org/D40645

llvm-svn: 319889

show more ...

[SCEV][NFC] Share value cache between SCEVs in GroupByComplexity

Current implementation of `compareSCEVComplexity` is being unreasonable with `SCEVUnknown`s:
every time it sees one, it creates a new

[SCEV][NFC] Share value cache between SCEVs in GroupByComplexity

Current implementation of `compareSCEVComplexity` is being unreasonable with `SCEVUnknown`s:
every time it sees one, it creates a new value cache and tries to prove equality of two values using it.
This cache reallocates and gets lost from SCEV to SCEV.

This patch changes this behavior: now we create one cache for all values and share it between SCEVs.

Reviewed By: sanjoy
Differential Revision: https://reviews.llvm.org/D40597

llvm-svn: 319880

show more ...

[SCEV] Use a "Discovered" set instead of a "Visited" set; NFC

Suggested by Max Kazantsev in https://reviews.llvm.org/D39361

llvm-svn: 319679

[SCEV] A different fix for PR33494

Summary:
I don't think rL309080 is the right fix for PR33494 -- caching ExitLimit only
hides the problem[0]. The real issue is that because of how we forget SCEV

[SCEV] A different fix for PR33494

Summary:
I don't think rL309080 is the right fix for PR33494 -- caching ExitLimit only
hides the problem[0]. The real issue is that because of how we forget SCEV
expressions ScalarEvolution::getBackedgeTakenInfo, in the test case for PR33494
computing the backedge for any loop invalidates the trip count for every other
loop. This effectively makes the SCEV cache useless.

I've instead made the SCEV expression invalidation in
ScalarEvolution::getBackedgeTakenInfo less aggressive to fix this issue.

[0]: One way to think about this is that rL309080 essentially augmented the
backedge-taken-count cache with another equivalent exit-limit cache. The bug
went away because we were explicitly not clearing the exit-limit cache in
getBackedgeTakenInfo. But instead of doing all of that, we can just avoid
clearing the backedge-taken-count cache.

Reviewers: mkazantsev, mzolotukhin

Subscribers: mcrosier, llvm-commits

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

llvm-svn: 319678

show more ...

Mark all library options as hidden.

These command line options are not intended for public use, and often
don't even make sense in the context of a particular tool anyway. About
90% of them are alre

Mark all library options as hidden.

These command line options are not intended for public use, and often
don't even make sense in the context of a particular tool anyway. About
90% of them are already hidden, but when people add new options they
forget to hide them, so if you were to make a brand new tool today, link
against one of LLVM's libraries, and run tool -help you would get a
bunch of junk that doesn't make sense for the tool you're writing.

This patch hides these options. The real solution is to not have
libraries defining command line options, but that's a much larger effort
and not something I'm prepared to take on.

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

llvm-svn: 319505

show more ...

[SCEV][NFC] Remove condition that can never happen due to check few lines above

llvm-svn: 319293

[SCEV][NFC] More efficient caching in CompareValueComplexity

Currently, we use a set of pairs to cache responces like `CompareValueComplexity(X, Y) == 0`. If we had
proved that `CompareValueComplexi

[SCEV][NFC] More efficient caching in CompareValueComplexity

Currently, we use a set of pairs to cache responces like `CompareValueComplexity(X, Y) == 0`. If we had
proved that `CompareValueComplexity(S1, S2) == 0` and `CompareValueComplexity(S2, S3) == 0`,
this cache does not allow us to prove that `CompareValueComplexity(S1, S3)` is also `0`.

This patch replaces this set with `EquivalenceClasses` that merges Values into equivalence sets so that
any two values from the same set are equal from point of `CompareValueComplexity`. This, in particular,
allows us to prove the fact from example above.

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

llvm-svn: 319153

show more ...

[SCEV][NFC] More efficient caching in CompareSCEVComplexity

Currently, we use a set of pairs to cache responces like `CompareSCEVComplexity(X, Y) == 0`. If we had
proved that `CompareSCEVComplexity(

[SCEV][NFC] More efficient caching in CompareSCEVComplexity

Currently, we use a set of pairs to cache responces like `CompareSCEVComplexity(X, Y) == 0`. If we had
proved that `CompareSCEVComplexity(S1, S2) == 0` and `CompareSCEVComplexity(S2, S3) == 0`,
this cache does not allow us to prove that `CompareSCEVComplexity(S1, S3)` is also `0`.

This patch replaces this set with `EquivalenceClasses` any two values from the same set are equal from
point of `CompareSCEVComplexity`. This, in particular, allows us to prove the fact from example above.

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

llvm-svn: 319149

show more ...

[SCEV] Adding a check on outgoing branches of a terminator instr for SCEVBackedgeConditionFolder, NFC.

Summary:
For a given loop, getLoopLatch returns a non-null value
when a loop has only one latch

[SCEV] Adding a check on outgoing branches of a terminator instr for SCEVBackedgeConditionFolder, NFC.

Summary:
For a given loop, getLoopLatch returns a non-null value
when a loop has only one latch block. In the modified
context adding an assertion to check that both the outgoing branches of
a terminator instruction (of latch) does not target same header.
+
few minor code reorganization.

Reviewers: jbhateja

Reviewed By: jbhateja

Subscribers: sanjoy

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

llvm-svn: 318997

show more ...