[SCEV][NFC] Introduce isBasicBlockEntryGuardedByCond

[mkazantsev]

Summary

Currently, we have isLoopEntryGuardedByCond method in SCEV, which
checks that some fact is true if we enter the loop. In fact, this is just a
particular case of more general concept isBasicBlockEntryGuardedByCond
applied to given loop's header. In fact, the logic if this code is largely
independent on the given loop and only cares code above it.

This patch makes this generalization. Now we can query it for any block,
and isBasicBlockEntryGuardedByCond is just a particular case.

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

9455

tab?

9518

I think it would be good to update the comment here, saying that we either start at the loop predecessor, if BB is the header of a loop or at the unique predecessor for other blocks.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

9455

Eeek! It was supposed to be clang-formated...

9518

Thanks for pointing out, I'll checkthe other comments here, too.

[mkazantsev]

Fixed comment.

llvm/lib/Analysis/ScalarEvolution.cpp

9455

I'm not sure what it is, it's all whitespaces in my diff file. Display bug of phabricator?

[mkazantsev]

Ping.

[fhahn]

LGTM, thanks!

llvm/include/llvm/Analysis/ScalarEvolution.h

682

nit: move to previous line?

llvm/lib/Analysis/ScalarEvolution.cpp

9455

Possibly :)

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   const SCEV *getSCEVAtScope(Value *V, const Loop *L);
 
   /// Test whether entry to the loop is protected by a conditional between LHS
   /// and RHS.  This is used to help avoid max expressions in loop trip
   /// counts, and to eliminate casts.
   bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
                                 const SCEV *LHS, const SCEV *RHS);
 
+  /// Test whether entry to the basic block is protected by a conditional
+  /// between LHS
+  /// and RHS.
+  bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB,
+                                      ICmpInst::Predicate Pred, const SCEV *LHS,
+                                      const SCEV *RHS);
+
   /// Test whether the backedge of the loop is protected by a conditional
   /// between LHS and RHS.  This is used to eliminate casts.
   bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
                                    const SCEV *LHS, const SCEV *RHS);
 
   /// Returns the maximum trip count of the loop if it is a single-exit
   /// loop and we can compute a small maximum for that loop.
   ///

llvm/lib/Analysis/ScalarEvolution.cpp

if (DominatingEdge.isSingleEdge()) {
                         BB != ContinuePredicate->getSuccessor(0)))
         return true;
     }
   }
 
   return false;
 }
 
-bool
-ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L,
+bool ScalarEvolution::isBasicBlockEntryGuardedByCond(const BasicBlock *BB,
                                                      ICmpInst::Predicate Pred,
-                                          const SCEV *LHS, const SCEV *RHS) {
-  // Interpret a null as meaning no loop, where there is obviously no guard
-  // (interprocedural conditions notwithstanding).
-  if (!L) return false;
-
+                                                     const SCEV *LHS,
+                                                     const SCEV *RHS) {
   if (VerifyIR)
-    assert(!verifyFunction(*L->getHeader()->getParent(), &dbgs()) &&
+    assert(!verifyFunction(*BB->getParent(), &dbgs()) &&
            "This cannot be done on broken IR!");
 
-  // Both LHS and RHS must be available at loop entry.
-  assert(isAvailableAtLoopEntry(LHS, L) &&
-         "LHS is not available at Loop Entry");
-  assert(isAvailableAtLoopEntry(RHS, L) &&
-         "RHS is not available at Loop Entry");
-
   if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
     return true;
 
   // If we cannot prove strict comparison (e.g. a > b), maybe we can prove
   // the facts (a >= b && a != b) separately. A typical situation is when the
   // non-strict comparison is known from ranges and non-equality is known from
   // dominating predicates. If we are proving strict comparison, we always try
   // to prove non-equality and non-strict comparison separately.
if (ProvingStrictComparison) {
         ProvedNonEquality =
             isImpliedCond(ICmpInst::ICMP_NE, LHS, RHS, Condition, Inverse);
       if (ProvedNonStrictComparison && ProvedNonEquality)
         return true;
     }
     return false;
   };
 
-  // Starting at the loop predecessor, climb up the predecessor chain, as long
+  // Starting at the block's predecessor, climb up the predecessor chain, as long
   // as there are predecessors that can be found that have unique successors
-  // leading to the original header.
-  for (std::pair<const BasicBlock *, const BasicBlock *> Pair(
-           L->getLoopPredecessor(), L->getHeader());
+  // leading to the original block.
+  const Loop *ContainingLoop = LI.getLoopFor(BB);
+  const BasicBlock *PredBB;
+  if (ContainingLoop && ContainingLoop->getHeader() == BB)
+    PredBB = ContainingLoop->getLoopPredecessor();
+  else
+    PredBB = BB->getSinglePredecessor();
+  for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
        Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
-
     if (ProveViaGuard(Pair.first))
       return true;
 
     const BranchInst *LoopEntryPredicate =
         dyn_cast<BranchInst>(Pair.first->getTerminator());
     if (!LoopEntryPredicate ||
         LoopEntryPredicate->isUnconditional())
       continue;
 
     if (ProveViaCond(LoopEntryPredicate->getCondition(),
                      LoopEntryPredicate->getSuccessor(0) != Pair.second))
       return true;
   }
 
   // Check conditions due to any @llvm.assume intrinsics.
   for (auto &AssumeVH : AC.assumptions()) {
     if (!AssumeVH)
       continue;
     auto *CI = cast<CallInst>(AssumeVH);
-    if (!DT.dominates(CI, L->getHeader()))
+    if (!DT.dominates(CI, BB))
       continue;
 
     if (ProveViaCond(CI->getArgOperand(0), false))
       return true;
   }
 
   return false;
 }
 
+bool ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L,
+                                               ICmpInst::Predicate Pred,
+                                               const SCEV *LHS,
+                                               const SCEV *RHS) {
+  // Interpret a null as meaning no loop, where there is obviously no guard
+  // (interprocedural conditions notwithstanding).
+  if (!L)
+    return false;
+
+  // Both LHS and RHS must be available at loop entry.
+  assert(isAvailableAtLoopEntry(LHS, L) &&
+         "LHS is not available at Loop Entry");
+  assert(isAvailableAtLoopEntry(RHS, L) &&
+         "RHS is not available at Loop Entry");
+  return isBasicBlockEntryGuardedByCond(L->getHeader(), Pred, LHS, RHS);
+}
+
 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS,
                                     const SCEV *RHS,
                                     const Value *FoundCondValue, bool Inverse) {
   if (!PendingLoopPredicates.insert(FoundCondValue).second)
     return false;
 
   auto ClearOnExit =
       make_scope_exit([&]() { PendingLoopPredicates.erase(FoundCondValue); });