Bug Summary

File:tools/polly/lib/External/isl/isl_polynomial.c
Warning:line 3043, column 5
Use of memory after it is freed

Annotated Source Code

1/*
2 * Copyright 2010 INRIA Saclay
3 *
4 * Use of this software is governed by the MIT license
5 *
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
8 * 91893 Orsay, France
9 */
10
11#include <stdlib.h>
12#define ISL_DIM_H
13#include <isl_ctx_private.h>
14#include <isl_map_private.h>
15#include <isl_factorization.h>
16#include <isl_lp_private.h>
17#include <isl_seq.h>
18#include <isl_union_map_private.h>
19#include <isl_constraint_private.h>
20#include <isl_polynomial_private.h>
21#include <isl_point_private.h>
22#include <isl_space_private.h>
23#include <isl_mat_private.h>
24#include <isl_vec_private.h>
25#include <isl_range.h>
26#include <isl_local.h>
27#include <isl_local_space_private.h>
28#include <isl_aff_private.h>
29#include <isl_val_private.h>
30#include <isl_config.h>
31#include <isl/deprecated/polynomial_int.h>
32
33static unsigned pos(__isl_keep isl_space *dim, enum isl_dim_type type)
34{
35 switch (type) {
36 case isl_dim_param: return 0;
37 case isl_dim_in: return dim->nparam;
38 case isl_dim_out: return dim->nparam + dim->n_in;
39 default: return 0;
40 }
41}
42
43int isl_upoly_is_cst(__isl_keep struct isl_upoly *up)
44{
45 if (!up)
46 return -1;
47
48 return up->var < 0;
49}
50
51__isl_keep struct isl_upoly_cst *isl_upoly_as_cst(__isl_keep struct isl_upoly *up)
52{
53 if (!up)
54 return NULL((void*)0);
55
56 isl_assert(up->ctx, up->var < 0, return NULL)do { if (up->var < 0) break; do { isl_handle_error(up->
ctx, isl_error_unknown, "Assertion \"" "up->var < 0" "\" failed"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~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)
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));
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)
828 return NULL((void*)0);
829
830 if (isl_upoly_is_cst(up))
831 return isl_upoly_cst_add_isl_int(up, v);
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)
15
Assuming 'qp' is non-null
16
Taking false branch
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)
22
Taking false branch
1208 return NULL((void*)0);
1209
1210 if (--qp->ref > 0)
23
Assuming the condition is false
24
Taking false branch
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);
25
Memory is released
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))
1565 return qp;
1566
1567 qp = isl_qpolynomial_cow(qp);
1568 if (!qp)
1569 return NULL((void*)0);
1570
1571 qp->upoly = isl_upoly_add_isl_int(qp->upoly, v);
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)
19
Taking false branch
1695 goto error;
1696
1697 if (qp1->div->n_row < qp2->div->n_row)
20
Taking false branch
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);
21
Calling 'isl_qpolynomial_free'
26
Returning; memory was released via 1st parameter
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)
1
Assuming 'pwqp1' is non-null
2
Assuming 'pwqp2' is non-null
3
Taking false branch
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)) {
4
Taking false branch
3008 isl_pw_qpolynomial_free(pwqp2);
3009 return pwqp1;
3010 }
3011
3012 if (isl_pw_qpolynomial_is_zero(pwqp2)) {
5
Taking false branch
3013 isl_pw_qpolynomial_free(pwqp1);
3014 return pwqp2;
3015 }
3016
3017 if (isl_pw_qpolynomial_is_one(pwqp1)) {
6
Taking false branch
3018 isl_pw_qpolynomial_free(pwqp1);
3019 return pwqp2;
3020 }
3021
3022 if (isl_pw_qpolynomial_is_one(pwqp2)) {
7
Taking false branch
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) {
8
Assuming the condition is true
9
Loop condition is true. Entering loop body
30
Assuming the condition is true
31
Loop condition is true. Entering loop body
3031 for (j = 0; j < pwqp2->n; ++j) {
10
Assuming the condition is true
11
Loop condition is true. Entering loop body
28
Assuming the condition is false
29
Loop condition is false. Execution continues on line 3030
32
Loop condition is true. Entering loop body
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)) {
12
Assuming the condition is false
13
Taking false branch
33
Assuming the condition is false
34
Taking false branch
3037 isl_set_free(common);
3038 continue;
3039 }
3040
3041 prod = isl_qpolynomial_mul(
18
Calling 'isl_qpolynomial_mul'
27
Returning; memory was released via 2nd parameter
3042 isl_qpolynomial_copy(pwqp1->p[i].qp),
3043 isl_qpolynomial_copy(pwqp2->p[j].qp));
14
Calling 'isl_qpolynomial_copy'
17
Returning from 'isl_qpolynomial_copy'
35
Use of memory after it is freed
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}