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_add_div(
219 __isl_take isl_local_space
*ls
, __isl_take isl_vec
*div
)
221 ls
= isl_local_space_cow(ls
);
225 if (ls
->div
->n_col
!= div
->size
)
226 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
227 "incompatible dimensions", goto error
);
229 ls
->div
= isl_mat_add_zero_cols(ls
->div
, 1);
230 ls
->div
= isl_mat_add_rows(ls
->div
, 1);
234 isl_seq_cpy(ls
->div
->row
[ls
->div
->n_row
- 1], div
->el
, div
->size
);
235 isl_int_set_si(ls
->div
->row
[ls
->div
->n_row
- 1][div
->size
], 0);
240 isl_local_space_free(ls
);
245 __isl_give isl_local_space
*isl_local_space_replace_divs(
246 __isl_take isl_local_space
*ls
, __isl_take isl_mat
*div
)
248 ls
= isl_local_space_cow(ls
);
253 isl_mat_free(ls
->div
);
258 isl_local_space_free(ls
);
262 /* Copy row "s" of "src" to row "d" of "dst", applying the expansion
265 static void expand_row(__isl_keep isl_mat
*dst
, int d
,
266 __isl_keep isl_mat
*src
, int s
, int *exp
)
269 unsigned c
= src
->n_col
- src
->n_row
;
271 isl_seq_cpy(dst
->row
[d
], src
->row
[s
], c
);
272 isl_seq_clr(dst
->row
[d
] + c
, dst
->n_col
- c
);
274 for (i
= 0; i
< s
; ++i
)
275 isl_int_set(dst
->row
[d
][c
+ exp
[i
]], src
->row
[s
][c
+ i
]);
278 /* Compare (known) divs.
279 * Return non-zero if at least one of the two divs is unknown.
281 static int cmp_row(__isl_keep isl_mat
*div
, int i
, int j
)
285 if (isl_int_is_zero(div
->row
[j
][0]))
287 if (isl_int_is_zero(div
->row
[i
][0]))
290 li
= isl_seq_last_non_zero(div
->row
[i
], div
->n_col
);
291 lj
= isl_seq_last_non_zero(div
->row
[j
], div
->n_col
);
296 return isl_seq_cmp(div
->row
[i
], div
->row
[j
], div
->n_col
);
299 /* Combine the two lists of divs into a single list.
300 * For each row i in div1, exp1[i] is set to the position of the corresponding
301 * row in the result. Similarly for div2 and exp2.
302 * This function guarantees
304 * exp1[i+1] > exp1[i]
305 * For optimal merging, the two input list should have been sorted.
307 __isl_give isl_mat
*isl_merge_divs(__isl_keep isl_mat
*div1
,
308 __isl_keep isl_mat
*div2
, int *exp1
, int *exp2
)
312 unsigned d
= div1
->n_col
- div1
->n_row
;
314 div
= isl_mat_alloc(div1
->ctx
, 1 + div1
->n_row
+ div2
->n_row
,
315 d
+ div1
->n_row
+ div2
->n_row
);
319 for (i
= 0, j
= 0, k
= 0; i
< div1
->n_row
&& j
< div2
->n_row
; ++k
) {
322 expand_row(div
, k
, div1
, i
, exp1
);
323 expand_row(div
, k
+ 1, div2
, j
, exp2
);
325 cmp
= cmp_row(div
, k
, k
+ 1);
329 } else if (cmp
< 0) {
333 isl_seq_cpy(div
->row
[k
], div
->row
[k
+ 1], div
->n_col
);
336 for (; i
< div1
->n_row
; ++i
, ++k
) {
337 expand_row(div
, k
, div1
, i
, exp1
);
340 for (; j
< div2
->n_row
; ++j
, ++k
) {
341 expand_row(div
, k
, div2
, j
, exp2
);
351 int isl_local_space_divs_known(__isl_keep isl_local_space
*ls
)
358 for (i
= 0; i
< ls
->div
->n_row
; ++i
)
359 if (isl_int_is_zero(ls
->div
->row
[i
][0]))
365 /* Construct a local space for a map that has the given local
366 * space as domain and that has a zero-dimensional range.
368 __isl_give isl_local_space
*isl_local_space_from_domain(
369 __isl_take isl_local_space
*ls
)
371 ls
= isl_local_space_cow(ls
);
374 ls
->dim
= isl_dim_from_domain(ls
->dim
);
376 return isl_local_space_free(ls
);
380 __isl_give isl_local_space
*isl_local_space_add_dims(
381 __isl_take isl_local_space
*ls
, enum isl_dim_type type
, unsigned n
)
387 pos
= isl_local_space_dim(ls
, type
);
388 return isl_local_space_insert_dims(ls
, type
, pos
, n
);
391 /* Remove common factor of non-constant terms and denominator.
393 static void normalize_div(__isl_keep isl_local_space
*ls
, int div
)
395 isl_ctx
*ctx
= ls
->div
->ctx
;
396 unsigned total
= ls
->div
->n_col
- 2;
398 isl_seq_gcd(ls
->div
->row
[div
] + 2, total
, &ctx
->normalize_gcd
);
399 isl_int_gcd(ctx
->normalize_gcd
,
400 ctx
->normalize_gcd
, ls
->div
->row
[div
][0]);
401 if (isl_int_is_one(ctx
->normalize_gcd
))
404 isl_seq_scale_down(ls
->div
->row
[div
] + 2, ls
->div
->row
[div
] + 2,
405 ctx
->normalize_gcd
, total
);
406 isl_int_divexact(ls
->div
->row
[div
][0], ls
->div
->row
[div
][0],
408 isl_int_fdiv_q(ls
->div
->row
[div
][1], ls
->div
->row
[div
][1],
412 /* Exploit the equalities in "eq" to simplify the expressions of
413 * the integer divisions in "ls".
414 * The integer divisions in "ls" are assumed to appear as regular
415 * dimensions in "eq".
417 __isl_give isl_local_space
*isl_local_space_substitute_equalities(
418 __isl_take isl_local_space
*ls
, __isl_take isl_basic_set
*eq
)
424 ls
= isl_local_space_cow(ls
);
428 total
= isl_dim_total(eq
->dim
);
429 if (isl_local_space_dim(ls
, isl_dim_all
) != total
)
430 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
431 "dimensions don't match", goto error
);
434 for (i
= 0; i
< eq
->n_eq
; ++i
) {
435 j
= isl_seq_last_non_zero(eq
->eq
[i
], total
+ n_div
);
436 if (j
< 0 || j
== 0 || j
>= total
)
439 for (k
= 0; k
< ls
->div
->n_row
; ++k
) {
440 if (isl_int_is_zero(ls
->div
->row
[k
][1 + j
]))
442 isl_seq_elim(ls
->div
->row
[k
] + 1, eq
->eq
[i
], j
, total
,
443 &ls
->div
->row
[k
][0]);
444 normalize_div(ls
, k
);
448 isl_basic_set_free(eq
);
451 isl_basic_set_free(eq
);
452 isl_local_space_free(ls
);
456 int isl_local_space_is_named_or_nested(__isl_keep isl_local_space
*ls
,
457 enum isl_dim_type type
)
461 return isl_dim_is_named_or_nested(ls
->dim
, type
);
464 __isl_give isl_local_space
*isl_local_space_drop_dims(
465 __isl_take isl_local_space
*ls
,
466 enum isl_dim_type type
, unsigned first
, unsigned n
)
472 if (n
== 0 && !isl_local_space_is_named_or_nested(ls
, type
))
475 ctx
= isl_local_space_get_ctx(ls
);
476 if (first
+ n
> isl_local_space_dim(ls
, type
))
477 isl_die(ctx
, isl_error_invalid
, "range out of bounds",
478 return isl_local_space_free(ls
));
480 ls
= isl_local_space_cow(ls
);
484 if (type
== isl_dim_div
) {
485 ls
->div
= isl_mat_drop_rows(ls
->div
, first
, n
);
487 ls
->dim
= isl_dim_drop(ls
->dim
, type
, first
, n
);
489 return isl_local_space_free(ls
);
492 first
+= 1 + isl_local_space_offset(ls
, type
);
493 ls
->div
= isl_mat_drop_cols(ls
->div
, first
, n
);
495 return isl_local_space_free(ls
);
500 __isl_give isl_local_space
*isl_local_space_insert_dims(
501 __isl_take isl_local_space
*ls
,
502 enum isl_dim_type type
, unsigned first
, unsigned n
)
508 if (n
== 0 && !isl_local_space_is_named_or_nested(ls
, type
))
511 ctx
= isl_local_space_get_ctx(ls
);
512 if (first
> isl_local_space_dim(ls
, type
))
513 isl_die(ctx
, isl_error_invalid
, "position out of bounds",
514 return isl_local_space_free(ls
));
516 ls
= isl_local_space_cow(ls
);
520 if (type
== isl_dim_div
) {
521 ls
->div
= isl_mat_insert_zero_rows(ls
->div
, first
, n
);
523 ls
->dim
= isl_dim_insert(ls
->dim
, type
, first
, n
);
525 return isl_local_space_free(ls
);
528 first
+= 1 + isl_local_space_offset(ls
, type
);
529 ls
->div
= isl_mat_insert_zero_cols(ls
->div
, first
, n
);
531 return isl_local_space_free(ls
);