Improve what can be promoted in LICM.

[trentxintong]

Summary

In case of non-alloca pointers, we check for whether it is a pointer
from malloc-like calls and it is not captured. In such case, we can
promote the pointer, as the caller will have no way to access this pointer
even if there is unwinding in middle of the loop.

[efriedma]

lib/Transforms/Scalar/LICM.cpp

1017–1018

Is there an existing testcase which covers this?

1021

Can we avoid calling PointerMayBeCaptured twice? (We perform a similar check later in this function.)

test/Transforms/LICM/scalar-promote-unwind.ll

210

It would be more useful to have a testcase which doesn't leak memory.

[trentxintong]

Address comments.

1. Call PointerMayBeCaptured only once.
2. 2 test cases for malloced memory, first can escape and the other cant.

Make sure only the latter is promoted.

[trentxintong]

Cleanup LIT test file.

[trentxintong]

We do not check for MayBeCaptured for alloca when there is throw in the loop.

[efriedma]

lib/Transforms/Scalar/LICM.cpp

1026

Maybe reorganize this so you don't call isAllocLikeFn twice?

1136

I don't think you need to check isAllocLikeFn here.

[trentxintong]

Address comments.

[efriedma]

lib/Transforms/Scalar/LICM.cpp

1030

I was thinking of something more like if (!isa<AllocaInst>()) { if (!isAllocLikeFn()) return false; [...] }.

test/Transforms/LICM/scalar-promote-unwind.ll

248

This doesn't really test what you want it to... it would fail the aliasing test anyway.

Actually, hmm, it's hard to come up with a practical test where the PointerMayBeCaptured check is actually necessary: you need a call which could throw, but provably doesn't access a malloc whose address is captured... our current AA infrastructure can't prove something like that given the way C++ unwinding works. I guess you could construct an artificial IR testcase with a call that's readnone but not nothrow.

[trentxintong]

test/Transforms/LICM/scalar-promote-unwind.ll

248

yea, thats what i can think off right now. the problem is if the ptr escapes, then the function that actually throws will potentially be able to read/write it ...

[trentxintong]

Address comments.

[efriedma]

LGTM.

[trentxintong]

@efriedma Thanks for the review !

lib/Transforms/Scalar/LICM.cpp

bool llvm::promoteLoopAccessesToScalars(
 
   // We start with an alignment of one and try to find instructions that allow
   // us to prove better alignment.
   unsigned Alignment = 1;
   AAMDNodes AATags;
 
   const DataLayout &MDL = Preheader->getModule()->getDataLayout();
 
+  // This really is a cache for whether the pointer is captured or not. 
+  // PointerMayBeCaptured can be expensive, so its worth caching it.
+  Optional<bool> KnownCaptureStatus = None;
   if (SafetyInfo->MayThrow) {
     // If a loop can throw, we have to insert a store along each unwind edge.
     // That said, we can't actually make the unwind edge explicit. Therefore,
     // we have to prove that the store is dead along the unwind edge.
     //
-    // Currently, this code just special-cases alloca instructions.
-    if (!isa<AllocaInst>(GetUnderlyingObject(SomePtr, MDL)))
+    // If the underlying object is not an alloca, nor a pointer that does not
+    // escape, then we can not effectively prove that the store is dead along
+    // the unwind edge. i.e. the caller of this function could have ways to
+    // access the pointed object.
+    //
+    // NOTE: PointerMayBeCaptured is not enough as the pointer may have escaped
+    // even though its not captured by the enclosing function. Standard allocation
+    // functions like malloc, calloc, and operator new return values which can
+    // be assumed not to have previously escaped.
+    Value *Object = GetUnderlyingObject(SomePtr, MDL);
+    // If this is some base pointer we do not understand, simply bail.
+    if (!isa<AllocaInst>(Object) && !isAllocLikeFn(Object, TLI))
       return false;
+    // For base pointer not from alloca inst, there are extra constraints we
+    // have to verify. More specifically, we must make sure that the pointer
+    // can not be captured.
+    if (!isa<AllocaInst>(Object)) {
+      if (PointerMayBeCaptured(Object, true, true))
+        return false;
+      KnownCaptureStatus = false;
+    }
   }
 
   // Check that all of the pointers in the alias set have the same type.  We
   // cannot (yet) promote a memory location that is loaded and stored in
   // different sizes.  While we are at it, collect alignment and AA info.
   for (const auto &ASI : AS) {
     Value *ASIV = ASI.getValue();
     PointerMustAliases.insert(ASIV);
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) || isa<AllocaInst>(Object)) &&
-        !PointerMayBeCaptured(Object, true, true);
+        (isAllocLikeFn(Object, TLI) || isa<AllocaInst>(Object)) && 
+        (KnownCaptureStatus.hasValue() ? !*KnownCaptureStatus :
+        !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

test/Transforms/LICM/scalar-promote-unwind.ll

 ; RUN: opt < %s -basicaa -licm -S | FileCheck %s
 ; RUN: opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' -S %s | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Make sure we don't hoist the store out of the loop; %a would
 ; have the wrong value if f() unwinds
 
+
+; This is a local allocation by new and the returned pointer is
+; not captured, so in case of unwind, the caller will have no way
+; to access this memory.
+define void @local_allocation(i1 zeroext %y) uwtable {
+entry:
+  %n = call i8* @_Znwm(i64 4)
+  %a = bitcast i8* %n to i32*
+  br label %for.body
+
+; CHECK: for.body:
+; CHECK-NOT: load
+; CHECK-NOT: store
+; CHECK: br
+for.body:
+  %i.03 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %0 = load i32, i32* %a, align 4
+  %add = add nsw i32 %0, 1
+  store i32 %add, i32* %a, align 4
+  br i1 %y, label %if.then, label %for.inc
+
+if.then:
+  tail call void @f()
+  br label %for.inc
+
+for.inc:
+  %inc = add nuw nsw i32 %i.03, 1
+  %exitcond = icmp eq i32 %inc, 10000
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+
+; CHECK: for.cond.cleanup:
+; CHECK: store
+; CHECK: ret void
+for.cond.cleanup:
+  ret void
+}
+
 define void @test1(i32* nocapture noalias %a, i1 zeroext %y) uwtable {
 entry:
   br label %for.body
 
 for.body:
   %i.03 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
   %0 = load i32, i32* %a, align 4
   %add = add nsw i32 %0, 1
for.end:
   br label %try.cont
 
 eh.resume:
   %lpad.val = insertvalue { i8*, i32 } undef, i8* %2, 0
   %lpad.val3 = insertvalue { i8*, i32 } %lpad.val, i32 %3, 1
   resume { i8*, i32 } %lpad.val3
 }
 
-declare void @boo()
+
+; The malloc'ed memory is not capture and therefore promoted.
+define void @malloc_no_capture() #0 personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+entry:
+  %call = call i8* @malloc(i64 4)
+  %0 = bitcast i8* %call to i32*
+  br label %for.body
+
+; CHECK: for.body:
+; CHECK-NOT: load
+; CHECK-NOT: store
+; CHECK: br 
+for.body:
+  %i.0 = phi i32 [ 0, %entry  ], [ %inc, %for.latch ]
+  %1 = load i32, i32* %0, align 4
+  %add = add nsw i32 %1, 1
+  store i32 %add, i32* %0, align 4
+  br label %for.call
+
+for.call:
+  invoke void @boo()
+          to label %invoke.cont unwind label %lpad
+
+invoke.cont:
+  br label %for.latch
+
+for.latch:
+  %inc = add i32 %i.0, 1
+  %cmp = icmp slt i32 %i.0, 1024
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+  br label %fun.ret
+
+lpad:
+  %2 = landingpad { i8*, i32 }
+          catch i8* null
+  %3 = extractvalue { i8*, i32 } %2, 0
+  %4 = extractvalue { i8*, i32 } %2, 1
+  br label %catch
+
+catch:
+  %5 = call i8* @__cxa_begin_catch(i8* %3) #4
+  %6 = bitcast i32* %0 to i8*
+  call void @free(i8* %6)
+  call void @__cxa_end_catch()
+  br label %fun.ret
+
+fun.ret:
+  ret void
+}
+
+; The malloc'ed memory can be captured and therefore not promoted.
+define void @malloc_capture() #0 personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+entry:
+  %call = call i8* @malloc(i64 4)
+  %0 = bitcast i8* %call to i32*
+  br label %for.body
+
+; CHECK: for.body:
+; CHECK: load
+; CHECK: store
+; CHECK: br 
+for.body:
+  %i.0 = phi i32 [ 0, %entry  ], [ %inc, %for.latch ]
+  %1 = load i32, i32* %0, align 4
+  %add = add nsw i32 %1, 1
+  store i32 %add, i32* %0, align 4
+  br label %for.call
+
+for.call:
+  invoke void @boo_with_arg(i32* %0)
+          to label %invoke.cont unwind label %lpad
+
+invoke.cont:
+  br label %for.latch
+
+for.latch:
+  %inc = add i32 %i.0, 1
+  %cmp = icmp slt i32 %i.0, 1024
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+  br label %fun.ret
+
+lpad:
+  %2 = landingpad { i8*, i32 }
+          catch i8* null
+  %3 = extractvalue { i8*, i32 } %2, 0
+  %4 = extractvalue { i8*, i32 } %2, 1
+  br label %catch
+
+catch:
+  %5 = call i8* @__cxa_begin_catch(i8* %3) #4
+  %6 = bitcast i32* %0 to i8*
+  call void @free(i8* %6)
+  call void @__cxa_end_catch()
+  br label %fun.ret
+
+fun.ret:
+  ret void
+}
+
+
+; Function Attrs: nobuiltin
+declare noalias i8* @_Znwm(i64)
+
+; Function Attrs: nounwind
+declare noalias i8* @malloc(i64)
+
+; Function Attrs: nounwind
+declare void @free(i8* nocapture)
+
+declare void @boo() 
 
-declare i32 @__gxx_personality_v0(...)
+declare void @boo_with_arg(i32 *) 
 
-declare i32 @llvm.eh.typeid.for(i8*)
+declare i32 @__gxx_personality_v0(...)
 
 declare i8* @__cxa_begin_catch(i8*)
 
 declare void @__cxa_end_catch()
 
+declare i32 @llvm.eh.typeid.for(i8*)
+
 declare void @f() uwtable
+
+