390 lines · c
1/*2 * Copyright 2012-2013 Ecole Normale Superieure3 *4 * Use of this software is governed by the MIT license5 *6 * Written by Sven Verdoolaege,7 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France8 */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 to18 * "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 offset105 * 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 given117 * value and expression.118 *119 * If we had already found a stride before, then the two strides120 * are combined into a single stride.121 *122 * In particular, if the new stride information is of the form123 *124 * i = f + s (...)125 *126 * and the old stride information is of the form127 *128 * i = f2 + s2 (...)129 *130 * then we compute the extended gcd of s and s2131 *132 * a s + b s2 = g,133 *134 * with g = gcd(s,s2), multiply the first equation with t1 = b s2/g135 * and the second with t2 = a s1/g.136 * This results in137 *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 else178 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->pos190 * 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 equality193 * and it needs to involve the dimension. Note that "c" may also be194 * a div constraint and thus an inequality that we cannot use.195 *196 * Let c be of the form197 *198 * h(p) + g * v * i + g * stride * f(alpha) = 0199 *200 * with h(p) an expression in terms of the parameters and other dimensions201 * and f(alpha) an expression in terms of the existentially quantified202 * variables.203 *204 * If "stride" is not zero and not one, then it represents a non-trivial stride205 * on "i". We compute a and b such that206 *207 * a v + b stride = 1208 *209 * We have210 *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" and292 * store the results in data->stride and data->offset.293 *294 * In particular, compute the affine hull and then check if295 * 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 taken297 * 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" and333 * 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" and347 * 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, and361 * 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 and364 * the single output dimension such that it be passed to365 * isl_set_get_stride_info and convert the result back to366 * 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