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
|
//===- 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");
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
bool ShouldInc = true;
// Found a call or invoke instruction?
if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
CallSite CS = CallSite::get(I);
if (Function *Callee = CS.getCalledFunction())
if (!Callee->isExternal() && !IsRecursiveFunction.count(Callee)) {
// Determine whether this is a function IN the SCC...
bool inSCC = SCCFunctions.count(Callee);
// Keep track of whether this is a directly recursive function.
if (Callee == F) IsRecursiveFunction.insert(F);
// 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());
// Save an iterator to the instruction before the call if it
// exists, otherwise get an iterator at the end of the
// block... because the call will be destroyed.
//
BasicBlock::iterator SI;
if (I != BB->begin()) {
SI = I; --SI; // Instruction before the call...
} else {
SI = BB->end();
}
if (performInlining(CS, SCCFunctions)) {
// Move to instruction before the call...
I = (SI == BB->end()) ? BB->begin() : SI;
ShouldInc = false; // Don't increment iterator until next time
Changed = true;
}
}
}
}
if (ShouldInc) ++I;
}
}
return Changed;
}
bool Inliner::performInlining(CallSite CS, std::set<Function*> &SCC) {
Function *Callee = CS.getCalledFunction();
Function *Caller = CS.getInstruction()->getParent()->getParent();
// Attempt to inline the function...
if (!InlineFunction(CS)) return false;
++NumInlined;
if (Callee->hasOneUse())
if (ConstantPointerRef *CPR =
dyn_cast<ConstantPointerRef>(Callee->use_back()))
if (CPR->use_empty())
CPR->destroyConstant();
// If we inlined the last possible call site to the function,
// delete the function body now.
if (Callee->use_empty() && Callee != Caller &&
(Callee->hasInternalLinkage() || Callee->hasLinkOnceLinkage())) {
DEBUG(std::cerr << " -> Deleting dead function: " << (void*)Callee
<< Callee->getName() << "\n");
std::set<Function*>::iterator I = SCC.find(Callee);
if (I != SCC.end()) // Remove function from this SCC...
SCC.erase(I);
Callee->getParent()->getFunctionList().erase(Callee);
++NumDeleted;
}
return true;
}
|
