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> 232