Coverage Report

Created: 2017-08-18 19:41

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/External/isl/isl_union_multi.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2010      INRIA Saclay
3
 * Copyright 2013      Ecole Normale Superieure
4
 * Copyright 2015      INRIA Paris-Rocquencourt
5
 *
6
 * Use of this software is governed by the MIT license
7
 *
8
 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9
 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10
 * 91893 Orsay, France
11
 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
12
 * and INRIA Paris-Rocquencourt, Domaine de Voluceau, Rocquenqourt, B.P. 105,
13
 * 78153 Le Chesnay Cedex France
14
 */
15
16
#include <isl_hash_private.h>
17
#include <isl_union_macro.h>
18
19
/* A group of expressions defined over the same domain space "domain_space".
20
 * The entries of "part_table" are the individual expressions,
21
 * keyed on the entire space of the expression.
22
 *
23
 * Each UNION has its own groups, so there can only ever be a single
24
 * reference to each group.
25
 */
26
S(UNION,group) {
27
  isl_space *domain_space;
28
  struct isl_hash_table part_table;
29
};
30
31
/* A union of expressions defined over different disjoint domains.
32
 * "space" describes the parameters.
33
 * The entries of "table" are keyed on the domain space of the entry and
34
 * contain groups of expressions that are defined over the same domain space.
35
 */
36
struct UNION {
37
  int ref;
38
  isl_space *space;
39
40
  struct isl_hash_table table;
41
};
42
43
/* Internal data structure for isl_union_*_foreach_group.
44
 * "fn" is the function that needs to be called on each group.
45
 */
46
S(UNION,foreach_group_data)
47
{
48
  isl_stat (*fn)(__isl_keep S(UNION,group) *group, void *user);
49
  void *user;
50
};
51
52
/* Call data->fn on the group stored at *entry.
53
 */
54
static isl_stat FN(UNION,call_on_group)(void **entry, void *user)
55
19.4k
{
56
19.4k
  S(UNION,group) *group = *entry;
57
19.4k
  S(UNION,foreach_group_data) *data;
58
19.4k
59
19.4k
  data = (S(UNION,foreach_group_data) *) user;
60
19.4k
  return data->fn(group, data->user);
61
19.4k
}
62
63
/* Call "fn" on each group of expressions in "u".
64
 */
65
static isl_stat FN(UNION,foreach_group)(__isl_keep UNION *u,
66
  isl_stat (*fn)(__isl_keep S(UNION,group) *group, void *user),
67
  void *user)
68
14.2k
{
69
14.2k
  S(UNION,foreach_group_data) data = { fn, user };
70
14.2k
71
14.2k
  if (!u)
72
0
    return isl_stat_error;
73
14.2k
74
14.2k
  return isl_hash_table_foreach(u->space->ctx, &u->table,
75
14.2k
              &FN(UNION,call_on_group), &data);
76
14.2k
}
77
78
/* A isl_union_*_foreach_group callback for counting the total number
79
 * of expressions in a UNION.  Add the number of expressions in "group"
80
 * to *n.
81
 */
82
static isl_stat FN(UNION,count_part)(__isl_keep S(UNION,group) *group,
83
  void *user)
84
2.74k
{
85
2.74k
  int *n = user;
86
2.74k
87
2.74k
  if (!group)
88
0
    return isl_stat_error;
89
2.74k
90
2.74k
  *n += group->part_table.n;
91
2.74k
  return isl_stat_ok;
92
2.74k
}
93
94
/* Return the number of base expressions in "u".
95
 */
96
int FN(FN(UNION,n),PARTS)(__isl_keep UNION *u)
97
1.78k
{
98
1.78k
  int n;
99
1.78k
100
1.78k
  n = 0;
101
1.78k
  if (
FN1.78k
(UNION,foreach_group)(u, &1.78k
FN1.78k
(UNION,count_part), &n) < 0)
102
0
    n = -1;
103
1.78k
  return n;
104
1.78k
}
105
106
/* Free an entry in a group of expressions.
107
 * Each entry in such a group is a single expression.
108
 */
109
static isl_stat FN(UNION,free_group_entry)(void **entry, void *user)
110
10.2k
{
111
10.2k
  PART *part = *entry;
112
10.2k
113
10.2k
  FN(PART,free)(part);
114
10.2k
  return isl_stat_ok;
115
10.2k
}
116
117
/* Free all memory allocated for "group" and return NULL.
118
 */
119
static __isl_null S(UNION,group) *FN(UNION,group_free)(
120
  __isl_take S(UNION,group) *group)
121
10.2k
{
122
10.2k
  isl_ctx *ctx;
123
10.2k
124
10.2k
  if (!group)
125
0
    return NULL;
126
10.2k
127
10.2k
  ctx = isl_space_get_ctx(group->domain_space);
128
10.2k
  isl_hash_table_foreach(ctx, &group->part_table,
129
10.2k
        &FN(UNION,free_group_entry), NULL);
130
10.2k
  isl_hash_table_clear(&group->part_table);
131
10.2k
  isl_space_free(group->domain_space);
132
10.2k
  free(group);
133
10.2k
  return NULL;
134
10.2k
}
135
136
/* Allocate a group of expressions defined over the same domain space
137
 * with domain space "domain_space" and initial size "size".
138
 */
139
static __isl_give S(UNION,group) *FN(UNION,group_alloc)(
140
  __isl_take isl_space *domain_space, int size)
141
10.2k
{
142
10.2k
  isl_ctx *ctx;
143
10.2k
  S(UNION,group) *group;
144
10.2k
145
10.2k
  if (!domain_space)
146
0
    return NULL;
147
10.2k
  ctx = isl_space_get_ctx(domain_space);
148
10.2k
  group = isl_calloc_type(ctx, S(UNION,group));
149
10.2k
  if (!group)
150
0
    goto error;
151
10.2k
  group->domain_space = domain_space;
152
10.2k
  if (isl_hash_table_init(ctx, &group->part_table, size) < 0)
153
0
    
return 0
FN0
(UNION,group_free)(group);
154
10.2k
155
10.2k
  return group;
156
10.2k
error:
157
0
  isl_space_free(domain_space);
158
10.2k
  return NULL;
159
10.2k
}
160
161
/* Is the space of "entry" equal to "space"?
162
 */
163
static int FN(UNION,has_space)(const void *entry, const void *val)
164
15
{
165
15
  PART *part = (PART *) entry;
166
15
  isl_space *space = (isl_space *) val;
167
15
168
15
  return isl_space_is_equal(part->dim, space);
169
15
}
170
171
/* Return a group equal to "group", but with a single reference.
172
 * Since all groups have only a single reference, simply return "group".
173
 */
174
static __isl_give S(UNION,group) *FN(UNION,group_cow)(
175
  __isl_take S(UNION,group) *group)
176
6
{
177
6
  return group;
178
6
}
179
180
S(UNION,foreach_data)
181
{
182
  isl_stat (*fn)(__isl_take PART *part, void *user);
183
  void *user;
184
};
185
186
static isl_stat FN(UNION,call_on_copy)(void **entry, void *user)
187
16.7k
{
188
16.7k
  PART *part = *entry;
189
16.7k
  S(UNION,foreach_data) *data = (S(UNION,foreach_data) *) user;
190
16.7k
191
16.7k
  part = FN(PART,copy)(part);
192
16.7k
  if (!part)
193
0
    return isl_stat_error;
194
16.7k
  return data->fn(part, data->user);
195
16.7k
}
196
197
/* Call data->fn on a copy of each expression in "group".
198
 */
199
static isl_stat FN(UNION,group_call_on_copy)(__isl_keep S(UNION,group) *group,
200
  void *user)
201
16.7k
{
202
16.7k
  isl_ctx *ctx;
203
16.7k
204
16.7k
  if (!group)
205
0
    return isl_stat_error;
206
16.7k
207
16.7k
  ctx = isl_space_get_ctx(group->domain_space);
208
16.7k
  return isl_hash_table_foreach(ctx, &group->part_table,
209
16.7k
              &FN(UNION,call_on_copy), user);
210
16.7k
}
211
212
isl_stat FN(FN(UNION,foreach),PARTS)(__isl_keep UNION *u,
213
  isl_stat (*fn)(__isl_take PART *part, void *user), void *user)
214
12.5k
{
215
12.5k
  S(UNION,foreach_data) data = { fn, user };
216
12.5k
217
12.5k
  if (!u)
218
0
    return isl_stat_error;
219
12.5k
220
12.5k
  
return 12.5k
FN12.5k
(UNION,foreach_group)(u, &
FN12.5k
(UNION,group_call_on_copy), &data);
221
12.5k
}
222
223
/* Is the domain space of the group of expressions at "entry"
224
 * equal to "space"?
225
 */
226
static int FN(UNION,group_has_domain_space)(const void *entry, const void *val)
227
25
{
228
25
  S(UNION,group) *group = (S(UNION,group) *) entry;
229
25
  isl_space *space = (isl_space *) val;
230
25
231
25
  return isl_space_is_domain_internal(group->domain_space, space);
232
25
}
233
234
/* Return the entry, if any, in "u" that lives in "space".
235
 * If "reserve" is set, then an entry is created if it does not exist yet.
236
 * Return NULL on error and isl_hash_table_entry_none if no entry was found.
237
 * Note that when "reserve" is set, the function will never return
238
 * isl_hash_table_entry_none.
239
 *
240
 * First look for the group of expressions with the same domain space,
241
 * creating one if needed.
242
 * Then look for the expression living in the specified space in that group.
243
 */
244
static struct isl_hash_table_entry *FN(UNION,find_part_entry)(
245
  __isl_keep UNION *u, __isl_keep isl_space *space, int reserve)
246
10.3k
{
247
10.3k
  isl_ctx *ctx;
248
10.3k
  uint32_t hash;
249
10.3k
  struct isl_hash_table_entry *group_entry, *part_entry;
250
10.3k
  S(UNION,group) *group;
251
10.3k
252
10.3k
  if (
!u || 10.3k
!space10.3k
)
253
0
    return NULL;
254
10.3k
255
10.3k
  
ctx = 10.3k
FN10.3k
(UNION,get_ctx)(u);
256
10.3k
  hash = isl_space_get_domain_hash(space);
257
10.3k
  group_entry = isl_hash_table_find(ctx, &u->table, hash,
258
10.3k
          &FN(UNION,group_has_domain_space), space, reserve);
259
10.3k
  if (!group_entry)
260
1
    
return reserve ? NULL : 1
isl_hash_table_entry_none1
;
261
10.3k
  
if (10.3k
reserve && 10.3k
!group_entry->data10.3k
)
{10.2k
262
10.2k
    isl_space *domain = isl_space_domain(isl_space_copy(space));
263
10.2k
    group = FN(UNION,group_alloc)(domain, 1);
264
10.2k
    group_entry->data = group;
265
10.3k
  } else {
266
18
    group = group_entry->data;
267
18
    if (reserve)
268
6
      
group = 6
FN6
(UNION,group_cow)(group);
269
10.3k
  }
270
10.3k
  if (!group)
271
0
    return NULL;
272
10.3k
  hash = isl_space_get_hash(space);
273
10.3k
  part_entry = isl_hash_table_find(ctx, &group->part_table, hash,
274
10.3k
        &FN(UNION,has_space), space, reserve);
275
10.3k
  if (
!reserve && 10.3k
!part_entry12
)
276
0
    return isl_hash_table_entry_none;
277
10.3k
  return part_entry;
278
10.3k
}
279
280
/* Remove "part_entry" from the hash table of "u".
281
 *
282
 * First look the group_entry in "u" holding the group that
283
 * contains "part_entry".  Remove "part_entry" from that group.
284
 * If the group becomes empty, then also remove the group_entry from "u".
285
 */
286
static __isl_give UNION *FN(UNION,remove_part_entry)(__isl_take UNION *u,
287
  struct isl_hash_table_entry *part_entry)
288
0
{
289
0
  isl_ctx *ctx;
290
0
  uint32_t hash;
291
0
  PART *part;
292
0
  struct isl_hash_table_entry *group_entry;
293
0
  S(UNION,group) *group;
294
0
295
0
  if (
!u || 0
!part_entry0
)
296
0
    
return 0
FN0
(UNION,free)(u);
297
0
298
0
  part = part_entry->data;
299
0
  ctx = FN(UNION,get_ctx)(u);
300
0
  hash = isl_space_get_domain_hash(part->dim);
301
0
  group_entry = isl_hash_table_find(ctx, &u->table, hash,
302
0
          &FN(UNION,group_has_domain_space), part->dim, 0);
303
0
  if (!group_entry)
304
0
    isl_die(ctx, isl_error_internal, "missing group",
305
0
      return FN(UNION,free)(u));
306
0
  group = group_entry->data;
307
0
  isl_hash_table_remove(ctx, &group->part_table, part_entry);
308
0
  FN(PART,free)(part);
309
0
310
0
  if (group->part_table.n != 0)
311
0
    return u;
312
0
313
0
  isl_hash_table_remove(ctx, &u->table, group_entry);
314
0
  FN(UNION,group_free)(group);
315
0
316
0
  return u;
317
0
}
318
319
/* Are the domains of "part1" and "part2" disjoint?
320
 */
321
static isl_bool FN(UNION,disjoint_domain)(__isl_keep PART *part1,
322
  __isl_keep PART *part2)
323
5
{
324
5
  isl_set *dom1, *dom2;
325
5
  isl_bool disjoint;
326
5
327
5
  if (
!part1 || 5
!part25
)
328
0
    return isl_bool_error;
329
5
  
dom1 = 5
FN5
(PART,domain)(
FN5
(PART,copy)(part1));
330
5
  dom2 = 
FN5
(PART,domain)(
FN5
(PART,copy)(part2));
331
5
  disjoint = isl_set_is_disjoint(dom1, dom2);
332
5
  isl_set_free(dom1);
333
5
  isl_set_free(dom2);
334
5
335
5
  return disjoint;
336
5
}
337
338
/* Check that the expression at *entry has a domain that is disjoint
339
 * from that of "part", unless they also have the same target space.
340
 */
341
static isl_stat FN(UNION,check_disjoint_domain_entry)(void **entry, void *user)
342
7
{
343
7
  PART *part = user;
344
7
  PART *other = *entry;
345
7
  isl_bool equal;
346
7
  isl_bool disjoint;
347
7
348
7
  equal = isl_space_is_equal(part->dim, other->dim);
349
7
  if (equal < 0)
350
0
    return isl_stat_error;
351
7
  
if (7
equal7
)
352
3
    return isl_stat_ok;
353
7
354
4
  
disjoint = 4
FN4
(UNION,disjoint_domain)(part, other);
355
4
  if (disjoint < 0)
356
0
    return isl_stat_error;
357
4
  
if (4
!disjoint4
)
358
1
    isl_die(FN(PART,get_ctx)(part), isl_error_invalid,
359
4
      "overlapping domain with other part",
360
4
      return isl_stat_error);
361
3
  return isl_stat_ok;
362
7
}
363
364
/* Check that the domain of "part" is disjoint from the domain of the entries
365
 * in "u" that are defined on the same domain space, but have a different
366
 * target space.
367
 * If there is no group of expressions in "u" with the same domain space,
368
 * then everything is fine.  Otherwise, check the individual expressions
369
 * in that group.
370
 */
371
static isl_stat FN(UNION,check_disjoint_domain_other)(__isl_keep UNION *u,
372
  __isl_keep PART *part)
373
10.3k
{
374
10.3k
  isl_ctx *ctx;
375
10.3k
  uint32_t hash;
376
10.3k
  struct isl_hash_table_entry *group_entry;
377
10.3k
  S(UNION,group) *group;
378
10.3k
379
10.3k
  if (
!u || 10.3k
!part10.3k
)
380
0
    return isl_stat_error;
381
10.3k
  
ctx = 10.3k
FN10.3k
(UNION,get_ctx)(u);
382
10.3k
  hash = isl_space_get_domain_hash(part->dim);
383
10.3k
  group_entry = isl_hash_table_find(ctx, &u->table, hash,
384
10.3k
          &FN(UNION,group_has_domain_space), part->dim, 0);
385
10.3k
  if (!group_entry)
386
10.2k
    return isl_stat_ok;
387
10.3k
  group = group_entry->data;
388
7
  return isl_hash_table_foreach(ctx, &group->part_table,
389
7
            &FN(UNION,check_disjoint_domain_entry), part);
390
10.3k
}
391
392
/* Check that the domain of "part1" is disjoint from the domain of "part2".
393
 * This check is performed before "part2" is added to a UNION to ensure
394
 * that the UNION expression remains a function.
395
 */
396
static isl_stat FN(UNION,check_disjoint_domain)(__isl_keep PART *part1,
397
  __isl_keep PART *part2)
398
1
{
399
1
  isl_bool disjoint;
400
1
401
1
  disjoint = FN(UNION,disjoint_domain)(part1, part2);
402
1
  if (disjoint < 0)
403
0
    return isl_stat_error;
404
1
  
if (1
!disjoint1
)
405
0
    isl_die(FN(PART,get_ctx)(part1), isl_error_invalid,
406
1
      "domain of additional part should be disjoint",
407
1
      return isl_stat_error);
408
1
  return isl_stat_ok;
409
1
}
410
411
/* Internal data structure for isl_union_*_foreach_inplace.
412
 * "fn" is the function that needs to be called on each entry.
413
 */
414
S(UNION,foreach_inplace_data)
415
{
416
  isl_stat (*fn)(void **entry, void *user);
417
  void *user;
418
};
419
420
/* isl_union_*_foreach_group callback for calling data->fn on
421
 * each part entry in the group.
422
 */
423
static isl_stat FN(UNION,group_call_inplace)(__isl_keep S(UNION,group) *group,
424
  void *user)
425
10
{
426
10
  isl_ctx *ctx;
427
10
  S(UNION,foreach_inplace_data) *data;
428
10
429
10
  if (!group)
430
0
    return isl_stat_error;
431
10
432
10
  data = (S(UNION,foreach_inplace_data) *) user;
433
10
  ctx = isl_space_get_ctx(group->domain_space);
434
10
  return isl_hash_table_foreach(ctx, &group->part_table,
435
10
              data->fn, data->user);
436
10
}
437
438
/* Call "fn" on each part entry of "u".
439
 */
440
static isl_stat FN(UNION,foreach_inplace)(__isl_keep UNION *u,
441
  isl_stat (*fn)(void **part, void *user), void *user)
442
9
{
443
9
  S(UNION,foreach_inplace_data) data = { fn, user };
444
9
445
9
  return 
FN9
(UNION,foreach_group)(u, &
FN9
(UNION,group_call_inplace), &data);
446
9
}
447
448
/* Does "u" have a single reference?
449
 * That is, can we change "u" inplace?
450
 */
451
static isl_bool FN(UNION,has_single_reference)(__isl_keep UNION *u)
452
0
{
453
0
  if (!u)
454
0
    return isl_bool_error;
455
0
  return u->ref == 1;
456
0
}
457
458
static isl_stat FN(UNION,free_u_entry)(void **entry, void *user)
459
10.2k
{
460
10.2k
  S(UNION,group) *group = *entry;
461
10.2k
  FN(UNION,group_free)(group);
462
10.2k
  return isl_stat_ok;
463
10.2k
}
464
465
#include <isl_union_templ.c>