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

Fix a lot of typos. NFC.

llvm-svn: 304974

[CodeGen] Extend Performance Counter to track per-scop information.

Previously, we would generate one performance counter for all scops.
Now, we generate both the old information, as well as a per-s

[CodeGen] Extend Performance Counter to track per-scop information.

Previously, we would generate one performance counter for all scops.
Now, we generate both the old information, as well as a per-scop
performance counter to generate finer grained information.

This patch needed a way to generate a unique name for a `Scop`.
The start region, end region, and function name combined provides a
unique `Scop` name. So, `Scop` has a new public API to provide its start
and end region names.

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

llvm-svn: 304528

show more ...

[Polly][NewPM] Port CodeGen to the new PM

Summary: To move CG to the new PM I outlined the various helper that were previously members of the CG class into free static functions. The CG class itself

[Polly][NewPM] Port CodeGen to the new PM

Summary: To move CG to the new PM I outlined the various helper that were previously members of the CG class into free static functions. The CG class itself I moved into a header, which is required because we need to include it in `RegisterPasses` eventually.

Reviewers: grosser, Meinersbur

Reviewed By: grosser

Subscribers: pollydev, llvm-commits, sanjoy

Tags: #polly

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

llvm-svn: 303624

show more ...

[Polly][NewPM] Port IslAst to the new ScopPassManager

Summary: This patch ports IslAst to the new PM. The change is mostly straightforward. The only major modification required is making IslAst move

[Polly][NewPM] Port IslAst to the new ScopPassManager

Summary: This patch ports IslAst to the new PM. The change is mostly straightforward. The only major modification required is making IslAst move-only, to correctly manage the isl resources it owns.

Reviewers: grosser, Meinersbur

Reviewed By: grosser

Subscribers: nemanjai, pollydev, llvm-commits

Tags: #polly

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

llvm-svn: 303622

show more ...

[Polly][NewPM] Port ScopDetection to the new PassManager

Summary: This is a proof of concept of how to port polly-passes to the new PassManager architecture. This approach works ootb for Function-P

[Polly][NewPM] Port ScopDetection to the new PassManager

Summary: This is a proof of concept of how to port polly-passes to the new PassManager architecture. This approach works ootb for Function-Passes, but might not be directly applicable to Scop/Region-Passes. While we could just run the Analyses/Transforms over functions instead, we'd surrender the nice pipelining behaviour we have now.

Reviewers: Meinersbur, grosser

Reviewed By: grosser

Subscribers: pollydev, sanjoy, nemanjai, llvm-commits

Tags: #polly

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

llvm-svn: 302902

show more ...

[Codegen] Disable Polly's codegen verification by default

As has been reported in the previous commit, codegen verification can result in
quadratic compile time increases for large functions with ma

[Codegen] Disable Polly's codegen verification by default

As has been reported in the previous commit, codegen verification can result in
quadratic compile time increases for large functions with many scops. This is
certainly not something we would like to have in the Polly default
configuration. Hence, we disable codegen verification by default -- also to see
if this resolves some of the compilation timeouts we currently see on the AOSP
buildbots. We still leave this feature in Polly as it has shown _very_ useful
for debugging. In fact, we may want to have a discussion if we can bring this
feature back in a way that does not impact compilation time so much.

Thanks to Eli Friedman <[email protected]> for reporting this issue and
for providing the test case in the previous commit (where I forgot to
acknowledge him).

llvm-svn: 301670

show more ...

[CodeGen] Skip verify if -polly-codegen-verify is set to false

Before this change, we always tried to verify the function and printed
verification errors, but just did not abort in case -polly-codeg

[CodeGen] Skip verify if -polly-codegen-verify is set to false

Before this change, we always tried to verify the function and printed
verification errors, but just did not abort in case -polly-codegen-verify=false
was set and verification failed. As verification can become very cosly -- for
large functions with many scops we may verify the very same function very often
-- this can affect compile time very negatively. Hence, we respect the
-polly-codegen-verify flag with this check, ensuring that no verification is run
if -polly-codegen-verify=false.

This reduces code generation time from 26 seconds to 4 seconds on the test
case below with -polly-codegen-verify=false:

struct X { int x; };
void a();
#define SIG (int x, X **y, X **z)
typedef void (*fn)SIG;
#define FN { for (int i = 0; i < x; ++i) { (*y)[i].x += (*z)[i].x; } a(); }
#define FN5 FN FN FN FN FN
#define FN25 FN5 FN5 FN5 FN5
#define FN125 FN25 FN25 FN25 FN25 FN25
#define FN250 FN125 FN125
#define FN1250 FN250 FN250 FN250 FN250 FN250
void x SIG { FN1250 }

llvm-svn: 301669

show more ...

Remove llvm.lifetime.start/end in original region.

The current StackColoring algorithm does not correctly handle the
situation when some, but not all paths from a BB to the entry node
cross a llvm.l

Remove llvm.lifetime.start/end in original region.

The current StackColoring algorithm does not correctly handle the
situation when some, but not all paths from a BB to the entry node
cross a llvm.lifetime.start. According to an interpretation of the
language reference at
http://llvm.org/docs/LangRef.html#llvm-lifetime-start-intrinsic
this might be correct, but it would cost too much effort to handle
in StackColoring.

To be on the safe side, remove all lifetime markers even in the original
code version (they have never been copied to the optimized version)
to ensure that no path to the entry block will cross a
llvm.lifetime.start.

The same principle applies to paths the a function return and the
llvm.lifetime.end marker, so we remove them as well.

This fixes llvm.org/PR32251.

Also see the discussion at
http://lists.llvm.org/pipermail/llvm-dev/2017-March/111551.html

llvm-svn: 299585

show more ...

[Polly][NewPM] Pull references to the legacy PM interface from utilities and helpers

Summary:
A couple of the utilities used to analyze or build IR make explicit use of the legacy PM on their interf

[Polly][NewPM] Pull references to the legacy PM interface from utilities and helpers

Summary:
A couple of the utilities used to analyze or build IR make explicit use of the legacy PM on their interface, to access analysis results. This patch removes the legacy PM from the interface, and just passes the required results directly.

This shouldn't introduce any function changes, although the API technically allowed to obtain two different analysis results before, one passed by reference and one through the PM. I don't believe that was ever intended, however.

Reviewers: grosser, Meinersbur

Reviewed By: grosser

Subscribers: nemanjai, pollydev, llvm-commits

Tags: #polly

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

llvm-svn: 299423

show more ...

[CodeGen] Add Performance Monitor

Add support for -polly-codegen-perf-monitoring. When performance monitoring
is enabled, we emit performance monitoring code during code generation that
prints after

[CodeGen] Add Performance Monitor

Add support for -polly-codegen-perf-monitoring. When performance monitoring
is enabled, we emit performance monitoring code during code generation that
prints after program exit statistics about the total number of cycles executed
as well as the number of cycles spent in scops. This gives an estimate on how
useful polyhedral optimizations might be for a given program.

Example output:

Polly runtime information
-------------------------
Total: 783110081637
Scops: 663718949365

In the future, we might also add functionality to measure how much time is spent
in optimized scops and how many cycles are spent in the fallback code.

Reviewers: bollu,sebpop

Tags: #polly

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

llvm-svn: 299359

show more ...

Remove all references to PostDominators. NFC.

Marking a pass as preserved is necessary if any Polly pass uses it, even
if it is not preserved within the generated code. Not marking it would
cause th

Remove all references to PostDominators. NFC.

Marking a pass as preserved is necessary if any Polly pass uses it, even
if it is not preserved within the generated code. Not marking it would
cause the the Polly pass chain to be interrupted. It is not used by any
Polly pass anymore, hence we can remove all references to it.

llvm-svn: 295983

show more ...

[Polly CodeGen] Break critical edge from RTC to original loop.

This makes polly generate a CFG which is closer to what we want
in LLVM IR, with a loop preheader for the original loop. This is
just a

[Polly CodeGen] Break critical edge from RTC to original loop.

This makes polly generate a CFG which is closer to what we want
in LLVM IR, with a loop preheader for the original loop. This is
just a cleanup, but it exposes some fragile assumptions.

I'm not completely happy with the changes related to expandCodeFor;
RTCBB->getTerminator() is basically a random insertion point which
happens to work due to the way we generate runtime checks. I'm not
sure what the right answer looks like, though.

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

llvm-svn: 285864

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

[IslNodeBuilder] Move run-time check generation to NodeBuilder [NFC]

This improves the structure of the code and allows us to reuse the runtime
code generation in the PPCGCodeGeneration.

llvm-svn:

[IslNodeBuilder] Move run-time check generation to NodeBuilder [NFC]

This improves the structure of the code and allows us to reuse the runtime
code generation in the PPCGCodeGeneration.

llvm-svn: 278017

show more ...

[CodeGeneration] Do not set insert position redundantly

There is no need to reset the position of the builder, as we can just continue
to insert code at the current position of the IRBuilder, which

[CodeGeneration] Do not set insert position redundantly

There is no need to reset the position of the builder, as we can just continue
to insert code at the current position of the IRBuilder, which happens to
be precisely the location we reset the builder to.

llvm-svn: 278014

show more ...

Extend the jscop interface to allow the user to declare new arrays and to reference these arrays from access expressions

Extend the jscop interface to allow the user to export arrays. It is required

Extend the jscop interface to allow the user to declare new arrays and to reference these arrays from access expressions

Extend the jscop interface to allow the user to export arrays. It is required
that already existing arrays of the list of arrays correspond to arrays
of the SCoP. Each array that is appended to the list will be newly created.
Furthermore, we allow the user to modify access expressions to reference
any array in case it has the same element type.

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

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

llvm-svn: 277263

show more ...

IslNodeBuilder: Make finalize() virtual

This allows the finalization routine of the IslNodeBuilder to be overwritten
by derived classes. Being here, we also drop the unnecessary 'Scop' postfix
and t

IslNodeBuilder: Make finalize() virtual

This allows the finalization routine of the IslNodeBuilder to be overwritten
by derived classes. Being here, we also drop the unnecessary 'Scop' postfix
and the unnecessary 'Scop' parameter.

llvm-svn: 276622

show more ...

clang-tidy: Add llvm namespace comments

llvm commonly adds a comment to the closing brace of a namespace to indicate
which namespace is closed. clang-tidy provides with llvm-namespace-comment
a hand

clang-tidy: Add llvm namespace comments

llvm commonly adds a comment to the closing brace of a namespace to indicate
which namespace is closed. clang-tidy provides with llvm-namespace-comment
a handy tool to check for this habit. We use it to ensure we consitently use
namespace comments in Polly.

There are slightly different styles in how namespaces are closed in LLVM. As
there is no large difference between the different comment styles we go for the
style clang-tidy suggests by default.

To reproduce this fix run:

for i in `ls tools/polly/lib/*/*.cpp`; \
clang-tidy -checks='-*,llvm-namespace-comment' -p build $i -fix \
-header-filter=".*"; \
done

This cleanup was suggested by Eugene Zelenko <[email protected]> in
http://reviews.llvm.org/D21488 and was split out to increase readability.

llvm-svn: 273621

show more ...

This reverts recent expression type changes

The recent expression type changes still need more discussion, which will happen
on phabricator or on the mailing list. The precise list of commits revert

This reverts recent expression type changes

The recent expression type changes still need more discussion, which will happen
on phabricator or on the mailing list. The precise list of commits reverted are:

- "Refactor division generation code"
- "[NFC] Generate runtime checks after the SCoP"
- "[FIX] Determine insertion point during SCEV expansion"
- "Look through IntToPtr & PtrToInt instructions"
- "Use minimal types for generated expressions"
- "Temporarily promote values to i64 again"
- "[NFC] Avoid unnecessary comparison for min/max expressions"
- "[Polly] Fix -Wunused-variable warnings (NFC)"
- "[NFC] Simplify min/max expression generation"
- "Simplify the type adjustment in the IslExprBuilder"

Some of them are just reverted as we would otherwise get conflicts. I will try
to re-commit them if possible.

llvm-svn: 272483

show more ...

[NFC] Generate runtime checks after the SCoP

We now generate runtime checks __after__ the SCoP code generation and
not before, though they are still inserted at the same position int
the code.

[NFC] Generate runtime checks after the SCoP

We now generate runtime checks __after__ the SCoP code generation and
not before, though they are still inserted at the same position int
the code. This allows to modify the runtime check during SCoP code
generation.

llvm-svn: 271894

show more ...

[NFC] Simplify code

llvm-svn: 271889

Decouple SCoP building logic from pass

Created a new pass ScopInfoRegionPass. As name suggests, it is a
region pass and it is there to preserve compatibility with our
existing Polly passes. S

Decouple SCoP building logic from pass

Created a new pass ScopInfoRegionPass. As name suggests, it is a
region pass and it is there to preserve compatibility with our
existing Polly passes. ScopInfoRegionPass will return a SCoP object
for a valid region while the creation of the SCoP stays in the
ScopInfo class.

Contributed-by: Utpal Bora <[email protected]>
Reviewed-by: Tobias Grosser <[email protected]>,
Johannes Doerfert <[email protected]>

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

llvm-svn: 271259

show more ...

Duplicate part of the Region interface in the Scop class [NFC]

This allows to use the SCoP directly for various queries,
thus to hide the underlying region more often.

llvm-svn: 270426

Directly access information through the Scop class [NFC]

llvm-svn: 270421