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