From 6b21b75cf239674ca6ab0943d9cce051c778d630 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Sun, 4 Nov 2012 16:30:54 +0100 Subject: [PATCH] isl_union_set_compute_schedule: ensure carry_dependences makes progress If solve_lp is unable to find a solution, then compute_schedule_wcc calls carry_dependences to carry as many dependences as possible. However, the reason that solve_lp was unable to find a solution may be due to proximity dependences. In particular, if there are an infinite number of dependences with the same starting or ending itereration, then the way proximity dependences are currently handled may force some of the schedule coefficients to be zero based solely on those proximity dependences. carry_dependences may then fail to carry any (validity) dependences simply because there are no validity dependences. More generally, it may produce a non-trivial solution on only some of the nodes. This may result in a number of schedule rows (infinite in the worst case) that is larger than the maximum computed in compute_max_row, leading to out-of-bounds accesses. We therefore check that the schedule row computed by carry_dependences is non-trivial on all the nodes where it should be non-trivial. If not, we try again on each dependence graph component separately or fail if there is only one component. Note that this commit does not fix the problem that the presence of proximity dependences may eliminate some valid solutions, but it should solve the out-of-bounds accesses. Reported-by: Tobias Grosser Signed-off-by: Sven Verdoolaege --- isl_schedule.c | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ isl_test.c | 46 +++++++++++++++++++++++++++++++++++++------ 2 files changed, 101 insertions(+), 6 deletions(-) diff --git a/isl_schedule.c b/isl_schedule.c index f2c3c892..954110e7 100644 --- a/isl_schedule.c +++ b/isl_schedule.c @@ -2485,8 +2485,61 @@ error: return -1; } +static int compute_component_schedule(isl_ctx *ctx, + struct isl_sched_graph *graph); + +/* Is the schedule row "sol" trivial on node "node"? + * That is, is the solution zero on the dimensions orthogonal to + * the previously found solutions? + * Each coefficient is represented as the difference between + * two non-negative values in "sol". The coefficient is then + * zero if those two values are equal to each other. + */ +static int is_trivial(struct isl_sched_node *node, __isl_keep isl_vec *sol) +{ + int i; + int pos; + int len; + + pos = 1 + node->start + 1 + 2 * (node->nparam + node->rank); + len = 2 * (node->nvar - node->rank); + + if (len == 0) + return 0; + + for (i = 0; i < len; i += 2) + if (isl_int_ne(sol->el[pos + i], sol->el[pos + i + 1])) + return 0; + + return 1; +} + +/* Is the schedule row "sol" trivial on any node where it should + * not be trivial? + */ +static int is_any_trivial(struct isl_sched_graph *graph, + __isl_keep isl_vec *sol) +{ + int i; + + for (i = 0; i < graph->n; ++i) { + struct isl_sched_node *node = &graph->node[i]; + + if (!needs_row(graph, node)) + continue; + if (is_trivial(node, sol)) + return 1; + } + + return 0; +} + /* Construct a schedule row for each node such that as many dependences * as possible are carried and then continue with the next band. + * + * If the computed schedule row turns out to be trivial on one or + * more nodes where it should not be trivial, then we throw it away + * and try again on each component separately. */ static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph) { @@ -2519,6 +2572,14 @@ static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph) "unable to carry dependences", return -1); } + if (is_any_trivial(graph, sol)) { + isl_vec_free(sol); + if (graph->scc > 1) + return compute_component_schedule(ctx, graph); + isl_die(ctx, isl_error_unknown, + "unable to construct non-trivial solution", return -1); + } + if (update_schedule(graph, sol, 0, 0) < 0) return -1; diff --git a/isl_test.c b/isl_test.c index fa018e3a..09c88f9f 100644 --- a/isl_test.c +++ b/isl_test.c @@ -2278,23 +2278,48 @@ int test_one_schedule(isl_ctx *ctx, const char *d, const char *w, return 0; } -int test_special_schedule(isl_ctx *ctx, const char *domain, - const char *validity, const char *proximity, const char *expected_sched) +static __isl_give isl_union_map *compute_schedule(isl_ctx *ctx, + const char *domain, const char *validity, const char *proximity) { isl_union_set *dom; isl_union_map *dep; isl_union_map *prox; - isl_union_map *sched1, *sched2; isl_schedule *schedule; - int equal; + isl_union_map *sched; dom = isl_union_set_read_from_str(ctx, domain); dep = isl_union_map_read_from_str(ctx, validity); prox = isl_union_map_read_from_str(ctx, proximity); schedule = isl_union_set_compute_schedule(dom, dep, prox); - sched1 = isl_schedule_get_map(schedule); + sched = isl_schedule_get_map(schedule); isl_schedule_free(schedule); + return sched; +} + +/* Check that a schedule can be constructed on the given domain + * with the given validity and proximity constraints. + */ +static int test_has_schedule(isl_ctx *ctx, const char *domain, + const char *validity, const char *proximity) +{ + isl_union_map *sched; + + sched = compute_schedule(ctx, domain, validity, proximity); + if (!sched) + return -1; + + isl_union_map_free(sched); + return 0; +} + +int test_special_schedule(isl_ctx *ctx, const char *domain, + const char *validity, const char *proximity, const char *expected_sched) +{ + isl_union_map *sched1, *sched2; + int equal; + + sched1 = compute_schedule(ctx, domain, validity, proximity); sched2 = isl_union_map_read_from_str(ctx, expected_sched); equal = isl_union_map_is_equal(sched1, sched2); @@ -2561,7 +2586,16 @@ int test_schedule(isl_ctx *ctx) if (test_special_schedule(ctx, D, V, P, S) < 0) return -1; ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_ISL; - return test_special_schedule(ctx, D, V, P, S); + if (test_special_schedule(ctx, D, V, P, S) < 0) + return -1; + + D = "{ A[a]; B[] }"; + V = "{}"; + P = "{ A[a] -> B[] }"; + if (test_has_schedule(ctx, D, V, P) < 0) + return -1; + + return 0; } int test_plain_injective(isl_ctx *ctx, const char *str, int injective) -- 2.11.4.GIT