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 // Summary not currently supported for anonymous functions, they should 82 // have been named. 83 assert(F.hasName()); 84 85 unsigned NumInsts = 0; 86 // Map from callee ValueId to profile count. Used to accumulate profile 87 // counts for all static calls to a given callee. 88 DenseMap<const Value *, CalleeInfo> CallGraphEdges; 89 DenseMap<GlobalValue::GUID, CalleeInfo> IndirectCallEdges; 90 DenseSet<const Value *> RefEdges; 91 ICallPromotionAnalysis ICallAnalysis; 92 93 SmallPtrSet<const User *, 8> Visited; 94 for (const BasicBlock &BB : F) 95 for (const Instruction &I : BB) { 96 if (isa<DbgInfoIntrinsic>(I)) 97 continue; 98 ++NumInsts; 99 findRefEdges(&I, RefEdges, Visited); 100 auto CS = ImmutableCallSite(&I); 101 if (!CS) 102 continue; 103 auto *CalledValue = CS.getCalledValue(); 104 auto *CalledFunction = CS.getCalledFunction(); 105 // Check if this is an alias to a function. If so, get the 106 // called aliasee for the checks below. 107 if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) { 108 assert(!CalledFunction && "Expected null called function in callsite for alias"); 109 CalledFunction = dyn_cast<Function>(GA->getBaseObject()); 110 } 111 // Check if this is a direct call to a known function. 112 if (CalledFunction) { 113 // Skip intrinsics. 114 if (CalledFunction->isIntrinsic()) 115 continue; 116 // We should have named any anonymous globals 117 assert(CalledFunction->hasName()); 118 auto ScaledCount = BFI ? BFI->getBlockProfileCount(&BB) : None; 119 // Use the original CalledValue, in case it was an alias. We want 120 // to record the call edge to the alias in that case. Eventually 121 // an alias summary will be created to associate the alias and 122 // aliasee. 123 auto *CalleeId = 124 M.getValueSymbolTable().lookup(CalledValue->getName()); 125 126 auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI) 127 : CalleeInfo::HotnessType::Unknown; 128 CallGraphEdges[CalleeId].updateHotness(Hotness); 129 } else { 130 const auto *CI = dyn_cast<CallInst>(&I); 131 // Skip inline assembly calls. 132 if (CI && CI->isInlineAsm()) 133 continue; 134 // Skip direct calls. 135 if (!CS.getCalledValue() || isa<Constant>(CS.getCalledValue())) 136 continue; 137 138 uint32_t NumVals, NumCandidates; 139 uint64_t TotalCount; 140 auto CandidateProfileData = 141 ICallAnalysis.getPromotionCandidatesForInstruction( 142 &I, NumVals, TotalCount, NumCandidates); 143 for (auto &Candidate : CandidateProfileData) 144 IndirectCallEdges[Candidate.Value].updateHotness( 145 getHotness(Candidate.Count, PSI)); 146 } 147 } 148 149 GlobalValueSummary::GVFlags Flags(F); 150 std::unique_ptr<FunctionSummary> FuncSummary = 151 llvm::make_unique<FunctionSummary>(Flags, NumInsts); 152 FuncSummary->addCallGraphEdges(CallGraphEdges); 153 FuncSummary->addCallGraphEdges(IndirectCallEdges); 154 FuncSummary->addRefEdges(RefEdges); 155 Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary)); 156 } 157 158 static void computeVariableSummary(ModuleSummaryIndex &Index, 159 const GlobalVariable &V) { 160 DenseSet<const Value *> RefEdges; 161 SmallPtrSet<const User *, 8> Visited; 162 findRefEdges(&V, RefEdges, Visited); 163 GlobalValueSummary::GVFlags Flags(V); 164 std::unique_ptr<GlobalVarSummary> GVarSummary = 165 llvm::make_unique<GlobalVarSummary>(Flags); 166 GVarSummary->addRefEdges(RefEdges); 167 Index.addGlobalValueSummary(V.getName(), std::move(GVarSummary)); 168 } 169 170 static void computeAliasSummary(ModuleSummaryIndex &Index, 171 const GlobalAlias &A) { 172 GlobalValueSummary::GVFlags Flags(A); 173 std::unique_ptr<AliasSummary> AS = llvm::make_unique<AliasSummary>(Flags); 174 auto *Aliasee = A.getBaseObject(); 175 auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee); 176 assert(AliaseeSummary && "Alias expects aliasee summary to be parsed"); 177 AS->setAliasee(AliaseeSummary); 178 Index.addGlobalValueSummary(A.getName(), std::move(AS)); 179 } 180 181 ModuleSummaryIndex llvm::buildModuleSummaryIndex( 182 const Module &M, 183 std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback, 184 ProfileSummaryInfo *PSI) { 185 ModuleSummaryIndex Index; 186 // Check if the module can be promoted, otherwise just disable importing from 187 // it by not emitting any summary. 188 // FIXME: we could still import *into* it most of the time. 189 if (!moduleCanBeRenamedForThinLTO(M)) 190 return Index; 191 192 // Compute summaries for all functions defined in module, and save in the 193 // index. 194 for (auto &F : M) { 195 if (F.isDeclaration()) 196 continue; 197 198 BlockFrequencyInfo *BFI = nullptr; 199 std::unique_ptr<BlockFrequencyInfo> BFIPtr; 200 if (GetBFICallback) 201 BFI = GetBFICallback(F); 202 else if (F.getEntryCount().hasValue()) { 203 LoopInfo LI{DominatorTree(const_cast<Function &>(F))}; 204 BranchProbabilityInfo BPI{F, LI}; 205 BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI); 206 BFI = BFIPtr.get(); 207 } 208 209 computeFunctionSummary(Index, M, F, BFI, PSI); 210 } 211 212 // Compute summaries for all variables defined in module, and save in the 213 // index. 214 for (const GlobalVariable &G : M.globals()) { 215 if (G.isDeclaration()) 216 continue; 217 computeVariableSummary(Index, G); 218 } 219 220 // Compute summaries for all aliases defined in module, and save in the 221 // index. 222 for (const GlobalAlias &A : M.aliases()) 223 computeAliasSummary(Index, A); 224 225 return Index; 226 } 227 228 char ModuleSummaryIndexAnalysis::PassID; 229 230 ModuleSummaryIndex 231 ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) { 232 ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M); 233 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 234 return buildModuleSummaryIndex( 235 M, 236 [&FAM](const Function &F) { 237 return &FAM.getResult<BlockFrequencyAnalysis>( 238 *const_cast<Function *>(&F)); 239 }, 240 &PSI); 241 } 242 243 char ModuleSummaryIndexWrapperPass::ID = 0; 244 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 245 "Module Summary Analysis", false, true) 246 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) 247 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 248 "Module Summary Analysis", false, true) 249 250 ModulePass *llvm::createModuleSummaryIndexWrapperPass() { 251 return new ModuleSummaryIndexWrapperPass(); 252 } 253 254 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass() 255 : ModulePass(ID) { 256 initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry()); 257 } 258 259 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) { 260 auto &PSI = *getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); 261 Index = buildModuleSummaryIndex( 262 M, 263 [this](const Function &F) { 264 return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>( 265 *const_cast<Function *>(&F)) 266 .getBFI()); 267 }, 268 &PSI); 269 return false; 270 } 271 272 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) { 273 Index.reset(); 274 return false; 275 } 276 277 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 278 AU.setPreservesAll(); 279 AU.addRequired<BlockFrequencyInfoWrapperPass>(); 280 AU.addRequired<ProfileSummaryInfoWrapperPass>(); 281 } 282 283 bool llvm::moduleCanBeRenamedForThinLTO(const Module &M) { 284 // We cannot currently promote or rename anything used in inline assembly, 285 // which are not visible to the compiler. Detect a possible case by looking 286 // for a llvm.used local value, in conjunction with an inline assembly call 287 // in the module. Prevent importing of any modules containing these uses by 288 // suppressing generation of the index. This also prevents importing 289 // into this module, which is also necessary to avoid needing to rename 290 // in case of a name clash between a local in this module and an imported 291 // global. 292 // FIXME: If we find we need a finer-grained approach of preventing promotion 293 // and renaming of just the functions using inline assembly we will need to: 294 // - Add flag in the function summaries to identify those with inline asm. 295 // - Prevent importing of any functions with flag set. 296 // - Prevent importing of any global function with the same name as a 297 // function in current module that has the flag set. 298 // - For any llvm.used value that is exported and promoted, add a private 299 // alias to the original name in the current module (even if we don't 300 // export the function using those values in inline asm, another function 301 // with a reference could be exported). 302 SmallPtrSet<GlobalValue *, 8> Used; 303 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false); 304 bool LocalIsUsed = 305 any_of(Used, [](GlobalValue *V) { return V->hasLocalLinkage(); }); 306 if (!LocalIsUsed) 307 return true; 308 309 // Walk all the instructions in the module and find if one is inline ASM 310 auto HasInlineAsm = any_of(M, [](const Function &F) { 311 return any_of(instructions(F), [](const Instruction &I) { 312 const CallInst *CallI = dyn_cast<CallInst>(&I); 313 if (!CallI) 314 return false; 315 return CallI->isInlineAsm(); 316 }); 317 }); 318 return !HasInlineAsm; 319 } 320