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 struct isl_ast_build {
 114         int ref;
 115
 116         int outer_pos;
 117         int depth;
 118
 119         isl_id_list *iterators;
 120
 121         isl_set *domain;
 122         isl_set *generated;
 123         isl_set *pending;
 124         isl_multi_aff *values;
 125
 126         isl_pw_aff *value;
 127
 128         isl_vec *strides;
 129         isl_multi_aff *offsets;
 130
 131         isl_multi_aff *schedule_map;
 132
 133         isl_union_map *options;
 134
 135         __isl_give isl_ast_node *(*at_each_domain)(
 136                 __isl_take isl_ast_node *node,
 137                 __isl_keep isl_ast_build *build, void *user);
 138         void *at_each_domain_user;
 139
 140         __isl_give isl_id *(*before_each_for)(
 141                 __isl_keep isl_ast_build *context, void *user);
 142         void *before_each_for_user;
 143         __isl_give isl_ast_node *(*after_each_for)(
 144                 __isl_take isl_ast_node *node,
 145                 __isl_keep isl_ast_build *context, void *user);
 146         void *after_each_for_user;
 147
 148         __isl_give isl_ast_node *(*create_leaf)(
 149                 __isl_take isl_ast_build *build, void *user);
 150         void *create_leaf_user;
 151
 152         isl_union_map *executed;
 153 };
 154
 155 __isl_give isl_ast_build *isl_ast_build_clear_local_info(
 156         __isl_take isl_ast_build *build);
 157 __isl_give isl_ast_build *isl_ast_build_increase_depth(
 158         __isl_take isl_ast_build *build);
 159 int isl_ast_build_get_depth(__isl_keep isl_ast_build *build);
 160 __isl_give isl_space *isl_ast_build_get_space(
 161         __isl_keep isl_ast_build *build, int internal);
 162 __isl_give isl_ast_build *isl_ast_build_align_params(
 163         __isl_take isl_ast_build *build, __isl_take isl_space *model);
 164 __isl_give isl_ast_build *isl_ast_build_cow(
 165         __isl_take isl_ast_build *build);
 166 __isl_give isl_ast_build *isl_ast_build_insert_dim(
 167         __isl_take isl_ast_build *build, int pos);
 168 __isl_give isl_ast_build *isl_ast_build_scale_down(
 169         __isl_take isl_ast_build *build, isl_int m,
 170         __isl_take isl_union_map *umap);
 171 __isl_give isl_ast_build *isl_ast_build_product(
 172         __isl_take isl_ast_build *build, __isl_take isl_space *embedding);
 173 __isl_give isl_ast_build *isl_ast_build_set_loop_bounds(
 174         __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds);
 175 __isl_give isl_ast_build *isl_ast_build_detect_strides(
 176         __isl_take isl_ast_build *build, __isl_take isl_set *set);
 177 __isl_give isl_ast_build *isl_ast_build_include_stride(
 178         __isl_take isl_ast_build *build);
 179 __isl_give isl_ast_build *isl_ast_build_set_executed(
 180         __isl_take isl_ast_build *build,
 181         __isl_take isl_union_map *executed);
 182 __isl_give isl_set *isl_ast_build_get_domain(
 183         __isl_keep isl_ast_build *build);
 184 __isl_give isl_ast_build *isl_ast_build_restrict_generated(
 185         __isl_take isl_ast_build *build, __isl_take isl_set *set);
 186 __isl_give isl_ast_build *isl_ast_build_restrict_pending(
 187         __isl_take isl_ast_build *build, __isl_take isl_set *set);
 188 __isl_give isl_ast_build *isl_ast_build_set_enforced(
 189         __isl_take isl_ast_build *build, __isl_take isl_basic_set *enforced);
 190 __isl_give int isl_ast_build_need_schedule_map(
 191         __isl_keep isl_ast_build *build);
 192 __isl_give isl_multi_aff *isl_ast_build_get_schedule_map_multi_aff(
 193         __isl_keep isl_ast_build *build);
 194 __isl_give isl_map *isl_ast_build_get_schedule_map(
 195         __isl_keep isl_ast_build *build);
 196 int isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build, int pos);
 197 int isl_ast_build_has_value(__isl_keep isl_ast_build *build);
 198 __isl_give isl_id *isl_ast_build_get_iterator_id(
 199         __isl_keep isl_ast_build *build, int pos);
 200
 201 __isl_give isl_basic_set *isl_ast_build_compute_gist_basic_set(
 202         __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset);
 203 __isl_give isl_set *isl_ast_build_compute_gist(
 204         __isl_keep isl_ast_build *build, __isl_take isl_set *set);
 205 __isl_give isl_map *isl_ast_build_compute_gist_map_domain(
 206         __isl_keep isl_ast_build *build, __isl_take isl_map *map);
 207 __isl_give isl_aff *isl_ast_build_compute_gist_aff(
 208         __isl_keep isl_ast_build *build, __isl_take isl_aff *aff);
 209 __isl_give isl_pw_aff *isl_ast_build_compute_gist_pw_aff(
 210         __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa);
 211 __isl_give isl_pw_multi_aff *isl_ast_build_compute_gist_pw_multi_aff(
 212         __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma);
 213
 214 int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build,
 215         __isl_keep isl_aff *aff);
 216
 217 int isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos);
 218 __isl_give isl_aff *isl_ast_build_get_offset(__isl_keep isl_ast_build *build,
 219         int pos);
 220 int isl_ast_build_get_stride(__isl_keep isl_ast_build *build, int pos,
 221         isl_int *stride);
 222 __isl_give isl_set *isl_ast_build_get_stride_constraint(
 223         __isl_keep isl_ast_build *build);
 224 __isl_give isl_multi_aff *isl_ast_build_get_stride_expansion(
 225         __isl_keep isl_ast_build *build);
 226
 227 void isl_ast_build_dump(__isl_keep isl_ast_build *build);
 228
 229 __isl_give isl_set *isl_ast_build_get_option_domain(
 230         __isl_keep isl_ast_build *build,
 231         enum isl_ast_build_domain_type type);
 232 __isl_give isl_map *isl_ast_build_get_separation_class(
 233         __isl_keep isl_ast_build *build);
 234 __isl_give isl_set *isl_ast_build_eliminate(
 235         __isl_keep isl_ast_build *build, __isl_take isl_set *domain);
 236 __isl_give isl_set *isl_ast_build_eliminate_inner(
 237         __isl_keep isl_ast_build *build, __isl_take isl_set *set);
 238 __isl_give isl_set *isl_ast_build_eliminate_divs(
 239         __isl_keep isl_ast_build *build, __isl_take isl_set *set);
 240
 241 __isl_give isl_map *isl_ast_build_map_to_iterator(
 242         __isl_keep isl_ast_build *build, __isl_take isl_set *set);
 243
 244 int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build *build);
 245
 246 #endif