2 * Copyright 2010 INRIA Saclay
4 * Use of this software is governed by the GNU LGPLv2.1 license
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11 #include <isl_union_map_private.h>
12 #include <isl_polynomial_private.h>
13 #include <isl_point_private.h>
14 #include <isl_dim_private.h>
15 #include <isl_map_private.h>
19 static __isl_give isl_qpolynomial_fold
*qpolynomial_fold_alloc(
20 enum isl_fold type
, __isl_take isl_dim
*dim
, int n
)
22 isl_qpolynomial_fold
*fold
;
27 isl_assert(dim
->ctx
, n
>= 0, goto error
);
28 fold
= isl_calloc(dim
->ctx
, struct isl_qpolynomial_fold
,
29 sizeof(struct isl_qpolynomial_fold
) +
30 (n
- 1) * sizeof(struct isl_qpolynomial
*));
46 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_reset_dim(
47 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_dim
*dim
)
52 isl_dim_free(fold
->dim
);
57 isl_qpolynomial_fold_free(fold
);
62 int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold
*fold
,
63 enum isl_dim_type type
, unsigned first
, unsigned n
)
69 if (fold
->n
== 0 || n
== 0)
72 for (i
= 0; i
< fold
->n
; ++i
) {
73 int involves
= isl_qpolynomial_involves_dims(fold
->qp
[i
],
75 if (involves
< 0 || involves
)
81 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_drop_dims(
82 __isl_take isl_qpolynomial_fold
*fold
,
83 enum isl_dim_type type
, unsigned first
, unsigned n
)
92 fold
= isl_qpolynomial_fold_cow(fold
);
95 fold
->dim
= isl_dim_drop(fold
->dim
, type
, first
, n
);
99 for (i
= 0; i
< fold
->n
; ++i
) {
100 fold
->qp
[i
] = isl_qpolynomial_drop_dims(fold
->qp
[i
],
108 isl_qpolynomial_fold_free(fold
);
112 static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial
*qp
)
114 struct isl_upoly_cst
*cst
;
116 cst
= isl_upoly_as_cst(qp
->upoly
);
120 return isl_int_sgn(cst
->n
) < 0 ? -1 : 1;
123 static int isl_qpolynomial_aff_sign(__isl_keep isl_set
*set
,
124 __isl_keep isl_qpolynomial
*qp
)
126 enum isl_lp_result res
;
131 aff
= isl_qpolynomial_extract_affine(qp
);
137 res
= isl_set_solve_lp(set
, 0, aff
->el
+ 1, aff
->el
[0],
139 if (res
== isl_lp_error
)
141 if (res
== isl_lp_empty
||
142 (res
== isl_lp_ok
&& !isl_int_is_neg(opt
))) {
147 res
= isl_set_solve_lp(set
, 1, aff
->el
+ 1, aff
->el
[0],
149 if (res
== isl_lp_ok
&& !isl_int_is_pos(opt
))
158 /* Determine, if possible, the sign of the quasipolynomial "qp" on
161 * If qp is a constant, then the problem is trivial.
162 * If qp is linear, then we check if the minimum of the corresponding
163 * affine constraint is non-negative or if the maximum is non-positive.
165 * Otherwise, we check if the outermost variable "v" has a lower bound "l"
166 * in "set". If so, we write qp(v,v') as
168 * q(v,v') * (v - l) + r(v')
170 * if q(v,v') and r(v') have the same known sign, then the original
171 * quasipolynomial has the same sign as well.
178 static int isl_qpolynomial_sign(__isl_keep isl_set
*set
,
179 __isl_keep isl_qpolynomial
*qp
)
184 struct isl_upoly_rec
*rec
;
187 enum isl_lp_result res
;
190 is
= isl_qpolynomial_is_cst(qp
, NULL
, NULL
);
194 return isl_qpolynomial_cst_sign(qp
);
196 is
= isl_qpolynomial_is_affine(qp
);
200 return isl_qpolynomial_aff_sign(set
, qp
);
202 if (qp
->div
->n_row
> 0)
205 rec
= isl_upoly_as_rec(qp
->upoly
);
209 d
= isl_dim_total(qp
->dim
);
210 v
= isl_vec_alloc(set
->ctx
, 2 + d
);
214 isl_seq_clr(v
->el
+ 1, 1 + d
);
215 isl_int_set_si(v
->el
[0], 1);
216 isl_int_set_si(v
->el
[2 + qp
->upoly
->var
], 1);
220 res
= isl_set_solve_lp(set
, 0, v
->el
+ 1, v
->el
[0], &l
, NULL
, NULL
);
221 if (res
== isl_lp_ok
) {
222 isl_qpolynomial
*min
;
223 isl_qpolynomial
*base
;
224 isl_qpolynomial
*r
, *q
;
227 min
= isl_qpolynomial_cst(isl_dim_copy(qp
->dim
), l
);
228 base
= isl_qpolynomial_pow(isl_dim_copy(qp
->dim
),
231 r
= isl_qpolynomial_alloc(isl_dim_copy(qp
->dim
), 0,
232 isl_upoly_copy(rec
->p
[rec
->n
- 1]));
233 q
= isl_qpolynomial_copy(r
);
235 for (i
= rec
->n
- 2; i
>= 0; --i
) {
236 r
= isl_qpolynomial_mul(r
, isl_qpolynomial_copy(min
));
237 t
= isl_qpolynomial_alloc(isl_dim_copy(qp
->dim
), 0,
238 isl_upoly_copy(rec
->p
[i
]));
239 r
= isl_qpolynomial_add(r
, t
);
242 q
= isl_qpolynomial_mul(q
, isl_qpolynomial_copy(base
));
243 q
= isl_qpolynomial_add(q
, isl_qpolynomial_copy(r
));
246 if (isl_qpolynomial_is_zero(q
))
247 sgn
= isl_qpolynomial_sign(set
, r
);
248 else if (isl_qpolynomial_is_zero(r
))
249 sgn
= isl_qpolynomial_sign(set
, q
);
252 sgn_r
= isl_qpolynomial_sign(set
, r
);
253 sgn_q
= isl_qpolynomial_sign(set
, q
);
258 isl_qpolynomial_free(min
);
259 isl_qpolynomial_free(base
);
260 isl_qpolynomial_free(q
);
261 isl_qpolynomial_free(r
);
271 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_fold_on_domain(
272 __isl_keep isl_set
*set
,
273 __isl_take isl_qpolynomial_fold
*fold1
,
274 __isl_take isl_qpolynomial_fold
*fold2
)
278 struct isl_qpolynomial_fold
*res
= NULL
;
281 if (!fold1
|| !fold2
)
284 isl_assert(fold1
->dim
->ctx
, fold1
->type
== fold2
->type
, goto error
);
285 isl_assert(fold1
->dim
->ctx
, isl_dim_equal(fold1
->dim
, fold2
->dim
),
288 better
= fold1
->type
== isl_fold_max
? -1 : 1;
290 if (isl_qpolynomial_fold_is_empty(fold1
)) {
291 isl_qpolynomial_fold_free(fold1
);
295 if (isl_qpolynomial_fold_is_empty(fold2
)) {
296 isl_qpolynomial_fold_free(fold2
);
300 res
= qpolynomial_fold_alloc(fold1
->type
, isl_dim_copy(fold1
->dim
),
301 fold1
->n
+ fold2
->n
);
305 for (i
= 0; i
< fold1
->n
; ++i
) {
306 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold1
->qp
[i
]);
307 if (!res
->qp
[res
->n
])
313 for (i
= 0; i
< fold2
->n
; ++i
) {
314 for (j
= n1
- 1; j
>= 0; --j
) {
317 d
= isl_qpolynomial_sub(
318 isl_qpolynomial_copy(res
->qp
[j
]),
319 isl_qpolynomial_copy(fold2
->qp
[i
]));
320 sgn
= isl_qpolynomial_sign(set
, d
);
321 isl_qpolynomial_free(d
);
326 isl_qpolynomial_free(res
->qp
[j
]);
328 res
->qp
[j
] = res
->qp
[n1
- 1];
330 if (n1
!= res
->n
- 1)
331 res
->qp
[n1
] = res
->qp
[res
->n
- 1];
336 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold2
->qp
[i
]);
337 if (!res
->qp
[res
->n
])
342 isl_qpolynomial_fold_free(fold1
);
343 isl_qpolynomial_fold_free(fold2
);
347 isl_qpolynomial_fold_free(res
);
348 isl_qpolynomial_fold_free(fold1
);
349 isl_qpolynomial_fold_free(fold2
);
354 #define PW isl_pw_qpolynomial_fold
356 #define EL isl_qpolynomial_fold
358 #define IS_ZERO is_empty
362 #define ADD(d,e1,e2) isl_qpolynomial_fold_fold_on_domain(d,e1,e2)
364 #include <isl_pw_templ.c>
367 #define UNION isl_union_pw_qpolynomial_fold
369 #define PART isl_pw_qpolynomial_fold
371 #define PARTS pw_qpolynomial_fold
373 #include <isl_union_templ.c>
375 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_empty(enum isl_fold type
,
376 __isl_take isl_dim
*dim
)
378 return qpolynomial_fold_alloc(type
, dim
, 0);
381 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_alloc(
382 enum isl_fold type
, __isl_take isl_qpolynomial
*qp
)
384 isl_qpolynomial_fold
*fold
;
389 fold
= qpolynomial_fold_alloc(type
, isl_dim_copy(qp
->dim
), 1);
398 isl_qpolynomial_fold_free(fold
);
399 isl_qpolynomial_free(qp
);
403 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_copy(
404 __isl_keep isl_qpolynomial_fold
*fold
)
413 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_dup(
414 __isl_keep isl_qpolynomial_fold
*fold
)
417 isl_qpolynomial_fold
*dup
;
421 dup
= qpolynomial_fold_alloc(fold
->type
,
422 isl_dim_copy(fold
->dim
), fold
->n
);
427 for (i
= 0; i
< fold
->n
; ++i
) {
428 dup
->qp
[i
] = isl_qpolynomial_copy(fold
->qp
[i
]);
435 isl_qpolynomial_fold_free(dup
);
439 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_cow(
440 __isl_take isl_qpolynomial_fold
*fold
)
448 return isl_qpolynomial_fold_dup(fold
);
451 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold
*fold
)
460 for (i
= 0; i
< fold
->n
; ++i
)
461 isl_qpolynomial_free(fold
->qp
[i
]);
462 isl_dim_free(fold
->dim
);
466 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold
*fold
)
474 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_fold(
475 __isl_take isl_qpolynomial_fold
*fold1
,
476 __isl_take isl_qpolynomial_fold
*fold2
)
479 struct isl_qpolynomial_fold
*res
= NULL
;
481 if (!fold1
|| !fold2
)
484 isl_assert(fold1
->dim
->ctx
, fold1
->type
== fold2
->type
, goto error
);
485 isl_assert(fold1
->dim
->ctx
, isl_dim_equal(fold1
->dim
, fold2
->dim
),
488 if (isl_qpolynomial_fold_is_empty(fold1
)) {
489 isl_qpolynomial_fold_free(fold1
);
493 if (isl_qpolynomial_fold_is_empty(fold2
)) {
494 isl_qpolynomial_fold_free(fold2
);
498 res
= qpolynomial_fold_alloc(fold1
->type
, isl_dim_copy(fold1
->dim
),
499 fold1
->n
+ fold2
->n
);
503 for (i
= 0; i
< fold1
->n
; ++i
) {
504 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold1
->qp
[i
]);
505 if (!res
->qp
[res
->n
])
510 for (i
= 0; i
< fold2
->n
; ++i
) {
511 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold2
->qp
[i
]);
512 if (!res
->qp
[res
->n
])
517 isl_qpolynomial_fold_free(fold1
);
518 isl_qpolynomial_fold_free(fold2
);
522 isl_qpolynomial_fold_free(res
);
523 isl_qpolynomial_fold_free(fold1
);
524 isl_qpolynomial_fold_free(fold2
);
528 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_from_pw_qpolynomial(
529 enum isl_fold type
, __isl_take isl_pw_qpolynomial
*pwqp
)
532 isl_pw_qpolynomial_fold
*pwf
;
537 pwf
= isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pwqp
->dim
), pwqp
->n
);
539 for (i
= 0; i
< pwqp
->n
; ++i
)
540 pwf
= isl_pw_qpolynomial_fold_add_piece(pwf
,
541 isl_set_copy(pwqp
->p
[i
].set
),
542 isl_qpolynomial_fold_alloc(type
,
543 isl_qpolynomial_copy(pwqp
->p
[i
].qp
)));
545 isl_pw_qpolynomial_free(pwqp
);
550 int isl_qpolynomial_fold_is_equal(__isl_keep isl_qpolynomial_fold
*fold1
,
551 __isl_keep isl_qpolynomial_fold
*fold2
)
555 if (!fold1
|| !fold2
)
558 if (fold1
->n
!= fold2
->n
)
561 /* We probably want to sort the qps first... */
562 for (i
= 0; i
< fold1
->n
; ++i
) {
563 int eq
= isl_qpolynomial_is_equal(fold1
->qp
[i
], fold2
->qp
[i
]);
571 __isl_give isl_qpolynomial
*isl_qpolynomial_fold_eval(
572 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_point
*pnt
)
578 isl_assert(pnt
->dim
->ctx
, isl_dim_equal(pnt
->dim
, fold
->dim
), goto error
);
579 isl_assert(pnt
->dim
->ctx
,
580 fold
->type
== isl_fold_max
|| fold
->type
== isl_fold_min
,
584 qp
= isl_qpolynomial_zero(isl_dim_copy(fold
->dim
));
587 qp
= isl_qpolynomial_eval(isl_qpolynomial_copy(fold
->qp
[0]),
588 isl_point_copy(pnt
));
589 for (i
= 1; i
< fold
->n
; ++i
) {
590 isl_qpolynomial
*qp_i
;
591 qp_i
= isl_qpolynomial_eval(
592 isl_qpolynomial_copy(fold
->qp
[i
]),
593 isl_point_copy(pnt
));
594 if (fold
->type
== isl_fold_max
)
595 qp
= isl_qpolynomial_max_cst(qp
, qp_i
);
597 qp
= isl_qpolynomial_min_cst(qp
, qp_i
);
600 isl_qpolynomial_fold_free(fold
);
605 isl_qpolynomial_fold_free(fold
);
610 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold
*pwf
)
615 for (i
= 0; i
< pwf
->n
; ++i
)
616 n
+= pwf
->p
[i
].fold
->n
;
621 __isl_give isl_qpolynomial
*isl_qpolynomial_fold_opt_on_domain(
622 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_set
*set
, int max
)
625 isl_qpolynomial
*opt
;
631 isl_dim
*dim
= isl_dim_copy(fold
->dim
);
633 isl_qpolynomial_fold_free(fold
);
634 return isl_qpolynomial_zero(dim
);
637 opt
= isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold
->qp
[0]),
638 isl_set_copy(set
), max
);
639 for (i
= 1; i
< fold
->n
; ++i
) {
640 isl_qpolynomial
*opt_i
;
641 opt_i
= isl_qpolynomial_opt_on_domain(
642 isl_qpolynomial_copy(fold
->qp
[i
]),
643 isl_set_copy(set
), max
);
645 opt
= isl_qpolynomial_max_cst(opt
, opt_i
);
647 opt
= isl_qpolynomial_min_cst(opt
, opt_i
);
651 isl_qpolynomial_fold_free(fold
);
656 isl_qpolynomial_fold_free(fold
);
660 /* Check whether for each quasi-polynomial in "fold2" there is
661 * a quasi-polynomial in "fold1" that dominates it on "set".
663 static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set
*set
,
664 __isl_keep isl_qpolynomial_fold
*fold1
,
665 __isl_keep isl_qpolynomial_fold
*fold2
)
670 if (!set
|| !fold1
|| !fold2
)
673 covers
= fold1
->type
== isl_fold_max
? 1 : -1;
675 for (i
= 0; i
< fold2
->n
; ++i
) {
676 for (j
= 0; j
< fold1
->n
; ++j
) {
680 d
= isl_qpolynomial_sub(
681 isl_qpolynomial_copy(fold1
->qp
[j
]),
682 isl_qpolynomial_copy(fold2
->qp
[i
]));
683 sgn
= isl_qpolynomial_sign(set
, d
);
684 isl_qpolynomial_free(d
);
695 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
696 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
699 int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold
*pwf1
,
700 __isl_keep isl_pw_qpolynomial_fold
*pwf2
)
703 isl_set
*dom1
, *dom2
;
714 dom1
= isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1
));
715 dom2
= isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2
));
716 is_subset
= isl_set_is_subset(dom2
, dom1
);
720 if (is_subset
< 0 || !is_subset
)
723 for (i
= 0; i
< pwf2
->n
; ++i
) {
724 for (j
= 0; j
< pwf1
->n
; ++j
) {
729 common
= isl_set_intersect(isl_set_copy(pwf1
->p
[j
].set
),
730 isl_set_copy(pwf2
->p
[i
].set
));
731 is_empty
= isl_set_is_empty(common
);
732 if (is_empty
< 0 || is_empty
) {
733 isl_set_free(common
);
738 covers
= qpolynomial_fold_covers_on_domain(common
,
739 pwf1
->p
[j
].fold
, pwf2
->p
[i
].fold
);
740 isl_set_free(common
);
741 if (covers
< 0 || !covers
)
749 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_morph(
750 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_morph
*morph
)
758 ctx
= fold
->dim
->ctx
;
759 isl_assert(ctx
, isl_dim_equal(fold
->dim
, morph
->dom
->dim
), goto error
);
761 fold
= isl_qpolynomial_fold_cow(fold
);
765 isl_dim_free(fold
->dim
);
766 fold
->dim
= isl_dim_copy(morph
->ran
->dim
);
770 for (i
= 0; i
< fold
->n
; ++i
) {
771 fold
->qp
[i
] = isl_qpolynomial_morph(fold
->qp
[i
],
772 isl_morph_copy(morph
));
777 isl_morph_free(morph
);
781 isl_qpolynomial_fold_free(fold
);
782 isl_morph_free(morph
);
786 enum isl_fold
isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold
*fold
)
789 return isl_fold_list
;
793 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_lift(
794 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_dim
*dim
)
802 if (isl_dim_equal(fold
->dim
, dim
)) {
807 fold
= isl_qpolynomial_fold_cow(fold
);
811 isl_dim_free(fold
->dim
);
812 fold
->dim
= isl_dim_copy(dim
);
816 for (i
= 0; i
< fold
->n
; ++i
) {
817 fold
->qp
[i
] = isl_qpolynomial_lift(fold
->qp
[i
],
827 isl_qpolynomial_fold_free(fold
);
832 int isl_qpolynomial_fold_foreach_qpolynomial(
833 __isl_keep isl_qpolynomial_fold
*fold
,
834 int (*fn
)(__isl_take isl_qpolynomial
*qp
, void *user
), void *user
)
841 for (i
= 0; i
< fold
->n
; ++i
)
842 if (fn(isl_qpolynomial_copy(fold
->qp
[i
]), user
) < 0)
848 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_move_dims(
849 __isl_take isl_qpolynomial_fold
*fold
,
850 enum isl_dim_type dst_type
, unsigned dst_pos
,
851 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
858 fold
= isl_qpolynomial_fold_cow(fold
);
862 fold
->dim
= isl_dim_move(fold
->dim
, dst_type
, dst_pos
,
863 src_type
, src_pos
, n
);
867 for (i
= 0; i
< fold
->n
; ++i
) {
868 fold
->qp
[i
] = isl_qpolynomial_move_dims(fold
->qp
[i
],
869 dst_type
, dst_pos
, src_type
, src_pos
, n
);
876 isl_qpolynomial_fold_free(fold
);