File: | tools/polly/lib/External/isl/isl_fold.c |
Warning: | line 918, column 4 Use of memory after it is freed |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* | |||
2 | * Copyright 2010 INRIA Saclay | |||
3 | * | |||
4 | * Use of this software is governed by the MIT license | |||
5 | * | |||
6 | * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, | |||
7 | * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, | |||
8 | * 91893 Orsay, France | |||
9 | */ | |||
10 | ||||
11 | #include <isl_map_private.h> | |||
12 | #include <isl_union_map_private.h> | |||
13 | #include <isl_polynomial_private.h> | |||
14 | #include <isl_point_private.h> | |||
15 | #include <isl_space_private.h> | |||
16 | #include <isl_lp_private.h> | |||
17 | #include <isl_seq.h> | |||
18 | #include <isl_mat_private.h> | |||
19 | #include <isl_val_private.h> | |||
20 | #include <isl_vec_private.h> | |||
21 | #include <isl_config.h> | |||
22 | ||||
23 | #undef BASEpw_qpolynomial_fold | |||
24 | #define BASEpw_qpolynomial_fold pw_qpolynomial_fold | |||
25 | ||||
26 | #include <isl_list_templ.c> | |||
27 | ||||
28 | enum isl_fold isl_fold_type_negate(enum isl_fold type) | |||
29 | { | |||
30 | switch (type) { | |||
31 | case isl_fold_min: | |||
32 | return isl_fold_max; | |||
33 | case isl_fold_max: | |||
34 | return isl_fold_min; | |||
35 | case isl_fold_list: | |||
36 | return isl_fold_list; | |||
37 | } | |||
38 | ||||
39 | isl_die(NULL, isl_error_internal, "unhandled isl_fold type", abort())do { isl_handle_error(((void*)0), isl_error_internal, "unhandled isl_fold type" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 39); abort(); } while (0); | |||
40 | } | |||
41 | ||||
42 | static __isl_give isl_qpolynomial_fold *qpolynomial_fold_alloc( | |||
43 | enum isl_fold type, __isl_take isl_space *dim, int n) | |||
44 | { | |||
45 | isl_qpolynomial_fold *fold; | |||
46 | ||||
47 | if (!dim) | |||
48 | goto error; | |||
49 | ||||
50 | isl_assert(dim->ctx, n >= 0, goto error)do { if (n >= 0) break; do { isl_handle_error(dim->ctx, isl_error_unknown, "Assertion \"" "n >= 0" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 50); goto error; } while (0); } while (0); | |||
51 | fold = isl_calloc(dim->ctx, struct isl_qpolynomial_fold,((struct isl_qpolynomial_fold *)isl_calloc_or_die(dim->ctx , 1, sizeof(struct isl_qpolynomial_fold) + (n - 1) * sizeof(struct isl_qpolynomial *))) | |||
52 | sizeof(struct isl_qpolynomial_fold) +((struct isl_qpolynomial_fold *)isl_calloc_or_die(dim->ctx , 1, sizeof(struct isl_qpolynomial_fold) + (n - 1) * sizeof(struct isl_qpolynomial *))) | |||
53 | (n - 1) * sizeof(struct isl_qpolynomial *))((struct isl_qpolynomial_fold *)isl_calloc_or_die(dim->ctx , 1, sizeof(struct isl_qpolynomial_fold) + (n - 1) * sizeof(struct isl_qpolynomial *))); | |||
54 | if (!fold) | |||
55 | goto error; | |||
56 | ||||
57 | fold->ref = 1; | |||
58 | fold->size = n; | |||
59 | fold->n = 0; | |||
60 | fold->type = type; | |||
61 | fold->dim = dim; | |||
62 | ||||
63 | return fold; | |||
64 | error: | |||
65 | isl_space_free(dim); | |||
66 | return NULL((void*)0); | |||
67 | } | |||
68 | ||||
69 | isl_ctx *isl_qpolynomial_fold_get_ctx(__isl_keep isl_qpolynomial_fold *fold) | |||
70 | { | |||
71 | return fold ? fold->dim->ctx : NULL((void*)0); | |||
72 | } | |||
73 | ||||
74 | __isl_give isl_space *isl_qpolynomial_fold_get_domain_space( | |||
75 | __isl_keep isl_qpolynomial_fold *fold) | |||
76 | { | |||
77 | return fold ? isl_space_copy(fold->dim) : NULL((void*)0); | |||
78 | } | |||
79 | ||||
80 | __isl_give isl_space *isl_qpolynomial_fold_get_space( | |||
81 | __isl_keep isl_qpolynomial_fold *fold) | |||
82 | { | |||
83 | isl_space *space; | |||
84 | if (!fold) | |||
85 | return NULL((void*)0); | |||
86 | space = isl_space_copy(fold->dim); | |||
87 | space = isl_space_from_domain(space); | |||
88 | space = isl_space_add_dims(space, isl_dim_out, 1); | |||
89 | return space; | |||
90 | } | |||
91 | ||||
92 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_reset_domain_space( | |||
93 | __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *dim) | |||
94 | { | |||
95 | int i; | |||
96 | ||||
97 | fold = isl_qpolynomial_fold_cow(fold); | |||
98 | if (!fold || !dim) | |||
99 | goto error; | |||
100 | ||||
101 | for (i = 0; i < fold->n; ++i) { | |||
102 | fold->qp[i] = isl_qpolynomial_reset_domain_space(fold->qp[i], | |||
103 | isl_space_copy(dim)); | |||
104 | if (!fold->qp[i]) | |||
105 | goto error; | |||
106 | } | |||
107 | ||||
108 | isl_space_free(fold->dim); | |||
109 | fold->dim = dim; | |||
110 | ||||
111 | return fold; | |||
112 | error: | |||
113 | isl_qpolynomial_fold_free(fold); | |||
114 | isl_space_free(dim); | |||
115 | return NULL((void*)0); | |||
116 | } | |||
117 | ||||
118 | /* Reset the space of "fold". This function is called from isl_pw_templ.c | |||
119 | * and doesn't know if the space of an element object is represented | |||
120 | * directly or through its domain. It therefore passes along both. | |||
121 | */ | |||
122 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_reset_space_and_domain( | |||
123 | __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *space, | |||
124 | __isl_take isl_space *domain) | |||
125 | { | |||
126 | isl_space_free(space); | |||
127 | return isl_qpolynomial_fold_reset_domain_space(fold, domain); | |||
128 | } | |||
129 | ||||
130 | int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold *fold, | |||
131 | enum isl_dim_type type, unsigned first, unsigned n) | |||
132 | { | |||
133 | int i; | |||
134 | ||||
135 | if (!fold) | |||
136 | return -1; | |||
137 | if (fold->n == 0 || n == 0) | |||
138 | return 0; | |||
139 | ||||
140 | for (i = 0; i < fold->n; ++i) { | |||
141 | int involves = isl_qpolynomial_involves_dims(fold->qp[i], | |||
142 | type, first, n); | |||
143 | if (involves < 0 || involves) | |||
144 | return involves; | |||
145 | } | |||
146 | return 0; | |||
147 | } | |||
148 | ||||
149 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_set_dim_name( | |||
150 | __isl_take isl_qpolynomial_fold *fold, | |||
151 | enum isl_dim_type type, unsigned pos, const char *s) | |||
152 | { | |||
153 | int i; | |||
154 | ||||
155 | fold = isl_qpolynomial_fold_cow(fold); | |||
156 | if (!fold) | |||
157 | return NULL((void*)0); | |||
158 | fold->dim = isl_space_set_dim_name(fold->dim, type, pos, s); | |||
159 | if (!fold->dim) | |||
160 | goto error; | |||
161 | ||||
162 | for (i = 0; i < fold->n; ++i) { | |||
163 | fold->qp[i] = isl_qpolynomial_set_dim_name(fold->qp[i], | |||
164 | type, pos, s); | |||
165 | if (!fold->qp[i]) | |||
166 | goto error; | |||
167 | } | |||
168 | ||||
169 | return fold; | |||
170 | error: | |||
171 | isl_qpolynomial_fold_free(fold); | |||
172 | return NULL((void*)0); | |||
173 | } | |||
174 | ||||
175 | /* Given a dimension type for an isl_qpolynomial_fold, | |||
176 | * return the corresponding type for the domain. | |||
177 | */ | |||
178 | static enum isl_dim_type domain_type(enum isl_dim_type type) | |||
179 | { | |||
180 | if (type == isl_dim_in) | |||
181 | return isl_dim_set; | |||
182 | return type; | |||
183 | } | |||
184 | ||||
185 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_drop_dims( | |||
186 | __isl_take isl_qpolynomial_fold *fold, | |||
187 | enum isl_dim_type type, unsigned first, unsigned n) | |||
188 | { | |||
189 | int i; | |||
190 | enum isl_dim_type set_type; | |||
191 | ||||
192 | if (!fold) | |||
193 | return NULL((void*)0); | |||
194 | if (n == 0) | |||
195 | return fold; | |||
196 | ||||
197 | set_type = domain_type(type); | |||
198 | ||||
199 | fold = isl_qpolynomial_fold_cow(fold); | |||
200 | if (!fold) | |||
201 | return NULL((void*)0); | |||
202 | fold->dim = isl_space_drop_dims(fold->dim, set_type, first, n); | |||
203 | if (!fold->dim) | |||
204 | goto error; | |||
205 | ||||
206 | for (i = 0; i < fold->n; ++i) { | |||
207 | fold->qp[i] = isl_qpolynomial_drop_dims(fold->qp[i], | |||
208 | type, first, n); | |||
209 | if (!fold->qp[i]) | |||
210 | goto error; | |||
211 | } | |||
212 | ||||
213 | return fold; | |||
214 | error: | |||
215 | isl_qpolynomial_fold_free(fold); | |||
216 | return NULL((void*)0); | |||
217 | } | |||
218 | ||||
219 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_insert_dims( | |||
220 | __isl_take isl_qpolynomial_fold *fold, | |||
221 | enum isl_dim_type type, unsigned first, unsigned n) | |||
222 | { | |||
223 | int i; | |||
224 | ||||
225 | if (!fold) | |||
226 | return NULL((void*)0); | |||
227 | if (n == 0 && !isl_space_is_named_or_nested(fold->dim, type)) | |||
228 | return fold; | |||
229 | ||||
230 | fold = isl_qpolynomial_fold_cow(fold); | |||
231 | if (!fold) | |||
232 | return NULL((void*)0); | |||
233 | fold->dim = isl_space_insert_dims(fold->dim, type, first, n); | |||
234 | if (!fold->dim) | |||
235 | goto error; | |||
236 | ||||
237 | for (i = 0; i < fold->n; ++i) { | |||
238 | fold->qp[i] = isl_qpolynomial_insert_dims(fold->qp[i], | |||
239 | type, first, n); | |||
240 | if (!fold->qp[i]) | |||
241 | goto error; | |||
242 | } | |||
243 | ||||
244 | return fold; | |||
245 | error: | |||
246 | isl_qpolynomial_fold_free(fold); | |||
247 | return NULL((void*)0); | |||
248 | } | |||
249 | ||||
250 | /* Determine the sign of the constant quasipolynomial "qp". | |||
251 | * | |||
252 | * Return | |||
253 | * -1 if qp <= 0 | |||
254 | * 1 if qp >= 0 | |||
255 | * 0 if unknown | |||
256 | * | |||
257 | * For qp == 0, we can return either -1 or 1. In practice, we return 1. | |||
258 | * For qp == NaN, the sign is undefined, so we return 0. | |||
259 | */ | |||
260 | static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial *qp) | |||
261 | { | |||
262 | struct isl_upoly_cst *cst; | |||
263 | ||||
264 | if (isl_qpolynomial_is_nan(qp)) | |||
265 | return 0; | |||
266 | ||||
267 | cst = isl_upoly_as_cst(qp->upoly); | |||
268 | if (!cst) | |||
269 | return 0; | |||
270 | ||||
271 | return isl_int_sgn(cst->n)isl_sioimath_sgn(*(cst->n)) < 0 ? -1 : 1; | |||
272 | } | |||
273 | ||||
274 | static int isl_qpolynomial_aff_sign(__isl_keep isl_setisl_map *set, | |||
275 | __isl_keep isl_qpolynomial *qp) | |||
276 | { | |||
277 | enum isl_lp_result res; | |||
278 | isl_vec *aff; | |||
279 | isl_int opt; | |||
280 | int sgn = 0; | |||
281 | ||||
282 | aff = isl_qpolynomial_extract_affine(qp); | |||
283 | if (!aff) | |||
284 | return 0; | |||
285 | ||||
286 | isl_int_init(opt)isl_sioimath_init((opt)); | |||
287 | ||||
288 | res = isl_set_solve_lp(set, 0, aff->el + 1, aff->el[0], | |||
289 | &opt, NULL((void*)0), NULL((void*)0)); | |||
290 | if (res == isl_lp_error) | |||
291 | goto done; | |||
292 | if (res == isl_lp_empty || | |||
293 | (res == isl_lp_ok && !isl_int_is_neg(opt)(isl_sioimath_sgn(*(opt)) < 0))) { | |||
294 | sgn = 1; | |||
295 | goto done; | |||
296 | } | |||
297 | ||||
298 | res = isl_set_solve_lp(set, 1, aff->el + 1, aff->el[0], | |||
299 | &opt, NULL((void*)0), NULL((void*)0)); | |||
300 | if (res == isl_lp_ok && !isl_int_is_pos(opt)(isl_sioimath_sgn(*(opt)) > 0)) | |||
301 | sgn = -1; | |||
302 | ||||
303 | done: | |||
304 | isl_int_clear(opt)isl_sioimath_clear((opt)); | |||
305 | isl_vec_free(aff); | |||
306 | return sgn; | |||
307 | } | |||
308 | ||||
309 | /* Determine, if possible, the sign of the quasipolynomial "qp" on | |||
310 | * the domain "set". | |||
311 | * | |||
312 | * If qp is a constant, then the problem is trivial. | |||
313 | * If qp is linear, then we check if the minimum of the corresponding | |||
314 | * affine constraint is non-negative or if the maximum is non-positive. | |||
315 | * | |||
316 | * Otherwise, we check if the outermost variable "v" has a lower bound "l" | |||
317 | * in "set". If so, we write qp(v,v') as | |||
318 | * | |||
319 | * q(v,v') * (v - l) + r(v') | |||
320 | * | |||
321 | * if q(v,v') and r(v') have the same known sign, then the original | |||
322 | * quasipolynomial has the same sign as well. | |||
323 | * | |||
324 | * Return | |||
325 | * -1 if qp <= 0 | |||
326 | * 1 if qp >= 0 | |||
327 | * 0 if unknown | |||
328 | */ | |||
329 | static int isl_qpolynomial_sign(__isl_keep isl_setisl_map *set, | |||
330 | __isl_keep isl_qpolynomial *qp) | |||
331 | { | |||
332 | int d; | |||
333 | int i; | |||
334 | int is; | |||
335 | struct isl_upoly_rec *rec; | |||
336 | isl_vec *v; | |||
337 | isl_int l; | |||
338 | enum isl_lp_result res; | |||
339 | int sgn = 0; | |||
340 | ||||
341 | is = isl_qpolynomial_is_cst(qp, NULL((void*)0), NULL((void*)0)); | |||
342 | if (is < 0) | |||
343 | return 0; | |||
344 | if (is) | |||
345 | return isl_qpolynomial_cst_sign(qp); | |||
346 | ||||
347 | is = isl_qpolynomial_is_affine(qp); | |||
348 | if (is < 0) | |||
349 | return 0; | |||
350 | if (is) | |||
351 | return isl_qpolynomial_aff_sign(set, qp); | |||
352 | ||||
353 | if (qp->div->n_row > 0) | |||
354 | return 0; | |||
355 | ||||
356 | rec = isl_upoly_as_rec(qp->upoly); | |||
357 | if (!rec) | |||
358 | return 0; | |||
359 | ||||
360 | d = isl_space_dim(qp->dim, isl_dim_all); | |||
361 | v = isl_vec_alloc(set->ctx, 2 + d); | |||
362 | if (!v) | |||
363 | return 0; | |||
364 | ||||
365 | isl_seq_clr(v->el + 1, 1 + d); | |||
366 | isl_int_set_si(v->el[0], 1)isl_sioimath_set_si((v->el[0]), 1); | |||
367 | isl_int_set_si(v->el[2 + qp->upoly->var], 1)isl_sioimath_set_si((v->el[2 + qp->upoly->var]), 1); | |||
368 | ||||
369 | isl_int_init(l)isl_sioimath_init((l)); | |||
370 | ||||
371 | res = isl_set_solve_lp(set, 0, v->el + 1, v->el[0], &l, NULL((void*)0), NULL((void*)0)); | |||
372 | if (res == isl_lp_ok) { | |||
373 | isl_qpolynomial *min; | |||
374 | isl_qpolynomial *base; | |||
375 | isl_qpolynomial *r, *q; | |||
376 | isl_qpolynomial *t; | |||
377 | ||||
378 | min = isl_qpolynomial_cst_on_domain(isl_space_copy(qp->dim), l); | |||
379 | base = isl_qpolynomial_var_pow_on_domain(isl_space_copy(qp->dim), | |||
380 | qp->upoly->var, 1); | |||
381 | ||||
382 | r = isl_qpolynomial_alloc(isl_space_copy(qp->dim), 0, | |||
383 | isl_upoly_copy(rec->p[rec->n - 1])); | |||
384 | q = isl_qpolynomial_copy(r); | |||
385 | ||||
386 | for (i = rec->n - 2; i >= 0; --i) { | |||
387 | r = isl_qpolynomial_mul(r, isl_qpolynomial_copy(min)); | |||
388 | t = isl_qpolynomial_alloc(isl_space_copy(qp->dim), 0, | |||
389 | isl_upoly_copy(rec->p[i])); | |||
390 | r = isl_qpolynomial_add(r, t); | |||
391 | if (i == 0) | |||
392 | break; | |||
393 | q = isl_qpolynomial_mul(q, isl_qpolynomial_copy(base)); | |||
394 | q = isl_qpolynomial_add(q, isl_qpolynomial_copy(r)); | |||
395 | } | |||
396 | ||||
397 | if (isl_qpolynomial_is_zero(q)) | |||
398 | sgn = isl_qpolynomial_sign(set, r); | |||
399 | else if (isl_qpolynomial_is_zero(r)) | |||
400 | sgn = isl_qpolynomial_sign(set, q); | |||
401 | else { | |||
402 | int sgn_q, sgn_r; | |||
403 | sgn_r = isl_qpolynomial_sign(set, r); | |||
404 | sgn_q = isl_qpolynomial_sign(set, q); | |||
405 | if (sgn_r == sgn_q) | |||
406 | sgn = sgn_r; | |||
407 | } | |||
408 | ||||
409 | isl_qpolynomial_free(min); | |||
410 | isl_qpolynomial_free(base); | |||
411 | isl_qpolynomial_free(q); | |||
412 | isl_qpolynomial_free(r); | |||
413 | } | |||
414 | ||||
415 | isl_int_clear(l)isl_sioimath_clear((l)); | |||
416 | ||||
417 | isl_vec_free(v); | |||
418 | ||||
419 | return sgn; | |||
420 | } | |||
421 | ||||
422 | /* Combine "fold1" and "fold2" into a single reduction, eliminating | |||
423 | * those elements of one reduction that are already covered by the other | |||
424 | * reduction on "set". | |||
425 | * | |||
426 | * If "fold1" or "fold2" is an empty reduction, then return | |||
427 | * the other reduction. | |||
428 | * If "fold1" or "fold2" is a NaN, then return this NaN. | |||
429 | */ | |||
430 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold_on_domain( | |||
431 | __isl_keep isl_setisl_map *set, | |||
432 | __isl_take isl_qpolynomial_fold *fold1, | |||
433 | __isl_take isl_qpolynomial_fold *fold2) | |||
434 | { | |||
435 | int i, j; | |||
436 | int n1; | |||
437 | struct isl_qpolynomial_fold *res = NULL((void*)0); | |||
438 | int better; | |||
439 | ||||
440 | if (!fold1 || !fold2) | |||
441 | goto error; | |||
442 | ||||
443 | isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error)do { if (fold1->type == fold2->type) break; do { isl_handle_error (fold1->dim->ctx, isl_error_unknown, "Assertion \"" "fold1->type == fold2->type" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 443); goto error; } while (0); } while (0); | |||
444 | isl_assert(fold1->dim->ctx, isl_space_is_equal(fold1->dim, fold2->dim),do { if (isl_space_is_equal(fold1->dim, fold2->dim)) break ; do { isl_handle_error(fold1->dim->ctx, isl_error_unknown , "Assertion \"" "isl_space_is_equal(fold1->dim, fold2->dim)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 445); goto error; } while (0); } while (0) | |||
445 | goto error)do { if (isl_space_is_equal(fold1->dim, fold2->dim)) break ; do { isl_handle_error(fold1->dim->ctx, isl_error_unknown , "Assertion \"" "isl_space_is_equal(fold1->dim, fold2->dim)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 445); goto error; } while (0); } while (0); | |||
446 | ||||
447 | better = fold1->type == isl_fold_max ? -1 : 1; | |||
448 | ||||
449 | if (isl_qpolynomial_fold_is_empty(fold1) || | |||
450 | isl_qpolynomial_fold_is_nan(fold2)) { | |||
451 | isl_qpolynomial_fold_free(fold1); | |||
452 | return fold2; | |||
453 | } | |||
454 | ||||
455 | if (isl_qpolynomial_fold_is_empty(fold2) || | |||
456 | isl_qpolynomial_fold_is_nan(fold1)) { | |||
457 | isl_qpolynomial_fold_free(fold2); | |||
458 | return fold1; | |||
459 | } | |||
460 | ||||
461 | res = qpolynomial_fold_alloc(fold1->type, isl_space_copy(fold1->dim), | |||
462 | fold1->n + fold2->n); | |||
463 | if (!res) | |||
464 | goto error; | |||
465 | ||||
466 | for (i = 0; i < fold1->n; ++i) { | |||
467 | res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]); | |||
468 | if (!res->qp[res->n]) | |||
469 | goto error; | |||
470 | res->n++; | |||
471 | } | |||
472 | n1 = res->n; | |||
473 | ||||
474 | for (i = 0; i < fold2->n; ++i) { | |||
475 | for (j = n1 - 1; j >= 0; --j) { | |||
476 | isl_qpolynomial *d; | |||
477 | int sgn, equal; | |||
478 | equal = isl_qpolynomial_plain_is_equal(res->qp[j], | |||
479 | fold2->qp[i]); | |||
480 | if (equal < 0) | |||
481 | goto error; | |||
482 | if (equal) | |||
483 | break; | |||
484 | d = isl_qpolynomial_sub( | |||
485 | isl_qpolynomial_copy(res->qp[j]), | |||
486 | isl_qpolynomial_copy(fold2->qp[i])); | |||
487 | sgn = isl_qpolynomial_sign(set, d); | |||
488 | isl_qpolynomial_free(d); | |||
489 | if (sgn == 0) | |||
490 | continue; | |||
491 | if (sgn != better) | |||
492 | break; | |||
493 | isl_qpolynomial_free(res->qp[j]); | |||
494 | if (j != n1 - 1) | |||
495 | res->qp[j] = res->qp[n1 - 1]; | |||
496 | n1--; | |||
497 | if (n1 != res->n - 1) | |||
498 | res->qp[n1] = res->qp[res->n - 1]; | |||
499 | res->n--; | |||
500 | } | |||
501 | if (j >= 0) | |||
502 | continue; | |||
503 | res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]); | |||
504 | if (!res->qp[res->n]) | |||
505 | goto error; | |||
506 | res->n++; | |||
507 | } | |||
508 | ||||
509 | isl_qpolynomial_fold_free(fold1); | |||
510 | isl_qpolynomial_fold_free(fold2); | |||
511 | ||||
512 | return res; | |||
513 | error: | |||
514 | isl_qpolynomial_fold_free(res); | |||
515 | isl_qpolynomial_fold_free(fold1); | |||
516 | isl_qpolynomial_fold_free(fold2); | |||
517 | return NULL((void*)0); | |||
518 | } | |||
519 | ||||
520 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_qpolynomial( | |||
521 | __isl_take isl_qpolynomial_fold *fold, __isl_take isl_qpolynomial *qp) | |||
522 | { | |||
523 | int i; | |||
524 | ||||
525 | if (!fold || !qp) | |||
526 | goto error; | |||
527 | ||||
528 | if (isl_qpolynomial_is_zero(qp)) { | |||
529 | isl_qpolynomial_free(qp); | |||
530 | return fold; | |||
531 | } | |||
532 | ||||
533 | fold = isl_qpolynomial_fold_cow(fold); | |||
534 | if (!fold) | |||
535 | goto error; | |||
536 | ||||
537 | for (i = 0; i < fold->n; ++i) { | |||
538 | fold->qp[i] = isl_qpolynomial_add(fold->qp[i], | |||
539 | isl_qpolynomial_copy(qp)); | |||
540 | if (!fold->qp[i]) | |||
541 | goto error; | |||
542 | } | |||
543 | ||||
544 | isl_qpolynomial_free(qp); | |||
545 | return fold; | |||
546 | error: | |||
547 | isl_qpolynomial_fold_free(fold); | |||
548 | isl_qpolynomial_free(qp); | |||
549 | return NULL((void*)0); | |||
550 | } | |||
551 | ||||
552 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_on_domain( | |||
553 | __isl_keep isl_setisl_map *dom, | |||
554 | __isl_take isl_qpolynomial_fold *fold1, | |||
555 | __isl_take isl_qpolynomial_fold *fold2) | |||
556 | { | |||
557 | int i; | |||
558 | isl_qpolynomial_fold *res = NULL((void*)0); | |||
559 | ||||
560 | if (!fold1 || !fold2) | |||
561 | goto error; | |||
562 | ||||
563 | if (isl_qpolynomial_fold_is_empty(fold1)) { | |||
564 | isl_qpolynomial_fold_free(fold1); | |||
565 | return fold2; | |||
566 | } | |||
567 | ||||
568 | if (isl_qpolynomial_fold_is_empty(fold2)) { | |||
569 | isl_qpolynomial_fold_free(fold2); | |||
570 | return fold1; | |||
571 | } | |||
572 | ||||
573 | if (fold1->n == 1 && fold2->n != 1) | |||
574 | return isl_qpolynomial_fold_add_on_domain(dom, fold2, fold1); | |||
575 | ||||
576 | if (fold2->n == 1) { | |||
577 | res = isl_qpolynomial_fold_add_qpolynomial(fold1, | |||
578 | isl_qpolynomial_copy(fold2->qp[0])); | |||
579 | isl_qpolynomial_fold_free(fold2); | |||
580 | return res; | |||
581 | } | |||
582 | ||||
583 | res = isl_qpolynomial_fold_add_qpolynomial( | |||
584 | isl_qpolynomial_fold_copy(fold1), | |||
585 | isl_qpolynomial_copy(fold2->qp[0])); | |||
586 | ||||
587 | for (i = 1; i < fold2->n; ++i) { | |||
588 | isl_qpolynomial_fold *res_i; | |||
589 | res_i = isl_qpolynomial_fold_add_qpolynomial( | |||
590 | isl_qpolynomial_fold_copy(fold1), | |||
591 | isl_qpolynomial_copy(fold2->qp[i])); | |||
592 | res = isl_qpolynomial_fold_fold_on_domain(dom, res, res_i); | |||
593 | } | |||
594 | ||||
595 | isl_qpolynomial_fold_free(fold1); | |||
596 | isl_qpolynomial_fold_free(fold2); | |||
597 | return res; | |||
598 | error: | |||
599 | isl_qpolynomial_fold_free(res); | |||
600 | isl_qpolynomial_fold_free(fold1); | |||
601 | isl_qpolynomial_fold_free(fold2); | |||
602 | return NULL((void*)0); | |||
603 | } | |||
604 | ||||
605 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute_equalities( | |||
606 | __isl_take isl_qpolynomial_fold *fold, __isl_take isl_basic_setisl_basic_map *eq) | |||
607 | { | |||
608 | int i; | |||
609 | ||||
610 | if (!fold || !eq) | |||
611 | goto error; | |||
612 | ||||
613 | fold = isl_qpolynomial_fold_cow(fold); | |||
614 | if (!fold) | |||
615 | return NULL((void*)0); | |||
616 | ||||
617 | for (i = 0; i < fold->n; ++i) { | |||
618 | fold->qp[i] = isl_qpolynomial_substitute_equalities(fold->qp[i], | |||
619 | isl_basic_set_copy(eq)); | |||
620 | if (!fold->qp[i]) | |||
621 | goto error; | |||
622 | } | |||
623 | ||||
624 | isl_basic_set_free(eq); | |||
625 | return fold; | |||
626 | error: | |||
627 | isl_basic_set_free(eq); | |||
628 | isl_qpolynomial_fold_free(fold); | |||
629 | return NULL((void*)0); | |||
630 | } | |||
631 | ||||
632 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist( | |||
633 | __isl_take isl_qpolynomial_fold *fold, __isl_take isl_setisl_map *context) | |||
634 | { | |||
635 | int i; | |||
636 | ||||
637 | if (!fold || !context) | |||
638 | goto error; | |||
639 | ||||
640 | fold = isl_qpolynomial_fold_cow(fold); | |||
641 | if (!fold) | |||
642 | return NULL((void*)0); | |||
643 | ||||
644 | for (i = 0; i < fold->n; ++i) { | |||
645 | fold->qp[i] = isl_qpolynomial_gist(fold->qp[i], | |||
646 | isl_set_copy(context)); | |||
647 | if (!fold->qp[i]) | |||
648 | goto error; | |||
649 | } | |||
650 | ||||
651 | isl_set_free(context); | |||
652 | return fold; | |||
653 | error: | |||
654 | isl_set_free(context); | |||
655 | isl_qpolynomial_fold_free(fold); | |||
656 | return NULL((void*)0); | |||
657 | } | |||
658 | ||||
659 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist_params( | |||
660 | __isl_take isl_qpolynomial_fold *fold, __isl_take isl_setisl_map *context) | |||
661 | { | |||
662 | isl_space *space = isl_qpolynomial_fold_get_domain_space(fold); | |||
663 | isl_setisl_map *dom_context = isl_set_universe(space); | |||
664 | dom_context = isl_set_intersect_params(dom_context, context); | |||
665 | return isl_qpolynomial_fold_gist(fold, dom_context); | |||
666 | } | |||
667 | ||||
668 | #define isl_qpolynomial_fold_involves_nanisl_qpolynomial_fold_is_nan isl_qpolynomial_fold_is_nan | |||
669 | ||||
670 | #define HAS_TYPE | |||
671 | ||||
672 | #undef PWisl_pw_qpolynomial_fold | |||
673 | #define PWisl_pw_qpolynomial_fold isl_pw_qpolynomial_fold | |||
674 | #undef ELisl_qpolynomial_fold | |||
675 | #define ELisl_qpolynomial_fold isl_qpolynomial_fold | |||
676 | #undef EL_IS_ZEROis_empty | |||
677 | #define EL_IS_ZEROis_empty is_empty | |||
678 | #undef ZEROzero | |||
679 | #define ZEROzero zero | |||
680 | #undef IS_ZEROis_zero | |||
681 | #define IS_ZEROis_zero is_zero | |||
682 | #undef FIELDfold | |||
683 | #define FIELDfold fold | |||
684 | #undef DEFAULT_IS_ZERO1 | |||
685 | #define DEFAULT_IS_ZERO1 1 | |||
686 | ||||
687 | #define NO_NEG | |||
688 | #define NO_SUB | |||
689 | #define NO_PULLBACK | |||
690 | ||||
691 | #include <isl_pw_templ.c> | |||
692 | #include <isl_pw_eval.c> | |||
693 | ||||
694 | #undef BASEpw_qpolynomial_fold | |||
695 | #define BASEpw_qpolynomial_fold pw_qpolynomial_fold | |||
696 | ||||
697 | #define NO_SUB | |||
698 | ||||
699 | #include <isl_union_single.c> | |||
700 | #include <isl_union_eval.c> | |||
701 | ||||
702 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type, | |||
703 | __isl_take isl_space *dim) | |||
704 | { | |||
705 | return qpolynomial_fold_alloc(type, dim, 0); | |||
706 | } | |||
707 | ||||
708 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc( | |||
709 | enum isl_fold type, __isl_take isl_qpolynomial *qp) | |||
710 | { | |||
711 | isl_qpolynomial_fold *fold; | |||
712 | ||||
713 | if (!qp) | |||
714 | return NULL((void*)0); | |||
715 | ||||
716 | fold = qpolynomial_fold_alloc(type, isl_space_copy(qp->dim), 1); | |||
717 | if (!fold) | |||
718 | goto error; | |||
719 | ||||
720 | fold->qp[0] = qp; | |||
721 | fold->n++; | |||
722 | ||||
723 | return fold; | |||
724 | error: | |||
725 | isl_qpolynomial_fold_free(fold); | |||
726 | isl_qpolynomial_free(qp); | |||
727 | return NULL((void*)0); | |||
728 | } | |||
729 | ||||
730 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy( | |||
731 | __isl_keep isl_qpolynomial_fold *fold) | |||
732 | { | |||
733 | if (!fold) | |||
734 | return NULL((void*)0); | |||
735 | ||||
736 | fold->ref++; | |||
737 | return fold; | |||
738 | } | |||
739 | ||||
740 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup( | |||
741 | __isl_keep isl_qpolynomial_fold *fold) | |||
742 | { | |||
743 | int i; | |||
744 | isl_qpolynomial_fold *dup; | |||
745 | ||||
746 | if (!fold) | |||
747 | return NULL((void*)0); | |||
748 | dup = qpolynomial_fold_alloc(fold->type, | |||
749 | isl_space_copy(fold->dim), fold->n); | |||
750 | if (!dup) | |||
751 | return NULL((void*)0); | |||
752 | ||||
753 | dup->n = fold->n; | |||
754 | for (i = 0; i < fold->n; ++i) { | |||
755 | dup->qp[i] = isl_qpolynomial_copy(fold->qp[i]); | |||
756 | if (!dup->qp[i]) | |||
757 | goto error; | |||
758 | } | |||
759 | ||||
760 | return dup; | |||
761 | error: | |||
762 | isl_qpolynomial_fold_free(dup); | |||
763 | return NULL((void*)0); | |||
764 | } | |||
765 | ||||
766 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow( | |||
767 | __isl_take isl_qpolynomial_fold *fold) | |||
768 | { | |||
769 | if (!fold) | |||
770 | return NULL((void*)0); | |||
771 | ||||
772 | if (fold->ref == 1) | |||
773 | return fold; | |||
774 | fold->ref--; | |||
775 | return isl_qpolynomial_fold_dup(fold); | |||
776 | } | |||
777 | ||||
778 | void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold *fold) | |||
779 | { | |||
780 | int i; | |||
781 | ||||
782 | if (!fold) | |||
783 | return; | |||
784 | if (--fold->ref > 0) | |||
785 | return; | |||
786 | ||||
787 | for (i = 0; i < fold->n; ++i) | |||
788 | isl_qpolynomial_free(fold->qp[i]); | |||
789 | isl_space_free(fold->dim); | |||
790 | free(fold); | |||
791 | } | |||
792 | ||||
793 | int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold) | |||
794 | { | |||
795 | if (!fold) | |||
796 | return -1; | |||
797 | ||||
798 | return fold->n == 0; | |||
799 | } | |||
800 | ||||
801 | /* Does "fold" represent max(NaN) or min(NaN)? | |||
802 | */ | |||
803 | isl_bool isl_qpolynomial_fold_is_nan(__isl_keep isl_qpolynomial_fold *fold) | |||
804 | { | |||
805 | if (!fold) | |||
806 | return isl_bool_error; | |||
807 | if (fold->n != 1) | |||
808 | return isl_bool_false; | |||
809 | return isl_qpolynomial_is_nan(fold->qp[0]); | |||
810 | } | |||
811 | ||||
812 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold( | |||
813 | __isl_take isl_qpolynomial_fold *fold1, | |||
814 | __isl_take isl_qpolynomial_fold *fold2) | |||
815 | { | |||
816 | int i; | |||
817 | struct isl_qpolynomial_fold *res = NULL((void*)0); | |||
818 | ||||
819 | if (!fold1 || !fold2) | |||
820 | goto error; | |||
821 | ||||
822 | isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error)do { if (fold1->type == fold2->type) break; do { isl_handle_error (fold1->dim->ctx, isl_error_unknown, "Assertion \"" "fold1->type == fold2->type" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 822); goto error; } while (0); } while (0); | |||
823 | isl_assert(fold1->dim->ctx, isl_space_is_equal(fold1->dim, fold2->dim),do { if (isl_space_is_equal(fold1->dim, fold2->dim)) break ; do { isl_handle_error(fold1->dim->ctx, isl_error_unknown , "Assertion \"" "isl_space_is_equal(fold1->dim, fold2->dim)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 824); goto error; } while (0); } while (0) | |||
824 | goto error)do { if (isl_space_is_equal(fold1->dim, fold2->dim)) break ; do { isl_handle_error(fold1->dim->ctx, isl_error_unknown , "Assertion \"" "isl_space_is_equal(fold1->dim, fold2->dim)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 824); goto error; } while (0); } while (0); | |||
825 | ||||
826 | if (isl_qpolynomial_fold_is_empty(fold1)) { | |||
827 | isl_qpolynomial_fold_free(fold1); | |||
828 | return fold2; | |||
829 | } | |||
830 | ||||
831 | if (isl_qpolynomial_fold_is_empty(fold2)) { | |||
832 | isl_qpolynomial_fold_free(fold2); | |||
833 | return fold1; | |||
834 | } | |||
835 | ||||
836 | res = qpolynomial_fold_alloc(fold1->type, isl_space_copy(fold1->dim), | |||
837 | fold1->n + fold2->n); | |||
838 | if (!res) | |||
839 | goto error; | |||
840 | ||||
841 | for (i = 0; i < fold1->n; ++i) { | |||
842 | res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]); | |||
843 | if (!res->qp[res->n]) | |||
844 | goto error; | |||
845 | res->n++; | |||
846 | } | |||
847 | ||||
848 | for (i = 0; i < fold2->n; ++i) { | |||
849 | res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]); | |||
850 | if (!res->qp[res->n]) | |||
851 | goto error; | |||
852 | res->n++; | |||
853 | } | |||
854 | ||||
855 | isl_qpolynomial_fold_free(fold1); | |||
856 | isl_qpolynomial_fold_free(fold2); | |||
857 | ||||
858 | return res; | |||
859 | error: | |||
860 | isl_qpolynomial_fold_free(res); | |||
861 | isl_qpolynomial_fold_free(fold1); | |||
862 | isl_qpolynomial_fold_free(fold2); | |||
863 | return NULL((void*)0); | |||
864 | } | |||
865 | ||||
866 | __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_fold( | |||
867 | __isl_take isl_pw_qpolynomial_fold *pw1, | |||
868 | __isl_take isl_pw_qpolynomial_fold *pw2) | |||
869 | { | |||
870 | int i, j, n; | |||
871 | struct isl_pw_qpolynomial_fold *res; | |||
872 | isl_setisl_map *set; | |||
873 | ||||
874 | if (!pw1 || !pw2) | |||
875 | goto error; | |||
876 | ||||
877 | isl_assert(pw1->dim->ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error)do { if (isl_space_is_equal(pw1->dim, pw2->dim)) break; do { isl_handle_error(pw1->dim->ctx, isl_error_unknown , "Assertion \"" "isl_space_is_equal(pw1->dim, pw2->dim)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 877); goto error; } while (0); } while (0); | |||
878 | ||||
879 | if (isl_pw_qpolynomial_fold_is_zero(pw1)) { | |||
880 | isl_pw_qpolynomial_fold_free(pw1); | |||
881 | return pw2; | |||
882 | } | |||
883 | ||||
884 | if (isl_pw_qpolynomial_fold_is_zero(pw2)) { | |||
885 | isl_pw_qpolynomial_fold_free(pw2); | |||
886 | return pw1; | |||
887 | } | |||
888 | ||||
889 | if (pw1->type != pw2->type) | |||
890 | isl_die(pw1->dim->ctx, isl_error_invalid,do { isl_handle_error(pw1->dim->ctx, isl_error_invalid, "fold types don't match", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 891); goto error; } while (0) | |||
891 | "fold types don't match", goto error)do { isl_handle_error(pw1->dim->ctx, isl_error_invalid, "fold types don't match", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 891); goto error; } while (0); | |||
892 | ||||
893 | n = (pw1->n + 1) * (pw2->n + 1); | |||
894 | res = isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pw1->dim), | |||
895 | pw1->type, n); | |||
896 | ||||
897 | for (i = 0; i < pw1->n; ++i) { | |||
898 | set = isl_set_copy(pw1->p[i].set); | |||
899 | for (j = 0; j < pw2->n; ++j) { | |||
900 | struct isl_setisl_map *common; | |||
901 | isl_qpolynomial_fold *sum; | |||
902 | set = isl_set_subtract(set, | |||
903 | isl_set_copy(pw2->p[j].set)); | |||
904 | common = isl_set_intersect(isl_set_copy(pw1->p[i].set), | |||
905 | isl_set_copy(pw2->p[j].set)); | |||
906 | if (isl_set_plain_is_empty(common)) { | |||
907 | isl_set_free(common); | |||
908 | continue; | |||
909 | } | |||
910 | ||||
911 | sum = isl_qpolynomial_fold_fold_on_domain(common, | |||
912 | isl_qpolynomial_fold_copy(pw1->p[i].fold), | |||
913 | isl_qpolynomial_fold_copy(pw2->p[j].fold)); | |||
914 | ||||
915 | res = isl_pw_qpolynomial_fold_add_piece(res, common, sum); | |||
916 | } | |||
917 | res = isl_pw_qpolynomial_fold_add_piece(res, set, | |||
918 | isl_qpolynomial_fold_copy(pw1->p[i].fold)); | |||
| ||||
919 | } | |||
920 | ||||
921 | for (j = 0; j < pw2->n; ++j) { | |||
922 | set = isl_set_copy(pw2->p[j].set); | |||
923 | for (i = 0; i < pw1->n; ++i) | |||
924 | set = isl_set_subtract(set, isl_set_copy(pw1->p[i].set)); | |||
925 | res = isl_pw_qpolynomial_fold_add_piece(res, set, | |||
926 | isl_qpolynomial_fold_copy(pw2->p[j].fold)); | |||
927 | } | |||
928 | ||||
929 | isl_pw_qpolynomial_fold_free(pw1); | |||
930 | isl_pw_qpolynomial_fold_free(pw2); | |||
931 | ||||
932 | return res; | |||
933 | error: | |||
934 | isl_pw_qpolynomial_fold_free(pw1); | |||
935 | isl_pw_qpolynomial_fold_free(pw2); | |||
936 | return NULL((void*)0); | |||
937 | } | |||
938 | ||||
939 | __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold( | |||
940 | __isl_take isl_union_pw_qpolynomial_fold *u, | |||
941 | __isl_take isl_pw_qpolynomial_fold *part) | |||
942 | { | |||
943 | struct isl_hash_table_entry *entry; | |||
944 | ||||
945 | u = isl_union_pw_qpolynomial_fold_cow(u); | |||
946 | ||||
947 | if (!part || !u) | |||
948 | goto error; | |||
949 | if (isl_space_check_equal_params(part->dim, u->space) < 0) | |||
950 | goto error; | |||
951 | ||||
952 | entry = isl_union_pw_qpolynomial_fold_find_part_entry(u, part->dim, 1); | |||
953 | if (!entry) | |||
954 | goto error; | |||
955 | ||||
956 | if (!entry->data) | |||
957 | entry->data = part; | |||
958 | else { | |||
959 | entry->data = isl_pw_qpolynomial_fold_fold(entry->data, | |||
960 | isl_pw_qpolynomial_fold_copy(part)); | |||
961 | if (!entry->data) | |||
962 | goto error; | |||
963 | isl_pw_qpolynomial_fold_free(part); | |||
964 | } | |||
965 | ||||
966 | return u; | |||
967 | error: | |||
968 | isl_pw_qpolynomial_fold_free(part); | |||
969 | isl_union_pw_qpolynomial_fold_free(u); | |||
970 | return NULL((void*)0); | |||
971 | } | |||
972 | ||||
973 | static isl_stat fold_part(__isl_take isl_pw_qpolynomial_fold *part, void *user) | |||
974 | { | |||
975 | isl_union_pw_qpolynomial_fold **u; | |||
976 | u = (isl_union_pw_qpolynomial_fold **)user; | |||
977 | ||||
978 | *u = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u, part); | |||
979 | ||||
980 | return isl_stat_ok; | |||
981 | } | |||
982 | ||||
983 | __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold( | |||
984 | __isl_take isl_union_pw_qpolynomial_fold *u1, | |||
985 | __isl_take isl_union_pw_qpolynomial_fold *u2) | |||
986 | { | |||
987 | u1 = isl_union_pw_qpolynomial_fold_cow(u1); | |||
988 | ||||
989 | if (!u1 || !u2) | |||
990 | goto error; | |||
991 | ||||
992 | if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2, | |||
993 | &fold_part, &u1) < 0) | |||
994 | goto error; | |||
995 | ||||
996 | isl_union_pw_qpolynomial_fold_free(u2); | |||
997 | ||||
998 | return u1; | |||
999 | error: | |||
1000 | isl_union_pw_qpolynomial_fold_free(u1); | |||
1001 | isl_union_pw_qpolynomial_fold_free(u2); | |||
1002 | return NULL((void*)0); | |||
1003 | } | |||
1004 | ||||
1005 | __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial( | |||
1006 | enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp) | |||
1007 | { | |||
1008 | int i; | |||
1009 | isl_pw_qpolynomial_fold *pwf; | |||
1010 | ||||
1011 | if (!pwqp) | |||
1012 | return NULL((void*)0); | |||
1013 | ||||
1014 | pwf = isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pwqp->dim), | |||
1015 | type, pwqp->n); | |||
1016 | ||||
1017 | for (i = 0; i < pwqp->n; ++i) | |||
1018 | pwf = isl_pw_qpolynomial_fold_add_piece(pwf, | |||
1019 | isl_set_copy(pwqp->p[i].set), | |||
1020 | isl_qpolynomial_fold_alloc(type, | |||
1021 | isl_qpolynomial_copy(pwqp->p[i].qp))); | |||
1022 | ||||
1023 | isl_pw_qpolynomial_free(pwqp); | |||
1024 | ||||
1025 | return pwf; | |||
1026 | } | |||
1027 | ||||
1028 | __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_add( | |||
1029 | __isl_take isl_pw_qpolynomial_fold *pwf1, | |||
1030 | __isl_take isl_pw_qpolynomial_fold *pwf2) | |||
1031 | { | |||
1032 | return isl_pw_qpolynomial_fold_union_add_(pwf1, pwf2); | |||
1033 | } | |||
1034 | ||||
1035 | /* Compare two quasi-polynomial reductions. | |||
1036 | * | |||
1037 | * Return -1 if "fold1" is "smaller" than "fold2", 1 if "fold1" is "greater" | |||
1038 | * than "fold2" and 0 if they are equal. | |||
1039 | */ | |||
1040 | int isl_qpolynomial_fold_plain_cmp(__isl_keep isl_qpolynomial_fold *fold1, | |||
1041 | __isl_keep isl_qpolynomial_fold *fold2) | |||
1042 | { | |||
1043 | int i; | |||
1044 | ||||
1045 | if (fold1 == fold2) | |||
1046 | return 0; | |||
1047 | if (!fold1) | |||
1048 | return -1; | |||
1049 | if (!fold2) | |||
1050 | return 1; | |||
1051 | ||||
1052 | if (fold1->n != fold2->n) | |||
1053 | return fold1->n - fold2->n; | |||
1054 | ||||
1055 | for (i = 0; i < fold1->n; ++i) { | |||
1056 | int cmp; | |||
1057 | ||||
1058 | cmp = isl_qpolynomial_plain_cmp(fold1->qp[i], fold2->qp[i]); | |||
1059 | if (cmp != 0) | |||
1060 | return cmp; | |||
1061 | } | |||
1062 | ||||
1063 | return 0; | |||
1064 | } | |||
1065 | ||||
1066 | int isl_qpolynomial_fold_plain_is_equal(__isl_keep isl_qpolynomial_fold *fold1, | |||
1067 | __isl_keep isl_qpolynomial_fold *fold2) | |||
1068 | { | |||
1069 | int i; | |||
1070 | ||||
1071 | if (!fold1 || !fold2) | |||
1072 | return -1; | |||
1073 | ||||
1074 | if (fold1->n != fold2->n) | |||
1075 | return 0; | |||
1076 | ||||
1077 | /* We probably want to sort the qps first... */ | |||
1078 | for (i = 0; i < fold1->n; ++i) { | |||
1079 | int eq = isl_qpolynomial_plain_is_equal(fold1->qp[i], fold2->qp[i]); | |||
1080 | if (eq < 0 || !eq) | |||
1081 | return eq; | |||
1082 | } | |||
1083 | ||||
1084 | return 1; | |||
1085 | } | |||
1086 | ||||
1087 | __isl_give isl_val *isl_qpolynomial_fold_eval( | |||
1088 | __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt) | |||
1089 | { | |||
1090 | isl_ctx *ctx; | |||
1091 | isl_val *v; | |||
1092 | ||||
1093 | if (!fold || !pnt) | |||
1094 | goto error; | |||
1095 | ctx = isl_point_get_ctx(pnt); | |||
1096 | isl_assert(pnt->dim->ctx, isl_space_is_equal(pnt->dim, fold->dim), goto error)do { if (isl_space_is_equal(pnt->dim, fold->dim)) break ; do { isl_handle_error(pnt->dim->ctx, isl_error_unknown , "Assertion \"" "isl_space_is_equal(pnt->dim, fold->dim)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 1096); goto error; } while (0); } while (0); | |||
1097 | isl_assert(pnt->dim->ctx,do { if (fold->type == isl_fold_max || fold->type == isl_fold_min ) break; do { isl_handle_error(pnt->dim->ctx, isl_error_unknown , "Assertion \"" "fold->type == isl_fold_max || fold->type == isl_fold_min" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 1099); goto error; } while (0); } while (0) | |||
1098 | fold->type == isl_fold_max || fold->type == isl_fold_min,do { if (fold->type == isl_fold_max || fold->type == isl_fold_min ) break; do { isl_handle_error(pnt->dim->ctx, isl_error_unknown , "Assertion \"" "fold->type == isl_fold_max || fold->type == isl_fold_min" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 1099); goto error; } while (0); } while (0) | |||
1099 | goto error)do { if (fold->type == isl_fold_max || fold->type == isl_fold_min ) break; do { isl_handle_error(pnt->dim->ctx, isl_error_unknown , "Assertion \"" "fold->type == isl_fold_max || fold->type == isl_fold_min" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 1099); goto error; } while (0); } while (0); | |||
1100 | ||||
1101 | if (fold->n == 0) | |||
1102 | v = isl_val_zero(ctx); | |||
1103 | else { | |||
1104 | int i; | |||
1105 | v = isl_qpolynomial_eval(isl_qpolynomial_copy(fold->qp[0]), | |||
1106 | isl_point_copy(pnt)); | |||
1107 | for (i = 1; i < fold->n; ++i) { | |||
1108 | isl_val *v_i; | |||
1109 | v_i = isl_qpolynomial_eval( | |||
1110 | isl_qpolynomial_copy(fold->qp[i]), | |||
1111 | isl_point_copy(pnt)); | |||
1112 | if (fold->type == isl_fold_max) | |||
1113 | v = isl_val_max(v, v_i); | |||
1114 | else | |||
1115 | v = isl_val_min(v, v_i); | |||
1116 | } | |||
1117 | } | |||
1118 | isl_qpolynomial_fold_free(fold); | |||
1119 | isl_point_free(pnt); | |||
1120 | ||||
1121 | return v; | |||
1122 | error: | |||
1123 | isl_qpolynomial_fold_free(fold); | |||
1124 | isl_point_free(pnt); | |||
1125 | return NULL((void*)0); | |||
1126 | } | |||
1127 | ||||
1128 | size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf) | |||
1129 | { | |||
1130 | int i; | |||
1131 | size_t n = 0; | |||
1132 | ||||
1133 | for (i = 0; i < pwf->n; ++i) | |||
1134 | n += pwf->p[i].fold->n; | |||
1135 | ||||
1136 | return n; | |||
1137 | } | |||
1138 | ||||
1139 | __isl_give isl_val *isl_qpolynomial_fold_opt_on_domain( | |||
1140 | __isl_take isl_qpolynomial_fold *fold, __isl_take isl_setisl_map *set, int max) | |||
1141 | { | |||
1142 | int i; | |||
1143 | isl_val *opt; | |||
1144 | ||||
1145 | if (!set || !fold) | |||
1146 | goto error; | |||
1147 | ||||
1148 | if (fold->n == 0) { | |||
1149 | opt = isl_val_zero(isl_set_get_ctx(set)); | |||
1150 | isl_set_free(set); | |||
1151 | isl_qpolynomial_fold_free(fold); | |||
1152 | return opt; | |||
1153 | } | |||
1154 | ||||
1155 | opt = isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold->qp[0]), | |||
1156 | isl_set_copy(set), max); | |||
1157 | for (i = 1; i < fold->n; ++i) { | |||
1158 | isl_val *opt_i; | |||
1159 | opt_i = isl_qpolynomial_opt_on_domain( | |||
1160 | isl_qpolynomial_copy(fold->qp[i]), | |||
1161 | isl_set_copy(set), max); | |||
1162 | if (max) | |||
1163 | opt = isl_val_max(opt, opt_i); | |||
1164 | else | |||
1165 | opt = isl_val_min(opt, opt_i); | |||
1166 | } | |||
1167 | ||||
1168 | isl_set_free(set); | |||
1169 | isl_qpolynomial_fold_free(fold); | |||
1170 | ||||
1171 | return opt; | |||
1172 | error: | |||
1173 | isl_set_free(set); | |||
1174 | isl_qpolynomial_fold_free(fold); | |||
1175 | return NULL((void*)0); | |||
1176 | } | |||
1177 | ||||
1178 | /* Check whether for each quasi-polynomial in "fold2" there is | |||
1179 | * a quasi-polynomial in "fold1" that dominates it on "set". | |||
1180 | */ | |||
1181 | static int qpolynomial_fold_covers_on_domain(__isl_keep isl_setisl_map *set, | |||
1182 | __isl_keep isl_qpolynomial_fold *fold1, | |||
1183 | __isl_keep isl_qpolynomial_fold *fold2) | |||
1184 | { | |||
1185 | int i, j; | |||
1186 | int covers; | |||
1187 | ||||
1188 | if (!set || !fold1 || !fold2) | |||
1189 | return -1; | |||
1190 | ||||
1191 | covers = fold1->type == isl_fold_max ? 1 : -1; | |||
1192 | ||||
1193 | for (i = 0; i < fold2->n; ++i) { | |||
1194 | for (j = 0; j < fold1->n; ++j) { | |||
1195 | isl_qpolynomial *d; | |||
1196 | int sgn; | |||
1197 | ||||
1198 | d = isl_qpolynomial_sub( | |||
1199 | isl_qpolynomial_copy(fold1->qp[j]), | |||
1200 | isl_qpolynomial_copy(fold2->qp[i])); | |||
1201 | sgn = isl_qpolynomial_sign(set, d); | |||
1202 | isl_qpolynomial_free(d); | |||
1203 | if (sgn == covers) | |||
1204 | break; | |||
1205 | } | |||
1206 | if (j >= fold1->n) | |||
1207 | return 0; | |||
1208 | } | |||
1209 | ||||
1210 | return 1; | |||
1211 | } | |||
1212 | ||||
1213 | /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains | |||
1214 | * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates | |||
1215 | * that of pwf2. | |||
1216 | */ | |||
1217 | int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold *pwf1, | |||
1218 | __isl_keep isl_pw_qpolynomial_fold *pwf2) | |||
1219 | { | |||
1220 | int i, j; | |||
1221 | isl_setisl_map *dom1, *dom2; | |||
1222 | int is_subset; | |||
1223 | ||||
1224 | if (!pwf1 || !pwf2) | |||
1225 | return -1; | |||
1226 | ||||
1227 | if (pwf2->n == 0) | |||
1228 | return 1; | |||
1229 | if (pwf1->n == 0) | |||
1230 | return 0; | |||
1231 | ||||
1232 | dom1 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1)); | |||
1233 | dom2 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2)); | |||
1234 | is_subset = isl_set_is_subset(dom2, dom1); | |||
1235 | isl_set_free(dom1); | |||
1236 | isl_set_free(dom2); | |||
1237 | ||||
1238 | if (is_subset < 0 || !is_subset) | |||
1239 | return is_subset; | |||
1240 | ||||
1241 | for (i = 0; i < pwf2->n; ++i) { | |||
1242 | for (j = 0; j < pwf1->n; ++j) { | |||
1243 | int is_empty; | |||
1244 | isl_setisl_map *common; | |||
1245 | int covers; | |||
1246 | ||||
1247 | common = isl_set_intersect(isl_set_copy(pwf1->p[j].set), | |||
1248 | isl_set_copy(pwf2->p[i].set)); | |||
1249 | is_empty = isl_set_is_empty(common); | |||
1250 | if (is_empty < 0 || is_empty) { | |||
1251 | isl_set_free(common); | |||
1252 | if (is_empty < 0) | |||
1253 | return -1; | |||
1254 | continue; | |||
1255 | } | |||
1256 | covers = qpolynomial_fold_covers_on_domain(common, | |||
1257 | pwf1->p[j].fold, pwf2->p[i].fold); | |||
1258 | isl_set_free(common); | |||
1259 | if (covers < 0 || !covers) | |||
1260 | return covers; | |||
1261 | } | |||
1262 | } | |||
1263 | ||||
1264 | return 1; | |||
1265 | } | |||
1266 | ||||
1267 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph_domain( | |||
1268 | __isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph) | |||
1269 | { | |||
1270 | int i; | |||
1271 | isl_ctx *ctx; | |||
1272 | ||||
1273 | if (!fold || !morph) | |||
1274 | goto error; | |||
1275 | ||||
1276 | ctx = fold->dim->ctx; | |||
1277 | isl_assert(ctx, isl_space_is_equal(fold->dim, morph->dom->dim), goto error)do { if (isl_space_is_equal(fold->dim, morph->dom->dim )) break; do { isl_handle_error(ctx, isl_error_unknown, "Assertion \"" "isl_space_is_equal(fold->dim, morph->dom->dim)" "\" failed" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 1277); goto error; } while (0); } while (0); | |||
1278 | ||||
1279 | fold = isl_qpolynomial_fold_cow(fold); | |||
1280 | if (!fold) | |||
1281 | goto error; | |||
1282 | ||||
1283 | isl_space_free(fold->dim); | |||
1284 | fold->dim = isl_space_copy(morph->ran->dim); | |||
1285 | if (!fold->dim) | |||
1286 | goto error; | |||
1287 | ||||
1288 | for (i = 0; i < fold->n; ++i) { | |||
1289 | fold->qp[i] = isl_qpolynomial_morph_domain(fold->qp[i], | |||
1290 | isl_morph_copy(morph)); | |||
1291 | if (!fold->qp[i]) | |||
1292 | goto error; | |||
1293 | } | |||
1294 | ||||
1295 | isl_morph_free(morph); | |||
1296 | ||||
1297 | return fold; | |||
1298 | error: | |||
1299 | isl_qpolynomial_fold_free(fold); | |||
1300 | isl_morph_free(morph); | |||
1301 | return NULL((void*)0); | |||
1302 | } | |||
1303 | ||||
1304 | enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold) | |||
1305 | { | |||
1306 | if (!fold) | |||
1307 | return isl_fold_list; | |||
1308 | return fold->type; | |||
1309 | } | |||
1310 | ||||
1311 | enum isl_fold isl_union_pw_qpolynomial_fold_get_type( | |||
1312 | __isl_keep isl_union_pw_qpolynomial_fold *upwf) | |||
1313 | { | |||
1314 | if (!upwf) | |||
1315 | return isl_fold_list; | |||
1316 | return upwf->type; | |||
1317 | } | |||
1318 | ||||
1319 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift( | |||
1320 | __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *dim) | |||
1321 | { | |||
1322 | int i; | |||
1323 | ||||
1324 | if (!fold || !dim) | |||
1325 | goto error; | |||
1326 | ||||
1327 | if (isl_space_is_equal(fold->dim, dim)) { | |||
1328 | isl_space_free(dim); | |||
1329 | return fold; | |||
1330 | } | |||
1331 | ||||
1332 | fold = isl_qpolynomial_fold_cow(fold); | |||
1333 | if (!fold) | |||
1334 | goto error; | |||
1335 | ||||
1336 | isl_space_free(fold->dim); | |||
1337 | fold->dim = isl_space_copy(dim); | |||
1338 | if (!fold->dim) | |||
1339 | goto error; | |||
1340 | ||||
1341 | for (i = 0; i < fold->n; ++i) { | |||
1342 | fold->qp[i] = isl_qpolynomial_lift(fold->qp[i], | |||
1343 | isl_space_copy(dim)); | |||
1344 | if (!fold->qp[i]) | |||
1345 | goto error; | |||
1346 | } | |||
1347 | ||||
1348 | isl_space_free(dim); | |||
1349 | ||||
1350 | return fold; | |||
1351 | error: | |||
1352 | isl_qpolynomial_fold_free(fold); | |||
1353 | isl_space_free(dim); | |||
1354 | return NULL((void*)0); | |||
1355 | } | |||
1356 | ||||
1357 | isl_stat isl_qpolynomial_fold_foreach_qpolynomial( | |||
1358 | __isl_keep isl_qpolynomial_fold *fold, | |||
1359 | isl_stat (*fn)(__isl_take isl_qpolynomial *qp, void *user), void *user) | |||
1360 | { | |||
1361 | int i; | |||
1362 | ||||
1363 | if (!fold) | |||
1364 | return isl_stat_error; | |||
1365 | ||||
1366 | for (i = 0; i < fold->n; ++i) | |||
1367 | if (fn(isl_qpolynomial_copy(fold->qp[i]), user) < 0) | |||
1368 | return isl_stat_error; | |||
1369 | ||||
1370 | return isl_stat_ok; | |||
1371 | } | |||
1372 | ||||
1373 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims( | |||
1374 | __isl_take isl_qpolynomial_fold *fold, | |||
1375 | enum isl_dim_type dst_type, unsigned dst_pos, | |||
1376 | enum isl_dim_type src_type, unsigned src_pos, unsigned n) | |||
1377 | { | |||
1378 | int i; | |||
1379 | enum isl_dim_type set_src_type, set_dst_type; | |||
1380 | ||||
1381 | if (n == 0) | |||
1382 | return fold; | |||
1383 | ||||
1384 | fold = isl_qpolynomial_fold_cow(fold); | |||
1385 | if (!fold) | |||
1386 | return NULL((void*)0); | |||
1387 | ||||
1388 | set_src_type = domain_type(src_type); | |||
1389 | set_dst_type = domain_type(dst_type); | |||
1390 | ||||
1391 | fold->dim = isl_space_move_dims(fold->dim, set_dst_type, dst_pos, | |||
1392 | set_src_type, src_pos, n); | |||
1393 | if (!fold->dim) | |||
1394 | goto error; | |||
1395 | ||||
1396 | for (i = 0; i < fold->n; ++i) { | |||
1397 | fold->qp[i] = isl_qpolynomial_move_dims(fold->qp[i], | |||
1398 | dst_type, dst_pos, src_type, src_pos, n); | |||
1399 | if (!fold->qp[i]) | |||
1400 | goto error; | |||
1401 | } | |||
1402 | ||||
1403 | return fold; | |||
1404 | error: | |||
1405 | isl_qpolynomial_fold_free(fold); | |||
1406 | return NULL((void*)0); | |||
1407 | } | |||
1408 | ||||
1409 | /* For each 0 <= i < "n", replace variable "first" + i of type "type" | |||
1410 | * in fold->qp[k] by subs[i]. | |||
1411 | */ | |||
1412 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute( | |||
1413 | __isl_take isl_qpolynomial_fold *fold, | |||
1414 | enum isl_dim_type type, unsigned first, unsigned n, | |||
1415 | __isl_keep isl_qpolynomial **subs) | |||
1416 | { | |||
1417 | int i; | |||
1418 | ||||
1419 | if (n == 0) | |||
1420 | return fold; | |||
1421 | ||||
1422 | fold = isl_qpolynomial_fold_cow(fold); | |||
1423 | if (!fold) | |||
1424 | return NULL((void*)0); | |||
1425 | ||||
1426 | for (i = 0; i < fold->n; ++i) { | |||
1427 | fold->qp[i] = isl_qpolynomial_substitute(fold->qp[i], | |||
1428 | type, first, n, subs); | |||
1429 | if (!fold->qp[i]) | |||
1430 | goto error; | |||
1431 | } | |||
1432 | ||||
1433 | return fold; | |||
1434 | error: | |||
1435 | isl_qpolynomial_fold_free(fold); | |||
1436 | return NULL((void*)0); | |||
1437 | } | |||
1438 | ||||
1439 | static isl_stat add_pwqp(__isl_take isl_pw_qpolynomial *pwqp, void *user) | |||
1440 | { | |||
1441 | isl_pw_qpolynomial_fold *pwf; | |||
1442 | isl_union_pw_qpolynomial_fold **upwf; | |||
1443 | struct isl_hash_table_entry *entry; | |||
1444 | ||||
1445 | upwf = (isl_union_pw_qpolynomial_fold **)user; | |||
1446 | ||||
1447 | entry = isl_union_pw_qpolynomial_fold_find_part_entry(*upwf, | |||
1448 | pwqp->dim, 1); | |||
1449 | if (!entry) | |||
1450 | goto error; | |||
1451 | ||||
1452 | pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf)->type, pwqp); | |||
1453 | if (!entry->data) | |||
1454 | entry->data = pwf; | |||
1455 | else { | |||
1456 | entry->data = isl_pw_qpolynomial_fold_add(entry->data, pwf); | |||
1457 | if (!entry->data) | |||
1458 | return isl_stat_error; | |||
1459 | if (isl_pw_qpolynomial_fold_is_zero(entry->data)) | |||
1460 | *upwf = isl_union_pw_qpolynomial_fold_remove_part_entry( | |||
1461 | *upwf, entry); | |||
1462 | } | |||
1463 | ||||
1464 | return isl_stat_ok; | |||
1465 | error: | |||
1466 | isl_pw_qpolynomial_free(pwqp); | |||
1467 | return isl_stat_error; | |||
1468 | } | |||
1469 | ||||
1470 | __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial( | |||
1471 | __isl_take isl_union_pw_qpolynomial_fold *upwf, | |||
1472 | __isl_take isl_union_pw_qpolynomial *upwqp) | |||
1473 | { | |||
1474 | upwf = isl_union_pw_qpolynomial_fold_align_params(upwf, | |||
1475 | isl_union_pw_qpolynomial_get_space(upwqp)); | |||
1476 | upwqp = isl_union_pw_qpolynomial_align_params(upwqp, | |||
1477 | isl_union_pw_qpolynomial_fold_get_space(upwf)); | |||
1478 | ||||
1479 | upwf = isl_union_pw_qpolynomial_fold_cow(upwf); | |||
1480 | if (!upwf || !upwqp) | |||
1481 | goto error; | |||
1482 | ||||
1483 | if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp, &add_pwqp, | |||
1484 | &upwf) < 0) | |||
1485 | goto error; | |||
1486 | ||||
1487 | isl_union_pw_qpolynomial_free(upwqp); | |||
1488 | ||||
1489 | return upwf; | |||
1490 | error: | |||
1491 | isl_union_pw_qpolynomial_fold_free(upwf); | |||
1492 | isl_union_pw_qpolynomial_free(upwqp); | |||
1493 | return NULL((void*)0); | |||
1494 | } | |||
1495 | ||||
1496 | static isl_bool join_compatible(__isl_keep isl_space *space1, | |||
1497 | __isl_keep isl_space *space2) | |||
1498 | { | |||
1499 | isl_bool m; | |||
1500 | m = isl_space_has_equal_params(space1, space2); | |||
1501 | if (m < 0 || !m) | |||
1502 | return m; | |||
1503 | return isl_space_tuple_is_equal(space1, isl_dim_out, | |||
1504 | space2, isl_dim_in); | |||
1505 | } | |||
1506 | ||||
1507 | /* Compute the intersection of the range of the map and the domain | |||
1508 | * of the piecewise quasipolynomial reduction and then compute a bound | |||
1509 | * on the associated quasipolynomial reduction over all elements | |||
1510 | * in this intersection. | |||
1511 | * | |||
1512 | * We first introduce some unconstrained dimensions in the | |||
1513 | * piecewise quasipolynomial, intersect the resulting domain | |||
1514 | * with the wrapped map and the compute the sum. | |||
1515 | */ | |||
1516 | __isl_give isl_pw_qpolynomial_fold *isl_map_apply_pw_qpolynomial_fold( | |||
1517 | __isl_take isl_map *map, __isl_take isl_pw_qpolynomial_fold *pwf, | |||
1518 | int *tight) | |||
1519 | { | |||
1520 | isl_ctx *ctx; | |||
1521 | isl_setisl_map *dom; | |||
1522 | isl_space *map_dim; | |||
1523 | isl_space *pwf_dim; | |||
1524 | unsigned n_in; | |||
1525 | isl_bool ok; | |||
1526 | ||||
1527 | ctx = isl_map_get_ctx(map); | |||
1528 | if (!ctx) | |||
1529 | goto error; | |||
1530 | ||||
1531 | map_dim = isl_map_get_space(map); | |||
1532 | pwf_dim = isl_pw_qpolynomial_fold_get_space(pwf); | |||
1533 | ok = join_compatible(map_dim, pwf_dim); | |||
1534 | isl_space_free(map_dim); | |||
1535 | isl_space_free(pwf_dim); | |||
1536 | if (ok < 0) | |||
1537 | goto error; | |||
1538 | if (!ok) | |||
1539 | isl_die(ctx, isl_error_invalid, "incompatible dimensions",do { isl_handle_error(ctx, isl_error_invalid, "incompatible dimensions" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 1540); goto error; } while (0) | |||
1540 | goto error)do { isl_handle_error(ctx, isl_error_invalid, "incompatible dimensions" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 1540); goto error; } while (0); | |||
1541 | ||||
1542 | n_in = isl_map_dim(map, isl_dim_in); | |||
1543 | pwf = isl_pw_qpolynomial_fold_insert_dims(pwf, isl_dim_in, 0, n_in); | |||
1544 | ||||
1545 | dom = isl_map_wrap(map); | |||
1546 | pwf = isl_pw_qpolynomial_fold_reset_domain_space(pwf, | |||
1547 | isl_set_get_space(dom)); | |||
1548 | ||||
1549 | pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, dom); | |||
1550 | pwf = isl_pw_qpolynomial_fold_bound(pwf, tight); | |||
1551 | ||||
1552 | return pwf; | |||
1553 | error: | |||
1554 | isl_map_free(map); | |||
1555 | isl_pw_qpolynomial_fold_free(pwf); | |||
1556 | return NULL((void*)0); | |||
1557 | } | |||
1558 | ||||
1559 | __isl_give isl_pw_qpolynomial_fold *isl_set_apply_pw_qpolynomial_fold( | |||
1560 | __isl_take isl_setisl_map *set, __isl_take isl_pw_qpolynomial_fold *pwf, | |||
1561 | int *tight) | |||
1562 | { | |||
1563 | return isl_map_apply_pw_qpolynomial_fold(set, pwf, tight); | |||
1564 | } | |||
1565 | ||||
1566 | struct isl_apply_fold_data { | |||
1567 | isl_union_pw_qpolynomial_fold *upwf; | |||
1568 | isl_union_pw_qpolynomial_fold *res; | |||
1569 | isl_map *map; | |||
1570 | int tight; | |||
1571 | }; | |||
1572 | ||||
1573 | static isl_stat pw_qpolynomial_fold_apply( | |||
1574 | __isl_take isl_pw_qpolynomial_fold *pwf, void *user) | |||
1575 | { | |||
1576 | isl_space *map_dim; | |||
1577 | isl_space *pwf_dim; | |||
1578 | struct isl_apply_fold_data *data = user; | |||
1579 | isl_bool ok; | |||
1580 | ||||
1581 | map_dim = isl_map_get_space(data->map); | |||
1582 | pwf_dim = isl_pw_qpolynomial_fold_get_space(pwf); | |||
1583 | ok = join_compatible(map_dim, pwf_dim); | |||
1584 | isl_space_free(map_dim); | |||
1585 | isl_space_free(pwf_dim); | |||
1586 | ||||
1587 | if (ok < 0) | |||
| ||||
1588 | return isl_stat_error; | |||
1589 | if (ok) { | |||
1590 | pwf = isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data->map), | |||
1591 | pwf, data->tight ? &data->tight : NULL((void*)0)); | |||
1592 | data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold( | |||
1593 | data->res, pwf); | |||
1594 | } else | |||
1595 | isl_pw_qpolynomial_fold_free(pwf); | |||
1596 | ||||
1597 | return isl_stat_ok; | |||
1598 | } | |||
1599 | ||||
1600 | static isl_stat map_apply(__isl_take isl_map *map, void *user) | |||
1601 | { | |||
1602 | struct isl_apply_fold_data *data = user; | |||
1603 | isl_stat r; | |||
1604 | ||||
1605 | data->map = map; | |||
1606 | r = isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold( | |||
1607 | data->upwf, &pw_qpolynomial_fold_apply, data); | |||
1608 | ||||
1609 | isl_map_free(map); | |||
1610 | return r; | |||
1611 | } | |||
1612 | ||||
1613 | __isl_give isl_union_pw_qpolynomial_fold *isl_union_map_apply_union_pw_qpolynomial_fold( | |||
1614 | __isl_take isl_union_map *umap, | |||
1615 | __isl_take isl_union_pw_qpolynomial_fold *upwf, int *tight) | |||
1616 | { | |||
1617 | isl_space *dim; | |||
1618 | enum isl_fold type; | |||
1619 | struct isl_apply_fold_data data; | |||
1620 | ||||
1621 | upwf = isl_union_pw_qpolynomial_fold_align_params(upwf, | |||
1622 | isl_union_map_get_space(umap)); | |||
1623 | umap = isl_union_map_align_params(umap, | |||
1624 | isl_union_pw_qpolynomial_fold_get_space(upwf)); | |||
1625 | ||||
1626 | data.upwf = upwf; | |||
1627 | data.tight = tight ? 1 : 0; | |||
1628 | dim = isl_union_pw_qpolynomial_fold_get_space(upwf); | |||
1629 | type = isl_union_pw_qpolynomial_fold_get_type(upwf); | |||
1630 | data.res = isl_union_pw_qpolynomial_fold_zero(dim, type); | |||
1631 | if (isl_union_map_foreach_map(umap, &map_apply, &data) < 0) | |||
1632 | goto error; | |||
1633 | ||||
1634 | isl_union_map_free(umap); | |||
1635 | isl_union_pw_qpolynomial_fold_free(upwf); | |||
1636 | ||||
1637 | if (tight) | |||
1638 | *tight = data.tight; | |||
1639 | ||||
1640 | return data.res; | |||
1641 | error: | |||
1642 | isl_union_map_free(umap); | |||
1643 | isl_union_pw_qpolynomial_fold_free(upwf); | |||
1644 | isl_union_pw_qpolynomial_fold_free(data.res); | |||
1645 | return NULL((void*)0); | |||
1646 | } | |||
1647 | ||||
1648 | __isl_give isl_union_pw_qpolynomial_fold *isl_union_set_apply_union_pw_qpolynomial_fold( | |||
1649 | __isl_take isl_union_setisl_union_map *uset, | |||
1650 | __isl_take isl_union_pw_qpolynomial_fold *upwf, int *tight) | |||
1651 | { | |||
1652 | return isl_union_map_apply_union_pw_qpolynomial_fold(uset, upwf, tight); | |||
1653 | } | |||
1654 | ||||
1655 | /* Reorder the dimension of "fold" according to the given reordering. | |||
1656 | */ | |||
1657 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_realign_domain( | |||
1658 | __isl_take isl_qpolynomial_fold *fold, __isl_take isl_reordering *r) | |||
1659 | { | |||
1660 | int i; | |||
1661 | isl_space *space; | |||
1662 | ||||
1663 | fold = isl_qpolynomial_fold_cow(fold); | |||
1664 | if (!fold || !r) | |||
1665 | goto error; | |||
1666 | ||||
1667 | for (i = 0; i < fold->n; ++i) { | |||
1668 | fold->qp[i] = isl_qpolynomial_realign_domain(fold->qp[i], | |||
1669 | isl_reordering_copy(r)); | |||
1670 | if (!fold->qp[i]) | |||
1671 | goto error; | |||
1672 | } | |||
1673 | ||||
1674 | space = isl_reordering_get_space(r); | |||
1675 | fold = isl_qpolynomial_fold_reset_domain_space(fold, space); | |||
1676 | ||||
1677 | isl_reordering_free(r); | |||
1678 | ||||
1679 | return fold; | |||
1680 | error: | |||
1681 | isl_qpolynomial_fold_free(fold); | |||
1682 | isl_reordering_free(r); | |||
1683 | return NULL((void*)0); | |||
1684 | } | |||
1685 | ||||
1686 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_mul_isl_int( | |||
1687 | __isl_take isl_qpolynomial_fold *fold, isl_int v) | |||
1688 | { | |||
1689 | int i; | |||
1690 | ||||
1691 | if (isl_int_is_one(v)(isl_sioimath_cmp_si(*(v), 1) == 0)) | |||
1692 | return fold; | |||
1693 | if (fold && isl_int_is_zero(v)(isl_sioimath_sgn(*(v)) == 0)) { | |||
1694 | isl_qpolynomial_fold *zero; | |||
1695 | isl_space *dim = isl_space_copy(fold->dim); | |||
1696 | zero = isl_qpolynomial_fold_empty(fold->type, dim); | |||
1697 | isl_qpolynomial_fold_free(fold); | |||
1698 | return zero; | |||
1699 | } | |||
1700 | ||||
1701 | fold = isl_qpolynomial_fold_cow(fold); | |||
1702 | if (!fold) | |||
1703 | return NULL((void*)0); | |||
1704 | ||||
1705 | if (isl_int_is_neg(v)(isl_sioimath_sgn(*(v)) < 0)) | |||
1706 | fold->type = isl_fold_type_negate(fold->type); | |||
1707 | for (i = 0; i < fold->n; ++i) { | |||
1708 | fold->qp[i] = isl_qpolynomial_mul_isl_int(fold->qp[i], v); | |||
1709 | if (!fold->qp[i]) | |||
1710 | goto error; | |||
1711 | } | |||
1712 | ||||
1713 | return fold; | |||
1714 | error: | |||
1715 | isl_qpolynomial_fold_free(fold); | |||
1716 | return NULL((void*)0); | |||
1717 | } | |||
1718 | ||||
1719 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale( | |||
1720 | __isl_take isl_qpolynomial_fold *fold, isl_int v) | |||
1721 | { | |||
1722 | return isl_qpolynomial_fold_mul_isl_int(fold, v); | |||
1723 | } | |||
1724 | ||||
1725 | /* Multiply "fold" by "v". | |||
1726 | */ | |||
1727 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale_val( | |||
1728 | __isl_take isl_qpolynomial_fold *fold, __isl_take isl_val *v) | |||
1729 | { | |||
1730 | int i; | |||
1731 | ||||
1732 | if (!fold || !v) | |||
1733 | goto error; | |||
1734 | ||||
1735 | if (isl_val_is_one(v)) { | |||
1736 | isl_val_free(v); | |||
1737 | return fold; | |||
1738 | } | |||
1739 | if (isl_val_is_zero(v)) { | |||
1740 | isl_qpolynomial_fold *zero; | |||
1741 | isl_space *space = isl_qpolynomial_fold_get_domain_space(fold); | |||
1742 | zero = isl_qpolynomial_fold_empty(fold->type, space); | |||
1743 | isl_qpolynomial_fold_free(fold); | |||
1744 | isl_val_free(v); | |||
1745 | return zero; | |||
1746 | } | |||
1747 | if (!isl_val_is_rat(v)) | |||
1748 | isl_die(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid,do { isl_handle_error(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid , "expecting rational factor", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 1749); goto error; } while (0) | |||
1749 | "expecting rational factor", goto error)do { isl_handle_error(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid , "expecting rational factor", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 1749); goto error; } while (0); | |||
1750 | ||||
1751 | fold = isl_qpolynomial_fold_cow(fold); | |||
1752 | if (!fold) | |||
1753 | goto error; | |||
1754 | ||||
1755 | if (isl_val_is_neg(v)) | |||
1756 | fold->type = isl_fold_type_negate(fold->type); | |||
1757 | for (i = 0; i < fold->n; ++i) { | |||
1758 | fold->qp[i] = isl_qpolynomial_scale_val(fold->qp[i], | |||
1759 | isl_val_copy(v)); | |||
1760 | if (!fold->qp[i]) | |||
1761 | goto error; | |||
1762 | } | |||
1763 | ||||
1764 | isl_val_free(v); | |||
1765 | return fold; | |||
1766 | error: | |||
1767 | isl_val_free(v); | |||
1768 | isl_qpolynomial_fold_free(fold); | |||
1769 | return NULL((void*)0); | |||
1770 | } | |||
1771 | ||||
1772 | /* Divide "fold" by "v". | |||
1773 | */ | |||
1774 | __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale_down_val( | |||
1775 | __isl_take isl_qpolynomial_fold *fold, __isl_take isl_val *v) | |||
1776 | { | |||
1777 | if (!fold || !v) | |||
1778 | goto error; | |||
1779 | ||||
1780 | if (isl_val_is_one(v)) { | |||
1781 | isl_val_free(v); | |||
1782 | return fold; | |||
1783 | } | |||
1784 | if (!isl_val_is_rat(v)) | |||
1785 | isl_die(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid,do { isl_handle_error(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid , "expecting rational factor", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 1786); goto error; } while (0) | |||
1786 | "expecting rational factor", goto error)do { isl_handle_error(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid , "expecting rational factor", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 1786); goto error; } while (0); | |||
1787 | if (isl_val_is_zero(v)) | |||
1788 | isl_die(isl_val_get_ctx(v), isl_error_invalid,do { isl_handle_error(isl_val_get_ctx(v), isl_error_invalid, "cannot scale down by zero" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 1789); goto error; } while (0) | |||
1789 | "cannot scale down by zero", goto error)do { isl_handle_error(isl_val_get_ctx(v), isl_error_invalid, "cannot scale down by zero" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_fold.c" , 1789); goto error; } while (0); | |||
1790 | ||||
1791 | return isl_qpolynomial_fold_scale_val(fold, isl_val_inv(v)); | |||
1792 | error: | |||
1793 | isl_val_free(v); | |||
1794 | isl_qpolynomial_fold_free(fold); | |||
1795 | return NULL((void*)0); | |||
1796 | } |