Add !thread.private metadata

[reames]

Summary

As recently proposed and discussed on LLVM dev: https://groups.google.com/forum/#!topic/llvm-dev/oYcAtJnwALY

Feedback on naming and specification is particularly welcome.

Note: The LangRef change may not build. I'll fix any warnings before submission. I generally don't build docs because it increases build time noticeable and enabling it requires a clean build, so I'll do that once at the end.

[reames]

Just noting a couple of known gaps (to save reviewers time):

• No verifier support (will add before submission)
• Need to add references from each support instruction type in the docs (done to avoid rebase headache)

Follow on things which need to happen later:

• Once we settle on naming, extra and rename existing logic in LICM and DSE into a utility file in Analysis.
• Add a way to test that analysis in isolation. (print-thread-private or something)

docs/LangRef.rst

5430

FIXME: Change to thread.private.

[reames]

Abandoning an old review I'm not going to return to any time soon.

docs/LangRef.rst

.. code-block:: llvm
     ...
     br i1 %cmp, label %t1, label %t2, !irr_loop !0
 
     ...
     !0 = !{"loop_header_weight", i64 100}
 
 Irreducible loop header weights are typically based on profile data.
 
 '``invariant.group``' Metadata
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
+The ``thread.private`` metadata may be attached to any instruction which
+directly accesses memory (load, store, cmpxchg, atomicrmw).  The only legal
+value is an empty metadata or the index of such an empty metadata node.
+
+If an instruction tagged with the metadata is executed, the optimizer may
+assume the memory location referenced by the instruction is thread private
+at all points in the program where the memory location is known to be
+dereferenceable; otherwise, the behavior is undefined.
+
+A thread private memory location is one which can only be accessed by a
+single thread.  The behavior of a program which contains a concurrent
+read or write of a location marked as thread private is undefined.  Such
+a program is erroneous and is assumed not to exist.
+
+Note that the optimizer can infer that some locations are thread
+private (e.g. a non-escaping alloca or allocation).  Annotating uses
+of such locations is not required or recommended.
+
+Examples of transforms which are allowed only on thread private
+locations include:
+
+* Inserting a store to a location which is not otherwise known to have
+  been stored to.
+
+* Spilling an unrelated value into the memory location during a period
+  in which the contents are known to be dead.
+
+* Removing stores to locations whose contents are not read again by
+  the writing thread.
+  
+Note that thread local storage and thread private are distinct concepts.
+Thread local storage simply ensures each thread has a copy of the value,
+not that the copy is uniquely accessed by a single thread.  In some
+implementations, the address of a thread local location can be
+communicated to another thread which can then read or write from it.
+
+.. code-block:: llvm
+
+    %v = load i32, i32* @G, !thread.private !{}
+
+'``invariant.group``' Metadata
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
 The experimental ``invariant.group`` metadata may be attached to 
 ``load``/``store`` instructions referencing a single metadata with no entries.
 The existence of the ``invariant.group`` metadata on the instruction tells
 the optimizer that every ``load`` and ``store`` to the same pointer operand
 can be assumed to load or store the same
 value (but see the ``llvm.launder.invariant.group`` intrinsic which affects
 when two pointers are considered the same). Pointers returned by bitcast or
 getelementptr with only zero indices are considered the same.

include/llvm/IR/LLVMContext.h

enum : unsigned {
     MD_align = 17,                    // "align"
     MD_loop = 18,                     // "llvm.loop"
     MD_type = 19,                     // "type"
     MD_section_prefix = 20,           // "section_prefix"
     MD_absolute_symbol = 21,          // "absolute_symbol"
     MD_associated = 22,               // "associated"
     MD_callees = 23,                  // "callees"
     MD_irr_loop = 24,                 // "irr_loop"
+    MD_thread_private = 25,           // "thread.private"  
   };
 
   /// Known operand bundle tag IDs, which always have the same value.  All
   /// operand bundle tags that LLVM has special knowledge of are listed here.
   /// Additionally, this scheme allows LLVM to efficiently check for specific
   /// operand bundle tags without comparing strings.
   enum : unsigned {
     OB_deopt = 0,         // "deopt"

lib/IR/LLVMContext.cpp

std::pair<unsigned, StringRef> MDKinds[] = {
     {MD_align, "align"},
     {MD_loop, "llvm.loop"},
     {MD_type, "type"},
     {MD_section_prefix, "section_prefix"},
     {MD_absolute_symbol, "absolute_symbol"},
     {MD_associated, "associated"},
     {MD_callees, "callees"},
     {MD_irr_loop, "irr_loop"},
+    {MD_thread_private, "thread.private"},
   };
 
   for (auto &MDKind : MDKinds) {
     unsigned ID = getMDKindID(MDKind.second);
     assert(ID == MDKind.first && "metadata kind id drifted");
     (void)ID;
   }
 

lib/Transforms/Scalar/LICM.cpp

for (User *U : ASIV->users()) {
       // it.
       if (LoadInst *Load = dyn_cast<LoadInst>(UI)) {
         if (!Load->isUnordered())
           return false;
 
         SawUnorderedAtomic |= Load->isAtomic();
         SawNotAtomic |= !Load->isAtomic();
 
+        if (Load->getMetadata(LLVMContext::MD_thread_private))
+          IsKnownThreadLocalObject = true;
+
         if (!DereferenceableInPH)
           DereferenceableInPH = isSafeToExecuteUnconditionally(
               *Load, DT, CurLoop, SafetyInfo, ORE, Preheader->getTerminator());
       } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
         // Stores *of* the pointer are not interesting, only stores *to* the
         // pointer.
         if (UI->getOperand(1) != ASIV)
           continue;
         if (!Store->isUnordered())
           return false;
 
         SawUnorderedAtomic |= Store->isAtomic();
         SawNotAtomic |= !Store->isAtomic();
 
+        if (Store->getMetadata(LLVMContext::MD_thread_private))
+          IsKnownThreadLocalObject = true;
+
+
         // If the store is guaranteed to execute, both properties are satisfied.
         // We may want to check if a store is guaranteed to execute even if we
         // already know that promotion is safe, since it may have higher
         // alignment than any other guaranteed stores, in which case we can
         // raise the alignment on the promoted store.
         unsigned InstAlignment = Store->getAlignment();
         if (!InstAlignment)
           InstAlignment =

test/Transforms/LICM/promote-tls.ll

; CHECK: store i32 %new, i32* %addr, align 4
   br i1 %cmp, label %for.header, label %for.cond.for.end_crit_edge
 
 for.cond.for.end_crit_edge:                       ; preds = %for.body
 ; CHECK-LABEL: for.cond.for.end_crit_edge:
 ; CHECK-NOT: store
   %split = phi i32* [ %addr, %for.body ]
   ret i32* null
 }
+
+
+; Did the user tell us the location was thread private? (on the load)
+; CHECK-LABEL: @test3
+define i32* @test3(i32 %n, i32* dereferenceable(8) %addr, i1 %taken) {
+entry:
+  br label %for.header
+
+for.header:
+  %i.02 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  br i1 %taken, label %for.body, label %early-exit
+
+early-exit:
+; CHECK-LABEL: early-exit:
+; CHECK: store i32 %new1.lcssa, i32* %addr, align 1
+  ret i32* null
+
+for.body:
+  %old = load i32, i32* %addr, align 4, !thread.private !{}
+  %new = add i32 %old, 1
+  store i32 %new, i32* %addr, align 4
+  %inc = add nsw i32 %i.02, 1
+  %cmp = icmp slt i32 %inc, %n
+  br i1 %cmp, label %for.header, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %for.body
+; CHECK-LABEL: for.cond.for.end_crit_edge:
+; CHECK: store i32 %new.lcssa, i32* %addr, align 1
+  %split = phi i32* [ %addr, %for.body ]
+  ret i32* null
+}
+
+; Did the user tell us the location was thread private? (on the store)
+; CHECK-LABEL: @test4
+define i32* @test4(i32 %n, i32* dereferenceable(8) %addr, i1 %taken) {
+entry:
+  br label %for.header
+
+for.header:
+  %i.02 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  br i1 %taken, label %for.body, label %early-exit
+
+early-exit:
+; CHECK-LABEL: early-exit:
+; CHECK: store i32 %new1.lcssa, i32* %addr, align 1
+  ret i32* null
+
+for.body:
+  %old = load i32, i32* %addr, align 4, !thread.private !{}
+  %new = add i32 %old, 1
+  store i32 %new, i32* %addr, align 4
+  %inc = add nsw i32 %i.02, 1
+  %cmp = icmp slt i32 %inc, %n
+  br i1 %cmp, label %for.header, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %for.body
+; CHECK-LABEL: for.cond.for.end_crit_edge:
+; CHECK: store i32 %new.lcssa, i32* %addr, align 1
+  %split = phi i32* [ %addr, %for.body ]
+  ret i32* null
+}
+
+; Also thread.private, but maybe no derefenceable
+; CHECK-LABEL: @test_neg3
+define i32* @test_neg3(i32 %n, i32* %addr, i1 %taken) {
+entry:
+  br label %for.header
+
+for.header:
+  %i.02 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  br i1 %taken, label %for.body, label %early-exit
+
+early-exit:
+; CHECK-LABEL: early-exit:
+; CHECK-NOT: store i32 %new1.lcssa, i32* %addr, align 1
+  ret i32* null
+
+for.body:
+; CHECK-LABEL: for.body:
+; CHECK: store i32 %new, i32* %addr, align 4
+  %old = load i32, i32* %addr, align 4, !thread.private !{}
+  %new = add i32 %old, 1
+  store i32 %new, i32* %addr, align 4
+  %inc = add nsw i32 %i.02, 1
+  %cmp = icmp slt i32 %inc, %n
+  br i1 %cmp, label %for.header, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %for.body
+; CHECK-LABEL: for.cond.for.end_crit_edge:
+; CHECK-NOT: store i32 %new.lcssa, i32* %addr, align 1
+  %split = phi i32* [ %addr, %for.body ]
+  ret i32* null
+}