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_gmp.h>
  11 #include <isl/set.h>
  12 #include <isl/map.h>
  13 #include <isl/constraint.h>
  14 #include "isl_set_polylib.h"
  15 #include "isl_map_polylib.h"
  16
  17 static __isl_give isl_constraint *copy_constraint_from(
  18         __isl_take isl_constraint *dst, Value *src)
  19 {
  20         int i, j, k;
  21         isl_ctx *ctx = isl_constraint_get_ctx(dst);
  22         isl_val *v;
  23         enum isl_dim_type types[] = { isl_dim_in, isl_dim_out, isl_dim_param };
  24
  25         k = 1;
  26         for (i = 0; i < 3; ++i) {
  27                 int n = isl_constraint_dim(dst, types[i]);
  28                 for (j = 0; j < n; ++j, ++k) {
  29                         v = isl_val_int_from_gmp(ctx, src[k]);
  30                         dst = isl_constraint_set_coefficient_val(dst, types[i],
  31                                                                 j, v);
  32                 }
  33         }
  34
  35         v = isl_val_int_from_gmp(ctx, src[k]);
  36         dst = isl_constraint_set_constant_val(dst, v);
  37
  38         return dst;
  39 }
  40
  41 static __isl_give isl_basic_map *add_equality(__isl_take isl_basic_map *bmap,
  42                          Value *constraint)
  43 {
  44         isl_constraint *c;
  45
  46         c = isl_constraint_alloc_equality(isl_basic_map_get_local_space(bmap));
  47
  48         c = copy_constraint_from(c, constraint);
  49
  50         bmap = isl_basic_map_add_constraint(bmap, c);
  51
  52         return bmap;
  53 }
  54
  55 static __isl_give isl_basic_map *add_inequality(__isl_take isl_basic_map *bmap,
  56                          Value *constraint)
  57 {
  58         isl_local_space *ls;
  59         isl_constraint *c;
  60
  61         ls = isl_basic_map_get_local_space(bmap);
  62         c = isl_constraint_alloc_inequality(ls);
  63
  64         copy_constraint_from(c, constraint);
  65
  66         bmap = isl_basic_map_add_constraint(bmap, c);
  67
  68         return bmap;
  69 }
  70
  71 static __isl_give isl_basic_map *copy_constraints(
  72                         __isl_take isl_basic_map *bmap, Polyhedron *P)
  73 {
  74         int i;
  75
  76         for (i = 0; i < P->NbConstraints; ++i) {
  77                 if (value_zero_p(P->Constraint[i][0]))
  78                         bmap = add_equality(bmap, P->Constraint[i]);
  79                 else
  80                         bmap = add_inequality(bmap, P->Constraint[i]);
  81         }
  82
  83         return bmap;
  84 }
  85
  86 struct isl_basic_set *isl_basic_set_new_from_polylib(Polyhedron *P,
  87                         struct isl_space *dim)
  88 {
  89         isl_ctx *ctx;
  90
  91         if (!dim)
  92                 return NULL;
  93         ctx = isl_space_get_ctx(dim);
  94         isl_assert(ctx, isl_space_dim(dim, isl_dim_in) == 0, return NULL);
  95
  96         return (struct isl_basic_set *)
  97                 isl_basic_map_new_from_polylib(P, dim);
  98 }
  99
 100 struct isl_basic_map *isl_basic_map_new_from_polylib(Polyhedron *P,
 101                         struct isl_space *dim)
 102 {
 103         isl_ctx *ctx;
 104         struct isl_basic_map *bmap;
 105         unsigned n_out;
 106         unsigned extra;
 107
 108         if (!dim)
 109                 return NULL;
 110
 111         ctx = isl_space_get_ctx(dim);
 112         isl_assert(ctx, P, goto error);
 113         isl_assert(ctx, P->Dimension >= isl_space_dim(dim, isl_dim_all),
 114                     goto error);
 115
 116         n_out = isl_space_dim(dim, isl_dim_out);
 117         extra = P->Dimension - isl_space_dim(dim, isl_dim_all);
 118         dim = isl_space_from_domain(isl_space_wrap(dim));
 119         dim = isl_space_add_dims(dim, isl_dim_out, extra);
 120         bmap = isl_basic_map_universe(dim);
 121         if (!bmap)
 122                 return NULL;
 123
 124         bmap = copy_constraints(bmap, P);
 125         bmap = isl_basic_set_unwrap(isl_basic_map_domain(bmap));
 126
 127         return bmap;
 128 error:
 129         isl_space_free(dim);
 130         return NULL;
 131 }
 132
 133 struct isl_set *isl_set_new_from_polylib(Polyhedron *D, struct isl_space *dim)
 134 {
 135         isl_ctx *ctx;
 136         struct isl_set *set = NULL;
 137         Polyhedron *P;
 138
 139         if (!dim)
 140                 return NULL;
 141         ctx = isl_space_get_ctx(dim);
 142         isl_assert(ctx, isl_space_dim(dim, isl_dim_in) == 0, return NULL);
 143
 144         set = isl_set_empty(isl_space_copy(dim));
 145         if (!set)
 146                 goto error;
 147
 148         for (P = D; P; P = P->next)
 149                 set = isl_set_union_disjoint(set,
 150                     isl_set_from_basic_set(
 151                     isl_basic_set_new_from_polylib(P, isl_space_copy(dim))));
 152         isl_space_free(dim);
 153         return set;
 154 error:
 155         isl_space_free(dim);
 156         return NULL;
 157 }
 158
 159 struct isl_map *isl_map_new_from_polylib(Polyhedron *D, struct isl_space *dim)
 160 {
 161         struct isl_map *map = NULL;
 162         Polyhedron *P;
 163
 164         if (!dim)
 165                 return NULL;
 166
 167         map = isl_map_empty(isl_space_copy(dim));
 168         if (!map)
 169                 goto error;
 170
 171         for (P = D; P; P = P->next)
 172                 map = isl_map_union_disjoint(map,
 173                     isl_map_from_basic_map(
 174                     isl_basic_map_new_from_polylib(P, isl_space_copy(dim))));
 175         isl_space_free(dim);
 176         return map;
 177 error:
 178         isl_space_free(dim);
 179         return NULL;
 180 }
 181
 182 static isl_stat count_constraints(__isl_take isl_constraint *c, void *user)
 183 {
 184         int *n = (int *)user;
 185         (*n)++;
 186         isl_constraint_free(c);
 187         return isl_stat_ok;
 188 }
 189
 190 struct isl_poly_copy {
 191         int n;
 192         Matrix *M;
 193 };
 194
 195 static isl_stat copy_constraint_to(__isl_take isl_constraint *c, void *user)
 196 {
 197         int i, j, k;
 198         enum isl_dim_type types[] = { isl_dim_in, isl_dim_out,
 199                                         isl_dim_div, isl_dim_param };
 200         struct isl_poly_copy *data = (struct isl_poly_copy *)user;
 201         isl_val *v;
 202
 203         if (isl_constraint_is_equality(c))
 204                 value_set_si(data->M->p[data->n][0], 0);
 205         else
 206                 value_set_si(data->M->p[data->n][0], 1);
 207         k = 1;
 208         for (i = 0; i < 4; ++i) {
 209                 int n = isl_constraint_dim(c, types[i]);
 210                 for (j = 0; j < n; ++j, ++k) {
 211                         v = isl_constraint_get_coefficient_val(c, types[i], j);
 212                         isl_val_get_num_gmp(v, data->M->p[data->n][k]);
 213                         isl_val_free(v);
 214                 }
 215         }
 216         v = isl_constraint_get_constant_val(c);
 217         isl_val_get_num_gmp(v, data->M->p[data->n][k]);
 218         isl_val_free(v);
 219         isl_constraint_free(c);
 220         data->n++;
 221         return isl_stat_ok;
 222 }
 223
 224 Polyhedron *isl_basic_map_to_polylib(struct isl_basic_map *bmap)
 225 {
 226         Polyhedron *P;
 227         unsigned off;
 228         unsigned nparam;
 229         unsigned n_in;
 230         unsigned n_out;
 231         unsigned max_rays;
 232         unsigned n_div;
 233         int n = 0;
 234         struct isl_poly_copy data;
 235
 236         if (!bmap)
 237                 return NULL;
 238
 239         if (isl_basic_map_is_rational(bmap))
 240                 max_rays = POL_NO_DUAL;
 241         else
 242                 max_rays = POL_NO_DUAL | POL_INTEGER;
 243
 244         if (isl_basic_map_foreach_constraint(bmap, &count_constraints, &n) < 0)
 245                 return NULL;
 246
 247         nparam = isl_basic_map_n_param(bmap);
 248         n_in = isl_basic_map_n_in(bmap);
 249         n_out = isl_basic_map_n_out(bmap);
 250         n_div = isl_basic_map_dim(bmap, isl_dim_div);
 251         data.M = Matrix_Alloc(n, 1 + n_in + n_out + n_div + nparam + 1);
 252         data.n = 0;
 253         if (isl_basic_map_foreach_constraint(bmap,
 254                                             &copy_constraint_to, &data) < 0) {
 255                 Matrix_Free(data.M);
 256                 return NULL;
 257         }
 258         P = Constraints2Polyhedron(data.M, max_rays);
 259         Matrix_Free(data.M);
 260
 261         return P;
 262 }
 263
 264 static isl_stat add_basic_map(__isl_take isl_basic_map *bmap, void *user)
 265 {
 266         Polyhedron ***next = user;
 267
 268         **next = isl_basic_map_to_polylib(bmap);
 269         *next = &(**next)->next;
 270
 271         isl_basic_map_free(bmap);
 272         return isl_stat_ok;
 273 }
 274
 275 Polyhedron *isl_map_to_polylib(struct isl_map *map)
 276 {
 277         int i;
 278         Polyhedron *R = NULL;
 279         Polyhedron **next = &R;
 280
 281         if (!map)
 282                 return NULL;
 283
 284         if (isl_map_foreach_basic_map(map, &add_basic_map, &next) < 0)
 285                 goto error;
 286
 287         return R ? R : Empty_Polyhedron(isl_map_dim(map, isl_dim_all));
 288 error:
 289         Domain_Free(R);
 290         return NULL;
 291 }
 292
 293 Polyhedron *isl_basic_set_to_polylib(struct isl_basic_set *bset)
 294 {
 295         return isl_basic_map_to_polylib((struct isl_basic_map *)bset);
 296 }
 297
 298 Polyhedron *isl_set_to_polylib(struct isl_set *set)
 299 {
 300         return isl_map_to_polylib((struct isl_map *)set);
 301 }