[static initializers] Emit global_ctors and global_dtors in reverse order when .ctors/.dtors are used.

[wolfgangp]

Summary

Commit c19f4f8069 caused some ordered dynamic initialization of static member variables to be treated like unordered initialization, i.e. put into global_ctors. This caused issues in some configurations, specifically when init_array is not used. This patch proposes to restrict this behaviour to the Microsoft ABI, where it is apparently necessary for correctness.

2 existing test cases are affected by this change.

This fixes PR50266.

[rnk]

+@rsmith @hans @aeubanks

I think this would be an unfortunate code size and startup time regression for Itanium C++ inline variables. The existing code was written under the assumption that vague linkage (GVA_DiscardableODR) implies no initialization ordering, but I think you've found a valid counterexample.

specifically when init_array is not used

Can you elaborate on why that is? Here's what I remember, and what I guess is happening. ELF has two initializer schemes: .init_array and .ctors. They are essentially equivalent, they are both arrays of function pointers, but one is called in reverse order and the other is called in forward order. The compiler knows which scheme is in use and it is controlled by -fuse-init-array.

The LLVM IR langref says that llvm.global_ctors are called in ascending priority order, and the order between initializers is not defined. That's not very helpful and often doesn't reflect reality. I wonder if we could do two things, perhaps separately:

1. emit llvm.global_ctors so that they are called in order of appearance in the IR array (is this not already true?)
2. define the order of initialization in LangRef

With the first change in place, we can be confident that so long as all includers of the StaticsClass in the test emit both initializers in the correct order, no matter which initializers prevail, they will be called in the correct order. Of course, this could break users relying on the existing ordering, nevermind that it is explicitly documented as undefined.

The second change is only a documentation change, but I would like to find a way to justify what LLVM does in GlobalOpt. GlobalOpt can effectively fold a dynamic initializer to constant memory in certain cases. That can only ever have the effect of making an initializer run earlier. As long as no initializers depend on observing uninitialized globals, that should be safe. The guarantee that we want to provide is that, for each initializer, all initializers prior to it in the global_ctors array will have run when it runs. Initializers that appear later may run earlier. Hopefully that covers both the usual way that .init_array sections are linked together and the way globalopt optimizes dynamic initialization.

[ychen]

The LLVM IR langref says that llvm.global_ctors are called in ascending priority order, and the order between initializers is not defined. That's not very helpful and often doesn't reflect reality. I wonder if we could do two things, perhaps separately:

1. emit llvm.global_ctors so that they are called in order of appearance in the IR array (is this not already true?)
2. define the order of initialization in LangRef

Is there anything preventing us from using the existing priority field to define the order instead of introducing the order among initializers with the same priority? If we go with 1., there would be no way to say that "the order does not matter" right?

[rnk]

In D103495#2794667, @ychen wrote:

Is there anything preventing us from using the existing priority field to define the order instead of introducing the order among initializers with the same priority? If we go with 1., there would be no way to say that "the order does not matter" right?

The priority is used mainly for inter-object initialization order. It moves the initializer into a .init_array.N section, for some number N. The programmer may be using existing numbers via __attribute__((init_priority(N))), so it isn't safe for the compiler to use anything other than the default initialization priority.

[ychen]

In D103495#2794684, @rnk wrote:

In D103495#2794667, @ychen wrote:

Is there anything preventing us from using the existing priority field to define the order instead of introducing the order among initializers with the same priority? If we go with 1., there would be no way to say that "the order does not matter" right?

The priority is used mainly for inter-object initialization order. It moves the initializer into a .init_array.N section, for some number N. The programmer may be using existing numbers via __attribute__((init_priority(N))), so it isn't safe for the compiler to use anything other than the default initialization priority.

I see. It makes sense to define the order at IR level then since the order is there in .init_array.N/.ctors section nevertheless.

[wolfgangp]

In D103495#2794329, @rnk wrote:

+@rsmith @hans @aeubanks

specifically when init_array is not used

Can you elaborate on why that is? Here's what I remember, and what I guess is happening. ELF has two initializer schemes: .init_array and .ctors. They are essentially equivalent, they are both arrays of function pointers, but one is called in reverse order and the other is called in forward order. The compiler knows which scheme is in use and it is controlled by -fuse-init-array.

For PS4, we use the .ctors scheme, and so the initialization order was suddenly reversed, which was not noticed for a while until the user had a dependency on the previous initialization. And using init_array or not has currently no effect on the order of emission of global_ctors.

The LLVM IR langref says that llvm.global_ctors are called in ascending priority order, and the order between initializers is not defined. That's not very helpful and often doesn't reflect reality. I wonder if we could do two things, perhaps separately:

1. emit llvm.global_ctors so that they are called in order of appearance in the IR array (is this not already true?)

AFAICT, this is already happening. After sorting by priority, the order remains intact at emission. So with -fno-use-init-array0we're going to emit global_ctors in reverse order, I suppose.

2. define the order of initialization in LangRef

With the first change in place, we can be confident that so long as all includers of the StaticsClass in the test emit both initializers in the correct order, no matter which initializers prevail, they will be called in the correct order. Of course, this could break users relying on the existing ordering, nevermind that it is explicitly documented as undefined.

The second change is only a documentation change, but I would like to find a way to justify what LLVM does in GlobalOpt. GlobalOpt can effectively fold a dynamic initializer to constant memory in certain cases. That can only ever have the effect of making an initializer run earlier. As long as no initializers depend on observing uninitialized globals, that should be safe. The guarantee that we want to provide is that, for each initializer, all initializers prior to it in the global_ctors array will have run when it runs. Initializers that appear later may run earlier. Hopefully that covers both the usual way that .init_array sections are linked together and the way globalopt optimizes dynamic initialization.

[rnk]

In D103495#2794870, @wolfgangp wrote:

For PS4, we use the .ctors scheme, and so the initialization order was suddenly reversed, which was not noticed for a while until the user had a dependency on the previous initialization. And using init_array or not has currently no effect on the order of emission of global_ctors.

Exactly, that's my suggestion: if fno-use-init-array is set, emit global_ctors into the .ctors section in reverse order. That way -fno-use-init-array doesn't reverse the order of initialization *inside* a given LLVM module, even if it reverses the order in which *modules* are initialized.

[wolfgangp]

Following the suggestion to define an order of initialization for the entries in llvm.global_ctors and llvm.global_dtors this is mainly a documentation change, as well as a simple reversed emission of global_ctors/dtors entries when InitArray is not used.
3 test cases are affected, 2 of them just by a reversed order of emission of priority-suffixed sections. I added a couple of entries to the third test case to verify in-order emission of entries with equal priority.

[rnk]

+ various .ctors stakeholders + @MaskRay + @mstorsjo

This change was my idea, so I want to make sure there is buy in from other folks who use -fno-init-array. This has the potential to break user programs that rely on the order of dynamic initialization *within* a TU, but there will be no change in order between TUs. This might also deserve a release note.

Overall this should be a positive change. In the past users have reported QoI issues where a template with an SDM instantiated earlier in the TU gets initialized after a template instantiated later in the TU. Technically, those initializers are not ordered, so this is not a correctness issue, but it would be nicer if initializers ran in source order.

We might need to add docs here about what happens when the initializer is in a comdat group, since the order guarantee in that case is very subtle.

[efriedma]

Are there any existing optimizations that might be affected by this? In particular, I think GlobalOpt implicitly reorders functions in global_ctors.

[MaskRay]

Thanks for tagging us.

glibc has supported DT_INIT_ARRAY/DT_FINI_ARRAY since 1999. GCC 4.7 defaulted to .init_array/.fini_array on glibc >= 2.4 and most Linux distributions have thus made the switch for many years. Actually, most ELF operating systems have switched to .init_array/.fini_array (FreeBSD added the support in 2012, OpenBSD in 2016, NetBSD in 2018.

.ctors doesn't have aren't many users now, but my users are unfortunately still using .ctors:(
Our tests can pass with .init_array + ld.lld --shuffle-sections=.init_array=-1, so I think we don't have code relying on the buggy .ctors order
(i.e. we don't have problems due to the shuffled dynamic initialization order *within* a TU).

This patch improves the situation for other users and we should do it.

Can you check whether clang/lib/CodeGen/CGDeclCXX.cpp:507 needs any comment update?
The subject "Don't put ordered dynamic initializers of static variables into global_ctors" needs an update as well.

llvm/test/CodeGen/X86/constructor.ll

61–63

Worth a comment that we check f/i/j are in order.

[MaskRay]

In D103495#2804254, @efriedma wrote:

Are there any existing optimizations that might be affected by this? In particular, I think GlobalOpt implicitly reorders functions in global_ctors.

Thanks for mentioning llvm::optimizeGlobalCtorsList. It keeps the order of the remaining items so I assume defining an order among constructors with the same priority should be fine.

[mstorsjo]

Thanks for looping me in; I don't have any objection to this, as far as I can see, the reasoning seems sensible, and the most brittle testcase I have (from what I remember offhand) seems to run fine with this change.

[rnk]

I think we do need to think about globalopt. Consider this example:

extern "C" {
int printf(const char *, ...);
extern int sharedState;
int sharedState = 0;
int init1() {
  asm volatile(""); // block globalopt
  return ++sharedState;
}
int init2() { return ++sharedState; }
int gv1 = init1();
int gv2 = init2();
}

int main() {
  printf("gv1: %d\n", gv1);
  printf("gv2: %d\n", gv2);
}

These initializers are ordered, and gv1 should be 1 and gv2 should be 2. Clang produces a single shared initializer @_GLOBAL__sub_I_${src} to ensure this ordering. However, if you manually split the initializers apart (https://reviews.llvm.org/P8266) and try to rely on the new langref ordering, globalopt will fold the second initializer and it appears as if init2 ran first. I have these two files in t.cpp and t.ll, and see the results:

$ clang -O2 t.cpp  && ./a.out
gv1: 1
gv2: 2

$ clang -O2 t.ll  && ./a.out
gv1: 2
gv2: 1

I've never been totally comfortable with the soundness of globalopt, so I wonder if that's the part that really needs to change. The value of globalopt is that it can fold simple constructors, and those don't access other mutable global variables. If we had some way of telling globalopt that it is only allowed to read from constants and the GV being initialized, that would solve this issue. Right now, there is no link in the IR between a global and its initializer unless the global is comdat.

---

As for this patch, I think we're not ready to add the LangRef guarantee. However, the code change is good: it ensures that -f[no-]use-init-array doesn't needlessly reverse the order of initialization in the TU.

Without the langref guarantee, clang is skating on thin ice: inline static data member initializers may not be run in source order. However, globalopt is currently completely unable to fold initializers for weak/comdat globals, so in practice, there is no risk to users.

I think we can defer the langref change until the next time someone makes a serious investment in globalopt. I think @asbirlea and @aeubanks might be interested in that sometime later this year.

[wolfgangp]

Given the assessment on GlobalOpt, removed the LangRef changes and updated the subject line.

[wolfgangp]

In D103495#2804685, @MaskRay wrote:

Can you check whether clang/lib/CodeGen/CGDeclCXX.cpp:507 needs any comment update?
The subject "Don't put ordered dynamic initializers of static variables into global_ctors" needs an update as well.

If we are not defining the initialization order, it seems the comment doesn't need any updating yet, although once we do, it definitely will.

[efriedma]

LGTM. Making the order of constructors independent of UseInitArray seems obviously good in any case.

[jyknight]

Won't this change cause weird effects with LTO, when you're merging multiple TUs' global_ctors arrays before emitting? Won't this end up reversing the order of the files, as well as the order of the functions within a single file? That does not seem likely to be expected, right?

The compiler knows which scheme is in use and it is controlled by -fuse-init-array.

This isn't exactly true -- the linker (binutils ld and ld.gold) can translate ctors to init_array, so we also need to look at what they do. I can't actually find the code that does it in bfd, but in examination of its output, it looks like it does reverse the order of pointers within a ctors section when translating to init_array, in order to preserve the expected "backwards" order that ctors users "wanted". And gold does the same -- except it is buggy, because it reverses the order of the text itself, yet not the relocation entries associated with it. So depending on whether you're building a PIC binary or not, you get different behavior (sigh). Anyhow, modulo that gold bug, it looks like this is actually OK.

[rnk]

In D103495#2806097, @jyknight wrote:

Won't this change cause weird effects with LTO, when you're merging multiple TUs' global_ctors arrays before emitting? Won't this end up reversing the order of the files, as well as the order of the functions within a single file? That does not seem likely to be expected, right?

True, I think that is an issue, and that probably does affect Sony's actual customers. I hear games tend to use regular LTO, so this will in fact reverse the order of initialization between object files for those users. The only solution I can think of would be to bring the LTO library into the game. It must know whether .ctors of .init_array are in use, since it generates code and it has to pick the section. To ensure that initialization of objects happens in reverse command line order as expected of users of -fno-init-array, the linker would join global_ctors in reverse order. That's not elegant. It encodes this knowledge in two places instead of one. But it does move in the direction of making things more defined, more deterministic, and that seems like a good thing.

So, a question for @wolfgangp and @probinson , do we need to make adjustments to the LTO library, or is this OK as is?

I think for non-Sony users we can accept the change in initialization order.

[wolfgangp]

In D103495#2808247, @rnk wrote:

So, a question for @wolfgangp and @probinson , do we need to make adjustments to the LTO library, or is this OK as is?

We never guaranteed our licensees any particular initialization order (between modules), so after checking with my team members I think this is OK as is.

[wolfgangp]

If nobody has any more objections, I'll commit this change, then. Please let me know if you think otherwise.

[rnk]

lgtm

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

 /// priority.
 void AsmPrinter::emitXXStructorList(const DataLayout &DL, const Constant *List,
                                     bool IsCtor) {
   SmallVector<Structor, 8> Structors;
   preprocessXXStructorList(DL, List, Structors);
   if (Structors.empty())
     return;
 
+  // Emit the structors in reverse order if we are using the .ctor/.dtor
+  // initialization scheme.
+  if (!TM.Options.UseInitArray)
+    std::reverse(Structors.begin(), Structors.end());
+
   const Align Align = DL.getPointerPrefAlignment();
   for (Structor &S : Structors) {
     const TargetLoweringObjectFile &Obj = getObjFileLowering();
     const MCSymbol *KeySym = nullptr;
     if (GlobalValue *GV = S.ComdatKey) {
       if (GV->isDeclarationForLinker())
         // If the associated variable is not defined in this module
         // (it might be available_externally, or have been an

llvm/test/CodeGen/SPARC/constructor.ll

 ; RUN: llc -mtriple sparc-sun-solaris2.11 -use-ctors < %s | FileCheck --check-prefix=CTOR %s
 ; RUN: llc -mtriple sparc-sun-solaris2.11 < %s | FileCheck --check-prefix=INIT-ARRAY %s
 @llvm.global_ctors = appending global [2 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @f, i8* null}, { i32, void ()*, i8* } { i32 15, void ()* @g, i8* @v }]
 
 @v = weak_odr global i8 0
 
 define void @f() {
 entry:
   ret void
 }
 
 define void @g() {
 entry:
   ret void
 }
 
-; CTOR:    .section  .ctors.65520,#alloc,#write
-; CTOR-NEXT: .p2align      2
-; CTOR-NEXT: .word  g
-; CTOR-NEXT: .section      .ctors,#alloc,#write
+; CTOR:      .section      .ctors,#alloc,#write
 ; CTOR-NEXT: .p2align      2
 ; CTOR-NEXT: .word  f
+; CTOR-NEXT: .section      .ctors.65520,#alloc,#write
+; CTOR-NEXT: .p2align      2
+; CTOR-NEXT: .word  g
 
 ; INIT-ARRAY:    .section  .init_array.15,#alloc,#write
 ; INIT-ARRAY-NEXT: .p2align  2
 ; INIT-ARRAY-NEXT: .word g
 ; INIT-ARRAY-NEXT: .section  .init_array,#alloc,#write
 ; INIT-ARRAY-NEXT: .p2align  2
 ; INIT-ARRAY-NEXT: .word f

llvm/test/CodeGen/X86/2011-08-29-InitOrder.ll

 ; RUN: llc < %s -mtriple=i386-linux-gnu -use-ctors | FileCheck %s --check-prefix=CHECK-DEFAULT
 ; RUN: llc < %s -mtriple=i386-apple-darwin | FileCheck %s --check-prefix=CHECK-DARWIN
 ; PR5329
 
 @llvm.global_ctors = appending global [3 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 2000, void ()* @construct_2, i8* null }, { i32, void ()*, i8* } { i32 3000, void ()* @construct_3, i8* null }, { i32, void ()*, i8* } { i32 1000, void ()* @construct_1, i8* null }]
-; CHECK-DEFAULT: .section        .ctors.64535,"aw",@progbits
-; CHECK-DEFAULT: .long construct_1
-; CHECK-DEFAULT: .section        .ctors.63535,"aw",@progbits
-; CHECK-DEFAULT: .long construct_2
 ; CHECK-DEFAULT: .section        .ctors.62535,"aw",@progbits
 ; CHECK-DEFAULT: .long construct_3
+; CHECK-DEFAULT: .section        .ctors.63535,"aw",@progbits
+; CHECK-DEFAULT: .long construct_2
+; CHECK-DEFAULT: .section        .ctors.64535,"aw",@progbits
+; CHECK-DEFAULT: .long construct_1
 
 ; CHECK-DARWIN: .long _construct_1
 ; CHECK-DARWIN-NEXT: .long _construct_2
 ; CHECK-DARWIN-NEXT: .long _construct_3
 
 @llvm.global_dtors = appending global [3 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 2000, void ()* @destruct_2, i8* null }, { i32, void ()*, i8* } { i32 1000, void ()* @destruct_1, i8* null }, { i32, void ()*, i8* } { i32 3000, void ()* @destruct_3, i8* null }]
-; CHECK-DEFAULT: .section        .dtors.64535,"aw",@progbits
-; CHECK-DEFAULT: .long destruct_1
-; CHECK-DEFAULT: .section        .dtors.63535,"aw",@progbits
-; CHECK-DEFAULT: .long destruct_2
 ; CHECK-DEFAULT: .section        .dtors.62535,"aw",@progbits
 ; CHECK-DEFAULT: .long destruct_3
+; CHECK-DEFAULT: .section        .dtors.63535,"aw",@progbits
+; CHECK-DEFAULT: .long destruct_2
+; CHECK-DEFAULT: .section        .dtors.64535,"aw",@progbits
+; CHECK-DEFAULT: .long destruct_1
 
 ; CHECK-DARWIN:      .long _destruct_1
 ; CHECK-DARWIN-NEXT: .long _destruct_2
 ; CHECK-DARWIN-NEXT: .long _destruct_3
 
 declare void @construct_1()
 declare void @construct_2()
 declare void @construct_3()
 declare void @destruct_1()
 declare void @destruct_2()
 declare void @destruct_3()

llvm/test/CodeGen/X86/constructor.ll

 ; RUN: llc -mtriple x86_64 < %s | FileCheck --check-prefix=INIT-ARRAY %s
 ; RUN: llc -mtriple x86_64-pc-linux -use-ctors < %s | FileCheck --check-prefix=CTOR %s
 ; RUN: llc -mtriple x86_64-unknown-freebsd -use-ctors < %s | FileCheck --check-prefix=CTOR %s
 ; RUN: llc -mtriple x86_64-pc-solaris2.11 -use-ctors < %s | FileCheck --check-prefix=CTOR %s
 ; RUN: llc -mtriple x86_64-pc-linux < %s | FileCheck --check-prefix=INIT-ARRAY %s
 ; RUN: llc -mtriple x86_64-unknown-freebsd < %s | FileCheck --check-prefix=INIT-ARRAY %s
 ; RUN: llc -mtriple x86_64-pc-solaris2.11 < %s | FileCheck --check-prefix=INIT-ARRAY %s
 ; RUN: llc -mtriple x86_64-unknown-nacl < %s | FileCheck --check-prefix=NACL %s
 ; RUN: llc -mtriple i586-intel-elfiamcu -use-ctors < %s | FileCheck %s --check-prefix=MCU-CTORS
 ; RUN: llc -mtriple i586-intel-elfiamcu < %s | FileCheck %s --check-prefix=MCU-INIT-ARRAY
 ; RUN: llc -mtriple x86_64-win32-gnu < %s | FileCheck --check-prefix=COFF-CTOR %s
[e-mail]_ctors = appending global [3 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @f, i8* null}, { i32, void ()*, i8* } { i32 15, void ()* @g, i8* @v }, { i32, void ()*, i8* } { i32 55555, void ()* @h, i8* @v }]
[e-mail]_ctors = appending global [5 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @f, i8* null}, { i32, void ()*, i8* } { i32 15, void ()* @g, i8* @v }, { i32, void ()*, i8* } { i32 55555, void ()* @h, i8* @v }, { i32, void ()*, i8* } { i32 65535, void ()* @i, i8* null }, { i32, void ()*, i8* } { i32 65535, void ()* @j, i8* null }]
 
 @v = weak_odr global i8 0
 
 define void @f() {
 entry:
   ret void
 }
 
 define void @g() {
 entry:
   ret void
 }
 
 define void @h() {
 entry:
   ret void
 }
 
-; CTOR:   .section  .ctors.65520,"aGw",@progbits,v,comdat
+define void @i() {
+entry:
+  ret void
+}
+
+define void @j() {
+entry:
+  ret void
+}
+
+; CTOR:         .section  .ctors,"aw",@progbits
 ; CTOR-NEXT:  .p2align  3
-; CTOR-NEXT:  .quad g
+; CTOR-NEXT:  .quad j
+; CTOR-NEXT:  .quad i
+; CTOR-NEXT:  .quad f
 ; CTOR-NEXT:  .section  .ctors.09980,"aGw",@progbits,v,comdat
 ; CTOR-NEXT:  .p2align  3
 ; CTOR-NEXT:  .quad h
-; CTOR-NEXT:  .section  .ctors,"aw",@progbits
+; CTOR-NEXT:  .section  .ctors.65520,"aGw",@progbits,v,comdat
 ; CTOR-NEXT:  .p2align  3
-; CTOR-NEXT:  .quad f
+; CTOR-NEXT:  .quad g
 
 ; INIT-ARRAY:   .section  .init_array.15,"aGw",@init_array,v,comdat
 ; INIT-ARRAY-NEXT:  .p2align  3
 ; INIT-ARRAY-NEXT:  .quad g
 ; INIT-ARRAY-NEXT:  .section  .init_array.55555,"aGw",@init_array,v,comdat
 ; INIT-ARRAY-NEXT:  .p2align  3
 ; INIT-ARRAY-NEXT:  .quad h
 ; INIT-ARRAY-NEXT:  .section  .init_array,"aw",@init_array
 ; INIT-ARRAY-NEXT:  .p2align  3
 ; INIT-ARRAY-NEXT:  .quad f
+; INIT-ARRAY-NEXT:  .quad i
+; INIT-ARRAY-NEXT:  .quad j
 
 ; NACL:   .section  .init_array.15,"aGw",@init_array,v,comdat
 ; NACL-NEXT:  .p2align  2
 ; NACL-NEXT:  .long g
 ; NACL-NEXT:  .section  .init_array.55555,"aGw",@init_array,v,comdat
 ; NACL-NEXT:  .p2align  2
 ; NACL-NEXT:  .long h
 ; NACL-NEXT:  .section  .init_array,"aw",@init_array
 ; NACL-NEXT:  .p2align  2
 ; NACL-NEXT:  .long f
+; NACL-NEXT:  .long i
+; NACL-NEXT:  .long j
 
 ; MCU-CTORS:         .section        .ctors,"aw",@progbits
 ; MCU-INIT-ARRAY:    .section        .init_array,"aw",@init_array
 
 ; COFF-CTOR:    .section  .ctors.65520,"dw",associative,v
 ; COFF-CTOR-NEXT: .p2align  3
 ; COFF-CTOR-NEXT: .quad g
 ; COFF-CTOR-NEXT: .section  .ctors.09980,"dw",associative,v
 ; COFF-CTOR-NEXT: .p2align  3
 ; COFF-CTOR-NEXT: .quad h
 ; COFF-CTOR-NEXT: .section  .ctors,"dw"
 ; COFF-CTOR-NEXT: .p2align  3
 ; COFF-CTOR-NEXT: .quad f
+; COFF-CTOR-NEXT: .quad i
+; COFF-CTOR-NEXT: .quad j