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