From 41b903e3afdc9ffdc1e0e1b34b02e42a9c225bc9 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Tue, 18 Jan 2011 14:17:25 +0100 Subject: [PATCH] isl_set_convex_hull: optionally use Fourier-Motzkin based algorithm The Fourier-Motzkin based algorithm used to be the default but was disabled when the wrapping based algorithm was completed in 6371ed7 (isl_map_convex_hull: handle unbounded, but pointed, case using wrapping, Mon Apr 13 23:11:19 2009 +0200). Signed-off-by: Sven Verdoolaege --- include/isl/options.h | 4 ++++ isl_convex_hull.c | 6 +++++- isl_options.c | 8 ++++++++ isl_test.c | 12 +++++++++++- 4 files changed, 28 insertions(+), 2 deletions(-) diff --git a/include/isl/options.h b/include/isl/options.h index 790972f..673c272 100644 --- a/include/isl/options.h +++ b/include/isl/options.h @@ -54,6 +54,10 @@ struct isl_options { int bernstein_triangulate; int pip_symmetry; + + #define ISL_CONVEX_HULL_WRAP 0 + #define ISL_CONVEX_HULL_FM 1 + int convex; }; ISL_ARG_DECL(isl_options, struct isl_options, isl_options_arg) diff --git a/isl_convex_hull.c b/isl_convex_hull.c index 40cca1b..260bbd4 100644 --- a/isl_convex_hull.c +++ b/isl_convex_hull.c @@ -1352,6 +1352,9 @@ static struct isl_basic_set *convex_hull_pair(struct isl_basic_set *bset1, isl_basic_set *lin, *aff; int bounded1, bounded2; + if (bset1->ctx->opt->convex == ISL_CONVEX_HULL_FM) + return convex_hull_pair_elim(bset1, bset2); + aff = isl_set_affine_hull(isl_basic_set_union(isl_basic_set_copy(bset1), isl_basic_set_copy(bset2))); if (!aff) @@ -1807,7 +1810,8 @@ static struct isl_basic_set *uset_convex_hull(struct isl_set *set) if (isl_set_n_dim(set) == 1) return convex_hull_1d(set); - if (isl_set_is_bounded(set)) + if (isl_set_is_bounded(set) && + set->ctx->opt->convex == ISL_CONVEX_HULL_WRAP) return uset_convex_hull_wrap(set); lin = uset_combined_lineality_space(isl_set_copy(set)); diff --git a/isl_options.c b/isl_options.c index d7f4169..c603c2a 100644 --- a/isl_options.c +++ b/isl_options.c @@ -75,6 +75,12 @@ static struct isl_arg_flags bernstein_recurse[] = { {0} }; +static struct isl_arg_choice convex[] = { + {"wrap", ISL_CONVEX_HULL_WRAP}, + {"fm", ISL_CONVEX_HULL_FM}, + {0} +}; + static void print_version(void) { printf("%s", isl_version()); @@ -107,6 +113,8 @@ ISL_ARG_BOOL(struct isl_options, bernstein_triangulate, 0, "triangulate domains during Bernstein expansion") ISL_ARG_BOOL(struct isl_options, pip_symmetry, 0, "pip-symmetry", 1, "detect simple symmetries in PIP input") +ISL_ARG_CHOICE(struct isl_options, convex, 0, "convex-hull", \ + convex, ISL_CONVEX_HULL_WRAP, "convex hull algorithm to use") ISL_ARG_VERSION(print_version) ISL_ARG_END }; diff --git a/isl_test.c b/isl_test.c index 4c65209..0382830 100644 --- a/isl_test.c +++ b/isl_test.c @@ -573,10 +573,12 @@ void test_convex_hull_case(struct isl_ctx *ctx, const char *name) fclose(input); } -void test_convex_hull(struct isl_ctx *ctx) +void test_convex_hull_algo(struct isl_ctx *ctx, int convex) { const char *str1, *str2; isl_set *set1, *set2; + int orig_convex = ctx->opt->convex; + ctx->opt->convex = convex; test_convex_hull_case(ctx, "convex0"); test_convex_hull_case(ctx, "convex1"); @@ -605,6 +607,14 @@ void test_convex_hull(struct isl_ctx *ctx) assert(isl_set_is_equal(set1, set2)); isl_set_free(set1); isl_set_free(set2); + + ctx->opt->convex = orig_convex; +} + +void test_convex_hull(struct isl_ctx *ctx) +{ + test_convex_hull_algo(ctx, ISL_CONVEX_HULL_FM); + test_convex_hull_algo(ctx, ISL_CONVEX_HULL_WRAP); } void test_gist_case(struct isl_ctx *ctx, const char *name) -- 2.7.4