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