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_basic_set *bset)
41 struct isl_vec *sample;
43 bset = isl_basic_set_simplify(bset);
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);
51 sample = isl_vec_alloc(bset->ctx, 2);
52 isl_int_set_si(sample->block.data[0], 1);
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]);
60 isl_assert(bset->ctx, isl_int_is_negone(bset->eq[0][1]),
62 isl_int_set(sample->el[1], bset->eq[0][0]);
64 isl_basic_set_free(bset);
69 if (isl_int_is_one(bset->ineq[0][1]))
70 isl_int_neg(sample->block.data[1], bset->ineq[0][0]);
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))
80 if (i < bset->n_ineq) {
82 return empty_sample(bset);
85 isl_basic_set_free(bset);
88 isl_basic_set_free(bset);
93 static struct isl_mat *independent_bounds(struct isl_ctx *ctx,
94 struct isl_basic_set *bset)
97 struct isl_mat *dirs = NULL;
103 dim = isl_basic_set_n_dim(bset);
104 if (bset->n_ineq == 0)
105 return isl_mat_alloc(ctx, 0, dim);
107 dirs = isl_mat_alloc(ctx, dim, dim);
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) {
114 isl_seq_cpy(dirs->row[n], bset->ineq[j]+1, dirs->n_col);
116 pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col);
119 for (i = 0; i < n; ++i) {
121 pos_i = isl_seq_first_non_zero(dirs->row[i], dirs->n_col);
126 isl_seq_elim(dirs->row[n], dirs->row[i], pos,
128 pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col);
136 isl_int *t = dirs->row[n];
137 for (k = n; k > i; --k)
138 dirs->row[k] = dirs->row[k-1];
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.
154 static struct isl_vec *sample_eq(struct isl_basic_set *bset,
155 struct isl_vec *(*recurse)(struct isl_basic_set *))
158 struct isl_vec *sample;
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);
170 sample = isl_mat_vec_product(ctx, T, sample);
174 static struct isl_vec *sample_no_lineality(struct isl_basic_set *bset)
178 if (isl_basic_set_fast_is_empty(bset))
179 return empty_sample(bset);
181 return sample_eq(bset, sample_no_lineality);
182 dim = isl_basic_set_total_dim(bset);
184 return zero_sample(bset);
186 return interval_sample(bset);
188 return isl_pip_basic_set_sample(bset);
191 /* Compute an integer point in "bset" with a lineality space that
192 * is orthogonal to the constraints in "bounds".
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.
202 static struct isl_vec *sample_lineality(struct isl_basic_set *bset,
203 struct isl_mat *bounds)
205 struct isl_mat *U = NULL;
206 unsigned old_dim, new_dim;
207 struct isl_vec *sample;
210 if (!bset || !bounds)
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);
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));
224 isl_mat_free(ctx, bounds);
226 sample = sample_no_lineality(bset);
227 if (sample && sample->size != 0)
228 sample = isl_mat_vec_product(ctx, U, sample);
230 isl_mat_free(ctx, U);
233 isl_mat_free(ctx, bounds);
234 isl_mat_free(ctx, U);
235 isl_basic_set_free(bset);
239 struct isl_vec *isl_basic_set_sample(struct isl_basic_set *bset)
242 struct isl_mat *bounds;
248 if (isl_basic_set_fast_is_empty(bset))
249 return empty_sample(bset);
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);
256 return sample_eq(bset, isl_basic_set_sample);
258 return zero_sample(bset);
260 return interval_sample(bset);
261 bounds = independent_bounds(ctx, bset);
265 if (bounds->n_row == 0) {
266 isl_mat_free(ctx, bounds);
267 return zero_sample(bset);
269 if (bounds->n_row < dim)
270 return sample_lineality(bset, bounds);
272 isl_mat_free(ctx, bounds);
273 return sample_no_lineality(bset);
275 isl_basic_set_free(bset);