|
147
|
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
|
