[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

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

lib/IR/BasicBlock.cpp

216

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

lib/Transforms/Utils/Local.cpp

799

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

803

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

816

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

No need to declare these before they're used.

830

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

834

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

839

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

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

849

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

855

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

This all looks very complicated.

881

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

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

917

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

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

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

221

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

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

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

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

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.

include/llvm/IR/BasicBlock.h

 
   /// \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();
   }

lib/IR/BasicBlock.cpp

           II->getIntrinsicID() == Intrinsic::lifetime_end)
         continue;
 
     return &I;
   }
   return nullptr;
 }
 
+Instruction *BasicBlock::getFirstNonPHIOrDbgOrLifetimeOrBitCast() {
+  for (Instruction &I : *this) {
+    BasicBlock::iterator TI = I.getIterator();
+    if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
+      continue;
+
+    if (auto *II = dyn_cast<IntrinsicInst>(&I))
+      if (II->getIntrinsicID() == Intrinsic::lifetime_end)
+        continue;
+
+    if (auto *II = dyn_cast<BitCastInst>(&I))
+      if (auto *TII = dyn_cast<IntrinsicInst>(++TI))
+        if (TII->getIntrinsicID() == Intrinsic::lifetime_end)
+          if (TII->getOperand(1) == II)
+            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;

lib/Transforms/Utils/Local.cpp

       // newly retargeted branch.
       PN->addIncoming(Selected, PredBB);
     }
   }
 
   replaceUndefValuesInPhi(PN, IncomingValues);
 }
 
+/// hasLifetimeEnd - Return true if BB has lifetime.end intrinsic.
+///
+static bool hasLifetimeEnd(BasicBlock *BB) {
+  BasicBlock::iterator I = BB->begin();
+  while (!I->isTerminator()) {
+    if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
+      if (II->getIntrinsicID() == Intrinsic::lifetime_end)
+        return true;
+    ++I;
+  }
+  return false;
+}
+
+/// hasPHI - Return true if BB has phi.
+///
+static bool hasPHI(BasicBlock *BB) {
+  BasicBlock::iterator I = BB->begin();
+  return isa<PHINode>(I) ? true : false;
+}
+
+/// hoistLifetimeFromEmptyBlockToPred - Hoist lifetime.end intrinsics and
+/// related
+/// bitcast instructions from BB to predecessors of BB.
+///
+static bool hoistLifetimeFromEmptyBlockToPred(BasicBlock *BB) {
+  BasicBlock::iterator I = BB->begin();
+  BasicBlock::iterator NI = BB->begin();
+
+  // Check to see if all Pred's terminators are unconditional branches and if
+  // not,
+  // we cannot hoist lifetime.end intrinsics because it would change semantics.
+  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
+    BasicBlock *Pred = *PI;
+    Instruction *PTI = Pred->getTerminator();
+    if (auto *BI = dyn_cast<BranchInst>(PTI)) {
+      if (BI->isUnconditional())
+        continue;
+      else
+        return false;
+    } else
+      return false;
+  }
+
+  // Hoist all lifetime.end intrinsics and related bitcast instrunctions in BB
+  // to Preds.
+  while (!I->isTerminator()) {
+    if (isa<BitCastInst>(I)) {
+      for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
+        BasicBlock *Pred = *PI;
+        pred_iterator NPI = PI;
+        if (++NPI == E) {
+          Pred->getInstList().splice(Pred->getTerminator()->getIterator(),
+                                     BB->getInstList(), I);
+        } else
+          I->clone()->insertBefore(Pred->getTerminator());
+      }
+      I = BB->begin();
+      NI = BB->begin();
+    } else if (auto *II = dyn_cast<IntrinsicInst>(I)) {
+      if (II->getIntrinsicID() == Intrinsic::lifetime_end) {
+        for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E;
+             ++PI) {
+          BasicBlock *Pred = *PI;
+          pred_iterator NPI = PI;
+          if (++NPI == E) {
+            Pred->getInstList().splice(Pred->getTerminator()->getIterator(),
+                                       BB->getInstList(), I);
+          } else {
+            I->clone()->insertBefore(Pred->getTerminator());
+            BasicBlock::iterator PEI = Pred->end();
+            --PEI;
+            --PEI;
+            BasicBlock::iterator NPEI = PEI;
+            if ((PEI != Pred->begin()) && isa<BitCastInst>(--PEI))
+              NPEI->setOperand(1, &*(PEI));
+          }
+        }
+        I = BB->begin();
+        NI = BB->begin();
+      } else
+        return false;
+    } else
+      return false;
+  }
+  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;
 
-  // 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;
-
-  // 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.
-  //
-  // 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);
-  // 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 (PN->getIncomingBlock(U) != BB)
+  // If BB has lifetime.end intrinsics, simplify BB under more constraints.
+  if (hasLifetimeEnd(BB)) {
+    // Check to see if BB and its predecessors and successors have PHI.
+    if (hasPHI(BB))
+      return false;
+
+    for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
+      if (hasPHI(*PI))
+        return false;
+
+    for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
+      if (hasPHI(*SI))
+        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 phi, 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;
+
+    // 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.
+    //
+    // 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);
+    // 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 (PN->getIncomingBlock(U) != BB)
+              return false;
+          } else {
             return false;
-        } else {
-          return false;
+          }
         }
+        ++BBI;
       }
-      ++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.
-  return true;
+    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) {

lib/Transforms/Utils/SimplifyCFG.cpp

 }
 
 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))