File: isl_union_multi.c

package info (click to toggle)
isl 0.20-2
  • links: PTS
  • area: main
  • in suites: buster, sid
  • size: 12,708 kB
  • sloc: ansic: 125,702; python: 5,770; sh: 4,291; cpp: 1,057; makefile: 497; lisp: 54; perl: 9
file content (465 lines) | stat: -rw-r--r-- 12,607 bytes parent folder | download | duplicates (11)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
/*
 * Copyright 2010      INRIA Saclay
 * Copyright 2013      Ecole Normale Superieure
 * Copyright 2015      INRIA Paris-Rocquencourt
 *
 * Use of this software is governed by the MIT license
 *
 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
 * 91893 Orsay, France
 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
 * and INRIA Paris-Rocquencourt, Domaine de Voluceau, Rocquenqourt, B.P. 105,
 * 78153 Le Chesnay Cedex France
 */

#include <isl_hash_private.h>
#include <isl_union_macro.h>

/* A group of expressions defined over the same domain space "domain_space".
 * The entries of "part_table" are the individual expressions,
 * keyed on the entire space of the expression.
 *
 * Each UNION has its own groups, so there can only ever be a single
 * reference to each group.
 */
S(UNION,group) {
	isl_space *domain_space;
	struct isl_hash_table	part_table;
};

/* A union of expressions defined over different disjoint domains.
 * "space" describes the parameters.
 * The entries of "table" are keyed on the domain space of the entry and
 * contain groups of expressions that are defined over the same domain space.
 */
struct UNION {
	int ref;
	isl_space *space;

	struct isl_hash_table	table;
};

/* Internal data structure for isl_union_*_foreach_group.
 * "fn" is the function that needs to be called on each group.
 */
S(UNION,foreach_group_data)
{
	isl_stat (*fn)(__isl_keep S(UNION,group) *group, void *user);
	void *user;
};

/* Call data->fn on the group stored at *entry.
 */
static isl_stat FN(UNION,call_on_group)(void **entry, void *user)
{
	S(UNION,group) *group = *entry;
	S(UNION,foreach_group_data) *data;

	data = (S(UNION,foreach_group_data) *) user;
	return data->fn(group, data->user);
}

/* Call "fn" on each group of expressions in "u".
 */
static isl_stat FN(UNION,foreach_group)(__isl_keep UNION *u,
	isl_stat (*fn)(__isl_keep S(UNION,group) *group, void *user),
	void *user)
{
	S(UNION,foreach_group_data) data = { fn, user };

	if (!u)
		return isl_stat_error;

	return isl_hash_table_foreach(u->space->ctx, &u->table,
				      &FN(UNION,call_on_group), &data);
}

/* A isl_union_*_foreach_group callback for counting the total number
 * of expressions in a UNION.  Add the number of expressions in "group"
 * to *n.
 */
static isl_stat FN(UNION,count_part)(__isl_keep S(UNION,group) *group,
	void *user)
{
	int *n = user;

	if (!group)
		return isl_stat_error;

	*n += group->part_table.n;
	return isl_stat_ok;
}

/* Return the number of base expressions in "u".
 */
int FN(FN(UNION,n),BASE)(__isl_keep UNION *u)
{
	int n;

	n = 0;
	if (FN(UNION,foreach_group)(u, &FN(UNION,count_part), &n) < 0)
		n = -1;
	return n;
}

/* Free an entry in a group of expressions.
 * Each entry in such a group is a single expression.
 */
static isl_stat FN(UNION,free_group_entry)(void **entry, void *user)
{
	PART *part = *entry;

	FN(PART,free)(part);
	return isl_stat_ok;
}

/* Free all memory allocated for "group" and return NULL.
 */
static __isl_null S(UNION,group) *FN(UNION,group_free)(
	__isl_take S(UNION,group) *group)
{
	isl_ctx *ctx;

	if (!group)
		return NULL;

	ctx = isl_space_get_ctx(group->domain_space);
	isl_hash_table_foreach(ctx, &group->part_table,
				&FN(UNION,free_group_entry), NULL);
	isl_hash_table_clear(&group->part_table);
	isl_space_free(group->domain_space);
	free(group);
	return NULL;
}

/* Allocate a group of expressions defined over the same domain space
 * with domain space "domain_space" and initial size "size".
 */
static __isl_give S(UNION,group) *FN(UNION,group_alloc)(
	__isl_take isl_space *domain_space, int size)
{
	isl_ctx *ctx;
	S(UNION,group) *group;

	if (!domain_space)
		return NULL;
	ctx = isl_space_get_ctx(domain_space);
	group = isl_calloc_type(ctx, S(UNION,group));
	if (!group)
		goto error;
	group->domain_space = domain_space;
	if (isl_hash_table_init(ctx, &group->part_table, size) < 0)
		return FN(UNION,group_free)(group);

	return group;
error:
	isl_space_free(domain_space);
	return NULL;
}

/* Is the space of "entry" equal to "space"?
 */
static int FN(UNION,has_space)(const void *entry, const void *val)
{
	PART *part = (PART *) entry;
	isl_space *space = (isl_space *) val;

	return isl_space_is_equal(part->dim, space);
}

/* Return a group equal to "group", but with a single reference.
 * Since all groups have only a single reference, simply return "group".
 */
static __isl_give S(UNION,group) *FN(UNION,group_cow)(
	__isl_take S(UNION,group) *group)
{
	return group;
}

S(UNION,foreach_data)
{
	isl_stat (*fn)(__isl_take PART *part, void *user);
	void *user;
};

static isl_stat FN(UNION,call_on_copy)(void **entry, void *user)
{
	PART *part = *entry;
	S(UNION,foreach_data) *data = (S(UNION,foreach_data) *) user;

	part = FN(PART,copy)(part);
	if (!part)
		return isl_stat_error;
	return data->fn(part, data->user);
}

/* Call data->fn on a copy of each expression in "group".
 */
static isl_stat FN(UNION,group_call_on_copy)(__isl_keep S(UNION,group) *group,
	void *user)
{
	isl_ctx *ctx;

	if (!group)
		return isl_stat_error;

	ctx = isl_space_get_ctx(group->domain_space);
	return isl_hash_table_foreach(ctx, &group->part_table,
				      &FN(UNION,call_on_copy), user);
}

isl_stat FN(FN(UNION,foreach),BASE)(__isl_keep UNION *u,
	isl_stat (*fn)(__isl_take PART *part, void *user), void *user)
{
	S(UNION,foreach_data) data = { fn, user };

	if (!u)
		return isl_stat_error;

	return FN(UNION,foreach_group)(u, &FN(UNION,group_call_on_copy), &data);
}

/* Is the domain space of the group of expressions at "entry"
 * equal to "space"?
 */
static int FN(UNION,group_has_domain_space)(const void *entry, const void *val)
{
	S(UNION,group) *group = (S(UNION,group) *) entry;
	isl_space *space = (isl_space *) val;

	return isl_space_is_domain_internal(group->domain_space, space);
}

/* Return the entry, if any, in "u" that lives in "space".
 * If "reserve" is set, then an entry is created if it does not exist yet.
 * Return NULL on error and isl_hash_table_entry_none if no entry was found.
 * Note that when "reserve" is set, the function will never return
 * isl_hash_table_entry_none.
 *
 * First look for the group of expressions with the same domain space,
 * creating one if needed.
 * Then look for the expression living in the specified space in that group.
 */
static struct isl_hash_table_entry *FN(UNION,find_part_entry)(
	__isl_keep UNION *u, __isl_keep isl_space *space, int reserve)
{
	isl_ctx *ctx;
	uint32_t hash;
	struct isl_hash_table_entry *group_entry, *part_entry;
	S(UNION,group) *group;

	if (!u || !space)
		return NULL;

	ctx = FN(UNION,get_ctx)(u);
	hash = isl_space_get_domain_hash(space);
	group_entry = isl_hash_table_find(ctx, &u->table, hash,
			    &FN(UNION,group_has_domain_space), space, reserve);
	if (!group_entry)
		return reserve ? NULL : isl_hash_table_entry_none;
	if (reserve && !group_entry->data) {
		isl_space *domain = isl_space_domain(isl_space_copy(space));
		group = FN(UNION,group_alloc)(domain, 1);
		group_entry->data = group;
	} else {
		group = group_entry->data;
		if (reserve)
			group = FN(UNION,group_cow)(group);
	}
	if (!group)
		return NULL;
	hash = isl_space_get_hash(space);
	part_entry = isl_hash_table_find(ctx, &group->part_table, hash,
				&FN(UNION,has_space), space, reserve);
	if (!reserve && !part_entry)
		return isl_hash_table_entry_none;
	return part_entry;
}

/* Remove "part_entry" from the hash table of "u".
 *
 * First look the group_entry in "u" holding the group that
 * contains "part_entry".  Remove "part_entry" from that group.
 * If the group becomes empty, then also remove the group_entry from "u".
 */
static __isl_give UNION *FN(UNION,remove_part_entry)(__isl_take UNION *u,
	struct isl_hash_table_entry *part_entry)
{
	isl_ctx *ctx;
	uint32_t hash;
	PART *part;
	struct isl_hash_table_entry *group_entry;
	S(UNION,group) *group;

	if (!u || !part_entry)
		return FN(UNION,free)(u);

	part = part_entry->data;
	ctx = FN(UNION,get_ctx)(u);
	hash = isl_space_get_domain_hash(part->dim);
	group_entry = isl_hash_table_find(ctx, &u->table, hash,
			    &FN(UNION,group_has_domain_space), part->dim, 0);
	if (!group_entry)
		isl_die(ctx, isl_error_internal, "missing group",
			return FN(UNION,free)(u));
	group = group_entry->data;
	isl_hash_table_remove(ctx, &group->part_table, part_entry);
	FN(PART,free)(part);

	if (group->part_table.n != 0)
		return u;

	isl_hash_table_remove(ctx, &u->table, group_entry);
	FN(UNION,group_free)(group);

	return u;
}

/* Are the domains of "part1" and "part2" disjoint?
 */
static isl_bool FN(UNION,disjoint_domain)(__isl_keep PART *part1,
	__isl_keep PART *part2)
{
	isl_set *dom1, *dom2;
	isl_bool disjoint;

	if (!part1 || !part2)
		return isl_bool_error;
	dom1 = FN(PART,domain)(FN(PART,copy)(part1));
	dom2 = FN(PART,domain)(FN(PART,copy)(part2));
	disjoint = isl_set_is_disjoint(dom1, dom2);
	isl_set_free(dom1);
	isl_set_free(dom2);

	return disjoint;
}

/* Check that the expression at *entry has a domain that is disjoint
 * from that of "part", unless they also have the same target space.
 */
static isl_stat FN(UNION,check_disjoint_domain_entry)(void **entry, void *user)
{
	PART *part = user;
	PART *other = *entry;
	isl_bool equal;
	isl_bool disjoint;

	equal = isl_space_is_equal(part->dim, other->dim);
	if (equal < 0)
		return isl_stat_error;
	if (equal)
		return isl_stat_ok;

	disjoint = FN(UNION,disjoint_domain)(part, other);
	if (disjoint < 0)
		return isl_stat_error;
	if (!disjoint)
		isl_die(FN(PART,get_ctx)(part), isl_error_invalid,
			"overlapping domain with other part",
			return isl_stat_error);
	return isl_stat_ok;
}

/* Check that the domain of "part" is disjoint from the domain of the entries
 * in "u" that are defined on the same domain space, but have a different
 * target space.
 * If there is no group of expressions in "u" with the same domain space,
 * then everything is fine.  Otherwise, check the individual expressions
 * in that group.
 */
static isl_stat FN(UNION,check_disjoint_domain_other)(__isl_keep UNION *u,
	__isl_keep PART *part)
{
	isl_ctx *ctx;
	uint32_t hash;
	struct isl_hash_table_entry *group_entry;
	S(UNION,group) *group;

	if (!u || !part)
		return isl_stat_error;
	ctx = FN(UNION,get_ctx)(u);
	hash = isl_space_get_domain_hash(part->dim);
	group_entry = isl_hash_table_find(ctx, &u->table, hash,
			    &FN(UNION,group_has_domain_space), part->dim, 0);
	if (!group_entry)
		return isl_stat_ok;
	group = group_entry->data;
	return isl_hash_table_foreach(ctx, &group->part_table,
			      &FN(UNION,check_disjoint_domain_entry), part);
}

/* Check that the domain of "part1" is disjoint from the domain of "part2".
 * This check is performed before "part2" is added to a UNION to ensure
 * that the UNION expression remains a function.
 */
static isl_stat FN(UNION,check_disjoint_domain)(__isl_keep PART *part1,
	__isl_keep PART *part2)
{
	isl_bool disjoint;

	disjoint = FN(UNION,disjoint_domain)(part1, part2);
	if (disjoint < 0)
		return isl_stat_error;
	if (!disjoint)
		isl_die(FN(PART,get_ctx)(part1), isl_error_invalid,
			"domain of additional part should be disjoint",
			return isl_stat_error);
	return isl_stat_ok;
}

/* Internal data structure for isl_union_*_foreach_inplace.
 * "fn" is the function that needs to be called on each entry.
 */
S(UNION,foreach_inplace_data)
{
	isl_stat (*fn)(void **entry, void *user);
	void *user;
};

/* isl_union_*_foreach_group callback for calling data->fn on
 * each part entry in the group.
 */
static isl_stat FN(UNION,group_call_inplace)(__isl_keep S(UNION,group) *group,
	void *user)
{
	isl_ctx *ctx;
	S(UNION,foreach_inplace_data) *data;

	if (!group)
		return isl_stat_error;

	data = (S(UNION,foreach_inplace_data) *) user;
	ctx = isl_space_get_ctx(group->domain_space);
	return isl_hash_table_foreach(ctx, &group->part_table,
				      data->fn, data->user);
}

/* Call "fn" on each part entry of "u".
 */
static isl_stat FN(UNION,foreach_inplace)(__isl_keep UNION *u,
	isl_stat (*fn)(void **part, void *user), void *user)
{
	S(UNION,foreach_inplace_data) data = { fn, user };

	return FN(UNION,foreach_group)(u, &FN(UNION,group_call_inplace), &data);
}

/* Does "u" have a single reference?
 * That is, can we change "u" inplace?
 */
static isl_bool FN(UNION,has_single_reference)(__isl_keep UNION *u)
{
	if (!u)
		return isl_bool_error;
	return u->ref == 1;
}

static isl_stat FN(UNION,free_u_entry)(void **entry, void *user)
{
	S(UNION,group) *group = *entry;
	FN(UNION,group_free)(group);
	return isl_stat_ok;
}

#include <isl_union_templ.c>