[Polly] Mark classes as final by default. NFC.

This make is obivious that a class was not intended to be derived from.

NPM analysis pass can unfortunately not marked as final because they are
deriv

[Polly] Mark classes as final by default. NFC.

This make is obivious that a class was not intended to be derived from.

NPM analysis pass can unfortunately not marked as final because they are
derived from a llvm::Checker<T> template internally by the NPM.

Also normalize the use of classes/structs
* NPM passes are structs
* Legacy passes are classes
* structs that have methods and are not a visitor pattern are classes
* structs have public inheritance by default, remove "public" keyword
* Use typedef'ed type instead of inline forward declaration

show more ...

Rename mayBeMemoryDependent in polly to fix build bot

This case was missed in ee7324b8.

[polly] Introduce -polly-print-* passes to replace -analyze.

The `opt -analyze` option only works with the legacy pass manager and might be removed in the future, as explained in llvm.org/PR53733. T

[polly] Introduce -polly-print-* passes to replace -analyze.

The `opt -analyze` option only works with the legacy pass manager and might be removed in the future, as explained in llvm.org/PR53733. This patch introduced -polly-print-* passes that print what the pass would print with the `-analyze` option and replaces all uses of `-analyze` in the regression tests.

There are two exceptions: `CodeGen\single_loop_param_less_equal.ll` and `CodeGen\loop_with_condition_nested.ll` use `-analyze on the `-loops` pass which is not part of Polly.

Reviewed By: aeubanks

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

show more ...

[polly] Match function definitions and header declarations. NFC.

Ensure that function definitions match their declrations in header
files, even if they have no effect on linking. This includes

1.

[polly] Match function definitions and header declarations. NFC.

Ensure that function definitions match their declrations in header
files, even if they have no effect on linking. This includes

1. Both have the same __isl_* annotations

2. Both use the same type alias

3. Remove unused declarations that have no definition

4. Use explicit polly namespace qualifier for definitions; generally,
the .cpp file should use at most an anon namespace region since
only symbols declared in the header file can be accessed from other
translation units anyway. For defintions that have been declared in
the header file, the explicit namespace qualifier ensures that both
match.

show more ...

[Polly][Isl] Use isl::union_map::unite() instead of isl::union_map::add_map(). NFC

This is part of an effort to reduce the differences between the custom C++ bindings used right now by polly in `lib

[Polly][Isl] Use isl::union_map::unite() instead of isl::union_map::add_map(). NFC

This is part of an effort to reduce the differences between the custom C++ bindings used right now by polly in `lib/External/isl/include/isl/isl-noxceptions.h` and the official isl C++ interface.

Changes made:
- Use `isl::union_map::unite()` instead of `isl::union_map::add_map()`
- `isl-noexceptions.h` has been generated by this https://github.com/patacca/isl/commit/3f43ae29fa2a22936a583b85b2fe8d439f805d8d

Depends on D106059

Reviewed By: Meinersbur

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

show more ...

[Polly][Isl] Removing explicit operator bool() from isl C++ bindings. NFC.

This is part of an effort to reduce the differences between the custom C++ bindings used right now by polly in `lib/Externa

[Polly][Isl] Removing explicit operator bool() from isl C++ bindings. NFC.

This is part of an effort to reduce the differences between the custom C++ bindings used right now by polly in `lib/External/isl/include/isl/isl-noxceptions.h` and the official isl C++ interface.

Changes made:
- Removing explicit operator bool() from all the classes in the isl C++ bindings.
- Replace each call to operator bool() to method `is_null()`.
- isl-noexceptions.h has been generated by this https://github.com/patacca/isl/commit/27396daac5a5ee8228d25511a12f4a814c92ba8f

Reviewed By: Meinersbur

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

show more ...

[Polly][Isl] Removing nullptr constructor from C++ bindings. NFC.

[Polly][Isl] Removing nullptr constructor from C++ bindings. NFC.

This is part of an effort to reduce the differences between the c

[Polly][Isl] Removing nullptr constructor from C++ bindings. NFC.

[Polly][Isl] Removing nullptr constructor from C++ bindings. NFC.

This is part of an effort to reduce the differences between the custom C++ bindings used right now by polly in `lib/External/isl/include/isl/isl-noxceptions.h` and the official isl C++ interface.

Changes made:
- Removed `std::nullptr_t` constructor from all the classes in the isl C++ bindings.
- `isl-noexceptions.h` has been generated by this https://github.com/patacca/isl/commit/a7e00bea38f251a4bcf5c2c6ce5fa7ee5f661528

Reviewed By: Meinersbur

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

show more ...

Revert "[Polly][Isl] Removing nullptr constructor from C++ bindings. NFC."

This reverts commit be5e2fc7bf781c7fc079943552ea1b519f45c815.

This introduced a building error for polly. https://lab.llvm

Revert "[Polly][Isl] Removing nullptr constructor from C++ bindings. NFC."

This reverts commit be5e2fc7bf781c7fc079943552ea1b519f45c815.

This introduced a building error for polly. https://lab.llvm.org/buildbot#builders/10/builds/4951

show more ...

[Polly][Isl] Removing nullptr constructor from C++ bindings. NFC.

[Polly][Isl] Removing nullptr constructor from C++ bindings. NFC.

This is part of an effort to reduce the differences between the c

[Polly][Isl] Removing nullptr constructor from C++ bindings. NFC.

[Polly][Isl] Removing nullptr constructor from C++ bindings. NFC.

This is part of an effort to reduce the differences between the custom C++ bindings used right now by polly in `lib/External/isl/include/isl/isl-noxceptions.h` and the official isl C++ interface.

Changes made:
- Removed `std::nullptr_t` constructor from all the classes in the isl C++ bindings.
- `isl-noexceptions.h` has been generated by this https://github.com/patacca/isl/commit/a7e00bea38f251a4bcf5c2c6ce5fa7ee5f661528

Reviewed By: Meinersbur

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

show more ...

[Polly] Port ForwardOpTree to the NewPM.

[Polly] Track defined behavior for PHI predecessor computation.

ZoneAlgorithms's computePHI relies on being provided with consistent a
schedule to compute the statement prodecessors of a statement c

[Polly] Track defined behavior for PHI predecessor computation.

ZoneAlgorithms's computePHI relies on being provided with consistent a
schedule to compute the statement prodecessors of a statement containing
PHINodes. Otherwise unexpected results such as PHI nodes with multiple
predecessors can occur which would result in problems in the
algorithms expecting consistent data.

In the added test case, statement instances are scrubbed from the
SCoP their execution would result in undefined behavior (Due to a nsw
overflow). As already being undefined behavior in LLVM-IR, neither
AssumedContext nor InvalidContext are updated, giving computePHI no
means to avoid these cases.

Intoduce a new SCoP property, the DefinedBehaviorContext, that among
the runtime-checked conditions, also tracks the assumptions not needing
a runtime check, in particular those affecting the assumed control flow.
This replaces the manual combination of the 3 other contexts that was
already done in computePHI and setNewAccessRelation. Currently, the only
additional assumption is that loop induction variables will nsw flag for
not wrap, but potentially more can be added. Use in
hasFeasibleRuntimeContext, isl::ast_build and gisting are other
potential uses.

To limit computational complexity, the DefinedBehaviorContext is not
availabe if it grows too large (atm hardcoded to 8 disjuncts).

Possible other fixes include bailing out in computePHI when
inconsistencies are detected, choose an arbitrary value for inconsistent
cases (since it is undefined behavior anyways), or make the code
receiving the result from ComputePHI handle inconsistent data. All of
them reduce the quality of implementation having to bail out more often
and disabling the ability to assert on actually wrong results.

This fixes llvm.org/PR48783.

show more ...

[Polly][OpTree] Fix mid-processing change of access kind.

Operand tree forwarding can cause the change of an access kind; in
particular change from a scalar kind to an array kind if the scalar
depen

[Polly][OpTree] Fix mid-processing change of access kind.

Operand tree forwarding can cause the change of an access kind; in
particular change from a scalar kind to an array kind if the scalar
dependency is not necessary. Such an access cannot and doesn't need to
be forwarded anymore.

Fixes llvm.org/PR48034

show more ...

[Polly][OpTree] Better report applied changes.

Print to dbgs() any taken action.

Also, read-only scalars do not require any action unless
-polly-analyze-read-only-scalars=true is used. Better refec

[Polly][OpTree] Better report applied changes.

Print to dbgs() any taken action.

Also, read-only scalars do not require any action unless
-polly-analyze-read-only-scalars=true is used. Better refect this by
using ForwardingAction::triviallyForwardable and thus not bumping the
statistics.

show more ...

[polly] Fix -Wunused-lambda-capture and -Wunused-variable

[Polly] Delete unused lambda capture after 7175cffb2133048018df74c1b49d1d4962ea18f2

[Polly] Reuse multiple uses in operand tree.

Recursively traversing the operand tree leads to an exponential blowup
if instructions are used multiple times due to every path leading to an
additional

[Polly] Reuse multiple uses in operand tree.

Recursively traversing the operand tree leads to an exponential blowup
if instructions are used multiple times due to every path leading to an
additional copy of the instructions after forwarding. This problem was
marked as a TODO in the code and was reported as a bug in llvm.org/PR47340.

Fix by caching already visited instructions and returning the cached
version when already visited. Instead of calling forwardTree() twice,
return a ForwardingAction structure that contains a lambda which will
carry-out the forwarding when requested. The lambdas are executed in
reverse-postorder to mimic the previous recursive calls unless there
is a reuse.

Fixes llvm.org/PR47340

show more ...

[Polly] Update ISL to isl-0.22.1-87-gfee05a13.

The primary motivation is to fix an assertion failure in
isl_basic_map_alloc_equality:

isl_assert(ctx, room_for_con(bmap, 1), return -1);

Althoug

[Polly] Update ISL to isl-0.22.1-87-gfee05a13.

The primary motivation is to fix an assertion failure in
isl_basic_map_alloc_equality:

isl_assert(ctx, room_for_con(bmap, 1), return -1);

Although the assertion does not occur anymore, I could not identify
which of ISL's commits fixed it.

Compared to the previous ISL version, Polly requires some changes for this update

* Since ISL commit
20d3574 "perform parameter alignment by modifying both arguments to function"
isl_*_gist_* and similar functions do not always align the paramter
list anymore. This caused the parameter lists in JScop files to
become out-of-sync. Since many regression tests use JScop files with
a fixed parameter list and order, we explicitly call align_params to
ensure a predictable parameter list.

* ISL changed some return types to isl_size, a typedef of (signed) int.
This caused some issues where the return type was unsigned int before:
- No overload for std::max(unsigned,isl_size)
- It cause additional 'mixed signed/unsigned comparison' warnings.
Since they do not break compilation, and sizes larger than 2^31
were never supported, I am going to fix it separately.

* With the change to isl_size, commit
57d547 "isl_*_list_size: return isl_size"
also changed the return value in case of an error from 0 to -1. This
caused undefined looping over isl_iterator since the 'end iterator'
got index -1, never reached from the 'begin iterator' with index 0.

* Some internal changes in ISL caused the number of operations to
increase when determining access ranges to determine aliasing
overlaps. In one test, this caused exceeding the default limit of
800000. The operations-limit was disabled for this test.

show more ...

Sink all InitializePasses.h includes

This file lists every pass in LLVM, and is included by Pass.h, which is
very popular. Every time we add, remove, or rename a pass in LLVM, it
caused lots of reco

Sink all InitializePasses.h includes

This file lists every pass in LLVM, and is included by Pass.h, which is
very popular. Every time we add, remove, or rename a pass in LLVM, it
caused lots of recompilation.

I found this fact by looking at this table, which is sorted by the
number of times a file was changed over the last 100,000 git commits
multiplied by the number of object files that depend on it in the
current checkout:
recompiles touches affected_files header
342380 95 3604 llvm/include/llvm/ADT/STLExtras.h
314730 234 1345 llvm/include/llvm/InitializePasses.h
307036 118 2602 llvm/include/llvm/ADT/APInt.h
213049 59 3611 llvm/include/llvm/Support/MathExtras.h
170422 47 3626 llvm/include/llvm/Support/Compiler.h
162225 45 3605 llvm/include/llvm/ADT/Optional.h
158319 63 2513 llvm/include/llvm/ADT/Triple.h
140322 39 3598 llvm/include/llvm/ADT/StringRef.h
137647 59 2333 llvm/include/llvm/Support/Error.h
131619 73 1803 llvm/include/llvm/Support/FileSystem.h

Before this change, touching InitializePasses.h would cause 1345 files
to recompile. After this change, touching it only causes 550 compiles in
an incremental rebuild.

Reviewers: bkramer, asbirlea, bollu, jdoerfert

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

show more ...

[Polly] Migrate llvm::make_unique to std::make_unique

Now that we've moved to C++14, we no longer need the llvm::make_unique
implementation from STLExtras.h. This patch is a mechanical replacement
o

[Polly] Migrate llvm::make_unique to std::make_unique

Now that we've moved to C++14, we no longer need the llvm::make_unique
implementation from STLExtras.h. This patch is a mechanical replacement
of (hopefully) all the llvm::make_unique instances across the monorepo.

Differential revision: https://reviews.llvm.org/D66259

llvm-svn: 368935

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

[ForwardOpTree] Replace isl foreach calls with for loops

llvm-svn: 337242

[ZoneAlgo] Use getDefToTarget in makeValInst. NFC.

Move the optimized getDefToTarget() from ForwardOpTree to ZoneAlgo such
that it can be used by makeValInst.

This reduces the compile time of GrTes

[ZoneAlgo] Use getDefToTarget in makeValInst. NFC.

Move the optimized getDefToTarget() from ForwardOpTree to ZoneAlgo such
that it can be used by makeValInst.

This reduces the compile time of GrTestUtils of the aosp buildbot from
2m46s to 21s, which should fix the timeout issue.

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

llvm-svn: 335606

show more ...

[OpTree] Introduce shortcut for computing the def->target mapping. NFCI.

In case the schedule has not changed and the operand tree root uses a
value defined in an ancestor loop, the def-to-target ma

[OpTree] Introduce shortcut for computing the def->target mapping. NFCI.

In case the schedule has not changed and the operand tree root uses a
value defined in an ancestor loop, the def-to-target mapping is trivial.
For instance, the SCoP

for (int i < 0; i < N; i+=1) {
DefStmt:
D = ...;
for (int j < 0; j < N; j+=1) {
TargetStmt:
use(D);
}
}

has DefStmt-to-TargetStmt mapping of

{ DefStmt[i] -> TargetStmt[i,j] }

This should apply on the majority of def-to-target mappings.
This patch detects this case and directly constructs the expected
mapping. It assumes that the mapping never crosses the loop header
DefStmt is in, which ForwardOpTree does not support at the moment
anyway.

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

llvm-svn: 334134

show more ...

[ZoneAlgo] Make ZoneAlgorithm::isNormalized out-of-quota safe.

The aosp-O3-polly-before-vectorizer-unprofitable buildbot currently
fails in ZoneAlgorithm::isNormalized, presumably because an
out-of-

[ZoneAlgo] Make ZoneAlgorithm::isNormalized out-of-quota safe.

The aosp-O3-polly-before-vectorizer-unprofitable buildbot currently
fails in ZoneAlgorithm::isNormalized, presumably because an
out-of-quota happens in that function.

Modify ZoneAlgorithm::isNormalized to return an isl::boolean such
it can report an error.

In the failing case, it was called in an assertion in ForwardOpTree.
Allow to pass the assertion in an out-of-quota event, a condition that
is later checked before forwarding an operand tree.

llvm-svn: 333709

show more ...