2 * Copyright 2011 INRIA Saclay
3 * Copyright 2014 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
13 #include <isl_vec_private.h>
14 #include <isl_mat_private.h>
16 #include <isl_local.h>
18 /* Return the isl_ctx to which "local" belongs.
20 isl_ctx
*isl_local_get_ctx(__isl_keep isl_local
*local
)
25 return isl_mat_get_ctx(local
);
28 /* Return the number of local variables (isl_dim_div),
29 * the number of other variables (isl_dim_set) or
30 * the total number of variables (isl_dim_all) in "local".
32 * Other types do not have any meaning for an isl_local object.
34 int isl_local_dim(__isl_keep isl_local
*local
, enum isl_dim_type type
)
40 if (type
== isl_dim_div
)
41 return isl_mat_rows(mat
);
42 if (type
== isl_dim_all
)
43 return isl_mat_cols(mat
) - 2;
44 if (type
== isl_dim_set
)
45 return isl_local_dim(local
, isl_dim_all
) -
46 isl_local_dim(local
, isl_dim_div
);
47 isl_die(isl_local_get_ctx(local
), isl_error_unsupported
,
48 "unsupported dimension type", return 0);
51 /* Check that "pos" is a valid position for a variable in "local".
53 static isl_stat
isl_local_check_pos(__isl_keep isl_local
*local
, int pos
)
56 return isl_stat_error
;
57 if (pos
< 0 || pos
>= isl_local_dim(local
, isl_dim_div
))
58 isl_die(isl_local_get_ctx(local
), isl_error_invalid
,
59 "position out of bounds", return isl_stat_error
);
63 /* Given local variables "local",
64 * is the variable at position "pos" marked as not having
65 * an explicit representation?
66 * Note that even if this variable is not marked in this way and therefore
67 * does have an explicit representation, this representation may still
68 * depend (indirectly) on other local variables that do not
69 * have an explicit representation.
71 isl_bool
isl_local_div_is_marked_unknown(__isl_keep isl_local
*local
, int pos
)
75 if (isl_local_check_pos(local
, pos
) < 0)
76 return isl_bool_error
;
77 return isl_int_is_zero(mat
->row
[pos
][0]);
80 /* Given local variables "local",
81 * does the variable at position "pos" have a complete explicit representation?
82 * Having a complete explicit representation requires not only
83 * an explicit representation, but also that all local variables
84 * that appear in this explicit representation in turn have
85 * a complete explicit representation.
87 isl_bool
isl_local_div_is_known(__isl_keep isl_local
*local
, int pos
)
93 if (isl_local_check_pos(local
, pos
) < 0)
94 return isl_bool_error
;
96 marked
= isl_local_div_is_marked_unknown(local
, pos
);
97 if (marked
< 0 || marked
)
98 return isl_bool_not(marked
);
100 n
= isl_local_dim(local
, isl_dim_div
);
101 off
= isl_mat_cols(mat
) - n
;
103 for (i
= n
- 1; i
>= 0; --i
) {
106 if (isl_int_is_zero(mat
->row
[pos
][off
+ i
]))
108 known
= isl_local_div_is_known(local
, i
);
109 if (known
< 0 || !known
)
113 return isl_bool_true
;
116 /* Does "local" have an explicit representation for all local variables?
118 isl_bool
isl_local_divs_known(__isl_keep isl_local
*local
)
123 return isl_bool_error
;
125 n
= isl_local_dim(local
, isl_dim_div
);
126 for (i
= 0; i
< n
; ++i
) {
127 isl_bool unknown
= isl_local_div_is_marked_unknown(local
, i
);
128 if (unknown
< 0 || unknown
)
129 return isl_bool_not(unknown
);
132 return isl_bool_true
;
135 /* Compare two sets of local variables, defined over
138 * Return -1 if "local1" is "smaller" than "local2", 1 if "local1" is "greater"
139 * than "local2" and 0 if they are equal.
141 * The order is fairly arbitrary. We do "prefer" divs that only involve
142 * earlier dimensions in the sense that we consider matrices where
143 * the first differing div involves earlier dimensions to be smaller.
145 int isl_local_cmp(__isl_keep isl_local
*local1
, __isl_keep isl_local
*local2
)
149 isl_bool unknown1
, unknown2
;
152 isl_mat
*mat1
= local1
;
153 isl_mat
*mat2
= local2
;
155 if (local1
== local2
)
162 if (mat1
->n_row
!= mat2
->n_row
)
163 return mat1
->n_row
- mat2
->n_row
;
165 n_col
= isl_mat_cols(mat1
);
166 for (i
= 0; i
< mat1
->n_row
; ++i
) {
167 unknown1
= isl_local_div_is_marked_unknown(local1
, i
);
168 unknown2
= isl_local_div_is_marked_unknown(local2
, i
);
169 if (unknown1
&& unknown2
)
175 last1
= isl_seq_last_non_zero(mat1
->row
[i
] + 1, n_col
- 1);
176 last2
= isl_seq_last_non_zero(mat2
->row
[i
] + 1, n_col
- 1);
178 return last1
- last2
;
179 cmp
= isl_seq_cmp(mat1
->row
[i
], mat2
->row
[i
], n_col
);
187 /* Extend a vector "v" representing an integer point
188 * in the domain space of "local"
189 * to one that also includes values for the local variables.
190 * All local variables are required to have an explicit representation.
192 __isl_give isl_vec
*isl_local_extend_point_vec(__isl_keep isl_local
*local
,
193 __isl_take isl_vec
*v
)
197 isl_mat
*mat
= local
;
200 return isl_vec_free(v
);
201 known
= isl_local_divs_known(local
);
203 return isl_vec_free(v
);
205 isl_die(isl_local_get_ctx(local
), isl_error_invalid
,
206 "unknown local variables", return isl_vec_free(v
));
207 if (isl_vec_size(v
) != 1 + isl_local_dim(local
, isl_dim_set
))
208 isl_die(isl_local_get_ctx(local
), isl_error_invalid
,
209 "incorrect size", return isl_vec_free(v
));
210 if (!isl_int_is_one(v
->el
[0]))
211 isl_die(isl_local_get_ctx(local
), isl_error_invalid
,
212 "expecting integer point", return isl_vec_free(v
));
213 n_div
= isl_local_dim(local
, isl_dim_div
);
216 unsigned dim
= isl_local_dim(local
, isl_dim_set
);
217 v
= isl_vec_add_els(v
, n_div
);
221 for (i
= 0; i
< n_div
; ++i
) {
222 isl_seq_inner_product(mat
->row
[i
] + 1, v
->el
,
223 1 + dim
+ i
, &v
->el
[1+dim
+i
]);
224 isl_int_fdiv_q(v
->el
[1+dim
+i
], v
->el
[1+dim
+i
],