pet 0.11.8
[pet.git] / aff.c
blobba55a32b898bbeb1c2ba9559fbaf935661c6a97e
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 <isl/val.h>
36 #include <isl/space.h>
37 #include <isl/local_space.h>
38 #include <isl/aff.h>
39 #include <isl/set.h>
40 #include <isl/map.h>
41 #include <isl/union_map.h>
43 #include "aff.h"
45 /* Internal data structure for pet_union_map_move_dims.
47 * dst_type, dst_pos, src_type, src_pos and n are the arguments
48 * to the isl_map_move_dims calls
49 * res collects the results.
51 struct pet_union_map_move_dims_data {
52 enum isl_dim_type dst_type;
53 unsigned dst_pos;
54 enum isl_dim_type src_type;
55 unsigned src_pos;
56 unsigned n;
58 isl_union_map *res;
61 /* Call isl_map_move_dims on "map" using the arguments in "data" and
62 * add the result to data->res.
64 static isl_stat map_move_dims(__isl_take isl_map *map, void *user)
66 struct pet_union_map_move_dims_data *data = user;
68 map = isl_map_move_dims(map, data->dst_type, data->dst_pos,
69 data->src_type, data->src_pos, data->n);
70 data->res = isl_union_map_add_map(data->res, map);
72 return isl_stat_ok;
75 /* Call isl_map_move_dims with the given arguments on each of the maps
76 * in "umap" and return the union of the results.
78 * This function can only meaningfully be called on a union map
79 * where all maps have the same space for both dst_type and src_type.
80 * One of these should then be isl_dim_param as otherwise the union map
81 * could only contain a single map.
83 __isl_give isl_union_map *pet_union_map_move_dims(
84 __isl_take isl_union_map *umap,
85 enum isl_dim_type dst_type, unsigned dst_pos,
86 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
88 isl_space *space;
89 struct pet_union_map_move_dims_data data =
90 { dst_type, dst_pos, src_type, src_pos, n };
92 space = isl_union_map_get_space(umap);
93 if (src_type == isl_dim_param)
94 space = isl_space_drop_dims(space, src_type, src_pos, n);
95 data.res = isl_union_map_empty(space);
96 if (isl_union_map_foreach_map(umap, &map_move_dims, &data) < 0)
97 data.res = isl_union_map_free(data.res);
99 isl_union_map_free(umap);
100 return data.res;
103 /* Return a function that projects "space" onto its first "n" dimensions,
104 * with anonymous target space.
106 __isl_give isl_multi_aff *pet_prefix_projection(__isl_take isl_space *space,
107 int n)
109 int dim;
111 dim = isl_space_dim(space, isl_dim_set);
112 return isl_multi_aff_project_out_map(space, isl_dim_set, n, dim - n);
115 /* If the isl_pw_aff on which isl_pw_aff_foreach_piece is called
116 * has a constant expression on its only domain, then replace
117 * the isl_val in *user by this constant.
118 * The caller is assumed to have checked that this function will
119 * be called exactly once.
121 static isl_stat extract_cst(__isl_take isl_set *set, __isl_take isl_aff *aff,
122 void *user)
124 isl_val **inc = (isl_val **)user;
126 if (isl_aff_is_cst(aff)) {
127 isl_val_free(*inc);
128 *inc = isl_aff_get_constant_val(aff);
131 isl_set_free(set);
132 isl_aff_free(aff);
134 return isl_stat_ok;
137 /* If "pa" represents a constant value over a single domain,
138 * then return this constant.
139 * Otherwise return NaN.
141 __isl_give isl_val *pet_extract_cst(__isl_keep isl_pw_aff *pa)
143 isl_val *v;
145 if (!pa)
146 return NULL;
147 v = isl_val_nan(isl_pw_aff_get_ctx(pa));
148 if (isl_pw_aff_n_piece(pa) != 1)
149 return v;
150 if (isl_pw_aff_foreach_piece(pa, &extract_cst, &v) < 0)
151 v = isl_val_free(v);
152 return v;
155 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
157 static __isl_give isl_pw_aff *indicator_function(__isl_take isl_set *set,
158 __isl_take isl_set *dom)
160 isl_pw_aff *pa;
161 pa = isl_set_indicator_function(set);
162 pa = isl_pw_aff_intersect_domain(pa, isl_set_coalesce(dom));
163 return pa;
166 /* Return "lhs && rhs", defined on the shared definition domain.
168 __isl_give isl_pw_aff *pet_and(__isl_take isl_pw_aff *lhs,
169 __isl_take isl_pw_aff *rhs)
171 isl_set *cond;
172 isl_set *dom;
174 dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs)),
175 isl_pw_aff_domain(isl_pw_aff_copy(rhs)));
176 cond = isl_set_intersect(isl_pw_aff_non_zero_set(lhs),
177 isl_pw_aff_non_zero_set(rhs));
178 return indicator_function(cond, dom);
181 /* Return "!pa", defined on the domain of "pa".
183 * If "pa" involves any NaN, then return NaN.
185 __isl_give isl_pw_aff *pet_not(__isl_take isl_pw_aff *pa)
187 isl_set *cond, *dom;
189 if (!pa)
190 return NULL;
191 if (isl_pw_aff_involves_nan(pa)) {
192 isl_space *space = isl_pw_aff_get_domain_space(pa);
193 isl_local_space *ls = isl_local_space_from_space(space);
194 isl_pw_aff_free(pa);
195 return isl_pw_aff_nan_on_domain(ls);
198 dom = isl_pw_aff_domain(isl_pw_aff_copy(pa));
199 cond = isl_pw_aff_zero_set(pa);
200 pa = indicator_function(cond, dom);
202 return pa;
205 /* Return "!!pa", i.e., a function that is equal to 1 when "pa"
206 * is non-zero and equal to 0 when "pa" is equal to zero,
207 * on the domain of "pa".
209 * If "pa" involves any NaN, then return NaN.
211 __isl_give isl_pw_aff *pet_to_bool(__isl_take isl_pw_aff *pa)
213 isl_set *cond, *dom;
215 if (!pa)
216 return NULL;
217 if (isl_pw_aff_involves_nan(pa)) {
218 isl_space *space = isl_pw_aff_get_domain_space(pa);
219 isl_local_space *ls = isl_local_space_from_space(space);
220 isl_pw_aff_free(pa);
221 return isl_pw_aff_nan_on_domain(ls);
224 dom = isl_pw_aff_domain(isl_pw_aff_copy(pa));
225 cond = isl_pw_aff_non_zero_set(pa);
226 pa = indicator_function(cond, dom);
228 return pa;
231 /* Return the result of applying the comparison operator "type"
232 * to "pa1" and "pa2".
234 * In particular, construct an isl_pw_aff that is equal to 1
235 * on the subset of the shared domain of "pa1" and "pa2" where
236 * the comparison holds and 0 on the other part of the shared domain.
238 * If "pa1" or "pa2" involve any NaN, then return NaN.
240 __isl_give isl_pw_aff *pet_comparison(enum pet_op_type type,
241 __isl_take isl_pw_aff *pa1, __isl_take isl_pw_aff *pa2)
243 isl_set *dom;
244 isl_set *cond;
245 isl_pw_aff *res;
247 if (!pa1 || !pa2)
248 goto error;
249 if (isl_pw_aff_involves_nan(pa1) || isl_pw_aff_involves_nan(pa2)) {
250 isl_space *space = isl_pw_aff_get_domain_space(pa1);
251 isl_local_space *ls = isl_local_space_from_space(space);
252 isl_pw_aff_free(pa1);
253 isl_pw_aff_free(pa2);
254 return isl_pw_aff_nan_on_domain(ls);
257 dom = isl_pw_aff_domain(isl_pw_aff_copy(pa1));
258 dom = isl_set_intersect(dom, isl_pw_aff_domain(isl_pw_aff_copy(pa2)));
260 switch (type) {
261 case pet_op_lt:
262 cond = isl_pw_aff_lt_set(pa1, pa2);
263 break;
264 case pet_op_le:
265 cond = isl_pw_aff_le_set(pa1, pa2);
266 break;
267 case pet_op_gt:
268 cond = isl_pw_aff_gt_set(pa1, pa2);
269 break;
270 case pet_op_ge:
271 cond = isl_pw_aff_ge_set(pa1, pa2);
272 break;
273 case pet_op_eq:
274 cond = isl_pw_aff_eq_set(pa1, pa2);
275 break;
276 case pet_op_ne:
277 cond = isl_pw_aff_ne_set(pa1, pa2);
278 break;
279 default:
280 isl_die(isl_pw_aff_get_ctx(pa1), isl_error_internal,
281 "not a comparison operator", cond = NULL);
282 isl_pw_aff_free(pa1);
283 isl_pw_aff_free(pa2);
286 cond = isl_set_coalesce(cond);
287 res = indicator_function(cond, dom);
289 return res;
290 error:
291 isl_pw_aff_free(pa1);
292 isl_pw_aff_free(pa2);
293 return NULL;
296 /* Return "lhs && rhs", with shortcut semantics.
297 * That is, if lhs is false, then the result is defined even if rhs is not.
298 * In practice, we compute lhs ? rhs : lhs.
300 static __isl_give isl_pw_aff *pw_aff_and_then(__isl_take isl_pw_aff *lhs,
301 __isl_take isl_pw_aff *rhs)
303 return isl_pw_aff_cond(isl_pw_aff_copy(lhs), rhs, lhs);
306 /* Return "lhs || rhs", with shortcut semantics.
307 * That is, if lhs is true, then the result is defined even if rhs is not.
308 * In practice, we compute lhs ? lhs : rhs.
310 static __isl_give isl_pw_aff *pw_aff_or_else(__isl_take isl_pw_aff *lhs,
311 __isl_take isl_pw_aff *rhs)
313 return isl_pw_aff_cond(isl_pw_aff_copy(lhs), lhs, rhs);
316 /* Return the result of applying the boolean operator "type"
317 * to "pa1" and "pa2".
319 __isl_give isl_pw_aff *pet_boolean(enum pet_op_type type,
320 __isl_take isl_pw_aff *pa1, __isl_take isl_pw_aff *pa2)
322 isl_ctx *ctx;
324 switch (type) {
325 case pet_op_land:
326 return pw_aff_and_then(pa1, pa2);
327 case pet_op_lor:
328 return pw_aff_or_else(pa1, pa2);
329 default:
330 ctx = isl_pw_aff_get_ctx(pa1);
331 isl_pw_aff_free(pa1);
332 isl_pw_aff_free(pa2);
333 isl_die(ctx, isl_error_internal,
334 "not a boolean operator", return NULL);
338 /* Return an isl_val equal to
340 * 2^width
342 static __isl_give isl_val *wrap_mod(isl_ctx *ctx, unsigned width)
344 return isl_val_2exp(isl_val_int_from_ui(ctx, width));
347 /* Compute
349 * aff mod 2^width
351 __isl_give isl_aff *pet_wrap_aff(__isl_take isl_aff *aff, unsigned width)
353 isl_val *mod;
355 mod = wrap_mod(isl_aff_get_ctx(aff), width);
356 aff = isl_aff_mod_val(aff, mod);
358 return aff;
361 /* Compute
363 * pwaff mod 2^width
365 __isl_give isl_pw_aff *pet_wrap_pw_aff(__isl_take isl_pw_aff *pwaff,
366 unsigned width)
368 isl_val *mod;
370 mod = wrap_mod(isl_pw_aff_get_ctx(pwaff), width);
371 pwaff = isl_pw_aff_mod_val(pwaff, mod);
373 return pwaff;