This is an archive of the discontinued LLVM Phabricator instance.

[LTO] Do not reorder global variables unnecessarily during merging
AcceptedPublic

Authored by tobiasvk on Mar 28 2017, 3:02 PM.

Details

Summary

The new resolution-based LTO API leads to global variables being re-ordered
during module merging for regular LTO. With the old LTO API and in the non-LTO
case, the source order is preserved.

The new order is semi-random; it is caused by recursively materializing
variables as their uses are discovered during materialization of functions. In
practice, it is often the exact reverse of source order.

While the C standard makes no guarantee about the relative ordering of global
variables, there is no discernable benefit to re-ordering them in this way.
Worse, it can negatively affect performance by degrading cache locality and
introduces unnecessary variation in behavior and performance between the two
LTO APIs, and the non-LTO case.

This fixes PR32441.

Diff Detail

Event Timeline

tobiasvk created this revision.Mar 28 2017, 3:02 PM
mehdi_amini accepted this revision.Mar 28 2017, 3:19 PM

LGTM.

But keep in mind that we don't want anyone relying on this ordering.

Also performance induced difference here is only showing potential optimization opportunities for the general case :)

This revision is now accepted and ready to land.Mar 28 2017, 3:19 PM

But please wait for the other to chime in with their opinion on the topic :)

Gerolf added a subscriber: Gerolf.Mar 28 2017, 3:29 PM

I'd love to see some comments an get your thoughts about a verifier.

Thank you
Gerolf

lib/Object/ModuleSymbolTable.cpp
48 ↗(On Diff #93307)

Please add a comment about why the order of the for loop is relevant and how it relates to source code ordering. Also, could there be a verifier that source code order is preserved?

test/LTO/Resolution/X86/globalorder.ll
2

How about 'Check that LTO keeps global variables in source code order'?

I'd love to see some comments an get your thoughts about a verifier.

I don't think we should add a verifier because there is no guarantee about the ordering of global variables or functions in the C/C++ standards. Any code that relies on it is pretty much broken (as has been pointed out during the discussion in the PR). The performance aspect is a different question, but I think the verifier should be about correctness, not optimal performance. We explicitly don't want to introduce a new guarantee about ordering here (or elsewehere).

tobiasvk marked 2 inline comments as done.Mar 28 2017, 3:56 PM
tobiasvk updated this revision to Diff 93317.Mar 28 2017, 4:14 PM

Make Gerolf's suggested changes to comments.

tobiasvk updated this revision to Diff 93938.Apr 3 2017, 1:43 PM

Rebase and update test case comment.

In the meantime, r299018 moved the iteration code into a new function,
Module::global_values(). The only users are in ModuleSymbolTable.cpp and
ThinLTOBitcodeWriter.cpp (where an order-sensitive hash is computed, hence the
test case change). This will not affect anything outside of LTO.

tobiasvk updated this revision to Diff 93952.Apr 3 2017, 2:49 PM

Add Rafael's suggested disclaimer to the test case.

Any further comments? I'd like to go ahead and merge this.

espindola edited reviewers, added: espindola; removed: rafael.Mar 14 2018, 4:58 PM