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_basic_set *bset)
  38 {
  39         int i;
  40         isl_int t;
  41         struct isl_vec *sample;
  42
  43         bset = isl_basic_set_simplify(bset);
  44         if (!bset)
  45                 return NULL;
  46         if (isl_basic_set_fast_is_empty(bset))
  47                 return empty_sample(bset);
  48         if (bset->n_eq == 0 && bset->n_ineq == 0)
  49                 return zero_sample(bset);
  50
  51         sample = isl_vec_alloc(bset->ctx, 2);
  52         isl_int_set_si(sample->block.data[0], 1);
  53
  54         if (bset->n_eq > 0) {
  55                 isl_assert(bset->ctx, bset->n_eq == 1, goto error);
  56                 isl_assert(bset->ctx, bset->n_ineq == 0, goto error);
  57                 if (isl_int_is_one(bset->eq[0][1]))
  58                         isl_int_neg(sample->el[1], bset->eq[0][0]);
  59                 else {
  60                         isl_assert(bset->ctx, isl_int_is_negone(bset->eq[0][1]),
  61                                    goto error);
  62                         isl_int_set(sample->el[1], bset->eq[0][0]);
  63                 }
  64                 isl_basic_set_free(bset);
  65                 return sample;
  66         }
  67
  68         isl_int_init(t);
  69         if (isl_int_is_one(bset->ineq[0][1]))
  70                 isl_int_neg(sample->block.data[1], bset->ineq[0][0]);
  71         else
  72                 isl_int_set(sample->block.data[1], bset->ineq[0][0]);
  73         for (i = 1; i < bset->n_ineq; ++i) {
  74                 isl_seq_inner_product(sample->block.data,
  75                                         bset->ineq[i], 2, &t);
  76                 if (isl_int_is_neg(t))
  77                         break;
  78         }
  79         isl_int_clear(t);
  80         if (i < bset->n_ineq) {
  81                 isl_vec_free(sample);
  82                 return empty_sample(bset);
  83         }
  84
  85         isl_basic_set_free(bset);
  86         return sample;
  87 error:
  88         isl_basic_set_free(bset);
  89         isl_vec_free(sample);
  90         return NULL;
  91 }
  92
  93 static struct isl_mat *independent_bounds(struct isl_ctx *ctx,
  94         struct isl_basic_set *bset)
  95 {
  96         int i, j, n;
  97         struct isl_mat *dirs = NULL;
  98         unsigned dim;
  99
 100         if (!bset)
 101                 return NULL;
 102
 103         dim = isl_basic_set_n_dim(bset);
 104         if (bset->n_ineq == 0)
 105                 return isl_mat_alloc(ctx, 0, dim);
 106
 107         dirs = isl_mat_alloc(ctx, dim, dim);
 108         if (!dirs)
 109                 return NULL;
 110         isl_seq_cpy(dirs->row[0], bset->ineq[0]+1, dirs->n_col);
 111         for (j = 1, n = 1; n < dim && j < bset->n_ineq; ++j) {
 112                 int pos;
 113
 114                 isl_seq_cpy(dirs->row[n], bset->ineq[j]+1, dirs->n_col);
 115
 116                 pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col);
 117                 if (pos < 0)
 118                         continue;
 119                 for (i = 0; i < n; ++i) {
 120                         int pos_i;
 121                         pos_i = isl_seq_first_non_zero(dirs->row[i], dirs->n_col);
 122                         if (pos_i < pos)
 123                                 continue;
 124                         if (pos_i > pos)
 125                                 break;
 126                         isl_seq_elim(dirs->row[n], dirs->row[i], pos,
 127                                         dirs->n_col, NULL);
 128                         pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col);
 129                         if (pos < 0)
 130                                 break;
 131                 }
 132                 if (pos < 0)
 133                         continue;
 134                 if (i < n) {
 135                         int k;
 136                         isl_int *t = dirs->row[n];
 137                         for (k = n; k > i; --k)
 138                                 dirs->row[k] = dirs->row[k-1];
 139                         dirs->row[i] = t;
 140                 }
 141                 ++n;
 142         }
 143         dirs->n_row = n;
 144         return dirs;
 145 }
 146
 147 /* Find a sample integer point, if any, in bset, which is known
 148  * to have equalities.  If bset contains no integer points, then
 149  * return a zero-length vector.
 150  * We simply remove the known equalities, compute a sample
 151  * in the resulting bset, using the specified recurse function,
 152  * and then transform the sample back to the original space.
 153  */
 154 static struct isl_vec *sample_eq(struct isl_basic_set *bset,
 155         struct isl_vec *(*recurse)(struct isl_basic_set *))
 156 {
 157         struct isl_mat *T;
 158         struct isl_vec *sample;
 159         struct isl_ctx *ctx;
 160
 161         if (!bset)
 162                 return NULL;
 163
 164         ctx = bset->ctx;
 165         bset = isl_basic_set_remove_equalities(bset, &T, NULL);
 166         sample = recurse(bset);
 167         if (!sample || sample->size == 0)
 168                 isl_mat_free(ctx, T);
 169         else
 170                 sample = isl_mat_vec_product(ctx, T, sample);
 171         return sample;
 172 }
 173
 174 static struct isl_vec *sample_no_lineality(struct isl_basic_set *bset)
 175 {
 176         unsigned dim;
 177
 178         if (isl_basic_set_fast_is_empty(bset))
 179                 return empty_sample(bset);
 180         if (bset->n_eq > 0)
 181                 return sample_eq(bset, sample_no_lineality);
 182         dim = isl_basic_set_total_dim(bset);
 183         if (dim == 0)
 184                 return zero_sample(bset);
 185         if (dim == 1)
 186                 return interval_sample(bset);
 187
 188         return isl_pip_basic_set_sample(bset);
 189 }
 190
 191 /* Compute an integer point in "bset" with a lineality space that
 192  * is orthogonal to the constraints in "bounds".
 193  *
 194  * We first perform a unimodular transformation on bset that
 195  * make the constraints in bounds (and therefore all constraints in bset)
 196  * only involve the first dimensions.  The remaining dimensions
 197  * then do not appear in any constraints and we can select any value
 198  * for them, say zero.  We therefore project out this final dimensions
 199  * and plug in the value zero later.  This is accomplished by simply
 200  * dropping the final columns of the unimodular transformation.
 201  */
 202 static struct isl_vec *sample_lineality(struct isl_basic_set *bset,
 203         struct isl_mat *bounds)
 204 {
 205         struct isl_mat *U = NULL;
 206         unsigned old_dim, new_dim;
 207         struct isl_vec *sample;
 208         struct isl_ctx *ctx;
 209
 210         if (!bset || !bounds)
 211                 goto error;
 212
 213         ctx = bset->ctx;
 214         old_dim = isl_basic_set_n_dim(bset);
 215         new_dim = bounds->n_row;
 216         bounds = isl_mat_left_hermite(ctx, bounds, 0, &U, NULL);
 217         if (!bounds)
 218                 goto error;
 219         U = isl_mat_lin_to_aff(ctx, U);
 220         U = isl_mat_drop_cols(ctx, U, 1 + new_dim, old_dim - new_dim);
 221         bset = isl_basic_set_preimage(bset, isl_mat_copy(ctx, U));
 222         if (!bset)
 223                 goto error;
 224         isl_mat_free(ctx, bounds);
 225
 226         sample = sample_no_lineality(bset);
 227         if (sample && sample->size != 0)
 228                 sample = isl_mat_vec_product(ctx, U, sample);
 229         else
 230                 isl_mat_free(ctx, U);
 231         return sample;
 232 error:
 233         isl_mat_free(ctx, bounds);
 234         isl_mat_free(ctx, U);
 235         isl_basic_set_free(bset);
 236         return NULL;
 237 }
 238
 239 struct isl_vec *isl_basic_set_sample(struct isl_basic_set *bset)
 240 {
 241         struct isl_ctx *ctx;
 242         struct isl_mat *bounds;
 243         unsigned dim;
 244         if (!bset)
 245                 return NULL;
 246
 247         ctx = bset->ctx;
 248         if (isl_basic_set_fast_is_empty(bset))
 249                 return empty_sample(bset);
 250
 251         dim = isl_basic_set_n_dim(bset);
 252         isl_assert(ctx, isl_basic_set_n_param(bset) == 0, goto error);
 253         isl_assert(ctx, bset->n_div == 0, goto error);
 254
 255         if (bset->n_eq > 0)
 256                 return sample_eq(bset, isl_basic_set_sample);
 257         if (dim == 0)
 258                 return zero_sample(bset);
 259         if (dim == 1)
 260                 return interval_sample(bset);
 261         bounds = independent_bounds(ctx, bset);
 262         if (!bounds)
 263                 goto error;
 264
 265         if (bounds->n_row == 0) {
 266                 isl_mat_free(ctx, bounds);
 267                 return zero_sample(bset);
 268         }
 269         if (bounds->n_row < dim)
 270                 return sample_lineality(bset, bounds);
 271
 272         isl_mat_free(ctx, bounds);
 273         return sample_no_lineality(bset);
 274 error:
 275         isl_basic_set_free(bset);
 276         return NULL;
 277 }