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 bool isNonRenamableLocal(const GlobalValue &GV) {
  84   return GV.hasSection() && GV.hasLocalLinkage();
  85 }
  86
  87 static void
  88 computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M,
  89                        const Function &F, BlockFrequencyInfo *BFI,
  90                        ProfileSummaryInfo *PSI, bool HasLocalsInUsed,
  91                        DenseSet<GlobalValue::GUID> &CantBePromoted) {
  92   // Summary not currently supported for anonymous functions, they should
  93   // have been named.
  94   assert(F.hasName());
  95
  96   unsigned NumInsts = 0;
  97   // Map from callee ValueId to profile count. Used to accumulate profile
  98   // counts for all static calls to a given callee.
  99   MapVector<ValueInfo, CalleeInfo> CallGraphEdges;
 100   SetVector<ValueInfo> RefEdges;
 101   SetVector<GlobalValue::GUID> TypeTests;
 102   ICallPromotionAnalysis ICallAnalysis;
 103
 104   bool HasInlineAsmMaybeReferencingInternal = false;
 105   SmallPtrSet<const User *, 8> Visited;
 106   for (const BasicBlock &BB : F)
 107     for (const Instruction &I : BB) {
 108       if (isa<DbgInfoIntrinsic>(I))
 109         continue;
 110       ++NumInsts;
 111       findRefEdges(&I, RefEdges, Visited);
 112       auto CS = ImmutableCallSite(&I);
 113       if (!CS)
 114         continue;
 115
 116       const auto *CI = dyn_cast<CallInst>(&I);
 117       // Since we don't know exactly which local values are referenced in inline
 118       // assembly, conservatively mark the function as possibly referencing
 119       // a local value from inline assembly to ensure we don't export a
 120       // reference (which would require renaming and promotion of the
 121       // referenced value).
 122       if (HasLocalsInUsed && CI && CI->isInlineAsm())
 123         HasInlineAsmMaybeReferencingInternal = true;
 124
 125       auto *CalledValue = CS.getCalledValue();
 126       auto *CalledFunction = CS.getCalledFunction();
 127       // Check if this is an alias to a function. If so, get the
 128       // called aliasee for the checks below.
 129       if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) {
 130         assert(!CalledFunction && "Expected null called function in callsite for alias");
 131         CalledFunction = dyn_cast<Function>(GA->getBaseObject());
 132       }
 133       // Check if this is a direct call to a known function or a known
 134       // intrinsic, or an indirect call with profile data.
 135       if (CalledFunction) {
 136         if (CalledFunction->isIntrinsic()) {
 137           if (CalledFunction->getIntrinsicID() != Intrinsic::type_test)
 138             continue;
 139           // Produce a summary from type.test intrinsics. We only summarize
 140           // type.test intrinsics that are used other than by an llvm.assume
 141           // intrinsic. Intrinsics that are assumed are relevant only to the
 142           // devirtualization pass, not the type test lowering pass.
 143           bool HasNonAssumeUses = llvm::any_of(CI->uses(), [](const Use &CIU) {
 144             auto *AssumeCI = dyn_cast<CallInst>(CIU.getUser());
 145             if (!AssumeCI)
 146               return true;
 147             Function *F = AssumeCI->getCalledFunction();
 148             return !F || F->getIntrinsicID() != Intrinsic::assume;
 149           });
 150           if (HasNonAssumeUses) {
 151             auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(1));
 152             if (auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata()))
 153               TypeTests.insert(GlobalValue::getGUID(TypeId->getString()));
 154           }
 155         }
 156         // We should have named any anonymous globals
 157         assert(CalledFunction->hasName());
 158         auto ScaledCount = BFI ? BFI->getBlockProfileCount(&BB) : None;
 159         auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI)
 160                                    : CalleeInfo::HotnessType::Unknown;
 161
 162         // Use the original CalledValue, in case it was an alias. We want
 163         // to record the call edge to the alias in that case. Eventually
 164         // an alias summary will be created to associate the alias and
 165         // aliasee.
 166         CallGraphEdges[cast<GlobalValue>(CalledValue)].updateHotness(Hotness);
 167       } else {
 168         // Skip inline assembly calls.
 169         if (CI && CI->isInlineAsm())
 170           continue;
 171         // Skip direct calls.
 172         if (!CS.getCalledValue() || isa<Constant>(CS.getCalledValue()))
 173           continue;
 174
 175         uint32_t NumVals, NumCandidates;
 176         uint64_t TotalCount;
 177         auto CandidateProfileData =
 178             ICallAnalysis.getPromotionCandidatesForInstruction(
 179                 &I, NumVals, TotalCount, NumCandidates);
 180         for (auto &Candidate : CandidateProfileData)
 181           CallGraphEdges[Candidate.Value].updateHotness(
 182               getHotness(Candidate.Count, PSI));
 183       }
 184     }
 185
 186   bool NonRenamableLocal = isNonRenamableLocal(F);
 187   bool NotEligibleForImport =
 188       NonRenamableLocal || HasInlineAsmMaybeReferencingInternal ||
 189       // Inliner doesn't handle variadic functions.
 190       // FIXME: refactor this to use the same code that inliner is using.
 191       F.isVarArg();
 192   GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport,
 193                                     /* LiveRoot = */ false);
 194   auto FuncSummary = llvm::make_unique<FunctionSummary>(
 195       Flags, NumInsts, RefEdges.takeVector(), CallGraphEdges.takeVector(),
 196       TypeTests.takeVector());
 197   if (NonRenamableLocal)
 198     CantBePromoted.insert(F.getGUID());
 199   Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary));
 200 }
 201
 202 static void
 203 computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V,
 204                        DenseSet<GlobalValue::GUID> &CantBePromoted) {
 205   SetVector<ValueInfo> RefEdges;
 206   SmallPtrSet<const User *, 8> Visited;
 207   findRefEdges(&V, RefEdges, Visited);
 208   bool NonRenamableLocal = isNonRenamableLocal(V);
 209   GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal,
 210                                     /* LiveRoot = */ false);
 211   auto GVarSummary =
 212       llvm::make_unique<GlobalVarSummary>(Flags, RefEdges.takeVector());
 213   if (NonRenamableLocal)
 214     CantBePromoted.insert(V.getGUID());
 215   Index.addGlobalValueSummary(V.getName(), std::move(GVarSummary));
 216 }
 217
 218 static void
 219 computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A,
 220                     DenseSet<GlobalValue::GUID> &CantBePromoted) {
 221   bool NonRenamableLocal = isNonRenamableLocal(A);
 222   GlobalValueSummary::GVFlags Flags(A.getLinkage(), NonRenamableLocal,
 223                                     /* LiveRoot = */ false);
 224   auto AS = llvm::make_unique<AliasSummary>(Flags, ArrayRef<ValueInfo>{});
 225   auto *Aliasee = A.getBaseObject();
 226   auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee);
 227   assert(AliaseeSummary && "Alias expects aliasee summary to be parsed");
 228   AS->setAliasee(AliaseeSummary);
 229   if (NonRenamableLocal)
 230     CantBePromoted.insert(A.getGUID());
 231   Index.addGlobalValueSummary(A.getName(), std::move(AS));
 232 }
 233
 234 // Set LiveRoot flag on entries matching the given value name.
 235 static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) {
 236   auto SummaryList =
 237       Index.findGlobalValueSummaryList(GlobalValue::getGUID(Name));
 238   if (SummaryList == Index.end())
 239     return;
 240   for (auto &Summary : SummaryList->second)
 241     Summary->setLiveRoot();
 242 }
 243
 244 ModuleSummaryIndex llvm::buildModuleSummaryIndex(
 245     const Module &M,
 246     std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback,
 247     ProfileSummaryInfo *PSI) {
 248   ModuleSummaryIndex Index;
 249
 250   // Identify the local values in the llvm.used and llvm.compiler.used sets,
 251   // which should not be exported as they would then require renaming and
 252   // promotion, but we may have opaque uses e.g. in inline asm. We collect them
 253   // here because we use this information to mark functions containing inline
 254   // assembly calls as not importable.
 255   SmallPtrSet<GlobalValue *, 8> LocalsUsed;
 256   SmallPtrSet<GlobalValue *, 8> Used;
 257   // First collect those in the llvm.used set.
 258   collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false);
 259   // Next collect those in the llvm.compiler.used set.
 260   collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ true);
 261   DenseSet<GlobalValue::GUID> CantBePromoted;
 262   for (auto *V : Used) {
 263     if (V->hasLocalLinkage()) {
 264       LocalsUsed.insert(V);
 265       CantBePromoted.insert(V->getGUID());
 266     }
 267   }
 268
 269   // Compute summaries for all functions defined in module, and save in the
 270   // index.
 271   for (auto &F : M) {
 272     if (F.isDeclaration())
 273       continue;
 274
 275     BlockFrequencyInfo *BFI = nullptr;
 276     std::unique_ptr<BlockFrequencyInfo> BFIPtr;
 277     if (GetBFICallback)
 278       BFI = GetBFICallback(F);
 279     else if (F.getEntryCount().hasValue()) {
 280       LoopInfo LI{DominatorTree(const_cast<Function &>(F))};
 281       BranchProbabilityInfo BPI{F, LI};
 282       BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI);
 283       BFI = BFIPtr.get();
 284     }
 285
 286     computeFunctionSummary(Index, M, F, BFI, PSI, !LocalsUsed.empty(),
 287                            CantBePromoted);
 288   }
 289
 290   // Compute summaries for all variables defined in module, and save in the
 291   // index.
 292   for (const GlobalVariable &G : M.globals()) {
 293     if (G.isDeclaration())
 294       continue;
 295     computeVariableSummary(Index, G, CantBePromoted);
 296   }
 297
 298   // Compute summaries for all aliases defined in module, and save in the
 299   // index.
 300   for (const GlobalAlias &A : M.aliases())
 301     computeAliasSummary(Index, A, CantBePromoted);
 302
 303   for (auto *V : LocalsUsed) {
 304     auto *Summary = Index.getGlobalValueSummary(*V);
 305     assert(Summary && "Missing summary for global value");
 306     Summary->setNotEligibleToImport();
 307   }
 308
 309   // The linker doesn't know about these LLVM produced values, so we need
 310   // to flag them as live in the index to ensure index-based dead value
 311   // analysis treats them as live roots of the analysis.
 312   setLiveRoot(Index, "llvm.used");
 313   setLiveRoot(Index, "llvm.compiler.used");
 314   setLiveRoot(Index, "llvm.global_ctors");
 315   setLiveRoot(Index, "llvm.global_dtors");
 316   setLiveRoot(Index, "llvm.global.annotations");
 317
 318   if (!M.getModuleInlineAsm().empty()) {
 319     // Collect the local values defined by module level asm, and set up
 320     // summaries for these symbols so that they can be marked as NoRename,
 321     // to prevent export of any use of them in regular IR that would require
 322     // renaming within the module level asm. Note we don't need to create a
 323     // summary for weak or global defs, as they don't need to be flagged as
 324     // NoRename, and defs in module level asm can't be imported anyway.
 325     // Also, any values used but not defined within module level asm should
 326     // be listed on the llvm.used or llvm.compiler.used global and marked as
 327     // referenced from there.
 328     ModuleSymbolTable::CollectAsmSymbols(
 329         Triple(M.getTargetTriple()), M.getModuleInlineAsm(),
 330         [&M, &Index, &CantBePromoted](StringRef Name,
 331                                       object::BasicSymbolRef::Flags Flags) {
 332           // Symbols not marked as Weak or Global are local definitions.
 333           if (Flags & (object::BasicSymbolRef::SF_Weak |
 334                        object::BasicSymbolRef::SF_Global))
 335             return;
 336           GlobalValue *GV = M.getNamedValue(Name);
 337           if (!GV)
 338             return;
 339           assert(GV->isDeclaration() && "Def in module asm already has definition");
 340           GlobalValueSummary::GVFlags GVFlags(GlobalValue::InternalLinkage,
 341                                               /* NotEligibleToImport */ true,
 342                                               /* LiveRoot */ true);
 343           CantBePromoted.insert(GlobalValue::getGUID(Name));
 344           // Create the appropriate summary type.
 345           if (isa<Function>(GV)) {
 346             std::unique_ptr<FunctionSummary> Summary =
 347                 llvm::make_unique<FunctionSummary>(
 348                     GVFlags, 0, ArrayRef<ValueInfo>{},
 349                     ArrayRef<FunctionSummary::EdgeTy>{},
 350                     ArrayRef<GlobalValue::GUID>{});
 351             Index.addGlobalValueSummary(Name, std::move(Summary));
 352           } else {
 353             std::unique_ptr<GlobalVarSummary> Summary =
 354                 llvm::make_unique<GlobalVarSummary>(GVFlags,
 355                                                     ArrayRef<ValueInfo>{});
 356             Index.addGlobalValueSummary(Name, std::move(Summary));
 357           }
 358         });
 359   }
 360
 361   for (auto &GlobalList : Index) {
 362     assert(GlobalList.second.size() == 1 &&
 363            "Expected module's index to have one summary per GUID");
 364     auto &Summary = GlobalList.second[0];
 365     bool AllRefsCanBeExternallyReferenced =
 366         llvm::all_of(Summary->refs(), [&](const ValueInfo &VI) {
 367           return !CantBePromoted.count(VI.getValue()->getGUID());
 368         });
 369     if (!AllRefsCanBeExternallyReferenced) {
 370       Summary->setNotEligibleToImport();
 371       continue;
 372     }
 373
 374     if (auto *FuncSummary = dyn_cast<FunctionSummary>(Summary.get())) {
 375       bool AllCallsCanBeExternallyReferenced = llvm::all_of(
 376           FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) {
 377             auto GUID = Edge.first.isGUID() ? Edge.first.getGUID()
 378                                             : Edge.first.getValue()->getGUID();
 379             return !CantBePromoted.count(GUID);
 380           });
 381       if (!AllCallsCanBeExternallyReferenced)
 382         Summary->setNotEligibleToImport();
 383     }
 384   }
 385
 386   return Index;
 387 }
 388
 389 AnalysisKey ModuleSummaryIndexAnalysis::Key;
 390
 391 ModuleSummaryIndex
 392 ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
 393   ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M);
 394   auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
 395   return buildModuleSummaryIndex(
 396       M,
 397       [&FAM](const Function &F) {
 398         return &FAM.getResult<BlockFrequencyAnalysis>(
 399             *const_cast<Function *>(&F));
 400       },
 401       &PSI);
 402 }
 403
 404 char ModuleSummaryIndexWrapperPass::ID = 0;
 405 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
 406                       "Module Summary Analysis", false, true)
 407 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
 408 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
 409 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
 410                     "Module Summary Analysis", false, true)
 411
 412 ModulePass *llvm::createModuleSummaryIndexWrapperPass() {
 413   return new ModuleSummaryIndexWrapperPass();
 414 }
 415
 416 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass()
 417     : ModulePass(ID) {
 418   initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry());
 419 }
 420
 421 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) {
 422   auto &PSI = *getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
 423   Index = buildModuleSummaryIndex(
 424       M,
 425       [this](const Function &F) {
 426         return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>(
 427                          *const_cast<Function *>(&F))
 428                      .getBFI());
 429       },
 430       &PSI);
 431   return false;
 432 }
 433
 434 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) {
 435   Index.reset();
 436   return false;
 437 }
 438
 439 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 440   AU.setPreservesAll();
 441   AU.addRequired<BlockFrequencyInfoWrapperPass>();
 442   AU.addRequired<ProfileSummaryInfoWrapperPass>();
 443 }