18bcb0991SDimitry Andric //===-- SpeculateAnalyses.cpp --*- C++ -*-===//
28bcb0991SDimitry Andric //
38bcb0991SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
48bcb0991SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
58bcb0991SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
68bcb0991SDimitry Andric //
78bcb0991SDimitry Andric //===----------------------------------------------------------------------===//
88bcb0991SDimitry Andric
98bcb0991SDimitry Andric #include "llvm/ExecutionEngine/Orc/SpeculateAnalyses.h"
108bcb0991SDimitry Andric #include "llvm/ADT/ArrayRef.h"
118bcb0991SDimitry Andric #include "llvm/ADT/DenseMap.h"
128bcb0991SDimitry Andric #include "llvm/ADT/STLExtras.h"
138bcb0991SDimitry Andric #include "llvm/ADT/SmallVector.h"
148bcb0991SDimitry Andric #include "llvm/Analysis/BlockFrequencyInfo.h"
158bcb0991SDimitry Andric #include "llvm/Analysis/BranchProbabilityInfo.h"
168bcb0991SDimitry Andric #include "llvm/Analysis/CFG.h"
178bcb0991SDimitry Andric #include "llvm/IR/PassManager.h"
188bcb0991SDimitry Andric #include "llvm/Passes/PassBuilder.h"
198bcb0991SDimitry Andric #include "llvm/Support/ErrorHandling.h"
208bcb0991SDimitry Andric
218bcb0991SDimitry Andric #include <algorithm>
228bcb0991SDimitry Andric
238bcb0991SDimitry Andric namespace {
248bcb0991SDimitry Andric using namespace llvm;
findBBwithCalls(const Function & F,bool IndirectCall=false)258bcb0991SDimitry Andric SmallVector<const BasicBlock *, 8> findBBwithCalls(const Function &F,
268bcb0991SDimitry Andric bool IndirectCall = false) {
278bcb0991SDimitry Andric SmallVector<const BasicBlock *, 8> BBs;
288bcb0991SDimitry Andric
298bcb0991SDimitry Andric auto findCallInst = [&IndirectCall](const Instruction &I) {
308bcb0991SDimitry Andric if (auto Call = dyn_cast<CallBase>(&I))
318bcb0991SDimitry Andric return Call->isIndirectCall() ? IndirectCall : true;
328bcb0991SDimitry Andric else
338bcb0991SDimitry Andric return false;
348bcb0991SDimitry Andric };
358bcb0991SDimitry Andric for (auto &BB : F)
368bcb0991SDimitry Andric if (findCallInst(*BB.getTerminator()) ||
378bcb0991SDimitry Andric llvm::any_of(BB.instructionsWithoutDebug(), findCallInst))
388bcb0991SDimitry Andric BBs.emplace_back(&BB);
398bcb0991SDimitry Andric
408bcb0991SDimitry Andric return BBs;
418bcb0991SDimitry Andric }
428bcb0991SDimitry Andric } // namespace
438bcb0991SDimitry Andric
448bcb0991SDimitry Andric // Implementations of Queries shouldn't need to lock the resources
458bcb0991SDimitry Andric // such as LLVMContext, each argument (function) has a non-shared LLVMContext
468bcb0991SDimitry Andric // Plus, if Queries contain states necessary locking scheme should be provided.
478bcb0991SDimitry Andric namespace llvm {
488bcb0991SDimitry Andric namespace orc {
498bcb0991SDimitry Andric
508bcb0991SDimitry Andric // Collect direct calls only
findCalles(const BasicBlock * BB,DenseSet<StringRef> & CallesNames)518bcb0991SDimitry Andric void SpeculateQuery::findCalles(const BasicBlock *BB,
528bcb0991SDimitry Andric DenseSet<StringRef> &CallesNames) {
538bcb0991SDimitry Andric assert(BB != nullptr && "Traversing Null BB to find calls?");
548bcb0991SDimitry Andric
558bcb0991SDimitry Andric auto getCalledFunction = [&CallesNames](const CallBase *Call) {
568bcb0991SDimitry Andric auto CalledValue = Call->getCalledOperand()->stripPointerCasts();
578bcb0991SDimitry Andric if (auto DirectCall = dyn_cast<Function>(CalledValue))
588bcb0991SDimitry Andric CallesNames.insert(DirectCall->getName());
598bcb0991SDimitry Andric };
608bcb0991SDimitry Andric for (auto &I : BB->instructionsWithoutDebug())
618bcb0991SDimitry Andric if (auto CI = dyn_cast<CallInst>(&I))
628bcb0991SDimitry Andric getCalledFunction(CI);
638bcb0991SDimitry Andric
648bcb0991SDimitry Andric if (auto II = dyn_cast<InvokeInst>(BB->getTerminator()))
658bcb0991SDimitry Andric getCalledFunction(II);
668bcb0991SDimitry Andric }
678bcb0991SDimitry Andric
isStraightLine(const Function & F)688bcb0991SDimitry Andric bool SpeculateQuery::isStraightLine(const Function &F) {
69bdd1243dSDimitry Andric return llvm::all_of(F, [](const BasicBlock &BB) {
708bcb0991SDimitry Andric return BB.getSingleSuccessor() != nullptr;
718bcb0991SDimitry Andric });
728bcb0991SDimitry Andric }
738bcb0991SDimitry Andric
748bcb0991SDimitry Andric // BlockFreqQuery Implementations
758bcb0991SDimitry Andric
numBBToGet(size_t numBB)768bcb0991SDimitry Andric size_t BlockFreqQuery::numBBToGet(size_t numBB) {
778bcb0991SDimitry Andric // small CFG
788bcb0991SDimitry Andric if (numBB < 4)
798bcb0991SDimitry Andric return numBB;
808bcb0991SDimitry Andric // mid-size CFG
818bcb0991SDimitry Andric else if (numBB < 20)
828bcb0991SDimitry Andric return (numBB / 2);
838bcb0991SDimitry Andric else
848bcb0991SDimitry Andric return (numBB / 2) + (numBB / 4);
858bcb0991SDimitry Andric }
868bcb0991SDimitry Andric
operator ()(Function & F)878bcb0991SDimitry Andric BlockFreqQuery::ResultTy BlockFreqQuery::operator()(Function &F) {
888bcb0991SDimitry Andric DenseMap<StringRef, DenseSet<StringRef>> CallerAndCalles;
898bcb0991SDimitry Andric DenseSet<StringRef> Calles;
908bcb0991SDimitry Andric SmallVector<std::pair<const BasicBlock *, uint64_t>, 8> BBFreqs;
918bcb0991SDimitry Andric
928bcb0991SDimitry Andric PassBuilder PB;
938bcb0991SDimitry Andric FunctionAnalysisManager FAM;
948bcb0991SDimitry Andric PB.registerFunctionAnalyses(FAM);
958bcb0991SDimitry Andric
968bcb0991SDimitry Andric auto IBBs = findBBwithCalls(F);
978bcb0991SDimitry Andric
988bcb0991SDimitry Andric if (IBBs.empty())
99bdd1243dSDimitry Andric return std::nullopt;
1008bcb0991SDimitry Andric
1018bcb0991SDimitry Andric auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
1028bcb0991SDimitry Andric
1038bcb0991SDimitry Andric for (const auto I : IBBs)
1048bcb0991SDimitry Andric BBFreqs.push_back({I, BFI.getBlockFreq(I).getFrequency()});
1058bcb0991SDimitry Andric
1068bcb0991SDimitry Andric assert(IBBs.size() == BBFreqs.size() && "BB Count Mismatch");
1078bcb0991SDimitry Andric
108e8d8bef9SDimitry Andric llvm::sort(BBFreqs, [](decltype(BBFreqs)::const_reference BBF,
1098bcb0991SDimitry Andric decltype(BBFreqs)::const_reference BBS) {
1108bcb0991SDimitry Andric return BBF.second > BBS.second ? true : false;
1118bcb0991SDimitry Andric });
1128bcb0991SDimitry Andric
1138bcb0991SDimitry Andric // ignoring number of direct calls in a BB
1148bcb0991SDimitry Andric auto Topk = numBBToGet(BBFreqs.size());
1158bcb0991SDimitry Andric
1168bcb0991SDimitry Andric for (size_t i = 0; i < Topk; i++)
1178bcb0991SDimitry Andric findCalles(BBFreqs[i].first, Calles);
1188bcb0991SDimitry Andric
1198bcb0991SDimitry Andric assert(!Calles.empty() && "Running Analysis on Function with no calls?");
1208bcb0991SDimitry Andric
1218bcb0991SDimitry Andric CallerAndCalles.insert({F.getName(), std::move(Calles)});
1228bcb0991SDimitry Andric
1238bcb0991SDimitry Andric return CallerAndCalles;
1248bcb0991SDimitry Andric }
1258bcb0991SDimitry Andric
1268bcb0991SDimitry Andric // SequenceBBQuery Implementation
getHottestBlocks(std::size_t TotalBlocks)1278bcb0991SDimitry Andric std::size_t SequenceBBQuery::getHottestBlocks(std::size_t TotalBlocks) {
1288bcb0991SDimitry Andric if (TotalBlocks == 1)
1298bcb0991SDimitry Andric return TotalBlocks;
1308bcb0991SDimitry Andric return TotalBlocks / 2;
1318bcb0991SDimitry Andric }
1328bcb0991SDimitry Andric
1338bcb0991SDimitry Andric // FIXME : find good implementation.
1348bcb0991SDimitry Andric SequenceBBQuery::BlockListTy
rearrangeBB(const Function & F,const BlockListTy & BBList)1358bcb0991SDimitry Andric SequenceBBQuery::rearrangeBB(const Function &F, const BlockListTy &BBList) {
1368bcb0991SDimitry Andric BlockListTy RearrangedBBSet;
1378bcb0991SDimitry Andric
138bdd1243dSDimitry Andric for (auto &Block : F)
1398bcb0991SDimitry Andric if (llvm::is_contained(BBList, &Block))
1408bcb0991SDimitry Andric RearrangedBBSet.push_back(&Block);
1418bcb0991SDimitry Andric
1428bcb0991SDimitry Andric assert(RearrangedBBSet.size() == BBList.size() &&
1438bcb0991SDimitry Andric "BasicBlock missing while rearranging?");
1448bcb0991SDimitry Andric return RearrangedBBSet;
1458bcb0991SDimitry Andric }
1468bcb0991SDimitry Andric
traverseToEntryBlock(const BasicBlock * AtBB,const BlockListTy & CallerBlocks,const BackEdgesInfoTy & BackEdgesInfo,const BranchProbabilityInfo * BPI,VisitedBlocksInfoTy & VisitedBlocks)1478bcb0991SDimitry Andric void SequenceBBQuery::traverseToEntryBlock(const BasicBlock *AtBB,
1488bcb0991SDimitry Andric const BlockListTy &CallerBlocks,
1498bcb0991SDimitry Andric const BackEdgesInfoTy &BackEdgesInfo,
1508bcb0991SDimitry Andric const BranchProbabilityInfo *BPI,
1518bcb0991SDimitry Andric VisitedBlocksInfoTy &VisitedBlocks) {
1528bcb0991SDimitry Andric auto Itr = VisitedBlocks.find(AtBB);
1538bcb0991SDimitry Andric if (Itr != VisitedBlocks.end()) { // already visited.
1548bcb0991SDimitry Andric if (!Itr->second.Upward)
1558bcb0991SDimitry Andric return;
1568bcb0991SDimitry Andric Itr->second.Upward = false;
1578bcb0991SDimitry Andric } else {
1588bcb0991SDimitry Andric // Create hint for newly discoverd blocks.
1598bcb0991SDimitry Andric WalkDirection BlockHint;
1608bcb0991SDimitry Andric BlockHint.Upward = false;
1618bcb0991SDimitry Andric // FIXME: Expensive Check
1628bcb0991SDimitry Andric if (llvm::is_contained(CallerBlocks, AtBB))
1638bcb0991SDimitry Andric BlockHint.CallerBlock = true;
1648bcb0991SDimitry Andric VisitedBlocks.insert(std::make_pair(AtBB, BlockHint));
1658bcb0991SDimitry Andric }
1668bcb0991SDimitry Andric
1678bcb0991SDimitry Andric const_pred_iterator PIt = pred_begin(AtBB), EIt = pred_end(AtBB);
1688bcb0991SDimitry Andric // Move this check to top, when we have code setup to launch speculative
1698bcb0991SDimitry Andric // compiles for function in entry BB, this triggers the speculative compiles
1708bcb0991SDimitry Andric // before running the program.
1718bcb0991SDimitry Andric if (PIt == EIt) // No Preds.
1728bcb0991SDimitry Andric return;
1738bcb0991SDimitry Andric
1748bcb0991SDimitry Andric DenseSet<const BasicBlock *> PredSkipNodes;
1758bcb0991SDimitry Andric
1768bcb0991SDimitry Andric // Since we are checking for predecessor's backedges, this Block
1778bcb0991SDimitry Andric // occurs in second position.
1788bcb0991SDimitry Andric for (auto &I : BackEdgesInfo)
1798bcb0991SDimitry Andric if (I.second == AtBB)
1808bcb0991SDimitry Andric PredSkipNodes.insert(I.first);
1818bcb0991SDimitry Andric
1828bcb0991SDimitry Andric // Skip predecessors which source of back-edges.
1838bcb0991SDimitry Andric for (; PIt != EIt; ++PIt)
1848bcb0991SDimitry Andric // checking EdgeHotness is cheaper
1858bcb0991SDimitry Andric if (BPI->isEdgeHot(*PIt, AtBB) && !PredSkipNodes.count(*PIt))
1868bcb0991SDimitry Andric traverseToEntryBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI,
1878bcb0991SDimitry Andric VisitedBlocks);
1888bcb0991SDimitry Andric }
1898bcb0991SDimitry Andric
traverseToExitBlock(const BasicBlock * AtBB,const BlockListTy & CallerBlocks,const BackEdgesInfoTy & BackEdgesInfo,const BranchProbabilityInfo * BPI,VisitedBlocksInfoTy & VisitedBlocks)1908bcb0991SDimitry Andric void SequenceBBQuery::traverseToExitBlock(const BasicBlock *AtBB,
1918bcb0991SDimitry Andric const BlockListTy &CallerBlocks,
1928bcb0991SDimitry Andric const BackEdgesInfoTy &BackEdgesInfo,
1938bcb0991SDimitry Andric const BranchProbabilityInfo *BPI,
1948bcb0991SDimitry Andric VisitedBlocksInfoTy &VisitedBlocks) {
1958bcb0991SDimitry Andric auto Itr = VisitedBlocks.find(AtBB);
1968bcb0991SDimitry Andric if (Itr != VisitedBlocks.end()) { // already visited.
1978bcb0991SDimitry Andric if (!Itr->second.Downward)
1988bcb0991SDimitry Andric return;
1998bcb0991SDimitry Andric Itr->second.Downward = false;
2008bcb0991SDimitry Andric } else {
2018bcb0991SDimitry Andric // Create hint for newly discoverd blocks.
2028bcb0991SDimitry Andric WalkDirection BlockHint;
2038bcb0991SDimitry Andric BlockHint.Downward = false;
2048bcb0991SDimitry Andric // FIXME: Expensive Check
2058bcb0991SDimitry Andric if (llvm::is_contained(CallerBlocks, AtBB))
2068bcb0991SDimitry Andric BlockHint.CallerBlock = true;
2078bcb0991SDimitry Andric VisitedBlocks.insert(std::make_pair(AtBB, BlockHint));
2088bcb0991SDimitry Andric }
2098bcb0991SDimitry Andric
2105ffd83dbSDimitry Andric const_succ_iterator PIt = succ_begin(AtBB), EIt = succ_end(AtBB);
2118bcb0991SDimitry Andric if (PIt == EIt) // No succs.
2128bcb0991SDimitry Andric return;
2138bcb0991SDimitry Andric
2148bcb0991SDimitry Andric // If there are hot edges, then compute SuccSkipNodes.
2158bcb0991SDimitry Andric DenseSet<const BasicBlock *> SuccSkipNodes;
2168bcb0991SDimitry Andric
2178bcb0991SDimitry Andric // Since we are checking for successor's backedges, this Block
2188bcb0991SDimitry Andric // occurs in first position.
2198bcb0991SDimitry Andric for (auto &I : BackEdgesInfo)
2208bcb0991SDimitry Andric if (I.first == AtBB)
2218bcb0991SDimitry Andric SuccSkipNodes.insert(I.second);
2228bcb0991SDimitry Andric
2238bcb0991SDimitry Andric for (; PIt != EIt; ++PIt)
2248bcb0991SDimitry Andric if (BPI->isEdgeHot(AtBB, *PIt) && !SuccSkipNodes.count(*PIt))
2258bcb0991SDimitry Andric traverseToExitBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI,
2268bcb0991SDimitry Andric VisitedBlocks);
2278bcb0991SDimitry Andric }
2288bcb0991SDimitry Andric
229*5f757f3fSDimitry Andric // Get Block frequencies for blocks and take most frequently executed block,
2308bcb0991SDimitry Andric // walk towards the entry block from those blocks and discover the basic blocks
2318bcb0991SDimitry Andric // with call.
2328bcb0991SDimitry Andric SequenceBBQuery::BlockListTy
queryCFG(Function & F,const BlockListTy & CallerBlocks)2338bcb0991SDimitry Andric SequenceBBQuery::queryCFG(Function &F, const BlockListTy &CallerBlocks) {
2348bcb0991SDimitry Andric
2358bcb0991SDimitry Andric BlockFreqInfoTy BBFreqs;
2368bcb0991SDimitry Andric VisitedBlocksInfoTy VisitedBlocks;
2378bcb0991SDimitry Andric BackEdgesInfoTy BackEdgesInfo;
2388bcb0991SDimitry Andric
2398bcb0991SDimitry Andric PassBuilder PB;
2408bcb0991SDimitry Andric FunctionAnalysisManager FAM;
2418bcb0991SDimitry Andric PB.registerFunctionAnalyses(FAM);
2428bcb0991SDimitry Andric
2438bcb0991SDimitry Andric auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
2448bcb0991SDimitry Andric
2458bcb0991SDimitry Andric llvm::FindFunctionBackedges(F, BackEdgesInfo);
2468bcb0991SDimitry Andric
2478bcb0991SDimitry Andric for (const auto I : CallerBlocks)
2488bcb0991SDimitry Andric BBFreqs.push_back({I, BFI.getBlockFreq(I).getFrequency()});
2498bcb0991SDimitry Andric
2508bcb0991SDimitry Andric llvm::sort(BBFreqs, [](decltype(BBFreqs)::const_reference Bbf,
2518bcb0991SDimitry Andric decltype(BBFreqs)::const_reference Bbs) {
2528bcb0991SDimitry Andric return Bbf.second > Bbs.second;
2538bcb0991SDimitry Andric });
2548bcb0991SDimitry Andric
2558bcb0991SDimitry Andric ArrayRef<std::pair<const BasicBlock *, uint64_t>> HotBlocksRef(BBFreqs);
2568bcb0991SDimitry Andric HotBlocksRef =
2578bcb0991SDimitry Andric HotBlocksRef.drop_back(BBFreqs.size() - getHottestBlocks(BBFreqs.size()));
2588bcb0991SDimitry Andric
2598bcb0991SDimitry Andric BranchProbabilityInfo *BPI =
2608bcb0991SDimitry Andric FAM.getCachedResult<BranchProbabilityAnalysis>(F);
2618bcb0991SDimitry Andric
2628bcb0991SDimitry Andric // visit NHotBlocks,
2638bcb0991SDimitry Andric // traverse upwards to entry
2648bcb0991SDimitry Andric // traverse downwards to end.
2658bcb0991SDimitry Andric
2668bcb0991SDimitry Andric for (auto I : HotBlocksRef) {
2678bcb0991SDimitry Andric traverseToEntryBlock(I.first, CallerBlocks, BackEdgesInfo, BPI,
2688bcb0991SDimitry Andric VisitedBlocks);
2698bcb0991SDimitry Andric traverseToExitBlock(I.first, CallerBlocks, BackEdgesInfo, BPI,
2708bcb0991SDimitry Andric VisitedBlocks);
2718bcb0991SDimitry Andric }
2728bcb0991SDimitry Andric
2738bcb0991SDimitry Andric BlockListTy MinCallerBlocks;
2748bcb0991SDimitry Andric for (auto &I : VisitedBlocks)
2758bcb0991SDimitry Andric if (I.second.CallerBlock)
2768bcb0991SDimitry Andric MinCallerBlocks.push_back(std::move(I.first));
2778bcb0991SDimitry Andric
2788bcb0991SDimitry Andric return rearrangeBB(F, MinCallerBlocks);
2798bcb0991SDimitry Andric }
2808bcb0991SDimitry Andric
operator ()(Function & F)2818bcb0991SDimitry Andric SpeculateQuery::ResultTy SequenceBBQuery::operator()(Function &F) {
2828bcb0991SDimitry Andric // reduce the number of lists!
2838bcb0991SDimitry Andric DenseMap<StringRef, DenseSet<StringRef>> CallerAndCalles;
2848bcb0991SDimitry Andric DenseSet<StringRef> Calles;
2858bcb0991SDimitry Andric BlockListTy SequencedBlocks;
2868bcb0991SDimitry Andric BlockListTy CallerBlocks;
2878bcb0991SDimitry Andric
2888bcb0991SDimitry Andric CallerBlocks = findBBwithCalls(F);
2898bcb0991SDimitry Andric if (CallerBlocks.empty())
290bdd1243dSDimitry Andric return std::nullopt;
2918bcb0991SDimitry Andric
2928bcb0991SDimitry Andric if (isStraightLine(F))
2938bcb0991SDimitry Andric SequencedBlocks = rearrangeBB(F, CallerBlocks);
2948bcb0991SDimitry Andric else
2958bcb0991SDimitry Andric SequencedBlocks = queryCFG(F, CallerBlocks);
2968bcb0991SDimitry Andric
297bdd1243dSDimitry Andric for (const auto *BB : SequencedBlocks)
2988bcb0991SDimitry Andric findCalles(BB, Calles);
2998bcb0991SDimitry Andric
3008bcb0991SDimitry Andric CallerAndCalles.insert({F.getName(), std::move(Calles)});
3018bcb0991SDimitry Andric return CallerAndCalles;
3028bcb0991SDimitry Andric }
3038bcb0991SDimitry Andric
3048bcb0991SDimitry Andric } // namespace orc
3058bcb0991SDimitry Andric } // namespace llvm
306