This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] limit recursion depth and operands number in getAddExpr
ClosedPublic

Authored by dfukalov on Dec 29 2016, 7:42 AM.

Details

Summary

for a quite big function with source like

%add = add nsw i32 %mul, %conv
%mul1 = mul nsw i32 %add, %conv
%add2 = add nsw i32 %mul1, %add
%mul3 = mul nsw i32 %add2, %add
; repeat couple of thousands times

that can be produced by loop unroll, getAddExpr() tries to recursively construct SCEV and runs almost infinite time.

Added recursion depth restriction (with new parameter to set it)

Diff Detail

Event Timeline

dfukalov updated this revision to Diff 82670.Dec 29 2016, 7:42 AM
dfukalov retitled this revision from to [SCEV] limit recursion depth and operands number in getAddExpr.
dfukalov updated this object.
dfukalov added a reviewer: sanjoy.
dfukalov added a subscriber: llvm-commits.
hfinkel added a subscriber: hfinkel.Jan 8 2017, 2:35 PM

added threshold for inlining addition operands (the same way as it's already implemented for multiplication operands inlining)

What do you mean exactly? getMulExpr does not have a depth parameter like this. We have a comparison depth limit and a depth limit on SimplifyICmpOperands.

include/llvm/Analysis/ScalarEvolution.h
1160

Increasing the depth here does not seem right - it is not a real recursion, but just a simple convenience wrapper.

1165

Same here.

What do you mean exactly? getMulExpr does not have a depth parameter like this. We have a comparison depth limit and a depth limit on SimplifyICmpOperands.

The second point is about new AddOpsInlineThreshold parameter. It is almost the same as MulOpsInlineThreshold used in getMulExpr (line 2608). And this part of change is independent of recursion depth limit, but suggested for the same purpose - to reduce almost infinite time of processing very long expressions.

dfukalov added inline comments.Jan 9 2017, 3:54 AM
include/llvm/Analysis/ScalarEvolution.h
1160

These wrappers are called in a few places within getAddExpr implementation. If they are not supposed to be used there (but from "outside" users), I can modify such calls and remove depth parameter.

sanjoy requested changes to this revision.Jan 15 2017, 1:37 PM
sanjoy edited edge metadata.
sanjoy added inline comments.
include/llvm/Analysis/ScalarEvolution.h
1158

Given that the "recursive" calls are really just tail calls, perhaps we can call this Iteration instead of Depth?

lib/Analysis/ScalarEvolution.cpp
2196

Use early return here instead. I.e. extract out the actual node construction logic into a helper function, and call that here on an early return.

2269

Can you please split out this bailout into a separate change with its own test?

unittests/Analysis/ScalarEvolutionTest.cpp
537

s/std::vector<Type *>()/{}/

541

clang-format this please.

543

Can you please use a real value (an llvm::Argument, say) instead of undef? SCEV does not simplify undef today, but that can change in the future, rendering this test a no-op.

This revision now requires changes to proceed.Jan 15 2017, 1:37 PM
dfukalov updated this revision to Diff 84989.Jan 19 2017, 10:57 AM
dfukalov edited edge metadata.
dfukalov edited the summary of this revision. (Show Details)
  1. add expr inlining limit moved to separate change https://reviews.llvm.org/D28812
  2. removed depth parameter from wrapper functions
  3. added helper function to early return
  4. refined test to use func params instead of undef
dfukalov marked 9 inline comments as done.Jan 19 2017, 11:00 AM

Hi Sanjoy,

Would you please take a look to updated diff? We have failing internal tests without the fix...

sanjoy accepted this revision.Feb 3 2017, 10:54 AM

lgtm! Sorry for the delay.

include/llvm/Analysis/ScalarEvolution.h
1619

Please clang-format this bit.

This revision is now accepted and ready to land.Feb 3 2017, 10:54 AM
This revision was automatically updated to reflect the committed changes.