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         unsigned dim;
  65
  66         if (!bset)
  67                 return NULL;
  68
  69         dim = isl_basic_set_n_dim(bset);
  70         if (bset->n_ineq == 0)
  71                 return isl_mat_alloc(ctx, 0, dim);
  72
  73         dirs = isl_mat_alloc(ctx, dim, dim);
  74         if (!dirs)
  75                 return NULL;
  76         isl_seq_cpy(dirs->row[0], bset->ineq[0]+1, dirs->n_col);
  77         for (j = 1, n = 1; n < dim && j < bset->n_ineq; ++j) {
  78                 int pos;
  79
  80                 isl_seq_cpy(dirs->row[n], bset->ineq[j]+1, dirs->n_col);
  81
  82                 pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col);
  83                 if (pos < 0)
  84                         continue;
  85                 for (i = 0; i < n; ++i) {
  86                         int pos_i;
  87                         pos_i = isl_seq_first_non_zero(dirs->row[i], dirs->n_col);
  88                         if (pos_i < pos)
  89                                 continue;
  90                         if (pos_i > pos)
  91                                 break;
  92                         isl_seq_elim(dirs->row[n], dirs->row[i], pos,
  93                                         dirs->n_col, NULL);
  94                         pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col);
  95                         if (pos < 0)
  96                                 break;
  97                 }
  98                 if (pos < 0)
  99                         continue;
 100                 if (i < n) {
 101                         int k;
 102                         isl_int *t = dirs->row[n];
 103                         for (k = n; k > i; --k)
 104                                 dirs->row[k] = dirs->row[k-1];
 105                         dirs->row[i] = t;
 106                 }
 107                 ++n;
 108         }
 109         dirs->n_row = n;
 110         return dirs;
 111 }
 112
 113 static struct isl_basic_set *remove_lineality(struct isl_ctx *ctx,
 114         struct isl_basic_set *bset, struct isl_mat *bounds, struct isl_mat **T)
 115 {
 116         struct isl_mat *U = NULL;
 117         unsigned old_dim, new_dim;
 118
 119         old_dim = isl_basic_set_n_dim(bset);
 120         new_dim = bounds->n_row;
 121         *T = NULL;
 122         bounds = isl_mat_left_hermite(ctx, bounds, 0, &U, NULL);
 123         if (!bounds)
 124                 goto error;
 125         U = isl_mat_lin_to_aff(ctx, U);
 126         U = isl_mat_drop_cols(ctx, U, 1 + new_dim, old_dim - new_dim);
 127         bset = isl_basic_set_preimage(ctx, bset, isl_mat_copy(ctx, U));
 128         if (!bset)
 129                 goto error;
 130         *T = U;
 131         isl_mat_free(ctx, bounds);
 132         return bset;
 133 error:
 134         isl_mat_free(ctx, bounds);
 135         isl_mat_free(ctx, U);
 136         isl_basic_set_free(bset);
 137         return NULL;
 138 }
 139
 140 struct isl_vec *isl_basic_set_sample(struct isl_basic_set *bset)
 141 {
 142         struct isl_ctx *ctx;
 143         struct isl_mat *bounds;
 144         unsigned dim;
 145         if (!bset)
 146                 return NULL;
 147
 148         ctx = bset->ctx;
 149         if (F_ISSET(bset, ISL_BASIC_SET_EMPTY)) {
 150                 isl_basic_set_free(bset);
 151                 return isl_vec_alloc(ctx, 0);
 152         }
 153
 154         dim = isl_basic_set_n_dim(bset);
 155         isl_assert(ctx, isl_basic_set_n_param(bset) == 0, goto error);
 156         isl_assert(ctx, bset->n_div == 0, goto error);
 157
 158         if (bset->n_eq > 0) {
 159                 struct isl_mat *T;
 160                 struct isl_vec *sample;
 161
 162                 bset = isl_basic_set_remove_equalities(bset, &T, NULL);
 163                 sample = isl_basic_set_sample(bset);
 164                 if (sample && sample->size != 0)
 165                         sample = isl_mat_vec_product(ctx, T, sample);
 166                 else
 167                         isl_mat_free(ctx, T);
 168                 return sample;
 169         }
 170         if (dim == 0)
 171                 return point_sample(ctx, bset);
 172         if (dim == 1)
 173                 return interval_sample(ctx, bset);
 174         bounds = independent_bounds(ctx, bset);
 175         if (!bounds)
 176                 goto error;
 177         if (bounds->n_row == dim)
 178                 isl_mat_free(ctx, bounds);
 179         else {
 180                 struct isl_mat *T;
 181                 struct isl_vec *sample;
 182
 183                 bset = remove_lineality(ctx, bset, bounds, &T);
 184                 sample = isl_basic_set_sample(bset);
 185                 if (sample && sample->size != 0)
 186                         sample = isl_mat_vec_product(ctx, T, sample);
 187                 else
 188                         isl_mat_free(ctx, T);
 189                 return sample;
 190         }
 191         return isl_pip_basic_set_sample(bset);
 192 error:
 193         isl_basic_set_free(bset);
 194         return NULL;
 195 }