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