isl_union_multi.c

   1 /*
   2  * Copyright 2010      INRIA Saclay
   3  * Copyright 2013      Ecole Normale Superieure
   4  * Copyright 2015      INRIA Paris-Rocquencourt
   5  *
   6  * Use of this software is governed by the MIT license
   7  *
   8  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   9  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
  10  * 91893 Orsay, France
  11  * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
  12  * and INRIA Paris-Rocquencourt, Domaine de Voluceau, Rocquenqourt, B.P. 105,
  13  * 78153 Le Chesnay Cedex France
  14  */
  15
  16 #include <isl/hash.h>
  17 #include <isl_union_macro.h>
  18
  19 /* A group of expressions defined over the same domain space "domain_space".
  20  * The entries of "part_table" are the individual expressions,
  21  * keyed on the entire space of the expression.
  22  *
  23  * Each UNION has its own groups, so there can only ever be a single
  24  * reference to each group.
  25  */
  26 S(UNION,group) {
  27         isl_space *domain_space;
  28         struct isl_hash_table   part_table;
  29 };
  30
  31 /* A union of expressions defined over different disjoint domains.
  32  * "space" describes the parameters.
  33  * The entries of "table" are keyed on the domain space of the entry and
  34  * contain groups of expressions that are defined over the same domain space.
  35  */
  36 struct UNION {
  37         int ref;
  38         isl_space *space;
  39
  40         struct isl_hash_table   table;
  41 };
  42
  43 /* Internal data structure for isl_union_*_foreach_group.
  44  * "fn" is the function that needs to be called on each group.
  45  */
  46 S(UNION,foreach_group_data)
  47 {
  48         isl_stat (*fn)(__isl_keep S(UNION,group) *group, void *user);
  49         void *user;
  50 };
  51
  52 /* Call data->fn on the group stored at *entry.
  53  */
  54 static isl_stat FN(UNION,call_on_group)(void **entry, void *user)
  55 {
  56         S(UNION,group) *group = *entry;
  57         S(UNION,foreach_group_data) *data;
  58
  59         data = (S(UNION,foreach_group_data) *) user;
  60         return data->fn(group, data->user);
  61 }
  62
  63 /* Call "fn" on each group of expressions in "u".
  64  */
  65 static isl_stat FN(UNION,foreach_group)(__isl_keep UNION *u,
  66         isl_stat (*fn)(__isl_keep S(UNION,group) *group, void *user),
  67         void *user)
  68 {
  69         S(UNION,foreach_group_data) data = { fn, user };
  70
  71         if (!u)
  72                 return isl_stat_error;
  73
  74         return isl_hash_table_foreach(u->space->ctx, &u->table,
  75                                       &FN(UNION,call_on_group), &data);
  76 }
  77
  78 /* A isl_union_*_foreach_group callback for counting the total number
  79  * of expressions in a UNION.  Add the number of expressions in "group"
  80  * to *n.
  81  */
  82 static isl_stat FN(UNION,count_part)(__isl_keep S(UNION,group) *group,
  83         void *user)
  84 {
  85         int *n = user;
  86
  87         if (!group)
  88                 return isl_stat_error;
  89
  90         *n += group->part_table.n;
  91         return isl_stat_ok;
  92 }
  93
  94 /* Return the number of base expressions in "u".
  95  */
  96 isl_size FN(FN(UNION,n),BASE)(__isl_keep UNION *u)
  97 {
  98         int n;
  99
 100         n = 0;
 101         if (FN(UNION,foreach_group)(u, &FN(UNION,count_part), &n) < 0)
 102                 return isl_size_error;
 103         return n;
 104 }
 105
 106 /* Free an entry in a group of expressions.
 107  * Each entry in such a group is a single expression.
 108  */
 109 static isl_stat FN(UNION,free_group_entry)(void **entry, void *user)
 110 {
 111         PART *part = *entry;
 112
 113         FN(PART,free)(part);
 114         return isl_stat_ok;
 115 }
 116
 117 /* Free all memory allocated for "group" and return NULL.
 118  */
 119 static __isl_null S(UNION,group) *FN(UNION,group_free)(
 120         __isl_take S(UNION,group) *group)
 121 {
 122         isl_ctx *ctx;
 123
 124         if (!group)
 125                 return NULL;
 126
 127         ctx = isl_space_get_ctx(group->domain_space);
 128         isl_hash_table_foreach(ctx, &group->part_table,
 129                                 &FN(UNION,free_group_entry), NULL);
 130         isl_hash_table_clear(&group->part_table);
 131         isl_space_free(group->domain_space);
 132         free(group);
 133         return NULL;
 134 }
 135
 136 /* Allocate a group of expressions defined over the same domain space
 137  * with domain space "domain_space" and initial size "size".
 138  */
 139 static __isl_give S(UNION,group) *FN(UNION,group_alloc)(
 140         __isl_take isl_space *domain_space, int size)
 141 {
 142         isl_ctx *ctx;
 143         S(UNION,group) *group;
 144
 145         if (!domain_space)
 146                 return NULL;
 147         ctx = isl_space_get_ctx(domain_space);
 148         group = isl_calloc_type(ctx, S(UNION,group));
 149         if (!group)
 150                 goto error;
 151         group->domain_space = domain_space;
 152         if (isl_hash_table_init(ctx, &group->part_table, size) < 0)
 153                 return FN(UNION,group_free)(group);
 154
 155         return group;
 156 error:
 157         isl_space_free(domain_space);
 158         return NULL;
 159 }
 160
 161 /* Is the space of "entry" equal to "space"?
 162  */
 163 static isl_bool FN(UNION,has_space)(const void *entry, const void *val)
 164 {
 165         PART *part = (PART *) entry;
 166         isl_space *space = (isl_space *) val;
 167
 168         return isl_space_is_equal(part->dim, space);
 169 }
 170
 171 /* Return a group equal to "group", but with a single reference.
 172  * Since all groups have only a single reference, simply return "group".
 173  */
 174 static __isl_give S(UNION,group) *FN(UNION,group_cow)(
 175         __isl_take S(UNION,group) *group)
 176 {
 177         return group;
 178 }
 179
 180 S(UNION,foreach_data)
 181 {
 182         isl_stat (*fn)(__isl_take PART *part, void *user);
 183         void *user;
 184 };
 185
 186 static isl_stat FN(UNION,call_on_copy)(void **entry, void *user)
 187 {
 188         PART *part = *entry;
 189         S(UNION,foreach_data) *data = (S(UNION,foreach_data) *) user;
 190
 191         part = FN(PART,copy)(part);
 192         if (!part)
 193                 return isl_stat_error;
 194         return data->fn(part, data->user);
 195 }
 196
 197 /* Call data->fn on a copy of each expression in "group".
 198  */
 199 static isl_stat FN(UNION,group_call_on_copy)(__isl_keep S(UNION,group) *group,
 200         void *user)
 201 {
 202         isl_ctx *ctx;
 203
 204         if (!group)
 205                 return isl_stat_error;
 206
 207         ctx = isl_space_get_ctx(group->domain_space);
 208         return isl_hash_table_foreach(ctx, &group->part_table,
 209                                       &FN(UNION,call_on_copy), user);
 210 }
 211
 212 isl_stat FN(FN(UNION,foreach),BASE)(__isl_keep UNION *u,
 213         isl_stat (*fn)(__isl_take PART *part, void *user), void *user)
 214 {
 215         S(UNION,foreach_data) data = { fn, user };
 216
 217         if (!u)
 218                 return isl_stat_error;
 219
 220         return FN(UNION,foreach_group)(u, &FN(UNION,group_call_on_copy), &data);
 221 }
 222
 223 /* Is the domain space of the group of expressions at "entry"
 224  * equal to that of "space"?
 225  */
 226 static isl_bool FN(UNION,group_has_same_domain_space)(const void *entry,
 227         const void *val)
 228 {
 229         S(UNION,group) *group = (S(UNION,group) *) entry;
 230         isl_space *space = (isl_space *) val;
 231
 232         return isl_space_is_domain_internal(group->domain_space, space);
 233 }
 234
 235 /* Return the entry, if any, in "u" that lives in "space".
 236  * If "reserve" is set, then an entry is created if it does not exist yet.
 237  * Return NULL on error and isl_hash_table_entry_none if no entry was found.
 238  * Note that when "reserve" is set, the function will never return
 239  * isl_hash_table_entry_none.
 240  *
 241  * First look for the group of expressions with the same domain space,
 242  * creating one if needed.
 243  * Then look for the expression living in the specified space in that group.
 244  */
 245 static struct isl_hash_table_entry *FN(UNION,find_part_entry)(
 246         __isl_keep UNION *u, __isl_keep isl_space *space, int reserve)
 247 {
 248         isl_ctx *ctx;
 249         uint32_t hash;
 250         struct isl_hash_table_entry *group_entry;
 251         S(UNION,group) *group;
 252
 253         if (!u || !space)
 254                 return NULL;
 255
 256         ctx = FN(UNION,get_ctx)(u);
 257         hash = isl_space_get_domain_hash(space);
 258         group_entry = isl_hash_table_find(ctx, &u->table, hash,
 259                         &FN(UNION,group_has_same_domain_space), space, reserve);
 260         if (!group_entry || group_entry == isl_hash_table_entry_none)
 261                 return group_entry;
 262         if (reserve && !group_entry->data) {
 263                 isl_space *domain = isl_space_domain(isl_space_copy(space));
 264                 group = FN(UNION,group_alloc)(domain, 1);
 265                 group_entry->data = group;
 266         } else {
 267                 group = group_entry->data;
 268                 if (reserve)
 269                         group = FN(UNION,group_cow)(group);
 270         }
 271         if (!group)
 272                 return NULL;
 273         hash = isl_space_get_hash(space);
 274         return isl_hash_table_find(ctx, &group->part_table, hash,
 275                                 &FN(UNION,has_space), space, reserve);
 276 }
 277
 278 /* Remove "part_entry" from the hash table of "u".
 279  *
 280  * First look the group_entry in "u" holding the group that
 281  * contains "part_entry".  Remove "part_entry" from that group.
 282  * If the group becomes empty, then also remove the group_entry from "u".
 283  */
 284 static __isl_give UNION *FN(UNION,remove_part_entry)(__isl_take UNION *u,
 285         struct isl_hash_table_entry *part_entry)
 286 {
 287         isl_ctx *ctx;
 288         uint32_t hash;
 289         isl_space *space;
 290         PART *part;
 291         struct isl_hash_table_entry *group_entry;
 292         S(UNION,group) *group;
 293
 294         if (!u || !part_entry)
 295                 return FN(UNION,free)(u);
 296
 297         part = part_entry->data;
 298         ctx = FN(UNION,get_ctx)(u);
 299         space = FN(PART,peek_space)(part);
 300         hash = isl_space_get_domain_hash(space);
 301         group_entry = isl_hash_table_find(ctx, &u->table, hash,
 302                             &FN(UNION,group_has_same_domain_space), space, 0);
 303         if (!group_entry)
 304                 return FN(UNION,free)(u);
 305         if (group_entry == isl_hash_table_entry_none)
 306                 isl_die(ctx, isl_error_internal, "missing group",
 307                         return FN(UNION,free)(u));
 308         group = group_entry->data;
 309         isl_hash_table_remove(ctx, &group->part_table, part_entry);
 310         FN(PART,free)(part);
 311
 312         if (group->part_table.n != 0)
 313                 return u;
 314
 315         isl_hash_table_remove(ctx, &u->table, group_entry);
 316         FN(UNION,group_free)(group);
 317
 318         return u;
 319 }
 320
 321 /* Are the domains of "part1" and "part2" disjoint?
 322  */
 323 static isl_bool FN(UNION,disjoint_domain)(__isl_keep PART *part1,
 324         __isl_keep PART *part2)
 325 {
 326         isl_set *dom1, *dom2;
 327         isl_bool disjoint;
 328
 329         if (!part1 || !part2)
 330                 return isl_bool_error;
 331         dom1 = FN(PART,domain)(FN(PART,copy)(part1));
 332         dom2 = FN(PART,domain)(FN(PART,copy)(part2));
 333         disjoint = isl_set_is_disjoint(dom1, dom2);
 334         isl_set_free(dom1);
 335         isl_set_free(dom2);
 336
 337         return disjoint;
 338 }
 339
 340 /* Check that the expression at *entry has a domain that is disjoint
 341  * from that of "part", unless they also have the same target space.
 342  */
 343 static isl_stat FN(UNION,check_disjoint_domain_entry)(void **entry, void *user)
 344 {
 345         PART *part = user;
 346         PART *other = *entry;
 347         isl_bool equal;
 348         isl_bool disjoint;
 349
 350         equal = isl_space_is_equal(part->dim, other->dim);
 351         if (equal < 0)
 352                 return isl_stat_error;
 353         if (equal)
 354                 return isl_stat_ok;
 355
 356         disjoint = FN(UNION,disjoint_domain)(part, other);
 357         if (disjoint < 0)
 358                 return isl_stat_error;
 359         if (!disjoint)
 360                 isl_die(FN(PART,get_ctx)(part), isl_error_invalid,
 361                         "overlapping domain with other part",
 362                         return isl_stat_error);
 363         return isl_stat_ok;
 364 }
 365
 366 /* Check that the domain of "part" is disjoint from the domain of the entries
 367  * in "u" that are defined on the same domain space, but have a different
 368  * target space.
 369  * If there is no group of expressions in "u" with the same domain space,
 370  * then everything is fine.  Otherwise, check the individual expressions
 371  * in that group.
 372  */
 373 static isl_stat FN(UNION,check_disjoint_domain_other)(__isl_keep UNION *u,
 374         __isl_keep PART *part)
 375 {
 376         isl_ctx *ctx;
 377         uint32_t hash;
 378         isl_space *space;
 379         struct isl_hash_table_entry *group_entry;
 380         S(UNION,group) *group;
 381
 382         if (!u || !part)
 383                 return isl_stat_error;
 384         ctx = FN(UNION,get_ctx)(u);
 385         space = FN(PART,peek_space)(part);
 386         hash = isl_space_get_domain_hash(space);
 387         group_entry = isl_hash_table_find(ctx, &u->table, hash,
 388                             &FN(UNION,group_has_same_domain_space), space, 0);
 389         if (!group_entry)
 390                 return isl_stat_error;
 391         if (group_entry == isl_hash_table_entry_none)
 392                 return isl_stat_ok;
 393         group = group_entry->data;
 394         return isl_hash_table_foreach(ctx, &group->part_table,
 395                               &FN(UNION,check_disjoint_domain_entry), part);
 396 }
 397
 398 /* Check that the domain of "part1" is disjoint from the domain of "part2".
 399  * This check is performed before "part2" is added to a UNION to ensure
 400  * that the UNION expression remains a function.
 401  */
 402 static isl_stat FN(UNION,check_disjoint_domain)(__isl_keep PART *part1,
 403         __isl_keep PART *part2)
 404 {
 405         isl_bool disjoint;
 406
 407         disjoint = FN(UNION,disjoint_domain)(part1, part2);
 408         if (disjoint < 0)
 409                 return isl_stat_error;
 410         if (!disjoint)
 411                 isl_die(FN(PART,get_ctx)(part1), isl_error_invalid,
 412                         "domain of additional part should be disjoint",
 413                         return isl_stat_error);
 414         return isl_stat_ok;
 415 }
 416
 417 /* Internal data structure for isl_union_*_foreach_inplace.
 418  * "fn" is the function that needs to be called on each entry.
 419  */
 420 S(UNION,foreach_inplace_data)
 421 {
 422         isl_stat (*fn)(void **entry, void *user);
 423         void *user;
 424 };
 425
 426 /* isl_union_*_foreach_group callback for calling data->fn on
 427  * each part entry in the group.
 428  */
 429 static isl_stat FN(UNION,group_call_inplace)(__isl_keep S(UNION,group) *group,
 430         void *user)
 431 {
 432         isl_ctx *ctx;
 433         S(UNION,foreach_inplace_data) *data;
 434
 435         if (!group)
 436                 return isl_stat_error;
 437
 438         data = (S(UNION,foreach_inplace_data) *) user;
 439         ctx = isl_space_get_ctx(group->domain_space);
 440         return isl_hash_table_foreach(ctx, &group->part_table,
 441                                       data->fn, data->user);
 442 }
 443
 444 /* Call "fn" on each part entry of "u".
 445  */
 446 static isl_stat FN(UNION,foreach_inplace)(__isl_keep UNION *u,
 447         isl_stat (*fn)(void **part, void *user), void *user)
 448 {
 449         S(UNION,foreach_inplace_data) data = { fn, user };
 450
 451         return FN(UNION,foreach_group)(u, &FN(UNION,group_call_inplace), &data);
 452 }
 453
 454 static isl_stat FN(UNION,free_u_entry)(void **entry, void *user)
 455 {
 456         S(UNION,group) *group = *entry;
 457         FN(UNION,group_free)(group);
 458         return isl_stat_ok;
 459 }
 460
 461 /* Set "single" to true if this group of expressions
 462  * contains an expression living in exactly one space.
 463  */
 464 static isl_stat FN(UNION,group_single_space)(__isl_keep S(UNION,group) *group,
 465         void *user)
 466 {
 467         isl_bool *single = user;
 468
 469         if (!group)
 470                 return isl_stat_error;
 471         *single = isl_bool_ok(group->part_table.n == 1);
 472         return isl_stat_ok;
 473 }
 474
 475 /* Can this union expression be converted to a single base expression?
 476  * That is, does it contain a base expression in exactly one space?
 477  * In particular, is only one domain space involved and
 478  * is only a single expression associated to that domain?
 479  */
 480 isl_bool FN(FN(UNION,isa),BASE)(__isl_take UNION *u)
 481 {
 482         isl_bool single;
 483
 484         if (!u)
 485                 return isl_bool_error;
 486         if (u->table.n != 1)
 487                 return isl_bool_false;
 488         if (FN(UNION,foreach_group)(u,
 489                                 &FN(UNION,group_single_space), &single) < 0)
 490                 return isl_bool_error;
 491         return single;
 492 }
 493
 494 /* Callback for isl_union_*_foreach_inplace call
 495  * on a union expression with a single base expression.
 496  * Store that base expression in "user".
 497  * This callback should only be called once
 498  * for any given isl_union_*_foreach_inplace call.
 499  */
 500 static isl_stat FN(UNION,extract_part)(void **entry, void *user)
 501 {
 502         PART **part_p = user;
 503         PART *part = *entry;
 504
 505         if (*part_p)
 506                 isl_die(FN(PART,get_ctx)(part), isl_error_internal,
 507                         "more than one part", return isl_stat_error);
 508         *part_p = FN(PART,copy)(part);
 509         if (!*part_p)
 510                 return isl_stat_error;
 511         return isl_stat_ok;
 512 }
 513
 514 /* Convert the union expression to its single base expression.
 515  */
 516 __isl_give PART *FN(FN(UNION,as),BASE)(__isl_take UNION *u)
 517 {
 518         isl_bool has_single_space;
 519         PART *part = NULL;
 520
 521         has_single_space = FN(FN(UNION,isa),BASE)(u);
 522         if (has_single_space < 0)
 523                 goto error;
 524         if (!has_single_space)
 525                 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
 526                         "expecting elements in exactly one space",
 527                         goto error);
 528         if (FN(UNION,foreach_inplace)(u, &FN(UNION,extract_part), &part) < 0)
 529                 part = FN(PART,free)(part);
 530         FN(UNION,free)(u);
 531         return part;
 532 error:
 533         FN(UNION,free)(u);
 534         return NULL;
 535 }
 536
 537 #include <isl_union_templ.c>