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