contrib/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp

   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       llvm::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 = llvm::any_of(M, [](const Function &F) {
 241     return llvm::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 }