Coverage Report

Created: 2018-02-20 23:11

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_vertices.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2010      INRIA Saclay
3
 *
4
 * Use of this software is governed by the MIT license
5
 *
6
 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7
 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
8
 * 91893 Orsay, France 
9
 */
10
11
#include <isl_map_private.h>
12
#include <isl_aff_private.h>
13
#include <isl/set.h>
14
#include <isl_seq.h>
15
#include <isl_tab.h>
16
#include <isl_space_private.h>
17
#include <isl_morph.h>
18
#include <isl_vertices_private.h>
19
#include <isl_mat_private.h>
20
#include <isl_vec_private.h>
21
22
222
#define SELECTED  1
23
270
#define DESELECTED  -1
24
39
#define UNSELECTED  0
25
26
static __isl_give isl_vertices *compute_chambers(__isl_take isl_basic_set *bset,
27
  __isl_take isl_vertices *vertices);
28
29
__isl_give isl_vertices *isl_vertices_copy(__isl_keep isl_vertices *vertices)
30
16
{
31
16
  if (!vertices)
32
0
    return NULL;
33
16
34
16
  vertices->ref++;
35
16
  return vertices;
36
16
}
37
38
__isl_null isl_vertices *isl_vertices_free(__isl_take isl_vertices *vertices)
39
20
{
40
20
  int i;
41
20
42
20
  if (!vertices)
43
0
    return NULL;
44
20
45
20
  if (--vertices->ref > 0)
46
16
    return NULL;
47
4
48
29
  
for (i = 0; 4
i < vertices->n_vertices;
++i25
) {
49
25
    isl_basic_set_free(vertices->v[i].vertex);
50
25
    isl_basic_set_free(vertices->v[i].dom);
51
25
  }
52
4
  free(vertices->v);
53
4
54
14
  for (i = 0; i < vertices->n_chambers; 
++i10
) {
55
10
    free(vertices->c[i].vertices);
56
10
    isl_basic_set_free(vertices->c[i].dom);
57
10
  }
58
4
  free(vertices->c);
59
4
60
4
  isl_basic_set_free(vertices->bset);
61
4
  free(vertices);
62
4
63
4
  return NULL;
64
4
}
65
66
struct isl_vertex_list {
67
  struct isl_vertex v;
68
  struct isl_vertex_list *next;
69
};
70
71
static struct isl_vertex_list *free_vertex_list(struct isl_vertex_list *list)
72
1
{
73
1
  struct isl_vertex_list *next;
74
1
75
2
  for (; list; 
list = next1
) {
76
1
    next = list->next;
77
1
    isl_basic_set_free(list->v.vertex);
78
1
    isl_basic_set_free(list->v.dom);
79
1
    free(list);
80
1
  }
81
1
82
1
  return NULL;
83
1
}
84
85
static __isl_give isl_vertices *vertices_from_list(__isl_keep isl_basic_set *bset,
86
  int n_vertices, struct isl_vertex_list *list)
87
3
{
88
3
  int i;
89
3
  struct isl_vertex_list *next;
90
3
  isl_vertices *vertices;
91
3
92
3
  vertices = isl_calloc_type(bset->ctx, isl_vertices);
93
3
  if (!vertices)
94
0
    goto error;
95
3
  vertices->ref = 1;
96
3
  vertices->bset = isl_basic_set_copy(bset);
97
3
  vertices->v = isl_alloc_array(bset->ctx, struct isl_vertex, n_vertices);
98
3
  if (n_vertices && !vertices->v)
99
0
    goto error;
100
3
  vertices->n_vertices = n_vertices;
101
3
102
27
  for (i = 0; list; 
list = next, i++24
) {
103
24
    next = list->next;
104
24
    vertices->v[i] = list->v;
105
24
    free(list);
106
24
  }
107
3
108
3
  return vertices;
109
0
error:
110
0
  isl_vertices_free(vertices);
111
0
  free_vertex_list(list);
112
0
  return NULL;
113
3
}
114
115
/* Prepend a vertex to the linked list "list" based on the equalities in "tab".
116
 * Return isl_bool_true if the vertex was actually added and
117
 * isl_bool_false otherwise.
118
 * In particular, vertices with a lower-dimensional activity domain are
119
 * not added to the list because they would not be included in any chamber.
120
 * Return isl_bool_error on error.
121
 */
122
static isl_bool add_vertex(struct isl_vertex_list **list,
123
  __isl_keep isl_basic_set *bset, struct isl_tab *tab)
124
25
{
125
25
  unsigned nvar;
126
25
  struct isl_vertex_list *v = NULL;
127
25
128
25
  if (isl_tab_detect_implicit_equalities(tab) < 0)
129
0
    return isl_bool_error;
130
25
131
25
  nvar = isl_basic_set_dim(bset, isl_dim_set);
132
25
133
25
  v = isl_calloc_type(tab->mat->ctx, struct isl_vertex_list);
134
25
  if (!v)
135
0
    goto error;
136
25
137
25
  v->v.vertex = isl_basic_set_copy(bset);
138
25
  v->v.vertex = isl_basic_set_cow(v->v.vertex);
139
25
  v->v.vertex = isl_basic_set_update_from_tab(v->v.vertex, tab);
140
25
  v->v.vertex = isl_basic_set_simplify(v->v.vertex);
141
25
  v->v.vertex = isl_basic_set_finalize(v->v.vertex);
142
25
  if (!v->v.vertex)
143
0
    goto error;
144
25
  isl_assert(bset->ctx, v->v.vertex->n_eq >= nvar, goto error);
145
25
  v->v.dom = isl_basic_set_copy(v->v.vertex);
146
25
  v->v.dom = isl_basic_set_params(v->v.dom);
147
25
  if (!v->v.dom)
148
0
    goto error;
149
25
150
25
  if (v->v.dom->n_eq > 0) {
151
1
    free_vertex_list(v);
152
1
    return isl_bool_false;
153
1
  }
154
24
155
24
  v->next = *list;
156
24
  *list = v;
157
24
158
24
  return isl_bool_true;
159
0
error:
160
0
  free_vertex_list(v);
161
0
  return isl_bool_error;
162
24
}
163
164
/* Compute the parametric vertices and the chamber decomposition
165
 * of an empty parametric polytope.
166
 */
167
static __isl_give isl_vertices *vertices_empty(__isl_keep isl_basic_set *bset)
168
0
{
169
0
  isl_vertices *vertices;
170
0
171
0
  if (!bset)
172
0
    return NULL;
173
0
174
0
  vertices = isl_calloc_type(bset->ctx, isl_vertices);
175
0
  if (!vertices)
176
0
    return NULL;
177
0
  vertices->bset = isl_basic_set_copy(bset);
178
0
  vertices->ref = 1;
179
0
180
0
  vertices->n_vertices = 0;
181
0
  vertices->n_chambers = 0;
182
0
183
0
  return vertices;
184
0
}
185
186
/* Compute the parametric vertices and the chamber decomposition
187
 * of the parametric polytope defined using the same constraints
188
 * as "bset" in the 0D case.
189
 * There is exactly one 0D vertex and a single chamber containing
190
 * the vertex.
191
 */
192
static __isl_give isl_vertices *vertices_0D(__isl_keep isl_basic_set *bset)
193
1
{
194
1
  isl_vertices *vertices;
195
1
196
1
  if (!bset)
197
0
    return NULL;
198
1
199
1
  vertices = isl_calloc_type(bset->ctx, isl_vertices);
200
1
  if (!vertices)
201
0
    return NULL;
202
1
  vertices->ref = 1;
203
1
  vertices->bset = isl_basic_set_copy(bset);
204
1
205
1
  vertices->v = isl_calloc_array(bset->ctx, struct isl_vertex, 1);
206
1
  if (!vertices->v)
207
0
    goto error;
208
1
  vertices->n_vertices = 1;
209
1
  vertices->v[0].vertex = isl_basic_set_copy(bset);
210
1
  vertices->v[0].dom = isl_basic_set_params(isl_basic_set_copy(bset));
211
1
  if (!vertices->v[0].vertex || !vertices->v[0].dom)
212
0
    goto error;
213
1
214
1
  vertices->c = isl_calloc_array(bset->ctx, struct isl_chamber, 1);
215
1
  if (!vertices->c)
216
0
    goto error;
217
1
  vertices->n_chambers = 1;
218
1
  vertices->c[0].n_vertices = 1;
219
1
  vertices->c[0].vertices = isl_calloc_array(bset->ctx, int, 1);
220
1
  if (!vertices->c[0].vertices)
221
0
    goto error;
222
1
  vertices->c[0].dom = isl_basic_set_copy(vertices->v[0].dom);
223
1
  if (!vertices->c[0].dom)
224
0
    goto error;
225
1
226
1
  return vertices;
227
0
error:
228
0
  isl_vertices_free(vertices);
229
0
  return NULL;
230
1
}
231
232
/* Is the row pointed to by "f" linearly independent of the "n" first
233
 * rows in "facets"?
234
 */
235
static int is_independent(__isl_keep isl_mat *facets, int n, isl_int *f)
236
84
{
237
84
  int rank;
238
84
239
84
  if (isl_seq_first_non_zero(f, facets->n_col) < 0)
240
16
    return 0;
241
68
242
68
  isl_seq_cpy(facets->row[n], f, facets->n_col);
243
68
  facets->n_row = n + 1;
244
68
  rank = isl_mat_rank(facets);
245
68
  if (rank < 0)
246
0
    return -1;
247
68
248
68
  return rank == n + 1;
249
68
}
250
251
/* Check whether we can select constraint "level", given the current selection
252
 * reflected by facets in "tab", the rows of "facets" and the earlier
253
 * "selected" elements of "selection".
254
 *
255
 * If the constraint is (strictly) redundant in the tableau, selecting it would
256
 * result in an empty tableau, so it can't be selected.
257
 * If the set variable part of the constraint is not linearly independent
258
 * of the set variable parts of the already selected constraints,
259
 * the constraint cannot be selected.
260
 * If selecting the constraint results in an empty tableau, the constraint
261
 * cannot be selected.
262
 * Finally, if selecting the constraint results in some explicitly
263
 * deselected constraints turning into equalities, then the corresponding
264
 * vertices have already been generated, so the constraint cannot be selected.
265
 */
266
static int can_select(__isl_keep isl_basic_set *bset, int level,
267
  struct isl_tab *tab, __isl_keep isl_mat *facets, int selected,
268
  int *selection)
269
100
{
270
100
  int i;
271
100
  int indep;
272
100
  unsigned ovar;
273
100
  struct isl_tab_undo *snap;
274
100
275
100
  if (isl_tab_is_redundant(tab, level))
276
16
    return 0;
277
84
278
84
  ovar = isl_space_offset(bset->dim, isl_dim_set);
279
84
280
84
  indep = is_independent(facets, selected, bset->ineq[level] + 1 + ovar);
281
84
  if (indep < 0)
282
0
    return -1;
283
84
  if (!indep)
284
22
    return 0;
285
62
286
62
  snap = isl_tab_snap(tab);
287
62
  if (isl_tab_select_facet(tab, level) < 0)
288
0
    return -1;
289
62
290
62
  if (tab->empty) {
291
0
    if (isl_tab_rollback(tab, snap) < 0)
292
0
      return -1;
293
0
    return 0;
294
0
  }
295
62
296
270
  
for (i = 0; 62
i < level;
++i208
) {
297
209
    int sgn;
298
209
299
209
    if (selection[i] != DESELECTED)
300
209
      
continue79
;
301
130
302
130
    if (isl_tab_is_equality(tab, i))
303
0
      sgn = 0;
304
130
    else if (isl_tab_is_redundant(tab, i))
305
0
      sgn = 1;
306
130
    else
307
130
      sgn = isl_tab_sign_of_max(tab, i);
308
130
    if (sgn < -1)
309
0
      return -1;
310
130
    if (sgn <= 0) {
311
1
      if (isl_tab_rollback(tab, snap) < 0)
312
0
        return -1;
313
1
      return 0;
314
1
    }
315
130
  }
316
62
317
62
  
return 161
;
318
62
}
319
320
/* Compute the parametric vertices and the chamber decomposition
321
 * of a parametric polytope that is not full-dimensional.
322
 *
323
 * Simply map the parametric polytope to a lower dimensional space
324
 * and map the resulting vertices back.
325
 */
326
static __isl_give isl_vertices *lower_dim_vertices(
327
  __isl_keep isl_basic_set *bset)
328
2
{
329
2
  isl_morph *morph;
330
2
  isl_vertices *vertices;
331
2
332
2
  bset = isl_basic_set_copy(bset);
333
2
  morph = isl_basic_set_full_compression(bset);
334
2
  bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
335
2
336
2
  vertices = isl_basic_set_compute_vertices(bset);
337
2
  isl_basic_set_free(bset);
338
2
339
2
  morph = isl_morph_inverse(morph);
340
2
341
2
  vertices = isl_morph_vertices(morph, vertices);
342
2
343
2
  return vertices;
344
2
}
345
346
/* Compute the parametric vertices and the chamber decomposition
347
 * of the parametric polytope defined using the same constraints
348
 * as "bset".  "bset" is assumed to have no existentially quantified
349
 * variables.
350
 *
351
 * The vertices themselves are computed in a fairly simplistic way.
352
 * We simply run through all combinations of d constraints,
353
 * with d the number of set variables, and check if those d constraints
354
 * define a vertex.  To avoid the generation of duplicate vertices,
355
 * which we may happen if a vertex is defined by more that d constraints,
356
 * we make sure we only generate the vertex for the d constraints with
357
 * smallest index.
358
 *
359
 * We set up a tableau and keep track of which facets have been
360
 * selected.  The tableau is marked strict_redundant so that we can be
361
 * sure that any constraint that is marked redundant (and that is not
362
 * also marked zero) is not an equality.
363
 * If a constraint is marked DESELECTED, it means the constraint was
364
 * SELECTED before (in combination with the same selection of earlier
365
 * constraints).  If such a deselected constraint turns out to be an
366
 * equality, then any vertex that may still be found with the current
367
 * selection has already been generated when the constraint was selected.
368
 * A constraint is marked UNSELECTED when there is no way selecting
369
 * the constraint could lead to a vertex (in combination with the current
370
 * selection of earlier constraints).
371
 *
372
 * The set variable coefficients of the selected constraints are stored
373
 * in the facets matrix.
374
 */
375
__isl_give isl_vertices *isl_basic_set_compute_vertices(
376
  __isl_keep isl_basic_set *bset)
377
6
{
378
6
  struct isl_tab *tab;
379
6
  int level;
380
6
  int init;
381
6
  unsigned nvar;
382
6
  int *selection = NULL;
383
6
  int selected;
384
6
  struct isl_tab_undo **snap = NULL;
385
6
  isl_mat *facets = NULL;
386
6
  struct isl_vertex_list *list = NULL;
387
6
  int n_vertices = 0;
388
6
  isl_vertices *vertices;
389
6
390
6
  if (!bset)
391
0
    return NULL;
392
6
393
6
  if (isl_basic_set_plain_is_empty(bset))
394
0
    return vertices_empty(bset);
395
6
396
6
  if (bset->n_eq != 0)
397
2
    return lower_dim_vertices(bset);
398
4
399
4
  isl_assert(bset->ctx, isl_basic_set_dim(bset, isl_dim_div) == 0,
400
4
    return NULL);
401
4
402
4
  if (isl_basic_set_dim(bset, isl_dim_set) == 0)
403
1
    return vertices_0D(bset);
404
3
405
3
  nvar = isl_basic_set_dim(bset, isl_dim_set);
406
3
407
3
  bset = isl_basic_set_copy(bset);
408
3
  bset = isl_basic_set_set_rational(bset);
409
3
  if (!bset)
410
0
    return NULL;
411
3
412
3
  tab = isl_tab_from_basic_set(bset, 0);
413
3
  if (!tab)
414
0
    goto error;
415
3
  tab->strict_redundant = 1;
416
3
417
3
  if (tab->empty)  {
418
0
    vertices = vertices_empty(bset);
419
0
    isl_basic_set_free(bset);
420
0
    isl_tab_free(tab);
421
0
    return vertices;
422
0
  }
423
3
424
3
  selection = isl_alloc_array(bset->ctx, int, bset->n_ineq);
425
3
  snap = isl_alloc_array(bset->ctx, struct isl_tab_undo *, bset->n_ineq);
426
3
  facets = isl_mat_alloc(bset->ctx, nvar, nvar);
427
3
  if ((bset->n_ineq && (!selection || !snap)) || !facets)
428
0
    goto error;
429
3
430
3
  level = 0;
431
3
  init = 1;
432
3
  selected = 0;
433
3
434
303
  while (level >= 0) {
435
300
    if (level >= bset->n_ineq ||
436
300
        
(261
!init261
&&
selection[level] != 161
SELECTED161
)) {
437
139
      --level;
438
139
      init = 0;
439
139
      continue;
440
139
    }
441
161
    if (init) {
442
100
      int ok;
443
100
      snap[level] = isl_tab_snap(tab);
444
100
      ok = can_select(bset, level, tab, facets, selected,
445
100
          selection);
446
100
      if (ok < 0)
447
0
        goto error;
448
100
      if (ok) {
449
61
        selection[level] = SELECTED;
450
61
        selected++;
451
61
      } else
452
39
        selection[level] = UNSELECTED;
453
100
    } else {
454
61
      selection[level] = DESELECTED;
455
61
      selected--;
456
61
      if (isl_tab_rollback(tab, snap[level]) < 0)
457
0
        goto error;
458
161
    }
459
161
    if (selected == nvar) {
460
25
      if (tab->n_dead == nvar) {
461
25
        isl_bool added = add_vertex(&list, bset, tab);
462
25
        if (added < 0)
463
0
          goto error;
464
25
        if (added)
465
24
          n_vertices++;
466
25
      }
467
25
      init = 0;
468
25
      continue;
469
136
    }
470
136
    ++level;
471
136
    init = 1;
472
136
  }
473
3
474
3
  isl_mat_free(facets);
475
3
  free(selection);
476
3
  free(snap);
477
3
478
3
  isl_tab_free(tab);
479
3
480
3
  vertices = vertices_from_list(bset, n_vertices, list);
481
3
482
3
  vertices = compute_chambers(bset, vertices);
483
3
484
3
  return vertices;
485
0
error:
486
0
  free_vertex_list(list);
487
0
  isl_mat_free(facets);
488
0
  free(selection);
489
0
  free(snap);
490
0
  isl_tab_free(tab);
491
0
  isl_basic_set_free(bset);
492
0
  return NULL;
493
3
}
494
495
struct isl_chamber_list {
496
  struct isl_chamber c;
497
  struct isl_chamber_list *next;
498
};
499
500
static void free_chamber_list(struct isl_chamber_list *list)
501
0
{
502
0
  struct isl_chamber_list *next;
503
0
504
0
  for (; list; list = next) {
505
0
    next = list->next;
506
0
    isl_basic_set_free(list->c.dom);
507
0
    free(list->c.vertices);
508
0
    free(list);
509
0
  }
510
0
}
511
512
/* Check whether the basic set "bset" is a superset of the basic set described
513
 * by "tab", i.e., check whether all constraints of "bset" are redundant.
514
 */
515
static isl_bool bset_covers_tab(__isl_keep isl_basic_set *bset,
516
  struct isl_tab *tab)
517
96
{
518
96
  int i;
519
96
520
96
  if (!bset || !tab)
521
0
    return isl_bool_error;
522
96
523
313
  
for (i = 0; 96
i < bset->n_ineq;
++i217
) {
524
258
    enum isl_ineq_type type = isl_tab_ineq_type(tab, bset->ineq[i]);
525
258
    switch (type) {
526
258
    
case isl_ineq_error:    return isl_bool_error0
;
527
258
    
case isl_ineq_redundant:  continue217
;
528
258
    
default:      return isl_bool_false41
;
529
258
    }
530
258
  }
531
96
532
96
  
return isl_bool_true55
;
533
96
}
534
535
static __isl_give isl_vertices *vertices_add_chambers(
536
  __isl_take isl_vertices *vertices, int n_chambers,
537
  struct isl_chamber_list *list)
538
3
{
539
3
  int i;
540
3
  isl_ctx *ctx;
541
3
  struct isl_chamber_list *next;
542
3
543
3
  ctx = isl_vertices_get_ctx(vertices);
544
3
  vertices->c = isl_alloc_array(ctx, struct isl_chamber, n_chambers);
545
3
  if (!vertices->c)
546
0
    goto error;
547
3
  vertices->n_chambers = n_chambers;
548
3
549
12
  for (i = 0; list; 
list = next, i++9
) {
550
9
    next = list->next;
551
9
    vertices->c[i] = list->c;
552
9
    free(list);
553
9
  }
554
3
555
3
  return vertices;
556
0
error:
557
0
  isl_vertices_free(vertices);
558
0
  free_chamber_list(list);
559
0
  return NULL;
560
3
}
561
562
/* Can "tab" be intersected with "bset" without resulting in
563
 * a lower-dimensional set.
564
 * "bset" itself is assumed to be full-dimensional.
565
 */
566
static isl_bool can_intersect(struct isl_tab *tab,
567
  __isl_keep isl_basic_set *bset)
568
79
{
569
79
  int i;
570
79
  struct isl_tab_undo *snap;
571
79
572
79
  if (bset->n_eq > 0)
573
79
    
isl_die0
(isl_basic_set_get_ctx(bset), isl_error_internal,
574
79
      "expecting full-dimensional input",
575
79
      return isl_bool_error);
576
79
577
79
  if (isl_tab_extend_cons(tab, bset->n_ineq) < 0)
578
0
    return isl_bool_error;
579
79
580
79
  snap = isl_tab_snap(tab);
581
79
582
308
  for (i = 0; i < bset->n_ineq; 
++i229
) {
583
229
    if (isl_tab_ineq_type(tab, bset->ineq[i]) == isl_ineq_redundant)
584
186
      continue;
585
43
    if (isl_tab_add_ineq(tab, bset->ineq[i]) < 0)
586
0
      return isl_bool_error;
587
43
  }
588
79
589
79
  if (isl_tab_detect_implicit_equalities(tab) < 0)
590
0
    return isl_bool_error;
591
79
  if (tab->n_dead) {
592
27
    if (isl_tab_rollback(tab, snap) < 0)
593
0
      return isl_bool_error;
594
27
    return isl_bool_false;
595
27
  }
596
52
597
52
  return isl_bool_true;
598
52
}
599
600
static int add_chamber(struct isl_chamber_list **list,
601
  __isl_keep isl_vertices *vertices, struct isl_tab *tab, int *selection)
602
9
{
603
9
  int n_frozen;
604
9
  int i, j;
605
9
  int n_vertices = 0;
606
9
  struct isl_tab_undo *snap;
607
9
  struct isl_chamber_list *c = NULL;
608
9
609
129
  for (i = 0; i < vertices->n_vertices; 
++i120
)
610
120
    if (selection[i])
611
52
      n_vertices++;
612
9
613
9
  snap = isl_tab_snap(tab);
614
9
615
38
  for (i = 0; i < tab->n_con && 
tab->con[i].frozen36
;
++i29
)
616
29
    tab->con[i].frozen = 0;
617
9
  n_frozen = i;
618
9
619
9
  if (isl_tab_detect_redundant(tab) < 0)
620
0
    return -1;
621
9
622
9
  c = isl_calloc_type(tab->mat->ctx, struct isl_chamber_list);
623
9
  if (!c)
624
0
    goto error;
625
9
  c->c.vertices = isl_alloc_array(tab->mat->ctx, int, n_vertices);
626
9
  if (n_vertices && !c->c.vertices)
627
0
    goto error;
628
9
  c->c.dom = isl_basic_set_copy(isl_tab_peek_bset(tab));
629
9
  c->c.dom = isl_basic_set_set_rational(c->c.dom);
630
9
  c->c.dom = isl_basic_set_cow(c->c.dom);
631
9
  c->c.dom = isl_basic_set_update_from_tab(c->c.dom, tab);
632
9
  c->c.dom = isl_basic_set_simplify(c->c.dom);
633
9
  c->c.dom = isl_basic_set_finalize(c->c.dom);
634
9
  if (!c->c.dom)
635
0
    goto error;
636
9
637
9
  c->c.n_vertices = n_vertices;
638
9
639
129
  for (i = 0, j = 0; i < vertices->n_vertices; 
++i120
)
640
120
    if (selection[i]) {
641
52
      c->c.vertices[j] = i;
642
52
      j++;
643
52
    }
644
9
645
9
  c->next = *list;
646
9
  *list = c;
647
9
648
38
  for (i = 0; i < n_frozen; 
++i29
)
649
29
    tab->con[i].frozen = 1;
650
9
651
9
  if (isl_tab_rollback(tab, snap) < 0)
652
0
    return -1;
653
9
654
9
  return 0;
655
0
error:
656
0
  free_chamber_list(c);
657
0
  return -1;
658
9
}
659
660
struct isl_facet_todo {
661
  struct isl_tab *tab;  /* A tableau representation of the facet */
662
  isl_basic_set *bset;    /* A normalized basic set representation */
663
  isl_vec *constraint;  /* Constraint pointing to the other side */
664
  struct isl_facet_todo *next;
665
};
666
667
static void free_todo(struct isl_facet_todo *todo)
668
10
{
669
20
  while (todo) {
670
10
    struct isl_facet_todo *next = todo->next;
671
10
672
10
    isl_tab_free(todo->tab);
673
10
    isl_basic_set_free(todo->bset);
674
10
    isl_vec_free(todo->constraint);
675
10
    free(todo);
676
10
677
10
    todo = next;
678
10
  }
679
10
}
680
681
static struct isl_facet_todo *create_todo(struct isl_tab *tab, int con)
682
10
{
683
10
  int i;
684
10
  int n_frozen;
685
10
  struct isl_tab_undo *snap;
686
10
  struct isl_facet_todo *todo;
687
10
688
10
  snap = isl_tab_snap(tab);
689
10
690
48
  for (i = 0; i < tab->n_con && tab->con[i].frozen; 
++i38
)
691
38
    tab->con[i].frozen = 0;
692
10
  n_frozen = i;
693
10
694
10
  if (isl_tab_detect_redundant(tab) < 0)
695
0
    return NULL;
696
10
697
10
  todo = isl_calloc_type(tab->mat->ctx, struct isl_facet_todo);
698
10
  if (!todo)
699
0
    return NULL;
700
10
701
10
  todo->constraint = isl_vec_alloc(tab->mat->ctx, 1 + tab->n_var);
702
10
  if (!todo->constraint)
703
0
    goto error;
704
10
  isl_seq_neg(todo->constraint->el, tab->bmap->ineq[con], 1 + tab->n_var);
705
10
  todo->bset = isl_basic_set_copy(isl_tab_peek_bset(tab));
706
10
  todo->bset = isl_basic_set_set_rational(todo->bset);
707
10
  todo->bset = isl_basic_set_cow(todo->bset);
708
10
  todo->bset = isl_basic_set_update_from_tab(todo->bset, tab);
709
10
  todo->bset = isl_basic_set_simplify(todo->bset);
710
10
  todo->bset = isl_basic_set_sort_constraints(todo->bset);
711
10
  if (!todo->bset)
712
0
    goto error;
713
10
  ISL_F_SET(todo->bset, ISL_BASIC_SET_NORMALIZED);
714
10
  todo->tab = isl_tab_dup(tab);
715
10
  if (!todo->tab)
716
0
    goto error;
717
10
718
48
  
for (i = 0; 10
i < n_frozen;
++i38
)
719
38
    tab->con[i].frozen = 1;
720
10
721
10
  if (isl_tab_rollback(tab, snap) < 0)
722
0
    goto error;
723
10
724
10
  return todo;
725
0
error:
726
0
  free_todo(todo);
727
0
  return NULL;
728
10
}
729
730
/* Create todo items for all interior facets of the chamber represented
731
 * by "tab" and collect them in "next".
732
 */
733
static int init_todo(struct isl_facet_todo **next, struct isl_tab *tab)
734
3
{
735
3
  int i;
736
3
  struct isl_tab_undo *snap;
737
3
  struct isl_facet_todo *todo;
738
3
739
3
  snap = isl_tab_snap(tab);
740
3
741
10
  for (i = 0; i < tab->n_con; 
++i7
) {
742
7
    if (tab->con[i].frozen)
743
5
      continue;
744
2
    if (tab->con[i].is_redundant)
745
0
      continue;
746
2
747
2
    if (isl_tab_select_facet(tab, i) < 0)
748
0
      return -1;
749
2
750
2
    todo = create_todo(tab, i);
751
2
    if (!todo)
752
0
      return -1;
753
2
754
2
    todo->next = *next;
755
2
    *next = todo;
756
2
757
2
    if (isl_tab_rollback(tab, snap) < 0)
758
0
      return -1;
759
2
  }
760
3
761
3
  return 0;
762
3
}
763
764
/* Does the linked list contain a todo item that is the opposite of "todo".
765
 * If so, return 1 and remove the opposite todo item.
766
 */
767
static int has_opposite(struct isl_facet_todo *todo,
768
  struct isl_facet_todo **list)
769
8
{
770
21
  for (; *list; 
list = &(*list)->next13
) {
771
15
    int eq;
772
15
    eq = isl_basic_set_plain_is_equal(todo->bset, (*list)->bset);
773
15
    if (eq < 0)
774
0
      return -1;
775
15
    if (!eq)
776
13
      continue;
777
2
    todo = *list;
778
2
    *list = todo->next;
779
2
    todo->next = NULL;
780
2
    free_todo(todo);
781
2
    return 1;
782
2
  }
783
8
784
8
  
return 06
;
785
8
}
786
787
/* Create todo items for all interior facets of the chamber represented
788
 * by "tab" and collect them in first->next, taking care to cancel
789
 * opposite todo items.
790
 */
791
static int update_todo(struct isl_facet_todo *first, struct isl_tab *tab)
792
6
{
793
6
  int i;
794
6
  struct isl_tab_undo *snap;
795
6
  struct isl_facet_todo *todo;
796
6
797
6
  snap = isl_tab_snap(tab);
798
6
799
40
  for (i = 0; i < tab->n_con; 
++i34
) {
800
34
    int drop;
801
34
802
34
    if (tab->con[i].frozen)
803
24
      continue;
804
10
    if (tab->con[i].is_redundant)
805
2
      continue;
806
8
807
8
    if (isl_tab_select_facet(tab, i) < 0)
808
0
      return -1;
809
8
810
8
    todo = create_todo(tab, i);
811
8
    if (!todo)
812
0
      return -1;
813
8
814
8
    drop = has_opposite(todo, &first->next);
815
8
    if (drop < 0)
816
0
      return -1;
817
8
818
8
    if (drop)
819
2
      free_todo(todo);
820
6
    else {
821
6
      todo->next = first->next;
822
6
      first->next = todo;
823
6
    }
824
8
825
8
    if (isl_tab_rollback(tab, snap) < 0)
826
0
      return -1;
827
8
  }
828
6
829
6
  return 0;
830
6
}
831
832
/* Compute the chamber decomposition of the parametric polytope respresented
833
 * by "bset" given the parametric vertices and their activity domains.
834
 *
835
 * We are only interested in full-dimensional chambers.
836
 * Each of these chambers is the intersection of the activity domains of
837
 * one or more vertices and the union of all chambers is equal to the
838
 * projection of the entire parametric polytope onto the parameter space.
839
 *
840
 * We first create an initial chamber by intersecting as many activity
841
 * domains as possible without ending up with an empty or lower-dimensional
842
 * set.  As a minor optimization, we only consider those activity domains
843
 * that contain some arbitrary point.
844
 *
845
 * For each of the interior facets of the chamber, we construct a todo item,
846
 * containing the facet and a constraint containing the other side of the facet,
847
 * for constructing the chamber on the other side.
848
 * While their are any todo items left, we pick a todo item and
849
 * create the required chamber by intersecting all activity domains
850
 * that contain the facet and have a full-dimensional intersection with
851
 * the other side of the facet.  For each of the interior facets, we
852
 * again create todo items, taking care to cancel opposite todo items.
853
 */
854
static __isl_give isl_vertices *compute_chambers(__isl_take isl_basic_set *bset,
855
  __isl_take isl_vertices *vertices)
856
3
{
857
3
  int i;
858
3
  isl_ctx *ctx;
859
3
  isl_vec *sample = NULL;
860
3
  struct isl_tab *tab = NULL;
861
3
  struct isl_tab_undo *snap;
862
3
  int *selection = NULL;
863
3
  int n_chambers = 0;
864
3
  struct isl_chamber_list *list = NULL;
865
3
  struct isl_facet_todo *todo = NULL;
866
3
867
3
  if (!bset || !vertices)
868
0
    goto error;
869
3
870
3
  ctx = isl_vertices_get_ctx(vertices);
871
3
  selection = isl_alloc_array(ctx, int, vertices->n_vertices);
872
3
  if (vertices->n_vertices && !selection)
873
0
    goto error;
874
3
875
3
  bset = isl_basic_set_params(bset);
876
3
877
3
  tab = isl_tab_from_basic_set(bset, 1);
878
3
  if (!tab)
879
0
    goto error;
880
8
  
for (i = 0; 3
i < bset->n_ineq;
++i5
)
881
5
    if (isl_tab_freeze_constraint(tab, i) < 0)
882
0
      goto error;
883
3
  isl_basic_set_free(bset);
884
3
885
3
  snap = isl_tab_snap(tab);
886
3
887
3
  sample = isl_tab_get_sample_value(tab);
888
3
889
27
  for (i = 0; i < vertices->n_vertices; 
++i24
) {
890
24
    selection[i] = isl_basic_set_contains(vertices->v[i].dom, sample);
891
24
    if (selection[i] < 0)
892
0
      goto error;
893
24
    if (!selection[i])
894
0
      continue;
895
24
    selection[i] = can_intersect(tab, vertices->v[i].dom);
896
24
    if (selection[i] < 0)
897
0
      goto error;
898
24
  }
899
3
900
3
  if (isl_tab_detect_redundant(tab) < 0)
901
0
    goto error;
902
3
903
3
  if (add_chamber(&list, vertices, tab, selection) < 0)
904
0
    goto error;
905
3
  n_chambers++;
906
3
907
3
  if (init_todo(&todo, tab) < 0)
908
0
    goto error;
909
3
910
9
  
while (3
todo) {
911
6
    struct isl_facet_todo *next;
912
6
913
6
    if (isl_tab_rollback(tab, snap) < 0)
914
0
      goto error;
915
6
916
6
    if (isl_tab_add_ineq(tab, todo->constraint->el) < 0)
917
0
      goto error;
918
6
    if (isl_tab_freeze_constraint(tab, tab->n_con - 1) < 0)
919
0
      goto error;
920
6
921
102
    
for (i = 0; 6
i < vertices->n_vertices;
++i96
) {
922
96
      selection[i] = bset_covers_tab(vertices->v[i].dom,
923
96
              todo->tab);
924
96
      if (selection[i] < 0)
925
0
        goto error;
926
96
      if (!selection[i])
927
41
        continue;
928
55
      selection[i] = can_intersect(tab, vertices->v[i].dom);
929
55
      if (selection[i] < 0)
930
0
        goto error;
931
55
    }
932
6
933
6
    if (isl_tab_detect_redundant(tab) < 0)
934
0
      goto error;
935
6
936
6
    if (add_chamber(&list, vertices, tab, selection) < 0)
937
0
      goto error;
938
6
    n_chambers++;
939
6
940
6
    if (update_todo(todo, tab) < 0)
941
0
      goto error;
942
6
943
6
    next = todo->next;
944
6
    todo->next = NULL;
945
6
    free_todo(todo);
946
6
    todo = next;
947
6
  }
948
3
949
3
  isl_vec_free(sample);
950
3
951
3
  isl_tab_free(tab);
952
3
  free(selection);
953
3
954
3
  vertices = vertices_add_chambers(vertices, n_chambers, list);
955
3
956
27
  for (i = 0; vertices && i < vertices->n_vertices; 
++i24
) {
957
24
    isl_basic_set_free(vertices->v[i].dom);
958
24
    vertices->v[i].dom = NULL;
959
24
  }
960
3
961
3
  return vertices;
962
0
error:
963
0
  free_chamber_list(list);
964
0
  free_todo(todo);
965
0
  isl_vec_free(sample);
966
0
  isl_tab_free(tab);
967
0
  free(selection);
968
0
  if (!tab)
969
0
    isl_basic_set_free(bset);
970
0
  isl_vertices_free(vertices);
971
0
  return NULL;
972
3
}
973
974
isl_ctx *isl_vertex_get_ctx(__isl_keep isl_vertex *vertex)
975
9
{
976
9
  return vertex ? isl_vertices_get_ctx(vertex->vertices) : NULL;
977
9
}
978
979
int isl_vertex_get_id(__isl_keep isl_vertex *vertex)
980
0
{
981
0
  return vertex ? vertex->id : -1;
982
0
}
983
984
/* Return the activity domain of the vertex "vertex".
985
 */
986
__isl_give isl_basic_set *isl_vertex_get_domain(__isl_keep isl_vertex *vertex)
987
9
{
988
9
  struct isl_vertex *v;
989
9
990
9
  if (!vertex)
991
0
    return NULL;
992
9
993
9
  v = &vertex->vertices->v[vertex->id];
994
9
  if (!v->dom) {
995
8
    v->dom = isl_basic_set_copy(v->vertex);
996
8
    v->dom = isl_basic_set_params(v->dom);
997
8
    v->dom = isl_basic_set_set_integral(v->dom);
998
8
  }
999
9
1000
9
  return isl_basic_set_copy(v->dom);
1001
9
}
1002
1003
/* Return a multiple quasi-affine expression describing the vertex "vertex"
1004
 * in terms of the parameters,
1005
 */
1006
__isl_give isl_multi_aff *isl_vertex_get_expr(__isl_keep isl_vertex *vertex)
1007
9
{
1008
9
  struct isl_vertex *v;
1009
9
  isl_basic_set *bset;
1010
9
1011
9
  if (!vertex)
1012
0
    return NULL;
1013
9
1014
9
  v = &vertex->vertices->v[vertex->id];
1015
9
1016
9
  bset = isl_basic_set_copy(v->vertex);
1017
9
  return isl_multi_aff_from_basic_set_equalities(bset);
1018
9
}
1019
1020
static __isl_give isl_vertex *isl_vertex_alloc(__isl_take isl_vertices *vertices,
1021
  int id)
1022
9
{
1023
9
  isl_ctx *ctx;
1024
9
  isl_vertex *vertex;
1025
9
1026
9
  if (!vertices)
1027
0
    return NULL;
1028
9
1029
9
  ctx = isl_vertices_get_ctx(vertices);
1030
9
  vertex = isl_alloc_type(ctx, isl_vertex);
1031
9
  if (!vertex)
1032
0
    goto error;
1033
9
1034
9
  vertex->vertices = vertices;
1035
9
  vertex->id = id;
1036
9
1037
9
  return vertex;
1038
0
error:
1039
0
  isl_vertices_free(vertices);
1040
0
  return NULL;
1041
9
}
1042
1043
void isl_vertex_free(__isl_take isl_vertex *vertex)
1044
9
{
1045
9
  if (!vertex)
1046
0
    return;
1047
9
  isl_vertices_free(vertex->vertices);
1048
9
  free(vertex);
1049
9
}
1050
1051
isl_ctx *isl_cell_get_ctx(__isl_keep isl_cell *cell)
1052
0
{
1053
0
  return cell ? cell->dom->ctx : NULL;
1054
0
}
1055
1056
__isl_give isl_basic_set *isl_cell_get_domain(__isl_keep isl_cell *cell)
1057
7
{
1058
7
  return cell ? isl_basic_set_copy(cell->dom) : NULL;
1059
7
}
1060
1061
static __isl_give isl_cell *isl_cell_alloc(__isl_take isl_vertices *vertices,
1062
  __isl_take isl_basic_set *dom, int id)
1063
7
{
1064
7
  int i;
1065
7
  isl_cell *cell = NULL;
1066
7
1067
7
  if (!vertices || !dom)
1068
0
    goto error;
1069
7
1070
7
  cell = isl_calloc_type(dom->ctx, isl_cell);
1071
7
  if (!cell)
1072
0
    goto error;
1073
7
1074
7
  cell->n_vertices = vertices->c[id].n_vertices;
1075
7
  cell->ids = isl_alloc_array(dom->ctx, int, cell->n_vertices);
1076
7
  if (cell->n_vertices && !cell->ids)
1077
0
    goto error;
1078
51
  
for (i = 0; 7
i < cell->n_vertices;
++i44
)
1079
44
    cell->ids[i] = vertices->c[id].vertices[i];
1080
7
  cell->vertices = vertices;
1081
7
  cell->dom = dom;
1082
7
1083
7
  return cell;
1084
0
error:
1085
0
  isl_cell_free(cell);
1086
0
  isl_vertices_free(vertices);
1087
0
  isl_basic_set_free(dom);
1088
0
  return NULL;
1089
7
}
1090
1091
void isl_cell_free(__isl_take isl_cell *cell)
1092
7
{
1093
7
  if (!cell)
1094
0
    return;
1095
7
1096
7
  isl_vertices_free(cell->vertices);
1097
7
  free(cell->ids);
1098
7
  isl_basic_set_free(cell->dom);
1099
7
  free(cell);
1100
7
}
1101
1102
/* Create a tableau of the cone obtained by first homogenizing the given
1103
 * polytope and then making all inequalities strict by setting the
1104
 * constant term to -1.
1105
 */
1106
static struct isl_tab *tab_for_shifted_cone(__isl_keep isl_basic_set *bset)
1107
1
{
1108
1
  int i;
1109
1
  isl_vec *c = NULL;
1110
1
  struct isl_tab *tab;
1111
1
1112
1
  if (!bset)
1113
0
    return NULL;
1114
1
  tab = isl_tab_alloc(bset->ctx, bset->n_eq + bset->n_ineq + 1,
1115
1
          1 + isl_basic_set_total_dim(bset), 0);
1116
1
  if (!tab)
1117
0
    return NULL;
1118
1
  tab->rational = ISL_F_ISSET(bset, ISL_BASIC_SET_RATIONAL);
1119
1
  if (ISL_F_ISSET(bset, ISL_BASIC_MAP_EMPTY)) {
1120
0
    if (isl_tab_mark_empty(tab) < 0)
1121
0
      goto error;
1122
0
    return tab;
1123
0
  }
1124
1
1125
1
  c = isl_vec_alloc(bset->ctx, 1 + 1 + isl_basic_set_total_dim(bset));
1126
1
  if (!c)
1127
0
    goto error;
1128
1
1129
1
  isl_int_set_si(c->el[0], 0);
1130
1
  for (i = 0; i < bset->n_eq; 
++i0
) {
1131
0
    isl_seq_cpy(c->el + 1, bset->eq[i], c->size - 1);
1132
0
    if (isl_tab_add_eq(tab, c->el) < 0)
1133
0
      goto error;
1134
0
  }
1135
1
1136
1
  isl_int_set_si(c->el[0], -1);
1137
4
  for (i = 0; i < bset->n_ineq; 
++i3
) {
1138
3
    isl_seq_cpy(c->el + 1, bset->ineq[i], c->size - 1);
1139
3
    if (isl_tab_add_ineq(tab, c->el) < 0)
1140
0
      goto error;
1141
3
    if (tab->empty) {
1142
0
      isl_vec_free(c);
1143
0
      return tab;
1144
0
    }
1145
3
  }
1146
1
1147
1
  isl_seq_clr(c->el + 1, c->size - 1);
1148
1
  isl_int_set_si(c->el[1], 1);
1149
1
  if (isl_tab_add_ineq(tab, c->el) < 0)
1150
0
    goto error;
1151
1
1152
1
  isl_vec_free(c);
1153
1
  return tab;
1154
0
error:
1155
0
  isl_vec_free(c);
1156
0
  isl_tab_free(tab);
1157
0
  return NULL;
1158
1
}
1159
1160
/* Compute an interior point of "bset" by selecting an interior
1161
 * point in homogeneous space and projecting the point back down.
1162
 */
1163
static __isl_give isl_vec *isl_basic_set_interior_point(
1164
  __isl_keep isl_basic_set *bset)
1165
1
{
1166
1
  isl_vec *vec;
1167
1
  struct isl_tab *tab;
1168
1
1169
1
  tab = tab_for_shifted_cone(bset);
1170
1
  vec = isl_tab_get_sample_value(tab);
1171
1
  isl_tab_free(tab);
1172
1
  if (!vec)
1173
0
    return NULL;
1174
1
1175
1
  isl_seq_cpy(vec->el, vec->el + 1, vec->size - 1);
1176
1
  vec->size--;
1177
1
1178
1
  return vec;
1179
1
}
1180
1181
/* Call "fn" on all chambers of the parametric polytope with the shared
1182
 * facets of neighboring chambers only appearing in one of the chambers.
1183
 *
1184
 * We pick an interior point from one of the chambers and then make
1185
 * all constraints that do not satisfy this point strict.
1186
 * For constraints that saturate the interior point, the sign
1187
 * of the first non-zero coefficient is used to determine which
1188
 * of the two (internal) constraints should be tightened.
1189
 */
1190
isl_stat isl_vertices_foreach_disjoint_cell(__isl_keep isl_vertices *vertices,
1191
  isl_stat (*fn)(__isl_take isl_cell *cell, void *user), void *user)
1192
1
{
1193
1
  int i;
1194
1
  isl_vec *vec;
1195
1
  isl_cell *cell;
1196
1
1197
1
  if (!vertices)
1198
0
    return isl_stat_error;
1199
1
1200
1
  if (vertices->n_chambers == 0)
1201
0
    return isl_stat_ok;
1202
1
1203
1
  if (vertices->n_chambers == 1) {
1204
0
    isl_basic_set *dom = isl_basic_set_copy(vertices->c[0].dom);
1205
0
    dom = isl_basic_set_set_integral(dom);
1206
0
    cell = isl_cell_alloc(isl_vertices_copy(vertices), dom, 0);
1207
0
    if (!cell)
1208
0
      return isl_stat_error;
1209
0
    return fn(cell, user);
1210
0
  }
1211
1
1212
1
  vec = isl_basic_set_interior_point(vertices->c[0].dom);
1213
1
  if (!vec)
1214
0
    return isl_stat_error;
1215
1
1216
8
  
for (i = 0; 1
i < vertices->n_chambers;
++i7
) {
1217
7
    int r;
1218
7
    isl_basic_set *dom = isl_basic_set_copy(vertices->c[i].dom);
1219
7
    if (i)
1220
6
      dom = isl_basic_set_tighten_outward(dom, vec);
1221
7
    dom = isl_basic_set_set_integral(dom);
1222
7
    cell = isl_cell_alloc(isl_vertices_copy(vertices), dom, i);
1223
7
    if (!cell)
1224
0
      goto error;
1225
7
    r = fn(cell, user);
1226
7
    if (r < 0)
1227
0
      goto error;
1228
7
  }
1229
1
1230
1
  isl_vec_free(vec);
1231
1
1232
1
  return isl_stat_ok;
1233
0
error:
1234
0
  isl_vec_free(vec);
1235
0
  return isl_stat_error;
1236
1
}
1237
1238
isl_stat isl_vertices_foreach_cell(__isl_keep isl_vertices *vertices,
1239
  isl_stat (*fn)(__isl_take isl_cell *cell, void *user), void *user)
1240
0
{
1241
0
  int i;
1242
0
  isl_cell *cell;
1243
0
1244
0
  if (!vertices)
1245
0
    return isl_stat_error;
1246
0
1247
0
  if (vertices->n_chambers == 0)
1248
0
    return isl_stat_ok;
1249
0
1250
0
  for (i = 0; i < vertices->n_chambers; ++i) {
1251
0
    isl_stat r;
1252
0
    isl_basic_set *dom = isl_basic_set_copy(vertices->c[i].dom);
1253
0
1254
0
    cell = isl_cell_alloc(isl_vertices_copy(vertices), dom, i);
1255
0
    if (!cell)
1256
0
      return isl_stat_error;
1257
0
1258
0
    r = fn(cell, user);
1259
0
    if (r < 0)
1260
0
      return isl_stat_error;
1261
0
  }
1262
0
1263
0
  return isl_stat_ok;
1264
0
}
1265
1266
isl_stat isl_vertices_foreach_vertex(__isl_keep isl_vertices *vertices,
1267
  isl_stat (*fn)(__isl_take isl_vertex *vertex, void *user), void *user)
1268
3
{
1269
3
  int i;
1270
3
  isl_vertex *vertex;
1271
3
1272
3
  if (!vertices)
1273
0
    return isl_stat_error;
1274
3
1275
3
  if (vertices->n_vertices == 0)
1276
0
    return isl_stat_ok;
1277
3
1278
12
  
for (i = 0; 3
i < vertices->n_vertices;
++i9
) {
1279
9
    isl_stat r;
1280
9
1281
9
    vertex = isl_vertex_alloc(isl_vertices_copy(vertices), i);
1282
9
    if (!vertex)
1283
0
      return isl_stat_error;
1284
9
1285
9
    r = fn(vertex, user);
1286
9
    if (r < 0)
1287
0
      return isl_stat_error;
1288
9
  }
1289
3
1290
3
  return isl_stat_ok;
1291
3
}
1292
1293
isl_stat isl_cell_foreach_vertex(__isl_keep isl_cell *cell,
1294
  isl_stat (*fn)(__isl_take isl_vertex *vertex, void *user), void *user)
1295
0
{
1296
0
  int i;
1297
0
  isl_vertex *vertex;
1298
0
1299
0
  if (!cell)
1300
0
    return isl_stat_error;
1301
0
1302
0
  if (cell->n_vertices == 0)
1303
0
    return isl_stat_ok;
1304
0
1305
0
  for (i = 0; i < cell->n_vertices; ++i) {
1306
0
    isl_stat r;
1307
0
1308
0
    vertex = isl_vertex_alloc(isl_vertices_copy(cell->vertices),
1309
0
            cell->ids[i]);
1310
0
    if (!vertex)
1311
0
      return isl_stat_error;
1312
0
1313
0
    r = fn(vertex, user);
1314
0
    if (r < 0)
1315
0
      return isl_stat_error;
1316
0
  }
1317
0
1318
0
  return isl_stat_ok;
1319
0
}
1320
1321
isl_ctx *isl_vertices_get_ctx(__isl_keep isl_vertices *vertices)
1322
24
{
1323
24
  return vertices ? vertices->bset->ctx : NULL;
1324
24
}
1325
1326
int isl_vertices_get_n_vertices(__isl_keep isl_vertices *vertices)
1327
3
{
1328
3
  return vertices ? vertices->n_vertices : 
-10
;
1329
3
}
1330
1331
__isl_give isl_vertices *isl_morph_vertices(__isl_take isl_morph *morph,
1332
  __isl_take isl_vertices *vertices)
1333
2
{
1334
2
  int i;
1335
2
  isl_morph *param_morph = NULL;
1336
2
1337
2
  if (!morph || !vertices)
1338
0
    goto error;
1339
2
1340
2
  isl_assert(vertices->bset->ctx, vertices->ref == 1, goto error);
1341
2
1342
2
  param_morph = isl_morph_copy(morph);
1343
2
  param_morph = isl_morph_dom_params(param_morph);
1344
2
  param_morph = isl_morph_ran_params(param_morph);
1345
2
1346
5
  for (i = 0; i < vertices->n_vertices; 
++i3
) {
1347
3
    vertices->v[i].dom = isl_morph_basic_set(
1348
3
      isl_morph_copy(param_morph), vertices->v[i].dom);
1349
3
    vertices->v[i].vertex = isl_morph_basic_set(
1350
3
      isl_morph_copy(morph), vertices->v[i].vertex);
1351
3
    if (!vertices->v[i].vertex)
1352
0
      goto error;
1353
3
  }
1354
2
1355
4
  
for (i = 0; 2
i < vertices->n_chambers;
++i2
) {
1356
2
    vertices->c[i].dom = isl_morph_basic_set(
1357
2
      isl_morph_copy(param_morph), vertices->c[i].dom);
1358
2
    if (!vertices->c[i].dom)
1359
0
      goto error;
1360
2
  }
1361
2
1362
2
  isl_morph_free(param_morph);
1363
2
  isl_morph_free(morph);
1364
2
  return vertices;
1365
0
error:
1366
0
  isl_morph_free(param_morph);
1367
0
  isl_morph_free(morph);
1368
0
  isl_vertices_free(vertices);
1369
0
  return NULL;
1370
2
}
1371
1372
/* Construct a simplex isl_cell spanned by the vertices with indices in
1373
 * "simplex_ids" and "other_ids" and call "fn" on this isl_cell.
1374
 */
1375
static isl_stat call_on_simplex(__isl_keep isl_cell *cell,
1376
  int *simplex_ids, int n_simplex, int *other_ids, int n_other,
1377
  isl_stat (*fn)(__isl_take isl_cell *simplex, void *user), void *user)
1378
0
{
1379
0
  int i;
1380
0
  isl_ctx *ctx;
1381
0
  struct isl_cell *simplex;
1382
0
1383
0
  ctx = isl_cell_get_ctx(cell);
1384
0
1385
0
  simplex = isl_calloc_type(ctx, struct isl_cell);
1386
0
  if (!simplex)
1387
0
    return isl_stat_error;
1388
0
  simplex->vertices = isl_vertices_copy(cell->vertices);
1389
0
  if (!simplex->vertices)
1390
0
    goto error;
1391
0
  simplex->dom = isl_basic_set_copy(cell->dom);
1392
0
  if (!simplex->dom)
1393
0
    goto error;
1394
0
  simplex->n_vertices = n_simplex + n_other;
1395
0
  simplex->ids = isl_alloc_array(ctx, int, simplex->n_vertices);
1396
0
  if (!simplex->ids)
1397
0
    goto error;
1398
0
1399
0
  for (i = 0; i < n_simplex; ++i)
1400
0
    simplex->ids[i] = simplex_ids[i];
1401
0
  for (i = 0; i < n_other; ++i)
1402
0
    simplex->ids[n_simplex + i] = other_ids[i];
1403
0
1404
0
  return fn(simplex, user);
1405
0
error:
1406
0
  isl_cell_free(simplex);
1407
0
  return isl_stat_error;
1408
0
}
1409
1410
/* Check whether the parametric vertex described by "vertex"
1411
 * lies on the facet corresponding to constraint "facet" of "bset".
1412
 * The isl_vec "v" is a temporary vector than can be used by this function.
1413
 *
1414
 * We eliminate the variables from the facet constraint using the
1415
 * equalities defining the vertex and check if the result is identical
1416
 * to zero.
1417
 *
1418
 * It would probably be better to keep track of the constraints defining
1419
 * a vertex during the vertex construction so that we could simply look
1420
 * it up here.
1421
 */
1422
static int vertex_on_facet(__isl_keep isl_basic_set *vertex,
1423
  __isl_keep isl_basic_set *bset, int facet, __isl_keep isl_vec *v)
1424
0
{
1425
0
  int i;
1426
0
  isl_int m;
1427
0
1428
0
  isl_seq_cpy(v->el, bset->ineq[facet], v->size);
1429
0
1430
0
  isl_int_init(m);
1431
0
  for (i = 0; i < vertex->n_eq; ++i) {
1432
0
    int k = isl_seq_last_non_zero(vertex->eq[i], v->size);
1433
0
    isl_seq_elim(v->el, vertex->eq[i], k, v->size, &m);
1434
0
  }
1435
0
  isl_int_clear(m);
1436
0
1437
0
  return isl_seq_first_non_zero(v->el, v->size) == -1;
1438
0
}
1439
1440
/* Triangulate the polytope spanned by the vertices with ids
1441
 * in "simplex_ids" and "other_ids" and call "fn" on each of
1442
 * the resulting simplices.
1443
 * If the input polytope is already a simplex, we simply call "fn".
1444
 * Otherwise, we pick a point from "other_ids" and add it to "simplex_ids".
1445
 * Then we consider each facet of "bset" that does not contain the point
1446
 * we just picked, but does contain some of the other points in "other_ids"
1447
 * and call ourselves recursively on the polytope spanned by the new
1448
 * "simplex_ids" and those points in "other_ids" that lie on the facet.
1449
 */
1450
static isl_stat triangulate(__isl_keep isl_cell *cell, __isl_keep isl_vec *v,
1451
  int *simplex_ids, int n_simplex, int *other_ids, int n_other,
1452
  isl_stat (*fn)(__isl_take isl_cell *simplex, void *user), void *user)
1453
0
{
1454
0
  int i, j, k;
1455
0
  int d, nparam;
1456
0
  int *ids;
1457
0
  isl_ctx *ctx;
1458
0
  isl_basic_set *vertex;
1459
0
  isl_basic_set *bset;
1460
0
1461
0
  ctx = isl_cell_get_ctx(cell);
1462
0
  d = isl_basic_set_dim(cell->vertices->bset, isl_dim_set);
1463
0
  nparam = isl_basic_set_dim(cell->vertices->bset, isl_dim_param);
1464
0
1465
0
  if (n_simplex + n_other == d + 1)
1466
0
    return call_on_simplex(cell, simplex_ids, n_simplex,
1467
0
               other_ids, n_other, fn, user);
1468
0
1469
0
  simplex_ids[n_simplex] = other_ids[0];
1470
0
  vertex = cell->vertices->v[other_ids[0]].vertex;
1471
0
  bset = cell->vertices->bset;
1472
0
1473
0
  ids = isl_alloc_array(ctx, int, n_other - 1);
1474
0
  if (!ids)
1475
0
    goto error;
1476
0
  for (i = 0; i < bset->n_ineq; ++i) {
1477
0
    if (isl_seq_first_non_zero(bset->ineq[i] + 1 + nparam, d) == -1)
1478
0
      continue;
1479
0
    if (vertex_on_facet(vertex, bset, i, v))
1480
0
      continue;
1481
0
1482
0
    for (j = 1, k = 0; j < n_other; ++j) {
1483
0
      isl_basic_set *ov;
1484
0
      ov = cell->vertices->v[other_ids[j]].vertex;
1485
0
      if (vertex_on_facet(ov, bset, i, v))
1486
0
        ids[k++] = other_ids[j];
1487
0
    }
1488
0
    if (k == 0)
1489
0
      continue;
1490
0
1491
0
    if (triangulate(cell, v, simplex_ids, n_simplex + 1,
1492
0
        ids, k, fn, user) < 0)
1493
0
      goto error;
1494
0
  }
1495
0
  free(ids);
1496
0
1497
0
  return isl_stat_ok;
1498
0
error:
1499
0
  free(ids);
1500
0
  return isl_stat_error;
1501
0
}
1502
1503
/* Triangulate the given cell and call "fn" on each of the resulting
1504
 * simplices.
1505
 */
1506
isl_stat isl_cell_foreach_simplex(__isl_take isl_cell *cell,
1507
  isl_stat (*fn)(__isl_take isl_cell *simplex, void *user), void *user)
1508
0
{
1509
0
  int d, total;
1510
0
  int r;
1511
0
  isl_ctx *ctx;
1512
0
  isl_vec *v = NULL;
1513
0
  int *simplex_ids = NULL;
1514
0
1515
0
  if (!cell)
1516
0
    return isl_stat_error;
1517
0
1518
0
  d = isl_basic_set_dim(cell->vertices->bset, isl_dim_set);
1519
0
  total = isl_basic_set_total_dim(cell->vertices->bset);
1520
0
1521
0
  if (cell->n_vertices == d + 1)
1522
0
    return fn(cell, user);
1523
0
1524
0
  ctx = isl_cell_get_ctx(cell);
1525
0
  simplex_ids = isl_alloc_array(ctx, int, d + 1);
1526
0
  if (!simplex_ids)
1527
0
    goto error;
1528
0
1529
0
  v = isl_vec_alloc(ctx, 1 + total);
1530
0
  if (!v)
1531
0
    goto error;
1532
0
1533
0
  r = triangulate(cell, v, simplex_ids, 0,
1534
0
      cell->ids, cell->n_vertices, fn, user);
1535
0
1536
0
  isl_vec_free(v);
1537
0
  free(simplex_ids);
1538
0
1539
0
  isl_cell_free(cell);
1540
0
1541
0
  return r;
1542
0
error:
1543
0
  free(simplex_ids);
1544
0
  isl_vec_free(v);
1545
0
  isl_cell_free(cell);
1546
0
  return isl_stat_error;
1547
0
}