Signed-off-by: Sven Verdoolaege <sven.verdoolaege@gmail.com>

Signed-off-by: Sven Verdoolaege <sven.verdoolaege@gmail.com>

The computation in compute_chambers assumes that the projection
of the entire parametric polytope onto the parameter space
is full-dimensional.  isl_basic_set_compute_vertices already handles
equality constraints that are explicitly available, but it failed
to handle implicit equality constraints.
Handle those as well.

Signed-off-by: Sven Verdoolaege <sven.verdoolaege@gmail.com>

This will be used in the next commit in case
any implicit equality constraints are detected.
In particular, if the original input is not marked rational,
then the unmarked original will be needed in the next commit
after the local copy has been marked rational.

Signed-off-by: Sven Verdoolaege <sven.verdoolaege@gmail.com>

This makes it easier to reuse this function in an upcoming commit.

Signed-off-by: Sven Verdoolaege <sven.verdoolaege@gmail.com>

The computation in compute_chambers assumes that the projection
of the entire parametric polytope onto the parameter space
is full-dimensional.  The function can_intersect already checks
that the activity domains of the vertices are full-dimensional,
but if the entire projection is not full-dimensional, then no vertices
get added in the first place because their activity domains
are not full-dimensional.
Note that even though isl_basic_set_compute_vertices already handles
equality constraints that are explicitly available, it fails
to handle implicit equality constraints.
This means that the sanity check may fail in some cases,
but this is already an improvement over running into an infinite loop.
The failure itself will be handled in upcoming commits.

Signed-off-by: Sven Verdoolaege <sven.verdoolaege@gmail.com>

Detecting redundant constraints and/or equality constraints
can be relatively expensive, but this may result
in lower-dimensional factors and breaking down a set
into lower-dimensional factors is the whole point of
isl_basic_set_multiplicative_call.
Still, postpone the detection until the factors
of the factorization that can be read off without the explicit detection
since these may already be of lower dimension than the input set.

Signed-off-by: Sven Verdoolaege <sven.verdoolaege@gmail.com>

The original (plain) C++ interface has a fixed C++ type for each
(exported) C type.
In the templated C++ interface, each plain C++ type
is mapped to a template type that can be parametrized
with zero, one or two tuple kinds, where the number
of tuple kinds corresponds to the number of tuples
of the elements of the objects and each tuple kind
represents a category of tuples.
This allows for more fine-grained and application-specific types,
allowing the compiler to perform consistency checks
on operations performed on the template type.
Typical tuple kinds are statement instances and array elements,
allowing for the definition of a specific type
for access relations, mapping statement instances to array elements.
The templated isl interface only contains the template types.
It is up to the application to define instantiations of those types.

In order to be able to gradually introduce template types
in an application, the plain types and the template types
need to coexist.  In order to ease the transition,
the template types are given the same name,
but that means they need to live in a different namespace.
In particular, the "isl::typed" namespace is used.

Since some of the C++ types can involve different numbers of tuples,
the templated types are defined with a variable number
of template parameters and (partial) specializations are provided
for each possible number of tuples.
In fact, for ease of implementation, all templated types are
defined with a variable number of template parameters, even
if only one specific number of tuples is allowed.

A special Anonymous tuple kind is introduced to represent
the one-dimensional unnamed tuples and
all specializations of isl::typed::aff,
as well as the single specialization of both isl::typed::val
and isl::typed::id have this tuple kind
as the final (or only) template argument.
For types such as isl::typed::aff that can also have a domain tuple,
an additional isl::typed::aff_on is defined that
adds the fixed Anonymous tuple kind to the specified domain tuple kind.

A static list is maintained of the number of tuples
some basic types can have.
Other types that are derived from those basic types
using type constructors have the same number of tuples.
The only modification is that the multi type constructor
changes the Anonymous tuple to a generic tuple.

Each of the template type specializations has a constructor
that takes an object of the corresponding plain C++ type.
This constructor is marked private and a static
method called "from" is provided for calling
the constructor indirectly.  This ensures
that the template arguments always need to be specified explicitly
when constructing a templated object from a plain object.
Otherwise, an object of a plain type could be passed
to a function expecting a templated type and
template type deduction would conjure up the right template arguments,
bypassing the consistency checks.
The constructor is also hidden from other specializations.
In particular it is made to only apply to the plain C++ type itself.
Otherwise, any inappropriate use of a specialization simply
points to the private constructor, which is not very informative
since it does not give any hint about the actual (incorrect)
specialization.

In any template specialization with a single Anonymous tuple kind,
the constructor is not marked private
to allow an automatic construction from the corresponding plain type.
In these cases, the tuple kind is required to be Anonymous anyway and
there is no point in requiring users to spell this out.

While, in general, a plain type object should not get converted
automatically to an object of a template type,
it should be possible to use an object of a template type
where one of a plain type is expected.
The specializations are therefore made to be subclasses
of the corresponding plain types.
An alternative would be to provide an implicit conversion operator,
but this does not have quite the same effect, especially
for functions already relying on implicit conversion operators
in the plain interface.  Deriving from the plain types
also allows some methods that do not need any further modifications
to be reused directly.

Since each template type specialization derives from
the corresponding plain type, all methods are inherited
from the plain type.
These do not offer any consistency checks, but for some methods,
in particular those derived from unary property functions
in the C interface, resulting in methods with no arguments,
this is sufficient.
For other methods, specialization specific versions are added
that enforce relationships between the argument types and the return type,
if any.

The methods are generated based on a table describing the behavior
of each method in terms of its effect on the tuples.
The behavior of methods with the same name is usually
the same and therefore only needs to be specified once.
Methods that have the result type in their names
also have this part removed when looking up their behavior.
Each behavior is described as a sequence of signatures,
where a signature consists of several sequences of 0, 1 or 2
abstract tuple kinds,
one such sequence for the return type and one for each argument.
The abstract tuple kinds are described by placeholders, each of which will
have a corresponding template parameter in the generated bindings.
That is, if the same placeholder appears multiple times, then
the corresponding (concrete) tuple kinds will be required to be the same.
When generating a method for a particular specialization
of a template type, the matching signature in the behavior will be used.
For a regular (non-static) method, a signature matches
if the abstract tuple kind sequence for the first argument matches that
of the specialization, i.e., if the lengths are the same and
if the placeholders in the first argument can be mapped to (consistent)
parts in the type specialization.
Different placeholders are mapped independently and they can map
to the same part.

Methods that take a callback have the result and argument kinds
of the callback spliced in at the position of the callback.
It is assumed that the callback is the final argument of the method
(apart from the user pointer that follows the callback argument
in the C interface).

Leaf is a special placeholder that can only
be matched with a template parameter.  In particular, no method
will be generated in any further specializations
where the range has a nested pair of tuples.
This special placeholder is used for set_*_tuple methods.
This means that tuples containing nested tuples can currently
not be assigned any name.  This may be relaxed in the future,
but for now this should not be a major restriction since
the nested leaf tuples can still have names.

In some rare cases, the behavior of a method depends on the type
on which it is invoked.  For example, on a set or binary relation,
gist takes two arguments with the same tuple kind(s),,
but on any type derived from aff, the second argument
refers to the domain of the function.
A separate table keeps track of such special cases,
which override the default.

If some behavior is described for a method, but
no matching signature can be found,
then the method is explicitly delete'd from the templated type
to hide the method inherited from the corresponding plain type.
This can happen in particular for methods involving nested tuples
because the template parameter does not
provide access to any nested tuples.
However, it should still be possible to call such methods and
therefore the partial specialization is further specialized
to provide a matching for the nested tuples.
While generating such a specialization,
the need for a further specialization may become apparent
for methods applied to objects with other nested tuples.
Since there are currently no functions in isl
that specifically operate on objects with doubly nested tuples,
no further specializations of this sort will be required.

Any "get_" method is also explicitly delete'd from the templated type.
As explained in isl-0.20-803-g53ec4e237d (bindings: drop "get_" prefix
of methods that start this way, Wed Nov 21 10:14:05 2018 +0100),
they are only in the plain interface for backward compatibility and
there is not such backward compatibility to be considered
for the templated interface.

In a user application, it can sometimes be useful to consider
some tuple kind to be a special case of some other kind.
For example, a scalar could be considered to be a special kind
of an array so that a function accepting an access to an array
can also accept an access to a scalar, but not the other way around.
In order to lift the subclass relationship to the level
of the templated isl types (at least to some extent),
an additional constructor is added to each specialization
that accepts more specific specializations as input.
In particular, for each template parameter of the type specialization
a corresponding template parameter for this new constructor is introduced.
The new parameter is then required to be a subclass of the original
type template parameter.

Note that the consistency checks offered by the templated interface
only apply to tuple kinds and not to specific tuples,
since those are usually only defined at run time.
This means that some run-time restrictions cannot be expressed
at compile time.

The compile-time checks can be circumvented by taking a pointer
to an object and modifying the plain type part.
This could happen accidentally in functions taking a pointer
to a plain isl object, but it is fairly rare for isl objects
to be passed by pointer.

The idea for a templated interface was partly inspired
by an unpublished C++ library developed by Armin Groesslinger
that provides operations for sets defined by formulas over polynomials and
that allows for the specification of nested spaces using templates.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

This helper function will be reused by the templated C++ interface
generator, so make it available as a (static) generator method.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

For the plain C++ interface, the argument position is irrelevant,
but for the templated C++ interface, it is important
to know the argument position in order to be able
to print the corresponding template arguments.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

The templated C++ isl interface generator will want
to print these descendent overloads whenever possible.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

This will be reused by the templated C++ interface generator
since the templated methods call the original plain methods
instead of the C functions and therefore do not need an extra copy.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

This will allow the templated C++ interface generator
to add template arguments.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

This will allow the templated C++ interface generator
to add template arguments.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

This separates the generic parts of the C++ generator.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

This method will be moved to interface/cpp.cc.
In order not to have to copy/share osprintf to/with interface/cpp.cc
simply use the output stream operator, which actually
results in simpler code.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

This method will be moved to interface/cpp.cc.
In order not to have to copy/share osprintf to/with interface/cpp.cc
simply use the output stream operator, which actually
results in simpler code.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

This method will be moved to interface/cpp.cc.
In order not to have to copy/share osprintf to/with interface/cpp.cc
simply use the output stream operator, which actually
results in simpler code.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

This generic part will be reused to print a templated C++ interface.
It will be moved to interface/cpp.* in an upcoming commit.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

The next commit will extract a generic cpp_generator
from plain_cpp_generator.  The copy_super_methods
will be moved to the generic cpp_generator because
it will also be useful for the templated C++ interface
that will be introduced later.
The call to copy_super_methods is first moved
to the (now) plain_cpp_generator constructor,
so that it can be moved to the cpp_generator constructor
along with the moved of the copy_super_methods itself.
This means it will get called automatically
for the templated C++ interface when it gets introduced.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

The print_method_header method implicitly depends on the "checked"
field of the plain_cpp_generator.
This field will not be moved to cpp_generator when
it gets extracted out from plain_cpp_generator,
while the entire class_printer will get moved to cpp_generator.
The dependence on "checked" therefore needs to be made
explicit through an extra type printer argument.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

Some methods in class_printer depend on the "checked" field
(possibly indirectly through the type printer).
This field will not be moved to cpp_generator when
it gets extracted out from plain_cpp_generator,
while class_printer will get moved to cpp_generator.
These methods therefore first need to be put
in an intermediate plain_printer.
The plain_printer keeps track of its own reference
to the generator because the one in class_printer
will become a reference to a generic cpp_generator.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

An upcoming commit will add support for generating a templated
C++ interface.  This will reuse the generic part
of the current (plain) C++ interface generator.
The entire generator is first renamed to plain_cpp_generator and
the generic pieces will be moved back to cpp_generator
in a later commit.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

An upcoming commit will add support for generating a templated
C++ interface.  This will reuse the generic part
of the current (plain) C++ interface generator.
The entire generator is first moved to plain_cpp.* and
the generic pieces will be moved back to cpp.*
in a later commit.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

When support for generating a templated C++ interface gets added,
it will be useful to be able to print extra elements
before the terminating semicolon of the method declaration.
Extract out a print_full_method_header that also prints
the semicolon and that will end up in the plain_cpp_generator,
while class_printer::print_method_header will remain
in the (then) generic cpp_generator.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

This separates out the difference in type printing for
the regular and the checked C++ interface.
The cpp_type_printer will also be reused
for specializing the printing of types
for the templated C++ interface.

The cpp_type_printer::isl_type method is extracted out
at the same time to make the implementation of
cpp_type_printer::param more consistent over all
different types.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

Since llvmorg-12-init-16745-gc495dfe0268b ([clang][cli] NFC: Decrease
the scope of ParseLangArgs parameters, Thu Jan 14 08:26:12 2021 +0100),
the fourth argument of CompilerInvocation::setLangDefaults is
a std::vector<std::string> rather than a clang::PreprocessorOptions.
Introduce a setLangDefaultsArg4 to pass in the right argument
depending on what is expected by the specific version of clang.

Signed-off-by: Sven Verdoolaege <sven.verdoolaege@gmail.com>

Commit isl-0.22.1-2-g36a719fd8f (isl_basic_map_set_to_empty: do not
modify input if already marked empty, Mon Mar 16 22:33:00 2020 +0100)
changed isl_basic_map_set_to_empty to not change
the internal representation if the input basic map is already
marked empty to avoid a case where the basic map was marked empty and
subsequently had all its constraints removed from resulting
in an error.
However, other parts of the code depend on the canonical representation
of an empty basic map, or at least that the internal representation
does not look like it needs further processing.
In particular, if there are any non-trivial equality constraints
involving local variables then isl_basic_map_drop_redundant_divs
will try to exploit those equality constraints to derive
an explicit representation for a local variable.
However, it only prepares the input for isl_basic_map_simplify,
while isl_basic_map_simplify skips all processing
on an input that is marked empty.
This results in an infinite recursion on isl_basic_map_drop_redundant_divs.
Adjust isl_basic_map_set_to_empty to only skip the modification
if the input is both marked empty and has no constraints.

Signed-off-by: Sven Verdoolaege <sven.verdoolaege@gmail.com>

Since isl-0.22.1-359-g8b9f94f262 (build extract_interface
using build compiler, Thu May 21 14:55:46 2020 +0200),
it is possible to specify a build compiler for building
extract_interface.
However, unlike the C++ compiler used to compile the test cases,
the build compiler did not get checked for any required flags
for supporting C++11.  Add such a check.

Note that building extract_interface in the first place
still depends on the host compiler supporting C++11,
meaning that the build will fail if the host compiler supports C++11,
but the build compiler does not.  However, this should be fairly rare.

Signed-off-by: Sven Verdoolaege <sven.verdoolaege@gmail.com>

Some isl types are annotated as being a subclass of other types.
In the Python bindings, the corresponding Python classes
are indeed subclasses of the corresponding other classes,
meaning, in particular, that a method available in a superclass
is also available in a subclass (if not overridden).
For example, calling intersect on a set with a union_set argument
will call the intersect method of the union_set superclass.
This is achieved by calling a superclass method
if the arguments are not of the expected type and
by converting self from a subclass type to the superclass type.

In the C++ bindings a choice was made in isl-0.18-598-g81c38ef4ce
(cpp: generate C++ wrapper classes, Sat Apr 8 05:12:50 2017 +0200)
not to reflect these subclass relationships in the C++ class hierarchy,
but to offer conversion through implicit constructors in
isl-0.18-599-g7d3c260fb5 (cpp: support methods and constructors,
Thu Apr 13 21:42:03 2017 +0200) instead.
However, this does not allow a superclass method to be called
on an object from a subclass.

It would be possible to also introduce a class hierarchy
in the C++ bindings and to use typeid to perform a similar
conversion of self (this), but it may be too disruptive
to make such a change at this point.
Furthermore, a method in a subclass hides all methods
with the same name in superclasses and therefore
explicit copies of those methods with all supported
combinations of arguments would have to be copied
to the subclass anyway and then the conversion of "this"
can be performed directly in the copied method, which
is what this commit does.

In particular, any method of a superclass is copied (recursively)
to all subclasses unless the subclass already has a method
with the same name and the same arguments.
If a method with a given signature appears in multiple superclasses
then the method from the closest ancestor is selected,
where an ancestor is closer if the distance in the class hierarchy
is smaller or the distance is the same and the ancestor appears
closer in the declaration of the type.
For example, in the isl::aff class, the add_constant method
with an isl::multi_val argument is not copied from isl::pw_aff
(where it is in turn copied from isl::pw_multi_aff), but instead
from isl::multi_aff because the class hierarchy distance is smaller
(one instead of two).  This means the isl:aff method will
return an isl::multi_aff instead of an isl::pw_multi_aff.
This selection mechanism may not always result in the same variant
of the method getting called as in the Python bindings, but it is
a reasonable choice and it would be difficult to mimic
Python exactly here.

The extra methods can cause ambiguities if a method is called
with an object in a subclass of the argument type
of the original method.
Without the extra methods, the object would automatically be
converted to the argument type.
This commit therefore additionally adds extra methods
for all subclass types that can be implicitly converted
to the original argument type.
This cannot easily be done in a separate commit since
it needs to be known whether any inherited methods got copied
before these extra conversion methods get added.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

The constructor will be extended in the next commit.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

None of the methods with automatic conversion take any isl type arguments.
However, when ConversionMethod gets reused to convert
the "this" argument in an upcoming commit, most
of the other arguments will be of isl type and
their conversion does not require an isl_ctx argument.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

This makes it easier to support conversion from isl types
in the next commit.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

That is, keep track of the type to which "this" should be converted and
perform the conversion (if needed) in the call to the original
method from the conversion method.
This type is currently always the type of the class, indicating
that "this" should not be converted, but this commit prepares
for conversion methods that do convert "this".

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

This allows the printing to be specialized in case "this"
needs to be converted in the next commit.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

Unlike methods that call an isl C function,
a conversion method never calls release() on an isl type argument,
so they can all be passed as const references.

This does not have any effect on any of the currently exported functions
because the methods with automatic conversion do not take
any isl type arguments.
However, when ConversionMethod gets reused to convert
the "this" argument in an upcoming commit, most
of the other arguments will be of isl type and
these should be passed as const references.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

This allows the behavior to be overridden by ConversionMethod
in the next commit.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

That is, instead of passing along an extra "convert" argument,
store the required information in a subclass of Method.
Printing out the implementation is already handled by two separate methods.
Before, the extra argument was used to pick the right method.
Now, the type of method (ConversionMethod or just Method) determines
which printing method gets called.
Printing out the header is done by a single method.
This used to call cpp_generator::class_printer::get_param with
the "convert" argument and now calls a get_param method of Method
that is overridden by ConversionMethod.
The latter then ends up calling cpp_generator::class_printer::get_param,
but this method is no longer called for a non-conversion method,
so it no longer needs to handle an empty "convert".

Note that the virtual print_method method is called
from a generic cpp_generator::class_printer::print_method_variants.
Only the cpp_generator::impl_printer versions have a different behavior
depending on whether a Method or a ConversionMethod gets printed.
The cpp_generator::decl_printer versions are now identical.

Also note that ConversionMethod::get_param does not call
cpp_generator::class_printer::get_param directly, but instead calls
a lambda passed in during construction.
This means ConversionMethod itself does not need to be aware
of how the argument conversion is performed and does not
store "convert" directly.
This will be useful when ConversionMethod is reused to convert
the "this" argument and not any of the other arguments.
This future reuse of ConversionMethod is also the main motivation
for introducing the ConversionMethod class.

Since ConversionMethod does not store "convert" directly,
the printing of the implementations uses an indirect way
of figuring out whether an argument is converted.
In particular, it checks if the method argument is different
from the C function argument.

Signed-off-by: Sven Verdoolaege <sven@cerebras.net>