1/* 2 * Copyright 2011 INRIA Saclay 3 * Copyright 2011 Sven Verdoolaege 4 * Copyright 2012-2013 Ecole Normale Superieure 5 * 6 * Use of this software is governed by the MIT license 7 * 8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, 9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, 10 * 91893 Orsay, France 11 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France 12 */ 13 14#include <isl_ctx_private.h> 15#define ISL_DIM_H 16#include <isl_map_private.h> 17#include <isl_union_map_private.h> 18#include <isl_aff_private.h> 19#include <isl_space_private.h> 20#include <isl_local_space_private.h> 21#include <isl_mat_private.h> 22#include <isl/constraint.h> 23#include <isl/seq.h> 24#include <isl/set.h> 25#include <isl_val_private.h> 26#include <isl_config.h> 27 28#undef BASE 29#define BASE aff 30 31#include <isl_list_templ.c> 32 33#undef BASE 34#define BASE pw_aff 35 36#include <isl_list_templ.c> 37 38__isl_give isl_aff *isl_aff_alloc_vec(__isl_take isl_local_space *ls, 39 __isl_take isl_vec *v) 40{ 41 isl_aff *aff; 42 43 if (!ls || !v) 44 goto error; 45 46 aff = isl_calloc_type(v->ctx, struct isl_aff); 47 if (!aff) 48 goto error; 49 50 aff->ref = 1; 51 aff->ls = ls; 52 aff->v = v; 53 54 return aff; 55error: 56 isl_local_space_free(ls); 57 isl_vec_free(v); 58 return NULL; 59} 60 61__isl_give isl_aff *isl_aff_alloc(__isl_take isl_local_space *ls) 62{ 63 isl_ctx *ctx; 64 isl_vec *v; 65 unsigned total; 66 67 if (!ls) 68 return NULL; 69 70 ctx = isl_local_space_get_ctx(ls); 71 if (!isl_local_space_divs_known(ls)) 72 isl_die(ctx, isl_error_invalid, "local space has unknown divs", 73 goto error); 74 if (!isl_local_space_is_set(ls)) 75 isl_die(ctx, isl_error_invalid, 76 "domain of affine expression should be a set", 77 goto error); 78 79 total = isl_local_space_dim(ls, isl_dim_all); 80 v = isl_vec_alloc(ctx, 1 + 1 + total); 81 return isl_aff_alloc_vec(ls, v); 82error: 83 isl_local_space_free(ls); 84 return NULL; 85} 86 87__isl_give isl_aff *isl_aff_zero_on_domain(__isl_take isl_local_space *ls) 88{ 89 isl_aff *aff; 90 91 aff = isl_aff_alloc(ls); 92 if (!aff) 93 return NULL; 94 95 isl_int_set_si(aff->v->el[0], 1); 96 isl_seq_clr(aff->v->el + 1, aff->v->size - 1); 97 98 return aff; 99} 100 101/* Return a piecewise affine expression defined on the specified domain 102 * that is equal to zero. 103 */ 104__isl_give isl_pw_aff *isl_pw_aff_zero_on_domain(__isl_take isl_local_space *ls) 105{ 106 return isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls)); 107} 108 109/* Return an affine expression that is equal to the specified dimension 110 * in "ls". 111 */ 112__isl_give isl_aff *isl_aff_var_on_domain(__isl_take isl_local_space *ls, 113 enum isl_dim_type type, unsigned pos) 114{ 115 isl_space *space; 116 isl_aff *aff; 117 118 if (!ls) 119 return NULL; 120 121 space = isl_local_space_get_space(ls); 122 if (!space) 123 goto error; 124 if (isl_space_is_map(space)) 125 isl_die(isl_space_get_ctx(space), isl_error_invalid, 126 "expecting (parameter) set space", goto error); 127 if (pos >= isl_local_space_dim(ls, type)) 128 isl_die(isl_space_get_ctx(space), isl_error_invalid, 129 "position out of bounds", goto error); 130 131 isl_space_free(space); 132 aff = isl_aff_alloc(ls); 133 if (!aff) 134 return NULL; 135 136 pos += isl_local_space_offset(aff->ls, type); 137 138 isl_int_set_si(aff->v->el[0], 1); 139 isl_seq_clr(aff->v->el + 1, aff->v->size - 1); 140 isl_int_set_si(aff->v->el[1 + pos], 1); 141 142 return aff; 143error: 144 isl_local_space_free(ls); 145 isl_space_free(space); 146 return NULL; 147} 148 149/* Return a piecewise affine expression that is equal to 150 * the specified dimension in "ls". 151 */ 152__isl_give isl_pw_aff *isl_pw_aff_var_on_domain(__isl_take isl_local_space *ls, 153 enum isl_dim_type type, unsigned pos) 154{ 155 return isl_pw_aff_from_aff(isl_aff_var_on_domain(ls, type, pos)); 156} 157 158__isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff) 159{ 160 if (!aff) 161 return NULL; 162 163 aff->ref++; 164 return aff; 165} 166 167__isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff) 168{ 169 if (!aff) 170 return NULL; 171 172 return isl_aff_alloc_vec(isl_local_space_copy(aff->ls), 173 isl_vec_copy(aff->v)); 174} 175 176__isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff) 177{ 178 if (!aff) 179 return NULL; 180 181 if (aff->ref == 1) 182 return aff; 183 aff->ref--; 184 return isl_aff_dup(aff); 185} 186 187void *isl_aff_free(__isl_take isl_aff *aff) 188{ 189 if (!aff) 190 return NULL; 191 192 if (--aff->ref > 0) 193 return NULL; 194 195 isl_local_space_free(aff->ls); 196 isl_vec_free(aff->v); 197 198 free(aff); 199 200 return NULL; 201} 202 203isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff) 204{ 205 return aff ? isl_local_space_get_ctx(aff->ls) : NULL; 206} 207 208/* Externally, an isl_aff has a map space, but internally, the 209 * ls field corresponds to the domain of that space. 210 */ 211int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type) 212{ 213 if (!aff) 214 return 0; 215 if (type == isl_dim_out) 216 return 1; 217 if (type == isl_dim_in) 218 type = isl_dim_set; 219 return isl_local_space_dim(aff->ls, type); 220} 221 222__isl_give isl_space *isl_aff_get_domain_space(__isl_keep isl_aff *aff) 223{ 224 return aff ? isl_local_space_get_space(aff->ls) : NULL; 225} 226 227__isl_give isl_space *isl_aff_get_space(__isl_keep isl_aff *aff) 228{ 229 isl_space *space; 230 if (!aff) 231 return NULL; 232 space = isl_local_space_get_space(aff->ls); 233 space = isl_space_from_domain(space); 234 space = isl_space_add_dims(space, isl_dim_out, 1); 235 return space; 236} 237 238__isl_give isl_local_space *isl_aff_get_domain_local_space( 239 __isl_keep isl_aff *aff) 240{ 241 return aff ? isl_local_space_copy(aff->ls) : NULL; 242} 243 244__isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff) 245{ 246 isl_local_space *ls; 247 if (!aff) 248 return NULL; 249 ls = isl_local_space_copy(aff->ls); 250 ls = isl_local_space_from_domain(ls); 251 ls = isl_local_space_add_dims(ls, isl_dim_out, 1); 252 return ls; 253} 254 255/* Externally, an isl_aff has a map space, but internally, the 256 * ls field corresponds to the domain of that space. 257 */ 258const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff, 259 enum isl_dim_type type, unsigned pos) 260{ 261 if (!aff) 262 return NULL; 263 if (type == isl_dim_out) 264 return NULL; 265 if (type == isl_dim_in) 266 type = isl_dim_set; 267 return isl_local_space_get_dim_name(aff->ls, type, pos); 268} 269 270__isl_give isl_aff *isl_aff_reset_domain_space(__isl_take isl_aff *aff, 271 __isl_take isl_space *dim) 272{ 273 aff = isl_aff_cow(aff); 274 if (!aff || !dim) 275 goto error; 276 277 aff->ls = isl_local_space_reset_space(aff->ls, dim); 278 if (!aff->ls) 279 return isl_aff_free(aff); 280 281 return aff; 282error: 283 isl_aff_free(aff); 284 isl_space_free(dim); 285 return NULL; 286} 287 288/* Reset the space of "aff". This function is called from isl_pw_templ.c 289 * and doesn't know if the space of an element object is represented 290 * directly or through its domain. It therefore passes along both. 291 */ 292__isl_give isl_aff *isl_aff_reset_space_and_domain(__isl_take isl_aff *aff, 293 __isl_take isl_space *space, __isl_take isl_space *domain) 294{ 295 isl_space_free(space); 296 return isl_aff_reset_domain_space(aff, domain); 297} 298 299/* Reorder the coefficients of the affine expression based 300 * on the given reodering. 301 * The reordering r is assumed to have been extended with the local 302 * variables. 303 */ 304static __isl_give isl_vec *vec_reorder(__isl_take isl_vec *vec, 305 __isl_take isl_reordering *r, int n_div) 306{ 307 isl_vec *res; 308 int i; 309 310 if (!vec || !r) 311 goto error; 312 313 res = isl_vec_alloc(vec->ctx, 314 2 + isl_space_dim(r->dim, isl_dim_all) + n_div); 315 isl_seq_cpy(res->el, vec->el, 2); 316 isl_seq_clr(res->el + 2, res->size - 2); 317 for (i = 0; i < r->len; ++i) 318 isl_int_set(res->el[2 + r->pos[i]], vec->el[2 + i]); 319 320 isl_reordering_free(r); 321 isl_vec_free(vec); 322 return res; 323error: 324 isl_vec_free(vec); 325 isl_reordering_free(r); 326 return NULL; 327} 328 329/* Reorder the dimensions of the domain of "aff" according 330 * to the given reordering. 331 */ 332__isl_give isl_aff *isl_aff_realign_domain(__isl_take isl_aff *aff, 333 __isl_take isl_reordering *r) 334{ 335 aff = isl_aff_cow(aff); 336 if (!aff) 337 goto error; 338 339 r = isl_reordering_extend(r, aff->ls->div->n_row); 340 aff->v = vec_reorder(aff->v, isl_reordering_copy(r), 341 aff->ls->div->n_row); 342 aff->ls = isl_local_space_realign(aff->ls, r); 343 344 if (!aff->v || !aff->ls) 345 return isl_aff_free(aff); 346 347 return aff; 348error: 349 isl_aff_free(aff); 350 isl_reordering_free(r); 351 return NULL; 352} 353 354__isl_give isl_aff *isl_aff_align_params(__isl_take isl_aff *aff, 355 __isl_take isl_space *model) 356{ 357 if (!aff || !model) 358 goto error; 359 360 if (!isl_space_match(aff->ls->dim, isl_dim_param, 361 model, isl_dim_param)) { 362 isl_reordering *exp; 363 364 model = isl_space_drop_dims(model, isl_dim_in, 365 0, isl_space_dim(model, isl_dim_in)); 366 model = isl_space_drop_dims(model, isl_dim_out, 367 0, isl_space_dim(model, isl_dim_out)); 368 exp = isl_parameter_alignment_reordering(aff->ls->dim, model); 369 exp = isl_reordering_extend_space(exp, 370 isl_aff_get_domain_space(aff)); 371 aff = isl_aff_realign_domain(aff, exp); 372 } 373 374 isl_space_free(model); 375 return aff; 376error: 377 isl_space_free(model); 378 isl_aff_free(aff); 379 return NULL; 380} 381 382int isl_aff_plain_is_zero(__isl_keep isl_aff *aff) 383{ 384 if (!aff) 385 return -1; 386 387 return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0; 388} 389 390int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2) 391{ 392 int equal; 393 394 if (!aff1 || !aff2) 395 return -1; 396 397 equal = isl_local_space_is_equal(aff1->ls, aff2->ls); 398 if (equal < 0 || !equal) 399 return equal; 400 401 return isl_vec_is_equal(aff1->v, aff2->v); 402} 403 404int isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v) 405{ 406 if (!aff) 407 return -1; 408 isl_int_set(*v, aff->v->el[0]); 409 return 0; 410} 411 412/* Return the common denominator of "aff". 413 */ 414__isl_give isl_val *isl_aff_get_denominator_val(__isl_keep isl_aff *aff) 415{ 416 isl_ctx *ctx; 417 418 if (!aff) 419 return NULL; 420 421 ctx = isl_aff_get_ctx(aff); 422 return isl_val_int_from_isl_int(ctx, aff->v->el[0]); 423} 424 425int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v) 426{ 427 if (!aff) 428 return -1; 429 isl_int_set(*v, aff->v->el[1]); 430 return 0; 431} 432 433/* Return the constant term of "aff". 434 */ 435__isl_give isl_val *isl_aff_get_constant_val(__isl_keep isl_aff *aff) 436{ 437 isl_ctx *ctx; 438 isl_val *v; 439 440 if (!aff) 441 return NULL; 442 443 ctx = isl_aff_get_ctx(aff); 444 v = isl_val_rat_from_isl_int(ctx, aff->v->el[1], aff->v->el[0]); 445 return isl_val_normalize(v); 446} 447 448int isl_aff_get_coefficient(__isl_keep isl_aff *aff, 449 enum isl_dim_type type, int pos, isl_int *v) 450{ 451 if (!aff) 452 return -1; 453 454 if (type == isl_dim_out) 455 isl_die(aff->v->ctx, isl_error_invalid, 456 "output/set dimension does not have a coefficient", 457 return -1); 458 if (type == isl_dim_in) 459 type = isl_dim_set; 460 461 if (pos >= isl_local_space_dim(aff->ls, type)) 462 isl_die(aff->v->ctx, isl_error_invalid, 463 "position out of bounds", return -1); 464 465 pos += isl_local_space_offset(aff->ls, type); 466 isl_int_set(*v, aff->v->el[1 + pos]); 467 468 return 0; 469} 470 471/* Return the coefficient of the variable of type "type" at position "pos" 472 * of "aff". 473 */ 474__isl_give isl_val *isl_aff_get_coefficient_val(__isl_keep isl_aff *aff, 475 enum isl_dim_type type, int pos) 476{ 477 isl_ctx *ctx; 478 isl_val *v; 479 480 if (!aff) 481 return NULL; 482 483 ctx = isl_aff_get_ctx(aff); 484 if (type == isl_dim_out) 485 isl_die(ctx, isl_error_invalid, 486 "output/set dimension does not have a coefficient", 487 return NULL); 488 if (type == isl_dim_in) 489 type = isl_dim_set; 490 491 if (pos >= isl_local_space_dim(aff->ls, type)) 492 isl_die(ctx, isl_error_invalid, 493 "position out of bounds", return NULL); 494 495 pos += isl_local_space_offset(aff->ls, type); 496 v = isl_val_rat_from_isl_int(ctx, aff->v->el[1 + pos], aff->v->el[0]); 497 return isl_val_normalize(v); 498} 499 500__isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v) 501{ 502 aff = isl_aff_cow(aff); 503 if (!aff) 504 return NULL; 505 506 aff->v = isl_vec_cow(aff->v); 507 if (!aff->v) 508 return isl_aff_free(aff); 509 510 isl_int_set(aff->v->el[0], v); 511 512 return aff; 513} 514 515__isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v) 516{ 517 aff = isl_aff_cow(aff); 518 if (!aff) 519 return NULL; 520 521 aff->v = isl_vec_cow(aff->v); 522 if (!aff->v) 523 return isl_aff_free(aff); 524 525 isl_int_set(aff->v->el[1], v); 526 527 return aff; 528} 529 530/* Replace the constant term of "aff" by "v". 531 */ 532__isl_give isl_aff *isl_aff_set_constant_val(__isl_take isl_aff *aff, 533 __isl_take isl_val *v) 534{ 535 if (!aff || !v) 536 goto error; 537 538 if (!isl_val_is_rat(v)) 539 isl_die(isl_aff_get_ctx(aff), isl_error_invalid, 540 "expecting rational value", goto error); 541 542 if (isl_int_eq(aff->v->el[1], v->n) && 543 isl_int_eq(aff->v->el[0], v->d)) { 544 isl_val_free(v); 545 return aff; 546 } 547 548 aff = isl_aff_cow(aff); 549 if (!aff) 550 goto error; 551 aff->v = isl_vec_cow(aff->v); 552 if (!aff->v) 553 goto error; 554 555 if (isl_int_eq(aff->v->el[0], v->d)) { 556 isl_int_set(aff->v->el[1], v->n); 557 } else if (isl_int_is_one(v->d)) { 558 isl_int_mul(aff->v->el[1], aff->v->el[0], v->n); 559 } else { 560 isl_seq_scale(aff->v->el + 1, 561 aff->v->el + 1, v->d, aff->v->size - 1); 562 isl_int_mul(aff->v->el[1], aff->v->el[0], v->n); 563 isl_int_mul(aff->v->el[0], aff->v->el[0], v->d); 564 aff->v = isl_vec_normalize(aff->v); 565 if (!aff->v) 566 goto error; 567 } 568 569 isl_val_free(v); 570 return aff; 571error: 572 isl_aff_free(aff); 573 isl_val_free(v); 574 return NULL; 575} 576 577__isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v) 578{ 579 if (isl_int_is_zero(v)) 580 return aff; 581 582 aff = isl_aff_cow(aff); 583 if (!aff) 584 return NULL; 585 586 aff->v = isl_vec_cow(aff->v); 587 if (!aff->v) 588 return isl_aff_free(aff); 589 590 isl_int_addmul(aff->v->el[1], aff->v->el[0], v); 591 592 return aff; 593} 594 595/* Add "v" to the constant term of "aff". 596 */ 597__isl_give isl_aff *isl_aff_add_constant_val(__isl_take isl_aff *aff, 598 __isl_take isl_val *v) 599{ 600 if (!aff || !v) 601 goto error; 602 603 if (isl_val_is_zero(v)) { 604 isl_val_free(v); 605 return aff; 606 } 607 608 if (!isl_val_is_rat(v)) 609 isl_die(isl_aff_get_ctx(aff), isl_error_invalid, 610 "expecting rational value", goto error); 611 612 aff = isl_aff_cow(aff); 613 if (!aff) 614 goto error; 615 616 aff->v = isl_vec_cow(aff->v); 617 if (!aff->v) 618 goto error; 619 620 if (isl_int_is_one(v->d)) { 621 isl_int_addmul(aff->v->el[1], aff->v->el[0], v->n); 622 } else if (isl_int_eq(aff->v->el[0], v->d)) { 623 isl_int_add(aff->v->el[1], aff->v->el[1], v->n); 624 aff->v = isl_vec_normalize(aff->v); 625 if (!aff->v) 626 goto error; 627 } else { 628 isl_seq_scale(aff->v->el + 1, 629 aff->v->el + 1, v->d, aff->v->size - 1); 630 isl_int_addmul(aff->v->el[1], aff->v->el[0], v->n); 631 isl_int_mul(aff->v->el[0], aff->v->el[0], v->d); 632 aff->v = isl_vec_normalize(aff->v); 633 if (!aff->v) 634 goto error; 635 } 636 637 isl_val_free(v); 638 return aff; 639error: 640 isl_aff_free(aff); 641 isl_val_free(v); 642 return NULL; 643} 644 645__isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v) 646{ 647 isl_int t; 648 649 isl_int_init(t); 650 isl_int_set_si(t, v); 651 aff = isl_aff_add_constant(aff, t); 652 isl_int_clear(t); 653 654 return aff; 655} 656 657/* Add "v" to the numerator of the constant term of "aff". 658 */ 659__isl_give isl_aff *isl_aff_add_constant_num(__isl_take isl_aff *aff, isl_int v) 660{ 661 if (isl_int_is_zero(v)) 662 return aff; 663 664 aff = isl_aff_cow(aff); 665 if (!aff) 666 return NULL; 667 668 aff->v = isl_vec_cow(aff->v); 669 if (!aff->v) 670 return isl_aff_free(aff); 671 672 isl_int_add(aff->v->el[1], aff->v->el[1], v); 673 674 return aff; 675} 676 677/* Add "v" to the numerator of the constant term of "aff". 678 */ 679__isl_give isl_aff *isl_aff_add_constant_num_si(__isl_take isl_aff *aff, int v) 680{ 681 isl_int t; 682 683 if (v == 0) 684 return aff; 685 686 isl_int_init(t); 687 isl_int_set_si(t, v); 688 aff = isl_aff_add_constant_num(aff, t); 689 isl_int_clear(t); 690 691 return aff; 692} 693 694__isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v) 695{ 696 aff = isl_aff_cow(aff); 697 if (!aff) 698 return NULL; 699 700 aff->v = isl_vec_cow(aff->v); 701 if (!aff->v) 702 return isl_aff_free(aff); 703 704 isl_int_set_si(aff->v->el[1], v); 705 706 return aff; 707} 708 709__isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff, 710 enum isl_dim_type type, int pos, isl_int v) 711{ 712 if (!aff) 713 return NULL; 714 715 if (type == isl_dim_out) 716 isl_die(aff->v->ctx, isl_error_invalid, 717 "output/set dimension does not have a coefficient", 718 return isl_aff_free(aff)); 719 if (type == isl_dim_in) 720 type = isl_dim_set; 721 722 if (pos >= isl_local_space_dim(aff->ls, type)) 723 isl_die(aff->v->ctx, isl_error_invalid, 724 "position out of bounds", return isl_aff_free(aff)); 725 726 aff = isl_aff_cow(aff); 727 if (!aff) 728 return NULL; 729 730 aff->v = isl_vec_cow(aff->v); 731 if (!aff->v) 732 return isl_aff_free(aff); 733 734 pos += isl_local_space_offset(aff->ls, type); 735 isl_int_set(aff->v->el[1 + pos], v); 736 737 return aff; 738} 739 740__isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff, 741 enum isl_dim_type type, int pos, int v) 742{ 743 if (!aff) 744 return NULL; 745 746 if (type == isl_dim_out) 747 isl_die(aff->v->ctx, isl_error_invalid, 748 "output/set dimension does not have a coefficient", 749 return isl_aff_free(aff)); 750 if (type == isl_dim_in) 751 type = isl_dim_set; 752 753 if (pos >= isl_local_space_dim(aff->ls, type)) 754 isl_die(aff->v->ctx, isl_error_invalid, 755 "position out of bounds", return isl_aff_free(aff)); 756 757 aff = isl_aff_cow(aff); 758 if (!aff) 759 return NULL; 760 761 aff->v = isl_vec_cow(aff->v); 762 if (!aff->v) 763 return isl_aff_free(aff); 764 765 pos += isl_local_space_offset(aff->ls, type); 766 isl_int_set_si(aff->v->el[1 + pos], v); 767 768 return aff; 769} 770 771/* Replace the coefficient of the variable of type "type" at position "pos" 772 * of "aff" by "v". 773 */ 774__isl_give isl_aff *isl_aff_set_coefficient_val(__isl_take isl_aff *aff, 775 enum isl_dim_type type, int pos, __isl_take isl_val *v) 776{ 777 if (!aff || !v) 778 goto error; 779 780 if (type == isl_dim_out) 781 isl_die(aff->v->ctx, isl_error_invalid, 782 "output/set dimension does not have a coefficient", 783 goto error); 784 if (type == isl_dim_in) 785 type = isl_dim_set; 786 787 if (pos >= isl_local_space_dim(aff->ls, type)) 788 isl_die(aff->v->ctx, isl_error_invalid, 789 "position out of bounds", goto error); 790 791 if (!isl_val_is_rat(v)) 792 isl_die(isl_aff_get_ctx(aff), isl_error_invalid, 793 "expecting rational value", goto error); 794 795 pos += isl_local_space_offset(aff->ls, type); 796 if (isl_int_eq(aff->v->el[1 + pos], v->n) && 797 isl_int_eq(aff->v->el[0], v->d)) { 798 isl_val_free(v); 799 return aff; 800 } 801 802 aff = isl_aff_cow(aff); 803 if (!aff) 804 goto error; 805 aff->v = isl_vec_cow(aff->v); 806 if (!aff->v) 807 goto error; 808 809 if (isl_int_eq(aff->v->el[0], v->d)) { 810 isl_int_set(aff->v->el[1 + pos], v->n); 811 } else if (isl_int_is_one(v->d)) { 812 isl_int_mul(aff->v->el[1 + pos], aff->v->el[0], v->n); 813 } else { 814 isl_seq_scale(aff->v->el + 1, 815 aff->v->el + 1, v->d, aff->v->size - 1); 816 isl_int_mul(aff->v->el[1 + pos], aff->v->el[0], v->n); 817 isl_int_mul(aff->v->el[0], aff->v->el[0], v->d); 818 aff->v = isl_vec_normalize(aff->v); 819 if (!aff->v) 820 goto error; 821 } 822 823 isl_val_free(v); 824 return aff; 825error: 826 isl_aff_free(aff); 827 isl_val_free(v); 828 return NULL; 829} 830 831__isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff, 832 enum isl_dim_type type, int pos, isl_int v) 833{ 834 if (!aff) 835 return NULL; 836 837 if (type == isl_dim_out) 838 isl_die(aff->v->ctx, isl_error_invalid, 839 "output/set dimension does not have a coefficient", 840 return isl_aff_free(aff)); 841 if (type == isl_dim_in) 842 type = isl_dim_set; 843 844 if (pos >= isl_local_space_dim(aff->ls, type)) 845 isl_die(aff->v->ctx, isl_error_invalid, 846 "position out of bounds", return isl_aff_free(aff)); 847 848 aff = isl_aff_cow(aff); 849 if (!aff) 850 return NULL; 851 852 aff->v = isl_vec_cow(aff->v); 853 if (!aff->v) 854 return isl_aff_free(aff); 855 856 pos += isl_local_space_offset(aff->ls, type); 857 isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v); 858 859 return aff; 860} 861 862/* Add "v" to the coefficient of the variable of type "type" 863 * at position "pos" of "aff". 864 */ 865__isl_give isl_aff *isl_aff_add_coefficient_val(__isl_take isl_aff *aff, 866 enum isl_dim_type type, int pos, __isl_take isl_val *v) 867{ 868 if (!aff || !v) 869 goto error; 870 871 if (isl_val_is_zero(v)) { 872 isl_val_free(v); 873 return aff; 874 } 875 876 if (type == isl_dim_out) 877 isl_die(aff->v->ctx, isl_error_invalid, 878 "output/set dimension does not have a coefficient", 879 goto error); 880 if (type == isl_dim_in) 881 type = isl_dim_set; 882 883 if (pos >= isl_local_space_dim(aff->ls, type)) 884 isl_die(aff->v->ctx, isl_error_invalid, 885 "position out of bounds", goto error); 886 887 if (!isl_val_is_rat(v)) 888 isl_die(isl_aff_get_ctx(aff), isl_error_invalid, 889 "expecting rational value", goto error); 890 891 aff = isl_aff_cow(aff); 892 if (!aff) 893 goto error; 894 895 aff->v = isl_vec_cow(aff->v); 896 if (!aff->v) 897 goto error; 898 899 pos += isl_local_space_offset(aff->ls, type); 900 if (isl_int_is_one(v->d)) { 901 isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v->n); 902 } else if (isl_int_eq(aff->v->el[0], v->d)) { 903 isl_int_add(aff->v->el[1 + pos], aff->v->el[1 + pos], v->n); 904 aff->v = isl_vec_normalize(aff->v); 905 if (!aff->v) 906 goto error; 907 } else { 908 isl_seq_scale(aff->v->el + 1, 909 aff->v->el + 1, v->d, aff->v->size - 1); 910 isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v->n); 911 isl_int_mul(aff->v->el[0], aff->v->el[0], v->d); 912 aff->v = isl_vec_normalize(aff->v); 913 if (!aff->v) 914 goto error; 915 } 916 917 isl_val_free(v); 918 return aff; 919error: 920 isl_aff_free(aff); 921 isl_val_free(v); 922 return NULL; 923} 924 925__isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff, 926 enum isl_dim_type type, int pos, int v) 927{ 928 isl_int t; 929 930 isl_int_init(t); 931 isl_int_set_si(t, v); 932 aff = isl_aff_add_coefficient(aff, type, pos, t); 933 isl_int_clear(t); 934 935 return aff; 936} 937 938__isl_give isl_aff *isl_aff_get_div(__isl_keep isl_aff *aff, int pos) 939{ 940 if (!aff) 941 return NULL; 942 943 return isl_local_space_get_div(aff->ls, pos); 944} 945 946__isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff) 947{ 948 aff = isl_aff_cow(aff); 949 if (!aff) 950 return NULL; 951 aff->v = isl_vec_cow(aff->v); 952 if (!aff->v) 953 return isl_aff_free(aff); 954 955 isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1); 956 957 return aff; 958} 959 960/* Remove divs from the local space that do not appear in the affine 961 * expression. 962 * We currently only remove divs at the end. 963 * Some intermediate divs may also not appear directly in the affine 964 * expression, but we would also need to check that no other divs are 965 * defined in terms of them. 966 */ 967__isl_give isl_aff *isl_aff_remove_unused_divs( __isl_take isl_aff *aff) 968{ 969 int pos; 970 int off; 971 int n; 972 973 if (!aff) 974 return NULL; 975 976 n = isl_local_space_dim(aff->ls, isl_dim_div); 977 off = isl_local_space_offset(aff->ls, isl_dim_div); 978 979 pos = isl_seq_last_non_zero(aff->v->el + 1 + off, n) + 1; 980 if (pos == n) 981 return aff; 982 983 aff = isl_aff_cow(aff); 984 if (!aff) 985 return NULL; 986 987 aff->ls = isl_local_space_drop_dims(aff->ls, isl_dim_div, pos, n - pos); 988 aff->v = isl_vec_drop_els(aff->v, 1 + off + pos, n - pos); 989 if (!aff->ls || !aff->v) 990 return isl_aff_free(aff); 991 992 return aff; 993} 994 995/* Given two affine expressions "p" of length p_len (including the 996 * denominator and the constant term) and "subs" of length subs_len, 997 * plug in "subs" for the variable at position "pos". 998 * The variables of "subs" and "p" are assumed to match up to subs_len, 999 * but "p" may have additional variables. 1000 * "v" is an initialized isl_int that can be used internally. 1001 * 1002 * In particular, if "p" represents the expression 1003 * 1004 * (a i + g)/m 1005 * 1006 * with i the variable at position "pos" and "subs" represents the expression 1007 * 1008 * f/d 1009 * 1010 * then the result represents the expression 1011 * 1012 * (a f + d g)/(m d) 1013 * 1014 */ 1015void isl_seq_substitute(isl_int *p, int pos, isl_int *subs, 1016 int p_len, int subs_len, isl_int v) 1017{ 1018 isl_int_set(v, p[1 + pos]); 1019 isl_int_set_si(p[1 + pos], 0); 1020 isl_seq_combine(p + 1, subs[0], p + 1, v, subs + 1, subs_len - 1); 1021 isl_seq_scale(p + subs_len, p + subs_len, subs[0], p_len - subs_len); 1022 isl_int_mul(p[0], p[0], subs[0]); 1023} 1024 1025/* Look for any divs in the aff->ls with a denominator equal to one 1026 * and plug them into the affine expression and any subsequent divs 1027 * that may reference the div. 1028 */ 1029static __isl_give isl_aff *plug_in_integral_divs(__isl_take isl_aff *aff) 1030{ 1031 int i, n; 1032 int len; 1033 isl_int v; 1034 isl_vec *vec; 1035 isl_local_space *ls; 1036 unsigned pos; 1037 1038 if (!aff) 1039 return NULL; 1040 1041 n = isl_local_space_dim(aff->ls, isl_dim_div); 1042 len = aff->v->size; 1043 for (i = 0; i < n; ++i) { 1044 if (!isl_int_is_one(aff->ls->div->row[i][0])) 1045 continue; 1046 ls = isl_local_space_copy(aff->ls); 1047 ls = isl_local_space_substitute_seq(ls, isl_dim_div, i, 1048 aff->ls->div->row[i], len, i + 1, n - (i + 1)); 1049 vec = isl_vec_copy(aff->v); 1050 vec = isl_vec_cow(vec); 1051 if (!ls || !vec) 1052 goto error; 1053 1054 isl_int_init(v); 1055 1056 pos = isl_local_space_offset(aff->ls, isl_dim_div) + i; 1057 isl_seq_substitute(vec->el, pos, aff->ls->div->row[i], 1058 len, len, v); 1059 1060 isl_int_clear(v); 1061 1062 isl_vec_free(aff->v); 1063 aff->v = vec; 1064 isl_local_space_free(aff->ls); 1065 aff->ls = ls; 1066 } 1067 1068 return aff; 1069error: 1070 isl_vec_free(vec); 1071 isl_local_space_free(ls); 1072 return isl_aff_free(aff); 1073} 1074 1075/* Look for any divs j that appear with a unit coefficient inside 1076 * the definitions of other divs i and plug them into the definitions 1077 * of the divs i. 1078 * 1079 * In particular, an expression of the form 1080 * 1081 * floor((f(..) + floor(g(..)/n))/m) 1082 * 1083 * is simplified to 1084 * 1085 * floor((n * f(..) + g(..))/(n * m)) 1086 * 1087 * This simplification is correct because we can move the expression 1088 * f(..) into the inner floor in the original expression to obtain 1089 * 1090 * floor(floor((n * f(..) + g(..))/n)/m) 1091 * 1092 * from which we can derive the simplified expression. 1093 */ 1094static __isl_give isl_aff *plug_in_unit_divs(__isl_take isl_aff *aff) 1095{ 1096 int i, j, n; 1097 int off; 1098 1099 if (!aff) 1100 return NULL; 1101 1102 n = isl_local_space_dim(aff->ls, isl_dim_div); 1103 off = isl_local_space_offset(aff->ls, isl_dim_div); 1104 for (i = 1; i < n; ++i) { 1105 for (j = 0; j < i; ++j) { 1106 if (!isl_int_is_one(aff->ls->div->row[i][1 + off + j])) 1107 continue; 1108 aff->ls = isl_local_space_substitute_seq(aff->ls, 1109 isl_dim_div, j, aff->ls->div->row[j], 1110 aff->v->size, i, 1); 1111 if (!aff->ls) 1112 return isl_aff_free(aff); 1113 } 1114 } 1115 1116 return aff; 1117} 1118 1119/* Swap divs "a" and "b" in "aff", which is assumed to be non-NULL. 1120 * 1121 * Even though this function is only called on isl_affs with a single 1122 * reference, we are careful to only change aff->v and aff->ls together. 1123 */ 1124static __isl_give isl_aff *swap_div(__isl_take isl_aff *aff, int a, int b) 1125{ 1126 unsigned off = isl_local_space_offset(aff->ls, isl_dim_div); 1127 isl_local_space *ls; 1128 isl_vec *v; 1129 1130 ls = isl_local_space_copy(aff->ls); 1131 ls = isl_local_space_swap_div(ls, a, b); 1132 v = isl_vec_copy(aff->v); 1133 v = isl_vec_cow(v); 1134 if (!ls || !v) 1135 goto error; 1136 1137 isl_int_swap(v->el[1 + off + a], v->el[1 + off + b]); 1138 isl_vec_free(aff->v); 1139 aff->v = v; 1140 isl_local_space_free(aff->ls); 1141 aff->ls = ls; 1142 1143 return aff; 1144error: 1145 isl_vec_free(v); 1146 isl_local_space_free(ls); 1147 return isl_aff_free(aff); 1148} 1149 1150/* Merge divs "a" and "b" in "aff", which is assumed to be non-NULL. 1151 * 1152 * We currently do not actually remove div "b", but simply add its 1153 * coefficient to that of "a" and then zero it out. 1154 */ 1155static __isl_give isl_aff *merge_divs(__isl_take isl_aff *aff, int a, int b) 1156{ 1157 unsigned off = isl_local_space_offset(aff->ls, isl_dim_div); 1158 1159 if (isl_int_is_zero(aff->v->el[1 + off + b])) 1160 return aff; 1161 1162 aff->v = isl_vec_cow(aff->v); 1163 if (!aff->v) 1164 return isl_aff_free(aff); 1165 1166 isl_int_add(aff->v->el[1 + off + a], 1167 aff->v->el[1 + off + a], aff->v->el[1 + off + b]); 1168 isl_int_set_si(aff->v->el[1 + off + b], 0); 1169 1170 return aff; 1171} 1172 1173/* Sort the divs in the local space of "aff" according to 1174 * the comparison function "cmp_row" in isl_local_space.c, 1175 * combining the coefficients of identical divs. 1176 * 1177 * Reordering divs does not change the semantics of "aff", 1178 * so there is no need to call isl_aff_cow. 1179 * Moreover, this function is currently only called on isl_affs 1180 * with a single reference. 1181 */ 1182static __isl_give isl_aff *sort_divs(__isl_take isl_aff *aff) 1183{ 1184 int i, j, n; 1185 unsigned off; 1186 1187 if (!aff) 1188 return NULL; 1189 1190 off = isl_local_space_offset(aff->ls, isl_dim_div); 1191 n = isl_aff_dim(aff, isl_dim_div); 1192 for (i = 1; i < n; ++i) { 1193 for (j = i - 1; j >= 0; --j) { 1194 int cmp = isl_mat_cmp_div(aff->ls->div, j, j + 1); 1195 if (cmp < 0) 1196 break; 1197 if (cmp == 0) 1198 aff = merge_divs(aff, j, j + 1); 1199 else 1200 aff = swap_div(aff, j, j + 1); 1201 if (!aff) 1202 return NULL; 1203 } 1204 } 1205 1206 return aff; 1207} 1208 1209/* Normalize the representation of "aff". 1210 * 1211 * This function should only be called of "new" isl_affs, i.e., 1212 * with only a single reference. We therefore do not need to 1213 * worry about affecting other instances. 1214 */ 1215__isl_give isl_aff *isl_aff_normalize(__isl_take isl_aff *aff) 1216{ 1217 if (!aff) 1218 return NULL; 1219 aff->v = isl_vec_normalize(aff->v); 1220 if (!aff->v) 1221 return isl_aff_free(aff); 1222 aff = plug_in_integral_divs(aff); 1223 aff = plug_in_unit_divs(aff); 1224 aff = sort_divs(aff); 1225 aff = isl_aff_remove_unused_divs(aff); 1226 return aff; 1227} 1228 1229/* Given f, return floor(f). 1230 * If f is an integer expression, then just return f. 1231 * If f is a constant, then return the constant floor(f). 1232 * Otherwise, if f = g/m, write g = q m + r, 1233 * create a new div d = [r/m] and return the expression q + d. 1234 * The coefficients in r are taken to lie between -m/2 and m/2. 1235 */ 1236__isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff) 1237{ 1238 int i; 1239 int size; 1240 isl_ctx *ctx; 1241 isl_vec *div; 1242 1243 if (!aff) 1244 return NULL; 1245 1246 if (isl_int_is_one(aff->v->el[0])) 1247 return aff; 1248 1249 aff = isl_aff_cow(aff); 1250 if (!aff) 1251 return NULL; 1252 1253 aff->v = isl_vec_cow(aff->v); 1254 if (!aff->v) 1255 return isl_aff_free(aff); 1256 1257 if (isl_aff_is_cst(aff)) { 1258 isl_int_fdiv_q(aff->v->el[1], aff->v->el[1], aff->v->el[0]); 1259 isl_int_set_si(aff->v->el[0], 1); 1260 return aff; 1261 } 1262 1263 div = isl_vec_copy(aff->v); 1264 div = isl_vec_cow(div); 1265 if (!div) 1266 return isl_aff_free(aff); 1267 1268 ctx = isl_aff_get_ctx(aff); 1269 isl_int_fdiv_q(aff->v->el[0], aff->v->el[0], ctx->two); 1270 for (i = 1; i < aff->v->size; ++i) { 1271 isl_int_fdiv_r(div->el[i], div->el[i], div->el[0]); 1272 isl_int_fdiv_q(aff->v->el[i], aff->v->el[i], div->el[0]); 1273 if (isl_int_gt(div->el[i], aff->v->el[0])) { 1274 isl_int_sub(div->el[i], div->el[i], div->el[0]); 1275 isl_int_add_ui(aff->v->el[i], aff->v->el[i], 1); 1276 } 1277 } 1278 1279 aff->ls = isl_local_space_add_div(aff->ls, div); 1280 if (!aff->ls) 1281 return isl_aff_free(aff); 1282 1283 size = aff->v->size; 1284 aff->v = isl_vec_extend(aff->v, size + 1); 1285 if (!aff->v) 1286 return isl_aff_free(aff); 1287 isl_int_set_si(aff->v->el[0], 1); 1288 isl_int_set_si(aff->v->el[size], 1); 1289 1290 aff = isl_aff_normalize(aff); 1291 1292 return aff; 1293} 1294 1295/* Compute 1296 * 1297 * aff mod m = aff - m * floor(aff/m) 1298 */ 1299__isl_give isl_aff *isl_aff_mod(__isl_take isl_aff *aff, isl_int m) 1300{ 1301 isl_aff *res; 1302 1303 res = isl_aff_copy(aff); 1304 aff = isl_aff_scale_down(aff, m); 1305 aff = isl_aff_floor(aff); 1306 aff = isl_aff_scale(aff, m); 1307 res = isl_aff_sub(res, aff); 1308 1309 return res; 1310} 1311 1312/* Compute 1313 * 1314 * aff mod m = aff - m * floor(aff/m) 1315 * 1316 * with m an integer value. 1317 */ 1318__isl_give isl_aff *isl_aff_mod_val(__isl_take isl_aff *aff, 1319 __isl_take isl_val *m) 1320{ 1321 isl_aff *res; 1322 1323 if (!aff || !m) 1324 goto error; 1325 1326 if (!isl_val_is_int(m)) 1327 isl_die(isl_val_get_ctx(m), isl_error_invalid, 1328 "expecting integer modulo", goto error); 1329 1330 res = isl_aff_copy(aff); 1331 aff = isl_aff_scale_down_val(aff, isl_val_copy(m)); 1332 aff = isl_aff_floor(aff); 1333 aff = isl_aff_scale_val(aff, m); 1334 res = isl_aff_sub(res, aff); 1335 1336 return res; 1337error: 1338 isl_aff_free(aff); 1339 isl_val_free(m); 1340 return NULL; 1341} 1342 1343/* Compute 1344 * 1345 * pwaff mod m = pwaff - m * floor(pwaff/m) 1346 */ 1347__isl_give isl_pw_aff *isl_pw_aff_mod(__isl_take isl_pw_aff *pwaff, isl_int m) 1348{ 1349 isl_pw_aff *res; 1350 1351 res = isl_pw_aff_copy(pwaff); 1352 pwaff = isl_pw_aff_scale_down(pwaff, m); 1353 pwaff = isl_pw_aff_floor(pwaff); 1354 pwaff = isl_pw_aff_scale(pwaff, m); 1355 res = isl_pw_aff_sub(res, pwaff); 1356 1357 return res; 1358} 1359 1360/* Compute 1361 * 1362 * pa mod m = pa - m * floor(pa/m) 1363 * 1364 * with m an integer value. 1365 */ 1366__isl_give isl_pw_aff *isl_pw_aff_mod_val(__isl_take isl_pw_aff *pa, 1367 __isl_take isl_val *m) 1368{ 1369 if (!pa || !m) 1370 goto error; 1371 if (!isl_val_is_int(m)) 1372 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid, 1373 "expecting integer modulo", goto error); 1374 pa = isl_pw_aff_mod(pa, m->n); 1375 isl_val_free(m); 1376 return pa; 1377error: 1378 isl_pw_aff_free(pa); 1379 isl_val_free(m); 1380 return NULL; 1381} 1382 1383/* Given f, return ceil(f). 1384 * If f is an integer expression, then just return f. 1385 * Otherwise, let f be the expression 1386 * 1387 * e/m 1388 * 1389 * then return 1390 * 1391 * floor((e + m - 1)/m) 1392 */ 1393__isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff) 1394{ 1395 if (!aff) 1396 return NULL; 1397 1398 if (isl_int_is_one(aff->v->el[0])) 1399 return aff; 1400 1401 aff = isl_aff_cow(aff); 1402 if (!aff) 1403 return NULL; 1404 aff->v = isl_vec_cow(aff->v); 1405 if (!aff->v) 1406 return isl_aff_free(aff); 1407 1408 isl_int_add(aff->v->el[1], aff->v->el[1], aff->v->el[0]); 1409 isl_int_sub_ui(aff->v->el[1], aff->v->el[1], 1); 1410 aff = isl_aff_floor(aff); 1411 1412 return aff; 1413} 1414 1415/* Apply the expansion computed by isl_merge_divs. 1416 * The expansion itself is given by "exp" while the resulting 1417 * list of divs is given by "div". 1418 */ 1419__isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff, 1420 __isl_take isl_mat *div, int *exp) 1421{ 1422 int i, j; 1423 int old_n_div; 1424 int new_n_div; 1425 int offset; 1426 1427 aff = isl_aff_cow(aff); 1428 if (!aff || !div) 1429 goto error; 1430 1431 old_n_div = isl_local_space_dim(aff->ls, isl_dim_div); 1432 new_n_div = isl_mat_rows(div); 1433 if (new_n_div < old_n_div) 1434 isl_die(isl_mat_get_ctx(div), isl_error_invalid, 1435 "not an expansion", goto error); 1436 1437 aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div); 1438 if (!aff->v) 1439 goto error; 1440 1441 offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div); 1442 j = old_n_div - 1; 1443 for (i = new_n_div - 1; i >= 0; --i) { 1444 if (j >= 0 && exp[j] == i) { 1445 if (i != j) 1446 isl_int_swap(aff->v->el[offset + i], 1447 aff->v->el[offset + j]); 1448 j--; 1449 } else 1450 isl_int_set_si(aff->v->el[offset + i], 0); 1451 } 1452 1453 aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div)); 1454 if (!aff->ls) 1455 goto error; 1456 isl_mat_free(div); 1457 return aff; 1458error: 1459 isl_aff_free(aff); 1460 isl_mat_free(div); 1461 return NULL; 1462} 1463 1464/* Add two affine expressions that live in the same local space. 1465 */ 1466static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1, 1467 __isl_take isl_aff *aff2) 1468{ 1469 isl_int gcd, f; 1470 1471 aff1 = isl_aff_cow(aff1); 1472 if (!aff1 || !aff2) 1473 goto error; 1474 1475 aff1->v = isl_vec_cow(aff1->v); 1476 if (!aff1->v) 1477 goto error; 1478 1479 isl_int_init(gcd); 1480 isl_int_init(f); 1481 isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]); 1482 isl_int_divexact(f, aff2->v->el[0], gcd); 1483 isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1); 1484 isl_int_divexact(f, aff1->v->el[0], gcd); 1485 isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1); 1486 isl_int_divexact(f, aff2->v->el[0], gcd); 1487 isl_int_mul(aff1->v->el[0], aff1->v->el[0], f); 1488 isl_int_clear(f); 1489 isl_int_clear(gcd); 1490 1491 isl_aff_free(aff2); 1492 return aff1; 1493error: 1494 isl_aff_free(aff1); 1495 isl_aff_free(aff2); 1496 return NULL; 1497} 1498 1499__isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1, 1500 __isl_take isl_aff *aff2) 1501{ 1502 isl_ctx *ctx; 1503 int *exp1 = NULL; 1504 int *exp2 = NULL; 1505 isl_mat *div; 1506 int n_div1, n_div2; 1507 1508 if (!aff1 || !aff2) 1509 goto error; 1510 1511 ctx = isl_aff_get_ctx(aff1); 1512 if (!isl_space_is_equal(aff1->ls->dim, aff2->ls->dim)) 1513 isl_die(ctx, isl_error_invalid, 1514 "spaces don't match", goto error); 1515 1516 n_div1 = isl_aff_dim(aff1, isl_dim_div); 1517 n_div2 = isl_aff_dim(aff2, isl_dim_div); 1518 if (n_div1 == 0 && n_div2 == 0) 1519 return add_expanded(aff1, aff2); 1520 1521 exp1 = isl_alloc_array(ctx, int, n_div1); 1522 exp2 = isl_alloc_array(ctx, int, n_div2); 1523 if ((n_div1 && !exp1) || (n_div2 && !exp2)) 1524 goto error; 1525 1526 div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2); 1527 aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1); 1528 aff2 = isl_aff_expand_divs(aff2, div, exp2); 1529 free(exp1); 1530 free(exp2); 1531 1532 return add_expanded(aff1, aff2); 1533error: 1534 free(exp1); 1535 free(exp2); 1536 isl_aff_free(aff1); 1537 isl_aff_free(aff2); 1538 return NULL; 1539} 1540 1541__isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1, 1542 __isl_take isl_aff *aff2) 1543{ 1544 return isl_aff_add(aff1, isl_aff_neg(aff2)); 1545} 1546 1547__isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f) 1548{ 1549 isl_int gcd; 1550 1551 if (isl_int_is_one(f)) 1552 return aff; 1553 1554 aff = isl_aff_cow(aff); 1555 if (!aff) 1556 return NULL; 1557 aff->v = isl_vec_cow(aff->v); 1558 if (!aff->v) 1559 return isl_aff_free(aff); 1560 1561 if (isl_int_is_pos(f) && isl_int_is_divisible_by(aff->v->el[0], f)) { 1562 isl_int_divexact(aff->v->el[0], aff->v->el[0], f); 1563 return aff; 1564 } 1565 1566 isl_int_init(gcd); 1567 isl_int_gcd(gcd, aff->v->el[0], f); 1568 isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd); 1569 isl_int_divexact(gcd, f, gcd); 1570 isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1); 1571 isl_int_clear(gcd); 1572 1573 return aff; 1574} 1575 1576/* Multiple "aff" by "v". 1577 */ 1578__isl_give isl_aff *isl_aff_scale_val(__isl_take isl_aff *aff, 1579 __isl_take isl_val *v) 1580{ 1581 if (!aff || !v) 1582 goto error; 1583 1584 if (isl_val_is_one(v)) { 1585 isl_val_free(v); 1586 return aff; 1587 } 1588 1589 if (!isl_val_is_rat(v)) 1590 isl_die(isl_aff_get_ctx(aff), isl_error_invalid, 1591 "expecting rational factor", goto error); 1592 1593 aff = isl_aff_scale(aff, v->n); 1594 aff = isl_aff_scale_down(aff, v->d); 1595 1596 isl_val_free(v); 1597 return aff; 1598error: 1599 isl_aff_free(aff); 1600 isl_val_free(v); 1601 return NULL; 1602} 1603 1604__isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f) 1605{ 1606 isl_int gcd; 1607 1608 if (isl_int_is_one(f)) 1609 return aff; 1610 1611 aff = isl_aff_cow(aff); 1612 if (!aff) 1613 return NULL; 1614 1615 if (isl_int_is_zero(f)) 1616 isl_die(isl_aff_get_ctx(aff), isl_error_invalid, 1617 "cannot scale down by zero", return isl_aff_free(aff)); 1618 1619 aff->v = isl_vec_cow(aff->v); 1620 if (!aff->v) 1621 return isl_aff_free(aff); 1622 1623 isl_int_init(gcd); 1624 isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd); 1625 isl_int_gcd(gcd, gcd, f); 1626 isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1); 1627 isl_int_divexact(gcd, f, gcd); 1628 isl_int_mul(aff->v->el[0], aff->v->el[0], gcd); 1629 isl_int_clear(gcd); 1630 1631 return aff; 1632} 1633 1634/* Divide "aff" by "v". 1635 */ 1636__isl_give isl_aff *isl_aff_scale_down_val(__isl_take isl_aff *aff, 1637 __isl_take isl_val *v) 1638{ 1639 if (!aff || !v) 1640 goto error; 1641 1642 if (isl_val_is_one(v)) { 1643 isl_val_free(v); 1644 return aff; 1645 } 1646 1647 if (!isl_val_is_rat(v)) 1648 isl_die(isl_aff_get_ctx(aff), isl_error_invalid, 1649 "expecting rational factor", goto error); 1650 if (!isl_val_is_pos(v)) 1651 isl_die(isl_aff_get_ctx(aff), isl_error_invalid, 1652 "factor needs to be positive", goto error); 1653 1654 aff = isl_aff_scale(aff, v->d); 1655 aff = isl_aff_scale_down(aff, v->n); 1656 1657 isl_val_free(v); 1658 return aff; 1659error: 1660 isl_aff_free(aff); 1661 isl_val_free(v); 1662 return NULL; 1663} 1664 1665__isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f) 1666{ 1667 isl_int v; 1668 1669 if (f == 1) 1670 return aff; 1671 1672 isl_int_init(v); 1673 isl_int_set_ui(v, f); 1674 aff = isl_aff_scale_down(aff, v); 1675 isl_int_clear(v); 1676 1677 return aff; 1678} 1679 1680__isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff, 1681 enum isl_dim_type type, unsigned pos, const char *s) 1682{ 1683 aff = isl_aff_cow(aff); 1684 if (!aff) 1685 return NULL; 1686 if (type == isl_dim_out) 1687 isl_die(aff->v->ctx, isl_error_invalid, 1688 "cannot set name of output/set dimension", 1689 return isl_aff_free(aff)); 1690 if (type == isl_dim_in) 1691 type = isl_dim_set; 1692 aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s); 1693 if (!aff->ls) 1694 return isl_aff_free(aff); 1695 1696 return aff; 1697} 1698 1699__isl_give isl_aff *isl_aff_set_dim_id(__isl_take isl_aff *aff, 1700 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id) 1701{ 1702 aff = isl_aff_cow(aff); 1703 if (!aff) 1704 return isl_id_free(id); 1705 if (type == isl_dim_out) 1706 isl_die(aff->v->ctx, isl_error_invalid, 1707 "cannot set name of output/set dimension", 1708 goto error); 1709 if (type == isl_dim_in) 1710 type = isl_dim_set; 1711 aff->ls = isl_local_space_set_dim_id(aff->ls, type, pos, id); 1712 if (!aff->ls) 1713 return isl_aff_free(aff); 1714 1715 return aff; 1716error: 1717 isl_id_free(id); 1718 isl_aff_free(aff); 1719 return NULL; 1720} 1721 1722/* Exploit the equalities in "eq" to simplify the affine expression 1723 * and the expressions of the integer divisions in the local space. 1724 * The integer divisions in this local space are assumed to appear 1725 * as regular dimensions in "eq". 1726 */ 1727static __isl_give isl_aff *isl_aff_substitute_equalities_lifted( 1728 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq) 1729{ 1730 int i, j; 1731 unsigned total; 1732 unsigned n_div; 1733 1734 if (!eq) 1735 goto error; 1736 if (eq->n_eq == 0) { 1737 isl_basic_set_free(eq); 1738 return aff; 1739 } 1740 1741 aff = isl_aff_cow(aff); 1742 if (!aff) 1743 goto error; 1744 1745 aff->ls = isl_local_space_substitute_equalities(aff->ls, 1746 isl_basic_set_copy(eq)); 1747 aff->v = isl_vec_cow(aff->v); 1748 if (!aff->ls || !aff->v) 1749 goto error; 1750 1751 total = 1 + isl_space_dim(eq->dim, isl_dim_all); 1752 n_div = eq->n_div; 1753 for (i = 0; i < eq->n_eq; ++i) { 1754 j = isl_seq_last_non_zero(eq->eq[i], total + n_div); 1755 if (j < 0 || j == 0 || j >= total) 1756 continue; 1757 1758 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total, 1759 &aff->v->el[0]); 1760 } 1761 1762 isl_basic_set_free(eq); 1763 aff = isl_aff_normalize(aff); 1764 return aff; 1765error: 1766 isl_basic_set_free(eq); 1767 isl_aff_free(aff); 1768 return NULL; 1769} 1770 1771/* Exploit the equalities in "eq" to simplify the affine expression 1772 * and the expressions of the integer divisions in the local space. 1773 */ 1774static __isl_give isl_aff *isl_aff_substitute_equalities( 1775 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq) 1776{ 1777 int n_div; 1778 1779 if (!aff || !eq) 1780 goto error; 1781 n_div = isl_local_space_dim(aff->ls, isl_dim_div); 1782 if (n_div > 0) 1783 eq = isl_basic_set_add_dims(eq, isl_dim_set, n_div); 1784 return isl_aff_substitute_equalities_lifted(aff, eq); 1785error: 1786 isl_basic_set_free(eq); 1787 isl_aff_free(aff); 1788 return NULL; 1789} 1790 1791/* Look for equalities among the variables shared by context and aff 1792 * and the integer divisions of aff, if any. 1793 * The equalities are then used to eliminate coefficients and/or integer 1794 * divisions from aff. 1795 */ 1796__isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff, 1797 __isl_take isl_set *context) 1798{ 1799 isl_basic_set *hull; 1800 int n_div; 1801 1802 if (!aff) 1803 goto error; 1804 n_div = isl_local_space_dim(aff->ls, isl_dim_div); 1805 if (n_div > 0) { 1806 isl_basic_set *bset; 1807 isl_local_space *ls; 1808 context = isl_set_add_dims(context, isl_dim_set, n_div); 1809 ls = isl_aff_get_domain_local_space(aff); 1810 bset = isl_basic_set_from_local_space(ls); 1811 bset = isl_basic_set_lift(bset); 1812 bset = isl_basic_set_flatten(bset); 1813 context = isl_set_intersect(context, 1814 isl_set_from_basic_set(bset)); 1815 } 1816 1817 hull = isl_set_affine_hull(context); 1818 return isl_aff_substitute_equalities_lifted(aff, hull); 1819error: 1820 isl_aff_free(aff); 1821 isl_set_free(context); 1822 return NULL; 1823} 1824 1825__isl_give isl_aff *isl_aff_gist_params(__isl_take isl_aff *aff, 1826 __isl_take isl_set *context) 1827{ 1828 isl_set *dom_context = isl_set_universe(isl_aff_get_domain_space(aff)); 1829 dom_context = isl_set_intersect_params(dom_context, context); 1830 return isl_aff_gist(aff, dom_context); 1831} 1832 1833/* Return a basic set containing those elements in the space 1834 * of aff where it is non-negative. 1835 * If "rational" is set, then return a rational basic set. 1836 */ 1837static __isl_give isl_basic_set *aff_nonneg_basic_set( 1838 __isl_take isl_aff *aff, int rational) 1839{ 1840 isl_constraint *ineq; 1841 isl_basic_set *bset; 1842 1843 ineq = isl_inequality_from_aff(aff); 1844 1845 bset = isl_basic_set_from_constraint(ineq); 1846 if (rational) 1847 bset = isl_basic_set_set_rational(bset); 1848 bset = isl_basic_set_simplify(bset); 1849 return bset; 1850} 1851 1852/* Return a basic set containing those elements in the space 1853 * of aff where it is non-negative. 1854 */ 1855__isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff) 1856{ 1857 return aff_nonneg_basic_set(aff, 0); 1858} 1859 1860/* Return a basic set containing those elements in the domain space 1861 * of aff where it is negative. 1862 */ 1863__isl_give isl_basic_set *isl_aff_neg_basic_set(__isl_take isl_aff *aff) 1864{ 1865 aff = isl_aff_neg(aff); 1866 aff = isl_aff_add_constant_num_si(aff, -1); 1867 return isl_aff_nonneg_basic_set(aff); 1868} 1869 1870/* Return a basic set containing those elements in the space 1871 * of aff where it is zero. 1872 * If "rational" is set, then return a rational basic set. 1873 */ 1874static __isl_give isl_basic_set *aff_zero_basic_set(__isl_take isl_aff *aff, 1875 int rational) 1876{ 1877 isl_constraint *ineq; 1878 isl_basic_set *bset; 1879 1880 ineq = isl_equality_from_aff(aff); 1881 1882 bset = isl_basic_set_from_constraint(ineq); 1883 if (rational) 1884 bset = isl_basic_set_set_rational(bset); 1885 bset = isl_basic_set_simplify(bset); 1886 return bset; 1887} 1888 1889/* Return a basic set containing those elements in the space 1890 * of aff where it is zero. 1891 */ 1892__isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff) 1893{ 1894 return aff_zero_basic_set(aff, 0); 1895} 1896 1897/* Return a basic set containing those elements in the shared space 1898 * of aff1 and aff2 where aff1 is greater than or equal to aff2. 1899 */ 1900__isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1, 1901 __isl_take isl_aff *aff2) 1902{ 1903 aff1 = isl_aff_sub(aff1, aff2); 1904 1905 return isl_aff_nonneg_basic_set(aff1); 1906} 1907 1908/* Return a basic set containing those elements in the shared space 1909 * of aff1 and aff2 where aff1 is smaller than or equal to aff2. 1910 */ 1911__isl_give isl_basic_set *isl_aff_le_basic_set(__isl_take isl_aff *aff1, 1912 __isl_take isl_aff *aff2) 1913{ 1914 return isl_aff_ge_basic_set(aff2, aff1); 1915} 1916 1917__isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom, 1918 __isl_take isl_aff *aff1, __isl_take isl_aff *aff2) 1919{ 1920 aff1 = isl_aff_add(aff1, aff2); 1921 aff1 = isl_aff_gist(aff1, isl_set_copy(dom)); 1922 return aff1; 1923} 1924 1925int isl_aff_is_empty(__isl_keep isl_aff *aff) 1926{ 1927 if (!aff) 1928 return -1; 1929 1930 return 0; 1931} 1932 1933/* Check whether the given affine expression has non-zero coefficient 1934 * for any dimension in the given range or if any of these dimensions 1935 * appear with non-zero coefficients in any of the integer divisions 1936 * involved in the affine expression. 1937 */ 1938int isl_aff_involves_dims(__isl_keep isl_aff *aff, 1939 enum isl_dim_type type, unsigned first, unsigned n) 1940{ 1941 int i; 1942 isl_ctx *ctx; 1943 int *active = NULL; 1944 int involves = 0; 1945 1946 if (!aff) 1947 return -1; 1948 if (n == 0) 1949 return 0; 1950 1951 ctx = isl_aff_get_ctx(aff); 1952 if (first + n > isl_aff_dim(aff, type)) 1953 isl_die(ctx, isl_error_invalid, 1954 "range out of bounds", return -1); 1955 1956 active = isl_local_space_get_active(aff->ls, aff->v->el + 2); 1957 if (!active) 1958 goto error; 1959 1960 first += isl_local_space_offset(aff->ls, type) - 1; 1961 for (i = 0; i < n; ++i) 1962 if (active[first + i]) { 1963 involves = 1; 1964 break; 1965 } 1966 1967 free(active); 1968 1969 return involves; 1970error: 1971 free(active); 1972 return -1; 1973} 1974 1975__isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff, 1976 enum isl_dim_type type, unsigned first, unsigned n) 1977{ 1978 isl_ctx *ctx; 1979 1980 if (!aff) 1981 return NULL; 1982 if (type == isl_dim_out) 1983 isl_die(aff->v->ctx, isl_error_invalid, 1984 "cannot drop output/set dimension", 1985 return isl_aff_free(aff)); 1986 if (type == isl_dim_in) 1987 type = isl_dim_set; 1988 if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type)) 1989 return aff; 1990 1991 ctx = isl_aff_get_ctx(aff); 1992 if (first + n > isl_local_space_dim(aff->ls, type)) 1993 isl_die(ctx, isl_error_invalid, "range out of bounds", 1994 return isl_aff_free(aff)); 1995 1996 aff = isl_aff_cow(aff); 1997 if (!aff) 1998 return NULL; 1999 2000 aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n); 2001 if (!aff->ls) 2002 return isl_aff_free(aff); 2003 2004 first += 1 + isl_local_space_offset(aff->ls, type); 2005 aff->v = isl_vec_drop_els(aff->v, first, n); 2006 if (!aff->v) 2007 return isl_aff_free(aff); 2008 2009 return aff; 2010} 2011 2012/* Project the domain of the affine expression onto its parameter space. 2013 * The affine expression may not involve any of the domain dimensions. 2014 */ 2015__isl_give isl_aff *isl_aff_project_domain_on_params(__isl_take isl_aff *aff) 2016{ 2017 isl_space *space; 2018 unsigned n; 2019 int involves; 2020 2021 n = isl_aff_dim(aff, isl_dim_in); 2022 involves = isl_aff_involves_dims(aff, isl_dim_in, 0, n); 2023 if (involves < 0) 2024 return isl_aff_free(aff); 2025 if (involves) 2026 isl_die(isl_aff_get_ctx(aff), isl_error_invalid, 2027 "affine expression involves some of the domain dimensions", 2028 return isl_aff_free(aff)); 2029 aff = isl_aff_drop_dims(aff, isl_dim_in, 0, n); 2030 space = isl_aff_get_domain_space(aff); 2031 space = isl_space_params(space); 2032 aff = isl_aff_reset_domain_space(aff, space); 2033 return aff; 2034} 2035 2036__isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff, 2037 enum isl_dim_type type, unsigned first, unsigned n) 2038{ 2039 isl_ctx *ctx; 2040 2041 if (!aff) 2042 return NULL; 2043 if (type == isl_dim_out) 2044 isl_die(aff->v->ctx, isl_error_invalid, 2045 "cannot insert output/set dimensions", 2046 return isl_aff_free(aff)); 2047 if (type == isl_dim_in) 2048 type = isl_dim_set; 2049 if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type)) 2050 return aff; 2051 2052 ctx = isl_aff_get_ctx(aff); 2053 if (first > isl_local_space_dim(aff->ls, type)) 2054 isl_die(ctx, isl_error_invalid, "position out of bounds", 2055 return isl_aff_free(aff)); 2056 2057 aff = isl_aff_cow(aff); 2058 if (!aff) 2059 return NULL; 2060 2061 aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n); 2062 if (!aff->ls) 2063 return isl_aff_free(aff); 2064 2065 first += 1 + isl_local_space_offset(aff->ls, type); 2066 aff->v = isl_vec_insert_zero_els(aff->v, first, n); 2067 if (!aff->v) 2068 return isl_aff_free(aff); 2069 2070 return aff; 2071} 2072 2073__isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff, 2074 enum isl_dim_type type, unsigned n) 2075{ 2076 unsigned pos; 2077 2078 pos = isl_aff_dim(aff, type); 2079 2080 return isl_aff_insert_dims(aff, type, pos, n); 2081} 2082 2083__isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff, 2084 enum isl_dim_type type, unsigned n) 2085{ 2086 unsigned pos; 2087 2088 pos = isl_pw_aff_dim(pwaff, type); 2089 2090 return isl_pw_aff_insert_dims(pwaff, type, pos, n); 2091} 2092 2093__isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff) 2094{ 2095 isl_set *dom = isl_set_universe(isl_aff_get_domain_space(aff)); 2096 return isl_pw_aff_alloc(dom, aff); 2097} 2098 2099#undef PW 2100#define PW isl_pw_aff 2101#undef EL 2102#define EL isl_aff 2103#undef EL_IS_ZERO 2104#define EL_IS_ZERO is_empty 2105#undef ZERO 2106#define ZERO empty 2107#undef IS_ZERO 2108#define IS_ZERO is_empty 2109#undef FIELD 2110#define FIELD aff 2111#undef DEFAULT_IS_ZERO 2112#define DEFAULT_IS_ZERO 0 2113 2114#define NO_EVAL 2115#define NO_OPT 2116#define NO_MOVE_DIMS 2117#define NO_LIFT 2118#define NO_MORPH 2119 2120#include <isl_pw_templ.c> 2121 2122static __isl_give isl_set *align_params_pw_pw_set_and( 2123 __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2, 2124 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1, 2125 __isl_take isl_pw_aff *pwaff2)) 2126{ 2127 if (!pwaff1 || !pwaff2) 2128 goto error; 2129 if (isl_space_match(pwaff1->dim, isl_dim_param, 2130 pwaff2->dim, isl_dim_param)) 2131 return fn(pwaff1, pwaff2); 2132 if (!isl_space_has_named_params(pwaff1->dim) || 2133 !isl_space_has_named_params(pwaff2->dim)) 2134 isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid, 2135 "unaligned unnamed parameters", goto error); 2136 pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_space(pwaff2)); 2137 pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_space(pwaff1)); 2138 return fn(pwaff1, pwaff2); 2139error: 2140 isl_pw_aff_free(pwaff1); 2141 isl_pw_aff_free(pwaff2); 2142 return NULL; 2143} 2144 2145/* Compute a piecewise quasi-affine expression with a domain that 2146 * is the union of those of pwaff1 and pwaff2 and such that on each 2147 * cell, the quasi-affine expression is the better (according to cmp) 2148 * of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2 2149 * is defined on a given cell, then the associated expression 2150 * is the defined one. 2151 */ 2152static __isl_give isl_pw_aff *pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1, 2153 __isl_take isl_pw_aff *pwaff2, 2154 __isl_give isl_basic_set *(*cmp)(__isl_take isl_aff *aff1, 2155 __isl_take isl_aff *aff2)) 2156{ 2157 int i, j, n; 2158 isl_pw_aff *res; 2159 isl_ctx *ctx; 2160 isl_set *set; 2161 2162 if (!pwaff1 || !pwaff2) 2163 goto error; 2164 2165 ctx = isl_space_get_ctx(pwaff1->dim); 2166 if (!isl_space_is_equal(pwaff1->dim, pwaff2->dim)) 2167 isl_die(ctx, isl_error_invalid, 2168 "arguments should live in same space", goto error); 2169 2170 if (isl_pw_aff_is_empty(pwaff1)) { 2171 isl_pw_aff_free(pwaff1); 2172 return pwaff2; 2173 } 2174 2175 if (isl_pw_aff_is_empty(pwaff2)) { 2176 isl_pw_aff_free(pwaff2); 2177 return pwaff1; 2178 } 2179 2180 n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1); 2181 res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n); 2182 2183 for (i = 0; i < pwaff1->n; ++i) { 2184 set = isl_set_copy(pwaff1->p[i].set); 2185 for (j = 0; j < pwaff2->n; ++j) { 2186 struct isl_set *common; 2187 isl_set *better; 2188 2189 common = isl_set_intersect( 2190 isl_set_copy(pwaff1->p[i].set), 2191 isl_set_copy(pwaff2->p[j].set)); 2192 better = isl_set_from_basic_set(cmp( 2193 isl_aff_copy(pwaff2->p[j].aff), 2194 isl_aff_copy(pwaff1->p[i].aff))); 2195 better = isl_set_intersect(common, better); 2196 if (isl_set_plain_is_empty(better)) { 2197 isl_set_free(better); 2198 continue; 2199 } 2200 set = isl_set_subtract(set, isl_set_copy(better)); 2201 2202 res = isl_pw_aff_add_piece(res, better, 2203 isl_aff_copy(pwaff2->p[j].aff)); 2204 } 2205 res = isl_pw_aff_add_piece(res, set, 2206 isl_aff_copy(pwaff1->p[i].aff)); 2207 } 2208 2209 for (j = 0; j < pwaff2->n; ++j) { 2210 set = isl_set_copy(pwaff2->p[j].set); 2211 for (i = 0; i < pwaff1->n; ++i) 2212 set = isl_set_subtract(set, 2213 isl_set_copy(pwaff1->p[i].set)); 2214 res = isl_pw_aff_add_piece(res, set, 2215 isl_aff_copy(pwaff2->p[j].aff)); 2216 } 2217 2218 isl_pw_aff_free(pwaff1); 2219 isl_pw_aff_free(pwaff2); 2220 2221 return res; 2222error: 2223 isl_pw_aff_free(pwaff1); 2224 isl_pw_aff_free(pwaff2); 2225 return NULL; 2226} 2227 2228/* Compute a piecewise quasi-affine expression with a domain that 2229 * is the union of those of pwaff1 and pwaff2 and such that on each 2230 * cell, the quasi-affine expression is the maximum of those of pwaff1 2231 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given 2232 * cell, then the associated expression is the defined one. 2233 */ 2234static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1, 2235 __isl_take isl_pw_aff *pwaff2) 2236{ 2237 return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_ge_basic_set); 2238} 2239 2240__isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1, 2241 __isl_take isl_pw_aff *pwaff2) 2242{ 2243 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, 2244 &pw_aff_union_max); 2245} 2246 2247/* Compute a piecewise quasi-affine expression with a domain that 2248 * is the union of those of pwaff1 and pwaff2 and such that on each 2249 * cell, the quasi-affine expression is the minimum of those of pwaff1 2250 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given 2251 * cell, then the associated expression is the defined one. 2252 */ 2253static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1, 2254 __isl_take isl_pw_aff *pwaff2) 2255{ 2256 return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_le_basic_set); 2257} 2258 2259__isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1, 2260 __isl_take isl_pw_aff *pwaff2) 2261{ 2262 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, 2263 &pw_aff_union_min); 2264} 2265 2266__isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1, 2267 __isl_take isl_pw_aff *pwaff2, int max) 2268{ 2269 if (max) 2270 return isl_pw_aff_union_max(pwaff1, pwaff2); 2271 else 2272 return isl_pw_aff_union_min(pwaff1, pwaff2); 2273} 2274 2275/* Construct a map with as domain the domain of pwaff and 2276 * one-dimensional range corresponding to the affine expressions. 2277 */ 2278static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff) 2279{ 2280 int i; 2281 isl_space *dim; 2282 isl_map *map; 2283 2284 if (!pwaff) 2285 return NULL; 2286 2287 dim = isl_pw_aff_get_space(pwaff); 2288 map = isl_map_empty(dim); 2289 2290 for (i = 0; i < pwaff->n; ++i) { 2291 isl_basic_map *bmap; 2292 isl_map *map_i; 2293 2294 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff)); 2295 map_i = isl_map_from_basic_map(bmap); 2296 map_i = isl_map_intersect_domain(map_i, 2297 isl_set_copy(pwaff->p[i].set)); 2298 map = isl_map_union_disjoint(map, map_i); 2299 } 2300 2301 isl_pw_aff_free(pwaff); 2302 2303 return map; 2304} 2305 2306/* Construct a map with as domain the domain of pwaff and 2307 * one-dimensional range corresponding to the affine expressions. 2308 */ 2309__isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff) 2310{ 2311 if (!pwaff) 2312 return NULL; 2313 if (isl_space_is_set(pwaff->dim)) 2314 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid, 2315 "space of input is not a map", 2316 return isl_pw_aff_free(pwaff)); 2317 return map_from_pw_aff(pwaff); 2318} 2319 2320/* Construct a one-dimensional set with as parameter domain 2321 * the domain of pwaff and the single set dimension 2322 * corresponding to the affine expressions. 2323 */ 2324__isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff) 2325{ 2326 if (!pwaff) 2327 return NULL; 2328 if (!isl_space_is_set(pwaff->dim)) 2329 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid, 2330 "space of input is not a set", 2331 return isl_pw_aff_free(pwaff)); 2332 return map_from_pw_aff(pwaff); 2333} 2334 2335/* Return a set containing those elements in the domain 2336 * of pwaff where it is non-negative. 2337 */ 2338__isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff) 2339{ 2340 int i; 2341 isl_set *set; 2342 2343 if (!pwaff) 2344 return NULL; 2345 2346 set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff)); 2347 2348 for (i = 0; i < pwaff->n; ++i) { 2349 isl_basic_set *bset; 2350 isl_set *set_i; 2351 int rational; 2352 2353 rational = isl_set_has_rational(pwaff->p[i].set); 2354 bset = aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff), 2355 rational); 2356 set_i = isl_set_from_basic_set(bset); 2357 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set)); 2358 set = isl_set_union_disjoint(set, set_i); 2359 } 2360 2361 isl_pw_aff_free(pwaff); 2362 2363 return set; 2364} 2365 2366/* Return a set containing those elements in the domain 2367 * of pwaff where it is zero (if complement is 0) or not zero 2368 * (if complement is 1). 2369 */ 2370static __isl_give isl_set *pw_aff_zero_set(__isl_take isl_pw_aff *pwaff, 2371 int complement) 2372{ 2373 int i; 2374 isl_set *set; 2375 2376 if (!pwaff) 2377 return NULL; 2378 2379 set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff)); 2380 2381 for (i = 0; i < pwaff->n; ++i) { 2382 isl_basic_set *bset; 2383 isl_set *set_i, *zero; 2384 int rational; 2385 2386 rational = isl_set_has_rational(pwaff->p[i].set); 2387 bset = aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff), 2388 rational); 2389 zero = isl_set_from_basic_set(bset); 2390 set_i = isl_set_copy(pwaff->p[i].set); 2391 if (complement) 2392 set_i = isl_set_subtract(set_i, zero); 2393 else 2394 set_i = isl_set_intersect(set_i, zero); 2395 set = isl_set_union_disjoint(set, set_i); 2396 } 2397 2398 isl_pw_aff_free(pwaff); 2399 2400 return set; 2401} 2402 2403/* Return a set containing those elements in the domain 2404 * of pwaff where it is zero. 2405 */ 2406__isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff) 2407{ 2408 return pw_aff_zero_set(pwaff, 0); 2409} 2410 2411/* Return a set containing those elements in the domain 2412 * of pwaff where it is not zero. 2413 */ 2414__isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff) 2415{ 2416 return pw_aff_zero_set(pwaff, 1); 2417} 2418 2419/* Return a set containing those elements in the shared domain 2420 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2. 2421 * 2422 * We compute the difference on the shared domain and then construct 2423 * the set of values where this difference is non-negative. 2424 * If strict is set, we first subtract 1 from the difference. 2425 * If equal is set, we only return the elements where pwaff1 and pwaff2 2426 * are equal. 2427 */ 2428static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1, 2429 __isl_take isl_pw_aff *pwaff2, int strict, int equal) 2430{ 2431 isl_set *set1, *set2; 2432 2433 set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)); 2434 set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)); 2435 set1 = isl_set_intersect(set1, set2); 2436 pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1)); 2437 pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1)); 2438 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2)); 2439 2440 if (strict) { 2441 isl_space *dim = isl_set_get_space(set1); 2442 isl_aff *aff; 2443 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim)); 2444 aff = isl_aff_add_constant_si(aff, -1); 2445 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff)); 2446 } else 2447 isl_set_free(set1); 2448 2449 if (equal) 2450 return isl_pw_aff_zero_set(pwaff1); 2451 return isl_pw_aff_nonneg_set(pwaff1); 2452} 2453 2454/* Return a set containing those elements in the shared domain 2455 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2. 2456 */ 2457static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1, 2458 __isl_take isl_pw_aff *pwaff2) 2459{ 2460 return pw_aff_gte_set(pwaff1, pwaff2, 0, 1); 2461} 2462 2463__isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1, 2464 __isl_take isl_pw_aff *pwaff2) 2465{ 2466 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set); 2467} 2468 2469/* Return a set containing those elements in the shared domain 2470 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2. 2471 */ 2472static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1, 2473 __isl_take isl_pw_aff *pwaff2) 2474{ 2475 return pw_aff_gte_set(pwaff1, pwaff2, 0, 0); 2476} 2477 2478__isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1, 2479 __isl_take isl_pw_aff *pwaff2) 2480{ 2481 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set); 2482} 2483 2484/* Return a set containing those elements in the shared domain 2485 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2. 2486 */ 2487static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1, 2488 __isl_take isl_pw_aff *pwaff2) 2489{ 2490 return pw_aff_gte_set(pwaff1, pwaff2, 1, 0); 2491} 2492 2493__isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1, 2494 __isl_take isl_pw_aff *pwaff2) 2495{ 2496 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set); 2497} 2498 2499__isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1, 2500 __isl_take isl_pw_aff *pwaff2) 2501{ 2502 return isl_pw_aff_ge_set(pwaff2, pwaff1); 2503} 2504 2505__isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1, 2506 __isl_take isl_pw_aff *pwaff2) 2507{ 2508 return isl_pw_aff_gt_set(pwaff2, pwaff1); 2509} 2510 2511/* Return a set containing those elements in the shared domain 2512 * of the elements of list1 and list2 where each element in list1 2513 * has the relation specified by "fn" with each element in list2. 2514 */ 2515static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1, 2516 __isl_take isl_pw_aff_list *list2, 2517 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1, 2518 __isl_take isl_pw_aff *pwaff2)) 2519{ 2520 int i, j; 2521 isl_ctx *ctx; 2522 isl_set *set; 2523 2524 if (!list1 || !list2) 2525 goto error; 2526 2527 ctx = isl_pw_aff_list_get_ctx(list1); 2528 if (list1->n < 1 || list2->n < 1) 2529 isl_die(ctx, isl_error_invalid, 2530 "list should contain at least one element", goto error); 2531 2532 set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0])); 2533 for (i = 0; i < list1->n; ++i) 2534 for (j = 0; j < list2->n; ++j) { 2535 isl_set *set_ij; 2536 2537 set_ij = fn(isl_pw_aff_copy(list1->p[i]), 2538 isl_pw_aff_copy(list2->p[j])); 2539 set = isl_set_intersect(set, set_ij); 2540 } 2541 2542 isl_pw_aff_list_free(list1); 2543 isl_pw_aff_list_free(list2); 2544 return set; 2545error: 2546 isl_pw_aff_list_free(list1); 2547 isl_pw_aff_list_free(list2); 2548 return NULL; 2549} 2550 2551/* Return a set containing those elements in the shared domain 2552 * of the elements of list1 and list2 where each element in list1 2553 * is equal to each element in list2. 2554 */ 2555__isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1, 2556 __isl_take isl_pw_aff_list *list2) 2557{ 2558 return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set); 2559} 2560 2561__isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1, 2562 __isl_take isl_pw_aff_list *list2) 2563{ 2564 return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set); 2565} 2566 2567/* Return a set containing those elements in the shared domain 2568 * of the elements of list1 and list2 where each element in list1 2569 * is less than or equal to each element in list2. 2570 */ 2571__isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1, 2572 __isl_take isl_pw_aff_list *list2) 2573{ 2574 return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set); 2575} 2576 2577__isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1, 2578 __isl_take isl_pw_aff_list *list2) 2579{ 2580 return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set); 2581} 2582 2583__isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1, 2584 __isl_take isl_pw_aff_list *list2) 2585{ 2586 return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set); 2587} 2588 2589__isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1, 2590 __isl_take isl_pw_aff_list *list2) 2591{ 2592 return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set); 2593} 2594 2595 2596/* Return a set containing those elements in the shared domain 2597 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2. 2598 */ 2599static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1, 2600 __isl_take isl_pw_aff *pwaff2) 2601{ 2602 isl_set *set_lt, *set_gt; 2603 2604 set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1), 2605 isl_pw_aff_copy(pwaff2)); 2606 set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2); 2607 return isl_set_union_disjoint(set_lt, set_gt); 2608} 2609 2610__isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1, 2611 __isl_take isl_pw_aff *pwaff2) 2612{ 2613 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set); 2614} 2615 2616__isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff, 2617 isl_int v) 2618{ 2619 int i; 2620 2621 if (isl_int_is_one(v)) 2622 return pwaff; 2623 if (!isl_int_is_pos(v)) 2624 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid, 2625 "factor needs to be positive", 2626 return isl_pw_aff_free(pwaff)); 2627 pwaff = isl_pw_aff_cow(pwaff); 2628 if (!pwaff) 2629 return NULL; 2630 if (pwaff->n == 0) 2631 return pwaff; 2632 2633 for (i = 0; i < pwaff->n; ++i) { 2634 pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v); 2635 if (!pwaff->p[i].aff) 2636 return isl_pw_aff_free(pwaff); 2637 } 2638 2639 return pwaff; 2640} 2641 2642/* Divide "pa" by "f". 2643 */ 2644__isl_give isl_pw_aff *isl_pw_aff_scale_down_val(__isl_take isl_pw_aff *pa, 2645 __isl_take isl_val *f) 2646{ 2647 int i; 2648 2649 if (!pa || !f) 2650 goto error; 2651 2652 if (isl_val_is_one(f)) { 2653 isl_val_free(f); 2654 return pa; 2655 } 2656 2657 if (!isl_val_is_rat(f)) 2658 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid, 2659 "expecting rational factor", goto error); 2660 if (!isl_val_is_pos(f)) 2661 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid, 2662 "factor needs to be positive", goto error); 2663 2664 pa = isl_pw_aff_cow(pa); 2665 if (!pa) 2666 return NULL; 2667 if (pa->n == 0) 2668 return pa; 2669 2670 for (i = 0; i < pa->n; ++i) { 2671 pa->p[i].aff = isl_aff_scale_down_val(pa->p[i].aff, 2672 isl_val_copy(f)); 2673 if (!pa->p[i].aff) 2674 goto error; 2675 } 2676 2677 isl_val_free(f); 2678 return pa; 2679error: 2680 isl_pw_aff_free(pa); 2681 isl_val_free(f); 2682 return NULL; 2683} 2684 2685__isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff) 2686{ 2687 int i; 2688 2689 pwaff = isl_pw_aff_cow(pwaff); 2690 if (!pwaff) 2691 return NULL; 2692 if (pwaff->n == 0) 2693 return pwaff; 2694 2695 for (i = 0; i < pwaff->n; ++i) { 2696 pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff); 2697 if (!pwaff->p[i].aff) 2698 return isl_pw_aff_free(pwaff); 2699 } 2700 2701 return pwaff; 2702} 2703 2704__isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff) 2705{ 2706 int i; 2707 2708 pwaff = isl_pw_aff_cow(pwaff); 2709 if (!pwaff) 2710 return NULL; 2711 if (pwaff->n == 0) 2712 return pwaff; 2713 2714 for (i = 0; i < pwaff->n; ++i) { 2715 pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff); 2716 if (!pwaff->p[i].aff) 2717 return isl_pw_aff_free(pwaff); 2718 } 2719 2720 return pwaff; 2721} 2722 2723/* Assuming that "cond1" and "cond2" are disjoint, 2724 * return an affine expression that is equal to pwaff1 on cond1 2725 * and to pwaff2 on cond2. 2726 */ 2727static __isl_give isl_pw_aff *isl_pw_aff_select( 2728 __isl_take isl_set *cond1, __isl_take isl_pw_aff *pwaff1, 2729 __isl_take isl_set *cond2, __isl_take isl_pw_aff *pwaff2) 2730{ 2731 pwaff1 = isl_pw_aff_intersect_domain(pwaff1, cond1); 2732 pwaff2 = isl_pw_aff_intersect_domain(pwaff2, cond2); 2733 2734 return isl_pw_aff_add_disjoint(pwaff1, pwaff2); 2735} 2736 2737/* Return an affine expression that is equal to pwaff_true for elements 2738 * where "cond" is non-zero and to pwaff_false for elements where "cond" 2739 * is zero. 2740 * That is, return cond ? pwaff_true : pwaff_false; 2741 */ 2742__isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_pw_aff *cond, 2743 __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false) 2744{ 2745 isl_set *cond_true, *cond_false; 2746 2747 cond_true = isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond)); 2748 cond_false = isl_pw_aff_zero_set(cond); 2749 return isl_pw_aff_select(cond_true, pwaff_true, 2750 cond_false, pwaff_false); 2751} 2752 2753int isl_aff_is_cst(__isl_keep isl_aff *aff) 2754{ 2755 if (!aff) 2756 return -1; 2757 2758 return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1; 2759} 2760 2761/* Check whether pwaff is a piecewise constant. 2762 */ 2763int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff) 2764{ 2765 int i; 2766 2767 if (!pwaff) 2768 return -1; 2769 2770 for (i = 0; i < pwaff->n; ++i) { 2771 int is_cst = isl_aff_is_cst(pwaff->p[i].aff); 2772 if (is_cst < 0 || !is_cst) 2773 return is_cst; 2774 } 2775 2776 return 1; 2777} 2778 2779__isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1, 2780 __isl_take isl_aff *aff2) 2781{ 2782 if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1)) 2783 return isl_aff_mul(aff2, aff1); 2784 2785 if (!isl_aff_is_cst(aff2)) 2786 isl_die(isl_aff_get_ctx(aff1), isl_error_invalid, 2787 "at least one affine expression should be constant", 2788 goto error); 2789 2790 aff1 = isl_aff_cow(aff1); 2791 if (!aff1 || !aff2) 2792 goto error; 2793 2794 aff1 = isl_aff_scale(aff1, aff2->v->el[1]); 2795 aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]); 2796 2797 isl_aff_free(aff2); 2798 return aff1; 2799error: 2800 isl_aff_free(aff1); 2801 isl_aff_free(aff2); 2802 return NULL; 2803} 2804 2805/* Divide "aff1" by "aff2", assuming "aff2" is a piecewise constant. 2806 */ 2807__isl_give isl_aff *isl_aff_div(__isl_take isl_aff *aff1, 2808 __isl_take isl_aff *aff2) 2809{ 2810 int is_cst; 2811 int neg; 2812 2813 is_cst = isl_aff_is_cst(aff2); 2814 if (is_cst < 0) 2815 goto error; 2816 if (!is_cst) 2817 isl_die(isl_aff_get_ctx(aff2), isl_error_invalid, 2818 "second argument should be a constant", goto error); 2819 2820 if (!aff2) 2821 goto error; 2822 2823 neg = isl_int_is_neg(aff2->v->el[1]); 2824 if (neg) { 2825 isl_int_neg(aff2->v->el[0], aff2->v->el[0]); 2826 isl_int_neg(aff2->v->el[1], aff2->v->el[1]); 2827 } 2828 2829 aff1 = isl_aff_scale(aff1, aff2->v->el[0]); 2830 aff1 = isl_aff_scale_down(aff1, aff2->v->el[1]); 2831 2832 if (neg) { 2833 isl_int_neg(aff2->v->el[0], aff2->v->el[0]); 2834 isl_int_neg(aff2->v->el[1], aff2->v->el[1]); 2835 } 2836 2837 isl_aff_free(aff2); 2838 return aff1; 2839error: 2840 isl_aff_free(aff1); 2841 isl_aff_free(aff2); 2842 return NULL; 2843} 2844 2845static __isl_give isl_pw_aff *pw_aff_add(__isl_take isl_pw_aff *pwaff1, 2846 __isl_take isl_pw_aff *pwaff2) 2847{ 2848 return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_add); 2849} 2850 2851__isl_give isl_pw_aff *isl_pw_aff_add(__isl_take isl_pw_aff *pwaff1, 2852 __isl_take isl_pw_aff *pwaff2) 2853{ 2854 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_add); 2855} 2856 2857__isl_give isl_pw_aff *isl_pw_aff_union_add(__isl_take isl_pw_aff *pwaff1, 2858 __isl_take isl_pw_aff *pwaff2) 2859{ 2860 return isl_pw_aff_union_add_(pwaff1, pwaff2); 2861} 2862 2863static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1, 2864 __isl_take isl_pw_aff *pwaff2) 2865{ 2866 return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_mul); 2867} 2868 2869__isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1, 2870 __isl_take isl_pw_aff *pwaff2) 2871{ 2872 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul); 2873} 2874 2875static __isl_give isl_pw_aff *pw_aff_div(__isl_take isl_pw_aff *pa1, 2876 __isl_take isl_pw_aff *pa2) 2877{ 2878 return isl_pw_aff_on_shared_domain(pa1, pa2, &isl_aff_div); 2879} 2880 2881/* Divide "pa1" by "pa2", assuming "pa2" is a piecewise constant. 2882 */ 2883__isl_give isl_pw_aff *isl_pw_aff_div(__isl_take isl_pw_aff *pa1, 2884 __isl_take isl_pw_aff *pa2) 2885{ 2886 int is_cst; 2887 2888 is_cst = isl_pw_aff_is_cst(pa2); 2889 if (is_cst < 0) 2890 goto error; 2891 if (!is_cst) 2892 isl_die(isl_pw_aff_get_ctx(pa2), isl_error_invalid, 2893 "second argument should be a piecewise constant", 2894 goto error); 2895 return isl_pw_aff_align_params_pw_pw_and(pa1, pa2, &pw_aff_div); 2896error: 2897 isl_pw_aff_free(pa1); 2898 isl_pw_aff_free(pa2); 2899 return NULL; 2900} 2901 2902/* Compute the quotient of the integer division of "pa1" by "pa2" 2903 * with rounding towards zero. 2904 * "pa2" is assumed to be a piecewise constant. 2905 * 2906 * In particular, return 2907 * 2908 * pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2) 2909 * 2910 */ 2911__isl_give isl_pw_aff *isl_pw_aff_tdiv_q(__isl_take isl_pw_aff *pa1, 2912 __isl_take isl_pw_aff *pa2) 2913{ 2914 int is_cst; 2915 isl_set *cond; 2916 isl_pw_aff *f, *c; 2917 2918 is_cst = isl_pw_aff_is_cst(pa2); 2919 if (is_cst < 0) 2920 goto error; 2921 if (!is_cst) 2922 isl_die(isl_pw_aff_get_ctx(pa2), isl_error_invalid, 2923 "second argument should be a piecewise constant", 2924 goto error); 2925 2926 pa1 = isl_pw_aff_div(pa1, pa2); 2927 2928 cond = isl_pw_aff_nonneg_set(isl_pw_aff_copy(pa1)); 2929 f = isl_pw_aff_floor(isl_pw_aff_copy(pa1)); 2930 c = isl_pw_aff_ceil(pa1); 2931 return isl_pw_aff_cond(isl_set_indicator_function(cond), f, c); 2932error: 2933 isl_pw_aff_free(pa1); 2934 isl_pw_aff_free(pa2); 2935 return NULL; 2936} 2937 2938/* Compute the remainder of the integer division of "pa1" by "pa2" 2939 * with rounding towards zero. 2940 * "pa2" is assumed to be a piecewise constant. 2941 * 2942 * In particular, return 2943 * 2944 * pa1 - pa2 * (pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2)) 2945 * 2946 */ 2947__isl_give isl_pw_aff *isl_pw_aff_tdiv_r(__isl_take isl_pw_aff *pa1, 2948 __isl_take isl_pw_aff *pa2) 2949{ 2950 int is_cst; 2951 isl_pw_aff *res; 2952 2953 is_cst = isl_pw_aff_is_cst(pa2); 2954 if (is_cst < 0) 2955 goto error; 2956 if (!is_cst) 2957 isl_die(isl_pw_aff_get_ctx(pa2), isl_error_invalid, 2958 "second argument should be a piecewise constant", 2959 goto error); 2960 res = isl_pw_aff_tdiv_q(isl_pw_aff_copy(pa1), isl_pw_aff_copy(pa2)); 2961 res = isl_pw_aff_mul(pa2, res); 2962 res = isl_pw_aff_sub(pa1, res); 2963 return res; 2964error: 2965 isl_pw_aff_free(pa1); 2966 isl_pw_aff_free(pa2); 2967 return NULL; 2968} 2969 2970static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1, 2971 __isl_take isl_pw_aff *pwaff2) 2972{ 2973 isl_set *le; 2974 isl_set *dom; 2975 2976 dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)), 2977 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2))); 2978 le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1), 2979 isl_pw_aff_copy(pwaff2)); 2980 dom = isl_set_subtract(dom, isl_set_copy(le)); 2981 return isl_pw_aff_select(le, pwaff1, dom, pwaff2); 2982} 2983 2984__isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1, 2985 __isl_take isl_pw_aff *pwaff2) 2986{ 2987 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min); 2988} 2989 2990static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1, 2991 __isl_take isl_pw_aff *pwaff2) 2992{ 2993 isl_set *ge; 2994 isl_set *dom; 2995 2996 dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)), 2997 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2))); 2998 ge = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1), 2999 isl_pw_aff_copy(pwaff2)); 3000 dom = isl_set_subtract(dom, isl_set_copy(ge)); 3001 return isl_pw_aff_select(ge, pwaff1, dom, pwaff2); 3002} 3003 3004__isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1, 3005 __isl_take isl_pw_aff *pwaff2) 3006{ 3007 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max); 3008} 3009 3010static __isl_give isl_pw_aff *pw_aff_list_reduce( 3011 __isl_take isl_pw_aff_list *list, 3012 __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1, 3013 __isl_take isl_pw_aff *pwaff2)) 3014{ 3015 int i; 3016 isl_ctx *ctx; 3017 isl_pw_aff *res; 3018 3019 if (!list) 3020 return NULL; 3021 3022 ctx = isl_pw_aff_list_get_ctx(list); 3023 if (list->n < 1) 3024 isl_die(ctx, isl_error_invalid, 3025 "list should contain at least one element", 3026 return isl_pw_aff_list_free(list)); 3027 3028 res = isl_pw_aff_copy(list->p[0]); 3029 for (i = 1; i < list->n; ++i) 3030 res = fn(res, isl_pw_aff_copy(list->p[i])); 3031 3032 isl_pw_aff_list_free(list); 3033 return res; 3034} 3035 3036/* Return an isl_pw_aff that maps each element in the intersection of the 3037 * domains of the elements of list to the minimal corresponding affine 3038 * expression. 3039 */ 3040__isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list) 3041{ 3042 return pw_aff_list_reduce(list, &isl_pw_aff_min); 3043} 3044 3045/* Return an isl_pw_aff that maps each element in the intersection of the 3046 * domains of the elements of list to the maximal corresponding affine 3047 * expression. 3048 */ 3049__isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list) 3050{ 3051 return pw_aff_list_reduce(list, &isl_pw_aff_max); 3052} 3053 3054/* Mark the domains of "pwaff" as rational. 3055 */ 3056__isl_give isl_pw_aff *isl_pw_aff_set_rational(__isl_take isl_pw_aff *pwaff) 3057{ 3058 int i; 3059 3060 pwaff = isl_pw_aff_cow(pwaff); 3061 if (!pwaff) 3062 return NULL; 3063 if (pwaff->n == 0) 3064 return pwaff; 3065 3066 for (i = 0; i < pwaff->n; ++i) { 3067 pwaff->p[i].set = isl_set_set_rational(pwaff->p[i].set); 3068 if (!pwaff->p[i].set) 3069 return isl_pw_aff_free(pwaff); 3070 } 3071 3072 return pwaff; 3073} 3074 3075/* Mark the domains of the elements of "list" as rational. 3076 */ 3077__isl_give isl_pw_aff_list *isl_pw_aff_list_set_rational( 3078 __isl_take isl_pw_aff_list *list) 3079{ 3080 int i, n; 3081 3082 if (!list) 3083 return NULL; 3084 if (list->n == 0) 3085 return list; 3086 3087 n = list->n; 3088 for (i = 0; i < n; ++i) { 3089 isl_pw_aff *pa; 3090 3091 pa = isl_pw_aff_list_get_pw_aff(list, i); 3092 pa = isl_pw_aff_set_rational(pa); 3093 list = isl_pw_aff_list_set_pw_aff(list, i, pa); 3094 } 3095 3096 return list; 3097} 3098 3099/* Check that the domain space of "aff" matches "space". 3100 * 3101 * Return 0 on success and -1 on error. 3102 */ 3103int isl_aff_check_match_domain_space(__isl_keep isl_aff *aff, 3104 __isl_keep isl_space *space) 3105{ 3106 isl_space *aff_space; 3107 int match; 3108 3109 if (!aff || !space) 3110 return -1; 3111 3112 aff_space = isl_aff_get_domain_space(aff); 3113 3114 match = isl_space_match(space, isl_dim_param, aff_space, isl_dim_param); 3115 if (match < 0) 3116 goto error; 3117 if (!match) 3118 isl_die(isl_aff_get_ctx(aff), isl_error_invalid, 3119 "parameters don't match", goto error); 3120 match = isl_space_tuple_match(space, isl_dim_in, 3121 aff_space, isl_dim_set); 3122 if (match < 0) 3123 goto error; 3124 if (!match) 3125 isl_die(isl_aff_get_ctx(aff), isl_error_invalid, 3126 "domains don't match", goto error); 3127 isl_space_free(aff_space); 3128 return 0; 3129error: 3130 isl_space_free(aff_space); 3131 return -1; 3132} 3133 3134#undef BASE 3135#define BASE aff 3136 3137#include <isl_multi_templ.c> 3138 3139/* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe 3140 * domain. 3141 */ 3142__isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_multi_aff( 3143 __isl_take isl_multi_aff *ma) 3144{ 3145 isl_set *dom = isl_set_universe(isl_multi_aff_get_domain_space(ma)); 3146 return isl_pw_multi_aff_alloc(dom, ma); 3147} 3148 3149/* Create a piecewise multi-affine expression in the given space that maps each 3150 * input dimension to the corresponding output dimension. 3151 */ 3152__isl_give isl_pw_multi_aff *isl_pw_multi_aff_identity( 3153 __isl_take isl_space *space) 3154{ 3155 return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_identity(space)); 3156} 3157 3158__isl_give isl_multi_aff *isl_multi_aff_add(__isl_take isl_multi_aff *maff1, 3159 __isl_take isl_multi_aff *maff2) 3160{ 3161 return isl_multi_aff_bin_op(maff1, maff2, &isl_aff_add); 3162} 3163 3164/* Subtract "ma2" from "ma1" and return the result. 3165 */ 3166__isl_give isl_multi_aff *isl_multi_aff_sub(__isl_take isl_multi_aff *ma1, 3167 __isl_take isl_multi_aff *ma2) 3168{ 3169 return isl_multi_aff_bin_op(ma1, ma2, &isl_aff_sub); 3170} 3171 3172/* Given two multi-affine expressions A -> B and C -> D, 3173 * construct a multi-affine expression [A -> C] -> [B -> D]. 3174 */ 3175__isl_give isl_multi_aff *isl_multi_aff_product( 3176 __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2) 3177{ 3178 int i; 3179 isl_aff *aff; 3180 isl_space *space; 3181 isl_multi_aff *res; 3182 int in1, in2, out1, out2; 3183 3184 in1 = isl_multi_aff_dim(ma1, isl_dim_in); 3185 in2 = isl_multi_aff_dim(ma2, isl_dim_in); 3186 out1 = isl_multi_aff_dim(ma1, isl_dim_out); 3187 out2 = isl_multi_aff_dim(ma2, isl_dim_out); 3188 space = isl_space_product(isl_multi_aff_get_space(ma1), 3189 isl_multi_aff_get_space(ma2)); 3190 res = isl_multi_aff_alloc(isl_space_copy(space)); 3191 space = isl_space_domain(space); 3192 3193 for (i = 0; i < out1; ++i) { 3194 aff = isl_multi_aff_get_aff(ma1, i); 3195 aff = isl_aff_insert_dims(aff, isl_dim_in, in1, in2); 3196 aff = isl_aff_reset_domain_space(aff, isl_space_copy(space)); 3197 res = isl_multi_aff_set_aff(res, i, aff); 3198 } 3199 3200 for (i = 0; i < out2; ++i) { 3201 aff = isl_multi_aff_get_aff(ma2, i); 3202 aff = isl_aff_insert_dims(aff, isl_dim_in, 0, in1); 3203 aff = isl_aff_reset_domain_space(aff, isl_space_copy(space)); 3204 res = isl_multi_aff_set_aff(res, out1 + i, aff); 3205 } 3206 3207 isl_space_free(space); 3208 isl_multi_aff_free(ma1); 3209 isl_multi_aff_free(ma2); 3210 return res; 3211} 3212 3213/* Exploit the equalities in "eq" to simplify the affine expressions. 3214 */ 3215static __isl_give isl_multi_aff *isl_multi_aff_substitute_equalities( 3216 __isl_take isl_multi_aff *maff, __isl_take isl_basic_set *eq) 3217{ 3218 int i; 3219 3220 maff = isl_multi_aff_cow(maff); 3221 if (!maff || !eq) 3222 goto error; 3223 3224 for (i = 0; i < maff->n; ++i) { 3225 maff->p[i] = isl_aff_substitute_equalities(maff->p[i], 3226 isl_basic_set_copy(eq)); 3227 if (!maff->p[i]) 3228 goto error; 3229 } 3230 3231 isl_basic_set_free(eq); 3232 return maff; 3233error: 3234 isl_basic_set_free(eq); 3235 isl_multi_aff_free(maff); 3236 return NULL; 3237} 3238 3239__isl_give isl_multi_aff *isl_multi_aff_scale(__isl_take isl_multi_aff *maff, 3240 isl_int f) 3241{ 3242 int i; 3243 3244 maff = isl_multi_aff_cow(maff); 3245 if (!maff) 3246 return NULL; 3247 3248 for (i = 0; i < maff->n; ++i) { 3249 maff->p[i] = isl_aff_scale(maff->p[i], f); 3250 if (!maff->p[i]) 3251 return isl_multi_aff_free(maff); 3252 } 3253 3254 return maff; 3255} 3256 3257__isl_give isl_multi_aff *isl_multi_aff_add_on_domain(__isl_keep isl_set *dom, 3258 __isl_take isl_multi_aff *maff1, __isl_take isl_multi_aff *maff2) 3259{ 3260 maff1 = isl_multi_aff_add(maff1, maff2); 3261 maff1 = isl_multi_aff_gist(maff1, isl_set_copy(dom)); 3262 return maff1; 3263} 3264 3265int isl_multi_aff_is_empty(__isl_keep isl_multi_aff *maff) 3266{ 3267 if (!maff) 3268 return -1; 3269 3270 return 0; 3271} 3272 3273int isl_multi_aff_plain_is_equal(__isl_keep isl_multi_aff *maff1, 3274 __isl_keep isl_multi_aff *maff2) 3275{ 3276 int i; 3277 int equal; 3278 3279 if (!maff1 || !maff2) 3280 return -1; 3281 if (maff1->n != maff2->n) 3282 return 0; 3283 equal = isl_space_is_equal(maff1->space, maff2->space); 3284 if (equal < 0 || !equal) 3285 return equal; 3286 3287 for (i = 0; i < maff1->n; ++i) { 3288 equal = isl_aff_plain_is_equal(maff1->p[i], maff2->p[i]); 3289 if (equal < 0 || !equal) 3290 return equal; 3291 } 3292 3293 return 1; 3294} 3295 3296/* Return the set of domain elements where "ma1" is lexicographically 3297 * smaller than or equal to "ma2". 3298 */ 3299__isl_give isl_set *isl_multi_aff_lex_le_set(__isl_take isl_multi_aff *ma1, 3300 __isl_take isl_multi_aff *ma2) 3301{ 3302 return isl_multi_aff_lex_ge_set(ma2, ma1); 3303} 3304 3305/* Return the set of domain elements where "ma1" is lexicographically 3306 * greater than or equal to "ma2". 3307 */ 3308__isl_give isl_set *isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff *ma1, 3309 __isl_take isl_multi_aff *ma2) 3310{ 3311 isl_space *space; 3312 isl_map *map1, *map2; 3313 isl_map *map, *ge; 3314 3315 map1 = isl_map_from_multi_aff(ma1); 3316 map2 = isl_map_from_multi_aff(ma2); 3317 map = isl_map_range_product(map1, map2); 3318 space = isl_space_range(isl_map_get_space(map)); 3319 space = isl_space_domain(isl_space_unwrap(space)); 3320 ge = isl_map_lex_ge(space); 3321 map = isl_map_intersect_range(map, isl_map_wrap(ge)); 3322 3323 return isl_map_domain(map); 3324} 3325 3326#undef PW 3327#define PW isl_pw_multi_aff 3328#undef EL 3329#define EL isl_multi_aff 3330#undef EL_IS_ZERO 3331#define EL_IS_ZERO is_empty 3332#undef ZERO 3333#define ZERO empty 3334#undef IS_ZERO 3335#define IS_ZERO is_empty 3336#undef FIELD 3337#define FIELD maff 3338#undef DEFAULT_IS_ZERO 3339#define DEFAULT_IS_ZERO 0 3340 3341#define NO_NEG 3342#define NO_EVAL 3343#define NO_OPT 3344#define NO_INVOLVES_DIMS 3345#define NO_MOVE_DIMS 3346#define NO_INSERT_DIMS 3347#define NO_LIFT 3348#define NO_MORPH 3349 3350#include <isl_pw_templ.c> 3351 3352#undef UNION 3353#define UNION isl_union_pw_multi_aff 3354#undef PART 3355#define PART isl_pw_multi_aff 3356#undef PARTS 3357#define PARTS pw_multi_aff 3358#define ALIGN_DOMAIN 3359 3360#define NO_EVAL 3361 3362#include <isl_union_templ.c> 3363 3364/* Given a function "cmp" that returns the set of elements where 3365 * "ma1" is "better" than "ma2", return the intersection of this 3366 * set with "dom1" and "dom2". 3367 */ 3368static __isl_give isl_set *shared_and_better(__isl_keep isl_set *dom1, 3369 __isl_keep isl_set *dom2, __isl_keep isl_multi_aff *ma1, 3370 __isl_keep isl_multi_aff *ma2, 3371 __isl_give isl_set *(*cmp)(__isl_take isl_multi_aff *ma1, 3372 __isl_take isl_multi_aff *ma2)) 3373{ 3374 isl_set *common; 3375 isl_set *better; 3376 int is_empty; 3377 3378 common = isl_set_intersect(isl_set_copy(dom1), isl_set_copy(dom2)); 3379 is_empty = isl_set_plain_is_empty(common); 3380 if (is_empty >= 0 && is_empty) 3381 return common; 3382 if (is_empty < 0) 3383 return isl_set_free(common); 3384 better = cmp(isl_multi_aff_copy(ma1), isl_multi_aff_copy(ma2)); 3385 better = isl_set_intersect(common, better); 3386 3387 return better; 3388} 3389 3390/* Given a function "cmp" that returns the set of elements where 3391 * "ma1" is "better" than "ma2", return a piecewise multi affine 3392 * expression defined on the union of the definition domains 3393 * of "pma1" and "pma2" that maps to the "best" of "pma1" and 3394 * "pma2" on each cell. If only one of the two input functions 3395 * is defined on a given cell, then it is considered the best. 3396 */ 3397static __isl_give isl_pw_multi_aff *pw_multi_aff_union_opt( 3398 __isl_take isl_pw_multi_aff *pma1, 3399 __isl_take isl_pw_multi_aff *pma2, 3400 __isl_give isl_set *(*cmp)(__isl_take isl_multi_aff *ma1, 3401 __isl_take isl_multi_aff *ma2)) 3402{ 3403 int i, j, n; 3404 isl_pw_multi_aff *res = NULL; 3405 isl_ctx *ctx; 3406 isl_set *set = NULL; 3407 3408 if (!pma1 || !pma2) 3409 goto error; 3410 3411 ctx = isl_space_get_ctx(pma1->dim); 3412 if (!isl_space_is_equal(pma1->dim, pma2->dim)) 3413 isl_die(ctx, isl_error_invalid, 3414 "arguments should live in the same space", goto error); 3415 3416 if (isl_pw_multi_aff_is_empty(pma1)) { 3417 isl_pw_multi_aff_free(pma1); 3418 return pma2; 3419 } 3420 3421 if (isl_pw_multi_aff_is_empty(pma2)) { 3422 isl_pw_multi_aff_free(pma2); 3423 return pma1; 3424 } 3425 3426 n = 2 * (pma1->n + 1) * (pma2->n + 1); 3427 res = isl_pw_multi_aff_alloc_size(isl_space_copy(pma1->dim), n); 3428 3429 for (i = 0; i < pma1->n; ++i) { 3430 set = isl_set_copy(pma1->p[i].set); 3431 for (j = 0; j < pma2->n; ++j) { 3432 isl_set *better; 3433 int is_empty; 3434 3435 better = shared_and_better(pma2->p[j].set, 3436 pma1->p[i].set, pma2->p[j].maff, 3437 pma1->p[i].maff, cmp); 3438 is_empty = isl_set_plain_is_empty(better); 3439 if (is_empty < 0 || is_empty) { 3440 isl_set_free(better); 3441 if (is_empty < 0) 3442 goto error; 3443 continue; 3444 } 3445 set = isl_set_subtract(set, isl_set_copy(better)); 3446 3447 res = isl_pw_multi_aff_add_piece(res, better, 3448 isl_multi_aff_copy(pma2->p[j].maff)); 3449 } 3450 res = isl_pw_multi_aff_add_piece(res, set, 3451 isl_multi_aff_copy(pma1->p[i].maff)); 3452 } 3453 3454 for (j = 0; j < pma2->n; ++j) { 3455 set = isl_set_copy(pma2->p[j].set); 3456 for (i = 0; i < pma1->n; ++i) 3457 set = isl_set_subtract(set, 3458 isl_set_copy(pma1->p[i].set)); 3459 res = isl_pw_multi_aff_add_piece(res, set, 3460 isl_multi_aff_copy(pma2->p[j].maff)); 3461 } 3462 3463 isl_pw_multi_aff_free(pma1); 3464 isl_pw_multi_aff_free(pma2); 3465 3466 return res; 3467error: 3468 isl_pw_multi_aff_free(pma1); 3469 isl_pw_multi_aff_free(pma2); 3470 isl_set_free(set); 3471 return isl_pw_multi_aff_free(res); 3472} 3473 3474static __isl_give isl_pw_multi_aff *pw_multi_aff_union_lexmax( 3475 __isl_take isl_pw_multi_aff *pma1, 3476 __isl_take isl_pw_multi_aff *pma2) 3477{ 3478 return pw_multi_aff_union_opt(pma1, pma2, &isl_multi_aff_lex_ge_set); 3479} 3480 3481/* Given two piecewise multi affine expressions, return a piecewise 3482 * multi-affine expression defined on the union of the definition domains 3483 * of the inputs that is equal to the lexicographic maximum of the two 3484 * inputs on each cell. If only one of the two inputs is defined on 3485 * a given cell, then it is considered to be the maximum. 3486 */ 3487__isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_lexmax( 3488 __isl_take isl_pw_multi_aff *pma1, 3489 __isl_take isl_pw_multi_aff *pma2) 3490{ 3491 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2, 3492 &pw_multi_aff_union_lexmax); 3493} 3494 3495static __isl_give isl_pw_multi_aff *pw_multi_aff_union_lexmin( 3496 __isl_take isl_pw_multi_aff *pma1, 3497 __isl_take isl_pw_multi_aff *pma2) 3498{ 3499 return pw_multi_aff_union_opt(pma1, pma2, &isl_multi_aff_lex_le_set); 3500} 3501 3502/* Given two piecewise multi affine expressions, return a piecewise 3503 * multi-affine expression defined on the union of the definition domains 3504 * of the inputs that is equal to the lexicographic minimum of the two 3505 * inputs on each cell. If only one of the two inputs is defined on 3506 * a given cell, then it is considered to be the minimum. 3507 */ 3508__isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_lexmin( 3509 __isl_take isl_pw_multi_aff *pma1, 3510 __isl_take isl_pw_multi_aff *pma2) 3511{ 3512 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2, 3513 &pw_multi_aff_union_lexmin); 3514} 3515 3516static __isl_give isl_pw_multi_aff *pw_multi_aff_add( 3517 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2) 3518{ 3519 return isl_pw_multi_aff_on_shared_domain(pma1, pma2, 3520 &isl_multi_aff_add); 3521} 3522 3523__isl_give isl_pw_multi_aff *isl_pw_multi_aff_add( 3524 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2) 3525{ 3526 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2, 3527 &pw_multi_aff_add); 3528} 3529 3530static __isl_give isl_pw_multi_aff *pw_multi_aff_sub( 3531 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2) 3532{ 3533 return isl_pw_multi_aff_on_shared_domain(pma1, pma2, 3534 &isl_multi_aff_sub); 3535} 3536 3537/* Subtract "pma2" from "pma1" and return the result. 3538 */ 3539__isl_give isl_pw_multi_aff *isl_pw_multi_aff_sub( 3540 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2) 3541{ 3542 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2, 3543 &pw_multi_aff_sub); 3544} 3545 3546__isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_add( 3547 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2) 3548{ 3549 return isl_pw_multi_aff_union_add_(pma1, pma2); 3550} 3551 3552/* Given two piecewise multi-affine expressions A -> B and C -> D, 3553 * construct a piecewise multi-affine expression [A -> C] -> [B -> D]. 3554 */ 3555static __isl_give isl_pw_multi_aff *pw_multi_aff_product( 3556 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2) 3557{ 3558 int i, j, n; 3559 isl_space *space; 3560 isl_pw_multi_aff *res; 3561 3562 if (!pma1 || !pma2) 3563 goto error; 3564 3565 n = pma1->n * pma2->n; 3566 space = isl_space_product(isl_space_copy(pma1->dim), 3567 isl_space_copy(pma2->dim)); 3568 res = isl_pw_multi_aff_alloc_size(space, n); 3569 3570 for (i = 0; i < pma1->n; ++i) { 3571 for (j = 0; j < pma2->n; ++j) { 3572 isl_set *domain; 3573 isl_multi_aff *ma; 3574 3575 domain = isl_set_product(isl_set_copy(pma1->p[i].set), 3576 isl_set_copy(pma2->p[j].set)); 3577 ma = isl_multi_aff_product( 3578 isl_multi_aff_copy(pma1->p[i].maff), 3579 isl_multi_aff_copy(pma2->p[j].maff)); 3580 res = isl_pw_multi_aff_add_piece(res, domain, ma); 3581 } 3582 } 3583 3584 isl_pw_multi_aff_free(pma1); 3585 isl_pw_multi_aff_free(pma2); 3586 return res; 3587error: 3588 isl_pw_multi_aff_free(pma1); 3589 isl_pw_multi_aff_free(pma2); 3590 return NULL; 3591} 3592 3593__isl_give isl_pw_multi_aff *isl_pw_multi_aff_product( 3594 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2) 3595{ 3596 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2, 3597 &pw_multi_aff_product); 3598} 3599 3600/* Construct a map mapping the domain of the piecewise multi-affine expression 3601 * to its range, with each dimension in the range equated to the 3602 * corresponding affine expression on its cell. 3603 */ 3604__isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma) 3605{ 3606 int i; 3607 isl_map *map; 3608 3609 if (!pma) 3610 return NULL; 3611 3612 map = isl_map_empty(isl_pw_multi_aff_get_space(pma)); 3613 3614 for (i = 0; i < pma->n; ++i) { 3615 isl_multi_aff *maff; 3616 isl_basic_map *bmap; 3617 isl_map *map_i; 3618 3619 maff = isl_multi_aff_copy(pma->p[i].maff); 3620 bmap = isl_basic_map_from_multi_aff(maff); 3621 map_i = isl_map_from_basic_map(bmap); 3622 map_i = isl_map_intersect_domain(map_i, 3623 isl_set_copy(pma->p[i].set)); 3624 map = isl_map_union_disjoint(map, map_i); 3625 } 3626 3627 isl_pw_multi_aff_free(pma); 3628 return map; 3629} 3630 3631__isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma) 3632{ 3633 if (!pma) 3634 return NULL; 3635 3636 if (!isl_space_is_set(pma->dim)) 3637 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid, 3638 "isl_pw_multi_aff cannot be converted into an isl_set", 3639 return isl_pw_multi_aff_free(pma)); 3640 3641 return isl_map_from_pw_multi_aff(pma); 3642} 3643 3644/* Given a basic map with a single output dimension that is defined 3645 * in terms of the parameters and input dimensions using an equality, 3646 * extract an isl_aff that expresses the output dimension in terms 3647 * of the parameters and input dimensions. 3648 * 3649 * Since some applications expect the result of isl_pw_multi_aff_from_map 3650 * to only contain integer affine expressions, we compute the floor 3651 * of the expression before returning. 3652 * 3653 * This function shares some similarities with 3654 * isl_basic_map_has_defining_equality and isl_constraint_get_bound. 3655 */ 3656static __isl_give isl_aff *extract_isl_aff_from_basic_map( 3657 __isl_take isl_basic_map *bmap) 3658{ 3659 int i; 3660 unsigned offset; 3661 unsigned total; 3662 isl_local_space *ls; 3663 isl_aff *aff; 3664 3665 if (!bmap) 3666 return NULL; 3667 if (isl_basic_map_dim(bmap, isl_dim_out) != 1) 3668 isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid, 3669 "basic map should have a single output dimension", 3670 goto error); 3671 offset = isl_basic_map_offset(bmap, isl_dim_out); 3672 total = isl_basic_map_total_dim(bmap); 3673 for (i = 0; i < bmap->n_eq; ++i) { 3674 if (isl_int_is_zero(bmap->eq[i][offset])) 3675 continue; 3676 if (isl_seq_first_non_zero(bmap->eq[i] + offset + 1, 3677 1 + total - (offset + 1)) != -1) 3678 continue; 3679 break; 3680 } 3681 if (i >= bmap->n_eq) 3682 isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid, 3683 "unable to find suitable equality", goto error); 3684 ls = isl_basic_map_get_local_space(bmap); 3685 aff = isl_aff_alloc(isl_local_space_domain(ls)); 3686 if (!aff) 3687 goto error; 3688 if (isl_int_is_neg(bmap->eq[i][offset])) 3689 isl_seq_cpy(aff->v->el + 1, bmap->eq[i], offset); 3690 else 3691 isl_seq_neg(aff->v->el + 1, bmap->eq[i], offset); 3692 isl_seq_clr(aff->v->el + 1 + offset, aff->v->size - (1 + offset)); 3693 isl_int_abs(aff->v->el[0], bmap->eq[i][offset]); 3694 isl_basic_map_free(bmap); 3695 3696 aff = isl_aff_remove_unused_divs(aff); 3697 aff = isl_aff_floor(aff); 3698 return aff; 3699error: 3700 isl_basic_map_free(bmap); 3701 return NULL; 3702} 3703 3704/* Given a basic map where each output dimension is defined 3705 * in terms of the parameters and input dimensions using an equality, 3706 * extract an isl_multi_aff that expresses the output dimensions in terms 3707 * of the parameters and input dimensions. 3708 */ 3709static __isl_give isl_multi_aff *extract_isl_multi_aff_from_basic_map( 3710 __isl_take isl_basic_map *bmap) 3711{ 3712 int i; 3713 unsigned n_out; 3714 isl_multi_aff *ma; 3715 3716 if (!bmap) 3717 return NULL; 3718 3719 ma = isl_multi_aff_alloc(isl_basic_map_get_space(bmap)); 3720 n_out = isl_basic_map_dim(bmap, isl_dim_out); 3721 3722 for (i = 0; i < n_out; ++i) { 3723 isl_basic_map *bmap_i; 3724 isl_aff *aff; 3725 3726 bmap_i = isl_basic_map_copy(bmap); 3727 bmap_i = isl_basic_map_project_out(bmap_i, isl_dim_out, 3728 i + 1, n_out - (1 + i)); 3729 bmap_i = isl_basic_map_project_out(bmap_i, isl_dim_out, 0, i); 3730 aff = extract_isl_aff_from_basic_map(bmap_i); 3731 ma = isl_multi_aff_set_aff(ma, i, aff); 3732 } 3733 3734 isl_basic_map_free(bmap); 3735 3736 return ma; 3737} 3738 3739/* Create an isl_pw_multi_aff that is equivalent to 3740 * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain). 3741 * The given basic map is such that each output dimension is defined 3742 * in terms of the parameters and input dimensions using an equality. 3743 */ 3744static __isl_give isl_pw_multi_aff *plain_pw_multi_aff_from_map( 3745 __isl_take isl_set *domain, __isl_take isl_basic_map *bmap) 3746{ 3747 isl_multi_aff *ma; 3748 3749 ma = extract_isl_multi_aff_from_basic_map(bmap); 3750 return isl_pw_multi_aff_alloc(domain, ma); 3751} 3752 3753/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map. 3754 * This obviously only works if the input "map" is single-valued. 3755 * If so, we compute the lexicographic minimum of the image in the form 3756 * of an isl_pw_multi_aff. Since the image is unique, it is equal 3757 * to its lexicographic minimum. 3758 * If the input is not single-valued, we produce an error. 3759 */ 3760static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_base( 3761 __isl_take isl_map *map) 3762{ 3763 int i; 3764 int sv; 3765 isl_pw_multi_aff *pma; 3766 3767 sv = isl_map_is_single_valued(map); 3768 if (sv < 0) 3769 goto error; 3770 if (!sv) 3771 isl_die(isl_map_get_ctx(map), isl_error_invalid, 3772 "map is not single-valued", goto error); 3773 map = isl_map_make_disjoint(map); 3774 if (!map) 3775 return NULL; 3776 3777 pma = isl_pw_multi_aff_empty(isl_map_get_space(map)); 3778 3779 for (i = 0; i < map->n; ++i) { 3780 isl_pw_multi_aff *pma_i; 3781 isl_basic_map *bmap; 3782 bmap = isl_basic_map_copy(map->p[i]); 3783 pma_i = isl_basic_map_lexmin_pw_multi_aff(bmap); 3784 pma = isl_pw_multi_aff_add_disjoint(pma, pma_i); 3785 } 3786 3787 isl_map_free(map); 3788 return pma; 3789error: 3790 isl_map_free(map); 3791 return NULL; 3792} 3793 3794/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map, 3795 * taking into account that the output dimension at position "d" 3796 * can be represented as 3797 * 3798 * x = floor((e(...) + c1) / m) 3799 * 3800 * given that constraint "i" is of the form 3801 * 3802 * e(...) + c1 - m x >= 0 3803 * 3804 * 3805 * Let "map" be of the form 3806 * 3807 * A -> B 3808 * 3809 * We construct a mapping 3810 * 3811 * A -> [A -> x = floor(...)] 3812 * 3813 * apply that to the map, obtaining 3814 * 3815 * [A -> x = floor(...)] -> B 3816 * 3817 * and equate dimension "d" to x. 3818 * We then compute a isl_pw_multi_aff representation of the resulting map 3819 * and plug in the mapping above. 3820 */ 3821static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_div( 3822 __isl_take isl_map *map, __isl_take isl_basic_map *hull, int d, int i) 3823{ 3824 isl_ctx *ctx; 3825 isl_space *space; 3826 isl_local_space *ls; 3827 isl_multi_aff *ma; 3828 isl_aff *aff; 3829 isl_vec *v; 3830 isl_map *insert; 3831 int offset; 3832 int n; 3833 int n_in; 3834 isl_pw_multi_aff *pma; 3835 int is_set; 3836 3837 is_set = isl_map_is_set(map); 3838 3839 offset = isl_basic_map_offset(hull, isl_dim_out); 3840 ctx = isl_map_get_ctx(map); 3841 space = isl_space_domain(isl_map_get_space(map)); 3842 n_in = isl_space_dim(space, isl_dim_set); 3843 n = isl_space_dim(space, isl_dim_all); 3844 3845 v = isl_vec_alloc(ctx, 1 + 1 + n); 3846 if (v) { 3847 isl_int_neg(v->el[0], hull->ineq[i][offset + d]); 3848 isl_seq_cpy(v->el + 1, hull->ineq[i], 1 + n); 3849 } 3850 isl_basic_map_free(hull); 3851 3852 ls = isl_local_space_from_space(isl_space_copy(space)); 3853 aff = isl_aff_alloc_vec(ls, v); 3854 aff = isl_aff_floor(aff); 3855 if (is_set) { 3856 isl_space_free(space); 3857 ma = isl_multi_aff_from_aff(aff); 3858 } else { 3859 ma = isl_multi_aff_identity(isl_space_map_from_set(space)); 3860 ma = isl_multi_aff_range_product(ma, 3861 isl_multi_aff_from_aff(aff)); 3862 } 3863 3864 insert = isl_map_from_multi_aff(isl_multi_aff_copy(ma)); 3865 map = isl_map_apply_domain(map, insert); 3866 map = isl_map_equate(map, isl_dim_in, n_in, isl_dim_out, d); 3867 pma = isl_pw_multi_aff_from_map(map); 3868 pma = isl_pw_multi_aff_pullback_multi_aff(pma, ma); 3869 3870 return pma; 3871} 3872 3873/* Is constraint "c" of the form 3874 * 3875 * e(...) + c1 - m x >= 0 3876 * 3877 * or 3878 * 3879 * -e(...) + c2 + m x >= 0 3880 * 3881 * where m > 1 and e only depends on parameters and input dimemnsions? 3882 * 3883 * "offset" is the offset of the output dimensions 3884 * "pos" is the position of output dimension x. 3885 */ 3886static int is_potential_div_constraint(isl_int *c, int offset, int d, int total) 3887{ 3888 if (isl_int_is_zero(c[offset + d])) 3889 return 0; 3890 if (isl_int_is_one(c[offset + d])) 3891 return 0; 3892 if (isl_int_is_negone(c[offset + d])) 3893 return 0; 3894 if (isl_seq_first_non_zero(c + offset, d) != -1) 3895 return 0; 3896 if (isl_seq_first_non_zero(c + offset + d + 1, 3897 total - (offset + d + 1)) != -1) 3898 return 0; 3899 return 1; 3900} 3901 3902/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map. 3903 * 3904 * As a special case, we first check if there is any pair of constraints, 3905 * shared by all the basic maps in "map" that force a given dimension 3906 * to be equal to the floor of some affine combination of the input dimensions. 3907 * 3908 * In particular, if we can find two constraints 3909 * 3910 * e(...) + c1 - m x >= 0 i.e., m x <= e(...) + c1 3911 * 3912 * and 3913 * 3914 * -e(...) + c2 + m x >= 0 i.e., m x >= e(...) - c2 3915 * 3916 * where m > 1 and e only depends on parameters and input dimemnsions, 3917 * and such that 3918 * 3919 * c1 + c2 < m i.e., -c2 >= c1 - (m - 1) 3920 * 3921 * then we know that we can take 3922 * 3923 * x = floor((e(...) + c1) / m) 3924 * 3925 * without having to perform any computation. 3926 * 3927 * Note that we know that 3928 * 3929 * c1 + c2 >= 1 3930 * 3931 * If c1 + c2 were 0, then we would have detected an equality during 3932 * simplification. If c1 + c2 were negative, then we would have detected 3933 * a contradiction. 3934 */ 3935static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_check_div( 3936 __isl_take isl_map *map) 3937{ 3938 int d, dim; 3939 int i, j, n; 3940 int offset, total; 3941 isl_int sum; 3942 isl_basic_map *hull; 3943 3944 hull = isl_map_unshifted_simple_hull(isl_map_copy(map)); 3945 if (!hull) 3946 goto error; 3947 3948 isl_int_init(sum); 3949 dim = isl_map_dim(map, isl_dim_out); 3950 offset = isl_basic_map_offset(hull, isl_dim_out); 3951 total = 1 + isl_basic_map_total_dim(hull); 3952 n = hull->n_ineq; 3953 for (d = 0; d < dim; ++d) { 3954 for (i = 0; i < n; ++i) { 3955 if (!is_potential_div_constraint(hull->ineq[i], 3956 offset, d, total)) 3957 continue; 3958 for (j = i + 1; j < n; ++j) { 3959 if (!isl_seq_is_neg(hull->ineq[i] + 1, 3960 hull->ineq[j] + 1, total - 1)) 3961 continue; 3962 isl_int_add(sum, hull->ineq[i][0], 3963 hull->ineq[j][0]); 3964 if (isl_int_abs_lt(sum, 3965 hull->ineq[i][offset + d])) 3966 break; 3967 3968 } 3969 if (j >= n) 3970 continue; 3971 isl_int_clear(sum); 3972 if (isl_int_is_pos(hull->ineq[j][offset + d])) 3973 j = i; 3974 return pw_multi_aff_from_map_div(map, hull, d, j); 3975 } 3976 } 3977 isl_int_clear(sum); 3978 isl_basic_map_free(hull); 3979 return pw_multi_aff_from_map_base(map); 3980error: 3981 isl_map_free(map); 3982 isl_basic_map_free(hull); 3983 return NULL; 3984} 3985 3986/* Given an affine expression 3987 * 3988 * [A -> B] -> f(A,B) 3989 * 3990 * construct an isl_multi_aff 3991 * 3992 * [A -> B] -> B' 3993 * 3994 * such that dimension "d" in B' is set to "aff" and the remaining 3995 * dimensions are set equal to the corresponding dimensions in B. 3996 * "n_in" is the dimension of the space A. 3997 * "n_out" is the dimension of the space B. 3998 * 3999 * If "is_set" is set, then the affine expression is of the form 4000 * 4001 * [B] -> f(B) 4002 * 4003 * and we construct an isl_multi_aff 4004 * 4005 * B -> B' 4006 */ 4007static __isl_give isl_multi_aff *range_map(__isl_take isl_aff *aff, int d, 4008 unsigned n_in, unsigned n_out, int is_set) 4009{ 4010 int i; 4011 isl_multi_aff *ma; 4012 isl_space *space, *space2; 4013 isl_local_space *ls; 4014 4015 space = isl_aff_get_domain_space(aff); 4016 ls = isl_local_space_from_space(isl_space_copy(space)); 4017 space2 = isl_space_copy(space); 4018 if (!is_set) 4019 space2 = isl_space_range(isl_space_unwrap(space2)); 4020 space = isl_space_map_from_domain_and_range(space, space2); 4021 ma = isl_multi_aff_alloc(space); 4022 ma = isl_multi_aff_set_aff(ma, d, aff); 4023 4024 for (i = 0; i < n_out; ++i) { 4025 if (i == d) 4026 continue; 4027 aff = isl_aff_var_on_domain(isl_local_space_copy(ls), 4028 isl_dim_set, n_in + i); 4029 ma = isl_multi_aff_set_aff(ma, i, aff); 4030 } 4031 4032 isl_local_space_free(ls); 4033 4034 return ma; 4035} 4036 4037/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map, 4038 * taking into account that the dimension at position "d" can be written as 4039 * 4040 * x = m a + f(..) (1) 4041 * 4042 * where m is equal to "gcd". 4043 * "i" is the index of the equality in "hull" that defines f(..). 4044 * In particular, the equality is of the form 4045 * 4046 * f(..) - x + m g(existentials) = 0 4047 * 4048 * or 4049 * 4050 * -f(..) + x + m g(existentials) = 0 4051 * 4052 * We basically plug (1) into "map", resulting in a map with "a" 4053 * in the range instead of "x". The corresponding isl_pw_multi_aff 4054 * defining "a" is then plugged back into (1) to obtain a definition fro "x". 4055 * 4056 * Specifically, given the input map 4057 * 4058 * A -> B 4059 * 4060 * We first wrap it into a set 4061 * 4062 * [A -> B] 4063 * 4064 * and define (1) on top of the corresponding space, resulting in "aff". 4065 * We use this to create an isl_multi_aff that maps the output position "d" 4066 * from "a" to "x", leaving all other (intput and output) dimensions unchanged. 4067 * We plug this into the wrapped map, unwrap the result and compute the 4068 * corresponding isl_pw_multi_aff. 4069 * The result is an expression 4070 * 4071 * A -> T(A) 4072 * 4073 * We adjust that to 4074 * 4075 * A -> [A -> T(A)] 4076 * 4077 * so that we can plug that into "aff", after extending the latter to 4078 * a mapping 4079 * 4080 * [A -> B] -> B' 4081 * 4082 * 4083 * If "map" is actually a set, then there is no "A" space, meaning 4084 * that we do not need to perform any wrapping, and that the result 4085 * of the recursive call is of the form 4086 * 4087 * [T] 4088 * 4089 * which is plugged into a mapping of the form 4090 * 4091 * B -> B' 4092 */ 4093static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_stride( 4094 __isl_take isl_map *map, __isl_take isl_basic_map *hull, int d, int i, 4095 isl_int gcd) 4096{ 4097 isl_set *set; 4098 isl_space *space; 4099 isl_local_space *ls; 4100 isl_aff *aff; 4101 isl_multi_aff *ma; 4102 isl_pw_multi_aff *pma, *id; 4103 unsigned n_in; 4104 unsigned o_out; 4105 unsigned n_out; 4106 int is_set; 4107 4108 is_set = isl_map_is_set(map); 4109 4110 n_in = isl_basic_map_dim(hull, isl_dim_in); 4111 n_out = isl_basic_map_dim(hull, isl_dim_out); 4112 o_out = isl_basic_map_offset(hull, isl_dim_out); 4113 4114 if (is_set) 4115 set = map; 4116 else 4117 set = isl_map_wrap(map); 4118 space = isl_space_map_from_set(isl_set_get_space(set)); 4119 ma = isl_multi_aff_identity(space); 4120 ls = isl_local_space_from_space(isl_set_get_space(set)); 4121 aff = isl_aff_alloc(ls); 4122 if (aff) { 4123 isl_int_set_si(aff->v->el[0], 1); 4124 if (isl_int_is_one(hull->eq[i][o_out + d])) 4125 isl_seq_neg(aff->v->el + 1, hull->eq[i], 4126 aff->v->size - 1); 4127 else 4128 isl_seq_cpy(aff->v->el + 1, hull->eq[i], 4129 aff->v->size - 1); 4130 isl_int_set(aff->v->el[1 + o_out + d], gcd); 4131 } 4132 ma = isl_multi_aff_set_aff(ma, n_in + d, isl_aff_copy(aff)); 4133 set = isl_set_preimage_multi_aff(set, ma); 4134 4135 ma = range_map(aff, d, n_in, n_out, is_set); 4136 4137 if (is_set) 4138 map = set; 4139 else 4140 map = isl_set_unwrap(set); 4141 pma = isl_pw_multi_aff_from_map(set); 4142 4143 if (!is_set) { 4144 space = isl_pw_multi_aff_get_domain_space(pma); 4145 space = isl_space_map_from_set(space); 4146 id = isl_pw_multi_aff_identity(space); 4147 pma = isl_pw_multi_aff_range_product(id, pma); 4148 } 4149 id = isl_pw_multi_aff_from_multi_aff(ma); 4150 pma = isl_pw_multi_aff_pullback_pw_multi_aff(id, pma); 4151 4152 isl_basic_map_free(hull); 4153 return pma; 4154} 4155 4156/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map. 4157 * 4158 * As a special case, we first check if all output dimensions are uniquely 4159 * defined in terms of the parameters and input dimensions over the entire 4160 * domain. If so, we extract the desired isl_pw_multi_aff directly 4161 * from the affine hull of "map" and its domain. 4162 * 4163 * Otherwise, we check if any of the output dimensions is "strided". 4164 * That is, we check if can be written as 4165 * 4166 * x = m a + f(..) 4167 * 4168 * with m greater than 1, a some combination of existentiall quantified 4169 * variables and f and expression in the parameters and input dimensions. 4170 * If so, we remove the stride in pw_multi_aff_from_map_stride. 4171 * 4172 * Otherwise, we continue with pw_multi_aff_from_map_check_div for a further 4173 * special case. 4174 */ 4175__isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_map(__isl_take isl_map *map) 4176{ 4177 int i, j; 4178 int sv; 4179 isl_basic_map *hull; 4180 unsigned n_out; 4181 unsigned o_out; 4182 unsigned n_div; 4183 unsigned o_div; 4184 isl_int gcd; 4185 4186 if (!map) 4187 return NULL; 4188 4189 hull = isl_map_affine_hull(isl_map_copy(map)); 4190 sv = isl_basic_map_plain_is_single_valued(hull); 4191 if (sv >= 0 && sv) 4192 return plain_pw_multi_aff_from_map(isl_map_domain(map), hull); 4193 if (sv < 0) 4194 hull = isl_basic_map_free(hull); 4195 if (!hull) 4196 goto error; 4197 4198 n_div = isl_basic_map_dim(hull, isl_dim_div); 4199 o_div = isl_basic_map_offset(hull, isl_dim_div); 4200 4201 if (n_div == 0) { 4202 isl_basic_map_free(hull); 4203 return pw_multi_aff_from_map_check_div(map); 4204 } 4205 4206 isl_int_init(gcd); 4207 4208 n_out = isl_basic_map_dim(hull, isl_dim_out); 4209 o_out = isl_basic_map_offset(hull, isl_dim_out); 4210 4211 for (i = 0; i < n_out; ++i) { 4212 for (j = 0; j < hull->n_eq; ++j) { 4213 isl_int *eq = hull->eq[j]; 4214 isl_pw_multi_aff *res; 4215 4216 if (!isl_int_is_one(eq[o_out + i]) && 4217 !isl_int_is_negone(eq[o_out + i])) 4218 continue; 4219 if (isl_seq_first_non_zero(eq + o_out, i) != -1) 4220 continue; 4221 if (isl_seq_first_non_zero(eq + o_out + i + 1, 4222 n_out - (i + 1)) != -1) 4223 continue; 4224 isl_seq_gcd(eq + o_div, n_div, &gcd); 4225 if (isl_int_is_zero(gcd)) 4226 continue; 4227 if (isl_int_is_one(gcd)) 4228 continue; 4229 4230 res = pw_multi_aff_from_map_stride(map, hull, 4231 i, j, gcd); 4232 isl_int_clear(gcd); 4233 return res; 4234 } 4235 } 4236 4237 isl_int_clear(gcd); 4238 isl_basic_map_free(hull); 4239 return pw_multi_aff_from_map_check_div(map); 4240error: 4241 isl_map_free(map); 4242 return NULL; 4243} 4244 4245__isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_set(__isl_take isl_set *set) 4246{ 4247 return isl_pw_multi_aff_from_map(set); 4248} 4249 4250/* Convert "map" into an isl_pw_multi_aff (if possible) and 4251 * add it to *user. 4252 */ 4253static int pw_multi_aff_from_map(__isl_take isl_map *map, void *user) 4254{ 4255 isl_union_pw_multi_aff **upma = user; 4256 isl_pw_multi_aff *pma; 4257 4258 pma = isl_pw_multi_aff_from_map(map); 4259 *upma = isl_union_pw_multi_aff_add_pw_multi_aff(*upma, pma); 4260 4261 return *upma ? 0 : -1; 4262} 4263 4264/* Try and create an isl_union_pw_multi_aff that is equivalent 4265 * to the given isl_union_map. 4266 * The isl_union_map is required to be single-valued in each space. 4267 * Otherwise, an error is produced. 4268 */ 4269__isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_from_union_map( 4270 __isl_take isl_union_map *umap) 4271{ 4272 isl_space *space; 4273 isl_union_pw_multi_aff *upma; 4274 4275 space = isl_union_map_get_space(umap); 4276 upma = isl_union_pw_multi_aff_empty(space); 4277 if (isl_union_map_foreach_map(umap, &pw_multi_aff_from_map, &upma) < 0) 4278 upma = isl_union_pw_multi_aff_free(upma); 4279 isl_union_map_free(umap); 4280 4281 return upma; 4282} 4283 4284/* Try and create an isl_union_pw_multi_aff that is equivalent 4285 * to the given isl_union_set. 4286 * The isl_union_set is required to be a singleton in each space. 4287 * Otherwise, an error is produced. 4288 */ 4289__isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_from_union_set( 4290 __isl_take isl_union_set *uset) 4291{ 4292 return isl_union_pw_multi_aff_from_union_map(uset); 4293} 4294 4295/* Return the piecewise affine expression "set ? 1 : 0". 4296 */ 4297__isl_give isl_pw_aff *isl_set_indicator_function(__isl_take isl_set *set) 4298{ 4299 isl_pw_aff *pa; 4300 isl_space *space = isl_set_get_space(set); 4301 isl_local_space *ls = isl_local_space_from_space(space); 4302 isl_aff *zero = isl_aff_zero_on_domain(isl_local_space_copy(ls)); 4303 isl_aff *one = isl_aff_zero_on_domain(ls); 4304 4305 one = isl_aff_add_constant_si(one, 1); 4306 pa = isl_pw_aff_alloc(isl_set_copy(set), one); 4307 set = isl_set_complement(set); 4308 pa = isl_pw_aff_add_disjoint(pa, isl_pw_aff_alloc(set, zero)); 4309 4310 return pa; 4311} 4312 4313/* Plug in "subs" for dimension "type", "pos" of "aff". 4314 * 4315 * Let i be the dimension to replace and let "subs" be of the form 4316 * 4317 * f/d 4318 * 4319 * and "aff" of the form 4320 * 4321 * (a i + g)/m 4322 * 4323 * The result is 4324 * 4325 * (a f + d g')/(m d) 4326 * 4327 * where g' is the result of plugging in "subs" in each of the integer 4328 * divisions in g. 4329 */ 4330__isl_give isl_aff *isl_aff_substitute(__isl_take isl_aff *aff, 4331 enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs) 4332{ 4333 isl_ctx *ctx; 4334 isl_int v; 4335 4336 aff = isl_aff_cow(aff); 4337 if (!aff || !subs) 4338 return isl_aff_free(aff); 4339 4340 ctx = isl_aff_get_ctx(aff); 4341 if (!isl_space_is_equal(aff->ls->dim, subs->ls->dim)) 4342 isl_die(ctx, isl_error_invalid, 4343 "spaces don't match", return isl_aff_free(aff)); 4344 if (isl_local_space_dim(subs->ls, isl_dim_div) != 0) 4345 isl_die(ctx, isl_error_unsupported, 4346 "cannot handle divs yet", return isl_aff_free(aff)); 4347 4348 aff->ls = isl_local_space_substitute(aff->ls, type, pos, subs); 4349 if (!aff->ls) 4350 return isl_aff_free(aff); 4351 4352 aff->v = isl_vec_cow(aff->v); 4353 if (!aff->v) 4354 return isl_aff_free(aff); 4355 4356 pos += isl_local_space_offset(aff->ls, type); 4357 4358 isl_int_init(v); 4359 isl_seq_substitute(aff->v->el, pos, subs->v->el, 4360 aff->v->size, subs->v->size, v); 4361 isl_int_clear(v); 4362 4363 return aff; 4364} 4365 4366/* Plug in "subs" for dimension "type", "pos" in each of the affine 4367 * expressions in "maff". 4368 */ 4369__isl_give isl_multi_aff *isl_multi_aff_substitute( 4370 __isl_take isl_multi_aff *maff, enum isl_dim_type type, unsigned pos, 4371 __isl_keep isl_aff *subs) 4372{ 4373 int i; 4374 4375 maff = isl_multi_aff_cow(maff); 4376 if (!maff || !subs) 4377 return isl_multi_aff_free(maff); 4378 4379 if (type == isl_dim_in) 4380 type = isl_dim_set; 4381 4382 for (i = 0; i < maff->n; ++i) { 4383 maff->p[i] = isl_aff_substitute(maff->p[i], type, pos, subs); 4384 if (!maff->p[i]) 4385 return isl_multi_aff_free(maff); 4386 } 4387 4388 return maff; 4389} 4390 4391/* Plug in "subs" for dimension "type", "pos" of "pma". 4392 * 4393 * pma is of the form 4394 * 4395 * A_i(v) -> M_i(v) 4396 * 4397 * while subs is of the form 4398 * 4399 * v' = B_j(v) -> S_j 4400 * 4401 * Each pair i,j such that C_ij = A_i \cap B_i is non-empty 4402 * has a contribution in the result, in particular 4403 * 4404 * C_ij(S_j) -> M_i(S_j) 4405 * 4406 * Note that plugging in S_j in C_ij may also result in an empty set 4407 * and this contribution should simply be discarded. 4408 */ 4409__isl_give isl_pw_multi_aff *isl_pw_multi_aff_substitute( 4410 __isl_take isl_pw_multi_aff *pma, enum isl_dim_type type, unsigned pos, 4411 __isl_keep isl_pw_aff *subs) 4412{ 4413 int i, j, n; 4414 isl_pw_multi_aff *res; 4415 4416 if (!pma || !subs) 4417 return isl_pw_multi_aff_free(pma); 4418 4419 n = pma->n * subs->n; 4420 res = isl_pw_multi_aff_alloc_size(isl_space_copy(pma->dim), n); 4421 4422 for (i = 0; i < pma->n; ++i) { 4423 for (j = 0; j < subs->n; ++j) { 4424 isl_set *common; 4425 isl_multi_aff *res_ij; 4426 int empty; 4427 4428 common = isl_set_intersect( 4429 isl_set_copy(pma->p[i].set), 4430 isl_set_copy(subs->p[j].set)); 4431 common = isl_set_substitute(common, 4432 type, pos, subs->p[j].aff); 4433 empty = isl_set_plain_is_empty(common); 4434 if (empty < 0 || empty) { 4435 isl_set_free(common); 4436 if (empty < 0) 4437 goto error; 4438 continue; 4439 } 4440 4441 res_ij = isl_multi_aff_substitute( 4442 isl_multi_aff_copy(pma->p[i].maff), 4443 type, pos, subs->p[j].aff); 4444 4445 res = isl_pw_multi_aff_add_piece(res, common, res_ij); 4446 } 4447 } 4448 4449 isl_pw_multi_aff_free(pma); 4450 return res; 4451error: 4452 isl_pw_multi_aff_free(pma); 4453 isl_pw_multi_aff_free(res); 4454 return NULL; 4455} 4456 4457/* Compute the preimage of a range of dimensions in the affine expression "src" 4458 * under "ma" and put the result in "dst". The number of dimensions in "src" 4459 * that precede the range is given by "n_before". The number of dimensions 4460 * in the range is given by the number of output dimensions of "ma". 4461 * The number of dimensions that follow the range is given by "n_after". 4462 * If "has_denom" is set (to one), 4463 * then "src" and "dst" have an extra initial denominator. 4464 * "n_div_ma" is the number of existentials in "ma" 4465 * "n_div_bset" is the number of existentials in "src" 4466 * The resulting "dst" (which is assumed to have been allocated by 4467 * the caller) contains coefficients for both sets of existentials, 4468 * first those in "ma" and then those in "src". 4469 * f, c1, c2 and g are temporary objects that have been initialized 4470 * by the caller. 4471 * 4472 * Let src represent the expression 4473 * 4474 * (a(p) + f_u u + b v + f_w w + c(divs))/d 4475 * 4476 * and let ma represent the expressions 4477 * 4478 * v_i = (r_i(p) + s_i(y) + t_i(divs'))/m_i 4479 * 4480 * We start out with the following expression for dst: 4481 * 4482 * (a(p) + f_u u + 0 y + f_w w + 0 divs' + c(divs) + f \sum_i b_i v_i)/d 4483 * 4484 * with the multiplication factor f initially equal to 1 4485 * and f \sum_i b_i v_i kept separately. 4486 * For each x_i that we substitute, we multiply the numerator 4487 * (and denominator) of dst by c_1 = m_i and add the numerator 4488 * of the x_i expression multiplied by c_2 = f b_i, 4489 * after removing the common factors of c_1 and c_2. 4490 * The multiplication factor f also needs to be multiplied by c_1 4491 * for the next x_j, j > i. 4492 */ 4493void isl_seq_preimage(isl_int *dst, isl_int *src, 4494 __isl_keep isl_multi_aff *ma, int n_before, int n_after, 4495 int n_div_ma, int n_div_bmap, 4496 isl_int f, isl_int c1, isl_int c2, isl_int g, int has_denom) 4497{ 4498 int i; 4499 int n_param, n_in, n_out; 4500 int o_dst, o_src; 4501 4502 n_param = isl_multi_aff_dim(ma, isl_dim_param); 4503 n_in = isl_multi_aff_dim(ma, isl_dim_in); 4504 n_out = isl_multi_aff_dim(ma, isl_dim_out); 4505 4506 isl_seq_cpy(dst, src, has_denom + 1 + n_param + n_before); 4507 o_dst = o_src = has_denom + 1 + n_param + n_before; 4508 isl_seq_clr(dst + o_dst, n_in); 4509 o_dst += n_in; 4510 o_src += n_out; 4511 isl_seq_cpy(dst + o_dst, src + o_src, n_after); 4512 o_dst += n_after; 4513 o_src += n_after; 4514 isl_seq_clr(dst + o_dst, n_div_ma); 4515 o_dst += n_div_ma; 4516 isl_seq_cpy(dst + o_dst, src + o_src, n_div_bmap); 4517 4518 isl_int_set_si(f, 1); 4519 4520 for (i = 0; i < n_out; ++i) { 4521 int offset = has_denom + 1 + n_param + n_before + i; 4522 4523 if (isl_int_is_zero(src[offset])) 4524 continue; 4525 isl_int_set(c1, ma->p[i]->v->el[0]); 4526 isl_int_mul(c2, f, src[offset]); 4527 isl_int_gcd(g, c1, c2); 4528 isl_int_divexact(c1, c1, g); 4529 isl_int_divexact(c2, c2, g); 4530 4531 isl_int_mul(f, f, c1); 4532 o_dst = has_denom; 4533 o_src = 1; 4534 isl_seq_combine(dst + o_dst, c1, dst + o_dst, 4535 c2, ma->p[i]->v->el + o_src, 1 + n_param); 4536 o_dst += 1 + n_param; 4537 o_src += 1 + n_param; 4538 isl_seq_scale(dst + o_dst, dst + o_dst, c1, n_before); 4539 o_dst += n_before; 4540 isl_seq_combine(dst + o_dst, c1, dst + o_dst, 4541 c2, ma->p[i]->v->el + o_src, n_in); 4542 o_dst += n_in; 4543 o_src += n_in; 4544 isl_seq_scale(dst + o_dst, dst + o_dst, c1, n_after); 4545 o_dst += n_after; 4546 isl_seq_combine(dst + o_dst, c1, dst + o_dst, 4547 c2, ma->p[i]->v->el + o_src, n_div_ma); 4548 o_dst += n_div_ma; 4549 o_src += n_div_ma; 4550 isl_seq_scale(dst + o_dst, dst + o_dst, c1, n_div_bmap); 4551 if (has_denom) 4552 isl_int_mul(dst[0], dst[0], c1); 4553 } 4554} 4555 4556/* Compute the pullback of "aff" by the function represented by "ma". 4557 * In other words, plug in "ma" in "aff". The result is an affine expression 4558 * defined over the domain space of "ma". 4559 * 4560 * If "aff" is represented by 4561 * 4562 * (a(p) + b x + c(divs))/d 4563 * 4564 * and ma is represented by 4565 * 4566 * x = D(p) + F(y) + G(divs') 4567 * 4568 * then the result is 4569 * 4570 * (a(p) + b D(p) + b F(y) + b G(divs') + c(divs))/d 4571 * 4572 * The divs in the local space of the input are similarly adjusted 4573 * through a call to isl_local_space_preimage_multi_aff. 4574 */ 4575__isl_give isl_aff *isl_aff_pullback_multi_aff(__isl_take isl_aff *aff, 4576 __isl_take isl_multi_aff *ma) 4577{ 4578 isl_aff *res = NULL; 4579 isl_local_space *ls; 4580 int n_div_aff, n_div_ma; 4581 isl_int f, c1, c2, g; 4582 4583 ma = isl_multi_aff_align_divs(ma); 4584 if (!aff || !ma) 4585 goto error; 4586 4587 n_div_aff = isl_aff_dim(aff, isl_dim_div); 4588 n_div_ma = ma->n ? isl_aff_dim(ma->p[0], isl_dim_div) : 0; 4589 4590 ls = isl_aff_get_domain_local_space(aff); 4591 ls = isl_local_space_preimage_multi_aff(ls, isl_multi_aff_copy(ma)); 4592 res = isl_aff_alloc(ls); 4593 if (!res) 4594 goto error; 4595 4596 isl_int_init(f); 4597 isl_int_init(c1); 4598 isl_int_init(c2); 4599 isl_int_init(g); 4600 4601 isl_seq_preimage(res->v->el, aff->v->el, ma, 0, 0, n_div_ma, n_div_aff, 4602 f, c1, c2, g, 1); 4603 4604 isl_int_clear(f); 4605 isl_int_clear(c1); 4606 isl_int_clear(c2); 4607 isl_int_clear(g); 4608 4609 isl_aff_free(aff); 4610 isl_multi_aff_free(ma); 4611 res = isl_aff_normalize(res); 4612 return res; 4613error: 4614 isl_aff_free(aff); 4615 isl_multi_aff_free(ma); 4616 isl_aff_free(res); 4617 return NULL; 4618} 4619 4620/* Compute the pullback of "ma1" by the function represented by "ma2". 4621 * In other words, plug in "ma2" in "ma1". 4622 */ 4623__isl_give isl_multi_aff *isl_multi_aff_pullback_multi_aff( 4624 __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2) 4625{ 4626 int i; 4627 isl_space *space = NULL; 4628 4629 ma2 = isl_multi_aff_align_divs(ma2); 4630 ma1 = isl_multi_aff_cow(ma1); 4631 if (!ma1 || !ma2) 4632 goto error; 4633 4634 space = isl_space_join(isl_multi_aff_get_space(ma2), 4635 isl_multi_aff_get_space(ma1)); 4636 4637 for (i = 0; i < ma1->n; ++i) { 4638 ma1->p[i] = isl_aff_pullback_multi_aff(ma1->p[i], 4639 isl_multi_aff_copy(ma2)); 4640 if (!ma1->p[i]) 4641 goto error; 4642 } 4643 4644 ma1 = isl_multi_aff_reset_space(ma1, space); 4645 isl_multi_aff_free(ma2); 4646 return ma1; 4647error: 4648 isl_space_free(space); 4649 isl_multi_aff_free(ma2); 4650 isl_multi_aff_free(ma1); 4651 return NULL; 4652} 4653 4654/* Extend the local space of "dst" to include the divs 4655 * in the local space of "src". 4656 */ 4657__isl_give isl_aff *isl_aff_align_divs(__isl_take isl_aff *dst, 4658 __isl_keep isl_aff *src) 4659{ 4660 isl_ctx *ctx; 4661 int *exp1 = NULL; 4662 int *exp2 = NULL; 4663 isl_mat *div; 4664 4665 if (!src || !dst) 4666 return isl_aff_free(dst); 4667 4668 ctx = isl_aff_get_ctx(src); 4669 if (!isl_space_is_equal(src->ls->dim, dst->ls->dim)) 4670 isl_die(ctx, isl_error_invalid, 4671 "spaces don't match", goto error); 4672 4673 if (src->ls->div->n_row == 0) 4674 return dst; 4675 4676 exp1 = isl_alloc_array(ctx, int, src->ls->div->n_row); 4677 exp2 = isl_alloc_array(ctx, int, dst->ls->div->n_row); 4678 if (!exp1 || (dst->ls->div->n_row && !exp2)) 4679 goto error; 4680 4681 div = isl_merge_divs(src->ls->div, dst->ls->div, exp1, exp2); 4682 dst = isl_aff_expand_divs(dst, div, exp2); 4683 free(exp1); 4684 free(exp2); 4685 4686 return dst; 4687error: 4688 free(exp1); 4689 free(exp2); 4690 return isl_aff_free(dst); 4691} 4692 4693/* Adjust the local spaces of the affine expressions in "maff" 4694 * such that they all have the save divs. 4695 */ 4696__isl_give isl_multi_aff *isl_multi_aff_align_divs( 4697 __isl_take isl_multi_aff *maff) 4698{ 4699 int i; 4700 4701 if (!maff) 4702 return NULL; 4703 if (maff->n == 0) 4704 return maff; 4705 maff = isl_multi_aff_cow(maff); 4706 if (!maff) 4707 return NULL; 4708 4709 for (i = 1; i < maff->n; ++i) 4710 maff->p[0] = isl_aff_align_divs(maff->p[0], maff->p[i]); 4711 for (i = 1; i < maff->n; ++i) { 4712 maff->p[i] = isl_aff_align_divs(maff->p[i], maff->p[0]); 4713 if (!maff->p[i]) 4714 return isl_multi_aff_free(maff); 4715 } 4716 4717 return maff; 4718} 4719 4720__isl_give isl_aff *isl_aff_lift(__isl_take isl_aff *aff) 4721{ 4722 aff = isl_aff_cow(aff); 4723 if (!aff) 4724 return NULL; 4725 4726 aff->ls = isl_local_space_lift(aff->ls); 4727 if (!aff->ls) 4728 return isl_aff_free(aff); 4729 4730 return aff; 4731} 4732 4733/* Lift "maff" to a space with extra dimensions such that the result 4734 * has no more existentially quantified variables. 4735 * If "ls" is not NULL, then *ls is assigned the local space that lies 4736 * at the basis of the lifting applied to "maff". 4737 */ 4738__isl_give isl_multi_aff *isl_multi_aff_lift(__isl_take isl_multi_aff *maff, 4739 __isl_give isl_local_space **ls) 4740{ 4741 int i; 4742 isl_space *space; 4743 unsigned n_div; 4744 4745 if (ls) 4746 *ls = NULL; 4747 4748 if (!maff) 4749 return NULL; 4750 4751 if (maff->n == 0) { 4752 if (ls) { 4753 isl_space *space = isl_multi_aff_get_domain_space(maff); 4754 *ls = isl_local_space_from_space(space); 4755 if (!*ls) 4756 return isl_multi_aff_free(maff); 4757 } 4758 return maff; 4759 } 4760 4761 maff = isl_multi_aff_cow(maff); 4762 maff = isl_multi_aff_align_divs(maff); 4763 if (!maff) 4764 return NULL; 4765 4766 n_div = isl_aff_dim(maff->p[0], isl_dim_div); 4767 space = isl_multi_aff_get_space(maff); 4768 space = isl_space_lift(isl_space_domain(space), n_div); 4769 space = isl_space_extend_domain_with_range(space, 4770 isl_multi_aff_get_space(maff)); 4771 if (!space) 4772 return isl_multi_aff_free(maff); 4773 isl_space_free(maff->space); 4774 maff->space = space; 4775 4776 if (ls) { 4777 *ls = isl_aff_get_domain_local_space(maff->p[0]); 4778 if (!*ls) 4779 return isl_multi_aff_free(maff); 4780 } 4781 4782 for (i = 0; i < maff->n; ++i) { 4783 maff->p[i] = isl_aff_lift(maff->p[i]); 4784 if (!maff->p[i]) 4785 goto error; 4786 } 4787 4788 return maff; 4789error: 4790 if (ls) 4791 isl_local_space_free(*ls); 4792 return isl_multi_aff_free(maff); 4793} 4794 4795 4796/* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma". 4797 */ 4798__isl_give isl_pw_aff *isl_pw_multi_aff_get_pw_aff( 4799 __isl_keep isl_pw_multi_aff *pma, int pos) 4800{ 4801 int i; 4802 int n_out; 4803 isl_space *space; 4804 isl_pw_aff *pa; 4805 4806 if (!pma) 4807 return NULL; 4808 4809 n_out = isl_pw_multi_aff_dim(pma, isl_dim_out); 4810 if (pos < 0 || pos >= n_out) 4811 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid, 4812 "index out of bounds", return NULL); 4813 4814 space = isl_pw_multi_aff_get_space(pma); 4815 space = isl_space_drop_dims(space, isl_dim_out, 4816 pos + 1, n_out - pos - 1); 4817 space = isl_space_drop_dims(space, isl_dim_out, 0, pos); 4818 4819 pa = isl_pw_aff_alloc_size(space, pma->n); 4820 for (i = 0; i < pma->n; ++i) { 4821 isl_aff *aff; 4822 aff = isl_multi_aff_get_aff(pma->p[i].maff, pos); 4823 pa = isl_pw_aff_add_piece(pa, isl_set_copy(pma->p[i].set), aff); 4824 } 4825 4826 return pa; 4827} 4828 4829/* Return an isl_pw_multi_aff with the given "set" as domain and 4830 * an unnamed zero-dimensional range. 4831 */ 4832__isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_domain( 4833 __isl_take isl_set *set) 4834{ 4835 isl_multi_aff *ma; 4836 isl_space *space; 4837 4838 space = isl_set_get_space(set); 4839 space = isl_space_from_domain(space); 4840 ma = isl_multi_aff_zero(space); 4841 return isl_pw_multi_aff_alloc(set, ma); 4842} 4843 4844/* Add an isl_pw_multi_aff with the given "set" as domain and 4845 * an unnamed zero-dimensional range to *user. 4846 */ 4847static int add_pw_multi_aff_from_domain(__isl_take isl_set *set, void *user) 4848{ 4849 isl_union_pw_multi_aff **upma = user; 4850 isl_pw_multi_aff *pma; 4851 4852 pma = isl_pw_multi_aff_from_domain(set); 4853 *upma = isl_union_pw_multi_aff_add_pw_multi_aff(*upma, pma); 4854 4855 return 0; 4856} 4857 4858/* Return an isl_union_pw_multi_aff with the given "uset" as domain and 4859 * an unnamed zero-dimensional range. 4860 */ 4861__isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_from_domain( 4862 __isl_take isl_union_set *uset) 4863{ 4864 isl_space *space; 4865 isl_union_pw_multi_aff *upma; 4866 4867 if (!uset) 4868 return NULL; 4869 4870 space = isl_union_set_get_space(uset); 4871 upma = isl_union_pw_multi_aff_empty(space); 4872 4873 if (isl_union_set_foreach_set(uset, 4874 &add_pw_multi_aff_from_domain, &upma) < 0) 4875 goto error; 4876 4877 isl_union_set_free(uset); 4878 return upma; 4879error: 4880 isl_union_set_free(uset); 4881 isl_union_pw_multi_aff_free(upma); 4882 return NULL; 4883} 4884 4885/* Convert "pma" to an isl_map and add it to *umap. 4886 */ 4887static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma, void *user) 4888{ 4889 isl_union_map **umap = user; 4890 isl_map *map; 4891 4892 map = isl_map_from_pw_multi_aff(pma); 4893 *umap = isl_union_map_add_map(*umap, map); 4894 4895 return 0; 4896} 4897 4898/* Construct a union map mapping the domain of the union 4899 * piecewise multi-affine expression to its range, with each dimension 4900 * in the range equated to the corresponding affine expression on its cell. 4901 */ 4902__isl_give isl_union_map *isl_union_map_from_union_pw_multi_aff( 4903 __isl_take isl_union_pw_multi_aff *upma) 4904{ 4905 isl_space *space; 4906 isl_union_map *umap; 4907 4908 if (!upma) 4909 return NULL; 4910 4911 space = isl_union_pw_multi_aff_get_space(upma); 4912 umap = isl_union_map_empty(space); 4913 4914 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma, 4915 &map_from_pw_multi_aff, &umap) < 0) 4916 goto error; 4917 4918 isl_union_pw_multi_aff_free(upma); 4919 return umap; 4920error: 4921 isl_union_pw_multi_aff_free(upma); 4922 isl_union_map_free(umap); 4923 return NULL; 4924} 4925 4926/* Local data for bin_entry and the callback "fn". 4927 */ 4928struct isl_union_pw_multi_aff_bin_data { 4929 isl_union_pw_multi_aff *upma2; 4930 isl_union_pw_multi_aff *res; 4931 isl_pw_multi_aff *pma; 4932 int (*fn)(void **entry, void *user); 4933}; 4934 4935/* Given an isl_pw_multi_aff from upma1, store it in data->pma 4936 * and call data->fn for each isl_pw_multi_aff in data->upma2. 4937 */ 4938static int bin_entry(void **entry, void *user) 4939{ 4940 struct isl_union_pw_multi_aff_bin_data *data = user; 4941 isl_pw_multi_aff *pma = *entry; 4942 4943 data->pma = pma; 4944 if (isl_hash_table_foreach(data->upma2->dim->ctx, &data->upma2->table, 4945 data->fn, data) < 0) 4946 return -1; 4947 4948 return 0; 4949} 4950 4951/* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2". 4952 * The isl_pw_multi_aff from upma1 is stored in data->pma (where data is 4953 * passed as user field) and the isl_pw_multi_aff from upma2 is available 4954 * as *entry. The callback should adjust data->res if desired. 4955 */ 4956static __isl_give isl_union_pw_multi_aff *bin_op( 4957 __isl_take isl_union_pw_multi_aff *upma1, 4958 __isl_take isl_union_pw_multi_aff *upma2, 4959 int (*fn)(void **entry, void *user)) 4960{ 4961 isl_space *space; 4962 struct isl_union_pw_multi_aff_bin_data data = { NULL, NULL, NULL, fn }; 4963 4964 space = isl_union_pw_multi_aff_get_space(upma2); 4965 upma1 = isl_union_pw_multi_aff_align_params(upma1, space); 4966 space = isl_union_pw_multi_aff_get_space(upma1); 4967 upma2 = isl_union_pw_multi_aff_align_params(upma2, space); 4968 4969 if (!upma1 || !upma2) 4970 goto error; 4971 4972 data.upma2 = upma2; 4973 data.res = isl_union_pw_multi_aff_alloc(isl_space_copy(upma1->dim), 4974 upma1->table.n); 4975 if (isl_hash_table_foreach(upma1->dim->ctx, &upma1->table, 4976 &bin_entry, &data) < 0) 4977 goto error; 4978 4979 isl_union_pw_multi_aff_free(upma1); 4980 isl_union_pw_multi_aff_free(upma2); 4981 return data.res; 4982error: 4983 isl_union_pw_multi_aff_free(upma1); 4984 isl_union_pw_multi_aff_free(upma2); 4985 isl_union_pw_multi_aff_free(data.res); 4986 return NULL; 4987} 4988 4989/* Given two aligned isl_pw_multi_affs A -> B and C -> D, 4990 * construct an isl_pw_multi_aff (A * C) -> [B -> D]. 4991 */ 4992static __isl_give isl_pw_multi_aff *pw_multi_aff_range_product( 4993 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2) 4994{ 4995 isl_space *space; 4996 4997 space = isl_space_range_product(isl_pw_multi_aff_get_space(pma1), 4998 isl_pw_multi_aff_get_space(pma2)); 4999 return isl_pw_multi_aff_on_shared_domain_in(pma1, pma2, space, 5000 &isl_multi_aff_range_product); 5001} 5002 5003/* Given two isl_pw_multi_affs A -> B and C -> D, 5004 * construct an isl_pw_multi_aff (A * C) -> [B -> D]. 5005 */ 5006__isl_give isl_pw_multi_aff *isl_pw_multi_aff_range_product( 5007 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2) 5008{ 5009 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2, 5010 &pw_multi_aff_range_product); 5011} 5012 5013/* Given two aligned isl_pw_multi_affs A -> B and C -> D, 5014 * construct an isl_pw_multi_aff (A * C) -> (B, D). 5015 */ 5016static __isl_give isl_pw_multi_aff *pw_multi_aff_flat_range_product( 5017 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2) 5018{ 5019 isl_space *space; 5020 5021 space = isl_space_range_product(isl_pw_multi_aff_get_space(pma1), 5022 isl_pw_multi_aff_get_space(pma2)); 5023 space = isl_space_flatten_range(space); 5024 return isl_pw_multi_aff_on_shared_domain_in(pma1, pma2, space, 5025 &isl_multi_aff_flat_range_product); 5026} 5027 5028/* Given two isl_pw_multi_affs A -> B and C -> D, 5029 * construct an isl_pw_multi_aff (A * C) -> (B, D). 5030 */ 5031__isl_give isl_pw_multi_aff *isl_pw_multi_aff_flat_range_product( 5032 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2) 5033{ 5034 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2, 5035 &pw_multi_aff_flat_range_product); 5036} 5037 5038/* If data->pma and *entry have the same domain space, then compute 5039 * their flat range product and the result to data->res. 5040 */ 5041static int flat_range_product_entry(void **entry, void *user) 5042{ 5043 struct isl_union_pw_multi_aff_bin_data *data = user; 5044 isl_pw_multi_aff *pma2 = *entry; 5045 5046 if (!isl_space_tuple_match(data->pma->dim, isl_dim_in, 5047 pma2->dim, isl_dim_in)) 5048 return 0; 5049 5050 pma2 = isl_pw_multi_aff_flat_range_product( 5051 isl_pw_multi_aff_copy(data->pma), 5052 isl_pw_multi_aff_copy(pma2)); 5053 5054 data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma2); 5055 5056 return 0; 5057} 5058 5059/* Given two isl_union_pw_multi_affs A -> B and C -> D, 5060 * construct an isl_union_pw_multi_aff (A * C) -> (B, D). 5061 */ 5062__isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_flat_range_product( 5063 __isl_take isl_union_pw_multi_aff *upma1, 5064 __isl_take isl_union_pw_multi_aff *upma2) 5065{ 5066 return bin_op(upma1, upma2, &flat_range_product_entry); 5067} 5068 5069/* Replace the affine expressions at position "pos" in "pma" by "pa". 5070 * The parameters are assumed to have been aligned. 5071 * 5072 * The implementation essentially performs an isl_pw_*_on_shared_domain, 5073 * except that it works on two different isl_pw_* types. 5074 */ 5075static __isl_give isl_pw_multi_aff *pw_multi_aff_set_pw_aff( 5076 __isl_take isl_pw_multi_aff *pma, unsigned pos, 5077 __isl_take isl_pw_aff *pa) 5078{ 5079 int i, j, n; 5080 isl_pw_multi_aff *res = NULL; 5081 5082 if (!pma || !pa) 5083 goto error; 5084 5085 if (!isl_space_tuple_match(pma->dim, isl_dim_in, pa->dim, isl_dim_in)) 5086 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid, 5087 "domains don't match", goto error); 5088 if (pos >= isl_pw_multi_aff_dim(pma, isl_dim_out)) 5089 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid, 5090 "index out of bounds", goto error); 5091 5092 n = pma->n * pa->n; 5093 res = isl_pw_multi_aff_alloc_size(isl_pw_multi_aff_get_space(pma), n); 5094 5095 for (i = 0; i < pma->n; ++i) { 5096 for (j = 0; j < pa->n; ++j) { 5097 isl_set *common; 5098 isl_multi_aff *res_ij; 5099 int empty; 5100 5101 common = isl_set_intersect(isl_set_copy(pma->p[i].set), 5102 isl_set_copy(pa->p[j].set)); 5103 empty = isl_set_plain_is_empty(common); 5104 if (empty < 0 || empty) { 5105 isl_set_free(common); 5106 if (empty < 0) 5107 goto error; 5108 continue; 5109 } 5110 5111 res_ij = isl_multi_aff_set_aff( 5112 isl_multi_aff_copy(pma->p[i].maff), pos, 5113 isl_aff_copy(pa->p[j].aff)); 5114 res_ij = isl_multi_aff_gist(res_ij, 5115 isl_set_copy(common)); 5116 5117 res = isl_pw_multi_aff_add_piece(res, common, res_ij); 5118 } 5119 } 5120 5121 isl_pw_multi_aff_free(pma); 5122 isl_pw_aff_free(pa); 5123 return res; 5124error: 5125 isl_pw_multi_aff_free(pma); 5126 isl_pw_aff_free(pa); 5127 return isl_pw_multi_aff_free(res); 5128} 5129 5130/* Replace the affine expressions at position "pos" in "pma" by "pa". 5131 */ 5132__isl_give isl_pw_multi_aff *isl_pw_multi_aff_set_pw_aff( 5133 __isl_take isl_pw_multi_aff *pma, unsigned pos, 5134 __isl_take isl_pw_aff *pa) 5135{ 5136 if (!pma || !pa) 5137 goto error; 5138 if (isl_space_match(pma->dim, isl_dim_param, pa->dim, isl_dim_param)) 5139 return pw_multi_aff_set_pw_aff(pma, pos, pa); 5140 if (!isl_space_has_named_params(pma->dim) || 5141 !isl_space_has_named_params(pa->dim)) 5142 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid, 5143 "unaligned unnamed parameters", goto error); 5144 pma = isl_pw_multi_aff_align_params(pma, isl_pw_aff_get_space(pa)); 5145 pa = isl_pw_aff_align_params(pa, isl_pw_multi_aff_get_space(pma)); 5146 return pw_multi_aff_set_pw_aff(pma, pos, pa); 5147error: 5148 isl_pw_multi_aff_free(pma); 5149 isl_pw_aff_free(pa); 5150 return NULL; 5151} 5152 5153/* Check that the domain space of "pa" matches "space". 5154 * 5155 * Return 0 on success and -1 on error. 5156 */ 5157int isl_pw_aff_check_match_domain_space(__isl_keep isl_pw_aff *pa, 5158 __isl_keep isl_space *space) 5159{ 5160 isl_space *pa_space; 5161 int match; 5162 5163 if (!pa || !space) 5164 return -1; 5165 5166 pa_space = isl_pw_aff_get_space(pa); 5167 5168 match = isl_space_match(space, isl_dim_param, pa_space, isl_dim_param); 5169 if (match < 0) 5170 goto error; 5171 if (!match) 5172 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid, 5173 "parameters don't match", goto error); 5174 match = isl_space_tuple_match(space, isl_dim_in, pa_space, isl_dim_in); 5175 if (match < 0) 5176 goto error; 5177 if (!match) 5178 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid, 5179 "domains don't match", goto error); 5180 isl_space_free(pa_space); 5181 return 0; 5182error: 5183 isl_space_free(pa_space); 5184 return -1; 5185} 5186 5187#undef BASE 5188#define BASE pw_aff 5189 5190#include <isl_multi_templ.c> 5191 5192/* Scale the elements of "pma" by the corresponding elements of "mv". 5193 */ 5194__isl_give isl_pw_multi_aff *isl_pw_multi_aff_scale_multi_val( 5195 __isl_take isl_pw_multi_aff *pma, __isl_take isl_multi_val *mv) 5196{ 5197 int i; 5198 5199 pma = isl_pw_multi_aff_cow(pma); 5200 if (!pma || !mv) 5201 goto error; 5202 if (!isl_space_tuple_match(pma->dim, isl_dim_out, 5203 mv->space, isl_dim_set)) 5204 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid, 5205 "spaces don't match", goto error); 5206 if (!isl_space_match(pma->dim, isl_dim_param, 5207 mv->space, isl_dim_param)) { 5208 pma = isl_pw_multi_aff_align_params(pma, 5209 isl_multi_val_get_space(mv)); 5210 mv = isl_multi_val_align_params(mv, 5211 isl_pw_multi_aff_get_space(pma)); 5212 if (!pma || !mv) 5213 goto error; 5214 } 5215 5216 for (i = 0; i < pma->n; ++i) { 5217 pma->p[i].maff = isl_multi_aff_scale_multi_val(pma->p[i].maff, 5218 isl_multi_val_copy(mv)); 5219 if (!pma->p[i].maff) 5220 goto error; 5221 } 5222 5223 isl_multi_val_free(mv); 5224 return pma; 5225error: 5226 isl_multi_val_free(mv); 5227 isl_pw_multi_aff_free(pma); 5228 return NULL; 5229} 5230 5231/* Internal data structure for isl_union_pw_multi_aff_scale_multi_val. 5232 * mv contains the mv argument. 5233 * res collects the results. 5234 */ 5235struct isl_union_pw_multi_aff_scale_multi_val_data { 5236 isl_multi_val *mv; 5237 isl_union_pw_multi_aff *res; 5238}; 5239 5240/* This function is called for each entry of an isl_union_pw_multi_aff. 5241 * If the space of the entry matches that of data->mv, 5242 * then apply isl_pw_multi_aff_scale_multi_val and add the result 5243 * to data->res. 5244 */ 5245static int union_pw_multi_aff_scale_multi_val_entry(void **entry, void *user) 5246{ 5247 struct isl_union_pw_multi_aff_scale_multi_val_data *data = user; 5248 isl_pw_multi_aff *pma = *entry; 5249 5250 if (!pma) 5251 return -1; 5252 if (!isl_space_tuple_match(pma->dim, isl_dim_out, 5253 data->mv->space, isl_dim_set)) 5254 return 0; 5255 5256 pma = isl_pw_multi_aff_copy(pma); 5257 pma = isl_pw_multi_aff_scale_multi_val(pma, 5258 isl_multi_val_copy(data->mv)); 5259 data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma); 5260 if (!data->res) 5261 return -1; 5262 5263 return 0; 5264} 5265 5266/* Scale the elements of "upma" by the corresponding elements of "mv", 5267 * for those entries that match the space of "mv". 5268 */ 5269__isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_scale_multi_val( 5270 __isl_take isl_union_pw_multi_aff *upma, __isl_take isl_multi_val *mv) 5271{ 5272 struct isl_union_pw_multi_aff_scale_multi_val_data data; 5273 5274 upma = isl_union_pw_multi_aff_align_params(upma, 5275 isl_multi_val_get_space(mv)); 5276 mv = isl_multi_val_align_params(mv, 5277 isl_union_pw_multi_aff_get_space(upma)); 5278 if (!upma || !mv) 5279 goto error; 5280 5281 data.mv = mv; 5282 data.res = isl_union_pw_multi_aff_alloc(isl_space_copy(upma->dim), 5283 upma->table.n); 5284 if (isl_hash_table_foreach(upma->dim->ctx, &upma->table, 5285 &union_pw_multi_aff_scale_multi_val_entry, &data) < 0) 5286 goto error; 5287 5288 isl_multi_val_free(mv); 5289 isl_union_pw_multi_aff_free(upma); 5290 return data.res; 5291error: 5292 isl_multi_val_free(mv); 5293 isl_union_pw_multi_aff_free(upma); 5294 return NULL; 5295} 5296