/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_ast_build.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Copyright 2012-2013 Ecole Normale Superieure |
3 | | * Copyright 2014 INRIA Rocquencourt |
4 | | * |
5 | | * Use of this software is governed by the MIT license |
6 | | * |
7 | | * Written by Sven Verdoolaege, |
8 | | * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France |
9 | | * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt, |
10 | | * B.P. 105 - 78153 Le Chesnay, France |
11 | | */ |
12 | | |
13 | | #include <isl/id.h> |
14 | | #include <isl/val.h> |
15 | | #include <isl/space.h> |
16 | | #include <isl/map.h> |
17 | | #include <isl/aff.h> |
18 | | #include <isl/constraint.h> |
19 | | #include <isl/map.h> |
20 | | #include <isl/union_set.h> |
21 | | #include <isl/union_map.h> |
22 | | #include <isl_ast_build_private.h> |
23 | | #include <isl_ast_private.h> |
24 | | #include <isl_config.h> |
25 | | |
26 | | /* Construct a map that isolates the current dimension. |
27 | | * |
28 | | * Essentially, the current dimension of "set" is moved to the single output |
29 | | * dimension in the result, with the current dimension in the domain replaced |
30 | | * by an unconstrained variable. |
31 | | */ |
32 | | __isl_give isl_map *isl_ast_build_map_to_iterator( |
33 | | __isl_keep isl_ast_build *build, __isl_take isl_set *set) |
34 | 4.07k | { |
35 | 4.07k | isl_map *map; |
36 | 4.07k | |
37 | 4.07k | map = isl_map_from_domain(set); |
38 | 4.07k | map = isl_map_add_dims(map, isl_dim_out, 1); |
39 | 4.07k | |
40 | 4.07k | if (!build) |
41 | 0 | return isl_map_free(map); |
42 | 4.07k | |
43 | 4.07k | map = isl_map_equate(map, isl_dim_in, build->depth, isl_dim_out, 0); |
44 | 4.07k | map = isl_map_eliminate(map, isl_dim_in, build->depth, 1); |
45 | 4.07k | |
46 | 4.07k | return map; |
47 | 4.07k | } |
48 | | |
49 | | /* Initialize the information derived during the AST generation to default |
50 | | * values for a schedule domain in "space". |
51 | | * |
52 | | * We also check that the remaining fields are not NULL so that |
53 | | * the calling functions don't have to perform this test. |
54 | | */ |
55 | | static __isl_give isl_ast_build *isl_ast_build_init_derived( |
56 | | __isl_take isl_ast_build *build, __isl_take isl_space *space) |
57 | 1.08k | { |
58 | 1.08k | isl_ctx *ctx; |
59 | 1.08k | isl_vec *strides; |
60 | 1.08k | |
61 | 1.08k | build = isl_ast_build_cow(build); |
62 | 1.08k | if (!build || !build->domain) |
63 | 0 | goto error; |
64 | 1.08k | |
65 | 1.08k | ctx = isl_ast_build_get_ctx(build); |
66 | 1.08k | strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set)); |
67 | 1.08k | strides = isl_vec_set_si(strides, 1); |
68 | 1.08k | |
69 | 1.08k | isl_vec_free(build->strides); |
70 | 1.08k | build->strides = strides; |
71 | 1.08k | |
72 | 1.08k | space = isl_space_map_from_set(space); |
73 | 1.08k | isl_multi_aff_free(build->offsets); |
74 | 1.08k | build->offsets = isl_multi_aff_zero(isl_space_copy(space)); |
75 | 1.08k | isl_multi_aff_free(build->values); |
76 | 1.08k | build->values = isl_multi_aff_identity(isl_space_copy(space)); |
77 | 1.08k | isl_multi_aff_free(build->internal2input); |
78 | 1.08k | build->internal2input = isl_multi_aff_identity(space); |
79 | 1.08k | |
80 | 1.08k | if (!build->iterators || !build->domain || !build->generated || |
81 | 1.08k | !build->pending || !build->values || !build->internal2input || |
82 | 1.08k | !build->strides || !build->offsets || !build->options) |
83 | 0 | return isl_ast_build_free(build); |
84 | 1.08k | |
85 | 1.08k | return build; |
86 | 0 | error: |
87 | 0 | isl_space_free(space); |
88 | 0 | return isl_ast_build_free(build); |
89 | 1.08k | } |
90 | | |
91 | | /* Return an isl_id called "c%d", with "%d" set to "i". |
92 | | * If an isl_id with such a name already appears among the parameters |
93 | | * in build->domain, then adjust the name to "c%d_%d". |
94 | | */ |
95 | | static __isl_give isl_id *generate_name(isl_ctx *ctx, int i, |
96 | | __isl_keep isl_ast_build *build) |
97 | 941 | { |
98 | 941 | int j; |
99 | 941 | char name[23]; |
100 | 941 | isl_set *dom = build->domain; |
101 | 941 | |
102 | 941 | snprintf(name, sizeof(name), "c%d", i); |
103 | 941 | j = 0; |
104 | 941 | while (isl_set_find_dim_by_name(dom, isl_dim_param, name) >= 0) |
105 | 941 | snprintf(name, sizeof(name), "c%d_%d", i, j++); |
106 | 941 | return isl_id_alloc(ctx, name, NULL); |
107 | 941 | } |
108 | | |
109 | | /* Create an isl_ast_build with "set" as domain. |
110 | | * |
111 | | * The input set is usually a parameter domain, but we currently allow it to |
112 | | * be any kind of set. We set the domain of the returned isl_ast_build |
113 | | * to "set" and initialize all the other fields to default values. |
114 | | */ |
115 | | __isl_give isl_ast_build *isl_ast_build_from_context(__isl_take isl_set *set) |
116 | 617 | { |
117 | 617 | int i, n; |
118 | 617 | isl_ctx *ctx; |
119 | 617 | isl_space *space; |
120 | 617 | isl_ast_build *build; |
121 | 617 | |
122 | 617 | set = isl_set_compute_divs(set); |
123 | 617 | if (!set) |
124 | 0 | return NULL; |
125 | 617 | |
126 | 617 | ctx = isl_set_get_ctx(set); |
127 | 617 | |
128 | 617 | build = isl_calloc_type(ctx, isl_ast_build); |
129 | 617 | if (!build) |
130 | 0 | goto error; |
131 | 617 | |
132 | 617 | build->ref = 1; |
133 | 617 | build->domain = set; |
134 | 617 | build->generated = isl_set_copy(build->domain); |
135 | 617 | build->pending = isl_set_universe(isl_set_get_space(build->domain)); |
136 | 617 | build->options = isl_union_map_empty(isl_space_params_alloc(ctx, 0)); |
137 | 617 | n = isl_set_dim(set, isl_dim_set); |
138 | 617 | build->depth = n; |
139 | 617 | build->iterators = isl_id_list_alloc(ctx, n); |
140 | 617 | for (i = 0; i < n; ++i0 ) { |
141 | 0 | isl_id *id; |
142 | 0 | if (isl_set_has_dim_id(set, isl_dim_set, i)) |
143 | 0 | id = isl_set_get_dim_id(set, isl_dim_set, i); |
144 | 0 | else |
145 | 0 | id = generate_name(ctx, i, build); |
146 | 0 | build->iterators = isl_id_list_add(build->iterators, id); |
147 | 0 | } |
148 | 617 | space = isl_set_get_space(set); |
149 | 617 | if (isl_space_is_params(space)) |
150 | 617 | space = isl_space_set_from_params(space); |
151 | 617 | |
152 | 617 | return isl_ast_build_init_derived(build, space); |
153 | 0 | error: |
154 | 0 | isl_set_free(set); |
155 | 0 | return NULL; |
156 | 617 | } |
157 | | |
158 | | /* Create an isl_ast_build with a universe (parametric) context. |
159 | | */ |
160 | | __isl_give isl_ast_build *isl_ast_build_alloc(isl_ctx *ctx) |
161 | 1 | { |
162 | 1 | isl_space *space; |
163 | 1 | isl_set *context; |
164 | 1 | |
165 | 1 | space = isl_space_params_alloc(ctx, 0); |
166 | 1 | context = isl_set_universe(space); |
167 | 1 | |
168 | 1 | return isl_ast_build_from_context(context); |
169 | 1 | } |
170 | | |
171 | | __isl_give isl_ast_build *isl_ast_build_copy(__isl_keep isl_ast_build *build) |
172 | 52.4k | { |
173 | 52.4k | if (!build) |
174 | 0 | return NULL; |
175 | 52.4k | |
176 | 52.4k | build->ref++; |
177 | 52.4k | return build; |
178 | 52.4k | } |
179 | | |
180 | | __isl_give isl_ast_build *isl_ast_build_dup(__isl_keep isl_ast_build *build) |
181 | 36.5k | { |
182 | 36.5k | isl_ctx *ctx; |
183 | 36.5k | isl_ast_build *dup; |
184 | 36.5k | |
185 | 36.5k | if (!build) |
186 | 0 | return NULL; |
187 | 36.5k | |
188 | 36.5k | ctx = isl_ast_build_get_ctx(build); |
189 | 36.5k | dup = isl_calloc_type(ctx, isl_ast_build); |
190 | 36.5k | if (!dup) |
191 | 0 | return NULL; |
192 | 36.5k | |
193 | 36.5k | dup->ref = 1; |
194 | 36.5k | dup->outer_pos = build->outer_pos; |
195 | 36.5k | dup->depth = build->depth; |
196 | 36.5k | dup->iterators = isl_id_list_copy(build->iterators); |
197 | 36.5k | dup->domain = isl_set_copy(build->domain); |
198 | 36.5k | dup->generated = isl_set_copy(build->generated); |
199 | 36.5k | dup->pending = isl_set_copy(build->pending); |
200 | 36.5k | dup->values = isl_multi_aff_copy(build->values); |
201 | 36.5k | dup->internal2input = isl_multi_aff_copy(build->internal2input); |
202 | 36.5k | dup->value = isl_pw_aff_copy(build->value); |
203 | 36.5k | dup->strides = isl_vec_copy(build->strides); |
204 | 36.5k | dup->offsets = isl_multi_aff_copy(build->offsets); |
205 | 36.5k | dup->executed = isl_union_map_copy(build->executed); |
206 | 36.5k | dup->single_valued = build->single_valued; |
207 | 36.5k | dup->options = isl_union_map_copy(build->options); |
208 | 36.5k | dup->at_each_domain = build->at_each_domain; |
209 | 36.5k | dup->at_each_domain_user = build->at_each_domain_user; |
210 | 36.5k | dup->before_each_for = build->before_each_for; |
211 | 36.5k | dup->before_each_for_user = build->before_each_for_user; |
212 | 36.5k | dup->after_each_for = build->after_each_for; |
213 | 36.5k | dup->after_each_for_user = build->after_each_for_user; |
214 | 36.5k | dup->before_each_mark = build->before_each_mark; |
215 | 36.5k | dup->before_each_mark_user = build->before_each_mark_user; |
216 | 36.5k | dup->after_each_mark = build->after_each_mark; |
217 | 36.5k | dup->after_each_mark_user = build->after_each_mark_user; |
218 | 36.5k | dup->create_leaf = build->create_leaf; |
219 | 36.5k | dup->create_leaf_user = build->create_leaf_user; |
220 | 36.5k | dup->node = isl_schedule_node_copy(build->node); |
221 | 36.5k | if (build->loop_type) { |
222 | 33.8k | int i; |
223 | 33.8k | |
224 | 33.8k | dup->n = build->n; |
225 | 33.8k | dup->loop_type = isl_alloc_array(ctx, |
226 | 33.8k | enum isl_ast_loop_type, dup->n); |
227 | 33.8k | if (dup->n && !dup->loop_type) |
228 | 0 | return isl_ast_build_free(dup); |
229 | 121k | for (i = 0; 33.8k i < dup->n; ++i87.1k ) |
230 | 87.1k | dup->loop_type[i] = build->loop_type[i]; |
231 | 33.8k | } |
232 | 36.5k | |
233 | 36.5k | if (!dup->iterators || !dup->domain || !dup->generated || |
234 | 36.5k | !dup->pending || !dup->values || |
235 | 36.5k | !dup->strides || !dup->offsets || !dup->options || |
236 | 36.5k | (build->internal2input && !dup->internal2input36.4k ) || |
237 | 36.5k | (build->executed && !dup->executed33.4k ) || |
238 | 36.5k | (build->value && !dup->value6.71k ) || |
239 | 36.5k | (build->node && !dup->node23.1k )) |
240 | 0 | return isl_ast_build_free(dup); |
241 | 36.5k | |
242 | 36.5k | return dup; |
243 | 36.5k | } |
244 | | |
245 | | /* Align the parameters of "build" to those of "model", introducing |
246 | | * additional parameters if needed. |
247 | | */ |
248 | | __isl_give isl_ast_build *isl_ast_build_align_params( |
249 | | __isl_take isl_ast_build *build, __isl_take isl_space *model) |
250 | 31 | { |
251 | 31 | build = isl_ast_build_cow(build); |
252 | 31 | if (!build) |
253 | 0 | goto error; |
254 | 31 | |
255 | 31 | build->domain = isl_set_align_params(build->domain, |
256 | 31 | isl_space_copy(model)); |
257 | 31 | build->generated = isl_set_align_params(build->generated, |
258 | 31 | isl_space_copy(model)); |
259 | 31 | build->pending = isl_set_align_params(build->pending, |
260 | 31 | isl_space_copy(model)); |
261 | 31 | build->values = isl_multi_aff_align_params(build->values, |
262 | 31 | isl_space_copy(model)); |
263 | 31 | build->offsets = isl_multi_aff_align_params(build->offsets, |
264 | 31 | isl_space_copy(model)); |
265 | 31 | build->options = isl_union_map_align_params(build->options, |
266 | 31 | isl_space_copy(model)); |
267 | 31 | if (build->internal2input) { |
268 | 31 | build->internal2input = |
269 | 31 | isl_multi_aff_align_params(build->internal2input, |
270 | 31 | model); |
271 | 31 | if (!build->internal2input) |
272 | 0 | return isl_ast_build_free(build); |
273 | 0 | } else { |
274 | 0 | isl_space_free(model); |
275 | 0 | } |
276 | 31 | |
277 | 31 | if (!build->domain || !build->values || !build->offsets || |
278 | 31 | !build->options) |
279 | 0 | return isl_ast_build_free(build); |
280 | 31 | |
281 | 31 | return build; |
282 | 0 | error: |
283 | 0 | isl_space_free(model); |
284 | 0 | return NULL; |
285 | 31 | } |
286 | | |
287 | | __isl_give isl_ast_build *isl_ast_build_cow(__isl_take isl_ast_build *build) |
288 | 65.3k | { |
289 | 65.3k | if (!build) |
290 | 0 | return NULL; |
291 | 65.3k | |
292 | 65.3k | if (build->ref == 1) |
293 | 28.7k | return build; |
294 | 36.5k | build->ref--; |
295 | 36.5k | return isl_ast_build_dup(build); |
296 | 36.5k | } |
297 | | |
298 | | __isl_null isl_ast_build *isl_ast_build_free( |
299 | | __isl_take isl_ast_build *build) |
300 | 53.0k | { |
301 | 53.0k | if (!build) |
302 | 0 | return NULL; |
303 | 53.0k | |
304 | 53.0k | if (--build->ref > 0) |
305 | 15.8k | return NULL; |
306 | 37.1k | |
307 | 37.1k | isl_id_list_free(build->iterators); |
308 | 37.1k | isl_set_free(build->domain); |
309 | 37.1k | isl_set_free(build->generated); |
310 | 37.1k | isl_set_free(build->pending); |
311 | 37.1k | isl_multi_aff_free(build->values); |
312 | 37.1k | isl_multi_aff_free(build->internal2input); |
313 | 37.1k | isl_pw_aff_free(build->value); |
314 | 37.1k | isl_vec_free(build->strides); |
315 | 37.1k | isl_multi_aff_free(build->offsets); |
316 | 37.1k | isl_multi_aff_free(build->schedule_map); |
317 | 37.1k | isl_union_map_free(build->executed); |
318 | 37.1k | isl_union_map_free(build->options); |
319 | 37.1k | isl_schedule_node_free(build->node); |
320 | 37.1k | free(build->loop_type); |
321 | 37.1k | isl_set_free(build->isolated); |
322 | 37.1k | |
323 | 37.1k | free(build); |
324 | 37.1k | |
325 | 37.1k | return NULL; |
326 | 37.1k | } |
327 | | |
328 | | isl_ctx *isl_ast_build_get_ctx(__isl_keep isl_ast_build *build) |
329 | 69.3k | { |
330 | 69.3k | return build ? isl_set_get_ctx(build->domain) : NULL; |
331 | 69.3k | } |
332 | | |
333 | | /* Replace build->options by "options". |
334 | | */ |
335 | | __isl_give isl_ast_build *isl_ast_build_set_options( |
336 | | __isl_take isl_ast_build *build, __isl_take isl_union_map *options) |
337 | 3 | { |
338 | 3 | build = isl_ast_build_cow(build); |
339 | 3 | |
340 | 3 | if (!build || !options) |
341 | 0 | goto error; |
342 | 3 | |
343 | 3 | isl_union_map_free(build->options); |
344 | 3 | build->options = options; |
345 | 3 | |
346 | 3 | return build; |
347 | 0 | error: |
348 | 0 | isl_union_map_free(options); |
349 | 0 | return isl_ast_build_free(build); |
350 | 3 | } |
351 | | |
352 | | /* Set the iterators for the next code generation. |
353 | | * |
354 | | * If we still have some iterators left from the previous code generation |
355 | | * (if any) or if iterators have already been set by a previous |
356 | | * call to this function, then we remove them first. |
357 | | */ |
358 | | __isl_give isl_ast_build *isl_ast_build_set_iterators( |
359 | | __isl_take isl_ast_build *build, __isl_take isl_id_list *iterators) |
360 | 0 | { |
361 | 0 | int dim, n_it; |
362 | 0 |
|
363 | 0 | build = isl_ast_build_cow(build); |
364 | 0 | if (!build) |
365 | 0 | goto error; |
366 | 0 | |
367 | 0 | dim = isl_set_dim(build->domain, isl_dim_set); |
368 | 0 | n_it = isl_id_list_n_id(build->iterators); |
369 | 0 | if (n_it < dim) |
370 | 0 | isl_die(isl_ast_build_get_ctx(build), isl_error_internal, |
371 | 0 | "isl_ast_build in inconsistent state", goto error); |
372 | 0 | if (n_it > dim) |
373 | 0 | build->iterators = isl_id_list_drop(build->iterators, |
374 | 0 | dim, n_it - dim); |
375 | 0 | build->iterators = isl_id_list_concat(build->iterators, iterators); |
376 | 0 | if (!build->iterators) |
377 | 0 | return isl_ast_build_free(build); |
378 | 0 | |
379 | 0 | return build; |
380 | 0 | error: |
381 | 0 | isl_id_list_free(iterators); |
382 | 0 | return isl_ast_build_free(build); |
383 | 0 | } |
384 | | |
385 | | /* Set the "at_each_domain" callback of "build" to "fn". |
386 | | */ |
387 | | __isl_give isl_ast_build *isl_ast_build_set_at_each_domain( |
388 | | __isl_take isl_ast_build *build, |
389 | | __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node, |
390 | | __isl_keep isl_ast_build *build, void *user), void *user) |
391 | 459 | { |
392 | 459 | build = isl_ast_build_cow(build); |
393 | 459 | |
394 | 459 | if (!build) |
395 | 0 | return NULL; |
396 | 459 | |
397 | 459 | build->at_each_domain = fn; |
398 | 459 | build->at_each_domain_user = user; |
399 | 459 | |
400 | 459 | return build; |
401 | 459 | } |
402 | | |
403 | | /* Set the "before_each_for" callback of "build" to "fn". |
404 | | */ |
405 | | __isl_give isl_ast_build *isl_ast_build_set_before_each_for( |
406 | | __isl_take isl_ast_build *build, |
407 | | __isl_give isl_id *(*fn)(__isl_keep isl_ast_build *build, |
408 | | void *user), void *user) |
409 | 124 | { |
410 | 124 | build = isl_ast_build_cow(build); |
411 | 124 | |
412 | 124 | if (!build) |
413 | 0 | return NULL; |
414 | 124 | |
415 | 124 | build->before_each_for = fn; |
416 | 124 | build->before_each_for_user = user; |
417 | 124 | |
418 | 124 | return build; |
419 | 124 | } |
420 | | |
421 | | /* Set the "after_each_for" callback of "build" to "fn". |
422 | | */ |
423 | | __isl_give isl_ast_build *isl_ast_build_set_after_each_for( |
424 | | __isl_take isl_ast_build *build, |
425 | | __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node, |
426 | | __isl_keep isl_ast_build *build, void *user), void *user) |
427 | 124 | { |
428 | 124 | build = isl_ast_build_cow(build); |
429 | 124 | |
430 | 124 | if (!build) |
431 | 0 | return NULL; |
432 | 124 | |
433 | 124 | build->after_each_for = fn; |
434 | 124 | build->after_each_for_user = user; |
435 | 124 | |
436 | 124 | return build; |
437 | 124 | } |
438 | | |
439 | | /* Set the "before_each_mark" callback of "build" to "fn". |
440 | | */ |
441 | | __isl_give isl_ast_build *isl_ast_build_set_before_each_mark( |
442 | | __isl_take isl_ast_build *build, |
443 | | isl_stat (*fn)(__isl_keep isl_id *mark, __isl_keep isl_ast_build *build, |
444 | | void *user), void *user) |
445 | 123 | { |
446 | 123 | build = isl_ast_build_cow(build); |
447 | 123 | |
448 | 123 | if (!build) |
449 | 0 | return NULL; |
450 | 123 | |
451 | 123 | build->before_each_mark = fn; |
452 | 123 | build->before_each_mark_user = user; |
453 | 123 | |
454 | 123 | return build; |
455 | 123 | } |
456 | | |
457 | | /* Set the "after_each_mark" callback of "build" to "fn". |
458 | | */ |
459 | | __isl_give isl_ast_build *isl_ast_build_set_after_each_mark( |
460 | | __isl_take isl_ast_build *build, |
461 | | __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node, |
462 | | __isl_keep isl_ast_build *build, void *user), void *user) |
463 | 123 | { |
464 | 123 | build = isl_ast_build_cow(build); |
465 | 123 | |
466 | 123 | if (!build) |
467 | 0 | return NULL; |
468 | 123 | |
469 | 123 | build->after_each_mark = fn; |
470 | 123 | build->after_each_mark_user = user; |
471 | 123 | |
472 | 123 | return build; |
473 | 123 | } |
474 | | |
475 | | /* Set the "create_leaf" callback of "build" to "fn". |
476 | | */ |
477 | | __isl_give isl_ast_build *isl_ast_build_set_create_leaf( |
478 | | __isl_take isl_ast_build *build, |
479 | | __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_build *build, |
480 | | void *user), void *user) |
481 | 1 | { |
482 | 1 | build = isl_ast_build_cow(build); |
483 | 1 | |
484 | 1 | if (!build) |
485 | 0 | return NULL; |
486 | 1 | |
487 | 1 | build->create_leaf = fn; |
488 | 1 | build->create_leaf_user = user; |
489 | 1 | |
490 | 1 | return build; |
491 | 1 | } |
492 | | |
493 | | /* Clear all information that is specific to this code generation |
494 | | * and that is (probably) not meaningful to any nested code generation. |
495 | | */ |
496 | | __isl_give isl_ast_build *isl_ast_build_clear_local_info( |
497 | | __isl_take isl_ast_build *build) |
498 | 3 | { |
499 | 3 | isl_space *space; |
500 | 3 | |
501 | 3 | build = isl_ast_build_cow(build); |
502 | 3 | if (!build) |
503 | 0 | return NULL; |
504 | 3 | |
505 | 3 | space = isl_union_map_get_space(build->options); |
506 | 3 | isl_union_map_free(build->options); |
507 | 3 | build->options = isl_union_map_empty(space); |
508 | 3 | |
509 | 3 | build->at_each_domain = NULL; |
510 | 3 | build->at_each_domain_user = NULL; |
511 | 3 | build->before_each_for = NULL; |
512 | 3 | build->before_each_for_user = NULL; |
513 | 3 | build->after_each_for = NULL; |
514 | 3 | build->after_each_for_user = NULL; |
515 | 3 | build->before_each_mark = NULL; |
516 | 3 | build->before_each_mark_user = NULL; |
517 | 3 | build->after_each_mark = NULL; |
518 | 3 | build->after_each_mark_user = NULL; |
519 | 3 | build->create_leaf = NULL; |
520 | 3 | build->create_leaf_user = NULL; |
521 | 3 | |
522 | 3 | if (!build->options) |
523 | 0 | return isl_ast_build_free(build); |
524 | 3 | |
525 | 3 | return build; |
526 | 3 | } |
527 | | |
528 | | /* Have any loops been eliminated? |
529 | | * That is, do any of the original schedule dimensions have a fixed |
530 | | * value that has been substituted? |
531 | | */ |
532 | | static int any_eliminated(isl_ast_build *build) |
533 | 3.33k | { |
534 | 3.33k | int i; |
535 | 3.33k | |
536 | 4.38k | for (i = 0; i < build->depth; ++i1.05k ) |
537 | 1.81k | if (isl_ast_build_has_affine_value(build, i)) |
538 | 758 | return 1; |
539 | 3.33k | |
540 | 3.33k | return 02.57k ; |
541 | 3.33k | } |
542 | | |
543 | | /* Clear build->schedule_map. |
544 | | * This function should be called whenever anything that might affect |
545 | | * the result of isl_ast_build_get_schedule_map_multi_aff changes. |
546 | | * In particular, it should be called when the depth is changed or |
547 | | * when an iterator is determined to have a fixed value. |
548 | | */ |
549 | | static void isl_ast_build_reset_schedule_map(__isl_keep isl_ast_build *build) |
550 | 7.38k | { |
551 | 7.38k | if (!build) |
552 | 0 | return; |
553 | 7.38k | isl_multi_aff_free(build->schedule_map); |
554 | 7.38k | build->schedule_map = NULL; |
555 | 7.38k | } |
556 | | |
557 | | /* Do we need a (non-trivial) schedule map? |
558 | | * That is, is the internal schedule space different from |
559 | | * the external schedule space? |
560 | | * |
561 | | * The internal and external schedule spaces are only the same |
562 | | * if code has been generated for the entire schedule and if none |
563 | | * of the loops have been eliminated. |
564 | | */ |
565 | | __isl_give int isl_ast_build_need_schedule_map(__isl_keep isl_ast_build *build) |
566 | 3.45k | { |
567 | 3.45k | int dim; |
568 | 3.45k | |
569 | 3.45k | if (!build) |
570 | 0 | return -1; |
571 | 3.45k | |
572 | 3.45k | dim = isl_set_dim(build->domain, isl_dim_set); |
573 | 3.45k | return build->depth != dim || any_eliminated(build)3.33k ; |
574 | 3.45k | } |
575 | | |
576 | | /* Return a mapping from the internal schedule space to the external |
577 | | * schedule space in the form of an isl_multi_aff. |
578 | | * The internal schedule space originally corresponds to that of the |
579 | | * input schedule. This may change during the code generation if |
580 | | * if isl_ast_build_insert_dim is ever called. |
581 | | * The external schedule space corresponds to the |
582 | | * loops that have been generated. |
583 | | * |
584 | | * Currently, the only difference between the internal schedule domain |
585 | | * and the external schedule domain is that some dimensions are projected |
586 | | * out in the external schedule domain. In particular, the dimensions |
587 | | * for which no code has been generated yet and the dimensions that correspond |
588 | | * to eliminated loops. |
589 | | * |
590 | | * We cache a copy of the schedule_map in build->schedule_map. |
591 | | * The cache is cleared through isl_ast_build_reset_schedule_map |
592 | | * whenever anything changes that might affect the result of this function. |
593 | | */ |
594 | | __isl_give isl_multi_aff *isl_ast_build_get_schedule_map_multi_aff( |
595 | | __isl_keep isl_ast_build *build) |
596 | 503 | { |
597 | 503 | isl_space *space; |
598 | 503 | isl_multi_aff *ma; |
599 | 503 | |
600 | 503 | if (!build) |
601 | 0 | return NULL; |
602 | 503 | if (build->schedule_map) |
603 | 325 | return isl_multi_aff_copy(build->schedule_map); |
604 | 178 | |
605 | 178 | space = isl_ast_build_get_space(build, 1); |
606 | 178 | space = isl_space_map_from_set(space); |
607 | 178 | ma = isl_multi_aff_identity(space); |
608 | 178 | if (isl_ast_build_need_schedule_map(build)) { |
609 | 178 | int i; |
610 | 178 | int dim = isl_set_dim(build->domain, isl_dim_set); |
611 | 178 | ma = isl_multi_aff_drop_dims(ma, isl_dim_out, |
612 | 178 | build->depth, dim - build->depth); |
613 | 938 | for (i = build->depth - 1; i >= 0; --i760 ) |
614 | 760 | if (isl_ast_build_has_affine_value(build, i)) |
615 | 326 | ma = isl_multi_aff_drop_dims(ma, |
616 | 326 | isl_dim_out, i, 1); |
617 | 178 | } |
618 | 178 | |
619 | 178 | build->schedule_map = ma; |
620 | 178 | return isl_multi_aff_copy(build->schedule_map); |
621 | 178 | } |
622 | | |
623 | | /* Return a mapping from the internal schedule space to the external |
624 | | * schedule space in the form of an isl_map. |
625 | | */ |
626 | | __isl_give isl_map *isl_ast_build_get_schedule_map( |
627 | | __isl_keep isl_ast_build *build) |
628 | 299 | { |
629 | 299 | isl_multi_aff *ma; |
630 | 299 | |
631 | 299 | ma = isl_ast_build_get_schedule_map_multi_aff(build); |
632 | 299 | return isl_map_from_multi_aff(ma); |
633 | 299 | } |
634 | | |
635 | | /* Return the position of the dimension in build->domain for which |
636 | | * an AST node is currently being generated. |
637 | | */ |
638 | | int isl_ast_build_get_depth(__isl_keep isl_ast_build *build) |
639 | 38.6k | { |
640 | 38.6k | return build ? build->depth : -10 ; |
641 | 38.6k | } |
642 | | |
643 | | /* Prepare for generating code for the next level. |
644 | | * In particular, increase the depth and reset any information |
645 | | * that is local to the current depth. |
646 | | */ |
647 | | __isl_give isl_ast_build *isl_ast_build_increase_depth( |
648 | | __isl_take isl_ast_build *build) |
649 | 4.06k | { |
650 | 4.06k | build = isl_ast_build_cow(build); |
651 | 4.06k | if (!build) |
652 | 0 | return NULL; |
653 | 4.06k | build->depth++; |
654 | 4.06k | isl_ast_build_reset_schedule_map(build); |
655 | 4.06k | build->value = isl_pw_aff_free(build->value); |
656 | 4.06k | return build; |
657 | 4.06k | } |
658 | | |
659 | | void isl_ast_build_dump(__isl_keep isl_ast_build *build) |
660 | 0 | { |
661 | 0 | if (!build) |
662 | 0 | return; |
663 | 0 | |
664 | 0 | fprintf(stderr, "domain: "); |
665 | 0 | isl_set_dump(build->domain); |
666 | 0 | fprintf(stderr, "generated: "); |
667 | 0 | isl_set_dump(build->generated); |
668 | 0 | fprintf(stderr, "pending: "); |
669 | 0 | isl_set_dump(build->pending); |
670 | 0 | fprintf(stderr, "iterators: "); |
671 | 0 | isl_id_list_dump(build->iterators); |
672 | 0 | fprintf(stderr, "values: "); |
673 | 0 | isl_multi_aff_dump(build->values); |
674 | 0 | if (build->value) { |
675 | 0 | fprintf(stderr, "value: "); |
676 | 0 | isl_pw_aff_dump(build->value); |
677 | 0 | } |
678 | 0 | fprintf(stderr, "strides: "); |
679 | 0 | isl_vec_dump(build->strides); |
680 | 0 | fprintf(stderr, "offsets: "); |
681 | 0 | isl_multi_aff_dump(build->offsets); |
682 | 0 | fprintf(stderr, "internal2input: "); |
683 | 0 | isl_multi_aff_dump(build->internal2input); |
684 | 0 | } |
685 | | |
686 | | /* Initialize "build" for AST construction in schedule space "space" |
687 | | * in the case that build->domain is a parameter set. |
688 | | * |
689 | | * build->iterators is assumed to have been updated already. |
690 | | */ |
691 | | static __isl_give isl_ast_build *isl_ast_build_init( |
692 | | __isl_take isl_ast_build *build, __isl_take isl_space *space) |
693 | 464 | { |
694 | 464 | isl_set *set; |
695 | 464 | |
696 | 464 | build = isl_ast_build_cow(build); |
697 | 464 | if (!build) |
698 | 0 | goto error; |
699 | 464 | |
700 | 464 | set = isl_set_universe(isl_space_copy(space)); |
701 | 464 | build->domain = isl_set_intersect_params(isl_set_copy(set), |
702 | 464 | build->domain); |
703 | 464 | build->pending = isl_set_intersect_params(isl_set_copy(set), |
704 | 464 | build->pending); |
705 | 464 | build->generated = isl_set_intersect_params(set, build->generated); |
706 | 464 | |
707 | 464 | return isl_ast_build_init_derived(build, space); |
708 | 0 | error: |
709 | 0 | isl_ast_build_free(build); |
710 | 0 | isl_space_free(space); |
711 | 0 | return NULL; |
712 | 464 | } |
713 | | |
714 | | /* Assign "aff" to *user and return -1, effectively extracting |
715 | | * the first (and presumably only) affine expression in the isl_pw_aff |
716 | | * on which this function is used. |
717 | | */ |
718 | | static isl_stat extract_single_piece(__isl_take isl_set *set, |
719 | | __isl_take isl_aff *aff, void *user) |
720 | 3.31k | { |
721 | 3.31k | isl_aff **p = user; |
722 | 3.31k | |
723 | 3.31k | *p = aff; |
724 | 3.31k | isl_set_free(set); |
725 | 3.31k | |
726 | 3.31k | return isl_stat_error; |
727 | 3.31k | } |
728 | | |
729 | | /* Intersect "set" with the stride constraint of "build", if any. |
730 | | */ |
731 | | static __isl_give isl_set *intersect_stride_constraint(__isl_take isl_set *set, |
732 | | __isl_keep isl_ast_build *build) |
733 | 4.06k | { |
734 | 4.06k | isl_set *stride; |
735 | 4.06k | |
736 | 4.06k | if (!build) |
737 | 0 | return isl_set_free(set); |
738 | 4.06k | if (!isl_ast_build_has_stride(build, build->depth)) |
739 | 4.05k | return set; |
740 | 15 | |
741 | 15 | stride = isl_ast_build_get_stride_constraint(build); |
742 | 15 | return isl_set_intersect(set, stride); |
743 | 15 | } |
744 | | |
745 | | /* Check if the given bounds on the current dimension (together with |
746 | | * the stride constraint, if any) imply that |
747 | | * this current dimension attains only a single value (in terms of |
748 | | * parameters and outer dimensions). |
749 | | * If so, we record it in build->value. |
750 | | * If, moreover, this value can be represented as a single affine expression, |
751 | | * then we also update build->values, effectively marking the current |
752 | | * dimension as "eliminated". |
753 | | * |
754 | | * When computing the gist of the fixed value that can be represented |
755 | | * as a single affine expression, it is important to only take into |
756 | | * account the domain constraints in the original AST build and |
757 | | * not the domain of the affine expression itself. |
758 | | * Otherwise, a [i/3] is changed into a i/3 because we know that i |
759 | | * is a multiple of 3, but then we end up not expressing anywhere |
760 | | * in the context that i is a multiple of 3. |
761 | | */ |
762 | | static __isl_give isl_ast_build *update_values( |
763 | | __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds) |
764 | 4.06k | { |
765 | 4.06k | int sv; |
766 | 4.06k | isl_pw_multi_aff *pma; |
767 | 4.06k | isl_aff *aff = NULL; |
768 | 4.06k | isl_map *it_map; |
769 | 4.06k | isl_set *set; |
770 | 4.06k | |
771 | 4.06k | set = isl_set_from_basic_set(bounds); |
772 | 4.06k | set = isl_set_intersect(set, isl_set_copy(build->domain)); |
773 | 4.06k | set = intersect_stride_constraint(set, build); |
774 | 4.06k | it_map = isl_ast_build_map_to_iterator(build, set); |
775 | 4.06k | |
776 | 4.06k | sv = isl_map_is_single_valued(it_map); |
777 | 4.06k | if (sv < 0) |
778 | 0 | build = isl_ast_build_free(build); |
779 | 4.06k | if (!build || !sv) { |
780 | 749 | isl_map_free(it_map); |
781 | 749 | return build; |
782 | 749 | } |
783 | 3.31k | |
784 | 3.31k | pma = isl_pw_multi_aff_from_map(it_map); |
785 | 3.31k | build->value = isl_pw_multi_aff_get_pw_aff(pma, 0); |
786 | 3.31k | build->value = isl_ast_build_compute_gist_pw_aff(build, build->value); |
787 | 3.31k | build->value = isl_pw_aff_coalesce(build->value); |
788 | 3.31k | isl_pw_multi_aff_free(pma); |
789 | 3.31k | |
790 | 3.31k | if (!build->value) |
791 | 0 | return isl_ast_build_free(build); |
792 | 3.31k | |
793 | 3.31k | if (isl_pw_aff_n_piece(build->value) != 1) |
794 | 0 | return build; |
795 | 3.31k | |
796 | 3.31k | isl_pw_aff_foreach_piece(build->value, &extract_single_piece, &aff); |
797 | 3.31k | |
798 | 3.31k | build->values = isl_multi_aff_set_aff(build->values, build->depth, aff); |
799 | 3.31k | if (!build->values) |
800 | 0 | return isl_ast_build_free(build); |
801 | 3.31k | isl_ast_build_reset_schedule_map(build); |
802 | 3.31k | return build; |
803 | 3.31k | } |
804 | | |
805 | | /* Update the AST build based on the given loop bounds for |
806 | | * the current dimension and the stride information available in the build. |
807 | | * |
808 | | * We first make sure that the bounds do not refer to any iterators |
809 | | * that have already been eliminated. |
810 | | * Then, we check if the bounds imply that the current iterator |
811 | | * has a fixed value. |
812 | | * If they do and if this fixed value can be expressed as a single |
813 | | * affine expression, we eliminate the iterators from the bounds. |
814 | | * Note that we cannot simply plug in this single value using |
815 | | * isl_basic_set_preimage_multi_aff as the single value may only |
816 | | * be defined on a subset of the domain. Plugging in the value |
817 | | * would restrict the build domain to this subset, while this |
818 | | * restriction may not be reflected in the generated code. |
819 | | * Finally, we intersect build->domain with the updated bounds. |
820 | | * We also add the stride constraint unless we have been able |
821 | | * to find a fixed value expressed as a single affine expression. |
822 | | * |
823 | | * Note that the check for a fixed value in update_values requires |
824 | | * us to intersect the bounds with the current build domain. |
825 | | * When we intersect build->domain with the updated bounds in |
826 | | * the final step, we make sure that these updated bounds have |
827 | | * not been intersected with the old build->domain. |
828 | | * Otherwise, we would indirectly intersect the build domain with itself, |
829 | | * which can lead to inefficiencies, in particular if the build domain |
830 | | * contains any unknown divs. |
831 | | * |
832 | | * The pending and generated sets are not updated by this function to |
833 | | * match the updated domain. |
834 | | * The caller still needs to call isl_ast_build_set_pending_generated. |
835 | | */ |
836 | | __isl_give isl_ast_build *isl_ast_build_set_loop_bounds( |
837 | | __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds) |
838 | 4.06k | { |
839 | 4.06k | isl_set *set; |
840 | 4.06k | |
841 | 4.06k | build = isl_ast_build_cow(build); |
842 | 4.06k | if (!build) |
843 | 0 | goto error; |
844 | 4.06k | |
845 | 4.06k | build = update_values(build, isl_basic_set_copy(bounds)); |
846 | 4.06k | if (!build) |
847 | 0 | goto error; |
848 | 4.06k | set = isl_set_from_basic_set(isl_basic_set_copy(bounds)); |
849 | 4.06k | if (isl_ast_build_has_affine_value(build, build->depth)) { |
850 | 3.31k | set = isl_set_eliminate(set, isl_dim_set, build->depth, 1); |
851 | 3.31k | set = isl_set_compute_divs(set); |
852 | 3.31k | build->pending = isl_set_intersect(build->pending, |
853 | 3.31k | isl_set_copy(set)); |
854 | 3.31k | build->domain = isl_set_intersect(build->domain, set); |
855 | 3.31k | } else { |
856 | 749 | build->domain = isl_set_intersect(build->domain, set); |
857 | 749 | build = isl_ast_build_include_stride(build); |
858 | 749 | if (!build) |
859 | 0 | goto error; |
860 | 4.06k | } |
861 | 4.06k | isl_basic_set_free(bounds); |
862 | 4.06k | |
863 | 4.06k | if (!build->domain || !build->pending || !build->generated) |
864 | 0 | return isl_ast_build_free(build); |
865 | 4.06k | |
866 | 4.06k | return build; |
867 | 0 | error: |
868 | 0 | isl_ast_build_free(build); |
869 | 0 | isl_basic_set_free(bounds); |
870 | 0 | return NULL; |
871 | 4.06k | } |
872 | | |
873 | | /* Update the pending and generated sets of "build" according to "bounds". |
874 | | * If the build has an affine value at the current depth, |
875 | | * then isl_ast_build_set_loop_bounds has already set the pending set. |
876 | | * Otherwise, do it here. |
877 | | */ |
878 | | __isl_give isl_ast_build *isl_ast_build_set_pending_generated( |
879 | | __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds) |
880 | 4.06k | { |
881 | 4.06k | isl_basic_set *generated, *pending; |
882 | 4.06k | |
883 | 4.06k | if (!build) |
884 | 0 | goto error; |
885 | 4.06k | |
886 | 4.06k | if (isl_ast_build_has_affine_value(build, build->depth)) { |
887 | 3.31k | isl_basic_set_free(bounds); |
888 | 3.31k | return build; |
889 | 3.31k | } |
890 | 749 | |
891 | 749 | build = isl_ast_build_cow(build); |
892 | 749 | if (!build) |
893 | 0 | goto error; |
894 | 749 | |
895 | 749 | pending = isl_basic_set_copy(bounds); |
896 | 749 | pending = isl_basic_set_drop_constraints_involving_dims(pending, |
897 | 749 | isl_dim_set, build->depth, 1); |
898 | 749 | build->pending = isl_set_intersect(build->pending, |
899 | 749 | isl_set_from_basic_set(pending)); |
900 | 749 | generated = bounds; |
901 | 749 | generated = isl_basic_set_drop_constraints_not_involving_dims( |
902 | 749 | generated, isl_dim_set, build->depth, 1); |
903 | 749 | build->generated = isl_set_intersect(build->generated, |
904 | 749 | isl_set_from_basic_set(generated)); |
905 | 749 | |
906 | 749 | if (!build->pending || !build->generated) |
907 | 0 | return isl_ast_build_free(build); |
908 | 749 | |
909 | 749 | return build; |
910 | 0 | error: |
911 | 0 | isl_ast_build_free(build); |
912 | 0 | isl_basic_set_free(bounds); |
913 | 0 | return NULL; |
914 | 749 | } |
915 | | |
916 | | /* Intersect build->domain with "set", where "set" is specified |
917 | | * in terms of the internal schedule domain. |
918 | | */ |
919 | | static __isl_give isl_ast_build *isl_ast_build_restrict_internal( |
920 | | __isl_take isl_ast_build *build, __isl_take isl_set *set) |
921 | 16.8k | { |
922 | 16.8k | build = isl_ast_build_cow(build); |
923 | 16.8k | if (!build) |
924 | 0 | goto error; |
925 | 16.8k | |
926 | 16.8k | set = isl_set_compute_divs(set); |
927 | 16.8k | build->domain = isl_set_intersect(build->domain, set); |
928 | 16.8k | build->domain = isl_set_coalesce(build->domain); |
929 | 16.8k | |
930 | 16.8k | if (!build->domain) |
931 | 0 | return isl_ast_build_free(build); |
932 | 16.8k | |
933 | 16.8k | return build; |
934 | 0 | error: |
935 | 0 | isl_ast_build_free(build); |
936 | 0 | isl_set_free(set); |
937 | 0 | return NULL; |
938 | 16.8k | } |
939 | | |
940 | | /* Intersect build->generated and build->domain with "set", |
941 | | * where "set" is specified in terms of the internal schedule domain. |
942 | | */ |
943 | | __isl_give isl_ast_build *isl_ast_build_restrict_generated( |
944 | | __isl_take isl_ast_build *build, __isl_take isl_set *set) |
945 | 16.8k | { |
946 | 16.8k | set = isl_set_compute_divs(set); |
947 | 16.8k | build = isl_ast_build_restrict_internal(build, isl_set_copy(set)); |
948 | 16.8k | build = isl_ast_build_cow(build); |
949 | 16.8k | if (!build) |
950 | 0 | goto error; |
951 | 16.8k | |
952 | 16.8k | build->generated = isl_set_intersect(build->generated, set); |
953 | 16.8k | build->generated = isl_set_coalesce(build->generated); |
954 | 16.8k | |
955 | 16.8k | if (!build->generated) |
956 | 0 | return isl_ast_build_free(build); |
957 | 16.8k | |
958 | 16.8k | return build; |
959 | 0 | error: |
960 | 0 | isl_ast_build_free(build); |
961 | 0 | isl_set_free(set); |
962 | 0 | return NULL; |
963 | 16.8k | } |
964 | | |
965 | | /* Replace the set of pending constraints by "guard", which is then |
966 | | * no longer considered as pending. |
967 | | * That is, add "guard" to the generated constraints and clear all pending |
968 | | * constraints, making the domain equal to the generated constraints. |
969 | | */ |
970 | | __isl_give isl_ast_build *isl_ast_build_replace_pending_by_guard( |
971 | | __isl_take isl_ast_build *build, __isl_take isl_set *guard) |
972 | 7.11k | { |
973 | 7.11k | build = isl_ast_build_restrict_generated(build, guard); |
974 | 7.11k | build = isl_ast_build_cow(build); |
975 | 7.11k | if (!build) |
976 | 0 | return NULL; |
977 | 7.11k | |
978 | 7.11k | isl_set_free(build->domain); |
979 | 7.11k | build->domain = isl_set_copy(build->generated); |
980 | 7.11k | isl_set_free(build->pending); |
981 | 7.11k | build->pending = isl_set_universe(isl_set_get_space(build->domain)); |
982 | 7.11k | |
983 | 7.11k | if (!build->pending) |
984 | 0 | return isl_ast_build_free(build); |
985 | 7.11k | |
986 | 7.11k | return build; |
987 | 7.11k | } |
988 | | |
989 | | /* Intersect build->domain with "set", where "set" is specified |
990 | | * in terms of the external schedule domain. |
991 | | */ |
992 | | __isl_give isl_ast_build *isl_ast_build_restrict( |
993 | | __isl_take isl_ast_build *build, __isl_take isl_set *set) |
994 | 12 | { |
995 | 12 | if (isl_set_is_params(set)) |
996 | 0 | return isl_ast_build_restrict_generated(build, set); |
997 | 12 | |
998 | 12 | if (isl_ast_build_need_schedule_map(build)) { |
999 | 7 | isl_multi_aff *ma; |
1000 | 7 | ma = isl_ast_build_get_schedule_map_multi_aff(build); |
1001 | 7 | set = isl_set_preimage_multi_aff(set, ma); |
1002 | 7 | } |
1003 | 12 | return isl_ast_build_restrict_generated(build, set); |
1004 | 12 | } |
1005 | | |
1006 | | /* Replace build->executed by "executed". |
1007 | | */ |
1008 | | __isl_give isl_ast_build *isl_ast_build_set_executed( |
1009 | | __isl_take isl_ast_build *build, __isl_take isl_union_map *executed) |
1010 | 6.47k | { |
1011 | 6.47k | build = isl_ast_build_cow(build); |
1012 | 6.47k | if (!build) |
1013 | 0 | goto error; |
1014 | 6.47k | |
1015 | 6.47k | isl_union_map_free(build->executed); |
1016 | 6.47k | build->executed = executed; |
1017 | 6.47k | |
1018 | 6.47k | return build; |
1019 | 0 | error: |
1020 | 0 | isl_ast_build_free(build); |
1021 | 0 | isl_union_map_free(executed); |
1022 | 0 | return NULL; |
1023 | 6.47k | } |
1024 | | |
1025 | | /* Does "build" point to a band node? |
1026 | | * That is, are we currently handling a band node inside a schedule tree? |
1027 | | */ |
1028 | | int isl_ast_build_has_schedule_node(__isl_keep isl_ast_build *build) |
1029 | 7.14k | { |
1030 | 7.14k | if (!build) |
1031 | 0 | return -1; |
1032 | 7.14k | return build->node != NULL; |
1033 | 7.14k | } |
1034 | | |
1035 | | /* Return a copy of the band node that "build" refers to. |
1036 | | */ |
1037 | | __isl_give isl_schedule_node *isl_ast_build_get_schedule_node( |
1038 | | __isl_keep isl_ast_build *build) |
1039 | 2.33k | { |
1040 | 2.33k | if (!build) |
1041 | 0 | return NULL; |
1042 | 2.33k | return isl_schedule_node_copy(build->node); |
1043 | 2.33k | } |
1044 | | |
1045 | | /* Extract the loop AST generation types for the members of build->node |
1046 | | * and store them in build->loop_type. |
1047 | | */ |
1048 | | static __isl_give isl_ast_build *extract_loop_types( |
1049 | | __isl_take isl_ast_build *build) |
1050 | 653 | { |
1051 | 653 | int i; |
1052 | 653 | isl_ctx *ctx; |
1053 | 653 | isl_schedule_node *node; |
1054 | 653 | |
1055 | 653 | if (!build) |
1056 | 0 | return NULL; |
1057 | 653 | ctx = isl_ast_build_get_ctx(build); |
1058 | 653 | if (!build->node) |
1059 | 653 | isl_die0 (ctx, isl_error_internal, "missing AST node", |
1060 | 653 | return isl_ast_build_free(build)); |
1061 | 653 | |
1062 | 653 | free(build->loop_type); |
1063 | 653 | build->n = isl_schedule_node_band_n_member(build->node); |
1064 | 653 | build->loop_type = isl_alloc_array(ctx, |
1065 | 653 | enum isl_ast_loop_type, build->n); |
1066 | 653 | if (build->n && !build->loop_type) |
1067 | 0 | return isl_ast_build_free(build); |
1068 | 653 | node = build->node; |
1069 | 1.51k | for (i = 0; i < build->n; ++i861 ) |
1070 | 861 | build->loop_type[i] = |
1071 | 861 | isl_schedule_node_band_member_get_ast_loop_type(node, i); |
1072 | 653 | |
1073 | 653 | return build; |
1074 | 653 | } |
1075 | | |
1076 | | /* Replace the band node that "build" refers to by "node" and |
1077 | | * extract the corresponding loop AST generation types. |
1078 | | */ |
1079 | | __isl_give isl_ast_build *isl_ast_build_set_schedule_node( |
1080 | | __isl_take isl_ast_build *build, |
1081 | | __isl_take isl_schedule_node *node) |
1082 | 653 | { |
1083 | 653 | build = isl_ast_build_cow(build); |
1084 | 653 | if (!build || !node) |
1085 | 0 | goto error; |
1086 | 653 | |
1087 | 653 | isl_schedule_node_free(build->node); |
1088 | 653 | build->node = node; |
1089 | 653 | |
1090 | 653 | build = extract_loop_types(build); |
1091 | 653 | |
1092 | 653 | return build; |
1093 | 0 | error: |
1094 | 0 | isl_ast_build_free(build); |
1095 | 0 | isl_schedule_node_free(node); |
1096 | 0 | return NULL; |
1097 | 653 | } |
1098 | | |
1099 | | /* Remove any reference to a band node from "build". |
1100 | | */ |
1101 | | __isl_give isl_ast_build *isl_ast_build_reset_schedule_node( |
1102 | | __isl_take isl_ast_build *build) |
1103 | 2.20k | { |
1104 | 2.20k | build = isl_ast_build_cow(build); |
1105 | 2.20k | if (!build) |
1106 | 0 | return NULL; |
1107 | 2.20k | |
1108 | 2.20k | isl_schedule_node_free(build->node); |
1109 | 2.20k | build->node = NULL; |
1110 | 2.20k | |
1111 | 2.20k | return build; |
1112 | 2.20k | } |
1113 | | |
1114 | | /* Return a copy of the current schedule domain. |
1115 | | */ |
1116 | | __isl_give isl_set *isl_ast_build_get_domain(__isl_keep isl_ast_build *build) |
1117 | 8.70k | { |
1118 | 8.70k | return build ? isl_set_copy(build->domain) : NULL; |
1119 | 8.70k | } |
1120 | | |
1121 | | /* Return a copy of the set of pending constraints. |
1122 | | */ |
1123 | | __isl_give isl_set *isl_ast_build_get_pending( |
1124 | | __isl_keep isl_ast_build *build) |
1125 | 6.30k | { |
1126 | 6.30k | return build ? isl_set_copy(build->pending) : NULL; |
1127 | 6.30k | } |
1128 | | |
1129 | | /* Return a copy of the set of generated constraints. |
1130 | | */ |
1131 | | __isl_give isl_set *isl_ast_build_get_generated( |
1132 | | __isl_keep isl_ast_build *build) |
1133 | 7.54k | { |
1134 | 7.54k | return build ? isl_set_copy(build->generated) : NULL; |
1135 | 7.54k | } |
1136 | | |
1137 | | /* Return a copy of the map from the internal schedule domain |
1138 | | * to the original input schedule domain. |
1139 | | */ |
1140 | | __isl_give isl_multi_aff *isl_ast_build_get_internal2input( |
1141 | | __isl_keep isl_ast_build *build) |
1142 | 0 | { |
1143 | 0 | return build ? isl_multi_aff_copy(build->internal2input) : NULL; |
1144 | 0 | } |
1145 | | |
1146 | | /* Return the number of variables of the given type |
1147 | | * in the (internal) schedule space. |
1148 | | */ |
1149 | | unsigned isl_ast_build_dim(__isl_keep isl_ast_build *build, |
1150 | | enum isl_dim_type type) |
1151 | 6.05k | { |
1152 | 6.05k | if (!build) |
1153 | 0 | return 0; |
1154 | 6.05k | return isl_set_dim(build->domain, type); |
1155 | 6.05k | } |
1156 | | |
1157 | | /* Return the (schedule) space of "build". |
1158 | | * |
1159 | | * If "internal" is set, then this space is the space of the internal |
1160 | | * representation of the entire schedule, including those parts for |
1161 | | * which no code has been generated yet. |
1162 | | * |
1163 | | * If "internal" is not set, then this space is the external representation |
1164 | | * of the loops generated so far. |
1165 | | */ |
1166 | | __isl_give isl_space *isl_ast_build_get_space(__isl_keep isl_ast_build *build, |
1167 | | int internal) |
1168 | 16.7k | { |
1169 | 16.7k | int i; |
1170 | 16.7k | int dim; |
1171 | 16.7k | isl_space *space; |
1172 | 16.7k | |
1173 | 16.7k | if (!build) |
1174 | 0 | return NULL; |
1175 | 16.7k | |
1176 | 16.7k | space = isl_set_get_space(build->domain); |
1177 | 16.7k | if (internal) |
1178 | 15.7k | return space; |
1179 | 1.01k | |
1180 | 1.01k | if (!isl_ast_build_need_schedule_map(build)) |
1181 | 822 | return space; |
1182 | 196 | |
1183 | 196 | dim = isl_set_dim(build->domain, isl_dim_set); |
1184 | 196 | space = isl_space_drop_dims(space, isl_dim_set, |
1185 | 196 | build->depth, dim - build->depth); |
1186 | 1.61k | for (i = build->depth - 1; i >= 0; --i1.41k ) { |
1187 | 1.41k | isl_bool affine = isl_ast_build_has_affine_value(build, i); |
1188 | 1.41k | |
1189 | 1.41k | if (affine < 0) |
1190 | 0 | return isl_space_free(space); |
1191 | 1.41k | if (affine) |
1192 | 638 | space = isl_space_drop_dims(space, isl_dim_set, i, 1); |
1193 | 1.41k | } |
1194 | 196 | |
1195 | 196 | return space; |
1196 | 196 | } |
1197 | | |
1198 | | /* Return the external representation of the schedule space of "build", |
1199 | | * i.e., a space with a dimension for each loop generated so far, |
1200 | | * with the names of the dimensions set to the loop iterators. |
1201 | | */ |
1202 | | __isl_give isl_space *isl_ast_build_get_schedule_space( |
1203 | | __isl_keep isl_ast_build *build) |
1204 | 3 | { |
1205 | 3 | isl_space *space; |
1206 | 3 | int i, skip; |
1207 | 3 | |
1208 | 3 | if (!build) |
1209 | 0 | return NULL; |
1210 | 3 | |
1211 | 3 | space = isl_ast_build_get_space(build, 0); |
1212 | 3 | |
1213 | 3 | skip = 0; |
1214 | 13 | for (i = 0; i < build->depth; ++i10 ) { |
1215 | 10 | isl_id *id; |
1216 | 10 | |
1217 | 10 | if (isl_ast_build_has_affine_value(build, i)) { |
1218 | 5 | skip++; |
1219 | 5 | continue; |
1220 | 5 | } |
1221 | 5 | |
1222 | 5 | id = isl_ast_build_get_iterator_id(build, i); |
1223 | 5 | space = isl_space_set_dim_id(space, isl_dim_set, i - skip, id); |
1224 | 5 | } |
1225 | 3 | |
1226 | 3 | return space; |
1227 | 3 | } |
1228 | | |
1229 | | /* Return the current schedule, as stored in build->executed, in terms |
1230 | | * of the external schedule domain. |
1231 | | */ |
1232 | | __isl_give isl_union_map *isl_ast_build_get_schedule( |
1233 | | __isl_keep isl_ast_build *build) |
1234 | 581 | { |
1235 | 581 | isl_union_map *executed; |
1236 | 581 | isl_union_map *schedule; |
1237 | 581 | |
1238 | 581 | if (!build) |
1239 | 0 | return NULL; |
1240 | 581 | |
1241 | 581 | executed = isl_union_map_copy(build->executed); |
1242 | 581 | if (isl_ast_build_need_schedule_map(build)) { |
1243 | 296 | isl_map *proj = isl_ast_build_get_schedule_map(build); |
1244 | 296 | executed = isl_union_map_apply_domain(executed, |
1245 | 296 | isl_union_map_from_map(proj)); |
1246 | 296 | } |
1247 | 581 | schedule = isl_union_map_reverse(executed); |
1248 | 581 | |
1249 | 581 | return schedule; |
1250 | 581 | } |
1251 | | |
1252 | | /* Return the iterator attached to the internal schedule dimension "pos". |
1253 | | */ |
1254 | | __isl_give isl_id *isl_ast_build_get_iterator_id( |
1255 | | __isl_keep isl_ast_build *build, int pos) |
1256 | 24.2k | { |
1257 | 24.2k | if (!build) |
1258 | 0 | return NULL; |
1259 | 24.2k | |
1260 | 24.2k | return isl_id_list_get_id(build->iterators, pos); |
1261 | 24.2k | } |
1262 | | |
1263 | | /* Set the stride and offset of the current dimension to the given |
1264 | | * value and expression. |
1265 | | */ |
1266 | | static __isl_give isl_ast_build *set_stride(__isl_take isl_ast_build *build, |
1267 | | __isl_take isl_val *stride, __isl_take isl_aff *offset) |
1268 | 15 | { |
1269 | 15 | int pos; |
1270 | 15 | |
1271 | 15 | build = isl_ast_build_cow(build); |
1272 | 15 | if (!build || !stride || !offset) |
1273 | 0 | goto error; |
1274 | 15 | |
1275 | 15 | pos = build->depth; |
1276 | 15 | |
1277 | 15 | build->strides = isl_vec_set_element_val(build->strides, pos, stride); |
1278 | 15 | build->offsets = isl_multi_aff_set_aff(build->offsets, pos, offset); |
1279 | 15 | if (!build->strides || !build->offsets) |
1280 | 0 | return isl_ast_build_free(build); |
1281 | 15 | |
1282 | 15 | return build; |
1283 | 0 | error: |
1284 | 0 | isl_val_free(stride); |
1285 | 0 | isl_aff_free(offset); |
1286 | 0 | return isl_ast_build_free(build); |
1287 | 15 | } |
1288 | | |
1289 | | /* Return a set expressing the stride constraint at the current depth. |
1290 | | * |
1291 | | * In particular, if the current iterator (i) is known to attain values |
1292 | | * |
1293 | | * f + s a |
1294 | | * |
1295 | | * where f is the offset and s is the stride, then the returned set |
1296 | | * expresses the constraint |
1297 | | * |
1298 | | * (f - i) mod s = 0 |
1299 | | */ |
1300 | | __isl_give isl_set *isl_ast_build_get_stride_constraint( |
1301 | | __isl_keep isl_ast_build *build) |
1302 | 39 | { |
1303 | 39 | isl_aff *aff; |
1304 | 39 | isl_set *set; |
1305 | 39 | isl_val *stride; |
1306 | 39 | int pos; |
1307 | 39 | |
1308 | 39 | if (!build) |
1309 | 0 | return NULL; |
1310 | 39 | |
1311 | 39 | pos = build->depth; |
1312 | 39 | |
1313 | 39 | if (!isl_ast_build_has_stride(build, pos)) |
1314 | 0 | return isl_set_universe(isl_ast_build_get_space(build, 1)); |
1315 | 39 | |
1316 | 39 | stride = isl_ast_build_get_stride(build, pos); |
1317 | 39 | aff = isl_ast_build_get_offset(build, pos); |
1318 | 39 | aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, -1); |
1319 | 39 | aff = isl_aff_mod_val(aff, stride); |
1320 | 39 | set = isl_set_from_basic_set(isl_aff_zero_basic_set(aff)); |
1321 | 39 | |
1322 | 39 | return set; |
1323 | 39 | } |
1324 | | |
1325 | | /* Return the expansion implied by the stride and offset at the current |
1326 | | * depth. |
1327 | | * |
1328 | | * That is, return the mapping |
1329 | | * |
1330 | | * [i_0, ..., i_{d-1}, i_d, i_{d+1}, ...] |
1331 | | * -> [i_0, ..., i_{d-1}, s * i_d + offset(i), i_{d+1}, ...] |
1332 | | * |
1333 | | * where s is the stride at the current depth d and offset(i) is |
1334 | | * the corresponding offset. |
1335 | | */ |
1336 | | __isl_give isl_multi_aff *isl_ast_build_get_stride_expansion( |
1337 | | __isl_keep isl_ast_build *build) |
1338 | 2.37k | { |
1339 | 2.37k | isl_space *space; |
1340 | 2.37k | isl_multi_aff *ma; |
1341 | 2.37k | int pos; |
1342 | 2.37k | isl_aff *aff, *offset; |
1343 | 2.37k | isl_val *stride; |
1344 | 2.37k | |
1345 | 2.37k | if (!build) |
1346 | 0 | return NULL; |
1347 | 2.37k | |
1348 | 2.37k | pos = isl_ast_build_get_depth(build); |
1349 | 2.37k | space = isl_ast_build_get_space(build, 1); |
1350 | 2.37k | space = isl_space_map_from_set(space); |
1351 | 2.37k | ma = isl_multi_aff_identity(space); |
1352 | 2.37k | |
1353 | 2.37k | if (!isl_ast_build_has_stride(build, pos)) |
1354 | 2.37k | return ma; |
1355 | 0 | |
1356 | 0 | offset = isl_ast_build_get_offset(build, pos); |
1357 | 0 | stride = isl_ast_build_get_stride(build, pos); |
1358 | 0 | aff = isl_multi_aff_get_aff(ma, pos); |
1359 | 0 | aff = isl_aff_scale_val(aff, stride); |
1360 | 0 | aff = isl_aff_add(aff, offset); |
1361 | 0 | ma = isl_multi_aff_set_aff(ma, pos, aff); |
1362 | 0 |
|
1363 | 0 | return ma; |
1364 | 0 | } |
1365 | | |
1366 | | /* Add constraints corresponding to any previously detected |
1367 | | * stride on the current dimension to build->domain. |
1368 | | */ |
1369 | | __isl_give isl_ast_build *isl_ast_build_include_stride( |
1370 | | __isl_take isl_ast_build *build) |
1371 | 749 | { |
1372 | 749 | isl_set *set; |
1373 | 749 | |
1374 | 749 | if (!build) |
1375 | 0 | return NULL; |
1376 | 749 | if (!isl_ast_build_has_stride(build, build->depth)) |
1377 | 737 | return build; |
1378 | 12 | build = isl_ast_build_cow(build); |
1379 | 12 | if (!build) |
1380 | 0 | return NULL; |
1381 | 12 | |
1382 | 12 | set = isl_ast_build_get_stride_constraint(build); |
1383 | 12 | |
1384 | 12 | build->domain = isl_set_intersect(build->domain, isl_set_copy(set)); |
1385 | 12 | build->generated = isl_set_intersect(build->generated, set); |
1386 | 12 | if (!build->domain || !build->generated) |
1387 | 0 | return isl_ast_build_free(build); |
1388 | 12 | |
1389 | 12 | return build; |
1390 | 12 | } |
1391 | | |
1392 | | /* Check if the constraints in "set" imply any stride on the current |
1393 | | * dimension and, if so, record the stride information in "build" |
1394 | | * and return the updated "build". |
1395 | | * |
1396 | | * We assume that inner dimensions have been eliminated from "set" |
1397 | | * by the caller. This is needed because the common stride |
1398 | | * may be imposed by different inner dimensions on different parts of |
1399 | | * the domain. |
1400 | | * The assumption ensures that the lower bound does not depend |
1401 | | * on inner dimensions. |
1402 | | */ |
1403 | | __isl_give isl_ast_build *isl_ast_build_detect_strides( |
1404 | | __isl_take isl_ast_build *build, __isl_take isl_set *set) |
1405 | 6.43k | { |
1406 | 6.43k | int pos; |
1407 | 6.43k | isl_bool no_stride; |
1408 | 6.43k | isl_val *stride; |
1409 | 6.43k | isl_aff *offset; |
1410 | 6.43k | isl_stride_info *si; |
1411 | 6.43k | |
1412 | 6.43k | if (!build) |
1413 | 0 | goto error; |
1414 | 6.43k | |
1415 | 6.43k | pos = isl_ast_build_get_depth(build); |
1416 | 6.43k | si = isl_set_get_stride_info(set, pos); |
1417 | 6.43k | stride = isl_stride_info_get_stride(si); |
1418 | 6.43k | offset = isl_stride_info_get_offset(si); |
1419 | 6.43k | isl_stride_info_free(si); |
1420 | 6.43k | isl_set_free(set); |
1421 | 6.43k | |
1422 | 6.43k | no_stride = isl_val_is_one(stride); |
1423 | 6.43k | if (no_stride >= 0 && !no_stride) |
1424 | 15 | return set_stride(build, stride, offset); |
1425 | 6.42k | isl_val_free(stride); |
1426 | 6.42k | isl_aff_free(offset); |
1427 | 6.42k | if (no_stride < 0) |
1428 | 0 | return isl_ast_build_free(build); |
1429 | 6.42k | return build; |
1430 | 0 | error: |
1431 | 0 | isl_set_free(set); |
1432 | 0 | return NULL; |
1433 | 6.42k | } |
1434 | | |
1435 | | struct isl_ast_build_involves_data { |
1436 | | int depth; |
1437 | | int involves; |
1438 | | }; |
1439 | | |
1440 | | /* Check if "map" involves the input dimension data->depth. |
1441 | | */ |
1442 | | static isl_stat involves_depth(__isl_take isl_map *map, void *user) |
1443 | 0 | { |
1444 | 0 | struct isl_ast_build_involves_data *data = user; |
1445 | 0 |
|
1446 | 0 | data->involves = isl_map_involves_dims(map, isl_dim_in, data->depth, 1); |
1447 | 0 | isl_map_free(map); |
1448 | 0 |
|
1449 | 0 | if (data->involves < 0 || data->involves) |
1450 | 0 | return isl_stat_error; |
1451 | 0 | return isl_stat_ok; |
1452 | 0 | } |
1453 | | |
1454 | | /* Do any options depend on the value of the dimension at the current depth? |
1455 | | */ |
1456 | | int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build *build) |
1457 | 1 | { |
1458 | 1 | struct isl_ast_build_involves_data data; |
1459 | 1 | |
1460 | 1 | if (!build) |
1461 | 0 | return -1; |
1462 | 1 | |
1463 | 1 | data.depth = build->depth; |
1464 | 1 | data.involves = 0; |
1465 | 1 | |
1466 | 1 | if (isl_union_map_foreach_map(build->options, |
1467 | 1 | &involves_depth, &data) < 0) { |
1468 | 0 | if (data.involves < 0 || !data.involves) |
1469 | 0 | return -1; |
1470 | 1 | } |
1471 | 1 | |
1472 | 1 | return data.involves; |
1473 | 1 | } |
1474 | | |
1475 | | /* Construct the map |
1476 | | * |
1477 | | * { [i] -> [i] : i < pos; [i] -> [i + 1] : i >= pos } |
1478 | | * |
1479 | | * with "space" the parameter space of the constructed map. |
1480 | | */ |
1481 | | static __isl_give isl_map *construct_insertion_map(__isl_take isl_space *space, |
1482 | | int pos) |
1483 | 0 | { |
1484 | 0 | isl_constraint *c; |
1485 | 0 | isl_basic_map *bmap1, *bmap2; |
1486 | 0 |
|
1487 | 0 | space = isl_space_set_from_params(space); |
1488 | 0 | space = isl_space_add_dims(space, isl_dim_set, 1); |
1489 | 0 | space = isl_space_map_from_set(space); |
1490 | 0 | c = isl_constraint_alloc_equality(isl_local_space_from_space(space)); |
1491 | 0 | c = isl_constraint_set_coefficient_si(c, isl_dim_in, 0, 1); |
1492 | 0 | c = isl_constraint_set_coefficient_si(c, isl_dim_out, 0, -1); |
1493 | 0 | bmap1 = isl_basic_map_from_constraint(isl_constraint_copy(c)); |
1494 | 0 | c = isl_constraint_set_constant_si(c, 1); |
1495 | 0 | bmap2 = isl_basic_map_from_constraint(c); |
1496 | 0 |
|
1497 | 0 | bmap1 = isl_basic_map_upper_bound_si(bmap1, isl_dim_in, 0, pos - 1); |
1498 | 0 | bmap2 = isl_basic_map_lower_bound_si(bmap2, isl_dim_in, 0, pos); |
1499 | 0 |
|
1500 | 0 | return isl_basic_map_union(bmap1, bmap2); |
1501 | 0 | } |
1502 | | |
1503 | | static const char *option_str[] = { |
1504 | | [isl_ast_loop_atomic] = "atomic", |
1505 | | [isl_ast_loop_unroll] = "unroll", |
1506 | | [isl_ast_loop_separate] = "separate" |
1507 | | }; |
1508 | | |
1509 | | /* Update the "options" to reflect the insertion of a dimension |
1510 | | * at position "pos" in the schedule domain space. |
1511 | | * "space" is the original domain space before the insertion and |
1512 | | * may be named and/or structured. |
1513 | | * |
1514 | | * The (relevant) input options all have "space" as domain, which |
1515 | | * has to be mapped to the extended space. |
1516 | | * The values of the ranges also refer to the schedule domain positions |
1517 | | * and they therefore also need to be adjusted. In particular, values |
1518 | | * smaller than pos do not need to change, while values greater than or |
1519 | | * equal to pos need to be incremented. |
1520 | | * That is, we need to apply the following map. |
1521 | | * |
1522 | | * { atomic[i] -> atomic[i] : i < pos; [i] -> [i + 1] : i >= pos; |
1523 | | * unroll[i] -> unroll[i] : i < pos; [i] -> [i + 1] : i >= pos; |
1524 | | * separate[i] -> separate[i] : i < pos; [i] -> [i + 1] : i >= pos; |
1525 | | * separation_class[[i] -> [c]] |
1526 | | * -> separation_class[[i] -> [c]] : i < pos; |
1527 | | * separation_class[[i] -> [c]] |
1528 | | * -> separation_class[[i + 1] -> [c]] : i >= pos } |
1529 | | */ |
1530 | | static __isl_give isl_union_map *options_insert_dim( |
1531 | | __isl_take isl_union_map *options, __isl_take isl_space *space, int pos) |
1532 | 0 | { |
1533 | 0 | isl_map *map; |
1534 | 0 | isl_union_map *insertion; |
1535 | 0 | enum isl_ast_loop_type type; |
1536 | 0 | const char *name = "separation_class"; |
1537 | 0 |
|
1538 | 0 | space = isl_space_map_from_set(space); |
1539 | 0 | map = isl_map_identity(space); |
1540 | 0 | map = isl_map_insert_dims(map, isl_dim_out, pos, 1); |
1541 | 0 | options = isl_union_map_apply_domain(options, |
1542 | 0 | isl_union_map_from_map(map)); |
1543 | 0 |
|
1544 | 0 | if (!options) |
1545 | 0 | return NULL; |
1546 | 0 | |
1547 | 0 | map = construct_insertion_map(isl_union_map_get_space(options), pos); |
1548 | 0 |
|
1549 | 0 | insertion = isl_union_map_empty(isl_union_map_get_space(options)); |
1550 | 0 |
|
1551 | 0 | for (type = isl_ast_loop_atomic; |
1552 | 0 | type <= isl_ast_loop_separate; ++type) { |
1553 | 0 | isl_map *map_type = isl_map_copy(map); |
1554 | 0 | const char *name = option_str[type]; |
1555 | 0 | map_type = isl_map_set_tuple_name(map_type, isl_dim_in, name); |
1556 | 0 | map_type = isl_map_set_tuple_name(map_type, isl_dim_out, name); |
1557 | 0 | insertion = isl_union_map_add_map(insertion, map_type); |
1558 | 0 | } |
1559 | 0 |
|
1560 | 0 | map = isl_map_product(map, isl_map_identity(isl_map_get_space(map))); |
1561 | 0 | map = isl_map_set_tuple_name(map, isl_dim_in, name); |
1562 | 0 | map = isl_map_set_tuple_name(map, isl_dim_out, name); |
1563 | 0 | insertion = isl_union_map_add_map(insertion, map); |
1564 | 0 |
|
1565 | 0 | options = isl_union_map_apply_range(options, insertion); |
1566 | 0 |
|
1567 | 0 | return options; |
1568 | 0 | } |
1569 | | |
1570 | | /* If we are generating an AST from a schedule tree (build->node is set), |
1571 | | * then update the loop AST generation types |
1572 | | * to reflect the insertion of a dimension at (global) position "pos" |
1573 | | * in the schedule domain space. |
1574 | | * We do not need to adjust any isolate option since we would not be inserting |
1575 | | * any dimensions if there were any isolate option. |
1576 | | */ |
1577 | | static __isl_give isl_ast_build *node_insert_dim( |
1578 | | __isl_take isl_ast_build *build, int pos) |
1579 | 3 | { |
1580 | 3 | int i; |
1581 | 3 | int local_pos; |
1582 | 3 | enum isl_ast_loop_type *loop_type; |
1583 | 3 | isl_ctx *ctx; |
1584 | 3 | |
1585 | 3 | build = isl_ast_build_cow(build); |
1586 | 3 | if (!build) |
1587 | 0 | return NULL; |
1588 | 3 | if (!build->node) |
1589 | 0 | return build; |
1590 | 3 | |
1591 | 3 | ctx = isl_ast_build_get_ctx(build); |
1592 | 3 | local_pos = pos - build->outer_pos; |
1593 | 3 | loop_type = isl_realloc_array(ctx, build->loop_type, |
1594 | 3 | enum isl_ast_loop_type, build->n + 1); |
1595 | 3 | if (!loop_type) |
1596 | 0 | return isl_ast_build_free(build); |
1597 | 3 | build->loop_type = loop_type; |
1598 | 3 | for (i = build->n - 1; i >= local_pos; --i0 ) |
1599 | 0 | loop_type[i + 1] = loop_type[i]; |
1600 | 3 | loop_type[local_pos] = isl_ast_loop_default; |
1601 | 3 | build->n++; |
1602 | 3 | |
1603 | 3 | return build; |
1604 | 3 | } |
1605 | | |
1606 | | /* Insert a single dimension in the schedule domain at position "pos". |
1607 | | * The new dimension is given an isl_id with the empty string as name. |
1608 | | * |
1609 | | * The main difficulty is updating build->options to reflect the |
1610 | | * extra dimension. This is handled in options_insert_dim. |
1611 | | * |
1612 | | * Note that because of the dimension manipulations, the resulting |
1613 | | * schedule domain space will always be unnamed and unstructured. |
1614 | | * However, the original schedule domain space may be named and/or |
1615 | | * structured, so we have to take this possibility into account |
1616 | | * while performing the transformations. |
1617 | | * |
1618 | | * Since the inserted schedule dimension is used by the caller |
1619 | | * to differentiate between different domain spaces, there is |
1620 | | * no longer a uniform mapping from the internal schedule space |
1621 | | * to the input schedule space. The internal2input mapping is |
1622 | | * therefore removed. |
1623 | | */ |
1624 | | __isl_give isl_ast_build *isl_ast_build_insert_dim( |
1625 | | __isl_take isl_ast_build *build, int pos) |
1626 | 3 | { |
1627 | 3 | isl_ctx *ctx; |
1628 | 3 | isl_space *space, *ma_space; |
1629 | 3 | isl_id *id; |
1630 | 3 | isl_multi_aff *ma; |
1631 | 3 | |
1632 | 3 | build = isl_ast_build_cow(build); |
1633 | 3 | if (!build) |
1634 | 0 | return NULL; |
1635 | 3 | |
1636 | 3 | ctx = isl_ast_build_get_ctx(build); |
1637 | 3 | id = isl_id_alloc(ctx, "", NULL); |
1638 | 3 | if (!build->node) |
1639 | 0 | space = isl_ast_build_get_space(build, 1); |
1640 | 3 | build->iterators = isl_id_list_insert(build->iterators, pos, id); |
1641 | 3 | build->domain = isl_set_insert_dims(build->domain, |
1642 | 3 | isl_dim_set, pos, 1); |
1643 | 3 | build->generated = isl_set_insert_dims(build->generated, |
1644 | 3 | isl_dim_set, pos, 1); |
1645 | 3 | build->pending = isl_set_insert_dims(build->pending, |
1646 | 3 | isl_dim_set, pos, 1); |
1647 | 3 | build->strides = isl_vec_insert_els(build->strides, pos, 1); |
1648 | 3 | build->strides = isl_vec_set_element_si(build->strides, pos, 1); |
1649 | 3 | ma_space = isl_space_params(isl_multi_aff_get_space(build->offsets)); |
1650 | 3 | ma_space = isl_space_set_from_params(ma_space); |
1651 | 3 | ma_space = isl_space_add_dims(ma_space, isl_dim_set, 1); |
1652 | 3 | ma_space = isl_space_map_from_set(ma_space); |
1653 | 3 | ma = isl_multi_aff_zero(isl_space_copy(ma_space)); |
1654 | 3 | build->offsets = isl_multi_aff_splice(build->offsets, pos, pos, ma); |
1655 | 3 | ma = isl_multi_aff_identity(ma_space); |
1656 | 3 | build->values = isl_multi_aff_splice(build->values, pos, pos, ma); |
1657 | 3 | if (!build->node) |
1658 | 0 | build->options = options_insert_dim(build->options, space, pos); |
1659 | 3 | build->internal2input = isl_multi_aff_free(build->internal2input); |
1660 | 3 | |
1661 | 3 | if (!build->iterators || !build->domain || !build->generated || |
1662 | 3 | !build->pending || !build->values || |
1663 | 3 | !build->strides || !build->offsets || !build->options) |
1664 | 0 | return isl_ast_build_free(build); |
1665 | 3 | |
1666 | 3 | build = node_insert_dim(build, pos); |
1667 | 3 | |
1668 | 3 | return build; |
1669 | 3 | } |
1670 | | |
1671 | | /* Scale down the current dimension by a factor of "m". |
1672 | | * "umap" is an isl_union_map that implements the scaling down. |
1673 | | * That is, it is of the form |
1674 | | * |
1675 | | * { [.... i ....] -> [.... i' ....] : i = m i' } |
1676 | | * |
1677 | | * This function is called right after the strides have been |
1678 | | * detected, but before any constraints on the current dimension |
1679 | | * have been included in build->domain. |
1680 | | * We therefore only need to update stride, offset, the options and |
1681 | | * the mapping from internal schedule space to the original schedule |
1682 | | * space, if we are still keeping track of such a mapping. |
1683 | | * The latter mapping is updated by plugging in |
1684 | | * { [... i ...] -> [... m i ... ] }. |
1685 | | */ |
1686 | | __isl_give isl_ast_build *isl_ast_build_scale_down( |
1687 | | __isl_take isl_ast_build *build, __isl_take isl_val *m, |
1688 | | __isl_take isl_union_map *umap) |
1689 | 0 | { |
1690 | 0 | isl_aff *aff; |
1691 | 0 | isl_val *v; |
1692 | 0 | int depth; |
1693 | 0 |
|
1694 | 0 | build = isl_ast_build_cow(build); |
1695 | 0 | if (!build || !umap || !m) |
1696 | 0 | goto error; |
1697 | 0 | |
1698 | 0 | depth = build->depth; |
1699 | 0 |
|
1700 | 0 | if (build->internal2input) { |
1701 | 0 | isl_space *space; |
1702 | 0 | isl_multi_aff *ma; |
1703 | 0 | isl_aff *aff; |
1704 | 0 |
|
1705 | 0 | space = isl_multi_aff_get_space(build->internal2input); |
1706 | 0 | space = isl_space_map_from_set(isl_space_domain(space)); |
1707 | 0 | ma = isl_multi_aff_identity(space); |
1708 | 0 | aff = isl_multi_aff_get_aff(ma, depth); |
1709 | 0 | aff = isl_aff_scale_val(aff, isl_val_copy(m)); |
1710 | 0 | ma = isl_multi_aff_set_aff(ma, depth, aff); |
1711 | 0 | build->internal2input = |
1712 | 0 | isl_multi_aff_pullback_multi_aff(build->internal2input, ma); |
1713 | 0 | if (!build->internal2input) |
1714 | 0 | goto error; |
1715 | 0 | } |
1716 | 0 | |
1717 | 0 | v = isl_vec_get_element_val(build->strides, depth); |
1718 | 0 | v = isl_val_div(v, isl_val_copy(m)); |
1719 | 0 | build->strides = isl_vec_set_element_val(build->strides, depth, v); |
1720 | 0 |
|
1721 | 0 | aff = isl_multi_aff_get_aff(build->offsets, depth); |
1722 | 0 | aff = isl_aff_scale_down_val(aff, m); |
1723 | 0 | build->offsets = isl_multi_aff_set_aff(build->offsets, depth, aff); |
1724 | 0 | build->options = isl_union_map_apply_domain(build->options, umap); |
1725 | 0 | if (!build->strides || !build->offsets || !build->options) |
1726 | 0 | return isl_ast_build_free(build); |
1727 | 0 | |
1728 | 0 | return build; |
1729 | 0 | error: |
1730 | 0 | isl_val_free(m); |
1731 | 0 | isl_union_map_free(umap); |
1732 | 0 | return isl_ast_build_free(build); |
1733 | 0 | } |
1734 | | |
1735 | | /* Return a list of "n" isl_ids called "c%d", with "%d" starting at "first". |
1736 | | * If an isl_id with such a name already appears among the parameters |
1737 | | * in build->domain, then adjust the name to "c%d_%d". |
1738 | | */ |
1739 | | static __isl_give isl_id_list *generate_names(isl_ctx *ctx, int n, int first, |
1740 | | __isl_keep isl_ast_build *build) |
1741 | 681 | { |
1742 | 681 | int i; |
1743 | 681 | isl_id_list *names; |
1744 | 681 | |
1745 | 681 | names = isl_id_list_alloc(ctx, n); |
1746 | 1.62k | for (i = 0; i < n; ++i941 ) { |
1747 | 941 | isl_id *id; |
1748 | 941 | |
1749 | 941 | id = generate_name(ctx, first + i, build); |
1750 | 941 | names = isl_id_list_add(names, id); |
1751 | 941 | } |
1752 | 681 | |
1753 | 681 | return names; |
1754 | 681 | } |
1755 | | |
1756 | | /* Embed "options" into the given isl_ast_build space. |
1757 | | * |
1758 | | * This function is called from within a nested call to |
1759 | | * isl_ast_build_node_from_schedule_map. |
1760 | | * "options" refers to the additional schedule, |
1761 | | * while space refers to both the space of the outer isl_ast_build and |
1762 | | * that of the additional schedule. |
1763 | | * Specifically, space is of the form |
1764 | | * |
1765 | | * [I -> S] |
1766 | | * |
1767 | | * while options lives in the space(s) |
1768 | | * |
1769 | | * S -> * |
1770 | | * |
1771 | | * We compute |
1772 | | * |
1773 | | * [I -> S] -> S |
1774 | | * |
1775 | | * and compose this with options, to obtain the new options |
1776 | | * living in the space(s) |
1777 | | * |
1778 | | * [I -> S] -> * |
1779 | | */ |
1780 | | static __isl_give isl_union_map *embed_options( |
1781 | | __isl_take isl_union_map *options, __isl_take isl_space *space) |
1782 | 678 | { |
1783 | 678 | isl_map *map; |
1784 | 678 | |
1785 | 678 | map = isl_map_universe(isl_space_unwrap(space)); |
1786 | 678 | map = isl_map_range_map(map); |
1787 | 678 | |
1788 | 678 | options = isl_union_map_apply_range( |
1789 | 678 | isl_union_map_from_map(map), options); |
1790 | 678 | |
1791 | 678 | return options; |
1792 | 678 | } |
1793 | | |
1794 | | /* Update "build" for use in a (possibly nested) code generation. That is, |
1795 | | * extend "build" from an AST build on some domain O to an AST build |
1796 | | * on domain [O -> S], with S corresponding to "space". |
1797 | | * If the original domain is a parameter domain, then the new domain is |
1798 | | * simply S. |
1799 | | * "iterators" is a list of iterators for S, but the number of elements |
1800 | | * may be smaller or greater than the number of set dimensions of S. |
1801 | | * If "keep_iterators" is set, then any extra ids in build->iterators |
1802 | | * are reused for S. Otherwise, these extra ids are dropped. |
1803 | | * |
1804 | | * We first update build->outer_pos to the current depth. |
1805 | | * This depth is zero in case this is the outermost code generation. |
1806 | | * |
1807 | | * We then add additional ids such that the number of iterators is at least |
1808 | | * equal to the dimension of the new build domain. |
1809 | | * |
1810 | | * If the original domain is parametric, then we are constructing |
1811 | | * an isl_ast_build for the outer code generation and we pass control |
1812 | | * to isl_ast_build_init. |
1813 | | * |
1814 | | * Otherwise, we adjust the fields of "build" to include "space". |
1815 | | */ |
1816 | | __isl_give isl_ast_build *isl_ast_build_product( |
1817 | | __isl_take isl_ast_build *build, __isl_take isl_space *space) |
1818 | 1.14k | { |
1819 | 1.14k | isl_ctx *ctx; |
1820 | 1.14k | isl_vec *strides; |
1821 | 1.14k | isl_set *set; |
1822 | 1.14k | isl_multi_aff *embedding; |
1823 | 1.14k | int dim, n_it; |
1824 | 1.14k | |
1825 | 1.14k | build = isl_ast_build_cow(build); |
1826 | 1.14k | if (!build) |
1827 | 0 | goto error; |
1828 | 1.14k | |
1829 | 1.14k | build->outer_pos = build->depth; |
1830 | 1.14k | |
1831 | 1.14k | ctx = isl_ast_build_get_ctx(build); |
1832 | 1.14k | dim = isl_set_dim(build->domain, isl_dim_set); |
1833 | 1.14k | dim += isl_space_dim(space, isl_dim_set); |
1834 | 1.14k | n_it = isl_id_list_n_id(build->iterators); |
1835 | 1.14k | if (n_it < dim) { |
1836 | 681 | isl_id_list *l; |
1837 | 681 | l = generate_names(ctx, dim - n_it, n_it, build); |
1838 | 681 | build->iterators = isl_id_list_concat(build->iterators, l); |
1839 | 681 | } |
1840 | 1.14k | |
1841 | 1.14k | if (isl_set_is_params(build->domain)) |
1842 | 464 | return isl_ast_build_init(build, space); |
1843 | 678 | |
1844 | 678 | set = isl_set_universe(isl_space_copy(space)); |
1845 | 678 | build->domain = isl_set_product(build->domain, isl_set_copy(set)); |
1846 | 678 | build->pending = isl_set_product(build->pending, isl_set_copy(set)); |
1847 | 678 | build->generated = isl_set_product(build->generated, set); |
1848 | 678 | |
1849 | 678 | strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set)); |
1850 | 678 | strides = isl_vec_set_si(strides, 1); |
1851 | 678 | build->strides = isl_vec_concat(build->strides, strides); |
1852 | 678 | |
1853 | 678 | space = isl_space_map_from_set(space); |
1854 | 678 | build->offsets = isl_multi_aff_align_params(build->offsets, |
1855 | 678 | isl_space_copy(space)); |
1856 | 678 | build->offsets = isl_multi_aff_product(build->offsets, |
1857 | 678 | isl_multi_aff_zero(isl_space_copy(space))); |
1858 | 678 | build->values = isl_multi_aff_align_params(build->values, |
1859 | 678 | isl_space_copy(space)); |
1860 | 678 | embedding = isl_multi_aff_identity(space); |
1861 | 678 | build->values = isl_multi_aff_product(build->values, |
1862 | 678 | isl_multi_aff_copy(embedding)); |
1863 | 678 | if (build->internal2input) { |
1864 | 678 | build->internal2input = |
1865 | 678 | isl_multi_aff_product(build->internal2input, embedding); |
1866 | 678 | build->internal2input = |
1867 | 678 | isl_multi_aff_flatten_range(build->internal2input); |
1868 | 678 | if (!build->internal2input) |
1869 | 0 | return isl_ast_build_free(build); |
1870 | 0 | } else { |
1871 | 0 | isl_multi_aff_free(embedding); |
1872 | 0 | } |
1873 | 678 | |
1874 | 678 | space = isl_ast_build_get_space(build, 1); |
1875 | 678 | build->options = embed_options(build->options, space); |
1876 | 678 | |
1877 | 678 | if (!build->iterators || !build->domain || !build->generated || |
1878 | 678 | !build->pending || !build->values || |
1879 | 678 | !build->strides || !build->offsets || !build->options) |
1880 | 0 | return isl_ast_build_free(build); |
1881 | 678 | |
1882 | 678 | return build; |
1883 | 0 | error: |
1884 | 0 | isl_ast_build_free(build); |
1885 | 0 | isl_space_free(space); |
1886 | 0 | return NULL; |
1887 | 678 | } |
1888 | | |
1889 | | /* Does "aff" only attain non-negative values over build->domain? |
1890 | | * That is, does it not attain any negative values? |
1891 | | */ |
1892 | | int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build, |
1893 | | __isl_keep isl_aff *aff) |
1894 | 153 | { |
1895 | 153 | isl_set *test; |
1896 | 153 | int empty; |
1897 | 153 | |
1898 | 153 | if (!build) |
1899 | 0 | return -1; |
1900 | 153 | |
1901 | 153 | aff = isl_aff_copy(aff); |
1902 | 153 | test = isl_set_from_basic_set(isl_aff_neg_basic_set(aff)); |
1903 | 153 | test = isl_set_intersect(test, isl_set_copy(build->domain)); |
1904 | 153 | empty = isl_set_is_empty(test); |
1905 | 153 | isl_set_free(test); |
1906 | 153 | |
1907 | 153 | return empty; |
1908 | 153 | } |
1909 | | |
1910 | | /* Does the dimension at (internal) position "pos" have a non-trivial stride? |
1911 | | */ |
1912 | | isl_bool isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos) |
1913 | 14.3k | { |
1914 | 14.3k | isl_val *v; |
1915 | 14.3k | isl_bool has_stride; |
1916 | 14.3k | |
1917 | 14.3k | if (!build) |
1918 | 0 | return isl_bool_error; |
1919 | 14.3k | |
1920 | 14.3k | v = isl_vec_get_element_val(build->strides, pos); |
1921 | 14.3k | has_stride = isl_bool_not(isl_val_is_one(v)); |
1922 | 14.3k | isl_val_free(v); |
1923 | 14.3k | |
1924 | 14.3k | return has_stride; |
1925 | 14.3k | } |
1926 | | |
1927 | | /* Given that the dimension at position "pos" takes on values |
1928 | | * |
1929 | | * f + s a |
1930 | | * |
1931 | | * with a an integer, return s through *stride. |
1932 | | */ |
1933 | | __isl_give isl_val *isl_ast_build_get_stride(__isl_keep isl_ast_build *build, |
1934 | | int pos) |
1935 | 78 | { |
1936 | 78 | if (!build) |
1937 | 0 | return NULL; |
1938 | 78 | |
1939 | 78 | return isl_vec_get_element_val(build->strides, pos); |
1940 | 78 | } |
1941 | | |
1942 | | /* Given that the dimension at position "pos" takes on values |
1943 | | * |
1944 | | * f + s a |
1945 | | * |
1946 | | * with a an integer, return f. |
1947 | | */ |
1948 | | __isl_give isl_aff *isl_ast_build_get_offset( |
1949 | | __isl_keep isl_ast_build *build, int pos) |
1950 | 66 | { |
1951 | 66 | if (!build) |
1952 | 0 | return NULL; |
1953 | 66 | |
1954 | 66 | return isl_multi_aff_get_aff(build->offsets, pos); |
1955 | 66 | } |
1956 | | |
1957 | | /* Is the dimension at position "pos" known to attain only a single |
1958 | | * value that, moreover, can be described by a single affine expression |
1959 | | * in terms of the outer dimensions and parameters? |
1960 | | * |
1961 | | * If not, then the corresponding affine expression in build->values |
1962 | | * is set to be equal to the same input dimension. |
1963 | | * Otherwise, it is set to the requested expression in terms of |
1964 | | * outer dimensions and parameters. |
1965 | | */ |
1966 | | isl_bool isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build, |
1967 | | int pos) |
1968 | 16.1k | { |
1969 | 16.1k | isl_aff *aff; |
1970 | 16.1k | isl_bool involves; |
1971 | 16.1k | |
1972 | 16.1k | if (!build) |
1973 | 0 | return isl_bool_error; |
1974 | 16.1k | |
1975 | 16.1k | aff = isl_multi_aff_get_aff(build->values, pos); |
1976 | 16.1k | involves = isl_aff_involves_dims(aff, isl_dim_in, pos, 1); |
1977 | 16.1k | isl_aff_free(aff); |
1978 | 16.1k | |
1979 | 16.1k | return isl_bool_not(involves); |
1980 | 16.1k | } |
1981 | | |
1982 | | /* Plug in the known values (fixed affine expressions in terms of |
1983 | | * parameters and outer loop iterators) of all loop iterators |
1984 | | * in the domain of "umap". |
1985 | | * |
1986 | | * We simply precompose "umap" with build->values. |
1987 | | */ |
1988 | | __isl_give isl_union_map *isl_ast_build_substitute_values_union_map_domain( |
1989 | | __isl_keep isl_ast_build *build, __isl_take isl_union_map *umap) |
1990 | 3.31k | { |
1991 | 3.31k | isl_multi_aff *values; |
1992 | 3.31k | |
1993 | 3.31k | if (!build) |
1994 | 0 | return isl_union_map_free(umap); |
1995 | 3.31k | |
1996 | 3.31k | values = isl_multi_aff_copy(build->values); |
1997 | 3.31k | umap = isl_union_map_preimage_domain_multi_aff(umap, values); |
1998 | 3.31k | |
1999 | 3.31k | return umap; |
2000 | 3.31k | } |
2001 | | |
2002 | | /* Is the current dimension known to attain only a single value? |
2003 | | */ |
2004 | | int isl_ast_build_has_value(__isl_keep isl_ast_build *build) |
2005 | 4.06k | { |
2006 | 4.06k | if (!build) |
2007 | 0 | return -1; |
2008 | 4.06k | |
2009 | 4.06k | return build->value != NULL; |
2010 | 4.06k | } |
2011 | | |
2012 | | /* Simplify the basic set "bset" based on what we know about |
2013 | | * the iterators of already generated loops. |
2014 | | * |
2015 | | * "bset" is assumed to live in the (internal) schedule domain. |
2016 | | */ |
2017 | | __isl_give isl_basic_set *isl_ast_build_compute_gist_basic_set( |
2018 | | __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset) |
2019 | 749 | { |
2020 | 749 | if (!build) |
2021 | 0 | goto error; |
2022 | 749 | |
2023 | 749 | bset = isl_basic_set_preimage_multi_aff(bset, |
2024 | 749 | isl_multi_aff_copy(build->values)); |
2025 | 749 | bset = isl_basic_set_gist(bset, |
2026 | 749 | isl_set_simple_hull(isl_set_copy(build->domain))); |
2027 | 749 | |
2028 | 749 | return bset; |
2029 | 0 | error: |
2030 | 0 | isl_basic_set_free(bset); |
2031 | 0 | return NULL; |
2032 | 749 | } |
2033 | | |
2034 | | /* Simplify the set "set" based on what we know about |
2035 | | * the iterators of already generated loops. |
2036 | | * |
2037 | | * "set" is assumed to live in the (internal) schedule domain. |
2038 | | */ |
2039 | | __isl_give isl_set *isl_ast_build_compute_gist( |
2040 | | __isl_keep isl_ast_build *build, __isl_take isl_set *set) |
2041 | 617 | { |
2042 | 617 | if (!build) |
2043 | 0 | goto error; |
2044 | 617 | |
2045 | 617 | if (!isl_set_is_params(set)) |
2046 | 23 | set = isl_set_preimage_multi_aff(set, |
2047 | 23 | isl_multi_aff_copy(build->values)); |
2048 | 617 | set = isl_set_gist(set, isl_set_copy(build->domain)); |
2049 | 617 | |
2050 | 617 | return set; |
2051 | 0 | error: |
2052 | 0 | isl_set_free(set); |
2053 | 0 | return NULL; |
2054 | 617 | } |
2055 | | |
2056 | | /* Include information about what we know about the iterators of |
2057 | | * already generated loops to "set". |
2058 | | * |
2059 | | * We currently only plug in the known affine values of outer loop |
2060 | | * iterators. |
2061 | | * In principle we could also introduce equalities or even other |
2062 | | * constraints implied by the intersection of "set" and build->domain. |
2063 | | */ |
2064 | | __isl_give isl_set *isl_ast_build_specialize(__isl_keep isl_ast_build *build, |
2065 | | __isl_take isl_set *set) |
2066 | 10.0k | { |
2067 | 10.0k | if (!build) |
2068 | 0 | return isl_set_free(set); |
2069 | 10.0k | |
2070 | 10.0k | return isl_set_preimage_multi_aff(set, |
2071 | 10.0k | isl_multi_aff_copy(build->values)); |
2072 | 10.0k | } |
2073 | | |
2074 | | /* Plug in the known affine values of outer loop iterators in "bset". |
2075 | | */ |
2076 | | __isl_give isl_basic_set *isl_ast_build_specialize_basic_set( |
2077 | | __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset) |
2078 | 4.06k | { |
2079 | 4.06k | if (!build) |
2080 | 0 | return isl_basic_set_free(bset); |
2081 | 4.06k | |
2082 | 4.06k | return isl_basic_set_preimage_multi_aff(bset, |
2083 | 4.06k | isl_multi_aff_copy(build->values)); |
2084 | 4.06k | } |
2085 | | |
2086 | | /* Simplify the map "map" based on what we know about |
2087 | | * the iterators of already generated loops. |
2088 | | * |
2089 | | * The domain of "map" is assumed to live in the (internal) schedule domain. |
2090 | | */ |
2091 | | __isl_give isl_map *isl_ast_build_compute_gist_map_domain( |
2092 | | __isl_keep isl_ast_build *build, __isl_take isl_map *map) |
2093 | 1.36k | { |
2094 | 1.36k | if (!build) |
2095 | 0 | goto error; |
2096 | 1.36k | |
2097 | 1.36k | map = isl_map_gist_domain(map, isl_set_copy(build->domain)); |
2098 | 1.36k | |
2099 | 1.36k | return map; |
2100 | 0 | error: |
2101 | 0 | isl_map_free(map); |
2102 | 0 | return NULL; |
2103 | 1.36k | } |
2104 | | |
2105 | | /* Simplify the affine expression "aff" based on what we know about |
2106 | | * the iterators of already generated loops. |
2107 | | * |
2108 | | * The domain of "aff" is assumed to live in the (internal) schedule domain. |
2109 | | */ |
2110 | | __isl_give isl_aff *isl_ast_build_compute_gist_aff( |
2111 | | __isl_keep isl_ast_build *build, __isl_take isl_aff *aff) |
2112 | 764 | { |
2113 | 764 | if (!build) |
2114 | 0 | goto error; |
2115 | 764 | |
2116 | 764 | aff = isl_aff_gist(aff, isl_set_copy(build->domain)); |
2117 | 764 | |
2118 | 764 | return aff; |
2119 | 0 | error: |
2120 | 0 | isl_aff_free(aff); |
2121 | 0 | return NULL; |
2122 | 764 | } |
2123 | | |
2124 | | /* Simplify the piecewise affine expression "aff" based on what we know about |
2125 | | * the iterators of already generated loops. |
2126 | | * |
2127 | | * The domain of "pa" is assumed to live in the (internal) schedule domain. |
2128 | | */ |
2129 | | __isl_give isl_pw_aff *isl_ast_build_compute_gist_pw_aff( |
2130 | | __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa) |
2131 | 11.6k | { |
2132 | 11.6k | if (!build) |
2133 | 0 | goto error; |
2134 | 11.6k | |
2135 | 11.6k | if (!isl_set_is_params(build->domain)) |
2136 | 10.6k | pa = isl_pw_aff_pullback_multi_aff(pa, |
2137 | 10.6k | isl_multi_aff_copy(build->values)); |
2138 | 11.6k | pa = isl_pw_aff_gist(pa, isl_set_copy(build->domain)); |
2139 | 11.6k | |
2140 | 11.6k | return pa; |
2141 | 0 | error: |
2142 | 0 | isl_pw_aff_free(pa); |
2143 | 0 | return NULL; |
2144 | 11.6k | } |
2145 | | |
2146 | | /* Simplify the piecewise multi-affine expression "aff" based on what |
2147 | | * we know about the iterators of already generated loops. |
2148 | | * |
2149 | | * The domain of "pma" is assumed to live in the (internal) schedule domain. |
2150 | | */ |
2151 | | __isl_give isl_pw_multi_aff *isl_ast_build_compute_gist_pw_multi_aff( |
2152 | | __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma) |
2153 | 2.23k | { |
2154 | 2.23k | if (!build) |
2155 | 0 | goto error; |
2156 | 2.23k | |
2157 | 2.23k | pma = isl_pw_multi_aff_pullback_multi_aff(pma, |
2158 | 2.23k | isl_multi_aff_copy(build->values)); |
2159 | 2.23k | pma = isl_pw_multi_aff_gist(pma, isl_set_copy(build->domain)); |
2160 | 2.23k | |
2161 | 2.23k | return pma; |
2162 | 0 | error: |
2163 | 0 | isl_pw_multi_aff_free(pma); |
2164 | 0 | return NULL; |
2165 | 2.23k | } |
2166 | | |
2167 | | /* Extract the schedule domain of the given type from build->options |
2168 | | * at the current depth. |
2169 | | * |
2170 | | * In particular, find the subset of build->options that is of |
2171 | | * the following form |
2172 | | * |
2173 | | * schedule_domain -> type[depth] |
2174 | | * |
2175 | | * and return the corresponding domain, after eliminating inner dimensions |
2176 | | * and divs that depend on the current dimension. |
2177 | | * |
2178 | | * Note that the domain of build->options has been reformulated |
2179 | | * in terms of the internal build space in embed_options, |
2180 | | * but the position is still that within the current code generation. |
2181 | | */ |
2182 | | __isl_give isl_set *isl_ast_build_get_option_domain( |
2183 | | __isl_keep isl_ast_build *build, enum isl_ast_loop_type type) |
2184 | 252 | { |
2185 | 252 | const char *name; |
2186 | 252 | isl_space *space; |
2187 | 252 | isl_map *option; |
2188 | 252 | isl_set *domain; |
2189 | 252 | int local_pos; |
2190 | 252 | |
2191 | 252 | if (!build) |
2192 | 0 | return NULL; |
2193 | 252 | |
2194 | 252 | name = option_str[type]; |
2195 | 252 | local_pos = build->depth - build->outer_pos; |
2196 | 252 | |
2197 | 252 | space = isl_ast_build_get_space(build, 1); |
2198 | 252 | space = isl_space_from_domain(space); |
2199 | 252 | space = isl_space_add_dims(space, isl_dim_out, 1); |
2200 | 252 | space = isl_space_set_tuple_name(space, isl_dim_out, name); |
2201 | 252 | |
2202 | 252 | option = isl_union_map_extract_map(build->options, space); |
2203 | 252 | option = isl_map_fix_si(option, isl_dim_out, 0, local_pos); |
2204 | 252 | |
2205 | 252 | domain = isl_map_domain(option); |
2206 | 252 | domain = isl_ast_build_eliminate(build, domain); |
2207 | 252 | |
2208 | 252 | return domain; |
2209 | 252 | } |
2210 | | |
2211 | | /* How does the user want the current schedule dimension to be generated? |
2212 | | * These choices have been extracted from the schedule node |
2213 | | * in extract_loop_types and stored in build->loop_type. |
2214 | | * They have been updated to reflect any dimension insertion in |
2215 | | * node_insert_dim. |
2216 | | * Return isl_ast_domain_error on error. |
2217 | | * |
2218 | | * If "isolated" is set, then we get the loop AST generation type |
2219 | | * directly from the band node since node_insert_dim cannot have been |
2220 | | * called on a band with the isolate option. |
2221 | | */ |
2222 | | enum isl_ast_loop_type isl_ast_build_get_loop_type( |
2223 | | __isl_keep isl_ast_build *build, int isolated) |
2224 | 3.26k | { |
2225 | 3.26k | int local_pos; |
2226 | 3.26k | isl_ctx *ctx; |
2227 | 3.26k | |
2228 | 3.26k | if (!build) |
2229 | 0 | return isl_ast_loop_error; |
2230 | 3.26k | ctx = isl_ast_build_get_ctx(build); |
2231 | 3.26k | if (!build->node) |
2232 | 3.26k | isl_die0 (ctx, isl_error_internal, |
2233 | 3.26k | "only works for schedule tree based AST generation", |
2234 | 3.26k | return isl_ast_loop_error); |
2235 | 3.26k | |
2236 | 3.26k | local_pos = build->depth - build->outer_pos; |
2237 | 3.26k | if (!isolated) |
2238 | 2.35k | return build->loop_type[local_pos]; |
2239 | 917 | return isl_schedule_node_band_member_get_isolate_ast_loop_type( |
2240 | 917 | build->node, local_pos); |
2241 | 917 | } |
2242 | | |
2243 | | /* Extract the isolated set from the isolate option, if any, |
2244 | | * and store in the build. |
2245 | | * If there is no isolate option, then the isolated set is |
2246 | | * set to the empty set. |
2247 | | * |
2248 | | * The isolate option is of the form |
2249 | | * |
2250 | | * isolate[[outer bands] -> current_band] |
2251 | | * |
2252 | | * We flatten this set and then map it back to the internal |
2253 | | * schedule space. |
2254 | | * |
2255 | | * If we have already extracted the isolated set |
2256 | | * or if internal2input is no longer set, then we do not |
2257 | | * need to do anything. In the latter case, we know |
2258 | | * that the current band cannot have any isolate option. |
2259 | | */ |
2260 | | __isl_give isl_ast_build *isl_ast_build_extract_isolated( |
2261 | | __isl_take isl_ast_build *build) |
2262 | 2.46k | { |
2263 | 2.46k | isl_set *isolated; |
2264 | 2.46k | |
2265 | 2.46k | if (!build) |
2266 | 0 | return NULL; |
2267 | 2.46k | if (!build->internal2input) |
2268 | 12 | return build; |
2269 | 2.45k | if (build->isolated) |
2270 | 0 | return build; |
2271 | 2.45k | |
2272 | 2.45k | build = isl_ast_build_cow(build); |
2273 | 2.45k | if (!build) |
2274 | 0 | return NULL; |
2275 | 2.45k | |
2276 | 2.45k | isolated = isl_schedule_node_band_get_ast_isolate_option(build->node); |
2277 | 2.45k | isolated = isl_set_flatten(isolated); |
2278 | 2.45k | isolated = isl_set_preimage_multi_aff(isolated, |
2279 | 2.45k | isl_multi_aff_copy(build->internal2input)); |
2280 | 2.45k | |
2281 | 2.45k | build->isolated = isolated; |
2282 | 2.45k | if (!build->isolated) |
2283 | 0 | return isl_ast_build_free(build); |
2284 | 2.45k | |
2285 | 2.45k | return build; |
2286 | 2.45k | } |
2287 | | |
2288 | | /* Does "build" have a non-empty isolated set? |
2289 | | * |
2290 | | * The caller is assumed to have called isl_ast_build_extract_isolated first. |
2291 | | */ |
2292 | | int isl_ast_build_has_isolated(__isl_keep isl_ast_build *build) |
2293 | 2.46k | { |
2294 | 2.46k | int empty; |
2295 | 2.46k | |
2296 | 2.46k | if (!build) |
2297 | 0 | return -1; |
2298 | 2.46k | if (!build->internal2input) |
2299 | 12 | return 0; |
2300 | 2.45k | if (!build->isolated) |
2301 | 2.45k | isl_die0 (isl_ast_build_get_ctx(build), isl_error_internal, |
2302 | 2.45k | "isolated set not extracted yet", return -1); |
2303 | 2.45k | |
2304 | 2.45k | empty = isl_set_plain_is_empty(build->isolated); |
2305 | 2.45k | return empty < 0 ? -10 : !empty; |
2306 | 2.45k | } |
2307 | | |
2308 | | /* Return a copy of the isolated set of "build". |
2309 | | * |
2310 | | * The caller is assume to have called isl_ast_build_has_isolated first, |
2311 | | * with this function returning true. |
2312 | | * In particular, this function should not be called if we are no |
2313 | | * longer keeping track of internal2input (and there therefore could |
2314 | | * not possibly be any isolated set). |
2315 | | */ |
2316 | | __isl_give isl_set *isl_ast_build_get_isolated(__isl_keep isl_ast_build *build) |
2317 | 1.48k | { |
2318 | 1.48k | if (!build) |
2319 | 0 | return NULL; |
2320 | 1.48k | if (!build->internal2input) |
2321 | 1.48k | isl_die0 (isl_ast_build_get_ctx(build), isl_error_internal, |
2322 | 1.48k | "build cannot have isolated set", return NULL); |
2323 | 1.48k | |
2324 | 1.48k | return isl_set_copy(build->isolated); |
2325 | 1.48k | } |
2326 | | |
2327 | | /* Extract the separation class mapping at the current depth. |
2328 | | * |
2329 | | * In particular, find and return the subset of build->options that is of |
2330 | | * the following form |
2331 | | * |
2332 | | * schedule_domain -> separation_class[[depth] -> [class]] |
2333 | | * |
2334 | | * The caller is expected to eliminate inner dimensions from the domain. |
2335 | | * |
2336 | | * Note that the domain of build->options has been reformulated |
2337 | | * in terms of the internal build space in embed_options, |
2338 | | * but the position is still that within the current code generation. |
2339 | | */ |
2340 | | __isl_give isl_map *isl_ast_build_get_separation_class( |
2341 | | __isl_keep isl_ast_build *build) |
2342 | 84 | { |
2343 | 84 | isl_ctx *ctx; |
2344 | 84 | isl_space *space_sep, *space; |
2345 | 84 | isl_map *res; |
2346 | 84 | int local_pos; |
2347 | 84 | |
2348 | 84 | if (!build) |
2349 | 0 | return NULL; |
2350 | 84 | |
2351 | 84 | local_pos = build->depth - build->outer_pos; |
2352 | 84 | ctx = isl_ast_build_get_ctx(build); |
2353 | 84 | space_sep = isl_space_alloc(ctx, 0, 1, 1); |
2354 | 84 | space_sep = isl_space_wrap(space_sep); |
2355 | 84 | space_sep = isl_space_set_tuple_name(space_sep, isl_dim_set, |
2356 | 84 | "separation_class"); |
2357 | 84 | space = isl_ast_build_get_space(build, 1); |
2358 | 84 | space_sep = isl_space_align_params(space_sep, isl_space_copy(space)); |
2359 | 84 | space = isl_space_map_from_domain_and_range(space, space_sep); |
2360 | 84 | |
2361 | 84 | res = isl_union_map_extract_map(build->options, space); |
2362 | 84 | res = isl_map_fix_si(res, isl_dim_out, 0, local_pos); |
2363 | 84 | res = isl_map_coalesce(res); |
2364 | 84 | |
2365 | 84 | return res; |
2366 | 84 | } |
2367 | | |
2368 | | /* Eliminate dimensions inner to the current dimension. |
2369 | | */ |
2370 | | __isl_give isl_set *isl_ast_build_eliminate_inner( |
2371 | | __isl_keep isl_ast_build *build, __isl_take isl_set *set) |
2372 | 10.2k | { |
2373 | 10.2k | int dim; |
2374 | 10.2k | int depth; |
2375 | 10.2k | |
2376 | 10.2k | if (!build) |
2377 | 0 | return isl_set_free(set); |
2378 | 10.2k | |
2379 | 10.2k | dim = isl_set_dim(set, isl_dim_set); |
2380 | 10.2k | depth = build->depth; |
2381 | 10.2k | set = isl_set_detect_equalities(set); |
2382 | 10.2k | set = isl_set_eliminate(set, isl_dim_set, depth + 1, dim - (depth + 1)); |
2383 | 10.2k | |
2384 | 10.2k | return set; |
2385 | 10.2k | } |
2386 | | |
2387 | | /* Eliminate unknown divs and divs that depend on the current dimension. |
2388 | | * |
2389 | | * Note that during the elimination of unknown divs, we may discover |
2390 | | * an explicit representation of some other unknown divs, which may |
2391 | | * depend on the current dimension. We therefore need to eliminate |
2392 | | * unknown divs first. |
2393 | | */ |
2394 | | __isl_give isl_set *isl_ast_build_eliminate_divs( |
2395 | | __isl_keep isl_ast_build *build, __isl_take isl_set *set) |
2396 | 8.56k | { |
2397 | 8.56k | int depth; |
2398 | 8.56k | |
2399 | 8.56k | if (!build) |
2400 | 0 | return isl_set_free(set); |
2401 | 8.56k | |
2402 | 8.56k | set = isl_set_remove_unknown_divs(set); |
2403 | 8.56k | depth = build->depth; |
2404 | 8.56k | set = isl_set_remove_divs_involving_dims(set, isl_dim_set, depth, 1); |
2405 | 8.56k | |
2406 | 8.56k | return set; |
2407 | 8.56k | } |
2408 | | |
2409 | | /* Eliminate dimensions inner to the current dimension as well as |
2410 | | * unknown divs and divs that depend on the current dimension. |
2411 | | * The result then consists only of constraints that are independent |
2412 | | * of the current dimension and upper and lower bounds on the current |
2413 | | * dimension. |
2414 | | */ |
2415 | | __isl_give isl_set *isl_ast_build_eliminate( |
2416 | | __isl_keep isl_ast_build *build, __isl_take isl_set *domain) |
2417 | 2.12k | { |
2418 | 2.12k | domain = isl_ast_build_eliminate_inner(build, domain); |
2419 | 2.12k | domain = isl_ast_build_eliminate_divs(build, domain); |
2420 | 2.12k | return domain; |
2421 | 2.12k | } |
2422 | | |
2423 | | /* Replace build->single_valued by "sv". |
2424 | | */ |
2425 | | __isl_give isl_ast_build *isl_ast_build_set_single_valued( |
2426 | | __isl_take isl_ast_build *build, int sv) |
2427 | 489 | { |
2428 | 489 | if (!build) |
2429 | 0 | return build; |
2430 | 489 | if (build->single_valued == sv) |
2431 | 467 | return build; |
2432 | 22 | build = isl_ast_build_cow(build); |
2433 | 22 | if (!build) |
2434 | 0 | return build; |
2435 | 22 | build->single_valued = sv; |
2436 | 22 | |
2437 | 22 | return build; |
2438 | 22 | } |