[LICM] Allow promotion of some stores that are not guaranteed to execute

[mkuper]

Summary

Promotion is always legal when a store within the loop is guaranteed to execute.

However, this is not a necessary condition - for promotion to be memory model semantics-preserving, it is enough to have a store that dominates every exit block. This is because if the store dominates every exit block, the fact the exit block was executed implies the original store was executed as well.

[reames]

I'm responding to the description. If the implementation splits a hair the description doesn't, my response may be off base.

I don't think this transform is legal. The exception being thrown might be what prevents the otherwise faulting load or store from executing.

Consider this small example:
for(.i = ...) {

throw_if_out_of_bounds(i);
a[i] += 5;

}

We can't speculatively execute the load from a[i] as it might be the case that it crosses a page boundary and dereferencing the memory will introduce a page fault which doesn't exist in the original program.

(I'm deliberately using a loop variant i in the example, but the same thing applies if i is loop invariant.)

lib/Transforms/Scalar/LICM.cpp

910–911

You don't need a store. A load is sufficient for this part.

[reames]

test/Transforms/LICM/scalar_promote.ll

209

Both of your examples have unconditional loads with conditional stores. This is interesting in that the dereferenceability would seem to be established by the load. Is this representative of the real example you're trying to address?

[mkuper]

Thanks, Philip!

Yes, sorry, that was unclear from the description. I think it's clearer in the inline comment.

For promotion to be legal you need two conditions to hold:

1. You can unconditionally dereference the pointer in a hoisted load. This holds is if at least one store or load is guaranteed to execute - but that's not a necessary condition. You may know the pointer is dereferencible through other means.
2. You are allowed to sink the store, from the memory model point of view. The previous code would check that the store is either guaranteed to execute or, if not, stores to a thread local.

What I'm doing here is relaxing condition 2.
Assuming I got the logic right, this patch should not be introducing any cases where the load can fault. That's why my tests have an unconditional load.

This targets reduction loops like

for (int i = 0; i < n; ++i)
  for (int j = 0; j < m; ++j)
    local[i] += foo(i,j)

Where local[i] would otherwise be promotable within the loop, except that the store is not guaranteed to execute because foo() may throw. Note that the load precedes the call to bar.

[mkuper]

Added more tests that hopefully alleviate Philip's concerns.

[reames]

Ok, with the inline discussion, it looks like this is a valid and useful extension. Can you update the description of the patch to reflect the discussion?

Inline code comments below.

lib/Transforms/Scalar/LICM.cpp

253

You've got a scattering of unrelated trivial cleanup changes here (style fixes, clarifying comments on the original code, etc..). Please separate those and submit them. No further review needed, but I'd like to get them out of this patch for future rounds.

258

Changing from the or and exit scheme to the and scheme should be NFC. Please separate and land without further review. (In particular, if this turns out *not* to be NFC, I want to be able to bisect to the refactoring.)

268

You switching from a lazy to an eager computation of both exit blocks and insert pts. In this case, it shouldn't matter since hasDedicatedExits also does the same (relatively expensive) computation of the loop exits.

At some point, we really do need to cache the loop exit walk.... (not for this change)

288

Use of the Changed variable here is overly conservative. We actually only need to run this if *store promotion* changed the loop. If you wanted to do that as a a separate change, it would be a useful cleanup and compile time win.

955

This loop is getting really complicated and hard to follow. I think we need to find an alternate structure here which makes your changes easier to reason about.

One idea would be to introduce two variables for the two different things we're trying to establish. (i.e. LocationIsDereferencable, and CanInsertStoresOnExits.) The key simplification is that we don't need to track *why* we know we can insert the stores.

I'm also open to other organizations here.

970

You still need a slightly modified version of this comment.

1034

I'm having a hard time following the semantic changes here intermixed with the refactoring. Please separate that and commit without further review. I suspect that once that's done, I'll spot a couple more things here.

test/Transforms/LICM/scalar_promote.ll

208

Looking at this test, it really should be handled by the thread local code we already have. Have you looked to see why it isn't?

In fact, looking at *all* of your tests, the thread local case should handle it...?

(Note: This is a very important question to that I'll want an answer to before we commit the semantics parts of this code.)

[mkuper]

lib/Transforms/Scalar/LICM.cpp

253

I'm not sure all of those changes makes sense while ExitBlocks are still computed lazily. I'll separate as many of them as reasonable, let me know if you still want things unbundled at the next iteration.

258

So, it's not NFC on its own, because it also requries the sinking the formLCSSARecursively() call out of the if.

Note that:

1. If Changed was true, then "Preheader || L->hasDedicatedExits()" is true, because the arguments to the or guard the previous transofrmations.
2. The "if (Changed)" on line 269 can be true even if promoteLoopAccessesToScalars() made no changes, since it's the same Changed variable, not one defined within the if block.

So we end up running formLCSSARecursively() for *any* change. Which works, by accident, but is really counter-intuitive. And would breaks if DisablePromotion actually happend to be true.

The two changes should be NFC when combined, though, so I'll commit that separately.

268

It's not just that - isGuaranteedToExecute() also does the same computation...
But yes, that's a separate change.

288

I think that's actually wrong (and the comment is misleading, I should fix it)- see above for explanation.

I mean, I'm not saying that we *need* to run it in other cases (although I'm pretty sure we do), I'm saying we *did* run it in other cases, and I'd prefer this part to be NFC.

910–911

No, if the load is guaranteed to be executed, but the store is under control flow, then it's not safe to promote, unless you have additional information (next paragraph).

I can try to rewrite this whole thing, but I'm not sure I can make it both precise and clearer.

955

I agree. I'll see if I can simplify.

test/Transforms/LICM/scalar_promote.ll

208

Why would it be handled by the thread-local code?
%local is an alloca, so it's not thread-local memory.

[mkuper]

lib/Transforms/Scalar/LICM.cpp

288

And looks like I was wrong, apparently this really is fine to run only for promotions, I guess the other transformations preserve LCSSA.
I'll sort all of that out first, then update this patch.

[reames]

Responding to the thread local discussion, but leaving the rest until you've separated the various pieces and landed them.

test/Transforms/LICM/scalar_promote.ll

208

An alloca is thread local until the first time it escapes and become visible to another thread. This is the same as a call to malloc().

I think the isAllocLikeFn check in the thread local case should become (isAllocLikeFn || isa<AllocaInst>). I believe that will handle the cases you've mentioned.

[mkuper]

test/Transforms/LICM/scalar_promote.ll

208

An alloca is thread local until the first time it escapes and become visible to another thread. This is the same as a call to malloc().

Argh, right.

I think the isAllocLikeFn check in the thread local case should become (isAllocLikeFn || isa<AllocaInst>). I believe that will handle the cases you've mentioned.

I guess you're right, that will solve most issues. Thanks for the (failed :-) ) sanity check.
I think we may want both things, though - this can fire even if the alloca is captured (or if it's a global or a function argument instead of the alloca), if bar is argmemonly/readnone.

[reames]

test/Transforms/LICM/scalar_promote.ll

208

Completely agreed that we want both. Multiple ways to skin a cat are always welcome; sometimes one falls over where another doesn't.

Why don't you spawn another thread for the thread local change and save this one for the current approach? I see that you've split out most of the pieces, so once we rebase this should be much easier to review. I'd really like to see both pieces land in the next day or so.

[mkuper]

So, the patch is now fairly small, but I'm having trouble with the testcases.
In particular, I think what we have now is unsound, because isGuaranteedToTransferExecutionToSuccessor() returns true for argmemonly calls, which means that things that should only get promoted with my patch get promoted without.

I'll get back to this on Tuesday. For now, I'll upload the code change, without fixing the tests, in case you want to take a look at the semantic change.

[reames]

In D28147#632595, @mkuper wrote:

So, the patch is now fairly small, but I'm having trouble with the testcases.
In particular, I think what we have now is unsound, because isGuaranteedToTransferExecutionToSuccessor() returns true for argmemonly calls, which means that things that should only get promoted with my patch get promoted without.

We have a prevaling assumption that to throw an exception, you must write to some global (but unknown) location to do so. We effectively assume that any readonly call is also nounwind. As you point out, we also assume that argmemonly must be readonly with respect to that unknown magic location. That doesn't seem sound as the location written to might be reachable through an argument of the function. So, yes, I think this is wrong.

I'll get back to this on Tuesday. For now, I'll upload the code change, without fixing the tests, in case you want to take a look at the semantic change.

Thanks. I took a look and have only minor comments on what's left. Once we have the above issue fixed, this will be quick.

lib/Transforms/Scalar/LICM.cpp

919

if an exception is thrown *on the first iteration*.

1006

Expand this comment a bit. possibly: because it must have executed in the original program before reaching one of the inert points.

[sanjoy]

In D28147#632595, @mkuper wrote:

So, the patch is now fairly small, but I'm having trouble with the testcases.
In particular, I think what we have now is unsound, because isGuaranteedToTransferExecutionToSuccessor() returns true for argmemonly calls, which means that things that should only get promoted with my patch get promoted without.

That was an oversight, fixed in https://reviews.llvm.org/rL290794

I'll get back to this on Tuesday. For now, I'll upload the code change, without fixing the tests, in case you want to take a look at the semantic change.

[mkuper]

After r290794, it looks like the tests are actually checking what they should.

[efriedma]

test/Transforms/LICM/scalar_promote.ll

222

I'm pretty sure this transform is wrong. For example, @capture could create a mutex protecting %local, and lock it. Then @opaque could release the mutex, does some work, and lock the mutex. In that case, the value stored by store i32 %x2, i32* %local is visible to other threads in each iteration, so you can't sink the store out of the loop.

[efriedma]

test/Transforms/LICM/scalar_promote.ll

222

Err, my example is overly complicated. You don't need multiple threads. The address of %local escapes, therefore @opaque could read it, therefore we have to update it every iteration of the loop.

[efriedma]

test/Transforms/LICM/scalar_promote.ll

222

Err, sorry, ignore me, didn't notice the argmemonly annotation on @opaque. I need to think a bit.

[mkuper]

test/Transforms/LICM/scalar_promote.ll

222

I'm not actually changing this behavior.
The transformation is already performed when @opaque is marked as nounwind. This patch only removes the nounwind requirement, which has no bearing on your scenario.

In any case, I don't think the stores are required to be observable in this scenario (and you also need to pass the mutex as an argument, but, technically, that's possible), so I believe the transformation is still legal. If we reach the conclusion it's not, then it will still be legal if opaque is "argmemonly readonly", since readonly functions are not allowed to perform atomic writes. So we'll need to start requiring readonly (and not just argmemonly), but that's orthogonal to this patch.

[efriedma]

I'm satisfied with this, with some minor tweaks.

lib/Transforms/Scalar/LICM.cpp

1013

This check is similar to llvm::isGuaranteedToExecute. Maybe worth noting the parallel here.

If the loop throws, you're depending on the earlier check that the memory location is an alloca; you should explicitly note that here.

test/Transforms/LICM/scalar_promote.ll

222

Mmm... okay, I think I understand what's happening.

From a memory model perspective, the rule is this: if the current thread performs a non-atomic store to %local, no other thread is allowed to read that memory until the current thread performs an atomic release (or equivalent). Therefore, if a loop doesn't contain an atomic release, and every exit is dominated by a non-atomic store, you can sink the store out of the loop. (An atomic release gets modeled by alias analysis as a read to all memory locations whose addresses have escaped, so the existence of the alias set implies the loop doesn't contain a relevant atomic release.)

The wrinkle introduced by a call which throws is that there are additional exits which are not modeled in the CFG; the store might not actually dominate all exits. That said, if a loop throws, we only allow sinking stores to allocas, and allocas get deallocated when the loop throws, so we're still okay.

[mkuper]

Thanks Eli.

Philip, do you have any more comments?

lib/Transforms/Scalar/LICM.cpp

1013

I'm not depending on it being an alloca. I'm only depending on it being dereferenceable - which is the DereferenceableInPH check and is documented. So I'm not sure how this can be more explicit.

[efriedma]

lib/Transforms/Scalar/LICM.cpp

1013

The implicit unwind edges from the loop aren't listed in ExitBlocks, so you aren't checking them. If the memory is an alloca, this doesn't matter because the unwind edge will end the lifetime of the alloca; if we somehow extended LICM so it could make implicit unwind edges explicit, the missing check might matter.

[mkuper]

lib/Transforms/Scalar/LICM.cpp

1013

Oh, got it, you mean the check on line 951. Right, will add a comment.

[reames]

No further comments, LGTM

lib/Transforms/Scalar/LICM.cpp

if (L->hasDedicatedExits())
     Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
                           CurAST, &SafetyInfo);
   if (Preheader)
     Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
                            CurAST, &SafetyInfo);
 
   // Now that all loop invariants have been removed from the loop, promote any
   // memory references to scalars that we can.
-  if (!DisablePromotion && (Preheader || L->hasDedicatedExits())) {
+  // Don't sink stores from loops without dedicated block exits. Exits
+  // containing indirect branches are not transformed by loop simplify,
+  // make sure we catch that. An additional load may be generated in the
+  // preheader for SSA updater, so also avoid sinking when no preheader
+  // is available.
+  if (!DisablePromotion && Preheader && L->hasDedicatedExits()) {
+    // Figure out the loop exits and their insertion points
     SmallVector<BasicBlock *, 8> ExitBlocks;
+    L->getUniqueExitBlocks(ExitBlocks);
+
+    // We can't insert into a catchswitch.
+    bool HasCatchSwitch = llvm::any_of(ExitBlocks, [](BasicBlock *Exit) {
+      return isa<CatchSwitchInst>(Exit->getTerminator());
+    });
+
+    if (!HasCatchSwitch) {
       SmallVector<Instruction *, 8> InsertPts;
+      InsertPts.reserve(ExitBlocks.size());
+      for (BasicBlock *ExitBlock : ExitBlocks)
+        InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
+
       PredIteratorCache PIC;
 
       // Loop over all of the alias sets in the tracker object.
       for (AliasSet &AS : *CurAST)
-      Changed |= promoteLoopAccessesToScalars(
-          AS, ExitBlocks, InsertPts, PIC, LI, DT, TLI, L, CurAST, &SafetyInfo);
+        Changed |=
+            promoteLoopAccessesToScalars(AS, ExitBlocks, InsertPts, PIC, LI, DT,
+                                         TLI, L, CurAST, &SafetyInfo);
+    }
+  }
 
-    // Once we have promoted values across the loop body we have to recursively
-    // reform LCSSA as any nested loop may now have values defined within the
-    // loop used in the outer loop.
-    // FIXME: This is really heavy handed. It would be a bit better to use an
-    // SSAUpdater strategy during promotion that was LCSSA aware and reformed
-    // it as it went.
-    if (Changed) {
-      formLCSSARecursively(*L, *DT, LI, SE);
-    }
-  }
+  // Once we have promoted values across the loop body we have to
+  // recursively
+  if (Changed)
 
   // Check that neither this loop nor its parent have had LCSSA broken. LICM is
   // specifically moving instructions across the loop boundary and so it is
   // especially in need of sanity checking here.
   assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!");
   assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) &&
          "Parent loop not left in LCSSA form after LICM!");
 
bool llvm::promoteLoopAccessesToScalars(
   //
   // The safety property divides into two parts:
   // 1) The memory may not be dereferenceable on entry to the loop.  In this
   //    case, we can't insert the required load in the preheader.
   // 2) The memory model does not allow us to insert a store along any dynamic
   //    path which did not originally have one.
   //
   // It is safe to promote P if all uses are direct load/stores and if at
-  // least one is guaranteed to be executed.
-  bool GuaranteedToExecute = false;
+  // least one store is guaranteed to be executed.
+  bool PromotionIsLegal = false;
 
   // It is also safe to promote P if we can prove that speculating a load into
   // the preheader is safe (i.e. proving dereferenceability on all
-  // paths through the loop), and that the memory can be proven thread local
-  // (so that the memory model requirement doesn't apply.)  We first establish
-  // the former, and then run a capture analysis below to establish the later.
-  // We can use any access within the alias set to prove dereferenceability
-  // since they're all must alias.
+  // paths through the loop), and if we are sure we don't introduce memory
+  // model issues by sinking the store.
+  // A store is safe to sink if:
+  // a) We can prove the memory it stores to is thread local, in which case
+  // the memory model requirement does not apply.
+  // b) It was already guaranteed to execute at least once (see above).
+  // c) It was not guaranteed to execute - but only because we may exit the loop
+  // through an exception. This guarantees that dynamic executions which would
+  // not execute the original store will not execute the exit block, so no 
+  // new store is introduced.
   bool CanSpeculateLoad = false;
+  bool StoreDominatesExits = false;
 
   SmallVector<Instruction *, 64> LoopUses;
   SmallPtrSet<Value *, 4> PointerMustAliases;
 
   // We start with an alignment of one and try to find instructions that allow
   // us to prove better alignment.
   unsigned Alignment = 1;
   AAMDNodes AATags;
-  bool HasDedicatedExits = CurLoop->hasDedicatedExits();
 
-  // Don't sink stores from loops without dedicated block exits. Exits
-  // containing indirect branches are not transformed by loop simplify,
-  // make sure we catch that. An additional load may be generated in the
-  // preheader for SSA updater, so also avoid sinking when no preheader
-  // is available.
-  if (!HasDedicatedExits || !Preheader)
-    return false;
+  assert(CurLoop->hasDedicatedExits() && Preheader &&
+         "Expected prehader and dedicated loop exits.");
 
   const DataLayout &MDL = Preheader->getModule()->getDataLayout();
 
   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)))
       return 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.
   bool Changed = false;
   for (const auto &ASI : AS) {
     Value *ASIV = ASI.getValue();
     PointerMustAliases.insert(ASIV);
 
     // 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.
     if (SomePtr->getType() != ASIV->getType())
       return Changed;
 
     for (User *U : ASIV->users()) {
       // Ignore instructions that are outside the loop.
       Instruction *UI = dyn_cast<Instruction>(U);
       if (!UI || !CurLoop->contains(UI))
         continue;
 
       // If there is an non-load/store instruction in the loop, we can't promote
       // it.
       if (const LoadInst *Load = dyn_cast<LoadInst>(UI)) {
         assert(!Load->isVolatile() && "AST broken");
         if (!Load->isSimple())
           return Changed;
 
-        if (!GuaranteedToExecute && !CanSpeculateLoad)
+        if (!PromotionIsLegal && !CanSpeculateLoad)
           CanSpeculateLoad = isSafeToExecuteUnconditionally(
               *Load, DT, CurLoop, SafetyInfo, 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;
         assert(!Store->isVolatile() && "AST broken");
         if (!Store->isSimple())
           return Changed;
 
-        // Note that we only check GuaranteedToExecute inside the store case
-        // so that we do not introduce stores where they did not exist before
-        // (which would break the LLVM concurrency model).
-
         // If the alignment of this instruction allows us to specify a more
         // restrictive (and performant) alignment and if we are sure this
         // instruction will be executed, update the alignment.
         // Larger is better, with the exception of 0 being the best alignment.
         unsigned InstAlignment = Store->getAlignment();
         if ((InstAlignment > Alignment || InstAlignment == 0) &&
             Alignment != 0) {
           if (isGuaranteedToExecute(*UI, DT, CurLoop, SafetyInfo)) {
-            GuaranteedToExecute = true;
+            PromotionIsLegal = true;
             Alignment = InstAlignment;
           }
-        } else if (!GuaranteedToExecute) {
-          GuaranteedToExecute =
+        } else if (!PromotionIsLegal) {
+          PromotionIsLegal =
               isGuaranteedToExecute(*UI, DT, CurLoop, SafetyInfo);
         }
 
-        if (!GuaranteedToExecute && !CanSpeculateLoad) {
+        if (!PromotionIsLegal) {
+          if (!CanSpeculateLoad)
             CanSpeculateLoad = isDereferenceableAndAlignedPointer(
                 Store->getPointerOperand(), Store->getAlignment(), MDL,
                 Preheader->getTerminator(), DT);
+          if(!StoreDominatesExits) {
+            StoreDominatesExits = llvm::all_of(ExitBlocks, [&](BasicBlock *Exit) {
+              return DT->dominates(Store->getParent(), Exit);
+            });
+          }
+
         }
       } else
         return Changed; // Not a load or store.
 
       // Merge the AA tags.
       if (LoopUses.empty()) {
         // On the first load/store, just take its AA tags.
         UI->getAAMetadata(AATags);
       } else if (AATags) {
         UI->getAAMetadata(AATags, /* Merge = */ true);
       }
 
       LoopUses.push_back(UI);
     }
   }
 
   // Check legality per comment above. Otherwise, we can't promote.
-  bool PromotionIsLegal = GuaranteedToExecute;
   if (!PromotionIsLegal && CanSpeculateLoad) {
+    PromotionIsLegal = StoreDominatesExits;
     // If this is a thread local location, then we can insert stores along
     // paths which originally didn't have them without violating the memory
     // model.
+    if (!PromotionIsLegal) {
       Value *Object = GetUnderlyingObject(SomePtr, MDL);
-    PromotionIsLegal =
-        isAllocLikeFn(Object, TLI) && !PointerMayBeCaptured(Object, true, true);
+      PromotionIsLegal = isAllocLikeFn(Object, TLI) &&
+                         !PointerMayBeCaptured(Object, true, true);
     }
-  if (!PromotionIsLegal)
-    return Changed;
-
-  // Figure out the loop exits and their insertion points, if this is the
-  // first promotion.
-  if (ExitBlocks.empty()) {
-    CurLoop->getUniqueExitBlocks(ExitBlocks);
-    InsertPts.clear();
-    InsertPts.reserve(ExitBlocks.size());
-    for (BasicBlock *ExitBlock : ExitBlocks)
-      InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
   }
-
-  // Can't insert into a catchswitch.
-  for (BasicBlock *ExitBlock : ExitBlocks)
-    if (isa<CatchSwitchInst>(ExitBlock->getTerminator()))
-      return Changed;
+  if (!PromotionIsLegal)
 
   // Otherwise, this is safe to promote, lets do it!
   DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " << *SomePtr
                << '\n');
   Changed = true;
   ++NumPromoted;
 
   // Grab a debug location for the inserted loads/stores; given that the

test/Transforms/LICM/scalar_promote.ll

 
 ; CHECK: for.body.lr.ph:
 ; CHECK-NEXT:  %gi.promoted = load i32, i32* %gi, align 4, !tbaa !0
 ; CHECK: for.cond.for.end_crit_edge:
 ; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %inc
 ; CHECK-NEXT:  store i32 %[[LCSSAPHI]], i32* %gi, align 4, !tbaa !0
 }
 
+declare i32 @opaque(i32)
+
+; We can promote even if opaque may throw.
+define i32 @test7() {
+; CHECK-LABEL: @test7(
+; CHECK: entry:
+; CHECK-NEXT: %local = alloca
+; CHECK-NEXT: load i32, i32* %local
+; CHECK-NEXT: br label %loop
+; CHECK: exit:
+; CHECK-NEXT: %[[LCSSAPHI:.*]] = phi i32 [ %x2, %loop ]
+; CHECK-NEXT: store i32 %[[LCSSAPHI]], i32* %local
+; CHECK-NEXT: %ret = load i32, i32* %local
+; CHECK-NEXT: ret i32 %ret
+entry:
+  %local = alloca i32
+  br label %loop
+
+
+loop:
+  %j = phi i32 [ 0, %entry ], [ %next, %loop ]
+  %x = load i32, i32* %local
+  %x2 = call i32 @opaque(i32 %x) ; Note this does not capture %local
+  store i32 %x2, i32* %local
+  %next = add i32 %j, 1
+  %cond = icmp eq i32 %next, 0
+  br i1 %cond, label %exit, label %loop
+
+exit:
+  %ret = load i32, i32* %local
+  ret i32 %ret
+}
+
+; Make sure we don't promote if the store is really control-flow dependent.
+define i32 @test7bad() {
+; CHECK-LABEL: @test7bad(
+; CHECK: entry:
+; CHECK-NEXT: %local = alloca
+; CHECK-NEXT: br label %loop
+; CHECK: if:
+; CHECK-NEXT: store i32 %x2, i32* %local
+; CHECK-NEXT: br label %else
+; CHECK: exit:
+; CHECK-NEXT: %ret = load i32, i32* %local
+; CHECK-NEXT: ret i32 %ret
+entry:
+  %local = alloca i32
+  br label %loop
+loop:
+  %j = phi i32 [ 0, %entry ], [ %next, %else ]
+  %x = load i32, i32* %local
+  %x2 = call i32 @opaque(i32 %x) ; Note this does not capture %local
+  %cmp = icmp eq i32 %x2, 0
+  br i1 %cmp, label %if, label %else
+
+if:  
+  store i32 %x2, i32* %local
+  br label %else
+
+else:
+  %next = add i32 %j, 1
+  %cond = icmp eq i32 %next, 0
+  br i1 %cond, label %exit, label %loop
+
+exit:
+  %ret = load i32, i32* %local
+  ret i32 %ret
+}
+
+; Even if neither the load nor the store or guaranteed to execute because
+; opaque() may throw, we can still promote - the load not being guaranteed
+; doesn't block us, because %local is always dereferencible.
+define i32 @test8() {
+; CHECK-LABEL: @test8(
+; CHECK: entry:
+; CHECK-NEXT: %local = alloca
+; CHECK-NEXT: load i32, i32* %local
+; CHECK-NEXT: br label %loop
+; CHECK: exit:
+; CHECK-NEXT: %[[LCSSAPHI:.*]] = phi i32 [ %x2, %loop ]
+; CHECK-NEXT: store i32 %[[LCSSAPHI]], i32* %local
+; CHECK-NEXT: %ret = load i32, i32* %local
+; CHECK-NEXT: ret i32 %ret
+entry:
+  %local = alloca i32
+  br label %loop
+
+loop:
+  %j = phi i32 [ 0, %entry ], [ %next, %loop ]
+  %throwaway = call i32 @opaque(i32 %j)
+  %x = load i32, i32* %local  
+  %x2 = call i32 @opaque(i32 %x)
+  store i32 %x2, i32* %local
+  %next = add i32 %j, 1
+  %cond = icmp eq i32 %next, 0
+  br i1 %cond, label %exit, label %loop
+
+exit:
+  %ret = load i32, i32* %local
+  ret i32 %ret
+}
+
+
+; If the store is "guaranteed modulo exceptions", and the load depends on
+; control flow, we can only promote if the pointer is otherwise known to be
+; dereferencible
+define i32 @test9() {
+; CHECK-LABEL: @test9(
+; CHECK: entry:
+; CHECK-NEXT: %local = alloca
+; CHECK-NEXT: load i32, i32* %local
+; CHECK-NEXT: br label %loop
+; CHECK: exit:
+; CHECK-NEXT: %[[LCSSAPHI:.*]] = phi i32 [ %x2, %else ]
+; CHECK-NEXT: store i32 %[[LCSSAPHI]], i32* %local
+; CHECK-NEXT: %ret = load i32, i32* %local
+; CHECK-NEXT: ret i32 %ret
+entry:
+  %local = alloca i32
+  br label %loop
+
+loop:
+  %j = phi i32 [ 0, %entry ], [ %next, %else ]  
+  %j2 = call i32 @opaque(i32 %j)
+  %cmp = icmp eq i32 %j2, 0
+  br i1 %cmp, label %if, label %else
+
+if:  
+  %x = load i32, i32* %local
+  br label %else
+
+else:
+  %x2 = phi i32 [ 0, %loop ], [ %x, %if]
+  store i32 %x2, i32* %local
+  %next = add i32 %j, 1
+  %cond = icmp eq i32 %next, 0
+  br i1 %cond, label %exit, label %loop
+
+exit:
+  %ret = load i32, i32* %local
+  ret i32 %ret
+}
+
+define i32 @test9bad(i32 %i) {
+; CHECK-LABEL: @test9bad(
+; CHECK: entry:
+; CHECK-NEXT: %local = alloca
+; CHECK-NEXT: %notderef = getelementptr
+; CHECK-NEXT: br label %loop
+; CHECK: if:
+; CHECK-NEXT: load i32, i32* %notderef
+; CHECK-NEXT: br label %else
+; CHECK: exit:
+; CHECK-NEXT: %ret = load i32, i32* %notderef
+; CHECK-NEXT: ret i32 %ret
+entry:
+  %local = alloca i32
+  %notderef = getelementptr i32, i32* %local, i32 %i
+  br label %loop
+
+loop:
+  %j = phi i32 [ 0, %entry ], [ %next, %else ]  
+  %j2 = call i32 @opaque(i32 %j)
+  %cmp = icmp eq i32 %j2, 0
+  br i1 %cmp, label %if, label %else
+
+if:  
+  %x = load i32, i32* %notderef
+  br label %else
+
+else:
+  %x2 = phi i32 [ 0, %loop ], [ %x, %if]
+  store i32 %x2, i32* %notderef
+  %next = add i32 %j, 1
+  %cond = icmp eq i32 %next, 0
+  br i1 %cond, label %exit, label %loop
+
+exit:
+  %ret = load i32, i32* %notderef
+  ret i32 %ret
+}
+
 !0 = !{!4, !4, i64 0}
 !1 = !{!"omnipotent char", !2}
 !2 = !{!"Simple C/C++ TBAA"}
 !3 = !{!5, !5, i64 0}
 !4 = !{!"int", !1}
 !5 = !{!"float", !1}