[MustExec][LICM] Handle latch being part of an inner cycle (PR57780)

[nikic]

Summary

The algorithm in allLoopPathsLeadToBlock() does not handle the case where the loop latch is part of the predecessor set correctly: In this case, we may take the backedge and not execute other latch successors. This can happen if the latch is part of an inner cycle.

Fixes https://github.com/llvm/llvm-project/issues/57780.

[mkazantsev]

I need to think more about this particular one, but my general preference would be "do nothing if there is an irreducible loop". Is it an option here?

[nikic]

Rebase over additional tests.

[nikic]

In D134279#3810852, @mkazantsev wrote:

I need to think more about this particular one, but my general preference would be "do nothing if there is an irreducible loop". Is it an option here?

I've given this some more thought, and the irreducible control flow is ultimately not relevant: We only need the latch to be part of an inner cycle. The LICM issue does not reproduce with an inner natural cycle (because we don't hoist instructions from inner loops), but we can see this when testing MustExecute directly.

[nikic]

Ping!

[nikic]

To provide some more context here: What the algorithm essentially does is collect all the predecessors in the loop, and then check that this is a closed set, in the sense that all control flow either stays in the set or goes to the target block. If no loops are involved, then this ensures control flow will eventually hit the target block.

Once loops are involved, we can run into two complications:

1. The issue fixed here: If we have a loop latch in the set, then control flow can escape the set by going to the next loop iteration. However, this "next iteration" distinction gets lost in the current representation, and it looks as if we were staying in the set. This is why the separate check is necessary.

2. Separate issue not addressed by this patch: Control flow might infinitely loop around an inner cycle and thus never reach the target block. Haven't tried to reproduce this, but I suspect that this may not be handled correctly (for non-mustprogress semantics).

[nikic]

Ping :)

[fhahn]

llvm/lib/Analysis/MustExecute.cpp

204

Should this say latch blocks?

Also, predecessors(CurLoop->getHeader() will include non-latch blocks (i.e. predecessors not in the loop). I suppose it doesn't matter in practice as Predecessors only contains loop blocks but it might be possible to include this in the comment somehow?

[fhahn]

LGTM, thanks!

llvm/lib/Analysis/MustExecute.cpp

bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop,
   if (BB == CurLoop->getHeader())
     return true;
 
   // Collect all transitive predecessors of BB in the same loop. This set will
   // be a subset of the blocks within the loop.
   SmallPtrSet<const BasicBlock *, 4> Predecessors;
   collectTransitivePredecessors(CurLoop, BB, Predecessors);
 
+  // Bail out if a latch block is part of the predecessor set. In this case
+  // we may take the backedge to the header and not execute other latch
+  // successors.
+  for (const BasicBlock *Pred : predecessors(CurLoop->getHeader()))
+    // Predecessors only contains loop blocks, so we don't have to worry about
+    // preheader predecessors here.
+    if (Predecessors.contains(Pred))
+      return false;
+
   // Make sure that all successors of, all predecessors of BB which are not
   // dominated by BB, are either:
   // 1) BB,
   // 2) Also predecessors of BB,
   // 3) Exit blocks which are not taken on 1st iteration.
   // Memoize blocks we've already checked.
   SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
   for (const auto *Pred : Predecessors) {

llvm/test/Analysis/MustExecute/pr57780.ll

 ; RUN: opt -disable-output -print-mustexecute < %s 2>&1 | FileCheck %s
 
 @c = global i16 0, align 2
 
-; FIXME: miscompile
 ; CHECK-LABEL: define void @latch_cycle_irreducible
-; CHECK: store i16 5, ptr @c, align 2 ; (mustexec in: loop)
+; CHECK: store i16 5, ptr @c, align 2{{$}}
 define void @latch_cycle_irreducible() {
 entry:
   br label %loop
 
 loop:                                             ; preds = %loop.latch, %entry
   %v = phi i32 [ 10, %entry ], [ 0, %loop.latch ]
   %c = icmp eq i32 %v, 0
   br i1 %c, label %loop.exit, label %loop.cont
 
 loop.cont:                                        ; preds = %loop
   br i1 false, label %loop.irreducible, label %loop.latch
 
 loop.irreducible:                                 ; preds = %loop.latch, %loop.cont
   store i16 5, ptr @c, align 2
   br label %loop.latch
 
 loop.latch:                                       ; preds = %loop.irreducible, %loop.cont
   br i1 false, label %loop.irreducible, label %loop
 
 loop.exit:                                        ; preds = %loop
   ret void
 }
 
-; FIXME: miscompile
 ; CHECK-LABEL: define void @latch_cycle_reducible
-; CHECK: store i16 5, ptr @c, align 2 ; (mustexec in: loop)
+; CHECK: store i16 5, ptr @c, align 2{{$}}
 define void @latch_cycle_reducible() {
 entry:
   br label %loop
 
 loop:                                             ; preds = %loop.latch, %entry
   %v = phi i32 [ 10, %entry ], [ 0, %loop.latch ]
   %c = icmp eq i32 %v, 0
   br i1 %c, label %loop.exit, label %loop2

llvm/test/Transforms/LICM/pr57780.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -licm < %s | FileCheck %s
 
 @c = global i16 0, align 2
 
 ; FIXME: The store should not be hoisted.
 define void @test() {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    store i16 5, ptr @c, align 2
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[V:%.*]] = phi i32 [ 10, [[ENTRY:%.*]] ], [ 0, [[LOOP_LATCH:%.*]] ]
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[V]], 0
 ; CHECK-NEXT:    br i1 [[C]], label [[LOOP_EXIT:%.*]], label [[LOOP_CONT:%.*]]
 ; CHECK:       loop.cont:
 ; CHECK-NEXT:    br i1 false, label [[LOOP_IRREDUCIBLE:%.*]], label [[LOOP_LATCH]]
 ; CHECK:       loop.irreducible:
+; CHECK-NEXT:    store i16 5, ptr @c, align 2
 ; CHECK-NEXT:    br label [[LOOP_LATCH]]
 ; CHECK:       loop.latch:
 ; CHECK-NEXT:    br i1 false, label [[LOOP_IRREDUCIBLE]], label [[LOOP]]
 ; CHECK:       loop.exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop