991 lines · c
1/*2 * Copyright 2011 Sven Verdoolaege3 * Copyright 2012-2014 Ecole Normale Superieure4 *5 * Use of this software is governed by the MIT license6 *7 * Written by Sven Verdoolaege,8 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France9 */10 11#include <isl/id.h>12#include <isl_space_private.h>13#include <isl/set.h>14#include <isl_reordering.h>15 16#include <isl_multi_macro.h>17 18#define MULTI_NAME(BASE) "isl_multi_" #BASE19 20isl_ctx *FN(MULTI(BASE),get_ctx)(__isl_keep MULTI(BASE) *multi)21{22 return multi ? isl_space_get_ctx(multi->space) : NULL;23}24 25/* Return the space of "multi".26 */27__isl_keep isl_space *FN(MULTI(BASE),peek_space)(__isl_keep MULTI(BASE) *multi)28{29 return multi ? multi->space : NULL;30}31 32__isl_give isl_space *FN(MULTI(BASE),get_space)(__isl_keep MULTI(BASE) *multi)33{34 return isl_space_copy(FN(MULTI(BASE),peek_space)(multi));35}36 37__isl_give isl_space *FN(MULTI(BASE),get_domain_space)(38 __isl_keep MULTI(BASE) *multi)39{40 return multi ? isl_space_domain(isl_space_copy(multi->space)) : NULL;41}42 43/* Allocate a multi expression living in "space".44 *45 * If the number of base expressions is zero, then make sure46 * there is enough room in the structure for the explicit domain,47 * in case the type supports such an explicit domain.48 */49__isl_give MULTI(BASE) *FN(MULTI(BASE),alloc)(__isl_take isl_space *space)50{51 isl_ctx *ctx;52 isl_size n;53 MULTI(BASE) *multi;54 55 n = isl_space_dim(space, isl_dim_out);56 if (n < 0)57 goto error;58 59 ctx = isl_space_get_ctx(space);60 if (n > 0)61 multi = isl_calloc(ctx, MULTI(BASE),62 sizeof(MULTI(BASE)) + (n - 1) * sizeof(struct EL *));63 else64 multi = isl_calloc(ctx, MULTI(BASE), sizeof(MULTI(BASE)));65 if (!multi)66 goto error;67 68 multi->space = space;69 multi->n = n;70 multi->ref = 1;71 if (FN(MULTI(BASE),has_explicit_domain)(multi))72 multi = FN(MULTI(BASE),init_explicit_domain)(multi);73 return multi;74error:75 isl_space_free(space);76 return NULL;77}78 79__isl_give MULTI(BASE) *FN(MULTI(BASE),dup)(__isl_keep MULTI(BASE) *multi)80{81 int i;82 MULTI(BASE) *dup;83 84 if (!multi)85 return NULL;86 87 dup = FN(MULTI(BASE),alloc)(isl_space_copy(multi->space));88 if (!dup)89 return NULL;90 91 for (i = 0; i < multi->n; ++i)92 dup = FN(FN(MULTI(BASE),set),BASE)(dup, i,93 FN(EL,copy)(multi->u.p[i]));94 if (FN(MULTI(BASE),has_explicit_domain)(multi))95 dup = FN(MULTI(BASE),copy_explicit_domain)(dup, multi);96 97 return dup;98}99 100__isl_give MULTI(BASE) *FN(MULTI(BASE),cow)(__isl_take MULTI(BASE) *multi)101{102 if (!multi)103 return NULL;104 105 if (multi->ref == 1)106 return multi;107 108 multi->ref--;109 return FN(MULTI(BASE),dup)(multi);110}111 112__isl_give MULTI(BASE) *FN(MULTI(BASE),copy)(__isl_keep MULTI(BASE) *multi)113{114 if (!multi)115 return NULL;116 117 multi->ref++;118 return multi;119}120 121__isl_null MULTI(BASE) *FN(MULTI(BASE),free)(__isl_take MULTI(BASE) *multi)122{123 int i;124 125 if (!multi)126 return NULL;127 128 if (--multi->ref > 0)129 return NULL;130 131 isl_space_free(multi->space);132 for (i = 0; i < multi->n; ++i)133 FN(EL,free)(multi->u.p[i]);134 if (FN(MULTI(BASE),has_explicit_domain)(multi))135 FN(MULTI(BASE),free_explicit_domain)(multi);136 free(multi);137 138 return NULL;139}140 141/* Return the space of "multi".142 * The caller is not allowed to modify "multi" between this call143 * and the call to *_restore_space because the number144 * of references needs to stay the same.145 * The only exception is that isl_multi_*_free can be called instead.146 * No copy is taken of multi->space if "multi" has only one reference147 * such that it can be modified inplace if both have only a single reference.148 */149__isl_give isl_space *FN(MULTI(BASE),take_space)(__isl_keep MULTI(BASE) *multi)150{151 isl_space *space;152 153 if (!multi)154 return NULL;155 if (multi->ref != 1)156 return FN(MULTI(BASE),get_space)(multi);157 space = multi->space;158 multi->space = NULL;159 return space;160}161 162/* Set the space of "multi" to "space", where the space of "multi"163 * may be missing due to a preceding call to isl_multi_*_take_space.164 * However, in this case, "multi" only has a single reference and165 * then the call to isl_multi_*_cow has no effect.166 */167__isl_give MULTI(BASE) *FN(MULTI(BASE),restore_space)(168 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space)169{170 if (!multi || !space)171 goto error;172 173 if (multi->space == space) {174 isl_space_free(space);175 return multi;176 }177 178 multi = FN(MULTI(BASE),cow)(multi);179 if (!multi)180 goto error;181 isl_space_free(multi->space);182 multi->space = space;183 184 return multi;185error:186 FN(MULTI(BASE),free)(multi);187 isl_space_free(space);188 return NULL;189}190 191isl_size FN(MULTI(BASE),dim)(__isl_keep MULTI(BASE) *multi,192 enum isl_dim_type type)193{194 return isl_space_dim(FN(MULTI(BASE),peek_space)(multi), type);195}196 197/* Return the number of base expressions in "multi".198 */199isl_size FN(MULTI(BASE),size)(__isl_keep MULTI(BASE) *multi)200{201 return multi ? multi->n : isl_size_error;202}203 204#undef TYPE205#define TYPE MULTI(BASE)206static207#include "check_type_range_templ.c"208 209/* Return the base expression at position "pos" in "multi".210 */211static __isl_give EL *FN(MULTI(BASE),peek_at)(__isl_keep MULTI(BASE) *multi,212 int pos)213{214 if (FN(MULTI(BASE),check_range)(multi, isl_dim_out, pos, 1) < 0)215 return NULL;216 return multi->u.p[pos];217}218 219/* Return a copy of the base expression at position "pos" in "multi".220 */221__isl_give EL *FN(MULTI(BASE),get_at)(__isl_keep MULTI(BASE) *multi, int pos)222{223 return FN(EL,copy)(FN(MULTI(BASE),peek_at)(multi, pos));224}225 226/* This is an alternative name for the function above.227 */228__isl_give EL *FN(FN(MULTI(BASE),get),BASE)(__isl_keep MULTI(BASE) *multi,229 int pos)230{231 return FN(MULTI(BASE),get_at)(multi, pos);232}233 234/* Return the base expression at position "pos" in "multi".235 * This may be either a copy or the base expression itself236 * if there is only one reference to "multi".237 * This allows the base expression to be modified inplace238 * if both the multi expression and this base expression239 * have only a single reference.240 * The caller is not allowed to modify "multi" between this call and241 * the subsequent call to isl_multi_*_restore_at_*.242 * The only exception is that isl_multi_*_free can be called instead.243 */244static __isl_give EL *FN(MULTI(BASE),take_at)(__isl_keep MULTI(BASE) *multi,245 int pos)246{247 EL *el;248 249 if (!multi)250 return NULL;251 if (multi->ref != 1)252 return FN(MULTI(BASE),get_at)(multi, pos);253 if (FN(MULTI(BASE),check_range)(multi, isl_dim_out, pos, 1) < 0)254 return NULL;255 el = multi->u.p[pos];256 multi->u.p[pos] = NULL;257 return el;258}259 260/* Set the element at position "pos" of "multi" to "el",261 * where the position may be empty if "multi" has only a single reference.262 */263static __isl_give MULTI(BASE) *FN(MULTI(BASE),restore_at)(264 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)265{266 if (FN(MULTI(BASE),check_range)(multi, isl_dim_out, pos, 1) < 0 || !el)267 goto error;268 269 if (multi->u.p[pos] == el) {270 FN(EL,free)(el);271 return multi;272 }273 274 multi = FN(MULTI(BASE),cow)(multi);275 if (!multi)276 goto error;277 278 FN(EL,free)(multi->u.p[pos]);279 multi->u.p[pos] = el;280 281 return multi;282error:283 FN(MULTI(BASE),free)(multi);284 FN(EL,free)(el);285 return NULL;286}287 288/* Set the element at position "pos" of "multi" to "el",289 * where the position may be empty if "multi" has only a single reference.290 * However, the space of "multi" is available and is checked291 * for compatibility with "el".292 */293static __isl_give MULTI(BASE) *FN(MULTI(BASE),restore_check_space)(294 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)295{296 isl_space *space;297 298 space = FN(MULTI(BASE),peek_space)(multi);299 if (FN(EL,check_match_domain_space)(el, space) < 0)300 multi = FN(MULTI(BASE),free)(multi);301 return FN(MULTI(BASE),restore_at)(multi, pos, el);302}303 304/* Replace the base expression at position "pos" in "multi" with "el".305 */306__isl_give MULTI(BASE) *FN(MULTI(BASE),set_at)(307 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)308{309 isl_space *multi_space = NULL;310 isl_space *el_space = NULL;311 isl_bool match;312 313 multi_space = FN(MULTI(BASE),get_space)(multi);314 match = FN(EL,matching_params)(el, multi_space);315 if (match < 0)316 goto error;317 if (!match) {318 multi = FN(MULTI(BASE),align_params)(multi,319 FN(EL,get_space)(el));320 isl_space_free(multi_space);321 multi_space = FN(MULTI(BASE),get_space)(multi);322 el = FN(EL,align_params)(el, isl_space_copy(multi_space));323 }324 325 multi = FN(MULTI(BASE),restore_check_space)(multi, pos, el);326 327 isl_space_free(multi_space);328 isl_space_free(el_space);329 330 return multi;331error:332 FN(MULTI(BASE),free)(multi);333 FN(EL,free)(el);334 isl_space_free(multi_space);335 isl_space_free(el_space);336 return NULL;337}338 339/* This is an alternative name for the function above.340 */341__isl_give MULTI(BASE) *FN(FN(MULTI(BASE),set),BASE)(342 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)343{344 return FN(MULTI(BASE),set_at)(multi, pos, el);345}346 347/* Return the base expressions of "multi" as a list.348 */349__isl_give LIST(EL) *FN(MULTI(BASE),get_list)(350 __isl_keep MULTI(BASE) *multi)351{352 isl_size n;353 int i;354 LIST(EL) *list;355 356 n = FN(MULTI(BASE),size)(multi);357 if (n < 0)358 return NULL;359 list = FN(LIST(EL),alloc)(FN(MULTI(BASE),get_ctx(multi)), n);360 for (i = 0; i < n; ++i) {361 EL *el = FN(MULTI(BASE),get_at)(multi, i);362 list = FN(LIST(EL),add)(list, el);363 }364 365 return list;366}367 368/* Reset the space of "multi". This function is called from isl_pw_templ.c369 * and doesn't know if the space of an element object is represented370 * directly or through its domain. It therefore passes along both,371 * which we pass along to the element function since we don't know how372 * that is represented either.373 *374 * If "multi" has an explicit domain, then the caller is expected375 * to make sure that any modification that would change the dimensions376 * of the explicit domain has bee applied before this function is called.377 */378__isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space_and_domain)(379 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space,380 __isl_take isl_space *domain)381{382 isl_size n;383 int i;384 385 n = FN(MULTI(BASE),size)(multi);386 if (n < 0 || !space || !domain)387 goto error;388 389 for (i = 0; i < n; ++i) {390 EL *el;391 392 el = FN(MULTI(BASE),take_at)(multi, i);393 el = FN(EL,reset_domain_space)(el, isl_space_copy(domain));394 multi = FN(MULTI(BASE),restore_at)(multi, i, el);395 }396 if (FN(MULTI(BASE),has_explicit_domain)(multi))397 multi = FN(MULTI(BASE),reset_explicit_domain_space)(multi,398 isl_space_copy(domain));399 isl_space_free(domain);400 401 multi = FN(MULTI(BASE),restore_space)(multi, space);402 403 return multi;404error:405 isl_space_free(domain);406 isl_space_free(space);407 FN(MULTI(BASE),free)(multi);408 return NULL;409}410 411__isl_give MULTI(BASE) *FN(MULTI(BASE),reset_domain_space)(412 __isl_take MULTI(BASE) *multi, __isl_take isl_space *domain)413{414 isl_space *space, *multi_space;415 416 multi_space = FN(MULTI(BASE),get_space)(multi);417 space = isl_space_extend_domain_with_range(isl_space_copy(domain),418 multi_space);419 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);420}421 422__isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space)(423 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space)424{425 isl_space *domain;426 427 domain = isl_space_domain(isl_space_copy(space));428 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);429}430 431/* Reset the user pointer on all identifiers of parameters and tuples432 * of the space of "multi".433 */434__isl_give MULTI(BASE) *FN(MULTI(BASE),reset_user)(435 __isl_take MULTI(BASE) *multi)436{437 isl_space *space;438 439 space = FN(MULTI(BASE),get_space)(multi);440 space = isl_space_reset_user(space);441 442 return FN(MULTI(BASE),reset_space)(multi, space);443}444 445__isl_give MULTI(BASE) *FN(MULTI(BASE),realign_domain)(446 __isl_take MULTI(BASE) *multi, __isl_take isl_reordering *exp)447{448 int i;449 isl_size n;450 isl_space *space;451 452 n = FN(MULTI(BASE),size)(multi);453 if (n < 0 || !exp)454 goto error;455 456 for (i = 0; i < n; ++i) {457 EL *el;458 459 el = FN(MULTI(BASE),take_at)(multi, i);460 el = FN(EL,realign_domain)(el, isl_reordering_copy(exp));461 multi = FN(MULTI(BASE),restore_at)(multi, i, el);462 }463 464 space = isl_reordering_get_space(exp);465 multi = FN(MULTI(BASE),reset_domain_space)(multi, space);466 467 isl_reordering_free(exp);468 return multi;469error:470 isl_reordering_free(exp);471 FN(MULTI(BASE),free)(multi);472 return NULL;473}474 475/* Align the parameters of "multi" to those of "model".476 *477 * If "multi" has an explicit domain, then align the parameters478 * of the domain first.479 */480__isl_give MULTI(BASE) *FN(MULTI(BASE),align_params)(481 __isl_take MULTI(BASE) *multi, __isl_take isl_space *model)482{483 isl_ctx *ctx;484 isl_bool equal_params;485 isl_space *domain_space;486 isl_reordering *exp;487 488 if (!multi || !model)489 goto error;490 491 equal_params = isl_space_has_equal_params(multi->space, model);492 if (equal_params < 0)493 goto error;494 if (equal_params) {495 isl_space_free(model);496 return multi;497 }498 499 ctx = isl_space_get_ctx(model);500 if (!isl_space_has_named_params(model))501 isl_die(ctx, isl_error_invalid,502 "model has unnamed parameters", goto error);503 if (!isl_space_has_named_params(multi->space))504 isl_die(ctx, isl_error_invalid,505 "input has unnamed parameters", goto error);506 507 if (FN(MULTI(BASE),has_explicit_domain)(multi)) {508 multi = FN(MULTI(BASE),align_explicit_domain_params)(multi,509 isl_space_copy(model));510 if (!multi)511 goto error;512 }513 domain_space = FN(MULTI(BASE),get_domain_space)(multi);514 exp = isl_parameter_alignment_reordering(domain_space, model);515 isl_space_free(domain_space);516 multi = FN(MULTI(BASE),realign_domain)(multi, exp);517 518 isl_space_free(model);519 return multi;520error:521 isl_space_free(model);522 FN(MULTI(BASE),free)(multi);523 return NULL;524}525 526/* Create a multi expression in the given space with the elements of "list"527 * as base expressions.528 *529 * Since isl_multi_*_restore_* assumes that the element and530 * the multi expression have matching spaces, the alignment531 * (if any) needs to be performed beforehand.532 */533__isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))(534 __isl_take isl_space *space, __isl_take LIST(EL) *list)535{536 int i;537 isl_size n, dim;538 isl_ctx *ctx;539 MULTI(BASE) *multi;540 541 dim = isl_space_dim(space, isl_dim_out);542 n = FN(FN(LIST(EL),n),BASE)(list);543 if (dim < 0 || n < 0)544 goto error;545 546 ctx = isl_space_get_ctx(space);547 if (n != dim)548 isl_die(ctx, isl_error_invalid,549 "invalid number of elements in list", goto error);550 551 for (i = 0; i < n; ++i) {552 EL *el = FN(LIST(EL),peek)(list, i);553 space = isl_space_align_params(space, FN(EL,get_space)(el));554 }555 multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));556 for (i = 0; i < n; ++i) {557 EL *el = FN(FN(LIST(EL),get),BASE)(list, i);558 el = FN(EL,align_params)(el, isl_space_copy(space));559 multi = FN(MULTI(BASE),restore_check_space)(multi, i, el);560 }561 562 isl_space_free(space);563 FN(LIST(EL),free)(list);564 return multi;565error:566 isl_space_free(space);567 FN(LIST(EL),free)(list);568 return NULL;569}570 571/* This function performs the same operation as isl_multi_*_from_*_list,572 * but is considered as a function on an isl_space when exported.573 */574__isl_give MULTI(BASE) *FN(isl_space_multi,BASE)(__isl_take isl_space *space,575 __isl_take LIST(EL) *list)576{577 return FN(FN(MULTI(BASE),from),LIST(BASE))(space, list);578}579 580/* Drop the "n" output dimensions of "multi" starting at "first",581 * where the space is assumed to have been adjusted already.582 */583static __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_output_dims)(584 __isl_take MULTI(BASE) *multi, unsigned first, unsigned n)585{586 int i;587 588 multi = FN(MULTI(BASE),cow)(multi);589 if (!multi)590 return NULL;591 592 for (i = 0; i < n; ++i)593 FN(EL,free)(multi->u.p[first + i]);594 for (i = first; i + n < multi->n; ++i)595 multi->u.p[i] = multi->u.p[i + n];596 multi->n -= n;597 if (n > 0 && FN(MULTI(BASE),has_explicit_domain)(multi))598 multi = FN(MULTI(BASE),init_explicit_domain)(multi);599 600 return multi;601}602 603__isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)(604 __isl_take MULTI(BASE) *multi,605 enum isl_dim_type type, unsigned first, unsigned n)606{607 isl_space *space;608 isl_size size;609 int i;610 611 if (FN(MULTI(BASE),check_range)(multi, type, first, n) < 0)612 return FN(MULTI(BASE),free)(multi);613 614 space = FN(MULTI(BASE),take_space)(multi);615 space = isl_space_drop_dims(space, type, first, n);616 multi = FN(MULTI(BASE),restore_space)(multi, space);617 618 if (type == isl_dim_out)619 return FN(MULTI(BASE),drop_output_dims)(multi, first, n);620 621 if (FN(MULTI(BASE),has_explicit_domain)(multi))622 multi = FN(MULTI(BASE),drop_explicit_domain_dims)(multi,623 type, first, n);624 625 size = FN(MULTI(BASE),size)(multi);626 if (size < 0)627 return FN(MULTI(BASE),free)(multi);628 for (i = 0; i < size; ++i) {629 EL *el;630 631 el = FN(MULTI(BASE),take_at)(multi, i);632 el = FN(EL,drop_dims)(el, type, first, n);633 multi = FN(MULTI(BASE),restore_at)(multi, i, el);634 }635 636 return multi;637}638 639#undef TYPE640#define TYPE MULTI(BASE)641 642#include "isl_check_named_params_templ.c"643static644#include "isl_align_params_bin_templ.c"645 646/* Given two MULTI(BASE)s A -> B and C -> D,647 * construct a MULTI(BASE) (A * C) -> [B -> D].648 *649 * If "multi1" and/or "multi2" has an explicit domain, then650 * intersect the domain of the result with these explicit domains.651 */652__isl_give MULTI(BASE) *FN(MULTI(BASE),range_product)(653 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)654{655 int i;656 isl_size n1, n2;657 EL *el;658 isl_space *space;659 MULTI(BASE) *res;660 661 FN(MULTI(BASE),align_params_bin)(&multi1, &multi2);662 n1 = FN(MULTI(BASE),size)(multi1);663 n2 = FN(MULTI(BASE),size)(multi2);664 if (n1 < 0 || n2 < 0)665 goto error;666 667 space = isl_space_range_product(FN(MULTI(BASE),get_space)(multi1),668 FN(MULTI(BASE),get_space)(multi2));669 res = FN(MULTI(BASE),alloc)(space);670 671 for (i = 0; i < n1; ++i) {672 el = FN(FN(MULTI(BASE),get),BASE)(multi1, i);673 res = FN(FN(MULTI(BASE),set),BASE)(res, i, el);674 }675 676 for (i = 0; i < n2; ++i) {677 el = FN(FN(MULTI(BASE),get),BASE)(multi2, i);678 res = FN(FN(MULTI(BASE),set),BASE)(res, n1 + i, el);679 }680 681 if (FN(MULTI(BASE),has_explicit_domain)(multi1))682 res = FN(MULTI(BASE),intersect_explicit_domain)(res, multi1);683 if (FN(MULTI(BASE),has_explicit_domain)(multi2))684 res = FN(MULTI(BASE),intersect_explicit_domain)(res, multi2);685 686 FN(MULTI(BASE),free)(multi1);687 FN(MULTI(BASE),free)(multi2);688 return res;689error:690 FN(MULTI(BASE),free)(multi1);691 FN(MULTI(BASE),free)(multi2);692 return NULL;693}694 695/* Is the range of "multi" a wrapped relation?696 */697isl_bool FN(MULTI(BASE),range_is_wrapping)(__isl_keep MULTI(BASE) *multi)698{699 if (!multi)700 return isl_bool_error;701 return isl_space_range_is_wrapping(multi->space);702}703 704/* Given a function A -> [B -> C], extract the function A -> B.705 */706__isl_give MULTI(BASE) *FN(MULTI(BASE),range_factor_domain)(707 __isl_take MULTI(BASE) *multi)708{709 isl_space *space;710 isl_size total, keep;711 712 total = FN(MULTI(BASE),dim)(multi, isl_dim_out);713 if (total < 0)714 return FN(MULTI(BASE),free)(multi);715 if (!isl_space_range_is_wrapping(multi->space))716 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,717 "range is not a product",718 return FN(MULTI(BASE),free)(multi));719 720 space = FN(MULTI(BASE),get_space)(multi);721 space = isl_space_range_factor_domain(space);722 keep = isl_space_dim(space, isl_dim_out);723 if (keep < 0)724 multi = FN(MULTI(BASE),free)(multi);725 multi = FN(MULTI(BASE),drop_dims)(multi,726 isl_dim_out, keep, total - keep);727 multi = FN(MULTI(BASE),reset_space)(multi, space);728 729 return multi;730}731 732/* Given a function A -> [B -> C], extract the function A -> C.733 */734__isl_give MULTI(BASE) *FN(MULTI(BASE),range_factor_range)(735 __isl_take MULTI(BASE) *multi)736{737 isl_space *space;738 isl_size total, keep;739 740 total = FN(MULTI(BASE),dim)(multi, isl_dim_out);741 if (total < 0)742 return FN(MULTI(BASE),free)(multi);743 if (!isl_space_range_is_wrapping(multi->space))744 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,745 "range is not a product",746 return FN(MULTI(BASE),free)(multi));747 748 space = FN(MULTI(BASE),get_space)(multi);749 space = isl_space_range_factor_range(space);750 keep = isl_space_dim(space, isl_dim_out);751 if (keep < 0)752 multi = FN(MULTI(BASE),free)(multi);753 multi = FN(MULTI(BASE),drop_dims)(multi, isl_dim_out, 0, total - keep);754 multi = FN(MULTI(BASE),reset_space)(multi, space);755 756 return multi;757}758 759/* Given a function [B -> C], extract the function C.760 */761__isl_give MULTI(BASE) *FN(MULTI(BASE),factor_range)(762 __isl_take MULTI(BASE) *multi)763{764 isl_space *space;765 isl_size total, keep;766 767 total = FN(MULTI(BASE),dim)(multi, isl_dim_set);768 if (total < 0)769 return FN(MULTI(BASE),free)(multi);770 if (!isl_space_is_wrapping(multi->space))771 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,772 "not a product", return FN(MULTI(BASE),free)(multi));773 774 space = FN(MULTI(BASE),get_space)(multi);775 space = isl_space_factor_range(space);776 keep = isl_space_dim(space, isl_dim_set);777 if (keep < 0)778 multi = FN(MULTI(BASE),free)(multi);779 multi = FN(MULTI(BASE),drop_dims)(multi, isl_dim_set, 0, total - keep);780 multi = FN(MULTI(BASE),reset_space)(multi, space);781 782 return multi;783}784 785__isl_give MULTI(BASE) *FN(MULTI(BASE),flatten_range)(786 __isl_take MULTI(BASE) *multi)787{788 isl_space *space;789 790 space = FN(MULTI(BASE),take_space)(multi);791 space = isl_space_flatten_range(space);792 multi = FN(MULTI(BASE),restore_space)(multi, space);793 794 return multi;795}796 797/* Given two MULTI(BASE)s A -> B and C -> D,798 * construct a MULTI(BASE) (A * C) -> (B, D).799 */800__isl_give MULTI(BASE) *FN(MULTI(BASE),flat_range_product)(801 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)802{803 MULTI(BASE) *multi;804 805 multi = FN(MULTI(BASE),range_product)(multi1, multi2);806 multi = FN(MULTI(BASE),flatten_range)(multi);807 return multi;808}809 810/* Given two multi expressions, "multi1"811 *812 * [A] -> [B1 B2]813 *814 * where B2 starts at position "pos", and "multi2"815 *816 * [A] -> [D]817 *818 * return the multi expression819 *820 * [A] -> [B1 D B2]821 */822__isl_give MULTI(BASE) *FN(MULTI(BASE),range_splice)(823 __isl_take MULTI(BASE) *multi1, unsigned pos,824 __isl_take MULTI(BASE) *multi2)825{826 MULTI(BASE) *res;827 isl_size dim;828 829 dim = FN(MULTI(BASE),size)(multi1);830 if (dim < 0 || !multi2)831 goto error;832 833 if (FN(MULTI(BASE),check_range)(multi1, isl_dim_out, pos, 0) < 0)834 goto error;835 836 res = FN(MULTI(BASE),copy)(multi1);837 res = FN(MULTI(BASE),drop_dims)(res, isl_dim_out, pos, dim - pos);838 multi1 = FN(MULTI(BASE),drop_dims)(multi1, isl_dim_out, 0, pos);839 840 res = FN(MULTI(BASE),flat_range_product)(res, multi2);841 res = FN(MULTI(BASE),flat_range_product)(res, multi1);842 843 return res;844error:845 FN(MULTI(BASE),free)(multi1);846 FN(MULTI(BASE),free)(multi2);847 return NULL;848}849 850#undef TYPE851#define TYPE MULTI(BASE)852 853static854#include "isl_type_has_equal_space_bin_templ.c"855static856#include "isl_type_check_equal_space_templ.c"857 858/* This function is currently only used from isl_aff.c859 */860static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(861 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,862 __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))863 __attribute__ ((unused));864 865/* Pairwise perform "fn" to the elements of "multi1" and "multi2" and866 * return the result.867 *868 * If "multi2" has an explicit domain, then869 * intersect the domain of the result with this explicit domain.870 */871static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(872 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,873 __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))874{875 isl_size n;876 int i;877 878 FN(MULTI(BASE),align_params_bin)(&multi1, &multi2);879 n = FN(MULTI(BASE),size)(multi1);880 if (n < 0 || FN(MULTI(BASE),check_equal_space)(multi1, multi2) < 0)881 goto error;882 883 for (i = 0; i < n; ++i) {884 EL *el1, *el2;885 886 el2 = FN(MULTI(BASE),get_at)(multi2, i);887 el1 = FN(MULTI(BASE),take_at)(multi1, i);888 el1 = fn(el1, el2);889 multi1 = FN(MULTI(BASE),restore_at)(multi1, i, el1);890 }891 892 if (FN(MULTI(BASE),has_explicit_domain)(multi2))893 multi1 = FN(MULTI(BASE),intersect_explicit_domain)(multi1,894 multi2);895 896 FN(MULTI(BASE),free)(multi2);897 return multi1;898error:899 FN(MULTI(BASE),free)(multi1);900 FN(MULTI(BASE),free)(multi2);901 return NULL;902}903 904/* Only used on some multi-expressions.905 */906static isl_bool FN(MULTI(BASE),any)(__isl_keep MULTI(BASE) *multi,907 isl_bool (*test)(__isl_keep EL *)) __attribute__ ((unused));908 909/* Does "test" succeed on any base expression of "multi"?910 */911static isl_bool FN(MULTI(BASE),any)(__isl_keep MULTI(BASE) *multi,912 isl_bool (*test)(__isl_keep EL *))913{914 isl_size n;915 int i;916 917 n = FN(MULTI(BASE),size)(multi);918 if (n < 0)919 return isl_bool_error;920 921 for (i = 0; i < n; ++i) {922 isl_bool any = test(multi->u.p[i]);923 if (any < 0 || any)924 return any;925 }926 927 return isl_bool_false;928}929 930/* Only used on some multi-expressions.931 */932static isl_bool FN(MULTI(BASE),every)(__isl_keep MULTI(BASE) *multi,933 isl_bool (*test)(__isl_keep EL *)) __attribute__ ((unused));934 935/* Does "test" succeed on every base expression of "multi"?936 */937static isl_bool FN(MULTI(BASE),every)(__isl_keep MULTI(BASE) *multi,938 isl_bool (*test)(__isl_keep EL *))939{940 isl_size n;941 int i;942 943 n = FN(MULTI(BASE),size)(multi);944 if (n < 0)945 return isl_bool_error;946 947 for (i = 0; i < n; ++i) {948 isl_bool every = test(multi->u.p[i]);949 if (every < 0 || !every)950 return every;951 }952 953 return isl_bool_true;954}955 956#undef TYPE957#define TYPE MULTI(BASE)958#include "isl_from_range_templ.c"959 960/* Are "multi1" and "multi2" obviously equal?961 */962isl_bool FN(MULTI(BASE),plain_is_equal)(__isl_keep MULTI(BASE) *multi1,963 __isl_keep MULTI(BASE) *multi2)964{965 int i;966 isl_bool equal;967 968 if (!multi1 || !multi2)969 return isl_bool_error;970 if (multi1->n != multi2->n)971 return isl_bool_false;972 equal = isl_space_is_equal(multi1->space, multi2->space);973 if (equal < 0 || !equal)974 return equal;975 976 for (i = 0; i < multi1->n; ++i) {977 equal = FN(EL,plain_is_equal)(multi1->u.p[i], multi2->u.p[i]);978 if (equal < 0 || !equal)979 return equal;980 }981 982 if (FN(MULTI(BASE),has_explicit_domain)(multi1) ||983 FN(MULTI(BASE),has_explicit_domain)(multi2)) {984 equal = FN(MULTI(BASE),equal_explicit_domain)(multi1, multi2);985 if (equal < 0 || !equal)986 return equal;987 }988 989 return isl_bool_true;990}991