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
diff --git a/llvm/lib/ExecutionEngine/Orc/CMakeLists.txt b/llvm/lib/ExecutionEngine/Orc/CMakeLists.txt
index 2c1a772..94d84b6 100644
--- a/llvm/lib/ExecutionEngine/Orc/CMakeLists.txt
+++ b/llvm/lib/ExecutionEngine/Orc/CMakeLists.txt
@@ -21,7 +21,8 @@
RPCUtils.cpp
RTDyldObjectLinkingLayer.cpp
ThreadSafeModule.cpp
-
+ Speculation.cpp
+ SpeculateAnalyses.cpp
ADDITIONAL_HEADER_DIRS
${LLVM_MAIN_INCLUDE_DIR}/llvm/ExecutionEngine/Orc
@@ -31,6 +32,7 @@
target_link_libraries(LLVMOrcJIT
PRIVATE
+ LLVMAnalysis
LLVMBitReader
LLVMBitWriter
)
diff --git a/llvm/lib/ExecutionEngine/Orc/CompileOnDemandLayer.cpp b/llvm/lib/ExecutionEngine/Orc/CompileOnDemandLayer.cpp
index efb98e0..a91dd4e 100644
--- a/llvm/lib/ExecutionEngine/Orc/CompileOnDemandLayer.cpp
+++ b/llvm/lib/ExecutionEngine/Orc/CompileOnDemandLayer.cpp
@@ -118,6 +118,9 @@
this->Partition = std::move(Partition);
}
+void CompileOnDemandLayer::setImplMap(ImplSymbolMap *Imp) {
+ this->AliaseeImpls = Imp;
+}
void CompileOnDemandLayer::emit(MaterializationResponsibility R,
ThreadSafeModule TSM) {
assert(TSM && "Null module");
@@ -161,7 +164,7 @@
R.replace(reexports(PDR.getImplDylib(), std::move(NonCallables), true));
R.replace(lazyReexports(LCTMgr, PDR.getISManager(), PDR.getImplDylib(),
- std::move(Callables)));
+ std::move(Callables), AliaseeImpls));
}
CompileOnDemandLayer::PerDylibResources &
diff --git a/llvm/lib/ExecutionEngine/Orc/LazyReexports.cpp b/llvm/lib/ExecutionEngine/Orc/LazyReexports.cpp
index fc82058..11ba2e5 100644
--- a/llvm/lib/ExecutionEngine/Orc/LazyReexports.cpp
+++ b/llvm/lib/ExecutionEngine/Orc/LazyReexports.cpp
@@ -50,7 +50,6 @@
SourceJD = I->second.first;
SymbolName = I->second.second;
}
-
auto LookupResult =
ES.lookup(JITDylibSearchList({{SourceJD, true}}), SymbolName);
@@ -121,7 +120,8 @@
LazyReexportsMaterializationUnit::LazyReexportsMaterializationUnit(
LazyCallThroughManager &LCTManager, IndirectStubsManager &ISManager,
- JITDylib &SourceJD, SymbolAliasMap CallableAliases, VModuleKey K)
+ JITDylib &SourceJD, SymbolAliasMap CallableAliases, ImplSymbolMap *SrcJDLoc,
+ VModuleKey K)
: MaterializationUnit(extractFlags(CallableAliases), std::move(K)),
LCTManager(LCTManager), ISManager(ISManager), SourceJD(SourceJD),
CallableAliases(std::move(CallableAliases)),
@@ -129,7 +129,8 @@
[&ISManager](JITDylib &JD, const SymbolStringPtr &SymbolName,
JITTargetAddress ResolvedAddr) {
return ISManager.updatePointer(*SymbolName, ResolvedAddr);
- })) {}
+ })),
+ AliaseeTable(SrcJDLoc) {}
StringRef LazyReexportsMaterializationUnit::getName() const {
return "<Lazy Reexports>";
@@ -149,7 +150,7 @@
if (!CallableAliases.empty())
R.replace(lazyReexports(LCTManager, ISManager, SourceJD,
- std::move(CallableAliases)));
+ std::move(CallableAliases), AliaseeTable));
IndirectStubsManager::StubInitsMap StubInits;
for (auto &Alias : RequestedAliases) {
@@ -168,6 +169,9 @@
std::make_pair(*CallThroughTrampoline, Alias.second.AliasFlags);
}
+ if (AliaseeTable != nullptr && !RequestedAliases.empty())
+ AliaseeTable->trackImpls(RequestedAliases, &SourceJD);
+
if (auto Err = ISManager.createStubs(StubInits)) {
SourceJD.getExecutionSession().reportError(std::move(Err));
R.failMaterialization();
diff --git a/llvm/lib/ExecutionEngine/Orc/SpeculateAnalyses.cpp b/llvm/lib/ExecutionEngine/Orc/SpeculateAnalyses.cpp
new file mode 100644
index 0000000..9d8c2f3
--- /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
diff --git a/llvm/lib/ExecutionEngine/Orc/Speculation.cpp b/llvm/lib/ExecutionEngine/Orc/Speculation.cpp
new file mode 100644
index 0000000..5ab5831
--- /dev/null
+++ b/llvm/lib/ExecutionEngine/Orc/Speculation.cpp
@@ -0,0 +1,97 @@
+//===---------- speculation.cpp - Utilities for Speculation ----------===//
+//
+// 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/Speculation.h"
+
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/Verifier.h"
+
+#include <vector>
+
+namespace llvm {
+
+namespace orc {
+
+// ImplSymbolMap methods
+void ImplSymbolMap::trackImpls(SymbolAliasMap ImplMaps, JITDylib *SrcJD) {
+ assert(SrcJD && "Tracking on Null Source .impl dylib");
+ std::lock_guard<std::mutex> Lockit(ConcurrentAccess);
+ for (auto &I : ImplMaps) {
+ auto It = Maps.insert({I.first, {I.second.Aliasee, SrcJD}});
+ // check rationale when independent dylibs have same symbol name?
+ assert(It.second && "ImplSymbols are already tracked for this Symbol?");
+ (void)(It);
+ }
+}
+
+// If two modules, share the same LLVMContext, different threads must
+// not access those modules concurrently, doing so leave the
+// LLVMContext in in-consistent state.
+// But here since each TSM has a unique Context associated with it,
+// on locking is necessary!
+void IRSpeculationLayer::emit(MaterializationResponsibility R,
+ ThreadSafeModule TSM) {
+
+ assert(TSM && "Speculation Layer received Null Module ?");
+ assert(TSM.getContext().getContext() != nullptr &&
+ "Module with null LLVMContext?");
+
+ // Instrumentation of runtime calls
+ auto &InContext = *TSM.getContext().getContext();
+ auto SpeculatorVTy = StructType::create(InContext, "Class.Speculator");
+ auto RuntimeCallTy = FunctionType::get(
+ Type::getVoidTy(InContext),
+ {SpeculatorVTy->getPointerTo(), Type::getInt64Ty(InContext)}, false);
+ auto RuntimeCall =
+ Function::Create(RuntimeCallTy, Function::LinkageTypes::ExternalLinkage,
+ "__orc_speculate_for", TSM.getModuleUnlocked());
+ auto SpeclAddr = new GlobalVariable(
+ *TSM.getModuleUnlocked(), SpeculatorVTy, false,
+ GlobalValue::LinkageTypes::ExternalLinkage, nullptr, "__orc_speculator");
+
+ IRBuilder<> Mutator(InContext);
+
+ // QueryAnalysis allowed to transform the IR source, one such example is
+ // Simplify CFG helps the static branch prediction heuristics!
+ for (auto &Fn : TSM.getModuleUnlocked()->getFunctionList()) {
+ if (!Fn.isDeclaration()) {
+ auto IRNames = QueryAnalysis(Fn, FAM);
+ // Instrument and register if Query has result
+ if (IRNames.hasValue()) {
+ Mutator.SetInsertPoint(&(Fn.getEntryBlock().front()));
+ auto ImplAddrToUint =
+ Mutator.CreatePtrToInt(&Fn, Type::getInt64Ty(InContext));
+ Mutator.CreateCall(RuntimeCallTy, RuntimeCall,
+ {SpeclAddr, ImplAddrToUint});
+ S.registerSymbols(internToJITSymbols(IRNames.getValue()),
+ &R.getTargetJITDylib());
+ }
+ }
+ }
+ // No locking needed read only operation.
+ assert(!(verifyModule(*TSM.getModuleUnlocked())) &&
+ "Speculation Instrumentation breaks IR?");
+
+ NextLayer.emit(std::move(R), std::move(TSM));
+}
+
+// Runtime Function Implementation
+extern "C" void __orc_speculate_for(Speculator *Ptr, uint64_t StubId) {
+ assert(Ptr && " Null Address Received in orc_speculate_for ");
+ Ptr->speculateFor(StubId);
+}
+
+} // namespace orc
+} // namespace llvm