1 //===- ModuleInliner.cpp - Code related to module inliner -----------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the mechanics required to implement inlining without 10 // missing any calls in the module level. It doesn't need any infromation about 11 // SCC or call graph, which is different from the SCC inliner. The decisions of 12 // which calls are profitable to inline are implemented elsewhere. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #include "llvm/Transforms/IPO/ModuleInliner.h" 17 #include "llvm/ADT/ScopeExit.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/ADT/Statistic.h" 20 #include "llvm/Analysis/AliasAnalysis.h" 21 #include "llvm/Analysis/AssumptionCache.h" 22 #include "llvm/Analysis/BlockFrequencyInfo.h" 23 #include "llvm/Analysis/CtxProfAnalysis.h" 24 #include "llvm/Analysis/InlineAdvisor.h" 25 #include "llvm/Analysis/InlineCost.h" 26 #include "llvm/Analysis/InlineOrder.h" 27 #include "llvm/Analysis/OptimizationRemarkEmitter.h" 28 #include "llvm/Analysis/ProfileSummaryInfo.h" 29 #include "llvm/Analysis/ReplayInlineAdvisor.h" 30 #include "llvm/Analysis/TargetLibraryInfo.h" 31 #include "llvm/IR/DiagnosticInfo.h" 32 #include "llvm/IR/Function.h" 33 #include "llvm/IR/InstIterator.h" 34 #include "llvm/IR/Instruction.h" 35 #include "llvm/IR/IntrinsicInst.h" 36 #include "llvm/IR/Module.h" 37 #include "llvm/IR/PassManager.h" 38 #include "llvm/Support/CommandLine.h" 39 #include "llvm/Support/Debug.h" 40 #include "llvm/Support/raw_ostream.h" 41 #include "llvm/Transforms/Utils/CallPromotionUtils.h" 42 #include "llvm/Transforms/Utils/Cloning.h" 43 #include <cassert> 44 45 using namespace llvm; 46 47 #define DEBUG_TYPE "module-inline" 48 49 STATISTIC(NumInlined, "Number of functions inlined"); 50 STATISTIC(NumDeleted, "Number of functions deleted because all callers found"); 51 52 /// Return true if the specified inline history ID 53 /// indicates an inline history that includes the specified function. 54 static bool inlineHistoryIncludes( 55 Function *F, int InlineHistoryID, 56 const SmallVectorImpl<std::pair<Function *, int>> &InlineHistory) { 57 while (InlineHistoryID != -1) { 58 assert(unsigned(InlineHistoryID) < InlineHistory.size() && 59 "Invalid inline history ID"); 60 if (InlineHistory[InlineHistoryID].first == F) 61 return true; 62 InlineHistoryID = InlineHistory[InlineHistoryID].second; 63 } 64 return false; 65 } 66 67 InlineAdvisor &ModuleInlinerPass::getAdvisor(const ModuleAnalysisManager &MAM, 68 FunctionAnalysisManager &FAM, 69 Module &M) { 70 if (OwnedAdvisor) 71 return *OwnedAdvisor; 72 73 auto *IAA = MAM.getCachedResult<InlineAdvisorAnalysis>(M); 74 if (!IAA) { 75 // It should still be possible to run the inliner as a stand-alone module 76 // pass, for test scenarios. In that case, we default to the 77 // DefaultInlineAdvisor, which doesn't need to keep state between module 78 // pass runs. It also uses just the default InlineParams. In this case, we 79 // need to use the provided FAM, which is valid for the duration of the 80 // inliner pass, and thus the lifetime of the owned advisor. The one we 81 // would get from the MAM can be invalidated as a result of the inliner's 82 // activity. 83 OwnedAdvisor = std::make_unique<DefaultInlineAdvisor>( 84 M, FAM, Params, InlineContext{LTOPhase, InlinePass::ModuleInliner}); 85 86 return *OwnedAdvisor; 87 } 88 assert(IAA->getAdvisor() && 89 "Expected a present InlineAdvisorAnalysis also have an " 90 "InlineAdvisor initialized"); 91 return *IAA->getAdvisor(); 92 } 93 94 static bool isKnownLibFunction(Function &F, TargetLibraryInfo &TLI) { 95 LibFunc LF; 96 97 // Either this is a normal library function or a "vectorizable" 98 // function. Not using the VFDatabase here because this query 99 // is related only to libraries handled via the TLI. 100 return TLI.getLibFunc(F, LF) || 101 TLI.isKnownVectorFunctionInLibrary(F.getName()); 102 } 103 104 PreservedAnalyses ModuleInlinerPass::run(Module &M, 105 ModuleAnalysisManager &MAM) { 106 LLVM_DEBUG(dbgs() << "---- Module Inliner is Running ---- \n"); 107 108 auto &IAA = MAM.getResult<InlineAdvisorAnalysis>(M); 109 if (!IAA.tryCreate(Params, Mode, {}, 110 InlineContext{LTOPhase, InlinePass::ModuleInliner})) { 111 M.getContext().emitError( 112 "Could not setup Inlining Advisor for the requested " 113 "mode and/or options"); 114 return PreservedAnalyses::all(); 115 } 116 117 auto &CtxProf = MAM.getResult<CtxProfAnalysis>(M); 118 119 bool Changed = false; 120 121 ProfileSummaryInfo *PSI = MAM.getCachedResult<ProfileSummaryAnalysis>(M); 122 123 FunctionAnalysisManager &FAM = 124 MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 125 126 auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & { 127 return FAM.getResult<TargetLibraryAnalysis>(F); 128 }; 129 130 InlineAdvisor &Advisor = getAdvisor(MAM, FAM, M); 131 Advisor.onPassEntry(); 132 133 auto AdvisorOnExit = make_scope_exit([&] { Advisor.onPassExit(); }); 134 135 // In the module inliner, a priority-based worklist is used for calls across 136 // the entire Module. With this module inliner, the inline order is not 137 // limited to bottom-up order. More globally scope inline order is enabled. 138 // Also, the inline deferral logic become unnecessary in this module inliner. 139 // It is possible to use other priority heuristics, e.g. profile-based 140 // heuristic. 141 // 142 // TODO: Here is a huge amount duplicate code between the module inliner and 143 // the SCC inliner, which need some refactoring. 144 auto Calls = getInlineOrder(FAM, Params, MAM, M); 145 assert(Calls != nullptr && "Expected an initialized InlineOrder"); 146 147 // Populate the initial list of calls in this module. 148 for (Function &F : M) { 149 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F); 150 for (Instruction &I : instructions(F)) 151 if (auto *CB = dyn_cast<CallBase>(&I)) 152 if (Function *Callee = CB->getCalledFunction()) { 153 if (!Callee->isDeclaration()) 154 Calls->push({CB, -1}); 155 else if (!isa<IntrinsicInst>(I)) { 156 using namespace ore; 157 setInlineRemark(*CB, "unavailable definition"); 158 ORE.emit([&]() { 159 return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I) 160 << NV("Callee", Callee) << " will not be inlined into " 161 << NV("Caller", CB->getCaller()) 162 << " because its definition is unavailable" 163 << setIsVerbose(); 164 }); 165 } 166 } 167 } 168 if (Calls->empty()) 169 return PreservedAnalyses::all(); 170 171 // When inlining a callee produces new call sites, we want to keep track of 172 // the fact that they were inlined from the callee. This allows us to avoid 173 // infinite inlining in some obscure cases. To represent this, we use an 174 // index into the InlineHistory vector. 175 SmallVector<std::pair<Function *, int>, 16> InlineHistory; 176 177 // Track the dead functions to delete once finished with inlining calls. We 178 // defer deleting these to make it easier to handle the call graph updates. 179 SmallVector<Function *, 4> DeadFunctions; 180 181 // Loop forward over all of the calls. 182 while (!Calls->empty()) { 183 auto P = Calls->pop(); 184 CallBase *CB = P.first; 185 const int InlineHistoryID = P.second; 186 Function &F = *CB->getCaller(); 187 Function &Callee = *CB->getCalledFunction(); 188 189 LLVM_DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n" 190 << " Function size: " << F.getInstructionCount() 191 << "\n"); 192 (void)F; 193 194 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & { 195 return FAM.getResult<AssumptionAnalysis>(F); 196 }; 197 198 if (InlineHistoryID != -1 && 199 inlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory)) { 200 setInlineRemark(*CB, "recursive"); 201 continue; 202 } 203 204 auto Advice = Advisor.getAdvice(*CB, /*OnlyMandatory*/ false); 205 // Check whether we want to inline this callsite. 206 if (!Advice->isInliningRecommended()) { 207 Advice->recordUnattemptedInlining(); 208 continue; 209 } 210 211 // Setup the data structure used to plumb customization into the 212 // `InlineFunction` routine. 213 InlineFunctionInfo IFI( 214 GetAssumptionCache, PSI, 215 &FAM.getResult<BlockFrequencyAnalysis>(*(CB->getCaller())), 216 &FAM.getResult<BlockFrequencyAnalysis>(Callee)); 217 218 InlineResult IR = 219 InlineFunction(*CB, IFI, CtxProf, /*MergeAttributes=*/true, 220 &FAM.getResult<AAManager>(*CB->getCaller())); 221 if (!IR.isSuccess()) { 222 Advice->recordUnsuccessfulInlining(IR); 223 continue; 224 } 225 226 Changed = true; 227 ++NumInlined; 228 229 LLVM_DEBUG(dbgs() << " Size after inlining: " << F.getInstructionCount() 230 << "\n"); 231 232 // Add any new callsites to defined functions to the worklist. 233 if (!IFI.InlinedCallSites.empty()) { 234 int NewHistoryID = InlineHistory.size(); 235 InlineHistory.push_back({&Callee, InlineHistoryID}); 236 237 for (CallBase *ICB : reverse(IFI.InlinedCallSites)) { 238 Function *NewCallee = ICB->getCalledFunction(); 239 if (!NewCallee) { 240 // Try to promote an indirect (virtual) call without waiting for 241 // the post-inline cleanup and the next DevirtSCCRepeatedPass 242 // iteration because the next iteration may not happen and we may 243 // miss inlining it. 244 if (tryPromoteCall(*ICB)) 245 NewCallee = ICB->getCalledFunction(); 246 } 247 if (NewCallee) 248 if (!NewCallee->isDeclaration()) 249 Calls->push({ICB, NewHistoryID}); 250 } 251 } 252 253 // For local functions, check whether this makes the callee trivially 254 // dead. In that case, we can drop the body of the function eagerly 255 // which may reduce the number of callers of other functions to one, 256 // changing inline cost thresholds. 257 bool CalleeWasDeleted = false; 258 if (Callee.hasLocalLinkage()) { 259 // To check this we also need to nuke any dead constant uses (perhaps 260 // made dead by this operation on other functions). 261 Callee.removeDeadConstantUsers(); 262 // if (Callee.use_empty() && !CG.isLibFunction(Callee)) { 263 if (Callee.use_empty() && !isKnownLibFunction(Callee, GetTLI(Callee))) { 264 Calls->erase_if([&](const std::pair<CallBase *, int> &Call) { 265 return Call.first->getCaller() == &Callee; 266 }); 267 // Clear the body and queue the function itself for deletion when we 268 // finish inlining. 269 // Note that after this point, it is an error to do anything other 270 // than use the callee's address or delete it. 271 Callee.dropAllReferences(); 272 assert(!is_contained(DeadFunctions, &Callee) && 273 "Cannot put cause a function to become dead twice!"); 274 DeadFunctions.push_back(&Callee); 275 CalleeWasDeleted = true; 276 } 277 } 278 if (CalleeWasDeleted) 279 Advice->recordInliningWithCalleeDeleted(); 280 else 281 Advice->recordInlining(); 282 } 283 284 // Now that we've finished inlining all of the calls across this module, 285 // delete all of the trivially dead functions. 286 // 287 // Note that this walks a pointer set which has non-deterministic order but 288 // that is OK as all we do is delete things and add pointers to unordered 289 // sets. 290 for (Function *DeadF : DeadFunctions) { 291 // Clear out any cached analyses. 292 FAM.clear(*DeadF, DeadF->getName()); 293 294 // And delete the actual function from the module. 295 M.getFunctionList().erase(DeadF); 296 297 ++NumDeleted; 298 } 299 300 if (!Changed) 301 return PreservedAnalyses::all(); 302 303 return PreservedAnalyses::none(); 304 } 305