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         el_space = FN(EL,get_space)(el);
 231
 232         if (!isl_space_match(multi_space, isl_dim_param,
 233                             el_space, isl_dim_param))
 234                 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
 235                         "parameters don't match", goto error);
 236         if (!isl_space_tuple_match(multi_space, isl_dim_in,
 237                             el_space, isl_dim_in))
 238                 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
 239                         "domains don't match", goto error);
 240
 241         if (pos < 0 || pos >= multi->n)
 242                 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
 243                         "index out of bounds", goto error);
 244
 245         FN(EL,free)(multi->p[pos]);
 246         multi->p[pos] = el;
 247
 248         isl_space_free(multi_space);
 249         isl_space_free(el_space);
 250
 251         return multi;
 252 error:
 253         FN(MULTI(BASE),free)(multi);
 254         FN(EL,free)(el);
 255         isl_space_free(multi_space);
 256         isl_space_free(el_space);
 257         return NULL;
 258 }
 259
 260 /* Reset the space of "multi".  This function is called from isl_pw_templ.c
 261  * and doesn't know if the space of an element object is represented
 262  * directly or through its domain.  It therefore passes along both,
 263  * which we pass along to the element function since we don't how
 264  * that is represented either.
 265  */
 266 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space_and_domain)(
 267         __isl_take MULTI(BASE) *multi, __isl_take isl_space *space,
 268         __isl_take isl_space *domain)
 269 {
 270         int i;
 271
 272         multi = FN(MULTI(BASE),cow)(multi);
 273         if (!multi || !space || !domain)
 274                 goto error;
 275
 276         for (i = 0; i < multi->n; ++i) {
 277                 multi->p[i] = FN(EL,reset_domain_space)(multi->p[i],
 278                                  isl_space_copy(domain));
 279                 if (!multi->p[i])
 280                         goto error;
 281         }
 282         isl_space_free(domain);
 283         isl_space_free(multi->space);
 284         multi->space = space;
 285
 286         return multi;
 287 error:
 288         isl_space_free(domain);
 289         isl_space_free(space);
 290         FN(MULTI(BASE),free)(multi);
 291         return NULL;
 292 }
 293
 294 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_domain_space)(
 295         __isl_take MULTI(BASE) *multi, __isl_take isl_space *domain)
 296 {
 297         isl_space *space;
 298
 299         space = isl_space_extend_domain_with_range(isl_space_copy(domain),
 300                                                 isl_space_copy(multi->space));
 301         return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
 302 }
 303
 304 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space)(
 305         __isl_take MULTI(BASE) *multi, __isl_take isl_space *space)
 306 {
 307         isl_space *domain;
 308
 309         domain = isl_space_domain(isl_space_copy(space));
 310         return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
 311 }
 312
 313 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_tuple_name)(
 314         __isl_keep MULTI(BASE) *multi, enum isl_dim_type type,
 315         const char *s)
 316 {
 317         isl_space *space;
 318
 319         multi = FN(MULTI(BASE),cow)(multi);
 320         if (!multi)
 321                 return NULL;
 322
 323         space = FN(MULTI(BASE),get_space)(multi);
 324         space = isl_space_set_tuple_name(space, type, s);
 325
 326         return FN(MULTI(BASE),reset_space)(multi, space);
 327 }
 328
 329 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_tuple_id)(
 330         __isl_keep MULTI(BASE) *multi, enum isl_dim_type type,
 331         __isl_take isl_id *id)
 332 {
 333         isl_space *space;
 334
 335         multi = FN(MULTI(BASE),cow)(multi);
 336         if (!multi)
 337                 return isl_id_free(id);
 338
 339         space = FN(MULTI(BASE),get_space)(multi);
 340         space = isl_space_set_tuple_id(space, type, id);
 341
 342         return FN(MULTI(BASE),reset_space)(multi, space);
 343 }
 344
 345 __isl_give MULTI(BASE) *FN(MULTI(BASE),realign_domain)(
 346         __isl_take MULTI(BASE) *multi, __isl_take isl_reordering *exp)
 347 {
 348         int i;
 349
 350         multi = FN(MULTI(BASE),cow)(multi);
 351         if (!multi || !exp)
 352                 goto error;
 353
 354         for (i = 0; i < multi->n; ++i) {
 355                 multi->p[i] = FN(EL,realign_domain)(multi->p[i],
 356                                                 isl_reordering_copy(exp));
 357                 if (!multi->p[i])
 358                         goto error;
 359         }
 360
 361         multi = FN(MULTI(BASE),reset_domain_space)(multi,
 362                                                     isl_space_copy(exp->dim));
 363
 364         isl_reordering_free(exp);
 365         return multi;
 366 error:
 367         isl_reordering_free(exp);
 368         FN(MULTI(BASE),free)(multi);
 369         return NULL;
 370 }
 371
 372 /* Align the parameters of "multi" to those of "model".
 373  */
 374 __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params)(
 375         __isl_take MULTI(BASE) *multi, __isl_take isl_space *model)
 376 {
 377         isl_ctx *ctx;
 378
 379         if (!multi || !model)
 380                 goto error;
 381
 382         ctx = isl_space_get_ctx(model);
 383         if (!isl_space_has_named_params(model))
 384                 isl_die(ctx, isl_error_invalid,
 385                         "model has unnamed parameters", goto error);
 386         if (!isl_space_has_named_params(multi->space))
 387                 isl_die(ctx, isl_error_invalid,
 388                         "input has unnamed parameters", goto error);
 389         if (!isl_space_match(multi->space, isl_dim_param,
 390                              model, isl_dim_param)) {
 391                 isl_reordering *exp;
 392
 393                 model = isl_space_params(model);
 394                 exp = isl_parameter_alignment_reordering(multi->space, model);
 395                 exp = isl_reordering_extend_space(exp,
 396                                     FN(MULTI(BASE),get_domain_space)(multi));
 397                 multi = FN(MULTI(BASE),realign_domain)(multi, exp);
 398         }
 399
 400         isl_space_free(model);
 401         return multi;
 402 error:
 403         isl_space_free(model);
 404         FN(MULTI(BASE),free)(multi);
 405         return NULL;
 406 }
 407
 408 static __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params_multi_set_and)(
 409         __isl_take MULTI(BASE) *multi, __isl_take isl_set *set,
 410         __isl_give MULTI(BASE) *(*fn)(__isl_take MULTI(BASE) *multi,
 411                                         __isl_take isl_set *set))
 412 {
 413         isl_ctx *ctx;
 414
 415         if (!multi || !set)
 416                 goto error;
 417         if (isl_space_match(multi->space, isl_dim_param,
 418                             set->dim, isl_dim_param))
 419                 return fn(multi, set);
 420         ctx = FN(MULTI(BASE),get_ctx)(multi);
 421         if (!isl_space_has_named_params(multi->space) ||
 422             !isl_space_has_named_params(set->dim))
 423                 isl_die(ctx, isl_error_invalid,
 424                         "unaligned unnamed parameters", goto error);
 425         multi = FN(MULTI(BASE),align_params)(multi, isl_set_get_space(set));
 426         set = isl_set_align_params(set, FN(MULTI(BASE),get_space)(multi));
 427         return fn(multi, set);
 428 error:
 429         FN(MULTI(BASE),free)(multi);
 430         isl_set_free(set);
 431         return NULL;
 432 }
 433
 434 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist_aligned)(
 435         __isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
 436 {
 437         int i;
 438
 439         if (!multi || !context)
 440                 goto error;
 441
 442         for (i = 0; i < multi->n; ++i) {
 443                 multi->p[i] = FN(EL,gist)(multi->p[i], isl_set_copy(context));
 444                 if (!multi->p[i])
 445                         goto error;
 446         }
 447
 448         isl_set_free(context);
 449         return multi;
 450 error:
 451         isl_set_free(context);
 452         FN(MULTI(BASE),free)(multi);
 453         return NULL;
 454 }
 455
 456 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist)(__isl_take MULTI(BASE) *multi,
 457         __isl_take isl_set *context)
 458 {
 459         return FN(MULTI(BASE),align_params_multi_set_and)(multi, context,
 460                                                 &FN(MULTI(BASE),gist_aligned));
 461 }
 462
 463 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist_params)(
 464         __isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
 465 {
 466         isl_space *space = FN(MULTI(BASE),get_domain_space)(multi);
 467         isl_set *dom_context = isl_set_universe(space);
 468         dom_context = isl_set_intersect_params(dom_context, context);
 469         return FN(MULTI(BASE),gist)(multi, dom_context);
 470 }
 471
 472 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))(
 473         __isl_take isl_space *space, __isl_take LIST(EL) *list)
 474 {
 475         int i;
 476         int n;
 477         isl_ctx *ctx;
 478         MULTI(BASE) *multi;
 479
 480         if (!space || !list)
 481                 goto error;
 482
 483         ctx = isl_space_get_ctx(space);
 484         n = FN(FN(LIST(EL),n),BASE)(list);
 485         if (n != isl_space_dim(space, isl_dim_out))
 486                 isl_die(ctx, isl_error_invalid,
 487                         "invalid number of elements in list", goto error);
 488
 489         multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
 490         for (i = 0; i < n; ++i) {
 491                 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
 492                                         FN(FN(LIST(EL),get),BASE)(list, i));
 493         }
 494
 495         isl_space_free(space);
 496         FN(LIST(EL),free)(list);
 497         return multi;
 498 error:
 499         isl_space_free(space);
 500         FN(LIST(EL),free)(list);
 501         return NULL;
 502 }
 503
 504 /* Create a multi expression in the given space that maps each
 505  * input dimension to the corresponding output dimension.
 506  */
 507 __isl_give MULTI(BASE) *FN(MULTI(BASE),identity)(__isl_take isl_space *space)
 508 {
 509         int i, n;
 510         isl_local_space *ls;
 511         MULTI(BASE) *multi;
 512
 513         if (!space)
 514                 return NULL;
 515
 516         if (isl_space_is_set(space))
 517                 isl_die(isl_space_get_ctx(space), isl_error_invalid,
 518                         "expecting map space", goto error);
 519
 520         n = isl_space_dim(space, isl_dim_out);
 521         if (n != isl_space_dim(space, isl_dim_in))
 522                 isl_die(isl_space_get_ctx(space), isl_error_invalid,
 523                         "number of input and output dimensions needs to be "
 524                         "the same", goto error);
 525
 526         multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
 527
 528         if (!n) {
 529                 isl_space_free(space);
 530                 return multi;
 531         }
 532
 533         space = isl_space_domain(space);
 534         ls = isl_local_space_from_space(space);
 535
 536         for (i = 0; i < n; ++i) {
 537                 EL *el;
 538                 el = FN(EL,var_on_domain)(isl_local_space_copy(ls),
 539                                                 isl_dim_set, i);
 540                 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i, el);
 541         }
 542
 543         isl_local_space_free(ls);
 544
 545         return multi;
 546 error:
 547         isl_space_free(space);
 548         return NULL;
 549 }
 550
 551 /* Construct a multi expression in the given space with value zero in
 552  * each of the output dimensions.
 553  */
 554 __isl_give MULTI(BASE) *FN(MULTI(BASE),zero)(__isl_take isl_space *space)
 555 {
 556         int n;
 557         MULTI(BASE) *multi;
 558
 559         if (!space)
 560                 return NULL;
 561
 562         n = isl_space_dim(space , isl_dim_out);
 563         multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
 564
 565         if (!n)
 566                 isl_space_free(space);
 567         else {
 568                 int i;
 569                 isl_local_space *ls;
 570                 EL *el;
 571
 572                 space = isl_space_domain(space);
 573                 ls = isl_local_space_from_space(space);
 574                 el = FN(EL,zero_on_domain)(ls);
 575
 576                 for (i = 0; i < n; ++i)
 577                         multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
 578                                                             FN(EL,copy)(el));
 579
 580                 FN(EL,free)(el);
 581         }
 582
 583         return multi;
 584 }
 585
 586 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),BASE)(__isl_take EL *el)
 587 {
 588         MULTI(BASE) *multi;
 589
 590         multi = FN(MULTI(BASE),alloc)(FN(EL,get_space)(el));
 591         multi = FN(FN(MULTI(BASE),set),BASE)(multi, 0, el);
 592
 593         return multi;
 594 }
 595
 596 __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)(
 597         __isl_take MULTI(BASE) *multi,
 598         enum isl_dim_type type, unsigned first, unsigned n)
 599 {
 600         int i;
 601         unsigned dim;
 602
 603         multi = FN(MULTI(BASE),cow)(multi);
 604         if (!multi)
 605                 return NULL;
 606
 607         dim = FN(MULTI(BASE),dim)(multi, type);
 608         if (first + n > dim || first + n < first)
 609                 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
 610                         "index out of bounds",
 611                         return FN(MULTI(BASE),cow)(multi));
 612
 613         multi->space = isl_space_drop_dims(multi->space, type, first, n);
 614         if (!multi->space)
 615                 return FN(MULTI(BASE),cow)(multi);
 616
 617         if (type == isl_dim_out) {
 618                 for (i = 0; i < n; ++i)
 619                         FN(EL,free)(multi->p[first + i]);
 620                 for (i = first; i + n < multi->n; ++i)
 621                         multi->p[i] = multi->p[i + n];
 622                 multi->n -= n;
 623
 624                 return multi;
 625         }
 626
 627         for (i = 0; i < multi->n; ++i) {
 628                 multi->p[i] = FN(EL,drop_dims)(multi->p[i], type, first, n);
 629                 if (!multi->p[i])
 630                         return FN(MULTI(BASE),cow)(multi);
 631         }
 632
 633         return multi;
 634 }
 635
 636 /* Given two MULTI(BASE)s A -> B and C -> D,
 637  * construct a MULTI(BASE) (A * C) -> (B, D).
 638  */
 639 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_product)(
 640         __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
 641 {
 642         int i, n1, n2;
 643         EL *el;
 644         isl_space *space;
 645         MULTI(BASE) *res;
 646
 647         if (!multi1 || !multi2)
 648                 goto error;
 649
 650         space = isl_space_range_product(FN(MULTI(BASE),get_space)(multi1),
 651                                         FN(MULTI(BASE),get_space)(multi2));
 652         res = FN(MULTI(BASE),alloc)(space);
 653
 654         n1 = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
 655         n2 = FN(MULTI(BASE),dim)(multi2, isl_dim_out);
 656
 657         for (i = 0; i < n1; ++i) {
 658                 el = FN(FN(MULTI(BASE),get),BASE)(multi1, i);
 659                 res = FN(FN(MULTI(BASE),set),BASE)(res, i, el);
 660         }
 661
 662         for (i = 0; i < n2; ++i) {
 663                 el = FN(FN(MULTI(BASE),get),BASE)(multi2, i);
 664                 res = FN(FN(MULTI(BASE),set),BASE)(res, n1 + i, el);
 665         }
 666
 667         FN(MULTI(BASE),free)(multi1);
 668         FN(MULTI(BASE),free)(multi2);
 669         return res;
 670 error:
 671         FN(MULTI(BASE),free)(multi1);
 672         FN(MULTI(BASE),free)(multi2);
 673         return NULL;
 674 }
 675
 676 __isl_give MULTI(BASE) *FN(MULTI(BASE),flatten_range)(
 677         __isl_take MULTI(BASE) *multi)
 678 {
 679         if (!multi)
 680                 return NULL;
 681
 682         if (!multi->space->nested[1])
 683                 return multi;
 684
 685         multi = FN(MULTI(BASE),cow)(multi);
 686         if (!multi)
 687                 return NULL;
 688
 689         multi->space = isl_space_flatten_range(multi->space);
 690         if (!multi->space)
 691                 return FN(MULTI(BASE),free)(multi);
 692
 693         return multi;
 694 }
 695
 696 /* Given two MULTI(BASE)s A -> B and C -> D,
 697  * construct a MULTI(BASE) (A * C) -> [B -> D].
 698  */
 699 __isl_give MULTI(BASE) *FN(MULTI(BASE),flat_range_product)(
 700         __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
 701 {
 702         MULTI(BASE) *multi;
 703
 704         multi = FN(MULTI(BASE),range_product)(multi1, multi2);
 705         multi = FN(MULTI(BASE),flatten_range)(multi);
 706         return multi;
 707 }
 708
 709 /* Given two multi expressions, "multi1"
 710  *
 711  *      [A] -> [B1 B2]
 712  *
 713  * where B2 starts at position "pos", and "multi2"
 714  *
 715  *      [A] -> [D]
 716  *
 717  * return the multi expression
 718  *
 719  *      [A] -> [B1 D B2]
 720  */
 721 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_splice)(
 722         __isl_take MULTI(BASE) *multi1, unsigned pos,
 723         __isl_take MULTI(BASE) *multi2)
 724 {
 725         MULTI(BASE) *res;
 726         unsigned dim;
 727
 728         if (!multi1 || !multi2)
 729                 goto error;
 730
 731         dim = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
 732         if (pos > dim)
 733                 isl_die(FN(MULTI(BASE),get_ctx)(multi1), isl_error_invalid,
 734                         "index out of bounds", goto error);
 735
 736         res = FN(MULTI(BASE),copy)(multi1);
 737         res = FN(MULTI(BASE),drop_dims)(res, isl_dim_out, pos, dim - pos);
 738         multi1 = FN(MULTI(BASE),drop_dims)(multi1, isl_dim_out, 0, pos);
 739
 740         res = FN(MULTI(BASE),flat_range_product)(res, multi2);
 741         res = FN(MULTI(BASE),flat_range_product)(res, multi1);
 742
 743         return res;
 744 error:
 745         FN(MULTI(BASE),free)(multi1);
 746         FN(MULTI(BASE),free)(multi2);
 747         return NULL;
 748 }
 749
 750 /* Given two multi expressions, "multi1"
 751  *
 752  *      [A1 A2] -> [B1 B2]
 753  *
 754  * where A2 starts at position "in_pos" and B2 starts at position "out_pos",
 755  * and "multi2"
 756  *
 757  *      [C] -> [D]
 758  *
 759  * return the multi expression
 760  *
 761  *      [A1 C A2] -> [B1 D B2]
 762  *
 763  * We first insert input dimensions to obtain
 764  *
 765  *      [A1 C A2] -> [B1 B2]
 766  *
 767  * and
 768  *
 769  *      [A1 C A2] -> [D]
 770  *
 771  * and then apply range_splice.
 772  */
 773 __isl_give MULTI(BASE) *FN(MULTI(BASE),splice)(
 774         __isl_take MULTI(BASE) *multi1, unsigned in_pos, unsigned out_pos,
 775         __isl_take MULTI(BASE) *multi2)
 776 {
 777         unsigned n_in1;
 778         unsigned n_in2;
 779
 780         if (!multi1 || !multi2)
 781                 goto error;
 782
 783         n_in1 = FN(MULTI(BASE),dim)(multi1, isl_dim_in);
 784         if (in_pos > n_in1)
 785                 isl_die(FN(MULTI(BASE),get_ctx)(multi1), isl_error_invalid,
 786                         "index out of bounds", goto error);
 787
 788         n_in2 = FN(MULTI(BASE),dim)(multi2, isl_dim_in);
 789
 790         multi1 = FN(MULTI(BASE),insert_dims)(multi1, isl_dim_in, in_pos, n_in2);
 791         multi2 = FN(MULTI(BASE),insert_dims)(multi2, isl_dim_in, n_in2,
 792                                                 n_in1 - in_pos);
 793         multi2 = FN(MULTI(BASE),insert_dims)(multi2, isl_dim_in, 0, in_pos);
 794
 795         return FN(MULTI(BASE),range_splice)(multi1, out_pos, multi2);
 796 error:
 797         FN(MULTI(BASE),free)(multi1);
 798         FN(MULTI(BASE),free)(multi2);
 799         return NULL;
 800 }
 801
 802 /* This function is currently only used from isl_aff.c
 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         __attribute__ ((unused));
 808
 809 /* Pairwise perform "fn" to the elements of "multi1" and "multi2" and
 810  * return the result.
 811  */
 812 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
 813         __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
 814         __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
 815 {
 816         int i;
 817         isl_ctx *ctx;
 818
 819         multi1 = FN(MULTI(BASE),cow)(multi1);
 820         if (!multi1 || !multi2)
 821                 goto error;
 822
 823         ctx = FN(MULTI(BASE),get_ctx)(multi1);
 824         if (!isl_space_is_equal(multi1->space, multi2->space))
 825                 isl_die(ctx, isl_error_invalid,
 826                         "spaces don't match", goto error);
 827
 828         for (i = 0; i < multi1->n; ++i) {
 829                 multi1->p[i] = fn(multi1->p[i], FN(EL,copy)(multi2->p[i]));
 830                 if (!multi1->p[i])
 831                         goto error;
 832         }
 833
 834         FN(MULTI(BASE),free)(multi2);
 835         return multi1;
 836 error:
 837         FN(MULTI(BASE),free)(multi1);
 838         FN(MULTI(BASE),free)(multi2);
 839         return NULL;
 840 }