isl_map_polylib.c

   1 #include "isl_set.h"
   2 #include "isl_map.h"
   3 #include "isl_seq.h"
   4 #include "isl_set_polylib.h"
   5 #include "isl_map_polylib.h"
   6 #include "isl_map_private.h"
   7
   8 static void copy_values_from(isl_int *dst, Value *src, unsigned n)
   9 {
  10         int i;
  11
  12         for (i = 0; i < n; ++i)
  13                 value_assign(dst[i], src[i]);
  14 }
  15
  16 static void copy_values_to(Value *dst, isl_int *src, unsigned n)
  17 {
  18         int i;
  19
  20         for (i = 0; i < n; ++i)
  21                 value_assign(dst[i], src[i]);
  22 }
  23
  24 static void copy_constraint_from(isl_int *dst, Value *src,
  25                 unsigned nparam, unsigned dim, unsigned extra)
  26 {
  27         copy_values_from(dst, src+1+dim+extra+nparam, 1);
  28         copy_values_from(dst+1, src+1+dim+extra, nparam);
  29         copy_values_from(dst+1+nparam, src+1, dim);
  30         copy_values_from(dst+1+nparam+dim, src+1+dim, extra);
  31 }
  32
  33 static void copy_constraint_to(Value *dst, isl_int *src,
  34                 unsigned nparam, unsigned dim, unsigned extra)
  35 {
  36         copy_values_to(dst+1+dim+extra+nparam, src, 1);
  37         copy_values_to(dst+1+dim+extra, src+1, nparam);
  38         copy_values_to(dst+1, src+1+nparam, dim);
  39         copy_values_to(dst+1+dim, src+1+nparam+dim, extra);
  40 }
  41
  42 static int add_equality(struct isl_ctx *ctx, struct isl_basic_map *bmap,
  43                          Value *constraint)
  44 {
  45         unsigned nparam;
  46         unsigned n_in;
  47         unsigned n_out;
  48         int i = isl_basic_map_alloc_equality(bmap);
  49         if (i < 0)
  50                 return -1;
  51         nparam = isl_basic_map_n_param(bmap);
  52         n_in = isl_basic_map_n_in(bmap);
  53         n_out = isl_basic_map_n_out(bmap);
  54         copy_constraint_from(bmap->eq[i], constraint, nparam,
  55                              n_in + n_out, bmap->extra);
  56         return 0;
  57 }
  58
  59 static int add_inequality(struct isl_ctx *ctx, struct isl_basic_map *bmap,
  60                          Value *constraint)
  61 {
  62         unsigned nparam;
  63         unsigned n_in;
  64         unsigned n_out;
  65         int i = isl_basic_map_alloc_inequality(bmap);
  66         if (i < 0)
  67                 return -1;
  68         nparam = isl_basic_map_n_param(bmap);
  69         n_in = isl_basic_map_n_in(bmap);
  70         n_out = isl_basic_map_n_out(bmap);
  71         copy_constraint_from(bmap->ineq[i], constraint, nparam,
  72                              n_in + n_out, bmap->extra);
  73         return 0;
  74 }
  75
  76 static struct isl_basic_map *copy_constraints(
  77                         struct isl_ctx *ctx, struct isl_basic_map *bmap,
  78                         Polyhedron *P)
  79 {
  80         int i;
  81         unsigned total = isl_basic_map_total_dim(bmap);
  82
  83         for (i = 0; i < P->NbConstraints; ++i) {
  84                 if (value_zero_p(P->Constraint[i][0])) {
  85                         if (add_equality(ctx, bmap, P->Constraint[i]))
  86                                 goto error;
  87                 } else {
  88                         if (add_inequality(ctx, bmap, P->Constraint[i]))
  89                                 goto error;
  90                 }
  91         }
  92         for (i = 0; i < bmap->extra; ++i) {
  93                 int j = isl_basic_map_alloc_div(bmap);
  94                 if (j == -1)
  95                         goto error;
  96                 isl_seq_clr(bmap->div[j], 1+1+total);
  97         }
  98         return bmap;
  99 error:
 100         isl_basic_map_free(bmap);
 101         return NULL;
 102 }
 103
 104 struct isl_basic_set *isl_basic_set_new_from_polylib(Polyhedron *P,
 105                         struct isl_dim *dim)
 106 {
 107         if (!dim)
 108                 return NULL;
 109         isl_assert(dim->ctx, dim->n_in == 0, return NULL);
 110
 111         return (struct isl_basic_set *)
 112                 isl_basic_map_new_from_polylib(P, dim);
 113 }
 114
 115 struct isl_basic_map *isl_basic_map_new_from_polylib(Polyhedron *P,
 116                         struct isl_dim *dim)
 117 {
 118         struct isl_basic_map *bmap;
 119         unsigned extra;
 120
 121         if (!dim)
 122                 return NULL;
 123
 124         isl_assert(dim->ctx, P, goto error);
 125         isl_assert(dim->ctx, P->Dimension >= isl_dim_total(dim), goto error);
 126
 127         extra = P->Dimension - isl_dim_total(dim);
 128         bmap = isl_basic_map_alloc_dim(dim, extra,
 129                                         P->NbEq, P->NbConstraints - P->NbEq);
 130         if (!bmap)
 131                 return NULL;
 132
 133         bmap = copy_constraints(dim->ctx, bmap, P);
 134         bmap = isl_basic_map_simplify(bmap);
 135         return isl_basic_map_finalize(bmap);
 136 error:
 137         isl_dim_free(dim);
 138         return NULL;
 139 }
 140
 141 struct isl_set *isl_set_new_from_polylib(Polyhedron *D, struct isl_dim *dim)
 142 {
 143         struct isl_set *set = NULL;
 144         Polyhedron *P;
 145         int n = 0;
 146
 147         if (!dim)
 148                 return NULL;
 149         isl_assert(dim->ctx, dim->n_in == 0, goto error);
 150
 151         for (P = D; P; P = P->next)
 152                 ++n;
 153
 154         set = isl_set_alloc_dim(isl_dim_copy(dim), n, ISL_MAP_DISJOINT);
 155         if (!set)
 156                 goto error;
 157
 158         for (P = D; P; P = P->next)
 159                 isl_set_add(set,
 160                     isl_basic_set_new_from_polylib(P, isl_dim_copy(dim)));
 161         isl_dim_free(dim);
 162         set = isl_set_remove_empty_parts(set);
 163         return set;
 164 error:
 165         isl_dim_free(dim);
 166         return NULL;
 167 }
 168
 169 struct isl_map *isl_map_new_from_polylib(Polyhedron *D, struct isl_dim *dim)
 170 {
 171         struct isl_map *map = NULL;
 172         Polyhedron *P;
 173         int n = 0;
 174
 175         if (!dim)
 176                 return NULL;
 177
 178         for (P = D; P; P = P->next)
 179                 ++n;
 180
 181         map = isl_map_alloc_dim(isl_dim_copy(dim), n, ISL_MAP_DISJOINT);
 182         if (!map)
 183                 goto error;
 184
 185         for (P = D; P; P = P->next)
 186                 isl_map_add(map,
 187                     isl_basic_map_new_from_polylib(P, isl_dim_copy(dim)));
 188         isl_dim_free(dim);
 189         map = isl_map_remove_empty_parts(map);
 190         return map;
 191 error:
 192         isl_dim_free(dim);
 193         return NULL;
 194 }
 195
 196 Polyhedron *isl_basic_map_to_polylib(struct isl_basic_map *bmap)
 197 {
 198         int i;
 199         Matrix *M;
 200         Polyhedron *P;
 201         unsigned off;
 202         unsigned nparam;
 203         unsigned n_in;
 204         unsigned n_out;
 205
 206         if (!bmap)
 207                 return NULL;
 208
 209         nparam = isl_basic_map_n_param(bmap);
 210         n_in = isl_basic_map_n_in(bmap);
 211         n_out = isl_basic_map_n_out(bmap);
 212         M = Matrix_Alloc(bmap->n_eq + bmap->n_ineq,
 213                  1 + n_in + n_out + bmap->n_div + nparam + 1);
 214         for (i = 0; i < bmap->n_eq; ++i) {
 215                 value_set_si(M->p[i][0], 0);
 216                 copy_constraint_to(M->p[i], bmap->eq[i],
 217                            nparam, n_in + n_out, bmap->n_div);
 218         }
 219         off = bmap->n_eq;
 220         for (i = 0; i < bmap->n_ineq; ++i) {
 221                 value_set_si(M->p[off+i][0], 1);
 222                 copy_constraint_to(M->p[off+i], bmap->ineq[i],
 223                            nparam, n_in + n_out, bmap->n_div);
 224         }
 225         P = Constraints2Polyhedron(M, bmap->ctx->MaxRays);
 226         Matrix_Free(M);
 227
 228         return P;
 229 }
 230
 231 Polyhedron *isl_map_to_polylib(struct isl_map *map)
 232 {
 233         int i;
 234         Polyhedron *R = NULL;
 235         Polyhedron **next = &R;
 236
 237         if (!map)
 238                 return NULL;
 239
 240         for (i = 0; i < map->n; ++i) {
 241                 *next = isl_basic_map_to_polylib(map->p[i]);
 242                 next = &(*next)->next;
 243         }
 244
 245         return R ? R : Empty_Polyhedron(isl_dim_total(map->dim));
 246 }
 247
 248 Polyhedron *isl_basic_set_to_polylib(struct isl_basic_set *bset)
 249 {
 250         return isl_basic_map_to_polylib((struct isl_basic_map *)bset);
 251 }
 252
 253 Polyhedron *isl_set_to_polylib(struct isl_set *set)
 254 {
 255         return isl_map_to_polylib((struct isl_map *)set);
 256 }