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 (n(dim1, dim1_type) != n(dim2, dim2_type))
 398                 return 0;
 399         name1 = tuple_name(dim1, dim1_type);
 400         name2 = tuple_name(dim2, dim2_type);
 401         if (!name1 ^ !name2)
 402                 return 0;
 403         if (name1 && name1->name != name2->name)
 404                 return 0;
 405         nested1 = nested(dim1, dim1_type);
 406         nested2 = nested(dim2, dim2_type);
 407         if (!nested1 ^ !nested2)
 408                 return 0;
 409         if (nested1 && !isl_dim_equal(nested1, nested2))
 410                 return 0;
 411         return 1;
 412 }
 413
 414 static int match(struct isl_dim *dim1, enum isl_dim_type dim1_type,
 415                 struct isl_dim *dim2, enum isl_dim_type dim2_type)
 416 {
 417         int i;
 418
 419         if (!isl_dim_tuple_match(dim1, dim1_type, dim2, dim2_type))
 420                 return 0;
 421
 422         if (!dim1->names && !dim2->names)
 423                 return 1;
 424
 425         for (i = 0; i < n(dim1, dim1_type); ++i) {
 426                 if (get_name(dim1, dim1_type, i) !=
 427                     get_name(dim2, dim2_type, i))
 428                         return 0;
 429         }
 430         return 1;
 431 }
 432
 433 int isl_dim_match(struct isl_dim *dim1, enum isl_dim_type dim1_type,
 434                 struct isl_dim *dim2, enum isl_dim_type dim2_type)
 435 {
 436         return match(dim1, dim1_type, dim2, dim2_type);
 437 }
 438
 439 static void get_names(struct isl_dim *dim, enum isl_dim_type type,
 440         unsigned first, unsigned n, struct isl_name **names)
 441 {
 442         int i;
 443
 444         for (i = 0; i < n ; ++i)
 445                 names[i] = get_name(dim, type, first+i);
 446 }
 447
 448 struct isl_dim *isl_dim_extend(struct isl_dim *dim,
 449                         unsigned nparam, unsigned n_in, unsigned n_out)
 450 {
 451         struct isl_name **names = NULL;
 452
 453         if (!dim)
 454                 return NULL;
 455         if (dim->nparam == nparam && dim->n_in == n_in && dim->n_out == n_out)
 456                 return dim;
 457
 458         isl_assert(dim->ctx, dim->nparam <= nparam, goto error);
 459         isl_assert(dim->ctx, dim->n_in <= n_in, goto error);
 460         isl_assert(dim->ctx, dim->n_out <= n_out, goto error);
 461
 462         dim = isl_dim_cow(dim);
 463
 464         if (dim->names) {
 465                 names = isl_calloc_array(dim->ctx, struct isl_name *,
 466                                          nparam + n_in + n_out);
 467                 if (!names)
 468                         goto error;
 469                 get_names(dim, isl_dim_param, 0, dim->nparam, names);
 470                 get_names(dim, isl_dim_in, 0, dim->n_in, names + nparam);
 471                 get_names(dim, isl_dim_out, 0, dim->n_out,
 472                                 names + nparam + n_in);
 473                 free(dim->names);
 474                 dim->names = names;
 475                 dim->n_name = nparam + n_in + n_out;
 476         }
 477         dim->nparam = nparam;
 478         dim->n_in = n_in;
 479         dim->n_out = n_out;
 480
 481         return dim;
 482 error:
 483         free(names);
 484         isl_dim_free(dim);
 485         return NULL;
 486 }
 487
 488 struct isl_dim *isl_dim_add(struct isl_dim *dim, enum isl_dim_type type,
 489         unsigned n)
 490 {
 491         if (!dim)
 492                 return NULL;
 493         dim = isl_dim_reset(dim, type);
 494         switch (type) {
 495         case isl_dim_param:
 496                 dim = isl_dim_extend(dim,
 497                                         dim->nparam + n, dim->n_in, dim->n_out);
 498                 if (dim && dim->nested[0] &&
 499                     !(dim->nested[0] = isl_dim_add(dim->nested[0],
 500                                                     isl_dim_param, n)))
 501                         goto error;
 502                 if (dim && dim->nested[1] &&
 503                     !(dim->nested[1] = isl_dim_add(dim->nested[1],
 504                                                     isl_dim_param, n)))
 505                         goto error;
 506                 return dim;
 507         case isl_dim_in:
 508                 return isl_dim_extend(dim,
 509                                         dim->nparam, dim->n_in + n, dim->n_out);
 510         case isl_dim_out:
 511                 return isl_dim_extend(dim,
 512                                         dim->nparam, dim->n_in, dim->n_out + n);
 513         default:
 514                 isl_die(dim->ctx, isl_error_invalid,
 515                         "cannot add dimensions of specified type", goto error);
 516         }
 517 error:
 518         isl_dim_free(dim);
 519         return NULL;
 520 }
 521
 522 static int valid_dim_type(enum isl_dim_type type)
 523 {
 524         switch (type) {
 525         case isl_dim_param:
 526         case isl_dim_in:
 527         case isl_dim_out:
 528                 return 1;
 529         default:
 530                 return 0;
 531         }
 532 }
 533
 534 __isl_give isl_dim *isl_dim_insert(__isl_take isl_dim *dim,
 535         enum isl_dim_type type, unsigned pos, unsigned n)
 536 {
 537         struct isl_name **names = NULL;
 538
 539         if (!dim)
 540                 return NULL;
 541         if (n == 0)
 542                 return isl_dim_reset(dim, type);
 543
 544         if (!valid_dim_type(type))
 545                 isl_die(dim->ctx, isl_error_invalid,
 546                         "cannot insert dimensions of specified type",
 547                         goto error);
 548
 549         isl_assert(dim->ctx, pos <= isl_dim_size(dim, type), goto error);
 550
 551         dim = isl_dim_cow(dim);
 552         if (!dim)
 553                 return NULL;
 554
 555         if (dim->names) {
 556                 enum isl_dim_type t;
 557                 int off;
 558                 int s[3];
 559                 int *size = s - isl_dim_param;
 560                 names = isl_calloc_array(dim->ctx, struct isl_name *,
 561                                      dim->nparam + dim->n_in + dim->n_out + n);
 562                 if (!names)
 563                         goto error;
 564                 off = 0;
 565                 size[isl_dim_param] = dim->nparam;
 566                 size[isl_dim_in] = dim->n_in;
 567                 size[isl_dim_out] = dim->n_out;
 568                 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
 569                         if (t != type) {
 570                                 get_names(dim, t, 0, size[t], names + off);
 571                                 off += size[t];
 572                         } else {
 573                                 get_names(dim, t, 0, pos, names + off);
 574                                 off += pos + n;
 575                                 get_names(dim, t, pos, size[t]-pos, names+off);
 576                                 off += size[t] - pos;
 577                         }
 578                 }
 579                 free(dim->names);
 580                 dim->names = names;
 581                 dim->n_name = dim->nparam + dim->n_in + dim->n_out + n;
 582         }
 583         switch (type) {
 584         case isl_dim_param:     dim->nparam += n; break;
 585         case isl_dim_in:        dim->n_in += n; break;
 586         case isl_dim_out:       dim->n_out += n; break;
 587         default:                ;
 588         }
 589         dim = isl_dim_reset(dim, type);
 590
 591         return dim;
 592 error:
 593         isl_dim_free(dim);
 594         return NULL;
 595 }
 596
 597 __isl_give isl_dim *isl_dim_move(__isl_take isl_dim *dim,
 598         enum isl_dim_type dst_type, unsigned dst_pos,
 599         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
 600 {
 601         int i;
 602
 603         if (!dim)
 604                 return NULL;
 605         if (n == 0)
 606                 return dim;
 607
 608         isl_assert(dim->ctx, src_pos + n <= isl_dim_size(dim, src_type),
 609                 goto error);
 610
 611         if (dst_type == src_type && dst_pos == src_pos)
 612                 return dim;
 613
 614         isl_assert(dim->ctx, dst_type != src_type, goto error);
 615
 616         dim = isl_dim_reset(dim, src_type);
 617         dim = isl_dim_reset(dim, dst_type);
 618
 619         dim = isl_dim_cow(dim);
 620         if (!dim)
 621                 return NULL;
 622
 623         if (dim->names) {
 624                 struct isl_name **names;
 625                 enum isl_dim_type t;
 626                 int off;
 627                 int s[3];
 628                 int *size = s - isl_dim_param;
 629                 names = isl_calloc_array(dim->ctx, struct isl_name *,
 630                                          dim->nparam + dim->n_in + dim->n_out);
 631                 if (!names)
 632                         goto error;
 633                 off = 0;
 634                 size[isl_dim_param] = dim->nparam;
 635                 size[isl_dim_in] = dim->n_in;
 636                 size[isl_dim_out] = dim->n_out;
 637                 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
 638                         if (t == dst_type) {
 639                                 get_names(dim, t, 0, dst_pos, names + off);
 640                                 off += dst_pos;
 641                                 get_names(dim, src_type, src_pos, n, names+off);
 642                                 off += n;
 643                                 get_names(dim, t, dst_pos, size[t] - dst_pos,
 644                                                 names + off);
 645                                 off += size[t] - dst_pos;
 646                         } else if (t == src_type) {
 647                                 get_names(dim, t, 0, src_pos, names + off);
 648                                 off += src_pos;
 649                                 get_names(dim, t, src_pos + n,
 650                                             size[t] - src_pos - n, names + off);
 651                                 off += size[t] - src_pos - n;
 652                         } else {
 653                                 get_names(dim, t, 0, size[t], names + off);
 654                                 off += size[t];
 655                         }
 656                 }
 657                 free(dim->names);
 658                 dim->names = names;
 659                 dim->n_name = dim->nparam + dim->n_in + dim->n_out;
 660         }
 661
 662         switch (dst_type) {
 663         case isl_dim_param:     dim->nparam += n; break;
 664         case isl_dim_in:        dim->n_in += n; break;
 665         case isl_dim_out:       dim->n_out += n; break;
 666         default:                ;
 667         }
 668
 669         switch (src_type) {
 670         case isl_dim_param:     dim->nparam -= n; break;
 671         case isl_dim_in:        dim->n_in -= n; break;
 672         case isl_dim_out:       dim->n_out -= n; break;
 673         default:                ;
 674         }
 675
 676         if (dst_type != isl_dim_param && src_type != isl_dim_param)
 677                 return dim;
 678
 679         for (i = 0; i < 2; ++i) {
 680                 if (!dim->nested[i])
 681                         continue;
 682                 dim->nested[i] = isl_dim_replace(dim->nested[i],
 683                                                  isl_dim_param, dim);
 684                 if (!dim->nested[i])
 685                         goto error;
 686         }
 687
 688         return dim;
 689 error:
 690         isl_dim_free(dim);
 691         return NULL;
 692 }
 693
 694 struct isl_dim *isl_dim_join(struct isl_dim *left, struct isl_dim *right)
 695 {
 696         struct isl_dim *dim;
 697
 698         if (!left || !right)
 699                 goto error;
 700
 701         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
 702                         goto error);
 703         isl_assert(left->ctx,
 704                 isl_dim_tuple_match(left, isl_dim_out, right, isl_dim_in),
 705                 goto error);
 706
 707         dim = isl_dim_alloc(left->ctx, left->nparam, left->n_in, right->n_out);
 708         if (!dim)
 709                 goto error;
 710
 711         dim = copy_names(dim, isl_dim_param, 0, left, isl_dim_param);
 712         dim = copy_names(dim, isl_dim_in, 0, left, isl_dim_in);
 713         dim = copy_names(dim, isl_dim_out, 0, right, isl_dim_out);
 714
 715         if (dim && left->tuple_name[0] &&
 716             !(dim->tuple_name[0] = isl_name_copy(dim->ctx, left->tuple_name[0])))
 717                 goto error;
 718         if (dim && right->tuple_name[1] &&
 719             !(dim->tuple_name[1] = isl_name_copy(dim->ctx, right->tuple_name[1])))
 720                 goto error;
 721         if (dim && left->nested[0] &&
 722             !(dim->nested[0] = isl_dim_copy(left->nested[0])))
 723                 goto error;
 724         if (dim && right->nested[1] &&
 725             !(dim->nested[1] = isl_dim_copy(right->nested[1])))
 726                 goto error;
 727
 728         isl_dim_free(left);
 729         isl_dim_free(right);
 730
 731         return dim;
 732 error:
 733         isl_dim_free(left);
 734         isl_dim_free(right);
 735         return NULL;
 736 }
 737
 738 struct isl_dim *isl_dim_product(struct isl_dim *left, struct isl_dim *right)
 739 {
 740         isl_dim *dom1, *dom2, *nest1, *nest2;
 741
 742         if (!left || !right)
 743                 goto error;
 744
 745         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
 746                         goto error);
 747
 748         dom1 = isl_dim_domain(isl_dim_copy(left));
 749         dom2 = isl_dim_domain(isl_dim_copy(right));
 750         nest1 = isl_dim_wrap(isl_dim_join(isl_dim_reverse(dom1), dom2));
 751
 752         dom1 = isl_dim_range(left);
 753         dom2 = isl_dim_range(right);
 754         nest2 = isl_dim_wrap(isl_dim_join(isl_dim_reverse(dom1), dom2));
 755
 756         return isl_dim_join(isl_dim_reverse(nest1), nest2);
 757 error:
 758         isl_dim_free(left);
 759         isl_dim_free(right);
 760         return NULL;
 761 }
 762
 763 __isl_give isl_dim *isl_dim_range_product(__isl_take isl_dim *left,
 764         __isl_take isl_dim *right)
 765 {
 766         isl_dim *dom, *ran1, *ran2, *nest;
 767
 768         if (!left || !right)
 769                 goto error;
 770
 771         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
 772                         goto error);
 773         if (!isl_dim_match(left, isl_dim_in, right, isl_dim_in))
 774                 isl_die(left->ctx, isl_error_invalid,
 775                         "domains need to match", goto error);
 776
 777         dom = isl_dim_domain(isl_dim_copy(left));
 778
 779         ran1 = isl_dim_range(left);
 780         ran2 = isl_dim_range(right);
 781         nest = isl_dim_wrap(isl_dim_join(isl_dim_reverse(ran1), ran2));
 782
 783         return isl_dim_join(isl_dim_reverse(dom), nest);
 784 error:
 785         isl_dim_free(left);
 786         isl_dim_free(right);
 787         return NULL;
 788 }
 789
 790 __isl_give isl_dim *isl_dim_map_from_set(__isl_take isl_dim *dim)
 791 {
 792         struct isl_name **names = NULL;
 793
 794         if (!dim)
 795                 return NULL;
 796         isl_assert(dim->ctx, dim->n_in == 0, goto error);
 797         if (dim->n_out == 0 && !isl_dim_is_named_or_nested(dim, isl_dim_out))
 798                 return dim;
 799         dim = isl_dim_cow(dim);
 800         if (!dim)
 801                 return NULL;
 802         if (dim->names) {
 803                 names = isl_calloc_array(dim->ctx, struct isl_name *,
 804                                         dim->nparam + dim->n_out + dim->n_out);
 805                 if (!names)
 806                         goto error;
 807                 get_names(dim, isl_dim_param, 0, dim->nparam, names);
 808                 get_names(dim, isl_dim_out, 0, dim->n_out, names + dim->nparam);
 809         }
 810         dim->n_in = dim->n_out;
 811         if (names) {
 812                 free(dim->names);
 813                 dim->names = names;
 814                 dim->n_name = dim->nparam + dim->n_out + dim->n_out;
 815                 dim = copy_names(dim, isl_dim_out, 0, dim, isl_dim_in);
 816         }
 817         isl_name_free(dim->ctx, dim->tuple_name[0]);
 818         dim->tuple_name[0] = isl_name_copy(dim->ctx, dim->tuple_name[1]);
 819         isl_dim_free(dim->nested[0]);
 820         dim->nested[0] = isl_dim_copy(dim->nested[1]);
 821         return dim;
 822 error:
 823         isl_dim_free(dim);
 824         return NULL;
 825 }
 826
 827 static struct isl_dim *set_names(struct isl_dim *dim, enum isl_dim_type type,
 828         unsigned first, unsigned n, struct isl_name **names)
 829 {
 830         int i;
 831
 832         for (i = 0; i < n ; ++i)
 833                 dim = set_name(dim, type, first+i, names[i]);
 834
 835         return dim;
 836 }
 837
 838 struct isl_dim *isl_dim_reverse(struct isl_dim *dim)
 839 {
 840         unsigned t;
 841         isl_dim *nested;
 842         struct isl_name **names = NULL;
 843         struct isl_name *name;
 844
 845         if (!dim)
 846                 return NULL;
 847         if (match(dim, isl_dim_in, dim, isl_dim_out))
 848                 return dim;
 849
 850         dim = isl_dim_cow(dim);
 851         if (!dim)
 852                 return NULL;
 853
 854         name = dim->tuple_name[0];
 855         dim->tuple_name[0] = dim->tuple_name[1];
 856         dim->tuple_name[1] = name;
 857
 858         nested = dim->nested[0];
 859         dim->nested[0] = dim->nested[1];
 860         dim->nested[1] = nested;
 861
 862         if (dim->names) {
 863                 names = isl_alloc_array(dim->ctx, struct isl_name *,
 864                                         dim->n_in + dim->n_out);
 865                 if (!names)
 866                         goto error;
 867                 get_names(dim, isl_dim_in, 0, dim->n_in, names);
 868                 get_names(dim, isl_dim_out, 0, dim->n_out, names + dim->n_in);
 869         }
 870
 871         t = dim->n_in;
 872         dim->n_in = dim->n_out;
 873         dim->n_out = t;
 874
 875         if (dim->names) {
 876                 dim = set_names(dim, isl_dim_out, 0, dim->n_out, names);
 877                 dim = set_names(dim, isl_dim_in, 0, dim->n_in, names + dim->n_out);
 878                 free(names);
 879         }
 880
 881         return dim;
 882 error:
 883         free(names);
 884         isl_dim_free(dim);
 885         return NULL;
 886 }
 887
 888 struct isl_dim *isl_dim_drop(struct isl_dim *dim, enum isl_dim_type type,
 889                 unsigned first, unsigned num)
 890 {
 891         int i;
 892
 893         if (!dim)
 894                 return NULL;
 895
 896         if (num == 0)
 897                 return isl_dim_reset(dim, type);
 898
 899         if (!valid_dim_type(type))
 900                 isl_die(dim->ctx, isl_error_invalid,
 901                         "cannot drop dimensions of specified type", goto error);
 902
 903         isl_assert(dim->ctx, first + num <= n(dim, type), goto error);
 904         dim = isl_dim_cow(dim);
 905         if (!dim)
 906                 goto error;
 907         if (dim->names) {
 908                 dim = extend_names(dim);
 909                 if (!dim)
 910                         goto error;
 911                 for (i = 0; i < num; ++i)
 912                         isl_name_free(dim->ctx, get_name(dim, type, first+i));
 913                 for (i = first+num; i < n(dim, type); ++i)
 914                         set_name(dim, type, i - num, get_name(dim, type, i));
 915                 switch (type) {
 916                 case isl_dim_param:
 917                         get_names(dim, isl_dim_in, 0, dim->n_in,
 918                                 dim->names + offset(dim, isl_dim_in) - num);
 919                 case isl_dim_in:
 920                         get_names(dim, isl_dim_out, 0, dim->n_out,
 921                                 dim->names + offset(dim, isl_dim_out) - num);
 922                 default:
 923                         ;
 924                 }
 925                 dim->n_name -= num;
 926         }
 927         switch (type) {
 928         case isl_dim_param:     dim->nparam -= num; break;
 929         case isl_dim_in:        dim->n_in -= num; break;
 930         case isl_dim_out:       dim->n_out -= num; break;
 931         default:                ;
 932         }
 933         dim = isl_dim_reset(dim, type);
 934         if (type == isl_dim_param) {
 935                 if (dim && dim->nested[0] &&
 936                     !(dim->nested[0] = isl_dim_drop(dim->nested[0],
 937                                                     isl_dim_param, first, num)))
 938                         goto error;
 939                 if (dim && dim->nested[1] &&
 940                     !(dim->nested[1] = isl_dim_drop(dim->nested[1],
 941                                                     isl_dim_param, first, num)))
 942                         goto error;
 943         }
 944         return dim;
 945 error:
 946         isl_dim_free(dim);
 947         return NULL;
 948 }
 949
 950 struct isl_dim *isl_dim_drop_inputs(struct isl_dim *dim,
 951                 unsigned first, unsigned n)
 952 {
 953         if (!dim)
 954                 return NULL;
 955         return isl_dim_drop(dim, isl_dim_in, first, n);
 956 }
 957
 958 struct isl_dim *isl_dim_drop_outputs(struct isl_dim *dim,
 959                 unsigned first, unsigned n)
 960 {
 961         if (!dim)
 962                 return NULL;
 963         return isl_dim_drop(dim, isl_dim_out, first, n);
 964 }
 965
 966 struct isl_dim *isl_dim_domain(struct isl_dim *dim)
 967 {
 968         if (!dim)
 969                 return NULL;
 970         dim = isl_dim_drop_outputs(dim, 0, dim->n_out);
 971         return isl_dim_reverse(dim);
 972 }
 973
 974 __isl_give isl_dim *isl_dim_from_domain(__isl_take isl_dim *dim)
 975 {
 976         return isl_dim_reverse(dim);
 977 }
 978
 979 struct isl_dim *isl_dim_range(struct isl_dim *dim)
 980 {
 981         if (!dim)
 982                 return NULL;
 983         return isl_dim_drop_inputs(dim, 0, dim->n_in);
 984 }
 985
 986 __isl_give isl_dim *isl_dim_from_range(__isl_take isl_dim *dim)
 987 {
 988         return dim;
 989 }
 990
 991 __isl_give isl_dim *isl_dim_as_set_dim(__isl_take isl_dim *dim)
 992 {
 993         dim = isl_dim_cow(dim);
 994         if (!dim)
 995                 return NULL;
 996
 997         dim->n_out += dim->n_in;
 998         dim->n_in = 0;
 999         dim = isl_dim_reset(dim, isl_dim_in);
1000         dim = isl_dim_reset(dim, isl_dim_out);
1001
1002         return dim;
1003 }
1004
1005 struct isl_dim *isl_dim_underlying(struct isl_dim *dim, unsigned n_div)
1006 {
1007         int i;
1008
1009         if (!dim)
1010                 return NULL;
1011         if (n_div == 0 &&
1012             dim->nparam == 0 && dim->n_in == 0 && dim->n_name == 0)
1013                 return isl_dim_reset(isl_dim_reset(dim, isl_dim_in), isl_dim_out);
1014         dim = isl_dim_cow(dim);
1015         if (!dim)
1016                 return NULL;
1017         dim->n_out += dim->nparam + dim->n_in + n_div;
1018         dim->nparam = 0;
1019         dim->n_in = 0;
1020
1021         for (i = 0; i < dim->n_name; ++i)
1022                 isl_name_free(dim->ctx, get_name(dim, isl_dim_out, i));
1023         dim->n_name = 0;
1024         dim = isl_dim_reset(dim, isl_dim_in);
1025         dim = isl_dim_reset(dim, isl_dim_out);
1026
1027         return dim;
1028 }
1029
1030 unsigned isl_dim_total(struct isl_dim *dim)
1031 {
1032         return dim ? dim->nparam + dim->n_in + dim->n_out : 0;
1033 }
1034
1035 int isl_dim_equal(struct isl_dim *dim1, struct isl_dim *dim2)
1036 {
1037         return match(dim1, isl_dim_param, dim2, isl_dim_param) &&
1038                isl_dim_tuple_match(dim1, isl_dim_in, dim2, isl_dim_in) &&
1039                isl_dim_tuple_match(dim1, isl_dim_out, dim2, isl_dim_out);
1040 }
1041
1042 int isl_dim_compatible(struct isl_dim *dim1, struct isl_dim *dim2)
1043 {
1044         return dim1->nparam == dim2->nparam &&
1045                dim1->n_in + dim1->n_out == dim2->n_in + dim2->n_out;
1046 }
1047
1048 static uint32_t isl_hash_dim(uint32_t hash, __isl_keep isl_dim *dim)
1049 {
1050         int i;
1051         struct isl_name *name;
1052
1053         if (!dim)
1054                 return hash;
1055
1056         hash = isl_hash_builtin(hash, dim->nparam);
1057         hash = isl_hash_builtin(hash, dim->n_in);
1058         hash = isl_hash_builtin(hash, dim->n_out);
1059
1060         for (i = 0; i < dim->nparam; ++i) {
1061                 name = get_name(dim, isl_dim_param, i);
1062                 hash = isl_hash_name(hash, name);
1063         }
1064
1065         name = tuple_name(dim, isl_dim_in);
1066         hash = isl_hash_name(hash, name);
1067         name = tuple_name(dim, isl_dim_out);
1068         hash = isl_hash_name(hash, name);
1069
1070         hash = isl_hash_dim(hash, dim->nested[0]);
1071         hash = isl_hash_dim(hash, dim->nested[1]);
1072
1073         return hash;
1074 }
1075
1076 uint32_t isl_dim_get_hash(__isl_keep isl_dim *dim)
1077 {
1078         uint32_t hash;
1079
1080         if (!dim)
1081                 return 0;
1082
1083         hash = isl_hash_init();
1084         hash = isl_hash_dim(hash, dim);
1085
1086         return hash;
1087 }
1088
1089 int isl_dim_is_wrapping(__isl_keep isl_dim *dim)
1090 {
1091         if (!dim)
1092                 return -1;
1093
1094         if (dim->n_in != 0 || dim->tuple_name[0] || dim->nested[0])
1095                 return 0;
1096
1097         return dim->nested[1] != NULL;
1098 }
1099
1100 __isl_give isl_dim *isl_dim_wrap(__isl_take isl_dim *dim)
1101 {
1102         isl_dim *wrap;
1103
1104         if (!dim)
1105                 return NULL;
1106
1107         wrap = isl_dim_alloc(dim->ctx, dim->nparam, 0, dim->n_in + dim->n_out);
1108
1109         wrap = copy_names(wrap, isl_dim_param, 0, dim, isl_dim_param);
1110         wrap = copy_names(wrap, isl_dim_set, 0, dim, isl_dim_in);
1111         wrap = copy_names(wrap, isl_dim_set, dim->n_in, dim, isl_dim_out);
1112
1113         if (!wrap)
1114                 goto error;
1115
1116         wrap->nested[1] = dim;
1117
1118         return wrap;
1119 error:
1120         isl_dim_free(dim);
1121         return NULL;
1122 }
1123
1124 __isl_give isl_dim *isl_dim_unwrap(__isl_take isl_dim *dim)
1125 {
1126         isl_dim *unwrap;
1127
1128         if (!dim)
1129                 return NULL;
1130
1131         if (!isl_dim_is_wrapping(dim))
1132                 isl_die(dim->ctx, isl_error_invalid, "not a wrapping dim",
1133                         goto error);
1134
1135         unwrap = isl_dim_copy(dim->nested[1]);
1136         isl_dim_free(dim);
1137
1138         return unwrap;
1139 error:
1140         isl_dim_free(dim);
1141         return NULL;
1142 }
1143
1144 int isl_dim_is_named_or_nested(__isl_keep isl_dim *dim, enum isl_dim_type type)
1145 {
1146         if (type != isl_dim_in && type != isl_dim_out)
1147                 return 0;
1148         if (!dim)
1149                 return -1;
1150         if (dim->tuple_name[type - isl_dim_in])
1151                 return 1;
1152         if (dim->nested[type - isl_dim_in])
1153                 return 1;
1154         return 0;
1155 }
1156
1157 int isl_dim_may_be_set(__isl_keep isl_dim *dim)
1158 {
1159         if (!dim)
1160                 return -1;
1161         if (isl_dim_size(dim, isl_dim_in) != 0)
1162                 return 0;
1163         if (isl_dim_is_named_or_nested(dim, isl_dim_in))
1164                 return 0;
1165         return 1;
1166 }
1167
1168 __isl_give isl_dim *isl_dim_reset(__isl_take isl_dim *dim,
1169         enum isl_dim_type type)
1170 {
1171         if (!isl_dim_is_named_or_nested(dim, type))
1172                 return dim;
1173
1174         dim = isl_dim_cow(dim);
1175         if (!dim)
1176                 return NULL;
1177
1178         isl_name_free(dim->ctx, dim->tuple_name[type - isl_dim_in]);
1179         dim->tuple_name[type - isl_dim_in] = NULL;
1180         isl_dim_free(dim->nested[type - isl_dim_in]);
1181         dim->nested[type - isl_dim_in] = NULL;
1182
1183         return dim;
1184 }
1185
1186 __isl_give isl_dim *isl_dim_flatten(__isl_take isl_dim *dim)
1187 {
1188         if (!dim)
1189                 return NULL;
1190         if (!dim->nested[0] && !dim->nested[1])
1191                 return dim;
1192
1193         if (dim->nested[0])
1194                 dim = isl_dim_reset(dim, isl_dim_in);
1195         if (dim && dim->nested[1])
1196                 dim = isl_dim_reset(dim, isl_dim_out);
1197
1198         return dim;
1199 }
1200
1201 __isl_give isl_dim *isl_dim_flatten_range(__isl_take isl_dim *dim)
1202 {
1203         if (!dim)
1204                 return NULL;
1205         if (!dim->nested[1])
1206                 return dim;
1207
1208         return isl_dim_reset(dim, isl_dim_out);
1209 }
1210
1211 /* Replace the dimensions of the given type of dst by those of src.
1212  */
1213 __isl_give isl_dim *isl_dim_replace(__isl_take isl_dim *dst,
1214         enum isl_dim_type type, __isl_keep isl_dim *src)
1215 {
1216         dst = isl_dim_cow(dst);
1217
1218         if (!dst || !src)
1219                 goto error;
1220
1221         dst = isl_dim_drop(dst, type, 0, isl_dim_size(dst, type));
1222         dst = isl_dim_add(dst, type, isl_dim_size(src, type));
1223         dst = copy_names(dst, type, 0, src, type);
1224
1225         if (dst && type == isl_dim_param) {
1226                 int i;
1227                 for (i = 0; i <= 1; ++i) {
1228                         if (!dst->nested[i])
1229                                 continue;
1230                         dst->nested[i] = isl_dim_replace(dst->nested[i],
1231                                                          type, src);
1232                         if (!dst->nested[i])
1233                                 goto error;
1234                 }
1235         }
1236
1237         return dst;
1238 error:
1239         isl_dim_free(dst);
1240         return NULL;
1241 }
1242
1243 /* Given a dimension specification "dim" of a set, create a dimension
1244  * specification for the lift of the set.  In particular, the result
1245  * is of the form [dim -> local[..]], with n_local variables in the
1246  * range of the wrapped map.
1247  */
1248 __isl_give isl_dim *isl_dim_lift(__isl_take isl_dim *dim, unsigned n_local)
1249 {
1250         isl_dim *local_dim;
1251
1252         if (!dim)
1253                 return NULL;
1254
1255         local_dim = isl_dim_dup(dim);
1256         local_dim = isl_dim_drop(local_dim, isl_dim_set, 0, dim->n_out);
1257         local_dim = isl_dim_add(local_dim, isl_dim_set, n_local);
1258         local_dim = isl_dim_set_tuple_name(local_dim, isl_dim_set, "local");
1259         dim = isl_dim_join(isl_dim_from_domain(dim),
1260                             isl_dim_from_range(local_dim));
1261         dim = isl_dim_wrap(dim);
1262         dim = isl_dim_set_tuple_name(dim, isl_dim_set, "lifted");
1263
1264         return dim;
1265 }
1266
1267 int isl_dim_can_zip(__isl_keep isl_dim *dim)
1268 {
1269         if (!dim)
1270                 return -1;
1271
1272         return dim->nested[0] && dim->nested[1];
1273 }
1274
1275 __isl_give isl_dim *isl_dim_zip(__isl_take isl_dim *dim)
1276 {
1277         isl_dim *dom, *ran;
1278         isl_dim *dom_dom, *dom_ran, *ran_dom, *ran_ran;
1279
1280         if (!isl_dim_can_zip(dim))
1281                 isl_die(dim->ctx, isl_error_invalid, "dim cannot be zipped",
1282                         goto error);
1283
1284         if (!dim)
1285                 return 0;
1286         dom = isl_dim_unwrap(isl_dim_domain(isl_dim_copy(dim)));
1287         ran = isl_dim_unwrap(isl_dim_range(dim));
1288         dom_dom = isl_dim_domain(isl_dim_copy(dom));
1289         dom_ran = isl_dim_range(dom);
1290         ran_dom = isl_dim_domain(isl_dim_copy(ran));
1291         ran_ran = isl_dim_range(ran);
1292         dom = isl_dim_join(isl_dim_from_domain(dom_dom),
1293                            isl_dim_from_range(ran_dom));
1294         ran = isl_dim_join(isl_dim_from_domain(dom_ran),
1295                            isl_dim_from_range(ran_ran));
1296         return isl_dim_join(isl_dim_from_domain(isl_dim_wrap(dom)),
1297                             isl_dim_from_range(isl_dim_wrap(ran)));
1298 error:
1299         isl_dim_free(dim);
1300         return NULL;
1301 }
1302
1303 int isl_dim_has_named_params(__isl_keep isl_dim *dim)
1304 {
1305         int i;
1306         unsigned off;
1307
1308         if (!dim)
1309                 return -1;
1310         if (dim->nparam == 0)
1311                 return 1;
1312         off = isl_dim_offset(dim, isl_dim_param);
1313         if (off + dim->nparam > dim->n_name)
1314                 return 0;
1315         for (i = 0; i < dim->nparam; ++i)
1316                 if (!dim->names[off + i])
1317                         return 0;
1318         return 1;
1319 }
1320
1321 /* Align the initial parameters of dim1 to match the order in dim2.
1322  */
1323 __isl_give isl_dim *isl_dim_align_params(__isl_take isl_dim *dim1,
1324         __isl_take isl_dim *dim2)
1325 {
1326         isl_reordering *exp;
1327
1328         if (!isl_dim_has_named_params(dim1) || !isl_dim_has_named_params(dim2))
1329                 isl_die(isl_dim_get_ctx(dim1), isl_error_invalid,
1330                         "parameter alignment requires named parameters",
1331                         goto error);
1332
1333         exp = isl_parameter_alignment_reordering(dim1, dim2);
1334         isl_dim_free(dim1);
1335         isl_dim_free(dim2);
1336         if (!exp)
1337                 return NULL;
1338         dim1 = isl_dim_copy(exp->dim);
1339         isl_reordering_free(exp);
1340         return dim1;
1341 error:
1342         isl_dim_free(dim1);
1343         isl_dim_free(dim2);
1344         return NULL;
1345 }