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