1 #include "isl_sample.h"
2 #include "isl_sample_piplib.h"
5 #include "isl_map_private.h"
6 #include "isl_equalities.h"
8 static struct isl_vec *point_sample(struct isl_ctx *ctx,
9 struct isl_basic_set *bset)
11 struct isl_vec *sample;
12 isl_basic_set_free(ctx, bset);
13 sample = isl_vec_alloc(ctx, 1);
16 isl_int_set_si(sample->block.data[0], 1);
20 static struct isl_vec *interval_sample(struct isl_ctx *ctx,
21 struct isl_basic_set *bset)
23 struct isl_vec *sample;
25 bset = isl_basic_set_simplify(ctx, bset);
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);
38 if (isl_int_is_one(bset->ineq[0][1]))
39 isl_int_neg(sample->block.data[1], bset->ineq[0][0]);
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))
49 if (i < bset->n_ineq) {
50 isl_vec_free(ctx, sample);
51 sample = isl_vec_alloc(ctx, 0);
54 isl_basic_set_free(ctx, bset);
58 static struct isl_mat *independent_bounds(struct isl_ctx *ctx,
59 struct isl_basic_set *bset)
62 struct isl_mat *dirs = NULL;
67 if (bset->n_ineq == 0)
68 return isl_mat_alloc(ctx, 0, bset->dim);
70 dirs = isl_mat_alloc(ctx, bset->dim, bset->dim);
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) {
77 isl_seq_cpy(dirs->row[n], bset->ineq[j]+1, dirs->n_col);
79 pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col);
82 for (i = 0; i < n; ++i) {
84 pos_i = isl_seq_first_non_zero(dirs->row[i], dirs->n_col);
89 isl_seq_elim(dirs->row[n], dirs->row[i], pos,
91 pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col);
99 isl_int *t = dirs->row[n];
100 for (k = n; k > i; --k)
101 dirs->row[k] = dirs->row[k-1];
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)
113 struct isl_mat *U = NULL;
114 unsigned old_dim, new_dim;
117 new_dim = bounds->n_row;
119 bounds = isl_mat_left_hermite(ctx, bounds, 0, &U, NULL);
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));
128 isl_mat_free(ctx, bounds);
131 isl_mat_free(ctx, bounds);
132 isl_mat_free(ctx, U);
133 isl_basic_set_free(ctx, bset);
137 struct isl_vec *isl_basic_set_sample(struct isl_ctx *ctx,
138 struct isl_basic_set *bset)
140 struct isl_mat *bounds;
144 if (F_ISSET(bset, ISL_BASIC_SET_EMPTY)) {
145 isl_basic_set_free(ctx, bset);
146 return isl_vec_alloc(ctx, 0);
149 isl_assert(ctx, bset->nparam == 0, goto error);
150 isl_assert(ctx, bset->n_div == 0, goto error);
152 if (bset->n_eq > 0) {
154 struct isl_vec *sample;
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);
161 isl_mat_free(ctx, T);
165 return point_sample(ctx, bset);
167 return interval_sample(ctx, bset);
168 bounds = independent_bounds(ctx, bset);
171 if (bounds->n_row == bset->dim)
172 isl_mat_free(ctx, bounds);
175 struct isl_vec *sample;
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);
182 isl_mat_free(ctx, T);
185 return isl_pip_basic_set_sample(ctx, bset);
187 isl_basic_set_free(ctx, bset);