From: Sven Verdoolaege Date: Wed, 21 Mar 2012 13:32:26 +0000 (+0100) Subject: introduce new schedule API X-Git-Tag: isl-0.13~115 X-Git-Url: https://repo.or.cz/w/isl.git/commitdiff_plain/74d4e1e7e51d9f8b530f3e3f6bd430c0dd60500b introduce new schedule API In particular, introduce an interface that computes schedules in terms of "schedule constraints" rather than in terms of "validity and proximity dependences". The use of "schedule constraints" allows us to more easily extend the interface to handle additional types of constraints. Signed-off-by: Sven Verdoolaege --- diff --git a/doc/user.pod b/doc/user.pod index 7cd5d793..e58a3989 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -5622,30 +5622,75 @@ whereas C is essentially equivalent to B -The following function can be used to compute a schedule -for a union of domains. + #include + __isl_give isl_schedule * + isl_schedule_constraints_compute_schedule( + __isl_take isl_schedule_constraints *sc); + void *isl_schedule_free(__isl_take isl_schedule *sched); + +The function C can be +used to compute a schedule that satisfy the given schedule constraints. +These schedule constraints include the iteration domain for which +a schedule should be computed and dependences between pairs of +iterations. In particular, these dependences include +I dependences and I dependences. By default, the algorithm used to construct the schedule is similar to that of C. Alternatively, Feautrier's multi-dimensional scheduling algorithm can be selected. -The generated schedule respects all C dependences. +The generated schedule respects all validity dependences. That is, all dependence distances over these dependences in the scheduled space are lexicographically positive. The default algorithm tries to minimize the dependence distances over -C dependences. +proximity dependences. Moreover, it tries to obtain sequences (bands) of schedule dimensions for groups of domains where the dependence distances have only non-negative values. -When using Feautrier's algorithm, the C dependence +When using Feautrier's algorithm, the proximity dependence distances are only minimized during the extension to a full-dimensional schedule. +An C object can be constructed +and manipulated using the following functions. + + #include + __isl_give isl_schedule_constraints * + isl_schedule_constraints_on_domain( + __isl_take isl_union_set *domain); + isl_ctx *isl_schedule_constraints_get_ctx( + __isl_keep isl_schedule_constraints *sc); + __isl_give isl_schedule_constraints * + isl_schedule_constraints_set_validity( + __isl_take isl_schedule_constraints *sc, + __isl_take isl_union_map *validity); + __isl_give isl_schedule_constraints * + isl_schedule_constraints_set_proximity( + __isl_take isl_schedule_constraints *sc, + __isl_take isl_union_map *proximity); + void *isl_schedule_constraints_free( + __isl_take isl_schedule_constraints *sc); + +The initial C object created by +C does not impose any constraints. +That is, it has an empty set of dependences. +The function C replaces the +validity dependences, mapping domain elements I to domain +elements that should be scheduled after I. +The function C replaces the +proximity dependences, mapping domain elements I to domain +elements that should be scheduled either before I +or as early as possible after I. + +The following function computes a schedule directly from +an iteration domain and validity and proximity dependences +and is implemented in terms of the functions described above. +The use of C is discouraged. + #include __isl_give isl_schedule *isl_union_set_compute_schedule( __isl_take isl_union_set *domain, __isl_take isl_union_map *validity, __isl_take isl_union_map *proximity); - void *isl_schedule_free(__isl_take isl_schedule *sched); A mapping from the domains to the scheduled space can be obtained from an C using the following function. diff --git a/include/isl/schedule.h b/include/isl/schedule.h index 385c6c4e..3c34a816 100644 --- a/include/isl/schedule.h +++ b/include/isl/schedule.h @@ -10,6 +10,8 @@ extern "C" { #endif +struct isl_schedule_constraints; +typedef struct isl_schedule_constraints isl_schedule_constraints; struct isl_schedule; typedef struct isl_schedule isl_schedule; @@ -36,6 +38,24 @@ int isl_options_get_schedule_separate_components(isl_ctx *ctx); int isl_options_set_schedule_fuse(isl_ctx *ctx, int val); int isl_options_get_schedule_fuse(isl_ctx *ctx); +__isl_give isl_schedule_constraints *isl_schedule_constraints_on_domain( + __isl_take isl_union_set *domain); +__isl_give isl_schedule_constraints *isl_schedule_constraints_set_validity( + __isl_take isl_schedule_constraints *sc, + __isl_take isl_union_map *validity); +__isl_give isl_schedule_constraints *isl_schedule_constraints_set_proximity( + __isl_take isl_schedule_constraints *sc, + __isl_take isl_union_map *proximity); +void *isl_schedule_constraints_free(__isl_take isl_schedule_constraints *sc); + +isl_ctx *isl_schedule_constraints_get_ctx( + __isl_keep isl_schedule_constraints *sc); + +void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints *sc); + +__isl_give isl_schedule *isl_schedule_constraints_compute_schedule( + __isl_take isl_schedule_constraints *sc); + __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_schedule.c b/isl_schedule.c index 362596db..9f0a8ff0 100644 --- a/isl_schedule.c +++ b/isl_schedule.c @@ -36,6 +36,157 @@ * Parallelization and Locality Optimization in the Polyhedral Model". */ +/* Construct an isl_schedule_constraints object for computing a schedule + * on "domain". The initial object does not impose any constraints. + */ +__isl_give isl_schedule_constraints *isl_schedule_constraints_on_domain( + __isl_take isl_union_set *domain) +{ + isl_ctx *ctx; + isl_space *space; + isl_schedule_constraints *sc; + isl_union_map *empty; + enum isl_edge_type i; + + if (!domain) + return NULL; + + ctx = isl_union_set_get_ctx(domain); + sc = isl_calloc_type(ctx, struct isl_schedule_constraints); + if (!sc) + return isl_union_set_free(domain); + + space = isl_union_set_get_space(domain); + sc->domain = domain; + empty = isl_union_map_empty(space); + for (i = isl_edge_first; i <= isl_edge_last; ++i) { + sc->constraint[i] = isl_union_map_copy(empty); + if (!sc->constraint[i]) + sc->domain = isl_union_set_free(sc->domain); + } + isl_union_map_free(empty); + + if (!sc->domain) + return isl_schedule_constraints_free(sc); + + return sc; +} + +/* Replace the validity constraints of "sc" by "validity". + */ +__isl_give isl_schedule_constraints *isl_schedule_constraints_set_validity( + __isl_take isl_schedule_constraints *sc, + __isl_take isl_union_map *validity) +{ + if (!sc || !validity) + goto error; + + isl_union_map_free(sc->constraint[isl_edge_validity]); + sc->constraint[isl_edge_validity] = validity; + + return sc; +error: + isl_schedule_constraints_free(sc); + isl_union_map_free(validity); + return NULL; +} + +/* Replace the proximity constraints of "sc" by "proximity". + */ +__isl_give isl_schedule_constraints *isl_schedule_constraints_set_proximity( + __isl_take isl_schedule_constraints *sc, + __isl_take isl_union_map *proximity) +{ + if (!sc || !proximity) + goto error; + + isl_union_map_free(sc->constraint[isl_edge_proximity]); + sc->constraint[isl_edge_proximity] = proximity; + + return sc; +error: + isl_schedule_constraints_free(sc); + isl_union_map_free(proximity); + return NULL; +} + +void *isl_schedule_constraints_free(__isl_take isl_schedule_constraints *sc) +{ + enum isl_edge_type i; + + if (!sc) + return NULL; + + isl_union_set_free(sc->domain); + for (i = isl_edge_first; i <= isl_edge_last; ++i) + isl_union_map_free(sc->constraint[i]); + + free(sc); + + return NULL; +} + +isl_ctx *isl_schedule_constraints_get_ctx( + __isl_keep isl_schedule_constraints *sc) +{ + return sc ? isl_union_set_get_ctx(sc->domain) : NULL; +} + +void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints *sc) +{ + if (!sc) + return; + + fprintf(stderr, "domain: "); + isl_union_set_dump(sc->domain); + fprintf(stderr, "validity: "); + isl_union_map_dump(sc->constraint[isl_edge_validity]); + fprintf(stderr, "proximity: "); + isl_union_map_dump(sc->constraint[isl_edge_proximity]); +} + +/* Align the parameters of the fields of "sc". + */ +static __isl_give isl_schedule_constraints * +isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints *sc) +{ + isl_space *space; + enum isl_edge_type i; + + if (!sc) + return NULL; + + space = isl_union_set_get_space(sc->domain); + for (i = isl_edge_first; i <= isl_edge_last; ++i) + space = isl_space_align_params(space, + isl_union_map_get_space(sc->constraint[i])); + + for (i = isl_edge_first; i <= isl_edge_last; ++i) { + sc->constraint[i] = isl_union_map_align_params( + sc->constraint[i], isl_space_copy(space)); + if (!sc->constraint[i]) + space = isl_space_free(space); + } + sc->domain = isl_union_set_align_params(sc->domain, space); + if (!sc->domain) + return isl_schedule_constraints_free(sc); + + return sc; +} + +/* Return the total number of isl_maps in the constraints of "sc". + */ +static __isl_give int isl_schedule_constraints_n_map( + __isl_keep isl_schedule_constraints *sc) +{ + enum isl_edge_type i; + int n = 0; + + for (i = isl_edge_first; i <= isl_edge_last; ++i) + n += isl_union_map_n_map(sc->constraint[i]); + + return n; +} /* Internal information about a node that is used during the construction * of a schedule. @@ -120,13 +271,6 @@ struct isl_sched_edge { int end; }; -enum isl_edge_type { - isl_edge_validity = 0, - isl_edge_first = isl_edge_validity, - isl_edge_proximity, - isl_edge_last = isl_edge_proximity -}; - /* Internal information about the dependence graph used during * the construction of the schedule. * @@ -2929,83 +3073,92 @@ static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph) return compute_schedule_wcc(ctx, graph); } -/* Compute a schedule for the given union of domains that respects - * all the validity dependences. +/* Compute a schedule on sc->domain that respects the given schedule + * constraints. + * + * In particular, the schedule respects all the validity dependences. * If the default isl scheduling algorithm is used, it tries to minimize * the dependence distances over the proximity dependences. * If Feautrier's scheduling algorithm is used, the proximity dependence * distances are only minimized during the extension to a full-dimensional * schedule. */ -__isl_give isl_schedule *isl_union_set_compute_schedule( - __isl_take isl_union_set *domain, - __isl_take isl_union_map *validity, - __isl_take isl_union_map *proximity) +__isl_give isl_schedule *isl_schedule_constraints_compute_schedule( + __isl_take isl_schedule_constraints *sc) { - isl_ctx *ctx = isl_union_set_get_ctx(domain); - isl_space *dim; + isl_ctx *ctx = isl_schedule_constraints_get_ctx(sc); struct isl_sched_graph graph = { 0 }; isl_schedule *sched; struct isl_extract_edge_data data; + enum isl_edge_type i; - domain = isl_union_set_align_params(domain, - isl_union_map_get_space(validity)); - domain = isl_union_set_align_params(domain, - isl_union_map_get_space(proximity)); - dim = isl_union_set_get_space(domain); - validity = isl_union_map_align_params(validity, isl_space_copy(dim)); - proximity = isl_union_map_align_params(proximity, dim); - - if (!domain) - goto error; + sc = isl_schedule_constraints_align_params(sc); + if (!sc) + return NULL; - graph.n = isl_union_set_n_set(domain); + graph.n = isl_union_set_n_set(sc->domain); if (graph.n == 0) goto empty; if (graph_alloc(ctx, &graph, graph.n, - isl_union_map_n_map(validity) + isl_union_map_n_map(proximity)) < 0) + isl_schedule_constraints_n_map(sc)) < 0) goto error; - if (compute_max_row(&graph, domain) < 0) + if (compute_max_row(&graph, sc->domain) < 0) goto error; graph.root = 1; graph.n = 0; - if (isl_union_set_foreach_set(domain, &extract_node, &graph) < 0) + if (isl_union_set_foreach_set(sc->domain, &extract_node, &graph) < 0) goto error; if (graph_init_table(ctx, &graph) < 0) goto error; - graph.max_edge[isl_edge_validity] = isl_union_map_n_map(validity); - graph.max_edge[isl_edge_proximity] = isl_union_map_n_map(proximity); + for (i = isl_edge_first; i <= isl_edge_last; ++i) + graph.max_edge[i] = isl_union_map_n_map(sc->constraint[i]); if (graph_init_edge_tables(ctx, &graph) < 0) goto error; graph.n_edge = 0; data.graph = &graph; - data.type = isl_edge_validity; - if (isl_union_map_foreach_map(validity, &extract_edge, &data) < 0) - goto error; - data.type = isl_edge_proximity; - if (isl_union_map_foreach_map(proximity, &extract_edge, &data) < 0) - goto error; + for (i = isl_edge_first; i <= isl_edge_last; ++i) { + data.type = i; + if (isl_union_map_foreach_map(sc->constraint[i], + &extract_edge, &data) < 0) + goto error; + } if (compute_schedule(ctx, &graph) < 0) goto error; empty: - sched = extract_schedule(&graph, isl_union_set_get_space(domain)); + sched = extract_schedule(&graph, isl_union_set_get_space(sc->domain)); graph_free(ctx, &graph); - isl_union_set_free(domain); - isl_union_map_free(validity); - isl_union_map_free(proximity); + isl_schedule_constraints_free(sc); return sched; error: graph_free(ctx, &graph); - isl_union_set_free(domain); - isl_union_map_free(validity); - isl_union_map_free(proximity); + isl_schedule_constraints_free(sc); return NULL; } +/* Compute a schedule for the given union of domains that respects + * all the validity dependences and minimizes + * the dependence distances over the proximity dependences. + * + * This function is kept for backward compatibility. + */ +__isl_give isl_schedule *isl_union_set_compute_schedule( + __isl_take isl_union_set *domain, + __isl_take isl_union_map *validity, + __isl_take isl_union_map *proximity) +{ + isl_schedule_constraints *sc; + + sc = isl_schedule_constraints_on_domain(domain); + sc = isl_schedule_constraints_set_validity(sc, validity); + sc = isl_schedule_constraints_set_proximity(sc, proximity); + + return isl_schedule_constraints_compute_schedule(sc); +} + void *isl_schedule_free(__isl_take isl_schedule *sched) { int i; @@ -3409,7 +3562,7 @@ static int cmp_band(const void *a, const void *b, void *user) * This order should be a more "natural" order for the user, but otherwise * shouldn't have any effect. * If we would be constructing an isl_band forest directly in - * isl_union_set_compute_schedule then there wouldn't be any need + * isl_schedule_constraints_compute_schedule then there wouldn't be any need * for a reordering, since the children would be added to the list * in their natural order automatically. * diff --git a/isl_schedule_private.h b/isl_schedule_private.h index 58310718..d9477ca1 100644 --- a/isl_schedule_private.h +++ b/isl_schedule_private.h @@ -4,6 +4,27 @@ #include #include +enum isl_edge_type { + isl_edge_validity = 0, + isl_edge_first = isl_edge_validity, + isl_edge_proximity, + isl_edge_last = isl_edge_proximity +}; + +/* The constraints that need to be satisfied by a schedule on "domain". + * + * "validity" constraints map domain elements i to domain elements + * that should be scheduled after i. (Hard constraint) + * "proximity" constraints map domain elements i to domains elements + * that should be scheduled as early as possible after i (or before i). + * (Soft constraint) + */ +struct isl_schedule_constraints { + isl_union_set *domain; + + isl_union_map *constraint[isl_edge_last + 1]; +}; + /* The schedule for an individual domain, plus information about the bands * and scheduling dimensions. * In particular, we keep track of the number of bands and for each diff --git a/isl_test.c b/isl_test.c index f1a790dd..cc8bab0a 100644 --- a/isl_test.c +++ b/isl_test.c @@ -2428,6 +2428,7 @@ int test_one_schedule(isl_ctx *ctx, const char *d, const char *w, isl_set *delta_set; isl_set *slice; isl_set *origin; + isl_schedule_constraints *sc; isl_schedule *sched; int is_nonneg, is_parallel, is_tilable, is_injection, is_complete; @@ -2455,8 +2456,10 @@ int test_one_schedule(isl_ctx *ctx, const char *d, const char *w, validity = isl_union_map_copy(dep); proximity = isl_union_map_copy(dep); - sched = isl_union_set_compute_schedule(isl_union_set_copy(D), - validity, proximity); + sc = isl_schedule_constraints_on_domain(isl_union_set_copy(D)); + sc = isl_schedule_constraints_set_validity(sc, validity); + sc = isl_schedule_constraints_set_proximity(sc, proximity); + sched = isl_schedule_constraints_compute_schedule(sc); schedule = isl_schedule_get_map(sched); isl_schedule_free(sched); isl_union_map_free(W); @@ -2541,13 +2544,17 @@ static __isl_give isl_union_map *compute_schedule(isl_ctx *ctx, isl_union_set *dom; isl_union_map *dep; isl_union_map *prox; + isl_schedule_constraints *sc; isl_schedule *schedule; 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); + sc = isl_schedule_constraints_on_domain(dom); + sc = isl_schedule_constraints_set_validity(sc, dep); + sc = isl_schedule_constraints_set_proximity(sc, prox); + schedule = isl_schedule_constraints_compute_schedule(sc); sched = isl_schedule_get_map(schedule); isl_schedule_free(schedule); @@ -2600,6 +2607,7 @@ static int test_padded_schedule(isl_ctx *ctx) const char *str; isl_union_set *D; isl_union_map *validity, *proximity; + isl_schedule_constraints *sc; isl_schedule *sched; isl_union_map *map1, *map2; isl_band_list *list; @@ -2609,7 +2617,10 @@ static int test_padded_schedule(isl_ctx *ctx) D = isl_union_set_read_from_str(ctx, str); validity = isl_union_map_empty(isl_union_set_get_space(D)); proximity = isl_union_map_copy(validity); - sched = isl_union_set_compute_schedule(D, validity, proximity); + sc = isl_schedule_constraints_on_domain(D); + sc = isl_schedule_constraints_set_validity(sc, validity); + sc = isl_schedule_constraints_set_proximity(sc, proximity); + sched = isl_schedule_constraints_compute_schedule(sc); map1 = isl_schedule_get_map(sched); list = isl_schedule_get_band_forest(sched); isl_band_list_free(list);