From 3b1b56d3fb9e7141d8d9cc331f2b3bcfa2039b20 Mon Sep 17 00:00:00 2001 From: Praveen Velliengiri Date: Tue, 27 Aug 2019 18:23:36 +0000 Subject: [ORCv2] - New Speculate Query Implementation Summary: This patch introduces, SequenceBBQuery - new heuristic to find likely next callable functions it tries to find the blocks with calls in order of execution sequence of Blocks. It still uses BlockFrequencyAnalysis to find high frequency blocks. For a handful of hottest blocks (plan to customize), the algorithm traverse and discovered the caller blocks along the way to Entry Basic Block and Exit Basic Block. It uses Block Hint, to stop traversing the already visited blocks in both direction. It implicitly assumes that once the block is visited during discovering entry or exit nodes, revisiting them again does not add much. It also branch probability info (cached result) to traverse only hot edges (planned to customize) from hot blocks. Without BPI, the algorithm mostly return's all the blocks in the CFG with calls. It also changes the heuristic queries, so they don't maintain states. Hence it is safe to call from multiple threads. It also implements, new instrumentation to avoid jumping into JIT on every call to the function with the help _orc_speculate.decision.block and _orc_speculate.block. "Speculator Registration Mechanism is also changed" - kudos to @lhames Open to review, mostly looking to change implementation of SequeceBBQuery heuristics with good data structure choices. Reviewers: lhames, dblaikie Reviewed By: lhames Subscribers: mgorny, hiraditya, mgrang, llvm-commits, lhames Tags: #speculative_compilation_in_orc, #llvm Differential Revision: https://reviews.llvm.org/D66399 llvm-svn: 370092 --- llvm/lib/ExecutionEngine/Orc/SpeculateAnalyses.cpp | 222 +++++++++++++++++++-- 1 file changed, 209 insertions(+), 13 deletions(-) (limited to 'llvm/lib/ExecutionEngine/Orc/SpeculateAnalyses.cpp') diff --git a/llvm/lib/ExecutionEngine/Orc/SpeculateAnalyses.cpp b/llvm/lib/ExecutionEngine/Orc/SpeculateAnalyses.cpp index 52e9919f57c..f22acf50419 100644 --- a/llvm/lib/ExecutionEngine/Orc/SpeculateAnalyses.cpp +++ b/llvm/lib/ExecutionEngine/Orc/SpeculateAnalyses.cpp @@ -7,24 +7,30 @@ //===----------------------------------------------------------------------===// #include "llvm/ExecutionEngine/Orc/SpeculateAnalyses.h" +#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/BlockFrequencyInfo.h" +#include "llvm/Analysis/BranchProbabilityInfo.h" +#include "llvm/Analysis/CFG.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Passes/PassBuilder.h" +#include "llvm/Support/ErrorHandling.h" + +#include namespace { using namespace llvm; -std::vector findBBwithCalls(const Function &F, - bool IndirectCall = false) { - std::vector BBs; +SmallVector findBBwithCalls(const Function &F, + bool IndirectCall = false) { + SmallVector BBs; auto findCallInst = [&IndirectCall](const Instruction &I) { - if (auto Call = dyn_cast(&I)) { - if (Call->isIndirectCall()) - return IndirectCall; - else - return true; - } else + if (auto Call = dyn_cast(&I)) + return Call->isIndirectCall() ? IndirectCall : true; + else return false; }; for (auto &BB : F) @@ -38,11 +44,12 @@ std::vector findBBwithCalls(const Function &F, // Implementations of Queries shouldn't need to lock the resources // such as LLVMContext, each argument (function) has a non-shared LLVMContext +// Plus, if Queries contain states necessary locking scheme should be provided. namespace llvm { namespace orc { // Collect direct calls only -void BlockFreqQuery::findCalles(const BasicBlock *BB, +void SpeculateQuery::findCalles(const BasicBlock *BB, DenseSet &CallesNames) { assert(BB != nullptr && "Traversing Null BB to find calls?"); @@ -59,7 +66,14 @@ void BlockFreqQuery::findCalles(const BasicBlock *BB, getCalledFunction(II); } -// blind calculation +bool SpeculateQuery::isStraightLine(const Function &F) { + return llvm::all_of(F.getBasicBlockList(), [](const BasicBlock &BB) { + return BB.getSingleSuccessor() != nullptr; + }); +} + +// BlockFreqQuery Implementations + size_t BlockFreqQuery::numBBToGet(size_t numBB) { // small CFG if (numBB < 4) @@ -71,12 +85,15 @@ size_t BlockFreqQuery::numBBToGet(size_t numBB) { return (numBB / 2) + (numBB / 4); } -BlockFreqQuery::ResultTy BlockFreqQuery:: -operator()(Function &F, FunctionAnalysisManager &FAM) { +BlockFreqQuery::ResultTy BlockFreqQuery::operator()(Function &F) { DenseMap> CallerAndCalles; DenseSet Calles; SmallVector, 8> BBFreqs; + PassBuilder PB; + FunctionAnalysisManager FAM; + PB.registerFunctionAnalyses(FAM); + auto IBBs = findBBwithCalls(F); if (IBBs.empty()) @@ -107,5 +124,184 @@ operator()(Function &F, FunctionAnalysisManager &FAM) { return CallerAndCalles; } + +// SequenceBBQuery Implementation +std::size_t SequenceBBQuery::getHottestBlocks(std::size_t TotalBlocks) { + if (TotalBlocks == 1) + return TotalBlocks; + return TotalBlocks / 2; +} + +// FIXME : find good implementation. +SequenceBBQuery::BlockListTy +SequenceBBQuery::rearrangeBB(const Function &F, const BlockListTy &BBList) { + BlockListTy RearrangedBBSet; + + for (auto &Block : F.getBasicBlockList()) + if (llvm::is_contained(BBList, &Block)) + RearrangedBBSet.push_back(&Block); + + assert(RearrangedBBSet.size() == BBList.size() && + "BasicBlock missing while rearranging?"); + return RearrangedBBSet; +} + +void SequenceBBQuery::traverseToEntryBlock(const BasicBlock *AtBB, + const BlockListTy &CallerBlocks, + const BackEdgesInfoTy &BackEdgesInfo, + const BranchProbabilityInfo *BPI, + VisitedBlocksInfoTy &VisitedBlocks) { + auto Itr = VisitedBlocks.find(AtBB); + if (Itr != VisitedBlocks.end()) { // already visited. + if (!Itr->second.Upward) + return; + Itr->second.Upward = false; + } else { + // Create hint for newly discoverd blocks. + WalkDirection BlockHint; + BlockHint.Upward = false; + // FIXME: Expensive Check + if (llvm::is_contained(CallerBlocks, AtBB)) + BlockHint.CallerBlock = true; + VisitedBlocks.insert(std::make_pair(AtBB, BlockHint)); + } + + const_pred_iterator PIt = pred_begin(AtBB), EIt = pred_end(AtBB); + // Move this check to top, when we have code setup to launch speculative + // compiles for function in entry BB, this triggers the speculative compiles + // before running the program. + if (PIt == EIt) // No Preds. + return; + + DenseSet PredSkipNodes; + + // Since we are checking for predecessor's backedges, this Block + // occurs in second position. + for (auto &I : BackEdgesInfo) + if (I.second == AtBB) + PredSkipNodes.insert(I.first); + + // Skip predecessors which source of back-edges. + for (; PIt != EIt; ++PIt) + // checking EdgeHotness is cheaper + if (BPI->isEdgeHot(*PIt, AtBB) && !PredSkipNodes.count(*PIt)) + traverseToEntryBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI, + VisitedBlocks); +} + +void SequenceBBQuery::traverseToExitBlock(const BasicBlock *AtBB, + const BlockListTy &CallerBlocks, + const BackEdgesInfoTy &BackEdgesInfo, + const BranchProbabilityInfo *BPI, + VisitedBlocksInfoTy &VisitedBlocks) { + auto Itr = VisitedBlocks.find(AtBB); + if (Itr != VisitedBlocks.end()) { // already visited. + if (!Itr->second.Downward) + return; + Itr->second.Downward = false; + } else { + // Create hint for newly discoverd blocks. + WalkDirection BlockHint; + BlockHint.Downward = false; + // FIXME: Expensive Check + if (llvm::is_contained(CallerBlocks, AtBB)) + BlockHint.CallerBlock = true; + VisitedBlocks.insert(std::make_pair(AtBB, BlockHint)); + } + + succ_const_iterator PIt = succ_begin(AtBB), EIt = succ_end(AtBB); + if (PIt == EIt) // No succs. + return; + + // If there are hot edges, then compute SuccSkipNodes. + DenseSet SuccSkipNodes; + + // Since we are checking for successor's backedges, this Block + // occurs in first position. + for (auto &I : BackEdgesInfo) + if (I.first == AtBB) + SuccSkipNodes.insert(I.second); + + for (; PIt != EIt; ++PIt) + if (BPI->isEdgeHot(AtBB, *PIt) && !SuccSkipNodes.count(*PIt)) + traverseToExitBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI, + VisitedBlocks); +} + +// Get Block frequencies for blocks and take most frquently executed block, +// walk towards the entry block from those blocks and discover the basic blocks +// with call. +SequenceBBQuery::BlockListTy +SequenceBBQuery::queryCFG(Function &F, const BlockListTy &CallerBlocks) { + + BlockFreqInfoTy BBFreqs; + VisitedBlocksInfoTy VisitedBlocks; + BackEdgesInfoTy BackEdgesInfo; + + PassBuilder PB; + FunctionAnalysisManager FAM; + PB.registerFunctionAnalyses(FAM); + + auto &BFI = FAM.getResult(F); + + llvm::FindFunctionBackedges(F, BackEdgesInfo); + + for (const auto I : CallerBlocks) + BBFreqs.push_back({I, BFI.getBlockFreq(I).getFrequency()}); + + llvm::sort(BBFreqs, [](decltype(BBFreqs)::const_reference Bbf, + decltype(BBFreqs)::const_reference Bbs) { + return Bbf.second > Bbs.second; + }); + + ArrayRef> HotBlocksRef(BBFreqs); + HotBlocksRef = + HotBlocksRef.drop_back(BBFreqs.size() - getHottestBlocks(BBFreqs.size())); + + BranchProbabilityInfo *BPI = + FAM.getCachedResult(F); + + // visit NHotBlocks, + // traverse upwards to entry + // traverse downwards to end. + + for (auto I : HotBlocksRef) { + traverseToEntryBlock(I.first, CallerBlocks, BackEdgesInfo, BPI, + VisitedBlocks); + traverseToExitBlock(I.first, CallerBlocks, BackEdgesInfo, BPI, + VisitedBlocks); + } + + BlockListTy MinCallerBlocks; + for (auto &I : VisitedBlocks) + if (I.second.CallerBlock) + MinCallerBlocks.push_back(std::move(I.first)); + + return rearrangeBB(F, MinCallerBlocks); +} + +SpeculateQuery::ResultTy SequenceBBQuery::operator()(Function &F) { + // reduce the number of lists! + DenseMap> CallerAndCalles; + DenseSet Calles; + BlockListTy SequencedBlocks; + BlockListTy CallerBlocks; + + CallerBlocks = findBBwithCalls(F); + if (CallerBlocks.empty()) + return None; + + if (isStraightLine(F)) + SequencedBlocks = rearrangeBB(F, CallerBlocks); + else + SequencedBlocks = queryCFG(F, CallerBlocks); + + for (auto BB : SequencedBlocks) + findCalles(BB, Calles); + + CallerAndCalles.insert({F.getName(), std::move(Calles)}); + return CallerAndCalles; +} + } // namespace orc } // namespace llvm -- cgit v1.2.3