Coverage Report

Created: 2018-02-20 12:54

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_point.c
Line
Count
Source (jump to first uncovered line)
1
#include <isl_map_private.h>
2
#include <isl_point_private.h>
3
#include <isl/set.h>
4
#include <isl/union_set.h>
5
#include <isl_sample.h>
6
#include <isl_scan.h>
7
#include <isl_seq.h>
8
#include <isl_space_private.h>
9
#include <isl_val_private.h>
10
#include <isl_vec_private.h>
11
#include <isl_output_private.h>
12
13
#include <set_to_map.c>
14
15
isl_ctx *isl_point_get_ctx(__isl_keep isl_point *pnt)
16
2
{
17
2
  return pnt ? isl_space_get_ctx(pnt->dim) : NULL;
18
2
}
19
20
__isl_give isl_space *isl_point_get_space(__isl_keep isl_point *pnt)
21
1
{
22
1
  return pnt ? isl_space_copy(pnt->dim) : NULL;
23
1
}
24
25
__isl_give isl_point *isl_point_alloc(__isl_take isl_space *dim,
26
  __isl_take isl_vec *vec)
27
405
{
28
405
  struct isl_point *pnt;
29
405
30
405
  if (!dim || !vec)
31
0
    goto error;
32
405
33
405
  if (vec->size > 1 + isl_space_dim(dim, isl_dim_all)) {
34
0
    vec = isl_vec_cow(vec);
35
0
    if (!vec)
36
0
      goto error;
37
0
    vec->size = 1 + isl_space_dim(dim, isl_dim_all);
38
0
  }
39
405
40
405
  pnt = isl_alloc_type(dim->ctx, struct isl_point);
41
405
  if (!pnt)
42
0
    goto error;
43
405
44
405
  pnt->ref = 1;
45
405
  pnt->dim = dim;
46
405
  pnt->vec = vec;
47
405
48
405
  return pnt;
49
0
error:
50
0
  isl_space_free(dim);
51
0
  isl_vec_free(vec);
52
0
  return NULL;
53
405
}
54
55
__isl_give isl_point *isl_point_zero(__isl_take isl_space *dim)
56
1
{
57
1
  isl_vec *vec;
58
1
59
1
  if (!dim)
60
0
    return NULL;
61
1
  vec = isl_vec_alloc(dim->ctx, 1 + isl_space_dim(dim, isl_dim_all));
62
1
  if (!vec)
63
0
    goto error;
64
1
  isl_int_set_si(vec->el[0], 1);
65
1
  isl_seq_clr(vec->el + 1, vec->size - 1);
66
1
  return isl_point_alloc(dim, vec);
67
0
error:
68
0
  isl_space_free(dim);
69
0
  return NULL;
70
1
}
71
72
__isl_give isl_point *isl_point_dup(__isl_keep isl_point *pnt)
73
0
{
74
0
  struct isl_point *pnt2;
75
0
76
0
  if (!pnt)
77
0
    return NULL;
78
0
  pnt2 = isl_point_alloc(isl_space_copy(pnt->dim), isl_vec_copy(pnt->vec));
79
0
  return pnt2;
80
0
}
81
82
__isl_give isl_point *isl_point_cow(__isl_take isl_point *pnt)
83
0
{
84
0
  struct isl_point *pnt2;
85
0
  if (!pnt)
86
0
    return NULL;
87
0
88
0
  if (pnt->ref == 1)
89
0
    return pnt;
90
0
91
0
  pnt2 = isl_point_dup(pnt);
92
0
  isl_point_free(pnt);
93
0
  return pnt2;
94
0
}
95
96
__isl_give isl_point *isl_point_copy(__isl_keep isl_point *pnt)
97
1
{
98
1
  if (!pnt)
99
0
    return NULL;
100
1
101
1
  pnt->ref++;
102
1
  return pnt;
103
1
}
104
105
__isl_null isl_point *isl_point_free(__isl_take isl_point *pnt)
106
406
{
107
406
  if (!pnt)
108
0
    return NULL;
109
406
110
406
  if (--pnt->ref > 0)
111
1
    return NULL;
112
405
113
405
  isl_space_free(pnt->dim);
114
405
  isl_vec_free(pnt->vec);
115
405
  free(pnt);
116
405
  return NULL;
117
405
}
118
119
__isl_give isl_point *isl_point_void(__isl_take isl_space *dim)
120
1
{
121
1
  if (!dim)
122
0
    return NULL;
123
1
124
1
  return isl_point_alloc(dim, isl_vec_alloc(dim->ctx, 0));
125
1
}
126
127
isl_bool isl_point_is_void(__isl_keep isl_point *pnt)
128
3
{
129
3
  if (!pnt)
130
0
    return isl_bool_error;
131
3
132
3
  return pnt->vec->size == 0;
133
3
}
134
135
/* Return the value of coordinate "pos" of type "type" of "pnt".
136
 */
137
__isl_give isl_val *isl_point_get_coordinate_val(__isl_keep isl_point *pnt,
138
  enum isl_dim_type type, int pos)
139
0
{
140
0
  isl_ctx *ctx;
141
0
  isl_val *v;
142
0
143
0
  if (!pnt)
144
0
    return NULL;
145
0
146
0
  ctx = isl_point_get_ctx(pnt);
147
0
  if (isl_point_is_void(pnt))
148
0
    isl_die(ctx, isl_error_invalid,
149
0
      "void point does not have coordinates", return NULL);
150
0
  if (pos < 0 || pos >= isl_space_dim(pnt->dim, type))
151
0
    isl_die(ctx, isl_error_invalid,
152
0
      "position out of bounds", return NULL);
153
0
154
0
  if (type == isl_dim_set)
155
0
    pos += isl_space_dim(pnt->dim, isl_dim_param);
156
0
157
0
  v = isl_val_rat_from_isl_int(ctx, pnt->vec->el[1 + pos],
158
0
            pnt->vec->el[0]);
159
0
  return isl_val_normalize(v);
160
0
}
161
162
/* Replace coordinate "pos" of type "type" of "pnt" by "v".
163
 */
164
__isl_give isl_point *isl_point_set_coordinate_val(__isl_take isl_point *pnt,
165
  enum isl_dim_type type, int pos, __isl_take isl_val *v)
166
0
{
167
0
  if (!pnt || !v)
168
0
    goto error;
169
0
  if (isl_point_is_void(pnt))
170
0
    isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
171
0
      "void point does not have coordinates", goto error);
172
0
  if (pos < 0 || pos >= isl_space_dim(pnt->dim, type))
173
0
    isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
174
0
      "position out of bounds", goto error);
175
0
  if (!isl_val_is_rat(v))
176
0
    isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
177
0
      "expecting rational value", goto error);
178
0
179
0
  if (isl_int_eq(pnt->vec->el[1 + pos], v->n) &&
180
0
      isl_int_eq(pnt->vec->el[0], v->d)) {
181
0
    isl_val_free(v);
182
0
    return pnt;
183
0
  }
184
0
185
0
  pnt = isl_point_cow(pnt);
186
0
  if (!pnt)
187
0
    goto error;
188
0
  pnt->vec = isl_vec_cow(pnt->vec);
189
0
  if (!pnt->vec)
190
0
    goto error;
191
0
192
0
  if (isl_int_eq(pnt->vec->el[0], v->d)) {
193
0
    isl_int_set(pnt->vec->el[1 + pos], v->n);
194
0
  } else if (isl_int_is_one(v->d)) {
195
0
    isl_int_mul(pnt->vec->el[1 + pos], pnt->vec->el[0], v->n);
196
0
  } else {
197
0
    isl_seq_scale(pnt->vec->el + 1,
198
0
        pnt->vec->el + 1, v->d, pnt->vec->size - 1);
199
0
    isl_int_mul(pnt->vec->el[1 + pos], pnt->vec->el[0], v->n);
200
0
    isl_int_mul(pnt->vec->el[0], pnt->vec->el[0], v->d);
201
0
    pnt->vec = isl_vec_normalize(pnt->vec);
202
0
    if (!pnt->vec)
203
0
      goto error;
204
0
  }
205
0
206
0
  isl_val_free(v);
207
0
  return pnt;
208
0
error:
209
0
  isl_val_free(v);
210
0
  isl_point_free(pnt);
211
0
  return NULL;
212
0
}
213
214
__isl_give isl_point *isl_point_add_ui(__isl_take isl_point *pnt,
215
  enum isl_dim_type type, int pos, unsigned val)
216
0
{
217
0
  if (!pnt || isl_point_is_void(pnt))
218
0
    return pnt;
219
0
220
0
  pnt = isl_point_cow(pnt);
221
0
  if (!pnt)
222
0
    return NULL;
223
0
  pnt->vec = isl_vec_cow(pnt->vec);
224
0
  if (!pnt->vec)
225
0
    goto error;
226
0
227
0
  if (type == isl_dim_set)
228
0
    pos += isl_space_dim(pnt->dim, isl_dim_param);
229
0
230
0
  isl_int_add_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
231
0
232
0
  return pnt;
233
0
error:
234
0
  isl_point_free(pnt);
235
0
  return NULL;
236
0
}
237
238
__isl_give isl_point *isl_point_sub_ui(__isl_take isl_point *pnt,
239
  enum isl_dim_type type, int pos, unsigned val)
240
0
{
241
0
  if (!pnt || isl_point_is_void(pnt))
242
0
    return pnt;
243
0
244
0
  pnt = isl_point_cow(pnt);
245
0
  if (!pnt)
246
0
    return NULL;
247
0
  pnt->vec = isl_vec_cow(pnt->vec);
248
0
  if (!pnt->vec)
249
0
    goto error;
250
0
251
0
  if (type == isl_dim_set)
252
0
    pos += isl_space_dim(pnt->dim, isl_dim_param);
253
0
254
0
  isl_int_sub_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
255
0
256
0
  return pnt;
257
0
error:
258
0
  isl_point_free(pnt);
259
0
  return NULL;
260
0
}
261
262
struct isl_foreach_point {
263
  struct isl_scan_callback callback;
264
  isl_stat (*fn)(__isl_take isl_point *pnt, void *user);
265
  void *user;
266
  isl_space *dim;
267
};
268
269
static isl_stat foreach_point(struct isl_scan_callback *cb,
270
  __isl_take isl_vec *sample)
271
0
{
272
0
  struct isl_foreach_point *fp = (struct isl_foreach_point *)cb;
273
0
  isl_point *pnt;
274
0
275
0
  pnt = isl_point_alloc(isl_space_copy(fp->dim), sample);
276
0
277
0
  return fp->fn(pnt, fp->user);
278
0
}
279
280
isl_stat isl_set_foreach_point(__isl_keep isl_set *set,
281
  isl_stat (*fn)(__isl_take isl_point *pnt, void *user), void *user)
282
84
{
283
84
  struct isl_foreach_point fp = { { &foreach_point }, fn, user };
284
84
  int i;
285
84
286
84
  if (!set)
287
0
    return isl_stat_error;
288
84
289
84
  fp.dim = isl_set_get_space(set);
290
84
  if (!fp.dim)
291
0
    return isl_stat_error;
292
84
293
84
  set = isl_set_copy(set);
294
84
  set = isl_set_cow(set);
295
84
  set = isl_set_make_disjoint(set);
296
84
  set = isl_set_compute_divs(set);
297
84
  if (!set)
298
0
    goto error;
299
84
300
84
  for (i = 0; i < set->n; 
++i0
)
301
0
    if (isl_basic_set_scan(isl_basic_set_copy(set->p[i]),
302
0
          &fp.callback) < 0)
303
0
      goto error;
304
84
305
84
  isl_set_free(set);
306
84
  isl_space_free(fp.dim);
307
84
308
84
  return isl_stat_ok;
309
0
error:
310
0
  isl_set_free(set);
311
0
  isl_space_free(fp.dim);
312
0
  return isl_stat_error;
313
84
}
314
315
/* Return 1 if "bmap" contains the point "point".
316
 * "bmap" is assumed to have known divs.
317
 * The point is first extended with the divs and then passed
318
 * to basic_map_contains.
319
 */
320
isl_bool isl_basic_map_contains_point(__isl_keep isl_basic_map *bmap,
321
  __isl_keep isl_point *point)
322
425
{
323
425
  int i;
324
425
  struct isl_vec *vec;
325
425
  unsigned dim;
326
425
  isl_bool contains;
327
425
328
425
  if (!bmap || !point)
329
0
    return isl_bool_error;
330
425
  isl_assert(bmap->ctx, isl_space_is_equal(bmap->dim, point->dim),
331
425
    return isl_bool_error);
332
425
  if (bmap->n_div == 0)
333
421
    return isl_basic_map_contains(bmap, point->vec);
334
4
335
4
  dim = isl_basic_map_total_dim(bmap) - bmap->n_div;
336
4
  vec = isl_vec_alloc(bmap->ctx, 1 + dim + bmap->n_div);
337
4
  if (!vec)
338
0
    return isl_bool_error;
339
4
340
4
  isl_seq_cpy(vec->el, point->vec->el, point->vec->size);
341
11
  for (i = 0; i < bmap->n_div; 
++i7
) {
342
7
    isl_seq_inner_product(bmap->div[i] + 1, vec->el,
343
7
          1 + dim + i, &vec->el[1+dim+i]);
344
7
    isl_int_fdiv_q(vec->el[1+dim+i], vec->el[1+dim+i],
345
7
        bmap->div[i][0]);
346
7
  }
347
4
348
4
  contains = isl_basic_map_contains(bmap, vec);
349
4
350
4
  isl_vec_free(vec);
351
4
  return contains;
352
4
}
353
354
isl_bool isl_map_contains_point(__isl_keep isl_map *map,
355
  __isl_keep isl_point *point)
356
1
{
357
1
  int i;
358
1
  isl_bool found = isl_bool_false;
359
1
360
1
  if (!map || !point)
361
0
    return isl_bool_error;
362
1
363
1
  map = isl_map_copy(map);
364
1
  map = isl_map_compute_divs(map);
365
1
  if (!map)
366
0
    return isl_bool_error;
367
1
368
1
  for (i = 0; i < map->n; 
++i0
) {
369
1
    found = isl_basic_map_contains_point(map->p[i], point);
370
1
    if (found < 0)
371
0
      goto error;
372
1
    if (found)
373
1
      break;
374
1
  }
375
1
  isl_map_free(map);
376
1
377
1
  return found;
378
0
error:
379
0
  isl_map_free(map);
380
0
  return isl_bool_error;
381
1
}
382
383
isl_bool isl_set_contains_point(__isl_keep isl_set *set,
384
  __isl_keep isl_point *point)
385
1
{
386
1
  return isl_map_contains_point(set_to_map(set), point);
387
1
}
388
389
__isl_give isl_basic_set *isl_basic_set_from_point(__isl_take isl_point *pnt)
390
1
{
391
1
  isl_basic_set *bset;
392
1
  isl_basic_set *model;
393
1
394
1
  if (!pnt)
395
0
    return NULL;
396
1
397
1
  model = isl_basic_set_empty(isl_space_copy(pnt->dim));
398
1
  bset = isl_basic_set_from_vec(isl_vec_copy(pnt->vec));
399
1
  bset = isl_basic_set_from_underlying_set(bset, model);
400
1
  isl_point_free(pnt);
401
1
402
1
  return bset;
403
1
}
404
405
__isl_give isl_set *isl_set_from_point(__isl_take isl_point *pnt)
406
0
{
407
0
  isl_basic_set *bset;
408
0
  bset = isl_basic_set_from_point(pnt);
409
0
  return isl_set_from_basic_set(bset);
410
0
}
411
412
/* Construct a union set, containing the single element "pnt".
413
 * If "pnt" is void, then return an empty union set.
414
 */
415
__isl_give isl_union_set *isl_union_set_from_point(__isl_take isl_point *pnt)
416
0
{
417
0
  if (!pnt)
418
0
    return NULL;
419
0
  if (isl_point_is_void(pnt)) {
420
0
    isl_space *space;
421
0
422
0
    space = isl_point_get_space(pnt);
423
0
    isl_point_free(pnt);
424
0
    return isl_union_set_empty(space);
425
0
  }
426
0
427
0
  return isl_union_set_from_set(isl_set_from_point(pnt));
428
0
}
429
430
__isl_give isl_basic_set *isl_basic_set_box_from_points(
431
  __isl_take isl_point *pnt1, __isl_take isl_point *pnt2)
432
0
{
433
0
  isl_basic_set *bset = NULL;
434
0
  unsigned total;
435
0
  int i;
436
0
  int k;
437
0
  isl_int t;
438
0
439
0
  isl_int_init(t);
440
0
441
0
  if (!pnt1 || !pnt2)
442
0
    goto error;
443
0
444
0
  isl_assert(pnt1->dim->ctx,
445
0
      isl_space_is_equal(pnt1->dim, pnt2->dim), goto error);
446
0
447
0
  if (isl_point_is_void(pnt1) && isl_point_is_void(pnt2)) {
448
0
    isl_space *dim = isl_space_copy(pnt1->dim);
449
0
    isl_point_free(pnt1);
450
0
    isl_point_free(pnt2);
451
0
    isl_int_clear(t);
452
0
    return isl_basic_set_empty(dim);
453
0
  }
454
0
  if (isl_point_is_void(pnt1)) {
455
0
    isl_point_free(pnt1);
456
0
    isl_int_clear(t);
457
0
    return isl_basic_set_from_point(pnt2);
458
0
  }
459
0
  if (isl_point_is_void(pnt2)) {
460
0
    isl_point_free(pnt2);
461
0
    isl_int_clear(t);
462
0
    return isl_basic_set_from_point(pnt1);
463
0
  }
464
0
465
0
  total = isl_space_dim(pnt1->dim, isl_dim_all);
466
0
  bset = isl_basic_set_alloc_space(isl_space_copy(pnt1->dim), 0, 0, 2 * total);
467
0
468
0
  for (i = 0; i < total; ++i) {
469
0
    isl_int_mul(t, pnt1->vec->el[1 + i], pnt2->vec->el[0]);
470
0
    isl_int_submul(t, pnt2->vec->el[1 + i], pnt1->vec->el[0]);
471
0
472
0
    k = isl_basic_set_alloc_inequality(bset);
473
0
    if (k < 0)
474
0
      goto error;
475
0
    isl_seq_clr(bset->ineq[k] + 1, total);
476
0
    if (isl_int_is_pos(t)) {
477
0
      isl_int_set_si(bset->ineq[k][1 + i], -1);
478
0
      isl_int_set(bset->ineq[k][0], pnt1->vec->el[1 + i]);
479
0
    } else {
480
0
      isl_int_set_si(bset->ineq[k][1 + i], 1);
481
0
      isl_int_neg(bset->ineq[k][0], pnt1->vec->el[1 + i]);
482
0
    }
483
0
    isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt1->vec->el[0]);
484
0
485
0
    k = isl_basic_set_alloc_inequality(bset);
486
0
    if (k < 0)
487
0
      goto error;
488
0
    isl_seq_clr(bset->ineq[k] + 1, total);
489
0
    if (isl_int_is_pos(t)) {
490
0
      isl_int_set_si(bset->ineq[k][1 + i], 1);
491
0
      isl_int_neg(bset->ineq[k][0], pnt2->vec->el[1 + i]);
492
0
    } else {
493
0
      isl_int_set_si(bset->ineq[k][1 + i], -1);
494
0
      isl_int_set(bset->ineq[k][0], pnt2->vec->el[1 + i]);
495
0
    }
496
0
    isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt2->vec->el[0]);
497
0
  }
498
0
499
0
  bset = isl_basic_set_finalize(bset);
500
0
501
0
  isl_point_free(pnt1);
502
0
  isl_point_free(pnt2);
503
0
504
0
  isl_int_clear(t);
505
0
506
0
  return bset;
507
0
error:
508
0
  isl_point_free(pnt1);
509
0
  isl_point_free(pnt2);
510
0
  isl_int_clear(t);
511
0
  isl_basic_set_free(bset);
512
0
  return NULL;
513
0
}
514
515
__isl_give isl_set *isl_set_box_from_points(__isl_take isl_point *pnt1,
516
  __isl_take isl_point *pnt2)
517
0
{
518
0
  isl_basic_set *bset;
519
0
  bset = isl_basic_set_box_from_points(pnt1, pnt2);
520
0
  return isl_set_from_basic_set(bset);
521
0
}
522
523
/* Print the coordinate at position "pos" of the point "pnt".
524
 */
525
static __isl_give isl_printer *print_coordinate(__isl_take isl_printer *p,
526
  struct isl_print_space_data *data, unsigned pos)
527
0
{
528
0
  isl_point *pnt = data->user;
529
0
530
0
  p = isl_printer_print_isl_int(p, pnt->vec->el[1 + pos]);
531
0
  if (!isl_int_is_one(pnt->vec->el[0])) {
532
0
    p = isl_printer_print_str(p, "/");
533
0
    p = isl_printer_print_isl_int(p, pnt->vec->el[0]);
534
0
  }
535
0
536
0
  return p;
537
0
}
538
539
__isl_give isl_printer *isl_printer_print_point(
540
  __isl_take isl_printer *p, __isl_keep isl_point *pnt)
541
0
{
542
0
  struct isl_print_space_data data = { 0 };
543
0
  int i;
544
0
  unsigned nparam;
545
0
546
0
  if (!pnt)
547
0
    return p;
548
0
  if (isl_point_is_void(pnt)) {
549
0
    p = isl_printer_print_str(p, "void");
550
0
    return p;
551
0
  }
552
0
553
0
  nparam = isl_space_dim(pnt->dim, isl_dim_param);
554
0
  if (nparam > 0) {
555
0
    p = isl_printer_print_str(p, "[");
556
0
    for (i = 0; i < nparam; ++i) {
557
0
      const char *name;
558
0
      if (i)
559
0
        p = isl_printer_print_str(p, ", ");
560
0
      name = isl_space_get_dim_name(pnt->dim, isl_dim_param, i);
561
0
      if (name) {
562
0
        p = isl_printer_print_str(p, name);
563
0
        p = isl_printer_print_str(p, " = ");
564
0
      }
565
0
      p = isl_printer_print_isl_int(p, pnt->vec->el[1 + i]);
566
0
      if (!isl_int_is_one(pnt->vec->el[0])) {
567
0
        p = isl_printer_print_str(p, "/");
568
0
        p = isl_printer_print_isl_int(p, pnt->vec->el[0]);
569
0
      }
570
0
    }
571
0
    p = isl_printer_print_str(p, "]");
572
0
    p = isl_printer_print_str(p, " -> ");
573
0
  }
574
0
  data.print_dim = &print_coordinate;
575
0
  data.user = pnt;
576
0
  p = isl_printer_print_str(p, "{ ");
577
0
  p = isl_print_space(pnt->dim, p, 0, &data);
578
0
  p = isl_printer_print_str(p, " }");
579
0
  return p;
580
0
}