This is an archive of the discontinued LLVM Phabricator instance.

[Verifier] Fix performance regression for LTO builds
ClosedPublic

Authored by krasin on Jan 19 2016, 5:04 PM.

Details

Summary

Fix a significant performance regression by introducing GlobalValueVisited field and reusing the map.
This is a follow up to r257823 that slowed down linking Chrome with LTO by 2.5x.

If you revert this commit, please, also revert r257823.

BUG=https://llvm.org/bugs/show_bug.cgi?id=26214

Diff Detail

Event Timeline

krasin updated this revision to Diff 45328.Jan 19 2016, 5:04 PM
krasin retitled this revision from to NOT FOR SUBMIT: an attempt to speed up IR Verifier..
krasin updated this object.
pcc added a subscriber: pcc.Jan 19 2016, 5:11 PM
pcc added inline comments.
lib/IR/Verifier.cpp
520

I don't think you want to clear every time. Verifier::VisitIt is checking a property of V, not of GV.

loladiro added inline comments.
lib/IR/Verifier.cpp
520

Correct, don't clear this.

krasin updated this revision to Diff 45329.Jan 19 2016, 5:19 PM

do not clear Visited map.

Done. Is it good for a test now?

krasin updated this revision to Diff 45352.Jan 19 2016, 10:54 PM

For submit

krasin1 retitled this revision from NOT FOR SUBMIT: an attempt to speed up IR Verifier. to [Verifier] Fix performance regression for LTO builds.Jan 19 2016, 10:57 PM
krasin1 updated this object.
krasin1 added reviewers: pcc, loladiro.
krasin updated this revision to Diff 45354.Jan 19 2016, 10:58 PM

Remove unnecessary empty line diff.

Since it's a pretty basic fix that does not change the logic (except of reusing GlobalValueVisited, which was already reviewed), I will go ahead and submit this revision.

Feel free to revert it, but in this case, I would also ask to revert r257823, so that we unbreak 'CFI Linux ToT' buildbot in Chrome.

Feel free to improve the CL (for example, by making forEachUser more reusable), but please, keep an eye on https://build.chromium.org/p/chromium.fyi/builders/CFI%20Linux%20ToT.

mehdi_amini added inline comments.Jan 19 2016, 11:03 PM
lib/IR/Verifier.cpp
477

What was the problem with this being a lambda? I missed why you needed to change this for this patch?

482

You changed the implementation of the function but kept the name, which is now no longer representative of what this does.

krasin updated this revision to Diff 45356.Jan 19 2016, 11:07 PM

forEachUser -> forEachUserGlobalValue

krasin1 added inline comments.Jan 19 2016, 11:08 PM
lib/IR/Verifier.cpp
482

Agree. I have renamed it forEachUserGlobalValue.

I expect that Keno would like to make a template implementation of forEachUser, then this function will go away.

krasin updated this revision to Diff 45357.Jan 19 2016, 11:09 PM

one more place to rename.

krasin1 added inline comments.Jan 19 2016, 11:14 PM
lib/IR/Verifier.cpp
477–478

Keno made a guess (https://llvm.org/bugs/show_bug.cgi?id=26214#c1), which I verified (took 4 hours). It could be that the major savings are from reusing the map, but my time budget for firefighting is limited. I am perfectly fine if Keno (or anyone else) to make another try with lambdas or templates. I will give a hint, if there's a visible regression due to that.

krasin updated this revision to Diff 45358.Jan 20 2016, 12:39 AM

just extract the map; keep the lambda.

I felt lonely and made another round of trials. Turns out it's the map reuse (or the lack of thereof) was the reason for the regression.

krasin1 updated this object.Jan 20 2016, 12:41 AM
mehdi_amini accepted this revision.Jan 20 2016, 12:41 AM
mehdi_amini added a reviewer: mehdi_amini.

LGTM.

This revision is now accepted and ready to land.Jan 20 2016, 12:41 AM
mehdi_amini added inline comments.Jan 20 2016, 12:44 AM
lib/IR/Verifier.cpp
481

I'm wondering which use case this recursive is catching? Why isn't looking at one level enough here?
(it's late here, I may miss something obvious)

This revision was automatically updated to reflect the committed changes.
loladiro edited edge metadata.Jan 20 2016, 3:08 AM

You could have a constant user that's not associated to a module.

Also @krasin, thanks for taking care of this, I appreciate it.

Also @krasin, thanks for taking care of this, I appreciate it.

No problem. While my knowledge of lib/IR is limited (so, your guidance was very helpful), I really was in the position to reliably reproduce the issue.