2 * Copyright 2008-2009 Katholieke Universiteit Leuven
4 * Use of this software is governed by the GNU LGPLv2.1 license
6 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
15 #include <isl_constraint.h>
19 void test_read(struct isl_ctx
*ctx
)
21 char filename
[PATH_MAX
];
24 struct isl_basic_set
*bset1
, *bset2
;
25 const char *str
= "{[y]: Exists ( alpha : 2alpha = y)}";
27 n
= snprintf(filename
, sizeof(filename
),
28 "%s/test_inputs/set.omega", srcdir
);
29 assert(n
< sizeof(filename
));
30 input
= fopen(filename
, "r");
33 bset1
= isl_basic_set_read_from_file(ctx
, input
, 0);
34 bset2
= isl_basic_set_read_from_str(ctx
, str
, 0);
36 assert(isl_basic_set_is_equal(bset1
, bset2
) == 1);
38 isl_basic_set_free(bset1
);
39 isl_basic_set_free(bset2
);
44 /* Construct the basic set { [i] : 5 <= i <= N } */
45 void test_construction(struct isl_ctx
*ctx
)
49 struct isl_basic_set
*bset
;
50 struct isl_constraint
*c
;
54 dim
= isl_dim_set_alloc(ctx
, 1, 1);
55 bset
= isl_basic_set_universe(dim
);
57 c
= isl_inequality_alloc(isl_dim_copy(bset
->dim
));
58 isl_int_set_si(v
, -1);
59 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
61 isl_constraint_set_coefficient(c
, isl_dim_param
, 0, v
);
62 bset
= isl_basic_set_add_constraint(bset
, c
);
64 c
= isl_inequality_alloc(isl_dim_copy(bset
->dim
));
66 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
67 isl_int_set_si(v
, -5);
68 isl_constraint_set_constant(c
, v
);
69 bset
= isl_basic_set_add_constraint(bset
, c
);
71 isl_basic_set_free(bset
);
76 void test_dim(struct isl_ctx
*ctx
)
80 map1
= isl_map_read_from_str(ctx
,
81 "[n] -> { [i] -> [j] : exists (a = [i/10] : i - 10a <= n ) }", -1);
82 map1
= isl_map_add(map1
, isl_dim_in
, 1);
83 map2
= isl_map_read_from_str(ctx
,
84 "[n] -> { [i,k] -> [j] : exists (a = [i/10] : i - 10a <= n ) }", -1);
85 assert(isl_map_is_equal(map1
, map2
));
90 void test_div(struct isl_ctx
*ctx
)
96 struct isl_basic_set
*bset
;
97 struct isl_constraint
*c
;
102 dim
= isl_dim_set_alloc(ctx
, 0, 1);
103 bset
= isl_basic_set_universe(dim
);
105 c
= isl_equality_alloc(isl_dim_copy(bset
->dim
));
106 isl_int_set_si(v
, -1);
107 isl_constraint_set_constant(c
, v
);
108 isl_int_set_si(v
, 1);
109 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
110 div
= isl_div_alloc(isl_dim_copy(bset
->dim
));
111 c
= isl_constraint_add_div(c
, div
, &pos
);
112 isl_int_set_si(v
, 3);
113 isl_constraint_set_coefficient(c
, isl_dim_div
, pos
, v
);
114 bset
= isl_basic_set_add_constraint(bset
, c
);
116 c
= isl_equality_alloc(isl_dim_copy(bset
->dim
));
117 isl_int_set_si(v
, 1);
118 isl_constraint_set_constant(c
, v
);
119 isl_int_set_si(v
, -1);
120 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
121 div
= isl_div_alloc(isl_dim_copy(bset
->dim
));
122 c
= isl_constraint_add_div(c
, div
, &pos
);
123 isl_int_set_si(v
, 3);
124 isl_constraint_set_coefficient(c
, isl_dim_div
, pos
, v
);
125 bset
= isl_basic_set_add_constraint(bset
, c
);
127 assert(bset
->n_div
== 1);
128 isl_basic_set_free(bset
);
131 dim
= isl_dim_set_alloc(ctx
, 0, 1);
132 bset
= isl_basic_set_universe(dim
);
134 c
= isl_equality_alloc(isl_dim_copy(bset
->dim
));
135 isl_int_set_si(v
, 1);
136 isl_constraint_set_constant(c
, v
);
137 isl_int_set_si(v
, -1);
138 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
139 div
= isl_div_alloc(isl_dim_copy(bset
->dim
));
140 c
= isl_constraint_add_div(c
, div
, &pos
);
141 isl_int_set_si(v
, 3);
142 isl_constraint_set_coefficient(c
, isl_dim_div
, pos
, v
);
143 bset
= isl_basic_set_add_constraint(bset
, c
);
145 c
= isl_equality_alloc(isl_dim_copy(bset
->dim
));
146 isl_int_set_si(v
, -1);
147 isl_constraint_set_constant(c
, v
);
148 isl_int_set_si(v
, 1);
149 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
150 div
= isl_div_alloc(isl_dim_copy(bset
->dim
));
151 c
= isl_constraint_add_div(c
, div
, &pos
);
152 isl_int_set_si(v
, 3);
153 isl_constraint_set_coefficient(c
, isl_dim_div
, pos
, v
);
154 bset
= isl_basic_set_add_constraint(bset
, c
);
156 assert(bset
->n_div
== 1);
157 isl_basic_set_free(bset
);
160 dim
= isl_dim_set_alloc(ctx
, 0, 1);
161 bset
= isl_basic_set_universe(dim
);
163 c
= isl_equality_alloc(isl_dim_copy(bset
->dim
));
164 isl_int_set_si(v
, 1);
165 isl_constraint_set_constant(c
, v
);
166 isl_int_set_si(v
, -1);
167 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
168 div
= isl_div_alloc(isl_dim_copy(bset
->dim
));
169 c
= isl_constraint_add_div(c
, div
, &pos
);
170 isl_int_set_si(v
, 3);
171 isl_constraint_set_coefficient(c
, isl_dim_div
, pos
, v
);
172 bset
= isl_basic_set_add_constraint(bset
, c
);
174 c
= isl_equality_alloc(isl_dim_copy(bset
->dim
));
175 isl_int_set_si(v
, -3);
176 isl_constraint_set_constant(c
, v
);
177 isl_int_set_si(v
, 1);
178 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
179 div
= isl_div_alloc(isl_dim_copy(bset
->dim
));
180 c
= isl_constraint_add_div(c
, div
, &pos
);
181 isl_int_set_si(v
, 4);
182 isl_constraint_set_coefficient(c
, isl_dim_div
, pos
, v
);
183 bset
= isl_basic_set_add_constraint(bset
, c
);
185 assert(bset
->n_div
== 1);
186 isl_basic_set_free(bset
);
189 dim
= isl_dim_set_alloc(ctx
, 0, 1);
190 bset
= isl_basic_set_universe(dim
);
192 c
= isl_equality_alloc(isl_dim_copy(bset
->dim
));
193 isl_int_set_si(v
, 2);
194 isl_constraint_set_constant(c
, v
);
195 isl_int_set_si(v
, -1);
196 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
197 div
= isl_div_alloc(isl_dim_copy(bset
->dim
));
198 c
= isl_constraint_add_div(c
, div
, &pos
);
199 isl_int_set_si(v
, 3);
200 isl_constraint_set_coefficient(c
, isl_dim_div
, pos
, v
);
201 bset
= isl_basic_set_add_constraint(bset
, c
);
203 c
= isl_equality_alloc(isl_dim_copy(bset
->dim
));
204 isl_int_set_si(v
, -1);
205 isl_constraint_set_constant(c
, v
);
206 isl_int_set_si(v
, 1);
207 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
208 div
= isl_div_alloc(isl_dim_copy(bset
->dim
));
209 c
= isl_constraint_add_div(c
, div
, &pos
);
210 isl_int_set_si(v
, 6);
211 isl_constraint_set_coefficient(c
, isl_dim_div
, pos
, v
);
212 bset
= isl_basic_set_add_constraint(bset
, c
);
214 assert(isl_basic_set_is_empty(bset
));
215 isl_basic_set_free(bset
);
218 dim
= isl_dim_set_alloc(ctx
, 0, 2);
219 bset
= isl_basic_set_universe(dim
);
221 c
= isl_equality_alloc(isl_dim_copy(bset
->dim
));
222 isl_int_set_si(v
, -1);
223 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
224 div
= isl_div_alloc(isl_dim_copy(bset
->dim
));
225 c
= isl_constraint_add_div(c
, div
, &pos
);
226 isl_int_set_si(v
, 3);
227 isl_constraint_set_coefficient(c
, isl_dim_div
, pos
, v
);
228 bset
= isl_basic_set_add_constraint(bset
, c
);
230 c
= isl_equality_alloc(isl_dim_copy(bset
->dim
));
231 isl_int_set_si(v
, 1);
232 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
233 isl_int_set_si(v
, -3);
234 isl_constraint_set_coefficient(c
, isl_dim_set
, 1, v
);
235 bset
= isl_basic_set_add_constraint(bset
, c
);
237 assert(bset
->n_div
== 0);
238 isl_basic_set_free(bset
);
241 dim
= isl_dim_set_alloc(ctx
, 0, 2);
242 bset
= isl_basic_set_universe(dim
);
244 c
= isl_equality_alloc(isl_dim_copy(bset
->dim
));
245 isl_int_set_si(v
, -1);
246 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
247 div
= isl_div_alloc(isl_dim_copy(bset
->dim
));
248 c
= isl_constraint_add_div(c
, div
, &pos
);
249 isl_int_set_si(v
, 6);
250 isl_constraint_set_coefficient(c
, isl_dim_div
, pos
, v
);
251 bset
= isl_basic_set_add_constraint(bset
, c
);
253 c
= isl_equality_alloc(isl_dim_copy(bset
->dim
));
254 isl_int_set_si(v
, 1);
255 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
256 isl_int_set_si(v
, -3);
257 isl_constraint_set_coefficient(c
, isl_dim_set
, 1, v
);
258 bset
= isl_basic_set_add_constraint(bset
, c
);
260 assert(bset
->n_div
== 1);
261 isl_basic_set_free(bset
);
264 /* This test is a bit tricky. We set up an equality
266 * Normalization of divs creates _two_ divs
269 * Afterwards e0 is removed again because it has coefficient -1
270 * and we end up with the original equality and div again.
271 * Perhaps we can avoid the introduction of this temporary div.
273 dim
= isl_dim_set_alloc(ctx
, 0, 3);
274 bset
= isl_basic_set_universe(dim
);
276 c
= isl_equality_alloc(isl_dim_copy(bset
->dim
));
277 isl_int_set_si(v
, -1);
278 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
279 isl_int_set_si(v
, -3);
280 isl_constraint_set_coefficient(c
, isl_dim_set
, 1, v
);
281 isl_int_set_si(v
, -3);
282 isl_constraint_set_coefficient(c
, isl_dim_set
, 2, v
);
283 div
= isl_div_alloc(isl_dim_copy(bset
->dim
));
284 c
= isl_constraint_add_div(c
, div
, &pos
);
285 isl_int_set_si(v
, 6);
286 isl_constraint_set_coefficient(c
, isl_dim_div
, pos
, v
);
287 bset
= isl_basic_set_add_constraint(bset
, c
);
289 assert(bset
->n_div
== 1);
290 isl_basic_set_free(bset
);
293 dim
= isl_dim_set_alloc(ctx
, 0, 4);
294 bset
= isl_basic_set_universe(dim
);
296 c
= isl_equality_alloc(isl_dim_copy(bset
->dim
));
297 isl_int_set_si(v
, -1);
298 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
299 isl_int_set_si(v
, -3);
300 isl_constraint_set_coefficient(c
, isl_dim_set
, 1, v
);
301 isl_int_set_si(v
, -3);
302 isl_constraint_set_coefficient(c
, isl_dim_set
, 3, v
);
303 div
= isl_div_alloc(isl_dim_copy(bset
->dim
));
304 c
= isl_constraint_add_div(c
, div
, &pos
);
305 isl_int_set_si(v
, 6);
306 isl_constraint_set_coefficient(c
, isl_dim_div
, pos
, v
);
307 bset
= isl_basic_set_add_constraint(bset
, c
);
309 c
= isl_equality_alloc(isl_dim_copy(bset
->dim
));
310 isl_int_set_si(v
, -1);
311 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
312 isl_int_set_si(v
, 1);
313 isl_constraint_set_coefficient(c
, isl_dim_set
, 2, v
);
314 isl_int_set_si(v
, 1);
315 isl_constraint_set_constant(c
, v
);
316 bset
= isl_basic_set_add_constraint(bset
, c
);
318 assert(bset
->n_div
== 1);
319 isl_basic_set_free(bset
);
322 dim
= isl_dim_set_alloc(ctx
, 0, 2);
323 bset
= isl_basic_set_universe(dim
);
325 c
= isl_equality_alloc(isl_dim_copy(bset
->dim
));
326 isl_int_set_si(v
, 1);
327 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
328 isl_int_set_si(v
, -1);
329 isl_constraint_set_coefficient(c
, isl_dim_set
, 1, v
);
330 div
= isl_div_alloc(isl_dim_copy(bset
->dim
));
331 c
= isl_constraint_add_div(c
, div
, &pos
);
332 isl_int_set_si(v
, -2);
333 isl_constraint_set_coefficient(c
, isl_dim_div
, pos
, v
);
334 bset
= isl_basic_set_add_constraint(bset
, c
);
336 c
= isl_equality_alloc(isl_dim_copy(bset
->dim
));
337 isl_int_set_si(v
, -1);
338 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
339 div
= isl_div_alloc(isl_dim_copy(bset
->dim
));
340 c
= isl_constraint_add_div(c
, div
, &pos
);
341 isl_int_set_si(v
, 3);
342 isl_constraint_set_coefficient(c
, isl_dim_div
, pos
, v
);
343 isl_int_set_si(v
, 2);
344 isl_constraint_set_constant(c
, v
);
345 bset
= isl_basic_set_add_constraint(bset
, c
);
347 bset
= isl_basic_set_fix_si(bset
, isl_dim_set
, 0, 2);
349 assert(!isl_basic_set_is_empty(bset
));
351 isl_basic_set_free(bset
);
354 dim
= isl_dim_set_alloc(ctx
, 0, 2);
355 bset
= isl_basic_set_universe(dim
);
357 c
= isl_equality_alloc(isl_dim_copy(bset
->dim
));
358 isl_int_set_si(v
, 1);
359 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, v
);
360 div
= isl_div_alloc(isl_dim_copy(bset
->dim
));
361 c
= isl_constraint_add_div(c
, div
, &pos
);
362 isl_int_set_si(v
, -2);
363 isl_constraint_set_coefficient(c
, isl_dim_div
, pos
, v
);
364 bset
= isl_basic_set_add_constraint(bset
, c
);
366 bset
= isl_basic_set_fix_si(bset
, isl_dim_set
, 0, 2);
368 isl_basic_set_free(bset
);
373 void test_application_case(struct isl_ctx
*ctx
, const char *name
)
375 char filename
[PATH_MAX
];
378 struct isl_basic_set
*bset1
, *bset2
;
379 struct isl_basic_map
*bmap
;
381 n
= snprintf(filename
, sizeof(filename
),
382 "%s/test_inputs/%s.omega", srcdir
, name
);
383 assert(n
< sizeof(filename
));
384 input
= fopen(filename
, "r");
387 bset1
= isl_basic_set_read_from_file(ctx
, input
, 0);
388 bmap
= isl_basic_map_read_from_file(ctx
, input
, 0);
390 bset1
= isl_basic_set_apply(bset1
, bmap
);
392 bset2
= isl_basic_set_read_from_file(ctx
, input
, 0);
394 assert(isl_basic_set_is_equal(bset1
, bset2
) == 1);
396 isl_basic_set_free(bset1
);
397 isl_basic_set_free(bset2
);
402 void test_application(struct isl_ctx
*ctx
)
404 test_application_case(ctx
, "application");
405 test_application_case(ctx
, "application2");
408 void test_affine_hull_case(struct isl_ctx
*ctx
, const char *name
)
410 char filename
[PATH_MAX
];
413 struct isl_basic_set
*bset1
, *bset2
;
415 n
= snprintf(filename
, sizeof(filename
),
416 "%s/test_inputs/%s.polylib", srcdir
, name
);
417 assert(n
< sizeof(filename
));
418 input
= fopen(filename
, "r");
421 bset1
= isl_basic_set_read_from_file(ctx
, input
, 0);
422 bset2
= isl_basic_set_read_from_file(ctx
, input
, 0);
424 bset1
= isl_basic_set_affine_hull(bset1
);
426 assert(isl_basic_set_is_equal(bset1
, bset2
) == 1);
428 isl_basic_set_free(bset1
);
429 isl_basic_set_free(bset2
);
434 void test_affine_hull(struct isl_ctx
*ctx
)
436 test_affine_hull_case(ctx
, "affine2");
437 test_affine_hull_case(ctx
, "affine");
438 test_affine_hull_case(ctx
, "affine3");
441 void test_convex_hull_case(struct isl_ctx
*ctx
, const char *name
)
443 char filename
[PATH_MAX
];
446 struct isl_basic_set
*bset1
, *bset2
;
449 n
= snprintf(filename
, sizeof(filename
),
450 "%s/test_inputs/%s.polylib", srcdir
, name
);
451 assert(n
< sizeof(filename
));
452 input
= fopen(filename
, "r");
455 bset1
= isl_basic_set_read_from_file(ctx
, input
, 0);
456 bset2
= isl_basic_set_read_from_file(ctx
, input
, 0);
458 set
= isl_basic_set_union(bset1
, bset2
);
459 bset1
= isl_set_convex_hull(set
);
461 bset2
= isl_basic_set_read_from_file(ctx
, input
, 0);
463 assert(isl_basic_set_is_equal(bset1
, bset2
) == 1);
465 isl_basic_set_free(bset1
);
466 isl_basic_set_free(bset2
);
471 void test_convex_hull(struct isl_ctx
*ctx
)
473 test_convex_hull_case(ctx
, "convex0");
474 test_convex_hull_case(ctx
, "convex1");
475 test_convex_hull_case(ctx
, "convex2");
476 test_convex_hull_case(ctx
, "convex3");
477 test_convex_hull_case(ctx
, "convex4");
478 test_convex_hull_case(ctx
, "convex5");
479 test_convex_hull_case(ctx
, "convex6");
480 test_convex_hull_case(ctx
, "convex7");
481 test_convex_hull_case(ctx
, "convex8");
482 test_convex_hull_case(ctx
, "convex9");
483 test_convex_hull_case(ctx
, "convex10");
484 test_convex_hull_case(ctx
, "convex11");
485 test_convex_hull_case(ctx
, "convex12");
486 test_convex_hull_case(ctx
, "convex13");
487 test_convex_hull_case(ctx
, "convex14");
490 void test_gist_case(struct isl_ctx
*ctx
, const char *name
)
492 char filename
[PATH_MAX
];
495 struct isl_basic_set
*bset1
, *bset2
;
497 n
= snprintf(filename
, sizeof(filename
),
498 "%s/test_inputs/%s.polylib", srcdir
, name
);
499 assert(n
< sizeof(filename
));
500 input
= fopen(filename
, "r");
503 bset1
= isl_basic_set_read_from_file(ctx
, input
, 0);
504 bset2
= isl_basic_set_read_from_file(ctx
, input
, 0);
506 bset1
= isl_basic_set_gist(bset1
, bset2
);
508 bset2
= isl_basic_set_read_from_file(ctx
, input
, 0);
510 assert(isl_basic_set_is_equal(bset1
, bset2
) == 1);
512 isl_basic_set_free(bset1
);
513 isl_basic_set_free(bset2
);
518 void test_gist(struct isl_ctx
*ctx
)
520 test_gist_case(ctx
, "gist1");
523 void test_coalesce(struct isl_ctx
*ctx
)
527 set
= isl_set_read_from_str(ctx
,
528 "{[x,y]: x >= 0 & x <= 10 & y >= 0 & y <= 10 or "
529 "y >= x & x >= 2 & 5 >= y }", -1);
530 set
= isl_set_coalesce(set
);
531 assert(set
&& set
->n
== 1);
534 set
= isl_set_read_from_str(ctx
,
535 "{[x,y]: y >= 0 & 2x + y <= 30 & y <= 10 & x >= 0 or "
536 "x + y >= 10 & y <= x & x + y <= 20 & y >= 0}", -1);
537 set
= isl_set_coalesce(set
);
538 assert(set
&& set
->n
== 1);
541 set
= isl_set_read_from_str(ctx
,
542 "{[x,y]: y >= 0 & 2x + y <= 30 & y <= 10 & x >= 0 or "
543 "x + y >= 10 & y <= x & x + y <= 19 & y >= 0}", -1);
544 set
= isl_set_coalesce(set
);
545 assert(set
&& set
->n
== 2);
548 set
= isl_set_read_from_str(ctx
,
549 "{[x,y]: y >= 0 & x <= 5 & y <= x or "
550 "y >= 0 & x >= 6 & x <= 10 & y <= x}", -1);
551 set
= isl_set_coalesce(set
);
552 assert(set
&& set
->n
== 1);
555 set
= isl_set_read_from_str(ctx
,
556 "{[x,y]: y >= 0 & x <= 5 & y <= x or "
557 "y >= 0 & x >= 7 & x <= 10 & y <= x}", -1);
558 set
= isl_set_coalesce(set
);
559 assert(set
&& set
->n
== 2);
562 set
= isl_set_read_from_str(ctx
,
563 "{[x,y]: y >= 0 & x <= 5 & y <= x or "
564 "y >= 0 & x >= 6 & x <= 10 & y + 1 <= x}", -1);
565 set
= isl_set_coalesce(set
);
566 assert(set
&& set
->n
== 2);
569 set
= isl_set_read_from_str(ctx
,
570 "{[x,y]: y >= 0 & x <= 5 & y <= x or "
571 "y >= 0 & x = 6 & y <= 6}", -1);
572 set
= isl_set_coalesce(set
);
573 assert(set
&& set
->n
== 1);
576 set
= isl_set_read_from_str(ctx
,
577 "{[x,y]: y >= 0 & x <= 5 & y <= x or "
578 "y >= 0 & x = 7 & y <= 6}", -1);
579 set
= isl_set_coalesce(set
);
580 assert(set
&& set
->n
== 2);
583 set
= isl_set_read_from_str(ctx
,
584 "{[x,y]: y >= 0 & x <= 5 & y <= x or "
585 "y >= 0 & x = 6 & y <= 5}", -1);
586 set
= isl_set_coalesce(set
);
587 assert(set
&& set
->n
== 2);
590 set
= isl_set_read_from_str(ctx
,
591 "{[x,y]: y >= 0 & x <= 5 & y <= x or "
592 "y >= 0 & x = 6 & y <= 7}", -1);
593 set
= isl_set_coalesce(set
);
594 assert(set
&& set
->n
== 2);
602 srcdir
= getenv("srcdir");
605 ctx
= isl_ctx_alloc();
607 test_construction(ctx
);
610 test_application(ctx
);
611 test_affine_hull(ctx
);
612 test_convex_hull(ctx
);