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/IR/CallSite.h" 22 #include "llvm/IR/Dominators.h" 23 #include "llvm/IR/InstIterator.h" 24 #include "llvm/IR/IntrinsicInst.h" 25 #include "llvm/IR/ValueSymbolTable.h" 26 #include "llvm/Pass.h" 27 using namespace llvm; 28 29 #define DEBUG_TYPE "module-summary-analysis" 30 31 // Walk through the operands of a given User via worklist iteration and populate 32 // the set of GlobalValue references encountered. Invoked either on an 33 // Instruction or a GlobalVariable (which walks its initializer). 34 static void findRefEdges(const User *CurUser, DenseSet<const Value *> &RefEdges, 35 SmallPtrSet<const User *, 8> &Visited) { 36 SmallVector<const User *, 32> Worklist; 37 Worklist.push_back(CurUser); 38 39 while (!Worklist.empty()) { 40 const User *U = Worklist.pop_back_val(); 41 42 if (!Visited.insert(U).second) 43 continue; 44 45 ImmutableCallSite CS(U); 46 47 for (const auto &OI : U->operands()) { 48 const User *Operand = dyn_cast<User>(OI); 49 if (!Operand) 50 continue; 51 if (isa<BlockAddress>(Operand)) 52 continue; 53 if (isa<GlobalValue>(Operand)) { 54 // We have a reference to a global value. This should be added to 55 // the reference set unless it is a callee. Callees are handled 56 // specially by WriteFunction and are added to a separate list. 57 if (!(CS && CS.isCallee(&OI))) 58 RefEdges.insert(Operand); 59 continue; 60 } 61 Worklist.push_back(Operand); 62 } 63 } 64 } 65 66 void ModuleSummaryIndexBuilder::computeFunctionSummary( 67 const Function &F, BlockFrequencyInfo *BFI) { 68 // Summary not currently supported for anonymous functions, they must 69 // be renamed. 70 if (!F.hasName()) 71 return; 72 73 unsigned NumInsts = 0; 74 // Map from callee ValueId to profile count. Used to accumulate profile 75 // counts for all static calls to a given callee. 76 DenseMap<const Value *, CalleeInfo> CallGraphEdges; 77 DenseMap<GlobalValue::GUID, CalleeInfo> IndirectCallEdges; 78 DenseSet<const Value *> RefEdges; 79 ICallPromotionAnalysis ICallAnalysis; 80 81 SmallPtrSet<const User *, 8> Visited; 82 for (const BasicBlock &BB : F) 83 for (const Instruction &I : BB) { 84 if (!isa<DbgInfoIntrinsic>(I)) 85 ++NumInsts; 86 87 if (auto CS = ImmutableCallSite(&I)) { 88 auto *CalledFunction = CS.getCalledFunction(); 89 // Check if this is a direct call to a known function. 90 if (CalledFunction) { 91 if (CalledFunction->hasName() && !CalledFunction->isIntrinsic()) { 92 auto ScaledCount = BFI ? BFI->getBlockProfileCount(&BB) : None; 93 auto *CalleeId = 94 M->getValueSymbolTable().lookup(CalledFunction->getName()); 95 CallGraphEdges[CalleeId] += 96 (ScaledCount ? ScaledCount.getValue() : 0); 97 } 98 } else { 99 // Otherwise, check for an indirect call (call to a non-const value 100 // that isn't an inline assembly call). 101 const CallInst *CI = dyn_cast<CallInst>(&I); 102 if (CS.getCalledValue() && !isa<Constant>(CS.getCalledValue()) && 103 !(CI && CI->isInlineAsm())) { 104 uint32_t NumVals, NumCandidates; 105 uint64_t TotalCount; 106 auto CandidateProfileData = 107 ICallAnalysis.getPromotionCandidatesForInstruction( 108 &I, NumVals, TotalCount, NumCandidates); 109 for (auto &Candidate : CandidateProfileData) 110 IndirectCallEdges[Candidate.Value] += Candidate.Count; 111 } 112 } 113 } 114 findRefEdges(&I, RefEdges, Visited); 115 } 116 117 GlobalValueSummary::GVFlags Flags(F); 118 std::unique_ptr<FunctionSummary> FuncSummary = 119 llvm::make_unique<FunctionSummary>(Flags, NumInsts); 120 FuncSummary->addCallGraphEdges(CallGraphEdges); 121 FuncSummary->addCallGraphEdges(IndirectCallEdges); 122 FuncSummary->addRefEdges(RefEdges); 123 Index->addGlobalValueSummary(F.getName(), std::move(FuncSummary)); 124 } 125 126 void ModuleSummaryIndexBuilder::computeVariableSummary( 127 const GlobalVariable &V) { 128 DenseSet<const Value *> RefEdges; 129 SmallPtrSet<const User *, 8> Visited; 130 findRefEdges(&V, RefEdges, Visited); 131 GlobalValueSummary::GVFlags Flags(V); 132 std::unique_ptr<GlobalVarSummary> GVarSummary = 133 llvm::make_unique<GlobalVarSummary>(Flags); 134 GVarSummary->addRefEdges(RefEdges); 135 Index->addGlobalValueSummary(V.getName(), std::move(GVarSummary)); 136 } 137 138 ModuleSummaryIndexBuilder::ModuleSummaryIndexBuilder( 139 const Module *M, 140 std::function<BlockFrequencyInfo *(const Function &F)> Ftor) 141 : Index(llvm::make_unique<ModuleSummaryIndex>()), M(M) { 142 // Check if the module can be promoted, otherwise just disable importing from 143 // it by not emitting any summary. 144 // FIXME: we could still import *into* it most of the time. 145 if (!moduleCanBeRenamedForThinLTO(*M)) 146 return; 147 148 // Compute summaries for all functions defined in module, and save in the 149 // index. 150 for (auto &F : *M) { 151 if (F.isDeclaration()) 152 continue; 153 154 BlockFrequencyInfo *BFI = nullptr; 155 std::unique_ptr<BlockFrequencyInfo> BFIPtr; 156 if (Ftor) 157 BFI = Ftor(F); 158 else if (F.getEntryCount().hasValue()) { 159 LoopInfo LI{DominatorTree(const_cast<Function &>(F))}; 160 BranchProbabilityInfo BPI{F, LI}; 161 BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI); 162 BFI = BFIPtr.get(); 163 } 164 165 computeFunctionSummary(F, BFI); 166 } 167 168 // Compute summaries for all variables defined in module, and save in the 169 // index. 170 for (const GlobalVariable &G : M->globals()) { 171 if (G.isDeclaration()) 172 continue; 173 computeVariableSummary(G); 174 } 175 } 176 177 char ModuleSummaryIndexAnalysis::PassID; 178 179 const ModuleSummaryIndex & 180 ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) { 181 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 182 IndexBuilder = llvm::make_unique<ModuleSummaryIndexBuilder>( 183 &M, [&FAM](const Function &F) { 184 return &( 185 FAM.getResult<BlockFrequencyAnalysis>(*const_cast<Function *>(&F))); 186 }); 187 return IndexBuilder->getIndex(); 188 } 189 190 char ModuleSummaryIndexWrapperPass::ID = 0; 191 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 192 "Module Summary Analysis", false, true) 193 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) 194 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 195 "Module Summary Analysis", false, true) 196 197 ModulePass *llvm::createModuleSummaryIndexWrapperPass() { 198 return new ModuleSummaryIndexWrapperPass(); 199 } 200 201 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass() 202 : ModulePass(ID) { 203 initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry()); 204 } 205 206 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) { 207 IndexBuilder = llvm::make_unique<ModuleSummaryIndexBuilder>( 208 &M, [this](const Function &F) { 209 return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>( 210 *const_cast<Function *>(&F)) 211 .getBFI()); 212 }); 213 return false; 214 } 215 216 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) { 217 IndexBuilder.reset(); 218 return false; 219 } 220 221 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 222 AU.setPreservesAll(); 223 AU.addRequired<BlockFrequencyInfoWrapperPass>(); 224 } 225 226 bool llvm::moduleCanBeRenamedForThinLTO(const Module &M) { 227 // We cannot currently promote or rename anything used in inline assembly, 228 // which are not visible to the compiler. Detect a possible case by looking 229 // for a llvm.used local value, in conjunction with an inline assembly call 230 // in the module. Prevent importing of any modules containing these uses by 231 // suppressing generation of the index. This also prevents importing 232 // into this module, which is also necessary to avoid needing to rename 233 // in case of a name clash between a local in this module and an imported 234 // global. 235 // FIXME: If we find we need a finer-grained approach of preventing promotion 236 // and renaming of just the functions using inline assembly we will need to: 237 // - Add flag in the function summaries to identify those with inline asm. 238 // - Prevent importing of any functions with flag set. 239 // - Prevent importing of any global function with the same name as a 240 // function in current module that has the flag set. 241 // - For any llvm.used value that is exported and promoted, add a private 242 // alias to the original name in the current module (even if we don't 243 // export the function using those values in inline asm, another function 244 // with a reference could be exported). 245 SmallPtrSet<GlobalValue *, 8> Used; 246 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false); 247 bool LocalIsUsed = 248 any_of(Used, [](GlobalValue *V) { return V->hasLocalLinkage(); }); 249 if (!LocalIsUsed) 250 return true; 251 252 // Walk all the instructions in the module and find if one is inline ASM 253 auto HasInlineAsm = any_of(M, [](const Function &F) { 254 return any_of(instructions(F), [](const Instruction &I) { 255 const CallInst *CallI = dyn_cast<CallInst>(&I); 256 if (!CallI) 257 return false; 258 return CallI->isInlineAsm(); 259 }); 260 }); 261 return !HasInlineAsm; 262 } 263