Affine Map Simplification Bug

MLIR
1

Here are three affine maps:

map1(d0) -> (((d0 floordiv 11) mod 2) * 44 + (d0 mod 11) * 2)

map2(d0) -> (((d0 floordiv 44) mod 2) * 172 + ((d0 floordiv 22) mod 2) * 86 + (d0 mod 22) * 2)

map3(d0) -> (((d0 floordiv 172) mod 2) * 680 + ((d0 floordiv 43) mod 4) * 170 + (d0 mod 43) * 2)

Values of d0 are in the range [0, 22) When I do a composition of these maps, I get the following simplified map (after SimplifyAffineStructures pass):

map3(map2(map1(d0))) -> (d0 * 8 + (d0 floordiv 11) * 256 + ((d0 * 4 + (d0 floordiv 11) * 128) floordiv 43) * 84 - (((d0 * 4 + (d0 floordiv 11) * 128) floordiv 43) floordiv 4) * 680)

The simplification process was wrong. If you try values of d0 = 0..22, you will find different results. The un-simplified maps will output this:

[0, 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 680, 688, 696, 704, 712, 720, 728, 736, 744, 752, 760]

whereas the simplified one will output this:

[0, 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 0, 8, 16, 24, 32, 40, 48, 56, 64, 72, 80]

This suggests that there is a bug in the affine simplification pass. Is there a way to disable these simplifications until a fix is found?

2

Does -canonicalize also yield the wrong output? (-canonicalize also composes affine apply ops.) Can you paste the minimal test case to reproduce this to be sure? (although one could write three affine apply ops with the maps you provided above)

3

Hi @bondhugula, thank you for looking into this. Running that through the --canonicalize pass results in the following composition map:

map3(map2(map1(d0))) -> (d0 * 8 + (d0 floordiv 11) * 256 + ((d0 * 4 + (d0 floordiv 11) * 128) floordiv 43) * 84 - (((d0 * 4 + (d0 floordiv 11) * 128) floordiv 43) floordiv 4) * 680)>

It is different but it yields the same (wrong) results for d0 = 0..22.

[0, 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 0, 8, 16, 24, 32, 40, 48, 56, 64, 72, 80]

4

Since LLVM bugzilla is currently down, can you just paste the minimal MLIR test case here (the valid MLIR snippet that causes the canonicalize bug)? This is nothing specific to -simplify-affine-structures. If that composed map is wrong, this is an issue with the affine map composer.

5

Bugzilla is permanently closed, but GitHub issues are opened on the LLVM project now!

6

@bondhugula – Nothing special for the test case. I am just creating two affine maps and composing one with another one.
auto composedMap = firstMap.compose(secondMap);
Then, I create a third one and compose that one with the result of the first two. You can reproduce this by compose the three maps and comparing the results for values of d0 = 0..22.

I would like to point out that out of 20 tests I have, only one fails. All tests have the same form ie. three maps being composed and only this one fails. All tests differ by the constant values in the maps (the actual scalar values).

7

Any progress replicating the bug?