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