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.getBasicBlockList(), [](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 None;
 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.begin(), BBFreqs.end(),
 110              [](decltype(BBFreqs)::const_reference BBF,
 111                 decltype(BBFreqs)::const_reference BBS) {
 112                return BBF.second > BBS.second ? true : false;
 113              });
 114
 115   // ignoring number of direct calls in a BB
 116   auto Topk = numBBToGet(BBFreqs.size());
 117
 118   for (size_t i = 0; i < Topk; i++)
 119     findCalles(BBFreqs[i].first, Calles);
 120
 121   assert(!Calles.empty() && "Running Analysis on Function with no calls?");
 122
 123   CallerAndCalles.insert({F.getName(), std::move(Calles)});
 124
 125   return CallerAndCalles;
 126 }
 127
 128 // SequenceBBQuery Implementation
 129 std::size_t SequenceBBQuery::getHottestBlocks(std::size_t TotalBlocks) {
 130   if (TotalBlocks == 1)
 131     return TotalBlocks;
 132   return TotalBlocks / 2;
 133 }
 134
 135 // FIXME : find good implementation.
 136 SequenceBBQuery::BlockListTy
 137 SequenceBBQuery::rearrangeBB(const Function &F, const BlockListTy &BBList) {
 138   BlockListTy RearrangedBBSet;
 139
 140   for (auto &Block : F.getBasicBlockList())
 141     if (llvm::is_contained(BBList, &Block))
 142       RearrangedBBSet.push_back(&Block);
 143
 144   assert(RearrangedBBSet.size() == BBList.size() &&
 145          "BasicBlock missing while rearranging?");
 146   return RearrangedBBSet;
 147 }
 148
 149 void SequenceBBQuery::traverseToEntryBlock(const BasicBlock *AtBB,
 150                                            const BlockListTy &CallerBlocks,
 151                                            const BackEdgesInfoTy &BackEdgesInfo,
 152                                            const BranchProbabilityInfo *BPI,
 153                                            VisitedBlocksInfoTy &VisitedBlocks) {
 154   auto Itr = VisitedBlocks.find(AtBB);
 155   if (Itr != VisitedBlocks.end()) { // already visited.
 156     if (!Itr->second.Upward)
 157       return;
 158     Itr->second.Upward = false;
 159   } else {
 160     // Create hint for newly discoverd blocks.
 161     WalkDirection BlockHint;
 162     BlockHint.Upward = false;
 163     // FIXME: Expensive Check
 164     if (llvm::is_contained(CallerBlocks, AtBB))
 165       BlockHint.CallerBlock = true;
 166     VisitedBlocks.insert(std::make_pair(AtBB, BlockHint));
 167   }
 168
 169   const_pred_iterator PIt = pred_begin(AtBB), EIt = pred_end(AtBB);
 170   // Move this check to top, when we have code setup to launch speculative
 171   // compiles for function in entry BB, this triggers the speculative compiles
 172   // before running the program.
 173   if (PIt == EIt) // No Preds.
 174     return;
 175
 176   DenseSet<const BasicBlock *> PredSkipNodes;
 177
 178   // Since we are checking for predecessor's backedges, this Block
 179   // occurs in second position.
 180   for (auto &I : BackEdgesInfo)
 181     if (I.second == AtBB)
 182       PredSkipNodes.insert(I.first);
 183
 184   // Skip predecessors which source of back-edges.
 185   for (; PIt != EIt; ++PIt)
 186     // checking EdgeHotness is cheaper
 187     if (BPI->isEdgeHot(*PIt, AtBB) && !PredSkipNodes.count(*PIt))
 188       traverseToEntryBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI,
 189                            VisitedBlocks);
 190 }
 191
 192 void SequenceBBQuery::traverseToExitBlock(const BasicBlock *AtBB,
 193                                           const BlockListTy &CallerBlocks,
 194                                           const BackEdgesInfoTy &BackEdgesInfo,
 195                                           const BranchProbabilityInfo *BPI,
 196                                           VisitedBlocksInfoTy &VisitedBlocks) {
 197   auto Itr = VisitedBlocks.find(AtBB);
 198   if (Itr != VisitedBlocks.end()) { // already visited.
 199     if (!Itr->second.Downward)
 200       return;
 201     Itr->second.Downward = false;
 202   } else {
 203     // Create hint for newly discoverd blocks.
 204     WalkDirection BlockHint;
 205     BlockHint.Downward = false;
 206     // FIXME: Expensive Check
 207     if (llvm::is_contained(CallerBlocks, AtBB))
 208       BlockHint.CallerBlock = true;
 209     VisitedBlocks.insert(std::make_pair(AtBB, BlockHint));
 210   }
 211
 212   succ_const_iterator PIt = succ_begin(AtBB), EIt = succ_end(AtBB);
 213   if (PIt == EIt) // No succs.
 214     return;
 215
 216   // If there are hot edges, then compute SuccSkipNodes.
 217   DenseSet<const BasicBlock *> SuccSkipNodes;
 218
 219   // Since we are checking for successor's backedges, this Block
 220   // occurs in first position.
 221   for (auto &I : BackEdgesInfo)
 222     if (I.first == AtBB)
 223       SuccSkipNodes.insert(I.second);
 224
 225   for (; PIt != EIt; ++PIt)
 226     if (BPI->isEdgeHot(AtBB, *PIt) && !SuccSkipNodes.count(*PIt))
 227       traverseToExitBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI,
 228                           VisitedBlocks);
 229 }
 230
 231 // Get Block frequencies for blocks and take most frquently executed block,
 232 // walk towards the entry block from those blocks and discover the basic blocks
 233 // with call.
 234 SequenceBBQuery::BlockListTy
 235 SequenceBBQuery::queryCFG(Function &F, const BlockListTy &CallerBlocks) {
 236
 237   BlockFreqInfoTy BBFreqs;
 238   VisitedBlocksInfoTy VisitedBlocks;
 239   BackEdgesInfoTy BackEdgesInfo;
 240
 241   PassBuilder PB;
 242   FunctionAnalysisManager FAM;
 243   PB.registerFunctionAnalyses(FAM);
 244
 245   auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
 246
 247   llvm::FindFunctionBackedges(F, BackEdgesInfo);
 248
 249   for (const auto I : CallerBlocks)
 250     BBFreqs.push_back({I, BFI.getBlockFreq(I).getFrequency()});
 251
 252   llvm::sort(BBFreqs, [](decltype(BBFreqs)::const_reference Bbf,
 253                          decltype(BBFreqs)::const_reference Bbs) {
 254     return Bbf.second > Bbs.second;
 255   });
 256
 257   ArrayRef<std::pair<const BasicBlock *, uint64_t>> HotBlocksRef(BBFreqs);
 258   HotBlocksRef =
 259       HotBlocksRef.drop_back(BBFreqs.size() - getHottestBlocks(BBFreqs.size()));
 260
 261   BranchProbabilityInfo *BPI =
 262       FAM.getCachedResult<BranchProbabilityAnalysis>(F);
 263
 264   // visit NHotBlocks,
 265   // traverse upwards to entry
 266   // traverse downwards to end.
 267
 268   for (auto I : HotBlocksRef) {
 269     traverseToEntryBlock(I.first, CallerBlocks, BackEdgesInfo, BPI,
 270                          VisitedBlocks);
 271     traverseToExitBlock(I.first, CallerBlocks, BackEdgesInfo, BPI,
 272                         VisitedBlocks);
 273   }
 274
 275   BlockListTy MinCallerBlocks;
 276   for (auto &I : VisitedBlocks)
 277     if (I.second.CallerBlock)
 278       MinCallerBlocks.push_back(std::move(I.first));
 279
 280   return rearrangeBB(F, MinCallerBlocks);
 281 }
 282
 283 SpeculateQuery::ResultTy SequenceBBQuery::operator()(Function &F) {
 284   // reduce the number of lists!
 285   DenseMap<StringRef, DenseSet<StringRef>> CallerAndCalles;
 286   DenseSet<StringRef> Calles;
 287   BlockListTy SequencedBlocks;
 288   BlockListTy CallerBlocks;
 289
 290   CallerBlocks = findBBwithCalls(F);
 291   if (CallerBlocks.empty())
 292     return None;
 293
 294   if (isStraightLine(F))
 295     SequencedBlocks = rearrangeBB(F, CallerBlocks);
 296   else
 297     SequencedBlocks = queryCFG(F, CallerBlocks);
 298
 299   for (auto BB : SequencedBlocks)
 300     findCalles(BB, Calles);
 301
 302   CallerAndCalles.insert({F.getName(), std::move(Calles)});
 303   return CallerAndCalles;
 304 }
 305
 306 } // namespace orc
 307 } // namespace llvm