/* * Copyright 2010-2011 INRIA Saclay * Copyright 2012-2013 Ecole Normale Superieure * * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, * 91893 Orsay, France * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France */ #include <isl/val.h> #include <isl/space.h> #include <isl_map_private.h> #include <isl_aff_private.h> #include <isl/constraint.h> #include <isl/ilp.h> #include <isl/fixed_box.h> /* Representation of a box of fixed size containing the elements * [offset, offset + size). * "size" lives in the target space of "offset". * * If any of the "offsets" is NaN, then the object represents * the failure of finding a fixed-size box. */ struct isl_fixed_box { … }; /* Free "box" and return NULL. */ __isl_null isl_fixed_box *isl_fixed_box_free(__isl_take isl_fixed_box *box) { … } /* Construct an isl_fixed_box with the given offset and size. */ static __isl_give isl_fixed_box *isl_fixed_box_alloc( __isl_take isl_multi_aff *offset, __isl_take isl_multi_val *size) { … } /* Construct an initial isl_fixed_box with zero offsets * in the given space and zero corresponding sizes. */ static __isl_give isl_fixed_box *isl_fixed_box_init( __isl_take isl_space *space) { … } /* Return a copy of "box". */ __isl_give isl_fixed_box *isl_fixed_box_copy(__isl_keep isl_fixed_box *box) { … } /* Replace the offset and size in direction "pos" by "offset" and "size" * (without checking whether "box" is a valid box). */ static __isl_give isl_fixed_box *isl_fixed_box_set_extent( __isl_take isl_fixed_box *box, int pos, __isl_keep isl_aff *offset, __isl_keep isl_val *size) { … } /* Replace the offset and size in direction "pos" by "offset" and "size", * if "box" is a valid box. */ static __isl_give isl_fixed_box *isl_fixed_box_set_valid_extent( __isl_take isl_fixed_box *box, int pos, __isl_keep isl_aff *offset, __isl_keep isl_val *size) { … } /* Replace "box" by an invalid box, by setting all offsets to NaN * (and all sizes to infinity). */ static __isl_give isl_fixed_box *isl_fixed_box_invalidate( __isl_take isl_fixed_box *box) { … } /* Project the domain of the fixed box onto its parameter space. * In particular, project out the domain of the offset. */ static __isl_give isl_fixed_box *isl_fixed_box_project_domain_on_params( __isl_take isl_fixed_box *box) { … } /* Return the isl_ctx to which "box" belongs. */ isl_ctx *isl_fixed_box_get_ctx(__isl_keep isl_fixed_box *box) { … } /* Return the space in which "box" lives. */ __isl_give isl_space *isl_fixed_box_get_space(__isl_keep isl_fixed_box *box) { … } /* Does "box" contain valid information? */ isl_bool isl_fixed_box_is_valid(__isl_keep isl_fixed_box *box) { … } /* Return the offsets of the box "box". */ __isl_give isl_multi_aff *isl_fixed_box_get_offset( __isl_keep isl_fixed_box *box) { … } /* Return the sizes of the box "box". */ __isl_give isl_multi_val *isl_fixed_box_get_size(__isl_keep isl_fixed_box *box) { … } /* Data used in set_dim_extent and compute_size_in_direction. * * "bset" is a wrapped copy of the basic map that has the selected * output dimension as range. * "pos" is the position of the variable representing the output dimension, * i.e., the variable for which the size should be computed. This variable * is also the last variable in "bset". * "size" is the best size found so far * (infinity if no offset was found so far). * "offset" is the offset corresponding to the best size * (NULL if no offset was found so far). */ struct isl_size_info { … }; /* Is "c" a suitable bound on dimension "pos" for use as a lower bound * of a fixed-size range. * In particular, it needs to be a lower bound on "pos". * In order for the final offset not to be too complicated, * the constraint itself should also not involve any integer divisions. */ static isl_bool is_suitable_bound(__isl_keep isl_constraint *c, unsigned pos) { … } /* Given a constraint from the basic set describing the bounds on * an array index, check if it is a lower bound, say m i >= b(x), and, * if so, check whether the expression "i - ceil(b(x)/m) + 1" has a constant * upper bound. If so, and if this bound is smaller than any bound * derived from earlier constraints, set the size to this bound on * the expression and the lower bound to ceil(b(x)/m). */ static isl_stat compute_size_in_direction(__isl_take isl_constraint *c, void *user) { … } /* Look for a fixed-size range of values for the output dimension "pos" * of "map", by looking for a lower-bound expression in the parameters * and input dimensions such that the range of the output dimension * is a constant shifted by this expression. * * In particular, look through the explicit lower bounds on the output dimension * for candidate expressions and pick the one that results in the smallest size. * Initialize the size with infinity and if no better size is found * then invalidate the box. Otherwise, set the offset and size * in the given direction by those that correspond to the smallest size. * * Note that while evaluating the size corresponding to a lower bound, * an affine expression is constructed from the lower bound. * This lower bound may therefore not have any unknown local variables. * Eliminate any unknown local variables up front. * No such restriction needs to be imposed on the set over which * the size is computed. */ static __isl_give isl_fixed_box *set_dim_extent(__isl_take isl_fixed_box *box, __isl_keep isl_map *map, int pos) { … } /* Try and construct a fixed-size rectangular box with an offset * in terms of the domain of "map" that contains the range of "map". * If no such box can be constructed, then return an invalidated box, * i.e., one where isl_fixed_box_is_valid returns false. * * Iterate over the dimensions in the range * setting the corresponding offset and extent. */ __isl_give isl_fixed_box *isl_map_get_range_simple_fixed_box_hull( __isl_keep isl_map *map) { … } /* Compute a fixed box from "set" using "map_box" by treating it as a map * with a zero-dimensional domain and * project out the domain again from the result. */ static __isl_give isl_fixed_box *fixed_box_as_map(__isl_keep isl_set *set, __isl_give isl_fixed_box *(*map_box)(__isl_keep isl_map *map)) { … } /* Try and construct a fixed-size rectangular box with an offset * in terms of the parameters of "set" that contains "set". * If no such box can be constructed, then return an invalidated box, * i.e., one where isl_fixed_box_is_valid returns false. * * Compute the box using isl_map_get_range_simple_fixed_box_hull * by constructing a map from the set and * project out the domain again from the result. */ __isl_give isl_fixed_box *isl_set_get_simple_fixed_box_hull( __isl_keep isl_set *set) { … } /* Check whether the output elements lie on a rectangular lattice, * possibly depending on the parameters and the input dimensions. * Return a tile in this lattice. * If no stride information can be found, then return a tile of size 1 * (and offset 0). * * Obtain stride information in each output dimension separately and * combine the results. */ __isl_give isl_fixed_box *isl_map_get_range_lattice_tile( __isl_keep isl_map *map) { … } /* Check whether the elements lie on a rectangular lattice, * possibly depending on the parameters. * Return a tile in this lattice. * If no stride information can be found, then return a tile of size 1 * (and offset 0). * * Consider the set as a map with a zero-dimensional domain and * obtain a lattice tile of that map. */ __isl_give isl_fixed_box *isl_set_get_lattice_tile(__isl_keep isl_set *set) { … } #undef BASE #define BASE … #include "print_yaml_field_templ.c" #undef BASE #define BASE … #include "print_yaml_field_templ.c" /* Print the information contained in "box" to "p". * The information is printed as a YAML document. */ __isl_give isl_printer *isl_printer_print_fixed_box( __isl_take isl_printer *p, __isl_keep isl_fixed_box *box) { … } #undef BASE #define BASE … #include <print_templ_yaml.c>
Codebase Browser
llvm