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