304 lines · cpp
1//===-- SpeculateAnalyses.cpp --*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/ExecutionEngine/Orc/SpeculateAnalyses.h"10#include "llvm/ADT/ArrayRef.h"11#include "llvm/ADT/DenseMap.h"12#include "llvm/ADT/STLExtras.h"13#include "llvm/ADT/SmallVector.h"14#include "llvm/Analysis/BlockFrequencyInfo.h"15#include "llvm/Analysis/BranchProbabilityInfo.h"16#include "llvm/Analysis/CFG.h"17#include "llvm/IR/PassManager.h"18#include "llvm/Passes/PassBuilder.h"19#include "llvm/Support/ErrorHandling.h"20 21namespace {22using namespace llvm;23SmallVector<const BasicBlock *, 8> findBBwithCalls(const Function &F,24 bool IndirectCall = false) {25 SmallVector<const BasicBlock *, 8> BBs;26 27 auto findCallInst = [&IndirectCall](const Instruction &I) {28 if (auto Call = dyn_cast<CallBase>(&I))29 return Call->isIndirectCall() ? IndirectCall : true;30 else31 return false;32 };33 for (auto &BB : F)34 if (findCallInst(*BB.getTerminator()) ||35 llvm::any_of(BB.instructionsWithoutDebug(), findCallInst))36 BBs.emplace_back(&BB);37 38 return BBs;39}40} // namespace41 42// Implementations of Queries shouldn't need to lock the resources43// such as LLVMContext, each argument (function) has a non-shared LLVMContext44// Plus, if Queries contain states necessary locking scheme should be provided.45namespace llvm {46namespace orc {47 48// Collect direct calls only49void SpeculateQuery::findCalles(const BasicBlock *BB,50 DenseSet<StringRef> &CallesNames) {51 assert(BB != nullptr && "Traversing Null BB to find calls?");52 53 auto getCalledFunction = [&CallesNames](const CallBase *Call) {54 auto CalledValue = Call->getCalledOperand()->stripPointerCasts();55 if (auto DirectCall = dyn_cast<Function>(CalledValue))56 CallesNames.insert(DirectCall->getName());57 };58 for (auto &I : BB->instructionsWithoutDebug())59 if (auto CI = dyn_cast<CallInst>(&I))60 getCalledFunction(CI);61 62 if (auto II = dyn_cast<InvokeInst>(BB->getTerminator()))63 getCalledFunction(II);64}65 66bool SpeculateQuery::isStraightLine(const Function &F) {67 return llvm::all_of(F, [](const BasicBlock &BB) {68 return BB.getSingleSuccessor() != nullptr;69 });70}71 72// BlockFreqQuery Implementations73 74size_t BlockFreqQuery::numBBToGet(size_t numBB) {75 // small CFG76 if (numBB < 4)77 return numBB;78 // mid-size CFG79 else if (numBB < 20)80 return (numBB / 2);81 else82 return (numBB / 2) + (numBB / 4);83}84 85BlockFreqQuery::ResultTy BlockFreqQuery::operator()(Function &F) {86 DenseMap<StringRef, DenseSet<StringRef>> CallerAndCalles;87 DenseSet<StringRef> Calles;88 SmallVector<std::pair<const BasicBlock *, uint64_t>, 8> BBFreqs;89 90 PassBuilder PB;91 FunctionAnalysisManager FAM;92 PB.registerFunctionAnalyses(FAM);93 94 auto IBBs = findBBwithCalls(F);95 96 if (IBBs.empty())97 return std::nullopt;98 99 auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);100 101 for (const auto I : IBBs)102 BBFreqs.push_back({I, BFI.getBlockFreq(I).getFrequency()});103 104 assert(IBBs.size() == BBFreqs.size() && "BB Count Mismatch");105 106 llvm::sort(BBFreqs, [](decltype(BBFreqs)::const_reference BBF,107 decltype(BBFreqs)::const_reference BBS) {108 return BBF.second > BBS.second ? true : false;109 });110 111 // ignoring number of direct calls in a BB112 auto Topk = numBBToGet(BBFreqs.size());113 114 for (size_t i = 0; i < Topk; i++)115 findCalles(BBFreqs[i].first, Calles);116 117 assert(!Calles.empty() && "Running Analysis on Function with no calls?");118 119 CallerAndCalles.insert({F.getName(), std::move(Calles)});120 121 return CallerAndCalles;122}123 124// SequenceBBQuery Implementation125std::size_t SequenceBBQuery::getHottestBlocks(std::size_t TotalBlocks) {126 if (TotalBlocks == 1)127 return TotalBlocks;128 return TotalBlocks / 2;129}130 131// FIXME : find good implementation.132SequenceBBQuery::BlockListTy133SequenceBBQuery::rearrangeBB(const Function &F, const BlockListTy &BBList) {134 BlockListTy RearrangedBBSet;135 136 for (auto &Block : F)137 if (llvm::is_contained(BBList, &Block))138 RearrangedBBSet.push_back(&Block);139 140 assert(RearrangedBBSet.size() == BBList.size() &&141 "BasicBlock missing while rearranging?");142 return RearrangedBBSet;143}144 145void SequenceBBQuery::traverseToEntryBlock(const BasicBlock *AtBB,146 const BlockListTy &CallerBlocks,147 const BackEdgesInfoTy &BackEdgesInfo,148 const BranchProbabilityInfo *BPI,149 VisitedBlocksInfoTy &VisitedBlocks) {150 auto Itr = VisitedBlocks.find(AtBB);151 if (Itr != VisitedBlocks.end()) { // already visited.152 if (!Itr->second.Upward)153 return;154 Itr->second.Upward = false;155 } else {156 // Create hint for newly discoverd blocks.157 WalkDirection BlockHint;158 BlockHint.Upward = false;159 // FIXME: Expensive Check160 if (llvm::is_contained(CallerBlocks, AtBB))161 BlockHint.CallerBlock = true;162 VisitedBlocks.insert(std::make_pair(AtBB, BlockHint));163 }164 165 const_pred_iterator PIt = pred_begin(AtBB), EIt = pred_end(AtBB);166 // Move this check to top, when we have code setup to launch speculative167 // compiles for function in entry BB, this triggers the speculative compiles168 // before running the program.169 if (PIt == EIt) // No Preds.170 return;171 172 DenseSet<const BasicBlock *> PredSkipNodes;173 174 // Since we are checking for predecessor's backedges, this Block175 // occurs in second position.176 for (auto &I : BackEdgesInfo)177 if (I.second == AtBB)178 PredSkipNodes.insert(I.first);179 180 // Skip predecessors which source of back-edges.181 for (; PIt != EIt; ++PIt)182 // checking EdgeHotness is cheaper183 if (BPI->isEdgeHot(*PIt, AtBB) && !PredSkipNodes.count(*PIt))184 traverseToEntryBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI,185 VisitedBlocks);186}187 188void SequenceBBQuery::traverseToExitBlock(const BasicBlock *AtBB,189 const BlockListTy &CallerBlocks,190 const BackEdgesInfoTy &BackEdgesInfo,191 const BranchProbabilityInfo *BPI,192 VisitedBlocksInfoTy &VisitedBlocks) {193 auto Itr = VisitedBlocks.find(AtBB);194 if (Itr != VisitedBlocks.end()) { // already visited.195 if (!Itr->second.Downward)196 return;197 Itr->second.Downward = false;198 } else {199 // Create hint for newly discoverd blocks.200 WalkDirection BlockHint;201 BlockHint.Downward = false;202 // FIXME: Expensive Check203 if (llvm::is_contained(CallerBlocks, AtBB))204 BlockHint.CallerBlock = true;205 VisitedBlocks.insert(std::make_pair(AtBB, BlockHint));206 }207 208 const_succ_iterator PIt = succ_begin(AtBB), EIt = succ_end(AtBB);209 if (PIt == EIt) // No succs.210 return;211 212 // If there are hot edges, then compute SuccSkipNodes.213 DenseSet<const BasicBlock *> SuccSkipNodes;214 215 // Since we are checking for successor's backedges, this Block216 // occurs in first position.217 for (auto &I : BackEdgesInfo)218 if (I.first == AtBB)219 SuccSkipNodes.insert(I.second);220 221 for (; PIt != EIt; ++PIt)222 if (BPI->isEdgeHot(AtBB, *PIt) && !SuccSkipNodes.count(*PIt))223 traverseToExitBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI,224 VisitedBlocks);225}226 227// Get Block frequencies for blocks and take most frequently executed block,228// walk towards the entry block from those blocks and discover the basic blocks229// with call.230SequenceBBQuery::BlockListTy231SequenceBBQuery::queryCFG(Function &F, const BlockListTy &CallerBlocks) {232 233 BlockFreqInfoTy BBFreqs;234 VisitedBlocksInfoTy VisitedBlocks;235 BackEdgesInfoTy BackEdgesInfo;236 237 PassBuilder PB;238 FunctionAnalysisManager FAM;239 PB.registerFunctionAnalyses(FAM);240 241 auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);242 243 llvm::FindFunctionBackedges(F, BackEdgesInfo);244 245 for (const auto I : CallerBlocks)246 BBFreqs.push_back({I, BFI.getBlockFreq(I).getFrequency()});247 248 llvm::sort(BBFreqs, [](decltype(BBFreqs)::const_reference Bbf,249 decltype(BBFreqs)::const_reference Bbs) {250 return Bbf.second > Bbs.second;251 });252 253 ArrayRef<std::pair<const BasicBlock *, uint64_t>> HotBlocksRef(BBFreqs);254 HotBlocksRef =255 HotBlocksRef.drop_back(BBFreqs.size() - getHottestBlocks(BBFreqs.size()));256 257 BranchProbabilityInfo *BPI =258 FAM.getCachedResult<BranchProbabilityAnalysis>(F);259 260 // visit NHotBlocks,261 // traverse upwards to entry262 // traverse downwards to end.263 264 for (auto I : HotBlocksRef) {265 traverseToEntryBlock(I.first, CallerBlocks, BackEdgesInfo, BPI,266 VisitedBlocks);267 traverseToExitBlock(I.first, CallerBlocks, BackEdgesInfo, BPI,268 VisitedBlocks);269 }270 271 BlockListTy MinCallerBlocks;272 for (auto &I : VisitedBlocks)273 if (I.second.CallerBlock)274 MinCallerBlocks.push_back(std::move(I.first));275 276 return rearrangeBB(F, MinCallerBlocks);277}278 279SpeculateQuery::ResultTy SequenceBBQuery::operator()(Function &F) {280 // reduce the number of lists!281 DenseMap<StringRef, DenseSet<StringRef>> CallerAndCalles;282 DenseSet<StringRef> Calles;283 BlockListTy SequencedBlocks;284 BlockListTy CallerBlocks;285 286 CallerBlocks = findBBwithCalls(F);287 if (CallerBlocks.empty())288 return std::nullopt;289 290 if (isStraightLine(F))291 SequencedBlocks = rearrangeBB(F, CallerBlocks);292 else293 SequencedBlocks = queryCFG(F, CallerBlocks);294 295 for (const auto *BB : SequencedBlocks)296 findCalles(BB, Calles);297 298 CallerAndCalles.insert({F.getName(), std::move(Calles)});299 return CallerAndCalles;300}301 302} // namespace orc303} // namespace llvm304