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
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
|
//===- PartialInlining.cpp - Inline parts of functions --------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass performs partial inlining, typically by inlining an if statement
// that surrounds the body of the function.
//
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/IPO/PartialInlining.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/BlockFrequencyInfo.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/Pass.h"
#include "llvm/Transforms/IPO.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/CodeExtractor.h"
using namespace llvm;
#define DEBUG_TYPE "partialinlining"
STATISTIC(NumPartialInlined, "Number of functions partially inlined");
namespace {
struct PartialInlinerImpl {
PartialInlinerImpl(InlineFunctionInfo IFI) : IFI(IFI) {}
bool run(Module &M);
Function *unswitchFunction(Function *F);
private:
InlineFunctionInfo IFI;
};
struct PartialInlinerLegacyPass : public ModulePass {
static char ID; // Pass identification, replacement for typeid
PartialInlinerLegacyPass() : ModulePass(ID) {
initializePartialInlinerLegacyPassPass(*PassRegistry::getPassRegistry());
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<AssumptionCacheTracker>();
}
bool runOnModule(Module &M) override {
if (skipModule(M))
return false;
AssumptionCacheTracker *ACT = &getAnalysis<AssumptionCacheTracker>();
std::function<AssumptionCache &(Function &)> GetAssumptionCache =
[&ACT](Function &F) -> AssumptionCache & {
return ACT->getAssumptionCache(F);
};
InlineFunctionInfo IFI(nullptr, &GetAssumptionCache);
return PartialInlinerImpl(IFI).run(M);
}
};
}
Function *PartialInlinerImpl::unswitchFunction(Function *F) {
// First, verify that this function is an unswitching candidate...
BasicBlock *EntryBlock = &F->front();
BranchInst *BR = dyn_cast<BranchInst>(EntryBlock->getTerminator());
if (!BR || BR->isUnconditional())
return nullptr;
BasicBlock *ReturnBlock = nullptr;
BasicBlock *NonReturnBlock = nullptr;
unsigned ReturnCount = 0;
for (BasicBlock *BB : successors(EntryBlock)) {
if (isa<ReturnInst>(BB->getTerminator())) {
ReturnBlock = BB;
ReturnCount++;
} else
NonReturnBlock = BB;
}
if (ReturnCount != 1)
return nullptr;
// Clone the function, so that we can hack away on it.
ValueToValueMapTy VMap;
Function *DuplicateFunction = CloneFunction(F, VMap);
DuplicateFunction->setLinkage(GlobalValue::InternalLinkage);
BasicBlock *NewEntryBlock = cast<BasicBlock>(VMap[EntryBlock]);
BasicBlock *NewReturnBlock = cast<BasicBlock>(VMap[ReturnBlock]);
BasicBlock *NewNonReturnBlock = cast<BasicBlock>(VMap[NonReturnBlock]);
// Go ahead and update all uses to the duplicate, so that we can just
// use the inliner functionality when we're done hacking.
F->replaceAllUsesWith(DuplicateFunction);
// Special hackery is needed with PHI nodes that have inputs from more than
// one extracted block. For simplicity, just split the PHIs into a two-level
// sequence of PHIs, some of which will go in the extracted region, and some
// of which will go outside.
BasicBlock *PreReturn = NewReturnBlock;
NewReturnBlock = NewReturnBlock->splitBasicBlock(
NewReturnBlock->getFirstNonPHI()->getIterator());
BasicBlock::iterator I = PreReturn->begin();
Instruction *Ins = &NewReturnBlock->front();
while (I != PreReturn->end()) {
PHINode *OldPhi = dyn_cast<PHINode>(I);
if (!OldPhi)
break;
PHINode *RetPhi = PHINode::Create(OldPhi->getType(), 2, "", Ins);
OldPhi->replaceAllUsesWith(RetPhi);
Ins = NewReturnBlock->getFirstNonPHI();
RetPhi->addIncoming(&*I, PreReturn);
RetPhi->addIncoming(OldPhi->getIncomingValueForBlock(NewEntryBlock),
NewEntryBlock);
OldPhi->removeIncomingValue(NewEntryBlock);
++I;
}
NewEntryBlock->getTerminator()->replaceUsesOfWith(PreReturn, NewReturnBlock);
// Gather up the blocks that we're going to extract.
std::vector<BasicBlock *> ToExtract;
ToExtract.push_back(NewNonReturnBlock);
for (BasicBlock &BB : *DuplicateFunction)
if (&BB != NewEntryBlock && &BB != NewReturnBlock &&
&BB != NewNonReturnBlock)
ToExtract.push_back(&BB);
// The CodeExtractor needs a dominator tree.
DominatorTree DT;
DT.recalculate(*DuplicateFunction);
// Manually calculate a BlockFrequencyInfo and BranchProbabilityInfo.
LoopInfo LI(DT);
BranchProbabilityInfo BPI(*DuplicateFunction, LI);
BlockFrequencyInfo BFI(*DuplicateFunction, BPI, LI);
// Extract the body of the if.
Function *ExtractedFunction =
CodeExtractor(ToExtract, &DT, /*AggregateArgs*/ false, &BFI, &BPI)
.extractCodeRegion();
// Inline the top-level if test into all callers.
std::vector<User *> Users(DuplicateFunction->user_begin(),
DuplicateFunction->user_end());
for (User *User : Users)
if (CallInst *CI = dyn_cast<CallInst>(User))
InlineFunction(CI, IFI);
else if (InvokeInst *II = dyn_cast<InvokeInst>(User))
InlineFunction(II, IFI);
// Ditch the duplicate, since we're done with it, and rewrite all remaining
// users (function pointers, etc.) back to the original function.
DuplicateFunction->replaceAllUsesWith(F);
DuplicateFunction->eraseFromParent();
++NumPartialInlined;
return ExtractedFunction;
}
bool PartialInlinerImpl::run(Module &M) {
std::vector<Function *> Worklist;
Worklist.reserve(M.size());
for (Function &F : M)
if (!F.use_empty() && !F.isDeclaration())
Worklist.push_back(&F);
bool Changed = false;
while (!Worklist.empty()) {
Function *CurrFunc = Worklist.back();
Worklist.pop_back();
if (CurrFunc->use_empty())
continue;
bool Recursive = false;
for (User *U : CurrFunc->users())
if (Instruction *I = dyn_cast<Instruction>(U))
if (I->getParent()->getParent() == CurrFunc) {
Recursive = true;
break;
}
if (Recursive)
continue;
if (Function *NewFunc = unswitchFunction(CurrFunc)) {
Worklist.push_back(NewFunc);
Changed = true;
}
}
return Changed;
}
char PartialInlinerLegacyPass::ID = 0;
INITIALIZE_PASS_BEGIN(PartialInlinerLegacyPass, "partial-inliner",
"Partial Inliner", false, false)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_PASS_END(PartialInlinerLegacyPass, "partial-inliner",
"Partial Inliner", false, false)
ModulePass *llvm::createPartialInliningPass() {
return new PartialInlinerLegacyPass();
}
PreservedAnalyses PartialInlinerPass::run(Module &M,
ModuleAnalysisManager &AM) {
auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
std::function<AssumptionCache &(Function &)> GetAssumptionCache =
[&FAM](Function &F) -> AssumptionCache & {
return FAM.getResult<AssumptionAnalysis>(F);
};
InlineFunctionInfo IFI(nullptr, &GetAssumptionCache);
if (PartialInlinerImpl(IFI).run(M))
return PreservedAnalyses::none();
return PreservedAnalyses::all();
}
|
