| blob | af10145ad2d0a3867cc13f7a2e0c19396bd15356 |
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2014 INRIA Rocquencourt
4 *
5 * Use of this software is governed by the MIT license
6 *
7 * Written by Sven Verdoolaege, K.U.Leuven, Departement
8 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
9 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
10 * B.P. 105 - 78153 Le Chesnay, France
11 */
13 #include <isl_ctx_private.h>
14 #include <isl_map_private.h>
15 #include <isl_lp_private.h>
16 #include <isl/map.h>
17 #include <isl_mat_private.h>
18 #include <isl_vec_private.h>
19 #include <isl/set.h>
20 #include <isl_seq.h>
21 #include <isl_options_private.h>
24 #include <isl_sort.h>
26 #include <bset_to_bmap.c>
27 #include <bset_from_bmap.c>
28 #include <set_to_map.c>
33 /* Remove redundant
34 * constraints. If the minimal value along the normal of a constraint
35 * is the same if the constraint is removed, then the constraint is redundant.
36 *
37 * Since some constraints may be mutually redundant, sort the constraints
38 * first such that constraints that involve existentially quantified
39 * variables are considered for removal before those that do not.
40 * The sorting is also needed for the use in map_simple_hull.
41 *
42 * Note that isl_tab_detect_implicit_equalities may also end up
43 * marking some constraints as redundant. Make sure the constraints
44 * are preserved and undo those marking such that isl_tab_detect_redundant
45 * can consider the constraints in the sorted order.
46 *
47 * Alternatively, we could have intersected the basic map with the
48 * corresponding equality and then checked if the dimension was that
49 * of a facet.
50 */
53 {
86 error:
90 }
94 {
97 }
99 /* Remove redundant constraints in each of the basic maps.
100 */
102 {
105 }
108 {
110 }
112 /* Check if the set set is bound in the direction of the affine
113 * constraint c and if so, set the constant term such that the
114 * resulting constraint is a bounding constraint for the set.
115 */
117 {
120 isl_int opt;
121 isl_int opt_denom;
143 }
148 }
150 }
154 error:
158 }
162 {
172 }
174 error:
177 }
179 /* Given a union of basic sets, construct the constraints for wrapping
180 * a facet around one of its ridges.
181 * In particular, if each of n the d-dimensional basic sets i in "set"
182 * contains the origin, satisfies the constraints x_1 >= 0 and x_2 >= 0
183 * and is defined by the constraints
184 * [ 1 ]
185 * A_i [ x ] >= 0
186 *
187 * then the resulting set is of dimension n*(1+d) and has as constraints
188 *
189 * [ a_i ]
190 * A_i [ x_i ] >= 0
191 *
192 * a_i >= 0
193 *
194 * \sum_i x_{i,1} = 1
195 */
197 {
213 }
225 }
236 }
243 }
244 }
246 }
248 /* Given a facet "facet" of the convex hull of "set" and a facet "ridge"
249 * of that facet, compute the other facet of the convex hull that contains
250 * the ridge.
251 *
252 * We first transform the set such that the facet constraint becomes
253 *
254 * x_1 >= 0
255 *
256 * I.e., the facet lies in
257 *
258 * x_1 = 0
259 *
260 * and on that facet, the constraint that defines the ridge is
261 *
262 * x_2 >= 0
263 *
264 * (This transformation is not strictly needed, all that is needed is
265 * that the ridge contains the origin.)
266 *
267 * Since the ridge contains the origin, the cone of the convex hull
268 * will be of the form
269 *
270 * x_1 >= 0
271 * x_2 >= a x_1
272 *
273 * with this second constraint defining the new facet.
274 * The constant a is obtained by settting x_1 in the cone of the
275 * convex hull to 1 and minimizing x_2.
276 * Now, each element in the cone of the convex hull is the sum
277 * of elements in the cones of the basic sets.
278 * If a_i is the dilation factor of basic set i, then the problem
279 * we need to solve is
280 *
281 * min \sum_i x_{i,2}
282 * st
283 * \sum_i x_{i,1} = 1
284 * a_i >= 0
285 * [ a_i ]
286 * A [ x_i ] >= 0
287 *
288 * with
289 * [ 1 ]
290 * A_i [ x_i ] >= 0
291 *
292 * the constraints of each (transformed) basic set.
293 * If a = n/d, then the constraint defining the new facet (in the transformed
294 * space) is
295 *
296 * -n x_1 + d x_2 >= 0
297 *
298 * In the original space, we need to take the same combination of the
299 * corresponding constraints "facet" and "ridge".
300 *
301 * If a = -infty = "-1/0", then we just return the original facet constraint.
302 * This means that the facet is unbounded, but has a bounded intersection
303 * with the union of sets.
304 */
307 {
345 }
354 }
365 error:
370 }
372 /* Compute the constraint of a facet of "set".
373 *
374 * We first compute the intersection with a bounding constraint
375 * that is orthogonal to one of the coordinate axes.
376 * If the affine hull of this intersection has only one equality,
377 * we have found a facet.
378 * Otherwise, we wrap the current bounding constraint around
379 * one of the equalities of the face (one that is not equal to
380 * the current bounding constraint).
381 * This process continues until we have found a facet.
382 * The dimension of the intersection increases by at least
383 * one on each iteration, so termination is guaranteed.
384 */
386 {
417 }
428 }
431 error:
435 }
437 /* Given the bounding constraint "c" of a facet of the convex hull of "set",
438 * compute a hyperplane description of the facet, i.e., compute the facets
439 * of the facet.
440 *
441 * We compute an affine transformation that transforms the constraint
442 *
443 * [ 1 ]
444 * c [ x ] = 0
445 *
446 * to the constraint
447 *
448 * z_1 = 0
449 *
450 * by computing the right inverse U of a matrix that starts with the rows
451 *
452 * [ 1 0 ]
453 * [ c ]
454 *
455 * Then
456 * [ 1 ] [ 1 ]
457 * [ x ] = U [ z ]
458 * and
459 * [ 1 ] [ 1 ]
460 * [ z ] = Q [ x ]
461 *
462 * with Q = U^{-1}
463 * Since z_1 is zero, we can drop this variable as well as the corresponding
464 * column of U to obtain
465 *
466 * [ 1 ] [ 1 ]
467 * [ x ] = U' [ z' ]
468 * and
469 * [ 1 ] [ 1 ]
470 * [ z' ] = Q' [ x ]
471 *
472 * with Q' equal to Q, but without the corresponding row.
473 * After computing the facets of the facet in the z' space,
474 * we convert them back to the x space through Q.
475 */
478 {
504 error:
508 }
510 /* Given an initial facet constraint, compute the remaining facets.
511 * We do this by running through all facets found so far and computing
512 * the adjacent facets through wrapping, adding those facets that we
513 * hadn't already found before.
514 *
515 * For each facet we have found so far, we first compute its facets
516 * in the resulting convex hull. That is, we compute the ridges
517 * of the resulting convex hull contained in the facet.
518 * We also compute the corresponding facet in the current approximation
519 * of the convex hull. There is no need to wrap around the ridges
520 * in this facet since that would result in a facet that is already
521 * present in the current approximation.
522 *
523 * This function can still be significantly optimized by checking which of
524 * the facets of the basic sets are also facets of the convex hull and
525 * using all the facets so far to help in constructing the facets of the
526 * facets
527 * and/or
528 * using the technique in section "3.1 Ridge Generation" of
529 * "Extended Convex Hull" by Fukuda et al.
530 */
533 {
576 }
579 }
583 error:
588 }
590 /* Special case for computing the convex hull of a one dimensional set.
591 * We simply collect the lower and upper bounds of each basic set
592 * and the biggest of those.
593 */
595 {
607 }
626 }
635 }
636 }
637 }
656 }
664 }
665 }
676 }
682 }
683 }
688 }
699 }
703 }
708 error:
712 }
715 {
723 else
727 }
729 /* Compute the convex hull of a pair of basic sets without any parameters or
730 * integer divisions using Fourier-Motzkin elimination.
731 * The convex hull is the set of all points that can be written as
732 * the sum of points from both basic sets (in homogeneous coordinates).
733 * We set up the constraints in a space with dimensions for each of
734 * the three sets and then project out the dimensions corresponding
735 * to the two original basic sets, retaining only those corresponding
736 * to the convex hull.
737 */
740 {
764 }
773 }
779 }
788 }
795 error:
800 }
802 /* Is the set bounded for each value of the parameters?
803 */
805 {
807 isl_bool bounded;
818 }
820 /* Is the image bounded for each value of the parameters and
821 * the domain variables?
822 */
824 {
827 isl_bool bounded;
837 }
839 /* Is the set bounded for each value of the parameters?
840 */
842 {
852 }
854 }
856 /* Compute the lineality space of the convex hull of bset1 and bset2.
857 *
858 * We first compute the intersection of the recession cone of bset1
859 * with the negative of the recession cone of bset2 and then compute
860 * the linear hull of the resulting cone.
861 */
864 {
885 }
892 }
899 }
906 }
911 error:
916 }
920 /* Given a set and a linear space "lin" of dimension n > 0,
921 * project the linear space from the set, compute the convex hull
922 * and then map the set back to the original space.
923 *
924 * Let
925 *
926 * M x = 0
927 *
928 * describe the linear space. We first compute the Hermite normal
929 * form H = M U of M = H Q, to obtain
930 *
931 * H Q x = 0
932 *
933 * The last n rows of H will be zero, so the last n variables of x' = Q x
934 * are the one we want to project out. We do this by transforming each
935 * basic set A x >= b to A U x' >= b and then removing the last n dimensions.
936 * After computing the convex hull in x'_1, i.e., A' x'_1 >= b',
937 * we transform the hull back to the original space as A' Q_1 x >= b',
938 * with Q_1 all but the last n rows of Q.
939 */
942 {
969 error:
973 }
975 /* Given two polyhedra with as constraints h_{ij} x >= 0 in homegeneous space,
976 * set up an LP for solving
977 *
978 * \sum_j \alpha_{1j} h_{1j} = \sum_j \alpha_{2j} h_{2j}
979 *
980 * \alpha{i0} corresponds to the (implicit) positivity constraint 1 >= 0
981 * The next \alpha{ij} correspond to the equalities and come in pairs.
982 * The final \alpha{ij} correspond to the inequalities.
983 */
986 {
1009 }
1016 /* positivity constraint 1 >= 0 */
1021 }
1024 }
1025 /* positivity constraint 1 >= 0 */
1030 }
1033 }
1034 }
1039 error:
1043 }
1045 /* Compute a vector s in the homogeneous space such that <s, r> > 0
1046 * for all rays in the homogeneous space of the two cones that correspond
1047 * to the input polyhedra bset1 and bset2.
1048 *
1049 * We compute s as a vector that satisfies
1050 *
1051 * s = \sum_j \alpha_{ij} h_{ij} for i = 1,2 (*)
1052 *
1053 * with h_{ij} the normals of the facets of polyhedron i
1054 * (including the "positivity constraint" 1 >= 0) and \alpha_{ij}
1055 * strictly positive numbers. For simplicity we impose \alpha_{ij} >= 1.
1056 * We first set up an LP with as variables the \alpha{ij}.
1057 * In this formulation, for each polyhedron i,
1058 * the first constraint is the positivity constraint, followed by pairs
1059 * of variables for the equalities, followed by variables for the inequalities.
1060 * We then simply pick a feasible solution and compute s using (*).
1061 *
1062 * Note that we simply pick any valid direction and make no attempt
1063 * to pick a "good" or even the "best" valid direction.
1064 */
1067 {
1092 /* positivity constraint 1 >= 0 */
1102 }
1112 error:
1117 }
1119 /* Given a polyhedron b_i + A_i x >= 0 and a map T = S^{-1},
1120 * compute b_i' + A_i' x' >= 0, with
1121 *
1122 * [ b_i A_i ] [ y' ] [ y' ]
1123 * [ 1 0 ] S^{-1} [ x' ] >= 0 or [ b_i' A_i' ] [ x' ] >= 0
1124 *
1125 * In particular, add the "positivity constraint" and then perform
1126 * the mapping.
1127 */
1130 {
1143 error:
1147 }
1149 /* Compute the convex hull of a pair of basic sets without any parameters or
1150 * integer divisions, where the convex hull is known to be pointed,
1151 * but the basic sets may be unbounded.
1152 *
1153 * We turn this problem into the computation of a convex hull of a pair
1154 * _bounded_ polyhedra by "changing the direction of the homogeneous
1155 * dimension". This idea is due to Matthias Koeppe.
1156 *
1157 * Consider the cones in homogeneous space that correspond to the
1158 * input polyhedra. The rays of these cones are also rays of the
1159 * polyhedra if the coordinate that corresponds to the homogeneous
1160 * dimension is zero. That is, if the inner product of the rays
1161 * with the homogeneous direction is zero.
1162 * The cones in the homogeneous space can also be considered to
1163 * correspond to other pairs of polyhedra by chosing a different
1164 * homogeneous direction. To ensure that both of these polyhedra
1165 * are bounded, we need to make sure that all rays of the cones
1166 * correspond to vertices and not to rays.
1167 * Let s be a direction such that <s, r> > 0 for all rays r of both cones.
1168 * Then using s as a homogeneous direction, we obtain a pair of polytopes.
1169 * The vector s is computed in valid_direction.
1170 *
1171 * Note that we need to consider _all_ rays of the cones and not just
1172 * the rays that correspond to rays in the polyhedra. If we were to
1173 * only consider those rays and turn them into vertices, then we
1174 * may inadvertently turn some vertices into rays.
1175 *
1176 * The standard homogeneous direction is the unit vector in the 0th coordinate.
1177 * We therefore transform the two polyhedra such that the selected
1178 * direction is mapped onto this standard direction and then proceed
1179 * with the normal computation.
1180 * Let S be a non-singular square matrix with s as its first row,
1181 * then we want to map the polyhedra to the space
1182 *
1183 * [ y' ] [ y ] [ y ] [ y' ]
1184 * [ x' ] = S [ x ] i.e., [ x ] = S^{-1} [ x' ]
1185 *
1186 * We take S to be the unimodular completion of s to limit the growth
1187 * of the coefficients in the following computations.
1188 *
1189 * Let b_i + A_i x >= 0 be the constraints of polyhedron i.
1190 * We first move to the homogeneous dimension
1191 *
1192 * b_i y + A_i x >= 0 [ b_i A_i ] [ y ] [ 0 ]
1193 * y >= 0 or [ 1 0 ] [ x ] >= [ 0 ]
1194 *
1195 * Then we change directoin
1196 *
1197 * [ b_i A_i ] [ y' ] [ y' ]
1198 * [ 1 0 ] S^{-1} [ x' ] >= 0 or [ b_i' A_i' ] [ x' ] >= 0
1199 *
1200 * Then we compute the convex hull of the polytopes b_i' + A_i' x' >= 0
1201 * resulting in b' + A' x' >= 0, which we then convert back
1202 *
1203 * [ y ] [ y ]
1204 * [ b' A' ] S [ x ] >= 0 or [ b A ] [ x ] >= 0
1205 *
1206 * The polyhedron b + A x >= 0 is then the convex hull of the input polyhedra.
1207 */
1210 {
1243 error:
1248 }
1254 /* Compute the convex hull of a pair of basic sets without any parameters or
1255 * integer divisions.
1256 *
1257 * This function is called from uset_convex_hull_unbounded, which
1258 * means that the complete convex hull is unbounded. Some pairs
1259 * of basic sets may still be bounded, though.
1260 * They may even lie inside a lower dimensional space, in which
1261 * case they need to be handled inside their affine hull since
1262 * the main algorithm assumes that the result is full-dimensional.
1263 *
1264 * If the convex hull of the two basic sets would have a non-trivial
1265 * lineality space, we first project out this lineality space.
1266 */
1269 {
1304 }
1311 }
1315 error:
1319 }
1321 /* Compute the lineality space of a basic set.
1322 * We basically just drop the constants and turn every inequality
1323 * into an equality.
1324 * Any explicit representations of local variables are removed
1325 * because they may no longer be valid representations
1326 * in the lineality space.
1327 */
1330 {
1353 }
1366 }
1369 error:
1373 }
1375 /* Compute the (linear) hull of the lineality spaces of the basic sets in the
1376 * set "set".
1377 */
1380 {
1390 }
1398 }
1400 /* Compute the convex hull of a set without any parameters or
1401 * integer divisions.
1402 * In each step, we combined two basic sets until only one
1403 * basic set is left.
1404 * The input basic sets are assumed not to have a non-trivial
1405 * lineality space. If any of the intermediate results has
1406 * a non-trivial lineality space, it is projected out.
1407 */
1410 {
1424 isl_error_internal,
1432 }
1444 }
1448 }
1450 }
1453 error:
1456 }
1458 /* Compute an initial hull for wrapping containing a single initial
1459 * facet.
1460 * This function assumes that the given set is bounded.
1461 */
1464 {
1483 error:
1487 }
1493 };
1496 {
1501 }
1505 {
1519 }
1527 }
1531 }
1533 /* Check whether the constraint hash table "table" contains the constraint
1534 * "con".
1535 */
1538 {
1552 }
1554 /* Check for inequality constraints of a basic set without equalities
1555 * such that the same or more stringent copies of the constraint appear
1556 * in all of the basic sets. Such constraints are necessarily facet
1557 * constraints of the convex hull.
1558 *
1559 * If the resulting basic set is by chance identical to one of
1560 * the basic sets in "set", then we know that this basic set contains
1561 * all other basic sets and is therefore the convex hull of set.
1562 * In this case we set *is_hull to 1.
1563 */
1566 {
1590 }
1592 min_constraints);
1606 }
1617 }
1630 }
1631 }
1636 }
1638 }
1649 }
1660 }
1663 }
1671 error:
1679 }
1681 /* Create a template for the convex hull of "set" and fill it up
1682 * obvious facet constraints, if any. If the result happens to
1683 * be the convex hull of "set" then *is_hull is set to 1.
1684 */
1687 {
1696 }
1702 }
1705 {
1714 }
1718 }
1720 /* Compute the convex hull of a set without any parameters or
1721 * integer divisions. Depending on whether the set is bounded,
1722 * we pass control to the wrapping based convex hull or
1723 * the Fourier-Motzkin elimination based convex hull.
1724 * We also handle a few special cases before checking the boundedness.
1725 */
1727 {
1728 isl_bool bounded;
1744 }
1760 }
1766 error:
1770 }
1772 /* This is the core procedure, where "set" is a "pure" set, i.e.,
1773 * without parameters or divs and where the convex hull of set is
1774 * known to be full-dimensional.
1775 */
1778 {
1789 }
1800 }
1805 error:
1808 }
1810 /* Compute the convex hull of set "set" with affine hull "affine_hull",
1811 * We first remove the equalities (transforming the set), compute the
1812 * convex hull of the transformed set and then add the equalities back
1813 * (after performing the inverse transformation.
1814 */
1817 {
1833 error:
1839 }
1841 /* Return an empty basic map living in the same space as "map".
1842 */
1845 {
1851 }
1853 /* Compute the convex hull of a map.
1854 *
1855 * The implementation was inspired by "Extended Convex Hull" by Fukuda et al.,
1856 * specifically, the wrapping of facets to obtain new facets.
1857 */
1859 {
1887 }
1897 error:
1901 }
1904 {
1906 }
1909 {
1914 }
1917 {
1919 }
1924 };
1926 /* Holds the data needed during the simple hull computation.
1927 * In particular,
1928 * n the number of basic sets in the original set
1929 * hull_table a hash table of already computed constraints
1930 * in the simple hull
1931 * p for each basic set,
1932 * table a hash table of the constraints
1933 * tab the tableau corresponding to the basic set
1934 */
1940 };
1943 {
1952 }
1954 }
1959 };
1962 {
1968 }
1972 {
1985 }
1987 /* Fill hash table "table" with the constraints of "bset".
1988 * Equalities are added as two inequalities.
1989 * The value in the hash table is a pointer to the (in)equality of "bset".
1990 */
1993 {
2002 }
2003 }
2007 }
2009 }
2012 {
2033 }
2035 error:
2038 }
2040 /* Check if inequality "ineq" is a bound for basic set "j" or if
2041 * it can be relaxed (by increasing the constant term) to become
2042 * a bound for that basic set. In the latter case, the constant
2043 * term is updated.
2044 * Relaxation of the constant term is only allowed if "shift" is set.
2045 *
2046 * Return 1 if "ineq" is a bound
2047 * 0 if "ineq" may attain arbitrarily small values on basic set "j"
2048 * -1 if some error occurred
2049 */
2052 {
2054 isl_int opt;
2060 }
2069 else
2071 }
2077 }
2079 /* Set the constant term of "ineq" to the maximum of those of the constraints
2080 * in the basic sets of "set" following "i" that are parallel to "ineq".
2081 * That is, if any of the basic sets of "set" following "i" have a more
2082 * relaxed copy of "ineq", then replace "ineq" by the most relaxed copy.
2083 * "c_hash" is the hash value of the linear part of "ineq".
2084 * "v" has been set up for use by has_ineq.
2085 *
2086 * Note that the two inequality constraints corresponding to an equality are
2087 * represented by the same inequality constraint in data->p[j].table
2088 * (but with different hash values). This means the constraint (or at
2089 * least its constant term) may need to be temporarily negated to get
2090 * the actually hashed constraint.
2091 */
2094 {
2117 }
2118 }
2120 /* Check if inequality "ineq" from basic set "i" is or can be relaxed to
2121 * become a bound on the whole set. If so, add the (relaxed) inequality
2122 * to "hull". Relaxation is only allowed if "shift" is set.
2123 *
2124 * We first check if "hull" already contains a translate of the inequality.
2125 * If so, we are done.
2126 * Then, we check if any of the previous basic sets contains a translate
2127 * of the inequality. If so, then we have already considered this
2128 * inequality and we are done.
2129 * Otherwise, for each basic set other than "i", we check if the inequality
2130 * is a bound on the basic set, but first replace the constant term
2131 * by the maximal value of any translate of the inequality in any
2132 * of the following basic sets.
2133 * For previous basic sets, we know that they do not contain a translate
2134 * of the inequality, so we directly call is_bound.
2135 * For following basic sets, we first check if a translate of the
2136 * inequality appears in its description. If so, the constant term
2137 * of the inequality has already been updated with respect to this
2138 * translate and the inequality is therefore known to be a bound
2139 * of this basic set.
2140 */
2144 {
2167 }
2184 }
2188 }
2201 }
2205 }
2214 error:
2217 }
2219 /* Check if any inequality from basic set "i" is or can be relaxed to
2220 * become a bound on the whole set. If so, add the (relaxed) inequality
2221 * to "hull". Relaxation is only allowed if "shift" is set.
2222 */
2225 {
2233 shift);
2234 }
2235 }
2239 }
2241 /* Compute a superset of the convex hull of set that is described
2242 * by only (translates of) the constraints in the constituents of set.
2243 * Translation is only allowed if "shift" is set.
2244 */
2247 {
2261 }
2278 error:
2283 }
2285 /* Compute a superset of the convex hull of map that is described
2286 * by only (translates of) the constraints in the constituents of map.
2287 * Handle trivial cases where map is NULL or contains at most one disjunct.
2288 */
2291 {
2302 }
2304 /* Return a copy of the simple hull cached inside "map".
2305 * "shift" determines whether to return the cached unshifted or shifted
2306 * simple hull.
2307 */
2310 {
2317 }
2319 /* Compute a superset of the convex hull of map that is described
2320 * by only (translates of) the constraints in the constituents of map.
2321 * Translation is only allowed if "shift" is set.
2322 *
2323 * The constraints are sorted while removing redundant constraints
2324 * in order to indicate a preference of which constraints should
2325 * be preserved. In particular, pairs of constraints that are
2326 * sorted together are preferred to either both be preserved
2327 * or both be removed. The sorting is performed inside
2328 * isl_basic_map_remove_redundancies.
2329 *
2330 * The result of the computation is stored in map->cached_simple_hull[shift]
2331 * such that it can be reused in subsequent calls. The cache is cleared
2332 * whenever the map is modified (in isl_map_cow).
2333 * Note that the results need to be stored in the input map for there
2334 * to be any chance that they may get reused. In particular, they
2335 * are stored in a copy of the input map that is saved before
2336 * the integer division alignment.
2337 */
2340 {
2374 }
2382 }
2384 /* Compute a superset of the convex hull of map that is described
2385 * by only translates of the constraints in the constituents of map.
2386 */
2388 {
2390 }
2393 {
2395 }
2397 /* Compute a superset of the convex hull of map that is described
2398 * by only the constraints in the constituents of map.
2399 */
2402 {
2404 }
2408 {
2410 }
2412 /* Drop all inequalities from "bmap1" that do not also appear in "bmap2".
2413 * A constraint that appears with different constant terms
2414 * in "bmap1" and "bmap2" is also kept, with the least restrictive
2415 * (i.e., greatest) constant term.
2416 * "bmap1" and "bmap2" are assumed to have the same (known)
2417 * integer divisions.
2418 * The constraints of both "bmap1" and "bmap2" are assumed
2419 * to have been sorted using isl_basic_map_sort_constraints.
2420 *
2421 * Run through the inequality constraints of "bmap1" and "bmap2"
2422 * in sorted order.
2423 * Each constraint of "bmap1" without a matching constraint in "bmap2"
2424 * is removed.
2425 * If a match is found, the constraint is kept. If needed, the constant
2426 * term of the constraint is adjusted.
2427 */
2430 {
2447 }
2453 }
2458 }
2464 }
2466 /* Drop all equalities from "bmap1" that do not also appear in "bmap2".
2467 * "bmap1" and "bmap2" are assumed to have the same (known)
2468 * integer divisions.
2469 *
2470 * Run through the equality constraints of "bmap1" and "bmap2".
2471 * Each constraint of "bmap1" without a matching constraint in "bmap2"
2472 * is removed.
2473 */
2476 {
2496 }
2502 }
2506 }
2509 }
2515 }
2517 /* Compute a superset of "bmap1" and "bmap2" that is described
2518 * by only the constraints that appear in both "bmap1" and "bmap2".
2519 *
2520 * First drop constraints that involve unknown integer divisions
2521 * since it is not trivial to check whether two such integer divisions
2522 * in different basic maps are the same.
2523 * Then align the remaining (known) divs and sort the constraints.
2524 * Finally drop all inequalities and equalities from "bmap1" that
2525 * do not also appear in "bmap2".
2526 */
2529 {
2545 }
2547 /* Compute a superset of the convex hull of "map" that is described
2548 * by only the constraints in the constituents of "map".
2549 * In particular, the result is composed of constraints that appear
2550 * in each of the basic maps of "map"
2551 *
2552 * Constraints that involve unknown integer divisions are dropped
2553 * since it is not trivial to check whether two such integer divisions
2554 * in different basic maps are the same.
2555 *
2556 * The hull is initialized from the first basic map and then
2557 * updated with respect to the other basic maps in turn.
2558 */
2561 {
2576 }
2580 }
2582 /* Compute a superset of the convex hull of "set" that is described
2583 * by only the constraints in the constituents of "set".
2584 * In particular, the result is composed of constraints that appear
2585 * in each of the basic sets of "set"
2586 */
2589 {
2591 }
2593 /* Check if "ineq" is a bound on "set" and, if so, add it to "hull".
2594 *
2595 * For each basic set in "set", we first check if the basic set
2596 * contains a translate of "ineq". If this translate is more relaxed,
2597 * then we assume that "ineq" is not a bound on this basic set.
2598 * Otherwise, we know that it is a bound.
2599 * If the basic set does not contain a translate of "ineq", then
2600 * we call is_bound to perform the test.
2601 */
2605 {
2637 else
2639 }
2645 }
2655 }
2657 /* Compute a superset of the convex hull of "set" that is described
2658 * by only some of the "n_ineq" constraints in the list "ineq", where "set"
2659 * has no parameters or integer divisions.
2660 *
2661 * The inequalities in "ineq" are assumed to have been sorted such
2662 * that constraints with the same linear part appear together and
2663 * that among constraints with the same linear part, those with
2664 * smaller constant term appear first.
2665 *
2666 * We reuse the same data structure that is used by uset_simple_hull,
2667 * but we do not need the hull table since we will not consider the
2668 * same constraint more than once. We therefore allocate it with zero size.
2669 *
2670 * We run through the constraints and try to add them one by one,
2671 * skipping identical constraints. If we have added a constraint and
2672 * the next constraint is a more relaxed translate, then we skip this
2673 * next constraint as well.
2674 */
2677 {
2698 dim);
2706 }
2711 error:
2716 }
2718 /* Collect pointers to all the inequalities in the elements of "list"
2719 * in "ineq". For equalities, store both a pointer to the equality and
2720 * a pointer to its opposite, which is first copied to "mat".
2721 * "ineq" and "mat" are assumed to have been preallocated to the right size
2722 * (the number of inequalities + 2 times the number of equalites and
2723 * the number of equalities, respectively).
2724 */
2727 {
2745 }
2749 }
2752 }
2754 /* Comparison routine for use as an isl_sort callback.
2755 *
2756 * Constraints with the same linear part are sorted together and
2757 * among constraints with the same linear part, those with smaller
2758 * constant term are sorted first.
2759 */
2761 {
2771 }
2773 /* Compute a superset of the convex hull of "set" that is described
2774 * by only constraints in the elements of "list", where "set" has
2775 * no parameters or integer divisions.
2776 *
2777 * We collect all the constraints in those elements and then
2778 * sort the constraints such that constraints with the same linear part
2779 * are sorted together and that those with smaller constant term are
2780 * sorted first.
2781 */
2784 {
2807 }
2828 error:
2834 }
2836 /* Compute a superset of the convex hull of "map" that is described
2837 * by only constraints in the elements of "list".
2838 *
2839 * If the list is empty, then we can only describe the universe set.
2840 * If the input map is empty, then all constraints are valid, so
2841 * we return the intersection of the elements in "list".
2842 *
2843 * Otherwise, we align all divs and temporarily treat them
2844 * as regular variables, computing the unshifted simple hull in
2845 * uset_unshifted_simple_hull_from_basic_set_list.
2846 */
2849 {
2865 }
2869 }
2885 error:
2889 }
2891 /* Return a sequence of the basic maps that make up the maps in "list".
2892 */
2895 {
2915 }
2919 }
2921 /* Compute a superset of the convex hull of "map" that is described
2922 * by only constraints in the elements of "list".
2923 *
2924 * If "map" is the universe, then the convex hull (and therefore
2925 * any superset of the convexhull) is the universe as well.
2926 *
2927 * Otherwise, we collect all the basic maps in the map list and
2928 * continue with map_unshifted_simple_hull_from_basic_map_list.
2929 */
2932 {
2942 }
2946 }
2948 /* Compute a superset of the convex hull of "set" that is described
2949 * by only constraints in the elements of "list".
2950 */
2953 {
2955 }
2957 /* Given a set "set", return parametric bounds on the dimension "dim".
2958 */
2960 {
2966 }
2968 /* Computes a "simple hull" and then check if each dimension in the
2969 * resulting hull is bounded by a symbolic constant. If not, the
2970 * hull is intersected with the corresponding bounds on the whole set.
2971 */
2973 {
2995 }
3009 else
3013 }
3023 }
3028 }
3032 error:
3036 }