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 */ 20struct isl_stride_info { 21 isl_val *stride; 22 isl_aff *offset; 23}; 24 25/* Return the ctx to which "si" belongs. 26 */ 27isl_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; 63error: 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 */ 108struct 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 */ 143static 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; 183error: 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 */ 223static 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; 286error: 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 */ 299static 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; 326error: 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} 390