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 static isl_stat count_constraints(__isl_take isl_constraint *c, void *user)
 160 {
 161         int *n = (int *)user;
 162         (*n)++;
 163         isl_constraint_free(c);
 164         return isl_stat_ok;
 165 }
 166
 167 struct isl_poly_copy {
 168         int n;
 169         Matrix *M;
 170 };
 171
 172 static isl_stat copy_constraint_to(__isl_take isl_constraint *c, void *user)
 173 {
 174         int i, j, k;
 175         enum isl_dim_type types[] = { isl_dim_in, isl_dim_out,
 176                                         isl_dim_div, isl_dim_param };
 177         struct isl_poly_copy *data = (struct isl_poly_copy *)user;
 178         isl_val *v;
 179
 180         if (isl_constraint_is_equality(c))
 181                 value_set_si(data->M->p[data->n][0], 0);
 182         else
 183                 value_set_si(data->M->p[data->n][0], 1);
 184         k = 1;
 185         for (i = 0; i < 4; ++i) {
 186                 int n = isl_constraint_dim(c, types[i]);
 187                 for (j = 0; j < n; ++j, ++k) {
 188                         v = isl_constraint_get_coefficient_val(c, types[i], j);
 189                         isl_val_get_num_gmp(v, data->M->p[data->n][k]);
 190                         isl_val_free(v);
 191                 }
 192         }
 193         v = isl_constraint_get_constant_val(c);
 194         isl_val_get_num_gmp(v, data->M->p[data->n][k]);
 195         isl_val_free(v);
 196         isl_constraint_free(c);
 197         data->n++;
 198         return isl_stat_ok;
 199 }
 200
 201 Polyhedron *isl_basic_map_to_polylib(struct isl_basic_map *bmap)
 202 {
 203         Polyhedron *P;
 204         unsigned nparam;
 205         unsigned n_in;
 206         unsigned n_out;
 207         unsigned max_rays;
 208         unsigned n_div;
 209         int n = 0;
 210         struct isl_poly_copy data;
 211
 212         if (!bmap)
 213                 return NULL;
 214
 215         if (isl_basic_map_is_rational(bmap))
 216                 max_rays = POL_NO_DUAL;
 217         else
 218                 max_rays = POL_NO_DUAL | POL_INTEGER;
 219
 220         if (isl_basic_map_foreach_constraint(bmap, &count_constraints, &n) < 0)
 221                 return NULL;
 222
 223         nparam = isl_basic_map_n_param(bmap);
 224         n_in = isl_basic_map_n_in(bmap);
 225         n_out = isl_basic_map_n_out(bmap);
 226         n_div = isl_basic_map_dim(bmap, isl_dim_div);
 227         data.M = Matrix_Alloc(n, 1 + n_in + n_out + n_div + nparam + 1);
 228         data.n = 0;
 229         if (isl_basic_map_foreach_constraint(bmap,
 230                                             &copy_constraint_to, &data) < 0) {
 231                 Matrix_Free(data.M);
 232                 return NULL;
 233         }
 234         P = Constraints2Polyhedron(data.M, max_rays);
 235         Matrix_Free(data.M);
 236
 237         return P;
 238 }
 239
 240 static isl_stat add_basic_map(__isl_take isl_basic_map *bmap, void *user)
 241 {
 242         Polyhedron ***next = user;
 243
 244         **next = isl_basic_map_to_polylib(bmap);
 245         *next = &(**next)->next;
 246
 247         isl_basic_map_free(bmap);
 248         return isl_stat_ok;
 249 }
 250
 251 Polyhedron *isl_map_to_polylib(struct isl_map *map)
 252 {
 253         Polyhedron *R = NULL;
 254         Polyhedron **next = &R;
 255
 256         if (!map)
 257                 return NULL;
 258
 259         if (isl_map_foreach_basic_map(map, &add_basic_map, &next) < 0)
 260                 goto error;
 261
 262         return R ? R : Empty_Polyhedron(isl_map_dim(map, isl_dim_all));
 263 error:
 264         Domain_Free(R);
 265         return NULL;
 266 }
 267
 268 Polyhedron *isl_basic_set_to_polylib(struct isl_basic_set *bset)
 269 {
 270         return isl_basic_map_to_polylib((struct isl_basic_map *)bset);
 271 }
 272
 273 Polyhedron *isl_set_to_polylib(struct isl_set *set)
 274 {
 275         return isl_map_to_polylib((struct isl_map *)set);
 276 }