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