Coverage Report

Created: 2017-06-23 12:40

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