add option to bound the constant scheduling coefficients

If larger coefficients appear as part of the input dependences, the
schedule calculation can take a very long time. We observed that the
main overhead in this calculation is due to optimizing the constant
coefficients. They are misused to increase locality by merging several
unrelated dimensions into a single dimension. This unwanted optimization
increases the complexity of the code and slows down the generated code.

We introduce a new option that bounds the values in the constant
dimension by a user defined value. If the right value is choosen,
costly overoptimization can be prevented.

This solution works, but requires the user to specify the value by
which the constants are bound. For the moment, this is our best
solution, but we hope to to find a more generic one later on.

Signed-off-by: Tobias Grosser <tobias@grosser.es>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

diff --git a/doc/user.pod b/doc/user.pod
index 25548f8..76b6e01 100644 (file)
--- a/doc/user.pod
+++ b/doc/user.pod
@@ -4128,6 +4128,10 @@ A representation of the band can be printed using
 =head3 Options
 
        #include <isl/schedule.h>
+       int isl_options_set_schedule_max_constant_term(
+               isl_ctx *ctx, int val);
+       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(
@@ -4144,6 +4148,14 @@ A representation of the band can be printed using
 
 =over
 
+=item * max_constant_term
+
+This option enforces that the constant coefficients in the calculated schedule
+are not larger than the maximal constant term. This option can significantly
+increase the speed of the scheduling calculation and may also prevent fusing of
+unrelated dimensions. A value of -1 means that this option does not introduce
+bounds on the constant coefficients.
+
 =item * maximize_band_depth
 
 If this option is set, we do not split bands at the point

diff --git a/include/isl/schedule.h b/include/isl/schedule.h
index 4ff211d..3770b7a 100644 (file)
--- a/include/isl/schedule.h
+++ b/include/isl/schedule.h
@@ -12,6 +12,9 @@ extern "C" {
 struct isl_schedule;
 typedef struct isl_schedule isl_schedule;
 
+int isl_options_set_schedule_max_constant_term(isl_ctx *ctx, int val);
+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);
 

diff --git a/isl_options.c b/isl_options.c
index fd342f0..f43e0be 100644 (file)
--- a/isl_options.c
+++ b/isl_options.c
@@ -124,6 +124,10 @@ ISL_ARG_BOOL(struct isl_options, pip_symmetry, 0, "pip-symmetry", 1,
        "detect simple symmetries in PIP input")
 ISL_ARG_CHOICE(struct isl_options, convex, 0, "convex-hull", \
        convex, ISL_CONVEX_HULL_WRAP, "convex hull algorithm to use")
+ISL_ARG_INT(struct isl_options, schedule_max_constant_term, 0,
+       "schedule-max-constant-term", "limit", -1, "Only consider schedules "
+       "where the coefficients of the constant dimension do not exceed "
+       "<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,
@@ -156,6 +160,11 @@ ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
 ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
        gbr_only_first)
 
+ISL_CTX_SET_INT_DEF(isl_options, struct isl_options, isl_options_args,
+       schedule_max_constant_term)
+ISL_CTX_GET_INT_DEF(isl_options, struct isl_options, isl_options_args,
+       schedule_max_constant_term)
+
 ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
        schedule_maximize_band_depth)
 ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,

diff --git a/isl_options_private.h b/isl_options_private.h
index f49077c..6cbd882 100644 (file)
--- a/isl_options_private.h
+++ b/isl_options_private.h
@@ -45,6 +45,7 @@ struct isl_options {
        #define                 ISL_CONVEX_HULL_FM      1
        int                     convex;
 
+       int                     schedule_max_constant_term;
        int                     schedule_parametric;
        int                     schedule_outer_zero_distance;
        int                     schedule_maximize_band_depth;

diff --git a/isl_schedule.c b/isl_schedule.c
index 9f261e0..8e8a35c 100644 (file)
--- a/isl_schedule.c
+++ b/isl_schedule.c
@@ -1139,6 +1139,9 @@ static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
        int parametric;
        int param_pos;
        int n_eq, n_ineq;
+       int max_constant_term;
+
+       max_constant_term = ctx->opt->schedule_max_constant_term;
 
        parametric = ctx->opt->schedule_parametric;
        nparam = isl_space_dim(graph->node[0].dim, isl_dim_param);
@@ -1158,6 +1161,9 @@ static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
        dim = isl_space_set_alloc(ctx, 0, total);
        isl_basic_set_free(graph->lp);
        n_eq += 2 + parametric + force_zero;
+       if (max_constant_term != -1)
+               n_ineq += graph->n;
+
        graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
 
        k = isl_basic_set_alloc_equality(graph->lp);
@@ -1204,6 +1210,17 @@ static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
                        isl_int_set_si(graph->lp->eq[k][pos + j], 1);
        }
 
+       if (max_constant_term != -1)
+               for (i = 0; i < graph->n; ++i) {
+                       struct isl_sched_node *node = &graph->node[i];
+                       k = isl_basic_set_alloc_inequality(graph->lp);
+                       if (k < 0)
+                               return -1;
+                       isl_seq_clr(graph->lp->ineq[k], 1 +  total);
+                       isl_int_set_si(graph->lp->ineq[k][1 + node->start], -1);
+                       isl_int_set_si(graph->lp->ineq[k][0], max_constant_term);
+               }
+
        if (add_all_validity_constraints(graph) < 0)
                return -1;
        if (add_all_proximity_constraints(graph) < 0)