1 #include "isl_sample.h"
2 #include "isl_sample_piplib.h"
6 #include "isl_map_private.h"
7 #include "isl_equalities.h"
9 static struct isl_vec *point_sample(struct isl_ctx *ctx,
10 struct isl_basic_set *bset)
12 struct isl_vec *sample;
13 isl_basic_set_free(bset);
14 sample = isl_vec_alloc(ctx, 1);
17 isl_int_set_si(sample->block.data[0], 1);
21 static struct isl_vec *interval_sample(struct isl_ctx *ctx,
22 struct isl_basic_set *bset)
24 struct isl_vec *sample;
26 bset = isl_basic_set_simplify(bset);
30 return isl_basic_set_sample(bset);
31 sample = isl_vec_alloc(ctx, 2);
32 isl_int_set_si(sample->block.data[0], 1);
33 if (bset->n_ineq == 0)
34 isl_int_set_si(sample->block.data[1], 0);
39 if (isl_int_is_one(bset->ineq[0][1]))
40 isl_int_neg(sample->block.data[1], bset->ineq[0][0]);
42 isl_int_set(sample->block.data[1], bset->ineq[0][0]);
43 for (i = 1; i < bset->n_ineq; ++i) {
44 isl_seq_inner_product(sample->block.data,
45 bset->ineq[i], 2, &t);
46 if (isl_int_is_neg(t))
50 if (i < bset->n_ineq) {
51 isl_vec_free(ctx, sample);
52 sample = isl_vec_alloc(ctx, 0);
55 isl_basic_set_free(bset);
59 static struct isl_mat *independent_bounds(struct isl_ctx *ctx,
60 struct isl_basic_set *bset)
63 struct isl_mat *dirs = NULL;
68 if (bset->n_ineq == 0)
69 return isl_mat_alloc(ctx, 0, bset->dim);
71 dirs = isl_mat_alloc(ctx, bset->dim, bset->dim);
74 isl_seq_cpy(dirs->row[0], bset->ineq[0]+1, dirs->n_col);
75 for (j = 1, n = 1; n < bset->dim && j < bset->n_ineq; ++j) {
78 isl_seq_cpy(dirs->row[n], bset->ineq[j]+1, dirs->n_col);
80 pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col);
83 for (i = 0; i < n; ++i) {
85 pos_i = isl_seq_first_non_zero(dirs->row[i], dirs->n_col);
90 isl_seq_elim(dirs->row[n], dirs->row[i], pos,
92 pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col);
100 isl_int *t = dirs->row[n];
101 for (k = n; k > i; --k)
102 dirs->row[k] = dirs->row[k-1];
111 static struct isl_basic_set *remove_lineality(struct isl_ctx *ctx,
112 struct isl_basic_set *bset, struct isl_mat *bounds, struct isl_mat **T)
114 struct isl_mat *U = NULL;
115 unsigned old_dim, new_dim;
118 new_dim = bounds->n_row;
120 bounds = isl_mat_left_hermite(ctx, bounds, 0, &U, NULL);
123 U = isl_mat_lin_to_aff(ctx, U);
124 U = isl_mat_drop_cols(ctx, U, 1 + new_dim, old_dim - new_dim);
125 bset = isl_basic_set_preimage(ctx, bset, isl_mat_copy(ctx, U));
129 isl_mat_free(ctx, bounds);
132 isl_mat_free(ctx, bounds);
133 isl_mat_free(ctx, U);
134 isl_basic_set_free(bset);
138 struct isl_vec *isl_basic_set_sample(struct isl_basic_set *bset)
141 struct isl_mat *bounds;
146 if (F_ISSET(bset, ISL_BASIC_SET_EMPTY)) {
147 isl_basic_set_free(bset);
148 return isl_vec_alloc(ctx, 0);
151 isl_assert(ctx, bset->nparam == 0, goto error);
152 isl_assert(ctx, bset->n_div == 0, goto error);
154 if (bset->n_eq > 0) {
156 struct isl_vec *sample;
158 bset = isl_basic_set_remove_equalities(bset, &T, NULL);
159 sample = isl_basic_set_sample(bset);
160 if (sample && sample->size != 0)
161 sample = isl_mat_vec_product(ctx, T, sample);
163 isl_mat_free(ctx, T);
167 return point_sample(ctx, bset);
169 return interval_sample(ctx, bset);
170 bounds = independent_bounds(ctx, bset);
173 if (bounds->n_row == bset->dim)
174 isl_mat_free(ctx, bounds);
177 struct isl_vec *sample;
179 bset = remove_lineality(ctx, bset, bounds, &T);
180 sample = isl_basic_set_sample(bset);
181 if (sample && sample->size != 0)
182 sample = isl_mat_vec_product(ctx, T, sample);
184 isl_mat_free(ctx, T);
187 return isl_pip_basic_set_sample(bset);
189 isl_basic_set_free(bset);