This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Use depth limit instead of local cache for SExt and ZExt
ClosedPublic

Authored by mkazantsev on Jun 16 2017, 5:02 AM.

Details

Summary

In rL300494 there was an attempt to deal with excessive compile time on
invocations of getSign/ZeroExtExpr using local caching. This approach only
helps if we request the same SCEV multiple times throughout recursion. But
in the bug PR33431 we see a case where we request different values all the time,
so caching does not help and the size of the cache grows enormously.

In this patch we remove the local cache for this methods and add the recursion
depth limit instead, as we do for arithmetics. This gives us a guarantee that the
invocation sequence is limited and reasonably short.

Diff Detail

Event Timeline

mkazantsev created this revision.Jun 16 2017, 5:02 AM
wmi edited edge metadata.Jun 21 2017, 3:30 PM

Thanks for helping on fixing the bug!

lib/Analysis/ScalarEvolution.cpp
1579

Do we want to pass Depth into getExtendAddRecStart? Since getZeroExtendExpr and getSignExtendExpr can be called recursively inside of getExtendAddRecStart.

mkazantsev added inline comments.Jun 21 2017, 9:47 PM
lib/Analysis/ScalarEvolution.cpp
1579

Thanks for pointing out! I will go through all invocations here, maybe we are missing it somewhere else.

mkazantsev added inline comments.Jun 22 2017, 10:08 PM
lib/Analysis/ScalarEvolution.cpp
1579

Wei, actually I failed to find a place where getAddRecExpr invokes either of them. I only see it invoing itself. We maybe need a separate depth limit for it, but it is out of scope of this patch.

If you know a way how getSign/ZeroExt can be invoked from getAddRecExpr, could you please point it out?

wmi added inline comments.Jun 23 2017, 8:22 AM
lib/Analysis/ScalarEvolution.cpp
1579

It is not getAddRecExpr. What I said was getExtendAddRecStart.

mkazantsev planned changes to this revision.Jun 25 2017, 8:38 PM

My bad, need to change this. :) Thanks!

mkazantsev marked an inline comment as done.

Added depth limitation passed through getExtendAddRecStart

wmi added inline comments.Jun 28 2017, 4:13 PM
lib/Analysis/ScalarEvolution.cpp
1429

Maybe also pass Depth to getPreStartForExtend? we have SE->*GetExtendExpr() called inside of getPreStartForExtend.

mkazantsev marked an inline comment as done.

Added depth passed through getPreStartForExtend.

wmi accepted this revision.Jun 29 2017, 9:42 AM
This revision is now accepted and ready to land.Jun 29 2017, 9:42 AM
This revision was automatically updated to reflect the committed changes.