From ca399021d47d640551eb786620bcd108e1758485 Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Sun, 14 Jun 2009 08:26:32 +0000 Subject: [PATCH] Add an early implementation of a partial inlining pass. The idea behind this is that, for functions whose bodies are entirely guarded by an if-statement, it can be profitable to pull the test out of the callee and into the caller. This code has had some cursory testing, but still has a number of known issues on the LLVM test suite. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73338 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/LinkAllPasses.h | 1 + include/llvm/Transforms/IPO.h | 5 + lib/Transforms/IPO/PartialInlining.cpp | 171 +++++++++++++++++++++++++++++++++ 3 files changed, 177 insertions(+) create mode 100644 lib/Transforms/IPO/PartialInlining.cpp diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h index edd27223aa8..0fb837da772 100644 --- a/include/llvm/LinkAllPasses.h +++ b/include/llvm/LinkAllPasses.h @@ -127,6 +127,7 @@ namespace { (void) llvm::createPrintModulePass(0); (void) llvm::createPrintFunctionPass("", 0); (void) llvm::createDbgInfoPrinterPass(); + (void) llvm::createPartialInliningPass(); (void)new llvm::IntervalPartition(); (void)new llvm::FindUsedTypes(); diff --git a/include/llvm/Transforms/IPO.h b/include/llvm/Transforms/IPO.h index 4372ea00d42..750969b36eb 100644 --- a/include/llvm/Transforms/IPO.h +++ b/include/llvm/Transforms/IPO.h @@ -214,6 +214,11 @@ Pass *createFunctionAttrsPass(); /// ModulePass *createMergeFunctionsPass(); +//===----------------------------------------------------------------------===// +/// createPartialInliningPass - This pass inlines parts of functions. +/// +ModulePass *createPartialInliningPass(); + } // End llvm namespace #endif diff --git a/lib/Transforms/IPO/PartialInlining.cpp b/lib/Transforms/IPO/PartialInlining.cpp new file mode 100644 index 00000000000..b3a2554039a --- /dev/null +++ b/lib/Transforms/IPO/PartialInlining.cpp @@ -0,0 +1,171 @@ +//===- 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. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "partialinlining" +#include "llvm/Transforms/IPO.h" +#include "llvm/Instructions.h" +#include "llvm/Module.h" +#include "llvm/Pass.h" +#include "llvm/Analysis/Dominators.h" +#include "llvm/Transforms/Utils/Cloning.h" +#include "llvm/Transforms/Utils/FunctionUtils.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/CFG.h" +using namespace llvm; + +namespace { + struct VISIBILITY_HIDDEN PartialInliner : public ModulePass { + virtual void getAnalysisUsage(AnalysisUsage &AU) const { } + static char ID; // Pass identification, replacement for typeid + PartialInliner() : ModulePass(&ID) {} + + bool runOnModule(Module& M); + + private: + Function* unswitchFunction(Function* F); + }; +} + +char PartialInliner::ID = 0; +static RegisterPass X("partial-inliner", "Partial Inliner"); + +ModulePass* llvm::createPartialInliningPass() { return new PartialInliner(); } + +Function* PartialInliner::unswitchFunction(Function* F) { + // First, verify that this function is an unswitching candidate... + BasicBlock* entryBlock = F->begin(); + if (!isa(entryBlock->getTerminator())) + return 0; + + BasicBlock* returnBlock = 0; + BasicBlock* nonReturnBlock = 0; + unsigned returnCount = 0; + for (succ_iterator SI = succ_begin(entryBlock), SE = succ_end(entryBlock); + SI != SE; ++SI) + if (isa((*SI)->getTerminator())) { + returnBlock = *SI; + returnCount++; + } else + nonReturnBlock = *SI; + + if (returnCount != 1) + return 0; + + // Clone the function, so that we can hack away on it. + DenseMap ValueMap; + Function* duplicateFunction = CloneFunction(F, ValueMap); + duplicateFunction->setLinkage(GlobalValue::InternalLinkage); + F->getParent()->getFunctionList().push_back(duplicateFunction); + BasicBlock* newEntryBlock = cast(ValueMap[entryBlock]); + BasicBlock* newReturnBlock = cast(ValueMap[returnBlock]); + BasicBlock* newNonReturnBlock = cast(ValueMap[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()); + BasicBlock::iterator I = preReturn->begin(); + BasicBlock::iterator Ins = newReturnBlock->begin(); + while (I != preReturn->end()) { + PHINode* OldPhi = dyn_cast(I); + if (!OldPhi) break; + + PHINode* retPhi = PHINode::Create(OldPhi->getType(), "", 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 toExtract; + toExtract.push_back(newNonReturnBlock); + for (Function::iterator FI = duplicateFunction->begin(), + FE = duplicateFunction->end(); FI != FE; ++FI) + if (&*FI != newEntryBlock && &*FI != newReturnBlock && + &*FI != newNonReturnBlock) + toExtract.push_back(FI); + + // The CodeExtractor needs a dominator tree. + DominatorTree DT; + DT.runOnFunction(*duplicateFunction); + + // Extract the body of the the if. + Function* extractedFunction = ExtractCodeRegion(DT, toExtract); + + // Inline the top-level if test into all callers. + std::vector Users(duplicateFunction->use_begin(), + duplicateFunction->use_end()); + for (std::vector::iterator UI = Users.begin(), UE = Users.end(); + UI != UE; ++UI) + if (CallInst* CI = dyn_cast(*UI)) + InlineFunction(CI); + else if (InvokeInst* II = dyn_cast(*UI)) + InlineFunction(II); + + // 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(); + + return extractedFunction; +} + +bool PartialInliner::runOnModule(Module& M) { + std::vector worklist; + worklist.reserve(M.size()); + for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI) + if (!FI->use_empty() && !FI->isDeclaration()) + worklist.push_back(&*FI); + + bool changed = false; + while (!worklist.empty()) { + Function* currFunc = worklist.back(); + worklist.pop_back(); + + if (currFunc->use_empty()) continue; + + bool recursive = false; + for (Function::use_iterator UI = currFunc->use_begin(), + UE = currFunc->use_end(); UI != UE; ++UI) + if (Instruction* I = dyn_cast(UI)) + if (I->getParent()->getParent() == currFunc) { + recursive = true; + break; + } + if (recursive) continue; + + + if (Function* newFunc = unswitchFunction(currFunc)) { + worklist.push_back(newFunc); + changed = true; + } + + } + + return changed; +} \ No newline at end of file -- 2.11.0