/
FunctionPropertiesAnalysis.cpp
173 lines (151 loc) · 6.29 KB
/
FunctionPropertiesAnalysis.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
//===- FunctionPropertiesAnalysis.cpp - Function Properties Analysis ------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines the FunctionPropertiesInfo and FunctionPropertiesAnalysis
// classes used to extract function properties.
//
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/FunctionPropertiesAnalysis.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Instructions.h"
#include <deque>
using namespace llvm;
namespace {
int64_t getNrBlocksFromCond(const BasicBlock &BB) {
int64_t Ret = 0;
if (const auto *BI = dyn_cast<BranchInst>(BB.getTerminator())) {
if (BI->isConditional())
Ret += BI->getNumSuccessors();
} else if (const auto *SI = dyn_cast<SwitchInst>(BB.getTerminator())) {
Ret += (SI->getNumCases() + (nullptr != SI->getDefaultDest()));
}
return Ret;
}
int64_t getUses(const Function &F) {
return ((!F.hasLocalLinkage()) ? 1 : 0) + F.getNumUses();
}
} // namespace
void FunctionPropertiesInfo::reIncludeBB(const BasicBlock &BB,
const LoopInfo &LI) {
updateForBB(BB, +1);
MaxLoopDepth =
std::max(MaxLoopDepth, static_cast<int64_t>(LI.getLoopDepth(&BB)));
}
void FunctionPropertiesInfo::updateForBB(const BasicBlock &BB,
int64_t Direction) {
assert(Direction == 1 || Direction == -1);
BasicBlockCount += Direction;
BlocksReachedFromConditionalInstruction +=
(Direction * getNrBlocksFromCond(BB));
for (const auto &I : BB) {
if (auto *CS = dyn_cast<CallBase>(&I)) {
const auto *Callee = CS->getCalledFunction();
if (Callee && !Callee->isIntrinsic() && !Callee->isDeclaration())
DirectCallsToDefinedFunctions += Direction;
}
if (I.getOpcode() == Instruction::Load) {
LoadInstCount += Direction;
} else if (I.getOpcode() == Instruction::Store) {
StoreInstCount += Direction;
}
}
TotalInstructionCount += Direction * BB.sizeWithoutDebug();
}
void FunctionPropertiesInfo::updateAggregateStats(const Function &F,
const LoopInfo &LI) {
Uses = getUses(F);
TopLevelLoopCount = llvm::size(LI);
}
FunctionPropertiesInfo
FunctionPropertiesInfo::getFunctionPropertiesInfo(const Function &F,
const LoopInfo &LI) {
FunctionPropertiesInfo FPI;
for (const auto &BB : F)
if (!pred_empty(&BB) || BB.isEntryBlock())
FPI.reIncludeBB(BB, LI);
FPI.updateAggregateStats(F, LI);
return FPI;
}
void FunctionPropertiesInfo::print(raw_ostream &OS) const {
OS << "BasicBlockCount: " << BasicBlockCount << "\n"
<< "BlocksReachedFromConditionalInstruction: "
<< BlocksReachedFromConditionalInstruction << "\n"
<< "Uses: " << Uses << "\n"
<< "DirectCallsToDefinedFunctions: " << DirectCallsToDefinedFunctions
<< "\n"
<< "LoadInstCount: " << LoadInstCount << "\n"
<< "StoreInstCount: " << StoreInstCount << "\n"
<< "MaxLoopDepth: " << MaxLoopDepth << "\n"
<< "TopLevelLoopCount: " << TopLevelLoopCount << "\n"
<< "TotalInstructionCount: " << TotalInstructionCount << "\n\n";
}
AnalysisKey FunctionPropertiesAnalysis::Key;
FunctionPropertiesInfo
FunctionPropertiesAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
return FunctionPropertiesInfo::getFunctionPropertiesInfo(
F, FAM.getResult<LoopAnalysis>(F));
}
PreservedAnalyses
FunctionPropertiesPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
OS << "Printing analysis results of CFA for function "
<< "'" << F.getName() << "':"
<< "\n";
AM.getResult<FunctionPropertiesAnalysis>(F).print(OS);
return PreservedAnalyses::all();
}
FunctionPropertiesUpdater::FunctionPropertiesUpdater(
FunctionPropertiesInfo &FPI, const CallBase &CB)
: FPI(FPI), CallSiteBB(*CB.getParent()), Caller(*CallSiteBB.getParent()) {
// For BBs that are likely to change, we subtract from feature totals their
// contribution. Some features, like max loop counts or depths, are left
// invalid, as they will be updated post-inlining.
SmallPtrSet<const BasicBlock *, 4> LikelyToChangeBBs;
// The CB BB will change - it'll either be split or the callee's body (single
// BB) will be pasted in.
LikelyToChangeBBs.insert(&CallSiteBB);
// The caller's entry BB may change due to new alloca instructions.
LikelyToChangeBBs.insert(&*Caller.begin());
// The successors may become unreachable in the case of `invoke` inlining.
// We track successors separately, too, because they form a boundary, together
// with the CB BB ('Entry') between which the inlined callee will be pasted.
Successors.insert(succ_begin(&CallSiteBB), succ_end(&CallSiteBB));
for (const auto *BB : Successors)
LikelyToChangeBBs.insert(BB);
// Commit the change. While some of the BBs accounted for above may play dual
// role - e.g. caller's entry BB may be the same as the callsite BB - set
// insertion semantics make sure we account them once. This needs to be
// followed in `finish`, too.
for (const auto *BB : LikelyToChangeBBs)
FPI.updateForBB(*BB, -1);
}
void FunctionPropertiesUpdater::finish(const LoopInfo &LI) {
DenseSet<const BasicBlock *> ReIncluded;
std::deque<const BasicBlock *> Worklist;
if (&CallSiteBB != &*Caller.begin()) {
FPI.reIncludeBB(*Caller.begin(), LI);
ReIncluded.insert(&*Caller.begin());
}
// Update feature values from the BBs that were copied from the callee, or
// might have been modified because of inlining. The latter have been
// subtracted in the FunctionPropertiesUpdater ctor.
Worklist.push_back(&CallSiteBB);
while (!Worklist.empty()) {
const auto *BB = Worklist.front();
Worklist.pop_front();
if (!ReIncluded.insert(BB).second)
continue;
FPI.reIncludeBB(*BB, LI);
if (!Successors.contains(BB))
for (const auto *Succ : successors(BB))
Worklist.push_back(Succ);
}
FPI.updateAggregateStats(Caller, LI);
assert(FPI == FunctionPropertiesInfo::getFunctionPropertiesInfo(Caller, LI));
}