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 int isl_local_space_dim(__isl_keep isl_local_space
*ls
,
116 enum isl_dim_type type
)
120 if (type
== isl_dim_div
)
121 return ls
->div
->n_row
;
122 if (type
== isl_dim_all
)
123 return isl_dim_size(ls
->dim
, isl_dim_all
) + ls
->div
->n_row
;
124 return isl_dim_size(ls
->dim
, type
);
127 unsigned isl_local_space_offset(__isl_keep isl_local_space
*ls
,
128 enum isl_dim_type type
)
137 case isl_dim_cst
: return 0;
138 case isl_dim_param
: return 1;
139 case isl_dim_in
: return 1 + dim
->nparam
;
140 case isl_dim_out
: return 1 + dim
->nparam
+ dim
->n_in
;
141 case isl_dim_div
: return 1 + dim
->nparam
+ dim
->n_in
+ dim
->n_out
;
146 const char *isl_local_space_get_dim_name(__isl_keep isl_local_space
*ls
,
147 enum isl_dim_type type
, unsigned pos
)
149 return ls
? isl_dim_get_name(ls
->dim
, type
, pos
) : NULL
;
152 __isl_give isl_div
*isl_local_space_get_div(__isl_keep isl_local_space
*ls
,
160 if (pos
< 0 || pos
>= ls
->div
->n_row
)
161 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
162 "index out of bounds", return NULL
);
164 bmap
= isl_basic_map_from_local_space(isl_local_space_copy(ls
));
165 return isl_basic_map_div(bmap
, pos
);
168 __isl_give isl_dim
*isl_local_space_get_dim(__isl_keep isl_local_space
*ls
)
173 return isl_dim_copy(ls
->dim
);
176 __isl_give isl_local_space
*isl_local_space_add_div(
177 __isl_take isl_local_space
*ls
, __isl_take isl_vec
*div
)
179 ls
= isl_local_space_cow(ls
);
183 if (ls
->div
->n_col
!= div
->size
)
184 isl_die(isl_local_space_get_ctx(ls
), isl_error_invalid
,
185 "incompatible dimensions", goto error
);
187 ls
->div
= isl_mat_add_zero_cols(ls
->div
, 1);
188 ls
->div
= isl_mat_add_rows(ls
->div
, 1);
192 isl_seq_cpy(ls
->div
->row
[ls
->div
->n_row
- 1], div
->el
, div
->size
);
193 isl_int_set_si(ls
->div
->row
[ls
->div
->n_row
- 1][div
->size
], 0);
198 isl_local_space_free(ls
);
203 __isl_give isl_local_space
*isl_local_space_replace_divs(
204 __isl_take isl_local_space
*ls
, __isl_take isl_mat
*div
)
206 ls
= isl_local_space_cow(ls
);
211 isl_mat_free(ls
->div
);
216 isl_local_space_free(ls
);
220 /* Copy row "s" of "src" to row "d" of "dst", applying the expansion
223 static void expand_row(__isl_keep isl_mat
*dst
, int d
,
224 __isl_keep isl_mat
*src
, int s
, int *exp
)
227 unsigned c
= src
->n_col
- src
->n_row
;
229 isl_seq_cpy(dst
->row
[d
], src
->row
[s
], c
);
230 isl_seq_clr(dst
->row
[d
] + c
, dst
->n_col
- c
);
232 for (i
= 0; i
< s
; ++i
)
233 isl_int_set(dst
->row
[d
][c
+ exp
[i
]], src
->row
[s
][c
+ i
]);
236 /* Compare (known) divs.
237 * Return non-zero if at least one of the two divs is unknown.
239 static int cmp_row(__isl_keep isl_mat
*div
, int i
, int j
)
243 if (isl_int_is_zero(div
->row
[j
][0]))
245 if (isl_int_is_zero(div
->row
[i
][0]))
248 li
= isl_seq_last_non_zero(div
->row
[i
], div
->n_col
);
249 lj
= isl_seq_last_non_zero(div
->row
[j
], div
->n_col
);
254 return isl_seq_cmp(div
->row
[i
], div
->row
[j
], div
->n_col
);
257 /* Combine the two lists of divs into a single list.
258 * For each row i in div1, exp1[i] is set to the position of the corresponding
259 * row in the result. Similarly for div2 and exp2.
260 * This function guarantees
262 * exp1[i+1] > exp1[i]
263 * For optimal merging, the two input list should have been sorted.
265 __isl_give isl_mat
*isl_merge_divs(__isl_keep isl_mat
*div1
,
266 __isl_keep isl_mat
*div2
, int *exp1
, int *exp2
)
270 unsigned d
= div1
->n_col
- div1
->n_row
;
272 div
= isl_mat_alloc(div1
->ctx
, 1 + div1
->n_row
+ div2
->n_row
,
273 d
+ div1
->n_row
+ div2
->n_row
);
277 for (i
= 0, j
= 0, k
= 0; i
< div1
->n_row
&& j
< div2
->n_row
; ++k
) {
280 expand_row(div
, k
, div1
, i
, exp1
);
281 expand_row(div
, k
+ 1, div2
, j
, exp2
);
283 cmp
= cmp_row(div
, k
, k
+ 1);
287 } else if (cmp
< 0) {
291 isl_seq_cpy(div
->row
[k
], div
->row
[k
+ 1], div
->n_col
);
294 for (; i
< div1
->n_row
; ++i
, ++k
) {
295 expand_row(div
, k
, div1
, i
, exp1
);
298 for (; j
< div2
->n_row
; ++j
, ++k
) {
299 expand_row(div
, k
, div2
, j
, exp2
);
309 int isl_local_space_divs_known(__isl_keep isl_local_space
*ls
)
316 for (i
= 0; i
< ls
->div
->n_row
; ++i
)
317 if (isl_int_is_zero(ls
->div
->row
[i
][0]))