This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Don't walk uses of phis without SCEV expression when forgetting
ClosedPublic

Authored by nikic on Apr 11 2021, 7:07 AM.

Details

Summary

I've run into some cases where a large fraction of compile-time is spent invalidating SCEV. One of the causes is forgetLoop(), which walks all values that are def-use reachable from the loop header phis. When invalidating a topmost loop, that might be close to all values in a function. Additionally, it's fairly common for there to not actually be anything to invalidate, but we'll still be performing this walk again and again.

My first thought was that we don't need to continue walking the uses if the current value doesn't have a SCEV expression. However, this isn't quite right, because SCEV construction can skip over values (e.g. for chain of adds, we might only create a SCEV expression for the final value).

What this patch does instead is to only walk the (full) def-use chain of loop phis that have a SCEV expression. If there's no expression for a phi, then we also don't have any dependent expressions to invalidate.

Diff Detail

Event Timeline

nikic created this revision.Apr 11 2021, 7:07 AM
nikic requested review of this revision.Apr 11 2021, 7:07 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 11 2021, 7:07 AM
mkazantsev added inline comments.Apr 11 2021, 9:34 PM
llvm/lib/Analysis/ScalarEvolution.cpp
7101

I don't quite get why is that supposed to help the compile time. We perform the same very check few lines below. Are you saving time on pushing/popping to the queue?

mkazantsev added inline comments.Apr 11 2021, 9:42 PM
llvm/include/llvm/Analysis/ScalarEvolution.h
2060

... const?

nikic added inline comments.Apr 12 2021, 12:52 AM
llvm/lib/Analysis/ScalarEvolution.cpp
7101

The problem is that PushDefUseChildren() gets called even if the current value is not in ValueExprMap, and that's where all time ends up being spent, as it will visit all direct and indirect users for the phi.

nikic updated this revision to Diff 336958.Apr 12 2021, 2:11 PM
nikic marked an inline comment as done.

Add const qualifier.

mkazantsev accepted this revision.Apr 12 2021, 11:26 PM

Ok, looks good!

This revision is now accepted and ready to land.Apr 12 2021, 11:26 PM

Can this have an effect on codegen? I'm seeing a loop being turned into an infinite loop with this change, trying to extract a test case but it's buried inside of an enormous JIT'ed program.

I wrote
https://bugs.llvm.org/show_bug.cgi?id=49967
about a crash that started appearing with this patch.

nikic added a comment.Apr 18 2021, 1:40 PM

I wrote
https://bugs.llvm.org/show_bug.cgi?id=49967
about a crash that started appearing with this patch.

Thanks, that was enlightening. I've left a comment there on why this broke. Unfortunately, the assumption this patch is based on turns out to be wrong :)