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  * "executed" contains the inverse schedule at this point
 102  * of the AST generation.
 103  * It is currently only used in isl_ast_build_get_schedule, which is
 104  * in turn only used by user code from within a callback.
 105  * The value is set right before we may be calling such a callback.
 106  */
 107 struct isl_ast_build {
 108         int ref;
 109
 110         int outer_pos;
 111         int depth;
 112
 113         isl_id_list *iterators;
 114
 115         isl_set *domain;
 116         isl_set *generated;
 117         isl_set *pending;
 118         isl_multi_aff *values;
 119
 120         isl_pw_aff *value;
 121
 122         isl_vec *strides;
 123         isl_multi_aff *offsets;
 124
 125         isl_multi_aff *schedule_map;
 126
 127         isl_union_map *options;
 128
 129         __isl_give isl_ast_node *(*at_each_domain)(
 130                 __isl_take isl_ast_node *node,
 131                 __isl_keep isl_ast_build *build, void *user);
 132         void *at_each_domain_user;
 133
 134         __isl_give isl_ast_node *(*create_leaf)(
 135                 __isl_take isl_ast_build *build, void *user);
 136         void *create_leaf_user;
 137
 138         isl_union_map *executed;
 139 };
 140
 141 __isl_give isl_ast_build *isl_ast_build_clear_local_info(
 142         __isl_take isl_ast_build *build);
 143 __isl_give isl_ast_build *isl_ast_build_increase_depth(
 144         __isl_take isl_ast_build *build);
 145 int isl_ast_build_get_depth(__isl_keep isl_ast_build *build);
 146 __isl_give isl_space *isl_ast_build_get_space(
 147         __isl_keep isl_ast_build *build, int internal);
 148 __isl_give isl_ast_build *isl_ast_build_align_params(
 149         __isl_take isl_ast_build *build, __isl_take isl_space *model);
 150 __isl_give isl_ast_build *isl_ast_build_cow(
 151         __isl_take isl_ast_build *build);
 152 __isl_give isl_ast_build *isl_ast_build_insert_dim(
 153         __isl_take isl_ast_build *build, int pos);
 154 __isl_give isl_ast_build *isl_ast_build_scale_down(
 155         __isl_take isl_ast_build *build, isl_int m,
 156         __isl_take isl_union_map *umap);
 157 __isl_give isl_ast_build *isl_ast_build_product(
 158         __isl_take isl_ast_build *build, __isl_take isl_space *embedding);
 159 __isl_give isl_ast_build *isl_ast_build_set_loop_bounds(
 160         __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds);
 161 __isl_give isl_ast_build *isl_ast_build_detect_strides(
 162         __isl_take isl_ast_build *build, __isl_take isl_set *set);
 163 __isl_give isl_ast_build *isl_ast_build_include_stride(
 164         __isl_take isl_ast_build *build);
 165 __isl_give isl_ast_build *isl_ast_build_set_executed(
 166         __isl_take isl_ast_build *build,
 167         __isl_take isl_union_map *executed);
 168 __isl_give isl_set *isl_ast_build_get_domain(
 169         __isl_keep isl_ast_build *build);
 170 __isl_give isl_ast_build *isl_ast_build_restrict_generated(
 171         __isl_take isl_ast_build *build, __isl_take isl_set *set);
 172 __isl_give isl_ast_build *isl_ast_build_restrict_pending(
 173         __isl_take isl_ast_build *build, __isl_take isl_set *set);
 174 __isl_give isl_ast_build *isl_ast_build_set_enforced(
 175         __isl_take isl_ast_build *build, __isl_take isl_basic_set *enforced);
 176 __isl_give int isl_ast_build_need_schedule_map(
 177         __isl_keep isl_ast_build *build);
 178 __isl_give isl_multi_aff *isl_ast_build_get_schedule_map_multi_aff(
 179         __isl_keep isl_ast_build *build);
 180 __isl_give isl_map *isl_ast_build_get_schedule_map(
 181         __isl_keep isl_ast_build *build);
 182 int isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build, int pos);
 183 int isl_ast_build_has_value(__isl_keep isl_ast_build *build);
 184 __isl_give isl_id *isl_ast_build_get_iterator_id(
 185         __isl_keep isl_ast_build *build, int pos);
 186
 187 __isl_give isl_basic_set *isl_ast_build_compute_gist_basic_set(
 188         __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset);
 189 __isl_give isl_set *isl_ast_build_compute_gist(
 190         __isl_keep isl_ast_build *build, __isl_take isl_set *set);
 191 __isl_give isl_map *isl_ast_build_compute_gist_map_domain(
 192         __isl_keep isl_ast_build *build, __isl_take isl_map *map);
 193 __isl_give isl_aff *isl_ast_build_compute_gist_aff(
 194         __isl_keep isl_ast_build *build, __isl_take isl_aff *aff);
 195 __isl_give isl_pw_aff *isl_ast_build_compute_gist_pw_aff(
 196         __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa);
 197 __isl_give isl_pw_multi_aff *isl_ast_build_compute_gist_pw_multi_aff(
 198         __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma);
 199
 200 int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build,
 201         __isl_keep isl_aff *aff);
 202
 203 int isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos);
 204 __isl_give isl_aff *isl_ast_build_get_offset(__isl_keep isl_ast_build *build,
 205         int pos);
 206 int isl_ast_build_get_stride(__isl_keep isl_ast_build *build, int pos,
 207         isl_int *stride);
 208 __isl_give isl_set *isl_ast_build_get_stride_constraint(
 209         __isl_keep isl_ast_build *build);
 210 __isl_give isl_multi_aff *isl_ast_build_get_stride_expansion(
 211         __isl_keep isl_ast_build *build);
 212
 213 void isl_ast_build_dump(__isl_keep isl_ast_build *build);
 214
 215 __isl_give isl_set *isl_ast_build_get_option_domain(
 216         __isl_keep isl_ast_build *build,
 217         enum isl_ast_build_domain_type type);
 218 __isl_give isl_map *isl_ast_build_get_separation_class(
 219         __isl_keep isl_ast_build *build);
 220 __isl_give isl_set *isl_ast_build_eliminate(
 221         __isl_keep isl_ast_build *build, __isl_take isl_set *domain);
 222 __isl_give isl_set *isl_ast_build_eliminate_inner(
 223         __isl_keep isl_ast_build *build, __isl_take isl_set *set);
 224 __isl_give isl_set *isl_ast_build_eliminate_divs(
 225         __isl_keep isl_ast_build *build, __isl_take isl_set *set);
 226
 227 __isl_give isl_map *isl_ast_build_map_to_iterator(
 228         __isl_keep isl_ast_build *build, __isl_take isl_set *set);
 229
 230 int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build *build);
 231
 232 #endif