[LoopFuse] Drop loop dispositions before reassigning blocks to other loop

[mkazantsev]

Summary

This bug was found by recent improvement in SCEV verifier. The code in LoopFuse
directly reassigns blocks to be a part of a different loop, which should automatically
invalidate all related cached loop dispositions.

[mkazantsev]

Keeping drop of these loop dispositions as a separate call generally looks increasingly annoying... I'll see if there is a way to get rid of it.

[nikic]

LGTM

[fhahn]

In D134173#3799159, @mkazantsev wrote:

Keeping drop of these loop dispositions as a separate call generally looks increasingly annoying... I'll see if there is a way to get rid of it.

Hmm, would it make sense to forget loop dispositions as part of forgetLoop? Having to clean them up separately is very easy to forget and also not really clear from the existing documentation.

[mkazantsev]

In D134173#3799177, @fhahn wrote:

In D134173#3799159, @mkazantsev wrote:

Keeping drop of these loop dispositions as a separate call generally looks increasingly annoying... I'll see if there is a way to get rid of it.

Hmm, would it make sense to forget loop dispositions as part of forgetLoop? Having to clean them up separately is very easy to forget and also not really clear from the existing documentation.

I'd be fine with that, but depends on CT. Let's extinguish fire and try to measure it.

[nikic]

In D134173#3799177, @fhahn wrote:

In D134173#3799159, @mkazantsev wrote:

Keeping drop of these loop dispositions as a separate call generally looks increasingly annoying... I'll see if there is a way to get rid of it.

Hmm, would it make sense to forget loop dispositions as part of forgetLoop? Having to clean them up separately is very easy to forget and also not really clear from the existing documentation.

forgetLoop() already clears loop dispositions for values it forgets -- but these are only the values based on loop header phis, so an explicit forgetLoopDispositions() is needed if the disposition of other values changes.

We can't easily clear all dispositions for a loop because of how these maps are indexed -- we can either efficiently clear dispositions for a SCEV or for a Loop, but not both at the same time. This is a recurring problem in SCEV, I wonder if it has some elegant solution. (We basically need a multi-key map where each key part can be efficiently invalidated.)

[mkazantsev]

But we could have a second parallel index, and whenever we cache SCEV-> loop also remember loop->SCEV mapping in other place. Doesn't really sound too complex.

llvm/lib/Transforms/Scalar/LoopFuse.cpp

Loop *performFusion(const FusionCandidate &FC0, const FusionCandidate &FC1) {
     DTU.flush();
 
     // Is there a way to keep SE up-to-date so we don't need to forget the loops
     // and rebuild the information in subsequent passes of fusion?
     // Note: Need to forget the loops before merging the loop latches, as
     // mergeLatch may remove the only block in FC1.
     SE.forgetLoop(FC1.L);
     SE.forgetLoop(FC0.L);
+    SE.forgetLoopDispositions();
 
     // Move instructions from FC0.Latch to FC1.Latch.
     // Note: mergeLatch requires an updated DT.
     mergeLatch(FC0, FC1);
 
     // Merge the loops.
     SmallVector<BasicBlock *, 8> Blocks(FC1.L->blocks());
     for (BasicBlock *BB : Blocks) {
Loop *fuseGuardedLoops(const FusionCandidate &FC0,
     DTU.flush();
 
     // Is there a way to keep SE up-to-date so we don't need to forget the loops
     // and rebuild the information in subsequent passes of fusion?
     // Note: Need to forget the loops before merging the loop latches, as
     // mergeLatch may remove the only block in FC1.
     SE.forgetLoop(FC1.L);
     SE.forgetLoop(FC0.L);
+    SE.forgetLoopDispositions();
 
     // Move instructions from FC0.Latch to FC1.Latch.
     // Note: mergeLatch requires an updated DT.
     mergeLatch(FC0, FC1);
 
     // Merge the loops.
     SmallVector<BasicBlock *, 8> Blocks(FC1.L->blocks());
     for (BasicBlock *BB : Blocks) {

llvm/test/Transforms/LoopFusion/double_loop_nest_inner_guard.ll

 ; RUN: opt -S -loop-fusion < %s 2>&1 | FileCheck %s
-; XFAIL: *
-; REQUIRES: asserts
-; Fails due to incorrect cached loop disposition.
 
 ; Verify that LoopFusion can fuse two double-loop nests with guarded inner
 ; loops. Loops are in canonical form.
 
 @a = common global [10 x [10 x i32]] zeroinitializer
 @b = common global [10 x [10 x i32]] zeroinitializer
 @c = common global [10 x [10 x i32]] zeroinitializer
 

llvm/test/Transforms/LoopFusion/loop_nest.ll

 ; RUN: opt -S -loop-fusion < %s | FileCheck %s
-; XFAIL: *
-; REQUIRES: asserts
-; Fails due to incorrect cached loop disposition.
 ;
 ;    int A[1024][1024];
 ;    int B[1024][1024];
 ;
 ;    #define EXPENSIVE_PURE_COMPUTATION(i) ((i - 3) * (i + 3) % i)
 ;
 ;    void dep_free() {
 ;

llvm/test/Transforms/LoopFusion/triple_loop_nest_inner_guard.ll

 ; RUN: opt -S -loop-fusion < %s 2>&1 | FileCheck %s
-; XFAIL: *
-; REQUIRES: asserts
-; Fails due to incorrect cached loop disposition.
 
 ; Verify that LoopFusion can fuse two triple-loop nests with guarded inner
 ; loops. Loops are in canonical form.
 
 @a = common global [10 x [10 x [10 x i32]]] zeroinitializer
 @b = common global [10 x [10 x [10 x i32]]] zeroinitializer
 @c = common global [10 x [10 x [10 x i32]]] zeroinitializer