isl_aff.c:5204: map is not single-valued

[Michael Kruse]

Hi,

this is a report derived from a crash in Polly:
https://github.com/llvm/llvm-project/issues/190459

isl_pw_multi_aff_from_set reports "map is not single-valued" on a map
that is single-valued.

The map is:

[p_0] -> { MemRef0[i0] : (i0 = 64 + 8p_0 and p_0 < 0) or (exists (e0 =
floor((-8p_0 + i0)/64): 64e0 = -8p_0 + i0 and i0 >= 0 and i0 <= 24)) }

which is equivalent to

[p_0] -> {
MemRef0[0] : (p_0) mod 8 = 0;
MemRef0[8] : (7 + p_0) mod 8 = 0;
MemRef0[16] : (6 + p_0) mod 8 = 0;
MemRef0[24] : (5 + p_0) mod 8 = 0;
MemRef0[32] : (4 + p_0) mod 8 = 0;
MemRef0[40] : (3 + p_0) mod 8 = 0;
MemRef0[48] : (2 + p_0) mod 8 = 0;
MemRef0[56] : (1 + p_0) mod 8 = 0
}

Whether it is reported as "single-valued" depends on which previous
(logically read-only) operations were applied to the set. In the
attached isltrace.c `-DFIX_CRASH` enables such code.

```
$ gcc isltrace.c -I ~/src/isl/include -I
~/build/isl/release_cmake/include ~/build/isl/release_cmake/libisl.a
-o isltrace -lgmp && ./isltrace
### ISL version : isl-0.27-358-g73247f6c-GMP-cmake
### at generation: isl-0.27-89-gdc16f8e3-IMath-32
Crash expected here:
../../../src/isl/isl_aff.c:5204: map is not single-valued
Aborted (core dumped)

$ gcc isltrace.c -I ~/src/isl/include -I
~/build/isl/release_cmake/include ~/build/isl/release_cmake/libisl.a
-o isltrace -DFIX_CRASH -lgmp
$ ./isltrace
$ gcc isltrace.c -I ~/src/isl/include -I
~/build/isl/release_cmake/include ~/build/isl/release_cmake/libisl.a
-o isltrace -DFIX_CRASH -lgmp && ./isltrace
### ISL version : isl-0.27-358-g73247f6c-GMP-cmake
### at generation: isl-0.27-89-gdc16f8e3-IMath-32
Crash expected here:
Not crashed?
```
```

The crash reduces to the attached isltrace-reduced.c

```
gcc isltrace-reduced.c -I ~/src/isl/include -I
~/build/isl/release_cmake/include ~/build/isl/release_cmake/libisl.a
-o isltrace -lgmp && ./isltrace
### ISL version : isl-0.27-358-g73247f6c-GMP-cmake
### at generation: isl-0.27-89-gdc16f8e3-IMath-32
Crash expected here:
../../../src/isl/isl_aff.c:5204: map is not single-valued
Aborted (core dumped)
```

I do not know which call within the FIX_CRASH region changes the
behavior. My best guess so far is that some function after some
analysis sets a flag on a copy of the set which should be logically
transparent, but isl_pw_multi_aff_from_set/ forgets to run that
analysis beforehand.

Michael

--
Tardyzentrismus verboten!

[Sven Verdoolaege]

On Mon, Apr 06, 2026 at 03:00:14AM +0200, Michael Kruse wrote:
> Hi,
>
> this is a report derived from a crash in Polly:
> https://github.com/llvm/llvm-project/issues/190459
>
> isl_pw_multi_aff_from_set reports "map is not single-valued" on a map
> that is single-valued.
>
> The map is:
>
> [p_0] -> { MemRef0[i0] : (i0 = 64 + 8p_0 and p_0 < 0) or (exists (e0 =
> floor((-8p_0 + i0)/64): 64e0 = -8p_0 + i0 and i0 >= 0 and i0 <= 24)) }
>
> which is equivalent to
>
> [p_0] -> {
> MemRef0[0] : (p_0) mod 8 = 0;
> MemRef0[8] : (7 + p_0) mod 8 = 0;
> MemRef0[16] : (6 + p_0) mod 8 = 0;
> MemRef0[24] : (5 + p_0) mod 8 = 0;
> MemRef0[32] : (4 + p_0) mod 8 = 0;
> MemRef0[40] : (3 + p_0) mod 8 = 0;
> MemRef0[48] : (2 + p_0) mod 8 = 0;
> MemRef0[56] : (1 + p_0) mod 8 = 0
> }

I don't quite understand.
Clearly, these two sets are not equivalent.
The first can contain negative elements, e.g.,
[p_0] -> { MemRef0[i0 = -8] : p_0 = -9 }.

Also, the first is _not_ a singleton. For example, for p_0 = -16,
it contains

[p_0] -> { MemRef0[i0 = 0] : p_0 = -16; MemRef0[i0 = -64] : p_0 = -16 }

> Whether it is reported as "single-valued" depends on which previous
> (logically read-only) operations were applied to the set. In the
> attached isltrace.c `-DFIX_CRASH` enables such code.

Are you saying that the set above is incorrectly considered
to be a singleton in the `-DFIX_CRASH` case?

skimo

[Sven Verdoolaege]

On Mon, Apr 06, 2026 at 03:07:56PM +0200, 'Sven Verdoolaege' via isl Development wrote:
> Are you saying that the set above is incorrectly considered
> to be a singleton in the `-DFIX_CRASH` case?

With `-DFIX_CRASH`, isl_pw_multi_aff_from_set is called on
the set

[p_0] -> { MemRef0[i0] : (exists (e0 = floor((-8p_0 + i0)/64): 64e0 = -8p_0 + i0 and i0 >= 32 and i0 <= 56)) or (exists (e0 = floor((-8p_0 + i0)/64): 64e0 = -8p_0 + i0 and i0 >= 0 and i0 <= 24)) }

This one _is_ a singleton.

skimo

[Michael Kruse]

Thanks for having a look I wanted to submit this before going on
travel which is the same reason why I could not immediately respond. I
think I mischaracterized the problem, treating the set before and
after the gist a equivalent. Here is another attempt (new reproducer
attached)

$ gcc isltrace-detecteq.c -I ~/src/isl/include/ ~/src/isl/libisl.a
-lgmp -o isltrace-crash
$ ./isltrace-crash
### ISL version : isl-0.27-368-g88970f3d-GMP-cmake
### at generation: isl-0.27-89-gdc16f8e3-IMath-32
[p_0] -> { MemRef0[i0] : (exists (e0 = floor((-1 - p_0)/8), e1 =
floor((-8p_0 + i0)/64): 64e1 = -8p_0 + i0 and i0 <= 56 and i0 >= 0 and
8e0 >= -8 - p_0 and 8e0 <= -5 - p_0)) or (exists (e0 = floor((3 -
p_0)/8), e1 = floor((-8p_0 + i0)/64): 64e1 = -8p_0 + i0 and i0 <= 88
and i0 >= 32 and 8e0 >= -4 - p_0 and 8e0 < -p_0)) }
[p_0] -> { MemRef0[i0] : (exists (e0 = floor((-1 - p_0)/8), e1 =
floor((-8p_0 + i0)/64): 64e1 = -8p_0 + i0 and i0 <= 56 and i0 >= 0 and
8e0 >= -8 - p_0 and 8e0 <= -5 - p_0)) or (exists (e0 = floor((3 -
p_0)/8), e1 = floor((-8p_0 + i0)/64): 64e1 = -8p_0 + i0 and i0 <= 88
and i0 >= 32 and 8e0 >= -4 - p_0 and 8e0 < -p_0)) }
Crash expected here:

isl_aff.c:5204: map is not single-valued
Aborted (core dumped)

$ gcc isltrace-detecteq.c -I ~/src/isl/include/ ~/src/isl/libisl.a
-lgmp -DDONT_CRASH -o isltrace-pass
$ ./isltrace-pass
### ISL version : isl-0.27-368-g88970f3d-GMP-cmake
### at generation: isl-0.27-89-gdc16f8e3-IMath-32
[p_0] -> { MemRef0[i0] : (exists (e0 = floor((-1 - p_0)/8), e1 =
floor((-8p_0 + i0)/64): 64e1 = -8p_0 + i0 and i0 <= 56 and i0 >= 0 and
8e0 >= -8 - p_0 and 8e0 <= -5 - p_0)) or (exists (e0 = floor((3 -
p_0)/8), e1 = floor((-8p_0 + i0)/64): 64e1 = -8p_0 + i0 and i0 <= 88
and i0 >= 32 and 8e0 >= -4 - p_0 and 8e0 < -p_0)) }

[p_0] -> { MemRef0[i0] : (exists (e0 = floor((-8p_0 + i0)/64): 64e0 =

-8p_0 + i0 and i0 <= 24 and i0 >= 0)) or (exists (e0 = floor((-8p_0 +
i0)/64): 64e0 = -8p_0 + i0 and i0 <= 56 and i0 >= 32)) }

Crash expected here:
Not crashed?

With -DDONT_CRASH, there is another call of isl_set_detect_equalities
on a copy of set479 and immediately discarded. Because it works on a
copy, it should not affect the result of anything else. Yet, it seems
to affect the result of isl_set_gist_params using set479.

Regarding the crash itself, I now think Polly is at fault: It must not
assume that a single-valued set is still single-valued after a gist
operation, which it might not be outside the context. It should apply
isl_multi_pw_aff_gist_params after isl_pw_multi_aff_from_set, not
before. However, it seems weird that the gist operation becomes *less*
powerful with detect_equalities applied (it just returns the original
set).

Michael

Am Mo., 6. Apr. 2026 um 15:24 Uhr schrieb 'Sven Verdoolaege' via isl
Development <isl-dev...@googlegroups.com>:

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "isl Development" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to isl-developme...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/isl-development/20260406132357.GP31921MdfPADPa%40purples.home.



--
Tardyzentrismus verboten!

[Sven Verdoolaege]

On Mon, Apr 20, 2026 at 12:02:16PM +0200, Michael Kruse wrote:
> With -DDONT_CRASH, there is another call of isl_set_detect_equalities
> on a copy of set479 and immediately discarded. Because it works on a
> copy, it should not affect the result of anything else. Yet, it seems
> to affect the result of isl_set_gist_params using set479.

If isl discovers more information about a set (such has implicit
equality constraints), then it may apply that to copies as well
since it doesn't affect the meaning of the set (or the copies).
Now, if you use the sets in *heuristic* operations such as gist,
then a different representation may very well affect the result.

> Regarding the crash itself, I now think Polly is at fault: It must not
> assume that a single-valued set is still single-valued after a gist
> operation, which it might not be outside the context. It should apply
> isl_multi_pw_aff_gist_params after isl_pw_multi_aff_from_set, not
> before. However, it seems weird that the gist operation becomes *less*
> powerful with detect_equalities applied (it just returns the original
> set).

After detecting equality constraints, the set is just

[p_0] -> { MemRef0[i0] : (-8p_0 + i0) mod 64 = 0 and 0 <= i0 <= 56 and (i0 <= 24 or i0 >= 32) }

The gist context is

[p_0] -> { : -4 <= p_0 <= 3 }

There are no constraints in the set that can be simplified away
using this information.

skimo

[Michael Kruse]

Am Mo., 20. Apr. 2026 um 23:53 Uhr schrieb Sven Verdoolaege
<sven.ver...@telenet.be>:

> If isl discovers more information about a set (such has implicit
> equality constraints), then it may apply that to copies as well
> since it doesn't affect the meaning of the set (or the copies).
> Now, if you use the sets in *heuristic* operations such as gist,
> then a different representation may very well affect the result.

Thanks for clarifying ISL's object model.

I don't want to argue to change it, but I think this is a questionable
choice. As a comparison, IEEE floating points has two bit patterns
representing a logical zero. The gist operation of a division.
Heuristically, IEEE fp math assumes that zero represents a very small
number (because of flush-to-zero), and returns either positive or
negative infinity, revealing which internal representation it was. I
would not like it when some unrelated code changes all negative zeros
to positive zero because they all have the same meaning of a
mathematical zero. Fortunately, this would be too ridiculous to
happen.
But of course it could: -ffast-math allows compilers to substitute any
negative and positive zero. Some people really dislike it [1]. Based
on your previous opinion on obscure side-effects [2], I would have
expected that you would share that opinion.

In my case this property of the ISL object model turned the issue into
a Heisenbug [3]: I added diagnostic code to analyze a *copy* of the
isl_set in question. That code happend to indirectly call
detect_equalities on the copy which made the issue disappear.

It also worries me that I could pass a copy of an isl_set to a
third-party library which might store it in its internal data
structure, and during its runtime might or might not trigger
detect_equalities, maybe depending on the phase of the moon [4],
affecting the results of my original copy.

[1] https://discourse.llvm.org/t/rfc-deprecate-ofast/78687/21
[2] https://groups.google.com/g/isl-development/c/ECQsgrDuSNc/m/qrCOXqa4AQAJ
[3] https://en.wikipedia.org/wiki/Heisenbug
[4] https://www.celestialprogramming.com/moonphases.html

> After detecting equality constraints, the set is just
>
> [p_0] -> { MemRef0[i0] : (-8p_0 + i0) mod 64 = 0 and 0 <= i0 <= 56 and (i0 <= 24 or i0 >= 32) }
>
> The gist context is
>
> [p_0] -> { : -4 <= p_0 <= 3 }
>
> There are no constraints in the set that can be simplified away
> using this information.

Understandable, but it was unexpected to me when I was debugging the problem.


Michael

--
Tardyzentrismus verboten!