?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_range.c: has_sign: drop unused variable
[isl.git] / isl_test.c
blobea8311da159e7dab65ecb534d3a7671dce4f2fd5
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
4 * Copyright 2012-2013 Ecole Normale Superieure
5 * Copyright 2014 INRIA Rocquencourt
6 *
7 * Use of this software is governed by the MIT license
8 *
9 * Written by Sven Verdoolaege, K.U.Leuven, Departement
10 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
11 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
12 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
13 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
14 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
15 * B.P. 105 - 78153 Le Chesnay, France
16 */
17
18 #include <assert.h>
19 #include <stdio.h>
20 #include <limits.h>
21 #include <isl_ctx_private.h>
22 #include <isl_map_private.h>
23 #include <isl_aff_private.h>
24 #include <isl/set.h>
25 #include <isl/flow.h>
26 #include <isl_constraint_private.h>
27 #include <isl/polynomial.h>
28 #include <isl/union_map.h>
29 #include <isl_factorization.h>
30 #include <isl/schedule.h>
31 #include <isl/schedule_node.h>
32 #include <isl_options_private.h>
33 #include <isl/vertices.h>
34 #include <isl/ast_build.h>
35 #include <isl/val.h>
36 #include <isl/ilp.h>
37 #include <isl_ast_build_expr.h>
38 #include <isl/options.h>
39
40 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
41
42 static char *srcdir;
43
44 static char *get_filename(isl_ctx *ctx, const char *name, const char *suffix) {
45 char *filename;
46 int length;
47 char *pattern = "%s/test_inputs/%s.%s";
48
49 length = strlen(pattern) - 6 + strlen(srcdir) + strlen(name)
50 + strlen(suffix) + 1;
51 filename = isl_alloc_array(ctx, char, length);
52
53 if (!filename)
54 return NULL;
55
56 sprintf(filename, pattern, srcdir, name, suffix);
57
58 return filename;
59 }
60
61 void test_parse_map(isl_ctx *ctx, const char *str)
62 {
63 isl_map *map;
64
65 map = isl_map_read_from_str(ctx, str);
66 assert(map);
67 isl_map_free(map);
68 }
69
70 int test_parse_map_equal(isl_ctx *ctx, const char *str, const char *str2)
71 {
72 isl_map *map, *map2;
73 int equal;
74
75 map = isl_map_read_from_str(ctx, str);
76 map2 = isl_map_read_from_str(ctx, str2);
77 equal = isl_map_is_equal(map, map2);
78 isl_map_free(map);
79 isl_map_free(map2);
80
81 if (equal < 0)
82 return -1;
83 if (!equal)
84 isl_die(ctx, isl_error_unknown, "maps not equal",
85 return -1);
86
87 return 0;
88 }
89
90 void test_parse_pwqp(isl_ctx *ctx, const char *str)
91 {
92 isl_pw_qpolynomial *pwqp;
93
94 pwqp = isl_pw_qpolynomial_read_from_str(ctx, str);
95 assert(pwqp);
96 isl_pw_qpolynomial_free(pwqp);
97 }
98
99 static void test_parse_pwaff(isl_ctx *ctx, const char *str)
100 {
101 isl_pw_aff *pwaff;
102
103 pwaff = isl_pw_aff_read_from_str(ctx, str);
104 assert(pwaff);
105 isl_pw_aff_free(pwaff);
106 }
107
108 /* Check that we can read an isl_multi_val from "str" without errors.
109 */
110 static int test_parse_multi_val(isl_ctx *ctx, const char *str)
111 {
112 isl_multi_val *mv;
113
114 mv = isl_multi_val_read_from_str(ctx, str);
115 isl_multi_val_free(mv);
116
117 return mv ? 0 : -1;
118 }
119
120 int test_parse(struct isl_ctx *ctx)
121 {
122 isl_map *map, *map2;
123 const char *str, *str2;
124
125 if (test_parse_multi_val(ctx, "{ A[B[2] -> C[5, 7]] }") < 0)
126 return -1;
127 if (test_parse_multi_val(ctx, "[n] -> { [2] }") < 0)
128 return -1;
129 if (test_parse_multi_val(ctx, "{ A[4, infty, NaN, -1/2, 2/3] }") < 0)
130 return -1;
131
132 str = "{ [i] -> [-i] }";
133 map = isl_map_read_from_str(ctx, str);
134 assert(map);
135 isl_map_free(map);
136
137 str = "{ A[i] -> L[([i/3])] }";
138 map = isl_map_read_from_str(ctx, str);
139 assert(map);
140 isl_map_free(map);
141
142 test_parse_map(ctx, "{[[s] -> A[i]] -> [[s+1] -> A[i]]}");
143 test_parse_map(ctx, "{ [p1, y1, y2] -> [2, y1, y2] : "
144 "p1 = 1 && (y1 <= y2 || y2 = 0) }");
145
146 str = "{ [x,y] : [([x/2]+y)/3] >= 1 }";
147 str2 = "{ [x, y] : 2y >= 6 - x }";
148 if (test_parse_map_equal(ctx, str, str2) < 0)
149 return -1;
150
151 if (test_parse_map_equal(ctx, "{ [x,y] : x <= min(y, 2*y+3) }",
152 "{ [x,y] : x <= y, 2*y + 3 }") < 0)
153 return -1;
154 str = "{ [x, y] : (y <= x and y >= -3) or (2y <= -3 + x and y <= -4) }";
155 if (test_parse_map_equal(ctx, "{ [x,y] : x >= min(y, 2*y+3) }",
156 str) < 0)
157 return -1;
158
159 str = "{[new,old] -> [new+1-2*[(new+1)/2],old+1-2*[(old+1)/2]]}";
160 map = isl_map_read_from_str(ctx, str);
161 str = "{ [new, old] -> [o0, o1] : "
162 "exists (e0 = [(-1 - new + o0)/2], e1 = [(-1 - old + o1)/2]: "
163 "2e0 = -1 - new + o0 and 2e1 = -1 - old + o1 and o0 >= 0 and "
164 "o0 <= 1 and o1 >= 0 and o1 <= 1) }";
165 map2 = isl_map_read_from_str(ctx, str);
166 assert(isl_map_is_equal(map, map2));
167 isl_map_free(map);
168 isl_map_free(map2);
169
170 str = "{[new,old] -> [new+1-2*[(new+1)/2],old+1-2*[(old+1)/2]]}";
171 map = isl_map_read_from_str(ctx, str);
172 str = "{[new,old] -> [(new+1)%2,(old+1)%2]}";
173 map2 = isl_map_read_from_str(ctx, str);
174 assert(isl_map_is_equal(map, map2));
175 isl_map_free(map);
176 isl_map_free(map2);
177
178 str = "[n] -> { [c1] : c1>=0 and c1<=floord(n-4,3) }";
179 str2 = "[n] -> { [c1] : c1 >= 0 and 3c1 <= -4 + n }";
180 if (test_parse_map_equal(ctx, str, str2) < 0)
181 return -1;
182
183 str = "{ [i,j] -> [i] : i < j; [i,j] -> [j] : j <= i }";
184 str2 = "{ [i,j] -> [min(i,j)] }";
185 if (test_parse_map_equal(ctx, str, str2) < 0)
186 return -1;
187
188 str = "{ [i,j] : i != j }";
189 str2 = "{ [i,j] : i < j or i > j }";
190 if (test_parse_map_equal(ctx, str, str2) < 0)
191 return -1;
192
193 str = "{ [i,j] : (i+1)*2 >= j }";
194 str2 = "{ [i, j] : j <= 2 + 2i }";
195 if (test_parse_map_equal(ctx, str, str2) < 0)
196 return -1;
197
198 str = "{ [i] -> [i > 0 ? 4 : 5] }";
199 str2 = "{ [i] -> [5] : i <= 0; [i] -> [4] : i >= 1 }";
200 if (test_parse_map_equal(ctx, str, str2) < 0)
201 return -1;
202
203 str = "[N=2,M] -> { [i=[(M+N)/4]] }";
204 str2 = "[N, M] -> { [i] : N = 2 and 4i <= 2 + M and 4i >= -1 + M }";
205 if (test_parse_map_equal(ctx, str, str2) < 0)
206 return -1;
207
208 str = "{ [x] : x >= 0 }";
209 str2 = "{ [x] : x-0 >= 0 }";
210 if (test_parse_map_equal(ctx, str, str2) < 0)
211 return -1;
212
213 str = "{ [i] : ((i > 10)) }";
214 str2 = "{ [i] : i >= 11 }";
215 if (test_parse_map_equal(ctx, str, str2) < 0)
216 return -1;
217
218 str = "{ [i] -> [0] }";
219 str2 = "{ [i] -> [0 * i] }";
220 if (test_parse_map_equal(ctx, str, str2) < 0)
221 return -1;
222
223 test_parse_pwqp(ctx, "{ [i] -> i + [ (i + [i/3])/2 ] }");
224 test_parse_map(ctx, "{ S1[i] -> [([i/10]),i%10] : 0 <= i <= 45 }");
225 test_parse_pwaff(ctx, "{ [i] -> [i + 1] : i > 0; [a] -> [a] : a < 0 }");
226 test_parse_pwqp(ctx, "{ [x] -> ([(x)/2] * [(x)/3]) }");
227
228 if (test_parse_map_equal(ctx, "{ [a] -> [b] : (not false) }",
229 "{ [a] -> [b] : true }") < 0)
230 return -1;
231
232 if (test_parse_map_equal(ctx, "{ [i] : i/2 <= 5 }",
233 "{ [i] : i <= 10 }") < 0)
234 return -1;
235
236 if (test_parse_map_equal(ctx, "{Sym=[n] [i] : i <= n }",
237 "[n] -> { [i] : i <= n }") < 0)
238 return -1;
239
240 if (test_parse_map_equal(ctx, "{ [*] }", "{ [a] }") < 0)
241 return -1;
242
243 if (test_parse_map_equal(ctx, "{ [i] : 2*floor(i/2) = i }",
244 "{ [i] : exists a : i = 2 a }") < 0)
245 return -1;
246
247 if (test_parse_map_equal(ctx, "{ [a] -> [b] : a = 5 implies b = 5 }",
248 "{ [a] -> [b] : a != 5 or b = 5 }") < 0)
249 return -1;
250
251 if (test_parse_map_equal(ctx, "{ [a] -> [a - 1 : a > 0] }",
252 "{ [a] -> [a - 1] : a > 0 }") < 0)
253 return -1;
254 if (test_parse_map_equal(ctx,
255 "{ [a] -> [a - 1 : a > 0; a : a <= 0] }",
256 "{ [a] -> [a - 1] : a > 0; [a] -> [a] : a <= 0 }") < 0)
257 return -1;
258 if (test_parse_map_equal(ctx,
259 "{ [a] -> [(a) * 2 : a >= 0; 0 : a < 0] }",
260 "{ [a] -> [2a] : a >= 0; [a] -> [0] : a < 0 }") < 0)
261 return -1;
262 if (test_parse_map_equal(ctx,
263 "{ [a] -> [(a * 2) : a >= 0; 0 : a < 0] }",
264 "{ [a] -> [2a] : a >= 0; [a] -> [0] : a < 0 }") < 0)
265 return -1;
266 if (test_parse_map_equal(ctx,
267 "{ [a] -> [(a * 2 : a >= 0); 0 : a < 0] }",
268 "{ [a] -> [2a] : a >= 0; [a] -> [0] : a < 0 }") < 0)
269 return -1;
270 if (test_parse_map_equal(ctx,
271 "{ [a] -> [(a * 2 : a >= 0; 0 : a < 0)] }",
272 "{ [a] -> [2a] : a >= 0; [a] -> [0] : a < 0 }") < 0)
273 return -1;
274
275 return 0;
276 }
277
278 void test_read(struct isl_ctx *ctx)
279 {
280 char *filename;
281 FILE *input;
282 struct isl_basic_set *bset1, *bset2;
283 const char *str = "{[y]: Exists ( alpha : 2alpha = y)}";
284
285 filename = get_filename(ctx, "set", "omega");
286 assert(filename);
287 input = fopen(filename, "r");
288 assert(input);
289
290 bset1 = isl_basic_set_read_from_file(ctx, input);
291 bset2 = isl_basic_set_read_from_str(ctx, str);
292
293 assert(isl_basic_set_is_equal(bset1, bset2) == 1);
294
295 isl_basic_set_free(bset1);
296 isl_basic_set_free(bset2);
297 free(filename);
298
299 fclose(input);
300 }
301
302 void test_bounded(struct isl_ctx *ctx)
303 {
304 isl_set *set;
305 int bounded;
306
307 set = isl_set_read_from_str(ctx, "[n] -> {[i] : 0 <= i <= n }");
308 bounded = isl_set_is_bounded(set);
309 assert(bounded);
310 isl_set_free(set);
311
312 set = isl_set_read_from_str(ctx, "{[n, i] : 0 <= i <= n }");
313 bounded = isl_set_is_bounded(set);
314 assert(!bounded);
315 isl_set_free(set);
316
317 set = isl_set_read_from_str(ctx, "[n] -> {[i] : i <= n }");
318 bounded = isl_set_is_bounded(set);
319 assert(!bounded);
320 isl_set_free(set);
321 }
322
323 /* Construct the basic set { [i] : 5 <= i <= N } */
324 void test_construction(struct isl_ctx *ctx)
325 {
326 isl_int v;
327 isl_space *dim;
328 isl_local_space *ls;
329 struct isl_basic_set *bset;
330 struct isl_constraint *c;
331
332 isl_int_init(v);
333
334 dim = isl_space_set_alloc(ctx, 1, 1);
335 bset = isl_basic_set_universe(isl_space_copy(dim));
336 ls = isl_local_space_from_space(dim);
337
338 c = isl_inequality_alloc(isl_local_space_copy(ls));
339 isl_int_set_si(v, -1);
340 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
341 isl_int_set_si(v, 1);
342 isl_constraint_set_coefficient(c, isl_dim_param, 0, v);
343 bset = isl_basic_set_add_constraint(bset, c);
344
345 c = isl_inequality_alloc(isl_local_space_copy(ls));
346 isl_int_set_si(v, 1);
347 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
348 isl_int_set_si(v, -5);
349 isl_constraint_set_constant(c, v);
350 bset = isl_basic_set_add_constraint(bset, c);
351
352 isl_local_space_free(ls);
353 isl_basic_set_free(bset);
354
355 isl_int_clear(v);
356 }
357
358 void test_dim(struct isl_ctx *ctx)
359 {
360 const char *str;
361 isl_map *map1, *map2;
362
363 map1 = isl_map_read_from_str(ctx,
364 "[n] -> { [i] -> [j] : exists (a = [i/10] : i - 10a <= n ) }");
365 map1 = isl_map_add_dims(map1, isl_dim_in, 1);
366 map2 = isl_map_read_from_str(ctx,
367 "[n] -> { [i,k] -> [j] : exists (a = [i/10] : i - 10a <= n ) }");
368 assert(isl_map_is_equal(map1, map2));
369 isl_map_free(map2);
370
371 map1 = isl_map_project_out(map1, isl_dim_in, 0, 1);
372 map2 = isl_map_read_from_str(ctx, "[n] -> { [i] -> [j] : n >= 0 }");
373 assert(isl_map_is_equal(map1, map2));
374
375 isl_map_free(map1);
376 isl_map_free(map2);
377
378 str = "[n] -> { [i] -> [] : exists a : 0 <= i <= n and i = 2 a }";
379 map1 = isl_map_read_from_str(ctx, str);
380 str = "{ [i] -> [j] : exists a : 0 <= i <= j and i = 2 a }";
381 map2 = isl_map_read_from_str(ctx, str);
382 map1 = isl_map_move_dims(map1, isl_dim_out, 0, isl_dim_param, 0, 1);
383 assert(isl_map_is_equal(map1, map2));
384
385 isl_map_free(map1);
386 isl_map_free(map2);
387 }
388
389 struct {
390 __isl_give isl_val *(*op)(__isl_take isl_val *v);
391 const char *arg;
392 const char *res;
393 } val_un_tests[] = {
394 { &isl_val_neg, "0", "0" },
395 { &isl_val_abs, "0", "0" },
396 { &isl_val_2exp, "0", "1" },
397 { &isl_val_floor, "0", "0" },
398 { &isl_val_ceil, "0", "0" },
399 { &isl_val_neg, "1", "-1" },
400 { &isl_val_neg, "-1", "1" },
401 { &isl_val_neg, "1/2", "-1/2" },
402 { &isl_val_neg, "-1/2", "1/2" },
403 { &isl_val_neg, "infty", "-infty" },
404 { &isl_val_neg, "-infty", "infty" },
405 { &isl_val_neg, "NaN", "NaN" },
406 { &isl_val_abs, "1", "1" },
407 { &isl_val_abs, "-1", "1" },
408 { &isl_val_abs, "1/2", "1/2" },
409 { &isl_val_abs, "-1/2", "1/2" },
410 { &isl_val_abs, "infty", "infty" },
411 { &isl_val_abs, "-infty", "infty" },
412 { &isl_val_abs, "NaN", "NaN" },
413 { &isl_val_floor, "1", "1" },
414 { &isl_val_floor, "-1", "-1" },
415 { &isl_val_floor, "1/2", "0" },
416 { &isl_val_floor, "-1/2", "-1" },
417 { &isl_val_floor, "infty", "infty" },
418 { &isl_val_floor, "-infty", "-infty" },
419 { &isl_val_floor, "NaN", "NaN" },
420 { &isl_val_ceil, "1", "1" },
421 { &isl_val_ceil, "-1", "-1" },
422 { &isl_val_ceil, "1/2", "1" },
423 { &isl_val_ceil, "-1/2", "0" },
424 { &isl_val_ceil, "infty", "infty" },
425 { &isl_val_ceil, "-infty", "-infty" },
426 { &isl_val_ceil, "NaN", "NaN" },
427 { &isl_val_2exp, "-3", "1/8" },
428 { &isl_val_2exp, "-1", "1/2" },
429 { &isl_val_2exp, "1", "2" },
430 { &isl_val_2exp, "2", "4" },
431 { &isl_val_2exp, "3", "8" },
432 { &isl_val_inv, "1", "1" },
433 { &isl_val_inv, "2", "1/2" },
434 { &isl_val_inv, "1/2", "2" },
435 { &isl_val_inv, "-2", "-1/2" },
436 { &isl_val_inv, "-1/2", "-2" },
437 { &isl_val_inv, "0", "NaN" },
438 { &isl_val_inv, "NaN", "NaN" },
439 { &isl_val_inv, "infty", "0" },
440 { &isl_val_inv, "-infty", "0" },
441 };
442
443 /* Perform some basic tests of unary operations on isl_val objects.
444 */
445 static int test_un_val(isl_ctx *ctx)
446 {
447 int i;
448 isl_val *v, *res;
449 __isl_give isl_val *(*fn)(__isl_take isl_val *v);
450 int ok;
451
452 for (i = 0; i < ARRAY_SIZE(val_un_tests); ++i) {
453 v = isl_val_read_from_str(ctx, val_un_tests[i].arg);
454 res = isl_val_read_from_str(ctx, val_un_tests[i].res);
455 fn = val_un_tests[i].op;
456 v = fn(v);
457 if (isl_val_is_nan(res))
458 ok = isl_val_is_nan(v);
459 else
460 ok = isl_val_eq(v, res);
461 isl_val_free(v);
462 isl_val_free(res);
463 if (ok < 0)
464 return -1;
465 if (!ok)
466 isl_die(ctx, isl_error_unknown,
467 "unexpected result", return -1);
468 }
469
470 return 0;
471 }
472
473 struct {
474 __isl_give isl_val *(*fn)(__isl_take isl_val *v1,
475 __isl_take isl_val *v2);
476 } val_bin_op[] = {
477 ['+'] = { &isl_val_add },
478 ['-'] = { &isl_val_sub },
479 ['*'] = { &isl_val_mul },
480 ['/'] = { &isl_val_div },
481 ['g'] = { &isl_val_gcd },
482 ['m'] = { &isl_val_min },
483 ['M'] = { &isl_val_max },
484 };
485
486 struct {
487 const char *arg1;
488 unsigned char op;
489 const char *arg2;
490 const char *res;
491 } val_bin_tests[] = {
492 { "0", '+', "0", "0" },
493 { "1", '+', "0", "1" },
494 { "1", '+', "1", "2" },
495 { "1", '-', "1", "0" },
496 { "1", '*', "1", "1" },
497 { "1", '/', "1", "1" },
498 { "2", '*', "3", "6" },
499 { "2", '*', "1/2", "1" },
500 { "2", '*', "1/3", "2/3" },
501 { "2/3", '*', "3/5", "2/5" },
502 { "2/3", '*', "7/5", "14/15" },
503 { "2", '/', "1/2", "4" },
504 { "-2", '/', "-1/2", "4" },
505 { "-2", '/', "1/2", "-4" },
506 { "2", '/', "-1/2", "-4" },
507 { "2", '/', "2", "1" },
508 { "2", '/', "3", "2/3" },
509 { "2/3", '/', "5/3", "2/5" },
510 { "2/3", '/', "5/7", "14/15" },
511 { "0", '/', "0", "NaN" },
512 { "42", '/', "0", "NaN" },
513 { "-42", '/', "0", "NaN" },
514 { "infty", '/', "0", "NaN" },
515 { "-infty", '/', "0", "NaN" },
516 { "NaN", '/', "0", "NaN" },
517 { "0", '/', "NaN", "NaN" },
518 { "42", '/', "NaN", "NaN" },
519 { "-42", '/', "NaN", "NaN" },
520 { "infty", '/', "NaN", "NaN" },
521 { "-infty", '/', "NaN", "NaN" },
522 { "NaN", '/', "NaN", "NaN" },
523 { "0", '/', "infty", "0" },
524 { "42", '/', "infty", "0" },
525 { "-42", '/', "infty", "0" },
526 { "infty", '/', "infty", "NaN" },
527 { "-infty", '/', "infty", "NaN" },
528 { "NaN", '/', "infty", "NaN" },
529 { "0", '/', "-infty", "0" },
530 { "42", '/', "-infty", "0" },
531 { "-42", '/', "-infty", "0" },
532 { "infty", '/', "-infty", "NaN" },
533 { "-infty", '/', "-infty", "NaN" },
534 { "NaN", '/', "-infty", "NaN" },
535 { "1", '-', "1/3", "2/3" },
536 { "1/3", '+', "1/2", "5/6" },
537 { "1/2", '+', "1/2", "1" },
538 { "3/4", '-', "1/4", "1/2" },
539 { "1/2", '-', "1/3", "1/6" },
540 { "infty", '+', "42", "infty" },
541 { "infty", '+', "infty", "infty" },
542 { "42", '+', "infty", "infty" },
543 { "infty", '-', "infty", "NaN" },
544 { "infty", '*', "infty", "infty" },
545 { "infty", '*', "-infty", "-infty" },
546 { "-infty", '*', "infty", "-infty" },
547 { "-infty", '*', "-infty", "infty" },
548 { "0", '*', "infty", "NaN" },
549 { "1", '*', "infty", "infty" },
550 { "infty", '*', "0", "NaN" },
551 { "infty", '*', "42", "infty" },
552 { "42", '-', "infty", "-infty" },
553 { "infty", '+', "-infty", "NaN" },
554 { "4", 'g', "6", "2" },
555 { "5", 'g', "6", "1" },
556 { "42", 'm', "3", "3" },
557 { "42", 'M', "3", "42" },
558 { "3", 'm', "42", "3" },
559 { "3", 'M', "42", "42" },
560 { "42", 'm', "infty", "42" },
561 { "42", 'M', "infty", "infty" },
562 { "42", 'm', "-infty", "-infty" },
563 { "42", 'M', "-infty", "42" },
564 { "42", 'm', "NaN", "NaN" },
565 { "42", 'M', "NaN", "NaN" },
566 { "infty", 'm', "-infty", "-infty" },
567 { "infty", 'M', "-infty", "infty" },
568 };
569
570 /* Perform some basic tests of binary operations on isl_val objects.
571 */
572 static int test_bin_val(isl_ctx *ctx)
573 {
574 int i;
575 isl_val *v1, *v2, *res;
576 __isl_give isl_val *(*fn)(__isl_take isl_val *v1,
577 __isl_take isl_val *v2);
578 int ok;
579
580 for (i = 0; i < ARRAY_SIZE(val_bin_tests); ++i) {
581 v1 = isl_val_read_from_str(ctx, val_bin_tests[i].arg1);
582 v2 = isl_val_read_from_str(ctx, val_bin_tests[i].arg2);
583 res = isl_val_read_from_str(ctx, val_bin_tests[i].res);
584 fn = val_bin_op[val_bin_tests[i].op].fn;
585 v1 = fn(v1, v2);
586 if (isl_val_is_nan(res))
587 ok = isl_val_is_nan(v1);
588 else
589 ok = isl_val_eq(v1, res);
590 isl_val_free(v1);
591 isl_val_free(res);
592 if (ok < 0)
593 return -1;
594 if (!ok)
595 isl_die(ctx, isl_error_unknown,
596 "unexpected result", return -1);
597 }
598
599 return 0;
600 }
601
602 /* Perform some basic tests on isl_val objects.
603 */
604 static int test_val(isl_ctx *ctx)
605 {
606 if (test_un_val(ctx) < 0)
607 return -1;
608 if (test_bin_val(ctx) < 0)
609 return -1;
610 return 0;
611 }
612
613 static int test_div(isl_ctx *ctx)
614 {
615 unsigned n;
616 const char *str;
617 int empty;
618 isl_int v;
619 isl_space *dim;
620 isl_set *set;
621 isl_local_space *ls;
622 struct isl_basic_set *bset;
623 struct isl_constraint *c;
624
625 isl_int_init(v);
626
627 /* test 1 */
628 dim = isl_space_set_alloc(ctx, 0, 3);
629 bset = isl_basic_set_universe(isl_space_copy(dim));
630 ls = isl_local_space_from_space(dim);
631
632 c = isl_equality_alloc(isl_local_space_copy(ls));
633 isl_int_set_si(v, -1);
634 isl_constraint_set_constant(c, v);
635 isl_int_set_si(v, 1);
636 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
637 isl_int_set_si(v, 3);
638 isl_constraint_set_coefficient(c, isl_dim_set, 1, v);
639 bset = isl_basic_set_add_constraint(bset, c);
640
641 c = isl_equality_alloc(isl_local_space_copy(ls));
642 isl_int_set_si(v, 1);
643 isl_constraint_set_constant(c, v);
644 isl_int_set_si(v, -1);
645 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
646 isl_int_set_si(v, 3);
647 isl_constraint_set_coefficient(c, isl_dim_set, 2, v);
648 bset = isl_basic_set_add_constraint(bset, c);
649
650 bset = isl_basic_set_project_out(bset, isl_dim_set, 1, 2);
651
652 assert(bset && bset->n_div == 1);
653 isl_local_space_free(ls);
654 isl_basic_set_free(bset);
655
656 /* test 2 */
657 dim = isl_space_set_alloc(ctx, 0, 3);
658 bset = isl_basic_set_universe(isl_space_copy(dim));
659 ls = isl_local_space_from_space(dim);
660
661 c = isl_equality_alloc(isl_local_space_copy(ls));
662 isl_int_set_si(v, 1);
663 isl_constraint_set_constant(c, v);
664 isl_int_set_si(v, -1);
665 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
666 isl_int_set_si(v, 3);
667 isl_constraint_set_coefficient(c, isl_dim_set, 1, v);
668 bset = isl_basic_set_add_constraint(bset, c);
669
670 c = isl_equality_alloc(isl_local_space_copy(ls));
671 isl_int_set_si(v, -1);
672 isl_constraint_set_constant(c, v);
673 isl_int_set_si(v, 1);
674 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
675 isl_int_set_si(v, 3);
676 isl_constraint_set_coefficient(c, isl_dim_set, 2, v);
677 bset = isl_basic_set_add_constraint(bset, c);
678
679 bset = isl_basic_set_project_out(bset, isl_dim_set, 1, 2);
680
681 assert(bset && bset->n_div == 1);
682 isl_local_space_free(ls);
683 isl_basic_set_free(bset);
684
685 /* test 3 */
686 dim = isl_space_set_alloc(ctx, 0, 3);
687 bset = isl_basic_set_universe(isl_space_copy(dim));
688 ls = isl_local_space_from_space(dim);
689
690 c = isl_equality_alloc(isl_local_space_copy(ls));
691 isl_int_set_si(v, 1);
692 isl_constraint_set_constant(c, v);
693 isl_int_set_si(v, -1);
694 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
695 isl_int_set_si(v, 3);
696 isl_constraint_set_coefficient(c, isl_dim_set, 1, v);
697 bset = isl_basic_set_add_constraint(bset, c);
698
699 c = isl_equality_alloc(isl_local_space_copy(ls));
700 isl_int_set_si(v, -3);
701 isl_constraint_set_constant(c, v);
702 isl_int_set_si(v, 1);
703 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
704 isl_int_set_si(v, 4);
705 isl_constraint_set_coefficient(c, isl_dim_set, 2, v);
706 bset = isl_basic_set_add_constraint(bset, c);
707
708 bset = isl_basic_set_project_out(bset, isl_dim_set, 1, 2);
709
710 assert(bset && bset->n_div == 1);
711 isl_local_space_free(ls);
712 isl_basic_set_free(bset);
713
714 /* test 4 */
715 dim = isl_space_set_alloc(ctx, 0, 3);
716 bset = isl_basic_set_universe(isl_space_copy(dim));
717 ls = isl_local_space_from_space(dim);
718
719 c = isl_equality_alloc(isl_local_space_copy(ls));
720 isl_int_set_si(v, 2);
721 isl_constraint_set_constant(c, v);
722 isl_int_set_si(v, -1);
723 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
724 isl_int_set_si(v, 3);
725 isl_constraint_set_coefficient(c, isl_dim_set, 1, v);
726 bset = isl_basic_set_add_constraint(bset, c);
727
728 c = isl_equality_alloc(isl_local_space_copy(ls));
729 isl_int_set_si(v, -1);
730 isl_constraint_set_constant(c, v);
731 isl_int_set_si(v, 1);
732 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
733 isl_int_set_si(v, 6);
734 isl_constraint_set_coefficient(c, isl_dim_set, 2, v);
735 bset = isl_basic_set_add_constraint(bset, c);
736
737 bset = isl_basic_set_project_out(bset, isl_dim_set, 1, 2);
738
739 assert(isl_basic_set_is_empty(bset));
740 isl_local_space_free(ls);
741 isl_basic_set_free(bset);
742
743 /* test 5 */
744 dim = isl_space_set_alloc(ctx, 0, 3);
745 bset = isl_basic_set_universe(isl_space_copy(dim));
746 ls = isl_local_space_from_space(dim);
747
748 c = isl_equality_alloc(isl_local_space_copy(ls));
749 isl_int_set_si(v, -1);
750 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
751 isl_int_set_si(v, 3);
752 isl_constraint_set_coefficient(c, isl_dim_set, 2, v);
753 bset = isl_basic_set_add_constraint(bset, c);
754
755 c = isl_equality_alloc(isl_local_space_copy(ls));
756 isl_int_set_si(v, 1);
757 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
758 isl_int_set_si(v, -3);
759 isl_constraint_set_coefficient(c, isl_dim_set, 1, v);
760 bset = isl_basic_set_add_constraint(bset, c);
761
762 bset = isl_basic_set_project_out(bset, isl_dim_set, 2, 1);
763
764 assert(bset && bset->n_div == 0);
765 isl_basic_set_free(bset);
766 isl_local_space_free(ls);
767
768 /* test 6 */
769 dim = isl_space_set_alloc(ctx, 0, 3);
770 bset = isl_basic_set_universe(isl_space_copy(dim));
771 ls = isl_local_space_from_space(dim);
772
773 c = isl_equality_alloc(isl_local_space_copy(ls));
774 isl_int_set_si(v, -1);
775 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
776 isl_int_set_si(v, 6);
777 isl_constraint_set_coefficient(c, isl_dim_set, 2, v);
778 bset = isl_basic_set_add_constraint(bset, c);
779
780 c = isl_equality_alloc(isl_local_space_copy(ls));
781 isl_int_set_si(v, 1);
782 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
783 isl_int_set_si(v, -3);
784 isl_constraint_set_coefficient(c, isl_dim_set, 1, v);
785 bset = isl_basic_set_add_constraint(bset, c);
786
787 bset = isl_basic_set_project_out(bset, isl_dim_set, 2, 1);
788
789 assert(bset && bset->n_div == 1);
790 isl_basic_set_free(bset);
791 isl_local_space_free(ls);
792
793 /* test 7 */
794 /* This test is a bit tricky. We set up an equality
795 * a + 3b + 3c = 6 e0
796 * Normalization of divs creates _two_ divs
797 * a = 3 e0
798 * c - b - e0 = 2 e1
799 * Afterwards e0 is removed again because it has coefficient -1
800 * and we end up with the original equality and div again.
801 * Perhaps we can avoid the introduction of this temporary div.
802 */
803 dim = isl_space_set_alloc(ctx, 0, 4);
804 bset = isl_basic_set_universe(isl_space_copy(dim));
805 ls = isl_local_space_from_space(dim);
806
807 c = isl_equality_alloc(isl_local_space_copy(ls));
808 isl_int_set_si(v, -1);
809 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
810 isl_int_set_si(v, -3);
811 isl_constraint_set_coefficient(c, isl_dim_set, 1, v);
812 isl_int_set_si(v, -3);
813 isl_constraint_set_coefficient(c, isl_dim_set, 2, v);
814 isl_int_set_si(v, 6);
815 isl_constraint_set_coefficient(c, isl_dim_set, 3, v);
816 bset = isl_basic_set_add_constraint(bset, c);
817
818 bset = isl_basic_set_project_out(bset, isl_dim_set, 3, 1);
819
820 /* Test disabled for now */
821 /*
822 assert(bset && bset->n_div == 1);
823 */
824 isl_local_space_free(ls);
825 isl_basic_set_free(bset);
826
827 /* test 8 */
828 dim = isl_space_set_alloc(ctx, 0, 5);
829 bset = isl_basic_set_universe(isl_space_copy(dim));
830 ls = isl_local_space_from_space(dim);
831
832 c = isl_equality_alloc(isl_local_space_copy(ls));
833 isl_int_set_si(v, -1);
834 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
835 isl_int_set_si(v, -3);
836 isl_constraint_set_coefficient(c, isl_dim_set, 1, v);
837 isl_int_set_si(v, -3);
838 isl_constraint_set_coefficient(c, isl_dim_set, 3, v);
839 isl_int_set_si(v, 6);
840 isl_constraint_set_coefficient(c, isl_dim_set, 4, v);
841 bset = isl_basic_set_add_constraint(bset, c);
842
843 c = isl_equality_alloc(isl_local_space_copy(ls));
844 isl_int_set_si(v, -1);
845 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
846 isl_int_set_si(v, 1);
847 isl_constraint_set_coefficient(c, isl_dim_set, 2, v);
848 isl_int_set_si(v, 1);
849 isl_constraint_set_constant(c, v);
850 bset = isl_basic_set_add_constraint(bset, c);
851
852 bset = isl_basic_set_project_out(bset, isl_dim_set, 4, 1);
853
854 /* Test disabled for now */
855 /*
856 assert(bset && bset->n_div == 1);
857 */
858 isl_local_space_free(ls);
859 isl_basic_set_free(bset);
860
861 /* test 9 */
862 dim = isl_space_set_alloc(ctx, 0, 4);
863 bset = isl_basic_set_universe(isl_space_copy(dim));
864 ls = isl_local_space_from_space(dim);
865
866 c = isl_equality_alloc(isl_local_space_copy(ls));
867 isl_int_set_si(v, 1);
868 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
869 isl_int_set_si(v, -1);
870 isl_constraint_set_coefficient(c, isl_dim_set, 1, v);
871 isl_int_set_si(v, -2);
872 isl_constraint_set_coefficient(c, isl_dim_set, 2, v);
873 bset = isl_basic_set_add_constraint(bset, c);
874
875 c = isl_equality_alloc(isl_local_space_copy(ls));
876 isl_int_set_si(v, -1);
877 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
878 isl_int_set_si(v, 3);
879 isl_constraint_set_coefficient(c, isl_dim_set, 3, v);
880 isl_int_set_si(v, 2);
881 isl_constraint_set_constant(c, v);
882 bset = isl_basic_set_add_constraint(bset, c);
883
884 bset = isl_basic_set_project_out(bset, isl_dim_set, 2, 2);
885
886 bset = isl_basic_set_fix_si(bset, isl_dim_set, 0, 2);
887
888 assert(!isl_basic_set_is_empty(bset));
889
890 isl_local_space_free(ls);
891 isl_basic_set_free(bset);
892
893 /* test 10 */
894 dim = isl_space_set_alloc(ctx, 0, 3);
895 bset = isl_basic_set_universe(isl_space_copy(dim));
896 ls = isl_local_space_from_space(dim);
897
898 c = isl_equality_alloc(isl_local_space_copy(ls));
899 isl_int_set_si(v, 1);
900 isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
901 isl_int_set_si(v, -2);
902 isl_constraint_set_coefficient(c, isl_dim_set, 2, v);
903 bset = isl_basic_set_add_constraint(bset, c);
904
905 bset = isl_basic_set_project_out(bset, isl_dim_set, 2, 1);
906
907 bset = isl_basic_set_fix_si(bset, isl_dim_set, 0, 2);
908
909 isl_local_space_free(ls);
910 isl_basic_set_free(bset);
911
912 isl_int_clear(v);
913
914 str = "{ [i] : exists (e0, e1: 3e1 >= 1 + 2e0 and "
915 "8e1 <= -1 + 5i - 5e0 and 2e1 >= 1 + 2i - 5e0) }";
916 set = isl_set_read_from_str(ctx, str);
917 set = isl_set_compute_divs(set);
918 isl_set_free(set);
919 if (!set)
920 return -1;
921
922 str = "{ [i,j] : 2*[i/2] + 3 * [j/4] <= 10 and 2 i = j }";
923 bset = isl_basic_set_read_from_str(ctx, str);
924 n = isl_basic_set_dim(bset, isl_dim_div);
925 isl_basic_set_free(bset);
926 if (!bset)
927 return -1;
928 if (n != 0)
929 isl_die(ctx, isl_error_unknown,
930 "expecting no existentials", return -1);
931
932 str = "{ [i,j,k] : 3 + i + 2j >= 0 and 2 * [(i+2j)/4] <= k }";
933 set = isl_set_read_from_str(ctx, str);
934 set = isl_set_remove_divs_involving_dims(set, isl_dim_set, 0, 2);
935 set = isl_set_fix_si(set, isl_dim_set, 2, -3);
936 empty = isl_set_is_empty(set);
937 isl_set_free(set);
938 if (empty < 0)
939 return -1;
940 if (!empty)
941 isl_die(ctx, isl_error_unknown,
942 "result not as accurate as expected", return -1);
943
944 return 0;
945 }
946
947 void test_application_case(struct isl_ctx *ctx, const char *name)
948 {
949 char *filename;
950 FILE *input;
951 struct isl_basic_set *bset1, *bset2;
952 struct isl_basic_map *bmap;
953
954 filename = get_filename(ctx, name, "omega");
955 assert(filename);
956 input = fopen(filename, "r");
957 assert(input);
958
959 bset1 = isl_basic_set_read_from_file(ctx, input);
960 bmap = isl_basic_map_read_from_file(ctx, input);
961
962 bset1 = isl_basic_set_apply(bset1, bmap);
963
964 bset2 = isl_basic_set_read_from_file(ctx, input);
965
966 assert(isl_basic_set_is_equal(bset1, bset2) == 1);
967
968 isl_basic_set_free(bset1);
969 isl_basic_set_free(bset2);
970 free(filename);
971
972 fclose(input);
973 }
974
975 void test_application(struct isl_ctx *ctx)
976 {
977 test_application_case(ctx, "application");
978 test_application_case(ctx, "application2");
979 }
980
981 void test_affine_hull_case(struct isl_ctx *ctx, const char *name)
982 {
983 char *filename;
984 FILE *input;
985 struct isl_basic_set *bset1, *bset2;
986
987 filename = get_filename(ctx, name, "polylib");
988 assert(filename);
989 input = fopen(filename, "r");
990 assert(input);
991
992 bset1 = isl_basic_set_read_from_file(ctx, input);
993 bset2 = isl_basic_set_read_from_file(ctx, input);
994
995 bset1 = isl_basic_set_affine_hull(bset1);
996
997 assert(isl_basic_set_is_equal(bset1, bset2) == 1);
998
999 isl_basic_set_free(bset1);
1000 isl_basic_set_free(bset2);
1001 free(filename);
1002
1003 fclose(input);
1004 }
1005
1006 int test_affine_hull(struct isl_ctx *ctx)
1007 {
1008 const char *str;
1009 isl_set *set;
1010 isl_basic_set *bset, *bset2;
1011 int n;
1012 int subset;
1013
1014 test_affine_hull_case(ctx, "affine2");
1015 test_affine_hull_case(ctx, "affine");
1016 test_affine_hull_case(ctx, "affine3");
1017
1018 str = "[m] -> { [i0] : exists (e0, e1: e1 <= 1 + i0 and "
1019 "m >= 3 and 4i0 <= 2 + m and e1 >= i0 and "
1020 "e1 >= 0 and e1 <= 2 and e1 >= 1 + 2e0 and "
1021 "2e1 <= 1 + m + 4e0 and 2e1 >= 2 - m + 4i0 - 4e0) }";
1022 set = isl_set_read_from_str(ctx, str);
1023 bset = isl_set_affine_hull(set);
1024 n = isl_basic_set_dim(bset, isl_dim_div);
1025 isl_basic_set_free(bset);
1026 if (n != 0)
1027 isl_die(ctx, isl_error_unknown, "not expecting any divs",
1028 return -1);
1029
1030 /* Check that isl_map_affine_hull is not confused by
1031 * the reordering of divs in isl_map_align_divs.
1032 */
1033 str = "{ [a, b, c, 0] : exists (e0 = [(b)/32], e1 = [(c)/32]: "
1034 "32e0 = b and 32e1 = c); "
1035 "[a, 0, c, 0] : exists (e0 = [(c)/32]: 32e0 = c) }";
1036 set = isl_set_read_from_str(ctx, str);
1037 bset = isl_set_affine_hull(set);
1038 isl_basic_set_free(bset);
1039 if (!bset)
1040 return -1;
1041
1042 str = "{ [a] : exists e0, e1, e2: 32e1 = 31 + 31a + 31e0 and "
1043 "32e2 = 31 + 31e0 }";
1044 set = isl_set_read_from_str(ctx, str);
1045 bset = isl_set_affine_hull(set);
1046 str = "{ [a] : exists e : a = 32 e }";
1047 bset2 = isl_basic_set_read_from_str(ctx, str);
1048 subset = isl_basic_set_is_subset(bset, bset2);
1049 isl_basic_set_free(bset);
1050 isl_basic_set_free(bset2);
1051 if (subset < 0)
1052 return -1;
1053 if (!subset)
1054 isl_die(ctx, isl_error_unknown, "not as accurate as expected",
1055 return -1);
1056
1057 return 0;
1058 }
1059
1060 void test_convex_hull_case(struct isl_ctx *ctx, const char *name)
1061 {
1062 char *filename;
1063 FILE *input;
1064 struct isl_basic_set *bset1, *bset2;
1065 struct isl_set *set;
1066
1067 filename = get_filename(ctx, name, "polylib");
1068 assert(filename);
1069 input = fopen(filename, "r");
1070 assert(input);
1071
1072 bset1 = isl_basic_set_read_from_file(ctx, input);
1073 bset2 = isl_basic_set_read_from_file(ctx, input);
1074
1075 set = isl_basic_set_union(bset1, bset2);
1076 bset1 = isl_set_convex_hull(set);
1077
1078 bset2 = isl_basic_set_read_from_file(ctx, input);
1079
1080 assert(isl_basic_set_is_equal(bset1, bset2) == 1);
1081
1082 isl_basic_set_free(bset1);
1083 isl_basic_set_free(bset2);
1084 free(filename);
1085
1086 fclose(input);
1087 }
1088
1089 struct {
1090 const char *set;
1091 const char *hull;
1092 } convex_hull_tests[] = {
1093 { "{ [i0, i1, i2] : (i2 = 1 and i0 = 0 and i1 >= 0) or "
1094 "(i0 = 1 and i1 = 0 and i2 = 1) or "
1095 "(i0 = 0 and i1 = 0 and i2 = 0) }",
1096 "{ [i0, i1, i2] : i0 >= 0 and i2 >= i0 and i2 <= 1 and i1 >= 0 }" },
1097 { "[n] -> { [i0, i1, i0] : i0 <= -4 + n; "
1098 "[i0, i0, i2] : n = 6 and i0 >= 0 and i2 <= 7 - i0 and "
1099 "i2 <= 5 and i2 >= 4; "
1100 "[3, i1, 3] : n = 5 and i1 <= 2 and i1 >= 0 }",
1101 "[n] -> { [i0, i1, i2] : i2 <= -1 + n and 2i2 <= -6 + 3n - i0 and "
1102 "i2 <= 5 + i0 and i2 >= i0 }" },
1103 { "{ [x, y] : 3y <= 2x and y >= -2 + 2x and 2y >= 2 - x }",
1104 "{ [x, y] : 1 = 0 }" },
1105 };
1106
1107 void test_convex_hull_algo(struct isl_ctx *ctx, int convex)
1108 {
1109 int i;
1110 int orig_convex = ctx->opt->convex;
1111 ctx->opt->convex = convex;
1112
1113 test_convex_hull_case(ctx, "convex0");
1114 test_convex_hull_case(ctx, "convex1");
1115 test_convex_hull_case(ctx, "convex2");
1116 test_convex_hull_case(ctx, "convex3");
1117 test_convex_hull_case(ctx, "convex4");
1118 test_convex_hull_case(ctx, "convex5");
1119 test_convex_hull_case(ctx, "convex6");
1120 test_convex_hull_case(ctx, "convex7");
1121 test_convex_hull_case(ctx, "convex8");
1122 test_convex_hull_case(ctx, "convex9");
1123 test_convex_hull_case(ctx, "convex10");
1124 test_convex_hull_case(ctx, "convex11");
1125 test_convex_hull_case(ctx, "convex12");
1126 test_convex_hull_case(ctx, "convex13");
1127 test_convex_hull_case(ctx, "convex14");
1128 test_convex_hull_case(ctx, "convex15");
1129
1130 for (i = 0; i < ARRAY_SIZE(convex_hull_tests); ++i) {
1131 isl_set *set1, *set2;
1132
1133 set1 = isl_set_read_from_str(ctx, convex_hull_tests[i].set);
1134 set2 = isl_set_read_from_str(ctx, convex_hull_tests[i].hull);
1135 set1 = isl_set_from_basic_set(isl_set_convex_hull(set1));
1136 assert(isl_set_is_equal(set1, set2));
1137 isl_set_free(set1);
1138 isl_set_free(set2);
1139 }
1140
1141 ctx->opt->convex = orig_convex;
1142 }
1143
1144 void test_convex_hull(struct isl_ctx *ctx)
1145 {
1146 test_convex_hull_algo(ctx, ISL_CONVEX_HULL_FM);
1147 test_convex_hull_algo(ctx, ISL_CONVEX_HULL_WRAP);
1148 }
1149
1150 void test_gist_case(struct isl_ctx *ctx, const char *name)
1151 {
1152 char *filename;
1153 FILE *input;
1154 struct isl_basic_set *bset1, *bset2;
1155
1156 filename = get_filename(ctx, name, "polylib");
1157 assert(filename);
1158 input = fopen(filename, "r");
1159 assert(input);
1160
1161 bset1 = isl_basic_set_read_from_file(ctx, input);
1162 bset2 = isl_basic_set_read_from_file(ctx, input);
1163
1164 bset1 = isl_basic_set_gist(bset1, bset2);
1165
1166 bset2 = isl_basic_set_read_from_file(ctx, input);
1167
1168 assert(isl_basic_set_is_equal(bset1, bset2) == 1);
1169
1170 isl_basic_set_free(bset1);
1171 isl_basic_set_free(bset2);
1172 free(filename);
1173
1174 fclose(input);
1175 }
1176
1177 struct {
1178 const char *set;
1179 const char *context;
1180 const char *gist;
1181 } gist_tests[] = {
1182 { "{ [a, b, c] : a <= 15 and a >= 1 }",
1183 "{ [a, b, c] : exists (e0 = floor((-1 + a)/16): a >= 1 and "
1184 "c <= 30 and 32e0 >= -62 + 2a + 2b - c and b >= 0) }",
1185 "{ [a, b, c] : a <= 15 }" },
1186 { "{ : }", "{ : 1 = 0 }", "{ : }" },
1187 { "{ : 1 = 0 }", "{ : 1 = 0 }", "{ : }" },
1188 { "[M] -> { [x] : exists (e0 = floor((-2 + x)/3): 3e0 = -2 + x) }",
1189 "[M] -> { [3M] }" , "[M] -> { [x] : 1 = 0 }" },
1190 { "{ [m, n, a, b] : a <= 2147 + n }",
1191 "{ [m, n, a, b] : (m >= 1 and n >= 1 and a <= 2148 - m and "
1192 "b <= 2148 - n and b >= 0 and b >= 2149 - n - a) or "
1193 "(n >= 1 and a >= 0 and b <= 2148 - n - a and "
1194 "b >= 0) }",
1195 "{ [m, n, ku, kl] }" },
1196 };
1197
1198 static int test_gist(struct isl_ctx *ctx)
1199 {
1200 int i;
1201 const char *str;
1202 isl_basic_set *bset1, *bset2;
1203 isl_map *map1, *map2;
1204 int equal;
1205
1206 for (i = 0; i < ARRAY_SIZE(gist_tests); ++i) {
1207 int equal_input;
1208 isl_set *set1, *set2, *copy;
1209
1210 set1 = isl_set_read_from_str(ctx, gist_tests[i].set);
1211 set2 = isl_set_read_from_str(ctx, gist_tests[i].context);
1212 copy = isl_set_copy(set1);
1213 set1 = isl_set_gist(set1, set2);
1214 set2 = isl_set_read_from_str(ctx, gist_tests[i].gist);
1215 equal = isl_set_is_equal(set1, set2);
1216 isl_set_free(set1);
1217 isl_set_free(set2);
1218 set1 = isl_set_read_from_str(ctx, gist_tests[i].set);
1219 equal_input = isl_set_is_equal(set1, copy);
1220 isl_set_free(set1);
1221 isl_set_free(copy);
1222 if (equal < 0 || equal_input < 0)
1223 return -1;
1224 if (!equal)
1225 isl_die(ctx, isl_error_unknown,
1226 "incorrect gist result", return -1);
1227 if (!equal_input)
1228 isl_die(ctx, isl_error_unknown,
1229 "gist modified input", return -1);
1230 }
1231
1232 test_gist_case(ctx, "gist1");
1233
1234 str = "[p0, p2, p3, p5, p6, p10] -> { [] : "
1235 "exists (e0 = [(15 + p0 + 15p6 + 15p10)/16], e1 = [(p5)/8], "
1236 "e2 = [(p6)/128], e3 = [(8p2 - p5)/128], "
1237 "e4 = [(128p3 - p6)/4096]: 8e1 = p5 and 128e2 = p6 and "
1238 "128e3 = 8p2 - p5 and 4096e4 = 128p3 - p6 and p2 >= 0 and "
1239 "16e0 >= 16 + 16p6 + 15p10 and p2 <= 15 and p3 >= 0 and "
1240 "p3 <= 31 and p6 >= 128p3 and p5 >= 8p2 and p10 >= 0 and "
1241 "16e0 <= 15 + p0 + 15p6 + 15p10 and 16e0 >= p0 + 15p6 + 15p10 and "
1242 "p10 <= 15 and p10 <= -1 + p0 - p6) }";
1243 bset1 = isl_basic_set_read_from_str(ctx, str);
1244 str = "[p0, p2, p3, p5, p6, p10] -> { [] : exists (e0 = [(p5)/8], "
1245 "e1 = [(p6)/128], e2 = [(8p2 - p5)/128], "
1246 "e3 = [(128p3 - p6)/4096]: 8e0 = p5 and 128e1 = p6 and "
1247 "128e2 = 8p2 - p5 and 4096e3 = 128p3 - p6 and p5 >= -7 and "
1248 "p2 >= 0 and 8p2 <= -1 + p0 and p2 <= 15 and p3 >= 0 and "
1249 "p3 <= 31 and 128p3 <= -1 + p0 and p6 >= -127 and "
1250 "p5 <= -1 + p0 and p6 <= -1 + p0 and p6 >= 128p3 and "
1251 "p0 >= 1 and p5 >= 8p2 and p10 >= 0 and p10 <= 15 ) }";
1252 bset2 = isl_basic_set_read_from_str(ctx, str);
1253 bset1 = isl_basic_set_gist(bset1, bset2);
1254 assert(bset1 && bset1->n_div == 0);
1255 isl_basic_set_free(bset1);
1256
1257 /* Check that the integer divisions of the second disjunct
1258 * do not spread to the first disjunct.
1259 */
1260 str = "[t1] -> { S_0[] -> A[o0] : (exists (e0 = [(-t1 + o0)/16]: "
1261 "16e0 = -t1 + o0 and o0 >= 0 and o0 <= 15 and t1 >= 0)) or "
1262 "(exists (e0 = [(-1 + t1)/16], "
1263 "e1 = [(-16 + t1 - 16e0)/4294967296]: "
1264 "4294967296e1 = -16 + t1 - o0 - 16e0 and "
1265 "16e0 <= -1 + t1 and 16e0 >= -16 + t1 and o0 >= 0 and "
1266 "o0 <= 4294967295 and t1 <= -1)) }";
1267 map1 = isl_map_read_from_str(ctx, str);
1268 str = "[t1] -> { S_0[] -> A[o0] : t1 >= 0 and t1 <= 4294967295 }";
1269 map2 = isl_map_read_from_str(ctx, str);
1270 map1 = isl_map_gist(map1, map2);
1271 if (!map1)
1272 return -1;
1273 if (map1->n != 1)
1274 isl_die(ctx, isl_error_unknown, "expecting single disjunct",
1275 isl_map_free(map1); return -1);
1276 if (isl_basic_map_dim(map1->p[0], isl_dim_div) != 1)
1277 isl_die(ctx, isl_error_unknown, "expecting single div",
1278 isl_map_free(map1); return -1);
1279 isl_map_free(map1);
1280
1281 return 0;
1282 }
1283
1284 int test_coalesce_set(isl_ctx *ctx, const char *str, int check_one)
1285 {
1286 isl_set *set, *set2;
1287 int equal;
1288 int one;
1289
1290 set = isl_set_read_from_str(ctx, str);
1291 set = isl_set_coalesce(set);
1292 set2 = isl_set_read_from_str(ctx, str);
1293 equal = isl_set_is_equal(set, set2);
1294 one = set && set->n == 1;
1295 isl_set_free(set);
1296 isl_set_free(set2);
1297
1298 if (equal < 0)
1299 return -1;
1300 if (!equal)
1301 isl_die(ctx, isl_error_unknown,
1302 "coalesced set not equal to input", return -1);
1303 if (check_one && !one)
1304 isl_die(ctx, isl_error_unknown,
1305 "coalesced set should not be a union", return -1);
1306
1307 return 0;
1308 }
1309
1310 /* Inputs for coalescing tests with unbounded wrapping.
1311 * "str" is a string representation of the input set.
1312 * "single_disjunct" is set if we expect the result to consist of
1313 * a single disjunct.
1314 */
1315 struct {
1316 int single_disjunct;
1317 const char *str;
1318 } coalesce_unbounded_tests[] = {
1319 { 1, "{ [x,y,z] : y + 2 >= 0 and x - y + 1 >= 0 and "
1320 "-x - y + 1 >= 0 and -3 <= z <= 3;"
1321 "[x,y,z] : -x+z + 20 >= 0 and -x-z + 20 >= 0 and "
1322 "x-z + 20 >= 0 and x+z + 20 >= 0 and "
1323 "-10 <= y <= 0}" },
1324 { 1, "{ [x,y] : 0 <= x,y <= 10; [5,y]: 4 <= y <= 11 }" },
1325 { 1, "{ [x,0,0] : -5 <= x <= 5; [0,y,1] : -5 <= y <= 5 }" },
1326 { 1, "{ [x,y] : 0 <= x <= 10 and 0 >= y >= -1 and x+y >= 0; [0,1] }" },
1327 { 1, "{ [x,y] : (0 <= x,y <= 4) or (2 <= x,y <= 5 and x + y <= 9) }" },
1328 };
1329
1330 /* Test the functionality of isl_set_coalesce with the bounded wrapping
1331 * option turned off.
1332 */
1333 int test_coalesce_unbounded_wrapping(isl_ctx *ctx)
1334 {
1335 int i;
1336 int r = 0;
1337 int bounded;
1338
1339 bounded = isl_options_get_coalesce_bounded_wrapping(ctx);
1340 isl_options_set_coalesce_bounded_wrapping(ctx, 0);
1341
1342 for (i = 0; i < ARRAY_SIZE(coalesce_unbounded_tests); ++i) {
1343 const char *str = coalesce_unbounded_tests[i].str;
1344 int check_one = coalesce_unbounded_tests[i].single_disjunct;
1345 if (test_coalesce_set(ctx, str, check_one) >= 0)
1346 continue;
1347 r = -1;
1348 break;
1349 }
1350
1351 isl_options_set_coalesce_bounded_wrapping(ctx, bounded);
1352
1353 return r;
1354 }
1355
1356 /* Inputs for coalescing tests.
1357 * "str" is a string representation of the input set.
1358 * "single_disjunct" is set if we expect the result to consist of
1359 * a single disjunct.
1360 */
1361 struct {
1362 int single_disjunct;
1363 const char *str;
1364 } coalesce_tests[] = {
1365 { 1, "{[x,y]: x >= 0 & x <= 10 & y >= 0 & y <= 10 or "
1366 "y >= x & x >= 2 & 5 >= y }" },
1367 { 1, "{[x,y]: y >= 0 & 2x + y <= 30 & y <= 10 & x >= 0 or "
1368 "x + y >= 10 & y <= x & x + y <= 20 & y >= 0}" },
1369 { 0, "{[x,y]: y >= 0 & 2x + y <= 30 & y <= 10 & x >= 0 or "
1370 "x + y >= 10 & y <= x & x + y <= 19 & y >= 0}" },
1371 { 1, "{[x,y]: y >= 0 & x <= 5 & y <= x or "
1372 "y >= 0 & x >= 6 & x <= 10 & y <= x}" },
1373 { 0, "{[x,y]: y >= 0 & x <= 5 & y <= x or "
1374 "y >= 0 & x >= 7 & x <= 10 & y <= x}" },
1375 { 0, "{[x,y]: y >= 0 & x <= 5 & y <= x or "
1376 "y >= 0 & x >= 6 & x <= 10 & y + 1 <= x}" },
1377 { 1, "{[x,y]: y >= 0 & x <= 5 & y <= x or y >= 0 & x = 6 & y <= 6}" },
1378 { 0, "{[x,y]: y >= 0 & x <= 5 & y <= x or y >= 0 & x = 7 & y <= 6}" },
1379 { 1, "{[x,y]: y >= 0 & x <= 5 & y <= x or y >= 0 & x = 6 & y <= 5}" },
1380 { 0, "{[x,y]: y >= 0 & x <= 5 & y <= x or y >= 0 & x = 6 & y <= 7}" },
1381 { 1, "[n] -> { [i] : i = 1 and n >= 2 or 2 <= i and i <= n }" },
1382 { 0, "{[x,y] : x >= 0 and y >= 0 or 0 <= y and y <= 5 and x = -1}" },
1383 { 1, "[n] -> { [i] : 1 <= i and i <= n - 1 or 2 <= i and i <= n }" },
1384 { 0, "[n] -> { [[i0] -> [o0]] : exists (e0 = [(i0)/4], e1 = [(o0)/4], "
1385 "e2 = [(n)/2], e3 = [(-2 + i0)/4], e4 = [(-2 + o0)/4], "
1386 "e5 = [(-2n + i0)/4]: 2e2 = n and 4e3 = -2 + i0 and "
1387 "4e4 = -2 + o0 and i0 >= 8 + 2n and o0 >= 2 + i0 and "
1388 "o0 <= 56 + 2n and o0 <= -12 + 4n and i0 <= 57 + 2n and "
1389 "i0 <= -11 + 4n and o0 >= 6 + 2n and 4e0 <= i0 and "
1390 "4e0 >= -3 + i0 and 4e1 <= o0 and 4e1 >= -3 + o0 and "
1391 "4e5 <= -2n + i0 and 4e5 >= -3 - 2n + i0);"
1392 "[[i0] -> [o0]] : exists (e0 = [(i0)/4], e1 = [(o0)/4], "
1393 "e2 = [(n)/2], e3 = [(-2 + i0)/4], e4 = [(-2 + o0)/4], "
1394 "e5 = [(-2n + i0)/4]: 2e2 = n and 4e3 = -2 + i0 and "
1395 "4e4 = -2 + o0 and 2e0 >= 3 + n and e0 <= -4 + n and "
1396 "2e0 <= 27 + n and e1 <= -4 + n and 2e1 <= 27 + n and "
1397 "2e1 >= 2 + n and e1 >= 1 + e0 and i0 >= 7 + 2n and "
1398 "i0 <= -11 + 4n and i0 <= 57 + 2n and 4e0 <= -2 + i0 and "
1399 "4e0 >= -3 + i0 and o0 >= 6 + 2n and o0 <= -11 + 4n and "
1400 "o0 <= 57 + 2n and 4e1 <= -2 + o0 and 4e1 >= -3 + o0 and "
1401 "4e5 <= -2n + i0 and 4e5 >= -3 - 2n + i0 ) }" },
1402 { 0, "[n, m] -> { [o0, o2, o3] : (o3 = 1 and o0 >= 1 + m and "
1403 "o0 <= n + m and o2 <= m and o0 >= 2 + n and o2 >= 3) or "
1404 "(o0 >= 2 + n and o0 >= 1 + m and o0 <= n + m and n >= 1 and "
1405 "o3 <= -1 + o2 and o3 >= 1 - m + o2 and o3 >= 2 and o3 <= n) }" },
1406 { 0, "[M, N] -> { [[i0, i1, i2, i3, i4, i5, i6] -> "
1407 "[o0, o1, o2, o3, o4, o5, o6]] : "
1408 "(o6 <= -4 + 2M - 2N + i0 + i1 - i2 + i6 - o0 - o1 + o2 and "
1409 "o3 <= -2 + i3 and o6 >= 2 + i0 + i3 + i6 - o0 - o3 and "
1410 "o6 >= 2 - M + N + i3 + i4 + i6 - o3 - o4 and o0 <= -1 + i0 and "
1411 "o4 >= 4 - 3M + 3N - i0 - i1 + i2 + 2i3 + i4 + o0 + o1 - o2 - 2o3 "
1412 "and o6 <= -3 + 2M - 2N + i3 + i4 - i5 + i6 - o3 - o4 + o5 and "
1413 "2o6 <= -5 + 5M - 5N + 2i0 + i1 - i2 - i5 + 2i6 - 2o0 - o1 + o2 + o5 "
1414 "and o6 >= 2i0 + i1 + i6 - 2o0 - o1 and "
1415 "3o6 <= -5 + 4M - 4N + 2i0 + i1 - i2 + 2i3 + i4 - i5 + 3i6 "
1416 "- 2o0 - o1 + o2 - 2o3 - o4 + o5) or "
1417 "(N >= 2 and o3 <= -1 + i3 and o0 <= -1 + i0 and "
1418 "o6 >= i3 + i6 - o3 and M >= 0 and "
1419 "2o6 >= 1 + i0 + i3 + 2i6 - o0 - o3 and "
1420 "o6 >= 1 - M + i0 + i6 - o0 and N >= 2M and o6 >= i0 + i6 - o0) }" },
1421 { 0, "[M, N] -> { [o0] : (o0 = 0 and M >= 1 and N >= 2) or "
1422 "(o0 = 0 and M >= 1 and N >= 2M and N >= 2 + M) or "
1423 "(o0 = 0 and M >= 2 and N >= 3) or "
1424 "(M = 0 and o0 = 0 and N >= 3) }" },
1425 { 0, "{ [i0, i1, i2, i3] : (i1 = 10i0 and i0 >= 1 and 10i0 <= 100 and "
1426 "i3 <= 9 + 10 i2 and i3 >= 1 + 10i2 and i3 >= 0) or "
1427 "(i1 <= 9 + 10i0 and i1 >= 1 + 10i0 and i2 >= 0 and "
1428 "i0 >= 0 and i1 <= 100 and i3 <= 9 + 10i2 and i3 >= 1 + 10i2) }" },
1429 { 0, "[M] -> { [i1] : (i1 >= 2 and i1 <= M) or (i1 = M and M >= 1) }" },
1430 { 0, "{[x,y] : x,y >= 0; [x,y] : 10 <= x <= 20 and y >= -1 }" },
1431 { 1, "{ [x, y] : (x >= 1 and y >= 1 and x <= 2 and y <= 2) or "
1432 "(y = 3 and x = 1) }" },
1433 { 1, "[M] -> { [i0, i1, i2, i3, i4] : (i1 >= 3 and i4 >= 2 + i2 and "
1434 "i2 >= 2 and i0 >= 2 and i3 >= 1 + i2 and i0 <= M and "
1435 "i1 <= M and i3 <= M and i4 <= M) or "
1436 "(i1 >= 2 and i4 >= 1 + i2 and i2 >= 2 and i0 >= 2 and "
1437 "i3 >= 1 + i2 and i0 <= M and i1 <= -1 + M and i3 <= M and "
1438 "i4 <= -1 + M) }" },
1439 { 1, "{ [x, y] : (x >= 0 and y >= 0 and x <= 10 and y <= 10) or "
1440 "(x >= 1 and y >= 1 and x <= 11 and y <= 11) }" },
1441 { 0, "{[x,0] : x >= 0; [x,1] : x <= 20}" },
1442 { 1, "{ [x, 1 - x] : 0 <= x <= 1; [0,0] }" },
1443 { 1, "{ [0,0]; [i,i] : 1 <= i <= 10 }" },
1444 { 0, "{ [0,0]; [i,j] : 1 <= i,j <= 10 }" },
1445 { 1, "{ [0,0]; [i,2i] : 1 <= i <= 10 }" },
1446 { 0, "{ [0,0]; [i,2i] : 2 <= i <= 10 }" },
1447 { 0, "{ [1,0]; [i,2i] : 1 <= i <= 10 }" },
1448 { 0, "{ [0,1]; [i,2i] : 1 <= i <= 10 }" },
1449 { 0, "{ [a, b] : exists e : 2e = a and "
1450 "a >= 0 and (a <= 3 or (b <= 0 and b >= -4 + a)) }" },
1451 { 0, "{ [i, j, i', j'] : i <= 2 and j <= 2 and "
1452 "j' >= -1 + 2i + j - 2i' and i' <= -1 + i and "
1453 "j >= 1 and j' <= i + j - i' and i >= 1; "
1454 "[1, 1, 1, 1] }" },
1455 { 1, "{ [i,j] : exists a,b : i = 2a and j = 3b; "
1456 "[i,j] : exists a : j = 3a }" },
1457 { 1, "{ [a, b, c] : (c <= 7 - b and b <= 1 and b >= 0 and "
1458 "c >= 3 + b and b <= 3 + 8a and b >= -26 + 8a and "
1459 "a >= 3) or "
1460 "(b <= 1 and c <= 7 and b >= 0 and c >= 4 + b and "
1461 "b <= 3 + 8a and b >= -26 + 8a and a >= 3) }" },
1462 { 1, "{ [a, 0, c] : c >= 1 and c <= 29 and c >= -1 + 8a and "
1463 "c <= 6 + 8a and a >= 3; "
1464 "[a, -1, c] : c >= 1 and c <= 30 and c >= 8a and "
1465 "c <= 7 + 8a and a >= 3 and a <= 4 }" },
1466 { 1, "{ [x,y] : 0 <= x <= 2 and y >= 0 and x + 2y <= 4; "
1467 "[x,0] : 3 <= x <= 4 }" },
1468 { 1, "{ [x,y] : 0 <= x <= 3 and y >= 0 and x + 3y <= 6; "
1469 "[x,0] : 4 <= x <= 5 }" },
1470 { 0, "{ [x,y] : 0 <= x <= 2 and y >= 0 and x + 2y <= 4; "
1471 "[x,0] : 3 <= x <= 5 }" },
1472 { 0, "{ [x,y] : 0 <= x <= 2 and y >= 0 and x + y <= 4; "
1473 "[x,0] : 3 <= x <= 4 }" },
1474 { 1, "{ [i0, i1] : i0 <= 122 and i0 >= 1 and 128i1 >= -249 + i0 and "
1475 "i1 <= 0; "
1476 "[i0, 0] : i0 >= 123 and i0 <= 124 }" },
1477 { 1, "{ [0,0]; [1,1] }" },
1478 { 1, "[n] -> { [k] : 16k <= -1 + n and k >= 1; [0] : n >= 2 }" },
1479 { 1, "{ [k, ii, k - ii] : ii >= -6 + k and ii <= 6 and ii >= 1 and "
1480 "ii <= k;"
1481 "[k, 0, k] : k <= 6 and k >= 1 }" },
1482 { 1, "{ [i,j] : i = 4 j and 0 <= i <= 100;"
1483 "[i,j] : 1 <= i <= 100 and i >= 4j + 1 and i <= 4j + 2 }" },
1484 { 1, "{ [x,y] : x % 2 = 0 and y % 2 = 0; [x,x] : x % 2 = 0 }" },
1485 { 1, "[n] -> { [1] : n >= 0;"
1486 "[x] : exists (e0 = floor((x)/2): x >= 2 and "
1487 "2e0 >= -1 + x and 2e0 <= x and 2e0 <= n) }" },
1488 { 1, "[n] -> { [x, y] : exists (e0 = floor((x)/2), e1 = floor((y)/3): "
1489 "3e1 = y and x >= 2 and 2e0 >= -1 + x and "
1490 "2e0 <= x and 2e0 <= n);"
1491 "[1, y] : exists (e0 = floor((y)/3): 3e0 = y and "
1492 "n >= 0) }" },
1493 { 1, "[t1] -> { [i0] : (exists (e0 = floor((63t1)/64): "
1494 "128e0 >= -134 + 127t1 and t1 >= 2 and "
1495 "64e0 <= 63t1 and 64e0 >= -63 + 63t1)) or "
1496 "t1 = 1 }" },
1497 { 1, "{ [i, i] : exists (e0 = floor((1 + 2i)/3): 3e0 <= 2i and "
1498 "3e0 >= -1 + 2i and i <= 9 and i >= 1);"
1499 "[0, 0] }" },
1500 { 1, "{ [t1] : exists (e0 = floor((-11 + t1)/2): 2e0 = -11 + t1 and "
1501 "t1 >= 13 and t1 <= 16);"
1502 "[t1] : t1 <= 15 and t1 >= 12 }" },
1503 { 1, "{ [x,y] : x = 3y and 0 <= y <= 2; [-3,-1] }" },
1504 { 1, "{ [x,y] : 2x = 3y and 0 <= y <= 4; [-3,-2] }" },
1505 { 0, "{ [x,y] : 2x = 3y and 0 <= y <= 4; [-2,-2] }" },
1506 { 0, "{ [x,y] : 2x = 3y and 0 <= y <= 4; [-3,-1] }" },
1507 { 1, "{ [i] : exists j : i = 4 j and 0 <= i <= 100;"
1508 "[i] : exists j : 1 <= i <= 100 and i >= 4j + 1 and "
1509 "i <= 4j + 2 }" },
1510 { 1, "{ [c0] : (exists (e0 : c0 - 1 <= 3e0 <= c0)) or "
1511 "(exists (e0 : 3e0 = -2 + c0)) }" },
1512 { 0, "[n, b0, t0] -> "
1513 "{ [i0, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11, i12] : "
1514 "(exists (e0 = floor((-32b0 + i4)/1048576), "
1515 "e1 = floor((i8)/32): 1048576e0 = -32b0 + i4 and 32e1 = i8 and "
1516 "n <= 2147483647 and b0 <= 32767 and b0 >= 0 and "
1517 "32b0 <= -2 + n and t0 <= 31 and t0 >= 0 and i0 >= 8 + n and "
1518 "3i4 <= -96 + 3t0 + i0 and 3i4 >= -95 - n + 3t0 + i0 and "
1519 "i8 >= -157 + i0 - 4i4 and i8 >= 0 and "
1520 "i8 <= -33 + i0 - 4i4 and 3i8 <= -91 + 4n - i0)) or "
1521 "(exists (e0 = floor((-32b0 + i4)/1048576), "
1522 "e1 = floor((i8)/32): 1048576e0 = -32b0 + i4 and 32e1 = i8 and "
1523 "n <= 2147483647 and b0 <= 32767 and b0 >= 0 and "
1524 "32b0 <= -2 + n and t0 <= 31 and t0 >= 0 and i0 <= 7 + n and "
1525 "4i4 <= -3 + i0 and 3i4 <= -96 + 3t0 + i0 and "
1526 "3i4 >= -95 - n + 3t0 + i0 and i8 >= -157 + i0 - 4i4 and "
1527 "i8 >= 0 and i8 <= -4 + i0 - 3i4 and i8 <= -41 + i0));"
1528 "[i0, i1, i2, i3, 0, i5, i6, i7, i8, i9, i10, i11, i12] : "
1529 "(exists (e0 = floor((i8)/32): b0 = 0 and 32e0 = i8 and "
1530 "n <= 2147483647 and t0 <= 31 and t0 >= 0 and i0 >= 11 and "
1531 "i0 >= 96 - 3t0 and i0 <= 95 + n - 3t0 and i0 <= 7 + n and "
1532 "i8 >= -40 + i0 and i8 <= -10 + i0)) }" },
1533 };
1534
1535 /* A specialized coalescing test case that would result
1536 * in a segmentation fault or a failed assertion in earlier versions of isl.
1537 */
1538 static int test_coalesce_special(struct isl_ctx *ctx)
1539 {
1540 const char *str;
1541 isl_map *map1, *map2;
1542
1543 str = "[y] -> { [S_L220_OUT[] -> T7[]] -> "
1544 "[[S_L309_IN[] -> T11[]] -> ce_imag2[1, o1]] : "
1545 "(y = 201 and o1 <= 239 and o1 >= 212) or "
1546 "(exists (e0 = [(y)/3]: 3e0 = y and y <= 198 and y >= 3 and "
1547 "o1 <= 239 and o1 >= 212)) or "
1548 "(exists (e0 = [(y)/3]: 3e0 = y and y <= 201 and y >= 3 and "
1549 "o1 <= 241 and o1 >= 240));"
1550 "[S_L220_OUT[] -> T7[]] -> "
1551 "[[S_L309_IN[] -> T11[]] -> ce_imag2[0, o1]] : "
1552 "(y = 2 and o1 <= 241 and o1 >= 212) or "
1553 "(exists (e0 = [(-2 + y)/3]: 3e0 = -2 + y and y <= 200 and "
1554 "y >= 5 and o1 <= 241 and o1 >= 212)) }";
1555 map1 = isl_map_read_from_str(ctx, str);
1556 map1 = isl_map_align_divs(map1);
1557 map1 = isl_map_coalesce(map1);
1558 str = "[y] -> { [S_L220_OUT[] -> T7[]] -> "
1559 "[[S_L309_IN[] -> T11[]] -> ce_imag2[o0, o1]] : "
1560 "exists (e0 = [(-1 - y + o0)/3]: 3e0 = -1 - y + o0 and "
1561 "y <= 201 and o0 <= 2 and o1 >= 212 and o1 <= 241 and "
1562 "o0 >= 3 - y and o0 <= -2 + y and o0 >= 0) }";
1563 map2 = isl_map_read_from_str(ctx, str);
1564 map2 = isl_map_union(map2, map1);
1565 map2 = isl_map_align_divs(map2);
1566 map2 = isl_map_coalesce(map2);
1567 isl_map_free(map2);
1568 if (!map2)
1569 return -1;
1570
1571 return 0;
1572 }
1573
1574 /* Test the functionality of isl_set_coalesce.
1575 * That is, check that the output is always equal to the input
1576 * and in some cases that the result consists of a single disjunct.
1577 */
1578 static int test_coalesce(struct isl_ctx *ctx)
1579 {
1580 int i;
1581
1582 for (i = 0; i < ARRAY_SIZE(coalesce_tests); ++i) {
1583 const char *str = coalesce_tests[i].str;
1584 int check_one = coalesce_tests[i].single_disjunct;
1585 if (test_coalesce_set(ctx, str, check_one) < 0)
1586 return -1;
1587 }
1588
1589 if (test_coalesce_unbounded_wrapping(ctx) < 0)
1590 return -1;
1591 if (test_coalesce_special(ctx) < 0)
1592 return -1;
1593
1594 return 0;
1595 }
1596
1597 void test_closure(struct isl_ctx *ctx)
1598 {
1599 const char *str;
1600 isl_set *dom;
1601 isl_map *up, *right;
1602 isl_map *map, *map2;
1603 int exact;
1604
1605 /* COCOA example 1 */
1606 map = isl_map_read_from_str(ctx,
1607 "[n] -> { [i,j] -> [i2,j2] : i2 = i + 1 and j2 = j + 1 and "
1608 "1 <= i and i < n and 1 <= j and j < n or "
1609 "i2 = i + 1 and j2 = j - 1 and "
1610 "1 <= i and i < n and 2 <= j and j <= n }");
1611 map = isl_map_power(map, &exact);
1612 assert(exact);
1613 isl_map_free(map);
1614
1615 /* COCOA example 1 */
1616 map = isl_map_read_from_str(ctx,
1617 "[n] -> { [i,j] -> [i2,j2] : i2 = i + 1 and j2 = j + 1 and "
1618 "1 <= i and i < n and 1 <= j and j < n or "
1619 "i2 = i + 1 and j2 = j - 1 and "
1620 "1 <= i and i < n and 2 <= j and j <= n }");
1621 map = isl_map_transitive_closure(map, &exact);
1622 assert(exact);
1623 map2 = isl_map_read_from_str(ctx,
1624 "[n] -> { [i,j] -> [i2,j2] : exists (k1,k2,k : "
1625 "1 <= i and i < n and 1 <= j and j <= n and "
1626 "2 <= i2 and i2 <= n and 1 <= j2 and j2 <= n and "
1627 "i2 = i + k1 + k2 and j2 = j + k1 - k2 and "
1628 "k1 >= 0 and k2 >= 0 and k1 + k2 = k and k >= 1 )}");
1629 assert(isl_map_is_equal(map, map2));
1630 isl_map_free(map2);
1631 isl_map_free(map);
1632
1633 map = isl_map_read_from_str(ctx,
1634 "[n] -> { [x] -> [y] : y = x + 1 and 0 <= x and x <= n and "
1635 " 0 <= y and y <= n }");
1636 map = isl_map_transitive_closure(map, &exact);
1637 map2 = isl_map_read_from_str(ctx,
1638 "[n] -> { [x] -> [y] : y > x and 0 <= x and x <= n and "
1639 " 0 <= y and y <= n }");
1640 assert(isl_map_is_equal(map, map2));
1641 isl_map_free(map2);
1642 isl_map_free(map);
1643
1644 /* COCOA example 2 */
1645 map = isl_map_read_from_str(ctx,
1646 "[n] -> { [i,j] -> [i2,j2] : i2 = i + 2 and j2 = j + 2 and "
1647 "1 <= i and i < n - 1 and 1 <= j and j < n - 1 or "
1648 "i2 = i + 2 and j2 = j - 2 and "
1649 "1 <= i and i < n - 1 and 3 <= j and j <= n }");
1650 map = isl_map_transitive_closure(map, &exact);
1651 assert(exact);
1652 map2 = isl_map_read_from_str(ctx,
1653 "[n] -> { [i,j] -> [i2,j2] : exists (k1,k2,k : "
1654 "1 <= i and i < n - 1 and 1 <= j and j <= n and "
1655 "3 <= i2 and i2 <= n and 1 <= j2 and j2 <= n and "
1656 "i2 = i + 2 k1 + 2 k2 and j2 = j + 2 k1 - 2 k2 and "
1657 "k1 >= 0 and k2 >= 0 and k1 + k2 = k and k >= 1) }");
1658 assert(isl_map_is_equal(map, map2));
1659 isl_map_free(map);
1660 isl_map_free(map2);
1661
1662 /* COCOA Fig.2 left */
1663 map = isl_map_read_from_str(ctx,
1664 "[n] -> { [i,j] -> [i2,j2] : i2 = i + 2 and j2 = j and "
1665 "i <= 2 j - 3 and i <= n - 2 and j <= 2 i - 1 and "
1666 "j <= n or "
1667 "i2 = i and j2 = j + 2 and i <= 2 j - 1 and i <= n and "
1668 "j <= 2 i - 3 and j <= n - 2 or "
1669 "i2 = i + 1 and j2 = j + 1 and i <= 2 j - 1 and "
1670 "i <= n - 1 and j <= 2 i - 1 and j <= n - 1 }");
1671 map = isl_map_transitive_closure(map, &exact);
1672 assert(exact);
1673 isl_map_free(map);
1674
1675 /* COCOA Fig.2 right */
1676 map = isl_map_read_from_str(ctx,
1677 "[n] -> { [i,j] -> [i2,j2] : i2 = i + 3 and j2 = j and "
1678 "i <= 2 j - 4 and i <= n - 3 and j <= 2 i - 1 and "
1679 "j <= n or "
1680 "i2 = i and j2 = j + 3 and i <= 2 j - 1 and i <= n and "
1681 "j <= 2 i - 4 and j <= n - 3 or "
1682 "i2 = i + 1 and j2 = j + 1 and i <= 2 j - 1 and "
1683 "i <= n - 1 and j <= 2 i - 1 and j <= n - 1 }");
1684 map = isl_map_power(map, &exact);
1685 assert(exact);
1686 isl_map_free(map);
1687
1688 /* COCOA Fig.2 right */
1689 map = isl_map_read_from_str(ctx,
1690 "[n] -> { [i,j] -> [i2,j2] : i2 = i + 3 and j2 = j and "
1691 "i <= 2 j - 4 and i <= n - 3 and j <= 2 i - 1 and "
1692 "j <= n or "
1693 "i2 = i and j2 = j + 3 and i <= 2 j - 1 and i <= n and "
1694 "j <= 2 i - 4 and j <= n - 3 or "
1695 "i2 = i + 1 and j2 = j + 1 and i <= 2 j - 1 and "
1696 "i <= n - 1 and j <= 2 i - 1 and j <= n - 1 }");
1697 map = isl_map_transitive_closure(map, &exact);
1698 assert(exact);
1699 map2 = isl_map_read_from_str(ctx,
1700 "[n] -> { [i,j] -> [i2,j2] : exists (k1,k2,k3,k : "
1701 "i <= 2 j - 1 and i <= n and j <= 2 i - 1 and "
1702 "j <= n and 3 + i + 2 j <= 3 n and "
1703 "3 + 2 i + j <= 3n and i2 <= 2 j2 -1 and i2 <= n and "
1704 "i2 <= 3 j2 - 4 and j2 <= 2 i2 -1 and j2 <= n and "
1705 "13 + 4 j2 <= 11 i2 and i2 = i + 3 k1 + k3 and "
1706 "j2 = j + 3 k2 + k3 and k1 >= 0 and k2 >= 0 and "
1707 "k3 >= 0 and k1 + k2 + k3 = k and k > 0) }");
1708 assert(isl_map_is_equal(map, map2));
1709 isl_map_free(map2);
1710 isl_map_free(map);
1711
1712 /* COCOA Fig.1 right */
1713 dom = isl_set_read_from_str(ctx,
1714 "{ [x,y] : x >= 0 and -2 x + 3 y >= 0 and x <= 3 and "
1715 "2 x - 3 y + 3 >= 0 }");
1716 right = isl_map_read_from_str(ctx,
1717 "{ [x,y] -> [x2,y2] : x2 = x + 1 and y2 = y }");
1718 up = isl_map_read_from_str(ctx,
1719 "{ [x,y] -> [x2,y2] : x2 = x and y2 = y + 1 }");
1720 right = isl_map_intersect_domain(right, isl_set_copy(dom));
1721 right = isl_map_intersect_range(right, isl_set_copy(dom));
1722 up = isl_map_intersect_domain(up, isl_set_copy(dom));
1723 up = isl_map_intersect_range(up, dom);
1724 map = isl_map_union(up, right);
1725 map = isl_map_transitive_closure(map, &exact);
1726 assert(exact);
1727 map2 = isl_map_read_from_str(ctx,
1728 "{ [0,0] -> [0,1]; [0,0] -> [1,1]; [0,1] -> [1,1]; "
1729 " [2,2] -> [3,2]; [2,2] -> [3,3]; [3,2] -> [3,3] }");
1730 assert(isl_map_is_equal(map, map2));
1731 isl_map_free(map2);
1732 isl_map_free(map);
1733
1734 /* COCOA Theorem 1 counter example */
1735 map = isl_map_read_from_str(ctx,
1736 "{ [i,j] -> [i2,j2] : i = 0 and 0 <= j and j <= 1 and "
1737 "i2 = 1 and j2 = j or "
1738 "i = 0 and j = 0 and i2 = 0 and j2 = 1 }");
1739 map = isl_map_transitive_closure(map, &exact);
1740 assert(exact);
1741 isl_map_free(map);
1742
1743 map = isl_map_read_from_str(ctx,
1744 "[m,n] -> { [i,j] -> [i2,j2] : i2 = i and j2 = j + 2 and "
1745 "1 <= i,i2 <= n and 1 <= j,j2 <= m or "
1746 "i2 = i + 1 and 3 <= j2 - j <= 4 and "
1747 "1 <= i,i2 <= n and 1 <= j,j2 <= m }");
1748 map = isl_map_transitive_closure(map, &exact);
1749 assert(exact);
1750 isl_map_free(map);
1751
1752 /* Kelly et al 1996, fig 12 */
1753 map = isl_map_read_from_str(ctx,
1754 "[n] -> { [i,j] -> [i2,j2] : i2 = i and j2 = j + 1 and "
1755 "1 <= i,j,j+1 <= n or "
1756 "j = n and j2 = 1 and i2 = i + 1 and "
1757 "1 <= i,i+1 <= n }");
1758 map = isl_map_transitive_closure(map, &exact);
1759 assert(exact);
1760 map2 = isl_map_read_from_str(ctx,
1761 "[n] -> { [i,j] -> [i2,j2] : 1 <= j < j2 <= n and "
1762 "1 <= i <= n and i = i2 or "
1763 "1 <= i < i2 <= n and 1 <= j <= n and "
1764 "1 <= j2 <= n }");
1765 assert(isl_map_is_equal(map, map2));
1766 isl_map_free(map2);
1767 isl_map_free(map);
1768
1769 /* Omega's closure4 */
1770 map = isl_map_read_from_str(ctx,
1771 "[m,n] -> { [x,y] -> [x2,y2] : x2 = x and y2 = y + 1 and "
1772 "1 <= x,y <= 10 or "
1773 "x2 = x + 1 and y2 = y and "
1774 "1 <= x <= 20 && 5 <= y <= 15 }");
1775 map = isl_map_transitive_closure(map, &exact);
1776 assert(exact);
1777 isl_map_free(map);
1778
1779 map = isl_map_read_from_str(ctx,
1780 "[n] -> { [x] -> [y]: 1 <= n <= y - x <= 10 }");
1781 map = isl_map_transitive_closure(map, &exact);
1782 assert(!exact);
1783 map2 = isl_map_read_from_str(ctx,
1784 "[n] -> { [x] -> [y] : 1 <= n <= 10 and y >= n + x }");
1785 assert(isl_map_is_equal(map, map2));
1786 isl_map_free(map);
1787 isl_map_free(map2);
1788
1789 str = "[n, m] -> { [i0, i1, i2, i3] -> [o0, o1, o2, o3] : "
1790 "i3 = 1 and o0 = i0 and o1 = -1 + i1 and o2 = -1 + i2 and "
1791 "o3 = -2 + i2 and i1 <= -1 + i0 and i1 >= 1 - m + i0 and "
1792 "i1 >= 2 and i1 <= n and i2 >= 3 and i2 <= 1 + n and i2 <= m }";
1793 map = isl_map_read_from_str(ctx, str);
1794 map = isl_map_transitive_closure(map, &exact);
1795 assert(exact);
1796 map2 = isl_map_read_from_str(ctx, str);
1797 assert(isl_map_is_equal(map, map2));
1798 isl_map_free(map);
1799 isl_map_free(map2);
1800
1801 str = "{[0] -> [1]; [2] -> [3]}";
1802 map = isl_map_read_from_str(ctx, str);
1803 map = isl_map_transitive_closure(map, &exact);
1804 assert(exact);
1805 map2 = isl_map_read_from_str(ctx, str);
1806 assert(isl_map_is_equal(map, map2));
1807 isl_map_free(map);
1808 isl_map_free(map2);
1809
1810 str = "[n] -> { [[i0, i1, 1, 0, i0] -> [i5, 1]] -> "
1811 "[[i0, -1 + i1, 2, 0, i0] -> [-1 + i5, 2]] : "
1812 "exists (e0 = [(3 - n)/3]: i5 >= 2 and i1 >= 2 and "
1813 "3i0 <= -1 + n and i1 <= -1 + n and i5 <= -1 + n and "
1814 "3e0 >= 1 - n and 3e0 <= 2 - n and 3i0 >= -2 + n); "
1815 "[[i0, i1, 2, 0, i0] -> [i5, 1]] -> "
1816 "[[i0, i1, 1, 0, i0] -> [-1 + i5, 2]] : "
1817 "exists (e0 = [(3 - n)/3]: i5 >= 2 and i1 >= 1 and "
1818 "3i0 <= -1 + n and i1 <= -1 + n and i5 <= -1 + n and "
1819 "3e0 >= 1 - n and 3e0 <= 2 - n and 3i0 >= -2 + n); "
1820 "[[i0, i1, 1, 0, i0] -> [i5, 2]] -> "
1821 "[[i0, -1 + i1, 2, 0, i0] -> [i5, 1]] : "
1822 "exists (e0 = [(3 - n)/3]: i1 >= 2 and i5 >= 1 and "
1823 "3i0 <= -1 + n and i1 <= -1 + n and i5 <= -1 + n and "
1824 "3e0 >= 1 - n and 3e0 <= 2 - n and 3i0 >= -2 + n); "
1825 "[[i0, i1, 2, 0, i0] -> [i5, 2]] -> "
1826 "[[i0, i1, 1, 0, i0] -> [i5, 1]] : "
1827 "exists (e0 = [(3 - n)/3]: i5 >= 1 and i1 >= 1 and "
1828 "3i0 <= -1 + n and i1 <= -1 + n and i5 <= -1 + n and "
1829 "3e0 >= 1 - n and 3e0 <= 2 - n and 3i0 >= -2 + n) }";
1830 map = isl_map_read_from_str(ctx, str);
1831 map = isl_map_transitive_closure(map, NULL);
1832 assert(map);
1833 isl_map_free(map);
1834 }
1835
1836 void test_lex(struct isl_ctx *ctx)
1837 {
1838 isl_space *dim;
1839 isl_map *map;
1840
1841 dim = isl_space_set_alloc(ctx, 0, 0);
1842 map = isl_map_lex_le(dim);
1843 assert(!isl_map_is_empty(map));
1844 isl_map_free(map);
1845 }
1846
1847 static int test_lexmin(struct isl_ctx *ctx)
1848 {
1849 int equal;
1850 const char *str;
1851 isl_basic_map *bmap;
1852 isl_map *map, *map2;
1853 isl_set *set;
1854 isl_set *set2;
1855 isl_pw_multi_aff *pma;
1856
1857 str = "[p0, p1] -> { [] -> [] : "
1858 "exists (e0 = [(2p1)/3], e1, e2, e3 = [(3 - p1 + 3e0)/3], "
1859 "e4 = [(p1)/3], e5 = [(p1 + 3e4)/3]: "
1860 "3e0 >= -2 + 2p1 and 3e0 >= p1 and 3e3 >= 1 - p1 + 3e0 and "
1861 "3e0 <= 2p1 and 3e3 >= -2 + p1 and 3e3 <= -1 + p1 and p1 >= 3 and "
1862 "3e5 >= -2 + 2p1 and 3e5 >= p1 and 3e5 <= -1 + p1 + 3e4 and "
1863 "3e4 <= p1 and 3e4 >= -2 + p1 and e3 <= -1 + e0 and "
1864 "3e4 >= 6 - p1 + 3e1 and 3e1 >= p1 and 3e5 >= -2 + p1 + 3e4 and "
1865 "2e4 >= 3 - p1 + 2e1 and e4 <= e1 and 3e3 <= 2 - p1 + 3e0 and "
1866 "e5 >= 1 + e1 and 3e4 >= 6 - 2p1 + 3e1 and "
1867 "p0 >= 2 and p1 >= p0 and 3e2 >= p1 and 3e4 >= 6 - p1 + 3e2 and "
1868 "e2 <= e1 and e3 >= 1 and e4 <= e2) }";
1869 map = isl_map_read_from_str(ctx, str);
1870 map = isl_map_lexmin(map);
1871 isl_map_free(map);
1872
1873 str = "[C] -> { [obj,a,b,c] : obj <= 38 a + 7 b + 10 c and "
1874 "a + b <= 1 and c <= 10 b and c <= C and a,b,c,C >= 0 }";
1875 set = isl_set_read_from_str(ctx, str);
1876 set = isl_set_lexmax(set);
1877 str = "[C] -> { [obj,a,b,c] : C = 8 }";
1878 set2 = isl_set_read_from_str(ctx, str);
1879 set = isl_set_intersect(set, set2);
1880 assert(!isl_set_is_empty(set));
1881 isl_set_free(set);
1882
1883 str = "{ [x] -> [y] : x <= y <= 10; [x] -> [5] : -8 <= x <= 8 }";
1884 map = isl_map_read_from_str(ctx, str);
1885 map = isl_map_lexmin(map);
1886 str = "{ [x] -> [5] : 6 <= x <= 8; "
1887 "[x] -> [x] : x <= 5 or (9 <= x <= 10) }";
1888 map2 = isl_map_read_from_str(ctx, str);
1889 assert(isl_map_is_equal(map, map2));
1890 isl_map_free(map);
1891 isl_map_free(map2);
1892
1893 str = "{ [x] -> [y] : 4y = x or 4y = -1 + x or 4y = -2 + x }";
1894 map = isl_map_read_from_str(ctx, str);
1895 map2 = isl_map_copy(map);
1896 map = isl_map_lexmin(map);
1897 assert(isl_map_is_equal(map, map2));
1898 isl_map_free(map);
1899 isl_map_free(map2);
1900
1901 str = "{ [x] -> [y] : x = 4y; [x] -> [y] : x = 2y }";
1902 map = isl_map_read_from_str(ctx, str);
1903 map = isl_map_lexmin(map);
1904 str = "{ [x] -> [y] : (4y = x and x >= 0) or "
1905 "(exists (e0 = [(x)/4], e1 = [(-2 + x)/4]: 2y = x and "
1906 "4e1 = -2 + x and 4e0 <= -1 + x and 4e0 >= -3 + x)) or "
1907 "(exists (e0 = [(x)/4]: 2y = x and 4e0 = x and x <= -4)) }";
1908 map2 = isl_map_read_from_str(ctx, str);
1909 assert(isl_map_is_equal(map, map2));
1910 isl_map_free(map);
1911 isl_map_free(map2);
1912
1913 str = "{ [i] -> [i', j] : j = i - 8i' and i' >= 0 and i' <= 7 and "
1914 " 8i' <= i and 8i' >= -7 + i }";
1915 bmap = isl_basic_map_read_from_str(ctx, str);
1916 pma = isl_basic_map_lexmin_pw_multi_aff(isl_basic_map_copy(bmap));
1917 map2 = isl_map_from_pw_multi_aff(pma);
1918 map = isl_map_from_basic_map(bmap);
1919 assert(isl_map_is_equal(map, map2));
1920 isl_map_free(map);
1921 isl_map_free(map2);
1922
1923 str = "{ T[a] -> S[b, c] : a = 4b-2c and c >= b }";
1924 map = isl_map_read_from_str(ctx, str);
1925 map = isl_map_lexmin(map);
1926 str = "{ T[a] -> S[b, c] : 2b = a and 2c = a }";
1927 map2 = isl_map_read_from_str(ctx, str);
1928 assert(isl_map_is_equal(map, map2));
1929 isl_map_free(map);
1930 isl_map_free(map2);
1931
1932 /* Check that empty pieces are properly combined. */
1933 str = "[K, N] -> { [x, y] -> [a, b] : K+2<=N<=K+4 and x>=4 and "
1934 "2N-6<=x<K+N and N-1<=a<=K+N-1 and N+b-6<=a<=2N-4 and "
1935 "b<=2N-3K+a and 3b<=4N-K+1 and b>=N and a>=x+1 }";
1936 map = isl_map_read_from_str(ctx, str);
1937 map = isl_map_lexmin(map);
1938 str = "[K, N] -> { [x, y] -> [1 + x, N] : x >= -6 + 2N and "
1939 "x <= -5 + 2N and x >= -1 + 3K - N and x <= -2 + K + N and "
1940 "x >= 4 }";
1941 map2 = isl_map_read_from_str(ctx, str);
1942 assert(isl_map_is_equal(map, map2));
1943 isl_map_free(map);
1944 isl_map_free(map2);
1945
1946 str = "[i] -> { [i', j] : j = i - 8i' and i' >= 0 and i' <= 7 and "
1947 " 8i' <= i and 8i' >= -7 + i }";
1948 set = isl_set_read_from_str(ctx, str);
1949 pma = isl_set_lexmin_pw_multi_aff(isl_set_copy(set));
1950 set2 = isl_set_from_pw_multi_aff(pma);
1951 equal = isl_set_is_equal(set, set2);
1952 isl_set_free(set);
1953 isl_set_free(set2);
1954 if (equal < 0)
1955 return -1;
1956 if (!equal)
1957 isl_die(ctx, isl_error_unknown,
1958 "unexpected difference between set and "
1959 "piecewise affine expression", return -1);
1960
1961 return 0;
1962 }
1963
1964 /* Check that isl_set_min_val and isl_set_max_val compute the correct
1965 * result on non-convex inputs.
1966 */
1967 static int test_min(struct isl_ctx *ctx)
1968 {
1969 isl_set *set;
1970 isl_aff *aff;
1971 isl_val *val;
1972 int min_ok, max_ok;
1973
1974 set = isl_set_read_from_str(ctx, "{ [-1]; [1] }");
1975 aff = isl_aff_read_from_str(ctx, "{ [x] -> [x] }");
1976 val = isl_set_min_val(set, aff);
1977 min_ok = isl_val_is_negone(val);
1978 isl_val_free(val);
1979 val = isl_set_max_val(set, aff);
1980 max_ok = isl_val_is_one(val);
1981 isl_val_free(val);
1982 isl_aff_free(aff);
1983 isl_set_free(set);
1984
1985 if (min_ok < 0 || max_ok < 0)
1986 return -1;
1987 if (!min_ok)
1988 isl_die(ctx, isl_error_unknown,
1989 "unexpected minimum", return -1);
1990 if (!max_ok)
1991 isl_die(ctx, isl_error_unknown,
1992 "unexpected maximum", return -1);
1993
1994 return 0;
1995 }
1996
1997 struct must_may {
1998 isl_map *must;
1999 isl_map *may;
2000 };
2001
2002 static int collect_must_may(__isl_take isl_map *dep, int must,
2003 void *dep_user, void *user)
2004 {
2005 struct must_may *mm = (struct must_may *)user;
2006
2007 if (must)
2008 mm->must = isl_map_union(mm->must, dep);
2009 else
2010 mm->may = isl_map_union(mm->may, dep);
2011
2012 return 0;
2013 }
2014
2015 static int common_space(void *first, void *second)
2016 {
2017 int depth = *(int *)first;
2018 return 2 * depth;
2019 }
2020
2021 static int map_is_equal(__isl_keep isl_map *map, const char *str)
2022 {
2023 isl_map *map2;
2024 int equal;
2025
2026 if (!map)
2027 return -1;
2028
2029 map2 = isl_map_read_from_str(map->ctx, str);
2030 equal = isl_map_is_equal(map, map2);
2031 isl_map_free(map2);
2032
2033 return equal;
2034 }
2035
2036 static int map_check_equal(__isl_keep isl_map *map, const char *str)
2037 {
2038 int equal;
2039
2040 equal = map_is_equal(map, str);
2041 if (equal < 0)
2042 return -1;
2043 if (!equal)
2044 isl_die(isl_map_get_ctx(map), isl_error_unknown,
2045 "result not as expected", return -1);
2046 return 0;
2047 }
2048
2049 void test_dep(struct isl_ctx *ctx)
2050 {
2051 const char *str;
2052 isl_space *dim;
2053 isl_map *map;
2054 isl_access_info *ai;
2055 isl_flow *flow;
2056 int depth;
2057 struct must_may mm;
2058
2059 depth = 3;
2060
2061 str = "{ [2,i,0] -> [i] : 0 <= i <= 10 }";
2062 map = isl_map_read_from_str(ctx, str);
2063 ai = isl_access_info_alloc(map, &depth, &common_space, 2);
2064
2065 str = "{ [0,i,0] -> [i] : 0 <= i <= 10 }";
2066 map = isl_map_read_from_str(ctx, str);
2067 ai = isl_access_info_add_source(ai, map, 1, &depth);
2068
2069 str = "{ [1,i,0] -> [5] : 0 <= i <= 10 }";
2070 map = isl_map_read_from_str(ctx, str);
2071 ai = isl_access_info_add_source(ai, map, 1, &depth);
2072
2073 flow = isl_access_info_compute_flow(ai);
2074 dim = isl_space_alloc(ctx, 0, 3, 3);
2075 mm.must = isl_map_empty(isl_space_copy(dim));
2076 mm.may = isl_map_empty(dim);
2077
2078 isl_flow_foreach(flow, collect_must_may, &mm);
2079
2080 str = "{ [0,i,0] -> [2,i,0] : (0 <= i <= 4) or (6 <= i <= 10); "
2081 " [1,10,0] -> [2,5,0] }";
2082 assert(map_is_equal(mm.must, str));
2083 str = "{ [i,j,k] -> [l,m,n] : 1 = 0 }";
2084 assert(map_is_equal(mm.may, str));
2085
2086 isl_map_free(mm.must);
2087 isl_map_free(mm.may);
2088 isl_flow_free(flow);
2089
2090
2091 str = "{ [2,i,0] -> [i] : 0 <= i <= 10 }";
2092 map = isl_map_read_from_str(ctx, str);
2093 ai = isl_access_info_alloc(map, &depth, &common_space, 2);
2094
2095 str = "{ [0,i,0] -> [i] : 0 <= i <= 10 }";
2096 map = isl_map_read_from_str(ctx, str);
2097 ai = isl_access_info_add_source(ai, map, 1, &depth);
2098
2099 str = "{ [1,i,0] -> [5] : 0 <= i <= 10 }";
2100 map = isl_map_read_from_str(ctx, str);
2101 ai = isl_access_info_add_source(ai, map, 0, &depth);
2102
2103 flow = isl_access_info_compute_flow(ai);
2104 dim = isl_space_alloc(ctx, 0, 3, 3);
2105 mm.must = isl_map_empty(isl_space_copy(dim));
2106 mm.may = isl_map_empty(dim);
2107
2108 isl_flow_foreach(flow, collect_must_may, &mm);
2109
2110 str = "{ [0,i,0] -> [2,i,0] : (0 <= i <= 4) or (6 <= i <= 10) }";
2111 assert(map_is_equal(mm.must, str));
2112 str = "{ [0,5,0] -> [2,5,0]; [1,i,0] -> [2,5,0] : 0 <= i <= 10 }";
2113 assert(map_is_equal(mm.may, str));
2114
2115 isl_map_free(mm.must);
2116 isl_map_free(mm.may);
2117 isl_flow_free(flow);
2118
2119
2120 str = "{ [2,i,0] -> [i] : 0 <= i <= 10 }";
2121 map = isl_map_read_from_str(ctx, str);
2122 ai = isl_access_info_alloc(map, &depth, &common_space, 2);
2123
2124 str = "{ [0,i,0] -> [i] : 0 <= i <= 10 }";
2125 map = isl_map_read_from_str(ctx, str);
2126 ai = isl_access_info_add_source(ai, map, 0, &depth);
2127
2128 str = "{ [1,i,0] -> [5] : 0 <= i <= 10 }";
2129 map = isl_map_read_from_str(ctx, str);
2130 ai = isl_access_info_add_source(ai, map, 0, &depth);
2131
2132 flow = isl_access_info_compute_flow(ai);
2133 dim = isl_space_alloc(ctx, 0, 3, 3);
2134 mm.must = isl_map_empty(isl_space_copy(dim));
2135 mm.may = isl_map_empty(dim);
2136
2137 isl_flow_foreach(flow, collect_must_may, &mm);
2138
2139 str = "{ [0,i,0] -> [2,i,0] : 0 <= i <= 10; "
2140 " [1,i,0] -> [2,5,0] : 0 <= i <= 10 }";
2141 assert(map_is_equal(mm.may, str));
2142 str = "{ [i,j,k] -> [l,m,n] : 1 = 0 }";
2143 assert(map_is_equal(mm.must, str));
2144
2145 isl_map_free(mm.must);
2146 isl_map_free(mm.may);
2147 isl_flow_free(flow);
2148
2149
2150 str = "{ [0,i,2] -> [i] : 0 <= i <= 10 }";
2151 map = isl_map_read_from_str(ctx, str);
2152 ai = isl_access_info_alloc(map, &depth, &common_space, 2);
2153
2154 str = "{ [0,i,0] -> [i] : 0 <= i <= 10 }";
2155 map = isl_map_read_from_str(ctx, str);
2156 ai = isl_access_info_add_source(ai, map, 0, &depth);
2157
2158 str = "{ [0,i,1] -> [5] : 0 <= i <= 10 }";
2159 map = isl_map_read_from_str(ctx, str);
2160 ai = isl_access_info_add_source(ai, map, 0, &depth);
2161
2162 flow = isl_access_info_compute_flow(ai);
2163 dim = isl_space_alloc(ctx, 0, 3, 3);
2164 mm.must = isl_map_empty(isl_space_copy(dim));
2165 mm.may = isl_map_empty(dim);
2166
2167 isl_flow_foreach(flow, collect_must_may, &mm);
2168
2169 str = "{ [0,i,0] -> [0,i,2] : 0 <= i <= 10; "
2170 " [0,i,1] -> [0,5,2] : 0 <= i <= 5 }";
2171 assert(map_is_equal(mm.may, str));
2172 str = "{ [i,j,k] -> [l,m,n] : 1 = 0 }";
2173 assert(map_is_equal(mm.must, str));
2174
2175 isl_map_free(mm.must);
2176 isl_map_free(mm.may);
2177 isl_flow_free(flow);
2178
2179
2180 str = "{ [0,i,1] -> [i] : 0 <= i <= 10 }";
2181 map = isl_map_read_from_str(ctx, str);
2182 ai = isl_access_info_alloc(map, &depth, &common_space, 2);
2183
2184 str = "{ [0,i,0] -> [i] : 0 <= i <= 10 }";
2185 map = isl_map_read_from_str(ctx, str);
2186 ai = isl_access_info_add_source(ai, map, 0, &depth);
2187
2188 str = "{ [0,i,2] -> [5] : 0 <= i <= 10 }";
2189 map = isl_map_read_from_str(ctx, str);
2190 ai = isl_access_info_add_source(ai, map, 0, &depth);
2191
2192 flow = isl_access_info_compute_flow(ai);
2193 dim = isl_space_alloc(ctx, 0, 3, 3);
2194 mm.must = isl_map_empty(isl_space_copy(dim));
2195 mm.may = isl_map_empty(dim);
2196
2197 isl_flow_foreach(flow, collect_must_may, &mm);
2198
2199 str = "{ [0,i,0] -> [0,i,1] : 0 <= i <= 10; "
2200 " [0,i,2] -> [0,5,1] : 0 <= i <= 4 }";
2201 assert(map_is_equal(mm.may, str));
2202 str = "{ [i,j,k] -> [l,m,n] : 1 = 0 }";
2203 assert(map_is_equal(mm.must, str));
2204
2205 isl_map_free(mm.must);
2206 isl_map_free(mm.may);
2207 isl_flow_free(flow);
2208
2209
2210 depth = 5;
2211
2212 str = "{ [1,i,0,0,0] -> [i,j] : 0 <= i <= 10 and 0 <= j <= 10 }";
2213 map = isl_map_read_from_str(ctx, str);
2214 ai = isl_access_info_alloc(map, &depth, &common_space, 1);
2215
2216 str = "{ [0,i,0,j,0] -> [i,j] : 0 <= i <= 10 and 0 <= j <= 10 }";
2217 map = isl_map_read_from_str(ctx, str);
2218 ai = isl_access_info_add_source(ai, map, 1, &depth);
2219
2220 flow = isl_access_info_compute_flow(ai);
2221 dim = isl_space_alloc(ctx, 0, 5, 5);
2222 mm.must = isl_map_empty(isl_space_copy(dim));
2223 mm.may = isl_map_empty(dim);
2224
2225 isl_flow_foreach(flow, collect_must_may, &mm);
2226
2227 str = "{ [0,i,0,j,0] -> [1,i,0,0,0] : 0 <= i,j <= 10 }";
2228 assert(map_is_equal(mm.must, str));
2229 str = "{ [0,0,0,0,0] -> [0,0,0,0,0] : 1 = 0 }";
2230 assert(map_is_equal(mm.may, str));
2231
2232 isl_map_free(mm.must);
2233 isl_map_free(mm.may);
2234 isl_flow_free(flow);
2235 }
2236
2237 /* Check that the dependence analysis proceeds without errors.
2238 * Earlier versions of isl would break down during the analysis
2239 * due to the use of the wrong spaces.
2240 */
2241 static int test_flow(isl_ctx *ctx)
2242 {
2243 const char *str;
2244 isl_union_map *access, *schedule;
2245 isl_union_map *must_dep, *may_dep;
2246 int r;
2247
2248 str = "{ S0[j] -> i[]; S1[j,i] -> i[]; S2[] -> i[]; S3[] -> i[] }";
2249 access = isl_union_map_read_from_str(ctx, str);
2250 str = "{ S0[j] -> [0,j,0,0] : 0 <= j < 10; "
2251 "S1[j,i] -> [0,j,1,i] : 0 <= j < i < 10; "
2252 "S2[] -> [1,0,0,0]; "
2253 "S3[] -> [-1,0,0,0] }";
2254 schedule = isl_union_map_read_from_str(ctx, str);
2255 r = isl_union_map_compute_flow(access, isl_union_map_copy(access),
2256 isl_union_map_copy(access), schedule,
2257 &must_dep, &may_dep, NULL, NULL);
2258 isl_union_map_free(may_dep);
2259 isl_union_map_free(must_dep);
2260
2261 return r;
2262 }
2263
2264 struct {
2265 const char *map;
2266 int sv;
2267 } sv_tests[] = {
2268 { "[N] -> { [i] -> [f] : 0 <= i <= N and 0 <= i - 10 f <= 9 }", 1 },
2269 { "[N] -> { [i] -> [f] : 0 <= i <= N and 0 <= i - 10 f <= 10 }", 0 },
2270 { "{ [i] -> [3*floor(i/2) + 5*floor(i/3)] }", 1 },
2271 { "{ S1[i] -> [i] : 0 <= i <= 9; S2[i] -> [i] : 0 <= i <= 9 }", 1 },
2272 { "{ [i] -> S1[i] : 0 <= i <= 9; [i] -> S2[i] : 0 <= i <= 9 }", 0 },
2273 { "{ A[i] -> [i]; B[i] -> [i]; B[i] -> [i + 1] }", 0 },
2274 { "{ A[i] -> [i]; B[i] -> [i] : i < 0; B[i] -> [i + 1] : i > 0 }", 1 },
2275 { "{ A[i] -> [i]; B[i] -> A[i] : i < 0; B[i] -> [i + 1] : i > 0 }", 1 },
2276 { "{ A[i] -> [i]; B[i] -> [j] : i - 1 <= j <= i }", 0 },
2277 };
2278
2279 int test_sv(isl_ctx *ctx)
2280 {
2281 isl_union_map *umap;
2282 int i;
2283 int sv;
2284
2285 for (i = 0; i < ARRAY_SIZE(sv_tests); ++i) {
2286 umap = isl_union_map_read_from_str(ctx, sv_tests[i].map);
2287 sv = isl_union_map_is_single_valued(umap);
2288 isl_union_map_free(umap);
2289 if (sv < 0)
2290 return -1;
2291 if (sv_tests[i].sv && !sv)
2292 isl_die(ctx, isl_error_internal,
2293 "map not detected as single valued", return -1);
2294 if (!sv_tests[i].sv && sv)
2295 isl_die(ctx, isl_error_internal,
2296 "map detected as single valued", return -1);
2297 }
2298
2299 return 0;
2300 }
2301
2302 void test_bijective_case(struct isl_ctx *ctx, const char *str, int bijective)
2303 {
2304 isl_map *map;
2305
2306 map = isl_map_read_from_str(ctx, str);
2307 if (bijective)
2308 assert(isl_map_is_bijective(map));
2309 else
2310 assert(!isl_map_is_bijective(map));
2311 isl_map_free(map);
2312 }
2313
2314 void test_bijective(struct isl_ctx *ctx)
2315 {
2316 test_bijective_case(ctx, "[N,M]->{[i,j] -> [i]}", 0);
2317 test_bijective_case(ctx, "[N,M]->{[i,j] -> [i] : j=i}", 1);
2318 test_bijective_case(ctx, "[N,M]->{[i,j] -> [i] : j=0}", 1);
2319 test_bijective_case(ctx, "[N,M]->{[i,j] -> [i] : j=N}", 1);
2320 test_bijective_case(ctx, "[N,M]->{[i,j] -> [j,i]}", 1);
2321 test_bijective_case(ctx, "[N,M]->{[i,j] -> [i+j]}", 0);
2322 test_bijective_case(ctx, "[N,M]->{[i,j] -> []}", 0);
2323 test_bijective_case(ctx, "[N,M]->{[i,j] -> [i,j,N]}", 1);
2324 test_bijective_case(ctx, "[N,M]->{[i,j] -> [2i]}", 0);
2325 test_bijective_case(ctx, "[N,M]->{[i,j] -> [i,i]}", 0);
2326 test_bijective_case(ctx, "[N,M]->{[i,j] -> [2i,i]}", 0);
2327 test_bijective_case(ctx, "[N,M]->{[i,j] -> [2i,j]}", 1);
2328 test_bijective_case(ctx, "[N,M]->{[i,j] -> [x,y] : 2x=i & y =j}", 1);
2329 }
2330
2331 /* Inputs for isl_pw_qpolynomial_gist tests.
2332 * "pwqp" is the input, "set" is the context and "gist" is the expected result.
2333 */
2334 struct {
2335 const char *pwqp;
2336 const char *set;
2337 const char *gist;
2338 } pwqp_gist_tests[] = {
2339 { "{ [i] -> i }", "{ [k] : exists a : k = 2a }", "{ [i] -> i }" },
2340 { "{ [i] -> i + [ (i + [i/3])/2 ] }", "{ [10] }", "{ [i] -> 16 }" },
2341 { "{ [i] -> ([(i)/2]) }", "{ [k] : exists a : k = 2a+1 }",
2342 "{ [i] -> -1/2 + 1/2 * i }" },
2343 { "{ [i] -> i^2 : i != 0 }", "{ [i] : i != 0 }", "{ [i] -> i^2 }" },
2344 };
2345
2346 static int test_pwqp(struct isl_ctx *ctx)
2347 {
2348 int i;
2349 const char *str;
2350 isl_set *set;
2351 isl_pw_qpolynomial *pwqp1, *pwqp2;
2352 int equal;
2353
2354 str = "{ [i,j,k] -> 1 + 9 * [i/5] + 7 * [j/11] + 4 * [k/13] }";
2355 pwqp1 = isl_pw_qpolynomial_read_from_str(ctx, str);
2356
2357 pwqp1 = isl_pw_qpolynomial_move_dims(pwqp1, isl_dim_param, 0,
2358 isl_dim_in, 1, 1);
2359
2360 str = "[j] -> { [i,k] -> 1 + 9 * [i/5] + 7 * [j/11] + 4 * [k/13] }";
2361 pwqp2 = isl_pw_qpolynomial_read_from_str(ctx, str);
2362
2363 pwqp1 = isl_pw_qpolynomial_sub(pwqp1, pwqp2);
2364
2365 assert(isl_pw_qpolynomial_is_zero(pwqp1));
2366
2367 isl_pw_qpolynomial_free(pwqp1);
2368
2369 for (i = 0; i < ARRAY_SIZE(pwqp_gist_tests); ++i) {
2370 str = pwqp_gist_tests[i].pwqp;
2371 pwqp1 = isl_pw_qpolynomial_read_from_str(ctx, str);
2372 str = pwqp_gist_tests[i].set;
2373 set = isl_set_read_from_str(ctx, str);
2374 pwqp1 = isl_pw_qpolynomial_gist(pwqp1, set);
2375 str = pwqp_gist_tests[i].gist;
2376 pwqp2 = isl_pw_qpolynomial_read_from_str(ctx, str);
2377 pwqp1 = isl_pw_qpolynomial_sub(pwqp1, pwqp2);
2378 equal = isl_pw_qpolynomial_is_zero(pwqp1);
2379 isl_pw_qpolynomial_free(pwqp1);
2380
2381 if (equal < 0)
2382 return -1;
2383 if (!equal)
2384 isl_die(ctx, isl_error_unknown,
2385 "unexpected result", return -1);
2386 }
2387
2388 str = "{ [i] -> ([([i/2] + [i/2])/5]) }";
2389 pwqp1 = isl_pw_qpolynomial_read_from_str(ctx, str);
2390 str = "{ [i] -> ([(2 * [i/2])/5]) }";
2391 pwqp2 = isl_pw_qpolynomial_read_from_str(ctx, str);
2392
2393 pwqp1 = isl_pw_qpolynomial_sub(pwqp1, pwqp2);
2394
2395 assert(isl_pw_qpolynomial_is_zero(pwqp1));
2396
2397 isl_pw_qpolynomial_free(pwqp1);
2398
2399 str = "{ [x] -> ([x/2] + [(x+1)/2]) }";
2400 pwqp1 = isl_pw_qpolynomial_read_from_str(ctx, str);
2401 str = "{ [x] -> x }";
2402 pwqp2 = isl_pw_qpolynomial_read_from_str(ctx, str);
2403
2404 pwqp1 = isl_pw_qpolynomial_sub(pwqp1, pwqp2);
2405
2406 assert(isl_pw_qpolynomial_is_zero(pwqp1));
2407
2408 isl_pw_qpolynomial_free(pwqp1);
2409
2410 str = "{ [i] -> ([i/2]) : i >= 0; [i] -> ([i/3]) : i < 0 }";
2411 pwqp1 = isl_pw_qpolynomial_read_from_str(ctx, str);
2412 pwqp2 = isl_pw_qpolynomial_read_from_str(ctx, str);
2413 pwqp1 = isl_pw_qpolynomial_coalesce(pwqp1);
2414 pwqp1 = isl_pw_qpolynomial_sub(pwqp1, pwqp2);
2415 assert(isl_pw_qpolynomial_is_zero(pwqp1));
2416 isl_pw_qpolynomial_free(pwqp1);
2417
2418 str = "{ [a,b,a] -> (([(2*[a/3]+b)/5]) * ([(2*[a/3]+b)/5])) }";
2419 pwqp2 = isl_pw_qpolynomial_read_from_str(ctx, str);
2420 str = "{ [a,b,c] -> (([(2*[a/3]+b)/5]) * ([(2*[c/3]+b)/5])) }";
2421 pwqp1 = isl_pw_qpolynomial_read_from_str(ctx, str);
2422 set = isl_set_read_from_str(ctx, "{ [a,b,a] }");
2423 pwqp1 = isl_pw_qpolynomial_intersect_domain(pwqp1, set);
2424 equal = isl_pw_qpolynomial_plain_is_equal(pwqp1, pwqp2);
2425 isl_pw_qpolynomial_free(pwqp1);
2426 isl_pw_qpolynomial_free(pwqp2);
2427 if (equal < 0)
2428 return -1;
2429 if (!equal)
2430 isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
2431
2432 str = "{ [a,b,c] -> (([(2*[a/3]+1)/5]) * ([(2*[c/3]+1)/5])) : b = 1 }";
2433 pwqp2 = isl_pw_qpolynomial_read_from_str(ctx, str);
2434 str = "{ [a,b,c] -> (([(2*[a/3]+b)/5]) * ([(2*[c/3]+b)/5])) }";
2435 pwqp1 = isl_pw_qpolynomial_read_from_str(ctx, str);
2436 pwqp1 = isl_pw_qpolynomial_fix_val(pwqp1, isl_dim_set, 1,
2437 isl_val_one(ctx));
2438 equal = isl_pw_qpolynomial_plain_is_equal(pwqp1, pwqp2);
2439 isl_pw_qpolynomial_free(pwqp1);
2440 isl_pw_qpolynomial_free(pwqp2);
2441 if (equal < 0)
2442 return -1;
2443 if (!equal)
2444 isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
2445
2446 return 0;
2447 }
2448
2449 void test_split_periods(isl_ctx *ctx)
2450 {
2451 const char *str;
2452 isl_pw_qpolynomial *pwqp;
2453
2454 str = "{ [U,V] -> 1/3 * U + 2/3 * V - [(U + 2V)/3] + [U/2] : "
2455 "U + 2V + 3 >= 0 and - U -2V >= 0 and - U + 10 >= 0 and "
2456 "U >= 0; [U,V] -> U^2 : U >= 100 }";
2457 pwqp = isl_pw_qpolynomial_read_from_str(ctx, str);
2458
2459 pwqp = isl_pw_qpolynomial_split_periods(pwqp, 2);
2460 assert(pwqp);
2461
2462 isl_pw_qpolynomial_free(pwqp);
2463 }
2464
2465 void test_union(isl_ctx *ctx)
2466 {
2467 const char *str;
2468 isl_union_set *uset1, *uset2;
2469 isl_union_map *umap1, *umap2;
2470
2471 str = "{ [i] : 0 <= i <= 1 }";
2472 uset1 = isl_union_set_read_from_str(ctx, str);
2473 str = "{ [1] -> [0] }";
2474 umap1 = isl_union_map_read_from_str(ctx, str);
2475
2476 umap2 = isl_union_set_lex_gt_union_set(isl_union_set_copy(uset1), uset1);
2477 assert(isl_union_map_is_equal(umap1, umap2));
2478
2479 isl_union_map_free(umap1);
2480 isl_union_map_free(umap2);
2481
2482 str = "{ A[i] -> B[i]; B[i] -> C[i]; A[0] -> C[1] }";
2483 umap1 = isl_union_map_read_from_str(ctx, str);
2484 str = "{ A[i]; B[i] }";
2485 uset1 = isl_union_set_read_from_str(ctx, str);
2486
2487 uset2 = isl_union_map_domain(umap1);
2488
2489 assert(isl_union_set_is_equal(uset1, uset2));
2490
2491 isl_union_set_free(uset1);
2492 isl_union_set_free(uset2);
2493 }
2494
2495 void test_bound(isl_ctx *ctx)
2496 {
2497 const char *str;
2498 isl_pw_qpolynomial *pwqp;
2499 isl_pw_qpolynomial_fold *pwf;
2500
2501 str = "{ [[a, b, c, d] -> [e]] -> 0 }";
2502 pwqp = isl_pw_qpolynomial_read_from_str(ctx, str);
2503 pwf = isl_pw_qpolynomial_bound(pwqp, isl_fold_max, NULL);
2504 assert(isl_pw_qpolynomial_fold_dim(pwf, isl_dim_in) == 4);
2505 isl_pw_qpolynomial_fold_free(pwf);
2506
2507 str = "{ [[x]->[x]] -> 1 : exists a : x = 2 a }";
2508 pwqp = isl_pw_qpolynomial_read_from_str(ctx, str);
2509 pwf = isl_pw_qpolynomial_bound(pwqp, isl_fold_max, NULL);
2510 assert(isl_pw_qpolynomial_fold_dim(pwf, isl_dim_in) == 1);
2511 isl_pw_qpolynomial_fold_free(pwf);
2512 }
2513
2514 void test_lift(isl_ctx *ctx)
2515 {
2516 const char *str;
2517 isl_basic_map *bmap;
2518 isl_basic_set *bset;
2519
2520 str = "{ [i0] : exists e0 : i0 = 4e0 }";
2521 bset = isl_basic_set_read_from_str(ctx, str);
2522 bset = isl_basic_set_lift(bset);
2523 bmap = isl_basic_map_from_range(bset);
2524 bset = isl_basic_map_domain(bmap);
2525 isl_basic_set_free(bset);
2526 }
2527
2528 struct {
2529 const char *set1;
2530 const char *set2;
2531 int subset;
2532 } subset_tests[] = {
2533 { "{ [112, 0] }",
2534 "{ [i0, i1] : exists (e0 = [(i0 - i1)/16], e1: "
2535 "16e0 <= i0 - i1 and 16e0 >= -15 + i0 - i1 and "
2536 "16e1 <= i1 and 16e0 >= -i1 and 16e1 >= -i0 + i1) }", 1 },
2537 { "{ [65] }",
2538 "{ [i] : exists (e0 = [(255i)/256], e1 = [(127i + 65e0)/191], "
2539 "e2 = [(3i + 61e1)/65], e3 = [(52i + 12e2)/61], "
2540 "e4 = [(2i + e3)/3], e5 = [(4i + e3)/4], e6 = [(8i + e3)/12]: "
2541 "3e4 = 2i + e3 and 4e5 = 4i + e3 and 12e6 = 8i + e3 and "
2542 "i <= 255 and 64e3 >= -45 + 67i and i >= 0 and "
2543 "256e0 <= 255i and 256e0 >= -255 + 255i and "
2544 "191e1 <= 127i + 65e0 and 191e1 >= -190 + 127i + 65e0 and "
2545 "65e2 <= 3i + 61e1 and 65e2 >= -64 + 3i + 61e1 and "
2546 "61e3 <= 52i + 12e2 and 61e3 >= -60 + 52i + 12e2) }", 1 },
2547 { "{ [i] : 0 <= i <= 10 }", "{ rat: [i] : 0 <= i <= 10 }", 1 },
2548 { "{ rat: [i] : 0 <= i <= 10 }", "{ [i] : 0 <= i <= 10 }", 0 },
2549 { "{ rat: [0] }", "{ [i] : 0 <= i <= 10 }", 1 },
2550 { "{ rat: [(1)/2] }", "{ [i] : 0 <= i <= 10 }", 0 },
2551 { "{ [t, i] : (exists (e0 = [(2 + t)/4]: 4e0 <= 2 + t and "
2552 "4e0 >= -1 + t and i >= 57 and i <= 62 and "
2553 "4e0 <= 62 + t - i and 4e0 >= -61 + t + i and "
2554 "t >= 0 and t <= 511 and 4e0 <= -57 + t + i and "
2555 "4e0 >= 58 + t - i and i >= 58 + t and i >= 62 - t)) }",
2556 "{ [i0, i1] : (exists (e0 = [(4 + i0)/4]: 4e0 <= 62 + i0 - i1 and "
2557 "4e0 >= 1 + i0 and i0 >= 0 and i0 <= 511 and "
2558 "4e0 <= -57 + i0 + i1)) or "
2559 "(exists (e0 = [(2 + i0)/4]: 4e0 <= i0 and "
2560 "4e0 >= 58 + i0 - i1 and i0 >= 2 and i0 <= 511 and "
2561 "4e0 >= -61 + i0 + i1)) or "
2562 "(i1 <= 66 - i0 and i0 >= 2 and i1 >= 59 + i0) }", 1 },
2563 };
2564
2565 static int test_subset(isl_ctx *ctx)
2566 {
2567 int i;
2568 isl_set *set1, *set2;
2569 int subset;
2570
2571 for (i = 0; i < ARRAY_SIZE(subset_tests); ++i) {
2572 set1 = isl_set_read_from_str(ctx, subset_tests[i].set1);
2573 set2 = isl_set_read_from_str(ctx, subset_tests[i].set2);
2574 subset = isl_set_is_subset(set1, set2);
2575 isl_set_free(set1);
2576 isl_set_free(set2);
2577 if (subset < 0)
2578 return -1;
2579 if (subset != subset_tests[i].subset)
2580 isl_die(ctx, isl_error_unknown,
2581 "incorrect subset result", return -1);
2582 }
2583
2584 return 0;
2585 }
2586
2587 struct {
2588 const char *minuend;
2589 const char *subtrahend;
2590 const char *difference;
2591 } subtract_domain_tests[] = {
2592 { "{ A[i] -> B[i] }", "{ A[i] }", "{ }" },
2593 { "{ A[i] -> B[i] }", "{ B[i] }", "{ A[i] -> B[i] }" },
2594 { "{ A[i] -> B[i] }", "{ A[i] : i > 0 }", "{ A[i] -> B[i] : i <= 0 }" },
2595 };
2596
2597 static int test_subtract(isl_ctx *ctx)
2598 {
2599 int i;
2600 isl_union_map *umap1, *umap2;
2601 isl_union_pw_multi_aff *upma1, *upma2;
2602 isl_union_set *uset;
2603 int equal;
2604
2605 for (i = 0; i < ARRAY_SIZE(subtract_domain_tests); ++i) {
2606 umap1 = isl_union_map_read_from_str(ctx,
2607 subtract_domain_tests[i].minuend);
2608 uset = isl_union_set_read_from_str(ctx,
2609 subtract_domain_tests[i].subtrahend);
2610 umap2 = isl_union_map_read_from_str(ctx,
2611 subtract_domain_tests[i].difference);
2612 umap1 = isl_union_map_subtract_domain(umap1, uset);
2613 equal = isl_union_map_is_equal(umap1, umap2);
2614 isl_union_map_free(umap1);
2615 isl_union_map_free(umap2);
2616 if (equal < 0)
2617 return -1;
2618 if (!equal)
2619 isl_die(ctx, isl_error_unknown,
2620 "incorrect subtract domain result", return -1);
2621 }
2622
2623 for (i = 0; i < ARRAY_SIZE(subtract_domain_tests); ++i) {
2624 upma1 = isl_union_pw_multi_aff_read_from_str(ctx,
2625 subtract_domain_tests[i].minuend);
2626 uset = isl_union_set_read_from_str(ctx,
2627 subtract_domain_tests[i].subtrahend);
2628 upma2 = isl_union_pw_multi_aff_read_from_str(ctx,
2629 subtract_domain_tests[i].difference);
2630 upma1 = isl_union_pw_multi_aff_subtract_domain(upma1, uset);
2631 equal = isl_union_pw_multi_aff_plain_is_equal(upma1, upma2);
2632 isl_union_pw_multi_aff_free(upma1);
2633 isl_union_pw_multi_aff_free(upma2);
2634 if (equal < 0)
2635 return -1;
2636 if (!equal)
2637 isl_die(ctx, isl_error_unknown,
2638 "incorrect subtract domain result", return -1);
2639 }
2640
2641 return 0;
2642 }
2643
2644 int test_factorize(isl_ctx *ctx)
2645 {
2646 const char *str;
2647 isl_basic_set *bset;
2648 isl_factorizer *f;
2649
2650 str = "{ [i0, i1, i2, i3, i4, i5, i6, i7] : 3i5 <= 2 - 2i0 and "
2651 "i0 >= -2 and i6 >= 1 + i3 and i7 >= 0 and 3i5 >= -2i0 and "
2652 "2i4 <= i2 and i6 >= 1 + 2i0 + 3i1 and i4 <= -1 and "
2653 "i6 >= 1 + 2i0 + 3i5 and i6 <= 2 + 2i0 + 3i5 and "
2654 "3i5 <= 2 - 2i0 - i2 + 3i4 and i6 <= 2 + 2i0 + 3i1 and "
2655 "i0 <= -1 and i7 <= i2 + i3 - 3i4 - i6 and "
2656 "3i5 >= -2i0 - i2 + 3i4 }";
2657 bset = isl_basic_set_read_from_str(ctx, str);
2658 f = isl_basic_set_factorizer(bset);
2659 isl_basic_set_free(bset);
2660 isl_factorizer_free(f);
2661 if (!f)
2662 isl_die(ctx, isl_error_unknown,
2663 "failed to construct factorizer", return -1);
2664
2665 str = "{ [i0, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11, i12] : "
2666 "i12 <= 2 + i0 - i11 and 2i8 >= -i4 and i11 >= i1 and "
2667 "3i5 <= -i2 and 2i11 >= -i4 - 2i7 and i11 <= 3 + i0 + 3i9 and "
2668 "i11 <= -i4 - 2i7 and i12 >= -i10 and i2 >= -2 and "
2669 "i11 >= i1 + 3i10 and i11 >= 1 + i0 + 3i9 and "
2670 "i11 <= 1 - i4 - 2i8 and 6i6 <= 6 - i2 and 3i6 >= 1 - i2 and "
2671 "i11 <= 2 + i1 and i12 <= i4 + i11 and i12 >= i0 - i11 and "
2672 "3i5 >= -2 - i2 and i12 >= -1 + i4 + i11 and 3i3 <= 3 - i2 and "
2673 "9i6 <= 11 - i2 + 6i5 and 3i3 >= 1 - i2 and "
2674 "9i6 <= 5 - i2 + 6i3 and i12 <= -1 and i2 <= 0 }";
2675 bset = isl_basic_set_read_from_str(ctx, str);
2676 f = isl_basic_set_factorizer(bset);
2677 isl_basic_set_free(bset);
2678 isl_factorizer_free(f);
2679 if (!f)
2680 isl_die(ctx, isl_error_unknown,
2681 "failed to construct factorizer", return -1);
2682
2683 return 0;
2684 }
2685
2686 static int check_injective(__isl_take isl_map *map, void *user)
2687 {
2688 int *injective = user;
2689
2690 *injective = isl_map_is_injective(map);
2691 isl_map_free(map);
2692
2693 if (*injective < 0 || !*injective)
2694 return -1;
2695
2696 return 0;
2697 }
2698
2699 int test_one_schedule(isl_ctx *ctx, const char *d, const char *w,
2700 const char *r, const char *s, int tilable, int parallel)
2701 {
2702 int i;
2703 isl_union_set *D;
2704 isl_union_map *W, *R, *S;
2705 isl_union_map *empty;
2706 isl_union_map *dep_raw, *dep_war, *dep_waw, *dep;
2707 isl_union_map *validity, *proximity, *coincidence;
2708 isl_union_map *schedule;
2709 isl_union_map *test;
2710 isl_union_set *delta;
2711 isl_union_set *domain;
2712 isl_set *delta_set;
2713 isl_set *slice;
2714 isl_set *origin;
2715 isl_schedule_constraints *sc;
2716 isl_schedule *sched;
2717 int is_nonneg, is_parallel, is_tilable, is_injection, is_complete;
2718
2719 D = isl_union_set_read_from_str(ctx, d);
2720 W = isl_union_map_read_from_str(ctx, w);
2721 R = isl_union_map_read_from_str(ctx, r);
2722 S = isl_union_map_read_from_str(ctx, s);
2723
2724 W = isl_union_map_intersect_domain(W, isl_union_set_copy(D));
2725 R = isl_union_map_intersect_domain(R, isl_union_set_copy(D));
2726
2727 empty = isl_union_map_empty(isl_union_map_get_space(S));
2728 isl_union_map_compute_flow(isl_union_map_copy(R),
2729 isl_union_map_copy(W), empty,
2730 isl_union_map_copy(S),
2731 &dep_raw, NULL, NULL, NULL);
2732 isl_union_map_compute_flow(isl_union_map_copy(W),
2733 isl_union_map_copy(W),
2734 isl_union_map_copy(R),
2735 isl_union_map_copy(S),
2736 &dep_waw, &dep_war, NULL, NULL);
2737
2738 dep = isl_union_map_union(dep_waw, dep_war);
2739 dep = isl_union_map_union(dep, dep_raw);
2740 validity = isl_union_map_copy(dep);
2741 coincidence = isl_union_map_copy(dep);
2742 proximity = isl_union_map_copy(dep);
2743
2744 sc = isl_schedule_constraints_on_domain(isl_union_set_copy(D));
2745 sc = isl_schedule_constraints_set_validity(sc, validity);
2746 sc = isl_schedule_constraints_set_coincidence(sc, coincidence);
2747 sc = isl_schedule_constraints_set_proximity(sc, proximity);
2748 sched = isl_schedule_constraints_compute_schedule(sc);
2749 schedule = isl_schedule_get_map(sched);
2750 isl_schedule_free(sched);
2751 isl_union_map_free(W);
2752 isl_union_map_free(R);
2753 isl_union_map_free(S);
2754
2755 is_injection = 1;
2756 isl_union_map_foreach_map(schedule, &check_injective, &is_injection);
2757
2758 domain = isl_union_map_domain(isl_union_map_copy(schedule));
2759 is_complete = isl_union_set_is_subset(D, domain);
2760 isl_union_set_free(D);
2761 isl_union_set_free(domain);
2762
2763 test = isl_union_map_reverse(isl_union_map_copy(schedule));
2764 test = isl_union_map_apply_range(test, dep);
2765 test = isl_union_map_apply_range(test, schedule);
2766
2767 delta = isl_union_map_deltas(test);
2768 if (isl_union_set_n_set(delta) == 0) {
2769 is_tilable = 1;
2770 is_parallel = 1;
2771 is_nonneg = 1;
2772 isl_union_set_free(delta);
2773 } else {
2774 delta_set = isl_set_from_union_set(delta);
2775
2776 slice = isl_set_universe(isl_set_get_space(delta_set));
2777 for (i = 0; i < tilable; ++i)
2778 slice = isl_set_lower_bound_si(slice, isl_dim_set, i, 0);
2779 is_tilable = isl_set_is_subset(delta_set, slice);
2780 isl_set_free(slice);
2781
2782 slice = isl_set_universe(isl_set_get_space(delta_set));
2783 for (i = 0; i < parallel; ++i)
2784 slice = isl_set_fix_si(slice, isl_dim_set, i, 0);
2785 is_parallel = isl_set_is_subset(delta_set, slice);
2786 isl_set_free(slice);
2787
2788 origin = isl_set_universe(isl_set_get_space(delta_set));
2789 for (i = 0; i < isl_set_dim(origin, isl_dim_set); ++i)
2790 origin = isl_set_fix_si(origin, isl_dim_set, i, 0);
2791
2792 delta_set = isl_set_union(delta_set, isl_set_copy(origin));
2793 delta_set = isl_set_lexmin(delta_set);
2794
2795 is_nonneg = isl_set_is_equal(delta_set, origin);
2796
2797 isl_set_free(origin);
2798 isl_set_free(delta_set);
2799 }
2800
2801 if (is_nonneg < 0 || is_parallel < 0 || is_tilable < 0 ||
2802 is_injection < 0 || is_complete < 0)
2803 return -1;
2804 if (!is_complete)
2805 isl_die(ctx, isl_error_unknown,
2806 "generated schedule incomplete", return -1);
2807 if (!is_injection)
2808 isl_die(ctx, isl_error_unknown,
2809 "generated schedule not injective on each statement",
2810 return -1);
2811 if (!is_nonneg)
2812 isl_die(ctx, isl_error_unknown,
2813 "negative dependences in generated schedule",
2814 return -1);
2815 if (!is_tilable)
2816 isl_die(ctx, isl_error_unknown,
2817 "generated schedule not as tilable as expected",
2818 return -1);
2819 if (!is_parallel)
2820 isl_die(ctx, isl_error_unknown,
2821 "generated schedule not as parallel as expected",
2822 return -1);
2823
2824 return 0;
2825 }
2826
2827 static __isl_give isl_union_map *compute_schedule(isl_ctx *ctx,
2828 const char *domain, const char *validity, const char *proximity)
2829 {
2830 isl_union_set *dom;
2831 isl_union_map *dep;
2832 isl_union_map *prox;
2833 isl_schedule_constraints *sc;
2834 isl_schedule *schedule;
2835 isl_union_map *sched;
2836
2837 dom = isl_union_set_read_from_str(ctx, domain);
2838 dep = isl_union_map_read_from_str(ctx, validity);
2839 prox = isl_union_map_read_from_str(ctx, proximity);
2840 sc = isl_schedule_constraints_on_domain(dom);
2841 sc = isl_schedule_constraints_set_validity(sc, dep);
2842 sc = isl_schedule_constraints_set_proximity(sc, prox);
2843 schedule = isl_schedule_constraints_compute_schedule(sc);
2844 sched = isl_schedule_get_map(schedule);
2845 isl_schedule_free(schedule);
2846
2847 return sched;
2848 }
2849
2850 /* Check that a schedule can be constructed on the given domain
2851 * with the given validity and proximity constraints.
2852 */
2853 static int test_has_schedule(isl_ctx *ctx, const char *domain,
2854 const char *validity, const char *proximity)
2855 {
2856 isl_union_map *sched;
2857
2858 sched = compute_schedule(ctx, domain, validity, proximity);
2859 if (!sched)
2860 return -1;
2861
2862 isl_union_map_free(sched);
2863 return 0;
2864 }
2865
2866 int test_special_schedule(isl_ctx *ctx, const char *domain,
2867 const char *validity, const char *proximity, const char *expected_sched)
2868 {
2869 isl_union_map *sched1, *sched2;
2870 int equal;
2871
2872 sched1 = compute_schedule(ctx, domain, validity, proximity);
2873 sched2 = isl_union_map_read_from_str(ctx, expected_sched);
2874
2875 equal = isl_union_map_is_equal(sched1, sched2);
2876 isl_union_map_free(sched1);
2877 isl_union_map_free(sched2);
2878
2879 if (equal < 0)
2880 return -1;
2881 if (!equal)
2882 isl_die(ctx, isl_error_unknown, "unexpected schedule",
2883 return -1);
2884
2885 return 0;
2886 }
2887
2888 /* Check that the schedule map is properly padded, even after being
2889 * reconstructed from the band forest.
2890 */
2891 static int test_padded_schedule(isl_ctx *ctx)
2892 {
2893 const char *str;
2894 isl_union_set *D;
2895 isl_union_map *validity, *proximity;
2896 isl_schedule_constraints *sc;
2897 isl_schedule *sched;
2898 isl_union_map *map1, *map2;
2899 isl_band_list *list;
2900 int equal;
2901
2902 str = "[N] -> { S0[i] : 0 <= i <= N; S1[i, j] : 0 <= i, j <= N }";
2903 D = isl_union_set_read_from_str(ctx, str);
2904 validity = isl_union_map_empty(isl_union_set_get_space(D));
2905 proximity = isl_union_map_copy(validity);
2906 sc = isl_schedule_constraints_on_domain(D);
2907 sc = isl_schedule_constraints_set_validity(sc, validity);
2908 sc = isl_schedule_constraints_set_proximity(sc, proximity);
2909 sched = isl_schedule_constraints_compute_schedule(sc);
2910 map1 = isl_schedule_get_map(sched);
2911 list = isl_schedule_get_band_forest(sched);
2912 isl_band_list_free(list);
2913 map2 = isl_schedule_get_map(sched);
2914 isl_schedule_free(sched);
2915 equal = isl_union_map_is_equal(map1, map2);
2916 isl_union_map_free(map1);
2917 isl_union_map_free(map2);
2918
2919 if (equal < 0)
2920 return -1;
2921 if (!equal)
2922 isl_die(ctx, isl_error_unknown,
2923 "reconstructed schedule map not the same as original",
2924 return -1);
2925
2926 return 0;
2927 }
2928
2929 /* Input for testing of schedule construction based on
2930 * conditional constraints.
2931 *
2932 * domain is the iteration domain
2933 * flow are the flow dependences, which determine the validity and
2934 * proximity constraints
2935 * condition are the conditions on the conditional validity constraints
2936 * conditional_validity are the conditional validity constraints
2937 * outer_band_n is the expected number of members in the outer band
2938 */
2939 struct {
2940 const char *domain;
2941 const char *flow;
2942 const char *condition;
2943 const char *conditional_validity;
2944 int outer_band_n;
2945 } live_range_tests[] = {
2946 /* Contrived example that illustrates that we need to keep
2947 * track of tagged condition dependences and
2948 * tagged conditional validity dependences
2949 * in isl_sched_edge separately.
2950 * In particular, the conditional validity constraints on A
2951 * cannot be satisfied,
2952 * but they can be ignored because there are no corresponding
2953 * condition constraints. However, we do have an additional
2954 * conditional validity constraint that maps to the same
2955 * dependence relation
2956 * as the condition constraint on B. If we did not make a distinction
2957 * between tagged condition and tagged conditional validity
2958 * dependences, then we
2959 * could end up treating this shared dependence as an condition
2960 * constraint on A, forcing a localization of the conditions,
2961 * which is impossible.
2962 */
2963 { "{ S[i] : 0 <= 1 < 100; T[i] : 0 <= 1 < 100 }",
2964 "{ S[i] -> S[i+1] : 0 <= i < 99 }",
2965 "{ [S[i] -> B[]] -> [S[i+1] -> B[]] : 0 <= i < 99 }",
2966 "{ [S[i] -> A[]] -> [T[i'] -> A[]] : 0 <= i', i < 100 and i != i';"
2967 "[T[i] -> A[]] -> [S[i'] -> A[]] : 0 <= i', i < 100 and i != i';"
2968 "[S[i] -> A[]] -> [S[i+1] -> A[]] : 0 <= i < 99 }",
2969 1
2970 },
2971 /* TACO 2013 Fig. 7 */
2972 { "[n] -> { S1[i,j] : 0 <= i,j < n; S2[i,j] : 0 <= i,j < n }",
2973 "[n] -> { S1[i,j] -> S2[i,j] : 0 <= i,j < n;"
2974 "S2[i,j] -> S2[i,j+1] : 0 <= i < n and 0 <= j < n - 1 }",
2975 "[n] -> { [S1[i,j] -> t[]] -> [S2[i,j] -> t[]] : 0 <= i,j < n;"
2976 "[S2[i,j] -> x1[]] -> [S2[i,j+1] -> x1[]] : "
2977 "0 <= i < n and 0 <= j < n - 1 }",
2978 "[n] -> { [S2[i,j] -> t[]] -> [S1[i,j'] -> t[]] : "
2979 "0 <= i < n and 0 <= j < j' < n;"
2980 "[S2[i,j] -> t[]] -> [S1[i',j'] -> t[]] : "
2981 "0 <= i < i' < n and 0 <= j,j' < n;"
2982 "[S2[i,j] -> x1[]] -> [S2[i,j'] -> x1[]] : "
2983 "0 <= i,j,j' < n and j < j' }",
2984 2
2985 },
2986 /* TACO 2013 Fig. 7, without tags */
2987 { "[n] -> { S1[i,j] : 0 <= i,j < n; S2[i,j] : 0 <= i,j < n }",
2988 "[n] -> { S1[i,j] -> S2[i,j] : 0 <= i,j < n;"
2989 "S2[i,j] -> S2[i,j+1] : 0 <= i < n and 0 <= j < n - 1 }",
2990 "[n] -> { S1[i,j] -> S2[i,j] : 0 <= i,j < n;"
2991 "S2[i,j] -> S2[i,j+1] : 0 <= i < n and 0 <= j < n - 1 }",
2992 "[n] -> { S2[i,j] -> S1[i,j'] : 0 <= i < n and 0 <= j < j' < n;"
2993 "S2[i,j] -> S1[i',j'] : 0 <= i < i' < n and 0 <= j,j' < n;"
2994 "S2[i,j] -> S2[i,j'] : 0 <= i,j,j' < n and j < j' }",
2995 1
2996 },
2997 /* TACO 2013 Fig. 12 */
2998 { "{ S1[i,0] : 0 <= i <= 1; S2[i,j] : 0 <= i <= 1 and 1 <= j <= 2;"
2999 "S3[i,3] : 0 <= i <= 1 }",
3000 "{ S1[i,0] -> S2[i,1] : 0 <= i <= 1;"
3001 "S2[i,1] -> S2[i,2] : 0 <= i <= 1;"
3002 "S2[i,2] -> S3[i,3] : 0 <= i <= 1 }",
3003 "{ [S1[i,0]->t[]] -> [S2[i,1]->t[]] : 0 <= i <= 1;"
3004 "[S2[i,1]->t[]] -> [S2[i,2]->t[]] : 0 <= i <= 1;"
3005 "[S2[i,2]->t[]] -> [S3[i,3]->t[]] : 0 <= i <= 1 }",
3006 "{ [S2[i,1]->t[]] -> [S2[i,2]->t[]] : 0 <= i <= 1;"
3007 "[S2[0,j]->t[]] -> [S2[1,j']->t[]] : 1 <= j,j' <= 2;"
3008 "[S2[0,j]->t[]] -> [S1[1,0]->t[]] : 1 <= j <= 2;"
3009 "[S3[0,3]->t[]] -> [S2[1,j]->t[]] : 1 <= j <= 2;"
3010 "[S3[0,3]->t[]] -> [S1[1,0]->t[]] }",
3011 1
3012 }
3013 };
3014
3015 /* Test schedule construction based on conditional constraints.
3016 * In particular, check the number of members in the outer band node
3017 * as an indication of whether tiling is possible or not.
3018 */
3019 static int test_conditional_schedule_constraints(isl_ctx *ctx)
3020 {
3021 int i;
3022 isl_union_set *domain;
3023 isl_union_map *condition;
3024 isl_union_map *flow;
3025 isl_union_map *validity;
3026 isl_schedule_constraints *sc;
3027 isl_schedule *schedule;
3028 isl_schedule_node *node;
3029 int n_member;
3030
3031 for (i = 0; i < ARRAY_SIZE(live_range_tests); ++i) {
3032 domain = isl_union_set_read_from_str(ctx,
3033 live_range_tests[i].domain);
3034 flow = isl_union_map_read_from_str(ctx,
3035 live_range_tests[i].flow);
3036 condition = isl_union_map_read_from_str(ctx,
3037 live_range_tests[i].condition);
3038 validity = isl_union_map_read_from_str(ctx,
3039 live_range_tests[i].conditional_validity);
3040 sc = isl_schedule_constraints_on_domain(domain);
3041 sc = isl_schedule_constraints_set_validity(sc,
3042 isl_union_map_copy(flow));
3043 sc = isl_schedule_constraints_set_proximity(sc, flow);
3044 sc = isl_schedule_constraints_set_conditional_validity(sc,
3045 condition, validity);
3046 schedule = isl_schedule_constraints_compute_schedule(sc);
3047 node = isl_schedule_get_root(schedule);
3048 while (node &&
3049 isl_schedule_node_get_type(node) != isl_schedule_node_band)
3050 node = isl_schedule_node_first_child(node);
3051 n_member = isl_schedule_node_band_n_member(node);
3052 isl_schedule_node_free(node);
3053 isl_schedule_free(schedule);
3054
3055 if (!schedule)
3056 return -1;
3057 if (n_member != live_range_tests[i].outer_band_n)
3058 isl_die(ctx, isl_error_unknown,
3059 "unexpected number of members in outer band",
3060 return -1);
3061 }
3062 return 0;
3063 }
3064
3065 int test_schedule(isl_ctx *ctx)
3066 {
3067 const char *D, *W, *R, *V, *P, *S;
3068
3069 /* Handle resulting schedule with zero bands. */
3070 if (test_one_schedule(ctx, "{[]}", "{}", "{}", "{[] -> []}", 0, 0) < 0)
3071 return -1;
3072
3073 /* Jacobi */
3074 D = "[T,N] -> { S1[t,i] : 1 <= t <= T and 2 <= i <= N - 1 }";
3075 W = "{ S1[t,i] -> a[t,i] }";
3076 R = "{ S1[t,i] -> a[t-1,i]; S1[t,i] -> a[t-1,i-1]; "
3077 "S1[t,i] -> a[t-1,i+1] }";
3078 S = "{ S1[t,i] -> [t,i] }";
3079 if (test_one_schedule(ctx, D, W, R, S, 2, 0) < 0)
3080 return -1;
3081
3082 /* Fig. 5 of CC2008 */
3083 D = "[N] -> { S_0[i, j] : i >= 0 and i <= -1 + N and j >= 2 and "
3084 "j <= -1 + N }";
3085 W = "[N] -> { S_0[i, j] -> a[i, j] : i >= 0 and i <= -1 + N and "
3086 "j >= 2 and j <= -1 + N }";
3087 R = "[N] -> { S_0[i, j] -> a[j, i] : i >= 0 and i <= -1 + N and "
3088 "j >= 2 and j <= -1 + N; "
3089 "S_0[i, j] -> a[i, -1 + j] : i >= 0 and i <= -1 + N and "
3090 "j >= 2 and j <= -1 + N }";
3091 S = "[N] -> { S_0[i, j] -> [0, i, 0, j, 0] }";
3092 if (test_one_schedule(ctx, D, W, R, S, 2, 0) < 0)
3093 return -1;
3094
3095 D = "{ S1[i] : 0 <= i <= 10; S2[i] : 0 <= i <= 9 }";
3096 W = "{ S1[i] -> a[i] }";
3097 R = "{ S2[i] -> a[i+1] }";
3098 S = "{ S1[i] -> [0,i]; S2[i] -> [1,i] }";
3099 if (test_one_schedule(ctx, D, W, R, S, 1, 1) < 0)
3100 return -1;
3101
3102 D = "{ S1[i] : 0 <= i < 10; S2[i] : 0 <= i < 10 }";
3103 W = "{ S1[i] -> a[i] }";
3104 R = "{ S2[i] -> a[9-i] }";
3105 S = "{ S1[i] -> [0,i]; S2[i] -> [1,i] }";
3106 if (test_one_schedule(ctx, D, W, R, S, 1, 1) < 0)
3107 return -1;
3108
3109 D = "[N] -> { S1[i] : 0 <= i < N; S2[i] : 0 <= i < N }";
3110 W = "{ S1[i] -> a[i] }";
3111 R = "[N] -> { S2[i] -> a[N-1-i] }";
3112 S = "{ S1[i] -> [0,i]; S2[i] -> [1,i] }";
3113 if (test_one_schedule(ctx, D, W, R, S, 1, 1) < 0)
3114 return -1;
3115
3116 D = "{ S1[i] : 0 < i < 10; S2[i] : 0 <= i < 10 }";
3117 W = "{ S1[i] -> a[i]; S2[i] -> b[i] }";
3118 R = "{ S2[i] -> a[i]; S1[i] -> b[i-1] }";
3119 S = "{ S1[i] -> [i,0]; S2[i] -> [i,1] }";
3120 if (test_one_schedule(ctx, D, W, R, S, 0, 0) < 0)
3121 return -1;
3122
3123 D = "[N] -> { S1[i] : 1 <= i <= N; S2[i,j] : 1 <= i,j <= N }";
3124 W = "{ S1[i] -> a[0,i]; S2[i,j] -> a[i,j] }";
3125 R = "{ S2[i,j] -> a[i-1,j] }";
3126 S = "{ S1[i] -> [0,i,0]; S2[i,j] -> [1,i,j] }";
3127 if (test_one_schedule(ctx, D, W, R, S, 2, 1) < 0)
3128 return -1;
3129
3130 D = "[N] -> { S1[i] : 1 <= i <= N; S2[i,j] : 1 <= i,j <= N }";
3131 W = "{ S1[i] -> a[i,0]; S2[i,j] -> a[i,j] }";
3132 R = "{ S2[i,j] -> a[i,j-1] }";
3133 S = "{ S1[i] -> [0,i,0]; S2[i,j] -> [1,i,j] }";
3134 if (test_one_schedule(ctx, D, W, R, S, 2, 1) < 0)
3135 return -1;
3136
3137 D = "[N] -> { S_0[]; S_1[i] : i >= 0 and i <= -1 + N; S_2[] }";
3138 W = "[N] -> { S_0[] -> a[0]; S_2[] -> b[0]; "
3139 "S_1[i] -> a[1 + i] : i >= 0 and i <= -1 + N }";
3140 R = "[N] -> { S_2[] -> a[N]; S_1[i] -> a[i] : i >= 0 and i <= -1 + N }";
3141 S = "[N] -> { S_1[i] -> [1, i, 0]; S_2[] -> [2, 0, 1]; "
3142 "S_0[] -> [0, 0, 0] }";
3143 if (test_one_schedule(ctx, D, W, R, S, 1, 0) < 0)
3144 return -1;
3145 ctx->opt->schedule_parametric = 0;
3146 if (test_one_schedule(ctx, D, W, R, S, 0, 0) < 0)
3147 return -1;
3148 ctx->opt->schedule_parametric = 1;
3149
3150 D = "[N] -> { S1[i] : 1 <= i <= N; S2[i] : 1 <= i <= N; "
3151 "S3[i,j] : 1 <= i,j <= N; S4[i] : 1 <= i <= N }";
3152 W = "{ S1[i] -> a[i,0]; S2[i] -> a[0,i]; S3[i,j] -> a[i,j] }";
3153 R = "[N] -> { S3[i,j] -> a[i-1,j]; S3[i,j] -> a[i,j-1]; "
3154 "S4[i] -> a[i,N] }";
3155 S = "{ S1[i] -> [0,i,0]; S2[i] -> [1,i,0]; S3[i,j] -> [2,i,j]; "
3156 "S4[i] -> [4,i,0] }";
3157 if (test_one_schedule(ctx, D, W, R, S, 2, 0) < 0)
3158 return -1;
3159
3160 D = "[N] -> { S_0[i, j] : i >= 1 and i <= N and j >= 1 and j <= N }";
3161 W = "[N] -> { S_0[i, j] -> s[0] : i >= 1 and i <= N and j >= 1 and "
3162 "j <= N }";
3163 R = "[N] -> { S_0[i, j] -> s[0] : i >= 1 and i <= N and j >= 1 and "
3164 "j <= N; "
3165 "S_0[i, j] -> a[i, j] : i >= 1 and i <= N and j >= 1 and "
3166 "j <= N }";
3167 S = "[N] -> { S_0[i, j] -> [0, i, 0, j, 0] }";
3168 if (test_one_schedule(ctx, D, W, R, S, 0, 0) < 0)
3169 return -1;
3170
3171 D = "[N] -> { S_0[t] : t >= 0 and t <= -1 + N; "
3172 " S_2[t] : t >= 0 and t <= -1 + N; "
3173 " S_1[t, i] : t >= 0 and t <= -1 + N and i >= 0 and "
3174 "i <= -1 + N }";
3175 W = "[N] -> { S_0[t] -> a[t, 0] : t >= 0 and t <= -1 + N; "
3176 " S_2[t] -> b[t] : t >= 0 and t <= -1 + N; "
3177 " S_1[t, i] -> a[t, 1 + i] : t >= 0 and t <= -1 + N and "
3178 "i >= 0 and i <= -1 + N }";
3179 R = "[N] -> { S_1[t, i] -> a[t, i] : t >= 0 and t <= -1 + N and "
3180 "i >= 0 and i <= -1 + N; "
3181 " S_2[t] -> a[t, N] : t >= 0 and t <= -1 + N }";
3182 S = "[N] -> { S_2[t] -> [0, t, 2]; S_1[t, i] -> [0, t, 1, i, 0]; "
3183 " S_0[t] -> [0, t, 0] }";
3184
3185 if (test_one_schedule(ctx, D, W, R, S, 2, 1) < 0)
3186 return -1;
3187 ctx->opt->schedule_parametric = 0;
3188 if (test_one_schedule(ctx, D, W, R, S, 0, 0) < 0)
3189 return -1;
3190 ctx->opt->schedule_parametric = 1;
3191
3192 D = "[N] -> { S1[i,j] : 0 <= i,j < N; S2[i,j] : 0 <= i,j < N }";
3193 S = "{ S1[i,j] -> [0,i,j]; S2[i,j] -> [1,i,j] }";
3194 if (test_one_schedule(ctx, D, "{}", "{}", S, 2, 2) < 0)
3195 return -1;
3196
3197 D = "[M, N] -> { S_1[i] : i >= 0 and i <= -1 + M; "
3198 "S_0[i, j] : i >= 0 and i <= -1 + M and j >= 0 and j <= -1 + N }";
3199 W = "[M, N] -> { S_0[i, j] -> a[j] : i >= 0 and i <= -1 + M and "
3200 "j >= 0 and j <= -1 + N; "
3201 "S_1[i] -> b[0] : i >= 0 and i <= -1 + M }";
3202 R = "[M, N] -> { S_0[i, j] -> a[0] : i >= 0 and i <= -1 + M and "
3203 "j >= 0 and j <= -1 + N; "
3204 "S_1[i] -> b[0] : i >= 0 and i <= -1 + M }";
3205 S = "[M, N] -> { S_1[i] -> [1, i, 0]; S_0[i, j] -> [0, i, 0, j, 0] }";
3206 if (test_one_schedule(ctx, D, W, R, S, 0, 0) < 0)
3207 return -1;
3208
3209 D = "{ S_0[i] : i >= 0 }";
3210 W = "{ S_0[i] -> a[i] : i >= 0 }";
3211 R = "{ S_0[i] -> a[0] : i >= 0 }";
3212 S = "{ S_0[i] -> [0, i, 0] }";
3213 if (test_one_schedule(ctx, D, W, R, S, 0, 0) < 0)
3214 return -1;
3215
3216 D = "{ S_0[i] : i >= 0; S_1[i] : i >= 0 }";
3217 W = "{ S_0[i] -> a[i] : i >= 0; S_1[i] -> b[i] : i >= 0 }";
3218 R = "{ S_0[i] -> b[0] : i >= 0; S_1[i] -> a[i] : i >= 0 }";
3219 S = "{ S_1[i] -> [0, i, 1]; S_0[i] -> [0, i, 0] }";
3220 if (test_one_schedule(ctx, D, W, R, S, 0, 0) < 0)
3221 return -1;
3222
3223 D = "[n] -> { S_0[j, k] : j <= -1 + n and j >= 0 and "
3224 "k <= -1 + n and k >= 0 }";
3225 W = "[n] -> { S_0[j, k] -> B[j] : j <= -1 + n and j >= 0 and " "k <= -1 + n and k >= 0 }";
3226 R = "[n] -> { S_0[j, k] -> B[j] : j <= -1 + n and j >= 0 and "
3227 "k <= -1 + n and k >= 0; "
3228 "S_0[j, k] -> B[k] : j <= -1 + n and j >= 0 and "
3229 "k <= -1 + n and k >= 0; "
3230 "S_0[j, k] -> A[k] : j <= -1 + n and j >= 0 and "
3231 "k <= -1 + n and k >= 0 }";
3232 S = "[n] -> { S_0[j, k] -> [2, j, k] }";
3233 ctx->opt->schedule_outer_coincidence = 1;
3234 if (test_one_schedule(ctx, D, W, R, S, 0, 0) < 0)
3235 return -1;
3236 ctx->opt->schedule_outer_coincidence = 0;
3237
3238 D = "{Stmt_for_body24[i0, i1, i2, i3]:"
3239 "i0 >= 0 and i0 <= 1 and i1 >= 0 and i1 <= 6 and i2 >= 2 and "
3240 "i2 <= 6 - i1 and i3 >= 0 and i3 <= -1 + i2;"
3241 "Stmt_for_body24[i0, i1, 1, 0]:"
3242 "i0 >= 0 and i0 <= 1 and i1 >= 0 and i1 <= 5;"
3243 "Stmt_for_body7[i0, i1, i2]:"
3244 "i0 >= 0 and i0 <= 1 and i1 >= 0 and i1 <= 7 and i2 >= 0 and "
3245 "i2 <= 7 }";
3246
3247 V = "{Stmt_for_body24[0, i1, i2, i3] -> "
3248 "Stmt_for_body24[1, i1, i2, i3]:"
3249 "i3 >= 0 and i3 <= -1 + i2 and i1 >= 0 and i2 <= 6 - i1 and "
3250 "i2 >= 1;"
3251 "Stmt_for_body24[0, i1, i2, i3] -> "
3252 "Stmt_for_body7[1, 1 + i1 + i3, 1 + i1 + i2]:"
3253 "i3 <= -1 + i2 and i2 <= 6 - i1 and i2 >= 1 and i1 >= 0 and "
3254 "i3 >= 0;"
3255 "Stmt_for_body24[0, i1, i2, i3] ->"
3256 "Stmt_for_body7[1, i1, 1 + i1 + i3]:"
3257 "i3 >= 0 and i2 <= 6 - i1 and i1 >= 0 and i3 <= -1 + i2;"
3258 "Stmt_for_body7[0, i1, i2] -> Stmt_for_body7[1, i1, i2]:"
3259 "(i2 >= 1 + i1 and i2 <= 6 and i1 >= 0 and i1 <= 4) or "
3260 "(i2 >= 3 and i2 <= 7 and i1 >= 1 and i2 >= 1 + i1) or "
3261 "(i2 >= 0 and i2 <= i1 and i2 >= -7 + i1 and i1 <= 7);"
3262 "Stmt_for_body7[0, i1, 1 + i1] -> Stmt_for_body7[1, i1, 1 + i1]:"
3263 "i1 <= 6 and i1 >= 0;"
3264 "Stmt_for_body7[0, 0, 7] -> Stmt_for_body7[1, 0, 7];"
3265 "Stmt_for_body7[i0, i1, i2] -> "
3266 "Stmt_for_body24[i0, o1, -1 + i2 - o1, -1 + i1 - o1]:"
3267 "i0 >= 0 and i0 <= 1 and o1 >= 0 and i2 >= 1 + i1 and "
3268 "o1 <= -2 + i2 and i2 <= 7 and o1 <= -1 + i1;"
3269 "Stmt_for_body7[i0, i1, i2] -> "
3270 "Stmt_for_body24[i0, i1, o2, -1 - i1 + i2]:"
3271 "i0 >= 0 and i0 <= 1 and i1 >= 0 and o2 >= -i1 + i2 and "
3272 "o2 >= 1 and o2 <= 6 - i1 and i2 >= 1 + i1 }";
3273 P = V;
3274 S = "{ Stmt_for_body24[i0, i1, i2, i3] -> "
3275 "[i0, 5i0 + i1, 6i0 + i1 + i2, 1 + 6i0 + i1 + i2 + i3, 1];"
3276 "Stmt_for_body7[i0, i1, i2] -> [0, 5i0, 6i0 + i1, 6i0 + i2, 0] }";
3277
3278 if (test_special_schedule(ctx, D, V, P, S) < 0)
3279 return -1;
3280
3281 D = "{ S_0[i, j] : i >= 1 and i <= 10 and j >= 1 and j <= 8 }";
3282 V = "{ S_0[i, j] -> S_0[i, 1 + j] : i >= 1 and i <= 10 and "
3283 "j >= 1 and j <= 7;"
3284 "S_0[i, j] -> S_0[1 + i, j] : i >= 1 and i <= 9 and "
3285 "j >= 1 and j <= 8 }";
3286 P = "{ }";
3287 S = "{ S_0[i, j] -> [i + j, j] }";
3288 ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_FEAUTRIER;
3289 if (test_special_schedule(ctx, D, V, P, S) < 0)
3290 return -1;
3291 ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_ISL;
3292
3293 /* Fig. 1 from Feautrier's "Some Efficient Solutions..." pt. 2, 1992 */
3294 D = "[N] -> { S_0[i, j] : i >= 0 and i <= -1 + N and "
3295 "j >= 0 and j <= -1 + i }";
3296 V = "[N] -> { S_0[i, j] -> S_0[i, 1 + j] : j <= -2 + i and "
3297 "i <= -1 + N and j >= 0;"
3298 "S_0[i, -1 + i] -> S_0[1 + i, 0] : i >= 1 and "
3299 "i <= -2 + N }";
3300 P = "{ }";
3301 S = "{ S_0[i, j] -> [i, j] }";
3302 ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_FEAUTRIER;
3303 if (test_special_schedule(ctx, D, V, P, S) < 0)
3304 return -1;
3305 ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_ISL;
3306
3307 /* Test both algorithms on a case with only proximity dependences. */
3308 D = "{ S[i,j] : 0 <= i <= 10 }";
3309 V = "{ }";
3310 P = "{ S[i,j] -> S[i+1,j] : 0 <= i,j <= 10 }";
3311 S = "{ S[i, j] -> [j, i] }";
3312 ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_FEAUTRIER;
3313 if (test_special_schedule(ctx, D, V, P, S) < 0)
3314 return -1;
3315 ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_ISL;
3316 if (test_special_schedule(ctx, D, V, P, S) < 0)
3317 return -1;
3318
3319 D = "{ A[a]; B[] }";
3320 V = "{}";
3321 P = "{ A[a] -> B[] }";
3322 if (test_has_schedule(ctx, D, V, P) < 0)
3323 return -1;
3324
3325 if (test_padded_schedule(ctx) < 0)
3326 return -1;
3327
3328 /* Check that check for progress is not confused by rational
3329 * solution.
3330 */
3331 D = "[N] -> { S0[i, j] : i >= 0 and i <= N and j >= 0 and j <= N }";
3332 V = "[N] -> { S0[i0, -1 + N] -> S0[2 + i0, 0] : i0 >= 0 and "
3333 "i0 <= -2 + N; "
3334 "S0[i0, i1] -> S0[i0, 1 + i1] : i0 >= 0 and "
3335 "i0 <= N and i1 >= 0 and i1 <= -1 + N }";
3336 P = "{}";
3337 ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_FEAUTRIER;
3338 if (test_has_schedule(ctx, D, V, P) < 0)
3339 return -1;
3340 ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_ISL;
3341
3342 /* Check that we allow schedule rows that are only non-trivial
3343 * on some full-dimensional domains.
3344 */
3345 D = "{ S1[j] : 0 <= j <= 1; S0[]; S2[k] : 0 <= k <= 1 }";
3346 V = "{ S0[] -> S1[j] : 0 <= j <= 1; S2[0] -> S0[];"
3347 "S1[j] -> S2[1] : 0 <= j <= 1 }";
3348 P = "{}";
3349 ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_FEAUTRIER;
3350 if (test_has_schedule(ctx, D, V, P) < 0)
3351 return -1;
3352 ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_ISL;
3353
3354 if (test_conditional_schedule_constraints(ctx) < 0)
3355 return -1;
3356
3357 return 0;
3358 }
3359
3360 int test_plain_injective(isl_ctx *ctx, const char *str, int injective)
3361 {
3362 isl_union_map *umap;
3363 int test;
3364
3365 umap = isl_union_map_read_from_str(ctx, str);
3366 test = isl_union_map_plain_is_injective(umap);
3367 isl_union_map_free(umap);
3368 if (test < 0)
3369 return -1;
3370 if (test == injective)
3371 return 0;
3372 if (injective)
3373 isl_die(ctx, isl_error_unknown,
3374 "map not detected as injective", return -1);
3375 else
3376 isl_die(ctx, isl_error_unknown,
3377 "map detected as injective", return -1);
3378 }
3379
3380 int test_injective(isl_ctx *ctx)
3381 {
3382 const char *str;
3383
3384 if (test_plain_injective(ctx, "{S[i,j] -> A[0]; T[i,j] -> B[1]}", 0))
3385 return -1;
3386 if (test_plain_injective(ctx, "{S[] -> A[0]; T[] -> B[0]}", 1))
3387 return -1;
3388 if (test_plain_injective(ctx, "{S[] -> A[0]; T[] -> A[1]}", 1))
3389 return -1;
3390 if (test_plain_injective(ctx, "{S[] -> A[0]; T[] -> A[0]}", 0))
3391 return -1;
3392 if (test_plain_injective(ctx, "{S[i] -> A[i,0]; T[i] -> A[i,1]}", 1))
3393 return -1;
3394 if (test_plain_injective(ctx, "{S[i] -> A[i]; T[i] -> A[i]}", 0))
3395 return -1;
3396 if (test_plain_injective(ctx, "{S[] -> A[0,0]; T[] -> A[0,1]}", 1))
3397 return -1;
3398 if (test_plain_injective(ctx, "{S[] -> A[0,0]; T[] -> A[1,0]}", 1))
3399 return -1;
3400
3401 str = "{S[] -> A[0,0]; T[] -> A[0,1]; U[] -> A[1,0]}";
3402 if (test_plain_injective(ctx, str, 1))
3403 return -1;
3404 str = "{S[] -> A[0,0]; T[] -> A[0,1]; U[] -> A[0,0]}";
3405 if (test_plain_injective(ctx, str, 0))
3406 return -1;
3407
3408 return 0;
3409 }
3410
3411 static int aff_plain_is_equal(__isl_keep isl_aff *aff, const char *str)
3412 {
3413 isl_aff *aff2;
3414 int equal;
3415
3416 if (!aff)
3417 return -1;
3418
3419 aff2 = isl_aff_read_from_str(isl_aff_get_ctx(aff), str);
3420 equal = isl_aff_plain_is_equal(aff, aff2);
3421 isl_aff_free(aff2);
3422
3423 return equal;
3424 }
3425
3426 static int aff_check_plain_equal(__isl_keep isl_aff *aff, const char *str)
3427 {
3428 int equal;
3429
3430 equal = aff_plain_is_equal(aff, str);
3431 if (equal < 0)
3432 return -1;
3433 if (!equal)
3434 isl_die(isl_aff_get_ctx(aff), isl_error_unknown,
3435 "result not as expected", return -1);
3436 return 0;
3437 }
3438
3439 struct {
3440 __isl_give isl_aff *(*fn)(__isl_take isl_aff *aff1,
3441 __isl_take isl_aff *aff2);
3442 } aff_bin_op[] = {
3443 ['+'] = { &isl_aff_add },
3444 ['-'] = { &isl_aff_sub },
3445 ['*'] = { &isl_aff_mul },
3446 ['/'] = { &isl_aff_div },
3447 };
3448
3449 struct {
3450 const char *arg1;
3451 unsigned char op;
3452 const char *arg2;
3453 const char *res;
3454 } aff_bin_tests[] = {
3455 { "{ [i] -> [i] }", '+', "{ [i] -> [i] }",
3456 "{ [i] -> [2i] }" },
3457 { "{ [i] -> [i] }", '-', "{ [i] -> [i] }",
3458 "{ [i] -> [0] }" },
3459 { "{ [i] -> [i] }", '*', "{ [i] -> [2] }",
3460 "{ [i] -> [2i] }" },
3461 { "{ [i] -> [2] }", '*', "{ [i] -> [i] }",
3462 "{ [i] -> [2i] }" },
3463 { "{ [i] -> [i] }", '/', "{ [i] -> [2] }",
3464 "{ [i] -> [i/2] }" },
3465 { "{ [i] -> [2i] }", '/', "{ [i] -> [2] }",
3466 "{ [i] -> [i] }" },
3467 { "{ [i] -> [i] }", '+', "{ [i] -> [NaN] }",
3468 "{ [i] -> [NaN] }" },
3469 { "{ [i] -> [i] }", '-', "{ [i] -> [NaN] }",
3470 "{ [i] -> [NaN] }" },
3471 { "{ [i] -> [i] }", '*', "{ [i] -> [NaN] }",
3472 "{ [i] -> [NaN] }" },
3473 { "{ [i] -> [2] }", '*', "{ [i] -> [NaN] }",
3474 "{ [i] -> [NaN] }" },
3475 { "{ [i] -> [i] }", '/', "{ [i] -> [NaN] }",
3476 "{ [i] -> [NaN] }" },
3477 { "{ [i] -> [2] }", '/', "{ [i] -> [NaN] }",
3478 "{ [i] -> [NaN] }" },
3479 { "{ [i] -> [NaN] }", '+', "{ [i] -> [i] }",
3480 "{ [i] -> [NaN] }" },
3481 { "{ [i] -> [NaN] }", '-', "{ [i] -> [i] }",
3482 "{ [i] -> [NaN] }" },
3483 { "{ [i] -> [NaN] }", '*', "{ [i] -> [2] }",
3484 "{ [i] -> [NaN] }" },
3485 { "{ [i] -> [NaN] }", '*', "{ [i] -> [i] }",
3486 "{ [i] -> [NaN] }" },
3487 { "{ [i] -> [NaN] }", '/', "{ [i] -> [2] }",
3488 "{ [i] -> [NaN] }" },
3489 { "{ [i] -> [NaN] }", '/', "{ [i] -> [i] }",
3490 "{ [i] -> [NaN] }" },
3491 };
3492
3493 /* Perform some basic tests of binary operations on isl_aff objects.
3494 */
3495 static int test_bin_aff(isl_ctx *ctx)
3496 {
3497 int i;
3498 isl_aff *aff1, *aff2, *res;
3499 __isl_give isl_aff *(*fn)(__isl_take isl_aff *aff1,
3500 __isl_take isl_aff *aff2);
3501 int ok;
3502
3503 for (i = 0; i < ARRAY_SIZE(aff_bin_tests); ++i) {
3504 aff1 = isl_aff_read_from_str(ctx, aff_bin_tests[i].arg1);
3505 aff2 = isl_aff_read_from_str(ctx, aff_bin_tests[i].arg2);
3506 res = isl_aff_read_from_str(ctx, aff_bin_tests[i].res);
3507 fn = aff_bin_op[aff_bin_tests[i].op].fn;
3508 aff1 = fn(aff1, aff2);
3509 if (isl_aff_is_nan(res))
3510 ok = isl_aff_is_nan(aff1);
3511 else
3512 ok = isl_aff_plain_is_equal(aff1, res);
3513 isl_aff_free(aff1);
3514 isl_aff_free(res);
3515 if (ok < 0)
3516 return -1;
3517 if (!ok)
3518 isl_die(ctx, isl_error_unknown,
3519 "unexpected result", return -1);
3520 }
3521
3522 return 0;
3523 }
3524
3525 struct {
3526 __isl_give isl_union_pw_multi_aff *(*fn)(
3527 __isl_take isl_union_pw_multi_aff *upma1,
3528 __isl_take isl_union_pw_multi_aff *upma2);
3529 const char *arg1;
3530 const char *arg2;
3531 const char *res;
3532 } upma_bin_tests[] = {
3533 { &isl_union_pw_multi_aff_add, "{ A[] -> [0]; B[0] -> [1] }",
3534 "{ B[x] -> [2] : x >= 0 }", "{ B[0] -> [3] }" },
3535 { &isl_union_pw_multi_aff_union_add, "{ A[] -> [0]; B[0] -> [1] }",
3536 "{ B[x] -> [2] : x >= 0 }",
3537 "{ A[] -> [0]; B[0] -> [3]; B[x] -> [2] : x >= 1 }" },
3538 };
3539
3540 /* Perform some basic tests of binary operations on
3541 * isl_union_pw_multi_aff objects.
3542 */
3543 static int test_bin_upma(isl_ctx *ctx)
3544 {
3545 int i;
3546 isl_union_pw_multi_aff *upma1, *upma2, *res;
3547 int ok;
3548
3549 for (i = 0; i < ARRAY_SIZE(upma_bin_tests); ++i) {
3550 upma1 = isl_union_pw_multi_aff_read_from_str(ctx,
3551 upma_bin_tests[i].arg1);
3552 upma2 = isl_union_pw_multi_aff_read_from_str(ctx,
3553 upma_bin_tests[i].arg2);
3554 res = isl_union_pw_multi_aff_read_from_str(ctx,
3555 upma_bin_tests[i].res);
3556 upma1 = upma_bin_tests[i].fn(upma1, upma2);
3557 ok = isl_union_pw_multi_aff_plain_is_equal(upma1, res);
3558 isl_union_pw_multi_aff_free(upma1);
3559 isl_union_pw_multi_aff_free(res);
3560 if (ok < 0)
3561 return -1;
3562 if (!ok)
3563 isl_die(ctx, isl_error_unknown,
3564 "unexpected result", return -1);
3565 }
3566
3567 return 0;
3568 }
3569
3570 int test_aff(isl_ctx *ctx)
3571 {
3572 const char *str;
3573 isl_set *set;
3574 isl_space *space;
3575 isl_local_space *ls;
3576 isl_aff *aff;
3577 int zero, equal;
3578
3579 if (test_bin_aff(ctx) < 0)
3580 return -1;
3581 if (test_bin_upma(ctx) < 0)
3582 return -1;
3583
3584 space = isl_space_set_alloc(ctx, 0, 1);
3585 ls = isl_local_space_from_space(space);
3586 aff = isl_aff_zero_on_domain(ls);
3587
3588 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, 0, 1);
3589 aff = isl_aff_scale_down_ui(aff, 3);
3590 aff = isl_aff_floor(aff);
3591 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, 0, 1);
3592 aff = isl_aff_scale_down_ui(aff, 2);
3593 aff = isl_aff_floor(aff);
3594 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, 0, 1);
3595
3596 str = "{ [10] }";
3597 set = isl_set_read_from_str(ctx, str);
3598 aff = isl_aff_gist(aff, set);
3599
3600 aff = isl_aff_add_constant_si(aff, -16);
3601 zero = isl_aff_plain_is_zero(aff);
3602 isl_aff_free(aff);
3603
3604 if (zero < 0)
3605 return -1;
3606 if (!zero)
3607 isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
3608
3609 aff = isl_aff_read_from_str(ctx, "{ [-1] }");
3610 aff = isl_aff_scale_down_ui(aff, 64);
3611 aff = isl_aff_floor(aff);
3612 equal = aff_check_plain_equal(aff, "{ [-1] }");
3613 isl_aff_free(aff);
3614 if (equal < 0)
3615 return -1;
3616
3617 return 0;
3618 }
3619
3620 int test_dim_max(isl_ctx *ctx)
3621 {
3622 int equal;
3623 const char *str;
3624 isl_set *set1, *set2;
3625 isl_set *set;
3626 isl_map *map;
3627 isl_pw_aff *pwaff;
3628
3629 str = "[N] -> { [i] : 0 <= i <= min(N,10) }";
3630 set = isl_set_read_from_str(ctx, str);
3631 pwaff = isl_set_dim_max(set, 0);
3632 set1 = isl_set_from_pw_aff(pwaff);
3633 str = "[N] -> { [10] : N >= 10; [N] : N <= 9 and N >= 0 }";
3634 set2 = isl_set_read_from_str(ctx, str);
3635 equal = isl_set_is_equal(set1, set2);
3636 isl_set_free(set1);
3637 isl_set_free(set2);
3638 if (equal < 0)
3639 return -1;
3640 if (!equal)
3641 isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
3642
3643 str = "[N] -> { [i] : 0 <= i <= max(2N,N+6) }";
3644 set = isl_set_read_from_str(ctx, str);
3645 pwaff = isl_set_dim_max(set, 0);
3646 set1 = isl_set_from_pw_aff(pwaff);
3647 str = "[N] -> { [6 + N] : -6 <= N <= 5; [2N] : N >= 6 }";
3648 set2 = isl_set_read_from_str(ctx, str);
3649 equal = isl_set_is_equal(set1, set2);
3650 isl_set_free(set1);
3651 isl_set_free(set2);
3652 if (equal < 0)
3653 return -1;
3654 if (!equal)
3655 isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
3656
3657 str = "[N] -> { [i] : 0 <= i <= 2N or 0 <= i <= N+6 }";
3658 set = isl_set_read_from_str(ctx, str);
3659 pwaff = isl_set_dim_max(set, 0);
3660 set1 = isl_set_from_pw_aff(pwaff);
3661 str = "[N] -> { [6 + N] : -6 <= N <= 5; [2N] : N >= 6 }";
3662 set2 = isl_set_read_from_str(ctx, str);
3663 equal = isl_set_is_equal(set1, set2);
3664 isl_set_free(set1);
3665 isl_set_free(set2);
3666 if (equal < 0)
3667 return -1;
3668 if (!equal)
3669 isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
3670
3671 str = "[N,M] -> { [i,j] -> [([i/16]), i%16, ([j/16]), j%16] : "
3672 "0 <= i < N and 0 <= j < M }";
3673 map = isl_map_read_from_str(ctx, str);
3674 set = isl_map_range(map);
3675
3676 pwaff = isl_set_dim_max(isl_set_copy(set), 0);
3677 set1 = isl_set_from_pw_aff(pwaff);
3678 str = "[N,M] -> { [([(N-1)/16])] : M,N > 0 }";
3679 set2 = isl_set_read_from_str(ctx, str);
3680 equal = isl_set_is_equal(set1, set2);
3681 isl_set_free(set1);
3682 isl_set_free(set2);
3683
3684 pwaff = isl_set_dim_max(isl_set_copy(set), 3);
3685 set1 = isl_set_from_pw_aff(pwaff);
3686 str = "[N,M] -> { [t] : t = min(M-1,15) and M,N > 0 }";
3687 set2 = isl_set_read_from_str(ctx, str);
3688 if (equal >= 0 && equal)
3689 equal = isl_set_is_equal(set1, set2);
3690 isl_set_free(set1);
3691 isl_set_free(set2);
3692
3693 isl_set_free(set);
3694
3695 if (equal < 0)
3696 return -1;
3697 if (!equal)
3698 isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
3699
3700 /* Check that solutions are properly merged. */
3701 str = "[n] -> { [a, b, c] : c >= -4a - 2b and "
3702 "c <= -1 + n - 4a - 2b and c >= -2b and "
3703 "4a >= -4 + n and c >= 0 }";
3704 set = isl_set_read_from_str(ctx, str);
3705 pwaff = isl_set_dim_min(set, 2);
3706 set1 = isl_set_from_pw_aff(pwaff);
3707 str = "[n] -> { [(0)] : n >= 1 }";
3708 set2 = isl_set_read_from_str(ctx, str);
3709 equal = isl_set_is_equal(set1, set2);
3710 isl_set_free(set1);
3711 isl_set_free(set2);
3712
3713 if (equal < 0)
3714 return -1;
3715 if (!equal)
3716 isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
3717
3718 /* Check that empty solution lie in the right space. */
3719 str = "[n] -> { [t,a] : 1 = 0 }";
3720 set = isl_set_read_from_str(ctx, str);
3721 pwaff = isl_set_dim_max(set, 0);
3722 set1 = isl_set_from_pw_aff(pwaff);
3723 str = "[n] -> { [t] : 1 = 0 }";
3724 set2 = isl_set_read_from_str(ctx, str);
3725 equal = isl_set_is_equal(set1, set2);
3726 isl_set_free(set1);
3727 isl_set_free(set2);
3728
3729 if (equal < 0)
3730 return -1;
3731 if (!equal)
3732 isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
3733
3734 return 0;
3735 }
3736
3737 /* Is "pma" obviously equal to the isl_pw_multi_aff represented by "str"?
3738 */
3739 static int pw_multi_aff_plain_is_equal(__isl_keep isl_pw_multi_aff *pma,
3740 const char *str)
3741 {
3742 isl_ctx *ctx;
3743 isl_pw_multi_aff *pma2;
3744 int equal;
3745
3746 if (!pma)
3747 return -1;
3748
3749 ctx = isl_pw_multi_aff_get_ctx(pma);
3750 pma2 = isl_pw_multi_aff_read_from_str(ctx, str);
3751 equal = isl_pw_multi_aff_plain_is_equal(pma, pma2);
3752 isl_pw_multi_aff_free(pma2);
3753
3754 return equal;
3755 }
3756
3757 /* Check that "pma" is obviously equal to the isl_pw_multi_aff
3758 * represented by "str".
3759 */
3760 static int pw_multi_aff_check_plain_equal(__isl_keep isl_pw_multi_aff *pma,
3761 const char *str)
3762 {
3763 int equal;
3764
3765 equal = pw_multi_aff_plain_is_equal(pma, str);
3766 if (equal < 0)
3767 return -1;
3768 if (!equal)
3769 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_unknown,
3770 "result not as expected", return -1);
3771 return 0;
3772 }
3773
3774 /* Basic test for isl_pw_multi_aff_product.
3775 *
3776 * Check that multiple pieces are properly handled.
3777 */
3778 static int test_product_pma(isl_ctx *ctx)
3779 {
3780 int equal;
3781 const char *str;
3782 isl_pw_multi_aff *pma1, *pma2;
3783
3784 str = "{ A[i] -> B[1] : i < 0; A[i] -> B[2] : i >= 0 }";
3785 pma1 = isl_pw_multi_aff_read_from_str(ctx, str);
3786 str = "{ C[] -> D[] }";
3787 pma2 = isl_pw_multi_aff_read_from_str(ctx, str);
3788 pma1 = isl_pw_multi_aff_product(pma1, pma2);
3789 str = "{ [A[i] -> C[]] -> [B[(1)] -> D[]] : i < 0;"
3790 "[A[i] -> C[]] -> [B[(2)] -> D[]] : i >= 0 }";
3791 equal = pw_multi_aff_check_plain_equal(pma1, str);
3792 isl_pw_multi_aff_free(pma1);
3793 if (equal < 0)
3794 return -1;
3795
3796 return 0;
3797 }
3798
3799 int test_product(isl_ctx *ctx)
3800 {
3801 const char *str;
3802 isl_set *set;
3803 isl_union_set *uset1, *uset2;
3804 int ok;
3805
3806 str = "{ A[i] }";
3807 set = isl_set_read_from_str(ctx, str);
3808 set = isl_set_product(set, isl_set_copy(set));
3809 ok = isl_set_is_wrapping(set);
3810 isl_set_free(set);
3811 if (ok < 0)
3812 return -1;
3813 if (!ok)
3814 isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
3815
3816 str = "{ [] }";
3817 uset1 = isl_union_set_read_from_str(ctx, str);
3818 uset1 = isl_union_set_product(uset1, isl_union_set_copy(uset1));
3819 str = "{ [[] -> []] }";
3820 uset2 = isl_union_set_read_from_str(ctx, str);
3821 ok = isl_union_set_is_equal(uset1, uset2);
3822 isl_union_set_free(uset1);
3823 isl_union_set_free(uset2);
3824 if (ok < 0)
3825 return -1;
3826 if (!ok)
3827 isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
3828
3829 if (test_product_pma(ctx) < 0)
3830 return -1;
3831
3832 return 0;
3833 }
3834
3835 /* Check that two sets are not considered disjoint just because
3836 * they have a different set of (named) parameters.
3837 */
3838 static int test_disjoint(isl_ctx *ctx)
3839 {
3840 const char *str;
3841 isl_set *set, *set2;
3842 int disjoint;
3843
3844 str = "[n] -> { [[]->[]] }";
3845 set = isl_set_read_from_str(ctx, str);
3846 str = "{ [[]->[]] }";
3847 set2 = isl_set_read_from_str(ctx, str);
3848 disjoint = isl_set_is_disjoint(set, set2);
3849 isl_set_free(set);
3850 isl_set_free(set2);
3851 if (disjoint < 0)
3852 return -1;
3853 if (disjoint)
3854 isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
3855
3856 return 0;
3857 }
3858
3859 int test_equal(isl_ctx *ctx)
3860 {
3861 const char *str;
3862 isl_set *set, *set2;
3863 int equal;
3864
3865 str = "{ S_6[i] }";
3866 set = isl_set_read_from_str(ctx, str);
3867 str = "{ S_7[i] }";
3868 set2 = isl_set_read_from_str(ctx, str);
3869 equal = isl_set_is_equal(set, set2);
3870 isl_set_free(set);
3871 isl_set_free(set2);
3872 if (equal < 0)
3873 return -1;
3874 if (equal)
3875 isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
3876
3877 return 0;
3878 }
3879
3880 static int test_plain_fixed(isl_ctx *ctx, __isl_take isl_map *map,
3881 enum isl_dim_type type, unsigned pos, int fixed)
3882 {
3883 int test;
3884
3885 test = isl_map_plain_is_fixed(map, type, pos, NULL);
3886 isl_map_free(map);
3887 if (test < 0)
3888 return -1;
3889 if (test == fixed)
3890 return 0;
3891 if (fixed)
3892 isl_die(ctx, isl_error_unknown,
3893 "map not detected as fixed", return -1);
3894 else
3895 isl_die(ctx, isl_error_unknown,
3896 "map detected as fixed", return -1);
3897 }
3898
3899 int test_fixed(isl_ctx *ctx)
3900 {
3901 const char *str;
3902 isl_map *map;
3903
3904 str = "{ [i] -> [i] }";
3905 map = isl_map_read_from_str(ctx, str);
3906 if (test_plain_fixed(ctx, map, isl_dim_out, 0, 0))
3907 return -1;
3908 str = "{ [i] -> [1] }";
3909 map = isl_map_read_from_str(ctx, str);
3910 if (test_plain_fixed(ctx, map, isl_dim_out, 0, 1))
3911 return -1;
3912 str = "{ S_1[p1] -> [o0] : o0 = -2 and p1 >= 1 and p1 <= 7 }";
3913 map = isl_map_read_from_str(ctx, str);
3914 if (test_plain_fixed(ctx, map, isl_dim_out, 0, 1))
3915 return -1;
3916 map = isl_map_read_from_str(ctx, str);
3917 map = isl_map_neg(map);
3918 if (test_plain_fixed(ctx, map, isl_dim_out, 0, 1))
3919 return -1;
3920
3921 return 0;
3922 }
3923
3924 struct isl_vertices_test_data {
3925 const char *set;
3926 int n;
3927 const char *vertex[2];
3928 } vertices_tests[] = {
3929 { "{ A[t, i] : t = 12 and i >= 4 and i <= 12 }",
3930 2, { "{ A[12, 4] }", "{ A[12, 12] }" } },
3931 { "{ A[t, i] : t = 14 and i = 1 }",
3932 1, { "{ A[14, 1] }" } },
3933 };
3934
3935 /* Check that "vertex" corresponds to one of the vertices in data->vertex.
3936 */
3937 static int find_vertex(__isl_take isl_vertex *vertex, void *user)
3938 {
3939 struct isl_vertices_test_data *data = user;
3940 isl_ctx *ctx;
3941 isl_multi_aff *ma;
3942 isl_basic_set *bset;
3943 isl_pw_multi_aff *pma;
3944 int i;
3945 int equal;
3946
3947 ctx = isl_vertex_get_ctx(vertex);
3948 bset = isl_vertex_get_domain(vertex);
3949 ma = isl_vertex_get_expr(vertex);
3950 pma = isl_pw_multi_aff_alloc(isl_set_from_basic_set(bset), ma);
3951
3952 for (i = 0; i < data->n; ++i) {
3953 isl_pw_multi_aff *pma_i;
3954
3955 pma_i = isl_pw_multi_aff_read_from_str(ctx, data->vertex[i]);
3956 equal = isl_pw_multi_aff_plain_is_equal(pma, pma_i);
3957 isl_pw_multi_aff_free(pma_i);
3958
3959 if (equal < 0 || equal)
3960 break;
3961 }
3962
3963 isl_pw_multi_aff_free(pma);
3964 isl_vertex_free(vertex);
3965
3966 if (equal < 0)
3967 return -1;
3968
3969 return equal ? 0 : - 1;
3970 }
3971
3972 int test_vertices(isl_ctx *ctx)
3973 {
3974 int i;
3975
3976 for (i = 0; i < ARRAY_SIZE(vertices_tests); ++i) {
3977 isl_basic_set *bset;
3978 isl_vertices *vertices;
3979 int ok = 1;
3980 int n;
3981
3982 bset = isl_basic_set_read_from_str(ctx, vertices_tests[i].set);
3983 vertices = isl_basic_set_compute_vertices(bset);
3984 n = isl_vertices_get_n_vertices(vertices);
3985 if (vertices_tests[i].n != n)
3986 ok = 0;
3987 if (isl_vertices_foreach_vertex(vertices, &find_vertex,
3988 &vertices_tests[i]) < 0)
3989 ok = 0;
3990 isl_vertices_free(vertices);
3991 isl_basic_set_free(bset);
3992
3993 if (!vertices)
3994 return -1;
3995 if (!ok)
3996 isl_die(ctx, isl_error_unknown, "unexpected vertices",
3997 return -1);
3998 }
3999
4000 return 0;
4001 }
4002
4003 int test_union_pw(isl_ctx *ctx)
4004 {
4005 int equal;
4006 const char *str;
4007 isl_union_set *uset;
4008 isl_union_pw_qpolynomial *upwqp1, *upwqp2;
4009
4010 str = "{ [x] -> x^2 }";
4011 upwqp1 = isl_union_pw_qpolynomial_read_from_str(ctx, str);
4012 upwqp2 = isl_union_pw_qpolynomial_copy(upwqp1);
4013 uset = isl_union_pw_qpolynomial_domain(upwqp1);
4014 upwqp1 = isl_union_pw_qpolynomial_copy(upwqp2);
4015 upwqp1 = isl_union_pw_qpolynomial_intersect_domain(upwqp1, uset);
4016 equal = isl_union_pw_qpolynomial_plain_is_equal(upwqp1, upwqp2);
4017 isl_union_pw_qpolynomial_free(upwqp1);
4018 isl_union_pw_qpolynomial_free(upwqp2);
4019 if (equal < 0)
4020 return -1;
4021 if (!equal)
4022 isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
4023
4024 return 0;
4025 }
4026
4027 int test_output(isl_ctx *ctx)
4028 {
4029 char *s;
4030 const char *str;
4031 isl_pw_aff *pa;
4032 isl_printer *p;
4033 int equal;
4034
4035 str = "[x] -> { [1] : x % 4 <= 2; [2] : x = 3 }";
4036 pa = isl_pw_aff_read_from_str(ctx, str);
4037
4038 p = isl_printer_to_str(ctx);
4039 p = isl_printer_set_output_format(p, ISL_FORMAT_C);
4040 p = isl_printer_print_pw_aff(p, pa);
4041 s = isl_printer_get_str(p);
4042 isl_printer_free(p);
4043 isl_pw_aff_free(pa);
4044 if (!s)
4045 equal = -1;
4046 else
4047 equal = !strcmp(s, "4 * floord(x, 4) + 2 >= x ? 1 : 2");
4048 free(s);
4049 if (equal < 0)
4050 return -1;
4051 if (!equal)
4052 isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
4053
4054 return 0;
4055 }
4056
4057 int test_sample(isl_ctx *ctx)
4058 {
4059 const char *str;
4060 isl_basic_set *bset1, *bset2;
4061 int empty, subset;
4062
4063 str = "{ [a, b, c, d, e, f, g, h, i, j, k] : "
4064 "3i >= 1073741823b - c - 1073741823e + f and c >= 0 and "
4065 "3i >= -1 + 3221225466b + c + d - 3221225466e - f and "
4066 "2e >= a - b and 3e <= 2a and 3k <= -a and f <= -1 + a and "
4067 "3i <= 4 - a + 4b + 2c - e - 2f and 3k <= -a + c - f and "
4068 "3h >= -2 + a and 3g >= -3 - a and 3k >= -2 - a and "
4069 "3i >= -2 - a - 2c + 3e + 2f and 3h <= a + c - f and "
4070 "3h >= a + 2147483646b + 2c - 2147483646e - 2f and "
4071 "3g <= -1 - a and 3i <= 1 + c + d - f and a <= 1073741823 and "
4072 "f >= 1 - a + 1073741822b + c + d - 1073741822e and "
4073 "3i >= 1 + 2b - 2c + e + 2f + 3g and "
4074 "1073741822f <= 1073741822 - a + 1073741821b + 1073741822c +"
4075 "d - 1073741821e and "
4076 "3j <= 3 - a + 3b and 3g <= -2 - 2b + c + d - e - f and "
4077 "3j >= 1 - a + b + 2e and "
4078 "3f >= -3 + a + 3221225462b + 3c + d - 3221225465e and "
4079 "3i <= 4 - a + 4b - e and "
4080 "f <= 1073741822 + 1073741822b - 1073741822e and 3h <= a and "
4081 "f >= 0 and 2e <= 4 - a + 5b - d and 2e <= a - b + d and "
4082 "c <= -1 + a and 3i >= -2 - a + 3e and "
4083 "1073741822e <= 1073741823 - a + 1073741822b + c and "
4084 "3g >= -4 + 3221225464b + 3c + d - 3221225467e - 3f and "
4085 "3i >= -1 + 3221225466b + 3c + d - 3221225466e - 3f and "
4086 "1073741823e >= 1 + 1073741823b - d and "
4087 "3i >= 1073741823b + c - 1073741823e - f and "
4088 "3i >= 1 + 2b + e + 3g }";
4089 bset1 = isl_basic_set_read_from_str(ctx, str);
4090 bset2 = isl_basic_set_sample(isl_basic_set_copy(bset1));
4091 empty = isl_basic_set_is_empty(bset2);
4092 subset = isl_basic_set_is_subset(bset2, bset1);
4093 isl_basic_set_free(bset1);
4094 isl_basic_set_free(bset2);
4095 if (empty < 0 || subset < 0)
4096 return -1;
4097 if (empty)
4098 isl_die(ctx, isl_error_unknown, "point not found", return -1);
4099 if (!subset)
4100 isl_die(ctx, isl_error_unknown, "bad point found", return -1);
4101
4102 return 0;
4103 }
4104
4105 int test_fixed_power(isl_ctx *ctx)
4106 {
4107 const char *str;
4108 isl_map *map;
4109 isl_int exp;
4110 int equal;
4111
4112 isl_int_init(exp);
4113 str = "{ [i] -> [i + 1] }";
4114 map = isl_map_read_from_str(ctx, str);
4115 isl_int_set_si(exp, 23);
4116 map = isl_map_fixed_power(map, exp);
4117 equal = map_check_equal(map, "{ [i] -> [i + 23] }");
4118 isl_int_clear(exp);
4119 isl_map_free(map);
4120 if (equal < 0)
4121 return -1;
4122
4123 return 0;
4124 }
4125
4126 int test_slice(isl_ctx *ctx)
4127 {
4128 const char *str;
4129 isl_map *map;
4130 int equal;
4131
4132 str = "{ [i] -> [j] }";
4133 map = isl_map_read_from_str(ctx, str);
4134 map = isl_map_equate(map, isl_dim_in, 0, isl_dim_out, 0);
4135 equal = map_check_equal(map, "{ [i] -> [i] }");
4136 isl_map_free(map);
4137 if (equal < 0)
4138 return -1;
4139
4140 str = "{ [i] -> [j] }";
4141 map = isl_map_read_from_str(ctx, str);
4142 map = isl_map_equate(map, isl_dim_in, 0, isl_dim_in, 0);
4143 equal = map_check_equal(map, "{ [i] -> [j] }");
4144 isl_map_free(map);
4145 if (equal < 0)
4146 return -1;
4147
4148 str = "{ [i] -> [j] }";
4149 map = isl_map_read_from_str(ctx, str);
4150 map = isl_map_oppose(map, isl_dim_in, 0, isl_dim_out, 0);
4151 equal = map_check_equal(map, "{ [i] -> [-i] }");
4152 isl_map_free(map);
4153 if (equal < 0)
4154 return -1;
4155
4156 str = "{ [i] -> [j] }";
4157 map = isl_map_read_from_str(ctx, str);
4158 map = isl_map_oppose(map, isl_dim_in, 0, isl_dim_in, 0);
4159 equal = map_check_equal(map, "{ [0] -> [j] }");
4160 isl_map_free(map);
4161 if (equal < 0)
4162 return -1;
4163
4164 str = "{ [i] -> [j] }";
4165 map = isl_map_read_from_str(ctx, str);
4166 map = isl_map_order_gt(map, isl_dim_in, 0, isl_dim_out, 0);
4167 equal = map_check_equal(map, "{ [i] -> [j] : i > j }");
4168 isl_map_free(map);
4169 if (equal < 0)
4170 return -1;
4171
4172 str = "{ [i] -> [j] }";
4173 map = isl_map_read_from_str(ctx, str);
4174 map = isl_map_order_gt(map, isl_dim_in, 0, isl_dim_in, 0);
4175 equal = map_check_equal(map, "{ [i] -> [j] : false }");
4176 isl_map_free(map);
4177 if (equal < 0)
4178 return -1;
4179
4180 return 0;
4181 }
4182
4183 int test_eliminate(isl_ctx *ctx)
4184 {
4185 const char *str;
4186 isl_map *map;
4187 int equal;
4188
4189 str = "{ [i] -> [j] : i = 2j }";
4190 map = isl_map_read_from_str(ctx, str);
4191 map = isl_map_eliminate(map, isl_dim_out, 0, 1);
4192 equal = map_check_equal(map, "{ [i] -> [j] : exists a : i = 2a }");
4193 isl_map_free(map);
4194 if (equal < 0)
4195 return -1;
4196
4197 return 0;
4198 }
4199
4200 /* Check that isl_set_dim_residue_class detects that the values of j
4201 * in the set below are all odd and that it does not detect any spurious
4202 * strides.
4203 */
4204 static int test_residue_class(isl_ctx *ctx)
4205 {
4206 const char *str;
4207 isl_set *set;
4208 isl_int m, r;
4209 int res;
4210
4211 str = "{ [i,j] : j = 4 i + 1 and 0 <= i <= 100; "
4212 "[i,j] : j = 4 i + 3 and 500 <= i <= 600 }";
4213 set = isl_set_read_from_str(ctx, str);
4214 isl_int_init(m);
4215 isl_int_init(r);
4216 res = isl_set_dim_residue_class(set, 1, &m, &r);
4217 if (res >= 0 &&
4218 (isl_int_cmp_si(m, 2) != 0 || isl_int_cmp_si(r, 1) != 0))
4219 isl_die(ctx, isl_error_unknown, "incorrect residue class",
4220 res = -1);
4221 isl_int_clear(r);
4222 isl_int_clear(m);
4223 isl_set_free(set);
4224
4225 return res;
4226 }
4227
4228 int test_align_parameters(isl_ctx *ctx)
4229 {
4230 const char *str;
4231 isl_space *space;
4232 isl_multi_aff *ma1, *ma2;
4233 int equal;
4234
4235 str = "{ A[B[] -> C[]] -> D[E[] -> F[]] }";
4236 ma1 = isl_multi_aff_read_from_str(ctx, str);
4237
4238 space = isl_space_params_alloc(ctx, 1);
4239 space = isl_space_set_dim_name(space, isl_dim_param, 0, "N");
4240 ma1 = isl_multi_aff_align_params(ma1, space);
4241
4242 str = "[N] -> { A[B[] -> C[]] -> D[E[] -> F[]] }";
4243 ma2 = isl_multi_aff_read_from_str(ctx, str);
4244
4245 equal = isl_multi_aff_plain_is_equal(ma1, ma2);
4246
4247 isl_multi_aff_free(ma1);
4248 isl_multi_aff_free(ma2);
4249
4250 if (equal < 0)
4251 return -1;
4252 if (!equal)
4253 isl_die(ctx, isl_error_unknown,
4254 "result not as expected", return -1);
4255
4256 return 0;
4257 }
4258
4259 static int test_list(isl_ctx *ctx)
4260 {
4261 isl_id *a, *b, *c, *d, *id;
4262 isl_id_list *list;
4263 int ok;
4264
4265 a = isl_id_alloc(ctx, "a", NULL);
4266 b = isl_id_alloc(ctx, "b", NULL);
4267 c = isl_id_alloc(ctx, "c", NULL);
4268 d = isl_id_alloc(ctx, "d", NULL);
4269
4270 list = isl_id_list_alloc(ctx, 4);
4271 list = isl_id_list_add(list, a);
4272 list = isl_id_list_add(list, b);
4273 list = isl_id_list_add(list, c);
4274 list = isl_id_list_add(list, d);
4275 list = isl_id_list_drop(list, 1, 1);
4276
4277 if (isl_id_list_n_id(list) != 3) {
4278 isl_id_list_free(list);
4279 isl_die(ctx, isl_error_unknown,
4280 "unexpected number of elements in list", return -1);
4281 }
4282
4283 id = isl_id_list_get_id(list, 0);
4284 ok = id == a;
4285 isl_id_free(id);
4286 id = isl_id_list_get_id(list, 1);
4287 ok = ok && id == c;
4288 isl_id_free(id);
4289 id = isl_id_list_get_id(list, 2);
4290 ok = ok && id == d;
4291 isl_id_free(id);
4292
4293 isl_id_list_free(list);
4294
4295 if (!ok)
4296 isl_die(ctx, isl_error_unknown,
4297 "unexpected elements in list", return -1);
4298
4299 return 0;
4300 }
4301
4302 const char *set_conversion_tests[] = {
4303 "[N] -> { [i] : N - 1 <= 2 i <= N }",
4304 "[N] -> { [i] : exists a : i = 4 a and N - 1 <= i <= N }",
4305 "[N] -> { [i,j] : exists a : i = 4 a and N - 1 <= i, 2j <= N }",
4306 "[N] -> { [[i]->[j]] : exists a : i = 4 a and N - 1 <= i, 2j <= N }",
4307 "[N] -> { [3*floor(N/2) + 5*floor(N/3)] }",
4308 };
4309
4310 /* Check that converting from isl_set to isl_pw_multi_aff and back
4311 * to isl_set produces the original isl_set.
4312 */
4313 static int test_set_conversion(isl_ctx *ctx)
4314 {
4315 int i;
4316 const char *str;
4317 isl_set *set1, *set2;
4318 isl_pw_multi_aff *pma;
4319 int equal;
4320
4321 for (i = 0; i < ARRAY_SIZE(set_conversion_tests); ++i) {
4322 str = set_conversion_tests[i];
4323 set1 = isl_set_read_from_str(ctx, str);
4324 pma = isl_pw_multi_aff_from_set(isl_set_copy(set1));
4325 set2 = isl_set_from_pw_multi_aff(pma);
4326 equal = isl_set_is_equal(set1, set2);
4327 isl_set_free(set1);
4328 isl_set_free(set2);
4329
4330 if (equal < 0)
4331 return -1;
4332 if (!equal)
4333 isl_die(ctx, isl_error_unknown, "bad conversion",
4334 return -1);
4335 }
4336
4337 return 0;
4338 }
4339
4340 /* Check that converting from isl_map to isl_pw_multi_aff and back
4341 * to isl_map produces the original isl_map.
4342 */
4343 static int test_map_conversion(isl_ctx *ctx)
4344 {
4345 const char *str;
4346 isl_map *map1, *map2;
4347 isl_pw_multi_aff *pma;
4348 int equal;
4349
4350 str = "{ [a, b, c, d] -> s0[a, b, e, f] : "
4351 "exists (e0 = [(a - 2c)/3], e1 = [(-4 + b - 5d)/9], "
4352 "e2 = [(-d + f)/9]: 3e0 = a - 2c and 9e1 = -4 + b - 5d and "
4353 "9e2 = -d + f and f >= 0 and f <= 8 and 9e >= -5 - 2a and "
4354 "9e <= -2 - 2a) }";
4355 map1 = isl_map_read_from_str(ctx, str);
4356 pma = isl_pw_multi_aff_from_map(isl_map_copy(map1));
4357 map2 = isl_map_from_pw_multi_aff(pma);
4358 equal = isl_map_is_equal(map1, map2);
4359 isl_map_free(map1);
4360 isl_map_free(map2);
4361
4362 if (equal < 0)
4363 return -1;
4364 if (!equal)
4365 isl_die(ctx, isl_error_unknown, "bad conversion", return -1);
4366
4367 return 0;
4368 }
4369
4370 static int test_conversion(isl_ctx *ctx)
4371 {
4372 if (test_set_conversion(ctx) < 0)
4373 return -1;
4374 if (test_map_conversion(ctx) < 0)
4375 return -1;
4376 return 0;
4377 }
4378
4379 /* Check that isl_basic_map_curry does not modify input.
4380 */
4381 static int test_curry(isl_ctx *ctx)
4382 {
4383 const char *str;
4384 isl_basic_map *bmap1, *bmap2;
4385 int equal;
4386
4387 str = "{ [A[] -> B[]] -> C[] }";
4388 bmap1 = isl_basic_map_read_from_str(ctx, str);
4389 bmap2 = isl_basic_map_curry(isl_basic_map_copy(bmap1));
4390 equal = isl_basic_map_is_equal(bmap1, bmap2);
4391 isl_basic_map_free(bmap1);
4392 isl_basic_map_free(bmap2);
4393
4394 if (equal < 0)
4395 return -1;
4396 if (equal)
4397 isl_die(ctx, isl_error_unknown,
4398 "curried map should not be equal to original",
4399 return -1);
4400
4401 return 0;
4402 }
4403
4404 struct {
4405 const char *set;
4406 const char *ma;
4407 const char *res;
4408 } preimage_tests[] = {
4409 { "{ B[i,j] : 0 <= i < 10 and 0 <= j < 100 }",
4410 "{ A[j,i] -> B[i,j] }",
4411 "{ A[j,i] : 0 <= i < 10 and 0 <= j < 100 }" },
4412 { "{ rat: B[i,j] : 0 <= i, j and 3 i + 5 j <= 100 }",
4413 "{ A[a,b] -> B[a/2,b/6] }",
4414 "{ rat: A[a,b] : 0 <= a, b and 9 a + 5 b <= 600 }" },
4415 { "{ B[i,j] : 0 <= i, j and 3 i + 5 j <= 100 }",
4416 "{ A[a,b] -> B[a/2,b/6] }",
4417 "{ A[a,b] : 0 <= a, b and 9 a + 5 b <= 600 and "
4418 "exists i,j : a = 2 i and b = 6 j }" },
4419 { "[n] -> { S[i] : 0 <= i <= 100 }", "[n] -> { S[n] }",
4420 "[n] -> { : 0 <= n <= 100 }" },
4421 { "{ B[i] : 0 <= i < 100 and exists a : i = 4 a }",
4422 "{ A[a] -> B[2a] }",
4423 "{ A[a] : 0 <= a < 50 and exists b : a = 2 b }" },
4424 { "{ B[i] : 0 <= i < 100 and exists a : i = 4 a }",
4425 "{ A[a] -> B[([a/2])] }",
4426 "{ A[a] : 0 <= a < 200 and exists b : [a/2] = 4 b }" },
4427 { "{ B[i,j,k] : 0 <= i,j,k <= 100 }",
4428 "{ A[a] -> B[a,a,a/3] }",
4429 "{ A[a] : 0 <= a <= 100 and exists b : a = 3 b }" },
4430 { "{ B[i,j] : j = [(i)/2] } ", "{ A[i,j] -> B[i/3,j] }",
4431 "{ A[i,j] : j = [(i)/6] and exists a : i = 3 a }" },
4432 };
4433
4434 static int test_preimage_basic_set(isl_ctx *ctx)
4435 {
4436 int i;
4437 isl_basic_set *bset1, *bset2;
4438 isl_multi_aff *ma;
4439 int equal;
4440
4441 for (i = 0; i < ARRAY_SIZE(preimage_tests); ++i) {
4442 bset1 = isl_basic_set_read_from_str(ctx, preimage_tests[i].set);
4443 ma = isl_multi_aff_read_from_str(ctx, preimage_tests[i].ma);
4444 bset2 = isl_basic_set_read_from_str(ctx, preimage_tests[i].res);
4445 bset1 = isl_basic_set_preimage_multi_aff(bset1, ma);
4446 equal = isl_basic_set_is_equal(bset1, bset2);
4447 isl_basic_set_free(bset1);
4448 isl_basic_set_free(bset2);
4449 if (equal < 0)
4450 return -1;
4451 if (!equal)
4452 isl_die(ctx, isl_error_unknown, "bad preimage",
4453 return -1);
4454 }
4455
4456 return 0;
4457 }
4458
4459 struct {
4460 const char *map;
4461 const char *ma;
4462 const char *res;
4463 } preimage_domain_tests[] = {
4464 { "{ B[i,j] -> C[2i + 3j] : 0 <= i < 10 and 0 <= j < 100 }",
4465 "{ A[j,i] -> B[i,j] }",
4466 "{ A[j,i] -> C[2i + 3j] : 0 <= i < 10 and 0 <= j < 100 }" },
4467 { "{ B[i] -> C[i]; D[i] -> E[i] }",
4468 "{ A[i] -> B[i + 1] }",
4469 "{ A[i] -> C[i + 1] }" },
4470 { "{ B[i] -> C[i]; B[i] -> E[i] }",
4471 "{ A[i] -> B[i + 1] }",
4472 "{ A[i] -> C[i + 1]; A[i] -> E[i + 1] }" },
4473 { "{ B[i] -> C[([i/2])] }",
4474 "{ A[i] -> B[2i] }",
4475 "{ A[i] -> C[i] }" },
4476 { "{ B[i,j] -> C[([i/2]), ([(i+j)/3])] }",
4477 "{ A[i] -> B[([i/5]), ([i/7])] }",
4478 "{ A[i] -> C[([([i/5])/2]), ([(([i/5])+([i/7]))/3])] }" },
4479 { "[N] -> { B[i] -> C[([N/2]), i, ([N/3])] }",
4480 "[N] -> { A[] -> B[([N/5])] }",
4481 "[N] -> { A[] -> C[([N/2]), ([N/5]), ([N/3])] }" },
4482 { "{ B[i] -> C[i] : exists a : i = 5 a }",
4483 "{ A[i] -> B[2i] }",
4484 "{ A[i] -> C[2i] : exists a : 2i = 5 a }" },
4485 { "{ B[i] -> C[i] : exists a : i = 2 a; "
4486 "B[i] -> D[i] : exists a : i = 2 a + 1 }",
4487 "{ A[i] -> B[2i] }",
4488 "{ A[i] -> C[2i] }" },
4489 };
4490
4491 static int test_preimage_union_map(isl_ctx *ctx)
4492 {
4493 int i;
4494 isl_union_map *umap1, *umap2;
4495 isl_multi_aff *ma;
4496 int equal;
4497
4498 for (i = 0; i < ARRAY_SIZE(preimage_domain_tests); ++i) {
4499 umap1 = isl_union_map_read_from_str(ctx,
4500 preimage_domain_tests[i].map);
4501 ma = isl_multi_aff_read_from_str(ctx,
4502 preimage_domain_tests[i].ma);
4503 umap2 = isl_union_map_read_from_str(ctx,
4504 preimage_domain_tests[i].res);
4505 umap1 = isl_union_map_preimage_domain_multi_aff(umap1, ma);
4506 equal = isl_union_map_is_equal(umap1, umap2);
4507 isl_union_map_free(umap1);
4508 isl_union_map_free(umap2);
4509 if (equal < 0)
4510 return -1;
4511 if (!equal)
4512 isl_die(ctx, isl_error_unknown, "bad preimage",
4513 return -1);
4514 }
4515
4516 return 0;
4517 }
4518
4519 static int test_preimage(isl_ctx *ctx)
4520 {
4521 if (test_preimage_basic_set(ctx) < 0)
4522 return -1;
4523 if (test_preimage_union_map(ctx) < 0)
4524 return -1;
4525
4526 return 0;
4527 }
4528
4529 struct {
4530 const char *ma1;
4531 const char *ma;
4532 const char *res;
4533 } pullback_tests[] = {
4534 { "{ B[i,j] -> C[i + 2j] }" , "{ A[a,b] -> B[b,a] }",
4535 "{ A[a,b] -> C[b + 2a] }" },
4536 { "{ B[i] -> C[2i] }", "{ A[a] -> B[(a)/2] }", "{ A[a] -> C[a] }" },
4537 { "{ B[i] -> C[(i)/2] }", "{ A[a] -> B[2a] }", "{ A[a] -> C[a] }" },
4538 { "{ B[i] -> C[(i)/2] }", "{ A[a] -> B[(a)/3] }",
4539 "{ A[a] -> C[(a)/6] }" },
4540 { "{ B[i] -> C[2i] }", "{ A[a] -> B[5a] }", "{ A[a] -> C[10a] }" },
4541 { "{ B[i] -> C[2i] }", "{ A[a] -> B[(a)/3] }",
4542 "{ A[a] -> C[(2a)/3] }" },
4543 { "{ B[i,j] -> C[i + j] }", "{ A[a] -> B[a,a] }", "{ A[a] -> C[2a] }"},
4544 { "{ B[a] -> C[a,a] }", "{ A[i,j] -> B[i + j] }",
4545 "{ A[i,j] -> C[i + j, i + j] }"},
4546 { "{ B[i] -> C[([i/2])] }", "{ B[5] }", "{ C[2] }" },
4547 { "[n] -> { B[i,j] -> C[([i/2]) + 2j] }",
4548 "[n] -> { B[n,[n/3]] }", "[n] -> { C[([n/2]) + 2*[n/3]] }", },
4549 { "{ [i, j] -> [floor((i)/4) + floor((2*i+j)/5)] }",
4550 "{ [i, j] -> [floor((i)/3), j] }",
4551 "{ [i, j] -> [(floor((i)/12) + floor((j + 2*floor((i)/3))/5))] }" },
4552 };
4553
4554 static int test_pullback(isl_ctx *ctx)
4555 {
4556 int i;
4557 isl_multi_aff *ma1, *ma2;
4558 isl_multi_aff *ma;
4559 int equal;
4560
4561 for (i = 0; i < ARRAY_SIZE(pullback_tests); ++i) {
4562 ma1 = isl_multi_aff_read_from_str(ctx, pullback_tests[i].ma1);
4563 ma = isl_multi_aff_read_from_str(ctx, pullback_tests[i].ma);
4564 ma2 = isl_multi_aff_read_from_str(ctx, pullback_tests[i].res);
4565 ma1 = isl_multi_aff_pullback_multi_aff(ma1, ma);
4566 equal = isl_multi_aff_plain_is_equal(ma1, ma2);
4567 isl_multi_aff_free(ma1);
4568 isl_multi_aff_free(ma2);
4569 if (equal < 0)
4570 return -1;
4571 if (!equal)
4572 isl_die(ctx, isl_error_unknown, "bad pullback",
4573 return -1);
4574 }
4575
4576 return 0;
4577 }
4578
4579 /* Check that negation is printed correctly and that equal expressions
4580 * are correctly identified.
4581 */
4582 static int test_ast(isl_ctx *ctx)
4583 {
4584 isl_ast_expr *expr, *expr1, *expr2, *expr3;
4585 char *str;
4586 int ok, equal;
4587
4588 expr1 = isl_ast_expr_from_id(isl_id_alloc(ctx, "A", NULL));
4589 expr2 = isl_ast_expr_from_id(isl_id_alloc(ctx, "B", NULL));
4590 expr = isl_ast_expr_add(expr1, expr2);
4591 expr2 = isl_ast_expr_copy(expr);
4592 expr = isl_ast_expr_neg(expr);
4593 expr2 = isl_ast_expr_neg(expr2);
4594 equal = isl_ast_expr_is_equal(expr, expr2);
4595 str = isl_ast_expr_to_str(expr);
4596 ok = str ? !strcmp(str, "-(A + B)") : -1;
4597 free(str);
4598 isl_ast_expr_free(expr);
4599 isl_ast_expr_free(expr2);
4600
4601 if (ok < 0 || equal < 0)
4602 return -1;
4603 if (!equal)
4604 isl_die(ctx, isl_error_unknown,
4605 "equal expressions not considered equal", return -1);
4606 if (!ok)
4607 isl_die(ctx, isl_error_unknown,
4608 "isl_ast_expr printed incorrectly", return -1);
4609
4610 expr1 = isl_ast_expr_from_id(isl_id_alloc(ctx, "A", NULL));
4611 expr2 = isl_ast_expr_from_id(isl_id_alloc(ctx, "B", NULL));
4612 expr = isl_ast_expr_add(expr1, expr2);
4613 expr3 = isl_ast_expr_from_id(isl_id_alloc(ctx, "C", NULL));
4614 expr = isl_ast_expr_sub(expr3, expr);
4615 str = isl_ast_expr_to_str(expr);
4616 ok = str ? !strcmp(str, "C - (A + B)") : -1;
4617 free(str);
4618 isl_ast_expr_free(expr);
4619
4620 if (ok < 0)
4621 return -1;
4622 if (!ok)
4623 isl_die(ctx, isl_error_unknown,
4624 "isl_ast_expr printed incorrectly", return -1);
4625
4626 return 0;
4627 }
4628
4629 /* Check that isl_ast_build_expr_from_set returns a valid expression
4630 * for an empty set. Note that isl_ast_build_expr_from_set getting
4631 * called on an empty set probably indicates a bug in the caller.
4632 */
4633 static int test_ast_build(isl_ctx *ctx)
4634 {
4635 isl_set *set;
4636 isl_ast_build *build;
4637 isl_ast_expr *expr;
4638
4639 set = isl_set_universe(isl_space_params_alloc(ctx, 0));
4640 build = isl_ast_build_from_context(set);
4641
4642 set = isl_set_empty(isl_space_params_alloc(ctx, 0));
4643 expr = isl_ast_build_expr_from_set(build, set);
4644
4645 isl_ast_expr_free(expr);
4646 isl_ast_build_free(build);
4647
4648 if (!expr)
4649 return -1;
4650
4651 return 0;
4652 }
4653
4654 /* Internal data structure for before_for and after_for callbacks.
4655 *
4656 * depth is the current depth
4657 * before is the number of times before_for has been called
4658 * after is the number of times after_for has been called
4659 */
4660 struct isl_test_codegen_data {
4661 int depth;
4662 int before;
4663 int after;
4664 };
4665
4666 /* This function is called before each for loop in the AST generated
4667 * from test_ast_gen1.
4668 *
4669 * Increment the number of calls and the depth.
4670 * Check that the space returned by isl_ast_build_get_schedule_space
4671 * matches the target space of the schedule returned by
4672 * isl_ast_build_get_schedule.
4673 * Return an isl_id that is checked by the corresponding call
4674 * to after_for.
4675 */
4676 static __isl_give isl_id *before_for(__isl_keep isl_ast_build *build,
4677 void *user)
4678 {
4679 struct isl_test_codegen_data *data = user;
4680 isl_ctx *ctx;
4681 isl_space *space;
4682 isl_union_map *schedule;
4683 isl_union_set *uset;
4684 isl_set *set;
4685 int empty;
4686 char name[] = "d0";
4687
4688 ctx = isl_ast_build_get_ctx(build);
4689
4690 if (data->before >= 3)
4691 isl_die(ctx, isl_error_unknown,
4692 "unexpected number of for nodes", return NULL);
4693 if (data->depth >= 2)
4694 isl_die(ctx, isl_error_unknown,
4695 "unexpected depth", return NULL);
4696
4697 snprintf(name, sizeof(name), "d%d", data->depth);
4698 data->before++;
4699 data->depth++;
4700
4701 schedule = isl_ast_build_get_schedule(build);
4702 uset = isl_union_map_range(schedule);
4703 if (!uset)
4704 return NULL;
4705 if (isl_union_set_n_set(uset) != 1) {
4706 isl_union_set_free(uset);
4707 isl_die(ctx, isl_error_unknown,
4708 "expecting single range space", return NULL);
4709 }
4710
4711 space = isl_ast_build_get_schedule_space(build);
4712 set = isl_union_set_extract_set(uset, space);
4713 isl_union_set_free(uset);
4714 empty = isl_set_is_empty(set);
4715 isl_set_free(set);
4716
4717 if (empty < 0)
4718 return NULL;
4719 if (empty)
4720 isl_die(ctx, isl_error_unknown,
4721 "spaces don't match", return NULL);
4722
4723 return isl_id_alloc(ctx, name, NULL);
4724 }
4725
4726 /* This function is called after each for loop in the AST generated
4727 * from test_ast_gen1.
4728 *
4729 * Increment the number of calls and decrement the depth.
4730 * Check that the annotation attached to the node matches
4731 * the isl_id returned by the corresponding call to before_for.
4732 */
4733 static __isl_give isl_ast_node *after_for(__isl_take isl_ast_node *node,
4734 __isl_keep isl_ast_build *build, void *user)
4735 {
4736 struct isl_test_codegen_data *data = user;
4737 isl_id *id;
4738 const char *name;
4739 int valid;
4740
4741 data->after++;
4742 data->depth--;
4743
4744 if (data->after > data->before)
4745 isl_die(isl_ast_node_get_ctx(node), isl_error_unknown,
4746 "mismatch in number of for nodes",
4747 return isl_ast_node_free(node));
4748
4749 id = isl_ast_node_get_annotation(node);
4750 if (!id)
4751 isl_die(isl_ast_node_get_ctx(node), isl_error_unknown,
4752 "missing annotation", return isl_ast_node_free(node));
4753
4754 name = isl_id_get_name(id);
4755 valid = name && atoi(name + 1) == data->depth;
4756 isl_id_free(id);
4757
4758 if (!valid)
4759 isl_die(isl_ast_node_get_ctx(node), isl_error_unknown,
4760 "wrong annotation", return isl_ast_node_free(node));
4761
4762 return node;
4763 }
4764
4765 /* Check that the before_each_for and after_each_for callbacks
4766 * are called for each for loop in the generated code,
4767 * that they are called in the right order and that the isl_id
4768 * returned from the before_each_for callback is attached to
4769 * the isl_ast_node passed to the corresponding after_each_for call.
4770 */
4771 static int test_ast_gen1(isl_ctx *ctx)
4772 {
4773 const char *str;
4774 isl_set *set;
4775 isl_union_map *schedule;
4776 isl_ast_build *build;
4777 isl_ast_node *tree;
4778 struct isl_test_codegen_data data;
4779
4780 str = "[N] -> { : N >= 10 }";
4781 set = isl_set_read_from_str(ctx, str);
4782 str = "[N] -> { A[i,j] -> S[8,i,3,j] : 0 <= i,j <= N; "
4783 "B[i,j] -> S[8,j,9,i] : 0 <= i,j <= N }";
4784 schedule = isl_union_map_read_from_str(ctx, str);
4785
4786 data.before = 0;
4787 data.after = 0;
4788 data.depth = 0;
4789 build = isl_ast_build_from_context(set);
4790 build = isl_ast_build_set_before_each_for(build,
4791 &before_for, &data);
4792 build = isl_ast_build_set_after_each_for(build,
4793 &after_for, &data);
4794 tree = isl_ast_build_ast_from_schedule(build, schedule);
4795 isl_ast_build_free(build);
4796 if (!tree)
4797 return -1;
4798
4799 isl_ast_node_free(tree);
4800
4801 if (data.before != 3 || data.after != 3)
4802 isl_die(ctx, isl_error_unknown,
4803 "unexpected number of for nodes", return -1);
4804
4805 return 0;
4806 }
4807
4808 /* Check that the AST generator handles domains that are integrally disjoint
4809 * but not ratinoally disjoint.
4810 */
4811 static int test_ast_gen2(isl_ctx *ctx)
4812 {
4813 const char *str;
4814 isl_set *set;
4815 isl_union_map *schedule;
4816 isl_union_map *options;
4817 isl_ast_build *build;
4818 isl_ast_node *tree;
4819
4820 str = "{ A[i,j] -> [i,j] : 0 <= i,j <= 1 }";
4821 schedule = isl_union_map_read_from_str(ctx, str);
4822 set = isl_set_universe(isl_space_params_alloc(ctx, 0));
4823 build = isl_ast_build_from_context(set);
4824
4825 str = "{ [i,j] -> atomic[1] : i + j = 1; [i,j] -> unroll[1] : i = j }";
4826 options = isl_union_map_read_from_str(ctx, str);
4827 build = isl_ast_build_set_options(build, options);
4828 tree = isl_ast_build_ast_from_schedule(build, schedule);
4829 isl_ast_build_free(build);
4830 if (!tree)
4831 return -1;
4832 isl_ast_node_free(tree);
4833
4834 return 0;
4835 }
4836
4837 /* Increment *user on each call.
4838 */
4839 static __isl_give isl_ast_node *count_domains(__isl_take isl_ast_node *node,
4840 __isl_keep isl_ast_build *build, void *user)
4841 {
4842 int *n = user;
4843
4844 (*n)++;
4845
4846 return node;
4847 }
4848
4849 /* Test that unrolling tries to minimize the number of instances.
4850 * In particular, for the schedule given below, make sure it generates
4851 * 3 nodes (rather than 101).
4852 */
4853 static int test_ast_gen3(isl_ctx *ctx)
4854 {
4855 const char *str;
4856 isl_set *set;
4857 isl_union_map *schedule;
4858 isl_union_map *options;
4859 isl_ast_build *build;
4860 isl_ast_node *tree;
4861 int n_domain = 0;
4862
4863 str = "[n] -> { A[i] -> [i] : 0 <= i <= 100 and n <= i <= n + 2 }";
4864 schedule = isl_union_map_read_from_str(ctx, str);
4865 set = isl_set_universe(isl_space_params_alloc(ctx, 0));
4866
4867 str = "{ [i] -> unroll[0] }";
4868 options = isl_union_map_read_from_str(ctx, str);
4869
4870 build = isl_ast_build_from_context(set);
4871 build = isl_ast_build_set_options(build, options);
4872 build = isl_ast_build_set_at_each_domain(build,
4873 &count_domains, &n_domain);
4874 tree = isl_ast_build_ast_from_schedule(build, schedule);
4875 isl_ast_build_free(build);
4876 if (!tree)
4877 return -1;
4878
4879 isl_ast_node_free(tree);
4880
4881 if (n_domain != 3)
4882 isl_die(ctx, isl_error_unknown,
4883 "unexpected number of for nodes", return -1);
4884
4885 return 0;
4886 }
4887
4888 /* Check that if the ast_build_exploit_nested_bounds options is set,
4889 * we do not get an outer if node in the generated AST,
4890 * while we do get such an outer if node if the options is not set.
4891 */
4892 static int test_ast_gen4(isl_ctx *ctx)
4893 {
4894 const char *str;
4895 isl_set *set;
4896 isl_union_map *schedule;
4897 isl_ast_build *build;
4898 isl_ast_node *tree;
4899 enum isl_ast_node_type type;
4900 int enb;
4901
4902 enb = isl_options_get_ast_build_exploit_nested_bounds(ctx);
4903 str = "[N,M] -> { A[i,j] -> [i,j] : 0 <= i <= N and 0 <= j <= M }";
4904
4905 isl_options_set_ast_build_exploit_nested_bounds(ctx, 1);
4906
4907 schedule = isl_union_map_read_from_str(ctx, str);
4908 set = isl_set_universe(isl_space_params_alloc(ctx, 0));
4909 build = isl_ast_build_from_context(set);
4910 tree = isl_ast_build_ast_from_schedule(build, schedule);
4911 isl_ast_build_free(build);
4912 if (!tree)
4913 return -1;
4914
4915 type = isl_ast_node_get_type(tree);
4916 isl_ast_node_free(tree);
4917
4918 if (type == isl_ast_node_if)
4919 isl_die(ctx, isl_error_unknown,
4920 "not expecting if node", return -1);
4921
4922 isl_options_set_ast_build_exploit_nested_bounds(ctx, 0);
4923
4924 schedule = isl_union_map_read_from_str(ctx, str);
4925 set = isl_set_universe(isl_space_params_alloc(ctx, 0));
4926 build = isl_ast_build_from_context(set);
4927 tree = isl_ast_build_ast_from_schedule(build, schedule);
4928 isl_ast_build_free(build);
4929 if (!tree)
4930 return -1;
4931
4932 type = isl_ast_node_get_type(tree);
4933 isl_ast_node_free(tree);
4934
4935 if (type != isl_ast_node_if)
4936 isl_die(ctx, isl_error_unknown,
4937 "expecting if node", return -1);
4938
4939 isl_options_set_ast_build_exploit_nested_bounds(ctx, enb);
4940
4941 return 0;
4942 }
4943
4944 /* This function is called for each leaf in the AST generated
4945 * from test_ast_gen5.
4946 *
4947 * We finalize the AST generation by extending the outer schedule
4948 * with a zero-dimensional schedule. If this results in any for loops,
4949 * then this means that we did not pass along enough information
4950 * about the outer schedule to the inner AST generation.
4951 */
4952 static __isl_give isl_ast_node *create_leaf(__isl_take isl_ast_build *build,
4953 void *user)
4954 {
4955 isl_union_map *schedule, *extra;
4956 isl_ast_node *tree;
4957
4958 schedule = isl_ast_build_get_schedule(build);
4959 extra = isl_union_map_copy(schedule);
4960 extra = isl_union_map_from_domain(isl_union_map_domain(extra));
4961 schedule = isl_union_map_range_product(schedule, extra);
4962 tree = isl_ast_build_ast_from_schedule(build, schedule);
4963 isl_ast_build_free(build);
4964
4965 if (!tree)
4966 return NULL;
4967
4968 if (isl_ast_node_get_type(tree) == isl_ast_node_for)
4969 isl_die(isl_ast_node_get_ctx(tree), isl_error_unknown,
4970 "code should not contain any for loop",
4971 return isl_ast_node_free(tree));
4972
4973 return tree;
4974 }
4975
4976 /* Check that we do not lose any information when going back and
4977 * forth between internal and external schedule.
4978 *
4979 * In particular, we create an AST where we unroll the only
4980 * non-constant dimension in the schedule. We therefore do
4981 * not expect any for loops in the AST. However, older versions
4982 * of isl would not pass along enough information about the outer
4983 * schedule when performing an inner code generation from a create_leaf
4984 * callback, resulting in the inner code generation producing a for loop.
4985 */
4986 static int test_ast_gen5(isl_ctx *ctx)
4987 {
4988 const char *str;
4989 isl_set *set;
4990 isl_union_map *schedule, *options;
4991 isl_ast_build *build;
4992 isl_ast_node *tree;
4993
4994 str = "{ A[] -> [1, 1, 2]; B[i] -> [1, i, 0] : i >= 1 and i <= 2 }";
4995 schedule = isl_union_map_read_from_str(ctx, str);
4996
4997 str = "{ [a, b, c] -> unroll[1] : exists (e0 = [(a)/4]: "
4998 "4e0 >= -1 + a - b and 4e0 <= -2 + a + b) }";
4999 options = isl_union_map_read_from_str(ctx, str);
5000
5001 set = isl_set_universe(isl_space_params_alloc(ctx, 0));
5002 build = isl_ast_build_from_context(set);
5003 build = isl_ast_build_set_options(build, options);
5004 build = isl_ast_build_set_create_leaf(build, &create_leaf, NULL);
5005 tree = isl_ast_build_ast_from_schedule(build, schedule);
5006 isl_ast_build_free(build);
5007 isl_ast_node_free(tree);
5008 if (!tree)
5009 return -1;
5010
5011 return 0;
5012 }
5013
5014 static int test_ast_gen(isl_ctx *ctx)
5015 {
5016 if (test_ast_gen1(ctx) < 0)
5017 return -1;
5018 if (test_ast_gen2(ctx) < 0)
5019 return -1;
5020 if (test_ast_gen3(ctx) < 0)
5021 return -1;
5022 if (test_ast_gen4(ctx) < 0)
5023 return -1;
5024 if (test_ast_gen5(ctx) < 0)
5025 return -1;
5026 return 0;
5027 }
5028
5029 /* Check if dropping output dimensions from an isl_pw_multi_aff
5030 * works properly.
5031 */
5032 static int test_pw_multi_aff(isl_ctx *ctx)
5033 {
5034 const char *str;
5035 isl_pw_multi_aff *pma1, *pma2;
5036 int equal;
5037
5038 str = "{ [i,j] -> [i+j, 4i-j] }";
5039 pma1 = isl_pw_multi_aff_read_from_str(ctx, str);
5040 str = "{ [i,j] -> [4i-j] }";
5041 pma2 = isl_pw_multi_aff_read_from_str(ctx, str);
5042
5043 pma1 = isl_pw_multi_aff_drop_dims(pma1, isl_dim_out, 0, 1);
5044
5045 equal = isl_pw_multi_aff_plain_is_equal(pma1, pma2);
5046
5047 isl_pw_multi_aff_free(pma1);
5048 isl_pw_multi_aff_free(pma2);
5049 if (equal < 0)
5050 return -1;
5051 if (!equal)
5052 isl_die(ctx, isl_error_unknown,
5053 "expressions not equal", return -1);
5054
5055 return 0;
5056 }
5057
5058 /* Check that we can properly parse multi piecewise affine expressions
5059 * where the piecewise affine expressions have different domains.
5060 */
5061 static int test_multi_pw_aff(isl_ctx *ctx)
5062 {
5063 const char *str;
5064 isl_set *dom, *dom2;
5065 isl_multi_pw_aff *mpa1, *mpa2;
5066 isl_pw_aff *pa;
5067 int equal;
5068 int equal_domain;
5069
5070 mpa1 = isl_multi_pw_aff_read_from_str(ctx, "{ [i] -> [i] }");
5071 dom = isl_set_read_from_str(ctx, "{ [i] : i > 0 }");
5072 mpa1 = isl_multi_pw_aff_intersect_domain(mpa1, dom);
5073 mpa2 = isl_multi_pw_aff_read_from_str(ctx, "{ [i] -> [2i] }");
5074 mpa2 = isl_multi_pw_aff_flat_range_product(mpa1, mpa2);
5075 str = "{ [i] -> [(i : i > 0), 2i] }";
5076 mpa1 = isl_multi_pw_aff_read_from_str(ctx, str);
5077
5078 equal = isl_multi_pw_aff_plain_is_equal(mpa1, mpa2);
5079
5080 pa = isl_multi_pw_aff_get_pw_aff(mpa1, 0);
5081 dom = isl_pw_aff_domain(pa);
5082 pa = isl_multi_pw_aff_get_pw_aff(mpa1, 1);
5083 dom2 = isl_pw_aff_domain(pa);
5084 equal_domain = isl_set_is_equal(dom, dom2);
5085
5086 isl_set_free(dom);
5087 isl_set_free(dom2);
5088 isl_multi_pw_aff_free(mpa1);
5089 isl_multi_pw_aff_free(mpa2);
5090
5091 if (equal < 0)
5092 return -1;
5093 if (!equal)
5094 isl_die(ctx, isl_error_unknown,
5095 "expressions not equal", return -1);
5096
5097 if (equal_domain < 0)
5098 return -1;
5099 if (equal_domain)
5100 isl_die(ctx, isl_error_unknown,
5101 "domains unexpectedly equal", return -1);
5102
5103 return 0;
5104 }
5105
5106 /* This is a regression test for a bug where isl_basic_map_simplify
5107 * would end up in an infinite loop. In particular, we construct
5108 * an empty basic set that is not obviously empty.
5109 * isl_basic_set_is_empty marks the basic set as empty.
5110 * After projecting out i3, the variable can be dropped completely,
5111 * but isl_basic_map_simplify refrains from doing so if the basic set
5112 * is empty and would end up in an infinite loop if it didn't test
5113 * explicitly for empty basic maps in the outer loop.
5114 */
5115 static int test_simplify(isl_ctx *ctx)
5116 {
5117 const char *str;
5118 isl_basic_set *bset;
5119 int empty;
5120
5121 str = "{ [i0, i1, i2, i3] : i0 >= -2 and 6i2 <= 4 + i0 + 5i1 and "
5122 "i2 <= 22 and 75i2 <= 111 + 13i0 + 60i1 and "
5123 "25i2 >= 38 + 6i0 + 20i1 and i0 <= -1 and i2 >= 20 and "
5124 "i3 >= i2 }";
5125 bset = isl_basic_set_read_from_str(ctx, str);
5126 empty = isl_basic_set_is_empty(bset);
5127 bset = isl_basic_set_project_out(bset, isl_dim_set, 3, 1);
5128 isl_basic_set_free(bset);
5129 if (!bset)
5130 return -1;
5131 if (!empty)
5132 isl_die(ctx, isl_error_unknown,
5133 "basic set should be empty", return -1);
5134
5135 return 0;
5136 }
5137
5138 /* This is a regression test for a bug where isl_tab_basic_map_partial_lexopt
5139 * with gbr context would fail to disable the use of the shifted tableau
5140 * when transferring equalities for the input to the context, resulting
5141 * in invalid sample values.
5142 */
5143 static int test_partial_lexmin(isl_ctx *ctx)
5144 {
5145 const char *str;
5146 isl_basic_set *bset;
5147 isl_basic_map *bmap;
5148 isl_map *map;
5149
5150 str = "{ [1, b, c, 1 - c] -> [e] : 2e <= -c and 2e >= -3 + c }";
5151 bmap = isl_basic_map_read_from_str(ctx, str);
5152 str = "{ [a, b, c, d] : c <= 1 and 2d >= 6 - 4b - c }";
5153 bset = isl_basic_set_read_from_str(ctx, str);
5154 map = isl_basic_map_partial_lexmin(bmap, bset, NULL);
5155 isl_map_free(map);
5156
5157 if (!map)
5158 return -1;
5159
5160 return 0;
5161 }
5162
5163 /* Check that the variable compression performed on the existentially
5164 * quantified variables inside isl_basic_set_compute_divs is not confused
5165 * by the implicit equalities among the parameters.
5166 */
5167 static int test_compute_divs(isl_ctx *ctx)
5168 {
5169 const char *str;
5170 isl_basic_set *bset;
5171 isl_set *set;
5172
5173 str = "[a, b, c, d, e] -> { [] : exists (e0: 2d = b and a <= 124 and "
5174 "b <= 2046 and b >= 0 and b <= 60 + 64a and 2e >= b + 2c and "
5175 "2e >= b and 2e <= 1 + b and 2e <= 1 + b + 2c and "
5176 "32768e0 >= -124 + a and 2097152e0 <= 60 + 64a - b) }";
5177 bset = isl_basic_set_read_from_str(ctx, str);
5178 set = isl_basic_set_compute_divs(bset);
5179 isl_set_free(set);
5180 if (!set)
5181 return -1;
5182
5183 return 0;
5184 }
5185
5186 struct {
5187 const char *set;
5188 const char *dual;
5189 } coef_tests[] = {
5190 { "{ rat: [i] : 0 <= i <= 10 }",
5191 "{ rat: coefficients[[cst] -> [a]] : cst >= 0 and 10a + cst >= 0 }" },
5192 { "{ rat: [i] : FALSE }",
5193 "{ rat: coefficients[[cst] -> [a]] }" },
5194 { "{ rat: [i] : }",
5195 "{ rat: coefficients[[cst] -> [0]] : cst >= 0 }" },
5196 };
5197
5198 struct {
5199 const char *set;
5200 const char *dual;
5201 } sol_tests[] = {
5202 { "{ rat: coefficients[[cst] -> [a]] : cst >= 0 and 10a + cst >= 0 }",
5203 "{ rat: [i] : 0 <= i <= 10 }" },
5204 { "{ rat: coefficients[[cst] -> [a]] : FALSE }",
5205 "{ rat: [i] }" },
5206 { "{ rat: coefficients[[cst] -> [a]] }",
5207 "{ rat: [i] : FALSE }" },
5208 };
5209
5210 /* Test the basic functionality of isl_basic_set_coefficients and
5211 * isl_basic_set_solutions.
5212 */
5213 static int test_dual(isl_ctx *ctx)
5214 {
5215 int i;
5216
5217 for (i = 0; i < ARRAY_SIZE(coef_tests); ++i) {
5218 int equal;
5219 isl_basic_set *bset1, *bset2;
5220
5221 bset1 = isl_basic_set_read_from_str(ctx, coef_tests[i].set);
5222 bset2 = isl_basic_set_read_from_str(ctx, coef_tests[i].dual);
5223 bset1 = isl_basic_set_coefficients(bset1);
5224 equal = isl_basic_set_is_equal(bset1, bset2);
5225 isl_basic_set_free(bset1);
5226 isl_basic_set_free(bset2);
5227 if (equal < 0)
5228 return -1;
5229 if (!equal)
5230 isl_die(ctx, isl_error_unknown,
5231 "incorrect dual", return -1);
5232 }
5233
5234 for (i = 0; i < ARRAY_SIZE(sol_tests); ++i) {
5235 int equal;
5236 isl_basic_set *bset1, *bset2;
5237
5238 bset1 = isl_basic_set_read_from_str(ctx, sol_tests[i].set);
5239 bset2 = isl_basic_set_read_from_str(ctx, sol_tests[i].dual);
5240 bset1 = isl_basic_set_solutions(bset1);
5241 equal = isl_basic_set_is_equal(bset1, bset2);
5242 isl_basic_set_free(bset1);
5243 isl_basic_set_free(bset2);
5244 if (equal < 0)
5245 return -1;
5246 if (!equal)
5247 isl_die(ctx, isl_error_unknown,
5248 "incorrect dual", return -1);
5249 }
5250
5251 return 0;
5252 }
5253
5254 struct {
5255 int scale_tile;
5256 int shift_point;
5257 const char *domain;
5258 const char *schedule;
5259 const char *sizes;
5260 const char *tile;
5261 const char *point;
5262 } tile_tests[] = {
5263 { 0, 0, "[n] -> { S[i,j] : 0 <= i,j < n }",
5264 "[{ S[i,j] -> [i] }, { S[i,j] -> [j] }]",
5265 "{ [32,32] }",
5266 "[{ S[i,j] -> [floor(i/32)] }, { S[i,j] -> [floor(j/32)] }]",
5267 "[{ S[i,j] -> [i] }, { S[i,j] -> [j] }]",
5268 },
5269 { 1, 0, "[n] -> { S[i,j] : 0 <= i,j < n }",
5270 "[{ S[i,j] -> [i] }, { S[i,j] -> [j] }]",
5271 "{ [32,32] }",
5272 "[{ S[i,j] -> [32*floor(i/32)] }, { S[i,j] -> [32*floor(j/32)] }]",
5273 "[{ S[i,j] -> [i] }, { S[i,j] -> [j] }]",
5274 },
5275 { 0, 1, "[n] -> { S[i,j] : 0 <= i,j < n }",
5276 "[{ S[i,j] -> [i] }, { S[i,j] -> [j] }]",
5277 "{ [32,32] }",
5278 "[{ S[i,j] -> [floor(i/32)] }, { S[i,j] -> [floor(j/32)] }]",
5279 "[{ S[i,j] -> [i%32] }, { S[i,j] -> [j%32] }]",
5280 },
5281 { 1, 1, "[n] -> { S[i,j] : 0 <= i,j < n }",
5282 "[{ S[i,j] -> [i] }, { S[i,j] -> [j] }]",
5283 "{ [32,32] }",
5284 "[{ S[i,j] -> [32*floor(i/32)] }, { S[i,j] -> [32*floor(j/32)] }]",
5285 "[{ S[i,j] -> [i%32] }, { S[i,j] -> [j%32] }]",
5286 },
5287 };
5288
5289 /* Basic tiling tests. Create a schedule tree with a domain and a band node,
5290 * tile the band and then check if the tile and point bands have the
5291 * expected partial schedule.
5292 */
5293 static int test_tile(isl_ctx *ctx)
5294 {
5295 int i;
5296 int scale;
5297 int shift;
5298
5299 scale = isl_options_get_tile_scale_tile_loops(ctx);
5300 shift = isl_options_get_tile_shift_point_loops(ctx);
5301
5302 for (i = 0; i < ARRAY_SIZE(tile_tests); ++i) {
5303 int opt;
5304 int equal;
5305 const char *str;
5306 isl_union_set *domain;
5307 isl_multi_union_pw_aff *mupa, *mupa2;
5308 isl_schedule_node *node;
5309 isl_multi_val *sizes;
5310
5311 opt = tile_tests[i].scale_tile;
5312 isl_options_set_tile_scale_tile_loops(ctx, opt);
5313 opt = tile_tests[i].shift_point;
5314 isl_options_set_tile_shift_point_loops(ctx, opt);
5315
5316 str = tile_tests[i].domain;
5317 domain = isl_union_set_read_from_str(ctx, str);
5318 node = isl_schedule_node_from_domain(domain);
5319 node = isl_schedule_node_child(node, 0);
5320 str = tile_tests[i].schedule;
5321 mupa = isl_multi_union_pw_aff_read_from_str(ctx, str);
5322 node = isl_schedule_node_insert_partial_schedule(node, mupa);
5323 str = tile_tests[i].sizes;
5324 sizes = isl_multi_val_read_from_str(ctx, str);
5325 node = isl_schedule_node_band_tile(node, sizes);
5326
5327 str = tile_tests[i].tile;
5328 mupa = isl_multi_union_pw_aff_read_from_str(ctx, str);
5329 mupa2 = isl_schedule_node_band_get_partial_schedule(node);
5330 equal = isl_multi_union_pw_aff_plain_is_equal(mupa, mupa2);
5331 isl_multi_union_pw_aff_free(mupa);
5332 isl_multi_union_pw_aff_free(mupa2);
5333
5334 node = isl_schedule_node_child(node, 0);
5335
5336 str = tile_tests[i].point;
5337 mupa = isl_multi_union_pw_aff_read_from_str(ctx, str);
5338 mupa2 = isl_schedule_node_band_get_partial_schedule(node);
5339 if (equal >= 0 && equal)
5340 equal = isl_multi_union_pw_aff_plain_is_equal(mupa,
5341 mupa2);
5342 isl_multi_union_pw_aff_free(mupa);
5343 isl_multi_union_pw_aff_free(mupa2);
5344
5345 isl_schedule_node_free(node);
5346
5347 if (equal < 0)
5348 return -1;
5349 if (!equal)
5350 isl_die(ctx, isl_error_unknown,
5351 "unexpected result", return -1);
5352 }
5353
5354 isl_options_set_tile_scale_tile_loops(ctx, scale);
5355 isl_options_set_tile_shift_point_loops(ctx, shift);
5356
5357 return 0;
5358 }
5359
5360 struct {
5361 const char *name;
5362 int (*fn)(isl_ctx *ctx);
5363 } tests [] = {
5364 { "dual", &test_dual },
5365 { "dependence analysis", &test_flow },
5366 { "val", &test_val },
5367 { "compute divs", &test_compute_divs },
5368 { "partial lexmin", &test_partial_lexmin },
5369 { "simplify", &test_simplify },
5370 { "curry", &test_curry },
5371 { "piecewise multi affine expressions", &test_pw_multi_aff },
5372 { "multi piecewise affine expressions", &test_multi_pw_aff },
5373 { "conversion", &test_conversion },
5374 { "list", &test_list },
5375 { "align parameters", &test_align_parameters },
5376 { "preimage", &test_preimage },
5377 { "pullback", &test_pullback },
5378 { "AST", &test_ast },
5379 { "AST build", &test_ast_build },
5380 { "AST generation", &test_ast_gen },
5381 { "eliminate", &test_eliminate },
5382 { "residue class", &test_residue_class },
5383 { "div", &test_div },
5384 { "slice", &test_slice },
5385 { "fixed power", &test_fixed_power },
5386 { "sample", &test_sample },
5387 { "output", &test_output },
5388 { "vertices", &test_vertices },
5389 { "fixed", &test_fixed },
5390 { "equal", &test_equal },
5391 { "disjoint", &test_disjoint },
5392 { "product", &test_product },
5393 { "dim_max", &test_dim_max },
5394 { "affine", &test_aff },
5395 { "injective", &test_injective },
5396 { "schedule", &test_schedule },
5397 { "tile", &test_tile },
5398 { "union_pw", &test_union_pw },
5399 { "parse", &test_parse },
5400 { "single-valued", &test_sv },
5401 { "affine hull", &test_affine_hull },
5402 { "coalesce", &test_coalesce },
5403 { "factorize", &test_factorize },
5404 { "subset", &test_subset },
5405 { "subtract", &test_subtract },
5406 { "lexmin", &test_lexmin },
5407 { "min", &test_min },
5408 { "gist", &test_gist },
5409 { "piecewise quasi-polynomials", &test_pwqp },
5410 };
5411
5412 int main(int argc, char **argv)
5413 {
5414 int i;
5415 struct isl_ctx *ctx;
5416 struct isl_options *options;
5417
5418 srcdir = getenv("srcdir");
5419 assert(srcdir);
5420
5421 options = isl_options_new_with_defaults();
5422 assert(options);
5423 argc = isl_options_parse(options, argc, argv, ISL_ARG_ALL);
5424
5425 ctx = isl_ctx_alloc_with_options(&isl_options_args, options);
5426 for (i = 0; i < ARRAY_SIZE(tests); ++i) {
5427 printf("%s\n", tests[i].name);
5428 if (tests[i].fn(ctx) < 0)
5429 goto error;
5430 }
5431 test_lift(ctx);
5432 test_bound(ctx);
5433 test_union(ctx);
5434 test_split_periods(ctx);
5435 test_lex(ctx);
5436 test_bijective(ctx);
5437 test_dep(ctx);
5438 test_read(ctx);
5439 test_bounded(ctx);
5440 test_construction(ctx);
5441 test_dim(ctx);
5442 test_application(ctx);
5443 test_convex_hull(ctx);
5444 test_closure(ctx);
5445 isl_ctx_free(ctx);
5446 return 0;
5447 error:
5448 isl_ctx_free(ctx);
5449 return -1;
5450 }
Integer set library