3 #include "isl_piplib.h"
4 #include "isl_sample_piplib.h"
6 static void swap_inequality(struct isl_basic_set *bset, int a, int b)
8 isl_int *t = bset->ineq[a];
9 bset->ineq[a] = bset->ineq[b];
13 static struct isl_mat *independent_bounds(struct isl_ctx *ctx,
14 struct isl_basic_set *bset)
17 struct isl_mat *dirs = NULL;
18 struct isl_mat *bounds = NULL;
23 bounds = isl_mat_alloc(ctx, 1+bset->dim, 1+bset->dim);
27 isl_int_set_si(bounds->row[0][0], 1);
28 isl_seq_clr(bounds->row[0]+1, bset->dim);
31 if (bset->n_ineq == 0)
34 dirs = isl_mat_alloc(ctx, bset->dim, bset->dim);
36 isl_mat_free(ctx, bounds);
39 isl_seq_cpy(dirs->row[0], bset->ineq[0]+1, dirs->n_col);
40 isl_seq_cpy(bounds->row[1], bset->ineq[0], bounds->n_col);
41 for (j = 1, n = 1; n < bset->dim && j < bset->n_ineq; ++j) {
44 isl_seq_cpy(dirs->row[n], bset->ineq[j]+1, dirs->n_col);
46 pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col);
49 for (i = 0; i < n; ++i) {
51 pos_i = isl_seq_first_non_zero(dirs->row[i], dirs->n_col);
56 isl_seq_elim(dirs->row[n], dirs->row[i], pos,
58 pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col);
66 isl_int *t = dirs->row[n];
67 for (k = n; k > i; --k)
68 dirs->row[k] = dirs->row[k-1];
72 isl_seq_cpy(bounds->row[n], bset->ineq[j], bounds->n_col);
74 isl_mat_free(ctx, dirs);
79 /* Skew into positive orthant and project out lineality space */
80 static struct isl_basic_set *isl_basic_set_skew_to_positive_orthant(
81 struct isl_ctx *ctx, struct isl_basic_set *bset,
84 struct isl_mat *U = NULL;
85 struct isl_mat *bounds = NULL;
87 unsigned old_dim, new_dim;
93 isl_assert(ctx, bset->nparam == 0, goto error);
94 isl_assert(ctx, bset->n_div == 0, goto error);
95 isl_assert(ctx, bset->n_eq == 0, goto error);
97 /* Try to move (multiples of) unit rows up. */
98 for (i = 0, j = 0; i < bset->n_ineq; ++i) {
99 int pos = isl_seq_first_non_zero(bset->ineq[i]+1,
103 if (isl_seq_first_non_zero(bset->ineq[i]+1+pos+1,
104 bset->dim-pos-1) >= 0)
107 swap_inequality(bset, i, j);
110 bounds = independent_bounds(ctx, bset);
114 new_dim = bounds->n_row - 1;
115 bounds = isl_mat_left_hermite(ctx, bounds, 1, &U, NULL);
118 U = isl_mat_drop_cols(ctx, U, 1 + new_dim, old_dim - new_dim);
119 bset = isl_basic_set_preimage(ctx, bset, isl_mat_copy(ctx, U));
123 isl_mat_free(ctx, bounds);
126 isl_mat_free(ctx, bounds);
127 isl_mat_free(ctx, U);
128 isl_basic_set_free(ctx, bset);
132 struct isl_vec *isl_pip_basic_set_sample(struct isl_ctx *ctx,
133 struct isl_basic_set *bset)
135 PipOptions *options = NULL;
136 PipMatrix *domain = NULL;
137 PipQuast *sol = NULL;
138 struct isl_vec *vec = NULL;
144 isl_assert(ctx, bset->nparam == 0, goto error);
145 isl_assert(ctx, bset->n_div == 0, goto error);
146 bset = isl_basic_set_skew_to_positive_orthant(ctx, bset, &T);
150 domain = isl_basic_map_to_pip((struct isl_basic_map *)bset, 0, 0, 0);
154 options = pip_options_init();
157 sol = pip_solve(domain, NULL, -1, options);
161 vec = isl_vec_alloc(ctx, 0);
162 isl_mat_free(ctx, T);
166 vec = isl_vec_alloc(ctx, 1 + dim);
169 isl_int_set_si(vec->block.data[0], 1);
170 for (i = 0, l = sol->list; l && i < dim; ++i, l = l->next) {
171 isl_seq_cpy_from_pip(&vec->block.data[1+i],
172 &l->vector->the_vector[0], 1);
173 isl_assert(ctx, !entier_zero_p(l->vector->the_deno[0]),
176 isl_assert(ctx, i == dim, goto error);
177 vec = isl_mat_vec_product(ctx, T, vec);
181 pip_options_free(options);
182 pip_matrix_free(domain);
184 isl_basic_set_free(ctx, bset);
187 isl_vec_free(ctx, vec);
188 isl_basic_set_free(ctx, bset);
192 pip_matrix_free(domain);