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 *empty_sample(struct isl_basic_set *bset)
13 vec = isl_vec_alloc(bset->ctx, 0);
14 isl_basic_set_free(bset);
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.
22 static struct isl_vec *zero_sample(struct isl_basic_set *bset)
25 struct isl_vec *sample;
27 dim = isl_basic_set_total_dim(bset);
28 sample = isl_vec_alloc(bset->ctx, 1 + dim);
30 isl_int_set_si(sample->el[0], 1);
31 isl_seq_clr(sample->el + 1, dim);
33 isl_basic_set_free(bset);
37 static struct isl_vec *interval_sample(struct isl_ctx *ctx,
38 struct isl_basic_set *bset)
42 struct isl_vec *sample;
44 bset = isl_basic_set_simplify(bset);
47 if (isl_basic_set_fast_is_empty(bset))
48 return empty_sample(bset);
49 if (bset->n_eq == 0 && bset->n_ineq == 0)
50 return zero_sample(bset);
52 sample = isl_vec_alloc(ctx, 2);
53 isl_int_set_si(sample->block.data[0], 1);
56 isl_assert(bset->ctx, bset->n_eq == 1, goto error);
57 isl_assert(bset->ctx, bset->n_ineq == 0, goto error);
58 if (isl_int_is_one(bset->eq[0][1]))
59 isl_int_neg(sample->el[1], bset->eq[0][0]);
61 isl_assert(bset->ctx, isl_int_is_negone(bset->eq[0][1]),
63 isl_int_set(sample->el[1], bset->eq[0][0]);
65 isl_basic_set_free(bset);
70 if (isl_int_is_one(bset->ineq[0][1]))
71 isl_int_neg(sample->block.data[1], bset->ineq[0][0]);
73 isl_int_set(sample->block.data[1], bset->ineq[0][0]);
74 for (i = 1; i < bset->n_ineq; ++i) {
75 isl_seq_inner_product(sample->block.data,
76 bset->ineq[i], 2, &t);
77 if (isl_int_is_neg(t))
81 if (i < bset->n_ineq) {
83 return empty_sample(bset);
86 isl_basic_set_free(bset);
89 isl_basic_set_free(bset);
94 static struct isl_mat *independent_bounds(struct isl_ctx *ctx,
95 struct isl_basic_set *bset)
98 struct isl_mat *dirs = NULL;
104 dim = isl_basic_set_n_dim(bset);
105 if (bset->n_ineq == 0)
106 return isl_mat_alloc(ctx, 0, dim);
108 dirs = isl_mat_alloc(ctx, dim, dim);
111 isl_seq_cpy(dirs->row[0], bset->ineq[0]+1, dirs->n_col);
112 for (j = 1, n = 1; n < dim && j < bset->n_ineq; ++j) {
115 isl_seq_cpy(dirs->row[n], bset->ineq[j]+1, dirs->n_col);
117 pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col);
120 for (i = 0; i < n; ++i) {
122 pos_i = isl_seq_first_non_zero(dirs->row[i], dirs->n_col);
127 isl_seq_elim(dirs->row[n], dirs->row[i], pos,
129 pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col);
137 isl_int *t = dirs->row[n];
138 for (k = n; k > i; --k)
139 dirs->row[k] = dirs->row[k-1];
148 static struct isl_basic_set *remove_lineality(struct isl_ctx *ctx,
149 struct isl_basic_set *bset, struct isl_mat *bounds, struct isl_mat **T)
151 struct isl_mat *U = NULL;
152 unsigned old_dim, new_dim;
154 old_dim = isl_basic_set_n_dim(bset);
155 new_dim = bounds->n_row;
157 bounds = isl_mat_left_hermite(ctx, bounds, 0, &U, NULL);
160 U = isl_mat_lin_to_aff(ctx, U);
161 U = isl_mat_drop_cols(ctx, U, 1 + new_dim, old_dim - new_dim);
162 bset = isl_basic_set_preimage(bset, isl_mat_copy(ctx, U));
166 isl_mat_free(ctx, bounds);
169 isl_mat_free(ctx, bounds);
170 isl_mat_free(ctx, U);
171 isl_basic_set_free(bset);
175 /* Find a sample integer point, if any, in bset, which is known
176 * to have equalities. If bset contains no integer points, then
177 * return a zero-length vector.
178 * We simply remove the known equalities, compute a sample
179 * in the resulting bset, using the specified recurse function,
180 * and then transform the sample back to the original space.
182 static struct isl_vec *sample_eq(struct isl_basic_set *bset,
183 struct isl_vec *(*recurse)(struct isl_basic_set *))
186 struct isl_vec *sample;
193 bset = isl_basic_set_remove_equalities(bset, &T, NULL);
194 sample = recurse(bset);
195 if (!sample || sample->size == 0)
196 isl_mat_free(ctx, T);
198 sample = isl_mat_vec_product(ctx, T, sample);
202 struct isl_vec *isl_basic_set_sample(struct isl_basic_set *bset)
205 struct isl_mat *bounds;
211 if (isl_basic_set_fast_is_empty(bset))
212 return empty_sample(bset);
214 dim = isl_basic_set_n_dim(bset);
215 isl_assert(ctx, isl_basic_set_n_param(bset) == 0, goto error);
216 isl_assert(ctx, bset->n_div == 0, goto error);
219 return sample_eq(bset, isl_basic_set_sample);
221 return zero_sample(bset);
223 return interval_sample(ctx, bset);
224 bounds = independent_bounds(ctx, bset);
227 if (bounds->n_row == dim)
228 isl_mat_free(ctx, bounds);
231 struct isl_vec *sample;
233 bset = remove_lineality(ctx, bset, bounds, &T);
234 sample = isl_basic_set_sample(bset);
235 if (sample && sample->size != 0)
236 sample = isl_mat_vec_product(ctx, T, sample);
238 isl_mat_free(ctx, T);
241 return isl_pip_basic_set_sample(bset);
243 isl_basic_set_free(bset);