1 files changed, 249 insertions, 0 deletions
diff --git a/contrib/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp b/contrib/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp
new file mode 100644
index 0000000..c9ac2bd
--- /dev/null
+++ b/contrib/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp
@@ -0,0 +1,249 @@
+//===- ModuleSummaryAnalysis.cpp - Module summary index builder -----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass builds a ModuleSummaryIndex object for the module, to be written
+// to bitcode or LLVM assembly.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/ModuleSummaryAnalysis.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/Analysis/IndirectCallPromotionAnalysis.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/ValueSymbolTable.h"
+#include "llvm/Pass.h"
+using namespace llvm;
+
+#define DEBUG_TYPE "module-summary-analysis"
+
+// Walk through the operands of a given User via worklist iteration and populate
+// the set of GlobalValue references encountered. Invoked either on an
+// Instruction or a GlobalVariable (which walks its initializer).
+static void findRefEdges(const User *CurUser, DenseSet<const Value *> &RefEdges,
+                         SmallPtrSet<const User *, 8> &Visited) {
+  SmallVector<const User *, 32> Worklist;
+  Worklist.push_back(CurUser);
+
+  while (!Worklist.empty()) {
+    const User *U = Worklist.pop_back_val();
+
+    if (!Visited.insert(U).second)
+      continue;
+
+    ImmutableCallSite CS(U);
+
+    for (const auto &OI : U->operands()) {
+      const User *Operand = dyn_cast<User>(OI);
+      if (!Operand)
+        continue;
+      if (isa<BlockAddress>(Operand))
+        continue;
+      if (isa<GlobalValue>(Operand)) {
+        // We have a reference to a global value. This should be added to
+        // the reference set unless it is a callee. Callees are handled
+        // specially by WriteFunction and are added to a separate list.
+        if (!(CS && CS.isCallee(&OI)))
+          RefEdges.insert(Operand);
+        continue;
+      }
+      Worklist.push_back(Operand);
+    }
+  }
+}
+
+void ModuleSummaryIndexBuilder::computeFunctionSummary(
+    const Function &F, BlockFrequencyInfo *BFI) {
+  // Summary not currently supported for anonymous functions, they must
+  // be renamed.
+  if (!F.hasName())
+    return;
+
+  unsigned NumInsts = 0;
+  // Map from callee ValueId to profile count. Used to accumulate profile
+  // counts for all static calls to a given callee.
+  DenseMap<const Value *, CalleeInfo> CallGraphEdges;
+  DenseMap<GlobalValue::GUID, CalleeInfo> IndirectCallEdges;
+  DenseSet<const Value *> RefEdges;
+  ICallPromotionAnalysis ICallAnalysis;
+
+  SmallPtrSet<const User *, 8> Visited;
+  for (const BasicBlock &BB : F)
+    for (const Instruction &I : BB) {
+      if (!isa<DbgInfoIntrinsic>(I))
+        ++NumInsts;
+
+      if (auto CS = ImmutableCallSite(&I)) {
+        auto *CalledFunction = CS.getCalledFunction();
+        // Check if this is a direct call to a known function.
+        if (CalledFunction) {
+          if (CalledFunction->hasName() && !CalledFunction->isIntrinsic()) {
+            auto ScaledCount = BFI ? BFI->getBlockProfileCount(&BB) : None;
+            auto *CalleeId =
+                M->getValueSymbolTable().lookup(CalledFunction->getName());
+            CallGraphEdges[CalleeId] +=
+                (ScaledCount ? ScaledCount.getValue() : 0);
+          }
+        } else {
+          // Otherwise, check for an indirect call (call to a non-const value
+          // that isn't an inline assembly call).
+          const CallInst *CI = dyn_cast<CallInst>(&I);
+          if (CS.getCalledValue() && !isa<Constant>(CS.getCalledValue()) &&
+              !(CI && CI->isInlineAsm())) {
+            uint32_t NumVals, NumCandidates;
+            uint64_t TotalCount;
+            auto CandidateProfileData =
+                ICallAnalysis.getPromotionCandidatesForInstruction(
+                    &I, NumVals, TotalCount, NumCandidates);
+            for (auto &Candidate : CandidateProfileData)
+              IndirectCallEdges[Candidate.Value] += Candidate.Count;
+          }
+        }
+      }
+      findRefEdges(&I, RefEdges, Visited);
+    }
+
+  GlobalValueSummary::GVFlags Flags(F);
+  std::unique_ptr<FunctionSummary> FuncSummary =
+      llvm::make_unique<FunctionSummary>(Flags, NumInsts);
+  FuncSummary->addCallGraphEdges(CallGraphEdges);
+  FuncSummary->addCallGraphEdges(IndirectCallEdges);
+  FuncSummary->addRefEdges(RefEdges);
+  Index->addGlobalValueSummary(F.getName(), std::move(FuncSummary));
+}
+
+void ModuleSummaryIndexBuilder::computeVariableSummary(
+    const GlobalVariable &V) {
+  DenseSet<const Value *> RefEdges;
+  SmallPtrSet<const User *, 8> Visited;
+  findRefEdges(&V, RefEdges, Visited);
+  GlobalValueSummary::GVFlags Flags(V);
+  std::unique_ptr<GlobalVarSummary> GVarSummary =
+      llvm::make_unique<GlobalVarSummary>(Flags);
+  GVarSummary->addRefEdges(RefEdges);
+  Index->addGlobalValueSummary(V.getName(), std::move(GVarSummary));
+}
+
+ModuleSummaryIndexBuilder::ModuleSummaryIndexBuilder(
+    const Module *M,
+    std::function<BlockFrequencyInfo *(const Function &F)> Ftor)
+    : Index(llvm::make_unique<ModuleSummaryIndex>()), M(M) {
+  // Check if the module can be promoted, otherwise just disable importing from
+  // it by not emitting any summary.
+  // FIXME: we could still import *into* it most of the time.
+  if (!moduleCanBeRenamedForThinLTO(*M))
+    return;
+
+  // Compute summaries for all functions defined in module, and save in the
+  // index.
+  for (auto &F : *M) {
+    if (F.isDeclaration())
+      continue;
+
+    BlockFrequencyInfo *BFI = nullptr;
+    std::unique_ptr<BlockFrequencyInfo> BFIPtr;
+    if (Ftor)
+      BFI = Ftor(F);
+    else if (F.getEntryCount().hasValue()) {
+      LoopInfo LI{DominatorTree(const_cast<Function &>(F))};
+      BranchProbabilityInfo BPI{F, LI};
+      BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI);
+      BFI = BFIPtr.get();
+    }
+
+    computeFunctionSummary(F, BFI);
+  }
+
+  // Compute summaries for all variables defined in module, and save in the
+  // index.
+  for (const GlobalVariable &G : M->globals()) {
+    if (G.isDeclaration())
+      continue;
+    computeVariableSummary(G);
+  }
+}
+
+char ModuleSummaryIndexWrapperPass::ID = 0;
+INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
+                      "Module Summary Analysis", false, true)
+INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
+INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
+                    "Module Summary Analysis", false, true)
+
+ModulePass *llvm::createModuleSummaryIndexWrapperPass() {
+  return new ModuleSummaryIndexWrapperPass();
+}
+
+ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass()
+    : ModulePass(ID) {
+  initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry());
+}
+
+bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) {
+  IndexBuilder = llvm::make_unique<ModuleSummaryIndexBuilder>(
+      &M, [this](const Function &F) {
+        return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>(
+                         *const_cast<Function *>(&F))
+                     .getBFI());
+      });
+  return false;
+}
+
+bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) {
+  IndexBuilder.reset();
+  return false;
+}
+
+void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+  AU.addRequired<BlockFrequencyInfoWrapperPass>();
+}
+
+bool llvm::moduleCanBeRenamedForThinLTO(const Module &M) {
+  // We cannot currently promote or rename anything used in inline assembly,
+  // which are not visible to the compiler. Detect a possible case by looking
+  // for a llvm.used local value, in conjunction with an inline assembly call
+  // in the module. Prevent importing of any modules containing these uses by
+  // suppressing generation of the index. This also prevents importing
+  // into this module, which is also necessary to avoid needing to rename
+  // in case of a name clash between a local in this module and an imported
+  // global.
+  // FIXME: If we find we need a finer-grained approach of preventing promotion
+  // and renaming of just the functions using inline assembly we will need to:
+  // - Add flag in the function summaries to identify those with inline asm.
+  // - Prevent importing of any functions with flag set.
+  // - Prevent importing of any global function with the same name as a
+  //   function in current module that has the flag set.
+  // - For any llvm.used value that is exported and promoted, add a private
+  //   alias to the original name in the current module (even if we don't
+  //   export the function using those values in inline asm, another function
+  //   with a reference could be exported).
+  SmallPtrSet<GlobalValue *, 8> Used;
+  collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false);
+  bool LocalIsUsed =
+      llvm::any_of(Used, [](GlobalValue *V) { return V->hasLocalLinkage(); });
+  if (!LocalIsUsed)
+    return true;
+
+  // Walk all the instructions in the module and find if one is inline ASM
+  auto HasInlineAsm = llvm::any_of(M, [](const Function &F) {
+    return llvm::any_of(instructions(F), [](const Instruction &I) {
+      const CallInst *CallI = dyn_cast<CallInst>(&I);
+      if (!CallI)
+        return false;
+      return CallI->isInlineAsm();
+    });
+  });
+  return !HasInlineAsm;
+}