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