test commit

llvm-svn: 298629

Revert "[ScalarEvolution] Predicate implication from operations"

This reverts commit rL298481

Fails clang-with-lto-ubuntu build.

llvm-svn: 298489

[ScalarEvolution] Predicate implication from operations

This patch allows SCEV predicate analysis to prove implication of some expression predicates
from context predicates related to arguments of t

[ScalarEvolution] Predicate implication from operations

This patch allows SCEV predicate analysis to prove implication of some expression predicates
from context predicates related to arguments of those expressions.
It introduces three new rules:

For addition:
(A >X && B >= 0) || (B >= 0 && A > X) ===> (A + B) > X.

For division:
(A > X) && (0 < B <= X + 1) ===> (A / B > 0).
(A > X) && (-B <= X < 0) ===> (A / B >= 0).

Using these rules, SCEV is able to prove facts like "if X > 1 then X / 2 > 0".
They can also be combined with the same context, to prove more complex expressions like
"if X > 1 then X/2 + 1 > 1".

Diffirential Revision: https://reviews.llvm.org/D30887

Reviewed by: sanjoy

llvm-svn: 298481

show more ...

[SCEV] Fix trip multiple calculation

If loop bound containing calculations like min(a,b), the Scalar
Evolution API getSmallConstantTripMultiple returns 4294967295 "-1"
as the trip multiple. The prob

[SCEV] Fix trip multiple calculation

If loop bound containing calculations like min(a,b), the Scalar
Evolution API getSmallConstantTripMultiple returns 4294967295 "-1"
as the trip multiple. The problem is that, SCEV use -1 * umax to
represent umin. The multiple constant -1 was returned, and the logic
of guarding against huge trip counts was skipped. Because -1 has 32
active bits.

The fix attempt to factor more general cases. First try to get the
greatest power of two divisor of trip count expression. In case
overflow happens, the trip count expression is still divisible by the
greatest power of two divisor returned. Returns 1 if not divisible by 2.

Patch by Huihui Zhang <huihuiz@codeaurora.org>

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

llvm-svn: 298301

show more ...

[SCEV] Use const Loop *L instead of Loop *L. NFC

Use const pointer in the trip count and trip multiple calculations.

Patch by Huihui Zhang <huihuiz@codeaurora.org>

llvm-svn: 298161

[SCEV] Compute affine range in another way to avoid bitwidth extending.

Summary:
This approach has two major advantages over the existing one:
1. We don't need to extend bitwidth in our computations

[SCEV] Compute affine range in another way to avoid bitwidth extending.

Summary:
This approach has two major advantages over the existing one:
1. We don't need to extend bitwidth in our computations. Extending
bitwidth is a big issue for compile time as we often end up working with
APInts wider than 64bit, which is a slow case for APInt.
2. When we zero extend a wrapped range, we lose some information (we
replace the range with [0, 1 << src bit width)). Thus, avoiding such
extensions better preserves information.

Correctness testing:
I ran 'ninja check' with assertions that the new implementation of
getRangeForAffineAR gives the same results as the old one (this
functionality is not present in this patch). There were several failures
- I inspected them manually and found out that they all are caused by
the fact that we're returning more accurate results now (see bullet (2)
above).
Without such assertions 'ninja check' works just fine, as well as
SPEC2006.

Compile time testing:
CTMark/Os:
- mafft/pairlocalalign -16.98%
- tramp3d-v4/tramp3d-v4 -12.72%
- lencod/lencod -11.51%
- Bullet/bullet -4.36%
- ClamAV/clamscan -3.66%
- 7zip/7zip-benchmark -3.19%
- sqlite3/sqlite3 -2.95%
- SPASS/SPASS -2.74%
- Average -5.81%

Performance testing:
The changes are expected to be neutral for runtime performance.

Reviewers: sanjoy, atrick, pete

Subscribers: llvm-commits

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

llvm-svn: 297992

show more ...

[SCEV] Decrease the recursion threshold for CompareValueComplexity

Fixes PR32142.

r287232 accidentally increased the recursion threshold for
CompareValueComplexity from 2 to 32. This change revers

[SCEV] Decrease the recursion threshold for CompareValueComplexity

Fixes PR32142.

r287232 accidentally increased the recursion threshold for
CompareValueComplexity from 2 to 32. This change reverses that change
by introducing a separate flag for CompareValueComplexity's threshold.

llvm-svn: 296992

show more ...

[SCEV] Cache results during GetMinTrailingZeros query

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

llvm-svn: 295060

[SCEV] limit recursion depth and operands number in getAddExpr

for a quite big function with source like

%add = add nsw i32 %mul, %conv
%mul1 = mul nsw i32 %add, %conv
%add2 = add nsw i32 %mul1, %a

[SCEV] limit recursion depth and operands number in getAddExpr

for a quite big function with source like

%add = add nsw i32 %mul, %conv
%mul1 = mul nsw i32 %add, %conv
%add2 = add nsw i32 %mul1, %add
%mul3 = mul nsw i32 %add2, %add
; repeat couple of thousands times
that can be produced by loop unroll, getAddExpr() tries to recursively construct SCEV and runs almost infinite time.

Added recursion depth restriction (with new parameter to set it)

Reviewers: sanjoy

Subscribers: hfinkel, llvm-commits, mzolotukhin

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

llvm-svn: 294181

show more ...

[SCEV] Simplify/generalize howFarToZero solving.

Make SolveLinEquationWithOverflow take the start as a SCEV, so we can
solve more cases. With that implemented, get rid of the special case
for powers

[SCEV] Simplify/generalize howFarToZero solving.

Make SolveLinEquationWithOverflow take the start as a SCEV, so we can
solve more cases. With that implemented, get rid of the special case
for powers of two.

The additional functionality probably isn't particularly useful,
but it might help a little for certain cases involving pointer
arithmetic.

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

llvm-svn: 293576

show more ...

Cleanup dump() functions.

We had various variants of defining dump() functions in LLVM. Normalize
them (this should just consistently implement the things discussed in
http://lists.llvm.org/pipermai

Cleanup dump() functions.

We had various variants of defining dump() functions in LLVM. Normalize
them (this should just consistently implement the things discussed in
http://lists.llvm.org/pipermail/cfe-dev/2014-January/034323.html

For reference:
- Public headers should just declare the dump() method but not use
LLVM_DUMP_METHOD or #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
- The definition of a dump method should look like this:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void MyClass::dump() {
// print stuff to dbgs()...
}
#endif

llvm-svn: 293359

show more ...

[SCEV] Introduce add operation inlining limit

Inlining in getAddExpr() can cause abnormal computational time in some cases.
New parameter -scev-addops-inline-threshold is intruduced with default val

[SCEV] Introduce add operation inlining limit

Inlining in getAddExpr() can cause abnormal computational time in some cases.
New parameter -scev-addops-inline-threshold is intruduced with default value 500.

Reviewers: sanjoy

Subscribers: mzolotukhin, llvm-commits

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

llvm-svn: 293176

show more ...

[SCEV] Make getUDivExactExpr handle non-nuw multiplies correctly.

To avoid regressions, make ScalarEvolution::createSCEV a bit more
clever.

Also get rid of some useless code in ScalarEvolution::how

[SCEV] Make getUDivExactExpr handle non-nuw multiplies correctly.

To avoid regressions, make ScalarEvolution::createSCEV a bit more
clever.

Also get rid of some useless code in ScalarEvolution::howFarToZero
which was hiding this bug.

No new testcase because it's impossible to actually expose this bug:
we don't have any in-tree users of getUDivExactExpr besides the two
functions I just mentioned, and they both dodged the problem. I'll
try to add some interesting users in a followup.

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

llvm-svn: 292449

show more ...

[SCEV] Limit recursion depth of constant evolving.

- For a loop body with VERY complicated exit condition evaluation, constant
evolving may run out of stack on platforms such as Windows. Need to l

[SCEV] Limit recursion depth of constant evolving.

- For a loop body with VERY complicated exit condition evaluation, constant
evolving may run out of stack on platforms such as Windows. Need to limit the
recursion depth.

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

llvm-svn: 291927

show more ...

[SCEV] Simplify SolveLinEquationWithOverflow a bit.

Cleanup in preparation for generalizing it.

llvm-svn: 291808

[SCEV] Make howFarToZero max backedge-taken count check for precondition.

Refines max backedge-taken count if a loop like
"for (int i = 0; i != n; ++i) { /* body */ }" is rotated.

Differential Revi

[SCEV] Make howFarToZero max backedge-taken count check for precondition.

Refines max backedge-taken count if a loop like
"for (int i = 0; i != n; ++i) { /* body */ }" is rotated.

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

llvm-svn: 291704

show more ...

[SCEV] Make howFarToZero use a simpler formula for max backedge-taken count.

This is both easier to understand, and produces a tighter bound in certain
cases.

Differential Revision: https://reviews

[SCEV] Make howFarToZero use a simpler formula for max backedge-taken count.

This is both easier to understand, and produces a tighter bound in certain
cases.

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

llvm-svn: 291701

show more ...

[PM] Teach SCEV to invalidate itself when its dependencies become
invalid.

This fixes use-after-free bugs that will arise with any interesting use
of SCEV.

I've added a dedicated test that works di

[PM] Teach SCEV to invalidate itself when its dependencies become
invalid.

This fixes use-after-free bugs that will arise with any interesting use
of SCEV.

I've added a dedicated test that works diligently to trigger these kinds
of bugs in the new pass manager and also checks for them explicitly as
well as triggering ASan failures when things go squirly.

llvm-svn: 291426

show more ...

[SCEV] Be less conservative when extending bitwidths for computing ranges.

Summary:
In getRangeForAffineAR we compute ranges for affine exprs E = A + B*C,
where ranges for A, B, and C are known. To

[SCEV] Be less conservative when extending bitwidths for computing ranges.

Summary:
In getRangeForAffineAR we compute ranges for affine exprs E = A + B*C,
where ranges for A, B, and C are known. To avoid overflow, we need to
operate on a bigger bitwidth, and originally we chose 2*x+1 for this
(x being the original bitwidth). However, it is safe to use just 2*x:

A+B*C <= (2^x - 1) + (2^x - 1)*(2^x - 1) =
= 2^x - 1 + 2^2x - 2^x - 2^x + 1 =
= 2^2x - 2^x <= 2^2x - 1

Unnecessary extending of bitwidths results in noticeable slowdowns: ranges
perform arithmetic operations using APInt, which are much slower when bitwidths
are bigger than 64.

Reviewers: sanjoy, majnemer, chandlerc

Subscribers: llvm-commits

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

llvm-svn: 290211

show more ...

Revert @llvm.assume with operator bundles (r289755-r289757)

This creates non-linear behavior in the inliner (see more details in
r289755's commit thread).

llvm-svn: 290086

Fix iterator-invalidation issue

Inserting a new key into a DenseMap potentially invalidates iterators into that
map. Trying to fix an issue from r289755 triggering this assertion:

Assertion `isHa

Fix iterator-invalidation issue

Inserting a new key into a DenseMap potentially invalidates iterators into that
map. Trying to fix an issue from r289755 triggering this assertion:

Assertion `isHandleInSync() && "invalid iterator access!"' failed.

llvm-svn: 289757

show more ...

Remove the AssumptionCache

After r289755, the AssumptionCache is no longer needed. Variables affected by
assumptions are now found by using the new operand-bundle-based scheme. This
new scheme is mo

Remove the AssumptionCache

After r289755, the AssumptionCache is no longer needed. Variables affected by
assumptions are now found by using the new operand-bundle-based scheme. This
new scheme is more computationally efficient, and also we need much less
code...

llvm-svn: 289756

show more ...

Make processing @llvm.assume more efficient by using operand bundles

There was an efficiency problem with how we processed @llvm.assume in
ValueTracking (and other places). The AssumptionCache track

Make processing @llvm.assume more efficient by using operand bundles

There was an efficiency problem with how we processed @llvm.assume in
ValueTracking (and other places). The AssumptionCache tracked all of the
assumptions in a given function. In order to find assumptions relevant to
computing known bits, etc. we searched every assumption in the function. For
ValueTracking, that means that we did O(#assumes * #values) work in InstCombine
and other passes (with a constant factor that can be quite large because we'd
repeat this search at every level of recursion of the analysis).

Several of us discussed this situation at the last developers' meeting, and
this implements the discussed solution: Make the values that an assume might
affect operands of the assume itself. To avoid exposing this detail to
frontends and passes that need not worry about it, I've used the new
operand-bundle feature to add these extra call "operands" in a way that does
not affect the intrinsic's signature. I think this solution is relatively
clean. InstCombine adds these extra operands based on what ValueTracking, LVI,
etc. will need and then those passes need only search the users of the values
under consideration. This should fix the computational-complexity problem.

At this point, no passes depend on the AssumptionCache, and so I'll remove
that as a follow-up change.

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

llvm-svn: 289755

show more ...

Revert "[SCEVExpand] do not hoist divisions by zero (PR30935)"

Reverts r289412. It caused an OOB PHI operand access in instcombine when
ASan is enabled. Reduction in progress.

Also reverts "[SCEVEx

Revert "[SCEVExpand] do not hoist divisions by zero (PR30935)"

Reverts r289412. It caused an OOB PHI operand access in instcombine when
ASan is enabled. Reduction in progress.

Also reverts "[SCEVExpander] Add a test case related to r289412"

llvm-svn: 289453

show more ...

[SCEVExpand] do not hoist divisions by zero (PR30935)

SCEVExpand computes the insertion point for the components of a SCEV to be code
generated. When it comes to generating code for a division, SCE

[SCEVExpand] do not hoist divisions by zero (PR30935)

SCEVExpand computes the insertion point for the components of a SCEV to be code
generated. When it comes to generating code for a division, SCEVexpand would
not be able to check (at compilation time) all the conditions necessary to avoid
a division by zero. The patch disables hoisting of expressions containing
divisions by anything other than non-zero constants in order to avoid hoisting
these expressions past conditions that should hold before doing the division.

The patch passes check-all on x86_64-linux.

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

llvm-svn: 289412

show more ...