isl_sample.c

   1 #include "isl_sample.h"
   2 #include "isl_sample_piplib.h"
   3 #include "isl_vec.h"
   4 #include "isl_mat.h"
   5 #include "isl_seq.h"
   6 #include "isl_map_private.h"
   7 #include "isl_equalities.h"
   8
   9 static struct isl_vec *point_sample(struct isl_ctx *ctx,
  10         struct isl_basic_set *bset)
  11 {
  12         struct isl_vec *sample;
  13         isl_basic_set_free(bset);
  14         sample = isl_vec_alloc(ctx, 1);
  15         if (!sample)
  16                 return NULL;
  17         isl_int_set_si(sample->block.data[0], 1);
  18         return sample;
  19 }
  20
  21 static struct isl_vec *interval_sample(struct isl_ctx *ctx,
  22         struct isl_basic_set *bset)
  23 {
  24         struct isl_vec *sample;
  25
  26         bset = isl_basic_set_simplify(bset);
  27         if (!bset)
  28                 return NULL;
  29         if (bset->n_eq > 0)
  30                 return isl_basic_set_sample(bset);
  31         sample = isl_vec_alloc(ctx, 2);
  32         isl_int_set_si(sample->block.data[0], 1);
  33         if (bset->n_ineq == 0)
  34                 isl_int_set_si(sample->block.data[1], 0);
  35         else {
  36                 int i;
  37                 isl_int t;
  38                 isl_int_init(t);
  39                 if (isl_int_is_one(bset->ineq[0][1]))
  40                         isl_int_neg(sample->block.data[1], bset->ineq[0][0]);
  41                 else
  42                         isl_int_set(sample->block.data[1], bset->ineq[0][0]);
  43                 for (i = 1; i < bset->n_ineq; ++i) {
  44                         isl_seq_inner_product(sample->block.data,
  45                                                 bset->ineq[i], 2, &t);
  46                         if (isl_int_is_neg(t))
  47                                 break;
  48                 }
  49                 isl_int_clear(t);
  50                 if (i < bset->n_ineq) {
  51                         isl_vec_free(ctx, sample);
  52                         sample = isl_vec_alloc(ctx, 0);
  53                 }
  54         }
  55         isl_basic_set_free(bset);
  56         return sample;
  57 }
  58
  59 static struct isl_mat *independent_bounds(struct isl_ctx *ctx,
  60         struct isl_basic_set *bset)
  61 {
  62         int i, j, n;
  63         struct isl_mat *dirs = NULL;
  64
  65         if (!bset)
  66                 return NULL;
  67
  68         if (bset->n_ineq == 0)
  69                 return isl_mat_alloc(ctx, 0, bset->dim);
  70
  71         dirs = isl_mat_alloc(ctx, bset->dim, bset->dim);
  72         if (!dirs)
  73                 return NULL;
  74         isl_seq_cpy(dirs->row[0], bset->ineq[0]+1, dirs->n_col);
  75         for (j = 1, n = 1; n < bset->dim && j < bset->n_ineq; ++j) {
  76                 int pos;
  77
  78                 isl_seq_cpy(dirs->row[n], bset->ineq[j]+1, dirs->n_col);
  79
  80                 pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col);
  81                 if (pos < 0)
  82                         continue;
  83                 for (i = 0; i < n; ++i) {
  84                         int pos_i;
  85                         pos_i = isl_seq_first_non_zero(dirs->row[i], dirs->n_col);
  86                         if (pos_i < pos)
  87                                 continue;
  88                         if (pos_i > pos)
  89                                 break;
  90                         isl_seq_elim(dirs->row[n], dirs->row[i], pos,
  91                                         dirs->n_col, NULL);
  92                         pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col);
  93                         if (pos < 0)
  94                                 break;
  95                 }
  96                 if (pos < 0)
  97                         continue;
  98                 if (i < n) {
  99                         int k;
 100                         isl_int *t = dirs->row[n];
 101                         for (k = n; k > i; --k)
 102                                 dirs->row[k] = dirs->row[k-1];
 103                         dirs->row[i] = t;
 104                 }
 105                 ++n;
 106         }
 107         dirs->n_row = n;
 108         return dirs;
 109 }
 110
 111 static struct isl_basic_set *remove_lineality(struct isl_ctx *ctx,
 112         struct isl_basic_set *bset, struct isl_mat *bounds, struct isl_mat **T)
 113 {
 114         struct isl_mat *U = NULL;
 115         unsigned old_dim, new_dim;
 116
 117         old_dim = bset->dim;
 118         new_dim = bounds->n_row;
 119         *T = NULL;
 120         bounds = isl_mat_left_hermite(ctx, bounds, 0, &U, NULL);
 121         if (!bounds)
 122                 goto error;
 123         U = isl_mat_lin_to_aff(ctx, U);
 124         U = isl_mat_drop_cols(ctx, U, 1 + new_dim, old_dim - new_dim);
 125         bset = isl_basic_set_preimage(ctx, bset, isl_mat_copy(ctx, U));
 126         if (!bset)
 127                 goto error;
 128         *T = U;
 129         isl_mat_free(ctx, bounds);
 130         return bset;
 131 error:
 132         isl_mat_free(ctx, bounds);
 133         isl_mat_free(ctx, U);
 134         isl_basic_set_free(bset);
 135         return NULL;
 136 }
 137
 138 struct isl_vec *isl_basic_set_sample(struct isl_basic_set *bset)
 139 {
 140         struct isl_ctx *ctx;
 141         struct isl_mat *bounds;
 142         if (!bset)
 143                 return NULL;
 144
 145         ctx = bset->ctx;
 146         if (F_ISSET(bset, ISL_BASIC_SET_EMPTY)) {
 147                 isl_basic_set_free(bset);
 148                 return isl_vec_alloc(ctx, 0);
 149         }
 150
 151         isl_assert(ctx, bset->nparam == 0, goto error);
 152         isl_assert(ctx, bset->n_div == 0, goto error);
 153
 154         if (bset->n_eq > 0) {
 155                 struct isl_mat *T;
 156                 struct isl_vec *sample;
 157
 158                 bset = isl_basic_set_remove_equalities(bset, &T, NULL);
 159                 sample = isl_basic_set_sample(bset);
 160                 if (sample && sample->size != 0)
 161                         sample = isl_mat_vec_product(ctx, T, sample);
 162                 else
 163                         isl_mat_free(ctx, T);
 164                 return sample;
 165         }
 166         if (bset->dim == 0)
 167                 return point_sample(ctx, bset);
 168         if (bset->dim == 1)
 169                 return interval_sample(ctx, bset);
 170         bounds = independent_bounds(ctx, bset);
 171         if (!bounds)
 172                 goto error;
 173         if (bounds->n_row == bset->dim)
 174                 isl_mat_free(ctx, bounds);
 175         else {
 176                 struct isl_mat *T;
 177                 struct isl_vec *sample;
 178
 179                 bset = remove_lineality(ctx, bset, bounds, &T);
 180                 sample = isl_basic_set_sample(bset);
 181                 if (sample && sample->size != 0)
 182                         sample = isl_mat_vec_product(ctx, T, sample);
 183                 else
 184                         isl_mat_free(ctx, T);
 185                 return sample;
 186         }
 187         return isl_pip_basic_set_sample(bset);
 188 error:
 189         isl_basic_set_free(bset);
 190         return NULL;
 191 }