Home | History | Annotate | Download | only in Analysis 
      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