Coverage Report

Created: 2018-04-24 22:41

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