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_private.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 int FN(FN(UNION,n),PARTS)(__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                 n = -1;
 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 int 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),PARTS)(__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 "space"?
 225  */
 226 static int FN(UNION,group_has_domain_space)(const void *entry, const void *val)
 227 {
 228         S(UNION,group) *group = (S(UNION,group) *) entry;
 229         isl_space *space = (isl_space *) val;
 230
 231         return isl_space_is_domain_internal(group->domain_space, space);
 232 }
 233
 234 /* Return the entry, if any, in "u" that lives in "space".
 235  * If "reserve" is set, then an entry is created if it does not exist yet.
 236  * Return NULL on error and isl_hash_table_entry_none if no entry was found.
 237  * Note that when "reserve" is set, the function will never return
 238  * isl_hash_table_entry_none.
 239  *
 240  * First look for the group of expressions with the same domain space,
 241  * creating one if needed.
 242  * Then look for the expression living in the specified space in that group.
 243  */
 244 static struct isl_hash_table_entry *FN(UNION,find_part_entry)(
 245         __isl_keep UNION *u, __isl_keep isl_space *space, int reserve)
 246 {
 247         isl_ctx *ctx;
 248         uint32_t hash;
 249         struct isl_hash_table_entry *group_entry, *part_entry;
 250         S(UNION,group) *group;
 251
 252         if (!u || !space)
 253                 return NULL;
 254
 255         ctx = FN(UNION,get_ctx)(u);
 256         hash = isl_space_get_domain_hash(space);
 257         group_entry = isl_hash_table_find(ctx, &u->table, hash,
 258                             &FN(UNION,group_has_domain_space), space, reserve);
 259         if (!group_entry)
 260                 return reserve ? NULL : isl_hash_table_entry_none;
 261         if (reserve && !group_entry->data) {
 262                 isl_space *domain = isl_space_domain(isl_space_copy(space));
 263                 group = FN(UNION,group_alloc)(domain, 1);
 264                 group_entry->data = group;
 265         } else {
 266                 group = group_entry->data;
 267                 if (reserve)
 268                         group = FN(UNION,group_cow)(group);
 269         }
 270         if (!group)
 271                 return NULL;
 272         hash = isl_space_get_hash(space);
 273         part_entry = isl_hash_table_find(ctx, &group->part_table, hash,
 274                                 &FN(UNION,has_space), space, reserve);
 275         if (!reserve && !part_entry)
 276                 return isl_hash_table_entry_none;
 277         return part_entry;
 278 }
 279
 280 /* Remove "part_entry" from the hash table of "u".
 281  *
 282  * First look the group_entry in "u" holding the group that
 283  * contains "part_entry".  Remove "part_entry" from that group.
 284  * If the group becomes empty, then also remove the group_entry from "u".
 285  */
 286 static __isl_give UNION *FN(UNION,remove_part_entry)(__isl_take UNION *u,
 287         struct isl_hash_table_entry *part_entry)
 288 {
 289         isl_ctx *ctx;
 290         uint32_t hash;
 291         PART *part;
 292         struct isl_hash_table_entry *group_entry;
 293         S(UNION,group) *group;
 294
 295         if (!u || !part_entry)
 296                 return FN(UNION,free)(u);
 297
 298         part = part_entry->data;
 299         ctx = FN(UNION,get_ctx)(u);
 300         hash = isl_space_get_domain_hash(part->dim);
 301         group_entry = isl_hash_table_find(ctx, &u->table, hash,
 302                             &FN(UNION,group_has_domain_space), part->dim, 0);
 303         if (!group_entry)
 304                 isl_die(ctx, isl_error_internal, "missing group",
 305                         return FN(UNION,free)(u));
 306         group = group_entry->data;
 307         isl_hash_table_remove(ctx, &group->part_table, part_entry);
 308         FN(PART,free)(part);
 309
 310         if (group->part_table.n != 0)
 311                 return u;
 312
 313         isl_hash_table_remove(ctx, &u->table, group_entry);
 314         FN(UNION,group_free)(group);
 315
 316         return u;
 317 }
 318
 319 /* Are the domains of "part1" and "part2" disjoint?
 320  */
 321 static isl_bool FN(UNION,disjoint_domain)(__isl_keep PART *part1,
 322         __isl_keep PART *part2)
 323 {
 324         isl_set *dom1, *dom2;
 325         isl_bool disjoint;
 326
 327         if (!part1 || !part2)
 328                 return isl_bool_error;
 329         dom1 = FN(PART,domain)(FN(PART,copy)(part1));
 330         dom2 = FN(PART,domain)(FN(PART,copy)(part2));
 331         disjoint = isl_set_is_disjoint(dom1, dom2);
 332         isl_set_free(dom1);
 333         isl_set_free(dom2);
 334
 335         return disjoint;
 336 }
 337
 338 /* Check that the expression at *entry has a domain that is disjoint
 339  * from that of "part", unless they also have the same target space.
 340  */
 341 static isl_stat FN(UNION,check_disjoint_domain_entry)(void **entry, void *user)
 342 {
 343         PART *part = user;
 344         PART *other = *entry;
 345         isl_bool equal;
 346         isl_bool disjoint;
 347
 348         equal = isl_space_is_equal(part->dim, other->dim);
 349         if (equal < 0)
 350                 return isl_stat_error;
 351         if (equal)
 352                 return isl_stat_ok;
 353
 354         disjoint = FN(UNION,disjoint_domain)(part, other);
 355         if (disjoint < 0)
 356                 return isl_stat_error;
 357         if (!disjoint)
 358                 isl_die(FN(PART,get_ctx)(part), isl_error_invalid,
 359                         "overlapping domain with other part",
 360                         return isl_stat_error);
 361         return isl_stat_ok;
 362 }
 363
 364 /* Check that the domain of "part" is disjoint from the domain of the entries
 365  * in "u" that are defined on the same domain space, but have a different
 366  * target space.
 367  * If there is no group of expressions in "u" with the same domain space,
 368  * then everything is fine.  Otherwise, check the individual expressions
 369  * in that group.
 370  */
 371 static isl_stat FN(UNION,check_disjoint_domain_other)(__isl_keep UNION *u,
 372         __isl_keep PART *part)
 373 {
 374         isl_ctx *ctx;
 375         uint32_t hash;
 376         struct isl_hash_table_entry *group_entry;
 377         S(UNION,group) *group;
 378
 379         if (!u || !part)
 380                 return isl_stat_error;
 381         ctx = FN(UNION,get_ctx)(u);
 382         hash = isl_space_get_domain_hash(part->dim);
 383         group_entry = isl_hash_table_find(ctx, &u->table, hash,
 384                             &FN(UNION,group_has_domain_space), part->dim, 0);
 385         if (!group_entry)
 386                 return isl_stat_ok;
 387         group = group_entry->data;
 388         return isl_hash_table_foreach(ctx, &group->part_table,
 389                               &FN(UNION,check_disjoint_domain_entry), part);
 390 }
 391
 392 /* Check that the domain of "part1" is disjoint from the domain of "part2".
 393  * This check is performed before "part2" is added to a UNION to ensure
 394  * that the UNION expression remains a function.
 395  */
 396 static isl_stat FN(UNION,check_disjoint_domain)(__isl_keep PART *part1,
 397         __isl_keep PART *part2)
 398 {
 399         isl_bool disjoint;
 400
 401         disjoint = FN(UNION,disjoint_domain)(part1, part2);
 402         if (disjoint < 0)
 403                 return isl_stat_error;
 404         if (!disjoint)
 405                 isl_die(FN(PART,get_ctx)(part1), isl_error_invalid,
 406                         "domain of additional part should be disjoint",
 407                         return isl_stat_error);
 408         return isl_stat_ok;
 409 }
 410
 411 /* Internal data structure for isl_union_*_foreach_inplace.
 412  * "fn" is the function that needs to be called on each entry.
 413  */
 414 S(UNION,foreach_inplace_data)
 415 {
 416         isl_stat (*fn)(void **entry, void *user);
 417         void *user;
 418 };
 419
 420 /* isl_union_*_foreach_group callback for calling data->fn on
 421  * each part entry in the group.
 422  */
 423 static isl_stat FN(UNION,group_call_inplace)(__isl_keep S(UNION,group) *group,
 424         void *user)
 425 {
 426         isl_ctx *ctx;
 427         S(UNION,foreach_inplace_data) *data;
 428
 429         if (!group)
 430                 return isl_stat_error;
 431
 432         data = (S(UNION,foreach_inplace_data) *) user;
 433         ctx = isl_space_get_ctx(group->domain_space);
 434         return isl_hash_table_foreach(ctx, &group->part_table,
 435                                       data->fn, data->user);
 436 }
 437
 438 /* Call "fn" on each part entry of "u".
 439  */
 440 static isl_stat FN(UNION,foreach_inplace)(__isl_keep UNION *u,
 441         isl_stat (*fn)(void **part, void *user), void *user)
 442 {
 443         S(UNION,foreach_inplace_data) data = { fn, user };
 444
 445         return FN(UNION,foreach_group)(u, &FN(UNION,group_call_inplace), &data);
 446 }
 447
 448 /* Does "u" have a single reference?
 449  * That is, can we change "u" inplace?
 450  */
 451 static isl_bool FN(UNION,has_single_reference)(__isl_keep UNION *u)
 452 {
 453         if (!u)
 454                 return isl_bool_error;
 455         return u->ref == 1;
 456 }
 457
 458 static isl_stat FN(UNION,free_u_entry)(void **entry, void *user)
 459 {
 460         S(UNION,group) *group = *entry;
 461         FN(UNION,group_free)(group);
 462         return isl_stat_ok;
 463 }
 464
 465 #include <isl_union_templ.c>