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 ↗

(On Diff #21844)

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 ↗

(On Diff #21844)

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 ↗

(On Diff #21844)

Isn't there only one successor, Succ?

4460 ↗

(On Diff #21844)

Nit: should be "equivalent"

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

bool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) {
 
   if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) {
     if (SimplifyIndirectBrOnSelect(IBI, SI))
       return SimplifyCFG(BB, TTI, BonusInstThreshold, 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);
+    }
+
+    // The debug info in OtherPred doesn't cover the merged control flow that
+    // used to go through BB.  We need to delete it or update it.
+    for (auto I = OtherPred->begin(), E = OtherPred->end();
+         I != E;) {
+      Instruction &Inst = *I; I++;
+      if (isa<DbgInfoIntrinsic>(Inst))
+        Inst.eraseFromParent();
+    }
+
+    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, DL, TTI,
                                                 BonusInstThreshold, AC))
         return true;
     }
 
+  // See if we can merge an empty landing pad block with another which is
+  // equivalent.
+  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, BonusInstThreshold))
     return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
   return false;
 }

llvm/trunk/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: @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
+}