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
 212         if (!isl_constraint_is_equality(c) ||
 213             !isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1)) {
 214                 isl_constraint_free(c);
 215                 return isl_stat_ok;
 216         }
 217
 218         ctx = isl_constraint_get_ctx(c);
 219         stride = isl_val_zero(ctx);
 220         n_div = isl_constraint_dim(c, isl_dim_div);
 221         for (i = 0; i < n_div; ++i) {
 222                 v = isl_constraint_get_coefficient_val(c, isl_dim_div, i);
 223                 stride = isl_val_gcd(stride, v);
 224         }
 225
 226         v = isl_constraint_get_coefficient_val(c, isl_dim_set, data->pos);
 227         m = isl_val_gcd(isl_val_copy(stride), isl_val_copy(v));
 228         stride = isl_val_div(stride, isl_val_copy(m));
 229         v = isl_val_div(v, isl_val_copy(m));
 230
 231         if (!isl_val_is_zero(stride) && !isl_val_is_one(stride)) {
 232                 isl_aff *aff;
 233                 isl_val *gcd, *a, *b;
 234
 235                 gcd = isl_val_gcdext(v, isl_val_copy(stride), &a, &b);
 236                 isl_val_free(gcd);
 237                 isl_val_free(b);
 238
 239                 aff = isl_constraint_get_aff(c);
 240                 for (i = 0; i < n_div; ++i)
 241                         aff = isl_aff_set_coefficient_si(aff,
 242                                                          isl_dim_div, i, 0);
 243                 aff = isl_aff_set_coefficient_si(aff, isl_dim_in, data->pos, 0);
 244                 a = isl_val_neg(a);
 245                 aff = isl_aff_scale_val(aff, a);
 246                 aff = isl_aff_scale_down_val(aff, m);
 247                 r = set_stride(data, stride, aff);
 248         } else {
 249                 isl_val_free(stride);
 250                 isl_val_free(m);
 251                 isl_val_free(v);
 252         }
 253
 254         isl_constraint_free(c);
 255         return r;
 256 }
 257
 258 /* Check if the constraints in "set" imply any stride on set dimension "pos" and
 259  * store the results in data->stride and data->offset.
 260  *
 261  * In particular, compute the affine hull and then check if
 262  * any of the constraints in the hull impose any stride on the dimension.
 263  * If no such constraint can be found, then the offset is taken
 264  * to be the zero expression and the stride is taken to be one.
 265  */
 266 static void set_detect_stride(__isl_keep isl_set *set, int pos,
 267         struct isl_detect_stride_data *data)
 268 {
 269         isl_basic_set *hull;
 270
 271         hull = isl_set_affine_hull(isl_set_copy(set));
 272
 273         data->pos = pos;
 274         data->found = 0;
 275         data->stride = NULL;
 276         data->offset = NULL;
 277         if (isl_basic_set_foreach_constraint(hull, &detect_stride, data) < 0)
 278                 goto error;
 279
 280         if (!data->found) {
 281                 data->stride = isl_val_one(isl_set_get_ctx(set));
 282                 if (data->want_offset) {
 283                         isl_space *space;
 284                         isl_local_space *ls;
 285
 286                         space = isl_set_get_space(set);
 287                         ls = isl_local_space_from_space(space);
 288                         data->offset = isl_aff_zero_on_domain(ls);
 289                 }
 290         }
 291         isl_basic_set_free(hull);
 292         return;
 293 error:
 294         isl_basic_set_free(hull);
 295         data->stride = isl_val_free(data->stride);
 296         data->offset = isl_aff_free(data->offset);
 297 }
 298
 299 /* Check if the constraints in "set" imply any stride on set dimension "pos" and
 300  * return the results in the form of an offset and a stride.
 301  */
 302 __isl_give isl_stride_info *isl_set_get_stride_info(__isl_keep isl_set *set,
 303         int pos)
 304 {
 305         struct isl_detect_stride_data data;
 306
 307         data.want_offset = 1;
 308         set_detect_stride(set, pos, &data);
 309
 310         return isl_stride_info_alloc(data.stride, data.offset);
 311 }
 312
 313 /* Check if the constraints in "set" imply any stride on set dimension "pos" and
 314  * return this stride.
 315  */
 316 __isl_give isl_val *isl_set_get_stride(__isl_keep isl_set *set, int pos)
 317 {
 318         struct isl_detect_stride_data data;
 319
 320         data.want_offset = 0;
 321         set_detect_stride(set, pos, &data);
 322
 323         return data.stride;
 324 }