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