Coverage Report

Created: 2018-04-23 18:20

/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_seq.h>
17
#include <isl_local.h>
18
19
/* Return the isl_ctx to which "local" belongs.
20
 */
21
isl_ctx *isl_local_get_ctx(__isl_keep isl_local *local)
22
0
{
23
0
  if (!local)
24
0
    return NULL;
25
0
26
0
  return isl_mat_get_ctx(local);
27
0
}
28
29
/* Return the number of local variables (isl_dim_div),
30
 * the number of other variables (isl_dim_set) or
31
 * the total number of variables (isl_dim_all) in "local".
32
 *
33
 * Other types do not have any meaning for an isl_local object.
34
 */
35
int isl_local_dim(__isl_keep isl_local *local, enum isl_dim_type type)
36
345k
{
37
345k
  isl_mat *mat = local;
38
345k
39
345k
  if (!local)
40
0
    return 0;
41
345k
  if (type == isl_dim_div)
42
345k
    return isl_mat_rows(mat);
43
64
  if (type == isl_dim_all)
44
32
    return isl_mat_cols(mat) - 2;
45
32
  if (type == isl_dim_set)
46
32
    return isl_local_dim(local, isl_dim_all) -
47
32
      isl_local_dim(local, isl_dim_div);
48
0
  isl_die(isl_local_get_ctx(local), isl_error_unsupported,
49
0
    "unsupported dimension type", return 0);
50
0
}
51
52
/* Check that "pos" is a valid position for a variable in "local".
53
 */
54
static isl_stat isl_local_check_pos(__isl_keep isl_local *local, int pos)
55
82.4k
{
56
82.4k
  if (!local)
57
0
    return isl_stat_error;
58
82.4k
  if (pos < 0 || pos >= isl_local_dim(local, isl_dim_div))
59
82.4k
    
isl_die0
(isl_local_get_ctx(local), isl_error_invalid,
60
82.4k
      "position out of bounds", return isl_stat_error);
61
82.4k
  return isl_stat_ok;
62
82.4k
}
63
64
/* Given local variables "local",
65
 * is the variable at position "pos" marked as not having
66
 * an explicit representation?
67
 * Note that even if this variable is not marked in this way and therefore
68
 * does have an explicit representation, this representation may still
69
 * depend (indirectly) on other local variables that do not
70
 * have an explicit representation.
71
 */
72
isl_bool isl_local_div_is_marked_unknown(__isl_keep isl_local *local, int pos)
73
81.6k
{
74
81.6k
  isl_mat *mat = local;
75
81.6k
76
81.6k
  if (isl_local_check_pos(local, pos) < 0)
77
0
    return isl_bool_error;
78
81.6k
  return isl_int_is_zero(mat->row[pos][0]);
79
81.6k
}
80
81
/* Given local variables "local",
82
 * does the variable at position "pos" have a complete explicit representation?
83
 * Having a complete explicit representation requires not only
84
 * an explicit representation, but also that all local variables
85
 * that appear in this explicit representation in turn have
86
 * a complete explicit representation.
87
 */
88
isl_bool isl_local_div_is_known(__isl_keep isl_local *local, int pos)
89
746
{
90
746
  isl_bool marked;
91
746
  int i, n, off;
92
746
  isl_mat *mat = local;
93
746
94
746
  if (isl_local_check_pos(local, pos) < 0)
95
0
    return isl_bool_error;
96
746
97
746
  marked = isl_local_div_is_marked_unknown(local, pos);
98
746
  if (marked < 0 || marked)
99
9
    return isl_bool_not(marked);
100
737
101
737
  n = isl_local_dim(local, isl_dim_div);
102
737
  off = isl_mat_cols(mat) - n;
103
737
104
1.84k
  for (i = n - 1; i >= 0; 
--i1.10k
) {
105
1.10k
    isl_bool known;
106
1.10k
107
1.10k
    if (isl_int_is_zero(mat->row[pos][off + i]))
108
1.10k
      
continue1.10k
;
109
2
    known = isl_local_div_is_known(local, i);
110
2
    if (known < 0 || !known)
111
0
      return known;
112
2
  }
113
737
114
737
  return isl_bool_true;
115
737
}
116
117
/* Does "local" have an explicit representation for all local variables?
118
 */
119
isl_bool isl_local_divs_known(__isl_keep isl_local *local)
120
261k
{
121
261k
  int i, n;
122
261k
123
261k
  if (!local)
124
0
    return isl_bool_error;
125
261k
126
261k
  n = isl_local_dim(local, isl_dim_div);
127
342k
  for (i = 0; i < n; 
++i80.6k
) {
128
80.6k
    isl_bool unknown = isl_local_div_is_marked_unknown(local, i);
129
80.6k
    if (unknown < 0 || unknown)
130
0
      return isl_bool_not(unknown);
131
80.6k
  }
132
261k
133
261k
  return isl_bool_true;
134
261k
}
135
136
/* Compare two sets of local variables, defined over
137
 * the same space.
138
 *
139
 * Return -1 if "local1" is "smaller" than "local2", 1 if "local1" is "greater"
140
 * than "local2" and 0 if they are equal.
141
 *
142
 * The order is fairly arbitrary.  We do "prefer" divs that only involve
143
 * earlier dimensions in the sense that we consider matrices where
144
 * the first differing div involves earlier dimensions to be smaller.
145
 */
146
int isl_local_cmp(__isl_keep isl_local *local1, __isl_keep isl_local *local2)
147
6.79k
{
148
6.79k
  int i;
149
6.79k
  int cmp;
150
6.79k
  isl_bool unknown1, unknown2;
151
6.79k
  int last1, last2;
152
6.79k
  int n_col;
153
6.79k
  isl_mat *mat1 = local1;
154
6.79k
  isl_mat *mat2 = local2;
155
6.79k
156
6.79k
  if (local1 == local2)
157
0
    return 0;
158
6.79k
  if (!local1)
159
0
    return -1;
160
6.79k
  if (!local2)
161
0
    return 1;
162
6.79k
163
6.79k
  if (mat1->n_row != mat2->n_row)
164
151
    return mat1->n_row - mat2->n_row;
165
6.64k
166
6.64k
  n_col = isl_mat_cols(mat1);
167
6.66k
  for (i = 0; i < mat1->n_row; 
++i16
) {
168
158
    unknown1 = isl_local_div_is_marked_unknown(local1, i);
169
158
    unknown2 = isl_local_div_is_marked_unknown(local2, i);
170
158
    if (unknown1 && 
unknown20
)
171
0
      continue;
172
158
    if (unknown1)
173
0
      return 1;
174
158
    if (unknown2)
175
0
      return -1;
176
158
    last1 = isl_seq_last_non_zero(mat1->row[i] + 1, n_col - 1);
177
158
    last2 = isl_seq_last_non_zero(mat2->row[i] + 1, n_col - 1);
178
158
    if (last1 != last2)
179
30
      return last1 - last2;
180
128
    cmp = isl_seq_cmp(mat1->row[i], mat2->row[i], n_col);
181
128
    if (cmp != 0)
182
112
      return cmp;
183
128
  }
184
6.64k
185
6.64k
  
return 06.50k
;
186
6.64k
}
187
188
/* Extend a vector "v" representing an integer point
189
 * in the domain space of "local"
190
 * to one that also includes values for the local variables.
191
 * All local variables are required to have an explicit representation.
192
 */
193
__isl_give isl_vec *isl_local_extend_point_vec(__isl_keep isl_local *local,
194
  __isl_take isl_vec *v)
195
20
{
196
20
  unsigned n_div;
197
20
  isl_bool known;
198
20
  isl_mat *mat = local;
199
20
200
20
  if (!local || !v)
201
0
    return isl_vec_free(v);
202
20
  known = isl_local_divs_known(local);
203
20
  if (known < 0)
204
0
    return isl_vec_free(v);
205
20
  if (!known)
206
20
    
isl_die0
(isl_local_get_ctx(local), isl_error_invalid,
207
20
      "unknown local variables", return isl_vec_free(v));
208
20
  if (isl_vec_size(v) != 1 + isl_local_dim(local, isl_dim_set))
209
20
    
isl_die0
(isl_local_get_ctx(local), isl_error_invalid,
210
20
      "incorrect size", return isl_vec_free(v));
211
20
  if (!isl_int_is_one(v->el[0]))
212
20
    
isl_die0
(isl_local_get_ctx(local), isl_error_invalid,
213
20
      "expecting integer point", return isl_vec_free(v));
214
20
  n_div = isl_local_dim(local, isl_dim_div);
215
20
  if (n_div != 0) {
216
12
    int i;
217
12
    unsigned dim = isl_local_dim(local, isl_dim_set);
218
12
    v = isl_vec_add_els(v, n_div);
219
12
    if (!v)
220
0
      return NULL;
221
12
222
36
    
for (i = 0; 12
i < n_div;
++i24
) {
223
24
      isl_seq_inner_product(mat->row[i] + 1, v->el,
224
24
            1 + dim + i, &v->el[1+dim+i]);
225
24
      isl_int_fdiv_q(v->el[1+dim+i], v->el[1+dim+i],
226
24
          mat->row[i][0]);
227
24
    }
228
12
  }
229
20
230
20
  return v;
231
20
}