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/LoopInfo.h" 20 #include "llvm/IR/CallSite.h" 21 #include "llvm/IR/Dominators.h" 22 #include "llvm/IR/IntrinsicInst.h" 23 #include "llvm/IR/ValueSymbolTable.h" 24 #include "llvm/Pass.h" 25 using namespace llvm; 26 27 #define DEBUG_TYPE "module-summary-analysis" 28 29 // Walk through the operands of a given User via worklist iteration and populate 30 // the set of GlobalValue references encountered. Invoked either on an 31 // Instruction or a GlobalVariable (which walks its initializer). 32 static void findRefEdges(const User *CurUser, DenseSet<const Value *> &RefEdges, 33 SmallPtrSet<const User *, 8> &Visited) { 34 SmallVector<const User *, 32> Worklist; 35 Worklist.push_back(CurUser); 36 37 while (!Worklist.empty()) { 38 const User *U = Worklist.pop_back_val(); 39 40 if (!Visited.insert(U).second) 41 continue; 42 43 ImmutableCallSite CS(U); 44 45 for (const auto &OI : U->operands()) { 46 const User *Operand = dyn_cast<User>(OI); 47 if (!Operand) 48 continue; 49 if (isa<BlockAddress>(Operand)) 50 continue; 51 if (isa<GlobalValue>(Operand)) { 52 // We have a reference to a global value. This should be added to 53 // the reference set unless it is a callee. Callees are handled 54 // specially by WriteFunction and are added to a separate list. 55 if (!(CS && CS.isCallee(&OI))) 56 RefEdges.insert(Operand); 57 continue; 58 } 59 Worklist.push_back(Operand); 60 } 61 } 62 } 63 64 void ModuleSummaryIndexBuilder::computeFunctionInfo(const Function &F, 65 BlockFrequencyInfo *BFI) { 66 // Summary not currently supported for anonymous functions, they must 67 // be renamed. 68 if (!F.hasName()) 69 return; 70 71 unsigned NumInsts = 0; 72 // Map from callee ValueId to profile count. Used to accumulate profile 73 // counts for all static calls to a given callee. 74 DenseMap<const Value *, CalleeInfo> CallGraphEdges; 75 DenseSet<const Value *> RefEdges; 76 77 SmallPtrSet<const User *, 8> Visited; 78 for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 79 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; 80 ++I) { 81 if (!isa<DbgInfoIntrinsic>(I)) 82 ++NumInsts; 83 84 if (auto CS = ImmutableCallSite(&*I)) { 85 auto *CalledFunction = CS.getCalledFunction(); 86 if (CalledFunction && CalledFunction->hasName() && 87 !CalledFunction->isIntrinsic()) { 88 auto ScaledCount = BFI ? BFI->getBlockProfileCount(&*BB) : None; 89 auto *CalleeId = 90 M->getValueSymbolTable().lookup(CalledFunction->getName()); 91 CallGraphEdges[CalleeId] += 92 (ScaledCount ? ScaledCount.getValue() : 0); 93 } 94 } 95 findRefEdges(&*I, RefEdges, Visited); 96 } 97 98 GlobalValueSummary::GVFlags Flags(F); 99 std::unique_ptr<FunctionSummary> FuncSummary = 100 llvm::make_unique<FunctionSummary>(Flags, NumInsts); 101 FuncSummary->addCallGraphEdges(CallGraphEdges); 102 FuncSummary->addRefEdges(RefEdges); 103 std::unique_ptr<GlobalValueInfo> GVInfo = 104 llvm::make_unique<GlobalValueInfo>(0, std::move(FuncSummary)); 105 Index->addGlobalValueInfo(F.getName(), std::move(GVInfo)); 106 } 107 108 void ModuleSummaryIndexBuilder::computeVariableInfo(const GlobalVariable &V) { 109 DenseSet<const Value *> RefEdges; 110 SmallPtrSet<const User *, 8> Visited; 111 findRefEdges(&V, RefEdges, Visited); 112 GlobalValueSummary::GVFlags Flags(V); 113 std::unique_ptr<GlobalVarSummary> GVarSummary = 114 llvm::make_unique<GlobalVarSummary>(Flags); 115 GVarSummary->addRefEdges(RefEdges); 116 std::unique_ptr<GlobalValueInfo> GVInfo = 117 llvm::make_unique<GlobalValueInfo>(0, std::move(GVarSummary)); 118 Index->addGlobalValueInfo(V.getName(), std::move(GVInfo)); 119 } 120 121 ModuleSummaryIndexBuilder::ModuleSummaryIndexBuilder( 122 const Module *M, 123 std::function<BlockFrequencyInfo *(const Function &F)> Ftor) 124 : Index(llvm::make_unique<ModuleSummaryIndex>()), M(M) { 125 // We cannot currently promote or rename anything that is in llvm.used, 126 // since any such value may have a use that won't see the new name. 127 // Specifically, any uses within inline assembly are not visible to the 128 // compiler. Prevent importing of any modules containing these uses by 129 // suppressing generation of the index. This also prevents importing 130 // into this module, which is also necessary to avoid needing to rename 131 // in case of a name clash between a local in this module and an imported 132 // global. 133 // FIXME: If we find we need a finer-grained approach of preventing promotion 134 // and renaming of just the functions using inline assembly we will need to: 135 // - Add flag in the function summaries to identify those with inline asm. 136 // - Prevent importing of any functions with flag set. 137 // - Prevent importing of any global function with the same name as a 138 // function in current module that has the flag set. 139 // - For any llvm.used value that is exported and promoted, add a private 140 // alias to the original name in the current module (even if we don't 141 // export the function using those values in inline asm, another function 142 // with a reference could be exported). 143 SmallPtrSet<GlobalValue *, 8> Used; 144 collectUsedGlobalVariables(*M, Used, /*CompilerUsed*/ false); 145 for (GlobalValue *V : Used) { 146 if (V->hasLocalLinkage()) 147 return; 148 } 149 150 // Compute summaries for all functions defined in module, and save in the 151 // index. 152 for (auto &F : *M) { 153 if (F.isDeclaration()) 154 continue; 155 156 BlockFrequencyInfo *BFI = nullptr; 157 std::unique_ptr<BlockFrequencyInfo> BFIPtr; 158 if (Ftor) 159 BFI = Ftor(F); 160 else if (F.getEntryCount().hasValue()) { 161 LoopInfo LI{DominatorTree(const_cast<Function &>(F))}; 162 BranchProbabilityInfo BPI{F, LI}; 163 BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI); 164 BFI = BFIPtr.get(); 165 } 166 167 computeFunctionInfo(F, BFI); 168 } 169 170 // Compute summaries for all variables defined in module, and save in the 171 // index. 172 for (const GlobalVariable &G : M->globals()) { 173 if (G.isDeclaration()) 174 continue; 175 computeVariableInfo(G); 176 } 177 } 178 179 char ModuleSummaryIndexWrapperPass::ID = 0; 180 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 181 "Module Summary Analysis", false, true) 182 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) 183 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 184 "Module Summary Analysis", false, true) 185 186 ModulePass *llvm::createModuleSummaryIndexWrapperPass() { 187 return new ModuleSummaryIndexWrapperPass(); 188 } 189 190 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass() 191 : ModulePass(ID) { 192 initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry()); 193 } 194 195 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) { 196 IndexBuilder = llvm::make_unique<ModuleSummaryIndexBuilder>( 197 &M, [this](const Function &F) { 198 return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>( 199 *const_cast<Function *>(&F)) 200 .getBFI()); 201 }); 202 return false; 203 } 204 205 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) { 206 IndexBuilder.reset(); 207 return false; 208 } 209 210 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 211 AU.setPreservesAll(); 212 AU.addRequired<BlockFrequencyInfoWrapperPass>(); 213 } 214