1/*
2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2014 Ecole Normale Superieure
4 *
5 * Use of this software is governed by the MIT license
6 *
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9 * 91893 Orsay, France
10 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
11 */
12
13#include <isl_ctx_private.h>
14#include <isl/id.h>
15#include <isl_map_private.h>
16#include <isl_local_space_private.h>
17#include <isl_space_private.h>
18#include <isl_mat_private.h>
19#include <isl_aff_private.h>
20#include <isl_vec_private.h>
21#include <isl_point_private.h>
22#include <isl_seq.h>
23#include <isl_local.h>
24
25isl_ctx *isl_local_space_get_ctx(__isl_keep isl_local_space *ls)
26{
27 return ls ? ls->dim->ctx : NULL;
28}
29
30/* Return a hash value that digests "ls".
31 */
32uint32_t isl_local_space_get_hash(__isl_keep isl_local_space *ls)
33{
34 uint32_t hash, space_hash, div_hash;
35
36 if (!ls)
37 return 0;
38
39 hash = isl_hash_init();
40 space_hash = isl_space_get_full_hash(space: isl_local_space_peek_space(ls));
41 isl_hash_hash(hash, space_hash);
42 div_hash = isl_mat_get_hash(mat: ls->div);
43 isl_hash_hash(hash, div_hash);
44
45 return hash;
46}
47
48__isl_give isl_local_space *isl_local_space_alloc_div(
49 __isl_take isl_space *space, __isl_take isl_mat *div)
50{
51 isl_ctx *ctx;
52 isl_local_space *ls = NULL;
53
54 if (!space || !div)
55 goto error;
56
57 ctx = isl_space_get_ctx(space);
58 ls = isl_calloc_type(ctx, struct isl_local_space);
59 if (!ls)
60 goto error;
61
62 ls->ref = 1;
63 ls->dim = space;
64 ls->div = div;
65
66 return ls;
67error:
68 isl_mat_free(mat: div);
69 isl_space_free(space);
70 isl_local_space_free(ls);
71 return NULL;
72}
73
74__isl_give isl_local_space *isl_local_space_alloc(__isl_take isl_space *space,
75 unsigned n_div)
76{
77 isl_ctx *ctx;
78 isl_mat *div;
79 isl_size total;
80
81 if (!space)
82 return NULL;
83
84 total = isl_space_dim(space, type: isl_dim_all);
85 if (total < 0)
86 return isl_local_space_from_space(space: isl_space_free(space));
87
88 ctx = isl_space_get_ctx(space);
89 div = isl_mat_alloc(ctx, n_row: n_div, n_col: 1 + 1 + total + n_div);
90 return isl_local_space_alloc_div(space, div);
91}
92
93__isl_give isl_local_space *isl_local_space_from_space(
94 __isl_take isl_space *space)
95{
96 return isl_local_space_alloc(space, n_div: 0);
97}
98
99__isl_give isl_local_space *isl_local_space_copy(__isl_keep isl_local_space *ls)
100{
101 if (!ls)
102 return NULL;
103
104 ls->ref++;
105 return ls;
106}
107
108__isl_give isl_local_space *isl_local_space_dup(__isl_keep isl_local_space *ls)
109{
110 if (!ls)
111 return NULL;
112
113 return isl_local_space_alloc_div(space: isl_space_copy(space: ls->dim),
114 div: isl_mat_copy(mat: ls->div));
115
116}
117
118__isl_give isl_local_space *isl_local_space_cow(__isl_take isl_local_space *ls)
119{
120 if (!ls)
121 return NULL;
122
123 if (ls->ref == 1)
124 return ls;
125 ls->ref--;
126 return isl_local_space_dup(ls);
127}
128
129__isl_null isl_local_space *isl_local_space_free(
130 __isl_take isl_local_space *ls)
131{
132 if (!ls)
133 return NULL;
134
135 if (--ls->ref > 0)
136 return NULL;
137
138 isl_space_free(space: ls->dim);
139 isl_mat_free(mat: ls->div);
140
141 free(ptr: ls);
142
143 return NULL;
144}
145
146/* Is the local space that of a parameter domain?
147 */
148isl_bool isl_local_space_is_params(__isl_keep isl_local_space *ls)
149{
150 if (!ls)
151 return isl_bool_error;
152 return isl_space_is_params(space: ls->dim);
153}
154
155/* Is the local space that of a set?
156 */
157isl_bool isl_local_space_is_set(__isl_keep isl_local_space *ls)
158{
159 return ls ? isl_space_is_set(space: ls->dim) : isl_bool_error;
160}
161
162#undef TYPE
163#define TYPE isl_local_space
164
165#include "isl_type_has_equal_space_bin_templ.c"
166#include "isl_type_has_space_templ.c"
167
168/* Check that the space of "ls" is equal to "space".
169 */
170static isl_stat isl_local_space_check_has_space(__isl_keep isl_local_space *ls,
171 __isl_keep isl_space *space)
172{
173 isl_bool ok;
174
175 ok = isl_local_space_has_space(obj: ls, space);
176 if (ok < 0)
177 return isl_stat_error;
178 if (!ok)
179 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
180 "spaces don't match", return isl_stat_error);
181 return isl_stat_ok;
182}
183
184/* Return true if the two local spaces are identical, with identical
185 * expressions for the integer divisions.
186 */
187isl_bool isl_local_space_is_equal(__isl_keep isl_local_space *ls1,
188 __isl_keep isl_local_space *ls2)
189{
190 isl_bool equal;
191
192 equal = isl_local_space_has_equal_space(obj1: ls1, obj2: ls2);
193 if (equal < 0 || !equal)
194 return equal;
195
196 if (!isl_local_space_divs_known(ls: ls1))
197 return isl_bool_false;
198 if (!isl_local_space_divs_known(ls: ls2))
199 return isl_bool_false;
200
201 return isl_mat_is_equal(mat1: ls1->div, mat2: ls2->div);
202}
203
204/* Compare two isl_local_spaces.
205 *
206 * Return -1 if "ls1" is "smaller" than "ls2", 1 if "ls1" is "greater"
207 * than "ls2" and 0 if they are equal.
208 */
209int isl_local_space_cmp(__isl_keep isl_local_space *ls1,
210 __isl_keep isl_local_space *ls2)
211{
212 int cmp;
213
214 if (ls1 == ls2)
215 return 0;
216 if (!ls1)
217 return -1;
218 if (!ls2)
219 return 1;
220
221 cmp = isl_space_cmp(space1: ls1->dim, space2: ls2->dim);
222 if (cmp != 0)
223 return cmp;
224
225 return isl_local_cmp(local1: ls1->div, local2: ls2->div);
226}
227
228isl_size isl_local_space_dim(__isl_keep isl_local_space *ls,
229 enum isl_dim_type type)
230{
231 if (!ls)
232 return isl_size_error;
233 if (type == isl_dim_div)
234 return ls->div->n_row;
235 if (type == isl_dim_all) {
236 isl_size dim = isl_space_dim(space: ls->dim, type: isl_dim_all);
237 if (dim < 0)
238 return isl_size_error;
239 return dim + ls->div->n_row;
240 }
241 return isl_space_dim(space: ls->dim, type);
242}
243
244#undef TYPE
245#define TYPE isl_local_space
246#include "check_type_range_templ.c"
247
248/* Return the position of the variables of the given type
249 * within the sequence of variables of "ls".
250 */
251isl_size isl_local_space_var_offset(__isl_keep isl_local_space *ls,
252 enum isl_dim_type type)
253{
254 isl_space *space;
255
256 space = isl_local_space_peek_space(ls);
257 if (space < 0)
258 return isl_size_error;
259 switch (type) {
260 case isl_dim_param:
261 case isl_dim_in:
262 case isl_dim_out: return isl_space_offset(space, type);
263 case isl_dim_div: return isl_space_dim(space, type: isl_dim_all);
264 case isl_dim_cst:
265 default:
266 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
267 "invalid dimension type", return isl_size_error);
268 }
269}
270
271/* Return the position of the coefficients of the variables of the given type
272 * within the sequence of coefficients of "ls".
273 */
274unsigned isl_local_space_offset(__isl_keep isl_local_space *ls,
275 enum isl_dim_type type)
276{
277 if (!ls)
278 return 0;
279
280 switch (type) {
281 case isl_dim_cst: return 0;
282 case isl_dim_param:
283 case isl_dim_in:
284 case isl_dim_out:
285 case isl_dim_div: return 1 + isl_local_space_var_offset(ls, type);
286 default: return 0;
287 }
288}
289
290/* Return the position of the dimension of the given type and name
291 * in "ls".
292 * Return -1 if no such dimension can be found.
293 */
294int isl_local_space_find_dim_by_name(__isl_keep isl_local_space *ls,
295 enum isl_dim_type type, const char *name)
296{
297 if (!ls)
298 return -1;
299 if (type == isl_dim_div)
300 return -1;
301 return isl_space_find_dim_by_name(space: ls->dim, type, name);
302}
303
304/* Does the given dimension have a name?
305 */
306isl_bool isl_local_space_has_dim_name(__isl_keep isl_local_space *ls,
307 enum isl_dim_type type, unsigned pos)
308{
309 return ls ? isl_space_has_dim_name(space: ls->dim, type, pos) : isl_bool_error;
310}
311
312const char *isl_local_space_get_dim_name(__isl_keep isl_local_space *ls,
313 enum isl_dim_type type, unsigned pos)
314{
315 return ls ? isl_space_get_dim_name(space: ls->dim, type, pos) : NULL;
316}
317
318isl_bool isl_local_space_has_dim_id(__isl_keep isl_local_space *ls,
319 enum isl_dim_type type, unsigned pos)
320{
321 return ls ? isl_space_has_dim_id(space: ls->dim, type, pos) : isl_bool_error;
322}
323
324__isl_give isl_id *isl_local_space_get_dim_id(__isl_keep isl_local_space *ls,
325 enum isl_dim_type type, unsigned pos)
326{
327 return ls ? isl_space_get_dim_id(space: ls->dim, type, pos) : NULL;
328}
329
330/* Return the argument of the integer division at position "pos" in "ls".
331 * All local variables in "ls" are known to have a (complete) explicit
332 * representation.
333 */
334static __isl_give isl_aff *extract_div(__isl_keep isl_local_space *ls, int pos)
335{
336 isl_aff *aff;
337
338 aff = isl_aff_alloc(ls: isl_local_space_copy(ls));
339 if (!aff)
340 return NULL;
341 isl_seq_cpy(dst: aff->v->el, src: ls->div->row[pos], len: aff->v->size);
342 return aff;
343}
344
345/* Return the argument of the integer division at position "pos" in "ls".
346 * The integer division at that position is known to have a complete
347 * explicit representation, but some of the others do not.
348 * Remove them first because the domain of an isl_aff
349 * is not allowed to have unknown local variables.
350 */
351static __isl_give isl_aff *drop_unknown_divs_and_extract_div(
352 __isl_keep isl_local_space *ls, int pos)
353{
354 int i;
355 isl_size n;
356 isl_bool unknown;
357 isl_aff *aff;
358
359 n = isl_local_space_dim(ls, type: isl_dim_div);
360 if (n < 0)
361 return NULL;
362 ls = isl_local_space_copy(ls);
363 for (i = n - 1; i >= 0; --i) {
364 unknown = isl_local_space_div_is_marked_unknown(ls, div: i);
365 if (unknown < 0)
366 ls = isl_local_space_free(ls);
367 else if (!unknown)
368 continue;
369 ls = isl_local_space_drop_dims(ls, type: isl_dim_div, first: i, n: 1);
370 if (pos > i)
371 --pos;
372 }
373 aff = extract_div(ls, pos);
374 isl_local_space_free(ls);
375 return aff;
376}
377
378/* Return the argument of the integer division at position "pos" in "ls".
379 * The integer division is assumed to have a complete explicit
380 * representation. If some of the other integer divisions
381 * do not have an explicit representation, then they need
382 * to be removed first because the domain of an isl_aff
383 * is not allowed to have unknown local variables.
384 */
385__isl_give isl_aff *isl_local_space_get_div(__isl_keep isl_local_space *ls,
386 int pos)
387{
388 isl_bool known;
389
390 if (!ls)
391 return NULL;
392
393 if (pos < 0 || pos >= ls->div->n_row)
394 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
395 "index out of bounds", return NULL);
396
397 known = isl_local_space_div_is_known(ls, div: pos);
398 if (known < 0)
399 return NULL;
400 if (!known)
401 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
402 "expression of div unknown", return NULL);
403 if (!isl_local_space_is_set(ls))
404 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
405 "cannot represent divs of map spaces", return NULL);
406
407 known = isl_local_space_divs_known(ls);
408 if (known < 0)
409 return NULL;
410 if (known)
411 return extract_div(ls, pos);
412 else
413 return drop_unknown_divs_and_extract_div(ls, pos);
414}
415
416/* Return the space of "ls".
417 */
418__isl_keep isl_space *isl_local_space_peek_space(__isl_keep isl_local_space *ls)
419{
420 if (!ls)
421 return NULL;
422
423 return ls->dim;
424}
425
426__isl_give isl_space *isl_local_space_get_space(__isl_keep isl_local_space *ls)
427{
428 return isl_space_copy(space: isl_local_space_peek_space(ls));
429}
430
431/* Return the space of "ls".
432 * This may be either a copy or the space itself
433 * if there is only one reference to "ls".
434 * This allows the space to be modified inplace
435 * if both the local space and its space have only a single reference.
436 * The caller is not allowed to modify "ls" between this call and
437 * a subsequent call to isl_local_space_restore_space.
438 * The only exception is that isl_local_space_free can be called instead.
439 */
440__isl_give isl_space *isl_local_space_take_space(__isl_keep isl_local_space *ls)
441{
442 isl_space *space;
443
444 if (!ls)
445 return NULL;
446 if (ls->ref != 1)
447 return isl_local_space_get_space(ls);
448 space = ls->dim;
449 ls->dim = NULL;
450 return space;
451}
452
453/* Set the space of "ls" to "space", where the space of "ls" may be missing
454 * due to a preceding call to isl_local_space_take_space.
455 * However, in this case, "ls" only has a single reference and
456 * then the call to isl_local_space_cow has no effect.
457 */
458__isl_give isl_local_space *isl_local_space_restore_space(
459 __isl_take isl_local_space *ls, __isl_take isl_space *space)
460{
461 if (!ls || !space)
462 goto error;
463
464 if (ls->dim == space) {
465 isl_space_free(space);
466 return ls;
467 }
468
469 ls = isl_local_space_cow(ls);
470 if (!ls)
471 goto error;
472 isl_space_free(space: ls->dim);
473 ls->dim = space;
474
475 return ls;
476error:
477 isl_local_space_free(ls);
478 isl_space_free(space);
479 return NULL;
480}
481
482/* Return the local variables of "ls".
483 */
484__isl_keep isl_local *isl_local_space_peek_local(__isl_keep isl_local_space *ls)
485{
486 return ls ? ls->div : NULL;
487}
488
489/* Return a copy of the local variables of "ls".
490 */
491__isl_keep isl_local *isl_local_space_get_local(__isl_keep isl_local_space *ls)
492{
493 return isl_local_copy(local: isl_local_space_peek_local(ls));
494}
495
496/* Return the local variables of "ls".
497 * This may be either a copy or the local variables itself
498 * if there is only one reference to "ls".
499 * This allows the local variables to be modified inplace
500 * if both the local space and its local variables have only a single reference.
501 * The caller is not allowed to modify "ls" between this call and
502 * the subsequent call to isl_local_space_restore_local.
503 * The only exception is that isl_local_space_free can be called instead.
504 */
505static __isl_give isl_local *isl_local_space_take_local(
506 __isl_keep isl_local_space *ls)
507{
508 isl_local *local;
509
510 if (!ls)
511 return NULL;
512 if (ls->ref != 1)
513 return isl_local_space_get_local(ls);
514 local = ls->div;
515 ls->div = NULL;
516 return local;
517}
518
519/* Set the local variables of "ls" to "local",
520 * where the local variables of "ls" may be missing
521 * due to a preceding call to isl_local_space_take_local.
522 * However, in this case, "ls" only has a single reference and
523 * then the call to isl_local_space_cow has no effect.
524 */
525static __isl_give isl_local_space *isl_local_space_restore_local(
526 __isl_take isl_local_space *ls, __isl_take isl_local *local)
527{
528 if (!ls || !local)
529 goto error;
530
531 if (ls->div == local) {
532 isl_local_free(local);
533 return ls;
534 }
535
536 ls = isl_local_space_cow(ls);
537 if (!ls)
538 goto error;
539 isl_local_free(local: ls->div);
540 ls->div = local;
541
542 return ls;
543error:
544 isl_local_space_free(ls);
545 isl_local_free(local);
546 return NULL;
547}
548
549/* Replace the identifier of the tuple of type "type" by "id".
550 */
551__isl_give isl_local_space *isl_local_space_set_tuple_id(
552 __isl_take isl_local_space *ls,
553 enum isl_dim_type type, __isl_take isl_id *id)
554{
555 ls = isl_local_space_cow(ls);
556 if (!ls)
557 goto error;
558 ls->dim = isl_space_set_tuple_id(space: ls->dim, type, id);
559 if (!ls->dim)
560 return isl_local_space_free(ls);
561 return ls;
562error:
563 isl_id_free(id);
564 return NULL;
565}
566
567__isl_give isl_local_space *isl_local_space_set_dim_name(
568 __isl_take isl_local_space *ls,
569 enum isl_dim_type type, unsigned pos, const char *s)
570{
571 ls = isl_local_space_cow(ls);
572 if (!ls)
573 return NULL;
574 ls->dim = isl_space_set_dim_name(space: ls->dim, type, pos, name: s);
575 if (!ls->dim)
576 return isl_local_space_free(ls);
577
578 return ls;
579}
580
581__isl_give isl_local_space *isl_local_space_set_dim_id(
582 __isl_take isl_local_space *ls,
583 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
584{
585 ls = isl_local_space_cow(ls);
586 if (!ls)
587 goto error;
588 ls->dim = isl_space_set_dim_id(space: ls->dim, type, pos, id);
589 if (!ls->dim)
590 return isl_local_space_free(ls);
591
592 return ls;
593error:
594 isl_id_free(id);
595 return NULL;
596}
597
598/* Construct a zero-dimensional local space with the given parameter domain.
599 */
600__isl_give isl_local_space *isl_local_space_set_from_params(
601 __isl_take isl_local_space *ls)
602{
603 isl_space *space;
604
605 space = isl_local_space_take_space(ls);
606 space = isl_space_set_from_params(space);
607 ls = isl_local_space_restore_space(ls, space);
608
609 return ls;
610}
611
612__isl_give isl_local_space *isl_local_space_reset_space(
613 __isl_take isl_local_space *ls, __isl_take isl_space *space)
614{
615 ls = isl_local_space_cow(ls);
616 if (!ls || !space)
617 goto error;
618
619 isl_space_free(space: ls->dim);
620 ls->dim = space;
621
622 return ls;
623error:
624 isl_local_space_free(ls);
625 isl_space_free(space);
626 return NULL;
627}
628
629/* Reorder the dimensions of "ls" according to the given reordering.
630 * The reordering r is assumed to have been extended with the local
631 * variables, leaving them in the same order.
632 */
633__isl_give isl_local_space *isl_local_space_realign(
634 __isl_take isl_local_space *ls, __isl_take isl_reordering *r)
635{
636 isl_local *local;
637
638 local = isl_local_space_take_local(ls);
639 local = isl_local_reorder(local, r: isl_reordering_copy(exp: r));
640 ls = isl_local_space_restore_local(ls, local);
641
642 ls = isl_local_space_reset_space(ls, space: isl_reordering_get_space(r));
643
644 isl_reordering_free(exp: r);
645 return ls;
646}
647
648__isl_give isl_local_space *isl_local_space_add_div(
649 __isl_take isl_local_space *ls, __isl_take isl_vec *div)
650{
651 ls = isl_local_space_cow(ls);
652 if (!ls || !div)
653 goto error;
654
655 if (ls->div->n_col != div->size)
656 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
657 "incompatible dimensions", goto error);
658
659 ls->div = isl_mat_add_zero_cols(mat: ls->div, n: 1);
660 ls->div = isl_mat_add_rows(mat: ls->div, n: 1);
661 if (!ls->div)
662 goto error;
663
664 isl_seq_cpy(dst: ls->div->row[ls->div->n_row - 1], src: div->el, len: div->size);
665 isl_int_set_si(ls->div->row[ls->div->n_row - 1][div->size], 0);
666
667 isl_vec_free(vec: div);
668 return ls;
669error:
670 isl_local_space_free(ls);
671 isl_vec_free(vec: div);
672 return NULL;
673}
674
675__isl_give isl_local_space *isl_local_space_replace_divs(
676 __isl_take isl_local_space *ls, __isl_take isl_mat *div)
677{
678 ls = isl_local_space_cow(ls);
679
680 if (!ls || !div)
681 goto error;
682
683 isl_mat_free(mat: ls->div);
684 ls->div = div;
685 return ls;
686error:
687 isl_mat_free(mat: div);
688 isl_local_space_free(ls);
689 return NULL;
690}
691
692/* Copy row "s" of "src" to row "d" of "dst", applying the expansion
693 * defined by "exp".
694 */
695static void expand_row(__isl_keep isl_mat *dst, int d,
696 __isl_keep isl_mat *src, int s, int *exp)
697{
698 int i;
699 unsigned c = src->n_col - src->n_row;
700
701 isl_seq_cpy(dst: dst->row[d], src: src->row[s], len: c);
702 isl_seq_clr(p: dst->row[d] + c, len: dst->n_col - c);
703
704 for (i = 0; i < s; ++i)
705 isl_int_set(dst->row[d][c + exp[i]], src->row[s][c + i]);
706}
707
708/* Compare (known) divs.
709 * Return non-zero if at least one of the two divs is unknown.
710 * In particular, if both divs are unknown, we respect their
711 * current order. Otherwise, we sort the known div after the unknown
712 * div only if the known div depends on the unknown div.
713 */
714static int cmp_row(isl_int *row_i, isl_int *row_j, int i, int j,
715 unsigned n_row, unsigned n_col)
716{
717 int li, lj;
718 int unknown_i, unknown_j;
719
720 unknown_i = isl_int_is_zero(row_i[0]);
721 unknown_j = isl_int_is_zero(row_j[0]);
722
723 if (unknown_i && unknown_j)
724 return i - j;
725
726 if (unknown_i)
727 li = n_col - n_row + i;
728 else
729 li = isl_seq_last_non_zero(p: row_i, len: n_col);
730 if (unknown_j)
731 lj = n_col - n_row + j;
732 else
733 lj = isl_seq_last_non_zero(p: row_j, len: n_col);
734
735 if (li != lj)
736 return li - lj;
737
738 return isl_seq_cmp(p1: row_i, p2: row_j, len: n_col);
739}
740
741/* Call cmp_row for divs in a matrix.
742 */
743int isl_mat_cmp_div(__isl_keep isl_mat *div, int i, int j)
744{
745 return cmp_row(row_i: div->row[i], row_j: div->row[j], i, j, n_row: div->n_row, n_col: div->n_col);
746}
747
748/* Call cmp_row for divs in a basic map.
749 */
750static int bmap_cmp_row(__isl_keep isl_basic_map *bmap, int i, int j,
751 unsigned total)
752{
753 return cmp_row(row_i: bmap->div[i], row_j: bmap->div[j], i, j, n_row: bmap->n_div, n_col: total);
754}
755
756/* Sort the divs in "bmap".
757 *
758 * We first make sure divs are placed after divs on which they depend.
759 * Then we perform a simple insertion sort based on the same ordering
760 * that is used in isl_merge_divs.
761 */
762__isl_give isl_basic_map *isl_basic_map_sort_divs(
763 __isl_take isl_basic_map *bmap)
764{
765 int i, j;
766 isl_size total;
767
768 bmap = isl_basic_map_order_divs(bmap);
769 if (!bmap)
770 return NULL;
771 if (bmap->n_div <= 1)
772 return bmap;
773
774 total = isl_basic_map_dim(bmap, type: isl_dim_all);
775 if (total < 0)
776 return isl_basic_map_free(bmap);
777 for (i = 1; i < bmap->n_div; ++i) {
778 for (j = i - 1; j >= 0; --j) {
779 if (bmap_cmp_row(bmap, i: j, j: j + 1, total: 2 + total) <= 0)
780 break;
781 bmap = isl_basic_map_swap_div(bmap, a: j, b: j + 1);
782 if (!bmap)
783 return NULL;
784 }
785 }
786
787 return bmap;
788}
789
790/* Sort the divs in the basic maps of "map".
791 */
792__isl_give isl_map *isl_map_sort_divs(__isl_take isl_map *map)
793{
794 return isl_map_inline_foreach_basic_map(map, fn: &isl_basic_map_sort_divs);
795}
796
797/* Combine the two lists of divs into a single list.
798 * For each row i in div1, exp1[i] is set to the position of the corresponding
799 * row in the result. Similarly for div2 and exp2.
800 * This function guarantees
801 * exp1[i] >= i
802 * exp1[i+1] > exp1[i]
803 * For optimal merging, the two input list should have been sorted.
804 */
805__isl_give isl_mat *isl_merge_divs(__isl_keep isl_mat *div1,
806 __isl_keep isl_mat *div2, int *exp1, int *exp2)
807{
808 int i, j, k;
809 isl_mat *div = NULL;
810 unsigned d;
811
812 if (!div1 || !div2)
813 return NULL;
814
815 d = div1->n_col - div1->n_row;
816 div = isl_mat_alloc(ctx: div1->ctx, n_row: 1 + div1->n_row + div2->n_row,
817 n_col: d + div1->n_row + div2->n_row);
818 if (!div)
819 return NULL;
820
821 for (i = 0, j = 0, k = 0; i < div1->n_row && j < div2->n_row; ++k) {
822 int cmp;
823
824 expand_row(dst: div, d: k, src: div1, s: i, exp: exp1);
825 expand_row(dst: div, d: k + 1, src: div2, s: j, exp: exp2);
826
827 cmp = isl_mat_cmp_div(div, i: k, j: k + 1);
828 if (cmp == 0) {
829 exp1[i++] = k;
830 exp2[j++] = k;
831 } else if (cmp < 0) {
832 exp1[i++] = k;
833 } else {
834 exp2[j++] = k;
835 isl_seq_cpy(dst: div->row[k], src: div->row[k + 1], len: div->n_col);
836 }
837 }
838 for (; i < div1->n_row; ++i, ++k) {
839 expand_row(dst: div, d: k, src: div1, s: i, exp: exp1);
840 exp1[i] = k;
841 }
842 for (; j < div2->n_row; ++j, ++k) {
843 expand_row(dst: div, d: k, src: div2, s: j, exp: exp2);
844 exp2[j] = k;
845 }
846
847 div->n_row = k;
848 div->n_col = d + k;
849
850 return div;
851}
852
853/* Swap divs "a" and "b" in "ls".
854 */
855__isl_give isl_local_space *isl_local_space_swap_div(
856 __isl_take isl_local_space *ls, int a, int b)
857{
858 int offset;
859
860 ls = isl_local_space_cow(ls);
861 if (!ls)
862 return NULL;
863 if (a < 0 || a >= ls->div->n_row || b < 0 || b >= ls->div->n_row)
864 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
865 "index out of bounds", return isl_local_space_free(ls));
866 offset = ls->div->n_col - ls->div->n_row;
867 ls->div = isl_mat_swap_cols(mat: ls->div, i: offset + a, j: offset + b);
868 ls->div = isl_mat_swap_rows(mat: ls->div, i: a, j: b);
869 if (!ls->div)
870 return isl_local_space_free(ls);
871 return ls;
872}
873
874/* Construct a local space that contains all the divs in either
875 * "ls1" or "ls2".
876 */
877__isl_give isl_local_space *isl_local_space_intersect(
878 __isl_take isl_local_space *ls1, __isl_take isl_local_space *ls2)
879{
880 isl_ctx *ctx;
881 int *exp1 = NULL;
882 int *exp2 = NULL;
883 isl_mat *div = NULL;
884 isl_bool equal;
885
886 if (!ls1 || !ls2)
887 goto error;
888
889 ctx = isl_local_space_get_ctx(ls: ls1);
890 if (!isl_space_is_equal(space1: ls1->dim, space2: ls2->dim))
891 isl_die(ctx, isl_error_invalid,
892 "spaces should be identical", goto error);
893
894 if (ls2->div->n_row == 0) {
895 isl_local_space_free(ls: ls2);
896 return ls1;
897 }
898
899 if (ls1->div->n_row == 0) {
900 isl_local_space_free(ls: ls1);
901 return ls2;
902 }
903
904 exp1 = isl_alloc_array(ctx, int, ls1->div->n_row);
905 exp2 = isl_alloc_array(ctx, int, ls2->div->n_row);
906 if (!exp1 || !exp2)
907 goto error;
908
909 div = isl_merge_divs(div1: ls1->div, div2: ls2->div, exp1, exp2);
910 if (!div)
911 goto error;
912
913 equal = isl_mat_is_equal(mat1: ls1->div, mat2: div);
914 if (equal < 0)
915 goto error;
916 if (!equal)
917 ls1 = isl_local_space_cow(ls: ls1);
918 if (!ls1)
919 goto error;
920
921 free(ptr: exp1);
922 free(ptr: exp2);
923 isl_local_space_free(ls: ls2);
924 isl_mat_free(mat: ls1->div);
925 ls1->div = div;
926
927 return ls1;
928error:
929 free(ptr: exp1);
930 free(ptr: exp2);
931 isl_mat_free(mat: div);
932 isl_local_space_free(ls: ls1);
933 isl_local_space_free(ls: ls2);
934 return NULL;
935}
936
937/* Is the local variable "div" of "ls" marked as not having
938 * an explicit representation?
939 * Note that even if this variable is not marked in this way and therefore
940 * does have an explicit representation, this representation may still
941 * depend (indirectly) on other local variables that do not
942 * have an explicit representation.
943 */
944isl_bool isl_local_space_div_is_marked_unknown(__isl_keep isl_local_space *ls,
945 int div)
946{
947 if (!ls)
948 return isl_bool_error;
949 return isl_local_div_is_marked_unknown(local: ls->div, pos: div);
950}
951
952/* Does "ls" have a complete explicit representation for div "div"?
953 */
954isl_bool isl_local_space_div_is_known(__isl_keep isl_local_space *ls, int div)
955{
956 if (!ls)
957 return isl_bool_error;
958 return isl_local_div_is_known(local: ls->div, pos: div);
959}
960
961/* Does "ls" have an explicit representation for all local variables?
962 */
963isl_bool isl_local_space_divs_known(__isl_keep isl_local_space *ls)
964{
965 if (!ls)
966 return isl_bool_error;
967 return isl_local_divs_known(local: ls->div);
968}
969
970__isl_give isl_local_space *isl_local_space_domain(
971 __isl_take isl_local_space *ls)
972{
973 isl_size n_out;
974
975 n_out = isl_local_space_dim(ls, type: isl_dim_out);
976 if (n_out < 0)
977 return isl_local_space_free(ls);
978 ls = isl_local_space_drop_dims(ls, type: isl_dim_out, first: 0, n: n_out);
979 ls = isl_local_space_cow(ls);
980 if (!ls)
981 return NULL;
982 ls->dim = isl_space_domain(space: ls->dim);
983 if (!ls->dim)
984 return isl_local_space_free(ls);
985 return ls;
986}
987
988__isl_give isl_local_space *isl_local_space_range(
989 __isl_take isl_local_space *ls)
990{
991 isl_size n_in;
992
993 n_in = isl_local_space_dim(ls, type: isl_dim_in);
994 if (n_in < 0)
995 return isl_local_space_free(ls);
996 ls = isl_local_space_drop_dims(ls, type: isl_dim_in, first: 0, n: n_in);
997 ls = isl_local_space_cow(ls);
998 if (!ls)
999 return NULL;
1000
1001 ls->dim = isl_space_range(space: ls->dim);
1002 if (!ls->dim)
1003 return isl_local_space_free(ls);
1004 return ls;
1005}
1006
1007/* Construct a local space for a map that has the given local
1008 * space as domain and that has a zero-dimensional range.
1009 */
1010__isl_give isl_local_space *isl_local_space_from_domain(
1011 __isl_take isl_local_space *ls)
1012{
1013 ls = isl_local_space_cow(ls);
1014 if (!ls)
1015 return NULL;
1016 ls->dim = isl_space_from_domain(space: ls->dim);
1017 if (!ls->dim)
1018 return isl_local_space_free(ls);
1019 return ls;
1020}
1021
1022__isl_give isl_local_space *isl_local_space_add_dims(
1023 __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned n)
1024{
1025 isl_size pos;
1026
1027 pos = isl_local_space_dim(ls, type);
1028 if (pos < 0)
1029 return isl_local_space_free(ls);
1030 return isl_local_space_insert_dims(ls, type, first: pos, n);
1031}
1032
1033/* Lift the basic set "bset", living in the space of "ls"
1034 * to live in a space with extra coordinates corresponding
1035 * to the local variables of "ls".
1036 */
1037__isl_give isl_basic_set *isl_local_space_lift_basic_set(
1038 __isl_take isl_local_space *ls, __isl_take isl_basic_set *bset)
1039{
1040 isl_size n_local;
1041 isl_space *space;
1042 isl_basic_set *ls_bset;
1043
1044 n_local = isl_local_space_dim(ls, type: isl_dim_div);
1045 space = isl_basic_set_peek_space(bset);
1046 if (n_local < 0 ||
1047 isl_local_space_check_has_space(ls, space) < 0)
1048 goto error;
1049
1050 if (n_local == 0) {
1051 isl_local_space_free(ls);
1052 return bset;
1053 }
1054
1055 bset = isl_basic_set_add_dims(bset, type: isl_dim_set, n: n_local);
1056 ls_bset = isl_basic_set_from_local_space(ls);
1057 ls_bset = isl_basic_set_lift(bset: ls_bset);
1058 ls_bset = isl_basic_set_flatten(bset: ls_bset);
1059 bset = isl_basic_set_intersect(bset1: bset, bset2: ls_bset);
1060
1061 return bset;
1062error:
1063 isl_local_space_free(ls);
1064 isl_basic_set_free(bset);
1065 return NULL;
1066}
1067
1068/* Lift the set "set", living in the space of "ls"
1069 * to live in a space with extra coordinates corresponding
1070 * to the local variables of "ls".
1071 */
1072__isl_give isl_set *isl_local_space_lift_set(__isl_take isl_local_space *ls,
1073 __isl_take isl_set *set)
1074{
1075 isl_size n_local;
1076 isl_basic_set *bset;
1077
1078 n_local = isl_local_space_dim(ls, type: isl_dim_div);
1079 if (n_local < 0 ||
1080 isl_local_space_check_has_space(ls, space: isl_set_peek_space(set)) < 0)
1081 goto error;
1082
1083 if (n_local == 0) {
1084 isl_local_space_free(ls);
1085 return set;
1086 }
1087
1088 set = isl_set_add_dims(set, type: isl_dim_set, n: n_local);
1089 bset = isl_basic_set_from_local_space(ls);
1090 bset = isl_basic_set_lift(bset);
1091 bset = isl_basic_set_flatten(bset);
1092 set = isl_set_intersect(set1: set, set2: isl_set_from_basic_set(bset));
1093
1094 return set;
1095error:
1096 isl_local_space_free(ls);
1097 isl_set_free(set);
1098 return NULL;
1099}
1100
1101/* Remove common factor of non-constant terms and denominator.
1102 */
1103static __isl_give isl_local_space *normalize_div(
1104 __isl_take isl_local_space *ls, int div)
1105{
1106 isl_ctx *ctx = ls->div->ctx;
1107 unsigned total = ls->div->n_col - 2;
1108
1109 isl_seq_gcd(p: ls->div->row[div] + 2, len: total, gcd: &ctx->normalize_gcd);
1110 isl_int_gcd(ctx->normalize_gcd,
1111 ctx->normalize_gcd, ls->div->row[div][0]);
1112 if (isl_int_is_one(ctx->normalize_gcd))
1113 return ls;
1114
1115 isl_seq_scale_down(dst: ls->div->row[div] + 2, src: ls->div->row[div] + 2,
1116 f: ctx->normalize_gcd, len: total);
1117 isl_int_divexact(ls->div->row[div][0], ls->div->row[div][0],
1118 ctx->normalize_gcd);
1119 isl_int_fdiv_q(ls->div->row[div][1], ls->div->row[div][1],
1120 ctx->normalize_gcd);
1121
1122 return ls;
1123}
1124
1125/* Exploit the equalities in "eq" to simplify the expressions of
1126 * the integer divisions in "ls".
1127 * The integer divisions in "ls" are assumed to appear as regular
1128 * dimensions in "eq".
1129 */
1130__isl_give isl_local_space *isl_local_space_substitute_equalities(
1131 __isl_take isl_local_space *ls, __isl_take isl_basic_set *eq)
1132{
1133 int i, j, k;
1134 isl_size total, dim;
1135 unsigned n_div;
1136
1137 if (!ls || !eq)
1138 goto error;
1139
1140 total = isl_space_dim(space: eq->dim, type: isl_dim_all);
1141 dim = isl_local_space_dim(ls, type: isl_dim_all);
1142 if (dim < 0 || total < 0)
1143 goto error;
1144 if (dim != total)
1145 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1146 "spaces don't match", goto error);
1147 total++;
1148 n_div = eq->n_div;
1149 for (i = 0; i < eq->n_eq; ++i) {
1150 j = isl_seq_last_non_zero(p: eq->eq[i], len: total + n_div);
1151 if (j < 0 || j == 0 || j >= total)
1152 continue;
1153
1154 for (k = 0; k < ls->div->n_row; ++k) {
1155 if (isl_int_is_zero(ls->div->row[k][1 + j]))
1156 continue;
1157 ls = isl_local_space_cow(ls);
1158 if (!ls)
1159 goto error;
1160 ls->div = isl_mat_cow(mat: ls->div);
1161 if (!ls->div)
1162 goto error;
1163 isl_seq_elim(dst: ls->div->row[k] + 1, src: eq->eq[i], pos: j, len: total,
1164 m: &ls->div->row[k][0]);
1165 ls = normalize_div(ls, div: k);
1166 if (!ls)
1167 goto error;
1168 }
1169 }
1170
1171 isl_basic_set_free(bset: eq);
1172 return ls;
1173error:
1174 isl_basic_set_free(bset: eq);
1175 isl_local_space_free(ls);
1176 return NULL;
1177}
1178
1179/* Plug in the affine expressions "subs" of length "subs_len" (including
1180 * the denominator and the constant term) into the variable at position "pos"
1181 * of the "n" div expressions starting at "first".
1182 *
1183 * Let i be the dimension to replace and let "subs" be of the form
1184 *
1185 * f/d
1186 *
1187 * Any integer division starting at "first" with a non-zero coefficient for i,
1188 *
1189 * floor((a i + g)/m)
1190 *
1191 * is replaced by
1192 *
1193 * floor((a f + d g)/(m d))
1194 */
1195__isl_give isl_local_space *isl_local_space_substitute_seq(
1196 __isl_take isl_local_space *ls,
1197 enum isl_dim_type type, unsigned pos, isl_int *subs, int subs_len,
1198 int first, int n)
1199{
1200 int i;
1201 isl_int v;
1202
1203 if (n == 0)
1204 return ls;
1205 ls = isl_local_space_cow(ls);
1206 if (!ls)
1207 return NULL;
1208 ls->div = isl_mat_cow(mat: ls->div);
1209 if (!ls->div)
1210 return isl_local_space_free(ls);
1211
1212 if (first + n > ls->div->n_row)
1213 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1214 "index out of bounds", return isl_local_space_free(ls));
1215
1216 pos += isl_local_space_offset(ls, type);
1217
1218 isl_int_init(v);
1219 for (i = first; i < first + n; ++i) {
1220 if (isl_int_is_zero(ls->div->row[i][1 + pos]))
1221 continue;
1222 isl_seq_substitute(p: ls->div->row[i], pos, subs,
1223 p_len: ls->div->n_col, subs_len, v);
1224 ls = normalize_div(ls, div: i);
1225 if (!ls)
1226 break;
1227 }
1228 isl_int_clear(v);
1229
1230 return ls;
1231}
1232
1233/* Plug in "subs" for dimension "type", "pos" in the integer divisions
1234 * of "ls".
1235 *
1236 * Let i be the dimension to replace and let "subs" be of the form
1237 *
1238 * f/d
1239 *
1240 * Any integer division with a non-zero coefficient for i,
1241 *
1242 * floor((a i + g)/m)
1243 *
1244 * is replaced by
1245 *
1246 * floor((a f + d g)/(m d))
1247 */
1248__isl_give isl_local_space *isl_local_space_substitute(
1249 __isl_take isl_local_space *ls,
1250 enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
1251{
1252 isl_size n_div;
1253
1254 ls = isl_local_space_cow(ls);
1255 if (!ls || !subs)
1256 return isl_local_space_free(ls);
1257
1258 if (!isl_space_is_equal(space1: ls->dim, space2: subs->ls->dim))
1259 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1260 "spaces don't match", return isl_local_space_free(ls));
1261 n_div = isl_local_space_dim(ls: subs->ls, type: isl_dim_div);
1262 if (n_div < 0)
1263 return isl_local_space_free(ls);
1264 if (n_div != 0)
1265 isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,
1266 "cannot handle divs yet",
1267 return isl_local_space_free(ls));
1268
1269 return isl_local_space_substitute_seq(ls, type, pos, subs: subs->v->el,
1270 subs_len: subs->v->size, first: 0, n: ls->div->n_row);
1271}
1272
1273isl_bool isl_local_space_is_named_or_nested(__isl_keep isl_local_space *ls,
1274 enum isl_dim_type type)
1275{
1276 if (!ls)
1277 return isl_bool_error;
1278 return isl_space_is_named_or_nested(space: ls->dim, type);
1279}
1280
1281__isl_give isl_local_space *isl_local_space_drop_dims(
1282 __isl_take isl_local_space *ls,
1283 enum isl_dim_type type, unsigned first, unsigned n)
1284{
1285 if (!ls)
1286 return NULL;
1287 if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
1288 return ls;
1289
1290 if (isl_local_space_check_range(obj: ls, type, first, n) < 0)
1291 return isl_local_space_free(ls);
1292
1293 ls = isl_local_space_cow(ls);
1294 if (!ls)
1295 return NULL;
1296
1297 if (type == isl_dim_div) {
1298 ls->div = isl_mat_drop_rows(mat: ls->div, row: first, n);
1299 } else {
1300 ls->dim = isl_space_drop_dims(space: ls->dim, type, first, num: n);
1301 if (!ls->dim)
1302 return isl_local_space_free(ls);
1303 }
1304
1305 first += 1 + isl_local_space_offset(ls, type);
1306 ls->div = isl_mat_drop_cols(mat: ls->div, col: first, n);
1307 if (!ls->div)
1308 return isl_local_space_free(ls);
1309
1310 return ls;
1311}
1312
1313__isl_give isl_local_space *isl_local_space_insert_dims(
1314 __isl_take isl_local_space *ls,
1315 enum isl_dim_type type, unsigned first, unsigned n)
1316{
1317 if (!ls)
1318 return NULL;
1319 if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
1320 return ls;
1321
1322 if (isl_local_space_check_range(obj: ls, type, first, n: 0) < 0)
1323 return isl_local_space_free(ls);
1324
1325 ls = isl_local_space_cow(ls);
1326 if (!ls)
1327 return NULL;
1328
1329 if (type == isl_dim_div) {
1330 ls->div = isl_mat_insert_zero_rows(mat: ls->div, row: first, n);
1331 } else {
1332 ls->dim = isl_space_insert_dims(space: ls->dim, type, pos: first, n);
1333 if (!ls->dim)
1334 return isl_local_space_free(ls);
1335 }
1336
1337 first += 1 + isl_local_space_offset(ls, type);
1338 ls->div = isl_mat_insert_zero_cols(mat: ls->div, first, n);
1339 if (!ls->div)
1340 return isl_local_space_free(ls);
1341
1342 return ls;
1343}
1344
1345/* Does the linear part of "constraint" correspond to
1346 * integer division "div" in "ls"?
1347 *
1348 * That is, given div = floor((c + f)/m), is the constraint of the form
1349 *
1350 * f - m d + c' >= 0 [sign = 1]
1351 * or
1352 * -f + m d + c'' >= 0 [sign = -1]
1353 * ?
1354 * If so, set *sign to the corresponding value.
1355 */
1356static isl_bool is_linear_div_constraint(__isl_keep isl_local_space *ls,
1357 isl_int *constraint, unsigned div, int *sign)
1358{
1359 isl_bool unknown;
1360 unsigned pos;
1361
1362 unknown = isl_local_space_div_is_marked_unknown(ls, div);
1363 if (unknown < 0)
1364 return isl_bool_error;
1365 if (unknown)
1366 return isl_bool_false;
1367
1368 pos = isl_local_space_offset(ls, type: isl_dim_div) + div;
1369
1370 if (isl_int_eq(constraint[pos], ls->div->row[div][0])) {
1371 *sign = -1;
1372 if (!isl_seq_is_neg(p1: constraint + 1,
1373 p2: ls->div->row[div] + 2, len: pos - 1))
1374 return isl_bool_false;
1375 } else if (isl_int_abs_eq(constraint[pos], ls->div->row[div][0])) {
1376 *sign = 1;
1377 if (!isl_seq_eq(p1: constraint + 1, p2: ls->div->row[div] + 2, len: pos - 1))
1378 return isl_bool_false;
1379 } else {
1380 return isl_bool_false;
1381 }
1382 if (isl_seq_first_non_zero(p: constraint + pos + 1,
1383 len: ls->div->n_row - div - 1) != -1)
1384 return isl_bool_false;
1385 return isl_bool_true;
1386}
1387
1388/* Check if the constraints pointed to by "constraint" is a div
1389 * constraint corresponding to div "div" in "ls".
1390 *
1391 * That is, if div = floor(f/m), then check if the constraint is
1392 *
1393 * f - m d >= 0
1394 * or
1395 * -(f-(m-1)) + m d >= 0
1396 *
1397 * First check if the linear part is of the right form and
1398 * then check the constant term.
1399 */
1400isl_bool isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls,
1401 isl_int *constraint, unsigned div)
1402{
1403 int sign;
1404 isl_bool linear;
1405
1406 linear = is_linear_div_constraint(ls, constraint, div, sign: &sign);
1407 if (linear < 0 || !linear)
1408 return linear;
1409
1410 if (sign < 0) {
1411 int neg;
1412 isl_int_sub(ls->div->row[div][1],
1413 ls->div->row[div][1], ls->div->row[div][0]);
1414 isl_int_add_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
1415 neg = isl_seq_is_neg(p1: constraint, p2: ls->div->row[div] + 1, len: 1);
1416 isl_int_sub_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
1417 isl_int_add(ls->div->row[div][1],
1418 ls->div->row[div][1], ls->div->row[div][0]);
1419 if (!neg)
1420 return isl_bool_false;
1421 } else {
1422 if (!isl_int_eq(constraint[0], ls->div->row[div][1]))
1423 return isl_bool_false;
1424 }
1425
1426 return isl_bool_true;
1427}
1428
1429/* Is the constraint pointed to by "constraint" one
1430 * of an equality that corresponds to integer division "div" in "ls"?
1431 *
1432 * That is, given an integer division of the form
1433 *
1434 * a = floor((f + c)/m)
1435 *
1436 * is the equality of the form
1437 *
1438 * -f + m d + c' = 0
1439 * ?
1440 * Note that the constant term is not checked explicitly, but given
1441 * that this is a valid equality constraint, the constant c' necessarily
1442 * has a value close to -c.
1443 */
1444isl_bool isl_local_space_is_div_equality(__isl_keep isl_local_space *ls,
1445 isl_int *constraint, unsigned div)
1446{
1447 int sign;
1448 isl_bool linear;
1449
1450 linear = is_linear_div_constraint(ls, constraint, div, sign: &sign);
1451 if (linear < 0 || !linear)
1452 return linear;
1453
1454 return isl_bool_ok(b: sign < 0);
1455}
1456
1457/*
1458 * Set active[i] to 1 if the dimension at position i is involved
1459 * in the linear expression l.
1460 */
1461int *isl_local_space_get_active(__isl_keep isl_local_space *ls, isl_int *l)
1462{
1463 int i, j;
1464 isl_ctx *ctx;
1465 int *active = NULL;
1466 isl_size total;
1467 unsigned offset;
1468
1469 ctx = isl_local_space_get_ctx(ls);
1470 total = isl_local_space_dim(ls, type: isl_dim_all);
1471 if (total < 0)
1472 return NULL;
1473 active = isl_calloc_array(ctx, int, total);
1474 if (total && !active)
1475 return NULL;
1476
1477 for (i = 0; i < total; ++i)
1478 active[i] = !isl_int_is_zero(l[i]);
1479
1480 offset = isl_local_space_offset(ls, type: isl_dim_div) - 1;
1481 for (i = ls->div->n_row - 1; i >= 0; --i) {
1482 if (!active[offset + i])
1483 continue;
1484 for (j = 0; j < total; ++j)
1485 active[j] |= !isl_int_is_zero(ls->div->row[i][2 + j]);
1486 }
1487
1488 return active;
1489}
1490
1491/* Given a local space "ls" of a set, create a local space
1492 * for the lift of the set. In particular, the result
1493 * is of the form [dim -> local[..]], with ls->div->n_row variables in the
1494 * range of the wrapped map.
1495 */
1496__isl_give isl_local_space *isl_local_space_lift(
1497 __isl_take isl_local_space *ls)
1498{
1499 ls = isl_local_space_cow(ls);
1500 if (!ls)
1501 return NULL;
1502
1503 ls->dim = isl_space_lift(space: ls->dim, n_local: ls->div->n_row);
1504 ls->div = isl_mat_drop_rows(mat: ls->div, row: 0, n: ls->div->n_row);
1505 if (!ls->dim || !ls->div)
1506 return isl_local_space_free(ls);
1507
1508 return ls;
1509}
1510
1511/* Construct a basic map that maps a set living in local space "ls"
1512 * to the corresponding lifted local space.
1513 */
1514__isl_give isl_basic_map *isl_local_space_lifting(
1515 __isl_take isl_local_space *ls)
1516{
1517 isl_basic_map *lifting;
1518 isl_basic_set *bset;
1519
1520 if (!ls)
1521 return NULL;
1522 if (!isl_local_space_is_set(ls))
1523 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1524 "lifting only defined on set spaces", goto error);
1525
1526 bset = isl_basic_set_from_local_space(ls);
1527 lifting = isl_basic_set_unwrap(bset: isl_basic_set_lift(bset));
1528 lifting = isl_basic_map_domain_map(bmap: lifting);
1529 lifting = isl_basic_map_reverse(bmap: lifting);
1530
1531 return lifting;
1532error:
1533 isl_local_space_free(ls);
1534 return NULL;
1535}
1536
1537/* Compute the preimage of "ls" under the function represented by "ma".
1538 * In other words, plug in "ma" in "ls". The result is a local space
1539 * that is part of the domain space of "ma".
1540 *
1541 * If the divs in "ls" are represented as
1542 *
1543 * floor((a_i(p) + b_i x + c_i(divs))/n_i)
1544 *
1545 * and ma is represented by
1546 *
1547 * x = D(p) + F(y) + G(divs')
1548 *
1549 * then the resulting divs are
1550 *
1551 * floor((a_i(p) + b_i D(p) + b_i F(y) + B_i G(divs') + c_i(divs))/n_i)
1552 *
1553 * We first copy over the divs from "ma" and then
1554 * we add the modified divs from "ls".
1555 */
1556__isl_give isl_local_space *isl_local_space_preimage_multi_aff(
1557 __isl_take isl_local_space *ls, __isl_take isl_multi_aff *ma)
1558{
1559 int i;
1560 isl_space *space;
1561 isl_local_space *res = NULL;
1562 isl_size n_div_ls, n_div_ma;
1563 isl_int f, c1, c2, g;
1564
1565 ma = isl_multi_aff_align_divs(maff: ma);
1566 if (!ls || !ma)
1567 goto error;
1568 if (!isl_space_is_range_internal(space1: ls->dim, space2: ma->space))
1569 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1570 "spaces don't match", goto error);
1571
1572 n_div_ls = isl_local_space_dim(ls, type: isl_dim_div);
1573 n_div_ma = ma->n ? isl_aff_dim(aff: ma->u.p[0], type: isl_dim_div) : 0;
1574 if (n_div_ls < 0 || n_div_ma < 0)
1575 goto error;
1576
1577 space = isl_space_domain(space: isl_multi_aff_get_space(multi: ma));
1578 res = isl_local_space_alloc(space, n_div: n_div_ma + n_div_ls);
1579 if (!res)
1580 goto error;
1581
1582 if (n_div_ma) {
1583 isl_mat_free(mat: res->div);
1584 res->div = isl_mat_copy(mat: ma->u.p[0]->ls->div);
1585 res->div = isl_mat_add_zero_cols(mat: res->div, n: n_div_ls);
1586 res->div = isl_mat_add_rows(mat: res->div, n: n_div_ls);
1587 if (!res->div)
1588 goto error;
1589 }
1590
1591 isl_int_init(f);
1592 isl_int_init(c1);
1593 isl_int_init(c2);
1594 isl_int_init(g);
1595
1596 for (i = 0; i < ls->div->n_row; ++i) {
1597 if (isl_int_is_zero(ls->div->row[i][0])) {
1598 isl_int_set_si(res->div->row[n_div_ma + i][0], 0);
1599 continue;
1600 }
1601 if (isl_seq_preimage(dst: res->div->row[n_div_ma + i],
1602 src: ls->div->row[i],
1603 ma, n_before: 0, n_after: 0, n_div_ma, n_div_bmap: n_div_ls, f, c1, c2, g, has_denom: 1) < 0)
1604 res = isl_local_space_free(ls: res);
1605 res = normalize_div(ls: res, div: n_div_ma + i);
1606 if (!res)
1607 break;
1608 }
1609
1610 isl_int_clear(f);
1611 isl_int_clear(c1);
1612 isl_int_clear(c2);
1613 isl_int_clear(g);
1614
1615 isl_local_space_free(ls);
1616 isl_multi_aff_free(multi: ma);
1617 return res;
1618error:
1619 isl_local_space_free(ls);
1620 isl_multi_aff_free(multi: ma);
1621 isl_local_space_free(ls: res);
1622 return NULL;
1623}
1624
1625/* Move the "n" dimensions of "src_type" starting at "src_pos" of "ls"
1626 * to dimensions of "dst_type" at "dst_pos".
1627 *
1628 * Moving to/from local dimensions is not allowed.
1629 * We currently assume that the dimension type changes.
1630 */
1631__isl_give isl_local_space *isl_local_space_move_dims(
1632 __isl_take isl_local_space *ls,
1633 enum isl_dim_type dst_type, unsigned dst_pos,
1634 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1635{
1636 isl_space *space;
1637 isl_local *local;
1638 isl_size v_src, v_dst;
1639 unsigned g_dst_pos;
1640 unsigned g_src_pos;
1641
1642 if (!ls)
1643 return NULL;
1644 if (n == 0 &&
1645 !isl_local_space_is_named_or_nested(ls, type: src_type) &&
1646 !isl_local_space_is_named_or_nested(ls, type: dst_type))
1647 return ls;
1648
1649 if (isl_local_space_check_range(obj: ls, type: src_type, first: src_pos, n) < 0)
1650 return isl_local_space_free(ls);
1651 if (isl_local_space_check_range(obj: ls, type: dst_type, first: dst_pos, n: 0) < 0)
1652 return isl_local_space_free(ls);
1653 if (src_type == isl_dim_div)
1654 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1655 "cannot move divs", return isl_local_space_free(ls));
1656 if (dst_type == isl_dim_div)
1657 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1658 "cannot move to divs", return isl_local_space_free(ls));
1659 if (dst_type == src_type && dst_pos == src_pos)
1660 return ls;
1661 if (dst_type == src_type)
1662 isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,
1663 "moving dims within the same type not supported",
1664 return isl_local_space_free(ls));
1665
1666 v_src = isl_local_space_var_offset(ls, type: src_type);
1667 v_dst = isl_local_space_var_offset(ls, type: dst_type);
1668 if (v_src < 0 || v_dst < 0)
1669 return isl_local_space_free(ls);
1670 g_src_pos = v_src + src_pos;
1671 g_dst_pos = v_dst + dst_pos;
1672 if (dst_type > src_type)
1673 g_dst_pos -= n;
1674
1675 local = isl_local_space_take_local(ls);
1676 local = isl_local_move_vars(local, dst_pos: g_dst_pos, src_pos: g_src_pos, n);
1677 ls = isl_local_space_restore_local(ls, local);
1678
1679 space = isl_local_space_take_space(ls);
1680 space = isl_space_move_dims(space, dst_type, dst_pos,
1681 src_type, src_pos, n);
1682 ls = isl_local_space_restore_space(ls, space);
1683
1684 return ls;
1685}
1686
1687/* Remove any internal structure of the domain of "ls".
1688 * If there is any such internal structure in the input,
1689 * then the name of the corresponding space is also removed.
1690 */
1691__isl_give isl_local_space *isl_local_space_flatten_domain(
1692 __isl_take isl_local_space *ls)
1693{
1694 if (!ls)
1695 return NULL;
1696
1697 if (!ls->dim->nested[0])
1698 return ls;
1699
1700 ls = isl_local_space_cow(ls);
1701 if (!ls)
1702 return NULL;
1703
1704 ls->dim = isl_space_flatten_domain(space: ls->dim);
1705 if (!ls->dim)
1706 return isl_local_space_free(ls);
1707
1708 return ls;
1709}
1710
1711/* Remove any internal structure of the range of "ls".
1712 * If there is any such internal structure in the input,
1713 * then the name of the corresponding space is also removed.
1714 */
1715__isl_give isl_local_space *isl_local_space_flatten_range(
1716 __isl_take isl_local_space *ls)
1717{
1718 if (!ls)
1719 return NULL;
1720
1721 if (!ls->dim->nested[1])
1722 return ls;
1723
1724 ls = isl_local_space_cow(ls);
1725 if (!ls)
1726 return NULL;
1727
1728 ls->dim = isl_space_flatten_range(space: ls->dim);
1729 if (!ls->dim)
1730 return isl_local_space_free(ls);
1731
1732 return ls;
1733}
1734
1735/* Given the local space "ls" of a map, return the local space of a set
1736 * that lives in a space that wraps the space of "ls" and that has
1737 * the same divs.
1738 */
1739__isl_give isl_local_space *isl_local_space_wrap(__isl_take isl_local_space *ls)
1740{
1741 ls = isl_local_space_cow(ls);
1742 if (!ls)
1743 return NULL;
1744
1745 ls->dim = isl_space_wrap(space: ls->dim);
1746 if (!ls->dim)
1747 return isl_local_space_free(ls);
1748
1749 return ls;
1750}
1751
1752/* Lift the point "pnt", living in the (set) space of "ls"
1753 * to live in a space with extra coordinates corresponding
1754 * to the local variables of "ls".
1755 */
1756__isl_give isl_point *isl_local_space_lift_point(__isl_take isl_local_space *ls,
1757 __isl_take isl_point *pnt)
1758{
1759 isl_size n_local;
1760 isl_space *space;
1761 isl_local *local;
1762 isl_vec *vec;
1763
1764 if (isl_local_space_check_has_space(ls, space: isl_point_peek_space(pnt)) < 0)
1765 goto error;
1766
1767 local = isl_local_space_peek_local(ls);
1768 n_local = isl_local_space_dim(ls, type: isl_dim_div);
1769 if (n_local < 0)
1770 goto error;
1771
1772 space = isl_point_take_space(pnt);
1773 vec = isl_point_take_vec(pnt);
1774
1775 space = isl_space_lift(space, n_local);
1776 vec = isl_local_extend_point_vec(local, v: vec);
1777
1778 pnt = isl_point_restore_vec(pnt, vec);
1779 pnt = isl_point_restore_space(pnt, space);
1780
1781 isl_local_space_free(ls);
1782
1783 return pnt;
1784error:
1785 isl_local_space_free(ls);
1786 isl_point_free(pnt);
1787 return NULL;
1788}
1789

source code of polly/lib/External/isl/isl_local_space.c