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 unsigned FN(MULTI(BASE),dim)(__isl_keep MULTI(BASE) *multi,
 155         enum isl_dim_type type)
 156 {
 157         return multi ? isl_space_dim(multi->space, type) : 0;
 158 }
 159
 160 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_dim_name)(
 161         __isl_take MULTI(BASE) *multi,
 162         enum isl_dim_type type, unsigned pos, const char *s)
 163 {
 164         int i;
 165
 166         multi = FN(MULTI(BASE),cow)(multi);
 167         if (!multi)
 168                 return NULL;
 169
 170         multi->space = isl_space_set_dim_name(multi->space, type, pos, s);
 171         if (!multi->space)
 172                 return FN(MULTI(BASE),free)(multi);
 173
 174         if (type == isl_dim_out)
 175                 return multi;
 176         for (i = 0; i < multi->n; ++i) {
 177                 multi->p[i] = FN(EL,set_dim_name)(multi->p[i], type, pos, s);
 178                 if (!multi->p[i])
 179                         return FN(MULTI(BASE),free)(multi);
 180         }
 181
 182         return multi;
 183 }
 184
 185 const char *FN(MULTI(BASE),get_tuple_name)(__isl_keep MULTI(BASE) *multi,
 186         enum isl_dim_type type)
 187 {
 188         return multi ? isl_space_get_tuple_name(multi->space, type) : NULL;
 189 }
 190
 191 __isl_give EL *FN(FN(MULTI(BASE),get),BASE)(__isl_keep MULTI(BASE) *multi,
 192         int pos)
 193 {
 194         isl_ctx *ctx;
 195
 196         if (!multi)
 197                 return NULL;
 198         ctx = FN(MULTI(BASE),get_ctx)(multi);
 199         if (pos < 0 || pos >= multi->n)
 200                 isl_die(ctx, isl_error_invalid,
 201                         "index out of bounds", return NULL);
 202         return FN(EL,copy)(multi->p[pos]);
 203 }
 204
 205 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),set),BASE)(
 206         __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
 207 {
 208         isl_space *multi_space = NULL;
 209         isl_space *el_space = NULL;
 210
 211         multi = FN(MULTI(BASE),cow)(multi);
 212         if (!multi || !el)
 213                 goto error;
 214
 215         multi_space = FN(MULTI(BASE),get_space)(multi);
 216         el_space = FN(EL,get_space)(el);
 217
 218         if (!isl_space_match(multi_space, isl_dim_param,
 219                             el_space, isl_dim_param))
 220                 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
 221                         "parameters don't match", goto error);
 222         if (!isl_space_tuple_match(multi_space, isl_dim_in,
 223                             el_space, isl_dim_in))
 224                 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
 225                         "domains don't match", goto error);
 226
 227         if (pos < 0 || pos >= multi->n)
 228                 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
 229                         "index out of bounds", goto error);
 230
 231         FN(EL,free)(multi->p[pos]);
 232         multi->p[pos] = el;
 233
 234         isl_space_free(multi_space);
 235         isl_space_free(el_space);
 236
 237         return multi;
 238 error:
 239         FN(MULTI(BASE),free)(multi);
 240         FN(EL,free)(el);
 241         isl_space_free(multi_space);
 242         isl_space_free(el_space);
 243         return NULL;
 244 }
 245
 246 /* Reset the space of "multi".  This function is called from isl_pw_templ.c
 247  * and doesn't know if the space of an element object is represented
 248  * directly or through its domain.  It therefore passes along both,
 249  * which we pass along to the element function since we don't how
 250  * that is represented either.
 251  */
 252 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space_and_domain)(
 253         __isl_take MULTI(BASE) *multi, __isl_take isl_space *space,
 254         __isl_take isl_space *domain)
 255 {
 256         int i;
 257
 258         multi = FN(MULTI(BASE),cow)(multi);
 259         if (!multi || !space || !domain)
 260                 goto error;
 261
 262         for (i = 0; i < multi->n; ++i) {
 263                 multi->p[i] = FN(EL,reset_domain_space)(multi->p[i],
 264                                  isl_space_copy(domain));
 265                 if (!multi->p[i])
 266                         goto error;
 267         }
 268         isl_space_free(domain);
 269         isl_space_free(multi->space);
 270         multi->space = space;
 271
 272         return multi;
 273 error:
 274         isl_space_free(domain);
 275         isl_space_free(space);
 276         FN(MULTI(BASE),free)(multi);
 277         return NULL;
 278 }
 279
 280 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_domain_space)(
 281         __isl_take MULTI(BASE) *multi, __isl_take isl_space *domain)
 282 {
 283         isl_space *space;
 284
 285         space = isl_space_extend_domain_with_range(isl_space_copy(domain),
 286                                                 isl_space_copy(multi->space));
 287         return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
 288 }
 289
 290 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space)(
 291         __isl_take MULTI(BASE) *multi, __isl_take isl_space *space)
 292 {
 293         isl_space *domain;
 294
 295         domain = isl_space_domain(isl_space_copy(space));
 296         return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
 297 }
 298
 299 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_tuple_id)(
 300         __isl_keep MULTI(BASE) *multi, enum isl_dim_type type,
 301         __isl_take isl_id *id)
 302 {
 303         isl_space *space;
 304
 305         multi = FN(MULTI(BASE),cow)(multi);
 306         if (!multi)
 307                 return isl_id_free(id);
 308
 309         space = FN(MULTI(BASE),get_space)(multi);
 310         space = isl_space_set_tuple_id(space, type, id);
 311
 312         return FN(MULTI(BASE),reset_space)(multi, space);
 313 }
 314
 315 __isl_give MULTI(BASE) *FN(MULTI(BASE),realign_domain)(
 316         __isl_take MULTI(BASE) *multi, __isl_take isl_reordering *exp)
 317 {
 318         int i;
 319
 320         multi = FN(MULTI(BASE),cow)(multi);
 321         if (!multi || !exp)
 322                 return NULL;
 323
 324         for (i = 0; i < multi->n; ++i) {
 325                 multi->p[i] = FN(EL,realign_domain)(multi->p[i],
 326                                                 isl_reordering_copy(exp));
 327                 if (!multi->p[i])
 328                         goto error;
 329         }
 330
 331         multi = FN(MULTI(BASE),reset_domain_space)(multi,
 332                                                     isl_space_copy(exp->dim));
 333
 334         isl_reordering_free(exp);
 335         return multi;
 336 error:
 337         isl_reordering_free(exp);
 338         FN(MULTI(BASE),free)(multi);
 339         return NULL;
 340 }
 341
 342 /* Align the parameters of "multi" to those of "model".
 343  */
 344 __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params)(
 345         __isl_take MULTI(BASE) *multi, __isl_take isl_space *model)
 346 {
 347         isl_ctx *ctx;
 348
 349         if (!multi || !model)
 350                 goto error;
 351
 352         ctx = isl_space_get_ctx(model);
 353         if (!isl_space_has_named_params(model))
 354                 isl_die(ctx, isl_error_invalid,
 355                         "model has unnamed parameters", goto error);
 356         if (!isl_space_has_named_params(multi->space))
 357                 isl_die(ctx, isl_error_invalid,
 358                         "input has unnamed parameters", goto error);
 359         if (!isl_space_match(multi->space, isl_dim_param,
 360                              model, isl_dim_param)) {
 361                 isl_reordering *exp;
 362
 363                 model = isl_space_params(model);
 364                 exp = isl_parameter_alignment_reordering(multi->space, model);
 365                 exp = isl_reordering_extend_space(exp,
 366                                     FN(MULTI(BASE),get_domain_space)(multi));
 367                 multi = FN(MULTI(BASE),realign_domain)(multi, exp);
 368         }
 369
 370         isl_space_free(model);
 371         return multi;
 372 error:
 373         isl_space_free(model);
 374         FN(MULTI(BASE),free)(multi);
 375         return NULL;
 376 }
 377
 378 static __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params_multi_set_and)(
 379         __isl_take MULTI(BASE) *multi, __isl_take isl_set *set,
 380         __isl_give MULTI(BASE) *(*fn)(__isl_take MULTI(BASE) *multi,
 381                                         __isl_take isl_set *set))
 382 {
 383         isl_ctx *ctx;
 384
 385         if (!multi || !set)
 386                 goto error;
 387         if (isl_space_match(multi->space, isl_dim_param,
 388                             set->dim, isl_dim_param))
 389                 return fn(multi, set);
 390         ctx = FN(MULTI(BASE),get_ctx)(multi);
 391         if (!isl_space_has_named_params(multi->space) ||
 392             !isl_space_has_named_params(set->dim))
 393                 isl_die(ctx, isl_error_invalid,
 394                         "unaligned unnamed parameters", goto error);
 395         multi = FN(MULTI(BASE),align_params)(multi, isl_set_get_space(set));
 396         set = isl_set_align_params(set, FN(MULTI(BASE),get_space)(multi));
 397         return fn(multi, set);
 398 error:
 399         FN(MULTI(BASE),free)(multi);
 400         isl_set_free(set);
 401         return NULL;
 402 }
 403
 404 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist_aligned)(
 405         __isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
 406 {
 407         int i;
 408
 409         if (!multi || !context)
 410                 goto error;
 411
 412         for (i = 0; i < multi->n; ++i) {
 413                 multi->p[i] = FN(EL,gist)(multi->p[i], isl_set_copy(context));
 414                 if (!multi->p[i])
 415                         goto error;
 416         }
 417
 418         isl_set_free(context);
 419         return multi;
 420 error:
 421         isl_set_free(context);
 422         FN(MULTI(BASE),free)(multi);
 423         return NULL;
 424 }
 425
 426 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist)(__isl_take MULTI(BASE) *multi,
 427         __isl_take isl_set *context)
 428 {
 429         return FN(MULTI(BASE),align_params_multi_set_and)(multi, context,
 430                                                 &FN(MULTI(BASE),gist_aligned));
 431 }
 432
 433 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist_params)(
 434         __isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
 435 {
 436         isl_space *space = FN(MULTI(BASE),get_domain_space)(multi);
 437         isl_set *dom_context = isl_set_universe(space);
 438         dom_context = isl_set_intersect_params(dom_context, context);
 439         return FN(MULTI(BASE),gist)(multi, dom_context);
 440 }
 441
 442 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))(
 443         __isl_take isl_space *space, __isl_take LIST(EL) *list)
 444 {
 445         int i;
 446         int n;
 447         isl_ctx *ctx;
 448         MULTI(BASE) *multi;
 449
 450         if (!space || !list)
 451                 goto error;
 452
 453         ctx = isl_space_get_ctx(space);
 454         n = FN(FN(LIST(EL),n),BASE)(list);
 455         if (n != isl_space_dim(space, isl_dim_out))
 456                 isl_die(ctx, isl_error_invalid,
 457                         "invalid number of elements in list", goto error);
 458
 459         multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
 460         for (i = 0; i < n; ++i) {
 461                 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
 462                                         FN(FN(LIST(EL),get),BASE)(list, i));
 463         }
 464
 465         isl_space_free(space);
 466         FN(LIST(EL),free)(list);
 467         return multi;
 468 error:
 469         isl_space_free(space);
 470         FN(LIST(EL),free)(list);
 471         return NULL;
 472 }
 473
 474 /* Create a multi expression in the given space that maps each
 475  * input dimension to the corresponding output dimension.
 476  */
 477 __isl_give MULTI(BASE) *FN(MULTI(BASE),identity)(__isl_take isl_space *space)
 478 {
 479         int i, n;
 480         isl_local_space *ls;
 481         MULTI(BASE) *multi;
 482
 483         if (!space)
 484                 return NULL;
 485
 486         if (isl_space_is_set(space))
 487                 isl_die(isl_space_get_ctx(space), isl_error_invalid,
 488                         "expecting map space", goto error);
 489
 490         n = isl_space_dim(space, isl_dim_out);
 491         if (n != isl_space_dim(space, isl_dim_in))
 492                 isl_die(isl_space_get_ctx(space), isl_error_invalid,
 493                         "number of input and output dimensions needs to be "
 494                         "the same", goto error);
 495
 496         multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
 497
 498         if (!n) {
 499                 isl_space_free(space);
 500                 return multi;
 501         }
 502
 503         space = isl_space_domain(space);
 504         ls = isl_local_space_from_space(space);
 505
 506         for (i = 0; i < n; ++i) {
 507                 EL *el;
 508                 el = FN(EL,var_on_domain)(isl_local_space_copy(ls),
 509                                                 isl_dim_set, i);
 510                 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i, el);
 511         }
 512
 513         isl_local_space_free(ls);
 514
 515         return multi;
 516 error:
 517         isl_space_free(space);
 518         return NULL;
 519 }
 520
 521 /* Construct a multi expression in the given space with value zero in
 522  * each of the output dimensions.
 523  */
 524 __isl_give MULTI(BASE) *FN(MULTI(BASE),zero)(__isl_take isl_space *space)
 525 {
 526         int n;
 527         MULTI(BASE) *multi;
 528
 529         if (!space)
 530                 return NULL;
 531
 532         n = isl_space_dim(space , isl_dim_out);
 533         multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
 534
 535         if (!n)
 536                 isl_space_free(space);
 537         else {
 538                 int i;
 539                 isl_local_space *ls;
 540                 EL *el;
 541
 542                 space = isl_space_domain(space);
 543                 ls = isl_local_space_from_space(space);
 544                 el = FN(EL,zero_on_domain)(ls);
 545
 546                 for (i = 0; i < n; ++i)
 547                         multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
 548                                                             FN(EL,copy)(el));
 549
 550                 FN(EL,free)(el);
 551         }
 552
 553         return multi;
 554 }
 555
 556 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),BASE)(__isl_take EL *el)
 557 {
 558         MULTI(BASE) *multi;
 559
 560         multi = FN(MULTI(BASE),alloc)(FN(EL,get_space)(el));
 561         multi = FN(FN(MULTI(BASE),set),BASE)(multi, 0, el);
 562
 563         return multi;
 564 }
 565
 566 __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)(
 567         __isl_take MULTI(BASE) *multi,
 568         enum isl_dim_type type, unsigned first, unsigned n)
 569 {
 570         int i;
 571         unsigned dim;
 572
 573         multi = FN(MULTI(BASE),cow)(multi);
 574         if (!multi)
 575                 return NULL;
 576
 577         dim = FN(MULTI(BASE),dim)(multi, type);
 578         if (first + n > dim || first + n < first)
 579                 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
 580                         "index out of bounds",
 581                         return FN(MULTI(BASE),cow)(multi));
 582
 583         multi->space = isl_space_drop_dims(multi->space, type, first, n);
 584         if (!multi->space)
 585                 return FN(MULTI(BASE),cow)(multi);
 586
 587         if (type == isl_dim_out) {
 588                 for (i = 0; i < n; ++i)
 589                         FN(EL,free)(multi->p[first + i]);
 590                 for (i = first; i + n < multi->n; ++i)
 591                         multi->p[i] = multi->p[i + n];
 592                 multi->n -= n;
 593
 594                 return multi;
 595         }
 596
 597         for (i = 0; i < multi->n; ++i) {
 598                 multi->p[i] = FN(EL,drop_dims)(multi->p[i], type, first, n);
 599                 if (!multi->p[i])
 600                         return FN(MULTI(BASE),cow)(multi);
 601         }
 602
 603         return multi;
 604 }
 605
 606 /* Given two MULTI(BASE)s A -> B and C -> D,
 607  * construct a MULTI(BASE) (A * C) -> (B, D).
 608  */
 609 __isl_give MULTI(BASE) *FN(MULTI(BASE),flat_range_product)(
 610         __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
 611 {
 612         int i, n1, n2;
 613         EL *el;
 614         isl_space *space;
 615         MULTI(BASE) *res;
 616
 617         if (!multi1 || !multi2)
 618                 goto error;
 619
 620         space = isl_space_range_product(FN(MULTI(BASE),get_space)(multi1),
 621                                         FN(MULTI(BASE),get_space)(multi2));
 622         space = isl_space_flatten_range(space);
 623         res = FN(MULTI(BASE),alloc)(space);
 624
 625         n1 = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
 626         n2 = FN(MULTI(BASE),dim)(multi2, isl_dim_out);
 627
 628         for (i = 0; i < n1; ++i) {
 629                 el = FN(FN(MULTI(BASE),get),BASE)(multi1, i);
 630                 res = FN(FN(MULTI(BASE),set),BASE)(res, i, el);
 631         }
 632
 633         for (i = 0; i < n2; ++i) {
 634                 el = FN(FN(MULTI(BASE),get),BASE)(multi2, i);
 635                 res = FN(FN(MULTI(BASE),set),BASE)(res, n1 + i, el);
 636         }
 637
 638         FN(MULTI(BASE),free)(multi1);
 639         FN(MULTI(BASE),free)(multi2);
 640         return res;
 641 error:
 642         FN(MULTI(BASE),free)(multi1);
 643         FN(MULTI(BASE),free)(multi2);
 644         return NULL;
 645 }