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 #ifndef NO_GIST
 401 static __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params_multi_set_and)(
 402         __isl_take MULTI(BASE) *multi, __isl_take isl_set *set,
 403         __isl_give MULTI(BASE) *(*fn)(__isl_take MULTI(BASE) *multi,
 404                                         __isl_take isl_set *set))
 405 {
 406         isl_ctx *ctx;
 407
 408         if (!multi || !set)
 409                 goto error;
 410         if (isl_space_match(multi->space, isl_dim_param,
 411                             set->dim, isl_dim_param))
 412                 return fn(multi, set);
 413         ctx = FN(MULTI(BASE),get_ctx)(multi);
 414         if (!isl_space_has_named_params(multi->space) ||
 415             !isl_space_has_named_params(set->dim))
 416                 isl_die(ctx, isl_error_invalid,
 417                         "unaligned unnamed parameters", goto error);
 418         multi = FN(MULTI(BASE),align_params)(multi, isl_set_get_space(set));
 419         set = isl_set_align_params(set, FN(MULTI(BASE),get_space)(multi));
 420         return fn(multi, set);
 421 error:
 422         FN(MULTI(BASE),free)(multi);
 423         isl_set_free(set);
 424         return NULL;
 425 }
 426
 427 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist_aligned)(
 428         __isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
 429 {
 430         int i;
 431
 432         multi = FN(MULTI(BASE),cow)(multi);
 433         if (!multi || !context)
 434                 goto error;
 435
 436         for (i = 0; i < multi->n; ++i) {
 437                 multi->p[i] = FN(EL,gist)(multi->p[i], isl_set_copy(context));
 438                 if (!multi->p[i])
 439                         goto error;
 440         }
 441
 442         isl_set_free(context);
 443         return multi;
 444 error:
 445         isl_set_free(context);
 446         FN(MULTI(BASE),free)(multi);
 447         return NULL;
 448 }
 449
 450 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist)(__isl_take MULTI(BASE) *multi,
 451         __isl_take isl_set *context)
 452 {
 453         return FN(MULTI(BASE),align_params_multi_set_and)(multi, context,
 454                                                 &FN(MULTI(BASE),gist_aligned));
 455 }
 456
 457 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist_params)(
 458         __isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
 459 {
 460         isl_space *space = FN(MULTI(BASE),get_domain_space)(multi);
 461         isl_set *dom_context = isl_set_universe(space);
 462         dom_context = isl_set_intersect_params(dom_context, context);
 463         return FN(MULTI(BASE),gist)(multi, dom_context);
 464 }
 465 #endif
 466
 467 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))(
 468         __isl_take isl_space *space, __isl_take LIST(EL) *list)
 469 {
 470         int i;
 471         int n;
 472         isl_ctx *ctx;
 473         MULTI(BASE) *multi;
 474
 475         if (!space || !list)
 476                 goto error;
 477
 478         ctx = isl_space_get_ctx(space);
 479         n = FN(FN(LIST(EL),n),BASE)(list);
 480         if (n != isl_space_dim(space, isl_dim_out))
 481                 isl_die(ctx, isl_error_invalid,
 482                         "invalid number of elements in list", goto error);
 483
 484         multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
 485         for (i = 0; i < n; ++i) {
 486                 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
 487                                         FN(FN(LIST(EL),get),BASE)(list, i));
 488         }
 489
 490         isl_space_free(space);
 491         FN(LIST(EL),free)(list);
 492         return multi;
 493 error:
 494         isl_space_free(space);
 495         FN(LIST(EL),free)(list);
 496         return NULL;
 497 }
 498
 499 #ifndef NO_IDENTITY
 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 #endif
 547
 548 /* Construct a multi expression in the given space with value zero in
 549  * each of the output dimensions.
 550  */
 551 __isl_give MULTI(BASE) *FN(MULTI(BASE),zero)(__isl_take isl_space *space)
 552 {
 553         int n;
 554         MULTI(BASE) *multi;
 555
 556         if (!space)
 557                 return NULL;
 558
 559         n = isl_space_dim(space , isl_dim_out);
 560         multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
 561
 562         if (!n)
 563                 isl_space_free(space);
 564         else {
 565                 int i;
 566                 isl_local_space *ls;
 567                 EL *el;
 568
 569                 space = isl_space_domain(space);
 570                 ls = isl_local_space_from_space(space);
 571                 el = FN(EL,zero_on_domain)(ls);
 572
 573                 for (i = 0; i < n; ++i)
 574                         multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
 575                                                             FN(EL,copy)(el));
 576
 577                 FN(EL,free)(el);
 578         }
 579
 580         return multi;
 581 }
 582
 583 #ifndef NO_FROM_BASE
 584 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),BASE)(__isl_take EL *el)
 585 {
 586         MULTI(BASE) *multi;
 587
 588         multi = FN(MULTI(BASE),alloc)(FN(EL,get_space)(el));
 589         multi = FN(FN(MULTI(BASE),set),BASE)(multi, 0, el);
 590
 591         return multi;
 592 }
 593 #endif
 594
 595 __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)(
 596         __isl_take MULTI(BASE) *multi,
 597         enum isl_dim_type type, unsigned first, unsigned n)
 598 {
 599         int i;
 600         unsigned dim;
 601
 602         multi = FN(MULTI(BASE),cow)(multi);
 603         if (!multi)
 604                 return NULL;
 605
 606         dim = FN(MULTI(BASE),dim)(multi, type);
 607         if (first + n > dim || first + n < first)
 608                 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
 609                         "index out of bounds",
 610                         return FN(MULTI(BASE),cow)(multi));
 611
 612         multi->space = isl_space_drop_dims(multi->space, type, first, n);
 613         if (!multi->space)
 614                 return FN(MULTI(BASE),cow)(multi);
 615
 616         if (type == isl_dim_out) {
 617                 for (i = 0; i < n; ++i)
 618                         FN(EL,free)(multi->p[first + i]);
 619                 for (i = first; i + n < multi->n; ++i)
 620                         multi->p[i] = multi->p[i + n];
 621                 multi->n -= n;
 622
 623                 return multi;
 624         }
 625
 626         for (i = 0; i < multi->n; ++i) {
 627                 multi->p[i] = FN(EL,drop_dims)(multi->p[i], type, first, n);
 628                 if (!multi->p[i])
 629                         return FN(MULTI(BASE),cow)(multi);
 630         }
 631
 632         return multi;
 633 }
 634
 635 /* Given two MULTI(BASE)s A -> B and C -> D,
 636  * construct a MULTI(BASE) (A * C) -> (B, D).
 637  */
 638 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_product)(
 639         __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
 640 {
 641         int i, n1, n2;
 642         EL *el;
 643         isl_space *space;
 644         MULTI(BASE) *res;
 645
 646         if (!multi1 || !multi2)
 647                 goto error;
 648
 649         space = isl_space_range_product(FN(MULTI(BASE),get_space)(multi1),
 650                                         FN(MULTI(BASE),get_space)(multi2));
 651         res = FN(MULTI(BASE),alloc)(space);
 652
 653         n1 = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
 654         n2 = FN(MULTI(BASE),dim)(multi2, isl_dim_out);
 655
 656         for (i = 0; i < n1; ++i) {
 657                 el = FN(FN(MULTI(BASE),get),BASE)(multi1, i);
 658                 res = FN(FN(MULTI(BASE),set),BASE)(res, i, el);
 659         }
 660
 661         for (i = 0; i < n2; ++i) {
 662                 el = FN(FN(MULTI(BASE),get),BASE)(multi2, i);
 663                 res = FN(FN(MULTI(BASE),set),BASE)(res, n1 + i, el);
 664         }
 665
 666         FN(MULTI(BASE),free)(multi1);
 667         FN(MULTI(BASE),free)(multi2);
 668         return res;
 669 error:
 670         FN(MULTI(BASE),free)(multi1);
 671         FN(MULTI(BASE),free)(multi2);
 672         return NULL;
 673 }
 674
 675 __isl_give MULTI(BASE) *FN(MULTI(BASE),flatten_range)(
 676         __isl_take MULTI(BASE) *multi)
 677 {
 678         if (!multi)
 679                 return NULL;
 680
 681         if (!multi->space->nested[1])
 682                 return multi;
 683
 684         multi = FN(MULTI(BASE),cow)(multi);
 685         if (!multi)
 686                 return NULL;
 687
 688         multi->space = isl_space_flatten_range(multi->space);
 689         if (!multi->space)
 690                 return FN(MULTI(BASE),free)(multi);
 691
 692         return multi;
 693 }
 694
 695 /* Given two MULTI(BASE)s A -> B and C -> D,
 696  * construct a MULTI(BASE) (A * C) -> [B -> D].
 697  */
 698 __isl_give MULTI(BASE) *FN(MULTI(BASE),flat_range_product)(
 699         __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
 700 {
 701         MULTI(BASE) *multi;
 702
 703         multi = FN(MULTI(BASE),range_product)(multi1, multi2);
 704         multi = FN(MULTI(BASE),flatten_range)(multi);
 705         return multi;
 706 }
 707
 708 /* Given two multi expressions, "multi1"
 709  *
 710  *      [A] -> [B1 B2]
 711  *
 712  * where B2 starts at position "pos", and "multi2"
 713  *
 714  *      [A] -> [D]
 715  *
 716  * return the multi expression
 717  *
 718  *      [A] -> [B1 D B2]
 719  */
 720 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_splice)(
 721         __isl_take MULTI(BASE) *multi1, unsigned pos,
 722         __isl_take MULTI(BASE) *multi2)
 723 {
 724         MULTI(BASE) *res;
 725         unsigned dim;
 726
 727         if (!multi1 || !multi2)
 728                 goto error;
 729
 730         dim = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
 731         if (pos > dim)
 732                 isl_die(FN(MULTI(BASE),get_ctx)(multi1), isl_error_invalid,
 733                         "index out of bounds", goto error);
 734
 735         res = FN(MULTI(BASE),copy)(multi1);
 736         res = FN(MULTI(BASE),drop_dims)(res, isl_dim_out, pos, dim - pos);
 737         multi1 = FN(MULTI(BASE),drop_dims)(multi1, isl_dim_out, 0, pos);
 738
 739         res = FN(MULTI(BASE),flat_range_product)(res, multi2);
 740         res = FN(MULTI(BASE),flat_range_product)(res, multi1);
 741
 742         return res;
 743 error:
 744         FN(MULTI(BASE),free)(multi1);
 745         FN(MULTI(BASE),free)(multi2);
 746         return NULL;
 747 }
 748
 749 /* Given two multi expressions, "multi1"
 750  *
 751  *      [A1 A2] -> [B1 B2]
 752  *
 753  * where A2 starts at position "in_pos" and B2 starts at position "out_pos",
 754  * and "multi2"
 755  *
 756  *      [C] -> [D]
 757  *
 758  * return the multi expression
 759  *
 760  *      [A1 C A2] -> [B1 D B2]
 761  *
 762  * We first insert input dimensions to obtain
 763  *
 764  *      [A1 C A2] -> [B1 B2]
 765  *
 766  * and
 767  *
 768  *      [A1 C A2] -> [D]
 769  *
 770  * and then apply range_splice.
 771  */
 772 __isl_give MULTI(BASE) *FN(MULTI(BASE),splice)(
 773         __isl_take MULTI(BASE) *multi1, unsigned in_pos, unsigned out_pos,
 774         __isl_take MULTI(BASE) *multi2)
 775 {
 776         unsigned n_in1;
 777         unsigned n_in2;
 778
 779         if (!multi1 || !multi2)
 780                 goto error;
 781
 782         n_in1 = FN(MULTI(BASE),dim)(multi1, isl_dim_in);
 783         if (in_pos > n_in1)
 784                 isl_die(FN(MULTI(BASE),get_ctx)(multi1), isl_error_invalid,
 785                         "index out of bounds", goto error);
 786
 787         n_in2 = FN(MULTI(BASE),dim)(multi2, isl_dim_in);
 788
 789         multi1 = FN(MULTI(BASE),insert_dims)(multi1, isl_dim_in, in_pos, n_in2);
 790         multi2 = FN(MULTI(BASE),insert_dims)(multi2, isl_dim_in, n_in2,
 791                                                 n_in1 - in_pos);
 792         multi2 = FN(MULTI(BASE),insert_dims)(multi2, isl_dim_in, 0, in_pos);
 793
 794         return FN(MULTI(BASE),range_splice)(multi1, out_pos, multi2);
 795 error:
 796         FN(MULTI(BASE),free)(multi1);
 797         FN(MULTI(BASE),free)(multi2);
 798         return NULL;
 799 }
 800
 801 /* This function is currently only used from isl_aff.c
 802  */
 803 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
 804         __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
 805         __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
 806         __attribute__ ((unused));
 807
 808 /* Pairwise perform "fn" to the elements of "multi1" and "multi2" and
 809  * return the result.
 810  */
 811 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
 812         __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
 813         __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
 814 {
 815         int i;
 816         isl_ctx *ctx;
 817
 818         multi1 = FN(MULTI(BASE),cow)(multi1);
 819         if (!multi1 || !multi2)
 820                 goto error;
 821
 822         ctx = FN(MULTI(BASE),get_ctx)(multi1);
 823         if (!isl_space_is_equal(multi1->space, multi2->space))
 824                 isl_die(ctx, isl_error_invalid,
 825                         "spaces don't match", goto error);
 826
 827         for (i = 0; i < multi1->n; ++i) {
 828                 multi1->p[i] = fn(multi1->p[i], FN(EL,copy)(multi2->p[i]));
 829                 if (!multi1->p[i])
 830                         goto error;
 831         }
 832
 833         FN(MULTI(BASE),free)(multi2);
 834         return multi1;
 835 error:
 836         FN(MULTI(BASE),free)(multi1);
 837         FN(MULTI(BASE),free)(multi2);
 838         return NULL;
 839 }
 840
 841 /* Multiply the elements of "multi" by "v" and return the result.
 842  */
 843 __isl_give MULTI(BASE) *FN(MULTI(BASE),scale_val)(__isl_take MULTI(BASE) *multi,
 844         __isl_take isl_val *v)
 845 {
 846         int i;
 847
 848         if (!multi || !v)
 849                 goto error;
 850
 851         if (isl_val_is_one(v)) {
 852                 isl_val_free(v);
 853                 return multi;
 854         }
 855
 856         if (!isl_val_is_rat(v))
 857                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
 858                         "expecting rational factor", goto error);
 859
 860         multi = FN(MULTI(BASE),cow)(multi);
 861         if (!multi)
 862                 return NULL;
 863
 864         for (i = 0; i < multi->n; ++i) {
 865                 multi->p[i] = FN(EL,scale_val)(multi->p[i], isl_val_copy(v));
 866                 if (!multi->p[i])
 867                         goto error;
 868         }
 869
 870         isl_val_free(v);
 871         return multi;
 872 error:
 873         isl_val_free(v);
 874         return FN(MULTI(BASE),free)(multi);
 875 }
 876
 877 /* Multiply the elements of "multi" by the corresponding element of "mv"
 878  * and return the result.
 879  */
 880 __isl_give MULTI(BASE) *FN(MULTI(BASE),scale_multi_val)(
 881         __isl_take MULTI(BASE) *multi, __isl_take isl_multi_val *mv)
 882 {
 883         int i;
 884
 885         if (!multi || !mv)
 886                 goto error;
 887
 888         if (!isl_space_tuple_match(multi->space, isl_dim_out,
 889                                         mv->space, isl_dim_set))
 890                 isl_die(isl_multi_val_get_ctx(mv), isl_error_invalid,
 891                         "spaces don't match", goto error);
 892
 893         multi = FN(MULTI(BASE),cow)(multi);
 894         if (!multi)
 895                 return NULL;
 896
 897         for (i = 0; i < multi->n; ++i) {
 898                 isl_val *v;
 899
 900                 v = isl_multi_val_get_val(mv, i);
 901                 multi->p[i] = FN(EL,scale_val)(multi->p[i], v);
 902                 if (!multi->p[i])
 903                         goto error;
 904         }
 905
 906         isl_multi_val_free(mv);
 907         return multi;
 908 error:
 909         isl_multi_val_free(mv);
 910         return FN(MULTI(BASE),free)(multi);
 911 }