isl_param_util.c

   1 #include <isl_set_polylib.h>
   2 #include <isl/vertices.h>
   3 #include "isl_param_util.h"
   4
   5 static Matrix *expr2vertex(Polyhedron *E, unsigned nvar)
   6 {
   7         int i;
   8         Matrix *M;
   9         unsigned nparam = E->Dimension - nvar;
  10         Value mone;
  11
  12         value_init(mone);
  13         value_set_si(mone, -1);
  14         M = Matrix_Alloc(nvar, nparam + 1 + 1);
  15         for (i = 0; i < nvar; ++i) {
  16                 Vector_Scale(E->Constraint[i] + 1 + nvar, M->p[i],
  17                                 mone, nparam + 1);
  18                 value_assign(M->p[i][nparam + 1], E->Constraint[i][1 + i]);
  19         }
  20         value_clear(mone);
  21
  22         return M;
  23 }
  24
  25 #define INT_BITS (sizeof(unsigned) * 8)
  26
  27 static int add_vertex(__isl_take isl_vertex *vertex, void *user)
  28 {
  29         Param_Vertices ***next_V = (Param_Vertices ***) user;
  30         Param_Vertices *V;
  31         Polyhedron *D, *E;
  32         isl_basic_set *dom;
  33         isl_basic_set *expr;
  34         isl_ctx *ctx;
  35         unsigned nvar;
  36
  37         ctx = isl_vertex_get_ctx(vertex);
  38
  39         dom = isl_vertex_get_domain(vertex);
  40         D = isl_basic_set_to_polylib(dom);
  41         isl_basic_set_free(dom);
  42
  43         expr = isl_vertex_get_expr(vertex);
  44         nvar = isl_basic_set_dim(expr, isl_dim_set);
  45         E = isl_basic_set_to_polylib(expr);
  46         isl_basic_set_free(expr);
  47
  48         V = isl_alloc_type(ctx, Param_Vertices);
  49         V->Vertex = expr2vertex(E, nvar);
  50         V->Domain = Polyhedron2Constraints(D);
  51         V->Facets = NULL;
  52         V->next = NULL;
  53
  54         Polyhedron_Free(D);
  55         Polyhedron_Free(E);
  56
  57         **next_V = V;
  58         *next_V = &V->next;
  59
  60         isl_vertex_free(vertex);
  61
  62         return 0;
  63 }
  64
  65 struct bv_add_chamber_data {
  66         Param_Domain **next_D;
  67         int vertex_len;
  68         Param_Domain *dom;
  69 };
  70
  71 static int add_chamber_vertex(__isl_take isl_vertex *vertex, void *user)
  72 {
  73         int j;
  74         struct bv_add_chamber_data *data = (struct bv_add_chamber_data *)user;
  75         unsigned v;
  76
  77         v = isl_vertex_get_id(vertex);
  78         data->dom->F[v / INT_BITS] |= 1u << (INT_BITS - (v % INT_BITS) - 1);
  79
  80         isl_vertex_free(vertex);
  81
  82         return 0;
  83 }
  84
  85 static int add_chamber(__isl_take isl_cell *cell, void *user)
  86 {
  87         struct bv_add_chamber_data *data = (struct bv_add_chamber_data *)user;
  88         isl_ctx *ctx;
  89         isl_basic_set *domain;
  90
  91         ctx = isl_cell_get_ctx(cell);
  92
  93         domain = isl_cell_get_domain(cell);
  94
  95         data->dom = isl_alloc_type(ctx, Param_Domain);
  96         data->dom->Domain = isl_basic_set_to_polylib(domain);
  97         data->dom->F = isl_calloc_array(ctx, unsigned, data->vertex_len);
  98         data->dom->next = NULL;
  99
 100         isl_basic_set_free(domain);
 101
 102         *data->next_D = data->dom;
 103         data->next_D = &data->dom->next;
 104
 105         isl_cell_foreach_vertex(cell, &add_chamber_vertex, data);
 106
 107         isl_cell_free(cell);
 108
 109         return 0;
 110 }
 111
 112 Param_Polyhedron *ISL_P2PP(Polyhedron *P, Polyhedron *C,
 113                           struct barvinok_options *options)
 114 {
 115         int i, j;
 116         isl_ctx *ctx = isl_ctx_alloc();
 117         isl_space *dim;
 118         isl_basic_set *bset, *context;
 119         isl_vertices *vertices;
 120         unsigned nparam = C->Dimension;
 121         unsigned nvar = P->Dimension - nparam;
 122         Param_Polyhedron *PP = isl_calloc_type(ctx, Param_Polyhedron);
 123         Param_Vertices **next_V;
 124         struct bv_add_chamber_data data;
 125
 126         dim = isl_space_set_alloc(ctx, nparam, nvar);
 127         bset = isl_basic_set_new_from_polylib(P, dim);
 128         dim = isl_space_set_alloc(ctx, nparam, 0);
 129         context = isl_basic_set_new_from_polylib(C, dim);
 130
 131         bset = isl_basic_set_intersect(bset, context);
 132
 133         vertices = isl_basic_set_compute_vertices(bset);
 134         isl_basic_set_free(bset);
 135
 136         PP->Rays = NULL;
 137         PP->nbV = isl_vertices_get_n_vertices(vertices);
 138         PP->Constraints = Polyhedron2Constraints(P);
 139
 140         next_V = &PP->V;
 141         isl_vertices_foreach_vertex(vertices, &add_vertex, &next_V);
 142
 143         data.next_D = &PP->D;
 144         data.vertex_len = (PP->nbV + INT_BITS - 1)/INT_BITS;
 145         isl_vertices_foreach_cell(vertices, &add_chamber, &data);
 146
 147         isl_vertices_free(vertices);
 148
 149         isl_ctx_free(ctx);
 150
 151         return PP;
 152 }