[Polly] Do not inline dumpIslObj methods. NFC.

Instead of being inline and having a neverCalled() workaround to make it
work in the debugger, define it as a regular exported function.

Also add over

[Polly] Do not inline dumpIslObj methods. NFC.

Instead of being inline and having a neverCalled() workaround to make it
work in the debugger, define it as a regular exported function.

Also add overloads for the C API types isl_* so it works with managed as
well as unmanaged ISL objects.

show more ...

[Polly] Add greedy fusion algorithm.

When the option -polly-loopfusion-greedy is set, the ScheduleOptimizer
tries to aggressively fuse any band it can and does not violate any
dependences.

As part

[Polly] Add greedy fusion algorithm.

When the option -polly-loopfusion-greedy is set, the ScheduleOptimizer
tries to aggressively fuse any band it can and does not violate any
dependences.

As part if the implementation, the functionalty for copying a band
into an new schedule was extracted out of the ScheduleTreeRewriter.

show more ...

[Polly][Isl] Move to the new-polly-generator branch version of isl-noexceptions.h. NFCI

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

[Polly][Isl] Move to the new-polly-generator branch version of isl-noexceptions.h. NFCI

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.

With this commit we are moving from the `polly-generator` branch to the `new-polly-generator` branch that is more mantainable and is based on the official C++ interface `cpp-checked.h`.

Changes made:
- There are now many sublcasses for `isl::ast_node` representing different isl types. Use `isl::ast_node_for`, `isl::ast_node_user`, `isl::ast_node_block` and `isl::ast_node_mark` where needed.
- There are now many sublcasses for `isl::schedule_node` representing different isl types. Use `isl::schedule_node_mark`, `isl::schedule_node_extension`, `isl::schedule_node_band` and `isl::schedule_node_filter` where needed.
- Replace the `isl::*::dump` with `dumpIslObj` since the isl dump method is not exposed in the C++ interface.
- `isl::schedule_node::get_child` has been renamed to `isl::schedule_node::child`
- `isl::pw_multi_aff::get_pw_aff` has been renamed to `isl::pw_multi_aff::at`
- The constructor `isl::union_map(isl::union_pw_multi_aff)` has been replaced with the static method `isl::union_map::from()`
- Replace usages of `isl::val::add_ui` with `isl::val::add`
- `isl::union_set_list::alloc` is now a constructor
- All the `isl_size` values are now wrapped inside the class `isl::size` use `isl::size::release` to get the internal `isl_size` value where needed.
- `isl-noexceptions.h` has been generated by https://github.com/patacca/isl/commit/73f5ed1f4d1f72582f731590ef9e43d9ab1956ad

No functional change intended.

Reviewed By: Meinersbur

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

show more ...

[Polly][Isl] Replacing isl method `to_str()` with `stringFromIslObj()`. NFC.

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

[Polly][Isl] Replacing isl method `to_str()` with `stringFromIslObj()`. 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 method `to_str()` from all the classes in the isl C++ bindings.
- Overload method `stringFromIslObj()` so it accepts isl C++ objects.
- To keep backward compatibility `stringFromIslObj()` now accepts a value that is returned if the isl C object is `null` or doesn't have a string representation (by default it's an empty string). In some cases it's better to have the string "null" instead of an empty string.
- isl-noexceptions.h has been generated by this https://github.com/patacca/isl/commit/d33ec3a3bbaf971b254a853e6d8200ff9f5a1385

Reviewed By: Meinersbur

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

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

Do not call band_list().dump()

This is in preparation for the removal of band_list from isl.

llvm-svn: 325554

[Support] Force instantiation of isl dump() methods. NFC.

In order for debuggers to be able to call an inline method, it must have
been instantiated somewhere. The dump() methods are usually not use

[Support] Force instantiation of isl dump() methods. NFC.

In order for debuggers to be able to call an inline method, it must have
been instantiated somewhere. The dump() methods are usually not used, so
add an instantiation in debug builds.

This allows to call .dump() on any isl++ object from the gcc/gdb and
Visual Studio debugger in debug builds with assertions enabled.
In optimized builds, even with assertions enabled, the dump() methods
are also inlined in GICHelper.cpp, so no externally visible symbols
will be available either.

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

llvm-svn: 314395

show more ...

Fix a lot of typos. NFC.

llvm-svn: 304974

[DeLICM] Known knowledge.

Extend the Knowledge class to store information about the contents
of array elements and which values are written. Two knowledges do
not conflict the known content is the s

[DeLICM] Known knowledge.

Extend the Knowledge class to store information about the contents
of array elements and which values are written. Two knowledges do
not conflict the known content is the same. The content information
if computed from writes to and loads from the array elements, and
represented by "ValInst": isl spaces that compare equal if the value
represented is the same.

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

llvm-svn: 302339

show more ...

[ScopInfo] Do not use LLVM names to identify statements, arrays, and parameters

LLVM-IR names are commonly available in debug builds, but often not in release
builds. Hence, using LLVM-IR names to i

[ScopInfo] Do not use LLVM names to identify statements, arrays, and parameters

LLVM-IR names are commonly available in debug builds, but often not in release
builds. Hence, using LLVM-IR names to identify statements or memory reference
results makes the behavior of Polly depend on the compile mode. This is
undesirable. Hence, we now just number the statements instead of using LLVM-IR
names to identify them (this issue has previously been brought up by Zino
Benaissa).

However, as LLVM-IR names help in making test cases more readable, we add an
option '-polly-use-llvm-names' to still use LLVM-IR names. This flag is by
default set in the polly tests to make test cases more readable.

This change reduces the time in ScopInfo from 32 seconds to 2 seconds for the
following test case provided by Eli Friedman <[email protected]> (already
used in one of the previous commits):

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 }

For a larger benchmark I have on-hand (10000 loops), this reduces the time for
running -polly-scops from 5 minutes to 4 minutes, a reduction by 20%.

The reason for this large speedup is that our previous use of printAsOperand
had a quadratic cost, as for each printed and unnamed operand the full function
was scanned to find the instruction number that identifies the operand.

We do not need to adjust the way memory reference ids are constructured, as
they do not use LLVM values.

Reviewed by: efriedma

Tags: #polly

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

llvm-svn: 302072

show more ...

Use isl C++ foreach implementation

This commit switches Polly over to the isl::obj::foreach_* implementation, which
is part of the new isl bindings and follows the foreach pattern established in
Pol

Use isl C++ foreach implementation

This commit switches Polly over to the isl::obj::foreach_* implementation, which
is part of the new isl bindings and follows the foreach pattern established in
Polly by Michael Kruse.

The original isl C function:

isl_stat isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
isl_stat (*fn)(__isl_take isl_set *set, void *user), void *user);

which required the user to define a static callback function to which all
interesting parameters are passed via a 'void *' user-pointer, is on the
C++ side available as a function that takes a std::function<>, which can
carry any additional arguments without the need for a user pointer:

stat UnionSet::foreach_set(const std::function<stat(set)> &fn) const;

The following code illustrates the use of the new C++ interface:

auto Lambda = [=, &Result](isl::set Set) -> isl::stat {
auto Shifted = shiftDimension(Set, Pos, Amount);
Result = Result.add(Shifted);
return isl::stat::ok;
}

UnionSet.foreach_set(Lambda);

Polly had some specialized foreach functions which did not require the lambdas
to return a status flag. We remove these functions in this commit to move Polly
completely over to the new isl interface. We may in the future discuss if
functors without return values can be supported easily.

Another extension proposed by Michael Kruse is the use of C++ iterators to allow
the use of normal for loops to iterate over these sets. Such an extension would
allow us to further simplify the code.

Reviewed-by: Michael Kruse <[email protected]>

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

llvm-svn: 300323

show more ...

Introduce isl C++ bindings, Part 1: value_ptr style interface

Over the last couple of months several authors of independent isl C++ bindings
worked together to jointly design an official set of isl

Introduce isl C++ bindings, Part 1: value_ptr style interface

Over the last couple of months several authors of independent isl C++ bindings
worked together to jointly design an official set of isl C++ bindings which
combines their experience in developing isl C++ bindings. The new bindings have
been designed around a value pointer style interface and remove the need for
explicit pointer managenent and instead use C++ language features to manage isl
objects.

This commit introduces the smart-pointer part of the isl C++ bindings and
replaces the current IslPtr<T> classes, which served the very same purpose, but
had to be manually maintained. Instead, we now rely on automatically generated
classes for each isl object, which provide value_ptr semantics.

An isl object has the following smart pointer interface:

inline set manage(__isl_take isl_set *ptr);

class set {
friend inline set manage(__isl_take isl_set *ptr);
isl_set *ptr = nullptr;
inline explicit set(__isl_take isl_set *ptr);

public:
inline set();
inline set(const set &obj);
inline set &operator=(set obj);
inline ~set();
inline __isl_give isl_set *copy() const &;
inline __isl_give isl_set *copy() && = delete;
inline __isl_keep isl_set *get() const;
inline __isl_give isl_set *release();
inline bool is_null() const;
}

The interface and behavior of the new value pointer style classes is inspired
by http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3339.pdf, which
proposes a std::value_ptr, a smart pointer that applies value semantics to its
pointee.

We currently only provide a limited set of public constructors and instead
require provide a global overloaded type constructor method "isl::obj
isl::manage(isl_obj *)", which allows to convert an isl_set* to an isl::set by
calling 'S = isl::manage(s)'. This pattern models the make_unique() constructor
for unique pointers.

The next two functions isl::obj::get() and isl::obj::release() are taken
directly from the std::value_ptr proposal:

S.get() extracts the raw pointer of the object managed by S.
S.release() extracts the raw pointer of the object managed by S and sets the
object in S to null.

We additionally add std::obj::copy(). S.copy() returns a raw pointer refering
to a copy of S, which is a shortcut for "isl::obj(oldobj).release()", a
functionality commonly needed when interacting directly with the isl C
interface where all methods marked with __isl_take require consumable raw
pointers.

S.is_null() checks if S manages a pointer or if the managed object is currently
null. We add this function to provide a more explicit way to check if the
pointer is empty compared to a direct conversion to bool.

This commit also introduces a couple of polly-specific extensions that cover
features currently not handled by the official isl C++ bindings draft, but
which have been provided by IslPtr<T> and are consequently added to avoid code
churn. These extensions include:

- operator bool() : Conversion from objects to bool
- construction from nullptr_t
- get_ctx() method
- take/keep/give methods, which match the currently used naming
convention of IslPtr<T> in Polly. They just forward to
(release/get/manage).
- raw_ostream printers

We expect that these extensions are over time either removed or upstreamed to
the official isl bindings.

We also export a couple of classes that have not yet been exported in isl (e.g.,
isl::space)

As part of the code review, the following two questions were asked:

- Why do we not use a standard smart pointer?

std::value_ptr was a proposal that has not been accepted. It is consequently
not available in the standard library. Even if it would be available, we want
to expand this interface with a complete method interface that is conveniently
available from each managed pointer. The most direct way to achieve this is to
generate a specialiced value style pointer class for each isl object type and
add any additional methods to this class. The relevant changes follow in
subsequent commits.

- Why do we not use templates or macros to avoid code duplication?

It is certainly possible to use templates or macros, but as this code is
auto-generated there is no need to make writing this code more efficient. Also,
most of these classes will be specialized with individual member functions in
subsequent commits, such that there will be little code reuse to exploit. Hence,
we decided to do so at the moment.

These bindings are not yet officially part of isl, but the draft is already very
stable. The smart pointer interface itself did not change since serveral months.
Adding this code to Polly is against our normal policy of only importing
official isl code. In this case however, we make an exception to showcase a
non-trivial use case of these bindings which should increase confidence in these
bindings and will help upstreaming them to isl.

Tags: #polly

Reviewed By: Meinersbur

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

llvm-svn: 297452

show more ...

Fix namespaces after clang-format update

llvm-svn: 296635

[Support] Remove NonowningIslPtr. NFC.

NonowningIslPtr<isl_X> was used as types of function parameters when the
function does not consume the isl object, i.e. an __isl_keep parameter.

The alternati

[Support] Remove NonowningIslPtr. NFC.

NonowningIslPtr<isl_X> was used as types of function parameters when the
function does not consume the isl object, i.e. an __isl_keep parameter.

The alternatives are:

1. IslPtr<isl_X>
This has additional calls to isl_X_copy and isl_X_free to
increase/decrease the reference counter even though not needed. The
caller already owns a reference to the isl object.

2. const IslPtr<isl_X>&
This does not change the reference counter, but requires an
additional load to get the pointer to the isl object (instead of just
passing the pointer itself).
Moreover, the compiler cannot rely on the constness of the pointer
and has to reload the pointer every time it writes to memory (unless
alias analysis such as TBAA says it is not possible).

The isl C++ bindings currently in development do not have an equivalent
to NonowningIslPtr and adding one would make the binding more
complicated and its advantage in performance is small. In order to
simplify the transition to these C++ bindings, remove NonowningIslPtr.
Change every former use of it to alternative 2 mentioned aboce
(const IslPtr<isl_X>&).

llvm-svn: 295998

show more ...

Add isl_multi_pw_aff to GICHelper

Add isl_multi_pw_aff* to GICHelper and add some missing isl_pw_multi_aff* handlers.

llvm-svn: 290007

Add more ISL foreachElt functions. NFC.

Add and implement foreachElt for isl_map, isl_set and isl_union_set. These are
used by an out-of-tree patch which is in process of being upstreamed.

llvm-svn

Add more ISL foreachElt functions. NFC.

Add and implement foreachElt for isl_map, isl_set and isl_union_set. These are
used by an out-of-tree patch which is in process of being upstreamed.

llvm-svn: 288924

show more ...

Add IslPtr type traits. NFC.

Add traits for isl_id and isl_multi_aff, required by out-of-tree patches
currently in progress of upstreaming.

isl_union_pw_aff_dump has been added to ISL during one of

Add IslPtr type traits. NFC.

Add traits for isl_id and isl_multi_aff, required by out-of-tree patches
currently in progress of upstreaming.

isl_union_pw_aff_dump has been added to ISL during one of the last ISL
updates, such that we can also enable its dump() trait.

llvm-svn: 288915

show more ...

[Support] Compile fix for gcc. NFC.

gcc 5.4 insists on template specialization to be in a namespace polly { ... }
block, instead of being prefixed with 'polly::'. Error message:

root/src/llvm/tools

[Support] Compile fix for gcc. NFC.

gcc 5.4 insists on template specialization to be in a namespace polly { ... }
block, instead of being prefixed with 'polly::'. Error message:

root/src/llvm/tools/polly/lib/Support/GICHelper.cpp:203:54: error: specialization of ‘template<class T> void polly::IslPtr<T>::dump() const’ in different namespace [-fpermissive]
template <> void polly::IslPtr<isl_##TYPE>::dump() const { \
^
msvc14 and clang 3.8 did not complain.

llvm-svn: 282874

show more ...

[Support] Add (Nonowning-)IslPtr::dump(). NFC.

The dump() methods can be called from a debugger instead of e.g.

isl_*_dump(Var.Obj)

where Var is a variable of type IslPtr/NonowningIslPtr. To e

[Support] Add (Nonowning-)IslPtr::dump(). NFC.

The dump() methods can be called from a debugger instead of e.g.

isl_*_dump(Var.Obj)

where Var is a variable of type IslPtr/NonowningIslPtr. To ensure that the
existence of the function pointers do not depdend on whether the methods are
used somwhere, they are declared with external linkage.

llvm-svn: 282870

show more ...

Add -polly-flatten-schedule pass.

The -polly-flatten-schedule pass reduces the number of scattering
dimensions in its isl_union_map form to make them easier to understand.
It is not meant to be used

Add -polly-flatten-schedule pass.

The -polly-flatten-schedule pass reduces the number of scattering
dimensions in its isl_union_map form to make them easier to understand.
It is not meant to be used in production, only for debugging and
regression tests.

To illustrate, how it can make sets simpler, here is a lifetime set
used computed by the porposed DeLICM pass without flattening:

{ Stmt_reduction_for[0, 4] -> [0, 2, o2, o3] : o2 < 0;
Stmt_reduction_for[0, 4] -> [0, 1, o2, o3] : o2 >= 5;
Stmt_reduction_for[0, 4] -> [0, 1, 4, o3] : o3 > 0;
Stmt_reduction_for[0, i1] -> [0, 1, i1, 1] : 0 <= i1 <= 3;
Stmt_reduction_for[0, 4] -> [0, 2, 0, o3] : o3 <= 0 }

And here the same lifetime for a semantically identical one-dimensional
schedule:

{ Stmt_reduction_for[0, i1] -> [2 + 3i1] : 0 <= i1 <= 4 }

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

llvm-svn: 280948

show more ...

GICHelper: Correctly assign return value

... to preserve reference counting logic.

In practice the missing assignment would not have caused any issues. We still
fix it as the code is wrong and it a

GICHelper: Correctly assign return value

... to preserve reference counting logic.

In practice the missing assignment would not have caused any issues. We still
fix it as the code is wrong and it also causes noise in the clang static
analysis runs.

llvm-svn: 280946

show more ...

Improve documentation and testing for isl_valFromAPInt

The recent unit tests we gained made clear that the semantics of
isl_valFromAPInt are not clear, due to missing documentation. In this change w

Improve documentation and testing for isl_valFromAPInt

The recent unit tests we gained made clear that the semantics of
isl_valFromAPInt are not clear, due to missing documentation. In this change we
document both the calling interface as well as the implementation of
isl_valFromAPInt.

We also make the implementation easier to read by removing integer wrappig in
abs() when passing in the minimal integer value for a given bitwidth. Even
though wrapping and subsequently interpreting the result as unsigned value gives
the correct result, this is far from obvious. Instead, we explicitly add one
more bit to the input type to ensure that abs will never wrap. This change did
not uncover a bug in the old implementation, but was introduced to increase
readability.

We update the tests to add a test case for this special case and use this
opportunity to also test a number larger than 64 bit. Finally, we order the
arguments of the test cases to make sure the expected output is first. This
helps readability in case of failing test cases as gtest assumes the first value
to be the exected value.

Reviewed-by: Michael Kruse <[email protected]>
Differential Revision: https://reviews.llvm.org/D23917

llvm-svn: 279815

show more ...

Improve documentation and testing of APIntFromVal

The recent unit tests we gained made clear that the semantics of APIntFromVal
are not clear, due to missing documentation. In this change we documen

Improve documentation and testing of APIntFromVal

The recent unit tests we gained made clear that the semantics of APIntFromVal
are not clear, due to missing documentation. In this change we document both
the calling interface as well as the implementation of APIntFromVal. We also
make the implementation easier to read by removing the use of magic numbers.
Finally, we add tests to check the bitwidth of the created values as well as
the correct modeling of very large numbers.

Reviewed-by: Michael Kruse <[email protected]>
Differential Revision: https://reviews.llvm.org/D23910

llvm-svn: 279813

show more ...

Add more isl object printing functions

llvm-svn: 261402