[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

1873 ↗

(On Diff #228750)

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.

1880 ↗

(On Diff #228750)

Looks like this forward declare can be in the cpp.

llvm/lib/Analysis/ScalarEvolution.cpp

1274

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

2946

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

2464

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

2464

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

2464

Will be fixed.

2946

I'll change it to use findExistingSCEVInCache instead.

[ekatz]

Fixed noted issues.

[ekatz]

Ping

[ekatz]

Ping

[ekatz]

Ping

[loladiro]

llvm/lib/Analysis/ScalarEvolution.cpp

2467

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

2467

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

2467

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/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);
+  else {
+    FoldingSetNodeID ID;
+    ID.AddInteger(scAddExpr);
+    for (const SCEV *Op : Ops)
+      ID.AddPointer(Op);
+    void *IP = nullptr;
+    if (SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
+      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;
#endif
   // Sort by complexity, this groups all similar expression types together.
   GroupByComplexity(Ops, &LI, DT);
 
   Flags = StrengthenNoWrapFlags(this, scMulExpr, Ops, Flags);
 
   // Limit recursion calls depth.
   if (Depth > MaxArithDepth || hasHugeExpression(Ops))
     return getOrCreateMulExpr(Ops, Flags);
+  else {
+    FoldingSetNodeID ID;
+    ID.AddInteger(scMulExpr);
+    for (unsigned i = 0, e = Ops.size(); i != e; ++i)
+      ID.AddPointer(Ops[i]);
+    void *IP = nullptr;
+    if (SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
+      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]))

 /// 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) {