[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 ↗

(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'?

[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.

include/llvm/IR/Module.h

/// @{
 
   const_global_object_iterator global_object_begin() const {
     return global_objects().begin();
   }
   const_global_object_iterator global_object_end() const {
     return global_objects().end();
   }
 
-  typedef concat_iterator<GlobalValue, iterator, global_iterator,
+  typedef concat_iterator<GlobalValue, global_iterator, iterator,
                           alias_iterator, ifunc_iterator>
       global_value_iterator;
-  typedef concat_iterator<const GlobalValue, const_iterator,
-                          const_global_iterator, const_alias_iterator,
+  typedef concat_iterator<const GlobalValue, const_global_iterator,
+                          const_iterator, const_alias_iterator,
                           const_ifunc_iterator>
       const_global_value_iterator;
 
   iterator_range<global_value_iterator> global_values() {
-    return concat<GlobalValue>(functions(), globals(), aliases(), ifuncs());
+    return concat<GlobalValue>(globals(), functions(), aliases(), ifuncs());
   }
   iterator_range<const_global_value_iterator> global_values() const {
-    return concat<const GlobalValue>(functions(), globals(), aliases(),
+    return concat<const GlobalValue>(globals(), functions(), aliases(),
                                      ifuncs());
   }
 
   global_value_iterator global_value_begin() { return global_values().begin(); }
   global_value_iterator global_value_end() { return global_values().end(); }
 
   const_global_value_iterator global_value_begin() const {
     return global_values().begin();

test/LTO/Resolution/X86/globalorder.ll

+; Test the order of global variables during LTO merging. Note that
+; this can change at any time, for any reason, or no reason whatsoever.
+; If you are depending on this order for correctness, your code has a
+; bug and should be fixed.
+;
+; 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
+}

test/Transforms/ThinLTOBitcodeWriter/split-internal-typeid.ll

 
 ; M0: @g = external global i8{{$}}
 ; M1: @g = global i8 42, !type !0, !type !1, !type !2
 @g = global i8 42, !type !1, !type !2, !type !4
 
 ; M0: define void @f()
 ; M1-NOT: @f()
 define void @f() {
-  ; M0: llvm.type.test{{.*}}metadata !"1$f50b51a12bb012bebbeff978335e34cf"
+  ; M0: llvm.type.test{{.*}}metadata !"1$761a10bdafb4c4efc0f254ab1655930a"
   %p = call i1 @llvm.type.test(i8* null, metadata !0)
-  ; M0: llvm.type.checked.load{{.*}}metadata !"2$f50b51a12bb012bebbeff978335e34cf"
+  ; M0: llvm.type.checked.load{{.*}}metadata !"2$761a10bdafb4c4efc0f254ab1655930a"
   %q = call {i8*, i1} @llvm.type.checked.load(i8* null, i32 0, metadata !3)
   ret void
 }
 
 declare i1 @llvm.type.test(i8*, metadata)
 declare {i8*, i1} @llvm.type.checked.load(i8*, i32, metadata)
 
 !0 = distinct !{}
-; M1: !0 = !{i32 0, !"1$f50b51a12bb012bebbeff978335e34cf"}
+; M1: !0 = !{i32 0, !"1$761a10bdafb4c4efc0f254ab1655930a"}
 !1 = !{i32 0, !0}
-; M1: !1 = !{i32 1, !"1$f50b51a12bb012bebbeff978335e34cf"}
+; M1: !1 = !{i32 1, !"1$761a10bdafb4c4efc0f254ab1655930a"}
 !2 = !{i32 1, !0}
 
 !3 = distinct !{}
-; M1: !2 = !{i32 0, !"2$f50b51a12bb012bebbeff978335e34cf"}
+; M1: !2 = !{i32 0, !"2$761a10bdafb4c4efc0f254ab1655930a"}
 !4 = !{i32 0, !3}