isl_sample_piplib.c

   1 #include "isl_mat.h"
   2 #include "isl_vec.h"
   3 #include "isl_piplib.h"
   4 #include "isl_sample_piplib.h"
   5
   6 static void swap_inequality(struct isl_basic_set *bset, int a, int b)
   7 {
   8         isl_int *t = bset->ineq[a];
   9         bset->ineq[a] = bset->ineq[b];
  10         bset->ineq[b] = t;
  11 }
  12
  13 static struct isl_mat *independent_bounds(struct isl_ctx *ctx,
  14         struct isl_basic_set *bset)
  15 {
  16         int i, j, n;
  17         struct isl_mat *dirs = NULL;
  18         struct isl_mat *bounds = NULL;
  19
  20         if (!bset)
  21                 return NULL;
  22
  23         bounds = isl_mat_alloc(ctx, 1+bset->dim, 1+bset->dim);
  24         if (!bounds)
  25                 return NULL;
  26
  27         isl_int_set_si(bounds->row[0][0], 1);
  28         isl_seq_clr(bounds->row[0]+1, bset->dim);
  29         bounds->n_row = 1;
  30
  31         if (bset->n_ineq == 0)
  32                 return bounds;
  33
  34         dirs = isl_mat_alloc(ctx, bset->dim, bset->dim);
  35         if (!dirs) {
  36                 isl_mat_free(ctx, bounds);
  37                 return NULL;
  38         }
  39         isl_seq_cpy(dirs->row[0], bset->ineq[0]+1, dirs->n_col);
  40         isl_seq_cpy(bounds->row[1], bset->ineq[0], bounds->n_col);
  41         for (j = 1, n = 1; n < bset->dim && j < bset->n_ineq; ++j) {
  42                 int pos;
  43
  44                 isl_seq_cpy(dirs->row[n], bset->ineq[j]+1, dirs->n_col);
  45
  46                 pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col);
  47                 if (pos < 0)
  48                         continue;
  49                 for (i = 0; i < n; ++i) {
  50                         int pos_i;
  51                         pos_i = isl_seq_first_non_zero(dirs->row[i], dirs->n_col);
  52                         if (pos_i < pos)
  53                                 continue;
  54                         if (pos_i > pos)
  55                                 break;
  56                         isl_seq_elim(dirs->row[n], dirs->row[i], pos,
  57                                         dirs->n_col, NULL);
  58                         pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col);
  59                         if (pos < 0)
  60                                 break;
  61                 }
  62                 if (pos < 0)
  63                         continue;
  64                 if (i < n) {
  65                         int k;
  66                         isl_int *t = dirs->row[n];
  67                         for (k = n; k > i; --k)
  68                                 dirs->row[k] = dirs->row[k-1];
  69                         dirs->row[i] = t;
  70                 }
  71                 ++n;
  72                 isl_seq_cpy(bounds->row[n], bset->ineq[j], bounds->n_col);
  73         }
  74         isl_mat_free(ctx, dirs);
  75         bounds->n_row = 1+n;
  76         return bounds;
  77 }
  78
  79 /* Skew into positive orthant and project out lineality space */
  80 static struct isl_basic_set *isl_basic_set_skew_to_positive_orthant(
  81         struct isl_basic_set *bset, struct isl_mat **T)
  82 {
  83         struct isl_mat *U = NULL;
  84         struct isl_mat *bounds = NULL;
  85         int i, j;
  86         unsigned old_dim, new_dim;
  87         struct isl_ctx *ctx;
  88
  89         *T = NULL;
  90         if (!bset)
  91                 return NULL;
  92
  93         ctx = bset->ctx;
  94         isl_assert(ctx, bset->nparam == 0, goto error);
  95         isl_assert(ctx, bset->n_div == 0, goto error);
  96         isl_assert(ctx, bset->n_eq == 0, goto error);
  97
  98         /* Try to move (multiples of) unit rows up. */
  99         for (i = 0, j = 0; i < bset->n_ineq; ++i) {
 100                 int pos = isl_seq_first_non_zero(bset->ineq[i]+1,
 101                                                             bset->dim);
 102                 if (pos < 0)
 103                         continue;
 104                 if (isl_seq_first_non_zero(bset->ineq[i]+1+pos+1,
 105                                                 bset->dim-pos-1) >= 0)
 106                         continue;
 107                 if (i != j)
 108                         swap_inequality(bset, i, j);
 109                 ++j;
 110         }
 111         bounds = independent_bounds(ctx, bset);
 112         if (!bounds)
 113                 goto error;
 114         old_dim = bset->dim;
 115         new_dim = bounds->n_row - 1;
 116         bounds = isl_mat_left_hermite(ctx, bounds, 1, &U, NULL);
 117         if (!bounds)
 118                 goto error;
 119         U = isl_mat_drop_cols(ctx, U, 1 + new_dim, old_dim - new_dim);
 120         bset = isl_basic_set_preimage(ctx, bset, isl_mat_copy(ctx, U));
 121         if (!bset)
 122                 goto error;
 123         *T = U;
 124         isl_mat_free(ctx, bounds);
 125         return bset;
 126 error:
 127         isl_mat_free(ctx, bounds);
 128         isl_mat_free(ctx, U);
 129         isl_basic_set_free(bset);
 130         return NULL;
 131 }
 132
 133 struct isl_vec *isl_pip_basic_set_sample(struct isl_basic_set *bset)
 134 {
 135         PipOptions      *options = NULL;
 136         PipMatrix       *domain = NULL;
 137         PipQuast        *sol = NULL;
 138         struct isl_vec *vec = NULL;
 139         unsigned        dim;
 140         struct isl_mat *T;
 141         struct isl_ctx *ctx;
 142
 143         if (!bset)
 144                 goto error;
 145         ctx = bset->ctx;
 146         isl_assert(ctx, bset->nparam == 0, goto error);
 147         isl_assert(ctx, bset->n_div == 0, goto error);
 148         bset = isl_basic_set_skew_to_positive_orthant(bset, &T);
 149         if (!bset)
 150                 goto error;
 151         dim = bset->dim;
 152         domain = isl_basic_map_to_pip((struct isl_basic_map *)bset, 0, 0, 0);
 153         if (!domain)
 154                 goto error;
 155
 156         options = pip_options_init();
 157         if (!options)
 158                 goto error;
 159         sol = pip_solve(domain, NULL, -1, options);
 160         if (!sol)
 161                 goto error;
 162         if (!sol->list) {
 163                 vec = isl_vec_alloc(ctx, 0);
 164                 isl_mat_free(ctx, T);
 165         } else {
 166                 PipList *l;
 167                 int i;
 168                 vec = isl_vec_alloc(ctx, 1 + dim);
 169                 if (!vec)
 170                         goto error;
 171                 isl_int_set_si(vec->block.data[0], 1);
 172                 for (i = 0, l = sol->list; l && i < dim; ++i, l = l->next) {
 173                         isl_seq_cpy_from_pip(&vec->block.data[1+i],
 174                                         &l->vector->the_vector[0], 1);
 175                         isl_assert(ctx, !entier_zero_p(l->vector->the_deno[0]),
 176                                         goto error);
 177                 }
 178                 isl_assert(ctx, i == dim, goto error);
 179                 vec = isl_mat_vec_product(ctx, T, vec);
 180         }
 181
 182         pip_quast_free(sol);
 183         pip_options_free(options);
 184         pip_matrix_free(domain);
 185
 186         isl_basic_set_free(bset);
 187         return vec;
 188 error:
 189         isl_vec_free(ctx, vec);
 190         isl_basic_set_free(bset);
 191         if (sol)
 192                 pip_quast_free(sol);
 193         if (domain)
 194                 pip_matrix_free(domain);
 195         return NULL;
 196 }