False Positives and False Negatives in Legality Checks

[Mascinissa]

Hi,

I’ve encountered several instances where TiraLib's schedule.is_legal() function returns incorrect legality assessments, resulting in both false negatives and false positives. I believe many of these cases stem from Tiramisu’s legality checking bugs, though some might be mitigable at the TiraLib level. These issues primarily occur with unconventional transformation patterns or orders.

Environment:

• Benchmarks: Tiramisu's PolyBench commit 804ae6c
• Tiramisu branch: merge_attempt, commit 804ae6c

False Negatives

i.e. Cases where schedule.is_legal() returns True but the schedule is actually illegal

1. Interchanging a parallelized loop. After interchanging a parallelized loop with a non-parallelizable loop, the parallelization tag improperly "sticks" to the loop level rather than the loop itself. For example, if loop i is parallelizable but j isn’t, and we apply Parallelize(i) followed by Interchange(i, j), parallelization incorrectly transfers to j, yet schedule.is_legal() returns True.

tiramisu_program = TiramisuProgram.from_file("function_gemver_MEDIUM_generator.cpp")
schedule = Schedule(tiramisu_program)
schedule.add_optimizations([tiramisu_actions.Parallelization([("x_temp", 0)])])
schedule.add_optimizations([tiramisu_actions.Interchange([("x_temp", 0),("x_temp", 1)])])
schedule.is_legal()  # returns True whereas it should return False

2. Tiling an Unrolled Loop This seems to happen whenever tiling is applied on an unrolled loop

tiramisu_program = TiramisuProgram.from_file("function_3mm_MEDIUM_generator.cpp")
schedule = Schedule(tiramisu_program)
schedule.add_optimizations([tiramisu_actions.Unrolling([("E", 2),8])])
schedule.add_optimizations([tiramisu_actions.TilingGeneral([("E", 1), ("E", 2), 4, 4])])
schedule.is_legal()  # returns True whereas it should return False

3. Unrolling with a factor of 1. This originates from a codegen bug in Tiramisu. This could be reproduced on any unrollable loop

tiramisu_program = TiramisuProgram.from_file("function_seidel2d_MEDIUM_generator.cpp")
schedule = Schedule(tiramisu_program)
schedule.add_optimizations([tiramisu_actions.Unrolling([("comp_A_out", 2),1])])
schedule.is_legal()  # returns True whereas it should return False

4. Unrolling two consecutive loops. This also appears to stem from a Tiramisu codegen bug. Consecutive unrollings don’t produce valid code, but schedule.is_legal() incorrectly passes them.

tiramisu_program = TiramisuProgram.from_file("function_seidel2d_MEDIUM_generator.cpp")
schedule = Schedule(tiramisu_program)
schedule.add_optimizations([tiramisu_actions.Unrolling([("comp_A_out", 1),8])])
schedule.add_optimizations([tiramisu_actions.Unrolling([("comp_A_out", 2),8])])
schedule.is_legal()  # returns True whereas it should return False

5. Unexplained Tiling and Parallelization Conflict Here is a case that I couldn't really grasp. Tiling(L1,L2) on its own returns the right output. P(L0) on its own returns the right output. Combining both (in any order) returns the wrong output but passes legality check.

tiramisu_program = TiramisuProgram.from_file("function_covariance_MEDIUM_generator.cpp")
schedule = Schedule(tiramisu_program)
schedule.add_optimizations([tiramisu_actions.Parallelization([("cov_prod", 0)])])
schedule.add_optimizations([tiramisu_actions.TilingGeneral([("cov_prod", 1), ("cov_prod", 2), 32, 64])])
schedule.is_legal()  # returns True whereas it should return False

False Positives

i.e. cases where schedule.is_legal() returns False whereas the schedule is actually legal

1. in Adi, this particular schedule doesn't pass legality check whereas it's legal.

tiramisu_program = TiramisuProgram.from_file("function_adi_MEDIUM_generator.cpp")
schedule = Schedule(tiramisu_program)
schedule.add_optimizations([tiramisu_actions.TilingGeneral([("p_col", 1), ("p_col", 2), 32, 32])])
schedule.add_optimizations([tiramisu_actions.Parallelization([("p_col", 1)])])
schedule.is_legal()  # returns False whereas it should return True

Interestingly, adding the transformations in a reverse order solves the issue while yielding an identical Halide IR

schedule.add_optimizations([tiramisu_actions.Parallelization([("p_col", 1)])])
schedule.add_optimizations([tiramisu_actions.TilingGeneral([("p_col", 1), ("p_col", 2), 32, 32])])
schedule.is_legal()  # Correctly returns True

I’ve noticed a few additional false positive cases but haven’t yet analyzed them fully. I’ll report them in more detail once I can review further.

Thanks!

[skourta]

Thank you @Mascinissa for the detailed report. Since these are mostly related to Tiramisu I do not think there is much we can do at the library level. If there are any checks or limitations you would like imposed on the transformations please let me know I believe we can add that to avoid these errors.

For FN1, we knew about this a while ago, and I thought Afif had fixed it in his work. It might be worth it to talk with him, as this might be an edge case in his fix.
Did you check if the generated code is correct for the rest of the cases?

Thank you

[Mascinissa]

I retested the examples against the current TiraLib and Tiramisu branches. Five of the six reported cases no longer reproduce; the 3mm case is still open.

Related PRs: TiraLib PR #58, TiraLibCpp PR #10, and Tiramisu PR #422.

1. Gemver — parallelization followed by interchange: fixed. Legality is now checked again after the complete schedule has been applied, so this example correctly returns False. See TiraLib 9ade86a, TiraLibCpp e0b6be2, and Tiramisu d7ad1e8b.

2. 3mm — tiling an unrolled loop: still open. is_legal() still returns True, but the generated program produces an incorrect result. This remains a valid unresolved case from the issue.

3. Seidel2D — unrolling by a factor of 1: fixed. Factor-one unrolling is now treated as a no-op. The generated IR is identical to the unscheduled program, so returning True is now correct. See Tiramisu 5a2e6731.

4. Seidel2D — two consecutive unroll actions: no longer reproduces. The exact example now generates valid code and matches the unscheduled program numerically. No sure at what point this case got fixed.

5. Covariance — parallelization combined with tiling: fixed. Parallelization is now applied to every computation covered by the selected loop instead of only the first one. The combined schedule now produces the correct result. See TiraLib 4f16a31 and TiraLibCpp a666990.

6. ADI — tile followed by parallelization: fixed. Both transformation orders now return True and generate identical Halide IR. This is covered by: TiraLib #43.

I suggest keeping the issue open for case 2.