| File: | build/source/polly/lib/External/isl/isl_stride.c |
| Warning: | line 151, column 2 Value stored to 'pos' is never read |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 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((void*)0); |
| 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((void*)0); |
| 42 | isl_val_free(si->stride); |
| 43 | isl_aff_free(si->offset); |
| 44 | free(si); |
| 45 | return NULL((void*)0); |
| 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)((struct isl_stride_info *)isl_malloc_or_die(isl_val_get_ctx( stride), sizeof(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((void*)0); |
| 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((void*)0); |
| 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((void*)0); |
| 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((void*)0); |
| 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; |
Value stored to 'pos' is never read | |
| 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_setisl_map *set, int pos, |
| 304 | struct isl_detect_stride_data *data) |
| 305 | { |
| 306 | isl_basic_setisl_basic_map *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((void*)0); |
| 313 | data->offset = NULL((void*)0); |
| 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_setisl_map *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_setisl_map *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_setisl_map *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((void*)0); |
| 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((void*)0); |
| 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 | } |