2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2014 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
13 #include <isl_ctx_private.h>
14 #include <isl_map_private.h>
15 #include <isl_local_space_private.h>
16 #include <isl_space_private.h>
17 #include <isl_mat_private.h>
18 #include <isl_aff_private.h>
19 #include <isl_vec_private.h>
21 #include <isl_local.h>
23 isl_ctx
*isl_local_space_get_ctx(__isl_keep isl_local_space
*ls
)
25 return ls
? ls
->dim
->ctx
: NULL
;
28 /* Return a hash value that digests "ls".
30 uint32_t isl_local_space_get_hash(__isl_keep isl_local_space
*ls
)
32 uint32_t hash
, space_hash
, div_hash
;
37 hash
= isl_hash_init();
38 space_hash
= isl_space_get_hash(ls
->dim
);
39 isl_hash_hash(hash
, space_hash
);
40 div_hash
= isl_mat_get_hash(ls
->div
);
41 isl_hash_hash(hash
, div_hash
);
46 __isl_give isl_local_space
*isl_local_space_alloc_div(__isl_take isl_space
*dim
,
47 __isl_take isl_mat
*div
)
50 isl_local_space
*ls
= NULL
;
55 ctx
= isl_space_get_ctx(dim
);
56 ls
= isl_calloc_type(ctx
, struct isl_local_space
);
68 isl_local_space_free(ls
);
72 __isl_give isl_local_space
*isl_local_space_alloc(__isl_take isl_space
*dim
,
82 total
= isl_space_dim(dim
, isl_dim_all
);
84 ctx
= isl_space_get_ctx(dim
);
85 div
= isl_mat_alloc(ctx
, n_div
, 1 + 1 + total
+ n_div
);
86 return isl_local_space_alloc_div(dim
, div
);
89 __isl_give isl_local_space
*isl_local_space_from_space(__isl_take isl_space
*dim
)
91 return isl_local_space_alloc(dim
, 0);
94 __isl_give isl_local_space
*isl_local_space_copy(__isl_keep isl_local_space
*ls
)
103 __isl_give isl_local_space
*isl_local_space_dup(__isl_keep isl_local_space
*ls
)
108 return isl_local_space_alloc_div(isl_space_copy(ls
->dim
),
109 isl_mat_copy(ls
->div
));
113 __isl_give isl_local_space
*isl_local_space_cow(__isl_take isl_local_space
*ls
)
121 return isl_local_space_dup(ls
);
124 __isl_null isl_local_space
*isl_local_space_free(
125 __isl_take isl_local_space
*ls
)
133 isl_space_free(ls
->dim
);
134 isl_mat_free(ls
->div
);
141 /* Is the local space that of a parameter domain?
143 isl_bool
isl_local_space_is_params(__isl_keep isl_local_space
*ls
)
146 return isl_bool_error
;
147 return isl_space_is_params(ls
->dim
);
150 /* Is the local space that of a set?
152 isl_bool
isl_local_space_is_set(__isl_keep isl_local_space
*ls
)
154 return ls
? isl_space_is_set(ls
->dim
) : isl_bool_error
;
157 /* Do "ls1" and "ls2" have the same space?
159 isl_bool
isl_local_space_has_equal_space(__isl_keep isl_local_space
*ls1
,
160 __isl_keep isl_local_space
*ls2
)
163 return isl_bool_error
;
165 return isl_space_is_equal(ls1
->dim
, ls2
->dim
);
168 /* Return true if the two local spaces are identical, with identical
169 * expressions for the integer divisions.
171 isl_bool
isl_local_space_is_equal(__isl_keep isl_local_space
*ls1
,
172 __isl_keep isl_local_space
*ls2
)
176 equal
= isl_local_space_has_equal_space(ls1
, ls2
);
177 if (equal
< 0 || !equal
)
180 if (!isl_local_space_divs_known(ls1
))
181 return isl_bool_false
;
182 if (!isl_local_space_divs_known(ls2
))
183 return isl_bool_false
;
185 return isl_mat_is_equal(ls1
->div
, ls2
->div
);
188 /* Compare two isl_local_spaces.
190 * Return -1 if "ls1" is "smaller" than "ls2", 1 if "ls1" is "greater"
191 * than "ls2" and 0 if they are equal.
193 int isl_local_space_cmp(__isl_keep isl_local_space
*ls1
,
194 __isl_keep isl_local_space
*ls2
)
205 cmp
= isl_space_cmp(ls1
->dim
, ls2
->dim
);
209 return isl_local_cmp(ls1
->div
, ls2
->div
);
212 int isl_local_space_dim(__isl_keep isl_local_space
*ls
,
213 enum isl_dim_type type
)
217 if (type
== isl_dim_div
)
218 return ls
->div
->n_row
;
219 if (type
== isl_dim_all
)
220 return isl_space_dim(ls
->dim
, isl_dim_all
) + ls
->div
->n_row
;
221 return isl_space_dim(ls
->dim
, type
);
224 unsigned isl_local_space_offset(__isl_keep isl_local_space
*ls
,
225 enum isl_dim_type type
)
234 case isl_dim_cst
: return 0;
235 case isl_dim_param
: return 1;
236 case isl_dim_in
: return 1 + dim
->nparam
;
237 case isl_dim_out
: return 1 + dim
->nparam
+ dim
->n_in
;
238 case isl_dim_div
: return 1 + dim
->nparam
+ dim
->n_in
+ dim
->n_out
;
243 /* Return the position of the dimension of the given type and name
245 * Return -1 if no such dimension can be found.
247 int isl_local_space_find_dim_by_name(__isl_keep isl_local_space
*ls
,
248 enum isl_dim_type type
, const char *name
)
252 if (type
== isl_dim_div
)
254 return isl_space_find_dim_by_name(ls
->dim
, type
, name
);
257 /* Does the given dimension have a name?
259 isl_bool
isl_local_space_has_dim_name(__isl_keep isl_local_space
*ls
,
260 enum isl_dim_type type
, unsigned pos
)
262 return ls
? isl_space_has_dim_name(ls
->dim
, type
, pos
) : isl_bool_error
;
265 const char *isl_local_space_get_dim_name(__isl_keep isl_local_space
*ls
,
266 enum isl_dim_type type
, unsigned pos
)
268 return ls
? isl_space_get_dim_name(ls
->dim
, type
, pos
) : NULL
;
271 isl_bool
isl_local_space_has_dim_id(__isl_keep isl_local_space
*ls
,
272 enum isl_dim_type type
, unsigned pos
)
274 return ls
? isl_space_has_dim_id(ls
->dim
, type
, pos
) : isl_bool_error
;
277 __isl_give isl_id
*isl_local_space_get_dim_id(__isl_keep isl_local_space
*ls
,
278 enum isl_dim_type type
, unsigned pos
)
280 return ls
? isl_space_get_dim_id(ls
->dim
, type
, pos
) : NULL
;
283 /* Return the argument of the integer division at position "pos" in "ls".
284 * All local variables in "ls" are known to have a (complete) explicit
287 static __isl_give isl_aff
*extract_div(__isl_keep isl_local_space
*ls
, int pos
)
291 aff
= isl_aff_alloc(isl_local_space_copy(ls
));
294 isl_seq_cpy(aff
->v
->el
, ls
->div
->row
[pos
], aff
->v
->size
);
298 /* Return the argument of the integer division at position "pos" in "ls".
299 * The integer division at that position is known to have a complete
300 * explicit representation, but some of the others do not.
301 * Remove them first because the domain of an isl_aff
302 * is not allowed to have unknown local variables.
304 static __isl_give isl_aff
*drop_unknown_divs_and_extract_div(
305 __isl_keep isl_local_space
*ls
, int pos
)
311 ls
= isl_local_space_copy(ls
);
312 n
= isl_local_space_dim(ls
, isl_dim_div
);
313 for (i
= n
- 1; i
>= 0; --i
) {
314 unknown
= isl_local_space_div_is_marked_unknown(ls
, i
);
316 ls
= isl_local_space_free(ls
);
319 ls
= isl_local_space_drop_dims(ls
, isl_dim_div
, i
, 1);
323 aff
= extract_div(ls
, pos
);
324 isl_local_space_free(ls
);
328 /* Return the argument of the integer division at position "pos" in "ls".
329 * The integer division is assumed to have a complete explicit
330 * representation. If some of the other integer divisions
331 * do not have an explicit representation, then they need
332 * to be removed first because the domain of an isl_aff
333 * is not allowed to have unknown local variables.
335 __isl_give isl_aff
*isl_local_space_get_div(__isl_keep isl_local_space
*ls
,
343 if (pos
< 0 || pos
>= ls
->div
->n_row
)
344 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
345 "index out of bounds", return NULL
);
347 known
= isl_local_space_div_is_known(ls
, pos
);
351 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
352 "expression of div unknown", return NULL
);
353 if (!isl_local_space_is_set(ls
))
354 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
355 "cannot represent divs of map spaces", return NULL
);
357 known
= isl_local_space_divs_known(ls
);
361 return extract_div(ls
, pos
);
363 return drop_unknown_divs_and_extract_div(ls
, pos
);
366 /* Return the space of "ls".
368 __isl_keep isl_space
*isl_local_space_peek_space(__isl_keep isl_local_space
*ls
)
376 __isl_give isl_space
*isl_local_space_get_space(__isl_keep isl_local_space
*ls
)
378 return isl_space_copy(isl_local_space_peek_space(ls
));
381 /* Return the space of "ls".
382 * This may be either a copy or the space itself
383 * if there is only one reference to "ls".
384 * This allows the space to be modified inplace
385 * if both the local space and its space have only a single reference.
386 * The caller is not allowed to modify "ls" between this call and
387 * a subsequent call to isl_local_space_restore_space.
388 * The only exception is that isl_local_space_free can be called instead.
390 __isl_give isl_space
*isl_local_space_take_space(__isl_keep isl_local_space
*ls
)
397 return isl_local_space_get_space(ls
);
403 /* Set the space of "ls" to "space", where the space of "ls" may be missing
404 * due to a preceding call to isl_local_space_take_space.
405 * However, in this case, "ls" only has a single reference and
406 * then the call to isl_local_space_cow has no effect.
408 __isl_give isl_local_space
*isl_local_space_restore_space(
409 __isl_take isl_local_space
*ls
, __isl_take isl_space
*space
)
414 if (ls
->dim
== space
) {
415 isl_space_free(space
);
419 ls
= isl_local_space_cow(ls
);
422 isl_space_free(ls
->dim
);
427 isl_local_space_free(ls
);
428 isl_space_free(space
);
432 /* Replace the identifier of the tuple of type "type" by "id".
434 __isl_give isl_local_space
*isl_local_space_set_tuple_id(
435 __isl_take isl_local_space
*ls
,
436 enum isl_dim_type type
, __isl_take isl_id
*id
)
438 ls
= isl_local_space_cow(ls
);
441 ls
->dim
= isl_space_set_tuple_id(ls
->dim
, type
, id
);
443 return isl_local_space_free(ls
);
450 __isl_give isl_local_space
*isl_local_space_set_dim_name(
451 __isl_take isl_local_space
*ls
,
452 enum isl_dim_type type
, unsigned pos
, const char *s
)
454 ls
= isl_local_space_cow(ls
);
457 ls
->dim
= isl_space_set_dim_name(ls
->dim
, type
, pos
, s
);
459 return isl_local_space_free(ls
);
464 __isl_give isl_local_space
*isl_local_space_set_dim_id(
465 __isl_take isl_local_space
*ls
,
466 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
468 ls
= isl_local_space_cow(ls
);
471 ls
->dim
= isl_space_set_dim_id(ls
->dim
, type
, pos
, id
);
473 return isl_local_space_free(ls
);
481 /* Construct a zero-dimensional local space with the given parameter domain.
483 __isl_give isl_local_space
*isl_local_space_set_from_params(
484 __isl_take isl_local_space
*ls
)
488 space
= isl_local_space_take_space(ls
);
489 space
= isl_space_set_from_params(space
);
490 ls
= isl_local_space_restore_space(ls
, space
);
495 __isl_give isl_local_space
*isl_local_space_reset_space(
496 __isl_take isl_local_space
*ls
, __isl_take isl_space
*dim
)
498 ls
= isl_local_space_cow(ls
);
502 isl_space_free(ls
->dim
);
507 isl_local_space_free(ls
);
512 /* Reorder the columns of the given div definitions according to the
514 * The order of the divs themselves is assumed not to change.
516 static __isl_give isl_mat
*reorder_divs(__isl_take isl_mat
*div
,
517 __isl_take isl_reordering
*r
)
526 extra
= isl_space_dim(r
->dim
, isl_dim_all
) + div
->n_row
- r
->len
;
527 mat
= isl_mat_alloc(div
->ctx
, div
->n_row
, div
->n_col
+ extra
);
531 for (i
= 0; i
< div
->n_row
; ++i
) {
532 isl_seq_cpy(mat
->row
[i
], div
->row
[i
], 2);
533 isl_seq_clr(mat
->row
[i
] + 2, mat
->n_col
- 2);
534 for (j
= 0; j
< r
->len
; ++j
)
535 isl_int_set(mat
->row
[i
][2 + r
->pos
[j
]],
539 isl_reordering_free(r
);
543 isl_reordering_free(r
);
548 /* Reorder the dimensions of "ls" according to the given reordering.
549 * The reordering r is assumed to have been extended with the local
550 * variables, leaving them in the same order.
552 __isl_give isl_local_space
*isl_local_space_realign(
553 __isl_take isl_local_space
*ls
, __isl_take isl_reordering
*r
)
555 ls
= isl_local_space_cow(ls
);
559 ls
->div
= reorder_divs(ls
->div
, isl_reordering_copy(r
));
563 ls
= isl_local_space_reset_space(ls
, isl_space_copy(r
->dim
));
565 isl_reordering_free(r
);
568 isl_local_space_free(ls
);
569 isl_reordering_free(r
);
573 __isl_give isl_local_space
*isl_local_space_add_div(
574 __isl_take isl_local_space
*ls
, __isl_take isl_vec
*div
)
576 ls
= isl_local_space_cow(ls
);
580 if (ls
->div
->n_col
!= div
->size
)
581 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
582 "incompatible dimensions", goto error
);
584 ls
->div
= isl_mat_add_zero_cols(ls
->div
, 1);
585 ls
->div
= isl_mat_add_rows(ls
->div
, 1);
589 isl_seq_cpy(ls
->div
->row
[ls
->div
->n_row
- 1], div
->el
, div
->size
);
590 isl_int_set_si(ls
->div
->row
[ls
->div
->n_row
- 1][div
->size
], 0);
595 isl_local_space_free(ls
);
600 __isl_give isl_local_space
*isl_local_space_replace_divs(
601 __isl_take isl_local_space
*ls
, __isl_take isl_mat
*div
)
603 ls
= isl_local_space_cow(ls
);
608 isl_mat_free(ls
->div
);
613 isl_local_space_free(ls
);
617 /* Copy row "s" of "src" to row "d" of "dst", applying the expansion
620 static void expand_row(__isl_keep isl_mat
*dst
, int d
,
621 __isl_keep isl_mat
*src
, int s
, int *exp
)
624 unsigned c
= src
->n_col
- src
->n_row
;
626 isl_seq_cpy(dst
->row
[d
], src
->row
[s
], c
);
627 isl_seq_clr(dst
->row
[d
] + c
, dst
->n_col
- c
);
629 for (i
= 0; i
< s
; ++i
)
630 isl_int_set(dst
->row
[d
][c
+ exp
[i
]], src
->row
[s
][c
+ i
]);
633 /* Compare (known) divs.
634 * Return non-zero if at least one of the two divs is unknown.
635 * In particular, if both divs are unknown, we respect their
636 * current order. Otherwise, we sort the known div after the unknown
637 * div only if the known div depends on the unknown div.
639 static int cmp_row(isl_int
*row_i
, isl_int
*row_j
, int i
, int j
,
640 unsigned n_row
, unsigned n_col
)
643 int unknown_i
, unknown_j
;
645 unknown_i
= isl_int_is_zero(row_i
[0]);
646 unknown_j
= isl_int_is_zero(row_j
[0]);
648 if (unknown_i
&& unknown_j
)
652 li
= n_col
- n_row
+ i
;
654 li
= isl_seq_last_non_zero(row_i
, n_col
);
656 lj
= n_col
- n_row
+ j
;
658 lj
= isl_seq_last_non_zero(row_j
, n_col
);
663 return isl_seq_cmp(row_i
, row_j
, n_col
);
666 /* Call cmp_row for divs in a matrix.
668 int isl_mat_cmp_div(__isl_keep isl_mat
*div
, int i
, int j
)
670 return cmp_row(div
->row
[i
], div
->row
[j
], i
, j
, div
->n_row
, div
->n_col
);
673 /* Call cmp_row for divs in a basic map.
675 static int bmap_cmp_row(__isl_keep isl_basic_map
*bmap
, int i
, int j
,
678 return cmp_row(bmap
->div
[i
], bmap
->div
[j
], i
, j
, bmap
->n_div
, total
);
681 /* Sort the divs in "bmap".
683 * We first make sure divs are placed after divs on which they depend.
684 * Then we perform a simple insertion sort based on the same ordering
685 * that is used in isl_merge_divs.
687 __isl_give isl_basic_map
*isl_basic_map_sort_divs(
688 __isl_take isl_basic_map
*bmap
)
693 bmap
= isl_basic_map_order_divs(bmap
);
696 if (bmap
->n_div
<= 1)
699 total
= 2 + isl_basic_map_total_dim(bmap
);
700 for (i
= 1; i
< bmap
->n_div
; ++i
) {
701 for (j
= i
- 1; j
>= 0; --j
) {
702 if (bmap_cmp_row(bmap
, j
, j
+ 1, total
) <= 0)
704 isl_basic_map_swap_div(bmap
, j
, j
+ 1);
711 /* Sort the divs in the basic maps of "map".
713 __isl_give isl_map
*isl_map_sort_divs(__isl_take isl_map
*map
)
715 return isl_map_inline_foreach_basic_map(map
, &isl_basic_map_sort_divs
);
718 /* Combine the two lists of divs into a single list.
719 * For each row i in div1, exp1[i] is set to the position of the corresponding
720 * row in the result. Similarly for div2 and exp2.
721 * This function guarantees
723 * exp1[i+1] > exp1[i]
724 * For optimal merging, the two input list should have been sorted.
726 __isl_give isl_mat
*isl_merge_divs(__isl_keep isl_mat
*div1
,
727 __isl_keep isl_mat
*div2
, int *exp1
, int *exp2
)
736 d
= div1
->n_col
- div1
->n_row
;
737 div
= isl_mat_alloc(div1
->ctx
, 1 + div1
->n_row
+ div2
->n_row
,
738 d
+ div1
->n_row
+ div2
->n_row
);
742 for (i
= 0, j
= 0, k
= 0; i
< div1
->n_row
&& j
< div2
->n_row
; ++k
) {
745 expand_row(div
, k
, div1
, i
, exp1
);
746 expand_row(div
, k
+ 1, div2
, j
, exp2
);
748 cmp
= isl_mat_cmp_div(div
, k
, k
+ 1);
752 } else if (cmp
< 0) {
756 isl_seq_cpy(div
->row
[k
], div
->row
[k
+ 1], div
->n_col
);
759 for (; i
< div1
->n_row
; ++i
, ++k
) {
760 expand_row(div
, k
, div1
, i
, exp1
);
763 for (; j
< div2
->n_row
; ++j
, ++k
) {
764 expand_row(div
, k
, div2
, j
, exp2
);
774 /* Swap divs "a" and "b" in "ls".
776 __isl_give isl_local_space
*isl_local_space_swap_div(
777 __isl_take isl_local_space
*ls
, int a
, int b
)
781 ls
= isl_local_space_cow(ls
);
784 if (a
< 0 || a
>= ls
->div
->n_row
|| b
< 0 || b
>= ls
->div
->n_row
)
785 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
786 "index out of bounds", return isl_local_space_free(ls
));
787 offset
= ls
->div
->n_col
- ls
->div
->n_row
;
788 ls
->div
= isl_mat_swap_cols(ls
->div
, offset
+ a
, offset
+ b
);
789 ls
->div
= isl_mat_swap_rows(ls
->div
, a
, b
);
791 return isl_local_space_free(ls
);
795 /* Construct a local space that contains all the divs in either
798 __isl_give isl_local_space
*isl_local_space_intersect(
799 __isl_take isl_local_space
*ls1
, __isl_take isl_local_space
*ls2
)
810 ctx
= isl_local_space_get_ctx(ls1
);
811 if (!isl_space_is_equal(ls1
->dim
, ls2
->dim
))
812 isl_die(ctx
, isl_error_invalid
,
813 "spaces should be identical", goto error
);
815 if (ls2
->div
->n_row
== 0) {
816 isl_local_space_free(ls2
);
820 if (ls1
->div
->n_row
== 0) {
821 isl_local_space_free(ls1
);
825 exp1
= isl_alloc_array(ctx
, int, ls1
->div
->n_row
);
826 exp2
= isl_alloc_array(ctx
, int, ls2
->div
->n_row
);
830 div
= isl_merge_divs(ls1
->div
, ls2
->div
, exp1
, exp2
);
834 equal
= isl_mat_is_equal(ls1
->div
, div
);
838 ls1
= isl_local_space_cow(ls1
);
844 isl_local_space_free(ls2
);
845 isl_mat_free(ls1
->div
);
853 isl_local_space_free(ls1
);
854 isl_local_space_free(ls2
);
858 /* Is the local variable "div" of "ls" marked as not having
859 * an explicit representation?
860 * Note that even if this variable is not marked in this way and therefore
861 * does have an explicit representation, this representation may still
862 * depend (indirectly) on other local variables that do not
863 * have an explicit representation.
865 isl_bool
isl_local_space_div_is_marked_unknown(__isl_keep isl_local_space
*ls
,
869 return isl_bool_error
;
870 return isl_local_div_is_marked_unknown(ls
->div
, div
);
873 /* Does "ls" have a complete explicit representation for div "div"?
875 isl_bool
isl_local_space_div_is_known(__isl_keep isl_local_space
*ls
, int div
)
878 return isl_bool_error
;
879 return isl_local_div_is_known(ls
->div
, div
);
882 /* Does "ls" have an explicit representation for all local variables?
884 isl_bool
isl_local_space_divs_known(__isl_keep isl_local_space
*ls
)
887 return isl_bool_error
;
888 return isl_local_divs_known(ls
->div
);
891 __isl_give isl_local_space
*isl_local_space_domain(
892 __isl_take isl_local_space
*ls
)
894 ls
= isl_local_space_drop_dims(ls
, isl_dim_out
,
895 0, isl_local_space_dim(ls
, isl_dim_out
));
896 ls
= isl_local_space_cow(ls
);
899 ls
->dim
= isl_space_domain(ls
->dim
);
901 return isl_local_space_free(ls
);
905 __isl_give isl_local_space
*isl_local_space_range(
906 __isl_take isl_local_space
*ls
)
908 ls
= isl_local_space_drop_dims(ls
, isl_dim_in
,
909 0, isl_local_space_dim(ls
, isl_dim_in
));
910 ls
= isl_local_space_cow(ls
);
914 ls
->dim
= isl_space_range(ls
->dim
);
916 return isl_local_space_free(ls
);
920 /* Construct a local space for a map that has the given local
921 * space as domain and that has a zero-dimensional range.
923 __isl_give isl_local_space
*isl_local_space_from_domain(
924 __isl_take isl_local_space
*ls
)
926 ls
= isl_local_space_cow(ls
);
929 ls
->dim
= isl_space_from_domain(ls
->dim
);
931 return isl_local_space_free(ls
);
935 __isl_give isl_local_space
*isl_local_space_add_dims(
936 __isl_take isl_local_space
*ls
, enum isl_dim_type type
, unsigned n
)
942 pos
= isl_local_space_dim(ls
, type
);
943 return isl_local_space_insert_dims(ls
, type
, pos
, n
);
946 /* Remove common factor of non-constant terms and denominator.
948 static void normalize_div(__isl_keep isl_local_space
*ls
, int div
)
950 isl_ctx
*ctx
= ls
->div
->ctx
;
951 unsigned total
= ls
->div
->n_col
- 2;
953 isl_seq_gcd(ls
->div
->row
[div
] + 2, total
, &ctx
->normalize_gcd
);
954 isl_int_gcd(ctx
->normalize_gcd
,
955 ctx
->normalize_gcd
, ls
->div
->row
[div
][0]);
956 if (isl_int_is_one(ctx
->normalize_gcd
))
959 isl_seq_scale_down(ls
->div
->row
[div
] + 2, ls
->div
->row
[div
] + 2,
960 ctx
->normalize_gcd
, total
);
961 isl_int_divexact(ls
->div
->row
[div
][0], ls
->div
->row
[div
][0],
963 isl_int_fdiv_q(ls
->div
->row
[div
][1], ls
->div
->row
[div
][1],
967 /* Exploit the equalities in "eq" to simplify the expressions of
968 * the integer divisions in "ls".
969 * The integer divisions in "ls" are assumed to appear as regular
970 * dimensions in "eq".
972 __isl_give isl_local_space
*isl_local_space_substitute_equalities(
973 __isl_take isl_local_space
*ls
, __isl_take isl_basic_set
*eq
)
982 total
= isl_space_dim(eq
->dim
, isl_dim_all
);
983 if (isl_local_space_dim(ls
, isl_dim_all
) != total
)
984 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
985 "spaces don't match", goto error
);
988 for (i
= 0; i
< eq
->n_eq
; ++i
) {
989 j
= isl_seq_last_non_zero(eq
->eq
[i
], total
+ n_div
);
990 if (j
< 0 || j
== 0 || j
>= total
)
993 for (k
= 0; k
< ls
->div
->n_row
; ++k
) {
994 if (isl_int_is_zero(ls
->div
->row
[k
][1 + j
]))
996 ls
= isl_local_space_cow(ls
);
999 ls
->div
= isl_mat_cow(ls
->div
);
1002 isl_seq_elim(ls
->div
->row
[k
] + 1, eq
->eq
[i
], j
, total
,
1003 &ls
->div
->row
[k
][0]);
1004 normalize_div(ls
, k
);
1008 isl_basic_set_free(eq
);
1011 isl_basic_set_free(eq
);
1012 isl_local_space_free(ls
);
1016 /* Plug in the affine expressions "subs" of length "subs_len" (including
1017 * the denominator and the constant term) into the variable at position "pos"
1018 * of the "n" div expressions starting at "first".
1020 * Let i be the dimension to replace and let "subs" be of the form
1024 * Any integer division starting at "first" with a non-zero coefficient for i,
1026 * floor((a i + g)/m)
1030 * floor((a f + d g)/(m d))
1032 __isl_give isl_local_space
*isl_local_space_substitute_seq(
1033 __isl_take isl_local_space
*ls
,
1034 enum isl_dim_type type
, unsigned pos
, isl_int
*subs
, int subs_len
,
1042 ls
= isl_local_space_cow(ls
);
1045 ls
->div
= isl_mat_cow(ls
->div
);
1047 return isl_local_space_free(ls
);
1049 if (first
+ n
> ls
->div
->n_row
)
1050 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
1051 "index out of bounds", return isl_local_space_free(ls
));
1053 pos
+= isl_local_space_offset(ls
, type
);
1056 for (i
= first
; i
< first
+ n
; ++i
) {
1057 if (isl_int_is_zero(ls
->div
->row
[i
][1 + pos
]))
1059 isl_seq_substitute(ls
->div
->row
[i
], pos
, subs
,
1060 ls
->div
->n_col
, subs_len
, v
);
1061 normalize_div(ls
, i
);
1068 /* Plug in "subs" for dimension "type", "pos" in the integer divisions
1071 * Let i be the dimension to replace and let "subs" be of the form
1075 * Any integer division with a non-zero coefficient for i,
1077 * floor((a i + g)/m)
1081 * floor((a f + d g)/(m d))
1083 __isl_give isl_local_space
*isl_local_space_substitute(
1084 __isl_take isl_local_space
*ls
,
1085 enum isl_dim_type type
, unsigned pos
, __isl_keep isl_aff
*subs
)
1087 ls
= isl_local_space_cow(ls
);
1089 return isl_local_space_free(ls
);
1091 if (!isl_space_is_equal(ls
->dim
, subs
->ls
->dim
))
1092 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
1093 "spaces don't match", return isl_local_space_free(ls
));
1094 if (isl_local_space_dim(subs
->ls
, isl_dim_div
) != 0)
1095 isl_die(isl_local_space_get_ctx(ls
), isl_error_unsupported
,
1096 "cannot handle divs yet",
1097 return isl_local_space_free(ls
));
1099 return isl_local_space_substitute_seq(ls
, type
, pos
, subs
->v
->el
,
1100 subs
->v
->size
, 0, ls
->div
->n_row
);
1103 isl_bool
isl_local_space_is_named_or_nested(__isl_keep isl_local_space
*ls
,
1104 enum isl_dim_type type
)
1107 return isl_bool_error
;
1108 return isl_space_is_named_or_nested(ls
->dim
, type
);
1111 __isl_give isl_local_space
*isl_local_space_drop_dims(
1112 __isl_take isl_local_space
*ls
,
1113 enum isl_dim_type type
, unsigned first
, unsigned n
)
1119 if (n
== 0 && !isl_local_space_is_named_or_nested(ls
, type
))
1122 ctx
= isl_local_space_get_ctx(ls
);
1123 if (first
+ n
> isl_local_space_dim(ls
, type
))
1124 isl_die(ctx
, isl_error_invalid
, "range out of bounds",
1125 return isl_local_space_free(ls
));
1127 ls
= isl_local_space_cow(ls
);
1131 if (type
== isl_dim_div
) {
1132 ls
->div
= isl_mat_drop_rows(ls
->div
, first
, n
);
1134 ls
->dim
= isl_space_drop_dims(ls
->dim
, type
, first
, n
);
1136 return isl_local_space_free(ls
);
1139 first
+= 1 + isl_local_space_offset(ls
, type
);
1140 ls
->div
= isl_mat_drop_cols(ls
->div
, first
, n
);
1142 return isl_local_space_free(ls
);
1147 __isl_give isl_local_space
*isl_local_space_insert_dims(
1148 __isl_take isl_local_space
*ls
,
1149 enum isl_dim_type type
, unsigned first
, unsigned n
)
1155 if (n
== 0 && !isl_local_space_is_named_or_nested(ls
, type
))
1158 ctx
= isl_local_space_get_ctx(ls
);
1159 if (first
> isl_local_space_dim(ls
, type
))
1160 isl_die(ctx
, isl_error_invalid
, "position out of bounds",
1161 return isl_local_space_free(ls
));
1163 ls
= isl_local_space_cow(ls
);
1167 if (type
== isl_dim_div
) {
1168 ls
->div
= isl_mat_insert_zero_rows(ls
->div
, first
, n
);
1170 ls
->dim
= isl_space_insert_dims(ls
->dim
, type
, first
, n
);
1172 return isl_local_space_free(ls
);
1175 first
+= 1 + isl_local_space_offset(ls
, type
);
1176 ls
->div
= isl_mat_insert_zero_cols(ls
->div
, first
, n
);
1178 return isl_local_space_free(ls
);
1183 /* Check if the constraints pointed to by "constraint" is a div
1184 * constraint corresponding to div "div" in "ls".
1186 * That is, if div = floor(f/m), then check if the constraint is
1190 * -(f-(m-1)) + m d >= 0
1192 isl_bool
isl_local_space_is_div_constraint(__isl_keep isl_local_space
*ls
,
1193 isl_int
*constraint
, unsigned div
)
1198 return isl_bool_error
;
1200 if (isl_int_is_zero(ls
->div
->row
[div
][0]))
1201 return isl_bool_false
;
1203 pos
= isl_local_space_offset(ls
, isl_dim_div
) + div
;
1205 if (isl_int_eq(constraint
[pos
], ls
->div
->row
[div
][0])) {
1207 isl_int_sub(ls
->div
->row
[div
][1],
1208 ls
->div
->row
[div
][1], ls
->div
->row
[div
][0]);
1209 isl_int_add_ui(ls
->div
->row
[div
][1], ls
->div
->row
[div
][1], 1);
1210 neg
= isl_seq_is_neg(constraint
, ls
->div
->row
[div
]+1, pos
);
1211 isl_int_sub_ui(ls
->div
->row
[div
][1], ls
->div
->row
[div
][1], 1);
1212 isl_int_add(ls
->div
->row
[div
][1],
1213 ls
->div
->row
[div
][1], ls
->div
->row
[div
][0]);
1215 return isl_bool_false
;
1216 if (isl_seq_first_non_zero(constraint
+pos
+1,
1217 ls
->div
->n_row
-div
-1) != -1)
1218 return isl_bool_false
;
1219 } else if (isl_int_abs_eq(constraint
[pos
], ls
->div
->row
[div
][0])) {
1220 if (!isl_seq_eq(constraint
, ls
->div
->row
[div
]+1, pos
))
1221 return isl_bool_false
;
1222 if (isl_seq_first_non_zero(constraint
+pos
+1,
1223 ls
->div
->n_row
-div
-1) != -1)
1224 return isl_bool_false
;
1226 return isl_bool_false
;
1228 return isl_bool_true
;
1232 * Set active[i] to 1 if the dimension at position i is involved
1233 * in the linear expression l.
1235 int *isl_local_space_get_active(__isl_keep isl_local_space
*ls
, isl_int
*l
)
1243 ctx
= isl_local_space_get_ctx(ls
);
1244 total
= isl_local_space_dim(ls
, isl_dim_all
);
1245 active
= isl_calloc_array(ctx
, int, total
);
1246 if (total
&& !active
)
1249 for (i
= 0; i
< total
; ++i
)
1250 active
[i
] = !isl_int_is_zero(l
[i
]);
1252 offset
= isl_local_space_offset(ls
, isl_dim_div
) - 1;
1253 for (i
= ls
->div
->n_row
- 1; i
>= 0; --i
) {
1254 if (!active
[offset
+ i
])
1256 for (j
= 0; j
< total
; ++j
)
1257 active
[j
] |= !isl_int_is_zero(ls
->div
->row
[i
][2 + j
]);
1263 /* Given a local space "ls" of a set, create a local space
1264 * for the lift of the set. In particular, the result
1265 * is of the form [dim -> local[..]], with ls->div->n_row variables in the
1266 * range of the wrapped map.
1268 __isl_give isl_local_space
*isl_local_space_lift(
1269 __isl_take isl_local_space
*ls
)
1271 ls
= isl_local_space_cow(ls
);
1275 ls
->dim
= isl_space_lift(ls
->dim
, ls
->div
->n_row
);
1276 ls
->div
= isl_mat_drop_rows(ls
->div
, 0, ls
->div
->n_row
);
1277 if (!ls
->dim
|| !ls
->div
)
1278 return isl_local_space_free(ls
);
1283 /* Construct a basic map that maps a set living in local space "ls"
1284 * to the corresponding lifted local space.
1286 __isl_give isl_basic_map
*isl_local_space_lifting(
1287 __isl_take isl_local_space
*ls
)
1289 isl_basic_map
*lifting
;
1290 isl_basic_set
*bset
;
1294 if (!isl_local_space_is_set(ls
))
1295 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
1296 "lifting only defined on set spaces", goto error
);
1298 bset
= isl_basic_set_from_local_space(ls
);
1299 lifting
= isl_basic_set_unwrap(isl_basic_set_lift(bset
));
1300 lifting
= isl_basic_map_domain_map(lifting
);
1301 lifting
= isl_basic_map_reverse(lifting
);
1305 isl_local_space_free(ls
);
1309 /* Compute the preimage of "ls" under the function represented by "ma".
1310 * In other words, plug in "ma" in "ls". The result is a local space
1311 * that is part of the domain space of "ma".
1313 * If the divs in "ls" are represented as
1315 * floor((a_i(p) + b_i x + c_i(divs))/n_i)
1317 * and ma is represented by
1319 * x = D(p) + F(y) + G(divs')
1321 * then the resulting divs are
1323 * floor((a_i(p) + b_i D(p) + b_i F(y) + B_i G(divs') + c_i(divs))/n_i)
1325 * We first copy over the divs from "ma" and then
1326 * we add the modified divs from "ls".
1328 __isl_give isl_local_space
*isl_local_space_preimage_multi_aff(
1329 __isl_take isl_local_space
*ls
, __isl_take isl_multi_aff
*ma
)
1333 isl_local_space
*res
= NULL
;
1334 int n_div_ls
, n_div_ma
;
1335 isl_int f
, c1
, c2
, g
;
1337 ma
= isl_multi_aff_align_divs(ma
);
1340 if (!isl_space_is_range_internal(ls
->dim
, ma
->space
))
1341 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
1342 "spaces don't match", goto error
);
1344 n_div_ls
= isl_local_space_dim(ls
, isl_dim_div
);
1345 n_div_ma
= ma
->n
? isl_aff_dim(ma
->u
.p
[0], isl_dim_div
) : 0;
1347 space
= isl_space_domain(isl_multi_aff_get_space(ma
));
1348 res
= isl_local_space_alloc(space
, n_div_ma
+ n_div_ls
);
1353 isl_mat_free(res
->div
);
1354 res
->div
= isl_mat_copy(ma
->u
.p
[0]->ls
->div
);
1355 res
->div
= isl_mat_add_zero_cols(res
->div
, n_div_ls
);
1356 res
->div
= isl_mat_add_rows(res
->div
, n_div_ls
);
1366 for (i
= 0; i
< ls
->div
->n_row
; ++i
) {
1367 if (isl_int_is_zero(ls
->div
->row
[i
][0])) {
1368 isl_int_set_si(res
->div
->row
[n_div_ma
+ i
][0], 0);
1371 isl_seq_preimage(res
->div
->row
[n_div_ma
+ i
], ls
->div
->row
[i
],
1372 ma
, 0, 0, n_div_ma
, n_div_ls
, f
, c1
, c2
, g
, 1);
1373 normalize_div(res
, n_div_ma
+ i
);
1381 isl_local_space_free(ls
);
1382 isl_multi_aff_free(ma
);
1385 isl_local_space_free(ls
);
1386 isl_multi_aff_free(ma
);
1387 isl_local_space_free(res
);
1391 /* Move the "n" dimensions of "src_type" starting at "src_pos" of "ls"
1392 * to dimensions of "dst_type" at "dst_pos".
1394 * Moving to/from local dimensions is not allowed.
1395 * We currently assume that the dimension type changes.
1397 __isl_give isl_local_space
*isl_local_space_move_dims(
1398 __isl_take isl_local_space
*ls
,
1399 enum isl_dim_type dst_type
, unsigned dst_pos
,
1400 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1408 !isl_local_space_is_named_or_nested(ls
, src_type
) &&
1409 !isl_local_space_is_named_or_nested(ls
, dst_type
))
1412 if (src_pos
+ n
> isl_local_space_dim(ls
, src_type
))
1413 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
1414 "range out of bounds", return isl_local_space_free(ls
));
1415 if (dst_pos
> isl_local_space_dim(ls
, dst_type
))
1416 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
1417 "position out of bounds",
1418 return isl_local_space_free(ls
));
1419 if (src_type
== isl_dim_div
)
1420 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
1421 "cannot move divs", return isl_local_space_free(ls
));
1422 if (dst_type
== isl_dim_div
)
1423 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
1424 "cannot move to divs", return isl_local_space_free(ls
));
1425 if (dst_type
== src_type
&& dst_pos
== src_pos
)
1427 if (dst_type
== src_type
)
1428 isl_die(isl_local_space_get_ctx(ls
), isl_error_unsupported
,
1429 "moving dims within the same type not supported",
1430 return isl_local_space_free(ls
));
1432 ls
= isl_local_space_cow(ls
);
1436 g_src_pos
= 1 + isl_local_space_offset(ls
, src_type
) + src_pos
;
1437 g_dst_pos
= 1 + isl_local_space_offset(ls
, dst_type
) + dst_pos
;
1438 if (dst_type
> src_type
)
1440 ls
->div
= isl_mat_move_cols(ls
->div
, g_dst_pos
, g_src_pos
, n
);
1442 return isl_local_space_free(ls
);
1443 ls
->dim
= isl_space_move_dims(ls
->dim
, dst_type
, dst_pos
,
1444 src_type
, src_pos
, n
);
1446 return isl_local_space_free(ls
);
1451 /* Remove any internal structure of the domain of "ls".
1452 * If there is any such internal structure in the input,
1453 * then the name of the corresponding space is also removed.
1455 __isl_give isl_local_space
*isl_local_space_flatten_domain(
1456 __isl_take isl_local_space
*ls
)
1461 if (!ls
->dim
->nested
[0])
1464 ls
= isl_local_space_cow(ls
);
1468 ls
->dim
= isl_space_flatten_domain(ls
->dim
);
1470 return isl_local_space_free(ls
);
1475 /* Remove any internal structure of the range of "ls".
1476 * If there is any such internal structure in the input,
1477 * then the name of the corresponding space is also removed.
1479 __isl_give isl_local_space
*isl_local_space_flatten_range(
1480 __isl_take isl_local_space
*ls
)
1485 if (!ls
->dim
->nested
[1])
1488 ls
= isl_local_space_cow(ls
);
1492 ls
->dim
= isl_space_flatten_range(ls
->dim
);
1494 return isl_local_space_free(ls
);
1499 /* Given the local space "ls" of a map, return the local space of a set
1500 * that lives in a space that wraps the space of "ls" and that has
1503 __isl_give isl_local_space
*isl_local_space_wrap(__isl_take isl_local_space
*ls
)
1505 ls
= isl_local_space_cow(ls
);
1509 ls
->dim
= isl_space_wrap(ls
->dim
);
1511 return isl_local_space_free(ls
);