summaryloggraphiclog1graphiclog2commitcommitdifftreerefseditfork
rawpatchinlineside by side (parent: 18b02e8)
rawpatchinlineside by side (parent: 18b02e8)
| author | Sven Verdoolaege <sven@cerebras.net> | |
| Thu, 16 Feb 2023 10:10:58 +0000 (16 11:10 +0100) | ||
| committer | Sven Verdoolaege <sven@cerebras.net> | |
| Sun, 10 Mar 2024 14:37:39 +0000 (10 15:37 +0100) |
In particular, move the detection of a pair of constraints
that define an integer division into isl_basic_map_extract_output_div,
renaming it to isl_basic_map_try_find_output_div and letting it
return an optional isl_aff.
The resulting isl_basic_map_try_find_output_div behaves similarly
to the isl_basic_map_try_find_output_mod that will be introduced
in the next commit, making it easier to call them in succession.
Signed-off-by: Sven Verdoolaege <sven@cerebras.net>
that define an integer division into isl_basic_map_extract_output_div,
renaming it to isl_basic_map_try_find_output_div and letting it
return an optional isl_aff.
The resulting isl_basic_map_try_find_output_div behaves similarly
to the isl_basic_map_try_find_output_mod that will be introduced
in the next commit, making it easier to call them in succession.
Signed-off-by: Sven Verdoolaege <sven@cerebras.net>
| Makefile.am | patchblobblamehistory | |
| isl_aff.c | patchblobblamehistory | |
| isl_maybe_aff.h | [new file with mode: 0644] | patchblob |
diff --git a/Makefile.am b/Makefile.am
--- a/Makefile.am
+++ b/Makefile.am
isl_map_to_basic_set.c \
isl_mat.c \
isl_mat_private.h \
+ isl_maybe_aff.h \
isl_morph.c \
isl_morph.h \
isl_id.c \
diff --git a/isl_aff.c b/isl_aff.c
--- a/isl_aff.c
+++ b/isl_aff.c
#include <isl/set.h>
#include <isl_val_private.h>
#include <isl_point_private.h>
+#include <isl_maybe_aff.h>
#include <isl_config.h>
#undef EL_BASE
return NULL;
}
-/* Return the integer division expression for the output dimension at "d"
- * taking into account that the output dimension at position "d"
- * can be represented as
+/* Look for a pair of constraints in "hull" that ensure
+ * that output dimension "d" is equal to some integer division expression
+ * in the parameters and input dimensions and
+ * return this expression if found.
*
- * x = floor((e(...) + c1) / m)
+ * In particular, looks for a pair of constraints
+ *
+ * e(...) + c1 - m x >= 0 i.e., m x <= e(...) + c1
+ *
+ * and
+ *
+ * -e(...) + c2 + m x >= 0 i.e., m x >= e(...) - c2
*
- * given that constraint "i" is of the form
+ * where m > 1 and e only depends on parameters and input dimensions,
+ * and such that
+ *
+ * c1 + c2 < m i.e., -c2 >= c1 - (m - 1)
*
- * e(...) + c1 - m x >= 0
+ * If such a pair of constraints can be found
+ * then
+ *
+ * x = floor((e(...) + c1) / m)
*
* with e(...) an expression that does not involve any other output dimensions.
*
- * The constraint "i" is guaranteed by the caller not to involve
+ * Note that we know that
+ *
+ * c1 + c2 >= 1
+ *
+ * If c1 + c2 were 0, then we would have detected an equality during
+ * simplification. If c1 + c2 were negative, then we would have detected
+ * a contradiction.
+ *
+ * The constraint defining the integer division is guaranteed not to involve
* any local variables without a known expression, but such local variables
* may appear in other constraints. They therefore need to be removed
* during the construction of the affine expression.
*/
-static __isl_give isl_aff *isl_basic_map_extract_output_div(
- __isl_keep isl_basic_map *hull, int d, int i)
+static __isl_give isl_maybe_isl_aff isl_basic_map_try_find_output_div(
+ __isl_keep isl_basic_map *hull, int d)
{
+ isl_size i;
+ isl_size n_ineq;
+ isl_maybe_isl_aff res = { isl_bool_false, NULL };
isl_local_space *ls;
isl_aff *aff;
isl_vec *v;
isl_bool is_set;
+ n_ineq = isl_basic_map_n_inequality(hull);
+ if (n_ineq < 0)
+ goto error;
+
+ i = isl_basic_map_find_output_upper_div_constraint(hull, d);
+ if (i < 0)
+ goto error;
+ if (i >= n_ineq)
+ return res;
+
is_set = isl_basic_map_is_set(hull);
if (is_set < 0)
hull = isl_basic_map_free(hull);
else
aff = isl_aff_domain_factor_domain(aff);
- return aff;
+ res.valid = isl_bool_true;
+ res.value = aff;
+ return res;
+error:
+ res.valid = isl_bool_error;
+ return res;
}
/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
*
* Sort the constraints first to make it easier to find such pairs
* of constraints.
- *
- * In particular, if we can find two constraints
- *
- * e(...) + c1 - m x >= 0 i.e., m x <= e(...) + c1
- *
- * and
- *
- * -e(...) + c2 + m x >= 0 i.e., m x >= e(...) - c2
- *
- * where m > 1 and e only depends on parameters and input dimensions,
- * and such that
- *
- * c1 + c2 < m i.e., -c2 >= c1 - (m - 1)
- *
- * then we know that we can take
- *
- * x = floor((e(...) + c1) / m)
- *
- * without having to perform any computation.
- *
- * Note that we know that
- *
- * c1 + c2 >= 1
- *
- * If c1 + c2 were 0, then we would have detected an equality during
- * simplification. If c1 + c2 were negative, then we would have detected
- * a contradiction.
*/
static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_check_div(
__isl_take isl_map *map)
{
int d;
isl_size dim;
- isl_size i;
- isl_size n_ineq;
isl_basic_map *hull;
hull = isl_map_unshifted_simple_hull(isl_map_copy(map));
hull = isl_basic_map_sort_constraints(hull);
dim = isl_map_dim(map, isl_dim_out);
- n_ineq = isl_basic_map_n_inequality(hull);
- if (dim < 0 || n_ineq < 0)
+ if (dim < 0)
goto error;
dim = isl_map_dim(map, isl_dim_out);
for (d = 0; d < dim; ++d) {
- isl_aff *sub;
+ isl_maybe_isl_aff sub;
- i = isl_basic_map_find_output_upper_div_constraint(hull, d);
- if (i < 0)
+ sub = isl_basic_map_try_find_output_div(hull, d);
+ if (sub.valid < 0)
goto error;
- if (i >= n_ineq)
+ if (!sub.valid)
continue;
- sub = isl_basic_map_extract_output_div(hull, d, i);
isl_basic_map_free(hull);
- return pw_multi_aff_from_map_plug_in(map, d, sub);
+ return pw_multi_aff_from_map_plug_in(map, d, sub.value);
}
isl_basic_map_free(hull);
return pw_multi_aff_from_map_base(map);
diff --git a/isl_maybe_aff.h b/isl_maybe_aff.h
--- /dev/null
+++ b/isl_maybe_aff.h
@@ -0,0 +1,10 @@
+#ifndef ISL_MAYBE_AFF_H
+#define ISL_MAYBE_AFF_H
+
+#include <isl/aff_type.h>
+
+#define ISL_TYPE isl_aff
+#include <isl/maybe_templ.h>
+#undef ISL_TYPE
+
+#endif