[RFC] Cross Block DSE

[karthikthecool]

Summary

Hi All,
I would like to propose a RFC on Cross Block Dead Store Elimination.

Cross Block Dead Store elimination implemented in this patch works as follows-

1. When a Store with non local memory dependency we call "handleNonLocalStoreDeletion".
2. In handleNonLocalStoreDeletion we traverse the predecessor blocks of the store instruction till we encounter post domination frontier and try to find a candidate store for deletion.
3. getStoreCandidates finds out if we have a candidate store for deletion which in any of the predecessor block.
4. If we find a candidate store we then see that the store is not used by any instruction in any of the path from the current block till block were the overwriting store is present.
5. We call DeleteDeadInstruction for the candidate store instruction if it is safe to remove the store.

No Regressions were found in make check-all and LLVM LNT test suites.

Please let me know your valuable option on the patch.

Thanks and Regards
Karthik Bhat

[karthikthecool]

Attaching LLVM LNT Test results.(15 Samples)
Execution time of 2 benchmarks improved post Cross block DSE patch. Surprisingly i didn't see any compile time regression.

[eastig]

lib/Transforms/Scalar/DeadStoreElimination.cpp

655

'nullptr' is returned when BB is not well formed. Maybe it's better to 'assert' here?

[eastig]

Karthik,

I don't know what was a reason to deprecate the DominanceFrontier class (see comments in DominanceFrontier.h). Your PostDominanceFrontier might be deprecated for the same reason.

[karthikthecool]

Hi Evgeny,
Thanks for looking into the patch. I think the reason dom frontier is deprecared is that it is costly to calculate the same.. im not sure as well though.
Im currently using postdom frontier to get the basic block boundry till which a store might overwrite a memory location making it dead. Dead store elimation without having postdom seems to be a bit tough especially given the overhead it would require without postdom.
Thanks
Karthik

[• dberlin]

First, If you want to calculate post-dom-frontier, you should use the
linear-time IDF calculator and make it work for postdominance
frontiers, and just calculate the pieces you want.

Second, this looks like a *really* expensive approach to doing this.

A. Is there a reason you aren't just using a hash table storing each
store you see in the top-down walk, so that you don't have to go
looking for stores to eliminate?
In fact, you can do better than even this:
Walk the function once, finding stores.
Store the stores in a linked list ordered by DFS in/out numbers of the
postdom tree.

For your given block, get the DFS in/out of that node in the postdom tree.
The stores you may be able to eliminate are those in the list starting
at DFS in and ending at DFS out.

Calculating the post-dom frontier just to figure out where to stop
looking seems remarkably expensive as well

(you could also just use memoryssa, once i finish my managery tasks
that have kept me busy the past month or two, and get back to llvm
work)

B. If you want complete store elimination, this is normally formulated
as a PRE-like problem on the reverse flowgraph.

[karthikthecool]

Hi Daniel,
Thanks for the input. Yes this approach is definitely very expensive. I was surprised when i didn't see any compile time regressions on LLVM LNT.
Your approach of using postdom and dfs in/out seems very interesting I will try out the same and update shortly.
Thanks for your valuable inputs. Will get back with the updated patch shortly.

Thanks and Regards
Karthik Bhat

[karthikthecool]

Hi Daniel,
Please find the updated patch as per your inputs. I have removed the dependency from PDT Frontier and using the DFS in/out on PDT to find the candidate store.

There are no regressions in make check-all and LLVM LNT.

I also compiled llvm with modified/unmodified clang binary to measure compile time overhead. Not much compile time overhead is observed. The rough figures are as shown below-

With Change-

real   35m42.705s
user  136m54.137s
sys    3m19.238s

Without Change-

real    35m38.747s
user   136m58.076s
sys     3m19.637s

In LLVM LNT we observe improvement in 2 benchmarks mentioned in the previous posts.

Please let me know your valuable inputs on the same.

Thanks and Regards
Karthik Bhat

[karthikthecool]

gentle ping..

[hfinkel]

lib/Transforms/Scalar/DeadStoreElimination.cpp

66

Use a DenseSet (I assume you're not depending on any ordering from std::map because it is storing pointers).

73

give -> given

76

You can use a range-based for loop here.

for (const auto &I : BB) {
  ...
}

87

Range-based for.

914

Use SmallVector<BasicBlock *, 16> (or some number you feel is appropriate).

915

Use DenseSet, or SmallPtrSet if the size will normally be small.

922

You don't need to do a cast here, you can compare a StoreInst* to an Instruction*, and they'll be equal only if they point to the same object (one is a base class of the other).

959

When you use a SmallVector instead, you can use pop_back_val().

986

Add space before 'Conservatively'

1000

Maybe you should store these in a SetVector instead to make this more efficient.

1008

finding out candidate stroes -> finding candidate stores

1022

Range-based for?

[karthikthecool]

Hi Hal,
Thanks for the review. Please find the updated patch addressing review comments.
Please let me know your opinion on the same.
Thanks and Regards
Karthik Bhat

[karthikthecool]

Hi All,
Update the patch to fix a failure in LLVM-LNT testcase on 32bit ubuntu. Unfortunetly i was not able to catch it on my 64bit machine.
This failure occured as we incorrectly deleted a store that was followed by a store that partially aliased it.
When seraching if a candidate store is safe we conservately mark a store as unsafe if we found a store that may/partially alias the candidate store.
This fixes failure found in LLVM LNT on 32bit ubuntu.
We still observe some 30%+ execution time improvement in MultiSource/Benchmarks/Trimaran/enc-pc1/enc-pc1.

Thanks and Regards
Karthik Bhat

[karthikthecool]

Gentle ping..

[hfinkel]

Danny, are you okay with the algorithm at this point?

lib/Transforms/Scalar/DeadStoreElimination.cpp

972

If I'm reading this correctly, this call to AA->alias is going to essentially re-do all of the same analysis done in the AA->getModRefInfo call above. Could we check whether I is a StoreInst first and only to one query on store instructions instead of two?

[karthikthecool]

Hi Hal,
Thanks for looking into the patch. Please find my comments inline.
Regards
Karthik Bhat

lib/Transforms/Scalar/DeadStoreElimination.cpp

972

Hi Hal,
The first check ensures that we see all instructions that may modify/ref a pointer (this is the pointer the store to which we are planning to delete). In case we find an instruction that refers to the pointer e.g. a load we then return false indicating that the store cannot be removed.

If the instruction is a store we can safely remove the 1st store if and only if both the store and the candidate MustAlias. To detect this i had to check the alias again.
Thanks and Regards
Karthik

[hfinkel]

lib/Transforms/Scalar/DeadStoreElimination.cpp

972

I understand that the interface here is less than ideal, but could you not skip the getModRefInfo call entirely if I is a StoreInst, and just use the result from AA->alias instead? In other words, hoist the dyn_cast<StoreInst>-based check above the ModRef logic?

[• dberlin]

LGTM with these comments

lib/Transforms/Scalar/DeadStoreElimination.cpp

82

Do you have a testcase for where PDT->getRootNode() is null?

because that seems broken :)

89

So, if we only have 1 block, why are you doing the rest of the work here, instead of returning false and exiting?
:)

530

Much like the one above, i don't understand why this PDT->getRootNode() check is here.

The PDT should always have a root node, fake or not.
If you've got cases it doesn't, it seems like we should fix PDT

972

As Karthik says, i'm not sure there is a way around this.
You can get better time bounds with PRE-like algorithms, but the underlying work here has to be done.

The getModRefInfo is like finding your data dependences. For stores they may not be mustalias. If they are mod/ref, they block removal because they may read or write the memory from the first store before the second store does the same thing, so you can't remove the first store.

IE given
Store of 1
Load of 1
Store of 1

You can't remove the first store.

(You could actually see if it's legal to sink everything below the second store to enable you to delete the first, but that is effectively global code motion. not hard, just a different algorithm with it's own issues. You could also see if it's possible to delete the second store instead of the first, but this is hard in the simple cross-block DSE we are doing here)

Same with
Store of 1
may-store of 1
Load of 1
Store of 1

Now, interestingly, given:

Store of 1
may-store of 1
Store of 1

You can still eliminate the first store.
In fact, i'm struggling to come up with a case where Mod without ref matters if you have a later mustalias store.
It's early, but i think it's safe to eliminate store over store with only a may-mod store in the way.

Karthik, do you have a counter-example?

If not, i'd expect the check on line 960 above to take this into account (IE be okay with nomodref and mod, but not ref or modref)

But as you can see, even if there is nothing "in the way" between the first and second store, you still have to check whether you *mustalias* the second store to know that you can remove the first one.

SSA based store-PRE algorithms basically do this "not on the fly". They build memory use chains so they don't have to walk blocks (sound familiar? :P). They still have to do the mod-ref checks and mustalias checks, however. They are just structured in a way that it is not N^2 to figure out placement.

[• dberlin]

Sigh, my review got drafted before, but submitted after you wrote
this, so it looks like a reply to this part.

You are right that you could hoist this check, IFF alias returns
must/mayalias in cases where getmodrefinfo returns mod.

Is this really guaranteed to be the case?

They are different properties, though modrefinfo is often implemented
with help from alias. In our world of synchronization instructions,
isn't it possible for ordering to cause something to not be aliased
with a store (which is about the abstract memory locations) but still
be modified by it (due to it being a release or whatever) ?

Or do we consider this aliasing in the AA interface to try to avoid
user confusion? :)

I haven't looked deeply enough to know if we truly have consistency
here. I know getModRefInfo performs checks on ordering, etc, before it
calls alias(), and i assumed those checks were actually necessary.
But, you know, not a lot of unit tests here :)

[karthikthecool]

Hi Daniel,Hal,
Thanks for the review. Please find my comments inline. I will try to upload the updated patch shortly.
Thanks and Regards
Karthik

lib/Transforms/Scalar/DeadStoreElimination.cpp

82

Hi Daniel,
I found in the below case we were getting getRootNode as NULL so added the above check.

void foo() {
  while(1);
}

89

Updated code to executed FindFunctionBackedges and BackEdgesMap population only if Count > 1. I think we cannot return false here because we still need to do single block dse.

[karthikthecool]

Hi All,
Rebased patch and implemented few review comments.
Please let me know your inputs on the same.
Thanks and Regards
Karthik Bhat

[• dberlin]

I think we should just fix the PDT in a separate patch, and remove this check.

The documentation for getRootNode says:
" /// getRootNode - This returns the entry node for the CFG of the
function. If

/// this tree represents the post-dominance relations for a

function, however,

/// this root may be a node with the block == NULL.  This is the case when
/// there are multiple exit nodes from a particular function.  Consumers of
/// post-dominance information must be capable of dealing with this
/// possibility."

Note: This may be a node with *block* == NULL, not that the root node
may be null.

The problem here is in PDT building.

GenericDomTreeConstruction does this:
if (TraitsTy::child_begin(I) == TraitsTy::child_end(I))

addRoot(I);

This is wrong, obviously, since in the case of an infinite loop like
you've shown, it will have a self-loop, but it is a root because there
is no exit.

This whole mechanism of trying to detect the roots is broken, in fact.
It's essentially trying to determine reachability without a DFS, which
is not possible in general.

The *only* correct way (i'm aware of) to determine which things need
to be children of artificial exit/a root is to DFS from all clear exit
blocks, and then, for anything still unvisited, DFS from each of them,
marking them as children of the artificial exit
(you could also reparent anything you reach that was marked as a
child of artificial exit , if we want to prefer anything over the
artificial exit as a parent. But this should not be necessary for
correct answers).

Please file a bug with your testcase and cc me, and i'l update the bug
with details.

(I'll see if i can find time to prepare a patch)

[karthikthecool]

Hi Daniel,
Thanks for the comments.. Filed a bug as
https://llvm.org/bugs/show_bug.cgi?id=24415 .
I too will try to have look at this issue seperatly.. Any other comments on this patch Daniel?
Thanks for your valuable time.
Regards
Karthik

[eeckstein]

Hi Karthik,
Daniel pointed me to your patch, because I'm also working on something in DeadStoreElimination: http://reviews.llvm.org/D11854

I think your patch is not directly related to what I'm doing. Nevertheless I looked at your patch and posted some comments.

Erik

lib/Transforms/Scalar/DeadStoreElimination.cpp

920

As I understand, this loop is just to get the iterator for I.
You can get it simply by:
BasicBlock::iterator BBI(SI);

930

I think using PtrSize here is wrong. It should be the size of the memory access. This can give you a wrong NoModRef, e.g. if I is a load of a global which has a smaller size than the pointer size.

Maybe you should just get the MemoryLocation of SI instead of Pointer+PtrSize and use AA->getModRefInfo(I, Location).

982

Why is a path with a backedge not safe?

[karthikthecool]

Hi Erik,
Thanks for looking into the patch. Please find my comments inline. Will post the updated patch shortly.
Thanks and Regards
Karthik Bhat

lib/Transforms/Scalar/DeadStoreElimination.cpp

920

Updated the code.

930

Thanks updated the code.

982

Hi Erik,
I came across the following code from MultiSource/Benchmarks/MiBench/consumer-typeset benchmark because of which i conservately added this check. The below .ll snippet is from file z36.c TrieRead function-

for.cond:                                         ; preds = %for.inc, %if.else.618
  %indvars.iv1644 = phi i64 [ %indvars.iv.next1645, %for.inc ], [ 0, %if.else.618 ]
  %j.0 = phi i32 [ %j.1, %for.inc ], [ 1, %if.else.618 ]
  %prev.0 = phi i32 [ %prev.1, %for.inc ], [ 56, %if.else.618 ]
  %arrayidx626 = getelementptr inbounds [512 x i8], [512 x i8]* %str, i64 0, i64 %indvars.iv1644
  %42 = load i8, i8* %arrayidx626, align 1, !tbaa !18
  switch i8 %42, label %if.else.636 [
    i8 0, label %for.end
    i8 45, label %for.inc
  ]

if.else.636:                                      ; preds = %for.cond
  %idxprom639 = sext i32 %j.0 to i64
  %arrayidx640 = getelementptr inbounds [512 x i8], [512 x i8]* %key, i64 0, i64 %idxprom639
  store i8 %42, i8* %arrayidx640, align 1, !tbaa !18
  %conv641 = trunc i32 %prev.0 to i8
  %inc642 = add nsw i32 %j.0, 1
  %arrayidx644 = getelementptr inbounds [512 x i8], [512 x i8]* %value, i64 0, i64 %idxprom639
  store i8 %conv641, i8* %arrayidx644, align 1, !tbaa !18
  br label %for.inc

for.inc:                                          ; preds = %for.cond, %if.else.636
  %j.1 = phi i32 [ %inc642, %if.else.636 ], [ %j.0, %for.cond ]
  %prev.1 = phi i32 [ 56, %if.else.636 ], [ 57, %for.cond ]
  %indvars.iv.next1645 = add nuw nsw i64 %indvars.iv1644, 1
  br label %for.cond

for.end:                                          ; preds = %for.cond
  %prev.0.lcssa = phi i32 [ %prev.0, %for.cond ]
  %j.0.lcssa = phi i32 [ %j.0, %for.cond ]
  %idxprom647 = sext i32 %j.0.lcssa to i64
  %arrayidx648 = getelementptr inbounds [512 x i8], [512 x i8]* %key, i64 0, i64 %idxprom647
  store i8 46, i8* %arrayidx648, align 1, !tbaa !18
  %conv649 = trunc i32 %prev.0.lcssa to i8
  %inc650 = add nsw i32 %j.0.lcssa, 1
  %arrayidx652 = getelementptr inbounds [512 x i8], [512 x i8]* %value, i64 0, i64 %idxprom647
  store i8 %conv649, i8* %arrayidx652, align 1, !tbaa !18
  %idxprom653 = sext i32 %inc650 to i64
  %arrayidx654 = getelementptr inbounds [512 x i8], [512 x i8]* %key, i64 0, i64 %idxprom653
  store i8 0, i8* %arrayidx654, align 1, !tbaa !18
  %arrayidx657 = getelementptr inbounds [512 x i8], [512 x i8]* %value, i64 0, i64 %idxprom653
  store i8 56, i8* %arrayidx657, align 1, !tbaa !18
  %add658 = add nsw i32 %j.0.lcssa, 2
  %idxprom659 = sext i32 %add658 to i64
  %arrayidx660 = getelementptr inbounds [512 x i8], [512 x i8]* %value, i64 0, i64 %idxprom659
  store i8 0, i8* %arrayidx660, align 1, !tbaa !18
  %call666 = call fastcc i32 @TrieInsert(i8* %5, i8* %6, %struct.trie_rec* %11, i8* %arraydecay, i32 %inc)
  %tobool667 = icmp eq i32 %call666, 0
  br i1 %tobool667, label %if.then.668, label %while.cond.224.backedge

Here block for.end post dominates if.else.636 and for.inc and alias analysis returns MustAlias for the pair-

store i8 %42, i8* %arrayidx640, align 1, !tbaa !18
and
store i8 46, i8* %arrayidx648, align 1, !tbaa !18

and

store i8 %conv649, i8* %arrayidx652, align 1, !tbaa !18
and
store i8 %conv641, i8* %arrayidx644, align 1, !tbaa !18

When we do a DFS from block if.else.636 to see if it is safe to delete the store we take a backedge and reach for.end were we find a MustAlias Store and hence delete the store in the block if.else.636. But this is incorrect as the store in if.else.636 is inside a loop and stores to various memory location based on the iterator which is updated in for.cond but the store in for.end: stores to a single location after the loop is executed.
I came across this issue during testing hence conservately added a check not to take backedges during DFS.
I'm not sure if there is any other way to fix this. Please let me know if you have any inputs on this. It would be of great help.
Thanks

[karthikthecool]

Updated patch as per Erik's comments.

[hfinkel]

lib/Transforms/Scalar/DeadStoreElimination.cpp

92

Range-based for

917

Line too long.

930

Line too long.

961

Line too long.

988

Remove this function and instead call:

DeadStores.count(SI)

1003

Line is too long.

1020

Line too long.

[hfinkel]

In D11143#217647, @dberlin wrote:

Sigh, my review got drafted before, but submitted after you wrote
this, so it looks like a reply to this part.

You are right that you could hoist this check, IFF alias returns
must/mayalias in cases where getmodrefinfo returns mod.

Is this really guaranteed to be the case?

I think that it should be. I'm not the best with the history here, but there's nothing in the comments on the interface that suggests that there should be a difference w.r.t. ordering/volatile of the instructions, and other clients, MemoryDependenceAnalysis for example, layer on their own checks for ordering/volatile.

They are different properties, though modrefinfo is often implemented
with help from alias. In our world of synchronization instructions,
isn't it possible for ordering to cause something to not be aliased
with a store (which is about the abstract memory locations) but still
be modified by it (due to it being a release or whatever) ?

There are certainly ordering constraints to preserve, but I don't believe that AA is the right place to enforce them. Clients can certainly bail on atomics, and should if they might disturb the ordering and can't do better, but optimizations on atomics are still possible and we don't want AA clients that can handle some optimizations on some atomics to need to work around the AA interface because it forces a conservative behavior.

So this is the wrong thread to fix this problem ;) -- but I don't think adding any new dependence on this behavior is a good thing.

Or do we consider this aliasing in the AA interface to try to avoid
user confusion? :)

I haven't looked deeply enough to know if we truly have consistency
here. I know getModRefInfo performs checks on ordering, etc, before it
calls alias(), and i assumed those checks were actually necessary.
But, you know, not a lot of unit tests here :)

Indeed I know :)

[karthikthecool]

Run clang-format on updated patch and implement Hal's review comments.
I agree with Hal that we may hoist dyn_cast<StoreInst> above ModRef check. In case of store we can rely on Alias Analysis's alias to check if the stores mustalias. For other cases we can use getModRefInfo to make make sure that this instruction which is not a store does not Mod/Ref the pointer. Updated and tested the code after modification.
Please let me know your inputs on the same.

Thanks once again to all reviewers for spending their valuable time on this patch.
Regards
Karthik Bhat

[karthikthecool]

Sorry guys for multiple updates on patch..:( forgot to move dyn_cast<StoreInst> above getModRefInfo in one of the place in the previous patch.
Regards
Karthik Bhat

[eeckstein]

lib/Transforms/Scalar/DeadStoreElimination.cpp

930

This is still not correct. You are passing the size of the pointer and not of the referenced memory location.

982

Thanks, I see the problem.

[karthikthecool]

Updated patch as per Erik's comments.
Thanks and Regards
Karthik Bhat

[karthikthecool]

Rebase patch and resolve confilts.
LNT Statistics:
Number of Cross Block Stores eliminated in LLVM-LNT: 849
Number of Benchmarks improved: 2

MultiSource/Benchmarks/Trimaran/enc-pc1/enc-pc1 : 38.86%
MultiSource/Benchmarks/mafft/pairlocalalign : 5.36%

No Regressions observed.

Hi Hal,Erik,Daniel,
Please let me know if you have any additional comments or if i can go ahead with committing this patch.
Thanks and Regards
Karthik Bhat

[hfinkel]

LGTM.

lib/Transforms/Scalar/DeadStoreElimination.cpp

974

Missing space after period.

include/llvm/Analysis/PostDominators.h

 // This file exposes interfaces to post dominance information.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_POSTDOMINATORS_H
 #define LLVM_ANALYSIS_POSTDOMINATORS_H
 
 #include "llvm/IR/Dominators.h"
-
+#include "llvm/Analysis/DominanceFrontier.h"
 namespace llvm {
 
 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
 /// compute the post-dominator tree.
 ///
 struct PostDominatorTree : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
   DominatorTreeBase<BasicBlock>* DT;
else
       return df_end(getEntryNode(N));
   }
 
   static nodes_iterator nodes_end(PostDominatorTree *N) {
     return df_end(getEntryNode(N));
   }
 };
 
+template <class BlockT>
+class ForwardPostDominanceFrontierBase : public DominanceFrontierBase<BlockT> {
+private:
+  typedef GraphTraits<BlockT *> BlockTraits;
+
+public:
+  typedef DominatorTreeBase<BlockT> DomTreeT;
+  typedef DomTreeNodeBase<BlockT> DomTreeNodeT;
+  typedef typename DominanceFrontierBase<BlockT>::DomSetType DomSetType;
+
+  ForwardPostDominanceFrontierBase() : DominanceFrontierBase<BlockT>(true) {}
+
+  void analyze(PostDominatorTree &DT) {
+    this->Roots = DT.getRoots();
+    if (const DomTreeNode *Root = DT.getRootNode())
+      calculate(DT, Root);
+  }
+
+  const DomSetType &calculate(const PostDominatorTree &DT,
+                              const DomTreeNodeT *Node);
+};
+
+template <class BlockT>
+const typename ForwardPostDominanceFrontierBase<BlockT>::DomSetType &
+ForwardPostDominanceFrontierBase<BlockT>::calculate(const PostDominatorTree &DT,
+                                                    const DomTreeNodeT *Node) {
+  // Loop over CFG successors to calculate DFlocal[Node]
+  BasicBlock *BB = Node->getBlock();
+  DomSetType &S = this->Frontiers[BB]; // The new set to fill in...
+  if (this->getRoots().empty())
+    return S;
+
+  if (BB)
+    for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB); SI != SE; ++SI) {
+      BasicBlock *P = *SI;
+      // Does Node immediately dominate this predecessor?
+      DomTreeNode *SINode = DT[P];
+      if (SINode && SINode->getIDom() != Node)
+        S.insert(P);
+    }
+
+  // At this point, S is DFlocal.  Now we union in DFup's of our children...
+  // Loop through and visit the nodes that Node immediately dominates (Node's
+  // children in the IDomTree)
+  //
+  for (DomTreeNode::const_iterator NI = Node->begin(), NE = Node->end();
+       NI != NE; ++NI) {
+    DomTreeNode *IDominee = *NI;
+    const DomSetType &ChildDF = calculate(DT, IDominee);
+
+    typename DomSetType::const_iterator CDFI = ChildDF.begin(),
+                                        CDFE = ChildDF.end();
+    for (; CDFI != CDFE; ++CDFI) {
+      if (!DT.properlyDominates(Node, DT[*CDFI]))
+        S.insert(*CDFI);
+    }
+  }
+
+  return S;
+}
+
+class PostDominanceFrontier : public FunctionPass {
+  ForwardPostDominanceFrontierBase<BasicBlock> Base;
+
+public:
+  typedef DominatorTreeBase<BasicBlock> DomTreeT;
+  typedef DomTreeNodeBase<BasicBlock> DomTreeNodeT;
+  typedef typename DominanceFrontierBase<BasicBlock>::DomSetType DomSetType;
+  typedef DominanceFrontierBase<BasicBlock>::iterator iterator;
+  typedef DominanceFrontierBase<BasicBlock>::const_iterator const_iterator;
+
+  static char ID; // Pass ID, replacement for typeid
+  PostDominanceFrontier();
+  ForwardPostDominanceFrontierBase<BasicBlock> &getBase() { return Base; }
+
+  inline const std::vector<BasicBlock *> &getRoots() const {
+    return Base.getRoots();
+  }
+
+  BasicBlock *getRoot() const { return Base.getRoot(); }
+
+  bool isPostDominator() const { return Base.isPostDominator(); }
+  iterator begin() { return Base.begin(); }
+  const_iterator begin() const { return Base.begin(); }
+
+  iterator end() { return Base.end(); }
+
+  const_iterator end() const { return Base.end(); }
+
+  iterator find(BasicBlock *B) { return Base.find(B); }
+
+  const_iterator find(BasicBlock *B) const { return Base.find(B); }
+
+  iterator addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
+    return Base.addBasicBlock(BB, frontier);
+  }
+
+  void removeBlock(BasicBlock *BB) { return Base.removeBlock(BB); }
+
+  void addToFrontier(iterator I, BasicBlock *Node) {
+    return Base.addToFrontier(I, Node);
+  }
+
+  void removeFromFrontier(iterator I, BasicBlock *Node) {
+    return Base.removeFromFrontier(I, Node);
+  }
+
+  bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const {
+    return Base.compareDomSet(DS1, DS2);
+  }
+
+  bool compare(DominanceFrontierBase<BasicBlock> &Other) const {
+    return Base.compare(Other);
+  }
+
+  void releaseMemory() override;
+
+  bool runOnFunction(Function &) override;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+};
+FunctionPass *createPostDomFrontier();
+EXTERN_TEMPLATE_INSTANTIATION(class DominanceFrontierBase<BasicBlock>);
+EXTERN_TEMPLATE_INSTANTIATION(class ForwardDominanceFrontierBase<BasicBlock>);
 } // End llvm namespace
 
 #endif

include/llvm/InitializePasses.h

 void initializePEIPass(PassRegistry&);
 void initializePHIEliminationPass(PassRegistry&);
 void initializePartialInlinerPass(PassRegistry&);
 void initializePeepholeOptimizerPass(PassRegistry&);
 void initializePostDomOnlyPrinterPass(PassRegistry&);
 void initializePostDomOnlyViewerPass(PassRegistry&);
 void initializePostDomPrinterPass(PassRegistry&);
 void initializePostDomViewerPass(PassRegistry&);
+void initializePostDominanceFrontierPass(PassRegistry &);
 void initializePostDominatorTreePass(PassRegistry&);
 void initializePostRASchedulerPass(PassRegistry&);
 void initializePostMachineSchedulerPass(PassRegistry&);
 void initializePrintFunctionPassWrapperPass(PassRegistry&);
 void initializePrintModulePassWrapperPass(PassRegistry&);
 void initializePrintBasicBlockPassPass(PassRegistry&);
 void initializeProcessImplicitDefsPass(PassRegistry&);
 void initializePromotePassPass(PassRegistry&);

include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createConstantHoistingPass();
       (void) llvm::createCodeGenPreparePass();
       (void) llvm::createEarlyCSEPass();
       (void) llvm::createMergedLoadStoreMotionPass();
       (void) llvm::createGVNPass();
       (void) llvm::createMemCpyOptPass();
       (void) llvm::createLoopDeletionPass();
       (void) llvm::createPostDomTree();
+      (void)llvm::createPostDomFrontier();
       (void) llvm::createInstructionNamerPass();
       (void) llvm::createMetaRenamerPass();
       (void) llvm::createFunctionAttrsPass();
       (void) llvm::createMergeFunctionsPass();
       (void) llvm::createPrintModulePass(*(llvm::raw_ostream*)nullptr);
       (void) llvm::createPrintFunctionPass(*(llvm::raw_ostream*)nullptr);
       (void) llvm::createPrintBasicBlockPass(*(llvm::raw_ostream*)nullptr);
       (void) llvm::createModuleDebugInfoPrinterPass();

lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeLibCallAliasAnalysisPass(Registry);
   initializeLintPass(Registry);
   initializeLoopInfoWrapperPassPass(Registry);
   initializeMemDepPrinterPass(Registry);
   initializeMemDerefPrinterPass(Registry);
   initializeMemoryDependenceAnalysisPass(Registry);
   initializeModuleDebugInfoPrinterPass(Registry);
   initializePostDominatorTreePass(Registry);
+  initializePostDominanceFrontierPass(Registry);
   initializeRegionInfoPassPass(Registry);
   initializeRegionViewerPass(Registry);
   initializeRegionPrinterPass(Registry);
   initializeRegionOnlyViewerPass(Registry);
   initializeRegionOnlyPrinterPass(Registry);
   initializeScalarEvolutionPass(Registry);
   initializeScalarEvolutionAliasAnalysisPass(Registry);
   initializeTargetTransformInfoWrapperPassPass(Registry);

lib/Analysis/PostDominators.cpp

 
 #define DEBUG_TYPE "postdomtree"
 
 //===----------------------------------------------------------------------===//
 //  PostDominatorTree Implementation
 //===----------------------------------------------------------------------===//
 
 char PostDominatorTree::ID = 0;
+char PostDominanceFrontier::ID = 0;
 INITIALIZE_PASS(PostDominatorTree, "postdomtree",
                 "Post-Dominator Tree Construction", true, true)
 
 bool PostDominatorTree::runOnFunction(Function &F) {
   DT->recalculate(F);
   return false;
 }
 
 PostDominatorTree::~PostDominatorTree() {
   delete DT;
 }
 
 void PostDominatorTree::print(raw_ostream &OS, const Module *) const {
   DT->print(OS);
 }
 
 
 FunctionPass* llvm::createPostDomTree() {
   return new PostDominatorTree();
 }
 
+//===----------------------------------------------------------------------===//
+//  PostDominanceFrontier Implementation
+//===----------------------------------------------------------------------===//
+
+INITIALIZE_PASS_BEGIN(PostDominanceFrontier, "postdomfrontier",
+                      "Post-Dominance Frontier Construction", true, true)
+INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
+INITIALIZE_PASS_END(PostDominanceFrontier, "postdomfrontier",
+                    "Post-Dominance Frontier Construction", true, true)
+
+FunctionPass *llvm::createPostDomFrontier() {
+  return new PostDominanceFrontier();
+}
+
+PostDominanceFrontier::PostDominanceFrontier() : FunctionPass(ID), Base() {
+  initializeDominanceFrontierPass(*PassRegistry::getPassRegistry());
+}
+
+void PostDominanceFrontier::releaseMemory() { Base.releaseMemory(); }
+
+bool PostDominanceFrontier::runOnFunction(Function &) {
+  releaseMemory();
+  Base.analyze(getAnalysis<PostDominatorTree>());
+  return false;
+}
+
+void PostDominanceFrontier::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+  AU.addRequired<PostDominatorTree>();
+}

lib/Transforms/Scalar/DeadStoreElimination.cpp

 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/Local.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Analysis/CFG.h"
+#include <stack>
+
 using namespace llvm;
 
 #define DEBUG_TYPE "dse"
 
 STATISTIC(NumFastStores, "Number of stores deleted");
 STATISTIC(NumFastOther , "Number of other instrs removed");
 
 namespace {
   struct DSE : public FunctionPass {
     AliasAnalysis *AA;
     MemoryDependenceAnalysis *MD;
     DominatorTree *DT;
+    PostDominanceFrontier *PDF;
     const TargetLibraryInfo *TLI;
-
+    SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 32>
+        BackEdges;
+    std::map<std::pair<const BasicBlock *, const BasicBlock *>, bool>
+        BackEdgesMap;
     static char ID; // Pass identification, replacement for typeid
-    DSE() : FunctionPass(ID), AA(nullptr), MD(nullptr), DT(nullptr) {
+    DSE()
+        : FunctionPass(ID), AA(nullptr), MD(nullptr), DT(nullptr),
+          PDF(nullptr) {
       initializeDSEPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override {
       if (skipOptnoneFunction(F))
         return false;
 
       AA = &getAnalysis<AliasAnalysis>();
       MD = &getAnalysis<MemoryDependenceAnalysis>();
       DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
       TLI = AA->getTargetLibraryInfo();
+      PDF = &getAnalysis<PostDominanceFrontier>();
 
       bool Changed = false;
+      FindFunctionBackedges(F, BackEdges);
+      for (unsigned i = 0, e = BackEdges.size(); i != e; ++i)
+        BackEdgesMap[BackEdges[i]] = true;
+
       for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
         // Only check non-dead blocks.  Dead blocks may have strange pointer
         // cycles that will confuse alias analysis.
         if (DT->isReachableFromEntry(I))
           Changed |= runOnBasicBlock(*I);
 
       AA = nullptr; MD = nullptr; DT = nullptr;
       return Changed;
     }
 
     bool runOnBasicBlock(BasicBlock &BB);
     bool HandleFree(CallInst *F);
     bool handleEndBlock(BasicBlock &BB);
     void RemoveAccessedObjects(const MemoryLocation &LoadedLoc,
                                SmallSetVector<Value *, 16> &DeadStackObjects,
                                const DataLayout &DL);
 
+    void handleNonLocalStoreDeletion(StoreInst *SI);
+    StoreInst *getStoreCandidates(BasicBlock *B, StoreInst *SI);
+    bool dfsCandidateBlock(BasicBlock *SrcBlock, BasicBlock *SinkBlock,
+                           StoreInst *SI);
+
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesCFG();
       AU.addRequired<DominatorTreeWrapperPass>();
       AU.addRequired<AliasAnalysis>();
       AU.addRequired<MemoryDependenceAnalysis>();
+      AU.addRequired<PostDominanceFrontier>();
+      AU.addRequired<PostDominatorTree>();
       AU.addPreserved<AliasAnalysis>();
       AU.addPreserved<DominatorTreeWrapperPass>();
       AU.addPreserved<MemoryDependenceAnalysis>();
+      AU.addPreserved<PostDominanceFrontier>();
+      AU.addPreserved<PostDominatorTree>();
     }
   };
 }
 
 char DSE::ID = 0;
 INITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis)
+INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
+INITIALIZE_PASS_DEPENDENCY(PostDominanceFrontier)
 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 INITIALIZE_PASS_END(DSE, "dse", "Dead Store Elimination", false, false)
 
 FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); }
 
 //===----------------------------------------------------------------------===//
 // Helper functions
 //===----------------------------------------------------------------------===//

 
 
 //===----------------------------------------------------------------------===//
 // DSE Pass
 //===----------------------------------------------------------------------===//
 
 bool DSE::runOnBasicBlock(BasicBlock &BB) {
   bool MadeChange = false;
-
   // Do a top-down walk on the BB.
   for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
     Instruction *Inst = BBI++;
 
     // Handle 'free' calls specially.
     if (CallInst *F = isFreeCall(Inst, TLI)) {
       MadeChange |= HandleFree(F);
       continue;
     }
 
     // If we find something that writes memory, get its memory dependence.
     if (!hasMemoryWrite(Inst, TLI))
       continue;
 
     MemDepResult InstDep = MD->getDependency(Inst);
 
-    // Ignore any store where we can't find a local dependence.
-    // FIXME: cross-block DSE would be fun. :)
-    if (!InstDep.isDef() && !InstDep.isClobber())
+    if (!InstDep.isDef() && !InstDep.isClobber() && !InstDep.isNonLocal())
+      continue;
+    if (InstDep.isNonLocal()) {
+      if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
+        handleNonLocalStoreDeletion(SI);
+      }
       continue;
+    }
 
     // If we're storing the same value back to a pointer that we just
     // loaded from, then the store can be removed.
     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
       if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) {
         if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
             SI->getOperand(0) == DepLoad && isRemovable(SI)) {
           DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n  "
while (InstDep.isDef() || InstDep.isClobber()) {
         break;
 
       InstDep = MD->getPointerDependencyFrom(Loc, false, DepWrite, &BB);
     }
   }
 
   // If this block ends in a return, unwind, or unreachable, all allocas are
   // dead at its end, which means stores to them are also dead.
-  if (BB.getTerminator()->getNumSuccessors() == 0)
+  if (TerminatorInst *TI = BB.getTerminator())
+    if (TI->getNumSuccessors() == 0)
       MadeChange |= handleEndBlock(BB);
 
   return MadeChange;
 }
 
 /// Find all blocks that will unconditionally lead to the block BB and append
 /// them to F.
 static void FindUnconditionalPreds(SmallVectorImpl<BasicBlock *> &Blocks,
                                    BasicBlock *BB, DominatorTree *DT) {
void DSE::RemoveAccessedObjects(const MemoryLocation &LoadedLoc,
   // Remove objects that could alias LoadedLoc.
   DeadStackObjects.remove_if([&](Value *I) {
     // See if the loaded location could alias the stack location.
     MemoryLocation StackLoc(I,
                             getPointerSize(I, DL, AA->getTargetLibraryInfo()));
     return !AA->isNoAlias(StackLoc, LoadedLoc);
   });
 }
+
+// Check all paths from the SrcBlock till SinkBlock to see if Store SI is
+// safe to be remove.
+// Returns true if the candidate store SI is safe to delete else returns false
+bool DSE::dfsCandidateBlock(BasicBlock *SrcBlock, BasicBlock *SinkBlock,
+                            StoreInst *SI) {
+  std::stack<BasicBlock *> Stck;
+  std::map<BasicBlock *, bool> Visited;
+  Value *Pointer = SI->getPointerOperand();
+  uint64_t PtrSize = AA->getTypeStoreSize(Pointer->getType());
+  for (succ_iterator I = succ_begin(SrcBlock), E = succ_end(SrcBlock); I != E;
+       ++I) {
+    if (!Visited[*I]) {
+      Stck.push(*I);
+      Visited[*I] = true;
+    }
+  }
+  while (!Stck.empty()) {
+    BasicBlock *B = Stck.top();
+    Stck.pop();
+    auto BI = B->begin();
+    auto BE = B->end();
+    for (; BI != BE; ++BI) {
+      Instruction *I = BI;
+      AliasAnalysis::ModRefResult Res = AA->getModRefInfo(I, Pointer, PtrSize);
+      if (Res != AliasAnalysis::NoModRef) {
+        if (StoreInst *CSI = dyn_cast<StoreInst>(I)) {
+          Value *MemPtr = CSI->getPointerOperand();
+          uint64_t MemSize = AA->getTypeStoreSize(MemPtr->getType());
+          AliasResult R = AA->alias(Pointer, PtrSize, MemPtr, MemSize);
+          if (R == MustAlias)
+            break;
+          else
+            continue;
+        }
+        return false;
+      }
+    }
+    if (B == SinkBlock || BI != BE)
+      continue;
+    for (succ_iterator I = succ_begin(B), E = succ_end(B); I != E; ++I) {
+      if (!Visited[*I]) {
+        Stck.push(*I);
+        Visited[*I] = true;
+      }
+    }
+  }
+  return true;
+}
+
+// Given a Store instruction SI find it Block B has potential candidate store
+// for deletion.
+StoreInst *DSE::getStoreCandidates(BasicBlock *B, StoreInst *SI) {
+  Value *Pointer = SI->getPointerOperand();
+  uint64_t PtrSize = AA->getTypeStoreSize(Pointer->getType());
+  for (auto BI = B->end(), BE = B->begin(); BI != BE;) {
+    Instruction *I = --BI;
+    AliasAnalysis::ModRefResult Res = AA->getModRefInfo(I, Pointer, PtrSize);
+    if (Res != AliasAnalysis::NoModRef) {
+      if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
+        Value *MemPtr = SI->getPointerOperand();
+        uint64_t MemSize = AA->getTypeStoreSize(MemPtr->getType());
+        AliasResult R = AA->alias(Pointer, PtrSize, MemPtr, MemSize);
+        if (R == MustAlias) {
+          return SI;
+        } else if (R == NoAlias) {
+          continue;
+        }
+      }
+      return nullptr;
+    }
+  }
+  return nullptr;
+}
+
+// Function to handle non-local dead stores.
+// This routine checks all predecessor blocks till post dom frontier to find
+// potential candidate for dead store elimination.
+void DSE::handleNonLocalStoreDeletion(StoreInst *SI) {
+
+  BasicBlock *BB = SI->getParent();
+  DominanceFrontier::const_iterator it = PDF->find(BB);
+  if (it == PDF->end())
+    return;
+
+  const DominanceFrontier::DomSetType &S = it->second;
+  std::map<BasicBlock *, bool> Visited;
+  std::stack<BasicBlock *> BBStack;
+  BBStack.push(BB);
+  Visited[BB] = true;
+  while (!BBStack.empty()) {
+    BasicBlock *CurrBlock = BBStack.top();
+    BBStack.pop();
+    for (pred_iterator I = pred_begin(CurrBlock), E = pred_end(CurrBlock);
+         I != E; ++I) {
+      BasicBlock *B = *I;
+      if (Visited[B])
+        continue;
+      if (S.find(B) != S.end())
+        continue;
+      if (BackEdgesMap[std::make_pair(B, CurrBlock)])
+        continue;
+      StoreInst *CandidateSI = getStoreCandidates(B, SI);
+      if (CandidateSI) {
+        bool IsSafe = dfsCandidateBlock(B, BB, SI);
+        if (!IsSafe)
+          continue;
+        DeleteDeadInstruction(CandidateSI, *MD, TLI);
+      }
+      BBStack.push(B);
+      Visited[B] = true;
+    }
+  }
+}

test/Transforms/DeadStoreElimination/cross_block_dse.ll

+; RUN: opt < %s -basicaa -dse -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@x = common global i32 0
+@y = common global i32 0
+
+define void @test_01(i32 %N) {
+  %1 = alloca i32
+  store i32 %N, i32* %1
+  store i32 10, i32* @x
+  %2 = load i32, i32* %1
+  %3 = icmp ne i32 %2, 0
+  br i1 %3, label %4, label %5
+
+; <label>:4
+  store i32 5, i32* @x
+  br label %5
+
+; <label>:5
+  store i32 15, i32* @x
+  ret void
+}
+; CHECK-LABEL: @test_01(
+; CHECK-NOT: store i32 10, i32* @x
+; CHECK-NOT: store i32 5, i32* @x
+; CHECK: store i32 15, i32* @x
+
+
+define void @test_02(i32 %N) {
+  %1 = alloca i32
+  store i32 %N, i32* %1
+  store i32 10, i32* @x
+  %2 = load i32, i32* %1
+  %3 = icmp ne i32 %2, 0
+  br i1 %3, label %4, label %5
+
+; <label>:4
+  store i32 5, i32* @x
+  br label %7
+
+; <label>:5
+  %6 = load i32, i32* @x
+  store i32 %6, i32* @y
+  br label %7
+
+; <label>:7
+  store i32 15, i32* @x
+  ret void
+}
+; CHECK-LABEL: @test_02(
+; CHECK: store i32 10, i32* @x
+; CHECK-NOT: store i32 5, i32* @x
+; CHECK: store i32 %6, i32* @y
+
+
+define void @test_03(i32 %N) #0 {
+  %1 = alloca i32
+  store i32 %N, i32* %1
+  store i32 10, i32* @x
+  %2 = load i32, i32* %1
+  %3 = icmp ne i32 %2, 0
+  br i1 %3, label %4, label %6
+
+; <label>:4                                       ; preds = %0
+  %5 = load i32, i32* @x
+  store i32 %5, i32* @y
+  br label %6
+
+; <label>:6                                       ; preds = %4, %0
+  store i32 15, i32* @x
+  ret void
+}
+; CHECK-LABEL: @test_03(
+; CHECK: store i32 10, i32* @x
+; CHECK: store i32 %5, i32* @y
+; CHECK: store i32 15, i32* @x

test/Transforms/DeadStoreElimination/cross_block_dse_loop.ll

+; RUN: opt < %s -basicaa -dse -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@A = common global [100 x i32] zeroinitializer, align 16
+@x = common global i32 0
+
+; Negative Test case-
+;void foo(int N) {
+;  A[0] = N;
+;  for(int i=0;i<N;++i)
+;    A[i]+=i;
+;  A[0] = 10;
+;}
+;; Stores should not be optimized away.
+
+define void @test_01(i32 %N) #0 {
+  %1 = alloca i32
+  %i = alloca i32
+  store i32 %N, i32* %1
+  %2 = load i32, i32* %1
+  store i32 %2, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i64 0)
+  store i32 0, i32* %i
+  br label %3
+
+; <label>:3                                       ; preds = %14, %0
+  %4 = load i32, i32* %i
+  %5 = load i32, i32* %1
+  %6 = icmp slt i32 %4, %5
+  br i1 %6, label %7, label %17
+
+; <label>:7                                       ; preds = %3
+  %8 = load i32, i32* %i
+  %9 = load i32, i32* %i
+  %10 = sext i32 %9 to i64
+  %11 = getelementptr inbounds [100 x i32], [100 x i32]* @A, i32 0, i64 %10
+  %12 = load i32, i32* %11
+  %13 = add nsw i32 %12, %8
+  store i32 %13, i32* %11
+  br label %14
+
+; <label>:14                                      ; preds = %7
+  %15 = load i32, i32* %i
+  %16 = add nsw i32 %15, 1
+  store i32 %16, i32* %i
+  br label %3
+
+; <label>:17                                      ; preds = %3
+  store i32 10, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i64 0)
+  ret void
+}
+; CHECK-LABEL: @test_01(
+; CHECK: store i32 %2, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i64 0)
+; CHECK: store i32 %13, i32* %11
+; CHECK: store i32 10, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i64 0)
+
+
+; Postive Test case-
+;void foo(int N) {
+;  A[0] = N;
+;  for(int i=0;i<N;++i)
+;    A[i]=i;
+;  A[0] = 10;
+;}
+;; Stores should not be optimized away.
+define void @test_02(i32 %N) #0 {
+  %1 = alloca i32
+  %i = alloca i32
+  store i32 %N, i32* %1
+  %2 = load i32, i32* %1
+  store i32 %2, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i64 0)
+  store i32 0, i32* %i
+  br label %3
+
+; <label>:3                                       ; preds = %12, %0
+  %4 = load i32, i32* %i
+  %5 = load i32, i32* %1
+  %6 = icmp slt i32 %4, %5
+  br i1 %6, label %7, label %15
+
+; <label>:7                                       ; preds = %3
+  %8 = load i32, i32* %i
+  %9 = load i32, i32* %i
+  %10 = sext i32 %9 to i64
+  %11 = getelementptr inbounds [100 x i32], [100 x i32]* @A, i32 0, i64 %10
+  store i32 %8, i32* %11
+  br label %12
+
+; <label>:12                                      ; preds = %7
+  %13 = load i32, i32* %i
+  %14 = add nsw i32 %13, 1
+  store i32 %14, i32* %i
+  br label %3
+
+; <label>:15                                      ; preds = %3
+  store i32 10, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i64 0)
+  ret void
+}
+
+; CHECK-LABEL: @test_02(
+; CHECK-NOT: store i32 %2, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i64 0)
+; CHECK: store i32 %7, i32* %10
+; CHECK: store i32 10, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i64 0)
+
+