From 0b74cb42312bfcfdb33c85d33443b2607636431f Mon Sep 17 00:00:00 2001
From: Max Kazantsev <mkazantsev@azul.com>
Date: Fri, 25 Nov 2022 13:10:24 +0700
Subject: [PATCH] [SCEV] Introduce field for storing SymbolicMaxNotTaken. NFCI

ritht is initialized with either exact (if available) or
with constant max exit count. In the future, this can be improved.

Hypothetically this is not an NFC (it is possible that exact is not
known and max is known for a particular exit), but for how we use
it now it seems be an NFC (or at least I could not find an example
where it differs). constant max exit count. In the future, this can
be improved.

Differential Revision: https://reviews.llvm.org/D138699
Reviewed By: lebedev.ri
---
 llvm/include/llvm/Analysis/ScalarEvolution.h |  7 +++++--
 llvm/lib/Analysis/ScalarEvolution.cpp        | 20 ++++++++++++++------
 2 files changed, 19 insertions(+), 8 deletions(-)

diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h
index af61d7f..5ea4bf8 100644
--- a/llvm/include/llvm/Analysis/ScalarEvolution.h
+++ b/llvm/include/llvm/Analysis/ScalarEvolution.h
@@ -1314,6 +1314,7 @@ private:
     const SCEV *ExactNotTaken; // The exit is not taken exactly this many times
     const SCEV *ConstantMaxNotTaken; // The exit is not taken at most this many
                                      // times
+    const SCEV *SymbolicMaxNotTaken;
 
     // Not taken either exactly ConstantMaxNotTaken or zero times
     bool MaxOrZero = false;
@@ -1360,14 +1361,16 @@ private:
     PoisoningVH<BasicBlock> ExitingBlock;
     const SCEV *ExactNotTaken;
     const SCEV *ConstantMaxNotTaken;
+    const SCEV *SymbolicMaxNotTaken;
     SmallPtrSet<const SCEVPredicate *, 4> Predicates;
 
     explicit ExitNotTakenInfo(
         PoisoningVH<BasicBlock> ExitingBlock, const SCEV *ExactNotTaken,
-        const SCEV *ConstantMaxNotTaken,
+        const SCEV *ConstantMaxNotTaken, const SCEV *SymbolicMaxNotTaken,
         const SmallPtrSet<const SCEVPredicate *, 4> &Predicates)
         : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
-          ConstantMaxNotTaken(ConstantMaxNotTaken), Predicates(Predicates) {}
+          ConstantMaxNotTaken(ConstantMaxNotTaken),
+          SymbolicMaxNotTaken(SymbolicMaxNotTaken), Predicates(Predicates) {}
 
     bool hasAlwaysTruePredicate() const {
       return Predicates.empty();
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 8ce175e..0149b8c 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -8560,8 +8560,11 @@ const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
 
 const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
     const BasicBlock *ExitingBlock, ScalarEvolution *SE) const {
-  // FIXME: Need to implement this. Return exact for now.
-  return getExact(ExitingBlock, SE);
+  for (const auto &ENT : ExitNotTaken)
+    if (ENT.ExitingBlock == ExitingBlock && ENT.hasAlwaysTruePredicate())
+      return ENT.SymbolicMaxNotTaken;
+
+  return SE->getCouldNotCompute();
 }
 
 /// getConstantMax - Get the constant max backedge taken count for the loop.
@@ -8611,6 +8614,13 @@ ScalarEvolution::ExitLimit::ExitLimit(
   if (ConstantMaxNotTaken->isZero())
     ExactNotTaken = ConstantMaxNotTaken;
 
+  // FIXME: For now, SymbolicMaxNotTaken is either exact (if available) or
+  // constant max. In the future, we are planning to make it more powerful.
+  if (isa<SCEVCouldNotCompute>(ExactNotTaken))
+    SymbolicMaxNotTaken = ConstantMaxNotTaken;
+  else
+    SymbolicMaxNotTaken = ExactNotTaken;
+
   assert((isa<SCEVCouldNotCompute>(ExactNotTaken) ||
           !isa<SCEVCouldNotCompute>(ConstantMaxNotTaken)) &&
          "Exact is not allowed to be less precise than Max");
@@ -8647,7 +8657,8 @@ ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
         BasicBlock *ExitBB = EEI.first;
         const ExitLimit &EL = EEI.second;
         return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
-                                EL.ConstantMaxNotTaken, EL.Predicates);
+                                EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
+                                EL.Predicates);
   });
   assert((isa<SCEVCouldNotCompute>(ConstantMax) ||
           isa<SCEVConstant>(ConstantMax)) &&
@@ -14752,9 +14763,6 @@ ScalarEvolution::computeSymbolicMaxBackedgeTakenCount(const Loop *L) {
   for (BasicBlock *ExitingBB : ExitingBlocks) {
     const SCEV *ExitCount =
         getExitCount(L, ExitingBB, ScalarEvolution::SymbolicMaximum);
-    if (isa<SCEVCouldNotCompute>(ExitCount))
-      ExitCount = getExitCount(L, ExitingBB,
-                                  ScalarEvolution::ConstantMaximum);
     if (!isa<SCEVCouldNotCompute>(ExitCount)) {
       assert(DT.dominates(ExitingBB, L->getLoopLatch()) &&
              "We should only have known counts for exiting blocks that "
-- 
2.7.4