isl_test_cpp17-generic.cc: work around std::optional::value issue in older macOS

In versions of macOS prior to 10.14, std::optional::value
is not available, while the compiler may still be detected
as supporting C++17.
While it would be possible to extend the detection
to include a check for std::optional::value, it is easy
enough to work around the absence of std::optional::value
by simply calling operator* on the std::optional.

Reported-by: Liviu Ionescu <ilg@livius.net>
Tested-by: Liviu Ionescu <ilg@livius.net>
Signed-off-by: Sven Verdoolaege <sven.verdoolaege@gmail.com>

isl_tab_basic_map_partial_lexopt: copy integer divisions to context

For the updated test case, one of the constraints expressing
the integer division floor((a)/6) would appear to have an indeterminate sign
in the context, triggering a split of the context and therefore
also a split of the solution.
There is no need to split the context on such a constraint,
especially since the integer division only involves variables
that also appear in the context.

Copy such integer divisions to the context, including
their defining constraints.
This ensures that no split will be performed based on these constraints
since they will be known to be non-negative in the context.

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

isl_tab_pip.c: find_context_div: extract out find_div_involving_only

This will be reused in the next commit.

Reviewed-by: Tianjiao Sun <tianjiao.sun@cerebras.net>
Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

add isl_basic_set_add_div_constraints

This will be used in an upcoming commit.

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

add isl_basic_set_insert_div

This will be used in an upcoming commit.

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

add check for isl_map_lexmin_pw_multi_aff returning single cell expression

This will illustrate the effect of an upcoming commit.
In particular, the test currently checks for the opposite
of the desired result.

It would be nicer if the actual result of isl_map_lexmin_pw_multi_aff
could be compared, but this is complicated by the fact that parsing
may change the representation of an isl_pw_multi_aff so that
it is no longer obviously equal to the input.
In particular, the result of isl_map_lexmin_pw_multi_aff is
{ [a] -> [(2a - 2*floor((5 + 5a)/6))] : 0 <= a <= 11 },
but it gets parsed as
{ [a] -> [(-2 - 2*floor((-1 - a)/6))] : 0 <= a <= 11 }.
Comparing the piecewise expressions using
isl_pw_multi_aff_is_equal instead of isl_pw_multi_aff_plain_is_equal
would not help since then it wouldn't be possible to make a distinction
based on the number of cells in the expression.

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

isl_test2.cc: has_single_cell_pma: extract out has_single_cell

This will be reused in the next commit.

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

isl_tab_pip.c: find_context_div: reuse is_known_div_not_involving

This reduces the dependence on the internal representation.

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

isl_tab_pip.c: find_context_div: extract out is_known_div_not_involving

This will be reused in the next commit.

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

isl_tab_pip.c: find_context_div: use isl_basic_map_div_expr_involves_vars

This reduces the dependence on the internal representation.

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

isl_tab_pip.c: find_context_div: use isl_basic_map_div_is_marked_unknown

This reduces the dependence on the internal representation.

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

isl_tab_pip.c: find_context_div: use isl_basic_set_dim

This reduces the dependence on the internal representation.

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

isl_tab_pip.c: basic_map_partial_lexopt_base_sol: remove micro-optimization

Both isl_basic_set_sort_divs and align_context_divs
should return fairly quickly when there are no local variables.
Removing the explicit check simplifies the code.

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

isl_tab_pip.c: align_context_divs: use isl_basic_set_dim

This reduces the dependence on the internal representation.

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

isl_tab_pip.c: align_context_divs: improve error handling

This was missing from isl-0.20-621-ge7f5c82acd (isl_*_dim:
return isl_size, Tue Aug 7 12:09:42 2018 +0200).

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

isl_tab_pip.c: find_context_div: return isl_size

This clarifies what the possible return values are.

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

detect some modulo expressions when extracting a function

In the worst case, isl_pw_multi_aff_from_map resorts
to parametric integer programming to find a function representation
of a single valued binary relation, but it detects
some special cases first by examining the constraints.
This prevents a subdivision of the domain that may result
from parametric integer programming.
In particular, it already checks for specific cases
of integer divisions.
Extend this to also check for some forms of modulo expressions.
This ensures that the new test cases can be represented
by functions defined over a single cell.

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

isl_aff.c: pw_multi_aff_from_map_check_div: move div detection down

In particular, move the detection of a pair of constraints
that define an integer division into isl_basic_map_extract_output_div,
renaming it to isl_basic_map_try_find_output_div and letting it
return an optional isl_aff.
The resulting isl_basic_map_try_find_output_div behaves similarly
to the isl_basic_map_try_find_output_mod that will be introduced
in the next commit, making it easier to call them in succession.

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

isl_aff.c: pw_multi_aff_from_map_div: return integer division expression

That is, instead of plugging in this expression in the input map and
continuing with the construction of an isl_pw_multi_aff representation,
let the caller handle this.
This prepares for handling modulo expressions in the same way.
The function is renamed accordingly.

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

isl_aff.c: extract out pw_multi_aff_from_map_plug_in

This will make it easier to lift this part out of pw_multi_aff_from_map_div
in the next commit.

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

isl_aff.c: pw_multi_aff_from_map_div: only get space when needed

This prepares for the next commit.

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

privately expose isl_basic_map_is_set

This function will be reused in an upcoming commit.

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

detect specific instance of modulos in constraints

During AST generation, when considering a given schedule dimension,
any integer divisions that may depend on this dimension
are removed to be able to extract usable lower and upper bounds.
If the schedule dimension happens to be equal to a modulo
of a floor or modulo expression, then the constraints
for encoding this relationship will involve an integer division
that is defined in terms of the schedule dimension.
Removing this integer division results in an approximation
where the schedule dimension may no longer have a fixed value.
This means that a loop gets generated with a (complicated) condition
in the body that picks out a single iteration of the loop.

Detect a specific instance of this kind of nested modulo expression and
make it explicit in the constraints such that the integer division
no longer depends on the schedule dimension and therefore
does not need to be removed, allowing the AST generator
to detect that the schedule dimension has a fixed value
in terms of the parameters and outer schedule dimensions.

Reviewed-by: Tianjiao Sun <tianjiao.sun@cerebras.net>
Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

sort constraints while looking for pair of opposite constraints

When the constraints are sorted, the opposite constraint, if any,
can be found more closely to the given constraint.

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

isl_map.c: find_later_constraint_in_pair: stop search after near hit

If an opposite constraint is found that does not satisfy the bound,
then no opposite constraint satisfying the bound will be found
as otherwise the constraint found first would have been removed already.

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

isl_basic_map_find_output_upper_div_constraint: extract find_later_constraint_...

This will make it easier to slightly improve the search
in the next two commits.

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

isl_basic_map_find_output_upper_div_constraint: extract constraint_pair_has_bound

This makes it easier to extract out a further
find_later_constraint_in_pair in the next commit.

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

isl_basic_map_find_output_upper_div_constraint: extract out is_constraint_pair

This makes it easier to extract out a further
find_later_constraint_in_pair in an upcoming commit.

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

extract out shared isl_basic_map_any_div_involves_vars

This reduces the dependence on the internal representation.

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

isl_map.c: basic_map_dim_is_bounded: use isl_basic_map_var_offset

This prepares for the next commit.

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

basic_map_dim_is_bounded: use isl_basic_map_dim

This reduces the dependence on the internal representation.

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

isl_map_simplify.c: div_find_coalesce: return isl_size

This clarifies what the possible return values are.

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

isl_map_simplify.c: div_find_coalesce: use isl_size for local variable

This was missing from isl-0.20-621-ge7f5c82acd (isl_*_dim:
return isl_size, Tue Aug 7 12:09:42 2018 +0200).

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

extract out shared isl_basic_map_div_expr_involves_vars

This removes some code duplication.

Note that the same pattern also occurs in other places,
but they will be covered by an isl_basic_map_any_div_involves_vars
that will be extracted in an upcoming commit and
that will also call isl_basic_map_div_expr_involves_vars.

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

isl_map.c: div_involves_vars: use isl_basic_map_var_offset

This prepares for the next commit.

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

isl_map.c: div_involves_vars:: use isl_basic_map_dim

This reduces the dependence on the internal representation.

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

isl_map.c: div_involves_vars: use isl_basic_map_div_is_marked_unknown

This reduces the dependence on the internal representation.

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

isl_basic_map_remove_divs_involving_dims: extract out remove_divs_involving_vars

This will be reused in an upcoming commit.

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

isl_map.c: extract out generic extract_bound_from_constraint

In particular, extract out a generic version of part
of isl_basic_map_inequality_extract_output_upper_bound
that works for both lower and upper bounds and also
equality constraints and that allows for the selection
of an initial subset of the variables.

This generic version will be reused in an upcoming commit.

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

isl_basic_map_simplify: eliminate integral integer divisions

That is, replace integer divisions with denominator 1
by their argument expressions.
Such integer divisions are usually eliminated already
because the pair of constraints that define such an integer division
form an equality constraint that is used for the elimination.
However, one or both of these constraints may have been eliminated
themselves for being redundant with respect to some other constraints or
the integer division may have undergone simplifications
that may not be directly reflected in those constraints.
It is therefore possible for such integer divisions to remain
after simplification.  This is confusing to the user and
also fairly inefficient.  Remove them.

The integral integer divisions are eliminated from first to last
because earlier integer divisions may appear in later ones and
eliminating an earlier one could therefore cause some later one
to become integral.

It is difficult to add a test to check that such integer divisions
are indeed eliminated because they occur only rarely and
because testing for a specific representation of a set
risks becoming invalid through other changes to that representation.

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

isl_map_simplify.c: extract out shared mark_progress

This removes some very minor code duplication.
Also use the extracted function in places where there is currently
no check for a NULL pointer.  Even though eliminate_divs_eq and
eliminate_divs_ineq are currently always called with a non-NULL pointer,
there is no need to make this assumption.

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

isl_basic_map_remove_duplicate_constraints: do not mark progress on removal

The function isl_basic_map_simplify keeps track of any progress being made
inside any of the simplifications it performs in order to rerun them
since some simplifications may trigger further simplifications
of a type that have already been considered.
However, the mere act of removing a duplicate constraint
cannot trigger any further simplifications.

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

isl_map_simplify.c: eliminate_selected_unit_divs: extract *_div_is_integral

This reduces the dependence on the internal representation.

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

isl_map_simplify.c: eliminate_selected_unit_divs: use *_is_marked_unknown

This reduces the dependence on the internal representation.

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

isl_map_simplify.c: eliminate_selected_unit_divs: use isl_basic_map_dim

This reduces the dependence on the internal representation.

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

elimination using equality constraint does not introduce redundant constraints

In particular, if a variable is eliminated using an equality constraint
of the basic map itself, then this should not make
any inequality constraints redundant or
turn them into implicit equality constraints.
Note that if the elimination results in additional scaling down
of the constraint, then this scaling down will still be considered
as potentially introducing redundant constraints.

This should not have any user visible effect
since it will at most avoid some redundant computations.

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

isl_basic_map_normalize_constraints: take into account effect on constraints

In particular, if the constraints were sorted before
then they may no longer be sorted after normalizing some of them.
The removal of the corresponding flags is put inside scale_down_inequality.
The other caller of scale_down_inequality (eliminate_var_using_equality)
already modifies the same flags and continues to do so after this commit
to take into account the effect of the actual elimination.
This is needed in those cases where no scaling is being performed.

This is unlikely to have an effect in practice.
The normalization usually happens when the set is first created
(before the constraints are sorted) or after a call to Gaussian
elimination, which already results in the removal of the flags.

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

extract out isl_basic_map_modify_inequality

This will be reused in the next commit.

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

isl_map_simplify.c: eliminate_var_using_equality: reuse scale_down_inequality

This prepares for an upcoming commit where scale_down_inequality
will take into account the effect of the scaling on the constraints.

Note that unlike the call from isl_basic_map_normalize_constraints,
the call from eliminate_var_using_equality always passes
in the gcd of the entire constraint, including the constant term.
This means that the scaling will never tighten the constraint.

It would be possible to let both callers only pass in
the gcd of the variable coefficients and to let scale_down_inequality
include the constant term in case of a rational input.
However, this would be a change with respect to the current behavior and
should therefore be considered separately.
In fact, this has an effect on some of the AST generation outputs and
it is not immediately obvious if those changes are desirable.

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

isl_basic_map_normalize_constraints: extract out scale_down_inequality

This will be reused in the next commit.

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

keep track of effect of variable elimination on implicit equality constraints

Any manipulation that may make a constraint redundant
may also turn it into an implicit equality.
In particular, when a constraint gets scaled down
a sample value in the tableau that could originally
reach the next integer value could potentially no longer
reach this next integer value after the scaling.

The chances of this having any user visible effect are very small.
When the ISL_BASIC_MAP_NO_REDUNDANT flag is cleared, any later
call to isl_basic_map_remove_redundancies will already
look for implicit equality constraints as well,
independently of the ISL_BASIC_MAP_NO_IMPLICIT flag.

There are a couple of places that explicitly check
the ISL_BASIC_MAP_NO_IMPLICIT flag, but this is either only an optimization
or only in effect on rational sets.

Note that there are some situations where
the elimination is known not to have an effect
on redundant constraints or implicit equality constraints.
These will be considered in an upcoming commit.

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

isl_map_simplify.c: eliminate_var_using_equality: use isl_basic_map_get_ctx

This reduces the dependence on the internal representation.

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

isl_map_coalesce: reduce coefficients of fused intermediate results

Any coefficient reduction performed by the top-level isl_map_coalesce
is likely to be undone by the call to isl_basic_map_gauss
on the fused intermediate results.
Apply coefficient reduction again on the result to improve
the chance that the fused intermediate results can be coalesced
with other basic maps, as in the newly added test case.

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

isl_basic_map_reduce_coefficients: reduce again after gauss

Much of the effect of the reduction may be undone by a call to
isl_basic_map_gauss.  Even though the call to isl_basic_map_gauss
itself may be useful to exploit any newly discovered equality
constraint, the coefficients should be reduced again
to ensure the function does what it is meant to do.

In particular, this allows the first of the newly added test cases
to be coalesced.  The second test case checks that
the second reduction is not done after the removal
of any local variables.

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

isl_basic_map_reduce_coefficients: move dropping variables last

The next commit will introduce a second reduction using data derived
from the original input.  This no longer applies if any local
variables have been dropped in between, which can happen
in the call to eliminate_divs_eq.
Move the call to eliminate_divs_eq down such that the second
reduction can be inserted between the call to isl_basic_map_gauss and
the call to eliminate_divs_eq.

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

isl_basic_map_reduce_coefficients: perform sanity check on reduction data

In particular, check that the total dimensionality of the basic map
has not changed since the data was derived.
This helps to prevent inappropriate reuse of reduce_coefficients.

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

isl_basic_map_reduce_coefficients: extract out reduce_coefficients

This will allow this part of isl_basic_map_reduce_coefficients
to be reused in an upcoming commit.

The extracted function is responsible for marking the basic map
as having had its coefficients reduced to ensure that it doesn't
get marked after some possible further constraint manipulations
after the call to reduce_coefficients.

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

isl_basic_map_reduce_coefficients: introduce isl_reduce_coefficients_data

By moving out the initialization and clearing, this reduces
the size of isl_basic_map_reduce_coefficients.
It will also make it easier to reuse the core reduction
in an upcoming commit.

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

clear ISL_BASIC_MAP_REDUCED_COEFFICIENTS when needed

That is, clear the flag when the coefficients (other than
the constant term) of an inequality constraint may get modified or
when a new inequality constraint is added.
Do so instead of clearing the flag every time the basic map
is changed in any way or when some progress is made during simplification.

This should more accurately reflect when the coefficients
may no longer be reduced and is more in line with how
the other flags are handled.

One case that was missed before in particular was the call
to isl_basic_map_gauss from within isl_basic_map_reduce_coefficients
itself.  It this call takes place, then the coefficients
may very well no longer be reduced, as evidenced by an upcoming commit.

Note that accurately keeping track of this flag is not all that important.
Since isl_basic_map_reduce_coefficients may leave the output
in an inconsistent state, it always needs to be followed
by a call to isl_basic_map_gauss, which would typically remove the flag.
The chance that the flag is still set on the next call
to isl_basic_map_reduce_coefficients is therefore very small.

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

isl_aff_remove_unused_divs: remove all unused local variables

Non-final unused local variables can be just as confusing
as final unused local variables.  In particular, they do not
get printed and therefore seemingly identical affine expressions
may still not be detected as being obviously equal.
The non-final ones are perhaps less common and are also
slightly more difficult to handle.  Handle them anyway.

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

isl_aff_remove_unused_divs: reuse isl_aff_drop_dims

This removes some code duplication and prepares for the next commit.

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

isl_aff_remove_unused_divs: use isl_aff_domain_var_offset

An upcoming commit will need to index into an array of active variables and
then it is more useful to have the offset of the local variables
within the variables rather than the offset among the coefficients.

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

isl_aff_domain_offset: extract out isl_aff_domain_var_offset

isl_aff_domain_offset returns the position of the coefficients
of a given type in the domain, while in some cases it is more convenient
to think in terms of the position among the variables of the domain.
isl_aff_domain_var_offset returns this position.

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

isl_aff_domain_offset: use isl_local_space_var_offset

This allows isl_aff_domain_offset to detect run-time errors,
which is not possible when calling isl_local_space_offset
since that function return 0 in case of errors.

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

properly document isl_local_space_get_active

This was missing from isl-0.07-145-gba33571fef (isl_aff.c: extract
isl_local_space_get_active, Mon Aug 29 15:00:33 2011 +0200).

Reported-by: Tianjiao Sun <tianjiao.sun@cerebras.net>
Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

isl_ast_codegen.c: add_domain: only take single copy of inverse schedule

When this function was introduced in isl-0.15-236-g0ab343912b
(isl_ast_codegen.c: generate_domain: extract out add_domain,
Sun Aug 2 12:25:48 2015 +0200), the caller was performing
a gist on the inverse schedule and passed down both the original version and
the gisted version.
In an earlier commit, the gisting was removed, so these two versions
of the inverse schedule are always the same.
Only pass it in once.

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

isl_ast_codegen.c: add_domain: fix typo in comment

Reported-by: Tianjiao Sun <tianjiao.sun@cerebras.net>
Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

isl_ast_build: stop keeping track of single-valuedness

This mechanism was introduced in isl-0.11.1-7-g076a978c43
(isl_ast_codegen.c: generate_domain: avoid infinite recursion,
Tue Feb 19 16:46:33 2013 +0100) to keep track of the fact
that the ungisted inverse schedule is necessarily single-valued.
Since the gisting of the inverse schedule was removed
in the previous commit, this property was no longer inspected and
so it can be removed completely.

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

isl_ast_codegen.c: generate_domain: construct call from non-gisted map

Using a gisted map removes information that could be used
to simplify expressions.
This is especially useful for the codegen/separate2.c test case
that is currently only able to obtain a relatively simple expression
because some unused integer division is still available,
but this will be removed in an upcoming commit.

Back in isl-0.11.1-7-g076a978c43 (isl_ast_codegen.c: generate_domain:
avoid infinite recursion, Tue Feb 19 16:46:33 2013 +0100),
the additional information had the opposite effect,
where using the non-gisted map would result in some test cases
being changed to include some expressions that are more complicated.
At this stage, the fall-out is minimal.

Note that the call to isl_map_coalesce is kept
to avoid splitting up the domain on some inputs, notably expansion.st.

Also note that this commit removes the only use of the single_valued
property in isl_ast_build.  The attribute itself will be removed
in the next commit.

Furthermore, all calls to add_domain now pass two copies
of the original inverse schedule.  One of the copies will be removed
in an upcoming commit.

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

add AST generation test case involving expansion node

This will illustrate the need to preserve a call to isl_map_coalesce
in the next commit.

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

isl_ast_build_expr.c: extract_modulo: consider simple sums of constraints

Modulo expressions are detected by looking at expressions
of the form

f * m * floor(a / m)

and checking that some variation of a is non-negative.
In particular, a and -a + m - 1 are tested for being non-negative,
but first the constraints are scanned for constraints that are
equal or opposite to a mod m up to a constant.

Also check if a happens to be equal (up to a constant)
to a positively weighted sum of constraints with disjoint sets of variables.
Since each constraint in non-negative, a positive combination
is non-negative as well.
Note that sum is required to be equal to a itself and not just a mod m
to make it easier to find the coefficients with which each constraint
should be multiplied.

The extra check allows for some extra cases to be discovered
on some inputs because the basic check only checks whether a itself
is non-negative, while the sum of constraints may have a different
constant term.
On other inputs, the extra check simply results in a different
modulo expression being detected.

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

isl_ast_build_expr.c: mod_constraint_is_simpler: extract out is_simpler

The extracted function will be reused in the next commit.
The callback function takes both an isl_extract_mod_data and
a user pointer because the next commit will use
the isl_extract_mod_data.

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

isl_ast_build_expr.c: replace_if_simpler: extract out replace_nonneg

The extracted function will be reused in an upcoming commit.

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

isl_ast_build_expr.c: is_parallel_or_opposite: add minor optimization

If the coefficient to be checked is zero, then no further checks
are needed.

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

isl_ast_build_expr.c: decompose check_parallel_or_opposite

This improves the readability of check_parallel_or_opposite and
prepares for further extensions in an upcoming commit.

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

isl_ast_build_expr.c: mod_constraint_is_simpler: return isl_bool

This clarifies what the possible return values are.

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

isl_ast_build_expr.c: check_parallel_or_opposite: extract replace_if_simpler

This reduces the size of check_parallel_or_opposite and
makes it easier to perform error handling on the result
of the mod_constraint_is_simpler call in the next commit.

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

isl_ast_build_expr.c: check_parallel_or_opposite: extract out wrapper

In particular, extract out the call to isl_constraint_free,
making it easier to return early from the core function.

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

isl_ast_build_expr.c: check_parallel_or_opposite: extract out helper function

This will simplify the next commit.

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

introduce isl_stat_non_error_bool

There are quite a few places where a temporary isl_bool result
needs to be converted to an isl_stat.  Provide a designated function
for this conversion to save space and to clarify the intent
of these code fragments, similarly to isl_stat_non_null.
This commit only introduces the function.  Calls will be added later.

Even though this function is mainly meant to be used internally,
it is exposed to the user since isl_stat_non_null is exposed as well.

Signed-off-by: Sven Verdoolaege <sven.verdoolaege@gmail.com>
Reviewed-by: Tianjiao Sun <tianjiao.sun@cerebras.net>
Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

isl_coalesce.c: set_from_updated_bmap: take single parameter

Ever since isl-0.14-122-g7147af3b4f (isl_map_coalesce: keep track of
information on basic maps in separate struct,
Sat Oct 11 16:44:21 2014 +0200), the two arguments passed
to this function always come from a given isl_coalesce_info,
so it is better to pass that in directly.

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

isl_coalesce.c: add_wrap: return isl_bool

This clarifies what the possible return values are.

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

isl_sample.c: tab_shift_cone: fix typo in comment

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

test_inputs/codegen/separate2.in: fix typo in comment

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

isl_basic_set_intersect_params: extract out isl_basic_map_intersect_params

The extracted function complements the already exported
isl_basic_set_intersect_params and isl_basic_map_intersect_*.

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

cpp/cpp.h.top: mark exception::what override

This clarifies that this method overrides the method of std::exception.

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

extract-interface: link in libclangSupport when available

Since LLVM commit llvmorg-15-init-17695-g7a5cb15ea6fa ([RISCV] Lazily add
RVV C intrinsics., Wed Jul 13 15:52:17 2022 +0800),
libclangSema depends on libclangSupport, so link that in as well.

Reported-by: Tianjiao Sun <tianjiao.sun@cerebras.net>
Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

extract-interface: link in clangDriver before clangBasic

It seems that clangBasic has always been a dependency of clangDriver,
but since LLVM commit llvmorg-15-init-16356-g3ce78cbd2392
([clang][deps] Fix handling of -MT in module command-line,
Tue Jul 12 16:55:11 2022 -0700), clangDriver started depending
on the quoteMakeTarget symbol in clangBasic, requiring clangDriver
to be linked in before clangBasic.

Reported-by: Tianjiao Sun <tianjiao.sun@cerebras.net>
Signed-off-by: Sven Verdoolaege <sven@cerebras.net>

isl_pw_qpolynomial_bound: special case affine polynomials

If one or more of the quasi-polynomials is actually a quasi-affine
expression, then the bound on the corresponding domain
can always be computed exactly.
Do this instead of using the generic bound computation.

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

isl_bound.c: unwrap: rename "poly" parameter to "qp"

The next commit calls this function on a quasi-polynomial
that may not be a polynomial.  The function itself does not depend
on the argument being a polynomial.  It is only the callback
that may require a polynomial, as is the case for
unwrapped_guarded_poly_bound.

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

isl_bound.c: guarded_poly_bound: extract out unwrap

The extracted function will be reused in an upcoming commit.

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

isl_bound.c: unwrapped_guarded_poly_bound: take struct isl_bound

Similarly to the previous commit, the caller has already performed
the cast to struct isl_bound, so there is no need to do it again.

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

isl_bound.c: compressed_guarded_poly_bound: take struct isl_bound

The caller has already performed the cast to struct isl_bound,
so there is no need to do it again.

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

extract out shared isl_qpolynomial_isa_aff

This removes some minor code duplication and matches
the isl_qpolynomial_as_aff extracted in the previous commit.

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

isl_basic_map_from_qpolynomial: extract out isl_qpolynomial_as_aff

This will be reused in an upcoming commit.

Since the extracted function may also be more generally useful,
expose it to the user as well.

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

extract out shared isl_qpolynomial_peek_poly

This reduces the dependence on the internal representation.

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

perform checked C++ bindings tests as soon as C++11 compiler is available

These bindings are now always available, even if they cannot
be regenerated.

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

remove check for presence of cpp.h

This header is now always available.

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

always run Python tests if Python is available

Now that the Python interface can always be built,
the Python tests can be run as soon as Python is available.

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

always build Python interface

Now that the machine independent part of the Python interface
is always available, the full interface can always be built.

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