From 6bde9f699422c041cfa613dd9034e8ea5d827414 Mon Sep 17 00:00:00 2001 From: Philip Reames Date: Tue, 24 Mar 2015 22:28:45 +0000 Subject: [PATCH] Merge empty landing pads in SimplifyCFG 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. Differential Revision: http://reviews.llvm.org/D8297 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@233125 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Utils/SimplifyCFG.cpp | 85 ++++++++++++++ .../SimplifyCFG/duplicate-landingpad.ll | 110 ++++++++++++++++++ 2 files changed, 195 insertions(+) create mode 100644 test/Transforms/SimplifyCFG/duplicate-landingpad.ll diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index b45a256bc24..c7c0ca6fc69 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -4349,6 +4349,82 @@ bool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) { 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(*Succ->begin())) + return false; + + for (BasicBlock *OtherPred : predecessors(Succ)) { + if (BB == OtherPred) + continue; + BasicBlock::iterator I = OtherPred->begin(); + LandingPadInst *LPad2 = dyn_cast(I); + if (!LPad2 || !LPad2->isIdenticalTo(LPad)) + continue; + for (++I; isa(I); ++I) {} + BranchInst *BI2 = dyn_cast(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 Preds; + Preds.insert(pred_begin(BB), pred_end(BB)); + for (BasicBlock *Pred : Preds) { + InvokeInst *II = cast(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(Inst)) + Inst.eraseFromParent(); + } + + SmallSet 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(); @@ -4373,6 +4449,15 @@ bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder){ return true; } + // See if we can merge an empty landing pad block with another which is + // equivalent. + if (LandingPadInst *LPad = dyn_cast(I)) { + for (++I; isa(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 diff --git a/test/Transforms/SimplifyCFG/duplicate-landingpad.ll b/test/Transforms/SimplifyCFG/duplicate-landingpad.ll new file mode 100644 index 00000000000..54028774d20 --- /dev/null +++ b/test/Transforms/SimplifyCFG/duplicate-landingpad.ll @@ -0,0 +1,110 @@ +; 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 +} -- 2.34.1