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