[LICM] Generalize unwinding check during scalar promotion

[nikic]

Summary

This generalizes the unwinding check during scalar promotion with the new semantics from D116998. I've extracted a common isNotVisibleOnUnwind() helper into AliasAnalysis, which handles allocas, byval arguments, sret arguments and noalias calls, as we have a few more places that need basically the same logic (DSE and MemCpyOpt at least). The noalias call case is a bit different from the others, because it also requires that the object is not captured.

[reames]

LGTM now if you remove the sret check (i.e invert the stack). LGTM once the sret patch lands otherwise.

llvm/lib/Transforms/Scalar/LICM.cpp

1931

I find compound conditions more confusing that an extra if check. I'd turn this into a series of early return if-clauses personally.

[nikic]

In D117000#3234529, @reames wrote:

LGTM now if you remove the sret check (i.e invert the stack). LGTM once the sret patch lands otherwise.

Ended up landing this without the sret check, which is split off into D118242.

llvm/include/llvm/Analysis/AliasAnalysis.h

 
 /// Return true if V is umabigously identified at the function-level.
 /// Different IdentifiedFunctionLocals can't alias.
 /// Further, an IdentifiedFunctionLocal can not alias with any function
 /// arguments other than itself, which is not necessarily true for
 /// IdentifiedObjects.
 bool isIdentifiedFunctionLocal(const Value *V);
 
+/// Return true if Object memory is not visible after an unwind, in the sense
+/// that program semantics cannot depend on Object containing any particular
+/// value on unwind. If the RequiresNoCaptureBeforeUnwind out parameter is set
+/// to true, then the memory is only not visible if the object has not been
+/// captured prior to the unwind. Otherwise it is not visible even if captured.
+bool isNotVisibleOnUnwind(const Value *Object,
+                          bool &RequiresNoCaptureBeforeUnwind);
+
 /// A manager for alias analyses.
 ///
 /// This class can have analyses registered with it and when run, it will run
 /// all of them and aggregate their results into single AA results interface
 /// that dispatches across all of the alias analysis results available.
 ///
 /// Note that the order in which analyses are registered is very significant.
 /// That is the order in which the results will be aggregated and queried.

llvm/lib/Analysis/AliasAnalysis.cpp

if (isNoAliasOrByValArgument(V))
     return true;
   return false;
 }
 
 bool llvm::isIdentifiedFunctionLocal(const Value *V) {
   return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasOrByValArgument(V);
 }
 
+bool llvm::isNotVisibleOnUnwind(const Value *Object,
+                                bool &RequiresNoCaptureBeforeUnwind) {
+  RequiresNoCaptureBeforeUnwind = false;
+
+  // Alloca goes out of scope on unwind.
+  if (isa<AllocaInst>(Object))
+    return true;
+
+  // Byval goes out of scope on unwind, sret is poisoned on unwind.
+  if (auto *A = dyn_cast<Argument>(Object))
+    return A->hasByValAttr() || A->hasStructRetAttr();
+
+  // A noalias return is not accessible from any other code. If the pointer
+  // does not escape prior to the unwind, then the caller cannot access the
+  // memory either.
+  if (isNoAliasCall(Object)) {
+    RequiresNoCaptureBeforeUnwind = true;
+    return true;
+  }
+
+  return false;
+}
+
 void llvm::getAAResultsAnalysisUsage(AnalysisUsage &AU) {
   // This function needs to be in sync with llvm::createLegacyPMAAResults -- if
   // more alias analyses are added to llvm::createLegacyPMAAResults, they need
   // to be added here also.
   AU.addRequired<TargetLibraryInfoWrapperPass>();
   AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
   AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
   AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
   AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
   AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
   AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
   AU.addUsedIfAvailable<ExternalAAWrapperPass>();
 }

llvm/lib/Transforms/Scalar/LICM.cpp

bool isNotCapturedBeforeOrInLoop(const Value *V, const Loop *L,
   // TODO: ReturnCaptures=true shouldn't be necessary here.
   return !PointerMayBeCapturedBefore(V, /* ReturnCaptures */ true,
                                      /* StoreCaptures */ true,
                                      L->getHeader()->getTerminator(), DT);
 }
 
 /// Return true if we can prove that a caller cannot inspect the object if an
 /// unwind occurs inside the loop.
-bool isNotVisibleOnUnwind(Value *Object, const Loop *L, DominatorTree *DT) {
-  if (isa<AllocaInst>(Object))
-    // Since the alloca goes out of scope, we know the caller can't retain a
-    // reference to it and be well defined.  Thus, we don't need to check for
-    // capture.
-    return true;
-
-  // For all other objects we need to know that the caller can't possibly
-  // have gotten a reference to the object prior to an unwind in the loop.
-  // There are two components of that:
-  //   1) Object can't have been captured prior to the definition site.
-  //      For this, we need to know the return value is noalias.
-  //   1) Object can't be captured before or inside the loop.  This is what
-  //      isNotCapturedBeforeOrInLoop() checks.
-  return isNoAliasCall(Object) && isNotCapturedBeforeOrInLoop(Object, L, DT);
+bool isNotVisibleOnUnwindInLoop(const Value *Object, const Loop *L,
+                                DominatorTree *DT) {
+  bool RequiresNoCaptureBeforeUnwind;
+  return isNotVisibleOnUnwind(Object, RequiresNoCaptureBeforeUnwind) &&
+         (!RequiresNoCaptureBeforeUnwind ||
+          isNotCapturedBeforeOrInLoop(Object, L, DT));
 }
 
 } // namespace
 
 /// Try to promote memory values to scalars by sinking stores out of the
 /// loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are
 /// loop invariant.
bool llvm::promoteLoopAccessesToScalars(
   bool IsKnownThreadLocalObject = false;
   if (SafetyInfo->anyBlockMayThrow()) {
     // 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.  We do
     // this by proving that the caller can't have a reference to the object
     // after return and thus can't possibly load from the object.
     Value *Object = getUnderlyingObject(SomePtr);
-    if (!isNotVisibleOnUnwind(Object, CurLoop, DT))
+    if (!isNotVisibleOnUnwindInLoop(Object, CurLoop, DT))
       return false;
     // Subtlety: Alloca's aren't visible to callers, but *are* potentially
     // visible to other threads if captured and used during their lifetimes.
     IsKnownThreadLocalObject = !isa<AllocaInst>(Object);
   }
 
   // Check that all accesses to pointers in the aliass set use the same type.
   // We cannot (yet) promote a memory location that is loaded and stored in

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

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
 
 for.cond.cleanup:
   ret void
 }
 
-; TODO: byval memory cannot be accessed on unwind either.
+; byval memory cannot be accessed on unwind either.
 define void @test_byval(i32* byval(i32) %a, i1 zeroext %y) uwtable {
 ; CHECK-LABEL: @test_byval(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A_PROMOTED:%.*]] = load i32, i32* [[A:%.*]], align 4
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
-; CHECK-NEXT:    [[I_03:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
-; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[A:%.*]], align 4
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[TMP0]], 1
-; CHECK-NEXT:    store i32 [[ADD]], i32* [[A]], align 4
+; CHECK-NEXT:    [[ADD1:%.*]] = phi i32 [ [[A_PROMOTED]], [[ENTRY:%.*]] ], [ [[ADD:%.*]], [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    [[I_03:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[FOR_INC]] ]
+; CHECK-NEXT:    [[ADD]] = add nsw i32 [[ADD1]], 1
 ; CHECK-NEXT:    br i1 [[Y:%.*]], label [[IF_THEN:%.*]], label [[FOR_INC]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    tail call void @f()
 ; CHECK-NEXT:    br label [[FOR_INC]]
 ; CHECK:       for.inc:
 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_03]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 10000
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[FOR_INC]] ]
+; CHECK-NEXT:    store i32 [[ADD_LCSSA]], i32* [[A]], align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.body
 
 for.body:
   %i.03 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
   %0 = load i32, i32* %a, align 4
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
 
 for.cond.cleanup:
   ret void
 }
 
-; TODO: sret memory cannot be accessed on unwind either.
+; sret memory cannot be accessed on unwind either.
 define void @test_sret(i32* noalias sret(i32) %a, i1 zeroext %y) uwtable {
 ; CHECK-LABEL: @test_sret(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A_PROMOTED:%.*]] = load i32, i32* [[A:%.*]], align 4
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
-; CHECK-NEXT:    [[I_03:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
-; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[A:%.*]], align 4
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[TMP0]], 1
-; CHECK-NEXT:    store i32 [[ADD]], i32* [[A]], align 4
+; CHECK-NEXT:    [[ADD1:%.*]] = phi i32 [ [[A_PROMOTED]], [[ENTRY:%.*]] ], [ [[ADD:%.*]], [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    [[I_03:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[FOR_INC]] ]
+; CHECK-NEXT:    [[ADD]] = add nsw i32 [[ADD1]], 1
 ; CHECK-NEXT:    br i1 [[Y:%.*]], label [[IF_THEN:%.*]], label [[FOR_INC]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    tail call void @f()
 ; CHECK-NEXT:    br label [[FOR_INC]]
 ; CHECK:       for.inc:
 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_03]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 10000
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[FOR_INC]] ]
+; CHECK-NEXT:    store i32 [[ADD_LCSSA]], i32* [[A]], align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.body
 
 for.body:
   %i.03 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
   %0 = load i32, i32* %a, align 4