Update isl to isl-0.18-800-g4018f45

This fixes a bug in isl_flow where triggering the compute out could result in
undefined or unexpected behavior. This fixes some recent regressions we saw
in the android buildbots. Thanks Eli Friedman for reducing the corresponding
test cases.

llvm-svn: 309274

7 files changed, 114 insertions, 17 deletions

diff --git a/polly/lib/External/isl/GIT_HEAD_ID b/polly/lib/External/isl/GIT_HEAD_ID
index 82e1cd3784ab..1501c6a37f8f 100644
--- a/polly/lib/External/isl/GIT_HEAD_ID
+++ b/polly/lib/External/isl/GIT_HEAD_ID
@@ -1 +1 @@
-isl-0.18-791-ga22eb92
+isl-0.18-800-g4018f45
diff --git a/polly/lib/External/isl/include/isl/aff.h b/polly/lib/External/isl/include/isl/aff.h
index 2d3efa0f42cf..dc67819af498 100644
--- a/polly/lib/External/isl/include/isl/aff.h
+++ b/polly/lib/External/isl/include/isl/aff.h
@@ -80,25 +80,34 @@ isl_bool isl_aff_is_nan(__isl_keep isl_aff *aff);
 
 __isl_give isl_aff *isl_aff_get_div(__isl_keep isl_aff *aff, int pos);
 
+__isl_export
 __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff);
+__isl_export
 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff);
+__isl_export
 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff);
+__isl_overload
 __isl_give isl_aff *isl_aff_mod_val(__isl_take isl_aff *aff,
 	__isl_take isl_val *mod);
 
+__isl_export
 __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
 	__isl_take isl_aff *aff2);
+__isl_export
 __isl_give isl_aff *isl_aff_div(__isl_take isl_aff *aff1,
 	__isl_take isl_aff *aff2);
 __isl_export
 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
 	__isl_take isl_aff *aff2);
+__isl_export
 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
 	__isl_take isl_aff *aff2);
 
+__isl_overload
 __isl_give isl_aff *isl_aff_scale_val(__isl_take isl_aff *aff,
 	__isl_take isl_val *v);
 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f);
+__isl_overload
 __isl_give isl_aff *isl_aff_scale_down_val(__isl_take isl_aff *aff,
 	__isl_take isl_val *v);
 
@@ -234,26 +243,37 @@ __isl_give isl_set *isl_pw_aff_params(__isl_take isl_pw_aff *pwa);
 __isl_give isl_set *isl_pw_aff_domain(__isl_take isl_pw_aff *pwaff);
 __isl_give isl_pw_aff *isl_pw_aff_from_range(__isl_take isl_pw_aff *pwa);
 
+__isl_export
 __isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
 	__isl_take isl_pw_aff *pwaff2);
+__isl_export
 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
 	__isl_take isl_pw_aff *pwaff2);
+__isl_export
 __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
 	__isl_take isl_pw_aff *pwaff2);
+__isl_export
 __isl_give isl_pw_aff *isl_pw_aff_div(__isl_take isl_pw_aff *pa1,
 	__isl_take isl_pw_aff *pa2);
 __isl_export
 __isl_give isl_pw_aff *isl_pw_aff_add(__isl_take isl_pw_aff *pwaff1,
 	__isl_take isl_pw_aff *pwaff2);
+__isl_export
 __isl_give isl_pw_aff *isl_pw_aff_sub(__isl_take isl_pw_aff *pwaff1,
 	__isl_take isl_pw_aff *pwaff2);
+__isl_export
 __isl_give isl_pw_aff *isl_pw_aff_neg(__isl_take isl_pw_aff *pwaff);
+__isl_export
 __isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff);
+__isl_export
 __isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff);
+__isl_overload
 __isl_give isl_pw_aff *isl_pw_aff_mod_val(__isl_take isl_pw_aff *pa,
 	__isl_take isl_val *mod);
+__isl_export
 __isl_give isl_pw_aff *isl_pw_aff_tdiv_q(__isl_take isl_pw_aff *pa1,
 	__isl_take isl_pw_aff *pa2);
+__isl_export
 __isl_give isl_pw_aff *isl_pw_aff_tdiv_r(__isl_take isl_pw_aff *pa1,
 	__isl_take isl_pw_aff *pa2);
 
@@ -264,11 +284,14 @@ __isl_give isl_pw_aff *isl_pw_aff_intersect_domain(__isl_take isl_pw_aff *pa,
 __isl_give isl_pw_aff *isl_pw_aff_subtract_domain(__isl_take isl_pw_aff *pa,
 	__isl_take isl_set *set);
 
+__isl_export
 __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_pw_aff *cond,
 	__isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false);
 
+__isl_overload
 __isl_give isl_pw_aff *isl_pw_aff_scale_val(__isl_take isl_pw_aff *pa,
 	__isl_take isl_val *v);
+__isl_overload
 __isl_give isl_pw_aff *isl_pw_aff_scale_down_val(__isl_take isl_pw_aff *pa,
 	__isl_take isl_val *f);
 
diff --git a/polly/lib/External/isl/include/isl/schedule.h b/polly/lib/External/isl/include/isl/schedule.h
index 895888e39a24..7970b6475414 100644
--- a/polly/lib/External/isl/include/isl/schedule.h
+++ b/polly/lib/External/isl/include/isl/schedule.h
@@ -52,19 +52,25 @@ int isl_options_get_schedule_carry_self_first(isl_ctx *ctx);
 
 __isl_give isl_schedule_constraints *isl_schedule_constraints_copy(
 	__isl_keep isl_schedule_constraints *sc);
+__isl_export
 __isl_give isl_schedule_constraints *isl_schedule_constraints_on_domain(
 	__isl_take isl_union_set *domain);
+__isl_export
 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_context(
 	__isl_take isl_schedule_constraints *sc, __isl_take isl_set *context);
+__isl_export
 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_validity(
 	__isl_take isl_schedule_constraints *sc,
 	__isl_take isl_union_map *validity);
+__isl_export
 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_coincidence(
 	__isl_take isl_schedule_constraints *sc,
 	__isl_take isl_union_map *coincidence);
+__isl_export
 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_proximity(
 	__isl_take isl_schedule_constraints *sc,
 	__isl_take isl_union_map *proximity);
+__isl_export
 __isl_give isl_schedule_constraints *
 isl_schedule_constraints_set_conditional_validity(
 	__isl_take isl_schedule_constraints *sc,
@@ -113,6 +119,7 @@ void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints *sc);
 __isl_give char *isl_schedule_constraints_to_str(
 	__isl_keep isl_schedule_constraints *sc);
 
+__isl_export
 __isl_give isl_schedule *isl_schedule_constraints_compute_schedule(
 	__isl_take isl_schedule_constraints *sc);
 
diff --git a/polly/lib/External/isl/isl_flow.c b/polly/lib/External/isl/isl_flow.c
index 77a87cbbfdd0..21872b2e1a2d 100644
--- a/polly/lib/External/isl/isl_flow.c
+++ b/polly/lib/External/isl/isl_flow.c
@@ -311,6 +311,13 @@ error:
 	return NULL;
 }
 
+/* A helper struct carrying the isl_access_info and an error condition.
+ */
+struct access_sort_info {
+	isl_access_info *access_info;
+	int error;
+};
+
 /* Return -n, 0 or n (with n a positive value), depending on whether
  * the source access identified by p1 should be sorted before, together
  * or after that identified by p2.
@@ -323,10 +330,18 @@ error:
  * If not, we try to order the two statements based on the description
  * of the iteration domains.  This results in an arbitrary, but fairly
  * stable ordering.
+ *
+ * In case of an error, sort_info.error is set to true and all elements are
+ * reported to be equal.
  */
 static int access_sort_cmp(const void *p1, const void *p2, void *user)
 {
-	isl_access_info *acc = user;
+	struct access_sort_info *sort_info = user;
+	isl_access_info *acc = sort_info->access_info;
+
+	if (sort_info->error)
+		return 0;
+
 	const struct isl_labeled_map *i1, *i2;
 	int level1, level2;
 	uint32_t h1, h2;
@@ -334,16 +349,24 @@ static int access_sort_cmp(const void *p1, const void *p2, void *user)
 	i2 = (const struct isl_labeled_map *) p2;
 
 	level1 = acc->level_before(i1->data, i2->data);
+	if (level1 < 0)
+		goto error;
 	if (level1 % 2)
 		return -1;
 
 	level2 = acc->level_before(i2->data, i1->data);
+	if (level2 < 0)
+		goto error;
 	if (level2 % 2)
 		return 1;
 
 	h1 = isl_map_get_hash(i1->map);
 	h2 = isl_map_get_hash(i2->map);
 	return h1 > h2 ? 1 : h1 < h2 ? -1 : 0;
+error:
+	sort_info->error = 1;
+	return 0;
+
 }
 
 /* Sort the must source accesses in their textual order.
@@ -351,13 +374,20 @@ static int access_sort_cmp(const void *p1, const void *p2, void *user)
 static __isl_give isl_access_info *isl_access_info_sort_sources(
 	__isl_take isl_access_info *acc)
 {
+	struct access_sort_info sort_info;
+
+	sort_info.access_info = acc;
+	sort_info.error = 0;
+
 	if (!acc)
 		return NULL;
 	if (acc->n_must <= 1)
 		return acc;
 
 	if (isl_sort(acc->source, acc->n_must, sizeof(struct isl_labeled_map),
-		    access_sort_cmp, acc) < 0)
+		    access_sort_cmp, &sort_info) < 0)
+		return isl_access_info_free(acc);
+	if (sort_info.error)
 		return isl_access_info_free(acc);
 
 	return acc;
@@ -690,6 +720,9 @@ static int can_precede_at_level(int shared_level, int target_level)
  *
  * If temp_rel[j] is empty, then there can be no improvement and
  * we return immediately.
+ *
+ * This function returns 0 in case it was executed successfully and
+ * -1 in case of errors during the execution of this function.
  */
 static int intermediate_sources(__isl_keep isl_access_info *acc,
 	struct isl_map **temp_rel, int j, int sink_level)
@@ -703,11 +736,15 @@ static int intermediate_sources(__isl_keep isl_access_info *acc,
 	for (k = j - 1; k >= 0; --k) {
 		int plevel, plevel2;
 		plevel = acc->level_before(acc->source[k].data, acc->sink.data);
+		if (plevel < 0)
+			return -1;
 		if (!can_precede_at_level(plevel, sink_level))
 			continue;
 
 		plevel2 = acc->level_before(acc->source[j].data,
 						acc->source[k].data);
+		if (plevel2 < 0)
+			return -1;
 
 		for (level = sink_level; level <= depth; ++level) {
 			struct isl_map *T;
@@ -816,6 +853,8 @@ static __isl_give isl_map *all_intermediate_sources(
 
 		plevel = acc->level_before(acc->source[k].data,
 					acc->source[acc->n_must + j].data);
+		if (plevel < 0)
+			return isl_map_free(map);
 
 		for (level = sink_level; level <= depth; ++level) {
 			isl_map *T;
@@ -864,6 +903,8 @@ static __isl_give isl_map *all_intermediate_sources(
  * uncurried to [T -> S] -> K.
  * This result is then intersected with the dependence relation S -> K
  * to form the output.
+ *
+ * In case a negative depth is given, NULL is returned to indicate an error.
  */
 static __isl_give isl_map *coscheduled_source(__isl_keep isl_access_info *acc,
 	__isl_keep isl_map *old_map, int pos, int depth)
@@ -876,6 +917,9 @@ static __isl_give isl_map *coscheduled_source(__isl_keep isl_access_info *acc,
 	isl_map *equal;
 	isl_map *map;
 
+	if (depth < 0)
+		return NULL;
+
 	set_C = isl_map_range(isl_map_copy(old_map));
 	read_map = isl_map_copy(acc->sink.map);
 	read_map = isl_map_intersect_domain(read_map, set_C);
@@ -1009,6 +1053,9 @@ static __isl_give isl_flow *compute_mem_based_dependences(
 		isl_map *dep;
 
 		plevel = acc->level_before(acc->source[i].data, acc->sink.data);
+		if (plevel < 0)
+			goto error;
+
 		is_before = plevel & 1;
 		plevel >>= 1;
 
@@ -1029,6 +1076,11 @@ static __isl_give isl_flow *compute_mem_based_dependences(
 	res->must_no_source = mustdo;
 
 	return res;
+error:
+	isl_set_free(mustdo);
+	isl_set_free(maydo);
+	isl_flow_free(res);
+	return NULL;
 }
 
 /* Compute dependences for the case where there is at least one
@@ -1099,8 +1151,8 @@ static __isl_give isl_flow *compute_val_based_dependences(
 	if (isl_set_plain_is_empty(mustdo))
 		goto done;
 
-	must_rel = isl_alloc_array(ctx, struct isl_map *, acc->n_must);
-	may_rel = isl_alloc_array(ctx, struct isl_map *, acc->n_must);
+	must_rel = isl_calloc_array(ctx, struct isl_map *, acc->n_must);
+	may_rel = isl_calloc_array(ctx, struct isl_map *, acc->n_must);
 	if (!must_rel || !may_rel)
 		goto error;
 
@@ -1119,6 +1171,8 @@ static __isl_give isl_flow *compute_val_based_dependences(
 
 			plevel = acc->level_before(acc->source[j].data,
 						     acc->sink.data);
+			if (plevel < 0)
+				goto error;
 			if (!can_precede_at_level(plevel, level))
 				continue;
 
@@ -1126,13 +1180,15 @@ static __isl_give isl_flow *compute_val_based_dependences(
 			must_rel[j] = isl_map_union_disjoint(must_rel[j], T);
 			mustdo = rest;
 
-			intermediate_sources(acc, must_rel, j, level);
+			if (intermediate_sources(acc, must_rel, j, level))
+				goto error;
 
 			T = last_source(acc, maydo, j, level, &rest);
 			may_rel[j] = isl_map_union_disjoint(may_rel[j], T);
 			maydo = rest;
 
-			intermediate_sources(acc, may_rel, j, level);
+			if (intermediate_sources(acc, may_rel, j, level))
+				goto error;
 
 			if (isl_set_plain_is_empty(mustdo) &&
 			    isl_set_plain_is_empty(maydo))
@@ -1143,11 +1199,15 @@ static __isl_give isl_flow *compute_val_based_dependences(
 
 			plevel = acc->level_before(acc->source[j].data,
 						     acc->sink.data);
+			if (plevel < 0)
+				goto error;
 			if (!can_precede_at_level(plevel, level))
 				continue;
 
-			intermediate_sources(acc, must_rel, j, level);
-			intermediate_sources(acc, may_rel, j, level);
+			if (intermediate_sources(acc, must_rel, j, level))
+				goto error;
+			if (intermediate_sources(acc, may_rel, j, level))
+				goto error;
 		}
 
 		handle_coscheduled(acc, must_rel, may_rel, res);
@@ -1159,6 +1219,8 @@ static __isl_give isl_flow *compute_val_based_dependences(
 
 			plevel = acc->level_before(acc->source[acc->n_must + j].data,
 						     acc->sink.data);
+			if (plevel < 0)
+				goto error;
 			if (!can_precede_at_level(plevel, level))
 				continue;
 
@@ -1199,6 +1261,12 @@ done:
 	res->may_no_source = maydo;
 	return res;
 error:
+	if (must_rel)
+		for (j = 0; j < acc->n_must; ++j)
+			isl_map_free(must_rel[j]);
+	if (may_rel)
+		for (j = 0; j < acc->n_must; ++j)
+			isl_map_free(may_rel[j]);
 	isl_flow_free(res);
 	isl_set_free(mustdo);
 	isl_set_free(maydo);
diff --git a/polly/lib/External/isl/isl_input.c b/polly/lib/External/isl/isl_input.c
index f6f66b8cd59a..e122053e273e 100644
--- a/polly/lib/External/isl/isl_input.c
+++ b/polly/lib/External/isl/isl_input.c
@@ -1805,11 +1805,8 @@ static struct isl_map *read_disjuncts(__isl_keep isl_stream *s,
 {
 	isl_map *res;
 
-	if (isl_stream_next_token_is(s, '}')) {
-		isl_space *dim = isl_map_get_space(map);
-		isl_map_free(map);
-		return isl_map_universe(dim);
-	}
+	if (isl_stream_next_token_is(s, '}'))
+		return map;
 
 	res = read_conjuncts(s, v, isl_map_copy(map), rational);
 	while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) {
diff --git a/polly/lib/External/isl/isl_multi_templ.c b/polly/lib/External/isl/isl_multi_templ.c
index 1ea6e02ac364..f2f2618117f3 100644
--- a/polly/lib/External/isl/isl_multi_templ.c
+++ b/polly/lib/External/isl/isl_multi_templ.c
@@ -705,11 +705,11 @@ __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)(
 	if (first + n > dim || first + n < first)
 		isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
 			"index out of bounds",
-			return FN(MULTI(BASE),cow)(multi));
+			return FN(MULTI(BASE),free)(multi));
 
 	multi->space = isl_space_drop_dims(multi->space, type, first, n);
 	if (!multi->space)
-		return FN(MULTI(BASE),cow)(multi);
+		return FN(MULTI(BASE),free)(multi);
 
 	if (type == isl_dim_out) {
 		for (i = 0; i < n; ++i)
@@ -724,7 +724,7 @@ __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)(
 	for (i = 0; i < multi->n; ++i) {
 		multi->p[i] = FN(EL,drop_dims)(multi->p[i], type, first, n);
 		if (!multi->p[i])
-			return FN(MULTI(BASE),cow)(multi);
+			return FN(MULTI(BASE),free)(multi);
 	}
 
 	return multi;
diff --git a/polly/lib/External/isl/isl_test.c b/polly/lib/External/isl/isl_test.c
index cc81e1b28248..2773be51dd0f 100644
--- a/polly/lib/External/isl/isl_test.c
+++ b/polly/lib/External/isl/isl_test.c
@@ -190,6 +190,8 @@ struct {
 	{ "{ [x] -> [] : exists (a, b: 0 <= a <= 1 and 0 <= b <= 3 and "
 			    "2b <= x - 8a and 2b >= -1 + x - 8a) }",
 	  "{ [x] -> [] : 0 <= x <= 15 }" },
+	{ "{ [x] -> [x] : }",
+	  "{ [x] -> [x] }" },
 };
 
 int test_parse(struct isl_ctx *ctx)