From 0bc931b344105309330bf1467fce18fef246d682 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Sat, 26 Nov 2011 15:52:07 +0100 Subject: [PATCH] scheduler: add an option to configure the level of fusing We currently only support maximal (the old behavior) and minimal fusion. Signed-off-by: Sven Verdoolaege --- include/isl/schedule.h | 5 +++++ isl_options.c | 14 +++++++++++++ isl_options_private.h | 1 + isl_schedule.c | 53 ++++++++++++++++++++++++++++++++++++++++++++------ 4 files changed, 67 insertions(+), 6 deletions(-) diff --git a/include/isl/schedule.h b/include/isl/schedule.h index 3770b7a..05f9f2a 100644 --- a/include/isl/schedule.h +++ b/include/isl/schedule.h @@ -24,6 +24,11 @@ int isl_options_get_schedule_outer_zero_distance(isl_ctx *ctx); int isl_options_set_schedule_split_parallel(isl_ctx *ctx, int val); int isl_options_get_schedule_split_parallel(isl_ctx *ctx); +#define ISL_SCHEDULE_FUSE_MAX 0 +#define ISL_SCHEDULE_FUSE_MIN 1 +int isl_options_set_schedule_fuse(isl_ctx *ctx, int val); +int isl_options_get_schedule_fuse(isl_ctx *ctx); + __isl_give isl_schedule *isl_union_set_compute_schedule( __isl_take isl_union_set *domain, __isl_take isl_union_map *validity, diff --git a/isl_options.c b/isl_options.c index ffb5b86..fe6a696 100644 --- a/isl_options.c +++ b/isl_options.c @@ -13,6 +13,7 @@ #include #include +#include #include struct isl_arg_choice isl_lp_solver_choice[] = { @@ -94,6 +95,12 @@ static struct isl_arg_choice convex[] = { {0} }; +static struct isl_arg_choice fuse[] = { + {"max", ISL_SCHEDULE_FUSE_MAX}, + {"min", ISL_SCHEDULE_FUSE_MIN}, + {0} +}; + static void print_version(void) { printf("%s", isl_version()); @@ -149,6 +156,8 @@ ISL_ARG_BOOL(struct isl_options, schedule_split_parallel, 0, ISL_ARG_CHOICE(struct isl_options, schedule_algorithm, 0, "schedule-algorithm", isl_schedule_algorithm_choice, ISL_SCHEDULE_ALGORITHM_ISL, "scheduling algorithm to use") +ISL_ARG_CHOICE(struct isl_options, schedule_fuse, 0, "schedule-fuse", fuse, + ISL_SCHEDULE_FUSE_MAX, "level of fusion during scheduling") ISL_ARG_VERSION(print_version) ISL_ARGS_END @@ -193,3 +202,8 @@ ISL_CTX_SET_CHOICE_DEF(isl_options, struct isl_options, isl_options_args, schedule_algorithm) ISL_CTX_GET_CHOICE_DEF(isl_options, struct isl_options, isl_options_args, schedule_algorithm) + +ISL_CTX_SET_CHOICE_DEF(isl_options, struct isl_options, isl_options_args, + schedule_fuse) +ISL_CTX_GET_CHOICE_DEF(isl_options, struct isl_options, isl_options_args, + schedule_fuse) diff --git a/isl_options_private.h b/isl_options_private.h index 5169096..1d9aba9 100644 --- a/isl_options_private.h +++ b/isl_options_private.h @@ -51,6 +51,7 @@ struct isl_options { int schedule_maximize_band_depth; int schedule_split_parallel; unsigned schedule_algorithm; + int schedule_fuse; }; #endif diff --git a/isl_schedule.c b/isl_schedule.c index 65573f5..4b5c1f2 100644 --- a/isl_schedule.c +++ b/isl_schedule.c @@ -1794,9 +1794,9 @@ static int node_scc_at_least(struct isl_sched_node *node, int scc) return node->scc >= scc; } -static int edge_src_scc_exactly(struct isl_sched_edge *edge, int scc) +static int edge_scc_exactly(struct isl_sched_edge *edge, int scc) { - return edge->src->scc == scc; + return edge->src->scc == scc && edge->dst->scc == scc; } static int edge_dst_scc_at_most(struct isl_sched_edge *edge, int scc) @@ -2446,8 +2446,37 @@ static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph) return sort_statements(ctx, graph); } +/* Add a row to the schedules that separates the SCCs and move + * to the next band. + */ +static int split_on_scc(struct isl_sched_graph *graph) +{ + int i; + + for (i = 0; i < graph->n; ++i) { + struct isl_sched_node *node = &graph->node[i]; + int row = isl_mat_rows(node->sched); + + isl_map_free(node->sched_map); + node->sched_map = NULL; + node->sched = isl_mat_add_zero_rows(node->sched, 1); + node->sched = isl_mat_set_element_si(node->sched, row, 0, + node->scc); + if (!node->sched) + return -1; + node->band[graph->n_total_row] = graph->n_band; + } + + graph->n_total_row++; + next_band(graph); + + return 0; +} + /* Compute a schedule for each component (identified by node->scc) * of the dependence graph separately and then combine the results. + * Depending on the setting of schedule_fuse, a component may be + * either weakly or strongly connected. * * The band_id is adjusted such that each component has a separate id. * Note that the band_id may have already been set to a value different @@ -2461,6 +2490,9 @@ static int compute_component_schedule(isl_ctx *ctx, int n_total_row, orig_total_row; int n_band, orig_band; + if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN) + split_on_scc(graph); + n_total_row = 0; orig_total_row = graph->n_total_row; n_band = 0; @@ -2474,12 +2506,13 @@ static int compute_component_schedule(isl_ctx *ctx, n++; n_edge = 0; for (i = 0; i < graph->n_edge; ++i) - if (graph->edge[i].src->scc == wcc) + if (graph->edge[i].src->scc == wcc && + graph->edge[i].dst->scc == wcc) n_edge++; if (compute_sub_schedule(ctx, graph, n, n_edge, &node_scc_exactly, - &edge_src_scc_exactly, wcc, 1) < 0) + &edge_scc_exactly, wcc, 1) < 0) return -1; if (graph->n_total_row > n_total_row) n_total_row = graph->n_total_row; @@ -2498,11 +2531,19 @@ static int compute_component_schedule(isl_ctx *ctx, /* Compute a schedule for the given dependence graph. * We first check if the graph is connected (through validity dependences) * and, if not, compute a schedule for each component separately. + * If schedule_fuse is set to minimal fusion, then we check for strongly + * connected components instead and compute a separate schedule for + * each such strongly connected component. */ static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph) { - if (detect_wccs(graph) < 0) - return -1; + if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN) { + if (detect_sccs(graph) < 0) + return -1; + } else { + if (detect_wccs(graph) < 0) + return -1; + } if (graph->scc > 1) return compute_component_schedule(ctx, graph); -- 2.7.4