Merge empty landing pads in SimplifyCFG

[reames]

Summary

This patch tries to merge duplicate landing pads when they branch to a common shared target.

Given IR that looks like this:
lpad1:

%exn = landingpad {i8*, i32} personality i32 (...)* @__gxx_personality_v0
       cleanup
br label %shared_resume

lpad2:

%exn2 = landingpad {i8*, i32} personality i32 (...)* @__gxx_personality_v0
        cleanup
br label %shared_resume

shared_resume:

call void @fn()
ret void

}

We can rewrite the users of both landing pad blocks to use one of them. This will generally allow the shared_resume block to be merged with the common landing pad as well.

Without this change, tail duplication would likely kick in - creating N (2 in this case) copies of the shared_resume basic block.

There are two subtitles with the choice of blocks to merge. From the comments:
/ We specifically choose to not worry about merging non-empty blocks
/ here. That is a PRE/scheduling problem and is best solved elsewhere. In
/ practice, the optimizer produces empty landing pad blocks quite frequently
/ when dealing with exception dense code. (see: instcombine, gvn, if-else
/ sinking in this file)
/
/ This is primarily a code size optimization. We need to avoid performing
/ any transform which might inhibit optimization (such as our ability to
/ specialize a particular handler via tail commoning). We do this by not
/ merging any blocks which require us to introduce a phi. Since the same
/ values are flowing through both blocks, we don't loose any ability to
/ specialize. If anything, we make such specialization more likely.

[reames]

Getting a correct diff (the test was screwed up in the last one)

[andrew.w.kaylor]

LGTM (with a minor question about debug info intrinsics)

lib/Transforms/Utils/SimplifyCFG.cpp

4462

If I'm reading this right these debug intrinsics just get thrown away if a merge is performed. Do they not contain anything that might be different from the corresponding debug intrinsics in the potential merge block?

[reames]

lib/Transforms/Utils/SimplifyCFG.cpp

4462

This is correct. dbg intriniscs are not allowed to modify optimization or code gen. You're right that we could contain them if they were the same though.

Actually, there's a bug here. I need to remove *both* sets of debug intrinsics if I they're not the same.

[sanjoy]

Minor drive-by comments inline.

lib/Transforms/Utils/SimplifyCFG.cpp

4423

Isn't there only one successor, Succ?

4460

Nit: should be "equivalent"

lib/Transforms/Utils/SimplifyCFG.cpp

 
   if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) {
     if (SimplifyIndirectBrOnSelect(IBI, SI))
       return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
   }
   return Changed;
 }
 
+/// Given an block with only a single landing pad and a unconditional branch
+/// try to find another basic block which this one can be merged with.  This
+/// handles cases where we have multiple invokes with unique landing pads, but
+/// a shared handler.
+///
+/// We specifically choose to not worry about merging non-empty blocks
+/// here.  That is a PRE/scheduling problem and is best solved elsewhere.  In
+/// practice, the optimizer produces empty landing pad blocks quite frequently
+/// when dealing with exception dense code.  (see: instcombine, gvn, if-else
+/// sinking in this file)
+///
+/// This is primarily a code size optimization.  We need to avoid performing
+/// any transform which might inhibit optimization (such as our ability to
+/// specialize a particular handler via tail commoning).  We do this by not
+/// merging any blocks which require us to introduce a phi.  Since the same
+/// values are flowing through both blocks, we don't loose any ability to
+/// specialize.  If anything, we make such specialization more likely.
+///
+/// TODO - This transformation could remove entries from a phi in the target
+/// block when the inputs in the phi are the same for the two blocks being
+/// merged.  In some cases, this could result in removal of the PHI entirely.
+static bool TryToMergeLandingPad(LandingPadInst *LPad, BranchInst *BI,
+                                 BasicBlock *BB) {
+  auto Succ = BB->getUniqueSuccessor();
+  assert(Succ);
+  // If there's a phi in the successor block, we'd likely have to introduce
+  // a phi into the merged landing pad block.
+  if (isa<PHINode>(*Succ->begin()))
+    return false;
+
+  for (BasicBlock *OtherPred : predecessors(Succ)) {
+    if (BB == OtherPred)
+      continue;
+    BasicBlock::iterator I = OtherPred->begin();
+    LandingPadInst *LPad2 = dyn_cast<LandingPadInst>(I);
+    if (!LPad2 || !LPad2->isIdenticalTo(LPad))
+      continue;
+    for (++I; isa<DbgInfoIntrinsic>(I); ++I) {}
+    BranchInst *BI2 = dyn_cast<BranchInst>(I);
+    if (!BI2 || !BI2->isIdenticalTo(BI))
+      continue;
+
+    // We've found an identical block.  Update our predeccessors to take that
+    // path instead and make ourselves dead.
+    SmallSet<BasicBlock *, 16> Preds;
+    Preds.insert(pred_begin(BB), pred_end(BB));
+    for (BasicBlock *Pred : Preds) {
+      InvokeInst *II = cast<InvokeInst>(Pred->getTerminator());
+      assert(II->getNormalDest() != BB &&
+             II->getUnwindDest() == BB && "unexpected successor");
+      II->setUnwindDest(OtherPred);
+    }
+
+    SmallSet<BasicBlock *, 16> Succs;
+    Succs.insert(succ_begin(BB), succ_end(BB));
+    for (BasicBlock *Succ : Succs) {
+      Succ->removePredecessor(BB);
+    }
+
+    IRBuilder<> Builder(BI);
+    Builder.CreateUnreachable();
+    BI->eraseFromParent();
+    return true;
+  }
+  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.
   BasicBlock::iterator I = BB->getFirstNonPHIOrDbg();
   if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() &&
       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))
     if (ICI->isEquality() && isa<ConstantInt>(ICI->getOperand(1))) {
       for (++I; isa<DbgInfoIntrinsic>(I); ++I)
         ;
       if (I->isTerminator() &&
           TryToSimplifyUncondBranchWithICmpInIt(ICI, Builder, TTI,
                                                 BonusInstThreshold, DL, AC))
         return true;
     }
 
+  // See if we can merge an empty landing pad block with another which is
+  // equivelent.
+  if (LandingPadInst *LPad = dyn_cast<LandingPadInst>(I)) {
+    for (++I; isa<DbgInfoIntrinsic>(I); ++I) {}
+    if (I->isTerminator() &&
+        TryToMergeLandingPad(LPad, BI, BB))
+      return true;
+  } 
+
   // If this basic block is ONLY a compare and a branch, and if a predecessor
   // branches to us and our successor, fold the comparison into the
   // predecessor and use logical operations to update the incoming value
   // for PHI nodes in common successor.
   if (FoldBranchToCommonDest(BI, DL, BonusInstThreshold))
     return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
   return false;
 }

test/Transforms/SimplifyCFG/duplicate-landingpad.ll

 ; RUN: opt < %s -simplifycfg -S | FileCheck %s
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
 declare i32 @__gxx_personality_v0(...)
 declare void @fn()
 
 
-; CHECK-LABEL: @f1(
-define void @f1() {
+; CHECK-LABEL: @test1
+define void @test1() {
 entry:
+; CHECK-LABEL: entry:
+; CHECK: to label %invoke2 unwind label %lpad2
   invoke void @fn()
     to label %invoke2 unwind label %lpad1
 
 invoke2:
+; CHECK-LABEL: invoke2:
+; CHECK: to label %invoke.cont unwind label %lpad2
   invoke void @fn()
     to label %invoke.cont unwind label %lpad2
 
 invoke.cont:
   ret void
 
 lpad1:
   %exn = landingpad {i8*, i32} personality i32 (...)* @__gxx_personality_v0
          cleanup
   br label %shared_resume
 
 lpad2:
+; CHECK-LABEL: lpad2:
+; CHECK: landingpad { i8*, i32 } personality i32 (...)* @__gxx_personality_v0
+; CHECK-NEXT: cleanup
+; CHECK-NEXT: call void @fn()
+; CHECK-NEXT: ret void
+  %exn2 = landingpad {i8*, i32} personality i32 (...)* @__gxx_personality_v0
+          cleanup
+  br label %shared_resume
+
+shared_resume:
+  call void @fn()
+  ret void
+}
+
+; Don't trigger if blocks aren't the same/empty
+define void @neg1() {
+; CHECK-LABEL: @neg1
+entry:
+; CHECK-LABEL: entry:
+; CHECK: to label %invoke2 unwind label %lpad1
+  invoke void @fn()
+    to label %invoke2 unwind label %lpad1
+
+invoke2:
+; CHECK-LABEL: invoke2:
+; CHECK: to label %invoke.cont unwind label %lpad2
+  invoke void @fn()
+    to label %invoke.cont unwind label %lpad2
+
+invoke.cont:
+  ret void
+
+lpad1:
+  %exn = landingpad {i8*, i32} personality i32 (...)* @__gxx_personality_v0
+         filter [0 x i8*] zeroinitializer
+  call void @fn()
+  br label %shared_resume
+
+lpad2:
+  %exn2 = landingpad {i8*, i32} personality i32 (...)* @__gxx_personality_v0
+          cleanup
+  br label %shared_resume
+
+shared_resume:
+  call void @fn()
+  ret void
+}
+
+; Should not trigger when the landing pads are not the exact same
+define void @neg2() {
+; CHECK-LABEL: @neg2
+entry:
+; CHECK-LABEL: entry:
+; CHECK: to label %invoke2 unwind label %lpad1
+  invoke void @fn()
+    to label %invoke2 unwind label %lpad1
+
+invoke2:
+; CHECK-LABEL: invoke2:
+; CHECK: to label %invoke.cont unwind label %lpad2
+  invoke void @fn()
+    to label %invoke.cont unwind label %lpad2
+
+invoke.cont:
+  ret void
+
+lpad1:
+  %exn = landingpad {i8*, i32} personality i32 (...)* @__gxx_personality_v0
+         filter [0 x i8*] zeroinitializer
+  br label %shared_resume
+
+lpad2:
   %exn2 = landingpad {i8*, i32} personality i32 (...)* @__gxx_personality_v0
           cleanup
   br label %shared_resume
 
 shared_resume:
   call void @fn()
   ret void
 }