Page MenuHomePhabricator

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

Authored by karthikthecool on Mar 20 2014, 5:15 AM.

Details

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

Diff Detail

Event Timeline

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 added inline comments.Jul 27 2016, 8:02 PM
lib/Analysis/ScalarEvolution.cpp
1965

Typo Dont

mehdi_amini added inline comments.Jul 27 2016, 8:21 PM
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 added inline comments.
lib/Analysis/ScalarEvolution.cpp
1967

Formatting.

sanjoy requested changes to this revision.Jul 27 2016, 9:54 PM
sanjoy added a reviewer: sanjoy.
sanjoy added a subscriber: sanjoy.
sanjoy added inline comments.
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.

This revision now requires changes to proceed.Jul 27 2016, 9:54 PM