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