Remove redundaunt virtual specifiers (NFC)

Identified with tidy-modernize-use-override.

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

[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] Stop generating isl::union_{set,map} from isl::space. NFC

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

[Polly][Isl] Stop generating isl::union_{set,map} from isl::space. 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:
- Stop generating `isl::union_set` and isl::union_map` from `isl::space` and instead generate them from `isl::ctx`
- Disable clang-format on `isl-noexceptions.h`
- Removed `isl::union_{set,map}` generator from `isl::space` from `isl-noexceptions.h`
- `isl-noexceptions.h` has been generated by this https://github.com/patacca/isl/commit/87c3413b6f1d62ca3dddf716352f90a0b8533353

Reviewed By: Meinersbur

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

show more ...

[Polly][Isl] Use isl::union_set::unite() instead of isl::union_set::add_set(). 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_set::unite() instead of isl::union_set::add_set(). 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_set::unite()` instead of `isl::union_set::add_set()`
- `isl-noexceptions.h` has been generated by this https://github.com/patacca/isl/commit/390c44982b5cee7eb43f8f7a80e185e6d21466b2

Depends on D104994

Reviewed By: Meinersbur

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

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

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

[DeLICM] Use polly::singleton to allow empty result.

isl_map_from_union_map cannot determine the map's space if the union_map
is empty. polly::singleton was designed for this case. We pass the
expec

[DeLICM] Use polly::singleton to allow empty result.

isl_map_from_union_map cannot determine the map's space if the union_map
is empty. polly::singleton was designed for this case. We pass the
expected map space to avoid crashing in isl_map_from_union_map.

This fixes an issue found by the aosp buildbot. Thanks to Eli Friedman
for the reproducer.

llvm-svn: 361290

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

[polly] Update uses of DEBUG macro to LLVM_DEBUG.

The DEBUG() macro is very generic so it might clash with other projects.
The renaming was done as follows:
- git grep -l 'DEBUG' | xargs sed -i 's/\

[polly] Update uses of DEBUG macro to LLVM_DEBUG.

The DEBUG() macro is very generic so it might clash with other projects.
The renaming was done as follows:
- git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g'
- git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM

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

llvm-svn: 332352

show more ...

Remove the last uses of isl::give and isl::take

llvm-svn: 331126

[DeLICM] Remove uses of isl::give

llvm-svn: 331122

Use isl::manage_copy to simplify calls to isl::manage(isl_.._copy())

As part of this cleanup a couple of unnecessary isl::manage(obj.copy()) pattern
are eliminated as well.

We checked for all poten

Use isl::manage_copy to simplify calls to isl::manage(isl_.._copy())

As part of this cleanup a couple of unnecessary isl::manage(obj.copy()) pattern
are eliminated as well.

We checked for all potential cleanups by scanning for:

"grep -R isl::manage\( lib/ | grep copy"

llvm-svn: 325558

show more ...

[ZoneAlgo/ForwardOpTree] Normalize PHIs to their known incoming values.

Represent PHIs by their incoming values instead of an opaque value of
themselves. This allows ForwardOpTree to "look through"

[ZoneAlgo/ForwardOpTree] Normalize PHIs to their known incoming values.

Represent PHIs by their incoming values instead of an opaque value of
themselves. This allows ForwardOpTree to "look through" the PHIs and
forward the incoming values since forwardings PHIs is currently not
supported.

This is particularly useful to cope with PHIs inserted by GVN LoadPRE.
The incoming values all resolve to a load from a single array element
which then can be forwarded.

It should in theory also reduce spurious conflicts in value mapping
(DeLICM), but I have not yet found a profitable case yet, so it is
not included here.

To avoid transitive closure and potentially necessary overapproximations
of those, PHIs that may reference themselves are excluded from
normalization and keep their opaque self-representation.

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

llvm-svn: 317008

show more ...

[DeLICM] Do not try to map to multiple array elements.

Add check and skip when the store used to determine the target accesses
multiple array elements. Only a single array location should for
mappin

[DeLICM] Do not try to map to multiple array elements.

Add check and skip when the store used to determine the target accesses
multiple array elements. Only a single array location should for
mapping the scalar. Having multiple creates problems when deciding which
element to load from. While MemoryAccess::getAddressFunction() should
select just one of them, other problems arise in code that assumes
that there is just one target element per statement instance.

This fixes llvm.org/PR34989

This also reverts r313902 which fixed llvm.org/PR34485 also caused by
a non-functional target array element. This patch avoids the situation
to occur in the first place.

llvm-svn: 316432

show more ...

[DeLICM] Allow non-injective PHIRead->PHIWrite mapping.

Remove an assertion that tests the injectivity of the
PHIRead -> PHIWrite relation. That is, allow a single PHI write to be
used by multiple

[DeLICM] Allow non-injective PHIRead->PHIWrite mapping.

Remove an assertion that tests the injectivity of the
PHIRead -> PHIWrite relation. That is, allow a single PHI write to be
used by multiple PHI reads. This may happen due to some statements
containing the PHI write not having the statement instances that would
overwrite the previous incoming value due to (assumed/invalid) contexts.
This result in that PHI write is mapped to multiple targets which is not
supported. Codegen will select one one of the targets using
getAddressFunction(). However, the runtime check should protect us from
this case ever being executed.

We therefore allow injective PHI relations. Additional calculations to
detect/santitize this case would probably not be worth the compuational
effort.

This fixes llvm.org/PR34485

llvm-svn: 313902

show more ...

[DeLICM] Move some functions to isl++ [NFC]

llvm-svn: 312475