Coverage Report

Created: 2018-12-13 20:48

/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.2k
{
38
10.2k
  return mat;
39
10.2k
}
40
41
/* Free "local" and return NULL.
42
 */
43
__isl_null isl_local *isl_local_free(__isl_take isl_local *local)
44
10.2k
{
45
10.2k
  isl_mat_free(local);
46
10.2k
  return NULL;
47
10.2k
}
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
383k
{
57
383k
  isl_mat *mat = local;
58
383k
59
383k
  if (!local)
60
0
    return 0;
61
383k
  if (type == isl_dim_div)
62
383k
    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
98.6k
{
76
98.6k
  if (!local)
77
0
    return isl_stat_error;
78
98.6k
  if (pos < 0 || pos >= isl_local_dim(local, isl_dim_div))
79
98.6k
    
isl_die0
(isl_local_get_ctx(local), isl_error_invalid,
80
98.6k
      "position out of bounds", return isl_stat_error);
81
98.6k
  return isl_stat_ok;
82
98.6k
}
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
97.2k
{
94
97.2k
  isl_mat *mat = local;
95
97.2k
96
97.2k
  if (isl_local_check_pos(local, pos) < 0)
97
0
    return isl_bool_error;
98
97.2k
  return isl_int_is_zero(mat->row[pos][0]);
99
97.2k
}
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.33k
{
110
1.33k
  isl_bool marked;
111
1.33k
  int i, n, off;
112
1.33k
  isl_mat *mat = local;
113
1.33k
114
1.33k
  if (isl_local_check_pos(local, pos) < 0)
115
0
    return isl_bool_error;
116
1.33k
117
1.33k
  marked = isl_local_div_is_marked_unknown(local, pos);
118
1.33k
  if (marked < 0 || marked)
119
5
    return isl_bool_not(marked);
120
1.32k
121
1.32k
  n = isl_local_dim(local, isl_dim_div);
122
1.32k
  off = isl_mat_cols(mat) - n;
123
1.32k
124
3.33k
  for (i = n - 1; i >= 0; 
--i2.00k
) {
125
2.00k
    isl_bool known;
126
2.00k
127
2.00k
    if (isl_int_is_zero(mat->row[pos][off + i]))
128
2.00k
      
continue2.00k
;
129
2
    known = isl_local_div_is_known(local, i);
130
2
    if (known < 0 || !known)
131
0
      return known;
132
2
  }
133
1.32k
134
1.32k
  return isl_bool_true;
135
1.32k
}
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
283k
{
141
283k
  int i, n;
142
283k
143
283k
  if (!local)
144
0
    return isl_bool_error;
145
283k
146
283k
  n = isl_local_dim(local, isl_dim_div);
147
378k
  for (i = 0; i < n; 
++i94.2k
) {
148
94.2k
    isl_bool unknown = isl_local_div_is_marked_unknown(local, i);
149
94.2k
    if (unknown < 0 || unknown)
150
0
      return isl_bool_not(unknown);
151
94.2k
  }
152
283k
153
283k
  return isl_bool_true;
154
283k
}
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.9k
{
168
17.9k
  int i;
169
17.9k
  int cmp;
170
17.9k
  isl_bool unknown1, unknown2;
171
17.9k
  int last1, last2;
172
17.9k
  int n_col;
173
17.9k
  isl_mat *mat1 = local1;
174
17.9k
  isl_mat *mat2 = local2;
175
17.9k
176
17.9k
  if (local1 == local2)
177
0
    return 0;
178
17.9k
  if (!local1)
179
0
    return -1;
180
17.9k
  if (!local2)
181
0
    return 1;
182
17.9k
183
17.9k
  if (mat1->n_row != mat2->n_row)
184
1.33k
    return mat1->n_row - mat2->n_row;
185
16.6k
186
16.6k
  n_col = isl_mat_cols(mat1);
187
16.7k
  for (i = 0; i < mat1->n_row; 
++i168
) {
188
701
    unknown1 = isl_local_div_is_marked_unknown(local1, i);
189
701
    unknown2 = isl_local_div_is_marked_unknown(local2, i);
190
701
    if (unknown1 && 
unknown20
)
191
0
      continue;
192
701
    if (unknown1)
193
0
      return 1;
194
701
    if (unknown2)
195
0
      return -1;
196
701
    last1 = isl_seq_last_non_zero(mat1->row[i] + 1, n_col - 1);
197
701
    last2 = isl_seq_last_non_zero(mat2->row[i] + 1, n_col - 1);
198
701
    if (last1 != last2)
199
183
      return last1 - last2;
200
518
    cmp = isl_seq_cmp(mat1->row[i], mat2->row[i], n_col);
201
518
    if (cmp != 0)
202
350
      return cmp;
203
518
  }
204
16.6k
205
16.6k
  
return 016.0k
;
206
16.6k
}
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.2k
{
215
10.2k
  isl_mat *div = local;
216
10.2k
  int i, j;
217
10.2k
  isl_space *space;
218
10.2k
  isl_mat *mat;
219
10.2k
  int extra;
220
10.2k
221
10.2k
  if (!local || !r)
222
0
    goto error;
223
10.2k
224
10.2k
  space = isl_reordering_peek_space(r);
225
10.2k
  extra = isl_space_dim(space, isl_dim_all) + div->n_row - r->len;
226
10.2k
  mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
227
10.2k
  if (!mat)
228
0
    goto error;
229
10.2k
230
10.6k
  
for (i = 0; 10.2k
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.2k
238
10.2k
  isl_reordering_free(r);
239
10.2k
  isl_local_free(local);
240
10.2k
  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.2k
}
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
}