[SCEV] Add missing cache queries

[ekatz]

Summary

Calculating SCEVs can be cumbersome, and may take very long time (even hours, for very long expressions). To prevent recalculating expressions over and over again, we cache them.
This change add cache queries to key positions, to prevent recalculation of the expressions.

Fix PR43571.

[xbolva00]

compile time numbers? how this speeds up eg. bootstrap of clang?

[ekatz]

In D70097#1741302, @xbolva00 wrote:

compile time numbers? how this speeds up eg. bootstrap of clang?

It seems like a simple performance boost, but this actually fixes PR43571, and I quote, "...it's been nearly 10hrs".
With this change it takes a less than a second.

[reames]

Can you explain where the claimed speed-up is coming from? We were missing cases in the caching before? Is it simply not rebuilding the folding set node multiple times? Something else?

This change appears to have a mix of functional change, and refactoring intermixed. It would make review much easier if you were to split them apart. In particular, a couple of suggestions:

1. The getOrCreateX functions appear to be easily implementable with the new infrastructure. Please do so, as this avoids changes to the (delicate!) flag handling which will otherwise slow review.
2. Separate any removal/movement of caching routine calls into a separate change if possible. (Not sure this is possible, which is the source of confusion.)

llvm/include/llvm/Analysis/ScalarEvolution.h

1906

Having the insert point as part of the key seems odd structurally. I'm also concerned about invalidation if the cache is otherwise modified between setting the IP and using it.

1913

Looks like this forward declare can be in the cpp.

llvm/lib/Analysis/ScalarEvolution.cpp

1271

It seems natural this should be before the rewrite rules?

[ekatz]

Remove unrelated changes. Now only the missing cache queries are present in the patch.

[ekatz]

This comment was removed by ekatz.

[ekatz]

This comment was removed by ekatz.

[ekatz]

This comment was removed by ekatz.

[ekatz]

This comment was removed by ekatz.

[ekatz]

Ping

[ekatz]

Ping

[ekatz]

@reames any comment on the change?

[ekatz]

Ping

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

2939

This code piece is reocurring over the code. Please factor out into a separate method that takes ArrayRef<Value *> or something.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

2461

This is not correct unless you also add no wrap flags into it.

[mkazantsev]

This comment was removed by mkazantsev.

[mkazantsev]

Your code basically duplicates functionality of getOrCreateAddExpr and such, with only difference that you don't create a new SCEV if the lookup failed. I think what you really want to do is to refector it, separating lookup from creation, call the lookup in the beginning and if it succeeded, just return it. That would make sense.

[mkazantsev]

Do you have a simple test demonstrating a claimed speedup?

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

2461

See how it's done in getOrCreateAddExpr.

[ekatz]

In D70097#1849129, @mkazantsev wrote:

Do you have a simple test demonstrating a claimed speedup?

Yes. As described in the summary - this solves bug PR43571.
Please refer to https://bugs.llvm.org/show_bug.cgi?id=43571#c1, to test/reproduce.

[ekatz]

llvm/lib/Analysis/ScalarEvolution.cpp

2461

Will be fixed.

2939

I'll change it to use findExistingSCEVInCache instead.

[ekatz]

Fixed noted issues.

[ekatz]

Ping

[ekatz]

Ping

[ekatz]

Ping

[loladiro]

llvm/lib/Analysis/ScalarEvolution.cpp

2455

I know we do this in a few other places, but why is this legal? Isn't it possible we're still using the old SCEV somewhere, but without the flags?

[ekatz]

llvm/lib/Analysis/ScalarEvolution.cpp

2455

That's a question I also had.. I am not an expert of this code, but I wanted to be consistent with all other places, where this flag is set on the cached value.
Maybe someone more familiar with the code can elaborate.
I guess you can raise that question in llvm-dev, but if it is a bug, then we should open a separate one - specific for this.

[ekatz]

Ping

[ekatz]

Ping

[mkazantsev]

Looks good. Sorry for long delay.

llvm/lib/Analysis/ScalarEvolution.cpp

2455

This has been a weird exception from SCEV immutability for a long enough time. The idea is that all SCEVs should be the same in all places of the program. It means that if in one place we can guarantee nsw for some addition, it should affect other places too. There have been discussions about how to get rid of it, but afaik we don't currently have a conclusive decision. The best way of action here is to follow the existing model.

[hans]

Seems to have broken this bot: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux/builds/26137/

[nickdesaulniers]

Please revert; also broke builds of the Linux kernel: https://bugs.llvm.org/show_bug.cgi?id=45195

[ekatz]

Fixed in rG18eae3312297.

llvm/include/llvm/Analysis/ScalarEvolution.h

private:
 
   /// Look for a SCEV expression with type `SCEVType` and operands `Ops` in
   /// `UniqueSCEVs`.
   ///
   /// The first component of the returned tuple is the SCEV if found and null
   /// otherwise.  The second component is the `FoldingSetNodeID` that was
   /// constructed to look up the SCEV and the third component is the insertion
   /// point.
-  std::tuple<const SCEV *, FoldingSetNodeID, void *>
+  std::tuple<SCEV *, FoldingSetNodeID, void *>
   findExistingSCEVInCache(int SCEVType, ArrayRef<const SCEV *> Ops);
 
   FoldingSet<SCEV> UniqueSCEVs;
   FoldingSet<SCEVPredicate> UniquePreds;
   BumpPtrAllocator SCEVAllocator;
 
   /// This maps loops to a list of SCEV expressions that (transitively) use said
   /// loop.
   DenseMap<const Loop *, SmallVector<const SCEV *, 4>> LoopUsers;
 
   /// Cache tentative mappings from UnknownSCEVs in a Loop, to a SCEV expression
   /// they can be rewritten into under certain predicates.
   DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
            std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
       PredicatedSCEVRewrites;
 
   /// 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.

llvm/lib/Analysis/ScalarEvolution.cpp

assert(isSCEVable(Ty) &&
          "This is not a conversion to a SCEVable type!");
   Ty = getEffectiveSCEVType(Ty);
 
   FoldingSetNodeID ID;
   ID.AddInteger(scTruncate);
   ID.AddPointer(Op);
   ID.AddPointer(Ty);
   void *IP = nullptr;
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
 
   // Fold if the operand is constant.
   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
     return getConstant(
       cast<ConstantInt>(ConstantExpr::getTrunc(SC->getValue(), Ty)));
 
   // trunc(trunc(x)) --> trunc(x)
   if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op))
if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
 
     if (Ops.size() == 1) return Ops[0];
   }
 
   // Limit recursion calls depth.
   if (Depth > MaxArithDepth || hasHugeExpression(Ops))
     return getOrCreateAddExpr(Ops, Flags);
 
+  if (SCEV *S = std::get<0>(findExistingSCEVInCache(scAddExpr, Ops))) {
+    static_cast<SCEVAddExpr *>(S)->setNoWrapFlags(Flags);
+    return S;
+  }
+
   // Okay, check to see if the same value occurs in the operand list more than
   // once.  If so, merge them together into an multiply expression.  Since we
   // sorted the list, these values are required to be adjacent.
   Type *Ty = Ops[0]->getType();
   bool FoundMatch = false;
   for (unsigned i = 0, e = Ops.size(); i != e-1; ++i)
     if (Ops[i] == Ops[i+1]) {      //  X + Y + Y  -->  X + Y*2
       // Scan ahead to count how many equal operands there are.
       unsigned Count = 2;
       while (i+Count != e && Ops[i+Count] == Ops[i])
#endif
   GroupByComplexity(Ops, &LI, DT);
 
   Flags = StrengthenNoWrapFlags(this, scMulExpr, Ops, Flags);
 
   // Limit recursion calls depth.
   if (Depth > MaxArithDepth || hasHugeExpression(Ops))
     return getOrCreateMulExpr(Ops, Flags);
 
+  if (SCEV *S = std::get<0>(findExistingSCEVInCache(scMulExpr, Ops))) {
+    static_cast<SCEVMulExpr *>(S)->setNoWrapFlags(Flags);
+    return S;
+  }
+
   // If there are any constants, fold them together.
   unsigned Idx = 0;
   if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
 
     if (Ops.size() == 2)
       // C1*(C2+V) -> C1*C2 + C1*V
       if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
         // If any of Add's ops are Adds or Muls with a constant, apply this

 /// Get a canonical unsigned division expression, or something simpler if
 /// possible.
 const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
                                          const SCEV *RHS) {
   assert(getEffectiveSCEVType(LHS->getType()) ==
          getEffectiveSCEVType(RHS->getType()) &&
          "SCEVUDivExpr operand types don't match!");
 
+  FoldingSetNodeID ID;
+  ID.AddInteger(scUDivExpr);
+  ID.AddPointer(LHS);
+  ID.AddPointer(RHS);
+  void *IP = nullptr;
+  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
+    return S;
+
   if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
     if (RHSC->getValue()->isOne())
       return LHS;                               // X udiv 1 --> x
     // If the denominator is zero, the result of the udiv is undefined. Don't
     // try to analyze it, because the resolution chosen here may differ from
     // the resolution chosen in other parts of the compiler.
     if (!RHSC->getValue()->isZero()) {
       // Determine if the division can be folded into the operands of
if (!RHSC->getValue()->isZero()) {
           const SCEVConstant *StartC = dyn_cast<SCEVConstant>(AR->getStart());
           if (StartC && !DivInt.urem(StepInt) &&
               getZeroExtendExpr(AR, ExtTy) ==
               getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy),
                             getZeroExtendExpr(Step, ExtTy),
                             AR->getLoop(), SCEV::FlagAnyWrap)) {
             const APInt &StartInt = StartC->getAPInt();
             const APInt &StartRem = StartInt.urem(StepInt);
-            if (StartRem != 0)
-              LHS = getAddRecExpr(getConstant(StartInt - StartRem), Step,
-                                  AR->getLoop(), SCEV::FlagNW);
+            if (StartRem != 0) {
+              const SCEV *NewLHS =
+                  getAddRecExpr(getConstant(StartInt - StartRem), Step,
+              if (LHS != NewLHS) {
+                LHS = NewLHS;
+
+                // Reset the ID to include the new LHS, and check if it is
+                // already cached.
+                ID.clear();
+                ID.AddInteger(scUDivExpr);
+                ID.AddPointer(LHS);
+                ID.AddPointer(RHS);
+                IP = nullptr;
+                if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
+                  return S;
+              }
+            }
           }
         }
       // (A*B)/C --> A*(B/C) if safe and B/C can be folded.
       if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(LHS)) {
         SmallVector<const SCEV *, 4> Operands;
         for (const SCEV *Op : M->operands())
           Operands.push_back(getZeroExtendExpr(Op, ExtTy));
         if (getZeroExtendExpr(M, ExtTy) == getMulExpr(Operands))
if (!RHSC->getValue()->isZero()) {
         Constant *LHSCV = LHSC->getValue();
         Constant *RHSCV = RHSC->getValue();
         return getConstant(cast<ConstantInt>(ConstantExpr::getUDiv(LHSCV,
                                                                    RHSCV)));
       }
     }
   }
 
-  FoldingSetNodeID ID;
-  ID.AddInteger(scUDivExpr);
-  ID.AddPointer(LHS);
-  ID.AddPointer(RHS);
-  void *IP = nullptr;
-  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
   SCEV *S = new (SCEVAllocator) SCEVUDivExpr(ID.Intern(SCEVAllocator),
                                              LHS, RHS);
   UniqueSCEVs.InsertNode(S, IP);
   addToLoopUseLists(S);
   return S;
 }
 
 static const APInt gcd(const SCEVConstant *C1, const SCEVConstant *C2) {
if (StructType *STy = dyn_cast<StructType>(CurTy)) {
       TotalOffset = getAddExpr(TotalOffset, LocalOffset);
     }
   }
 
   // Add the total offset from all the GEP indices to the base.
   return getAddExpr(BaseExpr, TotalOffset, Wrap);
 }
 
-std::tuple<const SCEV *, FoldingSetNodeID, void *>
+std::tuple<SCEV *, FoldingSetNodeID, void *>
 ScalarEvolution::findExistingSCEVInCache(int SCEVType,
                                          ArrayRef<const SCEV *> Ops) {
   FoldingSetNodeID ID;
   void *IP = nullptr;
   ID.AddInteger(SCEVType);
   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
     ID.AddPointer(Ops[i]);
-  return std::tuple<const SCEV *, FoldingSetNodeID, void *>(
+  return std::tuple<SCEV *, FoldingSetNodeID, void *>(
       UniqueSCEVs.FindNodeOrInsertPos(ID, IP), std::move(ID), IP);
 }
 
 const SCEV *ScalarEvolution::getMinMaxExpr(unsigned Kind,
                                            SmallVectorImpl<const SCEV *> &Ops) {
   assert(!Ops.empty() && "Cannot get empty (u|s)(min|max)!");
   if (Ops.size() == 1) return Ops[0];
 #ifndef NDEBUG