/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/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 | 21.3k | { |
22 | 21.3k | int i; |
23 | 21.3k | |
24 | 82.2k | for (i = 0; i < n82.2k ; ++i60.9k ) |
25 | 60.9k | GBR_lp_get_alpha(lp, first + i, &alpha[i]); |
26 | 21.3k | } |
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 | 2.84k | { |
51 | 2.84k | unsigned dim; |
52 | 2.84k | struct isl_ctx *ctx; |
53 | 2.84k | struct isl_mat *B; |
54 | 2.84k | int i; |
55 | 2.84k | GBR_LP *lp = NULL; |
56 | 2.84k | GBR_type F_old, alpha, F_new; |
57 | 2.84k | int row; |
58 | 2.84k | isl_int tmp; |
59 | 2.84k | struct isl_vec *b_tmp; |
60 | 2.84k | GBR_type *F = NULL; |
61 | 2.84k | GBR_type *alpha_buffer[2] = { NULL, NULL }; |
62 | 2.84k | GBR_type *alpha_saved; |
63 | 2.84k | GBR_type F_saved; |
64 | 2.84k | int use_saved = 0; |
65 | 2.84k | isl_int mu[2]; |
66 | 2.84k | GBR_type mu_F[2]; |
67 | 2.84k | GBR_type two; |
68 | 2.84k | GBR_type one; |
69 | 2.84k | int empty = 0; |
70 | 2.84k | int fixed = 0; |
71 | 2.84k | int fixed_saved = 0; |
72 | 2.84k | int mu_fixed[2]; |
73 | 2.84k | int n_bounded; |
74 | 2.84k | int gbr_only_first; |
75 | 2.84k | |
76 | 2.84k | if (!tab) |
77 | 0 | return NULL; |
78 | 2.84k | |
79 | 2.84k | if (2.84k tab->empty2.84k ) |
80 | 0 | return tab; |
81 | 2.84k | |
82 | 2.84k | ctx = tab->mat->ctx; |
83 | 2.84k | gbr_only_first = ctx->opt->gbr_only_first; |
84 | 2.84k | dim = tab->n_var; |
85 | 2.84k | B = tab->basis; |
86 | 2.84k | if (!B) |
87 | 0 | return tab; |
88 | 2.84k | |
89 | 2.84k | n_bounded = dim - tab->n_unbounded; |
90 | 2.84k | if (n_bounded <= tab->n_zero + 1) |
91 | 0 | return tab; |
92 | 2.84k | |
93 | 2.84k | isl_int_init2.84k (tmp); |
94 | 2.84k | isl_int_init(mu[0]); |
95 | 2.84k | isl_int_init(mu[1]); |
96 | 2.84k | |
97 | 2.84k | GBR_init(alpha); |
98 | 2.84k | GBR_init(F_old); |
99 | 2.84k | GBR_init(F_new); |
100 | 2.84k | GBR_init(F_saved); |
101 | 2.84k | GBR_init(mu_F[0]); |
102 | 2.84k | GBR_init(mu_F[1]); |
103 | 2.84k | GBR_init(two); |
104 | 2.84k | GBR_init(one); |
105 | 2.84k | |
106 | 2.84k | b_tmp = isl_vec_alloc(ctx, dim); |
107 | 2.84k | if (!b_tmp) |
108 | 0 | goto error; |
109 | 2.84k | |
110 | 2.84k | F = 2.84k isl_alloc_array2.84k (ctx, GBR_type, n_bounded); |
111 | 2.84k | alpha_buffer[0] = isl_alloc_array(ctx, GBR_type, n_bounded); |
112 | 2.84k | alpha_buffer[1] = isl_alloc_array(ctx, GBR_type, n_bounded); |
113 | 2.84k | alpha_saved = alpha_buffer[0]; |
114 | 2.84k | |
115 | 2.84k | if (!F || 2.84k !alpha_buffer[0]2.84k || !alpha_buffer[1]2.84k ) |
116 | 0 | goto error; |
117 | 2.84k | |
118 | 18.0k | for (i = 0; 2.84k i < n_bounded18.0k ; ++i15.1k ) { |
119 | 15.1k | GBR_init(F[i]); |
120 | 15.1k | GBR_init(alpha_buffer[0][i]); |
121 | 15.1k | GBR_init(alpha_buffer[1][i]); |
122 | 15.1k | } |
123 | 2.84k | |
124 | 2.84k | GBR_set_ui(two, 2); |
125 | 2.84k | GBR_set_ui(one, 1); |
126 | 2.84k | |
127 | 2.84k | lp = GBR_lp_init(tab); |
128 | 2.84k | if (!lp) |
129 | 0 | goto error; |
130 | 2.84k | |
131 | 2.84k | i = tab->n_zero; |
132 | 2.84k | |
133 | 2.84k | GBR_lp_set_obj(lp, B->row[1+i]+1, dim); |
134 | 2.84k | ctx->stats->gbr_solved_lps++; |
135 | 2.84k | if (GBR_lp_solve2.84k (lp) < 02.84k ) |
136 | 0 | goto error; |
137 | 2.84k | GBR_lp_get_obj_val2.84k (lp, &F[i]); |
138 | 2.84k | |
139 | 2.84k | if (GBR_lt2.84k (F[i], one)) { |
140 | 0 | if (!0 GBR_is_zero0 (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_ui0 (F[i], 0); |
145 | 0 | } |
146 | 0 | tab->n_zero++; |
147 | 0 | } |
148 | 2.84k | |
149 | 2.84k | do 2.84k { |
150 | 29.9k | if (i+1 == tab->n_zero29.9k ) { |
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_solve0 (lp) < 00 ) |
154 | 0 | goto error; |
155 | 0 | GBR_lp_get_obj_val0 (lp, &F_new); |
156 | 0 | fixed = GBR_lp_is_fixed(lp); |
157 | 0 | GBR_set_ui(alpha, 0); |
158 | 0 | } else |
159 | 29.9k | if (29.9k use_saved29.9k ) { |
160 | 10.0k | row = GBR_lp_next_row(lp); |
161 | 10.0k | GBR_set(F_new, F_saved); |
162 | 10.0k | fixed = fixed_saved; |
163 | 10.0k | GBR_set(alpha, alpha_saved[i]); |
164 | 29.9k | } else { |
165 | 19.8k | row = GBR_lp_add_row(lp, B->row[1+i]+1, dim); |
166 | 19.8k | GBR_lp_set_obj(lp, B->row[1+i+1]+1, dim); |
167 | 19.8k | ctx->stats->gbr_solved_lps++; |
168 | 19.8k | if (GBR_lp_solve19.8k (lp) < 019.8k ) |
169 | 0 | goto error; |
170 | 19.8k | GBR_lp_get_obj_val19.8k (lp, &F_new); |
171 | 19.8k | fixed = GBR_lp_is_fixed(lp); |
172 | 19.8k | |
173 | 19.8k | GBR_lp_get_alpha(lp, row, &alpha); |
174 | 19.8k | |
175 | 19.8k | if (i > 0) |
176 | 14.8k | save_alpha(lp, row-i, i, alpha_saved); |
177 | 19.8k | |
178 | 19.8k | if (GBR_lp_del_row19.8k (lp) < 019.8k ) |
179 | 0 | goto error; |
180 | 29.9k | } |
181 | 29.9k | GBR_set29.9k (F[i+1], F_new); |
182 | 29.9k | |
183 | 29.9k | GBR_floor(mu[0], alpha); |
184 | 29.9k | GBR_ceil(mu[1], alpha); |
185 | 29.9k | |
186 | 29.9k | if (isl_int_eq(mu[0], mu[1])) |
187 | 24.0k | isl_int_set(tmp, mu[0]); |
188 | 5.86k | else { |
189 | 5.86k | int j; |
190 | 5.86k | |
191 | 17.6k | for (j = 0; j <= 117.6k ; ++j11.7k ) { |
192 | 11.7k | isl_int_set(tmp, mu[j]); |
193 | 11.7k | isl_seq_combine(b_tmp->el, |
194 | 11.7k | ctx->one, B->row[1+i+1]+1, |
195 | 11.7k | tmp, B->row[1+i]+1, dim); |
196 | 11.7k | GBR_lp_set_obj(lp, b_tmp->el, dim); |
197 | 11.7k | ctx->stats->gbr_solved_lps++; |
198 | 11.7k | if (GBR_lp_solve11.7k (lp) < 011.7k ) |
199 | 0 | goto error; |
200 | 11.7k | GBR_lp_get_obj_val11.7k (lp, &mu_F[j]); |
201 | 11.7k | mu_fixed[j] = GBR_lp_is_fixed(lp); |
202 | 11.7k | if (i > 0) |
203 | 6.44k | save_alpha(lp, row-i, i, alpha_buffer[j]); |
204 | 11.7k | } |
205 | 5.86k | |
206 | 5.86k | if (5.86k GBR_lt5.86k (mu_F[0], mu_F[1])) |
207 | 3.05k | j = 0; |
208 | 5.86k | else |
209 | 2.80k | j = 1; |
210 | 5.86k | |
211 | 5.86k | isl_int_set(tmp, mu[j]); |
212 | 5.86k | GBR_set(F_new, mu_F[j]); |
213 | 5.86k | fixed = mu_fixed[j]; |
214 | 5.86k | alpha_saved = alpha_buffer[j]; |
215 | 5.86k | } |
216 | 29.9k | isl_seq_combine(B->row[1+i+1]+1, ctx->one, B->row[1+i+1]+1, |
217 | 29.9k | tmp, B->row[1+i]+1, dim); |
218 | 29.9k | |
219 | 29.9k | if (i+1 == tab->n_zero && 29.9k fixed0 ) { |
220 | 0 | if (!0 GBR_is_zero0 (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_ui0 (F[i+1], 0); |
225 | 0 | } |
226 | 0 | tab->n_zero++; |
227 | 0 | } |
228 | 29.9k | |
229 | 29.9k | GBR_set29.9k (F_old, F[i]); |
230 | 29.9k | |
231 | 29.9k | use_saved = 0; |
232 | 29.9k | /* mu_F[0] = 4 * F_new; mu_F[1] = 3 * F_old */ |
233 | 29.9k | GBR_set_ui(mu_F[0], 4); |
234 | 29.9k | GBR_mul(mu_F[0], mu_F[0], F_new); |
235 | 29.9k | GBR_set_ui(mu_F[1], 3); |
236 | 29.9k | GBR_mul(mu_F[1], mu_F[1], F_old); |
237 | 29.9k | if (GBR_lt29.9k (mu_F[0], mu_F[1])) { |
238 | 15.5k | B = isl_mat_swap_rows(B, 1 + i, 1 + i + 1); |
239 | 15.5k | if (i > tab->n_zero15.5k ) { |
240 | 10.0k | use_saved = 1; |
241 | 10.0k | GBR_set(F_saved, F_new); |
242 | 10.0k | fixed_saved = fixed; |
243 | 10.0k | if (GBR_lp_del_row10.0k (lp) < 010.0k ) |
244 | 0 | goto error; |
245 | 10.0k | --i; |
246 | 15.5k | } else { |
247 | 5.41k | GBR_set(F[tab->n_zero], F_new); |
248 | 5.41k | if (gbr_only_first && 5.41k GBR_lt5.41k (F[tab->n_zero], two)) |
249 | 1.85k | break; |
250 | 5.41k | |
251 | 3.55k | if (3.55k fixed3.55k ) { |
252 | 0 | if (!0 GBR_is_zero0 (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_ui0 (F[tab->n_zero], 0); |
257 | 0 | } |
258 | 0 | tab->n_zero++; |
259 | 0 | } |
260 | 5.41k | } |
261 | 29.9k | } else { |
262 | 14.4k | GBR_lp_add_row(lp, B->row[1+i]+1, dim); |
263 | 14.4k | ++i; |
264 | 14.4k | } |
265 | 28.0k | } while (i < n_bounded - 1); |
266 | 2.84k | |
267 | 2.84k | if (2.84k 02.84k ) { |
268 | 0 | done: |
269 | 0 | if (empty < 00 ) { |
270 | 0 | error: |
271 | 0 | isl_mat_free(B); |
272 | 0 | B = NULL; |
273 | 0 | } |
274 | 0 | } |
275 | 2.84k | |
276 | 2.84k | GBR_lp_delete2.84k (lp); |
277 | 2.84k | |
278 | 2.84k | if (alpha_buffer[1]) |
279 | 18.0k | for (i = 0; 2.84k i < n_bounded18.0k ; ++i15.1k ) { |
280 | 15.1k | GBR_clear(F[i]); |
281 | 15.1k | GBR_clear(alpha_buffer[0][i]); |
282 | 15.1k | GBR_clear(alpha_buffer[1][i]); |
283 | 2.84k | } |
284 | 2.84k | free(F); |
285 | 2.84k | free(alpha_buffer[0]); |
286 | 2.84k | free(alpha_buffer[1]); |
287 | 2.84k | |
288 | 2.84k | isl_vec_free(b_tmp); |
289 | 2.84k | |
290 | 2.84k | GBR_clear(alpha); |
291 | 2.84k | GBR_clear(F_old); |
292 | 2.84k | GBR_clear(F_new); |
293 | 2.84k | GBR_clear(F_saved); |
294 | 2.84k | GBR_clear(mu_F[0]); |
295 | 2.84k | GBR_clear(mu_F[1]); |
296 | 2.84k | GBR_clear(two); |
297 | 2.84k | GBR_clear(one); |
298 | 2.84k | |
299 | 2.84k | isl_int_clear(tmp); |
300 | 2.84k | isl_int_clear(mu[0]); |
301 | 2.84k | isl_int_clear(mu[1]); |
302 | 2.84k | |
303 | 2.84k | tab->basis = B; |
304 | 2.84k | |
305 | 2.84k | return tab; |
306 | 2.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 (0 isl_basic_set_dim(bset, isl_dim_div) != 00 ) |
326 | 0 | isl_die(bset->ctx, isl_error_invalid, |
327 | 0 | "no integer division allowed", return NULL); |
328 | 0 | if (0 isl_basic_set_dim(bset, isl_dim_param) != 00 ) |
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 (0 bset->n_eq == 00 ) |
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 | } |