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 10enum 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 */ 120struct 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); 167int 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_take isl_val *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); 206int isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build, int pos); 207int 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 227int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build, 228 __isl_keep isl_aff *aff); 229 230int 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__isl_give isl_val *isl_ast_build_get_stride(__isl_keep isl_ast_build *build, 234 int pos); 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 240void 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 257int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build *build); 258 259#endif 260