Revert "[SCEV] Simplify some flags expressions." -- dependent revision breaks MSVC builds.

This reverts D48238.

llvm-svn: 334877

[SCEV] Simplify some flags expressions.

Summary:
Sending for presubmit review out of an abundance of caution; it would be
bad to mess this up.

Reviewers: sanjoy

Subscribers: hiraditya, llvm-commit

[SCEV] Simplify some flags expressions.

Summary:
Sending for presubmit review out of an abundance of caution; it would be
bad to mess this up.

Reviewers: sanjoy

Subscribers: hiraditya, llvm-commits

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

llvm-svn: 334875

show more ...

[SCEV] Use LLVM_MARK_AS_BITMASK_ENUM in SCEV.

Summary:
Obviates the need for mask/clear/setFlags helpers.

There are some expressions here which can be simplified, but to keep
this easy to review, I

[SCEV] Use LLVM_MARK_AS_BITMASK_ENUM in SCEV.

Summary:
Obviates the need for mask/clear/setFlags helpers.

There are some expressions here which can be simplified, but to keep
this easy to review, I have not simplified them in this patch.

No functional change.

Reviewers: sanjoy

Subscribers: hiraditya, llvm-commits

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

llvm-svn: 334874

show more ...

[SCEV] Fix a variable name, NFC.

llvm-svn: 334738

[SCEV] Simplify zext/trunc idiom that appears when handling bitmasks.

Summary:
Specifically, we transform

zext(2^K * (trunc X to iN)) to iM ->
2^K * (zext(trunc X to i{N-K}) to iM)<nuw>

This i

[SCEV] Simplify zext/trunc idiom that appears when handling bitmasks.

Summary:
Specifically, we transform

zext(2^K * (trunc X to iN)) to iM ->
2^K * (zext(trunc X to i{N-K}) to iM)<nuw>

This is helpful because pulling the 2^K out of the zext allows further
optimizations.

Reviewers: sanjoy

Subscribers: hiraditya, llvm-commits, timshen

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

llvm-svn: 334737

show more ...

[SCEV] Simplify trunc-of-add/mul to add/mul-of-trunc under more circumstances.

Summary:
Previously we would do this simplification only if it did not introduce
any new truncs (excepting new truncs w

[SCEV] Simplify trunc-of-add/mul to add/mul-of-trunc under more circumstances.

Summary:
Previously we would do this simplification only if it did not introduce
any new truncs (excepting new truncs which replace other cast ops).

This change weakens this condition: If the number of truncs stays the
same, but we're able to transform trunc(X + Y) to X + trunc(Y), that's
still simpler, and it may open up additional transformations.

While we're here, also clean up some duplicated code.

Reviewers: sanjoy

Subscribers: hiraditya, llvm-commits

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

llvm-svn: 334736

show more ...

[SCEV] Fix indentation and combine two if statements in getMulExpr, NFC.

llvm-svn: 334735

[SCEV] Add transform zext((A * B * ...)<nuw>) --> (zext(A) * zext(B) * ...)<nuw>.

Reviewers: sanjoy

Subscribers: hiraditya, llvm-commits

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

llv

[SCEV] Add transform zext((A * B * ...)<nuw>) --> (zext(A) * zext(B) * ...)<nuw>.

Reviewers: sanjoy

Subscribers: hiraditya, llvm-commits

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

llvm-svn: 334429

show more ...

[SCEV] Add nuw/nsw to mul ops in StrengthenNoWrapFlags where safe.

Summary:
Previously we would add them for adds, but not multiplies.

Reviewers: sanjoy

Subscribers: llvm-commits, hiraditya

Diffe

[SCEV] Add nuw/nsw to mul ops in StrengthenNoWrapFlags where safe.

Summary:
Previously we would add them for adds, but not multiplies.

Reviewers: sanjoy

Subscribers: llvm-commits, hiraditya

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

llvm-svn: 334428

show more ...

Fix indentation in ScalarEvolution.cpp.

Whitespace-only change. (clang-formatted the whole block.)

llvm-svn: 334427

[SCEV] Canonicalize "A /u C1 /u C2" to "A /u (C1*C2)".

Summary: FWIW InstCombine already folds this. Also avoid the case where C1*C2 overflows.

Reviewers: sunfish, sanjoy

Subscribers: hiraditya, b

[SCEV] Canonicalize "A /u C1 /u C2" to "A /u (C1*C2)".

Summary: FWIW InstCombine already folds this. Also avoid the case where C1*C2 overflows.

Reviewers: sunfish, sanjoy

Subscribers: hiraditya, bixia, llvm-commits

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

llvm-svn: 334425

show more ...

[SCEV] Look through zero-extends in howFarToZero

An expression like
(zext i2 {(trunc i32 (1 + %B) to i2),+,1}<%while.body> to i32)
will become zero exactly when the nested value becomes zero in it

[SCEV] Look through zero-extends in howFarToZero

An expression like
(zext i2 {(trunc i32 (1 + %B) to i2),+,1}<%while.body> to i32)
will become zero exactly when the nested value becomes zero in its type.
Strip injective operations from the input value in howFarToZero to make
the value simpler.

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

llvm-svn: 334318

show more ...

Rename DEBUG macro to LLVM_DEBUG.

The DEBUG() macro is very generic so it might clash with other projects.
The renaming was done as follows:
- git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/

Rename DEBUG macro to LLVM_DEBUG.

The DEBUG() macro is very generic so it might clash with other projects.
The renaming was done as follows:
- git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g'
- git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM
- Manual change to APInt
- Manually chage DOCS as regex doesn't match it.

In the transition period the DEBUG() macro is still present and aliased
to the LLVM_DEBUG() one.

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

llvm-svn: 332240

show more ...

SCEV] Do not use induction in isKnownPredicate for simplification umax.

During simplification umax we trigger isKnownPredicate twice. As a first attempt it
tries the induction. To do that it tries t

SCEV] Do not use induction in isKnownPredicate for simplification umax.

During simplification umax we trigger isKnownPredicate twice. As a first attempt it
tries the induction. To do that it tries to get post increment of SCEV.
Re-writing the SCEV may result in simplification of umax. If the SCEV contains a lot
of umax operations this recursion becomes very slow.

The added test demonstrates the slow behavior.

To resolve this we use only simple ways to check whether the predicate is known.

Reviewers: sanjoy, mkazantsev
Reviewed By: sanjoy
Subscribers: lebedev.ri, javed.absar, llvm-commits
Differential Revision: https://reviews.llvm.org/D46046

llvm-svn: 331949

show more ...

Re-enable "[SCEV] Make computeExitLimit more simple and more powerful"

This patch was temporarily reverted because it has exposed bug 37229 on
PowerPC platform. The bug is unrelated to the patch and

Re-enable "[SCEV] Make computeExitLimit more simple and more powerful"

This patch was temporarily reverted because it has exposed bug 37229 on
PowerPC platform. The bug is unrelated to the patch and was just a general
bug in the optimization done for PowerPC platform only. The bug was fixed
by the patch rL331410.

This patch returns the disabled commit since the bug was fixed.

llvm-svn: 331427

show more ...

IWYU for llvm-config.h in llvm, additions.

See r331124 for how I made a list of files missing the include.
I then ran this Python script:

for f in open('filelist.txt'):
f = f.strip()

IWYU for llvm-config.h in llvm, additions.

See r331124 for how I made a list of files missing the include.
I then ran this Python script:

for f in open('filelist.txt'):
f = f.strip()
fl = open(f).readlines()

found = False
for i in xrange(len(fl)):
p = '#include "llvm/'
if not fl[i].startswith(p):
continue
if fl[i][len(p):] > 'Config':
fl.insert(i, '#include "llvm/Config/llvm-config.h"\n')
found = True
break
if not found:
print 'not found', f
else:
open(f, 'w').write(''.join(fl))

and then looked through everything with `svn diff | diffstat -l | xargs -n 1000 gvim -p`
and tried to fix include ordering and whatnot.

No intended behavior change.

llvm-svn: 331184

show more ...

[SCEV] Touch the unsused stats variables for product build.

This is a fix by elimination compiler warnings considered as errors.

llvm-svn: 331103

[SCEV] Reduce the number of invocation to non trivial getExact function

The invocation of getExact in ScalarEvolution::getBackedgeTakenInfo is used
only for getting statistic and for assert.
Even i

[SCEV] Reduce the number of invocation to non trivial getExact function

The invocation of getExact in ScalarEvolution::getBackedgeTakenInfo is used
only for getting statistic and for assert.
Even if statistics is disabled, the code related to it will be eliminated
the invocation to getExact itself will not be eliminated
because it may have side-effects like creation of new SCEVs.

So do invocation only when we collect statistics or executes asserts.

Reviewers: mkazantsev, sanjoy, javed.absar
Reviewed By: javed.absar
Subscribers: llvm-commits
Differential Revision: https://reviews.llvm.org/D46178

llvm-svn: 331099

show more ...

[SCEV] Add trivial case handling for umin utilities. NFC.

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

llvm

[SCEV] Add trivial case handling for umin utilities. NFC.

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

llvm-svn: 331022

show more ...

[SCEV] Introduce bulk umin creation utilities

Add new umin creation method which accepts a list of operands.

SCEV does not represents umin which is required in getExact, so
it transforms umin to um

[SCEV] Introduce bulk umin creation utilities

Add new umin creation method which accepts a list of operands.

SCEV does not represents umin which is required in getExact, so
it transforms umin to umax with not. As a result the transformation of
tree of max to max with several operands does not work.
We just use the new introduced method for creation umin from several operands.

Reviewers: sanjoy, mkazantsev
Reviewed By: sanjoy
Subscribers: javed.absar, llvm-commits
Differential Revision: https://reviews.llvm.org/D46047

llvm-svn: 331015

show more ...

Revert "[SCEV] Make computeExitLimit more simple and more powerful"

This reverts commit 023c8be90980e0180766196cba86f81608b35d38.

This patch triggers miscompile of zlib on PowerPC platform. Most li

Revert "[SCEV] Make computeExitLimit more simple and more powerful"

This reverts commit 023c8be90980e0180766196cba86f81608b35d38.

This patch triggers miscompile of zlib on PowerPC platform. Most likely it is
caused by some pre-backend PPC-specific pass, but we don't clearly know the
reason yet. So we temporally revert this patch with intention to return it
once the problem is resolved. See bug 37229 for details.

llvm-svn: 330893

show more ...

[LoopSimplify] Fix incorrect SCEV invalidation

In the function `simplifyOneLoop` we optimistically assume that changes in the
inner loop only affect this very loop and have no impact on its parents.

[LoopSimplify] Fix incorrect SCEV invalidation

In the function `simplifyOneLoop` we optimistically assume that changes in the
inner loop only affect this very loop and have no impact on its parents. In fact,
after rL329047 has been merged, we can now calculate exit counts for outer
loops which may depend on inner loops. Thus, we need to invalidate all parents
when we do something to a loop.

There is an evidence of incorrect behavior of `simplifyOneLoop`: when we insert
`SE->verify()` check in the end of this funciton, it fails on a bunch of existing
test, in particular:

LLVM :: Transforms/LoopUnroll/peel-loop-not-forced.ll
LLVM :: Transforms/LoopUnroll/peel-loop-pgo.ll
LLVM :: Transforms/LoopUnroll/peel-loop.ll
LLVM :: Transforms/LoopUnroll/peel-loop2.ll

Note that previously we have fixed issues of this variety, see rL328483.
This patch makes this function invalidate the outermost loop properly.

Differential Revision: https://reviews.llvm.org/D45937
Reviewed By: chandlerc

llvm-svn: 330576

show more ...

[NFC] Loosen restriction on preheader to fix buildbot

llvm-svn: 329379

[SCEV] Prove implications for SCEVUnknown Phis

This patch teaches SCEV how to prove implications for SCEVUnknown nodes that are Phis.
If we need to prove `Pred` for `LHS, RHS`, and `LHS` is a Phi wi

[SCEV] Prove implications for SCEVUnknown Phis

This patch teaches SCEV how to prove implications for SCEVUnknown nodes that are Phis.
If we need to prove `Pred` for `LHS, RHS`, and `LHS` is a Phi with possible incoming values
`L1, L2, ..., LN`, then if we prove `Pred` for `(L1, RHS), (L2, RHS), ..., (LN, RHS)` then we can also
prove it for `(LHS, RHS)`. If both `LHS` and `RHS` are Phis from the same block, it is sufficient
to prove the predicate for values that come from the same predecessor block.

The typical case that it handles is that we sometimes need to prove that `Phi(Len, Len - 1) >= 0`
given that `Len > 0`. The new logic was added to `isImpliedViaOperations` and only uses it and
non-recursive reasoning to prove the facts we need, so it should not hurt compile time a lot.

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

llvm-svn: 329150

show more ...

[SCEV] Fix PR36974.

The patch changes the usage of dominate to properlyDominate
to satisfy the condition !(a < a) while using std::max.

It is actually NFC due to set data structure is used to keep

[SCEV] Fix PR36974.

The patch changes the usage of dominate to properlyDominate
to satisfy the condition !(a < a) while using std::max.

It is actually NFC due to set data structure is used to keep
the Loops and no two identical loops can be in collection.
So in reality there is no difference between usage of
dominate and properlyDominate in this particular case.
However it might be changed so it is better to fix it.

llvm-svn: 329051

show more ...