2 * Copyright 2011 INRIA Saclay
4 * Use of this software is governed by the GNU LGPLv2.1 license
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11 #include <isl_ctx_private.h>
12 #include <isl_map_private.h>
13 #include <isl_local_space_private.h>
14 #include <isl_dim_private.h>
15 #include <isl_mat_private.h>
18 isl_ctx
*isl_local_space_get_ctx(__isl_keep isl_local_space
*ls
)
20 return ls
? ls
->dim
->ctx
: NULL
;
23 __isl_give isl_local_space
*isl_local_space_alloc_div(__isl_take isl_dim
*dim
,
24 __isl_take isl_mat
*div
)
27 isl_local_space
*ls
= NULL
;
32 ctx
= isl_dim_get_ctx(dim
);
33 ls
= isl_calloc_type(ctx
, struct isl_local_space
);
44 isl_local_space_free(ls
);
48 __isl_give isl_local_space
*isl_local_space_alloc(__isl_take isl_dim
*dim
,
58 total
= isl_dim_total(dim
);
60 ctx
= isl_dim_get_ctx(dim
);
61 div
= isl_mat_alloc(ctx
, n_div
, 1 + 1 + total
+ n_div
);
62 return isl_local_space_alloc_div(dim
, div
);
65 __isl_give isl_local_space
*isl_local_space_from_dim(__isl_take isl_dim
*dim
)
67 return isl_local_space_alloc(dim
, 0);
70 __isl_give isl_local_space
*isl_local_space_copy(__isl_keep isl_local_space
*ls
)
79 __isl_give isl_local_space
*isl_local_space_dup(__isl_keep isl_local_space
*ls
)
84 return isl_local_space_alloc_div(isl_dim_copy(ls
->dim
),
85 isl_mat_copy(ls
->div
));
89 __isl_give isl_local_space
*isl_local_space_cow(__isl_take isl_local_space
*ls
)
97 return isl_local_space_dup(ls
);
100 void *isl_local_space_free(__isl_take isl_local_space
*ls
)
108 isl_dim_free(ls
->dim
);
109 isl_mat_free(ls
->div
);
116 /* Return true if the two local spaces are identical, with identical
117 * expressions for the integer divisions.
119 int isl_local_space_is_equal(__isl_keep isl_local_space
*ls1
,
120 __isl_keep isl_local_space
*ls2
)
127 equal
= isl_dim_equal(ls1
->dim
, ls2
->dim
);
128 if (equal
< 0 || !equal
)
131 if (!isl_local_space_divs_known(ls1
))
133 if (!isl_local_space_divs_known(ls2
))
136 return isl_mat_is_equal(ls1
->div
, ls2
->div
);
139 int isl_local_space_dim(__isl_keep isl_local_space
*ls
,
140 enum isl_dim_type type
)
144 if (type
== isl_dim_div
)
145 return ls
->div
->n_row
;
146 if (type
== isl_dim_all
)
147 return isl_dim_size(ls
->dim
, isl_dim_all
) + ls
->div
->n_row
;
148 return isl_dim_size(ls
->dim
, type
);
151 unsigned isl_local_space_offset(__isl_keep isl_local_space
*ls
,
152 enum isl_dim_type type
)
161 case isl_dim_cst
: return 0;
162 case isl_dim_param
: return 1;
163 case isl_dim_in
: return 1 + dim
->nparam
;
164 case isl_dim_out
: return 1 + dim
->nparam
+ dim
->n_in
;
165 case isl_dim_div
: return 1 + dim
->nparam
+ dim
->n_in
+ dim
->n_out
;
170 const char *isl_local_space_get_dim_name(__isl_keep isl_local_space
*ls
,
171 enum isl_dim_type type
, unsigned pos
)
173 return ls
? isl_dim_get_name(ls
->dim
, type
, pos
) : NULL
;
176 __isl_give isl_div
*isl_local_space_get_div(__isl_keep isl_local_space
*ls
,
184 if (pos
< 0 || pos
>= ls
->div
->n_row
)
185 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
186 "index out of bounds", return NULL
);
188 if (isl_int_is_zero(ls
->div
->row
[pos
][0]))
189 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
190 "expression of div unknown", return NULL
);
192 bmap
= isl_basic_map_from_local_space(isl_local_space_copy(ls
));
193 return isl_basic_map_div(bmap
, pos
);
196 __isl_give isl_dim
*isl_local_space_get_dim(__isl_keep isl_local_space
*ls
)
201 return isl_dim_copy(ls
->dim
);
204 __isl_give isl_local_space
*isl_local_space_set_dim_name(
205 __isl_take isl_local_space
*ls
,
206 enum isl_dim_type type
, unsigned pos
, const char *s
)
208 ls
= isl_local_space_cow(ls
);
211 ls
->dim
= isl_dim_set_name(ls
->dim
, type
, pos
, s
);
213 return isl_local_space_free(ls
);
218 __isl_give isl_local_space
*isl_local_space_reset_dim(
219 __isl_take isl_local_space
*ls
, __isl_take isl_dim
*dim
)
221 ls
= isl_local_space_cow(ls
);
225 isl_dim_free(ls
->dim
);
230 isl_local_space_free(ls
);
235 __isl_give isl_local_space
*isl_local_space_add_div(
236 __isl_take isl_local_space
*ls
, __isl_take isl_vec
*div
)
238 ls
= isl_local_space_cow(ls
);
242 if (ls
->div
->n_col
!= div
->size
)
243 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
244 "incompatible dimensions", goto error
);
246 ls
->div
= isl_mat_add_zero_cols(ls
->div
, 1);
247 ls
->div
= isl_mat_add_rows(ls
->div
, 1);
251 isl_seq_cpy(ls
->div
->row
[ls
->div
->n_row
- 1], div
->el
, div
->size
);
252 isl_int_set_si(ls
->div
->row
[ls
->div
->n_row
- 1][div
->size
], 0);
257 isl_local_space_free(ls
);
262 __isl_give isl_local_space
*isl_local_space_replace_divs(
263 __isl_take isl_local_space
*ls
, __isl_take isl_mat
*div
)
265 ls
= isl_local_space_cow(ls
);
270 isl_mat_free(ls
->div
);
275 isl_local_space_free(ls
);
279 /* Copy row "s" of "src" to row "d" of "dst", applying the expansion
282 static void expand_row(__isl_keep isl_mat
*dst
, int d
,
283 __isl_keep isl_mat
*src
, int s
, int *exp
)
286 unsigned c
= src
->n_col
- src
->n_row
;
288 isl_seq_cpy(dst
->row
[d
], src
->row
[s
], c
);
289 isl_seq_clr(dst
->row
[d
] + c
, dst
->n_col
- c
);
291 for (i
= 0; i
< s
; ++i
)
292 isl_int_set(dst
->row
[d
][c
+ exp
[i
]], src
->row
[s
][c
+ i
]);
295 /* Compare (known) divs.
296 * Return non-zero if at least one of the two divs is unknown.
298 static int cmp_row(__isl_keep isl_mat
*div
, int i
, int j
)
302 if (isl_int_is_zero(div
->row
[j
][0]))
304 if (isl_int_is_zero(div
->row
[i
][0]))
307 li
= isl_seq_last_non_zero(div
->row
[i
], div
->n_col
);
308 lj
= isl_seq_last_non_zero(div
->row
[j
], div
->n_col
);
313 return isl_seq_cmp(div
->row
[i
], div
->row
[j
], div
->n_col
);
316 /* Combine the two lists of divs into a single list.
317 * For each row i in div1, exp1[i] is set to the position of the corresponding
318 * row in the result. Similarly for div2 and exp2.
319 * This function guarantees
321 * exp1[i+1] > exp1[i]
322 * For optimal merging, the two input list should have been sorted.
324 __isl_give isl_mat
*isl_merge_divs(__isl_keep isl_mat
*div1
,
325 __isl_keep isl_mat
*div2
, int *exp1
, int *exp2
)
329 unsigned d
= div1
->n_col
- div1
->n_row
;
331 div
= isl_mat_alloc(div1
->ctx
, 1 + div1
->n_row
+ div2
->n_row
,
332 d
+ div1
->n_row
+ div2
->n_row
);
336 for (i
= 0, j
= 0, k
= 0; i
< div1
->n_row
&& j
< div2
->n_row
; ++k
) {
339 expand_row(div
, k
, div1
, i
, exp1
);
340 expand_row(div
, k
+ 1, div2
, j
, exp2
);
342 cmp
= cmp_row(div
, k
, k
+ 1);
346 } else if (cmp
< 0) {
350 isl_seq_cpy(div
->row
[k
], div
->row
[k
+ 1], div
->n_col
);
353 for (; i
< div1
->n_row
; ++i
, ++k
) {
354 expand_row(div
, k
, div1
, i
, exp1
);
357 for (; j
< div2
->n_row
; ++j
, ++k
) {
358 expand_row(div
, k
, div2
, j
, exp2
);
368 int isl_local_space_divs_known(__isl_keep isl_local_space
*ls
)
375 for (i
= 0; i
< ls
->div
->n_row
; ++i
)
376 if (isl_int_is_zero(ls
->div
->row
[i
][0]))
382 /* Construct a local space for a map that has the given local
383 * space as domain and that has a zero-dimensional range.
385 __isl_give isl_local_space
*isl_local_space_from_domain(
386 __isl_take isl_local_space
*ls
)
388 ls
= isl_local_space_cow(ls
);
391 ls
->dim
= isl_dim_from_domain(ls
->dim
);
393 return isl_local_space_free(ls
);
397 __isl_give isl_local_space
*isl_local_space_add_dims(
398 __isl_take isl_local_space
*ls
, enum isl_dim_type type
, unsigned n
)
404 pos
= isl_local_space_dim(ls
, type
);
405 return isl_local_space_insert_dims(ls
, type
, pos
, n
);
408 /* Remove common factor of non-constant terms and denominator.
410 static void normalize_div(__isl_keep isl_local_space
*ls
, int div
)
412 isl_ctx
*ctx
= ls
->div
->ctx
;
413 unsigned total
= ls
->div
->n_col
- 2;
415 isl_seq_gcd(ls
->div
->row
[div
] + 2, total
, &ctx
->normalize_gcd
);
416 isl_int_gcd(ctx
->normalize_gcd
,
417 ctx
->normalize_gcd
, ls
->div
->row
[div
][0]);
418 if (isl_int_is_one(ctx
->normalize_gcd
))
421 isl_seq_scale_down(ls
->div
->row
[div
] + 2, ls
->div
->row
[div
] + 2,
422 ctx
->normalize_gcd
, total
);
423 isl_int_divexact(ls
->div
->row
[div
][0], ls
->div
->row
[div
][0],
425 isl_int_fdiv_q(ls
->div
->row
[div
][1], ls
->div
->row
[div
][1],
429 /* Exploit the equalities in "eq" to simplify the expressions of
430 * the integer divisions in "ls".
431 * The integer divisions in "ls" are assumed to appear as regular
432 * dimensions in "eq".
434 __isl_give isl_local_space
*isl_local_space_substitute_equalities(
435 __isl_take isl_local_space
*ls
, __isl_take isl_basic_set
*eq
)
441 ls
= isl_local_space_cow(ls
);
445 total
= isl_dim_total(eq
->dim
);
446 if (isl_local_space_dim(ls
, isl_dim_all
) != total
)
447 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
448 "dimensions don't match", goto error
);
451 for (i
= 0; i
< eq
->n_eq
; ++i
) {
452 j
= isl_seq_last_non_zero(eq
->eq
[i
], total
+ n_div
);
453 if (j
< 0 || j
== 0 || j
>= total
)
456 for (k
= 0; k
< ls
->div
->n_row
; ++k
) {
457 if (isl_int_is_zero(ls
->div
->row
[k
][1 + j
]))
459 isl_seq_elim(ls
->div
->row
[k
] + 1, eq
->eq
[i
], j
, total
,
460 &ls
->div
->row
[k
][0]);
461 normalize_div(ls
, k
);
465 isl_basic_set_free(eq
);
468 isl_basic_set_free(eq
);
469 isl_local_space_free(ls
);
473 int isl_local_space_is_named_or_nested(__isl_keep isl_local_space
*ls
,
474 enum isl_dim_type type
)
478 return isl_dim_is_named_or_nested(ls
->dim
, type
);
481 __isl_give isl_local_space
*isl_local_space_drop_dims(
482 __isl_take isl_local_space
*ls
,
483 enum isl_dim_type type
, unsigned first
, unsigned n
)
489 if (n
== 0 && !isl_local_space_is_named_or_nested(ls
, type
))
492 ctx
= isl_local_space_get_ctx(ls
);
493 if (first
+ n
> isl_local_space_dim(ls
, type
))
494 isl_die(ctx
, isl_error_invalid
, "range out of bounds",
495 return isl_local_space_free(ls
));
497 ls
= isl_local_space_cow(ls
);
501 if (type
== isl_dim_div
) {
502 ls
->div
= isl_mat_drop_rows(ls
->div
, first
, n
);
504 ls
->dim
= isl_dim_drop(ls
->dim
, type
, first
, n
);
506 return isl_local_space_free(ls
);
509 first
+= 1 + isl_local_space_offset(ls
, type
);
510 ls
->div
= isl_mat_drop_cols(ls
->div
, first
, n
);
512 return isl_local_space_free(ls
);
517 __isl_give isl_local_space
*isl_local_space_insert_dims(
518 __isl_take isl_local_space
*ls
,
519 enum isl_dim_type type
, unsigned first
, unsigned n
)
525 if (n
== 0 && !isl_local_space_is_named_or_nested(ls
, type
))
528 ctx
= isl_local_space_get_ctx(ls
);
529 if (first
> isl_local_space_dim(ls
, type
))
530 isl_die(ctx
, isl_error_invalid
, "position out of bounds",
531 return isl_local_space_free(ls
));
533 ls
= isl_local_space_cow(ls
);
537 if (type
== isl_dim_div
) {
538 ls
->div
= isl_mat_insert_zero_rows(ls
->div
, first
, n
);
540 ls
->dim
= isl_dim_insert(ls
->dim
, type
, first
, n
);
542 return isl_local_space_free(ls
);
545 first
+= 1 + isl_local_space_offset(ls
, type
);
546 ls
->div
= isl_mat_insert_zero_cols(ls
->div
, first
, n
);
548 return isl_local_space_free(ls
);