Make ScalarEvolution::ComputeExitLimit more agressive

[sanjoy]

Summary

Test case included demonstrates a situation where this matters

[artagnon]

Cursory review.

include/llvm/IR/BasicBlock.h

214

s/successir/successor/

217

Slightly tangential: is a hypothetical getSingleSucessor() not useful yet?

lib/Analysis/ScalarEvolution.cpp

4827

Um, pred_size()?

4831

Are you worried that L->getHeader() might be nullptr? Why check Next separately then?

4857–4862

Redundant && MustExecuteLoopHeader -- you do an &= anyway.

lib/IR/BasicBlock.cpp

249

succ_empty()?

252

Probably nicer with a range-based loop or std::all_of.

test/Analysis/ScalarEvolution/compute-exit-limit-aggressively.ll

73

Why have you shown two of these examples with the unknown parameter passed?

[sanjoy]

Replies inline.

include/llvm/IR/BasicBlock.h

214

Will fix.

217

Even if it is, that's not relevant to this patch. But honestly, I don't know.

lib/Analysis/ScalarEvolution.cpp

4827

I can't find a pred_size.

4831

L->getHeader() cannot be nullptr. Given that, I don't follow this comment -- I want to break if Next is nullptr OR Next is L->getHeader(). How do I do that with a single check?

4857–4862

DominatesHeaderIgnoringLoopEntry is not free, and I don't want to call it if MustExecuteLoopHeader is false.

lib/IR/BasicBlock.cpp

249

Again, I cannot find a succ_empty. But I did notice that // No preds. should be // No successors..

252

std::all_of is a good idea. I don't want to make that change in this patch because I want getUniqueSuccessor to be an exact dual of getUniquePredecessor. But I can refactor both in a cleanup change.

test/Analysis/ScalarEvolution/compute-exit-limit-aggressively.ll

73

These are negative tests that demonstrate that the transform does not fire incorrectly.

[sanjoy]

Fix nits in comments.

[hfinkel]

lib/Analysis/ScalarEvolution.cpp

4820

There really should not be any non-trivial "chains" of blocks with unique predecessors and successors once SimplifyCFG has run (as I understand it). What motivates this?

4827

This needs a comment. Why are you bailing out if there is more than one predecessor?

4844

In conclusion, I think this function is both overly limiting and too complicated (it handles a chain case that should not really occur -- although I certainly could be wrong about this).

It is also not quite correct (because you also need to check that none of these blocks have functions that might throw).

I think that a direct general approach would be better. Just walk the predecessor graph starting at BB, bailing out if you hit an edge that leaves the loop, and stopping when you hit the loop header. You also need to check for functions that might throw (this is what LICM does).

[sanjoy]

Thank you for taking out the time to review this!

It is quite possible that what I'm trying to fix can be solved by the right pass order in our frontend, I'll give that a try first before redoing this.

include/llvm/IR/BasicBlock.h

public:
   /// Note that unique predecessor doesn't mean single edge, there can be
   /// multiple edges from the unique predecessor to this block (for example a
   /// switch statement with multiple cases having the same destination).
   BasicBlock *getUniquePredecessor();
   const BasicBlock *getUniquePredecessor() const {
     return const_cast<BasicBlock*>(this)->getUniquePredecessor();
   }
 
+  /// \brief Return the successor of this block if it has a unique successor
+  /// block. Otherwise return a null pointer.
+  ///
+  /// Note that unique successor doesn't mean single edge, there can be
+  /// multiple edges from this block to the unique successor (for example a
+  /// switch statement with multiple cases having the same destination).
+  BasicBlock *getUniqueSuccessor();
+  const BasicBlock *getUniqueSuccessor() const {
+    return const_cast<BasicBlock*>(this)->getUniqueSuccessor();
+  }
+
   //===--------------------------------------------------------------------===//
   /// Instruction iterator methods
   ///
   inline iterator                begin()       { return InstList.begin(); }
   inline const_iterator          begin() const { return InstList.begin(); }
   inline iterator                end  ()       { return InstList.end();   }
   inline const_iterator          end  () const { return InstList.end();   }
 

lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) {
   return BackedgeTakenInfo(ExitCounts, CouldComputeBECount, MaxBECount);
 }
 
 /// ComputeExitLimit - Compute the number of times the backedge of the specified
 /// loop will execute if it exits via the specified block.
 ScalarEvolution::ExitLimit
 ScalarEvolution::ComputeExitLimit(const Loop *L, BasicBlock *ExitingBlock) {
 
+  // Conservatively check if BB dominates the loop header if we ignore the edges
+  // entering the loop.  In other words, given that we are already in the loop,
+  // does execution of BB guarantee the execution of the loop header?
+  auto DominatesHeaderIgnoringLoopEntry = [L](BasicBlock *BB) {
+    // We follow the chain of unique predecessors and successors from BB until
+    // we reach the header.  The header is allowed to have predecessors other
+    // than the basic block we reached it by as long as those are all outside
+    // the loop (i.e. entries into the loop).
+
+    BasicBlock *UniqueSucc = BB;
+    while (true) {
+      if (std::next(pred_begin(UniqueSucc)) != pred_end(UniqueSucc))
+        return false;
+
+      BasicBlock *Next = UniqueSucc->getUniqueSuccessor();
+      if (!Next || Next == L->getHeader())
+        break;
+
+      UniqueSucc = Next;
+    }
+
+    if (UniqueSucc->getUniqueSuccessor() != L->getHeader())
+      return false;
+
+    return std::all_of(pred_begin(L->getHeader()), pred_end(L->getHeader()),
+                       [UniqueSucc, L](BasicBlock *BB) {
+                         return UniqueSucc == BB || !L->contains(BB);
+                       });
+  };
+
   // Okay, we've chosen an exiting block.  See what condition causes us to
   // exit at this block and remember the exit block and whether all other targets
   // lead to the loop header.
   bool MustExecuteLoopHeader = true;
   BasicBlock *Exit = nullptr;
   for (succ_iterator SI = succ_begin(ExitingBlock), SE = succ_end(ExitingBlock);
        SI != SE; ++SI)
     if (!L->contains(*SI)) {
       if (Exit) // Multiple exit successors.
         return getCouldNotCompute();
       Exit = *SI;
-    } else if (*SI != L->getHeader()) {
-      MustExecuteLoopHeader = false;
+    } else if (*SI != L->getHeader() && MustExecuteLoopHeader) {
+      // TODO: DominatesHeaderIgnoringLoopEntry cannot be true for two different
+      // values for *SI so if it has already succeeded for some block != *SI,
+      // then we can substitute DominatesHeaderIgnoringLoopEntry(*SI) with
+      // false.
+      MustExecuteLoopHeader &= DominatesHeaderIgnoringLoopEntry(*SI);
     }
 
   // At this point, we know we have a conditional branch that determines whether
   // the loop is exited.  However, we don't know if the branch is executed each
   // time through the loop.  If not, then the execution count of the branch will
   // not be equal to the trip count of the loop.
   //
   // Currently we check for this by checking to see if the Exit branch goes to

lib/IR/BasicBlock.cpp

for (;PI != E; ++PI) {
     if (*PI != PredBB)
       return nullptr;
     // The same predecessor appears multiple times in the predecessor list.
     // This is OK.
   }
   return PredBB;
 }
 
+/// getUniqueSuccessor - If this basic block has a unique successor block,
+/// return the block, otherwise return a null pointer.
+/// Note that unique successor doesn't mean single edge, there can be
+/// multiple edges from this block to the unique successor (for example
+/// a switch statement with multiple cases having the same destination).
+BasicBlock *BasicBlock::getUniqueSuccessor() {
+  succ_iterator SI = succ_begin(this), E = succ_end(this);
+  if (SI == E) return nullptr; // No successors.
+  BasicBlock *SuccBB = *SI;
+  ++SI;
+  for (;SI != E; ++SI) {
+    if (*SI != SuccBB)
+      return nullptr;
+    // The same successor appears multiple times in the successor list.
+    // This is OK.
+  }
+  return SuccBB;
+}
+
 /// removePredecessor - This method is used to notify a BasicBlock that the
 /// specified Predecessor of the block is no longer able to reach it.  This is
 /// actually not used to update the Predecessor list, but is actually used to
 /// update the PHI nodes that reside in the block.  Note that this should be
 /// called while the predecessor still refers to this block.
 ///
 void BasicBlock::removePredecessor(BasicBlock *Pred,
                                    bool DontDeleteUselessPHIs) {

test/Analysis/ScalarEvolution/compute-exit-limit-aggressively.ll

+; RUN: opt < %s -analyze -scalar-evolution | FileCheck %s
+
+define void @f(i1 %c) {
+; CHECK-LABEL: Classifying expressions for: @f
+ entry:
+  br label %loop
+
+ loop:
+; CHECK: Determining loop execution counts for: @f
+; CHECK-NEXT: Loop %loop: backedge-taken count is 999
+; CHECK-NEXT: Loop %loop: max backedge-taken count is 999
+
+  %idx = phi i32 [ 0, %entry ], [ %idx.inc, %loop.split ]
+  br i1 %c, label %left, label %right
+
+left:
+  br label %continue
+right:
+  br label %continue
+
+continue:
+  %idx.inc = add i32 %idx, 1
+  %next.it = icmp slt i32 %idx.inc, 1000
+  br i1 %next.it, label %loop.split, label %break
+
+ loop.split:
+  br label %loop
+
+ break:
+  ret void
+}
+
+define void @g(i1 %c, i1* %unknown) {
+; CHECK-LABEL: Classifying expressions for: @g
+ entry:
+  br label %loop
+
+ loop:
+; CHECK: Determining loop execution counts for: @g
+; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count.
+; CHECK-NEXT: Loop %loop: Unpredictable max backedge-taken count.
+
+  %idx = phi i32 [ 0, %entry ], [ %idx.inc, %loop.split ], [ %idx.inc, %left ]
+  %idx.inc = add i32 %idx, 1
+  br i1 %c, label %left, label %right
+
+left:
+  %cond = load i1* %unknown
+  br i1 %cond, label %continue, label %loop
+
+right:
+  br label %continue
+
+continue:
+  %next.it = icmp slt i32 %idx.inc, 1000
+  br i1 %next.it, label %loop.split, label %break
+
+ loop.split:
+  br label %loop
+
+ break:
+  ret void
+}
+
+define void @h(i1 %c, i1* %unknown) {
+; CHECK-LABEL: Classifying expressions for: @h
+ entry:
+  br label %loop
+
+ loop:
+; CHECK: Determining loop execution counts for: @h
+; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count.
+; CHECK-NEXT: Loop %loop: Unpredictable max backedge-taken count.
+
+  %idx = phi i32 [ 0, %entry ], [ %idx.inc, %loop.split ]
+  %idx.inc = add i32 %idx, 1
+  br i1 %c, label %left, label %right
+
+left:
+  %cond = load i1* %unknown
+  br i1 %cond, label %continue, label %loop.split
+
+right:
+  br label %continue
+
+continue:
+  %next.it = icmp slt i32 %idx.inc, 1000
+  br i1 %next.it, label %loop.split, label %break
+
+ loop.split:
+  br label %loop
+
+ break:
+  ret void
+}