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         if (!multi || !context)
 433                 goto error;
 434
 435         for (i = 0; i < multi->n; ++i) {
 436                 multi->p[i] = FN(EL,gist)(multi->p[i], isl_set_copy(context));
 437                 if (!multi->p[i])
 438                         goto error;
 439         }
 440
 441         isl_set_free(context);
 442         return multi;
 443 error:
 444         isl_set_free(context);
 445         FN(MULTI(BASE),free)(multi);
 446         return NULL;
 447 }
 448
 449 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist)(__isl_take MULTI(BASE) *multi,
 450         __isl_take isl_set *context)
 451 {
 452         return FN(MULTI(BASE),align_params_multi_set_and)(multi, context,
 453                                                 &FN(MULTI(BASE),gist_aligned));
 454 }
 455
 456 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist_params)(
 457         __isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
 458 {
 459         isl_space *space = FN(MULTI(BASE),get_domain_space)(multi);
 460         isl_set *dom_context = isl_set_universe(space);
 461         dom_context = isl_set_intersect_params(dom_context, context);
 462         return FN(MULTI(BASE),gist)(multi, dom_context);
 463 }
 464 #endif
 465
 466 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))(
 467         __isl_take isl_space *space, __isl_take LIST(EL) *list)
 468 {
 469         int i;
 470         int n;
 471         isl_ctx *ctx;
 472         MULTI(BASE) *multi;
 473
 474         if (!space || !list)
 475                 goto error;
 476
 477         ctx = isl_space_get_ctx(space);
 478         n = FN(FN(LIST(EL),n),BASE)(list);
 479         if (n != isl_space_dim(space, isl_dim_out))
 480                 isl_die(ctx, isl_error_invalid,
 481                         "invalid number of elements in list", goto error);
 482
 483         multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
 484         for (i = 0; i < n; ++i) {
 485                 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
 486                                         FN(FN(LIST(EL),get),BASE)(list, i));
 487         }
 488
 489         isl_space_free(space);
 490         FN(LIST(EL),free)(list);
 491         return multi;
 492 error:
 493         isl_space_free(space);
 494         FN(LIST(EL),free)(list);
 495         return NULL;
 496 }
 497
 498 #ifndef NO_IDENTITY
 499 /* Create a multi expression in the given space that maps each
 500  * input dimension to the corresponding output dimension.
 501  */
 502 __isl_give MULTI(BASE) *FN(MULTI(BASE),identity)(__isl_take isl_space *space)
 503 {
 504         int i, n;
 505         isl_local_space *ls;
 506         MULTI(BASE) *multi;
 507
 508         if (!space)
 509                 return NULL;
 510
 511         if (isl_space_is_set(space))
 512                 isl_die(isl_space_get_ctx(space), isl_error_invalid,
 513                         "expecting map space", goto error);
 514
 515         n = isl_space_dim(space, isl_dim_out);
 516         if (n != isl_space_dim(space, isl_dim_in))
 517                 isl_die(isl_space_get_ctx(space), isl_error_invalid,
 518                         "number of input and output dimensions needs to be "
 519                         "the same", goto error);
 520
 521         multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
 522
 523         if (!n) {
 524                 isl_space_free(space);
 525                 return multi;
 526         }
 527
 528         space = isl_space_domain(space);
 529         ls = isl_local_space_from_space(space);
 530
 531         for (i = 0; i < n; ++i) {
 532                 EL *el;
 533                 el = FN(EL,var_on_domain)(isl_local_space_copy(ls),
 534                                                 isl_dim_set, i);
 535                 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i, el);
 536         }
 537
 538         isl_local_space_free(ls);
 539
 540         return multi;
 541 error:
 542         isl_space_free(space);
 543         return NULL;
 544 }
 545 #endif
 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 #ifndef NO_FROM_BASE
 583 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),BASE)(__isl_take EL *el)
 584 {
 585         MULTI(BASE) *multi;
 586
 587         multi = FN(MULTI(BASE),alloc)(FN(EL,get_space)(el));
 588         multi = FN(FN(MULTI(BASE),set),BASE)(multi, 0, el);
 589
 590         return multi;
 591 }
 592 #endif
 593
 594 __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)(
 595         __isl_take MULTI(BASE) *multi,
 596         enum isl_dim_type type, unsigned first, unsigned n)
 597 {
 598         int i;
 599         unsigned dim;
 600
 601         multi = FN(MULTI(BASE),cow)(multi);
 602         if (!multi)
 603                 return NULL;
 604
 605         dim = FN(MULTI(BASE),dim)(multi, type);
 606         if (first + n > dim || first + n < first)
 607                 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
 608                         "index out of bounds",
 609                         return FN(MULTI(BASE),cow)(multi));
 610
 611         multi->space = isl_space_drop_dims(multi->space, type, first, n);
 612         if (!multi->space)
 613                 return FN(MULTI(BASE),cow)(multi);
 614
 615         if (type == isl_dim_out) {
 616                 for (i = 0; i < n; ++i)
 617                         FN(EL,free)(multi->p[first + i]);
 618                 for (i = first; i + n < multi->n; ++i)
 619                         multi->p[i] = multi->p[i + n];
 620                 multi->n -= n;
 621
 622                 return multi;
 623         }
 624
 625         for (i = 0; i < multi->n; ++i) {
 626                 multi->p[i] = FN(EL,drop_dims)(multi->p[i], type, first, n);
 627                 if (!multi->p[i])
 628                         return FN(MULTI(BASE),cow)(multi);
 629         }
 630
 631         return multi;
 632 }
 633
 634 /* Given two MULTI(BASE)s A -> B and C -> D,
 635  * construct a MULTI(BASE) (A * C) -> (B, D).
 636  */
 637 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_product)(
 638         __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
 639 {
 640         int i, n1, n2;
 641         EL *el;
 642         isl_space *space;
 643         MULTI(BASE) *res;
 644
 645         if (!multi1 || !multi2)
 646                 goto error;
 647
 648         space = isl_space_range_product(FN(MULTI(BASE),get_space)(multi1),
 649                                         FN(MULTI(BASE),get_space)(multi2));
 650         res = FN(MULTI(BASE),alloc)(space);
 651
 652         n1 = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
 653         n2 = FN(MULTI(BASE),dim)(multi2, isl_dim_out);
 654
 655         for (i = 0; i < n1; ++i) {
 656                 el = FN(FN(MULTI(BASE),get),BASE)(multi1, i);
 657                 res = FN(FN(MULTI(BASE),set),BASE)(res, i, el);
 658         }
 659
 660         for (i = 0; i < n2; ++i) {
 661                 el = FN(FN(MULTI(BASE),get),BASE)(multi2, i);
 662                 res = FN(FN(MULTI(BASE),set),BASE)(res, n1 + i, el);
 663         }
 664
 665         FN(MULTI(BASE),free)(multi1);
 666         FN(MULTI(BASE),free)(multi2);
 667         return res;
 668 error:
 669         FN(MULTI(BASE),free)(multi1);
 670         FN(MULTI(BASE),free)(multi2);
 671         return NULL;
 672 }
 673
 674 __isl_give MULTI(BASE) *FN(MULTI(BASE),flatten_range)(
 675         __isl_take MULTI(BASE) *multi)
 676 {
 677         if (!multi)
 678                 return NULL;
 679
 680         if (!multi->space->nested[1])
 681                 return multi;
 682
 683         multi = FN(MULTI(BASE),cow)(multi);
 684         if (!multi)
 685                 return NULL;
 686
 687         multi->space = isl_space_flatten_range(multi->space);
 688         if (!multi->space)
 689                 return FN(MULTI(BASE),free)(multi);
 690
 691         return multi;
 692 }
 693
 694 /* Given two MULTI(BASE)s A -> B and C -> D,
 695  * construct a MULTI(BASE) (A * C) -> [B -> D].
 696  */
 697 __isl_give MULTI(BASE) *FN(MULTI(BASE),flat_range_product)(
 698         __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
 699 {
 700         MULTI(BASE) *multi;
 701
 702         multi = FN(MULTI(BASE),range_product)(multi1, multi2);
 703         multi = FN(MULTI(BASE),flatten_range)(multi);
 704         return multi;
 705 }
 706
 707 /* Given two multi expressions, "multi1"
 708  *
 709  *      [A] -> [B1 B2]
 710  *
 711  * where B2 starts at position "pos", and "multi2"
 712  *
 713  *      [A] -> [D]
 714  *
 715  * return the multi expression
 716  *
 717  *      [A] -> [B1 D B2]
 718  */
 719 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_splice)(
 720         __isl_take MULTI(BASE) *multi1, unsigned pos,
 721         __isl_take MULTI(BASE) *multi2)
 722 {
 723         MULTI(BASE) *res;
 724         unsigned dim;
 725
 726         if (!multi1 || !multi2)
 727                 goto error;
 728
 729         dim = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
 730         if (pos > dim)
 731                 isl_die(FN(MULTI(BASE),get_ctx)(multi1), isl_error_invalid,
 732                         "index out of bounds", goto error);
 733
 734         res = FN(MULTI(BASE),copy)(multi1);
 735         res = FN(MULTI(BASE),drop_dims)(res, isl_dim_out, pos, dim - pos);
 736         multi1 = FN(MULTI(BASE),drop_dims)(multi1, isl_dim_out, 0, pos);
 737
 738         res = FN(MULTI(BASE),flat_range_product)(res, multi2);
 739         res = FN(MULTI(BASE),flat_range_product)(res, multi1);
 740
 741         return res;
 742 error:
 743         FN(MULTI(BASE),free)(multi1);
 744         FN(MULTI(BASE),free)(multi2);
 745         return NULL;
 746 }
 747
 748 /* Given two multi expressions, "multi1"
 749  *
 750  *      [A1 A2] -> [B1 B2]
 751  *
 752  * where A2 starts at position "in_pos" and B2 starts at position "out_pos",
 753  * and "multi2"
 754  *
 755  *      [C] -> [D]
 756  *
 757  * return the multi expression
 758  *
 759  *      [A1 C A2] -> [B1 D B2]
 760  *
 761  * We first insert input dimensions to obtain
 762  *
 763  *      [A1 C A2] -> [B1 B2]
 764  *
 765  * and
 766  *
 767  *      [A1 C A2] -> [D]
 768  *
 769  * and then apply range_splice.
 770  */
 771 __isl_give MULTI(BASE) *FN(MULTI(BASE),splice)(
 772         __isl_take MULTI(BASE) *multi1, unsigned in_pos, unsigned out_pos,
 773         __isl_take MULTI(BASE) *multi2)
 774 {
 775         unsigned n_in1;
 776         unsigned n_in2;
 777
 778         if (!multi1 || !multi2)
 779                 goto error;
 780
 781         n_in1 = FN(MULTI(BASE),dim)(multi1, isl_dim_in);
 782         if (in_pos > n_in1)
 783                 isl_die(FN(MULTI(BASE),get_ctx)(multi1), isl_error_invalid,
 784                         "index out of bounds", goto error);
 785
 786         n_in2 = FN(MULTI(BASE),dim)(multi2, isl_dim_in);
 787
 788         multi1 = FN(MULTI(BASE),insert_dims)(multi1, isl_dim_in, in_pos, n_in2);
 789         multi2 = FN(MULTI(BASE),insert_dims)(multi2, isl_dim_in, n_in2,
 790                                                 n_in1 - in_pos);
 791         multi2 = FN(MULTI(BASE),insert_dims)(multi2, isl_dim_in, 0, in_pos);
 792
 793         return FN(MULTI(BASE),range_splice)(multi1, out_pos, multi2);
 794 error:
 795         FN(MULTI(BASE),free)(multi1);
 796         FN(MULTI(BASE),free)(multi2);
 797         return NULL;
 798 }
 799
 800 /* This function is currently only used from isl_aff.c
 801  */
 802 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
 803         __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
 804         __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
 805         __attribute__ ((unused));
 806
 807 /* Pairwise perform "fn" to the elements of "multi1" and "multi2" and
 808  * return the result.
 809  */
 810 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
 811         __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
 812         __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
 813 {
 814         int i;
 815         isl_ctx *ctx;
 816
 817         multi1 = FN(MULTI(BASE),cow)(multi1);
 818         if (!multi1 || !multi2)
 819                 goto error;
 820
 821         ctx = FN(MULTI(BASE),get_ctx)(multi1);
 822         if (!isl_space_is_equal(multi1->space, multi2->space))
 823                 isl_die(ctx, isl_error_invalid,
 824                         "spaces don't match", goto error);
 825
 826         for (i = 0; i < multi1->n; ++i) {
 827                 multi1->p[i] = fn(multi1->p[i], FN(EL,copy)(multi2->p[i]));
 828                 if (!multi1->p[i])
 829                         goto error;
 830         }
 831
 832         FN(MULTI(BASE),free)(multi2);
 833         return multi1;
 834 error:
 835         FN(MULTI(BASE),free)(multi1);
 836         FN(MULTI(BASE),free)(multi2);
 837         return NULL;
 838 }