polly/lib/External/isl/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.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  * (ignoring parameters).
  20  */
  21 struct UNION {
  22         int ref;
  23 #ifdef HAS_TYPE
  24         enum isl_fold type;
  25 #endif
  26         isl_space *space;
  27
  28         struct isl_hash_table   table;
  29 };
  30
  31 /* Return the number of base expressions in "u".
  32  */
  33 isl_size FN(FN(UNION,n),BASE)(__isl_keep UNION *u)
  34 {
  35         return u ? u->table.n : isl_size_error;
  36 }
  37
  38 S(UNION,foreach_data)
  39 {
  40         isl_stat (*fn)(__isl_take PART *part, void *user);
  41         void *user;
  42 };
  43
  44 static isl_stat FN(UNION,call_on_copy)(void **entry, void *user)
  45 {
  46         PART *part = *entry;
  47         S(UNION,foreach_data) *data = (S(UNION,foreach_data) *)user;
  48
  49         part = FN(PART,copy)(part);
  50         if (!part)
  51                 return isl_stat_error;
  52         return data->fn(part, data->user);
  53 }
  54
  55 isl_stat FN(FN(UNION,foreach),BASE)(__isl_keep UNION *u,
  56         isl_stat (*fn)(__isl_take PART *part, void *user), void *user)
  57 {
  58         S(UNION,foreach_data) data = { fn, user };
  59
  60         if (!u)
  61                 return isl_stat_error;
  62
  63         return isl_hash_table_foreach(u->space->ctx, &u->table,
  64                                       &FN(UNION,call_on_copy), &data);
  65 }
  66
  67 /* Is the domain space of "entry" equal to the domain of "space",
  68  * ignoring parameters?
  69  */
  70 static isl_bool FN(UNION,has_same_domain_space_tuples)(const void *entry,
  71         const void *val)
  72 {
  73         PART *part = (PART *)entry;
  74         isl_space *space = (isl_space *) val;
  75
  76         if (isl_space_is_set(space))
  77                 return isl_space_is_set(part->dim);
  78
  79         return isl_space_tuple_is_equal(part->dim, isl_dim_in,
  80                                         space, isl_dim_in);
  81 }
  82
  83 /* Return the entry, if any, in "u" that lives in "space".
  84  * If "reserve" is set, then an entry is created if it does not exist yet.
  85  * Return NULL on error and isl_hash_table_entry_none if no entry was found.
  86  * Note that when "reserve" is set, the function will never return
  87  * isl_hash_table_entry_none.
  88  *
  89  * First look for the entry (if any) with the same domain space.
  90  * If it exists, then check if the range space also matches.
  91  */
  92 static struct isl_hash_table_entry *FN(UNION,find_part_entry)(
  93         __isl_keep UNION *u, __isl_keep isl_space *space, int reserve)
  94 {
  95         isl_ctx *ctx;
  96         uint32_t hash;
  97         struct isl_hash_table_entry *entry;
  98         isl_bool equal;
  99         PART *part;
 100
 101         if (!u || !space)
 102                 return NULL;
 103
 104         ctx = FN(UNION,get_ctx)(u);
 105         hash = isl_space_get_tuple_domain_hash(space);
 106         entry = isl_hash_table_find(ctx, &u->table, hash,
 107                 &FN(UNION,has_same_domain_space_tuples), space, reserve);
 108         if (!entry || entry == isl_hash_table_entry_none)
 109                 return entry;
 110         if (reserve && !entry->data)
 111                 return entry;
 112         part = entry->data;
 113         equal = isl_space_tuple_is_equal(part->dim, isl_dim_out,
 114                                             space, isl_dim_out);
 115         if (equal < 0)
 116                 return NULL;
 117         if (equal)
 118                 return entry;
 119         if (!reserve)
 120                 return isl_hash_table_entry_none;
 121         isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
 122                 "union expression can only contain a single "
 123                 "expression over a given domain", return NULL);
 124 }
 125
 126 /* Remove "part_entry" from the hash table of "u".
 127  */
 128 static __isl_give UNION *FN(UNION,remove_part_entry)(__isl_take UNION *u,
 129         struct isl_hash_table_entry *part_entry)
 130 {
 131         isl_ctx *ctx;
 132
 133         if (!u || !part_entry)
 134                 return FN(UNION,free)(u);
 135
 136         FN(PART,free)(part_entry->data);
 137         ctx = FN(UNION,get_ctx)(u);
 138         isl_hash_table_remove(ctx, &u->table, part_entry);
 139
 140         return u;
 141 }
 142
 143 /* Check that the domain of "part" is disjoint from the domain of the entries
 144  * in "u" that are defined on the same domain space, but have a different
 145  * target space.
 146  * Since a UNION with a single entry per domain space is not allowed
 147  * to contain two entries with the same domain space, there cannot be
 148  * any such other entry.
 149  */
 150 static isl_stat FN(UNION,check_disjoint_domain_other)(__isl_keep UNION *u,
 151         __isl_keep PART *part)
 152 {
 153         return isl_stat_ok;
 154 }
 155
 156 /* Check that the domain of "part1" is disjoint from the domain of "part2".
 157  * This check is performed before "part2" is added to a UNION to ensure
 158  * that the UNION expression remains a function.
 159  * Since a UNION with a single entry per domain space is not allowed
 160  * to contain two entries with the same domain space, fail unconditionally.
 161  */
 162 static isl_stat FN(UNION,check_disjoint_domain)(__isl_keep PART *part1,
 163         __isl_keep PART *part2)
 164 {
 165         isl_die(FN(PART,get_ctx)(part1), isl_error_invalid,
 166                 "additional part should live on separate space",
 167                 return isl_stat_error);
 168 }
 169
 170 /* Call "fn" on each part entry of "u".
 171  */
 172 static isl_stat FN(UNION,foreach_inplace)(__isl_keep UNION *u,
 173         isl_stat (*fn)(void **part, void *user), void *user)
 174 {
 175         isl_ctx *ctx;
 176
 177         if (!u)
 178                 return isl_stat_error;
 179         ctx = FN(UNION,get_ctx)(u);
 180         return isl_hash_table_foreach(ctx, &u->table, fn, user);
 181 }
 182
 183 static isl_bool FN(PART,has_domain_space_tuples)(__isl_keep PART *part,
 184         __isl_keep isl_space *space);
 185
 186 /* Do the tuples of "space" correspond to those of the domain of "part"?
 187  * That is, is the domain space of "part" equal to "space", ignoring parameters?
 188  */
 189 static isl_bool FN(UNION,has_domain_space_tuples)(const void *entry,
 190         const void *val)
 191 {
 192         PART *part = (PART *)entry;
 193         isl_space *space = (isl_space *) val;
 194
 195         return FN(PART,has_domain_space_tuples)(part, space);
 196 }
 197
 198 /* Call "fn" on each part of "u" that has domain space "space".
 199  *
 200  * Since each entry is defined over a different domain space,
 201  * simply look for an entry with the given domain space and
 202  * call "fn" on the corresponding part if there is one.
 203  */
 204 isl_stat FN(UNION,foreach_on_domain)(__isl_keep UNION *u,
 205         __isl_keep isl_space *space,
 206         isl_stat (*fn)(__isl_take PART *part, void *user), void *user)
 207 {
 208         uint32_t hash;
 209         struct isl_hash_table_entry *entry;
 210
 211         if (!u || !space)
 212                 return isl_stat_error;
 213         hash = isl_space_get_tuple_hash(space);
 214         entry = isl_hash_table_find(FN(UNION,get_ctx)(u), &u->table,
 215                                     hash, &FN(UNION,has_domain_space_tuples),
 216                                     space, 0);
 217         if (!entry)
 218                 return isl_stat_error;
 219         if (entry == isl_hash_table_entry_none)
 220                 return isl_stat_ok;
 221         return fn(FN(PART,copy)(entry->data), user);
 222 }
 223
 224 static isl_stat FN(UNION,free_u_entry)(void **entry, void *user)
 225 {
 226         PART *part = *entry;
 227         FN(PART,free)(part);
 228         return isl_stat_ok;
 229 }
 230
 231 #include <isl_union_templ.c>