isl_ast_codegen.c: generate_domain: avoid infinite recursion

generate_domain checks if the inverse schedule is single-valued
so that the inverse schedule can be extended if needed.
Since this check is performed on the gisted inverse schedule,
it may fail even in a recursive call on an inverse schedule
that has been extended to ensure that it is single valued.
We may then end up in an infinite recursion.

To avoid this problem, we keep track of the fact that we have
already extended the inverse schedule to not be single-valued.
In such cases, we revert to the ungisted inverse schedule
if the gisted inverse schedule turns out not to be single-valued.

Reported-by: Tobias Grosser <tobias@grosser.es>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

diff --git a/isl_ast_build.c b/isl_ast_build.c
index fbbb5c5..ed67545 100644 (file)
--- a/isl_ast_build.c
+++ b/isl_ast_build.c
@@ -177,6 +177,7 @@ __isl_give isl_ast_build *isl_ast_build_dup(__isl_keep isl_ast_build *build)
        dup->strides = isl_vec_copy(build->strides);
        dup->offsets = isl_multi_aff_copy(build->offsets);
        dup->executed = isl_union_map_copy(build->executed);
+       dup->single_valued = build->single_valued;
        dup->options = isl_union_map_copy(build->options);
        dup->at_each_domain = build->at_each_domain;
        dup->at_each_domain_user = build->at_each_domain_user;
@@ -2076,3 +2077,20 @@ __isl_give isl_set *isl_ast_build_eliminate(
        domain = isl_ast_build_eliminate_divs(build, domain);
        return domain;
 }
+
+/* Replace build->single_valued by "sv".
+ */
+__isl_give isl_ast_build *isl_ast_build_set_single_valued(
+       __isl_take isl_ast_build *build, int sv)
+{
+       if (!build)
+               return build;
+       if (build->single_valued == sv)
+               return build;
+       build = isl_ast_build_cow(build);
+       if (!build)
+               return build;
+       build->single_valued = sv;
+
+       return build;
+}

diff --git a/isl_ast_build_private.h b/isl_ast_build_private.h
index 5881eff..516bc62 100644 (file)
--- a/isl_ast_build_private.h
+++ b/isl_ast_build_private.h
@@ -109,6 +109,13 @@ enum isl_ast_build_domain_type {
  * It is currently only used in isl_ast_build_get_schedule, which is
  * in turn only used by user code from within a callback.
  * The value is set right before we may be calling such a callback.
+ *
+ * "single_valued" is set if the current inverse schedule (which may or may
+ * not be stored in "executed") is known to be single valued, specifically
+ * an inverse schedule that was not (appeared not to be) single valued
+ * is extended to a single valued inverse schedule.  This is mainly used
+ * to avoid an infinite recursion when we fail to detect later on that
+ * the extended inverse schedule is single valued.
  */
 struct isl_ast_build {
        int ref;
@@ -150,6 +157,7 @@ struct isl_ast_build {
        void *create_leaf_user;
 
        isl_union_map *executed;
+       int single_valued;
 };
 
 __isl_give isl_ast_build *isl_ast_build_clear_local_info(
@@ -179,6 +187,8 @@ __isl_give isl_ast_build *isl_ast_build_include_stride(
 __isl_give isl_ast_build *isl_ast_build_set_executed(
        __isl_take isl_ast_build *build,
        __isl_take isl_union_map *executed);
+__isl_give isl_ast_build *isl_ast_build_set_single_valued(
+       __isl_take isl_ast_build *build, int sv);
 __isl_give isl_set *isl_ast_build_get_domain(
        __isl_keep isl_ast_build *build);
 __isl_give isl_ast_build *isl_ast_build_restrict_generated(

diff --git a/isl_ast_codegen.c b/isl_ast_codegen.c
index b262fed..e935550 100644 (file)
--- a/isl_ast_codegen.c
+++ b/isl_ast_codegen.c
@@ -108,6 +108,7 @@ static int generate_non_single_valued(__isl_take isl_map *executed,
 
        identity = isl_set_identity(isl_map_range(isl_map_copy(executed)));
        executed = isl_map_domain_product(executed, identity);
+       build = isl_ast_build_set_single_valued(build, 1);
 
        list = generate_code(isl_union_map_from_map(executed), build, 1);
 
@@ -155,7 +156,16 @@ static __isl_give isl_ast_graft *at_each_domain(__isl_take isl_ast_graft *graft,
  * the constraints from data->build->domain.
  * On the other hand, we only perform the test after having taken the gist
  * of the domain as the resulting map is the one from which the call
- * expression is constructed.
+ * expression is constructed.  Using this map to construct the call
+ * expression usually yields simpler results.
+ * Because we perform the single-valuedness test on the gisted map,
+ * we may in rare cases fail to recognize that the inverse schedule
+ * is single-valued.  This becomes problematic if this happens
+ * from the recursive call through generate_non_single_valued
+ * as we would then end up in an infinite recursion.
+ * We therefore check if we are inside a call to generate_non_single_valued
+ * and revert to the ungisted map if the gisted map turns out not to be
+ * single-valued.
  *
  * Otherwise, we generate a call expression for the single executed
  * domain element and put a guard around it based on the (simplified)
@@ -184,7 +194,10 @@ static int generate_domain(__isl_take isl_map *executed, void *user)
                goto error;
        if (!sv) {
                isl_map_free(map);
-               return generate_non_single_valued(executed, data);
+               if (data->build->single_valued)
+                       map = isl_map_copy(executed);
+               else
+                       return generate_non_single_valued(executed, data);
        }
        guard = isl_map_domain(isl_map_copy(map));
        guard = isl_set_coalesce(guard);
@@ -3629,9 +3642,12 @@ __isl_give isl_ast_node *isl_ast_build_ast_from_schedule(
        isl_ast_node *node;
        isl_union_map *executed;
 
+       build = isl_ast_build_copy(build);
+       build = isl_ast_build_set_single_valued(build, 0);
        executed = isl_union_map_reverse(schedule);
        list = generate_code(executed, isl_ast_build_copy(build), 0);
        node = isl_ast_node_from_graft_list(list, build);
+       isl_ast_build_free(build);
 
        return node;
 }

diff --git a/test_inputs/codegen/single_valued.c b/test_inputs/codegen/single_valued.c
new file mode 100644 (file)
index 0000000..aab4854
--- /dev/null
+++ b/test_inputs/codegen/single_valued.c
@@ -0,0 +1,2 @@
+if ((2 * (63 * t1 % 64) + t1 <= 134 && t1 >= 2) || t1 == 1)
+  S(2 * (63 * t1 % 64) + t1);

diff --git a/test_inputs/codegen/single_valued.in b/test_inputs/codegen/single_valued.in
new file mode 100644 (file)
index 0000000..d729942
--- /dev/null
+++ b/test_inputs/codegen/single_valued.in
@@ -0,0 +1,5 @@
+# Check that isl recognizes that the inverse schedule is single-valued
+# and does not end up in an infinite recursion.
+[t1] -> {S[c2] -> [c2]: t1 <= c2 <= 134 and (c2+t1) % 128 = 0 and c2 > 0}
+[t1] -> {: t1 > 0}
+[t1] -> {}