[SCEV] Make computeExitLimit more simple and more powerful

Current implementation of `computeExitLimit` has a big piece of code
the only purpose of which is to prove that after the execution of this

[SCEV] Make computeExitLimit more simple and more powerful

Current implementation of `computeExitLimit` has a big piece of code
the only purpose of which is to prove that after the execution of this
block the latch will be executed. What it currently checks is actually a
subset of situations where the exiting block dominates latch.

This patch replaces all these checks for simple particular cases with
domination check over loop's latch which is the only necessary condition
of taking the exiting block into consideration. This change allows to
calculate exact loop taken count for simple loops like

for (int i = 0; i < 100; i++) {
if (cond) {...} else {...}
if (i > 50) break;
. . .
}

Differential Revision: https://reviews.llvm.org/D44677
Reviewed By: efriedma

llvm-svn: 329047

show more ...

[Analysis] Change std::sort to llvm::sort in response to r327219

Summary:
r327219 added wrappers to std::sort which randomly shuffle the container before sorting.
This will help in uncovering non-de

[Analysis] Change std::sort to llvm::sort in response to r327219

Summary:
r327219 added wrappers to std::sort which randomly shuffle the container before sorting.
This will help in uncovering non-determinism caused due to undefined sorting
order of objects having the same key.

To make use of that infrastructure we need to invoke llvm::sort instead of std::sort.

Note: This patch is one of a series of patches to replace *all* std::sort to llvm::sort.
Refer D44363 for a list of all the required patches.

Reviewers: sanjoy, dexonsmith, hfinkel, RKSimon

Reviewed By: dexonsmith

Subscribers: david2050, llvm-commits

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

llvm-svn: 328925

show more ...

[NFC] Fix meaningless assert in SCEV

llvm-svn: 328764

[NFC] Fix comments in getExact()

llvm-svn: 328612

[SCEV] Make exact taken count calculation more optimistic

Currently, `getExact` fails if it sees two exit counts in different blocks. There is
no solid reason to do so, given that we only calculate

[SCEV] Make exact taken count calculation more optimistic

Currently, `getExact` fails if it sees two exit counts in different blocks. There is
no solid reason to do so, given that we only calculate exact non-taken count
for exiting blocks that dominate latch. Using this fact, we can simply take min
out of all exits of all blocks to get the exact taken count.

This patch makes the calculation more optimistic with enforcing our assumption
with asserts. It allows us to calculate exact backedge taken count in trivial loops
like

for (int i = 0; i < 100; i++) {
if (i > 50) break;
. . .
}

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

llvm-svn: 328611

show more ...

[SCEV] Add one more case in computeConstantDifference

This patch teaches `computeConstantDifference` handle calculation of constant
difference between `(X + C1)` and `(X + C2)` which is `(C2 - C1)`.

[SCEV] Add one more case in computeConstantDifference

This patch teaches `computeConstantDifference` handle calculation of constant
difference between `(X + C1)` and `(X + C2)` which is `(C2 - C1)`.

Differential Revision: https://reviews.llvm.org/D43759
Reviewed By: anna

llvm-svn: 328609

show more ...

Revert r325687 (workaround for PR36032).

Summary:
Revert r325687 workaround for PR36032 since
a fix was committed in r326154.

Reviewers: sbaranga

Differential Revision: http://reviews.llvm.org/D4

Revert r325687 (workaround for PR36032).

Summary:
Revert r325687 workaround for PR36032 since
a fix was committed in r326154.

Reviewers: sbaranga

Differential Revision: http://reviews.llvm.org/D44768

From: Evgeny Stupachenko <evstupac@gmail.com>
<evgeny.v.stupachenko@intel.com>
llvm-svn: 328257

show more ...

[SCEV] Factor out isKnownViaInduction. NFC.

This just extracts the isKnownViaInduction from isKnownPredicate.

Reviewers: sanjoy, mkazantsev, reames
Reviewed By: mkazantsev
Subscribers: llvm-commits

[SCEV] Factor out isKnownViaInduction. NFC.

This just extracts the isKnownViaInduction from isKnownPredicate.

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

llvm-svn: 327824

show more ...

[SCEV] Re-land: Fix isKnownPredicate

This is re-land of https://reviews.llvm.org/rL327362 with a fix
and regression test.

The crash was due to it is possible that for found MDL loop,
LHS or RHS may

[SCEV] Re-land: Fix isKnownPredicate

This is re-land of https://reviews.llvm.org/rL327362 with a fix
and regression test.

The crash was due to it is possible that for found MDL loop,
LHS or RHS may contain an invariant unknown SCEV which
does not dominate the MDL. Please see regression
test for an example.

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

llvm-svn: 327822

show more ...

[NFC] Void variables used for asserts only

llvm-svn: 327693

[SCEV][NFC] Remove TBB, FBB parameters from exit limit computations

Methods `computeExitLimitFromCondCached` and `computeExitLimitFromCondImpl` take
true and false branches as parameters and only us

[SCEV][NFC] Remove TBB, FBB parameters from exit limit computations

Methods `computeExitLimitFromCondCached` and `computeExitLimitFromCondImpl` take
true and false branches as parameters and only use them for asserts and for identifying
whether true/false branch belongs to the loop (which can be done once earlier). This fact
complicates generalization of exit limit computation logic on guards because the guards
don't have blocks to which they go in case of failure explicitly.

The motivation of this patch is that currently this part of SCEV knows nothing about guards
and only works with explicit branches. As result, it fails to prove that a loop

for (i = 0; i < 100; i++)
guard(i < 10);

exits after 10th iteration, while in the equivalent example

for (i = 0; i < 100; i++)
if (i >= 10) break;

SCEV easily proves this fact. We are going to change it in near future, and this is why
we need to make these methods operate on more abstract level.

This patch refactors this code to get rid of these parameters as meaningless and prepare
ground for teaching these methods to work with guards as well as they work with explicit
branching instructions.

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

llvm-svn: 327615

show more ...

[SCEV][NFC] Smarter implementation of isAvailableAtLoopEntry

isAvailableAtLoopEntry duplicates logic of `properlyDominates` after checking invariance.
This patch replaces this logic with invocation

[SCEV][NFC] Smarter implementation of isAvailableAtLoopEntry

isAvailableAtLoopEntry duplicates logic of `properlyDominates` after checking invariance.
This patch replaces this logic with invocation of this method which is more profitable
because it supports caching.

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

llvm-svn: 327373

show more ...

Revert [SCEV] Fix isKnownPredicate

It is a revert of rL327362 which causes build bot failures with assert like

Assertion `isAvailableAtLoopEntry(RHS, L) && "RHS is not available at Loop Entry"' fai

Revert [SCEV] Fix isKnownPredicate

It is a revert of rL327362 which causes build bot failures with assert like

Assertion `isAvailableAtLoopEntry(RHS, L) && "RHS is not available at Loop Entry"' failed.

llvm-svn: 327363

show more ...

[SCEV] Fix isKnownPredicate

IsKnownPredicate is updated to implement the following algorithm
proposed by @sanjoy and @mkazantsev :
isKnownPredicate(Pred, LHS, RHS) {
Collect set S all loops on whi

[SCEV] Fix isKnownPredicate

IsKnownPredicate is updated to implement the following algorithm
proposed by @sanjoy and @mkazantsev :
isKnownPredicate(Pred, LHS, RHS) {
Collect set S all loops on which either LHS or RHS depend.
If S is non-empty
a. Let PD be the element of S which is dominated by all other elements of S
b. Let E(LHS) be value of LHS on entry of PD.
To get E(LHS), we should just take LHS and replace all AddRecs that
are attached to PD on with their entry values.
Define E(RHS) in the same way.
c. Let B(LHS) be value of L on backedge of PD.
To get B(LHS), we should just take LHS and replace all AddRecs that
are attached to PD on with their backedge values.
Define B(RHS) in the same way.
d. Note that E(LHS) and E(RHS) are automatically available on entry of PD,
so we can assert on that.
e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) &&
isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
Return true if Pred, L, R is known from ranges, splitting etc.
}
This is follow-up for https://reviews.llvm.org/D42417.

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

llvm-svn: 327362

show more ...

[SCEV] Smart range calculation for SCEVUnknown Phis

The range of SCEVUnknown Phi which merges values `X1, X2, ..., XN`
can be evaluated as `U(Range(X1), Range(X2), ..., Range(XN))`.

Reviewed By: sa

[SCEV] Smart range calculation for SCEVUnknown Phis

The range of SCEVUnknown Phi which merges values `X1, X2, ..., XN`
can be evaluated as `U(Range(X1), Range(X2), ..., Range(XN))`.

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

llvm-svn: 326418

show more ...

[SCEV] Cleanup SCEVInitRewriter. NFC.

Set default value for IgnoreOtherLoops of SCEVInitRewriter::rewrite to true
to be consistent with SCEVPostIncRewriter which does not have this parameter
but beh

[SCEV] Cleanup SCEVInitRewriter. NFC.

Set default value for IgnoreOtherLoops of SCEVInitRewriter::rewrite to true
to be consistent with SCEVPostIncRewriter which does not have this parameter
but behaves as it would be true.

This is follow up for rL326067.

llvm-svn: 326174

show more ...

Fix PR36032, PR35432

Summary:

The change fix an assert fail at ScalarEvolutionExpander.cpp:
assert(ExitCount != SE.getCouldNotCompute() && "Invalid loop count");

Reviewers: sbaranga

Differentia

Fix PR36032, PR35432

Summary:

The change fix an assert fail at ScalarEvolutionExpander.cpp:
assert(ExitCount != SE.getCouldNotCompute() && "Invalid loop count");

Reviewers: sbaranga

Differential Revision: http://reviews.llvm.org/D42604

From: Evgeny Stupachenko <evstupac@gmail.com>
<evgeny.v.stupachenko@intel.com>
llvm-svn: 326154

show more ...

[SCEV] Factor out getUsedLoops

The patch introduces the new function in ScalarEvolution to get
all loops used in specified SCEV.

This is a preparation for re-writing isKnownPredicate utility as
des

[SCEV] Factor out getUsedLoops

The patch introduces the new function in ScalarEvolution to get
all loops used in specified SCEV.

This is a preparation for re-writing isKnownPredicate utility as
described in https://reviews.llvm.org/D42417.

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

llvm-svn: 326072

show more ...

[SCEV] Introduce SCEVPostIncRewriter

The patch introduces the SCEVPostIncRewriter rewriter which
is similar to SCEVInitRewriter but rewrites AddRec with post increment
value of this AddRec.

This is

[SCEV] Introduce SCEVPostIncRewriter

The patch introduces the SCEVPostIncRewriter rewriter which
is similar to SCEVInitRewriter but rewrites AddRec with post increment
value of this AddRec.

This is a preparation for re-writing isKnownPredicate utility as
described in https://reviews.llvm.org/D42417.

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

llvm-svn: 326071

show more ...

[SCEV] Extends the SCEVInitRewriter

The patch introduces an additional parameter IgnoreOtherLoops to SCEVInitRewriter.
if it is equal to true then rewriter will not invalidate result in case
SCEV de

[SCEV] Extends the SCEVInitRewriter

The patch introduces an additional parameter IgnoreOtherLoops to SCEVInitRewriter.
if it is equal to true then rewriter will not invalidate result in case
SCEV depends on other loops then specified during creation.

The patch does not change the default behavior.
This is a preparation for re-writing isKnownPredicate utility as
described in https://reviews.llvm.org/D42417.

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

llvm-svn: 326067

show more ...

[SCEV][NFC] Factor out common logic into a separate method

SCEV has multiple occurences of code when we need to prove some predicate on
every iteration of a loop and do it with invocations of couple

[SCEV][NFC] Factor out common logic into a separate method

SCEV has multiple occurences of code when we need to prove some predicate on
every iteration of a loop and do it with invocations of couple `isLoopEntryGuardedByCond`,
`isLoopBackedgeGuardedByCond`. This patch factors out these two calls into a separate
method. It is a preparation step to extend this logic: it is not the only way how we can prove
such conditions.

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

llvm-svn: 325745

show more ...

[SCEV] Temporarily disable loop versioning for the purpose
of turning SCEVUnknowns of PHIs into AddRecExprs.

This feature is now hidden behind the -scev-version-unknown flag.

Fixes PR36032 and PR35

[SCEV] Temporarily disable loop versioning for the purpose
of turning SCEVUnknowns of PHIs into AddRecExprs.

This feature is now hidden behind the -scev-version-unknown flag.

Fixes PR36032 and PR35432.

llvm-svn: 325687

show more ...

[NFC] Rename isKnownViaSimpleReasoning to isKnownViaNonRecursiveReasoning

llvm-svn: 325216

[SCEV] Favor isKnownViaSimpleReasoning over constant ranges check

There is a more powerful but still simple function `isKnownViaSimpleReasoning ` that
does constant range check and few more addition

[SCEV] Favor isKnownViaSimpleReasoning over constant ranges check

There is a more powerful but still simple function `isKnownViaSimpleReasoning ` that
does constant range check and few more additional checks. We use it some places (e.g.
when proving implications) and in some other places we only check constant ranges.

Currently, indvar simplifier fails to remove the check in following loop:

int inc = ...;
for (int i = inc, j = inc - 1; i < 200; ++i, ++j)
if (i > j) { ... }

This patch replaces all usages of `isKnownPredicateViaConstantRanges` with
`isKnownViaSimpleReasoning` to have smarter proofs. In particular, it fixes the
case above.

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

llvm-svn: 325214

show more ...

Adding a width of the GEP index to the Data Layout.

Making a width of GEP Index, which is used for address calculation, to be one of the pointer properties in the Data Layout.
p[address space]:size:

Adding a width of the GEP index to the Data Layout.

Making a width of GEP Index, which is used for address calculation, to be one of the pointer properties in the Data Layout.
p[address space]:size:memory_size:alignment:pref_alignment:index_size_in_bits.
The index size parameter is optional, if not specified, it is equal to the pointer size.

Till now, the InstCombiner normalized GEPs and extended the Index operand to the pointer width.
It works fine if you can convert pointer to integer for address calculation and all registered targets do this.
But some ISAs have very restricted instruction set for the pointer calculation. During discussions were desided to retrieve information for GEP index from the Data Layout.
http://lists.llvm.org/pipermail/llvm-dev/2018-January/120416.html

I added an interface to the Data Layout and I changed the InstCombiner and some other passes to take the Index width into account.
This change does not affect any in-tree target. I added tests to cover data layouts with explicitly specified index size.

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

llvm-svn: 325102

show more ...