Bug Summary

File:tools/polly/lib/External/isl/isl_polynomial.c
Warning:line 2141, column 28
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)
19
Assuming 'up' is non-null
20
Taking false branch
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)
27
Taking false branch
626 return;
627
628 if (--up->ref > 0)
28
Assuming the condition is false
29
Taking false branch
629 return;
630
631 if (up->var < 0)
30
Assuming the condition is true
31
Taking true branch
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);
32
Memory is released
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;
25
Control jumps to line 1096
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);
26
Calling 'isl_upoly_free'
33
Returning; memory was released via 1st parameter
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)
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)
1207 return NULL((void*)0);
1208
1209 if (--qp->ref > 0)
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);
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)
1694 goto error;
1695
1696 if (qp1->div->n_row < qp2->div->n_row)
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);
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)
13
Taking false branch
2118 return NULL((void*)0);
2119
2120 if (isl_upoly_is_cst(up))
14
Taking false branch
2121 return up;
2122
2123 if (up->var < first)
15
Taking false branch
2124 return up;
2125
2126 rec = isl_upoly_as_rec(up);
2127 if (!rec)
16
Taking false branch
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)
17
Taking false branch
2133 base = isl_upoly_var_pow(up->ctx, up->var, 1);
2134 else
2135 base = isl_upoly_copy(subs[up->var - first]);
18
Calling 'isl_upoly_copy'
21
Returning from 'isl_upoly_copy'
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) {
22
Assuming 'i' is >= 0
23
Loop condition is true. Entering loop body
35
Assuming 'i' is >= 0
36
Loop condition is true. Entering loop body
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));
24
Calling 'isl_upoly_mul'
34
Returning; memory was released via 2nd parameter
37
Use of memory after it is freed
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)
10
Taking false branch
2213 goto error;
2214
2215 qp = isl_qpolynomial_cow(qp);
2216 if (!qp)
11
Taking false branch
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);
12
Calling 'isl_upoly_subs'
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)
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)) {
3007 isl_pw_qpolynomial_free(pwqp2);
3008 return pwqp1;
3009 }
3010
3011 if (isl_pw_qpolynomial_is_zero(pwqp2)) {
3012 isl_pw_qpolynomial_free(pwqp1);
3013 return pwqp2;
3014 }
3015
3016 if (isl_pw_qpolynomial_is_one(pwqp1)) {
3017 isl_pw_qpolynomial_free(pwqp1);
3018 return pwqp2;
3019 }
3020
3021 if (isl_pw_qpolynomial_is_one(pwqp2)) {
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) {
3030 for (j = 0; j < pwqp2->n; ++j) {
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)) {
3036 isl_set_free(common);
3037 continue;
3038 }
3039
3040 prod = isl_qpolynomial_mul(
3041 isl_qpolynomial_copy(pwqp1->p[i].qp),
3042 isl_qpolynomial_copy(pwqp2->p[j].qp));
3043
3044 res = isl_pw_qpolynomial_add_piece(res, common, prod);
3045 }
3046 }
3047
3048 isl_pw_qpolynomial_free(pwqp1);
3049 isl_pw_qpolynomial_free(pwqp2);
3050
3051 return res;
3052error:
3053 isl_pw_qpolynomial_free(pwqp1);
3054 isl_pw_qpolynomial_free(pwqp2);
3055 return NULL((void*)0);
3056}
3057
3058__isl_give isl_val *isl_upoly_eval(__isl_take struct isl_upoly *up,
3059 __isl_take isl_vec *vec)
3060{
3061 int i;
3062 struct isl_upoly_rec *rec;
3063 isl_val *res;
3064 isl_val *base;
3065
3066 if (isl_upoly_is_cst(up)) {
3067 isl_vec_free(vec);
3068 res = isl_upoly_get_constant_val(up);
3069 isl_upoly_free(up);
3070 return res;
3071 }
3072
3073 rec = isl_upoly_as_rec(up);
3074 if (!rec)
3075 goto error;
3076
3077 isl_assert(up->ctx, rec->n >= 1, goto error)do { if (rec->n >= 1) break; do { isl_handle_error(up->
ctx, isl_error_unknown, "Assertion \"" "rec->n >= 1" "\" failed"
, "/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)
2
Assuming 'qp' is non-null
3
Taking false branch
4718 return NULL((void*)0);
4719 if (qp->div->n_row == 0)
4
Assuming the condition is false
5
Taking false branch
4720 return qp;
4721
4722 qp = isl_qpolynomial_cow(qp);
4723 if (!qp)
6
Taking false branch
4724 return NULL((void*)0);
4725
4726 for (i = qp->div->n_row - 1; i >= 0; --i) {
7
Loop condition is true. Entering loop body
4727 if (down) {
8
Taking true branch
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);
9
Calling 'substitute_div'
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);
1
Calling 'qp_drop_floors'
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}