« back to all changes in this revision
Viewing changes to isl/isl_polynomial.c
- browse files at revision 3
- compare with another revision
- download diff
- download tarball
- view history from revision 3
- Committer: Package Import Robot
- Author(s): Matthias Klose
- Date: 2011-12-15 18:39:17 UTC
- mfrom: (1.1.1)
- Revision ID: package-import@ubuntu.com-20111215183917-uqggmujou8wna9js
Tags: 0.17.0-1
New upstream version.
- files added:
- debian/cloog-isl.install
- isl/interface
- osl
- osl/autoconf
- osl/doc
- osl/doc/images
- osl/include
- osl/include/osl
- osl/include/osl/extensions
- osl/source
- osl/source/extensions
- osl/tests
- test/openscop
- files removed:
- debian/libcloog-isl2.install
- files modified:
- CLOOG_HEAD
added
removed
isl/isl_polynomial.c
9
9
*/
10
10
11
11
#include <stdlib.h>
12
#define ISL_DIM_H
12
13
#include <isl_ctx_private.h>
13
14
#include <isl_map_private.h>
14
15
#include <isl_factorization.h>
18
19
#include <isl_constraint_private.h>
19
20
#include <isl_polynomial_private.h>
20
21
#include <isl_point_private.h>
21
#include <isl_dim_private.h>
22
#include <isl_div_private.h>
22
#include <isl_space_private.h>
23
23
#include <isl_mat_private.h>
24
24
#include <isl_range.h>
25
25
#include <isl_local_space_private.h>
26
26
#include <isl_aff_private.h>
27
27
#include <isl_config.h>
28
28
29
static unsigned pos(__isl_keep isl_dim *dim, enum isl_dim_type type)
29
static unsigned pos(__isl_keep isl_space *dim, enum isl_dim_type type)
30
30
{
31
31
switch (type) {
32
32
case isl_dim_param: return 0;
343
343
return rec;
344
344
}
345
345
346
__isl_give isl_qpolynomial *isl_qpolynomial_reset_dim(
347
__isl_take isl_qpolynomial *qp, __isl_take isl_dim *dim)
346
__isl_give isl_qpolynomial *isl_qpolynomial_reset_domain_space(
347
__isl_take isl_qpolynomial *qp, __isl_take isl_space *dim)
348
348
{
349
349
qp = isl_qpolynomial_cow(qp);
350
350
if (!qp || !dim)
351
351
goto error;
352
352
353
isl_dim_free(qp->dim);
353
isl_space_free(qp->dim);
354
354
qp->dim = dim;
355
355
356
356
return qp;
357
357
error:
358
358
isl_qpolynomial_free(qp);
359
isl_dim_free(dim);
359
isl_space_free(dim);
360
360
return NULL;
361
361
}
362
362
363
/* Reset the space of "qp". This function is called from isl_pw_templ.c
364
* and doesn't know if the space of an element object is represented
365
* directly or through its domain. It therefore passes along both.
366
*/
367
__isl_give isl_qpolynomial *isl_qpolynomial_reset_space_and_domain(
368
__isl_take isl_qpolynomial *qp, __isl_take isl_space *space,
369
__isl_take isl_space *domain)
370
{
371
isl_space_free(space);
372
return isl_qpolynomial_reset_domain_space(qp, domain);
373
}
374
363
375
isl_ctx *isl_qpolynomial_get_ctx(__isl_keep isl_qpolynomial *qp)
364
376
{
365
377
return qp ? qp->dim->ctx : NULL;
366
378
}
367
379
368
__isl_give isl_dim *isl_qpolynomial_get_dim(__isl_keep isl_qpolynomial *qp)
369
{
370
return qp ? isl_dim_copy(qp->dim) : NULL;
371
}
372
380
__isl_give isl_space *isl_qpolynomial_get_domain_space(
381
__isl_keep isl_qpolynomial *qp)
382
{
383
return qp ? isl_space_copy(qp->dim) : NULL;
384
}
385
386
__isl_give isl_space *isl_qpolynomial_get_space(__isl_keep isl_qpolynomial *qp)
387
{
388
isl_space *space;
389
if (!qp)
390
return NULL;
391
space = isl_space_copy(qp->dim);
392
space = isl_space_from_domain(space);
393
space = isl_space_add_dims(space, isl_dim_out, 1);
394
return space;
395
}
396
397
/* Externally, an isl_qpolynomial has a map space, but internally, the
398
* ls field corresponds to the domain of that space.
399
*/
373
400
unsigned isl_qpolynomial_dim(__isl_keep isl_qpolynomial *qp,
374
401
enum isl_dim_type type)
375
402
{
376
return qp ? isl_dim_size(qp->dim, type) : 0;
403
if (!qp)
404
return 0;
405
if (type == isl_dim_out)
406
return 1;
407
if (type == isl_dim_in)
408
type = isl_dim_set;
409
return isl_space_dim(qp->dim, type);
377
410
}
378
411
379
412
int isl_qpolynomial_is_zero(__isl_keep isl_qpolynomial *qp)
945
978
return res;
946
979
}
947
980
948
__isl_give isl_qpolynomial *isl_qpolynomial_alloc(__isl_take isl_dim *dim,
981
__isl_give isl_qpolynomial *isl_qpolynomial_alloc(__isl_take isl_space *dim,
949
982
unsigned n_div, __isl_take struct isl_upoly *up)
950
983
{
951
984
struct isl_qpolynomial *qp = NULL;
954
987
if (!dim || !up)
955
988
goto error;
956
989
957
total = isl_dim_total(dim);
990
if (!isl_space_is_set(dim))
991
isl_die(isl_space_get_ctx(dim), isl_error_invalid,
992
"domain of polynomial should be a set", goto error);
993
994
total = isl_space_dim(dim, isl_dim_all);
958
995
959
996
qp = isl_calloc_type(dim->ctx, struct isl_qpolynomial);
960
997
if (!qp)
970
1007
971
1008
return qp;
972
1009
error:
973
isl_dim_free(dim);
1010
isl_space_free(dim);
974
1011
isl_upoly_free(up);
975
1012
isl_qpolynomial_free(qp);
976
1013
return NULL;
992
1029
if (!qp)
993
1030
return NULL;
994
1031
995
dup = isl_qpolynomial_alloc(isl_dim_copy(qp->dim), qp->div->n_row,
1032
dup = isl_qpolynomial_alloc(isl_space_copy(qp->dim), qp->div->n_row,
996
1033
isl_upoly_copy(qp->upoly));
997
1034
if (!dup)
998
1035
return NULL;
1018
1055
return isl_qpolynomial_dup(qp);
1019
1056
}
1020
1057
1021
void isl_qpolynomial_free(__isl_take isl_qpolynomial *qp)
1058
void *isl_qpolynomial_free(__isl_take isl_qpolynomial *qp)
1022
1059
{
1023
1060
if (!qp)
1024
return;
1061
return NULL;
1025
1062
1026
1063
if (--qp->ref > 0)
1027
return;
1064
return NULL;
1028
1065
1029
isl_dim_free(qp->dim);
1066
isl_space_free(qp->dim);
1030
1067
isl_mat_free(qp->div);
1031
1068
isl_upoly_free(qp->upoly);
1032
1069
1033
1070
free(qp);
1071
return NULL;
1034
1072
}
1035
1073
1036
1074
__isl_give struct isl_upoly *isl_upoly_var_pow(isl_ctx *ctx, int pos, int power)
1161
1199
if (qp->div->n_row <= 1)
1162
1200
return qp;
1163
1201
1164
div_pos = isl_dim_total(qp->dim);
1202
div_pos = isl_space_dim(qp->dim, isl_dim_all);
1165
1203
1166
1204
array = isl_alloc_array(qp->div->ctx, struct isl_div_sort_info,
1167
1205
qp->div->n_row);
1330
1368
if (qp1->div->n_row < qp2->div->n_row)
1331
1369
return isl_qpolynomial_add(qp2, qp1);
1332
1370
1333
isl_assert(qp1->dim->ctx, isl_dim_equal(qp1->dim, qp2->dim), goto error);
1371
isl_assert(qp1->dim->ctx, isl_space_is_equal(qp1->dim, qp2->dim), goto error);
1334
1372
if (!compatible_divs(qp1->div, qp2->div))
1335
1373
return with_merged_divs(isl_qpolynomial_add, qp1, qp2);
1336
1374
1400
1438
1401
1439
if (qp && isl_int_is_zero(v)) {
1402
1440
isl_qpolynomial *zero;
1403
zero = isl_qpolynomial_zero(isl_dim_copy(qp->dim));
1441
zero = isl_qpolynomial_zero_on_domain(isl_space_copy(qp->dim));
1404
1442
isl_qpolynomial_free(qp);
1405
1443
return zero;
1406
1444
}
1436
1474
if (qp1->div->n_row < qp2->div->n_row)
1437
1475
return isl_qpolynomial_mul(qp2, qp1);
1438
1476
1439
isl_assert(qp1->dim->ctx, isl_dim_equal(qp1->dim, qp2->dim), goto error);
1477
isl_assert(qp1->dim->ctx, isl_space_is_equal(qp1->dim, qp2->dim), goto error);
1440
1478
if (!compatible_divs(qp1->div, qp2->div))
1441
1479
return with_merged_divs(isl_qpolynomial_mul, qp1, qp2);
1442
1480
1471
1509
return NULL;
1472
1510
}
1473
1511
1474
__isl_give isl_qpolynomial *isl_qpolynomial_zero(__isl_take isl_dim *dim)
1512
__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_pow(
1513
__isl_take isl_pw_qpolynomial *pwqp, unsigned power)
1514
{
1515
int i;
1516
1517
if (power == 1)
1518
return pwqp;
1519
1520
pwqp = isl_pw_qpolynomial_cow(pwqp);
1521
if (!pwqp)
1522
return NULL;
1523
1524
for (i = 0; i < pwqp->n; ++i) {
1525
pwqp->p[i].qp = isl_qpolynomial_pow(pwqp->p[i].qp, power);
1526
if (!pwqp->p[i].qp)
1527
return isl_pw_qpolynomial_free(pwqp);
1528
}
1529
1530
return pwqp;
1531
}
1532
1533
__isl_give isl_qpolynomial *isl_qpolynomial_zero_on_domain(
1534
__isl_take isl_space *dim)
1475
1535
{
1476
1536
if (!dim)
1477
1537
return NULL;
1478
1538
return isl_qpolynomial_alloc(dim, 0, isl_upoly_zero(dim->ctx));
1479
1539
}
1480
1540
1481
__isl_give isl_qpolynomial *isl_qpolynomial_one(__isl_take isl_dim *dim)
1541
__isl_give isl_qpolynomial *isl_qpolynomial_one_on_domain(
1542
__isl_take isl_space *dim)
1482
1543
{
1483
1544
if (!dim)
1484
1545
return NULL;
1485
1546
return isl_qpolynomial_alloc(dim, 0, isl_upoly_one(dim->ctx));
1486
1547
}
1487
1548
1488
__isl_give isl_qpolynomial *isl_qpolynomial_infty(__isl_take isl_dim *dim)
1549
__isl_give isl_qpolynomial *isl_qpolynomial_infty_on_domain(
1550
__isl_take isl_space *dim)
1489
1551
{
1490
1552
if (!dim)
1491
1553
return NULL;
1492
1554
return isl_qpolynomial_alloc(dim, 0, isl_upoly_infty(dim->ctx));
1493
1555
}
1494
1556
1495
__isl_give isl_qpolynomial *isl_qpolynomial_neginfty(__isl_take isl_dim *dim)
1557
__isl_give isl_qpolynomial *isl_qpolynomial_neginfty_on_domain(
1558
__isl_take isl_space *dim)
1496
1559
{
1497
1560
if (!dim)
1498
1561
return NULL;
1499
1562
return isl_qpolynomial_alloc(dim, 0, isl_upoly_neginfty(dim->ctx));
1500
1563
}
1501
1564
1502
__isl_give isl_qpolynomial *isl_qpolynomial_nan(__isl_take isl_dim *dim)
1565
__isl_give isl_qpolynomial *isl_qpolynomial_nan_on_domain(
1566
__isl_take isl_space *dim)
1503
1567
{
1504
1568
if (!dim)
1505
1569
return NULL;
1506
1570
return isl_qpolynomial_alloc(dim, 0, isl_upoly_nan(dim->ctx));
1507
1571
}
1508
1572
1509
__isl_give isl_qpolynomial *isl_qpolynomial_cst(__isl_take isl_dim *dim,
1573
__isl_give isl_qpolynomial *isl_qpolynomial_cst_on_domain(
1574
__isl_take isl_space *dim,
1510
1575
isl_int v)
1511
1576
{
1512
1577
struct isl_qpolynomial *qp;
1649
1714
if (!qp)
1650
1715
return NULL;
1651
1716
1652
d = isl_dim_total(qp->dim);
1717
d = isl_space_dim(qp->dim, isl_dim_all);
1653
1718
aff = isl_vec_alloc(qp->div->ctx, 2 + d + qp->div->n_row);
1654
1719
if (!aff)
1655
1720
return NULL;
1674
1739
if (!qp1 || !qp2)
1675
1740
return -1;
1676
1741
1677
equal = isl_dim_equal(qp1->dim, qp2->dim);
1742
equal = isl_space_is_equal(qp1->dim, qp2->dim);
1678
1743
if (equal < 0 || !equal)
1679
1744
return equal;
1680
1745
1715
1780
upoly_update_den(qp->upoly, d);
1716
1781
}
1717
1782
1718
__isl_give isl_qpolynomial *isl_qpolynomial_var_pow(__isl_take isl_dim *dim,
1719
int pos, int power)
1783
__isl_give isl_qpolynomial *isl_qpolynomial_var_pow_on_domain(
1784
__isl_take isl_space *dim, int pos, int power)
1720
1785
{
1721
1786
struct isl_ctx *ctx;
1722
1787
1728
1793
return isl_qpolynomial_alloc(dim, 0, isl_upoly_var_pow(ctx, pos, power));
1729
1794
}
1730
1795
1731
__isl_give isl_qpolynomial *isl_qpolynomial_var(__isl_take isl_dim *dim,
1796
__isl_give isl_qpolynomial *isl_qpolynomial_var_on_domain(__isl_take isl_space *dim,
1732
1797
enum isl_dim_type type, unsigned pos)
1733
1798
{
1734
1799
if (!dim)
1735
1800
return NULL;
1736
1801
1737
isl_assert(dim->ctx, isl_dim_size(dim, isl_dim_in) == 0, goto error);
1738
isl_assert(dim->ctx, pos < isl_dim_size(dim, type), goto error);
1802
isl_assert(dim->ctx, isl_space_dim(dim, isl_dim_in) == 0, goto error);
1803
isl_assert(dim->ctx, pos < isl_space_dim(dim, type), goto error);
1739
1804
1740
1805
if (type == isl_dim_set)
1741
pos += isl_dim_size(dim, isl_dim_param);
1806
pos += isl_space_dim(dim, isl_dim_param);
1742
1807
1743
return isl_qpolynomial_var_pow(dim, pos, 1);
1808
return isl_qpolynomial_var_pow_on_domain(dim, pos, 1);
1744
1809
error:
1745
isl_dim_free(dim);
1810
isl_space_free(dim);
1746
1811
return NULL;
1747
1812
}
1748
1813
1855
1920
if (!qp)
1856
1921
goto error;
1857
1922
1858
total = isl_dim_total(qp->dim);
1923
total = isl_space_dim(qp->dim, isl_dim_all);
1859
1924
qp->upoly = isl_upoly_subs(qp->upoly, total + div, 1, &s);
1860
1925
if (!qp->upoly)
1861
1926
goto error;
1896
1961
if (!qp)
1897
1962
return NULL;
1898
1963
1899
total = isl_dim_total(qp->dim);
1964
total = isl_space_dim(qp->dim, isl_dim_all);
1900
1965
for (i = 0; qp && i < qp->div->n_row; ++i) {
1901
1966
if (!isl_int_is_one(qp->div->row[i][0]))
1902
1967
continue;
2061
2126
return NULL;
2062
2127
}
2063
2128
2064
/* Assumes each div only depends on earlier divs.
2065
*/
2066
__isl_give isl_qpolynomial *isl_qpolynomial_div_pow(__isl_take isl_div *div,
2067
int power)
2068
{
2069
struct isl_qpolynomial *qp = NULL;
2070
struct isl_upoly_rec *rec;
2071
struct isl_upoly_cst *cst;
2072
int i, d;
2073
int pos;
2074
2075
if (!div)
2076
return NULL;
2077
2078
d = div->line - div->bmap->div;
2079
2080
pos = isl_dim_total(div->bmap->dim) + d;
2081
rec = isl_upoly_alloc_rec(div->ctx, pos, 1 + power);
2082
qp = isl_qpolynomial_alloc(isl_basic_map_get_dim(div->bmap),
2083
div->bmap->n_div, &rec->up);
2084
if (!qp)
2085
goto error;
2086
2087
for (i = 0; i < div->bmap->n_div; ++i)
2088
isl_seq_cpy(qp->div->row[i], div->bmap->div[i], qp->div->n_col);
2089
2090
for (i = 0; i < 1 + power; ++i) {
2091
rec->p[i] = isl_upoly_zero(div->ctx);
2092
if (!rec->p[i])
2093
goto error;
2094
rec->n++;
2095
}
2096
cst = isl_upoly_as_cst(rec->p[power]);
2097
isl_int_set_si(cst->n, 1);
2098
2099
isl_div_free(div);
2100
2101
qp = reduce_divs(qp);
2102
2103
return qp;
2104
error:
2105
isl_qpolynomial_free(qp);
2106
isl_div_free(div);
2107
return NULL;
2108
}
2109
2110
__isl_give isl_qpolynomial *isl_qpolynomial_div(__isl_take isl_div *div)
2111
{
2112
return isl_qpolynomial_div_pow(div, 1);
2113
}
2114
2115
__isl_give isl_qpolynomial *isl_qpolynomial_rat_cst(__isl_take isl_dim *dim,
2116
const isl_int n, const isl_int d)
2129
__isl_give isl_qpolynomial *isl_qpolynomial_rat_cst_on_domain(
2130
__isl_take isl_space *dim, const isl_int n, const isl_int d)
2117
2131
{
2118
2132
struct isl_qpolynomial *qp;
2119
2133
struct isl_upoly_cst *cst;
2120
2134
2135
if (!dim)
2136
return NULL;
2137
2121
2138
qp = isl_qpolynomial_alloc(dim, 0, isl_upoly_zero(dim->ctx));
2122
2139
if (!qp)
2123
2140
return NULL;
2154
2171
static int set_active(__isl_keep isl_qpolynomial *qp, int *active)
2155
2172
{
2156
2173
int i, j;
2157
int d = isl_dim_total(qp->dim);
2174
int d = isl_space_dim(qp->dim, isl_dim_all);
2158
2175
2159
2176
if (!qp || !active)
2160
2177
return -1;
2182
2199
if (n == 0)
2183
2200
return 0;
2184
2201
2185
isl_assert(qp->dim->ctx, first + n <= isl_dim_size(qp->dim, type),
2186
return -1);
2202
isl_assert(qp->dim->ctx,
2203
first + n <= isl_qpolynomial_dim(qp, type), return -1);
2187
2204
isl_assert(qp->dim->ctx, type == isl_dim_param ||
2188
type == isl_dim_set, return -1);
2205
type == isl_dim_in, return -1);
2189
2206
2190
active = isl_calloc_array(qp->dim->ctx, int, isl_dim_total(qp->dim));
2207
active = isl_calloc_array(qp->dim->ctx, int,
2208
isl_space_dim(qp->dim, isl_dim_all));
2191
2209
if (set_active(qp, active) < 0)
2192
2210
goto error;
2193
2211
2194
if (type == isl_dim_set)
2195
first += isl_dim_size(qp->dim, isl_dim_param);
2212
if (type == isl_dim_in)
2213
first += isl_space_dim(qp->dim, isl_dim_param);
2196
2214
for (i = 0; i < n; ++i)
2197
2215
if (active[first + i]) {
2198
2216
involves = 1;
2228
2246
if (qp->div->n_row == 0)
2229
2247
return qp;
2230
2248
2231
d = isl_dim_total(qp->dim);
2249
d = isl_space_dim(qp->dim, isl_dim_all);
2232
2250
len = qp->div->n_col - 2;
2233
2251
ctx = isl_qpolynomial_get_ctx(qp);
2234
2252
active = isl_calloc_array(ctx, int, len);
2332
2350
qp = isl_qpolynomial_cow(qp);
2333
2351
if (!qp)
2334
2352
return NULL;
2335
qp->dim = isl_dim_set_name(qp->dim, type, pos, s);
2353
qp->dim = isl_space_set_dim_name(qp->dim, type, pos, s);
2336
2354
if (!qp->dim)
2337
2355
goto error;
2338
2356
return qp;
2347
2365
{
2348
2366
if (!qp)
2349
2367
return NULL;
2350
if (n == 0 && !isl_dim_is_named_or_nested(qp->dim, type))
2368
if (type == isl_dim_out)
2369
isl_die(qp->dim->ctx, isl_error_invalid,
2370
"cannot drop output/set dimension",
2371
goto error);
2372
if (type == isl_dim_in)
2373
type = isl_dim_set;
2374
if (n == 0 && !isl_space_is_named_or_nested(qp->dim, type))
2351
2375
return qp;
2352
2376
2353
2377
qp = isl_qpolynomial_cow(qp);
2354
2378
if (!qp)
2355
2379
return NULL;
2356
2380
2357
isl_assert(qp->dim->ctx, first + n <= isl_dim_size(qp->dim, type),
2381
isl_assert(qp->dim->ctx, first + n <= isl_space_dim(qp->dim, type),
2358
2382
goto error);
2359
2383
isl_assert(qp->dim->ctx, type == isl_dim_param ||
2360
2384
type == isl_dim_set, goto error);
2361
2385
2362
qp->dim = isl_dim_drop(qp->dim, type, first, n);
2386
qp->dim = isl_space_drop_dims(qp->dim, type, first, n);
2363
2387
if (!qp->dim)
2364
2388
goto error;
2365
2389
2366
2390
if (type == isl_dim_set)
2367
first += isl_dim_size(qp->dim, isl_dim_param);
2391
first += isl_space_dim(qp->dim, isl_dim_param);
2368
2392
2369
2393
qp->div = isl_mat_drop_cols(qp->div, 2 + first, n);
2370
2394
if (!qp->div)
2380
2404
return NULL;
2381
2405
}
2382
2406
2383
__isl_give isl_qpolynomial *isl_qpolynomial_substitute_equalities(
2407
/* Project the domain of the quasi-polynomial onto its parameter space.
2408
* The quasi-polynomial may not involve any of the domain dimensions.
2409
*/
2410
__isl_give isl_qpolynomial *isl_qpolynomial_project_domain_on_params(
2411
__isl_take isl_qpolynomial *qp)
2412
{
2413
isl_space *space;
2414
unsigned n;
2415
int involves;
2416
2417
n = isl_qpolynomial_dim(qp, isl_dim_in);
2418
involves = isl_qpolynomial_involves_dims(qp, isl_dim_in, 0, n);
2419
if (involves < 0)
2420
return isl_qpolynomial_free(qp);
2421
if (involves)
2422
isl_die(isl_qpolynomial_get_ctx(qp), isl_error_invalid,
2423
"polynomial involves some of the domain dimensions",
2424
return isl_qpolynomial_free(qp));
2425
qp = isl_qpolynomial_drop_dims(qp, isl_dim_in, 0, n);
2426
space = isl_qpolynomial_get_domain_space(qp);
2427
space = isl_space_params(space);
2428
qp = isl_qpolynomial_reset_domain_space(qp, space);
2429
return qp;
2430
}
2431
2432
static __isl_give isl_qpolynomial *isl_qpolynomial_substitute_equalities_lifted(
2384
2433
__isl_take isl_qpolynomial *qp, __isl_take isl_basic_set *eq)
2385
2434
{
2386
2435
int i, j, k;
2403
2452
if (!qp->div)
2404
2453
goto error;
2405
2454
2406
total = 1 + isl_dim_total(eq->dim);
2455
total = 1 + isl_space_dim(eq->dim, isl_dim_all);
2407
2456
n_div = eq->n_div;
2408
2457
isl_int_init(denom);
2409
2458
for (i = 0; i < eq->n_eq; ++i) {
2446
2495
return NULL;
2447
2496
}
2448
2497
2498
/* Exploit the equalities in "eq" to simplify the quasi-polynomial.
2499
*/
2500
__isl_give isl_qpolynomial *isl_qpolynomial_substitute_equalities(
2501
__isl_take isl_qpolynomial *qp, __isl_take isl_basic_set *eq)
2502
{
2503
if (!qp || !eq)
2504
goto error;
2505
if (qp->div->n_row > 0)
2506
eq = isl_basic_set_add(eq, isl_dim_set, qp->div->n_row);
2507
return isl_qpolynomial_substitute_equalities_lifted(qp, eq);
2508
error:
2509
isl_basic_set_free(eq);
2510
isl_qpolynomial_free(qp);
2511
return NULL;
2512
}
2513
2449
2514
static __isl_give isl_basic_set *add_div_constraints(
2450
2515
__isl_take isl_basic_set *bset, __isl_take isl_mat *div)
2451
2516
{
2488
2553
isl_basic_set *bset;
2489
2554
context = isl_set_add_dims(context, isl_dim_set,
2490
2555
qp->div->n_row);
2491
bset = isl_basic_set_universe(isl_set_get_dim(context));
2556
bset = isl_basic_set_universe(isl_set_get_space(context));
2492
2557
bset = add_div_constraints(bset, isl_mat_copy(qp->div));
2493
2558
context = isl_set_intersect(context,
2494
2559
isl_set_from_basic_set(bset));
2495
2560
}
2496
2561
2497
2562
aff = isl_set_affine_hull(context);
2498
return isl_qpolynomial_substitute_equalities(qp, aff);
2563
return isl_qpolynomial_substitute_equalities_lifted(qp, aff);
2499
2564
error:
2500
2565
isl_qpolynomial_free(qp);
2501
2566
isl_set_free(context);
2502
2567
return NULL;
2503
2568
}
2504
2569
2570
__isl_give isl_qpolynomial *isl_qpolynomial_gist_params(
2571
__isl_take isl_qpolynomial *qp, __isl_take isl_set *context)
2572
{
2573
isl_space *space = isl_qpolynomial_get_domain_space(qp);
2574
isl_set *dom_context = isl_set_universe(space);
2575
dom_context = isl_set_intersect_params(dom_context, context);
2576
return isl_qpolynomial_gist(qp, dom_context);
2577
}
2578
2579
__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_qpolynomial(
2580
__isl_take isl_qpolynomial *qp)
2581
{
2582
isl_set *dom;
2583
2584
if (!qp)
2585
return NULL;
2586
if (isl_qpolynomial_is_zero(qp)) {
2587
isl_space *dim = isl_qpolynomial_get_space(qp);
2588
isl_qpolynomial_free(qp);
2589
return isl_pw_qpolynomial_zero(dim);
2590
}
2591
2592
dom = isl_set_universe(isl_qpolynomial_get_domain_space(qp));
2593
return isl_pw_qpolynomial_alloc(dom, qp);
2594
}
2595
2505
2596
#undef PW
2506
2597
#define PW isl_pw_qpolynomial
2507
2598
#undef EL
2514
2605
#define IS_ZERO is_zero
2515
2606
#undef FIELD
2516
2607
#define FIELD qp
2608
#undef DEFAULT_IS_ZERO
2609
#define DEFAULT_IS_ZERO 1
2517
2610
2518
2611
#include <isl_pw_templ.c>
2519
2612
2523
2616
#define PART isl_pw_qpolynomial
2524
2617
#undef PARTS
2525
2618
#define PARTS pw_qpolynomial
2619
#define ALIGN_DOMAIN
2526
2620
2527
2621
#include <isl_union_templ.c>
2528
2622
2540
2634
return isl_qpolynomial_is_one(pwqp->p[0].qp);
2541
2635
}
2542
2636
2637
__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add(
2638
__isl_take isl_pw_qpolynomial *pwqp1,
2639
__isl_take isl_pw_qpolynomial *pwqp2)
2640
{
2641
return isl_pw_qpolynomial_union_add_(pwqp1, pwqp2);
2642
}
2643
2543
2644
__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_mul(
2544
2645
__isl_take isl_pw_qpolynomial *pwqp1,
2545
2646
__isl_take isl_pw_qpolynomial *pwqp2)
2550
2651
if (!pwqp1 || !pwqp2)
2551
2652
goto error;
2552
2653
2553
isl_assert(pwqp1->dim->ctx, isl_dim_equal(pwqp1->dim, pwqp2->dim),
2654
isl_assert(pwqp1->dim->ctx, isl_space_is_equal(pwqp1->dim, pwqp2->dim),
2554
2655
goto error);
2555
2656
2556
2657
if (isl_pw_qpolynomial_is_zero(pwqp1)) {
2574
2675
}
2575
2676
2576
2677
n = pwqp1->n * pwqp2->n;
2577
res = isl_pw_qpolynomial_alloc_(isl_dim_copy(pwqp1->dim), n);
2678
res = isl_pw_qpolynomial_alloc_size(isl_space_copy(pwqp1->dim), n);
2578
2679
2579
2680
for (i = 0; i < pwqp1->n; ++i) {
2580
2681
for (j = 0; j < pwqp2->n; ++j) {
2651
2752
{
2652
2753
isl_vec *ext;
2653
2754
struct isl_upoly *up;
2654
isl_dim *dim;
2755
isl_space *dim;
2655
2756
2656
2757
if (!qp || !pnt)
2657
2758
goto error;
2658
isl_assert(pnt->dim->ctx, isl_dim_equal(pnt->dim, qp->dim), goto error);
2759
isl_assert(pnt->dim->ctx, isl_space_is_equal(pnt->dim, qp->dim), goto error);
2659
2760
2660
2761
if (qp->div->n_row == 0)
2661
2762
ext = isl_vec_copy(pnt->vec);
2662
2763
else {
2663
2764
int i;
2664
unsigned dim = isl_dim_total(qp->dim);
2765
unsigned dim = isl_space_dim(qp->dim, isl_dim_all);
2665
2766
ext = isl_vec_alloc(qp->dim->ctx, 1 + dim + qp->div->n_row);
2666
2767
if (!ext)
2667
2768
goto error;
2679
2780
if (!up)
2680
2781
goto error;
2681
2782
2682
dim = isl_dim_copy(qp->dim);
2783
dim = isl_space_copy(qp->dim);
2683
2784
isl_qpolynomial_free(qp);
2684
2785
isl_point_free(pnt);
2685
2786
2784
2885
unsigned g_pos;
2785
2886
int *exp;
2786
2887
2787
if (n == 0 && !isl_dim_is_named_or_nested(qp->dim, type))
2888
if (!qp)
2889
return NULL;
2890
if (type == isl_dim_out)
2891
isl_die(qp->div->ctx, isl_error_invalid,
2892
"cannot insert output/set dimensions",
2893
goto error);
2894
if (type == isl_dim_in)
2895
type = isl_dim_set;
2896
if (n == 0 && !isl_space_is_named_or_nested(qp->dim, type))
2788
2897
return qp;
2789
2898
2790
2899
qp = isl_qpolynomial_cow(qp);
2791
2900
if (!qp)
2792
2901
return NULL;
2793
2902
2794
isl_assert(qp->div->ctx, first <= isl_dim_size(qp->dim, type),
2903
isl_assert(qp->div->ctx, first <= isl_space_dim(qp->dim, type),
2795
2904
goto error);
2796
2905
2797
2906
g_pos = pos(qp->dim, type) + first;
2814
2923
goto error;
2815
2924
}
2816
2925
2817
qp->dim = isl_dim_insert(qp->dim, type, first, n);
2926
qp->dim = isl_space_insert_dims(qp->dim, type, first, n);
2818
2927
if (!qp->dim)
2819
2928
goto error;
2820
2929
2891
3000
if (!qp)
2892
3001
return NULL;
2893
3002
2894
isl_assert(qp->dim->ctx, src_pos + n <= isl_dim_size(qp->dim, src_type),
3003
if (dst_type == isl_dim_out || src_type == isl_dim_out)
3004
isl_die(qp->dim->ctx, isl_error_invalid,
3005
"cannot move output/set dimension",
3006
goto error);
3007
if (dst_type == isl_dim_in)
3008
dst_type = isl_dim_set;
3009
if (src_type == isl_dim_in)
3010
src_type = isl_dim_set;
3011
3012
isl_assert(qp->dim->ctx, src_pos + n <= isl_space_dim(qp->dim, src_type),
2895
3013
goto error);
2896
3014
2897
3015
g_dst_pos = pos(qp->dim, dst_type) + dst_pos;
2916
3034
if (!qp->upoly)
2917
3035
goto error;
2918
3036
2919
qp->dim = isl_dim_move(qp->dim, dst_type, dst_pos, src_type, src_pos, n);
3037
qp->dim = isl_space_move_dims(qp->dim, dst_type, dst_pos, src_type, src_pos, n);
2920
3038
if (!qp->dim)
2921
3039
goto error;
2922
3040
2926
3044
return NULL;
2927
3045
}
2928
3046
2929
__isl_give isl_qpolynomial *isl_qpolynomial_from_affine(__isl_take isl_dim *dim,
3047
__isl_give isl_qpolynomial *isl_qpolynomial_from_affine(__isl_take isl_space *dim,
2930
3048
isl_int *f, isl_int denom)
2931
3049
{
2932
3050
struct isl_upoly *up;
2933
3051
3052
dim = isl_space_domain(dim);
2934
3053
if (!dim)
2935
3054
return NULL;
2936
3055
2937
up = isl_upoly_from_affine(dim->ctx, f, denom, 1 + isl_dim_total(dim));
3056
up = isl_upoly_from_affine(dim->ctx, f, denom,
3057
1 + isl_space_dim(dim, isl_dim_all));
2938
3058
2939
3059
return isl_qpolynomial_alloc(dim, 0, up);
2940
3060
}
2952
3072
up = isl_upoly_from_affine(ctx, aff->v->el + 1, aff->v->el[0],
2953
3073
aff->v->size - 1);
2954
3074
2955
qp = isl_qpolynomial_alloc(isl_aff_get_dim(aff),
3075
qp = isl_qpolynomial_alloc(isl_aff_get_domain_space(aff),
2956
3076
aff->ls->div->n_row, up);
2957
3077
if (!qp)
2958
3078
goto error;
2972
3092
return NULL;
2973
3093
}
2974
3094
3095
__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_pw_aff(
3096
__isl_take isl_pw_aff *pwaff)
3097
{
3098
int i;
3099
isl_pw_qpolynomial *pwqp;
3100
3101
if (!pwaff)
3102
return NULL;
3103
3104
pwqp = isl_pw_qpolynomial_alloc_size(isl_pw_aff_get_space(pwaff),
3105
pwaff->n);
3106
3107
for (i = 0; i < pwaff->n; ++i) {
3108
isl_set *dom;
3109
isl_qpolynomial *qp;
3110
3111
dom = isl_set_copy(pwaff->p[i].set);
3112
qp = isl_qpolynomial_from_aff(isl_aff_copy(pwaff->p[i].aff));
3113
pwqp = isl_pw_qpolynomial_add_piece(pwqp, dom, qp);
3114
}
3115
3116
isl_pw_aff_free(pwaff);
3117
return pwqp;
3118
}
3119
2975
3120
__isl_give isl_qpolynomial *isl_qpolynomial_from_constraint(
2976
3121
__isl_take isl_constraint *c, enum isl_dim_type type, unsigned pos)
2977
3122
{
2999
3144
qp = isl_qpolynomial_cow(qp);
3000
3145
if (!qp)
3001
3146
return NULL;
3147
3148
if (type == isl_dim_out)
3149
isl_die(qp->dim->ctx, isl_error_invalid,
3150
"cannot substitute output/set dimension",
3151
goto error);
3152
if (type == isl_dim_in)
3153
type = isl_dim_set;
3154
3002
3155
for (i = 0; i < n; ++i)
3003
3156
if (!subs[i])
3004
3157
goto error;
3005
3158
3006
isl_assert(qp->dim->ctx, first + n <= isl_dim_size(qp->dim, type),
3159
isl_assert(qp->dim->ctx, first + n <= isl_space_dim(qp->dim, type),
3007
3160
goto error);
3008
3161
3009
3162
for (i = 0; i < n; ++i)
3010
isl_assert(qp->dim->ctx, isl_dim_equal(qp->dim, subs[i]->dim),
3163
isl_assert(qp->dim->ctx, isl_space_is_equal(qp->dim, subs[i]->dim),
3011
3164
goto error);
3012
3165
3013
3166
isl_assert(qp->dim->ctx, qp->div->n_row == 0, goto error);
3045
3198
int (*fn)(__isl_take isl_basic_set *bset,
3046
3199
__isl_take isl_qpolynomial *poly, void *user), void *user)
3047
3200
{
3048
isl_dim *dim;
3201
isl_space *dim;
3049
3202
isl_mat *div;
3050
3203
isl_qpolynomial *poly;
3051
3204
3056
3209
user);
3057
3210
3058
3211
div = isl_mat_copy(qp->div);
3059
dim = isl_dim_copy(qp->dim);
3060
dim = isl_dim_add(dim, isl_dim_set, qp->div->n_row);
3212
dim = isl_space_copy(qp->dim);
3213
dim = isl_space_add_dims(dim, isl_dim_set, qp->div->n_row);
3061
3214
poly = isl_qpolynomial_alloc(dim, 0, isl_upoly_copy(qp->upoly));
3062
3215
bset = isl_basic_set_copy(bset);
3063
3216
bset = isl_basic_set_add(bset, isl_dim_set, qp->div->n_row);
3112
3265
if (!poly)
3113
3266
return -2;
3114
3267
3115
ovar = isl_dim_offset(poly->dim, isl_dim_set);
3116
nvar = isl_dim_size(poly->dim, isl_dim_set);
3268
ovar = isl_space_offset(poly->dim, isl_dim_set);
3269
nvar = isl_space_dim(poly->dim, isl_dim_set);
3117
3270
return isl_upoly_degree(poly->upoly, ovar, ovar + nvar);
3118
3271
}
3119
3272
3178
3331
if (!qp)
3179
3332
return NULL;
3180
3333
3181
isl_assert(qp->div->ctx, t_pos < isl_dim_size(qp->dim, type),
3334
if (type == isl_dim_out)
3335
isl_die(qp->div->ctx, isl_error_invalid,
3336
"output/set dimension does not have a coefficient",
3337
return NULL);
3338
if (type == isl_dim_in)
3339
type = isl_dim_set;
3340
3341
isl_assert(qp->div->ctx, t_pos < isl_space_dim(qp->dim, type),
3182
3342
return NULL);
3183
3343
3184
3344
g_pos = pos(qp->dim, type) + t_pos;
3185
3345
up = isl_upoly_coeff(qp->upoly, g_pos, deg);
3186
3346
3187
c = isl_qpolynomial_alloc(isl_dim_copy(qp->dim), qp->div->n_row, up);
3347
c = isl_qpolynomial_alloc(isl_space_copy(qp->dim), qp->div->n_row, up);
3188
3348
if (!c)
3189
3349
return NULL;
3190
3350
isl_mat_free(c->div);
3260
3420
if (deg < -1)
3261
3421
goto error;
3262
3422
3263
poly = isl_qpolynomial_insert_dims(poly, isl_dim_set, 0, 1);
3423
poly = isl_qpolynomial_insert_dims(poly, isl_dim_in, 0, 1);
3264
3424
poly = isl_qpolynomial_cow(poly);
3265
3425
if (!poly)
3266
3426
goto error;
3267
3427
3268
ovar = isl_dim_offset(poly->dim, isl_dim_set);
3269
nvar = isl_dim_size(poly->dim, isl_dim_set);
3428
ovar = isl_space_offset(poly->dim, isl_dim_set);
3429
nvar = isl_space_dim(poly->dim, isl_dim_set);
3270
3430
poly->upoly = isl_upoly_homogenize(poly->upoly, 0, deg,
3271
3431
ovar, ovar + nvar);
3272
3432
if (!poly->upoly)
3278
3438
return NULL;
3279
3439
}
3280
3440
3281
__isl_give isl_term *isl_term_alloc(__isl_take isl_dim *dim,
3441
__isl_give isl_term *isl_term_alloc(__isl_take isl_space *dim,
3282
3442
__isl_take isl_mat *div)
3283
3443
{
3284
3444
isl_term *term;
3287
3447
if (!dim || !div)
3288
3448
goto error;
3289
3449
3290
n = isl_dim_total(dim) + div->n_row;
3450
n = isl_space_dim(dim, isl_dim_all) + div->n_row;
3291
3451
3292
3452
term = isl_calloc(dim->ctx, struct isl_term,
3293
3453
sizeof(struct isl_term) + (n - 1) * sizeof(int));
3302
3462
3303
3463
return term;
3304
3464
error:
3305
isl_dim_free(dim);
3465
isl_space_free(dim);
3306
3466
isl_mat_free(div);
3307
3467
return NULL;
3308
3468
}
3325
3485
if (term)
3326
3486
return NULL;
3327
3487
3328
total = isl_dim_total(term->dim) + term->div->n_row;
3488
total = isl_space_dim(term->dim, isl_dim_all) + term->div->n_row;
3329
3489
3330
dup = isl_term_alloc(isl_dim_copy(term->dim), isl_mat_copy(term->div));
3490
dup = isl_term_alloc(isl_space_copy(term->dim), isl_mat_copy(term->div));
3331
3491
if (!dup)
3332
3492
return NULL;
3333
3493
3359
3519
if (--term->ref > 0)
3360
3520
return;
3361
3521
3362
isl_dim_free(term->dim);
3522
isl_space_free(term->dim);
3363
3523
isl_mat_free(term->div);
3364
3524
isl_int_clear(term->n);
3365
3525
isl_int_clear(term->d);
3374
3534
switch (type) {
3375
3535
case isl_dim_param:
3376
3536
case isl_dim_in:
3377
case isl_dim_out: return isl_dim_size(term->dim, type);
3537
case isl_dim_out: return isl_space_dim(term->dim, type);
3378
3538
case isl_dim_div: return term->div->n_row;
3379
case isl_dim_all: return isl_dim_total(term->dim) + term->div->n_row;
3539
case isl_dim_all: return isl_space_dim(term->dim, isl_dim_all) +
3540
term->div->n_row;
3380
3541
default: return 0;
3381
3542
}
3382
3543
}
3409
3570
isl_assert(term->dim->ctx, pos < isl_term_dim(term, type), return -1);
3410
3571
3411
3572
if (type >= isl_dim_set)
3412
pos += isl_dim_size(term->dim, isl_dim_param);
3573
pos += isl_space_dim(term->dim, isl_dim_param);
3413
3574
if (type >= isl_dim_div)
3414
pos += isl_dim_size(term->dim, isl_dim_set);
3575
pos += isl_space_dim(term->dim, isl_dim_set);
3415
3576
3416
3577
return term->pow[pos];
3417
3578
}
3418
3579
3419
__isl_give isl_div *isl_term_get_div(__isl_keep isl_term *term, unsigned pos)
3580
__isl_give isl_aff *isl_term_get_div(__isl_keep isl_term *term, unsigned pos)
3420
3581
{
3421
isl_basic_map *bmap;
3582
isl_local_space *ls;
3583
isl_aff *aff;
3422
3584
unsigned total;
3423
int k;
3424
3585
3425
3586
if (!term)
3426
3587
return NULL;
3435
3596
term->div->n_row) == -1,
3436
3597
return NULL);
3437
3598
3438
bmap = isl_basic_map_alloc_dim(isl_dim_copy(term->dim), 1, 0, 0);
3439
if ((k = isl_basic_map_alloc_div(bmap)) < 0)
3440
goto error;
3441
3442
isl_seq_cpy(bmap->div[k], term->div->row[pos], 2 + total);
3443
3444
return isl_basic_map_div(bmap, k);
3445
error:
3446
isl_basic_map_free(bmap);
3447
return NULL;
3599
ls = isl_local_space_alloc_div(isl_space_copy(term->dim),
3600
isl_mat_copy(term->div));
3601
aff = isl_aff_alloc(ls);
3602
if (!aff)
3603
return NULL;
3604
3605
isl_seq_cpy(aff->v->el, term->div->row[pos], aff->v->size);
3606
3607
return aff;
3448
3608
}
3449
3609
3450
3610
__isl_give isl_term *isl_upoly_foreach_term(__isl_keep struct isl_upoly *up,
3508
3668
if (!qp)
3509
3669
return -1;
3510
3670
3511
term = isl_term_alloc(isl_dim_copy(qp->dim), isl_mat_copy(qp->div));
3671
term = isl_term_alloc(isl_space_copy(qp->dim), isl_mat_copy(qp->div));
3512
3672
if (!term)
3513
3673
return -1;
3514
3674
3528
3688
if (!term)
3529
3689
return NULL;
3530
3690
3531
n = isl_dim_total(term->dim) + term->div->n_row;
3691
n = isl_space_dim(term->dim, isl_dim_all) + term->div->n_row;
3532
3692
3533
3693
up = isl_upoly_rat_cst(term->dim->ctx, term->n, term->d);
3534
3694
for (i = 0; i < n; ++i) {
3538
3698
isl_upoly_var_pow(term->dim->ctx, i, term->pow[i]));
3539
3699
}
3540
3700
3541
qp = isl_qpolynomial_alloc(isl_dim_copy(term->dim), term->div->n_row, up);
3701
qp = isl_qpolynomial_alloc(isl_space_copy(term->dim), term->div->n_row, up);
3542
3702
if (!qp)
3543
3703
goto error;
3544
3704
isl_mat_free(qp->div);
3555
3715
}
3556
3716
3557
3717
__isl_give isl_qpolynomial *isl_qpolynomial_lift(__isl_take isl_qpolynomial *qp,
3558
__isl_take isl_dim *dim)
3718
__isl_take isl_space *dim)
3559
3719
{
3560
3720
int i;
3561
3721
int extra;
3564
3724
if (!qp || !dim)
3565
3725
goto error;
3566
3726
3567
if (isl_dim_equal(qp->dim, dim)) {
3568
isl_dim_free(dim);
3727
if (isl_space_is_equal(qp->dim, dim)) {
3728
isl_space_free(dim);
3569
3729
return qp;
3570
3730
}
3571
3731
3573
3733
if (!qp)
3574
3734
goto error;
3575
3735
3576
extra = isl_dim_size(dim, isl_dim_set) -
3577
isl_dim_size(qp->dim, isl_dim_set);
3578
total = isl_dim_total(qp->dim);
3736
extra = isl_space_dim(dim, isl_dim_set) -
3737
isl_space_dim(qp->dim, isl_dim_set);
3738
total = isl_space_dim(qp->dim, isl_dim_all);
3579
3739
if (qp->div->n_row) {
3580
3740
int *exp;
3581
3741
3595
3755
for (i = 0; i < qp->div->n_row; ++i)
3596
3756
isl_seq_clr(qp->div->row[i] + 2 + total, extra);
3597
3757
3598
isl_dim_free(qp->dim);
3758
isl_space_free(qp->dim);
3599
3759
qp->dim = dim;
3600
3760
3601
3761
return qp;
3602
3762
error:
3603
isl_dim_free(dim);
3763
isl_space_free(dim);
3604
3764
isl_qpolynomial_free(qp);
3605
3765
return NULL;
3606
3766
}
3620
3780
if (!set || !qp)
3621
3781
goto error;
3622
3782
3623
d = isl_dim_total(set->dim);
3783
d = isl_space_dim(set->dim, isl_dim_all);
3624
3784
active = isl_calloc_array(set->ctx, int, d);
3625
3785
if (set_active(qp, active) < 0)
3626
3786
goto error;
3634
3794
return set;
3635
3795
}
3636
3796
3637
nparam = isl_dim_size(set->dim, isl_dim_param);
3638
nvar = isl_dim_size(set->dim, isl_dim_set);
3797
nparam = isl_space_dim(set->dim, isl_dim_param);
3798
nvar = isl_space_dim(set->dim, isl_dim_set);
3639
3799
for (i = 0; i < nparam; ++i) {
3640
3800
if (active[i])
3641
3801
continue;
3702
3862
if (isl_set_foreach_point(set, opt_fn, &data) < 0)
3703
3863
goto error;
3704
3864
3705
if (data.first)
3706
data.opt = isl_qpolynomial_zero(isl_qpolynomial_get_dim(qp));
3865
if (data.first) {
3866
isl_space *space = isl_qpolynomial_get_domain_space(qp);
3867
data.opt = isl_qpolynomial_zero_on_domain(space);
3868
}
3707
3869
3708
3870
isl_set_free(set);
3709
3871
isl_qpolynomial_free(qp);
3715
3877
return NULL;
3716
3878
}
3717
3879
3718
__isl_give isl_qpolynomial *isl_qpolynomial_morph(__isl_take isl_qpolynomial *qp,
3719
__isl_take isl_morph *morph)
3880
__isl_give isl_qpolynomial *isl_qpolynomial_morph_domain(
3881
__isl_take isl_qpolynomial *qp, __isl_take isl_morph *morph)
3720
3882
{
3721
3883
int i;
3722
3884
int n_sub;
3723
3885
isl_ctx *ctx;
3724
3886
struct isl_upoly **subs;
3725
isl_mat *mat;
3887
isl_mat *mat, *diag;
3726
3888
3727
3889
qp = isl_qpolynomial_cow(qp);
3728
3890
if (!qp || !morph)
3729
3891
goto error;
3730
3892
3731
3893
ctx = qp->dim->ctx;
3732
isl_assert(ctx, isl_dim_equal(qp->dim, morph->dom->dim), goto error);
3894
isl_assert(ctx, isl_space_is_equal(qp->dim, morph->dom->dim), goto error);
3733
3895
3734
3896
n_sub = morph->inv->n_row - 1;
3735
3897
if (morph->inv->n_row != morph->inv->n_col)
3752
3914
isl_upoly_free(subs[i]);
3753
3915
free(subs);
3754
3916
3755
mat = isl_mat_diagonal(isl_mat_identity(ctx, 1), isl_mat_copy(morph->inv));
3756
mat = isl_mat_diagonal(mat, isl_mat_identity(ctx, qp->div->n_row));
3917
diag = isl_mat_diag(ctx, 1, morph->inv->row[0][0]);
3918
mat = isl_mat_diagonal(diag, isl_mat_copy(morph->inv));
3919
diag = isl_mat_diag(ctx, qp->div->n_row, morph->inv->row[0][0]);
3920
mat = isl_mat_diagonal(mat, diag);
3757
3921
qp->div = isl_mat_product(qp->div, mat);
3758
isl_dim_free(qp->dim);
3759
qp->dim = isl_dim_copy(morph->ran->dim);
3922
isl_space_free(qp->dim);
3923
qp->dim = isl_space_copy(morph->ran->dim);
3760
3924
3761
3925
if (!qp->upoly || !qp->div || !qp->dim)
3762
3926
goto error;
3812
3976
isl_pw_qpolynomial *pwpq = *entry;
3813
3977
int empty;
3814
3978
3815
hash = isl_dim_get_hash(pwpq->dim);
3979
hash = isl_space_get_hash(pwpq->dim);
3816
3980
entry2 = isl_hash_table_find(data->u2->dim->ctx, &data->u2->table,
3817
3981
hash, &has_dim, pwpq->dim, 0);
3818
3982
if (!entry2)
3857
4021
if (!div || !r)
3858
4022
goto error;
3859
4023
3860
extra = isl_dim_total(r->dim) + div->n_row - r->len;
4024
extra = isl_space_dim(r->dim, isl_dim_all) + div->n_row - r->len;
3861
4025
mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
3862
4026
if (!mat)
3863
4027
goto error;
3881
4045
3882
4046
/* Reorder the dimension of "qp" according to the given reordering.
3883
4047
*/
3884
__isl_give isl_qpolynomial *isl_qpolynomial_realign(
4048
__isl_give isl_qpolynomial *isl_qpolynomial_realign_domain(
3885
4049
__isl_take isl_qpolynomial *qp, __isl_take isl_reordering *r)
3886
4050
{
3887
4051
qp = isl_qpolynomial_cow(qp);
3900
4064
if (!qp->upoly)
3901
4065
goto error;
3902
4066
3903
qp = isl_qpolynomial_reset_dim(qp, isl_dim_copy(r->dim));
4067
qp = isl_qpolynomial_reset_domain_space(qp, isl_space_copy(r->dim));
3904
4068
3905
4069
isl_reordering_free(r);
3906
4070
return qp;
3911
4075
}
3912
4076
3913
4077
__isl_give isl_qpolynomial *isl_qpolynomial_align_params(
3914
__isl_take isl_qpolynomial *qp, __isl_take isl_dim *model)
4078
__isl_take isl_qpolynomial *qp, __isl_take isl_space *model)
3915
4079
{
3916
4080
if (!qp || !model)
3917
4081
goto error;
3918
4082
3919
if (!isl_dim_match(qp->dim, isl_dim_param, model, isl_dim_param)) {
4083
if (!isl_space_match(qp->dim, isl_dim_param, model, isl_dim_param)) {
3920
4084
isl_reordering *exp;
3921
4085
3922
model = isl_dim_drop(model, isl_dim_in,
3923
0, isl_dim_size(model, isl_dim_in));
3924
model = isl_dim_drop(model, isl_dim_out,
3925
0, isl_dim_size(model, isl_dim_out));
4086
model = isl_space_drop_dims(model, isl_dim_in,
4087
0, isl_space_dim(model, isl_dim_in));
4088
model = isl_space_drop_dims(model, isl_dim_out,
4089
0, isl_space_dim(model, isl_dim_out));
3926
4090
exp = isl_parameter_alignment_reordering(qp->dim, model);
3927
exp = isl_reordering_extend_dim(exp,
3928
isl_qpolynomial_get_dim(qp));
3929
qp = isl_qpolynomial_realign(qp, exp);
4091
exp = isl_reordering_extend_space(exp,
4092
isl_qpolynomial_get_domain_space(qp));
4093
qp = isl_qpolynomial_realign_domain(qp, exp);
3930
4094
}
3931
4095
3932
isl_dim_free(model);
4096
isl_space_free(model);
3933
4097
return qp;
3934
4098
error:
3935
isl_dim_free(model);
4099
isl_space_free(model);
3936
4100
isl_qpolynomial_free(qp);
3937
4101
return NULL;
3938
4102
}
3952
4116
* f - m v >= 0
3953
4117
* -f + m v + (m - 1) >= 0
3954
4118
*/
3955
static __isl_give isl_set *set_div_slice(__isl_take isl_dim *dim,
4119
static __isl_give isl_set *set_div_slice(__isl_take isl_space *dim,
3956
4120
__isl_keep isl_qpolynomial *qp, int div, isl_int v)
3957
4121
{
3958
4122
int total;
3962
4126
if (!dim || !qp)
3963
4127
goto error;
3964
4128
3965
total = isl_dim_total(dim);
3966
bset = isl_basic_set_alloc_dim(isl_dim_copy(dim), 0, 0, 2);
4129
total = isl_space_dim(dim, isl_dim_all);
4130
bset = isl_basic_set_alloc_space(isl_space_copy(dim), 0, 0, 2);
3967
4131
3968
4132
k = isl_basic_set_alloc_inequality(bset);
3969
4133
if (k < 0)
3979
4143
isl_int_add(bset->ineq[k][0], bset->ineq[k][0], qp->div->row[div][0]);
3980
4144
isl_int_sub_ui(bset->ineq[k][0], bset->ineq[k][0], 1);
3981
4145
3982
isl_dim_free(dim);
4146
isl_space_free(dim);
3983
4147
return isl_set_from_basic_set(bset);
3984
4148
error:
3985
4149
isl_basic_set_free(bset);
3986
isl_dim_free(dim);
4150
isl_space_free(dim);
3987
4151
return NULL;
3988
4152
}
3989
4153
4003
4167
isl_set *slice;
4004
4168
struct isl_upoly *cst;
4005
4169
4006
slice = set_div_slice(isl_set_get_dim(set), qp, div, v);
4170
slice = set_div_slice(isl_set_get_space(set), qp, div, v);
4007
4171
set = isl_set_intersect(set, slice);
4008
4172
4009
4173
if (!qp)
4010
4174
goto error;
4011
4175
4012
total = isl_dim_total(qp->dim);
4176
total = isl_space_dim(qp->dim, isl_dim_all);
4013
4177
4014
4178
for (i = div + 1; i < qp->div->n_row; ++i) {
4015
4179
if (isl_int_is_zero(qp->div->row[i][2 + total + div]))
4082
4246
4083
4247
isl_int_init(min);
4084
4248
isl_int_init(max);
4085
total = isl_dim_total(qp->dim);
4249
total = isl_space_dim(qp->dim, isl_dim_all);
4086
4250
for (i = 0; i < qp->div->n_row; ++i) {
4087
4251
enum isl_lp_result lp_res;
4088
4252
4143
4307
struct isl_split_periods_data data;
4144
4308
4145
4309
data.max_periods = max_periods;
4146
data.res = isl_pw_qpolynomial_zero(isl_pw_qpolynomial_get_dim(pwqp));
4310
data.res = isl_pw_qpolynomial_zero(isl_pw_qpolynomial_get_space(pwqp));
4147
4311
4148
4312
if (isl_pw_qpolynomial_foreach_piece(pwqp, &split_periods, &data) < 0)
4149
4313
goto error;
4166
4330
static __isl_give isl_pw_qpolynomial *constant_on_domain(
4167
4331
__isl_take isl_basic_set *bset, int cst)
4168
4332
{
4169
isl_dim *dim;
4333
isl_space *dim;
4170
4334
isl_qpolynomial *qp;
4171
4335
4172
4336
if (!bset)
4173
4337
return NULL;
4174
4338
4175
bset = isl_basic_map_domain(isl_basic_map_from_range(bset));
4176
dim = isl_basic_set_get_dim(bset);
4339
bset = isl_basic_set_params(bset);
4340
dim = isl_basic_set_get_space(bset);
4177
4341
if (cst < 0)
4178
qp = isl_qpolynomial_infty(dim);
4342
qp = isl_qpolynomial_infty_on_domain(dim);
4179
4343
else if (cst == 0)
4180
qp = isl_qpolynomial_zero(dim);
4344
qp = isl_qpolynomial_zero_on_domain(dim);
4181
4345
else
4182
qp = isl_qpolynomial_one(dim);
4346
qp = isl_qpolynomial_one_on_domain(dim);
4183
4347
return isl_pw_qpolynomial_alloc(isl_set_from_basic_set(bset), qp);
4184
4348
}
4185
4349
4194
4358
__isl_give isl_pw_qpolynomial *(*fn)(__isl_take isl_basic_set *bset))
4195
4359
{
4196
4360
int i, n;
4197
isl_dim *dim;
4361
isl_space *dim;
4198
4362
isl_set *set;
4199
4363
isl_factorizer *f;
4200
4364
isl_qpolynomial *qp;
4213
4377
nparam = isl_basic_set_dim(bset, isl_dim_param);
4214
4378
nvar = isl_basic_set_dim(bset, isl_dim_set);
4215
4379
4216
dim = isl_basic_set_get_dim(bset);
4217
dim = isl_dim_domain(dim);
4218
set = isl_set_universe(isl_dim_copy(dim));
4219
qp = isl_qpolynomial_one(dim);
4380
dim = isl_basic_set_get_space(bset);
4381
dim = isl_space_domain(dim);
4382
set = isl_set_universe(isl_space_copy(dim));
4383
qp = isl_qpolynomial_one_on_domain(dim);
4220
4384
pwqp = isl_pw_qpolynomial_alloc(set, qp);
4221
4385
4222
4386
bset = isl_morph_basic_set(isl_morph_copy(f->morph), bset);
4264
4428
int bounded;
4265
4429
isl_morph *morph;
4266
4430
isl_pw_qpolynomial *pwqp;
4267
unsigned orig_nvar, final_nvar;
4268
4431
4269
4432
if (!bset)
4270
4433
return NULL;
4272
4435
if (isl_basic_set_plain_is_empty(bset))
4273
4436
return constant_on_domain(bset, 0);
4274
4437
4275
orig_nvar = isl_basic_set_dim(bset, isl_dim_set);
4276
4277
if (orig_nvar == 0)
4438
if (isl_basic_set_dim(bset, isl_dim_set) == 0)
4278
4439
return constant_on_domain(bset, 1);
4279
4440
4280
4441
bounded = isl_basic_set_is_bounded(bset);
4289
4450
morph = isl_basic_set_full_compression(bset);
4290
4451
bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
4291
4452
4292
final_nvar = isl_basic_set_dim(bset, isl_dim_set);
4293
4294
4453
pwqp = compressed_multiplicative_call(bset, fn);
4295
4454
4296
morph = isl_morph_remove_dom_dims(morph, isl_dim_set, 0, orig_nvar);
4297
morph = isl_morph_remove_ran_dims(morph, isl_dim_set, 0, final_nvar);
4455
morph = isl_morph_dom_params(morph);
4456
morph = isl_morph_ran_params(morph);
4298
4457
morph = isl_morph_inverse(morph);
4299
4458
4300
pwqp = isl_pw_qpolynomial_morph(pwqp, morph);
4459
pwqp = isl_pw_qpolynomial_morph_domain(pwqp, morph);
4301
4460
4302
4461
return pwqp;
4303
4462
error:
4401
4560
if (!qp->div)
4402
4561
goto error;
4403
4562
4404
total = isl_dim_total(qp->dim);
4563
total = isl_space_dim(qp->dim, isl_dim_all);
4405
4564
v = isl_vec_alloc(qp->div->ctx, qp->div->n_col - 1);
4406
4565
4407
4566
for (i = 0; i < qp->div->n_row; ++i) {
4518
4677
return NULL;
4519
4678
4520
4679
data.sign = sign;
4521
data.res = isl_pw_qpolynomial_zero(isl_pw_qpolynomial_get_dim(pwqp));
4680
data.res = isl_pw_qpolynomial_zero(isl_pw_qpolynomial_get_space(pwqp));
4522
4681
4523
4682
for (i = 0; i < pwqp->n; ++i) {
4524
4683
if (pwqp->p[i].qp->div->n_row == 0) {
4575
4734
__isl_take isl_qpolynomial *qp)
4576
4735
{
4577
4736
int i, k;
4578
isl_dim *dim;
4737
isl_space *dim;
4579
4738
isl_vec *aff = NULL;
4580
4739
isl_basic_map *bmap = NULL;
4581
4740
unsigned pos;
4589
4748
aff = isl_qpolynomial_extract_affine(qp);
4590
4749
if (!aff)
4591
4750
goto error;
4592
dim = isl_qpolynomial_get_dim(qp);
4593
dim = isl_dim_from_domain(dim);
4594
pos = 1 + isl_dim_offset(dim, isl_dim_out);
4595
dim = isl_dim_add(dim, isl_dim_out, 1);
4751
dim = isl_qpolynomial_get_space(qp);
4752
pos = 1 + isl_space_offset(dim, isl_dim_out);
4596
4753
n_div = qp->div->n_row;
4597
bmap = isl_basic_map_alloc_dim(dim, n_div, 1, 2 * n_div);
4754
bmap = isl_basic_map_alloc_space(dim, n_div, 1, 2 * n_div);
4598
4755
4599
4756
for (i = 0; i < n_div; ++i) {
4600
4757
k = isl_basic_map_alloc_div(bmap);
Loggerhead is a web-based interface for Breezy
Version: 2.0.1