DSE miscompile when store is clobbered across loop iterations

[apilipenko]

Summary

(This is a resubmission of D67870 with llvm-commits is subscribers)

Currently DSE miscompiles the following example:

a = calloc(n+1)
for (int i = 0; i < n; i++) {

store 1, a[i+1] // (1)
store 0, a[i]   // (2)

}
It eliminates the second store thinking that it's redundant. This happens because memoryIsNotModifiedBetween doesn't see a[i] being clobbered in between the allocation and the store.

memoryIsNotModifiedBetween does a backwards scan through the CFG from SecondI to FirstI. It looks for instructions which can modify the memory location accessed by SecondI. For every may-write-to-memory instruction is asks AA whether this instruction modifies memory location accessed by SecondI.

The problem occurs when it visits the loop block through a backedge. It asks the AA about aliasing between stores (1) and (2). BasicAA sees that two stores access addresses which are distincs offsets from the same base and concludes that they don't alias. This is true for accesses within one loop iteration, but this is not true across iterations.

The change is to keep track whether we visit a block through a backedge. If we visit the block through a backedge, be conservative and treat any may-write-to-memory instruction as a clobber.

Note that there is a somewhat similar problem in DA:
https://bugs.llvm.org/show_bug.cgi?id=42143

[apilipenko]

Ping?

[bjope]

lib/Transforms/Scalar/DeadStoreElimination.cpp

625 ↗

(On Diff #221656)

Isn't store-block confusing?

630 ↗

(On Diff #221656)

Load-block?

636 ↗

(On Diff #221656)

Is LI an old name for FirstI or FirstBBI? There is several more refs to LI and SI in the code below. Makes it a little bit hard to follow what is going on here, since the code/comments are rotten already in the baseline. Would not mind if that was cleaned up in a separate commit.

641 ↗

(On Diff #221656)

Is SI an old name for SecondI? Or SecondBBI?

666 ↗

(On Diff #221656)

nit: I don't think that we need this local variable. Just use *PredI instead. If you keep it, then be explicit about the type instead of using auto. (As currently written you have similarly named variables that more or less can denote the same thing, but without really explaining the difference by having any type information. Just confusing IMHO.)

670 ↗

(On Diff #221656)

If we have a cfg such as

A: (firstBB)
B: preds A, D
C: preds B (secondBB)
D: preds C

then I think we only visit block B once with this solution. And with VisitedThroughBackedge being false. It is only the SecondBB that can be visited twice afaict. Isn't that a problem?

[apilipenko]

• Comment cleanup was landed separately
• Fixed the issue mentioned in https://reviews.llvm.org/D68006#inline-616849
• Added more tests

[apilipenko]

Ping?

[efriedma]

This is specifically a hole in the calloc() handling, right? This case can't come up in regular load->store forwarding: the address of the load dominates the load, so the address dominates all the operations between the load and the store, so alias() does the right thing.

We could try to avoid the backedge checking for load->store forwarding. And we could try to be more aggressive if the address is some invariant offset into the calloc. Maybe not that likely to matter? What sort of impact does this have on how frequently the transforms triggers?

[apilipenko]

I reworked the patch using PHITransAddr. Now instead of tracking the backedge flag I keep track of the address to check and translate the address when needed.

This change should resolve the concern about overly conservative handling of load-store case, when the address dominates all the operations between load and store. Using PHITransAddr we would only do the translation if it's actually needed.

[efriedma]

This makes sense. Please add at least one testcase where PHI translation looks through a PHI node and makes the transform successful.

[apilipenko]

Demonstrating an improvement accuracy due to PHI translation turned out to be a bit tricky.

So, it doesn't apply to load-store case as in this case the accessed addresses are the same, so no translation is needed.

In calloc case there are two limitations:

1. Currently we look for stores to pointers with GetUnderlyingObject == calloc. Because GetUnderlyingObject doesn't look through phis we can't handle this case:

  %c = calloc
  %p1 = gep %c, X
  %p2 = gep %c, Y
  ...

label:  
  %p = phi %p1, %p2
  store 0, %p

So we are limited to cases like this:

  %c = calloc
  ...

label:
  %off = phi ...
  %p = gep %c, %off
  store 0, %p

2. Currently I don't analyze the same block with different addresses. If such situation occurs I bail out assuming clobber (the same logic is used in MDA). But because the calloc dominates the store, eventually we'll visit the calloc block. If there are different paths reaching this block with different pointer values we would bail out. So, the example I came up with uses the same pointer on different paths. See test45 and test46 cases.

Essentially I'm using PHITransAddr as a marker that the address needs translation walking up to the predecessor. I don't make real use of the translated address due to lack of path sensitivity.

[efriedma]

Okay, that makes sense. There isn't any particular reason we can't visit a block multiple times, but probably not worth doing unless we find some case where it matters.

LGTM

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 }
 
 /// Returns true if the memory which is accessed by the second instruction is not
 /// modified between the first and the second instruction.
 /// Precondition: Second instruction must be dominated by the first
 /// instruction.
 static bool memoryIsNotModifiedBetween(Instruction *FirstI,
                                        Instruction *SecondI,
-                                       AliasAnalysis *AA) {
-  SmallVector<BasicBlock *, 16> WorkList;
-  SmallPtrSet<BasicBlock *, 8> Visited;
+                                       AliasAnalysis *AA,
+                                       const DataLayout &DL,
+                                       DominatorTree *DT) {
+  // Do a backwards scan through the CFG from SecondI to FirstI. Look for
+  // instructions which can modify the memory location accessed by SecondI.
+  //
+  // While doing the walk keep track of the address to check. It might be
+  // different in different basic blocks due to PHI translation.
+  using BlockAddressPair = std::pair<BasicBlock *, PHITransAddr>;
+  SmallVector<BlockAddressPair, 16> WorkList;
+  // Keep track of the address we visited each block with. Bail out if we
+  // visit a block with different addresses.
+  DenseMap<BasicBlock *, Value *> Visited;
+
   BasicBlock::iterator FirstBBI(FirstI);
   ++FirstBBI;
   BasicBlock::iterator SecondBBI(SecondI);
   BasicBlock *FirstBB = FirstI->getParent();
   BasicBlock *SecondBB = SecondI->getParent();
   MemoryLocation MemLoc = MemoryLocation::get(SecondI);
+  auto *MemLocPtr = const_cast<Value *>(MemLoc.Ptr);
 
   // Start checking the SecondBB.
-  WorkList.push_back(SecondBB);
+  WorkList.push_back(
+      std::make_pair(SecondBB, PHITransAddr(MemLocPtr, DL, nullptr)));
   bool isFirstBlock = true;
 
   // Check all blocks going backward until we reach the FirstBB.
   while (!WorkList.empty()) {
-    BasicBlock *B = WorkList.pop_back_val();
+    BlockAddressPair Current = WorkList.pop_back_val();
+    BasicBlock *B = Current.first;
+    PHITransAddr &Addr = Current.second;
+    Value *Ptr = Addr.getAddr();
 
     // Ignore instructions before FirstI if this is the FirstBB.
     BasicBlock::iterator BI = (B == FirstBB ? FirstBBI : B->begin());
 
     BasicBlock::iterator EI;
     if (isFirstBlock) {
       // Ignore instructions after SecondI if this is the first visit of SecondBB.
       assert(B == SecondBB && "first block is not the store block");
       EI = SecondBBI;
       isFirstBlock = false;
     } else {
       // It's not SecondBB or (in case of a loop) the second visit of SecondBB.
       // In this case we also have to look at instructions after SecondI.
       EI = B->end();
     }
     for (; BI != EI; ++BI) {
       Instruction *I = &*BI;
       if (I->mayWriteToMemory() && I != SecondI)
-        if (isModSet(AA->getModRefInfo(I, MemLoc)))
+        if (isModSet(AA->getModRefInfo(I, MemLoc.getWithNewPtr(Ptr))))
           return false;
     }
     if (B != FirstBB) {
       assert(B != &FirstBB->getParent()->getEntryBlock() &&
           "Should not hit the entry block because SI must be dominated by LI");
       for (auto PredI = pred_begin(B), PE = pred_end(B); PredI != PE; ++PredI) {
-        if (!Visited.insert(*PredI).second)
+        PHITransAddr PredAddr = Addr;
+        if (PredAddr.NeedsPHITranslationFromBlock(B)) {
+          if (!PredAddr.IsPotentiallyPHITranslatable())
+            return false;
+          if (PredAddr.PHITranslateValue(B, *PredI, DT, false))
+            return false;
+        }
+        Value *TranslatedPtr = PredAddr.getAddr();
+        auto Inserted = Visited.insert(std::make_pair(*PredI, TranslatedPtr));
+        if (!Inserted.second) {
+          // We already visited this block before. If it was with a different
+          // address - bail out!
+          if (TranslatedPtr != Inserted.first->second)
+            return false;
+          // ... otherwise just skip it.
           continue;
-        WorkList.push_back(*PredI);
+        }
+        WorkList.push_back(std::make_pair(*PredI, PredAddr));
       }
     }
   }
   return true;
 }
 
 /// Find all blocks that will unconditionally lead to the block BB and append
 /// them to F.
static bool removePartiallyOverlappedStores(AliasAnalysis *AA,
   return Changed;
 }
 
 static bool eliminateNoopStore(Instruction *Inst, BasicBlock::iterator &BBI,
                                AliasAnalysis *AA, MemoryDependenceResults *MD,
                                const DataLayout &DL,
                                const TargetLibraryInfo *TLI,
                                InstOverlapIntervalsTy &IOL,
-                               MapVector<Instruction *, bool> &ThrowableInst) {
+                               MapVector<Instruction *, bool> &ThrowableInst,
+                               DominatorTree *DT) {
   // Must be a store instruction.
   StoreInst *SI = dyn_cast<StoreInst>(Inst);
   if (!SI)
     return false;
 
   // If we're storing the same value back to a pointer that we just loaded from,
   // then the store can be removed.
   if (LoadInst *DepLoad = dyn_cast<LoadInst>(SI->getValueOperand())) {
     if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
-        isRemovable(SI) && memoryIsNotModifiedBetween(DepLoad, SI, AA)) {
+        isRemovable(SI) &&
+        memoryIsNotModifiedBetween(DepLoad, SI, AA, DL, DT)) {
 
       LLVM_DEBUG(
           dbgs() << "DSE: Remove Store Of Load from same pointer:\n  LOAD: "
                  << *DepLoad << "\n  STORE: " << *SI << '\n');
 
       deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, ThrowableInst);
       ++NumRedundantStores;
       return true;
     }
   }
 
   // Remove null stores into the calloc'ed objects
   Constant *StoredConstant = dyn_cast<Constant>(SI->getValueOperand());
   if (StoredConstant && StoredConstant->isNullValue() && isRemovable(SI)) {
     Instruction *UnderlyingPointer =
         dyn_cast<Instruction>(GetUnderlyingObject(SI->getPointerOperand(), DL));
 
     if (UnderlyingPointer && isCallocLikeFn(UnderlyingPointer, TLI) &&
-        memoryIsNotModifiedBetween(UnderlyingPointer, SI, AA)) {
+        memoryIsNotModifiedBetween(UnderlyingPointer, SI, AA, DL, DT)) {
       LLVM_DEBUG(
           dbgs() << "DSE: Remove null store to the calloc'ed object:\n  DEAD: "
                  << *Inst << "\n  OBJECT: " << *UnderlyingPointer << '\n');
 
       deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, ThrowableInst);
       ++NumRedundantStores;
       return true;
     }
for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
     }
 
     // Check to see if Inst writes to memory.  If not, continue.
     if (!hasAnalyzableMemoryWrite(Inst, *TLI))
       continue;
 
     // eliminateNoopStore will update in iterator, if necessary.
     if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL,
-                           ThrowableInst)) {
+                           ThrowableInst, DT)) {
       MadeChange = true;
       continue;
     }
 
     // If we find something that writes memory, get its memory dependence.
     MemDepResult InstDep = MD->getDependency(Inst);
 
     // Ignore any store where we can't find a local dependence.
while (InstDep.isDef() || InstDep.isClobber()) {
           auto *Earlier = dyn_cast<StoreInst>(DepWrite);
           auto *Later = dyn_cast<StoreInst>(Inst);
           if (Earlier && isa<ConstantInt>(Earlier->getValueOperand()) &&
               DL.typeSizeEqualsStoreSize(
                   Earlier->getValueOperand()->getType()) &&
               Later && isa<ConstantInt>(Later->getValueOperand()) &&
               DL.typeSizeEqualsStoreSize(
                   Later->getValueOperand()->getType()) &&
-              memoryIsNotModifiedBetween(Earlier, Later, AA)) {
+              memoryIsNotModifiedBetween(Earlier, Later, AA, DL, DT)) {
             // If the store we find is:
             //   a) partially overwritten by the store to 'Loc'
             //   b) the later store is fully contained in the earlier one and
             //   c) they both have a constant value
             //   d) none of the two stores need padding
             // Merge the two stores, replacing the earlier store's value with a
             // merge of both values.
             // TODO: Deal with other constant types (vectors, etc), and probably

llvm/test/Transforms/DeadStoreElimination/simple.ll

 ; CHECK-NEXT:    ret void
 ;
 
   tail call void @llvm.memcpy.element.unordered.atomic.p0i8.p0i8.i64(i8* align 1 %P, i8* align 1 %Q, i64 12, i32 1)
   tail call void @llvm.memcpy.element.unordered.atomic.p0i8.p0i8.i64(i8* align 1 %P, i8* align 1 %R, i64 8, i32 1)
   ret void
 }
 
+define i32 @test40() {
+; CHECK-LABEL: @test40(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[M:%.*]] = call i8* @calloc(i32 9, i32 20)
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[P_NEXT:%.*]] = getelementptr inbounds i8, i8* [[M]], i64 [[INDVARS_IV_NEXT]]
+; CHECK-NEXT:    store i8 1, i8* [[P_NEXT]]
+; CHECK-NEXT:    [[P:%.*]] = getelementptr inbounds i8, i8* [[M]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store i8 0, i8* [[P]]
+; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ugt i64 [[INDVARS_IV]], 15
+; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[RETURN:%.*]]
+; CHECK:       return:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %m = call i8* @calloc(i32 9, i32 20)
+  br label %loop
+loop:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %loop ]
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %p.next = getelementptr inbounds i8, i8* %m, i64 %indvars.iv.next
+  store i8 1, i8* %p.next
+  %p = getelementptr inbounds i8, i8* %m, i64 %indvars.iv
+  store i8 0, i8* %p
+  %continue = icmp ugt i64 %indvars.iv, 15
+  br i1 %continue, label %loop, label %return
+return:
+  ret i32 0
+}
+
+define i32 @test41() {
+; CHECK-LABEL: @test41(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[M:%.*]] = call i8* @calloc(i32 9, i32 20)
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[CONT:%.*]] ]
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[P_NEXT:%.*]] = getelementptr inbounds i8, i8* [[M]], i64 [[INDVARS_IV_NEXT]]
+; CHECK-NEXT:    store i8 1, i8* [[P_NEXT]]
+; CHECK-NEXT:    br label [[CONT]]
+; CHECK:       cont:
+; CHECK-NEXT:    [[P:%.*]] = getelementptr inbounds i8, i8* [[M]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store i8 0, i8* [[P]]
+; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ugt i64 [[INDVARS_IV]], 15
+; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[RETURN:%.*]]
+; CHECK:       return:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %m = call i8* @calloc(i32 9, i32 20)
+  br label %loop
+loop:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %cont ]
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %p.next = getelementptr inbounds i8, i8* %m, i64 %indvars.iv.next
+  store i8 1, i8* %p.next
+  br label %cont
+
+cont:
+  %p = getelementptr inbounds i8, i8* %m, i64 %indvars.iv
+  store i8 0, i8* %p
+  %continue = icmp ugt i64 %indvars.iv, 15
+  br i1 %continue, label %loop, label %return
+
+return:
+  ret i32 0
+}
+
+; The store is redundant here, but currently we fail to eliminate it.
+; We are walking from the store up to the calloc and translate phis as
+; needed. In this case we fail to translate %p while going over the
+; backedge. Because of that we conservatively assume that zero initialized
+; memory is clobbered.
+define i32 @test42() {
+; CHECK-LABEL: @test42(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[M:%.*]] = call i8* @calloc(i32 9, i32 20)
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[CONT:%.*]] ]
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    br label [[CONT]]
+; CHECK:       cont:
+; CHECK-NEXT:    [[P:%.*]] = getelementptr inbounds i8, i8* [[M]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store i8 0, i8* [[P]]
+; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ugt i64 [[INDVARS_IV]], 15
+; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[RETURN:%.*]]
+; CHECK:       return:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %m = call i8* @calloc(i32 9, i32 20)
+  br label %loop
+loop:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %cont ]
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %cont
+
+cont:
+  %p = getelementptr inbounds i8, i8* %m, i64 %indvars.iv
+  store i8 0, i8* %p
+  %continue = icmp ugt i64 %indvars.iv, 15
+  br i1 %continue, label %loop, label %return
+
+return:
+  ret i32 0
+}
+
+define i32 @test43() {
+; CHECK-LABEL: @test43(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[M:%.*]] = call i8* @calloc(i32 9, i32 20)
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[CONT_2:%.*]] ]
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[P_NEXT:%.*]] = getelementptr inbounds i8, i8* [[M]], i64 [[INDVARS_IV_NEXT]]
+; CHECK-NEXT:    store i8 1, i8* [[P_NEXT]]
+; CHECK-NEXT:    br label [[CONT:%.*]]
+; CHECK:       cont:
+; CHECK-NEXT:    [[P:%.*]] = getelementptr inbounds i8, i8* [[M]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store i8 0, i8* [[P]]
+; CHECK-NEXT:    br label [[CONT_2]]
+; CHECK:       cont.2:
+; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ugt i64 [[INDVARS_IV]], 15
+; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[RETURN:%.*]]
+; CHECK:       return:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %m = call i8* @calloc(i32 9, i32 20)
+  br label %loop
+loop:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %cont.2 ]
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %p.next = getelementptr inbounds i8, i8* %m, i64 %indvars.iv.next
+  store i8 1, i8* %p.next
+  br label %cont
+
+cont:
+  %p = getelementptr inbounds i8, i8* %m, i64 %indvars.iv
+  store i8 0, i8* %p
+  br label %cont.2
+
+cont.2:
+  %continue = icmp ugt i64 %indvars.iv, 15
+  br i1 %continue, label %loop, label %return
+
+return:
+  ret i32 0
+}
+
+define i32 @test44() {
+; CHECK-LABEL: @test44(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[M:%.*]] = call i8* @calloc(i32 9, i32 20)
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[CONT_2:%.*]] ]
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[P_NEXT:%.*]] = getelementptr inbounds i8, i8* [[M]], i64 [[INDVARS_IV_NEXT]]
+; CHECK-NEXT:    [[P:%.*]] = getelementptr inbounds i8, i8* [[M]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store i8 0, i8* [[P]]
+; CHECK-NEXT:    br label [[CONT:%.*]]
+; CHECK:       cont:
+; CHECK-NEXT:    store i8 1, i8* [[P_NEXT]]
+; CHECK-NEXT:    br label [[CONT_2]]
+; CHECK:       cont.2:
+; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ugt i64 [[INDVARS_IV]], 15
+; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[RETURN:%.*]]
+; CHECK:       return:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %m = call i8* @calloc(i32 9, i32 20)
+  br label %loop
+loop:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %cont.2 ]
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %p.next = getelementptr inbounds i8, i8* %m, i64 %indvars.iv.next
+  %p = getelementptr inbounds i8, i8* %m, i64 %indvars.iv
+  store i8 0, i8* %p
+  br label %cont
+
+cont:
+  store i8 1, i8* %p.next
+  br label %cont.2
+
+cont.2:
+  %continue = icmp ugt i64 %indvars.iv, 15
+  br i1 %continue, label %loop, label %return
+
+return:
+  ret i32 0
+}
+
+; This is an example which can potentially benefit from PHI translation.
+; Current implementation doesn't handle this case though. This is because
+; we don't visit the same block with different addresses while looking for
+; clobbering instructions.
+define i32 @test45(i1 %c) {
+; CHECK-LABEL: @test45(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[M:%.*]] = call i8* @calloc(i32 9, i32 20)
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[TRUE:%.*]], label [[FALSE:%.*]]
+; CHECK:       true:
+; CHECK-NEXT:    [[P_1:%.*]] = getelementptr inbounds i8, i8* [[M]], i64 1
+; CHECK-NEXT:    store i8 1, i8* [[P_1]]
+; CHECK-NEXT:    br label [[CONT:%.*]]
+; CHECK:       false:
+; CHECK-NEXT:    [[P_2:%.*]] = getelementptr inbounds i8, i8* [[M]], i64 2
+; CHECK-NEXT:    store i8 1, i8* [[P_2]]
+; CHECK-NEXT:    br label [[CONT]]
+; CHECK:       cont:
+; CHECK-NEXT:    [[OFFSET:%.*]] = phi i64 [ 2, [[TRUE]] ], [ 1, [[FALSE]] ]
+; CHECK-NEXT:    [[P:%.*]] = getelementptr inbounds i8, i8* [[M]], i64 [[OFFSET]]
+; CHECK-NEXT:    store i8 0, i8* [[P]]
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       return:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %m = call i8* @calloc(i32 9, i32 20)
+  br i1 %c, label %true, label %false
+
+true:
+  %p.1 = getelementptr inbounds i8, i8* %m, i64 1
+  store i8 1, i8* %p.1
+  br label %cont
+
+false:
+  %p.2 = getelementptr inbounds i8, i8* %m, i64 2
+  store i8 1, i8* %p.2
+  br label %cont
+
+cont:
+  %offset = phi i64 [ 2, %true ], [ 1, %false ]
+  %p = getelementptr inbounds i8, i8* %m, i64 %offset
+  store i8 0, i8* %p
+  br label %return
+
+return:
+  ret i32 0
+}
+
+; This is test45 modified in a way to demonstrate PHI translation
+; improving the accuracy of the analysis (on a slightly convoluted
+; case though).
+define i32 @test46(i1 %c) {
+; CHECK-LABEL: @test46(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[M:%.*]] = call i8* @calloc(i32 9, i32 20)
+; CHECK-NEXT:    [[P_1:%.*]] = getelementptr inbounds i8, i8* [[M]], i64 1
+; CHECK-NEXT:    [[P_2:%.*]] = getelementptr inbounds i8, i8* [[M]], i64 2
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[TRUE:%.*]], label [[FALSE:%.*]]
+; CHECK:       true:
+; CHECK-NEXT:    store i8 1, i8* [[P_1]]
+; CHECK-NEXT:    br label [[CONT:%.*]]
+; CHECK:       false:
+; CHECK-NEXT:    store i8 1, i8* [[P_1]]
+; CHECK-NEXT:    br label [[CONT]]
+; CHECK:       cont:
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       return:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %m = call i8* @calloc(i32 9, i32 20)
+  %p.1 = getelementptr inbounds i8, i8* %m, i64 1
+  %p.2 = getelementptr inbounds i8, i8* %m, i64 2
+  br i1 %c, label %true, label %false
+
+true:
+  store i8 1, i8* %p.1
+  br label %cont
+
+false:
+  store i8 1, i8* %p.1
+  br label %cont
+
+cont:
+  %offset = phi i64 [ 2, %true ], [ 2, %false ]
+  %p = getelementptr inbounds i8, i8* %m, i64 %offset
+  store i8 0, i8* %p
+  br label %return
+
+return:
+  ret i32 0
+}
+
 declare void @llvm.memmove.p0i8.p0i8.i64(i8* nocapture, i8* nocapture readonly, i64, i1)
 declare void @llvm.memmove.element.unordered.atomic.p0i8.p0i8.i64(i8* nocapture, i8* nocapture readonly, i64, i32)