[Polly] Don't generate inter-iteration noalias metadata.

This metadata was intended to mark all accesses within an iteration to be pairwise non-aliasing, in this case because every memory of a base

[Polly] Don't generate inter-iteration noalias metadata.

This metadata was intended to mark all accesses within an iteration to be pairwise non-aliasing, in this case because every memory of a base pointer is touched (read or write) at most once. This is typical for 'sweeps' over all data. The stated motivation from D30606 is to ensure that unrolled iterations are considered non-aliasing.

Rhe implemention had multiple issues:

* The structure of the noalias metadata was malformed. D110026 added check in the verifier for this metadata, and the tests were failing since then.

* This is not true for the outer loops of the BLIS matrix multiplication, where it was being inserted. Each element of A, B, C is accessed multiple times, as often as the loop not used as an index is iterating.

* Scopes were added to SecondLevelOtherAliasScopeList (used for the !noalias scop list) on-the-fly when another SCEV was seen. This meant that previously visited instructions would not be updated with alias scopes that are only seen later, missing out those SCEVs they should not be aliasing with.

* Since the !noalias scope list would ideally consists of all other SCEV for this base pointer, we might run quickly into scalability issues. Especially after unrolling there would probably at least once SCEV per instruction and unroll instance.

* The inter-iteration noalias base pointer was not removed after leaving the loop marked with it, effectively marking everything after it to noalias as well.

A solution I considered was to mark each instruction as non-aliasing with its own scope. The instruction itself would obviously alias itself, but such construction might also be considered invalid. Duplicating the instruction (e.g. due to speculation) would mark the instruction non-aliasing with its clone. I don't want to go into this territory, especially since the original motivation of determining unrolled instances as noalias based on SCEV is the what scev-aa does as well.

This effectively reverts D30606 and D35761.

show more ...

[Polly] Partially fix scoped alias metadata

This partially addresses the verifier failures caused by D110026.
In particular, it does not fix the "second level" alias metadata.

[Polly][Optimizer] Apply user-directed unrolling.

Make Polly look for unrolling metadata (https://llvm.org/docs/TransformMetadata.html#loop-unrolling) that is usually only interpreted by the LoopUnr

[Polly][Optimizer] Apply user-directed unrolling.

Make Polly look for unrolling metadata (https://llvm.org/docs/TransformMetadata.html#loop-unrolling) that is usually only interpreted by the LoopUnroll pass and apply it to the SCoP's schedule.

While not that useful by itself (there already is an unroll pass), it introduces mechanism to apply arbitrary loop transformation directives in arbitrary order to the schedule. Transformations are applied until no more directives are found. Since ISL's rescheduling would discard the manual transformations and it is assumed that when the user specifies the sequence of transformations, they do not want any other transformations to apply. Applying user-directed transformations can be controlled using the `-polly-pragma-based-opts` switch and is enabled by default.

This does not influence the SCoP detection heuristic. As a consequence, loop that do not fulfill SCoP requirements or the initial profitability heuristic will be ignored. `-polly-process-unprofitable` can be used to disable the latter.

Other than manually editing the IR, there is currently no way for the user to add loop transformations in an order other than the order in the default pipeline, or transformations other than the one supported by clang's LoopHint. See the `unroll_double.ll` test as example that clang currently is unable to emit. My own extension of `#pragma clang loop` allowing an arbitrary order and additional transformations is available here: https://github.com/meinersbur/llvm-project/tree/pragma-clang-loop. An effort to upstream this functionality as `#pragma clang transform` (because `#pragma clang loop` has an implicit transformation order defined by the loop pipeline) is D69088.

Additional transformations from my downstream pragma-clang-loop branch are tiling, interchange, reversal, unroll-and-jam, thread-parallelization and array packing. Unroll was chosen because it uses already-defined metadata and does not require correctness checks.

Reviewed By: sebastiankreutzer

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

show more ...

[Polly][Codegen] Emit access group metadata.

Emit llvm.loop.parallel_accesses metadata instead of
llvm.mem.parallel_loop_access. The latter is deprecated because it
assumes that LoopIDs are persiste

[Polly][Codegen] Emit access group metadata.

Emit llvm.loop.parallel_accesses metadata instead of
llvm.mem.parallel_loop_access. The latter is deprecated because it
assumes that LoopIDs are persistent, which they are not.
We also emit parallel access metadata for all surrounding parallel
loops, not just the innermost parallel.

show more ...

[Polly][CodeGen] Remove use of ScalarEvolution.

ScalarEvolution::getSCEV cannot be used during codegen. ScalarEvolution
assumes a stable IR and control flow which is under construction during
Polly'

[Polly][CodeGen] Remove use of ScalarEvolution.

ScalarEvolution::getSCEV cannot be used during codegen. ScalarEvolution
assumes a stable IR and control flow which is under construction during
Polly's CodeGen. In particular, it uses DominatorTree for compute the
backedge taken count. However the DominatorTree is not updated during
codegen.

In this case, SCEV was used to determine the base pointer of an array
access. Replace it by our own function. Polly generates only GEP and
BitCasts for array acceses, i.e. it is sufficient to handle these to to
find the base pointer.

Fixes llvm.org/PR48422

show more ...

Avoid unnecessary uses of `MDNode::getTemporary`, NFC

This is a long-delayed follow-up to
5e5b85098dbeaea2cfa5d01695b5d2982634d7dd.

`TempMDNode` includes a bunch of machinery for RAUW, and should o

Avoid unnecessary uses of `MDNode::getTemporary`, NFC

This is a long-delayed follow-up to
5e5b85098dbeaea2cfa5d01695b5d2982634d7dd.

`TempMDNode` includes a bunch of machinery for RAUW, and should only be
used when necessary. RAUW wasn't being used in any of these cases... it
was just a placeholder for a self-reference.

Where the real node was using `MDNode::getDistinct`, just replace the
temporary argument with `nullptr`.

Where the real node was using `MDNode::get`, the `replaceOperandWith`
call was "promoting" the node to a distinct one implicitly due to
self-reference detection in `MDNode::handleChangedOperand`. The
`TempMDNode` was serving a purpose by delaying uniquing, but it's way
simpler to just call `MDNode::getDistinct` in the first place.

Note that using a self-reference at all in these places is a hold-over
from before `distinct` metadata existed. It was an old trick to create
distinct nodes. It would be intrusive to change, including bitcode
upgrades, etc., and it's harmless so I'm not sure there's much value in
removing it from existing schemas. After this commit it still has a tiny
memory cost (in the extra metadata operand) but no more overhead in
construction.

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

show more ...

Apply include-what-you-use #include removal suggestions. NFC.

This removes unused includes (and forward declarations) as
suggested by include-what-you-use. If a transitive include of a removed
inclu

Apply include-what-you-use #include removal suggestions. NFC.

This removes unused includes (and forward declarations) as
suggested by include-what-you-use. If a transitive include of a removed
include is required to compile a file, I added the required header (or
forward declaration if suggested by include-what-you-use).

This should reduce compilation time and reduce the number of iterative
recompilations when a header was changed.

llvm-svn: 357209

show more ...

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the ne

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the new license. We checked this carefully with the
Foundation's lawyer and we believe this is the correct approach.

Essentially, all code in the project is now made available by the LLVM
project under our new license, so you will see that the license headers
include that license only. Some of our contributors have contributed
code under our old license, and accordingly, we have retained a copy of
our old license notice in the top-level files in each project and
repository.

llvm-svn: 351636

show more ...

[CodeGen] Fix potential null pointer dereference. NFC.

ScalarEvolution::getSCEV dereferences its argument, s.t. passing nullptr
leads to undefined behaviour.

Check for nullptr before calling it ins

[CodeGen] Fix potential null pointer dereference. NFC.

ScalarEvolution::getSCEV dereferences its argument, s.t. passing nullptr
leads to undefined behaviour.

Check for nullptr before calling it instead of checking its argument
afterwards.

llvm-svn: 336350

show more ...

[CodeGen] Fix noalias annotations for memcpy/memmove.

Memory transfer instructions take two pointers. It is not defined to
which of those a noalias annotation applies. To ensure correctness,
do not

[CodeGen] Fix noalias annotations for memcpy/memmove.

Memory transfer instructions take two pointers. It is not defined to
which of those a noalias annotation applies. To ensure correctness,
do not add noalias annotations to memcpy/memmove instructions anymore.

The caused a miscompile with test-suite's MultiSource/Applications/obsequi.
Since r321138, the MemCpyOpt pass would remove memcpy/memmove calls if
known to copy uninitialized memory. In that case, it was initialized
by another memcpy, but the annotation for the target pointer said
it would not alias. The annotation was actually meant for the source
pointer, which was was an alloca and could not alias with the target
pointer.

llvm-svn: 321371

show more ...

[IRBuilder] Only emit alias scop metadata for arrays, but not scalars

Summary:
There is no need to emit alias metadata for scalars, as basicaa will easily
distinguish them from arrays. This reduces

[IRBuilder] Only emit alias scop metadata for arrays, but not scalars

Summary:
There is no need to emit alias metadata for scalars, as basicaa will easily
distinguish them from arrays. This reduces the size of the metadata we generate.
This is especially useful after we moved to -polly-position=before-vectorizer,
where a lot more scalar dependences are introduced, which increased the size of
the alias analysis metadata and made us commonly reach the limits after which
we do not emit alias metadata that have been introduced to prevent quadratic
growth of this alias metadata.

This improves 2mm performance from 1.5 seconds to 0.17 seconds.

Reviewers: Meinersbur, bollu, singam-sanjay

Reviewed By: Meinersbur

Subscribers: pollydev, llvm-commits

Tags: #polly

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

llvm-svn: 311498

show more ...

Disable the Loop Vectorizer in case of GEMM

Currently, in case of GEMM and the pattern matching based optimizations, we
use only the SLP Vectorizer out of two LLVM vectorizers. Since the Loop
Vector

Disable the Loop Vectorizer in case of GEMM

Currently, in case of GEMM and the pattern matching based optimizations, we
use only the SLP Vectorizer out of two LLVM vectorizers. Since the Loop
Vectorizer can get in the way of optimal code generation, we disable the Loop
Vectorizer for the innermost loop using mark nodes and emitting the
corresponding metadata.

Reviewed-by: Tobias Grosser <[email protected]>

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

llvm-svn: 311473

show more ...

Use SCEV information for the second level aliasing

We introduce another level of alias metadata to distinguish the individual
non-aliasing accesses that have inter iteration alias-free base pointers

Use SCEV information for the second level aliasing

We introduce another level of alias metadata to distinguish the individual
non-aliasing accesses that have inter iteration alias-free base pointers
marked with "Inter iteration alias-free" mark nodes. To distinguish two
accesses, the comparison of raw pointers representing base pointers is used.

In case of, for example, ublas's prod function that implements GEMM, and
DeLiCM we can get accesses to same location represented by different raw
pointers. Consequently, we create different alias sets that can prevent
accesses from, for example, being sinked or hoisted.

To avoid the issue, we compare the corresponding SCEV information instead
of the corresponding raw pointers.

Reviewed-by: Tobias Grosser <[email protected]>

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

llvm-svn: 310380

show more ...

[CodeGen] Emit aliasing metadata for new arrays.

Ensure that all array base pointers are assigned before generating
aliasing metadata by allocating new arrays beforehand.

Before this patch, getBase

[CodeGen] Emit aliasing metadata for new arrays.

Ensure that all array base pointers are assigned before generating
aliasing metadata by allocating new arrays beforehand.

Before this patch, getBasePtr() returned nullptr for new arrays because
the arrays were created at a later point. Nullptr did not match to any
array after the created array base pointers have been assigned and when
the loads/stores are generated.

llvm-svn: 305675

show more ...

[PollyIRBuilder] Bound size of alias metadata

No-alias metadata grows quadratic in the size of arrays involved, which can
become very costly for large programs. This commit bounds the number of arra

[PollyIRBuilder] Bound size of alias metadata

No-alias metadata grows quadratic in the size of arrays involved, which can
become very costly for large programs. This commit bounds the number of arrays
for which we construct no-alias information to ten. This is conservatively
correct, as we just provide less information to LLVM and speeds up the compile
time of one of my internal test cases from 'does-not-terminate' to
'finishes-in-less-than-a-minute'. In the future we might try to be more clever
here, but this change should provide a good baseline.

llvm-svn: 299352

show more ...

Introduce another level of metadata to distinguish non-aliasing accesses

Introduce another level of alias metadata to distinguish the individual
non-aliasing accesses that have inter iteration alias

Introduce another level of metadata to distinguish non-aliasing accesses

Introduce another level of alias metadata to distinguish the individual
non-aliasing accesses that have inter iteration alias-free base pointers
marked with "Inter iteration alias-free" mark nodes. It can be used to,
for example, distinguish different stores (loads) produced by unrolling of
the innermost loops and, subsequently, sink (hoist) them by LICM.

Reviewed-by: Tobias Grosser <[email protected]>

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

llvm-svn: 298510

show more ...

[IRBuilder] Extract base pointers directly from ScopArray

Instead of iterating over statements and their memory accesses to extract the
set of available base pointers, just directly iterate over all

[IRBuilder] Extract base pointers directly from ScopArray

Instead of iterating over statements and their memory accesses to extract the
set of available base pointers, just directly iterate over all ScopArray
objects. This reflects more the actual intend of the code: collect all arrays
(and their base pointers) to emit alias information that specifies that accesses
to different arrays cannot alias.

This change removes unnecessary uses of MemoryAddress::getBaseAddr() in
preparation for https://reviews.llvm.org/D28518.

llvm-svn: 294574

show more ...

Perform copying to created arrays according to the packing transformation

This is the fourth patch to apply the BLIS matmul optimization pattern on matmul
kernels (http://www.cs.utexas.edu/users/fla

Perform copying to created arrays according to the packing transformation

This is the fourth patch to apply the BLIS matmul optimization pattern on matmul
kernels (http://www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf).
BLIS implements gemm as three nested loops around a macro-kernel, plus two
packing routines. The macro-kernel is implemented in terms of two additional
loops around a micro-kernel. The micro-kernel is a loop around a rank-1
(i.e., outer product) update. In this change we perform copying to created
arrays, which is the last step to implement the packing transformation.

Reviewed-by: Tobias Grosser <[email protected]>

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

llvm-svn: 281441

show more ...

Drop '@brief' from doxygen comments

LLVM's coding guideline suggests to not use @brief for one-sentence doxygen
comments to improve readability. Switch this once and for all to ensure people
do not

Drop '@brief' from doxygen comments

LLVM's coding guideline suggests to not use @brief for one-sentence doxygen
comments to improve readability. Switch this once and for all to ensure people
do not copy @brief comments from other parts of Polly, when writing new code.

llvm-svn: 280468

show more ...

Support calls with known ModRef function behaviour

Check the ModRefBehaviour of functions in order to decide whether or
not a call instruction might be acceptable.

Differential Revision: http:/

Support calls with known ModRef function behaviour

Check the ModRefBehaviour of functions in order to decide whether or
not a call instruction might be acceptable.

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

llvm-svn: 261866

show more ...

Introduce MemAccInst helper class; NFC

MemAccInst wraps the common members of LoadInst and StoreInst. Also use
of this class in:
- ScopInfo::buildMemoryAccess
- BlockGenerator::generateLocationAcces

Introduce MemAccInst helper class; NFC

MemAccInst wraps the common members of LoadInst and StoreInst. Also use
of this class in:
- ScopInfo::buildMemoryAccess
- BlockGenerator::generateLocationAccessed
- ScopInfo::addArrayAccess
- Scop::buildAliasGroups
- Replace every use of polly::getPointerOperand

Reviewers: jdoerfert, grosser

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

llvm-svn: 258947

show more ...

IRBuilder: Use Map.lookup instead of Map.find [NFC]

This simplifies the code.

Suggested-by: Johannes Doerfert
llvm-svn: 249545

IRBuilder: Ensure we do not add empty map elements

Do not use "Map[Key] == nullptr" to check if a Key is in the map, but use
"Map.find(Key) == Map.end()". Map[Key] always adds Key into the map, a
si

IRBuilder: Ensure we do not add empty map elements

Do not use "Map[Key] == nullptr" to check if a Key is in the map, but use
"Map.find(Key) == Map.end()". Map[Key] always adds Key into the map, a
side-effect we do not want.

Found by inspection. This is hard to test outside of a targetted unit test,
which seems too much overhead for this individual issue.

llvm-svn: 249544

show more ...

IRBuilder: Simplify code and reduce indention [NFC]

llvm-svn: 249543

Generate alias metadata even in OpenMP mode

To make alias scope metadata generation work in OpenMP mode we now provide
the ScopAnnotator with information about the base pointer rewrite that happens

Generate alias metadata even in OpenMP mode

To make alias scope metadata generation work in OpenMP mode we now provide
the ScopAnnotator with information about the base pointer rewrite that happens
when passing arrays into the OpenMP subfunction.

llvm-svn: 245451

show more ...