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 */
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#endif
328

source code of polly/lib/External/isl/isl_ast_build_private.h