/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/basis_reduction_templ.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Copyright 2006-2007 Universiteit Leiden |
3 | | * Copyright 2008-2009 Katholieke Universiteit Leuven |
4 | | * |
5 | | * Use of this software is governed by the MIT license |
6 | | * |
7 | | * Written by Sven Verdoolaege, Leiden Institute of Advanced Computer Science, |
8 | | * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands |
9 | | * and K.U.Leuven, Departement Computerwetenschappen, Celestijnenlaan 200A, |
10 | | * B-3001 Leuven, Belgium |
11 | | */ |
12 | | |
13 | | #include <stdlib.h> |
14 | | #include <isl_ctx_private.h> |
15 | | #include <isl_map_private.h> |
16 | | #include <isl_vec_private.h> |
17 | | #include <isl_options_private.h> |
18 | | #include "isl_basis_reduction.h" |
19 | | |
20 | | static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha) |
21 | 72.4k | { |
22 | 72.4k | int i; |
23 | 72.4k | |
24 | 277k | for (i = 0; i < n; ++i205k ) |
25 | 205k | GBR_lp_get_alpha(lp, first + i, &alpha[i]); |
26 | 72.4k | } |
27 | | |
28 | | /* Compute a reduced basis for the set represented by the tableau "tab". |
29 | | * tab->basis, which must be initialized by the calling function to an affine |
30 | | * unimodular basis, is updated to reflect the reduced basis. |
31 | | * The first tab->n_zero rows of the basis (ignoring the constant row) |
32 | | * are assumed to correspond to equalities and are left untouched. |
33 | | * tab->n_zero is updated to reflect any additional equalities that |
34 | | * have been detected in the first rows of the new basis. |
35 | | * The final tab->n_unbounded rows of the basis are assumed to correspond |
36 | | * to unbounded directions and are also left untouched. |
37 | | * In particular this means that the remaining rows are assumed to |
38 | | * correspond to bounded directions. |
39 | | * |
40 | | * This function implements the algorithm described in |
41 | | * "An Implementation of the Generalized Basis Reduction Algorithm |
42 | | * for Integer Programming" of Cook el al. to compute a reduced basis. |
43 | | * We use \epsilon = 1/4. |
44 | | * |
45 | | * If ctx->opt->gbr_only_first is set, the user is only interested |
46 | | * in the first direction. In this case we stop the basis reduction when |
47 | | * the width in the first direction becomes smaller than 2. |
48 | | */ |
49 | | struct isl_tab *isl_tab_compute_reduced_basis(struct isl_tab *tab) |
50 | 6.84k | { |
51 | 6.84k | unsigned dim; |
52 | 6.84k | struct isl_ctx *ctx; |
53 | 6.84k | struct isl_mat *B; |
54 | 6.84k | int i; |
55 | 6.84k | GBR_LP *lp = NULL; |
56 | 6.84k | GBR_type F_old, alpha, F_new; |
57 | 6.84k | int row; |
58 | 6.84k | isl_int tmp; |
59 | 6.84k | struct isl_vec *b_tmp; |
60 | 6.84k | GBR_type *F = NULL; |
61 | 6.84k | GBR_type *alpha_buffer[2] = { NULL, NULL }; |
62 | 6.84k | GBR_type *alpha_saved; |
63 | 6.84k | GBR_type F_saved; |
64 | 6.84k | int use_saved = 0; |
65 | 6.84k | isl_int mu[2]; |
66 | 6.84k | GBR_type mu_F[2]; |
67 | 6.84k | GBR_type two; |
68 | 6.84k | GBR_type one; |
69 | 6.84k | int empty = 0; |
70 | 6.84k | int fixed = 0; |
71 | 6.84k | int fixed_saved = 0; |
72 | 6.84k | int mu_fixed[2]; |
73 | 6.84k | int n_bounded; |
74 | 6.84k | int gbr_only_first; |
75 | 6.84k | |
76 | 6.84k | if (!tab) |
77 | 0 | return NULL; |
78 | 6.84k | |
79 | 6.84k | if (tab->empty) |
80 | 0 | return tab; |
81 | 6.84k | |
82 | 6.84k | ctx = tab->mat->ctx; |
83 | 6.84k | gbr_only_first = ctx->opt->gbr_only_first; |
84 | 6.84k | dim = tab->n_var; |
85 | 6.84k | B = tab->basis; |
86 | 6.84k | if (!B) |
87 | 0 | return tab; |
88 | 6.84k | |
89 | 6.84k | n_bounded = dim - tab->n_unbounded; |
90 | 6.84k | if (n_bounded <= tab->n_zero + 1) |
91 | 0 | return tab; |
92 | 6.84k | |
93 | 6.84k | isl_int_init(tmp); |
94 | 6.84k | isl_int_init(mu[0]); |
95 | 6.84k | isl_int_init(mu[1]); |
96 | 6.84k | |
97 | 6.84k | GBR_init(alpha); |
98 | 6.84k | GBR_init(F_old); |
99 | 6.84k | GBR_init(F_new); |
100 | 6.84k | GBR_init(F_saved); |
101 | 6.84k | GBR_init(mu_F[0]); |
102 | 6.84k | GBR_init(mu_F[1]); |
103 | 6.84k | GBR_init(two); |
104 | 6.84k | GBR_init(one); |
105 | 6.84k | |
106 | 6.84k | b_tmp = isl_vec_alloc(ctx, dim); |
107 | 6.84k | if (!b_tmp) |
108 | 0 | goto error; |
109 | 6.84k | |
110 | 6.84k | F = isl_alloc_array(ctx, GBR_type, n_bounded); |
111 | 6.84k | alpha_buffer[0] = isl_alloc_array(ctx, GBR_type, n_bounded); |
112 | 6.84k | alpha_buffer[1] = isl_alloc_array(ctx, GBR_type, n_bounded); |
113 | 6.84k | alpha_saved = alpha_buffer[0]; |
114 | 6.84k | |
115 | 6.84k | if (!F || !alpha_buffer[0] || !alpha_buffer[1]) |
116 | 0 | goto error; |
117 | 6.84k | |
118 | 47.9k | for (i = 0; 6.84k i < n_bounded; ++i41.0k ) { |
119 | 41.0k | GBR_init(F[i]); |
120 | 41.0k | GBR_init(alpha_buffer[0][i]); |
121 | 41.0k | GBR_init(alpha_buffer[1][i]); |
122 | 41.0k | } |
123 | 6.84k | |
124 | 6.84k | GBR_set_ui(two, 2); |
125 | 6.84k | GBR_set_ui(one, 1); |
126 | 6.84k | |
127 | 6.84k | lp = GBR_lp_init(tab); |
128 | 6.84k | if (!lp) |
129 | 0 | goto error; |
130 | 6.84k | |
131 | 6.84k | i = tab->n_zero; |
132 | 6.84k | |
133 | 6.84k | GBR_lp_set_obj(lp, B->row[1+i]+1, dim); |
134 | 6.84k | ctx->stats->gbr_solved_lps++; |
135 | 6.84k | if (GBR_lp_solve(lp) < 0) |
136 | 0 | goto error; |
137 | 6.84k | GBR_lp_get_obj_val(lp, &F[i]); |
138 | 6.84k | |
139 | 6.84k | if (GBR_lt(F[i], one)) { |
140 | 0 | if (!GBR_is_zero(F[i])) { |
141 | 0 | empty = GBR_lp_cut(lp, B->row[1+i]+1); |
142 | 0 | if (empty) |
143 | 0 | goto done; |
144 | 0 | GBR_set_ui(F[i], 0); |
145 | 0 | } |
146 | 0 | tab->n_zero++; |
147 | 0 | } |
148 | 6.84k | |
149 | 107k | do 6.84k { |
150 | 107k | if (i+1 == tab->n_zero) { |
151 | 0 | GBR_lp_set_obj(lp, B->row[1+i+1]+1, dim); |
152 | 0 | ctx->stats->gbr_solved_lps++; |
153 | 0 | if (GBR_lp_solve(lp) < 0) |
154 | 0 | goto error; |
155 | 0 | GBR_lp_get_obj_val(lp, &F_new); |
156 | 0 | fixed = GBR_lp_is_fixed(lp); |
157 | 0 | GBR_set_ui(alpha, 0); |
158 | 0 | } else |
159 | 107k | if (use_saved) { |
160 | 39.4k | row = GBR_lp_next_row(lp); |
161 | 39.4k | GBR_set(F_new, F_saved); |
162 | 39.4k | fixed = fixed_saved; |
163 | 39.4k | GBR_set(alpha, alpha_saved[i]); |
164 | 68.1k | } else { |
165 | 68.1k | row = GBR_lp_add_row(lp, B->row[1+i]+1, dim); |
166 | 68.1k | GBR_lp_set_obj(lp, B->row[1+i+1]+1, dim); |
167 | 68.1k | ctx->stats->gbr_solved_lps++; |
168 | 68.1k | if (GBR_lp_solve(lp) < 0) |
169 | 0 | goto error; |
170 | 68.1k | GBR_lp_get_obj_val(lp, &F_new); |
171 | 68.1k | fixed = GBR_lp_is_fixed(lp); |
172 | 68.1k | |
173 | 68.1k | GBR_lp_get_alpha(lp, row, &alpha); |
174 | 68.1k | |
175 | 68.1k | if (i > 0) |
176 | 54.8k | save_alpha(lp, row-i, i, alpha_saved); |
177 | 68.1k | |
178 | 68.1k | if (GBR_lp_del_row(lp) < 0) |
179 | 0 | goto error; |
180 | 107k | } |
181 | 107k | GBR_set(F[i+1], F_new); |
182 | 107k | |
183 | 107k | GBR_floor(mu[0], alpha); |
184 | 107k | GBR_ceil(mu[1], alpha); |
185 | 107k | |
186 | 107k | if (isl_int_eq(mu[0], mu[1])) |
187 | 107k | isl_int_set93.7k (tmp, mu[0]); |
188 | 107k | else { |
189 | 13.8k | int j; |
190 | 13.8k | |
191 | 41.6k | for (j = 0; j <= 1; ++j27.7k ) { |
192 | 27.7k | isl_int_set(tmp, mu[j]); |
193 | 27.7k | isl_seq_combine(b_tmp->el, |
194 | 27.7k | ctx->one, B->row[1+i+1]+1, |
195 | 27.7k | tmp, B->row[1+i]+1, dim); |
196 | 27.7k | GBR_lp_set_obj(lp, b_tmp->el, dim); |
197 | 27.7k | ctx->stats->gbr_solved_lps++; |
198 | 27.7k | if (GBR_lp_solve(lp) < 0) |
199 | 0 | goto error; |
200 | 27.7k | GBR_lp_get_obj_val(lp, &mu_F[j]); |
201 | 27.7k | mu_fixed[j] = GBR_lp_is_fixed(lp); |
202 | 27.7k | if (i > 0) |
203 | 17.5k | save_alpha(lp, row-i, i, alpha_buffer[j]); |
204 | 27.7k | } |
205 | 13.8k | |
206 | 13.8k | if (GBR_lt(mu_F[0], mu_F[1])) |
207 | 13.8k | j = 07.88k ; |
208 | 5.99k | else |
209 | 5.99k | j = 1; |
210 | 13.8k | |
211 | 13.8k | isl_int_set(tmp, mu[j]); |
212 | 13.8k | GBR_set(F_new, mu_F[j]); |
213 | 13.8k | fixed = mu_fixed[j]; |
214 | 13.8k | alpha_saved = alpha_buffer[j]; |
215 | 13.8k | } |
216 | 107k | isl_seq_combine(B->row[1+i+1]+1, ctx->one, B->row[1+i+1]+1, |
217 | 107k | tmp, B->row[1+i]+1, dim); |
218 | 107k | |
219 | 107k | if (i+1 == tab->n_zero && fixed0 ) { |
220 | 0 | if (!GBR_is_zero(F[i+1])) { |
221 | 0 | empty = GBR_lp_cut(lp, B->row[1+i+1]+1); |
222 | 0 | if (empty) |
223 | 0 | goto done; |
224 | 0 | GBR_set_ui(F[i+1], 0); |
225 | 0 | } |
226 | 0 | tab->n_zero++; |
227 | 0 | } |
228 | 107k | |
229 | 107k | GBR_set(F_old, F[i]); |
230 | 107k | |
231 | 107k | use_saved = 0; |
232 | 107k | /* mu_F[0] = 4 * F_new; mu_F[1] = 3 * F_old */ |
233 | 107k | GBR_set_ui(mu_F[0], 4); |
234 | 107k | GBR_mul(mu_F[0], mu_F[0], F_new); |
235 | 107k | GBR_set_ui(mu_F[1], 3); |
236 | 107k | GBR_mul(mu_F[1], mu_F[1], F_old); |
237 | 107k | if (GBR_lt(mu_F[0], mu_F[1])) { |
238 | 52.3k | B = isl_mat_swap_rows(B, 1 + i, 1 + i + 1); |
239 | 52.3k | if (i > tab->n_zero) { |
240 | 39.4k | use_saved = 1; |
241 | 39.4k | GBR_set(F_saved, F_new); |
242 | 39.4k | fixed_saved = fixed; |
243 | 39.4k | if (GBR_lp_del_row(lp) < 0) |
244 | 0 | goto error; |
245 | 39.4k | --i; |
246 | 39.4k | } else { |
247 | 12.8k | GBR_set(F[tab->n_zero], F_new); |
248 | 12.8k | if (gbr_only_first && GBR_lt(F[tab->n_zero], two)) |
249 | 12.8k | break3.74k ; |
250 | 9.13k | |
251 | 9.13k | if (fixed) { |
252 | 0 | if (!GBR_is_zero(F[tab->n_zero])) { |
253 | 0 | empty = GBR_lp_cut(lp, B->row[1+tab->n_zero]+1); |
254 | 0 | if (empty) |
255 | 0 | goto done; |
256 | 0 | GBR_set_ui(F[tab->n_zero], 0); |
257 | 0 | } |
258 | 0 | tab->n_zero++; |
259 | 0 | } |
260 | 9.13k | } |
261 | 55.3k | } else { |
262 | 55.3k | GBR_lp_add_row(lp, B->row[1+i]+1, dim); |
263 | 55.3k | ++i; |
264 | 55.3k | } |
265 | 107k | } while (i < n_bounded - 1103k ); |
266 | 6.84k | |
267 | 6.84k | if (0) { |
268 | 0 | done: |
269 | 0 | if (empty < 0) { |
270 | 0 | error: |
271 | 0 | isl_mat_free(B); |
272 | 0 | B = NULL; |
273 | 0 | } |
274 | 0 | } |
275 | 6.84k | |
276 | 6.84k | GBR_lp_delete(lp); |
277 | 6.84k | |
278 | 6.84k | if (alpha_buffer[1]) |
279 | 47.9k | for (i = 0; 6.84k i < n_bounded; ++i41.0k ) { |
280 | 41.0k | GBR_clear(F[i]); |
281 | 41.0k | GBR_clear(alpha_buffer[0][i]); |
282 | 41.0k | GBR_clear(alpha_buffer[1][i]); |
283 | 41.0k | } |
284 | 6.84k | free(F); |
285 | 6.84k | free(alpha_buffer[0]); |
286 | 6.84k | free(alpha_buffer[1]); |
287 | 6.84k | |
288 | 6.84k | isl_vec_free(b_tmp); |
289 | 6.84k | |
290 | 6.84k | GBR_clear(alpha); |
291 | 6.84k | GBR_clear(F_old); |
292 | 6.84k | GBR_clear(F_new); |
293 | 6.84k | GBR_clear(F_saved); |
294 | 6.84k | GBR_clear(mu_F[0]); |
295 | 6.84k | GBR_clear(mu_F[1]); |
296 | 6.84k | GBR_clear(two); |
297 | 6.84k | GBR_clear(one); |
298 | 6.84k | |
299 | 6.84k | isl_int_clear(tmp); |
300 | 6.84k | isl_int_clear(mu[0]); |
301 | 6.84k | isl_int_clear(mu[1]); |
302 | 6.84k | |
303 | 6.84k | tab->basis = B; |
304 | 6.84k | |
305 | 6.84k | return tab; |
306 | 6.84k | } |
307 | | |
308 | | /* Compute an affine form of a reduced basis of the given basic |
309 | | * non-parametric set, which is assumed to be bounded and not |
310 | | * include any integer divisions. |
311 | | * The first column and the first row correspond to the constant term. |
312 | | * |
313 | | * If the input contains any equalities, we first create an initial |
314 | | * basis with the equalities first. Otherwise, we start off with |
315 | | * the identity matrix. |
316 | | */ |
317 | | __isl_give isl_mat *isl_basic_set_reduced_basis(__isl_keep isl_basic_set *bset) |
318 | 0 | { |
319 | 0 | struct isl_mat *basis; |
320 | 0 | struct isl_tab *tab; |
321 | 0 |
|
322 | 0 | if (!bset) |
323 | 0 | return NULL; |
324 | 0 | |
325 | 0 | if (isl_basic_set_dim(bset, isl_dim_div) != 0) |
326 | 0 | isl_die(bset->ctx, isl_error_invalid, |
327 | 0 | "no integer division allowed", return NULL); |
328 | 0 | if (isl_basic_set_dim(bset, isl_dim_param) != 0) |
329 | 0 | isl_die(bset->ctx, isl_error_invalid, |
330 | 0 | "no parameters allowed", return NULL); |
331 | 0 |
|
332 | 0 | tab = isl_tab_from_basic_set(bset, 0); |
333 | 0 | if (!tab) |
334 | 0 | return NULL; |
335 | 0 | |
336 | 0 | if (bset->n_eq == 0) |
337 | 0 | tab->basis = isl_mat_identity(bset->ctx, 1 + tab->n_var); |
338 | 0 | else { |
339 | 0 | isl_mat *eq; |
340 | 0 | unsigned nvar = isl_basic_set_total_dim(bset); |
341 | 0 | eq = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, bset->n_eq, |
342 | 0 | 1, nvar); |
343 | 0 | eq = isl_mat_left_hermite(eq, 0, NULL, &tab->basis); |
344 | 0 | tab->basis = isl_mat_lin_to_aff(tab->basis); |
345 | 0 | tab->n_zero = bset->n_eq; |
346 | 0 | isl_mat_free(eq); |
347 | 0 | } |
348 | 0 | tab = isl_tab_compute_reduced_basis(tab); |
349 | 0 | if (!tab) |
350 | 0 | return NULL; |
351 | 0 | |
352 | 0 | basis = isl_mat_copy(tab->basis); |
353 | 0 |
|
354 | 0 | isl_tab_free(tab); |
355 | 0 |
|
356 | 0 | return basis; |
357 | 0 | } |