Coverage Report

Created: 2018-08-20 19:24

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_local.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2011      INRIA Saclay
3
 * Copyright 2014      Ecole Normale Superieure
4
 *
5
 * Use of this software is governed by the MIT license
6
 *
7
 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8
 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9
 * 91893 Orsay, France
10
 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
11
 */
12
13
#include <isl/space.h>
14
#include <isl_vec_private.h>
15
#include <isl_mat_private.h>
16
#include <isl_reordering.h>
17
#include <isl_seq.h>
18
#include <isl_local.h>
19
20
/* Return the isl_ctx to which "local" belongs.
21
 */
22
isl_ctx *isl_local_get_ctx(__isl_keep isl_local *local)
23
0
{
24
0
  if (!local)
25
0
    return NULL;
26
0
27
0
  return isl_mat_get_ctx(local);
28
0
}
29
30
/* Create an isl_local object from a matrix describing
31
 * integer divisions.
32
 *
33
 * An isl_local object is current defined as exactly such a matrix,
34
 * so simply return the input.
35
 */
36
__isl_give isl_local *isl_local_alloc_from_mat(__isl_take isl_mat *mat)
37
10.1k
{
38
10.1k
  return mat;
39
10.1k
}
40
41
/* Free "local" and return NULL.
42
 */
43
__isl_null isl_local *isl_local_free(__isl_take isl_local *local)
44
10.1k
{
45
10.1k
  isl_mat_free(local);
46
10.1k
  return NULL;
47
10.1k
}
48
49
/* Return the number of local variables (isl_dim_div),
50
 * the number of other variables (isl_dim_set) or
51
 * the total number of variables (isl_dim_all) in "local".
52
 *
53
 * Other types do not have any meaning for an isl_local object.
54
 */
55
int isl_local_dim(__isl_keep isl_local *local, enum isl_dim_type type)
56
362k
{
57
362k
  isl_mat *mat = local;
58
362k
59
362k
  if (!local)
60
0
    return 0;
61
362k
  if (type == isl_dim_div)
62
361k
    return isl_mat_rows(mat);
63
64
  if (type == isl_dim_all)
64
32
    return isl_mat_cols(mat) - 2;
65
32
  if (type == isl_dim_set)
66
32
    return isl_local_dim(local, isl_dim_all) -
67
32
      isl_local_dim(local, isl_dim_div);
68
0
  isl_die(isl_local_get_ctx(local), isl_error_unsupported,
69
0
    "unsupported dimension type", return 0);
70
0
}
71
72
/* Check that "pos" is a valid position for a variable in "local".
73
 */
74
static isl_stat isl_local_check_pos(__isl_keep isl_local *local, int pos)
75
88.2k
{
76
88.2k
  if (!local)
77
0
    return isl_stat_error;
78
88.2k
  if (pos < 0 || pos >= isl_local_dim(local, isl_dim_div))
79
88.2k
    
isl_die0
(isl_local_get_ctx(local), isl_error_invalid,
80
88.2k
      "position out of bounds", return isl_stat_error);
81
88.2k
  return isl_stat_ok;
82
88.2k
}
83
84
/* Given local variables "local",
85
 * is the variable at position "pos" marked as not having
86
 * an explicit representation?
87
 * Note that even if this variable is not marked in this way and therefore
88
 * does have an explicit representation, this representation may still
89
 * depend (indirectly) on other local variables that do not
90
 * have an explicit representation.
91
 */
92
isl_bool isl_local_div_is_marked_unknown(__isl_keep isl_local *local, int pos)
93
87.1k
{
94
87.1k
  isl_mat *mat = local;
95
87.1k
96
87.1k
  if (isl_local_check_pos(local, pos) < 0)
97
0
    return isl_bool_error;
98
87.1k
  return isl_int_is_zero(mat->row[pos][0]);
99
87.1k
}
100
101
/* Given local variables "local",
102
 * does the variable at position "pos" have a complete explicit representation?
103
 * Having a complete explicit representation requires not only
104
 * an explicit representation, but also that all local variables
105
 * that appear in this explicit representation in turn have
106
 * a complete explicit representation.
107
 */
108
isl_bool isl_local_div_is_known(__isl_keep isl_local *local, int pos)
109
1.17k
{
110
1.17k
  isl_bool marked;
111
1.17k
  int i, n, off;
112
1.17k
  isl_mat *mat = local;
113
1.17k
114
1.17k
  if (isl_local_check_pos(local, pos) < 0)
115
0
    return isl_bool_error;
116
1.17k
117
1.17k
  marked = isl_local_div_is_marked_unknown(local, pos);
118
1.17k
  if (marked < 0 || marked)
119
5
    return isl_bool_not(marked);
120
1.16k
121
1.16k
  n = isl_local_dim(local, isl_dim_div);
122
1.16k
  off = isl_mat_cols(mat) - n;
123
1.16k
124
3.01k
  for (i = n - 1; i >= 0; 
--i1.84k
) {
125
1.84k
    isl_bool known;
126
1.84k
127
1.84k
    if (isl_int_is_zero(mat->row[pos][off + i]))
128
1.84k
      
continue1.84k
;
129
2
    known = isl_local_div_is_known(local, i);
130
2
    if (known < 0 || !known)
131
0
      return known;
132
2
  }
133
1.16k
134
1.16k
  return isl_bool_true;
135
1.16k
}
136
137
/* Does "local" have an explicit representation for all local variables?
138
 */
139
isl_bool isl_local_divs_known(__isl_keep isl_local *local)
140
272k
{
141
272k
  int i, n;
142
272k
143
272k
  if (!local)
144
0
    return isl_bool_error;
145
272k
146
272k
  n = isl_local_dim(local, isl_dim_div);
147
356k
  for (i = 0; i < n; 
++i84.3k
) {
148
84.3k
    isl_bool unknown = isl_local_div_is_marked_unknown(local, i);
149
84.3k
    if (unknown < 0 || unknown)
150
0
      return isl_bool_not(unknown);
151
84.3k
  }
152
272k
153
272k
  return isl_bool_true;
154
272k
}
155
156
/* Compare two sets of local variables, defined over
157
 * the same space.
158
 *
159
 * Return -1 if "local1" is "smaller" than "local2", 1 if "local1" is "greater"
160
 * than "local2" and 0 if they are equal.
161
 *
162
 * The order is fairly arbitrary.  We do "prefer" divs that only involve
163
 * earlier dimensions in the sense that we consider matrices where
164
 * the first differing div involves earlier dimensions to be smaller.
165
 */
166
int isl_local_cmp(__isl_keep isl_local *local1, __isl_keep isl_local *local2)
167
17.8k
{
168
17.8k
  int i;
169
17.8k
  int cmp;
170
17.8k
  isl_bool unknown1, unknown2;
171
17.8k
  int last1, last2;
172
17.8k
  int n_col;
173
17.8k
  isl_mat *mat1 = local1;
174
17.8k
  isl_mat *mat2 = local2;
175
17.8k
176
17.8k
  if (local1 == local2)
177
0
    return 0;
178
17.8k
  if (!local1)
179
0
    return -1;
180
17.8k
  if (!local2)
181
0
    return 1;
182
17.8k
183
17.8k
  if (mat1->n_row != mat2->n_row)
184
1.32k
    return mat1->n_row - mat2->n_row;
185
16.5k
186
16.5k
  n_col = isl_mat_cols(mat1);
187
16.6k
  for (i = 0; i < mat1->n_row; 
++i160
) {
188
693
    unknown1 = isl_local_div_is_marked_unknown(local1, i);
189
693
    unknown2 = isl_local_div_is_marked_unknown(local2, i);
190
693
    if (unknown1 && 
unknown20
)
191
0
      continue;
192
693
    if (unknown1)
193
0
      return 1;
194
693
    if (unknown2)
195
0
      return -1;
196
693
    last1 = isl_seq_last_non_zero(mat1->row[i] + 1, n_col - 1);
197
693
    last2 = isl_seq_last_non_zero(mat2->row[i] + 1, n_col - 1);
198
693
    if (last1 != last2)
199
183
      return last1 - last2;
200
510
    cmp = isl_seq_cmp(mat1->row[i], mat2->row[i], n_col);
201
510
    if (cmp != 0)
202
350
      return cmp;
203
510
  }
204
16.5k
205
16.5k
  
return 016.0k
;
206
16.5k
}
207
208
/* Reorder the columns of the given local variables according to the
209
 * given reordering.
210
 * The order of the local variables themselves is assumed not to change.
211
 */
212
__isl_give isl_local *isl_local_reorder(__isl_take isl_local *local,
213
  __isl_take isl_reordering *r)
214
10.1k
{
215
10.1k
  isl_mat *div = local;
216
10.1k
  int i, j;
217
10.1k
  isl_space *space;
218
10.1k
  isl_mat *mat;
219
10.1k
  int extra;
220
10.1k
221
10.1k
  if (!local || !r)
222
0
    goto error;
223
10.1k
224
10.1k
  space = isl_reordering_peek_space(r);
225
10.1k
  extra = isl_space_dim(space, isl_dim_all) + div->n_row - r->len;
226
10.1k
  mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
227
10.1k
  if (!mat)
228
0
    goto error;
229
10.1k
230
10.5k
  
for (i = 0; 10.1k
i < div->n_row;
++i415
) {
231
415
    isl_seq_cpy(mat->row[i], div->row[i], 2);
232
415
    isl_seq_clr(mat->row[i] + 2, mat->n_col - 2);
233
1.94k
    for (j = 0; j < r->len; 
++j1.53k
)
234
1.53k
      isl_int_set(mat->row[i][2 + r->pos[j]],
235
415
            div->row[i][2 + j]);
236
415
  }
237
10.1k
238
10.1k
  isl_reordering_free(r);
239
10.1k
  isl_local_free(local);
240
10.1k
  return isl_local_alloc_from_mat(mat);
241
0
error:
242
0
  isl_reordering_free(r);
243
0
  isl_local_free(local);
244
0
  return NULL;
245
10.1k
}
246
247
/* Extend a vector "v" representing an integer point
248
 * in the domain space of "local"
249
 * to one that also includes values for the local variables.
250
 * All local variables are required to have an explicit representation.
251
 */
252
__isl_give isl_vec *isl_local_extend_point_vec(__isl_keep isl_local *local,
253
  __isl_take isl_vec *v)
254
20
{
255
20
  unsigned n_div;
256
20
  isl_bool known;
257
20
  isl_mat *mat = local;
258
20
259
20
  if (!local || !v)
260
0
    return isl_vec_free(v);
261
20
  known = isl_local_divs_known(local);
262
20
  if (known < 0)
263
0
    return isl_vec_free(v);
264
20
  if (!known)
265
20
    
isl_die0
(isl_local_get_ctx(local), isl_error_invalid,
266
20
      "unknown local variables", return isl_vec_free(v));
267
20
  if (isl_vec_size(v) != 1 + isl_local_dim(local, isl_dim_set))
268
20
    
isl_die0
(isl_local_get_ctx(local), isl_error_invalid,
269
20
      "incorrect size", return isl_vec_free(v));
270
20
  if (!isl_int_is_one(v->el[0]))
271
20
    
isl_die0
(isl_local_get_ctx(local), isl_error_invalid,
272
20
      "expecting integer point", return isl_vec_free(v));
273
20
  n_div = isl_local_dim(local, isl_dim_div);
274
20
  if (n_div != 0) {
275
12
    int i;
276
12
    unsigned dim = isl_local_dim(local, isl_dim_set);
277
12
    v = isl_vec_add_els(v, n_div);
278
12
    if (!v)
279
0
      return NULL;
280
12
281
36
    
for (i = 0; 12
i < n_div;
++i24
) {
282
24
      isl_seq_inner_product(mat->row[i] + 1, v->el,
283
24
            1 + dim + i, &v->el[1+dim+i]);
284
24
      isl_int_fdiv_q(v->el[1+dim+i], v->el[1+dim+i],
285
24
          mat->row[i][0]);
286
24
    }
287
12
  }
288
20
289
20
  return v;
290
20
}