1 //===- ModuleSummaryAnalysis.cpp - Module summary index builder -----------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This pass builds a ModuleSummaryIndex object for the module, to be written 11 // to bitcode or LLVM assembly. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/Analysis/ModuleSummaryAnalysis.h" 16 #include "llvm/ADT/Triple.h" 17 #include "llvm/Analysis/BlockFrequencyInfo.h" 18 #include "llvm/Analysis/BlockFrequencyInfoImpl.h" 19 #include "llvm/Analysis/BranchProbabilityInfo.h" 20 #include "llvm/Analysis/IndirectCallPromotionAnalysis.h" 21 #include "llvm/Analysis/LoopInfo.h" 22 #include "llvm/Analysis/ProfileSummaryInfo.h" 23 #include "llvm/IR/CallSite.h" 24 #include "llvm/IR/Dominators.h" 25 #include "llvm/IR/InstIterator.h" 26 #include "llvm/IR/IntrinsicInst.h" 27 #include "llvm/IR/ValueSymbolTable.h" 28 #include "llvm/Object/IRObjectFile.h" 29 #include "llvm/Pass.h" 30 using namespace llvm; 31 32 #define DEBUG_TYPE "module-summary-analysis" 33 34 // Walk through the operands of a given User via worklist iteration and populate 35 // the set of GlobalValue references encountered. Invoked either on an 36 // Instruction or a GlobalVariable (which walks its initializer). 37 static void findRefEdges(const User *CurUser, DenseSet<const Value *> &RefEdges, 38 SmallPtrSet<const User *, 8> &Visited) { 39 SmallVector<const User *, 32> Worklist; 40 Worklist.push_back(CurUser); 41 42 while (!Worklist.empty()) { 43 const User *U = Worklist.pop_back_val(); 44 45 if (!Visited.insert(U).second) 46 continue; 47 48 ImmutableCallSite CS(U); 49 50 for (const auto &OI : U->operands()) { 51 const User *Operand = dyn_cast<User>(OI); 52 if (!Operand) 53 continue; 54 if (isa<BlockAddress>(Operand)) 55 continue; 56 if (isa<GlobalValue>(Operand)) { 57 // We have a reference to a global value. This should be added to 58 // the reference set unless it is a callee. Callees are handled 59 // specially by WriteFunction and are added to a separate list. 60 if (!(CS && CS.isCallee(&OI))) 61 RefEdges.insert(Operand); 62 continue; 63 } 64 Worklist.push_back(Operand); 65 } 66 } 67 } 68 69 static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount, 70 ProfileSummaryInfo *PSI) { 71 if (!PSI) 72 return CalleeInfo::HotnessType::Unknown; 73 if (PSI->isHotCount(ProfileCount)) 74 return CalleeInfo::HotnessType::Hot; 75 if (PSI->isColdCount(ProfileCount)) 76 return CalleeInfo::HotnessType::Cold; 77 return CalleeInfo::HotnessType::None; 78 } 79 80 static void computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M, 81 const Function &F, BlockFrequencyInfo *BFI, 82 ProfileSummaryInfo *PSI, 83 bool HasLocalsInUsed) { 84 // Summary not currently supported for anonymous functions, they should 85 // have been named. 86 assert(F.hasName()); 87 88 unsigned NumInsts = 0; 89 // Map from callee ValueId to profile count. Used to accumulate profile 90 // counts for all static calls to a given callee. 91 DenseMap<const Value *, CalleeInfo> CallGraphEdges; 92 DenseMap<GlobalValue::GUID, CalleeInfo> IndirectCallEdges; 93 DenseSet<const Value *> RefEdges; 94 ICallPromotionAnalysis ICallAnalysis; 95 96 bool HasInlineAsmMaybeReferencingInternal = false; 97 SmallPtrSet<const User *, 8> Visited; 98 for (const BasicBlock &BB : F) 99 for (const Instruction &I : BB) { 100 if (isa<DbgInfoIntrinsic>(I)) 101 continue; 102 ++NumInsts; 103 findRefEdges(&I, RefEdges, Visited); 104 auto CS = ImmutableCallSite(&I); 105 if (!CS) 106 continue; 107 108 const auto *CI = dyn_cast<CallInst>(&I); 109 // Since we don't know exactly which local values are referenced in inline 110 // assembly, conservatively mark the function as possibly referencing 111 // a local value from inline assembly to ensure we don't export a 112 // reference (which would require renaming and promotion of the 113 // referenced value). 114 if (HasLocalsInUsed && CI && CI->isInlineAsm()) 115 HasInlineAsmMaybeReferencingInternal = true; 116 117 auto *CalledValue = CS.getCalledValue(); 118 auto *CalledFunction = CS.getCalledFunction(); 119 // Check if this is an alias to a function. If so, get the 120 // called aliasee for the checks below. 121 if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) { 122 assert(!CalledFunction && "Expected null called function in callsite for alias"); 123 CalledFunction = dyn_cast<Function>(GA->getBaseObject()); 124 } 125 // Check if this is a direct call to a known function. 126 if (CalledFunction) { 127 // Skip intrinsics. 128 if (CalledFunction->isIntrinsic()) 129 continue; 130 // We should have named any anonymous globals 131 assert(CalledFunction->hasName()); 132 auto ScaledCount = BFI ? BFI->getBlockProfileCount(&BB) : None; 133 // Use the original CalledValue, in case it was an alias. We want 134 // to record the call edge to the alias in that case. Eventually 135 // an alias summary will be created to associate the alias and 136 // aliasee. 137 auto *CalleeId = 138 M.getValueSymbolTable().lookup(CalledValue->getName()); 139 140 auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI) 141 : CalleeInfo::HotnessType::Unknown; 142 CallGraphEdges[CalleeId].updateHotness(Hotness); 143 } else { 144 // Skip inline assembly calls. 145 if (CI && CI->isInlineAsm()) 146 continue; 147 // Skip direct calls. 148 if (!CS.getCalledValue() || isa<Constant>(CS.getCalledValue())) 149 continue; 150 151 uint32_t NumVals, NumCandidates; 152 uint64_t TotalCount; 153 auto CandidateProfileData = 154 ICallAnalysis.getPromotionCandidatesForInstruction( 155 &I, NumVals, TotalCount, NumCandidates); 156 for (auto &Candidate : CandidateProfileData) 157 IndirectCallEdges[Candidate.Value].updateHotness( 158 getHotness(Candidate.Count, PSI)); 159 } 160 } 161 162 GlobalValueSummary::GVFlags Flags(F); 163 std::unique_ptr<FunctionSummary> FuncSummary = 164 llvm::make_unique<FunctionSummary>(Flags, NumInsts); 165 FuncSummary->addCallGraphEdges(CallGraphEdges); 166 FuncSummary->addCallGraphEdges(IndirectCallEdges); 167 FuncSummary->addRefEdges(RefEdges); 168 if (HasInlineAsmMaybeReferencingInternal) 169 FuncSummary->setHasInlineAsmMaybeReferencingInternal(); 170 Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary)); 171 } 172 173 static void computeVariableSummary(ModuleSummaryIndex &Index, 174 const GlobalVariable &V) { 175 DenseSet<const Value *> RefEdges; 176 SmallPtrSet<const User *, 8> Visited; 177 findRefEdges(&V, RefEdges, Visited); 178 GlobalValueSummary::GVFlags Flags(V); 179 std::unique_ptr<GlobalVarSummary> GVarSummary = 180 llvm::make_unique<GlobalVarSummary>(Flags); 181 GVarSummary->addRefEdges(RefEdges); 182 Index.addGlobalValueSummary(V.getName(), std::move(GVarSummary)); 183 } 184 185 static void computeAliasSummary(ModuleSummaryIndex &Index, 186 const GlobalAlias &A) { 187 GlobalValueSummary::GVFlags Flags(A); 188 std::unique_ptr<AliasSummary> AS = llvm::make_unique<AliasSummary>(Flags); 189 auto *Aliasee = A.getBaseObject(); 190 auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee); 191 assert(AliaseeSummary && "Alias expects aliasee summary to be parsed"); 192 AS->setAliasee(AliaseeSummary); 193 Index.addGlobalValueSummary(A.getName(), std::move(AS)); 194 } 195 196 ModuleSummaryIndex llvm::buildModuleSummaryIndex( 197 const Module &M, 198 std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback, 199 ProfileSummaryInfo *PSI) { 200 ModuleSummaryIndex Index; 201 202 // Identify the local values in the llvm.used and llvm.compiler.used sets, 203 // which should not be exported as they would then require renaming and 204 // promotion, but we may have opaque uses e.g. in inline asm. We collect them 205 // here because we use this information to mark functions containing inline 206 // assembly calls as not importable. 207 SmallPtrSet<GlobalValue *, 8> LocalsUsed; 208 SmallPtrSet<GlobalValue *, 8> Used; 209 // First collect those in the llvm.used set. 210 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false); 211 // Next collect those in the llvm.compiler.used set. 212 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ true); 213 for (auto *V : Used) { 214 if (V->hasLocalLinkage()) 215 LocalsUsed.insert(V); 216 } 217 218 // Compute summaries for all functions defined in module, and save in the 219 // index. 220 for (auto &F : M) { 221 if (F.isDeclaration()) 222 continue; 223 224 BlockFrequencyInfo *BFI = nullptr; 225 std::unique_ptr<BlockFrequencyInfo> BFIPtr; 226 if (GetBFICallback) 227 BFI = GetBFICallback(F); 228 else if (F.getEntryCount().hasValue()) { 229 LoopInfo LI{DominatorTree(const_cast<Function &>(F))}; 230 BranchProbabilityInfo BPI{F, LI}; 231 BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI); 232 BFI = BFIPtr.get(); 233 } 234 235 computeFunctionSummary(Index, M, F, BFI, PSI, !LocalsUsed.empty()); 236 } 237 238 // Compute summaries for all variables defined in module, and save in the 239 // index. 240 for (const GlobalVariable &G : M.globals()) { 241 if (G.isDeclaration()) 242 continue; 243 computeVariableSummary(Index, G); 244 } 245 246 // Compute summaries for all aliases defined in module, and save in the 247 // index. 248 for (const GlobalAlias &A : M.aliases()) 249 computeAliasSummary(Index, A); 250 251 for (auto *V : LocalsUsed) { 252 auto *Summary = Index.getGlobalValueSummary(*V); 253 assert(Summary && "Missing summary for global value"); 254 Summary->setNoRename(); 255 } 256 257 if (!M.getModuleInlineAsm().empty()) { 258 // Collect the local values defined by module level asm, and set up 259 // summaries for these symbols so that they can be marked as NoRename, 260 // to prevent export of any use of them in regular IR that would require 261 // renaming within the module level asm. Note we don't need to create a 262 // summary for weak or global defs, as they don't need to be flagged as 263 // NoRename, and defs in module level asm can't be imported anyway. 264 // Also, any values used but not defined within module level asm should 265 // be listed on the llvm.used or llvm.compiler.used global and marked as 266 // referenced from there. 267 ModuleSymbolTable::CollectAsmSymbols( 268 Triple(M.getTargetTriple()), M.getModuleInlineAsm(), 269 [&M, &Index](StringRef Name, object::BasicSymbolRef::Flags Flags) { 270 // Symbols not marked as Weak or Global are local definitions. 271 if (Flags & (object::BasicSymbolRef::SF_Weak || 272 object::BasicSymbolRef::SF_Global)) 273 return; 274 GlobalValue *GV = M.getNamedValue(Name); 275 if (!GV) 276 return; 277 assert(GV->isDeclaration() && "Def in module asm already has definition"); 278 GlobalValueSummary::GVFlags GVFlags( 279 GlobalValue::InternalLinkage, 280 /* NoRename */ true, 281 /* HasInlineAsmMaybeReferencingInternal */ false, 282 /* IsNotViableToInline */ true); 283 // Create the appropriate summary type. 284 if (isa<Function>(GV)) { 285 std::unique_ptr<FunctionSummary> Summary = 286 llvm::make_unique<FunctionSummary>(GVFlags, 0); 287 Summary->setNoRename(); 288 Index.addGlobalValueSummary(Name, std::move(Summary)); 289 } else { 290 std::unique_ptr<GlobalVarSummary> Summary = 291 llvm::make_unique<GlobalVarSummary>(GVFlags); 292 Summary->setNoRename(); 293 Index.addGlobalValueSummary(Name, std::move(Summary)); 294 } 295 }); 296 } 297 298 return Index; 299 } 300 301 AnalysisKey ModuleSummaryIndexAnalysis::Key; 302 303 ModuleSummaryIndex 304 ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) { 305 ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M); 306 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 307 return buildModuleSummaryIndex( 308 M, 309 [&FAM](const Function &F) { 310 return &FAM.getResult<BlockFrequencyAnalysis>( 311 *const_cast<Function *>(&F)); 312 }, 313 &PSI); 314 } 315 316 char ModuleSummaryIndexWrapperPass::ID = 0; 317 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 318 "Module Summary Analysis", false, true) 319 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) 320 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 321 "Module Summary Analysis", false, true) 322 323 ModulePass *llvm::createModuleSummaryIndexWrapperPass() { 324 return new ModuleSummaryIndexWrapperPass(); 325 } 326 327 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass() 328 : ModulePass(ID) { 329 initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry()); 330 } 331 332 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) { 333 auto &PSI = *getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); 334 Index = buildModuleSummaryIndex( 335 M, 336 [this](const Function &F) { 337 return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>( 338 *const_cast<Function *>(&F)) 339 .getBFI()); 340 }, 341 &PSI); 342 return false; 343 } 344 345 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) { 346 Index.reset(); 347 return false; 348 } 349 350 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 351 AU.setPreservesAll(); 352 AU.addRequired<BlockFrequencyInfoWrapperPass>(); 353 AU.addRequired<ProfileSummaryInfoWrapperPass>(); 354 } 355