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         name = isl_name_get(dim->ctx, s);
 349         if (!name)
 350                 goto error;
 351         return set_name(dim, type, pos, name);
 352 error:
 353         isl_dim_free(dim);
 354         return NULL;
 355 }
 356
 357 const char *isl_dim_get_name(struct isl_dim *dim,
 358                                  enum isl_dim_type type, unsigned pos)
 359 {
 360         struct isl_name *name = get_name(dim, type, pos);
 361         return name ? name->name : NULL;
 362 }
 363
 364 static struct isl_name *tuple_name(__isl_keep isl_dim *dim,
 365         enum isl_dim_type type)
 366 {
 367         if (!dim)
 368                 return NULL;
 369         if (type == isl_dim_in)
 370                 return dim->tuple_name[0];
 371         if (type == isl_dim_out)
 372                 return dim->tuple_name[1];
 373         return NULL;
 374 }
 375
 376 static __isl_keep isl_dim *nested(__isl_keep isl_dim *dim,
 377         enum isl_dim_type type)
 378 {
 379         if (!dim)
 380                 return NULL;
 381         if (type == isl_dim_in)
 382                 return dim->nested[0];
 383         if (type == isl_dim_out)
 384                 return dim->nested[1];
 385         return NULL;
 386 }
 387
 388 int isl_dim_tuple_match(__isl_keep isl_dim *dim1, enum isl_dim_type dim1_type,
 389                         __isl_keep isl_dim *dim2, enum isl_dim_type dim2_type)
 390 {
 391         struct isl_name *name1, *name2;
 392         isl_dim *nested1, *nested2;
 393
 394         if (n(dim1, dim1_type) != n(dim2, dim2_type))
 395                 return 0;
 396         name1 = tuple_name(dim1, dim1_type);
 397         name2 = tuple_name(dim2, dim2_type);
 398         if (!name1 ^ !name2)
 399                 return 0;
 400         if (name1 && name1->name != name2->name)
 401                 return 0;
 402         nested1 = nested(dim1, dim1_type);
 403         nested2 = nested(dim2, dim2_type);
 404         if (!nested1 ^ !nested2)
 405                 return 0;
 406         if (nested1 && !isl_dim_equal(nested1, nested2))
 407                 return 0;
 408         return 1;
 409 }
 410
 411 static int match(struct isl_dim *dim1, enum isl_dim_type dim1_type,
 412                 struct isl_dim *dim2, enum isl_dim_type dim2_type)
 413 {
 414         int i;
 415
 416         if (!isl_dim_tuple_match(dim1, dim1_type, dim2, dim2_type))
 417                 return 0;
 418
 419         if (!dim1->names && !dim2->names)
 420                 return 1;
 421
 422         for (i = 0; i < n(dim1, dim1_type); ++i) {
 423                 if (get_name(dim1, dim1_type, i) !=
 424                     get_name(dim2, dim2_type, i))
 425                         return 0;
 426         }
 427         return 1;
 428 }
 429
 430 int isl_dim_match(struct isl_dim *dim1, enum isl_dim_type dim1_type,
 431                 struct isl_dim *dim2, enum isl_dim_type dim2_type)
 432 {
 433         return match(dim1, dim1_type, dim2, dim2_type);
 434 }
 435
 436 static void get_names(struct isl_dim *dim, enum isl_dim_type type,
 437         unsigned first, unsigned n, struct isl_name **names)
 438 {
 439         int i;
 440
 441         for (i = 0; i < n ; ++i)
 442                 names[i] = get_name(dim, type, first+i);
 443 }
 444
 445 struct isl_dim *isl_dim_extend(struct isl_dim *dim,
 446                         unsigned nparam, unsigned n_in, unsigned n_out)
 447 {
 448         struct isl_name **names = NULL;
 449
 450         if (!dim)
 451                 return NULL;
 452         if (dim->nparam == nparam && dim->n_in == n_in && dim->n_out == n_out)
 453                 return dim;
 454
 455         isl_assert(dim->ctx, dim->nparam <= nparam, goto error);
 456         isl_assert(dim->ctx, dim->n_in <= n_in, goto error);
 457         isl_assert(dim->ctx, dim->n_out <= n_out, goto error);
 458
 459         dim = isl_dim_cow(dim);
 460
 461         if (dim->names) {
 462                 names = isl_calloc_array(dim->ctx, struct isl_name *,
 463                                          nparam + n_in + n_out);
 464                 if (!names)
 465                         goto error;
 466                 get_names(dim, isl_dim_param, 0, dim->nparam, names);
 467                 get_names(dim, isl_dim_in, 0, dim->n_in, names + nparam);
 468                 get_names(dim, isl_dim_out, 0, dim->n_out,
 469                                 names + nparam + n_in);
 470                 free(dim->names);
 471                 dim->names = names;
 472                 dim->n_name = nparam + n_in + n_out;
 473         }
 474         dim->nparam = nparam;
 475         dim->n_in = n_in;
 476         dim->n_out = n_out;
 477
 478         return dim;
 479 error:
 480         free(names);
 481         isl_dim_free(dim);
 482         return NULL;
 483 }
 484
 485 struct isl_dim *isl_dim_add(struct isl_dim *dim, enum isl_dim_type type,
 486         unsigned n)
 487 {
 488         if (!dim)
 489                 return NULL;
 490         dim = isl_dim_reset(dim, type);
 491         switch (type) {
 492         case isl_dim_param:
 493                 dim = isl_dim_extend(dim,
 494                                         dim->nparam + n, dim->n_in, dim->n_out);
 495                 if (dim && dim->nested[0] &&
 496                     !(dim->nested[0] = isl_dim_add(dim->nested[0],
 497                                                     isl_dim_param, n)))
 498                         goto error;
 499                 if (dim && dim->nested[1] &&
 500                     !(dim->nested[1] = isl_dim_add(dim->nested[1],
 501                                                     isl_dim_param, n)))
 502                         goto error;
 503                 return dim;
 504         case isl_dim_in:
 505                 return isl_dim_extend(dim,
 506                                         dim->nparam, dim->n_in + n, dim->n_out);
 507         case isl_dim_out:
 508                 return isl_dim_extend(dim,
 509                                         dim->nparam, dim->n_in, dim->n_out + n);
 510         }
 511         return dim;
 512 error:
 513         isl_dim_free(dim);
 514         return NULL;
 515 }
 516
 517 __isl_give isl_dim *isl_dim_insert(__isl_take isl_dim *dim,
 518         enum isl_dim_type type, unsigned pos, unsigned n)
 519 {
 520         struct isl_name **names = NULL;
 521
 522         if (!dim)
 523                 return NULL;
 524         if (n == 0)
 525                 return isl_dim_reset(dim, type);
 526
 527         isl_assert(dim->ctx, pos <= isl_dim_size(dim, type), goto error);
 528
 529         dim = isl_dim_cow(dim);
 530         if (!dim)
 531                 return NULL;
 532
 533         if (dim->names) {
 534                 enum isl_dim_type t;
 535                 int off;
 536                 int s[3];
 537                 int *size = s - isl_dim_param;
 538                 names = isl_calloc_array(dim->ctx, struct isl_name *,
 539                                      dim->nparam + dim->n_in + dim->n_out + n);
 540                 if (!names)
 541                         goto error;
 542                 off = 0;
 543                 size[isl_dim_param] = dim->nparam;
 544                 size[isl_dim_in] = dim->n_in;
 545                 size[isl_dim_out] = dim->n_out;
 546                 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
 547                         if (t != type) {
 548                                 get_names(dim, t, 0, size[t], names + off);
 549                                 off += size[t];
 550                         } else {
 551                                 get_names(dim, t, 0, pos, names + off);
 552                                 off += pos + n;
 553                                 get_names(dim, t, pos, size[t]-pos, names+off);
 554                                 off += size[t] - pos;
 555                         }
 556                 }
 557                 free(dim->names);
 558                 dim->names = names;
 559                 dim->n_name = dim->nparam + dim->n_in + dim->n_out + n;
 560         }
 561         switch (type) {
 562         case isl_dim_param:     dim->nparam += n; break;
 563         case isl_dim_in:        dim->n_in += n; break;
 564         case isl_dim_out:       dim->n_out += n; break;
 565         }
 566         dim = isl_dim_reset(dim, type);
 567
 568         return dim;
 569 error:
 570         isl_dim_free(dim);
 571         return NULL;
 572 }
 573
 574 __isl_give isl_dim *isl_dim_move(__isl_take isl_dim *dim,
 575         enum isl_dim_type dst_type, unsigned dst_pos,
 576         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
 577 {
 578         if (!dim)
 579                 return NULL;
 580         if (n == 0)
 581                 return dim;
 582
 583         isl_assert(dim->ctx, src_pos + n <= isl_dim_size(dim, src_type),
 584                 goto error);
 585
 586         if (dst_type == src_type && dst_pos == src_pos)
 587                 return dim;
 588
 589         isl_assert(dim->ctx, dst_type != src_type, goto error);
 590
 591         dim = isl_dim_reset(dim, src_type);
 592         dim = isl_dim_reset(dim, dst_type);
 593
 594         dim = isl_dim_cow(dim);
 595         if (!dim)
 596                 return NULL;
 597
 598         if (dim->names) {
 599                 struct isl_name **names;
 600                 enum isl_dim_type t;
 601                 int off;
 602                 int s[3];
 603                 int *size = s - isl_dim_param;
 604                 names = isl_calloc_array(dim->ctx, struct isl_name *,
 605                                          dim->nparam + dim->n_in + dim->n_out);
 606                 if (!names)
 607                         goto error;
 608                 off = 0;
 609                 size[isl_dim_param] = dim->nparam;
 610                 size[isl_dim_in] = dim->n_in;
 611                 size[isl_dim_out] = dim->n_out;
 612                 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
 613                         if (t == dst_type) {
 614                                 get_names(dim, t, 0, dst_pos, names + off);
 615                                 off += dst_pos;
 616                                 get_names(dim, src_type, src_pos, n, names+off);
 617                                 off += n;
 618                                 get_names(dim, t, dst_pos, size[t] - dst_pos,
 619                                                 names + off);
 620                                 off += size[t] - dst_pos;
 621                         } else if (t == src_type) {
 622                                 get_names(dim, t, 0, src_pos, names + off);
 623                                 off += src_pos;
 624                                 get_names(dim, t, src_pos + n,
 625                                             size[t] - src_pos - n, names + off);
 626                                 off += size[t] - src_pos - n;
 627                         } else {
 628                                 get_names(dim, t, 0, size[t], names + off);
 629                                 off += size[t];
 630                         }
 631                 }
 632                 free(dim->names);
 633                 dim->names = names;
 634                 dim->n_name = dim->nparam + dim->n_in + dim->n_out;
 635         }
 636
 637         switch (dst_type) {
 638         case isl_dim_param:     dim->nparam += n; break;
 639         case isl_dim_in:        dim->n_in += n; break;
 640         case isl_dim_out:       dim->n_out += n; break;
 641         }
 642
 643         switch (src_type) {
 644         case isl_dim_param:     dim->nparam -= n; break;
 645         case isl_dim_in:        dim->n_in -= n; break;
 646         case isl_dim_out:       dim->n_out -= n; break;
 647         }
 648
 649         return dim;
 650 error:
 651         isl_dim_free(dim);
 652         return NULL;
 653 }
 654
 655 struct isl_dim *isl_dim_join(struct isl_dim *left, struct isl_dim *right)
 656 {
 657         struct isl_dim *dim;
 658
 659         if (!left || !right)
 660                 goto error;
 661
 662         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
 663                         goto error);
 664         isl_assert(left->ctx,
 665                 isl_dim_tuple_match(left, isl_dim_out, right, isl_dim_in),
 666                 goto error);
 667
 668         dim = isl_dim_alloc(left->ctx, left->nparam, left->n_in, right->n_out);
 669         if (!dim)
 670                 goto error;
 671
 672         dim = copy_names(dim, isl_dim_param, 0, left, isl_dim_param);
 673         dim = copy_names(dim, isl_dim_in, 0, left, isl_dim_in);
 674         dim = copy_names(dim, isl_dim_out, 0, right, isl_dim_out);
 675
 676         if (dim && left->tuple_name[0] &&
 677             !(dim->tuple_name[0] = isl_name_copy(dim->ctx, left->tuple_name[0])))
 678                 goto error;
 679         if (dim && right->tuple_name[1] &&
 680             !(dim->tuple_name[1] = isl_name_copy(dim->ctx, right->tuple_name[1])))
 681                 goto error;
 682         if (dim && left->nested[0] &&
 683             !(dim->nested[0] = isl_dim_copy(left->nested[0])))
 684                 goto error;
 685         if (dim && right->nested[1] &&
 686             !(dim->nested[1] = isl_dim_copy(right->nested[1])))
 687                 goto error;
 688
 689         isl_dim_free(left);
 690         isl_dim_free(right);
 691
 692         return dim;
 693 error:
 694         isl_dim_free(left);
 695         isl_dim_free(right);
 696         return NULL;
 697 }
 698
 699 struct isl_dim *isl_dim_product(struct isl_dim *left, struct isl_dim *right)
 700 {
 701         isl_dim *dom1, *dom2, *nest1, *nest2;
 702
 703         if (!left || !right)
 704                 goto error;
 705
 706         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
 707                         goto error);
 708
 709         dom1 = isl_dim_domain(isl_dim_copy(left));
 710         dom2 = isl_dim_domain(isl_dim_copy(right));
 711         nest1 = isl_dim_wrap(isl_dim_join(isl_dim_reverse(dom1), dom2));
 712
 713         dom1 = isl_dim_range(left);
 714         dom2 = isl_dim_range(right);
 715         nest2 = isl_dim_wrap(isl_dim_join(isl_dim_reverse(dom1), dom2));
 716
 717         return isl_dim_join(isl_dim_reverse(nest1), nest2);
 718 error:
 719         isl_dim_free(left);
 720         isl_dim_free(right);
 721         return NULL;
 722 }
 723
 724 struct isl_dim *isl_dim_map(struct isl_dim *dim)
 725 {
 726         struct isl_name **names = NULL;
 727
 728         if (!dim)
 729                 return NULL;
 730         isl_assert(dim->ctx, dim->n_in == 0, goto error);
 731         if (dim->n_out == 0 && !isl_dim_is_named_or_nested(dim, isl_dim_out))
 732                 return dim;
 733         dim = isl_dim_cow(dim);
 734         if (!dim)
 735                 return NULL;
 736         if (dim->names) {
 737                 names = isl_calloc_array(dim->ctx, struct isl_name *,
 738                                         dim->nparam + dim->n_out + dim->n_out);
 739                 if (!names)
 740                         goto error;
 741                 get_names(dim, isl_dim_param, 0, dim->nparam, names);
 742                 get_names(dim, isl_dim_out, 0, dim->n_out, names + dim->nparam);
 743         }
 744         dim->n_in = dim->n_out;
 745         if (names) {
 746                 free(dim->names);
 747                 dim->names = names;
 748                 dim->n_name = dim->nparam + dim->n_out + dim->n_out;
 749                 dim = copy_names(dim, isl_dim_out, 0, dim, isl_dim_in);
 750         }
 751         isl_name_free(dim->ctx, dim->tuple_name[0]);
 752         dim->tuple_name[0] = isl_name_copy(dim->ctx, dim->tuple_name[1]);
 753         isl_dim_free(dim->nested[0]);
 754         dim->nested[0] = isl_dim_copy(dim->nested[1]);
 755         return dim;
 756 error:
 757         isl_dim_free(dim);
 758         return NULL;
 759 }
 760
 761 static struct isl_dim *set_names(struct isl_dim *dim, enum isl_dim_type type,
 762         unsigned first, unsigned n, struct isl_name **names)
 763 {
 764         int i;
 765
 766         for (i = 0; i < n ; ++i)
 767                 dim = set_name(dim, type, first+i, names[i]);
 768
 769         return dim;
 770 }
 771
 772 struct isl_dim *isl_dim_reverse(struct isl_dim *dim)
 773 {
 774         unsigned t;
 775         isl_dim *nested;
 776         struct isl_name **names = NULL;
 777         struct isl_name *name;
 778
 779         if (!dim)
 780                 return NULL;
 781         if (match(dim, isl_dim_in, dim, isl_dim_out))
 782                 return dim;
 783
 784         dim = isl_dim_cow(dim);
 785         if (!dim)
 786                 return NULL;
 787
 788         name = dim->tuple_name[0];
 789         dim->tuple_name[0] = dim->tuple_name[1];
 790         dim->tuple_name[1] = name;
 791
 792         nested = dim->nested[0];
 793         dim->nested[0] = dim->nested[1];
 794         dim->nested[1] = nested;
 795
 796         if (dim->names) {
 797                 names = isl_alloc_array(dim->ctx, struct isl_name *,
 798                                         dim->n_in + dim->n_out);
 799                 if (!names)
 800                         goto error;
 801                 get_names(dim, isl_dim_in, 0, dim->n_in, names);
 802                 get_names(dim, isl_dim_out, 0, dim->n_out, names + dim->n_in);
 803         }
 804
 805         t = dim->n_in;
 806         dim->n_in = dim->n_out;
 807         dim->n_out = t;
 808
 809         if (dim->names) {
 810                 dim = set_names(dim, isl_dim_out, 0, dim->n_out, names);
 811                 dim = set_names(dim, isl_dim_in, 0, dim->n_in, names + dim->n_out);
 812                 free(names);
 813         }
 814
 815         return dim;
 816 error:
 817         free(names);
 818         isl_dim_free(dim);
 819         return NULL;
 820 }
 821
 822 struct isl_dim *isl_dim_drop(struct isl_dim *dim, enum isl_dim_type type,
 823                 unsigned first, unsigned num)
 824 {
 825         int i;
 826
 827         if (!dim)
 828                 return NULL;
 829
 830         if (n == 0)
 831                 return isl_dim_reset(dim, type);
 832
 833         isl_assert(dim->ctx, first + num <= n(dim, type), goto error);
 834         dim = isl_dim_cow(dim);
 835         if (!dim)
 836                 goto error;
 837         if (dim->names) {
 838                 dim = extend_names(dim);
 839                 if (!dim)
 840                         goto error;
 841                 for (i = 0; i < num; ++i)
 842                         isl_name_free(dim->ctx, get_name(dim, type, first+i));
 843                 for (i = first+num; i < n(dim, type); ++i)
 844                         set_name(dim, type, i - num, get_name(dim, type, i));
 845                 switch (type) {
 846                 case isl_dim_param:
 847                         get_names(dim, isl_dim_in, 0, dim->n_in,
 848                                 dim->names + offset(dim, isl_dim_in) - num);
 849                 case isl_dim_in:
 850                         get_names(dim, isl_dim_out, 0, dim->n_out,
 851                                 dim->names + offset(dim, isl_dim_out) - num);
 852                 case isl_dim_out:
 853                         ;
 854                 }
 855                 dim->n_name -= num;
 856         }
 857         switch (type) {
 858         case isl_dim_param:     dim->nparam -= num; break;
 859         case isl_dim_in:        dim->n_in -= num; break;
 860         case isl_dim_out:       dim->n_out -= num; break;
 861         }
 862         dim = isl_dim_reset(dim, type);
 863         if (type == isl_dim_param) {
 864                 if (dim && dim->nested[0] &&
 865                     !(dim->nested[0] = isl_dim_drop(dim->nested[0],
 866                                                     isl_dim_param, first, num)))
 867                         goto error;
 868                 if (dim && dim->nested[1] &&
 869                     !(dim->nested[1] = isl_dim_drop(dim->nested[1],
 870                                                     isl_dim_param, first, num)))
 871                         goto error;
 872         }
 873         return dim;
 874 error:
 875         isl_dim_free(dim);
 876         return NULL;
 877 }
 878
 879 struct isl_dim *isl_dim_drop_inputs(struct isl_dim *dim,
 880                 unsigned first, unsigned n)
 881 {
 882         if (!dim)
 883                 return NULL;
 884         return isl_dim_drop(dim, isl_dim_in, first, n);
 885 }
 886
 887 struct isl_dim *isl_dim_drop_outputs(struct isl_dim *dim,
 888                 unsigned first, unsigned n)
 889 {
 890         if (!dim)
 891                 return NULL;
 892         return isl_dim_drop(dim, isl_dim_out, first, n);
 893 }
 894
 895 struct isl_dim *isl_dim_domain(struct isl_dim *dim)
 896 {
 897         if (!dim)
 898                 return NULL;
 899         dim = isl_dim_drop_outputs(dim, 0, dim->n_out);
 900         return isl_dim_reverse(dim);
 901 }
 902
 903 __isl_give isl_dim *isl_dim_from_domain(__isl_take isl_dim *dim)
 904 {
 905         return isl_dim_reverse(dim);
 906 }
 907
 908 struct isl_dim *isl_dim_range(struct isl_dim *dim)
 909 {
 910         if (!dim)
 911                 return NULL;
 912         return isl_dim_drop_inputs(dim, 0, dim->n_in);
 913 }
 914
 915 __isl_give isl_dim *isl_dim_from_range(__isl_take isl_dim *dim)
 916 {
 917         return dim;
 918 }
 919
 920 __isl_give isl_dim *isl_dim_as_set_dim(__isl_take isl_dim *dim)
 921 {
 922         dim = isl_dim_cow(dim);
 923         if (!dim)
 924                 return NULL;
 925
 926         dim->n_out += dim->n_in;
 927         dim->n_in = 0;
 928         dim = isl_dim_reset(dim, isl_dim_in);
 929         dim = isl_dim_reset(dim, isl_dim_out);
 930
 931         return dim;
 932 }
 933
 934 struct isl_dim *isl_dim_underlying(struct isl_dim *dim, unsigned n_div)
 935 {
 936         int i;
 937
 938         if (!dim)
 939                 return NULL;
 940         if (n_div == 0 &&
 941             dim->nparam == 0 && dim->n_in == 0 && dim->n_name == 0)
 942                 return isl_dim_reset(isl_dim_reset(dim, isl_dim_in), isl_dim_out);
 943         dim = isl_dim_cow(dim);
 944         if (!dim)
 945                 return NULL;
 946         dim->n_out += dim->nparam + dim->n_in + n_div;
 947         dim->nparam = 0;
 948         dim->n_in = 0;
 949
 950         for (i = 0; i < dim->n_name; ++i)
 951                 isl_name_free(dim->ctx, get_name(dim, isl_dim_out, i));
 952         dim->n_name = 0;
 953         dim = isl_dim_reset(dim, isl_dim_in);
 954         dim = isl_dim_reset(dim, isl_dim_out);
 955
 956         return dim;
 957 }
 958
 959 unsigned isl_dim_total(struct isl_dim *dim)
 960 {
 961         return dim ? dim->nparam + dim->n_in + dim->n_out : 0;
 962 }
 963
 964 int isl_dim_equal(struct isl_dim *dim1, struct isl_dim *dim2)
 965 {
 966         return match(dim1, isl_dim_param, dim2, isl_dim_param) &&
 967                isl_dim_tuple_match(dim1, isl_dim_in, dim2, isl_dim_in) &&
 968                isl_dim_tuple_match(dim1, isl_dim_out, dim2, isl_dim_out);
 969 }
 970
 971 int isl_dim_compatible(struct isl_dim *dim1, struct isl_dim *dim2)
 972 {
 973         return dim1->nparam == dim2->nparam &&
 974                dim1->n_in + dim1->n_out == dim2->n_in + dim2->n_out;
 975 }
 976
 977 static uint32_t isl_hash_dim(uint32_t hash, __isl_keep isl_dim *dim)
 978 {
 979         int i;
 980         struct isl_name *name;
 981
 982         if (!dim)
 983                 return hash;
 984
 985         hash = isl_hash_builtin(hash, dim->nparam);
 986         hash = isl_hash_builtin(hash, dim->n_in);
 987         hash = isl_hash_builtin(hash, dim->n_out);
 988
 989         for (i = 0; i < dim->nparam; ++i) {
 990                 name = get_name(dim, isl_dim_param, i);
 991                 hash = isl_hash_builtin(hash, name);
 992         }
 993
 994         name = tuple_name(dim, isl_dim_in);
 995         hash = isl_hash_builtin(hash, name);
 996         name = tuple_name(dim, isl_dim_out);
 997         hash = isl_hash_builtin(hash, name);
 998
 999         hash = isl_hash_dim(hash, dim->nested[0]);
1000         hash = isl_hash_dim(hash, dim->nested[1]);
1001
1002         return hash;
1003 }
1004
1005 uint32_t isl_dim_get_hash(__isl_keep isl_dim *dim)
1006 {
1007         uint32_t hash;
1008
1009         if (!dim)
1010                 return 0;
1011
1012         hash = isl_hash_init();
1013         hash = isl_hash_dim(hash, dim);
1014
1015         return hash;
1016 }
1017
1018 int isl_dim_is_wrapping(__isl_keep isl_dim *dim)
1019 {
1020         if (!dim)
1021                 return -1;
1022
1023         if (dim->n_in != 0 || dim->tuple_name[0] || dim->nested[0])
1024                 return 0;
1025
1026         return dim->nested[1] != NULL;
1027 }
1028
1029 __isl_give isl_dim *isl_dim_wrap(__isl_take isl_dim *dim)
1030 {
1031         isl_dim *wrap;
1032
1033         if (!dim)
1034                 return NULL;
1035
1036         wrap = isl_dim_alloc(dim->ctx, dim->nparam, 0, dim->n_in + dim->n_out);
1037
1038         wrap = copy_names(wrap, isl_dim_param, 0, dim, isl_dim_param);
1039         wrap = copy_names(wrap, isl_dim_set, 0, dim, isl_dim_in);
1040         wrap = copy_names(wrap, isl_dim_set, dim->n_in, dim, isl_dim_out);
1041
1042         if (!wrap)
1043                 goto error;
1044
1045         wrap->nested[1] = dim;
1046
1047         return wrap;
1048 error:
1049         isl_dim_free(dim);
1050         return NULL;
1051 }
1052
1053 __isl_give isl_dim *isl_dim_unwrap(__isl_take isl_dim *dim)
1054 {
1055         isl_dim *unwrap;
1056
1057         if (!dim)
1058                 return NULL;
1059
1060         if (!isl_dim_is_wrapping(dim))
1061                 isl_die(dim->ctx, isl_error_invalid, "not a wrapping dim",
1062                         goto error);
1063
1064         unwrap = isl_dim_copy(dim->nested[1]);
1065         isl_dim_free(dim);
1066
1067         return unwrap;
1068 error:
1069         isl_dim_free(dim);
1070         return NULL;
1071 }
1072
1073 int isl_dim_is_named_or_nested(__isl_keep isl_dim *dim, enum isl_dim_type type)
1074 {
1075         if (type != isl_dim_in && type != isl_dim_out)
1076                 return 0;
1077         if (!dim)
1078                 return -1;
1079         if (dim->tuple_name[type - isl_dim_in])
1080                 return 1;
1081         if (dim->nested[type - isl_dim_in])
1082                 return 1;
1083         return 0;
1084 }
1085
1086 __isl_give isl_dim *isl_dim_reset(__isl_take isl_dim *dim,
1087         enum isl_dim_type type)
1088 {
1089         if (!isl_dim_is_named_or_nested(dim, type))
1090                 return dim;
1091
1092         dim = isl_dim_cow(dim);
1093         if (!dim)
1094                 return NULL;
1095
1096         isl_name_free(dim->ctx, dim->tuple_name[type - isl_dim_in]);
1097         dim->tuple_name[type - isl_dim_in] = NULL;
1098         isl_dim_free(dim->nested[type - isl_dim_in]);
1099         dim->nested[type - isl_dim_in] = NULL;
1100
1101         return dim;
1102 }
1103
1104 __isl_give isl_dim *isl_dim_flatten(__isl_take isl_dim *dim)
1105 {
1106         if (!dim)
1107                 return NULL;
1108         if (!dim->nested[0] && !dim->nested[1])
1109                 return dim;
1110
1111         if (dim->nested[0])
1112                 dim = isl_dim_reset(dim, isl_dim_in);
1113         if (dim && dim->nested[1])
1114                 dim = isl_dim_reset(dim, isl_dim_out);
1115
1116         return dim;
1117 }
1118
1119 /* Replace the dimensions of the given type of dst by those of src.
1120  */
1121 __isl_give isl_dim *isl_dim_replace(__isl_take isl_dim *dst,
1122         enum isl_dim_type type, __isl_keep isl_dim *src)
1123 {
1124         dst = isl_dim_cow(dst);
1125
1126         if (!dst || !src)
1127                 goto error;
1128
1129         dst = isl_dim_drop(dst, type, 0, isl_dim_size(dst, type));
1130         dst = isl_dim_add(dst, type, isl_dim_size(src, type));
1131         dst = copy_names(dst, type, 0, src, type);
1132
1133         if (dst && type == isl_dim_param) {
1134                 int i;
1135                 for (i = 0; i <= 1; ++i) {
1136                         if (!dst->nested[i])
1137                                 continue;
1138                         dst->nested[i] = isl_dim_replace(dst->nested[i],
1139                                                          type, src);
1140                         if (!dst->nested[i])
1141                                 goto error;
1142                 }
1143         }
1144
1145         return dst;
1146 error:
1147         isl_dim_free(dst);
1148         return NULL;
1149 }