[SCEV] Introduce field for storing SymbolicMaxNotTaken

[mkazantsev]

Summary

Currently, it 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).

[lebedev.ri]

Looks pretty NFC-iy to me.
LG, but maybe wait a day or two if there's another thoughts.

llvm/include/llvm/Analysis/ScalarEvolution.h

private:
   /// Information about the number of loop iterations for which a loop exit's
   /// branch condition evaluates to the not-taken path.  This is a temporary
   /// pair of exact and max expressions that are eventually summarized in
   /// ExitNotTakenInfo and BackedgeTakenInfo.
   struct ExitLimit {
     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;
 
     /// A set of predicate guards for this ExitLimit. The result is only valid
     /// if all of the predicates in \c Predicates evaluate to 'true' at
     /// run-time.
     SmallPtrSet<const SCEVPredicate *, 4> Predicates;
private:
   };
 
   /// Information about the number of times a particular loop exit may be
   /// reached before exiting the loop.
   struct ExitNotTakenInfo {
     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();
     }
   };
 
   /// Information about the backedge-taken count of a loop. This currently
   /// includes an exact count and a maximum count.

llvm/lib/Analysis/ScalarEvolution.cpp

for (const auto &ENT : ExitNotTaken)
     if (ENT.ExitingBlock == ExitingBlock && ENT.hasAlwaysTruePredicate())
       return ENT.ConstantMaxNotTaken;
 
   return SE->getCouldNotCompute();
 }
 
 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.
 const SCEV *
 ScalarEvolution::BackedgeTakenInfo::getConstantMax(ScalarEvolution *SE) const {
   auto PredicateNotAlwaysTrue = [](const ExitNotTakenInfo &ENT) {
     return !ENT.hasAlwaysTruePredicate();
   };
ScalarEvolution::ExitLimit::ExitLimit(
     : ExactNotTaken(E), ConstantMaxNotTaken(ConstantMaxNotTaken),
       MaxOrZero(MaxOrZero) {
   // If we prove the max count is zero, so is the symbolic bound.  This happens
   // in practice due to differences in a) how context sensitive we've chosen
   // to be and b) how we reason about bounds implied by UB.
   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");
   assert((isa<SCEVCouldNotCompute>(ConstantMaxNotTaken) ||
           isa<SCEVConstant>(ConstantMaxNotTaken)) &&
          "No point in having a non-constant max backedge taken count!");
   for (const auto *PredSet : PredSetList)
     for (const auto *P : *PredSet)
ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
 
   ExitNotTaken.reserve(ExitCounts.size());
   std::transform(ExitCounts.begin(), ExitCounts.end(),
                  std::back_inserter(ExitNotTaken),
                  [&](const EdgeExitInfo &EEI) {
         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)) &&
          "No point in having a non-constant max backedge taken count!");
 }
 
 /// Compute the number of times the backedge of the specified loop will execute.
 ScalarEvolution::BackedgeTakenInfo
ScalarEvolution::computeSymbolicMaxBackedgeTakenCount(const Loop *L) {
 
   // Form an expression for the maximum exit count possible for this loop. We
   // merge the max and exact information to approximate a version of
   // getConstantMaxBackedgeTakenCount which isn't restricted to just constants.
   SmallVector<const SCEV*, 4> ExitCounts;
   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 "
              "dominate latch!");
       ExitCounts.push_back(ExitCount);
     }
   }
   if (ExitCounts.empty())