isl_schedule_constraints: split proximity constraints into coincidence/proximity
authorSven Verdoolaege <skimo@kotnet.org>
Tue, 27 Aug 2013 12:40:07 +0000 (27 14:40 +0200)
committerSven Verdoolaege <skimo@kotnet.org>
Wed, 18 Sep 2013 11:09:59 +0000 (18 13:09 +0200)
Before this commit, the only way to tell the schedule to try and
schedule pairs of iterations together was to add the pair to the
proximity constraints hoping that the extreme case of zero dependence
distance can be reached over all proximity constraints.
This fortuitous case would result in the "zero_distance" of a band member
being set.

This works out reasonably well for flow dependences for which you
typically want to minimize the dependence distance and where having
a zero dependence distance may allow parallelization.

There are however cases where only one of these two effects is desired.
For example, false dependences affect parallelism, but
you may or may not be interested in minimizing the dependence
distance over them.
On the other hand, you may want to add input dependences to
the proximity constraints, but they should not affect parallelism.

We therefore split the proximity constraints into proximity and
coincidence constraints.  The new proximity constraints have
the same effect of communicating a desire to minimize dependence
distances as the original proximity constraints, but they no longer
affect any "zero_distance" property.
Instead, the coincidence constraints can be used to express
a desire to schedule pairs of domain iterations together.
Success results in the "coincident" property being set on the band member.

During the construction of a band, the scheduler first tries to
satisfy the coincidence constraints.  If this fails, then it tries
again without the coincidence constraints.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
doc/user.pod
include/isl/band.h
include/isl/schedule.h
isl_band.c
isl_band_private.h
isl_options.c
isl_options_private.h
isl_schedule.c
isl_schedule_private.h
isl_test.c

index 857e240..e2b7431 100644 (file)
@@ -194,6 +194,13 @@ C<isl_union_pw_qpolynomial_eval>, C<isl_pw_qpolynomial_fold_eval>
 and C<isl_union_pw_qpolynomial_fold_eval> have been changed to return
 an C<isl_val> instead of an C<isl_qpolynomial>.
 
+=item * The function C<isl_band_member_is_zero_distance>
+has been removed.  Essentially the same functionality is available
+through C<isl_band_member_is_coincident>, except that is requires
+setting up coincidence constraints.
+The option C<schedule_outer_zero_distance> has accordingly been
+replaced by the option C<schedule_outer_coincidence>.
+
 =back
 
 =head1 License
@@ -5641,13 +5648,14 @@ be selected.
 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
-proximity dependences.
+The default algorithm tries to ensure that the dependence distances
+over coincidence constraints are zero and to minimize the
+dependence distances over 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 proximity dependence
-distances are only minimized during the extension to a
+for groups of domains where the dependence distances over validity
+dependences have only non-negative values.
+When using Feautrier's algorithm, the coincidence and proximity constraints
+are only taken into account during the extension to a
 full-dimensional schedule.
 
 An C<isl_schedule_constraints> object can be constructed
@@ -5664,6 +5672,10 @@ and manipulated using the following functions.
                __isl_take isl_schedule_constraints *sc,
                __isl_take isl_union_map *validity);
        __isl_give isl_schedule_constraints *
+       isl_schedule_constraints_set_coincidence(
+               __isl_take isl_schedule_constraints *sc,
+               __isl_take isl_union_map *coincidence);
+       __isl_give isl_schedule_constraints *
        isl_schedule_constraints_set_proximity(
                __isl_take isl_schedule_constraints *sc,
                __isl_take isl_union_map *proximity);
@@ -5681,6 +5693,9 @@ 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_coincidence> replaces the
+coincidence dependences, mapping domain elements I<i> to domain
+elements that should be scheduled together with I<I>, if possible.
 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>
@@ -5785,7 +5800,7 @@ The properties of a band can be inspected using the following functions.
                __isl_keep isl_band *band);
 
        int isl_band_n_member(__isl_keep isl_band *band);
-       int isl_band_member_is_zero_distance(
+       int isl_band_member_is_coincident(
                __isl_keep isl_band *band, int pos);
 
        int isl_band_list_foreach_band(
@@ -5793,11 +5808,10 @@ The properties of a band can be inspected using the following functions.
                int (*fn)(__isl_keep isl_band *band, void *user),
                void *user);
 
-Note that a scheduling dimension is considered to be ``zero
-distance'' if it does not carry any proximity dependences
-within its band.
-That is, if the dependence distances of the proximity
-dependences are all zero in that direction (for fixed
+Note that a scheduling dimension is considered to be ``coincident''
+if it satisfies the coincidence constraints within its band.
+That is, if the dependence distances of the coincidence
+constraints are all zero in that direction (for fixed
 iterations of outer bands).
 Like C<isl_schedule_foreach_band>,
 the function C<isl_band_list_foreach_band> calls C<fn> on the bands
@@ -5856,9 +5870,9 @@ A representation of the band can be printed using
                isl_ctx *ctx, int val);
        int isl_options_get_schedule_maximize_band_depth(
                isl_ctx *ctx);
-       int isl_options_set_schedule_outer_zero_distance(
+       int isl_options_set_schedule_outer_coincidence(
                isl_ctx *ctx, int val);
-       int isl_options_get_schedule_outer_zero_distance(
+       int isl_options_get_schedule_outer_coincidence(
                isl_ctx *ctx);
        int isl_options_set_schedule_split_scaled(
                isl_ctx *ctx, int val);
@@ -5911,12 +5925,11 @@ Note that if the C<schedule_fuse> option is set to C<ISL_SCHEDULE_FUSE_MIN>,
 then bands will be split as early as possible, even if there is no need.
 The C<schedule_maximize_band_depth> option therefore has no effect in this case.
 
-=item * schedule_outer_zero_distance
+=item * schedule_outer_coincidence
 
 If this option is set, then we try to construct schedules
 where the outermost scheduling dimension in each band
-results in a zero dependence distance over the proximity
-dependences.
+satisfies the coincidence constraints.
 
 =item * schedule_split_scaled
 
index 882393e..50f1113 100644 (file)
@@ -40,7 +40,7 @@ int isl_band_tile(__isl_keep isl_band *band, __isl_take isl_vec *sizes);
 int isl_band_split(__isl_keep isl_band *band, int pos);
 
 int isl_band_n_member(__isl_keep isl_band *band);
-int isl_band_member_is_zero_distance(__isl_keep isl_band *band, int pos);
+int isl_band_member_is_coincident(__isl_keep isl_band *band, int pos);
 
 int isl_band_list_foreach_band(__isl_keep isl_band_list *list,
        int (*fn)(__isl_keep isl_band *band, void *user), void *user);
index 3617a59..347bf9d 100644 (file)
@@ -24,8 +24,8 @@ int isl_options_get_schedule_max_constant_term(isl_ctx *ctx);
 int isl_options_set_schedule_maximize_band_depth(isl_ctx *ctx, int val);
 int isl_options_get_schedule_maximize_band_depth(isl_ctx *ctx);
 
-int isl_options_set_schedule_outer_zero_distance(isl_ctx *ctx, int val);
-int isl_options_get_schedule_outer_zero_distance(isl_ctx *ctx);
+int isl_options_set_schedule_outer_coincidence(isl_ctx *ctx, int val);
+int isl_options_get_schedule_outer_coincidence(isl_ctx *ctx);
 
 int isl_options_set_schedule_split_scaled(isl_ctx *ctx, int val);
 int isl_options_get_schedule_split_scaled(isl_ctx *ctx);
@@ -43,6 +43,9 @@ __isl_give isl_schedule_constraints *isl_schedule_constraints_on_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_coincidence(
+       __isl_take isl_schedule_constraints *sc,
+       __isl_take isl_union_map *coincidence);
 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_proximity(
        __isl_take isl_schedule_constraints *sc,
        __isl_take isl_union_map *proximity);
index 60d52a1..b820b55 100644 (file)
@@ -55,12 +55,12 @@ __isl_give isl_band *isl_band_dup(__isl_keep isl_band *band)
                return NULL;
 
        dup->n = band->n;
-       dup->zero = isl_alloc_array(ctx, int, band->n);
-       if (band->n && !dup->zero)
+       dup->coincident = isl_alloc_array(ctx, int, band->n);
+       if (band->n && !dup->coincident)
                goto error;
 
        for (i = 0; i < band->n; ++i)
-               dup->zero[i] = band->zero[i];
+               dup->coincident[i] = band->coincident[i];
 
        dup->pma = isl_union_pw_multi_aff_copy(band->pma);
        dup->schedule = band->schedule;
@@ -106,7 +106,7 @@ void *isl_band_free(__isl_take isl_band *band)
 
        isl_union_pw_multi_aff_free(band->pma);
        isl_band_list_free(band->children);
-       free(band->zero);
+       free(band->coincident);
        free(band);
 
        return NULL;
@@ -136,10 +136,10 @@ int isl_band_n_member(__isl_keep isl_band *band)
        return band ? band->n : 0;
 }
 
-/* Is the given scheduling dimension zero distance within the band and
- * with respect to the proximity dependences.
+/* Is the given scheduling dimension coincident within the band and
+ * with respect to the coincidence constraints.
  */
-int isl_band_member_is_zero_distance(__isl_keep isl_band *band, int pos)
+int isl_band_member_is_coincident(__isl_keep isl_band *band, int pos)
 {
        if (!band)
                return -1;
@@ -148,7 +148,7 @@ int isl_band_member_is_zero_distance(__isl_keep isl_band *band, int pos)
                isl_die(isl_band_get_ctx(band), isl_error_invalid,
                        "invalid member position", return -1);
 
-       return band->zero[pos];
+       return band->coincident[pos];
 }
 
 /* Return the schedule that leads up to this band.
@@ -654,7 +654,7 @@ static int isl_band_drop(__isl_keep isl_band *band, int pos, int n)
        band->pma = sched;
 
        for (i = pos + n; i < band->n; ++i)
-               band->zero[i - n] = band->zero[i];
+               band->coincident[i - n] = band->coincident[i];
 
        band->n -= n;
 
index ef0e0ed..8b9c0b7 100644 (file)
@@ -9,8 +9,9 @@
 /* Information about a band within a schedule.
  *
  * n is the number of scheduling dimensions within the band.
- * zero is an array of length n, indicating whether a scheduling dimension
- *     results in zero dependence distances for the proximity dependences.
+ * coincident is an array of length n, indicating whether a scheduling dimension
+ *     satisfies the coincidence constraints in the sense that
+ *     the corresponding dependence distances are zero.
  * pma is the partial schedule corresponding to this band.
  * schedule is the schedule that contains this band.
  * parent is the parent of this band (or NULL if the band is a root).
@@ -25,7 +26,7 @@ struct isl_band {
        int ref;
 
        int n;
-       int *zero;
+       int *coincident;
 
        isl_union_pw_multi_aff *pma;
        isl_schedule *schedule;
index 58bc13f..7e96712 100644 (file)
@@ -126,10 +126,10 @@ ISL_ARG_INT(struct isl_options, schedule_max_constant_term, 0,
        "<limit>. A value of -1 allows arbitrary coefficients.")
 ISL_ARG_BOOL(struct isl_options, schedule_parametric, 0,
        "schedule-parametric", 1, "construct possibly parametric schedules")
-ISL_ARG_BOOL(struct isl_options, schedule_outer_zero_distance, 0,
-       "schedule-outer-zero-distance", 0,
-       "try to construct schedules with outer zero distances over "
-       "proximity dependences")
+ISL_ARG_BOOL(struct isl_options, schedule_outer_coincidence, 0,
+       "schedule-outer-coincidence", 0,
+       "try to construct schedules where the outer member of each band "
+       "satisfies the coincidence constraints")
 ISL_ARG_BOOL(struct isl_options, schedule_maximize_band_depth, 0,
        "schedule-maximize-band-depth", 0,
        "maximize the number of scheduling dimensions in a band")
@@ -223,9 +223,9 @@ ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
        schedule_separate_components)
 
 ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
-       schedule_outer_zero_distance)
+       schedule_outer_coincidence)
 ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
-       schedule_outer_zero_distance)
+       schedule_outer_coincidence)
 
 ISL_CTX_SET_CHOICE_DEF(isl_options, struct isl_options, isl_options_args,
        schedule_algorithm)
index e995ecc..b63eab0 100644 (file)
@@ -38,7 +38,7 @@ struct isl_options {
        int                     schedule_max_coefficient;
        int                     schedule_max_constant_term;
        int                     schedule_parametric;
-       int                     schedule_outer_zero_distance;
+       int                     schedule_outer_coincidence;
        int                     schedule_maximize_band_depth;
        int                     schedule_split_scaled;
        int                     schedule_separate_components;
index c7e93ed..472c7f5 100644 (file)
@@ -91,6 +91,25 @@ error:
        return NULL;
 }
 
+/* Replace the coincidence constraints of "sc" by "coincidence".
+ */
+__isl_give isl_schedule_constraints *isl_schedule_constraints_set_coincidence(
+       __isl_take isl_schedule_constraints *sc,
+       __isl_take isl_union_map *coincidence)
+{
+       if (!sc || !coincidence)
+               goto error;
+
+       isl_union_map_free(sc->constraint[isl_edge_coincidence]);
+       sc->constraint[isl_edge_coincidence] = coincidence;
+
+       return sc;
+error:
+       isl_schedule_constraints_free(sc);
+       isl_union_map_free(coincidence);
+       return NULL;
+}
+
 /* Replace the proximity constraints of "sc" by "proximity".
  */
 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_proximity(
@@ -168,6 +187,8 @@ void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints *sc)
        isl_union_map_dump(sc->constraint[isl_edge_validity]);
        fprintf(stderr, "proximity: ");
        isl_union_map_dump(sc->constraint[isl_edge_proximity]);
+       fprintf(stderr, "coincidence: ");
+       isl_union_map_dump(sc->constraint[isl_edge_coincidence]);
        fprintf(stderr, "condition: ");
        isl_union_map_dump(sc->constraint[isl_edge_condition]);
        fprintf(stderr, "conditional_validity: ");
@@ -242,10 +263,10 @@ static __isl_give int isl_schedule_constraints_n_map(
  * band_id is used to differentiate between separate bands at the same
  * level within the same parent band, i.e., bands that are separated
  * by the parent band or bands that are independent of each other.
- * zero contains a boolean for each of the rows of the schedule,
- * indicating whether the corresponding scheduling dimension results
- * in zero dependence distances within its band and with respect
- * to the proximity edges.
+ * coincident contains a boolean for each of the rows of the schedule,
+ * indicating whether the corresponding scheduling dimension satisfies
+ * the coincidence constraints in the sense that the corresponding
+ * dependence distances are zero.
  */
 struct isl_sched_node {
        isl_space *dim;
@@ -262,7 +283,7 @@ struct isl_sched_node {
 
        int     *band;
        int     *band_id;
-       int     *zero;
+       int     *coincident;
 };
 
 static int node_has_dim(const void *entry, const void *val)
@@ -287,6 +308,7 @@ static int node_has_dim(const void *entry, const void *val)
  * src is the source node
  * dst is the sink node
  * validity is set if the edge is used to ensure correctness
+ * coincidence is used to enforce zero dependence distances
  * proximity is set if the edge is used to minimize dependence distances
  * condition is set if the edge represents a condition
  *     for a conditional validity schedule constraint
@@ -308,6 +330,7 @@ struct isl_sched_edge {
        struct isl_sched_node *dst;
 
        unsigned validity : 1;
+       unsigned coincidence : 1;
        unsigned proximity : 1;
        unsigned local : 1;
        unsigned condition : 1;
@@ -672,7 +695,7 @@ static void graph_free(isl_ctx *ctx, struct isl_sched_graph *graph)
                if (graph->root) {
                        free(graph->node[i].band);
                        free(graph->node[i].band_id);
-                       free(graph->node[i].zero);
+                       free(graph->node[i].coincident);
                }
        }
        free(graph->node);
@@ -736,7 +759,7 @@ static int extract_node(__isl_take isl_set *set, void *user)
        isl_space *dim;
        isl_mat *sched;
        struct isl_sched_graph *graph = user;
-       int *band, *band_id, *zero;
+       int *band, *band_id, *coincident;
 
        ctx = isl_set_get_ctx(set);
        dim = isl_set_get_space(set);
@@ -755,11 +778,11 @@ static int extract_node(__isl_take isl_set *set, void *user)
        graph->node[graph->n].band = band;
        band_id = isl_calloc_array(ctx, int, graph->max_row);
        graph->node[graph->n].band_id = band_id;
-       zero = isl_calloc_array(ctx, int, graph->max_row);
-       graph->node[graph->n].zero = zero;
+       coincident = isl_calloc_array(ctx, int, graph->max_row);
+       graph->node[graph->n].coincident = coincident;
        graph->n++;
 
-       if (!sched || (graph->max_row && (!band || !band_id || !zero)))
+       if (!sched || (graph->max_row && (!band || !band_id || !coincident)))
                return -1;
 
        return 0;
@@ -781,6 +804,7 @@ static int merge_edge(enum isl_edge_type type, struct isl_sched_edge *edge1,
        struct isl_sched_edge *edge2)
 {
        edge1->validity |= edge2->validity;
+       edge1->coincidence |= edge2->coincidence;
        edge1->proximity |= edge2->proximity;
        edge1->condition |= edge2->condition;
        edge1->conditional_validity |= edge2->conditional_validity;
@@ -902,6 +926,7 @@ static int extract_edge(__isl_take isl_map *map, void *user)
        graph->edge[graph->n_edge].dst = dst;
        graph->edge[graph->n_edge].map = map;
        graph->edge[graph->n_edge].validity = 0;
+       graph->edge[graph->n_edge].coincidence = 0;
        graph->edge[graph->n_edge].proximity = 0;
        graph->edge[graph->n_edge].condition = 0;
        graph->edge[graph->n_edge].local = 0;
@@ -910,6 +935,8 @@ static int extract_edge(__isl_take isl_map *map, void *user)
        graph->edge[graph->n_edge].tagged_validity = NULL;
        if (data->type == isl_edge_validity)
                graph->edge[graph->n_edge].validity = 1;
+       if (data->type == isl_edge_coincidence)
+               graph->edge[graph->n_edge].coincidence = 1;
        if (data->type == isl_edge_proximity)
                graph->edge[graph->n_edge].proximity = 1;
        if (data->type == isl_edge_condition) {
@@ -1437,14 +1464,21 @@ error:
  * distances equal to zero.  We take care of bounding them by 0 from below
  * here.  add_all_proximity_constraints takes care of bounding them by 0
  * from above.
+ *
+ * If "use_coincidence" is set, then we treat coincidence edges as local edges.
+ * Otherwise, we ignore them.
  */
-static int add_all_validity_constraints(struct isl_sched_graph *graph)
+static int add_all_validity_constraints(struct isl_sched_graph *graph,
+       int use_coincidence)
 {
        int i;
 
        for (i = 0; i < graph->n_edge; ++i) {
                struct isl_sched_edge *edge= &graph->edge[i];
-               if (!edge->validity && !edge->local)
+               int local;
+
+               local = edge->local || (edge->coincidence && use_coincidence);
+               if (!edge->validity && !local)
                        continue;
                if (edge->src != edge->dst)
                        continue;
@@ -1454,7 +1488,10 @@ static int add_all_validity_constraints(struct isl_sched_graph *graph)
 
        for (i = 0; i < graph->n_edge; ++i) {
                struct isl_sched_edge *edge = &graph->edge[i];
-               if (!edge->validity && !edge->local)
+               int local;
+
+               local = edge->local || (edge->coincidence && use_coincidence);
+               if (!edge->validity && !local)
                        continue;
                if (edge->src == edge->dst)
                        continue;
@@ -1473,15 +1510,20 @@ static int add_all_validity_constraints(struct isl_sched_graph *graph)
  * from above.  (This includes the case of "local" dependences
  * which are treated as validity dependence by add_all_validity_constraints.)
  * Otherwise, we need to bound the distance both from above and from below.
+ *
+ * If "use_coincidence" is set, then we treat coincidence edges as local edges.
+ * Otherwise, we ignore them.
  */
-static int add_all_proximity_constraints(struct isl_sched_graph *graph)
+static int add_all_proximity_constraints(struct isl_sched_graph *graph,
+       int use_coincidence)
 {
        int i;
 
        for (i = 0; i < graph->n_edge; ++i) {
                struct isl_sched_edge *edge= &graph->edge[i];
-               int local = edge->local;
+               int local;
 
+               local = edge->local || (edge->coincidence && use_coincidence);
                if (!edge->proximity && !local)
                        continue;
                if (edge->src == edge->dst &&
@@ -1558,8 +1600,12 @@ static int node_update_cmap(struct isl_sched_node *node)
  *
  * If an edge is only marked conditional_validity then it counts
  * as zero since it is only checked afterwards.
+ *
+ * If "use_coincidence" is set, then we treat coincidence edges as local edges.
+ * Otherwise, we ignore them.
  */
-static int edge_multiplicity(struct isl_sched_edge *edge, int carry)
+static int edge_multiplicity(struct isl_sched_edge *edge, int carry,
+       int use_coincidence)
 {
        if (carry && !edge->validity && !edge->conditional_validity)
                return 0;
@@ -1567,6 +1613,8 @@ static int edge_multiplicity(struct isl_sched_edge *edge, int carry)
                return 1;
        if (edge->proximity || edge->local)
                return 2;
+       if (use_coincidence && edge->coincidence)
+               return 2;
        if (edge->validity)
                return 1;
        return 0;
@@ -1574,13 +1622,15 @@ static int edge_multiplicity(struct isl_sched_edge *edge, int carry)
 
 /* Count the number of equality and inequality constraints
  * that will be added for the given map.
+ *
+ * "use_coincidence" is set if we should take into account coincidence edges.
  */
 static int count_map_constraints(struct isl_sched_graph *graph,
        struct isl_sched_edge *edge, __isl_take isl_map *map,
-       int *n_eq, int *n_ineq, int carry)
+       int *n_eq, int *n_ineq, int carry, int use_coincidence)
 {
        isl_basic_set *coef;
-       int f = edge_multiplicity(edge, carry);
+       int f = edge_multiplicity(edge, carry, use_coincidence);
 
        if (f == 0) {
                isl_map_free(map);
@@ -1607,9 +1657,12 @@ static int count_map_constraints(struct isl_sched_graph *graph,
  * validity+proximity  -> 2 (>= 0 and upper bound)
  * proximity           -> 2 (lower and upper bound)
  * local(+any)         -> 2 (>= 0 and <= 0)
+ *
+ * If "use_coincidence" is set, then we treat coincidence edges as local edges.
+ * Otherwise, we ignore them.
  */
 static int count_constraints(struct isl_sched_graph *graph,
-       int *n_eq, int *n_ineq)
+       int *n_eq, int *n_ineq, int use_coincidence)
 {
        int i;
 
@@ -1618,8 +1671,8 @@ static int count_constraints(struct isl_sched_graph *graph,
                struct isl_sched_edge *edge= &graph->edge[i];
                isl_map *map = isl_map_copy(edge->map);
 
-               if (count_map_constraints(graph, edge, map,
-                                         n_eq, n_ineq, 0) < 0)
+               if (count_map_constraints(graph, edge, map, n_eq, n_ineq,
+                                           0, use_coincidence) < 0)
                        return -1;
        }
 
@@ -1714,11 +1767,11 @@ static int add_bound_coefficient_constraints(isl_ctx *ctx,
  * The constraints are those from the edges plus two or three equalities
  * to express the sums.
  *
- * If force_zero is set, then we add equalities to ensure that
- * the sum of the m_n coefficients and m_0 are both zero.
+ * If "use_coincidence" is set, then we treat coincidence edges as local edges.
+ * Otherwise, we ignore them.
  */
 static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
-       int force_zero)
+       int use_coincidence)
 {
        int i, j;
        int k;
@@ -1744,14 +1797,14 @@ static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
                total += 1 + 2 * (node->nparam + node->nvar);
        }
 
-       if (count_constraints(graph, &n_eq, &n_ineq) < 0)
+       if (count_constraints(graph, &n_eq, &n_ineq, use_coincidence) < 0)
                return -1;
        if (count_bound_coefficient_constraints(ctx, graph, &n_eq, &n_ineq) < 0)
                return -1;
 
        dim = isl_space_set_alloc(ctx, 0, total);
        isl_basic_set_free(graph->lp);
-       n_eq += 2 + parametric + force_zero;
+       n_eq += 2 + parametric;
        if (max_constant_term != -1)
                n_ineq += graph->n;
 
@@ -1761,19 +1814,10 @@ static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
        if (k < 0)
                return -1;
        isl_seq_clr(graph->lp->eq[k], 1 +  total);
-       if (!force_zero)
-               isl_int_set_si(graph->lp->eq[k][1], -1);
+       isl_int_set_si(graph->lp->eq[k][1], -1);
        for (i = 0; i < 2 * nparam; ++i)
                isl_int_set_si(graph->lp->eq[k][1 + param_pos + i], 1);
 
-       if (force_zero) {
-               k = isl_basic_set_alloc_equality(graph->lp);
-               if (k < 0)
-                       return -1;
-               isl_seq_clr(graph->lp->eq[k], 1 +  total);
-               isl_int_set_si(graph->lp->eq[k][2], -1);
-       }
-
        if (parametric) {
                k = isl_basic_set_alloc_equality(graph->lp);
                if (k < 0)
@@ -1814,9 +1858,9 @@ static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
 
        if (add_bound_coefficient_constraints(ctx, graph) < 0)
                return -1;
-       if (add_all_validity_constraints(graph) < 0)
+       if (add_all_validity_constraints(graph, use_coincidence) < 0)
                return -1;
-       if (add_all_proximity_constraints(graph) < 0)
+       if (add_all_proximity_constraints(graph, use_coincidence) < 0)
                return -1;
 
        return 0;
@@ -1914,16 +1958,13 @@ static __isl_give isl_vec *solve_lp(struct isl_sched_graph *graph)
  * In this case, we then also need to perform this multiplication
  * to obtain the values of c_i_x.
  *
- * If check_zero is set, then the first two coordinates of sol are
- * assumed to correspond to the dependence distance.  If these two
- * coordinates are zero, then the corresponding scheduling dimension
- * is marked as being zero distance.
+ * If coincident is set, then the caller guarantees that the new
+ * row satisfies the coincidence constraints.
  */
 static int update_schedule(struct isl_sched_graph *graph,
-       __isl_take isl_vec *sol, int use_cmap, int check_zero)
+       __isl_take isl_vec *sol, int use_cmap, int coincident)
 {
        int i, j;
-       int zero = 0;
        isl_vec *csol = NULL;
 
        if (!sol)
@@ -1935,10 +1976,6 @@ static int update_schedule(struct isl_sched_graph *graph,
                isl_die(sol->ctx, isl_error_internal,
                        "too many schedule rows", goto error);
 
-       if (check_zero)
-               zero = isl_int_is_zero(sol->el[1]) &&
-                          isl_int_is_zero(sol->el[2]);
-
        for (i = 0; i < graph->n; ++i) {
                struct isl_sched_node *node = &graph->node[i];
                int pos = node->start;
@@ -1975,7 +2012,7 @@ static int update_schedule(struct isl_sched_graph *graph,
                        node->sched = isl_mat_set_element(node->sched,
                                        row, 1 + node->nparam + j, csol->el[j]);
                node->band[graph->n_total_row] = graph->n_band;
-               node->zero[graph->n_total_row] = zero;
+               node->coincident[graph->n_total_row] = coincident;
        }
        isl_vec_free(sol);
        isl_vec_free(csol);
@@ -2231,7 +2268,7 @@ static __isl_give isl_schedule *extract_schedule(struct isl_sched_graph *graph,
 
        for (i = 0; i < sched->n; ++i) {
                int r, b;
-               int *band_end, *band_id, *zero;
+               int *band_end, *band_id, *coincident;
 
                sched->node[i].sched =
                        node_extract_schedule_multi_aff(&graph->node[i]);
@@ -2244,15 +2281,15 @@ static __isl_give isl_schedule *extract_schedule(struct isl_sched_graph *graph,
 
                band_end = isl_alloc_array(ctx, int, graph->n_band);
                band_id = isl_alloc_array(ctx, int, graph->n_band);
-               zero = isl_alloc_array(ctx, int, graph->n_total_row);
+               coincident = isl_alloc_array(ctx, int, graph->n_total_row);
                sched->node[i].band_end = band_end;
                sched->node[i].band_id = band_id;
-               sched->node[i].zero = zero;
-               if (!band_end || !band_id || !zero)
+               sched->node[i].coincident = coincident;
+               if (!band_end || !band_id || !coincident)
                        goto error;
 
                for (r = 0; r < graph->n_total_row; ++r)
-                       zero[r] = graph->node[i].zero[r];
+                       coincident[r] = graph->node[i].coincident[r];
                for (r = b = 0; r < graph->n_total_row; ++r) {
                        if (graph->node[i].band[r] == b)
                                continue;
@@ -2296,7 +2333,7 @@ static int copy_nodes(struct isl_sched_graph *dst, struct isl_sched_graph *src,
                        isl_map_copy(src->node[i].sched_map);
                dst->node[dst->n].band = src->node[i].band;
                dst->node[dst->n].band_id = src->node[i].band_id;
-               dst->node[dst->n].zero = src->node[i].zero;
+               dst->node[dst->n].coincident = src->node[i].coincident;
                dst->n++;
        }
 
@@ -2351,6 +2388,7 @@ static int copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst,
                dst->edge[dst->n_edge].tagged_validity = tagged_validity;
                dst->edge[dst->n_edge].validity = edge->validity;
                dst->edge[dst->n_edge].proximity = edge->proximity;
+               dst->edge[dst->n_edge].coincidence = edge->coincidence;
                dst->edge[dst->n_edge].condition = edge->condition;
                dst->edge[dst->n_edge].conditional_validity =
                                                edge->conditional_validity;
@@ -2577,9 +2615,9 @@ static int reset_band(struct isl_sched_graph *graph)
  * It would be possible to reuse them as the first rows in the next
  * band, but recomputing them may result in better rows as we are looking
  * at a smaller part of the dependence graph.
- * compute_split_schedule is only called when no zero-distance schedule row
- * could be found on the entire graph, so we wark the splitting row as
- * non zero-distance.
+ *
+ * Since we do not enforce coincidence, we conservatively mark the
+ * splitting row as not coincident.
  *
  * The band_id of the second group is set to n, where n is the number
  * of nodes in the first group.  This ensures that the band_ids over
@@ -2620,7 +2658,7 @@ static int compute_split_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
                        node->sched = isl_mat_set_element_si(node->sched,
                                                             row, j, 0);
                node->band[graph->n_total_row] = graph->n_band;
-               node->zero[graph->n_total_row] = 0;
+               node->coincident[graph->n_total_row] = 0;
        }
 
        e1 = e2 = 0;
@@ -2844,7 +2882,7 @@ static int count_all_constraints(struct isl_sched_graph *graph,
                        map = isl_map_from_basic_map(bmap);
 
                        if (count_map_constraints(graph, edge, map,
-                                                 n_eq, n_ineq, 1) < 0)
+                                                 n_eq, n_ineq, 1, 0) < 0)
                                    return -1;
                }
        }
@@ -3259,6 +3297,19 @@ static int need_condition_check(struct isl_sched_graph *graph)
        return any_condition && any_conditional_validity;
 }
 
+/* Does "graph" contain any coincidence edge?
+ */
+static int has_any_coincidence(struct isl_sched_graph *graph)
+{
+       int i;
+
+       for (i = 0; i < graph->n_edge; ++i)
+               if (graph->edge[i].coincidence)
+                       return 1;
+
+       return 0;
+}
+
 /* Extract the final schedule row as a map with the iteration domain
  * of "node" as domain.
  */
@@ -3475,7 +3526,8 @@ error:
 /* Compute a schedule for a connected dependence graph.
  * We try to find a sequence of as many schedule rows as possible that result
  * in non-negative dependence distances (independent of the previous rows
- * in the sequence, i.e., such that the sequence is tilable).
+ * in the sequence, i.e., such that the sequence is tilable), with as
+ * many of the initial rows as possible satisfying the coincidence constraints.
  * If we can't find any more rows we either
  * - split between SCCs and start over (assuming we found an interesting
  *     pair of SCCs between which to split)
@@ -3491,8 +3543,8 @@ error:
  * If we manage to complete the schedule, we finish off by topologically
  * sorting the statements based on the remaining dependences.
  *
- * If ctx->opt->schedule_outer_zero_distance is set, then we force the
- * outermost dimension in the current band to be zero distance.  If this
+ * If ctx->opt->schedule_outer_coincidence is set, then we force the
+ * outermost dimension to satisfy the coincidence constraints.  If this
  * turns out to be impossible, we fall back on the general scheme above
  * and try to carry as many dependences as possible.
  *
@@ -3514,8 +3566,9 @@ error:
  */
 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph)
 {
-       int init_force_zero = 0;
-       int force_zero;
+       int has_coincidence;
+       int use_coincidence;
+       int force_coincidence = 0;
        int check_conditional;
 
        if (detect_sccs(ctx, graph) < 0)
@@ -3531,37 +3584,44 @@ static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph)
 
        clear_local_edges(graph);
        check_conditional = need_condition_check(graph);
+       has_coincidence = has_any_coincidence(graph);
 
-       if (ctx->opt->schedule_outer_zero_distance)
-               init_force_zero = 1;
+       if (ctx->opt->schedule_outer_coincidence)
+               force_coincidence = 1;
 
-       force_zero = init_force_zero;
+       use_coincidence = has_coincidence;
        while (graph->n_row < graph->maxvar) {
                isl_vec *sol;
                int violated;
+               int coincident;
 
                graph->src_scc = -1;
                graph->dst_scc = -1;
 
-               if (setup_lp(ctx, graph, force_zero) < 0)
+               if (setup_lp(ctx, graph, use_coincidence) < 0)
                        return -1;
                sol = solve_lp(graph);
                if (!sol)
                        return -1;
                if (sol->size == 0) {
+                       int empty = graph->n_total_row == graph->band_start;
+
                        isl_vec_free(sol);
-                       if (!ctx->opt->schedule_maximize_band_depth &&
-                           graph->n_total_row > graph->band_start)
+                       if (use_coincidence && (!force_coincidence || !empty)) {
+                               use_coincidence = 0;
+                               continue;
+                       }
+                       if (!ctx->opt->schedule_maximize_band_depth && !empty)
                                return compute_next_band(ctx, graph);
                        if (graph->src_scc >= 0)
                                return compute_split_schedule(ctx, graph);
-                       if (graph->n_total_row > graph->band_start)
+                       if (!empty)
                                return compute_next_band(ctx, graph);
                        return carry_dependences(ctx, graph);
                }
-               if (update_schedule(graph, sol, 1, 1) < 0)
+               coincident = !has_coincidence || use_coincidence;
+               if (update_schedule(graph, sol, 1, coincident) < 0)
                        return -1;
-               force_zero = 0;
 
                if (!check_conditional)
                        continue;
@@ -3572,7 +3632,7 @@ static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph)
                        continue;
                if (reset_band(graph) < 0)
                        return -1;
-               force_zero = init_force_zero;
+               use_coincidence = has_coincidence;
        }
 
        if (graph->n_total_row > graph->band_start)
@@ -3796,7 +3856,7 @@ void *isl_schedule_free(__isl_take isl_schedule *sched)
                isl_multi_aff_free(sched->node[i].sched);
                free(sched->node[i].band_end);
                free(sched->node[i].band_id);
-               free(sched->node[i].zero);
+               free(sched->node[i].coincident);
        }
        isl_space_free(sched->dim);
        isl_band_list_free(sched->band_forest);
@@ -3957,12 +4017,12 @@ static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule,
                schedule->node[i].band_end[band_nr] : start;
        band->n = end - start;
 
-       band->zero = isl_alloc_array(ctx, int, band->n);
-       if (band->n && !band->zero)
+       band->coincident = isl_alloc_array(ctx, int, band->n);
+       if (band->n && !band->coincident)
                goto error;
 
        for (j = 0; j < band->n; ++j)
-               band->zero[j] = schedule->node[i].zero[start + j];
+               band->coincident[j] = schedule->node[i].coincident[start + j];
 
        band->pma = isl_union_pw_multi_aff_empty(isl_space_copy(schedule->dim));
        for (i = 0; i < schedule->n; ++i) {
index 4f46daf..4e12724 100644 (file)
@@ -7,6 +7,7 @@
 enum isl_edge_type {
        isl_edge_validity = 0,
        isl_edge_first = isl_edge_validity,
+       isl_edge_coincidence,
        isl_edge_condition,
        isl_edge_conditional_validity,
        isl_edge_proximity,
@@ -43,16 +44,15 @@ struct isl_schedule_constraints {
  * In particular, we keep track of the number of bands and for each
  * band, the starting position of the next band.  The first band starts at
  * position 0.
- * For each scheduling dimension, we keep track of whether it result
- * in zero dependence distances (within its band) with respect
- * to the proximity edges.
+ * For each scheduling dimension, we keep track of whether it satisfies
+ * the coincidence constraints (within its band).
  */
 struct isl_schedule_node {
        isl_multi_aff *sched;
        int      n_band;
        int     *band_end;
        int     *band_id;
-       int     *zero;
+       int     *coincident;
 };
 
 /* Information about the computed schedule.
index 2e2755c..8d393f0 100644 (file)
@@ -2420,7 +2420,7 @@ int test_one_schedule(isl_ctx *ctx, const char *d, const char *w,
        isl_union_map *W, *R, *S;
        isl_union_map *empty;
        isl_union_map *dep_raw, *dep_war, *dep_waw, *dep;
-       isl_union_map *validity, *proximity;
+       isl_union_map *validity, *proximity, *coincidence;
        isl_union_map *schedule;
        isl_union_map *test;
        isl_union_set *delta;
@@ -2454,10 +2454,12 @@ int test_one_schedule(isl_ctx *ctx, const char *d, const char *w,
        dep = isl_union_map_union(dep_waw, dep_war);
        dep = isl_union_map_union(dep, dep_raw);
        validity = isl_union_map_copy(dep);
+       coincidence = isl_union_map_copy(dep);
        proximity = isl_union_map_copy(dep);
 
        sc = isl_schedule_constraints_on_domain(isl_union_set_copy(D));
        sc = isl_schedule_constraints_set_validity(sc, validity);
+       sc = isl_schedule_constraints_set_coincidence(sc, coincidence);
        sc = isl_schedule_constraints_set_proximity(sc, proximity);
        sched = isl_schedule_constraints_compute_schedule(sc);
        schedule = isl_schedule_get_map(sched);
@@ -2944,10 +2946,10 @@ int test_schedule(isl_ctx *ctx)
                    "S_0[j, k] -> A[k] : j <= -1 + n and j >= 0 and "
                                        "k <= -1 + n and k >= 0 }";
        S = "[n] -> { S_0[j, k] -> [2, j, k] }";
-       ctx->opt->schedule_outer_zero_distance = 1;
+       ctx->opt->schedule_outer_coincidence = 1;
        if (test_one_schedule(ctx, D, W, R, S, 0, 0) < 0)
                return -1;
-       ctx->opt->schedule_outer_zero_distance = 0;
+       ctx->opt->schedule_outer_coincidence = 0;
 
        D = "{Stmt_for_body24[i0, i1, i2, i3]:"
                "i0 >= 0 and i0 <= 1 and i1 >= 0 and i1 <= 6 and i2 >= 2 and "