diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h
--- a/llvm/include/llvm/Analysis/ScalarEvolution.h
+++ b/llvm/include/llvm/Analysis/ScalarEvolution.h
@@ -1314,6 +1314,7 @@
     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 @@
     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
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -8560,8 +8560,11 @@
 
 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 @@
   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 @@
         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 @@
   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 "