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