summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--polly/lib/External/isl/GIT_HEAD_ID2
-rw-r--r--polly/lib/External/isl/doc/manual.pdfbin475438 -> 475438 bytes
-rw-r--r--polly/lib/External/isl/isl_coalesce.c272
-rw-r--r--polly/lib/External/isl/isl_tab.c267
-rw-r--r--polly/lib/External/isl/isl_tab.h2
-rw-r--r--polly/lib/External/isl/isl_test.c13
6 files changed, 512 insertions, 44 deletions
diff --git a/polly/lib/External/isl/GIT_HEAD_ID b/polly/lib/External/isl/GIT_HEAD_ID
index 37b0f696a6f..86302141e09 100644
--- a/polly/lib/External/isl/GIT_HEAD_ID
+++ b/polly/lib/External/isl/GIT_HEAD_ID
@@ -1 +1 @@
-isl-0.18-17-g2844ebf
+isl-0.18-28-gccb9f33
diff --git a/polly/lib/External/isl/doc/manual.pdf b/polly/lib/External/isl/doc/manual.pdf
index e9102f38195..61f0077d3d9 100644
--- a/polly/lib/External/isl/doc/manual.pdf
+++ b/polly/lib/External/isl/doc/manual.pdf
Binary files differ
diff --git a/polly/lib/External/isl/isl_coalesce.c b/polly/lib/External/isl/isl_coalesce.c
index 4a8e0ee24e9..09d9c7cc203 100644
--- a/polly/lib/External/isl/isl_coalesce.c
+++ b/polly/lib/External/isl/isl_coalesce.c
@@ -615,8 +615,11 @@ static int contains(struct isl_coalesce_info *info, struct isl_tab *tab)
* In particular, we replace constraint k, say f >= 0, by constraint
* f <= -1, add the inequalities of "j" that are valid for "i"
* and check if the result is a subset of basic map "j".
- * If so, then we know that this result is exactly equal to basic map "j"
- * since all its constraints are valid for basic map "j".
+ * To improve the chances of the subset relation being detected,
+ * any variable that only attains a single integer value
+ * in the tableau of "i" is first fixed to that value.
+ * If the result is a subset, then we know that this result is exactly equal
+ * to basic map "j" since all its constraints are valid for basic map "j".
* By combining the valid constraints of "i" (all equalities and all
* inequalities except "k") and the valid constraints of "j" we therefore
* obtain a basic map that is equal to their union.
@@ -677,6 +680,8 @@ static enum isl_change is_adj_ineq_extension(int i, int j,
if (isl_tab_add_ineq(info[i].tab, info[j].bmap->ineq[k]) < 0)
return isl_change_error;
}
+ if (isl_tab_detect_constants(info[i].tab) < 0)
+ return isl_change_error;
super = contains(&info[j], info[i].tab);
if (super < 0)
@@ -2298,72 +2303,263 @@ static int same_divs(__isl_keep isl_basic_map *bmap1,
return 1;
}
-/* Expand info->tab in the same way info->bmap was expanded in
- * isl_basic_map_expand_divs using the expansion "exp" and
+/* Assuming that "tab" contains the equality constraints and
+ * the initial inequality constraints of "bmap", copy the remaining
+ * inequality constraints of "bmap" to "Tab".
+ */
+static isl_stat copy_ineq(struct isl_tab *tab, __isl_keep isl_basic_map *bmap)
+{
+ int i, n_ineq;
+
+ if (!bmap)
+ return isl_stat_error;
+
+ n_ineq = tab->n_con - tab->n_eq;
+ for (i = n_ineq; i < bmap->n_ineq; ++i)
+ if (isl_tab_add_ineq(tab, bmap->ineq[i]) < 0)
+ return isl_stat_error;
+
+ return isl_stat_ok;
+}
+
+/* Description of an integer division that is added
+ * during an expansion.
+ * "pos" is the position of the corresponding variable.
+ * "cst" indicates whether this integer division has a fixed value.
+ * "val" contains the fixed value, if the value is fixed.
+ */
+struct isl_expanded {
+ int pos;
+ isl_bool cst;
+ isl_int val;
+};
+
+/* For each of the "n" integer division variables "expanded",
+ * if the variable has a fixed value, then add two inequality
+ * constraints expressing the fixed value.
+ * Otherwise, add the corresponding div constraints.
+ * The caller is responsible for removing the div constraints
+ * that it added for all these "n" integer divisions.
+ *
+ * The div constraints and the pair of inequality constraints
+ * forcing the fixed value cannot both be added for a given variable
+ * as the combination may render some of the original constraints redundant.
+ * These would then be ignored during the coalescing detection,
+ * while they could remain in the fused result.
+ *
+ * The two added inequality constraints are
+ *
+ * -a + v >= 0
+ * a - v >= 0
+ *
+ * with "a" the variable and "v" its fixed value.
+ * The facet corresponding to one of these two constraints is selected
+ * in the tableau to ensure that the pair of inequality constraints
+ * is treated as an equality constraint.
+ *
+ * The information in info->ineq is thrown away because it was
+ * computed in terms of div constraints, while some of those
+ * have now been replaced by these pairs of inequality constraints.
+ */
+static isl_stat fix_constant_divs(struct isl_coalesce_info *info,
+ int n, struct isl_expanded *expanded)
+{
+ unsigned o_div;
+ int i;
+ isl_vec *ineq;
+
+ o_div = isl_basic_map_offset(info->bmap, isl_dim_div) - 1;
+ ineq = isl_vec_alloc(isl_tab_get_ctx(info->tab), 1 + info->tab->n_var);
+ if (!ineq)
+ return isl_stat_error;
+ isl_seq_clr(ineq->el + 1, info->tab->n_var);
+
+ for (i = 0; i < n; ++i) {
+ if (!expanded[i].cst) {
+ info->bmap = isl_basic_map_extend_constraints(
+ info->bmap, 0, 2);
+ if (isl_basic_map_add_div_constraints(info->bmap,
+ expanded[i].pos - o_div) < 0)
+ break;
+ } else {
+ isl_int_set_si(ineq->el[1 + expanded[i].pos], -1);
+ isl_int_set(ineq->el[0], expanded[i].val);
+ info->bmap = isl_basic_map_add_ineq(info->bmap,
+ ineq->el);
+ isl_int_set_si(ineq->el[1 + expanded[i].pos], 1);
+ isl_int_neg(ineq->el[0], expanded[i].val);
+ info->bmap = isl_basic_map_add_ineq(info->bmap,
+ ineq->el);
+ isl_int_set_si(ineq->el[1 + expanded[i].pos], 0);
+ }
+ if (copy_ineq(info->tab, info->bmap) < 0)
+ break;
+ if (expanded[i].cst &&
+ isl_tab_select_facet(info->tab, info->tab->n_con - 1) < 0)
+ break;
+ }
+
+ isl_vec_free(ineq);
+
+ clear_status(info);
+ init_status(info);
+
+ return i < n ? isl_stat_error : isl_stat_ok;
+}
+
+/* Insert the "n" integer division variables "expanded"
+ * into info->tab and info->bmap and
* update info->ineq with respect to the redundant constraints
- * in the resulting tableau. "bmap" is the original version
- * of info->bmap, i.e., the one that corresponds to the current
- * state of info->tab. The number of constraints in "bmap"
+ * in the resulting tableau.
+ * "bmap" contains the result of this insertion in info->bmap,
+ * while info->bmap is the original version
+ * of "bmap", i.e., the one that corresponds to the current
+ * state of info->tab. The number of constraints in info->bmap
* is assumed to be the same as the number of constraints
* in info->tab. This is required to be able to detect
- * the extra constraints in info->bmap.
+ * the extra constraints in "bmap".
*
* In particular, introduce extra variables corresponding
* to the extra integer divisions and add the div constraints
- * that were added to info->bmap after info->tab was created
- * from the original info->bmap.
+ * that were added to "bmap" after info->tab was created
+ * from info->bmap.
+ * Furthermore, check if these extra integer divisions happen
+ * to attain a fixed integer value in info->tab.
+ * If so, replace the corresponding div constraints by pairs
+ * of inequality constraints that fix these
+ * integer divisions to their single integer values.
+ * Replace info->bmap by "bmap" to match the changes to info->tab.
* info->ineq was computed without a tableau and therefore
* does not take into account the redundant constraints
* in the tableau. Mark them here.
+ * There is no need to check the newly added div constraints
+ * since they cannot be redundant.
+ * The redundancy check is not performed when constants have been discovered
+ * since info->ineq is completely thrown away in this case.
*/
-static isl_stat expand_tab(struct isl_coalesce_info *info, int *exp,
- __isl_keep isl_basic_map *bmap)
+static isl_stat tab_insert_divs(struct isl_coalesce_info *info,
+ int n, struct isl_expanded *expanded, __isl_take isl_basic_map *bmap)
{
- unsigned total, pos, n_div;
- int extra_var;
- int i, n, j, n_ineq;
+ int i, n_ineq;
unsigned n_eq;
+ struct isl_tab_undo *snap;
+ int any;
if (!bmap)
return isl_stat_error;
- if (bmap->n_eq + bmap->n_ineq != info->tab->n_con)
+ if (info->bmap->n_eq + info->bmap->n_ineq != info->tab->n_con)
isl_die(isl_basic_map_get_ctx(bmap), isl_error_internal,
"original tableau does not correspond "
- "to original basic map", return isl_stat_error);
+ "to original basic map", goto error);
- total = isl_basic_map_dim(info->bmap, isl_dim_all);
- n_div = isl_basic_map_dim(info->bmap, isl_dim_div);
+ if (isl_tab_extend_vars(info->tab, n) < 0)
+ goto error;
+ if (isl_tab_extend_cons(info->tab, 2 * n) < 0)
+ goto error;
+
+ for (i = 0; i < n; ++i) {
+ if (isl_tab_insert_var(info->tab, expanded[i].pos) < 0)
+ goto error;
+ }
+
+ snap = isl_tab_snap(info->tab);
+
+ n_ineq = info->tab->n_con - info->tab->n_eq;
+ if (copy_ineq(info->tab, bmap) < 0)
+ goto error;
+
+ isl_basic_map_free(info->bmap);
+ info->bmap = bmap;
+
+ any = 0;
+ for (i = 0; i < n; ++i) {
+ expanded[i].cst = isl_tab_is_constant(info->tab,
+ expanded[i].pos, &expanded[i].val);
+ if (expanded[i].cst < 0)
+ return isl_stat_error;
+ if (expanded[i].cst)
+ any = 1;
+ }
+
+ if (any) {
+ if (isl_tab_rollback(info->tab, snap) < 0)
+ return isl_stat_error;
+ info->bmap = isl_basic_map_cow(info->bmap);
+ if (isl_basic_map_free_inequality(info->bmap, 2 * n) < 0)
+ return isl_stat_error;
+
+ return fix_constant_divs(info, n, expanded);
+ }
+
+ n_eq = info->bmap->n_eq;
+ for (i = 0; i < n_ineq; ++i) {
+ if (isl_tab_is_redundant(info->tab, n_eq + i))
+ info->ineq[i] = STATUS_REDUNDANT;
+ }
+
+ return isl_stat_ok;
+error:
+ isl_basic_map_free(bmap);
+ return isl_stat_error;
+}
+
+/* Expand info->tab and info->bmap in the same way "bmap" was expanded
+ * in isl_basic_map_expand_divs using the expansion "exp" and
+ * update info->ineq with respect to the redundant constraints
+ * in the resulting tableau. info->bmap is the original version
+ * of "bmap", i.e., the one that corresponds to the current
+ * state of info->tab. The number of constraints in info->bmap
+ * is assumed to be the same as the number of constraints
+ * in info->tab. This is required to be able to detect
+ * the extra constraints in "bmap".
+ *
+ * Extract the positions where extra local variables are introduced
+ * from "exp" and call tab_insert_divs.
+ */
+static isl_stat expand_tab(struct isl_coalesce_info *info, int *exp,
+ __isl_take isl_basic_map *bmap)
+{
+ isl_ctx *ctx;
+ struct isl_expanded *expanded;
+ int i, j, k, n;
+ int extra_var;
+ unsigned total, pos, n_div;
+ isl_stat r;
+
+ total = isl_basic_map_dim(bmap, isl_dim_all);
+ n_div = isl_basic_map_dim(bmap, isl_dim_div);
pos = total - n_div;
extra_var = total - info->tab->n_var;
n = n_div - extra_var;
- if (isl_tab_extend_vars(info->tab, extra_var) < 0)
- return isl_stat_error;
- if (isl_tab_extend_cons(info->tab, 2 * extra_var) < 0)
- return isl_stat_error;
+ ctx = isl_basic_map_get_ctx(bmap);
+ expanded = isl_calloc_array(ctx, struct isl_expanded, extra_var);
+ if (extra_var && !expanded)
+ goto error;
i = 0;
+ k = 0;
for (j = 0; j < n_div; ++j) {
if (i < n && exp[i] == j) {
++i;
continue;
}
- if (isl_tab_insert_var(info->tab, pos + j) < 0)
- return isl_stat_error;
+ expanded[k++].pos = pos + j;
}
- n_ineq = info->tab->n_con - info->tab->n_eq;
- for (i = n_ineq; i < info->bmap->n_ineq; ++i)
- if (isl_tab_add_ineq(info->tab, info->bmap->ineq[i]) < 0)
- return isl_stat_error;
+ for (k = 0; k < extra_var; ++k)
+ isl_int_init(expanded[k].val);
- n_eq = info->bmap->n_eq;
- for (i = 0; i < info->bmap->n_ineq; ++i) {
- if (isl_tab_is_redundant(info->tab, n_eq + i))
- info->ineq[i] = STATUS_REDUNDANT;
- }
+ r = tab_insert_divs(info, extra_var, expanded, bmap);
- return isl_stat_ok;
+ for (k = 0; k < extra_var; ++k)
+ isl_int_clear(expanded[k].val);
+ free(expanded);
+
+ return r;
+error:
+ isl_basic_map_free(bmap);
+ return isl_stat_error;
}
/* Check if the union of the basic maps represented by info[i] and info[j]
@@ -2412,10 +2608,9 @@ static enum isl_change coalesce_expand_tab_divs(__isl_take isl_basic_map *bmap,
return known < 0 ? isl_change_error : isl_change_none;
}
- bmap_i = info[i].bmap;
- info[i].bmap = isl_basic_map_copy(bmap);
+ bmap_i = isl_basic_map_copy(info[i].bmap);
snap = isl_tab_snap(info[i].tab);
- if (!info[i].bmap || expand_tab(&info[i], exp, bmap_i) < 0)
+ if (expand_tab(&info[i], exp, bmap) < 0)
change = isl_change_error;
init_status(&info[j]);
@@ -2433,7 +2628,6 @@ static enum isl_change coalesce_expand_tab_divs(__isl_take isl_basic_map *bmap,
change = isl_change_error;
}
- isl_basic_map_free(bmap);
return change;
}
diff --git a/polly/lib/External/isl/isl_tab.c b/polly/lib/External/isl/isl_tab.c
index e38c7fef14f..fff2dd1bd2b 100644
--- a/polly/lib/External/isl/isl_tab.c
+++ b/polly/lib/External/isl/isl_tab.c
@@ -2,6 +2,7 @@
* Copyright 2008-2009 Katholieke Universiteit Leuven
* Copyright 2013 Ecole Normale Superieure
* Copyright 2014 INRIA Rocquencourt
+ * Copyright 2016 Sven Verdoolaege
*
* Use of this software is governed by the MIT license
*
@@ -2010,13 +2011,21 @@ error:
return NULL;
}
+/* Does the sample value of row "row" of "tab" involve the big parameter,
+ * if any?
+ */
+static int row_is_big(struct isl_tab *tab, int row)
+{
+ return tab->M && !isl_int_is_zero(tab->mat->row[row][2]);
+}
+
static int row_is_manifestly_zero(struct isl_tab *tab, int row)
{
unsigned off = 2 + tab->M;
if (!isl_int_is_zero(tab->mat->row[row][1]))
return 0;
- if (tab->M && !isl_int_is_zero(tab->mat->row[row][2]))
+ if (row_is_big(tab, row))
return 0;
return isl_seq_first_non_zero(tab->mat->row[row] + off + tab->n_dead,
tab->n_col - tab->n_dead) == -1;
@@ -2576,6 +2585,22 @@ struct isl_vec *isl_tab_get_sample_value(struct isl_tab *tab)
return vec;
}
+/* Store the sample value of "var" of "tab" rounded up (if sgn > 0)
+ * or down (if sgn < 0) to the nearest integer in *v.
+ */
+static void get_rounded_sample_value(struct isl_tab *tab,
+ struct isl_tab_var *var, int sgn, isl_int *v)
+{
+ if (!var->is_row)
+ isl_int_set_si(*v, 0);
+ else if (sgn > 0)
+ isl_int_cdiv_q(*v, tab->mat->row[var->index][1],
+ tab->mat->row[var->index][0]);
+ else
+ isl_int_fdiv_q(*v, tab->mat->row[var->index][1],
+ tab->mat->row[var->index][0]);
+}
+
/* Update "bmap" based on the results of the tableau "tab".
* In particular, implicit equalities are made explicit, redundant constraints
* are removed and if the sample value happens to be integer, it is stored
@@ -3187,7 +3212,7 @@ int isl_tab_is_equality(struct isl_tab *tab, int con)
off = 2 + tab->M;
return isl_int_is_zero(tab->mat->row[row][1]) &&
- (!tab->M || isl_int_is_zero(tab->mat->row[row][2])) &&
+ !row_is_big(tab, row) &&
isl_seq_first_non_zero(tab->mat->row[row] + off + tab->n_dead,
tab->n_col - tab->n_dead) == -1;
}
@@ -3264,8 +3289,7 @@ enum isl_lp_result isl_tab_min(struct isl_tab *tab,
isl_int_set(*opt, tab->mat->row[var->index][1]);
isl_int_set(*opt_denom, tab->mat->row[var->index][0]);
} else
- isl_int_cdiv_q(*opt, tab->mat->row[var->index][1],
- tab->mat->row[var->index][0]);
+ get_rounded_sample_value(tab, var, 1, opt);
}
if (isl_tab_rollback(tab, snap) < 0)
return isl_lp_error;
@@ -3294,6 +3318,241 @@ int isl_tab_is_redundant(struct isl_tab *tab, int con)
return tab->con[con].is_row && tab->con[con].index < tab->n_redundant;
}
+/* Is variable "var" of "tab" fixed to a constant value by its row
+ * in the tableau?
+ * If so and if "value" is not NULL, then store this constant value
+ * in "value".
+ *
+ * That is, is it a row variable that only has non-zero coefficients
+ * for dead columns?
+ */
+static isl_bool is_constant(struct isl_tab *tab, struct isl_tab_var *var,
+ isl_int *value)
+{
+ unsigned off = 2 + tab->M;
+ isl_mat *mat = tab->mat;
+ int n;
+ int row;
+ int pos;
+
+ if (!var->is_row)
+ return isl_bool_false;
+ row = var->index;
+ if (row_is_big(tab, row))
+ return isl_bool_false;
+ n = tab->n_col - tab->n_dead;
+ pos = isl_seq_first_non_zero(mat->row[row] + off + tab->n_dead, n);
+ if (pos != -1)
+ return isl_bool_false;
+ if (value)
+ isl_int_divexact(*value, mat->row[row][1], mat->row[row][0]);
+ return isl_bool_true;
+}
+
+/* Has the variable "var' of "tab" reached a value that is greater than
+ * or equal (if sgn > 0) or smaller than or equal (if sgn < 0) to "target"?
+ * "tmp" has been initialized by the caller and can be used
+ * to perform local computations.
+ *
+ * If the sample value involves the big parameter, then any value
+ * is reached.
+ * Otherwise check if n/d >= t, i.e., n >= d * t (if sgn > 0)
+ * or n/d <= t, i.e., n <= d * t (if sgn < 0).
+ */
+static int reached(struct isl_tab *tab, struct isl_tab_var *var, int sgn,
+ isl_int target, isl_int *tmp)
+{
+ if (row_is_big(tab, var->index))
+ return 1;
+ isl_int_mul(*tmp, tab->mat->row[var->index][0], target);
+ if (sgn > 0)
+ return isl_int_ge(tab->mat->row[var->index][1], *tmp);
+ else
+ return isl_int_le(tab->mat->row[var->index][1], *tmp);
+}
+
+/* Can variable "var" of "tab" attain the value "target" by
+ * pivoting up (if sgn > 0) or down (if sgn < 0)?
+ * If not, then pivot up [down] to the greatest [smallest]
+ * rational value.
+ * "tmp" has been initialized by the caller and can be used
+ * to perform local computations.
+ *
+ * If the variable is manifestly unbounded in the desired direction,
+ * then it can attain any value.
+ * Otherwise, it can be moved to a row.
+ * Continue pivoting until the target is reached.
+ * If no more pivoting can be performed, the maximal [minimal]
+ * rational value has been reached and the target cannot be reached.
+ * If the variable would be pivoted into a manifestly unbounded column,
+ * then the target can be reached.
+ */
+static isl_bool var_reaches(struct isl_tab *tab, struct isl_tab_var *var,
+ int sgn, isl_int target, isl_int *tmp)
+{
+ int row, col;
+
+ if (sgn < 0 && min_is_manifestly_unbounded(tab, var))
+ return isl_bool_true;
+ if (sgn > 0 && max_is_manifestly_unbounded(tab, var))
+ return isl_bool_true;
+ if (to_row(tab, var, sgn) < 0)
+ return isl_bool_error;
+ while (!reached(tab, var, sgn, target, tmp)) {
+ find_pivot(tab, var, var, sgn, &row, &col);
+ if (row == -1)
+ return isl_bool_false;
+ if (row == var->index)
+ return isl_bool_true;
+ if (isl_tab_pivot(tab, row, col) < 0)
+ return isl_bool_error;
+ }
+
+ return isl_bool_true;
+}
+
+/* Check if variable "var" of "tab" can only attain a single (integer)
+ * value, and, if so, add an equality constraint to fix the variable
+ * to this single value and store the result in "target".
+ * "target" and "tmp" have been initialized by the caller.
+ *
+ * Given the current sample value, round it down and check
+ * whether it is possible to attain a strictly smaller integer value.
+ * If so, the variable is not restricted to a single integer value.
+ * Otherwise, the search stops at the smallest rational value.
+ * Round up this value and check whether it is possible to attain
+ * a strictly greater integer value.
+ * If so, the variable is not restricted to a single integer value.
+ * Otherwise, the search stops at the greatest rational value.
+ * If rounding down this value yields a value that is different
+ * from rounding up the smallest rational value, then the variable
+ * cannot attain any integer value. Mark the tableau empty.
+ * Otherwise, add an equality constraint that fixes the variable
+ * to the single integer value found.
+ */
+static isl_bool detect_constant_with_tmp(struct isl_tab *tab,
+ struct isl_tab_var *var, isl_int *target, isl_int *tmp)
+{
+ isl_bool reached;
+ isl_vec *eq;
+ int pos;
+ isl_stat r;
+
+ get_rounded_sample_value(tab, var, -1, target);
+ isl_int_sub_ui(*target, *target, 1);
+ reached = var_reaches(tab, var, -1, *target, tmp);
+ if (reached < 0 || reached)
+ return isl_bool_not(reached);
+ get_rounded_sample_value(tab, var, 1, target);
+ isl_int_add_ui(*target, *target, 1);
+ reached = var_reaches(tab, var, 1, *target, tmp);
+ if (reached < 0 || reached)
+ return isl_bool_not(reached);
+ get_rounded_sample_value(tab, var, -1, tmp);
+ isl_int_sub_ui(*target, *target, 1);
+ if (isl_int_ne(*target, *tmp)) {
+ if (isl_tab_mark_empty(tab) < 0)
+ return isl_bool_error;
+ return isl_bool_false;
+ }
+
+ if (isl_tab_extend_cons(tab, 1) < 0)
+ return isl_bool_error;
+ eq = isl_vec_alloc(isl_tab_get_ctx(tab), 1 + tab->n_var);
+ if (!eq)
+ return isl_bool_error;
+ pos = var - tab->var;
+ isl_seq_clr(eq->el + 1, tab->n_var);
+ isl_int_set_si(eq->el[1 + pos], -1);
+ isl_int_set(eq->el[0], *target);
+ r = isl_tab_add_eq(tab, eq->el);
+ isl_vec_free(eq);
+
+ return r < 0 ? isl_bool_error : isl_bool_true;
+}
+
+/* Check if variable "var" of "tab" can only attain a single (integer)
+ * value, and, if so, add an equality constraint to fix the variable
+ * to this single value and store the result in "value" (if "value"
+ * is not NULL).
+ *
+ * If the current sample value involves the big parameter,
+ * then the variable cannot have a fixed integer value.
+ * If the variable is already fixed to a single value by its row, then
+ * there is no need to add another equality constraint.
+ *
+ * Otherwise, allocate some temporary variables and continue
+ * with detect_constant_with_tmp.
+ */
+static isl_bool get_constant(struct isl_tab *tab, struct isl_tab_var *var,
+ isl_int *value)
+{
+ isl_int target, tmp;
+ isl_bool is_cst;
+
+ if (var->is_row && row_is_big(tab, var->index))
+ return isl_bool_false;
+ is_cst = is_constant(tab, var, value);
+ if (is_cst < 0 || is_cst)
+ return is_cst;
+
+ if (!value)
+ isl_int_init(target);
+ isl_int_init(tmp);
+
+ is_cst = detect_constant_with_tmp(tab, var,
+ value ? value : &target, &tmp);
+
+ isl_int_clear(tmp);
+ if (!value)
+ isl_int_clear(target);
+
+ return is_cst;
+}
+
+/* Check if variable "var" of "tab" can only attain a single (integer)
+ * value, and, if so, add an equality constraint to fix the variable
+ * to this single value and store the result in "value" (if "value"
+ * is not NULL).
+ *
+ * For rational tableaus, nothing needs to be done.
+ */
+isl_bool isl_tab_is_constant(struct isl_tab *tab, int var, isl_int *value)
+{
+ if (!tab)
+ return isl_bool_error;
+ if (var < 0 || var >= tab->n_var)
+ isl_die(isl_tab_get_ctx(tab), isl_error_invalid,
+ "position out of bounds", return isl_bool_error);
+ if (tab->rational)
+ return isl_bool_false;
+
+ return get_constant(tab, &tab->var[var], value);
+}
+
+/* Check if any of the variables of "tab" can only attain a single (integer)
+ * value, and, if so, add equality constraints to fix those variables
+ * to these single values.
+ *
+ * For rational tableaus, nothing needs to be done.
+ */
+isl_stat isl_tab_detect_constants(struct isl_tab *tab)
+{
+ int i;
+
+ if (!tab)
+ return isl_stat_error;
+ if (tab->rational)
+ return isl_stat_ok;
+
+ for (i = 0; i < tab->n_var; ++i) {
+ if (get_constant(tab, &tab->var[i], NULL) < 0)
+ return isl_stat_error;
+ }
+
+ return isl_stat_ok;
+}
+
/* Take a snapshot of the tableau that can be restored by a call to
* isl_tab_rollback.
*/
diff --git a/polly/lib/External/isl/isl_tab.h b/polly/lib/External/isl/isl_tab.h
index df5642ee41e..eee25d7fd16 100644
--- a/polly/lib/External/isl/isl_tab.h
+++ b/polly/lib/External/isl/isl_tab.h
@@ -317,6 +317,8 @@ int isl_tab_save_samples(struct isl_tab *tab) WARN_UNUSED;
struct isl_tab *isl_tab_detect_equalities(struct isl_tab *tab,
struct isl_tab *tab_cone) WARN_UNUSED;
+isl_bool isl_tab_is_constant(struct isl_tab *tab, int var, isl_int *value);
+isl_stat isl_tab_detect_constants(struct isl_tab *tab);
int isl_tab_push_callback(struct isl_tab *tab,
struct isl_tab_callback *callback) WARN_UNUSED;
diff --git a/polly/lib/External/isl/isl_test.c b/polly/lib/External/isl/isl_test.c
index c129f3e11da..42a5b63cd2d 100644
--- a/polly/lib/External/isl/isl_test.c
+++ b/polly/lib/External/isl/isl_test.c
@@ -1878,6 +1878,19 @@ struct {
"(a < 0 and 3*floor((a)/3) < a) }" },
{ 1, "{ [a] : (a <= 0 and 3*floor((a)/3) = a) or "
"(a < -1 and 3*floor((a)/3) < a) }" },
+ { 1, "{ [a, b] : a <= 1024 and b >= 0 and "
+ "((-31 - a + b <= 32*floor((-1 - a)/32) <= -33 + b and "
+ "32*floor((-1 - a)/32) <= -16 + b + 16*floor((-1 - a)/16))"
+ "or (2 <= a <= 15 and b < a)) }" },
+ { 1, "{ [a] : a > 0 and ((16*floor((a)/16) < a and "
+ "32*floor((a)/32) < a) or a <= 15) }" },
+ { 1, "{ [a, b, c, d] : (-a + d) mod 64 = 0 and a <= 8 and b <= 1 and "
+ "10 - a <= c <= 3 and d >= 5 and 9 - 64b <= d <= 70;"
+ "[a, b = 1, c, d] : (-a + d) mod 64 = 0 and a <= 8 and c >= 4 and "
+ "10 - a <= c <= 5 and 5 <= d <= 73 - c }" },
+ { 1, "[n, m] -> { S_0[i] : (-n + i) mod 3 = 0 and m >= 3 + n and "
+ "i >= n and 3*floor((2 + n + 2m)/3) <= n + 3m - i; "
+ "S_0[n] : n <= m <= 2 + n }" },
};
/* A specialized coalescing test case that would result
OpenPOWER on IntegriCloud