update isl for support for recent versions of clang
[barvinok.git] / isl_map_polylib.c
blob9a155862385ae96cbcaf2a68936c16ad58342ed0
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
4 * Use of this software is governed by the GNU GPLv2 license
6 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
8 */
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"
19 struct isl_basic_set *isl_basic_set_new_from_polylib(Polyhedron *P,
20 struct isl_space *dim)
22 isl_ctx *ctx;
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);
29 return (struct isl_basic_set *)
30 isl_basic_map_new_from_polylib(P, dim);
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.
38 static int polyhedron_n_eq(Polyhedron *P)
40 int i, n = 0;
42 for (i = 0; i < P->NbConstraints; ++i)
43 if (value_zero_p(P->Constraint[i][0]))
44 ++n;
46 return n;
49 /* Set the row "row" of "dst" to the values in array "src".
51 static __isl_give isl_mat *set_row(__isl_take isl_mat *dst, int row,
52 Value *src)
54 int i, n;
55 isl_ctx *ctx;
57 ctx = isl_mat_get_ctx(dst);
58 n = isl_mat_cols(dst);
59 for (i = 0; i < n; ++i) {
60 isl_val *v;
62 v = isl_val_int_from_gmp(ctx, src[i]);
63 dst = isl_mat_set_element_val(dst, row, i, v);
66 return dst;
69 /* Extract the "n_eq" equality constraints from "P", dropping the column
70 * that identifies equality constraints.
72 static __isl_give isl_mat *extract_equalities(isl_ctx *ctx, Polyhedron *P,
73 int n_eq)
75 int i, j;
76 isl_mat *eq;
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);
85 return eq;
88 /* Extract the "n_ineq" inequality constraints from "P", dropping the column
89 * that identifies equality constraints.
91 static __isl_give isl_mat *extract_inequalities(isl_ctx *ctx, Polyhedron *P,
92 int n_ineq)
94 int i, j;
95 isl_mat *ineq;
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);
104 return ineq;
107 __isl_give isl_basic_map *isl_basic_map_new_from_polylib(Polyhedron *P,
108 __isl_take isl_space *space)
110 isl_ctx *ctx;
111 isl_mat *eq, *ineq;
112 unsigned n_eq, n_ineq;
114 if (!space)
115 return NULL;
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);
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);
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;
134 struct isl_set *isl_set_new_from_polylib(Polyhedron *D, struct isl_space *dim)
136 isl_ctx *ctx;
137 struct isl_set *set = NULL;
138 Polyhedron *P;
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);
145 set = isl_set_empty(isl_space_copy(dim));
146 if (!set)
147 goto error;
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;
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.
164 static Matrix *add_constraints(Matrix *M, __isl_keep isl_mat *c, int eq,
165 int pos)
167 int i, j, n;
169 if (!M)
170 return NULL;
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);
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;
189 return M;
190 error:
191 Matrix_Free(M);
192 return NULL;
195 Polyhedron *isl_basic_map_to_polylib(__isl_keep isl_basic_map *bmap)
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;
204 if (!bmap)
205 return NULL;
207 if (isl_basic_map_is_rational(bmap))
208 max_rays = POL_NO_DUAL;
209 else
210 max_rays = POL_NO_DUAL | POL_INTEGER;
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);
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);
227 isl_mat_free(ineq);
228 isl_mat_free(eq);
230 if (!M)
231 return NULL;
233 P = Constraints2Polyhedron(M, max_rays);
234 Matrix_Free(M);
236 return P;
239 static isl_stat add_basic_map(__isl_take isl_basic_map *bmap, void *user)
241 Polyhedron ***next = user;
243 **next = isl_basic_map_to_polylib(bmap);
244 *next = &(**next)->next;
246 isl_basic_map_free(bmap);
247 return isl_stat_ok;
250 Polyhedron *isl_map_to_polylib(struct isl_map *map)
252 Polyhedron *R = NULL;
253 Polyhedron **next = &R;
255 if (!map)
256 return NULL;
258 if (isl_map_foreach_basic_map(map, &add_basic_map, &next) < 0)
259 goto error;
261 return R ? R : Empty_Polyhedron(isl_map_dim(map, isl_dim_all));
262 error:
263 Domain_Free(R);
264 return NULL;
267 Polyhedron *isl_basic_set_to_polylib(__isl_keep isl_basic_set *bset)
269 return isl_basic_map_to_polylib((struct isl_basic_map *)bset);
272 Polyhedron *isl_set_to_polylib(__isl_keep isl_set *set)
274 return isl_map_to_polylib((struct isl_map *)set);