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