Coverage Report

Created: 2017-08-21 19:50

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/External/isl/basis_reduction_tab.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2008-2009 Katholieke Universiteit Leuven
3
 *
4
 * Use of this software is governed by the MIT license
5
 *
6
 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7
 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
8
 */
9
10
#include <assert.h>
11
#include <isl_map_private.h>
12
#include <isl_seq.h>
13
#include "isl_tab.h"
14
#include <isl_int.h>
15
#include <isl_config.h>
16
17
struct tab_lp {
18
  struct isl_ctx  *ctx;
19
  struct isl_vec  *row;
20
  struct isl_tab  *tab;
21
  struct isl_tab_undo **stack;
22
  isl_int   *obj;
23
  isl_int    opt;
24
  isl_int    opt_denom;
25
  isl_int    tmp;
26
  isl_int    tmp2;
27
  int          neq;
28
  unsigned   dim;
29
  /* number of constraints in initial product tableau */
30
  int    con_offset;
31
  /* objective function has fixed or no integer value */
32
  int    is_fixed;
33
};
34
35
#ifdef USE_GMP_FOR_MP
36
#define GBR_type              mpq_t
37
#define GBR_init(v)             mpq_init(v)
38
#define GBR_clear(v)              mpq_clear(v)
39
#define GBR_set(a,b)          mpq_set(a,b)
40
#define GBR_set_ui(a,b)         mpq_set_ui(a,b,1)
41
#define GBR_mul(a,b,c)          mpq_mul(a,b,c)
42
#define GBR_lt(a,b)         (mpq_cmp(a,b) < 0)
43
#define GBR_is_zero(a)          (mpq_sgn(a) == 0)
44
#define GBR_numref(a)         mpq_numref(a)
45
#define GBR_denref(a)         mpq_denref(a)
46
#define GBR_floor(a,b)          mpz_fdiv_q(a,GBR_numref(b),GBR_denref(b))
47
#define GBR_ceil(a,b)         mpz_cdiv_q(a,GBR_numref(b),GBR_denref(b))
48
#define GBR_set_num_neg(a, b)       mpz_neg(GBR_numref(*a), b);
49
#define GBR_set_den(a, b)       mpz_set(GBR_denref(*a), b);
50
#endif /* USE_GMP_FOR_MP */
51
52
#ifdef USE_IMATH_FOR_MP
53
#include <imrat.h>
54
55
14.5k
#define GBR_type              mp_rat
56
39.6k
#define GBR_init(v)             v = mp_rat_alloc()
57
39.6k
#define GBR_clear(v)              mp_rat_free(v)
58
34.9k
#define GBR_set(a,b)          mp_rat_copy(b,a)
59
24.0k
#define GBR_set_ui(a,b)         mp_rat_set_uvalue(a,b,1)
60
20.3k
#define GBR_mul(a,b,c)          mp_rat_mul(b,c,a)
61
17.3k
#define GBR_lt(a,b)         (mp_rat_compare(a,b) < 0)
62
0
#define GBR_is_zero(a)          (mp_rat_compare_zero(a) == 0)
63
#ifdef USE_SMALL_INT_OPT
64
20.3k
#define GBR_numref(a) isl_sioimath_encode_big(mp_rat_numer_ref(a))
65
20.3k
#define GBR_denref(a) isl_sioimath_encode_big(mp_rat_denom_ref(a))
66
10.1k
#define GBR_floor(a, b) 
isl_sioimath_fdiv_q((a), 10.1k
GBR_numref10.1k
(b),
GBR_denref10.1k
(b))
67
10.1k
#define GBR_ceil(a, b)  
isl_sioimath_cdiv_q((a), 10.1k
GBR_numref10.1k
(b),
GBR_denref10.1k
(b))
68
#define GBR_set_num_neg(a, b)                              \
69
42.7k
  
do 42.7k
{ \42.7k
70
42.7k
    isl_sioimath_scratchspace_t scratch;       \
71
42.7k
    impz_neg(mp_rat_numer_ref(*a),             \
72
42.7k
        isl_sioimath_bigarg_src(*b, &scratch));\
73
42.7k
  } while (0)
74
#define GBR_set_den(a, b)                                  \
75
42.7k
  
do 42.7k
{ \42.7k
76
42.7k
    isl_sioimath_scratchspace_t scratch;       \
77
42.7k
    impz_set(mp_rat_denom_ref(*a),             \
78
42.7k
        isl_sioimath_bigarg_src(*b, &scratch));\
79
42.7k
  } while (0)
80
#else /* USE_SMALL_INT_OPT */
81
#define GBR_numref(a)   mp_rat_numer_ref(a)
82
#define GBR_denref(a)   mp_rat_denom_ref(a)
83
#define GBR_floor(a,b)    impz_fdiv_q(a,GBR_numref(b),GBR_denref(b))
84
#define GBR_ceil(a,b)   impz_cdiv_q(a,GBR_numref(b),GBR_denref(b))
85
#define GBR_set_num_neg(a, b) impz_neg(GBR_numref(*a), b)
86
#define GBR_set_den(a, b) impz_set(GBR_denref(*a), b)
87
#endif /* USE_SMALL_INT_OPT */
88
#endif /* USE_IMATH_FOR_MP */
89
90
static struct tab_lp *init_lp(struct isl_tab *tab);
91
static void set_lp_obj(struct tab_lp *lp, isl_int *row, int dim);
92
static int solve_lp(struct tab_lp *lp);
93
static void get_obj_val(struct tab_lp* lp, GBR_type *F);
94
static void delete_lp(struct tab_lp *lp);
95
static int add_lp_row(struct tab_lp *lp, isl_int *row, int dim);
96
static void get_alpha(struct tab_lp* lp, int row, GBR_type *alpha);
97
static int del_lp_row(struct tab_lp *lp) WARN_UNUSED;
98
static int cut_lp_to_hyperplane(struct tab_lp *lp, isl_int *row);
99
100
1.82k
#define GBR_LP                struct tab_lp
101
1.82k
#define GBR_lp_init(P)              init_lp(P)
102
14.7k
#define GBR_lp_set_obj(lp, obj, dim)      set_lp_obj(lp, obj, dim)
103
14.7k
#define GBR_lp_solve(lp)        solve_lp(lp)
104
14.7k
#define GBR_lp_get_obj_val(lp, F)     get_obj_val(lp, F)
105
1.82k
#define GBR_lp_delete(lp)       delete_lp(lp)
106
3.09k
#define GBR_lp_next_row(lp)       lp->neq
107
11.8k
#define GBR_lp_add_row(lp, row, dim)      add_lp_row(lp, row, dim)
108
27.9k
#define GBR_lp_get_alpha(lp, row, alpha)    get_alpha(lp, row, alpha)
109
10.1k
#define GBR_lp_del_row(lp)        del_lp_row(lp)
110
12.9k
#define GBR_lp_is_fixed(lp)       (lp)->is_fixed
111
0
#define GBR_lp_cut(lp, obj)           cut_lp_to_hyperplane(lp, obj)
112
#include "basis_reduction_templ.c"
113
114
/* Set up a tableau for the Cartesian product of bset with itself.
115
 * This could be optimized by first setting up a tableau for bset
116
 * and then performing the Cartesian product on the tableau.
117
 */
118
static struct isl_tab *gbr_tab(struct isl_tab *tab, struct isl_vec *row)
119
1.82k
{
120
1.82k
  unsigned dim;
121
1.82k
  struct isl_tab *prod;
122
1.82k
123
1.82k
  if (
!tab || 1.82k
!row1.82k
)
124
0
    return NULL;
125
1.82k
126
1.82k
  dim = tab->n_var;
127
1.82k
  prod = isl_tab_product(tab, tab);
128
1.82k
  if (
isl_tab_extend_cons(prod, 3 * dim + 1) < 01.82k
)
{0
129
0
    isl_tab_free(prod);
130
0
    return NULL;
131
1.82k
  }
132
1.82k
  return prod;
133
1.82k
}
134
135
static struct tab_lp *init_lp(struct isl_tab *tab)
136
1.82k
{
137
1.82k
  struct tab_lp *lp = NULL;
138
1.82k
139
1.82k
  if (!tab)
140
0
    return NULL;
141
1.82k
142
1.82k
  
lp = 1.82k
isl_calloc_type1.82k
(tab->mat->ctx, struct tab_lp);
143
1.82k
  if (!lp)
144
0
    return NULL;
145
1.82k
146
1.82k
  
isl_int_init1.82k
(lp->opt);1.82k
147
1.82k
  isl_int_init(lp->opt_denom);
148
1.82k
  isl_int_init(lp->tmp);
149
1.82k
  isl_int_init(lp->tmp2);
150
1.82k
151
1.82k
  lp->dim = tab->n_var;
152
1.82k
153
1.82k
  lp->ctx = tab->mat->ctx;
154
1.82k
  isl_ctx_ref(lp->ctx);
155
1.82k
156
1.82k
  lp->stack = isl_alloc_array(lp->ctx, struct isl_tab_undo *, lp->dim);
157
1.82k
158
1.82k
  lp->row = isl_vec_alloc(lp->ctx, 1 + 2 * lp->dim);
159
1.82k
  if (!lp->row)
160
0
    goto error;
161
1.82k
  lp->tab = gbr_tab(tab, lp->row);
162
1.82k
  if (!lp->tab)
163
0
    goto error;
164
1.82k
  lp->con_offset = lp->tab->n_con;
165
1.82k
  lp->obj = NULL;
166
1.82k
  lp->neq = 0;
167
1.82k
168
1.82k
  return lp;
169
1.82k
error:
170
0
  delete_lp(lp);
171
1.82k
  return NULL;
172
1.82k
}
173
174
static void set_lp_obj(struct tab_lp *lp, isl_int *row, int dim)
175
14.7k
{
176
14.7k
  lp->obj = row;
177
14.7k
}
178
179
static int solve_lp(struct tab_lp *lp)
180
14.7k
{
181
14.7k
  enum isl_lp_result res;
182
14.7k
  unsigned flags = 0;
183
14.7k
184
14.7k
  lp->is_fixed = 0;
185
14.7k
186
14.7k
  isl_int_set_si(lp->row->el[0], 0);
187
14.7k
  isl_seq_cpy(lp->row->el + 1, lp->obj, lp->dim);
188
14.7k
  isl_seq_neg(lp->row->el + 1 + lp->dim, lp->obj, lp->dim);
189
14.7k
  if (lp->neq)
190
9.90k
    
flags = 9.90k
ISL_TAB_SAVE_DUAL9.90k
;
191
14.7k
  res = isl_tab_min(lp->tab, lp->row->el, lp->ctx->one,
192
14.7k
        &lp->opt, &lp->opt_denom, flags);
193
14.7k
  isl_int_mul_ui(lp->opt_denom, lp->opt_denom, 2);
194
14.7k
  if (
isl_int_abs_lt14.7k
(lp->opt, lp->opt_denom))
{4.69k
195
4.69k
    struct isl_vec *sample = isl_tab_get_sample_value(lp->tab);
196
4.69k
    if (!sample)
197
0
      return -1;
198
4.69k
    isl_seq_inner_product(lp->obj, sample->el + 1, lp->dim, &lp->tmp);
199
4.69k
    isl_seq_inner_product(lp->obj, sample->el + 1 + lp->dim, lp->dim, &lp->tmp2);
200
4.69k
    isl_int_cdiv_q(lp->tmp, lp->tmp, sample->el[0]);
201
4.69k
    isl_int_fdiv_q(lp->tmp2, lp->tmp2, sample->el[0]);
202
4.69k
    if (isl_int_ge(lp->tmp, lp->tmp2))
203
3.68k
      lp->is_fixed = 1;
204
4.69k
    isl_vec_free(sample);
205
14.7k
  }
206
14.7k
  
isl_int_divexact_ui14.7k
(lp->opt_denom, lp->opt_denom, 2);14.7k
207
14.7k
  if (res < 0)
208
0
    return -1;
209
14.7k
  
if (14.7k
res != isl_lp_ok14.7k
)
210
0
    isl_die(lp->ctx, isl_error_internal,
211
14.7k
      "unexpected missing (bounded) solution", return -1);
212
14.7k
  return 0;
213
14.7k
}
214
215
/* The current objective function has a fixed (or no) integer value.
216
 * Cut the tableau to the hyperplane that fixes this value in
217
 * both halves of the tableau.
218
 * Return 1 if the resulting tableau is empty.
219
 */
220
static int cut_lp_to_hyperplane(struct tab_lp *lp, isl_int *row)
221
0
{
222
0
  enum isl_lp_result res;
223
0
224
0
  isl_int_set_si(lp->row->el[0], 0);
225
0
  isl_seq_cpy(lp->row->el + 1, row, lp->dim);
226
0
  isl_seq_clr(lp->row->el + 1 + lp->dim, lp->dim);
227
0
  res = isl_tab_min(lp->tab, lp->row->el, lp->ctx->one,
228
0
        &lp->tmp, NULL, 0);
229
0
  if (res != isl_lp_ok)
230
0
    return -1;
231
0
232
0
  
isl_int_neg0
(lp->row->el[0], lp->tmp);0
233
0
  if (isl_tab_add_eq(lp->tab, lp->row->el) < 0)
234
0
    return -1;
235
0
236
0
  isl_seq_cpy(lp->row->el + 1 + lp->dim, row, lp->dim);
237
0
  isl_seq_clr(lp->row->el + 1, lp->dim);
238
0
  if (isl_tab_add_eq(lp->tab, lp->row->el) < 0)
239
0
    return -1;
240
0
241
0
  lp->con_offset += 2;
242
0
243
0
  return lp->tab->empty;
244
0
}
245
246
static void get_obj_val(struct tab_lp* lp, GBR_type *F)
247
14.7k
{
248
14.7k
  GBR_set_num_neg(F, lp->opt);
249
14.7k
  GBR_set_den(F, lp->opt_denom);
250
14.7k
}
251
252
static void delete_lp(struct tab_lp *lp)
253
1.82k
{
254
1.82k
  if (!lp)
255
0
    return;
256
1.82k
257
1.82k
  
isl_int_clear1.82k
(lp->opt);1.82k
258
1.82k
  isl_int_clear(lp->opt_denom);
259
1.82k
  isl_int_clear(lp->tmp);
260
1.82k
  isl_int_clear(lp->tmp2);
261
1.82k
  isl_vec_free(lp->row);
262
1.82k
  free(lp->stack);
263
1.82k
  isl_tab_free(lp->tab);
264
1.82k
  isl_ctx_deref(lp->ctx);
265
1.82k
  free(lp);
266
1.82k
}
267
268
static int add_lp_row(struct tab_lp *lp, isl_int *row, int dim)
269
11.8k
{
270
11.8k
  lp->stack[lp->neq] = isl_tab_snap(lp->tab);
271
11.8k
272
11.8k
  isl_int_set_si(lp->row->el[0], 0);
273
11.8k
  isl_seq_cpy(lp->row->el + 1, row, lp->dim);
274
11.8k
  isl_seq_neg(lp->row->el + 1 + lp->dim, row, lp->dim);
275
11.8k
276
11.8k
  if (isl_tab_add_valid_eq(lp->tab, lp->row->el) < 0)
277
0
    return -1;
278
11.8k
279
11.8k
  return lp->neq++;
280
11.8k
}
281
282
static void get_alpha(struct tab_lp* lp, int row, GBR_type *alpha)
283
27.9k
{
284
27.9k
  row += lp->con_offset;
285
27.9k
  GBR_set_num_neg(alpha, lp->tab->dual->el[1 + row]);
286
27.9k
  GBR_set_den(alpha, lp->tab->dual->el[0]);
287
27.9k
}
288
289
static int del_lp_row(struct tab_lp *lp)
290
10.1k
{
291
10.1k
  lp->neq--;
292
10.1k
  return isl_tab_rollback(lp->tab, lp->stack[lp->neq]);
293
10.1k
}