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 ModuleSummaryIndexWrapperPass::ID = 0; 178 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 179 "Module Summary Analysis", false, true) 180 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) 181 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 182 "Module Summary Analysis", false, true) 183 184 ModulePass *llvm::createModuleSummaryIndexWrapperPass() { 185 return new ModuleSummaryIndexWrapperPass(); 186 } 187 188 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass() 189 : ModulePass(ID) { 190 initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry()); 191 } 192 193 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) { 194 IndexBuilder = llvm::make_unique<ModuleSummaryIndexBuilder>( 195 &M, [this](const Function &F) { 196 return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>( 197 *const_cast<Function *>(&F)) 198 .getBFI()); 199 }); 200 return false; 201 } 202 203 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) { 204 IndexBuilder.reset(); 205 return false; 206 } 207 208 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 209 AU.setPreservesAll(); 210 AU.addRequired<BlockFrequencyInfoWrapperPass>(); 211 } 212 213 bool llvm::moduleCanBeRenamedForThinLTO(const Module &M) { 214 // We cannot currently promote or rename anything used in inline assembly, 215 // which are not visible to the compiler. Detect a possible case by looking 216 // for a llvm.used local value, in conjunction with an inline assembly call 217 // in the module. Prevent importing of any modules containing these uses by 218 // suppressing generation of the index. This also prevents importing 219 // into this module, which is also necessary to avoid needing to rename 220 // in case of a name clash between a local in this module and an imported 221 // global. 222 // FIXME: If we find we need a finer-grained approach of preventing promotion 223 // and renaming of just the functions using inline assembly we will need to: 224 // - Add flag in the function summaries to identify those with inline asm. 225 // - Prevent importing of any functions with flag set. 226 // - Prevent importing of any global function with the same name as a 227 // function in current module that has the flag set. 228 // - For any llvm.used value that is exported and promoted, add a private 229 // alias to the original name in the current module (even if we don't 230 // export the function using those values in inline asm, another function 231 // with a reference could be exported). 232 SmallPtrSet<GlobalValue *, 8> Used; 233 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false); 234 bool LocalIsUsed = 235 any_of(Used, [](GlobalValue *V) { return V->hasLocalLinkage(); }); 236 if (!LocalIsUsed) 237 return true; 238 239 // Walk all the instructions in the module and find if one is inline ASM 240 auto HasInlineAsm = any_of(M, [](const Function &F) { 241 return any_of(instructions(F), [](const Instruction &I) { 242 const CallInst *CallI = dyn_cast<CallInst>(&I); 243 if (!CallI) 244 return false; 245 return CallI->isInlineAsm(); 246 }); 247 }); 248 return !HasInlineAsm; 249 } 250