[LLE] Don't hoist conditionally executed loads

If the load is conditional we can't hoist its 0-iteration instance to
the preheader because that would make it unconditional. Thus we would
access a m

[LLE] Don't hoist conditionally executed loads

If the load is conditional we can't hoist its 0-iteration instance to
the preheader because that would make it unconditional. Thus we would
access a memory location that the original loop did not access.

llvm-svn: 273991

show more ...

[LAA] Default getInfo to not speculate symbolic strides. NFC

Soon we won't be passing Strides to getInfo and then we'll have fewer
call sites to update.

llvm-svn: 272878

Revert r272194 No need for it if loop Analysis Manager is used

llvm-svn: 272243

[PM] Refector LoopAccessInfo analysis code

This is the preparation patch to port the analysis to new PM

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

llvm-svn: 272194

[LAA] Rename "isStridedPtr" with "getPtrStride". NFC.

Changing misleading function name was approved in http://reviews.llvm.org/D17268.
Patch by Roman Shirokiy.

llvm-svn: 269021

[LLE] Fix typo from r263058

This was meant to check unit stride for both the load and the store.

Thanks to Roman Shirokiy for noticing this.

llvm-svn: 268251

Re-commit optimization bisect support (r267022) without new pass manager support.

The original commit was reverted because of a buildbot problem with LazyCallGraph::SCC handling (not related to the

Re-commit optimization bisect support (r267022) without new pass manager support.

The original commit was reverted because of a buildbot problem with LazyCallGraph::SCC handling (not related to the OptBisect handling).

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

llvm-svn: 267231

show more ...

Revert "Initial implementation of optimization bisect support."

This reverts commit r267022, due to an ASan failure:

http://lab.llvm.org:8080/green/job/clang-stage2-cmake-RgSan_check/1549

llvm-s

Revert "Initial implementation of optimization bisect support."

This reverts commit r267022, due to an ASan failure:

http://lab.llvm.org:8080/green/job/clang-stage2-cmake-RgSan_check/1549

llvm-svn: 267115

show more ...

Initial implementation of optimization bisect support.

This patch implements a optimization bisect feature, which will allow optimizations to be selectively disabled at compile time in order to trac

Initial implementation of optimization bisect support.

This patch implements a optimization bisect feature, which will allow optimizations to be selectively disabled at compile time in order to track down test failures that are caused by incorrect optimizations.

The bisection is enabled using a new command line option (-opt-bisect-limit). Individual passes that may be skipped call the OptBisect object (via an LLVMContext) to see if they should be skipped based on the bisect limit. A finer level of control (disabling individual transformations) can be managed through an addition OptBisect method, but this is not yet used.

The skip checking in this implementation is based on (and replaces) the skipOptnoneFunction check. Where that check was being called, a new call has been inserted in its place which checks the bisect limit and the optnone attribute. A new function call has been added for module and SCC passes that behaves in a similar way.

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

llvm-svn: 267022

show more ...

[LLE] Check for mismatching types between the store and the load earlier

isDependenceDistanceOfOne asserts that the store and the load access
through the same type. This function is also used by
re

[LLE] Check for mismatching types between the store and the load earlier

isDependenceDistanceOfOne asserts that the store and the load access
through the same type. This function is also used by
removeDependencesFromMultipleStores so we need to make sure we filter
out mismatching types before reaching this point.

Now we do this when the initial candidates are gathered.

This is a refinement of the fix made in r262267.

Fixes PR27048.

llvm-svn: 264313

show more ...

[LLE] Add missed LoopSimplify dependence

The code assumed that we always had a preheader without making the pass
dependent on LoopSimplify.

Thanks to Mattias Eriksson V for reporting this.

llvm-sv

[LLE] Add missed LoopSimplify dependence

The code assumed that we always had a preheader without making the pass
dependent on LoopSimplify.

Thanks to Mattias Eriksson V for reporting this.

llvm-svn: 263173

show more ...

[LLE] Add missing check for unit stride

I somehow missed this. The case in GCC (global_alloc) was similar to
the new testcase except it had an array of structs rather than a two
dimensional array.

[LLE] Add missing check for unit stride

I somehow missed this. The case in GCC (global_alloc) was similar to
the new testcase except it had an array of structs rather than a two
dimensional array.

Fixes RP26885.

llvm-svn: 263058

show more ...

[LLE] Fix a comment

llvm-svn: 262270

[LLE] Fix SingleSource/Benchmarks/Polybench/stencils/jacobi-2d-imper with Polly

We can actually have dependences between accesses with different
underlying types. Bail in this case.

A test will fo

[LLE] Fix SingleSource/Benchmarks/Polybench/stencils/jacobi-2d-imper with Polly

We can actually have dependences between accesses with different
underlying types. Bail in this case.

A test will follow shortly.

llvm-svn: 262267

show more ...

[LoopLoadElim] Don't allow versioning when optForSize

This was requested in the review of D16300.

llvm-svn: 259861

[SCEV] Add and use SCEVConstant::getAPInt; NFCI

llvm-svn: 255921

[LLE] Use the PredicatedScalarEvolution interface to query SCEVs for dependences

Summary:
LAA uses the PredicatedScalarEvolution interface, so it can produce
forward/backward dependences having SCEV

[LLE] Use the PredicatedScalarEvolution interface to query SCEVs for dependences

Summary:
LAA uses the PredicatedScalarEvolution interface, so it can produce
forward/backward dependences having SCEVs that are AddRecExprs only after being
transformed by PredicatedScalarEvolution.

Use PredicatedScalarEvolution to get the expected expressions.

Reviewers: anemet

Subscribers: llvm-commits, sanjoy

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

llvm-svn: 255241

show more ...

Re-commit r255115, with the PredicatedScalarEvolution class moved to
ScalarEvolution.h, in order to avoid cyclic dependencies between the Transform
and Analysis modules:

[LV][LAA] Add a layer over S

Re-commit r255115, with the PredicatedScalarEvolution class moved to
ScalarEvolution.h, in order to avoid cyclic dependencies between the Transform
and Analysis modules:

[LV][LAA] Add a layer over SCEV to apply run-time checked knowledge on SCEV expressions

Summary:
This change creates a layer over ScalarEvolution for LAA and LV, and centralizes the
usage of SCEV predicates. The SCEVPredicatedLayer takes the statically deduced knowledge
by ScalarEvolution and applies the knowledge from the SCEV predicates. The end goal is
that both LAA and LV should use this interface everywhere.

This also solves a problem involving the result of SCEV expression rewritting when
the predicate changes. Suppose we have the expression (sext {a,+,b}) and two predicates
P1: {a,+,b} has nsw
P2: b = 1.

Applying P1 and then P2 gives us {a,+,1}, while applying P2 and the P1 gives us
sext({a,+,1}) (the AddRec expression was changed by P2 so P1 no longer applies).
The SCEVPredicatedLayer maintains the order of transformations by feeding back
the results of previous transformations into new transformations, and therefore
avoiding this issue.

The SCEVPredicatedLayer maintains a cache to remember the results of previous
SCEV rewritting results. This also has the benefit of reducing the overall number
of expression rewrites.

Reviewers: mzolotukhin, anemet

Subscribers: jmolloy, sanjoy, llvm-commits

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

llvm-svn: 255122

show more ...

Revert r255115 until we figure out how to fix the bot failures.

llvm-svn: 255117

[LV][LAA] Add a layer over SCEV to apply run-time checked knowledge on SCEV expressions

Summary:
This change creates a layer over ScalarEvolution for LAA and LV, and centralizes the
usage of SCEV pr

[LV][LAA] Add a layer over SCEV to apply run-time checked knowledge on SCEV expressions

Summary:
This change creates a layer over ScalarEvolution for LAA and LV, and centralizes the
usage of SCEV predicates. The SCEVPredicatedLayer takes the statically deduced knowledge
by ScalarEvolution and applies the knowledge from the SCEV predicates. The end goal is
that both LAA and LV should use this interface everywhere.

This also solves a problem involving the result of SCEV expression rewritting when
the predicate changes. Suppose we have the expression (sext {a,+,b}) and two predicates
P1: {a,+,b} has nsw
P2: b = 1.

Applying P1 and then P2 gives us {a,+,1}, while applying P2 and the P1 gives us
sext({a,+,1}) (the AddRec expression was changed by P2 so P1 no longer applies).
The SCEVPredicatedLayer maintains the order of transformations by feeding back
the results of previous transformations into new transformations, and therefore
avoiding this issue.

The SCEVPredicatedLayer maintains a cache to remember the results of previous
SCEV rewritting results. This also has the benefit of reducing the overall number
of expression rewrites.

Reviewers: mzolotukhin, anemet

Subscribers: jmolloy, sanjoy, llvm-commits

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

llvm-svn: 255115

show more ...

Allow LLE/LD and the loop versioning infrastructure to use SCEV predicates

Summary:
LAA currently generates a set of SCEV predicates that must be checked by users.
In the case of Loop Distribute/Loo

Allow LLE/LD and the loop versioning infrastructure to use SCEV predicates

Summary:
LAA currently generates a set of SCEV predicates that must be checked by users.
In the case of Loop Distribute/Loop Load Elimination, no such predicates could have
been emitted, since we don't allow stride versioning. However, in the future there
could be SCEV predicates that will need to be checked.

This change adds support for SCEV predicate versioning in the Loop Distribute, Loop
Load Eliminate and the loop versioning infrastructure.

Reviewers: anemet

Subscribers: mssimpso, sanjoy, llvm-commits

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

llvm-svn: 252467

show more ...

ADT: Remove last implicit ilist iterator conversions, NFC

Some implicit ilist iterator conversions have crept back into Analysis,
Transforms, Hexagon, and llvm-stress. This removes them.

I'll comm

ADT: Remove last implicit ilist iterator conversions, NFC

Some implicit ilist iterator conversions have crept back into Analysis,
Transforms, Hexagon, and llvm-stress. This removes them.

I'll commit a patch immediately after this to disallow them (in a
separate patch so that it's easy to revert if necessary).

llvm-svn: 252371

show more ...

Fix unused variable warning from r252017

llvm-svn: 252019

LLE 6/6: Add LoopLoadElimination pass

Summary:
The goal of this pass is to perform store-to-load forwarding across the
backedge of a loop. E.g.:

for (i)
A[i + 1] = A[i] + B[i]

=>

T =

LLE 6/6: Add LoopLoadElimination pass

Summary:
The goal of this pass is to perform store-to-load forwarding across the
backedge of a loop. E.g.:

for (i)
A[i + 1] = A[i] + B[i]

=>

T = A[0]
for (i)
T = T + B[i]
A[i + 1] = T

The pass relies on loop dependence analysis via LoopAccessAnalisys to
find opportunities of loop-carried dependences with a distance of one
between a store and a load. Since it's using LoopAccessAnalysis, it was
easy to also add support for versioning away may-aliasing intervening
stores that would otherwise prevent this transformation.

This optimization is also performed by Load-PRE in GVN without the
option of multi-versioning. As was discussed with Daniel Berlin in
http://reviews.llvm.org/D9548, this is inferior to a more loop-aware
solution applied here. Hopefully, we will be able to remove some
complexity from GVN/MemorySSA as a consequence.

In the long run, we may want to extend this pass (or create a new one if
there is little overlap) to also eliminate loop-indepedent redundant
loads and store that *require* versioning due to may-aliasing
intervening stores/loads. I have some motivating cases for store
elimination. My plan right now is to wait for MemorySSA to come online
first rather than using memdep for this.

The main motiviation for this pass is the 456.hmmer loop in SPECint2006
where after distributing the original loop and vectorizing the top part,
we are left with the critical path exposed in the bottom loop. Being
able to promote the memory dependence into a register depedence (even
though the HW does perform store-to-load fowarding as well) results in a
major gain (~20%). This gain also transfers over to x86: it's
around 8-10%.

Right now the pass is off by default and can be enabled
with -enable-loop-load-elim. On the LNT testsuite, there are two
performance changes (negative number -> improvement):

1. -28% in Polybench/linear-algebra/solvers/dynprog: the length of the
critical paths is reduced
2. +2% in Polybench/stencils/adi: Unfortunately, I couldn't reproduce this
outside of LNT

The pass is scheduled after the loop vectorizer (which is after loop
distribution). The rational is to try to reuse LAA state, rather than
recomputing it. The order between LV and LLE is not critical because
normally LV does not touch scalar st->ld forwarding cases where
vectorizing would inhibit the CPU's st->ld forwarding to kick in.

LoopLoadElimination requires LAA to provide the full set of dependences
(including forward dependences). LAA is known to omit loop-independent
dependences in certain situations. The big comment before
removeDependencesFromMultipleStores explains why this should not occur
for the cases that we're interested in.

Reviewers: dberlin, hfinkel

Subscribers: junbuml, dberlin, mssimpso, rengolin, sanjoy, llvm-commits

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

llvm-svn: 252017

show more ...