232 lines · c
1/*2 * Copyright 2010 INRIA Saclay3 * Copyright 2013 Ecole Normale Superieure4 *5 * Use of this software is governed by the MIT license6 *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, France10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France11 */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 entry19 * (ignoring parameters).20 */21struct UNION {22 int ref;23#ifdef HAS_TYPE24 enum isl_fold type;25#endif26 isl_space *space;27 28 struct isl_hash_table table;29};30 31/* Return the number of base expressions in "u".32 */33isl_size FN(FN(UNION,n),BASE)(__isl_keep UNION *u)34{35 return u ? u->table.n : isl_size_error;36}37 38S(UNION,foreach_data)39{40 isl_stat (*fn)(__isl_take PART *part, void *user);41 void *user;42};43 44static 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 55isl_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 */70static 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 return87 * 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 */92static 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 */128static __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 entries144 * in "u" that are defined on the same domain space, but have a different145 * target space.146 * Since a UNION with a single entry per domain space is not allowed147 * to contain two entries with the same domain space, there cannot be148 * any such other entry.149 */150static 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 ensure158 * that the UNION expression remains a function.159 * Since a UNION with a single entry per domain space is not allowed160 * to contain two entries with the same domain space, fail unconditionally.161 */162static 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 */172static 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 183static 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 */189static 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 and202 * call "fn" on the corresponding part if there is one.203 */204isl_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 224static 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>232