[CodeGen] Emit dynamic initializers for static TLS vars in outlined scopes

[Prince781]

Summary

For static TLS vars only visible inside a function, clang will only generate an initializer inside the function body where the variable was declared. However, it is possible for the variable to be indirectly referenced without ever calling the function it was declared in, if a scope referring to the variable gets outlined into a function that is executed on a new thread. Here are two examples that demonstrate this:

#include <thread>
#include <iostream>

struct Object {
    int i;
    Object() : i(3) {}
};

int main(void) {
    static thread_local Object o;

    std::cout << "[main] o.i = " << o.i << std::endl;
    std::thread t([] { std::cout << "[new thread] o.i = " << o.i << std::endl; });
    t.join();
}

#include <iostream>
#include <omp.h>

struct Object {
    int i;
    Object() : i(3) {}
};

int main(void) {
    static Object o;
    #pragma omp threadprivate(o)

    #pragma omp parallel
    #pragma omp critical
    std::cout << "[" << omp_get_thread_num() << "] o.i = " << o.i << std::endl;
}

In this patch, we generate an initializer in a function for every unique reference to a static TLS var that was declared in a different function.

[efriedma]

This might be a silly question, but what happens if the initializer for a thread-local variable refers to another thread-local variable? Do you need to initialize both variables? In what order?

[Prince781]

In D66122#1626412, @efriedma wrote:

This might be a silly question, but what happens if the initializer for a thread-local variable refers to another thread-local variable? Do you need to initialize both variables? In what order?

If variable A's initializer references variable B, then it will call B's initializer. So when we call A's initializer, B's initialization completes before A's.

If B is a static thread-local variable declared outside of the body of A's initializer, then a guarded initializer will be inserted the body of A's initializer.

[efriedma]

If variable A's initializer references variable B, then it will call B's initializer.

I'm considering a testcase like this:

struct S { int x; };
void bar(S**);
void baz(void());
void f() { 
    thread_local S s = {1};
    thread_local S* p = &s;
    baz([]{bar(&p);});
}

The initializer for p normally just assumes s is initialized. I don't think this patch adds any code that would address that, although I could be missing something.

---

Thinking about it a bit more, I also have a general question: how is this supposed to work? What do other compilers do? Does the C++ standard say when the initializer is supposed to run? [stmt.dcl]p4 just says "Dynamic initialization [...] is performed the first time control passes through its declaration."

[Prince781]

In D66122#1627252, @efriedma wrote:

If variable A's initializer references variable B, then it will call B's initializer.

I don't think this patch adds any code that would address that, although I could be missing something.

No, you're absolutely right. I'll fix my patch later to address this oversight.

Thinking about it a bit more, I also have a general question: how is this supposed to work? What do other compilers do? Does the C++ standard say when the initializer is supposed to run? [stmt.dcl]p4 just says "Dynamic initialization [...] is performed the first time control passes through its declaration."

This I was not too sure about. gcc also does the same thing. I was not able to find anything addressing this situation directly. clang should either generate an error or do "the right thing." If the latter, then I take this from the standard to mean, "we can initialize at any time before the variable is referenced":

[ 3.7.2 Thread storage duration ] [basic.std.thread] A variable with thread storage duration shall be initialized before its first odr-use (3.2) and, if constructed, shall be destroyed on thread exit.

[Prince781]

I've updated the patch to initialize, in the proper order, all foreign static TLS variables and the variables they depend on for initialization. I've also cleaned up the patch a bit.

[mgrang]

clang/lib/CodeGen/CodeGenFunction.cpp

472

You can use the range-based version of llvm::sort here:

llvm::sort(OrderedVarInits);

[Prince781]

Use range-based version of llvm::sort

[efriedma]

in the proper order

I would prefer lexical order, if possible. (At least, the order should be deterministic.)

clang should either generate an error or do "the right thing."

Agreed.

I think we should send a defect report to the C++ standards committee to clarify the ambiguity here.

[Prince781]

I think this should order the initializers deterministically according to their var declaration order. Let me know if there's something I haven't considered.

[Prince781]

In D66122#1633990, @efriedma wrote:

I think we should send a defect report to the C++ standards committee to clarify the ambiguity here.

I followed the instructions on this page and sent it to std-discussion first.

[efriedma]

clang/lib/CodeGen/CodeGenFunction.cpp

479

Is the call to a_deps.find() here actually necessary? It shouldn't be possible for an initializer to directly refer to a variable declared later.

"<" on SourceLocations isn't source order, in general; you need isBeforeInTranslationUnit. (This should be documented somewhere, but I'm not finding the documentation, unfortunately. Any suggestions for where it should be documented?)

[Prince781]

clang/lib/CodeGen/CodeGenFunction.cpp

479

It shouldn't be possible for an initializer to directly refer to a variable declared later.

That's true. I was using deps.find() to order the initialization of the variables. But since you mention isBeforeInTranslationUnit, I can use that instead. It appears to be documented here.

[efriedma]

clang/lib/CodeGen/CodeGenFunction.cpp

479

The documentation question was more referring to the lack of documentation for operator< on SourceLocation.

[Prince781]

Use SourceManager to order inits.

[Prince781]

clang/lib/CodeGen/CodeGenFunction.cpp

479

I see. I misinterpreted what you said. Well, then, I think that operator<(SourceLocation &, SourceLocation &) should have Doxygen comments and maybe a note saying, "this probably isn't what you want; see SourceManager::isBeforeInTranslationUnit()"

[efriedma]

Added a few more minor comments.

It looks like the consensus on std-discussion is actually that your testcase has undefined behavior? That seems like an awful conclusion, and the standard text doesn't really seem to support it. (I mean, I guess you could argue that " variable with thread storage duration shall be initialized before its first odr-use" means if it's not initialized, the behavior is undefined, but that's really confusing.) But given that, I think we should submit a core issue, and hold off on merging this until we hear back from the committee.

clang/lib/CodeGen/CodeGenFunction.cpp

306

If you don't care about the iteration order, using pop_back on a vector is faster.

317

Do you need to recurse here? It looks like the caller should handle that.

469

Indentation.

[Prince781]

In D66122#1639947, @efriedma wrote:

But given that, I think we should submit a core issue, and hold off on merging this until we hear back from the committee.

I agree here. There does appear to be some previous discussion on this matter, but the spec itself still doesn't contain any language addressing this issue. I will submit a core issue.

clang/lib/CodeGen/CodeGenFunction.cpp

317

Oops, I think you might be right.

[Prince781]

The more I think about this, the more I have doubts about whether this should be supported. For example, what happens in cases like this?:

#include <thread>
#include <iostream>

struct Object {
    int i;
    Object() : i(3) {}
    Object(int v) : i(3 + v) {}
};

int main(void) {
    int w = 4;
    static thread_local Object o(w);

    std::cout << "[main] o.i = " << o.i << std::endl;
    std::thread([] {
        std::cout << "[new thread] o.i = " << o.i << std::endl;
    }).join();
}

Should w be captured or not? Furthermore, if o referenced another block-scope thread-local that had an initializer referencing another local variable, that would have to be captured too. So I now think this should be an error.

[efriedma]

Oh, I somehow forgot that was legal. :( That breaks this whole approach (well, maybe the lambda could capture "w", but that seems way too complicated). So we're left with a few possibilities:

1. an error
2. undefined behavior (probably we would want to warn in this case)
3. capturing the address of the thread_local variable

clang/lib/CodeGen/CGExpr.cpp

if (const auto *VD = dyn_cast<VarDecl>(ND)) {
 
     // Otherwise, it might be static local we haven't emitted yet for
     // some reason; most likely, because it's in an outer function.
     } else if (VD->isStaticLocal()) {
       addr = Address(CGM.getOrCreateStaticVarDecl(
           *VD, CGM.getLLVMLinkageVarDefinition(VD, /*IsConstant=*/false)),
                      getContext().getDeclAlign(VD));
 
+      // add to ForeignStaticVarDecls if this is a thread-local variable
+      // declared in a different function
+      const Decl *DC = cast<Decl>(VD->getDeclContext());
+      if (DC != CurGD.getDecl() && VD->getTLSKind() == VarDecl::TLS_Dynamic)
+        ForeignStaticTLSVars.insert(VD);
      // No other cases for now.
     } else {
       llvm_unreachable("DeclRefExpr for Decl not entered in LocalDeclMap?");
     }
 
 
     // Check for OpenMP threadprivate variables.
     if (getLangOpts().OpenMP && !getLangOpts().OpenMPSimd &&
         VD->hasAttr<OMPThreadPrivateDeclAttr>()) {

clang/lib/CodeGen/CodeGenFunction.h

public:
     SanitizerScope(CodeGenFunction *CGF);
     ~SanitizerScope();
   };
 
   /// In C++, whether we are code generating a thunk.  This controls whether we
   /// should emit cleanups.
   bool CurFuncIsThunk = false;
 
+  /// static thread-local variables we've referenced that were declared in a
+  /// parent function.
+  llvm::SmallSet<const VarDecl *, 32> ForeignStaticTLSVars;
+
   /// In ARC, whether we should autorelease the return value.
   bool AutoreleaseResult = false;
 
   /// Whether we processed a Microsoft-style asm block during CodeGen. These can
   /// potentially set the return value.
   bool SawAsmBlock = false;
 
   const NamedDecl *CurSEHParent = nullptr;

clang/lib/CodeGen/CodeGenFunction.cpp

 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/StmtCXX.h"
 #include "clang/AST/StmtObjC.h"
 #include "clang/Basic/Builtins.h"
 #include "clang/Basic/CodeGenOptions.h"
 #include "clang/Basic/TargetInfo.h"
 #include "clang/CodeGen/CGFunctionInfo.h"
 #include "clang/Frontend/FrontendDiagnostic.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/Transforms/Utils/PromoteMemToReg.h"
 using namespace clang;
 using namespace CodeGen;

 
 static void EmitIfUsed(CodeGenFunction &CGF, llvm::BasicBlock *BB) {
   if (!BB) return;
   if (!BB->use_empty())
     return CGF.CurFn->getBasicBlockList().push_back(BB);
   delete BB;
 }
 
+/// If a variable has an initializer, list all of the
+/// variables that it depends on.
+static llvm::SmallSet<const VarDecl *, 32> 
+enumerateVarInitDependencies(const VarDecl *VD) {
+  llvm::SmallSet<const VarDecl *, 32> deps;
+
+  if (const auto *InitExpr = VD->getInit()) {
+    std::deque<const Stmt *> frontier;
+
+    for (const auto *s : InitExpr->children())
+      frontier.emplace_back(s);
+
+    while (!frontier.empty()) {
+      auto x = frontier.front();
+      frontier.pop_front();
+      if (x->getStmtClass() == clang::Stmt::DeclRefExprClass) {
+        if (const auto *V = dyn_cast<VarDecl>(cast<DeclRefExpr>(x)->getDecl())) {
+          deps.insert(V);
+          auto V_Refs = enumerateVarInitDependencies(V);
+          deps.insert(V_Refs.begin(), V_Refs.end());
+        }
+      } else {
+        for (const auto *s : x->children())
+          frontier.emplace_back(s);
+      }
+    }
+  }
+
+  return deps;
+}
+
 void CodeGenFunction::FinishFunction(SourceLocation EndLoc) {
   assert(BreakContinueStack.empty() &&
          "mismatched push/pop in break/continue stack!");
 
   bool OnlySimpleReturnStmts = NumSimpleReturnExprs > 0
     && NumSimpleReturnExprs == NumReturnExprs
     && ReturnBlock.getBlock()->use_empty();
   // Usually the return expression is evaluated before the cleanup
if (!EscapedLocals.empty()) {
     EscapeArgs.resize(EscapedLocals.size());
     for (auto &Pair : EscapedLocals)
       EscapeArgs[Pair.second] = Pair.first;
     llvm::Function *FrameEscapeFn = llvm::Intrinsic::getDeclaration(
         &CGM.getModule(), llvm::Intrinsic::localescape);
     CGBuilderTy(*this, AllocaInsertPt).CreateCall(FrameEscapeFn, EscapeArgs);
   }
 
+  // Emit initializers for static local variables that we referenced that are
+  // declared in another function, which may be uninitialized on entry if this
+  // function may execute on a separate thread.  For example, when we're
+  // emitting the lambda in the following code:
+  // 
+  // class Object {
+  //   int init;
+  //   Object() : init(1) {}
+  // };
+  //
+  // main() {
+  //    static thread_local Object var;
+  //    std::thread([] {
+  //        ...emit initializer for var here...
+  //    });
+  // }
+  // 
+  // or another example:
+  //
+  // main() {
+  //    static Object var;
+  //    #pragma omp threadprivate(var)
+  //    #pragma omp parallel
+  //    {
+  //        ...emit initializer for var here...
+  //    }
+  // }
+  llvm::SmallSet<const VarDecl *, 32> UniqueVarsToInit;
+  llvm::SmallVector<const VarDecl *, 32> OrderedVarInits;
+  llvm::DenseMap<const VarDecl *, llvm::SmallSet<const VarDecl *, 4>> VarInitDependencies;
+
+  for (const VarDecl *VD : ForeignStaticTLSVars) {
+    llvm::SmallVector<const VarDecl *, 4> Frontier = {VD};
+
+    // don't initialize dependencies of CUDA __shared__ var with initializer?
+    bool isCudaSharedVar = getLangOpts().CUDA && getLangOpts().CUDAIsDevice &&
+      VD->hasAttr<CUDASharedAttr>();
+    while (!isCudaSharedVar && !Frontier.empty()) {
+      auto *Child = Frontier.pop_back_val();
+
+      if (UniqueVarsToInit.find(Child) == UniqueVarsToInit.end()) {
+        for (auto *N : enumerateVarInitDependencies(Child)) {
+          Frontier.push_back(N);
+          VarInitDependencies[Child].insert(N);
+        }
+        UniqueVarsToInit.insert(Child);
+      }
+    }
+  }
+
+  for (const VarDecl *VD : UniqueVarsToInit)
+      OrderedVarInits.push_back(VD);
+
+  llvm::sort(OrderedVarInits,
+      [&VarInitDependencies](const VarDecl *a, const VarDecl *b) {
+        auto a_deps = VarInitDependencies[a];
+        // A < B iff (B \in VarInitDependencies(A) OR B comes before A)
+        // the order is reversed because our codegen reverses the order of 
+        // initializers
+        return a_deps.find(b) != a_deps.end() 
+            || b->getLocation() < a->getLocation(); // ensure deterministic ordering
+      });
+
+  for (const VarDecl *VD : OrderedVarInits) {
+    // CUDA's local and local static __shared__ variables should not
+    // have any non-empty initializers. This is ensured by Sema.
+    // Whatever initializer such variable may have when it gets here is
+    // a no-op and should not be emitted.
+    bool isCudaSharedVar = getLangOpts().CUDA && getLangOpts().CUDAIsDevice &&
+      VD->hasAttr<CUDASharedAttr>();
+    // If this value has an initializer, and it's thread-local, emit it.
+    if (VD->getInit() && !isCudaSharedVar) {
+      auto *GV = dyn_cast<llvm::GlobalVariable>(CGM.getStaticLocalDeclAddress(VD));
+      auto IP = Builder.saveAndClearIP();
+      llvm::BasicBlock *BBParent = AllocaInsertPt->getParent();
+      llvm::Instruction *INext = AllocaInsertPt->getNextNonDebugInstruction();
+      llvm::BasicBlock *BBNext = BBParent->splitBasicBlock(INext, BBParent->getName() + ".next");
+
+      INext = AllocaInsertPt->getNextNonDebugInstruction();
+
+      Builder.SetInsertPoint(BBParent);
+      // the global variable shouldn't change, as this function should've
+      // been called first when generating the parent function
+      AddInitializerToStaticVarDecl(*VD, GV);
+      if (INext != BBParent->getTerminator()) {
+        INext->eraseFromParent();
+        Builder.CreateBr(BBNext);
+      }
+      Builder.restoreIP(IP);
+    }
+  }
+
   // Remove the AllocaInsertPt instruction, which is just a convenience for us.
   llvm::Instruction *Ptr = AllocaInsertPt;
   AllocaInsertPt = nullptr;
   Ptr->eraseFromParent();
 
   // If someone took the address of a label but never did an indirect goto, we
   // made a zero entry PHI node, which is illegal, zap it now.
   if (IndirectBranch) {

clang/test/CodeGenCXX/cxx11-thread-local.cpp

 };
 // CHECK: define {{.*}} @_ZN7PR192541fEv(
 int PR19254::f() {
   // LINUX: call void @_ZTHN7PR192541nE(
   // DARWIN: call cxx_fast_tlscc i32* @_ZTWN7PR192541nE(
   return this->n;
 }
 
+namespace static_tls_in_lambda {
+  struct X {
+    X() {}
+  };
+
+
+  X (*f())() {
+    static thread_local X x;
+
+    return [] { return x; };
+  }
+
+  auto y = f();
+
+  void g() { y(); }
+
+  void bar(X**, X**, X**);
+  void baz(void());
+  void f2() {
+      thread_local X x;
+      thread_local X* p = &x;
+      thread_local X* q = p;
+      thread_local X* r = q;
+      baz([]{bar(&p, &q, &r);});
+  }
+}
+
 namespace {
 thread_local int anon_i{1};
 }
 void set_anon_i() {
   anon_i = 2;
 }
 // LINUX-LABEL: define internal i32* @_ZTWN12_GLOBAL__N_16anon_iE()
 // DARWIN-LABEL: define internal cxx_fast_tlscc i32* @_ZTWN12_GLOBAL__N_16anon_iE()

 // CHECK: %[[X_M_INITIALIZED:.*]] = icmp eq i8 %{{.*}}, 0
 // CHECK: br i1 %[[X_M_INITIALIZED]],
 // need init:
 // LINUX: call {{.*}}__cxa_thread_atexit
 // DARWIN: call {{.*}}_tlv_atexit
 // CHECK: store i64 1, i64* @_ZGVN1XIiE1mE
 // CHECK: br label
 
+// CHECK: define internal void @"_ZZN20static_tls_in_lambda1fEvENK3$_1clEv"
+// CHECK: %[[static_tls_guard_val:.*]] = load i8, i8* @_ZGVZN20static_tls_in_lambda1fEvE1x
+// CHECK: %[[static_tls_guard_init:.*]] = icmp eq i8 %[[static_tls_guard_val]], 0
+// CHECK: br i1 %[[static_tls_guard_init]],
+// CHECK: call void @_ZN20static_tls_in_lambda1XC1Ev(%"struct.static_tls_in_lambda::X"* @_ZZN20static_tls_in_lambda1fEvE1x)
+// CHECK: store i8 1, i8* @_ZGVZN20static_tls_in_lambda1fEvE1x, align 1
+
+// CHECK: define internal void @"_ZZN20static_tls_in_lambda2f2EvENK3$_2clEv"
+// init x
+// CHECK: %[[static_tls_guard_val:.*]] = load i8, i8* @_ZGVZN20static_tls_in_lambda2f2EvE1x
+// CHECK: %[[static_tls_guard_init:.*]] = icmp eq i8 %[[static_tls_guard_val]], 0
+// CHECK: br i1 %[[static_tls_guard_init]],
+// CHECK: call void @_ZN20static_tls_in_lambda1XC1Ev(%"struct.static_tls_in_lambda::X"* @_ZZN20static_tls_in_lambda2f2EvE1x)
+// CHECK: store i8 1, i8* @_ZGVZN20static_tls_in_lambda2f2EvE1x, align 1
+// init p
+// CHECK: %[[static_tls_guard_val:.*]] = load i8, i8* @_ZGVZN20static_tls_in_lambda2f2EvE1p
+// CHECK: %[[static_tls_guard_init:.*]] = icmp eq i8 %[[static_tls_guard_val]], 0
+// CHECK: br i1 %[[static_tls_guard_init]],
+// CHECK: store %"struct.static_tls_in_lambda::X"* @_ZZN20static_tls_in_lambda2f2EvE1x, %"struct.static_tls_in_lambda::X"** @_ZZN20static_tls_in_lambda2f2EvE1p
+// CHECK: store i8 1, i8* @_ZGVZN20static_tls_in_lambda2f2EvE1p, align 1
+// init q
+// CHECK: %[[static_tls_guard_val:.*]] = load i8, i8* @_ZGVZN20static_tls_in_lambda2f2EvE1q
+// CHECK: %[[static_tls_guard_init:.*]] = icmp eq i8 %[[static_tls_guard_val]], 0
+// CHECK: br i1 %[[static_tls_guard_init]],
+// CHECK: %[[static_tls_var_prev:.*]] = load %"struct.static_tls_in_lambda::X"*, %"struct.static_tls_in_lambda::X"** @_ZZN20static_tls_in_lambda2f2EvE1p, align 8
+// CHECK: store %"struct.static_tls_in_lambda::X"* %[[static_tls_var_prev]], %"struct.static_tls_in_lambda::X"** @_ZZN20static_tls_in_lambda2f2EvE1q, align 8
+// CHECK: store i8 1, i8* @_ZGVZN20static_tls_in_lambda2f2EvE1q, align 1
+// init r
+// CHECK: %[[static_tls_guard_val:.*]] = load i8, i8* @_ZGVZN20static_tls_in_lambda2f2EvE1r
+// CHECK: %[[static_tls_guard_init:.*]] = icmp eq i8 %[[static_tls_guard_val]], 0
+// CHECK: br i1 %[[static_tls_guard_init]],
+// CHECK: %[[static_tls_var_prev:.*]] = load %"struct.static_tls_in_lambda::X"*, %"struct.static_tls_in_lambda::X"** @_ZZN20static_tls_in_lambda2f2EvE1q, align 8
+// CHECK: store %"struct.static_tls_in_lambda::X"* %[[static_tls_var_prev]], %"struct.static_tls_in_lambda::X"** @_ZZN20static_tls_in_lambda2f2EvE1r, align 8
+// CHECK: store i8 1, i8* @_ZGVZN20static_tls_in_lambda2f2EvE1r, align 1
+
+
 // CHECK: define {{.*}}@[[GLOBAL_INIT:.*]]()
 // CHECK: call void @[[C_INIT]]()
 // CHECK: call void @[[E_INIT]]()
 
 
 // CHECK: define {{.*}}@__tls_init()
 // CHECK: load i8, i8* @__tls_guard
 // CHECK: %[[NEED_TLS_INIT:.*]] = icmp eq i8 %{{.*}}, 0