[ScalarEvolution]Fix PR18607 resulting in long compilation time and memory usage

[karthikthecool]

Summary

Hi All,
This patch fixes PR18607. Added a threshold beyond which we do not inline mul operands into SCEV.
This seems reasonable as inlining all mul operands without a threshold is resulting in exponential complexity.

Few other modifications include-

1. In compare function for scConstant if LHS and RHS are same we need to return 0 instead of 1
2. Remove redundant code in switch case of scMulExpr in compare function.

I'm new to this part of code. It would be great if someone and review the patch and give inputs if this approach is fine.

Thanks
Karthik Bhat

[karthikthecool]

ping.
Hi All,
Do you think adding threshold is a reasonable approach to solve this problem as we do not have support for pow in SCEV?
Not having a threshold in this case seems to result in infinite loop as in PR18607.

Thanks
Karthik

[arsenm]

lib/Analysis/ScalarEvolution.cpp

1965

Typo Dont

[mehdi_amini]

lib/Analysis/ScalarEvolution.cpp

545

Is it related to the threshold defined in this patch?
Otherwise it should be a separate patch.

594

Same.

1967

512 is you threshold right? Usually I believe we use a cl::opt with a default value for such things.

test/Transforms/IndVarSimplify/pr18607.ll

1

A test without output is not great.
With a cl::opt threshold you should be able to have a simpler case and run it with two threshold and check how the SCEV that is printed changes

[majnemer]

lib/Analysis/ScalarEvolution.cpp

1967

Formatting.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

545

We should not be seeing this, since we unique SCEVConstant s by their content, so two equal SCEVConstant s should have been caught by the pointer equality check in the beginning of the method.

test/Transforms/IndVarSimplify/pr18607.ll

1

If possible, this test should directly test -analyze -scalar-evolution.

89

Not sure that you even need a loop -- just a sequence of multiplications should do the trick.

[arsenm]

May also relate to https://llvm.org/bugs/show_bug.cgi?id=28721

[arsenm]

Please rebase if still relevant

lib/Analysis/ScalarEvolution.cpp

int compare(const SCEV *LHS, const SCEV *RHS) const {
         const SCEVConstant *RC = cast<SCEVConstant>(RHS);
 
         // Compare constant values.
         const APInt &LA = LC->getValue()->getValue();
         const APInt &RA = RC->getValue()->getValue();
         unsigned LBitWidth = LA.getBitWidth(), RBitWidth = RA.getBitWidth();
         if (LBitWidth != RBitWidth)
           return (int)LBitWidth - (int)RBitWidth;
-        return LA.ult(RA) ? -1 : 1;
+        return LA.ult(RA) ? -1 : (LA.eq(RA) ? 0 : 1);
       }
 
       case scAddRecExpr: {
         const SCEVAddRecExpr *LA = cast<SCEVAddRecExpr>(LHS);
         const SCEVAddRecExpr *RA = cast<SCEVAddRecExpr>(RHS);
 
         // Compare addrec loop depths.
         const Loop *LLoop = LA->getLoop(), *RLoop = RA->getLoop();
int compare(const SCEV *LHS, const SCEV *RHS) const {
         const SCEVNAryExpr *LC = cast<SCEVNAryExpr>(LHS);
         const SCEVNAryExpr *RC = cast<SCEVNAryExpr>(RHS);
 
         // Lexicographically compare n-ary expressions.
         unsigned LNumOps = LC->getNumOperands(), RNumOps = RC->getNumOperands();
         if (LNumOps != RNumOps)
           return (int)LNumOps - (int)RNumOps;
 
+        // From here on LNumOps == RNumOps
         for (unsigned i = 0; i != LNumOps; ++i) {
-          if (i >= RNumOps)
-            return 1;
           long X = compare(LC->getOperand(i), RC->getOperand(i));
           if (X != 0)
             return X;
         }
-        return (int)LNumOps - (int)RNumOps;
+        return 0;
       }
 
       case scUDivExpr: {
         const SCEVUDivExpr *LC = cast<SCEVUDivExpr>(LHS);
         const SCEVUDivExpr *RC = cast<SCEVUDivExpr>(RHS);
 
         // Lexicographically compare udiv expressions.
         long X = compare(LC->getLHS(), RC->getLHS());
#endif
   // Skip over the add expression until we get to a multiply.
   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
     ++Idx;
 
   // If there are mul operands inline them all into this expression.
   if (Idx < Ops.size()) {
     bool DeletedMul = false;
     while (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
+      // Dont inline mul into expresssion if resultant Ops becomes too large.
+      // Add a threshold to check the same.
+      if((Ops.size() + Mul->getNumOperands() -1) > 512)
+        break;
       // If we have an mul, expand the mul operands onto the end of the operands
       // list.
       Ops.erase(Ops.begin()+Idx);
       Ops.append(Mul->op_begin(), Mul->op_end());
       DeletedMul = true;
     }
 
     // If we deleted at least one mul, we added operands to the end of the list,

test/Transforms/IndVarSimplify/pr18607.ll

+; RUN: opt < %s -indvars -disable-output -S  
+
+target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v16:16:16-v24:32:32-v32:32:32-v48:64:64-v64:64:64-v96:128:128-v128:128:128-v192:256:256-v256:256:256-v512:512:512-v1024:1024:1024-a0:0:64-f80:32:32"
+
+; Function Attrs: nounwind
+define void @scev_loop(i32 addrspace(1)* noalias %a, i32 addrspace(1)* %c, i32 %iter) #0 {
+entry:
+  %tmp2 = load i32 addrspace(1)* %a, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %rb.0 = phi i32 [ 1, %entry ], [ %tmp388, %for.body ]
+  %ra.0 = phi i32 [ %tmp2, %entry ], [ %tmp385, %for.body ]
+  %storemerge = phi i32 [ 0, %entry ], [ %tmp390, %for.body ]
+  %cmp = icmp ult i32 %storemerge, %iter
+  br i1 %cmp, label %for.body, label %for.exit
+
+for.exit:                                         ; preds = %for.cond
+  %tmp396 = add nsw i32 %ra.0, %rb.0
+  store i32 %tmp396, i32 addrspace(1)* %c, align 4
+  ret void
+
+for.body:                                         ; preds = %for.cond
+  %tmp7 = mul i32 %rb.0, %ra.0
+  %tmp10 = mul i32 %tmp7, %rb.0
+  %tmp13 = mul i32 %tmp10, %tmp7
+  %tmp16 = mul i32 %tmp13, %tmp10
+  %tmp19 = mul i32 %tmp16, %tmp13
+  %tmp22 = mul i32 %tmp19, %tmp16
+  %tmp25 = mul i32 %tmp22, %tmp19
+  %tmp28 = mul i32 %tmp25, %tmp22
+  %tmp31 = mul i32 %tmp28, %tmp25
+  %tmp34 = mul i32 %tmp31, %tmp28
+  %tmp37 = mul i32 %tmp34, %tmp31
+  %tmp40 = mul i32 %tmp37, %tmp34
+  %tmp43 = mul i32 %tmp40, %tmp37
+  %tmp46 = mul i32 %tmp43, %tmp40
+  %tmp49 = mul i32 %tmp46, %tmp43
+  %tmp52 = mul i32 %tmp49, %tmp46
+  %tmp55 = mul i32 %tmp52, %tmp49
+  %tmp58 = mul i32 %tmp55, %tmp52
+  %tmp61 = mul i32 %tmp58, %tmp55
+  %tmp64 = mul i32 %tmp61, %tmp58
+  %tmp67 = mul i32 %tmp64, %tmp61
+  %tmp70 = mul i32 %tmp67, %tmp64
+  %tmp73 = mul i32 %tmp70, %tmp67
+  %tmp76 = mul i32 %tmp73, %tmp70
+  %tmp79 = mul i32 %tmp76, %tmp73
+  %tmp82 = mul i32 %tmp79, %tmp76
+  %tmp85 = mul i32 %tmp82, %tmp79
+  %tmp88 = mul i32 %tmp85, %tmp82
+  %tmp91 = mul i32 %tmp88, %tmp85
+  %tmp94 = mul i32 %tmp91, %tmp88
+  %tmp97 = mul i32 %tmp94, %tmp91
+  %tmp100 = mul i32 %tmp97, %tmp94
+  %tmp103 = mul i32 %tmp100, %tmp97
+  %tmp106 = mul i32 %tmp103, %tmp100
+  %tmp109 = mul i32 %tmp106, %tmp103
+  %tmp112 = mul i32 %tmp109, %tmp106
+  %tmp115 = mul i32 %tmp112, %tmp109
+  %tmp118 = mul i32 %tmp115, %tmp112
+  %tmp121 = mul i32 %tmp118, %tmp115
+  %tmp124 = mul i32 %tmp121, %tmp118
+  %tmp127 = mul i32 %tmp124, %tmp121
+  %tmp130 = mul i32 %tmp127, %tmp124
+  %tmp133 = mul i32 %tmp130, %tmp127
+  %tmp136 = mul i32 %tmp133, %tmp130
+  %tmp139 = mul i32 %tmp136, %tmp133
+  %tmp142 = mul i32 %tmp139, %tmp136
+  %tmp145 = mul i32 %tmp142, %tmp139
+  %tmp148 = mul i32 %tmp145, %tmp142
+  %tmp151 = mul i32 %tmp148, %tmp145
+  %tmp154 = mul i32 %tmp151, %tmp148
+  %tmp157 = mul i32 %tmp154, %tmp151
+  %tmp160 = mul i32 %tmp157, %tmp154
+  %tmp163 = mul i32 %tmp160, %tmp157
+  %tmp166 = mul i32 %tmp163, %tmp160
+  %tmp169 = mul i32 %tmp166, %tmp163
+  %tmp172 = mul i32 %tmp169, %tmp166
+  %tmp175 = mul i32 %tmp172, %tmp169
+  %tmp178 = mul i32 %tmp175, %tmp172
+  %tmp181 = mul i32 %tmp178, %tmp175
+  %tmp184 = mul i32 %tmp181, %tmp178
+  %tmp187 = mul i32 %tmp184, %tmp181
+  %tmp190 = mul i32 %tmp187, %tmp184
+  %tmp193 = mul i32 %tmp190, %tmp187
+  %tmp196 = mul i32 %tmp193, %tmp190
+  %tmp199 = mul i32 %tmp196, %tmp193
+  %tmp202 = mul i32 %tmp199, %tmp196
+  %tmp205 = mul i32 %tmp202, %tmp199
+  %tmp208 = mul i32 %tmp205, %tmp202
+  %tmp211 = mul i32 %tmp208, %tmp205
+  %tmp214 = mul i32 %tmp211, %tmp208
+  %tmp217 = mul i32 %tmp214, %tmp211
+  %tmp220 = mul i32 %tmp217, %tmp214
+  %tmp223 = mul i32 %tmp220, %tmp217
+  %tmp226 = mul i32 %tmp223, %tmp220
+  %tmp229 = mul i32 %tmp226, %tmp223
+  %tmp232 = mul i32 %tmp229, %tmp226
+  %tmp235 = mul i32 %tmp232, %tmp229
+  %tmp238 = mul i32 %tmp235, %tmp232
+  %tmp241 = mul i32 %tmp238, %tmp235
+  %tmp244 = mul i32 %tmp241, %tmp238
+  %tmp247 = mul i32 %tmp244, %tmp241
+  %tmp250 = mul i32 %tmp247, %tmp244
+  %tmp253 = mul i32 %tmp250, %tmp247
+  %tmp256 = mul i32 %tmp253, %tmp250
+  %tmp259 = mul i32 %tmp256, %tmp253
+  %tmp262 = mul i32 %tmp259, %tmp256
+  %tmp265 = mul i32 %tmp262, %tmp259
+  %tmp268 = mul i32 %tmp265, %tmp262
+  %tmp271 = mul i32 %tmp268, %tmp265
+  %tmp274 = mul i32 %tmp271, %tmp268
+  %tmp277 = mul i32 %tmp274, %tmp271
+  %tmp280 = mul i32 %tmp277, %tmp274
+  %tmp283 = mul i32 %tmp280, %tmp277
+  %tmp286 = mul i32 %tmp283, %tmp280
+  %tmp289 = mul i32 %tmp286, %tmp283
+  %tmp292 = mul i32 %tmp289, %tmp286
+  %tmp295 = mul i32 %tmp292, %tmp289
+  %tmp298 = mul i32 %tmp295, %tmp292
+  %tmp301 = mul i32 %tmp298, %tmp295
+  %tmp304 = mul i32 %tmp301, %tmp298
+  %tmp307 = mul i32 %tmp304, %tmp301
+  %tmp310 = mul i32 %tmp307, %tmp304
+  %tmp313 = mul i32 %tmp310, %tmp307
+  %tmp316 = mul i32 %tmp313, %tmp310
+  %tmp319 = mul i32 %tmp316, %tmp313
+  %tmp322 = mul i32 %tmp319, %tmp316
+  %tmp325 = mul i32 %tmp322, %tmp319
+  %tmp328 = mul i32 %tmp325, %tmp322
+  %tmp331 = mul i32 %tmp328, %tmp325
+  %tmp334 = mul i32 %tmp331, %tmp328
+  %tmp337 = mul i32 %tmp334, %tmp331
+  %tmp340 = mul i32 %tmp337, %tmp334
+  %tmp343 = mul i32 %tmp340, %tmp337
+  %tmp346 = mul i32 %tmp343, %tmp340
+  %tmp349 = mul i32 %tmp346, %tmp343
+  %tmp352 = mul i32 %tmp349, %tmp346
+  %tmp355 = mul i32 %tmp352, %tmp349
+  %tmp358 = mul i32 %tmp355, %tmp352
+  %tmp361 = mul i32 %tmp358, %tmp355
+  %tmp364 = mul i32 %tmp361, %tmp358
+  %tmp367 = mul i32 %tmp364, %tmp361
+  %tmp370 = mul i32 %tmp367, %tmp364
+  %tmp373 = mul i32 %tmp370, %tmp367
+  %tmp376 = mul i32 %tmp373, %tmp370
+  %tmp379 = mul i32 %tmp376, %tmp373
+  %tmp382 = mul i32 %tmp379, %tmp376
+  %tmp385 = mul i32 %tmp382, %tmp379
+  %tmp388 = mul i32 %tmp385, %tmp382
+  %tmp390 = add i32 %storemerge, 1
+  br label %for.cond
+}
+
+attributes #0 = { nounwind }