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/SetVector.h" 19 #include "llvm/ADT/SmallVector.h" 20 #include "llvm/ADT/Statistic.h" 21 #include "llvm/Analysis/AliasAnalysis.h" 22 #include "llvm/Analysis/AssumptionCache.h" 23 #include "llvm/Analysis/BlockFrequencyInfo.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 static cl::opt<bool> InlineEnablePriorityOrder( 53 "module-inline-enable-priority-order", cl::Hidden, cl::init(true), 54 cl::desc("Enable the priority inline order for the module inliner")); 55 56 /// Return true if the specified inline history ID 57 /// indicates an inline history that includes the specified function. 58 static bool inlineHistoryIncludes( 59 Function *F, int InlineHistoryID, 60 const SmallVectorImpl<std::pair<Function *, int>> &InlineHistory) { 61 while (InlineHistoryID != -1) { 62 assert(unsigned(InlineHistoryID) < InlineHistory.size() && 63 "Invalid inline history ID"); 64 if (InlineHistory[InlineHistoryID].first == F) 65 return true; 66 InlineHistoryID = InlineHistory[InlineHistoryID].second; 67 } 68 return false; 69 } 70 71 InlineAdvisor &ModuleInlinerPass::getAdvisor(const ModuleAnalysisManager &MAM, 72 FunctionAnalysisManager &FAM, 73 Module &M) { 74 if (OwnedAdvisor) 75 return *OwnedAdvisor; 76 77 auto *IAA = MAM.getCachedResult<InlineAdvisorAnalysis>(M); 78 if (!IAA) { 79 // It should still be possible to run the inliner as a stand-alone module 80 // pass, for test scenarios. In that case, we default to the 81 // DefaultInlineAdvisor, which doesn't need to keep state between module 82 // pass runs. It also uses just the default InlineParams. In this case, we 83 // need to use the provided FAM, which is valid for the duration of the 84 // inliner pass, and thus the lifetime of the owned advisor. The one we 85 // would get from the MAM can be invalidated as a result of the inliner's 86 // activity. 87 OwnedAdvisor = std::make_unique<DefaultInlineAdvisor>( 88 M, FAM, Params, 89 InlineContext{LTOPhase, InlinePass::ModuleInliner}); 90 91 return *OwnedAdvisor; 92 } 93 assert(IAA->getAdvisor() && 94 "Expected a present InlineAdvisorAnalysis also have an " 95 "InlineAdvisor initialized"); 96 return *IAA->getAdvisor(); 97 } 98 99 static bool isKnownLibFunction(Function &F, TargetLibraryInfo &TLI) { 100 LibFunc LF; 101 102 // Either this is a normal library function or a "vectorizable" 103 // function. Not using the VFDatabase here because this query 104 // is related only to libraries handled via the TLI. 105 return TLI.getLibFunc(F, LF) || 106 TLI.isKnownVectorFunctionInLibrary(F.getName()); 107 } 108 109 PreservedAnalyses ModuleInlinerPass::run(Module &M, 110 ModuleAnalysisManager &MAM) { 111 LLVM_DEBUG(dbgs() << "---- Module Inliner is Running ---- \n"); 112 113 auto &IAA = MAM.getResult<InlineAdvisorAnalysis>(M); 114 if (!IAA.tryCreate( 115 Params, Mode, {}, 116 InlineContext{LTOPhase, InlinePass::ModuleInliner})) { 117 M.getContext().emitError( 118 "Could not setup Inlining Advisor for the requested " 119 "mode and/or options"); 120 return PreservedAnalyses::all(); 121 } 122 123 bool Changed = false; 124 125 ProfileSummaryInfo *PSI = MAM.getCachedResult<ProfileSummaryAnalysis>(M); 126 127 FunctionAnalysisManager &FAM = 128 MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 129 130 auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & { 131 return FAM.getResult<TargetLibraryAnalysis>(F); 132 }; 133 134 InlineAdvisor &Advisor = getAdvisor(MAM, FAM, M); 135 Advisor.onPassEntry(); 136 137 auto AdvisorOnExit = make_scope_exit([&] { Advisor.onPassExit(); }); 138 139 // In the module inliner, a priority-based worklist is used for calls across 140 // the entire Module. With this module inliner, the inline order is not 141 // limited to bottom-up order. More globally scope inline order is enabled. 142 // Also, the inline deferral logic become unnecessary in this module inliner. 143 // It is possible to use other priority heuristics, e.g. profile-based 144 // heuristic. 145 // 146 // TODO: Here is a huge amount duplicate code between the module inliner and 147 // the SCC inliner, which need some refactoring. 148 std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>> Calls; 149 if (InlineEnablePriorityOrder) 150 Calls = std::make_unique<PriorityInlineOrder>( 151 std::make_unique<SizePriority>()); 152 else 153 Calls = std::make_unique<DefaultInlineOrder<std::pair<CallBase *, int>>>(); 154 assert(Calls != nullptr && "Expected an initialized InlineOrder"); 155 156 // Populate the initial list of calls in this module. 157 for (Function &F : M) { 158 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F); 159 // We want to generally process call sites top-down in order for 160 // simplifications stemming from replacing the call with the returned value 161 // after inlining to be visible to subsequent inlining decisions. 162 // FIXME: Using instructions sequence is a really bad way to do this. 163 // Instead we should do an actual RPO walk of the function body. 164 for (Instruction &I : instructions(F)) 165 if (auto *CB = dyn_cast<CallBase>(&I)) 166 if (Function *Callee = CB->getCalledFunction()) { 167 if (!Callee->isDeclaration()) 168 Calls->push({CB, -1}); 169 else if (!isa<IntrinsicInst>(I)) { 170 using namespace ore; 171 setInlineRemark(*CB, "unavailable definition"); 172 ORE.emit([&]() { 173 return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I) 174 << NV("Callee", Callee) << " will not be inlined into " 175 << NV("Caller", CB->getCaller()) 176 << " because its definition is unavailable" 177 << setIsVerbose(); 178 }); 179 } 180 } 181 } 182 if (Calls->empty()) 183 return PreservedAnalyses::all(); 184 185 // When inlining a callee produces new call sites, we want to keep track of 186 // the fact that they were inlined from the callee. This allows us to avoid 187 // infinite inlining in some obscure cases. To represent this, we use an 188 // index into the InlineHistory vector. 189 SmallVector<std::pair<Function *, int>, 16> InlineHistory; 190 191 // Track a set vector of inlined callees so that we can augment the caller 192 // with all of their edges in the call graph before pruning out the ones that 193 // got simplified away. 194 SmallSetVector<Function *, 4> InlinedCallees; 195 196 // Track the dead functions to delete once finished with inlining calls. We 197 // defer deleting these to make it easier to handle the call graph updates. 198 SmallVector<Function *, 4> DeadFunctions; 199 200 // Loop forward over all of the calls. 201 while (!Calls->empty()) { 202 // We expect the calls to typically be batched with sequences of calls that 203 // have the same caller, so we first set up some shared infrastructure for 204 // this caller. We also do any pruning we can at this layer on the caller 205 // alone. 206 Function &F = *Calls->front().first->getCaller(); 207 208 LLVM_DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n" 209 << " Function size: " << F.getInstructionCount() 210 << "\n"); 211 212 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & { 213 return FAM.getResult<AssumptionAnalysis>(F); 214 }; 215 216 // Now process as many calls as we have within this caller in the sequence. 217 // We bail out as soon as the caller has to change so we can 218 // prepare the context of that new caller. 219 bool DidInline = false; 220 while (!Calls->empty() && Calls->front().first->getCaller() == &F) { 221 auto P = Calls->pop(); 222 CallBase *CB = P.first; 223 const int InlineHistoryID = P.second; 224 Function &Callee = *CB->getCalledFunction(); 225 226 if (InlineHistoryID != -1 && 227 inlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory)) { 228 setInlineRemark(*CB, "recursive"); 229 continue; 230 } 231 232 auto Advice = Advisor.getAdvice(*CB, /*OnlyMandatory*/ false); 233 // Check whether we want to inline this callsite. 234 if (!Advice->isInliningRecommended()) { 235 Advice->recordUnattemptedInlining(); 236 continue; 237 } 238 239 // Setup the data structure used to plumb customization into the 240 // `InlineFunction` routine. 241 InlineFunctionInfo IFI( 242 /*cg=*/nullptr, GetAssumptionCache, PSI, 243 &FAM.getResult<BlockFrequencyAnalysis>(*(CB->getCaller())), 244 &FAM.getResult<BlockFrequencyAnalysis>(Callee)); 245 246 InlineResult IR = 247 InlineFunction(*CB, IFI, &FAM.getResult<AAManager>(*CB->getCaller())); 248 if (!IR.isSuccess()) { 249 Advice->recordUnsuccessfulInlining(IR); 250 continue; 251 } 252 253 DidInline = true; 254 InlinedCallees.insert(&Callee); 255 ++NumInlined; 256 257 LLVM_DEBUG(dbgs() << " Size after inlining: " 258 << F.getInstructionCount() << "\n"); 259 260 // Add any new callsites to defined functions to the worklist. 261 if (!IFI.InlinedCallSites.empty()) { 262 int NewHistoryID = InlineHistory.size(); 263 InlineHistory.push_back({&Callee, InlineHistoryID}); 264 265 for (CallBase *ICB : reverse(IFI.InlinedCallSites)) { 266 Function *NewCallee = ICB->getCalledFunction(); 267 if (!NewCallee) { 268 // Try to promote an indirect (virtual) call without waiting for 269 // the post-inline cleanup and the next DevirtSCCRepeatedPass 270 // iteration because the next iteration may not happen and we may 271 // miss inlining it. 272 if (tryPromoteCall(*ICB)) 273 NewCallee = ICB->getCalledFunction(); 274 } 275 if (NewCallee) 276 if (!NewCallee->isDeclaration()) 277 Calls->push({ICB, NewHistoryID}); 278 } 279 } 280 281 // Merge the attributes based on the inlining. 282 AttributeFuncs::mergeAttributesForInlining(F, Callee); 283 284 // For local functions, check whether this makes the callee trivially 285 // dead. In that case, we can drop the body of the function eagerly 286 // which may reduce the number of callers of other functions to one, 287 // changing inline cost thresholds. 288 bool CalleeWasDeleted = false; 289 if (Callee.hasLocalLinkage()) { 290 // To check this we also need to nuke any dead constant uses (perhaps 291 // made dead by this operation on other functions). 292 Callee.removeDeadConstantUsers(); 293 // if (Callee.use_empty() && !CG.isLibFunction(Callee)) { 294 if (Callee.use_empty() && !isKnownLibFunction(Callee, GetTLI(Callee))) { 295 Calls->erase_if([&](const std::pair<CallBase *, int> &Call) { 296 return Call.first->getCaller() == &Callee; 297 }); 298 // Clear the body and queue the function itself for deletion when we 299 // finish inlining. 300 // Note that after this point, it is an error to do anything other 301 // than use the callee's address or delete it. 302 Callee.dropAllReferences(); 303 assert(!is_contained(DeadFunctions, &Callee) && 304 "Cannot put cause a function to become dead twice!"); 305 DeadFunctions.push_back(&Callee); 306 CalleeWasDeleted = true; 307 } 308 } 309 if (CalleeWasDeleted) 310 Advice->recordInliningWithCalleeDeleted(); 311 else 312 Advice->recordInlining(); 313 } 314 315 if (!DidInline) 316 continue; 317 Changed = true; 318 319 InlinedCallees.clear(); 320 } 321 322 // Now that we've finished inlining all of the calls across this module, 323 // delete all of the trivially dead functions. 324 // 325 // Note that this walks a pointer set which has non-deterministic order but 326 // that is OK as all we do is delete things and add pointers to unordered 327 // sets. 328 for (Function *DeadF : DeadFunctions) { 329 // Clear out any cached analyses. 330 FAM.clear(*DeadF, DeadF->getName()); 331 332 // And delete the actual function from the module. 333 M.getFunctionList().erase(DeadF); 334 335 ++NumDeleted; 336 } 337 338 if (!Changed) 339 return PreservedAnalyses::all(); 340 341 return PreservedAnalyses::none(); 342 } 343