Coverage Report

Created: 2017-08-21 19:50

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/External/isl/isl_factorization.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2005-2007 Universiteit Leiden
3
 * Copyright 2008-2009 Katholieke Universiteit Leuven
4
 * Copyright 2010      INRIA Saclay
5
 *
6
 * Use of this software is governed by the MIT license
7
 *
8
 * Written by Sven Verdoolaege, Leiden Institute of Advanced Computer Science,
9
 * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
10
 * and K.U.Leuven, Departement Computerwetenschappen, Celestijnenlaan 200A,
11
 * B-3001 Leuven, Belgium
12
 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
13
 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France 
14
 */
15
16
#include <isl_map_private.h>
17
#include <isl_factorization.h>
18
#include <isl_space_private.h>
19
#include <isl_mat_private.h>
20
21
static __isl_give isl_factorizer *isl_factorizer_alloc(
22
  __isl_take isl_morph *morph, int n_group)
23
77.3k
{
24
77.3k
  isl_factorizer *f = NULL;
25
77.3k
  int *len = NULL;
26
77.3k
27
77.3k
  if (!morph)
28
0
    return NULL;
29
77.3k
30
77.3k
  
if (77.3k
n_group > 077.3k
)
{32.5k
31
32.5k
    len = isl_alloc_array(morph->dom->ctx, int, n_group);
32
32.5k
    if (!len)
33
0
      goto error;
34
77.3k
  }
35
77.3k
36
77.3k
  
f = 77.3k
isl_alloc_type77.3k
(morph->dom->ctx, struct isl_factorizer);
37
77.3k
  if (!f)
38
0
    goto error;
39
77.3k
40
77.3k
  f->morph = morph;
41
77.3k
  f->n_group = n_group;
42
77.3k
  f->len = len;
43
77.3k
44
77.3k
  return f;
45
77.3k
error:
46
0
  free(len);
47
0
  isl_morph_free(morph);
48
77.3k
  return NULL;
49
77.3k
}
50
51
void isl_factorizer_free(__isl_take isl_factorizer *f)
52
77.3k
{
53
77.3k
  if (!f)
54
0
    return;
55
77.3k
56
77.3k
  isl_morph_free(f->morph);
57
77.3k
  free(f->len);
58
77.3k
  free(f);
59
77.3k
}
60
61
void isl_factorizer_dump(__isl_take isl_factorizer *f)
62
0
{
63
0
  int i;
64
0
65
0
  if (!f)
66
0
    return;
67
0
68
0
  isl_morph_print_internal(f->morph, stderr);
69
0
  fprintf(stderr, "[");
70
0
  for (i = 0; 
i < f->n_group0
;
++i0
)
{0
71
0
    if (i)
72
0
      fprintf(stderr, ", ");
73
0
    fprintf(stderr, "%d", f->len[i]);
74
0
  }
75
0
  fprintf(stderr, "]\n");
76
0
}
77
78
__isl_give isl_factorizer *isl_factorizer_identity(__isl_keep isl_basic_set *bset)
79
44.8k
{
80
44.8k
  return isl_factorizer_alloc(isl_morph_identity(bset), 0);
81
44.8k
}
82
83
__isl_give isl_factorizer *isl_factorizer_groups(__isl_keep isl_basic_set *bset,
84
  __isl_take isl_mat *Q, __isl_take isl_mat *U, int n, int *len)
85
32.5k
{
86
32.5k
  int i;
87
32.5k
  unsigned nvar;
88
32.5k
  unsigned ovar;
89
32.5k
  isl_space *dim;
90
32.5k
  isl_basic_set *dom;
91
32.5k
  isl_basic_set *ran;
92
32.5k
  isl_morph *morph;
93
32.5k
  isl_factorizer *f;
94
32.5k
  isl_mat *id;
95
32.5k
96
32.5k
  if (
!bset || 32.5k
!Q32.5k
||
!U32.5k
)
97
0
    goto error;
98
32.5k
99
32.5k
  ovar = 1 + isl_space_offset(bset->dim, isl_dim_set);
100
32.5k
  id = isl_mat_identity(bset->ctx, ovar);
101
32.5k
  Q = isl_mat_diagonal(isl_mat_copy(id), Q);
102
32.5k
  U = isl_mat_diagonal(id, U);
103
32.5k
104
32.5k
  nvar = isl_basic_set_dim(bset, isl_dim_set);
105
32.5k
  dim = isl_basic_set_get_space(bset);
106
32.5k
  dom = isl_basic_set_universe(isl_space_copy(dim));
107
32.5k
  dim = isl_space_drop_dims(dim, isl_dim_set, 0, nvar);
108
32.5k
  dim = isl_space_add_dims(dim, isl_dim_set, nvar);
109
32.5k
  ran = isl_basic_set_universe(dim);
110
32.5k
  morph = isl_morph_alloc(dom, ran, Q, U);
111
32.5k
  f = isl_factorizer_alloc(morph, n);
112
32.5k
  if (!f)
113
0
    return NULL;
114
173k
  
for (i = 0; 32.5k
i < n173k
;
++i140k
)
115
140k
    f->len[i] = len[i];
116
32.5k
  return f;
117
32.5k
error:
118
0
  isl_mat_free(Q);
119
0
  isl_mat_free(U);
120
32.5k
  return NULL;
121
32.5k
}
122
123
struct isl_factor_groups {
124
  int *pos;   /* for each column: row position of pivot */
125
  int *group;   /* group to which a column belongs */
126
  int *cnt;   /* number of columns in the group */
127
  int *rowgroup;    /* group to which a constraint belongs */
128
};
129
130
/* Initialize isl_factor_groups structure: find pivot row positions,
131
 * each column initially belongs to its own group and the groups
132
 * of the constraints are still unknown.
133
 */
134
static int init_groups(struct isl_factor_groups *g, __isl_keep isl_mat *H)
135
77.3k
{
136
77.3k
  int i, j;
137
77.3k
138
77.3k
  if (!H)
139
0
    return -1;
140
77.3k
141
77.3k
  
g->pos = 77.3k
isl_alloc_array77.3k
(H->ctx, int, H->n_col);
142
77.3k
  g->group = isl_alloc_array(H->ctx, int, H->n_col);
143
77.3k
  g->cnt = isl_alloc_array(H->ctx, int, H->n_col);
144
77.3k
  g->rowgroup = isl_alloc_array(H->ctx, int, H->n_row);
145
77.3k
146
77.3k
  if (
!g->pos || 77.3k
!g->group77.3k
||
!g->cnt77.3k
||
!g->rowgroup77.3k
)
147
0
    return -1;
148
77.3k
149
730k
  
for (i = 0; 77.3k
i < H->n_row730k
;
++i653k
)
150
653k
    g->rowgroup[i] = -1;
151
363k
  for (i = 0, j = 0; 
i < H->n_col363k
;
++i285k
)
{285k
152
682k
    for ( ; 
j < H->n_row682k
;
++j396k
)
153
682k
      
if (682k
!682k
isl_int_is_zero682k
(H->row[j][i]))
154
285k
        break;
155
285k
    g->pos[i] = j;
156
285k
  }
157
363k
  for (i = 0; 
i < H->n_col363k
;
++i285k
)
{285k
158
285k
    g->group[i] = i;
159
285k
    g->cnt[i] = 1;
160
285k
  }
161
77.3k
162
77.3k
  return 0;
163
77.3k
}
164
165
/* Update group[k] to the group column k belongs to.
166
 * When merging two groups, only the group of the current
167
 * group leader is changed.  Here we change the group of
168
 * the other members to also point to the group that the
169
 * old group leader now points to.
170
 */
171
static void update_group(struct isl_factor_groups *g, int k)
172
1.24M
{
173
1.24M
  int p = g->group[k];
174
1.24M
  while (g->cnt[p] == 0)
175
13
    p = g->group[p];
176
1.24M
  g->group[k] = p;
177
1.24M
}
178
179
/* Merge group i with all groups of the subsequent columns
180
 * with non-zero coefficients in row j of H.
181
 * (The previous columns are all zero; otherwise we would have handled
182
 * the row before.)
183
 */
184
static int update_group_i_with_row_j(struct isl_factor_groups *g, int i, int j,
185
  __isl_keep isl_mat *H)
186
364k
{
187
364k
  int k;
188
364k
189
364k
  g->rowgroup[j] = g->group[i];
190
884k
  for (k = i + 1; 
k < H->n_col && 884k
j >= g->pos[k]718k
;
++k519k
)
{519k
191
519k
    update_group(g, k);
192
519k
    update_group(g, i);
193
519k
    if (g->group[k] != g->group[i] &&
194
519k
        
!354k
isl_int_is_zero354k
(H->row[j][k]))
{99.9k
195
99.9k
      isl_assert(H->ctx, g->cnt[g->group[k]] != 0, return -1);
196
99.9k
      
isl_assert99.9k
(H->ctx, g->cnt[g->group[i]] != 0, return -1);99.9k
197
99.9k
      
if (99.9k
g->group[i] < g->group[k]99.9k
)
{99.3k
198
99.3k
        g->cnt[g->group[i]] += g->cnt[g->group[k]];
199
99.3k
        g->cnt[g->group[k]] = 0;
200
99.3k
        g->group[g->group[k]] = g->group[i];
201
99.9k
      } else {
202
605
        g->cnt[g->group[k]] += g->cnt[g->group[i]];
203
605
        g->cnt[g->group[i]] = 0;
204
605
        g->group[g->group[i]] = g->group[k];
205
99.9k
      }
206
519k
    }
207
519k
  }
208
364k
209
364k
  return 0;
210
364k
}
211
212
/* Update the group information based on the constraint matrix.
213
 */
214
static int update_groups(struct isl_factor_groups *g, __isl_keep isl_mat *H)
215
77.3k
{
216
77.3k
  int i, j;
217
77.3k
218
305k
  for (i = 0; 
i < H->n_col && 305k
g->cnt[0] < H->n_col272k
;
++i227k
)
{227k
219
227k
    if (g->pos[i] == H->n_row)
220
0
      continue; /* A line direction */
221
227k
    
if (227k
g->rowgroup[g->pos[i]] == -1227k
)
222
210k
      g->rowgroup[g->pos[i]] = i;
223
3.81M
    for (j = g->pos[i] + 1; 
j < H->n_row3.81M
;
++j3.58M
)
{3.58M
224
3.58M
      if (isl_int_is_zero(H->row[j][i]))
225
3.15M
        continue;
226
430k
      
if (430k
g->rowgroup[j] != -1430k
)
227
65.1k
        continue;
228
364k
      
if (364k
update_group_i_with_row_j(g, i, j, H) < 0364k
)
229
0
        return -1;
230
364k
    }
231
227k
  }
232
285k
  
for (i = 1; 77.3k
i < H->n_col285k
;
++i208k
)
233
208k
    update_group(g, i);
234
77.3k
235
77.3k
  return 0;
236
77.3k
}
237
238
static void clear_groups(struct isl_factor_groups *g)
239
77.3k
{
240
77.3k
  if (!g)
241
0
    return;
242
77.3k
  free(g->pos);
243
77.3k
  free(g->group);
244
77.3k
  free(g->cnt);
245
77.3k
  free(g->rowgroup);
246
77.3k
}
247
248
/* Determine if the set variables of the basic set can be factorized and
249
 * return the results in an isl_factorizer.
250
 *
251
 * The algorithm works by first computing the Hermite normal form
252
 * and then grouping columns linked by one or more constraints together,
253
 * where a constraints "links" two or more columns if the constraint
254
 * has nonzero coefficients in the columns.
255
 */
256
__isl_give isl_factorizer *isl_basic_set_factorizer(
257
  __isl_keep isl_basic_set *bset)
258
77.3k
{
259
77.3k
  int i, j, n, done;
260
77.3k
  isl_mat *H, *U, *Q;
261
77.3k
  unsigned nvar;
262
77.3k
  struct isl_factor_groups g = { 0 };
263
77.3k
  isl_factorizer *f;
264
77.3k
265
77.3k
  if (!bset)
266
0
    return NULL;
267
77.3k
268
77.3k
  
isl_assert77.3k
(bset->ctx, isl_basic_set_dim(bset, isl_dim_div) == 0,77.3k
269
77.3k
    return NULL);
270
77.3k
271
77.3k
  nvar = isl_basic_set_dim(bset, isl_dim_set);
272
77.3k
  if (nvar <= 1)
273
1
    return isl_factorizer_identity(bset);
274
77.3k
275
77.3k
  H = isl_mat_alloc(bset->ctx, bset->n_eq + bset->n_ineq, nvar);
276
77.3k
  if (!H)
277
0
    return NULL;
278
77.3k
  isl_mat_sub_copy(bset->ctx, H->row, bset->eq, bset->n_eq,
279
77.3k
    0, 1 + isl_space_offset(bset->dim, isl_dim_set), nvar);
280
77.3k
  isl_mat_sub_copy(bset->ctx, H->row + bset->n_eq, bset->ineq, bset->n_ineq,
281
77.3k
    0, 1 + isl_space_offset(bset->dim, isl_dim_set), nvar);
282
77.3k
  H = isl_mat_left_hermite(H, 0, &U, &Q);
283
77.3k
284
77.3k
  if (init_groups(&g, H) < 0)
285
0
    goto error;
286
77.3k
  
if (77.3k
update_groups(&g, H) < 077.3k
)
287
0
    goto error;
288
77.3k
289
77.3k
  
if (77.3k
g.cnt[0] == nvar77.3k
)
{44.8k
290
44.8k
    isl_mat_free(H);
291
44.8k
    isl_mat_free(U);
292
44.8k
    isl_mat_free(Q);
293
44.8k
    clear_groups(&g);
294
44.8k
295
44.8k
    return isl_factorizer_identity(bset);
296
77.3k
  }
297
77.3k
298
77.3k
  done = 0;
299
32.5k
  n = 0;
300
173k
  while (
done != nvar173k
)
{140k
301
140k
    int group = g.group[done];
302
181k
    for (i = 1; 
i < g.cnt[group]181k
;
++i40.0k
)
{40.0k
303
40.0k
      if (g.group[done + i] == group)
304
21.1k
        continue;
305
63.1k
      
for (j = done + g.cnt[group]; 18.9k
j < nvar63.1k
;
++j44.1k
)
306
63.1k
        
if (63.1k
g.group[j] == group63.1k
)
307
18.9k
          break;
308
18.9k
      if (j == nvar)
309
0
        isl_die(bset->ctx, isl_error_internal,
310
18.9k
          "internal error", goto error);
311
18.9k
      g.group[j] = g.group[done + i];
312
18.9k
      Q = isl_mat_swap_rows(Q, done + i, j);
313
18.9k
      U = isl_mat_swap_cols(U, done + i, j);
314
140k
    }
315
140k
    done += g.cnt[group];
316
140k
    g.pos[n++] = g.cnt[group];
317
140k
  }
318
32.5k
319
32.5k
  f = isl_factorizer_groups(bset, Q, U, n, g.pos);
320
32.5k
321
32.5k
  isl_mat_free(H);
322
32.5k
  clear_groups(&g);
323
32.5k
324
32.5k
  return f;
325
32.5k
error:
326
0
  isl_mat_free(H);
327
0
  isl_mat_free(U);
328
0
  isl_mat_free(Q);
329
0
  clear_groups(&g);
330
32.5k
  return NULL;
331
77.3k
}