introduce new schedule API
authorSven Verdoolaege <skimo@kotnet.org>
Wed, 21 Mar 2012 13:32:26 +0000 (21 14:32 +0100)
committerSven Verdoolaege <skimo@kotnet.org>
Wed, 18 Sep 2013 11:09:58 +0000 (18 13:09 +0200)
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 <skimo@kotnet.org>
doc/user.pod
include/isl/schedule.h
isl_schedule.c
isl_schedule_private.h
isl_test.c

index 7cd5d79..e58a398 100644 (file)
@@ -5622,30 +5622,75 @@ whereas C<isl_restriction_empty> is essentially equivalent to
 B<The functionality described in this section is fairly new
 and may be subject to change.>
 
-The following function can be used to compute a schedule
-for a union of domains.
+       #include <isl/schedule.h>
+       __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<isl_schedule_constraints_compute_schedule> 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<validity> dependences and I<proximity> dependences.
 By default, the algorithm used to construct the schedule is similar
 to that of C<Pluto>.
 Alternatively, Feautrier's multi-dimensional scheduling algorithm can
 be selected.
-The generated schedule respects all C<validity> 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<proximity> 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<proximity> dependence
+When using Feautrier's algorithm, the proximity dependence
 distances are only minimized during the extension to a
 full-dimensional schedule.
 
+An C<isl_schedule_constraints> object can be constructed
+and manipulated using the following functions.
+
+       #include <isl/schedule.h>
+       __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<isl_schedule_constraints> object created by
+C<isl_schedule_constraints_on_domain> does not impose any constraints.
+That is, it has an empty set of dependences.
+The function C<isl_schedule_constraints_set_validity> replaces the
+validity dependences, mapping domain elements I<i> to domain
+elements that should be scheduled after I<i>.
+The function C<isl_schedule_constraints_set_proximity> replaces the
+proximity dependences, mapping domain elements I<i> to domain
+elements that should be scheduled either before I<I>
+or as early as possible after I<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<isl_union_set_compute_schedule> is discouraged.
+
        #include <isl/schedule.h>
        __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<isl_schedule> using the following function.
index 385c6c4..3c34a81 100644 (file)
@@ -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,
index 362596d..9f0a8ff 100644 (file)
  * 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.
  *
index 5831071..d9477ca 100644 (file)
@@ -4,6 +4,27 @@
 #include <isl/aff.h>
 #include <isl/schedule.h>
 
+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
index f1a790d..cc8bab0 100644 (file)
@@ -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);