This is an archive of the discontinued LLVM Phabricator instance.

[MergeFuncs] Efficiently defer functions on merge
ClosedPublic

Authored by jrkoenig on Sep 1 2015, 11:56 AM.

Details

Summary

This patch introduces a side table in Merge Functions to
efficiently remove functions from the function set when functions
they refer to are merged. Previously these functions would need to
be compared lg(N) times to find the appropriate FunctionNode in the
tree to defer. With the recent determinism changes, this comparison
is more expensive. In addition, the removal function would not always
actually remove the function from the set (i.e. after remove(F),
there would sometimes still be a node in the tree which contains F).

With these changes, these functions are properly deferred, and so more
functions can be merged. In addition, when there are many merged
functions (and thus more deferred functions), there is a speedup:

chromium: 48678 merged -> 49380 merged; 6.58s -> 5.49s
libxul.so: 41004 merged -> 41030 merged; 8.02s -> 6.94s
mysqld: 1607 merged -> 1607 merged (same); 0.215s -> 0.212s (probably noise)

Diff Detail

Repository
rL LLVM

Event Timeline

jrkoenig retitled this revision from to [MergeFuncs] Efficiently defer functions on merge.
jrkoenig updated this object.
jrkoenig added reviewers: jfb, dschuff.
jrkoenig added subscribers: nlewycky, llvm-commits.
jfb edited edge metadata.Sep 1 2015, 4:20 PM

I'm not super comfortable with keeping iterators around: iterator invalidation is a great gotcha in C++. Is there a way to avoid keeping the iterators, without changing complexity (potentially by doing a replace on ->second)? e.g. set insertion doesn't invalidate, but set deletion does, and you have both so I can't naively convince myself that your code is valid.

lib/Transforms/IPO/MergeFunctions.cpp
1723 ↗(On Diff #33718)

Move this assert up one line, after find.

jrkoenig edited edge metadata.

Clarified invariant linking FnTree and FNodesInTree, use more descriptive
names, and add more comments.

According to this C++ standard draft/prerelease/whatever, Section 23.2.4, paragraph 9 claims that only the elements erased are invalidated. This is subtle but correct usage. Sounds like I need to add some comments.

The alternative is to iterate over the tree and remove any copy of F that is found, which is quite expensive. The current implementation (which uses the ordering to find the right node) sometimes missed functions, which most likely occurs due to functions changed before they are actually removed from the tree, changing the implicit invariant of the tree that it's elements remain in a stable order.

jfb added a comment.Sep 2 2015, 9:42 AM

The current implementation (which uses the ordering to find the right node) sometimes missed functions, which most likely occurs due to functions changed before they are actually removed from the tree, changing the implicit invariant of the tree that it's elements remain in a stable order.

Can you clarify this? Is that a new thing? It at least seems like something that should be in a FIXME.

lib/Transforms/IPO/MergeFunctions.cpp
1734 ↗(On Diff #33763)

It's a more common style to do the following instead of having a comment:

assert(foo && "I expected foo because bar");
jfb added a comment.Sep 2 2015, 9:45 AM
This comment was removed by jfb.

Move comments into asserts.

In r245139, before hashing and the other recent changes, remove() was buggy as well. The problem manifests in all three LTO builds of chromium, mysql, and libxul.

jfb accepted this revision.Sep 2 2015, 12:56 PM
jfb edited edge metadata.

lgtm

This revision is now accepted and ready to land.Sep 2 2015, 12:56 PM
dschuff accepted this revision.Sep 2 2015, 1:12 PM
dschuff edited edge metadata.
This revision was automatically updated to reflect the committed changes.