/* * Copyright 2012-2013 Ecole Normale Superieure * * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France */ #include <isl/val.h> #include <isl_map_private.h> #include <isl_aff_private.h> #include <isl/constraint.h> #include <isl/set.h> /* Stride information about a specific set dimension. * The values of the set dimension are equal to * "offset" plus a multiple of "stride". */ struct isl_stride_info { … }; /* Return the ctx to which "si" belongs. */ isl_ctx *isl_stride_info_get_ctx(__isl_keep isl_stride_info *si) { … } /* Free "si" and return NULL. */ __isl_null isl_stride_info *isl_stride_info_free( __isl_take isl_stride_info *si) { … } /* Construct an isl_stride_info object with given offset and stride. */ __isl_give isl_stride_info *isl_stride_info_alloc( __isl_take isl_val *stride, __isl_take isl_aff *offset) { … } /* Make a copy of "si" and return it. */ __isl_give isl_stride_info *isl_stride_info_copy( __isl_keep isl_stride_info *si) { … } /* Return the stride of "si". */ __isl_give isl_val *isl_stride_info_get_stride(__isl_keep isl_stride_info *si) { … } /* Return the offset of "si". */ __isl_give isl_aff *isl_stride_info_get_offset(__isl_keep isl_stride_info *si) { … } /* Information used inside detect_stride. * * "pos" is the set dimension at which the stride is being determined. * "want_offset" is set if the offset should be computed. * "found" is set if some stride was found already. * "stride" and "offset" contain the (combined) stride and offset * found so far and are NULL when "found" is not set. * If "want_offset" is not set, then "offset" remains NULL. */ struct isl_detect_stride_data { … }; /* Set the stride and offset of data->pos to the given * value and expression. * * If we had already found a stride before, then the two strides * are combined into a single stride. * * In particular, if the new stride information is of the form * * i = f + s (...) * * and the old stride information is of the form * * i = f2 + s2 (...) * * then we compute the extended gcd of s and s2 * * a s + b s2 = g, * * with g = gcd(s,s2), multiply the first equation with t1 = b s2/g * and the second with t2 = a s1/g. * This results in * * i = (b s2 + a s1)/g i = t1 f + t2 f2 + (s s2)/g (...) * * so that t1 f + t2 f2 is the combined offset and (s s2)/g = lcm(s,s2) * is the combined stride. */ static isl_stat set_stride(struct isl_detect_stride_data *data, __isl_take isl_val *stride, __isl_take isl_aff *offset) { … } /* Check if constraint "c" imposes any stride on dimension data->pos * and, if so, update the stride information in "data". * * In order to impose a stride on the dimension, "c" needs to be an equality * and it needs to involve the dimension. Note that "c" may also be * a div constraint and thus an inequality that we cannot use. * * Let c be of the form * * h(p) + g * v * i + g * stride * f(alpha) = 0 * * with h(p) an expression in terms of the parameters and other dimensions * and f(alpha) an expression in terms of the existentially quantified * variables. * * If "stride" is not zero and not one, then it represents a non-trivial stride * on "i". We compute a and b such that * * a v + b stride = 1 * * We have * * g v i = -h(p) + g stride f(alpha) * * a g v i = -a h(p) + g stride f(alpha) * * a g v i + b g stride i = -a h(p) + g stride * (...) * * g i = -a h(p) + g stride * (...) * * i = -a h(p)/g + stride * (...) * * The expression "-a h(p)/g" can therefore be used as offset. */ static isl_stat detect_stride(__isl_take isl_constraint *c, void *user) { … } /* Check if the constraints in "set" imply any stride on set dimension "pos" and * store the results in data->stride and data->offset. * * In particular, compute the affine hull and then check if * any of the constraints in the hull impose any stride on the dimension. * If no such constraint can be found, then the offset is taken * to be the zero expression and the stride is taken to be one. */ static void set_detect_stride(__isl_keep isl_set *set, int pos, struct isl_detect_stride_data *data) { … } /* Check if the constraints in "set" imply any stride on set dimension "pos" and * return the results in the form of an offset and a stride. */ __isl_give isl_stride_info *isl_set_get_stride_info(__isl_keep isl_set *set, int pos) { … } /* Check if the constraints in "set" imply any stride on set dimension "pos" and * return this stride. */ __isl_give isl_val *isl_set_get_stride(__isl_keep isl_set *set, int pos) { … } /* Check if the constraints in "map" imply any stride on output dimension "pos", * independently of any other output dimensions, and * return the results in the form of an offset and a stride. * * Convert the input to a set with only the input dimensions and * the single output dimension such that it be passed to * isl_set_get_stride_info and convert the result back to * an expression defined over the domain of "map". */ __isl_give isl_stride_info *isl_map_get_range_stride_info( __isl_keep isl_map *map, int pos) { … }
Codebase Browser
llvm