[SimplifyCFG] Extend TryToSimplifyUncondBranchFromEmptyBlock for empty block including lifetime intrinsics

[• Josh]

Summary

Make it possible that TryToSimplifyUncondBranchFromEmptyBlock merges empty basic block including lifetime intrinsics as well as phi nodes and unconditional branch into its successor or predecessor(s).

If successor of empty block has single predecessor, all contents including lifetime intrinsics are sinked into the successor. Otherwise, they are hoisted into its predecessor(s) and then merged into the predecessor(s) like below example codes.

Input IR:

define void @foo(i1 %x, i1 %y) {
entry:

%a = alloca i32, align 4
br label %while.cond

while.cond: ; preds = %if.end, %entry

br i1 %y, label %while.body, label %bb

while.body: ; preds = %while.cond

%b = bitcast i32* %a to i8*
call void @llvm.lifetime.start(i64 4, i8* %b) #1
%d = load i32, i32* %a, align 4
br i1 %x, label %if.then, label %if.else

if.then: ; preds = %while.body

%e = add i32 %d, 1
store i32 %e, i32* %a, align 4
br label %if.end

if.else: ; preds = %while.body

%g = sub i32 %d, 1
store i32 %g, i32* %a, align 4
br label %if.end

if.end: ; preds = %if.else, %if.then

%c = bitcast i32* %a to i8*
call void @llvm.lifetime.end(i64 4, i8* %c) #1
br label %while.cond

bb: ; preds = %while.cond

ret void

}

Optimized output IR by SimplifyCFG:
define void @foo(i1 %x, i1 %y) {
entry:

%a = alloca i32, align 4
br label %while.cond

while.cond: ; preds = %if.then, %if.else, %entry

br i1 %y, label %while.body, label %bb

while.body: ; preds = %while.cond

%b = bitcast i32* %a to i8*
call void @llvm.lifetime.start(i64 4, i8* %b)
%d = load i32, i32* %a, align 4
br i1 %x, label %if.then, label %if.else

if.then: ; preds = %while.body

%e = add i32 %d, 1
store i32 %e, i32* %a, align 4
%c = bitcast i32* %a to i8*
call void @llvm.lifetime.end(i64 4, i8* %c)
br label %while.cond

if.else: ; preds = %while.body

%g = sub i32 %d, 1
store i32 %g, i32* %a, align 4
%0 = bitcast i32* %a to i8*
call void @llvm.lifetime.end(i64 4, i8* %0)
br label %while.cond

bb: ; preds = %while.cond

ret void

}

[hans]

I've put some comments in the code, but my main concern is that this patch needs a lot of test cases.

include/llvm/IR/BasicBlock.h

159 ↗

(On Diff #54165)

nit: The formatting of this comment doesn't look right.

lib/IR/BasicBlock.cpp

216 ↗

(On Diff #54165)

The getFirstNonPHIOrDbgOrLifetime() function also considers Intrinsic::lifetime_start. Should this function do that too?

lib/Transforms/Utils/Local.cpp

799 ↗

(On Diff #54165)

No need to repeat the name of the function in the comment. This applies to the other functions as well.

803 ↗

(On Diff #54165)

How about writing this with a range-based for-loop instead?

816 ↗

(On Diff #54165)

No need for the the ?: operator here.
In fact, how about just:

return isa<PHINode>(BB->begin());

And that means maybe we don't need a separate function for this? For example, on line 977 we already do the same kind of check with "if (isa<PHINode>(Succ->begin())) {"

825 ↗

(On Diff #54165)

No need to declare these before they're used.

830 ↗

(On Diff #54165)

You could use a range-based for-loop over predecessors(BB) instead

834 ↗

(On Diff #54165)

Would it be sufficient to just check "BI->getSingleSuccessor()"?

839 ↗

(On Diff #54165)

Some of these "else" and "return false" lines seem unnecessary.. how about something like:

for (each predecessor P) {
  if (not P has single successor)
    return false;
}

846 ↗

(On Diff #54165)

Again, range-based for-loop would be nice.

849 ↗

(On Diff #54165)

I'm not sure this extra logic to splice instead of clone the instruction into the predecessor is worth it.

855 ↗

(On Diff #54165)

I suppose this is because we might have moved I into a predecessor? This makes the loop hard to follow. If you used cloned the instruction into the predecessor, there would be no need for this, right?

873 ↗

(On Diff #54165)

This all looks very complicated.

881 ↗

(On Diff #54165)

Didn't we check earlier the contents of the BB so we know it can be hoisted? In that case there shouldn't be a need for all this checking and "return false" statements. Can you just add asserts that the instructions are what we expect, and then clone them to the predecessors?

905 ↗

(On Diff #54165)

You could use a range-based for-loop over predecessors(BB) instead, and successors(BB) in the loop below.

917 ↗

(On Diff #54165)

Didn't we check above that BB has no phi instructions?

[• Josh]

According to Hans's comments, I updated this patch as followings.

• Add test cases
• Consider Intrisic:lifetime_start
• Make codes more clear

Thanks.

[hans]

Thanks! This is looking much better :-)

Some comments below.

lib/IR/BasicBlock.cpp

211 ↗

(On Diff #55142)

No need to declare this until its use, further below.

But I also think maybe we can do without it; see below.

221 ↗

(On Diff #55142)

I think we can do away with the TI variable by just doing something like:

if (auto *BCI = dyn_cast<BitCastInst>(&I)) {
  if (auto *II = dyn_cast<IntrinsicInst>(++I.getIterator())) {
    if ((II->getIntrinsicID() == Intrinsic::lifetime_start ||
         II->getIntrinsicID() == Intrinsic::lifetime_end) &&
        II->getOperand(1) == BCI) {
      continue;
    }
  }
}

lib/Transforms/Utils/Local.cpp

799 ↗

(On Diff #55142)

Still no need to repeat the name in the comment. Just write this as

/// Return true if BB has lifetime.end intrinsic.

This applies to the functions you're declaring below as well.

I know older functions do repeat the name in their comment, but it's unnecessary and we should stop doing that.

802 ↗

(On Diff #55142)

I would suggest putting braces around the for-loop body. Even though it's technically one statement, it's several lines long so braces will help make it easier to read.

826 ↗

(On Diff #55142)

clone() is a member of Instruction, so there's no need to go via the iterator here. Just

I.clone()->insertBefore(Pred->getTerminator());

should do it.

835 ↗

(On Diff #55142)

I'm not super happy with this code..

First, there's no need to iterate backwards to look for the IntrinsicInst we just inserted. We could do something like:

Instruction *NewII = I->clone();
NewII->insertBefore(pred->getTerminator());

and then use NewII below.

Also, even if the instruction before NewII is a BitCast, can we be sure it's *the right* BitCast, i.e. the one we cloned earlier? I wish we could do this in a more principled way..

I think it would be better if we could clone the bitcast and intrinsic together. How about we ignore the "if (isa<BitCastInst>)" case above, and then do something like this here:

for (auto Pred : predecessors(BB)) {
  Instruction *NewII = I->clone();
  NewII->insertBefore(Pred->getTerminator());

  if (I != BB->begin()) {
    if (auto BC = dyn_cast<BitCastInst>(--I->getIterator())) {
      assert(BC == I->getOperand(1));
      auto NewBC = BC->clone();
      NewBC->insertBefore(NewII);
      NewII->setOperand(1, NewBC);
    }
  }
}

test/Transforms/SimplifyCFG/lifetime.ll

31 ↗

(On Diff #55142)

This is great, thanks!

It would be good to have a few tests that cover the situations when the block *cannot* be removed as well.

[• Josh]

Hans, first of all, thanks for your kind comments.

Your suggested codes are very efficient and highly readable.
I followed your guide for all commented codes.

Thanks

[hans]

lgtm

Do you have commit access, or do you need someone to commit it for you?

[• Josh]

Hans, thank you for your quick and kind review.

I do not have commit access. So, if you don't mind, would you please commit this code for me?
After I get the commit access, I'll do by myself.

(This diff revision is for fix formatting of comment)

Thanks.

llvm/trunk/include/llvm/IR/BasicBlock.h

public:
 
   /// \brief Returns a pointer to the first instruction in this block that is not
   /// a PHINode, a debug intrinsic, or a lifetime intrinsic.
   Instruction* getFirstNonPHIOrDbgOrLifetime();
   const Instruction* getFirstNonPHIOrDbgOrLifetime() const {
     return const_cast<BasicBlock*>(this)->getFirstNonPHIOrDbgOrLifetime();
   }
 
+  /// \brief Returns a pointer to the first instruction in this block that is
+  /// not a PHINode, a debug intrinsic, a lifetime intrinsic, or a bitcast
+  /// instruction coupled with the following lifetime intrinsic.
+  Instruction *getFirstNonPHIOrDbgOrLifetimeOrBitCast();
+  const Instruction *getFirstNonPHIOrDbgOrLifetimeOrBitCast() const {
+    return const_cast<BasicBlock *>(this)
+        ->getFirstNonPHIOrDbgOrLifetimeOrBitCast();
+  }
+
   /// \brief Returns an iterator to the first instruction in this block that is
   /// suitable for inserting a non-PHI instruction.
   ///
   /// In particular, it skips all PHIs and LandingPad instructions.
   iterator getFirstInsertionPt();
   const_iterator getFirstInsertionPt() const {
     return const_cast<BasicBlock*>(this)->getFirstInsertionPt();
   }

llvm/trunk/lib/IR/BasicBlock.cpp

if (auto *II = dyn_cast<IntrinsicInst>(&I))
           II->getIntrinsicID() == Intrinsic::lifetime_end)
         continue;
 
     return &I;
   }
   return nullptr;
 }
 
+Instruction *BasicBlock::getFirstNonPHIOrDbgOrLifetimeOrBitCast() {
+  for (Instruction &I : *this) {
+    if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
+      continue;
+
+    if (auto *II = dyn_cast<IntrinsicInst>(&I))
+      if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
+          II->getIntrinsicID() == Intrinsic::lifetime_end)
+        continue;
+
+    if (auto *BCI = dyn_cast<BitCastInst>(&I)) {
+      if (auto *II = dyn_cast<IntrinsicInst>(++I.getIterator())) {
+        if ((II->getIntrinsicID() == Intrinsic::lifetime_start ||
+             II->getIntrinsicID() == Intrinsic::lifetime_end) &&
+            II->getOperand(1) == BCI) {
+          continue;
+        }
+      }
+    }
+    return &I;
+  }
+  return nullptr;
+}
+
 BasicBlock::iterator BasicBlock::getFirstInsertionPt() {
   Instruction *FirstNonPHI = getFirstNonPHI();
   if (!FirstNonPHI)
     return end();
 
   iterator InsertPt = FirstNonPHI->getIterator();
   if (InsertPt->isEHPad()) ++InsertPt;
   return InsertPt;

llvm/trunk/lib/Transforms/Utils/Local.cpp

for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) {
       // newly retargeted branch.
       PN->addIncoming(Selected, PredBB);
     }
   }
 
   replaceUndefValuesInPhi(PN, IncomingValues);
 }
 
+/// Return true if BB has lifetime.end intrinsic.
+///
+static bool hasLifetime(BasicBlock *BB) {
+  for (auto &I : *BB) {
+    if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I)) {
+      if (II->getIntrinsicID() == Intrinsic::lifetime_end ||
+          II->getIntrinsicID() == Intrinsic::lifetime_start) {
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
+/// hoistLifetimeFromEmptyBlockToPred - Hoist lifetime.end intrinsics and
+/// related bitcast instructions from BB to predecessors of BB.
+///
+static bool hoistLifetimeFromEmptyBlockToPred(BasicBlock *BB) {
+  // Check to see if all Preds have single successor and if not, we cannot
+  // hoist lifetime intrinsics because it would change semantics.
+  for (auto Pred : predecessors(BB))
+    if (!Pred->getSingleSuccessor())
+      return false;
+
+  // Hoist all lifetime.end intrinsics and related bitcast instrunctions
+  // in BB to Preds.
+  for (auto &I : *BB) {
+    if (auto *II = dyn_cast<IntrinsicInst>(&I)) {
+      if (II->getIntrinsicID() == Intrinsic::lifetime_end ||
+          II->getIntrinsicID() == Intrinsic::lifetime_start) {
+        for (auto Pred : predecessors(BB)) {
+          Instruction *NewII = I.clone();
+          NewII->insertBefore(Pred->getTerminator());
+
+          if (I.getIterator() != BB->begin()) {
+            if (auto BC = dyn_cast<BitCastInst>(--I.getIterator())) {
+              assert(BC == I.getOperand(1));
+              auto NewBC = BC->clone();
+              NewBC->insertBefore(NewII);
+              NewII->setOperand(1, NewBC);
+            }
+          }
+        }
+      }
+    }
+  }
+  return true;
+}
+
 /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an
 /// unconditional branch, and contains no instructions other than PHI nodes,
 /// potential side-effect free intrinsics and the branch.  If possible,
 /// eliminate BB by rewriting all the predecessors to branch to the successor
 /// block and return true.  If we can't transform, return false.
 bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) {
   assert(BB != &BB->getParent()->getEntryBlock() &&
          "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
 
   // We can't eliminate infinite loops.
   BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);
   if (BB == Succ) return false;
 
+  // If BB has lifetime.end intrinsics, simplify BB under more constraints.
+  if (hasLifetime(BB)) {
+    // Check to see if BB and its predecessors and successors have PHI.
+    if (isa<PHINode>(BB->begin()))
+      return false;
+
+    for (auto Pred : predecessors(BB))
+      if (isa<PHINode>(Pred->begin()))
+        return false;
+
+    for (auto Succ : successors(BB))
+      if (isa<PHINode>(Succ->begin()))
+        return false;
+
+    if (Succ->getSinglePredecessor()) {
+      // BB is the only predecessor of Succ, so Succ will end up with exactly
+      // the same predecessors BB had.
+
+      // Copy over any debug or lifetime instruction.
+      BB->getTerminator()->eraseFromParent();
+      Succ->getInstList().splice(Succ->getFirstNonPHI()->getIterator(),
+                                 BB->getInstList());
+
+    } else {
+      // Unless BB is the only predecessor of Succ, hoist lifetime intrinsics
+      // to predecessors of BB and simplify BB.
+      if (!hoistLifetimeFromEmptyBlockToPred(BB)) {
+        return false;
+      }
+    }
+
+    DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
+
+    // Everything that jumped to BB now goes to Succ.
+    BB->replaceAllUsesWith(Succ);
+    if (!Succ->hasName())
+      Succ->takeName(BB);
+    BB->eraseFromParent(); // Delete the old basic block.
+    return true;
+  } else {
     // Check to see if merging these blocks would cause conflicts for any of the
     // phi nodes in BB or Succ. If not, we can safely merge.
-  if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false;
+    if (!CanPropagatePredecessorsForPHIs(BB, Succ))
+      return false;
 
     // Check for cases where Succ has multiple predecessors and a PHI node in BB
     // has uses which will not disappear when the PHI nodes are merged.  It is
-  // possible to handle such cases, but difficult: it requires checking whether
-  // BB dominates Succ, which is non-trivial to calculate in the case where
-  // Succ has multiple predecessors.  Also, it requires checking whether
-  // constructing the necessary self-referential PHI node doesn't introduce any
-  // conflicts; this isn't too difficult, but the previous code for doing this
-  // was incorrect.
+    // possible to handle such cases, but difficult: it requires checking
+    // whether BB dominates Succ, which is non-trivial to calculate in the
+    // case where Succ has multiple predecessors.  Also, it requires checking
+    // whether constructing the necessary self-referential PHI node doesn't
+    // introduce any conflicts; this isn't too difficult, but the previous code
+    // for doing this was incorrect.
     //
     // Note that if this check finds a live use, BB dominates Succ, so BB is
-  // something like a loop pre-header (or rarely, a part of an irreducible CFG);
+    // something like a loop pre-header (or rarely, a part of an irreducible
+    // CFG);
     // folding the branch isn't profitable in that case anyway.
     if (!Succ->getSinglePredecessor()) {
       BasicBlock::iterator BBI = BB->begin();
       while (isa<PHINode>(*BBI)) {
         for (Use &U : BBI->uses()) {
-        if (PHINode* PN = dyn_cast<PHINode>(U.getUser())) {
+          if (PHINode *PN = dyn_cast<PHINode>(U.getUser())) {
             if (PN->getIncomingBlock(U) != BB)
               return false;
           } else {
             return false;
           }
         }
         ++BBI;
       }
     }
 
     DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
 
     if (isa<PHINode>(Succ->begin())) {
       // If there is more than one pred of succ, and there are PHI nodes in
       // the successor, then we need to add incoming edges for the PHI nodes
       //
       const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB));
 
       // Loop over all of the PHI nodes in the successor of BB.
       for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
         PHINode *PN = cast<PHINode>(I);
 
         redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN);
       }
     }
 
     if (Succ->getSinglePredecessor()) {
       // BB is the only predecessor of Succ, so Succ will end up with exactly
       // the same predecessors BB had.
 
       // Copy over any phi, debug or lifetime instruction.
       BB->getTerminator()->eraseFromParent();
       Succ->getInstList().splice(Succ->getFirstNonPHI()->getIterator(),
                                  BB->getInstList());
     } else {
       while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
         // We explicitly check for such uses in CanPropagatePredecessorsForPHIs.
         assert(PN->use_empty() && "There shouldn't be any uses here!");
         PN->eraseFromParent();
       }
     }
 
     // Everything that jumped to BB now goes to Succ.
     BB->replaceAllUsesWith(Succ);
-  if (!Succ->hasName()) Succ->takeName(BB);
-  BB->eraseFromParent();              // Delete the old basic block.
+    if (!Succ->hasName())
+      Succ->takeName(BB);
+    BB->eraseFromParent(); // Delete the old basic block.
     return true;
   }
+}
 
 /// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI
 /// nodes in this block. This doesn't try to be clever about PHI nodes
 /// which differ only in the order of the incoming values, but instcombine
 /// orders them so it usually won't matter.
 ///
 bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) {
   // This implementation doesn't currently consider undef operands

llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp

static bool TryToMergeLandingPad(LandingPadInst *LPad, BranchInst *BI,
   return false;
 }
 
 bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder){
   BasicBlock *BB = BI->getParent();
 
   if (SinkCommon && SinkThenElseCodeToEnd(BI))
     return true;
-
-  // If the Terminator is the only non-phi instruction, simplify the block.
-  // if LoopHeader is provided, check if the block is a loop header
+  // If the Terminator is the only non-phi instruction except for bitcast
+  // instruction coupled with the following lifetime intrinsic, simplify the
+  // block. If LoopHeader is provided, check if the block is a loop header
   // (This is for early invocations before loop simplify and vectorization
   // to keep canonical loop forms for nested loops.
   // These blocks can be eliminated when the pass is invoked later
   // in the back-end.)
-  BasicBlock::iterator I = BB->getFirstNonPHIOrDbg()->getIterator();
+  BasicBlock::iterator I =
+      BB->getFirstNonPHIOrDbgOrLifetimeOrBitCast()->getIterator();
   if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() &&
       (!LoopHeaders || !LoopHeaders->count(BB)) &&
       TryToSimplifyUncondBranchFromEmptyBlock(BB))
     return true;
 
   // If the only instruction in the block is a seteq/setne comparison
   // against a constant, try to simplify the block.
   if (ICmpInst *ICI = dyn_cast<ICmpInst>(I))

llvm/trunk/test/Transforms/SimplifyCFG/lifetime.ll

 ; RUN: opt < %s -simplifycfg -S | FileCheck %s
 
 ; Test that a lifetime intrinsic isn't removed because that would change semantics
+; This case is that predecessor(s) of the target empty block (bb0) has multiple
+; successors (bb0 and bb1) and its successor has multiple predecessors (entry and
+; bb0).
 
 ; CHECK: foo
 ; CHECK: entry:
 ; CHECK: bb0:
 ; CHECK: bb1:
 ; CHECK: ret
 define void @foo(i1 %x) {
 entry:
bb1:
   ret void
 }
 
 declare void @f()
 
 declare void @llvm.lifetime.start(i64, i8* nocapture) nounwind
 
 declare void @llvm.lifetime.end(i64, i8* nocapture) nounwind
+
+; Test that empty block including lifetime intrinsic and not related bitcast
+; instruction cannot be removed. It is because the block is not empty.
+ 
+; CHECK-LABEL: coo
+; CHECK-LABEL: entry:
+; CHECK-LABEL: if.then:
+; CHECK-LABEL: if.else:
+; CHECK-LABEL: if.end:
+; CHECK-LABEL: bb:
+; CHECK: ret
+
+define void @coo(i1 %x, i1 %y) {
+entry:
+  %a = alloca i8, align 4
+  %b = alloca i32, align 4
+  br label %while.cond
+
+while.cond:                                       ; preds = %if.end, %entry
+  br i1 %y, label %while.body, label %bb
+
+while.body:                                       ; preds = %while.cond
+  call void @llvm.lifetime.start(i64 4, i8* %a)
+  %c = load i8, i8* %a, align 4
+  br i1 %x, label %if.then, label %if.else
+
+if.then:                                          ; preds = %while.body
+  %d = add i8 %c, 1
+  br label %if.end
+
+if.else:                                          ; preds = %while.body
+  %e = sub i8 %c, 1
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %f = bitcast i32* %b to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %a)
+  br label %while.cond
+
+bb:                                               ; preds = %while.cond
+  ret void
+}
+
+; Test that empty block including lifetime intrinsic can be removed.
+; Lifetime.end intrinsic is moved to predecessors because successor has 
+; multiple predecessors.
+
+; CHECK-LABEL: soo
+; CHECK-LABEL: entry:
+; CHECK-LABEL: if.then:
+; CHECK-NEXT: %e
+; CHECK-NEXT: call void @llvm.lifetime.end
+; CHECK-LABEL: if.else:
+; CHECK-NEXT: %g
+; CHECK-NEXT: call void @llvm.lifetime.end
+; CHECK-NEXT: br label %while.cond
+; CHECK-NOT: if.end:
+; CHECK: ret
+
+define void @soo(i1 %x, i1 %y) {
+entry:
+  %a = alloca i8, align 4
+  br label %while.cond
+
+while.cond:                                       ; preds = %if.end, %entry
+  br i1 %y, label %while.body, label %bb
+
+while.body:                                       ; preds = %while.cond
+  call void @llvm.lifetime.start(i64 4, i8* %a)
+  %d = load i8, i8* %a, align 4
+  br i1 %x, label %if.then, label %if.else
+
+if.then:                                          ; preds = %while.body
+  %e = add i8 %d, 1
+  br label %if.end
+
+if.else:                                          ; preds = %while.body
+  %g = sub i8 %d, 1
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  call void @llvm.lifetime.end(i64 4, i8* %a)
+  br label %while.cond
+
+bb:                                               ; preds = %while.cond
+  ret void
+}
+
+; Test that empty block including lifetime intrinsic and related bitcast
+; instruction can be removed. Lifetime.end intrinsic and related bitcast 
+; instruction are moved to predecessors because successor has multiple
+; predecessors.
+
+; CHECK-LABEL: boo
+; CHECK-LABEL: entry:
+; CHECK-LABEL: if.then:
+; CHECK-NEXT: %e
+; CHECK-NEXT: %[[T:[^ ]+]] = bitcast
+; CHECK-NEXT: call void @llvm.lifetime.end(i64 4, i8* %[[T]])
+; CHECK-LABEL: if.else:
+; CHECK-NEXT: %g
+; CHECK-NEXT: %[[B:[^ ]+]] = bitcast
+; CHECK-NEXT: call void @llvm.lifetime.end(i64 4, i8* %[[B]])
+; CHECK-NEXT: br label %while.cond
+; CHECK-NOT: if.end:
+; CHECK: ret
+
+define void @boo(i1 %x, i1 %y) {
+entry:
+  %a = alloca i32, align 4
+  br label %while.cond
+
+while.cond:                                       ; preds = %if.end, %entry
+  br i1 %y, label %while.body, label %bb
+
+while.body:                                       ; preds = %while.cond
+  %b = bitcast i32* %a to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %b)
+  %d = load i32, i32* %a, align 4
+  br i1 %x, label %if.then, label %if.else
+
+if.then:                                          ; preds = %while.body
+  %e = add i32 %d, 1
+  br label %if.end
+
+if.else:                                          ; preds = %while.body
+  %g = sub i32 %d, 1
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %c = bitcast i32* %a to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %c)
+  br label %while.cond
+
+bb:                                               ; preds = %while.cond
+  ret void
+}
+
+; Test that empty block including lifetime intrinsic can be removed.
+; Lifetime.start intrinsic is moved to predecessors because successor has 
+; multiple predecessors.
+
+; CHECK-LABEL: koo
+; CHECK-LABEL: entry:
+; CHECK-LABEL: if.then:
+; CHECK-NEXT: call void @f
+; CHECK-NEXT: call void @llvm.lifetime.start
+; CHECK-LABEL: if.else:
+; CHECK-NEXT: call void @g
+; CHECK-NEXT: call void @llvm.lifetime.start
+; CHECK-NEXT: br label %bb
+; CHECK-NOT: if.end:
+; CHECK: ret
+
+define void @koo(i1 %x, i1 %y, i1 %z) {
+entry:
+  %a = alloca i8, align 4
+  br i1 %z, label %bb, label %bb0
+
+bb0:                                              ; preds = %entry
+  br i1 %x, label %if.then, label %if.else
+
+if.then:                                          ; preds = %bb0
+  call void @f()
+  br label %if.end
+
+if.else:                                          ; preds = %bb0
+  call void @g()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  call void @llvm.lifetime.start(i64 4, i8* %a)
+  br label %bb
+
+bb:                                               ; preds = %if.end, %entry
+  %d = load i8, i8* %a, align 4
+  call void @llvm.lifetime.end(i64 4, i8* %a)
+  ret void
+}
+
+declare void @g()
+
+; Test that empty block including lifetime intrinsic and related bitcast
+; instruction can be removed. Lifetime.start intrinsic and related bitcast 
+; instruction are moved to predecessors because successor has multiple
+; predecessors.
+
+
+; CHECK-LABEL: goo
+; CHECK-LABEL: entry:
+; CHECK-LABEL: if.then:
+; CHECK-NEXT: call void @f
+; CHECK-NEXT: %[[T:[^ ]+]] = bitcast
+; CHECK-NEXT: call void @llvm.lifetime.start(i64 4, i8* %[[T]])
+; CHECK-LABEL: if.else:
+; CHECK-NEXT: call void @g
+; CHECK-NEXT: %[[B:[^ ]+]] = bitcast
+; CHECK-NEXT: call void @llvm.lifetime.start(i64 4, i8* %[[B]])
+; CHECK-NEXT: br label %bb
+; CHECK-NOT: if.end:
+; CHECK: ret
+
+define void @goo(i1 %x, i1 %y, i1 %z) {
+entry:
+  %a = alloca i32, align 4
+  br i1 %z, label %bb, label %bb0
+
+bb0:                                              ; preds = %entry
+  br i1 %x, label %if.then, label %if.else
+
+if.then:                                          ; preds = %bb0
+  call void @f()
+  br label %if.end
+
+if.else:                                          ; preds = %bb0
+  call void @g()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %b = bitcast i32* %a to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %b)
+  br label %bb
+
+bb:                                               ; preds = %if.end, %entry
+  %d = load i32, i32* %a, align 4
+  %c = bitcast i32* %a to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %c)
+  ret void
+}