[SCEV] Do not fold dominated SCEVUnknown into AddRecExpr start

When folding arguments of AddExpr or MulExpr with recurrences, we rely on the fact that
the loop of our base recurrency is the bottom-l

[SCEV] Do not fold dominated SCEVUnknown into AddRecExpr start

When folding arguments of AddExpr or MulExpr with recurrences, we rely on the fact that
the loop of our base recurrency is the bottom-lost in terms of domination. This assumption
may be broken by an expression which is treated as invariant, and which depends on a complex
Phi for which SCEVUnknown was created. If such Phi is a loop Phi, and this loop is lower than
the chosen AddRecExpr's loop, it is invalid to fold our expression with the recurrence.

Another reason why it might be invalid to fold SCEVUnknown into Phi start value is that unlike
other SCEVs, SCEVUnknown are sometimes position-bound. For example, here:

for (...) { // loop
phi = {A,+,B}
}
X = load ...
Folding phi + X into {A+X,+,B}<loop> actually makes no sense, because X does not exist and cannot
exist while we are iterating in loop (this memory can be even not allocated and not filled by this moment).
It is only valid to make such folding if X is defined before the loop. In this case the recurrence {A+X,+,B}<loop>
may be existant.

This patch prohibits folding of SCEVUnknown (and those who use them) into the start value of an AddRecExpr,
if this instruction is dominated by the loop. Merging the dominating unknown values is still valid. Some tests that
relied on the fact that some SCEVUnknown should be folded into AddRec's are changed so that they no longer
expect such behavior.

llvm-svn: 303730

show more ...

[SCEV] Clarify behavior around max backedge taken count

This is a re-application of a r303497 that was reverted in r303498.
I thought it had broken a bot when it had not (the breakage did not
go awa

[SCEV] Clarify behavior around max backedge taken count

This is a re-application of a r303497 that was reverted in r303498.
I thought it had broken a bot when it had not (the breakage did not
go away with the revert).

This change makes the split between the "exact" backedge taken count
and the "maximum" backedge taken count a bit more obvious. Both of
these are upper bounds on the number of times the loop header
executes (since SCEV does not account for most kinds of abnormal
control flow), but the latter is guaranteed to be a constant.

There were a few places where the max backedge taken count *was* a
non-constant; I've changed those to compute constants instead.

At this point, I'm not sure if the constant max backedge count can be
computed by calling `getUnsignedRange(Exact).getUnsignedMax()` without
losing precision. If it can, we can simplify even further by making
`getMaxBackedgeTakenCount` a thin wrapper around
`getBackedgeTakenCount` and `getUnsignedRange`.

llvm-svn: 303531

show more ...

Revert "[SCEV] Clarify behavior around max backedge taken count"

This reverts commit r303497 since it breaks the msan bootstrap bot:
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstra

Revert "[SCEV] Clarify behavior around max backedge taken count"

This reverts commit r303497 since it breaks the msan bootstrap bot:
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap/builds/1379/

llvm-svn: 303498

show more ...

[SCEV] Clarify behavior around max backedge taken count

This change makes the split between the "exact" backedge taken count
and the "maximum" backedge taken count a bit more obvious. Both of
these

[SCEV] Clarify behavior around max backedge taken count

This change makes the split between the "exact" backedge taken count
and the "maximum" backedge taken count a bit more obvious. Both of
these are upper bounds on the number of times the loop header
executes (since SCEV does not account for most kinds of abnormal
control flow), but the latter is guaranteed to be a constant.

There were a few places where the max backedge taken count *was* a
non-constant; I've changed those to compute constants instead.

At this point, I'm not sure if the constant max backedge count can be
computed by calling `getUnsignedRange(Exact).getUnsignedMax()` without
losing precision. If it can, we can simplify even further by making
`getMaxBackedgeTakenCount` a thin wrapper around
`getBackedgeTakenCount` and `getUnsignedRange`.

llvm-svn: 303497

show more ...

[SCEV][NFC] Remove duplication of isLoopInvariant code

Replace two places that duplicate the code of isLoopInvariant method with
the invocation of this method.

Differential Revision: https://review

[SCEV][NFC] Remove duplication of isLoopInvariant code

Replace two places that duplicate the code of isLoopInvariant method with
the invocation of this method.

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

llvm-svn: 303336

show more ...

[SCEV] Always sort AddRecExprs from different loops by dominance

Sorting of AddRecExprs by loop nesting does not make sense since we only invoke
the CompareSCEVComplexity for AddRecExprs that are us

[SCEV] Always sort AddRecExprs from different loops by dominance

Sorting of AddRecExprs by loop nesting does not make sense since we only invoke
the CompareSCEVComplexity for AddRecExprs that are used by one SCEV. This
guarantees that there is always a dominance relationship between them. This
patch removes the sorting by nesting which is a dead code in current usage of
this function.

Reviewed By: sanjoy

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

llvm-svn: 303235

show more ...

[SCEV][NFC] Replace redundant dyn_cast with cast in getAddExpr

Replace dyn_cast which is ensured by isa just one line above with cast.

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

llvm-s

[SCEV][NFC] Replace redundant dyn_cast with cast in getAddExpr

Replace dyn_cast which is ensured by isa just one line above with cast.

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

llvm-svn: 303234

show more ...

[SCEV] Fix sorting order for AddRecExprs

The existing sorting order in defined CompareSCEVComplexity sorts AddRecExprs
by loop depth, but does not pay attention to dominance of loops. This can
lead

[SCEV] Fix sorting order for AddRecExprs

The existing sorting order in defined CompareSCEVComplexity sorts AddRecExprs
by loop depth, but does not pay attention to dominance of loops. This can
lead us to the following buggy situation:

for (...) { // loop1
op1 = {A,+,B}
}
for (...) { // loop2
op2 = {A,+,B}
S = add op1, op2
}

In this case there is no guarantee that in operand list of S the op2 comes
before op1 (loop depth is the same, so they will be sorted just
lexicographically), so we can incorrectly treat S as a recurrence of loop1,
which is wrong.

This patch changes the sorting logic so that it places the dominated recs
before the dominating recs. This ensures that when we pick the first recurrency
in the operands order, it will be the bottom-most in terms of domination tree.
The attached test set includes some tests that produce incorrect SCEV
estimations and crashes with oldlogic.

Reviewers: sanjoy, reames, apilipenko, anna

Reviewed By: sanjoy

Subscribers: llvm-commits, mzolotukhin

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

llvm-svn: 303148

show more ...

[SCEV] Use copy initialization of APInts instead of direct initialization.

This is based on post commit feed back from r302769.

llvm-svn: 303092

[ValueTracking] Replace all uses of ComputeSignBit with computeKnownBits.

This patch finishes off the conversion of ComputeSignBit to computeKnownBits.

Differential Revision: https://reviews.llvm.o

[ValueTracking] Replace all uses of ComputeSignBit with computeKnownBits.

This patch finishes off the conversion of ComputeSignBit to computeKnownBits.

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

llvm-svn: 303035

show more ...

Move some code into ScalarEvolution.cpp; NFC

I need to add some asserts to these constructors that are easier to
add once they're in the .cpp file.

llvm-svn: 303032

[KnownBits] Add bit counting methods to KnownBits struct and use them where possible

This patch adds min/max population count, leading/trailing zero/one bit counting methods.

The min methods return

[KnownBits] Add bit counting methods to KnownBits struct and use them where possible

This patch adds min/max population count, leading/trailing zero/one bit counting methods.

The min methods return answers based on bits that are known without considering unknown bits. The max methods give answers taking into account the largest count that unknown bits could give.

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

llvm-svn: 302925

show more ...

[SCEV] Reduce possible APInt allocations a bit.

llvm-svn: 302769

[SCEV] Remove unneeded 'using namespace APIntOps'.

llvm-svn: 302768

[SCEV] Don't use std::move on both inputs to APInt::operator+ or operator-. It might be confusing to the reader. NFC

llvm-svn: 302448

[SCEV] Use APInt::operator*=(uint64_t) to avoid a temporary APInt for a constant.

llvm-svn: 302404

[SCEV] Have getRangeForAffineARHelper take StartRange by const reference to avoid a copy in many of the cases.

llvm-svn: 302398

[SCEV] Use move semantics in ScalarEvolution::setRange

Summary: This makes setRange take ConstantRange by rvalue reference since most callers were passing an unnamed temporary ConstantRange. We can

[SCEV] Use move semantics in ScalarEvolution::setRange

Summary: This makes setRange take ConstantRange by rvalue reference since most callers were passing an unnamed temporary ConstantRange. We can then move that ConstantRange into the DenseMap caches. For the callers that weren't passing a temporary, I've added std::move to to the local variable being passed.

Reviewers: sanjoy, mzolotukhin, efriedma

Reviewed By: sanjoy

Subscribers: takuto.ikuta, llvm-commits

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

llvm-svn: 302371

show more ...

Remove unnecessary const_cast

llvm-svn: 302368

Use array_pod_sort instead of std::sort

llvm-svn: 302367

[SCEV] Remove extra APInt copies from getRangeForAffineARHelper.

This changes one parameter to be a const APInt& since we only read from it. Use std::move on local APInts once they are no longer nee

[SCEV] Remove extra APInt copies from getRangeForAffineARHelper.

This changes one parameter to be a const APInt& since we only read from it. Use std::move on local APInts once they are no longer needed so we can reuse their allocations. Lastly, use operator+=(uint64_t) instead of adding 1 to an APInt twice creating a new APInt each time.

llvm-svn: 302335

show more ...

[SCEV] Use std::move to avoid some APInt copies.

llvm-svn: 302334

[SCEV] Use APInt's uint64_t operations instead of creating a temporary APInt to hold 1.

llvm-svn: 302333

[SCEV] Avoid a couple APInt copies by capturing by reference since the method returns a reference.

llvm-svn: 302332

Fix a typo.

llvm-svn: 302175