1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 *
4 * Use of this software is governed by the GNU GPLv2 license
5 *
6 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
8 */
9
10 #include <isl/val.h>
11 #include <isl/val_gmp.h>
12 #include <isl/space.h>
13 #include <isl/set.h>
14 #include <isl/map.h>
15 #include <isl/constraint.h>
16 #include "isl_set_polylib.h"
17 #include "isl_map_polylib.h"
18
isl_basic_set_new_from_polylib(Polyhedron * P,struct isl_space * dim)19 struct isl_basic_set *isl_basic_set_new_from_polylib(Polyhedron *P,
20 struct isl_space *dim)
21 {
22 isl_ctx *ctx;
23
24 if (!dim)
25 return NULL;
26 ctx = isl_space_get_ctx(dim);
27 isl_assert(ctx, isl_space_dim(dim, isl_dim_in) == 0, return NULL);
28
29 return (struct isl_basic_set *)
30 isl_basic_map_new_from_polylib(P, dim);
31 }
32
33 /* Return the number of equality constraints in the polyhedron description "P".
34 * The equality constraints have a zero in the first column.
35 * They also appear before the inequality constraints, but this code
36 * does not rely on this order.
37 */
polyhedron_n_eq(Polyhedron * P)38 static int polyhedron_n_eq(Polyhedron *P)
39 {
40 int i, n = 0;
41
42 for (i = 0; i < P->NbConstraints; ++i)
43 if (value_zero_p(P->Constraint[i][0]))
44 ++n;
45
46 return n;
47 }
48
49 /* Set the row "row" of "dst" to the values in array "src".
50 */
set_row(__isl_take isl_mat * dst,int row,Value * src)51 static __isl_give isl_mat *set_row(__isl_take isl_mat *dst, int row,
52 Value *src)
53 {
54 int i, n;
55 isl_ctx *ctx;
56
57 ctx = isl_mat_get_ctx(dst);
58 n = isl_mat_cols(dst);
59 for (i = 0; i < n; ++i) {
60 isl_val *v;
61
62 v = isl_val_int_from_gmp(ctx, src[i]);
63 dst = isl_mat_set_element_val(dst, row, i, v);
64 }
65
66 return dst;
67 }
68
69 /* Extract the "n_eq" equality constraints from "P", dropping the column
70 * that identifies equality constraints.
71 */
extract_equalities(isl_ctx * ctx,Polyhedron * P,int n_eq)72 static __isl_give isl_mat *extract_equalities(isl_ctx *ctx, Polyhedron *P,
73 int n_eq)
74 {
75 int i, j;
76 isl_mat *eq;
77
78 eq = isl_mat_alloc(ctx, n_eq, P->Dimension + 1);
79 for (i = 0, j = 0; i < P->NbConstraints; ++i) {
80 if (!value_zero_p(P->Constraint[i][0]))
81 continue;
82 eq = set_row(eq, j++, P->Constraint[i] + 1);
83 }
84
85 return eq;
86 }
87
88 /* Extract the "n_ineq" inequality constraints from "P", dropping the column
89 * that identifies equality constraints.
90 */
extract_inequalities(isl_ctx * ctx,Polyhedron * P,int n_ineq)91 static __isl_give isl_mat *extract_inequalities(isl_ctx *ctx, Polyhedron *P,
92 int n_ineq)
93 {
94 int i, j;
95 isl_mat *ineq;
96
97 ineq = isl_mat_alloc(ctx, n_ineq, P->Dimension + 1);
98 for (i = 0, j = 0; i < P->NbConstraints; ++i) {
99 if (value_zero_p(P->Constraint[i][0]))
100 continue;
101 ineq = set_row(ineq, j++, P->Constraint[i] + 1);
102 }
103
104 return ineq;
105 }
106
isl_basic_map_new_from_polylib(Polyhedron * P,__isl_take isl_space * space)107 __isl_give isl_basic_map *isl_basic_map_new_from_polylib(Polyhedron *P,
108 __isl_take isl_space *space)
109 {
110 isl_ctx *ctx;
111 isl_mat *eq, *ineq;
112 unsigned n_eq, n_ineq;
113
114 if (!space)
115 return NULL;
116
117 ctx = isl_space_get_ctx(space);
118 isl_assert(ctx, P, goto error);
119 isl_assert(ctx, P->Dimension >= isl_space_dim(space, isl_dim_all),
120 goto error);
121
122 n_eq = polyhedron_n_eq(P);
123 n_ineq = P->NbConstraints - n_eq;
124 eq = extract_equalities(ctx, P, n_eq);
125 ineq = extract_inequalities(ctx, P, n_ineq);
126
127 return isl_basic_map_from_constraint_matrices(space, eq, ineq,
128 isl_dim_in, isl_dim_out, isl_dim_div, isl_dim_param, isl_dim_cst);
129 error:
130 isl_space_free(space);
131 return NULL;
132 }
133
isl_set_new_from_polylib(Polyhedron * D,struct isl_space * dim)134 struct isl_set *isl_set_new_from_polylib(Polyhedron *D, struct isl_space *dim)
135 {
136 isl_ctx *ctx;
137 struct isl_set *set = NULL;
138 Polyhedron *P;
139
140 if (!dim)
141 return NULL;
142 ctx = isl_space_get_ctx(dim);
143 isl_assert(ctx, isl_space_dim(dim, isl_dim_in) == 0, return NULL);
144
145 set = isl_set_empty(isl_space_copy(dim));
146 if (!set)
147 goto error;
148
149 for (P = D; P; P = P->next)
150 set = isl_set_union_disjoint(set,
151 isl_set_from_basic_set(
152 isl_basic_set_new_from_polylib(P, isl_space_copy(dim))));
153 isl_space_free(dim);
154 return set;
155 error:
156 isl_space_free(dim);
157 return NULL;
158 }
159
160 /* Store the elements of "c" in the rows of "M" starting at "pos",
161 * adding an extra initial column identifying equality constraints.
162 * In particular, add 0 if "eq" is set and 1 otherwise.
163 */
add_constraints(Matrix * M,__isl_keep isl_mat * c,int eq,int pos)164 static Matrix *add_constraints(Matrix *M, __isl_keep isl_mat *c, int eq,
165 int pos)
166 {
167 int i, j, n;
168
169 if (!M)
170 return NULL;
171
172 n = isl_mat_rows(c);
173 for (i = 0; i < n; ++i) {
174 if (eq)
175 value_set_si(M->p[pos + i][0], 0);
176 else
177 value_set_si(M->p[pos + i][0], 1);
178
179 for (j = 0; 1 + j < M->NbColumns; ++j) {
180 isl_val *v;
181 v = isl_mat_get_element_val(c, i, j);
182 isl_val_get_num_gmp(v, M->p[pos + i][1 + j]);
183 isl_val_free(v);
184 if (!v)
185 goto error;
186 }
187 }
188
189 return M;
190 error:
191 Matrix_Free(M);
192 return NULL;
193 }
194
isl_basic_map_to_polylib(__isl_keep isl_basic_map * bmap)195 Polyhedron *isl_basic_map_to_polylib(__isl_keep isl_basic_map *bmap)
196 {
197 Matrix *M;
198 Polyhedron *P;
199 unsigned max_rays;
200 isl_mat *eq, *ineq;
201 int n_eq, n_ineq;
202 int n_col;
203
204 if (!bmap)
205 return NULL;
206
207 if (isl_basic_map_is_rational(bmap))
208 max_rays = POL_NO_DUAL;
209 else
210 max_rays = POL_NO_DUAL | POL_INTEGER;
211
212 ineq = isl_basic_map_inequalities_matrix(bmap,
213 isl_dim_in, isl_dim_out, isl_dim_div, isl_dim_param, isl_dim_cst);
214 eq = isl_basic_map_equalities_matrix(bmap,
215 isl_dim_in, isl_dim_out, isl_dim_div, isl_dim_param, isl_dim_cst);
216 n_eq = isl_mat_rows(eq);
217 n_ineq = isl_mat_rows(ineq);
218 n_col = isl_mat_cols(eq);
219
220 M = NULL;
221 if (n_eq >= 0 && n_ineq >= 0 && n_col >= 0) {
222 M = Matrix_Alloc(n_eq + n_ineq, 1 + n_col);
223 M = add_constraints(M, eq, 1, 0);
224 M = add_constraints(M, ineq, 0, n_eq);
225 }
226
227 isl_mat_free(ineq);
228 isl_mat_free(eq);
229
230 if (!M)
231 return NULL;
232
233 P = Constraints2Polyhedron(M, max_rays);
234 Matrix_Free(M);
235
236 return P;
237 }
238
add_basic_map(__isl_take isl_basic_map * bmap,void * user)239 static isl_stat add_basic_map(__isl_take isl_basic_map *bmap, void *user)
240 {
241 Polyhedron ***next = user;
242
243 **next = isl_basic_map_to_polylib(bmap);
244 *next = &(**next)->next;
245
246 isl_basic_map_free(bmap);
247 return isl_stat_ok;
248 }
249
isl_map_to_polylib(struct isl_map * map)250 Polyhedron *isl_map_to_polylib(struct isl_map *map)
251 {
252 Polyhedron *R = NULL;
253 Polyhedron **next = &R;
254
255 if (!map)
256 return NULL;
257
258 if (isl_map_foreach_basic_map(map, &add_basic_map, &next) < 0)
259 goto error;
260
261 return R ? R : Empty_Polyhedron(isl_map_dim(map, isl_dim_all));
262 error:
263 Domain_Free(R);
264 return NULL;
265 }
266
isl_basic_set_to_polylib(__isl_keep isl_basic_set * bset)267 Polyhedron *isl_basic_set_to_polylib(__isl_keep isl_basic_set *bset)
268 {
269 return isl_basic_map_to_polylib((struct isl_basic_map *)bset);
270 }
271
isl_set_to_polylib(__isl_keep isl_set * set)272 Polyhedron *isl_set_to_polylib(__isl_keep isl_set *set)
273 {
274 return isl_map_to_polylib((struct isl_map *)set);
275 }
276