[MustExecute] Improve MustExecute to correctly handle loop nest

[Whitney]

Summary

for.outer:
  br for.inner
for.inner:
  LI <loop invariant load instruction>
for.inner.latch:
  br for.inner, for.outer.latch
for.outer.latch:
  br for.outer, for.outer.exit

LI is a loop invariant load instruction that post dominate for.outer, so LI should be able to move out of the loop nest. However, there is a bug in allLoopPathsLeadToBlock().

Current algorithm of allLoopPathsLeadToBlock()

1. get all the transitive predecessors of the basic block LI belongs to (for.inner) ==> for.outer, for.inner.latch
2. if any successors of any of the predecessors are not for.inner or for.inner's predecessors, then return false
3. return true

Although for.inner.latch is for.inner's predecessor, but for.inner dominates for.inner.latch, which means if for.inner.latch is ever executed, for.inner should be as well. It should not return false for cases like this.

[jdoerfert]

LGTM once the two comments are adjusted.

llvm/lib/Analysis/MustExecute.cpp

199 ↗

(On Diff #201311)

The comment should reflect the change.

207 ↗

(On Diff #201311)

The check here is basically testing if the edge is a loop latch. I think the comment should include that.

[Whitney]

Addressed all review comments.

llvm/trunk/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);
 
-  // Make sure that all successors of all predecessors of BB are either:
+  // 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 (auto *Pred : Predecessors) {
     // Predecessor block may throw, so it has a side exit.
     if (blockMayThrow(Pred))
       return false;
+
+    // BB dominates Pred, so if Pred runs, BB must run.
+    // This is true when Pred is a loop latch.
+    if (DT->dominates(BB, Pred))
+      continue;
+
     for (auto *Succ : successors(Pred))
       if (CheckedSuccessors.insert(Succ).second &&
           Succ != BB && !Predecessors.count(Succ))
         // By discharging conditions that are not executed on the 1st iteration,
         // we guarantee that *at least* on the first iteration all paths from
         // header that *may* execute will lead us to the block of interest. So
         // that if we had virtually peeled one iteration away, in this peeled
         // iteration the set of predecessors would contain only paths from

llvm/trunk/test/Analysis/MustExecute/loop-header.ll

next:
   %iv.next = add nsw nuw i32 %iv, 1
   %exit.test = icmp slt i32 %iv, %high
   br i1 %exit.test, label %exit, label %loop
 
 exit:
   ret i1 false
 }
 
-; FIXME: everything in inner loop header should be must execute
-; for outer as well
 define i1 @nested_no_throw(i32* noalias %p, i32 %high) {
 ; CHECK-LABEL: @nested_no_throw
 ; CHECK-LABEL: loop:                                             ; preds = %next
 ; CHECK:         %iv = phi i32 [ 0, %entry ], [ %iv.next, %next ] ; (mustexec in: loop)
 ; CHECK:         br label %inner_loop ; (mustexec in: loop)
 ; CHECK-LABEL: inner_loop:
-; CHECK:         %v = load i32, i32* %p ; (mustexec in: inner_loop)
-; CHECK:         %inner.test = icmp eq i32 %v, 0  ; (mustexec in: inner_loop)
-; CHECK:         br i1 %inner.test, label %inner_loop, label %next  ; (mustexec in: inner_loop)
+; CHECK:         %v = load i32, i32* %p ; (mustexec in 2 loops: inner_loop, loop)
+; CHECK:         %inner.test = icmp eq i32 %v, 0  ; (mustexec in 2 loops: inner_loop, loop)
+; CHECK:         br i1 %inner.test, label %inner_loop, label %next  ; (mustexec in 2 loops: inner_loop, loop)
 ; CHECK-LABEL: next:
 ; CHECK:         %iv.next = add nuw nsw i32 %iv, 1 ; (mustexec in: loop)
 ; CHECK:         %exit.test = icmp slt i32 %iv, %high ; (mustexec in: loop)
 ; CHECK:         br i1 %exit.test, label %exit, label %loop ; (mustexec in: loop)
 
 entry:
   br label %loop