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