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