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