From 0ad7b6e773b33f4c4fd3c82c8a5c10ac0597792c Mon Sep 17 00:00:00 2001 From: Duncan Sands Date: Fri, 30 Sep 2011 13:12:16 +0000 Subject: [PATCH] Inlining often produces landingpad instructions with repeated catch or repeated filter clauses. Teach instcombine a bunch of tricks for simplifying landingpad clauses. Currently the code only recognizes the GNU C++ and Ada personality functions, but that doesn't stop it doing a bunch of "generic" transforms which are hopefully fine for any real-world personality function. If these "generic" transforms turn out not to be generic, they can always be conditioned on the personality function. Probably someone should add the ObjC++ personality function. I didn't as I don't know anything about it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140852 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/InstCombine/InstCombine.h | 1 + .../InstCombine/InstructionCombining.cpp | 337 ++++++++++++++++++ .../InstCombine/LandingPadClauses.ll | 157 ++++++++ 3 files changed, 495 insertions(+) create mode 100644 test/Transforms/InstCombine/LandingPadClauses.ll diff --git a/lib/Transforms/InstCombine/InstCombine.h b/lib/Transforms/InstCombine/InstCombine.h index be4454b8789..38082787ce4 100644 --- a/lib/Transforms/InstCombine/InstCombine.h +++ b/lib/Transforms/InstCombine/InstCombine.h @@ -193,6 +193,7 @@ public: Instruction *visitExtractElementInst(ExtractElementInst &EI); Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI); Instruction *visitExtractValueInst(ExtractValueInst &EV); + Instruction *visitLandingPadInst(LandingPadInst &LI); // visitInstruction - Specify what to return for unhandled instructions... Instruction *visitInstruction(Instruction &I) { return 0; } diff --git a/lib/Transforms/InstCombine/InstructionCombining.cpp b/lib/Transforms/InstCombine/InstructionCombining.cpp index af2a5d2c1e9..cee27ff5913 100644 --- a/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -49,6 +49,7 @@ #include "llvm/Support/ValueHandle.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" +#include "llvm/ADT/StringSwitch.h" #include "llvm-c/Initialization.h" #include #include @@ -1413,6 +1414,342 @@ Instruction *InstCombiner::visitExtractValueInst(ExtractValueInst &EV) { return 0; } +enum Personality_Type { + Unknown_Personality, + GNU_Ada_Personality, + GNU_CXX_Personality +}; + +/// RecognizePersonality - See if the given exception handling personality +/// function is one that we understand. If so, return a description of it; +/// otherwise return Unknown_Personality. +static Personality_Type RecognizePersonality(Value *Pers) { + Function *F = dyn_cast(Pers->stripPointerCasts()); + if (!F) + return Unknown_Personality; + return StringSwitch(F->getName()) + .Case("__gnat_eh_personality", GNU_Ada_Personality) + .Case("__gxx_personality_v0", GNU_CXX_Personality) + .Default(Unknown_Personality); +} + +/// isCatchAll - Return 'true' if the given typeinfo will match anything. +static bool isCatchAll(Personality_Type Personality, Constant *TypeInfo) { + switch (Personality) { + case Unknown_Personality: + return false; + case GNU_Ada_Personality: + // While __gnat_all_others_value will match any Ada exception, it doesn't + // match foreign exceptions (or didn't, before gcc-4.7). + return false; + case GNU_CXX_Personality: + return TypeInfo->isNullValue(); + } + llvm_unreachable("Unknown personality!"); +} + +static bool shorter_filter(const Value *LHS, const Value *RHS) { + return + cast(LHS->getType())->getNumElements() + < + cast(RHS->getType())->getNumElements(); +} + +Instruction *InstCombiner::visitLandingPadInst(LandingPadInst &LI) { + // The logic here should be correct for any real-world personality function. + // However if that turns out not to be true, the offending logic can always + // be conditioned on the personality function, like the catch-all logic is. + Personality_Type Personality = RecognizePersonality(LI.getPersonalityFn()); + + // Simplify the list of clauses, eg by removing repeated catch clauses + // (these are often created by inlining). + bool MakeNewInstruction = false; // If true, recreate using the following: + SmallVector NewClauses; // - Clauses for the new instruction; + bool CleanupFlag = LI.isCleanup(); // - The new instruction is a cleanup. + + SmallPtrSet AlreadyCaught; // Typeinfos known caught already. + for (unsigned i = 0, e = LI.getNumClauses(); i != e; ++i) { + bool isLastClause = i + 1 == e; + if (LI.isCatch(i)) { + // A catch clause. + Value *CatchClause = LI.getClause(i); + Constant *TypeInfo = cast(CatchClause->stripPointerCasts()); + + // If we already saw this clause, there is no point in having a second + // copy of it. + if (AlreadyCaught.insert(TypeInfo)) { + // This catch clause was not already seen. + NewClauses.push_back(CatchClause); + } else { + // Repeated catch clause - drop the redundant copy. + MakeNewInstruction = true; + } + + // If this is a catch-all then there is no point in keeping any following + // clauses or marking the landingpad as having a cleanup. + if (isCatchAll(Personality, TypeInfo)) { + if (!isLastClause) + MakeNewInstruction = true; + CleanupFlag = false; + break; + } + } else { + // A filter clause. If any of the filter elements were already caught + // then they can be dropped from the filter. It is tempting to try to + // exploit the filter further by saying that any typeinfo that does not + // occur in the filter can't be caught later (and thus can be dropped). + // However this would be wrong, since typeinfos can match without being + // equal (for example if one represents a C++ class, and the other some + // class derived from it). + assert(LI.isFilter(i) && "Unsupported landingpad clause!"); + Value *FilterClause = LI.getClause(i); + ArrayType *FilterType = cast(FilterClause->getType()); + unsigned NumTypeInfos = FilterType->getNumElements(); + + // An empty filter catches everything, so there is no point in keeping any + // following clauses or marking the landingpad as having a cleanup. By + // dealing with this case here the following code is made a bit simpler. + if (!NumTypeInfos) { + NewClauses.push_back(FilterClause); + if (!isLastClause) + MakeNewInstruction = true; + CleanupFlag = false; + break; + } + + bool MakeNewFilter = false; // If true, make a new filter. + SmallVector NewFilterElts; // New elements. + if (isa(FilterClause)) { + // Not an empty filter - it contains at least one null typeinfo. + assert(NumTypeInfos > 0 && "Should have handled empty filter already!"); + Constant *TypeInfo = + Constant::getNullValue(FilterType->getElementType()); + // If this typeinfo is a catch-all then the filter can never match. + if (isCatchAll(Personality, TypeInfo)) { + // Throw the filter away. + MakeNewInstruction = true; + continue; + } + + // There is no point in having multiple copies of this typeinfo, so + // discard all but the first copy if there is more than one. + NewFilterElts.push_back(TypeInfo); + if (NumTypeInfos > 1) + MakeNewFilter = true; + } else { + ConstantArray *Filter = cast(FilterClause); + SmallPtrSet SeenInFilter; // For uniquing the elements. + NewFilterElts.reserve(NumTypeInfos); + + // Remove any filter elements that were already caught or that already + // occurred in the filter. While there, see if any of the elements are + // catch-alls. If so, the filter can be discarded. + bool SawCatchAll = false; + for (unsigned j = 0; j != NumTypeInfos; ++j) { + Value *Elt = Filter->getOperand(j); + Constant *TypeInfo = cast(Elt->stripPointerCasts()); + if (isCatchAll(Personality, TypeInfo)) { + // This element is a catch-all. Bail out, noting this fact. + SawCatchAll = true; + break; + } + if (AlreadyCaught.count(TypeInfo)) + // Already caught by an earlier clause, so having it in the filter + // is pointless. + continue; + // There is no point in having multiple copies of the same typeinfo in + // a filter, so only add it if we didn't already. + if (SeenInFilter.insert(TypeInfo)) + NewFilterElts.push_back(cast(Elt)); + } + // A filter containing a catch-all cannot match anything by definition. + if (SawCatchAll) { + // Throw the filter away. + MakeNewInstruction = true; + continue; + } + + // If we dropped something from the filter, make a new one. + if (NewFilterElts.size() < NumTypeInfos) + MakeNewFilter = true; + } + if (MakeNewFilter) { + FilterType = ArrayType::get(FilterType->getElementType(), + NewFilterElts.size()); + FilterClause = ConstantArray::get(FilterType, NewFilterElts); + MakeNewInstruction = true; + } + + NewClauses.push_back(FilterClause); + + // If the new filter is empty then it will catch everything so there is + // no point in keeping any following clauses or marking the landingpad + // as having a cleanup. The case of the original filter being empty was + // already handled above. + if (MakeNewFilter && !NewFilterElts.size()) { + assert(MakeNewInstruction && "New filter but not a new instruction!"); + CleanupFlag = false; + break; + } + } + } + + // If several filters occur in a row then reorder them so that the shortest + // filters come first (those with the smallest number of elements). This is + // advantageous because shorter filters are more likely to match, speeding up + // unwinding, but mostly because it increases the effectiveness of the other + // filter optimizations below. + for (unsigned i = 0, e = NewClauses.size(); i + 1 < e; ) { + unsigned j; + // Find the maximal 'j' s.t. the range [i, j) consists entirely of filters. + for (j = i; j != e; ++j) + if (!isa(NewClauses[j]->getType())) + break; + + // Check whether the filters are already sorted by length. We need to know + // if sorting them is actually going to do anything so that we only make a + // new landingpad instruction if it does. + for (unsigned k = i; k + 1 < j; ++k) + if (shorter_filter(NewClauses[k+1], NewClauses[k])) { + // Not sorted, so sort the filters now. Doing an unstable sort would be + // correct too but reordering filters pointlessly might confuse users. + std::stable_sort(NewClauses.begin() + i, NewClauses.begin() + j, + shorter_filter); + MakeNewInstruction = true; + break; + } + + // Look for the next batch of filters. + i = j + 1; + } + + // If typeinfos matched if and only if equal, then the elements of a filter L + // that occurs later than a filter F could be replaced by the intersection of + // the elements of F and L. In reality two typeinfos can match without being + // equal (for example if one represents a C++ class, and the other some class + // derived from it) so it would be wrong to perform this transform in general. + // However the transform is correct and useful if F is a subset of L. In that + // case L can be replaced by F, and thus removed altogether since repeating a + // filter is pointless. So here we look at all pairs of filters F and L where + // L follows F in the list of clauses, and remove L if every element of F is + // an element of L. This can occur when inlining C++ functions with exception + // specifications. + for (unsigned i = 0; i + 1 < NewClauses.size(); ++i) { + // Examine each filter in turn. + Value *Filter = NewClauses[i]; + ArrayType *FTy = dyn_cast(Filter->getType()); + if (!FTy) + // Not a filter - skip it. + continue; + unsigned FElts = FTy->getNumElements(); + // Examine each filter following this one. Doing this backwards means that + // we don't have to worry about filters disappearing under us when removed. + for (unsigned j = NewClauses.size() - 1; j != i; --j) { + Value *LFilter = NewClauses[j]; + ArrayType *LTy = dyn_cast(LFilter->getType()); + if (!LTy) + // Not a filter - skip it. + continue; + // If Filter is a subset of LFilter, i.e. every element of Filter is also + // an element of LFilter, then discard LFilter. + SmallVector::iterator J = NewClauses.begin() + j; + // If Filter is empty then it is a subset of LFilter. + if (!FElts) { + // Discard LFilter. + NewClauses.erase(J); + MakeNewInstruction = true; + // Move on to the next filter. + continue; + } + unsigned LElts = LTy->getNumElements(); + // If Filter is longer than LFilter then it cannot be a subset of it. + if (FElts > LElts) + // Move on to the next filter. + continue; + // At this point we know that LFilter has at least one element. + if (isa(LFilter)) { // LFilter only contains zeros. + // Filter is a subset of LFilter iff Filter contains only zeros (as we + // already know that Filter is not longer than LFilter). + if (isa(Filter)) { + assert(FElts <= LElts && "Should have handled this case earlier!"); + // Discard LFilter. + NewClauses.erase(J); + MakeNewInstruction = true; + } + // Move on to the next filter. + continue; + } + ConstantArray *LArray = cast(LFilter); + if (isa(Filter)) { // Filter only contains zeros. + // Since Filter is non-empty and contains only zeros, it is a subset of + // LFilter iff LFilter contains a zero. + assert(FElts > 0 && "Should have eliminated the empty filter earlier!"); + for (unsigned l = 0; l != LElts; ++l) + if (LArray->getOperand(l)->isNullValue()) { + // LFilter contains a zero - discard it. + NewClauses.erase(J); + MakeNewInstruction = true; + break; + } + // Move on to the next filter. + continue; + } + // At this point we know that both filters are ConstantArrays. Loop over + // operands to see whether every element of Filter is also an element of + // LFilter. Since filters tend to be short this is probably faster than + // using a method that scales nicely. + ConstantArray *FArray = cast(Filter); + bool AllFound = true; + for (unsigned f = 0; f != FElts; ++f) { + Value *FTypeInfo = FArray->getOperand(f)->stripPointerCasts(); + AllFound = false; + for (unsigned l = 0; l != LElts; ++l) { + Value *LTypeInfo = LArray->getOperand(l)->stripPointerCasts(); + if (LTypeInfo == FTypeInfo) { + AllFound = true; + break; + } + } + if (!AllFound) + break; + } + if (AllFound) { + // Discard LFilter. + NewClauses.erase(J); + MakeNewInstruction = true; + } + // Move on to the next filter. + } + } + + // If we changed any of the clauses, replace the old landingpad instruction + // with a new one. + if (MakeNewInstruction) { + LandingPadInst *NLI = LandingPadInst::Create(LI.getType(), + LI.getPersonalityFn(), + NewClauses.size()); + for (unsigned i = 0, e = NewClauses.size(); i != e; ++i) + NLI->addClause(NewClauses[i]); + // A landing pad with no clauses must have the cleanup flag set. It is + // theoretically possible, though highly unlikely, that we eliminated all + // clauses. If so, force the cleanup flag to true. + if (NewClauses.empty()) + CleanupFlag = true; + NLI->setCleanup(CleanupFlag); + return NLI; + } + + // Even if none of the clauses changed, we may nonetheless have understood + // that the cleanup flag is pointless. Clear it if so. + if (LI.isCleanup() != CleanupFlag) { + assert(!CleanupFlag && "Adding a cleanup, not removing one?!"); + LI.setCleanup(CleanupFlag); + return &LI; + } + + return 0; +} + diff --git a/test/Transforms/InstCombine/LandingPadClauses.ll b/test/Transforms/InstCombine/LandingPadClauses.ll new file mode 100644 index 00000000000..e96bf4c7f4c --- /dev/null +++ b/test/Transforms/InstCombine/LandingPadClauses.ll @@ -0,0 +1,157 @@ +; RUN: opt < %s -instcombine -S | FileCheck %s + +@T1 = external constant i32 +@T2 = external constant i32 +@T3 = external constant i32 + +declare i32 @generic_personality(i32, i64, i8*, i8*) +declare i32 @__gxx_personality_v0(i32, i64, i8*, i8*) + +declare void @bar() + +define void @foo_generic() { +; CHECK: @foo_generic + invoke void @bar() + to label %cont.a unwind label %lpad.a +cont.a: + invoke void @bar() + to label %cont.b unwind label %lpad.b +cont.b: + invoke void @bar() + to label %cont.c unwind label %lpad.c +cont.c: + invoke void @bar() + to label %cont.d unwind label %lpad.d +cont.d: + invoke void @bar() + to label %cont.e unwind label %lpad.e +cont.e: + invoke void @bar() + to label %cont.f unwind label %lpad.f +cont.f: + invoke void @bar() + to label %cont.g unwind label %lpad.g +cont.g: + invoke void @bar() + to label %cont.h unwind label %lpad.h +cont.h: + ret void + +lpad.a: + %a = landingpad { i8*, i32 } personality i32 (i32, i64, i8*, i8*)* @generic_personality + catch i32* @T1 + catch i32* @T2 + catch i32* @T1 + catch i32* @T2 + unreachable +; CHECK: %a = landingpad +; CHECK-NEXT: @T1 +; CHECK-NEXT: @T2 +; CHECK-NEXT: unreachable + +lpad.b: + %b = landingpad { i8*, i32 } personality i32 (i32, i64, i8*, i8*)* @generic_personality + filter [0 x i32*] zeroinitializer + catch i32* @T1 + unreachable +; CHECK: %b = landingpad +; CHECK-NEXT: filter +; CHECK-NEXT: unreachable + +lpad.c: + %c = landingpad { i8*, i32 } personality i32 (i32, i64, i8*, i8*)* @generic_personality + catch i32* @T1 + filter [1 x i32*] [i32* @T1] + catch i32* @T2 + unreachable +; CHECK: %c = landingpad +; CHECK-NEXT: @T1 +; CHECK-NEXT: filter [0 x i32*] +; CHECK-NEXT: unreachable + +lpad.d: + %d = landingpad { i8*, i32 } personality i32 (i32, i64, i8*, i8*)* @generic_personality + filter [3 x i32*] zeroinitializer + unreachable +; CHECK: %d = landingpad +; CHECK-NEXT: filter [1 x i32*] zeroinitializer +; CHECK-NEXT: unreachable + +lpad.e: + %e = landingpad { i8*, i32 } personality i32 (i32, i64, i8*, i8*)* @generic_personality + catch i32* @T1 + filter [3 x i32*] [i32* @T1, i32* @T2, i32* @T2] + unreachable +; CHECK: %e = landingpad +; CHECK-NEXT: @T1 +; CHECK-NEXT: filter [1 x i32*] [i32* @T2] +; CHECK-NEXT: unreachable + +lpad.f: + %f = landingpad { i8*, i32 } personality i32 (i32, i64, i8*, i8*)* @generic_personality + filter [2 x i32*] [i32* @T2, i32* @T1] + filter [1 x i32*] [i32* @T1] + unreachable +; CHECK: %f = landingpad +; CHECK-NEXT: filter [1 x i32*] [i32* @T1] +; CHECK-NEXT: unreachable + +lpad.g: + %g = landingpad { i8*, i32 } personality i32 (i32, i64, i8*, i8*)* @generic_personality + filter [1 x i32*] [i32* @T1] + catch i32* @T3 + filter [2 x i32*] [i32* @T2, i32* @T1] + unreachable +; CHECK: %g = landingpad +; CHECK-NEXT: filter [1 x i32*] [i32* @T1] +; CHECK-NEXT: catch i32* @T3 +; CHECK-NEXT: unreachable + +lpad.h: + %h = landingpad { i8*, i32 } personality i32 (i32, i64, i8*, i8*)* @generic_personality + filter [2 x i32*] [i32* @T1, i32* null] + filter [1 x i32*] zeroinitializer + unreachable +; CHECK: %h = landingpad +; CHECK-NEXT: filter [1 x i32*] zeroinitializer +; CHECK-NEXT: unreachable +} + +define void @foo_cxx() { +; CHECK: @foo_cxx + invoke void @bar() + to label %cont.a unwind label %lpad.a +cont.a: + invoke void @bar() + to label %cont.b unwind label %lpad.b +cont.b: + invoke void @bar() + to label %cont.c unwind label %lpad.c +cont.c: + ret void + +lpad.a: + %a = landingpad { i8*, i32 } personality i32 (i32, i64, i8*, i8*)* @__gxx_personality_v0 + catch i32* null + catch i32* @T1 + unreachable +; CHECK: %a = landingpad +; CHECK-NEXT: null +; CHECK-NEXT: unreachable + +lpad.b: + %b = landingpad { i8*, i32 } personality i32 (i32, i64, i8*, i8*)* @__gxx_personality_v0 + filter [1 x i32*] zeroinitializer + unreachable +; CHECK: %b = landingpad +; CHECK-NEXT: cleanup +; CHECK-NEXT: unreachable + +lpad.c: + %c = landingpad { i8*, i32 } personality i32 (i32, i64, i8*, i8*)* @__gxx_personality_v0 + filter [2 x i32*] [i32* @T1, i32* null] + unreachable +; CHECK: %c = landingpad +; CHECK-NEXT: cleanup +; CHECK-NEXT: unreachable +} -- 2.34.1