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/DenseMap.h"
11 #include "llvm/ADT/STLExtras.h"
12 #include "llvm/ADT/SmallVector.h"
13 #include "llvm/Analysis/BlockFrequencyInfo.h"
14 
15 // Implementations of Queries shouldn't need to lock the resources
16 // such as LLVMContext, each argument (function) has a non-shared LLVMContext
17 namespace llvm {
18 namespace orc {
19 
20 // Collect direct calls only
21 void BlockFreqQuery::findCalles(const BasicBlock *BB,
22                                 DenseSet<StringRef> &CallesNames) {
23   assert(BB != nullptr && "Traversing Null BB to find calls?");
24 
25   auto getCalledFunction = [&CallesNames](const CallBase *Call) {
26     auto CalledValue = Call->getCalledOperand()->stripPointerCasts();
27     if (auto DirectCall = dyn_cast<Function>(CalledValue))
28       CallesNames.insert(DirectCall->getName());
29   };
30   for (auto &I : BB->instructionsWithoutDebug())
31     if (auto CI = dyn_cast<CallInst>(&I))
32       getCalledFunction(CI);
33 
34   if (auto II = dyn_cast<InvokeInst>(BB->getTerminator()))
35     getCalledFunction(II);
36 }
37 
38 // blind calculation
39 size_t BlockFreqQuery::numBBToGet(size_t numBB) {
40   // small CFG
41   if (numBB < 4)
42     return numBB;
43   // mid-size CFG
44   else if (numBB < 20)
45     return (numBB / 2);
46   else
47     return (numBB / 2) + (numBB / 4);
48 }
49 
50 BlockFreqQuery::ResultTy BlockFreqQuery::
51 operator()(Function &F, FunctionAnalysisManager &FAM) {
52   DenseMap<StringRef, DenseSet<StringRef>> CallerAndCalles;
53   DenseSet<StringRef> Calles;
54   SmallVector<std::pair<const BasicBlock *, uint64_t>, 8> BBFreqs;
55 
56   auto IBBs = findBBwithCalls(F);
57 
58   if (IBBs.empty())
59     return None;
60 
61   auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
62 
63   for (const auto I : IBBs)
64     BBFreqs.push_back({I, BFI.getBlockFreq(I).getFrequency()});
65 
66   assert(IBBs.size() == BBFreqs.size() && "BB Count Mismatch");
67 
68   llvm::sort(BBFreqs.begin(), BBFreqs.end(),
69              [](decltype(BBFreqs)::const_reference BBF,
70                 decltype(BBFreqs)::const_reference BBS) {
71                return BBF.second > BBS.second ? true : false;
72              });
73 
74   // ignoring number of direct calls in a BB
75   auto Topk = numBBToGet(BBFreqs.size());
76 
77   for (size_t i = 0; i < Topk; i++)
78     findCalles(BBFreqs[i].first, Calles);
79 
80   assert(!Calles.empty() && "Running Analysis on Function with no calls?");
81 
82   CallerAndCalles.insert({F.getName(), std::move(Calles)});
83 
84   return CallerAndCalles;
85 }
86 } // namespace orc
87 } // namespace llvm
88