Index: /Users/rriddle/Desktop/llvm/llvm/include/llvm/Transforms/IPO/PartialInlining.h =================================================================== --- /Users/rriddle/Desktop/llvm/llvm/include/llvm/Transforms/IPO/PartialInlining.h +++ /Users/rriddle/Desktop/llvm/llvm/include/llvm/Transforms/IPO/PartialInlining.h @@ -24,9 +24,6 @@ class PartialInlinerPass : public PassInfoMixin { public: PreservedAnalyses run(Module &M, ModuleAnalysisManager &); - -private: - Function *unswitchFunction(Function *F); }; } #endif // LLVM_TRANSFORMS_IPO_PARTIALINLINING_H Index: /Users/rriddle/Desktop/llvm/llvm/lib/Transforms/IPO/PartialInlining.cpp =================================================================== --- /Users/rriddle/Desktop/llvm/llvm/lib/Transforms/IPO/PartialInlining.cpp +++ /Users/rriddle/Desktop/llvm/llvm/lib/Transforms/IPO/PartialInlining.cpp @@ -14,6 +14,7 @@ #include "llvm/Transforms/IPO/PartialInlining.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AssumptionCache.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Instructions.h" @@ -29,42 +30,75 @@ 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(); + } bool runOnModule(Module &M) override { if (skipModule(M)) return false; - ModuleAnalysisManager DummyMAM; - auto PA = Impl.run(M, DummyMAM); - return !PA.areAllPreserved(); + InlineFunctionInfo IFI; + IFI.ACT = &getAnalysis(); + return PartialInlinerImpl(IFI).run(M); } - -private: - PartialInlinerPass Impl; - }; +}; } -char PartialInlinerLegacyPass::ID = 0; -INITIALIZE_PASS(PartialInlinerLegacyPass, "partial-inliner", "Partial Inliner", - false, false) +bool PartialInlinerImpl::run(Module &M) { + std::vector worklist; + worklist.reserve(M.size()); + for (Function &F : M) + if (!F.use_empty() && !F.isDeclaration()) + worklist.push_back(&F); -ModulePass *llvm::createPartialInliningPass() { - return new PartialInlinerLegacyPass(); + 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(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; } -Function *PartialInlinerPass::unswitchFunction(Function *F) { +Function *PartialInlinerImpl::unswitchFunction(Function *F) { // First, verify that this function is an unswitching candidate... BasicBlock *entryBlock = &F->front(); BranchInst *BR = dyn_cast(entryBlock->getTerminator()); if (!BR || BR->isUnconditional()) return nullptr; - - BasicBlock* returnBlock = nullptr; - BasicBlock* nonReturnBlock = nullptr; + + BasicBlock *returnBlock = nullptr; + BasicBlock *nonReturnBlock = nullptr; unsigned returnCount = 0; for (BasicBlock *BB : successors(entryBlock)) { if (isa(BB->getTerminator())) { @@ -73,34 +107,35 @@ } 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); + Function *duplicateFunction = CloneFunction(F, VMap); duplicateFunction->setLinkage(GlobalValue::InternalLinkage); - BasicBlock* newEntryBlock = cast(VMap[entryBlock]); - BasicBlock* newReturnBlock = cast(VMap[returnBlock]); - BasicBlock* newNonReturnBlock = cast(VMap[nonReturnBlock]); - + BasicBlock *newEntryBlock = cast(VMap[entryBlock]); + BasicBlock *newReturnBlock = cast(VMap[returnBlock]); + BasicBlock *newNonReturnBlock = cast(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; + 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(I); - if (!OldPhi) break; + PHINode *OldPhi = dyn_cast(I); + if (!OldPhi) + break; PHINode *retPhi = PHINode::Create(OldPhi->getType(), 2, "", Ins); OldPhi->replaceAllUsesWith(retPhi); @@ -110,13 +145,13 @@ 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; + std::vector toExtract; toExtract.push_back(newNonReturnBlock); for (BasicBlock &BB : *duplicateFunction) if (&BB != newEntryBlock && &BB != newReturnBlock && @@ -128,11 +163,9 @@ DT.recalculate(*duplicateFunction); // Extract the body of the if. - Function* extractedFunction - = CodeExtractor(toExtract, &DT).extractCodeRegion(); - - InlineFunctionInfo IFI; - + Function *extractedFunction = + CodeExtractor(toExtract, &DT).extractCodeRegion(); + // Inline the top-level if test into all callers. std::vector Users(duplicateFunction->user_begin(), duplicateFunction->user_end()); @@ -141,49 +174,32 @@ InlineFunction(CI, IFI); else if (InvokeInst *II = dyn_cast(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; } -PreservedAnalyses PartialInlinerPass::run(Module &M, ModuleAnalysisManager &) { - std::vector worklist; - worklist.reserve(M.size()); - for (Function &F : M) - if (!F.use_empty() && !F.isDeclaration()) - worklist.push_back(&F); +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) - 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(U)) - if (I->getParent()->getParent() == currFunc) { - recursive = true; - break; - } - if (recursive) continue; - - - if (Function* newFunc = unswitchFunction(currFunc)) { - worklist.push_back(newFunc); - changed = true; - } - - } +ModulePass *llvm::createPartialInliningPass() { + return new PartialInlinerLegacyPass(); +} - if (changed) +PreservedAnalyses PartialInlinerPass::run(Module &M, + ModuleAnalysisManager &AM) { + InlineFunctionInfo IFI; + if (PartialInlinerImpl(IFI).run(M)) return PreservedAnalyses::none(); return PreservedAnalyses::all(); -} +} \ No newline at end of file Index: /Users/rriddle/Desktop/llvm/llvm/test/Transforms/Inline/partial-inline-act.ll =================================================================== --- /Users/rriddle/Desktop/llvm/llvm/test/Transforms/Inline/partial-inline-act.ll +++ /Users/rriddle/Desktop/llvm/llvm/test/Transforms/Inline/partial-inline-act.ll @@ -0,0 +1,20 @@ +; RUN: opt < %s -partial-inliner -disable-output +; This testcase tests the assumption cache + +define internal i32 @inlinedFunc(i1, i32* align 4) { +entry: + br i1 %0, label %if.then, label %return +if.then: + ; Dummy store to have more than 0 uses + store i32 10, i32* %1, align 4 + br label %return +return: ; preds = %entry + ret i32 0 +} + +define internal i32 @dummyCaller(i1, i32* align 2) { +entry: + %val = call i32 @inlinedFunc(i1 %0, i32* %1) + ret i32 %val +} +