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         if (!stride || !offset)
 147                 goto error;
 148
 149         if (data->found) {
 150                 isl_val *stride2, *a, *b, *g;
 151                 isl_aff *offset2;
 152
 153                 stride2 = data->stride;
 154                 g = isl_val_gcdext(isl_val_copy(stride), isl_val_copy(stride2),
 155                                         &a, &b);
 156                 a = isl_val_mul(a, isl_val_copy(stride));
 157                 a = isl_val_div(a, isl_val_copy(g));
 158                 stride2 = isl_val_div(stride2, g);
 159                 b = isl_val_mul(b, isl_val_copy(stride2));
 160                 stride = isl_val_mul(stride, stride2);
 161
 162                 if (!data->want_offset) {
 163                         isl_val_free(a);
 164                         isl_val_free(b);
 165                 } else {
 166                         offset2 = data->offset;
 167                         offset2 = isl_aff_scale_val(offset2, a);
 168                         offset = isl_aff_scale_val(offset, b);
 169                         offset = isl_aff_add(offset, offset2);
 170                 }
 171         }
 172
 173         data->found = 1;
 174         data->stride = stride;
 175         if (data->want_offset)
 176                 data->offset = offset;
 177         else
 178                 isl_aff_free(offset);
 179         if (!data->stride || (data->want_offset && !data->offset))
 180                 return isl_stat_error;
 181
 182         return isl_stat_ok;
 183 error:
 184         isl_val_free(stride);
 185         isl_aff_free(offset);
 186         return isl_stat_error;
 187 }
 188
 189 /* Check if constraint "c" imposes any stride on dimension data->pos
 190  * and, if so, update the stride information in "data".
 191  *
 192  * In order to impose a stride on the dimension, "c" needs to be an equality
 193  * and it needs to involve the dimension.  Note that "c" may also be
 194  * a div constraint and thus an inequality that we cannot use.
 195  *
 196  * Let c be of the form
 197  *
 198  *      h(p) + g * v * i + g * stride * f(alpha) = 0
 199  *
 200  * with h(p) an expression in terms of the parameters and other dimensions
 201  * and f(alpha) an expression in terms of the existentially quantified
 202  * variables.
 203  *
 204  * If "stride" is not zero and not one, then it represents a non-trivial stride
 205  * on "i".  We compute a and b such that
 206  *
 207  *      a v + b stride = 1
 208  *
 209  * We have
 210  *
 211  *      g v i = -h(p) + g stride f(alpha)
 212  *
 213  *      a g v i = -a h(p) + g stride f(alpha)
 214  *
 215  *      a g v i + b g stride i = -a h(p) + g stride * (...)
 216  *
 217  *      g i = -a h(p) + g stride * (...)
 218  *
 219  *      i = -a h(p)/g + stride * (...)
 220  *
 221  * The expression "-a h(p)/g" can therefore be used as offset.
 222  */
 223 static isl_stat detect_stride(__isl_take isl_constraint *c, void *user)
 224 {
 225         struct isl_detect_stride_data *data = user;
 226         int i;
 227         isl_size n_div;
 228         isl_ctx *ctx;
 229         isl_stat r = isl_stat_ok;
 230         isl_val *v, *stride, *m;
 231         isl_bool is_eq, relevant, has_stride;
 232
 233         is_eq = isl_constraint_is_equality(c);
 234         relevant = isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1);
 235         if (is_eq < 0 || relevant < 0)
 236                 goto error;
 237         if (!is_eq || !relevant) {
 238                 isl_constraint_free(c);
 239                 return isl_stat_ok;
 240         }
 241
 242         n_div = isl_constraint_dim(c, isl_dim_div);
 243         if (n_div < 0)
 244                 goto error;
 245         ctx = isl_constraint_get_ctx(c);
 246         stride = isl_val_zero(ctx);
 247         for (i = 0; i < n_div; ++i) {
 248                 v = isl_constraint_get_coefficient_val(c, isl_dim_div, i);
 249                 stride = isl_val_gcd(stride, v);
 250         }
 251
 252         v = isl_constraint_get_coefficient_val(c, isl_dim_set, data->pos);
 253         m = isl_val_gcd(isl_val_copy(stride), isl_val_copy(v));
 254         stride = isl_val_div(stride, isl_val_copy(m));
 255         v = isl_val_div(v, isl_val_copy(m));
 256
 257         has_stride = isl_val_gt_si(stride, 1);
 258         if (has_stride >= 0 && has_stride) {
 259                 isl_aff *aff;
 260                 isl_val *gcd, *a, *b;
 261
 262                 gcd = isl_val_gcdext(v, isl_val_copy(stride), &a, &b);
 263                 isl_val_free(gcd);
 264                 isl_val_free(b);
 265
 266                 aff = isl_constraint_get_aff(c);
 267                 for (i = 0; i < n_div; ++i)
 268                         aff = isl_aff_set_coefficient_si(aff,
 269                                                          isl_dim_div, i, 0);
 270                 aff = isl_aff_set_coefficient_si(aff, isl_dim_in, data->pos, 0);
 271                 aff = isl_aff_remove_unused_divs(aff);
 272                 a = isl_val_neg(a);
 273                 aff = isl_aff_scale_val(aff, a);
 274                 aff = isl_aff_scale_down_val(aff, m);
 275                 r = set_stride(data, stride, aff);
 276         } else {
 277                 isl_val_free(stride);
 278                 isl_val_free(m);
 279                 isl_val_free(v);
 280         }
 281
 282         isl_constraint_free(c);
 283         if (has_stride < 0)
 284                 return isl_stat_error;
 285         return r;
 286 error:
 287         isl_constraint_free(c);
 288         return isl_stat_error;
 289 }
 290
 291 /* Check if the constraints in "set" imply any stride on set dimension "pos" and
 292  * store the results in data->stride and data->offset.
 293  *
 294  * In particular, compute the affine hull and then check if
 295  * any of the constraints in the hull impose any stride on the dimension.
 296  * If no such constraint can be found, then the offset is taken
 297  * to be the zero expression and the stride is taken to be one.
 298  */
 299 static void set_detect_stride(__isl_keep isl_set *set, int pos,
 300         struct isl_detect_stride_data *data)
 301 {
 302         isl_basic_set *hull;
 303
 304         hull = isl_set_affine_hull(isl_set_copy(set));
 305
 306         data->pos = pos;
 307         data->found = 0;
 308         data->stride = NULL;
 309         data->offset = NULL;
 310         if (isl_basic_set_foreach_constraint(hull, &detect_stride, data) < 0)
 311                 goto error;
 312
 313         if (!data->found) {
 314                 data->stride = isl_val_one(isl_set_get_ctx(set));
 315                 if (data->want_offset) {
 316                         isl_space *space;
 317                         isl_local_space *ls;
 318
 319                         space = isl_set_get_space(set);
 320                         ls = isl_local_space_from_space(space);
 321                         data->offset = isl_aff_zero_on_domain(ls);
 322                 }
 323         }
 324         isl_basic_set_free(hull);
 325         return;
 326 error:
 327         isl_basic_set_free(hull);
 328         data->stride = isl_val_free(data->stride);
 329         data->offset = isl_aff_free(data->offset);
 330 }
 331
 332 /* Check if the constraints in "set" imply any stride on set dimension "pos" and
 333  * return the results in the form of an offset and a stride.
 334  */
 335 __isl_give isl_stride_info *isl_set_get_stride_info(__isl_keep isl_set *set,
 336         int pos)
 337 {
 338         struct isl_detect_stride_data data;
 339
 340         data.want_offset = 1;
 341         set_detect_stride(set, pos, &data);
 342
 343         return isl_stride_info_alloc(data.stride, data.offset);
 344 }
 345
 346 /* Check if the constraints in "set" imply any stride on set dimension "pos" and
 347  * return this stride.
 348  */
 349 __isl_give isl_val *isl_set_get_stride(__isl_keep isl_set *set, int pos)
 350 {
 351         struct isl_detect_stride_data data;
 352
 353         data.want_offset = 0;
 354         set_detect_stride(set, pos, &data);
 355
 356         return data.stride;
 357 }
 358
 359 /* Check if the constraints in "map" imply any stride on output dimension "pos",
 360  * independently of any other output dimensions, and
 361  * return the results in the form of an offset and a stride.
 362  *
 363  * Convert the input to a set with only the input dimensions and
 364  * the single output dimension such that it be passed to
 365  * isl_set_get_stride_info and convert the result back to
 366  * an expression defined over the domain of "map".
 367  */
 368 __isl_give isl_stride_info *isl_map_get_range_stride_info(
 369         __isl_keep isl_map *map, int pos)
 370 {
 371         isl_stride_info *si;
 372         isl_set *set;
 373         isl_size n_in;
 374
 375         n_in = isl_map_dim(map, isl_dim_in);
 376         if (n_in < 0)
 377                 return NULL;
 378         map = isl_map_copy(map);
 379         map = isl_map_project_onto(map, isl_dim_out, pos, 1);
 380         set = isl_map_wrap(map);
 381         si = isl_set_get_stride_info(set, n_in);
 382         isl_set_free(set);
 383         if (!si)
 384                 return NULL;
 385         si->offset = isl_aff_domain_factor_domain(si->offset);
 386         if (!si->offset)
 387                 return isl_stride_info_free(si);
 388         return si;
 389 }