push affine conditions into index expressions
[pet.git] / aff.c
blobb4e684c94f91feac14234f3f88008ad7d0ee6890
1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2014 Ecole Normale Superieure. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following
14 * disclaimer in the documentation and/or other materials provided
15 * with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
24 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 * The views and conclusions contained in the software and documentation
30 * are those of the authors and should not be interpreted as
31 * representing official policies, either expressed or implied, of
32 * Leiden University.
35 #include "aff.h"
37 /* Internal data structure for pet_union_map_move_dims.
39 * dst_type, dst_pos, src_type, src_pos and n are the arguments
40 * to the isl_map_move_dims calls
41 * res collects the results.
43 struct pet_union_map_move_dims_data {
44 enum isl_dim_type dst_type;
45 unsigned dst_pos;
46 enum isl_dim_type src_type;
47 unsigned src_pos;
48 unsigned n;
50 isl_union_map *res;
53 /* Call isl_map_move_dims on "map" using the arguments in "data" and
54 * add the result to data->res.
56 static isl_stat map_move_dims(__isl_take isl_map *map, void *user)
58 struct pet_union_map_move_dims_data *data = user;
60 map = isl_map_move_dims(map, data->dst_type, data->dst_pos,
61 data->src_type, data->src_pos, data->n);
62 data->res = isl_union_map_add_map(data->res, map);
64 return isl_stat_ok;
67 /* Call isl_map_move_dims with the given arguments on each of the maps
68 * in "umap" and return the union of the results.
70 * This function can only meaningfully be called on a union map
71 * where all maps have the same space for both dst_type and src_type.
72 * One of these should then be isl_dim_param as otherwise the union map
73 * could only contain a single map.
75 __isl_give isl_union_map *pet_union_map_move_dims(
76 __isl_take isl_union_map *umap,
77 enum isl_dim_type dst_type, unsigned dst_pos,
78 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
80 isl_space *space;
81 struct pet_union_map_move_dims_data data =
82 { dst_type, dst_pos, src_type, src_pos, n };
84 space = isl_union_map_get_space(umap);
85 if (src_type == isl_dim_param)
86 space = isl_space_drop_dims(space, src_type, src_pos, n);
87 data.res = isl_union_map_empty(space);
88 if (isl_union_map_foreach_map(umap, &map_move_dims, &data) < 0)
89 data.res = isl_union_map_free(data.res);
91 isl_union_map_free(umap);
92 return data.res;
95 /* Return a function that projects "space" onto its first "n" dimensions,
96 * with anonymous target space.
98 __isl_give isl_multi_aff *pet_prefix_projection(__isl_take isl_space *space,
99 int n)
101 int dim;
103 dim = isl_space_dim(space, isl_dim_set);
104 return isl_multi_aff_project_out_map(space, isl_dim_set, n, dim - n);
107 /* If the isl_pw_aff on which isl_pw_aff_foreach_piece is called
108 * has a constant expression on its only domain, then replace
109 * the isl_val in *user by this constant.
110 * The caller is assumed to have checked that this function will
111 * be called exactly once.
113 static isl_stat extract_cst(__isl_take isl_set *set, __isl_take isl_aff *aff,
114 void *user)
116 isl_val **inc = (isl_val **)user;
118 if (isl_aff_is_cst(aff)) {
119 isl_val_free(*inc);
120 *inc = isl_aff_get_constant_val(aff);
123 isl_set_free(set);
124 isl_aff_free(aff);
126 return isl_stat_ok;
129 /* If "pa" represents a constant value over a single domain,
130 * then return this constant.
131 * Otherwise return NaN.
133 __isl_give isl_val *pet_extract_cst(__isl_keep isl_pw_aff *pa)
135 isl_val *v;
137 if (!pa)
138 return NULL;
139 v = isl_val_nan(isl_pw_aff_get_ctx(pa));
140 if (isl_pw_aff_n_piece(pa) != 1)
141 return v;
142 if (isl_pw_aff_foreach_piece(pa, &extract_cst, &v) < 0)
143 v = isl_val_free(v);
144 return v;
147 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
149 static __isl_give isl_pw_aff *indicator_function(__isl_take isl_set *set,
150 __isl_take isl_set *dom)
152 isl_pw_aff *pa;
153 pa = isl_set_indicator_function(set);
154 pa = isl_pw_aff_intersect_domain(pa, isl_set_coalesce(dom));
155 return pa;
158 /* Return "lhs && rhs", defined on the shared definition domain.
160 __isl_give isl_pw_aff *pet_and(__isl_take isl_pw_aff *lhs,
161 __isl_take isl_pw_aff *rhs)
163 isl_set *cond;
164 isl_set *dom;
166 dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs)),
167 isl_pw_aff_domain(isl_pw_aff_copy(rhs)));
168 cond = isl_set_intersect(isl_pw_aff_non_zero_set(lhs),
169 isl_pw_aff_non_zero_set(rhs));
170 return indicator_function(cond, dom);
173 /* Return "!pa", defined on the domain of "pa".
175 * If "pa" involves any NaN, then return NaN.
177 __isl_give isl_pw_aff *pet_not(__isl_take isl_pw_aff *pa)
179 isl_set *cond, *dom;
181 if (!pa)
182 return NULL;
183 if (isl_pw_aff_involves_nan(pa)) {
184 isl_space *space = isl_pw_aff_get_domain_space(pa);
185 isl_local_space *ls = isl_local_space_from_space(space);
186 isl_pw_aff_free(pa);
187 return isl_pw_aff_nan_on_domain(ls);
190 dom = isl_pw_aff_domain(isl_pw_aff_copy(pa));
191 cond = isl_pw_aff_zero_set(pa);
192 pa = indicator_function(cond, dom);
194 return pa;
197 /* Return "!!pa", i.e., a function that is equal to 1 when "pa"
198 * is non-zero and equal to 0 when "pa" is equal to zero,
199 * on the domain of "pa".
201 * If "pa" involves any NaN, then return NaN.
203 __isl_give isl_pw_aff *pet_to_bool(__isl_take isl_pw_aff *pa)
205 isl_set *cond, *dom;
207 if (!pa)
208 return NULL;
209 if (isl_pw_aff_involves_nan(pa)) {
210 isl_space *space = isl_pw_aff_get_domain_space(pa);
211 isl_local_space *ls = isl_local_space_from_space(space);
212 isl_pw_aff_free(pa);
213 return isl_pw_aff_nan_on_domain(ls);
216 dom = isl_pw_aff_domain(isl_pw_aff_copy(pa));
217 cond = isl_pw_aff_non_zero_set(pa);
218 pa = indicator_function(cond, dom);
220 return pa;
223 /* Return the result of applying the comparison operator "type"
224 * to "pa1" and "pa2".
226 * In particular, construct an isl_pw_aff that is equal to 1
227 * on the subset of the shared domain of "pa1" and "pa2" where
228 * the comparison holds and 0 on the other part of the shared domain.
230 * If "pa1" or "pa2" involve any NaN, then return NaN.
232 __isl_give isl_pw_aff *pet_comparison(enum pet_op_type type,
233 __isl_take isl_pw_aff *pa1, __isl_take isl_pw_aff *pa2)
235 isl_set *dom;
236 isl_set *cond;
237 isl_pw_aff *res;
239 if (!pa1 || !pa2)
240 goto error;
241 if (isl_pw_aff_involves_nan(pa1) || isl_pw_aff_involves_nan(pa2)) {
242 isl_space *space = isl_pw_aff_get_domain_space(pa1);
243 isl_local_space *ls = isl_local_space_from_space(space);
244 isl_pw_aff_free(pa1);
245 isl_pw_aff_free(pa2);
246 return isl_pw_aff_nan_on_domain(ls);
249 dom = isl_pw_aff_domain(isl_pw_aff_copy(pa1));
250 dom = isl_set_intersect(dom, isl_pw_aff_domain(isl_pw_aff_copy(pa2)));
252 switch (type) {
253 case pet_op_lt:
254 cond = isl_pw_aff_lt_set(pa1, pa2);
255 break;
256 case pet_op_le:
257 cond = isl_pw_aff_le_set(pa1, pa2);
258 break;
259 case pet_op_gt:
260 cond = isl_pw_aff_gt_set(pa1, pa2);
261 break;
262 case pet_op_ge:
263 cond = isl_pw_aff_ge_set(pa1, pa2);
264 break;
265 case pet_op_eq:
266 cond = isl_pw_aff_eq_set(pa1, pa2);
267 break;
268 case pet_op_ne:
269 cond = isl_pw_aff_ne_set(pa1, pa2);
270 break;
271 default:
272 isl_die(isl_pw_aff_get_ctx(pa1), isl_error_internal,
273 "not a comparison operator", cond = NULL);
274 isl_pw_aff_free(pa1);
275 isl_pw_aff_free(pa2);
278 cond = isl_set_coalesce(cond);
279 res = indicator_function(cond, dom);
281 return res;
282 error:
283 isl_pw_aff_free(pa1);
284 isl_pw_aff_free(pa2);
285 return NULL;
288 /* Return "lhs && rhs", with shortcut semantics.
289 * That is, if lhs is false, then the result is defined even if rhs is not.
290 * In practice, we compute lhs ? rhs : lhs.
292 static __isl_give isl_pw_aff *pw_aff_and_then(__isl_take isl_pw_aff *lhs,
293 __isl_take isl_pw_aff *rhs)
295 return isl_pw_aff_cond(isl_pw_aff_copy(lhs), rhs, lhs);
298 /* Return "lhs || rhs", with shortcut semantics.
299 * That is, if lhs is true, then the result is defined even if rhs is not.
300 * In practice, we compute lhs ? lhs : rhs.
302 static __isl_give isl_pw_aff *pw_aff_or_else(__isl_take isl_pw_aff *lhs,
303 __isl_take isl_pw_aff *rhs)
305 return isl_pw_aff_cond(isl_pw_aff_copy(lhs), lhs, rhs);
308 /* Return the result of applying the boolean operator "type"
309 * to "pa1" and "pa2".
311 __isl_give isl_pw_aff *pet_boolean(enum pet_op_type type,
312 __isl_take isl_pw_aff *pa1, __isl_take isl_pw_aff *pa2)
314 isl_ctx *ctx;
316 switch (type) {
317 case pet_op_land:
318 return pw_aff_and_then(pa1, pa2);
319 case pet_op_lor:
320 return pw_aff_or_else(pa1, pa2);
321 default:
322 ctx = isl_pw_aff_get_ctx(pa1);
323 isl_pw_aff_free(pa1);
324 isl_pw_aff_free(pa2);
325 isl_die(ctx, isl_error_internal,
326 "not a boolean operator", return NULL);