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