This is an archive of the discontinued LLVM Phabricator instance.

[llvm] Improve performance of programUndefinedIfUndefOrPoison
ClosedPublic

Authored by gezalore on Oct 29 2022, 2:58 PM.

Details

Summary

programUndefinedIfUndefOrPoison used to eagerly propagate the fact that
a value is poison to the users of the value. The problem is that if the
value has a lot of uses (orders of magnitude more than the scanning
limit we use in this function), then we spend the bulk of our time in
eagerly propagating the poison property, which we will mostly never use
later anyway due to the scanning limit.

I have a test case (of ~50k lines of machine generated C++), where this
results in ~60% of 35s compilation time being spent doing just this
eager propagation.

This patch changes programUndefinedIfUndefOrPoison to only propagate to
instructions actually visited, looking back to see if their operands are
poison. This should be equivalent and no functional change is intended,
but we regain virtually all of the 60% compilation time spent in this
function in my test case (i.e.: a 2.5x total compilation speedup).

Diff Detail

Event Timeline

gezalore created this revision.Oct 29 2022, 2:58 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 29 2022, 2:58 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
gezalore requested review of this revision.Oct 29 2022, 2:58 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 29 2022, 2:58 PM

Hello, this is my first patch to LLVM so please educate me as you feel is appropriate.

@nikic @aqjune git tells me you might be appropriate reviewers, could you take a look please?

nikic added a comment.Oct 29 2022, 3:28 PM

Not a fan of the mix of lazy and eager propagation here. I think the way you implemented the lazy isPoison check we may also run into a problem where the poison check will try to recurse past the initial instruction, and might explore a large tree that way, introducing a different compile-time problem.

Can we simply propagate poison as we visit instructions? I.e. when we visit an instruction, check whether it propagates poison and has a poison operand, if so mark it as poison itself?

gezalore updated this revision to Diff 471792.Oct 29 2022, 4:24 PM
gezalore edited the summary of this revision. (Show Details)

Simplify according to feedback

You are right about the recursion problem, and I think your suggestion works (and the test suite and my benchmark agrees), so I updated the patch.

Thanks for the speedy review and suggestions!

nikic accepted this revision.Oct 30 2022, 1:04 AM

LGTM, thanks!

llvm/lib/Analysis/ValueTracking.cpp
5800

You can use for (const Value *Op : I.operands()) here and use Op in place of U.get(), as you don't care about the specific position of the use in this case.

This revision is now accepted and ready to land.Oct 30 2022, 1:04 AM
nikic added a comment.Oct 30 2022, 1:05 AM

Can you please also share Name <email> to use for the commit (assuming you don't have commit access)?

Thank you. I don't have commit access, I am:

Geza Lore <gezalore@gmail.com>

gezalore updated this revision to Diff 471828.Oct 30 2022, 3:28 AM

Fix code style as recommended. Hopefully patch is good to go now.

This revision was landed with ongoing or failed builds.Oct 31 2022, 2:22 AM
This revision was automatically updated to reflect the committed changes.