[CodeGen] guarantee templated static variables are initialized in the reverse instantiation order

[ychen]

Summary

Based on Richard's suggestion in D126341:
`If we can actually describe a rule that we provide for initialization
order of instantiated variables, and we can easily implement that rule
and be confident we won't want to substantially weaken it later, and we
can thereby assure our users that we will satisfy that rule, then I
think that could be interesting, but anything less than that doesn't
seem worthwhile to me.`

I'm giving it try here. IMHO the implementation is pretty simple and
does not change behavior for unrelated constructs like the timing when
instantiated variables are passed to CodeGen.

This is based on the same ordering guarantee needed for inline variables D127233.
To provide this guarantee, we also need to
emit DeferredDeclsToEmit in the DFS order. https://github.com/llvm/llvm-project/commit/e5df59ff78faebd897e81907606ce6074aac0df6
originally supported this but it is not exactly DFS order for cases like
the one in cwg362. For the example of Fib<5>, it triggers the instantiation
of Fib<4> and Fib<3>. However, due to the way GlobalEagerInstantiationScope
is implemented, Fib<4> does not actually trigger Fib<3> instantiation
since it is already triggered by Fib<5>. This breaks the guarantee.

This patch makes sure DeferredDeclsToEmit is emitted in DFS order by moving
DeferredDeclsToEmit storage from the call stack to an explicit stack-like
data structure. Then the DFS order could be enforced.

[ychen]

gentle ping..

[rnk]

I think Richard had some concerns in the other review that this may not be enough to really guarantee initialization order within the TU. I couldn't say either way, I shouldn't review this code. Conceptually, this change seems small enough to me. Can we ask @aaron.ballman to take a look?

[ychen]

In D127259#3590127, @rnk wrote:

I think Richard had some concerns in the other review that this may not be enough to really guarantee initialization order within the TU. I couldn't say either way, I shouldn't review this code. Conceptually, this change seems small enough to me. Can we ask @aaron.ballman to take a look?

@rnk, thanks. @rsmith, please correct me if I'm wrong. I think the current approach is relying on two things: partial ordering in llvm.global_ctors entries (this is also needed to fix https://github.com/llvm/llvm-project/issues/55804, D127233, I could submit a follow-up patch to either make IR verifier check the order is not unexpected changed or simply check the order is maintained by GlobalOpt) and a linker that picks the *first* COMDAT consistently (this is not guaranteed but generally true for major linkers for a long time). The alternative is to coalesce llvm.global_ctors entries with order requirements into a single dynamic initialization function, however, as already being discussed, this has code size and startup time overhead. We could discuss the partial ordering in llvm.global_ctors entries in D127233.

[ychen]

I'll do a compile-time impact measurement.

[erichkeane]

I don't see much compile-time concerns myself, and this seems to fix a pretty serious regression, I think this is acceptable once Aaron and the author think so as well.

[ychen]

In D127259#4156314, @erichkeane wrote:

I don't see much compile-time concerns myself,

Indeed. http://llvm-compile-time-tracker.com/compare.php?from=54faf22f7b947464a070669711100211e87f3ea8&to=ad87d0dbd44f3a8f66c31fa9b731aea34c8fe64d&stat=instructions:u

[ychen]

• rebase

[shafik]

clang/lib/Sema/SemaExpr.cpp

19907

Doesn't this invalidate the iterators?

clang/include/clang/Sema/Sema.h

   /// The queue of implicit template instantiations that are required
   /// but have not yet been performed.
   std::deque<PendingImplicitInstantiation> PendingInstantiations;
 
   /// Queue of implicit template instantiations that cannot be performed
   /// eagerly.
   SmallVector<PendingImplicitInstantiation, 1> LateParsedInstantiations;
 
+  SmallVector<SmallVector<VTableUse, 16>, 8> SavedVTableUses;
+  SmallVector<std::deque<PendingImplicitInstantiation>, 8>
+      SavedPendingInstantiations;
+
   class GlobalEagerInstantiationScope {
   public:
     GlobalEagerInstantiationScope(Sema &S, bool Enabled)
         : S(S), Enabled(Enabled) {
       if (!Enabled) return;
 
-      SavedPendingInstantiations.swap(S.PendingInstantiations);
-      SavedVTableUses.swap(S.VTableUses);
+      S.SavedPendingInstantiations.emplace_back();
+      S.SavedPendingInstantiations.back().swap(S.PendingInstantiations);
+
+      S.SavedVTableUses.emplace_back();
+      S.SavedVTableUses.back().swap(S.VTableUses);
     }
 
     void perform() {
       if (Enabled) {
         S.DefineUsedVTables();
         S.PerformPendingInstantiations();
       }
     }
 
     ~GlobalEagerInstantiationScope() {
       if (!Enabled) return;
 
       // Restore the set of pending vtables.
       assert(S.VTableUses.empty() &&
              "VTableUses should be empty before it is discarded.");
-      S.VTableUses.swap(SavedVTableUses);
+      S.VTableUses.swap(S.SavedVTableUses.back());
+      S.SavedVTableUses.pop_back();
 
       // Restore the set of pending implicit instantiations.
       if (S.TUKind != TU_Prefix || !S.LangOpts.PCHInstantiateTemplates) {
         assert(S.PendingInstantiations.empty() &&
                "PendingInstantiations should be empty before it is discarded.");
-        S.PendingInstantiations.swap(SavedPendingInstantiations);
+        S.PendingInstantiations.swap(S.SavedPendingInstantiations.back());
+        S.SavedPendingInstantiations.pop_back();
       } else {
         // Template instantiations in the PCH may be delayed until the TU.
-        S.PendingInstantiations.swap(SavedPendingInstantiations);
-        S.PendingInstantiations.insert(S.PendingInstantiations.end(),
-                                       SavedPendingInstantiations.begin(),
-                                       SavedPendingInstantiations.end());
+        S.PendingInstantiations.swap(S.SavedPendingInstantiations.back());
+        S.PendingInstantiations.insert(
+            S.PendingInstantiations.end(),
+            S.SavedPendingInstantiations.back().begin(),
+            S.SavedPendingInstantiations.back().end());
+        S.SavedPendingInstantiations.pop_back();
       }
     }
 
   private:
     Sema &S;
-    SmallVector<VTableUse, 16> SavedVTableUses;
-    std::deque<PendingImplicitInstantiation> SavedPendingInstantiations;
     bool Enabled;
   };
 
   /// The queue of implicit template instantiations that are required
   /// and must be performed within the current local scope.
   ///
   /// This queue is only used for member functions of local classes in
   /// templates, which must be instantiated in the same scope as their

clang/lib/Sema/SemaExpr.cpp

if (TryInstantiating) {
                  isa<VarTemplateSpecializationDecl>(Var)) {
         // FIXME: For a specialization of a variable template, we don't
         // distinguish between "declaration and type implicitly instantiated"
         // and "implicit instantiation of definition requested", so we have
         // no direct way to avoid enqueueing the pending instantiation
         // multiple times.
         SemaRef.PendingInstantiations
             .push_back(std::make_pair(Var, PointOfInstantiation));
+      } else {
+        for (auto &I : SemaRef.SavedPendingInstantiations) {
+          auto Iter = llvm::find_if(
+              I, [Var](const Sema::PendingImplicitInstantiation &P) {
+                return P.first == Var;
+              });
+          if (Iter != I.end()) {
+            SemaRef.PendingInstantiations.push_back(*Iter);
+            I.erase(Iter);
+            break;
+          }
+        }
       }
     }
   }
 
   // C++2a [basic.def.odr]p4:
   //   A variable x whose name appears as a potentially-evaluated expression e
   //   is odr-used by e unless
   //   -- x is a reference that is usable in constant expressions

clang/test/CodeGenCXX/static-member-variable-explicit-specialization.cpp

 template<typename T> int A<T>::a = foo();
 
 // ALLK-NOT: @_ZN1AIcE1aE
 template<> int A<char>::a;
 
 // ALL: @_ZN1AIbE1aE ={{.*}} global i32 10
 template<> int A<bool>::a = 10;
 
-// ALL: @llvm.global_ctors = appending global [8 x { i32, ptr, ptr }]
+// ALL: @llvm.global_ctors = appending global [16 x { i32, ptr, ptr }]
 
-// ELF: [{ i32, ptr, ptr } { i32 65535, ptr @[[unordered1:[^,]*]], ptr @_ZN1AIsE1aE },
-// MACHO: [{ i32, ptr, ptr } { i32 65535, ptr @[[unordered1:[^,]*]], ptr null },
+// ELF:  [{ i32, ptr, ptr } { i32 65535, ptr @[[unordered:[^,]*]], ptr @_ZN1AIsE1aE },
+// MACHO: [{ i32, ptr, ptr } { i32 65535, ptr @[[unordered:[^,]*]], ptr null },
 
-// ELF:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered2:[^,]*]], ptr @_Z1xIsE },
-// MACHO:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered2:[^,]*]], ptr null },
+// ELF:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered7:[^,]*]], ptr @_Z1xIsE },
+// MACHO:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered7:[^,]*]], ptr null },
 
-// ELF:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered3:[^,]*]], ptr @_ZN2ns1aIiE1iE },
-// MACHO:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered3:[^,]*]], ptr null },
+// ELF:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered10:[^,]*]], ptr @_ZN2ns1aIiE1iE },
+// MACHO:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered10:[^,]*]], ptr null },
 
-// ELF:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered4:[^,]*]], ptr @_ZN2ns1b1iIiEE },
-// MACHO:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered4:[^,]*]], ptr null },
+// ELF:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered11:[^,]*]], ptr @_ZN2ns1b1iIiEE },
+// MACHO:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered11:[^,]*]], ptr null },
 
-// ELF:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered5:[^,]*]], ptr @_ZN1AIvE1aE },
-// MACHO:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered5:[^,]*]], ptr null },
+// ELF:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered14:[^,]*]], ptr @_ZN1AIvE1aE },
+// MACHO:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered14:[^,]*]], ptr null },
 
-// ELF:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered6:[^,]*]], ptr @_Z1xIcE },
-// MACHO:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered6:[^,]*]], ptr null },
+// ELF:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered15:[^,]*]], ptr @_Z1xIcE },
+// MACHO:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered15:[^,]*]], ptr null },
 
-// ALL:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered7:[^,]*]], ptr null },
+// ALL:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered16:[^,]*]], ptr null },
+
+// ELF:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered19:[^,]*]], ptr @_ZN3FibILi2EE1aE },
+// MACHO: { i32, ptr, ptr } { i32 65535, ptr @[[unordered19:[^,]*]], ptr null },
+
+// ELF:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered18:[^,]*]], ptr @_ZN3FibILi3EE1aE },
+// MACHO: { i32, ptr, ptr } { i32 65535, ptr @[[unordered18:[^,]*]], ptr null },
+
+// ELF:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered20:[^,]*]], ptr @_ZN3FibILi4EE1aE },
+// MACHO: { i32, ptr, ptr } { i32 65535, ptr @[[unordered20:[^,]*]], ptr null },
+
+// ELF:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered17:[^,]*]], ptr @_ZN3FibILi5EE1aE },
+// MACHO: { i32, ptr, ptr } { i32 65535, ptr @[[unordered17:[^,]*]], ptr null },
+
+// ELF:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered23:[^,]*]], ptr @_ZN4Fib2ILi2EE1aE },
+// MACHO: { i32, ptr, ptr } { i32 65535, ptr @[[unordered23:[^,]*]], ptr null },
+
+// ELF:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered24:[^,]*]], ptr @_ZN4Fib2ILi3EE1aE },
+// MACHO: { i32, ptr, ptr } { i32 65535, ptr @[[unordered24:[^,]*]], ptr null },
+
+// ELF:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered22:[^,]*]], ptr @_ZN4Fib2ILi4EE1aE },
+// MACHO: { i32, ptr, ptr } { i32 65535, ptr @[[unordered22:[^,]*]], ptr null },
+
+// ELF:  { i32, ptr, ptr } { i32 65535, ptr @[[unordered21:[^,]*]], ptr @_ZN4Fib2ILi5EE1aE },
+// MACHO: { i32, ptr, ptr } { i32 65535, ptr @[[unordered21:[^,]*]], ptr null }, 
 
 // ALL:  { i32, ptr, ptr } { i32 65535, ptr @_GLOBAL__sub_I_static_member_variable_explicit_specialization.cpp, ptr null }]
 
 /// llvm.used ensures SHT_INIT_ARRAY in a section group cannot be GCed.
-// ELF: @llvm.used = appending global [6 x ptr] [ptr @_ZN1AIsE1aE, ptr @_Z1xIsE, ptr @_ZN2ns1aIiE1iE, ptr @_ZN2ns1b1iIiEE, ptr @_ZN1AIvE1aE, ptr @_Z1xIcE]
+// ELF: @llvm.used = appending global [14 x ptr] [ptr @_ZN1AIsE1aE, ptr @_Z1xIsE, ptr @_ZN2ns1aIiE1iE, ptr @_ZN2ns1b1iIiEE, ptr @_ZN1AIvE1aE, ptr @_Z1xIcE, ptr @_ZN3FibILi5EE1aE, ptr @_ZN3FibILi3EE1aE, ptr @_ZN3FibILi2EE1aE, ptr @_ZN3FibILi4EE1aE, ptr @_ZN4Fib2ILi5EE1aE, ptr @_ZN4Fib2ILi4EE1aE, ptr @_ZN4Fib2ILi2EE1aE, ptr @_ZN4Fib2ILi3EE1aE]
 
 template int A<short>::a;  // Unordered
 int b = foo();
 int c = foo();
 int d = A<void>::a; // Unordered
 
 // An explicit specialization is ordered, and goes in __GLOBAL_sub_I_static_member_variable_explicit_specialization.cpp.
 template<> struct A<int> { static int a; };

 }
 
 namespace {
 template<typename T> struct Internal { static int a; };
 template<typename T> int Internal<T>::a = foo();
 }
 int *use_internal_a = &Internal<int>::a;
 
+template<int n> struct Fib { static int a; };
+template<> int Fib<0>::a = 0;
+template<> int Fib<1>::a = 1;
+template<int n> int Fib<n>::a = Fib<n-2>::a + Fib<n-1>::a;
+int f = Fib<5>::a;
+
+template<int n> struct Fib2 { static int a; };
+template<> int Fib2<0>::a = 0;
+template<> int Fib2<1>::a = 1;
+template<int n> int Fib2<n>::a = Fib2<n-1>::a + Fib2<n-2>::a;
+int f2 = Fib2<5>::a;
+
 #endif
 
-// ALL: define internal void @[[unordered1]](
+// ALL: define internal void @[[unordered]](
 // ALL: call i32 @foo()
 // ALL: store {{.*}} @_ZN1AIsE1aE
 // ALL: ret
 
-// ALL: define internal void @[[unordered2]](
+// ALL: define internal void @[[unordered7]](
 // ALL: call i32 @foo()
 // ALL: store {{.*}} @_Z1xIsE
 // ALL: ret
 
-// ALL: define internal void @[[unordered3]](
+// ALL: define internal void @[[unordered10]](
 // ALL: call i32 @foo()
 // ALL: store {{.*}} @_ZN2ns1aIiE1iE
 // ALL: ret
 
-// ALL: define internal void @[[unordered4]](
+// ALL: define internal void @[[unordered11]](
 // ALL: call i32 @foo()
 // ALL: store {{.*}} @_ZN2ns1b1iIiEE
 // ALL: ret
 
-// ALL: define internal void @[[unordered5]](
-// ALL: call i32 @foo()
-// ALL: store {{.*}} @_ZN1AIvE1aE
-// ALL: ret
-
-// ALL: define internal void @[[unordered6]](
+// ALL: define internal void @[[unordered15]](
 // ALL: call i32 @foo()
 // ALL: store {{.*}} @_Z1xIcE
 // ALL: ret
 
-// ALL: define internal void @[[unordered7]](
+// ALL: define internal void @[[unordered16]](
 // ALL: call i32 @foo()
 // ALL: store {{.*}} @_ZN12_GLOBAL__N_18InternalIiE1aE
 // ALL: ret
 
+// ALL: define internal void @[[unordered17]](
+// ALL: store {{.*}} @_ZN3FibILi5EE1aE
+// ALL: ret
+
+// ALL: define internal void @[[unordered18]](
+// ALL: store {{.*}} @_ZN3FibILi3EE1aE
+// ALL: ret
+
+// ALL: define internal void @[[unordered19]](
+// ALL: store {{.*}} @_ZN3FibILi2EE1aE
+// ALL: ret
+
+// ALL: define internal void @[[unordered20]](
+// ALL: store {{.*}} @_ZN3FibILi4EE1aE
+// ALL: ret
+
+// ALL: define internal void @[[unordered21]](
+// ALL: store {{.*}} @_ZN4Fib2ILi5EE1aE
+// ALL: ret
+
+// ALL: define internal void @[[unordered22]](
+// ALL: store {{.*}} @_ZN4Fib2ILi4EE1aE
+// ALL: ret
+
+// ALL: define internal void @[[unordered23]](
+// ALL: store {{.*}} @_ZN4Fib2ILi2EE1aE
+// ALL: ret
+
+// ALL: define internal void @[[unordered24]](
+// ALL: store {{.*}} @_ZN4Fib2ILi3EE1aE
+// ALL: ret
+
 // ALL: define internal void @_GLOBAL__sub_I_static_member_variable_explicit_specialization.cpp()
 //   We call unique stubs for every ordered dynamic initializer in the TU.
 // ALL: call
 // ALL: call
 // ALL: call
 // ALL: call
 // ALL: call
 // ALL: call
 // ALL: call
 // ALL: call
+// ALL: call
+// ALL: call
 // ALL-NOT: call
 // ALL: ret