Bug Summary

File:tools/polly/lib/External/isl/isl_polynomial.c
Warning:line 3042, 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)
43
Taking false branch
1207 return NULL((void*)0);
1208
1209 if (--qp->ref > 0)
44
Assuming the condition is false
45
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);
46
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
Assuming 'qp1' is non-null
40
Taking false branch
1694 goto error;
1695
1696 if (qp1->div->n_row < qp2->div->n_row)
41
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);
1715 isl_qpolynomial_free(qp2);
42
Calling 'isl_qpolynomial_free'
47
Returning; memory was released via 1st parameter
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
51
Assuming the condition is true
52
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
49
Assuming the condition is false
50
Loop condition is false. Execution continues on line 3029
53
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
54
Assuming the condition is false
55
Taking false branch
3036 isl_set_free(common);
3037 continue;
3038 }
3039
3040 prod = isl_qpolynomial_mul(
38
Calling 'isl_qpolynomial_mul'
48
Returning; memory was released via 2nd parameter
3041 isl_qpolynomial_copy(pwqp1->p[i].qp),
3042 isl_qpolynomial_copy(pwqp2->p[j].qp));
34
Calling 'isl_qpolynomial_copy'
37
Returning from 'isl_qpolynomial_copy'
56
Use of memory after it is freed
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}