blob: 1186c3e617fff103621c03f152a3e1a2e8f9ae79 [file] [log] [blame]
Chris Lattnerd075cc22003-08-31 19:10:30 +00001//===- InlineCommon.cpp - Code common to all inliners ---------------------===//
John Criswell482202a2003-10-20 19:43:21 +00002//
3// The LLVM Compiler Infrastructure
4//
5// This file was developed by the LLVM research group and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
Chris Lattnerd075cc22003-08-31 19:10:30 +00009//
Chris Lattner6754b822004-05-23 21:22:17 +000010// This file implements the mechanics required to implement inlining without
11// missing any calls and updating the call graph. The decisions of which calls
12// are profitable to inline are implemented elsewhere.
Chris Lattnerd075cc22003-08-31 19:10:30 +000013//
14//===----------------------------------------------------------------------===//
15
16#include "Inliner.h"
Chris Lattnerb45d9072003-10-31 21:05:58 +000017#include "llvm/Constants.h" // ConstantPointerRef should die
Chris Lattnerd075cc22003-08-31 19:10:30 +000018#include "llvm/Module.h"
19#include "llvm/iOther.h"
20#include "llvm/iTerminators.h"
21#include "llvm/Analysis/CallGraph.h"
22#include "llvm/Support/CallSite.h"
23#include "llvm/Transforms/Utils/Cloning.h"
24#include "Support/CommandLine.h"
25#include "Support/Debug.h"
26#include "Support/Statistic.h"
Chris Lattner6754b822004-05-23 21:22:17 +000027#include <set>
Chris Lattnera82f1312003-11-21 21:45:31 +000028using namespace llvm;
Brian Gaeke960707c2003-11-11 22:41:34 +000029
Chris Lattnerd075cc22003-08-31 19:10:30 +000030namespace {
31 Statistic<> NumInlined("inline", "Number of functions inlined");
32 Statistic<> NumDeleted("inline", "Number of functions deleted because all callers found");
33 cl::opt<unsigned> // FIXME: 200 is VERY conservative
34 InlineLimit("inline-threshold", cl::Hidden, cl::init(200),
35 cl::desc("Control the amount of inlining to perform (default = 200)"));
36}
37
38Inliner::Inliner() : InlineThreshold(InlineLimit) {}
39
Chris Lattner6754b822004-05-23 21:22:17 +000040// InlineCallIfPossible - If it is possible to inline the specified call site,
41// do so and update the CallGraph for this operation.
42static bool InlineCallIfPossible(CallSite CS, CallGraph &CG,
43 const std::set<Function*> &SCCFunctions) {
44 Function *Caller = CS.getInstruction()->getParent()->getParent();
45 Function *Callee = CS.getCalledFunction();
46 if (!InlineFunction(CS)) return false;
47
48 // Update the call graph by deleting the edge from Callee to Caller
49 CallGraphNode *CalleeNode = CG[Callee];
50 CallGraphNode *CallerNode = CG[Caller];
51 CallerNode->removeCallEdgeTo(CalleeNode);
52
53 // Since we inlined all uninlined call sites in the callee into the caller,
54 // add edges from the caller to all of the callees of the callee.
55 for (CallGraphNode::iterator I = CalleeNode->begin(),
56 E = CalleeNode->end(); I != E; ++I)
57 CallerNode->addCalledFunction(*I);
58
59 // If we inlined the last possible call site to the function,
60 // delete the function body now.
61 if (Callee->use_empty() && Callee->hasInternalLinkage() &&
62 !SCCFunctions.count(Callee)) {
63 DEBUG(std::cerr << " -> Deleting dead function: "
64 << Callee->getName() << "\n");
65
66 // Remove any call graph edges from the callee to its callees.
67 while (CalleeNode->begin() != CalleeNode->end())
68 CalleeNode->removeCallEdgeTo(*(CalleeNode->end()-1));
69
70 // Removing the node for callee from the call graph and delete it.
71 delete CG.removeFunctionFromModule(CalleeNode);
72 ++NumDeleted;
73 }
74 return true;
Chris Lattnerd075cc22003-08-31 19:10:30 +000075}
76
77bool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) {
78 CallGraph &CG = getAnalysis<CallGraph>();
79
80 std::set<Function*> SCCFunctions;
81 DEBUG(std::cerr << "Inliner visiting SCC:");
82 for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
Chris Lattner6754b822004-05-23 21:22:17 +000083 Function *F = SCC[i]->getFunction();
84 if (F) SCCFunctions.insert(F);
85 DEBUG(std::cerr << " " << (F ? F->getName() : "INDIRECTNODE"));
Chris Lattnerd075cc22003-08-31 19:10:30 +000086 }
Chris Lattnerd075cc22003-08-31 19:10:30 +000087
Chris Lattner6754b822004-05-23 21:22:17 +000088 // Scan through and identify all call sites ahead of time so that we only
89 // inline call sites in the original functions, not call sites that result
90 // from inlining other functions.
91 std::vector<CallSite> CallSites;
92
Chris Lattnerd075cc22003-08-31 19:10:30 +000093 for (std::set<Function*>::iterator SCCI = SCCFunctions.begin(),
Chris Lattner6754b822004-05-23 21:22:17 +000094 E = SCCFunctions.end(); SCCI != E; ++SCCI)
95 if (Function *F = *SCCI)
96 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
97 for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
98 CallSite CS = CallSite::get(I);
99 if (CS.getInstruction() && (!CS.getCalledFunction() ||
100 !CS.getCalledFunction()->isExternal()))
101 CallSites.push_back(CS);
102 }
Chris Lattnerd075cc22003-08-31 19:10:30 +0000103
Chris Lattner6754b822004-05-23 21:22:17 +0000104 DEBUG(std::cerr << ": " << CallSites.size() << " call sites.\n");
105
106 // Now that we have all of the call sites, move the ones to functions in the
107 // current SCC to the end of the list.
108 unsigned FirstCallInSCC = CallSites.size();
109 for (unsigned i = 0; i < FirstCallInSCC; ++i)
110 if (Function *F = CallSites[i].getCalledFunction())
111 if (SCCFunctions.count(F))
112 std::swap(CallSites[i--], CallSites[--FirstCallInSCC]);
113
114 // Now that we have all of the call sites, loop over them and inline them if
115 // it looks profitable to do so.
116 bool Changed = false;
117 bool LocalChange;
118 do {
119 LocalChange = false;
120 // Iterate over the outer loop because inlining functions can cause indirect
121 // calls to become direct calls.
122 for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi)
123 if (Function *Callee = CallSites[CSi].getCalledFunction()) {
124 // Calls to external functions are never inlinable.
125 if (Callee->isExternal() ||
126 CallSites[CSi].getInstruction()->getParent()->getParent() ==Callee){
127 std::swap(CallSites[CSi], CallSites.back());
128 --CSi;
129 continue;
130 }
Chris Lattner4d25c862004-04-08 06:34:31 +0000131
Chris Lattner6754b822004-05-23 21:22:17 +0000132 // If the policy determines that we should inline this function,
133 // try to do so.
134 CallSite CS = CallSites[CSi];
135 int InlineCost = getInlineCost(CS);
136 if (InlineCost >= (int)InlineThreshold) {
137 DEBUG(std::cerr << " NOT Inlining: cost=" << InlineCost
138 << ", Call: " << *CS.getInstruction());
139 } else {
140 DEBUG(std::cerr << " Inlining: cost=" << InlineCost
141 << ", Call: " << *CS.getInstruction());
142
143 Function *Caller = CS.getInstruction()->getParent()->getParent();
Chris Lattner4d25c862004-04-08 06:34:31 +0000144
Chris Lattner6754b822004-05-23 21:22:17 +0000145 // Attempt to inline the function...
146 if (InlineCallIfPossible(CS, CG, SCCFunctions)) {
147 // Remove this call site from the list.
148 std::swap(CallSites[CSi], CallSites.back());
149 CallSites.pop_back();
150 --CSi;
Chris Lattnerbe435442004-04-12 05:37:29 +0000151
Chris Lattner6754b822004-05-23 21:22:17 +0000152 ++NumInlined;
153 Changed = true;
154 LocalChange = true;
Chris Lattner4d25c862004-04-08 06:34:31 +0000155 }
Chris Lattner4d25c862004-04-08 06:34:31 +0000156 }
157 }
Chris Lattner6754b822004-05-23 21:22:17 +0000158 } while (LocalChange);
Chris Lattner4d25c862004-04-08 06:34:31 +0000159
Chris Lattnerd075cc22003-08-31 19:10:30 +0000160 return Changed;
161}
162
Chris Lattnerc87784f2004-04-20 22:06:53 +0000163// doFinalization - Remove now-dead linkonce functions at the end of
164// processing to avoid breaking the SCC traversal.
165bool Inliner::doFinalization(CallGraph &CG) {
Chris Lattnerbe8bb802004-04-21 20:44:33 +0000166 std::set<CallGraphNode*> FunctionsToRemove;
167
168 // Scan for all of the functions, looking for ones that should now be removed
169 // from the program. Insert the dead ones in the FunctionsToRemove set.
170 for (CallGraph::iterator I = CG.begin(), E = CG.end(); I != E; ++I) {
171 CallGraphNode *CGN = I->second;
Chris Lattnerc87784f2004-04-20 22:06:53 +0000172 Function *F = CGN ? CGN->getFunction() : 0;
Chris Lattnerbe8bb802004-04-21 20:44:33 +0000173
174 // If the only remaining use of the function is a dead constant
175 // pointer ref, remove it.
176 if (F && F->hasOneUse())
177 if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(F->use_back()))
178 if (CPR->use_empty()) {
179 CPR->destroyConstant();
180 if (F->hasInternalLinkage()) {
181 // There *MAY* be an edge from the external call node to this
182 // function. If so, remove it.
183 CallGraphNode *EN = CG.getExternalCallingNode();
184 CallGraphNode::iterator I = std::find(EN->begin(), EN->end(), CGN);
185 if (I != EN->end()) EN->removeCallEdgeTo(CGN);
186 }
187 }
188
Chris Lattnerc87784f2004-04-20 22:06:53 +0000189 if (F && (F->hasLinkOnceLinkage() || F->hasInternalLinkage()) &&
190 F->use_empty()) {
Chris Lattnerbe8bb802004-04-21 20:44:33 +0000191 // Remove any call graph edges from the function to its callees.
Chris Lattnerc87784f2004-04-20 22:06:53 +0000192 while (CGN->begin() != CGN->end())
193 CGN->removeCallEdgeTo(*(CGN->end()-1));
194
Chris Lattnerbe8bb802004-04-21 20:44:33 +0000195 // If the function has external linkage (basically if it's a linkonce
196 // function) remove the edge from the external node to the callee node.
Chris Lattnerc87784f2004-04-20 22:06:53 +0000197 if (!F->hasInternalLinkage())
198 CG.getExternalCallingNode()->removeCallEdgeTo(CGN);
199
200 // Removing the node for callee from the call graph and delete it.
Chris Lattnerbe8bb802004-04-21 20:44:33 +0000201 FunctionsToRemove.insert(CGN);
Chris Lattnerc87784f2004-04-20 22:06:53 +0000202 }
203 }
Chris Lattnerbe8bb802004-04-21 20:44:33 +0000204
205 // Now that we know which functions to delete, do so. We didn't want to do
206 // this inline, because that would invalidate our CallGraph::iterator
207 // objects. :(
208 bool Changed = false;
209 for (std::set<CallGraphNode*>::iterator I = FunctionsToRemove.begin(),
210 E = FunctionsToRemove.end(); I != E; ++I) {
211 delete CG.removeFunctionFromModule(*I);
212 ++NumDeleted;
213 Changed = true;
214 }
215
Chris Lattnerc87784f2004-04-20 22:06:53 +0000216 return Changed;
217}