This is an archive of the discontinued LLVM Phabricator instance.

[DomTreeUpdater] Add all insert before all delete updates to reduce compile time.
ClosedPublic

Authored by asbirlea on Jun 6 2019, 1:53 PM.

Details

Summary

The cleanup in D62751 introduced a compile-time regression due to the way DT updates are performed.
Add all insert edges then all delete edges in DTU to match the previous compile time.
Compile time on the test provided by @mstorsjo before and after this patch on my machine:
113.046s vs 35.649s
Repro: clang -target x86_64-w64-mingw32 -c -O3 glew-preproc.c; on https://martin.st/temp/glew-preproc.c.

Diff Detail

Event Timeline

asbirlea created this revision.Jun 6 2019, 1:53 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 6 2019, 1:53 PM
Herald added a subscriber: jlebar. · View Herald Transcript

I don't know this area so I can't comment on it from that perspective, but it does indeed speed up my case, to even faster than it was before the regression. On my system, it originally took 75 s to compile, 220 s after the regression, and now 62 s with this patch. So looking good in that aspect at least!

Thanks for the patch! I believe that the modification here fulfills the precondition of calling mutation APIs of the DomTreeUpdater.
B.T.W., After seeing this patch, I recalled a not-merged patch, D54730, which has the same motivation and similar modifications.
I think "sorting updates so that insertions always happen before deletions" needs to be analyzed case-by-case, as there isn't enough evidence that the updating process will always be faster that way.

lib/Transforms/Utils/BasicBlockUtils.cpp
215–221

I would like the comment here explaining the order of updates matters the performance. :)

asbirlea updated this revision to Diff 203588.Jun 7 2019, 11:24 AM
asbirlea marked an inline comment as done.

Add detalied comment.

NutshellySima accepted this revision.Jun 7 2019, 11:58 AM

Thanks for the changes. LGTM.

This revision is now accepted and ready to land.Jun 7 2019, 11:58 AM
This revision was automatically updated to reflect the committed changes.