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