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