From 83fbaf0c10ee72fa18b600abdaa385420dca2466 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Wed, 26 Apr 2017 11:39:46 +0200 Subject: [PATCH] scheduler: fix checking conditional validity constraints on compressed domains The original implementation would take a schedule on the compressed domain and use it as if it were a schedule on the original domain, possibly resulting in a missed detection of violated conditional validity constraints. This fix is based on code inspection. It is not clear if the bug would ever trigger in practice. The new test cases was specifically constructed by hand to tickle the bug and only fails for the whole-component scheduler. In particular, with conditions { B[1, i] -> A[0, i + 1] } and conditioned validity constraints { A[0, i] -> B[1, i - 1] } on domain { A[0, i] : 0 <= i <= 10; B[1, i] : 0 <= i <= 10 }, the whole-component scheduler would produce domain: "{ B[1, i] : 0 <= i <= 10; A[0, i] : 0 <= i <= 10 }" child: schedule: "[{ B[i0, i] -> [(i)]; A[i0, i] -> [(i)] }]" permutable: 1 coincident: [ 1 ] child: sequence: - filter: "{ A[i0, i] }" - filter: "{ B[i0, i] }" The single band violates the conditional validity constraints since the conditions have distance 1 and the conditioned validity constraints have distance -1. With the fix, it produces domain: "{ B[1, i] : 0 <= i <= 10; A[0, i] : 0 <= i <= 10 }" child: schedule: "[{ B[i0, i] -> [(1 + i)]; A[i0, i] -> [(i)] }]" permutable: 1 coincident: [ 1 ] child: sequence: - filter: "{ A[i0, i] }" - filter: "{ B[i0, i] }" Here, both distances are zero. Signed-off-by: Sven Verdoolaege --- isl_scheduler.c | 8 +++----- isl_test.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 54 insertions(+), 5 deletions(-) diff --git a/isl_scheduler.c b/isl_scheduler.c index 0f40c5e0..16497fda 100644 --- a/isl_scheduler.c +++ b/isl_scheduler.c @@ -4334,14 +4334,12 @@ static int has_any_coincidence(struct isl_sched_graph *graph) */ static __isl_give isl_map *final_row(struct isl_sched_node *node) { - isl_local_space *ls; - isl_aff *aff; + isl_multi_aff *ma; int row; row = isl_mat_rows(node->sched) - 1; - ls = isl_local_space_from_space(isl_space_copy(node->space)); - aff = extract_schedule_row(ls, node, row); - return isl_map_from_aff(aff); + ma = node_extract_partial_schedule_multi_aff(node, row, 1); + return isl_map_from_multi_aff(ma); } /* Is the conditional validity dependence in the edge with index "edge_index" diff --git a/isl_test.c b/isl_test.c index 06a91c68..01f3e6d2 100644 --- a/isl_test.c +++ b/isl_test.c @@ -3681,6 +3681,55 @@ static int test_special_conditional_schedule_constraints(isl_ctx *ctx) return 0; } +/* Check that the test for violated conditional validity constraints + * is not confused by domain compression. + * In particular, earlier versions of isl would apply + * a schedule on the compressed domains to the original domains, + * resulting in a failure to detect that the default schedule + * violates the conditional validity constraints. + */ +static int test_special_conditional_schedule_constraints_2(isl_ctx *ctx) +{ + const char *str; + isl_bool empty; + isl_union_set *domain; + isl_union_map *validity, *condition; + isl_schedule_constraints *sc; + isl_schedule *schedule; + isl_union_map *umap; + isl_map *map, *ge; + + str = "{ A[0, i] : 0 <= i <= 10; B[1, i] : 0 <= i <= 10 }"; + domain = isl_union_set_read_from_str(ctx, str); + sc = isl_schedule_constraints_on_domain(domain); + str = "{ B[1, i] -> A[0, i + 1] }"; + condition = isl_union_map_read_from_str(ctx, str); + str = "{ A[0, i] -> B[1, i - 1] }"; + validity = isl_union_map_read_from_str(ctx, str); + sc = isl_schedule_constraints_set_conditional_validity(sc, condition, + isl_union_map_copy(validity)); + schedule = isl_schedule_constraints_compute_schedule(sc); + umap = isl_schedule_get_map(schedule); + isl_schedule_free(schedule); + validity = isl_union_map_apply_domain(validity, + isl_union_map_copy(umap)); + validity = isl_union_map_apply_range(validity, umap); + map = isl_map_from_union_map(validity); + 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, + "conditional validity constraints not satisfied", + return -1); + + return 0; +} + /* Input for testing of schedule construction based on * conditional constraints. * @@ -3785,6 +3834,8 @@ static int test_conditional_schedule_constraints(isl_ctx *ctx) if (test_special_conditional_schedule_constraints(ctx) < 0) return -1; + if (test_special_conditional_schedule_constraints_2(ctx) < 0) + return -1; for (i = 0; i < ARRAY_SIZE(live_range_tests); ++i) { domain = isl_union_set_read_from_str(ctx, -- 2.11.4.GIT