Preserving or detecting nested divisions

[Shizhi Tang]

Hi there,

Is it possible to keep expressions like `x mod y div z` in a set, map or aff? For example, I can construct a map with the following string:

{[x] -> [floor((x mod 8) / 2)] : 0 <= x < 64}

When I print it out, it becomes:

{ [x] -> [o0] : 0 <= x <= 63 and -1 + x - 2o0 <= 8*floor((x)/8) <= x - 2o0 }

I want an explicit expression of o0, so I convert it into a pw_multi_aff, which becomes:

{ [x] -> [(4 - 3x - floor((1 + x)/2) + 4*floor((1 + 7x)/8))] : 0 <= x <= 63 and 8*floor((1 - x)/8) < -x; [x] -> [(0)] : 0 <= x <= 63 and 8*floor((1 - x)/8) >= -x }

Now it has even two parts. I am wondering whether it is a limitation from the form of affine expressions, or a limitation from isl's implementation? Is it possible to recover the floor((x mod 8) / 2) form from this map?

Thanks in advance!

[Sven Verdoolaege]

On Sat, Jan 13, 2024 at 09:08:00PM -0800, Shizhi Tang wrote:
> Hi there,
>
> Is it possible to keep expressions like `x mod y div z` in a set, map or
> aff? For example, I can construct a map with the following string:
>
> {[x] -> [floor((x mod 8) / 2)] : 0 <= x < 64}
>
> When I print it out, it becomes:
>
> { [x] -> [o0] : 0 <= x <= 63 and -1 + x - 2o0 <= 8*floor((x)/8) <= x - 2o0 }
>
> I want an explicit expression of o0, so I convert it into a pw_multi_aff,
> which becomes:
>
> { [x] -> [(4 - 3x - floor((1 + x)/2) + 4*floor((1 + 7x)/8))] : 0 <= x <= 63
> and 8*floor((1 - x)/8) < -x; [x] -> [(0)] : 0 <= x <= 63 and 8*floor((1 -
> x)/8) >= -x }

Which version of isl are you using and how did you perform the conversion?
I get

>>> isl.map("{ [x] -> [o0] : 0 <= x <= 63 and -1 + x - 2o0 <= 8*floor((x)/8) <= x - 2o0 }").as_pw_multi_aff()
isl.pw_multi_aff("{ [x] -> [(floor((x)/2) - 4*floor((x)/8))] : 0 <= x <= 63 }")

> Now it has even two parts. I am wondering whether it is a limitation from
> the form of affine expressions, or a limitation from isl's implementation?
> Is it possible to recover the floor((x mod 8) / 2) form from this map?

The representation of a set/map gets simplified in various ways.
In some cases this means that explicit representations of some dimensions
get lost.
isl can sometimes recover such explicit representations,
but this is based on heuristics, so not guaranteed to be as simple as possible.

If you need to preserve an explicit representation, it's best
not to convert it to a set/map first.
Also note that there is no internal representation for "mod",
so it will get encoded in terms of "floor".
The AST generator, on the other hand, will try and detect "mod" operations,
but this is again based on heuristics.

skimo

[Shizhi Tang]

Thanks for your timely response.

I am using isl 0.26, via its C API. I can reproduce your result from islpy 2023.2.5. It seems islpy is older. Does this imply a regression bug?

I think the  "{ [x] -> [(floor((x)/2) - 4*floor((x)/8))] : 0 <= x <= 63 }" result from islpy is simple enough for me, and I don't need mod. How can I get this in the C API?  What version of isl is used in islpy?

[Shizhi Tang]

Oh I found islpy 2023.2.5 was release in Oct 14, 2023 (instead of Feb 5). Should it be using isl 0.26? Or is it using the master version?

[Sven Verdoolaege]

On Sun, Jan 14, 2024 at 05:56:57AM -0800, Shizhi Tang wrote:
> Thanks for your timely response.
>
> I am using isl 0.26, via its C API.

Send a minimal (but complete) test case.

> I can reproduce your result from
> islpy 2023.2.5. It seems islpy is older. Does this imply a regression bug?

I get the same result on master as on isl-0.26.

> I think the "{ [x] -> [(floor((x)/2) - 4*floor((x)/8))] : 0 <= x <= 63 }"
> result from islpy is simple enough for me, and I don't need mod. How can I
> get this in the C API? What version of isl is used in islpy?

See https://groups.google.com/g/isl-development/c/hjuoBJAa8J8/m/Rln3kVJvAgAJ

skimo

[Shizhi Tang]

Sorry, it was my fault. I got my LD_LIBRARY_PATH wrong and I was using the older isl version from OS release. Now I got it right on isl 0.26.

Just another following question: I have two equivalent maps, but their pw_multi_aff yields different expression, where one is more complex than the other.

>>> map1 = isl.Map("{[x] -> [floor((x mod 8) / 2)] : 0 <= x < 64}")
>>> map2 = isl.Map("{ [i0] -> [i] : 0 <= i <= 3 and -57 + i0 <= 2i <= 6 + i0 and 8*floor((-2 + i0 - 2i)/8) <= -8 + i0 - 2i }")
>>> map1 == map2
True
>>> map1.as_pw_multi_aff()
PwMultiAff("{ [x] -> [(floor((x)/2) - 4*floor((x)/8))] : 0 <= x <= 63 }")
>>> map2.as_pw_multi_aff()
PwMultiAff("{ [i0] -> [(4 - 3i0 - floor((1 + i0)/2) + 4*floor((1 + 7i0)/8))] : exists (e1: i0 <= 57 and 8*floor((1 - i0)/8) < -i0 and 0 <= e1 <= 3 and 7 + i0 + 8*floor((1 - i0)/8) <= 2e1 <= 6 + i0 and 2e1 <= 8 + i0 + 8*floor((1 - i0)/8)); [i0] -> [(0)] : exists (e1: i0 <= 57 and 8*floor((1 - i0)/8) >= -i0 and 0 <= e1 <= 3 and 2e1 <= 6 + i0 and 8*floor((-2 + i0 - 2e1)/8) <= -8 + i0 - 2e1); [i0] -> [(-28 + i0 - floor((1 + i0)/2))] : 58 <= i0 <= 63 }")

Is there a way to simplify map2 to map1? If not, is there a way to somehow normalize the maps so they can yield the same output?

[Sven Verdoolaege]

On Sun, Jan 14, 2024 at 06:53:34AM -0800, Shizhi Tang wrote:
> Is there a way to simplify map2 to map1? If not, is there a way to somehow
> normalize the maps so they can yield the same output?

Extracting an explicit function is a matter of heuristics so
they may fail to detect particular cases depending
on the representation.
I don't think you can affect that except by extending
the heuristics (or by coincidence).

skimo

[Sven Verdoolaege]

On Sun, Jan 14, 2024 at 06:53:34AM -0800, Shizhi Tang wrote:

> Sorry, it was my fault. I got my LD_LIBRARY_PATH wrong and I was using the
> older isl version from OS release. Now I got it right on isl 0.26.
>
> Just another following question: I have two equivalent maps, but their
> pw_multi_aff yields different expression, where one is more complex than
> the other.
>
> >>> map1 = isl.Map("{[x] -> [floor((x mod 8) / 2)] : 0 <= x < 64}")
> >>> map2 = isl.Map("{ [i0] -> [i] : 0 <= i <= 3 and -57 + i0 <= 2i <= 6 +
> i0 and 8*floor((-2 + i0 - 2i)/8) <= -8 + i0 - 2i }")
> >>> map1 == map2
> True
> >>> map1.as_pw_multi_aff()
> PwMultiAff("{ [x] -> [(floor((x)/2) - 4*floor((x)/8))] : 0 <= x <= 63 }")
> >>> map2.as_pw_multi_aff()
> PwMultiAff("{ [i0] -> [(4 - 3i0 - floor((1 + i0)/2) + 4*floor((1 +
> 7i0)/8))] : exists (e1: i0 <= 57 and 8*floor((1 - i0)/8) < -i0 and 0 <= e1
> <= 3 and 7 + i0 + 8*floor((1 - i0)/8) <= 2e1 <= 6 + i0 and 2e1 <= 8 + i0 +
> 8*floor((1 - i0)/8)); [i0] -> [(0)] : exists (e1: i0 <= 57 and 8*floor((1 -
> i0)/8) >= -i0 and 0 <= e1 <= 3 and 2e1 <= 6 + i0 and 8*floor((-2 + i0 -
> 2e1)/8) <= -8 + i0 - 2e1); [i0] -> [(-28 + i0 - floor((1 + i0)/2))] : 58 <=
> i0 <= 63 }")
>
> Is there a way to simplify map2 to map1? If not, is there a way to somehow
> normalize the maps so they can yield the same output?

I improved the heuristics a bit and now you should get the same result
for the second representation.

skimo