[WIP][DSE] Add basic cross-block dse pass using MemorySSA

[Tyker]

Summary

This patch add a cross-block dead store elimination pass that eliminate stores.
This pass work by detecting if a store is observable. this detection has 2 phases. the first phase is a search through the MemorySSA graph for loads or end of function. if on all path in the memssa graph hit a store before they hit a load. if the first phase didn't find any use we passe to the second phase which check if an optimization barrier (throw, fence ...) is reachable between the "dead" store and a killing store. and that all killing store together post-dominate the "dead" store. this pass also has a special case for non-escaping pointers on which we can consider end of function as a killer.

todo in the patch:

• improve the test suite.

todo probably in separate patchs:

• measure and tune for compile time impact.
• fix the many todos in code.
• handle builtin / library functions.
• deal with store merging.

todo maybe:

• improve the pass to deal with partial overwrites.

for a meta build of check-llvm + check-clang here is the stats:

• sum of dse.* transformation old: 145k this: 202k
• sum of dse.NumFastStores old: 98k this: 174k

this patch was inspired by D40480
i wasn't planning to post it for review before i improved test but i saw D72146 and we probably should probably try to collaborate.

[Tyker]

improved the test suite.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 // traversal.  Doing so would be pretty trivial.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/DeadStoreElimination.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Analysis/MemoryLocation.h"
+#include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/OrderedBasicBlock.h"
+#include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking",
   cl::init(true), cl::Hidden,
   cl::desc("Enable partial-overwrite tracking in DSE"));
 
 static cl::opt<bool>
 EnablePartialStoreMerging("enable-dse-partial-store-merging",
   cl::init(true), cl::Hidden,
   cl::desc("Enable partial store merging in DSE"));
 
+static cl::opt<bool>
+    EnableMemorySSA("enable-dse-memoryssa", cl::init(false), cl::Hidden,
+                    cl::desc("Use the new MemorySSA-backed DSE."));
+
+static cl::opt<unsigned>
+    MaxDSEIteration("dse-max-iteration", cl::init(24), cl::Hidden,
+                    cl::desc("Maximum number of iteration for graph traversal "
+                             "operation inside MemorySSA-backed DSE"));
+
 //===----------------------------------------------------------------------===//
 // Helper functions
 //===----------------------------------------------------------------------===//
 using OverlapIntervalsTy = std::map<int64_t, int64_t>;
 using InstOverlapIntervalsTy = DenseMap<Instruction *, OverlapIntervalsTy>;
 
 /// Delete this instruction.  Before we do, go through and zero out all the
 /// operands of this instruction.  If any of them become dead, delete them and
for (BasicBlock &BB : F)
     // Only check non-dead blocks.  Dead blocks may have strange pointer
     // cycles that will confuse alias analysis.
     if (DT->isReachableFromEntry(&BB))
       MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI);
 
   return MadeChange;
 }
 
+namespace {
+
+bool isIncomplete(MemoryLocation Loc) { return !Loc.Ptr; }
+
+/// Check if I is a volatile operation.
+/// FIXME: Maybe this should be moved to Value.
+bool isVolatile(Instruction *I) {
+  if (auto *SI = dyn_cast<StoreInst>(I))
+    return SI->isVolatile();
+  if (auto *LI = dyn_cast<LoadInst>(I))
+    return LI->isVolatile();
+  if (auto *MemOp = dyn_cast<AnyMemIntrinsic>(I))
+    return MemOp->isVolatile();
+  return false;
+}
+
+struct DSEContext {
+  Function &F;
+  AliasAnalysis &AA;
+  MemorySSA &MSSA;
+  DominatorTree &DT;
+  PostDominatorTree &PDT;
+  const TargetLibraryInfo &TLI;
+  bool MadeChange = false;
+
+  /// Index associated of an instruction. it can be used to know the ordering of
+  /// instruction in a basic block. indexes are in reverse order.
+  using InstIndex = unsigned;
+
+  /// All instruction instruction that can act as an optimization barrier.
+  /// eg: throw, fence, atomics ...
+  /// Those barrier are used to not prevent transformation removal of a store
+  /// being overriden by another store when an optimization barrier
+  /// could be executed between the two stores.
+  /// They are not garanted to prevent optimization based on a non-escaping
+  /// pointer not being used.
+  SmallVector<InstIndex, 16> OptBarrierInst;
+
+  /// StoreInst or memory intrinsics that writes to memory. mapped to there
+  /// index in there basic block.
+  SmallDenseMap<Instruction *, InstIndex, 32> InstructionIndex;
+
+  enum DSECandidateFlags : unsigned {
+    DCF_NormalStore = 0,
+    DCF_LifetimeEndLike = 1,
+  };
+
+  using DSECandidate = PointerIntPair<Instruction *, 2>;
+
+  SmallVector<DSECandidate, 16> DSECandidates;
+
+  /// Set of pointer we know to be non-escaping.
+  /// non-escaping mean that at the end of the function the value store at there
+  /// address is not observable.
+  SmallSet<const Value *, 16> NonEscapingPtr;
+
+  /// state we need to keep track of for every BasicBlock.
+  struct BBState {
+    /// Instruction index of the first/last instruction in the basic block that
+    /// is an optimization barrier.
+    unsigned FirstBarrierIdx;
+    unsigned LastBarrierIdx;
+
+    /// Its the PostOrder index of the BasicBlock. it is used to detect
+    /// backedges.
+    InstIndex BlockPostOrder;
+  };
+
+  /// Map of BasicBlocks to there state. [First, Last[ OptBarrierInst.
+  SmallDenseMap<BasicBlock *, BBState, 16> BBStateMap;
+
+  /// isOveride needs this, but it is currently unused.
+  InstOverlapIntervalsTy IOL;
+
+  DSEContext(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
+             PostDominatorTree &PDT, const TargetLibraryInfo &TLI)
+      : F(F), AA(AA), MSSA(MSSA), DT(DT), PDT(PDT), TLI(TLI) {}
+  bool run();
+  void deleteDeadInstruction(Instruction *I);
+
+  MemoryLocation getWriteLoc(Instruction *I) {
+    assert(I->mayWriteToMemory());
+    return getLocForWrite(I);
+  }
+
+  MemoryLocation getReadLoc(Instruction *I) {
+    assert(I->mayReadFromMemory() && !isEndLifetimeLike(I));
+    if (auto *LI = dyn_cast<LoadInst>(I))
+      return MemoryLocation::get(LI);
+    // TODO: extend the definition. to handle libray functions and builtins.
+    return MemoryLocation();
+  }
+
+  enum BarrierPlacement { BP_Before, BP_After };
+
+  /// check if there is any Instruction form the OptBarrierInst
+  /// before or after in the current BasicBlock.
+  template <BarrierPlacement BP> bool hasOptBarrier(Instruction *I) {
+    BBState &BBS = BBStateMap[I->getParent()];
+    if (BBS.FirstBarrierIdx == BBS.LastBarrierIdx)
+      return false;
+    if (BP == BP_Before)
+      return InstructionIndex[I] < OptBarrierInst[BBS.FirstBarrierIdx];
+    assert(BP == BP_After);
+    return InstructionIndex[I] > OptBarrierInst[BBS.LastBarrierIdx - 1];
+  }
+
+  bool isFullOverrite(const MemoryLocation &Loc, Instruction *I) {
+    assert(mustWriteToMemory(I));
+    MemoryLocation OtherLoc = getWriteLoc(I);
+    int64_t DeadOffset, KillerOffset;
+    OverwriteResult OR =
+        isOverwriteWrapper(OtherLoc, Loc, KillerOffset, DeadOffset, I);
+    return OR == OW_Complete;
+  }
+
+  static Instruction *getMemInst(const MemoryAccess *MA) {
+    if (!MA)
+      return nullptr;
+    if (auto *UOD = dyn_cast<MemoryUseOrDef>(MA))
+      return UOD->getMemoryInst();
+    return nullptr;
+  }
+
+  OverwriteResult isOverwriteWrapper(const MemoryLocation &Later,
+                                     const MemoryLocation &Earlier,
+                                     int64_t &LaterOff, int64_t &EarlierOff,
+                                     Instruction *LaterWrite) {
+    if (isEndLifetimeLike(LaterWrite)) {
+      if (GetUnderlyingObject(Earlier.Ptr, F.getParent()->getDataLayout()) ==
+          GetUnderlyingObject(Later.Ptr, F.getParent()->getDataLayout()))
+        return OW_Complete;
+      return OW_Unknown;
+    }
+    return isOverwrite(Later, Earlier, F.getParent()->getDataLayout(), TLI,
+                       EarlierOff, LaterOff, LaterWrite, IOL, AA, &F);
+  }
+
+  bool mustWriteToMemory(Instruction *I) {
+    if (!I->mayWriteToMemory())
+      return false;
+    if (auto *Intr = dyn_cast<AnyMemIntrinsic>(I)) {
+      switch (Intr->getIntrinsicID()) {
+      case Intrinsic::memcpy:
+      case Intrinsic::memset:
+      case Intrinsic::memmove:
+      case Intrinsic::memcpy_element_unordered_atomic:
+      case Intrinsic::memset_element_unordered_atomic:
+      case Intrinsic::memmove_element_unordered_atomic:
+      /// This is not strictly a write but treating it as such does exactly
+      /// what we want.
+      case Intrinsic::lifetime_end:
+        return true;
+      default:
+        return false;
+      }
+    }
+    /// For calls we don't know if they actually write to memory just if they
+    /// can.
+    if (isa<CallBase>(I) && !isEndLifetimeLike(I))
+      return false;
+    return true;
+  }
+
+  bool hasLoadUsersInFunction(
+      MemoryAccess *Start, const MemoryLocation &FirstLoc,
+      SmallDenseMap<BasicBlock *, MemoryAccess *, 8> &LastAccessOfPath,
+      bool isNonEscapingPtr) {
+    SmallSet<MemoryAccess *, 8> Visited;
+    SmallVector<User *, 8> WL;
+    unsigned Iterations = 0;
+    Visited.insert(Start);
+    WL.append(Start->user_begin(), Start->user_end());
+
+    while (!WL.empty()) {
+      if (WL.size() + Iterations++ >= MaxDSEIteration)
+        return true;
+      MemoryAccess *MA = cast_or_null<MemoryAccess>(WL.pop_back_val());
+      if (Visited.find(MA) != Visited.end())
+        return true;
+      if (!MA)
+        continue;
+      Visited.insert(MA);
+      if (Instruction *Access = getMemInst(MA)) {
+
+        if (isOptBarrier(Access))
+          return true;
+        if (Access->mayReadFromMemory() && !isEndLifetimeLike(Access)) {
+          MemoryLocation Loc = getReadLoc(Access);
+          if (isIncomplete(Loc) || !AA.isNoAlias(Loc, FirstLoc))
+            return true;
+        }
+        if (mustWriteToMemory(Access) && isFullOverrite(FirstLoc, Access)) {
+          LastAccessOfPath[MA->getBlock()] = MA;
+          continue;
+        }
+      }
+
+      if (!isa<MemoryUse>(MA)) {
+        if (MA->user_empty() && !isNonEscapingPtr)
+          return true;
+
+        WL.append(MA->user_begin(), MA->user_end());
+      }
+    }
+    return false;
+  }
+
+  /// Check If there is an optimization barrier and if all LastAccessOfPath
+  /// together post-dominate First.
+  bool hasOptBarrierInReachableBB(
+      SmallDenseMap<BasicBlock *, MemoryAccess *, 8> &LastAccessOfPath,
+      Instruction *First, bool isNonEscapingPtr) {
+    // TODO: When a path from the non-escaping pointer reaches the end of the
+    // function. we do not need to check for optimization barrier because they
+    // will not skip any overriding instruction as there is none in this case.
+    // Currently we always check for optimization barriers event when we don't
+    // need to.
+
+    /// Special case for overrite in the same block in the right order.
+    /// If instruction are in the reverse order we trying to remove stores in a
+    /// loop so we need to check all reachble basic blocks.
+    auto SameBBIterator = LastAccessOfPath.find(First->getParent());
+    if (SameBBIterator != LastAccessOfPath.end()) {
+
+      if (isNonEscapingPtr && SameBBIterator->second->user_empty())
+        return false;
+
+      unsigned FirstIdx = InstructionIndex[First];
+      unsigned LastIdx = InstructionIndex[getMemInst(SameBBIterator->second)];
+      if (FirstIdx > LastIdx) {
+        assert(LastAccessOfPath.size() == 1);
+        BBState &BBS = BBStateMap[First->getParent()];
+        if (BBS.FirstBarrierIdx == BBS.LastBarrierIdx)
+          return false;
+
+        for (unsigned Idx = BBS.FirstBarrierIdx; Idx < BBS.LastBarrierIdx;
+             Idx++)
+          if (OptBarrierInst[Idx] < FirstIdx && OptBarrierInst[Idx] > LastIdx)
+            return true;
+        return false;
+      }
+    }
+
+    /// We know that the elimination doesn't occur in the same block or the if
+    /// above would have been taken.
+    if (!isNonEscapingPtr && succ_empty(First->getParent())) {
+      assert(LastAccessOfPath.empty());
+      return true;
+    }
+
+    if (hasOptBarrier<BP_After>(First))
+      return true;
+
+    SmallSet<BasicBlock *, 8> VisitedBB;
+    SmallVector<BasicBlock *, 8> WL;
+
+    /// BasicBlock this set of BasicBlock postdominate the BasicBlock of First
+    /// and a LastAccessOfPath. It is used to reduce the search
+    /// space of the following DFS algorithm. When this block is reached it can
+    /// be treated as a end of function.
+    /// This set is only used for function with many BasicBlocks.
+    SmallSet<BasicBlock *, 8> EndOfSearchSpace;
+    unsigned Iterations = 0;
+
+    if (BBStateMap.size() > MaxDSEIteration)
+      for (auto Elem : LastAccessOfPath) {
+        BasicBlock *PostDom =
+            PDT.findNearestCommonDominator(Elem.first, First->getParent());
+        if (PostDom && PostDom != Elem.first)
+          EndOfSearchSpace.insert(PostDom);
+      }
+
+    WL.append(succ_begin(First->getParent()), succ_end(First->getParent()));
+
+    while (!WL.empty()) {
+      if (WL.size() + Iterations++ >= MaxDSEIteration)
+        return true;
+      BasicBlock *N = WL.pop_back_val();
+      assert(N);
+
+      if (VisitedBB.find(N) != VisitedBB.end())
+        continue;
+      VisitedBB.insert(N);
+
+      auto LookupResult = LastAccessOfPath.find(N);
+      if (LookupResult != LastAccessOfPath.end()) {
+        if (hasOptBarrier<BP_Before>(getMemInst(LookupResult->second)))
+          return true;
+        continue;
+      }
+
+      /// If we are here this block is entirely traversed.
+      BBState &BBS = BBStateMap[N];
+      if (BBS.FirstBarrierIdx != BBS.LastBarrierIdx)
+        return true;
+
+      if (succ_empty(N) || EndOfSearchSpace.find(N) != EndOfSearchSpace.end()) {
+        /// We have reached an exit of the function or equivalent. if the
+        /// pointer can escape the function it is observable.
+        if (isNonEscapingPtr)
+          continue;
+        else
+          return true;
+      }
+
+      WL.append(succ_begin(N), succ_end(N));
+    }
+
+    return false;
+  }
+
+  bool isEndLifetimeLike(Instruction *I) {
+    if (auto *Intrinsic = dyn_cast<IntrinsicInst>(I)) {
+      return Intrinsic->getIntrinsicID() == Intrinsic::lifetime_end;
+    }
+    if (auto *Call = dyn_cast<CallBase>(I)) {
+      if (isFreeCall(I, &TLI))
+        return true;
+    }
+    return false;
+  }
+
+  DSECandidate getDSECandidate(Instruction *I) {
+    if (isVolatile(I) || I->isAtomic())
+      return {nullptr, DCF_NormalStore};
+    if (auto *SI = dyn_cast<StoreInst>(I))
+      return {I, DCF_NormalStore};
+    if (isEndLifetimeLike(I))
+      return {I, DCF_LifetimeEndLike};
+    /// TODO : make DSE remove handle calls too.
+    return {nullptr, DCF_NormalStore};
+  }
+
+  bool isOptBarrier(Instruction *I) {
+    if (isEndLifetimeLike(I))
+      return false;
+    return I->mayThrow() || I->isAtomic();
+  }
+};
+
+void DSEContext::deleteDeadInstruction(Instruction *I) {
+  MadeChange = true;
+  SmallVector<Instruction *, 32> NowDeadInsts;
+  MemorySSAUpdater MSSAUpdater(&MSSA);
+
+  NowDeadInsts.push_back(I);
+  --NumFastOther;
+  InstructionIndex.erase(I);
+
+  do {
+    Instruction *DeadInst = NowDeadInsts.pop_back_val();
+    ++NumFastOther;
+
+    // Try to preserve debug information attached to the dead instruction.
+    salvageDebugInfo(*DeadInst);
+
+    // This instruction is dead, zap it, in stages.  Start by removing it from
+    // MemDep, which needs to know the operands and needs it to be in the
+    // function.
+    MSSAUpdater.removeMemoryAccess(DeadInst);
+
+    for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) {
+      Value *Op = DeadInst->getOperand(op);
+      DeadInst->setOperand(op, nullptr);
+
+      // If this operand just became dead, add it to the NowDeadInsts list.
+      if (!Op->use_empty())
+        continue;
+
+      if (Instruction *OpI = dyn_cast<Instruction>(Op))
+        if (isInstructionTriviallyDead(OpI, &TLI))
+          NowDeadInsts.push_back(OpI);
+    }
+
+    DeadInst->eraseFromParent();
+  } while (!NowDeadInsts.empty());
+}
+
+// Expand the set of non-escaping pointer by propagating the property down there
+// use chain.
+static void PropagateNonEscaping(SmallSet<const Value *, 16> &NonEscapingPtr) {
+  SmallVector<const Value *, 32> WL;
+  WL.append(NonEscapingPtr.begin(), NonEscapingPtr.end());
+
+  while (!WL.empty()) {
+    const Value *V = WL.pop_back_val();
+    NonEscapingPtr.insert(V);
+    assert(V->getType()->isPointerTy());
+    for (const User *U : V->users()) {
+      if (auto *I = dyn_cast<Instruction>(U)) {
+        switch (I->getOpcode()) {
+        case Instruction::GetElementPtr:
+        case Instruction::BitCast:
+          WL.push_back(I);
+          break;
+        case Instruction::PHI:
+          if (llvm::all_of(
+                  I->operand_values(), [&NonEscapingPtr](const Value *Op) {
+                    assert(Op->getType()->isPointerTy());
+                    return NonEscapingPtr.find(Op) != NonEscapingPtr.end();
+                  }))
+            WL.push_back(I);
+          break;
+        default:
+          if (auto *Call = dyn_cast<CallBase>(I))
+            if (V == Call->getReturnedArgOperand()) {
+              WL.push_back(I);
+              break;
+            }
+          /// TODO: there is propably many other ways to propagate down the
+          /// use chain.
+        }
+      }
+    }
+  }
+}
+
+bool DSEContext::run() {
+  InstIndex FuncIdx = 0;
+
+  /// Build the various data structures that are needed for DSE.
+  for (BasicBlock *BB : post_order(&F)) {
+    unsigned BBStartOptBarrier = OptBarrierInst.size();
+    if (DT.isReachableFromEntry(BB))
+      for (Instruction &I : reverse(*BB)) {
+
+        /// We can know they are non-escaping.
+        if (isa<AllocaInst>(&I))
+          NonEscapingPtr.insert(&I);
+        else if (isAllocationFn(&I, &TLI) &&
+                 !PointerMayBeCaptured(&I, true, true))
+          NonEscapingPtr.insert(&I);
+
+        if (isOptBarrier(&I))
+          OptBarrierInst.push_back(FuncIdx);
+        if (I.mayReadOrWriteMemory())
+          InstructionIndex.insert(std::make_pair(&I, FuncIdx));
+
+        DSECandidate Cand = getDSECandidate(&I);
+        if (Cand.getPointer())
+          DSECandidates.push_back(Cand);
+        FuncIdx++;
+      }
+
+    BBState &State = BBStateMap[BB];
+    State.FirstBarrierIdx = BBStartOptBarrier;
+    State.LastBarrierIdx = OptBarrierInst.size();
+    State.BlockPostOrder = FuncIdx++;
+  }
+
+  for (Argument &Arg : F.args())
+    if (Arg.hasByValOrInAllocaAttr())
+      NonEscapingPtr.insert(&Arg);
+  PropagateNonEscaping(NonEscapingPtr);
+
+  /// Map containing the Last Access of each Path.
+  SmallDenseMap<BasicBlock *, MemoryAccess *, 8> LastAccessOfPath;
+
+  /// Element are pushed in the DSECandidate in post order so looking at the in
+  /// reverse order gives iterate in normal order. which is easier for debuging.
+  for (DSECandidate Cand : reverse(DSECandidates)) {
+
+    /// Check if the instruction hasn't already been deleted.
+    if (InstructionIndex.find(Cand.getPointer()) == InstructionIndex.end())
+      continue;
+    MemoryLocation CandLoc = getWriteLoc(Cand.getPointer());
+
+    /// Check if we may have enough information the optimize the store.
+    if (isIncomplete(CandLoc))
+      continue;
+
+    MemoryAccess *MA = MSSA.getMemoryAccess(Cand.getPointer());
+
+    if (Cand.getInt() & DCF_LifetimeEndLike) {
+      // traverseMemSSA(MA, Cand.getPointer(), CandLoc, 6);
+      continue;
+    }
+
+    bool isNonEscapingPtr =
+        NonEscapingPtr.find(CandLoc.Ptr) != NonEscapingPtr.end();
+
+    LastAccessOfPath.clear();
+    if (!hasLoadUsersInFunction(MA, CandLoc, LastAccessOfPath,
+                                isNonEscapingPtr) &&
+        !hasOptBarrierInReachableBB(LastAccessOfPath, Cand.getPointer(),
+                                    isNonEscapingPtr)) {
+      NumFastStores++;
+      deleteDeadInstruction(Cand.getPointer());
+    }
+  }
+  return MadeChange;
+}
+
+} // namespace
+
 //===----------------------------------------------------------------------===//
 // DSE Pass
 //===----------------------------------------------------------------------===//
 PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {
-  AliasAnalysis *AA = &AM.getResult<AAManager>(F);
-  DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F);
-  MemoryDependenceResults *MD = &AM.getResult<MemoryDependenceAnalysis>(F);
-  const TargetLibraryInfo *TLI = &AM.getResult<TargetLibraryAnalysis>(F);
+  AliasAnalysis &AA = AM.getResult<AAManager>(F);
+  const TargetLibraryInfo &TLI = AM.getResult<TargetLibraryAnalysis>(F);
+  DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
+
+  if (EnableMemorySSA) {
+    MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
+    PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
 
-  if (!eliminateDeadStores(F, AA, MD, DT, TLI))
+    if (!std::make_unique<DSEContext>(F, AA, MSSA, DT, PDT, TLI)->run())
       return PreservedAnalyses::all();
+  } else {
+    MemoryDependenceResults &MD = AM.getResult<MemoryDependenceAnalysis>(F);
+
+    if (!eliminateDeadStores(F, &AA, &MD, &DT, &TLI))
+      return PreservedAnalyses::all();
+  }
 
   PreservedAnalyses PA;
   PA.preserveSet<CFGAnalyses>();
   PA.preserve<GlobalsAA>();
+  if (EnableMemorySSA)
+    PA.preserve<MemorySSAAnalysis>();
+  else
     PA.preserve<MemoryDependenceAnalysis>();
   return PA;
 }
 
 namespace {
 
 /// A legacy pass for the legacy pass manager that wraps \c DSEPass.
 class DSELegacyPass : public FunctionPass {
 public:
   static char ID; // Pass identification, replacement for typeid
 
   DSELegacyPass() : FunctionPass(ID) {
     initializeDSELegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
 
-    DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-    AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
-    MemoryDependenceResults *MD =
-        &getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
-    const TargetLibraryInfo *TLI =
-        &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
+    AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
+    DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+    const TargetLibraryInfo &TLI =
+        getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
+
+    if (EnableMemorySSA) {
+      MemorySSA &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
+      PostDominatorTree &PDT =
+          getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
 
-    return eliminateDeadStores(F, AA, MD, DT, TLI);
+      return std::make_unique<DSEContext>(F, AA, MSSA, DT, PDT, TLI)->run();
+    } else {
+      MemoryDependenceResults &MD =
+          getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
+
+      return eliminateDeadStores(F, &AA, &MD, &DT, &TLI);
+    }
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
-    AU.addRequired<DominatorTreeWrapperPass>();
+
     AU.addRequired<AAResultsWrapperPass>();
-    AU.addRequired<MemoryDependenceWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
-    AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
+    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addPreserved<DominatorTreeWrapperPass>();
+
+    if (EnableMemorySSA) {
+      AU.addRequired<PostDominatorTreeWrapperPass>();
+      AU.addRequired<MemorySSAWrapperPass>();
+      AU.addPreserved<PostDominatorTreeWrapperPass>();
+      AU.addPreserved<MemorySSAWrapperPass>();
+    } else {
+      AU.addRequired<MemoryDependenceWrapperPass>();
       AU.addPreserved<MemoryDependenceWrapperPass>();
     }
+  }
 };
 
 } // end anonymous namespace
 
 char DSELegacyPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_END(DSELegacyPass, "dse", "Dead Store Elimination", false,
                     false)
 
 FunctionPass *llvm::createDeadStoreEliminationPass() {
   return new DSELegacyPass();
 }

llvm/test/Transforms/DeadStoreElimination/multiblock-aliasing.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt %s -basicaa -dse -enable-dse-memoryssa -S | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+declare void @unknown_func()
+declare void @may_throw_func() readnone
+declare void @llvm.lifetime.end.p0i32(i64, i32* nocapture) nounwind
+declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) nounwind
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i1) nounwind
+declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
+declare noalias i8* @malloc(i32)
+declare void @free(i8* nocapture)
+
+; we could be much more aggressive here
+define i32 @_Z6test50Pxb(i64* %P, i1 zeroext %B) #0 {
+; CHECK-LABEL: @_Z6test50Pxb(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[FROMBOOL:%.*]] = zext i1 [[B:%.*]] to i8
+; CHECK-NEXT:    store i64 1, i64* [[P:%.*]], align 8
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i64* [[P]] to i32*
+; CHECK-NEXT:    store i32 0, i32* [[TMP0]], align 4
+; CHECK-NEXT:    [[TOBOOL:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i64* [[P]] to i16*
+; CHECK-NEXT:    [[ADD_PTR2:%.*]] = getelementptr inbounds i16, i16* [[TMP1]], i64 2
+; CHECK-NEXT:    [[TMP2:%.*]] = load i16, i16* [[ADD_PTR2]], align 2
+; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[TMP2]] to i32
+; CHECK-NEXT:    store i64 1, i64* [[P]], align 8
+; CHECK-NEXT:    ret i32 [[CONV]]
+;
+entry:
+  %frombool = zext i1 %B to i8
+  store i64 1, i64* %P, align 8
+  %0 = bitcast i64* %P to i32*
+  store i32 0, i32* %0, align 4
+  %tobool = trunc i8 %frombool to i1
+  br i1 %tobool, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  br label %bb1
+
+bb1:
+  %1 = bitcast i64* %P to i16*
+  %add.ptr = getelementptr inbounds i16, i16* %1, i64 3
+  store i16 1, i16* %add.ptr, align 2
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  %2 = bitcast i64* %P to i16*
+  %add.ptr1 = getelementptr inbounds i16, i16* %2, i64 3
+  store i16 2, i16* %add.ptr1, align 2
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %3 = bitcast i64* %P to i16*
+  %add.ptr2 = getelementptr inbounds i16, i16* %3, i64 2
+  %4 = load i16, i16* %add.ptr2, align 2
+  %conv = sext i16 %4 to i32
+  store i64 1, i64* %P, align 8
+  ret i32 %conv
+}
+
+define void @test1(i32* %P) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    ret void
+;
+  %DEAD = load i32, i32* %P
+  %DEAD2 = add i32 %DEAD, 1
+  store i32 %DEAD2, i32* %P
+  br label %bb1
+bb1:
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @test1A(i32* %P) {
+; CHECK-LABEL: @test1A(
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br label [[BB2:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    ret void
+;
+  %DEAD = load i32, i32* %P
+  %DEAD2 = add i32 %DEAD, 1
+  store i32 %DEAD2, i32* %P
+  br label %bb1
+bb1:
+  store i32 0, i32* %P
+  br label %bb2
+bb2:
+  ret void
+}
+
+define void @test3A(i32* %P) {
+; CHECK-LABEL: @test3A(
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  store i32 0, i32* %P
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @test4(i32* %P) {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  %x = load i32, i32* %P
+  br label %bb3
+bb3:
+  store i32 1, i32* %P
+  ret void
+}
+
+define void @test4A(i32* %P) {
+; CHECK-LABEL: @test4A(
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    [[P1:%.*]] = bitcast i32* [[P]] to i8*
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[X:%.*]] = load i8, i8* [[P1]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  store i32 0, i32* %P
+  %P1 = bitcast i32* %P to i8*
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  %x = load i8, i8* %P1
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+define i32 @test4B(i32* %P) {
+; CHECK-LABEL: @test4B(
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P]]
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    ret i32 [[X]]
+;
+  store i32 0, i32* %P
+  %x = load i32, i32* %P
+  store i32 1, i32* %P
+  ret i32 %x
+}
+
+define i32 @test4D(i32* %P, i32* %Q) {
+; CHECK-LABEL: @test4D(
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[Q:%.*]]
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    ret i32 [[X]]
+;
+  store i32 0, i32* %P
+  %x = load i32, i32* %Q
+  store i32 1, i32* %P
+  ret i32 %x
+}
+
+define i32 @test4E(i32* noalias %P, i32* %Q) {
+; CHECK-LABEL: @test4E(
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[Q:%.*]]
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    ret i32 [[X]]
+;
+  store i32 0, i32* %P
+  %x = load i32, i32* %Q
+  store i32 1, i32* %P
+  ret i32 %x
+}
+
+define i32 @test4F(i32* %P, i32* noalias %Q) {
+; CHECK-LABEL: @test4F(
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[Q:%.*]]
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    ret i32 [[X]]
+;
+  store i32 0, i32* %P
+  %x = load i32, i32* %Q
+  store i32 1, i32* %P
+  ret i32 %x
+}
+
+define i32 @test4C(i32* %P) {
+; CHECK-LABEL: @test4C(
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P]]
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    [[X1:%.*]] = load i32, i32* [[P]]
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    ret i32 [[X1]]
+;
+  store i32 0, i32* %P
+  %x = load i32, i32* %P
+  store i32 1, i32* %P
+  store i32 0, i32* %P
+  %x1 = load i32, i32* %P
+  store i32 1, i32* %P
+  ret i32 %x1
+}
+
+define i32 @test4G(i32* %P, i32* %Q) {
+; CHECK-LABEL: @test4G(
+; CHECK-NEXT:    store i32 0, i32* [[Q:%.*]]
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P:%.*]]
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    store i32 0, i32* [[Q]]
+; CHECK-NEXT:    [[X1:%.*]] = load i32, i32* [[P]]
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    ret i32 [[X1]]
+;
+  store i32 0, i32* %Q
+  %x = load i32, i32* %P
+  store i32 1, i32* %P
+  store i32 0, i32* %Q
+  %x1 = load i32, i32* %P
+  store i32 1, i32* %P
+  ret i32 %x1
+}
+
+define i32 @test4H(i32* noalias %P, i32* %Q) {
+; CHECK-LABEL: @test4H(
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P:%.*]]
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    store i32 0, i32* [[Q:%.*]]
+; CHECK-NEXT:    [[X1:%.*]] = load i32, i32* [[P]]
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    ret i32 [[X1]]
+;
+  store i32 0, i32* %Q
+  %x = load i32, i32* %P
+  store i32 1, i32* %P
+  store i32 0, i32* %Q
+  %x1 = load i32, i32* %P
+  store i32 1, i32* %P
+  ret i32 %x1
+}
+
+define void @test5(i32* %P, i32* %Q) {
+; CHECK-LABEL: @test5(
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 1, i32* [[Q:%.*]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    ret void
+;
+  br i1 true, label %bb1, label %bb2
+bb1:
+  store i32 1, i32* %P
+  br label %bb3
+bb2:
+  store i32 1, i32* %Q
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @test5A(i32* %P, i32* %Q) {
+; CHECK-LABEL: @test5A(
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[Q:%.*]]
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  store i32 1, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  store i32 0, i32* %Q
+  br label %bb3
+bb2:
+  store i32 1, i32* %P
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @test5E(i32* %P, i32* %Q) {
+; CHECK-LABEL: @test5E(
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[Q:%.*]]
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    ret void
+;
+  store i32 1, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  store i32 0, i32* %Q
+  br label %bb3
+bb2:
+  store i32 1, i32* %P
+  br label %bb3
+bb3:
+  store i32 1, i32* %P
+  ret void
+}
+
+define void @test7(i32* %P, i32* noalias %Q) {
+; CHECK-LABEL: @test7(
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[P:%.*]]
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[Q:%.*]]
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  store i32 1, i32* %Q
+  br i1 true, label %bb1, label %bb2
+bb1:
+  load i32, i32* %P
+  br label %bb3
+bb2:
+  br label %bb3
+bb3:
+  store i32 0, i32* %Q
+  store i32 0, i32* %P
+  ret void
+}
+
+
+define void @test8(i32* %P) {
+; CHECK-LABEL: @test8(
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[P]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  br i1 true, label %bb1, label %bb2
+bb1:
+  store i32 1, i32* %P
+  br label %bb3
+bb2:
+  store i32 1, i32* %P
+  load i32, i32* %P
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+
+define void @test10(i32* %P) {
+; CHECK-LABEL: @test10(
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i8 1, i8* [[P2]]
+; CHECK-NEXT:    ret void
+;
+  %P2 = bitcast i32* %P to i8*
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  br label %bb3
+bb3:
+  store i8 1, i8* %P2
+  ret void
+}
+
+define void @test13(i32* %P, i32* %Q) {
+; CHECK-LABEL: @test13(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[Q:%.*]]
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br i1 false, label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i32 0, i32* %P
+  br label %for
+for:
+  store i32 0, i32* %P
+  load i32, i32* %Q
+  store i32 0, i32* %P
+  br i1 false, label %for, label %end
+end:
+  ret void
+}
+
+define void @test13A(i32* %P, i32* noalias %Q) {
+; CHECK-LABEL: @test13A(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[Q:%.*]]
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 false, label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i32 0, i32* %P
+  br label %for
+for:
+  store i32 0, i32* %P
+  load i32, i32* %Q
+  store i32 0, i32* %P
+  br i1 false, label %for, label %end
+end:
+  ret void
+}
+
+define void @test14(i32* %P, i32* %Q) {
+; CHECK-LABEL: @test14(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    store i32 0, i32* [[Q:%.*]]
+; CHECK-NEXT:    br i1 false, label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i32 1, i32* %P
+  br label %for
+for:
+  store i32 0, i32* %Q
+  br i1 false, label %for, label %end
+end:
+  ret void
+}
+
+define void @test16(i32* %P, i32* %Q) {
+; CHECK-LABEL: @test16(
+; CHECK-NEXT:    [[Q2:%.*]] = bitcast i32* [[Q:%.*]] to i8*
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB3:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    call void @free(i8* [[Q2]])
+; CHECK-NEXT:    store i32 1, i32* [[Q]]
+; CHECK-NEXT:    ret void
+;
+  %Q2 = bitcast i32* %Q to i8*
+  store i32 1, i32* %P
+  store i8 1, i8* %Q2
+  br i1 true, label %bb1, label %bb3
+bb1:
+  store i32 1, i32* %P
+  store i32 1, i32* %Q
+  br label %bb3
+bb3:
+  call void @free(i8* %Q2)
+  store i32 1, i32* %Q
+  ret void
+}
+
+define void @test17B(i32* %P) {
+; CHECK-LABEL: @test17B(
+; CHECK-NEXT:    [[P2:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[P2]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB3:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 1, i32* [[P2]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  %P2 = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %P
+  store i32 1, i32* %P2
+  br i1 true, label %bb1, label %bb3
+bb1:
+  store i32 1, i32* %P
+  store i32 1, i32* %P2
+  br label %bb3
+bb3:
+  store i32 1, i32* %P
+  ret void
+}
+
+define void @test17C(i32* %P, i32* %Q) {
+; CHECK-LABEL: @test17C(
+; CHECK-NEXT:    [[P2:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    store i32 1, i32* [[P2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[Q:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB3:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    store i32 1, i32* [[P2]]
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[Q]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* [[Q]]
+; CHECK-NEXT:    ret void
+;
+  %P2 = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %P
+  store i32 1, i32* %P2
+  load i32, i32* %Q
+  br i1 true, label %bb1, label %bb3
+bb1:
+  store i32 1, i32* %P
+  store i32 1, i32* %P2
+  load i32, i32* %Q
+  br label %bb3
+bb3:
+  store i32 1, i32* %P
+  load i32, i32* %Q
+  ret void
+}
+
+define void @test17D(i32* %P, i32* noalias %Q) {
+; CHECK-LABEL: @test17D(
+; CHECK-NEXT:    [[P2:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[P2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[Q:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB3:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 1, i32* [[P2]]
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[Q]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* [[Q]]
+; CHECK-NEXT:    ret void
+;
+  %P2 = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %P
+  store i32 1, i32* %P2
+  load i32, i32* %Q
+  br i1 true, label %bb1, label %bb3
+bb1:
+  store i32 1, i32* %P
+  store i32 1, i32* %P2
+  load i32, i32* %Q
+  br label %bb3
+bb3:
+  store i32 1, i32* %P
+  load i32, i32* %Q
+  ret void
+}
+
+define void @test18(i32* %P) {
+; CHECK-LABEL: @test18(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    store i8 1, i8* [[P2]]
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P]]
+; CHECK-NEXT:    store i8 2, i8* [[P2]]
+; CHECK-NEXT:    br i1 false, label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %P2 = bitcast i32* %P to i8*
+  store i32 0, i32* %P
+  br label %for
+for:
+  store i8 1, i8* %P2
+  %x = load i32, i32* %P
+  store i8 2, i8* %P2
+  br i1 false, label %for, label %end
+end:
+  ret void
+}
+
+
+define void @test19(i32* %P) {
+; CHECK-LABEL: @test19(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
+; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1
+  %p3 = bitcast i32* %arrayidx0 to i8*
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  %arrayidx1 = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %arrayidx1, align 4
+  br label %bb3
+bb3:
+  ret void
+}
+
+
+define void @test20(i32* %P) {
+; CHECK-LABEL: @test20(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
+; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1
+  %p3 = bitcast i32* %arrayidx0 to i8*
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  br label %bb3
+bb3:
+  %arrayidx1 = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %arrayidx1, align 4
+  ret void
+}
+
+
+define void @test21(i32* %P) {
+; CHECK-LABEL: @test21(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
+; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    br i1 false, label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1
+  %p3 = bitcast i32* %arrayidx0 to i8*
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
+  br label %for
+for:
+  %arrayidx1 = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %arrayidx1, align 4
+  br i1 false, label %for, label %end
+end:
+  ret void
+}
+
+define void @test21A(i32* %P) {
+; CHECK-LABEL: @test21A(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P:%.*]]
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    [[X1:%.*]] = trunc i32 [[X]] to i1
+; CHECK-NEXT:    br i1 [[X1]], label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for
+for:
+  %x = load i32, i32* %P
+  store i32 1, i32* %P, align 4
+  %x1 = trunc i32 %x to i1
+  br i1 %x1, label %for, label %end
+end:
+  store i32 1, i32* %P, align 4
+  ret void
+}
+
+define i32 @test22(i32* %P, i32* noalias %Q, i32* %R) {
+; CHECK-LABEL: @test22(
+; CHECK-NEXT:    store i32 2, i32* [[P:%.*]]
+; CHECK-NEXT:    store i32 3, i32* [[Q:%.*]]
+; CHECK-NEXT:    [[L:%.*]] = load i32, i32* [[R:%.*]]
+; CHECK-NEXT:    ret i32 [[L]]
+;
+  store i32 1, i32* %Q
+  store i32 2, i32* %P
+  store i32 3, i32* %Q
+  %l = load i32, i32* %R
+  ret i32 %l
+}
+
+
+define void @test23(i32* %P) {
+; CHECK-LABEL: @test23(
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    ret void
+;
+  br i1 true, label %bb1, label %bb2
+bb1:
+  store i32 0, i32* %P
+  br label %bb3
+bb2:
+  call void @unknown_func()
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @test24(i32* %P) {
+; CHECK-LABEL: @test24(
+; CHECK-NEXT:    br i1 true, label [[BB2:%.*]], label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    ret void
+;
+  br i1 true, label %bb2, label %bb1
+bb1:
+  store i32 0, i32* %P
+  br label %bb3
+bb2:
+  call void @unknown_func()
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+
+define void @test25(i32* %P) {
+; CHECK-LABEL: @test25(
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P]] to i8*
+; CHECK-NEXT:    br i1 true, label [[BB2:%.*]], label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    call void @free(i8* [[P2]])
+; CHECK-NEXT:    ret void
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  store i32 1, i32* %P
+  %P2 = bitcast i32* %P to i8*
+  br i1 true, label %bb2, label %bb1
+bb1:
+  br label %bb3
+bb2:
+  call void @free(i8* %P2)
+  ret void
+bb3:
+  ret void
+}
+
+
+define i8* @test26() {
+; CHECK-LABEL: @test26(
+; CHECK-NEXT:  bb1:
+; CHECK-NEXT:    br i1 true, label [[BB2:%.*]], label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[M:%.*]] = call noalias i8* @malloc(i32 10)
+; CHECK-NEXT:    store i8 1, i8* [[M]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[R:%.*]] = phi i8* [ null, [[BB1:%.*]] ], [ [[M]], [[BB2]] ]
+; CHECK-NEXT:    ret i8* [[R]]
+;
+bb1:
+  br i1 true, label %bb2, label %bb3
+bb2:
+  %m = call noalias i8* @malloc(i32 10)
+  store i8 1, i8* %m
+  br label %bb3
+bb3:
+  %r = phi i8* [ null, %bb1 ], [ %m, %bb2 ]
+  ret i8* %r
+}
+
+
+define void @test27() {
+; CHECK-LABEL: @test27(
+; CHECK-NEXT:  bb1:
+; CHECK-NEXT:    br i1 true, label [[BB2:%.*]], label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[M:%.*]] = call noalias i8* @malloc(i32 10)
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[R:%.*]] = phi i8* [ null, [[BB1:%.*]] ], [ [[M]], [[BB2]] ]
+; CHECK-NEXT:    ret void
+;
+bb1:
+  br i1 true, label %bb2, label %bb3
+bb2:
+  %m = call noalias i8* @malloc(i32 10)
+  store i8 1, i8* %m
+  br label %bb3
+bb3:
+  %r = phi i8* [ null, %bb1 ], [ %m, %bb2 ]
+  ret void
+}
+
+
+define i8* @test28() {
+; CHECK-LABEL: @test28(
+; CHECK-NEXT:  bb0:
+; CHECK-NEXT:    [[M:%.*]] = call noalias i8* @malloc(i32 10)
+; CHECK-NEXT:    [[MC0:%.*]] = bitcast i8* [[M]] to i8*
+; CHECK-NEXT:    [[MC1:%.*]] = bitcast i8* [[MC0]] to i8*
+; CHECK-NEXT:    [[MC2:%.*]] = bitcast i8* [[MC1]] to i8*
+; CHECK-NEXT:    [[MC3:%.*]] = bitcast i8* [[MC2]] to i8*
+; CHECK-NEXT:    [[MC4:%.*]] = bitcast i8* [[MC3]] to i8*
+; CHECK-NEXT:    [[MC5:%.*]] = bitcast i8* [[MC4]] to i8*
+; CHECK-NEXT:    [[MC6:%.*]] = bitcast i8* [[MC5]] to i8*
+; CHECK-NEXT:    [[M0:%.*]] = bitcast i8* [[MC6]] to i8*
+; CHECK-NEXT:    store i8 2, i8* [[M]]
+; CHECK-NEXT:    ret i8* [[M0]]
+;
+bb0:
+  %m = call noalias i8* @malloc(i32 10)
+  %mc0 = bitcast i8* %m to i8*
+  %mc1 = bitcast i8* %mc0 to i8*
+  %mc2 = bitcast i8* %mc1 to i8*
+  %mc3 = bitcast i8* %mc2 to i8*
+  %mc4 = bitcast i8* %mc3 to i8*
+  %mc5 = bitcast i8* %mc4 to i8*
+  %mc6 = bitcast i8* %mc5 to i8*
+  %m0 = bitcast i8* %mc6 to i8*
+  store i8 2, i8* %m
+  ret i8* %m0
+}
+
+
+define void @test_loop(i32 %N, i32* noalias nocapture readonly %A, i32* noalias nocapture readonly %x, i32* noalias nocapture %b) local_unnamed_addr {
+; CHECK-LABEL: @test_loop(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP27:%.*]] = icmp sgt i32 [[N:%.*]], 0
+; CHECK-NEXT:    br i1 [[CMP27]], label [[FOR_BODY4_LR_PH_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]
+; CHECK:       for.body4.lr.ph.preheader:
+; CHECK-NEXT:    br label [[FOR_BODY4_LR_PH:%.*]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    ret void
+; CHECK:       for.body4.lr.ph:
+; CHECK-NEXT:    [[I_028:%.*]] = phi i32 [ [[INC11:%.*]], [[FOR_COND_CLEANUP3:%.*]] ], [ 0, [[FOR_BODY4_LR_PH_PREHEADER]] ]
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i32 [[I_028]]
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[I_028]], [[N]]
+; CHECK-NEXT:    br label [[FOR_BODY4:%.*]]
+; CHECK:       for.cond.cleanup3:
+; CHECK-NEXT:    store i32 [[ADD9:%.*]], i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[INC11]] = add nuw nsw i32 [[I_028]], 1
+; CHECK-NEXT:    [[EXITCOND29:%.*]] = icmp eq i32 [[INC11]], [[N]]
+; CHECK-NEXT:    br i1 [[EXITCOND29]], label [[FOR_COND_CLEANUP]], label [[FOR_BODY4_LR_PH]]
+; CHECK:       for.body4:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ 0, [[FOR_BODY4_LR_PH]] ], [ [[ADD9]], [[FOR_BODY4]] ]
+; CHECK-NEXT:    [[J_026:%.*]] = phi i32 [ 0, [[FOR_BODY4_LR_PH]] ], [ [[INC:%.*]], [[FOR_BODY4]] ]
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[J_026]], [[MUL]]
+; CHECK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i32 [[ADD]]
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[ARRAYIDX5]], align 4
+; CHECK-NEXT:    [[ARRAYIDX6:%.*]] = getelementptr inbounds i32, i32* [[X:%.*]], i32 [[J_026]]
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[ARRAYIDX6]], align 4
+; CHECK-NEXT:    [[MUL7:%.*]] = mul nsw i32 [[TMP2]], [[TMP1]]
+; CHECK-NEXT:    [[ADD9]] = add nsw i32 [[MUL7]], [[TMP0]]
+; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[J_026]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], [[N]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP3]], label [[FOR_BODY4]]
+;
+entry:
+  %cmp27 = icmp sgt i32 %N, 0
+  br i1 %cmp27, label %for.body4.lr.ph.preheader, label %for.cond.cleanup
+
+for.body4.lr.ph.preheader:                        ; preds = %entry
+  br label %for.body4.lr.ph
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3, %entry
+  ret void
+
+for.body4.lr.ph:                                  ; preds = %for.body4.lr.ph.preheader, %for.cond.cleanup3
+  %i.028 = phi i32 [ %inc11, %for.cond.cleanup3 ], [ 0, %for.body4.lr.ph.preheader ]
+  %arrayidx = getelementptr inbounds i32, i32* %b, i32 %i.028
+  store i32 0, i32* %arrayidx, align 4
+  %mul = mul nsw i32 %i.028, %N
+  br label %for.body4
+
+for.cond.cleanup3:                                ; preds = %for.body4
+  store i32 %add9, i32* %arrayidx, align 4
+  %inc11 = add nuw nsw i32 %i.028, 1
+  %exitcond29 = icmp eq i32 %inc11, %N
+  br i1 %exitcond29, label %for.cond.cleanup, label %for.body4.lr.ph
+
+for.body4:                                        ; preds = %for.body4, %for.body4.lr.ph
+  %0 = phi i32 [ 0, %for.body4.lr.ph ], [ %add9, %for.body4 ]
+  %j.026 = phi i32 [ 0, %for.body4.lr.ph ], [ %inc, %for.body4 ]
+  %add = add nsw i32 %j.026, %mul
+  %arrayidx5 = getelementptr inbounds i32, i32* %A, i32 %add
+  %1 = load i32, i32* %arrayidx5, align 4
+  %arrayidx6 = getelementptr inbounds i32, i32* %x, i32 %j.026
+  %2 = load i32, i32* %arrayidx6, align 4
+  %mul7 = mul nsw i32 %2, %1
+  %add9 = add nsw i32 %mul7, %0
+  %inc = add nuw nsw i32 %j.026, 1
+  %exitcond = icmp eq i32 %inc, %N
+  br i1 %exitcond, label %for.cond.cleanup3, label %for.body4
+}
+
+define void @test52(i32* %P, i1 %B) {
+; CHECK-LABEL: @test52(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[FROMBOOL:%.*]] = zext i1 [[B:%.*]] to i8
+; CHECK-NEXT:    [[TOBOOL:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[IF_THEN:%.*]], label [[IF_END15:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[TOBOOL1:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL1]], label [[IF_THEN2:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then2:
+; CHECK-NEXT:    br label [[IF_END14:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[TOBOOL3:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL3]], label [[IF_THEN4:%.*]], label [[IF_ELSE5:%.*]]
+; CHECK:       if.then4:
+; CHECK-NEXT:    br label [[IF_END13:%.*]]
+; CHECK:       if.else5:
+; CHECK-NEXT:    [[TOBOOL6:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL6]], label [[IF_THEN7:%.*]], label [[IF_ELSE8:%.*]]
+; CHECK:       if.then7:
+; CHECK-NEXT:    br label [[IF_END12:%.*]]
+; CHECK:       if.else8:
+; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
+; CHECK:       while.cond:
+; CHECK-NEXT:    [[TOBOOL9:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[P]]
+; CHECK-NEXT:    br i1 [[TOBOOL9]], label [[WHILE_BODY:%.*]], label [[WHILE_END:%.*]]
+; CHECK:       while.body:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    br i1 [[B]], label [[IF_THEN11:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then11:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[P]]
+; CHECK-NEXT:    br label [[WHILE_COND]]
+; CHECK:       while.end:
+; CHECK-NEXT:    br label [[IF_END12]]
+; CHECK:       if.end12:
+; CHECK-NEXT:    br label [[IF_END13]]
+; CHECK:       if.end13:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[P]]
+; CHECK-NEXT:    br label [[IF_END14]]
+; CHECK:       if.end14:
+; CHECK-NEXT:    br label [[IF_END15]]
+; CHECK:       if.end15:
+; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  %frombool = zext i1 %B to i8
+  store i32 1, i32* %P, align 4
+  %tobool = trunc i8 %frombool to i1
+  br i1 %tobool, label %if.then, label %if.end15
+
+if.then:                                          ; preds = %entry
+  %tobool1 = trunc i8 %frombool to i1
+  store i32 1, i32* %P, align 4
+  br i1 %tobool1, label %if.then2, label %if.else
+
+if.then2:                                         ; preds = %if.then
+  store i32 1, i32* %P, align 4
+  br label %if.end14
+
+if.else:                                          ; preds = %if.then
+  %tobool3 = trunc i8 %frombool to i1
+  br i1 %tobool3, label %if.then4, label %if.else5
+
+if.then4:                                         ; preds = %if.else
+  store i32 1, i32* %P, align 4
+  br label %if.end13
+
+if.else5:                                         ; preds = %if.else
+  %tobool6 = trunc i8 %frombool to i1
+  store i32 1, i32* %P, align 4
+  br i1 %tobool6, label %if.then7, label %if.else8
+
+if.then7:                                         ; preds = %if.else5
+  br label %if.end12
+
+if.else8:                                         ; preds = %if.else5
+  store i32 1, i32* %P, align 4
+  br label %while.cond
+
+while.cond:                                       ; preds = %if.end, %if.else8
+  %tobool9 = trunc i8 %frombool to i1
+  store i32 1, i32* %P, align 4
+  load i32, i32* %P
+  br i1 %tobool9, label %while.body, label %while.end
+
+while.body:                                       ; preds = %while.cond
+  store i32 1, i32* %P, align 4
+  br i1 %B, label %if.then11, label %if.end
+
+if.then11:                                        ; preds = %while.body
+  store i32 1, i32* %P, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.then11, %while.body
+  load i32, i32* %P
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  store i32 1, i32* %P, align 4
+  br label %if.end12
+
+if.end12:                                         ; preds = %while.end, %if.then7
+  store i32 1, i32* %P, align 4
+  br label %if.end13
+
+if.end13:                                         ; preds = %if.end12, %if.then4
+  store i32 1, i32* %P, align 4
+  load i32, i32* %P
+  br label %if.end14
+
+if.end14:                                         ; preds = %if.end13, %if.then2
+  br label %if.end15
+
+if.end15:                                         ; preds = %if.end14, %entry
+  store i32 0, i32* %P, align 4
+  ret void
+}
+
+declare void @may_write_func(i32*) nounwind writeonly
+
+define void @test53(i32* %P, i1 %B) {
+; CHECK-LABEL: @test53(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[FROMBOOL:%.*]] = zext i1 [[B:%.*]] to i8
+; CHECK-NEXT:    [[TOBOOL:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[IF_THEN:%.*]], label [[IF_END15:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[TOBOOL1:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL1]], label [[IF_THEN2:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then2:
+; CHECK-NEXT:    br label [[IF_END14:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[TOBOOL3:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL3]], label [[IF_THEN4:%.*]], label [[IF_ELSE5:%.*]]
+; CHECK:       if.then4:
+; CHECK-NEXT:    br label [[IF_END13:%.*]]
+; CHECK:       if.else5:
+; CHECK-NEXT:    [[TOBOOL6:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL6]], label [[IF_THEN7:%.*]], label [[IF_ELSE8:%.*]]
+; CHECK:       if.then7:
+; CHECK-NEXT:    call void @may_write_func(i32* [[P:%.*]])
+; CHECK-NEXT:    br label [[IF_END12:%.*]]
+; CHECK:       if.else8:
+; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
+; CHECK:       while.cond:
+; CHECK-NEXT:    [[TOBOOL9:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL9]], label [[WHILE_BODY:%.*]], label [[WHILE_END:%.*]]
+; CHECK:       while.body:
+; CHECK-NEXT:    br i1 [[B]], label [[IF_THEN11:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then11:
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    br label [[WHILE_COND]]
+; CHECK:       while.end:
+; CHECK-NEXT:    br label [[IF_END12]]
+; CHECK:       if.end12:
+; CHECK-NEXT:    br label [[IF_END13]]
+; CHECK:       if.end13:
+; CHECK-NEXT:    br label [[IF_END14]]
+; CHECK:       if.end14:
+; CHECK-NEXT:    br label [[IF_END15]]
+; CHECK:       if.end15:
+; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  %frombool = zext i1 %B to i8
+  store i32 1, i32* %P, align 4
+  %tobool = trunc i8 %frombool to i1
+  br i1 %tobool, label %if.then, label %if.end15
+
+if.then:                                          ; preds = %entry
+  store i32 1, i32* %P, align 4
+  %tobool1 = trunc i8 %frombool to i1
+  br i1 %tobool1, label %if.then2, label %if.else
+
+if.then2:                                         ; preds = %if.then
+  store i32 1, i32* %P, align 4
+  br label %if.end14
+
+if.else:                                          ; preds = %if.then
+  store i32 1, i32* %P, align 4
+  %tobool3 = trunc i8 %frombool to i1
+  br i1 %tobool3, label %if.then4, label %if.else5
+
+if.then4:                                         ; preds = %if.else
+  store i32 1, i32* %P, align 4
+  br label %if.end13
+
+if.else5:                                         ; preds = %if.else
+  %tobool6 = trunc i8 %frombool to i1
+  store i32 1, i32* %P, align 4
+  br i1 %tobool6, label %if.then7, label %if.else8
+
+if.then7:                                         ; preds = %if.else5
+  store i32 1, i32* %P, align 4
+  call void @may_write_func(i32* %P)
+  store i32 1, i32* %P, align 4
+  br label %if.end12
+
+if.else8:                                         ; preds = %if.else5
+  store i32 1, i32* %P, align 4
+  br label %while.cond
+
+while.cond:                                       ; preds = %if.end, %if.else8
+  %tobool9 = trunc i8 %frombool to i1
+  store i32 1, i32* %P, align 4
+  br i1 %tobool9, label %while.body, label %while.end
+
+while.body:                                       ; preds = %while.cond
+  store i32 1, i32* %P, align 4
+  br i1 %B, label %if.then11, label %if.end
+
+if.then11:                                        ; preds = %while.body
+  store i32 1, i32* %P, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.then11, %while.body
+  store i32 1, i32* %P, align 4
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  store i32 1, i32* %P, align 4
+  br label %if.end12
+
+if.end12:                                         ; preds = %while.end, %if.then7
+  store i32 1, i32* %P, align 4
+  br label %if.end13
+
+if.end13:                                         ; preds = %if.end12, %if.then4
+  store i32 1, i32* %P, align 4
+  br label %if.end14
+
+if.end14:                                         ; preds = %if.end13, %if.then2
+  store i32 1, i32* %P, align 4
+  br label %if.end15
+
+if.end15:                                         ; preds = %if.end14, %entry
+  store i32 0, i32* %P, align 4
+  ret void
+}
+
+define void @test56A(i1 %B) {
+; CHECK-LABEL: @test56A(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[P:%.*]] = alloca i32, align 1
+; CHECK-NEXT:    [[FROMBOOL:%.*]] = zext i1 [[B:%.*]] to i8
+; CHECK-NEXT:    [[TOBOOL:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[IF_THEN:%.*]], label [[IF_END15:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[TOBOOL1:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL1]], label [[IF_THEN2:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then2:
+; CHECK-NEXT:    br label [[IF_END14:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[TOBOOL3:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL3]], label [[IF_THEN4:%.*]], label [[IF_ELSE5:%.*]]
+; CHECK:       if.then4:
+; CHECK-NEXT:    br label [[IF_END13:%.*]]
+; CHECK:       if.else5:
+; CHECK-NEXT:    [[TOBOOL6:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL6]], label [[IF_THEN7:%.*]], label [[IF_ELSE8:%.*]]
+; CHECK:       if.then7:
+; CHECK-NEXT:    br label [[IF_END12:%.*]]
+; CHECK:       if.else8:
+; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
+; CHECK:       while.cond:
+; CHECK-NEXT:    [[TOBOOL9:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL9]], label [[WHILE_BODY:%.*]], label [[WHILE_END:%.*]]
+; CHECK:       while.body:
+; CHECK-NEXT:    br i1 [[B]], label [[IF_THEN11:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then11:
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    br label [[WHILE_COND]]
+; CHECK:       while.end:
+; CHECK-NEXT:    br label [[IF_END12]]
+; CHECK:       if.end12:
+; CHECK-NEXT:    br label [[IF_END13]]
+; CHECK:       if.end13:
+; CHECK-NEXT:    br label [[IF_END14]]
+; CHECK:       if.end14:
+; CHECK-NEXT:    br label [[IF_END15]]
+; CHECK:       if.end15:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %P = alloca i32, i32 1, align 1
+  %frombool = zext i1 %B to i8
+  store i32 1, i32* %P, align 4
+  %tobool = trunc i8 %frombool to i1
+  br i1 %tobool, label %if.then, label %if.end15
+
+if.then:                                          ; preds = %entry
+  store i32 1, i32* %P, align 4
+  %tobool1 = trunc i8 %frombool to i1
+  br i1 %tobool1, label %if.then2, label %if.else
+
+if.then2:                                         ; preds = %if.then
+  store i32 1, i32* %P, align 4
+  br label %if.end14
+
+if.else:                                          ; preds = %if.then
+  store i32 1, i32* %P, align 4
+  %tobool3 = trunc i8 %frombool to i1
+  br i1 %tobool3, label %if.then4, label %if.else5
+
+if.then4:                                         ; preds = %if.else
+  store i32 1, i32* %P, align 4
+  br label %if.end13
+
+if.else5:                                         ; preds = %if.else
+  store i32 1, i32* %P, align 4
+  %tobool6 = trunc i8 %frombool to i1
+  br i1 %tobool6, label %if.then7, label %if.else8
+
+if.then7:                                         ; preds = %if.else5
+  store i32 1, i32* %P, align 4
+  br label %if.end12
+
+if.else8:                                         ; preds = %if.else5
+  store i32 1, i32* %P, align 4
+  br label %while.cond
+
+while.cond:                                       ; preds = %if.end, %if.else8
+  store i32 1, i32* %P, align 4
+  %tobool9 = trunc i8 %frombool to i1
+  br i1 %tobool9, label %while.body, label %while.end
+
+while.body:                                       ; preds = %while.cond
+  store i32 1, i32* %P, align 4
+  br i1 %B, label %if.then11, label %if.end
+
+if.then11:                                        ; preds = %while.body
+  store i32 1, i32* %P, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.then11, %while.body
+  store i32 1, i32* %P, align 4
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  store i32 1, i32* %P, align 4
+  br label %if.end12
+
+if.end12:                                         ; preds = %while.end, %if.then7
+  store i32 1, i32* %P, align 4
+  br label %if.end13
+
+if.end13:                                         ; preds = %if.end12, %if.then4
+  store i32 1, i32* %P, align 4
+  br label %if.end14
+
+if.end14:                                         ; preds = %if.end13, %if.then2
+  store i32 1, i32* %P, align 4
+  br label %if.end15
+
+if.end15:                                         ; preds = %if.end14, %entry
+  store i32 1, i32* %P, align 4
+  ret void
+}
+
+define void @test57(i32* %P, i1 zeroext %B) #0 {
+; CHECK-LABEL: @test57(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 false, label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i32* [[P:%.*]] to i64*
+; CHECK-NEXT:    store i64 0, i64* [[TMP0]], align 8
+; CHECK-NEXT:    [[ADD_PTR:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[ADD_PTR]], align 4
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[P]], align 4
+; CHECK-NEXT:    [[TOBOOL1:%.*]] = icmp ne i32 [[TMP1]], 0
+; CHECK-NEXT:    [[FROMBOOL2:%.*]] = zext i1 [[TOBOOL1]] to i8
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i32 1, i32* %P, align 4
+  br i1 0, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %0 = bitcast i32* %P to i64*
+  store i64 0, i64* %0, align 8
+  %add.ptr = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %add.ptr, align 4
+  %1 = load i32, i32* %P, align 4
+  %tobool1 = icmp ne i32 %1, 0
+  %frombool2 = zext i1 %tobool1 to i8
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %entry
+  store i32 0, i32* %P, align 4
+  ret void
+}

llvm/test/Transforms/DeadStoreElimination/multiblock-barriers.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt %s -basicaa -dse -enable-dse-memoryssa -S | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+declare void @unknown_func()
+declare void @may_throw_func() readnone
+declare void @may_argread_func(i32* ) nounwind readonly argmemonly
+declare void @may_argwrite_func(i32* ) nounwind readonly argmemonly
+declare void @may_read_func() nounwind readonly
+declare void @may_write_func() nounwind readonly
+declare void @llvm.lifetime.end.p0i32(i64, i32* nocapture) nounwind
+declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) nounwind
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i1) nounwind
+declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
+declare noalias i8* @malloc(i32)
+declare void @free(i8* nocapture)
+
+define void @test1(i32* %P) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    ret void
+;
+  call void @unknown_func()
+  store i32 1, i32* %P
+  br label %bb1
+bb1:
+  store i32 0, i32* %P
+  call void @unknown_func()
+  ret void
+}
+
+define void @test1B(i32* %P) {
+; CHECK-LABEL: @test1B(
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    ret void
+;
+  store i32 1, i32* %P
+  call void @unknown_func()
+  br label %bb1
+bb1:
+  store i32 0, i32* %P
+  call void @unknown_func()
+  ret void
+}
+
+define void @test1C(i32* %P) {
+; CHECK-LABEL: @test1C(
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  call void @unknown_func()
+  store i32 1, i32* %P
+  br label %bb1
+bb1:
+  call void @unknown_func()
+  store i32 0, i32* %P
+  ret void
+}
+
+
+define void @test2(i32* %P) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  store i32 1, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  call void @unknown_func()
+  br label %bb3
+bb2:
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+; we could remove all the stores here.
+define void @test3D() {
+; CHECK-LABEL: @test3D(
+; CHECK-NEXT:    [[P:%.*]] = alloca i32, align 1
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    ret void
+;
+  %P = alloca i32, i32 1, align 1
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  store i32 1, i32* %P
+  br label %bb3
+bb3:
+  call void @unknown_func()
+  ret void
+}
+
+define void @test3A(i32* %P) {
+; CHECK-LABEL: @test3A(
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  call void @unknown_func()
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  store i32 0, i32* %P
+  call void @unknown_func()
+  br label %bb3
+bb2:
+  store i32 0, i32* %P
+  call void @unknown_func()
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @test3B(i32* %P) {
+; CHECK-LABEL: @test3B(
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    ret void
+;
+  call void @unknown_func()
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  store i32 0, i32* %P
+  call void @unknown_func()
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  call void @unknown_func()
+  ret void
+}
+
+define void @testA3A(i32* %P) {
+; CHECK-LABEL: @testA3A(
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  call void @unknown_func()
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  call void @unknown_func()
+  store i32 0, i32* %P
+  br label %bb3
+bb2:
+  store i32 0, i32* %P
+  call void @unknown_func()
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @testA3B(i32* %P) {
+; CHECK-LABEL: @testA3B(
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    ret void
+;
+  call void @unknown_func()
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  call void @unknown_func()
+  store i32 0, i32* %P
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  call void @unknown_func()
+  ret void
+}
+define void @testB3A(i32* %P) {
+; CHECK-LABEL: @testB3A(
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  call void @unknown_func()
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  store i32 0, i32* %P
+  call void @unknown_func()
+  br label %bb3
+bb2:
+  call void @unknown_func()
+  store i32 0, i32* %P
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @testB3B(i32* %P) {
+; CHECK-LABEL: @testB3B(
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  call void @unknown_func()
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  store i32 0, i32* %P
+  call void @unknown_func()
+  br label %bb3
+bb3:
+  call void @unknown_func()
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @test5(i32* %P) {
+; CHECK-LABEL: @test5(
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    ret void
+;
+  br i1 true, label %bb1, label %bb2
+bb1:
+  call void @unknown_func()
+  store i32 1, i32* %P
+  br label %bb3
+bb2:
+  call void @unknown_func()
+  store i32 1, i32* %P
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  call void @unknown_func()
+  ret void
+}
+
+define void @test5C(i32* %P) {
+; CHECK-LABEL: @test5C(
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    ret void
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  call void @unknown_func()
+  store i32 1, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  store i32 0, i32* %P
+  call void @unknown_func()
+  ret void
+bb2:
+  store i32 1, i32* %P
+  call void @unknown_func()
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @test5D(i32* %P) {
+; CHECK-LABEL: @test5D(
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  call void @unknown_func()
+  store i32 1, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  call void @unknown_func()
+  br label %bb4
+bb4:
+  store i32 0, i32* %P
+  ret void
+bb2:
+  store i32 1, i32* %P
+  call void @unknown_func()
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @test6(i32* %P) {
+; CHECK-LABEL: @test6(
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  call void @unknown_func()
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @test6A(i32* %P) {
+; CHECK-LABEL: @test6A(
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB5:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  br label %bb4
+bb4:
+  call void @unknown_func()
+  br label %bb5
+bb5:
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @test14(i32* %P) {
+; CHECK-LABEL: @test14(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 false, label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    ret void
+;
+entry:
+  call void @unknown_func()
+  store i32 1, i32* %P
+  br label %for
+for:
+  store i32 0, i32* %P
+  br i1 false, label %for, label %end
+end:
+  call void @unknown_func()
+  ret void
+}
+
+define void @test14A(i32* %P) {
+; CHECK-LABEL: @test14A(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br i1 false, label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  call void @unknown_func()
+  store i32 1, i32* %P
+  br label %for
+for:
+  store i32 0, i32* %P
+  call void @unknown_func()
+  store i32 0, i32* %P
+  br i1 false, label %for, label %end
+end:
+  store i32 0, i32* %P
+  call void @unknown_func()
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @test14B(i32* %P) {
+; CHECK-LABEL: @test14B(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[FOR]]
+; CHECK:       for:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br i1 false, label [[BB1:%.*]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i32 0, i32* %P
+  call void @unknown_func()
+  store i32 0, i32* %P
+  br label %for
+bb1:
+  store i32 0, i32* %P
+  call void @unknown_func()
+  store i32 0, i32* %P
+  br label %for
+for:
+  store i32 0, i32* %P
+  call void @unknown_func()
+  store i32 0, i32* %P
+  br i1 false, label %bb1, label %end
+end:
+  store i32 0, i32* %P
+  call void @unknown_func()
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @test18(i32* %P) {
+; CHECK-LABEL: @test18(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    store i8 1, i8* [[P2]]
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P]]
+; CHECK-NEXT:    br i1 false, label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    store i8 2, i8* [[P2]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  %P2 = bitcast i32* %P to i8*
+  store i32 0, i32* %P
+  br label %for
+for:
+  store i8 1, i8* %P2
+  %x = load i32, i32* %P
+  store i8 2, i8* %P2
+  br i1 false, label %for, label %end
+end:
+  store i8 2, i8* %P2
+  ret void
+}
+
+define void @test19(i32* %P) {
+; CHECK-LABEL: @test19(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
+; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1
+  %p3 = bitcast i32* %arrayidx0 to i8*
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  %arrayidx1 = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %arrayidx1, align 4
+  br label %bb3
+bb3:
+  ret void
+}
+
+
+define void @test20(i32* %P) {
+; CHECK-LABEL: @test20(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
+; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1
+  %p3 = bitcast i32* %arrayidx0 to i8*
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  br label %bb3
+bb3:
+  %arrayidx1 = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %arrayidx1, align 4
+  ret void
+}
+
+
+define void @test21(i32* %P) {
+; CHECK-LABEL: @test21(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
+; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    br i1 false, label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1
+  %p3 = bitcast i32* %arrayidx0 to i8*
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
+  br label %for
+for:
+  %arrayidx1 = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %arrayidx1, align 4
+  br i1 false, label %for, label %end
+end:
+  ret void
+}
+
+define void @test21A(i32* %P) {
+; CHECK-LABEL: @test21A(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P:%.*]]
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    [[X1:%.*]] = trunc i32 [[X]] to i1
+; CHECK-NEXT:    br i1 [[X1]], label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for
+for:
+  %x = load i32, i32* %P
+  store i32 1, i32* %P, align 4
+  %x1 = trunc i32 %x to i1
+  br i1 %x1, label %for, label %end
+end:
+  store i32 1, i32* %P, align 4
+  ret void
+}
+
+define i8* @test26() {
+; CHECK-LABEL: @test26(
+; CHECK-NEXT:  bb1:
+; CHECK-NEXT:    br i1 true, label [[BB2:%.*]], label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[M:%.*]] = call noalias i8* @malloc(i32 10)
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[R:%.*]] = phi i8* [ null, [[BB1:%.*]] ], [ [[M]], [[BB2]] ]
+; CHECK-NEXT:    ret i8* null
+;
+bb1:
+  br i1 true, label %bb2, label %bb3
+bb2:
+  %m = call noalias i8* @malloc(i32 10)
+  call void @unknown_func()
+  store i8 1, i8* %m
+  br label %bb3
+bb3:
+  %r = phi i8* [ null, %bb1 ], [ %m, %bb2 ]
+  ret i8* null
+}
+
+define i8* @test28() {
+; CHECK-LABEL: @test28(
+; CHECK-NEXT:  bb0:
+; CHECK-NEXT:    [[M:%.*]] = call noalias i8* @malloc(i32 10)
+; CHECK-NEXT:    [[MC0:%.*]] = bitcast i8* [[M]] to i8*
+; CHECK-NEXT:    [[MC1:%.*]] = bitcast i8* [[MC0]] to i8*
+; CHECK-NEXT:    [[MC2:%.*]] = bitcast i8* [[MC1]] to i8*
+; CHECK-NEXT:    [[MC3:%.*]] = bitcast i8* [[MC2]] to i8*
+; CHECK-NEXT:    [[MC4:%.*]] = bitcast i8* [[MC3]] to i8*
+; CHECK-NEXT:    [[MC5:%.*]] = bitcast i8* [[MC4]] to i8*
+; CHECK-NEXT:    [[MC6:%.*]] = bitcast i8* [[MC5]] to i8*
+; CHECK-NEXT:    [[M0:%.*]] = bitcast i8* [[MC6]] to i8*
+; CHECK-NEXT:    store i8 2, i8* [[M]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    ret i8* [[M0]]
+;
+bb0:
+  %m = call noalias i8* @malloc(i32 10)
+  %mc0 = bitcast i8* %m to i8*
+  %mc1 = bitcast i8* %mc0 to i8*
+  %mc2 = bitcast i8* %mc1 to i8*
+  %mc3 = bitcast i8* %mc2 to i8*
+  %mc4 = bitcast i8* %mc3 to i8*
+  %mc5 = bitcast i8* %mc4 to i8*
+  %mc6 = bitcast i8* %mc5 to i8*
+  %m0 = bitcast i8* %mc6 to i8*
+  store i8 2, i8* %m
+  call void @unknown_func()
+  ret i8* %m0
+}
+
+define i8* @test28A() {
+; CHECK-LABEL: @test28A(
+; CHECK-NEXT:  bb0:
+; CHECK-NEXT:    [[M:%.*]] = call noalias i8* @malloc(i32 10)
+; CHECK-NEXT:    [[MC0:%.*]] = bitcast i8* [[M]] to i8*
+; CHECK-NEXT:    [[MC1:%.*]] = bitcast i8* [[MC0]] to i8*
+; CHECK-NEXT:    [[MC2:%.*]] = bitcast i8* [[MC1]] to i8*
+; CHECK-NEXT:    [[MC3:%.*]] = bitcast i8* [[MC2]] to i8*
+; CHECK-NEXT:    [[MC4:%.*]] = bitcast i8* [[MC3]] to i8*
+; CHECK-NEXT:    [[MC5:%.*]] = bitcast i8* [[MC4]] to i8*
+; CHECK-NEXT:    [[MC6:%.*]] = bitcast i8* [[MC5]] to i8*
+; CHECK-NEXT:    [[M0:%.*]] = bitcast i8* [[MC6]] to i8*
+; CHECK-NEXT:    store i8 2, i8* [[M0]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    ret i8* null
+;
+bb0:
+  %m = call noalias i8* @malloc(i32 10)
+  %mc0 = bitcast i8* %m to i8*
+  %mc1 = bitcast i8* %mc0 to i8*
+  %mc2 = bitcast i8* %mc1 to i8*
+  %mc3 = bitcast i8* %mc2 to i8*
+  %mc4 = bitcast i8* %mc3 to i8*
+  %mc5 = bitcast i8* %mc4 to i8*
+  %mc6 = bitcast i8* %mc5 to i8*
+  %m0 = bitcast i8* %mc6 to i8*
+  store i8 2, i8* %m0
+  call void @unknown_func()
+  ret i8* null
+}
+
+define void @test52(i32* %P, i1 %B) {
+; CHECK-LABEL: @test52(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[FROMBOOL:%.*]] = zext i1 [[B:%.*]] to i8
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    [[TOBOOL:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[IF_THEN:%.*]], label [[IF_END15:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[TOBOOL1:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br i1 [[TOBOOL1]], label [[IF_THEN2:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then2:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[IF_END14:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[TOBOOL3:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    br i1 [[TOBOOL3]], label [[IF_THEN4:%.*]], label [[IF_ELSE5:%.*]]
+; CHECK:       if.then4:
+; CHECK-NEXT:    br label [[IF_END13:%.*]]
+; CHECK:       if.else5:
+; CHECK-NEXT:    [[TOBOOL6:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    br i1 [[TOBOOL6]], label [[IF_THEN7:%.*]], label [[IF_ELSE8:%.*]]
+; CHECK:       if.then7:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[IF_END12:%.*]]
+; CHECK:       if.else8:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
+; CHECK:       while.cond:
+; CHECK-NEXT:    [[TOBOOL9:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br i1 [[TOBOOL9]], label [[WHILE_BODY:%.*]], label [[WHILE_END:%.*]]
+; CHECK:       while.body:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br i1 [[B]], label [[IF_THEN11:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then11:
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    br label [[WHILE_COND]]
+; CHECK:       while.end:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[IF_END12]]
+; CHECK:       if.end12:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    br label [[IF_END13]]
+; CHECK:       if.end13:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[IF_END14]]
+; CHECK:       if.end14:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[IF_END15]]
+; CHECK:       if.end15:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  %frombool = zext i1 %B to i8
+  store i32 1, i32* %P, align 4
+  call void @unknown_func()
+  store i32 1, i32* %P, align 4
+  %tobool = trunc i8 %frombool to i1
+  br i1 %tobool, label %if.then, label %if.end15
+
+if.then:                                          ; preds = %entry
+  %tobool1 = trunc i8 %frombool to i1
+  store i32 1, i32* %P, align 4
+  call void @unknown_func()
+  store i32 1, i32* %P, align 4
+  br i1 %tobool1, label %if.then2, label %if.else
+
+if.then2:                                         ; preds = %if.then
+  store i32 1, i32* %P, align 4
+  call void @unknown_func()
+  store i32 1, i32* %P, align 4
+  br label %if.end14
+
+if.else:                                          ; preds = %if.then
+  %tobool3 = trunc i8 %frombool to i1
+  store i32 1, i32* %P, align 4
+  call void @unknown_func()
+  store i32 1, i32* %P, align 4
+  br i1 %tobool3, label %if.then4, label %if.else5
+
+if.then4:                                         ; preds = %if.else
+  br label %if.end13
+
+if.else5:                                         ; preds = %if.else
+  %tobool6 = trunc i8 %frombool to i1
+  store i32 1, i32* %P, align 4
+  call void @unknown_func()
+  store i32 1, i32* %P, align 4
+  br i1 %tobool6, label %if.then7, label %if.else8
+
+if.then7:                                         ; preds = %if.else5
+  store i32 1, i32* %P, align 4
+  call void @unknown_func()
+  store i32 1, i32* %P, align 4
+  br label %if.end12
+
+if.else8:                                         ; preds = %if.else5
+  call void @unknown_func()
+  store i32 1, i32* %P, align 4
+  br label %while.cond
+
+while.cond:                                       ; preds = %if.end, %if.else8
+  %tobool9 = trunc i8 %frombool to i1
+  call void @unknown_func()
+  store i32 1, i32* %P, align 4
+  br i1 %tobool9, label %while.body, label %while.end
+
+while.body:                                       ; preds = %while.cond
+  store i32 1, i32* %P, align 4
+  call void @unknown_func()
+  store i32 1, i32* %P, align 4
+  br i1 %B, label %if.then11, label %if.end
+
+if.then11:                                        ; preds = %while.body
+  store i32 1, i32* %P, align 4
+  store i32 1, i32* %P, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.then11, %while.body
+  store i32 1, i32* %P, align 4
+  call void @unknown_func()
+  store i32 1, i32* %P, align 4
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  store i32 1, i32* %P, align 4
+  call void @unknown_func()
+  store i32 1, i32* %P, align 4
+  br label %if.end12
+
+if.end12:                                         ; preds = %while.end, %if.then7
+  store i32 1, i32* %P, align 4
+  call void @unknown_func()
+  store i32 1, i32* %P, align 4
+  br label %if.end13
+
+if.end13:                                         ; preds = %if.end12, %if.then4
+  call void @unknown_func()
+  store i32 1, i32* %P, align 4
+  br label %if.end14
+
+if.end14:                                         ; preds = %if.end13, %if.then2
+  store i32 1, i32* %P, align 4
+  call void @unknown_func()
+  store i32 1, i32* %P, align 4
+  br label %if.end15
+
+if.end15:                                         ; preds = %if.end14, %entry
+  store i32 1, i32* %P, align 4
+  call void @unknown_func()
+  store i32 1, i32* %P, align 4
+  ret void
+}
+
+define void @test57(i32* %P, i1 zeroext %B) #0 {
+; CHECK-LABEL: @test57(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 false, label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i32* [[P:%.*]] to i64*
+; CHECK-NEXT:    store i64 0, i64* [[TMP0]], align 8
+; CHECK-NEXT:    [[ADD_PTR:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[ADD_PTR]], align 4
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[P]], align 4
+; CHECK-NEXT:    [[TOBOOL1:%.*]] = icmp ne i32 [[TMP1]], 0
+; CHECK-NEXT:    [[FROMBOOL2:%.*]] = zext i1 [[TOBOOL1]] to i8
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i32 1, i32* %P, align 4
+  br i1 0, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %0 = bitcast i32* %P to i64*
+  store i64 0, i64* %0, align 8
+  %add.ptr = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %add.ptr, align 4
+  %1 = load i32, i32* %P, align 4
+  %tobool1 = icmp ne i32 %1, 0
+  %frombool2 = zext i1 %tobool1 to i8
+  call void @unknown_func()
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %entry
+  store i32 0, i32* %P, align 4
+  ret void
+}
+
+; ------
+
+define void @Atest1(i32* %P) {
+; CHECK-LABEL: @Atest1(
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    ret void
+;
+  call void @may_throw_func()
+  store i32 1, i32* %P
+  br label %bb1
+bb1:
+  store i32 0, i32* %P
+  call void @may_throw_func()
+  ret void
+}
+
+define void @Atest1B(i32* %P) {
+; CHECK-LABEL: @Atest1B(
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    ret void
+;
+  store i32 1, i32* %P
+  call void @may_throw_func()
+  br label %bb1
+bb1:
+  store i32 0, i32* %P
+  call void @may_throw_func()
+  ret void
+}
+
+define void @Atest1C(i32* %P) {
+; CHECK-LABEL: @Atest1C(
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  call void @may_throw_func()
+  store i32 1, i32* %P
+  br label %bb1
+bb1:
+  call void @may_throw_func()
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @Atest2(i32* %P) {
+; CHECK-LABEL: @Atest2(
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  store i32 1, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  call void @may_throw_func()
+  br label %bb3
+bb2:
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+; we could remove all stores here
+define void @Atest3D() {
+; CHECK-LABEL: @Atest3D(
+; CHECK-NEXT:    [[P:%.*]] = alloca i32, align 1
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    ret void
+;
+  %P = alloca i32, i32 1, align 1
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  store i32 1, i32* %P
+  br label %bb3
+bb3:
+  call void @may_throw_func()
+  ret void
+}
+
+define void @Atest3A(i32* %P) {
+; CHECK-LABEL: @Atest3A(
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  call void @may_throw_func()
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  store i32 0, i32* %P
+  call void @may_throw_func()
+  br label %bb3
+bb2:
+  store i32 0, i32* %P
+  call void @may_throw_func()
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @Atest3B(i32* %P) {
+; CHECK-LABEL: @Atest3B(
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    ret void
+;
+  call void @may_throw_func()
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  store i32 0, i32* %P
+  call void @may_throw_func()
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  call void @may_throw_func()
+  ret void
+}
+
+define void @AtestA3A(i32* %P) {
+; CHECK-LABEL: @AtestA3A(
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  call void @may_throw_func()
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  call void @may_throw_func()
+  store i32 0, i32* %P
+  br label %bb3
+bb2:
+  store i32 0, i32* %P
+  call void @may_throw_func()
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @AtestA3B(i32* %P) {
+; CHECK-LABEL: @AtestA3B(
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    ret void
+;
+  call void @may_throw_func()
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  call void @may_throw_func()
+  store i32 0, i32* %P
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  call void @may_throw_func()
+  ret void
+}
+define void @AtestB3A(i32* %P) {
+; CHECK-LABEL: @AtestB3A(
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  call void @may_throw_func()
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  store i32 0, i32* %P
+  call void @may_throw_func()
+  br label %bb3
+bb2:
+  call void @may_throw_func()
+  store i32 0, i32* %P
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @AtestB3B(i32* %P) {
+; CHECK-LABEL: @AtestB3B(
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  call void @may_throw_func()
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  store i32 0, i32* %P
+  call void @may_throw_func()
+  br label %bb3
+bb3:
+  call void @may_throw_func()
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @Atest5(i32* %P) {
+; CHECK-LABEL: @Atest5(
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    ret void
+;
+  br i1 true, label %bb1, label %bb2
+bb1:
+  call void @may_throw_func()
+  store i32 1, i32* %P
+  br label %bb3
+bb2:
+  call void @may_throw_func()
+  store i32 1, i32* %P
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  call void @may_throw_func()
+  ret void
+}
+
+define void @Atest5C(i32* %P) {
+; CHECK-LABEL: @Atest5C(
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    ret void
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  call void @may_throw_func()
+  store i32 1, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  store i32 0, i32* %P
+  call void @may_throw_func()
+  ret void
+bb2:
+  store i32 1, i32* %P
+  call void @may_throw_func()
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @Atest5D(i32* %P) {
+; CHECK-LABEL: @Atest5D(
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  call void @may_throw_func()
+  store i32 1, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  call void @may_throw_func()
+  br label %bb4
+bb4:
+  store i32 0, i32* %P
+  ret void
+bb2:
+  store i32 1, i32* %P
+  call void @may_throw_func()
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @Atest6(i32* %P) {
+; CHECK-LABEL: @Atest6(
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  call void @may_throw_func()
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @Atest6A(i32* %P) {
+; CHECK-LABEL: @Atest6A(
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[BB5:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  br label %bb4
+bb4:
+  call void @may_throw_func()
+  br label %bb5
+bb5:
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @Atest14(i32* %P) {
+; CHECK-LABEL: @Atest14(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 false, label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    ret void
+;
+entry:
+  call void @may_throw_func()
+  store i32 1, i32* %P
+  br label %for
+for:
+  store i32 0, i32* %P
+  br i1 false, label %for, label %end
+end:
+  call void @may_throw_func()
+  ret void
+}
+
+define void @Atest14A(i32* %P) {
+; CHECK-LABEL: @Atest14A(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br i1 false, label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  call void @may_throw_func()
+  store i32 1, i32* %P
+  br label %for
+for:
+  store i32 0, i32* %P
+  call void @may_throw_func()
+  store i32 0, i32* %P
+  br i1 false, label %for, label %end
+end:
+  store i32 0, i32* %P
+  call void @may_throw_func()
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @Atest14B(i32* %P) {
+; CHECK-LABEL: @Atest14B(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br label [[FOR]]
+; CHECK:       for:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    br i1 false, label [[BB1:%.*]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @may_throw_func()
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i32 0, i32* %P
+  call void @may_throw_func()
+  store i32 0, i32* %P
+  br label %for
+bb1:
+  store i32 0, i32* %P
+  call void @may_throw_func()
+  store i32 0, i32* %P
+  br label %for
+for:
+  store i32 0, i32* %P
+  call void @may_throw_func()
+  store i32 0, i32* %P
+  br i1 false, label %bb1, label %end
+end:
+  store i32 0, i32* %P
+  call void @may_throw_func()
+  store i32 0, i32* %P
+  ret void
+}
+
+; ------
+
+define void @Btest1(i32* %P) {
+; CHECK-LABEL: @Btest1(
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    ret void
+;
+  fence seq_cst
+  store i32 1, i32* %P
+  br label %bb1
+bb1:
+  store i32 0, i32* %P
+  fence seq_cst
+  ret void
+}
+
+define void @Btest1B(i32* %P) {
+; CHECK-LABEL: @Btest1B(
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    ret void
+;
+  store i32 1, i32* %P
+  fence seq_cst
+  br label %bb1
+bb1:
+  store i32 0, i32* %P
+  fence seq_cst
+  ret void
+}
+
+define void @Btest1C(i32* %P) {
+; CHECK-LABEL: @Btest1C(
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  fence seq_cst
+  store i32 1, i32* %P
+  br label %bb1
+bb1:
+  fence seq_cst
+  store i32 0, i32* %P
+  ret void
+}
+
+
+define void @Btest2(i32* %P) {
+; CHECK-LABEL: @Btest2(
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  store i32 1, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  fence seq_cst
+  br label %bb3
+bb2:
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+; we could remove all the stores here.
+define void @Btest3D() {
+; CHECK-LABEL: @Btest3D(
+; CHECK-NEXT:    [[P:%.*]] = alloca i32, align 1
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    ret void
+;
+  %P = alloca i32, i32 1, align 1
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  store i32 1, i32* %P
+  br label %bb3
+bb3:
+  fence seq_cst
+  ret void
+}
+
+define void @Btest3A(i32* %P) {
+; CHECK-LABEL: @Btest3A(
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  fence seq_cst
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  store i32 0, i32* %P
+  fence seq_cst
+  br label %bb3
+bb2:
+  store i32 0, i32* %P
+  fence seq_cst
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @Btest3B(i32* %P) {
+; CHECK-LABEL: @Btest3B(
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    ret void
+;
+  fence seq_cst
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  store i32 0, i32* %P
+  fence seq_cst
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  fence seq_cst
+  ret void
+}
+
+define void @BtestA3A(i32* %P) {
+; CHECK-LABEL: @BtestA3A(
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  fence seq_cst
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  fence seq_cst
+  store i32 0, i32* %P
+  br label %bb3
+bb2:
+  store i32 0, i32* %P
+  fence seq_cst
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @BtestA3B(i32* %P) {
+; CHECK-LABEL: @BtestA3B(
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    ret void
+;
+  fence seq_cst
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  fence seq_cst
+  store i32 0, i32* %P
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  fence seq_cst
+  ret void
+}
+define void @BtestB3A(i32* %P) {
+; CHECK-LABEL: @BtestB3A(
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  fence seq_cst
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  store i32 0, i32* %P
+  fence seq_cst
+  br label %bb3
+bb2:
+  fence seq_cst
+  store i32 0, i32* %P
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @BtestB3B(i32* %P) {
+; CHECK-LABEL: @BtestB3B(
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  fence seq_cst
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  store i32 0, i32* %P
+  fence seq_cst
+  br label %bb3
+bb3:
+  fence seq_cst
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @Btest5(i32* %P) {
+; CHECK-LABEL: @Btest5(
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    ret void
+;
+  br i1 true, label %bb1, label %bb2
+bb1:
+  fence seq_cst
+  store i32 1, i32* %P
+  br label %bb3
+bb2:
+  fence seq_cst
+  store i32 1, i32* %P
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  fence seq_cst
+  ret void
+}
+
+define void @Btest5C(i32* %P) {
+; CHECK-LABEL: @Btest5C(
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    ret void
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  fence seq_cst
+  store i32 1, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  store i32 0, i32* %P
+  fence seq_cst
+  ret void
+bb2:
+  store i32 1, i32* %P
+  fence seq_cst
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @Btest5D(i32* %P) {
+; CHECK-LABEL: @Btest5D(
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  fence seq_cst
+  store i32 1, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  fence seq_cst
+  br label %bb4
+bb4:
+  store i32 0, i32* %P
+  ret void
+bb2:
+  store i32 1, i32* %P
+  fence seq_cst
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @Btest6(i32* %P) {
+; CHECK-LABEL: @Btest6(
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  fence seq_cst
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @Btest6A(i32* %P) {
+; CHECK-LABEL: @Btest6A(
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[BB5:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  br label %bb4
+bb4:
+  fence seq_cst
+  br label %bb5
+bb5:
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @Btest14(i32* %P) {
+; CHECK-LABEL: @Btest14(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 false, label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    ret void
+;
+entry:
+  fence seq_cst
+  store i32 1, i32* %P
+  br label %for
+for:
+  store i32 0, i32* %P
+  br i1 false, label %for, label %end
+end:
+  fence seq_cst
+  ret void
+}
+
+define void @Btest14A(i32* %P) {
+; CHECK-LABEL: @Btest14A(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br i1 false, label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  fence seq_cst
+  store i32 1, i32* %P
+  br label %for
+for:
+  store i32 0, i32* %P
+  fence seq_cst
+  store i32 0, i32* %P
+  br i1 false, label %for, label %end
+end:
+  store i32 0, i32* %P
+  fence seq_cst
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @Btest14B(i32* %P) {
+; CHECK-LABEL: @Btest14B(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br label [[FOR]]
+; CHECK:       for:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    br i1 false, label [[BB1:%.*]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    fence seq_cst
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i32 0, i32* %P
+  fence seq_cst
+  store i32 0, i32* %P
+  br label %for
+bb1:
+  store i32 0, i32* %P
+  fence seq_cst
+  store i32 0, i32* %P
+  br label %for
+for:
+  store i32 0, i32* %P
+  fence seq_cst
+  store i32 0, i32* %P
+  br i1 false, label %bb1, label %end
+end:
+  store i32 0, i32* %P
+  fence seq_cst
+  store i32 0, i32* %P
+  ret void
+}

llvm/test/Transforms/DeadStoreElimination/multiblock-post-dom.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt %s -basicaa -dse -enable-dse-memoryssa -S | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+declare void @unknown_func()
+declare void @may_throw_func() readnone
+declare void @llvm.lifetime.end.p0i32(i64, i32* nocapture) nounwind
+declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) nounwind
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i1) nounwind
+declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
+declare noalias i8* @malloc(i32)
+declare void @free(i8* nocapture)
+
+define void @test2(i32* %P) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    ret void
+;
+  store i32 1, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @test3(i32* %P) {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  store i32 1, i32* %P
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @test3D() {
+; CHECK-LABEL: @test3D(
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  %P = alloca i32, i32 1, align 1
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  store i32 1, i32* %P
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @test3A(i32* %P) {
+; CHECK-LABEL: @test3A(
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  store i32 0, i32* %P
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @test5(i32* %P) {
+; CHECK-LABEL: @test5(
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    ret void
+;
+  br i1 true, label %bb1, label %bb2
+bb1:
+  store i32 1, i32* %P
+  br label %bb3
+bb2:
+  store i32 1, i32* %P
+  br label %bb3
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @test5A(i32* %P) {
+; CHECK-LABEL: @test5A(
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  store i32 1, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  store i32 0, i32* %P
+  br label %bb3
+bb2:
+  store i32 1, i32* %P
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @test5B(i32* %P) {
+; CHECK-LABEL: @test5B(
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    ret void
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  store i32 1, i32* %P
+  br i1 true, label %bb1, label %bb2
+bb1:
+  store i32 0, i32* %P
+  ret void
+bb2:
+  store i32 1, i32* %P
+  br label %bb3
+bb3:
+  ret void
+}
+
+define void @test8(i32* %P) {
+; CHECK-LABEL: @test8(
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br i1 true, label [[BB3:%.*]], label [[BB4:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 true, label [[BB3]], label [[BB4]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    ret void
+; CHECK:       bb4:
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  br i1 true, label %bb1, label %bb2
+bb1:
+  store i32 1, i32* %P
+  br i1 true, label %bb3, label %bb4
+bb2:
+  store i32 1, i32* %P
+  br i1 true, label %bb3, label %bb4
+bb3:
+  store i32 0, i32* %P
+  ret void
+bb4:
+  store i32 1, i32* %P
+  ret void
+}
+
+define void @test9A(i32* %P) {
+; CHECK-LABEL: @test9A(
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB3:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br i1 true, label [[BB4]], label [[BB5:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    br i1 true, label [[BB6:%.*]], label [[BB7:%.*]]
+; CHECK:       bb6:
+; CHECK-NEXT:    br i1 true, label [[BB3]], label [[BB7]]
+; CHECK:       bb7:
+; CHECK-NEXT:    br label [[BB8:%.*]]
+; CHECK:       bb8:
+; CHECK-NEXT:    br i1 true, label [[BB1]], label [[BB9:%.*]]
+; CHECK:       bb9:
+; CHECK-NEXT:    ret void
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb3
+bb1:
+  br label %bb4
+bb4:
+  br i1 true, label %bb4, label %bb5
+bb5:
+  br i1 true, label %bb6, label %bb7
+bb6:
+  br i1 true, label %bb3, label %bb7
+bb7:
+  br label %bb8
+bb8:
+  br i1 true, label %bb1, label %bb9
+bb9:
+  ret void
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+; the store in the entry block could be removed but the passe stays on the safe side.
+define void @test9E(i32* %P) {
+; CHECK-LABEL: @test9E(
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB3:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br i1 true, label [[BB4]], label [[BB5:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    br i1 true, label [[BB6:%.*]], label [[BB7:%.*]]
+; CHECK:       bb6:
+; CHECK-NEXT:    br i1 true, label [[BB3]], label [[BB7]]
+; CHECK:       bb7:
+; CHECK-NEXT:    br label [[BB8:%.*]]
+; CHECK:       bb8:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br i1 true, label [[BB1]], label [[BB9:%.*]]
+; CHECK:       bb9:
+; CHECK-NEXT:    ret void
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    ret void
+;
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb3
+bb1:
+  br label %bb4
+bb4:
+  br i1 true, label %bb4, label %bb5
+bb5:
+  br i1 true, label %bb6, label %bb7
+bb6:
+  br i1 true, label %bb3, label %bb7
+bb7:
+  br label %bb8
+bb8:
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb9
+bb9:
+  ret void
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @test9B() {
+; CHECK-LABEL: @test9B(
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB3:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br i1 true, label [[BB4:%.*]], label [[BB5:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    br i1 true, label [[BB6:%.*]], label [[BB7:%.*]]
+; CHECK:       bb6:
+; CHECK-NEXT:    br i1 true, label [[BB3]], label [[BB7]]
+; CHECK:       bb7:
+; CHECK-NEXT:    br label [[BB8:%.*]]
+; CHECK:       bb8:
+; CHECK-NEXT:    br i1 true, label [[BB1]], label [[BB9:%.*]]
+; CHECK:       bb9:
+; CHECK-NEXT:    ret void
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  %P = alloca i32, i32 1, align 4
+  store i32 0, i32* %P
+  br i1 true, label %bb1, label %bb3
+bb1:
+  br label %bb3
+bb4:
+  br i1 true, label %bb4, label %bb5
+bb5:
+  br i1 true, label %bb6, label %bb7
+bb6:
+  br i1 true, label %bb3, label %bb7
+bb7:
+  br label %bb8
+bb8:
+  br i1 true, label %bb1, label %bb9
+bb9:
+  ret void
+bb3:
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @test16(i32* %P) {
+; CHECK-LABEL: @test16(
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB3:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    call void @free(i8* [[P2]])
+; CHECK-NEXT:    ret void
+;
+  %P2 = bitcast i32* %P to i8*
+  store i32 1, i32* %P
+  br i1 true, label %bb1, label %bb3
+bb1:
+  store i32 1, i32* %P
+  br label %bb3
+bb3:
+  call void @free(i8* %P2)
+  ret void
+}
+
+define void @test18(i32* %P) {
+; CHECK-LABEL: @test18(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    store i8 1, i8* [[P2]]
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P]]
+; CHECK-NEXT:    store i8 2, i8* [[P2]]
+; CHECK-NEXT:    br i1 false, label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %P2 = bitcast i32* %P to i8*
+  store i32 0, i32* %P
+  br label %for
+for:
+  store i8 1, i8* %P2
+  %x = load i32, i32* %P
+  store i8 2, i8* %P2
+  br i1 false, label %for, label %end
+end:
+  ret void
+}
+
+
+define void @test19(i32* %P) {
+; CHECK-LABEL: @test19(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
+; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1
+  %p3 = bitcast i32* %arrayidx0 to i8*
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  %arrayidx1 = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %arrayidx1, align 4
+  br label %bb3
+bb3:
+  ret void
+}
+
+
+define void @test20(i32* %P) {
+; CHECK-LABEL: @test20(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
+; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1
+  %p3 = bitcast i32* %arrayidx0 to i8*
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
+  br i1 true, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  br label %bb3
+bb3:
+  %arrayidx1 = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %arrayidx1, align 4
+  ret void
+}
+
+
+define void @test21(i32* %P) {
+; CHECK-LABEL: @test21(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
+; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    br i1 false, label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1
+  %p3 = bitcast i32* %arrayidx0 to i8*
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
+  br label %for
+for:
+  %arrayidx1 = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %arrayidx1, align 4
+  br i1 false, label %for, label %end
+end:
+  ret void
+}
+
+define void @test21A(i32* %P) {
+; CHECK-LABEL: @test21A(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P:%.*]]
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    [[X1:%.*]] = trunc i32 [[X]] to i1
+; CHECK-NEXT:    br i1 [[X1]], label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for
+for:
+  %x = load i32, i32* %P
+  store i32 1, i32* %P, align 4
+  %x1 = trunc i32 %x to i1
+  br i1 %x1, label %for, label %end
+end:
+  store i32 1, i32* %P, align 4
+  ret void
+}
+
+
+define void @test25(i32* %P) {
+; CHECK-LABEL: @test25(
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P]] to i8*
+; CHECK-NEXT:    br i1 true, label [[BB2:%.*]], label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    call void @free(i8* [[P2]])
+; CHECK-NEXT:    ret void
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  store i32 1, i32* %P
+  %P2 = bitcast i32* %P to i8*
+  br i1 true, label %bb2, label %bb1
+bb1:
+  br label %bb3
+bb2:
+  call void @free(i8* %P2)
+  ret void
+bb3:
+  ret void
+}
+
+
+define i8* @test26() {
+; CHECK-LABEL: @test26(
+; CHECK-NEXT:  bb1:
+; CHECK-NEXT:    br i1 true, label [[BB2:%.*]], label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[M:%.*]] = call noalias i8* @malloc(i32 10)
+; CHECK-NEXT:    store i8 1, i8* [[M]]
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[R:%.*]] = phi i8* [ null, [[BB1:%.*]] ], [ [[M]], [[BB2]] ]
+; CHECK-NEXT:    ret i8* [[R]]
+;
+bb1:
+  br i1 true, label %bb2, label %bb3
+bb2:
+  %m = call noalias i8* @malloc(i32 10)
+  store i8 1, i8* %m
+  br label %bb3
+bb3:
+  %r = phi i8* [ null, %bb1 ], [ %m, %bb2 ]
+  ret i8* %r
+}
+
+define void @test27() {
+; CHECK-LABEL: @test27(
+; CHECK-NEXT:  bb1:
+; CHECK-NEXT:    br i1 true, label [[BB2:%.*]], label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[M:%.*]] = call noalias i8* @malloc(i32 10)
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[R:%.*]] = phi i8* [ null, [[BB1:%.*]] ], [ [[M]], [[BB2]] ]
+; CHECK-NEXT:    ret void
+;
+bb1:
+  br i1 true, label %bb2, label %bb3
+bb2:
+  %m = call noalias i8* @malloc(i32 10)
+  store i8 1, i8* %m
+  br label %bb3
+bb3:
+  %r = phi i8* [ null, %bb1 ], [ %m, %bb2 ]
+  ret void
+}
+
+define void @test_loop(i32 %N, i32* noalias nocapture readonly %A, i32* noalias nocapture readonly %x, i32* noalias nocapture %b) local_unnamed_addr {
+; CHECK-LABEL: @test_loop(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP27:%.*]] = icmp sgt i32 [[N:%.*]], 0
+; CHECK-NEXT:    br i1 [[CMP27]], label [[FOR_BODY4_LR_PH_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]
+; CHECK:       for.body4.lr.ph.preheader:
+; CHECK-NEXT:    br label [[FOR_BODY4_LR_PH:%.*]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    ret void
+; CHECK:       for.body4.lr.ph:
+; CHECK-NEXT:    [[I_028:%.*]] = phi i32 [ [[INC11:%.*]], [[FOR_COND_CLEANUP3:%.*]] ], [ 0, [[FOR_BODY4_LR_PH_PREHEADER]] ]
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i32 [[I_028]]
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[I_028]], [[N]]
+; CHECK-NEXT:    br label [[FOR_BODY4:%.*]]
+; CHECK:       for.cond.cleanup3:
+; CHECK-NEXT:    store i32 [[ADD9:%.*]], i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[INC11]] = add nuw nsw i32 [[I_028]], 1
+; CHECK-NEXT:    [[EXITCOND29:%.*]] = icmp eq i32 [[INC11]], [[N]]
+; CHECK-NEXT:    br i1 [[EXITCOND29]], label [[FOR_COND_CLEANUP]], label [[FOR_BODY4_LR_PH]]
+; CHECK:       for.body4:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ 0, [[FOR_BODY4_LR_PH]] ], [ [[ADD9]], [[FOR_BODY4]] ]
+; CHECK-NEXT:    [[J_026:%.*]] = phi i32 [ 0, [[FOR_BODY4_LR_PH]] ], [ [[INC:%.*]], [[FOR_BODY4]] ]
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[J_026]], [[MUL]]
+; CHECK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i32 [[ADD]]
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[ARRAYIDX5]], align 4
+; CHECK-NEXT:    [[ARRAYIDX6:%.*]] = getelementptr inbounds i32, i32* [[X:%.*]], i32 [[J_026]]
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[ARRAYIDX6]], align 4
+; CHECK-NEXT:    [[MUL7:%.*]] = mul nsw i32 [[TMP2]], [[TMP1]]
+; CHECK-NEXT:    [[ADD9]] = add nsw i32 [[MUL7]], [[TMP0]]
+; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[J_026]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], [[N]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP3]], label [[FOR_BODY4]]
+;
+entry:
+  %cmp27 = icmp sgt i32 %N, 0
+  br i1 %cmp27, label %for.body4.lr.ph.preheader, label %for.cond.cleanup
+
+for.body4.lr.ph.preheader:                        ; preds = %entry
+  br label %for.body4.lr.ph
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3, %entry
+  ret void
+
+for.body4.lr.ph:                                  ; preds = %for.body4.lr.ph.preheader, %for.cond.cleanup3
+  %i.028 = phi i32 [ %inc11, %for.cond.cleanup3 ], [ 0, %for.body4.lr.ph.preheader ]
+  %arrayidx = getelementptr inbounds i32, i32* %b, i32 %i.028
+  store i32 0, i32* %arrayidx, align 4
+  %mul = mul nsw i32 %i.028, %N
+  br label %for.body4
+
+for.cond.cleanup3:                                ; preds = %for.body4
+  store i32 %add9, i32* %arrayidx, align 4
+  %inc11 = add nuw nsw i32 %i.028, 1
+  %exitcond29 = icmp eq i32 %inc11, %N
+  br i1 %exitcond29, label %for.cond.cleanup, label %for.body4.lr.ph
+
+for.body4:                                        ; preds = %for.body4, %for.body4.lr.ph
+  %0 = phi i32 [ 0, %for.body4.lr.ph ], [ %add9, %for.body4 ]
+  %j.026 = phi i32 [ 0, %for.body4.lr.ph ], [ %inc, %for.body4 ]
+  %add = add nsw i32 %j.026, %mul
+  %arrayidx5 = getelementptr inbounds i32, i32* %A, i32 %add
+  %1 = load i32, i32* %arrayidx5, align 4
+  %arrayidx6 = getelementptr inbounds i32, i32* %x, i32 %j.026
+  %2 = load i32, i32* %arrayidx6, align 4
+  %mul7 = mul nsw i32 %2, %1
+  %add9 = add nsw i32 %mul7, %0
+  %inc = add nuw nsw i32 %j.026, 1
+  %exitcond = icmp eq i32 %inc, %N
+  br i1 %exitcond, label %for.cond.cleanup3, label %for.body4
+}
+
+define void @test52(i32* %P, i1 %B) {
+; CHECK-LABEL: @test52(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[FROMBOOL:%.*]] = zext i1 [[B:%.*]] to i8
+; CHECK-NEXT:    [[TOBOOL:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[IF_THEN:%.*]], label [[IF_END15:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[TOBOOL1:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL1]], label [[IF_THEN2:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then2:
+; CHECK-NEXT:    br label [[IF_END14:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[TOBOOL3:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL3]], label [[IF_THEN4:%.*]], label [[IF_ELSE5:%.*]]
+; CHECK:       if.then4:
+; CHECK-NEXT:    br label [[IF_END13:%.*]]
+; CHECK:       if.else5:
+; CHECK-NEXT:    [[TOBOOL6:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL6]], label [[IF_THEN7:%.*]], label [[IF_ELSE8:%.*]]
+; CHECK:       if.then7:
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[IF_END12:%.*]]
+; CHECK:       if.else8:
+; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
+; CHECK:       while.cond:
+; CHECK-NEXT:    [[TOBOOL9:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL9]], label [[WHILE_BODY:%.*]], label [[WHILE_END:%.*]]
+; CHECK:       while.body:
+; CHECK-NEXT:    br i1 [[B]], label [[IF_THEN11:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then11:
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    br label [[WHILE_COND]]
+; CHECK:       while.end:
+; CHECK-NEXT:    br label [[IF_END12]]
+; CHECK:       if.end12:
+; CHECK-NEXT:    br label [[IF_END13]]
+; CHECK:       if.end13:
+; CHECK-NEXT:    br label [[IF_END14]]
+; CHECK:       if.end14:
+; CHECK-NEXT:    br label [[IF_END15]]
+; CHECK:       if.end15:
+; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  %frombool = zext i1 %B to i8
+  store i32 1, i32* %P, align 4
+  %tobool = trunc i8 %frombool to i1
+  br i1 %tobool, label %if.then, label %if.end15
+
+if.then:                                          ; preds = %entry
+  %tobool1 = trunc i8 %frombool to i1
+  store i32 1, i32* %P, align 4
+  br i1 %tobool1, label %if.then2, label %if.else
+
+if.then2:                                         ; preds = %if.then
+  store i32 1, i32* %P, align 4
+  br label %if.end14
+
+if.else:                                          ; preds = %if.then
+  %tobool3 = trunc i8 %frombool to i1
+  store i32 1, i32* %P, align 4
+  br i1 %tobool3, label %if.then4, label %if.else5
+
+if.then4:                                         ; preds = %if.else
+  store i32 1, i32* %P, align 4
+  br label %if.end13
+
+if.else5:                                         ; preds = %if.else
+  %tobool6 = trunc i8 %frombool to i1
+  store i32 1, i32* %P, align 4
+  br i1 %tobool6, label %if.then7, label %if.else8
+
+if.then7:                                         ; preds = %if.else5
+  store i32 1, i32* %P, align 4
+  call void @unknown_func()
+  store i32 1, i32* %P, align 4
+  br label %if.end12
+
+if.else8:                                         ; preds = %if.else5
+  store i32 1, i32* %P, align 4
+  br label %while.cond
+
+while.cond:                                       ; preds = %if.end, %if.else8
+  %tobool9 = trunc i8 %frombool to i1
+  store i32 1, i32* %P, align 4
+  br i1 %tobool9, label %while.body, label %while.end
+
+while.body:                                       ; preds = %while.cond
+  store i32 1, i32* %P, align 4
+  br i1 %B, label %if.then11, label %if.end
+
+if.then11:                                        ; preds = %while.body
+  store i32 1, i32* %P, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.then11, %while.body
+  store i32 1, i32* %P, align 4
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  store i32 1, i32* %P, align 4
+  br label %if.end12
+
+if.end12:                                         ; preds = %while.end, %if.then7
+  store i32 1, i32* %P, align 4
+  br label %if.end13
+
+if.end13:                                         ; preds = %if.end12, %if.then4
+  store i32 1, i32* %P, align 4
+  br label %if.end14
+
+if.end14:                                         ; preds = %if.end13, %if.then2
+  store i32 1, i32* %P, align 4
+  br label %if.end15
+
+if.end15:                                         ; preds = %if.end14, %entry
+  store i32 0, i32* %P, align 4
+  ret void
+}
+
+declare void @may_write_func(i32*) nounwind writeonly
+
+define void @test53(i32* %P, i1 %B) {
+; CHECK-LABEL: @test53(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[FROMBOOL:%.*]] = zext i1 [[B:%.*]] to i8
+; CHECK-NEXT:    [[TOBOOL:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[IF_THEN:%.*]], label [[IF_END15:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[TOBOOL1:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL1]], label [[IF_THEN2:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then2:
+; CHECK-NEXT:    br label [[IF_END14:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[TOBOOL3:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL3]], label [[IF_THEN4:%.*]], label [[IF_ELSE5:%.*]]
+; CHECK:       if.then4:
+; CHECK-NEXT:    br label [[IF_END13:%.*]]
+; CHECK:       if.else5:
+; CHECK-NEXT:    [[TOBOOL6:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL6]], label [[IF_THEN7:%.*]], label [[IF_ELSE8:%.*]]
+; CHECK:       if.then7:
+; CHECK-NEXT:    call void @may_write_func(i32* [[P:%.*]])
+; CHECK-NEXT:    br label [[IF_END12:%.*]]
+; CHECK:       if.else8:
+; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
+; CHECK:       while.cond:
+; CHECK-NEXT:    [[TOBOOL9:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL9]], label [[WHILE_BODY:%.*]], label [[WHILE_END:%.*]]
+; CHECK:       while.body:
+; CHECK-NEXT:    br i1 [[B]], label [[IF_THEN11:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then11:
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    br label [[WHILE_COND]]
+; CHECK:       while.end:
+; CHECK-NEXT:    br label [[IF_END12]]
+; CHECK:       if.end12:
+; CHECK-NEXT:    br label [[IF_END13]]
+; CHECK:       if.end13:
+; CHECK-NEXT:    br label [[IF_END14]]
+; CHECK:       if.end14:
+; CHECK-NEXT:    br label [[IF_END15]]
+; CHECK:       if.end15:
+; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  %frombool = zext i1 %B to i8
+  store i32 1, i32* %P, align 4
+  %tobool = trunc i8 %frombool to i1
+  br i1 %tobool, label %if.then, label %if.end15
+
+if.then:                                          ; preds = %entry
+  store i32 1, i32* %P, align 4
+  %tobool1 = trunc i8 %frombool to i1
+  br i1 %tobool1, label %if.then2, label %if.else
+
+if.then2:                                         ; preds = %if.then
+  store i32 1, i32* %P, align 4
+  br label %if.end14
+
+if.else:                                          ; preds = %if.then
+  store i32 1, i32* %P, align 4
+  %tobool3 = trunc i8 %frombool to i1
+  br i1 %tobool3, label %if.then4, label %if.else5
+
+if.then4:                                         ; preds = %if.else
+  store i32 1, i32* %P, align 4
+  br label %if.end13
+
+if.else5:                                         ; preds = %if.else
+  %tobool6 = trunc i8 %frombool to i1
+  store i32 1, i32* %P, align 4
+  br i1 %tobool6, label %if.then7, label %if.else8
+
+if.then7:                                         ; preds = %if.else5
+  store i32 1, i32* %P, align 4
+  call void @may_write_func(i32* %P)
+  store i32 1, i32* %P, align 4
+  br label %if.end12
+
+if.else8:                                         ; preds = %if.else5
+  store i32 1, i32* %P, align 4
+  br label %while.cond
+
+while.cond:                                       ; preds = %if.end, %if.else8
+  %tobool9 = trunc i8 %frombool to i1
+  store i32 1, i32* %P, align 4
+  br i1 %tobool9, label %while.body, label %while.end
+
+while.body:                                       ; preds = %while.cond
+  store i32 1, i32* %P, align 4
+  br i1 %B, label %if.then11, label %if.end
+
+if.then11:                                        ; preds = %while.body
+  store i32 1, i32* %P, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.then11, %while.body
+  store i32 1, i32* %P, align 4
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  store i32 1, i32* %P, align 4
+  br label %if.end12
+
+if.end12:                                         ; preds = %while.end, %if.then7
+  store i32 1, i32* %P, align 4
+  br label %if.end13
+
+if.end13:                                         ; preds = %if.end12, %if.then4
+  store i32 1, i32* %P, align 4
+  br label %if.end14
+
+if.end14:                                         ; preds = %if.end13, %if.then2
+  store i32 1, i32* %P, align 4
+  br label %if.end15
+
+if.end15:                                         ; preds = %if.end14, %entry
+  store i32 0, i32* %P, align 4
+  ret void
+}
+
+define void @test56(i32* %P, i1 %B) {
+; CHECK-LABEL: @test56(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[FROMBOOL:%.*]] = zext i1 [[B:%.*]] to i8
+; CHECK-NEXT:    [[TOBOOL:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[IF_THEN:%.*]], label [[IF_END15:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[TOBOOL1:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL1]], label [[IF_THEN2:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then2:
+; CHECK-NEXT:    br label [[IF_END14:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[TOBOOL3:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL3]], label [[IF_THEN4:%.*]], label [[IF_ELSE5:%.*]]
+; CHECK:       if.then4:
+; CHECK-NEXT:    br label [[IF_END13:%.*]]
+; CHECK:       if.else5:
+; CHECK-NEXT:    [[TOBOOL6:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL6]], label [[IF_THEN7:%.*]], label [[IF_ELSE8:%.*]]
+; CHECK:       if.then7:
+; CHECK-NEXT:    br label [[IF_END12:%.*]]
+; CHECK:       if.else8:
+; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
+; CHECK:       while.cond:
+; CHECK-NEXT:    [[TOBOOL9:%.*]] = trunc i8 [[FROMBOOL]] to i1
+; CHECK-NEXT:    br i1 [[TOBOOL9]], label [[WHILE_BODY:%.*]], label [[WHILE_END:%.*]]
+; CHECK:       while.body:
+; CHECK-NEXT:    br i1 [[B]], label [[IF_THEN11:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then11:
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    ret void
+; CHECK:       if.end:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    br label [[WHILE_COND]]
+; CHECK:       while.end:
+; CHECK-NEXT:    br label [[IF_END12]]
+; CHECK:       if.end12:
+; CHECK-NEXT:    br label [[IF_END13]]
+; CHECK:       if.end13:
+; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
+; CHECK-NEXT:    ret void
+; CHECK:       if.end14:
+; CHECK-NEXT:    br label [[IF_END15]]
+; CHECK:       if.end15:
+; CHECK-NEXT:    call void @llvm.lifetime.end.p0i32(i64 -1, i32* [[P]])
+; CHECK-NEXT:    ret void
+;
+entry:
+  %frombool = zext i1 %B to i8
+  store i32 1, i32* %P, align 4
+  %tobool = trunc i8 %frombool to i1
+  br i1 %tobool, label %if.then, label %if.end15
+
+if.then:                                          ; preds = %entry
+  store i32 1, i32* %P, align 4
+  %tobool1 = trunc i8 %frombool to i1
+  br i1 %tobool1, label %if.then2, label %if.else
+
+if.then2:                                         ; preds = %if.then
+  store i32 1, i32* %P, align 4
+  br label %if.end14
+
+if.else:                                          ; preds = %if.then
+  store i32 1, i32* %P, align 4
+  %tobool3 = trunc i8 %frombool to i1
+  br i1 %tobool3, label %if.then4, label %if.else5
+
+if.then4:                                         ; preds = %if.else
+  store i32 1, i32* %P, align 4
+  br label %if.end13
+
+if.else5:                                         ; preds = %if.else
+  store i32 1, i32* %P, align 4
+  %tobool6 = trunc i8 %frombool to i1
+  br i1 %tobool6, label %if.then7, label %if.else8
+
+if.then7:                                         ; preds = %if.else5
+  store i32 1, i32* %P, align 4
+  br label %if.end12
+
+if.else8:                                         ; preds = %if.else5
+  store i32 1, i32* %P, align 4
+  br label %while.cond
+
+while.cond:                                       ; preds = %if.end, %if.else8
+  store i32 1, i32* %P, align 4
+  %tobool9 = trunc i8 %frombool to i1
+  br i1 %tobool9, label %while.body, label %while.end
+
+while.body:                                       ; preds = %while.cond
+  store i32 1, i32* %P, align 4
+  br i1 %B, label %if.then11, label %if.end
+
+if.then11:                                        ; preds = %while.body
+  store i32 1, i32* %P, align 4
+  ret void
+
+if.end:                                           ; preds = %if.then11, %while.body
+  store i32 1, i32* %P, align 4
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  store i32 1, i32* %P, align 4
+  br label %if.end12
+
+if.end12:                                         ; preds = %while.end, %if.then7
+  store i32 1, i32* %P, align 4
+  br label %if.end13
+
+if.end13:                                         ; preds = %if.end12, %if.then4
+  store i32 1, i32* %P, align 4
+  ret void
+
+if.end14:                                         ; preds = %if.end13, %if.then2
+  store i32 1, i32* %P, align 4
+  br label %if.end15
+
+if.end15:                                         ; preds = %if.end14, %entry
+  call void @llvm.lifetime.end.p0i32(i64 -1, i32* %P)
+  ret void
+}

llvm/test/Transforms/DeadStoreElimination/non-escaping-ptr.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt %s -basicaa -dse -enable-dse-memoryssa -S | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+
+declare i32* @return_first(i32* returned, i32*)
+declare i32* @return_second(i32*, i32* returned)
+declare noalias i8* @malloc(i32)
+
+define void @test1() {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:    ret void
+;
+  %P = alloca i32, i32 1, align 1
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @test2() {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:    ret void
+;
+  %P = alloca i32, i32 1, align 1
+  %P1 = bitcast i32* %P to i8*
+  store i8 0, i8* %P1
+  ret void
+}
+
+define void @test3() {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:    ret void
+;
+  %P = alloca i32, i32 4, align 1
+  %P1 = bitcast i32* %P to i8*
+  %P2 = bitcast i8* %P1 to i32*
+  %P2.gep = getelementptr i32, i32* %P2, i32 4
+  %P3 = bitcast i32* %P2.gep to i8*
+  %P4 = bitcast i8* %P3 to i32*
+  %P5 = bitcast i32* %P4 to i8*
+  store i8 0, i8* %P5
+  ret void
+}
+
+define void @test4() {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  %P = alloca i32, i32 4, align 1
+  %P1 = bitcast i32* %P to i8*
+  %P2 = bitcast i8* %P1 to i32*
+  %P2.gep = getelementptr i32, i32* %P2, i32 4
+  br i1 true, label %bb1, label %bb2
+bb1:
+  %P3.1 = bitcast i32* %P2.gep to i8*
+  br label %bb3
+bb2:
+  %P3.2 = bitcast i32* %P2.gep to i8*
+  br label %bb3
+bb3:
+  %P3 = phi i8* [ %P3.1, %bb1 ], [%P3.2, %bb2 ]
+  %P4 = bitcast i8* %P3 to i32*
+  %P5 = bitcast i32* %P4 to i8*
+  store i8 0, i8* %P5
+  ret void
+}
+
+define void @test5() {
+; CHECK-LABEL: @test5(
+; CHECK-NEXT:    [[P:%.*]] = alloca i32, i32 4, align 1
+; CHECK-NEXT:    [[P1:%.*]] = bitcast i32* [[P]] to i8*
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i8* [[P1]] to i32*
+; CHECK-NEXT:    [[P2_GEP:%.*]] = getelementptr i32, i32* [[P2]], i32 4
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[P3_3:%.*]] = call i32* @return_first(i32* [[P2_GEP]], i32* null)
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[P3_3_I:%.*]] = call i32* @return_second(i32* null, i32* [[P2_GEP]])
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  %P = alloca i32, i32 4, align 1
+  %P1 = bitcast i32* %P to i8*
+  %P2 = bitcast i8* %P1 to i32*
+  %P2.gep = getelementptr i32, i32* %P2, i32 4
+  br i1 true, label %bb1, label %bb2
+bb1:
+  %P3.3 = call i32* @return_first(i32* %P2.gep, i32* null)
+  %P3.1 = bitcast i32* %P3.3 to i8*
+  br label %bb3
+bb2:
+  %P3.3.i = call i32* @return_second(i32* null, i32* %P2.gep)
+  %P3.1.i = bitcast i32* %P3.3.i to i8*
+  br label %bb3
+bb3:
+  %P3 = phi i8* [ %P3.1, %bb1 ], [%P3.1.i, %bb2 ]
+  %P4 = bitcast i8* %P3 to i32*
+  %P5 = bitcast i32* %P4 to i8*
+  store i8 0, i8* %P5
+  ret void
+}
+
+define i8* @test28() {
+; CHECK-LABEL: @test28(
+; CHECK-NEXT:  bb0:
+; CHECK-NEXT:    [[M:%.*]] = call noalias i8* @malloc(i32 10)
+; CHECK-NEXT:    [[MC0:%.*]] = bitcast i8* [[M]] to i8*
+; CHECK-NEXT:    [[MC1:%.*]] = bitcast i8* [[MC0]] to i8*
+; CHECK-NEXT:    [[MC2:%.*]] = bitcast i8* [[MC1]] to i8*
+; CHECK-NEXT:    [[MC3:%.*]] = bitcast i8* [[MC2]] to i8*
+; CHECK-NEXT:    [[MC4:%.*]] = bitcast i8* [[MC3]] to i8*
+; CHECK-NEXT:    [[MC5:%.*]] = bitcast i8* [[MC4]] to i8*
+; CHECK-NEXT:    [[MC6:%.*]] = bitcast i8* [[MC5]] to i8*
+; CHECK-NEXT:    [[M0:%.*]] = bitcast i8* [[MC6]] to i8*
+; CHECK-NEXT:    store i8 2, i8* [[M0]]
+; CHECK-NEXT:    ret i8* [[M0]]
+;
+bb0:
+  %m = call noalias i8* @malloc(i32 10)
+  %mc0 = bitcast i8* %m to i8*
+  %mc1 = bitcast i8* %mc0 to i8*
+  %mc2 = bitcast i8* %mc1 to i8*
+  %mc3 = bitcast i8* %mc2 to i8*
+  %mc4 = bitcast i8* %mc3 to i8*
+  %mc5 = bitcast i8* %mc4 to i8*
+  %mc6 = bitcast i8* %mc5 to i8*
+  %m0 = bitcast i8* %mc6 to i8*
+  store i8 2, i8* %m0
+  ret i8* %m0
+}
+
+define i8* @test28A() {
+; CHECK-LABEL: @test28A(
+; CHECK-NEXT:  bb0:
+; CHECK-NEXT:    ret i8* null
+;
+bb0:
+  %m = call noalias i8* @malloc(i32 10)
+  %mc0 = bitcast i8* %m to i8*
+  %mc1 = bitcast i8* %mc0 to i8*
+  %mc2 = bitcast i8* %mc1 to i8*
+  %mc3 = bitcast i8* %mc2 to i8*
+  %mc4 = bitcast i8* %mc3 to i8*
+  %mc5 = bitcast i8* %mc4 to i8*
+  %mc6 = bitcast i8* %mc5 to i8*
+  %m0 = bitcast i8* %mc6 to i8*
+  store i8 2, i8* %m0
+  ret i8* null
+}
+
+define void @test6() {
+; CHECK-LABEL: @test6(
+; CHECK-NEXT:    [[P:%.*]] = alloca i32, i32 4, align 1
+; CHECK-NEXT:    [[P1:%.*]] = bitcast i32* [[P]] to i8*
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i8* [[P1]] to i32*
+; CHECK-NEXT:    [[P2_GEP:%.*]] = getelementptr i32, i32* [[P2]], i32 4
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[P3_3:%.*]] = call i32* @return_first(i32* [[P2_GEP]], i32* null)
+; CHECK-NEXT:    [[P3_1:%.*]] = bitcast i32* [[P3_3]] to i8*
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[P3_3_I:%.*]] = call i32* @return_second(i32* [[P2_GEP]], i32* null)
+; CHECK-NEXT:    [[P3_1_I:%.*]] = bitcast i32* [[P3_3_I]] to i8*
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P3:%.*]] = phi i8* [ [[P3_1]], [[BB1]] ], [ [[P3_1_I]], [[BB2]] ]
+; CHECK-NEXT:    [[P4:%.*]] = bitcast i8* [[P3]] to i32*
+; CHECK-NEXT:    [[P5:%.*]] = bitcast i32* [[P4]] to i8*
+; CHECK-NEXT:    store i8 0, i8* [[P5]]
+; CHECK-NEXT:    ret void
+;
+  %P = alloca i32, i32 4, align 1
+  %P1 = bitcast i32* %P to i8*
+  %P2 = bitcast i8* %P1 to i32*
+  %P2.gep = getelementptr i32, i32* %P2, i32 4
+  br i1 true, label %bb1, label %bb2
+bb1:
+  %P3.3 = call i32* @return_first(i32* %P2.gep, i32* null)
+  %P3.1 = bitcast i32* %P3.3 to i8*
+  br label %bb3
+bb2:
+  %P3.3.i = call i32* @return_second(i32* %P2.gep, i32* null)
+  %P3.1.i = bitcast i32* %P3.3.i to i8*
+  br label %bb3
+bb3:
+  %P3 = phi i8* [ %P3.1, %bb1 ], [%P3.1.i, %bb2 ]
+  %P4 = bitcast i8* %P3 to i32*
+  %P5 = bitcast i32* %P4 to i8*
+  store i8 0, i8* %P5
+  ret void
+}
+
+define void @testA1(i32* %P) {
+; CHECK-LABEL: @testA1(
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
+; CHECK-NEXT:    ret void
+;
+  store i32 0, i32* %P
+  ret void
+}
+
+define void @testA2(i32* %P) {
+; CHECK-LABEL: @testA2(
+; CHECK-NEXT:    [[P1:%.*]] = bitcast i32* [[P:%.*]] to i8*
+; CHECK-NEXT:    store i8 0, i8* [[P1]]
+; CHECK-NEXT:    ret void
+;
+  %P1 = bitcast i32* %P to i8*
+  store i8 0, i8* %P1
+  ret void
+}
+
+define void @testA3(i32* %P) {
+; CHECK-LABEL: @testA3(
+; CHECK-NEXT:    [[P1:%.*]] = bitcast i32* [[P:%.*]] to i8*
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i8* [[P1]] to i32*
+; CHECK-NEXT:    [[P2_GEP:%.*]] = getelementptr i32, i32* [[P2]], i32 4
+; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[P2_GEP]] to i8*
+; CHECK-NEXT:    [[P4:%.*]] = bitcast i8* [[P3]] to i32*
+; CHECK-NEXT:    [[P5:%.*]] = bitcast i32* [[P4]] to i8*
+; CHECK-NEXT:    store i8 0, i8* [[P5]]
+; CHECK-NEXT:    ret void
+;
+  %P1 = bitcast i32* %P to i8*
+  %P2 = bitcast i8* %P1 to i32*
+  %P2.gep = getelementptr i32, i32* %P2, i32 4
+  %P3 = bitcast i32* %P2.gep to i8*
+  %P4 = bitcast i8* %P3 to i32*
+  %P5 = bitcast i32* %P4 to i8*
+  store i8 0, i8* %P5
+  ret void
+}
+
+define void @testA4(i32* %P) {
+; CHECK-LABEL: @testA4(
+; CHECK-NEXT:    [[P1:%.*]] = bitcast i32* [[P:%.*]] to i8*
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i8* [[P1]] to i32*
+; CHECK-NEXT:    [[P2_GEP:%.*]] = getelementptr i32, i32* [[P2]], i32 4
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[P3_1:%.*]] = bitcast i32* [[P2_GEP]] to i8*
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[P3_2:%.*]] = bitcast i32* [[P2_GEP]] to i8*
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P3:%.*]] = phi i8* [ [[P3_1]], [[BB1]] ], [ [[P3_2]], [[BB2]] ]
+; CHECK-NEXT:    [[P4:%.*]] = bitcast i8* [[P3]] to i32*
+; CHECK-NEXT:    [[P5:%.*]] = bitcast i32* [[P4]] to i8*
+; CHECK-NEXT:    store i8 0, i8* [[P5]]
+; CHECK-NEXT:    ret void
+;
+  %P1 = bitcast i32* %P to i8*
+  %P2 = bitcast i8* %P1 to i32*
+  %P2.gep = getelementptr i32, i32* %P2, i32 4
+  br i1 true, label %bb1, label %bb2
+bb1:
+  %P3.1 = bitcast i32* %P2.gep to i8*
+  br label %bb3
+bb2:
+  %P3.2 = bitcast i32* %P2.gep to i8*
+  br label %bb3
+bb3:
+  %P3 = phi i8* [ %P3.1, %bb1 ], [%P3.2, %bb2 ]
+  %P4 = bitcast i8* %P3 to i32*
+  %P5 = bitcast i32* %P4 to i8*
+  store i8 0, i8* %P5
+  ret void
+}
+
+define void @testA5(i32* %P) {
+; CHECK-LABEL: @testA5(
+; CHECK-NEXT:    [[P1:%.*]] = bitcast i32* [[P:%.*]] to i8*
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i8* [[P1]] to i32*
+; CHECK-NEXT:    [[P2_GEP:%.*]] = getelementptr i32, i32* [[P2]], i32 4
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[P3_3:%.*]] = call i32* @return_first(i32* [[P2_GEP]], i32* null)
+; CHECK-NEXT:    [[P3_1:%.*]] = bitcast i32* [[P3_3]] to i8*
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[P3_3_I:%.*]] = call i32* @return_second(i32* null, i32* [[P2_GEP]])
+; CHECK-NEXT:    [[P3_1_I:%.*]] = bitcast i32* [[P3_3_I]] to i8*
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P3:%.*]] = phi i8* [ [[P3_1]], [[BB1]] ], [ [[P3_1_I]], [[BB2]] ]
+; CHECK-NEXT:    [[P4:%.*]] = bitcast i8* [[P3]] to i32*
+; CHECK-NEXT:    [[P5:%.*]] = bitcast i32* [[P4]] to i8*
+; CHECK-NEXT:    store i8 0, i8* [[P5]]
+; CHECK-NEXT:    ret void
+;
+  %P1 = bitcast i32* %P to i8*
+  %P2 = bitcast i8* %P1 to i32*
+  %P2.gep = getelementptr i32, i32* %P2, i32 4
+  br i1 true, label %bb1, label %bb2
+bb1:
+  %P3.3 = call i32* @return_first(i32* %P2.gep, i32* null)
+  %P3.1 = bitcast i32* %P3.3 to i8*
+  br label %bb3
+bb2:
+  %P3.3.i = call i32* @return_second(i32* null, i32* %P2.gep)
+  %P3.1.i = bitcast i32* %P3.3.i to i8*
+  br label %bb3
+bb3:
+  %P3 = phi i8* [ %P3.1, %bb1 ], [%P3.1.i, %bb2 ]
+  %P4 = bitcast i8* %P3 to i32*
+  %P5 = bitcast i32* %P4 to i8*
+  store i8 0, i8* %P5
+  ret void
+}