[CodeGen] Sort llvm.global_ctors by lexing order before emission

[ychen]

Summary

Fixes https://github.com/llvm/llvm-project/issues/55804

The lexing order is already bookkept in DelayedCXXInitPosition but we
were not using it based on the wrong assumption that inline variable is
unordered. This patch fixes it by ordering entries in llvm.global_ctors
by orders in DelayedCXXInitPosition.

for llvm.global_ctors entries without a lexing order, ordering them by
the insertion order.

(This *mostly* orders the template instantiation in
https://reviews.llvm.org/D126341 intuitively, minus one tweak for which I'll
submit a separate patch.)

[ychen]

lint

[ychen]

gentle ping..

[ychen]

ping.

[ychen]

ping

[rnk]

I think this is a straightforward improvement. I would like to see it land. Do the other reviewers have any outstanding concerns?

+cc other clang people @ayzhao @ilya-biryukov @usaxena95

clang/lib/CodeGen/CodeGenModule.cpp

564

Please move this sorting into EmitCtorList and apply it to destructors. I believe they are currently emitted in source order, and the loader executes them in reverse order, so we get the desired reverse source order cleanup behavior.

[aaron.ballman]

This looks correct per my reading of [basic.start.dynamic], but is this an ABI breaking change that we may want to use ABI versioning for in case someone is relying on the old order for some reason?

Also, the change should have a release note for the fix.

[ychen]

clang/lib/CodeGen/CodeGenModule.cpp

564

I looked into this. They are indeed "currently emitted in source order". However, if a dtor ever uses an entry in llvm.global_dtors, it must have bailed out of deferred emission here (https://github.com/llvm/llvm-project/blob/69c09d11f877a35655e285cda96ec0699e385fc9/clang/lib/CodeGen/CodeGenModule.cpp#L3256-L3263), which is to say, the corresponding ctor is also in lexing order. So the situation is either the ctor/dtor pair both use lexing order, or there is no dtor (like inline int with an initializer) and the ctor is deferred/reordered where this patch kicks in.

[rjmccall]

There's no compiler interoperation problem here; it's just a semantic concern that someone could've been relying on the old behavior. The new behavior is (AIUI) clearly required by the language standard, and I don't think we want to get into the business of providing "do the old buggy thing" flags for everything we fix like this.

[aaron.ballman]

In D127233#3726613, @rjmccall wrote:

There's no compiler interoperation problem here; it's just a semantic concern that someone could've been relying on the old behavior. The new behavior is (AIUI) clearly required by the language standard, and I don't think we want to get into the business of providing "do the old buggy thing" flags for everything we fix like this.

Thanks for verifying! (I agree that we don't want to get into the business of providing flags for old buggy behavior, too.)

[efriedma]

is this an ABI breaking change

It only affects the order of initialization within a file, so it doesn't really have any implications for the binary ABI. It might break code, of course, but that's a different issue.

If we want a flag to maintain the old behavior, we need to define what the "old" order is. Not sure that's worthwhile.

clang/lib/CodeGen/CGDeclCXX.cpp

592

This ensures delayed initialization calls are ordered relative to each other... but are they ordered correctly relative to non-delayed initialization calls? I'm skeptical that using a LexOrder of "~0U" is really correct. (For example, if you change the variable "b" in your testcase to a struct with a destructor.)

clang/lib/CodeGen/CodeGenModule.cpp

564

Is MayBeEmittedEagerly always true for variables with destructors?

[ychen]

clang/lib/CodeGen/CGDeclCXX.cpp

592

Hmm, That's a great point. I didn't think of that. I'll take a look.

clang/lib/CodeGen/CodeGenModule.cpp

564

Yeah, for this and CodeGenModule::MustBeEmitted, as long as the destructors are not constexpr where init order is not an issue.

https://github.com/llvm/llvm-project/blob/aacf1a9742f714dd432117d82d19a007289c3dee/clang/lib/AST/ASTContext.cpp#L11646-L11648

[ychen]

• use correct lexing order for non-deferred constructors.

[ychen]

• rebase

[efriedma]

clang/lib/CodeGen/CGDeclCXX.cpp

592

Using CXXGlobalInits.size() like this is sort of hard to reason about: multiple values can end up with the same LexOrder. (I'm not sure if all the values with the same LexOrder end up sorted correctly.)

Instead of trying to reason about whether this is right, can we just use a separate counter to assign a unique index to each global init?

[ychen]

clang/lib/CodeGen/CGDeclCXX.cpp

592

Agreed that this whole thing is confusing if not looked at closely. IIUC, LexOrder is unique for each global variables and all global variables with an initialization are pushed into CXXGlobalInits in lexing order regardless of deferred/non-deferred emission. I could add a counter which basically tracks the size of CXXGlobalInits. Which do you think is more clear: add an explicit counter or add more comments to CXXGlobalInits explaining the usage?

[efriedma]

clang/lib/CodeGen/CGDeclCXX.cpp

592

For each global, CXXGlobalInits is supposed to contain either a pointer to a function, or nullptr to indicate emission was delayed. I guess that works as a unique ordering. But it looks like this codepath doesn't actually insert anything into CXXGlobalInits; it skips that, and goes straight to AddGlobalCtor. I think that would lead to multiple globals with the same index? (Not 100% sure about this since the CXXGlobalInits code is scattered all over.)

If we do expect that there won't be multiple globals with the same index, please add an assertion after we sort GlobalCtors, that there aren't any entries with the same LexOrder value (besides ~0).

A comment explaining the uniqueness of LexOrder is probably sufficient, given nothing else is trying to produce a LexOrder.

[ychen]

• add more explanation as comments
• rebase

clang/lib/CodeGen/CGDeclCXX.cpp

592

(Not 100% sure about this since the CXXGlobalInits code is scattered all over.)

I spoke too soon. You're correct. Using CXXGlobalInits.size() is correct in that it is the lex order number for the next deferred global variable. So as expected, its lex order is different from/bigger than the lex order of all previous deferred global variables, and regardless the next global variable is non-deferred or deferred, they have the same lex order as the current one but the order of insertion into llvm.global_ctors is maintained by the following stable sort.

I tried to implement the lex order counter approach. Due to the deferred/non-deferred partition, I could not simply track it using a plain integer counter. Instead, it would look almost the same as DelayedCXXInitPosition except that it would contain both deferred/non-deferred global variables. It does not feel like easier to understand the code since there is one more non-trivial state to track. I'll try clear this up in the comments instead.

[efriedma]

clang/lib/CodeGen/CGDeclCXX.cpp

592

That's a little fragile, but okay, I guess.

clang/test/CodeGenCXX/static-init-inline-variable.cpp

15

I'd like to see more tests here. The given testcase passes without your patch.

[ychen]

• add more test cases

[efriedma]

LGTM

clang/lib/CodeGen/CGDeclCXX.cpp

if (D->getTLSKind()) {
     // 200 and "init_seg(lib)" corresponds to priority 400.
     int Priority = -1;
     if (ISA->getSection() == ".CRT$XCC")
       Priority = 200;
     else if (ISA->getSection() == ".CRT$XCL")
       Priority = 400;
 
     if (Priority != -1)
-      AddGlobalCtor(Fn, Priority, COMDATKey);
+      AddGlobalCtor(Fn, Priority, ~0U, COMDATKey);
     else
       EmitPointerToInitFunc(D, Addr, Fn, ISA);
   } else if (auto *IPA = D->getAttr<InitPriorityAttr>()) {
     OrderGlobalInitsOrStermFinalizers Key(IPA->getPriority(),
                                           PrioritizedCXXGlobalInits.size());
     PrioritizedCXXGlobalInits.push_back(std::make_pair(Key, Fn));
   } else if (isTemplateInstantiation(D->getTemplateSpecializationKind()) ||
              getContext().GetGVALinkageForVariable(D) == GVA_DiscardableODR ||
if (D->getTLSKind()) {
     // If the global is externally visible, put the initializer into a COMDAT
     // group with the global being initialized.  On most platforms, this is a
     // minor startup time optimization.  In the MS C++ ABI, there are no guard
     // variables, so this COMDAT key is required for correctness.
     //
     // SelectAny globals will be comdat-folded. Put the initializer into a
     // COMDAT group associated with the global, so the initializers get folded
     // too.
-
-    AddGlobalCtor(Fn, 65535, COMDATKey);
+    I = DelayedCXXInitPosition.find(D);
+    // CXXGlobalInits.size() is the lex order number for the next deferred
+    // VarDecl. Use it when the current VarDecl is non-deferred. Although this
+    // lex order number is shared between current VarDecl and some following
+    // VarDecls, their order of insertion into `llvm.global_ctors` is the same
+    // as the lexing order and the following stable sort would preserve such
+    // order.
+    unsigned LexOrder =
+        I == DelayedCXXInitPosition.end() ? CXXGlobalInits.size() : I->second;
+    AddGlobalCtor(Fn, 65535, LexOrder, COMDATKey);
     if (COMDATKey && (getTriple().isOSBinFormatELF() ||
                       getTarget().getCXXABI().isMicrosoft())) {
       // When COMDAT is used on ELF or in the MS C++ ABI, the key must be in
       // llvm.used to prevent linker GC.
       addUsedGlobal(COMDATKey);
     }
 
     // If we used a COMDAT key for the global ctor, the init function can be

clang/lib/CodeGen/CodeGenModule.h

 /// This class organizes the cross-function state that is used while generating
 /// LLVM code.
 class CodeGenModule : public CodeGenTypeCache {
   CodeGenModule(const CodeGenModule &) = delete;
   void operator=(const CodeGenModule &) = delete;
 
 public:
   struct Structor {
-    Structor() : Priority(0), Initializer(nullptr), AssociatedData(nullptr) {}
-    Structor(int Priority, llvm::Constant *Initializer,
+    Structor()
+        : Priority(0), LexOrder(~0u), Initializer(nullptr),
+          AssociatedData(nullptr) {}
+    Structor(int Priority, unsigned LexOrder, llvm::Constant *Initializer,
              llvm::Constant *AssociatedData)
-        : Priority(Priority), Initializer(Initializer),
+        : Priority(Priority), LexOrder(LexOrder), Initializer(Initializer),
           AssociatedData(AssociatedData) {}
     int Priority;
+    unsigned LexOrder;
     llvm::Constant *Initializer;
     llvm::Constant *AssociatedData;
   };
 
   typedef std::vector<Structor> CtorList;
 
 private:
   ASTContext &Context;
void EmitCXXGlobalVarDeclInitFunc(const VarDecl *D,
                                     llvm::GlobalVariable *Addr,
                                     bool PerformInit);
 
   void EmitPointerToInitFunc(const VarDecl *VD, llvm::GlobalVariable *Addr,
                              llvm::Function *InitFunc, InitSegAttr *ISA);
 
   // FIXME: Hardcoding priority here is gross.
   void AddGlobalCtor(llvm::Function *Ctor, int Priority = 65535,
+                     unsigned LexOrder = ~0U,
                      llvm::Constant *AssociatedData = nullptr);
   void AddGlobalDtor(llvm::Function *Dtor, int Priority = 65535,
                      bool IsDtorAttrFunc = false);
 
   /// EmitCtorList - Generates a global array of functions and priorities using
   /// the given list and name. This array will have appending linkage and is
   /// suitable for use as a LLVM constructor or destructor array. Clears Fns.
   void EmitCtorList(CtorList &Fns, const char *GlobalName);

clang/lib/CodeGen/CodeGenModule.cpp

 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/Module.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/TargetInfo.h"
 #include "clang/Basic/Version.h"
 #include "clang/CodeGen/BackendUtil.h"
 #include "clang/CodeGen/ConstantInitBuilder.h"
 #include "clang/Frontend/FrontendDiagnostic.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Frontend/OpenMP/OMPIRBuilder.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
void CodeGenModule::Release() {
   }
   if (PGOReader) {
     getModule().setProfileSummary(
         PGOReader->getSummary(/* UseCS */ false).getMD(VMContext),
         llvm::ProfileSummary::PSK_Instr);
     if (PGOStats.hasDiagnostics())
       PGOStats.reportDiagnostics(getDiags(), getCodeGenOpts().MainFileName);
   }
+  llvm::stable_sort(GlobalCtors, [](const Structor &L, const Structor &R) {
+    return L.LexOrder < R.LexOrder;
+  });
   EmitCtorList(GlobalCtors, "llvm.global_ctors");
   EmitCtorList(GlobalDtors, "llvm.global_dtors");
   EmitGlobalAnnotations();
   EmitStaticExternCAliases();
   checkAliases();
   EmitDeferredUnusedCoverageMappings();
   CodeGenPGO(*this).setValueProfilingFlag(getModule());
   if (CoverageMapping)

 
 llvm::GlobalValue *CodeGenModule::GetGlobalValue(StringRef Name) {
   return getModule().getNamedValue(Name);
 }
 
 /// AddGlobalCtor - Add a function to the list that will be called before
 /// main() runs.
 void CodeGenModule::AddGlobalCtor(llvm::Function *Ctor, int Priority,
+                                  unsigned LexOrder,
                                   llvm::Constant *AssociatedData) {
   // FIXME: Type coercion of void()* types.
-  GlobalCtors.push_back(Structor(Priority, Ctor, AssociatedData));
+  GlobalCtors.push_back(Structor(Priority, LexOrder, Ctor, AssociatedData));
 }
 
 /// AddGlobalDtor - Add a function to the list that will be called
 /// when the module is unloaded.
 void CodeGenModule::AddGlobalDtor(llvm::Function *Dtor, int Priority,
                                   bool IsDtorAttrFunc) {
   if (CodeGenOpts.RegisterGlobalDtorsWithAtExit &&
       (!getContext().getTargetInfo().getTriple().isOSAIX() || IsDtorAttrFunc)) {
     DtorsUsingAtExit[Priority].push_back(Dtor);
     return;
   }
 
   // FIXME: Type coercion of void()* types.
-  GlobalDtors.push_back(Structor(Priority, Dtor, nullptr));
+  GlobalDtors.push_back(Structor(Priority, ~0U, Dtor, nullptr));
 }
 
 void CodeGenModule::EmitCtorList(CtorList &Fns, const char *GlobalName) {
   if (Fns.empty()) return;
 
   // Ctor function type is void()*.
   llvm::FunctionType* CtorFTy = llvm::FunctionType::get(VoidTy, false);
   llvm::Type *CtorPFTy = llvm::PointerType::get(CtorFTy,

clang/lib/CodeGen/ItaniumCXXABI.cpp

for (auto *Dtor : Dtors) {
         // reasonably call with the correct CC.  Go ahead and cast it to the
         // right prototype.
         CGF.registerGlobalDtorWithAtExit(
             llvm::ConstantExpr::getBitCast(Dtor, dtorTy));
       }
     }
 
     CGF.FinishFunction();
-    AddGlobalCtor(GlobalInitFn, Priority, nullptr);
+    AddGlobalCtor(GlobalInitFn, Priority);
   }
 
   if (getCXXABI().useSinitAndSterm())
     unregisterGlobalDtorsWithUnAtExit();
 }
 
 /// Register a global destructor as best as we know how.
 void ItaniumCXXABI::registerGlobalDtor(CodeGenFunction &CGF, const VarDecl &D,

clang/test/CodeGenCXX/static-init-inline-variable.cpp

+// RUN: %clang_cc1 -std=c++17 -S -emit-llvm -disable-llvm-passes -o - %s -triple x86_64-linux-gnu | FileCheck %s
+
+struct A {
+  int x;
+  A(int x) : x(x) {}
+  ~A() {}
+};
+
+namespace DeferredSequence {
+inline int a = 1;
+inline int b = a + 1;
+inline int c = b + 1;
+inline int d = c + 1;
+int e = d;
+}
+
+namespace MixedSequence {
+inline A a(1);
+inline int x = a.x + 1;
+inline int y = x + 1;
+inline A b(y);
+inline int z = b.x + 1;
+inline int w = z + 1;
+inline A c(b.x);
+inline A d(c.x);
+int t = w;
+}
+
+namespace NonDeferredSequence {
+inline A a(1);
+inline A b(a.x);
+inline A c(b.x);
+inline A d(c.x);
+}
+
+// CHECK: @llvm.global_ctors = appending global [16 x { i32, ptr, ptr }] [
+// CHECK-SAME: { i32, ptr, ptr } { i32 65535, ptr @__cxx_global_var_init.12, ptr @_ZN16DeferredSequence1bE },
+// CHECK-SAME: { i32, ptr, ptr } { i32 65535, ptr @__cxx_global_var_init.11, ptr @_ZN16DeferredSequence1cE },
+// CHECK-SAME: { i32, ptr, ptr } { i32 65535, ptr @__cxx_global_var_init.10, ptr @_ZN16DeferredSequence1dE },
+// CHECK-SAME: { i32, ptr, ptr } { i32 65535, ptr @__cxx_global_var_init.1,  ptr @_ZN13MixedSequence1aE },
+// CHECK-SAME: { i32, ptr, ptr } { i32 65535, ptr @__cxx_global_var_init.14, ptr @_ZN13MixedSequence1xE },
+// CHECK-SAME: { i32, ptr, ptr } { i32 65535, ptr @__cxx_global_var_init.13, ptr @_ZN13MixedSequence1yE },
+// CHECK-SAME: { i32, ptr, ptr } { i32 65535, ptr @__cxx_global_var_init.2,  ptr @_ZN13MixedSequence1bE },
+// CHECK-SAME: { i32, ptr, ptr } { i32 65535, ptr @__cxx_global_var_init.16, ptr @_ZN13MixedSequence1zE },
+// CHECK-SAME: { i32, ptr, ptr } { i32 65535, ptr @__cxx_global_var_init.15, ptr @_ZN13MixedSequence1wE },
+// CHECK-SAME: { i32, ptr, ptr } { i32 65535, ptr @__cxx_global_var_init.3,  ptr @_ZN13MixedSequence1cE },
+// CHECK-SAME: { i32, ptr, ptr } { i32 65535, ptr @__cxx_global_var_init.4,  ptr @_ZN13MixedSequence1dE },
+// CHECK-SAME: { i32, ptr, ptr } { i32 65535, ptr @__cxx_global_var_init.6,  ptr @_ZN19NonDeferredSequence1aE },
+// CHECK-SAME: { i32, ptr, ptr } { i32 65535, ptr @__cxx_global_var_init.7,  ptr @_ZN19NonDeferredSequence1bE },
+// CHECK-SAME: { i32, ptr, ptr } { i32 65535, ptr @__cxx_global_var_init.8,  ptr @_ZN19NonDeferredSequence1cE },
+// CHECK-SAME: { i32, ptr, ptr } { i32 65535, ptr @__cxx_global_var_init.9,  ptr @_ZN19NonDeferredSequence1dE },
+// CHECK-SAME: { i32, ptr, ptr } { i32 65535, ptr @_GLOBAL__sub_I_static_init_inline_variable.cpp, ptr null }