isl_stride.c

   1 /*
   2  * Copyright 2012-2013 Ecole Normale Superieure
   3  *
   4  * Use of this software is governed by the MIT license
   5  *
   6  * Written by Sven Verdoolaege,
   7  * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
   8  */
   9
  10 #include <isl/val.h>
  11 #include <isl/aff.h>
  12 #include <isl/constraint.h>
  13 #include <isl/set.h>
  14
  15 /* Stride information about a specific set dimension.
  16  * The values of the set dimension are equal to
  17  * "offset" plus a multiple of "stride".
  18  */
  19 struct isl_stride_info {
  20         isl_val *stride;
  21         isl_aff *offset;
  22 };
  23
  24 /* Free "si" and return NULL.
  25  */
  26 __isl_null isl_stride_info *isl_stride_info_free(
  27         __isl_take isl_stride_info *si)
  28 {
  29         if (!si)
  30                 return NULL;
  31         isl_val_free(si->stride);
  32         isl_aff_free(si->offset);
  33         free(si);
  34         return NULL;
  35 }
  36
  37 /* Construct an isl_stride_info object with given offset and stride.
  38  */
  39 __isl_give isl_stride_info *isl_stride_info_alloc(
  40         __isl_take isl_val *stride, __isl_take isl_aff *offset)
  41 {
  42         struct isl_stride_info *si;
  43
  44         if (!stride || !offset)
  45                 goto error;
  46         si = isl_alloc_type(isl_val_get_ctx(stride), struct isl_stride_info);
  47         if (!si)
  48                 goto error;
  49         si->stride = stride;
  50         si->offset = offset;
  51         return si;
  52 error:
  53         isl_val_free(stride);
  54         isl_aff_free(offset);
  55         return NULL;
  56 }
  57
  58 /* Return the stride of "si".
  59  */
  60 __isl_give isl_val *isl_stride_info_get_stride(__isl_keep isl_stride_info *si)
  61 {
  62         if (!si)
  63                 return NULL;
  64         return isl_val_copy(si->stride);
  65 }
  66
  67 /* Return the offset of "si".
  68  */
  69 __isl_give isl_aff *isl_stride_info_get_offset(__isl_keep isl_stride_info *si)
  70 {
  71         if (!si)
  72                 return NULL;
  73         return isl_aff_copy(si->offset);
  74 }
  75
  76 /* Information used inside detect_stride.
  77  *
  78  * "pos" is the set dimension at which the stride is being determined.
  79  * "want_offset" is set if the offset should be computed.
  80  * "found" is set if some stride was found already.
  81  * "stride" and "offset" contain the (combined) stride and offset
  82  * found so far and are NULL when "found" is not set.
  83  * If "want_offset" is not set, then "offset" remains NULL.
  84  */
  85 struct isl_detect_stride_data {
  86         int pos;
  87         int want_offset;
  88         int found;
  89         isl_val *stride;
  90         isl_aff *offset;
  91 };
  92
  93 /* Set the stride and offset of data->pos to the given
  94  * value and expression.
  95  *
  96  * If we had already found a stride before, then the two strides
  97  * are combined into a single stride.
  98  *
  99  * In particular, if the new stride information is of the form
 100  *
 101  *      i = f + s (...)
 102  *
 103  * and the old stride information is of the form
 104  *
 105  *      i = f2 + s2 (...)
 106  *
 107  * then we compute the extended gcd of s and s2
 108  *
 109  *      a s + b s2 = g,
 110  *
 111  * with g = gcd(s,s2), multiply the first equation with t1 = b s2/g
 112  * and the second with t2 = a s1/g.
 113  * This results in
 114  *
 115  *      i = (b s2 + a s1)/g i = t1 f + t2 f2 + (s s2)/g (...)
 116  *
 117  * so that t1 f + t2 f2 is the combined offset and (s s2)/g = lcm(s,s2)
 118  * is the combined stride.
 119  */
 120 static isl_stat set_stride(struct isl_detect_stride_data *data,
 121         __isl_take isl_val *stride, __isl_take isl_aff *offset)
 122 {
 123         int pos;
 124
 125         if (!stride || !offset)
 126                 goto error;
 127
 128         pos = data->pos;
 129
 130         if (data->found) {
 131                 isl_val *stride2, *a, *b, *g;
 132                 isl_aff *offset2;
 133
 134                 stride2 = data->stride;
 135                 g = isl_val_gcdext(isl_val_copy(stride), isl_val_copy(stride2),
 136                                         &a, &b);
 137                 a = isl_val_mul(a, isl_val_copy(stride));
 138                 a = isl_val_div(a, isl_val_copy(g));
 139                 stride2 = isl_val_div(stride2, g);
 140                 b = isl_val_mul(b, isl_val_copy(stride2));
 141                 stride = isl_val_mul(stride, stride2);
 142
 143                 if (!data->want_offset) {
 144                         isl_val_free(a);
 145                         isl_val_free(b);
 146                 } else {
 147                         offset2 = data->offset;
 148                         offset2 = isl_aff_scale_val(offset2, a);
 149                         offset = isl_aff_scale_val(offset, b);
 150                         offset = isl_aff_add(offset, offset2);
 151                 }
 152         }
 153
 154         data->found = 1;
 155         data->stride = stride;
 156         if (data->want_offset)
 157                 data->offset = offset;
 158         else
 159                 isl_aff_free(offset);
 160         if (!data->stride || (data->want_offset && !data->offset))
 161                 return isl_stat_error;
 162
 163         return isl_stat_ok;
 164 error:
 165         isl_val_free(stride);
 166         isl_aff_free(offset);
 167         return isl_stat_error;
 168 }
 169
 170 /* Check if constraint "c" imposes any stride on dimension data->pos
 171  * and, if so, update the stride information in "data".
 172  *
 173  * In order to impose a stride on the dimension, "c" needs to be an equality
 174  * and it needs to involve the dimension.  Note that "c" may also be
 175  * a div constraint and thus an inequality that we cannot use.
 176  *
 177  * Let c be of the form
 178  *
 179  *      h(p) + g * v * i + g * stride * f(alpha) = 0
 180  *
 181  * with h(p) an expression in terms of the parameters and other dimensions
 182  * and f(alpha) an expression in terms of the existentially quantified
 183  * variables.
 184  *
 185  * If "stride" is not zero and not one, then it represents a non-trivial stride
 186  * on "i".  We compute a and b such that
 187  *
 188  *      a v + b stride = 1
 189  *
 190  * We have
 191  *
 192  *      g v i = -h(p) + g stride f(alpha)
 193  *
 194  *      a g v i = -a h(p) + g stride f(alpha)
 195  *
 196  *      a g v i + b g stride i = -a h(p) + g stride * (...)
 197  *
 198  *      g i = -a h(p) + g stride * (...)
 199  *
 200  *      i = -a h(p)/g + stride * (...)
 201  *
 202  * The expression "-a h(p)/g" can therefore be used as offset.
 203  */
 204 static isl_stat detect_stride(__isl_take isl_constraint *c, void *user)
 205 {
 206         struct isl_detect_stride_data *data = user;
 207         int i, n_div;
 208         isl_ctx *ctx;
 209         isl_stat r = isl_stat_ok;
 210         isl_val *v, *stride, *m;
 211         isl_bool is_eq, relevant, has_stride;
 212
 213         is_eq = isl_constraint_is_equality(c);
 214         relevant = isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1);
 215         if (is_eq < 0 || relevant < 0)
 216                 goto error;
 217         if (!is_eq || !relevant) {
 218                 isl_constraint_free(c);
 219                 return isl_stat_ok;
 220         }
 221
 222         ctx = isl_constraint_get_ctx(c);
 223         stride = isl_val_zero(ctx);
 224         n_div = isl_constraint_dim(c, isl_dim_div);
 225         for (i = 0; i < n_div; ++i) {
 226                 v = isl_constraint_get_coefficient_val(c, isl_dim_div, i);
 227                 stride = isl_val_gcd(stride, v);
 228         }
 229
 230         v = isl_constraint_get_coefficient_val(c, isl_dim_set, data->pos);
 231         m = isl_val_gcd(isl_val_copy(stride), isl_val_copy(v));
 232         stride = isl_val_div(stride, isl_val_copy(m));
 233         v = isl_val_div(v, isl_val_copy(m));
 234
 235         has_stride = isl_val_gt_si(stride, 1);
 236         if (has_stride >= 0 && has_stride) {
 237                 isl_aff *aff;
 238                 isl_val *gcd, *a, *b;
 239
 240                 gcd = isl_val_gcdext(v, isl_val_copy(stride), &a, &b);
 241                 isl_val_free(gcd);
 242                 isl_val_free(b);
 243
 244                 aff = isl_constraint_get_aff(c);
 245                 for (i = 0; i < n_div; ++i)
 246                         aff = isl_aff_set_coefficient_si(aff,
 247                                                          isl_dim_div, i, 0);
 248                 aff = isl_aff_set_coefficient_si(aff, isl_dim_in, data->pos, 0);
 249                 a = isl_val_neg(a);
 250                 aff = isl_aff_scale_val(aff, a);
 251                 aff = isl_aff_scale_down_val(aff, m);
 252                 r = set_stride(data, stride, aff);
 253         } else {
 254                 isl_val_free(stride);
 255                 isl_val_free(m);
 256                 isl_val_free(v);
 257         }
 258
 259         isl_constraint_free(c);
 260         if (has_stride < 0)
 261                 return isl_stat_error;
 262         return r;
 263 error:
 264         isl_constraint_free(c);
 265         return isl_stat_error;
 266 }
 267
 268 /* Check if the constraints in "set" imply any stride on set dimension "pos" and
 269  * store the results in data->stride and data->offset.
 270  *
 271  * In particular, compute the affine hull and then check if
 272  * any of the constraints in the hull impose any stride on the dimension.
 273  * If no such constraint can be found, then the offset is taken
 274  * to be the zero expression and the stride is taken to be one.
 275  */
 276 static void set_detect_stride(__isl_keep isl_set *set, int pos,
 277         struct isl_detect_stride_data *data)
 278 {
 279         isl_basic_set *hull;
 280
 281         hull = isl_set_affine_hull(isl_set_copy(set));
 282
 283         data->pos = pos;
 284         data->found = 0;
 285         data->stride = NULL;
 286         data->offset = NULL;
 287         if (isl_basic_set_foreach_constraint(hull, &detect_stride, data) < 0)
 288                 goto error;
 289
 290         if (!data->found) {
 291                 data->stride = isl_val_one(isl_set_get_ctx(set));
 292                 if (data->want_offset) {
 293                         isl_space *space;
 294                         isl_local_space *ls;
 295
 296                         space = isl_set_get_space(set);
 297                         ls = isl_local_space_from_space(space);
 298                         data->offset = isl_aff_zero_on_domain(ls);
 299                 }
 300         }
 301         isl_basic_set_free(hull);
 302         return;
 303 error:
 304         isl_basic_set_free(hull);
 305         data->stride = isl_val_free(data->stride);
 306         data->offset = isl_aff_free(data->offset);
 307 }
 308
 309 /* Check if the constraints in "set" imply any stride on set dimension "pos" and
 310  * return the results in the form of an offset and a stride.
 311  */
 312 __isl_give isl_stride_info *isl_set_get_stride_info(__isl_keep isl_set *set,
 313         int pos)
 314 {
 315         struct isl_detect_stride_data data;
 316
 317         data.want_offset = 1;
 318         set_detect_stride(set, pos, &data);
 319
 320         return isl_stride_info_alloc(data.stride, data.offset);
 321 }
 322
 323 /* Check if the constraints in "set" imply any stride on set dimension "pos" and
 324  * return this stride.
 325  */
 326 __isl_give isl_val *isl_set_get_stride(__isl_keep isl_set *set, int pos)
 327 {
 328         struct isl_detect_stride_data data;
 329
 330         data.want_offset = 0;
 331         set_detect_stride(set, pos, &data);
 332
 333         return data.stride;
 334 }