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