Bug Summary

File:tools/polly/lib/External/isl/isl_polynomial.c
Warning:line 3043, column 5
Use of memory after it is freed

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name isl_polynomial.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-9/lib/clang/9.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/pet/include -I /build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/ppcg/include -I /build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/ppcg/imath -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/tools/polly/lib/External/ppcg -I /build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/imath -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/tools/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/tools/polly/include -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-9~svn362543/tools/polly/include -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/include -I /build/llvm-toolchain-snapshot-9~svn362543/include -U NDEBUG -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-9/lib/clang/9.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=gnu99 -fconst-strings -fdebug-compilation-dir /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/tools/polly/lib/External -fdebug-prefix-map=/build/llvm-toolchain-snapshot-9~svn362543=. -ferror-limit 19 -fmessage-length 0 -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2019-06-05-060531-1271-1 -x c /build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_polynomial.c -faddrsig
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
36static 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
46int 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 */
79static 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
125isl_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
164int 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
180int 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
196int 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
212int 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
228int 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
244int 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
260int 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;
415error:
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
433isl_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 */
457unsigned 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 */
473unsigned 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 */
488unsigned 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
506isl_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
511isl_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
516isl_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
521isl_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
526isl_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
531int isl_qpolynomial_sgn(__isl_keep isl_qpolynomial *qp)
532{
533 return qp ? isl_upoly_sgn(qp->upoly) : 0;
534}
535
536static 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
542static 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;
599error:
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
644static 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;
682error:
683 isl_upoly_free(up1);
684 isl_upoly_free(up2);
685 return NULL((void*)0);
686}
687
688static __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
700static __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;
715error:
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;
803error:
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;
846error:
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;
894error:
895 isl_upoly_free(up);
896 return NULL((void*)0);
897}
898
899/* Multiply the constant polynomial "up" by "v".
900 */
901static __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 */
924static __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;
948error:
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;
973error:
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;
1025error:
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);
1099error:
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;
1158error:
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)
38
Assuming 'qp' is non-null
39
Taking false branch
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;
1191error:
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)
50
Taking false branch
1211 return NULL((void*)0);
1212
1213 if (--qp->ref > 0)
51
Assuming the condition is false
52
Taking false branch
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);
53
Memory is released
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;
1243error:
1244 isl_upoly_free(&rec->up);
1245 return NULL((void*)0);
1246}
1247
1248/* r array maps original positions to new positions.
1249 */
1250static __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;
1279error:
1280 isl_upoly_free(up);
1281 return NULL((void*)0);
1282}
1283
1284static 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
1310static 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
1323struct isl_div_sort_info {
1324 isl_mat *div;
1325 int row;
1326};
1327
1328static 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 */
1339static __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;
1414error:
1415 free(at);
1416 free(pos);
1417 free(array);
1418 free(reordering);
1419 isl_qpolynomial_free(qp);
1420 return NULL((void*)0);
1421}
1422
1423static __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;
1455error:
1456 isl_upoly_free(up);
1457 return NULL((void*)0);
1458}
1459
1460static __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);
1506error:
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;
1542error:
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;
1579error:
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;
1615error:
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;
1662error:
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));
1684error:
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)
42
Assuming 'qp1' is non-null
43
Taking false branch
1698 goto error;
1699
1700 if (qp1->div->n_row < qp2->div->n_row)
44
Assuming the condition is false
45
Taking false branch
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)
;
46
Assuming the condition is false
47
Taking false branch
48
Control jumps to line 1718
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;
1717error:
1718 isl_qpolynomial_free(qp1);
1719 isl_qpolynomial_free(qp2);
49
Calling 'isl_qpolynomial_free'
54
Returning; memory was released via 1st parameter
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;
1736error:
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
1822int 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 */
1847static __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
1881int 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
1910int 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
1921static 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
1941int 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;
1994error:
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 */
2004int 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 */
2031isl_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
2053static 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
2075void 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);
2109error:
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;
2153error:
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 */
2185static 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 */
2208static __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;
2245error:
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 */
2254static __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 */
2296static 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 */
2329static 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 */
2354static 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 */
2383static __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;
2435error:
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;
2484error:
2485 isl_space_free(domain);
2486 isl_val_free(val);
2487 return NULL((void*)0);
2488}
2489
2490static 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
2512static 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
2531isl_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;
2565error:
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 */
2573static __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;
2647error:
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;
2683error:
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;
2705error:
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;
2750error:
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
2780static __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;
2840error:
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);
2856error:
2857 isl_basic_set_free(eq);
2858 isl_qpolynomial_free(qp);
2859 return NULL((void*)0);
2860}
2861
2862static __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;
2882error:
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);
2912error:
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
2973int 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)
21
Assuming 'pwqp1' is non-null
22
Assuming 'pwqp2' is non-null
23
Taking false branch
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)
24
Assuming the condition is true
25
Taking true branch
26
Execution continues on line 3007
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)) {
27
Taking false branch
3008 isl_pw_qpolynomial_free(pwqp2);
3009 return pwqp1;
3010 }
3011
3012 if (isl_pw_qpolynomial_is_zero(pwqp2)) {
28
Taking false branch
3013 isl_pw_qpolynomial_free(pwqp1);
3014 return pwqp2;
3015 }
3016
3017 if (isl_pw_qpolynomial_is_one(pwqp1)) {
29
Taking false branch
3018 isl_pw_qpolynomial_free(pwqp1);
3019 return pwqp2;
3020 }
3021
3022 if (isl_pw_qpolynomial_is_one(pwqp2)) {
30
Taking false branch
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) {
31
Assuming the condition is true
32
Loop condition is true. Entering loop body
58
Assuming the condition is true
59
Loop condition is true. Entering loop body
3031 for (j = 0; j < pwqp2->n; ++j) {
33
Assuming the condition is true
34
Loop condition is true. Entering loop body
56
Assuming the condition is false
57
Loop condition is false. Execution continues on line 3030
60
Loop condition is true. Entering loop body
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)) {
35
Assuming the condition is false
36
Taking false branch
61
Assuming the condition is false
62
Taking false branch
3037 isl_set_free(common);
3038 continue;
3039 }
3040
3041 prod = isl_qpolynomial_mul(
41
Calling 'isl_qpolynomial_mul'
55
Returning; memory was released via 2nd parameter
3042 isl_qpolynomial_copy(pwqp1->p[i].qp),
3043 isl_qpolynomial_copy(pwqp2->p[j].qp));
37
Calling 'isl_qpolynomial_copy'
40
Returning from 'isl_qpolynomial_copy'
63
Use of memory after it is freed
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;
3053error:
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;
3097error:
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 */
3106static __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;
3141error:
3142 isl_qpolynomial_free(qp);
3143 isl_point_free(pnt);
3144 return NULL((void*)0);
3145}
3146
3147int 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;
3211error:
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
3237static 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;
3330error:
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;
3378error:
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;
3474error:
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 */
3484isl_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 */
3512int 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 */
3546int 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;
3602error:
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;
3641error:
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;
3691error:
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;
3722error:
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;
3750error:
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
3800void 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
3815unsigned 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
3831isl_ctx *isl_term_get_ctx(__isl_keep isl_term *term)
3832{
3833 return term ? term->dim->ctx : NULL((void*)0);
3834}
3835
3836void 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
3854int 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;
3942error:
3943 isl_term_free(term);
3944 return NULL((void*)0);
3945}
3946
3947isl_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;
3995error:
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;
4046error:
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 */
4055static __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;
4099error:
4100 free(active);
4101 isl_set_free(set);
4102 return NULL((void*)0);
4103}
4104
4105struct isl_opt_data {
4106 isl_qpolynomial *qp;
4107 int first;
4108 isl_val *opt;
4109 int max;
4110};
4111
4112static 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;
4157error:
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;
4215error:
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;
4257error:
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;
4285error:
4286 isl_space_free(model);
4287 isl_qpolynomial_free(qp);
4288 return NULL((void*)0);
4289}
4290
4291struct 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 */
4306static __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);
4335error:
4336 isl_basic_set_free(bset);
4337 isl_space_free(dim);
4338 return NULL((void*)0);
4339}
4340
4341static 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 */
4348static 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);
4377error:
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 */
4387static 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;
4401error:
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 */
4413static 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;
4478error2:
4479 isl_int_clear(max)isl_sioimath_clear((max));
4480 isl_int_clear(min)isl_sioimath_clear((min));
4481error:
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;
4505error:
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 */
4520static __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 */
4548static __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)
14
Assuming 'f' is non-null
15
Taking false branch
4563 goto error;
4564 if (f->n_group == 0) {
16
Assuming the condition is false
17
Taking false branch
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) {
18
Assuming the condition is true
19
Loop condition is true. Entering loop body
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);
20
Calling 'isl_pw_qpolynomial_mul'
4595
4596 n += f->len[i];
4597 }
4598
4599 isl_basic_set_free(bset);
4600 isl_factorizer_free(f);
4601
4602 return pwqp;
4603error:
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)
1
Assuming 'bset' is non-null
2
Taking false branch
4625 return NULL((void*)0);
4626
4627 if (isl_basic_set_plain_is_empty(bset))
3
Assuming the condition is false
4
Taking false branch
4628 return constant_on_domain(bset, 0);
4629
4630 if (isl_basic_set_dim(bset, isl_dim_set) == 0)
5
Assuming the condition is false
6
Taking false branch
4631 return constant_on_domain(bset, 1);
4632
4633 bounded = isl_basic_set_is_bounded(bset);
4634 if (bounded < 0)
7
Assuming 'bounded' is >= 0
8
Taking false branch
4635 goto error;
4636 if (!bounded)
9
Assuming 'bounded' is not equal to 0
10
Taking false branch
4637 return constant_on_domain(bset, -1);
4638
4639 if (bset->n_eq == 0)
11
Assuming the condition is true
12
Taking true branch
4640 return compressed_multiplicative_call(bset, fn);
13
Calling 'compressed_multiplicative_call'
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;
4654error:
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 */
4663static __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 */
4698static __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;
4720error:
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 */
4740static __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;
4803error:
4804 isl_vec_free(v);
4805 isl_qpolynomial_free(qp);
4806 return NULL((void*)0);
4807}
4808
4809struct 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 */
4823static 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;
4892error:
4893 isl_pw_qpolynomial_free(pwqp);
4894 isl_pw_qpolynomial_free(data.res);
4895 return NULL((void*)0);
4896}
4897
4898static __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;
4956error:
4957 isl_vec_free(aff);
4958 isl_qpolynomial_free(qp);
4959 isl_basic_map_free(bmap);
4960 return NULL((void*)0);
4961}