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

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#include <isl/deprecated/polynomial_int.h>
32
33static unsigned pos(__isl_keep isl_space *dim, enum isl_dim_type type)
34{
35 switch (type) {
36 case isl_dim_param: return 0;
37 case isl_dim_in: return dim->nparam;
38 case isl_dim_out: return dim->nparam + dim->n_in;
39 default: return 0;
40 }
41}
42
43int isl_upoly_is_cst(__isl_keep struct isl_upoly *up)
44{
45 if (!up)
46 return -1;
47
48 return up->var < 0;
49}
50
51__isl_keep struct isl_upoly_cst *isl_upoly_as_cst(__isl_keep struct isl_upoly *up)
52{
53 if (!up)
54 return NULL((void*)0);
55
56 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"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 56); return ((void*)0); } while (0); } while (0)
;
57
58 return (struct isl_upoly_cst *)up;
59}
60
61__isl_keep struct isl_upoly_rec *isl_upoly_as_rec(__isl_keep struct isl_upoly *up)
62{
63 if (!up)
64 return NULL((void*)0);
65
66 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"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 66); return ((void*)0); } while (0); } while (0)
;
67
68 return (struct isl_upoly_rec *)up;
69}
70
71/* Compare two polynomials.
72 *
73 * Return -1 if "up1" is "smaller" than "up2", 1 if "up1" is "greater"
74 * than "up2" and 0 if they are equal.
75 */
76static int isl_upoly_plain_cmp(__isl_keep struct isl_upoly *up1,
77 __isl_keep struct isl_upoly *up2)
78{
79 int i;
80 struct isl_upoly_rec *rec1, *rec2;
81
82 if (up1 == up2)
83 return 0;
84 if (!up1)
85 return -1;
86 if (!up2)
87 return 1;
88 if (up1->var != up2->var)
89 return up1->var - up2->var;
90
91 if (isl_upoly_is_cst(up1)) {
92 struct isl_upoly_cst *cst1, *cst2;
93 int cmp;
94
95 cst1 = isl_upoly_as_cst(up1);
96 cst2 = isl_upoly_as_cst(up2);
97 if (!cst1 || !cst2)
98 return 0;
99 cmp = isl_int_cmp(cst1->n, cst2->n)isl_sioimath_cmp(*(cst1->n), *(cst2->n));
100 if (cmp != 0)
101 return cmp;
102 return isl_int_cmp(cst1->d, cst2->d)isl_sioimath_cmp(*(cst1->d), *(cst2->d));
103 }
104
105 rec1 = isl_upoly_as_rec(up1);
106 rec2 = isl_upoly_as_rec(up2);
107 if (!rec1 || !rec2)
108 return 0;
109
110 if (rec1->n != rec2->n)
111 return rec1->n - rec2->n;
112
113 for (i = 0; i < rec1->n; ++i) {
114 int cmp = isl_upoly_plain_cmp(rec1->p[i], rec2->p[i]);
115 if (cmp != 0)
116 return cmp;
117 }
118
119 return 0;
120}
121
122isl_bool isl_upoly_is_equal(__isl_keep struct isl_upoly *up1,
123 __isl_keep struct isl_upoly *up2)
124{
125 int i;
126 struct isl_upoly_rec *rec1, *rec2;
127
128 if (!up1 || !up2)
129 return isl_bool_error;
130 if (up1 == up2)
131 return isl_bool_true;
132 if (up1->var != up2->var)
133 return isl_bool_false;
134 if (isl_upoly_is_cst(up1)) {
135 struct isl_upoly_cst *cst1, *cst2;
136 cst1 = isl_upoly_as_cst(up1);
137 cst2 = isl_upoly_as_cst(up2);
138 if (!cst1 || !cst2)
139 return isl_bool_error;
140 return isl_int_eq(cst1->n, cst2->n)(isl_sioimath_cmp(*(cst1->n), *(cst2->n)) == 0) &&
141 isl_int_eq(cst1->d, cst2->d)(isl_sioimath_cmp(*(cst1->d), *(cst2->d)) == 0);
142 }
143
144 rec1 = isl_upoly_as_rec(up1);
145 rec2 = isl_upoly_as_rec(up2);
146 if (!rec1 || !rec2)
147 return isl_bool_error;
148
149 if (rec1->n != rec2->n)
150 return isl_bool_false;
151
152 for (i = 0; i < rec1->n; ++i) {
153 isl_bool eq = isl_upoly_is_equal(rec1->p[i], rec2->p[i]);
154 if (eq < 0 || !eq)
155 return eq;
156 }
157
158 return isl_bool_true;
159}
160
161int isl_upoly_is_zero(__isl_keep struct isl_upoly *up)
162{
163 struct isl_upoly_cst *cst;
164
165 if (!up)
166 return -1;
167 if (!isl_upoly_is_cst(up))
168 return 0;
169
170 cst = isl_upoly_as_cst(up);
171 if (!cst)
172 return -1;
173
174 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);
175}
176
177int isl_upoly_sgn(__isl_keep struct isl_upoly *up)
178{
179 struct isl_upoly_cst *cst;
180
181 if (!up)
182 return 0;
183 if (!isl_upoly_is_cst(up))
184 return 0;
185
186 cst = isl_upoly_as_cst(up);
187 if (!cst)
188 return 0;
189
190 return isl_int_sgn(cst->n)isl_sioimath_sgn(*(cst->n));
191}
192
193int isl_upoly_is_nan(__isl_keep struct isl_upoly *up)
194{
195 struct isl_upoly_cst *cst;
196
197 if (!up)
198 return -1;
199 if (!isl_upoly_is_cst(up))
200 return 0;
201
202 cst = isl_upoly_as_cst(up);
203 if (!cst)
204 return -1;
205
206 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);
207}
208
209int isl_upoly_is_infty(__isl_keep struct isl_upoly *up)
210{
211 struct isl_upoly_cst *cst;
212
213 if (!up)
214 return -1;
215 if (!isl_upoly_is_cst(up))
216 return 0;
217
218 cst = isl_upoly_as_cst(up);
219 if (!cst)
220 return -1;
221
222 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);
223}
224
225int isl_upoly_is_neginfty(__isl_keep struct isl_upoly *up)
226{
227 struct isl_upoly_cst *cst;
228
229 if (!up)
230 return -1;
231 if (!isl_upoly_is_cst(up))
232 return 0;
233
234 cst = isl_upoly_as_cst(up);
235 if (!cst)
236 return -1;
237
238 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);
239}
240
241int isl_upoly_is_one(__isl_keep struct isl_upoly *up)
242{
243 struct isl_upoly_cst *cst;
244
245 if (!up)
246 return -1;
247 if (!isl_upoly_is_cst(up))
248 return 0;
249
250 cst = isl_upoly_as_cst(up);
251 if (!cst)
252 return -1;
253
254 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);
255}
256
257int isl_upoly_is_negone(__isl_keep struct isl_upoly *up)
258{
259 struct isl_upoly_cst *cst;
260
261 if (!up)
262 return -1;
263 if (!isl_upoly_is_cst(up))
264 return 0;
265
266 cst = isl_upoly_as_cst(up);
267 if (!cst)
268 return -1;
269
270 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);
271}
272
273__isl_give struct isl_upoly_cst *isl_upoly_cst_alloc(struct isl_ctx *ctx)
274{
275 struct isl_upoly_cst *cst;
276
277 cst = isl_alloc_type(ctx, struct isl_upoly_cst)((struct isl_upoly_cst *)isl_malloc_or_die(ctx, sizeof(struct
isl_upoly_cst)))
;
278 if (!cst)
279 return NULL((void*)0);
280
281 cst->up.ref = 1;
282 cst->up.ctx = ctx;
283 isl_ctx_ref(ctx);
284 cst->up.var = -1;
285
286 isl_int_init(cst->n)isl_sioimath_init((cst->n));
287 isl_int_init(cst->d)isl_sioimath_init((cst->d));
288
289 return cst;
290}
291
292__isl_give struct isl_upoly *isl_upoly_zero(struct isl_ctx *ctx)
293{
294 struct isl_upoly_cst *cst;
295
296 cst = isl_upoly_cst_alloc(ctx);
297 if (!cst)
298 return NULL((void*)0);
299
300 isl_int_set_si(cst->n, 0)isl_sioimath_set_si((cst->n), 0);
301 isl_int_set_si(cst->d, 1)isl_sioimath_set_si((cst->d), 1);
302
303 return &cst->up;
304}
305
306__isl_give struct isl_upoly *isl_upoly_one(struct isl_ctx *ctx)
307{
308 struct isl_upoly_cst *cst;
309
310 cst = isl_upoly_cst_alloc(ctx);
311 if (!cst)
312 return NULL((void*)0);
313
314 isl_int_set_si(cst->n, 1)isl_sioimath_set_si((cst->n), 1);
315 isl_int_set_si(cst->d, 1)isl_sioimath_set_si((cst->d), 1);
316
317 return &cst->up;
318}
319
320__isl_give struct isl_upoly *isl_upoly_infty(struct isl_ctx *ctx)
321{
322 struct isl_upoly_cst *cst;
323
324 cst = isl_upoly_cst_alloc(ctx);
325 if (!cst)
326 return NULL((void*)0);
327
328 isl_int_set_si(cst->n, 1)isl_sioimath_set_si((cst->n), 1);
329 isl_int_set_si(cst->d, 0)isl_sioimath_set_si((cst->d), 0);
330
331 return &cst->up;
332}
333
334__isl_give struct isl_upoly *isl_upoly_neginfty(struct isl_ctx *ctx)
335{
336 struct isl_upoly_cst *cst;
337
338 cst = isl_upoly_cst_alloc(ctx);
339 if (!cst)
340 return NULL((void*)0);
341
342 isl_int_set_si(cst->n, -1)isl_sioimath_set_si((cst->n), -1);
343 isl_int_set_si(cst->d, 0)isl_sioimath_set_si((cst->d), 0);
344
345 return &cst->up;
346}
347
348__isl_give struct isl_upoly *isl_upoly_nan(struct isl_ctx *ctx)
349{
350 struct isl_upoly_cst *cst;
351
352 cst = isl_upoly_cst_alloc(ctx);
353 if (!cst)
354 return NULL((void*)0);
355
356 isl_int_set_si(cst->n, 0)isl_sioimath_set_si((cst->n), 0);
357 isl_int_set_si(cst->d, 0)isl_sioimath_set_si((cst->d), 0);
358
359 return &cst->up;
360}
361
362__isl_give struct isl_upoly *isl_upoly_rat_cst(struct isl_ctx *ctx,
363 isl_int n, isl_int d)
364{
365 struct isl_upoly_cst *cst;
366
367 cst = isl_upoly_cst_alloc(ctx);
368 if (!cst)
369 return NULL((void*)0);
370
371 isl_int_set(cst->n, n)isl_sioimath_set((cst->n), *(n));
372 isl_int_set(cst->d, d)isl_sioimath_set((cst->d), *(d));
373
374 return &cst->up;
375}
376
377__isl_give struct isl_upoly_rec *isl_upoly_alloc_rec(struct isl_ctx *ctx,
378 int var, int size)
379{
380 struct isl_upoly_rec *rec;
381
382 isl_assert(ctx, var >= 0, return NULL)do { if (var >= 0) break; do { isl_handle_error(ctx, isl_error_unknown
, "Assertion \"" "var >= 0" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 382); return ((void*)0); } while (0); } while (0)
;
383 isl_assert(ctx, size >= 0, return NULL)do { if (size >= 0) break; do { isl_handle_error(ctx, isl_error_unknown
, "Assertion \"" "size >= 0" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 383); return ((void*)0); } while (0); } while (0)
;
384 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 *)))
385 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 *)))
386 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 *)))
;
387 if (!rec)
388 return NULL((void*)0);
389
390 rec->up.ref = 1;
391 rec->up.ctx = ctx;
392 isl_ctx_ref(ctx);
393 rec->up.var = var;
394
395 rec->n = 0;
396 rec->size = size;
397
398 return rec;
399}
400
401__isl_give isl_qpolynomial *isl_qpolynomial_reset_domain_space(
402 __isl_take isl_qpolynomial *qp, __isl_take isl_space *dim)
403{
404 qp = isl_qpolynomial_cow(qp);
405 if (!qp || !dim)
406 goto error;
407
408 isl_space_free(qp->dim);
409 qp->dim = dim;
410
411 return qp;
412error:
413 isl_qpolynomial_free(qp);
414 isl_space_free(dim);
415 return NULL((void*)0);
416}
417
418/* Reset the space of "qp". This function is called from isl_pw_templ.c
419 * and doesn't know if the space of an element object is represented
420 * directly or through its domain. It therefore passes along both.
421 */
422__isl_give isl_qpolynomial *isl_qpolynomial_reset_space_and_domain(
423 __isl_take isl_qpolynomial *qp, __isl_take isl_space *space,
424 __isl_take isl_space *domain)
425{
426 isl_space_free(space);
427 return isl_qpolynomial_reset_domain_space(qp, domain);
428}
429
430isl_ctx *isl_qpolynomial_get_ctx(__isl_keep isl_qpolynomial *qp)
431{
432 return qp ? qp->dim->ctx : NULL((void*)0);
433}
434
435__isl_give isl_space *isl_qpolynomial_get_domain_space(
436 __isl_keep isl_qpolynomial *qp)
437{
438 return qp ? isl_space_copy(qp->dim) : NULL((void*)0);
439}
440
441__isl_give isl_space *isl_qpolynomial_get_space(__isl_keep isl_qpolynomial *qp)
442{
443 isl_space *space;
444 if (!qp)
445 return NULL((void*)0);
446 space = isl_space_copy(qp->dim);
447 space = isl_space_from_domain(space);
448 space = isl_space_add_dims(space, isl_dim_out, 1);
449 return space;
450}
451
452/* Return the number of variables of the given type in the domain of "qp".
453 */
454unsigned isl_qpolynomial_domain_dim(__isl_keep isl_qpolynomial *qp,
455 enum isl_dim_type type)
456{
457 if (!qp)
458 return 0;
459 if (type == isl_dim_div)
460 return qp->div->n_row;
461 if (type == isl_dim_all)
462 return isl_space_dim(qp->dim, isl_dim_all) +
463 isl_qpolynomial_domain_dim(qp, isl_dim_div);
464 return isl_space_dim(qp->dim, type);
465}
466
467/* Externally, an isl_qpolynomial has a map space, but internally, the
468 * ls field corresponds to the domain of that space.
469 */
470unsigned isl_qpolynomial_dim(__isl_keep isl_qpolynomial *qp,
471 enum isl_dim_type type)
472{
473 if (!qp)
474 return 0;
475 if (type == isl_dim_out)
476 return 1;
477 if (type == isl_dim_in)
478 type = isl_dim_set;
479 return isl_qpolynomial_domain_dim(qp, type);
480}
481
482/* Return the offset of the first coefficient of type "type" in
483 * the domain of "qp".
484 */
485unsigned isl_qpolynomial_domain_offset(__isl_keep isl_qpolynomial *qp,
486 enum isl_dim_type type)
487{
488 if (!qp)
489 return 0;
490 switch (type) {
491 case isl_dim_cst:
492 return 0;
493 case isl_dim_param:
494 case isl_dim_set:
495 return 1 + isl_space_offset(qp->dim, type);
496 case isl_dim_div:
497 return 1 + isl_space_dim(qp->dim, isl_dim_all);
498 default:
499 return 0;
500 }
501}
502
503isl_bool isl_qpolynomial_is_zero(__isl_keep isl_qpolynomial *qp)
504{
505 return qp ? isl_upoly_is_zero(qp->upoly) : isl_bool_error;
506}
507
508isl_bool isl_qpolynomial_is_one(__isl_keep isl_qpolynomial *qp)
509{
510 return qp ? isl_upoly_is_one(qp->upoly) : isl_bool_error;
511}
512
513isl_bool isl_qpolynomial_is_nan(__isl_keep isl_qpolynomial *qp)
514{
515 return qp ? isl_upoly_is_nan(qp->upoly) : isl_bool_error;
516}
517
518isl_bool isl_qpolynomial_is_infty(__isl_keep isl_qpolynomial *qp)
519{
520 return qp ? isl_upoly_is_infty(qp->upoly) : isl_bool_error;
521}
522
523isl_bool isl_qpolynomial_is_neginfty(__isl_keep isl_qpolynomial *qp)
524{
525 return qp ? isl_upoly_is_neginfty(qp->upoly) : isl_bool_error;
526}
527
528int isl_qpolynomial_sgn(__isl_keep isl_qpolynomial *qp)
529{
530 return qp ? isl_upoly_sgn(qp->upoly) : 0;
531}
532
533static void upoly_free_cst(__isl_take struct isl_upoly_cst *cst)
534{
535 isl_int_clear(cst->n)isl_sioimath_clear((cst->n));
536 isl_int_clear(cst->d)isl_sioimath_clear((cst->d));
537}
538
539static void upoly_free_rec(__isl_take struct isl_upoly_rec *rec)
540{
541 int i;
542
543 for (i = 0; i < rec->n; ++i)
544 isl_upoly_free(rec->p[i]);
545}
546
547__isl_give struct isl_upoly *isl_upoly_copy(__isl_keep struct isl_upoly *up)
548{
549 if (!up)
550 return NULL((void*)0);
551
552 up->ref++;
553 return up;
554}
555
556__isl_give struct isl_upoly *isl_upoly_dup_cst(__isl_keep struct isl_upoly *up)
557{
558 struct isl_upoly_cst *cst;
559 struct isl_upoly_cst *dup;
560
561 cst = isl_upoly_as_cst(up);
562 if (!cst)
563 return NULL((void*)0);
564
565 dup = isl_upoly_as_cst(isl_upoly_zero(up->ctx));
566 if (!dup)
567 return NULL((void*)0);
568 isl_int_set(dup->n, cst->n)isl_sioimath_set((dup->n), *(cst->n));
569 isl_int_set(dup->d, cst->d)isl_sioimath_set((dup->d), *(cst->d));
570
571 return &dup->up;
572}
573
574__isl_give struct isl_upoly *isl_upoly_dup_rec(__isl_keep struct isl_upoly *up)
575{
576 int i;
577 struct isl_upoly_rec *rec;
578 struct isl_upoly_rec *dup;
579
580 rec = isl_upoly_as_rec(up);
581 if (!rec)
582 return NULL((void*)0);
583
584 dup = isl_upoly_alloc_rec(up->ctx, up->var, rec->n);
585 if (!dup)
586 return NULL((void*)0);
587
588 for (i = 0; i < rec->n; ++i) {
589 dup->p[i] = isl_upoly_copy(rec->p[i]);
590 if (!dup->p[i])
591 goto error;
592 dup->n++;
593 }
594
595 return &dup->up;
596error:
597 isl_upoly_free(&dup->up);
598 return NULL((void*)0);
599}
600
601__isl_give struct isl_upoly *isl_upoly_dup(__isl_keep struct isl_upoly *up)
602{
603 if (!up)
604 return NULL((void*)0);
605
606 if (isl_upoly_is_cst(up))
607 return isl_upoly_dup_cst(up);
608 else
609 return isl_upoly_dup_rec(up);
610}
611
612__isl_give struct isl_upoly *isl_upoly_cow(__isl_take struct isl_upoly *up)
613{
614 if (!up)
615 return NULL((void*)0);
616
617 if (up->ref == 1)
618 return up;
619 up->ref--;
620 return isl_upoly_dup(up);
621}
622
623void isl_upoly_free(__isl_take struct isl_upoly *up)
624{
625 if (!up)
626 return;
627
628 if (--up->ref > 0)
629 return;
630
631 if (up->var < 0)
632 upoly_free_cst((struct isl_upoly_cst *)up);
633 else
634 upoly_free_rec((struct isl_upoly_rec *)up);
635
636 isl_ctx_deref(up->ctx);
637 free(up);
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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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)
15
Assuming 'qp' is non-null
16
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)
22
Taking false branch
1207 return NULL((void*)0);
1208
1209 if (--qp->ref > 0)
23
Assuming the condition is false
24
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);
25
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"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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)
19
Taking false branch
1694 goto error;
1695
1696 if (qp1->div->n_row < qp2->div->n_row)
20
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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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);
21
Calling 'isl_qpolynomial_free'
26
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"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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)
1
Assuming 'pwqp1' is non-null
2
Assuming 'pwqp2' is non-null
3
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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3004); goto error; } while (0); } while (0)
;
3005
3006 if (isl_pw_qpolynomial_is_zero(pwqp1)) {
4
Taking false branch
3007 isl_pw_qpolynomial_free(pwqp2);
3008 return pwqp1;
3009 }
3010
3011 if (isl_pw_qpolynomial_is_zero(pwqp2)) {
5
Taking false branch
3012 isl_pw_qpolynomial_free(pwqp1);
3013 return pwqp2;
3014 }
3015
3016 if (isl_pw_qpolynomial_is_one(pwqp1)) {
6
Taking false branch
3017 isl_pw_qpolynomial_free(pwqp1);
3018 return pwqp2;
3019 }
3020
3021 if (isl_pw_qpolynomial_is_one(pwqp2)) {
7
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) {
8
Assuming the condition is true
9
Loop condition is true. Entering loop body
30
Assuming the condition is true
31
Loop condition is true. Entering loop body
3030 for (j = 0; j < pwqp2->n; ++j) {
10
Assuming the condition is true
11
Loop condition is true. Entering loop body
28
Assuming the condition is false
29
Loop condition is false. Execution continues on line 3029
32
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)) {
12
Assuming the condition is false
13
Taking false branch
33
Assuming the condition is false
34
Taking false branch
3036 isl_set_free(common);
3037 continue;
3038 }
3039
3040 prod = isl_qpolynomial_mul(
18
Calling 'isl_qpolynomial_mul'
27
Returning; memory was released via 2nd parameter
3041 isl_qpolynomial_copy(pwqp1->p[i].qp),
3042 isl_qpolynomial_copy(pwqp2->p[j].qp));
14
Calling 'isl_qpolynomial_copy'
17
Returning from 'isl_qpolynomial_copy'
35
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"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/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 (n == 0)
3295 return qp;
3296
3297 qp = isl_qpolynomial_cow(qp);
3298 if (!qp)
3299 return NULL((void*)0);
3300
3301 if (dst_type == isl_dim_out || src_type == isl_dim_out)
3302 isl_die(qp->dim->ctx, isl_error_invalid,do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "cannot move output/set dimension"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3304); goto error; } while (0)
3303 "cannot move output/set dimension",do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "cannot move output/set dimension"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3304); goto error; } while (0)
3304 goto error)do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "cannot move output/set dimension"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3304); goto error; } while (0)
;
3305 if (dst_type == isl_dim_in)
3306 dst_type = isl_dim_set;
3307 if (src_type == isl_dim_in)
3308 src_type = isl_dim_set;
3309
3310 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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3311); goto error; } while (0); } while (0)
3311 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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3311); goto error; } while (0); } while (0)
;
3312
3313 g_dst_pos = pos(qp->dim, dst_type) + dst_pos;
3314 g_src_pos = pos(qp->dim, src_type) + src_pos;
3315 if (dst_type > src_type)
3316 g_dst_pos -= n;
3317
3318 qp->div = isl_mat_move_cols(qp->div, 2 + g_dst_pos, 2 + g_src_pos, n);
3319 if (!qp->div)
3320 goto error;
3321 qp = sort_divs(qp);
3322 if (!qp)
3323 goto error;
3324
3325 reordering = reordering_move(qp->dim->ctx,
3326 qp->div->n_col - 2, g_dst_pos, g_src_pos, n);
3327 if (!reordering)
3328 goto error;
3329
3330 qp->upoly = reorder(qp->upoly, reordering);
3331 free(reordering);
3332 if (!qp->upoly)
3333 goto error;
3334
3335 qp->dim = isl_space_move_dims(qp->dim, dst_type, dst_pos, src_type, src_pos, n);
3336 if (!qp->dim)
3337 goto error;
3338
3339 return qp;
3340error:
3341 isl_qpolynomial_free(qp);
3342 return NULL((void*)0);
3343}
3344
3345__isl_give isl_qpolynomial *isl_qpolynomial_from_affine(__isl_take isl_space *dim,
3346 isl_int *f, isl_int denom)
3347{
3348 struct isl_upoly *up;
3349
3350 dim = isl_space_domain(dim);
3351 if (!dim)
3352 return NULL((void*)0);
3353
3354 up = isl_upoly_from_affine(dim->ctx, f, denom,
3355 1 + isl_space_dim(dim, isl_dim_all));
3356
3357 return isl_qpolynomial_alloc(dim, 0, up);
3358}
3359
3360__isl_give isl_qpolynomial *isl_qpolynomial_from_aff(__isl_take isl_aff *aff)
3361{
3362 isl_ctx *ctx;
3363 struct isl_upoly *up;
3364 isl_qpolynomial *qp;
3365
3366 if (!aff)
3367 return NULL((void*)0);
3368
3369 ctx = isl_aff_get_ctx(aff);
3370 up = isl_upoly_from_affine(ctx, aff->v->el + 1, aff->v->el[0],
3371 aff->v->size - 1);
3372
3373 qp = isl_qpolynomial_alloc(isl_aff_get_domain_space(aff),
3374 aff->ls->div->n_row, up);
3375 if (!qp)
3376 goto error;
3377
3378 isl_mat_free(qp->div);
3379 qp->div = isl_mat_copy(aff->ls->div);
3380 qp->div = isl_mat_cow(qp->div);
3381 if (!qp->div)
3382 goto error;
3383
3384 isl_aff_free(aff);
3385 qp = reduce_divs(qp);
3386 qp = remove_redundant_divs(qp);
3387 return qp;
3388error:
3389 isl_aff_free(aff);
3390 return isl_qpolynomial_free(qp);
3391}
3392
3393__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_pw_aff(
3394 __isl_take isl_pw_aff *pwaff)
3395{
3396 int i;
3397 isl_pw_qpolynomial *pwqp;
3398
3399 if (!pwaff)
3400 return NULL((void*)0);
3401
3402 pwqp = isl_pw_qpolynomial_alloc_size(isl_pw_aff_get_space(pwaff),
3403 pwaff->n);
3404
3405 for (i = 0; i < pwaff->n; ++i) {
3406 isl_setisl_map *dom;
3407 isl_qpolynomial *qp;
3408
3409 dom = isl_set_copy(pwaff->p[i].set);
3410 qp = isl_qpolynomial_from_aff(isl_aff_copy(pwaff->p[i].aff));
3411 pwqp = isl_pw_qpolynomial_add_piece(pwqp, dom, qp);
3412 }
3413
3414 isl_pw_aff_free(pwaff);
3415 return pwqp;
3416}
3417
3418__isl_give isl_qpolynomial *isl_qpolynomial_from_constraint(
3419 __isl_take isl_constraint *c, enum isl_dim_type type, unsigned pos)
3420{
3421 isl_aff *aff;
3422
3423 aff = isl_constraint_get_bound(c, type, pos);
3424 isl_constraint_free(c);
3425 return isl_qpolynomial_from_aff(aff);
3426}
3427
3428/* For each 0 <= i < "n", replace variable "first" + i of type "type"
3429 * in "qp" by subs[i].
3430 */
3431__isl_give isl_qpolynomial *isl_qpolynomial_substitute(
3432 __isl_take isl_qpolynomial *qp,
3433 enum isl_dim_type type, unsigned first, unsigned n,
3434 __isl_keep isl_qpolynomial **subs)
3435{
3436 int i;
3437 struct isl_upoly **ups;
3438
3439 if (n == 0)
3440 return qp;
3441
3442 qp = isl_qpolynomial_cow(qp);
3443 if (!qp)
3444 return NULL((void*)0);
3445
3446 if (type == isl_dim_out)
3447 isl_die(qp->dim->ctx, isl_error_invalid,do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "cannot substitute output/set dimension"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3449); goto error; } while (0)
3448 "cannot substitute output/set dimension",do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "cannot substitute output/set dimension"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3449); goto error; } while (0)
3449 goto error)do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "cannot substitute output/set dimension"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3449); goto error; } while (0)
;
3450 if (type == isl_dim_in)
3451 type = isl_dim_set;
3452
3453 for (i = 0; i < n; ++i)
3454 if (!subs[i])
3455 goto error;
3456
3457 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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3458); goto error; } while (0); } while (0)
3458 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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3458); goto error; } while (0); } while (0)
;
3459
3460 for (i = 0; i < n; ++i)
3461 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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3462); goto error; } while (0); } while (0)
3462 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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3462); goto error; } while (0); } while (0)
;
3463
3464 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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3464); goto error; } while (0); } while (0)
;
3465 for (i = 0; i < n; ++i)
3466 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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3466); goto error; } while (0); } while (0)
;
3467
3468 first += pos(qp->dim, type);
3469
3470 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 *)))
;
3471 if (!ups)
3472 goto error;
3473 for (i = 0; i < n; ++i)
3474 ups[i] = subs[i]->upoly;
3475
3476 qp->upoly = isl_upoly_subs(qp->upoly, first, n, ups);
3477
3478 free(ups);
3479
3480 if (!qp->upoly)
3481 goto error;
3482
3483 return qp;
3484error:
3485 isl_qpolynomial_free(qp);
3486 return NULL((void*)0);
3487}
3488
3489/* Extend "bset" with extra set dimensions for each integer division
3490 * in "qp" and then call "fn" with the extended bset and the polynomial
3491 * that results from replacing each of the integer divisions by the
3492 * corresponding extra set dimension.
3493 */
3494isl_stat isl_qpolynomial_as_polynomial_on_domain(__isl_keep isl_qpolynomial *qp,
3495 __isl_keep isl_basic_setisl_basic_map *bset,
3496 isl_stat (*fn)(__isl_take isl_basic_setisl_basic_map *bset,
3497 __isl_take isl_qpolynomial *poly, void *user), void *user)
3498{
3499 isl_space *dim;
3500 isl_mat *div;
3501 isl_qpolynomial *poly;
3502
3503 if (!qp || !bset)
3504 return isl_stat_error;
3505 if (qp->div->n_row == 0)
3506 return fn(isl_basic_set_copy(bset), isl_qpolynomial_copy(qp),
3507 user);
3508
3509 div = isl_mat_copy(qp->div);
3510 dim = isl_space_copy(qp->dim);
3511 dim = isl_space_add_dims(dim, isl_dim_set, qp->div->n_row);
3512 poly = isl_qpolynomial_alloc(dim, 0, isl_upoly_copy(qp->upoly));
3513 bset = isl_basic_set_copy(bset);
3514 bset = isl_basic_set_add_dims(bset, isl_dim_set, qp->div->n_row);
3515 bset = add_div_constraints(bset, div);
3516
3517 return fn(bset, poly, user);
3518}
3519
3520/* Return total degree in variables first (inclusive) up to last (exclusive).
3521 */
3522int isl_upoly_degree(__isl_keep struct isl_upoly *up, int first, int last)
3523{
3524 int deg = -1;
3525 int i;
3526 struct isl_upoly_rec *rec;
3527
3528 if (!up)
3529 return -2;
3530 if (isl_upoly_is_zero(up))
3531 return -1;
3532 if (isl_upoly_is_cst(up) || up->var < first)
3533 return 0;
3534
3535 rec = isl_upoly_as_rec(up);
3536 if (!rec)
3537 return -2;
3538
3539 for (i = 0; i < rec->n; ++i) {
3540 int d;
3541
3542 if (isl_upoly_is_zero(rec->p[i]))
3543 continue;
3544 d = isl_upoly_degree(rec->p[i], first, last);
3545 if (up->var < last)
3546 d += i;
3547 if (d > deg)
3548 deg = d;
3549 }
3550
3551 return deg;
3552}
3553
3554/* Return total degree in set variables.
3555 */
3556int isl_qpolynomial_degree(__isl_keep isl_qpolynomial *poly)
3557{
3558 unsigned ovar;
3559 unsigned nvar;
3560
3561 if (!poly)
3562 return -2;
3563
3564 ovar = isl_space_offset(poly->dim, isl_dim_set);
3565 nvar = isl_space_dim(poly->dim, isl_dim_set);
3566 return isl_upoly_degree(poly->upoly, ovar, ovar + nvar);
3567}
3568
3569__isl_give struct isl_upoly *isl_upoly_coeff(__isl_keep struct isl_upoly *up,
3570 unsigned pos, int deg)
3571{
3572 int i;
3573 struct isl_upoly_rec *rec;
3574
3575 if (!up)
3576 return NULL((void*)0);
3577
3578 if (isl_upoly_is_cst(up) || up->var < pos) {
3579 if (deg == 0)
3580 return isl_upoly_copy(up);
3581 else
3582 return isl_upoly_zero(up->ctx);
3583 }
3584
3585 rec = isl_upoly_as_rec(up);
3586 if (!rec)
3587 return NULL((void*)0);
3588
3589 if (up->var == pos) {
3590 if (deg < rec->n)
3591 return isl_upoly_copy(rec->p[deg]);
3592 else
3593 return isl_upoly_zero(up->ctx);
3594 }
3595
3596 up = isl_upoly_copy(up);
3597 up = isl_upoly_cow(up);
3598 rec = isl_upoly_as_rec(up);
3599 if (!rec)
3600 goto error;
3601
3602 for (i = 0; i < rec->n; ++i) {
3603 struct isl_upoly *t;
3604 t = isl_upoly_coeff(rec->p[i], pos, deg);
3605 if (!t)
3606 goto error;
3607 isl_upoly_free(rec->p[i]);
3608 rec->p[i] = t;
3609 }
3610
3611 return up;
3612error:
3613 isl_upoly_free(up);
3614 return NULL((void*)0);
3615}
3616
3617/* Return coefficient of power "deg" of variable "t_pos" of type "type".
3618 */
3619__isl_give isl_qpolynomial *isl_qpolynomial_coeff(
3620 __isl_keep isl_qpolynomial *qp,
3621 enum isl_dim_type type, unsigned t_pos, int deg)
3622{
3623 unsigned g_pos;
3624 struct isl_upoly *up;
3625 isl_qpolynomial *c;
3626
3627 if (!qp)
3628 return NULL((void*)0);
3629
3630 if (type == isl_dim_out)
3631 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"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3633); return ((void*)0); } while (0)
3632 "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"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3633); return ((void*)0); } while (0)
3633 return NULL)do { isl_handle_error(qp->div->ctx, isl_error_invalid, "output/set dimension does not have a coefficient"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3633); return ((void*)0); } while (0)
;
3634 if (type == isl_dim_in)
3635 type = isl_dim_set;
3636
3637 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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3638); return ((void*)0); } while (0); } while (0)
3638 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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3638); return ((void*)0); } while (0); } while (0)
;
3639
3640 g_pos = pos(qp->dim, type) + t_pos;
3641 up = isl_upoly_coeff(qp->upoly, g_pos, deg);
3642
3643 c = isl_qpolynomial_alloc(isl_space_copy(qp->dim), qp->div->n_row, up);
3644 if (!c)
3645 return NULL((void*)0);
3646 isl_mat_free(c->div);
3647 c->div = isl_mat_copy(qp->div);
3648 if (!c->div)
3649 goto error;
3650 return c;
3651error:
3652 isl_qpolynomial_free(c);
3653 return NULL((void*)0);
3654}
3655
3656/* Homogenize the polynomial in the variables first (inclusive) up to
3657 * last (exclusive) by inserting powers of variable first.
3658 * Variable first is assumed not to appear in the input.
3659 */
3660__isl_give struct isl_upoly *isl_upoly_homogenize(
3661 __isl_take struct isl_upoly *up, int deg, int target,
3662 int first, int last)
3663{
3664 int i;
3665 struct isl_upoly_rec *rec;
3666
3667 if (!up)
3668 return NULL((void*)0);
3669 if (isl_upoly_is_zero(up))
3670 return up;
3671 if (deg == target)
3672 return up;
3673 if (isl_upoly_is_cst(up) || up->var < first) {
3674 struct isl_upoly *hom;
3675
3676 hom = isl_upoly_var_pow(up->ctx, first, target - deg);
3677 if (!hom)
3678 goto error;
3679 rec = isl_upoly_as_rec(hom);
3680 rec->p[target - deg] = isl_upoly_mul(rec->p[target - deg], up);
3681
3682 return hom;
3683 }
3684
3685 up = isl_upoly_cow(up);
3686 rec = isl_upoly_as_rec(up);
3687 if (!rec)
3688 goto error;
3689
3690 for (i = 0; i < rec->n; ++i) {
3691 if (isl_upoly_is_zero(rec->p[i]))
3692 continue;
3693 rec->p[i] = isl_upoly_homogenize(rec->p[i],
3694 up->var < last ? deg + i : i, target,
3695 first, last);
3696 if (!rec->p[i])
3697 goto error;
3698 }
3699
3700 return up;
3701error:
3702 isl_upoly_free(up);
3703 return NULL((void*)0);
3704}
3705
3706/* Homogenize the polynomial in the set variables by introducing
3707 * powers of an extra set variable at position 0.
3708 */
3709__isl_give isl_qpolynomial *isl_qpolynomial_homogenize(
3710 __isl_take isl_qpolynomial *poly)
3711{
3712 unsigned ovar;
3713 unsigned nvar;
3714 int deg = isl_qpolynomial_degree(poly);
3715
3716 if (deg < -1)
3717 goto error;
3718
3719 poly = isl_qpolynomial_insert_dims(poly, isl_dim_in, 0, 1);
3720 poly = isl_qpolynomial_cow(poly);
3721 if (!poly)
3722 goto error;
3723
3724 ovar = isl_space_offset(poly->dim, isl_dim_set);
3725 nvar = isl_space_dim(poly->dim, isl_dim_set);
3726 poly->upoly = isl_upoly_homogenize(poly->upoly, 0, deg,
3727 ovar, ovar + nvar);
3728 if (!poly->upoly)
3729 goto error;
3730
3731 return poly;
3732error:
3733 isl_qpolynomial_free(poly);
3734 return NULL((void*)0);
3735}
3736
3737__isl_give isl_term *isl_term_alloc(__isl_take isl_space *dim,
3738 __isl_take isl_mat *div)
3739{
3740 isl_term *term;
3741 int n;
3742
3743 if (!dim || !div)
3744 goto error;
3745
3746 n = isl_space_dim(dim, isl_dim_all) + div->n_row;
3747
3748 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)))
3749 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)))
;
3750 if (!term)
3751 goto error;
3752
3753 term->ref = 1;
3754 term->dim = dim;
3755 term->div = div;
3756 isl_int_init(term->n)isl_sioimath_init((term->n));
3757 isl_int_init(term->d)isl_sioimath_init((term->d));
3758
3759 return term;
3760error:
3761 isl_space_free(dim);
3762 isl_mat_free(div);
3763 return NULL((void*)0);
3764}
3765
3766__isl_give isl_term *isl_term_copy(__isl_keep isl_term *term)
3767{
3768 if (!term)
3769 return NULL((void*)0);
3770
3771 term->ref++;
3772 return term;
3773}
3774
3775__isl_give isl_term *isl_term_dup(__isl_keep isl_term *term)
3776{
3777 int i;
3778 isl_term *dup;
3779 unsigned total;
3780
3781 if (!term)
3782 return NULL((void*)0);
3783
3784 total = isl_space_dim(term->dim, isl_dim_all) + term->div->n_row;
3785
3786 dup = isl_term_alloc(isl_space_copy(term->dim), isl_mat_copy(term->div));
3787 if (!dup)
3788 return NULL((void*)0);
3789
3790 isl_int_set(dup->n, term->n)isl_sioimath_set((dup->n), *(term->n));
3791 isl_int_set(dup->d, term->d)isl_sioimath_set((dup->d), *(term->d));
3792
3793 for (i = 0; i < total; ++i)
3794 dup->pow[i] = term->pow[i];
3795
3796 return dup;
3797}
3798
3799__isl_give isl_term *isl_term_cow(__isl_take isl_term *term)
3800{
3801 if (!term)
3802 return NULL((void*)0);
3803
3804 if (term->ref == 1)
3805 return term;
3806 term->ref--;
3807 return isl_term_dup(term);
3808}
3809
3810void isl_term_free(__isl_take isl_term *term)
3811{
3812 if (!term)
3813 return;
3814
3815 if (--term->ref > 0)
3816 return;
3817
3818 isl_space_free(term->dim);
3819 isl_mat_free(term->div);
3820 isl_int_clear(term->n)isl_sioimath_clear((term->n));
3821 isl_int_clear(term->d)isl_sioimath_clear((term->d));
3822 free(term);
3823}
3824
3825unsigned isl_term_dim(__isl_keep isl_term *term, enum isl_dim_type type)
3826{
3827 if (!term)
3828 return 0;
3829
3830 switch (type) {
3831 case isl_dim_param:
3832 case isl_dim_in:
3833 case isl_dim_out: return isl_space_dim(term->dim, type);
3834 case isl_dim_div: return term->div->n_row;
3835 case isl_dim_all: return isl_space_dim(term->dim, isl_dim_all) +
3836 term->div->n_row;
3837 default: return 0;
3838 }
3839}
3840
3841isl_ctx *isl_term_get_ctx(__isl_keep isl_term *term)
3842{
3843 return term ? term->dim->ctx : NULL((void*)0);
3844}
3845
3846void isl_term_get_num(__isl_keep isl_term *term, isl_int *n)
3847{
3848 if (!term)
3849 return;
3850 isl_int_set(*n, term->n)isl_sioimath_set((*n), *(term->n));
3851}
3852
3853void isl_term_get_den(__isl_keep isl_term *term, isl_int *d)
3854{
3855 if (!term)
3856 return;
3857 isl_int_set(*d, term->d)isl_sioimath_set((*d), *(term->d));
3858}
3859
3860/* Return the coefficient of the term "term".
3861 */
3862__isl_give isl_val *isl_term_get_coefficient_val(__isl_keep isl_term *term)
3863{
3864 if (!term)
3865 return NULL((void*)0);
3866
3867 return isl_val_rat_from_isl_int(isl_term_get_ctx(term),
3868 term->n, term->d);
3869}
3870
3871int isl_term_get_exp(__isl_keep isl_term *term,
3872 enum isl_dim_type type, unsigned pos)
3873{
3874 if (!term)
3875 return -1;
3876
3877 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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3877); return -1; } while (0); } while (0)
;
3878
3879 if (type >= isl_dim_set)
3880 pos += isl_space_dim(term->dim, isl_dim_param);
3881 if (type >= isl_dim_div)
3882 pos += isl_space_dim(term->dim, isl_dim_set);
3883
3884 return term->pow[pos];
3885}
3886
3887__isl_give isl_aff *isl_term_get_div(__isl_keep isl_term *term, unsigned pos)
3888{
3889 isl_local_space *ls;
3890 isl_aff *aff;
3891
3892 if (!term)
3893 return NULL((void*)0);
3894
3895 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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3896); return ((void*)0); } while (0); } while (0)
3896 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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3896); return ((void*)0); } while (0); } while (0)
;
3897
3898 ls = isl_local_space_alloc_div(isl_space_copy(term->dim),
3899 isl_mat_copy(term->div));
3900 aff = isl_aff_alloc(ls);
3901 if (!aff)
3902 return NULL((void*)0);
3903
3904 isl_seq_cpy(aff->v->el, term->div->row[pos], aff->v->size);
3905
3906 aff = isl_aff_normalize(aff);
3907
3908 return aff;
3909}
3910
3911__isl_give isl_term *isl_upoly_foreach_term(__isl_keep struct isl_upoly *up,
3912 isl_stat (*fn)(__isl_take isl_term *term, void *user),
3913 __isl_take isl_term *term, void *user)
3914{
3915 int i;
3916 struct isl_upoly_rec *rec;
3917
3918 if (!up || !term)
3919 goto error;
3920
3921 if (isl_upoly_is_zero(up))
3922 return term;
3923
3924 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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3924); goto error; } while (0); } while (0)
;
3925 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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3925); goto error; } while (0); } while (0)
;
3926 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", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 3926); goto error; } while (0); } while (0)
;
3927
3928 if (isl_upoly_is_cst(up)) {
3929 struct isl_upoly_cst *cst;
3930 cst = isl_upoly_as_cst(up);
3931 if (!cst)
3932 goto error;
3933 term = isl_term_cow(term);
3934 if (!term)
3935 goto error;
3936 isl_int_set(term->n, cst->n)isl_sioimath_set((term->n), *(cst->n));
3937 isl_int_set(term->d, cst->d)isl_sioimath_set((term->d), *(cst->d));
3938 if (fn(isl_term_copy(term), user) < 0)
3939 goto error;
3940 return term;
3941 }
3942
3943 rec = isl_upoly_as_rec(up);
3944 if (!rec)
3945 goto error;
3946
3947 for (i = 0; i < rec->n; ++i) {
3948 term = isl_term_cow(term);
3949 if (!term)
3950 goto error;
3951 term->pow[up->var] = i;
3952 term = isl_upoly_foreach_term(rec->p[i], fn, term, user);
3953 if (!term)
3954 goto error;
3955 }
3956 term->pow[up->var] = 0;
3957
3958 return term;
3959error:
3960 isl_term_free(term);
3961 return NULL((void*)0);
3962}
3963
3964isl_stat isl_qpolynomial_foreach_term(__isl_keep isl_qpolynomial *qp,
3965 isl_stat (*fn)(__isl_take isl_term *term, void *user), void *user)
3966{
3967 isl_term *term;
3968
3969 if (!qp)
3970 return isl_stat_error;
3971
3972 term = isl_term_alloc(isl_space_copy(qp->dim), isl_mat_copy(qp->div));
3973 if (!term)
3974 return isl_stat_error;
3975
3976 term = isl_upoly_foreach_term(qp->upoly, fn, term, user);
3977
3978 isl_term_free(term);
3979
3980 return term ? isl_stat_ok : isl_stat_error;
3981}
3982
3983__isl_give isl_qpolynomial *isl_qpolynomial_from_term(__isl_take isl_term *term)
3984{
3985 struct isl_upoly *up;
3986 isl_qpolynomial *qp;
3987 int i, n;
3988
3989 if (!term)
3990 return NULL((void*)0);
3991
3992 n = isl_space_dim(term->dim, isl_dim_all) + term->div->n_row;
3993
3994 up = isl_upoly_rat_cst(term->dim->ctx, term->n, term->d);
3995 for (i = 0; i < n; ++i) {
3996 if (!term->pow[i])
3997 continue;
3998 up = isl_upoly_mul(up,
3999 isl_upoly_var_pow(term->dim->ctx, i, term->pow[i]));
4000 }
4001
4002 qp = isl_qpolynomial_alloc(isl_space_copy(term->dim), term->div->n_row, up);
4003 if (!qp)
4004 goto error;
4005 isl_mat_free(qp->div);
4006 qp->div = isl_mat_copy(term->div);
4007 if (!qp->div)
4008 goto error;
4009
4010 isl_term_free(term);
4011 return qp;
4012error:
4013 isl_qpolynomial_free(qp);
4014 isl_term_free(term);
4015 return NULL((void*)0);
4016}
4017
4018__isl_give isl_qpolynomial *isl_qpolynomial_lift(__isl_take isl_qpolynomial *qp,
4019 __isl_take isl_space *dim)
4020{
4021 int i;
4022 int extra;
4023 unsigned total;
4024
4025 if (!qp || !dim)
4026 goto error;
4027
4028 if (isl_space_is_equal(qp->dim, dim)) {
4029 isl_space_free(dim);
4030 return qp;
4031 }
4032
4033 qp = isl_qpolynomial_cow(qp);
4034 if (!qp)
4035 goto error;
4036
4037 extra = isl_space_dim(dim, isl_dim_set) -
4038 isl_space_dim(qp->dim, isl_dim_set);
4039 total = isl_space_dim(qp->dim, isl_dim_all);
4040 if (qp->div->n_row) {
4041 int *exp;
4042
4043 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)))
;
4044 if (!exp)
4045 goto error;
4046 for (i = 0; i < qp->div->n_row; ++i)
4047 exp[i] = extra + i;
4048 qp->upoly = expand(qp->upoly, exp, total);
4049 free(exp);
4050 if (!qp->upoly)
4051 goto error;
4052 }
4053 qp->div = isl_mat_insert_cols(qp->div, 2 + total, extra);
4054 if (!qp->div)
4055 goto error;
4056 for (i = 0; i < qp->div->n_row; ++i)
4057 isl_seq_clr(qp->div->row[i] + 2 + total, extra);
4058
4059 isl_space_free(qp->dim);
4060 qp->dim = dim;
4061
4062 return qp;
4063error:
4064 isl_space_free(dim);
4065 isl_qpolynomial_free(qp);
4066 return NULL((void*)0);
4067}
4068
4069/* For each parameter or variable that does not appear in qp,
4070 * first eliminate the variable from all constraints and then set it to zero.
4071 */
4072static __isl_give isl_setisl_map *fix_inactive(__isl_take isl_setisl_map *set,
4073 __isl_keep isl_qpolynomial *qp)
4074{
4075 int *active = NULL((void*)0);
4076 int i;
4077 int d;
4078 unsigned nparam;
4079 unsigned nvar;
4080
4081 if (!set || !qp)
4082 goto error;
4083
4084 d = isl_space_dim(set->dim, isl_dim_all);
4085 active = isl_calloc_array(set->ctx, int, d)((int *)isl_calloc_or_die(set->ctx, d, sizeof(int)));
4086 if (set_active(qp, active) < 0)
4087 goto error;
4088
4089 for (i = 0; i < d; ++i)
4090 if (!active[i])
4091 break;
4092
4093 if (i == d) {
4094 free(active);
4095 return set;
4096 }
4097
4098 nparam = isl_space_dim(set->dim, isl_dim_param);
4099 nvar = isl_space_dim(set->dim, isl_dim_set);
4100 for (i = 0; i < nparam; ++i) {
4101 if (active[i])
4102 continue;
4103 set = isl_set_eliminate(set, isl_dim_param, i, 1);
4104 set = isl_set_fix_si(set, isl_dim_param, i, 0);
4105 }
4106 for (i = 0; i < nvar; ++i) {
4107 if (active[nparam + i])
4108 continue;
4109 set = isl_set_eliminate(set, isl_dim_set, i, 1);
4110 set = isl_set_fix_si(set, isl_dim_set, i, 0);
4111 }
4112
4113 free(active);
4114
4115 return set;
4116error:
4117 free(active);
4118 isl_set_free(set);
4119 return NULL((void*)0);
4120}
4121
4122struct isl_opt_data {
4123 isl_qpolynomial *qp;
4124 int first;
4125 isl_val *opt;
4126 int max;
4127};
4128
4129static isl_stat opt_fn(__isl_take isl_point *pnt, void *user)
4130{
4131 struct isl_opt_data *data = (struct isl_opt_data *)user;
4132 isl_val *val;
4133
4134 val = isl_qpolynomial_eval(isl_qpolynomial_copy(data->qp), pnt);
4135 if (data->first) {
4136 data->first = 0;
4137 data->opt = val;
4138 } else if (data->max) {
4139 data->opt = isl_val_max(data->opt, val);
4140 } else {
4141 data->opt = isl_val_min(data->opt, val);
4142 }
4143
4144 return isl_stat_ok;
4145}
4146
4147__isl_give isl_val *isl_qpolynomial_opt_on_domain(
4148 __isl_take isl_qpolynomial *qp, __isl_take isl_setisl_map *set, int max)
4149{
4150 struct isl_opt_data data = { NULL((void*)0), 1, NULL((void*)0), max };
4151
4152 if (!set || !qp)
4153 goto error;
4154
4155 if (isl_upoly_is_cst(qp->upoly)) {
4156 isl_set_free(set);
4157 data.opt = isl_qpolynomial_get_constant_val(qp);
4158 isl_qpolynomial_free(qp);
4159 return data.opt;
4160 }
4161
4162 set = fix_inactive(set, qp);
4163
4164 data.qp = qp;
4165 if (isl_set_foreach_point(set, opt_fn, &data) < 0)
4166 goto error;
4167
4168 if (data.first)
4169 data.opt = isl_val_zero(isl_set_get_ctx(set));
4170
4171 isl_set_free(set);
4172 isl_qpolynomial_free(qp);
4173 return data.opt;
4174error:
4175 isl_set_free(set);
4176 isl_qpolynomial_free(qp);
4177 isl_val_free(data.opt);
4178 return NULL((void*)0);
4179}
4180
4181__isl_give isl_qpolynomial *isl_qpolynomial_morph_domain(
4182 __isl_take isl_qpolynomial *qp, __isl_take isl_morph *morph)
4183{
4184 int i;
4185 int n_sub;
4186 isl_ctx *ctx;
4187 struct isl_upoly **subs;
4188 isl_mat *mat, *diag;
4189
4190 qp = isl_qpolynomial_cow(qp);
4191 if (!qp || !morph)
4192 goto error;
4193
4194 ctx = qp->dim->ctx;
4195 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"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 4195); goto error; } while (0); } while (0)
;
4196
4197 n_sub = morph->inv->n_row - 1;
4198 if (morph->inv->n_row != morph->inv->n_col)
4199 n_sub += qp->div->n_row;
4200 subs = isl_calloc_array(ctx, struct isl_upoly *, n_sub)((struct isl_upoly * *)isl_calloc_or_die(ctx, n_sub, sizeof(struct
isl_upoly *)))
;
4201 if (n_sub && !subs)
4202 goto error;
4203
4204 for (i = 0; 1 + i < morph->inv->n_row; ++i)
4205 subs[i] = isl_upoly_from_affine(ctx, morph->inv->row[1 + i],
4206 morph->inv->row[0][0], morph->inv->n_col);
4207 if (morph->inv->n_row != morph->inv->n_col)
4208 for (i = 0; i < qp->div->n_row; ++i)
4209 subs[morph->inv->n_row - 1 + i] =
4210 isl_upoly_var_pow(ctx, morph->inv->n_col - 1 + i, 1);
4211
4212 qp->upoly = isl_upoly_subs(qp->upoly, 0, n_sub, subs);
4213
4214 for (i = 0; i < n_sub; ++i)
4215 isl_upoly_free(subs[i]);
4216 free(subs);
4217
4218 diag = isl_mat_diag(ctx, 1, morph->inv->row[0][0]);
4219 mat = isl_mat_diagonal(diag, isl_mat_copy(morph->inv));
4220 diag = isl_mat_diag(ctx, qp->div->n_row, morph->inv->row[0][0]);
4221 mat = isl_mat_diagonal(mat, diag);
4222 qp->div = isl_mat_product(qp->div, mat);
4223 isl_space_free(qp->dim);
4224 qp->dim = isl_space_copy(morph->ran->dim);
4225
4226 if (!qp->upoly || !qp->div || !qp->dim)
4227 goto error;
4228
4229 isl_morph_free(morph);
4230
4231 return qp;
4232error:
4233 isl_qpolynomial_free(qp);
4234 isl_morph_free(morph);
4235 return NULL((void*)0);
4236}
4237
4238__isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_mul(
4239 __isl_take isl_union_pw_qpolynomial *upwqp1,
4240 __isl_take isl_union_pw_qpolynomial *upwqp2)
4241{
4242 return isl_union_pw_qpolynomial_match_bin_op(upwqp1, upwqp2,
4243 &isl_pw_qpolynomial_mul);
4244}
4245
4246/* Reorder the columns of the given div definitions according to the
4247 * given reordering.
4248 */
4249static __isl_give isl_mat *reorder_divs(__isl_take isl_mat *div,
4250 __isl_take isl_reordering *r)
4251{
4252 int i, j;
4253 isl_mat *mat;
4254 int extra;
4255
4256 if (!div || !r)
4257 goto error;
4258
4259 extra = isl_space_dim(r->dim, isl_dim_all) + div->n_row - r->len;
4260 mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
4261 if (!mat)
4262 goto error;
4263
4264 for (i = 0; i < div->n_row; ++i) {
4265 isl_seq_cpy(mat->row[i], div->row[i], 2);
4266 isl_seq_clr(mat->row[i] + 2, mat->n_col - 2);
4267 for (j = 0; j < r->len; ++j)
4268 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]))
4269 div->row[i][2 + j])isl_sioimath_set((mat->row[i][2 + r->pos[j]]), *(div->
row[i][2 + j]))
;
4270 }
4271
4272 isl_reordering_free(r);
4273 isl_mat_free(div);
4274 return mat;
4275error:
4276 isl_reordering_free(r);
4277 isl_mat_free(div);
4278 return NULL((void*)0);
4279}
4280
4281/* Reorder the dimension of "qp" according to the given reordering.
4282 */
4283__isl_give isl_qpolynomial *isl_qpolynomial_realign_domain(
4284 __isl_take isl_qpolynomial *qp, __isl_take isl_reordering *r)
4285{
4286 qp = isl_qpolynomial_cow(qp);
4287 if (!qp)
4288 goto error;
4289
4290 r = isl_reordering_extend(r, qp->div->n_row);
4291 if (!r)
4292 goto error;
4293
4294 qp->div = reorder_divs(qp->div, isl_reordering_copy(r));
4295 if (!qp->div)
4296 goto error;
4297
4298 qp->upoly = reorder(qp->upoly, r->pos);
4299 if (!qp->upoly)
4300 goto error;
4301
4302 qp = isl_qpolynomial_reset_domain_space(qp, isl_space_copy(r->dim));
4303
4304 isl_reordering_free(r);
4305 return qp;
4306error:
4307 isl_qpolynomial_free(qp);
4308 isl_reordering_free(r);
4309 return NULL((void*)0);
4310}
4311
4312__isl_give isl_qpolynomial *isl_qpolynomial_align_params(
4313 __isl_take isl_qpolynomial *qp, __isl_take isl_space *model)
4314{
4315 isl_bool equal_params;
4316
4317 if (!qp || !model)
4318 goto error;
4319
4320 equal_params = isl_space_has_equal_params(qp->dim, model);
4321 if (equal_params < 0)
4322 goto error;
4323 if (!equal_params) {
4324 isl_reordering *exp;
4325
4326 model = isl_space_drop_dims(model, isl_dim_in,
4327 0, isl_space_dim(model, isl_dim_in));
4328 model = isl_space_drop_dims(model, isl_dim_out,
4329 0, isl_space_dim(model, isl_dim_out));
4330 exp = isl_parameter_alignment_reordering(qp->dim, model);
4331 exp = isl_reordering_extend_space(exp,
4332 isl_qpolynomial_get_domain_space(qp));
4333 qp = isl_qpolynomial_realign_domain(qp, exp);
4334 }
4335
4336 isl_space_free(model);
4337 return qp;
4338error:
4339 isl_space_free(model);
4340 isl_qpolynomial_free(qp);
4341 return NULL((void*)0);
4342}
4343
4344struct isl_split_periods_data {
4345 int max_periods;
4346 isl_pw_qpolynomial *res;
4347};
4348
4349/* Create a slice where the integer division "div" has the fixed value "v".
4350 * In particular, if "div" refers to floor(f/m), then create a slice
4351 *
4352 * m v <= f <= m v + (m - 1)
4353 *
4354 * or
4355 *
4356 * f - m v >= 0
4357 * -f + m v + (m - 1) >= 0
4358 */
4359static __isl_give isl_setisl_map *set_div_slice(__isl_take isl_space *dim,
4360 __isl_keep isl_qpolynomial *qp, int div, isl_int v)
4361{
4362 int total;
4363 isl_basic_setisl_basic_map *bset = NULL((void*)0);
4364 int k;
4365
4366 if (!dim || !qp)
4367 goto error;
4368
4369 total = isl_space_dim(dim, isl_dim_all);
4370 bset = isl_basic_set_alloc_space(isl_space_copy(dim), 0, 0, 2);
4371
4372 k = isl_basic_set_alloc_inequality(bset);
4373 if (k < 0)
4374 goto error;
4375 isl_seq_cpy(bset->ineq[k], qp->div->row[div] + 1, 1 + total);
4376 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]))
;
4377
4378 k = isl_basic_set_alloc_inequality(bset);
4379 if (k < 0)
4380 goto error;
4381 isl_seq_neg(bset->ineq[k], qp->div->row[div] + 1, 1 + total);
4382 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]))
;
4383 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]))
;
4384 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)
;
4385
4386 isl_space_free(dim);
4387 return isl_set_from_basic_set(bset);
4388error:
4389 isl_basic_set_free(bset);
4390 isl_space_free(dim);
4391 return NULL((void*)0);
4392}
4393
4394static isl_stat split_periods(__isl_take isl_setisl_map *set,
4395 __isl_take isl_qpolynomial *qp, void *user);
4396
4397/* Create a slice of the domain "set" such that integer division "div"
4398 * has the fixed value "v" and add the results to data->res,
4399 * replacing the integer division by "v" in "qp".
4400 */
4401static isl_stat set_div(__isl_take isl_setisl_map *set,
4402 __isl_take isl_qpolynomial *qp, int div, isl_int v,
4403 struct isl_split_periods_data *data)
4404{
4405 int i;
4406 int total;
4407 isl_setisl_map *slice;
4408 struct isl_upoly *cst;
4409
4410 slice = set_div_slice(isl_set_get_space(set), qp, div, v);
4411 set = isl_set_intersect(set, slice);
4412
4413 if (!qp)
4414 goto error;
4415
4416 total = isl_space_dim(qp->dim, isl_dim_all);
4417
4418 for (i = div + 1; i < qp->div->n_row; ++i) {
4419 if (isl_int_is_zero(qp->div->row[i][2 + total + div])(isl_sioimath_sgn(*(qp->div->row[i][2 + total + div])) ==
0)
)
4420 continue;
4421 isl_int_addmul(qp->div->row[i][1],isl_sioimath_addmul((qp->div->row[i][1]), *(qp->div->
row[i][2 + total + div]), *(v))
4422 qp->div->row[i][2 + total + div], v)isl_sioimath_addmul((qp->div->row[i][1]), *(qp->div->
row[i][2 + total + div]), *(v))
;
4423 isl_int_set_si(qp->div->row[i][2 + total + div], 0)isl_sioimath_set_si((qp->div->row[i][2 + total + div]),
0)
;
4424 }
4425
4426 cst = isl_upoly_rat_cst(qp->dim->ctx, v, qp->dim->ctx->one);
4427 qp = substitute_div(qp, div, cst);
4428
4429 return split_periods(set, qp, data);
4430error:
4431 isl_set_free(set);
4432 isl_qpolynomial_free(qp);
4433 return -1;
4434}
4435
4436/* Split the domain "set" such that integer division "div"
4437 * has a fixed value (ranging from "min" to "max") on each slice
4438 * and add the results to data->res.
4439 */
4440static isl_stat split_div(__isl_take isl_setisl_map *set,
4441 __isl_take isl_qpolynomial *qp, int div, isl_int min, isl_int max,
4442 struct isl_split_periods_data *data)
4443{
4444 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)) {
4445 isl_setisl_map *set_i = isl_set_copy(set);
4446 isl_qpolynomial *qp_i = isl_qpolynomial_copy(qp);
4447
4448 if (set_div(set_i, qp_i, div, min, data) < 0)
4449 goto error;
4450 }
4451 isl_set_free(set);
4452 isl_qpolynomial_free(qp);
4453 return isl_stat_ok;
4454error:
4455 isl_set_free(set);
4456 isl_qpolynomial_free(qp);
4457 return isl_stat_error;
4458}
4459
4460/* If "qp" refers to any integer division
4461 * that can only attain "max_periods" distinct values on "set"
4462 * then split the domain along those distinct values.
4463 * Add the results (or the original if no splitting occurs)
4464 * to data->res.
4465 */
4466static isl_stat split_periods(__isl_take isl_setisl_map *set,
4467 __isl_take isl_qpolynomial *qp, void *user)
4468{
4469 int i;
4470 isl_pw_qpolynomial *pwqp;
4471 struct isl_split_periods_data *data;
4472 isl_int min, max;
4473 int total;
4474 isl_stat r = isl_stat_ok;
4475
4476 data = (struct isl_split_periods_data *)user;
4477
4478 if (!set || !qp)
4479 goto error;
4480
4481 if (qp->div->n_row == 0) {
4482 pwqp = isl_pw_qpolynomial_alloc(set, qp);
4483 data->res = isl_pw_qpolynomial_add_disjoint(data->res, pwqp);
4484 return isl_stat_ok;
4485 }
4486
4487 isl_int_init(min)isl_sioimath_init((min));
4488 isl_int_init(max)isl_sioimath_init((max));
4489 total = isl_space_dim(qp->dim, isl_dim_all);
4490 for (i = 0; i < qp->div->n_row; ++i) {
4491 enum isl_lp_result lp_res;
4492
4493 if (isl_seq_first_non_zero(qp->div->row[i] + 2 + total,
4494 qp->div->n_row) != -1)
4495 continue;
4496
4497 lp_res = isl_set_solve_lp(set, 0, qp->div->row[i] + 1,
4498 set->ctx->one, &min, NULL((void*)0), NULL((void*)0));
4499 if (lp_res == isl_lp_error)
4500 goto error2;
4501 if (lp_res == isl_lp_unbounded || lp_res == isl_lp_empty)
4502 continue;
4503 isl_int_fdiv_q(min, min, qp->div->row[i][0])isl_sioimath_fdiv_q((min), *(min), *(qp->div->row[i][0]
))
;
4504
4505 lp_res = isl_set_solve_lp(set, 1, qp->div->row[i] + 1,
4506 set->ctx->one, &max, NULL((void*)0), NULL((void*)0));
4507 if (lp_res == isl_lp_error)
4508 goto error2;
4509 if (lp_res == isl_lp_unbounded || lp_res == isl_lp_empty)
4510 continue;
4511 isl_int_fdiv_q(max, max, qp->div->row[i][0])isl_sioimath_fdiv_q((max), *(max), *(qp->div->row[i][0]
))
;
4512
4513 isl_int_sub(max, max, min)isl_sioimath_sub((max), *(max), *(min));
4514 if (isl_int_cmp_si(max, data->max_periods)isl_sioimath_cmp_si(*(max), data->max_periods) < 0) {
4515 isl_int_add(max, max, min)isl_sioimath_add((max), *(max), *(min));
4516 break;
4517 }
4518 }
4519
4520 if (i < qp->div->n_row) {
4521 r = split_div(set, qp, i, min, max, data);
4522 } else {
4523 pwqp = isl_pw_qpolynomial_alloc(set, qp);
4524 data->res = isl_pw_qpolynomial_add_disjoint(data->res, pwqp);
4525 }
4526
4527 isl_int_clear(max)isl_sioimath_clear((max));
4528 isl_int_clear(min)isl_sioimath_clear((min));
4529
4530 return r;
4531error2:
4532 isl_int_clear(max)isl_sioimath_clear((max));
4533 isl_int_clear(min)isl_sioimath_clear((min));
4534error:
4535 isl_set_free(set);
4536 isl_qpolynomial_free(qp);
4537 return isl_stat_error;
4538}
4539
4540/* If any quasi-polynomial in pwqp refers to any integer division
4541 * that can only attain "max_periods" distinct values on its domain
4542 * then split the domain along those distinct values.
4543 */
4544__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_split_periods(
4545 __isl_take isl_pw_qpolynomial *pwqp, int max_periods)
4546{
4547 struct isl_split_periods_data data;
4548
4549 data.max_periods = max_periods;
4550 data.res = isl_pw_qpolynomial_zero(isl_pw_qpolynomial_get_space(pwqp));
4551
4552 if (isl_pw_qpolynomial_foreach_piece(pwqp, &split_periods, &data) < 0)
4553 goto error;
4554
4555 isl_pw_qpolynomial_free(pwqp);
4556
4557 return data.res;
4558error:
4559 isl_pw_qpolynomial_free(data.res);
4560 isl_pw_qpolynomial_free(pwqp);
4561 return NULL((void*)0);
4562}
4563
4564/* Construct a piecewise quasipolynomial that is constant on the given
4565 * domain. In particular, it is
4566 * 0 if cst == 0
4567 * 1 if cst == 1
4568 * infinity if cst == -1
4569 */
4570static __isl_give isl_pw_qpolynomial *constant_on_domain(
4571 __isl_take isl_basic_setisl_basic_map *bset, int cst)
4572{
4573 isl_space *dim;
4574 isl_qpolynomial *qp;
4575
4576 if (!bset)
4577 return NULL((void*)0);
4578
4579 bset = isl_basic_set_params(bset);
4580 dim = isl_basic_set_get_space(bset);
4581 if (cst < 0)
4582 qp = isl_qpolynomial_infty_on_domain(dim);
4583 else if (cst == 0)
4584 qp = isl_qpolynomial_zero_on_domain(dim);
4585 else
4586 qp = isl_qpolynomial_one_on_domain(dim);
4587 return isl_pw_qpolynomial_alloc(isl_set_from_basic_set(bset), qp);
4588}
4589
4590/* Factor bset, call fn on each of the factors and return the product.
4591 *
4592 * If no factors can be found, simply call fn on the input.
4593 * Otherwise, construct the factors based on the factorizer,
4594 * call fn on each factor and compute the product.
4595 */
4596static __isl_give isl_pw_qpolynomial *compressed_multiplicative_call(
4597 __isl_take isl_basic_setisl_basic_map *bset,
4598 __isl_give isl_pw_qpolynomial *(*fn)(__isl_take isl_basic_setisl_basic_map *bset))
4599{
4600 int i, n;
4601 isl_space *space;
4602 isl_setisl_map *set;
4603 isl_factorizer *f;
4604 isl_qpolynomial *qp;
4605 isl_pw_qpolynomial *pwqp;
4606 unsigned nparam;
4607 unsigned nvar;
4608
4609 f = isl_basic_set_factorizer(bset);
4610 if (!f)
4611 goto error;
4612 if (f->n_group == 0) {
4613 isl_factorizer_free(f);
4614 return fn(bset);
4615 }
4616
4617 nparam = isl_basic_set_dim(bset, isl_dim_param);
4618 nvar = isl_basic_set_dim(bset, isl_dim_set);
4619
4620 space = isl_basic_set_get_space(bset);
4621 space = isl_space_params(space);
4622 set = isl_set_universe(isl_space_copy(space));
4623 qp = isl_qpolynomial_one_on_domain(space);
4624 pwqp = isl_pw_qpolynomial_alloc(set, qp);
4625
4626 bset = isl_morph_basic_set(isl_morph_copy(f->morph), bset);
4627
4628 for (i = 0, n = 0; i < f->n_group; ++i) {
4629 isl_basic_setisl_basic_map *bset_i;
4630 isl_pw_qpolynomial *pwqp_i;
4631
4632 bset_i = isl_basic_set_copy(bset);
4633 bset_i = isl_basic_set_drop_constraints_involving(bset_i,
4634 nparam + n + f->len[i], nvar - n - f->len[i]);
4635 bset_i = isl_basic_set_drop_constraints_involving(bset_i,
4636 nparam, n);
4637 bset_i = isl_basic_set_drop(bset_i, isl_dim_set,
4638 n + f->len[i], nvar - n - f->len[i]);
4639 bset_i = isl_basic_set_drop(bset_i, isl_dim_set, 0, n);
4640
4641 pwqp_i = fn(bset_i);
4642 pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp_i);
4643
4644 n += f->len[i];
4645 }
4646
4647 isl_basic_set_free(bset);
4648 isl_factorizer_free(f);
4649
4650 return pwqp;
4651error:
4652 isl_basic_set_free(bset);
4653 return NULL((void*)0);
4654}
4655
4656/* Factor bset, call fn on each of the factors and return the product.
4657 * The function is assumed to evaluate to zero on empty domains,
4658 * to one on zero-dimensional domains and to infinity on unbounded domains
4659 * and will not be called explicitly on zero-dimensional or unbounded domains.
4660 *
4661 * We first check for some special cases and remove all equalities.
4662 * Then we hand over control to compressed_multiplicative_call.
4663 */
4664__isl_give isl_pw_qpolynomial *isl_basic_set_multiplicative_call(
4665 __isl_take isl_basic_setisl_basic_map *bset,
4666 __isl_give isl_pw_qpolynomial *(*fn)(__isl_take isl_basic_setisl_basic_map *bset))
4667{
4668 isl_bool bounded;
4669 isl_morph *morph;
4670 isl_pw_qpolynomial *pwqp;
4671
4672 if (!bset)
4673 return NULL((void*)0);
4674
4675 if (isl_basic_set_plain_is_empty(bset))
4676 return constant_on_domain(bset, 0);
4677
4678 if (isl_basic_set_dim(bset, isl_dim_set) == 0)
4679 return constant_on_domain(bset, 1);
4680
4681 bounded = isl_basic_set_is_bounded(bset);
4682 if (bounded < 0)
4683 goto error;
4684 if (!bounded)
4685 return constant_on_domain(bset, -1);
4686
4687 if (bset->n_eq == 0)
4688 return compressed_multiplicative_call(bset, fn);
4689
4690 morph = isl_basic_set_full_compression(bset);
4691 bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
4692
4693 pwqp = compressed_multiplicative_call(bset, fn);
4694
4695 morph = isl_morph_dom_params(morph);
4696 morph = isl_morph_ran_params(morph);
4697 morph = isl_morph_inverse(morph);
4698
4699 pwqp = isl_pw_qpolynomial_morph_domain(pwqp, morph);
4700
4701 return pwqp;
4702error:
4703 isl_basic_set_free(bset);
4704 return NULL((void*)0);
4705}
4706
4707/* Drop all floors in "qp", turning each integer division [a/m] into
4708 * a rational division a/m. If "down" is set, then the integer division
4709 * is replaced by (a-(m-1))/m instead.
4710 */
4711static __isl_give isl_qpolynomial *qp_drop_floors(
4712 __isl_take isl_qpolynomial *qp, int down)
4713{
4714 int i;
4715 struct isl_upoly *s;
4716
4717 if (!qp)
4718 return NULL((void*)0);
4719 if (qp->div->n_row == 0)
4720 return qp;
4721
4722 qp = isl_qpolynomial_cow(qp);
4723 if (!qp)
4724 return NULL((void*)0);
4725
4726 for (i = qp->div->n_row - 1; i >= 0; --i) {
4727 if (down) {
4728 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]))
4729 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]))
;
4730 isl_int_add_ui(qp->div->row[i][1],isl_sioimath_add_ui((qp->div->row[i][1]), *(qp->div->
row[i][1]), 1)
4731 qp->div->row[i][1], 1)isl_sioimath_add_ui((qp->div->row[i][1]), *(qp->div->
row[i][1]), 1)
;
4732 }
4733 s = isl_upoly_from_affine(qp->dim->ctx, qp->div->row[i] + 1,
4734 qp->div->row[i][0], qp->div->n_col - 1);
4735 qp = substitute_div(qp, i, s);
4736 if (!qp)
4737 return NULL((void*)0);
4738 }
4739
4740 return qp;
4741}
4742
4743/* Drop all floors in "pwqp", turning each integer division [a/m] into
4744 * a rational division a/m.
4745 */
4746static __isl_give isl_pw_qpolynomial *pwqp_drop_floors(
4747 __isl_take isl_pw_qpolynomial *pwqp)
4748{
4749 int i;
4750
4751 if (!pwqp)
4752 return NULL((void*)0);
4753
4754 if (isl_pw_qpolynomial_is_zero(pwqp))
4755 return pwqp;
4756
4757 pwqp = isl_pw_qpolynomial_cow(pwqp);
4758 if (!pwqp)
4759 return NULL((void*)0);
4760
4761 for (i = 0; i < pwqp->n; ++i) {
4762 pwqp->p[i].qp = qp_drop_floors(pwqp->p[i].qp, 0);
4763 if (!pwqp->p[i].qp)
4764 goto error;
4765 }
4766
4767 return pwqp;
4768error:
4769 isl_pw_qpolynomial_free(pwqp);
4770 return NULL((void*)0);
4771}
4772
4773/* Adjust all the integer divisions in "qp" such that they are at least
4774 * one over the given orthant (identified by "signs"). This ensures
4775 * that they will still be non-negative even after subtracting (m-1)/m.
4776 *
4777 * In particular, f is replaced by f' + v, changing f = [a/m]
4778 * to f' = [(a - m v)/m].
4779 * If the constant term k in a is smaller than m,
4780 * the constant term of v is set to floor(k/m) - 1.
4781 * For any other term, if the coefficient c and the variable x have
4782 * the same sign, then no changes are needed.
4783 * Otherwise, if the variable is positive (and c is negative),
4784 * then the coefficient of x in v is set to floor(c/m).
4785 * If the variable is negative (and c is positive),
4786 * then the coefficient of x in v is set to ceil(c/m).
4787 */
4788static __isl_give isl_qpolynomial *make_divs_pos(__isl_take isl_qpolynomial *qp,
4789 int *signs)
4790{
4791 int i, j;
4792 int total;
4793 isl_vec *v = NULL((void*)0);
4794 struct isl_upoly *s;
4795
4796 qp = isl_qpolynomial_cow(qp);
4797 if (!qp)
4798 return NULL((void*)0);
4799 qp->div = isl_mat_cow(qp->div);
4800 if (!qp->div)
4801 goto error;
4802
4803 total = isl_space_dim(qp->dim, isl_dim_all);
4804 v = isl_vec_alloc(qp->div->ctx, qp->div->n_col - 1);
4805
4806 for (i = 0; i < qp->div->n_row; ++i) {
4807 isl_int *row = qp->div->row[i];
4808 v = isl_vec_clr(v);
4809 if (!v)
4810 goto error;
4811 if (isl_int_lt(row[1], row[0])(isl_sioimath_cmp(*(row[1]), *(row[0])) < 0)) {
4812 isl_int_fdiv_q(v->el[0], row[1], row[0])isl_sioimath_fdiv_q((v->el[0]), *(row[1]), *(row[0]));
4813 isl_int_sub_ui(v->el[0], v->el[0], 1)isl_sioimath_sub_ui((v->el[0]), *(v->el[0]), 1);
4814 isl_int_submul(row[1], row[0], v->el[0])isl_sioimath_submul((row[1]), *(row[0]), *(v->el[0]));
4815 }
4816 for (j = 0; j < total; ++j) {
4817 if (isl_int_sgn(row[2 + j])isl_sioimath_sgn(*(row[2 + j])) * signs[j] >= 0)
4818 continue;
4819 if (signs[j] < 0)
4820 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
]))
;
4821 else
4822 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
]))
;
4823 isl_int_submul(row[2 + j], row[0], v->el[1 + j])isl_sioimath_submul((row[2 + j]), *(row[0]), *(v->el[1 + j
]))
;
4824 }
4825 for (j = 0; j < i; ++j) {
4826 if (isl_int_sgn(row[2 + total + j])isl_sioimath_sgn(*(row[2 + total + j])) >= 0)
4827 continue;
4828 isl_int_fdiv_q(v->el[1 + total + j],isl_sioimath_fdiv_q((v->el[1 + total + j]), *(row[2 + total
+ j]), *(row[0]))
4829 row[2 + total + j], row[0])isl_sioimath_fdiv_q((v->el[1 + total + j]), *(row[2 + total
+ j]), *(row[0]))
;
4830 isl_int_submul(row[2 + total + j],isl_sioimath_submul((row[2 + total + j]), *(row[0]), *(v->
el[1 + total + j]))
4831 row[0], v->el[1 + total + j])isl_sioimath_submul((row[2 + total + j]), *(row[0]), *(v->
el[1 + total + j]))
;
4832 }
4833 for (j = i + 1; j < qp->div->n_row; ++j) {
4834 if (isl_int_is_zero(qp->div->row[j][2 + total + i])(isl_sioimath_sgn(*(qp->div->row[j][2 + total + i])) ==
0)
)
4835 continue;
4836 isl_seq_combine(qp->div->row[j] + 1,
4837 qp->div->ctx->one, qp->div->row[j] + 1,
4838 qp->div->row[j][2 + total + i], v->el, v->size);
4839 }
4840 isl_int_set_si(v->el[1 + total + i], 1)isl_sioimath_set_si((v->el[1 + total + i]), 1);
4841 s = isl_upoly_from_affine(qp->dim->ctx, v->el,
4842 qp->div->ctx->one, v->size);
4843 qp->upoly = isl_upoly_subs(qp->upoly, total + i, 1, &s);
4844 isl_upoly_free(s);
4845 if (!qp->upoly)
4846 goto error;
4847 }
4848
4849 isl_vec_free(v);
4850 return qp;
4851error:
4852 isl_vec_free(v);
4853 isl_qpolynomial_free(qp);
4854 return NULL((void*)0);
4855}
4856
4857struct isl_to_poly_data {
4858 int sign;
4859 isl_pw_qpolynomial *res;
4860 isl_qpolynomial *qp;
4861};
4862
4863/* Appoximate data->qp by a polynomial on the orthant identified by "signs".
4864 * We first make all integer divisions positive and then split the
4865 * quasipolynomials into terms with sign data->sign (the direction
4866 * of the requested approximation) and terms with the opposite sign.
4867 * In the first set of terms, each integer division [a/m] is
4868 * overapproximated by a/m, while in the second it is underapproximated
4869 * by (a-(m-1))/m.
4870 */
4871static isl_stat to_polynomial_on_orthant(__isl_take isl_setisl_map *orthant,
4872 int *signs, void *user)
4873{
4874 struct isl_to_poly_data *data = user;
4875 isl_pw_qpolynomial *t;
4876 isl_qpolynomial *qp, *up, *down;
4877
4878 qp = isl_qpolynomial_copy(data->qp);
4879 qp = make_divs_pos(qp, signs);
4880
4881 up = isl_qpolynomial_terms_of_sign(qp, signs, data->sign);
4882 up = qp_drop_floors(up, 0);
4883 down = isl_qpolynomial_terms_of_sign(qp, signs, -data->sign);
4884 down = qp_drop_floors(down, 1);
4885
4886 isl_qpolynomial_free(qp);
4887 qp = isl_qpolynomial_add(up, down);
4888
4889 t = isl_pw_qpolynomial_alloc(orthant, qp);
4890 data->res = isl_pw_qpolynomial_add_disjoint(data->res, t);
4891
4892 return isl_stat_ok;
4893}
4894
4895/* Approximate each quasipolynomial by a polynomial. If "sign" is positive,
4896 * the polynomial will be an overapproximation. If "sign" is negative,
4897 * it will be an underapproximation. If "sign" is zero, the approximation
4898 * will lie somewhere in between.
4899 *
4900 * In particular, is sign == 0, we simply drop the floors, turning
4901 * the integer divisions into rational divisions.
4902 * Otherwise, we split the domains into orthants, make all integer divisions
4903 * positive and then approximate each [a/m] by either a/m or (a-(m-1))/m,
4904 * depending on the requested sign and the sign of the term in which
4905 * the integer division appears.
4906 */
4907__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_to_polynomial(
4908 __isl_take isl_pw_qpolynomial *pwqp, int sign)
4909{
4910 int i;
4911 struct isl_to_poly_data data;
4912
4913 if (sign == 0)
4914 return pwqp_drop_floors(pwqp);
4915
4916 if (!pwqp)
4917 return NULL((void*)0);
4918
4919 data.sign = sign;
4920 data.res = isl_pw_qpolynomial_zero(isl_pw_qpolynomial_get_space(pwqp));
4921
4922 for (i = 0; i < pwqp->n; ++i) {
4923 if (pwqp->p[i].qp->div->n_row == 0) {
4924 isl_pw_qpolynomial *t;
4925 t = isl_pw_qpolynomial_alloc(
4926 isl_set_copy(pwqp->p[i].set),
4927 isl_qpolynomial_copy(pwqp->p[i].qp));
4928 data.res = isl_pw_qpolynomial_add_disjoint(data.res, t);
4929 continue;
4930 }
4931 data.qp = pwqp->p[i].qp;
4932 if (isl_set_foreach_orthant(pwqp->p[i].set,
4933 &to_polynomial_on_orthant, &data) < 0)
4934 goto error;
4935 }
4936
4937 isl_pw_qpolynomial_free(pwqp);
4938
4939 return data.res;
4940error:
4941 isl_pw_qpolynomial_free(pwqp);
4942 isl_pw_qpolynomial_free(data.res);
4943 return NULL((void*)0);
4944}
4945
4946static __isl_give isl_pw_qpolynomial *poly_entry(
4947 __isl_take isl_pw_qpolynomial *pwqp, void *user)
4948{
4949 int *sign = user;
4950
4951 return isl_pw_qpolynomial_to_polynomial(pwqp, *sign);
4952}
4953
4954__isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_to_polynomial(
4955 __isl_take isl_union_pw_qpolynomial *upwqp, int sign)
4956{
4957 return isl_union_pw_qpolynomial_transform_inplace(upwqp,
4958 &poly_entry, &sign);
4959}
4960
4961__isl_give isl_basic_map *isl_basic_map_from_qpolynomial(
4962 __isl_take isl_qpolynomial *qp)
4963{
4964 int i, k;
4965 isl_space *dim;
4966 isl_vec *aff = NULL((void*)0);
4967 isl_basic_map *bmap = NULL((void*)0);
4968 unsigned pos;
4969 unsigned n_div;
4970
4971 if (!qp)
4972 return NULL((void*)0);
4973 if (!isl_upoly_is_affine(qp->upoly))
4974 isl_die(qp->dim->ctx, isl_error_invalid,do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "input quasi-polynomial not affine"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 4975); goto error; } while (0)
4975 "input quasi-polynomial not affine", goto error)do { isl_handle_error(qp->dim->ctx, isl_error_invalid, "input quasi-polynomial not affine"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_polynomial.c"
, 4975); goto error; } while (0)
;
4976 aff = isl_qpolynomial_extract_affine(qp);
4977 if (!aff)
4978 goto error;
4979 dim = isl_qpolynomial_get_space(qp);
4980 pos = 1 + isl_space_offset(dim, isl_dim_out);
4981 n_div = qp->div->n_row;
4982 bmap = isl_basic_map_alloc_space(dim, n_div, 1, 2 * n_div);
4983
4984 for (i = 0; i < n_div; ++i) {
4985 k = isl_basic_map_alloc_div(bmap);
4986 if (k < 0)
4987 goto error;
4988 isl_seq_cpy(bmap->div[k], qp->div->row[i], qp->div->n_col);
4989 isl_int_set_si(bmap->div[k][qp->div->n_col], 0)isl_sioimath_set_si((bmap->div[k][qp->div->n_col]), 0
)
;
4990 if (isl_basic_map_add_div_constraints(bmap, k) < 0)
4991 goto error;
4992 }
4993 k = isl_basic_map_alloc_equality(bmap);
4994 if (k < 0)
4995 goto error;
4996 isl_int_neg(bmap->eq[k][pos], aff->el[0])isl_sioimath_neg((bmap->eq[k][pos]), *(aff->el[0]));
4997 isl_seq_cpy(bmap->eq[k], aff->el + 1, pos);
4998 isl_seq_cpy(bmap->eq[k] + pos + 1, aff->el + 1 + pos, n_div);
4999
5000 isl_vec_free(aff);
5001 isl_qpolynomial_free(qp);
5002 bmap = isl_basic_map_finalize(bmap);
5003 return bmap;
5004error:
5005 isl_vec_free(aff);
5006 isl_qpolynomial_free(qp);
5007 isl_basic_map_free(bmap);
5008 return NULL((void*)0);
5009}