[SCEV] Avoid repeated proveNoSignedWrapViaInduction calls.

[fhahn]

Summary

At the moment, proveNoSignedWrapViaInduction may be called for the
same AddRec a large number of times via getSignExtendExpr. This can have
a severe compile-time impact for very loop-heavy code.

If proveNoSignedWrapViaInduction failed to prove NSW the first time,
it is unlikely to succeed on subsequent tries and the cost doesn't seem
to be justified.

This is the signed version of 8daa338297d533d / D130648.

This can drastically improve compile-time in some excessive cases and
also has a slightly positive compile-time impact on CTMark:

NewPM-O3: -0.06%
NewPM-ReleaseThinLTO: -0.04%
NewPM-ReleaseLTO-g: -0.04%

https://llvm-compile-time-tracker.com/compare.php?from=8daa338297d533db4d1ae8d3770613eb25c29688&to=aed126a196e7a5a9803543d9b4d6bdb233d0009c&stat=instructions

[nikic]

LG

llvm/include/llvm/Analysis/ScalarEvolution.h

private:
   DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
            std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
       PredicatedSCEVRewrites;
 
   /// Set of AddRecs for which proving NUW via an induction has already been
   /// tried.
   SmallPtrSet<const SCEVAddRecExpr *, 16> UnsignedWrapViaInductionTried;
 
+  /// Set of AddRecs for which proving NSW via an induction has already been
+  /// tried.
+  SmallPtrSet<const SCEVAddRecExpr *, 16> SignedWrapViaInductionTried;
+
   /// The head of a linked list of all SCEVUnknown values that have been
   /// allocated. This is used by releaseMemory to locate them all and call
   /// their destructors.
   SCEVUnknown *FirstUnknown = nullptr;
 };
 
 /// Analysis pass that exposes the \c ScalarEvolution for a function.
 class ScalarEvolutionAnalysis

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::proveNoSignedWrapViaInduction(const SCEVAddRecExpr *AR) {
   SCEV::NoWrapFlags Result = AR->getNoWrapFlags();
 
   if (AR->hasNoSignedWrap())
     return Result;
 
   if (!AR->isAffine())
     return Result;
 
+  // This function can be expensive, only try to prove NSW once per AddRec.
+  if (!SignedWrapViaInductionTried.insert(AR).second)
+    return Result;
+
   const SCEV *Step = AR->getStepRecurrence(*this);
   const Loop *L = AR->getLoop();
 
   // Check whether the backedge-taken count is SCEVCouldNotCompute.
   // Note that this serves two purposes: It filters out loops that are
   // simply not analyzable, and it covers the case where this code is
   // being called from within backedge-taken count analysis, such that
   // attempting to ask for the backedge-taken count would likely result

 void ScalarEvolution::forgetMemoizedResultsImpl(const SCEV *S) {
   LoopDispositions.erase(S);
   BlockDispositions.erase(S);
   UnsignedRanges.erase(S);
   SignedRanges.erase(S);
   HasRecMap.erase(S);
   MinTrailingZerosCache.erase(S);
 
-  if (auto *AR = dyn_cast<SCEVAddRecExpr>(S))
+  if (auto *AR = dyn_cast<SCEVAddRecExpr>(S)) {
     UnsignedWrapViaInductionTried.erase(AR);
+    SignedWrapViaInductionTried.erase(AR);
+  }
 
   auto ExprIt = ExprValueMap.find(S);
   if (ExprIt != ExprValueMap.end()) {
     for (Value *V : ExprIt->second) {
       auto ValueIt = ValueExprMap.find_as(V);
       if (ValueIt != ValueExprMap.end())
         ValueExprMap.erase(ValueIt);
     }