Line data Source code
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 0 : __isl_give isl_map *isl_ast_build_map_to_iterator(
33 : __isl_keep isl_ast_build *build, __isl_take isl_set *set)
34 : {
35 : isl_map *map;
36 :
37 0 : map = isl_map_from_domain(set);
38 0 : map = isl_map_add_dims(map, isl_dim_out, 1);
39 :
40 0 : if (!build)
41 0 : return isl_map_free(map);
42 :
43 0 : map = isl_map_equate(map, isl_dim_in, build->depth, isl_dim_out, 0);
44 0 : map = isl_map_eliminate(map, isl_dim_in, build->depth, 1);
45 :
46 0 : return map;
47 : }
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 0 : static __isl_give isl_ast_build *isl_ast_build_init_derived(
56 : __isl_take isl_ast_build *build, __isl_take isl_space *space)
57 : {
58 : isl_ctx *ctx;
59 : isl_vec *strides;
60 :
61 0 : build = isl_ast_build_cow(build);
62 0 : if (!build || !build->domain)
63 : goto error;
64 :
65 0 : ctx = isl_ast_build_get_ctx(build);
66 0 : strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set));
67 0 : strides = isl_vec_set_si(strides, 1);
68 :
69 0 : isl_vec_free(build->strides);
70 0 : build->strides = strides;
71 :
72 0 : space = isl_space_map_from_set(space);
73 0 : isl_multi_aff_free(build->offsets);
74 0 : build->offsets = isl_multi_aff_zero(isl_space_copy(space));
75 0 : isl_multi_aff_free(build->values);
76 0 : build->values = isl_multi_aff_identity(isl_space_copy(space));
77 0 : isl_multi_aff_free(build->internal2input);
78 0 : build->internal2input = isl_multi_aff_identity(space);
79 :
80 0 : if (!build->iterators || !build->domain || !build->generated ||
81 0 : !build->pending || !build->values || !build->internal2input ||
82 0 : !build->strides || !build->offsets || !build->options)
83 0 : return isl_ast_build_free(build);
84 :
85 0 : return build;
86 : error:
87 0 : isl_space_free(space);
88 0 : return isl_ast_build_free(build);
89 : }
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 0 : static __isl_give isl_id *generate_name(isl_ctx *ctx, int i,
96 : __isl_keep isl_ast_build *build)
97 : {
98 : int j;
99 : char name[23];
100 0 : isl_set *dom = build->domain;
101 :
102 0 : snprintf(name, sizeof(name), "c%d", i);
103 0 : j = 0;
104 0 : while (isl_set_find_dim_by_name(dom, isl_dim_param, name) >= 0)
105 0 : snprintf(name, sizeof(name), "c%d_%d", i, j++);
106 0 : return isl_id_alloc(ctx, name, NULL);
107 : }
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 0 : __isl_give isl_ast_build *isl_ast_build_from_context(__isl_take isl_set *set)
116 : {
117 : int i, n;
118 : isl_ctx *ctx;
119 : isl_space *space;
120 : isl_ast_build *build;
121 :
122 0 : set = isl_set_compute_divs(set);
123 0 : if (!set)
124 0 : return NULL;
125 :
126 0 : ctx = isl_set_get_ctx(set);
127 :
128 0 : build = isl_calloc_type(ctx, isl_ast_build);
129 0 : if (!build)
130 0 : goto error;
131 :
132 0 : build->ref = 1;
133 0 : build->domain = set;
134 0 : build->generated = isl_set_copy(build->domain);
135 0 : build->pending = isl_set_universe(isl_set_get_space(build->domain));
136 0 : build->options = isl_union_map_empty(isl_space_params_alloc(ctx, 0));
137 0 : n = isl_set_dim(set, isl_dim_set);
138 0 : build->depth = n;
139 0 : build->iterators = isl_id_list_alloc(ctx, n);
140 0 : for (i = 0; i < n; ++i) {
141 : 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 : else
145 0 : id = generate_name(ctx, i, build);
146 0 : build->iterators = isl_id_list_add(build->iterators, id);
147 : }
148 0 : space = isl_set_get_space(set);
149 0 : if (isl_space_is_params(space))
150 0 : space = isl_space_set_from_params(space);
151 :
152 0 : return isl_ast_build_init_derived(build, space);
153 : error:
154 0 : isl_set_free(set);
155 0 : return NULL;
156 : }
157 :
158 : /* Create an isl_ast_build with a universe (parametric) context.
159 : */
160 0 : __isl_give isl_ast_build *isl_ast_build_alloc(isl_ctx *ctx)
161 : {
162 : isl_space *space;
163 : isl_set *context;
164 :
165 0 : space = isl_space_params_alloc(ctx, 0);
166 0 : context = isl_set_universe(space);
167 :
168 0 : return isl_ast_build_from_context(context);
169 : }
170 :
171 0 : __isl_give isl_ast_build *isl_ast_build_copy(__isl_keep isl_ast_build *build)
172 : {
173 0 : if (!build)
174 0 : return NULL;
175 :
176 0 : build->ref++;
177 0 : return build;
178 : }
179 :
180 0 : __isl_give isl_ast_build *isl_ast_build_dup(__isl_keep isl_ast_build *build)
181 : {
182 : isl_ctx *ctx;
183 : isl_ast_build *dup;
184 :
185 0 : if (!build)
186 0 : return NULL;
187 :
188 0 : ctx = isl_ast_build_get_ctx(build);
189 0 : dup = isl_calloc_type(ctx, isl_ast_build);
190 0 : if (!dup)
191 0 : return NULL;
192 :
193 0 : dup->ref = 1;
194 0 : dup->outer_pos = build->outer_pos;
195 0 : dup->depth = build->depth;
196 0 : dup->iterators = isl_id_list_copy(build->iterators);
197 0 : dup->domain = isl_set_copy(build->domain);
198 0 : dup->generated = isl_set_copy(build->generated);
199 0 : dup->pending = isl_set_copy(build->pending);
200 0 : dup->values = isl_multi_aff_copy(build->values);
201 0 : dup->internal2input = isl_multi_aff_copy(build->internal2input);
202 0 : dup->value = isl_pw_aff_copy(build->value);
203 0 : dup->strides = isl_vec_copy(build->strides);
204 0 : dup->offsets = isl_multi_aff_copy(build->offsets);
205 0 : dup->executed = isl_union_map_copy(build->executed);
206 0 : dup->single_valued = build->single_valued;
207 0 : dup->options = isl_union_map_copy(build->options);
208 0 : dup->at_each_domain = build->at_each_domain;
209 0 : dup->at_each_domain_user = build->at_each_domain_user;
210 0 : dup->before_each_for = build->before_each_for;
211 0 : dup->before_each_for_user = build->before_each_for_user;
212 0 : dup->after_each_for = build->after_each_for;
213 0 : dup->after_each_for_user = build->after_each_for_user;
214 0 : dup->before_each_mark = build->before_each_mark;
215 0 : dup->before_each_mark_user = build->before_each_mark_user;
216 0 : dup->after_each_mark = build->after_each_mark;
217 0 : dup->after_each_mark_user = build->after_each_mark_user;
218 0 : dup->create_leaf = build->create_leaf;
219 0 : dup->create_leaf_user = build->create_leaf_user;
220 0 : dup->node = isl_schedule_node_copy(build->node);
221 0 : if (build->loop_type) {
222 : int i;
223 :
224 0 : dup->n = build->n;
225 0 : dup->loop_type = isl_alloc_array(ctx,
226 : enum isl_ast_loop_type, dup->n);
227 0 : if (dup->n && !dup->loop_type)
228 0 : return isl_ast_build_free(dup);
229 0 : for (i = 0; i < dup->n; ++i)
230 0 : dup->loop_type[i] = build->loop_type[i];
231 : }
232 :
233 0 : if (!dup->iterators || !dup->domain || !dup->generated ||
234 0 : !dup->pending || !dup->values ||
235 0 : !dup->strides || !dup->offsets || !dup->options ||
236 0 : (build->internal2input && !dup->internal2input) ||
237 0 : (build->executed && !dup->executed) ||
238 0 : (build->value && !dup->value) ||
239 0 : (build->node && !dup->node))
240 0 : return isl_ast_build_free(dup);
241 :
242 0 : return dup;
243 : }
244 :
245 : /* Align the parameters of "build" to those of "model", introducing
246 : * additional parameters if needed.
247 : */
248 0 : __isl_give isl_ast_build *isl_ast_build_align_params(
249 : __isl_take isl_ast_build *build, __isl_take isl_space *model)
250 : {
251 0 : build = isl_ast_build_cow(build);
252 0 : if (!build)
253 0 : goto error;
254 :
255 0 : build->domain = isl_set_align_params(build->domain,
256 : isl_space_copy(model));
257 0 : build->generated = isl_set_align_params(build->generated,
258 : isl_space_copy(model));
259 0 : build->pending = isl_set_align_params(build->pending,
260 : isl_space_copy(model));
261 0 : build->values = isl_multi_aff_align_params(build->values,
262 : isl_space_copy(model));
263 0 : build->offsets = isl_multi_aff_align_params(build->offsets,
264 : isl_space_copy(model));
265 0 : build->options = isl_union_map_align_params(build->options,
266 : isl_space_copy(model));
267 0 : if (build->internal2input) {
268 0 : build->internal2input =
269 0 : isl_multi_aff_align_params(build->internal2input,
270 : model);
271 0 : if (!build->internal2input)
272 0 : return isl_ast_build_free(build);
273 : } else {
274 0 : isl_space_free(model);
275 : }
276 :
277 0 : if (!build->domain || !build->values || !build->offsets ||
278 0 : !build->options)
279 0 : return isl_ast_build_free(build);
280 :
281 0 : return build;
282 : error:
283 0 : isl_space_free(model);
284 0 : return NULL;
285 : }
286 :
287 0 : __isl_give isl_ast_build *isl_ast_build_cow(__isl_take isl_ast_build *build)
288 : {
289 0 : if (!build)
290 0 : return NULL;
291 :
292 0 : if (build->ref == 1)
293 0 : return build;
294 0 : build->ref--;
295 0 : return isl_ast_build_dup(build);
296 : }
297 :
298 0 : __isl_null isl_ast_build *isl_ast_build_free(
299 : __isl_take isl_ast_build *build)
300 : {
301 0 : if (!build)
302 0 : return NULL;
303 :
304 0 : if (--build->ref > 0)
305 0 : return NULL;
306 :
307 0 : isl_id_list_free(build->iterators);
308 0 : isl_set_free(build->domain);
309 0 : isl_set_free(build->generated);
310 0 : isl_set_free(build->pending);
311 0 : isl_multi_aff_free(build->values);
312 0 : isl_multi_aff_free(build->internal2input);
313 0 : isl_pw_aff_free(build->value);
314 0 : isl_vec_free(build->strides);
315 0 : isl_multi_aff_free(build->offsets);
316 0 : isl_multi_aff_free(build->schedule_map);
317 0 : isl_union_map_free(build->executed);
318 0 : isl_union_map_free(build->options);
319 0 : isl_schedule_node_free(build->node);
320 0 : free(build->loop_type);
321 0 : isl_set_free(build->isolated);
322 :
323 0 : free(build);
324 :
325 0 : return NULL;
326 : }
327 :
328 0 : isl_ctx *isl_ast_build_get_ctx(__isl_keep isl_ast_build *build)
329 : {
330 0 : return build ? isl_set_get_ctx(build->domain) : NULL;
331 : }
332 :
333 : /* Replace build->options by "options".
334 : */
335 0 : __isl_give isl_ast_build *isl_ast_build_set_options(
336 : __isl_take isl_ast_build *build, __isl_take isl_union_map *options)
337 : {
338 0 : build = isl_ast_build_cow(build);
339 :
340 0 : if (!build || !options)
341 : goto error;
342 :
343 0 : isl_union_map_free(build->options);
344 0 : build->options = options;
345 :
346 0 : return build;
347 : error:
348 0 : isl_union_map_free(options);
349 0 : return isl_ast_build_free(build);
350 : }
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 0 : __isl_give isl_ast_build *isl_ast_build_set_iterators(
359 : __isl_take isl_ast_build *build, __isl_take isl_id_list *iterators)
360 : {
361 : int dim, n_it;
362 :
363 0 : build = isl_ast_build_cow(build);
364 0 : if (!build)
365 0 : goto error;
366 :
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 : "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 :
379 0 : return build;
380 : error:
381 0 : isl_id_list_free(iterators);
382 0 : return isl_ast_build_free(build);
383 : }
384 :
385 : /* Set the "at_each_domain" callback of "build" to "fn".
386 : */
387 0 : __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 : {
392 0 : build = isl_ast_build_cow(build);
393 :
394 0 : if (!build)
395 0 : return NULL;
396 :
397 0 : build->at_each_domain = fn;
398 0 : build->at_each_domain_user = user;
399 :
400 0 : return build;
401 : }
402 :
403 : /* Set the "before_each_for" callback of "build" to "fn".
404 : */
405 0 : __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 : {
410 0 : build = isl_ast_build_cow(build);
411 :
412 0 : if (!build)
413 0 : return NULL;
414 :
415 0 : build->before_each_for = fn;
416 0 : build->before_each_for_user = user;
417 :
418 0 : return build;
419 : }
420 :
421 : /* Set the "after_each_for" callback of "build" to "fn".
422 : */
423 0 : __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 : {
428 0 : build = isl_ast_build_cow(build);
429 :
430 0 : if (!build)
431 0 : return NULL;
432 :
433 0 : build->after_each_for = fn;
434 0 : build->after_each_for_user = user;
435 :
436 0 : return build;
437 : }
438 :
439 : /* Set the "before_each_mark" callback of "build" to "fn".
440 : */
441 0 : __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 : {
446 0 : build = isl_ast_build_cow(build);
447 :
448 0 : if (!build)
449 0 : return NULL;
450 :
451 0 : build->before_each_mark = fn;
452 0 : build->before_each_mark_user = user;
453 :
454 0 : return build;
455 : }
456 :
457 : /* Set the "after_each_mark" callback of "build" to "fn".
458 : */
459 0 : __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 : {
464 0 : build = isl_ast_build_cow(build);
465 :
466 0 : if (!build)
467 0 : return NULL;
468 :
469 0 : build->after_each_mark = fn;
470 0 : build->after_each_mark_user = user;
471 :
472 0 : return build;
473 : }
474 :
475 : /* Set the "create_leaf" callback of "build" to "fn".
476 : */
477 0 : __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 : {
482 0 : build = isl_ast_build_cow(build);
483 :
484 0 : if (!build)
485 0 : return NULL;
486 :
487 0 : build->create_leaf = fn;
488 0 : build->create_leaf_user = user;
489 :
490 0 : return build;
491 : }
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 0 : __isl_give isl_ast_build *isl_ast_build_clear_local_info(
497 : __isl_take isl_ast_build *build)
498 : {
499 : isl_space *space;
500 :
501 0 : build = isl_ast_build_cow(build);
502 0 : if (!build)
503 0 : return NULL;
504 :
505 0 : space = isl_union_map_get_space(build->options);
506 0 : isl_union_map_free(build->options);
507 0 : build->options = isl_union_map_empty(space);
508 :
509 0 : build->at_each_domain = NULL;
510 0 : build->at_each_domain_user = NULL;
511 0 : build->before_each_for = NULL;
512 0 : build->before_each_for_user = NULL;
513 0 : build->after_each_for = NULL;
514 0 : build->after_each_for_user = NULL;
515 0 : build->before_each_mark = NULL;
516 0 : build->before_each_mark_user = NULL;
517 0 : build->after_each_mark = NULL;
518 0 : build->after_each_mark_user = NULL;
519 0 : build->create_leaf = NULL;
520 0 : build->create_leaf_user = NULL;
521 :
522 0 : if (!build->options)
523 0 : return isl_ast_build_free(build);
524 :
525 0 : return build;
526 : }
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 0 : static int any_eliminated(isl_ast_build *build)
533 : {
534 : int i;
535 :
536 0 : for (i = 0; i < build->depth; ++i)
537 0 : if (isl_ast_build_has_affine_value(build, i))
538 0 : return 1;
539 :
540 0 : return 0;
541 : }
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 0 : static void isl_ast_build_reset_schedule_map(__isl_keep isl_ast_build *build)
550 : {
551 0 : if (!build)
552 0 : return;
553 0 : isl_multi_aff_free(build->schedule_map);
554 0 : build->schedule_map = NULL;
555 : }
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 0 : __isl_give int isl_ast_build_need_schedule_map(__isl_keep isl_ast_build *build)
566 : {
567 : int dim;
568 :
569 0 : if (!build)
570 0 : return -1;
571 :
572 0 : dim = isl_set_dim(build->domain, isl_dim_set);
573 0 : return build->depth != dim || any_eliminated(build);
574 : }
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 0 : __isl_give isl_multi_aff *isl_ast_build_get_schedule_map_multi_aff(
595 : __isl_keep isl_ast_build *build)
596 : {
597 : isl_space *space;
598 : isl_multi_aff *ma;
599 :
600 0 : if (!build)
601 0 : return NULL;
602 0 : if (build->schedule_map)
603 0 : return isl_multi_aff_copy(build->schedule_map);
604 :
605 0 : space = isl_ast_build_get_space(build, 1);
606 0 : space = isl_space_map_from_set(space);
607 0 : ma = isl_multi_aff_identity(space);
608 0 : if (isl_ast_build_need_schedule_map(build)) {
609 : int i;
610 0 : int dim = isl_set_dim(build->domain, isl_dim_set);
611 0 : ma = isl_multi_aff_drop_dims(ma, isl_dim_out,
612 0 : build->depth, dim - build->depth);
613 0 : for (i = build->depth - 1; i >= 0; --i)
614 0 : if (isl_ast_build_has_affine_value(build, i))
615 0 : ma = isl_multi_aff_drop_dims(ma,
616 : isl_dim_out, i, 1);
617 : }
618 :
619 0 : build->schedule_map = ma;
620 0 : return isl_multi_aff_copy(build->schedule_map);
621 : }
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 0 : __isl_give isl_map *isl_ast_build_get_schedule_map(
627 : __isl_keep isl_ast_build *build)
628 : {
629 : isl_multi_aff *ma;
630 :
631 0 : ma = isl_ast_build_get_schedule_map_multi_aff(build);
632 0 : return isl_map_from_multi_aff(ma);
633 : }
634 :
635 : /* Return the position of the dimension in build->domain for which
636 : * an AST node is currently being generated.
637 : */
638 0 : int isl_ast_build_get_depth(__isl_keep isl_ast_build *build)
639 : {
640 0 : return build ? build->depth : -1;
641 : }
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 0 : __isl_give isl_ast_build *isl_ast_build_increase_depth(
648 : __isl_take isl_ast_build *build)
649 : {
650 0 : build = isl_ast_build_cow(build);
651 0 : if (!build)
652 0 : return NULL;
653 0 : build->depth++;
654 0 : isl_ast_build_reset_schedule_map(build);
655 0 : build->value = isl_pw_aff_free(build->value);
656 0 : return build;
657 : }
658 :
659 0 : void isl_ast_build_dump(__isl_keep isl_ast_build *build)
660 : {
661 0 : if (!build)
662 0 : return;
663 :
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 : }
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 : }
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 0 : static __isl_give isl_ast_build *isl_ast_build_init(
692 : __isl_take isl_ast_build *build, __isl_take isl_space *space)
693 : {
694 : isl_set *set;
695 :
696 0 : build = isl_ast_build_cow(build);
697 0 : if (!build)
698 0 : goto error;
699 :
700 0 : set = isl_set_universe(isl_space_copy(space));
701 0 : build->domain = isl_set_intersect_params(isl_set_copy(set),
702 : build->domain);
703 0 : build->pending = isl_set_intersect_params(isl_set_copy(set),
704 : build->pending);
705 0 : build->generated = isl_set_intersect_params(set, build->generated);
706 :
707 0 : return isl_ast_build_init_derived(build, space);
708 : error:
709 0 : isl_ast_build_free(build);
710 0 : isl_space_free(space);
711 0 : return NULL;
712 : }
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 0 : static isl_stat extract_single_piece(__isl_take isl_set *set,
719 : __isl_take isl_aff *aff, void *user)
720 : {
721 0 : isl_aff **p = user;
722 :
723 0 : *p = aff;
724 0 : isl_set_free(set);
725 :
726 0 : return isl_stat_error;
727 : }
728 :
729 : /* Intersect "set" with the stride constraint of "build", if any.
730 : */
731 0 : static __isl_give isl_set *intersect_stride_constraint(__isl_take isl_set *set,
732 : __isl_keep isl_ast_build *build)
733 : {
734 : isl_set *stride;
735 :
736 0 : if (!build)
737 0 : return isl_set_free(set);
738 0 : if (!isl_ast_build_has_stride(build, build->depth))
739 0 : return set;
740 :
741 0 : stride = isl_ast_build_get_stride_constraint(build);
742 0 : return isl_set_intersect(set, stride);
743 : }
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 0 : static __isl_give isl_ast_build *update_values(
763 : __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
764 : {
765 : int sv;
766 : isl_pw_multi_aff *pma;
767 0 : isl_aff *aff = NULL;
768 : isl_map *it_map;
769 : isl_set *set;
770 :
771 0 : set = isl_set_from_basic_set(bounds);
772 0 : set = isl_set_intersect(set, isl_set_copy(build->domain));
773 0 : set = intersect_stride_constraint(set, build);
774 0 : it_map = isl_ast_build_map_to_iterator(build, set);
775 :
776 0 : sv = isl_map_is_single_valued(it_map);
777 0 : if (sv < 0)
778 0 : build = isl_ast_build_free(build);
779 0 : if (!build || !sv) {
780 0 : isl_map_free(it_map);
781 0 : return build;
782 : }
783 :
784 0 : pma = isl_pw_multi_aff_from_map(it_map);
785 0 : build->value = isl_pw_multi_aff_get_pw_aff(pma, 0);
786 0 : build->value = isl_ast_build_compute_gist_pw_aff(build, build->value);
787 0 : build->value = isl_pw_aff_coalesce(build->value);
788 0 : isl_pw_multi_aff_free(pma);
789 :
790 0 : if (!build->value)
791 0 : return isl_ast_build_free(build);
792 :
793 0 : if (isl_pw_aff_n_piece(build->value) != 1)
794 0 : return build;
795 :
796 0 : isl_pw_aff_foreach_piece(build->value, &extract_single_piece, &aff);
797 :
798 0 : build->values = isl_multi_aff_set_aff(build->values, build->depth, aff);
799 0 : if (!build->values)
800 0 : return isl_ast_build_free(build);
801 0 : isl_ast_build_reset_schedule_map(build);
802 0 : return build;
803 : }
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 0 : __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 : {
839 : isl_set *set;
840 :
841 0 : build = isl_ast_build_cow(build);
842 0 : if (!build)
843 0 : goto error;
844 :
845 0 : build = update_values(build, isl_basic_set_copy(bounds));
846 0 : if (!build)
847 0 : goto error;
848 0 : set = isl_set_from_basic_set(isl_basic_set_copy(bounds));
849 0 : if (isl_ast_build_has_affine_value(build, build->depth)) {
850 0 : set = isl_set_eliminate(set, isl_dim_set, build->depth, 1);
851 0 : set = isl_set_compute_divs(set);
852 0 : build->pending = isl_set_intersect(build->pending,
853 : isl_set_copy(set));
854 0 : build->domain = isl_set_intersect(build->domain, set);
855 : } else {
856 0 : build->domain = isl_set_intersect(build->domain, set);
857 0 : build = isl_ast_build_include_stride(build);
858 0 : if (!build)
859 0 : goto error;
860 : }
861 0 : isl_basic_set_free(bounds);
862 :
863 0 : if (!build->domain || !build->pending || !build->generated)
864 0 : return isl_ast_build_free(build);
865 :
866 0 : return build;
867 : error:
868 0 : isl_ast_build_free(build);
869 0 : isl_basic_set_free(bounds);
870 0 : return NULL;
871 : }
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 0 : __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 : {
881 : isl_basic_set *generated, *pending;
882 :
883 0 : if (!build)
884 0 : goto error;
885 :
886 0 : if (isl_ast_build_has_affine_value(build, build->depth)) {
887 0 : isl_basic_set_free(bounds);
888 0 : return build;
889 : }
890 :
891 0 : build = isl_ast_build_cow(build);
892 0 : if (!build)
893 0 : goto error;
894 :
895 0 : pending = isl_basic_set_copy(bounds);
896 0 : pending = isl_basic_set_drop_constraints_involving_dims(pending,
897 0 : isl_dim_set, build->depth, 1);
898 0 : build->pending = isl_set_intersect(build->pending,
899 : isl_set_from_basic_set(pending));
900 0 : generated = bounds;
901 0 : generated = isl_basic_set_drop_constraints_not_involving_dims(
902 0 : generated, isl_dim_set, build->depth, 1);
903 0 : build->generated = isl_set_intersect(build->generated,
904 : isl_set_from_basic_set(generated));
905 :
906 0 : if (!build->pending || !build->generated)
907 0 : return isl_ast_build_free(build);
908 :
909 0 : return build;
910 : error:
911 0 : isl_ast_build_free(build);
912 0 : isl_basic_set_free(bounds);
913 0 : return NULL;
914 : }
915 :
916 : /* Intersect build->domain with "set", where "set" is specified
917 : * in terms of the internal schedule domain.
918 : */
919 0 : static __isl_give isl_ast_build *isl_ast_build_restrict_internal(
920 : __isl_take isl_ast_build *build, __isl_take isl_set *set)
921 : {
922 0 : build = isl_ast_build_cow(build);
923 0 : if (!build)
924 0 : goto error;
925 :
926 0 : set = isl_set_compute_divs(set);
927 0 : build->domain = isl_set_intersect(build->domain, set);
928 0 : build->domain = isl_set_coalesce(build->domain);
929 :
930 0 : if (!build->domain)
931 0 : return isl_ast_build_free(build);
932 :
933 0 : return build;
934 : error:
935 0 : isl_ast_build_free(build);
936 0 : isl_set_free(set);
937 0 : return NULL;
938 : }
939 :
940 : /* Intersect build->generated and build->domain with "set",
941 : * where "set" is specified in terms of the internal schedule domain.
942 : */
943 0 : __isl_give isl_ast_build *isl_ast_build_restrict_generated(
944 : __isl_take isl_ast_build *build, __isl_take isl_set *set)
945 : {
946 0 : set = isl_set_compute_divs(set);
947 0 : build = isl_ast_build_restrict_internal(build, isl_set_copy(set));
948 0 : build = isl_ast_build_cow(build);
949 0 : if (!build)
950 0 : goto error;
951 :
952 0 : build->generated = isl_set_intersect(build->generated, set);
953 0 : build->generated = isl_set_coalesce(build->generated);
954 :
955 0 : if (!build->generated)
956 0 : return isl_ast_build_free(build);
957 :
958 0 : return build;
959 : error:
960 0 : isl_ast_build_free(build);
961 0 : isl_set_free(set);
962 0 : return NULL;
963 : }
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 0 : __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 : {
973 0 : build = isl_ast_build_restrict_generated(build, guard);
974 0 : build = isl_ast_build_cow(build);
975 0 : if (!build)
976 0 : return NULL;
977 :
978 0 : isl_set_free(build->domain);
979 0 : build->domain = isl_set_copy(build->generated);
980 0 : isl_set_free(build->pending);
981 0 : build->pending = isl_set_universe(isl_set_get_space(build->domain));
982 :
983 0 : if (!build->pending)
984 0 : return isl_ast_build_free(build);
985 :
986 0 : return build;
987 : }
988 :
989 : /* Intersect build->domain with "set", where "set" is specified
990 : * in terms of the external schedule domain.
991 : */
992 0 : __isl_give isl_ast_build *isl_ast_build_restrict(
993 : __isl_take isl_ast_build *build, __isl_take isl_set *set)
994 : {
995 0 : if (isl_set_is_params(set))
996 0 : return isl_ast_build_restrict_generated(build, set);
997 :
998 0 : if (isl_ast_build_need_schedule_map(build)) {
999 : isl_multi_aff *ma;
1000 0 : ma = isl_ast_build_get_schedule_map_multi_aff(build);
1001 0 : set = isl_set_preimage_multi_aff(set, ma);
1002 : }
1003 0 : return isl_ast_build_restrict_generated(build, set);
1004 : }
1005 :
1006 : /* Replace build->executed by "executed".
1007 : */
1008 0 : __isl_give isl_ast_build *isl_ast_build_set_executed(
1009 : __isl_take isl_ast_build *build, __isl_take isl_union_map *executed)
1010 : {
1011 0 : build = isl_ast_build_cow(build);
1012 0 : if (!build)
1013 0 : goto error;
1014 :
1015 0 : isl_union_map_free(build->executed);
1016 0 : build->executed = executed;
1017 :
1018 0 : return build;
1019 : error:
1020 0 : isl_ast_build_free(build);
1021 0 : isl_union_map_free(executed);
1022 0 : return NULL;
1023 : }
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 0 : int isl_ast_build_has_schedule_node(__isl_keep isl_ast_build *build)
1029 : {
1030 0 : if (!build)
1031 0 : return -1;
1032 0 : return build->node != NULL;
1033 : }
1034 :
1035 : /* Return a copy of the band node that "build" refers to.
1036 : */
1037 0 : __isl_give isl_schedule_node *isl_ast_build_get_schedule_node(
1038 : __isl_keep isl_ast_build *build)
1039 : {
1040 0 : if (!build)
1041 0 : return NULL;
1042 0 : return isl_schedule_node_copy(build->node);
1043 : }
1044 :
1045 : /* Extract the loop AST generation types for the members of build->node
1046 : * and store them in build->loop_type.
1047 : */
1048 0 : static __isl_give isl_ast_build *extract_loop_types(
1049 : __isl_take isl_ast_build *build)
1050 : {
1051 : int i;
1052 : isl_ctx *ctx;
1053 : isl_schedule_node *node;
1054 :
1055 0 : if (!build)
1056 0 : return NULL;
1057 0 : ctx = isl_ast_build_get_ctx(build);
1058 0 : if (!build->node)
1059 0 : isl_die(ctx, isl_error_internal, "missing AST node",
1060 : return isl_ast_build_free(build));
1061 :
1062 0 : free(build->loop_type);
1063 0 : build->n = isl_schedule_node_band_n_member(build->node);
1064 0 : build->loop_type = isl_alloc_array(ctx,
1065 : enum isl_ast_loop_type, build->n);
1066 0 : if (build->n && !build->loop_type)
1067 0 : return isl_ast_build_free(build);
1068 0 : node = build->node;
1069 0 : for (i = 0; i < build->n; ++i)
1070 0 : build->loop_type[i] =
1071 0 : isl_schedule_node_band_member_get_ast_loop_type(node, i);
1072 :
1073 0 : return build;
1074 : }
1075 :
1076 : /* Replace the band node that "build" refers to by "node" and
1077 : * extract the corresponding loop AST generation types.
1078 : */
1079 0 : __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 : {
1083 0 : build = isl_ast_build_cow(build);
1084 0 : if (!build || !node)
1085 : goto error;
1086 :
1087 0 : isl_schedule_node_free(build->node);
1088 0 : build->node = node;
1089 :
1090 0 : build = extract_loop_types(build);
1091 :
1092 0 : return build;
1093 : error:
1094 0 : isl_ast_build_free(build);
1095 0 : isl_schedule_node_free(node);
1096 0 : return NULL;
1097 : }
1098 :
1099 : /* Remove any reference to a band node from "build".
1100 : */
1101 0 : __isl_give isl_ast_build *isl_ast_build_reset_schedule_node(
1102 : __isl_take isl_ast_build *build)
1103 : {
1104 0 : build = isl_ast_build_cow(build);
1105 0 : if (!build)
1106 0 : return NULL;
1107 :
1108 0 : isl_schedule_node_free(build->node);
1109 0 : build->node = NULL;
1110 :
1111 0 : return build;
1112 : }
1113 :
1114 : /* Return a copy of the current schedule domain.
1115 : */
1116 0 : __isl_give isl_set *isl_ast_build_get_domain(__isl_keep isl_ast_build *build)
1117 : {
1118 0 : return build ? isl_set_copy(build->domain) : NULL;
1119 : }
1120 :
1121 : /* Return a copy of the set of pending constraints.
1122 : */
1123 0 : __isl_give isl_set *isl_ast_build_get_pending(
1124 : __isl_keep isl_ast_build *build)
1125 : {
1126 0 : return build ? isl_set_copy(build->pending) : NULL;
1127 : }
1128 :
1129 : /* Return a copy of the set of generated constraints.
1130 : */
1131 0 : __isl_give isl_set *isl_ast_build_get_generated(
1132 : __isl_keep isl_ast_build *build)
1133 : {
1134 0 : return build ? isl_set_copy(build->generated) : NULL;
1135 : }
1136 :
1137 : /* Return a copy of the map from the internal schedule domain
1138 : * to the original input schedule domain.
1139 : */
1140 0 : __isl_give isl_multi_aff *isl_ast_build_get_internal2input(
1141 : __isl_keep isl_ast_build *build)
1142 : {
1143 0 : return build ? isl_multi_aff_copy(build->internal2input) : NULL;
1144 : }
1145 :
1146 : /* Return the number of variables of the given type
1147 : * in the (internal) schedule space.
1148 : */
1149 0 : unsigned isl_ast_build_dim(__isl_keep isl_ast_build *build,
1150 : enum isl_dim_type type)
1151 : {
1152 0 : if (!build)
1153 0 : return 0;
1154 0 : return isl_set_dim(build->domain, type);
1155 : }
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 0 : __isl_give isl_space *isl_ast_build_get_space(__isl_keep isl_ast_build *build,
1167 : int internal)
1168 : {
1169 : int i;
1170 : int dim;
1171 : isl_space *space;
1172 :
1173 0 : if (!build)
1174 0 : return NULL;
1175 :
1176 0 : space = isl_set_get_space(build->domain);
1177 0 : if (internal)
1178 0 : return space;
1179 :
1180 0 : if (!isl_ast_build_need_schedule_map(build))
1181 0 : return space;
1182 :
1183 0 : dim = isl_set_dim(build->domain, isl_dim_set);
1184 0 : space = isl_space_drop_dims(space, isl_dim_set,
1185 0 : build->depth, dim - build->depth);
1186 0 : for (i = build->depth - 1; i >= 0; --i) {
1187 0 : isl_bool affine = isl_ast_build_has_affine_value(build, i);
1188 :
1189 0 : if (affine < 0)
1190 0 : return isl_space_free(space);
1191 0 : if (affine)
1192 0 : space = isl_space_drop_dims(space, isl_dim_set, i, 1);
1193 : }
1194 :
1195 0 : return space;
1196 : }
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 0 : __isl_give isl_space *isl_ast_build_get_schedule_space(
1203 : __isl_keep isl_ast_build *build)
1204 : {
1205 : isl_space *space;
1206 : int i, skip;
1207 :
1208 0 : if (!build)
1209 0 : return NULL;
1210 :
1211 0 : space = isl_ast_build_get_space(build, 0);
1212 :
1213 0 : skip = 0;
1214 0 : for (i = 0; i < build->depth; ++i) {
1215 : isl_id *id;
1216 :
1217 0 : if (isl_ast_build_has_affine_value(build, i)) {
1218 0 : skip++;
1219 0 : continue;
1220 : }
1221 :
1222 0 : id = isl_ast_build_get_iterator_id(build, i);
1223 0 : space = isl_space_set_dim_id(space, isl_dim_set, i - skip, id);
1224 : }
1225 :
1226 0 : return space;
1227 : }
1228 :
1229 : /* Return the current schedule, as stored in build->executed, in terms
1230 : * of the external schedule domain.
1231 : */
1232 0 : __isl_give isl_union_map *isl_ast_build_get_schedule(
1233 : __isl_keep isl_ast_build *build)
1234 : {
1235 : isl_union_map *executed;
1236 : isl_union_map *schedule;
1237 :
1238 0 : if (!build)
1239 0 : return NULL;
1240 :
1241 0 : executed = isl_union_map_copy(build->executed);
1242 0 : if (isl_ast_build_need_schedule_map(build)) {
1243 0 : isl_map *proj = isl_ast_build_get_schedule_map(build);
1244 0 : executed = isl_union_map_apply_domain(executed,
1245 : isl_union_map_from_map(proj));
1246 : }
1247 0 : schedule = isl_union_map_reverse(executed);
1248 :
1249 0 : return schedule;
1250 : }
1251 :
1252 : /* Return the iterator attached to the internal schedule dimension "pos".
1253 : */
1254 0 : __isl_give isl_id *isl_ast_build_get_iterator_id(
1255 : __isl_keep isl_ast_build *build, int pos)
1256 : {
1257 0 : if (!build)
1258 0 : return NULL;
1259 :
1260 0 : return isl_id_list_get_id(build->iterators, pos);
1261 : }
1262 :
1263 : /* Set the stride and offset of the current dimension to the given
1264 : * value and expression.
1265 : */
1266 0 : 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 : {
1269 : int pos;
1270 :
1271 0 : build = isl_ast_build_cow(build);
1272 0 : if (!build || !stride || !offset)
1273 : goto error;
1274 :
1275 0 : pos = build->depth;
1276 :
1277 0 : build->strides = isl_vec_set_element_val(build->strides, pos, stride);
1278 0 : build->offsets = isl_multi_aff_set_aff(build->offsets, pos, offset);
1279 0 : if (!build->strides || !build->offsets)
1280 0 : return isl_ast_build_free(build);
1281 :
1282 0 : return build;
1283 : error:
1284 0 : isl_val_free(stride);
1285 0 : isl_aff_free(offset);
1286 0 : return isl_ast_build_free(build);
1287 : }
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 0 : __isl_give isl_set *isl_ast_build_get_stride_constraint(
1301 : __isl_keep isl_ast_build *build)
1302 : {
1303 : isl_aff *aff;
1304 : isl_set *set;
1305 : isl_val *stride;
1306 : int pos;
1307 :
1308 0 : if (!build)
1309 0 : return NULL;
1310 :
1311 0 : pos = build->depth;
1312 :
1313 0 : if (!isl_ast_build_has_stride(build, pos))
1314 0 : return isl_set_universe(isl_ast_build_get_space(build, 1));
1315 :
1316 0 : stride = isl_ast_build_get_stride(build, pos);
1317 0 : aff = isl_ast_build_get_offset(build, pos);
1318 0 : aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, -1);
1319 0 : aff = isl_aff_mod_val(aff, stride);
1320 0 : set = isl_set_from_basic_set(isl_aff_zero_basic_set(aff));
1321 :
1322 0 : return set;
1323 : }
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 0 : __isl_give isl_multi_aff *isl_ast_build_get_stride_expansion(
1337 : __isl_keep isl_ast_build *build)
1338 : {
1339 : isl_space *space;
1340 : isl_multi_aff *ma;
1341 : int pos;
1342 : isl_aff *aff, *offset;
1343 : isl_val *stride;
1344 :
1345 0 : if (!build)
1346 0 : return NULL;
1347 :
1348 0 : pos = isl_ast_build_get_depth(build);
1349 0 : space = isl_ast_build_get_space(build, 1);
1350 0 : space = isl_space_map_from_set(space);
1351 0 : ma = isl_multi_aff_identity(space);
1352 :
1353 0 : if (!isl_ast_build_has_stride(build, pos))
1354 0 : return ma;
1355 :
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 :
1363 0 : return ma;
1364 : }
1365 :
1366 : /* Add constraints corresponding to any previously detected
1367 : * stride on the current dimension to build->domain.
1368 : */
1369 0 : __isl_give isl_ast_build *isl_ast_build_include_stride(
1370 : __isl_take isl_ast_build *build)
1371 : {
1372 : isl_set *set;
1373 :
1374 0 : if (!build)
1375 0 : return NULL;
1376 0 : if (!isl_ast_build_has_stride(build, build->depth))
1377 0 : return build;
1378 0 : build = isl_ast_build_cow(build);
1379 0 : if (!build)
1380 0 : return NULL;
1381 :
1382 0 : set = isl_ast_build_get_stride_constraint(build);
1383 :
1384 0 : build->domain = isl_set_intersect(build->domain, isl_set_copy(set));
1385 0 : build->generated = isl_set_intersect(build->generated, set);
1386 0 : if (!build->domain || !build->generated)
1387 0 : return isl_ast_build_free(build);
1388 :
1389 0 : return build;
1390 : }
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 0 : __isl_give isl_ast_build *isl_ast_build_detect_strides(
1404 : __isl_take isl_ast_build *build, __isl_take isl_set *set)
1405 : {
1406 : int pos;
1407 : isl_bool no_stride;
1408 : isl_val *stride;
1409 : isl_aff *offset;
1410 : isl_stride_info *si;
1411 :
1412 0 : if (!build)
1413 0 : goto error;
1414 :
1415 0 : pos = isl_ast_build_get_depth(build);
1416 0 : si = isl_set_get_stride_info(set, pos);
1417 0 : stride = isl_stride_info_get_stride(si);
1418 0 : offset = isl_stride_info_get_offset(si);
1419 0 : isl_stride_info_free(si);
1420 0 : isl_set_free(set);
1421 :
1422 0 : no_stride = isl_val_is_one(stride);
1423 0 : if (no_stride >= 0 && !no_stride)
1424 0 : return set_stride(build, stride, offset);
1425 0 : isl_val_free(stride);
1426 0 : isl_aff_free(offset);
1427 0 : if (no_stride < 0)
1428 0 : return isl_ast_build_free(build);
1429 0 : return build;
1430 : error:
1431 0 : isl_set_free(set);
1432 0 : return NULL;
1433 : }
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 0 : static isl_stat involves_depth(__isl_take isl_map *map, void *user)
1443 : {
1444 0 : struct isl_ast_build_involves_data *data = user;
1445 :
1446 0 : data->involves = isl_map_involves_dims(map, isl_dim_in, data->depth, 1);
1447 0 : isl_map_free(map);
1448 :
1449 0 : if (data->involves < 0 || data->involves)
1450 0 : return isl_stat_error;
1451 0 : return isl_stat_ok;
1452 : }
1453 :
1454 : /* Do any options depend on the value of the dimension at the current depth?
1455 : */
1456 0 : int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build *build)
1457 : {
1458 : struct isl_ast_build_involves_data data;
1459 :
1460 0 : if (!build)
1461 0 : return -1;
1462 :
1463 0 : data.depth = build->depth;
1464 0 : data.involves = 0;
1465 :
1466 0 : if (isl_union_map_foreach_map(build->options,
1467 : &involves_depth, &data) < 0) {
1468 0 : if (data.involves < 0 || !data.involves)
1469 0 : return -1;
1470 : }
1471 :
1472 0 : return data.involves;
1473 : }
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 0 : static __isl_give isl_map *construct_insertion_map(__isl_take isl_space *space,
1482 : int pos)
1483 : {
1484 : isl_constraint *c;
1485 : isl_basic_map *bmap1, *bmap2;
1486 :
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 :
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 :
1500 0 : return isl_basic_map_union(bmap1, bmap2);
1501 : }
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 0 : static __isl_give isl_union_map *options_insert_dim(
1531 : __isl_take isl_union_map *options, __isl_take isl_space *space, int pos)
1532 : {
1533 : isl_map *map;
1534 : isl_union_map *insertion;
1535 : enum isl_ast_loop_type type;
1536 0 : const char *name = "separation_class";
1537 :
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 : isl_union_map_from_map(map));
1543 :
1544 0 : if (!options)
1545 0 : return NULL;
1546 :
1547 0 : map = construct_insertion_map(isl_union_map_get_space(options), pos);
1548 :
1549 0 : insertion = isl_union_map_empty(isl_union_map_get_space(options));
1550 :
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 : }
1559 :
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 :
1565 0 : options = isl_union_map_apply_range(options, insertion);
1566 :
1567 0 : return options;
1568 : }
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 0 : static __isl_give isl_ast_build *node_insert_dim(
1578 : __isl_take isl_ast_build *build, int pos)
1579 : {
1580 : int i;
1581 : int local_pos;
1582 : enum isl_ast_loop_type *loop_type;
1583 : isl_ctx *ctx;
1584 :
1585 0 : build = isl_ast_build_cow(build);
1586 0 : if (!build)
1587 0 : return NULL;
1588 0 : if (!build->node)
1589 0 : return build;
1590 :
1591 0 : ctx = isl_ast_build_get_ctx(build);
1592 0 : local_pos = pos - build->outer_pos;
1593 0 : loop_type = isl_realloc_array(ctx, build->loop_type,
1594 : enum isl_ast_loop_type, build->n + 1);
1595 0 : if (!loop_type)
1596 0 : return isl_ast_build_free(build);
1597 0 : build->loop_type = loop_type;
1598 0 : for (i = build->n - 1; i >= local_pos; --i)
1599 0 : loop_type[i + 1] = loop_type[i];
1600 0 : loop_type[local_pos] = isl_ast_loop_default;
1601 0 : build->n++;
1602 :
1603 0 : return build;
1604 : }
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 0 : __isl_give isl_ast_build *isl_ast_build_insert_dim(
1625 : __isl_take isl_ast_build *build, int pos)
1626 : {
1627 : isl_ctx *ctx;
1628 : isl_space *space, *ma_space;
1629 : isl_id *id;
1630 : isl_multi_aff *ma;
1631 :
1632 0 : build = isl_ast_build_cow(build);
1633 0 : if (!build)
1634 0 : return NULL;
1635 :
1636 0 : ctx = isl_ast_build_get_ctx(build);
1637 0 : id = isl_id_alloc(ctx, "", NULL);
1638 0 : if (!build->node)
1639 0 : space = isl_ast_build_get_space(build, 1);
1640 0 : build->iterators = isl_id_list_insert(build->iterators, pos, id);
1641 0 : build->domain = isl_set_insert_dims(build->domain,
1642 : isl_dim_set, pos, 1);
1643 0 : build->generated = isl_set_insert_dims(build->generated,
1644 : isl_dim_set, pos, 1);
1645 0 : build->pending = isl_set_insert_dims(build->pending,
1646 : isl_dim_set, pos, 1);
1647 0 : build->strides = isl_vec_insert_els(build->strides, pos, 1);
1648 0 : build->strides = isl_vec_set_element_si(build->strides, pos, 1);
1649 0 : ma_space = isl_space_params(isl_multi_aff_get_space(build->offsets));
1650 0 : ma_space = isl_space_set_from_params(ma_space);
1651 0 : ma_space = isl_space_add_dims(ma_space, isl_dim_set, 1);
1652 0 : ma_space = isl_space_map_from_set(ma_space);
1653 0 : ma = isl_multi_aff_zero(isl_space_copy(ma_space));
1654 0 : build->offsets = isl_multi_aff_splice(build->offsets, pos, pos, ma);
1655 0 : ma = isl_multi_aff_identity(ma_space);
1656 0 : build->values = isl_multi_aff_splice(build->values, pos, pos, ma);
1657 0 : if (!build->node)
1658 0 : build->options = options_insert_dim(build->options, space, pos);
1659 0 : build->internal2input = isl_multi_aff_free(build->internal2input);
1660 :
1661 0 : if (!build->iterators || !build->domain || !build->generated ||
1662 0 : !build->pending || !build->values ||
1663 0 : !build->strides || !build->offsets || !build->options)
1664 0 : return isl_ast_build_free(build);
1665 :
1666 0 : build = node_insert_dim(build, pos);
1667 :
1668 0 : return build;
1669 : }
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 0 : __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 : {
1690 : isl_aff *aff;
1691 : isl_val *v;
1692 : int depth;
1693 :
1694 0 : build = isl_ast_build_cow(build);
1695 0 : if (!build || !umap || !m)
1696 : goto error;
1697 :
1698 0 : depth = build->depth;
1699 :
1700 0 : if (build->internal2input) {
1701 : isl_space *space;
1702 : isl_multi_aff *ma;
1703 : isl_aff *aff;
1704 :
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 : }
1716 :
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 :
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 :
1728 0 : return build;
1729 : error:
1730 0 : isl_val_free(m);
1731 0 : isl_union_map_free(umap);
1732 0 : return isl_ast_build_free(build);
1733 : }
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 0 : static __isl_give isl_id_list *generate_names(isl_ctx *ctx, int n, int first,
1740 : __isl_keep isl_ast_build *build)
1741 : {
1742 : int i;
1743 : isl_id_list *names;
1744 :
1745 0 : names = isl_id_list_alloc(ctx, n);
1746 0 : for (i = 0; i < n; ++i) {
1747 : isl_id *id;
1748 :
1749 0 : id = generate_name(ctx, first + i, build);
1750 0 : names = isl_id_list_add(names, id);
1751 : }
1752 :
1753 0 : return names;
1754 : }
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 0 : static __isl_give isl_union_map *embed_options(
1781 : __isl_take isl_union_map *options, __isl_take isl_space *space)
1782 : {
1783 : isl_map *map;
1784 :
1785 0 : map = isl_map_universe(isl_space_unwrap(space));
1786 0 : map = isl_map_range_map(map);
1787 :
1788 0 : options = isl_union_map_apply_range(
1789 : isl_union_map_from_map(map), options);
1790 :
1791 0 : return options;
1792 : }
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 0 : __isl_give isl_ast_build *isl_ast_build_product(
1817 : __isl_take isl_ast_build *build, __isl_take isl_space *space)
1818 : {
1819 : isl_ctx *ctx;
1820 : isl_vec *strides;
1821 : isl_set *set;
1822 : isl_multi_aff *embedding;
1823 : int dim, n_it;
1824 :
1825 0 : build = isl_ast_build_cow(build);
1826 0 : if (!build)
1827 0 : goto error;
1828 :
1829 0 : build->outer_pos = build->depth;
1830 :
1831 0 : ctx = isl_ast_build_get_ctx(build);
1832 0 : dim = isl_set_dim(build->domain, isl_dim_set);
1833 0 : dim += isl_space_dim(space, isl_dim_set);
1834 0 : n_it = isl_id_list_n_id(build->iterators);
1835 0 : if (n_it < dim) {
1836 : isl_id_list *l;
1837 0 : l = generate_names(ctx, dim - n_it, n_it, build);
1838 0 : build->iterators = isl_id_list_concat(build->iterators, l);
1839 : }
1840 :
1841 0 : if (isl_set_is_params(build->domain))
1842 0 : return isl_ast_build_init(build, space);
1843 :
1844 0 : set = isl_set_universe(isl_space_copy(space));
1845 0 : build->domain = isl_set_product(build->domain, isl_set_copy(set));
1846 0 : build->pending = isl_set_product(build->pending, isl_set_copy(set));
1847 0 : build->generated = isl_set_product(build->generated, set);
1848 :
1849 0 : strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set));
1850 0 : strides = isl_vec_set_si(strides, 1);
1851 0 : build->strides = isl_vec_concat(build->strides, strides);
1852 :
1853 0 : space = isl_space_map_from_set(space);
1854 0 : build->offsets = isl_multi_aff_align_params(build->offsets,
1855 : isl_space_copy(space));
1856 0 : build->offsets = isl_multi_aff_product(build->offsets,
1857 : isl_multi_aff_zero(isl_space_copy(space)));
1858 0 : build->values = isl_multi_aff_align_params(build->values,
1859 : isl_space_copy(space));
1860 0 : embedding = isl_multi_aff_identity(space);
1861 0 : build->values = isl_multi_aff_product(build->values,
1862 : isl_multi_aff_copy(embedding));
1863 0 : if (build->internal2input) {
1864 0 : build->internal2input =
1865 0 : isl_multi_aff_product(build->internal2input, embedding);
1866 0 : build->internal2input =
1867 0 : isl_multi_aff_flatten_range(build->internal2input);
1868 0 : if (!build->internal2input)
1869 0 : return isl_ast_build_free(build);
1870 : } else {
1871 0 : isl_multi_aff_free(embedding);
1872 : }
1873 :
1874 0 : space = isl_ast_build_get_space(build, 1);
1875 0 : build->options = embed_options(build->options, space);
1876 :
1877 0 : if (!build->iterators || !build->domain || !build->generated ||
1878 0 : !build->pending || !build->values ||
1879 0 : !build->strides || !build->offsets || !build->options)
1880 0 : return isl_ast_build_free(build);
1881 :
1882 0 : return build;
1883 : error:
1884 0 : isl_ast_build_free(build);
1885 0 : isl_space_free(space);
1886 0 : return NULL;
1887 : }
1888 :
1889 : /* Does "aff" only attain non-negative values over build->domain?
1890 : * That is, does it not attain any negative values?
1891 : */
1892 0 : int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build,
1893 : __isl_keep isl_aff *aff)
1894 : {
1895 : isl_set *test;
1896 : int empty;
1897 :
1898 0 : if (!build)
1899 0 : return -1;
1900 :
1901 0 : aff = isl_aff_copy(aff);
1902 0 : test = isl_set_from_basic_set(isl_aff_neg_basic_set(aff));
1903 0 : test = isl_set_intersect(test, isl_set_copy(build->domain));
1904 0 : empty = isl_set_is_empty(test);
1905 0 : isl_set_free(test);
1906 :
1907 0 : return empty;
1908 : }
1909 :
1910 : /* Does the dimension at (internal) position "pos" have a non-trivial stride?
1911 : */
1912 0 : isl_bool isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos)
1913 : {
1914 : isl_val *v;
1915 : isl_bool has_stride;
1916 :
1917 0 : if (!build)
1918 0 : return isl_bool_error;
1919 :
1920 0 : v = isl_vec_get_element_val(build->strides, pos);
1921 0 : has_stride = isl_bool_not(isl_val_is_one(v));
1922 0 : isl_val_free(v);
1923 :
1924 0 : return has_stride;
1925 : }
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 0 : __isl_give isl_val *isl_ast_build_get_stride(__isl_keep isl_ast_build *build,
1934 : int pos)
1935 : {
1936 0 : if (!build)
1937 0 : return NULL;
1938 :
1939 0 : return isl_vec_get_element_val(build->strides, pos);
1940 : }
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 0 : __isl_give isl_aff *isl_ast_build_get_offset(
1949 : __isl_keep isl_ast_build *build, int pos)
1950 : {
1951 0 : if (!build)
1952 0 : return NULL;
1953 :
1954 0 : return isl_multi_aff_get_aff(build->offsets, pos);
1955 : }
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 0 : isl_bool isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build,
1967 : int pos)
1968 : {
1969 : isl_aff *aff;
1970 : isl_bool involves;
1971 :
1972 0 : if (!build)
1973 0 : return isl_bool_error;
1974 :
1975 0 : aff = isl_multi_aff_get_aff(build->values, pos);
1976 0 : involves = isl_aff_involves_dims(aff, isl_dim_in, pos, 1);
1977 0 : isl_aff_free(aff);
1978 :
1979 0 : return isl_bool_not(involves);
1980 : }
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 0 : __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 : {
1991 : isl_multi_aff *values;
1992 :
1993 0 : if (!build)
1994 0 : return isl_union_map_free(umap);
1995 :
1996 0 : values = isl_multi_aff_copy(build->values);
1997 0 : umap = isl_union_map_preimage_domain_multi_aff(umap, values);
1998 :
1999 0 : return umap;
2000 : }
2001 :
2002 : /* Is the current dimension known to attain only a single value?
2003 : */
2004 0 : int isl_ast_build_has_value(__isl_keep isl_ast_build *build)
2005 : {
2006 0 : if (!build)
2007 0 : return -1;
2008 :
2009 0 : return build->value != NULL;
2010 : }
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 0 : __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 : {
2020 0 : if (!build)
2021 0 : goto error;
2022 :
2023 0 : bset = isl_basic_set_preimage_multi_aff(bset,
2024 : isl_multi_aff_copy(build->values));
2025 0 : bset = isl_basic_set_gist(bset,
2026 : isl_set_simple_hull(isl_set_copy(build->domain)));
2027 :
2028 0 : return bset;
2029 : error:
2030 0 : isl_basic_set_free(bset);
2031 0 : return NULL;
2032 : }
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 0 : __isl_give isl_set *isl_ast_build_compute_gist(
2040 : __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2041 : {
2042 0 : if (!build)
2043 0 : goto error;
2044 :
2045 0 : if (!isl_set_is_params(set))
2046 0 : set = isl_set_preimage_multi_aff(set,
2047 : isl_multi_aff_copy(build->values));
2048 0 : set = isl_set_gist(set, isl_set_copy(build->domain));
2049 :
2050 0 : return set;
2051 : error:
2052 0 : isl_set_free(set);
2053 0 : return NULL;
2054 : }
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 0 : __isl_give isl_set *isl_ast_build_specialize(__isl_keep isl_ast_build *build,
2065 : __isl_take isl_set *set)
2066 : {
2067 0 : if (!build)
2068 0 : return isl_set_free(set);
2069 :
2070 0 : return isl_set_preimage_multi_aff(set,
2071 : isl_multi_aff_copy(build->values));
2072 : }
2073 :
2074 : /* Plug in the known affine values of outer loop iterators in "bset".
2075 : */
2076 0 : __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 : {
2079 0 : if (!build)
2080 0 : return isl_basic_set_free(bset);
2081 :
2082 0 : return isl_basic_set_preimage_multi_aff(bset,
2083 : isl_multi_aff_copy(build->values));
2084 : }
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 0 : __isl_give isl_map *isl_ast_build_compute_gist_map_domain(
2092 : __isl_keep isl_ast_build *build, __isl_take isl_map *map)
2093 : {
2094 0 : if (!build)
2095 0 : goto error;
2096 :
2097 0 : map = isl_map_gist_domain(map, isl_set_copy(build->domain));
2098 :
2099 0 : return map;
2100 : error:
2101 0 : isl_map_free(map);
2102 0 : return NULL;
2103 : }
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 0 : __isl_give isl_aff *isl_ast_build_compute_gist_aff(
2111 : __isl_keep isl_ast_build *build, __isl_take isl_aff *aff)
2112 : {
2113 0 : if (!build)
2114 0 : goto error;
2115 :
2116 0 : aff = isl_aff_gist(aff, isl_set_copy(build->domain));
2117 :
2118 0 : return aff;
2119 : error:
2120 0 : isl_aff_free(aff);
2121 0 : return NULL;
2122 : }
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 0 : __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 : {
2132 0 : if (!build)
2133 0 : goto error;
2134 :
2135 0 : if (!isl_set_is_params(build->domain))
2136 0 : pa = isl_pw_aff_pullback_multi_aff(pa,
2137 : isl_multi_aff_copy(build->values));
2138 0 : pa = isl_pw_aff_gist(pa, isl_set_copy(build->domain));
2139 :
2140 0 : return pa;
2141 : error:
2142 0 : isl_pw_aff_free(pa);
2143 0 : return NULL;
2144 : }
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 0 : __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 : {
2154 0 : if (!build)
2155 0 : goto error;
2156 :
2157 0 : pma = isl_pw_multi_aff_pullback_multi_aff(pma,
2158 : isl_multi_aff_copy(build->values));
2159 0 : pma = isl_pw_multi_aff_gist(pma, isl_set_copy(build->domain));
2160 :
2161 0 : return pma;
2162 : error:
2163 0 : isl_pw_multi_aff_free(pma);
2164 0 : return NULL;
2165 : }
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 0 : __isl_give isl_set *isl_ast_build_get_option_domain(
2183 : __isl_keep isl_ast_build *build, enum isl_ast_loop_type type)
2184 : {
2185 : const char *name;
2186 : isl_space *space;
2187 : isl_map *option;
2188 : isl_set *domain;
2189 : int local_pos;
2190 :
2191 0 : if (!build)
2192 0 : return NULL;
2193 :
2194 0 : name = option_str[type];
2195 0 : local_pos = build->depth - build->outer_pos;
2196 :
2197 0 : space = isl_ast_build_get_space(build, 1);
2198 0 : space = isl_space_from_domain(space);
2199 0 : space = isl_space_add_dims(space, isl_dim_out, 1);
2200 0 : space = isl_space_set_tuple_name(space, isl_dim_out, name);
2201 :
2202 0 : option = isl_union_map_extract_map(build->options, space);
2203 0 : option = isl_map_fix_si(option, isl_dim_out, 0, local_pos);
2204 :
2205 0 : domain = isl_map_domain(option);
2206 0 : domain = isl_ast_build_eliminate(build, domain);
2207 :
2208 0 : return domain;
2209 : }
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 0 : enum isl_ast_loop_type isl_ast_build_get_loop_type(
2223 : __isl_keep isl_ast_build *build, int isolated)
2224 : {
2225 : int local_pos;
2226 : isl_ctx *ctx;
2227 :
2228 0 : if (!build)
2229 0 : return isl_ast_loop_error;
2230 0 : ctx = isl_ast_build_get_ctx(build);
2231 0 : if (!build->node)
2232 0 : isl_die(ctx, isl_error_internal,
2233 : "only works for schedule tree based AST generation",
2234 : return isl_ast_loop_error);
2235 :
2236 0 : local_pos = build->depth - build->outer_pos;
2237 0 : if (!isolated)
2238 0 : return build->loop_type[local_pos];
2239 0 : return isl_schedule_node_band_member_get_isolate_ast_loop_type(
2240 : build->node, local_pos);
2241 : }
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 0 : __isl_give isl_ast_build *isl_ast_build_extract_isolated(
2261 : __isl_take isl_ast_build *build)
2262 : {
2263 : isl_set *isolated;
2264 :
2265 0 : if (!build)
2266 0 : return NULL;
2267 0 : if (!build->internal2input)
2268 0 : return build;
2269 0 : if (build->isolated)
2270 0 : return build;
2271 :
2272 0 : build = isl_ast_build_cow(build);
2273 0 : if (!build)
2274 0 : return NULL;
2275 :
2276 0 : isolated = isl_schedule_node_band_get_ast_isolate_option(build->node);
2277 0 : isolated = isl_set_flatten(isolated);
2278 0 : isolated = isl_set_preimage_multi_aff(isolated,
2279 : isl_multi_aff_copy(build->internal2input));
2280 :
2281 0 : build->isolated = isolated;
2282 0 : if (!build->isolated)
2283 0 : return isl_ast_build_free(build);
2284 :
2285 0 : return build;
2286 : }
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 0 : int isl_ast_build_has_isolated(__isl_keep isl_ast_build *build)
2293 : {
2294 : int empty;
2295 :
2296 0 : if (!build)
2297 0 : return -1;
2298 0 : if (!build->internal2input)
2299 0 : return 0;
2300 0 : if (!build->isolated)
2301 0 : isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
2302 : "isolated set not extracted yet", return -1);
2303 :
2304 0 : empty = isl_set_plain_is_empty(build->isolated);
2305 0 : return empty < 0 ? -1 : !empty;
2306 : }
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 0 : __isl_give isl_set *isl_ast_build_get_isolated(__isl_keep isl_ast_build *build)
2317 : {
2318 0 : if (!build)
2319 0 : return NULL;
2320 0 : if (!build->internal2input)
2321 0 : isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
2322 : "build cannot have isolated set", return NULL);
2323 :
2324 0 : return isl_set_copy(build->isolated);
2325 : }
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 0 : __isl_give isl_map *isl_ast_build_get_separation_class(
2341 : __isl_keep isl_ast_build *build)
2342 : {
2343 : isl_ctx *ctx;
2344 : isl_space *space_sep, *space;
2345 : isl_map *res;
2346 : int local_pos;
2347 :
2348 0 : if (!build)
2349 0 : return NULL;
2350 :
2351 0 : local_pos = build->depth - build->outer_pos;
2352 0 : ctx = isl_ast_build_get_ctx(build);
2353 0 : space_sep = isl_space_alloc(ctx, 0, 1, 1);
2354 0 : space_sep = isl_space_wrap(space_sep);
2355 0 : space_sep = isl_space_set_tuple_name(space_sep, isl_dim_set,
2356 : "separation_class");
2357 0 : space = isl_ast_build_get_space(build, 1);
2358 0 : space_sep = isl_space_align_params(space_sep, isl_space_copy(space));
2359 0 : space = isl_space_map_from_domain_and_range(space, space_sep);
2360 :
2361 0 : res = isl_union_map_extract_map(build->options, space);
2362 0 : res = isl_map_fix_si(res, isl_dim_out, 0, local_pos);
2363 0 : res = isl_map_coalesce(res);
2364 :
2365 0 : return res;
2366 : }
2367 :
2368 : /* Eliminate dimensions inner to the current dimension.
2369 : */
2370 0 : __isl_give isl_set *isl_ast_build_eliminate_inner(
2371 : __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2372 : {
2373 : int dim;
2374 : int depth;
2375 :
2376 0 : if (!build)
2377 0 : return isl_set_free(set);
2378 :
2379 0 : dim = isl_set_dim(set, isl_dim_set);
2380 0 : depth = build->depth;
2381 0 : set = isl_set_detect_equalities(set);
2382 0 : set = isl_set_eliminate(set, isl_dim_set, depth + 1, dim - (depth + 1));
2383 :
2384 0 : return set;
2385 : }
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 0 : __isl_give isl_set *isl_ast_build_eliminate_divs(
2395 : __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2396 : {
2397 : int depth;
2398 :
2399 0 : if (!build)
2400 0 : return isl_set_free(set);
2401 :
2402 0 : set = isl_set_remove_unknown_divs(set);
2403 0 : depth = build->depth;
2404 0 : set = isl_set_remove_divs_involving_dims(set, isl_dim_set, depth, 1);
2405 :
2406 0 : return set;
2407 : }
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 0 : __isl_give isl_set *isl_ast_build_eliminate(
2416 : __isl_keep isl_ast_build *build, __isl_take isl_set *domain)
2417 : {
2418 0 : domain = isl_ast_build_eliminate_inner(build, domain);
2419 0 : domain = isl_ast_build_eliminate_divs(build, domain);
2420 0 : return domain;
2421 : }
2422 :
2423 : /* Replace build->single_valued by "sv".
2424 : */
2425 0 : __isl_give isl_ast_build *isl_ast_build_set_single_valued(
2426 : __isl_take isl_ast_build *build, int sv)
2427 : {
2428 0 : if (!build)
2429 0 : return build;
2430 0 : if (build->single_valued == sv)
2431 0 : return build;
2432 0 : build = isl_ast_build_cow(build);
2433 0 : if (!build)
2434 0 : return build;
2435 0 : build->single_valued = sv;
2436 :
2437 0 : return build;
2438 : }
|
