From cc19c5c1b31aa1263d7aef44d8bdf8d996920c21 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Thu, 20 Jul 2017 17:51:53 +0200 Subject: [PATCH] allow consecutivity constraints to be applied within a tile By default, consecutivity constraints are applied globally. In some cases, it may be preferable to focus on proximity at the global level and only take into account consecutivity within tiled bands. Add support for this second case. Signed-off-by: Sven Verdoolaege --- cpu.c | 80 +++++++++++++++++++++++++++++++++++++++++++++++++++++----- ppcg_options.c | 12 +++++++++ ppcg_options.h | 5 ++++ 3 files changed, 91 insertions(+), 6 deletions(-) diff --git a/cpu.c b/cpu.c index b83e908..e26220c 100644 --- a/cpu.c +++ b/cpu.c @@ -575,16 +575,68 @@ static __isl_give isl_schedule_node *tile(__isl_take isl_schedule_node *node, return node; } +/* Is "node" not a tilable band node? + */ +static isl_bool not_band(__isl_keep isl_schedule_node *node, void *user) +{ + return isl_bool_not(is_tilable_band(node)); +} + +/* Is the subtree rooted at "node" free of tilable band nodes? + */ +static isl_bool free_of_tilable_band_nodes(__isl_keep isl_schedule_node *node) +{ + return isl_schedule_node_every_descendant(node, ¬_band, NULL); +} + +/* Given a pointer "node" to a tiled band node, does the point band + * need to be rescheduled? + * + * In particular, are there any arrays marked consecutive, + * should the consecutivity constraints be applied within + * the innermost tile and is this the innermost tilable band? + */ +static isl_bool point_band_needs_rescheduling(struct ppcg_scop *scop, + __isl_keep isl_schedule_node *node) +{ + isl_bool empty, innermost; + + if (scop->options->consecutivity_level != PPCG_CONSECUTIVITY_INTRA_TILE) + return isl_bool_false; + + empty = ppcg_consecutive_is_empty(scop->consecutive); + if (empty < 0) + return isl_bool_error; + if (empty) + return isl_bool_false; + + node = isl_schedule_node_copy(node); + node = isl_schedule_node_child(node, 0); + node = isl_schedule_node_child(node, 0); + innermost = free_of_tilable_band_nodes(node); + isl_schedule_node_free(node); + + return innermost; +} + +static __isl_give isl_schedule_constraints *construct_cpu_schedule_constraints( + struct ppcg_scop *ps); + /* Tile "node", if it is a band node with at least 2 members. * The tile sizes are set from the "tile_size" option. + * + * If the tile band needs to be rescheduled for consecutivity purposes, + * then reconstruct the schedule constraints, add consecutivity constraints + * and reschedule the point band. */ static __isl_give isl_schedule_node *tile_band( __isl_take isl_schedule_node *node, void *user) { struct ppcg_scop *scop = user; - isl_bool tilable; + isl_bool tilable, reschedule; isl_space *space; isl_multi_val *sizes; + isl_schedule_constraints *sc; tilable = is_tilable_band(node); if (tilable < 0) @@ -595,7 +647,21 @@ static __isl_give isl_schedule_node *tile_band( space = isl_schedule_node_band_get_space(node); sizes = ppcg_multi_val_from_int(space, scop->options->tile_size); - return tile(node, sizes); + node = tile(node, sizes); + + reschedule = point_band_needs_rescheduling(scop, node); + if (reschedule < 0) + return isl_schedule_node_free(node); + if (!reschedule) + return node; + + node = isl_schedule_node_child(node, 0); + sc = construct_cpu_schedule_constraints(scop); + sc = ppcg_add_consecutivity_constraints(sc, scop); + node = isl_schedule_node_schedule(node, sc); + node = isl_schedule_node_parent(node); + + return node; } /* Construct schedule constraints from the dependences in ps @@ -666,14 +732,16 @@ static __isl_give isl_schedule_constraints *construct_cpu_schedule_constraints( /* Compute a schedule on the domain of "sc" that respects the schedule * constraints in "sc", taking into account the arrays that are - * marked consecutive in "scop". + * marked consecutive in "scop" if consecutivity constraints + * should be considered at the global level. * Do not perform any grouping of statements because the grouping * process does not take into account the consecutivity constraints. */ -__isl_give isl_schedule *ppcg_compute_consecutive_schedule( +__isl_give isl_schedule *ppcg_compute_global_consecutive_schedule( __isl_take isl_schedule_constraints *sc, struct ppcg_scop *scop) { - sc = ppcg_add_consecutivity_constraints(sc, scop); + if (scop->options->consecutivity_level == PPCG_CONSECUTIVITY_GLOBAL) + sc = ppcg_add_consecutivity_constraints(sc, scop); return ppcg_compute_non_grouping_schedule(sc, scop->options); } @@ -705,7 +773,7 @@ static __isl_give isl_schedule *compute_cpu_schedule(struct ppcg_scop *ps) sc = construct_cpu_schedule_constraints(ps); if (!empty) - schedule = ppcg_compute_consecutive_schedule(sc, ps); + schedule = ppcg_compute_global_consecutive_schedule(sc, ps); else schedule = ppcg_compute_schedule(sc, ps->schedule, ps->options); diff --git a/ppcg_options.c b/ppcg_options.c index c2fcbaa..2fa2d2c 100644 --- a/ppcg_options.c +++ b/ppcg_options.c @@ -17,6 +17,15 @@ static struct isl_arg_choice target[] = { {0} }; +/* The level at which consecutivity constraints should be applied, + * either globally or within the innermost tiles. + */ +static struct isl_arg_choice consecutivity[] = { + { "global", PPCG_CONSECUTIVITY_GLOBAL }, + { "intra-tile", PPCG_CONSECUTIVITY_INTRA_TILE }, + { 0 } +}; + /* Set defaults that depend on the target. * In particular, set --schedule-outer-coincidence iff target is a GPU. */ @@ -122,6 +131,9 @@ ISL_ARG_BOOL(struct ppcg_options, live_range_reordering, 0, "to be reordered") ISL_ARG_STR(struct ppcg_options, consecutive_arrays, 0, "consecutive-arrays", "id-list", NULL, "list of consecutive array identifiers") +ISL_ARG_CHOICE(struct ppcg_options, consecutivity_level, 0, + "consecutivity-level", consecutivity, PPCG_CONSECUTIVITY_GLOBAL, + "the level at which consecutivity constraints should be applied") ISL_ARG_BOOL(struct ppcg_options, hybrid, 0, "hybrid", 0, "apply hybrid tiling whenever a suitable input pattern is found " "(GPU targets)") diff --git a/ppcg_options.h b/ppcg_options.h index 987ec1d..b5e63d2 100644 --- a/ppcg_options.h +++ b/ppcg_options.h @@ -62,6 +62,8 @@ struct ppcg_options { /* List of consecutive array identifiers, as specified by the user */ char *consecutive_arrays; + /* The level at which consecutivity constraints should be applied */ + int consecutivity_level; /* Allow hybrid tiling whenever a suitable input pattern is found. */ int hybrid; @@ -100,4 +102,7 @@ ISL_ARG_DECL(ppcg_options, struct ppcg_options, ppcg_options_args) void ppcg_options_set_target_defaults(struct ppcg_options *options); +#define PPCG_CONSECUTIVITY_GLOBAL 0 +#define PPCG_CONSECUTIVITY_INTRA_TILE 1 + #endif -- 2.11.4.GIT