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         default:                return 0;
 172         }
 173 }
 174
 175 unsigned isl_dim_size(struct isl_dim *dim, enum isl_dim_type type)
 176 {
 177         if (!dim)
 178                 return 0;
 179         return n(dim, type);
 180 }
 181
 182 unsigned isl_dim_offset(__isl_keep isl_dim *dim, enum isl_dim_type type)
 183 {
 184         if (!dim)
 185                 return 0;
 186         return offset(dim, type);
 187 }
 188
 189 static struct isl_dim *copy_names(struct isl_dim *dst,
 190         enum isl_dim_type dst_type, unsigned offset, struct isl_dim *src,
 191         enum isl_dim_type src_type)
 192 {
 193         int i;
 194         struct isl_name *name;
 195
 196         if (!dst)
 197                 return NULL;
 198
 199         for (i = 0; i < n(src, src_type); ++i) {
 200                 name = get_name(src, src_type, i);
 201                 if (!name)
 202                         continue;
 203                 dst = set_name(dst, dst_type, offset + i,
 204                                         isl_name_copy(dst->ctx, name));
 205                 if (!dst)
 206                         return NULL;
 207         }
 208         return dst;
 209 }
 210
 211 struct isl_dim *isl_dim_dup(struct isl_dim *dim)
 212 {
 213         struct isl_dim *dup;
 214         if (!dim)
 215                 return NULL;
 216         dup = isl_dim_alloc(dim->ctx, dim->nparam, dim->n_in, dim->n_out);
 217         if (dim->tuple_name[0] &&
 218             !(dup->tuple_name[0] = isl_name_copy(dim->ctx, dim->tuple_name[0])))
 219                 goto error;
 220         if (dim->tuple_name[1] &&
 221             !(dup->tuple_name[1] = isl_name_copy(dim->ctx, dim->tuple_name[1])))
 222                 goto error;
 223         if (dim->nested[0] && !(dup->nested[0] = isl_dim_copy(dim->nested[0])))
 224                 goto error;
 225         if (dim->nested[1] && !(dup->nested[1] = isl_dim_copy(dim->nested[1])))
 226                 goto error;
 227         if (!dim->names)
 228                 return dup;
 229         dup = copy_names(dup, isl_dim_param, 0, dim, isl_dim_param);
 230         dup = copy_names(dup, isl_dim_in, 0, dim, isl_dim_in);
 231         dup = copy_names(dup, isl_dim_out, 0, dim, isl_dim_out);
 232         return dup;
 233 error:
 234         isl_dim_free(dup);
 235         return NULL;
 236 }
 237
 238 struct isl_dim *isl_dim_cow(struct isl_dim *dim)
 239 {
 240         if (!dim)
 241                 return NULL;
 242
 243         if (dim->ref == 1)
 244                 return dim;
 245         dim->ref--;
 246         return isl_dim_dup(dim);
 247 }
 248
 249 struct isl_dim *isl_dim_copy(struct isl_dim *dim)
 250 {
 251         if (!dim)
 252                 return NULL;
 253
 254         dim->ref++;
 255         return dim;
 256 }
 257
 258 void isl_dim_free(struct isl_dim *dim)
 259 {
 260         int i;
 261
 262         if (!dim)
 263                 return;
 264
 265         if (--dim->ref > 0)
 266                 return;
 267
 268         isl_name_free(dim->ctx, dim->tuple_name[0]);
 269         isl_name_free(dim->ctx, dim->tuple_name[1]);
 270
 271         isl_dim_free(dim->nested[0]);
 272         isl_dim_free(dim->nested[1]);
 273
 274         for (i = 0; i < dim->n_name; ++i)
 275                 isl_name_free(dim->ctx, dim->names[i]);
 276         free(dim->names);
 277         isl_ctx_deref(dim->ctx);
 278
 279         free(dim);
 280 }
 281
 282 static int name_ok(isl_ctx *ctx, const char *s)
 283 {
 284         char *p;
 285         long dummy;
 286
 287         dummy = strtol(s, &p, 0);
 288         if (p != s)
 289                 isl_die(ctx, isl_error_invalid, "name looks like a number",
 290                         return 0);
 291
 292         return 1;
 293 }
 294
 295 __isl_give isl_dim *isl_dim_set_tuple_name(__isl_take isl_dim *dim,
 296         enum isl_dim_type type, const char *s)
 297 {
 298         struct isl_name *name;
 299
 300         dim = isl_dim_cow(dim);
 301         if (!dim)
 302                 return NULL;
 303         if (type != isl_dim_in && type != isl_dim_out)
 304                 isl_die(dim->ctx, isl_error_invalid,
 305                         "only input, output and set tuples can have names",
 306                         goto error);
 307         if (!s) {
 308                 name = NULL;
 309         } else {
 310                 if (!name_ok(dim->ctx, s))
 311                         goto error;
 312                 name = isl_name_get(dim->ctx, s);
 313                 if (!name)
 314                         goto error;
 315         }
 316
 317         isl_name_free(dim->ctx, dim->tuple_name[type - isl_dim_in]);
 318         dim->tuple_name[type - isl_dim_in] = name;
 319
 320         return dim;
 321 error:
 322         isl_dim_free(dim);
 323         return NULL;
 324 }
 325
 326 const char *isl_dim_get_tuple_name(__isl_keep isl_dim *dim,
 327          enum isl_dim_type type)
 328 {
 329         struct isl_name *name;
 330         if (!dim)
 331                 return NULL;
 332         if (type != isl_dim_in && type != isl_dim_out)
 333                 return NULL;
 334         name = dim->tuple_name[type - isl_dim_in];
 335         return name ? name->name : NULL;
 336 }
 337
 338 struct isl_dim *isl_dim_set_name(struct isl_dim *dim,
 339                                  enum isl_dim_type type, unsigned pos,
 340                                  const char *s)
 341 {
 342         struct isl_name *name;
 343
 344         if (!dim)
 345                 return NULL;
 346         if (!name_ok(dim->ctx, s))
 347                 goto error;
 348         isl_name_free(dim->ctx, get_name(dim, type, pos));
 349         name = isl_name_get(dim->ctx, s);
 350         if (!name)
 351                 goto error;
 352         return set_name(dim, type, pos, name);
 353 error:
 354         isl_dim_free(dim);
 355         return NULL;
 356 }
 357
 358 const char *isl_dim_get_name(struct isl_dim *dim,
 359                                  enum isl_dim_type type, unsigned pos)
 360 {
 361         struct isl_name *name = get_name(dim, type, pos);
 362         return name ? name->name : NULL;
 363 }
 364
 365 static struct isl_name *tuple_name(__isl_keep isl_dim *dim,
 366         enum isl_dim_type type)
 367 {
 368         if (!dim)
 369                 return NULL;
 370         if (type == isl_dim_in)
 371                 return dim->tuple_name[0];
 372         if (type == isl_dim_out)
 373                 return dim->tuple_name[1];
 374         return NULL;
 375 }
 376
 377 static __isl_keep isl_dim *nested(__isl_keep isl_dim *dim,
 378         enum isl_dim_type type)
 379 {
 380         if (!dim)
 381                 return NULL;
 382         if (type == isl_dim_in)
 383                 return dim->nested[0];
 384         if (type == isl_dim_out)
 385                 return dim->nested[1];
 386         return NULL;
 387 }
 388
 389 int isl_dim_tuple_match(__isl_keep isl_dim *dim1, enum isl_dim_type dim1_type,
 390                         __isl_keep isl_dim *dim2, enum isl_dim_type dim2_type)
 391 {
 392         struct isl_name *name1, *name2;
 393         isl_dim *nested1, *nested2;
 394
 395         if (n(dim1, dim1_type) != n(dim2, dim2_type))
 396                 return 0;
 397         name1 = tuple_name(dim1, dim1_type);
 398         name2 = tuple_name(dim2, dim2_type);
 399         if (!name1 ^ !name2)
 400                 return 0;
 401         if (name1 && name1->name != name2->name)
 402                 return 0;
 403         nested1 = nested(dim1, dim1_type);
 404         nested2 = nested(dim2, dim2_type);
 405         if (!nested1 ^ !nested2)
 406                 return 0;
 407         if (nested1 && !isl_dim_equal(nested1, nested2))
 408                 return 0;
 409         return 1;
 410 }
 411
 412 static int match(struct isl_dim *dim1, enum isl_dim_type dim1_type,
 413                 struct isl_dim *dim2, enum isl_dim_type dim2_type)
 414 {
 415         int i;
 416
 417         if (!isl_dim_tuple_match(dim1, dim1_type, dim2, dim2_type))
 418                 return 0;
 419
 420         if (!dim1->names && !dim2->names)
 421                 return 1;
 422
 423         for (i = 0; i < n(dim1, dim1_type); ++i) {
 424                 if (get_name(dim1, dim1_type, i) !=
 425                     get_name(dim2, dim2_type, i))
 426                         return 0;
 427         }
 428         return 1;
 429 }
 430
 431 int isl_dim_match(struct isl_dim *dim1, enum isl_dim_type dim1_type,
 432                 struct isl_dim *dim2, enum isl_dim_type dim2_type)
 433 {
 434         return match(dim1, dim1_type, dim2, dim2_type);
 435 }
 436
 437 static void get_names(struct isl_dim *dim, enum isl_dim_type type,
 438         unsigned first, unsigned n, struct isl_name **names)
 439 {
 440         int i;
 441
 442         for (i = 0; i < n ; ++i)
 443                 names[i] = get_name(dim, type, first+i);
 444 }
 445
 446 struct isl_dim *isl_dim_extend(struct isl_dim *dim,
 447                         unsigned nparam, unsigned n_in, unsigned n_out)
 448 {
 449         struct isl_name **names = NULL;
 450
 451         if (!dim)
 452                 return NULL;
 453         if (dim->nparam == nparam && dim->n_in == n_in && dim->n_out == n_out)
 454                 return dim;
 455
 456         isl_assert(dim->ctx, dim->nparam <= nparam, goto error);
 457         isl_assert(dim->ctx, dim->n_in <= n_in, goto error);
 458         isl_assert(dim->ctx, dim->n_out <= n_out, goto error);
 459
 460         dim = isl_dim_cow(dim);
 461
 462         if (dim->names) {
 463                 names = isl_calloc_array(dim->ctx, struct isl_name *,
 464                                          nparam + n_in + n_out);
 465                 if (!names)
 466                         goto error;
 467                 get_names(dim, isl_dim_param, 0, dim->nparam, names);
 468                 get_names(dim, isl_dim_in, 0, dim->n_in, names + nparam);
 469                 get_names(dim, isl_dim_out, 0, dim->n_out,
 470                                 names + nparam + n_in);
 471                 free(dim->names);
 472                 dim->names = names;
 473                 dim->n_name = nparam + n_in + n_out;
 474         }
 475         dim->nparam = nparam;
 476         dim->n_in = n_in;
 477         dim->n_out = n_out;
 478
 479         return dim;
 480 error:
 481         free(names);
 482         isl_dim_free(dim);
 483         return NULL;
 484 }
 485
 486 struct isl_dim *isl_dim_add(struct isl_dim *dim, enum isl_dim_type type,
 487         unsigned n)
 488 {
 489         if (!dim)
 490                 return NULL;
 491         dim = isl_dim_reset(dim, type);
 492         switch (type) {
 493         case isl_dim_param:
 494                 dim = isl_dim_extend(dim,
 495                                         dim->nparam + n, dim->n_in, dim->n_out);
 496                 if (dim && dim->nested[0] &&
 497                     !(dim->nested[0] = isl_dim_add(dim->nested[0],
 498                                                     isl_dim_param, n)))
 499                         goto error;
 500                 if (dim && dim->nested[1] &&
 501                     !(dim->nested[1] = isl_dim_add(dim->nested[1],
 502                                                     isl_dim_param, n)))
 503                         goto error;
 504                 return dim;
 505         case isl_dim_in:
 506                 return isl_dim_extend(dim,
 507                                         dim->nparam, dim->n_in + n, dim->n_out);
 508         case isl_dim_out:
 509                 return isl_dim_extend(dim,
 510                                         dim->nparam, dim->n_in, dim->n_out + n);
 511         }
 512         return dim;
 513 error:
 514         isl_dim_free(dim);
 515         return NULL;
 516 }
 517
 518 __isl_give isl_dim *isl_dim_insert(__isl_take isl_dim *dim,
 519         enum isl_dim_type type, unsigned pos, unsigned n)
 520 {
 521         struct isl_name **names = NULL;
 522
 523         if (!dim)
 524                 return NULL;
 525         if (n == 0)
 526                 return isl_dim_reset(dim, type);
 527
 528         isl_assert(dim->ctx, pos <= isl_dim_size(dim, type), goto error);
 529
 530         dim = isl_dim_cow(dim);
 531         if (!dim)
 532                 return NULL;
 533
 534         if (dim->names) {
 535                 enum isl_dim_type t;
 536                 int off;
 537                 int s[3];
 538                 int *size = s - isl_dim_param;
 539                 names = isl_calloc_array(dim->ctx, struct isl_name *,
 540                                      dim->nparam + dim->n_in + dim->n_out + n);
 541                 if (!names)
 542                         goto error;
 543                 off = 0;
 544                 size[isl_dim_param] = dim->nparam;
 545                 size[isl_dim_in] = dim->n_in;
 546                 size[isl_dim_out] = dim->n_out;
 547                 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
 548                         if (t != type) {
 549                                 get_names(dim, t, 0, size[t], names + off);
 550                                 off += size[t];
 551                         } else {
 552                                 get_names(dim, t, 0, pos, names + off);
 553                                 off += pos + n;
 554                                 get_names(dim, t, pos, size[t]-pos, names+off);
 555                                 off += size[t] - pos;
 556                         }
 557                 }
 558                 free(dim->names);
 559                 dim->names = names;
 560                 dim->n_name = dim->nparam + dim->n_in + dim->n_out + n;
 561         }
 562         switch (type) {
 563         case isl_dim_param:     dim->nparam += n; break;
 564         case isl_dim_in:        dim->n_in += n; break;
 565         case isl_dim_out:       dim->n_out += n; break;
 566         }
 567         dim = isl_dim_reset(dim, type);
 568
 569         return dim;
 570 error:
 571         isl_dim_free(dim);
 572         return NULL;
 573 }
 574
 575 __isl_give isl_dim *isl_dim_move(__isl_take isl_dim *dim,
 576         enum isl_dim_type dst_type, unsigned dst_pos,
 577         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
 578 {
 579         int i;
 580
 581         if (!dim)
 582                 return NULL;
 583         if (n == 0)
 584                 return dim;
 585
 586         isl_assert(dim->ctx, src_pos + n <= isl_dim_size(dim, src_type),
 587                 goto error);
 588
 589         if (dst_type == src_type && dst_pos == src_pos)
 590                 return dim;
 591
 592         isl_assert(dim->ctx, dst_type != src_type, goto error);
 593
 594         dim = isl_dim_reset(dim, src_type);
 595         dim = isl_dim_reset(dim, dst_type);
 596
 597         dim = isl_dim_cow(dim);
 598         if (!dim)
 599                 return NULL;
 600
 601         if (dim->names) {
 602                 struct isl_name **names;
 603                 enum isl_dim_type t;
 604                 int off;
 605                 int s[3];
 606                 int *size = s - isl_dim_param;
 607                 names = isl_calloc_array(dim->ctx, struct isl_name *,
 608                                          dim->nparam + dim->n_in + dim->n_out);
 609                 if (!names)
 610                         goto error;
 611                 off = 0;
 612                 size[isl_dim_param] = dim->nparam;
 613                 size[isl_dim_in] = dim->n_in;
 614                 size[isl_dim_out] = dim->n_out;
 615                 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
 616                         if (t == dst_type) {
 617                                 get_names(dim, t, 0, dst_pos, names + off);
 618                                 off += dst_pos;
 619                                 get_names(dim, src_type, src_pos, n, names+off);
 620                                 off += n;
 621                                 get_names(dim, t, dst_pos, size[t] - dst_pos,
 622                                                 names + off);
 623                                 off += size[t] - dst_pos;
 624                         } else if (t == src_type) {
 625                                 get_names(dim, t, 0, src_pos, names + off);
 626                                 off += src_pos;
 627                                 get_names(dim, t, src_pos + n,
 628                                             size[t] - src_pos - n, names + off);
 629                                 off += size[t] - src_pos - n;
 630                         } else {
 631                                 get_names(dim, t, 0, size[t], names + off);
 632                                 off += size[t];
 633                         }
 634                 }
 635                 free(dim->names);
 636                 dim->names = names;
 637                 dim->n_name = dim->nparam + dim->n_in + dim->n_out;
 638         }
 639
 640         switch (dst_type) {
 641         case isl_dim_param:     dim->nparam += n; break;
 642         case isl_dim_in:        dim->n_in += n; break;
 643         case isl_dim_out:       dim->n_out += n; break;
 644         }
 645
 646         switch (src_type) {
 647         case isl_dim_param:     dim->nparam -= n; break;
 648         case isl_dim_in:        dim->n_in -= n; break;
 649         case isl_dim_out:       dim->n_out -= n; break;
 650         }
 651
 652         if (dst_type != isl_dim_param && src_type != isl_dim_param)
 653                 return dim;
 654
 655         for (i = 0; i < 2; ++i) {
 656                 if (!dim->nested[i])
 657                         continue;
 658                 dim->nested[i] = isl_dim_replace(dim->nested[i],
 659                                                  isl_dim_param, dim);
 660                 if (!dim->nested[i])
 661                         goto error;
 662         }
 663
 664         return dim;
 665 error:
 666         isl_dim_free(dim);
 667         return NULL;
 668 }
 669
 670 struct isl_dim *isl_dim_join(struct isl_dim *left, struct isl_dim *right)
 671 {
 672         struct isl_dim *dim;
 673
 674         if (!left || !right)
 675                 goto error;
 676
 677         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
 678                         goto error);
 679         isl_assert(left->ctx,
 680                 isl_dim_tuple_match(left, isl_dim_out, right, isl_dim_in),
 681                 goto error);
 682
 683         dim = isl_dim_alloc(left->ctx, left->nparam, left->n_in, right->n_out);
 684         if (!dim)
 685                 goto error;
 686
 687         dim = copy_names(dim, isl_dim_param, 0, left, isl_dim_param);
 688         dim = copy_names(dim, isl_dim_in, 0, left, isl_dim_in);
 689         dim = copy_names(dim, isl_dim_out, 0, right, isl_dim_out);
 690
 691         if (dim && left->tuple_name[0] &&
 692             !(dim->tuple_name[0] = isl_name_copy(dim->ctx, left->tuple_name[0])))
 693                 goto error;
 694         if (dim && right->tuple_name[1] &&
 695             !(dim->tuple_name[1] = isl_name_copy(dim->ctx, right->tuple_name[1])))
 696                 goto error;
 697         if (dim && left->nested[0] &&
 698             !(dim->nested[0] = isl_dim_copy(left->nested[0])))
 699                 goto error;
 700         if (dim && right->nested[1] &&
 701             !(dim->nested[1] = isl_dim_copy(right->nested[1])))
 702                 goto error;
 703
 704         isl_dim_free(left);
 705         isl_dim_free(right);
 706
 707         return dim;
 708 error:
 709         isl_dim_free(left);
 710         isl_dim_free(right);
 711         return NULL;
 712 }
 713
 714 struct isl_dim *isl_dim_product(struct isl_dim *left, struct isl_dim *right)
 715 {
 716         isl_dim *dom1, *dom2, *nest1, *nest2;
 717
 718         if (!left || !right)
 719                 goto error;
 720
 721         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
 722                         goto error);
 723
 724         dom1 = isl_dim_domain(isl_dim_copy(left));
 725         dom2 = isl_dim_domain(isl_dim_copy(right));
 726         nest1 = isl_dim_wrap(isl_dim_join(isl_dim_reverse(dom1), dom2));
 727
 728         dom1 = isl_dim_range(left);
 729         dom2 = isl_dim_range(right);
 730         nest2 = isl_dim_wrap(isl_dim_join(isl_dim_reverse(dom1), dom2));
 731
 732         return isl_dim_join(isl_dim_reverse(nest1), nest2);
 733 error:
 734         isl_dim_free(left);
 735         isl_dim_free(right);
 736         return NULL;
 737 }
 738
 739 __isl_give isl_dim *isl_dim_range_product(__isl_take isl_dim *left,
 740         __isl_take isl_dim *right)
 741 {
 742         isl_dim *dom, *ran1, *ran2, *nest;
 743
 744         if (!left || !right)
 745                 goto error;
 746
 747         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
 748                         goto error);
 749         if (!isl_dim_match(left, isl_dim_in, right, isl_dim_in))
 750                 isl_die(left->ctx, isl_error_invalid,
 751                         "domains need to match", goto error);
 752
 753         dom = isl_dim_domain(isl_dim_copy(left));
 754
 755         ran1 = isl_dim_range(left);
 756         ran2 = isl_dim_range(right);
 757         nest = isl_dim_wrap(isl_dim_join(isl_dim_reverse(ran1), ran2));
 758
 759         return isl_dim_join(isl_dim_reverse(dom), nest);
 760 error:
 761         isl_dim_free(left);
 762         isl_dim_free(right);
 763         return NULL;
 764 }
 765
 766 struct isl_dim *isl_dim_map(struct isl_dim *dim)
 767 {
 768         struct isl_name **names = NULL;
 769
 770         if (!dim)
 771                 return NULL;
 772         isl_assert(dim->ctx, dim->n_in == 0, goto error);
 773         if (dim->n_out == 0 && !isl_dim_is_named_or_nested(dim, isl_dim_out))
 774                 return dim;
 775         dim = isl_dim_cow(dim);
 776         if (!dim)
 777                 return NULL;
 778         if (dim->names) {
 779                 names = isl_calloc_array(dim->ctx, struct isl_name *,
 780                                         dim->nparam + dim->n_out + dim->n_out);
 781                 if (!names)
 782                         goto error;
 783                 get_names(dim, isl_dim_param, 0, dim->nparam, names);
 784                 get_names(dim, isl_dim_out, 0, dim->n_out, names + dim->nparam);
 785         }
 786         dim->n_in = dim->n_out;
 787         if (names) {
 788                 free(dim->names);
 789                 dim->names = names;
 790                 dim->n_name = dim->nparam + dim->n_out + dim->n_out;
 791                 dim = copy_names(dim, isl_dim_out, 0, dim, isl_dim_in);
 792         }
 793         isl_name_free(dim->ctx, dim->tuple_name[0]);
 794         dim->tuple_name[0] = isl_name_copy(dim->ctx, dim->tuple_name[1]);
 795         isl_dim_free(dim->nested[0]);
 796         dim->nested[0] = isl_dim_copy(dim->nested[1]);
 797         return dim;
 798 error:
 799         isl_dim_free(dim);
 800         return NULL;
 801 }
 802
 803 static struct isl_dim *set_names(struct isl_dim *dim, enum isl_dim_type type,
 804         unsigned first, unsigned n, struct isl_name **names)
 805 {
 806         int i;
 807
 808         for (i = 0; i < n ; ++i)
 809                 dim = set_name(dim, type, first+i, names[i]);
 810
 811         return dim;
 812 }
 813
 814 struct isl_dim *isl_dim_reverse(struct isl_dim *dim)
 815 {
 816         unsigned t;
 817         isl_dim *nested;
 818         struct isl_name **names = NULL;
 819         struct isl_name *name;
 820
 821         if (!dim)
 822                 return NULL;
 823         if (match(dim, isl_dim_in, dim, isl_dim_out))
 824                 return dim;
 825
 826         dim = isl_dim_cow(dim);
 827         if (!dim)
 828                 return NULL;
 829
 830         name = dim->tuple_name[0];
 831         dim->tuple_name[0] = dim->tuple_name[1];
 832         dim->tuple_name[1] = name;
 833
 834         nested = dim->nested[0];
 835         dim->nested[0] = dim->nested[1];
 836         dim->nested[1] = nested;
 837
 838         if (dim->names) {
 839                 names = isl_alloc_array(dim->ctx, struct isl_name *,
 840                                         dim->n_in + dim->n_out);
 841                 if (!names)
 842                         goto error;
 843                 get_names(dim, isl_dim_in, 0, dim->n_in, names);
 844                 get_names(dim, isl_dim_out, 0, dim->n_out, names + dim->n_in);
 845         }
 846
 847         t = dim->n_in;
 848         dim->n_in = dim->n_out;
 849         dim->n_out = t;
 850
 851         if (dim->names) {
 852                 dim = set_names(dim, isl_dim_out, 0, dim->n_out, names);
 853                 dim = set_names(dim, isl_dim_in, 0, dim->n_in, names + dim->n_out);
 854                 free(names);
 855         }
 856
 857         return dim;
 858 error:
 859         free(names);
 860         isl_dim_free(dim);
 861         return NULL;
 862 }
 863
 864 struct isl_dim *isl_dim_drop(struct isl_dim *dim, enum isl_dim_type type,
 865                 unsigned first, unsigned num)
 866 {
 867         int i;
 868
 869         if (!dim)
 870                 return NULL;
 871
 872         if (n == 0)
 873                 return isl_dim_reset(dim, type);
 874
 875         isl_assert(dim->ctx, first + num <= n(dim, type), goto error);
 876         dim = isl_dim_cow(dim);
 877         if (!dim)
 878                 goto error;
 879         if (dim->names) {
 880                 dim = extend_names(dim);
 881                 if (!dim)
 882                         goto error;
 883                 for (i = 0; i < num; ++i)
 884                         isl_name_free(dim->ctx, get_name(dim, type, first+i));
 885                 for (i = first+num; i < n(dim, type); ++i)
 886                         set_name(dim, type, i - num, get_name(dim, type, i));
 887                 switch (type) {
 888                 case isl_dim_param:
 889                         get_names(dim, isl_dim_in, 0, dim->n_in,
 890                                 dim->names + offset(dim, isl_dim_in) - num);
 891                 case isl_dim_in:
 892                         get_names(dim, isl_dim_out, 0, dim->n_out,
 893                                 dim->names + offset(dim, isl_dim_out) - num);
 894                 case isl_dim_out:
 895                         ;
 896                 }
 897                 dim->n_name -= num;
 898         }
 899         switch (type) {
 900         case isl_dim_param:     dim->nparam -= num; break;
 901         case isl_dim_in:        dim->n_in -= num; break;
 902         case isl_dim_out:       dim->n_out -= num; break;
 903         }
 904         dim = isl_dim_reset(dim, type);
 905         if (type == isl_dim_param) {
 906                 if (dim && dim->nested[0] &&
 907                     !(dim->nested[0] = isl_dim_drop(dim->nested[0],
 908                                                     isl_dim_param, first, num)))
 909                         goto error;
 910                 if (dim && dim->nested[1] &&
 911                     !(dim->nested[1] = isl_dim_drop(dim->nested[1],
 912                                                     isl_dim_param, first, num)))
 913                         goto error;
 914         }
 915         return dim;
 916 error:
 917         isl_dim_free(dim);
 918         return NULL;
 919 }
 920
 921 struct isl_dim *isl_dim_drop_inputs(struct isl_dim *dim,
 922                 unsigned first, unsigned n)
 923 {
 924         if (!dim)
 925                 return NULL;
 926         return isl_dim_drop(dim, isl_dim_in, first, n);
 927 }
 928
 929 struct isl_dim *isl_dim_drop_outputs(struct isl_dim *dim,
 930                 unsigned first, unsigned n)
 931 {
 932         if (!dim)
 933                 return NULL;
 934         return isl_dim_drop(dim, isl_dim_out, first, n);
 935 }
 936
 937 struct isl_dim *isl_dim_domain(struct isl_dim *dim)
 938 {
 939         if (!dim)
 940                 return NULL;
 941         dim = isl_dim_drop_outputs(dim, 0, dim->n_out);
 942         return isl_dim_reverse(dim);
 943 }
 944
 945 __isl_give isl_dim *isl_dim_from_domain(__isl_take isl_dim *dim)
 946 {
 947         return isl_dim_reverse(dim);
 948 }
 949
 950 struct isl_dim *isl_dim_range(struct isl_dim *dim)
 951 {
 952         if (!dim)
 953                 return NULL;
 954         return isl_dim_drop_inputs(dim, 0, dim->n_in);
 955 }
 956
 957 __isl_give isl_dim *isl_dim_from_range(__isl_take isl_dim *dim)
 958 {
 959         return dim;
 960 }
 961
 962 __isl_give isl_dim *isl_dim_as_set_dim(__isl_take isl_dim *dim)
 963 {
 964         dim = isl_dim_cow(dim);
 965         if (!dim)
 966                 return NULL;
 967
 968         dim->n_out += dim->n_in;
 969         dim->n_in = 0;
 970         dim = isl_dim_reset(dim, isl_dim_in);
 971         dim = isl_dim_reset(dim, isl_dim_out);
 972
 973         return dim;
 974 }
 975
 976 struct isl_dim *isl_dim_underlying(struct isl_dim *dim, unsigned n_div)
 977 {
 978         int i;
 979
 980         if (!dim)
 981                 return NULL;
 982         if (n_div == 0 &&
 983             dim->nparam == 0 && dim->n_in == 0 && dim->n_name == 0)
 984                 return isl_dim_reset(isl_dim_reset(dim, isl_dim_in), isl_dim_out);
 985         dim = isl_dim_cow(dim);
 986         if (!dim)
 987                 return NULL;
 988         dim->n_out += dim->nparam + dim->n_in + n_div;
 989         dim->nparam = 0;
 990         dim->n_in = 0;
 991
 992         for (i = 0; i < dim->n_name; ++i)
 993                 isl_name_free(dim->ctx, get_name(dim, isl_dim_out, i));
 994         dim->n_name = 0;
 995         dim = isl_dim_reset(dim, isl_dim_in);
 996         dim = isl_dim_reset(dim, isl_dim_out);
 997
 998         return dim;
 999 }
1000
1001 unsigned isl_dim_total(struct isl_dim *dim)
1002 {
1003         return dim ? dim->nparam + dim->n_in + dim->n_out : 0;
1004 }
1005
1006 int isl_dim_equal(struct isl_dim *dim1, struct isl_dim *dim2)
1007 {
1008         return match(dim1, isl_dim_param, dim2, isl_dim_param) &&
1009                isl_dim_tuple_match(dim1, isl_dim_in, dim2, isl_dim_in) &&
1010                isl_dim_tuple_match(dim1, isl_dim_out, dim2, isl_dim_out);
1011 }
1012
1013 int isl_dim_compatible(struct isl_dim *dim1, struct isl_dim *dim2)
1014 {
1015         return dim1->nparam == dim2->nparam &&
1016                dim1->n_in + dim1->n_out == dim2->n_in + dim2->n_out;
1017 }
1018
1019 static uint32_t isl_hash_dim(uint32_t hash, __isl_keep isl_dim *dim)
1020 {
1021         int i;
1022         struct isl_name *name;
1023
1024         if (!dim)
1025                 return hash;
1026
1027         hash = isl_hash_builtin(hash, dim->nparam);
1028         hash = isl_hash_builtin(hash, dim->n_in);
1029         hash = isl_hash_builtin(hash, dim->n_out);
1030
1031         for (i = 0; i < dim->nparam; ++i) {
1032                 name = get_name(dim, isl_dim_param, i);
1033                 hash = isl_hash_name(hash, name);
1034         }
1035
1036         name = tuple_name(dim, isl_dim_in);
1037         hash = isl_hash_name(hash, name);
1038         name = tuple_name(dim, isl_dim_out);
1039         hash = isl_hash_name(hash, name);
1040
1041         hash = isl_hash_dim(hash, dim->nested[0]);
1042         hash = isl_hash_dim(hash, dim->nested[1]);
1043
1044         return hash;
1045 }
1046
1047 uint32_t isl_dim_get_hash(__isl_keep isl_dim *dim)
1048 {
1049         uint32_t hash;
1050
1051         if (!dim)
1052                 return 0;
1053
1054         hash = isl_hash_init();
1055         hash = isl_hash_dim(hash, dim);
1056
1057         return hash;
1058 }
1059
1060 int isl_dim_is_wrapping(__isl_keep isl_dim *dim)
1061 {
1062         if (!dim)
1063                 return -1;
1064
1065         if (dim->n_in != 0 || dim->tuple_name[0] || dim->nested[0])
1066                 return 0;
1067
1068         return dim->nested[1] != NULL;
1069 }
1070
1071 __isl_give isl_dim *isl_dim_wrap(__isl_take isl_dim *dim)
1072 {
1073         isl_dim *wrap;
1074
1075         if (!dim)
1076                 return NULL;
1077
1078         wrap = isl_dim_alloc(dim->ctx, dim->nparam, 0, dim->n_in + dim->n_out);
1079
1080         wrap = copy_names(wrap, isl_dim_param, 0, dim, isl_dim_param);
1081         wrap = copy_names(wrap, isl_dim_set, 0, dim, isl_dim_in);
1082         wrap = copy_names(wrap, isl_dim_set, dim->n_in, dim, isl_dim_out);
1083
1084         if (!wrap)
1085                 goto error;
1086
1087         wrap->nested[1] = dim;
1088
1089         return wrap;
1090 error:
1091         isl_dim_free(dim);
1092         return NULL;
1093 }
1094
1095 __isl_give isl_dim *isl_dim_unwrap(__isl_take isl_dim *dim)
1096 {
1097         isl_dim *unwrap;
1098
1099         if (!dim)
1100                 return NULL;
1101
1102         if (!isl_dim_is_wrapping(dim))
1103                 isl_die(dim->ctx, isl_error_invalid, "not a wrapping dim",
1104                         goto error);
1105
1106         unwrap = isl_dim_copy(dim->nested[1]);
1107         isl_dim_free(dim);
1108
1109         return unwrap;
1110 error:
1111         isl_dim_free(dim);
1112         return NULL;
1113 }
1114
1115 int isl_dim_is_named_or_nested(__isl_keep isl_dim *dim, enum isl_dim_type type)
1116 {
1117         if (type != isl_dim_in && type != isl_dim_out)
1118                 return 0;
1119         if (!dim)
1120                 return -1;
1121         if (dim->tuple_name[type - isl_dim_in])
1122                 return 1;
1123         if (dim->nested[type - isl_dim_in])
1124                 return 1;
1125         return 0;
1126 }
1127
1128 __isl_give isl_dim *isl_dim_reset(__isl_take isl_dim *dim,
1129         enum isl_dim_type type)
1130 {
1131         if (!isl_dim_is_named_or_nested(dim, type))
1132                 return dim;
1133
1134         dim = isl_dim_cow(dim);
1135         if (!dim)
1136                 return NULL;
1137
1138         isl_name_free(dim->ctx, dim->tuple_name[type - isl_dim_in]);
1139         dim->tuple_name[type - isl_dim_in] = NULL;
1140         isl_dim_free(dim->nested[type - isl_dim_in]);
1141         dim->nested[type - isl_dim_in] = NULL;
1142
1143         return dim;
1144 }
1145
1146 __isl_give isl_dim *isl_dim_flatten(__isl_take isl_dim *dim)
1147 {
1148         if (!dim)
1149                 return NULL;
1150         if (!dim->nested[0] && !dim->nested[1])
1151                 return dim;
1152
1153         if (dim->nested[0])
1154                 dim = isl_dim_reset(dim, isl_dim_in);
1155         if (dim && dim->nested[1])
1156                 dim = isl_dim_reset(dim, isl_dim_out);
1157
1158         return dim;
1159 }
1160
1161 /* Replace the dimensions of the given type of dst by those of src.
1162  */
1163 __isl_give isl_dim *isl_dim_replace(__isl_take isl_dim *dst,
1164         enum isl_dim_type type, __isl_keep isl_dim *src)
1165 {
1166         dst = isl_dim_cow(dst);
1167
1168         if (!dst || !src)
1169                 goto error;
1170
1171         dst = isl_dim_drop(dst, type, 0, isl_dim_size(dst, type));
1172         dst = isl_dim_add(dst, type, isl_dim_size(src, type));
1173         dst = copy_names(dst, type, 0, src, type);
1174
1175         if (dst && type == isl_dim_param) {
1176                 int i;
1177                 for (i = 0; i <= 1; ++i) {
1178                         if (!dst->nested[i])
1179                                 continue;
1180                         dst->nested[i] = isl_dim_replace(dst->nested[i],
1181                                                          type, src);
1182                         if (!dst->nested[i])
1183                                 goto error;
1184                 }
1185         }
1186
1187         return dst;
1188 error:
1189         isl_dim_free(dst);
1190         return NULL;
1191 }