[LTO] Do not reorder global variables unnecessarily during merging

[tobiasvk]

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.

[mehdi_amini]

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 :)

[mehdi_amini]

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

[Gerolf]

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

Thank you
Gerolf

lib/Object/ModuleSymbolTable.cpp

48

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

1

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

[tobiasvk]

In D31443#712679, @Gerolf wrote:

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]

Make Gerolf's suggested changes to comments.

[tobiasvk]

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]

Add Rafael's suggested disclaimer to the test case.

[tobiasvk]

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

lib/Object/ModuleSymbolTable.cpp

 using namespace object;
 
 void ModuleSymbolTable::addModule(Module *M) {
   if (FirstMod)
     assert(FirstMod->getTargetTriple() == M->getTargetTriple());
   else
     FirstMod = M;
 
-  for (Function &F : *M)
-    SymTab.push_back(&F);
   for (GlobalVariable &GV : M->globals())
     SymTab.push_back(&GV);
+  for (Function &F : *M)
+    SymTab.push_back(&F);
   for (GlobalAlias &GA : M->aliases())
     SymTab.push_back(&GA);
 
   CollectAsmSymbols(*M, [this](StringRef Name, BasicSymbolRef::Flags Flags) {
     SymTab.push_back(new (AsmSymbols.Allocate()) AsmSymbol(Name, Flags));
   });
 }
 

test/LTO/Resolution/X86/globalorder.ll

+; Check that the order of global variables is not unnecessarily
+; perturbed by LTO during module merging.
+;
+; RUN: llvm-as %s -o %t.bc
+; RUN: llvm-lto2 %t.bc -O0 -save-temps -o %t.o -r %t.bc,var1,px -r %t.bc,var2,px -r %t.bc,var3,px -r %t.bc,var4,px -r %t.bc,foo,px
+; RUN: llvm-dis -o - %t.o.0.0.preopt.bc | FileCheck %s
+;
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK: @var1 =
+@var1 = global i32 0, align 4
+; CHECK: @var2 =
+@var2 = global i32 0, align 4
+; CHECK: @var3 =
+@var3 = global i32* @var1, align 4
+; CHECK: @var4 =
+@var4 = global i32* @var2, align 4
+
+define i32 @foo() {
+entry:
+  %0 = load i32*, i32** @var3, align 4
+  %1 = load i32, i32* %0, align 4
+  %2 = load i32*, i32** @var4, align 4
+  %3 = load i32, i32* %2, align 4
+  %add = add nsw i32 %3, %1
+  ret i32 %add
+}