Speculative Compilation

[ORC] Remove Speculator Variants for Different Program Representations

[ORC] Block Freq Analysis

Speculative Compilation with Naive Block Frequency

Add Applications to OrcSpeculation

ORC v2 with Block Freq Query & Example

Deleted BenchMark Programs

Signed-off-by: preejackie <praveenvelliengiri@gmail.com>

ORCv2 comments resolved

[ORCV2] NFC

ORCv2 NFC

[ORCv2] Speculative compilation - CFGWalkQuery

ORCv2 Adapting IRSpeculationLayer to new locking scheme

llvm-svn: 367756

1 files changed, 87 insertions, 0 deletions

diff --git a/llvm/lib/ExecutionEngine/Orc/SpeculateAnalyses.cpp b/llvm/lib/ExecutionEngine/Orc/SpeculateAnalyses.cpp
new file mode 100644
index 00000000000..9d8c2f331de
--- /dev/null
+++ b/llvm/lib/ExecutionEngine/Orc/SpeculateAnalyses.cpp
@@ -0,0 +1,87 @@
+//===-- SpeculateAnalyses.cpp  --*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ExecutionEngine/Orc/SpeculateAnalyses.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+
+// Implementations of Queries shouldn't need to lock the resources
+// such as LLVMContext, each argument (function) has a non-shared LLVMContext
+namespace llvm {
+namespace orc {
+
+// Collect direct calls only
+void BlockFreqQuery::findCalles(const BasicBlock *BB,
+                                DenseSet<StringRef> &CallesNames) {
+  assert(BB != nullptr && "Traversing Null BB to find calls?");
+
+  auto getCalledFunction = [&CallesNames](const CallBase *Call) {
+    auto CalledValue = Call->getCalledOperand()->stripPointerCasts();
+    if (auto DirectCall = dyn_cast<Function>(CalledValue))
+      CallesNames.insert(DirectCall->getName());
+  };
+  for (auto &I : BB->instructionsWithoutDebug())
+    if (auto CI = dyn_cast<CallInst>(&I))
+      getCalledFunction(CI);
+
+  if (auto II = dyn_cast<InvokeInst>(BB->getTerminator()))
+    getCalledFunction(II);
+}
+
+// blind calculation
+size_t BlockFreqQuery::numBBToGet(size_t numBB) {
+  // small CFG
+  if (numBB < 4)
+    return numBB;
+  // mid-size CFG
+  else if (numBB < 20)
+    return (numBB / 2);
+  else
+    return (numBB / 2) + (numBB / 4);
+}
+
+BlockFreqQuery::ResultTy BlockFreqQuery::
+operator()(Function &F, FunctionAnalysisManager &FAM) {
+  DenseMap<StringRef, DenseSet<StringRef>> CallerAndCalles;
+  DenseSet<StringRef> Calles;
+  SmallVector<std::pair<const BasicBlock *, uint64_t>, 8> BBFreqs;
+
+  auto IBBs = findBBwithCalls(F);
+
+  if (IBBs.empty())
+    return None;
+
+  auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
+
+  for (const auto I : IBBs)
+    BBFreqs.push_back({I, BFI.getBlockFreq(I).getFrequency()});
+
+  assert(IBBs.size() == BBFreqs.size() && "BB Count Mismatch");
+
+  llvm::sort(BBFreqs.begin(), BBFreqs.end(),
+             [](decltype(BBFreqs)::const_reference BBF,
+                decltype(BBFreqs)::const_reference BBS) {
+               return BBF.second > BBS.second ? true : false;
+             });
+
+  // ignoring number of direct calls in a BB
+  auto Topk = numBBToGet(BBFreqs.size());
+
+  for (size_t i = 0; i < Topk; i++)
+    findCalles(BBFreqs[i].first, Calles);
+
+  assert(!Calles.empty() && "Running Analysis on Function with no calls?");
+
+  CallerAndCalles.insert({F.getName(), std::move(Calles)});
+
+  return CallerAndCalles;
+}
+} // namespace orc
+} // namespace llvm