Bug Summary

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