isl_dim.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  * Copyright 2010      INRIA Saclay
   4  *
   5  * Use of this software is governed by the GNU LGPLv2.1 license
   6  *
   7  * Written by Sven Verdoolaege, K.U.Leuven, Departement
   8  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
   9  * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
  10  * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
  11  */
  12
  13 #include <stdlib.h>
  14 #include <isl_dim_private.h>
  15 #include "isl_name.h"
  16 #include <isl_reordering.h>
  17
  18 isl_ctx *isl_dim_get_ctx(__isl_keep isl_dim *dim)
  19 {
  20         return dim ? dim->ctx : NULL;
  21 }
  22
  23 struct isl_dim *isl_dim_alloc(struct isl_ctx *ctx,
  24                         unsigned nparam, unsigned n_in, unsigned n_out)
  25 {
  26         struct isl_dim *dim;
  27
  28         dim = isl_alloc_type(ctx, struct isl_dim);
  29         if (!dim)
  30                 return NULL;
  31
  32         dim->ctx = ctx;
  33         isl_ctx_ref(ctx);
  34         dim->ref = 1;
  35         dim->nparam = nparam;
  36         dim->n_in = n_in;
  37         dim->n_out = n_out;
  38
  39         dim->tuple_name[0] = NULL;
  40         dim->tuple_name[1] = NULL;
  41
  42         dim->nested[0] = NULL;
  43         dim->nested[1] = NULL;
  44
  45         dim->n_name = 0;
  46         dim->names = NULL;
  47
  48         return dim;
  49 }
  50
  51 struct isl_dim *isl_dim_set_alloc(struct isl_ctx *ctx,
  52                         unsigned nparam, unsigned dim)
  53 {
  54         return isl_dim_alloc(ctx, nparam, 0, dim);
  55 }
  56
  57 static unsigned global_pos(struct isl_dim *dim,
  58                                  enum isl_dim_type type, unsigned pos)
  59 {
  60         struct isl_ctx *ctx = dim->ctx;
  61
  62         switch (type) {
  63         case isl_dim_param:
  64                 isl_assert(ctx, pos < dim->nparam, return isl_dim_total(dim));
  65                 return pos;
  66         case isl_dim_in:
  67                 isl_assert(ctx, pos < dim->n_in, return isl_dim_total(dim));
  68                 return pos + dim->nparam;
  69         case isl_dim_out:
  70                 isl_assert(ctx, pos < dim->n_out, return isl_dim_total(dim));
  71                 return pos + dim->nparam + dim->n_in;
  72         default:
  73                 isl_assert(ctx, 0, return isl_dim_total(dim));
  74         }
  75         return isl_dim_total(dim);
  76 }
  77
  78 /* Extend length of names array to the total number of dimensions.
  79  */
  80 static __isl_give isl_dim *extend_names(__isl_take isl_dim *dim)
  81 {
  82         struct isl_name **names;
  83         int i;
  84
  85         if (isl_dim_total(dim) <= dim->n_name)
  86                 return dim;
  87
  88         if (!dim->names) {
  89                 dim->names = isl_calloc_array(dim->ctx,
  90                                 struct isl_name *, isl_dim_total(dim));
  91                 if (!dim->names)
  92                         goto error;
  93         } else {
  94                 names = isl_realloc_array(dim->ctx, dim->names,
  95                                 struct isl_name *, isl_dim_total(dim));
  96                 if (!names)
  97                         goto error;
  98                 dim->names = names;
  99                 for (i = dim->n_name; i < isl_dim_total(dim); ++i)
 100                         dim->names[i] = NULL;
 101         }
 102
 103         dim->n_name = isl_dim_total(dim);
 104
 105         return dim;
 106 error:
 107         isl_dim_free(dim);
 108         return NULL;
 109 }
 110
 111 static struct isl_dim *set_name(struct isl_dim *dim,
 112                                  enum isl_dim_type type, unsigned pos,
 113                                  struct isl_name *name)
 114 {
 115         struct isl_ctx *ctx = dim->ctx;
 116         dim = isl_dim_cow(dim);
 117
 118         if (!dim)
 119                 goto error;
 120
 121         pos = global_pos(dim, type, pos);
 122         if (pos == isl_dim_total(dim))
 123                 goto error;
 124
 125         if (pos >= dim->n_name) {
 126                 if (!name)
 127                         return dim;
 128                 dim = extend_names(dim);
 129                 if (!dim)
 130                         goto error;
 131         }
 132
 133         dim->names[pos] = name;
 134
 135         return dim;
 136 error:
 137         isl_name_free(ctx, name);
 138         isl_dim_free(dim);
 139         return NULL;
 140 }
 141
 142 static struct isl_name *get_name(struct isl_dim *dim,
 143                                  enum isl_dim_type type, unsigned pos)
 144 {
 145         if (!dim)
 146                 return NULL;
 147
 148         pos = global_pos(dim, type, pos);
 149         if (pos == isl_dim_total(dim))
 150                 return NULL;
 151         if (pos >= dim->n_name)
 152                 return NULL;
 153         return dim->names[pos];
 154 }
 155
 156 static unsigned offset(struct isl_dim *dim, enum isl_dim_type type)
 157 {
 158         switch (type) {
 159         case isl_dim_param:     return 0;
 160         case isl_dim_in:        return dim->nparam;
 161         case isl_dim_out:       return dim->nparam + dim->n_in;
 162         default:                return 0;
 163         }
 164 }
 165
 166 static unsigned n(struct isl_dim *dim, enum isl_dim_type type)
 167 {
 168         switch (type) {
 169         case isl_dim_param:     return dim->nparam;
 170         case isl_dim_in:        return dim->n_in;
 171         case isl_dim_out:       return dim->n_out;
 172         case isl_dim_all:       return dim->nparam + dim->n_in + dim->n_out;
 173         default:                return 0;
 174         }
 175 }
 176
 177 unsigned isl_dim_size(struct isl_dim *dim, enum isl_dim_type type)
 178 {
 179         if (!dim)
 180                 return 0;
 181         return n(dim, type);
 182 }
 183
 184 unsigned isl_dim_offset(__isl_keep isl_dim *dim, enum isl_dim_type type)
 185 {
 186         if (!dim)
 187                 return 0;
 188         return offset(dim, type);
 189 }
 190
 191 static struct isl_dim *copy_names(struct isl_dim *dst,
 192         enum isl_dim_type dst_type, unsigned offset, struct isl_dim *src,
 193         enum isl_dim_type src_type)
 194 {
 195         int i;
 196         struct isl_name *name;
 197
 198         if (!dst)
 199                 return NULL;
 200
 201         for (i = 0; i < n(src, src_type); ++i) {
 202                 name = get_name(src, src_type, i);
 203                 if (!name)
 204                         continue;
 205                 dst = set_name(dst, dst_type, offset + i,
 206                                         isl_name_copy(dst->ctx, name));
 207                 if (!dst)
 208                         return NULL;
 209         }
 210         return dst;
 211 }
 212
 213 struct isl_dim *isl_dim_dup(struct isl_dim *dim)
 214 {
 215         struct isl_dim *dup;
 216         if (!dim)
 217                 return NULL;
 218         dup = isl_dim_alloc(dim->ctx, dim->nparam, dim->n_in, dim->n_out);
 219         if (dim->tuple_name[0] &&
 220             !(dup->tuple_name[0] = isl_name_copy(dim->ctx, dim->tuple_name[0])))
 221                 goto error;
 222         if (dim->tuple_name[1] &&
 223             !(dup->tuple_name[1] = isl_name_copy(dim->ctx, dim->tuple_name[1])))
 224                 goto error;
 225         if (dim->nested[0] && !(dup->nested[0] = isl_dim_copy(dim->nested[0])))
 226                 goto error;
 227         if (dim->nested[1] && !(dup->nested[1] = isl_dim_copy(dim->nested[1])))
 228                 goto error;
 229         if (!dim->names)
 230                 return dup;
 231         dup = copy_names(dup, isl_dim_param, 0, dim, isl_dim_param);
 232         dup = copy_names(dup, isl_dim_in, 0, dim, isl_dim_in);
 233         dup = copy_names(dup, isl_dim_out, 0, dim, isl_dim_out);
 234         return dup;
 235 error:
 236         isl_dim_free(dup);
 237         return NULL;
 238 }
 239
 240 struct isl_dim *isl_dim_cow(struct isl_dim *dim)
 241 {
 242         if (!dim)
 243                 return NULL;
 244
 245         if (dim->ref == 1)
 246                 return dim;
 247         dim->ref--;
 248         return isl_dim_dup(dim);
 249 }
 250
 251 struct isl_dim *isl_dim_copy(struct isl_dim *dim)
 252 {
 253         if (!dim)
 254                 return NULL;
 255
 256         dim->ref++;
 257         return dim;
 258 }
 259
 260 void isl_dim_free(struct isl_dim *dim)
 261 {
 262         int i;
 263
 264         if (!dim)
 265                 return;
 266
 267         if (--dim->ref > 0)
 268                 return;
 269
 270         isl_name_free(dim->ctx, dim->tuple_name[0]);
 271         isl_name_free(dim->ctx, dim->tuple_name[1]);
 272
 273         isl_dim_free(dim->nested[0]);
 274         isl_dim_free(dim->nested[1]);
 275
 276         for (i = 0; i < dim->n_name; ++i)
 277                 isl_name_free(dim->ctx, dim->names[i]);
 278         free(dim->names);
 279         isl_ctx_deref(dim->ctx);
 280
 281         free(dim);
 282 }
 283
 284 static int name_ok(isl_ctx *ctx, const char *s)
 285 {
 286         char *p;
 287         long dummy;
 288
 289         dummy = strtol(s, &p, 0);
 290         if (p != s)
 291                 isl_die(ctx, isl_error_invalid, "name looks like a number",
 292                         return 0);
 293
 294         return 1;
 295 }
 296
 297 __isl_give isl_dim *isl_dim_set_tuple_name(__isl_take isl_dim *dim,
 298         enum isl_dim_type type, const char *s)
 299 {
 300         struct isl_name *name;
 301
 302         dim = isl_dim_cow(dim);
 303         if (!dim)
 304                 return NULL;
 305         if (type != isl_dim_in && type != isl_dim_out)
 306                 isl_die(dim->ctx, isl_error_invalid,
 307                         "only input, output and set tuples can have names",
 308                         goto error);
 309         if (!s) {
 310                 name = NULL;
 311         } else {
 312                 if (!name_ok(dim->ctx, s))
 313                         goto error;
 314                 name = isl_name_get(dim->ctx, s);
 315                 if (!name)
 316                         goto error;
 317         }
 318
 319         isl_name_free(dim->ctx, dim->tuple_name[type - isl_dim_in]);
 320         dim->tuple_name[type - isl_dim_in] = name;
 321
 322         return dim;
 323 error:
 324         isl_dim_free(dim);
 325         return NULL;
 326 }
 327
 328 const char *isl_dim_get_tuple_name(__isl_keep isl_dim *dim,
 329          enum isl_dim_type type)
 330 {
 331         struct isl_name *name;
 332         if (!dim)
 333                 return NULL;
 334         if (type != isl_dim_in && type != isl_dim_out)
 335                 return NULL;
 336         name = dim->tuple_name[type - isl_dim_in];
 337         return name ? name->name : NULL;
 338 }
 339
 340 struct isl_dim *isl_dim_set_name(struct isl_dim *dim,
 341                                  enum isl_dim_type type, unsigned pos,
 342                                  const char *s)
 343 {
 344         struct isl_name *name;
 345
 346         if (!dim)
 347                 return NULL;
 348         if (!name_ok(dim->ctx, s))
 349                 goto error;
 350         isl_name_free(dim->ctx, get_name(dim, type, pos));
 351         name = isl_name_get(dim->ctx, s);
 352         if (!name)
 353                 goto error;
 354         return set_name(dim, type, pos, name);
 355 error:
 356         isl_dim_free(dim);
 357         return NULL;
 358 }
 359
 360 const char *isl_dim_get_name(struct isl_dim *dim,
 361                                  enum isl_dim_type type, unsigned pos)
 362 {
 363         struct isl_name *name = get_name(dim, type, pos);
 364         return name ? name->name : NULL;
 365 }
 366
 367 static struct isl_name *tuple_name(__isl_keep isl_dim *dim,
 368         enum isl_dim_type type)
 369 {
 370         if (!dim)
 371                 return NULL;
 372         if (type == isl_dim_in)
 373                 return dim->tuple_name[0];
 374         if (type == isl_dim_out)
 375                 return dim->tuple_name[1];
 376         return NULL;
 377 }
 378
 379 static __isl_keep isl_dim *nested(__isl_keep isl_dim *dim,
 380         enum isl_dim_type type)
 381 {
 382         if (!dim)
 383                 return NULL;
 384         if (type == isl_dim_in)
 385                 return dim->nested[0];
 386         if (type == isl_dim_out)
 387                 return dim->nested[1];
 388         return NULL;
 389 }
 390
 391 int isl_dim_tuple_match(__isl_keep isl_dim *dim1, enum isl_dim_type dim1_type,
 392                         __isl_keep isl_dim *dim2, enum isl_dim_type dim2_type)
 393 {
 394         struct isl_name *name1, *name2;
 395         isl_dim *nested1, *nested2;
 396
 397         if (!dim1 || !dim2)
 398                 return -1;
 399
 400         if (n(dim1, dim1_type) != n(dim2, dim2_type))
 401                 return 0;
 402         name1 = tuple_name(dim1, dim1_type);
 403         name2 = tuple_name(dim2, dim2_type);
 404         if (!name1 ^ !name2)
 405                 return 0;
 406         if (name1 && name1->name != name2->name)
 407                 return 0;
 408         nested1 = nested(dim1, dim1_type);
 409         nested2 = nested(dim2, dim2_type);
 410         if (!nested1 ^ !nested2)
 411                 return 0;
 412         if (nested1 && !isl_dim_equal(nested1, nested2))
 413                 return 0;
 414         return 1;
 415 }
 416
 417 static int match(struct isl_dim *dim1, enum isl_dim_type dim1_type,
 418                 struct isl_dim *dim2, enum isl_dim_type dim2_type)
 419 {
 420         int i;
 421
 422         if (!isl_dim_tuple_match(dim1, dim1_type, dim2, dim2_type))
 423                 return 0;
 424
 425         if (!dim1->names && !dim2->names)
 426                 return 1;
 427
 428         for (i = 0; i < n(dim1, dim1_type); ++i) {
 429                 if (get_name(dim1, dim1_type, i) !=
 430                     get_name(dim2, dim2_type, i))
 431                         return 0;
 432         }
 433         return 1;
 434 }
 435
 436 int isl_dim_match(struct isl_dim *dim1, enum isl_dim_type dim1_type,
 437                 struct isl_dim *dim2, enum isl_dim_type dim2_type)
 438 {
 439         return match(dim1, dim1_type, dim2, dim2_type);
 440 }
 441
 442 static void get_names(struct isl_dim *dim, enum isl_dim_type type,
 443         unsigned first, unsigned n, struct isl_name **names)
 444 {
 445         int i;
 446
 447         for (i = 0; i < n ; ++i)
 448                 names[i] = get_name(dim, type, first+i);
 449 }
 450
 451 struct isl_dim *isl_dim_extend(struct isl_dim *dim,
 452                         unsigned nparam, unsigned n_in, unsigned n_out)
 453 {
 454         struct isl_name **names = NULL;
 455
 456         if (!dim)
 457                 return NULL;
 458         if (dim->nparam == nparam && dim->n_in == n_in && dim->n_out == n_out)
 459                 return dim;
 460
 461         isl_assert(dim->ctx, dim->nparam <= nparam, goto error);
 462         isl_assert(dim->ctx, dim->n_in <= n_in, goto error);
 463         isl_assert(dim->ctx, dim->n_out <= n_out, goto error);
 464
 465         dim = isl_dim_cow(dim);
 466
 467         if (dim->names) {
 468                 names = isl_calloc_array(dim->ctx, struct isl_name *,
 469                                          nparam + n_in + n_out);
 470                 if (!names)
 471                         goto error;
 472                 get_names(dim, isl_dim_param, 0, dim->nparam, names);
 473                 get_names(dim, isl_dim_in, 0, dim->n_in, names + nparam);
 474                 get_names(dim, isl_dim_out, 0, dim->n_out,
 475                                 names + nparam + n_in);
 476                 free(dim->names);
 477                 dim->names = names;
 478                 dim->n_name = nparam + n_in + n_out;
 479         }
 480         dim->nparam = nparam;
 481         dim->n_in = n_in;
 482         dim->n_out = n_out;
 483
 484         return dim;
 485 error:
 486         free(names);
 487         isl_dim_free(dim);
 488         return NULL;
 489 }
 490
 491 struct isl_dim *isl_dim_add(struct isl_dim *dim, enum isl_dim_type type,
 492         unsigned n)
 493 {
 494         if (!dim)
 495                 return NULL;
 496         dim = isl_dim_reset(dim, type);
 497         switch (type) {
 498         case isl_dim_param:
 499                 dim = isl_dim_extend(dim,
 500                                         dim->nparam + n, dim->n_in, dim->n_out);
 501                 if (dim && dim->nested[0] &&
 502                     !(dim->nested[0] = isl_dim_add(dim->nested[0],
 503                                                     isl_dim_param, n)))
 504                         goto error;
 505                 if (dim && dim->nested[1] &&
 506                     !(dim->nested[1] = isl_dim_add(dim->nested[1],
 507                                                     isl_dim_param, n)))
 508                         goto error;
 509                 return dim;
 510         case isl_dim_in:
 511                 return isl_dim_extend(dim,
 512                                         dim->nparam, dim->n_in + n, dim->n_out);
 513         case isl_dim_out:
 514                 return isl_dim_extend(dim,
 515                                         dim->nparam, dim->n_in, dim->n_out + n);
 516         default:
 517                 isl_die(dim->ctx, isl_error_invalid,
 518                         "cannot add dimensions of specified type", goto error);
 519         }
 520 error:
 521         isl_dim_free(dim);
 522         return NULL;
 523 }
 524
 525 static int valid_dim_type(enum isl_dim_type type)
 526 {
 527         switch (type) {
 528         case isl_dim_param:
 529         case isl_dim_in:
 530         case isl_dim_out:
 531                 return 1;
 532         default:
 533                 return 0;
 534         }
 535 }
 536
 537 __isl_give isl_dim *isl_dim_insert(__isl_take isl_dim *dim,
 538         enum isl_dim_type type, unsigned pos, unsigned n)
 539 {
 540         struct isl_name **names = NULL;
 541
 542         if (!dim)
 543                 return NULL;
 544         if (n == 0)
 545                 return isl_dim_reset(dim, type);
 546
 547         if (!valid_dim_type(type))
 548                 isl_die(dim->ctx, isl_error_invalid,
 549                         "cannot insert dimensions of specified type",
 550                         goto error);
 551
 552         isl_assert(dim->ctx, pos <= isl_dim_size(dim, type), goto error);
 553
 554         dim = isl_dim_cow(dim);
 555         if (!dim)
 556                 return NULL;
 557
 558         if (dim->names) {
 559                 enum isl_dim_type t;
 560                 int off;
 561                 int s[3];
 562                 int *size = s - isl_dim_param;
 563                 names = isl_calloc_array(dim->ctx, struct isl_name *,
 564                                      dim->nparam + dim->n_in + dim->n_out + n);
 565                 if (!names)
 566                         goto error;
 567                 off = 0;
 568                 size[isl_dim_param] = dim->nparam;
 569                 size[isl_dim_in] = dim->n_in;
 570                 size[isl_dim_out] = dim->n_out;
 571                 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
 572                         if (t != type) {
 573                                 get_names(dim, t, 0, size[t], names + off);
 574                                 off += size[t];
 575                         } else {
 576                                 get_names(dim, t, 0, pos, names + off);
 577                                 off += pos + n;
 578                                 get_names(dim, t, pos, size[t]-pos, names+off);
 579                                 off += size[t] - pos;
 580                         }
 581                 }
 582                 free(dim->names);
 583                 dim->names = names;
 584                 dim->n_name = dim->nparam + dim->n_in + dim->n_out + n;
 585         }
 586         switch (type) {
 587         case isl_dim_param:     dim->nparam += n; break;
 588         case isl_dim_in:        dim->n_in += n; break;
 589         case isl_dim_out:       dim->n_out += n; break;
 590         default:                ;
 591         }
 592         dim = isl_dim_reset(dim, type);
 593
 594         return dim;
 595 error:
 596         isl_dim_free(dim);
 597         return NULL;
 598 }
 599
 600 __isl_give isl_dim *isl_dim_move(__isl_take isl_dim *dim,
 601         enum isl_dim_type dst_type, unsigned dst_pos,
 602         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
 603 {
 604         int i;
 605
 606         if (!dim)
 607                 return NULL;
 608         if (n == 0)
 609                 return dim;
 610
 611         isl_assert(dim->ctx, src_pos + n <= isl_dim_size(dim, src_type),
 612                 goto error);
 613
 614         if (dst_type == src_type && dst_pos == src_pos)
 615                 return dim;
 616
 617         isl_assert(dim->ctx, dst_type != src_type, goto error);
 618
 619         dim = isl_dim_reset(dim, src_type);
 620         dim = isl_dim_reset(dim, dst_type);
 621
 622         dim = isl_dim_cow(dim);
 623         if (!dim)
 624                 return NULL;
 625
 626         if (dim->names) {
 627                 struct isl_name **names;
 628                 enum isl_dim_type t;
 629                 int off;
 630                 int s[3];
 631                 int *size = s - isl_dim_param;
 632                 names = isl_calloc_array(dim->ctx, struct isl_name *,
 633                                          dim->nparam + dim->n_in + dim->n_out);
 634                 if (!names)
 635                         goto error;
 636                 off = 0;
 637                 size[isl_dim_param] = dim->nparam;
 638                 size[isl_dim_in] = dim->n_in;
 639                 size[isl_dim_out] = dim->n_out;
 640                 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
 641                         if (t == dst_type) {
 642                                 get_names(dim, t, 0, dst_pos, names + off);
 643                                 off += dst_pos;
 644                                 get_names(dim, src_type, src_pos, n, names+off);
 645                                 off += n;
 646                                 get_names(dim, t, dst_pos, size[t] - dst_pos,
 647                                                 names + off);
 648                                 off += size[t] - dst_pos;
 649                         } else if (t == src_type) {
 650                                 get_names(dim, t, 0, src_pos, names + off);
 651                                 off += src_pos;
 652                                 get_names(dim, t, src_pos + n,
 653                                             size[t] - src_pos - n, names + off);
 654                                 off += size[t] - src_pos - n;
 655                         } else {
 656                                 get_names(dim, t, 0, size[t], names + off);
 657                                 off += size[t];
 658                         }
 659                 }
 660                 free(dim->names);
 661                 dim->names = names;
 662                 dim->n_name = dim->nparam + dim->n_in + dim->n_out;
 663         }
 664
 665         switch (dst_type) {
 666         case isl_dim_param:     dim->nparam += n; break;
 667         case isl_dim_in:        dim->n_in += n; break;
 668         case isl_dim_out:       dim->n_out += n; break;
 669         default:                ;
 670         }
 671
 672         switch (src_type) {
 673         case isl_dim_param:     dim->nparam -= n; break;
 674         case isl_dim_in:        dim->n_in -= n; break;
 675         case isl_dim_out:       dim->n_out -= n; break;
 676         default:                ;
 677         }
 678
 679         if (dst_type != isl_dim_param && src_type != isl_dim_param)
 680                 return dim;
 681
 682         for (i = 0; i < 2; ++i) {
 683                 if (!dim->nested[i])
 684                         continue;
 685                 dim->nested[i] = isl_dim_replace(dim->nested[i],
 686                                                  isl_dim_param, dim);
 687                 if (!dim->nested[i])
 688                         goto error;
 689         }
 690
 691         return dim;
 692 error:
 693         isl_dim_free(dim);
 694         return NULL;
 695 }
 696
 697 struct isl_dim *isl_dim_join(struct isl_dim *left, struct isl_dim *right)
 698 {
 699         struct isl_dim *dim;
 700
 701         if (!left || !right)
 702                 goto error;
 703
 704         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
 705                         goto error);
 706         isl_assert(left->ctx,
 707                 isl_dim_tuple_match(left, isl_dim_out, right, isl_dim_in),
 708                 goto error);
 709
 710         dim = isl_dim_alloc(left->ctx, left->nparam, left->n_in, right->n_out);
 711         if (!dim)
 712                 goto error;
 713
 714         dim = copy_names(dim, isl_dim_param, 0, left, isl_dim_param);
 715         dim = copy_names(dim, isl_dim_in, 0, left, isl_dim_in);
 716         dim = copy_names(dim, isl_dim_out, 0, right, isl_dim_out);
 717
 718         if (dim && left->tuple_name[0] &&
 719             !(dim->tuple_name[0] = isl_name_copy(dim->ctx, left->tuple_name[0])))
 720                 goto error;
 721         if (dim && right->tuple_name[1] &&
 722             !(dim->tuple_name[1] = isl_name_copy(dim->ctx, right->tuple_name[1])))
 723                 goto error;
 724         if (dim && left->nested[0] &&
 725             !(dim->nested[0] = isl_dim_copy(left->nested[0])))
 726                 goto error;
 727         if (dim && right->nested[1] &&
 728             !(dim->nested[1] = isl_dim_copy(right->nested[1])))
 729                 goto error;
 730
 731         isl_dim_free(left);
 732         isl_dim_free(right);
 733
 734         return dim;
 735 error:
 736         isl_dim_free(left);
 737         isl_dim_free(right);
 738         return NULL;
 739 }
 740
 741 struct isl_dim *isl_dim_product(struct isl_dim *left, struct isl_dim *right)
 742 {
 743         isl_dim *dom1, *dom2, *nest1, *nest2;
 744
 745         if (!left || !right)
 746                 goto error;
 747
 748         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
 749                         goto error);
 750
 751         dom1 = isl_dim_domain(isl_dim_copy(left));
 752         dom2 = isl_dim_domain(isl_dim_copy(right));
 753         nest1 = isl_dim_wrap(isl_dim_join(isl_dim_reverse(dom1), dom2));
 754
 755         dom1 = isl_dim_range(left);
 756         dom2 = isl_dim_range(right);
 757         nest2 = isl_dim_wrap(isl_dim_join(isl_dim_reverse(dom1), dom2));
 758
 759         return isl_dim_join(isl_dim_reverse(nest1), nest2);
 760 error:
 761         isl_dim_free(left);
 762         isl_dim_free(right);
 763         return NULL;
 764 }
 765
 766 __isl_give isl_dim *isl_dim_range_product(__isl_take isl_dim *left,
 767         __isl_take isl_dim *right)
 768 {
 769         isl_dim *dom, *ran1, *ran2, *nest;
 770
 771         if (!left || !right)
 772                 goto error;
 773
 774         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
 775                         goto error);
 776         if (!isl_dim_tuple_match(left, isl_dim_in, right, isl_dim_in))
 777                 isl_die(left->ctx, isl_error_invalid,
 778                         "domains need to match", goto error);
 779
 780         dom = isl_dim_domain(isl_dim_copy(left));
 781
 782         ran1 = isl_dim_range(left);
 783         ran2 = isl_dim_range(right);
 784         nest = isl_dim_wrap(isl_dim_join(isl_dim_reverse(ran1), ran2));
 785
 786         return isl_dim_join(isl_dim_reverse(dom), nest);
 787 error:
 788         isl_dim_free(left);
 789         isl_dim_free(right);
 790         return NULL;
 791 }
 792
 793 __isl_give isl_dim *isl_dim_map_from_set(__isl_take isl_dim *dim)
 794 {
 795         struct isl_name **names = NULL;
 796
 797         if (!dim)
 798                 return NULL;
 799         isl_assert(dim->ctx, dim->n_in == 0, goto error);
 800         if (dim->n_out == 0 && !isl_dim_is_named_or_nested(dim, isl_dim_out))
 801                 return dim;
 802         dim = isl_dim_cow(dim);
 803         if (!dim)
 804                 return NULL;
 805         if (dim->names) {
 806                 names = isl_calloc_array(dim->ctx, struct isl_name *,
 807                                         dim->nparam + dim->n_out + dim->n_out);
 808                 if (!names)
 809                         goto error;
 810                 get_names(dim, isl_dim_param, 0, dim->nparam, names);
 811                 get_names(dim, isl_dim_out, 0, dim->n_out, names + dim->nparam);
 812         }
 813         dim->n_in = dim->n_out;
 814         if (names) {
 815                 free(dim->names);
 816                 dim->names = names;
 817                 dim->n_name = dim->nparam + dim->n_out + dim->n_out;
 818                 dim = copy_names(dim, isl_dim_out, 0, dim, isl_dim_in);
 819         }
 820         isl_name_free(dim->ctx, dim->tuple_name[0]);
 821         dim->tuple_name[0] = isl_name_copy(dim->ctx, dim->tuple_name[1]);
 822         isl_dim_free(dim->nested[0]);
 823         dim->nested[0] = isl_dim_copy(dim->nested[1]);
 824         return dim;
 825 error:
 826         isl_dim_free(dim);
 827         return NULL;
 828 }
 829
 830 static struct isl_dim *set_names(struct isl_dim *dim, enum isl_dim_type type,
 831         unsigned first, unsigned n, struct isl_name **names)
 832 {
 833         int i;
 834
 835         for (i = 0; i < n ; ++i)
 836                 dim = set_name(dim, type, first+i, names[i]);
 837
 838         return dim;
 839 }
 840
 841 struct isl_dim *isl_dim_reverse(struct isl_dim *dim)
 842 {
 843         unsigned t;
 844         isl_dim *nested;
 845         struct isl_name **names = NULL;
 846         struct isl_name *name;
 847
 848         if (!dim)
 849                 return NULL;
 850         if (match(dim, isl_dim_in, dim, isl_dim_out))
 851                 return dim;
 852
 853         dim = isl_dim_cow(dim);
 854         if (!dim)
 855                 return NULL;
 856
 857         name = dim->tuple_name[0];
 858         dim->tuple_name[0] = dim->tuple_name[1];
 859         dim->tuple_name[1] = name;
 860
 861         nested = dim->nested[0];
 862         dim->nested[0] = dim->nested[1];
 863         dim->nested[1] = nested;
 864
 865         if (dim->names) {
 866                 names = isl_alloc_array(dim->ctx, struct isl_name *,
 867                                         dim->n_in + dim->n_out);
 868                 if (!names)
 869                         goto error;
 870                 get_names(dim, isl_dim_in, 0, dim->n_in, names);
 871                 get_names(dim, isl_dim_out, 0, dim->n_out, names + dim->n_in);
 872         }
 873
 874         t = dim->n_in;
 875         dim->n_in = dim->n_out;
 876         dim->n_out = t;
 877
 878         if (dim->names) {
 879                 dim = set_names(dim, isl_dim_out, 0, dim->n_out, names);
 880                 dim = set_names(dim, isl_dim_in, 0, dim->n_in, names + dim->n_out);
 881                 free(names);
 882         }
 883
 884         return dim;
 885 error:
 886         free(names);
 887         isl_dim_free(dim);
 888         return NULL;
 889 }
 890
 891 struct isl_dim *isl_dim_drop(struct isl_dim *dim, enum isl_dim_type type,
 892                 unsigned first, unsigned num)
 893 {
 894         int i;
 895
 896         if (!dim)
 897                 return NULL;
 898
 899         if (num == 0)
 900                 return isl_dim_reset(dim, type);
 901
 902         if (!valid_dim_type(type))
 903                 isl_die(dim->ctx, isl_error_invalid,
 904                         "cannot drop dimensions of specified type", goto error);
 905
 906         isl_assert(dim->ctx, first + num <= n(dim, type), goto error);
 907         dim = isl_dim_cow(dim);
 908         if (!dim)
 909                 goto error;
 910         if (dim->names) {
 911                 dim = extend_names(dim);
 912                 if (!dim)
 913                         goto error;
 914                 for (i = 0; i < num; ++i)
 915                         isl_name_free(dim->ctx, get_name(dim, type, first+i));
 916                 for (i = first+num; i < n(dim, type); ++i)
 917                         set_name(dim, type, i - num, get_name(dim, type, i));
 918                 switch (type) {
 919                 case isl_dim_param:
 920                         get_names(dim, isl_dim_in, 0, dim->n_in,
 921                                 dim->names + offset(dim, isl_dim_in) - num);
 922                 case isl_dim_in:
 923                         get_names(dim, isl_dim_out, 0, dim->n_out,
 924                                 dim->names + offset(dim, isl_dim_out) - num);
 925                 default:
 926                         ;
 927                 }
 928                 dim->n_name -= num;
 929         }
 930         switch (type) {
 931         case isl_dim_param:     dim->nparam -= num; break;
 932         case isl_dim_in:        dim->n_in -= num; break;
 933         case isl_dim_out:       dim->n_out -= num; break;
 934         default:                ;
 935         }
 936         dim = isl_dim_reset(dim, type);
 937         if (type == isl_dim_param) {
 938                 if (dim && dim->nested[0] &&
 939                     !(dim->nested[0] = isl_dim_drop(dim->nested[0],
 940                                                     isl_dim_param, first, num)))
 941                         goto error;
 942                 if (dim && dim->nested[1] &&
 943                     !(dim->nested[1] = isl_dim_drop(dim->nested[1],
 944                                                     isl_dim_param, first, num)))
 945                         goto error;
 946         }
 947         return dim;
 948 error:
 949         isl_dim_free(dim);
 950         return NULL;
 951 }
 952
 953 struct isl_dim *isl_dim_drop_inputs(struct isl_dim *dim,
 954                 unsigned first, unsigned n)
 955 {
 956         if (!dim)
 957                 return NULL;
 958         return isl_dim_drop(dim, isl_dim_in, first, n);
 959 }
 960
 961 struct isl_dim *isl_dim_drop_outputs(struct isl_dim *dim,
 962                 unsigned first, unsigned n)
 963 {
 964         if (!dim)
 965                 return NULL;
 966         return isl_dim_drop(dim, isl_dim_out, first, n);
 967 }
 968
 969 struct isl_dim *isl_dim_domain(struct isl_dim *dim)
 970 {
 971         if (!dim)
 972                 return NULL;
 973         dim = isl_dim_drop_outputs(dim, 0, dim->n_out);
 974         return isl_dim_reverse(dim);
 975 }
 976
 977 __isl_give isl_dim *isl_dim_from_domain(__isl_take isl_dim *dim)
 978 {
 979         return isl_dim_reverse(dim);
 980 }
 981
 982 struct isl_dim *isl_dim_range(struct isl_dim *dim)
 983 {
 984         if (!dim)
 985                 return NULL;
 986         return isl_dim_drop_inputs(dim, 0, dim->n_in);
 987 }
 988
 989 __isl_give isl_dim *isl_dim_from_range(__isl_take isl_dim *dim)
 990 {
 991         return dim;
 992 }
 993
 994 __isl_give isl_dim *isl_dim_as_set_dim(__isl_take isl_dim *dim)
 995 {
 996         dim = isl_dim_cow(dim);
 997         if (!dim)
 998                 return NULL;
 999
1000         dim->n_out += dim->n_in;
1001         dim->n_in = 0;
1002         dim = isl_dim_reset(dim, isl_dim_in);
1003         dim = isl_dim_reset(dim, isl_dim_out);
1004
1005         return dim;
1006 }
1007
1008 struct isl_dim *isl_dim_underlying(struct isl_dim *dim, unsigned n_div)
1009 {
1010         int i;
1011
1012         if (!dim)
1013                 return NULL;
1014         if (n_div == 0 &&
1015             dim->nparam == 0 && dim->n_in == 0 && dim->n_name == 0)
1016                 return isl_dim_reset(isl_dim_reset(dim, isl_dim_in), isl_dim_out);
1017         dim = isl_dim_cow(dim);
1018         if (!dim)
1019                 return NULL;
1020         dim->n_out += dim->nparam + dim->n_in + n_div;
1021         dim->nparam = 0;
1022         dim->n_in = 0;
1023
1024         for (i = 0; i < dim->n_name; ++i)
1025                 isl_name_free(dim->ctx, get_name(dim, isl_dim_out, i));
1026         dim->n_name = 0;
1027         dim = isl_dim_reset(dim, isl_dim_in);
1028         dim = isl_dim_reset(dim, isl_dim_out);
1029
1030         return dim;
1031 }
1032
1033 unsigned isl_dim_total(struct isl_dim *dim)
1034 {
1035         return dim ? dim->nparam + dim->n_in + dim->n_out : 0;
1036 }
1037
1038 int isl_dim_equal(struct isl_dim *dim1, struct isl_dim *dim2)
1039 {
1040         return match(dim1, isl_dim_param, dim2, isl_dim_param) &&
1041                isl_dim_tuple_match(dim1, isl_dim_in, dim2, isl_dim_in) &&
1042                isl_dim_tuple_match(dim1, isl_dim_out, dim2, isl_dim_out);
1043 }
1044
1045 int isl_dim_compatible(struct isl_dim *dim1, struct isl_dim *dim2)
1046 {
1047         return dim1->nparam == dim2->nparam &&
1048                dim1->n_in + dim1->n_out == dim2->n_in + dim2->n_out;
1049 }
1050
1051 static uint32_t isl_hash_dim(uint32_t hash, __isl_keep isl_dim *dim)
1052 {
1053         int i;
1054         struct isl_name *name;
1055
1056         if (!dim)
1057                 return hash;
1058
1059         hash = isl_hash_builtin(hash, dim->nparam);
1060         hash = isl_hash_builtin(hash, dim->n_in);
1061         hash = isl_hash_builtin(hash, dim->n_out);
1062
1063         for (i = 0; i < dim->nparam; ++i) {
1064                 name = get_name(dim, isl_dim_param, i);
1065                 hash = isl_hash_name(hash, name);
1066         }
1067
1068         name = tuple_name(dim, isl_dim_in);
1069         hash = isl_hash_name(hash, name);
1070         name = tuple_name(dim, isl_dim_out);
1071         hash = isl_hash_name(hash, name);
1072
1073         hash = isl_hash_dim(hash, dim->nested[0]);
1074         hash = isl_hash_dim(hash, dim->nested[1]);
1075
1076         return hash;
1077 }
1078
1079 uint32_t isl_dim_get_hash(__isl_keep isl_dim *dim)
1080 {
1081         uint32_t hash;
1082
1083         if (!dim)
1084                 return 0;
1085
1086         hash = isl_hash_init();
1087         hash = isl_hash_dim(hash, dim);
1088
1089         return hash;
1090 }
1091
1092 int isl_dim_is_wrapping(__isl_keep isl_dim *dim)
1093 {
1094         if (!dim)
1095                 return -1;
1096
1097         if (dim->n_in != 0 || dim->tuple_name[0] || dim->nested[0])
1098                 return 0;
1099
1100         return dim->nested[1] != NULL;
1101 }
1102
1103 __isl_give isl_dim *isl_dim_wrap(__isl_take isl_dim *dim)
1104 {
1105         isl_dim *wrap;
1106
1107         if (!dim)
1108                 return NULL;
1109
1110         wrap = isl_dim_alloc(dim->ctx, dim->nparam, 0, dim->n_in + dim->n_out);
1111
1112         wrap = copy_names(wrap, isl_dim_param, 0, dim, isl_dim_param);
1113         wrap = copy_names(wrap, isl_dim_set, 0, dim, isl_dim_in);
1114         wrap = copy_names(wrap, isl_dim_set, dim->n_in, dim, isl_dim_out);
1115
1116         if (!wrap)
1117                 goto error;
1118
1119         wrap->nested[1] = dim;
1120
1121         return wrap;
1122 error:
1123         isl_dim_free(dim);
1124         return NULL;
1125 }
1126
1127 __isl_give isl_dim *isl_dim_unwrap(__isl_take isl_dim *dim)
1128 {
1129         isl_dim *unwrap;
1130
1131         if (!dim)
1132                 return NULL;
1133
1134         if (!isl_dim_is_wrapping(dim))
1135                 isl_die(dim->ctx, isl_error_invalid, "not a wrapping dim",
1136                         goto error);
1137
1138         unwrap = isl_dim_copy(dim->nested[1]);
1139         isl_dim_free(dim);
1140
1141         return unwrap;
1142 error:
1143         isl_dim_free(dim);
1144         return NULL;
1145 }
1146
1147 int isl_dim_is_named_or_nested(__isl_keep isl_dim *dim, enum isl_dim_type type)
1148 {
1149         if (type != isl_dim_in && type != isl_dim_out)
1150                 return 0;
1151         if (!dim)
1152                 return -1;
1153         if (dim->tuple_name[type - isl_dim_in])
1154                 return 1;
1155         if (dim->nested[type - isl_dim_in])
1156                 return 1;
1157         return 0;
1158 }
1159
1160 int isl_dim_may_be_set(__isl_keep isl_dim *dim)
1161 {
1162         if (!dim)
1163                 return -1;
1164         if (isl_dim_size(dim, isl_dim_in) != 0)
1165                 return 0;
1166         if (isl_dim_is_named_or_nested(dim, isl_dim_in))
1167                 return 0;
1168         return 1;
1169 }
1170
1171 __isl_give isl_dim *isl_dim_reset(__isl_take isl_dim *dim,
1172         enum isl_dim_type type)
1173 {
1174         if (!isl_dim_is_named_or_nested(dim, type))
1175                 return dim;
1176
1177         dim = isl_dim_cow(dim);
1178         if (!dim)
1179                 return NULL;
1180
1181         isl_name_free(dim->ctx, dim->tuple_name[type - isl_dim_in]);
1182         dim->tuple_name[type - isl_dim_in] = NULL;
1183         isl_dim_free(dim->nested[type - isl_dim_in]);
1184         dim->nested[type - isl_dim_in] = NULL;
1185
1186         return dim;
1187 }
1188
1189 __isl_give isl_dim *isl_dim_flatten(__isl_take isl_dim *dim)
1190 {
1191         if (!dim)
1192                 return NULL;
1193         if (!dim->nested[0] && !dim->nested[1])
1194                 return dim;
1195
1196         if (dim->nested[0])
1197                 dim = isl_dim_reset(dim, isl_dim_in);
1198         if (dim && dim->nested[1])
1199                 dim = isl_dim_reset(dim, isl_dim_out);
1200
1201         return dim;
1202 }
1203
1204 __isl_give isl_dim *isl_dim_flatten_range(__isl_take isl_dim *dim)
1205 {
1206         if (!dim)
1207                 return NULL;
1208         if (!dim->nested[1])
1209                 return dim;
1210
1211         return isl_dim_reset(dim, isl_dim_out);
1212 }
1213
1214 /* Replace the dimensions of the given type of dst by those of src.
1215  */
1216 __isl_give isl_dim *isl_dim_replace(__isl_take isl_dim *dst,
1217         enum isl_dim_type type, __isl_keep isl_dim *src)
1218 {
1219         dst = isl_dim_cow(dst);
1220
1221         if (!dst || !src)
1222                 goto error;
1223
1224         dst = isl_dim_drop(dst, type, 0, isl_dim_size(dst, type));
1225         dst = isl_dim_add(dst, type, isl_dim_size(src, type));
1226         dst = copy_names(dst, type, 0, src, type);
1227
1228         if (dst && type == isl_dim_param) {
1229                 int i;
1230                 for (i = 0; i <= 1; ++i) {
1231                         if (!dst->nested[i])
1232                                 continue;
1233                         dst->nested[i] = isl_dim_replace(dst->nested[i],
1234                                                          type, src);
1235                         if (!dst->nested[i])
1236                                 goto error;
1237                 }
1238         }
1239
1240         return dst;
1241 error:
1242         isl_dim_free(dst);
1243         return NULL;
1244 }
1245
1246 /* Given a dimension specification "dim" of a set, create a dimension
1247  * specification for the lift of the set.  In particular, the result
1248  * is of the form [dim -> local[..]], with n_local variables in the
1249  * range of the wrapped map.
1250  */
1251 __isl_give isl_dim *isl_dim_lift(__isl_take isl_dim *dim, unsigned n_local)
1252 {
1253         isl_dim *local_dim;
1254
1255         if (!dim)
1256                 return NULL;
1257
1258         local_dim = isl_dim_dup(dim);
1259         local_dim = isl_dim_drop(local_dim, isl_dim_set, 0, dim->n_out);
1260         local_dim = isl_dim_add(local_dim, isl_dim_set, n_local);
1261         local_dim = isl_dim_set_tuple_name(local_dim, isl_dim_set, "local");
1262         dim = isl_dim_join(isl_dim_from_domain(dim),
1263                             isl_dim_from_range(local_dim));
1264         dim = isl_dim_wrap(dim);
1265         dim = isl_dim_set_tuple_name(dim, isl_dim_set, "lifted");
1266
1267         return dim;
1268 }
1269
1270 int isl_dim_can_zip(__isl_keep isl_dim *dim)
1271 {
1272         if (!dim)
1273                 return -1;
1274
1275         return dim->nested[0] && dim->nested[1];
1276 }
1277
1278 __isl_give isl_dim *isl_dim_zip(__isl_take isl_dim *dim)
1279 {
1280         isl_dim *dom, *ran;
1281         isl_dim *dom_dom, *dom_ran, *ran_dom, *ran_ran;
1282
1283         if (!isl_dim_can_zip(dim))
1284                 isl_die(dim->ctx, isl_error_invalid, "dim cannot be zipped",
1285                         goto error);
1286
1287         if (!dim)
1288                 return 0;
1289         dom = isl_dim_unwrap(isl_dim_domain(isl_dim_copy(dim)));
1290         ran = isl_dim_unwrap(isl_dim_range(dim));
1291         dom_dom = isl_dim_domain(isl_dim_copy(dom));
1292         dom_ran = isl_dim_range(dom);
1293         ran_dom = isl_dim_domain(isl_dim_copy(ran));
1294         ran_ran = isl_dim_range(ran);
1295         dom = isl_dim_join(isl_dim_from_domain(dom_dom),
1296                            isl_dim_from_range(ran_dom));
1297         ran = isl_dim_join(isl_dim_from_domain(dom_ran),
1298                            isl_dim_from_range(ran_ran));
1299         return isl_dim_join(isl_dim_from_domain(isl_dim_wrap(dom)),
1300                             isl_dim_from_range(isl_dim_wrap(ran)));
1301 error:
1302         isl_dim_free(dim);
1303         return NULL;
1304 }
1305
1306 int isl_dim_has_named_params(__isl_keep isl_dim *dim)
1307 {
1308         int i;
1309         unsigned off;
1310
1311         if (!dim)
1312                 return -1;
1313         if (dim->nparam == 0)
1314                 return 1;
1315         off = isl_dim_offset(dim, isl_dim_param);
1316         if (off + dim->nparam > dim->n_name)
1317                 return 0;
1318         for (i = 0; i < dim->nparam; ++i)
1319                 if (!dim->names[off + i])
1320                         return 0;
1321         return 1;
1322 }
1323
1324 /* Align the initial parameters of dim1 to match the order in dim2.
1325  */
1326 __isl_give isl_dim *isl_dim_align_params(__isl_take isl_dim *dim1,
1327         __isl_take isl_dim *dim2)
1328 {
1329         isl_reordering *exp;
1330
1331         if (!isl_dim_has_named_params(dim1) || !isl_dim_has_named_params(dim2))
1332                 isl_die(isl_dim_get_ctx(dim1), isl_error_invalid,
1333                         "parameter alignment requires named parameters",
1334                         goto error);
1335
1336         exp = isl_parameter_alignment_reordering(dim1, dim2);
1337         isl_dim_free(dim1);
1338         isl_dim_free(dim2);
1339         if (!exp)
1340                 return NULL;
1341         dim1 = isl_dim_copy(exp->dim);
1342         isl_reordering_free(exp);
1343         return dim1;
1344 error:
1345         isl_dim_free(dim1);
1346         isl_dim_free(dim2);
1347         return NULL;
1348 }