This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Cache results during GetMinTrailingZeros query
ClosedPublic

Authored by igor-laevsky on Feb 9 2017, 6:56 AM.

Details

Summary

This fixes bug 18606.

In certain cases we may get exponentially sized SCEV's in the form of:
S0 = InitialValue
S1 = mul S0 S0
S2 = mul S1 S1
S3 = mul S2 S2

Naively visiting every expression will result in the exponential complexity. However by adding caching layer we can simplify this and achieve linear complexity.

Note that caching doesn't protect us from other forms of the exponentially sized SCEV's. In order to not run infinite compiles in those cases I will add separate threshold in the follow up change.

Diff Detail

Event Timeline

igor-laevsky created this revision.Feb 9 2017, 6:56 AM
igor-laevsky edited the summary of this revision. (Show Details)Feb 9 2017, 7:07 AM

Would it make sense to add a global GetMinTrailingZeros cache instead?

sanjoy requested changes to this revision.Feb 9 2017, 2:17 PM

Would it make sense to add a global GetMinTrailingZeros cache instead?

That's actually what I had in mind -- please make the cache global to the SCEV class.

This revision now requires changes to proceed.Feb 9 2017, 2:17 PM
igor-laevsky edited edge metadata.
igor-laevsky edited the summary of this revision. (Show Details)

Store cache inside of the ScalarEvolution pass.

sanjoy accepted this revision.Feb 10 2017, 12:36 PM

lgtm, but please make the Impl a private member function of ScalarEvolution.

lib/Analysis/ScalarEvolution.cpp
4441

Extracting out the Impl function as a static function is somewhat odd -- why did you just keep it as a normal member function?

This revision is now accepted and ready to land.Feb 10 2017, 12:36 PM
This revision was automatically updated to reflect the committed changes.
igor-laevsky marked an inline comment as done.Feb 14 2017, 8:08 AM
igor-laevsky added inline comments.
lib/Analysis/ScalarEvolution.cpp
4441

Idea was to hide implementation details, but both options seem fine to me.