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         u = isl_calloc_type(ctx, UNION);
  50         if (!u)
  51                 return NULL;
  52
  53         u->ref = 1;
  54 #ifdef HAS_TYPE
  55         u->type = type;
  56 #endif
  57         u->dim = dim;
  58         if (isl_hash_table_init(dim->ctx, &u->table, size) < 0)
  59                 goto error;
  60
  61         return u;
  62 error:
  63         isl_dim_free(dim);
  64         FN(UNION,free)(u);
  65         return NULL;
  66 }
  67
  68 #ifdef HAS_TYPE
  69 __isl_give UNION *FN(UNION,zero)(__isl_take isl_dim *dim, enum isl_fold type)
  70 {
  71         return FN(UNION,alloc)(dim, type, 16);
  72 }
  73 #else
  74 __isl_give UNION *FN(UNION,zero)(__isl_take isl_dim *dim)
  75 {
  76         return FN(UNION,alloc)(dim, 16);
  77 }
  78 #endif
  79
  80 __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
  81 {
  82         if (!u)
  83                 return NULL;
  84
  85         u->ref++;
  86         return u;
  87 }
  88
  89 S(UNION,foreach_data)
  90 {
  91         int (*fn)(__isl_take PART *part, void *user);
  92         void *user;
  93 };
  94
  95 static int call_on_copy(void **entry, void *user)
  96 {
  97         PART *part = *entry;
  98         S(UNION,foreach_data) *data = (S(UNION,foreach_data) *)user;
  99
 100         return data->fn(FN(PART,copy)(part), data->user);
 101 }
 102
 103 int FN(FN(UNION,foreach),PARTS)(__isl_keep UNION *u,
 104         int (*fn)(__isl_take PART *part, void *user), void *user)
 105 {
 106         S(UNION,foreach_data) data = { fn, user };
 107
 108         if (!u)
 109                 return -1;
 110
 111         return isl_hash_table_foreach(u->dim->ctx, &u->table,
 112                                       &call_on_copy, &data);
 113 }
 114
 115 static int has_dim(const void *entry, const void *val)
 116 {
 117         PART *part = (PART *)entry;
 118         isl_dim *dim = (isl_dim *)val;
 119
 120         return isl_dim_equal(part->dim, dim);
 121 }
 122
 123 __isl_give PART *FN(FN(UNION,extract),PARTS)(__isl_keep UNION *u,
 124         __isl_take isl_dim *dim)
 125 {
 126         uint32_t hash;
 127         struct isl_hash_table_entry *entry;
 128
 129         if (!u || !dim)
 130                 goto error;
 131
 132         hash = isl_dim_get_hash(dim);
 133         entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
 134                                     &has_dim, dim, 0);
 135         if (!entry)
 136 #ifdef HAS_TYPE
 137                 return FN(PART,zero)(dim, u->type);
 138 #else
 139                 return FN(PART,zero)(dim);
 140 #endif
 141         isl_dim_free(dim);
 142         return FN(PART,copy)(entry->data);
 143 error:
 144         isl_dim_free(dim);
 145         return NULL;
 146 }
 147
 148 __isl_give UNION *FN(FN(UNION,add),PARTS)(__isl_take UNION *u,
 149         __isl_take PART *part)
 150 {
 151         uint32_t hash;
 152         struct isl_hash_table_entry *entry;
 153
 154         if (!part)
 155                 goto error;
 156
 157         if (FN(PART,is_zero)(part)) {
 158                 FN(PART,free)(part);
 159                 return u;
 160         }
 161
 162         u = FN(UNION,cow)(u);
 163
 164         if (!u)
 165                 goto error;
 166
 167         isl_assert(u->dim->ctx, isl_dim_match(part->dim, isl_dim_param, u->dim,
 168                                               isl_dim_param), goto error);
 169
 170         hash = isl_dim_get_hash(part->dim);
 171         entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
 172                                     &has_dim, part->dim, 1);
 173         if (!entry)
 174                 goto error;
 175
 176         if (!entry->data)
 177                 entry->data = part;
 178         else {
 179                 entry->data = FN(PART,add)(entry->data, FN(PART,copy)(part));
 180                 if (!entry->data)
 181                         goto error;
 182                 FN(PART,free)(part);
 183                 if (FN(PART,is_zero)(entry->data)) {
 184                         FN(PART,free)(entry->data);
 185                         isl_hash_table_remove(u->dim->ctx, &u->table, entry);
 186                 }
 187         }
 188
 189         return u;
 190 error:
 191         FN(PART,free)(part);
 192         FN(UNION,free)(u);
 193         return NULL;
 194 }
 195
 196 static int add_part(__isl_take PART *part, void *user)
 197 {
 198         UNION **u = (UNION **)user;
 199
 200         *u = FN(FN(UNION,add),PARTS)(*u, part);
 201
 202         return 0;
 203 }
 204
 205 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
 206 {
 207         UNION *dup;
 208
 209         if (!u)
 210                 return NULL;
 211
 212 #ifdef HAS_TYPE
 213         dup = FN(UNION,zero)(isl_dim_copy(u->dim), u->type);
 214 #else
 215         dup = FN(UNION,zero)(isl_dim_copy(u->dim));
 216 #endif
 217         if (FN(FN(UNION,foreach),PARTS)(u, &add_part, &dup) < 0)
 218                 goto error;
 219         return dup;
 220 error:
 221         FN(UNION,free)(dup);
 222         return NULL;
 223 }
 224
 225 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
 226 {
 227         if (!u)
 228                 return NULL;
 229
 230         if (u->ref == 1)
 231                 return u;
 232         u->ref--;
 233         return FN(UNION,dup)(u);
 234 }
 235
 236 static int free_u_entry(void **entry, void *user)
 237 {
 238         PART *part = *entry;
 239         FN(PART,free)(part);
 240         return 0;
 241 }
 242
 243 void FN(UNION,free)(__isl_take UNION *u)
 244 {
 245         if (!u)
 246                 return;
 247
 248         if (--u->ref > 0)
 249                 return;
 250
 251         isl_hash_table_foreach(u->dim->ctx, &u->table, &free_u_entry, NULL);
 252         isl_hash_table_clear(&u->table);
 253         isl_dim_free(u->dim);
 254         free(u);
 255 }
 256
 257 S(UNION,align) {
 258         isl_reordering *exp;
 259         UNION *res;
 260 };
 261
 262 static int align_entry(__isl_take PART *part, void *user)
 263 {
 264         isl_reordering *exp;
 265         S(UNION,align) *data = user;
 266
 267         exp = isl_reordering_extend_dim(isl_reordering_copy(data->exp),
 268                                     FN(PART,get_dim)(part));
 269
 270         data->res = FN(FN(UNION,add),PARTS)(data->res,
 271                                             FN(PART,realign)(part, exp));
 272
 273         return 0;
 274 }
 275
 276 __isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
 277         __isl_take isl_dim *model)
 278 {
 279         int i, j;
 280         S(UNION,align) data = { NULL, NULL };
 281
 282         if (!u || !model)
 283                 goto error;
 284
 285         if (isl_dim_match(u->dim, isl_dim_param, model, isl_dim_param)) {
 286                 isl_dim_free(model);
 287                 return u;
 288         }
 289
 290         data.exp = isl_parameter_alignment_reordering(u->dim, model);
 291         if (!data.exp)
 292                 goto error;
 293
 294 #ifdef HAS_TYPE
 295         data.res = FN(UNION,alloc)(isl_dim_copy(data.exp->dim),
 296                                                 u->type, u->table.n);
 297 #else
 298         data.res = FN(UNION,alloc)(isl_dim_copy(data.exp->dim), u->table.n);
 299 #endif
 300         if (FN(FN(UNION,foreach),PARTS)(u, &align_entry, &data) < 0)
 301                 goto error;
 302
 303         isl_reordering_free(data.exp);
 304         FN(UNION,free)(u);
 305         isl_dim_free(model);
 306         return data.res;
 307 error:
 308         isl_reordering_free(data.exp);
 309         FN(UNION,free)(u);
 310         FN(UNION,free)(data.res);
 311         isl_dim_free(model);
 312         return NULL;
 313 }
 314
 315 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
 316 {
 317         u1 = FN(UNION,align_params)(u1, FN(UNION,get_dim)(u2));
 318         u2 = FN(UNION,align_params)(u2, FN(UNION,get_dim)(u1));
 319
 320         u1 = FN(UNION,cow)(u1);
 321
 322         if (!u1 || !u2)
 323                 goto error;
 324
 325         if (FN(FN(UNION,foreach),PARTS)(u2, &add_part, &u1) < 0)
 326                 goto error;
 327
 328         FN(UNION,free)(u2);
 329
 330         return u1;
 331 error:
 332         FN(UNION,free)(u1);
 333         FN(UNION,free)(u2);
 334         return NULL;
 335 }
 336
 337 __isl_give UNION *FN(FN(UNION,from),PARTS)(__isl_take PART *part)
 338 {
 339         isl_dim *dim;
 340         UNION *u;
 341
 342         if (!part)
 343                 return NULL;
 344
 345         dim = FN(PART,get_dim)(part);
 346         dim = isl_dim_drop(dim, isl_dim_in, 0, isl_dim_size(dim, isl_dim_in));
 347         dim = isl_dim_drop(dim, isl_dim_out, 0, isl_dim_size(dim, isl_dim_out));
 348 #ifdef HAS_TYPE
 349         u = FN(UNION,zero)(dim, part->type);
 350 #else
 351         u = FN(UNION,zero)(dim);
 352 #endif
 353         u = FN(FN(UNION,add),PARTS)(u, part);
 354
 355         return u;
 356 }
 357
 358 S(UNION,match_bin_data) {
 359         UNION *u2;
 360         UNION *res;
 361 };
 362
 363 static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
 364         __isl_take UNION *u2, int (*fn)(void **, void *))
 365 {
 366         S(UNION,match_bin_data) data = { NULL, NULL };
 367
 368         u1 = FN(UNION,align_params)(u1, FN(UNION,get_dim)(u2));
 369         u2 = FN(UNION,align_params)(u2, FN(UNION,get_dim)(u1));
 370
 371         if (!u1 || !u2)
 372                 goto error;
 373
 374         data.u2 = u2;
 375 #ifdef HAS_TYPE
 376         data.res = FN(UNION,alloc)(isl_dim_copy(u1->dim), u1->type, u1->table.n);
 377 #else
 378         data.res = FN(UNION,alloc)(isl_dim_copy(u1->dim), u1->table.n);
 379 #endif
 380         if (isl_hash_table_foreach(u1->dim->ctx, &u1->table, fn, &data) < 0)
 381                 goto error;
 382
 383         FN(UNION,free)(u1);
 384         FN(UNION,free)(u2);
 385         return data.res;
 386 error:
 387         FN(UNION,free)(u1);
 388         FN(UNION,free)(u2);
 389         FN(UNION,free)(data.res);
 390         return NULL;
 391 }
 392
 393 S(UNION,match_set_data) {
 394         isl_union_set *uset;
 395         UNION *res;
 396         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
 397 };
 398
 399 static int set_has_dim(const void *entry, const void *val)
 400 {
 401         isl_set *set = (isl_set *)entry;
 402         isl_dim *dim = (isl_dim *)val;
 403
 404         return isl_dim_equal(set->dim, dim);
 405 }
 406
 407 static int match_set_entry(void **entry, void *user)
 408 {
 409         S(UNION,match_set_data) *data = user;
 410         uint32_t hash;
 411         struct isl_hash_table_entry *entry2;
 412         isl_dim *dim;
 413         PW *pw = *entry;
 414         int empty;
 415
 416         hash = isl_dim_get_hash(pw->dim);
 417         entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
 418                                      hash, &set_has_dim, pw->dim, 0);
 419         if (!entry2)
 420                 return 0;
 421
 422         pw = FN(PW,copy)(pw);
 423         pw = data->fn(pw, isl_set_copy(entry2->data));
 424
 425         empty = FN(PW,is_zero)(pw);
 426         if (empty < 0) {
 427                 FN(PW,free)(pw);
 428                 return -1;
 429         }
 430         if (empty) {
 431                 FN(PW,free)(pw);
 432                 return 0;
 433         }
 434
 435         data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
 436
 437         return 0;
 438 }
 439
 440 static __isl_give UNION *match_set_op(__isl_take UNION *u,
 441         __isl_take isl_union_set *uset,
 442         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
 443 {
 444         S(UNION,match_set_data) data = { NULL, NULL, fn };
 445
 446         u = FN(UNION,align_params)(u, isl_union_set_get_dim(uset));
 447         uset = isl_union_set_align_params(uset, FN(UNION,get_dim)(u));
 448
 449         if (!u || !uset)
 450                 goto error;
 451
 452         data.uset = uset;
 453 #ifdef HAS_TYPE
 454         data.res = FN(UNION,alloc)(isl_dim_copy(u->dim), u->type, u->table.n);
 455 #else
 456         data.res = FN(UNION,alloc)(isl_dim_copy(u->dim), u->table.n);
 457 #endif
 458         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
 459                                    &match_set_entry, &data) < 0)
 460                 goto error;
 461
 462         FN(UNION,free)(u);
 463         isl_union_set_free(uset);
 464         return data.res;
 465 error:
 466         FN(UNION,free)(u);
 467         isl_union_set_free(uset);
 468         FN(UNION,free)(data.res);
 469         return NULL;
 470 }
 471
 472 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
 473         __isl_take isl_union_set *uset)
 474 {
 475         return match_set_op(u, uset, &FN(PW,intersect_domain));
 476 }
 477
 478 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
 479         __isl_take isl_union_set *uset)
 480 {
 481         return match_set_op(u, uset, &FN(PW,gist));
 482 }
 483
 484 __isl_give isl_qpolynomial *FN(UNION,eval)(__isl_take UNION *u,
 485         __isl_take isl_point *pnt)
 486 {
 487         uint32_t hash;
 488         struct isl_hash_table_entry *entry;
 489         isl_qpolynomial *qp;
 490
 491         if (!u || !pnt)
 492                 goto error;
 493
 494         hash = isl_dim_get_hash(pnt->dim);
 495         entry = isl_hash_table_find(u->dim->ctx, &u->table,
 496                                     hash, &has_dim, pnt->dim, 0);
 497         if (!entry) {
 498                 qp = isl_qpolynomial_zero(isl_dim_copy(pnt->dim));
 499                 isl_point_free(pnt);
 500         } else {
 501                 qp = FN(PART,eval)(FN(PART,copy)(entry->data), pnt);
 502         }
 503         FN(UNION,free)(u);
 504         return qp;
 505 error:
 506         FN(UNION,free)(u);
 507         isl_point_free(pnt);
 508         return NULL;
 509 }
 510
 511 static int coalesce_entry(void **entry, void *user)
 512 {
 513         PW **pw = (PW **)entry;
 514
 515         *pw = FN(PW,coalesce)(*pw);
 516         if (!*pw)
 517                 return -1;
 518
 519         return 0;
 520 }
 521
 522 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
 523 {
 524         if (!u)
 525                 return NULL;
 526
 527         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
 528                                    &coalesce_entry, NULL) < 0)
 529                 goto error;
 530
 531         return u;
 532 error:
 533         FN(UNION,free)(u);
 534         return NULL;
 535 }
 536
 537 static int domain(__isl_take PART *part, void *user)
 538 {
 539         isl_union_set **uset = (isl_union_set **)user;
 540
 541         *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
 542
 543         return 0;
 544 }
 545
 546 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
 547 {
 548         isl_union_set *uset;
 549
 550         uset = isl_union_set_empty(FN(UNION,get_dim)(u));
 551         if (FN(FN(UNION,foreach),PARTS)(u, &domain, &uset) < 0)
 552                 goto error;
 553
 554         FN(UNION,free)(u);
 555
 556         return uset;
 557 error:
 558         isl_union_set_free(uset);
 559         FN(UNION,free)(u);
 560         return NULL;
 561 }