[SCEV] NFC : Removing unnecessary check on outgoing branches of a branch instr.

Summary:
For a given loop, getLoopLatch returns a non-null value
when a loop has only one latch block. In the modified

[SCEV] NFC : Removing unnecessary check on outgoing branches of a branch instr.

Summary:
For a given loop, getLoopLatch returns a non-null value
when a loop has only one latch block. In the modified
context a check on both the outgoing branches of a terminator instruction (of latch) to same header is redundant.

Reviewers: jbhateja

Reviewed By: jbhateja

Subscribers: sanjoy

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

llvm-svn: 318991

show more ...

[SCEV] Strengthen variance condition in calculateLoopDisposition

Given loops `L1` and `L2` with AddRecs `AR1` and `AR2` varying in them respectively.
When identifying loop disposition of `AR2` w.r.t

[SCEV] Strengthen variance condition in calculateLoopDisposition

Given loops `L1` and `L2` with AddRecs `AR1` and `AR2` varying in them respectively.
When identifying loop disposition of `AR2` w.r.t. `L1`, we only say that it is varying if
`L1` contains `L2`. But there is also a possible situation where `L1` and `L2` are
consecutive sibling loops within the parent loop. In this case, `AR2` is also varying
w.r.t. `L1`, but we don't correctly identify it.

It can lead, for exaple, to attempt of incorrect folding. Consider:
AR1 = {a,+,b}<L1>
AR2 = {c,+,d}<L2>
EXAR2 = sext(AR1)
MUL = mul AR1, EXAR2
If we incorrectly assume that `EXAR2` is invariant w.r.t. `L1`, we can end up trying to
construct something like: `{a * {c,+,d}<L2>,+,b * {c,+,d}<L2>}<L1>`, which is incorrect
because `AR2` is not available on entrance of `L1`.

Both situations "`L1` contains `L2`" and "`L1` preceeds sibling loop `L2`" can be handled
with one check: "header of `L1` dominates header of `L2`". This patch replaces the old
insufficient check with this one.

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

llvm-svn: 318819

show more ...

[SCEV] simplify loop. NFC.

Change loop to range-based

llvm-svn: 318401

Fix clang -Wsometimes-uninitialized warning in SCEV code

I don't believe this was a problem in practice, as it's likely that the
boolean wasn't checked unless the backend condition was non-null.

ll

Fix clang -Wsometimes-uninitialized warning in SCEV code

I don't believe this was a problem in practice, as it's likely that the
boolean wasn't checked unless the backend condition was non-null.

llvm-svn: 318073

show more ...

[SCEV] Handling for ICmp occuring in the evolution chain.

Summary:
If a compare instruction is same or inverse of the compare in the
branch of the loop latch, then return a constant evolution node

[SCEV] Handling for ICmp occuring in the evolution chain.

Summary:
If a compare instruction is same or inverse of the compare in the
branch of the loop latch, then return a constant evolution node.
This shall facilitate computations of loop exit counts in cases
where compare appears in the evolution chain of induction variables.

Will fix PR 34538

Reviewers: sanjoy, hfinkel, junryoungju

Reviewed By: sanjoy, junryoungju

Subscribers: javed.absar, llvm-commits

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

llvm-svn: 318050

show more ...

[SCEV] Fix an assertion failure in the max backedge taken count

Max backedge taken count is always expected to be a constant; and this is
usually true by construction -- it is a SCEV expression with

[SCEV] Fix an assertion failure in the max backedge taken count

Max backedge taken count is always expected to be a constant; and this is
usually true by construction -- it is a SCEV expression with constant inputs.
However, if the max backedge expression ends up being computed to be a udiv with
a constant zero denominator[0], SCEV does not fold the result to a constant
since there is no constant it can fold it to (SCEV has no representation for
"infinity" or "undef").

However, in computeMaxBECountForLT we already know the denominator is positive,
and thus at least 1; and we can use this fact to avoid dividing by zero.

[0]: We can end up with a constant zero denominator if the signed range of the
stride is more precise than the unsigned range.

llvm-svn: 316615

show more ...

Add a comment to clarify a future change

llvm-svn: 316614

Revert "[ScalarEvolution] Handling for ICmp occuring in the evolution chain."

This reverts commit r316054. There was some confusion over the review process:
http://lists.llvm.org/pipermail/llvm-com

Revert "[ScalarEvolution] Handling for ICmp occuring in the evolution chain."

This reverts commit r316054. There was some confusion over the review process:
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20171016/495884.html

llvm-svn: 316129

show more ...

[ScalarEvolution] Handling for ICmp occuring in the evolution chain.

Summary:
If a compare instruction is same or inverse of the compare in the
branch of the loop latch, then return a constant evo

[ScalarEvolution] Handling for ICmp occuring in the evolution chain.

Summary:
If a compare instruction is same or inverse of the compare in the
branch of the loop latch, then return a constant evolution node.
Currently scope of evaluation is limited to SCEV computation for
PHI nodes.

This shall facilitate computations of loop exit counts in cases
where compare appears in the evolution chain of induction variables.

Will fix PR 34538
Reviewers: sanjoy, hfinkel, junryoungju

Reviewed By: junryoungju

Subscribers: javed.absar, llvm-commits

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

llvm-svn: 316054

show more ...

Revert "[SCEV] Maintain and use a loop->loop invalidation dependency"

This reverts commit r315713. It causes PR34968.

I think I know what the problem is, but I don't think I'll have time to fix it

Revert "[SCEV] Maintain and use a loop->loop invalidation dependency"

This reverts commit r315713. It causes PR34968.

I think I know what the problem is, but I don't think I'll have time to fix it
this week.

llvm-svn: 315962

show more ...

[SCEV] Rename getMaxBECount and update comments. NFC

Post commit review comments at D38825.

llvm-svn: 315920

Reverting r315590; it did not include changes for llvm-tblgen, which is causing link errors for several people.

Error LNK2019 unresolved external symbol "public: void __cdecl `anonymous namespace'::

Reverting r315590; it did not include changes for llvm-tblgen, which is causing link errors for several people.

Error LNK2019 unresolved external symbol "public: void __cdecl `anonymous namespace'::MatchableInfo::dump(void)const " (?dump@MatchableInfo@?A0xf4f1c304@@QEBAXXZ) referenced in function "public: void __cdecl `anonymous namespace'::AsmMatcherEmitter::run(class llvm::raw_ostream &)" (?run@AsmMatcherEmitter@?A0xf4f1c304@@QEAAXAEAVraw_ostream@llvm@@@Z) llvm-tblgen D:\llvm\2017\utils\TableGen\AsmMatcherEmitter.obj 1

llvm-svn: 315854

show more ...

[SCEV] Maintain and use a loop->loop invalidation dependency

Summary:
This change uses the loop use list added in the previous change to remember the
loops that appear in the trip count expressions

[SCEV] Maintain and use a loop->loop invalidation dependency

Summary:
This change uses the loop use list added in the previous change to remember the
loops that appear in the trip count expressions of other loops; and uses it in
forgetLoop. This lets us not scan every loop in the function on a forgetLoop
call.

With this change we no longer invalidate clear out backedge taken counts on
forgetValue. I think this is fine -- the contract is that SCEV users must call
forgetLoop(L) if their change to the IR could have changed the trip count of L;
solely calling forgetValue on a value feeding into the backedge condition of L
is not enough. Moreover, I don't think we can strengthen forgetValue to be
sufficient for invalidating trip counts without significantly re-architecting
SCEV. For instance, if we have the loop:

I = *Ptr;
E = I + 10;
do {
// ...
} while (++I != E);

then the backedge taken count of the loop is 9, and it has no reference to
either I or E, i.e. there is no way in SCEV today to re-discover the dependency
of the loop's trip count on E or I. So a SCEV client cannot change E to (say)
"I + 20", call forgetValue(E) and expect the loop's trip count to be updated.

Reviewers: atrick, sunfish, mkazantsev

Subscribers: mcrosier, llvm-commits

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

llvm-svn: 315713

show more ...

[SCEV] Teach SCEV to find maxBECount when loop endbound is variant

Summary:
This patch teaches SCEV to calculate the maxBECount when the end bound
of the loop can vary. Note that we cannot calculate

[SCEV] Teach SCEV to find maxBECount when loop endbound is variant

Summary:
This patch teaches SCEV to calculate the maxBECount when the end bound
of the loop can vary. Note that we cannot calculate the exactBECount.

This will only be done when both conditions are satisfied:
1. the loop termination condition is strictly LT.
2. the IV is proven to not overflow.

This provides more information to users of SCEV and can be used to
improve identification of finite loops.

Reviewers: sanjoy, mkazantsev, silviu.baranga, atrick

Reviewed by: mkazantsev

Subscribers: llvm-commits

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

llvm-svn: 315683

show more ...

[SCEV] Maintain loop use lists, and use them in forgetLoop

Summary:
Currently we do not correctly invalidate memoized results for add recurrences
that were created directly (i.e. they were not creat

[SCEV] Maintain loop use lists, and use them in forgetLoop

Summary:
Currently we do not correctly invalidate memoized results for add recurrences
that were created directly (i.e. they were not created from a `Value`). This
change fixes this by keeping loop use lists and using the loop use lists to
determine which SCEV expressions to invalidate.

Here are some statistics on the number of uses of in the use lists of all loops
on a clang bootstrap (config: release, no asserts):

Count: 731310
Min: 1
Mean: 8.555150
50th %time: 4
95th %tile: 25
99th %tile: 53
Max: 433

Reviewers: atrick, sunfish, mkazantsev

Subscribers: mcrosier, llvm-commits

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

llvm-svn: 315672

show more ...

[dump] Remove NDEBUG from test to enable dump methods [NFC]

Summary:
Add LLVM_FORCE_ENABLE_DUMP cmake option, and use it along with
LLVM_ENABLE_ASSERTIONS to set LLVM_ENABLE_DUMP.

Remove NDEBUG and

[dump] Remove NDEBUG from test to enable dump methods [NFC]

Summary:
Add LLVM_FORCE_ENABLE_DUMP cmake option, and use it along with
LLVM_ENABLE_ASSERTIONS to set LLVM_ENABLE_DUMP.

Remove NDEBUG and only use LLVM_ENABLE_DUMP to enable dump methods.

Move definition of LLVM_ENABLE_DUMP from config.h to llvm-config.h so
it'll be picked up by public headers.

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

llvm-svn: 315590

show more ...

[SCEV] Properly handle the case of a non-constant start with a zero accum in ScalarEvolution::createAddRecFromPHIWithCastsImpl

Summary:
This patch fixes an error in the patch to ScalarEvolution::cr

[SCEV] Properly handle the case of a non-constant start with a zero accum in ScalarEvolution::createAddRecFromPHIWithCastsImpl

Summary:
This patch fixes an error in the patch to ScalarEvolution::createAddRecFromPHIWithCastsImpl
made in D37265. In that patch we handle the cases where the either the start or accum values can be
zero after truncation. But, we assume that the start value must be a constant if the accum is
zero. This is clearly an erroneous assumption. This change removes that assumption.

Reviewers: sanjoy, dorit, mkazantsev

Reviewed By: sanjoy

Subscribers: llvm-commits

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

llvm-svn: 315491

show more ...

Remove trailing whitespaces.

llvm-svn: 314115

[SCEV] Generalize folding of trunc(x)+n*trunc(y) into folding m*trunc(x)+n*trunc(y)

Summary:
A SCEV such as:
{%v2,+,((-1 * (trunc i64 (-1 * %v1) to i32)) + (-1 * (trunc i64 %v1 to i32)))}<%loop>

c

[SCEV] Generalize folding of trunc(x)+n*trunc(y) into folding m*trunc(x)+n*trunc(y)

Summary:
A SCEV such as:
{%v2,+,((-1 * (trunc i64 (-1 * %v1) to i32)) + (-1 * (trunc i64 %v1 to i32)))}<%loop>

can be folded into, simply, {%v2,+,0}. However, the current code in ::getAddExpr()
will not try to apply the simplification m*trunc(x)+n*trunc(y) -> trunc(trunc(m)*x+trunc(n)*y)
because it only keys off having a non-multiplied trunc as the first term in the simplification.

This patch generalizes this code to try to do a more generic fold of these trunc
expressions.

Reviewers: sanjoy

Reviewed By: sanjoy

Subscribers: llvm-commits

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

llvm-svn: 313988

show more ...

[ScalarEvolution] Refactor forgetLoop() to improve performance

forgetLoop() has pretty bad performance because it goes over
the same instructions over and over again in particular when
nested loop a

[ScalarEvolution] Refactor forgetLoop() to improve performance

forgetLoop() has pretty bad performance because it goes over
the same instructions over and over again in particular when
nested loop are involved.
The refactoring changes the function to a not-recursive function
and reusing the allocation for data-structures and the Visited
set.

NFCI

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

llvm-svn: 312920

show more ...

[SCEV] Ensure ScalarEvolution::createAddRecFromPHIWithCastsImpl properly handles out of range truncations of the start and accum values

Summary:
When constructing the predicate P1 in ScalarEvolutio

[SCEV] Ensure ScalarEvolution::createAddRecFromPHIWithCastsImpl properly handles out of range truncations of the start and accum values

Summary:
When constructing the predicate P1 in ScalarEvolution::createAddRecFromPHIWithCastsImpl() it is possible
for the PHISCEV from which the predicate is constructed to be a SCEVConstant instead of a SCEVAddRec. If
this happens, then the cast<SCEVAddRec>(PHISCEV) in the code will assert.

Such a PHISCEV is possible if either the start value or the accumulator value is a constant value
that not equal to its truncated value, and if the truncated value is zero.

This patch adds tests that demonstrate the cast<> assertion, and fixes this problem by checking
whether the PHISCEV is a constant before constructing the P1 predicate; if it is, then P1 is
equivalent to one of P2 or P3. Additionally, if we know that the start value or accumulator
value are constants then we check whether the P2 and/or P3 predicates are known false at compile
time; if either is, then we bail out of constructing the AddRec.

Reviewers: sanjoy, mkazantsev, silviu.baranga

Reviewed By: mkazantsev

Subscribers: mkazantsev, llvm-commits

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

llvm-svn: 312568

show more ...

[SCEV] Add URem support to SCEV

In LLVM IR the following code:

%r = urem <ty> %t, %b

is equivalent to

%q = udiv <ty> %t, %b
%s = mul <ty> nuw %q, %b
%r = sub <ty> nuw %t, %q ; (t

[SCEV] Add URem support to SCEV

In LLVM IR the following code:

%r = urem <ty> %t, %b

is equivalent to

%q = udiv <ty> %t, %b
%s = mul <ty> nuw %q, %b
%r = sub <ty> nuw %t, %q ; (t / b) * b + (t % b) = t

As UDiv, Mul and Sub are already supported by SCEV, URem can be implemented
with minimal effort using that relation:

%r --> (-%b * (%t /u %b)) + %t

We implement two special cases:

- if %b is 1, the result is always 0
- if %b is a power-of-two, we produce a zext/trunc based expression instead

That is, the following code:

%r = urem i32 %t, 65536

Produces:

%r --> (zext i16 (trunc i32 %a to i16) to i32)

Note that while this helps get a tighter bound on the range analysis and the
known-bits analysis, this exposes some normalization shortcoming of SCEVs:

%div = udim i32 %a, 65536
%mul = mul i32 %div, 65536
%rem = urem i32 %a, 65536
%add = add i32 %mul, %rem

Will usually not be reduced.

llvm-svn: 312329

show more ...

[Analysis] Fix some Clang-tidy modernize and Include What You Use warnings; other minor fixes (NFC).

llvm-svn: 311212

[SCEV] Preserve NSW information for sext(subtract).

Pushes the sext onto the operands of a Sub if NSW is present.
Also adds support for propagating the nowrap flags of the
llvm.ssub.with.overflow in

[SCEV] Preserve NSW information for sext(subtract).

Pushes the sext onto the operands of a Sub if NSW is present.
Also adds support for propagating the nowrap flags of the
llvm.ssub.with.overflow intrinsic during analysis.

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

llvm-svn: 310117

show more ...

[SCEV] Re-enable "Cache results of computeExitLimit"

The patch rL309080 was reverted because it did not clean up the cache on "forgetValue"
method call. This patch re-enables this change, adds the m

[SCEV] Re-enable "Cache results of computeExitLimit"

The patch rL309080 was reverted because it did not clean up the cache on "forgetValue"
method call. This patch re-enables this change, adds the missing check and introduces
two new unit tests that make sure that the cache is cleaned properly.

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

llvm-svn: 309925

show more ...