isl_union_templ.c

   1 /*
   2  * Copyright 2010      INRIA Saclay
   3  *
   4  * Use of this software is governed by the GNU LGPLv2.1 license
   5  *
   6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   8  * 91893 Orsay, France
   9  */
  10
  11 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
  12 #define FN(TYPE,NAME) xFN(TYPE,NAME)
  13 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
  14 #define S(TYPE,NAME) xS(TYPE,NAME)
  15
  16 struct UNION {
  17         int ref;
  18 #ifdef HAS_TYPE
  19         enum isl_fold type;
  20 #endif
  21         isl_dim *dim;
  22
  23         struct isl_hash_table   table;
  24 };
  25
  26 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u);
  27
  28 isl_ctx *FN(UNION,get_ctx)(__isl_keep UNION *u)
  29 {
  30         return u ? u->dim->ctx : NULL;
  31 }
  32
  33 __isl_give isl_dim *FN(UNION,get_dim)(__isl_keep UNION *u)
  34 {
  35         if (!u)
  36                 return NULL;
  37         return isl_dim_copy(u->dim);
  38 }
  39
  40 #ifdef HAS_TYPE
  41 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_dim *dim,
  42         enum isl_fold type, int size)
  43 #else
  44 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_dim *dim, int size)
  45 #endif
  46 {
  47         UNION *u;
  48
  49         if (!dim)
  50                 return NULL;
  51
  52         u = isl_calloc_type(dim->ctx, UNION);
  53         if (!u)
  54                 return NULL;
  55
  56         u->ref = 1;
  57 #ifdef HAS_TYPE
  58         u->type = type;
  59 #endif
  60         u->dim = dim;
  61         if (isl_hash_table_init(dim->ctx, &u->table, size) < 0)
  62                 goto error;
  63
  64         return u;
  65 error:
  66         isl_dim_free(dim);
  67         FN(UNION,free)(u);
  68         return NULL;
  69 }
  70
  71 #ifdef HAS_TYPE
  72 __isl_give UNION *FN(UNION,zero)(__isl_take isl_dim *dim, enum isl_fold type)
  73 {
  74         return FN(UNION,alloc)(dim, type, 16);
  75 }
  76 #else
  77 __isl_give UNION *FN(UNION,zero)(__isl_take isl_dim *dim)
  78 {
  79         return FN(UNION,alloc)(dim, 16);
  80 }
  81 #endif
  82
  83 __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
  84 {
  85         if (!u)
  86                 return NULL;
  87
  88         u->ref++;
  89         return u;
  90 }
  91
  92 S(UNION,foreach_data)
  93 {
  94         int (*fn)(__isl_take PART *part, void *user);
  95         void *user;
  96 };
  97
  98 static int call_on_copy(void **entry, void *user)
  99 {
 100         PART *part = *entry;
 101         S(UNION,foreach_data) *data = (S(UNION,foreach_data) *)user;
 102
 103         return data->fn(FN(PART,copy)(part), data->user);
 104 }
 105
 106 int FN(FN(UNION,foreach),PARTS)(__isl_keep UNION *u,
 107         int (*fn)(__isl_take PART *part, void *user), void *user)
 108 {
 109         S(UNION,foreach_data) data = { fn, user };
 110
 111         if (!u)
 112                 return -1;
 113
 114         return isl_hash_table_foreach(u->dim->ctx, &u->table,
 115                                       &call_on_copy, &data);
 116 }
 117
 118 static int has_dim(const void *entry, const void *val)
 119 {
 120         PART *part = (PART *)entry;
 121         isl_dim *dim = (isl_dim *)val;
 122
 123         return isl_dim_equal(part->dim, dim);
 124 }
 125
 126 __isl_give PART *FN(FN(UNION,extract),PARTS)(__isl_keep UNION *u,
 127         __isl_take isl_dim *dim)
 128 {
 129         uint32_t hash;
 130         struct isl_hash_table_entry *entry;
 131
 132         if (!u || !dim)
 133                 goto error;
 134
 135         hash = isl_dim_get_hash(dim);
 136         entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
 137                                     &has_dim, dim, 0);
 138         if (!entry)
 139 #ifdef HAS_TYPE
 140                 return FN(PART,zero)(dim, u->type);
 141 #else
 142                 return FN(PART,zero)(dim);
 143 #endif
 144         isl_dim_free(dim);
 145         return FN(PART,copy)(entry->data);
 146 error:
 147         isl_dim_free(dim);
 148         return NULL;
 149 }
 150
 151 __isl_give UNION *FN(FN(UNION,add),PARTS)(__isl_take UNION *u,
 152         __isl_take PART *part)
 153 {
 154         uint32_t hash;
 155         struct isl_hash_table_entry *entry;
 156
 157         if (!part)
 158                 goto error;
 159
 160         if (FN(PART,is_zero)(part)) {
 161                 FN(PART,free)(part);
 162                 return u;
 163         }
 164
 165         u = FN(UNION,cow)(u);
 166
 167         if (!u)
 168                 goto error;
 169
 170         isl_assert(u->dim->ctx, isl_dim_match(part->dim, isl_dim_param, u->dim,
 171                                               isl_dim_param), goto error);
 172
 173         hash = isl_dim_get_hash(part->dim);
 174         entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
 175                                     &has_dim, part->dim, 1);
 176         if (!entry)
 177                 goto error;
 178
 179         if (!entry->data)
 180                 entry->data = part;
 181         else {
 182                 entry->data = FN(PART,add)(entry->data, FN(PART,copy)(part));
 183                 if (!entry->data)
 184                         goto error;
 185                 FN(PART,free)(part);
 186                 if (FN(PART,is_zero)(entry->data)) {
 187                         FN(PART,free)(entry->data);
 188                         isl_hash_table_remove(u->dim->ctx, &u->table, entry);
 189                 }
 190         }
 191
 192         return u;
 193 error:
 194         FN(PART,free)(part);
 195         FN(UNION,free)(u);
 196         return NULL;
 197 }
 198
 199 static int add_part(__isl_take PART *part, void *user)
 200 {
 201         UNION **u = (UNION **)user;
 202
 203         *u = FN(FN(UNION,add),PARTS)(*u, part);
 204
 205         return 0;
 206 }
 207
 208 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
 209 {
 210         UNION *dup;
 211
 212         if (!u)
 213                 return NULL;
 214
 215 #ifdef HAS_TYPE
 216         dup = FN(UNION,zero)(isl_dim_copy(u->dim), u->type);
 217 #else
 218         dup = FN(UNION,zero)(isl_dim_copy(u->dim));
 219 #endif
 220         if (FN(FN(UNION,foreach),PARTS)(u, &add_part, &dup) < 0)
 221                 goto error;
 222         return dup;
 223 error:
 224         FN(UNION,free)(dup);
 225         return NULL;
 226 }
 227
 228 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
 229 {
 230         if (!u)
 231                 return NULL;
 232
 233         if (u->ref == 1)
 234                 return u;
 235         u->ref--;
 236         return FN(UNION,dup)(u);
 237 }
 238
 239 static int free_u_entry(void **entry, void *user)
 240 {
 241         PART *part = *entry;
 242         FN(PART,free)(part);
 243         return 0;
 244 }
 245
 246 void FN(UNION,free)(__isl_take UNION *u)
 247 {
 248         if (!u)
 249                 return;
 250
 251         if (--u->ref > 0)
 252                 return;
 253
 254         isl_hash_table_foreach(u->dim->ctx, &u->table, &free_u_entry, NULL);
 255         isl_hash_table_clear(&u->table);
 256         isl_dim_free(u->dim);
 257         free(u);
 258 }
 259
 260 S(UNION,align) {
 261         isl_reordering *exp;
 262         UNION *res;
 263 };
 264
 265 static int align_entry(__isl_take PART *part, void *user)
 266 {
 267         isl_reordering *exp;
 268         S(UNION,align) *data = user;
 269
 270         exp = isl_reordering_extend_dim(isl_reordering_copy(data->exp),
 271                                     FN(PART,get_dim)(part));
 272
 273         data->res = FN(FN(UNION,add),PARTS)(data->res,
 274                                             FN(PART,realign)(part, exp));
 275
 276         return 0;
 277 }
 278
 279 __isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
 280         __isl_take isl_dim *model)
 281 {
 282         S(UNION,align) data = { NULL, NULL };
 283
 284         if (!u || !model)
 285                 goto error;
 286
 287         if (isl_dim_match(u->dim, isl_dim_param, model, isl_dim_param)) {
 288                 isl_dim_free(model);
 289                 return u;
 290         }
 291
 292         data.exp = isl_parameter_alignment_reordering(u->dim, model);
 293         if (!data.exp)
 294                 goto error;
 295
 296 #ifdef HAS_TYPE
 297         data.res = FN(UNION,alloc)(isl_dim_copy(data.exp->dim),
 298                                                 u->type, u->table.n);
 299 #else
 300         data.res = FN(UNION,alloc)(isl_dim_copy(data.exp->dim), u->table.n);
 301 #endif
 302         if (FN(FN(UNION,foreach),PARTS)(u, &align_entry, &data) < 0)
 303                 goto error;
 304
 305         isl_reordering_free(data.exp);
 306         FN(UNION,free)(u);
 307         isl_dim_free(model);
 308         return data.res;
 309 error:
 310         isl_reordering_free(data.exp);
 311         FN(UNION,free)(u);
 312         FN(UNION,free)(data.res);
 313         isl_dim_free(model);
 314         return NULL;
 315 }
 316
 317 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
 318 {
 319         u1 = FN(UNION,align_params)(u1, FN(UNION,get_dim)(u2));
 320         u2 = FN(UNION,align_params)(u2, FN(UNION,get_dim)(u1));
 321
 322         u1 = FN(UNION,cow)(u1);
 323
 324         if (!u1 || !u2)
 325                 goto error;
 326
 327         if (FN(FN(UNION,foreach),PARTS)(u2, &add_part, &u1) < 0)
 328                 goto error;
 329
 330         FN(UNION,free)(u2);
 331
 332         return u1;
 333 error:
 334         FN(UNION,free)(u1);
 335         FN(UNION,free)(u2);
 336         return NULL;
 337 }
 338
 339 __isl_give UNION *FN(FN(UNION,from),PARTS)(__isl_take PART *part)
 340 {
 341         isl_dim *dim;
 342         UNION *u;
 343
 344         if (!part)
 345                 return NULL;
 346
 347         dim = FN(PART,get_dim)(part);
 348         dim = isl_dim_drop(dim, isl_dim_in, 0, isl_dim_size(dim, isl_dim_in));
 349         dim = isl_dim_drop(dim, isl_dim_out, 0, isl_dim_size(dim, isl_dim_out));
 350 #ifdef HAS_TYPE
 351         u = FN(UNION,zero)(dim, part->type);
 352 #else
 353         u = FN(UNION,zero)(dim);
 354 #endif
 355         u = FN(FN(UNION,add),PARTS)(u, part);
 356
 357         return u;
 358 }
 359
 360 S(UNION,match_bin_data) {
 361         UNION *u2;
 362         UNION *res;
 363 };
 364
 365 /* This function is currently only used from isl_polynomial.c
 366  * and not from isl_fold.c.
 367  */
 368 static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
 369         __isl_take UNION *u2,
 370         int (*fn)(void **, void *)) __attribute__ ((unused));
 371 static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
 372         __isl_take UNION *u2, int (*fn)(void **, void *))
 373 {
 374         S(UNION,match_bin_data) data = { NULL, NULL };
 375
 376         u1 = FN(UNION,align_params)(u1, FN(UNION,get_dim)(u2));
 377         u2 = FN(UNION,align_params)(u2, FN(UNION,get_dim)(u1));
 378
 379         if (!u1 || !u2)
 380                 goto error;
 381
 382         data.u2 = u2;
 383 #ifdef HAS_TYPE
 384         data.res = FN(UNION,alloc)(isl_dim_copy(u1->dim), u1->type, u1->table.n);
 385 #else
 386         data.res = FN(UNION,alloc)(isl_dim_copy(u1->dim), u1->table.n);
 387 #endif
 388         if (isl_hash_table_foreach(u1->dim->ctx, &u1->table, fn, &data) < 0)
 389                 goto error;
 390
 391         FN(UNION,free)(u1);
 392         FN(UNION,free)(u2);
 393         return data.res;
 394 error:
 395         FN(UNION,free)(u1);
 396         FN(UNION,free)(u2);
 397         FN(UNION,free)(data.res);
 398         return NULL;
 399 }
 400
 401 S(UNION,match_set_data) {
 402         isl_union_set *uset;
 403         UNION *res;
 404         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
 405 };
 406
 407 static int set_has_dim(const void *entry, const void *val)
 408 {
 409         isl_set *set = (isl_set *)entry;
 410         isl_dim *dim = (isl_dim *)val;
 411
 412         return isl_dim_equal(set->dim, dim);
 413 }
 414
 415 static int match_set_entry(void **entry, void *user)
 416 {
 417         S(UNION,match_set_data) *data = user;
 418         uint32_t hash;
 419         struct isl_hash_table_entry *entry2;
 420         PW *pw = *entry;
 421         int empty;
 422
 423         hash = isl_dim_get_hash(pw->dim);
 424         entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
 425                                      hash, &set_has_dim, pw->dim, 0);
 426         if (!entry2)
 427                 return 0;
 428
 429         pw = FN(PW,copy)(pw);
 430         pw = data->fn(pw, isl_set_copy(entry2->data));
 431
 432         empty = FN(PW,is_zero)(pw);
 433         if (empty < 0) {
 434                 FN(PW,free)(pw);
 435                 return -1;
 436         }
 437         if (empty) {
 438                 FN(PW,free)(pw);
 439                 return 0;
 440         }
 441
 442         data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
 443
 444         return 0;
 445 }
 446
 447 static __isl_give UNION *match_set_op(__isl_take UNION *u,
 448         __isl_take isl_union_set *uset,
 449         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
 450 {
 451         S(UNION,match_set_data) data = { NULL, NULL, fn };
 452
 453         u = FN(UNION,align_params)(u, isl_union_set_get_dim(uset));
 454         uset = isl_union_set_align_params(uset, FN(UNION,get_dim)(u));
 455
 456         if (!u || !uset)
 457                 goto error;
 458
 459         data.uset = uset;
 460 #ifdef HAS_TYPE
 461         data.res = FN(UNION,alloc)(isl_dim_copy(u->dim), u->type, u->table.n);
 462 #else
 463         data.res = FN(UNION,alloc)(isl_dim_copy(u->dim), u->table.n);
 464 #endif
 465         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
 466                                    &match_set_entry, &data) < 0)
 467                 goto error;
 468
 469         FN(UNION,free)(u);
 470         isl_union_set_free(uset);
 471         return data.res;
 472 error:
 473         FN(UNION,free)(u);
 474         isl_union_set_free(uset);
 475         FN(UNION,free)(data.res);
 476         return NULL;
 477 }
 478
 479 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
 480         __isl_take isl_union_set *uset)
 481 {
 482         return match_set_op(u, uset, &FN(PW,intersect_domain));
 483 }
 484
 485 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
 486         __isl_take isl_union_set *uset)
 487 {
 488         return match_set_op(u, uset, &FN(PW,gist));
 489 }
 490
 491 __isl_give isl_qpolynomial *FN(UNION,eval)(__isl_take UNION *u,
 492         __isl_take isl_point *pnt)
 493 {
 494         uint32_t hash;
 495         struct isl_hash_table_entry *entry;
 496         isl_qpolynomial *qp;
 497
 498         if (!u || !pnt)
 499                 goto error;
 500
 501         hash = isl_dim_get_hash(pnt->dim);
 502         entry = isl_hash_table_find(u->dim->ctx, &u->table,
 503                                     hash, &has_dim, pnt->dim, 0);
 504         if (!entry) {
 505                 qp = isl_qpolynomial_zero(isl_dim_copy(pnt->dim));
 506                 isl_point_free(pnt);
 507         } else {
 508                 qp = FN(PART,eval)(FN(PART,copy)(entry->data), pnt);
 509         }
 510         FN(UNION,free)(u);
 511         return qp;
 512 error:
 513         FN(UNION,free)(u);
 514         isl_point_free(pnt);
 515         return NULL;
 516 }
 517
 518 static int coalesce_entry(void **entry, void *user)
 519 {
 520         PW **pw = (PW **)entry;
 521
 522         *pw = FN(PW,coalesce)(*pw);
 523         if (!*pw)
 524                 return -1;
 525
 526         return 0;
 527 }
 528
 529 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
 530 {
 531         if (!u)
 532                 return NULL;
 533
 534         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
 535                                    &coalesce_entry, NULL) < 0)
 536                 goto error;
 537
 538         return u;
 539 error:
 540         FN(UNION,free)(u);
 541         return NULL;
 542 }
 543
 544 static int domain(__isl_take PART *part, void *user)
 545 {
 546         isl_union_set **uset = (isl_union_set **)user;
 547
 548         *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
 549
 550         return 0;
 551 }
 552
 553 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
 554 {
 555         isl_union_set *uset;
 556
 557         uset = isl_union_set_empty(FN(UNION,get_dim)(u));
 558         if (FN(FN(UNION,foreach),PARTS)(u, &domain, &uset) < 0)
 559                 goto error;
 560
 561         FN(UNION,free)(u);
 562
 563         return uset;
 564 error:
 565         isl_union_set_free(uset);
 566         FN(UNION,free)(u);
 567         return NULL;
 568 }
 569
 570 static int mul_isl_int(void **entry, void *user)
 571 {
 572         PW **pw = (PW **)entry;
 573         isl_int *v = user;
 574
 575         *pw = FN(PW,mul_isl_int)(*pw, *v);
 576         if (!*pw)
 577                 return -1;
 578
 579         return 0;
 580 }
 581
 582 __isl_give UNION *FN(UNION,mul_isl_int)(__isl_take UNION *u, isl_int v)
 583 {
 584         if (isl_int_is_one(v))
 585                 return u;
 586
 587         if (u && isl_int_is_zero(v)) {
 588                 UNION *zero;
 589                 isl_dim *dim = FN(UNION,get_dim)(u);
 590 #ifdef HAS_TYPE
 591                 zero = FN(UNION,zero)(dim, u->type);
 592 #else
 593                 zero = FN(UNION,zero)(dim);
 594 #endif
 595                 FN(UNION,free)(u);
 596                 return zero;
 597         }
 598
 599         u = FN(UNION,cow)(u);
 600         if (!u)
 601                 return NULL;
 602
 603 #ifdef HAS_TYPE
 604         if (isl_int_is_neg(v))
 605                 u->type = isl_fold_type_negate(u->type);
 606 #endif
 607         if (isl_hash_table_foreach(u->dim->ctx, &u->table, &mul_isl_int, v) < 0)
 608                 goto error;
 609
 610         return u;
 611 error:
 612         FN(UNION,free)(u);
 613         return NULL;
 614 }