[LICM] Allow load-only scalar promotion in the presence of unwinding

[nikic]

Summary

Currently, we bail out of scalar promotion if the loop may unwind and the memory may be visible on unwind. This is because we can't insert stores of the promoted value on unwind edges.

However, nowadays scalar promotion also has support for only promoting loads, while leaving stores in place. This kind of promotion is safe even in the presence of unwinding.

(The next and more interesting step is that we can also allow potentially aliasing reads of the pointer when doing load-only promotion.)

[djtodoro]

Very interesting. This looks good to me. Thanks.

[djtodoro]

llvm/lib/Transforms/Scalar/LICM.cpp

1962

enum class?

[reames]

LGTM w/minor comment.

llvm/lib/Transforms/Scalar/LICM.cpp

1962

Can you add a quick comment which emphasizes this is a lattice and not an optional bool? That is, once it falls from unknown to known, it's not every legal to transition from unsafe to safe?

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

471

Update comment

llvm/lib/Transforms/Scalar/LICM.cpp

bool llvm::promoteLoopAccessesToScalars(
   // b) Prove a store dominates every exit block. In this case, if an exit
   // blocks is reached, the original dynamic path would have taken us through
   // the store, so inserting a store into the exit block is safe. Note that this
   // is different from the store being guaranteed to execute. For instance,
   // if an exception is thrown on the first iteration of the loop, the original
   // store is never executed, but the exit blocks are not executed either.
 
   bool DereferenceableInPH = false;
-  bool SafeToInsertStore = false;
   bool StoreIsGuanteedToExecute = false;
   bool FoundLoadToPromote = false;
+  // Goes from Unknown to either Safe or Unsafe, but can't switch between them.
+  enum {
+    StoreSafe,
+    StoreUnsafe,
+    StoreSafetyUnknown,
+  } StoreSafety = StoreSafetyUnknown;
 
   SmallVector<Instruction *, 64> LoopUses;
 
   // We start with an alignment of one and try to find instructions that allow
   // us to prove better alignment.
   Align Alignment;
   // Keep track of which types of access we see
   bool SawUnorderedAtomic = false;
   bool SawNotAtomic = false;
   AAMDNodes AATags;
 
   const DataLayout &MDL = Preheader->getModule()->getDataLayout();
 
   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 (!isNotVisibleOnUnwindInLoop(Object, CurLoop, DT))
-      return false;
+      StoreSafety = StoreUnsafe;
   }
 
   // Check that all accesses to pointers in the alias set use 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.
   Type *AccessTy = nullptr;
   for (Value *ASIV : PointerMustAliases) {
     for (Use &U : ASIV->uses()) {
for (Use &U : ASIV->uses()) {
         // alignment than any other guaranteed stores, in which case we can
         // raise the alignment on the promoted store.
         Align InstAlignment = Store->getAlign();
         bool GuaranteedToExecute =
             SafetyInfo->isGuaranteedToExecute(*UI, DT, CurLoop);
         StoreIsGuanteedToExecute |= GuaranteedToExecute;
         if (GuaranteedToExecute) {
           DereferenceableInPH = true;
-          SafeToInsertStore = true;
+          if (StoreSafety == StoreSafetyUnknown)
+            StoreSafety = StoreSafe;
           Alignment = std::max(Alignment, InstAlignment);
         }
 
         // If a store dominates all exit blocks, it is safe to sink.
         // As explained above, if an exit block was executed, a dominating
         // store must have been executed at least once, so we are not
         // introducing stores on paths that did not have them.
         // Note that this only looks at explicit exit blocks. If we ever
         // start sinking stores into unwind edges (see above), this will break.
-        if (!SafeToInsertStore)
-          SafeToInsertStore = llvm::all_of(ExitBlocks, [&](BasicBlock *Exit) {
+        if (StoreSafety == StoreSafetyUnknown &&
+            llvm::all_of(ExitBlocks, [&](BasicBlock *Exit) {
               return DT->dominates(Store->getParent(), Exit);
-          });
+            }))
+          StoreSafety = StoreSafe;
 
         // If the store is not guaranteed to execute, we may still get
         // deref info through it.
         if (!DereferenceableInPH) {
           DereferenceableInPH = isDereferenceableAndAlignedPointer(
               Store->getPointerOperand(), Store->getValueOperand()->getType(),
               Store->getAlign(), MDL, Preheader->getTerminator(), DT, TLI);
         }
if (!DereferenceableInPH) {
     LLVM_DEBUG(dbgs() << "Not promoting: Not dereferenceable in preheader\n");
     return false;
   }
 
   // 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) {
+  if (StoreSafety == StoreSafetyUnknown) {
     Value *Object = getUnderlyingObject(SomePtr);
-    SafeToInsertStore =
-        (isNoAliasCall(Object) || isa<AllocaInst>(Object) ||
+    if ((isNoAliasCall(Object) || isa<AllocaInst>(Object) ||
          (isa<Argument>(Object) && cast<Argument>(Object)->hasByValAttr())) &&
-        isNotCapturedBeforeOrInLoop(Object, CurLoop, DT);
+        isNotCapturedBeforeOrInLoop(Object, CurLoop, DT))
+      StoreSafety = StoreSafe;
   }
 
   // If we've still failed to prove we can sink the store, hoist the load
   // only, if possible.
-  if (!SafeToInsertStore && !FoundLoadToPromote)
+  if (StoreSafety != StoreSafe && !FoundLoadToPromote)
     // If we cannot hoist the load either, give up.
     return false;
 
   // Lets do the promotion!
-  if (SafeToInsertStore)
+  if (StoreSafety == StoreSafe)
     LLVM_DEBUG(dbgs() << "LICM: Promoting load/store of the value: " << *SomePtr
                       << '\n');
   else
     LLVM_DEBUG(dbgs() << "LICM: Promoting load of the value: " << *SomePtr
                       << '\n');
 
   ORE->emit([&]() {
     return OptimizationRemark(DEBUG_TYPE, "PromoteLoopAccessesToScalar",
bool llvm::promoteLoopAccessesToScalars(
   auto DL = DebugLoc(DILocation::getMergedLocations(LoopUsesLocs));
 
   // We use the SSAUpdater interface to insert phi nodes as required.
   SmallVector<PHINode *, 16> NewPHIs;
   SSAUpdater SSA(&NewPHIs);
   LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks,
                         InsertPts, MSSAInsertPts, PIC, MSSAU, *LI, DL,
                         Alignment, SawUnorderedAtomic, AATags, *SafetyInfo,
-                        SafeToInsertStore);
+                        StoreSafety == StoreSafe);
 
   // Set up the preheader to have a definition of the value.  It is the live-out
   // value from the preheader that uses in the loop will use.
   LoadInst *PreheaderLoad = nullptr;
   if (FoundLoadToPromote || !StoreIsGuanteedToExecute) {
     PreheaderLoad =
         new LoadInst(AccessTy, SomePtr, SomePtr->getName() + ".promoted",
                      Preheader->getTerminator());

llvm/test/Transforms/LICM/guards.ll

loop:
   %p2 = getelementptr i32, i32* %ptr, i32 1
   store i32 0, i32* %p2
   call void (i1, ...) @llvm.experimental.guard(i1 %cond) ["deopt" (i32 0)]
   %val = load i32, i32* %ptr
   %x.inc = add i32 %x, %val
   br label %loop
 }
 
-; Hoist guard. Cannot hoist load because of aliasing.
+; Hoist guard. Cannot hoist load because of aliasing, but can promote.
 define void @test3(i1 %cond, i32* %ptr) {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[COND:%.*]]) [ "deopt"(i32 0) ]
+; CHECK-NEXT:    [[PTR_PROMOTED:%.*]] = load i32, i32* [[PTR:%.*]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[X:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[X_INC:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[VAL:%.*]] = load i32, i32* [[PTR:%.*]], align 4
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ [[PTR_PROMOTED]], [[ENTRY:%.*]] ], [ 0, [[LOOP]] ]
+; CHECK-NEXT:    [[X:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[X_INC:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    store i32 0, i32* [[PTR]], align 4
-; CHECK-NEXT:    [[X_INC]] = add i32 [[X]], [[VAL]]
+; CHECK-NEXT:    [[X_INC]] = add i32 [[X]], [[TMP0]]
 ; CHECK-NEXT:    br label [[LOOP]]
 ;
 
 entry:
   br label %loop
 
 loop:
   %x = phi i32 [ 0, %entry ], [ %x.inc, %loop ]

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -basic-aa -licm -S | FileCheck %s
 ; RUN: opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop-mssa(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
 define void @test1(i32* nocapture noalias %a, i1 zeroext %y) uwtable {
 ; CHECK-LABEL: @test1(
 ; 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:    [[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:    store i32 [[ADD]], i32* [[A]], align 4
 ; 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

 for.cond.cleanup:
   ret void
 }
 
 ; TODO: sret could be specified to not 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:    [[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:    store i32 [[ADD]], i32* [[A]], align 4
 ; 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
catch:
   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.
+; The malloc'ed memory can be captured and therefore only loads can be promoted.
 define void @malloc_capture(i32** noalias %A) personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
 ; CHECK-LABEL: @malloc_capture(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CALL:%.*]] = call i8* @malloc(i64 4)
 ; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i8* [[CALL]] to i32*
+; CHECK-NEXT:    [[DOTPROMOTED:%.*]] = load i32, i32* [[TMP0]], align 4
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
-; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_LATCH:%.*]] ]
-; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[TMP0]], align 4
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[TMP1]], 1
+; CHECK-NEXT:    [[ADD1:%.*]] = phi i32 [ [[DOTPROMOTED]], [[ENTRY:%.*]] ], [ [[ADD:%.*]], [[FOR_LATCH:%.*]] ]
+; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[FOR_LATCH]] ]
+; CHECK-NEXT:    [[ADD]] = add nsw i32 [[ADD1]], 1
 ; CHECK-NEXT:    store i32 [[ADD]], i32* [[TMP0]], align 4
 ; CHECK-NEXT:    br label [[FOR_CALL:%.*]]
 ; CHECK:       for.call:
 ; CHECK-NEXT:    invoke void @boo_readnone()
 ; CHECK-NEXT:    to label [[INVOKE_CONT:%.*]] unwind label [[LPAD:%.*]]
 ; CHECK:       invoke.cont:
 ; CHECK-NEXT:    br label [[FOR_LATCH]]
 ; CHECK:       for.latch:
 ; CHECK-NEXT:    store i32* [[TMP0]], i32** [[A:%.*]], align 8
 ; CHECK-NEXT:    [[INC]] = add i32 [[I_0]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_0]], 1024
 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    br label [[FUN_RET:%.*]]
 ; CHECK:       lpad:
-; CHECK-NEXT:    [[TMP2:%.*]] = landingpad { i8*, i32 }
+; CHECK-NEXT:    [[TMP1:%.*]] = landingpad { i8*, i32 }
 ; CHECK-NEXT:    catch i8* null
-; CHECK-NEXT:    [[TMP3:%.*]] = extractvalue { i8*, i32 } [[TMP2]], 0
-; CHECK-NEXT:    [[TMP4:%.*]] = extractvalue { i8*, i32 } [[TMP2]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = extractvalue { i8*, i32 } [[TMP1]], 0
+; CHECK-NEXT:    [[TMP3:%.*]] = extractvalue { i8*, i32 } [[TMP1]], 1
 ; CHECK-NEXT:    br label [[CATCH:%.*]]
 ; CHECK:       catch:
-; CHECK-NEXT:    [[TMP5:%.*]] = call i8* @__cxa_begin_catch(i8* [[TMP3]])
-; CHECK-NEXT:    [[TMP6:%.*]] = bitcast i32* [[TMP0]] to i8*
-; CHECK-NEXT:    call void @free(i8* [[TMP6]])
+; CHECK-NEXT:    [[TMP4:%.*]] = call i8* @__cxa_begin_catch(i8* [[TMP2]])
+; CHECK-NEXT:    [[TMP5:%.*]] = bitcast i32* [[TMP0]] to i8*
+; CHECK-NEXT:    call void @free(i8* [[TMP5]])
 ; CHECK-NEXT:    call void @__cxa_end_catch()
 ; CHECK-NEXT:    br label [[FUN_RET]]
 ; CHECK:       fun.ret:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %call = call i8* @malloc(i64 4)
   %0 = bitcast i8* %call to i32*