isl_multi_templ.c

   1 /*
   2  * Copyright 2011      Sven Verdoolaege
   3  * Copyright 2012      Ecole Normale Superieure
   4  *
   5  * Use of this software is governed by the MIT license
   6  *
   7  * Written by Sven Verdoolaege,
   8  * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
   9  */
  10
  11 #include <isl_space_private.h>
  12 #include <isl/set.h>
  13 #include <isl_reordering.h>
  14
  15 #define xCAT(A,B) A ## B
  16 #define CAT(A,B) xCAT(A,B)
  17 #undef EL
  18 #define EL CAT(isl_,BASE)
  19 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
  20 #define FN(TYPE,NAME) xFN(TYPE,NAME)
  21 #define xMULTI(BASE) isl_multi_ ## BASE
  22 #define MULTI(BASE) xMULTI(BASE)
  23 #define MULTI_NAME(BASE) "isl_multi_" #BASE
  24 #define xLIST(EL) EL ## _list
  25 #define LIST(EL) xLIST(EL)
  26
  27 isl_ctx *FN(MULTI(BASE),get_ctx)(__isl_keep MULTI(BASE) *multi)
  28 {
  29         return multi ? isl_space_get_ctx(multi->space) : NULL;
  30 }
  31
  32 __isl_give isl_space *FN(MULTI(BASE),get_space)(__isl_keep MULTI(BASE) *multi)
  33 {
  34         return multi ? isl_space_copy(multi->space) : NULL;
  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 __isl_give MULTI(BASE) *FN(MULTI(BASE),alloc)(__isl_take isl_space *space)
  44 {
  45         isl_ctx *ctx;
  46         int n;
  47         MULTI(BASE) *multi;
  48
  49         if (!space)
  50                 return NULL;
  51
  52         ctx = isl_space_get_ctx(space);
  53         n = isl_space_dim(space, isl_dim_out);
  54         multi = isl_calloc(ctx, MULTI(BASE),
  55                          sizeof(MULTI(BASE)) + (n - 1) * sizeof(struct EL *));
  56         if (!multi)
  57                 goto error;
  58
  59         multi->space = space;
  60         multi->n = n;
  61         multi->ref = 1;
  62         return multi;
  63 error:
  64         isl_space_free(space);
  65         return NULL;
  66 }
  67
  68 __isl_give MULTI(BASE) *FN(MULTI(BASE),dup)(__isl_keep MULTI(BASE) *multi)
  69 {
  70         int i;
  71         MULTI(BASE) *dup;
  72
  73         if (!multi)
  74                 return NULL;
  75
  76         dup = FN(MULTI(BASE),alloc)(isl_space_copy(multi->space));
  77         if (!dup)
  78                 return NULL;
  79
  80         for (i = 0; i < multi->n; ++i)
  81                 dup = FN(FN(MULTI(BASE),set),BASE)(dup, i,
  82                                                     FN(EL,copy)(multi->p[i]));
  83
  84         return dup;
  85 }
  86
  87 __isl_give MULTI(BASE) *FN(MULTI(BASE),cow)(__isl_take MULTI(BASE) *multi)
  88 {
  89         if (!multi)
  90                 return NULL;
  91
  92         if (multi->ref == 1)
  93                 return multi;
  94
  95         multi->ref--;
  96         return FN(MULTI(BASE),dup)(multi);
  97 }
  98
  99 __isl_give MULTI(BASE) *FN(MULTI(BASE),copy)(__isl_keep MULTI(BASE) *multi)
 100 {
 101         if (!multi)
 102                 return NULL;
 103
 104         multi->ref++;
 105         return multi;
 106 }
 107
 108 void *FN(MULTI(BASE),free)(__isl_take MULTI(BASE) *multi)
 109 {
 110         int i;
 111
 112         if (!multi)
 113                 return NULL;
 114
 115         if (--multi->ref > 0)
 116                 return NULL;
 117
 118         isl_space_free(multi->space);
 119         for (i = 0; i < multi->n; ++i)
 120                 FN(EL,free)(multi->p[i]);
 121         free(multi);
 122
 123         return NULL;
 124 }
 125
 126 __isl_give MULTI(BASE) *FN(MULTI(BASE),insert_dims)(
 127         __isl_take MULTI(BASE) *multi,
 128         enum isl_dim_type type, unsigned first, unsigned n)
 129 {
 130         int i;
 131
 132         if (!multi)
 133                 return NULL;
 134         if (type == isl_dim_out)
 135                 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
 136                         "cannot insert output/set dimensions",
 137                         return FN(MULTI(BASE),free)(multi));
 138         if (n == 0 && !isl_space_is_named_or_nested(multi->space, type))
 139                 return multi;
 140
 141         multi = FN(MULTI(BASE),cow)(multi);
 142         if (!multi)
 143                 return NULL;
 144
 145         multi->space = isl_space_insert_dims(multi->space, type, first, n);
 146         if (!multi->space)
 147                 return FN(MULTI(BASE),free)(multi);
 148
 149         for (i = 0; i < multi->n; ++i) {
 150                 multi->p[i] = FN(EL,insert_dims)(multi->p[i], type, first, n);
 151                 if (!multi->p[i])
 152                         return FN(MULTI(BASE),free)(multi);
 153         }
 154
 155         return multi;
 156 }
 157
 158 __isl_give MULTI(BASE) *FN(MULTI(BASE),add_dims)(__isl_take MULTI(BASE) *multi,
 159         enum isl_dim_type type, unsigned n)
 160 {
 161         unsigned pos;
 162
 163         pos = FN(MULTI(BASE),dim)(multi, type);
 164
 165         return FN(MULTI(BASE),insert_dims)(multi, type, pos, n);
 166 }
 167
 168 unsigned FN(MULTI(BASE),dim)(__isl_keep MULTI(BASE) *multi,
 169         enum isl_dim_type type)
 170 {
 171         return multi ? isl_space_dim(multi->space, type) : 0;
 172 }
 173
 174 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_dim_name)(
 175         __isl_take MULTI(BASE) *multi,
 176         enum isl_dim_type type, unsigned pos, const char *s)
 177 {
 178         int i;
 179
 180         multi = FN(MULTI(BASE),cow)(multi);
 181         if (!multi)
 182                 return NULL;
 183
 184         multi->space = isl_space_set_dim_name(multi->space, type, pos, s);
 185         if (!multi->space)
 186                 return FN(MULTI(BASE),free)(multi);
 187
 188         if (type == isl_dim_out)
 189                 return multi;
 190         for (i = 0; i < multi->n; ++i) {
 191                 multi->p[i] = FN(EL,set_dim_name)(multi->p[i], type, pos, s);
 192                 if (!multi->p[i])
 193                         return FN(MULTI(BASE),free)(multi);
 194         }
 195
 196         return multi;
 197 }
 198
 199 const char *FN(MULTI(BASE),get_tuple_name)(__isl_keep MULTI(BASE) *multi,
 200         enum isl_dim_type type)
 201 {
 202         return multi ? isl_space_get_tuple_name(multi->space, type) : NULL;
 203 }
 204
 205 __isl_give EL *FN(FN(MULTI(BASE),get),BASE)(__isl_keep MULTI(BASE) *multi,
 206         int pos)
 207 {
 208         isl_ctx *ctx;
 209
 210         if (!multi)
 211                 return NULL;
 212         ctx = FN(MULTI(BASE),get_ctx)(multi);
 213         if (pos < 0 || pos >= multi->n)
 214                 isl_die(ctx, isl_error_invalid,
 215                         "index out of bounds", return NULL);
 216         return FN(EL,copy)(multi->p[pos]);
 217 }
 218
 219 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),set),BASE)(
 220         __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
 221 {
 222         isl_space *multi_space = NULL;
 223         isl_space *el_space = NULL;
 224
 225         multi = FN(MULTI(BASE),cow)(multi);
 226         if (!multi || !el)
 227                 goto error;
 228
 229         multi_space = FN(MULTI(BASE),get_space)(multi);
 230         if (FN(EL,check_match_domain_space)(el, multi_space) < 0)
 231                 goto error;
 232
 233         if (pos < 0 || pos >= multi->n)
 234                 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
 235                         "index out of bounds", goto error);
 236
 237         FN(EL,free)(multi->p[pos]);
 238         multi->p[pos] = el;
 239
 240         isl_space_free(multi_space);
 241         isl_space_free(el_space);
 242
 243         return multi;
 244 error:
 245         FN(MULTI(BASE),free)(multi);
 246         FN(EL,free)(el);
 247         isl_space_free(multi_space);
 248         isl_space_free(el_space);
 249         return NULL;
 250 }
 251
 252 /* Reset the space of "multi".  This function is called from isl_pw_templ.c
 253  * and doesn't know if the space of an element object is represented
 254  * directly or through its domain.  It therefore passes along both,
 255  * which we pass along to the element function since we don't how
 256  * that is represented either.
 257  */
 258 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space_and_domain)(
 259         __isl_take MULTI(BASE) *multi, __isl_take isl_space *space,
 260         __isl_take isl_space *domain)
 261 {
 262         int i;
 263
 264         multi = FN(MULTI(BASE),cow)(multi);
 265         if (!multi || !space || !domain)
 266                 goto error;
 267
 268         for (i = 0; i < multi->n; ++i) {
 269                 multi->p[i] = FN(EL,reset_domain_space)(multi->p[i],
 270                                  isl_space_copy(domain));
 271                 if (!multi->p[i])
 272                         goto error;
 273         }
 274         isl_space_free(domain);
 275         isl_space_free(multi->space);
 276         multi->space = space;
 277
 278         return multi;
 279 error:
 280         isl_space_free(domain);
 281         isl_space_free(space);
 282         FN(MULTI(BASE),free)(multi);
 283         return NULL;
 284 }
 285
 286 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_domain_space)(
 287         __isl_take MULTI(BASE) *multi, __isl_take isl_space *domain)
 288 {
 289         isl_space *space;
 290
 291         space = isl_space_extend_domain_with_range(isl_space_copy(domain),
 292                                                 isl_space_copy(multi->space));
 293         return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
 294 }
 295
 296 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space)(
 297         __isl_take MULTI(BASE) *multi, __isl_take isl_space *space)
 298 {
 299         isl_space *domain;
 300
 301         domain = isl_space_domain(isl_space_copy(space));
 302         return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
 303 }
 304
 305 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_tuple_name)(
 306         __isl_keep MULTI(BASE) *multi, enum isl_dim_type type,
 307         const char *s)
 308 {
 309         isl_space *space;
 310
 311         multi = FN(MULTI(BASE),cow)(multi);
 312         if (!multi)
 313                 return NULL;
 314
 315         space = FN(MULTI(BASE),get_space)(multi);
 316         space = isl_space_set_tuple_name(space, type, s);
 317
 318         return FN(MULTI(BASE),reset_space)(multi, space);
 319 }
 320
 321 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_tuple_id)(
 322         __isl_keep MULTI(BASE) *multi, enum isl_dim_type type,
 323         __isl_take isl_id *id)
 324 {
 325         isl_space *space;
 326
 327         multi = FN(MULTI(BASE),cow)(multi);
 328         if (!multi)
 329                 return isl_id_free(id);
 330
 331         space = FN(MULTI(BASE),get_space)(multi);
 332         space = isl_space_set_tuple_id(space, type, id);
 333
 334         return FN(MULTI(BASE),reset_space)(multi, space);
 335 }
 336
 337 __isl_give MULTI(BASE) *FN(MULTI(BASE),realign_domain)(
 338         __isl_take MULTI(BASE) *multi, __isl_take isl_reordering *exp)
 339 {
 340         int i;
 341
 342         multi = FN(MULTI(BASE),cow)(multi);
 343         if (!multi || !exp)
 344                 goto error;
 345
 346         for (i = 0; i < multi->n; ++i) {
 347                 multi->p[i] = FN(EL,realign_domain)(multi->p[i],
 348                                                 isl_reordering_copy(exp));
 349                 if (!multi->p[i])
 350                         goto error;
 351         }
 352
 353         multi = FN(MULTI(BASE),reset_domain_space)(multi,
 354                                                     isl_space_copy(exp->dim));
 355
 356         isl_reordering_free(exp);
 357         return multi;
 358 error:
 359         isl_reordering_free(exp);
 360         FN(MULTI(BASE),free)(multi);
 361         return NULL;
 362 }
 363
 364 /* Align the parameters of "multi" to those of "model".
 365  */
 366 __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params)(
 367         __isl_take MULTI(BASE) *multi, __isl_take isl_space *model)
 368 {
 369         isl_ctx *ctx;
 370
 371         if (!multi || !model)
 372                 goto error;
 373
 374         ctx = isl_space_get_ctx(model);
 375         if (!isl_space_has_named_params(model))
 376                 isl_die(ctx, isl_error_invalid,
 377                         "model has unnamed parameters", goto error);
 378         if (!isl_space_has_named_params(multi->space))
 379                 isl_die(ctx, isl_error_invalid,
 380                         "input has unnamed parameters", goto error);
 381         if (!isl_space_match(multi->space, isl_dim_param,
 382                              model, isl_dim_param)) {
 383                 isl_reordering *exp;
 384
 385                 model = isl_space_params(model);
 386                 exp = isl_parameter_alignment_reordering(multi->space, model);
 387                 exp = isl_reordering_extend_space(exp,
 388                                     FN(MULTI(BASE),get_domain_space)(multi));
 389                 multi = FN(MULTI(BASE),realign_domain)(multi, exp);
 390         }
 391
 392         isl_space_free(model);
 393         return multi;
 394 error:
 395         isl_space_free(model);
 396         FN(MULTI(BASE),free)(multi);
 397         return NULL;
 398 }
 399
 400 static __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params_multi_set_and)(
 401         __isl_take MULTI(BASE) *multi, __isl_take isl_set *set,
 402         __isl_give MULTI(BASE) *(*fn)(__isl_take MULTI(BASE) *multi,
 403                                         __isl_take isl_set *set))
 404 {
 405         isl_ctx *ctx;
 406
 407         if (!multi || !set)
 408                 goto error;
 409         if (isl_space_match(multi->space, isl_dim_param,
 410                             set->dim, isl_dim_param))
 411                 return fn(multi, set);
 412         ctx = FN(MULTI(BASE),get_ctx)(multi);
 413         if (!isl_space_has_named_params(multi->space) ||
 414             !isl_space_has_named_params(set->dim))
 415                 isl_die(ctx, isl_error_invalid,
 416                         "unaligned unnamed parameters", goto error);
 417         multi = FN(MULTI(BASE),align_params)(multi, isl_set_get_space(set));
 418         set = isl_set_align_params(set, FN(MULTI(BASE),get_space)(multi));
 419         return fn(multi, set);
 420 error:
 421         FN(MULTI(BASE),free)(multi);
 422         isl_set_free(set);
 423         return NULL;
 424 }
 425
 426 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist_aligned)(
 427         __isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
 428 {
 429         int i;
 430
 431         if (!multi || !context)
 432                 goto error;
 433
 434         for (i = 0; i < multi->n; ++i) {
 435                 multi->p[i] = FN(EL,gist)(multi->p[i], isl_set_copy(context));
 436                 if (!multi->p[i])
 437                         goto error;
 438         }
 439
 440         isl_set_free(context);
 441         return multi;
 442 error:
 443         isl_set_free(context);
 444         FN(MULTI(BASE),free)(multi);
 445         return NULL;
 446 }
 447
 448 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist)(__isl_take MULTI(BASE) *multi,
 449         __isl_take isl_set *context)
 450 {
 451         return FN(MULTI(BASE),align_params_multi_set_and)(multi, context,
 452                                                 &FN(MULTI(BASE),gist_aligned));
 453 }
 454
 455 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist_params)(
 456         __isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
 457 {
 458         isl_space *space = FN(MULTI(BASE),get_domain_space)(multi);
 459         isl_set *dom_context = isl_set_universe(space);
 460         dom_context = isl_set_intersect_params(dom_context, context);
 461         return FN(MULTI(BASE),gist)(multi, dom_context);
 462 }
 463
 464 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))(
 465         __isl_take isl_space *space, __isl_take LIST(EL) *list)
 466 {
 467         int i;
 468         int n;
 469         isl_ctx *ctx;
 470         MULTI(BASE) *multi;
 471
 472         if (!space || !list)
 473                 goto error;
 474
 475         ctx = isl_space_get_ctx(space);
 476         n = FN(FN(LIST(EL),n),BASE)(list);
 477         if (n != isl_space_dim(space, isl_dim_out))
 478                 isl_die(ctx, isl_error_invalid,
 479                         "invalid number of elements in list", goto error);
 480
 481         multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
 482         for (i = 0; i < n; ++i) {
 483                 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
 484                                         FN(FN(LIST(EL),get),BASE)(list, i));
 485         }
 486
 487         isl_space_free(space);
 488         FN(LIST(EL),free)(list);
 489         return multi;
 490 error:
 491         isl_space_free(space);
 492         FN(LIST(EL),free)(list);
 493         return NULL;
 494 }
 495
 496 /* Create a multi expression in the given space that maps each
 497  * input dimension to the corresponding output dimension.
 498  */
 499 __isl_give MULTI(BASE) *FN(MULTI(BASE),identity)(__isl_take isl_space *space)
 500 {
 501         int i, n;
 502         isl_local_space *ls;
 503         MULTI(BASE) *multi;
 504
 505         if (!space)
 506                 return NULL;
 507
 508         if (isl_space_is_set(space))
 509                 isl_die(isl_space_get_ctx(space), isl_error_invalid,
 510                         "expecting map space", goto error);
 511
 512         n = isl_space_dim(space, isl_dim_out);
 513         if (n != isl_space_dim(space, isl_dim_in))
 514                 isl_die(isl_space_get_ctx(space), isl_error_invalid,
 515                         "number of input and output dimensions needs to be "
 516                         "the same", goto error);
 517
 518         multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
 519
 520         if (!n) {
 521                 isl_space_free(space);
 522                 return multi;
 523         }
 524
 525         space = isl_space_domain(space);
 526         ls = isl_local_space_from_space(space);
 527
 528         for (i = 0; i < n; ++i) {
 529                 EL *el;
 530                 el = FN(EL,var_on_domain)(isl_local_space_copy(ls),
 531                                                 isl_dim_set, i);
 532                 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i, el);
 533         }
 534
 535         isl_local_space_free(ls);
 536
 537         return multi;
 538 error:
 539         isl_space_free(space);
 540         return NULL;
 541 }
 542
 543 /* Construct a multi expression in the given space with value zero in
 544  * each of the output dimensions.
 545  */
 546 __isl_give MULTI(BASE) *FN(MULTI(BASE),zero)(__isl_take isl_space *space)
 547 {
 548         int n;
 549         MULTI(BASE) *multi;
 550
 551         if (!space)
 552                 return NULL;
 553
 554         n = isl_space_dim(space , isl_dim_out);
 555         multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
 556
 557         if (!n)
 558                 isl_space_free(space);
 559         else {
 560                 int i;
 561                 isl_local_space *ls;
 562                 EL *el;
 563
 564                 space = isl_space_domain(space);
 565                 ls = isl_local_space_from_space(space);
 566                 el = FN(EL,zero_on_domain)(ls);
 567
 568                 for (i = 0; i < n; ++i)
 569                         multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
 570                                                             FN(EL,copy)(el));
 571
 572                 FN(EL,free)(el);
 573         }
 574
 575         return multi;
 576 }
 577
 578 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),BASE)(__isl_take EL *el)
 579 {
 580         MULTI(BASE) *multi;
 581
 582         multi = FN(MULTI(BASE),alloc)(FN(EL,get_space)(el));
 583         multi = FN(FN(MULTI(BASE),set),BASE)(multi, 0, el);
 584
 585         return multi;
 586 }
 587
 588 __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)(
 589         __isl_take MULTI(BASE) *multi,
 590         enum isl_dim_type type, unsigned first, unsigned n)
 591 {
 592         int i;
 593         unsigned dim;
 594
 595         multi = FN(MULTI(BASE),cow)(multi);
 596         if (!multi)
 597                 return NULL;
 598
 599         dim = FN(MULTI(BASE),dim)(multi, type);
 600         if (first + n > dim || first + n < first)
 601                 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
 602                         "index out of bounds",
 603                         return FN(MULTI(BASE),cow)(multi));
 604
 605         multi->space = isl_space_drop_dims(multi->space, type, first, n);
 606         if (!multi->space)
 607                 return FN(MULTI(BASE),cow)(multi);
 608
 609         if (type == isl_dim_out) {
 610                 for (i = 0; i < n; ++i)
 611                         FN(EL,free)(multi->p[first + i]);
 612                 for (i = first; i + n < multi->n; ++i)
 613                         multi->p[i] = multi->p[i + n];
 614                 multi->n -= n;
 615
 616                 return multi;
 617         }
 618
 619         for (i = 0; i < multi->n; ++i) {
 620                 multi->p[i] = FN(EL,drop_dims)(multi->p[i], type, first, n);
 621                 if (!multi->p[i])
 622                         return FN(MULTI(BASE),cow)(multi);
 623         }
 624
 625         return multi;
 626 }
 627
 628 /* Given two MULTI(BASE)s A -> B and C -> D,
 629  * construct a MULTI(BASE) (A * C) -> (B, D).
 630  */
 631 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_product)(
 632         __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
 633 {
 634         int i, n1, n2;
 635         EL *el;
 636         isl_space *space;
 637         MULTI(BASE) *res;
 638
 639         if (!multi1 || !multi2)
 640                 goto error;
 641
 642         space = isl_space_range_product(FN(MULTI(BASE),get_space)(multi1),
 643                                         FN(MULTI(BASE),get_space)(multi2));
 644         res = FN(MULTI(BASE),alloc)(space);
 645
 646         n1 = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
 647         n2 = FN(MULTI(BASE),dim)(multi2, isl_dim_out);
 648
 649         for (i = 0; i < n1; ++i) {
 650                 el = FN(FN(MULTI(BASE),get),BASE)(multi1, i);
 651                 res = FN(FN(MULTI(BASE),set),BASE)(res, i, el);
 652         }
 653
 654         for (i = 0; i < n2; ++i) {
 655                 el = FN(FN(MULTI(BASE),get),BASE)(multi2, i);
 656                 res = FN(FN(MULTI(BASE),set),BASE)(res, n1 + i, el);
 657         }
 658
 659         FN(MULTI(BASE),free)(multi1);
 660         FN(MULTI(BASE),free)(multi2);
 661         return res;
 662 error:
 663         FN(MULTI(BASE),free)(multi1);
 664         FN(MULTI(BASE),free)(multi2);
 665         return NULL;
 666 }
 667
 668 __isl_give MULTI(BASE) *FN(MULTI(BASE),flatten_range)(
 669         __isl_take MULTI(BASE) *multi)
 670 {
 671         if (!multi)
 672                 return NULL;
 673
 674         if (!multi->space->nested[1])
 675                 return multi;
 676
 677         multi = FN(MULTI(BASE),cow)(multi);
 678         if (!multi)
 679                 return NULL;
 680
 681         multi->space = isl_space_flatten_range(multi->space);
 682         if (!multi->space)
 683                 return FN(MULTI(BASE),free)(multi);
 684
 685         return multi;
 686 }
 687
 688 /* Given two MULTI(BASE)s A -> B and C -> D,
 689  * construct a MULTI(BASE) (A * C) -> [B -> D].
 690  */
 691 __isl_give MULTI(BASE) *FN(MULTI(BASE),flat_range_product)(
 692         __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
 693 {
 694         MULTI(BASE) *multi;
 695
 696         multi = FN(MULTI(BASE),range_product)(multi1, multi2);
 697         multi = FN(MULTI(BASE),flatten_range)(multi);
 698         return multi;
 699 }
 700
 701 /* Given two multi expressions, "multi1"
 702  *
 703  *      [A] -> [B1 B2]
 704  *
 705  * where B2 starts at position "pos", and "multi2"
 706  *
 707  *      [A] -> [D]
 708  *
 709  * return the multi expression
 710  *
 711  *      [A] -> [B1 D B2]
 712  */
 713 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_splice)(
 714         __isl_take MULTI(BASE) *multi1, unsigned pos,
 715         __isl_take MULTI(BASE) *multi2)
 716 {
 717         MULTI(BASE) *res;
 718         unsigned dim;
 719
 720         if (!multi1 || !multi2)
 721                 goto error;
 722
 723         dim = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
 724         if (pos > dim)
 725                 isl_die(FN(MULTI(BASE),get_ctx)(multi1), isl_error_invalid,
 726                         "index out of bounds", goto error);
 727
 728         res = FN(MULTI(BASE),copy)(multi1);
 729         res = FN(MULTI(BASE),drop_dims)(res, isl_dim_out, pos, dim - pos);
 730         multi1 = FN(MULTI(BASE),drop_dims)(multi1, isl_dim_out, 0, pos);
 731
 732         res = FN(MULTI(BASE),flat_range_product)(res, multi2);
 733         res = FN(MULTI(BASE),flat_range_product)(res, multi1);
 734
 735         return res;
 736 error:
 737         FN(MULTI(BASE),free)(multi1);
 738         FN(MULTI(BASE),free)(multi2);
 739         return NULL;
 740 }
 741
 742 /* Given two multi expressions, "multi1"
 743  *
 744  *      [A1 A2] -> [B1 B2]
 745  *
 746  * where A2 starts at position "in_pos" and B2 starts at position "out_pos",
 747  * and "multi2"
 748  *
 749  *      [C] -> [D]
 750  *
 751  * return the multi expression
 752  *
 753  *      [A1 C A2] -> [B1 D B2]
 754  *
 755  * We first insert input dimensions to obtain
 756  *
 757  *      [A1 C A2] -> [B1 B2]
 758  *
 759  * and
 760  *
 761  *      [A1 C A2] -> [D]
 762  *
 763  * and then apply range_splice.
 764  */
 765 __isl_give MULTI(BASE) *FN(MULTI(BASE),splice)(
 766         __isl_take MULTI(BASE) *multi1, unsigned in_pos, unsigned out_pos,
 767         __isl_take MULTI(BASE) *multi2)
 768 {
 769         unsigned n_in1;
 770         unsigned n_in2;
 771
 772         if (!multi1 || !multi2)
 773                 goto error;
 774
 775         n_in1 = FN(MULTI(BASE),dim)(multi1, isl_dim_in);
 776         if (in_pos > n_in1)
 777                 isl_die(FN(MULTI(BASE),get_ctx)(multi1), isl_error_invalid,
 778                         "index out of bounds", goto error);
 779
 780         n_in2 = FN(MULTI(BASE),dim)(multi2, isl_dim_in);
 781
 782         multi1 = FN(MULTI(BASE),insert_dims)(multi1, isl_dim_in, in_pos, n_in2);
 783         multi2 = FN(MULTI(BASE),insert_dims)(multi2, isl_dim_in, n_in2,
 784                                                 n_in1 - in_pos);
 785         multi2 = FN(MULTI(BASE),insert_dims)(multi2, isl_dim_in, 0, in_pos);
 786
 787         return FN(MULTI(BASE),range_splice)(multi1, out_pos, multi2);
 788 error:
 789         FN(MULTI(BASE),free)(multi1);
 790         FN(MULTI(BASE),free)(multi2);
 791         return NULL;
 792 }
 793
 794 /* This function is currently only used from isl_aff.c
 795  */
 796 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
 797         __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
 798         __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
 799         __attribute__ ((unused));
 800
 801 /* Pairwise perform "fn" to the elements of "multi1" and "multi2" and
 802  * return the result.
 803  */
 804 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
 805         __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
 806         __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
 807 {
 808         int i;
 809         isl_ctx *ctx;
 810
 811         multi1 = FN(MULTI(BASE),cow)(multi1);
 812         if (!multi1 || !multi2)
 813                 goto error;
 814
 815         ctx = FN(MULTI(BASE),get_ctx)(multi1);
 816         if (!isl_space_is_equal(multi1->space, multi2->space))
 817                 isl_die(ctx, isl_error_invalid,
 818                         "spaces don't match", goto error);
 819
 820         for (i = 0; i < multi1->n; ++i) {
 821                 multi1->p[i] = fn(multi1->p[i], FN(EL,copy)(multi2->p[i]));
 822                 if (!multi1->p[i])
 823                         goto error;
 824         }
 825
 826         FN(MULTI(BASE),free)(multi2);
 827         return multi1;
 828 error:
 829         FN(MULTI(BASE),free)(multi1);
 830         FN(MULTI(BASE),free)(multi2);
 831         return NULL;
 832 }