[LICM] When promoting scalars, allow inserting stores to thread-local allocas

[mkuper]

Summary

This is similar to the allocfn case - if an alloca is not captured, then it's necessarily thread-local.

[reames]

LGTM, thanks!

[trentxintong]

llvm/trunk/test/Transforms/LICM/promote-tls.ll

67

Any particular reason why this can not be br i1 undef, label %a, label %b ? Understandably, this can be simplified by SimplifyCFG or SCCP. but we are only running LICM here ?

[trentxintong]

llvm/trunk/lib/Transforms/Scalar/LICM.cpp

1037

The question I really want to ask is whether the check for MayNotBeCaptured is necessary for Alloca. Should not alloca be implicitly thread local ? The language reference does not explicitly state it.

[efriedma]

llvm/trunk/lib/Transforms/Scalar/LICM.cpp

1037

In general, memory allocated using alloca can be used in all the same ways you could use memory allocated with malloc(). Not sure what sort of restriction you're expecting.

[sanjoy]

llvm/trunk/lib/Transforms/Scalar/LICM.cpp

1037

(Slight digression) There is one difference -- alloca memory is inherently frame local. This means you don't have to worry about the memory escaping via a ret. DSE handles a specific instance of this, where the stores are in the return block itself:

i8* @f() {
  %t = alloca i32
  store i32 42, i32* %t
  ret i32* %t
}

but e.g. slightly more complex cases like

define i32* @f(i1* %cond) {
  %t = alloca i32
  store i32 42, i32* %t
  %c = load volatile i1, i1* %cond
  br i1 %c, label %a, label %b

a:
  %c2 = load volatile i1, i1* %cond
  ret i32* %t

b:
  ret i32* null
}

are not handled by -O3.

llvm/trunk/lib/Transforms/Scalar/LICM.cpp

bool llvm::promoteLoopAccessesToScalars(
 
   // We know we can hoist the load, but don't have a guaranteed store.
   // Check whether the location is thread-local. If it is, then we can insert
   // stores along paths which originally didn't have them without violating the
   // memory model.
   if (!SafeToInsertStore) {
     Value *Object = GetUnderlyingObject(SomePtr, MDL);
     SafeToInsertStore =
-        isAllocLikeFn(Object, TLI) && !PointerMayBeCaptured(Object, true, true);
+        (isAllocLikeFn(Object, TLI) || isa<AllocaInst>(Object)) &&
+        !PointerMayBeCaptured(Object, true, true);
   }
 
   // If we've still failed to prove we can sink the store, give up.
   if (!SafeToInsertStore)
     return false;
 
   // Otherwise, this is safe to promote, lets do it!
   DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " << *SomePtr

llvm/trunk/test/Transforms/LICM/promote-tls.ll

 ; RUN: opt -tbaa -basicaa -licm -S < %s | FileCheck %s
 ; RUN: opt -aa-pipeline=type-based-aa,basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,loop(licm)' -S %s | FileCheck %s
 
 ; If we can prove a local is thread local, we can insert stores during
 ; promotion which wouldn't be legal otherwise.
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-linux-generic"
 
 @p = external global i8*
 
 declare i8* @malloc(i64)
 
 ; Exercise the TLS case
+; CHECK-LABEL: @test
 define i32* @test(i32 %n) {
 entry:
   ;; ignore the required null check for simplicity
   %mem = call dereferenceable(16) noalias i8* @malloc(i64 16)
   %addr = bitcast i8* %mem to i32*
   br label %for.body.lr.ph
 
 for.body.lr.ph:                                   ; preds = %entry

 
 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
 }
 
+; Stack allocations can also be thread-local
+; CHECK-LABEL: @test2
+define i32* @test2(i32 %n) {
+entry:
+  %mem = alloca i8, i32 16
+  %addr = bitcast i8* %mem to i32*
+  br label %for.body.lr.ph
+
+for.body.lr.ph:                                   ; preds = %entry
+  br label %for.header
+
+for.header:
+  %i.02 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]
+  %old = load i32, i32* %addr, align 4
+  ; deliberate impossible to analyze branch
+  %guard = load atomic i8*, i8** @p monotonic, align 8
+  %exitcmp = icmp eq i8* %guard, null
+  br i1 %exitcmp, 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:
+  %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
+}
+
 declare i8* @not_malloc(i64)
 
 ; Negative test - not TLS
+; CHECK-LABEL: @test_neg
 define i32* @test_neg(i32 %n) {
 entry:
   ;; ignore the required null check for simplicity
   %mem = call dereferenceable(16) noalias i8* @not_malloc(i64 16)
   %addr = bitcast i8* %mem to i32*
   br label %for.body.lr.ph
 
 for.body.lr.ph:                                   ; preds = %entry

 ; CHECK-LABEL: for.cond.for.end_crit_edge:
 ; CHECK-NOT: store
   %split = phi i32* [ %addr, %for.body ]
   ret i32* null
 }
 
 ; Negative test - can't speculate load since branch
 ; may control alignment
+; CHECK-LABEL: @test_neg2
 define i32* @test_neg2(i32 %n) {
 entry:
   ;; ignore the required null check for simplicity
   %mem = call dereferenceable(16) noalias i8* @malloc(i64 16)
   %addr = bitcast i8* %mem to i32*
   br label %for.body.lr.ph
 
 for.body.lr.ph:                                   ; preds = %entry
; 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
 }
-