Bug Summary

File:tools/polly/lib/External/isl/isl_polynomial.c
Warning:line 817, column 2
Dereference of null pointer

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