1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
/*
* Copyright 2014 Ecole Normale Superieure
*
* Use of this software is governed by the MIT license
*
* Written by Sven Verdoolaege,
* Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
*/
#include <isl_mat_private.h>
#include <isl_seq.h>
/* Given a matrix "div" representing local variables,
* is the variable at position "pos" marked as not having
* an explicit representation?
* Note that even if this variable is not marked in this way and therefore
* does have an explicit representation, this representation may still
* depend (indirectly) on other local variables that do not
* have an explicit representation.
*/
isl_bool isl_local_div_is_marked_unknown(__isl_keep isl_mat *div, int pos)
{
if (!div)
return isl_bool_error;
if (pos < 0 || pos >= div->n_row)
isl_die(isl_mat_get_ctx(div), isl_error_invalid,
"position out of bounds", return isl_bool_error);
return isl_int_is_zero(div->row[pos][0]);
}
/* Given a matrix "div" representing local variables,
* does the variable at position "pos" have a complete explicit representation?
* Having a complete explicit representation requires not only
* an explicit representation, but also that all local variables
* that appear in this explicit representation in turn have
* a complete explicit representation.
*/
isl_bool isl_local_div_is_known(__isl_keep isl_mat *div, int pos)
{
isl_bool marked;
int i, n, off;
if (!div)
return isl_bool_error;
if (pos < 0 || pos >= div->n_row)
isl_die(isl_mat_get_ctx(div), isl_error_invalid,
"position out of bounds", return isl_bool_error);
marked = isl_local_div_is_marked_unknown(div, pos);
if (marked < 0 || marked)
return isl_bool_not(marked);
n = isl_mat_rows(div);
off = isl_mat_cols(div) - n;
for (i = n - 1; i >= 0; --i) {
isl_bool known;
if (isl_int_is_zero(div->row[pos][off + i]))
continue;
known = isl_local_div_is_known(div, i);
if (known < 0 || !known)
return known;
}
return isl_bool_true;
}
/* Compare two matrices representing local variables, defined over
* the same space.
*
* Return -1 if "div1" is "smaller" than "div2", 1 if "div1" is "greater"
* than "div2" and 0 if they are equal.
*
* The order is fairly arbitrary. We do "prefer" divs that only involve
* earlier dimensions in the sense that we consider matrices where
* the first differing div involves earlier dimensions to be smaller.
*/
int isl_local_cmp(__isl_keep isl_mat *div1, __isl_keep isl_mat *div2)
{
int i;
int cmp;
isl_bool unknown1, unknown2;
int last1, last2;
int n_col;
if (div1 == div2)
return 0;
if (!div1)
return -1;
if (!div2)
return 1;
if (div1->n_row != div2->n_row)
return div1->n_row - div2->n_row;
n_col = isl_mat_cols(div1);
for (i = 0; i < div1->n_row; ++i) {
unknown1 = isl_local_div_is_marked_unknown(div1, i);
unknown2 = isl_local_div_is_marked_unknown(div2, i);
if (unknown1 && unknown2)
continue;
if (unknown1)
return 1;
if (unknown2)
return -1;
last1 = isl_seq_last_non_zero(div1->row[i] + 1, n_col - 1);
last2 = isl_seq_last_non_zero(div2->row[i] + 1, n_col - 1);
if (last1 != last2)
return last1 - last2;
cmp = isl_seq_cmp(div1->row[i], div2->row[i], n_col);
if (cmp != 0)
return cmp;
}
return 0;
}
|
