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/ADT/MapVector.h"
  17 #include "llvm/ADT/SetVector.h"
  18 #include "llvm/ADT/Triple.h"
  19 #include "llvm/Analysis/BlockFrequencyInfo.h"
  20 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
  21 #include "llvm/Analysis/BranchProbabilityInfo.h"
  22 #include "llvm/Analysis/IndirectCallPromotionAnalysis.h"
  23 #include "llvm/Analysis/LoopInfo.h"
  24 #include "llvm/Analysis/ProfileSummaryInfo.h"
  25 #include "llvm/Analysis/TypeMetadataUtils.h"
  26 #include "llvm/IR/CallSite.h"
  27 #include "llvm/IR/Dominators.h"
  28 #include "llvm/IR/InstIterator.h"
  29 #include "llvm/IR/IntrinsicInst.h"
  30 #include "llvm/IR/ValueSymbolTable.h"
  31 #include "llvm/Object/IRObjectFile.h"
  32 #include "llvm/Pass.h"
  33 using namespace llvm;
  34
  35 #define DEBUG_TYPE "module-summary-analysis"
  36
  37 // Walk through the operands of a given User via worklist iteration and populate
  38 // the set of GlobalValue references encountered. Invoked either on an
  39 // Instruction or a GlobalVariable (which walks its initializer).
  40 static void findRefEdges(const User *CurUser, SetVector<ValueInfo> &RefEdges,
  41                          SmallPtrSet<const User *, 8> &Visited) {
  42   SmallVector<const User *, 32> Worklist;
  43   Worklist.push_back(CurUser);
  44
  45   while (!Worklist.empty()) {
  46     const User *U = Worklist.pop_back_val();
  47
  48     if (!Visited.insert(U).second)
  49       continue;
  50
  51     ImmutableCallSite CS(U);
  52
  53     for (const auto &OI : U->operands()) {
  54       const User *Operand = dyn_cast<User>(OI);
  55       if (!Operand)
  56         continue;
  57       if (isa<BlockAddress>(Operand))
  58         continue;
  59       if (auto *GV = dyn_cast<GlobalValue>(Operand)) {
  60         // We have a reference to a global value. This should be added to
  61         // the reference set unless it is a callee. Callees are handled
  62         // specially by WriteFunction and are added to a separate list.
  63         if (!(CS && CS.isCallee(&OI)))
  64           RefEdges.insert(GV);
  65         continue;
  66       }
  67       Worklist.push_back(Operand);
  68     }
  69   }
  70 }
  71
  72 static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount,
  73                                           ProfileSummaryInfo *PSI) {
  74   if (!PSI)
  75     return CalleeInfo::HotnessType::Unknown;
  76   if (PSI->isHotCount(ProfileCount))
  77     return CalleeInfo::HotnessType::Hot;
  78   if (PSI->isColdCount(ProfileCount))
  79     return CalleeInfo::HotnessType::Cold;
  80   return CalleeInfo::HotnessType::None;
  81 }
  82
  83 static void computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M,
  84                                    const Function &F, BlockFrequencyInfo *BFI,
  85                                    ProfileSummaryInfo *PSI,
  86                                    bool HasLocalsInUsed) {
  87   // Summary not currently supported for anonymous functions, they should
  88   // have been named.
  89   assert(F.hasName());
  90
  91   unsigned NumInsts = 0;
  92   // Map from callee ValueId to profile count. Used to accumulate profile
  93   // counts for all static calls to a given callee.
  94   MapVector<ValueInfo, CalleeInfo> CallGraphEdges;
  95   SetVector<ValueInfo> RefEdges;
  96   SetVector<GlobalValue::GUID> TypeTests;
  97   ICallPromotionAnalysis ICallAnalysis;
  98
  99   bool HasInlineAsmMaybeReferencingInternal = false;
 100   SmallPtrSet<const User *, 8> Visited;
 101   for (const BasicBlock &BB : F)
 102     for (const Instruction &I : BB) {
 103       if (isa<DbgInfoIntrinsic>(I))
 104         continue;
 105       ++NumInsts;
 106       findRefEdges(&I, RefEdges, Visited);
 107       auto CS = ImmutableCallSite(&I);
 108       if (!CS)
 109         continue;
 110
 111       const auto *CI = dyn_cast<CallInst>(&I);
 112       // Since we don't know exactly which local values are referenced in inline
 113       // assembly, conservatively mark the function as possibly referencing
 114       // a local value from inline assembly to ensure we don't export a
 115       // reference (which would require renaming and promotion of the
 116       // referenced value).
 117       if (HasLocalsInUsed && CI && CI->isInlineAsm())
 118         HasInlineAsmMaybeReferencingInternal = true;
 119
 120       auto *CalledValue = CS.getCalledValue();
 121       auto *CalledFunction = CS.getCalledFunction();
 122       // Check if this is an alias to a function. If so, get the
 123       // called aliasee for the checks below.
 124       if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) {
 125         assert(!CalledFunction && "Expected null called function in callsite for alias");
 126         CalledFunction = dyn_cast<Function>(GA->getBaseObject());
 127       }
 128       // Check if this is a direct call to a known function or a known
 129       // intrinsic, or an indirect call with profile data.
 130       if (CalledFunction) {
 131         if (CalledFunction->isIntrinsic()) {
 132           if (CalledFunction->getIntrinsicID() != Intrinsic::type_test)
 133             continue;
 134           // Produce a summary from type.test intrinsics. We only summarize
 135           // type.test intrinsics that are used other than by an llvm.assume
 136           // intrinsic. Intrinsics that are assumed are relevant only to the
 137           // devirtualization pass, not the type test lowering pass.
 138           bool HasNonAssumeUses = llvm::any_of(CI->uses(), [](const Use &CIU) {
 139             auto *AssumeCI = dyn_cast<CallInst>(CIU.getUser());
 140             if (!AssumeCI)
 141               return true;
 142             Function *F = AssumeCI->getCalledFunction();
 143             return !F || F->getIntrinsicID() != Intrinsic::assume;
 144           });
 145           if (HasNonAssumeUses) {
 146             auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(1));
 147             if (auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata()))
 148               TypeTests.insert(GlobalValue::getGUID(TypeId->getString()));
 149           }
 150         }
 151         // We should have named any anonymous globals
 152         assert(CalledFunction->hasName());
 153         auto ScaledCount = BFI ? BFI->getBlockProfileCount(&BB) : None;
 154         auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI)
 155                                    : CalleeInfo::HotnessType::Unknown;
 156
 157         // Use the original CalledValue, in case it was an alias. We want
 158         // to record the call edge to the alias in that case. Eventually
 159         // an alias summary will be created to associate the alias and
 160         // aliasee.
 161         CallGraphEdges[cast<GlobalValue>(CalledValue)].updateHotness(Hotness);
 162       } else {
 163         // Skip inline assembly calls.
 164         if (CI && CI->isInlineAsm())
 165           continue;
 166         // Skip direct calls.
 167         if (!CS.getCalledValue() || isa<Constant>(CS.getCalledValue()))
 168           continue;
 169
 170         uint32_t NumVals, NumCandidates;
 171         uint64_t TotalCount;
 172         auto CandidateProfileData =
 173             ICallAnalysis.getPromotionCandidatesForInstruction(
 174                 &I, NumVals, TotalCount, NumCandidates);
 175         for (auto &Candidate : CandidateProfileData)
 176           CallGraphEdges[Candidate.Value].updateHotness(
 177               getHotness(Candidate.Count, PSI));
 178       }
 179     }
 180
 181   GlobalValueSummary::GVFlags Flags(F);
 182   auto FuncSummary = llvm::make_unique<FunctionSummary>(
 183       Flags, NumInsts, RefEdges.takeVector(), CallGraphEdges.takeVector(),
 184       TypeTests.takeVector());
 185   if (HasInlineAsmMaybeReferencingInternal)
 186     FuncSummary->setHasInlineAsmMaybeReferencingInternal();
 187   Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary));
 188 }
 189
 190 static void computeVariableSummary(ModuleSummaryIndex &Index,
 191                                    const GlobalVariable &V) {
 192   SetVector<ValueInfo> RefEdges;
 193   SmallPtrSet<const User *, 8> Visited;
 194   findRefEdges(&V, RefEdges, Visited);
 195   GlobalValueSummary::GVFlags Flags(V);
 196   auto GVarSummary =
 197       llvm::make_unique<GlobalVarSummary>(Flags, RefEdges.takeVector());
 198   Index.addGlobalValueSummary(V.getName(), std::move(GVarSummary));
 199 }
 200
 201 static void computeAliasSummary(ModuleSummaryIndex &Index,
 202                                 const GlobalAlias &A) {
 203   GlobalValueSummary::GVFlags Flags(A);
 204   auto AS = llvm::make_unique<AliasSummary>(Flags, ArrayRef<ValueInfo>{});
 205   auto *Aliasee = A.getBaseObject();
 206   auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee);
 207   assert(AliaseeSummary && "Alias expects aliasee summary to be parsed");
 208   AS->setAliasee(AliaseeSummary);
 209   Index.addGlobalValueSummary(A.getName(), std::move(AS));
 210 }
 211
 212 ModuleSummaryIndex llvm::buildModuleSummaryIndex(
 213     const Module &M,
 214     std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback,
 215     ProfileSummaryInfo *PSI) {
 216   ModuleSummaryIndex Index;
 217
 218   // Identify the local values in the llvm.used and llvm.compiler.used sets,
 219   // which should not be exported as they would then require renaming and
 220   // promotion, but we may have opaque uses e.g. in inline asm. We collect them
 221   // here because we use this information to mark functions containing inline
 222   // assembly calls as not importable.
 223   SmallPtrSet<GlobalValue *, 8> LocalsUsed;
 224   SmallPtrSet<GlobalValue *, 8> Used;
 225   // First collect those in the llvm.used set.
 226   collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false);
 227   // Next collect those in the llvm.compiler.used set.
 228   collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ true);
 229   for (auto *V : Used) {
 230     if (V->hasLocalLinkage())
 231       LocalsUsed.insert(V);
 232   }
 233
 234   // Compute summaries for all functions defined in module, and save in the
 235   // index.
 236   for (auto &F : M) {
 237     if (F.isDeclaration())
 238       continue;
 239
 240     BlockFrequencyInfo *BFI = nullptr;
 241     std::unique_ptr<BlockFrequencyInfo> BFIPtr;
 242     if (GetBFICallback)
 243       BFI = GetBFICallback(F);
 244     else if (F.getEntryCount().hasValue()) {
 245       LoopInfo LI{DominatorTree(const_cast<Function &>(F))};
 246       BranchProbabilityInfo BPI{F, LI};
 247       BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI);
 248       BFI = BFIPtr.get();
 249     }
 250
 251     computeFunctionSummary(Index, M, F, BFI, PSI, !LocalsUsed.empty());
 252   }
 253
 254   // Compute summaries for all variables defined in module, and save in the
 255   // index.
 256   for (const GlobalVariable &G : M.globals()) {
 257     if (G.isDeclaration())
 258       continue;
 259     computeVariableSummary(Index, G);
 260   }
 261
 262   // Compute summaries for all aliases defined in module, and save in the
 263   // index.
 264   for (const GlobalAlias &A : M.aliases())
 265     computeAliasSummary(Index, A);
 266
 267   for (auto *V : LocalsUsed) {
 268     auto *Summary = Index.getGlobalValueSummary(*V);
 269     assert(Summary && "Missing summary for global value");
 270     Summary->setNoRename();
 271   }
 272
 273   if (!M.getModuleInlineAsm().empty()) {
 274     // Collect the local values defined by module level asm, and set up
 275     // summaries for these symbols so that they can be marked as NoRename,
 276     // to prevent export of any use of them in regular IR that would require
 277     // renaming within the module level asm. Note we don't need to create a
 278     // summary for weak or global defs, as they don't need to be flagged as
 279     // NoRename, and defs in module level asm can't be imported anyway.
 280     // Also, any values used but not defined within module level asm should
 281     // be listed on the llvm.used or llvm.compiler.used global and marked as
 282     // referenced from there.
 283     ModuleSymbolTable::CollectAsmSymbols(
 284         Triple(M.getTargetTriple()), M.getModuleInlineAsm(),
 285         [&M, &Index](StringRef Name, object::BasicSymbolRef::Flags Flags) {
 286           // Symbols not marked as Weak or Global are local definitions.
 287           if (Flags & (object::BasicSymbolRef::SF_Weak |
 288                        object::BasicSymbolRef::SF_Global))
 289             return;
 290           GlobalValue *GV = M.getNamedValue(Name);
 291           if (!GV)
 292             return;
 293           assert(GV->isDeclaration() && "Def in module asm already has definition");
 294           GlobalValueSummary::GVFlags GVFlags(
 295               GlobalValue::InternalLinkage,
 296               /* NoRename */ true,
 297               /* HasInlineAsmMaybeReferencingInternal */ false,
 298               /* IsNotViableToInline */ true);
 299           // Create the appropriate summary type.
 300           if (isa<Function>(GV)) {
 301             std::unique_ptr<FunctionSummary> Summary =
 302                 llvm::make_unique<FunctionSummary>(
 303                     GVFlags, 0, ArrayRef<ValueInfo>{},
 304                     ArrayRef<FunctionSummary::EdgeTy>{},
 305                     ArrayRef<GlobalValue::GUID>{});
 306             Summary->setNoRename();
 307             Index.addGlobalValueSummary(Name, std::move(Summary));
 308           } else {
 309             std::unique_ptr<GlobalVarSummary> Summary =
 310                 llvm::make_unique<GlobalVarSummary>(GVFlags,
 311                                                     ArrayRef<ValueInfo>{});
 312             Summary->setNoRename();
 313             Index.addGlobalValueSummary(Name, std::move(Summary));
 314           }
 315         });
 316   }
 317
 318   return Index;
 319 }
 320
 321 AnalysisKey ModuleSummaryIndexAnalysis::Key;
 322
 323 ModuleSummaryIndex
 324 ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
 325   ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M);
 326   auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
 327   return buildModuleSummaryIndex(
 328       M,
 329       [&FAM](const Function &F) {
 330         return &FAM.getResult<BlockFrequencyAnalysis>(
 331             *const_cast<Function *>(&F));
 332       },
 333       &PSI);
 334 }
 335
 336 char ModuleSummaryIndexWrapperPass::ID = 0;
 337 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
 338                       "Module Summary Analysis", false, true)
 339 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
 340 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
 341                     "Module Summary Analysis", false, true)
 342
 343 ModulePass *llvm::createModuleSummaryIndexWrapperPass() {
 344   return new ModuleSummaryIndexWrapperPass();
 345 }
 346
 347 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass()
 348     : ModulePass(ID) {
 349   initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry());
 350 }
 351
 352 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) {
 353   auto &PSI = *getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
 354   Index = buildModuleSummaryIndex(
 355       M,
 356       [this](const Function &F) {
 357         return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>(
 358                          *const_cast<Function *>(&F))
 359                      .getBFI());
 360       },
 361       &PSI);
 362   return false;
 363 }
 364
 365 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) {
 366   Index.reset();
 367   return false;
 368 }
 369
 370 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 371   AU.setPreservesAll();
 372   AU.addRequired<BlockFrequencyInfoWrapperPass>();
 373   AU.addRequired<ProfileSummaryInfoWrapperPass>();
 374 }