Stride detection fails in AST generation in presence of floordiv expression

[Vimal Patel]

Hi,

I have two schedule maps:

[N] -> { S[i0] -> [i0] : exists (e0 : i0 = N + 6*e0 and 0 <= e0 <= 1) }
and,
[N] -> { S[i0] -> [i0] : exists (e0 : i0 = floor(N/2) + 6*e0 and 0 <= e0 <= 1) }

I'm trying to generate ASTs for these maps, but stride detection fails
to detect the stride of i0. The generated ASTs with ISL version
01147343-GMP are as follows:

for (int c0 = N; c0 <= N + 6; c0 += 6)
S(c0);

for (int c0 = floord(N, 2); c0 <= floord(N, 2) + 6; c0 += 1)
if ((-N + 2 * c0 + 11) % 12 >= 10)
S(c0);

I want to avoid the `if` condition in the second AST. Is there any
transformation that can be applied to the schedule so that the stride
gets detected, so that the if condition in the AST could be avoided?

I would really appreciate any help in this matter.

Thanks & Regards,
Vimal Patel,
Staff AI Compiler Engineer,
Polymage Labs.

[Sven Verdoolaege]

On Sun, Apr 26, 2026 at 04:05:08PM +0530, Vimal Patel wrote:
> Hi,
>
> I have two schedule maps:
>
> [N] -> { S[i0] -> [i0] : exists (e0 : i0 = N + 6*e0 and 0 <= e0 <= 1) }
> and,
> [N] -> { S[i0] -> [i0] : exists (e0 : i0 = floor(N/2) + 6*e0 and 0 <= e0 <= 1) }
>
> I'm trying to generate ASTs for these maps, but stride detection fails
> to detect the stride of i0. The generated ASTs with ISL version
> 01147343-GMP are as follows:

I'm guessing this is a local version of yours because I don't have that.

> for (int c0 = N; c0 <= N + 6; c0 += 6)
> S(c0);
>
> for (int c0 = floord(N, 2); c0 <= floord(N, 2) + 6; c0 += 1)
> if ((-N + 2 * c0 + 11) % 12 >= 10)
> S(c0);
>
> I want to avoid the `if` condition in the second AST. Is there any
> transformation that can be applied to the schedule so that the stride
> gets detected, so that the if condition in the AST could be avoided?

If you somehow now in advance that this is going to happen,
then you could an extra parameter, say T, with constraint T = floor(N/2)
in the context and then the loop should get generated in terms of T,
at which point you can just plug in T = floor(N/2) in the generated AST.

However, isl should be able to detect such cases with some modifications.
I'll see if I can do that next weekend.

skimo

[Vimal Patel]

Hi Sven,

Thanks for the reply. Yeah, seems like I missed checking the latest version. Also, I think it should be possible to preprocess the constraints, as you suggested, so that there is no floordivs.

> However, isl should be able to detect such cases with some modifications. I'll see if I can do that next weekend.

Thanks, that would be very helpful. Looking forward to it.

Thanks & Regards,
Vimal Patel,

Staff Compiler Engineer,
Polymage Labs.

[Sven Verdoolaege]

On Mon, Apr 27, 2026 at 08:23:39AM +0530, Vimal Patel wrote:
> > However, isl should be able to detect such cases with some modifications.
> I'll see if I can do that next weekend.
>
> Thanks, that would be very helpful. Looking forward to it.

Still needs some cleaning up, but it seems to work.

skimo

diff --git a/include/isl/constraint.h b/include/isl/constraint.h
index a8b1611220..6cd38cef08 100644
--- a/include/isl/constraint.h
+++ b/include/isl/constraint.h
@@ -58,6 +58,11 @@ isl_stat isl_basic_set_foreach_bound_pair(__isl_keep isl_basic_set *bset,
__isl_take isl_constraint *upper,
__isl_take isl_basic_set *bset, void *user), void *user);

+isl_stat isl_basic_set_foreach_opposite_constraint_pair(
+ __isl_keep isl_basic_set *bset,
+ isl_stat (*fn)(__isl_take isl_constraint *c, __isl_take isl_val *gap,
+ void *user), void *user);
+
__isl_give isl_basic_map *isl_basic_map_add_constraint(
__isl_take isl_basic_map *bmap, __isl_take isl_constraint *constraint);
__isl_give isl_basic_set *isl_basic_set_add_constraint(
@@ -111,6 +116,9 @@ __isl_give isl_aff *isl_constraint_get_div(__isl_keep isl_constraint *constraint
__isl_give isl_constraint *isl_constraint_negate(
__isl_take isl_constraint *constraint);

+__isl_give isl_constraint *isl_constraint_drop_all_locals(
+ __isl_take isl_constraint *c);
+
isl_bool isl_constraint_is_equality(__isl_keep isl_constraint *constraint);
isl_bool isl_constraint_is_div_constraint(
__isl_keep isl_constraint *constraint);
diff --git a/isl_constraint.c b/isl_constraint.c
index 31b162e0db..aa6deb3208 100644
--- a/isl_constraint.c
+++ b/isl_constraint.c
@@ -386,6 +386,37 @@ __isl_give isl_local_space *isl_constraint_get_local_space(
return constraint ? isl_local_space_copy(constraint->ls) : NULL;
}

+#undef TYPE
+#define TYPE isl_constraint
+
+#undef FIELD_TYPE
+#define FIELD_TYPE isl_local_space
+#undef FIELD_NAME
+#define FIELD_NAME ls
+#undef NAME
+#define NAME local_space
+
+static
+#include "isl_take_templ.c"
+static
+#include "isl_restore_templ.c"
+
+#undef FIELD_TYPE
+#define FIELD_TYPE isl_vec
+#undef FIELD_NAME
+#define FIELD_NAME v
+#undef NAME
+#define NAME vec
+
+static
+#include "isl_peek_templ.c"
+static
+#include "isl_get_templ.c"
+static
+#include "isl_take_templ.c"
+static
+#include "isl_restore_templ.c"
+
isl_size isl_constraint_dim(__isl_keep isl_constraint *constraint,
enum isl_dim_type type)
{
@@ -639,6 +670,34 @@ __isl_give isl_constraint *isl_constraint_negate(
return constraint;
}

+__isl_give isl_constraint *isl_constraint_drop_all_locals(
+ __isl_take isl_constraint *c)
+{
+ isl_local_space *ls;
+ isl_vec *v;
+ isl_size n_div, dim;
+
+ n_div = isl_constraint_dim(c, isl_dim_div);
+ if (n_div < 0)
+ return isl_constraint_free(c);
+ if (n_div == 0)
+ return c;
+ dim = isl_constraint_dim(c, isl_dim_all);
+ if (dim < 0)
+ return isl_constraint_free(c);
+
+ ls = isl_constraint_take_local_space(c);
+ v = isl_constraint_take_vec(c);
+
+ ls = isl_local_space_drop_dims(ls, isl_dim_div, 0, n_div);
+ v = isl_vec_drop_els(v, 1 + dim - n_div, n_div);
+
+ c = isl_constraint_restore_vec(c, v);
+ c = isl_constraint_restore_local_space(c, ls);
+
+ return c;
+}
+
isl_bool isl_constraint_is_equality(struct isl_constraint *constraint)
{
if (!constraint)
diff --git a/isl_get_templ.c b/isl_get_templ.c
new file mode 100644
index 0000000000..c5025b1880
--- /dev/null
+++ b/isl_get_templ.c
@@ -0,0 +1,9 @@
+#define xFN(TYPE,NAME) TYPE ## _ ## NAME
+#define FN(TYPE,NAME) xFN(TYPE,NAME)
+
+/* Return a copy of the NAME of "obj".
+ */
+__isl_give FIELD_TYPE *FN(FN(TYPE,get),NAME)(__isl_keep TYPE *obj)
+{
+ return FN(FIELD_TYPE,copy)(FN(FN(TYPE,peek),NAME)(obj));
+}
diff --git a/isl_map_simplify.c b/isl_map_simplify.c
index 869a208663..d829ba2251 100644
--- a/isl_map_simplify.c
+++ b/isl_map_simplify.c
@@ -24,6 +24,8 @@
#include <isl_space_private.h>
#include <isl_mat_private.h>
#include <isl_vec_private.h>
+#include <isl_constraint_private.h>
+#include <isl_val_private.h>

#include <bset_to_bmap.c>
#include <bset_from_bmap.c>
@@ -2207,6 +2209,62 @@ __isl_give isl_basic_map *isl_basic_map_remove_duplicate_constraints(
detect_divs);
}

+isl_stat isl_basic_set_foreach_opposite_constraint_pair(
+ __isl_keep isl_basic_set *bset,
+ isl_stat (*fn)(__isl_take isl_constraint *c, __isl_take isl_val *gap,
+ void *user), void *user)
+{
+ struct isl_constraint_index ci;
+ int *opposite;
+ isl_size n;
+ int i;
+ isl_int sum;
+
+ n = isl_basic_set_n_inequality(bset);
+ if (n < 0)
+ return isl_stat_error;
+ if (n < 2)
+ return isl_stat_ok;
+
+ if (setup_constraint_index(&ci, bset) < 0)
+ return isl_stat_error;
+
+ opposite = detect_opposites(&ci, bset);
+ constraint_index_free(&ci);
+
+ if (!opposite)
+ return isl_stat_error;
+ isl_int_init(sum);
+ for (i = 0; i < n; ++i) {
+ int j;
+ isl_constraint *c;
+ isl_ctx *ctx;
+ isl_val *gap;
+
+ if (!opposite[i])
+ continue;
+
+ j = opposite[i] - 1;
+ if (j < i)
+ continue;
+
+ c = isl_basic_set_constraint(isl_basic_set_copy(bset),
+ &bset->ineq[i]);
+ isl_int_add(sum, bset->ineq[i][0], bset->ineq[j][0]);
+ ctx = isl_basic_set_get_ctx(bset);
+ gap = isl_val_int_from_isl_int(ctx, sum);
+ if (fn(c, gap, user))
+ break;
+ }
+
+ isl_int_clear(sum);
+ free(opposite);
+
+ if (i < n)
+ return isl_stat_error;
+ return isl_stat_ok;
+}
+
/* Detect all pairs of inequalities that form an equality.
*
* isl_basic_map_remove_duplicate_constraints detects at most one such pair.
diff --git a/isl_peek_templ.c b/isl_peek_templ.c
new file mode 100644
index 0000000000..623188fcf3
--- /dev/null
+++ b/isl_peek_templ.c
@@ -0,0 +1,11 @@
+#define xFN(TYPE,NAME) TYPE ## _ ## NAME
+#define FN(TYPE,NAME) xFN(TYPE,NAME)
+
+/* Return the NAME of "obj".
+ */
+__isl_keep FIELD_TYPE *FN(FN(TYPE,peek),NAME)(__isl_keep TYPE *obj)
+{
+ if (!obj)
+ return NULL;
+ return obj->FIELD_NAME;
+}
diff --git a/isl_restore_templ.c b/isl_restore_templ.c
new file mode 100644
index 0000000000..a966ae15b6
--- /dev/null
+++ b/isl_restore_templ.c
@@ -0,0 +1,32 @@
+#define xFN(TYPE,NAME) TYPE ## _ ## NAME
+#define FN(TYPE,NAME) xFN(TYPE,NAME)
+
+/* Set the NAME of "obj" to "field",
+ * where the NAME of "obj" may be missing
+ * due to a preceding call to TYPE_take_NAME.
+ * However, in this case, "obj" only has a single reference and
+ * then the call to TYPE_cow has no effect.
+ */
+__isl_give TYPE *FN(FN(TYPE,restore),NAME)(__isl_keep TYPE *obj,
+ __isl_take FIELD_TYPE *field)
+{
+ if (!obj || !field)
+ goto error;
+
+ if (obj->FIELD_NAME == field) {
+ FN(FIELD_TYPE,free)(field);
+ return obj;
+ }
+
+ obj = FN(TYPE,cow)(obj);
+ if (!obj)
+ goto error;
+ FN(FIELD_TYPE,free)(obj->FIELD_NAME);
+ obj->FIELD_NAME = field;
+
+ return obj;
+error:
+ FN(TYPE,free)(obj);
+ FN(FIELD_TYPE,free)(field);
+ return NULL;
+}
diff --git a/isl_stride.c b/isl_stride.c
index df5cacc342..e2b5a5d73c 100644
--- a/isl_stride.c
+++ b/isl_stride.c
@@ -186,6 +186,82 @@ error:
return isl_stat_error;
}

+static isl_stat detect_stride(struct isl_detect_stride_data *data,
+ __isl_take isl_constraint *c,
+ isl_bool (*can_round)(__isl_keep isl_val *denom, void *user),
+ void *user, __isl_give isl_aff *(*round)(__isl_take isl_aff *offset))
+{
+ int i;
+ isl_size n_div;
+ isl_ctx *ctx;
+ isl_stat r = isl_stat_ok;
+ isl_val *v, *stride, *m;
+ isl_bool relevant, valid, has_stride;
+
+ relevant = isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1);
+ if (relevant < 0)
+ goto error;
+ if (!relevant)
+ goto done;
+
+ n_div = isl_constraint_dim(c, isl_dim_div);
+ if (n_div < 0)
+ goto error;
+ ctx = isl_constraint_get_ctx(c);
+ stride = isl_val_zero(ctx);
+ for (i = 0; i < n_div; ++i) {
+ v = isl_constraint_get_coefficient_val(c, isl_dim_div, i);
+ stride = isl_val_gcd(stride, v);
+ }
+
+ v = isl_constraint_get_coefficient_val(c, isl_dim_set, data->pos);
+ m = isl_val_gcd(isl_val_copy(stride), isl_val_copy(v));
+ stride = isl_val_div(stride, isl_val_copy(m));
+ v = isl_val_div(v, isl_val_copy(m));
+
+ valid = can_round(m, user);
+ has_stride = isl_val_gt_si(stride, 1);
+ if (has_stride >= 0 && has_stride && valid >= 0 && valid) {
+ isl_aff *aff;
+ isl_val *gcd, *a, *b;
+
+ gcd = isl_val_gcdext(v, isl_val_copy(stride), &a, &b);
+ isl_val_free(gcd);
+ isl_val_free(b);
+
+ c = isl_constraint_drop_all_locals(c);
+ aff = isl_constraint_get_aff(c);
+ aff = isl_aff_set_coefficient_si(aff, isl_dim_in, data->pos, 0);
+ a = isl_val_neg(a);
+ aff = isl_aff_scale_val(aff, a);
+ aff = isl_aff_scale_down_val(aff, m);
+ aff = round(aff);
+ r = set_stride(data, stride, aff);
+ } else {
+ isl_val_free(stride);
+ isl_val_free(m);
+ isl_val_free(v);
+ }
+
+ if (has_stride < 0)
+error:
+ r = isl_stat_error;
+
+done:
+ isl_constraint_free(c);
+ return r;
+}
+
+static isl_bool always(__isl_keep isl_val *denom, void *user)
+{
+ return isl_bool_true;
+}
+
+static __isl_give isl_aff *no_round(__isl_take isl_aff *offset)
+{
+ return offset;
+}
+
/* Check if constraint "c" imposes any stride on dimension data->pos
* and, if so, update the stride information in "data".
*
@@ -220,74 +296,86 @@ error:
*
* The expression "-a h(p)/g" can therefore be used as offset.
*/
-static isl_stat detect_stride(__isl_take isl_constraint *c, void *user)
+static isl_stat detect_stride_eq(__isl_take isl_constraint *c, void *user)
{
struct isl_detect_stride_data *data = user;
- int i;
- isl_size n_div;
- isl_ctx *ctx;
- isl_stat r = isl_stat_ok;
- isl_val *v, *stride, *m;
- isl_bool is_eq, relevant, has_stride;
+ isl_bool is_eq;

is_eq = isl_constraint_is_equality(c);
- relevant = isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1);
- if (is_eq < 0 || relevant < 0)
+ if (is_eq < 0)
goto error;
- if (!is_eq || !relevant) {
+ if (!is_eq) {
isl_constraint_free(c);
return isl_stat_ok;
}

- n_div = isl_constraint_dim(c, isl_dim_div);
- if (n_div < 0)
- goto error;
- ctx = isl_constraint_get_ctx(c);
- stride = isl_val_zero(ctx);
- for (i = 0; i < n_div; ++i) {
- v = isl_constraint_get_coefficient_val(c, isl_dim_div, i);
- stride = isl_val_gcd(stride, v);
- }
+ return detect_stride(data, c, &always, NULL, &no_round);
+error:
+ isl_constraint_free(c);
+ return isl_stat_error;
+}

- v = isl_constraint_get_coefficient_val(c, isl_dim_set, data->pos);
- m = isl_val_gcd(isl_val_copy(stride), isl_val_copy(v));
- stride = isl_val_div(stride, isl_val_copy(m));
- v = isl_val_div(v, isl_val_copy(m));
+static isl_stat set_detect_stride_eq(__isl_keep isl_set *set, int pos,
+ struct isl_detect_stride_data *data)
+{
+ isl_basic_set *hull;
+ isl_stat res;

- has_stride = isl_val_gt_si(stride, 1);
- if (has_stride >= 0 && has_stride) {
- isl_aff *aff;
- isl_val *gcd, *a, *b;
+ hull = isl_set_affine_hull(isl_set_copy(set));

- gcd = isl_val_gcdext(v, isl_val_copy(stride), &a, &b);
- isl_val_free(gcd);
- isl_val_free(b);
+ res = isl_basic_set_foreach_constraint(hull, &detect_stride_eq, data);

- aff = isl_constraint_get_aff(c);
- for (i = 0; i < n_div; ++i)
- aff = isl_aff_set_coefficient_si(aff,
- isl_dim_div, i, 0);
- aff = isl_aff_set_coefficient_si(aff, isl_dim_in, data->pos, 0);
- aff = isl_aff_remove_unused_divs(aff);
- a = isl_val_neg(a);
- aff = isl_aff_scale_val(aff, a);
- aff = isl_aff_scale_down_val(aff, m);
- r = set_stride(data, stride, aff);
- } else {
- isl_val_free(stride);
- isl_val_free(m);
- isl_val_free(v);
- }
+ isl_basic_set_free(hull);

- isl_constraint_free(c);
- if (has_stride < 0)
- return isl_stat_error;
- return r;
+ return res;
+}
+
+static isl_bool can_round(__isl_keep isl_val *denom, void *user)
+{
+ isl_val *gap = user;
+
+ return isl_val_lt(gap, denom);
+}
+
+static isl_stat detect_stride_ineq(__isl_take isl_constraint *c,
+ __isl_take isl_val *gap, void *user)
+{
+ struct isl_detect_stride_data *data = user;
+ isl_stat res;
+ isl_bool upper;
+
+ upper = isl_constraint_is_upper_bound(c, isl_dim_set, data->pos);
+ if (upper < 0)
+ goto error;
+
+ res = detect_stride(data, c, &can_round, gap,
+ upper ? &isl_aff_floor : &isl_aff_ceil);
+
+ isl_val_free(gap);
+
+ return res;
error:
isl_constraint_free(c);
+ isl_val_free(gap);
return isl_stat_error;
}

+static isl_stat set_detect_stride_ineq(__isl_keep isl_set *set, int pos,
+ struct isl_detect_stride_data *data)
+{
+ isl_basic_set *hull;
+ isl_stat res;
+
+ hull = isl_set_plain_unshifted_simple_hull(isl_set_copy(set));
+
+ res = isl_basic_set_foreach_opposite_constraint_pair(hull,
+ &detect_stride_ineq, data);
+
+ isl_basic_set_free(hull);
+
+ return res;
+}
+
/* Check if the constraints in "set" imply any stride on set dimension "pos" and
* store the results in data->stride and data->offset.
*
@@ -299,15 +387,14 @@ error:
static void set_detect_stride(__isl_keep isl_set *set, int pos,
struct isl_detect_stride_data *data)
{
- isl_basic_set *hull;
-
- hull = isl_set_affine_hull(isl_set_copy(set));
-
data->pos = pos;
data->found = 0;
data->stride = NULL;
data->offset = NULL;
- if (isl_basic_set_foreach_constraint(hull, &detect_stride, data) < 0)
+
+ if (set_detect_stride_eq(set, pos, data) < 0)
+ goto error;
+ if (set_detect_stride_ineq(set, pos, data) < 0)
goto error;

if (!data->found) {
@@ -321,10 +408,8 @@ static void set_detect_stride(__isl_keep isl_set *set, int pos,
data->offset = isl_aff_zero_on_domain(ls);
}
}
- isl_basic_set_free(hull);
return;
error:
- isl_basic_set_free(hull);
data->stride = isl_val_free(data->stride);
data->offset = isl_aff_free(data->offset);
}
diff --git a/isl_take_templ.c b/isl_take_templ.c
new file mode 100644
index 0000000000..384422d243
--- /dev/null
+++ b/isl_take_templ.c
@@ -0,0 +1,24 @@
+#define xFN(TYPE,NAME) TYPE ## _ ## NAME
+#define FN(TYPE,NAME) xFN(TYPE,NAME)
+
+/* Return the NAME of "obj".
+ * This may be either a copy or the NAME itself
+ * if there is only one reference to "obj".
+ * This allows the NAME to be modified inplace
+ * if both the TYPE and its NAME have only a single reference.
+ * The caller is not allowed to modify "obj" between this call and
+ * a subsequent call to TYPE_restore_NAME.
+ * The only exception is that TYPE_free can be called instead.
+ */
+__isl_give FIELD_TYPE *FN(FN(TYPE,take),NAME)(__isl_keep TYPE *obj)
+{
+ FIELD_TYPE *field;
+
+ if (!obj)
+ return NULL;
+ if (obj->ref != 1)
+ return FN(FN(TYPE,get),NAME)(obj);
+ field = obj->FIELD_NAME;
+ obj->FIELD_NAME = NULL;
+ return field;
+}