/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 | 29.6k | { |
22 | 29.6k | int i; |
23 | 29.6k | |
24 | 112k | for (i = 0; i < n; ++i82.5k ) |
25 | 82.5k | GBR_lp_get_alpha(lp, first + i, &alpha[i]); |
26 | 29.6k | } |
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 | 3.67k | { |
51 | 3.67k | unsigned dim; |
52 | 3.67k | struct isl_ctx *ctx; |
53 | 3.67k | struct isl_mat *B; |
54 | 3.67k | int i; |
55 | 3.67k | GBR_LP *lp = NULL; |
56 | 3.67k | GBR_type F_old, alpha, F_new; |
57 | 3.67k | int row; |
58 | 3.67k | isl_int tmp; |
59 | 3.67k | struct isl_vec *b_tmp; |
60 | 3.67k | GBR_type *F = NULL; |
61 | 3.67k | GBR_type *alpha_buffer[2] = { NULL, NULL }; |
62 | 3.67k | GBR_type *alpha_saved; |
63 | 3.67k | GBR_type F_saved; |
64 | 3.67k | int use_saved = 0; |
65 | 3.67k | isl_int mu[2]; |
66 | 3.67k | GBR_type mu_F[2]; |
67 | 3.67k | GBR_type two; |
68 | 3.67k | GBR_type one; |
69 | 3.67k | int empty = 0; |
70 | 3.67k | int fixed = 0; |
71 | 3.67k | int fixed_saved = 0; |
72 | 3.67k | int mu_fixed[2]; |
73 | 3.67k | int n_bounded; |
74 | 3.67k | int gbr_only_first; |
75 | 3.67k | |
76 | 3.67k | if (!tab) |
77 | 0 | return NULL; |
78 | 3.67k | |
79 | 3.67k | if (tab->empty) |
80 | 0 | return tab; |
81 | 3.67k | |
82 | 3.67k | ctx = tab->mat->ctx; |
83 | 3.67k | gbr_only_first = ctx->opt->gbr_only_first; |
84 | 3.67k | dim = tab->n_var; |
85 | 3.67k | B = tab->basis; |
86 | 3.67k | if (!B) |
87 | 0 | return tab; |
88 | 3.67k | |
89 | 3.67k | n_bounded = dim - tab->n_unbounded; |
90 | 3.67k | if (n_bounded <= tab->n_zero + 1) |
91 | 0 | return tab; |
92 | 3.67k | |
93 | 3.67k | isl_int_init(tmp); |
94 | 3.67k | isl_int_init(mu[0]); |
95 | 3.67k | isl_int_init(mu[1]); |
96 | 3.67k | |
97 | 3.67k | GBR_init(alpha); |
98 | 3.67k | GBR_init(F_old); |
99 | 3.67k | GBR_init(F_new); |
100 | 3.67k | GBR_init(F_saved); |
101 | 3.67k | GBR_init(mu_F[0]); |
102 | 3.67k | GBR_init(mu_F[1]); |
103 | 3.67k | GBR_init(two); |
104 | 3.67k | GBR_init(one); |
105 | 3.67k | |
106 | 3.67k | b_tmp = isl_vec_alloc(ctx, dim); |
107 | 3.67k | if (!b_tmp) |
108 | 0 | goto error; |
109 | 3.67k | |
110 | 3.67k | F = isl_alloc_array(ctx, GBR_type, n_bounded); |
111 | 3.67k | alpha_buffer[0] = isl_alloc_array(ctx, GBR_type, n_bounded); |
112 | 3.67k | alpha_buffer[1] = isl_alloc_array(ctx, GBR_type, n_bounded); |
113 | 3.67k | alpha_saved = alpha_buffer[0]; |
114 | 3.67k | |
115 | 3.67k | if (!F || !alpha_buffer[0] || !alpha_buffer[1]) |
116 | 0 | goto error; |
117 | 3.67k | |
118 | 24.0k | for (i = 0; 3.67k i < n_bounded; ++i20.3k ) { |
119 | 20.3k | GBR_init(F[i]); |
120 | 20.3k | GBR_init(alpha_buffer[0][i]); |
121 | 20.3k | GBR_init(alpha_buffer[1][i]); |
122 | 20.3k | } |
123 | 3.67k | |
124 | 3.67k | GBR_set_ui(two, 2); |
125 | 3.67k | GBR_set_ui(one, 1); |
126 | 3.67k | |
127 | 3.67k | lp = GBR_lp_init(tab); |
128 | 3.67k | if (!lp) |
129 | 0 | goto error; |
130 | 3.67k | |
131 | 3.67k | i = tab->n_zero; |
132 | 3.67k | |
133 | 3.67k | GBR_lp_set_obj(lp, B->row[1+i]+1, dim); |
134 | 3.67k | ctx->stats->gbr_solved_lps++; |
135 | 3.67k | if (GBR_lp_solve(lp) < 0) |
136 | 0 | goto error; |
137 | 3.67k | GBR_lp_get_obj_val(lp, &F[i]); |
138 | 3.67k | |
139 | 3.67k | 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 | 3.67k | |
149 | 41.0k | do 3.67k { |
150 | 41.0k | 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 | 41.0k | if (use_saved) { |
160 | 14.0k | row = GBR_lp_next_row(lp); |
161 | 14.0k | GBR_set(F_new, F_saved); |
162 | 14.0k | fixed = fixed_saved; |
163 | 14.0k | GBR_set(alpha, alpha_saved[i]); |
164 | 27.0k | } else { |
165 | 27.0k | row = GBR_lp_add_row(lp, B->row[1+i]+1, dim); |
166 | 27.0k | GBR_lp_set_obj(lp, B->row[1+i+1]+1, dim); |
167 | 27.0k | ctx->stats->gbr_solved_lps++; |
168 | 27.0k | if (GBR_lp_solve(lp) < 0) |
169 | 0 | goto error; |
170 | 27.0k | GBR_lp_get_obj_val(lp, &F_new); |
171 | 27.0k | fixed = GBR_lp_is_fixed(lp); |
172 | 27.0k | |
173 | 27.0k | GBR_lp_get_alpha(lp, row, &alpha); |
174 | 27.0k | |
175 | 27.0k | if (i > 0) |
176 | 20.3k | save_alpha(lp, row-i, i, alpha_saved); |
177 | 27.0k | |
178 | 27.0k | if (GBR_lp_del_row(lp) < 0) |
179 | 0 | goto error; |
180 | 41.0k | } |
181 | 41.0k | GBR_set(F[i+1], F_new); |
182 | 41.0k | |
183 | 41.0k | GBR_floor(mu[0], alpha); |
184 | 41.0k | GBR_ceil(mu[1], alpha); |
185 | 41.0k | |
186 | 41.0k | if (isl_int_eq(mu[0], mu[1])) |
187 | 41.0k | isl_int_set32.7k (tmp, mu[0]); |
188 | 41.0k | else { |
189 | 8.39k | int j; |
190 | 8.39k | |
191 | 25.1k | for (j = 0; j <= 1; ++j16.7k ) { |
192 | 16.7k | isl_int_set(tmp, mu[j]); |
193 | 16.7k | isl_seq_combine(b_tmp->el, |
194 | 16.7k | ctx->one, B->row[1+i+1]+1, |
195 | 16.7k | tmp, B->row[1+i]+1, dim); |
196 | 16.7k | GBR_lp_set_obj(lp, b_tmp->el, dim); |
197 | 16.7k | ctx->stats->gbr_solved_lps++; |
198 | 16.7k | if (GBR_lp_solve(lp) < 0) |
199 | 0 | goto error; |
200 | 16.7k | GBR_lp_get_obj_val(lp, &mu_F[j]); |
201 | 16.7k | mu_fixed[j] = GBR_lp_is_fixed(lp); |
202 | 16.7k | if (i > 0) |
203 | 9.33k | save_alpha(lp, row-i, i, alpha_buffer[j]); |
204 | 16.7k | } |
205 | 8.39k | |
206 | 8.39k | if (GBR_lt(mu_F[0], mu_F[1])) |
207 | 8.39k | j = 04.55k ; |
208 | 3.83k | else |
209 | 3.83k | j = 1; |
210 | 8.39k | |
211 | 8.39k | isl_int_set(tmp, mu[j]); |
212 | 8.39k | GBR_set(F_new, mu_F[j]); |
213 | 8.39k | fixed = mu_fixed[j]; |
214 | 8.39k | alpha_saved = alpha_buffer[j]; |
215 | 8.39k | } |
216 | 41.0k | isl_seq_combine(B->row[1+i+1]+1, ctx->one, B->row[1+i+1]+1, |
217 | 41.0k | tmp, B->row[1+i]+1, dim); |
218 | 41.0k | |
219 | 41.0k | 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 | 41.0k | |
229 | 41.0k | GBR_set(F_old, F[i]); |
230 | 41.0k | |
231 | 41.0k | use_saved = 0; |
232 | 41.0k | /* mu_F[0] = 4 * F_new; mu_F[1] = 3 * F_old */ |
233 | 41.0k | GBR_set_ui(mu_F[0], 4); |
234 | 41.0k | GBR_mul(mu_F[0], mu_F[0], F_new); |
235 | 41.0k | GBR_set_ui(mu_F[1], 3); |
236 | 41.0k | GBR_mul(mu_F[1], mu_F[1], F_old); |
237 | 41.0k | if (GBR_lt(mu_F[0], mu_F[1])) { |
238 | 21.2k | B = isl_mat_swap_rows(B, 1 + i, 1 + i + 1); |
239 | 21.2k | if (i > tab->n_zero) { |
240 | 14.0k | use_saved = 1; |
241 | 14.0k | GBR_set(F_saved, F_new); |
242 | 14.0k | fixed_saved = fixed; |
243 | 14.0k | if (GBR_lp_del_row(lp) < 0) |
244 | 0 | goto error; |
245 | 14.0k | --i; |
246 | 14.0k | } else { |
247 | 7.18k | GBR_set(F[tab->n_zero], F_new); |
248 | 7.18k | if (gbr_only_first && GBR_lt(F[tab->n_zero], two)) |
249 | 7.18k | break2.41k ; |
250 | 4.76k | |
251 | 4.76k | 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 | 4.76k | } |
261 | 21.2k | } else { |
262 | 19.8k | GBR_lp_add_row(lp, B->row[1+i]+1, dim); |
263 | 19.8k | ++i; |
264 | 19.8k | } |
265 | 41.0k | } while (i < n_bounded - 138.6k ); |
266 | 3.67k | |
267 | 3.67k | 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 | 3.67k | |
276 | 3.67k | GBR_lp_delete(lp); |
277 | 3.67k | |
278 | 3.67k | if (alpha_buffer[1]) |
279 | 24.0k | for (i = 0; 3.67k i < n_bounded; ++i20.3k ) { |
280 | 20.3k | GBR_clear(F[i]); |
281 | 20.3k | GBR_clear(alpha_buffer[0][i]); |
282 | 20.3k | GBR_clear(alpha_buffer[1][i]); |
283 | 20.3k | } |
284 | 3.67k | free(F); |
285 | 3.67k | free(alpha_buffer[0]); |
286 | 3.67k | free(alpha_buffer[1]); |
287 | 3.67k | |
288 | 3.67k | isl_vec_free(b_tmp); |
289 | 3.67k | |
290 | 3.67k | GBR_clear(alpha); |
291 | 3.67k | GBR_clear(F_old); |
292 | 3.67k | GBR_clear(F_new); |
293 | 3.67k | GBR_clear(F_saved); |
294 | 3.67k | GBR_clear(mu_F[0]); |
295 | 3.67k | GBR_clear(mu_F[1]); |
296 | 3.67k | GBR_clear(two); |
297 | 3.67k | GBR_clear(one); |
298 | 3.67k | |
299 | 3.67k | isl_int_clear(tmp); |
300 | 3.67k | isl_int_clear(mu[0]); |
301 | 3.67k | isl_int_clear(mu[1]); |
302 | 3.67k | |
303 | 3.67k | tab->basis = B; |
304 | 3.67k | |
305 | 3.67k | return tab; |
306 | 3.67k | } |
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 | } |