diff options
| -rw-r--r-- | llvm/include/llvm/Transforms/Utils/ModuleUtils.h | 16 | ||||
| -rw-r--r-- | llvm/lib/Transforms/IPO/AlwaysInliner.cpp | 28 | ||||
| -rw-r--r-- | llvm/lib/Transforms/IPO/Inliner.cpp | 40 | ||||
| -rw-r--r-- | llvm/lib/Transforms/Utils/ModuleUtils.cpp | 64 | ||||
| -rw-r--r-- | llvm/test/Transforms/Inline/always-inline.ll | 27 |
5 files changed, 137 insertions, 38 deletions
diff --git a/llvm/include/llvm/Transforms/Utils/ModuleUtils.h b/llvm/include/llvm/Transforms/Utils/ModuleUtils.h index ca5750cf68d..27508799f8e 100644 --- a/llvm/include/llvm/Transforms/Utils/ModuleUtils.h +++ b/llvm/include/llvm/Transforms/Utils/ModuleUtils.h @@ -65,6 +65,22 @@ void appendToUsed(Module &M, ArrayRef<GlobalValue *> Values); /// \brief Adds global values to the llvm.compiler.used list. void appendToCompilerUsed(Module &M, ArrayRef<GlobalValue *> Values); +/// Filter out potentially dead comdat functions where other entries keep the +/// entire comdat group alive. +/// +/// This is designed for cases where functions appear to become dead but remain +/// alive due to other live entries in their comdat group. +/// +/// The \p DeadComdatFunctions container should only have pointers to +/// `Function`s which are members of a comdat group and are believed to be +/// dead. +/// +/// After this routine finishes, the only remaining `Function`s in \p +/// DeadComdatFunctions are those where every member of the comdat is listed +/// and thus removing them is safe (provided *all* are removed). +void filterDeadComdatFunctions( + Module &M, SmallVectorImpl<Function *> &DeadComdatFunctions); + } // End llvm namespace #endif // LLVM_TRANSFORMS_UTILS_MODULEUTILS_H diff --git a/llvm/lib/Transforms/IPO/AlwaysInliner.cpp b/llvm/lib/Transforms/IPO/AlwaysInliner.cpp index 1a3f8ced465..b7d96007c24 100644 --- a/llvm/lib/Transforms/IPO/AlwaysInliner.cpp +++ b/llvm/lib/Transforms/IPO/AlwaysInliner.cpp @@ -29,6 +29,7 @@ #include "llvm/Transforms/IPO.h" #include "llvm/Transforms/IPO/Inliner.h" #include "llvm/Transforms/Utils/Cloning.h" +#include "llvm/Transforms/Utils/ModuleUtils.h" using namespace llvm; @@ -60,13 +61,26 @@ PreservedAnalyses AlwaysInlinerPass::run(Module &M, ModuleAnalysisManager &) { InlinedFunctions.push_back(&F); } - // Now try to delete all the functions we inlined. - for (Function *InlinedF : InlinedFunctions) { - InlinedF->removeDeadConstantUsers(); - // FIXME: We should use some utility to handle cases where we can - // completely remove the comdat. - if (InlinedF->isDefTriviallyDead() && !InlinedF->hasComdat()) - M.getFunctionList().erase(InlinedF); + // Remove any live functions. + erase_if(InlinedFunctions, [&](Function *F) { + F->removeDeadConstantUsers(); + return !F->isDefTriviallyDead(); + }); + + // Delete the non-comdat ones from the module and also from our vector. + auto NonComdatBegin = partition( + InlinedFunctions, [&](Function *F) { return F->hasComdat(); }); + for (Function *F : make_range(NonComdatBegin, InlinedFunctions.end())) + M.getFunctionList().erase(F); + InlinedFunctions.erase(NonComdatBegin, InlinedFunctions.end()); + + if (!InlinedFunctions.empty()) { + // Now we just have the comdat functions. Filter out the ones whose comdats + // are not actually dead. + filterDeadComdatFunctions(M, InlinedFunctions); + // The remaining functions are actually dead. + for (Function *F : InlinedFunctions) + M.getFunctionList().erase(F); } return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all(); diff --git a/llvm/lib/Transforms/IPO/Inliner.cpp b/llvm/lib/Transforms/IPO/Inliner.cpp index 7b2db949d5a..ff534a19e53 100644 --- a/llvm/lib/Transforms/IPO/Inliner.cpp +++ b/llvm/lib/Transforms/IPO/Inliner.cpp @@ -35,6 +35,7 @@ #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/Cloning.h" #include "llvm/Transforms/Utils/Local.h" +#include "llvm/Transforms/Utils/ModuleUtils.h" using namespace llvm; #define DEBUG_TYPE "inline" @@ -668,8 +669,7 @@ bool LegacyInlinerBase::doFinalization(CallGraph &CG) { bool LegacyInlinerBase::removeDeadFunctions(CallGraph &CG, bool AlwaysInlineOnly) { SmallVector<CallGraphNode *, 16> FunctionsToRemove; - SmallVector<CallGraphNode *, 16> DeadFunctionsInComdats; - SmallDenseMap<const Comdat *, int, 16> ComdatEntriesAlive; + SmallVector<Function *, 16> DeadFunctionsInComdats; auto RemoveCGN = [&](CallGraphNode *CGN) { // Remove any call graph edges from the function to its callees. @@ -710,9 +710,8 @@ bool LegacyInlinerBase::removeDeadFunctions(CallGraph &CG, // The inliner doesn't visit non-function entities which are in COMDAT // groups so it is unsafe to do so *unless* the linkage is local. if (!F->hasLocalLinkage()) { - if (const Comdat *C = F->getComdat()) { - --ComdatEntriesAlive[C]; - DeadFunctionsInComdats.push_back(CGN); + if (F->hasComdat()) { + DeadFunctionsInComdats.push_back(F); continue; } } @@ -720,32 +719,11 @@ bool LegacyInlinerBase::removeDeadFunctions(CallGraph &CG, RemoveCGN(CGN); } if (!DeadFunctionsInComdats.empty()) { - // Count up all the entities in COMDAT groups - auto ComdatGroupReferenced = [&](const Comdat *C) { - auto I = ComdatEntriesAlive.find(C); - if (I != ComdatEntriesAlive.end()) - ++(I->getSecond()); - }; - for (const Function &F : CG.getModule()) - if (const Comdat *C = F.getComdat()) - ComdatGroupReferenced(C); - for (const GlobalVariable &GV : CG.getModule().globals()) - if (const Comdat *C = GV.getComdat()) - ComdatGroupReferenced(C); - for (const GlobalAlias &GA : CG.getModule().aliases()) - if (const Comdat *C = GA.getComdat()) - ComdatGroupReferenced(C); - for (CallGraphNode *CGN : DeadFunctionsInComdats) { - Function *F = CGN->getFunction(); - const Comdat *C = F->getComdat(); - int NumAlive = ComdatEntriesAlive[C]; - // We can remove functions in a COMDAT group if the entire group is dead. - assert(NumAlive >= 0); - if (NumAlive > 0) - continue; - - RemoveCGN(CGN); - } + // Filter out the functions whose comdats remain alive. + filterDeadComdatFunctions(CG.getModule(), DeadFunctionsInComdats); + // Remove the rest. + for (Function *F : DeadFunctionsInComdats) + RemoveCGN(CG[F]); } if (FunctionsToRemove.empty()) diff --git a/llvm/lib/Transforms/Utils/ModuleUtils.cpp b/llvm/lib/Transforms/Utils/ModuleUtils.cpp index be9b77b7771..0d623df77a6 100644 --- a/llvm/lib/Transforms/Utils/ModuleUtils.cpp +++ b/llvm/lib/Transforms/Utils/ModuleUtils.cpp @@ -164,3 +164,67 @@ std::pair<Function *, Function *> llvm::createSanitizerCtorAndInitFunctions( } return std::make_pair(Ctor, InitFunction); } + +void llvm::filterDeadComdatFunctions( + Module &M, SmallVectorImpl<Function *> &DeadComdatFunctions) { + // Build a map from the comdat to the number of entries in that comdat we + // think are dead. If this fully covers the comdat group, then the entire + // group is dead. If we find another entry in the comdat group though, we'll + // have to preserve the whole group. + SmallDenseMap<Comdat *, int, 16> ComdatEntriesCovered; + for (Function *F : DeadComdatFunctions) { + Comdat *C = F->getComdat(); + assert(C && "Expected all input GVs to be in a comdat!"); + ComdatEntriesCovered[C] += 1; + } + + auto CheckComdat = [&](Comdat &C) { + auto CI = ComdatEntriesCovered.find(&C); + if (CI == ComdatEntriesCovered.end()) + return; + + // If this could have been covered by a dead entry, just subtract one to + // account for it. + if (CI->second > 0) { + CI->second -= 1; + return; + } + + // If we've already accounted for all the entries that were dead, the + // entire comdat is alive so remove it from the map. + ComdatEntriesCovered.erase(CI); + }; + + auto CheckAllComdats = [&] { + for (Function &F : M.functions()) + if (Comdat *C = F.getComdat()) { + CheckComdat(*C); + if (ComdatEntriesCovered.empty()) + return; + } + for (GlobalVariable &GV : M.globals()) + if (Comdat *C = GV.getComdat()) { + CheckComdat(*C); + if (ComdatEntriesCovered.empty()) + return; + } + for (GlobalAlias &GA : M.aliases()) + if (Comdat *C = GA.getComdat()) { + CheckComdat(*C); + if (ComdatEntriesCovered.empty()) + return; + } + }; + CheckAllComdats(); + + if (ComdatEntriesCovered.empty()) { + DeadComdatFunctions.clear(); + return; + } + + // Remove the entries that were not covering. + erase_if(DeadComdatFunctions, [&](GlobalValue *GV) { + return ComdatEntriesCovered.find(GV->getComdat()) == + ComdatEntriesCovered.end(); + }); +} diff --git a/llvm/test/Transforms/Inline/always-inline.ll b/llvm/test/Transforms/Inline/always-inline.ll index e8322410b74..5366b5a16cc 100644 --- a/llvm/test/Transforms/Inline/always-inline.ll +++ b/llvm/test/Transforms/Inline/always-inline.ll @@ -278,3 +278,30 @@ entry: ret void ; CHECK: ret void } + +; The 'inner13*' and 'outer13' functions test that we do remove functions +; which are part of a comdat group where all of the members are removed during +; always inlining. +$comdat13 = comdat any + +define linkonce void @inner13a() alwaysinline comdat($comdat13) { +; CHECK-NOT: @inner13a( + ret void +} + +define linkonce void @inner13b() alwaysinline comdat($comdat13) { +; CHECK-NOT: @inner13b( + ret void +} + +define void @outer13() { +; CHECK-LABEL: @outer13( +entry: + call void @inner13a() + call void @inner13b() +; CHECK-NOT: call void @inner13a +; CHECK-NOT: call void @inner13b + + ret void +; CHECK: ret void +} |
