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