isl_ast_build_private.h

   1 #ifndef ISL_AST_BUILD_PRIVATE_H
   2 #define ISL_AST_BUILD_PRIVATE_H
   3
   4 #include <isl/aff.h>
   5 #include <isl/ast.h>
   6 #include <isl/ast_build.h>
   7 #include <isl/set.h>
   8 #include <isl/list.h>
   9
  10 enum isl_ast_build_domain_type {
  11         atomic,
  12         unroll,
  13         separate
  14 };
  15
  16 /* An isl_ast_build represents the context in which AST is being
  17  * generated.  That is, it (mostly) contains information about outer
  18  * loops that can be used to simplify inner loops.
  19  *
  20  * "domain" represents constraints on the internal schedule domain,
  21  * corresponding to the context of the AST generation and the constraints
  22  * implied by the loops that have already been generated.
  23  * When an isl_ast_build is first created, outside any AST generation,
  24  * the domain is typically a parameter set.  It is only when a AST
  25  * generation phase is initiated that the domain of the isl_ast_build
  26  * is changed to refer to the internal schedule domain.
  27  * The domain then lives in a space of the form
  28  *
  29  *      S
  30  *
  31  *  or
  32  *
  33  *      [O -> S]
  34  *
  35  * O represents the loops generated in outer AST generations.
  36  * S represents the loops (both generated and to be generated)
  37  * of the current AST generation.
  38  * Both include eliminated loops.
  39  * "domain" is expected not to have any unknown divs because
  40  * it is used as the context argument in a call to isl_basic_set_gist
  41  * in isl_ast_build_compute_gist_basic_set.
  42  *
  43  * "depth" is equal to the number of loops that have already
  44  * been generated (including those in outer AST generations).
  45  * "outer_pos" is equal to the number of loops in outer AST generations.
  46  *
  47  * "generated" is a superset of "domain" corresponding to those
  48  * constraints that were either given by the user or that have
  49  * effectively been generated (as bounds on a for loop).
  50  *
  51  * "pending" is a superset of "domain" corresponding to the constraints
  52  * that still need to be generated (as guards), but that may end up
  53  * not getting generated if they are implied by any constraints
  54  * enforced by inner loops.
  55  *
  56  * "strides" contains the stride of each loop.  The number of elements
  57  * is equal to the number of dimensions in "domain".
  58  * "offsets" constains the offsets of strided loops.  If s is the stride
  59  * for a given dimension and f is the corresponding offset, then the
  60  * dimension takes on values
  61  *
  62  *      f + s a
  63  *
  64  * with a an integer.  For non-strided loops, the offset is zero.
  65  *
  66  * "iterators" contains the loop iterators of both generated and
  67  * to be generated loops.  The number of elements is at least as
  68  * large as the dimension of the internal schedule domain.  The
  69  * number may be larger, in which case the additional ids can be
  70  * used in a nested AST generation should the schedule be non-injective.
  71  *
  72  * "values" lives in the space
  73  *
  74  *      [O -> S] -> [O -> S]            (or S -> S)
  75  *
  76  * and expresses (if possible) loop iterators in terms of parameters
  77  * and outer loop iterators.  If the value of a given loop iterator
  78  * cannot be expressed as an affine expression (either because the iterator
  79  * attains multiple values or because the single value is a piecewise
  80  * affine expression), then it is expressed in "values" as being equal
  81  * to itself.
  82  *
  83  * "value" is the value of the loop iterator at the current depth.
  84  * It is NULL if it has not been computed yet or if the value of the
  85  * given loop iterator cannot be expressed as a piecewise affine expression
  86  * (because the iterator attains multiple values).
  87  *
  88  * "schedule_map" maps the internal schedule domain to the external schedule
  89  * domain.  It may be NULL if it hasn't been computed yet.
  90  * See isl_ast_build_get_schedule_map_multi_aff.
  91  *
  92  * The "create_leaf" callback is called for every leaf in the generated AST.
  93  * The callback is responsible for creating the node to be placed at those
  94  * leaves.  If this callback is not set, then isl will generated user
  95  * nodes with call expressions corresponding to an element of the domain.
  96  *
  97  * The "at_each_domain" callback is called on every node created to represent
  98  * an element of the domain.  Each of these nodes is a user node
  99  * with as expression a call expression.
 100  *
 101  * The "before_each_for" callback is called on each for node before
 102  * its children have been created.
 103  *
 104  * The "after_each_for" callback is called on each for node after
 105  * its children have been created.
 106  *
 107  * "executed" contains the inverse schedule at this point
 108  * of the AST generation.
 109  * It is currently only used in isl_ast_build_get_schedule, which is
 110  * in turn only used by user code from within a callback.
 111  * The value is set right before we may be calling such a callback.
 112  *
 113  * "single_valued" is set if the current inverse schedule (which may or may
 114  * not be stored in "executed") is known to be single valued, specifically
 115  * an inverse schedule that was not (appeared not to be) single valued
 116  * is extended to a single valued inverse schedule.  This is mainly used
 117  * to avoid an infinite recursion when we fail to detect later on that
 118  * the extended inverse schedule is single valued.
 119  */
 120 struct isl_ast_build {
 121         int ref;
 122
 123         int outer_pos;
 124         int depth;
 125
 126         isl_id_list *iterators;
 127
 128         isl_set *domain;
 129         isl_set *generated;
 130         isl_set *pending;
 131         isl_multi_aff *values;
 132
 133         isl_pw_aff *value;
 134
 135         isl_vec *strides;
 136         isl_multi_aff *offsets;
 137
 138         isl_multi_aff *schedule_map;
 139
 140         isl_union_map *options;
 141
 142         __isl_give isl_ast_node *(*at_each_domain)(
 143                 __isl_take isl_ast_node *node,
 144                 __isl_keep isl_ast_build *build, void *user);
 145         void *at_each_domain_user;
 146
 147         __isl_give isl_id *(*before_each_for)(
 148                 __isl_keep isl_ast_build *context, void *user);
 149         void *before_each_for_user;
 150         __isl_give isl_ast_node *(*after_each_for)(
 151                 __isl_take isl_ast_node *node,
 152                 __isl_keep isl_ast_build *context, void *user);
 153         void *after_each_for_user;
 154
 155         __isl_give isl_ast_node *(*create_leaf)(
 156                 __isl_take isl_ast_build *build, void *user);
 157         void *create_leaf_user;
 158
 159         isl_union_map *executed;
 160         int single_valued;
 161 };
 162
 163 __isl_give isl_ast_build *isl_ast_build_clear_local_info(
 164         __isl_take isl_ast_build *build);
 165 __isl_give isl_ast_build *isl_ast_build_increase_depth(
 166         __isl_take isl_ast_build *build);
 167 int isl_ast_build_get_depth(__isl_keep isl_ast_build *build);
 168 __isl_give isl_space *isl_ast_build_get_space(
 169         __isl_keep isl_ast_build *build, int internal);
 170 __isl_give isl_ast_build *isl_ast_build_align_params(
 171         __isl_take isl_ast_build *build, __isl_take isl_space *model);
 172 __isl_give isl_ast_build *isl_ast_build_cow(
 173         __isl_take isl_ast_build *build);
 174 __isl_give isl_ast_build *isl_ast_build_insert_dim(
 175         __isl_take isl_ast_build *build, int pos);
 176 __isl_give isl_ast_build *isl_ast_build_scale_down(
 177         __isl_take isl_ast_build *build, isl_int m,
 178         __isl_take isl_union_map *umap);
 179 __isl_give isl_ast_build *isl_ast_build_product(
 180         __isl_take isl_ast_build *build, __isl_take isl_space *embedding);
 181 __isl_give isl_ast_build *isl_ast_build_set_loop_bounds(
 182         __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds);
 183 __isl_give isl_ast_build *isl_ast_build_detect_strides(
 184         __isl_take isl_ast_build *build, __isl_take isl_set *set);
 185 __isl_give isl_ast_build *isl_ast_build_include_stride(
 186         __isl_take isl_ast_build *build);
 187 __isl_give isl_ast_build *isl_ast_build_set_executed(
 188         __isl_take isl_ast_build *build,
 189         __isl_take isl_union_map *executed);
 190 __isl_give isl_ast_build *isl_ast_build_set_single_valued(
 191         __isl_take isl_ast_build *build, int sv);
 192 __isl_give isl_set *isl_ast_build_get_domain(
 193         __isl_keep isl_ast_build *build);
 194 __isl_give isl_ast_build *isl_ast_build_restrict_generated(
 195         __isl_take isl_ast_build *build, __isl_take isl_set *set);
 196 __isl_give isl_ast_build *isl_ast_build_restrict_pending(
 197         __isl_take isl_ast_build *build, __isl_take isl_set *set);
 198 __isl_give isl_ast_build *isl_ast_build_set_enforced(
 199         __isl_take isl_ast_build *build, __isl_take isl_basic_set *enforced);
 200 __isl_give int isl_ast_build_need_schedule_map(
 201         __isl_keep isl_ast_build *build);
 202 __isl_give isl_multi_aff *isl_ast_build_get_schedule_map_multi_aff(
 203         __isl_keep isl_ast_build *build);
 204 __isl_give isl_map *isl_ast_build_get_schedule_map(
 205         __isl_keep isl_ast_build *build);
 206 int isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build, int pos);
 207 int isl_ast_build_has_value(__isl_keep isl_ast_build *build);
 208 __isl_give isl_id *isl_ast_build_get_iterator_id(
 209         __isl_keep isl_ast_build *build, int pos);
 210
 211 __isl_give isl_basic_set *isl_ast_build_compute_gist_basic_set(
 212         __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset);
 213 __isl_give isl_set *isl_ast_build_compute_gist(
 214         __isl_keep isl_ast_build *build, __isl_take isl_set *set);
 215 __isl_give isl_map *isl_ast_build_compute_gist_map_domain(
 216         __isl_keep isl_ast_build *build, __isl_take isl_map *map);
 217 __isl_give isl_aff *isl_ast_build_compute_gist_aff(
 218         __isl_keep isl_ast_build *build, __isl_take isl_aff *aff);
 219 __isl_give isl_pw_aff *isl_ast_build_compute_gist_pw_aff(
 220         __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa);
 221 __isl_give isl_pw_multi_aff *isl_ast_build_compute_gist_pw_multi_aff(
 222         __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma);
 223
 224 __isl_give isl_union_map *isl_ast_build_substitute_values_union_map_domain(
 225         __isl_keep isl_ast_build *build, __isl_take isl_union_map *umap);
 226
 227 int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build,
 228         __isl_keep isl_aff *aff);
 229
 230 int isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos);
 231 __isl_give isl_aff *isl_ast_build_get_offset(__isl_keep isl_ast_build *build,
 232         int pos);
 233 int isl_ast_build_get_stride(__isl_keep isl_ast_build *build, int pos,
 234         isl_int *stride);
 235 __isl_give isl_set *isl_ast_build_get_stride_constraint(
 236         __isl_keep isl_ast_build *build);
 237 __isl_give isl_multi_aff *isl_ast_build_get_stride_expansion(
 238         __isl_keep isl_ast_build *build);
 239
 240 void isl_ast_build_dump(__isl_keep isl_ast_build *build);
 241
 242 __isl_give isl_set *isl_ast_build_get_option_domain(
 243         __isl_keep isl_ast_build *build,
 244         enum isl_ast_build_domain_type type);
 245 __isl_give isl_map *isl_ast_build_get_separation_class(
 246         __isl_keep isl_ast_build *build);
 247 __isl_give isl_set *isl_ast_build_eliminate(
 248         __isl_keep isl_ast_build *build, __isl_take isl_set *domain);
 249 __isl_give isl_set *isl_ast_build_eliminate_inner(
 250         __isl_keep isl_ast_build *build, __isl_take isl_set *set);
 251 __isl_give isl_set *isl_ast_build_eliminate_divs(
 252         __isl_keep isl_ast_build *build, __isl_take isl_set *set);
 253
 254 __isl_give isl_map *isl_ast_build_map_to_iterator(
 255         __isl_keep isl_ast_build *build, __isl_take isl_set *set);
 256
 257 int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build *build);
 258
 259 #endif