[SCEV] Only verify BECounts for reachable loops (PR50523)

[nikic]

Summary

For unreachable loops, any BECount is legal, and since D98706 SCEV can make use of this for loops that are unreachable due to constant branches. To avoid false positives, adjust SCEV verification to only check BECounts in reachable loops.

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

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

13465

Why not just use DT->isReachableFromEntry(L->getHeader())?

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

13465

The problematic case is br i1 false style branches, for which you added special handling in isImpliedCond(). The blocks are reachable in the DT, which does not special-case constant branch conditions.

[mkazantsev]

llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll

2

Can we do both command lines for old & new PM?

[nikic]

llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll

2

Maybe makes sense to land D120551 first, in which case this could be -indvars -verify-scev? I only wrote it this way because currently -verify-scev is effectively ignored.

[mkazantsev]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

13465

Got it, thanks

llvm/lib/Analysis/ScalarEvolution.cpp

struct FindUsedLoops {
 
     bool isDone() const { return false; }
   };
 
   FindUsedLoops F(LoopsUsed);
   SCEVTraversal<FindUsedLoops>(F).visitAll(S);
 }
 
+static void getReachableBlocks(SmallPtrSetImpl<BasicBlock *> &Reachable,
+                               Function &F) {
+  SmallVector<BasicBlock *> Worklist;
+  Worklist.push_back(&F.getEntryBlock());
+  while (!Worklist.empty()) {
+    BasicBlock *BB = Worklist.pop_back_val();
+    if (!Reachable.insert(BB).second)
+      continue;
+
+    const APInt *Cond;
+    BasicBlock *TrueBB, *FalseBB;
+    if (match(BB->getTerminator(),
+              m_Br(m_APInt(Cond), m_BasicBlock(TrueBB), m_BasicBlock(FalseBB))))
+      Worklist.push_back(Cond->isOne() ? TrueBB : FalseBB);
+    else
+      append_range(Worklist, successors(BB));
+  }
+}
+
 void ScalarEvolution::verify() const {
   ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this);
   ScalarEvolution SE2(F, TLI, AC, DT, LI);
 
   SmallVector<Loop *, 8> LoopStack(LI.begin(), LI.end());
 
   // Map's SCEV expressions from one ScalarEvolution "universe" to another.
   struct SCEVMapper : public SCEVRewriteVisitor<SCEVMapper> {
     SCEVMapper(ScalarEvolution &SE) : SCEVRewriteVisitor<SCEVMapper>(SE) {}
 
     const SCEV *visitConstant(const SCEVConstant *Constant) {
       return SE.getConstant(Constant->getAPInt());
     }
 
     const SCEV *visitUnknown(const SCEVUnknown *Expr) {
       return SE.getUnknown(Expr->getValue());
     }
 
     const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
       return SE.getCouldNotCompute();
     }
   };
 
   SCEVMapper SCM(SE2);
+  SmallPtrSet<BasicBlock *, 16> ReachableBlocks;
+  getReachableBlocks(ReachableBlocks, F);
 
   while (!LoopStack.empty()) {
     auto *L = LoopStack.pop_back_val();
     llvm::append_range(LoopStack, *L);
 
+    // Only verify BECounts in reachable loops. For an unreachable loop,
+    // any BECount is legal.
+    if (!ReachableBlocks.contains(L->getHeader()))
+      continue;
+
     auto *CurBECount = SCM.visit(
         const_cast<ScalarEvolution *>(this)->getBackedgeTakenCount(L));
     auto *NewBECount = SE2.getBackedgeTakenCount(L);
 
     if (CurBECount == SE2.getCouldNotCompute() ||
         NewBECount == SE2.getCouldNotCompute()) {
       // NB! This situation is legal, but is very suspicious -- whatever pass
       // change the loop to make a trip count go from could not compute to

llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S -indvars %s | FileCheck %s
+; RUN: opt -S -passes='loop(indvars),verify<scalar-evolution>' %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
 target triple = "x86_64-unknown-linux-gnu"
 
 define i32 @testDiv(i8* %p, i64* %p1) {
 ; CHECK-LABEL: @testDiv(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP1:%.*]]
 ; CHECK:       loop1: