[WebAssembly] Implement thread-local storage (local-exec model)

Summary:
Thread local variables are placed inside a `.tdata` segment. Their symbols are
offsets from the start of the segment. The address of a thread local variable
is computed as `__tls_base` + the offset from the start of the segment.

`.tdata` segment is a passive segment and `memory.init` is used once per thread
to initialize the thread local storage.

`__tls_base` is a wasm global. Since each thread has its own wasm instance,
it is effectively thread local. Currently, `__tls_base` must be initialized
at thread startup, and so cannot be used with dynamic libraries.

`__tls_base` is to be initialized with a new linker-synthesized function,
`__wasm_init_tls`, which takes as an argument a block of memory to use as the
storage for thread locals. It then initializes the block of memory and sets
`__tls_base`. As `__wasm_init_tls` will handle the memory initialization,
the memory does not have to be zeroed.

To help allocating memory for thread-local storage, a new compiler intrinsic
is introduced: `__builtin_wasm_tls_size()`. This instrinsic function returns
the size of the thread-local storage for the current function.

The expected usage is to run something like the following upon thread startup:

    __wasm_init_tls(malloc(__builtin_wasm_tls_size()));

Reviewers: tlively, aheejin, kripken, sbc100

Subscribers: dschuff, jgravelle-google, hiraditya, sunfish, jfb, cfe-commits, llvm-commits

Tags: #clang, #llvm

Differential Revision: https://reviews.llvm.org/D64537

git-svn-id: https://llvm.org/svn/llvm-project/lld/trunk@366272 91177308-0d34-0410-b5e6-96231b3b80d8

6 files changed, 221 insertions, 10 deletions

diff --git a/test/wasm/data-segments.ll b/test/wasm/data-segments.ll
index a9a403f3c..944895a0d 100644
--- a/test/wasm/data-segments.ll
+++ b/test/wasm/data-segments.ll
@@ -4,11 +4,11 @@
 
 ; atomics => active segments (TODO: error)
 ; RUN: wasm-ld -no-gc-sections --no-entry --shared-memory --max-memory=131072 %t.atomics.o -o %t.atomics.wasm
-; RUN: obj2yaml %t.atomics.wasm | FileCheck %s --check-prefix ACTIVE
+; RUN: obj2yaml %t.atomics.wasm | FileCheck %s --check-prefixes ACTIVE,ACTIVE-TLS
 
 ; atomics, active segments => active segments
 ; RUN: wasm-ld -no-gc-sections --no-entry --shared-memory --max-memory=131072 --active-segments %t.atomics.o -o %t.atomics.active.wasm
-; RUN: obj2yaml %t.atomics.active.wasm | FileCheck %s --check-prefix ACTIVE
+; RUN: obj2yaml %t.atomics.active.wasm | FileCheck %s --check-prefixes ACTIVE,ACTIVE-TLS
 
 ; atomics, passive segments => error
 ; RUN: not wasm-ld -no-gc-sections --no-entry --shared-memory --max-memory=131072 --passive-segments %t.atomics.o -o %t.atomics.passive.wasm 2>&1 | FileCheck %s --check-prefix ERROR
@@ -27,15 +27,15 @@
 
 ; atomics, bulk memory => active segments (TODO: passive)
 ; RUN: wasm-ld -no-gc-sections --no-entry --shared-memory --max-memory=131072 %t.atomics.bulk-mem.o -o %t.atomics.bulk-mem.wasm
-; RUN: obj2yaml %t.atomics.bulk-mem.wasm | FileCheck %s --check-prefix ACTIVE
+; RUN: obj2yaml %t.atomics.bulk-mem.wasm | FileCheck %s --check-prefixes ACTIVE,ACTIVE-TLS
 
 ; atomics, bulk memory, active segments   => active segments
 ; RUN: wasm-ld -no-gc-sections --no-entry --shared-memory --max-memory=131072 --active-segments %t.atomics.bulk-mem.o -o %t.atomics.bulk-mem.active.wasm
-; RUN: obj2yaml %t.atomics.bulk-mem.active.wasm | FileCheck %s --check-prefix ACTIVE
+; RUN: obj2yaml %t.atomics.bulk-mem.active.wasm | FileCheck %s --check-prefixes ACTIVE,ACTIVE-TLS
 
 ; atomics, bulk memory, passive segments  => passive segments
 ; RUN: wasm-ld -no-gc-sections --no-entry --shared-memory --max-memory=131072 --passive-segments %t.atomics.bulk-mem.o -o %t.atomics.bulk-mem.passive.wasm
-; RUN: obj2yaml %t.atomics.bulk-mem.passive.wasm | FileCheck %s --check-prefix PASSIVE
+; RUN: obj2yaml %t.atomics.bulk-mem.passive.wasm | FileCheck %s --check-prefixes PASSIVE,PASSIVE-TLS
 
 target triple = "wasm32-unknown-unknown"
 
@@ -54,6 +54,9 @@ target triple = "wasm32-unknown-unknown"
 ; ACTIVE-NEXT:      - Index:           0
 ; ACTIVE-NEXT:        Locals:          []
 ; ACTIVE-NEXT:        Body:            0B
+; ACTIVE-TLS-NEXT:  - Index:           1
+; ACTIVE-TLS-NEXT:    Locals:          []
+; ACTIVE-TLS-NEXT:    Body:            0B
 ; ACTIVE-NEXT:  - Type:            DATA
 ; ACTIVE-NEXT:    Segments:
 ; ACTIVE-NEXT:      - SectionOffset:   7
@@ -80,6 +83,8 @@ target triple = "wasm32-unknown-unknown"
 ; ACTIVE-NEXT:    FunctionNames:
 ; ACTIVE-NEXT:      - Index:           0
 ; ACTIVE-NEXT:        Name:            __wasm_call_ctors
+; ACTIVE-TLS-NEXT:  - Index:           1
+; ACTIVE-TLS-NEXT:    Name:            __wasm_init_tls
 
 ; PASSIVE-LABEL: - Type:            CODE
 ; PASSIVE-NEXT:    Functions:
@@ -89,6 +94,9 @@ target triple = "wasm32-unknown-unknown"
 ; PASSIVE-NEXT:      - Index:           1
 ; PASSIVE-NEXT:        Locals:          []
 ; PASSIVE-NEXT:        Body:            41800841004114FC080000FC090041940841004190CE00FC080100FC090141A4D6004100410DFC080200FC09020B
+; PASSIVE-TLS-NEXT:  - Index:           2
+; PASSIVE-TLS-NEXT:    Locals:          []
+; PASSIVE-TLS-NEXT:    Body:            0B
 ; PASSIVE-NEXT:  - Type:            DATA
 ; PASSIVE-NEXT:    Segments:
 ; PASSIVE-NEXT:      - SectionOffset:   3
@@ -108,3 +116,5 @@ target triple = "wasm32-unknown-unknown"
 ; PASSIVE-NEXT:        Name:            __wasm_call_ctors
 ; PASSIVE-NEXT:      - Index:           1
 ; PASSIVE-NEXT:        Name:            __wasm_init_memory
+; PASSIVE-TLS-NEXT:  - Index:           2
+; PASSIVE-TLS-NEXT:    Name:            __wasm_init_tls
diff --git a/test/wasm/tls.ll b/test/wasm/tls.ll
new file mode 100644
index 000000000..b570d4675
--- /dev/null
+++ b/test/wasm/tls.ll
@@ -0,0 +1,81 @@
+; RUN: llc -mattr=+bulk-memory -filetype=obj %s -o %t.o
+
+target triple = "wasm32-unknown-unknown"
+
+@tls1 = thread_local(localexec) global i32 1, align 4
+@no_tls = global i32 0, align 4
+@tls2 = thread_local(localexec) global i32 1, align 4
+
+define i32* @tls1_addr() {
+  ret i32* @tls1
+}
+
+define i32* @tls2_addr() {
+  ret i32* @tls2
+}
+
+; RUN: wasm-ld -no-gc-sections --shared-memory --max-memory=131072 --no-entry -o %t.wasm %t.o
+; RUN: obj2yaml %t.wasm | FileCheck %s
+
+; RUN: wasm-ld -no-gc-sections --shared-memory --max-memory=131072 --no-merge-data-segments --no-entry -o %t.wasm %t.o
+; RUN: obj2yaml %t.wasm | FileCheck %s
+
+; CHECK:      - Type:            GLOBAL
+; CHECK-NEXT:   Globals:
+; CHECK-NEXT:     - Index:           0
+; CHECK-NEXT:       Type:            I32
+; CHECK-NEXT:       Mutable:         true
+; CHECK-NEXT:       InitExpr:
+; CHECK-NEXT:         Opcode:          I32_CONST
+; CHECK-NEXT:         Value:           66576
+; CHECK-NEXT:     - Index:           1
+; CHECK-NEXT:       Type:            I32
+; CHECK-NEXT:       Mutable:         true
+; CHECK-NEXT:       InitExpr:
+; CHECK-NEXT:         Opcode:          I32_CONST
+; CHECK-NEXT:         Value:           0
+; CHECK-NEXT:     - Index:           2
+; CHECK-NEXT:       Type:            I32
+; CHECK-NEXT:       Mutable:         false
+; CHECK-NEXT:       InitExpr:
+; CHECK-NEXT:         Opcode:          I32_CONST
+; CHECK-NEXT:         Value:           8
+
+
+; CHECK:      - Type:            CODE
+; CHECK-NEXT:   Functions:
+; CHECK-NEXT:     - Index:           0
+; CHECK-NEXT:       Locals:          []
+; CHECK-NEXT:       Body:            0B
+; CHECK-NEXT:     - Index:           1
+; CHECK-NEXT:       Locals:          []
+; CHECK-NEXT:       Body:            20002401200041004108FC0800000B
+
+; Expected body of __wasm_init_tls:
+;   local.get 0
+;   global.set  1
+;   local.get 0
+;   i32.const 0
+;   i32.const 8
+;   memory.init 0, 0
+;   end
+
+; CHECK-NEXT:     - Index:           2
+; CHECK-NEXT:       Locals:          []
+; CHECK-NEXT:       Body:            2381808080004180808080006A0B
+
+; Expected body of tls1_addr:
+;   global.get 1
+;   i32.const 0
+;   i32.add
+;   end
+
+; CHECK-NEXT:     - Index:           3
+; CHECK-NEXT:       Locals:          []
+; CHECK-NEXT:       Body:            2381808080004184808080006A0B
+
+; Expected body of tls1_addr:
+;   global.get 1
+;   i32.const 4
+;   i32.add
+;   end
diff --git a/wasm/Driver.cpp b/wasm/Driver.cpp
index 3de69954e..900cd051d 100644
--- a/wasm/Driver.cpp
+++ b/wasm/Driver.cpp
@@ -454,6 +454,7 @@ createUndefinedGlobal(StringRef name, llvm::wasm::WasmGlobalType *type) {
 // Create ABI-defined synthetic symbols
 static void createSyntheticSymbols() {
   static WasmSignature nullSignature = {{}, {}};
+  static WasmSignature i32ArgSignature = {{}, {ValType::I32}};
   static llvm::wasm::WasmGlobalType globalTypeI32 = {WASM_TYPE_I32, false};
   static llvm::wasm::WasmGlobalType mutableGlobalTypeI32 = {WASM_TYPE_I32,
                                                             true};
@@ -516,6 +517,30 @@ static void createSyntheticSymbols() {
     WasmSym::heapBase = symtab->addOptionalDataSymbol("__heap_base");
   }
 
+  if (config->sharedMemory && !config->shared) {
+    llvm::wasm::WasmGlobal tlsBaseGlobal;
+    tlsBaseGlobal.Type = {WASM_TYPE_I32, true};
+    tlsBaseGlobal.InitExpr.Value.Int32 = 0;
+    tlsBaseGlobal.InitExpr.Opcode = WASM_OPCODE_I32_CONST;
+    tlsBaseGlobal.SymbolName = "__tls_base";
+    WasmSym::tlsBase =
+        symtab->addSyntheticGlobal("__tls_base", WASM_SYMBOL_VISIBILITY_HIDDEN,
+                                   make<InputGlobal>(tlsBaseGlobal, nullptr));
+
+    llvm::wasm::WasmGlobal tlsSizeGlobal;
+    tlsSizeGlobal.Type = {WASM_TYPE_I32, false};
+    tlsSizeGlobal.InitExpr.Value.Int32 = 0;
+    tlsSizeGlobal.InitExpr.Opcode = WASM_OPCODE_I32_CONST;
+    tlsSizeGlobal.SymbolName = "__tls_size";
+    WasmSym::tlsSize =
+        symtab->addSyntheticGlobal("__tls_size", WASM_SYMBOL_VISIBILITY_HIDDEN,
+                                   make<InputGlobal>(tlsSizeGlobal, nullptr));
+
+    WasmSym::initTLS = symtab->addSyntheticFunction(
+        "__wasm_init_tls", WASM_SYMBOL_VISIBILITY_HIDDEN,
+        make<SyntheticFunction>(i32ArgSignature, "__wasm_init_tls"));
+  }
+
   WasmSym::dsoHandle = symtab->addSyntheticDataSymbol(
       "__dso_handle", WASM_SYMBOL_VISIBILITY_HIDDEN);
 }
diff --git a/wasm/Symbols.cpp b/wasm/Symbols.cpp
index 61868f375..7d8d532c8 100644
--- a/wasm/Symbols.cpp
+++ b/wasm/Symbols.cpp
@@ -27,11 +27,14 @@ using namespace lld::wasm;
 DefinedFunction *WasmSym::callCtors;
 DefinedFunction *WasmSym::initMemory;
 DefinedFunction *WasmSym::applyRelocs;
+DefinedFunction *WasmSym::initTLS;
 DefinedData *WasmSym::dsoHandle;
 DefinedData *WasmSym::dataEnd;
 DefinedData *WasmSym::globalBase;
 DefinedData *WasmSym::heapBase;
 GlobalSymbol *WasmSym::stackPointer;
+GlobalSymbol *WasmSym::tlsBase;
+GlobalSymbol *WasmSym::tlsSize;
 UndefinedGlobal *WasmSym::tableBase;
 UndefinedGlobal *WasmSym::memoryBase;
 
@@ -200,8 +203,14 @@ DefinedFunction::DefinedFunction(StringRef name, uint32_t flags, InputFile *f,
 
 uint32_t DefinedData::getVirtualAddress() const {
   LLVM_DEBUG(dbgs() << "getVirtualAddress: " << getName() << "\n");
-  if (segment)
+  if (segment) {
+    // For thread local data, the symbol location is relative to the start of
+    // the .tdata section, since they are used as offsets from __tls_base.
+    // Hence, we do not add in segment->outputSeg->startVA.
+    if (segment->outputSeg->name == ".tdata")
+      return segment->outputSegmentOffset + offset;
     return segment->outputSeg->startVA + segment->outputSegmentOffset + offset;
+  }
   return offset;
 }
 
diff --git a/wasm/Symbols.h b/wasm/Symbols.h
index 499a265be..f4816aae7 100644
--- a/wasm/Symbols.h
+++ b/wasm/Symbols.h
@@ -426,6 +426,15 @@ struct WasmSym {
   // linear memory.
   static GlobalSymbol *stackPointer;
 
+  // __tls_base
+  // Global that holds the address of the base of the current thread's
+  // TLS block.
+  static GlobalSymbol *tlsBase;
+
+  // __tls_size
+  // Symbol whose value is the size of the TLS block.
+  static GlobalSymbol *tlsSize;
+
   // __data_end
   // Symbol marking the end of the data and bss.
   static DefinedData *dataEnd;
@@ -448,6 +457,10 @@ struct WasmSym {
   // Function that applies relocations to data segment post-instantiation.
   static DefinedFunction *applyRelocs;
 
+  // __wasm_init_tls
+  // Function that allocates thread-local storage and initializes it.
+  static DefinedFunction *initTLS;
+
   // __dso_handle
   // Symbol used in calls to __cxa_atexit to determine current DLL
   static DefinedData *dsoHandle;
diff --git a/wasm/Writer.cpp b/wasm/Writer.cpp
index 77a29a2d9..23a63edee 100644
--- a/wasm/Writer.cpp
+++ b/wasm/Writer.cpp
@@ -57,6 +57,7 @@ private:
   void createInitMemoryFunction();
   void createApplyRelocationsFunction();
   void createCallCtorsFunction();
+  void createInitTLSFunction();
 
   void assignIndexes();
   void populateSymtab();
@@ -242,6 +243,11 @@ void Writer::layoutMemory() {
     log(formatv("mem: {0,-15} offset={1,-8} size={2,-8} align={3}", seg->name,
                 memoryPtr, seg->size, seg->alignment));
     memoryPtr += seg->size;
+
+    if (WasmSym::tlsSize && seg->name == ".tdata") {
+      auto *tlsSize = cast<DefinedGlobal>(WasmSym::tlsSize);
+      tlsSize->global->global.InitExpr.Value.Int32 = seg->size;
+    }
   }
 
   // TODO: Add .bss space here.
@@ -353,6 +359,7 @@ void Writer::populateTargetFeatures() {
   StringMap<std::string> used;
   StringMap<std::string> required;
   StringMap<std::string> disallowed;
+  bool tlsUsed = false;
 
   // Only infer used features if user did not specify features
   bool inferFeatures = !config->features.hasValue();
@@ -385,6 +392,14 @@ void Writer::populateTargetFeatures() {
               std::to_string(feature.Prefix));
       }
     }
+
+    for (InputSegment *segment : file->segments) {
+      if (!segment->live)
+        continue;
+      StringRef name = segment->getName();
+      if (name.startswith(".tdata") || name.startswith(".tbss"))
+        tlsUsed = true;
+    }
   }
 
   if (inferFeatures)
@@ -411,6 +426,10 @@ void Writer::populateTargetFeatures() {
     error("'bulk-memory' feature must be used in order to emit passive "
           "segments");
 
+  if (!used.count("bulk-memory") && tlsUsed)
+    error("'bulk-memory' feature must be used in order to use thread-local "
+          "storage");
+
   // Validate that used features are allowed in output
   if (!inferFeatures) {
     for (auto &feature : used.keys()) {
@@ -492,8 +511,8 @@ void Writer::calculateExports() {
       // implement in all major browsers.
       // See: https://github.com/WebAssembly/mutable-global
       if (g->getGlobalType()->Mutable) {
-        // Only the __stack_pointer should ever be create as mutable.
-        assert(g == WasmSym::stackPointer);
+        // Only __stack_pointer and __tls_base should ever be create as mutable.
+        assert(g == WasmSym::stackPointer || g == WasmSym::tlsBase);
         continue;
       }
       export_ = {name, WASM_EXTERNAL_GLOBAL, g->getGlobalIndex()};
@@ -602,6 +621,11 @@ static StringRef getOutputDataSegmentName(StringRef name) {
   // we only have a single __memory_base to use as our base address.
   if (config->isPic)
     return ".data";
+  // We only support one thread-local segment, so we must merge the segments
+  // despite --no-merge-data-segments.
+  // We also need to merge .tbss into .tdata so they share the same offsets.
+  if (name.startswith(".tdata") || name.startswith(".tbss"))
+    return ".tdata";
   if (!config->mergeDataSegments)
     return name;
   if (name.startswith(".text."))
@@ -625,7 +649,7 @@ void Writer::createOutputSegments() {
       if (s == nullptr) {
         LLVM_DEBUG(dbgs() << "new segment: " << name << "\n");
         s = make<OutputSegment>(name, segments.size());
-        if (config->passiveSegments)
+        if (config->passiveSegments || name == ".tdata")
           s->initFlags = WASM_SEGMENT_IS_PASSIVE;
         segments.push_back(s);
       }
@@ -655,7 +679,7 @@ void Writer::createInitMemoryFunction() {
 
     // initialize passive data segments
     for (const OutputSegment *s : segments) {
-      if (s->initFlags & WASM_SEGMENT_IS_PASSIVE) {
+      if (s->initFlags & WASM_SEGMENT_IS_PASSIVE && s->name != ".tdata") {
         // destination address
         writeU8(os, WASM_OPCODE_I32_CONST, "i32.const");
         writeSleb128(os, s->startVA, "destination address");
@@ -737,6 +761,49 @@ void Writer::createCallCtorsFunction() {
   createFunction(WasmSym::callCtors, bodyContent);
 }
 
+void Writer::createInitTLSFunction() {
+  if (!WasmSym::initTLS->isLive())
+    return;
+
+  std::string bodyContent;
+  {
+    raw_string_ostream os(bodyContent);
+
+    OutputSegment *tlsSeg = nullptr;
+    for (auto *seg : segments) {
+      if (seg->name == ".tdata")
+        tlsSeg = seg;
+      break;
+    }
+
+    writeUleb128(os, 0, "num locals");
+    if (tlsSeg) {
+      writeU8(os, WASM_OPCODE_LOCAL_GET, "local.get");
+      writeUleb128(os, 0, "local index");
+
+      writeU8(os, WASM_OPCODE_GLOBAL_SET, "global.set");
+      writeUleb128(os, WasmSym::tlsBase->getGlobalIndex(), "global index");
+
+      writeU8(os, WASM_OPCODE_LOCAL_GET, "local.get");
+      writeUleb128(os, 0, "local index");
+
+      writeU8(os, WASM_OPCODE_I32_CONST, "i32.const");
+      writeSleb128(os, 0, "segment offset");
+
+      writeU8(os, WASM_OPCODE_I32_CONST, "i32.const");
+      writeSleb128(os, tlsSeg->size, "memory region size");
+
+      writeU8(os, WASM_OPCODE_MISC_PREFIX, "bulk-memory prefix");
+      writeUleb128(os, WASM_OPCODE_MEMORY_INIT, "MEMORY.INIT");
+      writeUleb128(os, tlsSeg->index, "segment index immediate");
+      writeU8(os, 0, "memory index immediate");
+    }
+    writeU8(os, WASM_OPCODE_END, "end function");
+  }
+
+  createFunction(WasmSym::initTLS, bodyContent);
+}
+
 // Populate InitFunctions vector with init functions from all input objects.
 // This is then used either when creating the output linking section or to
 // synthesize the "__wasm_call_ctors" function.
@@ -829,6 +896,12 @@ void Writer::run() {
     createCallCtorsFunction();
   }
 
+  if (config->sharedMemory && !config->shared)
+    createInitTLSFunction();
+
+  if (errorCount())
+    return;
+
   log("-- calculateTypes");
   calculateTypes();
   log("-- calculateExports");