Coverage Report

Created: 2017-08-18 19:41

/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
8.56k
{
22
8.56k
  int i;
23
8.56k
24
29.4k
  for (i = 0; 
i < n29.4k
;
++i20.8k
)
25
20.8k
    GBR_lp_get_alpha(lp, first + i, &alpha[i]);
26
8.56k
}
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
1.82k
{
51
1.82k
  unsigned dim;
52
1.82k
  struct isl_ctx *ctx;
53
1.82k
  struct isl_mat *B;
54
1.82k
  int i;
55
1.82k
  GBR_LP *lp = NULL;
56
1.82k
  GBR_type F_old, alpha, F_new;
57
1.82k
  int row;
58
1.82k
  isl_int tmp;
59
1.82k
  struct isl_vec *b_tmp;
60
1.82k
  GBR_type *F = NULL;
61
1.82k
  GBR_type *alpha_buffer[2] = { NULL, NULL };
62
1.82k
  GBR_type *alpha_saved;
63
1.82k
  GBR_type F_saved;
64
1.82k
  int use_saved = 0;
65
1.82k
  isl_int mu[2];
66
1.82k
  GBR_type mu_F[2];
67
1.82k
  GBR_type two;
68
1.82k
  GBR_type one;
69
1.82k
  int empty = 0;
70
1.82k
  int fixed = 0;
71
1.82k
  int fixed_saved = 0;
72
1.82k
  int mu_fixed[2];
73
1.82k
  int n_bounded;
74
1.82k
  int gbr_only_first;
75
1.82k
76
1.82k
  if (!tab)
77
0
    return NULL;
78
1.82k
79
1.82k
  
if (1.82k
tab->empty1.82k
)
80
0
    return tab;
81
1.82k
82
1.82k
  ctx = tab->mat->ctx;
83
1.82k
  gbr_only_first = ctx->opt->gbr_only_first;
84
1.82k
  dim = tab->n_var;
85
1.82k
  B = tab->basis;
86
1.82k
  if (!B)
87
0
    return tab;
88
1.82k
89
1.82k
  n_bounded = dim - tab->n_unbounded;
90
1.82k
  if (n_bounded <= tab->n_zero + 1)
91
0
    return tab;
92
1.82k
93
1.82k
  
isl_int_init1.82k
(tmp);1.82k
94
1.82k
  isl_int_init(mu[0]);
95
1.82k
  isl_int_init(mu[1]);
96
1.82k
97
1.82k
  GBR_init(alpha);
98
1.82k
  GBR_init(F_old);
99
1.82k
  GBR_init(F_new);
100
1.82k
  GBR_init(F_saved);
101
1.82k
  GBR_init(mu_F[0]);
102
1.82k
  GBR_init(mu_F[1]);
103
1.82k
  GBR_init(two);
104
1.82k
  GBR_init(one);
105
1.82k
106
1.82k
  b_tmp = isl_vec_alloc(ctx, dim);
107
1.82k
  if (!b_tmp)
108
0
    goto error;
109
1.82k
110
1.82k
  
F = 1.82k
isl_alloc_array1.82k
(ctx, GBR_type, n_bounded);
111
1.82k
  alpha_buffer[0] = isl_alloc_array(ctx, GBR_type, n_bounded);
112
1.82k
  alpha_buffer[1] = isl_alloc_array(ctx, GBR_type, n_bounded);
113
1.82k
  alpha_saved = alpha_buffer[0];
114
1.82k
115
1.82k
  if (
!F || 1.82k
!alpha_buffer[0]1.82k
||
!alpha_buffer[1]1.82k
)
116
0
    goto error;
117
1.82k
118
10.1k
  
for (i = 0; 1.82k
i < n_bounded10.1k
;
++i8.36k
)
{8.36k
119
8.36k
    GBR_init(F[i]);
120
8.36k
    GBR_init(alpha_buffer[0][i]);
121
8.36k
    GBR_init(alpha_buffer[1][i]);
122
8.36k
  }
123
1.82k
124
1.82k
  GBR_set_ui(two, 2);
125
1.82k
  GBR_set_ui(one, 1);
126
1.82k
127
1.82k
  lp = GBR_lp_init(tab);
128
1.82k
  if (!lp)
129
0
    goto error;
130
1.82k
131
1.82k
  i = tab->n_zero;
132
1.82k
133
1.82k
  GBR_lp_set_obj(lp, B->row[1+i]+1, dim);
134
1.82k
  ctx->stats->gbr_solved_lps++;
135
1.82k
  if (
GBR_lp_solve1.82k
(lp) < 01.82k
)
136
0
    goto error;
137
1.82k
  
GBR_lp_get_obj_val1.82k
(lp, &F[i]);1.82k
138
1.82k
139
1.82k
  if (
GBR_lt1.82k
(F[i], one))
{0
140
0
    if (
!0
GBR_is_zero0
(F[i]))
{0
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);0
145
0
    }
146
0
    tab->n_zero++;
147
1.82k
  }
148
1.82k
149
1.82k
  
do 1.82k
{10.1k
150
10.1k
    if (
i+1 == tab->n_zero10.1k
)
{0
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);0
156
0
      fixed = GBR_lp_is_fixed(lp);
157
0
      GBR_set_ui(alpha, 0);
158
10.1k
    } else
159
10.1k
    
if (10.1k
use_saved10.1k
)
{3.09k
160
3.09k
      row = GBR_lp_next_row(lp);
161
3.09k
      GBR_set(F_new, F_saved);
162
3.09k
      fixed = fixed_saved;
163
3.09k
      GBR_set(alpha, alpha_saved[i]);
164
10.1k
    } else {
165
7.09k
      row = GBR_lp_add_row(lp, B->row[1+i]+1, dim);
166
7.09k
      GBR_lp_set_obj(lp, B->row[1+i+1]+1, dim);
167
7.09k
      ctx->stats->gbr_solved_lps++;
168
7.09k
      if (
GBR_lp_solve7.09k
(lp) < 07.09k
)
169
0
        goto error;
170
7.09k
      
GBR_lp_get_obj_val7.09k
(lp, &F_new);7.09k
171
7.09k
      fixed = GBR_lp_is_fixed(lp);
172
7.09k
173
7.09k
      GBR_lp_get_alpha(lp, row, &alpha);
174
7.09k
175
7.09k
      if (i > 0)
176
5.00k
        save_alpha(lp, row-i, i, alpha_saved);
177
7.09k
178
7.09k
      if (
GBR_lp_del_row7.09k
(lp) < 07.09k
)
179
0
        goto error;
180
10.1k
    }
181
10.1k
    
GBR_set10.1k
(F[i+1], F_new);10.1k
182
10.1k
183
10.1k
    GBR_floor(mu[0], alpha);
184
10.1k
    GBR_ceil(mu[1], alpha);
185
10.1k
186
10.1k
    if (isl_int_eq(mu[0], mu[1]))
187
7.27k
      isl_int_set(tmp, mu[0]);
188
10.1k
    else {
189
2.92k
      int j;
190
2.92k
191
8.77k
      for (j = 0; 
j <= 18.77k
;
++j5.84k
)
{5.84k
192
5.84k
        isl_int_set(tmp, mu[j]);
193
5.84k
        isl_seq_combine(b_tmp->el,
194
5.84k
            ctx->one, B->row[1+i+1]+1,
195
5.84k
            tmp, B->row[1+i]+1, dim);
196
5.84k
        GBR_lp_set_obj(lp, b_tmp->el, dim);
197
5.84k
        ctx->stats->gbr_solved_lps++;
198
5.84k
        if (
GBR_lp_solve5.84k
(lp) < 05.84k
)
199
0
          goto error;
200
5.84k
        
GBR_lp_get_obj_val5.84k
(lp, &mu_F[j]);5.84k
201
5.84k
        mu_fixed[j] = GBR_lp_is_fixed(lp);
202
5.84k
        if (i > 0)
203
3.56k
          save_alpha(lp, row-i, i, alpha_buffer[j]);
204
5.84k
      }
205
2.92k
206
2.92k
      
if (2.92k
GBR_lt2.92k
(mu_F[0], mu_F[1]))
207
1.31k
        j = 0;
208
2.92k
      else
209
1.61k
        j = 1;
210
2.92k
211
2.92k
      isl_int_set(tmp, mu[j]);
212
2.92k
      GBR_set(F_new, mu_F[j]);
213
2.92k
      fixed = mu_fixed[j];
214
2.92k
      alpha_saved = alpha_buffer[j];
215
10.1k
    }
216
10.1k
    isl_seq_combine(B->row[1+i+1]+1, ctx->one, B->row[1+i+1]+1,
217
10.1k
        tmp, B->row[1+i]+1, dim);
218
10.1k
219
10.1k
    if (
i+1 == tab->n_zero && 10.1k
fixed0
)
{0
220
0
      if (
!0
GBR_is_zero0
(F[i+1]))
{0
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);0
225
0
      }
226
0
      tab->n_zero++;
227
10.1k
    }
228
10.1k
229
10.1k
    
GBR_set10.1k
(F_old, F[i]);10.1k
230
10.1k
231
10.1k
    use_saved = 0;
232
10.1k
    /* mu_F[0] = 4 * F_new; mu_F[1] = 3 * F_old */
233
10.1k
    GBR_set_ui(mu_F[0], 4);
234
10.1k
    GBR_mul(mu_F[0], mu_F[0], F_new);
235
10.1k
    GBR_set_ui(mu_F[1], 3);
236
10.1k
    GBR_mul(mu_F[1], mu_F[1], F_old);
237
10.1k
    if (
GBR_lt10.1k
(mu_F[0], mu_F[1]))
{5.45k
238
5.45k
      B = isl_mat_swap_rows(B, 1 + i, 1 + i + 1);
239
5.45k
      if (
i > tab->n_zero5.45k
)
{3.09k
240
3.09k
        use_saved = 1;
241
3.09k
        GBR_set(F_saved, F_new);
242
3.09k
        fixed_saved = fixed;
243
3.09k
        if (
GBR_lp_del_row3.09k
(lp) < 03.09k
)
244
0
          goto error;
245
3.09k
        --i;
246
5.45k
      } else {
247
2.35k
        GBR_set(F[tab->n_zero], F_new);
248
2.35k
        if (
gbr_only_first && 2.35k
GBR_lt2.35k
(F[tab->n_zero], two))
249
1.32k
          break;
250
2.35k
251
1.03k
        
if (1.03k
fixed1.03k
)
{0
252
0
          if (
!0
GBR_is_zero0
(F[tab->n_zero]))
{0
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);0
257
0
          }
258
0
          tab->n_zero++;
259
1.03k
        }
260
5.45k
      }
261
10.1k
    } else {
262
4.74k
      GBR_lp_add_row(lp, B->row[1+i]+1, dim);
263
4.74k
      ++i;
264
10.1k
    }
265
8.87k
  } while (i < n_bounded - 1);
266
1.82k
267
1.82k
  
if (1.82k
01.82k
)
{0
268
0
done:
269
0
    if (
empty < 00
)
{0
270
0
error:
271
0
      isl_mat_free(B);
272
0
      B = NULL;
273
0
    }
274
1.82k
  }
275
1.82k
276
1.82k
  
GBR_lp_delete1.82k
(lp);1.82k
277
1.82k
278
1.82k
  if (alpha_buffer[1])
279
10.1k
    
for (i = 0; 1.82k
i < n_bounded10.1k
;
++i8.36k
)
{8.36k
280
8.36k
      GBR_clear(F[i]);
281
8.36k
      GBR_clear(alpha_buffer[0][i]);
282
8.36k
      GBR_clear(alpha_buffer[1][i]);
283
8.36k
    }
284
1.82k
  free(F);
285
1.82k
  free(alpha_buffer[0]);
286
1.82k
  free(alpha_buffer[1]);
287
1.82k
288
1.82k
  isl_vec_free(b_tmp);
289
1.82k
290
1.82k
  GBR_clear(alpha);
291
1.82k
  GBR_clear(F_old);
292
1.82k
  GBR_clear(F_new);
293
1.82k
  GBR_clear(F_saved);
294
1.82k
  GBR_clear(mu_F[0]);
295
1.82k
  GBR_clear(mu_F[1]);
296
1.82k
  GBR_clear(two);
297
1.82k
  GBR_clear(one);
298
1.82k
299
1.82k
  isl_int_clear(tmp);
300
1.82k
  isl_int_clear(mu[0]);
301
1.82k
  isl_int_clear(mu[1]);
302
1.82k
303
1.82k
  tab->basis = B;
304
1.82k
305
1.82k
  return tab;
306
1.82k
}
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
}