isl_union_single.c

   1 /*
   2  * Copyright 2010      INRIA Saclay
   3  * Copyright 2013      Ecole Normale Superieure
   4  *
   5  * Use of this software is governed by the MIT license
   6  *
   7  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   8  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   9  * 91893 Orsay, France
  10  * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
  11  */
  12
  13 #include <isl_hash_private.h>
  14 #include <isl_union_macro.h>
  15
  16 /* A union of expressions defined over different domain spaces.
  17  * "space" describes the parameters.
  18  * The entries of "table" are keyed on the domain space of the entry.
  19  */
  20 struct UNION {
  21         int ref;
  22 #ifdef HAS_TYPE
  23         enum isl_fold type;
  24 #endif
  25         isl_space *space;
  26
  27         struct isl_hash_table   table;
  28 };
  29
  30 /* Return the number of base expressions in "u".
  31  */
  32 int FN(FN(UNION,n),PARTS)(__isl_keep UNION *u)
  33 {
  34         return u ? u->table.n : 0;
  35 }
  36
  37 S(UNION,foreach_data)
  38 {
  39         isl_stat (*fn)(__isl_take PART *part, void *user);
  40         void *user;
  41 };
  42
  43 static isl_stat FN(UNION,call_on_copy)(void **entry, void *user)
  44 {
  45         PART *part = *entry;
  46         S(UNION,foreach_data) *data = (S(UNION,foreach_data) *)user;
  47
  48         part = FN(PART,copy)(part);
  49         if (!part)
  50                 return isl_stat_error;
  51         return data->fn(part, data->user);
  52 }
  53
  54 isl_stat FN(FN(UNION,foreach),PARTS)(__isl_keep UNION *u,
  55         isl_stat (*fn)(__isl_take PART *part, void *user), void *user)
  56 {
  57         S(UNION,foreach_data) data = { fn, user };
  58
  59         if (!u)
  60                 return isl_stat_error;
  61
  62         return isl_hash_table_foreach(u->space->ctx, &u->table,
  63                                       &FN(UNION,call_on_copy), &data);
  64 }
  65
  66 /* Is the domain space of "entry" equal to the domain of "space"?
  67  */
  68 static int FN(UNION,has_same_domain_space)(const void *entry, const void *val)
  69 {
  70         PART *part = (PART *)entry;
  71         isl_space *space = (isl_space *) val;
  72
  73         if (isl_space_is_set(space))
  74                 return isl_space_is_set(part->dim);
  75
  76         return isl_space_tuple_is_equal(part->dim, isl_dim_in,
  77                                         space, isl_dim_in);
  78 }
  79
  80 /* Return the entry, if any, in "u" that lives in "space".
  81  * If "reserve" is set, then an entry is created if it does not exist yet.
  82  * Return NULL on error and isl_hash_table_entry_none if no entry was found.
  83  * Note that when "reserve" is set, the function will never return
  84  * isl_hash_table_entry_none.
  85  *
  86  * First look for the entry (if any) with the same domain space.
  87  * If it exists, then check if the range space also matches.
  88  */
  89 static struct isl_hash_table_entry *FN(UNION,find_part_entry)(
  90         __isl_keep UNION *u, __isl_keep isl_space *space, int reserve)
  91 {
  92         isl_ctx *ctx;
  93         uint32_t hash;
  94         struct isl_hash_table_entry *entry;
  95         isl_bool equal;
  96         PART *part;
  97
  98         if (!u || !space)
  99                 return NULL;
 100
 101         ctx = FN(UNION,get_ctx)(u);
 102         hash = isl_space_get_domain_hash(space);
 103         entry = isl_hash_table_find(ctx, &u->table, hash,
 104                         &FN(UNION,has_same_domain_space), space, reserve);
 105         if (!entry)
 106                 return reserve ? NULL : isl_hash_table_entry_none;
 107         if (reserve && !entry->data)
 108                 return entry;
 109         part = entry->data;
 110         equal = isl_space_tuple_is_equal(part->dim, isl_dim_out,
 111                                             space, isl_dim_out);
 112         if (equal < 0)
 113                 return NULL;
 114         if (equal)
 115                 return entry;
 116         if (!reserve)
 117                 return isl_hash_table_entry_none;
 118         isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
 119                 "union expression can only contain a single "
 120                 "expression over a given domain", return NULL);
 121 }
 122
 123 /* Remove "part_entry" from the hash table of "u".
 124  */
 125 static __isl_give UNION *FN(UNION,remove_part_entry)(__isl_take UNION *u,
 126         struct isl_hash_table_entry *part_entry)
 127 {
 128         isl_ctx *ctx;
 129
 130         if (!u || !part_entry)
 131                 return FN(UNION,free)(u);
 132
 133         ctx = FN(UNION,get_ctx)(u);
 134         isl_hash_table_remove(ctx, &u->table, part_entry);
 135         FN(PART,free)(part_entry->data);
 136
 137         return u;
 138 }
 139
 140 /* Check that the domain of "part" is disjoint from the domain of the entries
 141  * in "u" that are defined on the same domain space, but have a different
 142  * target space.
 143  * Since a UNION with a single entry per domain space is not allowed
 144  * to contain two entries with the same domain space, there cannot be
 145  * any such other entry.
 146  */
 147 static isl_stat FN(UNION,check_disjoint_domain_other)(__isl_keep UNION *u,
 148         __isl_keep PART *part)
 149 {
 150         return isl_stat_ok;
 151 }
 152
 153 /* Check that the domain of "part1" is disjoint from the domain of "part2".
 154  * This check is performed before "part2" is added to a UNION to ensure
 155  * that the UNION expression remains a function.
 156  * Since a UNION with a single entry per domain space is not allowed
 157  * to contain two entries with the same domain space, fail unconditionally.
 158  */
 159 static isl_stat FN(UNION,check_disjoint_domain)(__isl_keep PART *part1,
 160         __isl_keep PART *part2)
 161 {
 162         isl_die(FN(PART,get_ctx)(part1), isl_error_invalid,
 163                 "additional part should live on separate space",
 164                 return isl_stat_error);
 165 }
 166
 167 /* Call "fn" on each part entry of "u".
 168  */
 169 static isl_stat FN(UNION,foreach_inplace)(__isl_keep UNION *u,
 170         isl_stat (*fn)(void **part, void *user), void *user)
 171 {
 172         isl_ctx *ctx;
 173
 174         if (!u)
 175                 return isl_stat_error;
 176         ctx = FN(UNION,get_ctx)(u);
 177         return isl_hash_table_foreach(ctx, &u->table, fn, user);
 178 }
 179
 180 /* Does "u" have a single reference?
 181  * That is, can we change "u" inplace?
 182  */
 183 static isl_bool FN(UNION,has_single_reference)(__isl_keep UNION *u)
 184 {
 185         if (!u)
 186                 return isl_bool_error;
 187         return u->ref == 1;
 188 }
 189
 190 static isl_stat FN(UNION,free_u_entry)(void **entry, void *user)
 191 {
 192         PART *part = *entry;
 193         FN(PART,free)(part);
 194         return isl_stat_ok;
 195 }
 196
 197 #include <isl_union_templ.c>