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 // Compute summaries for all functions defined in module, and save in the 124 // index. 125 for (auto &F : *M) { 126 if (F.isDeclaration()) 127 continue; 128 129 BlockFrequencyInfo *BFI = nullptr; 130 std::unique_ptr<BlockFrequencyInfo> BFIPtr; 131 if (Ftor) 132 BFI = Ftor(F); 133 else if (F.getEntryCount().hasValue()) { 134 LoopInfo LI{DominatorTree(const_cast<Function &>(F))}; 135 BranchProbabilityInfo BPI{F, LI}; 136 BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI); 137 BFI = BFIPtr.get(); 138 } 139 140 computeFunctionInfo(F, BFI); 141 } 142 143 // Compute summaries for all variables defined in module, and save in the 144 // index. 145 for (const GlobalVariable &G : M->globals()) { 146 if (G.isDeclaration()) 147 continue; 148 computeVariableInfo(G); 149 } 150 } 151 152 char ModuleSummaryIndexWrapperPass::ID = 0; 153 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 154 "Module Summary Analysis", false, true) 155 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) 156 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 157 "Module Summary Analysis", false, true) 158 159 ModulePass *llvm::createModuleSummaryIndexWrapperPass() { 160 return new ModuleSummaryIndexWrapperPass(); 161 } 162 163 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass() 164 : ModulePass(ID) { 165 initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry()); 166 } 167 168 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) { 169 IndexBuilder = llvm::make_unique<ModuleSummaryIndexBuilder>( 170 &M, [this](const Function &F) { 171 return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>( 172 *const_cast<Function *>(&F)) 173 .getBFI()); 174 }); 175 return false; 176 } 177 178 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) { 179 IndexBuilder.reset(); 180 return false; 181 } 182 183 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 184 AU.setPreservesAll(); 185 AU.addRequired<BlockFrequencyInfoWrapperPass>(); 186 } 187