blob: f22acf50419d47e91ebbc1b6b9df2f8ce50d612e [file] [log] [blame]
//===-- 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/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 <algorithm>
namespace {
using namespace llvm;
SmallVector<const BasicBlock *, 8> findBBwithCalls(const Function &F,
bool IndirectCall = false) {
SmallVector<const BasicBlock *, 8> BBs;
auto findCallInst = [&IndirectCall](const Instruction &I) {
if (auto Call = dyn_cast<CallBase>(&I))
return Call->isIndirectCall() ? IndirectCall : true;
else
return false;
};
for (auto &BB : F)
if (findCallInst(*BB.getTerminator()) ||
llvm::any_of(BB.instructionsWithoutDebug(), findCallInst))
BBs.emplace_back(&BB);
return BBs;
}
} // namespace
// 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 SpeculateQuery::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);
}
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)
return numBB;
// mid-size CFG
else if (numBB < 20)
return (numBB / 2);
else
return (numBB / 2) + (numBB / 4);
}
BlockFreqQuery::ResultTy BlockFreqQuery::operator()(Function &F) {
DenseMap<StringRef, DenseSet<StringRef>> CallerAndCalles;
DenseSet<StringRef> Calles;
SmallVector<std::pair<const BasicBlock *, uint64_t>, 8> BBFreqs;
PassBuilder PB;
FunctionAnalysisManager FAM;
PB.registerFunctionAnalyses(FAM);
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;
}
// 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<const BasicBlock *> 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<const BasicBlock *> 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<BlockFrequencyAnalysis>(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<std::pair<const BasicBlock *, uint64_t>> HotBlocksRef(BBFreqs);
HotBlocksRef =
HotBlocksRef.drop_back(BBFreqs.size() - getHottestBlocks(BBFreqs.size()));
BranchProbabilityInfo *BPI =
FAM.getCachedResult<BranchProbabilityAnalysis>(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<StringRef, DenseSet<StringRef>> CallerAndCalles;
DenseSet<StringRef> 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