[LSR] Add a cap for reassociation of AllFixupsOutsideLoop type LSRUse to protect compile time

[wmi]

Summary

In PR32043, we saw a testcase containing a AllFixupsOutsideLoop type LSRUse with huge SCEVAddExpr. LSRInstance::GenerateReassociations generates lots of new formula for the LSRUse because of the huge AddExpr, and causes compilation to hang.

Since AllFixupsOutsideLoop type LSRUses are outside of current loop, reassociation for them should have much less impact compared with that for normal LSRUses. The fix is to add a cap in reassociation if the LSRUse is of AllFixupsOutsideLoop type. I admit this is a workround. AllFixupsOutsideLoop LSRUse needs to be handled in a better way to reduce compile time and improve LSR results.

No test because I am not sure the potential hanging test from PR32043 is proper to be added.

[davide]

Probably this is OK as stopgap solution but I'm generally very wary of adding cutoffs to the code as they add technical debt etc..

[davide]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

3429

How did you chose this cap, BTW?
Maybe we should do some measurements and pick a less arbitrary value?

[davide]

Also, I think the test from the PR (after some polishing, maybe) is good to add. If somebody removes these lines at least all (or a subset of) the bots will timeout and we'll notice the regression.

[wmi]

I don't like a hanging test to be killed after timeout. I will try to create another testcase by checking the LSR trace.

lib/Transforms/Scalar/LoopStrengthReduce.cpp

3429

On one side, for AddOps.size()==5, even without the workaround, the compile time will not bloat up too much, so I think it can cover the cases suffering compile time issue. On the other side, not many cases have very large AddOps numbers. I choose 5 which is not a too small number so it will not kick in frequently. Since current model handling AllFixupsOutsideLoop is very imprecise, I think it is better to just fix the compile time issue and don't change the existing code.

I found no regressions using some internal benchmarks.

[davide]

@qcolombet what do you think?

[wmi]

Add a testcase by checking the LSR debug output.

[wmi]

Fixed a typo in the testcase.

[sanjoy]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

3430

I'm not too familiar with LSR, but this looks pretty ad-hoc -- why can't the same compile-time blowup happen for an LSRUse with AllFixupsOutsideLoop = false?

[davide]

Wei, any progress on this? We should either commit a workaround or revert the patchset to unblock folks.

[atrick]

LSR is fundamentally combinatorial. It relies on arbitrary pruning. I don't like it, but that's the way it is, and we need to guard against pathological cases. I just wonder why you complete bypass the reassociation code instead of simply limiting the number of expressions that participate.

[wmi]

Andy,

Thanks for the comment.

I just wonder why you complete bypass the reassociation code instead of simply limiting the number of expressions that participate.

Because I feel it brings less uncertainty about the LSR result. If I limit the number of expressions that participate, suppose there is a candidate formula matters for the final LSR result, whether it will be used depends on when it is seen and it brings some uncertainty to the LSR result.

Another reason is, for LSRUse with AllFixupsOutsideLoop = true, I don't feel reassociation for their formulas matters much for the performance, since the uses are all outside of loop. From my understanding, LSRUse with AllFixupsOutsideLoop = true shouldn't have equal weight as other LSRUse with fixups inside the loop. It is ok for a LSRFixup user outside of loop to use many registers. That is why I simply choose to bypass the reassociation. If it is for LSRUse with AllFixupsOutsideLoop = false, I feel I need to be more careful.

Thanks,
Wei.

[davide]

@qcolombet ping

[davide]

@qcolombet Ping?

[qcolombet]

Hi Wei,

Sorry for the delay, I thought Andy's comment was clear enough for you to explore other directions. So I didn't pay attention to the review.

Anyhow, at this point you would have guessed it, but I agree with Andy. I think this patch is a workaround for a problem we yet don't understand.

I wanted to provide a patch to demonstrate Andy's point and what I found when playing around is interesting. (Patch attached nonetheless:

experimental_lsr_reassoc.diff1 KBDownload

)

TL;DR I believe the problem is in the SCEVExpander code and not in LSR per se, I would suggest to recreate a profile using opt -loop-reduce and look where the time is spent.

Basically, I wanted to limit the number of reassociations per recursive call to 5. The max depth of the call is 3. The call happens for each base register (typically less than 3) of all formulae (typically a couple) for each LSRUse.
So, that gives us a total of: 5 * 3 * 3 * 2 = 90 reassociation formulae per LSRUse and given that they are typically 4 uses per loop, the grant total is less than 400, which does not sound too bad to explore.

However, with such limit, the compile time in the example from PR32042 was already blowing up (I killed it after 4 min).

So, I tried with a limit of 2 reassociations per call, i.e., about 36 formulae per LSRUse (to be exact the example generate 25 formulae), and still opt didn't finish after 4 min.

In the end, the only way to get a reasonable compile time was to not allow any reassociation. I started to become suspicious that the problem is not in the size of the search space and after doing a quick profile, I found that at least 80% of the compile time is spent materializing the solution in SCEVExpander. The problem seems to be related to the "nesting-level" of the expression of the formula that the solver picks.
Apply my patch and compare the output of lsr-num-reassoc=1 and lsr-num-reassoc=2 to see how the nesting level materialize.

Admittedly my profile may be bogus (my Instruments is quite old and the trace looked weird), but I would nonetheless recommend to look into creating a proper profile and investigating what is going on instead of bypassing the whole reassociation process.

That being said, I also understand that this patch blocks some people, so I would be okay for you to push it now as long as you commit to look at the actual problem in a reasonable time. In other words, if this patch is really needed to unblock people, go for it, but I want a different solution in a near future.

Cheers,
-Quentin

lib/Transforms/Scalar/LoopStrengthReduce.cpp

3429

What is the highest number you get from the LLVM test suite?
Same for clang self-host?

3430

I agree with Sanjoy that there is nothing preventing this for happening when AllFixupsOutsideLoop is false.

[atrick]

@qcolombet, thanks for the analysis. It would be even better if we had a fix to the SCEVExpander's pathological behavior. Now I'm afraid this patch just hides the problem for this particular category of test case.

[wmi]

Quentin, it is really a good finding, thanks a lot! I was cheated by the large amount of reassociation candidates and I have verified the non-linear increase of compile time is indeed because of SCEVExpand!

I digged into it a little and found a problem in SCEV:
For an SCEVAddRecExpr like this:
{{{{{{{{{{{{2002,+,-1}<nsw><%bb5>,+,-1}<nsw><%bb23>,+,-1}<nsw><%bb41>,+,-1}<nsw><%bb59>,+,-1}<nsw><%bb77>,+,-1}<nsw><%bb95>,+,-1}<nsw><%bb113>,+,-1}<nsw><%bb131>,+,-1}<nsw><%bb149>,+,-1}<nsw><%bb167>,+,-1}<nsw><%bb185>,+,-1}<nw><%bb203>

When ScalarEvolution::getZeroExtendExpr is called for a SCEVAddRecExpr, it will try to prove the wrap flag by computing whether sext(start + step *iterations) == sext(start) + sext(step*iterations). It means getZeroExtendExpr will be called at least twice for each level. If the SCEVAddRecExpr above has N level of SCEVAddRecExpr, the complexity is O(2^N). However, if we have cache for wrap flag, many such getZeroExtendExpr calls can be saved.

If the result of wrap flag analysis for a SCEVAddRecExpr is FlagNSW/FlagNUW, it will be recorded. If the wrap analysis result is FlagAnyWrap, it will be computed again next time. A problem of current implementation is: FlagAnyWrap cannot tell us whether this is the first time to analyze the wrap flag of the SCEV.

I try a hack by adding a FlagMayWrap in SCEV::NoWrapFlags. When we have done analysis for a SCEVAddRecExpr and still have no idea whether it will wrap, we set it to be FlagMayWrap. Then we can skip wrap analysis for any SCEV with flag other than FlagAnyWrap. I find the hack can solve the compile time problem, but it[[

patch3 KBDownload

| name ]] definitely needs to be improved.

[qcolombet]

It would be even better if we had a fix to the SCEVExpander's pathological behavior.

Completely agree! The patch was a mean to demonstrate the problem :).

[sanjoy]

Hi Wei,

If this indeed is a problem with ScalarEvolution::getZeroExtendExpr then you should be able to write a .ll file that triggers the exponential behavior on -analyze -scalar-evolution. Do you mind giving writing such a test case (as a first step) a shot?

[wmi]

I extended the test and now it took more than one hour on my sandybridge machine when built with clang in release mode.
I added early returns in getZeroExtendExpr/getSignExtendExpr for SCEVAddRecExpr with NW flag. Like the test shows, the compile explosion can only happen when the step of SCEVAddRecExpr is negative and NW flag can be marked. With the change, the test now takes less than one second.

Sanjoy, could you take a look?

[sanjoy]

Hi Wei,

I may be wrong, but I'm not convinced that your approach is correct (the reason is inline).

Is it possible to solve this by adding a cache that maps SCEV expressions to their zero (and sign) extended variants? We'd not want this cache to be permanent, since it can lock SCEV into a pessimistic state that it won't get out of even after (say) proving a value to be nuw. However, we can create one such cache in the lexical scope of the top level getZeroExtendExpr (and maybe split out a getZeroExtendImpl that takes a pointer to said cache).

lib/Analysis/ScalarEvolution.cpp

1790 ↗

(On Diff #94115)

I'm not sure if this is correct. You're saying that, e.g., sext({A,+,B}<nw> is {sext A,+,zext B}, but what if A is INT_MAX, B is 1, and the backedge taken count count is 1?

unittests/Analysis/ScalarEvolutionTest.cpp

625 ↗

(On Diff #94115)

Did you consider generating this IR programmatically? That would be easier to modify.

[wmi]

Sanjoy, thanks for the comments.

Is it possible to solve this by adding a cache that maps SCEV expressions to their zero (and sign) extended variants? We'd not want this cache to be permanent, since it can lock SCEV into a pessimistic state that it won't get out of even after (say) proving a value to be nuw. However, we can create one such cache in the lexical scope of the top level getZeroExtendExpr (and maybe split out a getZeroExtendImpl that takes a pointer to said cache).

It sounds a good solution. I will try it if my simple fix is still not enough after adding the constraint.

lib/Analysis/ScalarEvolution.cpp

1790 ↗

(On Diff #94115)

Is adding one more constraint isKnownNegative(Step) enough?

unittests/Analysis/ScalarEvolutionTest.cpp

625 ↗

(On Diff #94115)

Ok, I will do it.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

1790 ↗

(On Diff #94115)

I don't think so (btw, the same issue applies to the getSignExtendExpr case as well): {-1,0,-1} is <nw> for a loop that runs (say) 10 times, but it unsigned overflows the first time the loop's backedge is taken.

[wmi]

Address Sanjoy's comments.

• Implement local caches for getZeroExtendExpr and getSignExtendExpr.
• Generate the IR programatically for the testcase.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

1509 ↗

(On Diff #95000)

DenseMap is probably too heavyweight here -- can you change this to SmallDenseMap<8>?

2002 ↗

(On Diff #95000)

Can you create a lambda for this that use as return InsertResult(SExt); instead of goto RET;?

[wmi]

Address Sanjoy's comments: Use SmallDenseMap and lambda.

[sanjoy]

I think the code can be structured to make things more robust against future changes. PTAL and see if you agree:

lib/Analysis/ScalarEvolution.cpp

1520 ↗

(On Diff #95071)

s/use/Use/
s/func/function/

1547 ↗

(On Diff #95071)

No need to move this comment?

1734 ↗

(On Diff #95071)

Can you please make SmallDenseMap<std::pair<const SCEV *, Type *>, const SCEV *, 8> a typedef?

1739 ↗

(On Diff #95071)

s/use/Use/
s/func/function/

Also CacheResult may be a better name (sorry for not suggesting it before! -- hopefully this should be a quick find-replace).

Also, what do you think about an RAII object (under #ifndef NDEBUG) that checks that {Op, Ty} is in the cache on destruction? I can imagine someone adding a new return path and forgetting to call CacheResult.

Actually, a better solution would be to make the caching guarantee true by construction:

getZeroExtendExpr creates a cache, and calls getZeroExtendExprCached with the cache. getZeroExtendExprCached calls getZeroExtendExprImpl to do the heavy lifting (which recursively calls getZeroExtendExprCached when needed), and also does the pre-check in the cache, and also the insertion into the cache (that way getZeroExtendExprImpl does not have to remember to insert into the cache at each return site).

[wmi]

Address Sanjoy's comments: Add another two proxy functions: getZeroExtendExprCached and getSignExtendExprCached.

[sanjoy]

lgtm with nits

include/llvm/Analysis/ScalarEvolution.h

1163 ↗

(On Diff #95151)

I think the usual naming scheme here is ExtendCacheTy?

lib/Analysis/ScalarEvolution.cpp

1522 ↗

(On Diff #95151)

If possible, you should

auto InsertResult = Cache.insert({{Op, Ty}, ZExt});
assert(InsertResult.second);

otherwise state that it is possible (how?) that the key is already present in the cache.

[wmi]

Sanjoy, thanks for all the helpful comments.

include/llvm/Analysis/ScalarEvolution.h

1163 ↗

(On Diff #95151)

Fixed.

lib/Analysis/ScalarEvolution.cpp

1522 ↗

(On Diff #95151)

I added the assertion and at least unittest and llvm testsuite didn't trigger it.

lib/Transforms/Scalar/LoopStrengthReduce.cpp

void LSRInstance::GenerateReassociationsImpl(LSRUse &LU, unsigned LUIdx,
   SmallVector<const SCEV *, 8> AddOps;
   const SCEV *Remainder = CollectSubexprs(BaseReg, nullptr, AddOps, L, SE);
   if (Remainder)
     AddOps.push_back(Remainder);
 
   if (AddOps.size() == 1)
     return;
 
+  // For AllFixupsOutsideLoop uses, their reassociations have less impact than
+  // normal uses since they are outside of current loop.
+  // Arbitrarily choose a cap size of AddOps to protect compile time.
+  if (AddOps.size() >= 5 && LU.AllFixupsOutsideLoop)
+    return;
+
   for (SmallVectorImpl<const SCEV *>::const_iterator J = AddOps.begin(),
                                                      JE = AddOps.end();
        J != JE; ++J) {
 
     // Loop-variant "unknown" values are uninteresting; we won't be able to
     // do anything meaningful with them.
     if (isa<SCEVUnknown>(*J) && !SE.isLoopInvariant(*J, L))
       continue;

test/Transforms/LoopStrengthReduce/X86/reassociation-cap.ll

+; REQUIRES: asserts
+; RUN: opt -mtriple=x86_64-unknown-linux-gnu -loop-reduce -disable-output -debug-only=loop-reduce -S < %s 2>&1| FileCheck %s
+; PR32043. Check LSR will not generate many formulae via reassociation for
+; all-fixups-outside-loop type LSRUse.
+
+; CHECK: LSR on loop %bb15:
+; CHECK: After generating reuse formulae:
+; CHECK: LSR Use: Kind=Basic, Offsets={0}, all-fixups-outside-loop, widest fixup type: i64
+; CHECK-NEXT: reg((-4 * (%tmp34 + %tmp27 + %tmp20 + %tmp13 + %tmp6)))
+; CHECK-NEXT: reg((-4 * (%tmp34 + %tmp27 + %tmp20 + %tmp13 + %tmp6)))
+; CHECK-NEXT: reg((-4 * (%tmp34 + %tmp27 + %tmp20 + %tmp13 + %tmp6)))
+; CHECK-NEXT: LSR Use: Kind=Basic, Offsets={0}, all-fixups-outside-loop, widest fixup type: i64
+; CHECK: LSR on loop %bb12:
+; After put a cap on reassociation for all-fixups-outside-loop type LSRUse, LSR will only
+; generate three reuse formulae for LSRUse %tmp563 used in store.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @foo(i64* %arg) {
+bb:
+  br label %bb3
+bb2:
+  %tmp2 = add nuw nsw i64 %tmp1, 1
+  %tmp7 = icmp slt i64 %tmp1, 29
+  br i1 %tmp7, label %bb3, label %bb4
+bb3:
+  %tmp1 = phi i64 [ %tmp2, %bb2 ], [ 0, %bb ]
+  %tmp3 = phi i32 [ %tmp4, %bb2 ], [ 0, %bb ]
+  %tmp5 = getelementptr inbounds i64, i64* %arg, i64 %tmp1
+  %tmp6 = load i64, i64* %tmp5, align 1
+  %tmp4 = add nuw nsw i32 %tmp3, 1
+  br i1 false, label %bb4, label %bb2
+bb4:
+  %tmp90 = sext i32 %tmp4 to i64
+  br label %bb6
+
+bb5:
+  %tmp9 = add nuw nsw i64 %tmp8, 1
+  %tmp14 = icmp slt i64 %tmp8, 29
+  br i1 %tmp14, label %bb6, label %bb7
+bb6:
+  %tmp8 = phi i64 [ %tmp9, %bb5 ], [ 0, %bb4 ]
+  %tmp10 = phi i32 [ %tmp11, %bb5 ], [ 0, %bb4 ]
+  %tmp12 = getelementptr inbounds i64, i64* %arg, i64 %tmp8
+  %tmp13 = load i64, i64* %tmp12, align 1
+  %tmp11 = add nuw nsw i32 %tmp10, 1
+  br i1 false, label %bb7, label %bb5
+bb7:
+  %tmp91 = sext i32 %tmp11 to i64
+  br label %bb9
+
+bb8:
+  %tmp16 = add nuw nsw i64 %tmp15, 1
+  %tmp21 = icmp slt i64 %tmp15, 29
+  br i1 %tmp21, label %bb9, label %bb10
+bb9:
+  %tmp15 = phi i64 [ %tmp16, %bb8 ], [ 0, %bb7 ]
+  %tmp17 = phi i32 [ %tmp18, %bb8 ], [ 0, %bb7 ]
+  %tmp19 = getelementptr inbounds i64, i64* %arg, i64 %tmp15
+  %tmp20 = load i64, i64* %tmp19, align 1
+  %tmp18 = add nuw nsw i32 %tmp17, 1
+  br i1 false, label %bb10, label %bb8
+bb10:
+  %tmp92 = sext i32 %tmp18 to i64
+  br label %bb12
+
+bb11:
+  %tmp23 = add nuw nsw i64 %tmp22, 1
+  %tmp28 = icmp slt i64 %tmp22, 29
+  br i1 %tmp28, label %bb12, label %bb13
+bb12:
+  %tmp22 = phi i64 [ %tmp23, %bb11 ], [ 0, %bb10 ]
+  %tmp24 = phi i32 [ %tmp25, %bb11 ], [ 0, %bb10 ]
+  %tmp26 = getelementptr inbounds i64, i64* %arg, i64 %tmp22
+  %tmp27 = load i64, i64* %tmp26, align 1
+  %tmp25 = add nuw nsw i32 %tmp24, 1
+  br i1 false, label %bb13, label %bb11
+bb13:
+  %tmp93 = sext i32 %tmp25 to i64
+  br label %bb15
+
+bb14:
+  %tmp30 = add nuw nsw i64 %tmp29, 1
+  %tmp35 = icmp slt i64 %tmp29, 29
+  br i1 %tmp35, label %bb15, label %bb16
+bb15:
+  %tmp29 = phi i64 [ %tmp30, %bb14 ], [ 0, %bb13 ]
+  %tmp31 = phi i32 [ %tmp32, %bb14 ], [ 0, %bb13 ]
+  %tmp33 = getelementptr inbounds i64, i64* %arg, i64 %tmp29
+  %tmp34 = load i64, i64* %tmp33, align 1
+  %tmp32 = add nuw nsw i32 %tmp31, 1
+  br i1 false, label %bb16, label %bb14
+bb16:
+  %tmp94 = sext i32 %tmp32 to i64
+  br label %bb556
+
+bb556:
+  %tmp554 = add i64 %tmp6, %tmp13
+  %tmp555 = add i64 %tmp554, %tmp20
+  %tmp556 = add i64 %tmp555, %tmp27
+  %tmp557 = add i64 %tmp556, %tmp34
+  %tmp558 = mul i64 %tmp557, -4
+  %tmp559 = add i64 %tmp558, %tmp90
+  %tmp560 = add i64 %tmp559, %tmp91
+  %tmp561 = add i64 %tmp560, %tmp92
+  %tmp562 = add i64 %tmp561, %tmp93
+  %tmp563 = add i64 %tmp562, %tmp94
+  store i64 %tmp563, i64* %arg, align 8
+  ret void
+}
+