[SCEV] Avoid redundant computations when doing AddRec merge

[mkazantsev]

Summary

When we calculate a product of 2 AddRecs, we end up making quite massive
computations to deduce the operands of resulting AddRec. This process can
be optimized by computing all args of intermediate sum and then calling
getAddExpr once rather than calling getAddExpr with intermediate
result every time a new argument is computed.

[mkazantsev]

Rebased: the patch slightly alters simplification, but in this test the expression is still within reasonable bounds.

[rtereshin]

Do you think it's better to remove the NFC tag from the patch? It doesn't look like it's completely NFC, though, I've tested this out for a major (though, out of tree) GPU target on a very large suite of shaders and found no difference.

What's the compile time impact roughly?

I also think that giving the wrapping flags a thought here (in a sense of preserving / re-deriving them a bit better) is valuable, but I don't have any concrete suggestions unfortunately.

Regardless, LGTM, thanks for doing this.

[mkazantsev]

I expect compile time impact to be zero for majority of cases. It should only affect corner cases at which we reach limit depth during simplifications. For them, depending on simplifications complexity, we save O(N) time simplifying. I don't think it will really be observable on anything other than corner-cases.

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

for (unsigned OtherIdx = Idx+1;
         continue;
 
       bool Overflow = false;
       Type *Ty = AddRec->getType();
       bool LargerThan64Bits = getTypeSizeInBits(Ty) > 64;
       SmallVector<const SCEV*, 7> AddRecOps;
       for (int x = 0, xe = AddRec->getNumOperands() +
              OtherAddRec->getNumOperands() - 1; x != xe && !Overflow; ++x) {
-        const SCEV *Term = getZero(Ty);
+        SmallVector <const SCEV *, 7> SumOps;
         for (int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
           uint64_t Coeff1 = Choose(x, 2*x - y, Overflow);
           for (int z = std::max(y-x, y-(int)AddRec->getNumOperands()+1),
                  ze = std::min(x+1, (int)OtherAddRec->getNumOperands());
                z < ze && !Overflow; ++z) {
             uint64_t Coeff2 = Choose(2*x - y, x-z, Overflow);
             uint64_t Coeff;
             if (LargerThan64Bits)
               Coeff = umul_ov(Coeff1, Coeff2, Overflow);
             else
               Coeff = Coeff1*Coeff2;
             const SCEV *CoeffTerm = getConstant(Ty, Coeff);
             const SCEV *Term1 = AddRec->getOperand(y-z);
             const SCEV *Term2 = OtherAddRec->getOperand(z);
-            Term = getAddExpr(Term, getMulExpr(CoeffTerm, Term1, Term2,
-                                               SCEV::FlagAnyWrap, Depth + 1),
-                              SCEV::FlagAnyWrap, Depth + 1);
+            SumOps.push_back(getMulExpr(CoeffTerm, Term1, Term2,
+                                        SCEV::FlagAnyWrap, Depth + 1));
           }
         }
-        AddRecOps.push_back(Term);
+        if (SumOps.empty())
+          SumOps.push_back(getZero(Ty));
+        AddRecOps.push_back(getAddExpr(SumOps, SCEV::FlagAnyWrap, Depth + 1));
       }
       if (!Overflow) {
         const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRec->getLoop(),
                                               SCEV::FlagAnyWrap);
         if (Ops.size() == 2) return NewAddRec;
         Ops[Idx] = NewAddRec;
         Ops.erase(Ops.begin() + OtherIdx); --OtherIdx;
         OpsModified = true;

llvm/trunk/test/Analysis/ScalarEvolution/binomial-explision.ll

 ; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
 
 ; Check that we don't have unreasonably huge SCEVs and in particular only a
 ; reasonable amount of AddRecs in the notation of %tmp19. If we "simplify" SCEVs
 ; too aggressively, we may end up with huge nested expressions.
 define void @test(i32 %x, i64 %y, i1 %cond) {
 
 ; CHECK: %tmp19 = mul i32 %tmp17, %tmp18
-; CHECK: ((((
+; CHECK: ((((((
 ; CHECK-NOT: (((((
 ; CHECK: %tmp20 = add i32 %tmp19, %x
 
 bb:
   br label %bb1
 
 bb1:                                              ; preds = %bb3, %bb
   %tmp = phi i64 [ %y, %bb ], [ %tmp22, %bb3 ]