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