1 //===- PartialInlining.cpp - Inline parts of functions --------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass performs partial inlining, typically by inlining an if statement
11 // that surrounds the body of the function.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "partialinlining"
16 #include "llvm/Transforms/IPO.h"
17 #include "llvm/Instructions.h"
18 #include "llvm/Module.h"
19 #include "llvm/Pass.h"
20 #include "llvm/Analysis/Dominators.h"
21 #include "llvm/Transforms/Utils/Cloning.h"
22 #include "llvm/Transforms/Utils/FunctionUtils.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/Support/CFG.h"
27 STATISTIC(NumPartialInlined
, "Number of functions partially inlined");
30 struct PartialInliner
: public ModulePass
{
31 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const { }
32 static char ID
; // Pass identification, replacement for typeid
33 PartialInliner() : ModulePass(ID
) {}
35 bool runOnModule(Module
& M
);
38 Function
* unswitchFunction(Function
* F
);
42 char PartialInliner::ID
= 0;
43 INITIALIZE_PASS(PartialInliner
, "partial-inliner",
44 "Partial Inliner", false, false);
46 ModulePass
* llvm::createPartialInliningPass() { return new PartialInliner(); }
48 Function
* PartialInliner::unswitchFunction(Function
* F
) {
49 // First, verify that this function is an unswitching candidate...
50 BasicBlock
* entryBlock
= F
->begin();
51 BranchInst
*BR
= dyn_cast
<BranchInst
>(entryBlock
->getTerminator());
52 if (!BR
|| BR
->isUnconditional())
55 BasicBlock
* returnBlock
= 0;
56 BasicBlock
* nonReturnBlock
= 0;
57 unsigned returnCount
= 0;
58 for (succ_iterator SI
= succ_begin(entryBlock
), SE
= succ_end(entryBlock
);
60 if (isa
<ReturnInst
>((*SI
)->getTerminator())) {
69 // Clone the function, so that we can hack away on it.
70 ValueMap
<const Value
*, Value
*> VMap
;
71 Function
* duplicateFunction
= CloneFunction(F
, VMap
);
72 duplicateFunction
->setLinkage(GlobalValue::InternalLinkage
);
73 F
->getParent()->getFunctionList().push_back(duplicateFunction
);
74 BasicBlock
* newEntryBlock
= cast
<BasicBlock
>(VMap
[entryBlock
]);
75 BasicBlock
* newReturnBlock
= cast
<BasicBlock
>(VMap
[returnBlock
]);
76 BasicBlock
* newNonReturnBlock
= cast
<BasicBlock
>(VMap
[nonReturnBlock
]);
78 // Go ahead and update all uses to the duplicate, so that we can just
79 // use the inliner functionality when we're done hacking.
80 F
->replaceAllUsesWith(duplicateFunction
);
82 // Special hackery is needed with PHI nodes that have inputs from more than
83 // one extracted block. For simplicity, just split the PHIs into a two-level
84 // sequence of PHIs, some of which will go in the extracted region, and some
85 // of which will go outside.
86 BasicBlock
* preReturn
= newReturnBlock
;
87 newReturnBlock
= newReturnBlock
->splitBasicBlock(
88 newReturnBlock
->getFirstNonPHI());
89 BasicBlock::iterator I
= preReturn
->begin();
90 BasicBlock::iterator Ins
= newReturnBlock
->begin();
91 while (I
!= preReturn
->end()) {
92 PHINode
* OldPhi
= dyn_cast
<PHINode
>(I
);
95 PHINode
* retPhi
= PHINode::Create(OldPhi
->getType(), "", Ins
);
96 OldPhi
->replaceAllUsesWith(retPhi
);
97 Ins
= newReturnBlock
->getFirstNonPHI();
99 retPhi
->addIncoming(I
, preReturn
);
100 retPhi
->addIncoming(OldPhi
->getIncomingValueForBlock(newEntryBlock
),
102 OldPhi
->removeIncomingValue(newEntryBlock
);
106 newEntryBlock
->getTerminator()->replaceUsesOfWith(preReturn
, newReturnBlock
);
108 // Gather up the blocks that we're going to extract.
109 std::vector
<BasicBlock
*> toExtract
;
110 toExtract
.push_back(newNonReturnBlock
);
111 for (Function::iterator FI
= duplicateFunction
->begin(),
112 FE
= duplicateFunction
->end(); FI
!= FE
; ++FI
)
113 if (&*FI
!= newEntryBlock
&& &*FI
!= newReturnBlock
&&
114 &*FI
!= newNonReturnBlock
)
115 toExtract
.push_back(FI
);
117 // The CodeExtractor needs a dominator tree.
119 DT
.runOnFunction(*duplicateFunction
);
121 // Extract the body of the if.
122 Function
* extractedFunction
= ExtractCodeRegion(DT
, toExtract
);
124 InlineFunctionInfo IFI
;
126 // Inline the top-level if test into all callers.
127 std::vector
<User
*> Users(duplicateFunction
->use_begin(),
128 duplicateFunction
->use_end());
129 for (std::vector
<User
*>::iterator UI
= Users
.begin(), UE
= Users
.end();
131 if (CallInst
*CI
= dyn_cast
<CallInst
>(*UI
))
132 InlineFunction(CI
, IFI
);
133 else if (InvokeInst
*II
= dyn_cast
<InvokeInst
>(*UI
))
134 InlineFunction(II
, IFI
);
136 // Ditch the duplicate, since we're done with it, and rewrite all remaining
137 // users (function pointers, etc.) back to the original function.
138 duplicateFunction
->replaceAllUsesWith(F
);
139 duplicateFunction
->eraseFromParent();
143 return extractedFunction
;
146 bool PartialInliner::runOnModule(Module
& M
) {
147 std::vector
<Function
*> worklist
;
148 worklist
.reserve(M
.size());
149 for (Module::iterator FI
= M
.begin(), FE
= M
.end(); FI
!= FE
; ++FI
)
150 if (!FI
->use_empty() && !FI
->isDeclaration())
151 worklist
.push_back(&*FI
);
153 bool changed
= false;
154 while (!worklist
.empty()) {
155 Function
* currFunc
= worklist
.back();
158 if (currFunc
->use_empty()) continue;
160 bool recursive
= false;
161 for (Function::use_iterator UI
= currFunc
->use_begin(),
162 UE
= currFunc
->use_end(); UI
!= UE
; ++UI
)
163 if (Instruction
* I
= dyn_cast
<Instruction
>(*UI
))
164 if (I
->getParent()->getParent() == currFunc
) {
168 if (recursive
) continue;
171 if (Function
* newFunc
= unswitchFunction(currFunc
)) {
172 worklist
.push_back(newFunc
);