1 #ifndef ISL_AST_BUILD_PRIVATE_H
2 #define ISL_AST_BUILD_PRIVATE_H
6 #include <isl/ast_build.h>
9 #include <isl/schedule_node.h>
11 enum isl_ast_build_domain_type
{
17 /* An isl_ast_build represents the context in which AST is being
18 * generated. That is, it (mostly) contains information about outer
19 * loops that can be used to simplify inner loops.
21 * "domain" represents constraints on the internal schedule domain,
22 * corresponding to the context of the AST generation and the constraints
23 * implied by the loops that have already been generated.
24 * When an isl_ast_build is first created, outside any AST generation,
25 * the domain is typically a parameter set. It is only when a AST
26 * generation phase is initiated that the domain of the isl_ast_build
27 * is changed to refer to the internal schedule domain.
28 * The domain then lives in a space of the form
36 * O represents the loops generated in outer AST generations.
37 * S represents the loops (both generated and to be generated)
38 * of the current AST generation.
39 * Both include eliminated loops.
40 * "domain" is expected not to have any unknown divs because
41 * it is used as the context argument in a call to isl_basic_set_gist
42 * in isl_ast_build_compute_gist_basic_set.
44 * "depth" is equal to the number of loops that have already
45 * been generated (including those in outer AST generations).
46 * "outer_pos" is equal to the number of loops in outer AST generations.
48 * "generated" is a superset of "domain" corresponding to those
49 * constraints that were either given by the user or that have
50 * effectively been generated (as bounds on a for loop).
52 * "pending" is a superset of "domain" corresponding to the constraints
53 * that still need to be generated (as guards), but that may end up
54 * not getting generated if they are implied by any constraints
55 * enforced by inner loops.
57 * "strides" contains the stride of each loop. The number of elements
58 * is equal to the number of dimensions in "domain".
59 * "offsets" constains the offsets of strided loops. If s is the stride
60 * for a given dimension and f is the corresponding offset, then the
61 * dimension takes on values
65 * with a an integer. For non-strided loops, the offset is zero.
67 * "iterators" contains the loop iterators of both generated and
68 * to be generated loops. The number of elements is at least as
69 * large as the dimension of the internal schedule domain. The
70 * number may be larger, in which case the additional ids can be
71 * used in a nested AST generation should the schedule be non-injective.
73 * "values" lives in the space
75 * [O -> S] -> [O -> S] (or S -> S)
77 * and expresses (if possible) loop iterators in terms of parameters
78 * and outer loop iterators. If the value of a given loop iterator
79 * cannot be expressed as an affine expression (either because the iterator
80 * attains multiple values or because the single value is a piecewise
81 * affine expression), then it is expressed in "values" as being equal
84 * "value" is the value of the loop iterator at the current depth.
85 * It is NULL if it has not been computed yet or if the value of the
86 * given loop iterator cannot be expressed as a piecewise affine expression
87 * (because the iterator attains multiple values).
89 * "schedule_map" maps the internal schedule domain to the external schedule
90 * domain. It may be NULL if it hasn't been computed yet.
91 * See isl_ast_build_get_schedule_map_multi_aff.
93 * "options" contains the AST build options in case we are generating
94 * an AST from a flat schedule map. When creating an AST from a schedule
95 * tree, this field is ignored.
97 * The "create_leaf" callback is called for every leaf in the generated AST.
98 * The callback is responsible for creating the node to be placed at those
99 * leaves. If this callback is not set, then isl will generated user
100 * nodes with call expressions corresponding to an element of the domain.
102 * The "at_each_domain" callback is called on every node created to represent
103 * an element of the domain. Each of these nodes is a user node
104 * with as expression a call expression.
106 * The "before_each_for" callback is called on each for node before
107 * its children have been created.
109 * The "after_each_for" callback is called on each for node after
110 * its children have been created.
112 * "executed" contains the inverse schedule at this point
113 * of the AST generation.
114 * It is currently only used in isl_ast_build_get_schedule, which is
115 * in turn only used by user code from within a callback.
116 * The value is set right before we may be calling such a callback.
118 * "single_valued" is set if the current inverse schedule (which may or may
119 * not be stored in "executed") is known to be single valued, specifically
120 * an inverse schedule that was not (appeared not to be) single valued
121 * is extended to a single valued inverse schedule. This is mainly used
122 * to avoid an infinite recursion when we fail to detect later on that
123 * the extended inverse schedule is single valued.
125 * "node" points to the current band node in case we are generating
126 * an AST from a schedule tree. It may be NULL if we are not generating
127 * an AST from a schedule tree or if we are not inside a band node.
129 struct isl_ast_build
{
135 isl_id_list
*iterators
;
140 isl_multi_aff
*values
;
145 isl_multi_aff
*offsets
;
147 isl_multi_aff
*schedule_map
;
149 isl_union_map
*options
;
151 __isl_give isl_ast_node
*(*at_each_domain
)(
152 __isl_take isl_ast_node
*node
,
153 __isl_keep isl_ast_build
*build
, void *user
);
154 void *at_each_domain_user
;
156 __isl_give isl_id
*(*before_each_for
)(
157 __isl_keep isl_ast_build
*context
, void *user
);
158 void *before_each_for_user
;
159 __isl_give isl_ast_node
*(*after_each_for
)(
160 __isl_take isl_ast_node
*node
,
161 __isl_keep isl_ast_build
*context
, void *user
);
162 void *after_each_for_user
;
164 __isl_give isl_ast_node
*(*create_leaf
)(
165 __isl_take isl_ast_build
*build
, void *user
);
166 void *create_leaf_user
;
168 isl_union_map
*executed
;
171 isl_schedule_node
*node
;
174 __isl_give isl_ast_build
*isl_ast_build_clear_local_info(
175 __isl_take isl_ast_build
*build
);
176 __isl_give isl_ast_build
*isl_ast_build_increase_depth(
177 __isl_take isl_ast_build
*build
);
178 int isl_ast_build_get_depth(__isl_keep isl_ast_build
*build
);
179 unsigned isl_ast_build_dim(__isl_keep isl_ast_build
*build
,
180 enum isl_dim_type type
);
181 __isl_give isl_space
*isl_ast_build_get_space(
182 __isl_keep isl_ast_build
*build
, int internal
);
183 __isl_give isl_ast_build
*isl_ast_build_align_params(
184 __isl_take isl_ast_build
*build
, __isl_take isl_space
*model
);
185 __isl_give isl_ast_build
*isl_ast_build_cow(
186 __isl_take isl_ast_build
*build
);
187 __isl_give isl_ast_build
*isl_ast_build_insert_dim(
188 __isl_take isl_ast_build
*build
, int pos
);
189 __isl_give isl_ast_build
*isl_ast_build_scale_down(
190 __isl_take isl_ast_build
*build
, __isl_take isl_val
*m
,
191 __isl_take isl_union_map
*umap
);
192 __isl_give isl_ast_build
*isl_ast_build_product(
193 __isl_take isl_ast_build
*build
, __isl_take isl_space
*embedding
);
194 __isl_give isl_ast_build
*isl_ast_build_set_loop_bounds(
195 __isl_take isl_ast_build
*build
, __isl_take isl_basic_set
*bounds
);
196 __isl_give isl_ast_build
*isl_ast_build_detect_strides(
197 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
);
198 __isl_give isl_ast_build
*isl_ast_build_include_stride(
199 __isl_take isl_ast_build
*build
);
200 __isl_give isl_ast_build
*isl_ast_build_set_executed(
201 __isl_take isl_ast_build
*build
,
202 __isl_take isl_union_map
*executed
);
203 __isl_give isl_ast_build
*isl_ast_build_set_single_valued(
204 __isl_take isl_ast_build
*build
, int sv
);
205 __isl_give isl_set
*isl_ast_build_get_domain(
206 __isl_keep isl_ast_build
*build
);
207 __isl_give isl_set
*isl_ast_build_get_pending(
208 __isl_keep isl_ast_build
*build
);
209 __isl_give isl_set
*isl_ast_build_get_generated(
210 __isl_keep isl_ast_build
*build
);
211 __isl_give isl_ast_build
*isl_ast_build_restrict_generated(
212 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
);
213 __isl_give isl_ast_build
*isl_ast_build_replace_pending_by_guard(
214 __isl_take isl_ast_build
*build
, __isl_take isl_set
*guard
);
215 __isl_give isl_ast_build
*isl_ast_build_restrict_pending(
216 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
);
217 __isl_give
int isl_ast_build_need_schedule_map(
218 __isl_keep isl_ast_build
*build
);
219 __isl_give isl_multi_aff
*isl_ast_build_get_schedule_map_multi_aff(
220 __isl_keep isl_ast_build
*build
);
221 __isl_give isl_map
*isl_ast_build_get_schedule_map(
222 __isl_keep isl_ast_build
*build
);
223 int isl_ast_build_has_affine_value(__isl_keep isl_ast_build
*build
, int pos
);
224 int isl_ast_build_has_value(__isl_keep isl_ast_build
*build
);
225 __isl_give isl_id
*isl_ast_build_get_iterator_id(
226 __isl_keep isl_ast_build
*build
, int pos
);
228 int isl_ast_build_has_schedule_node(__isl_keep isl_ast_build
*build
);
229 __isl_give isl_schedule_node
*isl_ast_build_get_schedule_node(
230 __isl_keep isl_ast_build
*build
);
231 __isl_give isl_ast_build
*isl_ast_build_set_schedule_node(
232 __isl_take isl_ast_build
*build
,
233 __isl_take isl_schedule_node
*node
);
234 __isl_give isl_ast_build
*isl_ast_build_reset_schedule_node(
235 __isl_take isl_ast_build
*build
);
237 __isl_give isl_basic_set
*isl_ast_build_compute_gist_basic_set(
238 __isl_keep isl_ast_build
*build
, __isl_take isl_basic_set
*bset
);
239 __isl_give isl_set
*isl_ast_build_specialize(__isl_keep isl_ast_build
*build
,
240 __isl_take isl_set
*set
);
241 __isl_give isl_set
*isl_ast_build_compute_gist(
242 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
);
243 __isl_give isl_map
*isl_ast_build_compute_gist_map_domain(
244 __isl_keep isl_ast_build
*build
, __isl_take isl_map
*map
);
245 __isl_give isl_aff
*isl_ast_build_compute_gist_aff(
246 __isl_keep isl_ast_build
*build
, __isl_take isl_aff
*aff
);
247 __isl_give isl_pw_aff
*isl_ast_build_compute_gist_pw_aff(
248 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_aff
*pa
);
249 __isl_give isl_pw_multi_aff
*isl_ast_build_compute_gist_pw_multi_aff(
250 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
);
252 __isl_give isl_union_map
*isl_ast_build_substitute_values_union_map_domain(
253 __isl_keep isl_ast_build
*build
, __isl_take isl_union_map
*umap
);
255 int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build
*build
,
256 __isl_keep isl_aff
*aff
);
258 int isl_ast_build_has_stride(__isl_keep isl_ast_build
*build
, int pos
);
259 __isl_give isl_aff
*isl_ast_build_get_offset(__isl_keep isl_ast_build
*build
,
261 __isl_give isl_val
*isl_ast_build_get_stride(__isl_keep isl_ast_build
*build
,
263 __isl_give isl_set
*isl_ast_build_get_stride_constraint(
264 __isl_keep isl_ast_build
*build
);
265 __isl_give isl_multi_aff
*isl_ast_build_get_stride_expansion(
266 __isl_keep isl_ast_build
*build
);
268 void isl_ast_build_dump(__isl_keep isl_ast_build
*build
);
270 __isl_give isl_set
*isl_ast_build_get_option_domain(
271 __isl_keep isl_ast_build
*build
,
272 enum isl_ast_build_domain_type type
);
273 __isl_give isl_map
*isl_ast_build_get_separation_class(
274 __isl_keep isl_ast_build
*build
);
275 __isl_give isl_set
*isl_ast_build_eliminate(
276 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*domain
);
277 __isl_give isl_set
*isl_ast_build_eliminate_inner(
278 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
);
279 __isl_give isl_set
*isl_ast_build_eliminate_divs(
280 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
);
282 __isl_give isl_map
*isl_ast_build_map_to_iterator(
283 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
);
285 int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build
*build
);