diff options
| -rw-r--r-- | polly/lib/External/isl/doc/user.pod | 3 | ||||
| -rw-r--r-- | polly/lib/External/isl/include/isl/deprecated/map_int.h | 2 | ||||
| -rw-r--r-- | polly/lib/External/isl/include/isl/map.h | 8 | ||||
| -rw-r--r-- | polly/lib/External/isl/include/isl/set.h | 13 | ||||
| -rw-r--r-- | polly/lib/External/isl/isl_hide_deprecated.h | 1 | ||||
| -rw-r--r-- | polly/lib/External/isl/isl_map.c | 60 | ||||
| -rw-r--r-- | polly/lib/External/isl/isl_map_simplify.c | 5 | ||||
| -rw-r--r-- | polly/lib/External/isl/isl_scheduler.c | 89 | ||||
| -rw-r--r-- | polly/lib/External/isl/isl_tab_pip.c | 2 | ||||
| -rw-r--r-- | polly/lib/External/isl/isl_test.c | 40 |
10 files changed, 104 insertions, 119 deletions
diff --git a/polly/lib/External/isl/doc/user.pod b/polly/lib/External/isl/doc/user.pod index b5b65feeb27..68b00676a21 100644 --- a/polly/lib/External/isl/doc/user.pod +++ b/polly/lib/External/isl/doc/user.pod @@ -5239,6 +5239,9 @@ are not sufficient. unsigned n); #include <isl/map.h> + __isl_give isl_basic_map *isl_basic_map_add_dims( + __isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned n); __isl_give isl_map *isl_map_add_dims( __isl_take isl_map *map, enum isl_dim_type type, unsigned n); diff --git a/polly/lib/External/isl/include/isl/deprecated/map_int.h b/polly/lib/External/isl/include/isl/deprecated/map_int.h index 915afbf8661..e9f770191fb 100644 --- a/polly/lib/External/isl/include/isl/deprecated/map_int.h +++ b/polly/lib/External/isl/include/isl/deprecated/map_int.h @@ -15,8 +15,6 @@ __isl_give isl_map *isl_map_fix(__isl_take isl_map *map, enum isl_dim_type type, unsigned pos, isl_int value); int isl_map_plain_is_fixed(__isl_keep isl_map *map, enum isl_dim_type type, unsigned pos, isl_int *val); -int isl_map_fast_is_fixed(__isl_keep isl_map *map, - enum isl_dim_type type, unsigned pos, isl_int *val); __isl_give isl_map *isl_map_fixed_power(__isl_take isl_map *map, isl_int exp); diff --git a/polly/lib/External/isl/include/isl/map.h b/polly/lib/External/isl/include/isl/map.h index 7da71d3fc24..837d565522d 100644 --- a/polly/lib/External/isl/include/isl/map.h +++ b/polly/lib/External/isl/include/isl/map.h @@ -295,8 +295,6 @@ __isl_give isl_val *isl_basic_map_plain_get_val_if_fixed( int isl_basic_map_image_is_bounded(__isl_keep isl_basic_map *bmap); int isl_basic_map_is_universe(__isl_keep isl_basic_map *bmap); int isl_basic_map_plain_is_empty(__isl_keep isl_basic_map *bmap); -ISL_DEPRECATED -int isl_basic_map_fast_is_empty(__isl_keep isl_basic_map *bmap); __isl_export int isl_basic_map_is_empty(__isl_keep isl_basic_map *bmap); __isl_export @@ -436,7 +434,7 @@ __isl_give isl_basic_map *isl_map_affine_hull(__isl_take isl_map *map); __isl_give isl_basic_map *isl_map_convex_hull(__isl_take isl_map *map); __isl_export __isl_give isl_basic_map *isl_map_polyhedral_hull(__isl_take isl_map *map); -__isl_give isl_basic_map *isl_basic_map_add(__isl_take isl_basic_map *bmap, +__isl_give isl_basic_map *isl_basic_map_add_dims(__isl_take isl_basic_map *bmap, enum isl_dim_type type, unsigned n); __isl_give isl_map *isl_map_add_dims(__isl_take isl_map *map, enum isl_dim_type type, unsigned n); @@ -547,8 +545,6 @@ __isl_export __isl_give isl_basic_map *isl_map_sample(__isl_take isl_map *map); int isl_map_plain_is_empty(__isl_keep isl_map *map); -ISL_DEPRECATED -int isl_map_fast_is_empty(__isl_keep isl_map *map); int isl_map_plain_is_universe(__isl_keep isl_map *map); __isl_export int isl_map_is_empty(__isl_keep isl_map *map); @@ -631,8 +627,6 @@ __isl_export __isl_give isl_map *isl_map_coalesce(__isl_take isl_map *map); int isl_map_plain_is_equal(__isl_keep isl_map *map1, __isl_keep isl_map *map2); -ISL_DEPRECATED -int isl_map_fast_is_equal(__isl_keep isl_map *map1, __isl_keep isl_map *map2); uint32_t isl_map_get_hash(__isl_keep isl_map *map); diff --git a/polly/lib/External/isl/include/isl/set.h b/polly/lib/External/isl/include/isl/set.h index 068e785a691..50e91db637e 100644 --- a/polly/lib/External/isl/include/isl/set.h +++ b/polly/lib/External/isl/include/isl/set.h @@ -240,8 +240,6 @@ int isl_basic_set_dims_get_sign(__isl_keep isl_basic_set *bset, int isl_basic_set_is_universe(__isl_keep isl_basic_set *bset); int isl_basic_set_plain_is_empty(__isl_keep isl_basic_set *bset); -ISL_DEPRECATED -int isl_basic_set_fast_is_empty(__isl_keep isl_basic_set *bset); __isl_export int isl_basic_set_is_empty(__isl_keep isl_basic_set *bset); int isl_basic_set_is_bounded(__isl_keep isl_basic_set *bset); @@ -333,7 +331,7 @@ __isl_give isl_set *isl_set_insert_dims(__isl_take isl_set *set, enum isl_dim_type type, unsigned pos, unsigned n); __isl_give isl_basic_set *isl_basic_set_add_dims(__isl_take isl_basic_set *bset, enum isl_dim_type type, unsigned n); -/* deprecated */ +ISL_DEPRECATED __isl_give isl_basic_set *isl_basic_set_add(__isl_take isl_basic_set *bset, enum isl_dim_type type, unsigned n); __isl_give isl_set *isl_set_add_dims(__isl_take isl_set *set, @@ -389,11 +387,7 @@ int isl_set_involves_dims(__isl_keep isl_set *set, void isl_set_print_internal(__isl_keep isl_set *set, FILE *out, int indent); int isl_set_plain_is_empty(__isl_keep isl_set *set); -ISL_DEPRECATED -int isl_set_fast_is_empty(__isl_keep isl_set *set); int isl_set_plain_is_universe(__isl_keep isl_set *set); -ISL_DEPRECATED -int isl_set_fast_is_universe(__isl_keep isl_set *set); int isl_set_is_params(__isl_keep isl_set *set); __isl_export int isl_set_is_empty(__isl_keep isl_set *set); @@ -455,13 +449,8 @@ __isl_give isl_set *isl_set_coalesce(__isl_take isl_set *set); int isl_set_plain_cmp(__isl_keep isl_set *set1, __isl_keep isl_set *set2); int isl_set_plain_is_equal(__isl_keep isl_set *set1, __isl_keep isl_set *set2); -ISL_DEPRECATED -int isl_set_fast_is_equal(__isl_keep isl_set *set1, __isl_keep isl_set *set2); int isl_set_plain_is_disjoint(__isl_keep isl_set *set1, __isl_keep isl_set *set2); -ISL_DEPRECATED -int isl_set_fast_is_disjoint(__isl_keep isl_set *set1, - __isl_keep isl_set *set2); uint32_t isl_set_get_hash(struct isl_set *set); diff --git a/polly/lib/External/isl/isl_hide_deprecated.h b/polly/lib/External/isl/isl_hide_deprecated.h index 006e796f88f..344a368600d 100644 --- a/polly/lib/External/isl/isl_hide_deprecated.h +++ b/polly/lib/External/isl/isl_hide_deprecated.h @@ -26,7 +26,6 @@ #define isl_basic_map_plain_is_fixed isl_gmp_basic_map_plain_is_fixed #define isl_map_fix isl_gmp_map_fix #define isl_map_plain_is_fixed isl_gmp_map_plain_is_fixed -#define isl_map_fast_is_fixed isl_gmp_map_fast_is_fixed #define isl_map_fixed_power isl_gmp_map_fixed_power #define isl_mat_get_element isl_gmp_mat_get_element #define isl_mat_set_element isl_gmp_mat_set_element diff --git a/polly/lib/External/isl/isl_map.c b/polly/lib/External/isl/isl_map.c index 6cfc1da8f6b..6d8c164d7b3 100644 --- a/polly/lib/External/isl/isl_map.c +++ b/polly/lib/External/isl/isl_map.c @@ -3171,7 +3171,7 @@ __isl_give isl_basic_set *isl_basic_set_insert_dims( return isl_basic_map_insert_dims(bset, type, pos, n); } -__isl_give isl_basic_map *isl_basic_map_add(__isl_take isl_basic_map *bmap, +__isl_give isl_basic_map *isl_basic_map_add_dims(__isl_take isl_basic_map *bmap, enum isl_dim_type type, unsigned n) { if (!bmap) @@ -3186,7 +3186,7 @@ __isl_give isl_basic_set *isl_basic_set_add_dims(__isl_take isl_basic_set *bset, if (!bset) return NULL; isl_assert(bset->ctx, type != isl_dim_in, goto error); - return (isl_basic_set *)isl_basic_map_add((isl_basic_map *)bset, type, n); + return isl_basic_map_add_dims(bset, type, n); error: isl_basic_set_free(bset); return NULL; @@ -7792,6 +7792,7 @@ __isl_give isl_set *isl_set_split_dims(__isl_take isl_set *set, enum isl_dim_type type, unsigned first, unsigned n) { int i; + unsigned offset; isl_basic_set *nonneg; isl_basic_set *neg; @@ -7802,11 +7803,11 @@ __isl_give isl_set *isl_set_split_dims(__isl_take isl_set *set, isl_assert(set->ctx, first + n <= isl_set_dim(set, type), goto error); + offset = pos(set->dim, type); for (i = 0; i < n; ++i) { nonneg = nonneg_halfspace(isl_set_get_space(set), - pos(set->dim, type) + first + i); - neg = neg_halfspace(isl_set_get_space(set), - pos(set->dim, type) + first + i); + offset + first + i); + neg = neg_halfspace(isl_set_get_space(set), offset + first + i); set = isl_set_intersect(set, isl_basic_set_union(nonneg, neg)); } @@ -7956,21 +7957,11 @@ int isl_map_plain_is_empty(__isl_keep isl_map *map) return map ? map->n == 0 : -1; } -int isl_map_fast_is_empty(__isl_keep isl_map *map) -{ - return isl_map_plain_is_empty(map); -} - int isl_set_plain_is_empty(struct isl_set *set) { return set ? set->n == 0 : -1; } -int isl_set_fast_is_empty(__isl_keep isl_set *set) -{ - return isl_set_plain_is_empty(set); -} - int isl_set_is_empty(struct isl_set *set) { return isl_map_is_empty((struct isl_map *)set); @@ -8081,11 +8072,6 @@ int isl_set_plain_is_universe(__isl_keep isl_set *set) return isl_map_plain_is_universe((isl_map *) set); } -int isl_set_fast_is_universe(__isl_keep isl_set *set) -{ - return isl_set_plain_is_universe(set); -} - int isl_basic_map_is_empty(struct isl_basic_map *bmap) { struct isl_basic_set *bset = NULL; @@ -8142,11 +8128,6 @@ int isl_basic_map_plain_is_empty(__isl_keep isl_basic_map *bmap) return ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY); } -int isl_basic_map_fast_is_empty(__isl_keep isl_basic_map *bmap) -{ - return isl_basic_map_plain_is_empty(bmap); -} - int isl_basic_set_plain_is_empty(__isl_keep isl_basic_set *bset) { if (!bset) @@ -8154,11 +8135,6 @@ int isl_basic_set_plain_is_empty(__isl_keep isl_basic_set *bset) return ISL_F_ISSET(bset, ISL_BASIC_SET_EMPTY); } -int isl_basic_set_fast_is_empty(__isl_keep isl_basic_set *bset) -{ - return isl_basic_set_plain_is_empty(bset); -} - int isl_basic_set_is_empty(struct isl_basic_set *bset) { return isl_basic_map_is_empty((struct isl_basic_map *)bset); @@ -8881,12 +8857,6 @@ int isl_set_plain_is_fixed(__isl_keep isl_set *set, return isl_map_plain_is_fixed(set, type, pos, val); } -int isl_map_fast_is_fixed(__isl_keep isl_map *map, - enum isl_dim_type type, unsigned pos, isl_int *val) -{ - return isl_map_plain_is_fixed(map, type, pos, val); -} - /* Check if dimension dim has fixed value and if so and if val is not NULL, * then return this fixed value in *val. */ @@ -8906,12 +8876,6 @@ int isl_set_plain_dim_is_fixed(__isl_keep isl_set *set, return isl_set_plain_has_fixed_var(set, isl_set_n_param(set) + dim, val); } -int isl_set_fast_dim_is_fixed(__isl_keep isl_set *set, - unsigned dim, isl_int *val) -{ - return isl_set_plain_dim_is_fixed(set, dim, val); -} - /* Check if input variable in has fixed value and if so and if val is not NULL, * then return this fixed value in *val. */ @@ -9140,6 +9104,8 @@ int isl_set_plain_cmp(__isl_keep isl_set *set1, __isl_keep isl_set *set2) int isl_basic_map_plain_is_equal(__isl_keep isl_basic_map *bmap1, __isl_keep isl_basic_map *bmap2) { + if (!bmap1 || !bmap2) + return -1; return isl_basic_map_plain_cmp(bmap1, bmap2) == 0; } @@ -9287,22 +9253,12 @@ error: return -1; } -int isl_map_fast_is_equal(__isl_keep isl_map *map1, __isl_keep isl_map *map2) -{ - return isl_map_plain_is_equal(map1, map2); -} - int isl_set_plain_is_equal(__isl_keep isl_set *set1, __isl_keep isl_set *set2) { return isl_map_plain_is_equal((struct isl_map *)set1, (struct isl_map *)set2); } -int isl_set_fast_is_equal(__isl_keep isl_set *set1, __isl_keep isl_set *set2) -{ - return isl_set_plain_is_equal(set1, set2); -} - /* Return an interval that ranges from min to max (inclusive) */ struct isl_basic_set *isl_basic_set_interval(struct isl_ctx *ctx, diff --git a/polly/lib/External/isl/isl_map_simplify.c b/polly/lib/External/isl/isl_map_simplify.c index 8ad4304fe8d..fa915ca898b 100644 --- a/polly/lib/External/isl/isl_map_simplify.c +++ b/polly/lib/External/isl/isl_map_simplify.c @@ -2761,11 +2761,6 @@ int isl_set_is_disjoint(__isl_keep isl_set *set1, __isl_keep isl_set *set2) return isl_map_is_disjoint(set1, set2); } -int isl_set_fast_is_disjoint(__isl_keep isl_set *set1, __isl_keep isl_set *set2) -{ - return isl_set_plain_is_disjoint(set1, set2); -} - /* Check if we can combine a given div with lower bound l and upper * bound u with some other div and if so return that other div. * Otherwise return -1. diff --git a/polly/lib/External/isl/isl_scheduler.c b/polly/lib/External/isl/isl_scheduler.c index 856c9851fcd..863e4502267 100644 --- a/polly/lib/External/isl/isl_scheduler.c +++ b/polly/lib/External/isl/isl_scheduler.c @@ -2794,43 +2794,6 @@ static __isl_give isl_union_set_list *extract_split(isl_ctx *ctx, return filters; } -/* Topologically sort statements mapped to the same schedule iteration - * and add insert a sequence node in front of "node" - * corresponding to this order. - */ -static __isl_give isl_schedule_node *sort_statements( - __isl_take isl_schedule_node *node, struct isl_sched_graph *graph) -{ - isl_ctx *ctx; - isl_union_set_list *filters; - - if (!node) - return NULL; - - ctx = isl_schedule_node_get_ctx(node); - if (graph->n < 1) - isl_die(ctx, isl_error_internal, - "graph should have at least one node", - return isl_schedule_node_free(node)); - - if (graph->n == 1) - return node; - - if (update_edges(ctx, graph) < 0) - return isl_schedule_node_free(node); - - if (graph->n_edge == 0) - return node; - - if (detect_sccs(ctx, graph) < 0) - return isl_schedule_node_free(node); - - filters = extract_sccs(ctx, graph); - node = isl_schedule_node_insert_sequence(node, filters); - - return node; -} - /* Copy nodes that satisfy node_pred from the src dependence graph * to the dst dependence graph. */ @@ -3785,6 +3748,52 @@ static __isl_give isl_schedule_node *carry_dependences( return split_scaled(node, graph); } +/* Topologically sort statements mapped to the same schedule iteration + * and add insert a sequence node in front of "node" + * corresponding to this order. + * + * If it turns out to be impossible to sort the statements apart, + * because different dependences impose different orderings + * on the statements, then we extend the schedule such that + * it carries at least one more dependence. + */ +static __isl_give isl_schedule_node *sort_statements( + __isl_take isl_schedule_node *node, struct isl_sched_graph *graph) +{ + isl_ctx *ctx; + isl_union_set_list *filters; + + if (!node) + return NULL; + + ctx = isl_schedule_node_get_ctx(node); + if (graph->n < 1) + isl_die(ctx, isl_error_internal, + "graph should have at least one node", + return isl_schedule_node_free(node)); + + if (graph->n == 1) + return node; + + if (update_edges(ctx, graph) < 0) + return isl_schedule_node_free(node); + + if (graph->n_edge == 0) + return node; + + if (detect_sccs(ctx, graph) < 0) + return isl_schedule_node_free(node); + + next_band(graph); + if (graph->scc < graph->n) + return carry_dependences(node, graph); + + filters = extract_sccs(ctx, graph); + node = isl_schedule_node_insert_sequence(node, filters); + + return node; +} + /* Are there any (non-empty) (conditional) validity edges in the graph? */ static int has_validity_edges(struct isl_sched_graph *graph) @@ -4082,6 +4091,7 @@ static __isl_give isl_schedule_node *compute_schedule_wcc( int use_coincidence; int force_coincidence = 0; int check_conditional; + int insert; isl_ctx *ctx; if (!node) @@ -4152,12 +4162,13 @@ static __isl_give isl_schedule_node *compute_schedule_wcc( use_coincidence = has_coincidence; } - if (graph->n_total_row > graph->band_start) { + insert = graph->n_total_row > graph->band_start; + if (insert) { node = insert_current_band(node, graph, 1); node = isl_schedule_node_child(node, 0); } node = sort_statements(node, graph); - if (graph->n_total_row > graph->band_start) + if (insert) node = isl_schedule_node_parent(node); return node; diff --git a/polly/lib/External/isl/isl_tab_pip.c b/polly/lib/External/isl/isl_tab_pip.c index 63603e5e0a8..84e85ffa5d3 100644 --- a/polly/lib/External/isl/isl_tab_pip.c +++ b/polly/lib/External/isl/isl_tab_pip.c @@ -4619,7 +4619,7 @@ static union isl_lex_res basic_map_partial_lexopt_symm( if (isl_basic_map_drop_inequality(bmap, list[i]) < 0) goto error; - bmap = isl_basic_map_add(bmap, isl_dim_in, 1); + bmap = isl_basic_map_add_dims(bmap, isl_dim_in, 1); bmap = isl_basic_map_extend_constraints(bmap, 0, 1); k = isl_basic_map_alloc_inequality(bmap); if (k < 0) diff --git a/polly/lib/External/isl/isl_test.c b/polly/lib/External/isl/isl_test.c index a5dab947e48..05b953634d8 100644 --- a/polly/lib/External/isl/isl_test.c +++ b/polly/lib/External/isl/isl_test.c @@ -3302,6 +3302,43 @@ static int test_conditional_schedule_constraints(isl_ctx *ctx) return 0; } +/* Check that the schedule computed for the given instance set and + * dependence relation strongly satisfies the dependences. + * In particular, check that no instance is scheduled before + * or together with an instance on which it depends. + * Earlier versions of isl would produce a schedule that + * only weakly satisfies the dependences. + */ +static int test_strongly_satisfying_schedule(isl_ctx *ctx) +{ + const char *domain, *dep; + isl_union_map *D, *schedule; + isl_map *map, *ge; + int empty; + + domain = "{ B[i0, i1] : 0 <= i0 <= 1 and 0 <= i1 <= 11; " + "A[i0] : 0 <= i0 <= 1 }"; + dep = "{ B[i0, i1] -> B[i0, 1 + i1] : 0 <= i0 <= 1 and 0 <= i1 <= 10; " + "B[0, 11] -> A[1]; A[i0] -> B[i0, 0] : 0 <= i0 <= 1 }"; + schedule = compute_schedule(ctx, domain, dep, dep); + D = isl_union_map_read_from_str(ctx, dep); + D = isl_union_map_apply_domain(D, isl_union_map_copy(schedule)); + D = isl_union_map_apply_range(D, schedule); + map = isl_map_from_union_map(D); + ge = isl_map_lex_ge(isl_space_domain(isl_map_get_space(map))); + map = isl_map_intersect(map, ge); + empty = isl_map_is_empty(map); + isl_map_free(map); + + if (empty < 0) + return -1; + if (!empty) + isl_die(ctx, isl_error_unknown, + "dependences not strongly satisfied", return -1); + + return 0; +} + int test_schedule(isl_ctx *ctx) { const char *D, *W, *R, *V, *P, *S; @@ -3594,6 +3631,9 @@ int test_schedule(isl_ctx *ctx) if (test_conditional_schedule_constraints(ctx) < 0) return -1; + if (test_strongly_satisfying_schedule(ctx) < 0) + return -1; + return 0; } |
