X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_test.c;h=eeb2fc365c3c6e17ca5dea1482e054b44ca24ad2;hb=7a361e6e472e452b3fb6794c96f6ab983fc716cc;hp=bc8b7487bcc2b422aee99bcf3ed40c3f39f46484;hpb=ec8f3527599403f6c80955420e6b4ade48e91316;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_test.c b/isl_test.c
index bc8b748..eeb2fc3 100644
--- a/isl_test.c
+++ b/isl_test.c
@@ -23,6 +23,7 @@
 #include <isl_options_private.h>
 #include <isl/vertices.h>
 #include <isl/ast_build.h>
+#include <isl/val.h>
 
 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
 
@@ -322,6 +323,221 @@ void test_dim(struct isl_ctx *ctx)
 	isl_map_free(map2);
 }
 
+struct {
+	__isl_give isl_val *(*op)(__isl_take isl_val *v);
+	const char *arg;
+	const char *res;
+} val_un_tests[] = {
+	{ &isl_val_neg, "0", "0" },
+	{ &isl_val_abs, "0", "0" },
+	{ &isl_val_2exp, "0", "1" },
+	{ &isl_val_floor, "0", "0" },
+	{ &isl_val_ceil, "0", "0" },
+	{ &isl_val_neg, "1", "-1" },
+	{ &isl_val_neg, "-1", "1" },
+	{ &isl_val_neg, "1/2", "-1/2" },
+	{ &isl_val_neg, "-1/2", "1/2" },
+	{ &isl_val_neg, "infty", "-infty" },
+	{ &isl_val_neg, "-infty", "infty" },
+	{ &isl_val_neg, "NaN", "NaN" },
+	{ &isl_val_abs, "1", "1" },
+	{ &isl_val_abs, "-1", "1" },
+	{ &isl_val_abs, "1/2", "1/2" },
+	{ &isl_val_abs, "-1/2", "1/2" },
+	{ &isl_val_abs, "infty", "infty" },
+	{ &isl_val_abs, "-infty", "infty" },
+	{ &isl_val_abs, "NaN", "NaN" },
+	{ &isl_val_floor, "1", "1" },
+	{ &isl_val_floor, "-1", "-1" },
+	{ &isl_val_floor, "1/2", "0" },
+	{ &isl_val_floor, "-1/2", "-1" },
+	{ &isl_val_floor, "infty", "infty" },
+	{ &isl_val_floor, "-infty", "-infty" },
+	{ &isl_val_floor, "NaN", "NaN" },
+	{ &isl_val_ceil, "1", "1" },
+	{ &isl_val_ceil, "-1", "-1" },
+	{ &isl_val_ceil, "1/2", "1" },
+	{ &isl_val_ceil, "-1/2", "0" },
+	{ &isl_val_ceil, "infty", "infty" },
+	{ &isl_val_ceil, "-infty", "-infty" },
+	{ &isl_val_ceil, "NaN", "NaN" },
+	{ &isl_val_2exp, "-3", "1/8" },
+	{ &isl_val_2exp, "-1", "1/2" },
+	{ &isl_val_2exp, "1", "2" },
+	{ &isl_val_2exp, "2", "4" },
+	{ &isl_val_2exp, "3", "8" },
+};
+
+/* Perform some basic tests of unary operations on isl_val objects.
+ */
+static int test_un_val(isl_ctx *ctx)
+{
+	int i;
+	isl_val *v, *res;
+	__isl_give isl_val *(*fn)(__isl_take isl_val *v);
+	int ok;
+
+	for (i = 0; i < ARRAY_SIZE(val_un_tests); ++i) {
+		v = isl_val_read_from_str(ctx, val_un_tests[i].arg);
+		res = isl_val_read_from_str(ctx, val_un_tests[i].res);
+		fn = val_un_tests[i].op;
+		v = fn(v);
+		if (isl_val_is_nan(res))
+			ok = isl_val_is_nan(v);
+		else
+			ok = isl_val_eq(v, res);
+		isl_val_free(v);
+		isl_val_free(res);
+		if (ok < 0)
+			return -1;
+		if (!ok)
+			isl_die(ctx, isl_error_unknown,
+				"unexpected result", return -1);
+	}
+
+	return 0;
+}
+
+struct {
+	__isl_give isl_val *(*fn)(__isl_take isl_val *v1,
+				__isl_take isl_val *v2);
+} val_bin_op[] = {
+	['+'] = { &isl_val_add },
+	['-'] = { &isl_val_sub },
+	['*'] = { &isl_val_mul },
+	['/'] = { &isl_val_div },
+	['g'] = { &isl_val_gcd },
+	['m'] = { &isl_val_min },
+	['M'] = { &isl_val_max },
+};
+
+struct {
+	const char *arg1;
+	unsigned char op;
+	const char *arg2;
+	const char *res;
+} val_bin_tests[] = {
+	{ "0", '+', "0", "0" },
+	{ "1", '+', "0", "1" },
+	{ "1", '+', "1", "2" },
+	{ "1", '-', "1", "0" },
+	{ "1", '*', "1", "1" },
+	{ "1", '/', "1", "1" },
+	{ "2", '*', "3", "6" },
+	{ "2", '*', "1/2", "1" },
+	{ "2", '*', "1/3", "2/3" },
+	{ "2/3", '*', "3/5", "2/5" },
+	{ "2/3", '*', "7/5", "14/15" },
+	{ "2", '/', "1/2", "4" },
+	{ "-2", '/', "-1/2", "4" },
+	{ "-2", '/', "1/2", "-4" },
+	{ "2", '/', "-1/2", "-4" },
+	{ "2", '/', "2", "1" },
+	{ "2", '/', "3", "2/3" },
+	{ "2/3", '/', "5/3", "2/5" },
+	{ "2/3", '/', "5/7", "14/15" },
+	{ "0", '/', "0", "NaN" },
+	{ "42", '/', "0", "NaN" },
+	{ "-42", '/', "0", "NaN" },
+	{ "infty", '/', "0", "NaN" },
+	{ "-infty", '/', "0", "NaN" },
+	{ "NaN", '/', "0", "NaN" },
+	{ "0", '/', "NaN", "NaN" },
+	{ "42", '/', "NaN", "NaN" },
+	{ "-42", '/', "NaN", "NaN" },
+	{ "infty", '/', "NaN", "NaN" },
+	{ "-infty", '/', "NaN", "NaN" },
+	{ "NaN", '/', "NaN", "NaN" },
+	{ "0", '/', "infty", "0" },
+	{ "42", '/', "infty", "0" },
+	{ "-42", '/', "infty", "0" },
+	{ "infty", '/', "infty", "NaN" },
+	{ "-infty", '/', "infty", "NaN" },
+	{ "NaN", '/', "infty", "NaN" },
+	{ "0", '/', "-infty", "0" },
+	{ "42", '/', "-infty", "0" },
+	{ "-42", '/', "-infty", "0" },
+	{ "infty", '/', "-infty", "NaN" },
+	{ "-infty", '/', "-infty", "NaN" },
+	{ "NaN", '/', "-infty", "NaN" },
+	{ "1", '-', "1/3", "2/3" },
+	{ "1/3", '+', "1/2", "5/6" },
+	{ "1/2", '+', "1/2", "1" },
+	{ "3/4", '-', "1/4", "1/2" },
+	{ "1/2", '-', "1/3", "1/6" },
+	{ "infty", '+', "42", "infty" },
+	{ "infty", '+', "infty", "infty" },
+	{ "42", '+', "infty", "infty" },
+	{ "infty", '-', "infty", "NaN" },
+	{ "infty", '*', "infty", "infty" },
+	{ "infty", '*', "-infty", "-infty" },
+	{ "-infty", '*', "infty", "-infty" },
+	{ "-infty", '*', "-infty", "infty" },
+	{ "0", '*', "infty", "NaN" },
+	{ "1", '*', "infty", "infty" },
+	{ "infty", '*', "0", "NaN" },
+	{ "infty", '*', "42", "infty" },
+	{ "42", '-', "infty", "-infty" },
+	{ "infty", '+', "-infty", "NaN" },
+	{ "4", 'g', "6", "2" },
+	{ "5", 'g', "6", "1" },
+	{ "42", 'm', "3", "3" },
+	{ "42", 'M', "3", "42" },
+	{ "3", 'm', "42", "3" },
+	{ "3", 'M', "42", "42" },
+	{ "42", 'm', "infty", "42" },
+	{ "42", 'M', "infty", "infty" },
+	{ "42", 'm', "-infty", "-infty" },
+	{ "42", 'M', "-infty", "42" },
+	{ "42", 'm', "NaN", "NaN" },
+	{ "42", 'M', "NaN", "NaN" },
+	{ "infty", 'm', "-infty", "-infty" },
+	{ "infty", 'M', "-infty", "infty" },
+};
+
+/* Perform some basic tests of binary operations on isl_val objects.
+ */
+static int test_bin_val(isl_ctx *ctx)
+{
+	int i;
+	isl_val *v1, *v2, *res;
+	__isl_give isl_val *(*fn)(__isl_take isl_val *v1,
+				__isl_take isl_val *v2);
+	int ok;
+
+	for (i = 0; i < ARRAY_SIZE(val_bin_tests); ++i) {
+		v1 = isl_val_read_from_str(ctx, val_bin_tests[i].arg1);
+		v2 = isl_val_read_from_str(ctx, val_bin_tests[i].arg2);
+		res = isl_val_read_from_str(ctx, val_bin_tests[i].res);
+		fn = val_bin_op[val_bin_tests[i].op].fn;
+		v1 = fn(v1, v2);
+		if (isl_val_is_nan(res))
+			ok = isl_val_is_nan(v1);
+		else
+			ok = isl_val_eq(v1, res);
+		isl_val_free(v1);
+		isl_val_free(res);
+		if (ok < 0)
+			return -1;
+		if (!ok)
+			isl_die(ctx, isl_error_unknown,
+				"unexpected result", return -1);
+	}
+
+	return 0;
+}
+
+/* Perform some basic tests on isl_val objects.
+ */
+static int test_val(isl_ctx *ctx)
+{
+	if (test_un_val(ctx) < 0)
+		return -1;
+	if (test_bin_val(ctx) < 0)
+		return -1;
+	return 0;
+}
+
 static int test_div(isl_ctx *ctx)
 {
 	unsigned n;
@@ -719,8 +935,9 @@ int test_affine_hull(struct isl_ctx *ctx)
 {
 	const char *str;
 	isl_set *set;
-	isl_basic_set *bset;
+	isl_basic_set *bset, *bset2;
 	int n;
+	int subset;
 
 	test_affine_hull_case(ctx, "affine2");
 	test_affine_hull_case(ctx, "affine");
@@ -750,6 +967,21 @@ int test_affine_hull(struct isl_ctx *ctx)
 	if (!bset)
 		return -1;
 
+	str = "{ [a] : exists e0, e1, e2: 32e1 = 31 + 31a + 31e0 and "
+			"32e2 = 31 + 31e0 }";
+	set = isl_set_read_from_str(ctx, str);
+	bset = isl_set_affine_hull(set);
+	str = "{ [a] : exists e : a = 32 e }";
+	bset2 = isl_basic_set_read_from_str(ctx, str);
+	subset = isl_basic_set_is_subset(bset, bset2);
+	isl_basic_set_free(bset);
+	isl_basic_set_free(bset2);
+	if (subset < 0)
+		return -1;
+	if (!subset)
+		isl_die(ctx, isl_error_unknown, "not as accurate as expected",
+			return -1);
+
 	return 0;
 }
 
@@ -1421,6 +1653,20 @@ static int test_lexmin(struct isl_ctx *ctx)
 	isl_map_free(map);
 	isl_map_free(map2);
 
+	/* Check that empty pieces are properly combined. */
+	str = "[K, N] -> { [x, y] -> [a, b] : K+2<=N<=K+4 and x>=4 and "
+		"2N-6<=x<K+N and N-1<=a<=K+N-1 and N+b-6<=a<=2N-4 and "
+		"b<=2N-3K+a and 3b<=4N-K+1 and b>=N and a>=x+1 }";
+	map = isl_map_read_from_str(ctx, str);
+	map = isl_map_lexmin(map);
+	str = "[K, N] -> { [x, y] -> [1 + x, N] : x >= -6 + 2N and "
+		"x <= -5 + 2N and x >= -1 + 3K - N and x <= -2 + K + N and "
+		"x >= 4 }";
+	map2 = isl_map_read_from_str(ctx, str);
+	assert(isl_map_is_equal(map, map2));
+	isl_map_free(map);
+	isl_map_free(map2);
+
 	str = "[i] -> { [i', j] : j = i - 8i' and i' >= 0 and i' <= 7 and "
 				" 8i' <= i and 8i' >= -7 + i }";
 	set = isl_set_read_from_str(ctx, str);
@@ -1758,11 +2004,12 @@ void test_bijective(struct isl_ctx *ctx)
 	test_bijective_case(ctx, "[N,M]->{[i,j] -> [x,y] : 2x=i & y =j}", 1);
 }
 
-void test_pwqp(struct isl_ctx *ctx)
+static int test_pwqp(struct isl_ctx *ctx)
 {
 	const char *str;
 	isl_set *set;
 	isl_pw_qpolynomial *pwqp1, *pwqp2;
+	int equal;
 
 	str = "{ [i,j,k] -> 1 + 9 * [i/5] + 7 * [j/11] + 4 * [k/13] }";
 	pwqp1 = isl_pw_qpolynomial_read_from_str(ctx, str);
@@ -1850,6 +2097,36 @@ void test_pwqp(struct isl_ctx *ctx)
 	pwqp1 = isl_pw_qpolynomial_sub(pwqp1, pwqp2);
 	assert(isl_pw_qpolynomial_is_zero(pwqp1));
 	isl_pw_qpolynomial_free(pwqp1);
+
+	str = "{ [a,b,a] -> (([(2*[a/3]+b)/5]) * ([(2*[a/3]+b)/5])) }";
+	pwqp2 = isl_pw_qpolynomial_read_from_str(ctx, str);
+	str = "{ [a,b,c] -> (([(2*[a/3]+b)/5]) * ([(2*[c/3]+b)/5])) }";
+	pwqp1 = isl_pw_qpolynomial_read_from_str(ctx, str);
+	set = isl_set_read_from_str(ctx, "{ [a,b,a] }");
+	pwqp1 = isl_pw_qpolynomial_intersect_domain(pwqp1, set);
+	equal = isl_pw_qpolynomial_plain_is_equal(pwqp1, pwqp2);
+	isl_pw_qpolynomial_free(pwqp1);
+	isl_pw_qpolynomial_free(pwqp2);
+	if (equal < 0)
+		return -1;
+	if (!equal)
+		isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
+
+	str = "{ [a,b,c] -> (([(2*[a/3]+1)/5]) * ([(2*[c/3]+1)/5])) : b = 1 }";
+	pwqp2 = isl_pw_qpolynomial_read_from_str(ctx, str);
+	str = "{ [a,b,c] -> (([(2*[a/3]+b)/5]) * ([(2*[c/3]+b)/5])) }";
+	pwqp1 = isl_pw_qpolynomial_read_from_str(ctx, str);
+	pwqp1 = isl_pw_qpolynomial_fix_val(pwqp1, isl_dim_set, 1,
+						isl_val_one(ctx));
+	equal = isl_pw_qpolynomial_plain_is_equal(pwqp1, pwqp2);
+	isl_pw_qpolynomial_free(pwqp1);
+	isl_pw_qpolynomial_free(pwqp2);
+	if (equal < 0)
+		return -1;
+	if (!equal)
+		isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
+
+	return 0;
 }
 
 void test_split_periods(isl_ctx *ctx)
@@ -2551,6 +2828,20 @@ int test_schedule(isl_ctx *ctx)
 	if (test_padded_schedule(ctx) < 0)
 		return -1;
 
+	/* Check that check for progress is not confused by rational
+	 * solution.
+	 */
+	D = "[N] -> { S0[i, j] : i >= 0 and i <= N and j >= 0 and j <= N }";
+	V = "[N] -> { S0[i0, -1 + N] -> S0[2 + i0, 0] : i0 >= 0 and "
+							"i0 <= -2 + N; "
+			"S0[i0, i1] -> S0[i0, 1 + i1] : i0 >= 0 and "
+				"i0 <= N and i1 >= 0 and i1 <= -1 + N }";
+	P = "{}";
+	ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_FEAUTRIER;
+	if (test_has_schedule(ctx, D, V, P) < 0)
+		return -1;
+	ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_ISL;
+
 	return 0;
 }
 
@@ -3332,7 +3623,7 @@ struct {
 	  "{ A[i,j] : j = [(i)/6] and exists a : i = 3 a }" },
 };
 
-int test_preimage(isl_ctx *ctx)
+static int test_preimage_basic_set(isl_ctx *ctx)
 {
 	int i;
 	isl_basic_set *bset1, *bset2;
@@ -3358,6 +3649,76 @@ int test_preimage(isl_ctx *ctx)
 }
 
 struct {
+	const char *map;
+	const char *ma;
+	const char *res;
+} preimage_domain_tests[] = {
+	{ "{ B[i,j] -> C[2i + 3j] : 0 <= i < 10 and 0 <= j < 100 }",
+	  "{ A[j,i] -> B[i,j] }",
+	  "{ A[j,i] -> C[2i + 3j] : 0 <= i < 10 and 0 <= j < 100 }" },
+	{ "{ B[i] -> C[i]; D[i] -> E[i] }",
+	  "{ A[i] -> B[i + 1] }",
+	  "{ A[i] -> C[i + 1] }" },
+	{ "{ B[i] -> C[i]; B[i] -> E[i] }",
+	  "{ A[i] -> B[i + 1] }",
+	  "{ A[i] -> C[i + 1]; A[i] -> E[i + 1] }" },
+	{ "{ B[i] -> C[([i/2])] }",
+	  "{ A[i] -> B[2i] }",
+	  "{ A[i] -> C[i] }" },
+	{ "{ B[i,j] -> C[([i/2]), ([(i+j)/3])] }",
+	  "{ A[i] -> B[([i/5]), ([i/7])] }",
+	  "{ A[i] -> C[([([i/5])/2]), ([(([i/5])+([i/7]))/3])] }" },
+	{ "[N] -> { B[i] -> C[([N/2]), i, ([N/3])] }",
+	  "[N] -> { A[] -> B[([N/5])] }",
+	  "[N] -> { A[] -> C[([N/2]), ([N/5]), ([N/3])] }" },
+	{ "{ B[i] -> C[i] : exists a : i = 5 a }",
+	  "{ A[i] -> B[2i] }",
+	  "{ A[i] -> C[2i] : exists a : 2i = 5 a }" },
+	{ "{ B[i] -> C[i] : exists a : i = 2 a; "
+	    "B[i] -> D[i] : exists a : i = 2 a + 1 }",
+	  "{ A[i] -> B[2i] }",
+	  "{ A[i] -> C[2i] }" },
+};
+
+static int test_preimage_union_map(isl_ctx *ctx)
+{
+	int i;
+	isl_union_map *umap1, *umap2;
+	isl_multi_aff *ma;
+	int equal;
+
+	for (i = 0; i < ARRAY_SIZE(preimage_domain_tests); ++i) {
+		umap1 = isl_union_map_read_from_str(ctx,
+						preimage_domain_tests[i].map);
+		ma = isl_multi_aff_read_from_str(ctx,
+						preimage_domain_tests[i].ma);
+		umap2 = isl_union_map_read_from_str(ctx,
+						preimage_domain_tests[i].res);
+		umap1 = isl_union_map_preimage_domain_multi_aff(umap1, ma);
+		equal = isl_union_map_is_equal(umap1, umap2);
+		isl_union_map_free(umap1);
+		isl_union_map_free(umap2);
+		if (equal < 0)
+			return -1;
+		if (!equal)
+			isl_die(ctx, isl_error_unknown, "bad preimage",
+				return -1);
+	}
+
+	return 0;
+}
+
+static int test_preimage(isl_ctx *ctx)
+{
+	if (test_preimage_basic_set(ctx) < 0)
+		return -1;
+	if (test_preimage_union_map(ctx) < 0)
+		return -1;
+
+	return 0;
+}
+
+struct {
 	const char *ma1;
 	const char *ma;
 	const char *res;
@@ -3736,6 +4097,76 @@ static int test_ast_gen4(isl_ctx *ctx)
 	return 0;
 }
 
+/* This function is called for each leaf in the AST generated
+ * from test_ast_gen5.
+ *
+ * We finalize the AST generation by extending the outer schedule
+ * with a zero-dimensional schedule.  If this results in any for loops,
+ * then this means that we did not pass along enough information
+ * about the outer schedule to the inner AST generation.
+ */
+static __isl_give isl_ast_node *create_leaf(__isl_take isl_ast_build *build,
+	void *user)
+{
+	isl_union_map *schedule, *extra;
+	isl_ast_node *tree;
+
+	schedule = isl_ast_build_get_schedule(build);
+	extra = isl_union_map_copy(schedule);
+	extra = isl_union_map_from_domain(isl_union_map_domain(extra));
+	schedule = isl_union_map_range_product(schedule, extra);
+	tree = isl_ast_build_ast_from_schedule(build, schedule);
+	isl_ast_build_free(build);
+
+	if (!tree)
+		return NULL;
+
+	if (isl_ast_node_get_type(tree) == isl_ast_node_for)
+		isl_die(isl_ast_node_get_ctx(tree), isl_error_unknown,
+			"code should not contain any for loop",
+			return isl_ast_node_free(tree));
+
+	return tree;
+}
+
+/* Check that we do not lose any information when going back and
+ * forth between internal and external schedule.
+ *
+ * In particular, we create an AST where we unroll the only
+ * non-constant dimension in the schedule.  We therefore do
+ * not expect any for loops in the AST.  However, older versions
+ * of isl would not pass along enough information about the outer
+ * schedule when performing an inner code generation from a create_leaf
+ * callback, resulting in the inner code generation producing a for loop.
+ */
+static int test_ast_gen5(isl_ctx *ctx)
+{
+	const char *str;
+	isl_set *set;
+	isl_union_map *schedule, *options;
+	isl_ast_build *build;
+	isl_ast_node *tree;
+
+	str = "{ A[] -> [1, 1, 2]; B[i] -> [1, i, 0] : i >= 1 and i <= 2 }";
+	schedule = isl_union_map_read_from_str(ctx, str);
+
+	str = "{ [a, b, c] -> unroll[1] : exists (e0 = [(a)/4]: "
+				"4e0 >= -1 + a - b and 4e0 <= -2 + a + b) }";
+	options = isl_union_map_read_from_str(ctx, str);
+
+	set = isl_set_universe(isl_space_params_alloc(ctx, 0));
+	build = isl_ast_build_from_context(set);
+	build = isl_ast_build_set_options(build, options);
+        build = isl_ast_build_set_create_leaf(build, &create_leaf, NULL);
+	tree = isl_ast_build_ast_from_schedule(build, schedule);
+	isl_ast_build_free(build);
+	isl_ast_node_free(tree);
+	if (!tree)
+		return -1;
+
+	return 0;
+}
+
 static int test_ast_gen(isl_ctx *ctx)
 {
 	if (test_ast_gen1(ctx) < 0)
@@ -3746,6 +4177,8 @@ static int test_ast_gen(isl_ctx *ctx)
 		return -1;
 	if (test_ast_gen4(ctx) < 0)
 		return -1;
+	if (test_ast_gen5(ctx) < 0)
+		return -1;
 	return 0;
 }
 
@@ -3862,6 +4295,7 @@ struct {
 	const char *name;
 	int (*fn)(isl_ctx *ctx);
 } tests [] = {
+	{ "val", &test_val },
 	{ "compute divs", &test_compute_divs },
 	{ "partial lexmin", &test_partial_lexmin },
 	{ "simplify", &test_simplify },
@@ -3898,6 +4332,7 @@ struct {
 	{ "subset", &test_subset },
 	{ "subtract", &test_subtract },
 	{ "lexmin", &test_lexmin },
+	{ "piecewise quasi-polynomials", &test_pwqp },
 };
 
 int main()
@@ -3918,7 +4353,6 @@ int main()
 	test_bound(ctx);
 	test_union(ctx);
 	test_split_periods(ctx);
-	test_pwqp(ctx);
 	test_lex(ctx);
 	test_bijective(ctx);
 	test_dep(ctx);