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 #include "llvm/Transforms/IPO/PartialInlining.h"
16 #include "llvm/ADT/Statistic.h"
17 #include "llvm/Analysis/BlockFrequencyInfo.h"
18 #include "llvm/Analysis/BranchProbabilityInfo.h"
19 #include "llvm/Analysis/LoopInfo.h"
20 #include "llvm/IR/CFG.h"
21 #include "llvm/IR/Dominators.h"
22 #include "llvm/IR/Instructions.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/Pass.h"
25 #include "llvm/Transforms/IPO.h"
26 #include "llvm/Transforms/Utils/Cloning.h"
27 #include "llvm/Transforms/Utils/CodeExtractor.h"
30 #define DEBUG_TYPE "partialinlining"
32 STATISTIC(NumPartialInlined, "Number of functions partially inlined");
35 struct PartialInlinerImpl {
36 PartialInlinerImpl(InlineFunctionInfo IFI) : IFI(IFI) {}
38 Function *unswitchFunction(Function *F);
41 InlineFunctionInfo IFI;
43 struct PartialInlinerLegacyPass : public ModulePass {
44 static char ID; // Pass identification, replacement for typeid
45 PartialInlinerLegacyPass() : ModulePass(ID) {
46 initializePartialInlinerLegacyPassPass(*PassRegistry::getPassRegistry());
49 void getAnalysisUsage(AnalysisUsage &AU) const override {
50 AU.addRequired<AssumptionCacheTracker>();
52 bool runOnModule(Module &M) override {
56 AssumptionCacheTracker *ACT = &getAnalysis<AssumptionCacheTracker>();
57 std::function<AssumptionCache &(Function &)> GetAssumptionCache =
58 [&ACT](Function &F) -> AssumptionCache & {
59 return ACT->getAssumptionCache(F);
61 InlineFunctionInfo IFI(nullptr, &GetAssumptionCache);
62 return PartialInlinerImpl(IFI).run(M);
67 Function *PartialInlinerImpl::unswitchFunction(Function *F) {
68 // First, verify that this function is an unswitching candidate...
69 BasicBlock *EntryBlock = &F->front();
70 BranchInst *BR = dyn_cast<BranchInst>(EntryBlock->getTerminator());
71 if (!BR || BR->isUnconditional())
74 BasicBlock *ReturnBlock = nullptr;
75 BasicBlock *NonReturnBlock = nullptr;
76 unsigned ReturnCount = 0;
77 for (BasicBlock *BB : successors(EntryBlock)) {
78 if (isa<ReturnInst>(BB->getTerminator())) {
88 // Clone the function, so that we can hack away on it.
89 ValueToValueMapTy VMap;
90 Function *DuplicateFunction = CloneFunction(F, VMap);
91 DuplicateFunction->setLinkage(GlobalValue::InternalLinkage);
92 BasicBlock *NewEntryBlock = cast<BasicBlock>(VMap[EntryBlock]);
93 BasicBlock *NewReturnBlock = cast<BasicBlock>(VMap[ReturnBlock]);
94 BasicBlock *NewNonReturnBlock = cast<BasicBlock>(VMap[NonReturnBlock]);
96 // Go ahead and update all uses to the duplicate, so that we can just
97 // use the inliner functionality when we're done hacking.
98 F->replaceAllUsesWith(DuplicateFunction);
100 // Special hackery is needed with PHI nodes that have inputs from more than
101 // one extracted block. For simplicity, just split the PHIs into a two-level
102 // sequence of PHIs, some of which will go in the extracted region, and some
103 // of which will go outside.
104 BasicBlock *PreReturn = NewReturnBlock;
105 NewReturnBlock = NewReturnBlock->splitBasicBlock(
106 NewReturnBlock->getFirstNonPHI()->getIterator());
107 BasicBlock::iterator I = PreReturn->begin();
108 Instruction *Ins = &NewReturnBlock->front();
109 while (I != PreReturn->end()) {
110 PHINode *OldPhi = dyn_cast<PHINode>(I);
114 PHINode *RetPhi = PHINode::Create(OldPhi->getType(), 2, "", Ins);
115 OldPhi->replaceAllUsesWith(RetPhi);
116 Ins = NewReturnBlock->getFirstNonPHI();
118 RetPhi->addIncoming(&*I, PreReturn);
119 RetPhi->addIncoming(OldPhi->getIncomingValueForBlock(NewEntryBlock),
121 OldPhi->removeIncomingValue(NewEntryBlock);
125 NewEntryBlock->getTerminator()->replaceUsesOfWith(PreReturn, NewReturnBlock);
127 // Gather up the blocks that we're going to extract.
128 std::vector<BasicBlock *> ToExtract;
129 ToExtract.push_back(NewNonReturnBlock);
130 for (BasicBlock &BB : *DuplicateFunction)
131 if (&BB != NewEntryBlock && &BB != NewReturnBlock &&
132 &BB != NewNonReturnBlock)
133 ToExtract.push_back(&BB);
135 // The CodeExtractor needs a dominator tree.
137 DT.recalculate(*DuplicateFunction);
139 // Manually calculate a BlockFrequencyInfo and BranchProbabilityInfo.
141 BranchProbabilityInfo BPI(*DuplicateFunction, LI);
142 BlockFrequencyInfo BFI(*DuplicateFunction, BPI, LI);
144 // Extract the body of the if.
145 Function *ExtractedFunction =
146 CodeExtractor(ToExtract, &DT, /*AggregateArgs*/ false, &BFI, &BPI)
147 .extractCodeRegion();
149 // Inline the top-level if test into all callers.
150 std::vector<User *> Users(DuplicateFunction->user_begin(),
151 DuplicateFunction->user_end());
152 for (User *User : Users)
153 if (CallInst *CI = dyn_cast<CallInst>(User))
154 InlineFunction(CI, IFI);
155 else if (InvokeInst *II = dyn_cast<InvokeInst>(User))
156 InlineFunction(II, IFI);
158 // Ditch the duplicate, since we're done with it, and rewrite all remaining
159 // users (function pointers, etc.) back to the original function.
160 DuplicateFunction->replaceAllUsesWith(F);
161 DuplicateFunction->eraseFromParent();
165 return ExtractedFunction;
168 bool PartialInlinerImpl::run(Module &M) {
169 std::vector<Function *> Worklist;
170 Worklist.reserve(M.size());
171 for (Function &F : M)
172 if (!F.use_empty() && !F.isDeclaration())
173 Worklist.push_back(&F);
175 bool Changed = false;
176 while (!Worklist.empty()) {
177 Function *CurrFunc = Worklist.back();
180 if (CurrFunc->use_empty())
183 bool Recursive = false;
184 for (User *U : CurrFunc->users())
185 if (Instruction *I = dyn_cast<Instruction>(U))
186 if (I->getParent()->getParent() == CurrFunc) {
193 if (Function *NewFunc = unswitchFunction(CurrFunc)) {
194 Worklist.push_back(NewFunc);
202 char PartialInlinerLegacyPass::ID = 0;
203 INITIALIZE_PASS_BEGIN(PartialInlinerLegacyPass, "partial-inliner",
204 "Partial Inliner", false, false)
205 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
206 INITIALIZE_PASS_END(PartialInlinerLegacyPass, "partial-inliner",
207 "Partial Inliner", false, false)
209 ModulePass *llvm::createPartialInliningPass() {
210 return new PartialInlinerLegacyPass();
213 PreservedAnalyses PartialInlinerPass::run(Module &M,
214 ModuleAnalysisManager &AM) {
215 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
216 std::function<AssumptionCache &(Function &)> GetAssumptionCache =
217 [&FAM](Function &F) -> AssumptionCache & {
218 return FAM.getResult<AssumptionAnalysis>(F);
220 InlineFunctionInfo IFI(nullptr, &GetAssumptionCache);
221 if (PartialInlinerImpl(IFI).run(M))
222 return PreservedAnalyses::none();
223 return PreservedAnalyses::all();