File: | tools/polly/lib/External/isl/isl_polynomial.c |
Warning: | line 3042, column 5 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 <stdlib.h> | |||
12 | #include <isl_ctx_private.h> | |||
13 | #include <isl_map_private.h> | |||
14 | #include <isl_factorization.h> | |||
15 | #include <isl_lp_private.h> | |||
16 | #include <isl_seq.h> | |||
17 | #include <isl_union_map_private.h> | |||
18 | #include <isl_constraint_private.h> | |||
19 | #include <isl_polynomial_private.h> | |||
20 | #include <isl_point_private.h> | |||
21 | #include <isl_space_private.h> | |||
22 | #include <isl_mat_private.h> | |||
23 | #include <isl_vec_private.h> | |||
24 | #include <isl_range.h> | |||
25 | #include <isl_local.h> | |||
26 | #include <isl_local_space_private.h> | |||
27 | #include <isl_aff_private.h> | |||
28 | #include <isl_val_private.h> | |||
29 | #include <isl_config.h> | |||
30 | ||||
31 | #undef BASEpw_qpolynomial | |||
32 | #define BASEpw_qpolynomial pw_qpolynomial | |||
33 | ||||
34 | #include <isl_list_templ.c> | |||
35 | ||||
36 | static unsigned pos(__isl_keep isl_space *dim, enum isl_dim_type type) | |||
37 | { | |||
38 | switch (type) { | |||
39 | case isl_dim_param: return 0; | |||
40 | case isl_dim_in: return dim->nparam; | |||
41 | case isl_dim_out: return dim->nparam + dim->n_in; | |||
42 | default: return 0; | |||
43 | } | |||
44 | } | |||
45 | ||||
46 | int isl_upoly_is_cst(__isl_keep struct isl_upoly *up) | |||
47 | { | |||
48 | if (!up) | |||
49 | return -1; | |||
50 | ||||
51 | return up->var < 0; | |||
52 | } | |||
53 | ||||
54 | __isl_keep struct isl_upoly_cst *isl_upoly_as_cst(__isl_keep struct isl_upoly *up) | |||
55 | { | |||
56 | if (!up) | |||
57 | return NULL((void*)0); | |||
58 | ||||
59 | isl_assert(up->ctx, up->var < 0, return NULL)do { if (up->var < 0) break; do { isl_handle_error(up-> ctx, isl_error_unknown, "Assertion \"" "up->var < 0" "\" failed" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 59); return ((void*)0); } while (0); } while (0); | |||
60 | ||||
61 | return (struct isl_upoly_cst *)up; | |||
62 | } | |||
63 | ||||
64 | __isl_keep struct isl_upoly_rec *isl_upoly_as_rec(__isl_keep struct isl_upoly *up) | |||
65 | { | |||
66 | if (!up) | |||
67 | return NULL((void*)0); | |||
68 | ||||
69 | isl_assert(up->ctx, up->var >= 0, return NULL)do { if (up->var >= 0) break; do { isl_handle_error(up-> ctx, isl_error_unknown, "Assertion \"" "up->var >= 0" "\" failed" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 69); return ((void*)0); } while (0); } while (0); | |||
70 | ||||
71 | return (struct isl_upoly_rec *)up; | |||
72 | } | |||
73 | ||||
74 | /* Compare two polynomials. | |||
75 | * | |||
76 | * Return -1 if "up1" is "smaller" than "up2", 1 if "up1" is "greater" | |||
77 | * than "up2" and 0 if they are equal. | |||
78 | */ | |||
79 | static int isl_upoly_plain_cmp(__isl_keep struct isl_upoly *up1, | |||
80 | __isl_keep struct isl_upoly *up2) | |||
81 | { | |||
82 | int i; | |||
83 | struct isl_upoly_rec *rec1, *rec2; | |||
84 | ||||
85 | if (up1 == up2) | |||
86 | return 0; | |||
87 | if (!up1) | |||
88 | return -1; | |||
89 | if (!up2) | |||
90 | return 1; | |||
91 | if (up1->var != up2->var) | |||
92 | return up1->var - up2->var; | |||
93 | ||||
94 | if (isl_upoly_is_cst(up1)) { | |||
95 | struct isl_upoly_cst *cst1, *cst2; | |||
96 | int cmp; | |||
97 | ||||
98 | cst1 = isl_upoly_as_cst(up1); | |||
99 | cst2 = isl_upoly_as_cst(up2); | |||
100 | if (!cst1 || !cst2) | |||
101 | return 0; | |||
102 | cmp = isl_int_cmp(cst1->n, cst2->n)isl_sioimath_cmp(*(cst1->n), *(cst2->n)); | |||
103 | if (cmp != 0) | |||
104 | return cmp; | |||
105 | return isl_int_cmp(cst1->d, cst2->d)isl_sioimath_cmp(*(cst1->d), *(cst2->d)); | |||
106 | } | |||
107 | ||||
108 | rec1 = isl_upoly_as_rec(up1); | |||
109 | rec2 = isl_upoly_as_rec(up2); | |||
110 | if (!rec1 || !rec2) | |||
111 | return 0; | |||
112 | ||||
113 | if (rec1->n != rec2->n) | |||
114 | return rec1->n - rec2->n; | |||
115 | ||||
116 | for (i = 0; i < rec1->n; ++i) { | |||
117 | int cmp = isl_upoly_plain_cmp(rec1->p[i], rec2->p[i]); | |||
118 | if (cmp != 0) | |||
119 | return cmp; | |||
120 | } | |||
121 | ||||
122 | return 0; | |||
123 | } | |||
124 | ||||
125 | isl_bool isl_upoly_is_equal(__isl_keep struct isl_upoly *up1, | |||
126 | __isl_keep struct isl_upoly *up2) | |||
127 | { | |||
128 | int i; | |||
129 | struct isl_upoly_rec *rec1, *rec2; | |||
130 | ||||
131 | if (!up1 || !up2) | |||
132 | return isl_bool_error; | |||
133 | if (up1 == up2) | |||
134 | return isl_bool_true; | |||
135 | if (up1->var != up2->var) | |||
136 | return isl_bool_false; | |||
137 | if (isl_upoly_is_cst(up1)) { | |||
138 | struct isl_upoly_cst *cst1, *cst2; | |||
139 | cst1 = isl_upoly_as_cst(up1); | |||
140 | cst2 = isl_upoly_as_cst(up2); | |||
141 | if (!cst1 || !cst2) | |||
142 | return isl_bool_error; | |||
143 | return isl_int_eq(cst1->n, cst2->n)(isl_sioimath_cmp(*(cst1->n), *(cst2->n)) == 0) && | |||
144 | isl_int_eq(cst1->d, cst2->d)(isl_sioimath_cmp(*(cst1->d), *(cst2->d)) == 0); | |||
145 | } | |||
146 | ||||
147 | rec1 = isl_upoly_as_rec(up1); | |||
148 | rec2 = isl_upoly_as_rec(up2); | |||
149 | if (!rec1 || !rec2) | |||
150 | return isl_bool_error; | |||
151 | ||||
152 | if (rec1->n != rec2->n) | |||
153 | return isl_bool_false; | |||
154 | ||||
155 | for (i = 0; i < rec1->n; ++i) { | |||
156 | isl_bool eq = isl_upoly_is_equal(rec1->p[i], rec2->p[i]); | |||
157 | if (eq < 0 || !eq) | |||
158 | return eq; | |||
159 | } | |||
160 | ||||
161 | return isl_bool_true; | |||
162 | } | |||
163 | ||||
164 | int isl_upoly_is_zero(__isl_keep struct isl_upoly *up) | |||
165 | { | |||
166 | struct isl_upoly_cst *cst; | |||
167 | ||||
168 | if (!up) | |||
169 | return -1; | |||
170 | if (!isl_upoly_is_cst(up)) | |||
171 | return 0; | |||
172 | ||||
173 | cst = isl_upoly_as_cst(up); | |||
174 | if (!cst) | |||
175 | return -1; | |||
176 | ||||
177 | return isl_int_is_zero(cst->n)(isl_sioimath_sgn(*(cst->n)) == 0) && isl_int_is_pos(cst->d)(isl_sioimath_sgn(*(cst->d)) > 0); | |||
178 | } | |||
179 | ||||
180 | int isl_upoly_sgn(__isl_keep struct isl_upoly *up) | |||
181 | { | |||
182 | struct isl_upoly_cst *cst; | |||
183 | ||||
184 | if (!up) | |||
185 | return 0; | |||
186 | if (!isl_upoly_is_cst(up)) | |||
187 | return 0; | |||
188 | ||||
189 | cst = isl_upoly_as_cst(up); | |||
190 | if (!cst) | |||
191 | return 0; | |||
192 | ||||
193 | return isl_int_sgn(cst->n)isl_sioimath_sgn(*(cst->n)); | |||
194 | } | |||
195 | ||||
196 | int isl_upoly_is_nan(__isl_keep struct isl_upoly *up) | |||
197 | { | |||
198 | struct isl_upoly_cst *cst; | |||
199 | ||||
200 | if (!up) | |||
201 | return -1; | |||
202 | if (!isl_upoly_is_cst(up)) | |||
203 | return 0; | |||
204 | ||||
205 | cst = isl_upoly_as_cst(up); | |||
206 | if (!cst) | |||
207 | return -1; | |||
208 | ||||
209 | return isl_int_is_zero(cst->n)(isl_sioimath_sgn(*(cst->n)) == 0) && isl_int_is_zero(cst->d)(isl_sioimath_sgn(*(cst->d)) == 0); | |||
210 | } | |||
211 | ||||
212 | int isl_upoly_is_infty(__isl_keep struct isl_upoly *up) | |||
213 | { | |||
214 | struct isl_upoly_cst *cst; | |||
215 | ||||
216 | if (!up) | |||
217 | return -1; | |||
218 | if (!isl_upoly_is_cst(up)) | |||
219 | return 0; | |||
220 | ||||
221 | cst = isl_upoly_as_cst(up); | |||
222 | if (!cst) | |||
223 | return -1; | |||
224 | ||||
225 | return isl_int_is_pos(cst->n)(isl_sioimath_sgn(*(cst->n)) > 0) && isl_int_is_zero(cst->d)(isl_sioimath_sgn(*(cst->d)) == 0); | |||
226 | } | |||
227 | ||||
228 | int isl_upoly_is_neginfty(__isl_keep struct isl_upoly *up) | |||
229 | { | |||
230 | struct isl_upoly_cst *cst; | |||
231 | ||||
232 | if (!up) | |||
233 | return -1; | |||
234 | if (!isl_upoly_is_cst(up)) | |||
235 | return 0; | |||
236 | ||||
237 | cst = isl_upoly_as_cst(up); | |||
238 | if (!cst) | |||
239 | return -1; | |||
240 | ||||
241 | return isl_int_is_neg(cst->n)(isl_sioimath_sgn(*(cst->n)) < 0) && isl_int_is_zero(cst->d)(isl_sioimath_sgn(*(cst->d)) == 0); | |||
242 | } | |||
243 | ||||
244 | int isl_upoly_is_one(__isl_keep struct isl_upoly *up) | |||
245 | { | |||
246 | struct isl_upoly_cst *cst; | |||
247 | ||||
248 | if (!up) | |||
249 | return -1; | |||
250 | if (!isl_upoly_is_cst(up)) | |||
251 | return 0; | |||
252 | ||||
253 | cst = isl_upoly_as_cst(up); | |||
254 | if (!cst) | |||
255 | return -1; | |||
256 | ||||
257 | return isl_int_eq(cst->n, cst->d)(isl_sioimath_cmp(*(cst->n), *(cst->d)) == 0) && isl_int_is_pos(cst->d)(isl_sioimath_sgn(*(cst->d)) > 0); | |||
258 | } | |||
259 | ||||
260 | int isl_upoly_is_negone(__isl_keep struct isl_upoly *up) | |||
261 | { | |||
262 | struct isl_upoly_cst *cst; | |||
263 | ||||
264 | if (!up) | |||
265 | return -1; | |||
266 | if (!isl_upoly_is_cst(up)) | |||
267 | return 0; | |||
268 | ||||
269 | cst = isl_upoly_as_cst(up); | |||
270 | if (!cst) | |||
271 | return -1; | |||
272 | ||||
273 | return isl_int_is_negone(cst->n)(isl_sioimath_cmp_si(*(cst->n), -1) == 0) && isl_int_is_one(cst->d)(isl_sioimath_cmp_si(*(cst->d), 1) == 0); | |||
274 | } | |||
275 | ||||
276 | __isl_give struct isl_upoly_cst *isl_upoly_cst_alloc(struct isl_ctx *ctx) | |||
277 | { | |||
278 | struct isl_upoly_cst *cst; | |||
279 | ||||
280 | cst = isl_alloc_type(ctx, struct isl_upoly_cst)((struct isl_upoly_cst *)isl_malloc_or_die(ctx, sizeof(struct isl_upoly_cst))); | |||
281 | if (!cst) | |||
282 | return NULL((void*)0); | |||
283 | ||||
284 | cst->up.ref = 1; | |||
285 | cst->up.ctx = ctx; | |||
286 | isl_ctx_ref(ctx); | |||
287 | cst->up.var = -1; | |||
288 | ||||
289 | isl_int_init(cst->n)isl_sioimath_init((cst->n)); | |||
290 | isl_int_init(cst->d)isl_sioimath_init((cst->d)); | |||
291 | ||||
292 | return cst; | |||
293 | } | |||
294 | ||||
295 | __isl_give struct isl_upoly *isl_upoly_zero(struct isl_ctx *ctx) | |||
296 | { | |||
297 | struct isl_upoly_cst *cst; | |||
298 | ||||
299 | cst = isl_upoly_cst_alloc(ctx); | |||
300 | if (!cst) | |||
301 | return NULL((void*)0); | |||
302 | ||||
303 | isl_int_set_si(cst->n, 0)isl_sioimath_set_si((cst->n), 0); | |||
304 | isl_int_set_si(cst->d, 1)isl_sioimath_set_si((cst->d), 1); | |||
305 | ||||
306 | return &cst->up; | |||
307 | } | |||
308 | ||||
309 | __isl_give struct isl_upoly *isl_upoly_one(struct isl_ctx *ctx) | |||
310 | { | |||
311 | struct isl_upoly_cst *cst; | |||
312 | ||||
313 | cst = isl_upoly_cst_alloc(ctx); | |||
314 | if (!cst) | |||
315 | return NULL((void*)0); | |||
316 | ||||
317 | isl_int_set_si(cst->n, 1)isl_sioimath_set_si((cst->n), 1); | |||
318 | isl_int_set_si(cst->d, 1)isl_sioimath_set_si((cst->d), 1); | |||
319 | ||||
320 | return &cst->up; | |||
321 | } | |||
322 | ||||
323 | __isl_give struct isl_upoly *isl_upoly_infty(struct isl_ctx *ctx) | |||
324 | { | |||
325 | struct isl_upoly_cst *cst; | |||
326 | ||||
327 | cst = isl_upoly_cst_alloc(ctx); | |||
328 | if (!cst) | |||
329 | return NULL((void*)0); | |||
330 | ||||
331 | isl_int_set_si(cst->n, 1)isl_sioimath_set_si((cst->n), 1); | |||
332 | isl_int_set_si(cst->d, 0)isl_sioimath_set_si((cst->d), 0); | |||
333 | ||||
334 | return &cst->up; | |||
335 | } | |||
336 | ||||
337 | __isl_give struct isl_upoly *isl_upoly_neginfty(struct isl_ctx *ctx) | |||
338 | { | |||
339 | struct isl_upoly_cst *cst; | |||
340 | ||||
341 | cst = isl_upoly_cst_alloc(ctx); | |||
342 | if (!cst) | |||
343 | return NULL((void*)0); | |||
344 | ||||
345 | isl_int_set_si(cst->n, -1)isl_sioimath_set_si((cst->n), -1); | |||
346 | isl_int_set_si(cst->d, 0)isl_sioimath_set_si((cst->d), 0); | |||
347 | ||||
348 | return &cst->up; | |||
349 | } | |||
350 | ||||
351 | __isl_give struct isl_upoly *isl_upoly_nan(struct isl_ctx *ctx) | |||
352 | { | |||
353 | struct isl_upoly_cst *cst; | |||
354 | ||||
355 | cst = isl_upoly_cst_alloc(ctx); | |||
356 | if (!cst) | |||
357 | return NULL((void*)0); | |||
358 | ||||
359 | isl_int_set_si(cst->n, 0)isl_sioimath_set_si((cst->n), 0); | |||
360 | isl_int_set_si(cst->d, 0)isl_sioimath_set_si((cst->d), 0); | |||
361 | ||||
362 | return &cst->up; | |||
363 | } | |||
364 | ||||
365 | __isl_give struct isl_upoly *isl_upoly_rat_cst(struct isl_ctx *ctx, | |||
366 | isl_int n, isl_int d) | |||
367 | { | |||
368 | struct isl_upoly_cst *cst; | |||
369 | ||||
370 | cst = isl_upoly_cst_alloc(ctx); | |||
371 | if (!cst) | |||
372 | return NULL((void*)0); | |||
373 | ||||
374 | isl_int_set(cst->n, n)isl_sioimath_set((cst->n), *(n)); | |||
375 | isl_int_set(cst->d, d)isl_sioimath_set((cst->d), *(d)); | |||
376 | ||||
377 | return &cst->up; | |||
378 | } | |||
379 | ||||
380 | __isl_give struct isl_upoly_rec *isl_upoly_alloc_rec(struct isl_ctx *ctx, | |||
381 | int var, int size) | |||
382 | { | |||
383 | struct isl_upoly_rec *rec; | |||
384 | ||||
385 | isl_assert(ctx, var >= 0, return NULL)do { if (var >= 0) break; do { isl_handle_error(ctx, isl_error_unknown , "Assertion \"" "var >= 0" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 385); return ((void*)0); } while (0); } while (0); | |||
386 | isl_assert(ctx, size >= 0, return NULL)do { if (size >= 0) break; do { isl_handle_error(ctx, isl_error_unknown , "Assertion \"" "size >= 0" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 386); return ((void*)0); } while (0); } while (0); | |||
387 | rec = isl_calloc(ctx, struct isl_upoly_rec,((struct isl_upoly_rec *)isl_calloc_or_die(ctx, 1, sizeof(struct isl_upoly_rec) + size * sizeof(struct isl_upoly *))) | |||
388 | sizeof(struct isl_upoly_rec) +((struct isl_upoly_rec *)isl_calloc_or_die(ctx, 1, sizeof(struct isl_upoly_rec) + size * sizeof(struct isl_upoly *))) | |||
389 | size * sizeof(struct isl_upoly *))((struct isl_upoly_rec *)isl_calloc_or_die(ctx, 1, sizeof(struct isl_upoly_rec) + size * sizeof(struct isl_upoly *))); | |||
390 | if (!rec) | |||
391 | return NULL((void*)0); | |||
392 | ||||
393 | rec->up.ref = 1; | |||
394 | rec->up.ctx = ctx; | |||
395 | isl_ctx_ref(ctx); | |||
396 | rec->up.var = var; | |||
397 | ||||
398 | rec->n = 0; | |||
399 | rec->size = size; | |||
400 | ||||
401 | return rec; | |||
402 | } | |||
403 | ||||
404 | __isl_give isl_qpolynomial *isl_qpolynomial_reset_domain_space( | |||
405 | __isl_take isl_qpolynomial *qp, __isl_take isl_space *dim) | |||
406 | { | |||
407 | qp = isl_qpolynomial_cow(qp); | |||
408 | if (!qp || !dim) | |||
409 | goto error; | |||
410 | ||||
411 | isl_space_free(qp->dim); | |||
412 | qp->dim = dim; | |||
413 | ||||
414 | return qp; | |||
415 | error: | |||
416 | isl_qpolynomial_free(qp); | |||
417 | isl_space_free(dim); | |||
418 | return NULL((void*)0); | |||
419 | } | |||
420 | ||||
421 | /* Reset the space of "qp". This function is called from isl_pw_templ.c | |||
422 | * and doesn't know if the space of an element object is represented | |||
423 | * directly or through its domain. It therefore passes along both. | |||
424 | */ | |||
425 | __isl_give isl_qpolynomial *isl_qpolynomial_reset_space_and_domain( | |||
426 | __isl_take isl_qpolynomial *qp, __isl_take isl_space *space, | |||
427 | __isl_take isl_space *domain) | |||
428 | { | |||
429 | isl_space_free(space); | |||
430 | return isl_qpolynomial_reset_domain_space(qp, domain); | |||
431 | } | |||
432 | ||||
433 | isl_ctx *isl_qpolynomial_get_ctx(__isl_keep isl_qpolynomial *qp) | |||
434 | { | |||
435 | return qp ? qp->dim->ctx : NULL((void*)0); | |||
436 | } | |||
437 | ||||
438 | __isl_give isl_space *isl_qpolynomial_get_domain_space( | |||
439 | __isl_keep isl_qpolynomial *qp) | |||
440 | { | |||
441 | return qp ? isl_space_copy(qp->dim) : NULL((void*)0); | |||
442 | } | |||
443 | ||||
444 | __isl_give isl_space *isl_qpolynomial_get_space(__isl_keep isl_qpolynomial *qp) | |||
445 | { | |||
446 | isl_space *space; | |||
447 | if (!qp) | |||
448 | return NULL((void*)0); | |||
449 | space = isl_space_copy(qp->dim); | |||
450 | space = isl_space_from_domain(space); | |||
451 | space = isl_space_add_dims(space, isl_dim_out, 1); | |||
452 | return space; | |||
453 | } | |||
454 | ||||
455 | /* Return the number of variables of the given type in the domain of "qp". | |||
456 | */ | |||
457 | unsigned isl_qpolynomial_domain_dim(__isl_keep isl_qpolynomial *qp, | |||
458 | enum isl_dim_type type) | |||
459 | { | |||
460 | if (!qp) | |||
461 | return 0; | |||
462 | if (type == isl_dim_div) | |||
463 | return qp->div->n_row; | |||
464 | if (type == isl_dim_all) | |||
465 | return isl_space_dim(qp->dim, isl_dim_all) + | |||
466 | isl_qpolynomial_domain_dim(qp, isl_dim_div); | |||
467 | return isl_space_dim(qp->dim, type); | |||
468 | } | |||
469 | ||||
470 | /* Externally, an isl_qpolynomial has a map space, but internally, the | |||
471 | * ls field corresponds to the domain of that space. | |||
472 | */ | |||
473 | unsigned isl_qpolynomial_dim(__isl_keep isl_qpolynomial *qp, | |||
474 | enum isl_dim_type type) | |||
475 | { | |||
476 | if (!qp) | |||
477 | return 0; | |||
478 | if (type == isl_dim_out) | |||
479 | return 1; | |||
480 | if (type == isl_dim_in) | |||
481 | type = isl_dim_set; | |||
482 | return isl_qpolynomial_domain_dim(qp, type); | |||
483 | } | |||
484 | ||||
485 | /* Return the offset of the first coefficient of type "type" in | |||
486 | * the domain of "qp". | |||
487 | */ | |||
488 | unsigned isl_qpolynomial_domain_offset(__isl_keep isl_qpolynomial *qp, | |||
489 | enum isl_dim_type type) | |||
490 | { | |||
491 | if (!qp) | |||
492 | return 0; | |||
493 | switch (type) { | |||
494 | case isl_dim_cst: | |||
495 | return 0; | |||
496 | case isl_dim_param: | |||
497 | case isl_dim_set: | |||
498 | return 1 + isl_space_offset(qp->dim, type); | |||
499 | case isl_dim_div: | |||
500 | return 1 + isl_space_dim(qp->dim, isl_dim_all); | |||
501 | default: | |||
502 | return 0; | |||
503 | } | |||
504 | } | |||
505 | ||||
506 | isl_bool isl_qpolynomial_is_zero(__isl_keep isl_qpolynomial *qp) | |||
507 | { | |||
508 | return qp ? isl_upoly_is_zero(qp->upoly) : isl_bool_error; | |||
509 | } | |||
510 | ||||
511 | isl_bool isl_qpolynomial_is_one(__isl_keep isl_qpolynomial *qp) | |||
512 | { | |||
513 | return qp ? isl_upoly_is_one(qp->upoly) : isl_bool_error; | |||
514 | } | |||
515 | ||||
516 | isl_bool isl_qpolynomial_is_nan(__isl_keep isl_qpolynomial *qp) | |||
517 | { | |||
518 | return qp ? isl_upoly_is_nan(qp->upoly) : isl_bool_error; | |||
519 | } | |||
520 | ||||
521 | isl_bool isl_qpolynomial_is_infty(__isl_keep isl_qpolynomial *qp) | |||
522 | { | |||
523 | return qp ? isl_upoly_is_infty(qp->upoly) : isl_bool_error; | |||
524 | } | |||
525 | ||||
526 | isl_bool isl_qpolynomial_is_neginfty(__isl_keep isl_qpolynomial *qp) | |||
527 | { | |||
528 | return qp ? isl_upoly_is_neginfty(qp->upoly) : isl_bool_error; | |||
529 | } | |||
530 | ||||
531 | int isl_qpolynomial_sgn(__isl_keep isl_qpolynomial *qp) | |||
532 | { | |||
533 | return qp ? isl_upoly_sgn(qp->upoly) : 0; | |||
534 | } | |||
535 | ||||
536 | static void upoly_free_cst(__isl_take struct isl_upoly_cst *cst) | |||
537 | { | |||
538 | isl_int_clear(cst->n)isl_sioimath_clear((cst->n)); | |||
539 | isl_int_clear(cst->d)isl_sioimath_clear((cst->d)); | |||
540 | } | |||
541 | ||||
542 | static void upoly_free_rec(__isl_take struct isl_upoly_rec *rec) | |||
543 | { | |||
544 | int i; | |||
545 | ||||
546 | for (i = 0; i < rec->n; ++i) | |||
547 | isl_upoly_free(rec->p[i]); | |||
548 | } | |||
549 | ||||
550 | __isl_give struct isl_upoly *isl_upoly_copy(__isl_keep struct isl_upoly *up) | |||
551 | { | |||
552 | if (!up) | |||
553 | return NULL((void*)0); | |||
554 | ||||
555 | up->ref++; | |||
556 | return up; | |||
557 | } | |||
558 | ||||
559 | __isl_give struct isl_upoly *isl_upoly_dup_cst(__isl_keep struct isl_upoly *up) | |||
560 | { | |||
561 | struct isl_upoly_cst *cst; | |||
562 | struct isl_upoly_cst *dup; | |||
563 | ||||
564 | cst = isl_upoly_as_cst(up); | |||
565 | if (!cst) | |||
566 | return NULL((void*)0); | |||
567 | ||||
568 | dup = isl_upoly_as_cst(isl_upoly_zero(up->ctx)); | |||
569 | if (!dup) | |||
570 | return NULL((void*)0); | |||
571 | isl_int_set(dup->n, cst->n)isl_sioimath_set((dup->n), *(cst->n)); | |||
572 | isl_int_set(dup->d, cst->d)isl_sioimath_set((dup->d), *(cst->d)); | |||
573 | ||||
574 | return &dup->up; | |||
575 | } | |||
576 | ||||
577 | __isl_give struct isl_upoly *isl_upoly_dup_rec(__isl_keep struct isl_upoly *up) | |||
578 | { | |||
579 | int i; | |||
580 | struct isl_upoly_rec *rec; | |||
581 | struct isl_upoly_rec *dup; | |||
582 | ||||
583 | rec = isl_upoly_as_rec(up); | |||
584 | if (!rec) | |||
585 | return NULL((void*)0); | |||
586 | ||||
587 | dup = isl_upoly_alloc_rec(up->ctx, up->var, rec->n); | |||
588 | if (!dup) | |||
589 | return NULL((void*)0); | |||
590 | ||||
591 | for (i = 0; i < rec->n; ++i) { | |||
592 | dup->p[i] = isl_upoly_copy(rec->p[i]); | |||
593 | if (!dup->p[i]) | |||
594 | goto error; | |||
595 | dup->n++; | |||
596 | } | |||
597 | ||||
598 | return &dup->up; | |||
599 | error: | |||
600 | isl_upoly_free(&dup->up); | |||
601 | return NULL((void*)0); | |||
602 | } | |||
603 | ||||
604 | __isl_give struct isl_upoly *isl_upoly_dup(__isl_keep struct isl_upoly *up) | |||
605 | { | |||
606 | if (!up) | |||
607 | return NULL((void*)0); | |||
608 | ||||
609 | if (isl_upoly_is_cst(up)) | |||
610 | return isl_upoly_dup_cst(up); | |||
611 | else | |||
612 | return isl_upoly_dup_rec(up); | |||
613 | } | |||
614 | ||||
615 | __isl_give struct isl_upoly *isl_upoly_cow(__isl_take struct isl_upoly *up) | |||
616 | { | |||
617 | if (!up) | |||
618 | return NULL((void*)0); | |||
619 | ||||
620 | if (up->ref == 1) | |||
621 | return up; | |||
622 | up->ref--; | |||
623 | return isl_upoly_dup(up); | |||
624 | } | |||
625 | ||||
626 | __isl_null struct isl_upoly *isl_upoly_free(__isl_take struct isl_upoly *up) | |||
627 | { | |||
628 | if (!up) | |||
629 | return NULL((void*)0); | |||
630 | ||||
631 | if (--up->ref > 0) | |||
632 | return NULL((void*)0); | |||
633 | ||||
634 | if (up->var < 0) | |||
635 | upoly_free_cst((struct isl_upoly_cst *)up); | |||
636 | else | |||
637 | upoly_free_rec((struct isl_upoly_rec *)up); | |||
638 | ||||
639 | isl_ctx_deref(up->ctx); | |||
640 | free(up); | |||
641 | return NULL((void*)0); | |||
642 | } | |||
643 | ||||
644 | static void isl_upoly_cst_reduce(__isl_keep struct isl_upoly_cst *cst) | |||
645 | { | |||
646 | isl_int gcd; | |||
647 | ||||
648 | isl_int_init(gcd)isl_sioimath_init((gcd)); | |||
649 | isl_int_gcd(gcd, cst->n, cst->d)isl_sioimath_gcd((gcd), *(cst->n), *(cst->d)); | |||
650 | if (!isl_int_is_zero(gcd)(isl_sioimath_sgn(*(gcd)) == 0) && !isl_int_is_one(gcd)(isl_sioimath_cmp_si(*(gcd), 1) == 0)) { | |||
651 | isl_int_divexact(cst->n, cst->n, gcd)isl_sioimath_tdiv_q((cst->n), *(cst->n), *(gcd)); | |||
652 | isl_int_divexact(cst->d, cst->d, gcd)isl_sioimath_tdiv_q((cst->d), *(cst->d), *(gcd)); | |||
653 | } | |||
654 | isl_int_clear(gcd)isl_sioimath_clear((gcd)); | |||
655 | } | |||
656 | ||||
657 | __isl_give struct isl_upoly *isl_upoly_sum_cst(__isl_take struct isl_upoly *up1, | |||
658 | __isl_take struct isl_upoly *up2) | |||
659 | { | |||
660 | struct isl_upoly_cst *cst1; | |||
661 | struct isl_upoly_cst *cst2; | |||
662 | ||||
663 | up1 = isl_upoly_cow(up1); | |||
664 | if (!up1 || !up2) | |||
665 | goto error; | |||
666 | ||||
667 | cst1 = isl_upoly_as_cst(up1); | |||
668 | cst2 = isl_upoly_as_cst(up2); | |||
669 | ||||
670 | if (isl_int_eq(cst1->d, cst2->d)(isl_sioimath_cmp(*(cst1->d), *(cst2->d)) == 0)) | |||
671 | isl_int_add(cst1->n, cst1->n, cst2->n)isl_sioimath_add((cst1->n), *(cst1->n), *(cst2->n)); | |||
672 | else { | |||
673 | isl_int_mul(cst1->n, cst1->n, cst2->d)isl_sioimath_mul((cst1->n), *(cst1->n), *(cst2->d)); | |||
674 | isl_int_addmul(cst1->n, cst2->n, cst1->d)isl_sioimath_addmul((cst1->n), *(cst2->n), *(cst1->d )); | |||
675 | isl_int_mul(cst1->d, cst1->d, cst2->d)isl_sioimath_mul((cst1->d), *(cst1->d), *(cst2->d)); | |||
676 | } | |||
677 | ||||
678 | isl_upoly_cst_reduce(cst1); | |||
679 | ||||
680 | isl_upoly_free(up2); | |||
681 | return up1; | |||
682 | error: | |||
683 | isl_upoly_free(up1); | |||
684 | isl_upoly_free(up2); | |||
685 | return NULL((void*)0); | |||
686 | } | |||
687 | ||||
688 | static __isl_give struct isl_upoly *replace_by_zero( | |||
689 | __isl_take struct isl_upoly *up) | |||
690 | { | |||
691 | struct isl_ctx *ctx; | |||
692 | ||||
693 | if (!up) | |||
694 | return NULL((void*)0); | |||
695 | ctx = up->ctx; | |||
696 | isl_upoly_free(up); | |||
697 | return isl_upoly_zero(ctx); | |||
698 | } | |||
699 | ||||
700 | static __isl_give struct isl_upoly *replace_by_constant_term( | |||
701 | __isl_take struct isl_upoly *up) | |||
702 | { | |||
703 | struct isl_upoly_rec *rec; | |||
704 | struct isl_upoly *cst; | |||
705 | ||||
706 | if (!up) | |||
707 | return NULL((void*)0); | |||
708 | ||||
709 | rec = isl_upoly_as_rec(up); | |||
710 | if (!rec) | |||
711 | goto error; | |||
712 | cst = isl_upoly_copy(rec->p[0]); | |||
713 | isl_upoly_free(up); | |||
714 | return cst; | |||
715 | error: | |||
716 | isl_upoly_free(up); | |||
717 | return NULL((void*)0); | |||
718 | } | |||
719 | ||||
720 | __isl_give struct isl_upoly *isl_upoly_sum(__isl_take struct isl_upoly *up1, | |||
721 | __isl_take struct isl_upoly *up2) | |||
722 | { | |||
723 | int i; | |||
724 | struct isl_upoly_rec *rec1, *rec2; | |||
725 | ||||
726 | if (!up1 || !up2) | |||
727 | goto error; | |||
728 | ||||
729 | if (isl_upoly_is_nan(up1)) { | |||
730 | isl_upoly_free(up2); | |||
731 | return up1; | |||
732 | } | |||
733 | ||||
734 | if (isl_upoly_is_nan(up2)) { | |||
735 | isl_upoly_free(up1); | |||
736 | return up2; | |||
737 | } | |||
738 | ||||
739 | if (isl_upoly_is_zero(up1)) { | |||
740 | isl_upoly_free(up1); | |||
741 | return up2; | |||
742 | } | |||
743 | ||||
744 | if (isl_upoly_is_zero(up2)) { | |||
745 | isl_upoly_free(up2); | |||
746 | return up1; | |||
747 | } | |||
748 | ||||
749 | if (up1->var < up2->var) | |||
750 | return isl_upoly_sum(up2, up1); | |||
751 | ||||
752 | if (up2->var < up1->var) { | |||
753 | struct isl_upoly_rec *rec; | |||
754 | if (isl_upoly_is_infty(up2) || isl_upoly_is_neginfty(up2)) { | |||
755 | isl_upoly_free(up1); | |||
756 | return up2; | |||
757 | } | |||
758 | up1 = isl_upoly_cow(up1); | |||
759 | rec = isl_upoly_as_rec(up1); | |||
760 | if (!rec) | |||
761 | goto error; | |||
762 | rec->p[0] = isl_upoly_sum(rec->p[0], up2); | |||
763 | if (rec->n == 1) | |||
764 | up1 = replace_by_constant_term(up1); | |||
765 | return up1; | |||
766 | } | |||
767 | ||||
768 | if (isl_upoly_is_cst(up1)) | |||
769 | return isl_upoly_sum_cst(up1, up2); | |||
770 | ||||
771 | rec1 = isl_upoly_as_rec(up1); | |||
772 | rec2 = isl_upoly_as_rec(up2); | |||
773 | if (!rec1 || !rec2) | |||
774 | goto error; | |||
775 | ||||
776 | if (rec1->n < rec2->n) | |||
777 | return isl_upoly_sum(up2, up1); | |||
778 | ||||
779 | up1 = isl_upoly_cow(up1); | |||
780 | rec1 = isl_upoly_as_rec(up1); | |||
781 | if (!rec1) | |||
782 | goto error; | |||
783 | ||||
784 | for (i = rec2->n - 1; i >= 0; --i) { | |||
785 | rec1->p[i] = isl_upoly_sum(rec1->p[i], | |||
786 | isl_upoly_copy(rec2->p[i])); | |||
787 | if (!rec1->p[i]) | |||
788 | goto error; | |||
789 | if (i == rec1->n - 1 && isl_upoly_is_zero(rec1->p[i])) { | |||
790 | isl_upoly_free(rec1->p[i]); | |||
791 | rec1->n--; | |||
792 | } | |||
793 | } | |||
794 | ||||
795 | if (rec1->n == 0) | |||
796 | up1 = replace_by_zero(up1); | |||
797 | else if (rec1->n == 1) | |||
798 | up1 = replace_by_constant_term(up1); | |||
799 | ||||
800 | isl_upoly_free(up2); | |||
801 | ||||
802 | return up1; | |||
803 | error: | |||
804 | isl_upoly_free(up1); | |||
805 | isl_upoly_free(up2); | |||
806 | return NULL((void*)0); | |||
807 | } | |||
808 | ||||
809 | __isl_give struct isl_upoly *isl_upoly_cst_add_isl_int( | |||
810 | __isl_take struct isl_upoly *up, isl_int v) | |||
811 | { | |||
812 | struct isl_upoly_cst *cst; | |||
813 | ||||
814 | up = isl_upoly_cow(up); | |||
815 | if (!up) | |||
816 | return NULL((void*)0); | |||
817 | ||||
818 | cst = isl_upoly_as_cst(up); | |||
819 | ||||
820 | isl_int_addmul(cst->n, cst->d, v)isl_sioimath_addmul((cst->n), *(cst->d), *(v)); | |||
821 | ||||
822 | return up; | |||
823 | } | |||
824 | ||||
825 | __isl_give struct isl_upoly *isl_upoly_add_isl_int( | |||
826 | __isl_take struct isl_upoly *up, isl_int v) | |||
827 | { | |||
828 | struct isl_upoly_rec *rec; | |||
829 | ||||
830 | if (!up) | |||
831 | return NULL((void*)0); | |||
832 | ||||
833 | if (isl_upoly_is_cst(up)) | |||
834 | return isl_upoly_cst_add_isl_int(up, v); | |||
835 | ||||
836 | up = isl_upoly_cow(up); | |||
837 | rec = isl_upoly_as_rec(up); | |||
838 | if (!rec) | |||
839 | goto error; | |||
840 | ||||
841 | rec->p[0] = isl_upoly_add_isl_int(rec->p[0], v); | |||
842 | if (!rec->p[0]) | |||
843 | goto error; | |||
844 | ||||
845 | return up; | |||
846 | error: | |||
847 | isl_upoly_free(up); | |||
848 | return NULL((void*)0); | |||
849 | } | |||
850 | ||||
851 | __isl_give struct isl_upoly *isl_upoly_cst_mul_isl_int( | |||
852 | __isl_take struct isl_upoly *up, isl_int v) | |||
853 | { | |||
854 | struct isl_upoly_cst *cst; | |||
855 | ||||
856 | if (isl_upoly_is_zero(up)) | |||
857 | return up; | |||
858 | ||||
859 | up = isl_upoly_cow(up); | |||
860 | if (!up) | |||
861 | return NULL((void*)0); | |||
862 | ||||
863 | cst = isl_upoly_as_cst(up); | |||
864 | ||||
865 | isl_int_mul(cst->n, cst->n, v)isl_sioimath_mul((cst->n), *(cst->n), *(v)); | |||
866 | ||||
867 | return up; | |||
868 | } | |||
869 | ||||
870 | __isl_give struct isl_upoly *isl_upoly_mul_isl_int( | |||
871 | __isl_take struct isl_upoly *up, isl_int v) | |||
872 | { | |||
873 | int i; | |||
874 | struct isl_upoly_rec *rec; | |||
875 | ||||
876 | if (!up) | |||
877 | return NULL((void*)0); | |||
878 | ||||
879 | if (isl_upoly_is_cst(up)) | |||
880 | return isl_upoly_cst_mul_isl_int(up, v); | |||
881 | ||||
882 | up = isl_upoly_cow(up); | |||
883 | rec = isl_upoly_as_rec(up); | |||
884 | if (!rec) | |||
885 | goto error; | |||
886 | ||||
887 | for (i = 0; i < rec->n; ++i) { | |||
888 | rec->p[i] = isl_upoly_mul_isl_int(rec->p[i], v); | |||
889 | if (!rec->p[i]) | |||
890 | goto error; | |||
891 | } | |||
892 | ||||
893 | return up; | |||
894 | error: | |||
895 | isl_upoly_free(up); | |||
896 | return NULL((void*)0); | |||
897 | } | |||
898 | ||||
899 | /* Multiply the constant polynomial "up" by "v". | |||
900 | */ | |||
901 | static __isl_give struct isl_upoly *isl_upoly_cst_scale_val( | |||
902 | __isl_take struct isl_upoly *up, __isl_keep isl_val *v) | |||
903 | { | |||
904 | struct isl_upoly_cst *cst; | |||
905 | ||||
906 | if (isl_upoly_is_zero(up)) | |||
907 | return up; | |||
908 | ||||
909 | up = isl_upoly_cow(up); | |||
910 | if (!up) | |||
911 | return NULL((void*)0); | |||
912 | ||||
913 | cst = isl_upoly_as_cst(up); | |||
914 | ||||
915 | isl_int_mul(cst->n, cst->n, v->n)isl_sioimath_mul((cst->n), *(cst->n), *(v->n)); | |||
916 | isl_int_mul(cst->d, cst->d, v->d)isl_sioimath_mul((cst->d), *(cst->d), *(v->d)); | |||
917 | isl_upoly_cst_reduce(cst); | |||
918 | ||||
919 | return up; | |||
920 | } | |||
921 | ||||
922 | /* Multiply the polynomial "up" by "v". | |||
923 | */ | |||
924 | static __isl_give struct isl_upoly *isl_upoly_scale_val( | |||
925 | __isl_take struct isl_upoly *up, __isl_keep isl_val *v) | |||
926 | { | |||
927 | int i; | |||
928 | struct isl_upoly_rec *rec; | |||
929 | ||||
930 | if (!up) | |||
931 | return NULL((void*)0); | |||
932 | ||||
933 | if (isl_upoly_is_cst(up)) | |||
934 | return isl_upoly_cst_scale_val(up, v); | |||
935 | ||||
936 | up = isl_upoly_cow(up); | |||
937 | rec = isl_upoly_as_rec(up); | |||
938 | if (!rec) | |||
939 | goto error; | |||
940 | ||||
941 | for (i = 0; i < rec->n; ++i) { | |||
942 | rec->p[i] = isl_upoly_scale_val(rec->p[i], v); | |||
943 | if (!rec->p[i]) | |||
944 | goto error; | |||
945 | } | |||
946 | ||||
947 | return up; | |||
948 | error: | |||
949 | isl_upoly_free(up); | |||
950 | return NULL((void*)0); | |||
951 | } | |||
952 | ||||
953 | __isl_give struct isl_upoly *isl_upoly_mul_cst(__isl_take struct isl_upoly *up1, | |||
954 | __isl_take struct isl_upoly *up2) | |||
955 | { | |||
956 | struct isl_upoly_cst *cst1; | |||
957 | struct isl_upoly_cst *cst2; | |||
958 | ||||
959 | up1 = isl_upoly_cow(up1); | |||
960 | if (!up1 || !up2) | |||
961 | goto error; | |||
962 | ||||
963 | cst1 = isl_upoly_as_cst(up1); | |||
964 | cst2 = isl_upoly_as_cst(up2); | |||
965 | ||||
966 | isl_int_mul(cst1->n, cst1->n, cst2->n)isl_sioimath_mul((cst1->n), *(cst1->n), *(cst2->n)); | |||
967 | isl_int_mul(cst1->d, cst1->d, cst2->d)isl_sioimath_mul((cst1->d), *(cst1->d), *(cst2->d)); | |||
968 | ||||
969 | isl_upoly_cst_reduce(cst1); | |||
970 | ||||
971 | isl_upoly_free(up2); | |||
972 | return up1; | |||
973 | error: | |||
974 | isl_upoly_free(up1); | |||
975 | isl_upoly_free(up2); | |||
976 | return NULL((void*)0); | |||
977 | } | |||
978 | ||||
979 | __isl_give struct isl_upoly *isl_upoly_mul_rec(__isl_take struct isl_upoly *up1, | |||
980 | __isl_take struct isl_upoly *up2) | |||
981 | { | |||
982 | struct isl_upoly_rec *rec1; | |||
983 | struct isl_upoly_rec *rec2; | |||
984 | struct isl_upoly_rec *res = NULL((void*)0); | |||
985 | int i, j; | |||
986 | int size; | |||
987 | ||||
988 | rec1 = isl_upoly_as_rec(up1); | |||
989 | rec2 = isl_upoly_as_rec(up2); | |||
990 | if (!rec1 || !rec2) | |||
991 | goto error; | |||
992 | size = rec1->n + rec2->n - 1; | |||
993 | res = isl_upoly_alloc_rec(up1->ctx, up1->var, size); | |||
994 | if (!res) | |||
995 | goto error; | |||
996 | ||||
997 | for (i = 0; i < rec1->n; ++i) { | |||
998 | res->p[i] = isl_upoly_mul(isl_upoly_copy(rec2->p[0]), | |||
999 | isl_upoly_copy(rec1->p[i])); | |||
1000 | if (!res->p[i]) | |||
1001 | goto error; | |||
1002 | res->n++; | |||
1003 | } | |||
1004 | for (; i < size; ++i) { | |||
1005 | res->p[i] = isl_upoly_zero(up1->ctx); | |||
1006 | if (!res->p[i]) | |||
1007 | goto error; | |||
1008 | res->n++; | |||
1009 | } | |||
1010 | for (i = 0; i < rec1->n; ++i) { | |||
1011 | for (j = 1; j < rec2->n; ++j) { | |||
1012 | struct isl_upoly *up; | |||
1013 | up = isl_upoly_mul(isl_upoly_copy(rec2->p[j]), | |||
1014 | isl_upoly_copy(rec1->p[i])); | |||
1015 | res->p[i + j] = isl_upoly_sum(res->p[i + j], up); | |||
1016 | if (!res->p[i + j]) | |||
1017 | goto error; | |||
1018 | } | |||
1019 | } | |||
1020 | ||||
1021 | isl_upoly_free(up1); | |||
1022 | isl_upoly_free(up2); | |||
1023 | ||||
1024 | return &res->up; | |||
1025 | error: | |||
1026 | isl_upoly_free(up1); | |||
1027 | isl_upoly_free(up2); | |||
1028 | isl_upoly_free(&res->up); | |||
1029 | return NULL((void*)0); | |||
1030 | } | |||
1031 | ||||
1032 | __isl_give struct isl_upoly *isl_upoly_mul(__isl_take struct isl_upoly *up1, | |||
1033 | __isl_take struct isl_upoly *up2) | |||
1034 | { | |||
1035 | if (!up1 || !up2) | |||
1036 | goto error; | |||
1037 | ||||
1038 | if (isl_upoly_is_nan(up1)) { | |||
1039 | isl_upoly_free(up2); | |||
1040 | return up1; | |||
1041 | } | |||
1042 | ||||
1043 | if (isl_upoly_is_nan(up2)) { | |||
1044 | isl_upoly_free(up1); | |||
1045 | return up2; | |||
1046 | } | |||
1047 | ||||
1048 | if (isl_upoly_is_zero(up1)) { | |||
1049 | isl_upoly_free(up2); | |||
1050 | return up1; | |||
1051 | } | |||
1052 | ||||
1053 | if (isl_upoly_is_zero(up2)) { | |||
1054 | isl_upoly_free(up1); | |||
1055 | return up2; | |||
1056 | } | |||
1057 | ||||
1058 | if (isl_upoly_is_one(up1)) { | |||
1059 | isl_upoly_free(up1); | |||
1060 | return up2; | |||
1061 | } | |||
1062 | ||||
1063 | if (isl_upoly_is_one(up2)) { | |||
1064 | isl_upoly_free(up2); | |||
1065 | return up1; | |||
1066 | } | |||
1067 | ||||
1068 | if (up1->var < up2->var) | |||
1069 | return isl_upoly_mul(up2, up1); | |||
1070 | ||||
1071 | if (up2->var < up1->var) { | |||
1072 | int i; | |||
1073 | struct isl_upoly_rec *rec; | |||
1074 | if (isl_upoly_is_infty(up2) || isl_upoly_is_neginfty(up2)) { | |||
1075 | isl_ctx *ctx = up1->ctx; | |||
1076 | isl_upoly_free(up1); | |||
1077 | isl_upoly_free(up2); | |||
1078 | return isl_upoly_nan(ctx); | |||
1079 | } | |||
1080 | up1 = isl_upoly_cow(up1); | |||
1081 | rec = isl_upoly_as_rec(up1); | |||
1082 | if (!rec) | |||
1083 | goto error; | |||
1084 | ||||
1085 | for (i = 0; i < rec->n; ++i) { | |||
1086 | rec->p[i] = isl_upoly_mul(rec->p[i], | |||
1087 | isl_upoly_copy(up2)); | |||
1088 | if (!rec->p[i]) | |||
1089 | goto error; | |||
1090 | } | |||
1091 | isl_upoly_free(up2); | |||
1092 | return up1; | |||
1093 | } | |||
1094 | ||||
1095 | if (isl_upoly_is_cst(up1)) | |||
1096 | return isl_upoly_mul_cst(up1, up2); | |||
1097 | ||||
1098 | return isl_upoly_mul_rec(up1, up2); | |||
1099 | error: | |||
1100 | isl_upoly_free(up1); | |||
1101 | isl_upoly_free(up2); | |||
1102 | return NULL((void*)0); | |||
1103 | } | |||
1104 | ||||
1105 | __isl_give struct isl_upoly *isl_upoly_pow(__isl_take struct isl_upoly *up, | |||
1106 | unsigned power) | |||
1107 | { | |||
1108 | struct isl_upoly *res; | |||
1109 | ||||
1110 | if (!up) | |||
1111 | return NULL((void*)0); | |||
1112 | if (power == 1) | |||
1113 | return up; | |||
1114 | ||||
1115 | if (power % 2) | |||
1116 | res = isl_upoly_copy(up); | |||
1117 | else | |||
1118 | res = isl_upoly_one(up->ctx); | |||
1119 | ||||
1120 | while (power >>= 1) { | |||
1121 | up = isl_upoly_mul(up, isl_upoly_copy(up)); | |||
1122 | if (power % 2) | |||
1123 | res = isl_upoly_mul(res, isl_upoly_copy(up)); | |||
1124 | } | |||
1125 | ||||
1126 | isl_upoly_free(up); | |||
1127 | return res; | |||
1128 | } | |||
1129 | ||||
1130 | __isl_give isl_qpolynomial *isl_qpolynomial_alloc(__isl_take isl_space *dim, | |||
1131 | unsigned n_div, __isl_take struct isl_upoly *up) | |||
1132 | { | |||
1133 | struct isl_qpolynomial *qp = NULL((void*)0); | |||
1134 | unsigned total; | |||
1135 | ||||
1136 | if (!dim || !up) | |||
1137 | goto error; | |||
1138 | ||||
1139 | if (!isl_space_is_set(dim)) | |||
1140 | isl_die(isl_space_get_ctx(dim), isl_error_invalid,do { isl_handle_error(isl_space_get_ctx(dim), isl_error_invalid , "domain of polynomial should be a set", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 1141); goto error; } while (0) | |||
1141 | "domain of polynomial should be a set", goto error)do { isl_handle_error(isl_space_get_ctx(dim), isl_error_invalid , "domain of polynomial should be a set", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 1141); goto error; } while (0); | |||
1142 | ||||
1143 | total = isl_space_dim(dim, isl_dim_all); | |||
1144 | ||||
1145 | qp = isl_calloc_type(dim->ctx, struct isl_qpolynomial)((struct isl_qpolynomial *)isl_calloc_or_die(dim->ctx, 1, sizeof (struct isl_qpolynomial))); | |||
1146 | if (!qp) | |||
1147 | goto error; | |||
1148 | ||||
1149 | qp->ref = 1; | |||
1150 | qp->div = isl_mat_alloc(dim->ctx, n_div, 1 + 1 + total + n_div); | |||
1151 | if (!qp->div) | |||
1152 | goto error; | |||
1153 | ||||
1154 | qp->dim = dim; | |||
1155 | qp->upoly = up; | |||
1156 | ||||
1157 | return qp; | |||
1158 | error: | |||
1159 | isl_space_free(dim); | |||
1160 | isl_upoly_free(up); | |||
1161 | isl_qpolynomial_free(qp); | |||
1162 | return NULL((void*)0); | |||
1163 | } | |||
1164 | ||||
1165 | __isl_give isl_qpolynomial *isl_qpolynomial_copy(__isl_keep isl_qpolynomial *qp) | |||
1166 | { | |||
1167 | if (!qp) | |||
1168 | return NULL((void*)0); | |||
1169 | ||||
1170 | qp->ref++; | |||
1171 | return qp; | |||
1172 | } | |||
1173 | ||||
1174 | __isl_give isl_qpolynomial *isl_qpolynomial_dup(__isl_keep isl_qpolynomial *qp) | |||
1175 | { | |||
1176 | struct isl_qpolynomial *dup; | |||
1177 | ||||
1178 | if (!qp) | |||
1179 | return NULL((void*)0); | |||
1180 | ||||
1181 | dup = isl_qpolynomial_alloc(isl_space_copy(qp->dim), qp->div->n_row, | |||
1182 | isl_upoly_copy(qp->upoly)); | |||
1183 | if (!dup) | |||
1184 | return NULL((void*)0); | |||
1185 | isl_mat_free(dup->div); | |||
1186 | dup->div = isl_mat_copy(qp->div); | |||
1187 | if (!dup->div) | |||
1188 | goto error; | |||
1189 | ||||
1190 | return dup; | |||
1191 | error: | |||
1192 | isl_qpolynomial_free(dup); | |||
1193 | return NULL((void*)0); | |||
1194 | } | |||
1195 | ||||
1196 | __isl_give isl_qpolynomial *isl_qpolynomial_cow(__isl_take isl_qpolynomial *qp) | |||
1197 | { | |||
1198 | if (!qp) | |||
1199 | return NULL((void*)0); | |||
1200 | ||||
1201 | if (qp->ref == 1) | |||
1202 | return qp; | |||
1203 | qp->ref--; | |||
1204 | return isl_qpolynomial_dup(qp); | |||
1205 | } | |||
1206 | ||||
1207 | __isl_null isl_qpolynomial *isl_qpolynomial_free( | |||
1208 | __isl_take isl_qpolynomial *qp) | |||
1209 | { | |||
1210 | if (!qp) | |||
1211 | return NULL((void*)0); | |||
1212 | ||||
1213 | if (--qp->ref > 0) | |||
1214 | return NULL((void*)0); | |||
1215 | ||||
1216 | isl_space_free(qp->dim); | |||
1217 | isl_mat_free(qp->div); | |||
1218 | isl_upoly_free(qp->upoly); | |||
1219 | ||||
1220 | free(qp); | |||
1221 | return NULL((void*)0); | |||
1222 | } | |||
1223 | ||||
1224 | __isl_give struct isl_upoly *isl_upoly_var_pow(isl_ctx *ctx, int pos, int power) | |||
1225 | { | |||
1226 | int i; | |||
1227 | struct isl_upoly_rec *rec; | |||
1228 | struct isl_upoly_cst *cst; | |||
1229 | ||||
1230 | rec = isl_upoly_alloc_rec(ctx, pos, 1 + power); | |||
1231 | if (!rec) | |||
1232 | return NULL((void*)0); | |||
1233 | for (i = 0; i < 1 + power; ++i) { | |||
1234 | rec->p[i] = isl_upoly_zero(ctx); | |||
1235 | if (!rec->p[i]) | |||
1236 | goto error; | |||
1237 | rec->n++; | |||
1238 | } | |||
1239 | cst = isl_upoly_as_cst(rec->p[power]); | |||
1240 | isl_int_set_si(cst->n, 1)isl_sioimath_set_si((cst->n), 1); | |||
1241 | ||||
1242 | return &rec->up; | |||
1243 | error: | |||
1244 | isl_upoly_free(&rec->up); | |||
1245 | return NULL((void*)0); | |||
1246 | } | |||
1247 | ||||
1248 | /* r array maps original positions to new positions. | |||
1249 | */ | |||
1250 | static __isl_give struct isl_upoly *reorder(__isl_take struct isl_upoly *up, | |||
1251 | int *r) | |||
1252 | { | |||
1253 | int i; | |||
1254 | struct isl_upoly_rec *rec; | |||
1255 | struct isl_upoly *base; | |||
1256 | struct isl_upoly *res; | |||
1257 | ||||
1258 | if (isl_upoly_is_cst(up)) | |||
1259 | return up; | |||
1260 | ||||
1261 | rec = isl_upoly_as_rec(up); | |||
1262 | if (!rec) | |||
1263 | goto error; | |||
1264 | ||||
1265 | isl_assert(up->ctx, rec->n >= 1, goto error)do { if (rec->n >= 1) break; do { isl_handle_error(up-> ctx, isl_error_unknown, "Assertion \"" "rec->n >= 1" "\" failed" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 1265); goto error; } while (0); } while (0); | |||
1266 | ||||
1267 | base = isl_upoly_var_pow(up->ctx, r[up->var], 1); | |||
1268 | res = reorder(isl_upoly_copy(rec->p[rec->n - 1]), r); | |||
1269 | ||||
1270 | for (i = rec->n - 2; i >= 0; --i) { | |||
1271 | res = isl_upoly_mul(res, isl_upoly_copy(base)); | |||
1272 | res = isl_upoly_sum(res, reorder(isl_upoly_copy(rec->p[i]), r)); | |||
1273 | } | |||
1274 | ||||
1275 | isl_upoly_free(base); | |||
1276 | isl_upoly_free(up); | |||
1277 | ||||
1278 | return res; | |||
1279 | error: | |||
1280 | isl_upoly_free(up); | |||
1281 | return NULL((void*)0); | |||
1282 | } | |||
1283 | ||||
1284 | static isl_bool compatible_divs(__isl_keep isl_mat *div1, | |||
1285 | __isl_keep isl_mat *div2) | |||
1286 | { | |||
1287 | int n_row, n_col; | |||
1288 | isl_bool equal; | |||
1289 | ||||
1290 | isl_assert(div1->ctx, div1->n_row >= div2->n_row &&do { if (div1->n_row >= div2->n_row && div1-> n_col >= div2->n_col) break; do { isl_handle_error(div1 ->ctx, isl_error_unknown, "Assertion \"" "div1->n_row >= div2->n_row && div1->n_col >= div2->n_col" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 1292); return isl_bool_error; } while (0); } while (0) | |||
1291 | div1->n_col >= div2->n_col,do { if (div1->n_row >= div2->n_row && div1-> n_col >= div2->n_col) break; do { isl_handle_error(div1 ->ctx, isl_error_unknown, "Assertion \"" "div1->n_row >= div2->n_row && div1->n_col >= div2->n_col" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 1292); return isl_bool_error; } while (0); } while (0) | |||
1292 | return isl_bool_error)do { if (div1->n_row >= div2->n_row && div1-> n_col >= div2->n_col) break; do { isl_handle_error(div1 ->ctx, isl_error_unknown, "Assertion \"" "div1->n_row >= div2->n_row && div1->n_col >= div2->n_col" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 1292); return isl_bool_error; } while (0); } while (0); | |||
1293 | ||||
1294 | if (div1->n_row == div2->n_row) | |||
1295 | return isl_mat_is_equal(div1, div2); | |||
1296 | ||||
1297 | n_row = div1->n_row; | |||
1298 | n_col = div1->n_col; | |||
1299 | div1->n_row = div2->n_row; | |||
1300 | div1->n_col = div2->n_col; | |||
1301 | ||||
1302 | equal = isl_mat_is_equal(div1, div2); | |||
1303 | ||||
1304 | div1->n_row = n_row; | |||
1305 | div1->n_col = n_col; | |||
1306 | ||||
1307 | return equal; | |||
1308 | } | |||
1309 | ||||
1310 | static int cmp_row(__isl_keep isl_mat *div, int i, int j) | |||
1311 | { | |||
1312 | int li, lj; | |||
1313 | ||||
1314 | li = isl_seq_last_non_zero(div->row[i], div->n_col); | |||
1315 | lj = isl_seq_last_non_zero(div->row[j], div->n_col); | |||
1316 | ||||
1317 | if (li != lj) | |||
1318 | return li - lj; | |||
1319 | ||||
1320 | return isl_seq_cmp(div->row[i], div->row[j], div->n_col); | |||
1321 | } | |||
1322 | ||||
1323 | struct isl_div_sort_info { | |||
1324 | isl_mat *div; | |||
1325 | int row; | |||
1326 | }; | |||
1327 | ||||
1328 | static int div_sort_cmp(const void *p1, const void *p2) | |||
1329 | { | |||
1330 | const struct isl_div_sort_info *i1, *i2; | |||
1331 | i1 = (const struct isl_div_sort_info *) p1; | |||
1332 | i2 = (const struct isl_div_sort_info *) p2; | |||
1333 | ||||
1334 | return cmp_row(i1->div, i1->row, i2->row); | |||
1335 | } | |||
1336 | ||||
1337 | /* Sort divs and remove duplicates. | |||
1338 | */ | |||
1339 | static __isl_give isl_qpolynomial *sort_divs(__isl_take isl_qpolynomial *qp) | |||
1340 | { | |||
1341 | int i; | |||
1342 | int skip; | |||
1343 | int len; | |||
1344 | struct isl_div_sort_info *array = NULL((void*)0); | |||
1345 | int *pos = NULL((void*)0), *at = NULL((void*)0); | |||
1346 | int *reordering = NULL((void*)0); | |||
1347 | unsigned div_pos; | |||
1348 | ||||
1349 | if (!qp) | |||
1350 | return NULL((void*)0); | |||
1351 | if (qp->div->n_row <= 1) | |||
1352 | return qp; | |||
1353 | ||||
1354 | div_pos = isl_space_dim(qp->dim, isl_dim_all); | |||
1355 | ||||
1356 | array = isl_alloc_array(qp->div->ctx, struct isl_div_sort_info,((struct isl_div_sort_info *)isl_malloc_or_die(qp->div-> ctx, (qp->div->n_row)*sizeof(struct isl_div_sort_info)) ) | |||
1357 | qp->div->n_row)((struct isl_div_sort_info *)isl_malloc_or_die(qp->div-> ctx, (qp->div->n_row)*sizeof(struct isl_div_sort_info)) ); | |||
1358 | pos = isl_alloc_array(qp->div->ctx, int, qp->div->n_row)((int *)isl_malloc_or_die(qp->div->ctx, (qp->div-> n_row)*sizeof(int))); | |||
1359 | at = isl_alloc_array(qp->div->ctx, int, qp->div->n_row)((int *)isl_malloc_or_die(qp->div->ctx, (qp->div-> n_row)*sizeof(int))); | |||
1360 | len = qp->div->n_col - 2; | |||
1361 | reordering = isl_alloc_array(qp->div->ctx, int, len)((int *)isl_malloc_or_die(qp->div->ctx, (len)*sizeof(int ))); | |||
1362 | if (!array || !pos || !at || !reordering) | |||
1363 | goto error; | |||
1364 | ||||
1365 | for (i = 0; i < qp->div->n_row; ++i) { | |||
1366 | array[i].div = qp->div; | |||
1367 | array[i].row = i; | |||
1368 | pos[i] = i; | |||
1369 | at[i] = i; | |||
1370 | } | |||
1371 | ||||
1372 | qsort(array, qp->div->n_row, sizeof(struct isl_div_sort_info), | |||
1373 | div_sort_cmp); | |||
1374 | ||||
1375 | for (i = 0; i < div_pos; ++i) | |||
1376 | reordering[i] = i; | |||
1377 | ||||
1378 | for (i = 0; i < qp->div->n_row; ++i) { | |||
1379 | if (pos[array[i].row] == i) | |||
1380 | continue; | |||
1381 | qp->div = isl_mat_swap_rows(qp->div, i, pos[array[i].row]); | |||
1382 | pos[at[i]] = pos[array[i].row]; | |||
1383 | at[pos[array[i].row]] = at[i]; | |||
1384 | at[i] = array[i].row; | |||
1385 | pos[array[i].row] = i; | |||
1386 | } | |||
1387 | ||||
1388 | skip = 0; | |||
1389 | for (i = 0; i < len - div_pos; ++i) { | |||
1390 | if (i > 0 && | |||
1391 | isl_seq_eq(qp->div->row[i - skip - 1], | |||
1392 | qp->div->row[i - skip], qp->div->n_col)) { | |||
1393 | qp->div = isl_mat_drop_rows(qp->div, i - skip, 1); | |||
1394 | isl_mat_col_add(qp->div, 2 + div_pos + i - skip - 1, | |||
1395 | 2 + div_pos + i - skip); | |||
1396 | qp->div = isl_mat_drop_cols(qp->div, | |||
1397 | 2 + div_pos + i - skip, 1); | |||
1398 | skip++; | |||
1399 | } | |||
1400 | reordering[div_pos + array[i].row] = div_pos + i - skip; | |||
1401 | } | |||
1402 | ||||
1403 | qp->upoly = reorder(qp->upoly, reordering); | |||
1404 | ||||
1405 | if (!qp->upoly || !qp->div) | |||
1406 | goto error; | |||
1407 | ||||
1408 | free(at); | |||
1409 | free(pos); | |||
1410 | free(array); | |||
1411 | free(reordering); | |||
1412 | ||||
1413 | return qp; | |||
1414 | error: | |||
1415 | free(at); | |||
1416 | free(pos); | |||
1417 | free(array); | |||
1418 | free(reordering); | |||
1419 | isl_qpolynomial_free(qp); | |||
1420 | return NULL((void*)0); | |||
1421 | } | |||
1422 | ||||
1423 | static __isl_give struct isl_upoly *expand(__isl_take struct isl_upoly *up, | |||
1424 | int *exp, int first) | |||
1425 | { | |||
1426 | int i; | |||
1427 | struct isl_upoly_rec *rec; | |||
1428 | ||||
1429 | if (isl_upoly_is_cst(up)) | |||
1430 | return up; | |||
1431 | ||||
1432 | if (up->var < first) | |||
1433 | return up; | |||
1434 | ||||
1435 | if (exp[up->var - first] == up->var - first) | |||
1436 | return up; | |||
1437 | ||||
1438 | up = isl_upoly_cow(up); | |||
1439 | if (!up) | |||
1440 | goto error; | |||
1441 | ||||
1442 | up->var = exp[up->var - first] + first; | |||
1443 | ||||
1444 | rec = isl_upoly_as_rec(up); | |||
1445 | if (!rec) | |||
1446 | goto error; | |||
1447 | ||||
1448 | for (i = 0; i < rec->n; ++i) { | |||
1449 | rec->p[i] = expand(rec->p[i], exp, first); | |||
1450 | if (!rec->p[i]) | |||
1451 | goto error; | |||
1452 | } | |||
1453 | ||||
1454 | return up; | |||
1455 | error: | |||
1456 | isl_upoly_free(up); | |||
1457 | return NULL((void*)0); | |||
1458 | } | |||
1459 | ||||
1460 | static __isl_give isl_qpolynomial *with_merged_divs( | |||
1461 | __isl_give isl_qpolynomial *(*fn)(__isl_take isl_qpolynomial *qp1, | |||
1462 | __isl_take isl_qpolynomial *qp2), | |||
1463 | __isl_take isl_qpolynomial *qp1, __isl_take isl_qpolynomial *qp2) | |||
1464 | { | |||
1465 | int *exp1 = NULL((void*)0); | |||
1466 | int *exp2 = NULL((void*)0); | |||
1467 | isl_mat *div = NULL((void*)0); | |||
1468 | int n_div1, n_div2; | |||
1469 | ||||
1470 | qp1 = isl_qpolynomial_cow(qp1); | |||
1471 | qp2 = isl_qpolynomial_cow(qp2); | |||
1472 | ||||
1473 | if (!qp1 || !qp2) | |||
1474 | goto error; | |||
1475 | ||||
1476 | isl_assert(qp1->div->ctx, qp1->div->n_row >= qp2->div->n_row &&do { if (qp1->div->n_row >= qp2->div->n_row && qp1->div->n_col >= qp2->div->n_col) break; do { isl_handle_error(qp1->div->ctx, isl_error_unknown, "Assertion \"" "qp1->div->n_row >= qp2->div->n_row && qp1->div->n_col >= qp2->div->n_col" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 1477); goto error; } while (0); } while (0) | |||
1477 | qp1->div->n_col >= qp2->div->n_col, goto error)do { if (qp1->div->n_row >= qp2->div->n_row && qp1->div->n_col >= qp2->div->n_col) break; do { isl_handle_error(qp1->div->ctx, isl_error_unknown, "Assertion \"" "qp1->div->n_row >= qp2->div->n_row && qp1->div->n_col >= qp2->div->n_col" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 1477); goto error; } while (0); } while (0); | |||
1478 | ||||
1479 | n_div1 = qp1->div->n_row; | |||
1480 | n_div2 = qp2->div->n_row; | |||
1481 | exp1 = isl_alloc_array(qp1->div->ctx, int, n_div1)((int *)isl_malloc_or_die(qp1->div->ctx, (n_div1)*sizeof (int))); | |||
1482 | exp2 = isl_alloc_array(qp2->div->ctx, int, n_div2)((int *)isl_malloc_or_die(qp2->div->ctx, (n_div2)*sizeof (int))); | |||
1483 | if ((n_div1 && !exp1) || (n_div2 && !exp2)) | |||
1484 | goto error; | |||
1485 | ||||
1486 | div = isl_merge_divs(qp1->div, qp2->div, exp1, exp2); | |||
1487 | if (!div) | |||
1488 | goto error; | |||
1489 | ||||
1490 | isl_mat_free(qp1->div); | |||
1491 | qp1->div = isl_mat_copy(div); | |||
1492 | isl_mat_free(qp2->div); | |||
1493 | qp2->div = isl_mat_copy(div); | |||
1494 | ||||
1495 | qp1->upoly = expand(qp1->upoly, exp1, div->n_col - div->n_row - 2); | |||
1496 | qp2->upoly = expand(qp2->upoly, exp2, div->n_col - div->n_row - 2); | |||
1497 | ||||
1498 | if (!qp1->upoly || !qp2->upoly) | |||
1499 | goto error; | |||
1500 | ||||
1501 | isl_mat_free(div); | |||
1502 | free(exp1); | |||
1503 | free(exp2); | |||
1504 | ||||
1505 | return fn(qp1, qp2); | |||
1506 | error: | |||
1507 | isl_mat_free(div); | |||
1508 | free(exp1); | |||
1509 | free(exp2); | |||
1510 | isl_qpolynomial_free(qp1); | |||
1511 | isl_qpolynomial_free(qp2); | |||
1512 | return NULL((void*)0); | |||
1513 | } | |||
1514 | ||||
1515 | __isl_give isl_qpolynomial *isl_qpolynomial_add(__isl_take isl_qpolynomial *qp1, | |||
1516 | __isl_take isl_qpolynomial *qp2) | |||
1517 | { | |||
1518 | isl_bool compatible; | |||
1519 | ||||
1520 | qp1 = isl_qpolynomial_cow(qp1); | |||
1521 | ||||
1522 | if (!qp1 || !qp2) | |||
1523 | goto error; | |||
1524 | ||||
1525 | if (qp1->div->n_row < qp2->div->n_row) | |||
1526 | return isl_qpolynomial_add(qp2, qp1); | |||
1527 | ||||
1528 | isl_assert(qp1->dim->ctx, isl_space_is_equal(qp1->dim, qp2->dim), goto error)do { if (isl_space_is_equal(qp1->dim, qp2->dim)) break; do { isl_handle_error(qp1->dim->ctx, isl_error_unknown , "Assertion \"" "isl_space_is_equal(qp1->dim, qp2->dim)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 1528); goto error; } while (0); } while (0); | |||
1529 | compatible = compatible_divs(qp1->div, qp2->div); | |||
1530 | if (compatible < 0) | |||
1531 | goto error; | |||
1532 | if (!compatible) | |||
1533 | return with_merged_divs(isl_qpolynomial_add, qp1, qp2); | |||
1534 | ||||
1535 | qp1->upoly = isl_upoly_sum(qp1->upoly, isl_upoly_copy(qp2->upoly)); | |||
1536 | if (!qp1->upoly) | |||
1537 | goto error; | |||
1538 | ||||
1539 | isl_qpolynomial_free(qp2); | |||
1540 | ||||
1541 | return qp1; | |||
1542 | error: | |||
1543 | isl_qpolynomial_free(qp1); | |||
1544 | isl_qpolynomial_free(qp2); | |||
1545 | return NULL((void*)0); | |||
1546 | } | |||
1547 | ||||
1548 | __isl_give isl_qpolynomial *isl_qpolynomial_add_on_domain( | |||
1549 | __isl_keep isl_setisl_map *dom, | |||
1550 | __isl_take isl_qpolynomial *qp1, | |||
1551 | __isl_take isl_qpolynomial *qp2) | |||
1552 | { | |||
1553 | qp1 = isl_qpolynomial_add(qp1, qp2); | |||
1554 | qp1 = isl_qpolynomial_gist(qp1, isl_set_copy(dom)); | |||
1555 | return qp1; | |||
1556 | } | |||
1557 | ||||
1558 | __isl_give isl_qpolynomial *isl_qpolynomial_sub(__isl_take isl_qpolynomial *qp1, | |||
1559 | __isl_take isl_qpolynomial *qp2) | |||
1560 | { | |||
1561 | return isl_qpolynomial_add(qp1, isl_qpolynomial_neg(qp2)); | |||
1562 | } | |||
1563 | ||||
1564 | __isl_give isl_qpolynomial *isl_qpolynomial_add_isl_int( | |||
1565 | __isl_take isl_qpolynomial *qp, isl_int v) | |||
1566 | { | |||
1567 | if (isl_int_is_zero(v)(isl_sioimath_sgn(*(v)) == 0)) | |||
1568 | return qp; | |||
1569 | ||||
1570 | qp = isl_qpolynomial_cow(qp); | |||
1571 | if (!qp) | |||
1572 | return NULL((void*)0); | |||
1573 | ||||
1574 | qp->upoly = isl_upoly_add_isl_int(qp->upoly, v); | |||
1575 | if (!qp->upoly) | |||
1576 | goto error; | |||
1577 | ||||
1578 | return qp; | |||
1579 | error: | |||
1580 | isl_qpolynomial_free(qp); | |||
1581 | return NULL((void*)0); | |||
1582 | ||||
1583 | } | |||
1584 | ||||
1585 | __isl_give isl_qpolynomial *isl_qpolynomial_neg(__isl_take isl_qpolynomial *qp) | |||
1586 | { | |||
1587 | if (!qp) | |||
1588 | return NULL((void*)0); | |||
1589 | ||||
1590 | return isl_qpolynomial_mul_isl_int(qp, qp->dim->ctx->negone); | |||
1591 | } | |||
1592 | ||||
1593 | __isl_give isl_qpolynomial *isl_qpolynomial_mul_isl_int( | |||
1594 | __isl_take isl_qpolynomial *qp, isl_int v) | |||
1595 | { | |||
1596 | if (isl_int_is_one(v)(isl_sioimath_cmp_si(*(v), 1) == 0)) | |||
1597 | return qp; | |||
1598 | ||||
1599 | if (qp && isl_int_is_zero(v)(isl_sioimath_sgn(*(v)) == 0)) { | |||
1600 | isl_qpolynomial *zero; | |||
1601 | zero = isl_qpolynomial_zero_on_domain(isl_space_copy(qp->dim)); | |||
1602 | isl_qpolynomial_free(qp); | |||
1603 | return zero; | |||
1604 | } | |||
1605 | ||||
1606 | qp = isl_qpolynomial_cow(qp); | |||
1607 | if (!qp) | |||
1608 | return NULL((void*)0); | |||
1609 | ||||
1610 | qp->upoly = isl_upoly_mul_isl_int(qp->upoly, v); | |||
1611 | if (!qp->upoly) | |||
1612 | goto error; | |||
1613 | ||||
1614 | return qp; | |||
1615 | error: | |||
1616 | isl_qpolynomial_free(qp); | |||
1617 | return NULL((void*)0); | |||
1618 | } | |||
1619 | ||||
1620 | __isl_give isl_qpolynomial *isl_qpolynomial_scale( | |||
1621 | __isl_take isl_qpolynomial *qp, isl_int v) | |||
1622 | { | |||
1623 | return isl_qpolynomial_mul_isl_int(qp, v); | |||
1624 | } | |||
1625 | ||||
1626 | /* Multiply "qp" by "v". | |||
1627 | */ | |||
1628 | __isl_give isl_qpolynomial *isl_qpolynomial_scale_val( | |||
1629 | __isl_take isl_qpolynomial *qp, __isl_take isl_val *v) | |||
1630 | { | |||
1631 | if (!qp || !v) | |||
1632 | goto error; | |||
1633 | ||||
1634 | if (!isl_val_is_rat(v)) | |||
1635 | isl_die(isl_qpolynomial_get_ctx(qp), isl_error_invalid,do { isl_handle_error(isl_qpolynomial_get_ctx(qp), isl_error_invalid , "expecting rational factor", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 1636); goto error; } while (0) | |||
1636 | "expecting rational factor", goto error)do { isl_handle_error(isl_qpolynomial_get_ctx(qp), isl_error_invalid , "expecting rational factor", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 1636); goto error; } while (0); | |||
1637 | ||||
1638 | if (isl_val_is_one(v)) { | |||
1639 | isl_val_free(v); | |||
1640 | return qp; | |||
1641 | } | |||
1642 | ||||
1643 | if (isl_val_is_zero(v)) { | |||
1644 | isl_space *space; | |||
1645 | ||||
1646 | space = isl_qpolynomial_get_domain_space(qp); | |||
1647 | isl_qpolynomial_free(qp); | |||
1648 | isl_val_free(v); | |||
1649 | return isl_qpolynomial_zero_on_domain(space); | |||
1650 | } | |||
1651 | ||||
1652 | qp = isl_qpolynomial_cow(qp); | |||
1653 | if (!qp) | |||
1654 | goto error; | |||
1655 | ||||
1656 | qp->upoly = isl_upoly_scale_val(qp->upoly, v); | |||
1657 | if (!qp->upoly) | |||
1658 | qp = isl_qpolynomial_free(qp); | |||
1659 | ||||
1660 | isl_val_free(v); | |||
1661 | return qp; | |||
1662 | error: | |||
1663 | isl_val_free(v); | |||
1664 | isl_qpolynomial_free(qp); | |||
1665 | return NULL((void*)0); | |||
1666 | } | |||
1667 | ||||
1668 | /* Divide "qp" by "v". | |||
1669 | */ | |||
1670 | __isl_give isl_qpolynomial *isl_qpolynomial_scale_down_val( | |||
1671 | __isl_take isl_qpolynomial *qp, __isl_take isl_val *v) | |||
1672 | { | |||
1673 | if (!qp || !v) | |||
1674 | goto error; | |||
1675 | ||||
1676 | if (!isl_val_is_rat(v)) | |||
1677 | isl_die(isl_qpolynomial_get_ctx(qp), isl_error_invalid,do { isl_handle_error(isl_qpolynomial_get_ctx(qp), isl_error_invalid , "expecting rational factor", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 1678); goto error; } while (0) | |||
1678 | "expecting rational factor", goto error)do { isl_handle_error(isl_qpolynomial_get_ctx(qp), isl_error_invalid , "expecting rational factor", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 1678); goto error; } while (0); | |||
1679 | if (isl_val_is_zero(v)) | |||
1680 | 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_polynomial.c" , 1681); goto error; } while (0) | |||
1681 | "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_polynomial.c" , 1681); goto error; } while (0); | |||
1682 | ||||
1683 | return isl_qpolynomial_scale_val(qp, isl_val_inv(v)); | |||
1684 | error: | |||
1685 | isl_val_free(v); | |||
1686 | isl_qpolynomial_free(qp); | |||
1687 | return NULL((void*)0); | |||
1688 | } | |||
1689 | ||||
1690 | __isl_give isl_qpolynomial *isl_qpolynomial_mul(__isl_take isl_qpolynomial *qp1, | |||
1691 | __isl_take isl_qpolynomial *qp2) | |||
1692 | { | |||
1693 | isl_bool compatible; | |||
1694 | ||||
1695 | qp1 = isl_qpolynomial_cow(qp1); | |||
1696 | ||||
1697 | if (!qp1 || !qp2) | |||
1698 | goto error; | |||
1699 | ||||
1700 | if (qp1->div->n_row < qp2->div->n_row) | |||
1701 | return isl_qpolynomial_mul(qp2, qp1); | |||
1702 | ||||
1703 | isl_assert(qp1->dim->ctx, isl_space_is_equal(qp1->dim, qp2->dim), goto error)do { if (isl_space_is_equal(qp1->dim, qp2->dim)) break; do { isl_handle_error(qp1->dim->ctx, isl_error_unknown , "Assertion \"" "isl_space_is_equal(qp1->dim, qp2->dim)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 1703); goto error; } while (0); } while (0); | |||
1704 | compatible = compatible_divs(qp1->div, qp2->div); | |||
1705 | if (compatible < 0) | |||
1706 | goto error; | |||
1707 | if (!compatible) | |||
1708 | return with_merged_divs(isl_qpolynomial_mul, qp1, qp2); | |||
1709 | ||||
1710 | qp1->upoly = isl_upoly_mul(qp1->upoly, isl_upoly_copy(qp2->upoly)); | |||
1711 | if (!qp1->upoly) | |||
1712 | goto error; | |||
1713 | ||||
1714 | isl_qpolynomial_free(qp2); | |||
1715 | ||||
1716 | return qp1; | |||
1717 | error: | |||
1718 | isl_qpolynomial_free(qp1); | |||
1719 | isl_qpolynomial_free(qp2); | |||
1720 | return NULL((void*)0); | |||
1721 | } | |||
1722 | ||||
1723 | __isl_give isl_qpolynomial *isl_qpolynomial_pow(__isl_take isl_qpolynomial *qp, | |||
1724 | unsigned power) | |||
1725 | { | |||
1726 | qp = isl_qpolynomial_cow(qp); | |||
1727 | ||||
1728 | if (!qp) | |||
1729 | return NULL((void*)0); | |||
1730 | ||||
1731 | qp->upoly = isl_upoly_pow(qp->upoly, power); | |||
1732 | if (!qp->upoly) | |||
1733 | goto error; | |||
1734 | ||||
1735 | return qp; | |||
1736 | error: | |||
1737 | isl_qpolynomial_free(qp); | |||
1738 | return NULL((void*)0); | |||
1739 | } | |||
1740 | ||||
1741 | __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_pow( | |||
1742 | __isl_take isl_pw_qpolynomial *pwqp, unsigned power) | |||
1743 | { | |||
1744 | int i; | |||
1745 | ||||
1746 | if (power == 1) | |||
1747 | return pwqp; | |||
1748 | ||||
1749 | pwqp = isl_pw_qpolynomial_cow(pwqp); | |||
1750 | if (!pwqp) | |||
1751 | return NULL((void*)0); | |||
1752 | ||||
1753 | for (i = 0; i < pwqp->n; ++i) { | |||
1754 | pwqp->p[i].qp = isl_qpolynomial_pow(pwqp->p[i].qp, power); | |||
1755 | if (!pwqp->p[i].qp) | |||
1756 | return isl_pw_qpolynomial_free(pwqp); | |||
1757 | } | |||
1758 | ||||
1759 | return pwqp; | |||
1760 | } | |||
1761 | ||||
1762 | __isl_give isl_qpolynomial *isl_qpolynomial_zero_on_domain( | |||
1763 | __isl_take isl_space *dim) | |||
1764 | { | |||
1765 | if (!dim) | |||
1766 | return NULL((void*)0); | |||
1767 | return isl_qpolynomial_alloc(dim, 0, isl_upoly_zero(dim->ctx)); | |||
1768 | } | |||
1769 | ||||
1770 | __isl_give isl_qpolynomial *isl_qpolynomial_one_on_domain( | |||
1771 | __isl_take isl_space *dim) | |||
1772 | { | |||
1773 | if (!dim) | |||
1774 | return NULL((void*)0); | |||
1775 | return isl_qpolynomial_alloc(dim, 0, isl_upoly_one(dim->ctx)); | |||
1776 | } | |||
1777 | ||||
1778 | __isl_give isl_qpolynomial *isl_qpolynomial_infty_on_domain( | |||
1779 | __isl_take isl_space *dim) | |||
1780 | { | |||
1781 | if (!dim) | |||
1782 | return NULL((void*)0); | |||
1783 | return isl_qpolynomial_alloc(dim, 0, isl_upoly_infty(dim->ctx)); | |||
1784 | } | |||
1785 | ||||
1786 | __isl_give isl_qpolynomial *isl_qpolynomial_neginfty_on_domain( | |||
1787 | __isl_take isl_space *dim) | |||
1788 | { | |||
1789 | if (!dim) | |||
1790 | return NULL((void*)0); | |||
1791 | return isl_qpolynomial_alloc(dim, 0, isl_upoly_neginfty(dim->ctx)); | |||
1792 | } | |||
1793 | ||||
1794 | __isl_give isl_qpolynomial *isl_qpolynomial_nan_on_domain( | |||
1795 | __isl_take isl_space *dim) | |||
1796 | { | |||
1797 | if (!dim) | |||
1798 | return NULL((void*)0); | |||
1799 | return isl_qpolynomial_alloc(dim, 0, isl_upoly_nan(dim->ctx)); | |||
1800 | } | |||
1801 | ||||
1802 | __isl_give isl_qpolynomial *isl_qpolynomial_cst_on_domain( | |||
1803 | __isl_take isl_space *dim, | |||
1804 | isl_int v) | |||
1805 | { | |||
1806 | struct isl_qpolynomial *qp; | |||
1807 | struct isl_upoly_cst *cst; | |||
1808 | ||||
1809 | if (!dim) | |||
1810 | return NULL((void*)0); | |||
1811 | ||||
1812 | qp = isl_qpolynomial_alloc(dim, 0, isl_upoly_zero(dim->ctx)); | |||
1813 | if (!qp) | |||
1814 | return NULL((void*)0); | |||
1815 | ||||
1816 | cst = isl_upoly_as_cst(qp->upoly); | |||
1817 | isl_int_set(cst->n, v)isl_sioimath_set((cst->n), *(v)); | |||
1818 | ||||
1819 | return qp; | |||
1820 | } | |||
1821 | ||||
1822 | int isl_qpolynomial_is_cst(__isl_keep isl_qpolynomial *qp, | |||
1823 | isl_int *n, isl_int *d) | |||
1824 | { | |||
1825 | struct isl_upoly_cst *cst; | |||
1826 | ||||
1827 | if (!qp) | |||
1828 | return -1; | |||
1829 | ||||
1830 | if (!isl_upoly_is_cst(qp->upoly)) | |||
1831 | return 0; | |||
1832 | ||||
1833 | cst = isl_upoly_as_cst(qp->upoly); | |||
1834 | if (!cst) | |||
1835 | return -1; | |||
1836 | ||||
1837 | if (n) | |||
1838 | isl_int_set(*n, cst->n)isl_sioimath_set((*n), *(cst->n)); | |||
1839 | if (d) | |||
1840 | isl_int_set(*d, cst->d)isl_sioimath_set((*d), *(cst->d)); | |||
1841 | ||||
1842 | return 1; | |||
1843 | } | |||
1844 | ||||
1845 | /* Return the constant term of "up". | |||
1846 | */ | |||
1847 | static __isl_give isl_val *isl_upoly_get_constant_val( | |||
1848 | __isl_keep struct isl_upoly *up) | |||
1849 | { | |||
1850 | struct isl_upoly_cst *cst; | |||
1851 | ||||
1852 | if (!up) | |||
1853 | return NULL((void*)0); | |||
1854 | ||||
1855 | while (!isl_upoly_is_cst(up)) { | |||
1856 | struct isl_upoly_rec *rec; | |||
1857 | ||||
1858 | rec = isl_upoly_as_rec(up); | |||
1859 | if (!rec) | |||
1860 | return NULL((void*)0); | |||
1861 | up = rec->p[0]; | |||
1862 | } | |||
1863 | ||||
1864 | cst = isl_upoly_as_cst(up); | |||
1865 | if (!cst) | |||
1866 | return NULL((void*)0); | |||
1867 | return isl_val_rat_from_isl_int(cst->up.ctx, cst->n, cst->d); | |||
1868 | } | |||
1869 | ||||
1870 | /* Return the constant term of "qp". | |||
1871 | */ | |||
1872 | __isl_give isl_val *isl_qpolynomial_get_constant_val( | |||
1873 | __isl_keep isl_qpolynomial *qp) | |||
1874 | { | |||
1875 | if (!qp) | |||
1876 | return NULL((void*)0); | |||
1877 | ||||
1878 | return isl_upoly_get_constant_val(qp->upoly); | |||
1879 | } | |||
1880 | ||||
1881 | int isl_upoly_is_affine(__isl_keep struct isl_upoly *up) | |||
1882 | { | |||
1883 | int is_cst; | |||
1884 | struct isl_upoly_rec *rec; | |||
1885 | ||||
1886 | if (!up) | |||
1887 | return -1; | |||
1888 | ||||
1889 | if (up->var < 0) | |||
1890 | return 1; | |||
1891 | ||||
1892 | rec = isl_upoly_as_rec(up); | |||
1893 | if (!rec) | |||
1894 | return -1; | |||
1895 | ||||
1896 | if (rec->n > 2) | |||
1897 | return 0; | |||
1898 | ||||
1899 | isl_assert(up->ctx, rec->n > 1, return -1)do { if (rec->n > 1) break; do { isl_handle_error(up-> ctx, isl_error_unknown, "Assertion \"" "rec->n > 1" "\" failed" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 1899); return -1; } while (0); } while (0); | |||
1900 | ||||
1901 | is_cst = isl_upoly_is_cst(rec->p[1]); | |||
1902 | if (is_cst < 0) | |||
1903 | return -1; | |||
1904 | if (!is_cst) | |||
1905 | return 0; | |||
1906 | ||||
1907 | return isl_upoly_is_affine(rec->p[0]); | |||
1908 | } | |||
1909 | ||||
1910 | int isl_qpolynomial_is_affine(__isl_keep isl_qpolynomial *qp) | |||
1911 | { | |||
1912 | if (!qp) | |||
1913 | return -1; | |||
1914 | ||||
1915 | if (qp->div->n_row > 0) | |||
1916 | return 0; | |||
1917 | ||||
1918 | return isl_upoly_is_affine(qp->upoly); | |||
1919 | } | |||
1920 | ||||
1921 | static void update_coeff(__isl_keep isl_vec *aff, | |||
1922 | __isl_keep struct isl_upoly_cst *cst, int pos) | |||
1923 | { | |||
1924 | isl_int gcd; | |||
1925 | isl_int f; | |||
1926 | ||||
1927 | if (isl_int_is_zero(cst->n)(isl_sioimath_sgn(*(cst->n)) == 0)) | |||
1928 | return; | |||
1929 | ||||
1930 | isl_int_init(gcd)isl_sioimath_init((gcd)); | |||
1931 | isl_int_init(f)isl_sioimath_init((f)); | |||
1932 | isl_int_gcd(gcd, cst->d, aff->el[0])isl_sioimath_gcd((gcd), *(cst->d), *(aff->el[0])); | |||
1933 | isl_int_divexact(f, cst->d, gcd)isl_sioimath_tdiv_q((f), *(cst->d), *(gcd)); | |||
1934 | isl_int_divexact(gcd, aff->el[0], gcd)isl_sioimath_tdiv_q((gcd), *(aff->el[0]), *(gcd)); | |||
1935 | isl_seq_scale(aff->el, aff->el, f, aff->size); | |||
1936 | isl_int_mul(aff->el[1 + pos], gcd, cst->n)isl_sioimath_mul((aff->el[1 + pos]), *(gcd), *(cst->n)); | |||
1937 | isl_int_clear(gcd)isl_sioimath_clear((gcd)); | |||
1938 | isl_int_clear(f)isl_sioimath_clear((f)); | |||
1939 | } | |||
1940 | ||||
1941 | int isl_upoly_update_affine(__isl_keep struct isl_upoly *up, | |||
1942 | __isl_keep isl_vec *aff) | |||
1943 | { | |||
1944 | struct isl_upoly_cst *cst; | |||
1945 | struct isl_upoly_rec *rec; | |||
1946 | ||||
1947 | if (!up || !aff) | |||
1948 | return -1; | |||
1949 | ||||
1950 | if (up->var < 0) { | |||
1951 | struct isl_upoly_cst *cst; | |||
1952 | ||||
1953 | cst = isl_upoly_as_cst(up); | |||
1954 | if (!cst) | |||
1955 | return -1; | |||
1956 | update_coeff(aff, cst, 0); | |||
1957 | return 0; | |||
1958 | } | |||
1959 | ||||
1960 | rec = isl_upoly_as_rec(up); | |||
1961 | if (!rec) | |||
1962 | return -1; | |||
1963 | isl_assert(up->ctx, rec->n == 2, return -1)do { if (rec->n == 2) break; do { isl_handle_error(up-> ctx, isl_error_unknown, "Assertion \"" "rec->n == 2" "\" failed" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 1963); return -1; } while (0); } while (0); | |||
1964 | ||||
1965 | cst = isl_upoly_as_cst(rec->p[1]); | |||
1966 | if (!cst) | |||
1967 | return -1; | |||
1968 | update_coeff(aff, cst, 1 + up->var); | |||
1969 | ||||
1970 | return isl_upoly_update_affine(rec->p[0], aff); | |||
1971 | } | |||
1972 | ||||
1973 | __isl_give isl_vec *isl_qpolynomial_extract_affine( | |||
1974 | __isl_keep isl_qpolynomial *qp) | |||
1975 | { | |||
1976 | isl_vec *aff; | |||
1977 | unsigned d; | |||
1978 | ||||
1979 | if (!qp) | |||
1980 | return NULL((void*)0); | |||
1981 | ||||
1982 | d = isl_space_dim(qp->dim, isl_dim_all); | |||
1983 | aff = isl_vec_alloc(qp->div->ctx, 2 + d + qp->div->n_row); | |||
1984 | if (!aff) | |||
1985 | return NULL((void*)0); | |||
1986 | ||||
1987 | isl_seq_clr(aff->el + 1, 1 + d + qp->div->n_row); | |||
1988 | isl_int_set_si(aff->el[0], 1)isl_sioimath_set_si((aff->el[0]), 1); | |||
1989 | ||||
1990 | if (isl_upoly_update_affine(qp->upoly, aff) < 0) | |||
1991 | goto error; | |||
1992 | ||||
1993 | return aff; | |||
1994 | error: | |||
1995 | isl_vec_free(aff); | |||
1996 | return NULL((void*)0); | |||
1997 | } | |||
1998 | ||||
1999 | /* Compare two quasi-polynomials. | |||
2000 | * | |||
2001 | * Return -1 if "qp1" is "smaller" than "qp2", 1 if "qp1" is "greater" | |||
2002 | * than "qp2" and 0 if they are equal. | |||
2003 | */ | |||
2004 | int isl_qpolynomial_plain_cmp(__isl_keep isl_qpolynomial *qp1, | |||
2005 | __isl_keep isl_qpolynomial *qp2) | |||
2006 | { | |||
2007 | int cmp; | |||
2008 | ||||
2009 | if (qp1 == qp2) | |||
2010 | return 0; | |||
2011 | if (!qp1) | |||
2012 | return -1; | |||
2013 | if (!qp2) | |||
2014 | return 1; | |||
2015 | ||||
2016 | cmp = isl_space_cmp(qp1->dim, qp2->dim); | |||
2017 | if (cmp != 0) | |||
2018 | return cmp; | |||
2019 | ||||
2020 | cmp = isl_local_cmp(qp1->div, qp2->div); | |||
2021 | if (cmp != 0) | |||
2022 | return cmp; | |||
2023 | ||||
2024 | return isl_upoly_plain_cmp(qp1->upoly, qp2->upoly); | |||
2025 | } | |||
2026 | ||||
2027 | /* Is "qp1" obviously equal to "qp2"? | |||
2028 | * | |||
2029 | * NaN is not equal to anything, not even to another NaN. | |||
2030 | */ | |||
2031 | isl_bool isl_qpolynomial_plain_is_equal(__isl_keep isl_qpolynomial *qp1, | |||
2032 | __isl_keep isl_qpolynomial *qp2) | |||
2033 | { | |||
2034 | isl_bool equal; | |||
2035 | ||||
2036 | if (!qp1 || !qp2) | |||
2037 | return isl_bool_error; | |||
2038 | ||||
2039 | if (isl_qpolynomial_is_nan(qp1) || isl_qpolynomial_is_nan(qp2)) | |||
2040 | return isl_bool_false; | |||
2041 | ||||
2042 | equal = isl_space_is_equal(qp1->dim, qp2->dim); | |||
2043 | if (equal < 0 || !equal) | |||
2044 | return equal; | |||
2045 | ||||
2046 | equal = isl_mat_is_equal(qp1->div, qp2->div); | |||
2047 | if (equal < 0 || !equal) | |||
2048 | return equal; | |||
2049 | ||||
2050 | return isl_upoly_is_equal(qp1->upoly, qp2->upoly); | |||
2051 | } | |||
2052 | ||||
2053 | static void upoly_update_den(__isl_keep struct isl_upoly *up, isl_int *d) | |||
2054 | { | |||
2055 | int i; | |||
2056 | struct isl_upoly_rec *rec; | |||
2057 | ||||
2058 | if (isl_upoly_is_cst(up)) { | |||
2059 | struct isl_upoly_cst *cst; | |||
2060 | cst = isl_upoly_as_cst(up); | |||
2061 | if (!cst) | |||
2062 | return; | |||
2063 | isl_int_lcm(*d, *d, cst->d)isl_sioimath_lcm((*d), *(*d), *(cst->d)); | |||
2064 | return; | |||
2065 | } | |||
2066 | ||||
2067 | rec = isl_upoly_as_rec(up); | |||
2068 | if (!rec) | |||
2069 | return; | |||
2070 | ||||
2071 | for (i = 0; i < rec->n; ++i) | |||
2072 | upoly_update_den(rec->p[i], d); | |||
2073 | } | |||
2074 | ||||
2075 | void isl_qpolynomial_get_den(__isl_keep isl_qpolynomial *qp, isl_int *d) | |||
2076 | { | |||
2077 | isl_int_set_si(*d, 1)isl_sioimath_set_si((*d), 1); | |||
2078 | if (!qp) | |||
2079 | return; | |||
2080 | upoly_update_den(qp->upoly, d); | |||
2081 | } | |||
2082 | ||||
2083 | __isl_give isl_qpolynomial *isl_qpolynomial_var_pow_on_domain( | |||
2084 | __isl_take isl_space *dim, int pos, int power) | |||
2085 | { | |||
2086 | struct isl_ctx *ctx; | |||
2087 | ||||
2088 | if (!dim) | |||
2089 | return NULL((void*)0); | |||
2090 | ||||
2091 | ctx = dim->ctx; | |||
2092 | ||||
2093 | return isl_qpolynomial_alloc(dim, 0, isl_upoly_var_pow(ctx, pos, power)); | |||
2094 | } | |||
2095 | ||||
2096 | __isl_give isl_qpolynomial *isl_qpolynomial_var_on_domain(__isl_take isl_space *dim, | |||
2097 | enum isl_dim_type type, unsigned pos) | |||
2098 | { | |||
2099 | if (!dim) | |||
2100 | return NULL((void*)0); | |||
2101 | ||||
2102 | isl_assert(dim->ctx, isl_space_dim(dim, isl_dim_in) == 0, goto error)do { if (isl_space_dim(dim, isl_dim_in) == 0) break; do { isl_handle_error (dim->ctx, isl_error_unknown, "Assertion \"" "isl_space_dim(dim, isl_dim_in) == 0" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2102); goto error; } while (0); } while (0); | |||
2103 | isl_assert(dim->ctx, pos < isl_space_dim(dim, type), goto error)do { if (pos < isl_space_dim(dim, type)) break; do { isl_handle_error (dim->ctx, isl_error_unknown, "Assertion \"" "pos < isl_space_dim(dim, type)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2103); goto error; } while (0); } while (0); | |||
2104 | ||||
2105 | if (type == isl_dim_set) | |||
2106 | pos += isl_space_dim(dim, isl_dim_param); | |||
2107 | ||||
2108 | return isl_qpolynomial_var_pow_on_domain(dim, pos, 1); | |||
2109 | error: | |||
2110 | isl_space_free(dim); | |||
2111 | return NULL((void*)0); | |||
2112 | } | |||
2113 | ||||
2114 | __isl_give struct isl_upoly *isl_upoly_subs(__isl_take struct isl_upoly *up, | |||
2115 | unsigned first, unsigned n, __isl_keep struct isl_upoly **subs) | |||
2116 | { | |||
2117 | int i; | |||
2118 | struct isl_upoly_rec *rec; | |||
2119 | struct isl_upoly *base, *res; | |||
2120 | ||||
2121 | if (!up) | |||
2122 | return NULL((void*)0); | |||
2123 | ||||
2124 | if (isl_upoly_is_cst(up)) | |||
2125 | return up; | |||
2126 | ||||
2127 | if (up->var < first) | |||
2128 | return up; | |||
2129 | ||||
2130 | rec = isl_upoly_as_rec(up); | |||
2131 | if (!rec) | |||
2132 | goto error; | |||
2133 | ||||
2134 | isl_assert(up->ctx, rec->n >= 1, goto error)do { if (rec->n >= 1) break; do { isl_handle_error(up-> ctx, isl_error_unknown, "Assertion \"" "rec->n >= 1" "\" failed" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2134); goto error; } while (0); } while (0); | |||
2135 | ||||
2136 | if (up->var >= first + n) | |||
2137 | base = isl_upoly_var_pow(up->ctx, up->var, 1); | |||
2138 | else | |||
2139 | base = isl_upoly_copy(subs[up->var - first]); | |||
2140 | ||||
2141 | res = isl_upoly_subs(isl_upoly_copy(rec->p[rec->n - 1]), first, n, subs); | |||
2142 | for (i = rec->n - 2; i >= 0; --i) { | |||
2143 | struct isl_upoly *t; | |||
2144 | t = isl_upoly_subs(isl_upoly_copy(rec->p[i]), first, n, subs); | |||
2145 | res = isl_upoly_mul(res, isl_upoly_copy(base)); | |||
2146 | res = isl_upoly_sum(res, t); | |||
2147 | } | |||
2148 | ||||
2149 | isl_upoly_free(base); | |||
2150 | isl_upoly_free(up); | |||
2151 | ||||
2152 | return res; | |||
2153 | error: | |||
2154 | isl_upoly_free(up); | |||
2155 | return NULL((void*)0); | |||
2156 | } | |||
2157 | ||||
2158 | __isl_give struct isl_upoly *isl_upoly_from_affine(isl_ctx *ctx, isl_int *f, | |||
2159 | isl_int denom, unsigned len) | |||
2160 | { | |||
2161 | int i; | |||
2162 | struct isl_upoly *up; | |||
2163 | ||||
2164 | isl_assert(ctx, len >= 1, return NULL)do { if (len >= 1) break; do { isl_handle_error(ctx, isl_error_unknown , "Assertion \"" "len >= 1" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2164); return ((void*)0); } while (0); } while (0); | |||
2165 | ||||
2166 | up = isl_upoly_rat_cst(ctx, f[0], denom); | |||
2167 | for (i = 0; i < len - 1; ++i) { | |||
2168 | struct isl_upoly *t; | |||
2169 | struct isl_upoly *c; | |||
2170 | ||||
2171 | if (isl_int_is_zero(f[1 + i])(isl_sioimath_sgn(*(f[1 + i])) == 0)) | |||
2172 | continue; | |||
2173 | ||||
2174 | c = isl_upoly_rat_cst(ctx, f[1 + i], denom); | |||
2175 | t = isl_upoly_var_pow(ctx, i, 1); | |||
2176 | t = isl_upoly_mul(c, t); | |||
2177 | up = isl_upoly_sum(up, t); | |||
2178 | } | |||
2179 | ||||
2180 | return up; | |||
2181 | } | |||
2182 | ||||
2183 | /* Remove common factor of non-constant terms and denominator. | |||
2184 | */ | |||
2185 | static void normalize_div(__isl_keep isl_qpolynomial *qp, int div) | |||
2186 | { | |||
2187 | isl_ctx *ctx = qp->div->ctx; | |||
2188 | unsigned total = qp->div->n_col - 2; | |||
2189 | ||||
2190 | isl_seq_gcd(qp->div->row[div] + 2, total, &ctx->normalize_gcd); | |||
2191 | isl_int_gcd(ctx->normalize_gcd,isl_sioimath_gcd((ctx->normalize_gcd), *(ctx->normalize_gcd ), *(qp->div->row[div][0])) | |||
2192 | ctx->normalize_gcd, qp->div->row[div][0])isl_sioimath_gcd((ctx->normalize_gcd), *(ctx->normalize_gcd ), *(qp->div->row[div][0])); | |||
2193 | if (isl_int_is_one(ctx->normalize_gcd)(isl_sioimath_cmp_si(*(ctx->normalize_gcd), 1) == 0)) | |||
2194 | return; | |||
2195 | ||||
2196 | isl_seq_scale_down(qp->div->row[div] + 2, qp->div->row[div] + 2, | |||
2197 | ctx->normalize_gcd, total); | |||
2198 | isl_int_divexact(qp->div->row[div][0], qp->div->row[div][0],isl_sioimath_tdiv_q((qp->div->row[div][0]), *(qp->div ->row[div][0]), *(ctx->normalize_gcd)) | |||
2199 | ctx->normalize_gcd)isl_sioimath_tdiv_q((qp->div->row[div][0]), *(qp->div ->row[div][0]), *(ctx->normalize_gcd)); | |||
2200 | isl_int_fdiv_q(qp->div->row[div][1], qp->div->row[div][1],isl_sioimath_fdiv_q((qp->div->row[div][1]), *(qp->div ->row[div][1]), *(ctx->normalize_gcd)) | |||
2201 | ctx->normalize_gcd)isl_sioimath_fdiv_q((qp->div->row[div][1]), *(qp->div ->row[div][1]), *(ctx->normalize_gcd)); | |||
2202 | } | |||
2203 | ||||
2204 | /* Replace the integer division identified by "div" by the polynomial "s". | |||
2205 | * The integer division is assumed not to appear in the definition | |||
2206 | * of any other integer divisions. | |||
2207 | */ | |||
2208 | static __isl_give isl_qpolynomial *substitute_div( | |||
2209 | __isl_take isl_qpolynomial *qp, | |||
2210 | int div, __isl_take struct isl_upoly *s) | |||
2211 | { | |||
2212 | int i; | |||
2213 | int total; | |||
2214 | int *reordering; | |||
2215 | ||||
2216 | if (!qp || !s) | |||
2217 | goto error; | |||
2218 | ||||
2219 | qp = isl_qpolynomial_cow(qp); | |||
2220 | if (!qp) | |||
2221 | goto error; | |||
2222 | ||||
2223 | total = isl_space_dim(qp->dim, isl_dim_all); | |||
2224 | qp->upoly = isl_upoly_subs(qp->upoly, total + div, 1, &s); | |||
2225 | if (!qp->upoly) | |||
2226 | goto error; | |||
2227 | ||||
2228 | reordering = isl_alloc_array(qp->dim->ctx, int, total + qp->div->n_row)((int *)isl_malloc_or_die(qp->dim->ctx, (total + qp-> div->n_row)*sizeof(int))); | |||
2229 | if (!reordering) | |||
2230 | goto error; | |||
2231 | for (i = 0; i < total + div; ++i) | |||
2232 | reordering[i] = i; | |||
2233 | for (i = total + div + 1; i < total + qp->div->n_row; ++i) | |||
2234 | reordering[i] = i - 1; | |||
2235 | qp->div = isl_mat_drop_rows(qp->div, div, 1); | |||
2236 | qp->div = isl_mat_drop_cols(qp->div, 2 + total + div, 1); | |||
2237 | qp->upoly = reorder(qp->upoly, reordering); | |||
2238 | free(reordering); | |||
2239 | ||||
2240 | if (!qp->upoly || !qp->div) | |||
2241 | goto error; | |||
2242 | ||||
2243 | isl_upoly_free(s); | |||
2244 | return qp; | |||
2245 | error: | |||
2246 | isl_qpolynomial_free(qp); | |||
2247 | isl_upoly_free(s); | |||
2248 | return NULL((void*)0); | |||
2249 | } | |||
2250 | ||||
2251 | /* Replace all integer divisions [e/d] that turn out to not actually be integer | |||
2252 | * divisions because d is equal to 1 by their definition, i.e., e. | |||
2253 | */ | |||
2254 | static __isl_give isl_qpolynomial *substitute_non_divs( | |||
2255 | __isl_take isl_qpolynomial *qp) | |||
2256 | { | |||
2257 | int i, j; | |||
2258 | int total; | |||
2259 | struct isl_upoly *s; | |||
2260 | ||||
2261 | if (!qp) | |||
2262 | return NULL((void*)0); | |||
2263 | ||||
2264 | total = isl_space_dim(qp->dim, isl_dim_all); | |||
2265 | for (i = 0; qp && i < qp->div->n_row; ++i) { | |||
2266 | if (!isl_int_is_one(qp->div->row[i][0])(isl_sioimath_cmp_si(*(qp->div->row[i][0]), 1) == 0)) | |||
2267 | continue; | |||
2268 | for (j = i + 1; j < qp->div->n_row; ++j) { | |||
2269 | if (isl_int_is_zero(qp->div->row[j][2 + total + i])(isl_sioimath_sgn(*(qp->div->row[j][2 + total + i])) == 0)) | |||
2270 | continue; | |||
2271 | isl_seq_combine(qp->div->row[j] + 1, | |||
2272 | qp->div->ctx->one, qp->div->row[j] + 1, | |||
2273 | qp->div->row[j][2 + total + i], | |||
2274 | qp->div->row[i] + 1, 1 + total + i); | |||
2275 | isl_int_set_si(qp->div->row[j][2 + total + i], 0)isl_sioimath_set_si((qp->div->row[j][2 + total + i]), 0 ); | |||
2276 | normalize_div(qp, j); | |||
2277 | } | |||
2278 | s = isl_upoly_from_affine(qp->dim->ctx, qp->div->row[i] + 1, | |||
2279 | qp->div->row[i][0], qp->div->n_col - 1); | |||
2280 | qp = substitute_div(qp, i, s); | |||
2281 | --i; | |||
2282 | } | |||
2283 | ||||
2284 | return qp; | |||
2285 | } | |||
2286 | ||||
2287 | /* Reduce the coefficients of div "div" to lie in the interval [0, d-1], | |||
2288 | * with d the denominator. When replacing the coefficient e of x by | |||
2289 | * d * frac(e/d) = e - d * floor(e/d), we are subtracting d * floor(e/d) * x | |||
2290 | * inside the division, so we need to add floor(e/d) * x outside. | |||
2291 | * That is, we replace q by q' + floor(e/d) * x and we therefore need | |||
2292 | * to adjust the coefficient of x in each later div that depends on the | |||
2293 | * current div "div" and also in the affine expressions in the rows of "mat" | |||
2294 | * (if they too depend on "div"). | |||
2295 | */ | |||
2296 | static void reduce_div(__isl_keep isl_qpolynomial *qp, int div, | |||
2297 | __isl_keep isl_mat **mat) | |||
2298 | { | |||
2299 | int i, j; | |||
2300 | isl_int v; | |||
2301 | unsigned total = qp->div->n_col - qp->div->n_row - 2; | |||
2302 | ||||
2303 | isl_int_init(v)isl_sioimath_init((v)); | |||
2304 | for (i = 0; i < 1 + total + div; ++i) { | |||
2305 | if (isl_int_is_nonneg(qp->div->row[div][1 + i])(isl_sioimath_sgn(*(qp->div->row[div][1 + i])) >= 0) && | |||
2306 | isl_int_lt(qp->div->row[div][1 + i], qp->div->row[div][0])(isl_sioimath_cmp(*(qp->div->row[div][1 + i]), *(qp-> div->row[div][0])) < 0)) | |||
2307 | continue; | |||
2308 | isl_int_fdiv_q(v, qp->div->row[div][1 + i], qp->div->row[div][0])isl_sioimath_fdiv_q((v), *(qp->div->row[div][1 + i]), * (qp->div->row[div][0])); | |||
2309 | isl_int_fdiv_r(qp->div->row[div][1 + i],isl_sioimath_fdiv_r((qp->div->row[div][1 + i]), *(qp-> div->row[div][1 + i]), *(qp->div->row[div][0])) | |||
2310 | qp->div->row[div][1 + i], qp->div->row[div][0])isl_sioimath_fdiv_r((qp->div->row[div][1 + i]), *(qp-> div->row[div][1 + i]), *(qp->div->row[div][0])); | |||
2311 | *mat = isl_mat_col_addmul(*mat, i, v, 1 + total + div); | |||
2312 | for (j = div + 1; j < qp->div->n_row; ++j) { | |||
2313 | if (isl_int_is_zero(qp->div->row[j][2 + total + div])(isl_sioimath_sgn(*(qp->div->row[j][2 + total + div])) == 0)) | |||
2314 | continue; | |||
2315 | isl_int_addmul(qp->div->row[j][1 + i],isl_sioimath_addmul((qp->div->row[j][1 + i]), *(v), *(qp ->div->row[j][2 + total + div])) | |||
2316 | v, qp->div->row[j][2 + total + div])isl_sioimath_addmul((qp->div->row[j][1 + i]), *(v), *(qp ->div->row[j][2 + total + div])); | |||
2317 | } | |||
2318 | } | |||
2319 | isl_int_clear(v)isl_sioimath_clear((v)); | |||
2320 | } | |||
2321 | ||||
2322 | /* Check if the last non-zero coefficient is bigger that half of the | |||
2323 | * denominator. If so, we will invert the div to further reduce the number | |||
2324 | * of distinct divs that may appear. | |||
2325 | * If the last non-zero coefficient is exactly half the denominator, | |||
2326 | * then we continue looking for earlier coefficients that are bigger | |||
2327 | * than half the denominator. | |||
2328 | */ | |||
2329 | static int needs_invert(__isl_keep isl_mat *div, int row) | |||
2330 | { | |||
2331 | int i; | |||
2332 | int cmp; | |||
2333 | ||||
2334 | for (i = div->n_col - 1; i >= 1; --i) { | |||
2335 | if (isl_int_is_zero(div->row[row][i])(isl_sioimath_sgn(*(div->row[row][i])) == 0)) | |||
2336 | continue; | |||
2337 | isl_int_mul_ui(div->row[row][i], div->row[row][i], 2)isl_sioimath_mul_ui((div->row[row][i]), *(div->row[row] [i]), 2); | |||
2338 | cmp = isl_int_cmp(div->row[row][i], div->row[row][0])isl_sioimath_cmp(*(div->row[row][i]), *(div->row[row][0 ])); | |||
2339 | isl_int_divexact_ui(div->row[row][i], div->row[row][i], 2)isl_sioimath_tdiv_q_ui((div->row[row][i]), *(div->row[row ][i]), 2); | |||
2340 | if (cmp) | |||
2341 | return cmp > 0; | |||
2342 | if (i == 1) | |||
2343 | return 1; | |||
2344 | } | |||
2345 | ||||
2346 | return 0; | |||
2347 | } | |||
2348 | ||||
2349 | /* Replace div "div" q = [e/d] by -[(-e+(d-1))/d]. | |||
2350 | * We only invert the coefficients of e (and the coefficient of q in | |||
2351 | * later divs and in the rows of "mat"). After calling this function, the | |||
2352 | * coefficients of e should be reduced again. | |||
2353 | */ | |||
2354 | static void invert_div(__isl_keep isl_qpolynomial *qp, int div, | |||
2355 | __isl_keep isl_mat **mat) | |||
2356 | { | |||
2357 | unsigned total = qp->div->n_col - qp->div->n_row - 2; | |||
2358 | ||||
2359 | isl_seq_neg(qp->div->row[div] + 1, | |||
2360 | qp->div->row[div] + 1, qp->div->n_col - 1); | |||
2361 | isl_int_sub_ui(qp->div->row[div][1], qp->div->row[div][1], 1)isl_sioimath_sub_ui((qp->div->row[div][1]), *(qp->div ->row[div][1]), 1); | |||
2362 | isl_int_add(qp->div->row[div][1],isl_sioimath_add((qp->div->row[div][1]), *(qp->div-> row[div][1]), *(qp->div->row[div][0])) | |||
2363 | qp->div->row[div][1], qp->div->row[div][0])isl_sioimath_add((qp->div->row[div][1]), *(qp->div-> row[div][1]), *(qp->div->row[div][0])); | |||
2364 | *mat = isl_mat_col_neg(*mat, 1 + total + div); | |||
2365 | isl_mat_col_mul(qp->div, 2 + total + div, | |||
2366 | qp->div->ctx->negone, 2 + total + div); | |||
2367 | } | |||
2368 | ||||
2369 | /* Reduce all divs of "qp" to have coefficients | |||
2370 | * in the interval [0, d-1], with d the denominator and such that the | |||
2371 | * last non-zero coefficient that is not equal to d/2 is smaller than d/2. | |||
2372 | * The modifications to the integer divisions need to be reflected | |||
2373 | * in the factors of the polynomial that refer to the original | |||
2374 | * integer divisions. To this end, the modifications are collected | |||
2375 | * as a set of affine expressions and then plugged into the polynomial. | |||
2376 | * | |||
2377 | * After the reduction, some divs may have become redundant or identical, | |||
2378 | * so we call substitute_non_divs and sort_divs. If these functions | |||
2379 | * eliminate divs or merge two or more divs into one, the coefficients | |||
2380 | * of the enclosing divs may have to be reduced again, so we call | |||
2381 | * ourselves recursively if the number of divs decreases. | |||
2382 | */ | |||
2383 | static __isl_give isl_qpolynomial *reduce_divs(__isl_take isl_qpolynomial *qp) | |||
2384 | { | |||
2385 | int i; | |||
2386 | isl_ctx *ctx; | |||
2387 | isl_mat *mat; | |||
2388 | struct isl_upoly **s; | |||
2389 | unsigned o_div, n_div, total; | |||
2390 | ||||
2391 | if (!qp) | |||
2392 | return NULL((void*)0); | |||
2393 | ||||
2394 | total = isl_qpolynomial_domain_dim(qp, isl_dim_all); | |||
2395 | n_div = isl_qpolynomial_domain_dim(qp, isl_dim_div); | |||
2396 | o_div = isl_qpolynomial_domain_offset(qp, isl_dim_div); | |||
2397 | ctx = isl_qpolynomial_get_ctx(qp); | |||
2398 | mat = isl_mat_zero(ctx, n_div, 1 + total); | |||
2399 | ||||
2400 | for (i = 0; i < n_div; ++i) | |||
2401 | mat = isl_mat_set_element_si(mat, i, o_div + i, 1); | |||
2402 | ||||
2403 | for (i = 0; i < qp->div->n_row; ++i) { | |||
2404 | normalize_div(qp, i); | |||
2405 | reduce_div(qp, i, &mat); | |||
2406 | if (needs_invert(qp->div, i)) { | |||
2407 | invert_div(qp, i, &mat); | |||
2408 | reduce_div(qp, i, &mat); | |||
2409 | } | |||
2410 | } | |||
2411 | if (!mat) | |||
2412 | goto error; | |||
2413 | ||||
2414 | s = isl_alloc_array(ctx, struct isl_upoly *, n_div)((struct isl_upoly * *)isl_malloc_or_die(ctx, (n_div)*sizeof( struct isl_upoly *))); | |||
2415 | if (n_div && !s) | |||
2416 | goto error; | |||
2417 | for (i = 0; i < n_div; ++i) | |||
2418 | s[i] = isl_upoly_from_affine(ctx, mat->row[i], ctx->one, | |||
2419 | 1 + total); | |||
2420 | qp->upoly = isl_upoly_subs(qp->upoly, o_div - 1, n_div, s); | |||
2421 | for (i = 0; i < n_div; ++i) | |||
2422 | isl_upoly_free(s[i]); | |||
2423 | free(s); | |||
2424 | if (!qp->upoly) | |||
2425 | goto error; | |||
2426 | ||||
2427 | isl_mat_free(mat); | |||
2428 | ||||
2429 | qp = substitute_non_divs(qp); | |||
2430 | qp = sort_divs(qp); | |||
2431 | if (qp && isl_qpolynomial_domain_dim(qp, isl_dim_div) < n_div) | |||
2432 | return reduce_divs(qp); | |||
2433 | ||||
2434 | return qp; | |||
2435 | error: | |||
2436 | isl_qpolynomial_free(qp); | |||
2437 | isl_mat_free(mat); | |||
2438 | return NULL((void*)0); | |||
2439 | } | |||
2440 | ||||
2441 | __isl_give isl_qpolynomial *isl_qpolynomial_rat_cst_on_domain( | |||
2442 | __isl_take isl_space *dim, const isl_int n, const isl_int d) | |||
2443 | { | |||
2444 | struct isl_qpolynomial *qp; | |||
2445 | struct isl_upoly_cst *cst; | |||
2446 | ||||
2447 | if (!dim) | |||
2448 | return NULL((void*)0); | |||
2449 | ||||
2450 | qp = isl_qpolynomial_alloc(dim, 0, isl_upoly_zero(dim->ctx)); | |||
2451 | if (!qp) | |||
2452 | return NULL((void*)0); | |||
2453 | ||||
2454 | cst = isl_upoly_as_cst(qp->upoly); | |||
2455 | isl_int_set(cst->n, n)isl_sioimath_set((cst->n), *(n)); | |||
2456 | isl_int_set(cst->d, d)isl_sioimath_set((cst->d), *(d)); | |||
2457 | ||||
2458 | return qp; | |||
2459 | } | |||
2460 | ||||
2461 | /* Return an isl_qpolynomial that is equal to "val" on domain space "domain". | |||
2462 | */ | |||
2463 | __isl_give isl_qpolynomial *isl_qpolynomial_val_on_domain( | |||
2464 | __isl_take isl_space *domain, __isl_take isl_val *val) | |||
2465 | { | |||
2466 | isl_qpolynomial *qp; | |||
2467 | struct isl_upoly_cst *cst; | |||
2468 | ||||
2469 | if (!domain || !val) | |||
2470 | goto error; | |||
2471 | ||||
2472 | qp = isl_qpolynomial_alloc(isl_space_copy(domain), 0, | |||
2473 | isl_upoly_zero(domain->ctx)); | |||
2474 | if (!qp) | |||
2475 | goto error; | |||
2476 | ||||
2477 | cst = isl_upoly_as_cst(qp->upoly); | |||
2478 | isl_int_set(cst->n, val->n)isl_sioimath_set((cst->n), *(val->n)); | |||
2479 | isl_int_set(cst->d, val->d)isl_sioimath_set((cst->d), *(val->d)); | |||
2480 | ||||
2481 | isl_space_free(domain); | |||
2482 | isl_val_free(val); | |||
2483 | return qp; | |||
2484 | error: | |||
2485 | isl_space_free(domain); | |||
2486 | isl_val_free(val); | |||
2487 | return NULL((void*)0); | |||
2488 | } | |||
2489 | ||||
2490 | static int up_set_active(__isl_keep struct isl_upoly *up, int *active, int d) | |||
2491 | { | |||
2492 | struct isl_upoly_rec *rec; | |||
2493 | int i; | |||
2494 | ||||
2495 | if (!up) | |||
2496 | return -1; | |||
2497 | ||||
2498 | if (isl_upoly_is_cst(up)) | |||
2499 | return 0; | |||
2500 | ||||
2501 | if (up->var < d) | |||
2502 | active[up->var] = 1; | |||
2503 | ||||
2504 | rec = isl_upoly_as_rec(up); | |||
2505 | for (i = 0; i < rec->n; ++i) | |||
2506 | if (up_set_active(rec->p[i], active, d) < 0) | |||
2507 | return -1; | |||
2508 | ||||
2509 | return 0; | |||
2510 | } | |||
2511 | ||||
2512 | static int set_active(__isl_keep isl_qpolynomial *qp, int *active) | |||
2513 | { | |||
2514 | int i, j; | |||
2515 | int d = isl_space_dim(qp->dim, isl_dim_all); | |||
2516 | ||||
2517 | if (!qp || !active) | |||
2518 | return -1; | |||
2519 | ||||
2520 | for (i = 0; i < d; ++i) | |||
2521 | for (j = 0; j < qp->div->n_row; ++j) { | |||
2522 | if (isl_int_is_zero(qp->div->row[j][2 + i])(isl_sioimath_sgn(*(qp->div->row[j][2 + i])) == 0)) | |||
2523 | continue; | |||
2524 | active[i] = 1; | |||
2525 | break; | |||
2526 | } | |||
2527 | ||||
2528 | return up_set_active(qp->upoly, active, d); | |||
2529 | } | |||
2530 | ||||
2531 | isl_bool isl_qpolynomial_involves_dims(__isl_keep isl_qpolynomial *qp, | |||
2532 | enum isl_dim_type type, unsigned first, unsigned n) | |||
2533 | { | |||
2534 | int i; | |||
2535 | int *active = NULL((void*)0); | |||
2536 | isl_bool involves = isl_bool_false; | |||
2537 | ||||
2538 | if (!qp) | |||
2539 | return isl_bool_error; | |||
2540 | if (n == 0) | |||
2541 | return isl_bool_false; | |||
2542 | ||||
2543 | isl_assert(qp->dim->ctx,do { if (first + n <= isl_qpolynomial_dim(qp, type)) break ; do { isl_handle_error(qp->dim->ctx, isl_error_unknown , "Assertion \"" "first + n <= isl_qpolynomial_dim(qp, type)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2545); return isl_bool_error; } while (0); } while (0) | |||
2544 | first + n <= isl_qpolynomial_dim(qp, type),do { if (first + n <= isl_qpolynomial_dim(qp, type)) break ; do { isl_handle_error(qp->dim->ctx, isl_error_unknown , "Assertion \"" "first + n <= isl_qpolynomial_dim(qp, type)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2545); return isl_bool_error; } while (0); } while (0) | |||
2545 | return isl_bool_error)do { if (first + n <= isl_qpolynomial_dim(qp, type)) break ; do { isl_handle_error(qp->dim->ctx, isl_error_unknown , "Assertion \"" "first + n <= isl_qpolynomial_dim(qp, type)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2545); return isl_bool_error; } while (0); } while (0); | |||
2546 | isl_assert(qp->dim->ctx, type == isl_dim_param ||do { if (type == isl_dim_param || type == isl_dim_in) break; do { isl_handle_error(qp->dim->ctx, isl_error_unknown, "Assertion \"" "type == isl_dim_param || type == isl_dim_in" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2547); return isl_bool_error; } while (0); } while (0) | |||
2547 | type == isl_dim_in, return isl_bool_error)do { if (type == isl_dim_param || type == isl_dim_in) break; do { isl_handle_error(qp->dim->ctx, isl_error_unknown, "Assertion \"" "type == isl_dim_param || type == isl_dim_in" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2547); return isl_bool_error; } while (0); } while (0); | |||
2548 | ||||
2549 | active = isl_calloc_array(qp->dim->ctx, int,((int *)isl_calloc_or_die(qp->dim->ctx, isl_space_dim(qp ->dim, isl_dim_all), sizeof(int))) | |||
2550 | isl_space_dim(qp->dim, isl_dim_all))((int *)isl_calloc_or_die(qp->dim->ctx, isl_space_dim(qp ->dim, isl_dim_all), sizeof(int))); | |||
2551 | if (set_active(qp, active) < 0) | |||
2552 | goto error; | |||
2553 | ||||
2554 | if (type == isl_dim_in) | |||
2555 | first += isl_space_dim(qp->dim, isl_dim_param); | |||
2556 | for (i = 0; i < n; ++i) | |||
2557 | if (active[first + i]) { | |||
2558 | involves = isl_bool_true; | |||
2559 | break; | |||
2560 | } | |||
2561 | ||||
2562 | free(active); | |||
2563 | ||||
2564 | return involves; | |||
2565 | error: | |||
2566 | free(active); | |||
2567 | return isl_bool_error; | |||
2568 | } | |||
2569 | ||||
2570 | /* Remove divs that do not appear in the quasi-polynomial, nor in any | |||
2571 | * of the divs that do appear in the quasi-polynomial. | |||
2572 | */ | |||
2573 | static __isl_give isl_qpolynomial *remove_redundant_divs( | |||
2574 | __isl_take isl_qpolynomial *qp) | |||
2575 | { | |||
2576 | int i, j; | |||
2577 | int d; | |||
2578 | int len; | |||
2579 | int skip; | |||
2580 | int *active = NULL((void*)0); | |||
2581 | int *reordering = NULL((void*)0); | |||
2582 | int redundant = 0; | |||
2583 | int n_div; | |||
2584 | isl_ctx *ctx; | |||
2585 | ||||
2586 | if (!qp) | |||
2587 | return NULL((void*)0); | |||
2588 | if (qp->div->n_row == 0) | |||
2589 | return qp; | |||
2590 | ||||
2591 | d = isl_space_dim(qp->dim, isl_dim_all); | |||
2592 | len = qp->div->n_col - 2; | |||
2593 | ctx = isl_qpolynomial_get_ctx(qp); | |||
2594 | active = isl_calloc_array(ctx, int, len)((int *)isl_calloc_or_die(ctx, len, sizeof(int))); | |||
2595 | if (!active) | |||
2596 | goto error; | |||
2597 | ||||
2598 | if (up_set_active(qp->upoly, active, len) < 0) | |||
2599 | goto error; | |||
2600 | ||||
2601 | for (i = qp->div->n_row - 1; i >= 0; --i) { | |||
2602 | if (!active[d + i]) { | |||
2603 | redundant = 1; | |||
2604 | continue; | |||
2605 | } | |||
2606 | for (j = 0; j < i; ++j) { | |||
2607 | if (isl_int_is_zero(qp->div->row[i][2 + d + j])(isl_sioimath_sgn(*(qp->div->row[i][2 + d + j])) == 0)) | |||
2608 | continue; | |||
2609 | active[d + j] = 1; | |||
2610 | break; | |||
2611 | } | |||
2612 | } | |||
2613 | ||||
2614 | if (!redundant) { | |||
2615 | free(active); | |||
2616 | return qp; | |||
2617 | } | |||
2618 | ||||
2619 | reordering = isl_alloc_array(qp->div->ctx, int, len)((int *)isl_malloc_or_die(qp->div->ctx, (len)*sizeof(int ))); | |||
2620 | if (!reordering) | |||
2621 | goto error; | |||
2622 | ||||
2623 | for (i = 0; i < d; ++i) | |||
2624 | reordering[i] = i; | |||
2625 | ||||
2626 | skip = 0; | |||
2627 | n_div = qp->div->n_row; | |||
2628 | for (i = 0; i < n_div; ++i) { | |||
2629 | if (!active[d + i]) { | |||
2630 | qp->div = isl_mat_drop_rows(qp->div, i - skip, 1); | |||
2631 | qp->div = isl_mat_drop_cols(qp->div, | |||
2632 | 2 + d + i - skip, 1); | |||
2633 | skip++; | |||
2634 | } | |||
2635 | reordering[d + i] = d + i - skip; | |||
2636 | } | |||
2637 | ||||
2638 | qp->upoly = reorder(qp->upoly, reordering); | |||
2639 | ||||
2640 | if (!qp->upoly || !qp->div) | |||
2641 | goto error; | |||
2642 | ||||
2643 | free(active); | |||
2644 | free(reordering); | |||
2645 | ||||
2646 | return qp; | |||
2647 | error: | |||
2648 | free(active); | |||
2649 | free(reordering); | |||
2650 | isl_qpolynomial_free(qp); | |||
2651 | return NULL((void*)0); | |||
2652 | } | |||
2653 | ||||
2654 | __isl_give struct isl_upoly *isl_upoly_drop(__isl_take struct isl_upoly *up, | |||
2655 | unsigned first, unsigned n) | |||
2656 | { | |||
2657 | int i; | |||
2658 | struct isl_upoly_rec *rec; | |||
2659 | ||||
2660 | if (!up) | |||
2661 | return NULL((void*)0); | |||
2662 | if (n == 0 || up->var < 0 || up->var < first) | |||
2663 | return up; | |||
2664 | if (up->var < first + n) { | |||
2665 | up = replace_by_constant_term(up); | |||
2666 | return isl_upoly_drop(up, first, n); | |||
2667 | } | |||
2668 | up = isl_upoly_cow(up); | |||
2669 | if (!up) | |||
2670 | return NULL((void*)0); | |||
2671 | up->var -= n; | |||
2672 | rec = isl_upoly_as_rec(up); | |||
2673 | if (!rec) | |||
2674 | goto error; | |||
2675 | ||||
2676 | for (i = 0; i < rec->n; ++i) { | |||
2677 | rec->p[i] = isl_upoly_drop(rec->p[i], first, n); | |||
2678 | if (!rec->p[i]) | |||
2679 | goto error; | |||
2680 | } | |||
2681 | ||||
2682 | return up; | |||
2683 | error: | |||
2684 | isl_upoly_free(up); | |||
2685 | return NULL((void*)0); | |||
2686 | } | |||
2687 | ||||
2688 | __isl_give isl_qpolynomial *isl_qpolynomial_set_dim_name( | |||
2689 | __isl_take isl_qpolynomial *qp, | |||
2690 | enum isl_dim_type type, unsigned pos, const char *s) | |||
2691 | { | |||
2692 | qp = isl_qpolynomial_cow(qp); | |||
2693 | if (!qp) | |||
2694 | return NULL((void*)0); | |||
2695 | if (type == isl_dim_out) | |||
2696 | isl_die(isl_qpolynomial_get_ctx(qp), isl_error_invalid,do { isl_handle_error(isl_qpolynomial_get_ctx(qp), isl_error_invalid , "cannot set name of output/set dimension", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2698); return isl_qpolynomial_free(qp); } while (0) | |||
2697 | "cannot set name of output/set dimension",do { isl_handle_error(isl_qpolynomial_get_ctx(qp), isl_error_invalid , "cannot set name of output/set dimension", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2698); return isl_qpolynomial_free(qp); } while (0) | |||
2698 | return isl_qpolynomial_free(qp))do { isl_handle_error(isl_qpolynomial_get_ctx(qp), isl_error_invalid , "cannot set name of output/set dimension", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2698); return isl_qpolynomial_free(qp); } while (0); | |||
2699 | if (type == isl_dim_in) | |||
2700 | type = isl_dim_set; | |||
2701 | qp->dim = isl_space_set_dim_name(qp->dim, type, pos, s); | |||
2702 | if (!qp->dim) | |||
2703 | goto error; | |||
2704 | return qp; | |||
2705 | error: | |||
2706 | isl_qpolynomial_free(qp); | |||
2707 | return NULL((void*)0); | |||
2708 | } | |||
2709 | ||||
2710 | __isl_give isl_qpolynomial *isl_qpolynomial_drop_dims( | |||
2711 | __isl_take isl_qpolynomial *qp, | |||
2712 | enum isl_dim_type type, unsigned first, unsigned n) | |||
2713 | { | |||
2714 | if (!qp) | |||
2715 | return NULL((void*)0); | |||
2716 | if (type == isl_dim_out) | |||
2717 | isl_die(qp->dim->ctx, isl_error_invalid,do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "cannot drop output/set dimension" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2719); goto error; } while (0) | |||
2718 | "cannot drop output/set dimension",do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "cannot drop output/set dimension" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2719); goto error; } while (0) | |||
2719 | goto error)do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "cannot drop output/set dimension" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2719); goto error; } while (0); | |||
2720 | if (type == isl_dim_in) | |||
2721 | type = isl_dim_set; | |||
2722 | if (n == 0 && !isl_space_is_named_or_nested(qp->dim, type)) | |||
2723 | return qp; | |||
2724 | ||||
2725 | qp = isl_qpolynomial_cow(qp); | |||
2726 | if (!qp) | |||
2727 | return NULL((void*)0); | |||
2728 | ||||
2729 | isl_assert(qp->dim->ctx, first + n <= isl_space_dim(qp->dim, type),do { if (first + n <= isl_space_dim(qp->dim, type)) break ; do { isl_handle_error(qp->dim->ctx, isl_error_unknown , "Assertion \"" "first + n <= isl_space_dim(qp->dim, type)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2730); goto error; } while (0); } while (0) | |||
2730 | goto error)do { if (first + n <= isl_space_dim(qp->dim, type)) break ; do { isl_handle_error(qp->dim->ctx, isl_error_unknown , "Assertion \"" "first + n <= isl_space_dim(qp->dim, type)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2730); goto error; } while (0); } while (0); | |||
2731 | isl_assert(qp->dim->ctx, type == isl_dim_param ||do { if (type == isl_dim_param || type == isl_dim_set) break; do { isl_handle_error(qp->dim->ctx, isl_error_unknown, "Assertion \"" "type == isl_dim_param || type == isl_dim_set" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2732); goto error; } while (0); } while (0) | |||
2732 | type == isl_dim_set, goto error)do { if (type == isl_dim_param || type == isl_dim_set) break; do { isl_handle_error(qp->dim->ctx, isl_error_unknown, "Assertion \"" "type == isl_dim_param || type == isl_dim_set" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2732); goto error; } while (0); } while (0); | |||
2733 | ||||
2734 | qp->dim = isl_space_drop_dims(qp->dim, type, first, n); | |||
2735 | if (!qp->dim) | |||
2736 | goto error; | |||
2737 | ||||
2738 | if (type == isl_dim_set) | |||
2739 | first += isl_space_dim(qp->dim, isl_dim_param); | |||
2740 | ||||
2741 | qp->div = isl_mat_drop_cols(qp->div, 2 + first, n); | |||
2742 | if (!qp->div) | |||
2743 | goto error; | |||
2744 | ||||
2745 | qp->upoly = isl_upoly_drop(qp->upoly, first, n); | |||
2746 | if (!qp->upoly) | |||
2747 | goto error; | |||
2748 | ||||
2749 | return qp; | |||
2750 | error: | |||
2751 | isl_qpolynomial_free(qp); | |||
2752 | return NULL((void*)0); | |||
2753 | } | |||
2754 | ||||
2755 | /* Project the domain of the quasi-polynomial onto its parameter space. | |||
2756 | * The quasi-polynomial may not involve any of the domain dimensions. | |||
2757 | */ | |||
2758 | __isl_give isl_qpolynomial *isl_qpolynomial_project_domain_on_params( | |||
2759 | __isl_take isl_qpolynomial *qp) | |||
2760 | { | |||
2761 | isl_space *space; | |||
2762 | unsigned n; | |||
2763 | int involves; | |||
2764 | ||||
2765 | n = isl_qpolynomial_dim(qp, isl_dim_in); | |||
2766 | involves = isl_qpolynomial_involves_dims(qp, isl_dim_in, 0, n); | |||
2767 | if (involves < 0) | |||
2768 | return isl_qpolynomial_free(qp); | |||
2769 | if (involves) | |||
2770 | isl_die(isl_qpolynomial_get_ctx(qp), isl_error_invalid,do { isl_handle_error(isl_qpolynomial_get_ctx(qp), isl_error_invalid , "polynomial involves some of the domain dimensions", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2772); return isl_qpolynomial_free(qp); } while (0) | |||
2771 | "polynomial involves some of the domain dimensions",do { isl_handle_error(isl_qpolynomial_get_ctx(qp), isl_error_invalid , "polynomial involves some of the domain dimensions", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2772); return isl_qpolynomial_free(qp); } while (0) | |||
2772 | return isl_qpolynomial_free(qp))do { isl_handle_error(isl_qpolynomial_get_ctx(qp), isl_error_invalid , "polynomial involves some of the domain dimensions", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 2772); return isl_qpolynomial_free(qp); } while (0); | |||
2773 | qp = isl_qpolynomial_drop_dims(qp, isl_dim_in, 0, n); | |||
2774 | space = isl_qpolynomial_get_domain_space(qp); | |||
2775 | space = isl_space_params(space); | |||
2776 | qp = isl_qpolynomial_reset_domain_space(qp, space); | |||
2777 | return qp; | |||
2778 | } | |||
2779 | ||||
2780 | static __isl_give isl_qpolynomial *isl_qpolynomial_substitute_equalities_lifted( | |||
2781 | __isl_take isl_qpolynomial *qp, __isl_take isl_basic_setisl_basic_map *eq) | |||
2782 | { | |||
2783 | int i, j, k; | |||
2784 | isl_int denom; | |||
2785 | unsigned total; | |||
2786 | unsigned n_div; | |||
2787 | struct isl_upoly *up; | |||
2788 | ||||
2789 | if (!eq) | |||
2790 | goto error; | |||
2791 | if (eq->n_eq == 0) { | |||
2792 | isl_basic_set_free(eq); | |||
2793 | return qp; | |||
2794 | } | |||
2795 | ||||
2796 | qp = isl_qpolynomial_cow(qp); | |||
2797 | if (!qp) | |||
2798 | goto error; | |||
2799 | qp->div = isl_mat_cow(qp->div); | |||
2800 | if (!qp->div) | |||
2801 | goto error; | |||
2802 | ||||
2803 | total = 1 + isl_space_dim(eq->dim, isl_dim_all); | |||
2804 | n_div = eq->n_div; | |||
2805 | isl_int_init(denom)isl_sioimath_init((denom)); | |||
2806 | for (i = 0; i < eq->n_eq; ++i) { | |||
2807 | j = isl_seq_last_non_zero(eq->eq[i], total + n_div); | |||
2808 | if (j < 0 || j == 0 || j >= total) | |||
2809 | continue; | |||
2810 | ||||
2811 | for (k = 0; k < qp->div->n_row; ++k) { | |||
2812 | if (isl_int_is_zero(qp->div->row[k][1 + j])(isl_sioimath_sgn(*(qp->div->row[k][1 + j])) == 0)) | |||
2813 | continue; | |||
2814 | isl_seq_elim(qp->div->row[k] + 1, eq->eq[i], j, total, | |||
2815 | &qp->div->row[k][0]); | |||
2816 | normalize_div(qp, k); | |||
2817 | } | |||
2818 | ||||
2819 | if (isl_int_is_pos(eq->eq[i][j])(isl_sioimath_sgn(*(eq->eq[i][j])) > 0)) | |||
2820 | isl_seq_neg(eq->eq[i], eq->eq[i], total); | |||
2821 | isl_int_abs(denom, eq->eq[i][j])isl_sioimath_abs((denom), *(eq->eq[i][j])); | |||
2822 | isl_int_set_si(eq->eq[i][j], 0)isl_sioimath_set_si((eq->eq[i][j]), 0); | |||
2823 | ||||
2824 | up = isl_upoly_from_affine(qp->dim->ctx, | |||
2825 | eq->eq[i], denom, total); | |||
2826 | qp->upoly = isl_upoly_subs(qp->upoly, j - 1, 1, &up); | |||
2827 | isl_upoly_free(up); | |||
2828 | } | |||
2829 | isl_int_clear(denom)isl_sioimath_clear((denom)); | |||
2830 | ||||
2831 | if (!qp->upoly) | |||
2832 | goto error; | |||
2833 | ||||
2834 | isl_basic_set_free(eq); | |||
2835 | ||||
2836 | qp = substitute_non_divs(qp); | |||
2837 | qp = sort_divs(qp); | |||
2838 | ||||
2839 | return qp; | |||
2840 | error: | |||
2841 | isl_basic_set_free(eq); | |||
2842 | isl_qpolynomial_free(qp); | |||
2843 | return NULL((void*)0); | |||
2844 | } | |||
2845 | ||||
2846 | /* Exploit the equalities in "eq" to simplify the quasi-polynomial. | |||
2847 | */ | |||
2848 | __isl_give isl_qpolynomial *isl_qpolynomial_substitute_equalities( | |||
2849 | __isl_take isl_qpolynomial *qp, __isl_take isl_basic_setisl_basic_map *eq) | |||
2850 | { | |||
2851 | if (!qp || !eq) | |||
2852 | goto error; | |||
2853 | if (qp->div->n_row > 0) | |||
2854 | eq = isl_basic_set_add_dims(eq, isl_dim_set, qp->div->n_row); | |||
2855 | return isl_qpolynomial_substitute_equalities_lifted(qp, eq); | |||
2856 | error: | |||
2857 | isl_basic_set_free(eq); | |||
2858 | isl_qpolynomial_free(qp); | |||
2859 | return NULL((void*)0); | |||
2860 | } | |||
2861 | ||||
2862 | static __isl_give isl_basic_setisl_basic_map *add_div_constraints( | |||
2863 | __isl_take isl_basic_setisl_basic_map *bset, __isl_take isl_mat *div) | |||
2864 | { | |||
2865 | int i; | |||
2866 | unsigned total; | |||
2867 | ||||
2868 | if (!bset || !div) | |||
2869 | goto error; | |||
2870 | ||||
2871 | bset = isl_basic_set_extend_constraints(bset, 0, 2 * div->n_row); | |||
2872 | if (!bset) | |||
2873 | goto error; | |||
2874 | total = isl_basic_set_total_dim(bset); | |||
2875 | for (i = 0; i < div->n_row; ++i) | |||
2876 | if (isl_basic_set_add_div_constraints_var(bset, | |||
2877 | total - div->n_row + i, div->row[i]) < 0) | |||
2878 | goto error; | |||
2879 | ||||
2880 | isl_mat_free(div); | |||
2881 | return bset; | |||
2882 | error: | |||
2883 | isl_mat_free(div); | |||
2884 | isl_basic_set_free(bset); | |||
2885 | return NULL((void*)0); | |||
2886 | } | |||
2887 | ||||
2888 | /* Look for equalities among the variables shared by context and qp | |||
2889 | * and the integer divisions of qp, if any. | |||
2890 | * The equalities are then used to eliminate variables and/or integer | |||
2891 | * divisions from qp. | |||
2892 | */ | |||
2893 | __isl_give isl_qpolynomial *isl_qpolynomial_gist( | |||
2894 | __isl_take isl_qpolynomial *qp, __isl_take isl_setisl_map *context) | |||
2895 | { | |||
2896 | isl_basic_setisl_basic_map *aff; | |||
2897 | ||||
2898 | if (!qp) | |||
2899 | goto error; | |||
2900 | if (qp->div->n_row > 0) { | |||
2901 | isl_basic_setisl_basic_map *bset; | |||
2902 | context = isl_set_add_dims(context, isl_dim_set, | |||
2903 | qp->div->n_row); | |||
2904 | bset = isl_basic_set_universe(isl_set_get_space(context)); | |||
2905 | bset = add_div_constraints(bset, isl_mat_copy(qp->div)); | |||
2906 | context = isl_set_intersect(context, | |||
2907 | isl_set_from_basic_set(bset)); | |||
2908 | } | |||
2909 | ||||
2910 | aff = isl_set_affine_hull(context); | |||
2911 | return isl_qpolynomial_substitute_equalities_lifted(qp, aff); | |||
2912 | error: | |||
2913 | isl_qpolynomial_free(qp); | |||
2914 | isl_set_free(context); | |||
2915 | return NULL((void*)0); | |||
2916 | } | |||
2917 | ||||
2918 | __isl_give isl_qpolynomial *isl_qpolynomial_gist_params( | |||
2919 | __isl_take isl_qpolynomial *qp, __isl_take isl_setisl_map *context) | |||
2920 | { | |||
2921 | isl_space *space = isl_qpolynomial_get_domain_space(qp); | |||
2922 | isl_setisl_map *dom_context = isl_set_universe(space); | |||
2923 | dom_context = isl_set_intersect_params(dom_context, context); | |||
2924 | return isl_qpolynomial_gist(qp, dom_context); | |||
2925 | } | |||
2926 | ||||
2927 | __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_qpolynomial( | |||
2928 | __isl_take isl_qpolynomial *qp) | |||
2929 | { | |||
2930 | isl_setisl_map *dom; | |||
2931 | ||||
2932 | if (!qp) | |||
2933 | return NULL((void*)0); | |||
2934 | if (isl_qpolynomial_is_zero(qp)) { | |||
2935 | isl_space *dim = isl_qpolynomial_get_space(qp); | |||
2936 | isl_qpolynomial_free(qp); | |||
2937 | return isl_pw_qpolynomial_zero(dim); | |||
2938 | } | |||
2939 | ||||
2940 | dom = isl_set_universe(isl_qpolynomial_get_domain_space(qp)); | |||
2941 | return isl_pw_qpolynomial_alloc(dom, qp); | |||
2942 | } | |||
2943 | ||||
2944 | #define isl_qpolynomial_involves_nanisl_qpolynomial_is_nan isl_qpolynomial_is_nan | |||
2945 | ||||
2946 | #undef PWisl_pw_qpolynomial | |||
2947 | #define PWisl_pw_qpolynomial isl_pw_qpolynomial | |||
2948 | #undef ELisl_qpolynomial | |||
2949 | #define ELisl_qpolynomial isl_qpolynomial | |||
2950 | #undef EL_IS_ZEROis_zero | |||
2951 | #define EL_IS_ZEROis_zero is_zero | |||
2952 | #undef ZEROzero | |||
2953 | #define ZEROzero zero | |||
2954 | #undef IS_ZEROis_zero | |||
2955 | #define IS_ZEROis_zero is_zero | |||
2956 | #undef FIELDqp | |||
2957 | #define FIELDqp qp | |||
2958 | #undef DEFAULT_IS_ZERO1 | |||
2959 | #define DEFAULT_IS_ZERO1 1 | |||
2960 | ||||
2961 | #define NO_PULLBACK | |||
2962 | ||||
2963 | #include <isl_pw_templ.c> | |||
2964 | #include <isl_pw_eval.c> | |||
2965 | ||||
2966 | #undef BASEpw_qpolynomial | |||
2967 | #define BASEpw_qpolynomial pw_qpolynomial | |||
2968 | ||||
2969 | #include <isl_union_single.c> | |||
2970 | #include <isl_union_eval.c> | |||
2971 | #include <isl_union_neg.c> | |||
2972 | ||||
2973 | int isl_pw_qpolynomial_is_one(__isl_keep isl_pw_qpolynomial *pwqp) | |||
2974 | { | |||
2975 | if (!pwqp) | |||
2976 | return -1; | |||
2977 | ||||
2978 | if (pwqp->n != -1) | |||
2979 | return 0; | |||
2980 | ||||
2981 | if (!isl_set_plain_is_universe(pwqp->p[0].set)) | |||
2982 | return 0; | |||
2983 | ||||
2984 | return isl_qpolynomial_is_one(pwqp->p[0].qp); | |||
2985 | } | |||
2986 | ||||
2987 | __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add( | |||
2988 | __isl_take isl_pw_qpolynomial *pwqp1, | |||
2989 | __isl_take isl_pw_qpolynomial *pwqp2) | |||
2990 | { | |||
2991 | return isl_pw_qpolynomial_union_add_(pwqp1, pwqp2); | |||
2992 | } | |||
2993 | ||||
2994 | __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_mul( | |||
2995 | __isl_take isl_pw_qpolynomial *pwqp1, | |||
2996 | __isl_take isl_pw_qpolynomial *pwqp2) | |||
2997 | { | |||
2998 | int i, j, n; | |||
2999 | struct isl_pw_qpolynomial *res; | |||
3000 | ||||
3001 | if (!pwqp1 || !pwqp2) | |||
3002 | goto error; | |||
3003 | ||||
3004 | isl_assert(pwqp1->dim->ctx, isl_space_is_equal(pwqp1->dim, pwqp2->dim),do { if (isl_space_is_equal(pwqp1->dim, pwqp2->dim)) break ; do { isl_handle_error(pwqp1->dim->ctx, isl_error_unknown , "Assertion \"" "isl_space_is_equal(pwqp1->dim, pwqp2->dim)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3005); goto error; } while (0); } while (0) | |||
3005 | goto error)do { if (isl_space_is_equal(pwqp1->dim, pwqp2->dim)) break ; do { isl_handle_error(pwqp1->dim->ctx, isl_error_unknown , "Assertion \"" "isl_space_is_equal(pwqp1->dim, pwqp2->dim)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3005); goto error; } while (0); } while (0); | |||
3006 | ||||
3007 | if (isl_pw_qpolynomial_is_zero(pwqp1)) { | |||
3008 | isl_pw_qpolynomial_free(pwqp2); | |||
3009 | return pwqp1; | |||
3010 | } | |||
3011 | ||||
3012 | if (isl_pw_qpolynomial_is_zero(pwqp2)) { | |||
3013 | isl_pw_qpolynomial_free(pwqp1); | |||
3014 | return pwqp2; | |||
3015 | } | |||
3016 | ||||
3017 | if (isl_pw_qpolynomial_is_one(pwqp1)) { | |||
3018 | isl_pw_qpolynomial_free(pwqp1); | |||
3019 | return pwqp2; | |||
3020 | } | |||
3021 | ||||
3022 | if (isl_pw_qpolynomial_is_one(pwqp2)) { | |||
3023 | isl_pw_qpolynomial_free(pwqp2); | |||
3024 | return pwqp1; | |||
3025 | } | |||
3026 | ||||
3027 | n = pwqp1->n * pwqp2->n; | |||
3028 | res = isl_pw_qpolynomial_alloc_size(isl_space_copy(pwqp1->dim), n); | |||
3029 | ||||
3030 | for (i = 0; i < pwqp1->n; ++i) { | |||
3031 | for (j = 0; j < pwqp2->n; ++j) { | |||
3032 | struct isl_setisl_map *common; | |||
3033 | struct isl_qpolynomial *prod; | |||
3034 | common = isl_set_intersect(isl_set_copy(pwqp1->p[i].set), | |||
3035 | isl_set_copy(pwqp2->p[j].set)); | |||
3036 | if (isl_set_plain_is_empty(common)) { | |||
3037 | isl_set_free(common); | |||
3038 | continue; | |||
3039 | } | |||
3040 | ||||
3041 | prod = isl_qpolynomial_mul( | |||
3042 | isl_qpolynomial_copy(pwqp1->p[i].qp), | |||
| ||||
3043 | isl_qpolynomial_copy(pwqp2->p[j].qp)); | |||
3044 | ||||
3045 | res = isl_pw_qpolynomial_add_piece(res, common, prod); | |||
3046 | } | |||
3047 | } | |||
3048 | ||||
3049 | isl_pw_qpolynomial_free(pwqp1); | |||
3050 | isl_pw_qpolynomial_free(pwqp2); | |||
3051 | ||||
3052 | return res; | |||
3053 | error: | |||
3054 | isl_pw_qpolynomial_free(pwqp1); | |||
3055 | isl_pw_qpolynomial_free(pwqp2); | |||
3056 | return NULL((void*)0); | |||
3057 | } | |||
3058 | ||||
3059 | __isl_give isl_val *isl_upoly_eval(__isl_take struct isl_upoly *up, | |||
3060 | __isl_take isl_vec *vec) | |||
3061 | { | |||
3062 | int i; | |||
3063 | struct isl_upoly_rec *rec; | |||
3064 | isl_val *res; | |||
3065 | isl_val *base; | |||
3066 | ||||
3067 | if (isl_upoly_is_cst(up)) { | |||
3068 | isl_vec_free(vec); | |||
3069 | res = isl_upoly_get_constant_val(up); | |||
3070 | isl_upoly_free(up); | |||
3071 | return res; | |||
3072 | } | |||
3073 | ||||
3074 | rec = isl_upoly_as_rec(up); | |||
3075 | if (!rec || !vec) | |||
3076 | goto error; | |||
3077 | ||||
3078 | isl_assert(up->ctx, rec->n >= 1, goto error)do { if (rec->n >= 1) break; do { isl_handle_error(up-> ctx, isl_error_unknown, "Assertion \"" "rec->n >= 1" "\" failed" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3078); goto error; } while (0); } while (0); | |||
3079 | ||||
3080 | base = isl_val_rat_from_isl_int(up->ctx, | |||
3081 | vec->el[1 + up->var], vec->el[0]); | |||
3082 | ||||
3083 | res = isl_upoly_eval(isl_upoly_copy(rec->p[rec->n - 1]), | |||
3084 | isl_vec_copy(vec)); | |||
3085 | ||||
3086 | for (i = rec->n - 2; i >= 0; --i) { | |||
3087 | res = isl_val_mul(res, isl_val_copy(base)); | |||
3088 | res = isl_val_add(res, | |||
3089 | isl_upoly_eval(isl_upoly_copy(rec->p[i]), | |||
3090 | isl_vec_copy(vec))); | |||
3091 | } | |||
3092 | ||||
3093 | isl_val_free(base); | |||
3094 | isl_upoly_free(up); | |||
3095 | isl_vec_free(vec); | |||
3096 | return res; | |||
3097 | error: | |||
3098 | isl_upoly_free(up); | |||
3099 | isl_vec_free(vec); | |||
3100 | return NULL((void*)0); | |||
3101 | } | |||
3102 | ||||
3103 | /* Evaluate "qp" in the void point "pnt". | |||
3104 | * In particular, return the value NaN. | |||
3105 | */ | |||
3106 | static __isl_give isl_val *eval_void(__isl_take isl_qpolynomial *qp, | |||
3107 | __isl_take isl_point *pnt) | |||
3108 | { | |||
3109 | isl_ctx *ctx; | |||
3110 | ||||
3111 | ctx = isl_point_get_ctx(pnt); | |||
3112 | isl_qpolynomial_free(qp); | |||
3113 | isl_point_free(pnt); | |||
3114 | return isl_val_nan(ctx); | |||
3115 | } | |||
3116 | ||||
3117 | __isl_give isl_val *isl_qpolynomial_eval(__isl_take isl_qpolynomial *qp, | |||
3118 | __isl_take isl_point *pnt) | |||
3119 | { | |||
3120 | isl_bool is_void; | |||
3121 | isl_vec *ext; | |||
3122 | isl_val *v; | |||
3123 | ||||
3124 | if (!qp || !pnt) | |||
3125 | goto error; | |||
3126 | isl_assert(pnt->dim->ctx, isl_space_is_equal(pnt->dim, qp->dim), goto error)do { if (isl_space_is_equal(pnt->dim, qp->dim)) break; do { isl_handle_error(pnt->dim->ctx, isl_error_unknown, "Assertion \"" "isl_space_is_equal(pnt->dim, qp->dim)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3126); goto error; } while (0); } while (0); | |||
3127 | is_void = isl_point_is_void(pnt); | |||
3128 | if (is_void < 0) | |||
3129 | goto error; | |||
3130 | if (is_void) | |||
3131 | return eval_void(qp, pnt); | |||
3132 | ||||
3133 | ext = isl_local_extend_point_vec(qp->div, isl_vec_copy(pnt->vec)); | |||
3134 | ||||
3135 | v = isl_upoly_eval(isl_upoly_copy(qp->upoly), ext); | |||
3136 | ||||
3137 | isl_qpolynomial_free(qp); | |||
3138 | isl_point_free(pnt); | |||
3139 | ||||
3140 | return v; | |||
3141 | error: | |||
3142 | isl_qpolynomial_free(qp); | |||
3143 | isl_point_free(pnt); | |||
3144 | return NULL((void*)0); | |||
3145 | } | |||
3146 | ||||
3147 | int isl_upoly_cmp(__isl_keep struct isl_upoly_cst *cst1, | |||
3148 | __isl_keep struct isl_upoly_cst *cst2) | |||
3149 | { | |||
3150 | int cmp; | |||
3151 | isl_int t; | |||
3152 | isl_int_init(t)isl_sioimath_init((t)); | |||
3153 | isl_int_mul(t, cst1->n, cst2->d)isl_sioimath_mul((t), *(cst1->n), *(cst2->d)); | |||
3154 | isl_int_submul(t, cst2->n, cst1->d)isl_sioimath_submul((t), *(cst2->n), *(cst1->d)); | |||
3155 | cmp = isl_int_sgn(t)isl_sioimath_sgn(*(t)); | |||
3156 | isl_int_clear(t)isl_sioimath_clear((t)); | |||
3157 | return cmp; | |||
3158 | } | |||
3159 | ||||
3160 | __isl_give isl_qpolynomial *isl_qpolynomial_insert_dims( | |||
3161 | __isl_take isl_qpolynomial *qp, enum isl_dim_type type, | |||
3162 | unsigned first, unsigned n) | |||
3163 | { | |||
3164 | unsigned total; | |||
3165 | unsigned g_pos; | |||
3166 | int *exp; | |||
3167 | ||||
3168 | if (!qp) | |||
3169 | return NULL((void*)0); | |||
3170 | if (type == isl_dim_out) | |||
3171 | isl_die(qp->div->ctx, isl_error_invalid,do { isl_handle_error(qp->div->ctx, isl_error_invalid, "cannot insert output/set dimensions" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3173); goto error; } while (0) | |||
3172 | "cannot insert output/set dimensions",do { isl_handle_error(qp->div->ctx, isl_error_invalid, "cannot insert output/set dimensions" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3173); goto error; } while (0) | |||
3173 | goto error)do { isl_handle_error(qp->div->ctx, isl_error_invalid, "cannot insert output/set dimensions" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3173); goto error; } while (0); | |||
3174 | if (type == isl_dim_in) | |||
3175 | type = isl_dim_set; | |||
3176 | if (n == 0 && !isl_space_is_named_or_nested(qp->dim, type)) | |||
3177 | return qp; | |||
3178 | ||||
3179 | qp = isl_qpolynomial_cow(qp); | |||
3180 | if (!qp) | |||
3181 | return NULL((void*)0); | |||
3182 | ||||
3183 | isl_assert(qp->div->ctx, first <= isl_space_dim(qp->dim, type),do { if (first <= isl_space_dim(qp->dim, type)) break; do { isl_handle_error(qp->div->ctx, isl_error_unknown, "Assertion \"" "first <= isl_space_dim(qp->dim, type)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3184); goto error; } while (0); } while (0) | |||
3184 | goto error)do { if (first <= isl_space_dim(qp->dim, type)) break; do { isl_handle_error(qp->div->ctx, isl_error_unknown, "Assertion \"" "first <= isl_space_dim(qp->dim, type)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3184); goto error; } while (0); } while (0); | |||
3185 | ||||
3186 | g_pos = pos(qp->dim, type) + first; | |||
3187 | ||||
3188 | qp->div = isl_mat_insert_zero_cols(qp->div, 2 + g_pos, n); | |||
3189 | if (!qp->div) | |||
3190 | goto error; | |||
3191 | ||||
3192 | total = qp->div->n_col - 2; | |||
3193 | if (total > g_pos) { | |||
3194 | int i; | |||
3195 | exp = isl_alloc_array(qp->div->ctx, int, total - g_pos)((int *)isl_malloc_or_die(qp->div->ctx, (total - g_pos) *sizeof(int))); | |||
3196 | if (!exp) | |||
3197 | goto error; | |||
3198 | for (i = 0; i < total - g_pos; ++i) | |||
3199 | exp[i] = i + n; | |||
3200 | qp->upoly = expand(qp->upoly, exp, g_pos); | |||
3201 | free(exp); | |||
3202 | if (!qp->upoly) | |||
3203 | goto error; | |||
3204 | } | |||
3205 | ||||
3206 | qp->dim = isl_space_insert_dims(qp->dim, type, first, n); | |||
3207 | if (!qp->dim) | |||
3208 | goto error; | |||
3209 | ||||
3210 | return qp; | |||
3211 | error: | |||
3212 | isl_qpolynomial_free(qp); | |||
3213 | return NULL((void*)0); | |||
3214 | } | |||
3215 | ||||
3216 | __isl_give isl_qpolynomial *isl_qpolynomial_add_dims( | |||
3217 | __isl_take isl_qpolynomial *qp, enum isl_dim_type type, unsigned n) | |||
3218 | { | |||
3219 | unsigned pos; | |||
3220 | ||||
3221 | pos = isl_qpolynomial_dim(qp, type); | |||
3222 | ||||
3223 | return isl_qpolynomial_insert_dims(qp, type, pos, n); | |||
3224 | } | |||
3225 | ||||
3226 | __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add_dims( | |||
3227 | __isl_take isl_pw_qpolynomial *pwqp, | |||
3228 | enum isl_dim_type type, unsigned n) | |||
3229 | { | |||
3230 | unsigned pos; | |||
3231 | ||||
3232 | pos = isl_pw_qpolynomial_dim(pwqp, type); | |||
3233 | ||||
3234 | return isl_pw_qpolynomial_insert_dims(pwqp, type, pos, n); | |||
3235 | } | |||
3236 | ||||
3237 | static int *reordering_move(isl_ctx *ctx, | |||
3238 | unsigned len, unsigned dst, unsigned src, unsigned n) | |||
3239 | { | |||
3240 | int i; | |||
3241 | int *reordering; | |||
3242 | ||||
3243 | reordering = isl_alloc_array(ctx, int, len)((int *)isl_malloc_or_die(ctx, (len)*sizeof(int))); | |||
3244 | if (!reordering) | |||
3245 | return NULL((void*)0); | |||
3246 | ||||
3247 | if (dst <= src) { | |||
3248 | for (i = 0; i < dst; ++i) | |||
3249 | reordering[i] = i; | |||
3250 | for (i = 0; i < n; ++i) | |||
3251 | reordering[src + i] = dst + i; | |||
3252 | for (i = 0; i < src - dst; ++i) | |||
3253 | reordering[dst + i] = dst + n + i; | |||
3254 | for (i = 0; i < len - src - n; ++i) | |||
3255 | reordering[src + n + i] = src + n + i; | |||
3256 | } else { | |||
3257 | for (i = 0; i < src; ++i) | |||
3258 | reordering[i] = i; | |||
3259 | for (i = 0; i < n; ++i) | |||
3260 | reordering[src + i] = dst + i; | |||
3261 | for (i = 0; i < dst - src; ++i) | |||
3262 | reordering[src + n + i] = src + i; | |||
3263 | for (i = 0; i < len - dst - n; ++i) | |||
3264 | reordering[dst + n + i] = dst + n + i; | |||
3265 | } | |||
3266 | ||||
3267 | return reordering; | |||
3268 | } | |||
3269 | ||||
3270 | __isl_give isl_qpolynomial *isl_qpolynomial_move_dims( | |||
3271 | __isl_take isl_qpolynomial *qp, | |||
3272 | enum isl_dim_type dst_type, unsigned dst_pos, | |||
3273 | enum isl_dim_type src_type, unsigned src_pos, unsigned n) | |||
3274 | { | |||
3275 | unsigned g_dst_pos; | |||
3276 | unsigned g_src_pos; | |||
3277 | int *reordering; | |||
3278 | ||||
3279 | if (!qp) | |||
3280 | return NULL((void*)0); | |||
3281 | ||||
3282 | if (dst_type == isl_dim_out || src_type == isl_dim_out) | |||
3283 | isl_die(qp->dim->ctx, isl_error_invalid,do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "cannot move output/set dimension" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3285); goto error; } while (0) | |||
3284 | "cannot move output/set dimension",do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "cannot move output/set dimension" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3285); goto error; } while (0) | |||
3285 | goto error)do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "cannot move output/set dimension" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3285); goto error; } while (0); | |||
3286 | if (dst_type == isl_dim_in) | |||
3287 | dst_type = isl_dim_set; | |||
3288 | if (src_type == isl_dim_in) | |||
3289 | src_type = isl_dim_set; | |||
3290 | ||||
3291 | if (n == 0 && | |||
3292 | !isl_space_is_named_or_nested(qp->dim, src_type) && | |||
3293 | !isl_space_is_named_or_nested(qp->dim, dst_type)) | |||
3294 | return qp; | |||
3295 | ||||
3296 | qp = isl_qpolynomial_cow(qp); | |||
3297 | if (!qp) | |||
3298 | return NULL((void*)0); | |||
3299 | ||||
3300 | isl_assert(qp->dim->ctx, src_pos + n <= isl_space_dim(qp->dim, src_type),do { if (src_pos + n <= isl_space_dim(qp->dim, src_type )) break; do { isl_handle_error(qp->dim->ctx, isl_error_unknown , "Assertion \"" "src_pos + n <= isl_space_dim(qp->dim, src_type)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3301); goto error; } while (0); } while (0) | |||
3301 | goto error)do { if (src_pos + n <= isl_space_dim(qp->dim, src_type )) break; do { isl_handle_error(qp->dim->ctx, isl_error_unknown , "Assertion \"" "src_pos + n <= isl_space_dim(qp->dim, src_type)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3301); goto error; } while (0); } while (0); | |||
3302 | ||||
3303 | g_dst_pos = pos(qp->dim, dst_type) + dst_pos; | |||
3304 | g_src_pos = pos(qp->dim, src_type) + src_pos; | |||
3305 | if (dst_type > src_type) | |||
3306 | g_dst_pos -= n; | |||
3307 | ||||
3308 | qp->div = isl_mat_move_cols(qp->div, 2 + g_dst_pos, 2 + g_src_pos, n); | |||
3309 | if (!qp->div) | |||
3310 | goto error; | |||
3311 | qp = sort_divs(qp); | |||
3312 | if (!qp) | |||
3313 | goto error; | |||
3314 | ||||
3315 | reordering = reordering_move(qp->dim->ctx, | |||
3316 | qp->div->n_col - 2, g_dst_pos, g_src_pos, n); | |||
3317 | if (!reordering) | |||
3318 | goto error; | |||
3319 | ||||
3320 | qp->upoly = reorder(qp->upoly, reordering); | |||
3321 | free(reordering); | |||
3322 | if (!qp->upoly) | |||
3323 | goto error; | |||
3324 | ||||
3325 | qp->dim = isl_space_move_dims(qp->dim, dst_type, dst_pos, src_type, src_pos, n); | |||
3326 | if (!qp->dim) | |||
3327 | goto error; | |||
3328 | ||||
3329 | return qp; | |||
3330 | error: | |||
3331 | isl_qpolynomial_free(qp); | |||
3332 | return NULL((void*)0); | |||
3333 | } | |||
3334 | ||||
3335 | __isl_give isl_qpolynomial *isl_qpolynomial_from_affine(__isl_take isl_space *dim, | |||
3336 | isl_int *f, isl_int denom) | |||
3337 | { | |||
3338 | struct isl_upoly *up; | |||
3339 | ||||
3340 | dim = isl_space_domain(dim); | |||
3341 | if (!dim) | |||
3342 | return NULL((void*)0); | |||
3343 | ||||
3344 | up = isl_upoly_from_affine(dim->ctx, f, denom, | |||
3345 | 1 + isl_space_dim(dim, isl_dim_all)); | |||
3346 | ||||
3347 | return isl_qpolynomial_alloc(dim, 0, up); | |||
3348 | } | |||
3349 | ||||
3350 | __isl_give isl_qpolynomial *isl_qpolynomial_from_aff(__isl_take isl_aff *aff) | |||
3351 | { | |||
3352 | isl_ctx *ctx; | |||
3353 | struct isl_upoly *up; | |||
3354 | isl_qpolynomial *qp; | |||
3355 | ||||
3356 | if (!aff) | |||
3357 | return NULL((void*)0); | |||
3358 | ||||
3359 | ctx = isl_aff_get_ctx(aff); | |||
3360 | up = isl_upoly_from_affine(ctx, aff->v->el + 1, aff->v->el[0], | |||
3361 | aff->v->size - 1); | |||
3362 | ||||
3363 | qp = isl_qpolynomial_alloc(isl_aff_get_domain_space(aff), | |||
3364 | aff->ls->div->n_row, up); | |||
3365 | if (!qp) | |||
3366 | goto error; | |||
3367 | ||||
3368 | isl_mat_free(qp->div); | |||
3369 | qp->div = isl_mat_copy(aff->ls->div); | |||
3370 | qp->div = isl_mat_cow(qp->div); | |||
3371 | if (!qp->div) | |||
3372 | goto error; | |||
3373 | ||||
3374 | isl_aff_free(aff); | |||
3375 | qp = reduce_divs(qp); | |||
3376 | qp = remove_redundant_divs(qp); | |||
3377 | return qp; | |||
3378 | error: | |||
3379 | isl_aff_free(aff); | |||
3380 | return isl_qpolynomial_free(qp); | |||
3381 | } | |||
3382 | ||||
3383 | __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_pw_aff( | |||
3384 | __isl_take isl_pw_aff *pwaff) | |||
3385 | { | |||
3386 | int i; | |||
3387 | isl_pw_qpolynomial *pwqp; | |||
3388 | ||||
3389 | if (!pwaff) | |||
3390 | return NULL((void*)0); | |||
3391 | ||||
3392 | pwqp = isl_pw_qpolynomial_alloc_size(isl_pw_aff_get_space(pwaff), | |||
3393 | pwaff->n); | |||
3394 | ||||
3395 | for (i = 0; i < pwaff->n; ++i) { | |||
3396 | isl_setisl_map *dom; | |||
3397 | isl_qpolynomial *qp; | |||
3398 | ||||
3399 | dom = isl_set_copy(pwaff->p[i].set); | |||
3400 | qp = isl_qpolynomial_from_aff(isl_aff_copy(pwaff->p[i].aff)); | |||
3401 | pwqp = isl_pw_qpolynomial_add_piece(pwqp, dom, qp); | |||
3402 | } | |||
3403 | ||||
3404 | isl_pw_aff_free(pwaff); | |||
3405 | return pwqp; | |||
3406 | } | |||
3407 | ||||
3408 | __isl_give isl_qpolynomial *isl_qpolynomial_from_constraint( | |||
3409 | __isl_take isl_constraint *c, enum isl_dim_type type, unsigned pos) | |||
3410 | { | |||
3411 | isl_aff *aff; | |||
3412 | ||||
3413 | aff = isl_constraint_get_bound(c, type, pos); | |||
3414 | isl_constraint_free(c); | |||
3415 | return isl_qpolynomial_from_aff(aff); | |||
3416 | } | |||
3417 | ||||
3418 | /* For each 0 <= i < "n", replace variable "first" + i of type "type" | |||
3419 | * in "qp" by subs[i]. | |||
3420 | */ | |||
3421 | __isl_give isl_qpolynomial *isl_qpolynomial_substitute( | |||
3422 | __isl_take isl_qpolynomial *qp, | |||
3423 | enum isl_dim_type type, unsigned first, unsigned n, | |||
3424 | __isl_keep isl_qpolynomial **subs) | |||
3425 | { | |||
3426 | int i; | |||
3427 | struct isl_upoly **ups; | |||
3428 | ||||
3429 | if (n == 0) | |||
3430 | return qp; | |||
3431 | ||||
3432 | qp = isl_qpolynomial_cow(qp); | |||
3433 | if (!qp) | |||
3434 | return NULL((void*)0); | |||
3435 | ||||
3436 | if (type == isl_dim_out) | |||
3437 | isl_die(qp->dim->ctx, isl_error_invalid,do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "cannot substitute output/set dimension" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3439); goto error; } while (0) | |||
3438 | "cannot substitute output/set dimension",do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "cannot substitute output/set dimension" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3439); goto error; } while (0) | |||
3439 | goto error)do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "cannot substitute output/set dimension" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3439); goto error; } while (0); | |||
3440 | if (type == isl_dim_in) | |||
3441 | type = isl_dim_set; | |||
3442 | ||||
3443 | for (i = 0; i < n; ++i) | |||
3444 | if (!subs[i]) | |||
3445 | goto error; | |||
3446 | ||||
3447 | isl_assert(qp->dim->ctx, first + n <= isl_space_dim(qp->dim, type),do { if (first + n <= isl_space_dim(qp->dim, type)) break ; do { isl_handle_error(qp->dim->ctx, isl_error_unknown , "Assertion \"" "first + n <= isl_space_dim(qp->dim, type)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3448); goto error; } while (0); } while (0) | |||
3448 | goto error)do { if (first + n <= isl_space_dim(qp->dim, type)) break ; do { isl_handle_error(qp->dim->ctx, isl_error_unknown , "Assertion \"" "first + n <= isl_space_dim(qp->dim, type)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3448); goto error; } while (0); } while (0); | |||
3449 | ||||
3450 | for (i = 0; i < n; ++i) | |||
3451 | isl_assert(qp->dim->ctx, isl_space_is_equal(qp->dim, subs[i]->dim),do { if (isl_space_is_equal(qp->dim, subs[i]->dim)) break ; do { isl_handle_error(qp->dim->ctx, isl_error_unknown , "Assertion \"" "isl_space_is_equal(qp->dim, subs[i]->dim)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3452); goto error; } while (0); } while (0) | |||
3452 | goto error)do { if (isl_space_is_equal(qp->dim, subs[i]->dim)) break ; do { isl_handle_error(qp->dim->ctx, isl_error_unknown , "Assertion \"" "isl_space_is_equal(qp->dim, subs[i]->dim)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3452); goto error; } while (0); } while (0); | |||
3453 | ||||
3454 | isl_assert(qp->dim->ctx, qp->div->n_row == 0, goto error)do { if (qp->div->n_row == 0) break; do { isl_handle_error (qp->dim->ctx, isl_error_unknown, "Assertion \"" "qp->div->n_row == 0" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3454); goto error; } while (0); } while (0); | |||
3455 | for (i = 0; i < n; ++i) | |||
3456 | isl_assert(qp->dim->ctx, subs[i]->div->n_row == 0, goto error)do { if (subs[i]->div->n_row == 0) break; do { isl_handle_error (qp->dim->ctx, isl_error_unknown, "Assertion \"" "subs[i]->div->n_row == 0" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3456); goto error; } while (0); } while (0); | |||
3457 | ||||
3458 | first += pos(qp->dim, type); | |||
3459 | ||||
3460 | ups = isl_alloc_array(qp->dim->ctx, struct isl_upoly *, n)((struct isl_upoly * *)isl_malloc_or_die(qp->dim->ctx, ( n)*sizeof(struct isl_upoly *))); | |||
3461 | if (!ups) | |||
3462 | goto error; | |||
3463 | for (i = 0; i < n; ++i) | |||
3464 | ups[i] = subs[i]->upoly; | |||
3465 | ||||
3466 | qp->upoly = isl_upoly_subs(qp->upoly, first, n, ups); | |||
3467 | ||||
3468 | free(ups); | |||
3469 | ||||
3470 | if (!qp->upoly) | |||
3471 | goto error; | |||
3472 | ||||
3473 | return qp; | |||
3474 | error: | |||
3475 | isl_qpolynomial_free(qp); | |||
3476 | return NULL((void*)0); | |||
3477 | } | |||
3478 | ||||
3479 | /* Extend "bset" with extra set dimensions for each integer division | |||
3480 | * in "qp" and then call "fn" with the extended bset and the polynomial | |||
3481 | * that results from replacing each of the integer divisions by the | |||
3482 | * corresponding extra set dimension. | |||
3483 | */ | |||
3484 | isl_stat isl_qpolynomial_as_polynomial_on_domain(__isl_keep isl_qpolynomial *qp, | |||
3485 | __isl_keep isl_basic_setisl_basic_map *bset, | |||
3486 | isl_stat (*fn)(__isl_take isl_basic_setisl_basic_map *bset, | |||
3487 | __isl_take isl_qpolynomial *poly, void *user), void *user) | |||
3488 | { | |||
3489 | isl_space *dim; | |||
3490 | isl_mat *div; | |||
3491 | isl_qpolynomial *poly; | |||
3492 | ||||
3493 | if (!qp || !bset) | |||
3494 | return isl_stat_error; | |||
3495 | if (qp->div->n_row == 0) | |||
3496 | return fn(isl_basic_set_copy(bset), isl_qpolynomial_copy(qp), | |||
3497 | user); | |||
3498 | ||||
3499 | div = isl_mat_copy(qp->div); | |||
3500 | dim = isl_space_copy(qp->dim); | |||
3501 | dim = isl_space_add_dims(dim, isl_dim_set, qp->div->n_row); | |||
3502 | poly = isl_qpolynomial_alloc(dim, 0, isl_upoly_copy(qp->upoly)); | |||
3503 | bset = isl_basic_set_copy(bset); | |||
3504 | bset = isl_basic_set_add_dims(bset, isl_dim_set, qp->div->n_row); | |||
3505 | bset = add_div_constraints(bset, div); | |||
3506 | ||||
3507 | return fn(bset, poly, user); | |||
3508 | } | |||
3509 | ||||
3510 | /* Return total degree in variables first (inclusive) up to last (exclusive). | |||
3511 | */ | |||
3512 | int isl_upoly_degree(__isl_keep struct isl_upoly *up, int first, int last) | |||
3513 | { | |||
3514 | int deg = -1; | |||
3515 | int i; | |||
3516 | struct isl_upoly_rec *rec; | |||
3517 | ||||
3518 | if (!up) | |||
3519 | return -2; | |||
3520 | if (isl_upoly_is_zero(up)) | |||
3521 | return -1; | |||
3522 | if (isl_upoly_is_cst(up) || up->var < first) | |||
3523 | return 0; | |||
3524 | ||||
3525 | rec = isl_upoly_as_rec(up); | |||
3526 | if (!rec) | |||
3527 | return -2; | |||
3528 | ||||
3529 | for (i = 0; i < rec->n; ++i) { | |||
3530 | int d; | |||
3531 | ||||
3532 | if (isl_upoly_is_zero(rec->p[i])) | |||
3533 | continue; | |||
3534 | d = isl_upoly_degree(rec->p[i], first, last); | |||
3535 | if (up->var < last) | |||
3536 | d += i; | |||
3537 | if (d > deg) | |||
3538 | deg = d; | |||
3539 | } | |||
3540 | ||||
3541 | return deg; | |||
3542 | } | |||
3543 | ||||
3544 | /* Return total degree in set variables. | |||
3545 | */ | |||
3546 | int isl_qpolynomial_degree(__isl_keep isl_qpolynomial *poly) | |||
3547 | { | |||
3548 | unsigned ovar; | |||
3549 | unsigned nvar; | |||
3550 | ||||
3551 | if (!poly) | |||
3552 | return -2; | |||
3553 | ||||
3554 | ovar = isl_space_offset(poly->dim, isl_dim_set); | |||
3555 | nvar = isl_space_dim(poly->dim, isl_dim_set); | |||
3556 | return isl_upoly_degree(poly->upoly, ovar, ovar + nvar); | |||
3557 | } | |||
3558 | ||||
3559 | __isl_give struct isl_upoly *isl_upoly_coeff(__isl_keep struct isl_upoly *up, | |||
3560 | unsigned pos, int deg) | |||
3561 | { | |||
3562 | int i; | |||
3563 | struct isl_upoly_rec *rec; | |||
3564 | ||||
3565 | if (!up) | |||
3566 | return NULL((void*)0); | |||
3567 | ||||
3568 | if (isl_upoly_is_cst(up) || up->var < pos) { | |||
3569 | if (deg == 0) | |||
3570 | return isl_upoly_copy(up); | |||
3571 | else | |||
3572 | return isl_upoly_zero(up->ctx); | |||
3573 | } | |||
3574 | ||||
3575 | rec = isl_upoly_as_rec(up); | |||
3576 | if (!rec) | |||
3577 | return NULL((void*)0); | |||
3578 | ||||
3579 | if (up->var == pos) { | |||
3580 | if (deg < rec->n) | |||
3581 | return isl_upoly_copy(rec->p[deg]); | |||
3582 | else | |||
3583 | return isl_upoly_zero(up->ctx); | |||
3584 | } | |||
3585 | ||||
3586 | up = isl_upoly_copy(up); | |||
3587 | up = isl_upoly_cow(up); | |||
3588 | rec = isl_upoly_as_rec(up); | |||
3589 | if (!rec) | |||
3590 | goto error; | |||
3591 | ||||
3592 | for (i = 0; i < rec->n; ++i) { | |||
3593 | struct isl_upoly *t; | |||
3594 | t = isl_upoly_coeff(rec->p[i], pos, deg); | |||
3595 | if (!t) | |||
3596 | goto error; | |||
3597 | isl_upoly_free(rec->p[i]); | |||
3598 | rec->p[i] = t; | |||
3599 | } | |||
3600 | ||||
3601 | return up; | |||
3602 | error: | |||
3603 | isl_upoly_free(up); | |||
3604 | return NULL((void*)0); | |||
3605 | } | |||
3606 | ||||
3607 | /* Return coefficient of power "deg" of variable "t_pos" of type "type". | |||
3608 | */ | |||
3609 | __isl_give isl_qpolynomial *isl_qpolynomial_coeff( | |||
3610 | __isl_keep isl_qpolynomial *qp, | |||
3611 | enum isl_dim_type type, unsigned t_pos, int deg) | |||
3612 | { | |||
3613 | unsigned g_pos; | |||
3614 | struct isl_upoly *up; | |||
3615 | isl_qpolynomial *c; | |||
3616 | ||||
3617 | if (!qp) | |||
3618 | return NULL((void*)0); | |||
3619 | ||||
3620 | if (type == isl_dim_out) | |||
3621 | isl_die(qp->div->ctx, isl_error_invalid,do { isl_handle_error(qp->div->ctx, isl_error_invalid, "output/set dimension does not have a coefficient" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3623); return ((void*)0); } while (0) | |||
3622 | "output/set dimension does not have a coefficient",do { isl_handle_error(qp->div->ctx, isl_error_invalid, "output/set dimension does not have a coefficient" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3623); return ((void*)0); } while (0) | |||
3623 | return NULL)do { isl_handle_error(qp->div->ctx, isl_error_invalid, "output/set dimension does not have a coefficient" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3623); return ((void*)0); } while (0); | |||
3624 | if (type == isl_dim_in) | |||
3625 | type = isl_dim_set; | |||
3626 | ||||
3627 | isl_assert(qp->div->ctx, t_pos < isl_space_dim(qp->dim, type),do { if (t_pos < isl_space_dim(qp->dim, type)) break; do { isl_handle_error(qp->div->ctx, isl_error_unknown, "Assertion \"" "t_pos < isl_space_dim(qp->dim, type)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3628); return ((void*)0); } while (0); } while (0) | |||
3628 | return NULL)do { if (t_pos < isl_space_dim(qp->dim, type)) break; do { isl_handle_error(qp->div->ctx, isl_error_unknown, "Assertion \"" "t_pos < isl_space_dim(qp->dim, type)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3628); return ((void*)0); } while (0); } while (0); | |||
3629 | ||||
3630 | g_pos = pos(qp->dim, type) + t_pos; | |||
3631 | up = isl_upoly_coeff(qp->upoly, g_pos, deg); | |||
3632 | ||||
3633 | c = isl_qpolynomial_alloc(isl_space_copy(qp->dim), qp->div->n_row, up); | |||
3634 | if (!c) | |||
3635 | return NULL((void*)0); | |||
3636 | isl_mat_free(c->div); | |||
3637 | c->div = isl_mat_copy(qp->div); | |||
3638 | if (!c->div) | |||
3639 | goto error; | |||
3640 | return c; | |||
3641 | error: | |||
3642 | isl_qpolynomial_free(c); | |||
3643 | return NULL((void*)0); | |||
3644 | } | |||
3645 | ||||
3646 | /* Homogenize the polynomial in the variables first (inclusive) up to | |||
3647 | * last (exclusive) by inserting powers of variable first. | |||
3648 | * Variable first is assumed not to appear in the input. | |||
3649 | */ | |||
3650 | __isl_give struct isl_upoly *isl_upoly_homogenize( | |||
3651 | __isl_take struct isl_upoly *up, int deg, int target, | |||
3652 | int first, int last) | |||
3653 | { | |||
3654 | int i; | |||
3655 | struct isl_upoly_rec *rec; | |||
3656 | ||||
3657 | if (!up) | |||
3658 | return NULL((void*)0); | |||
3659 | if (isl_upoly_is_zero(up)) | |||
3660 | return up; | |||
3661 | if (deg == target) | |||
3662 | return up; | |||
3663 | if (isl_upoly_is_cst(up) || up->var < first) { | |||
3664 | struct isl_upoly *hom; | |||
3665 | ||||
3666 | hom = isl_upoly_var_pow(up->ctx, first, target - deg); | |||
3667 | if (!hom) | |||
3668 | goto error; | |||
3669 | rec = isl_upoly_as_rec(hom); | |||
3670 | rec->p[target - deg] = isl_upoly_mul(rec->p[target - deg], up); | |||
3671 | ||||
3672 | return hom; | |||
3673 | } | |||
3674 | ||||
3675 | up = isl_upoly_cow(up); | |||
3676 | rec = isl_upoly_as_rec(up); | |||
3677 | if (!rec) | |||
3678 | goto error; | |||
3679 | ||||
3680 | for (i = 0; i < rec->n; ++i) { | |||
3681 | if (isl_upoly_is_zero(rec->p[i])) | |||
3682 | continue; | |||
3683 | rec->p[i] = isl_upoly_homogenize(rec->p[i], | |||
3684 | up->var < last ? deg + i : i, target, | |||
3685 | first, last); | |||
3686 | if (!rec->p[i]) | |||
3687 | goto error; | |||
3688 | } | |||
3689 | ||||
3690 | return up; | |||
3691 | error: | |||
3692 | isl_upoly_free(up); | |||
3693 | return NULL((void*)0); | |||
3694 | } | |||
3695 | ||||
3696 | /* Homogenize the polynomial in the set variables by introducing | |||
3697 | * powers of an extra set variable at position 0. | |||
3698 | */ | |||
3699 | __isl_give isl_qpolynomial *isl_qpolynomial_homogenize( | |||
3700 | __isl_take isl_qpolynomial *poly) | |||
3701 | { | |||
3702 | unsigned ovar; | |||
3703 | unsigned nvar; | |||
3704 | int deg = isl_qpolynomial_degree(poly); | |||
3705 | ||||
3706 | if (deg < -1) | |||
3707 | goto error; | |||
3708 | ||||
3709 | poly = isl_qpolynomial_insert_dims(poly, isl_dim_in, 0, 1); | |||
3710 | poly = isl_qpolynomial_cow(poly); | |||
3711 | if (!poly) | |||
3712 | goto error; | |||
3713 | ||||
3714 | ovar = isl_space_offset(poly->dim, isl_dim_set); | |||
3715 | nvar = isl_space_dim(poly->dim, isl_dim_set); | |||
3716 | poly->upoly = isl_upoly_homogenize(poly->upoly, 0, deg, | |||
3717 | ovar, ovar + nvar); | |||
3718 | if (!poly->upoly) | |||
3719 | goto error; | |||
3720 | ||||
3721 | return poly; | |||
3722 | error: | |||
3723 | isl_qpolynomial_free(poly); | |||
3724 | return NULL((void*)0); | |||
3725 | } | |||
3726 | ||||
3727 | __isl_give isl_term *isl_term_alloc(__isl_take isl_space *dim, | |||
3728 | __isl_take isl_mat *div) | |||
3729 | { | |||
3730 | isl_term *term; | |||
3731 | int n; | |||
3732 | ||||
3733 | if (!dim || !div) | |||
3734 | goto error; | |||
3735 | ||||
3736 | n = isl_space_dim(dim, isl_dim_all) + div->n_row; | |||
3737 | ||||
3738 | term = isl_calloc(dim->ctx, struct isl_term,((struct isl_term *)isl_calloc_or_die(dim->ctx, 1, sizeof( struct isl_term) + (n - 1) * sizeof(int))) | |||
3739 | sizeof(struct isl_term) + (n - 1) * sizeof(int))((struct isl_term *)isl_calloc_or_die(dim->ctx, 1, sizeof( struct isl_term) + (n - 1) * sizeof(int))); | |||
3740 | if (!term) | |||
3741 | goto error; | |||
3742 | ||||
3743 | term->ref = 1; | |||
3744 | term->dim = dim; | |||
3745 | term->div = div; | |||
3746 | isl_int_init(term->n)isl_sioimath_init((term->n)); | |||
3747 | isl_int_init(term->d)isl_sioimath_init((term->d)); | |||
3748 | ||||
3749 | return term; | |||
3750 | error: | |||
3751 | isl_space_free(dim); | |||
3752 | isl_mat_free(div); | |||
3753 | return NULL((void*)0); | |||
3754 | } | |||
3755 | ||||
3756 | __isl_give isl_term *isl_term_copy(__isl_keep isl_term *term) | |||
3757 | { | |||
3758 | if (!term) | |||
3759 | return NULL((void*)0); | |||
3760 | ||||
3761 | term->ref++; | |||
3762 | return term; | |||
3763 | } | |||
3764 | ||||
3765 | __isl_give isl_term *isl_term_dup(__isl_keep isl_term *term) | |||
3766 | { | |||
3767 | int i; | |||
3768 | isl_term *dup; | |||
3769 | unsigned total; | |||
3770 | ||||
3771 | if (!term) | |||
3772 | return NULL((void*)0); | |||
3773 | ||||
3774 | total = isl_space_dim(term->dim, isl_dim_all) + term->div->n_row; | |||
3775 | ||||
3776 | dup = isl_term_alloc(isl_space_copy(term->dim), isl_mat_copy(term->div)); | |||
3777 | if (!dup) | |||
3778 | return NULL((void*)0); | |||
3779 | ||||
3780 | isl_int_set(dup->n, term->n)isl_sioimath_set((dup->n), *(term->n)); | |||
3781 | isl_int_set(dup->d, term->d)isl_sioimath_set((dup->d), *(term->d)); | |||
3782 | ||||
3783 | for (i = 0; i < total; ++i) | |||
3784 | dup->pow[i] = term->pow[i]; | |||
3785 | ||||
3786 | return dup; | |||
3787 | } | |||
3788 | ||||
3789 | __isl_give isl_term *isl_term_cow(__isl_take isl_term *term) | |||
3790 | { | |||
3791 | if (!term) | |||
3792 | return NULL((void*)0); | |||
3793 | ||||
3794 | if (term->ref == 1) | |||
3795 | return term; | |||
3796 | term->ref--; | |||
3797 | return isl_term_dup(term); | |||
3798 | } | |||
3799 | ||||
3800 | void isl_term_free(__isl_take isl_term *term) | |||
3801 | { | |||
3802 | if (!term) | |||
3803 | return; | |||
3804 | ||||
3805 | if (--term->ref > 0) | |||
3806 | return; | |||
3807 | ||||
3808 | isl_space_free(term->dim); | |||
3809 | isl_mat_free(term->div); | |||
3810 | isl_int_clear(term->n)isl_sioimath_clear((term->n)); | |||
3811 | isl_int_clear(term->d)isl_sioimath_clear((term->d)); | |||
3812 | free(term); | |||
3813 | } | |||
3814 | ||||
3815 | unsigned isl_term_dim(__isl_keep isl_term *term, enum isl_dim_type type) | |||
3816 | { | |||
3817 | if (!term) | |||
3818 | return 0; | |||
3819 | ||||
3820 | switch (type) { | |||
3821 | case isl_dim_param: | |||
3822 | case isl_dim_in: | |||
3823 | case isl_dim_out: return isl_space_dim(term->dim, type); | |||
3824 | case isl_dim_div: return term->div->n_row; | |||
3825 | case isl_dim_all: return isl_space_dim(term->dim, isl_dim_all) + | |||
3826 | term->div->n_row; | |||
3827 | default: return 0; | |||
3828 | } | |||
3829 | } | |||
3830 | ||||
3831 | isl_ctx *isl_term_get_ctx(__isl_keep isl_term *term) | |||
3832 | { | |||
3833 | return term ? term->dim->ctx : NULL((void*)0); | |||
3834 | } | |||
3835 | ||||
3836 | void isl_term_get_num(__isl_keep isl_term *term, isl_int *n) | |||
3837 | { | |||
3838 | if (!term) | |||
3839 | return; | |||
3840 | isl_int_set(*n, term->n)isl_sioimath_set((*n), *(term->n)); | |||
3841 | } | |||
3842 | ||||
3843 | /* Return the coefficient of the term "term". | |||
3844 | */ | |||
3845 | __isl_give isl_val *isl_term_get_coefficient_val(__isl_keep isl_term *term) | |||
3846 | { | |||
3847 | if (!term) | |||
3848 | return NULL((void*)0); | |||
3849 | ||||
3850 | return isl_val_rat_from_isl_int(isl_term_get_ctx(term), | |||
3851 | term->n, term->d); | |||
3852 | } | |||
3853 | ||||
3854 | int isl_term_get_exp(__isl_keep isl_term *term, | |||
3855 | enum isl_dim_type type, unsigned pos) | |||
3856 | { | |||
3857 | if (!term) | |||
3858 | return -1; | |||
3859 | ||||
3860 | isl_assert(term->dim->ctx, pos < isl_term_dim(term, type), return -1)do { if (pos < isl_term_dim(term, type)) break; do { isl_handle_error (term->dim->ctx, isl_error_unknown, "Assertion \"" "pos < isl_term_dim(term, type)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3860); return -1; } while (0); } while (0); | |||
3861 | ||||
3862 | if (type >= isl_dim_set) | |||
3863 | pos += isl_space_dim(term->dim, isl_dim_param); | |||
3864 | if (type >= isl_dim_div) | |||
3865 | pos += isl_space_dim(term->dim, isl_dim_set); | |||
3866 | ||||
3867 | return term->pow[pos]; | |||
3868 | } | |||
3869 | ||||
3870 | __isl_give isl_aff *isl_term_get_div(__isl_keep isl_term *term, unsigned pos) | |||
3871 | { | |||
3872 | isl_local_space *ls; | |||
3873 | isl_aff *aff; | |||
3874 | ||||
3875 | if (!term) | |||
3876 | return NULL((void*)0); | |||
3877 | ||||
3878 | isl_assert(term->dim->ctx, pos < isl_term_dim(term, isl_dim_div),do { if (pos < isl_term_dim(term, isl_dim_div)) break; do { isl_handle_error(term->dim->ctx, isl_error_unknown, "Assertion \"" "pos < isl_term_dim(term, isl_dim_div)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3879); return ((void*)0); } while (0); } while (0) | |||
3879 | return NULL)do { if (pos < isl_term_dim(term, isl_dim_div)) break; do { isl_handle_error(term->dim->ctx, isl_error_unknown, "Assertion \"" "pos < isl_term_dim(term, isl_dim_div)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3879); return ((void*)0); } while (0); } while (0); | |||
3880 | ||||
3881 | ls = isl_local_space_alloc_div(isl_space_copy(term->dim), | |||
3882 | isl_mat_copy(term->div)); | |||
3883 | aff = isl_aff_alloc(ls); | |||
3884 | if (!aff) | |||
3885 | return NULL((void*)0); | |||
3886 | ||||
3887 | isl_seq_cpy(aff->v->el, term->div->row[pos], aff->v->size); | |||
3888 | ||||
3889 | aff = isl_aff_normalize(aff); | |||
3890 | ||||
3891 | return aff; | |||
3892 | } | |||
3893 | ||||
3894 | __isl_give isl_term *isl_upoly_foreach_term(__isl_keep struct isl_upoly *up, | |||
3895 | isl_stat (*fn)(__isl_take isl_term *term, void *user), | |||
3896 | __isl_take isl_term *term, void *user) | |||
3897 | { | |||
3898 | int i; | |||
3899 | struct isl_upoly_rec *rec; | |||
3900 | ||||
3901 | if (!up || !term) | |||
3902 | goto error; | |||
3903 | ||||
3904 | if (isl_upoly_is_zero(up)) | |||
3905 | return term; | |||
3906 | ||||
3907 | isl_assert(up->ctx, !isl_upoly_is_nan(up), goto error)do { if (!isl_upoly_is_nan(up)) break; do { isl_handle_error( up->ctx, isl_error_unknown, "Assertion \"" "!isl_upoly_is_nan(up)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3907); goto error; } while (0); } while (0); | |||
3908 | isl_assert(up->ctx, !isl_upoly_is_infty(up), goto error)do { if (!isl_upoly_is_infty(up)) break; do { isl_handle_error (up->ctx, isl_error_unknown, "Assertion \"" "!isl_upoly_is_infty(up)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3908); goto error; } while (0); } while (0); | |||
3909 | isl_assert(up->ctx, !isl_upoly_is_neginfty(up), goto error)do { if (!isl_upoly_is_neginfty(up)) break; do { isl_handle_error (up->ctx, isl_error_unknown, "Assertion \"" "!isl_upoly_is_neginfty(up)" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 3909); goto error; } while (0); } while (0); | |||
3910 | ||||
3911 | if (isl_upoly_is_cst(up)) { | |||
3912 | struct isl_upoly_cst *cst; | |||
3913 | cst = isl_upoly_as_cst(up); | |||
3914 | if (!cst) | |||
3915 | goto error; | |||
3916 | term = isl_term_cow(term); | |||
3917 | if (!term) | |||
3918 | goto error; | |||
3919 | isl_int_set(term->n, cst->n)isl_sioimath_set((term->n), *(cst->n)); | |||
3920 | isl_int_set(term->d, cst->d)isl_sioimath_set((term->d), *(cst->d)); | |||
3921 | if (fn(isl_term_copy(term), user) < 0) | |||
3922 | goto error; | |||
3923 | return term; | |||
3924 | } | |||
3925 | ||||
3926 | rec = isl_upoly_as_rec(up); | |||
3927 | if (!rec) | |||
3928 | goto error; | |||
3929 | ||||
3930 | for (i = 0; i < rec->n; ++i) { | |||
3931 | term = isl_term_cow(term); | |||
3932 | if (!term) | |||
3933 | goto error; | |||
3934 | term->pow[up->var] = i; | |||
3935 | term = isl_upoly_foreach_term(rec->p[i], fn, term, user); | |||
3936 | if (!term) | |||
3937 | goto error; | |||
3938 | } | |||
3939 | term->pow[up->var] = 0; | |||
3940 | ||||
3941 | return term; | |||
3942 | error: | |||
3943 | isl_term_free(term); | |||
3944 | return NULL((void*)0); | |||
3945 | } | |||
3946 | ||||
3947 | isl_stat isl_qpolynomial_foreach_term(__isl_keep isl_qpolynomial *qp, | |||
3948 | isl_stat (*fn)(__isl_take isl_term *term, void *user), void *user) | |||
3949 | { | |||
3950 | isl_term *term; | |||
3951 | ||||
3952 | if (!qp) | |||
3953 | return isl_stat_error; | |||
3954 | ||||
3955 | term = isl_term_alloc(isl_space_copy(qp->dim), isl_mat_copy(qp->div)); | |||
3956 | if (!term) | |||
3957 | return isl_stat_error; | |||
3958 | ||||
3959 | term = isl_upoly_foreach_term(qp->upoly, fn, term, user); | |||
3960 | ||||
3961 | isl_term_free(term); | |||
3962 | ||||
3963 | return term ? isl_stat_ok : isl_stat_error; | |||
3964 | } | |||
3965 | ||||
3966 | __isl_give isl_qpolynomial *isl_qpolynomial_from_term(__isl_take isl_term *term) | |||
3967 | { | |||
3968 | struct isl_upoly *up; | |||
3969 | isl_qpolynomial *qp; | |||
3970 | int i, n; | |||
3971 | ||||
3972 | if (!term) | |||
3973 | return NULL((void*)0); | |||
3974 | ||||
3975 | n = isl_space_dim(term->dim, isl_dim_all) + term->div->n_row; | |||
3976 | ||||
3977 | up = isl_upoly_rat_cst(term->dim->ctx, term->n, term->d); | |||
3978 | for (i = 0; i < n; ++i) { | |||
3979 | if (!term->pow[i]) | |||
3980 | continue; | |||
3981 | up = isl_upoly_mul(up, | |||
3982 | isl_upoly_var_pow(term->dim->ctx, i, term->pow[i])); | |||
3983 | } | |||
3984 | ||||
3985 | qp = isl_qpolynomial_alloc(isl_space_copy(term->dim), term->div->n_row, up); | |||
3986 | if (!qp) | |||
3987 | goto error; | |||
3988 | isl_mat_free(qp->div); | |||
3989 | qp->div = isl_mat_copy(term->div); | |||
3990 | if (!qp->div) | |||
3991 | goto error; | |||
3992 | ||||
3993 | isl_term_free(term); | |||
3994 | return qp; | |||
3995 | error: | |||
3996 | isl_qpolynomial_free(qp); | |||
3997 | isl_term_free(term); | |||
3998 | return NULL((void*)0); | |||
3999 | } | |||
4000 | ||||
4001 | __isl_give isl_qpolynomial *isl_qpolynomial_lift(__isl_take isl_qpolynomial *qp, | |||
4002 | __isl_take isl_space *dim) | |||
4003 | { | |||
4004 | int i; | |||
4005 | int extra; | |||
4006 | unsigned total; | |||
4007 | ||||
4008 | if (!qp || !dim) | |||
4009 | goto error; | |||
4010 | ||||
4011 | if (isl_space_is_equal(qp->dim, dim)) { | |||
4012 | isl_space_free(dim); | |||
4013 | return qp; | |||
4014 | } | |||
4015 | ||||
4016 | qp = isl_qpolynomial_cow(qp); | |||
4017 | if (!qp) | |||
4018 | goto error; | |||
4019 | ||||
4020 | extra = isl_space_dim(dim, isl_dim_set) - | |||
4021 | isl_space_dim(qp->dim, isl_dim_set); | |||
4022 | total = isl_space_dim(qp->dim, isl_dim_all); | |||
4023 | if (qp->div->n_row) { | |||
4024 | int *exp; | |||
4025 | ||||
4026 | exp = isl_alloc_array(qp->div->ctx, int, qp->div->n_row)((int *)isl_malloc_or_die(qp->div->ctx, (qp->div-> n_row)*sizeof(int))); | |||
4027 | if (!exp) | |||
4028 | goto error; | |||
4029 | for (i = 0; i < qp->div->n_row; ++i) | |||
4030 | exp[i] = extra + i; | |||
4031 | qp->upoly = expand(qp->upoly, exp, total); | |||
4032 | free(exp); | |||
4033 | if (!qp->upoly) | |||
4034 | goto error; | |||
4035 | } | |||
4036 | qp->div = isl_mat_insert_cols(qp->div, 2 + total, extra); | |||
4037 | if (!qp->div) | |||
4038 | goto error; | |||
4039 | for (i = 0; i < qp->div->n_row; ++i) | |||
4040 | isl_seq_clr(qp->div->row[i] + 2 + total, extra); | |||
4041 | ||||
4042 | isl_space_free(qp->dim); | |||
4043 | qp->dim = dim; | |||
4044 | ||||
4045 | return qp; | |||
4046 | error: | |||
4047 | isl_space_free(dim); | |||
4048 | isl_qpolynomial_free(qp); | |||
4049 | return NULL((void*)0); | |||
4050 | } | |||
4051 | ||||
4052 | /* For each parameter or variable that does not appear in qp, | |||
4053 | * first eliminate the variable from all constraints and then set it to zero. | |||
4054 | */ | |||
4055 | static __isl_give isl_setisl_map *fix_inactive(__isl_take isl_setisl_map *set, | |||
4056 | __isl_keep isl_qpolynomial *qp) | |||
4057 | { | |||
4058 | int *active = NULL((void*)0); | |||
4059 | int i; | |||
4060 | int d; | |||
4061 | unsigned nparam; | |||
4062 | unsigned nvar; | |||
4063 | ||||
4064 | if (!set || !qp) | |||
4065 | goto error; | |||
4066 | ||||
4067 | d = isl_space_dim(set->dim, isl_dim_all); | |||
4068 | active = isl_calloc_array(set->ctx, int, d)((int *)isl_calloc_or_die(set->ctx, d, sizeof(int))); | |||
4069 | if (set_active(qp, active) < 0) | |||
4070 | goto error; | |||
4071 | ||||
4072 | for (i = 0; i < d; ++i) | |||
4073 | if (!active[i]) | |||
4074 | break; | |||
4075 | ||||
4076 | if (i == d) { | |||
4077 | free(active); | |||
4078 | return set; | |||
4079 | } | |||
4080 | ||||
4081 | nparam = isl_space_dim(set->dim, isl_dim_param); | |||
4082 | nvar = isl_space_dim(set->dim, isl_dim_set); | |||
4083 | for (i = 0; i < nparam; ++i) { | |||
4084 | if (active[i]) | |||
4085 | continue; | |||
4086 | set = isl_set_eliminate(set, isl_dim_param, i, 1); | |||
4087 | set = isl_set_fix_si(set, isl_dim_param, i, 0); | |||
4088 | } | |||
4089 | for (i = 0; i < nvar; ++i) { | |||
4090 | if (active[nparam + i]) | |||
4091 | continue; | |||
4092 | set = isl_set_eliminate(set, isl_dim_set, i, 1); | |||
4093 | set = isl_set_fix_si(set, isl_dim_set, i, 0); | |||
4094 | } | |||
4095 | ||||
4096 | free(active); | |||
4097 | ||||
4098 | return set; | |||
4099 | error: | |||
4100 | free(active); | |||
4101 | isl_set_free(set); | |||
4102 | return NULL((void*)0); | |||
4103 | } | |||
4104 | ||||
4105 | struct isl_opt_data { | |||
4106 | isl_qpolynomial *qp; | |||
4107 | int first; | |||
4108 | isl_val *opt; | |||
4109 | int max; | |||
4110 | }; | |||
4111 | ||||
4112 | static isl_stat opt_fn(__isl_take isl_point *pnt, void *user) | |||
4113 | { | |||
4114 | struct isl_opt_data *data = (struct isl_opt_data *)user; | |||
4115 | isl_val *val; | |||
4116 | ||||
4117 | val = isl_qpolynomial_eval(isl_qpolynomial_copy(data->qp), pnt); | |||
4118 | if (data->first) { | |||
4119 | data->first = 0; | |||
4120 | data->opt = val; | |||
4121 | } else if (data->max) { | |||
4122 | data->opt = isl_val_max(data->opt, val); | |||
4123 | } else { | |||
4124 | data->opt = isl_val_min(data->opt, val); | |||
4125 | } | |||
4126 | ||||
4127 | return isl_stat_ok; | |||
4128 | } | |||
4129 | ||||
4130 | __isl_give isl_val *isl_qpolynomial_opt_on_domain( | |||
4131 | __isl_take isl_qpolynomial *qp, __isl_take isl_setisl_map *set, int max) | |||
4132 | { | |||
4133 | struct isl_opt_data data = { NULL((void*)0), 1, NULL((void*)0), max }; | |||
4134 | ||||
4135 | if (!set || !qp) | |||
4136 | goto error; | |||
4137 | ||||
4138 | if (isl_upoly_is_cst(qp->upoly)) { | |||
4139 | isl_set_free(set); | |||
4140 | data.opt = isl_qpolynomial_get_constant_val(qp); | |||
4141 | isl_qpolynomial_free(qp); | |||
4142 | return data.opt; | |||
4143 | } | |||
4144 | ||||
4145 | set = fix_inactive(set, qp); | |||
4146 | ||||
4147 | data.qp = qp; | |||
4148 | if (isl_set_foreach_point(set, opt_fn, &data) < 0) | |||
4149 | goto error; | |||
4150 | ||||
4151 | if (data.first) | |||
4152 | data.opt = isl_val_zero(isl_set_get_ctx(set)); | |||
4153 | ||||
4154 | isl_set_free(set); | |||
4155 | isl_qpolynomial_free(qp); | |||
4156 | return data.opt; | |||
4157 | error: | |||
4158 | isl_set_free(set); | |||
4159 | isl_qpolynomial_free(qp); | |||
4160 | isl_val_free(data.opt); | |||
4161 | return NULL((void*)0); | |||
4162 | } | |||
4163 | ||||
4164 | __isl_give isl_qpolynomial *isl_qpolynomial_morph_domain( | |||
4165 | __isl_take isl_qpolynomial *qp, __isl_take isl_morph *morph) | |||
4166 | { | |||
4167 | int i; | |||
4168 | int n_sub; | |||
4169 | isl_ctx *ctx; | |||
4170 | struct isl_upoly **subs; | |||
4171 | isl_mat *mat, *diag; | |||
4172 | ||||
4173 | qp = isl_qpolynomial_cow(qp); | |||
4174 | if (!qp || !morph) | |||
4175 | goto error; | |||
4176 | ||||
4177 | ctx = qp->dim->ctx; | |||
4178 | isl_assert(ctx, isl_space_is_equal(qp->dim, morph->dom->dim), goto error)do { if (isl_space_is_equal(qp->dim, morph->dom->dim )) break; do { isl_handle_error(ctx, isl_error_unknown, "Assertion \"" "isl_space_is_equal(qp->dim, morph->dom->dim)" "\" failed" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 4178); goto error; } while (0); } while (0); | |||
4179 | ||||
4180 | n_sub = morph->inv->n_row - 1; | |||
4181 | if (morph->inv->n_row != morph->inv->n_col) | |||
4182 | n_sub += qp->div->n_row; | |||
4183 | subs = isl_calloc_array(ctx, struct isl_upoly *, n_sub)((struct isl_upoly * *)isl_calloc_or_die(ctx, n_sub, sizeof(struct isl_upoly *))); | |||
4184 | if (n_sub && !subs) | |||
4185 | goto error; | |||
4186 | ||||
4187 | for (i = 0; 1 + i < morph->inv->n_row; ++i) | |||
4188 | subs[i] = isl_upoly_from_affine(ctx, morph->inv->row[1 + i], | |||
4189 | morph->inv->row[0][0], morph->inv->n_col); | |||
4190 | if (morph->inv->n_row != morph->inv->n_col) | |||
4191 | for (i = 0; i < qp->div->n_row; ++i) | |||
4192 | subs[morph->inv->n_row - 1 + i] = | |||
4193 | isl_upoly_var_pow(ctx, morph->inv->n_col - 1 + i, 1); | |||
4194 | ||||
4195 | qp->upoly = isl_upoly_subs(qp->upoly, 0, n_sub, subs); | |||
4196 | ||||
4197 | for (i = 0; i < n_sub; ++i) | |||
4198 | isl_upoly_free(subs[i]); | |||
4199 | free(subs); | |||
4200 | ||||
4201 | diag = isl_mat_diag(ctx, 1, morph->inv->row[0][0]); | |||
4202 | mat = isl_mat_diagonal(diag, isl_mat_copy(morph->inv)); | |||
4203 | diag = isl_mat_diag(ctx, qp->div->n_row, morph->inv->row[0][0]); | |||
4204 | mat = isl_mat_diagonal(mat, diag); | |||
4205 | qp->div = isl_mat_product(qp->div, mat); | |||
4206 | isl_space_free(qp->dim); | |||
4207 | qp->dim = isl_space_copy(morph->ran->dim); | |||
4208 | ||||
4209 | if (!qp->upoly || !qp->div || !qp->dim) | |||
4210 | goto error; | |||
4211 | ||||
4212 | isl_morph_free(morph); | |||
4213 | ||||
4214 | return qp; | |||
4215 | error: | |||
4216 | isl_qpolynomial_free(qp); | |||
4217 | isl_morph_free(morph); | |||
4218 | return NULL((void*)0); | |||
4219 | } | |||
4220 | ||||
4221 | __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_mul( | |||
4222 | __isl_take isl_union_pw_qpolynomial *upwqp1, | |||
4223 | __isl_take isl_union_pw_qpolynomial *upwqp2) | |||
4224 | { | |||
4225 | return isl_union_pw_qpolynomial_match_bin_op(upwqp1, upwqp2, | |||
4226 | &isl_pw_qpolynomial_mul); | |||
4227 | } | |||
4228 | ||||
4229 | /* Reorder the dimension of "qp" according to the given reordering. | |||
4230 | */ | |||
4231 | __isl_give isl_qpolynomial *isl_qpolynomial_realign_domain( | |||
4232 | __isl_take isl_qpolynomial *qp, __isl_take isl_reordering *r) | |||
4233 | { | |||
4234 | isl_space *space; | |||
4235 | ||||
4236 | qp = isl_qpolynomial_cow(qp); | |||
4237 | if (!qp) | |||
4238 | goto error; | |||
4239 | ||||
4240 | r = isl_reordering_extend(r, qp->div->n_row); | |||
4241 | if (!r) | |||
4242 | goto error; | |||
4243 | ||||
4244 | qp->div = isl_local_reorder(qp->div, isl_reordering_copy(r)); | |||
4245 | if (!qp->div) | |||
4246 | goto error; | |||
4247 | ||||
4248 | qp->upoly = reorder(qp->upoly, r->pos); | |||
4249 | if (!qp->upoly) | |||
4250 | goto error; | |||
4251 | ||||
4252 | space = isl_reordering_get_space(r); | |||
4253 | qp = isl_qpolynomial_reset_domain_space(qp, space); | |||
4254 | ||||
4255 | isl_reordering_free(r); | |||
4256 | return qp; | |||
4257 | error: | |||
4258 | isl_qpolynomial_free(qp); | |||
4259 | isl_reordering_free(r); | |||
4260 | return NULL((void*)0); | |||
4261 | } | |||
4262 | ||||
4263 | __isl_give isl_qpolynomial *isl_qpolynomial_align_params( | |||
4264 | __isl_take isl_qpolynomial *qp, __isl_take isl_space *model) | |||
4265 | { | |||
4266 | isl_bool equal_params; | |||
4267 | ||||
4268 | if (!qp || !model) | |||
4269 | goto error; | |||
4270 | ||||
4271 | equal_params = isl_space_has_equal_params(qp->dim, model); | |||
4272 | if (equal_params < 0) | |||
4273 | goto error; | |||
4274 | if (!equal_params) { | |||
4275 | isl_reordering *exp; | |||
4276 | ||||
4277 | exp = isl_parameter_alignment_reordering(qp->dim, model); | |||
4278 | exp = isl_reordering_extend_space(exp, | |||
4279 | isl_qpolynomial_get_domain_space(qp)); | |||
4280 | qp = isl_qpolynomial_realign_domain(qp, exp); | |||
4281 | } | |||
4282 | ||||
4283 | isl_space_free(model); | |||
4284 | return qp; | |||
4285 | error: | |||
4286 | isl_space_free(model); | |||
4287 | isl_qpolynomial_free(qp); | |||
4288 | return NULL((void*)0); | |||
4289 | } | |||
4290 | ||||
4291 | struct isl_split_periods_data { | |||
4292 | int max_periods; | |||
4293 | isl_pw_qpolynomial *res; | |||
4294 | }; | |||
4295 | ||||
4296 | /* Create a slice where the integer division "div" has the fixed value "v". | |||
4297 | * In particular, if "div" refers to floor(f/m), then create a slice | |||
4298 | * | |||
4299 | * m v <= f <= m v + (m - 1) | |||
4300 | * | |||
4301 | * or | |||
4302 | * | |||
4303 | * f - m v >= 0 | |||
4304 | * -f + m v + (m - 1) >= 0 | |||
4305 | */ | |||
4306 | static __isl_give isl_setisl_map *set_div_slice(__isl_take isl_space *dim, | |||
4307 | __isl_keep isl_qpolynomial *qp, int div, isl_int v) | |||
4308 | { | |||
4309 | int total; | |||
4310 | isl_basic_setisl_basic_map *bset = NULL((void*)0); | |||
4311 | int k; | |||
4312 | ||||
4313 | if (!dim || !qp) | |||
4314 | goto error; | |||
4315 | ||||
4316 | total = isl_space_dim(dim, isl_dim_all); | |||
4317 | bset = isl_basic_set_alloc_space(isl_space_copy(dim), 0, 0, 2); | |||
4318 | ||||
4319 | k = isl_basic_set_alloc_inequality(bset); | |||
4320 | if (k < 0) | |||
4321 | goto error; | |||
4322 | isl_seq_cpy(bset->ineq[k], qp->div->row[div] + 1, 1 + total); | |||
4323 | isl_int_submul(bset->ineq[k][0], v, qp->div->row[div][0])isl_sioimath_submul((bset->ineq[k][0]), *(v), *(qp->div ->row[div][0])); | |||
4324 | ||||
4325 | k = isl_basic_set_alloc_inequality(bset); | |||
4326 | if (k < 0) | |||
4327 | goto error; | |||
4328 | isl_seq_neg(bset->ineq[k], qp->div->row[div] + 1, 1 + total); | |||
4329 | isl_int_addmul(bset->ineq[k][0], v, qp->div->row[div][0])isl_sioimath_addmul((bset->ineq[k][0]), *(v), *(qp->div ->row[div][0])); | |||
4330 | isl_int_add(bset->ineq[k][0], bset->ineq[k][0], qp->div->row[div][0])isl_sioimath_add((bset->ineq[k][0]), *(bset->ineq[k][0] ), *(qp->div->row[div][0])); | |||
4331 | isl_int_sub_ui(bset->ineq[k][0], bset->ineq[k][0], 1)isl_sioimath_sub_ui((bset->ineq[k][0]), *(bset->ineq[k] [0]), 1); | |||
4332 | ||||
4333 | isl_space_free(dim); | |||
4334 | return isl_set_from_basic_set(bset); | |||
4335 | error: | |||
4336 | isl_basic_set_free(bset); | |||
4337 | isl_space_free(dim); | |||
4338 | return NULL((void*)0); | |||
4339 | } | |||
4340 | ||||
4341 | static isl_stat split_periods(__isl_take isl_setisl_map *set, | |||
4342 | __isl_take isl_qpolynomial *qp, void *user); | |||
4343 | ||||
4344 | /* Create a slice of the domain "set" such that integer division "div" | |||
4345 | * has the fixed value "v" and add the results to data->res, | |||
4346 | * replacing the integer division by "v" in "qp". | |||
4347 | */ | |||
4348 | static isl_stat set_div(__isl_take isl_setisl_map *set, | |||
4349 | __isl_take isl_qpolynomial *qp, int div, isl_int v, | |||
4350 | struct isl_split_periods_data *data) | |||
4351 | { | |||
4352 | int i; | |||
4353 | int total; | |||
4354 | isl_setisl_map *slice; | |||
4355 | struct isl_upoly *cst; | |||
4356 | ||||
4357 | slice = set_div_slice(isl_set_get_space(set), qp, div, v); | |||
4358 | set = isl_set_intersect(set, slice); | |||
4359 | ||||
4360 | if (!qp) | |||
4361 | goto error; | |||
4362 | ||||
4363 | total = isl_space_dim(qp->dim, isl_dim_all); | |||
4364 | ||||
4365 | for (i = div + 1; i < qp->div->n_row; ++i) { | |||
4366 | if (isl_int_is_zero(qp->div->row[i][2 + total + div])(isl_sioimath_sgn(*(qp->div->row[i][2 + total + div])) == 0)) | |||
4367 | continue; | |||
4368 | isl_int_addmul(qp->div->row[i][1],isl_sioimath_addmul((qp->div->row[i][1]), *(qp->div-> row[i][2 + total + div]), *(v)) | |||
4369 | qp->div->row[i][2 + total + div], v)isl_sioimath_addmul((qp->div->row[i][1]), *(qp->div-> row[i][2 + total + div]), *(v)); | |||
4370 | isl_int_set_si(qp->div->row[i][2 + total + div], 0)isl_sioimath_set_si((qp->div->row[i][2 + total + div]), 0); | |||
4371 | } | |||
4372 | ||||
4373 | cst = isl_upoly_rat_cst(qp->dim->ctx, v, qp->dim->ctx->one); | |||
4374 | qp = substitute_div(qp, div, cst); | |||
4375 | ||||
4376 | return split_periods(set, qp, data); | |||
4377 | error: | |||
4378 | isl_set_free(set); | |||
4379 | isl_qpolynomial_free(qp); | |||
4380 | return isl_stat_error; | |||
4381 | } | |||
4382 | ||||
4383 | /* Split the domain "set" such that integer division "div" | |||
4384 | * has a fixed value (ranging from "min" to "max") on each slice | |||
4385 | * and add the results to data->res. | |||
4386 | */ | |||
4387 | static isl_stat split_div(__isl_take isl_setisl_map *set, | |||
4388 | __isl_take isl_qpolynomial *qp, int div, isl_int min, isl_int max, | |||
4389 | struct isl_split_periods_data *data) | |||
4390 | { | |||
4391 | for (; isl_int_le(min, max)(isl_sioimath_cmp(*(min), *(max)) <= 0); isl_int_add_ui(min, min, 1)isl_sioimath_add_ui((min), *(min), 1)) { | |||
4392 | isl_setisl_map *set_i = isl_set_copy(set); | |||
4393 | isl_qpolynomial *qp_i = isl_qpolynomial_copy(qp); | |||
4394 | ||||
4395 | if (set_div(set_i, qp_i, div, min, data) < 0) | |||
4396 | goto error; | |||
4397 | } | |||
4398 | isl_set_free(set); | |||
4399 | isl_qpolynomial_free(qp); | |||
4400 | return isl_stat_ok; | |||
4401 | error: | |||
4402 | isl_set_free(set); | |||
4403 | isl_qpolynomial_free(qp); | |||
4404 | return isl_stat_error; | |||
4405 | } | |||
4406 | ||||
4407 | /* If "qp" refers to any integer division | |||
4408 | * that can only attain "max_periods" distinct values on "set" | |||
4409 | * then split the domain along those distinct values. | |||
4410 | * Add the results (or the original if no splitting occurs) | |||
4411 | * to data->res. | |||
4412 | */ | |||
4413 | static isl_stat split_periods(__isl_take isl_setisl_map *set, | |||
4414 | __isl_take isl_qpolynomial *qp, void *user) | |||
4415 | { | |||
4416 | int i; | |||
4417 | isl_pw_qpolynomial *pwqp; | |||
4418 | struct isl_split_periods_data *data; | |||
4419 | isl_int min, max; | |||
4420 | int total; | |||
4421 | isl_stat r = isl_stat_ok; | |||
4422 | ||||
4423 | data = (struct isl_split_periods_data *)user; | |||
4424 | ||||
4425 | if (!set || !qp) | |||
4426 | goto error; | |||
4427 | ||||
4428 | if (qp->div->n_row == 0) { | |||
4429 | pwqp = isl_pw_qpolynomial_alloc(set, qp); | |||
4430 | data->res = isl_pw_qpolynomial_add_disjoint(data->res, pwqp); | |||
4431 | return isl_stat_ok; | |||
4432 | } | |||
4433 | ||||
4434 | isl_int_init(min)isl_sioimath_init((min)); | |||
4435 | isl_int_init(max)isl_sioimath_init((max)); | |||
4436 | total = isl_space_dim(qp->dim, isl_dim_all); | |||
4437 | for (i = 0; i < qp->div->n_row; ++i) { | |||
4438 | enum isl_lp_result lp_res; | |||
4439 | ||||
4440 | if (isl_seq_first_non_zero(qp->div->row[i] + 2 + total, | |||
4441 | qp->div->n_row) != -1) | |||
4442 | continue; | |||
4443 | ||||
4444 | lp_res = isl_set_solve_lp(set, 0, qp->div->row[i] + 1, | |||
4445 | set->ctx->one, &min, NULL((void*)0), NULL((void*)0)); | |||
4446 | if (lp_res == isl_lp_error) | |||
4447 | goto error2; | |||
4448 | if (lp_res == isl_lp_unbounded || lp_res == isl_lp_empty) | |||
4449 | continue; | |||
4450 | isl_int_fdiv_q(min, min, qp->div->row[i][0])isl_sioimath_fdiv_q((min), *(min), *(qp->div->row[i][0] )); | |||
4451 | ||||
4452 | lp_res = isl_set_solve_lp(set, 1, qp->div->row[i] + 1, | |||
4453 | set->ctx->one, &max, NULL((void*)0), NULL((void*)0)); | |||
4454 | if (lp_res == isl_lp_error) | |||
4455 | goto error2; | |||
4456 | if (lp_res == isl_lp_unbounded || lp_res == isl_lp_empty) | |||
4457 | continue; | |||
4458 | isl_int_fdiv_q(max, max, qp->div->row[i][0])isl_sioimath_fdiv_q((max), *(max), *(qp->div->row[i][0] )); | |||
4459 | ||||
4460 | isl_int_sub(max, max, min)isl_sioimath_sub((max), *(max), *(min)); | |||
4461 | if (isl_int_cmp_si(max, data->max_periods)isl_sioimath_cmp_si(*(max), data->max_periods) < 0) { | |||
4462 | isl_int_add(max, max, min)isl_sioimath_add((max), *(max), *(min)); | |||
4463 | break; | |||
4464 | } | |||
4465 | } | |||
4466 | ||||
4467 | if (i < qp->div->n_row) { | |||
4468 | r = split_div(set, qp, i, min, max, data); | |||
4469 | } else { | |||
4470 | pwqp = isl_pw_qpolynomial_alloc(set, qp); | |||
4471 | data->res = isl_pw_qpolynomial_add_disjoint(data->res, pwqp); | |||
4472 | } | |||
4473 | ||||
4474 | isl_int_clear(max)isl_sioimath_clear((max)); | |||
4475 | isl_int_clear(min)isl_sioimath_clear((min)); | |||
4476 | ||||
4477 | return r; | |||
4478 | error2: | |||
4479 | isl_int_clear(max)isl_sioimath_clear((max)); | |||
4480 | isl_int_clear(min)isl_sioimath_clear((min)); | |||
4481 | error: | |||
4482 | isl_set_free(set); | |||
4483 | isl_qpolynomial_free(qp); | |||
4484 | return isl_stat_error; | |||
4485 | } | |||
4486 | ||||
4487 | /* If any quasi-polynomial in pwqp refers to any integer division | |||
4488 | * that can only attain "max_periods" distinct values on its domain | |||
4489 | * then split the domain along those distinct values. | |||
4490 | */ | |||
4491 | __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_split_periods( | |||
4492 | __isl_take isl_pw_qpolynomial *pwqp, int max_periods) | |||
4493 | { | |||
4494 | struct isl_split_periods_data data; | |||
4495 | ||||
4496 | data.max_periods = max_periods; | |||
4497 | data.res = isl_pw_qpolynomial_zero(isl_pw_qpolynomial_get_space(pwqp)); | |||
4498 | ||||
4499 | if (isl_pw_qpolynomial_foreach_piece(pwqp, &split_periods, &data) < 0) | |||
4500 | goto error; | |||
4501 | ||||
4502 | isl_pw_qpolynomial_free(pwqp); | |||
4503 | ||||
4504 | return data.res; | |||
4505 | error: | |||
4506 | isl_pw_qpolynomial_free(data.res); | |||
4507 | isl_pw_qpolynomial_free(pwqp); | |||
4508 | return NULL((void*)0); | |||
4509 | } | |||
4510 | ||||
4511 | /* Construct a piecewise quasipolynomial that is constant on the given | |||
4512 | * domain. In particular, it is | |||
4513 | * 0 if cst == 0 | |||
4514 | * 1 if cst == 1 | |||
4515 | * infinity if cst == -1 | |||
4516 | * | |||
4517 | * If cst == -1, then explicitly check whether the domain is empty and, | |||
4518 | * if so, return 0 instead. | |||
4519 | */ | |||
4520 | static __isl_give isl_pw_qpolynomial *constant_on_domain( | |||
4521 | __isl_take isl_basic_setisl_basic_map *bset, int cst) | |||
4522 | { | |||
4523 | isl_space *dim; | |||
4524 | isl_qpolynomial *qp; | |||
4525 | ||||
4526 | if (cst < 0 && isl_basic_set_is_empty(bset) == isl_bool_true) | |||
4527 | cst = 0; | |||
4528 | if (!bset) | |||
4529 | return NULL((void*)0); | |||
4530 | ||||
4531 | bset = isl_basic_set_params(bset); | |||
4532 | dim = isl_basic_set_get_space(bset); | |||
4533 | if (cst < 0) | |||
4534 | qp = isl_qpolynomial_infty_on_domain(dim); | |||
4535 | else if (cst == 0) | |||
4536 | qp = isl_qpolynomial_zero_on_domain(dim); | |||
4537 | else | |||
4538 | qp = isl_qpolynomial_one_on_domain(dim); | |||
4539 | return isl_pw_qpolynomial_alloc(isl_set_from_basic_set(bset), qp); | |||
4540 | } | |||
4541 | ||||
4542 | /* Factor bset, call fn on each of the factors and return the product. | |||
4543 | * | |||
4544 | * If no factors can be found, simply call fn on the input. | |||
4545 | * Otherwise, construct the factors based on the factorizer, | |||
4546 | * call fn on each factor and compute the product. | |||
4547 | */ | |||
4548 | static __isl_give isl_pw_qpolynomial *compressed_multiplicative_call( | |||
4549 | __isl_take isl_basic_setisl_basic_map *bset, | |||
4550 | __isl_give isl_pw_qpolynomial *(*fn)(__isl_take isl_basic_setisl_basic_map *bset)) | |||
4551 | { | |||
4552 | int i, n; | |||
4553 | isl_space *space; | |||
4554 | isl_setisl_map *set; | |||
4555 | isl_factorizer *f; | |||
4556 | isl_qpolynomial *qp; | |||
4557 | isl_pw_qpolynomial *pwqp; | |||
4558 | unsigned nparam; | |||
4559 | unsigned nvar; | |||
4560 | ||||
4561 | f = isl_basic_set_factorizer(bset); | |||
4562 | if (!f) | |||
4563 | goto error; | |||
4564 | if (f->n_group == 0) { | |||
4565 | isl_factorizer_free(f); | |||
4566 | return fn(bset); | |||
4567 | } | |||
4568 | ||||
4569 | nparam = isl_basic_set_dim(bset, isl_dim_param); | |||
4570 | nvar = isl_basic_set_dim(bset, isl_dim_set); | |||
4571 | ||||
4572 | space = isl_basic_set_get_space(bset); | |||
4573 | space = isl_space_params(space); | |||
4574 | set = isl_set_universe(isl_space_copy(space)); | |||
4575 | qp = isl_qpolynomial_one_on_domain(space); | |||
4576 | pwqp = isl_pw_qpolynomial_alloc(set, qp); | |||
4577 | ||||
4578 | bset = isl_morph_basic_set(isl_morph_copy(f->morph), bset); | |||
4579 | ||||
4580 | for (i = 0, n = 0; i < f->n_group; ++i) { | |||
4581 | isl_basic_setisl_basic_map *bset_i; | |||
4582 | isl_pw_qpolynomial *pwqp_i; | |||
4583 | ||||
4584 | bset_i = isl_basic_set_copy(bset); | |||
4585 | bset_i = isl_basic_set_drop_constraints_involving(bset_i, | |||
4586 | nparam + n + f->len[i], nvar - n - f->len[i]); | |||
4587 | bset_i = isl_basic_set_drop_constraints_involving(bset_i, | |||
4588 | nparam, n); | |||
4589 | bset_i = isl_basic_set_drop(bset_i, isl_dim_set, | |||
4590 | n + f->len[i], nvar - n - f->len[i]); | |||
4591 | bset_i = isl_basic_set_drop(bset_i, isl_dim_set, 0, n); | |||
4592 | ||||
4593 | pwqp_i = fn(bset_i); | |||
4594 | pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp_i); | |||
4595 | ||||
4596 | n += f->len[i]; | |||
4597 | } | |||
4598 | ||||
4599 | isl_basic_set_free(bset); | |||
4600 | isl_factorizer_free(f); | |||
4601 | ||||
4602 | return pwqp; | |||
4603 | error: | |||
4604 | isl_basic_set_free(bset); | |||
4605 | return NULL((void*)0); | |||
4606 | } | |||
4607 | ||||
4608 | /* Factor bset, call fn on each of the factors and return the product. | |||
4609 | * The function is assumed to evaluate to zero on empty domains, | |||
4610 | * to one on zero-dimensional domains and to infinity on unbounded domains | |||
4611 | * and will not be called explicitly on zero-dimensional or unbounded domains. | |||
4612 | * | |||
4613 | * We first check for some special cases and remove all equalities. | |||
4614 | * Then we hand over control to compressed_multiplicative_call. | |||
4615 | */ | |||
4616 | __isl_give isl_pw_qpolynomial *isl_basic_set_multiplicative_call( | |||
4617 | __isl_take isl_basic_setisl_basic_map *bset, | |||
4618 | __isl_give isl_pw_qpolynomial *(*fn)(__isl_take isl_basic_setisl_basic_map *bset)) | |||
4619 | { | |||
4620 | isl_bool bounded; | |||
4621 | isl_morph *morph; | |||
4622 | isl_pw_qpolynomial *pwqp; | |||
4623 | ||||
4624 | if (!bset) | |||
| ||||
4625 | return NULL((void*)0); | |||
4626 | ||||
4627 | if (isl_basic_set_plain_is_empty(bset)) | |||
4628 | return constant_on_domain(bset, 0); | |||
4629 | ||||
4630 | if (isl_basic_set_dim(bset, isl_dim_set) == 0) | |||
4631 | return constant_on_domain(bset, 1); | |||
4632 | ||||
4633 | bounded = isl_basic_set_is_bounded(bset); | |||
4634 | if (bounded < 0) | |||
4635 | goto error; | |||
4636 | if (!bounded) | |||
4637 | return constant_on_domain(bset, -1); | |||
4638 | ||||
4639 | if (bset->n_eq == 0) | |||
4640 | return compressed_multiplicative_call(bset, fn); | |||
4641 | ||||
4642 | morph = isl_basic_set_full_compression(bset); | |||
4643 | bset = isl_morph_basic_set(isl_morph_copy(morph), bset); | |||
4644 | ||||
4645 | pwqp = compressed_multiplicative_call(bset, fn); | |||
4646 | ||||
4647 | morph = isl_morph_dom_params(morph); | |||
4648 | morph = isl_morph_ran_params(morph); | |||
4649 | morph = isl_morph_inverse(morph); | |||
4650 | ||||
4651 | pwqp = isl_pw_qpolynomial_morph_domain(pwqp, morph); | |||
4652 | ||||
4653 | return pwqp; | |||
4654 | error: | |||
4655 | isl_basic_set_free(bset); | |||
4656 | return NULL((void*)0); | |||
4657 | } | |||
4658 | ||||
4659 | /* Drop all floors in "qp", turning each integer division [a/m] into | |||
4660 | * a rational division a/m. If "down" is set, then the integer division | |||
4661 | * is replaced by (a-(m-1))/m instead. | |||
4662 | */ | |||
4663 | static __isl_give isl_qpolynomial *qp_drop_floors( | |||
4664 | __isl_take isl_qpolynomial *qp, int down) | |||
4665 | { | |||
4666 | int i; | |||
4667 | struct isl_upoly *s; | |||
4668 | ||||
4669 | if (!qp) | |||
4670 | return NULL((void*)0); | |||
4671 | if (qp->div->n_row == 0) | |||
4672 | return qp; | |||
4673 | ||||
4674 | qp = isl_qpolynomial_cow(qp); | |||
4675 | if (!qp) | |||
4676 | return NULL((void*)0); | |||
4677 | ||||
4678 | for (i = qp->div->n_row - 1; i >= 0; --i) { | |||
4679 | if (down) { | |||
4680 | isl_int_sub(qp->div->row[i][1],isl_sioimath_sub((qp->div->row[i][1]), *(qp->div-> row[i][1]), *(qp->div->row[i][0])) | |||
4681 | qp->div->row[i][1], qp->div->row[i][0])isl_sioimath_sub((qp->div->row[i][1]), *(qp->div-> row[i][1]), *(qp->div->row[i][0])); | |||
4682 | isl_int_add_ui(qp->div->row[i][1],isl_sioimath_add_ui((qp->div->row[i][1]), *(qp->div-> row[i][1]), 1) | |||
4683 | qp->div->row[i][1], 1)isl_sioimath_add_ui((qp->div->row[i][1]), *(qp->div-> row[i][1]), 1); | |||
4684 | } | |||
4685 | s = isl_upoly_from_affine(qp->dim->ctx, qp->div->row[i] + 1, | |||
4686 | qp->div->row[i][0], qp->div->n_col - 1); | |||
4687 | qp = substitute_div(qp, i, s); | |||
4688 | if (!qp) | |||
4689 | return NULL((void*)0); | |||
4690 | } | |||
4691 | ||||
4692 | return qp; | |||
4693 | } | |||
4694 | ||||
4695 | /* Drop all floors in "pwqp", turning each integer division [a/m] into | |||
4696 | * a rational division a/m. | |||
4697 | */ | |||
4698 | static __isl_give isl_pw_qpolynomial *pwqp_drop_floors( | |||
4699 | __isl_take isl_pw_qpolynomial *pwqp) | |||
4700 | { | |||
4701 | int i; | |||
4702 | ||||
4703 | if (!pwqp) | |||
4704 | return NULL((void*)0); | |||
4705 | ||||
4706 | if (isl_pw_qpolynomial_is_zero(pwqp)) | |||
4707 | return pwqp; | |||
4708 | ||||
4709 | pwqp = isl_pw_qpolynomial_cow(pwqp); | |||
4710 | if (!pwqp) | |||
4711 | return NULL((void*)0); | |||
4712 | ||||
4713 | for (i = 0; i < pwqp->n; ++i) { | |||
4714 | pwqp->p[i].qp = qp_drop_floors(pwqp->p[i].qp, 0); | |||
4715 | if (!pwqp->p[i].qp) | |||
4716 | goto error; | |||
4717 | } | |||
4718 | ||||
4719 | return pwqp; | |||
4720 | error: | |||
4721 | isl_pw_qpolynomial_free(pwqp); | |||
4722 | return NULL((void*)0); | |||
4723 | } | |||
4724 | ||||
4725 | /* Adjust all the integer divisions in "qp" such that they are at least | |||
4726 | * one over the given orthant (identified by "signs"). This ensures | |||
4727 | * that they will still be non-negative even after subtracting (m-1)/m. | |||
4728 | * | |||
4729 | * In particular, f is replaced by f' + v, changing f = [a/m] | |||
4730 | * to f' = [(a - m v)/m]. | |||
4731 | * If the constant term k in a is smaller than m, | |||
4732 | * the constant term of v is set to floor(k/m) - 1. | |||
4733 | * For any other term, if the coefficient c and the variable x have | |||
4734 | * the same sign, then no changes are needed. | |||
4735 | * Otherwise, if the variable is positive (and c is negative), | |||
4736 | * then the coefficient of x in v is set to floor(c/m). | |||
4737 | * If the variable is negative (and c is positive), | |||
4738 | * then the coefficient of x in v is set to ceil(c/m). | |||
4739 | */ | |||
4740 | static __isl_give isl_qpolynomial *make_divs_pos(__isl_take isl_qpolynomial *qp, | |||
4741 | int *signs) | |||
4742 | { | |||
4743 | int i, j; | |||
4744 | int total; | |||
4745 | isl_vec *v = NULL((void*)0); | |||
4746 | struct isl_upoly *s; | |||
4747 | ||||
4748 | qp = isl_qpolynomial_cow(qp); | |||
4749 | if (!qp) | |||
4750 | return NULL((void*)0); | |||
4751 | qp->div = isl_mat_cow(qp->div); | |||
4752 | if (!qp->div) | |||
4753 | goto error; | |||
4754 | ||||
4755 | total = isl_space_dim(qp->dim, isl_dim_all); | |||
4756 | v = isl_vec_alloc(qp->div->ctx, qp->div->n_col - 1); | |||
4757 | ||||
4758 | for (i = 0; i < qp->div->n_row; ++i) { | |||
4759 | isl_int *row = qp->div->row[i]; | |||
4760 | v = isl_vec_clr(v); | |||
4761 | if (!v) | |||
4762 | goto error; | |||
4763 | if (isl_int_lt(row[1], row[0])(isl_sioimath_cmp(*(row[1]), *(row[0])) < 0)) { | |||
4764 | isl_int_fdiv_q(v->el[0], row[1], row[0])isl_sioimath_fdiv_q((v->el[0]), *(row[1]), *(row[0])); | |||
4765 | isl_int_sub_ui(v->el[0], v->el[0], 1)isl_sioimath_sub_ui((v->el[0]), *(v->el[0]), 1); | |||
4766 | isl_int_submul(row[1], row[0], v->el[0])isl_sioimath_submul((row[1]), *(row[0]), *(v->el[0])); | |||
4767 | } | |||
4768 | for (j = 0; j < total; ++j) { | |||
4769 | if (isl_int_sgn(row[2 + j])isl_sioimath_sgn(*(row[2 + j])) * signs[j] >= 0) | |||
4770 | continue; | |||
4771 | if (signs[j] < 0) | |||
4772 | isl_int_cdiv_q(v->el[1 + j], row[2 + j], row[0])isl_sioimath_cdiv_q((v->el[1 + j]), *(row[2 + j]), *(row[0 ])); | |||
4773 | else | |||
4774 | isl_int_fdiv_q(v->el[1 + j], row[2 + j], row[0])isl_sioimath_fdiv_q((v->el[1 + j]), *(row[2 + j]), *(row[0 ])); | |||
4775 | isl_int_submul(row[2 + j], row[0], v->el[1 + j])isl_sioimath_submul((row[2 + j]), *(row[0]), *(v->el[1 + j ])); | |||
4776 | } | |||
4777 | for (j = 0; j < i; ++j) { | |||
4778 | if (isl_int_sgn(row[2 + total + j])isl_sioimath_sgn(*(row[2 + total + j])) >= 0) | |||
4779 | continue; | |||
4780 | isl_int_fdiv_q(v->el[1 + total + j],isl_sioimath_fdiv_q((v->el[1 + total + j]), *(row[2 + total + j]), *(row[0])) | |||
4781 | row[2 + total + j], row[0])isl_sioimath_fdiv_q((v->el[1 + total + j]), *(row[2 + total + j]), *(row[0])); | |||
4782 | isl_int_submul(row[2 + total + j],isl_sioimath_submul((row[2 + total + j]), *(row[0]), *(v-> el[1 + total + j])) | |||
4783 | row[0], v->el[1 + total + j])isl_sioimath_submul((row[2 + total + j]), *(row[0]), *(v-> el[1 + total + j])); | |||
4784 | } | |||
4785 | for (j = i + 1; j < qp->div->n_row; ++j) { | |||
4786 | if (isl_int_is_zero(qp->div->row[j][2 + total + i])(isl_sioimath_sgn(*(qp->div->row[j][2 + total + i])) == 0)) | |||
4787 | continue; | |||
4788 | isl_seq_combine(qp->div->row[j] + 1, | |||
4789 | qp->div->ctx->one, qp->div->row[j] + 1, | |||
4790 | qp->div->row[j][2 + total + i], v->el, v->size); | |||
4791 | } | |||
4792 | isl_int_set_si(v->el[1 + total + i], 1)isl_sioimath_set_si((v->el[1 + total + i]), 1); | |||
4793 | s = isl_upoly_from_affine(qp->dim->ctx, v->el, | |||
4794 | qp->div->ctx->one, v->size); | |||
4795 | qp->upoly = isl_upoly_subs(qp->upoly, total + i, 1, &s); | |||
4796 | isl_upoly_free(s); | |||
4797 | if (!qp->upoly) | |||
4798 | goto error; | |||
4799 | } | |||
4800 | ||||
4801 | isl_vec_free(v); | |||
4802 | return qp; | |||
4803 | error: | |||
4804 | isl_vec_free(v); | |||
4805 | isl_qpolynomial_free(qp); | |||
4806 | return NULL((void*)0); | |||
4807 | } | |||
4808 | ||||
4809 | struct isl_to_poly_data { | |||
4810 | int sign; | |||
4811 | isl_pw_qpolynomial *res; | |||
4812 | isl_qpolynomial *qp; | |||
4813 | }; | |||
4814 | ||||
4815 | /* Appoximate data->qp by a polynomial on the orthant identified by "signs". | |||
4816 | * We first make all integer divisions positive and then split the | |||
4817 | * quasipolynomials into terms with sign data->sign (the direction | |||
4818 | * of the requested approximation) and terms with the opposite sign. | |||
4819 | * In the first set of terms, each integer division [a/m] is | |||
4820 | * overapproximated by a/m, while in the second it is underapproximated | |||
4821 | * by (a-(m-1))/m. | |||
4822 | */ | |||
4823 | static isl_stat to_polynomial_on_orthant(__isl_take isl_setisl_map *orthant, | |||
4824 | int *signs, void *user) | |||
4825 | { | |||
4826 | struct isl_to_poly_data *data = user; | |||
4827 | isl_pw_qpolynomial *t; | |||
4828 | isl_qpolynomial *qp, *up, *down; | |||
4829 | ||||
4830 | qp = isl_qpolynomial_copy(data->qp); | |||
4831 | qp = make_divs_pos(qp, signs); | |||
4832 | ||||
4833 | up = isl_qpolynomial_terms_of_sign(qp, signs, data->sign); | |||
4834 | up = qp_drop_floors(up, 0); | |||
4835 | down = isl_qpolynomial_terms_of_sign(qp, signs, -data->sign); | |||
4836 | down = qp_drop_floors(down, 1); | |||
4837 | ||||
4838 | isl_qpolynomial_free(qp); | |||
4839 | qp = isl_qpolynomial_add(up, down); | |||
4840 | ||||
4841 | t = isl_pw_qpolynomial_alloc(orthant, qp); | |||
4842 | data->res = isl_pw_qpolynomial_add_disjoint(data->res, t); | |||
4843 | ||||
4844 | return isl_stat_ok; | |||
4845 | } | |||
4846 | ||||
4847 | /* Approximate each quasipolynomial by a polynomial. If "sign" is positive, | |||
4848 | * the polynomial will be an overapproximation. If "sign" is negative, | |||
4849 | * it will be an underapproximation. If "sign" is zero, the approximation | |||
4850 | * will lie somewhere in between. | |||
4851 | * | |||
4852 | * In particular, is sign == 0, we simply drop the floors, turning | |||
4853 | * the integer divisions into rational divisions. | |||
4854 | * Otherwise, we split the domains into orthants, make all integer divisions | |||
4855 | * positive and then approximate each [a/m] by either a/m or (a-(m-1))/m, | |||
4856 | * depending on the requested sign and the sign of the term in which | |||
4857 | * the integer division appears. | |||
4858 | */ | |||
4859 | __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_to_polynomial( | |||
4860 | __isl_take isl_pw_qpolynomial *pwqp, int sign) | |||
4861 | { | |||
4862 | int i; | |||
4863 | struct isl_to_poly_data data; | |||
4864 | ||||
4865 | if (sign == 0) | |||
4866 | return pwqp_drop_floors(pwqp); | |||
4867 | ||||
4868 | if (!pwqp) | |||
4869 | return NULL((void*)0); | |||
4870 | ||||
4871 | data.sign = sign; | |||
4872 | data.res = isl_pw_qpolynomial_zero(isl_pw_qpolynomial_get_space(pwqp)); | |||
4873 | ||||
4874 | for (i = 0; i < pwqp->n; ++i) { | |||
4875 | if (pwqp->p[i].qp->div->n_row == 0) { | |||
4876 | isl_pw_qpolynomial *t; | |||
4877 | t = isl_pw_qpolynomial_alloc( | |||
4878 | isl_set_copy(pwqp->p[i].set), | |||
4879 | isl_qpolynomial_copy(pwqp->p[i].qp)); | |||
4880 | data.res = isl_pw_qpolynomial_add_disjoint(data.res, t); | |||
4881 | continue; | |||
4882 | } | |||
4883 | data.qp = pwqp->p[i].qp; | |||
4884 | if (isl_set_foreach_orthant(pwqp->p[i].set, | |||
4885 | &to_polynomial_on_orthant, &data) < 0) | |||
4886 | goto error; | |||
4887 | } | |||
4888 | ||||
4889 | isl_pw_qpolynomial_free(pwqp); | |||
4890 | ||||
4891 | return data.res; | |||
4892 | error: | |||
4893 | isl_pw_qpolynomial_free(pwqp); | |||
4894 | isl_pw_qpolynomial_free(data.res); | |||
4895 | return NULL((void*)0); | |||
4896 | } | |||
4897 | ||||
4898 | static __isl_give isl_pw_qpolynomial *poly_entry( | |||
4899 | __isl_take isl_pw_qpolynomial *pwqp, void *user) | |||
4900 | { | |||
4901 | int *sign = user; | |||
4902 | ||||
4903 | return isl_pw_qpolynomial_to_polynomial(pwqp, *sign); | |||
4904 | } | |||
4905 | ||||
4906 | __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_to_polynomial( | |||
4907 | __isl_take isl_union_pw_qpolynomial *upwqp, int sign) | |||
4908 | { | |||
4909 | return isl_union_pw_qpolynomial_transform_inplace(upwqp, | |||
4910 | &poly_entry, &sign); | |||
4911 | } | |||
4912 | ||||
4913 | __isl_give isl_basic_map *isl_basic_map_from_qpolynomial( | |||
4914 | __isl_take isl_qpolynomial *qp) | |||
4915 | { | |||
4916 | int i, k; | |||
4917 | isl_space *dim; | |||
4918 | isl_vec *aff = NULL((void*)0); | |||
4919 | isl_basic_map *bmap = NULL((void*)0); | |||
4920 | unsigned pos; | |||
4921 | unsigned n_div; | |||
4922 | ||||
4923 | if (!qp) | |||
4924 | return NULL((void*)0); | |||
4925 | if (!isl_upoly_is_affine(qp->upoly)) | |||
4926 | isl_die(qp->dim->ctx, isl_error_invalid,do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "input quasi-polynomial not affine" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 4927); goto error; } while (0) | |||
4927 | "input quasi-polynomial not affine", goto error)do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "input quasi-polynomial not affine" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c" , 4927); goto error; } while (0); | |||
4928 | aff = isl_qpolynomial_extract_affine(qp); | |||
4929 | if (!aff) | |||
4930 | goto error; | |||
4931 | dim = isl_qpolynomial_get_space(qp); | |||
4932 | pos = 1 + isl_space_offset(dim, isl_dim_out); | |||
4933 | n_div = qp->div->n_row; | |||
4934 | bmap = isl_basic_map_alloc_space(dim, n_div, 1, 2 * n_div); | |||
4935 | ||||
4936 | for (i = 0; i < n_div; ++i) { | |||
4937 | k = isl_basic_map_alloc_div(bmap); | |||
4938 | if (k < 0) | |||
4939 | goto error; | |||
4940 | isl_seq_cpy(bmap->div[k], qp->div->row[i], qp->div->n_col); | |||
4941 | isl_int_set_si(bmap->div[k][qp->div->n_col], 0)isl_sioimath_set_si((bmap->div[k][qp->div->n_col]), 0 ); | |||
4942 | if (isl_basic_map_add_div_constraints(bmap, k) < 0) | |||
4943 | goto error; | |||
4944 | } | |||
4945 | k = isl_basic_map_alloc_equality(bmap); | |||
4946 | if (k < 0) | |||
4947 | goto error; | |||
4948 | isl_int_neg(bmap->eq[k][pos], aff->el[0])isl_sioimath_neg((bmap->eq[k][pos]), *(aff->el[0])); | |||
4949 | isl_seq_cpy(bmap->eq[k], aff->el + 1, pos); | |||
4950 | isl_seq_cpy(bmap->eq[k] + pos + 1, aff->el + 1 + pos, n_div); | |||
4951 | ||||
4952 | isl_vec_free(aff); | |||
4953 | isl_qpolynomial_free(qp); | |||
4954 | bmap = isl_basic_map_finalize(bmap); | |||
4955 | return bmap; | |||
4956 | error: | |||
4957 | isl_vec_free(aff); | |||
4958 | isl_qpolynomial_free(qp); | |||
4959 | isl_basic_map_free(bmap); | |||
4960 | return NULL((void*)0); | |||
4961 | } |