isl_sample_piplib.c

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