isl_dim.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  *
   4  * Use of this software is governed by the GNU LGPLv2.1 license
   5  *
   6  * Written by Sven Verdoolaege, K.U.Leuven, Departement
   7  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
   8  */
   9
  10 #include "isl_dim.h"
  11 #include "isl_name.h"
  12
  13 struct isl_dim *isl_dim_alloc(struct isl_ctx *ctx,
  14                         unsigned nparam, unsigned n_in, unsigned n_out)
  15 {
  16         struct isl_dim *dim;
  17
  18         dim = isl_alloc_type(ctx, struct isl_dim);
  19         if (!dim)
  20                 return NULL;
  21
  22         dim->ctx = ctx;
  23         isl_ctx_ref(ctx);
  24         dim->ref = 1;
  25         dim->nparam = nparam;
  26         dim->n_in = n_in;
  27         dim->n_out = n_out;
  28
  29         dim->n_name = 0;
  30         dim->names = NULL;
  31
  32         return dim;
  33 }
  34
  35 struct isl_dim *isl_dim_set_alloc(struct isl_ctx *ctx,
  36                         unsigned nparam, unsigned dim)
  37 {
  38         return isl_dim_alloc(ctx, nparam, 0, dim);
  39 }
  40
  41 static unsigned global_pos(struct isl_dim *dim,
  42                                  enum isl_dim_type type, unsigned pos)
  43 {
  44         struct isl_ctx *ctx = dim->ctx;
  45
  46         switch (type) {
  47         case isl_dim_param:
  48                 isl_assert(ctx, pos < dim->nparam, return isl_dim_total(dim));
  49                 return pos;
  50         case isl_dim_in:
  51                 isl_assert(ctx, pos < dim->n_in, return isl_dim_total(dim));
  52                 return pos + dim->nparam;
  53         case isl_dim_out:
  54                 isl_assert(ctx, pos < dim->n_out, return isl_dim_total(dim));
  55                 return pos + dim->nparam + dim->n_in;
  56         default:
  57                 isl_assert(ctx, 0, return isl_dim_total(dim));
  58         }
  59         return isl_dim_total(dim);
  60 }
  61
  62 static struct isl_dim *set_name(struct isl_dim *dim,
  63                                  enum isl_dim_type type, unsigned pos,
  64                                  struct isl_name *name)
  65 {
  66         struct isl_ctx *ctx = dim->ctx;
  67         dim = isl_dim_cow(dim);
  68
  69         if (!dim)
  70                 goto error;
  71
  72         pos = global_pos(dim, type, pos);
  73         isl_assert(ctx, pos != isl_dim_total(dim), goto error);
  74
  75         if (pos >= dim->n_name) {
  76                 if (!name)
  77                         return dim;
  78                 if (!dim->names) {
  79                         dim->names = isl_calloc_array(dim->ctx,
  80                                         struct isl_name *, isl_dim_total(dim));
  81                         if (!dim->names)
  82                                 goto error;
  83                 } else {
  84                         int i;
  85                         dim->names = isl_realloc_array(dim->ctx, dim->names,
  86                                         struct isl_name *, isl_dim_total(dim));
  87                         if (!dim->names)
  88                                 goto error;
  89                         for (i = dim->n_name; i < isl_dim_total(dim); ++i)
  90                                 dim->names[i] = NULL;
  91                 }
  92                 dim->n_name = isl_dim_total(dim);
  93         }
  94
  95         dim->names[pos] = name;
  96
  97         return dim;
  98 error:
  99         isl_name_free(ctx, name);
 100         isl_dim_free(dim);
 101         return NULL;
 102 }
 103
 104 static struct isl_name *get_name(struct isl_dim *dim,
 105                                  enum isl_dim_type type, unsigned pos)
 106 {
 107         if (!dim)
 108                 return NULL;
 109
 110         pos = global_pos(dim, type, pos);
 111         if (pos == isl_dim_total(dim))
 112                 return NULL;
 113         if (pos >= dim->n_name)
 114                 return NULL;
 115         return dim->names[pos];
 116 }
 117
 118 static unsigned offset(struct isl_dim *dim, enum isl_dim_type type)
 119 {
 120         switch (type) {
 121         case isl_dim_param:     return 0;
 122         case isl_dim_in:        return dim->nparam;
 123         case isl_dim_out:       return dim->nparam + dim->n_in;
 124         }
 125 }
 126
 127 static unsigned n(struct isl_dim *dim, enum isl_dim_type type)
 128 {
 129         switch (type) {
 130         case isl_dim_param:     return dim->nparam;
 131         case isl_dim_in:        return dim->n_in;
 132         case isl_dim_out:       return dim->n_out;
 133         }
 134 }
 135
 136 unsigned isl_dim_size(struct isl_dim *dim, enum isl_dim_type type)
 137 {
 138         if (!dim)
 139                 return 0;
 140         return n(dim, type);
 141 }
 142
 143 static struct isl_dim *copy_names(struct isl_dim *dst,
 144         enum isl_dim_type dst_type, unsigned offset, struct isl_dim *src,
 145         enum isl_dim_type src_type)
 146 {
 147         int i;
 148         struct isl_name *name;
 149
 150         for (i = 0; i < n(src, src_type); ++i) {
 151                 name = get_name(src, src_type, i);
 152                 if (!name)
 153                         continue;
 154                 dst = set_name(dst, dst_type, offset + i,
 155                                         isl_name_copy(dst->ctx, name));
 156                 if (!dst)
 157                         return NULL;
 158         }
 159         return dst;
 160 }
 161
 162 struct isl_dim *isl_dim_dup(struct isl_dim *dim)
 163 {
 164         struct isl_dim *dup;
 165         dup = isl_dim_alloc(dim->ctx, dim->nparam, dim->n_in, dim->n_out);
 166         if (!dim->names)
 167                 return dup;
 168         dup = copy_names(dup, isl_dim_param, 0, dim, isl_dim_param);
 169         dup = copy_names(dup, isl_dim_in, 0, dim, isl_dim_in);
 170         dup = copy_names(dup, isl_dim_out, 0, dim, isl_dim_out);
 171         return dup;
 172 }
 173
 174 struct isl_dim *isl_dim_cow(struct isl_dim *dim)
 175 {
 176         if (!dim)
 177                 return NULL;
 178
 179         if (dim->ref == 1)
 180                 return dim;
 181         dim->ref--;
 182         return isl_dim_dup(dim);
 183 }
 184
 185 struct isl_dim *isl_dim_copy(struct isl_dim *dim)
 186 {
 187         if (!dim)
 188                 return NULL;
 189
 190         dim->ref++;
 191         return dim;
 192 }
 193
 194 void isl_dim_free(struct isl_dim *dim)
 195 {
 196         int i;
 197
 198         if (!dim)
 199                 return;
 200
 201         if (--dim->ref > 0)
 202                 return;
 203
 204         for (i = 0; i < dim->n_name; ++i)
 205                 isl_name_free(dim->ctx, dim->names[i]);
 206         free(dim->names);
 207         isl_ctx_deref(dim->ctx);
 208
 209         free(dim);
 210 }
 211
 212 struct isl_dim *isl_dim_set_name(struct isl_dim *dim,
 213                                  enum isl_dim_type type, unsigned pos,
 214                                  const char *s)
 215 {
 216         struct isl_name *name;
 217         if (!dim)
 218                 return NULL;
 219         name = isl_name_get(dim->ctx, s);
 220         if (!name)
 221                 goto error;
 222         return set_name(dim, type, pos, name);
 223 error:
 224         isl_dim_free(dim);
 225         return NULL;
 226 }
 227
 228 const char *isl_dim_get_name(struct isl_dim *dim,
 229                                  enum isl_dim_type type, unsigned pos)
 230 {
 231         struct isl_name *name = get_name(dim, type, pos);
 232         return name ? name->name : NULL;
 233 }
 234
 235 static int match(struct isl_dim *dim1, enum isl_dim_type dim1_type,
 236                 struct isl_dim *dim2, enum isl_dim_type dim2_type)
 237 {
 238         int i;
 239
 240         if (n(dim1, dim1_type) != n(dim2, dim2_type))
 241                 return 0;
 242
 243         if (!dim1->names && !dim2->names)
 244                 return 1;
 245
 246         for (i = 0; i < n(dim1, dim1_type); ++i) {
 247                 if (get_name(dim1, dim1_type, i) !=
 248                     get_name(dim2, dim2_type, i))
 249                         return 0;
 250         }
 251         return 1;
 252 }
 253
 254 int isl_dim_match(struct isl_dim *dim1, enum isl_dim_type dim1_type,
 255                 struct isl_dim *dim2, enum isl_dim_type dim2_type)
 256 {
 257         return match(dim1, dim1_type, dim2, dim2_type);
 258 }
 259
 260 static void get_names(struct isl_dim *dim, enum isl_dim_type type,
 261         unsigned first, unsigned n, struct isl_name **names)
 262 {
 263         int i;
 264
 265         for (i = 0; i < n ; ++i)
 266                 names[i] = get_name(dim, type, first+i);
 267 }
 268
 269 struct isl_dim *isl_dim_extend(struct isl_dim *dim,
 270                         unsigned nparam, unsigned n_in, unsigned n_out)
 271 {
 272         struct isl_name **names = NULL;
 273
 274         if (!dim)
 275                 return NULL;
 276         if (dim->nparam == nparam && dim->n_in == n_in && dim->n_out == n_out)
 277                 return dim;
 278
 279         isl_assert(dim->ctx, dim->nparam <= nparam, goto error);
 280         isl_assert(dim->ctx, dim->n_in <= n_in, goto error);
 281         isl_assert(dim->ctx, dim->n_out <= n_out, goto error);
 282
 283         dim = isl_dim_cow(dim);
 284
 285         if (dim->names) {
 286                 names = isl_calloc_array(dim->ctx, struct isl_name *,
 287                                          nparam + n_in + n_out);
 288                 if (!names)
 289                         goto error;
 290                 get_names(dim, isl_dim_param, 0, dim->nparam, names);
 291                 get_names(dim, isl_dim_in, 0, dim->n_in, names + nparam);
 292                 get_names(dim, isl_dim_out, 0, dim->n_out,
 293                                 names + nparam + n_in);
 294                 free(dim->names);
 295                 dim->names = names;
 296                 dim->n_name = nparam + n_in + n_out;
 297         }
 298         dim->nparam = nparam;
 299         dim->n_in = n_in;
 300         dim->n_out = n_out;
 301
 302         return dim;
 303 error:
 304         free(names);
 305         isl_dim_free(dim);
 306         return NULL;
 307 }
 308
 309 struct isl_dim *isl_dim_add(struct isl_dim *dim, enum isl_dim_type type,
 310         unsigned n)
 311 {
 312         switch (type) {
 313         case isl_dim_param:
 314                 return isl_dim_extend(dim,
 315                                         dim->nparam + n, dim->n_in, dim->n_out);
 316         case isl_dim_in:
 317                 return isl_dim_extend(dim,
 318                                         dim->nparam, dim->n_in + n, dim->n_out);
 319         case isl_dim_out:
 320                 return isl_dim_extend(dim,
 321                                         dim->nparam, dim->n_in, dim->n_out + n);
 322         }
 323         return dim;
 324 }
 325
 326 struct isl_dim *isl_dim_join(struct isl_dim *left, struct isl_dim *right)
 327 {
 328         struct isl_dim *dim;
 329
 330         if (!left || !right)
 331                 goto error;
 332
 333         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
 334                         goto error);
 335         isl_assert(left->ctx, match(left, isl_dim_out, right, isl_dim_in),
 336                         goto error);
 337
 338         dim = isl_dim_alloc(left->ctx, left->nparam, left->n_in, right->n_out);
 339         if (!dim)
 340                 goto error;
 341
 342         dim = copy_names(dim, isl_dim_param, 0, left, isl_dim_param);
 343         dim = copy_names(dim, isl_dim_in, 0, left, isl_dim_in);
 344         dim = copy_names(dim, isl_dim_out, 0, right, isl_dim_out);
 345
 346         isl_dim_free(left);
 347         isl_dim_free(right);
 348
 349         return dim;
 350 error:
 351         isl_dim_free(left);
 352         isl_dim_free(right);
 353         return NULL;
 354 }
 355
 356 struct isl_dim *isl_dim_product(struct isl_dim *left, struct isl_dim *right)
 357 {
 358         struct isl_dim *dim;
 359
 360         if (!left || !right)
 361                 goto error;
 362
 363         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
 364                         goto error);
 365
 366         dim = isl_dim_alloc(left->ctx, left->nparam,
 367                         left->n_in + right->n_in, left->n_out + right->n_out);
 368         if (!dim)
 369                 goto error;
 370
 371         dim = copy_names(dim, isl_dim_param, 0, left, isl_dim_param);
 372         dim = copy_names(dim, isl_dim_in, 0, left, isl_dim_in);
 373         dim = copy_names(dim, isl_dim_in, left->n_in, right, isl_dim_in);
 374         dim = copy_names(dim, isl_dim_out, 0, left, isl_dim_out);
 375         dim = copy_names(dim, isl_dim_out, left->n_out, right, isl_dim_out);
 376
 377         isl_dim_free(left);
 378         isl_dim_free(right);
 379
 380         return dim;
 381 error:
 382         isl_dim_free(left);
 383         isl_dim_free(right);
 384         return NULL;
 385 }
 386
 387 struct isl_dim *isl_dim_map(struct isl_dim *dim)
 388 {
 389         struct isl_name **names = NULL;
 390
 391         if (!dim)
 392                 return NULL;
 393         isl_assert(dim->ctx, dim->n_in == 0, goto error);
 394         if (dim->n_out == 0)
 395                 return dim;
 396         dim = isl_dim_cow(dim);
 397         if (!dim)
 398                 return NULL;
 399         if (dim->names) {
 400                 names = isl_calloc_array(dim->ctx, struct isl_name *,
 401                                         dim->nparam + dim->n_out + dim->n_out);
 402                 if (!names)
 403                         goto error;
 404                 get_names(dim, isl_dim_param, 0, dim->nparam, names);
 405                 get_names(dim, isl_dim_out, 0, dim->n_out, names + dim->nparam);
 406         }
 407         dim->n_in = dim->n_out;
 408         if (names) {
 409                 copy_names(dim, isl_dim_out, 0, dim, isl_dim_in);
 410                 free(dim->names);
 411                 dim->names = names;
 412                 dim->n_name = dim->nparam + dim->n_out + dim->n_out;
 413         }
 414         return dim;
 415 error:
 416         isl_dim_free(dim);
 417         return NULL;
 418 }
 419
 420 static struct isl_dim *set_names(struct isl_dim *dim, enum isl_dim_type type,
 421         unsigned first, unsigned n, struct isl_name **names)
 422 {
 423         int i;
 424
 425         for (i = 0; i < n ; ++i)
 426                 dim = set_name(dim, type, first+i, names[i]);
 427
 428         return dim;
 429 }
 430
 431 struct isl_dim *isl_dim_reverse(struct isl_dim *dim)
 432 {
 433         unsigned t;
 434         struct isl_name **names = NULL;
 435
 436         if (!dim)
 437                 return NULL;
 438         if (match(dim, isl_dim_in, dim, isl_dim_out))
 439                 return dim;
 440
 441         dim = isl_dim_cow(dim);
 442         if (!dim)
 443                 return NULL;
 444
 445         if (dim->names) {
 446                 names = isl_alloc_array(dim->ctx, struct isl_name *,
 447                                         dim->n_in + dim->n_out);
 448                 if (!names)
 449                         goto error;
 450                 get_names(dim, isl_dim_in, 0, dim->n_in, names);
 451                 get_names(dim, isl_dim_out, 0, dim->n_out, names + dim->n_in);
 452         }
 453
 454         t = dim->n_in;
 455         dim->n_in = dim->n_out;
 456         dim->n_out = t;
 457
 458         if (dim->names) {
 459                 dim = set_names(dim, isl_dim_out, 0, dim->n_out, names);
 460                 dim = set_names(dim, isl_dim_in, 0, dim->n_in, names + dim->n_out);
 461                 free(names);
 462         }
 463
 464         return dim;
 465 error:
 466         free(names);
 467         isl_dim_free(dim);
 468         return NULL;
 469 }
 470
 471 struct isl_dim *isl_dim_drop(struct isl_dim *dim, enum isl_dim_type type,
 472                 unsigned first, unsigned num)
 473 {
 474         int i;
 475
 476         if (!dim)
 477                 return NULL;
 478
 479         if (n == 0)
 480                 return dim;
 481
 482         isl_assert(dim->ctx, first + num <= n(dim, type), goto error);
 483         dim = isl_dim_cow(dim);
 484         if (!dim)
 485                 goto error;
 486         if (dim->names) {
 487                 for (i = 0; i < num; ++i)
 488                         isl_name_free(dim->ctx, get_name(dim, type, first+i));
 489                 for (i = first+num; i < n(dim, type); ++i)
 490                         set_name(dim, type, i - num, get_name(dim, type, i));
 491                 switch (type) {
 492                 case isl_dim_param:
 493                         get_names(dim, isl_dim_in, 0, dim->n_in,
 494                                 dim->names + offset(dim, isl_dim_in) - num);
 495                 case isl_dim_in:
 496                         get_names(dim, isl_dim_out, 0, dim->n_out,
 497                                 dim->names + offset(dim, isl_dim_out) - num);
 498                 case isl_dim_out:
 499                         ;
 500                 }
 501         }
 502         switch (type) {
 503         case isl_dim_param:     dim->nparam -= num; break;
 504         case isl_dim_in:        dim->n_in -= num; break;
 505         case isl_dim_out:       dim->n_out -= num; break;
 506         }
 507         return dim;
 508 error:
 509         isl_dim_free(dim);
 510         return NULL;
 511 }
 512
 513 struct isl_dim *isl_dim_drop_inputs(struct isl_dim *dim,
 514                 unsigned first, unsigned n)
 515 {
 516         return isl_dim_drop(dim, isl_dim_in, first, n);
 517 }
 518
 519 struct isl_dim *isl_dim_drop_outputs(struct isl_dim *dim,
 520                 unsigned first, unsigned n)
 521 {
 522         return isl_dim_drop(dim, isl_dim_out, first, n);
 523 }
 524
 525 struct isl_dim *isl_dim_domain(struct isl_dim *dim)
 526 {
 527         if (!dim)
 528                 return NULL;
 529         dim = isl_dim_drop_outputs(dim, 0, dim->n_out);
 530         return isl_dim_reverse(dim);
 531 }
 532
 533 struct isl_dim *isl_dim_range(struct isl_dim *dim)
 534 {
 535         if (!dim)
 536                 return NULL;
 537         return isl_dim_drop_inputs(dim, 0, dim->n_in);
 538 }
 539
 540 struct isl_dim *isl_dim_underlying(struct isl_dim *dim, unsigned n_div)
 541 {
 542         int i;
 543
 544         if (!dim)
 545                 return NULL;
 546         if (n_div == 0 &&
 547             dim->nparam == 0 && dim->n_in == 0 && dim->n_name == 0)
 548                 return dim;
 549         dim = isl_dim_cow(dim);
 550         if (!dim)
 551                 return NULL;
 552         dim->n_out += dim->nparam + dim->n_in + n_div;
 553         dim->nparam = 0;
 554         dim->n_in = 0;
 555
 556         for (i = 0; i < dim->n_name; ++i)
 557                 isl_name_free(dim->ctx, get_name(dim, isl_dim_out, i));
 558         dim->n_name = 0;
 559
 560         return dim;
 561 }
 562
 563 unsigned isl_dim_total(struct isl_dim *dim)
 564 {
 565         return dim->nparam + dim->n_in + dim->n_out;
 566 }
 567
 568 int isl_dim_equal(struct isl_dim *dim1, struct isl_dim *dim2)
 569 {
 570         return match(dim1, isl_dim_param, dim2, isl_dim_param) &&
 571                match(dim1, isl_dim_in, dim2, isl_dim_in) &&
 572                match(dim1, isl_dim_out, dim2, isl_dim_out);
 573 }
 574
 575 int isl_dim_compatible(struct isl_dim *dim1, struct isl_dim *dim2)
 576 {
 577         return dim1->nparam == dim2->nparam &&
 578                dim1->n_in + dim1->n_out == dim2->n_in + dim2->n_out;
 579 }