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 #include <isl/schedule_node.h> 10 11 /* An isl_ast_build represents the context in which AST is being 12 * generated. That is, it (mostly) contains information about outer 13 * 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 constraints 17 * 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 AST 20 * generation phase is initiated that the domain of the isl_ast_build 21 * is changed to refer to the internal schedule domain. 22 * The domain then lives in a space of the form 23 * 24 * S 25 * 26 * or 27 * 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 because 35 * it is used as the context argument in a call to isl_basic_set_gist 36 * in isl_ast_build_compute_gist_basic_set. 37 * 38 * "depth" is equal to the number of loops that have already 39 * 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 those 43 * constraints that were either given by the user or that have 44 * effectively been generated (as bounds on a for loop). 45 * 46 * "pending" is a superset of "domain" corresponding to the constraints 47 * that still need to be generated (as guards), but that may end up 48 * not getting generated if they are implied by any constraints 49 * enforced by inner loops. 50 * 51 * "strides" contains the stride of each loop. The number of elements 52 * is equal to the number of dimensions in "domain". 53 * "offsets" contains the offsets of strided loops. If s is the stride 54 * for a given dimension and f is the corresponding offset, then the 55 * dimension takes on values 56 * 57 * f + s a 58 * 59 * with a an integer. For non-strided loops, the offset is zero. 60 * 61 * "iterators" contains the loop iterators of both generated and 62 * to be generated loops. The number of elements is at least as 63 * large as the dimension of the internal schedule domain. The 64 * number may be larger, in which case the additional ids can be 65 * used in a nested AST generation should the schedule be non-injective. 66 * 67 * "values" lives in the space 68 * 69 * [O -> S] -> [O -> S] (or S -> S) 70 * 71 * and expresses (if possible) loop iterators in terms of parameters 72 * and outer loop iterators. If the value of a given loop iterator 73 * cannot be expressed as an affine expression (either because the iterator 74 * attains multiple values or because the single value is a piecewise 75 * affine expression), then it is expressed in "values" as being equal 76 * 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 the 80 * given loop iterator cannot be expressed as a piecewise affine expression 81 * (because the iterator attains multiple values). 82 * 83 * "schedule_map" maps the internal schedule domain to the external schedule 84 * 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 original 88 * input schedule domain. In case of a schedule tree input, the original 89 * input schedule domain consist of the flat product of all outer 90 * band node spaces, including the current band node. 91 * It may be NULL if there no longer is such a uniform mapping 92 * (because different iterations have been rescheduled differently). 93 * 94 * "options" contains the AST build options in case we are generating 95 * an AST from a flat schedule map. When creating an AST from a schedule 96 * 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 those 100 * leaves. If this callback is not set, then isl will generated user 101 * 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 represent 104 * an element of the domain. Each of these nodes is a user node 105 * with as expression a call expression. 106 * 107 * The "before_each_for" callback is called on each for node before 108 * its children have been created. 109 * 110 * The "after_each_for" callback is called on each for node after 111 * its children have been created. 112 * 113 * The "before_each_mark" callback is called before we handle the subtree 114 * of an isl_schedule_node_mark node. 115 * 116 * The "after_each_mark" callback is called after we have handled the subtree 117 * of an isl_schedule_node_mark node. 118 * 119 * "executed" contains the inverse schedule at this point 120 * of the AST generation. 121 * It is currently only used in isl_ast_build_get_schedule, which is 122 * 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 may 126 * not be stored in "executed") is known to be single valued, specifically 127 * an inverse schedule that was not (appeared not to be) single valued 128 * is extended to a single valued inverse schedule. This is mainly used 129 * to avoid an infinite recursion when we fail to detect later on that 130 * the extended inverse schedule is single valued. 131 * 132 * "node" points to the current band node in case we are generating 133 * an AST from a schedule tree. It may be NULL if we are not generating 134 * 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 for 137 * the "n" members of "node" and it is updated (along with "n") when 138 * 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 isolate 142 * option on the current band. This set may be NULL if we have not checked 143 * for the isolate option yet. 144 */ 145 struct 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); 206 int isl_ast_build_get_depth(__isl_keep isl_ast_build *build); 207 isl_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); 247 isl_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); 252 isl_bool isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build, 253 int pos); 254 int 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 258 int 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); 269 int 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 293 int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build, 294 __isl_keep isl_aff *aff); 295 296 isl_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 306 void 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 319 enum 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 325 int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build *build); 326 327 #endif 328