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 std::unique_ptr<FunctionSummary> FuncSummary = 99 llvm::make_unique<FunctionSummary>(F.getLinkage(), NumInsts); 100 FuncSummary->addCallGraphEdges(CallGraphEdges); 101 FuncSummary->addRefEdges(RefEdges); 102 std::unique_ptr<GlobalValueInfo> GVInfo = 103 llvm::make_unique<GlobalValueInfo>(0, std::move(FuncSummary)); 104 Index->addGlobalValueInfo(F.getName(), std::move(GVInfo)); 105 } 106 107 void ModuleSummaryIndexBuilder::computeVariableInfo(const GlobalVariable &V) { 108 DenseSet<const Value *> RefEdges; 109 SmallPtrSet<const User *, 8> Visited; 110 findRefEdges(&V, RefEdges, Visited); 111 std::unique_ptr<GlobalVarSummary> GVarSummary = 112 llvm::make_unique<GlobalVarSummary>(V.getLinkage()); 113 GVarSummary->addRefEdges(RefEdges); 114 std::unique_ptr<GlobalValueInfo> GVInfo = 115 llvm::make_unique<GlobalValueInfo>(0, std::move(GVarSummary)); 116 Index->addGlobalValueInfo(V.getName(), std::move(GVInfo)); 117 } 118 119 ModuleSummaryIndexBuilder::ModuleSummaryIndexBuilder( 120 const Module *M, 121 std::function<BlockFrequencyInfo *(const Function &F)> Ftor) 122 : Index(llvm::make_unique<ModuleSummaryIndex>()), M(M) { 123 // We cannot currently promote or rename anything that is in llvm.used, 124 // since any such value may have a use that won't see the new name. 125 // Specifically, any uses within inline assembly are not visible to the 126 // compiler. Prevent importing of any modules containing these uses by 127 // suppressing generation of the index. This also prevents importing 128 // into this module, which is also necessary to avoid needing to rename 129 // in case of a name clash between a local in this module and an imported 130 // global. 131 // FIXME: If we find we need a finer-grained approach of preventing promotion 132 // and renaming of just the functions using inline assembly we will need to: 133 // - Add flag in the function summaries to identify those with inline asm. 134 // - Prevent importing of any functions with flag set. 135 // - Prevent importing of any global function with the same name as a 136 // function in current module that has the flag set. 137 // - For any llvm.used value that is exported and promoted, add a private 138 // alias to the original name in the current module (even if we don't 139 // export the function using those values in inline asm, another function 140 // with a reference could be exported). 141 SmallPtrSet<GlobalValue *, 8> Used; 142 collectUsedGlobalVariables(*M, Used, /*CompilerUsed*/ false); 143 for (GlobalValue *V : Used) { 144 if (V->hasLocalLinkage()) 145 return; 146 } 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 computeFunctionInfo(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 computeVariableInfo(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