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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
|
//===- InlineCommon.cpp - Code common to all inliners ---------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the code shared between the LLVM inliners. This
// implements all of the boring mechanics of the bottom-up inlining.
//
//===----------------------------------------------------------------------===//
#include "Inliner.h"
#include "llvm/Constants.h" // ConstantPointerRef should die
#include "llvm/Module.h"
#include "llvm/iOther.h"
#include "llvm/iTerminators.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "Support/CommandLine.h"
#include "Support/Debug.h"
#include "Support/Statistic.h"
using namespace llvm;
namespace {
Statistic<> NumInlined("inline", "Number of functions inlined");
Statistic<> NumDeleted("inline", "Number of functions deleted because all callers found");
cl::opt<unsigned> // FIXME: 200 is VERY conservative
InlineLimit("inline-threshold", cl::Hidden, cl::init(200),
cl::desc("Control the amount of inlining to perform (default = 200)"));
}
Inliner::Inliner() : InlineThreshold(InlineLimit) {}
int Inliner::getRecursiveInlineCost(CallSite CS) {
return getInlineCost(CS);
}
bool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) {
CallGraph &CG = getAnalysis<CallGraph>();
std::set<Function*> SCCFunctions;
DEBUG(std::cerr << "Inliner visiting SCC:");
for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
SCCFunctions.insert(SCC[i]->getFunction());
DEBUG(std::cerr << " " << (SCC[i]->getFunction() ?
SCC[i]->getFunction()->getName() : "INDIRECTNODE"));
}
DEBUG(std::cerr << "\n");
bool Changed = false;
for (std::set<Function*>::iterator SCCI = SCCFunctions.begin(),
E = SCCFunctions.end(); SCCI != E; ++SCCI) {
Function *F = *SCCI;
if (F == 0 || F->isExternal()) continue;
DEBUG(std::cerr << " Inspecting function: " << F->getName() << "\n");
// Scan through and identify all call sites ahead of time so that we only
// inline call sites in the original functions, not call sites that result
// in inlining other functions.
std::vector<CallSite> CallSites;
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
CallSite CS = CallSite::get(I);
if (CS.getInstruction() && CS.getCalledFunction() &&
!CS.getCalledFunction()->isExternal())
CallSites.push_back(CS);
}
// Now that we have all of the call sites, loop over them and inline them if
// it looks profitable to do so.
for (unsigned i = 0, e = CallSites.size(); i != e; ++i) {
CallSite CS = CallSites[i];
Function *Callee = CS.getCalledFunction();
// Determine whether this is a function IN the SCC...
bool inSCC = SCCFunctions.count(Callee);
// If the policy determines that we should inline this function,
// try to do so...
int InlineCost = inSCC ? getRecursiveInlineCost(CS) : getInlineCost(CS);
if (InlineCost >= (int)InlineThreshold) {
DEBUG(std::cerr << " NOT Inlining: cost=" << InlineCost
<< ", Call: " << *CS.getInstruction());
} else {
DEBUG(std::cerr << " Inlining: cost=" << InlineCost
<< ", Call: " << *CS.getInstruction());
Function *Caller = CS.getInstruction()->getParent()->getParent();
// Attempt to inline the function...
if (InlineFunction(CS)) {
++NumInlined;
// Update the call graph by deleting the edge from Callee to Caller
CallGraphNode *CalleeNode = CG[Callee];
CallGraphNode *CallerNode = CG[Caller];
CallerNode->removeCallEdgeTo(CalleeNode);
// Since we inlined all uninlinable call sites in the callee into the
// caller, add edges from the caller to all of the callees of the
// callee.
for (CallGraphNode::iterator I = CalleeNode->begin(),
E = CalleeNode->end(); I != E; ++I)
CallerNode->addCalledFunction(*I);
// If we inlined the last possible call site to the function,
// delete the function body now.
if (Callee->use_empty() && Callee != Caller &&
Callee->hasInternalLinkage()) {
DEBUG(std::cerr << " -> Deleting dead function: "
<< Callee->getName() << "\n");
SCCFunctions.erase(Callee); // Remove function from this SCC.
// Remove any call graph edges from the callee to its callees.
while (CalleeNode->begin() != CalleeNode->end())
CalleeNode->removeCallEdgeTo(*(CalleeNode->end()-1));
// Removing the node for callee from the call graph and delete it.
delete CG.removeFunctionFromModule(CalleeNode);
++NumDeleted;
}
Changed = true;
}
}
}
}
return Changed;
}
// doFinalization - Remove now-dead linkonce functions at the end of
// processing to avoid breaking the SCC traversal.
bool Inliner::doFinalization(CallGraph &CG) {
std::set<CallGraphNode*> FunctionsToRemove;
// Scan for all of the functions, looking for ones that should now be removed
// from the program. Insert the dead ones in the FunctionsToRemove set.
for (CallGraph::iterator I = CG.begin(), E = CG.end(); I != E; ++I) {
CallGraphNode *CGN = I->second;
Function *F = CGN ? CGN->getFunction() : 0;
// If the only remaining use of the function is a dead constant
// pointer ref, remove it.
if (F && F->hasOneUse())
if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(F->use_back()))
if (CPR->use_empty()) {
CPR->destroyConstant();
if (F->hasInternalLinkage()) {
// There *MAY* be an edge from the external call node to this
// function. If so, remove it.
CallGraphNode *EN = CG.getExternalCallingNode();
CallGraphNode::iterator I = std::find(EN->begin(), EN->end(), CGN);
if (I != EN->end()) EN->removeCallEdgeTo(CGN);
}
}
if (F && (F->hasLinkOnceLinkage() || F->hasInternalLinkage()) &&
F->use_empty()) {
// Remove any call graph edges from the function to its callees.
while (CGN->begin() != CGN->end())
CGN->removeCallEdgeTo(*(CGN->end()-1));
// If the function has external linkage (basically if it's a linkonce
// function) remove the edge from the external node to the callee node.
if (!F->hasInternalLinkage())
CG.getExternalCallingNode()->removeCallEdgeTo(CGN);
// Removing the node for callee from the call graph and delete it.
FunctionsToRemove.insert(CGN);
}
}
// Now that we know which functions to delete, do so. We didn't want to do
// this inline, because that would invalidate our CallGraph::iterator
// objects. :(
bool Changed = false;
for (std::set<CallGraphNode*>::iterator I = FunctionsToRemove.begin(),
E = FunctionsToRemove.end(); I != E; ++I) {
delete CG.removeFunctionFromModule(*I);
++NumDeleted;
Changed = true;
}
return Changed;
}
|
