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_map_private.h>
12 #include <isl_local_space_private.h>
13 #include <isl_dim_private.h>
14 #include <isl_mat_private.h>
17 isl_ctx
*isl_local_space_get_ctx(__isl_keep isl_local_space
*ls
)
19 return ls
? ls
->dim
->ctx
: NULL
;
22 __isl_give isl_local_space
*isl_local_space_alloc_div(__isl_take isl_dim
*dim
,
23 __isl_take isl_mat
*div
)
26 isl_local_space
*ls
= NULL
;
31 ctx
= isl_dim_get_ctx(dim
);
32 ls
= isl_calloc_type(ctx
, struct isl_local_space
);
43 isl_local_space_free(ls
);
47 __isl_give isl_local_space
*isl_local_space_alloc(__isl_take isl_dim
*dim
,
57 total
= isl_dim_total(dim
);
59 ctx
= isl_dim_get_ctx(dim
);
60 div
= isl_mat_alloc(ctx
, n_div
, 1 + 1 + total
+ n_div
);
61 return isl_local_space_alloc_div(dim
, div
);
64 __isl_give isl_local_space
*isl_local_space_from_dim(__isl_take isl_dim
*dim
)
66 return isl_local_space_alloc(dim
, 0);
69 __isl_give isl_local_space
*isl_local_space_copy(__isl_keep isl_local_space
*ls
)
78 __isl_give isl_local_space
*isl_local_space_dup(__isl_keep isl_local_space
*ls
)
83 return isl_local_space_alloc_div(isl_dim_copy(ls
->dim
),
84 isl_mat_copy(ls
->div
));
88 __isl_give isl_local_space
*isl_local_space_cow(__isl_take isl_local_space
*ls
)
96 return isl_local_space_dup(ls
);
99 void *isl_local_space_free(__isl_take isl_local_space
*ls
)
107 isl_dim_free(ls
->dim
);
108 isl_mat_free(ls
->div
);
115 /* Return true if the two local spaces are identical, with identical
116 * expressions for the integer divisions.
118 int isl_local_space_is_equal(__isl_keep isl_local_space
*ls1
,
119 __isl_keep isl_local_space
*ls2
)
126 equal
= isl_dim_equal(ls1
->dim
, ls2
->dim
);
127 if (equal
< 0 || !equal
)
130 return isl_mat_is_equal(ls1
->div
, ls2
->div
);
133 int isl_local_space_dim(__isl_keep isl_local_space
*ls
,
134 enum isl_dim_type type
)
138 if (type
== isl_dim_div
)
139 return ls
->div
->n_row
;
140 if (type
== isl_dim_all
)
141 return isl_dim_size(ls
->dim
, isl_dim_all
) + ls
->div
->n_row
;
142 return isl_dim_size(ls
->dim
, type
);
145 unsigned isl_local_space_offset(__isl_keep isl_local_space
*ls
,
146 enum isl_dim_type type
)
155 case isl_dim_cst
: return 0;
156 case isl_dim_param
: return 1;
157 case isl_dim_in
: return 1 + dim
->nparam
;
158 case isl_dim_out
: return 1 + dim
->nparam
+ dim
->n_in
;
159 case isl_dim_div
: return 1 + dim
->nparam
+ dim
->n_in
+ dim
->n_out
;
164 const char *isl_local_space_get_dim_name(__isl_keep isl_local_space
*ls
,
165 enum isl_dim_type type
, unsigned pos
)
167 return ls
? isl_dim_get_name(ls
->dim
, type
, pos
) : NULL
;
170 __isl_give isl_div
*isl_local_space_get_div(__isl_keep isl_local_space
*ls
,
178 if (pos
< 0 || pos
>= ls
->div
->n_row
)
179 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
180 "index out of bounds", return NULL
);
182 bmap
= isl_basic_map_from_local_space(isl_local_space_copy(ls
));
183 return isl_basic_map_div(bmap
, pos
);
186 __isl_give isl_dim
*isl_local_space_get_dim(__isl_keep isl_local_space
*ls
)
191 return isl_dim_copy(ls
->dim
);
194 __isl_give isl_local_space
*isl_local_space_add_div(
195 __isl_take isl_local_space
*ls
, __isl_take isl_vec
*div
)
197 ls
= isl_local_space_cow(ls
);
201 if (ls
->div
->n_col
!= div
->size
)
202 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
203 "incompatible dimensions", goto error
);
205 ls
->div
= isl_mat_add_zero_cols(ls
->div
, 1);
206 ls
->div
= isl_mat_add_rows(ls
->div
, 1);
210 isl_seq_cpy(ls
->div
->row
[ls
->div
->n_row
- 1], div
->el
, div
->size
);
211 isl_int_set_si(ls
->div
->row
[ls
->div
->n_row
- 1][div
->size
], 0);
216 isl_local_space_free(ls
);
221 __isl_give isl_local_space
*isl_local_space_replace_divs(
222 __isl_take isl_local_space
*ls
, __isl_take isl_mat
*div
)
224 ls
= isl_local_space_cow(ls
);
229 isl_mat_free(ls
->div
);
234 isl_local_space_free(ls
);
238 /* Copy row "s" of "src" to row "d" of "dst", applying the expansion
241 static void expand_row(__isl_keep isl_mat
*dst
, int d
,
242 __isl_keep isl_mat
*src
, int s
, int *exp
)
245 unsigned c
= src
->n_col
- src
->n_row
;
247 isl_seq_cpy(dst
->row
[d
], src
->row
[s
], c
);
248 isl_seq_clr(dst
->row
[d
] + c
, dst
->n_col
- c
);
250 for (i
= 0; i
< s
; ++i
)
251 isl_int_set(dst
->row
[d
][c
+ exp
[i
]], src
->row
[s
][c
+ i
]);
254 /* Compare (known) divs.
255 * Return non-zero if at least one of the two divs is unknown.
257 static int cmp_row(__isl_keep isl_mat
*div
, int i
, int j
)
261 if (isl_int_is_zero(div
->row
[j
][0]))
263 if (isl_int_is_zero(div
->row
[i
][0]))
266 li
= isl_seq_last_non_zero(div
->row
[i
], div
->n_col
);
267 lj
= isl_seq_last_non_zero(div
->row
[j
], div
->n_col
);
272 return isl_seq_cmp(div
->row
[i
], div
->row
[j
], div
->n_col
);
275 /* Combine the two lists of divs into a single list.
276 * For each row i in div1, exp1[i] is set to the position of the corresponding
277 * row in the result. Similarly for div2 and exp2.
278 * This function guarantees
280 * exp1[i+1] > exp1[i]
281 * For optimal merging, the two input list should have been sorted.
283 __isl_give isl_mat
*isl_merge_divs(__isl_keep isl_mat
*div1
,
284 __isl_keep isl_mat
*div2
, int *exp1
, int *exp2
)
288 unsigned d
= div1
->n_col
- div1
->n_row
;
290 div
= isl_mat_alloc(div1
->ctx
, 1 + div1
->n_row
+ div2
->n_row
,
291 d
+ div1
->n_row
+ div2
->n_row
);
295 for (i
= 0, j
= 0, k
= 0; i
< div1
->n_row
&& j
< div2
->n_row
; ++k
) {
298 expand_row(div
, k
, div1
, i
, exp1
);
299 expand_row(div
, k
+ 1, div2
, j
, exp2
);
301 cmp
= cmp_row(div
, k
, k
+ 1);
305 } else if (cmp
< 0) {
309 isl_seq_cpy(div
->row
[k
], div
->row
[k
+ 1], div
->n_col
);
312 for (; i
< div1
->n_row
; ++i
, ++k
) {
313 expand_row(div
, k
, div1
, i
, exp1
);
316 for (; j
< div2
->n_row
; ++j
, ++k
) {
317 expand_row(div
, k
, div2
, j
, exp2
);
327 int isl_local_space_divs_known(__isl_keep isl_local_space
*ls
)
334 for (i
= 0; i
< ls
->div
->n_row
; ++i
)
335 if (isl_int_is_zero(ls
->div
->row
[i
][0]))
341 /* Construct a local space for a map that has the given local
342 * space as domain and that has a zero-dimensional range.
344 __isl_give isl_local_space
*isl_local_space_from_domain(
345 __isl_take isl_local_space
*ls
)
347 ls
= isl_local_space_cow(ls
);
350 ls
->dim
= isl_dim_from_domain(ls
->dim
);
352 return isl_local_space_free(ls
);
356 __isl_give isl_local_space
*isl_local_space_add_dim(
357 __isl_take isl_local_space
*ls
, enum isl_dim_type type
, unsigned n
)
364 ls
= isl_local_space_cow(ls
);
368 pos
= isl_local_space_offset(ls
, type
);
369 pos
+= isl_local_space_dim(ls
, type
);
371 ls
->div
= isl_mat_insert_zero_cols(ls
->div
, 1 + pos
, n
);
373 if (type
== isl_dim_div
) {
374 ls
->div
= isl_mat_add_zero_rows(ls
->div
, n
);
376 ls
->dim
= isl_dim_add(ls
->dim
, type
, n
);
378 return isl_local_space_free(ls
);
382 return isl_local_space_free(ls
);