isl_map_coalesce: allow general coalescing with expanded divs
commita130b583583fd057b686c2010653c7cc3e1be327
authorSven Verdoolaege <skimo@kotnet.org>
Fri, 27 May 2016 11:12:48 +0000 (27 13:12 +0200)
committerSven Verdoolaege <skimo@kotnet.org>
Fri, 10 Jun 2016 16:15:14 +0000 (10 18:15 +0200)
tree77918359b36663f0a33ceadd240fccea0fbc23f1
parent4d728c02a903182e2312bf111aede6f512aebba2
isl_map_coalesce: allow general coalescing with expanded divs

If one basic map has extra integer divisions compared to another
basic map, then isl_map_coalesce would already check if the first
is a subset of the second.  This check can be performed by
only expanding the second basic map.
Perform more general coalescing by also expanding the corresponding
tableau.  This helps in particular in cases where one basic map
has a cut constraint with respect to the other that involves an
integer division, while the corresponding facet lies entirely
inside that other basic map.

For example, for the following test case reported by
Tobias Grosser,

{ [i0, i1] : 0 <= i0 <= 1 and i1 >= 0 and ((0 < i1 <= 13)
or (2*floor((i0 + i1)/2) >= -5 + i0 + 2i1)) }

the constraint 2*floor((i0 + i1)/2) >= -5 + i0 + 2i1 of one disjunct
cuts the other disjunct, but the corresponding facet lies entirely
in the other disjunct.  The same holds for the cut constraints
"0 < i1" of the other disjunct.  The two disjuncts can therefore
be replaced by their mutually valid constraints.

The test case added by this commit is an extended case, with
the upper bound 1 on i0 replaced by 2.  The reason is that,
in principle, the disjunct

{ [i0, i1] : 0 <= i0 <= 1 and i1 >= 0 and
2*floor((i0 + i1)/2) >= -5 + i0 + 2i1 }

can be simplified to

{[i0,i1]: 0, i1-4 <= i0 <= 1 && 0 <= i1}

In fact, this is what Omega does by looking at sums of constraints.
After this simplification, coalescing the two disjuncts does not
require the changes in this commit.
With the extended upper bound, the simplification is no longer possible
and the changes in this commit are required to coalesce the two disjuncts.

Requested-by: Tobias Grosser <tobias@grosser.es>
Tested-by: Tobias Grosser <tobias@grosser.es>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
isl_coalesce.c
isl_test.c