328 lines · c
1#ifndef ISL_AST_BUILD_PRIVATE_H2#define ISL_AST_BUILD_PRIVATE_H3 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#include <isl/schedule_node.h>10 11/* An isl_ast_build represents the context in which AST is being12 * generated. That is, it (mostly) contains information about outer13 * loops that can be used to simplify inner loops.14 *15 * "domain" represents constraints on the internal schedule domain,16 * corresponding to the context of the AST generation and the constraints17 * implied by the loops that have already been generated.18 * When an isl_ast_build is first created, outside any AST generation,19 * the domain is typically a parameter set. It is only when a AST20 * generation phase is initiated that the domain of the isl_ast_build21 * is changed to refer to the internal schedule domain.22 * The domain then lives in a space of the form23 *24 * S25 *26 * or27 *28 * [O -> S]29 *30 * O represents the loops generated in outer AST generations.31 * S represents the loops (both generated and to be generated)32 * of the current AST generation.33 * Both include eliminated loops.34 * "domain" is expected not to have any unknown divs because35 * it is used as the context argument in a call to isl_basic_set_gist36 * in isl_ast_build_compute_gist_basic_set.37 *38 * "depth" is equal to the number of loops that have already39 * been generated (including those in outer AST generations).40 * "outer_pos" is equal to the number of loops in outer AST generations.41 *42 * "generated" is a superset of "domain" corresponding to those43 * constraints that were either given by the user or that have44 * effectively been generated (as bounds on a for loop).45 *46 * "pending" is a superset of "domain" corresponding to the constraints47 * that still need to be generated (as guards), but that may end up48 * not getting generated if they are implied by any constraints49 * enforced by inner loops.50 *51 * "strides" contains the stride of each loop. The number of elements52 * is equal to the number of dimensions in "domain".53 * "offsets" contains the offsets of strided loops. If s is the stride54 * for a given dimension and f is the corresponding offset, then the55 * dimension takes on values56 *57 * f + s a58 *59 * with a an integer. For non-strided loops, the offset is zero.60 *61 * "iterators" contains the loop iterators of both generated and62 * to be generated loops. The number of elements is at least as63 * large as the dimension of the internal schedule domain. The64 * number may be larger, in which case the additional ids can be65 * used in a nested AST generation should the schedule be non-injective.66 *67 * "values" lives in the space68 *69 * [O -> S] -> [O -> S] (or S -> S)70 *71 * and expresses (if possible) loop iterators in terms of parameters72 * and outer loop iterators. If the value of a given loop iterator73 * cannot be expressed as an affine expression (either because the iterator74 * attains multiple values or because the single value is a piecewise75 * affine expression), then it is expressed in "values" as being equal76 * to itself.77 *78 * "value" is the value of the loop iterator at the current depth.79 * It is NULL if it has not been computed yet or if the value of the80 * given loop iterator cannot be expressed as a piecewise affine expression81 * (because the iterator attains multiple values).82 *83 * "schedule_map" maps the internal schedule domain to the external schedule84 * domain. It may be NULL if it hasn't been computed yet.85 * See isl_ast_build_get_schedule_map_multi_aff.86 *87 * "internal2input" maps the internal schedule domain to the original88 * input schedule domain. In case of a schedule tree input, the original89 * input schedule domain consist of the flat product of all outer90 * band node spaces, including the current band node.91 * It may be NULL if there no longer is such a uniform mapping92 * (because different iterations have been rescheduled differently).93 *94 * "options" contains the AST build options in case we are generating95 * an AST from a flat schedule map. When creating an AST from a schedule96 * tree, this field is ignored.97 *98 * The "create_leaf" callback is called for every leaf in the generated AST.99 * The callback is responsible for creating the node to be placed at those100 * leaves. If this callback is not set, then isl will generated user101 * nodes with call expressions corresponding to an element of the domain.102 *103 * The "at_each_domain" callback is called on every node created to represent104 * an element of the domain. Each of these nodes is a user node105 * with as expression a call expression.106 *107 * The "before_each_for" callback is called on each for node before108 * its children have been created.109 *110 * The "after_each_for" callback is called on each for node after111 * its children have been created.112 *113 * The "before_each_mark" callback is called before we handle the subtree114 * of an isl_schedule_node_mark node.115 *116 * The "after_each_mark" callback is called after we have handled the subtree117 * of an isl_schedule_node_mark node.118 *119 * "executed" contains the inverse schedule at this point120 * of the AST generation.121 * It is currently only used in isl_ast_build_get_schedule, which is122 * in turn only used by user code from within a callback.123 * The value is set right before we may be calling such a callback.124 *125 * "single_valued" is set if the current inverse schedule (which may or may126 * not be stored in "executed") is known to be single valued, specifically127 * an inverse schedule that was not (appeared not to be) single valued128 * is extended to a single valued inverse schedule. This is mainly used129 * to avoid an infinite recursion when we fail to detect later on that130 * the extended inverse schedule is single valued.131 *132 * "node" points to the current band node in case we are generating133 * an AST from a schedule tree. It may be NULL if we are not generating134 * an AST from a schedule tree or if we are not inside a band node.135 *136 * "loop_type" originally contains loop AST generation types for137 * the "n" members of "node" and it is updated (along with "n") when138 * a schedule dimension is inserted.139 * It is NULL if "node" is NULL.140 *141 * "isolated" is the piece of the schedule domain isolated by the isolate142 * option on the current band. This set may be NULL if we have not checked143 * for the isolate option yet.144 */145struct isl_ast_build {146 int ref;147 148 int outer_pos;149 int depth;150 151 isl_id_list *iterators;152 153 isl_set *domain;154 isl_set *generated;155 isl_set *pending;156 isl_multi_aff *values;157 158 isl_pw_aff *value;159 160 isl_vec *strides;161 isl_multi_aff *offsets;162 163 isl_multi_aff *schedule_map;164 isl_multi_aff *internal2input;165 166 isl_union_map *options;167 168 __isl_give isl_ast_node *(*at_each_domain)(169 __isl_take isl_ast_node *node,170 __isl_keep isl_ast_build *build, void *user);171 void *at_each_domain_user;172 173 __isl_give isl_id *(*before_each_for)(174 __isl_keep isl_ast_build *context, void *user);175 void *before_each_for_user;176 __isl_give isl_ast_node *(*after_each_for)(177 __isl_take isl_ast_node *node,178 __isl_keep isl_ast_build *context, void *user);179 void *after_each_for_user;180 181 isl_stat (*before_each_mark)(__isl_keep isl_id *mark,182 __isl_keep isl_ast_build *build, void *user);183 void *before_each_mark_user;184 __isl_give isl_ast_node *(*after_each_mark)(185 __isl_take isl_ast_node *node,186 __isl_keep isl_ast_build *context, void *user);187 void *after_each_mark_user;188 189 __isl_give isl_ast_node *(*create_leaf)(190 __isl_take isl_ast_build *build, void *user);191 void *create_leaf_user;192 193 isl_union_map *executed;194 int single_valued;195 196 isl_schedule_node *node;197 int n;198 enum isl_ast_loop_type *loop_type;199 isl_set *isolated;200};201 202__isl_give isl_ast_build *isl_ast_build_clear_local_info(203 __isl_take isl_ast_build *build);204__isl_give isl_ast_build *isl_ast_build_increase_depth(205 __isl_take isl_ast_build *build);206isl_size isl_ast_build_get_depth(__isl_keep isl_ast_build *build);207isl_size isl_ast_build_dim(__isl_keep isl_ast_build *build,208 enum isl_dim_type type);209__isl_give isl_space *isl_ast_build_get_space(210 __isl_keep isl_ast_build *build, int internal);211__isl_give isl_ast_build *isl_ast_build_align_params(212 __isl_take isl_ast_build *build, __isl_take isl_space *model);213__isl_give isl_ast_build *isl_ast_build_cow(214 __isl_take isl_ast_build *build);215__isl_give isl_ast_build *isl_ast_build_insert_dim(216 __isl_take isl_ast_build *build, int pos);217__isl_give isl_ast_build *isl_ast_build_scale_down(218 __isl_take isl_ast_build *build, __isl_take isl_val *m,219 __isl_take isl_union_map *umap);220__isl_give isl_ast_build *isl_ast_build_product(221 __isl_take isl_ast_build *build, __isl_take isl_space *embedding);222__isl_give isl_ast_build *isl_ast_build_set_loop_bounds(223 __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds);224__isl_give isl_ast_build *isl_ast_build_set_pending_generated(225 __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds);226__isl_give isl_ast_build *isl_ast_build_detect_strides(227 __isl_take isl_ast_build *build, __isl_take isl_set *set);228__isl_give isl_ast_build *isl_ast_build_include_stride(229 __isl_take isl_ast_build *build);230__isl_give isl_ast_build *isl_ast_build_set_executed(231 __isl_take isl_ast_build *build,232 __isl_take isl_union_map *executed);233__isl_give isl_ast_build *isl_ast_build_set_single_valued(234 __isl_take isl_ast_build *build, int sv);235__isl_give isl_multi_aff *isl_ast_build_get_internal2input(236 __isl_keep isl_ast_build *build);237__isl_give isl_set *isl_ast_build_get_domain(238 __isl_keep isl_ast_build *build);239__isl_give isl_set *isl_ast_build_get_pending(240 __isl_keep isl_ast_build *build);241__isl_give isl_set *isl_ast_build_get_generated(242 __isl_keep isl_ast_build *build);243__isl_give isl_ast_build *isl_ast_build_restrict_generated(244 __isl_take isl_ast_build *build, __isl_take isl_set *set);245__isl_give isl_ast_build *isl_ast_build_replace_pending_by_guard(246 __isl_take isl_ast_build *build, __isl_take isl_set *guard);247isl_bool isl_ast_build_need_schedule_map(__isl_keep isl_ast_build *build);248__isl_give isl_multi_aff *isl_ast_build_get_schedule_map_multi_aff(249 __isl_keep isl_ast_build *build);250__isl_give isl_map *isl_ast_build_get_schedule_map(251 __isl_keep isl_ast_build *build);252isl_bool isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build,253 int pos);254int isl_ast_build_has_value(__isl_keep isl_ast_build *build);255__isl_give isl_id *isl_ast_build_get_iterator_id(256 __isl_keep isl_ast_build *build, int pos);257 258int isl_ast_build_has_schedule_node(__isl_keep isl_ast_build *build);259__isl_give isl_schedule_node *isl_ast_build_get_schedule_node(260 __isl_keep isl_ast_build *build);261__isl_give isl_ast_build *isl_ast_build_set_schedule_node(262 __isl_take isl_ast_build *build,263 __isl_take isl_schedule_node *node);264__isl_give isl_ast_build *isl_ast_build_reset_schedule_node(265 __isl_take isl_ast_build *build);266 267__isl_give isl_ast_build *isl_ast_build_extract_isolated(268 __isl_take isl_ast_build *build);269int isl_ast_build_has_isolated(__isl_keep isl_ast_build *build);270__isl_give isl_set *isl_ast_build_get_isolated(271 __isl_keep isl_ast_build *build);272 273__isl_give isl_basic_set *isl_ast_build_specialize_basic_set(274 __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset);275__isl_give isl_basic_set *isl_ast_build_compute_gist_basic_set(276 __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset);277__isl_give isl_set *isl_ast_build_specialize(__isl_keep isl_ast_build *build,278 __isl_take isl_set *set);279__isl_give isl_set *isl_ast_build_compute_gist(280 __isl_keep isl_ast_build *build, __isl_take isl_set *set);281__isl_give isl_map *isl_ast_build_compute_gist_map_domain(282 __isl_keep isl_ast_build *build, __isl_take isl_map *map);283__isl_give isl_aff *isl_ast_build_compute_gist_aff(284 __isl_keep isl_ast_build *build, __isl_take isl_aff *aff);285__isl_give isl_pw_aff *isl_ast_build_compute_gist_pw_aff(286 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa);287__isl_give isl_pw_multi_aff *isl_ast_build_compute_gist_pw_multi_aff(288 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma);289 290__isl_give isl_union_map *isl_ast_build_substitute_values_union_map_domain(291 __isl_keep isl_ast_build *build, __isl_take isl_union_map *umap);292 293isl_bool isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build,294 __isl_keep isl_aff *aff);295 296isl_bool isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos);297__isl_give isl_aff *isl_ast_build_get_offset(__isl_keep isl_ast_build *build,298 int pos);299__isl_give isl_val *isl_ast_build_get_stride(__isl_keep isl_ast_build *build,300 int pos);301__isl_give isl_set *isl_ast_build_get_stride_constraint(302 __isl_keep isl_ast_build *build);303__isl_give isl_multi_aff *isl_ast_build_get_stride_expansion(304 __isl_keep isl_ast_build *build);305 306void isl_ast_build_dump(__isl_keep isl_ast_build *build);307 308__isl_give isl_set *isl_ast_build_get_option_domain(309 __isl_keep isl_ast_build *build, enum isl_ast_loop_type type);310__isl_give isl_map *isl_ast_build_get_separation_class(311 __isl_keep isl_ast_build *build);312__isl_give isl_set *isl_ast_build_eliminate(313 __isl_keep isl_ast_build *build, __isl_take isl_set *domain);314__isl_give isl_set *isl_ast_build_eliminate_inner(315 __isl_keep isl_ast_build *build, __isl_take isl_set *set);316__isl_give isl_set *isl_ast_build_eliminate_divs(317 __isl_keep isl_ast_build *build, __isl_take isl_set *set);318 319enum isl_ast_loop_type isl_ast_build_get_loop_type(320 __isl_keep isl_ast_build *build, int isolated);321 322__isl_give isl_map *isl_ast_build_map_to_iterator(323 __isl_keep isl_ast_build *build, __isl_take isl_set *set);324 325int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build *build);326 327#endif328