llvm/lib/ExecutionEngine/Orc/SpeculateAnalyses.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-exception
   6 //
   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
  21 namespace {
  22 using namespace llvm;
  23 SmallVector<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     else
  31       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 } // namespace
  41
  42 // Implementations of Queries shouldn't need to lock the resources
  43 // such as LLVMContext, each argument (function) has a non-shared LLVMContext
  44 // Plus, if Queries contain states necessary locking scheme should be provided.
  45 namespace llvm {
  46 namespace orc {
  47
  48 // Collect direct calls only
  49 void 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
  66 bool SpeculateQuery::isStraightLine(const Function &F) {
  67   return llvm::all_of(F, [](const BasicBlock &BB) {
  68     return BB.getSingleSuccessor() != nullptr;
  69   });
  70 }
  71
  72 // BlockFreqQuery Implementations
  73
  74 size_t BlockFreqQuery::numBBToGet(size_t numBB) {
  75   // small CFG
  76   if (numBB < 4)
  77     return numBB;
  78   // mid-size CFG
  79   else if (numBB < 20)
  80     return (numBB / 2);
  81   else
  82     return (numBB / 2) + (numBB / 4);
  83 }
  84
  85 BlockFreqQuery::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 BB
 112   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 Implementation
 125 std::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.
 132 SequenceBBQuery::BlockListTy
 133 SequenceBBQuery::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
 145 void 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 Check
 160     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 speculative
 167   // compiles for function in entry BB, this triggers the speculative compiles
 168   // 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 Block
 175   // 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 cheaper
 183     if (BPI->isEdgeHot(*PIt, AtBB) && !PredSkipNodes.count(*PIt))
 184       traverseToEntryBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI,
 185                            VisitedBlocks);
 186 }
 187
 188 void 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 Check
 203     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 Block
 216   // 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 blocks
 229 // with call.
 230 SequenceBBQuery::BlockListTy
 231 SequenceBBQuery::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 entry
 262   // 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
 279 SpeculateQuery::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   else
 293     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 orc
 303 } // namespace llvm