This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by ychen on Jun 7 2022, 10:34 AM.

Details

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

Diff Detail

Event Timeline

ychen created this revision.Jun 7 2022, 10:34 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 7 2022, 10:34 AM
ychen requested review of this revision.Jun 7 2022, 10:34 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 7 2022, 10:34 AM
Herald added a subscriber: cfe-commits. · View Herald Transcript
ychen retitled this revision from [CodeGen] Sort llvm.global_ctors by lexing order before emission to [CodeGen] Sort llvm.global_ctors by lexical order before emission.Jun 9 2022, 11:31 AM

gentle ping..

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.

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 added inline comments.Aug 16 2022, 10:00 AM
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.

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.

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

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 added inline comments.Aug 16 2022, 11:21 AM
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 updated this revision to Diff 453094.Aug 16 2022, 12:18 PM
  • use correct lexing order for non-deferred constructors.
ychen updated this revision to Diff 453095.Aug 16 2022, 12:20 PM
  • rebase
efriedma added inline comments.Aug 16 2022, 1:01 PM
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 added inline comments.Aug 16 2022, 1:16 PM
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?

ychen retitled this revision from [CodeGen] Sort llvm.global_ctors by lexical order before emission to [CodeGen] Sort llvm.global_ctors by lexing order before emission.Aug 16 2022, 1:48 PM
efriedma added inline comments.Aug 16 2022, 1:57 PM
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 updated this revision to Diff 453373.Aug 17 2022, 11:31 AM
  • 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 added inline comments.Aug 17 2022, 12:25 PM
clang/lib/CodeGen/CGDeclCXX.cpp
592

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

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

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

ychen updated this revision to Diff 453403.Aug 17 2022, 1:02 PM
  • add more test cases
ychen marked an inline comment as done.Aug 17 2022, 1:04 PM
This revision is now accepted and ready to land.Aug 17 2022, 1:38 PM