Is this over-approximation in isl_set_get_simple_fixed_box_hull expected?

[Vimal Patel]

Hi all,

When computing a bounding box of `isl_set` using `isl_set_get_simple_fixed_box_hull`, the bounding box is larger than expected. This is the original set:

[p0, p1] -> { C0[i0, i1, i2] : exists (e0 = floor((-p0 + i1)/32): 32e0 = -p0 + i1 and p0 >= 0 and p0 <= 255 and p1 >= 0 and p1 <= 15 and 32i0 >= -31 + p0 and 32i0 <= p0 and i1 >= 0 and i1 <= 31 and i2 >= 64p1 and i2 <= 63 + 64p1) }

and the bounding box returned by `isl_set_get_simple_fixed_box_hull`:

offset: "[p0, p1] -> { C0[(floor((p0)/32)), (0), (64p1)] }" size: "{ C0[1, 32, 64] }"

But the second dimension of the offset and size of the bounding box could have been `p0 mod 32` and 1, respectively.
Is this over-approximation expected? If so, is there any other API to get a more precise box_hull in this case?

Thank you.

[Sven Verdoolaege]

On Tue, Dec 30, 2025 at 03:08:06AM -0800, Vimal Patel wrote:
> Hi all,
>
> When computing a bounding box of `isl_set` using
> `isl_set_get_simple_fixed_box_hull`, the bounding box is larger than
> expected. This is the original set:
> [p0, p1] -> { C0[i0, i1, i2] : exists (e0 = floor((-p0 + i1)/32): 32e0 =
> -p0 + i1 and p0 >= 0 and p0 <= 255 and p1 >= 0 and p1 <= 15 and 32i0 >= -31
> + p0 and 32i0 <= p0 and i1 >= 0 and i1 <= 31 and i2 >= 64p1 and i2 <= 63 +
> 64p1) }
> and the bounding box returned by `isl_set_get_simple_fixed_box_hull`:
> offset: "[p0, p1] -> { C0[(floor((p0)/32)), (0), (64p1)] }" size: "{ C0[1,
> 32, 64] }"
>
> But the second dimension of the offset and size of the bounding box could
> have been `p0 mod 32` and 1, respectively.
> Is this over-approximation expected?

Based on the current implementation in master, yes.
I have some improvements locally. I'll try and extract them.

skimo

[Vimal Patel]

Thank you for the update. Meanwhile is there any other way to get a more accurate bounding box? Maybe computing dimension wise parametric min/max and then constructing bounding box manually?

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

[Uday Bondhugula]

It would appear that one can get the accurate bounding box by computing the parametric min and max for each dimension (projecting out the remaining n-1 dimensional variables) - but you'll get a max and min resp. as the lower and upper bounds, and it'll be parametric. Note that this isn't a fixed_box_hull - isl_set_get_simple_fixed_box_hull is finding a fixed(constant)-size range. In your example, there is a tighter fixed-size range, as you pointed out. But are you looking for a parametric box hull or a fixed one?

-Uday

[Vimal Patel]

Hi Uday,

Thanks for pointing that out. That's correct. I'm actually looking for a fixed sized box hull.

--

---
You received this message because you are subscribed to a topic in the Google Groups "isl Development" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/isl-development/yVkHKaklTck/unsubscribe.
To unsubscribe from this group and all its topics, send an email to isl-developme...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/isl-development/f69b62fd-d8ae-4286-9336-e088be72f953n%40googlegroups.com.

[Sven Verdoolaege]

On Tue, Dec 30, 2025 at 03:08:06AM -0800, Vimal Patel wrote:

> Hi all,
>
> When computing a bounding box of `isl_set` using
> `isl_set_get_simple_fixed_box_hull`, the bounding box is larger than
> expected. This is the original set:
> [p0, p1] -> { C0[i0, i1, i2] : exists (e0 = floor((-p0 + i1)/32): 32e0 =
> -p0 + i1 and p0 >= 0 and p0 <= 255 and p1 >= 0 and p1 <= 15 and 32i0 >= -31
> + p0 and 32i0 <= p0 and i1 >= 0 and i1 <= 31 and i2 >= 64p1 and i2 <= 63 +
> 64p1) }
> and the bounding box returned by `isl_set_get_simple_fixed_box_hull`:
> offset: "[p0, p1] -> { C0[(floor((p0)/32)), (0), (64p1)] }" size: "{ C0[1,
> 32, 64] }"

Try with the latest version.

skimo

[Vimal Patel]

Thanks, Sven, for a super quick resolution.