isl_map_polylib.c

   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
  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  */
  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  */
  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  */
  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  */
  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
 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
 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  */
 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
 195 /* Return the constraints of "bmap" as a PolyLib Matrix.
 196  */
 197 static Matrix *isl_basic_map_to_polylib_constraints(
 198         __isl_keep isl_basic_map *bmap)
 199 {
 200         Matrix *M;
 201         isl_mat *eq, *ineq;
 202         int n_eq, n_ineq;
 203         int n_col;
 204
 205         if (!bmap)
 206                 return NULL;
 207
 208         ineq = isl_basic_map_inequalities_matrix(bmap,
 209             isl_dim_in, isl_dim_out, isl_dim_div, isl_dim_param, isl_dim_cst);
 210         eq = isl_basic_map_equalities_matrix(bmap,
 211             isl_dim_in, isl_dim_out, isl_dim_div, isl_dim_param, isl_dim_cst);
 212         n_eq = isl_mat_rows(eq);
 213         n_ineq = isl_mat_rows(ineq);
 214         n_col = isl_mat_cols(eq);
 215
 216         M = NULL;
 217         if (n_eq >= 0 && n_ineq >= 0 && n_col >= 0) {
 218                 M = Matrix_Alloc(n_eq + n_ineq, 1 + n_col);
 219                 M = add_constraints(M, eq, 1, 0);
 220                 M = add_constraints(M, ineq, 0, n_eq);
 221         }
 222
 223         isl_mat_free(ineq);
 224         isl_mat_free(eq);
 225
 226         return M;
 227 }
 228
 229 /* Return the constraints of "bset" as a PolyLib Matrix.
 230  */
 231 Matrix *isl_basic_set_to_polylib_constraints(__isl_keep isl_basic_set *bset)
 232 {
 233         return isl_basic_map_to_polylib_constraints((isl_basic_map *) bset);
 234 }
 235
 236 Polyhedron *isl_basic_map_to_polylib(__isl_keep isl_basic_map *bmap)
 237 {
 238         Matrix *M;
 239         Polyhedron *P;
 240         unsigned max_rays;
 241
 242         if (!bmap)
 243                 return NULL;
 244
 245         if (isl_basic_map_is_rational(bmap))
 246                 max_rays = POL_NO_DUAL;
 247         else
 248                 max_rays = POL_NO_DUAL | POL_INTEGER;
 249
 250         M = isl_basic_map_to_polylib_constraints(bmap);
 251         if (!M)
 252                 return NULL;
 253
 254         P = Constraints2Polyhedron(M, max_rays);
 255         Matrix_Free(M);
 256
 257         return P;
 258 }
 259
 260 static isl_stat add_basic_map(__isl_take isl_basic_map *bmap, void *user)
 261 {
 262         Polyhedron ***next = user;
 263
 264         **next = isl_basic_map_to_polylib(bmap);
 265         *next = &(**next)->next;
 266
 267         isl_basic_map_free(bmap);
 268         return isl_stat_ok;
 269 }
 270
 271 Polyhedron *isl_map_to_polylib(struct isl_map *map)
 272 {
 273         Polyhedron *R = NULL;
 274         Polyhedron **next = &R;
 275
 276         if (!map)
 277                 return NULL;
 278
 279         if (isl_map_foreach_basic_map(map, &add_basic_map, &next) < 0)
 280                 goto error;
 281
 282         return R ? R : Empty_Polyhedron(isl_map_dim(map, isl_dim_all));
 283 error:
 284         Domain_Free(R);
 285         return NULL;
 286 }
 287
 288 Polyhedron *isl_basic_set_to_polylib(__isl_keep isl_basic_set *bset)
 289 {
 290         return isl_basic_map_to_polylib((struct isl_basic_map *)bset);
 291 }
 292
 293 Polyhedron *isl_set_to_polylib(__isl_keep isl_set *set)
 294 {
 295         return isl_map_to_polylib((struct isl_map *)set);
 296 }