Remove \brief commands from doxygen comments.

We've been running doxygen with the autobrief option for a couple of
years now. This makes the \brief markers into our comments
redundant. Since they ar

Remove \brief commands from doxygen comments.

We've been running doxygen with the autobrief option for a couple of
years now. This makes the \brief markers into our comments
redundant. Since they are a visual distraction and we don't want to
encourage more \brief markers in new code either, this patch removes
them all.

Patch produced by

for i in $(git grep -l '\\brief'); do perl -pi -e 's/\\brief //g' $i & done

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

llvm-svn: 331272

show more ...

[LoopVersioning] Require loop-simplify form for loop versioning.

Summary:
Requiring loop-simplify form for loop versioning ensures that the
runtime check block always dominates the exit block.

[LoopVersioning] Require loop-simplify form for loop versioning.

Summary:
Requiring loop-simplify form for loop versioning ensures that the
runtime check block always dominates the exit block.

This patch closes #30958 (https://llvm.org/bugs/show_bug.cgi?id=30958).

Reviewers: silviu.baranga, hfinkel, anemet, ashutosh.nema

Subscribers: ashutosh.nema, mzolotukhin, efriedma, hfinkel, llvm-commits

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

llvm-svn: 290116

show more ...

Rename LoopAccessAnalysis to LoopAccessLegacyAnalysis /NFC

llvm-svn: 274927

[PM] refactor LoopAccessInfo code part-2

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

llvm-svn: 274334

[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

[LoopVer] Remove an assert that's redundant now. NFC

Ensuring that the PHI are all single-operand is not performed in the
second pass added by the previous pass. This removes the assert from
the fi

[LoopVer] Remove an assert that's redundant now. NFC

Ensuring that the PHI are all single-operand is not performed in the
second pass added by the previous pass. This removes the assert from
the first pass.

llvm-svn: 272650

show more ...

[LoopVer] Update all existing PHIs in the exit block

We only used to add the edge from the cloned loop to PHIs that
corresponded to values defined by the loop. We need to do this for all
PHIs obvio

[LoopVer] Update all existing PHIs in the exit block

We only used to add the edge from the cloned loop to PHIs that
corresponded to values defined by the loop. We need to do this for all
PHIs obviously since we need a PHI operand for each incoming edge.

This includes things like PHIs with a constant value or with values
defined before the original loop (see the testcases).

After the patch the PHIs are added to the exit block in two passes.

In the first pass we ensure there is a single-operand (LCSSA) PHI for
each value defined by the loop.

In the second pass we loop through each (single-operand) PHI and add the
value for the edge from the cloned loop. If the value is defined in the
loop we'll use the cloned instruction from the cloned loop.

Fixes PR28037

llvm-svn: 272649

show more ...

Fix a typo in loop versioning.

Reviewers: ashutosh.nema

Subscribers: llvm-commits

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

llvm-svn: 272545

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

Remove some 'const' specifiers that do nothing but prevent moving the argument.

Found by clang-tidy's misc-move-const-arg. While there drop some
obsolete c_str() calls.

llvm-svn: 271181

[LoopVersioning] Relax an assert for LCSSA PHIs

When you have multiple LCSSA (single-operand) PHIs that are converted
into two-operand PHIs due to versioning, only assert that the PHI
currently bein

[LoopVersioning] Relax an assert for LCSSA PHIs

When you have multiple LCSSA (single-operand) PHIs that are converted
into two-operand PHIs due to versioning, only assert that the PHI
currently being converted has a single operand. I.e. we don't want to
check PHIs that were converted earlier in the loop.

Fixes PR27023.

Thanks to Karl-Johan Karlsson for the minimized testcase!

llvm-svn: 264081

show more ...

[LoopVectorize] Annotate versioned loop with noalias metadata

Summary:
Use the new LoopVersioning facility (D16712) to add noalias metadata in
the vector loop if we versioned with memchecks. This c

[LoopVectorize] Annotate versioned loop with noalias metadata

Summary:
Use the new LoopVersioning facility (D16712) to add noalias metadata in
the vector loop if we versioned with memchecks. This can enable some
optimization opportunities further down the pipeline (see the included
test or the benchmark improvement quoted in D16712).

The test also covers the bug I had in the initial version in D16712.

The vectorizer did not previously use LoopVersioning. The reason is
that the vectorizer performs its transformations in single shot. It
creates an empty single-block vector loop that it then populates with
the widened, if-converted instructions. Thus creating an intermediate
versioned scalar loop seems wasteful.

So this patch (rather than bringing in LoopVersioning fully) adds a
special interface to LoopVersioning to allow the vectorizer to add
no-alias annotation while still performing its own versioning.

As the vectorizer propagates metadata from the instructions in the
original loop to the vector instructions we also check the pointer in
the original instruction and see if LoopVersioning can add no-alias
metadata based on the issued memchecks.

Reviewers: hfinkel, nadav, mzolotukhin

Subscribers: mzolotukhin, llvm-commits

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

llvm-svn: 263744

show more ...

[LoopVersioning] Annotate versioned loop with noalias metadata

Summary:
If we decide to version a loop to benefit a transformation, it makes
sense to record the now non-aliasing accesses in the newl

[LoopVersioning] Annotate versioned loop with noalias metadata

Summary:
If we decide to version a loop to benefit a transformation, it makes
sense to record the now non-aliasing accesses in the newly versioned
loop. This allows non-aliasing information to be used by subsequent
passes.

One example is 456.hmmer in SPECint2006 where after loop distribution,
we vectorize one of the newly distributed loops. To vectorize we
version this loop to fully disambiguate may-aliasing accesses. If we
add the noalias markers, we can use the same information in a later DSE
pass to eliminate some dead stores which amounts to ~25% of the
instructions of this hot memory-pipeline-bound loop. The overall
performance improves by 18% on our ARM64.

The scoped noalias annotation is added in LoopVersioning. The patch
then enables this for loop distribution. A follow-on patch will enable
it for the vectorizer. Eventually this should be run by default when
versioning the loop but first I'd like to get some feedback whether my
understanding and application of scoped noalias metadata is correct.

Essentially my approach was to have a separate alias domain for each
versioning of the loop. For example, if we first version in loop
distribution and then in vectorization of the distributed loops, we have
a different set of memchecks for each versioning. By keeping the scopes
in different domains they can conveniently be defined independently
since different alias domains don't affect each other.

As written, I also have a separate domain for each loop. This is not
necessary and we could save some metadata here by using the same domain
across the different loops. I don't think it's a big deal either way.

Probably the best is to review the tests first to see if I mapped this
problem correctly to scoped noalias markers. I have plenty of comments
in the tests.

Note that the interface is prepared for the vectorizer which needs the
annotateInstWithNoAlias API. The vectorizer does not use LoopVersioning
so we need a way to pass in the versioned instructions. This is also
why the maps have to become part of the object state.

Also currently, we only have an AA-aware DSE after the vectorizer if we
also run the LTO pipeline. Depending how widely this triggers we may
want to schedule a DSE toward the end of the regular pass pipeline.

Reviewers: hfinkel, nadav, ashutosh.nema

Subscribers: mssimpso, aemerson, llvm-commits, mcrosier

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

llvm-svn: 263743

show more ...

[SCEV][LAA] Re-commit r260085 and r260086, this time with a fix for the memory
sanitizer issue. The PredicatedScalarEvolution's copy constructor
wasn't copying the Generation value, and was leaving i

[SCEV][LAA] Re-commit r260085 and r260086, this time with a fix for the memory
sanitizer issue. The PredicatedScalarEvolution's copy constructor
wasn't copying the Generation value, and was leaving it un-initialized.

Original commit message:

[SCEV][LAA] Add no wrap SCEV predicates and use use them to improve strided pointer detection

Summary:
This change adds no wrap SCEV predicates with:
- support for runtime checking
- support for expression rewriting:
(sext ({x,+,y}) -> {sext(x),+,sext(y)}
(zext ({x,+,y}) -> {zext(x),+,sext(y)}

Note that we are sign extending the increment of the SCEV, even for
the zext case. This is needed to cover the fairly common case where y would
be a (small) negative integer. In order to do this, this change adds two new
flags: nusw and nssw that are applicable to AddRecExprs and permit the
transformations above.

We also change isStridedPtr in LAA to be able to make use of
these predicates. With this feature we should now always be able to
work around overflow issues in the dependence analysis.

Reviewers: mzolotukhin, sanjoy, anemet

Subscribers: mzolotukhin, sanjoy, llvm-commits, rengolin, jmolloy, hfinkel

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

llvm-svn: 260112

show more ...

Revert r260086 and r260085. They have broken the memory
sanitizer bots.

llvm-svn: 260087

[LoopVersioning] Don't assert when there are no memchecks

We shouldn't assert when there are no memchecks, since we
can have SCEV checks. There is already an assert covering
the case where there are

[LoopVersioning] Don't assert when there are no memchecks

We shouldn't assert when there are no memchecks, since we
can have SCEV checks. There is already an assert covering
the case where there are no SCEV checks or memchecks.

This also changes the LAA pointer wrapping versioning test
to use the loop versioning pass (this was how I managed to
trigger the assert in the loop versioning pass).

llvm-svn: 260086

show more ...

[LoopVersioning] Expose loop versioning as a pass too

Summary:
LoopVersioning is a transform utility that transform passes can use to
run-time disambiguate may-aliasing accesses. I'd like to also ex

[LoopVersioning] Expose loop versioning as a pass too

Summary:
LoopVersioning is a transform utility that transform passes can use to
run-time disambiguate may-aliasing accesses. I'd like to also expose as
pass to allow it to be unit-tested.

I am planning to add support for non-aliasing annotation in
LoopVersioning and I'd like to be able to write tests directly using
this pass.

(After that feature is done, the pass could also be used to look for
optimization opportunities that are hidden behind incomplete alias
information at compile time.)

The pass drives LoopVersioning in its default way which is to fully
disambiguate may-aliasing accesses no matter how many checks are
required.

Reviewers: hfinkel, ashutosh.nema, sbaranga

Subscribers: zzheng, mssimpso, llvm-commits, sanjoy

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

llvm-svn: 259610

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 ...

[Utils] Put includes in correct order. NFC.

Summary:
Followed the guidelines in:
http://llvm.org/docs/CodingStandards.html#include-style

However, I noticed that uppercase named head

[Utils] Put includes in correct order. NFC.

Summary:
Followed the guidelines in:
http://llvm.org/docs/CodingStandards.html#include-style

However, I noticed that uppercase named headers come before lowercase ones
throughout the codebase. So kept them as is.

Patch by Mandeep Singh Grang <mgrang@codeaurora.org>

Reviewers: majnemer, davide, jmolloy, atrick

Subscribers: sanjoy

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

llvm-svn: 254005

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 ...

Move the canonical header to the top of its matching cpp file as per coding convention

This ensures that the header will be verified to be standalone (and
avoid mistakes like the one fixed in r25117

Move the canonical header to the top of its matching cpp file as per coding convention

This ensures that the header will be verified to be standalone (and
avoid mistakes like the one fixed in r251178)

llvm-svn: 251326

show more ...

TransformUtils: Remove implicit ilist iterator conversions, NFC

Continuing the work from last week to remove implicit ilist iterator
conversions. First related commit was probably r249767, with som

TransformUtils: Remove implicit ilist iterator conversions, NFC

Continuing the work from last week to remove implicit ilist iterator
conversions. First related commit was probably r249767, with some more
motivation in r249925. This edition gets LLVMTransformUtils compiling
without the implicit conversions.

No functional change intended.

llvm-svn: 250142

show more ...